1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000,2002,2005 Silicon Graphics, Inc.
4 * Copyright (c) 2013 Red Hat, Inc.
7 #ifndef __XFS_DA_BTREE_H__
8 #define __XFS_DA_BTREE_H__
17 * Directory/attribute geometry information. There will be one of these for each
18 * data fork type, and it will be passed around via the xfs_da_args. Global
19 * structures will be attached to the xfs_mount.
21 struct xfs_da_geometry
{
22 int blksize
; /* da block size in bytes */
23 int fsbcount
; /* da block size in filesystem blocks */
24 uint8_t fsblog
; /* log2 of _filesystem_ block size */
25 uint8_t blklog
; /* log2 of da block size */
26 uint node_ents
; /* # of entries in a danode */
27 int magicpct
; /* 37% of block size in bytes */
28 xfs_dablk_t datablk
; /* blockno of dir data v2 */
29 xfs_dablk_t leafblk
; /* blockno of leaf data v2 */
30 xfs_dablk_t freeblk
; /* blockno of free data v2 */
33 /*========================================================================
34 * Btree searching and modification structure definitions.
35 *========================================================================*/
38 * Search comparison results
41 XFS_CMP_DIFFERENT
, /* names are completely different */
42 XFS_CMP_EXACT
, /* names are exactly the same */
43 XFS_CMP_CASE
/* names are same but differ in case */
47 * Structure to ease passing around component names.
49 typedef struct xfs_da_args
{
50 struct xfs_da_geometry
*geo
; /* da block geometry */
51 const uint8_t *name
; /* string (maybe not NULL terminated) */
52 int namelen
; /* length of string (maybe no NULL) */
53 uint8_t filetype
; /* filetype of inode for directories */
54 uint8_t *value
; /* set of bytes (maybe contain NULLs) */
55 int valuelen
; /* length of value */
56 int flags
; /* argument flags (eg: ATTR_NOCREATE) */
57 xfs_dahash_t hashval
; /* hash value of name */
58 xfs_ino_t inumber
; /* input/output inode number */
59 struct xfs_inode
*dp
; /* directory inode to manipulate */
60 struct xfs_trans
*trans
; /* current trans (changes over time) */
61 xfs_extlen_t total
; /* total blocks needed, for 1st bmap */
62 int whichfork
; /* data or attribute fork */
63 xfs_dablk_t blkno
; /* blkno of attr leaf of interest */
64 int index
; /* index of attr of interest in blk */
65 xfs_dablk_t rmtblkno
; /* remote attr value starting blkno */
66 int rmtblkcnt
; /* remote attr value block count */
67 int rmtvaluelen
; /* remote attr value length in bytes */
68 xfs_dablk_t blkno2
; /* blkno of 2nd attr leaf of interest */
69 int index2
; /* index of 2nd attr in blk */
70 xfs_dablk_t rmtblkno2
; /* remote attr value starting blkno */
71 int rmtblkcnt2
; /* remote attr value block count */
72 int rmtvaluelen2
; /* remote attr value length in bytes */
73 int op_flags
; /* operation flags */
74 enum xfs_dacmp cmpresult
; /* name compare result for lookups */
80 #define XFS_DA_OP_JUSTCHECK 0x0001 /* check for ok with no space */
81 #define XFS_DA_OP_RENAME 0x0002 /* this is an atomic rename op */
82 #define XFS_DA_OP_ADDNAME 0x0004 /* this is an add operation */
83 #define XFS_DA_OP_OKNOENT 0x0008 /* lookup/add op, ENOENT ok, else die */
84 #define XFS_DA_OP_CILOOKUP 0x0010 /* lookup to return CI name if found */
86 #define XFS_DA_OP_FLAGS \
87 { XFS_DA_OP_JUSTCHECK, "JUSTCHECK" }, \
88 { XFS_DA_OP_RENAME, "RENAME" }, \
89 { XFS_DA_OP_ADDNAME, "ADDNAME" }, \
90 { XFS_DA_OP_OKNOENT, "OKNOENT" }, \
91 { XFS_DA_OP_CILOOKUP, "CILOOKUP" }
94 * Storage for holding state during Btree searches and split/join ops.
96 * Only need space for 5 intermediate nodes. With a minimum of 62-way
97 * fanout to the Btree, we can support over 900 million directory blocks,
98 * which is slightly more than enough.
100 typedef struct xfs_da_state_blk
{
101 struct xfs_buf
*bp
; /* buffer containing block */
102 xfs_dablk_t blkno
; /* filesystem blkno of buffer */
103 xfs_daddr_t disk_blkno
; /* on-disk blkno (in BBs) of buffer */
104 int index
; /* relevant index into block */
105 xfs_dahash_t hashval
; /* last hash value in block */
106 int magic
; /* blk's magic number, ie: blk type */
107 } xfs_da_state_blk_t
;
109 typedef struct xfs_da_state_path
{
110 int active
; /* number of active levels */
111 xfs_da_state_blk_t blk
[XFS_DA_NODE_MAXDEPTH
];
112 } xfs_da_state_path_t
;
114 typedef struct xfs_da_state
{
115 xfs_da_args_t
*args
; /* filename arguments */
116 struct xfs_mount
*mp
; /* filesystem mount point */
117 xfs_da_state_path_t path
; /* search/split paths */
118 xfs_da_state_path_t altpath
; /* alternate path for join */
119 unsigned char inleaf
; /* insert into 1->lf, 0->splf */
120 unsigned char extravalid
; /* T/F: extrablk is in use */
121 unsigned char extraafter
; /* T/F: extrablk is after new */
122 xfs_da_state_blk_t extrablk
; /* for double-splits on leaves */
123 /* for dirv2 extrablk is data */
127 * Utility macros to aid in logging changed structure fields.
129 #define XFS_DA_LOGOFF(BASE, ADDR) ((char *)(ADDR) - (char *)(BASE))
130 #define XFS_DA_LOGRANGE(BASE, ADDR, SIZE) \
131 (uint)(XFS_DA_LOGOFF(BASE, ADDR)), \
132 (uint)(XFS_DA_LOGOFF(BASE, ADDR)+(SIZE)-1)
135 * Name ops for directory and/or attr name operations
138 xfs_dahash_t (*hashname
)(struct xfs_name
*);
139 enum xfs_dacmp (*compname
)(struct xfs_da_args
*,
140 const unsigned char *, int);
144 /*========================================================================
145 * Function prototypes.
146 *========================================================================*/
149 * Routines used for growing the Btree.
151 int xfs_da3_node_create(struct xfs_da_args
*args
, xfs_dablk_t blkno
,
152 int level
, struct xfs_buf
**bpp
, int whichfork
);
153 int xfs_da3_split(xfs_da_state_t
*state
);
156 * Routines used for shrinking the Btree.
158 int xfs_da3_join(xfs_da_state_t
*state
);
159 void xfs_da3_fixhashpath(struct xfs_da_state
*state
,
160 struct xfs_da_state_path
*path_to_to_fix
);
163 * Routines used for finding things in the Btree.
165 int xfs_da3_node_lookup_int(xfs_da_state_t
*state
, int *result
);
166 int xfs_da3_path_shift(xfs_da_state_t
*state
, xfs_da_state_path_t
*path
,
167 int forward
, int release
, int *result
);
171 int xfs_da3_blk_link(xfs_da_state_t
*state
, xfs_da_state_blk_t
*old_blk
,
172 xfs_da_state_blk_t
*new_blk
);
173 int xfs_da3_node_read(struct xfs_trans
*tp
, struct xfs_inode
*dp
,
174 xfs_dablk_t bno
, xfs_daddr_t mappedbno
,
175 struct xfs_buf
**bpp
, int which_fork
);
180 int xfs_da_grow_inode(xfs_da_args_t
*args
, xfs_dablk_t
*new_blkno
);
181 int xfs_da_grow_inode_int(struct xfs_da_args
*args
, xfs_fileoff_t
*bno
,
183 int xfs_da_get_buf(struct xfs_trans
*trans
, struct xfs_inode
*dp
,
184 xfs_dablk_t bno
, xfs_daddr_t mappedbno
,
185 struct xfs_buf
**bp
, int whichfork
);
186 int xfs_da_read_buf(struct xfs_trans
*trans
, struct xfs_inode
*dp
,
187 xfs_dablk_t bno
, xfs_daddr_t mappedbno
,
188 struct xfs_buf
**bpp
, int whichfork
,
189 const struct xfs_buf_ops
*ops
);
190 int xfs_da_reada_buf(struct xfs_inode
*dp
, xfs_dablk_t bno
,
191 xfs_daddr_t mapped_bno
, int whichfork
,
192 const struct xfs_buf_ops
*ops
);
193 int xfs_da_shrink_inode(xfs_da_args_t
*args
, xfs_dablk_t dead_blkno
,
194 struct xfs_buf
*dead_buf
);
196 uint
xfs_da_hashname(const uint8_t *name_string
, int name_length
);
197 enum xfs_dacmp
xfs_da_compname(struct xfs_da_args
*args
,
198 const unsigned char *name
, int len
);
201 xfs_da_state_t
*xfs_da_state_alloc(void);
202 void xfs_da_state_free(xfs_da_state_t
*state
);
204 extern struct kmem_zone
*xfs_da_state_zone
;
205 extern const struct xfs_nameops xfs_default_nameops
;
207 #endif /* __XFS_DA_BTREE_H__ */