Blame view
fs/xfs/xfs_da_btree.h
10.1 KB
1da177e4c Linux-2.6.12-rc2 |
1 |
/* |
7b7187698 [XFS] Update lice... |
2 3 |
* Copyright (c) 2000,2002,2005 Silicon Graphics, Inc. * All Rights Reserved. |
1da177e4c Linux-2.6.12-rc2 |
4 |
* |
7b7187698 [XFS] Update lice... |
5 6 |
* This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as |
1da177e4c Linux-2.6.12-rc2 |
7 8 |
* published by the Free Software Foundation. * |
7b7187698 [XFS] Update lice... |
9 10 11 12 |
* This program is distributed in the hope that it would be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. |
1da177e4c Linux-2.6.12-rc2 |
13 |
* |
7b7187698 [XFS] Update lice... |
14 15 16 |
* You should have received a copy of the GNU General Public License * along with this program; if not, write the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
1da177e4c Linux-2.6.12-rc2 |
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
*/ #ifndef __XFS_DA_BTREE_H__ #define __XFS_DA_BTREE_H__ struct xfs_buf; struct xfs_bmap_free; struct xfs_inode; struct xfs_mount; struct xfs_trans; struct zone; /*======================================================================== * Directory Structure when greater than XFS_LBSIZE(mp) bytes. *========================================================================*/ /* * This structure is common to both leaf nodes and non-leaf nodes in the Btree. * * Is is used to manage a doubly linked list of all blocks at the same * level in the Btree, and to identify which type of block this is. */ #define XFS_DA_NODE_MAGIC 0xfebe /* magic number: non-leaf blocks */ |
1da177e4c Linux-2.6.12-rc2 |
39 40 41 |
#define XFS_ATTR_LEAF_MAGIC 0xfbee /* magic number: attribute leaf blks */ #define XFS_DIR2_LEAF1_MAGIC 0xd2f1 /* magic number: v2 dirlf single blks */ #define XFS_DIR2_LEAFN_MAGIC 0xd2ff /* magic number: v2 dirlf multi blks */ |
1da177e4c Linux-2.6.12-rc2 |
42 |
typedef struct xfs_da_blkinfo { |
89da05442 [XFS] endianess a... |
43 44 45 46 |
__be32 forw; /* previous block in list */ __be32 back; /* following block in list */ __be16 magic; /* validity check on block */ __be16 pad; /* unused */ |
1da177e4c Linux-2.6.12-rc2 |
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
} xfs_da_blkinfo_t; /* * This is the structure of the root and intermediate nodes in the Btree. * The leaf nodes are defined above. * * Entries are not packed. * * Since we have duplicate keys, use a binary search but always follow * all match in the block, not just the first match found. */ #define XFS_DA_NODE_MAXDEPTH 5 /* max depth of Btree */ typedef struct xfs_da_intnode { struct xfs_da_node_hdr { /* constant-structure header block */ xfs_da_blkinfo_t info; /* block type, links, etc. */ |
fac80cce0 [XFS] endianess a... |
63 64 |
__be16 count; /* count of active entries */ __be16 level; /* level above leaves (leaf == 0) */ |
1da177e4c Linux-2.6.12-rc2 |
65 66 |
} hdr; struct xfs_da_node_entry { |
403432dcb [XFS] endianess a... |
67 68 |
__be32 hashval; /* hash value for this descendant */ __be32 before; /* Btree block before this key */ |
1da177e4c Linux-2.6.12-rc2 |
69 70 71 72 |
} btree[1]; /* variable sized array of keys */ } xfs_da_intnode_t; typedef struct xfs_da_node_hdr xfs_da_node_hdr_t; typedef struct xfs_da_node_entry xfs_da_node_entry_t; |
a844f4510 [XFS] Remove xfs_... |
73 |
#define XFS_LBSIZE(mp) (mp)->m_sb.sb_blocksize |
1da177e4c Linux-2.6.12-rc2 |
74 75 76 77 78 79 |
/*======================================================================== * Btree searching and modification structure definitions. *========================================================================*/ /* |
5163f95a0 [XFS] Name operat... |
80 81 82 83 84 85 86 87 88 |
* Search comparison results */ enum xfs_dacmp { XFS_CMP_DIFFERENT, /* names are completely different */ XFS_CMP_EXACT, /* names are exactly the same */ XFS_CMP_CASE /* names are same but differ in case */ }; /* |
1da177e4c Linux-2.6.12-rc2 |
89 90 91 |
* Structure to ease passing around component names. */ typedef struct xfs_da_args { |
a56877873 xfs: remove uchar... |
92 |
const __uint8_t *name; /* string (maybe not NULL terminated) */ |
1da177e4c Linux-2.6.12-rc2 |
93 |
int namelen; /* length of string (maybe no NULL) */ |
a56877873 xfs: remove uchar... |
94 |
__uint8_t *value; /* set of bytes (maybe contain NULLs) */ |
1da177e4c Linux-2.6.12-rc2 |
95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
int valuelen; /* length of value */ int flags; /* argument flags (eg: ATTR_NOCREATE) */ xfs_dahash_t hashval; /* hash value of name */ xfs_ino_t inumber; /* input/output inode number */ struct xfs_inode *dp; /* directory inode to manipulate */ xfs_fsblock_t *firstblock; /* ptr to firstblock for bmap calls */ struct xfs_bmap_free *flist; /* ptr to freelist for bmap_finish */ struct xfs_trans *trans; /* current trans (changes over time) */ xfs_extlen_t total; /* total blocks needed, for 1st bmap */ int whichfork; /* data or attribute fork */ xfs_dablk_t blkno; /* blkno of attr leaf of interest */ int index; /* index of attr of interest in blk */ xfs_dablk_t rmtblkno; /* remote attr value starting blkno */ int rmtblkcnt; /* remote attr value block count */ xfs_dablk_t blkno2; /* blkno of 2nd attr leaf of interest */ int index2; /* index of 2nd attr in blk */ xfs_dablk_t rmtblkno2; /* remote attr value starting blkno */ int rmtblkcnt2; /* remote attr value block count */ |
6a178100a [XFS] Add op_flag... |
113 |
int op_flags; /* operation flags */ |
5163f95a0 [XFS] Name operat... |
114 |
enum xfs_dacmp cmpresult; /* name compare result for lookups */ |
1da177e4c Linux-2.6.12-rc2 |
115 116 117 |
} xfs_da_args_t; /* |
6a178100a [XFS] Add op_flag... |
118 119 120 121 122 123 |
* Operation flags: */ #define XFS_DA_OP_JUSTCHECK 0x0001 /* check for ok with no space */ #define XFS_DA_OP_RENAME 0x0002 /* this is an atomic rename op */ #define XFS_DA_OP_ADDNAME 0x0004 /* this is an add operation */ #define XFS_DA_OP_OKNOENT 0x0008 /* lookup/add op, ENOENT ok, else die */ |
384f3ced0 [XFS] Return case... |
124 |
#define XFS_DA_OP_CILOOKUP 0x0010 /* lookup to return CI name if found */ |
6a178100a [XFS] Add op_flag... |
125 |
|
0b1b213fc xfs: event tracin... |
126 127 128 129 130 131 |
#define XFS_DA_OP_FLAGS \ { XFS_DA_OP_JUSTCHECK, "JUSTCHECK" }, \ { XFS_DA_OP_RENAME, "RENAME" }, \ { XFS_DA_OP_ADDNAME, "ADDNAME" }, \ { XFS_DA_OP_OKNOENT, "OKNOENT" }, \ { XFS_DA_OP_CILOOKUP, "CILOOKUP" } |
6a178100a [XFS] Add op_flag... |
132 |
/* |
1da177e4c Linux-2.6.12-rc2 |
133 134 135 136 137 138 139 140 141 142 143 144 |
* Structure to describe buffer(s) for a block. * This is needed in the directory version 2 format case, when * multiple non-contiguous fsblocks might be needed to cover one * logical directory block. * If the buffer count is 1 then the data pointer points to the * same place as the b_addr field for the buffer, else to kmem_alloced memory. */ typedef struct xfs_dabuf { int nbuf; /* number of buffer pointers present */ short dirty; /* data needs to be copied back */ short bbcount; /* how large is data in bbs */ void *data; /* pointer for buffers' data */ |
1da177e4c Linux-2.6.12-rc2 |
145 146 147 148 |
struct xfs_buf *bps[1]; /* actually nbuf of these */ } xfs_dabuf_t; #define XFS_DA_BUF_SIZE(n) \ (sizeof(xfs_dabuf_t) + sizeof(struct xfs_buf *) * ((n) - 1)) |
1da177e4c Linux-2.6.12-rc2 |
149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 |
/* * Storage for holding state during Btree searches and split/join ops. * * Only need space for 5 intermediate nodes. With a minimum of 62-way * fanout to the Btree, we can support over 900 million directory blocks, * which is slightly more than enough. */ typedef struct xfs_da_state_blk { xfs_dabuf_t *bp; /* buffer containing block */ xfs_dablk_t blkno; /* filesystem blkno of buffer */ xfs_daddr_t disk_blkno; /* on-disk blkno (in BBs) of buffer */ int index; /* relevant index into block */ xfs_dahash_t hashval; /* last hash value in block */ int magic; /* blk's magic number, ie: blk type */ } xfs_da_state_blk_t; typedef struct xfs_da_state_path { int active; /* number of active levels */ xfs_da_state_blk_t blk[XFS_DA_NODE_MAXDEPTH]; } xfs_da_state_path_t; typedef struct xfs_da_state { xfs_da_args_t *args; /* filename arguments */ struct xfs_mount *mp; /* filesystem mount point */ unsigned int blocksize; /* logical block size */ unsigned int node_ents; /* how many entries in danode */ xfs_da_state_path_t path; /* search/split paths */ xfs_da_state_path_t altpath; /* alternate path for join */ unsigned char inleaf; /* insert into 1->lf, 0->splf */ unsigned char extravalid; /* T/F: extrablk is in use */ unsigned char extraafter; /* T/F: extrablk is after new */ |
9da096fd1 xfs: fix various ... |
180 |
xfs_da_state_blk_t extrablk; /* for double-splits on leaves */ |
1da177e4c Linux-2.6.12-rc2 |
181 182 183 184 185 186 187 188 189 190 |
/* for dirv2 extrablk is data */ } xfs_da_state_t; /* * Utility macros to aid in logging changed structure fields. */ #define XFS_DA_LOGOFF(BASE, ADDR) ((char *)(ADDR) - (char *)(BASE)) #define XFS_DA_LOGRANGE(BASE, ADDR, SIZE) \ (uint)(XFS_DA_LOGOFF(BASE, ADDR)), \ (uint)(XFS_DA_LOGOFF(BASE, ADDR)+(SIZE)-1) |
5163f95a0 [XFS] Name operat... |
191 192 193 194 195 |
/* * Name ops for directory and/or attr name operations */ struct xfs_nameops { xfs_dahash_t (*hashname)(struct xfs_name *); |
2bc754213 xfs: convert dirn... |
196 197 |
enum xfs_dacmp (*compname)(struct xfs_da_args *, const unsigned char *, int); |
5163f95a0 [XFS] Name operat... |
198 |
}; |
1da177e4c Linux-2.6.12-rc2 |
199 |
|
1da177e4c Linux-2.6.12-rc2 |
200 |
/*======================================================================== |
847fff5ca [XFS] Sync up ker... |
201 |
* Function prototypes. |
1da177e4c Linux-2.6.12-rc2 |
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 |
*========================================================================*/ /* * Routines used for growing the Btree. */ int xfs_da_node_create(xfs_da_args_t *args, xfs_dablk_t blkno, int level, xfs_dabuf_t **bpp, int whichfork); int xfs_da_split(xfs_da_state_t *state); /* * Routines used for shrinking the Btree. */ int xfs_da_join(xfs_da_state_t *state); void xfs_da_fixhashpath(xfs_da_state_t *state, xfs_da_state_path_t *path_to_to_fix); /* * Routines used for finding things in the Btree. */ int xfs_da_node_lookup_int(xfs_da_state_t *state, int *result); int xfs_da_path_shift(xfs_da_state_t *state, xfs_da_state_path_t *path, int forward, int release, int *result); /* * Utility routines. */ |
1da177e4c Linux-2.6.12-rc2 |
227 228 229 230 231 232 233 |
int xfs_da_blk_link(xfs_da_state_t *state, xfs_da_state_blk_t *old_blk, xfs_da_state_blk_t *new_blk); /* * Utility routines. */ int xfs_da_grow_inode(xfs_da_args_t *args, xfs_dablk_t *new_blkno); |
77936d028 xfs: factor out x... |
234 235 |
int xfs_da_grow_inode_int(struct xfs_da_args *args, xfs_fileoff_t *bno, int count); |
1da177e4c Linux-2.6.12-rc2 |
236 237 238 239 240 241 242 243 244 245 |
int xfs_da_get_buf(struct xfs_trans *trans, struct xfs_inode *dp, xfs_dablk_t bno, xfs_daddr_t mappedbno, xfs_dabuf_t **bp, int whichfork); int xfs_da_read_buf(struct xfs_trans *trans, struct xfs_inode *dp, xfs_dablk_t bno, xfs_daddr_t mappedbno, xfs_dabuf_t **bpp, int whichfork); xfs_daddr_t xfs_da_reada_buf(struct xfs_trans *trans, struct xfs_inode *dp, xfs_dablk_t bno, int whichfork); int xfs_da_shrink_inode(xfs_da_args_t *args, xfs_dablk_t dead_blkno, xfs_dabuf_t *dead_buf); |
a56877873 xfs: remove uchar... |
246 |
uint xfs_da_hashname(const __uint8_t *name_string, int name_length); |
5163f95a0 [XFS] Name operat... |
247 |
enum xfs_dacmp xfs_da_compname(struct xfs_da_args *args, |
2bc754213 xfs: convert dirn... |
248 |
const unsigned char *name, int len); |
5163f95a0 [XFS] Name operat... |
249 |
|
1da177e4c Linux-2.6.12-rc2 |
250 251 |
xfs_da_state_t *xfs_da_state_alloc(void); void xfs_da_state_free(xfs_da_state_t *state); |
1da177e4c Linux-2.6.12-rc2 |
252 253 254 255 256 257 258 259 260 |
void xfs_da_buf_done(xfs_dabuf_t *dabuf); void xfs_da_log_buf(struct xfs_trans *tp, xfs_dabuf_t *dabuf, uint first, uint last); void xfs_da_brelse(struct xfs_trans *tp, xfs_dabuf_t *dabuf); void xfs_da_binval(struct xfs_trans *tp, xfs_dabuf_t *dabuf); xfs_daddr_t xfs_da_blkno(xfs_dabuf_t *dabuf); extern struct kmem_zone *xfs_da_state_zone; |
a8272ce0c [XFS] Fix up spar... |
261 |
extern struct kmem_zone *xfs_dabuf_zone; |
24418492a xfs: move declara... |
262 |
extern const struct xfs_nameops xfs_default_nameops; |
1da177e4c Linux-2.6.12-rc2 |
263 264 |
#endif /* __XFS_DA_BTREE_H__ */ |