xfs_attr_leaf.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306
  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. * Attribute storage layout, internal structure, access macros, etc.
  22. *
  23. * Attribute lists are structured around Btrees where all the data
  24. * elements are in the leaf nodes. Attribute names are hashed into an int,
  25. * then that int is used as the index into the Btree. Since the hashval
  26. * of an attribute name may not be unique, we may have duplicate keys. The
  27. * internal links in the Btree are logical block offsets into the file.
  28. */
  29. struct attrlist;
  30. struct attrlist_cursor_kern;
  31. struct attrnames;
  32. struct xfs_dabuf;
  33. struct xfs_da_args;
  34. struct xfs_da_state;
  35. struct xfs_da_state_blk;
  36. struct xfs_inode;
  37. struct xfs_trans;
  38. /*========================================================================
  39. * Attribute structure when equal to XFS_LBSIZE(mp) bytes.
  40. *========================================================================*/
  41. /*
  42. * This is the structure of the leaf nodes in the Btree.
  43. *
  44. * Struct leaf_entry's are packed from the top. Name/values grow from the
  45. * bottom but are not packed. The freemap contains run-length-encoded entries
  46. * for the free bytes after the leaf_entry's, but only the N largest such,
  47. * smaller runs are dropped. When the freemap doesn't show enough space
  48. * for an allocation, we compact the name/value area and try again. If we
  49. * still don't have enough space, then we have to split the block. The
  50. * name/value structs (both local and remote versions) must be 32bit aligned.
  51. *
  52. * Since we have duplicate hash keys, for each key that matches, compare
  53. * the actual name string. The root and intermediate node search always
  54. * takes the first-in-the-block key match found, so we should only have
  55. * to work "forw"ard. If none matches, continue with the "forw"ard leaf
  56. * nodes until the hash key changes or the attribute name is found.
  57. *
  58. * We store the fact that an attribute is a ROOT/USER/SECURE attribute in
  59. * the leaf_entry. The namespaces are independent only because we also look
  60. * at the namespace bit when we are looking for a matching attribute name.
  61. *
  62. * We also store an "incomplete" bit in the leaf_entry. It shows that an
  63. * attribute is in the middle of being created and should not be shown to
  64. * the user if we crash during the time that the bit is set. We clear the
  65. * bit when we have finished setting up the attribute. We do this because
  66. * we cannot create some large attributes inside a single transaction, and we
  67. * need some indication that we weren't finished if we crash in the middle.
  68. */
  69. #define XFS_ATTR_LEAF_MAPSIZE 3 /* how many freespace slots */
  70. typedef struct xfs_attr_leaf_map { /* RLE map of free bytes */
  71. __be16 base; /* base of free region */
  72. __be16 size; /* length of free region */
  73. } xfs_attr_leaf_map_t;
  74. typedef struct xfs_attr_leaf_hdr { /* constant-structure header block */
  75. xfs_da_blkinfo_t info; /* block type, links, etc. */
  76. __be16 count; /* count of active leaf_entry's */
  77. __be16 usedbytes; /* num bytes of names/values stored */
  78. __be16 firstused; /* first used byte in name area */
  79. __u8 holes; /* != 0 if blk needs compaction */
  80. __u8 pad1;
  81. xfs_attr_leaf_map_t freemap[XFS_ATTR_LEAF_MAPSIZE];
  82. /* N largest free regions */
  83. } xfs_attr_leaf_hdr_t;
  84. typedef struct xfs_attr_leaf_entry { /* sorted on key, not name */
  85. __be32 hashval; /* hash value of name */
  86. __be16 nameidx; /* index into buffer of name/value */
  87. __u8 flags; /* LOCAL/ROOT/SECURE/INCOMPLETE flag */
  88. __u8 pad2; /* unused pad byte */
  89. } xfs_attr_leaf_entry_t;
  90. typedef struct xfs_attr_leaf_name_local {
  91. __be16 valuelen; /* number of bytes in value */
  92. __u8 namelen; /* length of name bytes */
  93. __u8 nameval[1]; /* name/value bytes */
  94. } xfs_attr_leaf_name_local_t;
  95. typedef struct xfs_attr_leaf_name_remote {
  96. __be32 valueblk; /* block number of value bytes */
  97. __be32 valuelen; /* number of bytes in value */
  98. __u8 namelen; /* length of name bytes */
  99. __u8 name[1]; /* name bytes */
  100. } xfs_attr_leaf_name_remote_t;
  101. typedef struct xfs_attr_leafblock {
  102. xfs_attr_leaf_hdr_t hdr; /* constant-structure header block */
  103. xfs_attr_leaf_entry_t entries[1]; /* sorted on key, not name */
  104. xfs_attr_leaf_name_local_t namelist; /* grows from bottom of buf */
  105. xfs_attr_leaf_name_remote_t valuelist; /* grows from bottom of buf */
  106. } xfs_attr_leafblock_t;
  107. /*
  108. * Flags used in the leaf_entry[i].flags field.
  109. * NOTE: the INCOMPLETE bit must not collide with the flags bits specified
  110. * on the system call, they are "or"ed together for various operations.
  111. */
  112. #define XFS_ATTR_LOCAL_BIT 0 /* attr is stored locally */
  113. #define XFS_ATTR_ROOT_BIT 1 /* limit access to trusted attrs */
  114. #define XFS_ATTR_SECURE_BIT 2 /* limit access to secure attrs */
  115. #define XFS_ATTR_INCOMPLETE_BIT 7 /* attr in middle of create/delete */
  116. #define XFS_ATTR_LOCAL (1 << XFS_ATTR_LOCAL_BIT)
  117. #define XFS_ATTR_ROOT (1 << XFS_ATTR_ROOT_BIT)
  118. #define XFS_ATTR_SECURE (1 << XFS_ATTR_SECURE_BIT)
  119. #define XFS_ATTR_INCOMPLETE (1 << XFS_ATTR_INCOMPLETE_BIT)
  120. /*
  121. * Conversion macros for converting namespace bits from argument flags
  122. * to ondisk flags.
  123. */
  124. #define XFS_ATTR_NSP_ARGS_MASK (ATTR_ROOT | ATTR_SECURE)
  125. #define XFS_ATTR_NSP_ONDISK_MASK (XFS_ATTR_ROOT | XFS_ATTR_SECURE)
  126. #define XFS_ATTR_NSP_ONDISK(flags) ((flags) & XFS_ATTR_NSP_ONDISK_MASK)
  127. #define XFS_ATTR_NSP_ARGS(flags) ((flags) & XFS_ATTR_NSP_ARGS_MASK)
  128. #define XFS_ATTR_NSP_ARGS_TO_ONDISK(x) (((x) & ATTR_ROOT ? XFS_ATTR_ROOT : 0) |\
  129. ((x) & ATTR_SECURE ? XFS_ATTR_SECURE : 0))
  130. #define XFS_ATTR_NSP_ONDISK_TO_ARGS(x) (((x) & XFS_ATTR_ROOT ? ATTR_ROOT : 0) |\
  131. ((x) & XFS_ATTR_SECURE ? ATTR_SECURE : 0))
  132. /*
  133. * Alignment for namelist and valuelist entries (since they are mixed
  134. * there can be only one alignment value)
  135. */
  136. #define XFS_ATTR_LEAF_NAME_ALIGN ((uint)sizeof(xfs_dablk_t))
  137. /*
  138. * Cast typed pointers for "local" and "remote" name/value structs.
  139. */
  140. #define XFS_ATTR_LEAF_NAME_REMOTE(leafp,idx) \
  141. xfs_attr_leaf_name_remote(leafp,idx)
  142. static inline xfs_attr_leaf_name_remote_t *
  143. xfs_attr_leaf_name_remote(xfs_attr_leafblock_t *leafp, int idx)
  144. {
  145. return (xfs_attr_leaf_name_remote_t *)
  146. &((char *)leafp)[be16_to_cpu(leafp->entries[idx].nameidx)];
  147. }
  148. #define XFS_ATTR_LEAF_NAME_LOCAL(leafp,idx) \
  149. xfs_attr_leaf_name_local(leafp,idx)
  150. static inline xfs_attr_leaf_name_local_t *
  151. xfs_attr_leaf_name_local(xfs_attr_leafblock_t *leafp, int idx)
  152. {
  153. return (xfs_attr_leaf_name_local_t *)
  154. &((char *)leafp)[be16_to_cpu(leafp->entries[idx].nameidx)];
  155. }
  156. #define XFS_ATTR_LEAF_NAME(leafp,idx) \
  157. xfs_attr_leaf_name(leafp,idx)
  158. static inline char *xfs_attr_leaf_name(xfs_attr_leafblock_t *leafp, int idx)
  159. {
  160. return &((char *)leafp)[be16_to_cpu(leafp->entries[idx].nameidx)];
  161. }
  162. /*
  163. * Calculate total bytes used (including trailing pad for alignment) for
  164. * a "local" name/value structure, a "remote" name/value structure, and
  165. * a pointer which might be either.
  166. */
  167. #define XFS_ATTR_LEAF_ENTSIZE_REMOTE(nlen) \
  168. xfs_attr_leaf_entsize_remote(nlen)
  169. static inline int xfs_attr_leaf_entsize_remote(int nlen)
  170. {
  171. return ((uint)sizeof(xfs_attr_leaf_name_remote_t) - 1 + (nlen) + \
  172. XFS_ATTR_LEAF_NAME_ALIGN - 1) & ~(XFS_ATTR_LEAF_NAME_ALIGN - 1);
  173. }
  174. #define XFS_ATTR_LEAF_ENTSIZE_LOCAL(nlen,vlen) \
  175. xfs_attr_leaf_entsize_local(nlen,vlen)
  176. static inline int xfs_attr_leaf_entsize_local(int nlen, int vlen)
  177. {
  178. return ((uint)sizeof(xfs_attr_leaf_name_local_t) - 1 + (nlen) + (vlen) +
  179. XFS_ATTR_LEAF_NAME_ALIGN - 1) & ~(XFS_ATTR_LEAF_NAME_ALIGN - 1);
  180. }
  181. #define XFS_ATTR_LEAF_ENTSIZE_LOCAL_MAX(bsize) \
  182. xfs_attr_leaf_entsize_local_max(bsize)
  183. static inline int xfs_attr_leaf_entsize_local_max(int bsize)
  184. {
  185. return (((bsize) >> 1) + ((bsize) >> 2));
  186. }
  187. /*========================================================================
  188. * Structure used to pass context around among the routines.
  189. *========================================================================*/
  190. struct xfs_attr_list_context;
  191. typedef int (*put_listent_func_t)(struct xfs_attr_list_context *, struct attrnames *,
  192. char *, int, int, char *);
  193. typedef struct xfs_attr_list_context {
  194. struct xfs_inode *dp; /* inode */
  195. struct attrlist_cursor_kern *cursor; /* position in list */
  196. struct attrlist *alist; /* output buffer */
  197. int seen_enough; /* T/F: seen enough of list? */
  198. int count; /* num used entries */
  199. int dupcnt; /* count dup hashvals seen */
  200. int bufsize; /* total buffer size */
  201. int firstu; /* first used byte in buffer */
  202. int flags; /* from VOP call */
  203. int resynch; /* T/F: resynch with cursor */
  204. int put_value; /* T/F: need value for listent */
  205. put_listent_func_t put_listent; /* list output fmt function */
  206. int index; /* index into output buffer */
  207. } xfs_attr_list_context_t;
  208. /*
  209. * Used to keep a list of "remote value" extents when unlinking an inode.
  210. */
  211. typedef struct xfs_attr_inactive_list {
  212. xfs_dablk_t valueblk; /* block number of value bytes */
  213. int valuelen; /* number of bytes in value */
  214. } xfs_attr_inactive_list_t;
  215. /*========================================================================
  216. * Function prototypes for the kernel.
  217. *========================================================================*/
  218. /*
  219. * Internal routines when attribute fork size < XFS_LITINO(mp).
  220. */
  221. void xfs_attr_shortform_create(struct xfs_da_args *args);
  222. void xfs_attr_shortform_add(struct xfs_da_args *args, int forkoff);
  223. int xfs_attr_shortform_lookup(struct xfs_da_args *args);
  224. int xfs_attr_shortform_getvalue(struct xfs_da_args *args);
  225. int xfs_attr_shortform_to_leaf(struct xfs_da_args *args);
  226. int xfs_attr_shortform_remove(struct xfs_da_args *args);
  227. int xfs_attr_shortform_list(struct xfs_attr_list_context *context);
  228. int xfs_attr_shortform_allfit(struct xfs_dabuf *bp, struct xfs_inode *dp);
  229. int xfs_attr_shortform_bytesfit(xfs_inode_t *dp, int bytes);
  230. /*
  231. * Internal routines when attribute fork size == XFS_LBSIZE(mp).
  232. */
  233. int xfs_attr_leaf_to_node(struct xfs_da_args *args);
  234. int xfs_attr_leaf_to_shortform(struct xfs_dabuf *bp,
  235. struct xfs_da_args *args, int forkoff);
  236. int xfs_attr_leaf_clearflag(struct xfs_da_args *args);
  237. int xfs_attr_leaf_setflag(struct xfs_da_args *args);
  238. int xfs_attr_leaf_flipflags(xfs_da_args_t *args);
  239. /*
  240. * Routines used for growing the Btree.
  241. */
  242. int xfs_attr_leaf_split(struct xfs_da_state *state,
  243. struct xfs_da_state_blk *oldblk,
  244. struct xfs_da_state_blk *newblk);
  245. int xfs_attr_leaf_lookup_int(struct xfs_dabuf *leaf,
  246. struct xfs_da_args *args);
  247. int xfs_attr_leaf_getvalue(struct xfs_dabuf *bp, struct xfs_da_args *args);
  248. int xfs_attr_leaf_add(struct xfs_dabuf *leaf_buffer,
  249. struct xfs_da_args *args);
  250. int xfs_attr_leaf_remove(struct xfs_dabuf *leaf_buffer,
  251. struct xfs_da_args *args);
  252. int xfs_attr_leaf_list_int(struct xfs_dabuf *bp,
  253. struct xfs_attr_list_context *context);
  254. /*
  255. * Routines used for shrinking the Btree.
  256. */
  257. int xfs_attr_leaf_toosmall(struct xfs_da_state *state, int *retval);
  258. void xfs_attr_leaf_unbalance(struct xfs_da_state *state,
  259. struct xfs_da_state_blk *drop_blk,
  260. struct xfs_da_state_blk *save_blk);
  261. int xfs_attr_root_inactive(struct xfs_trans **trans, struct xfs_inode *dp);
  262. /*
  263. * Utility routines.
  264. */
  265. xfs_dahash_t xfs_attr_leaf_lasthash(struct xfs_dabuf *bp, int *count);
  266. int xfs_attr_leaf_order(struct xfs_dabuf *leaf1_bp,
  267. struct xfs_dabuf *leaf2_bp);
  268. int xfs_attr_leaf_newentsize(int namelen, int valuelen, int blocksize,
  269. int *local);
  270. int xfs_attr_rolltrans(struct xfs_trans **transp, struct xfs_inode *dp);
  271. #endif /* __XFS_ATTR_LEAF_H__ */