2 * Copyright (c) 2000,2002,2005 Silicon Graphics, Inc.
3 * Copyright (c) 2013 Red Hat, Inc.
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
8 * published by the Free Software Foundation.
10 * This program is distributed in the hope that it would be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 #ifndef __XFS_DA_BTREE_H__
20 #define __XFS_DA_BTREE_H__
27 /*========================================================================
28 * Directory Structure when greater than XFS_LBSIZE(mp) bytes.
29 *========================================================================*/
32 * This structure is common to both leaf nodes and non-leaf nodes in the Btree.
34 * It is used to manage a doubly linked list of all blocks at the same
35 * level in the Btree, and to identify which type of block this is.
37 #define XFS_DA_NODE_MAGIC 0xfebe /* magic number: non-leaf blocks */
38 #define XFS_ATTR_LEAF_MAGIC 0xfbee /* magic number: attribute leaf blks */
39 #define XFS_DIR2_LEAF1_MAGIC 0xd2f1 /* magic number: v2 dirlf single blks */
40 #define XFS_DIR2_LEAFN_MAGIC 0xd2ff /* magic number: v2 dirlf multi blks */
42 typedef struct xfs_da_blkinfo
{
43 __be32 forw
; /* previous block in list */
44 __be32 back
; /* following block in list */
45 __be16 magic
; /* validity check on block */
46 __be16 pad
; /* unused */
50 * CRC enabled directory structure types
52 * The headers change size for the additional verification information, but
53 * otherwise the tree layouts and contents are unchanged. Hence the da btree
54 * code can use the struct xfs_da_blkinfo for manipulating the tree links and
55 * magic numbers without modification for both v2 and v3 nodes.
57 #define XFS_DA3_NODE_MAGIC 0x3ebe /* magic number: non-leaf blocks */
58 #define XFS_DIR3_LEAF1_MAGIC 0x3df1 /* magic number: v2 dirlf single blks */
59 #define XFS_DIR3_LEAFN_MAGIC 0x3dff /* magic number: v2 dirlf multi blks */
61 struct xfs_da3_blkinfo
{
63 * the node link manipulation code relies on the fact that the first
64 * element of this structure is the struct xfs_da_blkinfo so it can
65 * ignore the differences in the rest of the structures.
67 struct xfs_da_blkinfo hdr
;
68 __be32 crc
; /* CRC of block */
69 __be64 blkno
; /* first block of the buffer */
70 __be64 lsn
; /* sequence number of last write */
71 uuid_t uuid
; /* filesystem we belong to */
72 __be64 owner
; /* inode that owns the block */
76 * This is the structure of the root and intermediate nodes in the Btree.
77 * The leaf nodes are defined above.
79 * Entries are not packed.
81 * Since we have duplicate keys, use a binary search but always follow
82 * all match in the block, not just the first match found.
84 #define XFS_DA_NODE_MAXDEPTH 5 /* max depth of Btree */
86 typedef struct xfs_da_node_hdr
{
87 struct xfs_da_blkinfo info
; /* block type, links, etc. */
88 __be16 count
; /* count of active entries */
89 __be16 __level
; /* level above leaves (leaf == 0) */
92 struct xfs_da3_node_hdr
{
93 struct xfs_da3_blkinfo info
; /* block type, links, etc. */
94 __be16 count
; /* count of active entries */
95 __be16 __level
; /* level above leaves (leaf == 0) */
99 #define XFS_DA3_NODE_CRC_OFF (offsetof(struct xfs_da3_node_hdr, info.crc))
101 typedef struct xfs_da_node_entry
{
102 __be32 hashval
; /* hash value for this descendant */
103 __be32 before
; /* Btree block before this key */
104 } xfs_da_node_entry_t
;
106 typedef struct xfs_da_intnode
{
107 struct xfs_da_node_hdr hdr
;
108 struct xfs_da_node_entry __btree
[];
111 struct xfs_da3_intnode
{
112 struct xfs_da3_node_hdr hdr
;
113 struct xfs_da_node_entry __btree
[];
117 * In-core version of the node header to abstract the differences in the v2 and
118 * v3 disk format of the headers. Callers need to convert to/from disk format as
121 struct xfs_da3_icnode_hdr
{
129 extern void xfs_da3_node_hdr_from_disk(struct xfs_da3_icnode_hdr
*to
,
130 struct xfs_da_intnode
*from
);
131 extern void xfs_da3_node_hdr_to_disk(struct xfs_da_intnode
*to
,
132 struct xfs_da3_icnode_hdr
*from
);
135 xfs_da3_node_hdr_size(struct xfs_da_intnode
*dap
)
137 if (dap
->hdr
.info
.magic
== cpu_to_be16(XFS_DA3_NODE_MAGIC
))
138 return sizeof(struct xfs_da3_node_hdr
);
139 return sizeof(struct xfs_da_node_hdr
);
142 static inline struct xfs_da_node_entry
*
143 xfs_da3_node_tree_p(struct xfs_da_intnode
*dap
)
145 if (dap
->hdr
.info
.magic
== cpu_to_be16(XFS_DA3_NODE_MAGIC
)) {
146 struct xfs_da3_intnode
*dap3
= (struct xfs_da3_intnode
*)dap
;
147 return dap3
->__btree
;
152 extern void xfs_da3_intnode_from_disk(struct xfs_da3_icnode_hdr
*to
,
153 struct xfs_da_intnode
*from
);
154 extern void xfs_da3_intnode_to_disk(struct xfs_da_intnode
*to
,
155 struct xfs_da3_icnode_hdr
*from
);
157 #define XFS_LBSIZE(mp) (mp)->m_sb.sb_blocksize
159 /*========================================================================
160 * Btree searching and modification structure definitions.
161 *========================================================================*/
164 * Search comparison results
167 XFS_CMP_DIFFERENT
, /* names are completely different */
168 XFS_CMP_EXACT
, /* names are exactly the same */
169 XFS_CMP_CASE
/* names are same but differ in case */
173 * Structure to ease passing around component names.
175 typedef struct xfs_da_args
{
176 const __uint8_t
*name
; /* string (maybe not NULL terminated) */
177 int namelen
; /* length of string (maybe no NULL) */
178 __uint8_t
*value
; /* set of bytes (maybe contain NULLs) */
179 int valuelen
; /* length of value */
180 int flags
; /* argument flags (eg: ATTR_NOCREATE) */
181 xfs_dahash_t hashval
; /* hash value of name */
182 xfs_ino_t inumber
; /* input/output inode number */
183 struct xfs_inode
*dp
; /* directory inode to manipulate */
184 xfs_fsblock_t
*firstblock
; /* ptr to firstblock for bmap calls */
185 struct xfs_bmap_free
*flist
; /* ptr to freelist for bmap_finish */
186 struct xfs_trans
*trans
; /* current trans (changes over time) */
187 xfs_extlen_t total
; /* total blocks needed, for 1st bmap */
188 int whichfork
; /* data or attribute fork */
189 xfs_dablk_t blkno
; /* blkno of attr leaf of interest */
190 int index
; /* index of attr of interest in blk */
191 xfs_dablk_t rmtblkno
; /* remote attr value starting blkno */
192 int rmtblkcnt
; /* remote attr value block count */
193 xfs_dablk_t blkno2
; /* blkno of 2nd attr leaf of interest */
194 int index2
; /* index of 2nd attr in blk */
195 xfs_dablk_t rmtblkno2
; /* remote attr value starting blkno */
196 int rmtblkcnt2
; /* remote attr value block count */
197 int op_flags
; /* operation flags */
198 enum xfs_dacmp cmpresult
; /* name compare result for lookups */
204 #define XFS_DA_OP_JUSTCHECK 0x0001 /* check for ok with no space */
205 #define XFS_DA_OP_RENAME 0x0002 /* this is an atomic rename op */
206 #define XFS_DA_OP_ADDNAME 0x0004 /* this is an add operation */
207 #define XFS_DA_OP_OKNOENT 0x0008 /* lookup/add op, ENOENT ok, else die */
208 #define XFS_DA_OP_CILOOKUP 0x0010 /* lookup to return CI name if found */
210 #define XFS_DA_OP_FLAGS \
211 { XFS_DA_OP_JUSTCHECK, "JUSTCHECK" }, \
212 { XFS_DA_OP_RENAME, "RENAME" }, \
213 { XFS_DA_OP_ADDNAME, "ADDNAME" }, \
214 { XFS_DA_OP_OKNOENT, "OKNOENT" }, \
215 { XFS_DA_OP_CILOOKUP, "CILOOKUP" }
218 * Storage for holding state during Btree searches and split/join ops.
220 * Only need space for 5 intermediate nodes. With a minimum of 62-way
221 * fanout to the Btree, we can support over 900 million directory blocks,
222 * which is slightly more than enough.
224 typedef struct xfs_da_state_blk
{
225 struct xfs_buf
*bp
; /* buffer containing block */
226 xfs_dablk_t blkno
; /* filesystem blkno of buffer */
227 xfs_daddr_t disk_blkno
; /* on-disk blkno (in BBs) of buffer */
228 int index
; /* relevant index into block */
229 xfs_dahash_t hashval
; /* last hash value in block */
230 int magic
; /* blk's magic number, ie: blk type */
231 } xfs_da_state_blk_t
;
233 typedef struct xfs_da_state_path
{
234 int active
; /* number of active levels */
235 xfs_da_state_blk_t blk
[XFS_DA_NODE_MAXDEPTH
];
236 } xfs_da_state_path_t
;
238 typedef struct xfs_da_state
{
239 xfs_da_args_t
*args
; /* filename arguments */
240 struct xfs_mount
*mp
; /* filesystem mount point */
241 unsigned int blocksize
; /* logical block size */
242 unsigned int node_ents
; /* how many entries in danode */
243 xfs_da_state_path_t path
; /* search/split paths */
244 xfs_da_state_path_t altpath
; /* alternate path for join */
245 unsigned char inleaf
; /* insert into 1->lf, 0->splf */
246 unsigned char extravalid
; /* T/F: extrablk is in use */
247 unsigned char extraafter
; /* T/F: extrablk is after new */
248 xfs_da_state_blk_t extrablk
; /* for double-splits on leaves */
249 /* for dirv2 extrablk is data */
253 * Utility macros to aid in logging changed structure fields.
255 #define XFS_DA_LOGOFF(BASE, ADDR) ((char *)(ADDR) - (char *)(BASE))
256 #define XFS_DA_LOGRANGE(BASE, ADDR, SIZE) \
257 (uint)(XFS_DA_LOGOFF(BASE, ADDR)), \
258 (uint)(XFS_DA_LOGOFF(BASE, ADDR)+(SIZE)-1)
261 * Name ops for directory and/or attr name operations
264 xfs_dahash_t (*hashname
)(struct xfs_name
*);
265 enum xfs_dacmp (*compname
)(struct xfs_da_args
*,
266 const unsigned char *, int);
270 /*========================================================================
271 * Function prototypes.
272 *========================================================================*/
275 * Routines used for growing the Btree.
277 int xfs_da3_node_create(struct xfs_da_args
*args
, xfs_dablk_t blkno
,
278 int level
, struct xfs_buf
**bpp
, int whichfork
);
279 int xfs_da3_split(xfs_da_state_t
*state
);
282 * Routines used for shrinking the Btree.
284 int xfs_da3_join(xfs_da_state_t
*state
);
285 void xfs_da3_fixhashpath(struct xfs_da_state
*state
,
286 struct xfs_da_state_path
*path_to_to_fix
);
289 * Routines used for finding things in the Btree.
291 int xfs_da3_node_lookup_int(xfs_da_state_t
*state
, int *result
);
292 int xfs_da3_path_shift(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
,
293 int forward
, int release
, int *result
);
297 int xfs_da3_blk_link(xfs_da_state_t
*state
, xfs_da_state_blk_t
*old_blk
,
298 xfs_da_state_blk_t
*new_blk
);
299 int xfs_da3_node_read(struct xfs_trans
*tp
, struct xfs_inode
*dp
,
300 xfs_dablk_t bno
, xfs_daddr_t mappedbno
,
301 struct xfs_buf
**bpp
, int which_fork
);
306 int xfs_da_grow_inode(xfs_da_args_t
*args
, xfs_dablk_t
*new_blkno
);
307 int xfs_da_grow_inode_int(struct xfs_da_args
*args
, xfs_fileoff_t
*bno
,
309 int xfs_da_get_buf(struct xfs_trans
*trans
, struct xfs_inode
*dp
,
310 xfs_dablk_t bno
, xfs_daddr_t mappedbno
,
311 struct xfs_buf
**bp
, int whichfork
);
312 int xfs_da_read_buf(struct xfs_trans
*trans
, struct xfs_inode
*dp
,
313 xfs_dablk_t bno
, xfs_daddr_t mappedbno
,
314 struct xfs_buf
**bpp
, int whichfork
,
315 const struct xfs_buf_ops
*ops
);
316 xfs_daddr_t
xfs_da_reada_buf(struct xfs_trans
*trans
, struct xfs_inode
*dp
,
317 xfs_dablk_t bno
, xfs_daddr_t mapped_bno
,
318 int whichfork
, const struct xfs_buf_ops
*ops
);
319 int xfs_da_shrink_inode(xfs_da_args_t
*args
, xfs_dablk_t dead_blkno
,
320 struct xfs_buf
*dead_buf
);
322 uint
xfs_da_hashname(const __uint8_t
*name_string
, int name_length
);
323 enum xfs_dacmp
xfs_da_compname(struct xfs_da_args
*args
,
324 const unsigned char *name
, int len
);
327 xfs_da_state_t
*xfs_da_state_alloc(void);
328 void xfs_da_state_free(xfs_da_state_t
*state
);
330 extern struct kmem_zone
*xfs_da_state_zone
;
331 extern const struct xfs_nameops xfs_default_nameops
;
333 #endif /* __XFS_DA_BTREE_H__ */