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