Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
xfs_attr_leaf.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000,2002-2003,2005 Silicon Graphics, Inc.
3  * All Rights Reserved.
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms 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,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write the Free Software Foundation,
16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17  */
18 #ifndef __XFS_ATTR_LEAF_H__
19 #define __XFS_ATTR_LEAF_H__
20 
21 /*
22  * Attribute storage layout, internal structure, access macros, etc.
23  *
24  * Attribute lists are structured around Btrees where all the data
25  * elements are in the leaf nodes. Attribute names are hashed into an int,
26  * then that int is used as the index into the Btree. Since the hashval
27  * of an attribute name may not be unique, we may have duplicate keys. The
28  * internal links in the Btree are logical block offsets into the file.
29  */
30 
31 struct attrlist;
34 struct xfs_da_args;
35 struct xfs_da_state;
36 struct xfs_da_state_blk;
37 struct xfs_inode;
38 struct xfs_trans;
39 
40 /*========================================================================
41  * Attribute structure when equal to XFS_LBSIZE(mp) bytes.
42  *========================================================================*/
43 
44 /*
45  * This is the structure of the leaf nodes in the Btree.
46  *
47  * Struct leaf_entry's are packed from the top. Name/values grow from the
48  * bottom but are not packed. The freemap contains run-length-encoded entries
49  * for the free bytes after the leaf_entry's, but only the N largest such,
50  * smaller runs are dropped. When the freemap doesn't show enough space
51  * for an allocation, we compact the name/value area and try again. If we
52  * still don't have enough space, then we have to split the block. The
53  * name/value structs (both local and remote versions) must be 32bit aligned.
54  *
55  * Since we have duplicate hash keys, for each key that matches, compare
56  * the actual name string. The root and intermediate node search always
57  * takes the first-in-the-block key match found, so we should only have
58  * to work "forw"ard. If none matches, continue with the "forw"ard leaf
59  * nodes until the hash key changes or the attribute name is found.
60  *
61  * We store the fact that an attribute is a ROOT/USER/SECURE attribute in
62  * the leaf_entry. The namespaces are independent only because we also look
63  * at the namespace bit when we are looking for a matching attribute name.
64  *
65  * We also store an "incomplete" bit in the leaf_entry. It shows that an
66  * attribute is in the middle of being created and should not be shown to
67  * the user if we crash during the time that the bit is set. We clear the
68  * bit when we have finished setting up the attribute. We do this because
69  * we cannot create some large attributes inside a single transaction, and we
70  * need some indication that we weren't finished if we crash in the middle.
71  */
72 #define XFS_ATTR_LEAF_MAPSIZE 3 /* how many freespace slots */
73 
74 typedef struct xfs_attr_leaf_map { /* RLE map of free bytes */
75  __be16 base; /* base of free region */
76  __be16 size; /* length of free region */
78 
79 typedef struct xfs_attr_leaf_hdr { /* constant-structure header block */
80  xfs_da_blkinfo_t info; /* block type, links, etc. */
81  __be16 count; /* count of active leaf_entry's */
82  __be16 usedbytes; /* num bytes of names/values stored */
83  __be16 firstused; /* first used byte in name area */
84  __u8 holes; /* != 0 if blk needs compaction */
87  /* N largest free regions */
89 
90 typedef struct xfs_attr_leaf_entry { /* sorted on key, not name */
91  __be32 hashval; /* hash value of name */
92  __be16 nameidx; /* index into buffer of name/value */
93  __u8 flags; /* LOCAL/ROOT/SECURE/INCOMPLETE flag */
94  __u8 pad2; /* unused pad byte */
96 
97 typedef struct xfs_attr_leaf_name_local {
98  __be16 valuelen; /* number of bytes in value */
99  __u8 namelen; /* length of name bytes */
100  __u8 nameval[1]; /* name/value bytes */
102 
104  __be32 valueblk; /* block number of value bytes */
105  __be32 valuelen; /* number of bytes in value */
106  __u8 namelen; /* length of name bytes */
107  __u8 name[1]; /* name bytes */
109 
110 typedef struct xfs_attr_leafblock {
111  xfs_attr_leaf_hdr_t hdr; /* constant-structure header block */
112  xfs_attr_leaf_entry_t entries[1]; /* sorted on key, not name */
113  xfs_attr_leaf_name_local_t namelist; /* grows from bottom of buf */
114  xfs_attr_leaf_name_remote_t valuelist; /* grows from bottom of buf */
116 
117 /*
118  * Flags used in the leaf_entry[i].flags field.
119  * NOTE: the INCOMPLETE bit must not collide with the flags bits specified
120  * on the system call, they are "or"ed together for various operations.
121  */
122 #define XFS_ATTR_LOCAL_BIT 0 /* attr is stored locally */
123 #define XFS_ATTR_ROOT_BIT 1 /* limit access to trusted attrs */
124 #define XFS_ATTR_SECURE_BIT 2 /* limit access to secure attrs */
125 #define XFS_ATTR_INCOMPLETE_BIT 7 /* attr in middle of create/delete */
126 #define XFS_ATTR_LOCAL (1 << XFS_ATTR_LOCAL_BIT)
127 #define XFS_ATTR_ROOT (1 << XFS_ATTR_ROOT_BIT)
128 #define XFS_ATTR_SECURE (1 << XFS_ATTR_SECURE_BIT)
129 #define XFS_ATTR_INCOMPLETE (1 << XFS_ATTR_INCOMPLETE_BIT)
130 
131 /*
132  * Conversion macros for converting namespace bits from argument flags
133  * to ondisk flags.
134  */
135 #define XFS_ATTR_NSP_ARGS_MASK (ATTR_ROOT | ATTR_SECURE)
136 #define XFS_ATTR_NSP_ONDISK_MASK (XFS_ATTR_ROOT | XFS_ATTR_SECURE)
137 #define XFS_ATTR_NSP_ONDISK(flags) ((flags) & XFS_ATTR_NSP_ONDISK_MASK)
138 #define XFS_ATTR_NSP_ARGS(flags) ((flags) & XFS_ATTR_NSP_ARGS_MASK)
139 #define XFS_ATTR_NSP_ARGS_TO_ONDISK(x) (((x) & ATTR_ROOT ? XFS_ATTR_ROOT : 0) |\
140  ((x) & ATTR_SECURE ? XFS_ATTR_SECURE : 0))
141 #define XFS_ATTR_NSP_ONDISK_TO_ARGS(x) (((x) & XFS_ATTR_ROOT ? ATTR_ROOT : 0) |\
142  ((x) & XFS_ATTR_SECURE ? ATTR_SECURE : 0))
143 
144 /*
145  * Alignment for namelist and valuelist entries (since they are mixed
146  * there can be only one alignment value)
147  */
148 #define XFS_ATTR_LEAF_NAME_ALIGN ((uint)sizeof(xfs_dablk_t))
149 
150 /*
151  * Cast typed pointers for "local" and "remote" name/value structs.
152  */
153 static inline xfs_attr_leaf_name_remote_t *
155 {
156  return (xfs_attr_leaf_name_remote_t *)
157  &((char *)leafp)[be16_to_cpu(leafp->entries[idx].nameidx)];
158 }
159 
160 static inline xfs_attr_leaf_name_local_t *
162 {
163  return (xfs_attr_leaf_name_local_t *)
164  &((char *)leafp)[be16_to_cpu(leafp->entries[idx].nameidx)];
165 }
166 
167 static inline char *xfs_attr_leaf_name(xfs_attr_leafblock_t *leafp, int idx)
168 {
169  return &((char *)leafp)[be16_to_cpu(leafp->entries[idx].nameidx)];
170 }
171 
172 /*
173  * Calculate total bytes used (including trailing pad for alignment) for
174  * a "local" name/value structure, a "remote" name/value structure, and
175  * a pointer which might be either.
176  */
177 static inline int xfs_attr_leaf_entsize_remote(int nlen)
178 {
179  return ((uint)sizeof(xfs_attr_leaf_name_remote_t) - 1 + (nlen) + \
181 }
182 
183 static inline int xfs_attr_leaf_entsize_local(int nlen, int vlen)
184 {
185  return ((uint)sizeof(xfs_attr_leaf_name_local_t) - 1 + (nlen) + (vlen) +
187 }
188 
189 static inline int xfs_attr_leaf_entsize_local_max(int bsize)
190 {
191  return (((bsize) >> 1) + ((bsize) >> 2));
192 }
193 
194 /*
195  * Used to keep a list of "remote value" extents when unlinking an inode.
196  */
197 typedef struct xfs_attr_inactive_list {
198  xfs_dablk_t valueblk; /* block number of value bytes */
199  int valuelen; /* number of bytes in value */
201 
202 
203 /*========================================================================
204  * Function prototypes for the kernel.
205  *========================================================================*/
206 
207 /*
208  * Internal routines when attribute fork size < XFS_LITINO(mp).
209  */
210 void xfs_attr_shortform_create(struct xfs_da_args *args);
211 void xfs_attr_shortform_add(struct xfs_da_args *args, int forkoff);
212 int xfs_attr_shortform_lookup(struct xfs_da_args *args);
213 int xfs_attr_shortform_getvalue(struct xfs_da_args *args);
214 int xfs_attr_shortform_to_leaf(struct xfs_da_args *args);
215 int xfs_attr_shortform_remove(struct xfs_da_args *args);
217 int xfs_attr_shortform_allfit(struct xfs_buf *bp, struct xfs_inode *dp);
218 int xfs_attr_shortform_bytesfit(xfs_inode_t *dp, int bytes);
219 
220 
221 /*
222  * Internal routines when attribute fork size == XFS_LBSIZE(mp).
223  */
224 int xfs_attr_leaf_to_node(struct xfs_da_args *args);
225 int xfs_attr_leaf_to_shortform(struct xfs_buf *bp,
226  struct xfs_da_args *args, int forkoff);
227 int xfs_attr_leaf_clearflag(struct xfs_da_args *args);
228 int xfs_attr_leaf_setflag(struct xfs_da_args *args);
230 
231 /*
232  * Routines used for growing the Btree.
233  */
235  struct xfs_da_state_blk *oldblk,
236  struct xfs_da_state_blk *newblk);
238  struct xfs_da_args *args);
239 int xfs_attr_leaf_getvalue(struct xfs_buf *bp, struct xfs_da_args *args);
240 int xfs_attr_leaf_add(struct xfs_buf *leaf_buffer,
241  struct xfs_da_args *args);
242 int xfs_attr_leaf_remove(struct xfs_buf *leaf_buffer,
243  struct xfs_da_args *args);
244 int xfs_attr_leaf_list_int(struct xfs_buf *bp,
246 
247 /*
248  * Routines used for shrinking the Btree.
249  */
252  struct xfs_da_state_blk *drop_blk,
253  struct xfs_da_state_blk *save_blk);
254 int xfs_attr_root_inactive(struct xfs_trans **trans, struct xfs_inode *dp);
255 
256 /*
257  * Utility routines.
258  */
260 int xfs_attr_leaf_order(struct xfs_buf *leaf1_bp,
261  struct xfs_buf *leaf2_bp);
262 int xfs_attr_leaf_newentsize(int namelen, int valuelen, int blocksize,
263  int *local);
264 #endif /* __XFS_ATTR_LEAF_H__ */