xfs_bmap_btree.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341
  1. /*
  2. * Copyright (c) 2000,2002-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_BMAP_BTREE_H__
  19. #define __XFS_BMAP_BTREE_H__
  20. #define XFS_BMAP_MAGIC 0x424d4150 /* 'BMAP' */
  21. struct xfs_btree_cur;
  22. struct xfs_btree_lblock;
  23. struct xfs_mount;
  24. struct xfs_inode;
  25. /*
  26. * Bmap root header, on-disk form only.
  27. */
  28. typedef struct xfs_bmdr_block {
  29. __be16 bb_level; /* 0 is a leaf */
  30. __be16 bb_numrecs; /* current # of data records */
  31. } xfs_bmdr_block_t;
  32. /*
  33. * Bmap btree record and extent descriptor.
  34. * For 32-bit kernels,
  35. * l0:31 is an extent flag (value 1 indicates non-normal).
  36. * l0:0-30 and l1:9-31 are startoff.
  37. * l1:0-8, l2:0-31, and l3:21-31 are startblock.
  38. * l3:0-20 are blockcount.
  39. * For 64-bit kernels,
  40. * l0:63 is an extent flag (value 1 indicates non-normal).
  41. * l0:9-62 are startoff.
  42. * l0:0-8 and l1:21-63 are startblock.
  43. * l1:0-20 are blockcount.
  44. */
  45. #ifndef XFS_NATIVE_HOST
  46. #define BMBT_TOTAL_BITLEN 128 /* 128 bits, 16 bytes */
  47. #define BMBT_EXNTFLAG_BITOFF 0
  48. #define BMBT_EXNTFLAG_BITLEN 1
  49. #define BMBT_STARTOFF_BITOFF (BMBT_EXNTFLAG_BITOFF + BMBT_EXNTFLAG_BITLEN)
  50. #define BMBT_STARTOFF_BITLEN 54
  51. #define BMBT_STARTBLOCK_BITOFF (BMBT_STARTOFF_BITOFF + BMBT_STARTOFF_BITLEN)
  52. #define BMBT_STARTBLOCK_BITLEN 52
  53. #define BMBT_BLOCKCOUNT_BITOFF \
  54. (BMBT_STARTBLOCK_BITOFF + BMBT_STARTBLOCK_BITLEN)
  55. #define BMBT_BLOCKCOUNT_BITLEN (BMBT_TOTAL_BITLEN - BMBT_BLOCKCOUNT_BITOFF)
  56. #else
  57. #define BMBT_TOTAL_BITLEN 128 /* 128 bits, 16 bytes */
  58. #define BMBT_EXNTFLAG_BITOFF 63
  59. #define BMBT_EXNTFLAG_BITLEN 1
  60. #define BMBT_STARTOFF_BITOFF (BMBT_EXNTFLAG_BITOFF - BMBT_STARTOFF_BITLEN)
  61. #define BMBT_STARTOFF_BITLEN 54
  62. #define BMBT_STARTBLOCK_BITOFF 85 /* 128 - 43 (other 9 is in first word) */
  63. #define BMBT_STARTBLOCK_BITLEN 52
  64. #define BMBT_BLOCKCOUNT_BITOFF 64 /* Start of second 64 bit container */
  65. #define BMBT_BLOCKCOUNT_BITLEN 21
  66. #endif /* XFS_NATIVE_HOST */
  67. #define BMBT_USE_64 1
  68. typedef struct xfs_bmbt_rec_32
  69. {
  70. __uint32_t l0, l1, l2, l3;
  71. } xfs_bmbt_rec_32_t;
  72. typedef struct xfs_bmbt_rec_64
  73. {
  74. __uint64_t l0, l1;
  75. } xfs_bmbt_rec_64_t;
  76. typedef __uint64_t xfs_bmbt_rec_base_t; /* use this for casts */
  77. typedef xfs_bmbt_rec_64_t xfs_bmbt_rec_t, xfs_bmdr_rec_t;
  78. /*
  79. * Values and macros for delayed-allocation startblock fields.
  80. */
  81. #define STARTBLOCKVALBITS 17
  82. #define STARTBLOCKMASKBITS (15 + XFS_BIG_BLKNOS * 20)
  83. #define DSTARTBLOCKMASKBITS (15 + 20)
  84. #define STARTBLOCKMASK \
  85. (((((xfs_fsblock_t)1) << STARTBLOCKMASKBITS) - 1) << STARTBLOCKVALBITS)
  86. #define DSTARTBLOCKMASK \
  87. (((((xfs_dfsbno_t)1) << DSTARTBLOCKMASKBITS) - 1) << STARTBLOCKVALBITS)
  88. #define ISNULLSTARTBLOCK(x) isnullstartblock(x)
  89. static inline int isnullstartblock(xfs_fsblock_t x)
  90. {
  91. return ((x) & STARTBLOCKMASK) == STARTBLOCKMASK;
  92. }
  93. #define ISNULLDSTARTBLOCK(x) isnulldstartblock(x)
  94. static inline int isnulldstartblock(xfs_dfsbno_t x)
  95. {
  96. return ((x) & DSTARTBLOCKMASK) == DSTARTBLOCKMASK;
  97. }
  98. #define NULLSTARTBLOCK(k) nullstartblock(k)
  99. static inline xfs_fsblock_t nullstartblock(int k)
  100. {
  101. ASSERT(k < (1 << STARTBLOCKVALBITS));
  102. return STARTBLOCKMASK | (k);
  103. }
  104. #define STARTBLOCKVAL(x) startblockval(x)
  105. static inline xfs_filblks_t startblockval(xfs_fsblock_t x)
  106. {
  107. return (xfs_filblks_t)((x) & ~STARTBLOCKMASK);
  108. }
  109. /*
  110. * Possible extent formats.
  111. */
  112. typedef enum {
  113. XFS_EXTFMT_NOSTATE = 0,
  114. XFS_EXTFMT_HASSTATE
  115. } xfs_exntfmt_t;
  116. /*
  117. * Possible extent states.
  118. */
  119. typedef enum {
  120. XFS_EXT_NORM, XFS_EXT_UNWRITTEN,
  121. XFS_EXT_DMAPI_OFFLINE, XFS_EXT_INVALID
  122. } xfs_exntst_t;
  123. /*
  124. * Extent state and extent format macros.
  125. */
  126. #define XFS_EXTFMT_INODE(x) \
  127. (XFS_SB_VERSION_HASEXTFLGBIT(&((x)->i_mount->m_sb)) ? \
  128. XFS_EXTFMT_HASSTATE : XFS_EXTFMT_NOSTATE)
  129. #define ISUNWRITTEN(x) ((x)->br_state == XFS_EXT_UNWRITTEN)
  130. /*
  131. * Incore version of above.
  132. */
  133. typedef struct xfs_bmbt_irec
  134. {
  135. xfs_fileoff_t br_startoff; /* starting file offset */
  136. xfs_fsblock_t br_startblock; /* starting block number */
  137. xfs_filblks_t br_blockcount; /* number of blocks */
  138. xfs_exntst_t br_state; /* extent state */
  139. } xfs_bmbt_irec_t;
  140. /*
  141. * Key structure for non-leaf levels of the tree.
  142. */
  143. typedef struct xfs_bmbt_key {
  144. __be64 br_startoff; /* starting file offset */
  145. } xfs_bmbt_key_t, xfs_bmdr_key_t;
  146. /* btree pointer type */
  147. typedef __be64 xfs_bmbt_ptr_t, xfs_bmdr_ptr_t;
  148. /* btree block header type */
  149. typedef struct xfs_btree_lblock xfs_bmbt_block_t;
  150. #define XFS_BUF_TO_BMBT_BLOCK(bp) ((xfs_bmbt_block_t *)XFS_BUF_PTR(bp))
  151. #define XFS_BMAP_RBLOCK_DSIZE(lev,cur) ((cur)->bc_private.b.forksize)
  152. #define XFS_BMAP_RBLOCK_ISIZE(lev,cur) \
  153. ((int)XFS_IFORK_PTR((cur)->bc_private.b.ip, \
  154. (cur)->bc_private.b.whichfork)->if_broot_bytes)
  155. #define XFS_BMAP_BLOCK_DMAXRECS(lev,cur) \
  156. (((lev) == (cur)->bc_nlevels - 1 ? \
  157. XFS_BTREE_BLOCK_MAXRECS(XFS_BMAP_RBLOCK_DSIZE(lev,cur), \
  158. xfs_bmdr, (lev) == 0) : \
  159. ((cur)->bc_mp->m_bmap_dmxr[(lev) != 0])))
  160. #define XFS_BMAP_BLOCK_IMAXRECS(lev,cur) \
  161. (((lev) == (cur)->bc_nlevels - 1 ? \
  162. XFS_BTREE_BLOCK_MAXRECS(XFS_BMAP_RBLOCK_ISIZE(lev,cur),\
  163. xfs_bmbt, (lev) == 0) : \
  164. ((cur)->bc_mp->m_bmap_dmxr[(lev) != 0])))
  165. #define XFS_BMAP_BLOCK_DMINRECS(lev,cur) \
  166. (((lev) == (cur)->bc_nlevels - 1 ? \
  167. XFS_BTREE_BLOCK_MINRECS(XFS_BMAP_RBLOCK_DSIZE(lev,cur),\
  168. xfs_bmdr, (lev) == 0) : \
  169. ((cur)->bc_mp->m_bmap_dmnr[(lev) != 0])))
  170. #define XFS_BMAP_BLOCK_IMINRECS(lev,cur) \
  171. (((lev) == (cur)->bc_nlevels - 1 ? \
  172. XFS_BTREE_BLOCK_MINRECS(XFS_BMAP_RBLOCK_ISIZE(lev,cur),\
  173. xfs_bmbt, (lev) == 0) : \
  174. ((cur)->bc_mp->m_bmap_dmnr[(lev) != 0])))
  175. #define XFS_BMAP_REC_DADDR(bb,i,cur) (XFS_BTREE_REC_ADDR(xfs_bmbt, bb, i))
  176. #define XFS_BMAP_REC_IADDR(bb,i,cur) (XFS_BTREE_REC_ADDR(xfs_bmbt, bb, i))
  177. #define XFS_BMAP_KEY_DADDR(bb,i,cur) \
  178. (XFS_BTREE_KEY_ADDR(xfs_bmbt, bb, i))
  179. #define XFS_BMAP_KEY_IADDR(bb,i,cur) \
  180. (XFS_BTREE_KEY_ADDR(xfs_bmbt, bb, i))
  181. #define XFS_BMAP_PTR_DADDR(bb,i,cur) \
  182. (XFS_BTREE_PTR_ADDR(xfs_bmbt, bb, i, XFS_BMAP_BLOCK_DMAXRECS( \
  183. be16_to_cpu((bb)->bb_level), cur)))
  184. #define XFS_BMAP_PTR_IADDR(bb,i,cur) \
  185. (XFS_BTREE_PTR_ADDR(xfs_bmbt, bb, i, XFS_BMAP_BLOCK_IMAXRECS( \
  186. be16_to_cpu((bb)->bb_level), cur)))
  187. /*
  188. * These are to be used when we know the size of the block and
  189. * we don't have a cursor.
  190. */
  191. #define XFS_BMAP_BROOT_REC_ADDR(bb,i,sz) \
  192. (XFS_BTREE_REC_ADDR(xfs_bmbt,bb,i))
  193. #define XFS_BMAP_BROOT_KEY_ADDR(bb,i,sz) \
  194. (XFS_BTREE_KEY_ADDR(xfs_bmbt,bb,i))
  195. #define XFS_BMAP_BROOT_PTR_ADDR(bb,i,sz) \
  196. (XFS_BTREE_PTR_ADDR(xfs_bmbt,bb,i,XFS_BMAP_BROOT_MAXRECS(sz)))
  197. #define XFS_BMAP_BROOT_NUMRECS(bb) be16_to_cpu((bb)->bb_numrecs)
  198. #define XFS_BMAP_BROOT_MAXRECS(sz) XFS_BTREE_BLOCK_MAXRECS(sz,xfs_bmbt,0)
  199. #define XFS_BMAP_BROOT_SPACE_CALC(nrecs) \
  200. (int)(sizeof(xfs_bmbt_block_t) + \
  201. ((nrecs) * (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t))))
  202. #define XFS_BMAP_BROOT_SPACE(bb) \
  203. (XFS_BMAP_BROOT_SPACE_CALC(be16_to_cpu((bb)->bb_numrecs)))
  204. #define XFS_BMDR_SPACE_CALC(nrecs) \
  205. (int)(sizeof(xfs_bmdr_block_t) + \
  206. ((nrecs) * (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t))))
  207. /*
  208. * Maximum number of bmap btree levels.
  209. */
  210. #define XFS_BM_MAXLEVELS(mp,w) ((mp)->m_bm_maxlevels[(w)])
  211. #define XFS_BMAP_SANITY_CHECK(mp,bb,level) \
  212. (be32_to_cpu((bb)->bb_magic) == XFS_BMAP_MAGIC && \
  213. be16_to_cpu((bb)->bb_level) == level && \
  214. be16_to_cpu((bb)->bb_numrecs) > 0 && \
  215. be16_to_cpu((bb)->bb_numrecs) <= (mp)->m_bmap_dmxr[(level) != 0])
  216. #ifdef __KERNEL__
  217. #if defined(XFS_BMBT_TRACE)
  218. /*
  219. * Trace buffer entry types.
  220. */
  221. #define XFS_BMBT_KTRACE_ARGBI 1
  222. #define XFS_BMBT_KTRACE_ARGBII 2
  223. #define XFS_BMBT_KTRACE_ARGFFFI 3
  224. #define XFS_BMBT_KTRACE_ARGI 4
  225. #define XFS_BMBT_KTRACE_ARGIFK 5
  226. #define XFS_BMBT_KTRACE_ARGIFR 6
  227. #define XFS_BMBT_KTRACE_ARGIK 7
  228. #define XFS_BMBT_KTRACE_CUR 8
  229. #define XFS_BMBT_TRACE_SIZE 4096 /* size of global trace buffer */
  230. #define XFS_BMBT_KTRACE_SIZE 32 /* size of per-inode trace buffer */
  231. extern ktrace_t *xfs_bmbt_trace_buf;
  232. #endif
  233. /*
  234. * Prototypes for xfs_bmap.c to call.
  235. */
  236. extern void xfs_bmdr_to_bmbt(xfs_bmdr_block_t *, int, xfs_bmbt_block_t *, int);
  237. extern int xfs_bmbt_decrement(struct xfs_btree_cur *, int, int *);
  238. extern int xfs_bmbt_delete(struct xfs_btree_cur *, int *);
  239. extern void xfs_bmbt_get_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s);
  240. extern xfs_bmbt_block_t *xfs_bmbt_get_block(struct xfs_btree_cur *cur,
  241. int, struct xfs_buf **bpp);
  242. extern xfs_filblks_t xfs_bmbt_get_blockcount(xfs_bmbt_rec_t *r);
  243. extern xfs_fsblock_t xfs_bmbt_get_startblock(xfs_bmbt_rec_t *r);
  244. extern xfs_fileoff_t xfs_bmbt_get_startoff(xfs_bmbt_rec_t *r);
  245. extern xfs_exntst_t xfs_bmbt_get_state(xfs_bmbt_rec_t *r);
  246. #ifndef XFS_NATIVE_HOST
  247. extern void xfs_bmbt_disk_get_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s);
  248. extern xfs_filblks_t xfs_bmbt_disk_get_blockcount(xfs_bmbt_rec_t *r);
  249. extern xfs_fileoff_t xfs_bmbt_disk_get_startoff(xfs_bmbt_rec_t *r);
  250. #else
  251. #define xfs_bmbt_disk_get_all(r, s) xfs_bmbt_get_all(r, s)
  252. #define xfs_bmbt_disk_get_blockcount(r) xfs_bmbt_get_blockcount(r)
  253. #define xfs_bmbt_disk_get_startoff(r) xfs_bmbt_get_startoff(r)
  254. #endif /* XFS_NATIVE_HOST */
  255. extern int xfs_bmbt_increment(struct xfs_btree_cur *, int, int *);
  256. extern int xfs_bmbt_insert(struct xfs_btree_cur *, int *);
  257. extern void xfs_bmbt_log_block(struct xfs_btree_cur *, struct xfs_buf *, int);
  258. extern void xfs_bmbt_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int,
  259. int);
  260. extern int xfs_bmbt_lookup_eq(struct xfs_btree_cur *, xfs_fileoff_t,
  261. xfs_fsblock_t, xfs_filblks_t, int *);
  262. extern int xfs_bmbt_lookup_ge(struct xfs_btree_cur *, xfs_fileoff_t,
  263. xfs_fsblock_t, xfs_filblks_t, int *);
  264. /*
  265. * Give the bmap btree a new root block. Copy the old broot contents
  266. * down into a real block and make the broot point to it.
  267. */
  268. extern int xfs_bmbt_newroot(struct xfs_btree_cur *cur, int *lflags, int *stat);
  269. extern void xfs_bmbt_set_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s);
  270. extern void xfs_bmbt_set_allf(xfs_bmbt_rec_t *r, xfs_fileoff_t o,
  271. xfs_fsblock_t b, xfs_filblks_t c, xfs_exntst_t v);
  272. extern void xfs_bmbt_set_blockcount(xfs_bmbt_rec_t *r, xfs_filblks_t v);
  273. extern void xfs_bmbt_set_startblock(xfs_bmbt_rec_t *r, xfs_fsblock_t v);
  274. extern void xfs_bmbt_set_startoff(xfs_bmbt_rec_t *r, xfs_fileoff_t v);
  275. extern void xfs_bmbt_set_state(xfs_bmbt_rec_t *r, xfs_exntst_t v);
  276. #ifndef XFS_NATIVE_HOST
  277. extern void xfs_bmbt_disk_set_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s);
  278. extern void xfs_bmbt_disk_set_allf(xfs_bmbt_rec_t *r, xfs_fileoff_t o,
  279. xfs_fsblock_t b, xfs_filblks_t c, xfs_exntst_t v);
  280. #else
  281. #define xfs_bmbt_disk_set_all(r, s) xfs_bmbt_set_all(r, s)
  282. #define xfs_bmbt_disk_set_allf(r, o, b, c, v) xfs_bmbt_set_allf(r, o, b, c, v)
  283. #endif /* XFS_NATIVE_HOST */
  284. extern void xfs_bmbt_to_bmdr(xfs_bmbt_block_t *, int, xfs_bmdr_block_t *, int);
  285. extern int xfs_bmbt_update(struct xfs_btree_cur *, xfs_fileoff_t,
  286. xfs_fsblock_t, xfs_filblks_t, xfs_exntst_t);
  287. #endif /* __KERNEL__ */
  288. #endif /* __XFS_BMAP_BTREE_H__ */