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