]>
Commit | Line | Data |
---|---|---|
2bd0ea18 | 1 | /* |
854f7c66 | 2 | * Copyright (c) 2000, 2002 Silicon Graphics, Inc. All Rights Reserved. |
5000d01d | 3 | * |
2bd0ea18 NS |
4 | * This program is free software; you can redistribute it and/or modify it |
5 | * under the terms of version 2 of the GNU General Public License as | |
6 | * published by the Free Software Foundation. | |
5000d01d | 7 | * |
2bd0ea18 NS |
8 | * This program is distributed in the hope that it would be useful, but |
9 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
5000d01d | 11 | * |
2bd0ea18 NS |
12 | * Further, this software is distributed without any warranty that it is |
13 | * free of the rightful claim of any third person regarding infringement | |
dfc130f3 | 14 | * or the like. Any license provided herein, whether implied or |
2bd0ea18 NS |
15 | * otherwise, applies only to this software file. Patent licenses, if |
16 | * any, provided herein do not apply to combinations of this program with | |
17 | * other software, or any other product whatsoever. | |
5000d01d | 18 | * |
2bd0ea18 NS |
19 | * You should have received a copy of the GNU General Public License along |
20 | * with this program; if not, write the Free Software Foundation, Inc., 59 | |
21 | * Temple Place - Suite 330, Boston MA 02111-1307, USA. | |
5000d01d | 22 | * |
2bd0ea18 NS |
23 | * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy, |
24 | * Mountain View, CA 94043, or: | |
5000d01d SL |
25 | * |
26 | * http://www.sgi.com | |
27 | * | |
28 | * For further information regarding this notice, see: | |
29 | * | |
2bd0ea18 NS |
30 | * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/ |
31 | */ | |
32 | #ifndef __XFS_ATTR_LEAF_H__ | |
dfc130f3 | 33 | #define __XFS_ATTR_LEAF_H__ |
2bd0ea18 NS |
34 | |
35 | /* | |
36 | * Attribute storage layout, internal structure, access macros, etc. | |
37 | * | |
38 | * Attribute lists are structured around Btrees where all the data | |
39 | * elements are in the leaf nodes. Attribute names are hashed into an int, | |
40 | * then that int is used as the index into the Btree. Since the hashval | |
dfc130f3 | 41 | * of an attribute name may not be unique, we may have duplicate keys. The |
2bd0ea18 NS |
42 | * internal links in the Btree are logical block offsets into the file. |
43 | */ | |
44 | ||
45 | struct attrlist; | |
46 | struct attrlist_cursor_kern; | |
47 | struct xfs_dabuf; | |
48 | struct xfs_da_args; | |
49 | struct xfs_da_state; | |
50 | struct xfs_da_state_blk; | |
51 | struct xfs_inode; | |
52 | struct xfs_trans; | |
53 | ||
54 | /*======================================================================== | |
55 | * Attribute structure when equal to XFS_LBSIZE(mp) bytes. | |
56 | *========================================================================*/ | |
57 | ||
58 | /* | |
59 | * This is the structure of the leaf nodes in the Btree. | |
60 | * | |
dfc130f3 | 61 | * Struct leaf_entry's are packed from the top. Name/values grow from the |
2bd0ea18 NS |
62 | * bottom but are not packed. The freemap contains run-length-encoded entries |
63 | * for the free bytes after the leaf_entry's, but only the N largest such, | |
64 | * smaller runs are dropped. When the freemap doesn't show enough space | |
65 | * for an allocation, we compact the name/value area and try again. If we | |
66 | * still don't have enough space, then we have to split the block. The | |
67 | * name/value structs (both local and remote versions) must be 32bit aligned. | |
68 | * | |
69 | * Since we have duplicate hash keys, for each key that matches, compare | |
70 | * the actual name string. The root and intermediate node search always | |
71 | * takes the first-in-the-block key match found, so we should only have | |
72 | * to work "forw"ard. If none matches, continue with the "forw"ard leaf | |
73 | * nodes until the hash key changes or the attribute name is found. | |
74 | * | |
75 | * We store the fact that an attribute is a ROOT versus USER attribute in | |
76 | * the leaf_entry. The namespaces are independent only because we also look | |
77 | * at the root/user bit when we are looking for a matching attribute name. | |
78 | * | |
dfc130f3 | 79 | * We also store a "incomplete" bit in the leaf_entry. It shows that an |
2bd0ea18 NS |
80 | * attribute is in the middle of being created and should not be shown to |
81 | * the user if we crash during the time that the bit is set. We clear the | |
dfc130f3 | 82 | * bit when we have finished setting up the attribute. We do this because |
2bd0ea18 NS |
83 | * we cannot create some large attributes inside a single transaction, and we |
84 | * need some indication that we weren't finished if we crash in the middle. | |
85 | */ | |
86 | #define XFS_ATTR_LEAF_MAPSIZE 3 /* how many freespace slots */ | |
87 | ||
88 | typedef struct xfs_attr_leafblock { | |
89 | struct xfs_attr_leaf_hdr { /* constant-structure header block */ | |
90 | xfs_da_blkinfo_t info; /* block type, links, etc. */ | |
91 | __uint16_t count; /* count of active leaf_entry's */ | |
92 | __uint16_t usedbytes; /* num bytes of names/values stored */ | |
93 | __uint16_t firstused; /* first used byte in name area */ | |
94 | __uint8_t holes; /* != 0 if blk needs compaction */ | |
95 | __uint8_t pad1; | |
96 | struct xfs_attr_leaf_map { /* RLE map of free bytes */ | |
97 | __uint16_t base; /* base of free region */ | |
98 | __uint16_t size; /* length of free region */ | |
99 | } freemap[XFS_ATTR_LEAF_MAPSIZE]; /* N largest free regions */ | |
100 | } hdr; | |
101 | struct xfs_attr_leaf_entry { /* sorted on key, not name */ | |
102 | xfs_dahash_t hashval; /* hash value of name */ | |
103 | __uint16_t nameidx; /* index into buffer of name/value */ | |
104 | __uint8_t flags; /* LOCAL, ROOT and INCOMPLETE flags */ | |
105 | __uint8_t pad2; /* unused pad byte */ | |
106 | } entries[1]; /* variable sized array */ | |
107 | struct xfs_attr_leaf_name_local { | |
108 | __uint16_t valuelen; /* number of bytes in value */ | |
109 | __uint8_t namelen; /* length of name bytes */ | |
110 | __uint8_t nameval[1]; /* name/value bytes */ | |
111 | } namelist; /* grows from bottom of buf */ | |
112 | struct xfs_attr_leaf_name_remote { | |
113 | xfs_dablk_t valueblk; /* block number of value bytes */ | |
114 | __uint32_t valuelen; /* number of bytes in value */ | |
115 | __uint8_t namelen; /* length of name bytes */ | |
116 | __uint8_t name[1]; /* name bytes */ | |
117 | } valuelist; /* grows from bottom of buf */ | |
118 | } xfs_attr_leafblock_t; | |
119 | typedef struct xfs_attr_leaf_hdr xfs_attr_leaf_hdr_t; | |
120 | typedef struct xfs_attr_leaf_map xfs_attr_leaf_map_t; | |
121 | typedef struct xfs_attr_leaf_entry xfs_attr_leaf_entry_t; | |
122 | typedef struct xfs_attr_leaf_name_local xfs_attr_leaf_name_local_t; | |
123 | typedef struct xfs_attr_leaf_name_remote xfs_attr_leaf_name_remote_t; | |
124 | ||
125 | /* | |
126 | * Flags used in the leaf_entry[i].flags field. | |
127 | * NOTE: the INCOMPLETE bit must not collide with the flags bits specified | |
128 | * on the system call, they are "or"ed together for various operations. | |
129 | */ | |
dfc130f3 RC |
130 | #define XFS_ATTR_LOCAL_BIT 0 /* attr is stored locally */ |
131 | #define XFS_ATTR_ROOT_BIT 1 /* limit access to attr to userid 0 */ | |
132 | #define XFS_ATTR_INCOMPLETE_BIT 7 /* attr in middle of create/delete */ | |
2bd0ea18 NS |
133 | #define XFS_ATTR_LOCAL (1 << XFS_ATTR_LOCAL_BIT) |
134 | #define XFS_ATTR_ROOT (1 << XFS_ATTR_ROOT_BIT) | |
135 | #define XFS_ATTR_INCOMPLETE (1 << XFS_ATTR_INCOMPLETE_BIT) | |
136 | ||
137 | /* | |
138 | * Alignment for namelist and valuelist entries (since they are mixed | |
139 | * there can be only one alignment value) | |
140 | */ | |
dfc130f3 | 141 | #define XFS_ATTR_LEAF_NAME_ALIGN ((uint)sizeof(xfs_dablk_t)) |
2bd0ea18 NS |
142 | |
143 | /* | |
144 | * Cast typed pointers for "local" and "remote" name/value structs. | |
145 | */ | |
146 | #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_NAME_REMOTE) | |
147 | xfs_attr_leaf_name_remote_t * | |
148 | xfs_attr_leaf_name_remote(xfs_attr_leafblock_t *leafp, int idx); | |
149 | #define XFS_ATTR_LEAF_NAME_REMOTE(leafp,idx) \ | |
150 | xfs_attr_leaf_name_remote(leafp,idx) | |
151 | #else | |
152 | #define XFS_ATTR_LEAF_NAME_REMOTE(leafp,idx) /* remote name struct ptr */ \ | |
153 | ((xfs_attr_leaf_name_remote_t *) \ | |
154 | &((char *)(leafp))[ INT_GET((leafp)->entries[idx].nameidx, ARCH_CONVERT) ]) | |
155 | #endif | |
156 | #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_NAME_LOCAL) | |
157 | xfs_attr_leaf_name_local_t * | |
158 | xfs_attr_leaf_name_local(xfs_attr_leafblock_t *leafp, int idx); | |
159 | #define XFS_ATTR_LEAF_NAME_LOCAL(leafp,idx) \ | |
160 | xfs_attr_leaf_name_local(leafp,idx) | |
161 | #else | |
162 | #define XFS_ATTR_LEAF_NAME_LOCAL(leafp,idx) /* local name struct ptr */ \ | |
163 | ((xfs_attr_leaf_name_local_t *) \ | |
164 | &((char *)(leafp))[ INT_GET((leafp)->entries[idx].nameidx, ARCH_CONVERT) ]) | |
165 | #endif | |
166 | #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_NAME) | |
167 | char *xfs_attr_leaf_name(xfs_attr_leafblock_t *leafp, int idx); | |
168 | #define XFS_ATTR_LEAF_NAME(leafp,idx) xfs_attr_leaf_name(leafp,idx) | |
169 | #else | |
170 | #define XFS_ATTR_LEAF_NAME(leafp,idx) /* generic name struct ptr */ \ | |
171 | (&((char *)(leafp))[ INT_GET((leafp)->entries[idx].nameidx, ARCH_CONVERT) ]) | |
172 | #endif | |
173 | ||
174 | /* | |
175 | * Calculate total bytes used (including trailing pad for alignment) for | |
176 | * a "local" name/value structure, a "remote" name/value structure, and | |
177 | * a pointer which might be either. | |
178 | */ | |
179 | #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_ENTSIZE_REMOTE) | |
180 | int xfs_attr_leaf_entsize_remote(int nlen); | |
181 | #define XFS_ATTR_LEAF_ENTSIZE_REMOTE(nlen) \ | |
182 | xfs_attr_leaf_entsize_remote(nlen) | |
183 | #else | |
184 | #define XFS_ATTR_LEAF_ENTSIZE_REMOTE(nlen) /* space for remote struct */ \ | |
185 | (((uint)sizeof(xfs_attr_leaf_name_remote_t) - 1 + (nlen) + \ | |
186 | XFS_ATTR_LEAF_NAME_ALIGN - 1) & ~(XFS_ATTR_LEAF_NAME_ALIGN - 1)) | |
187 | #endif | |
188 | #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_ENTSIZE_LOCAL) | |
189 | int xfs_attr_leaf_entsize_local(int nlen, int vlen); | |
190 | #define XFS_ATTR_LEAF_ENTSIZE_LOCAL(nlen,vlen) \ | |
191 | xfs_attr_leaf_entsize_local(nlen,vlen) | |
192 | #else | |
193 | #define XFS_ATTR_LEAF_ENTSIZE_LOCAL(nlen,vlen) /* space for local struct */ \ | |
194 | (((uint)sizeof(xfs_attr_leaf_name_local_t) - 1 + (nlen) + (vlen) + \ | |
195 | XFS_ATTR_LEAF_NAME_ALIGN - 1) & ~(XFS_ATTR_LEAF_NAME_ALIGN - 1)) | |
196 | #endif | |
197 | #if XFS_WANT_FUNCS || (XFS_WANT_SPACE && XFSSO_XFS_ATTR_LEAF_ENTSIZE_LOCAL_MAX) | |
198 | int xfs_attr_leaf_entsize_local_max(int bsize); | |
199 | #define XFS_ATTR_LEAF_ENTSIZE_LOCAL_MAX(bsize) \ | |
200 | xfs_attr_leaf_entsize_local_max(bsize) | |
201 | #else | |
202 | #define XFS_ATTR_LEAF_ENTSIZE_LOCAL_MAX(bsize) /* max local struct size */ \ | |
203 | (((bsize) >> 1) + ((bsize) >> 2)) | |
204 | #endif | |
205 | ||
206 | ||
207 | /*======================================================================== | |
208 | * Structure used to pass context around among the routines. | |
209 | *========================================================================*/ | |
210 | ||
211 | typedef struct xfs_attr_list_context { | |
212 | struct xfs_inode *dp; /* inode */ | |
213 | struct attrlist_cursor_kern *cursor;/* position in list */ | |
dfc130f3 | 214 | struct attrlist *alist; /* output buffer */ |
2bd0ea18 | 215 | int count; /* num used entries */ |
dfc130f3 | 216 | int dupcnt; /* count dup hashvals seen */ |
2bd0ea18 | 217 | int bufsize;/* total buffer size */ |
dfc130f3 | 218 | int firstu; /* first used byte in buffer */ |
2bd0ea18 NS |
219 | int flags; /* from VOP call */ |
220 | int resynch;/* T/F: resynch with cursor */ | |
221 | } xfs_attr_list_context_t; | |
222 | ||
223 | /* | |
224 | * Used to keep a list of "remote value" extents when unlinking an inode. | |
225 | */ | |
226 | typedef struct xfs_attr_inactive_list { | |
227 | xfs_dablk_t valueblk; /* block number of value bytes */ | |
228 | int valuelen; /* number of bytes in value */ | |
229 | } xfs_attr_inactive_list_t; | |
230 | ||
231 | ||
232 | /*======================================================================== | |
233 | * Function prototypes for the kernel. | |
234 | *========================================================================*/ | |
235 | ||
236 | /* | |
237 | * Internal routines when dirsize < XFS_LITINO(mp). | |
238 | */ | |
239 | int xfs_attr_shortform_create(struct xfs_da_args *args); | |
240 | int xfs_attr_shortform_add(struct xfs_da_args *add); | |
241 | int xfs_attr_shortform_lookup(struct xfs_da_args *args); | |
242 | int xfs_attr_shortform_getvalue(struct xfs_da_args *args); | |
243 | int xfs_attr_shortform_to_leaf(struct xfs_da_args *args); | |
244 | int xfs_attr_shortform_remove(struct xfs_da_args *remove); | |
245 | int xfs_attr_shortform_list(struct xfs_attr_list_context *context); | |
246 | int xfs_attr_shortform_replace(struct xfs_da_args *args); | |
247 | int xfs_attr_shortform_allfit(struct xfs_dabuf *bp, struct xfs_inode *dp); | |
248 | ||
249 | /* | |
250 | * Internal routines when dirsize == XFS_LBSIZE(mp). | |
251 | */ | |
252 | int xfs_attr_leaf_to_node(struct xfs_da_args *args); | |
253 | int xfs_attr_leaf_to_shortform(struct xfs_dabuf *bp, | |
254 | struct xfs_da_args *args); | |
255 | int xfs_attr_leaf_clearflag(struct xfs_da_args *args); | |
256 | int xfs_attr_leaf_setflag(struct xfs_da_args *args); | |
257 | int xfs_attr_leaf_flipflags(xfs_da_args_t *args); | |
258 | ||
259 | /* | |
260 | * Routines used for growing the Btree. | |
261 | */ | |
262 | int xfs_attr_leaf_create(struct xfs_da_args *args, xfs_dablk_t which_block, | |
263 | struct xfs_dabuf **bpp); | |
264 | int xfs_attr_leaf_split(struct xfs_da_state *state, | |
265 | struct xfs_da_state_blk *oldblk, | |
266 | struct xfs_da_state_blk *newblk); | |
267 | int xfs_attr_leaf_lookup_int(struct xfs_dabuf *leaf, | |
268 | struct xfs_da_args *args); | |
269 | int xfs_attr_leaf_getvalue(struct xfs_dabuf *bp, struct xfs_da_args *args); | |
270 | int xfs_attr_leaf_add(struct xfs_dabuf *leaf_buffer, | |
271 | struct xfs_da_args *args); | |
272 | int xfs_attr_leaf_remove(struct xfs_dabuf *leaf_buffer, | |
273 | struct xfs_da_args *args); | |
274 | int xfs_attr_leaf_list_int(struct xfs_dabuf *bp, | |
275 | struct xfs_attr_list_context *context); | |
276 | ||
277 | /* | |
278 | * Routines used for shrinking the Btree. | |
279 | */ | |
280 | int xfs_attr_leaf_toosmall(struct xfs_da_state *state, int *retval); | |
281 | void xfs_attr_leaf_unbalance(struct xfs_da_state *state, | |
282 | struct xfs_da_state_blk *drop_blk, | |
283 | struct xfs_da_state_blk *save_blk); | |
284 | int xfs_attr_root_inactive(struct xfs_trans **trans, struct xfs_inode *dp); | |
285 | int xfs_attr_node_inactive(struct xfs_trans **trans, struct xfs_inode *dp, | |
286 | struct xfs_dabuf *bp, int level); | |
287 | int xfs_attr_leaf_inactive(struct xfs_trans **trans, struct xfs_inode *dp, | |
288 | struct xfs_dabuf *bp); | |
289 | int xfs_attr_leaf_freextent(struct xfs_trans **trans, struct xfs_inode *dp, | |
290 | xfs_dablk_t blkno, int blkcnt); | |
291 | ||
292 | /* | |
293 | * Utility routines. | |
294 | */ | |
295 | xfs_dahash_t xfs_attr_leaf_lasthash(struct xfs_dabuf *bp, int *count); | |
296 | int xfs_attr_leaf_order(struct xfs_dabuf *leaf1_bp, | |
297 | struct xfs_dabuf *leaf2_bp); | |
298 | int xfs_attr_leaf_newentsize(struct xfs_da_args *args, int blocksize, | |
299 | int *local); | |
300 | int xfs_attr_leaf_entsize(struct xfs_attr_leafblock *leaf, int index); | |
301 | int xfs_attr_put_listent(struct xfs_attr_list_context *context, | |
2f8883de | 302 | int ns, char *name, int namelen, int valuelen); |
2bd0ea18 NS |
303 | int xfs_attr_rolltrans(struct xfs_trans **transp, struct xfs_inode *dp); |
304 | ||
305 | #endif /* __XFS_ATTR_LEAF_H__ */ |