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