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 __be64 br_startoff; /* starting file offset */ 168} xfs_bmbt_key_t, xfs_bmdr_key_t; 169 170/* btree pointer type */ 171typedef __be64 xfs_bmbt_ptr_t, xfs_bmdr_ptr_t; 172 173/* btree block header type */ 174typedef struct xfs_btree_lblock xfs_bmbt_block_t; 175 176#define XFS_BUF_TO_BMBT_BLOCK(bp) ((xfs_bmbt_block_t *)XFS_BUF_PTR(bp)) 177 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_DMAXRECS(lev,cur) \ 184 (((lev) == (cur)->bc_nlevels - 1 ? \ 185 XFS_BTREE_BLOCK_MAXRECS(XFS_BMAP_RBLOCK_DSIZE(lev,cur), \ 186 xfs_bmdr, (lev) == 0) : \ 187 ((cur)->bc_mp->m_bmap_dmxr[(lev) != 0]))) 188#define XFS_BMAP_BLOCK_IMAXRECS(lev,cur) \ 189 (((lev) == (cur)->bc_nlevels - 1 ? \ 190 XFS_BTREE_BLOCK_MAXRECS(XFS_BMAP_RBLOCK_ISIZE(lev,cur),\ 191 xfs_bmbt, (lev) == 0) : \ 192 ((cur)->bc_mp->m_bmap_dmxr[(lev) != 0]))) 193 194#define XFS_BMAP_BLOCK_DMINRECS(lev,cur) \ 195 (((lev) == (cur)->bc_nlevels - 1 ? \ 196 XFS_BTREE_BLOCK_MINRECS(XFS_BMAP_RBLOCK_DSIZE(lev,cur),\ 197 xfs_bmdr, (lev) == 0) : \ 198 ((cur)->bc_mp->m_bmap_dmnr[(lev) != 0]))) 199#define XFS_BMAP_BLOCK_IMINRECS(lev,cur) \ 200 (((lev) == (cur)->bc_nlevels - 1 ? \ 201 XFS_BTREE_BLOCK_MINRECS(XFS_BMAP_RBLOCK_ISIZE(lev,cur),\ 202 xfs_bmbt, (lev) == 0) : \ 203 ((cur)->bc_mp->m_bmap_dmnr[(lev) != 0]))) 204 205#define XFS_BMAP_REC_DADDR(bb,i,cur) (XFS_BTREE_REC_ADDR(xfs_bmbt, bb, i)) 206 207#define XFS_BMAP_REC_IADDR(bb,i,cur) (XFS_BTREE_REC_ADDR(xfs_bmbt, bb, i)) 208 209#define XFS_BMAP_KEY_DADDR(bb,i,cur) \ 210 (XFS_BTREE_KEY_ADDR(xfs_bmbt, bb, i)) 211 212#define XFS_BMAP_KEY_IADDR(bb,i,cur) \ 213 (XFS_BTREE_KEY_ADDR(xfs_bmbt, bb, i)) 214 215#define XFS_BMAP_PTR_DADDR(bb,i,cur) \ 216 (XFS_BTREE_PTR_ADDR(xfs_bmbt, bb, i, XFS_BMAP_BLOCK_DMAXRECS( \ 217 be16_to_cpu((bb)->bb_level), cur))) 218#define XFS_BMAP_PTR_IADDR(bb,i,cur) \ 219 (XFS_BTREE_PTR_ADDR(xfs_bmbt, bb, i, XFS_BMAP_BLOCK_IMAXRECS( \ 220 be16_to_cpu((bb)->bb_level), cur))) 221 222/* 223 * These are to be used when we know the size of the block and 224 * we don't have a cursor. 225 */ 226#define XFS_BMAP_BROOT_REC_ADDR(bb,i,sz) \ 227 (XFS_BTREE_REC_ADDR(xfs_bmbt,bb,i)) 228#define XFS_BMAP_BROOT_KEY_ADDR(bb,i,sz) \ 229 (XFS_BTREE_KEY_ADDR(xfs_bmbt,bb,i)) 230#define XFS_BMAP_BROOT_PTR_ADDR(bb,i,sz) \ 231 (XFS_BTREE_PTR_ADDR(xfs_bmbt,bb,i,XFS_BMAP_BROOT_MAXRECS(sz))) 232 233#define XFS_BMAP_BROOT_NUMRECS(bb) be16_to_cpu((bb)->bb_numrecs) 234#define XFS_BMAP_BROOT_MAXRECS(sz) XFS_BTREE_BLOCK_MAXRECS(sz,xfs_bmbt,0) 235 236#define XFS_BMAP_BROOT_SPACE_CALC(nrecs) \ 237 (int)(sizeof(xfs_bmbt_block_t) + \ 238 ((nrecs) * (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t)))) 239 240#define XFS_BMAP_BROOT_SPACE(bb) \ 241 (XFS_BMAP_BROOT_SPACE_CALC(be16_to_cpu((bb)->bb_numrecs))) 242#define XFS_BMDR_SPACE_CALC(nrecs) \ 243 (int)(sizeof(xfs_bmdr_block_t) + \ 244 ((nrecs) * (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t)))) 245 246/* 247 * Maximum number of bmap btree levels. 248 */ 249#define XFS_BM_MAXLEVELS(mp,w) ((mp)->m_bm_maxlevels[(w)]) 250 251#define XFS_BMAP_SANITY_CHECK(mp,bb,level) \ 252 (be32_to_cpu((bb)->bb_magic) == XFS_BMAP_MAGIC && \ 253 be16_to_cpu((bb)->bb_level) == level && \ 254 be16_to_cpu((bb)->bb_numrecs) > 0 && \ 255 be16_to_cpu((bb)->bb_numrecs) <= (mp)->m_bmap_dmxr[(level) != 0]) 256 257 258#ifdef __KERNEL__ 259 260#if defined(XFS_BMBT_TRACE) 261/* 262 * Trace buffer entry types. 263 */ 264#define XFS_BMBT_KTRACE_ARGBI 1 265#define XFS_BMBT_KTRACE_ARGBII 2 266#define XFS_BMBT_KTRACE_ARGFFFI 3 267#define XFS_BMBT_KTRACE_ARGI 4 268#define XFS_BMBT_KTRACE_ARGIFK 5 269#define XFS_BMBT_KTRACE_ARGIFR 6 270#define XFS_BMBT_KTRACE_ARGIK 7 271#define XFS_BMBT_KTRACE_CUR 8 272 273#define XFS_BMBT_TRACE_SIZE 4096 /* size of global trace buffer */ 274#define XFS_BMBT_KTRACE_SIZE 32 /* size of per-inode trace buffer */ 275extern ktrace_t *xfs_bmbt_trace_buf; 276#endif 277 278/* 279 * Prototypes for xfs_bmap.c to call. 280 */ 281extern void xfs_bmdr_to_bmbt(xfs_bmdr_block_t *, int, xfs_bmbt_block_t *, int); 282extern int xfs_bmbt_decrement(struct xfs_btree_cur *, int, int *); 283extern int xfs_bmbt_delete(struct xfs_btree_cur *, int *); 284extern void xfs_bmbt_get_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s); 285extern xfs_bmbt_block_t *xfs_bmbt_get_block(struct xfs_btree_cur *cur, 286 int, struct xfs_buf **bpp); 287extern xfs_filblks_t xfs_bmbt_get_blockcount(xfs_bmbt_rec_t *r); 288extern xfs_fsblock_t xfs_bmbt_get_startblock(xfs_bmbt_rec_t *r); 289extern xfs_fileoff_t xfs_bmbt_get_startoff(xfs_bmbt_rec_t *r); 290extern xfs_exntst_t xfs_bmbt_get_state(xfs_bmbt_rec_t *r); 291 292#ifndef XFS_NATIVE_HOST 293extern void xfs_bmbt_disk_get_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s); 294extern xfs_filblks_t xfs_bmbt_disk_get_blockcount(xfs_bmbt_rec_t *r); 295extern xfs_fileoff_t xfs_bmbt_disk_get_startoff(xfs_bmbt_rec_t *r); 296#else 297#define xfs_bmbt_disk_get_all(r, s) xfs_bmbt_get_all(r, s) 298#define xfs_bmbt_disk_get_blockcount(r) xfs_bmbt_get_blockcount(r) 299#define xfs_bmbt_disk_get_startoff(r) xfs_bmbt_get_startoff(r) 300#endif /* XFS_NATIVE_HOST */ 301 302extern int xfs_bmbt_increment(struct xfs_btree_cur *, int, int *); 303extern int xfs_bmbt_insert(struct xfs_btree_cur *, int *); 304extern void xfs_bmbt_log_block(struct xfs_btree_cur *, struct xfs_buf *, int); 305extern void xfs_bmbt_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, 306 int); 307extern int xfs_bmbt_lookup_eq(struct xfs_btree_cur *, xfs_fileoff_t, 308 xfs_fsblock_t, xfs_filblks_t, int *); 309extern int xfs_bmbt_lookup_ge(struct xfs_btree_cur *, xfs_fileoff_t, 310 xfs_fsblock_t, xfs_filblks_t, int *); 311 312/* 313 * Give the bmap btree a new root block. Copy the old broot contents 314 * down into a real block and make the broot point to it. 315 */ 316extern int xfs_bmbt_newroot(struct xfs_btree_cur *cur, int *lflags, int *stat); 317 318extern void xfs_bmbt_set_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s); 319extern void xfs_bmbt_set_allf(xfs_bmbt_rec_t *r, xfs_fileoff_t o, 320 xfs_fsblock_t b, xfs_filblks_t c, xfs_exntst_t v); 321extern void xfs_bmbt_set_blockcount(xfs_bmbt_rec_t *r, xfs_filblks_t v); 322extern void xfs_bmbt_set_startblock(xfs_bmbt_rec_t *r, xfs_fsblock_t v); 323extern void xfs_bmbt_set_startoff(xfs_bmbt_rec_t *r, xfs_fileoff_t v); 324extern void xfs_bmbt_set_state(xfs_bmbt_rec_t *r, xfs_exntst_t v); 325 326#ifndef XFS_NATIVE_HOST 327extern void xfs_bmbt_disk_set_all(xfs_bmbt_rec_t *r, xfs_bmbt_irec_t *s); 328extern void xfs_bmbt_disk_set_allf(xfs_bmbt_rec_t *r, xfs_fileoff_t o, 329 xfs_fsblock_t b, xfs_filblks_t c, xfs_exntst_t v); 330#else 331#define xfs_bmbt_disk_set_all(r, s) xfs_bmbt_set_all(r, s) 332#define xfs_bmbt_disk_set_allf(r, o, b, c, v) xfs_bmbt_set_allf(r, o, b, c, v) 333#endif /* XFS_NATIVE_HOST */ 334 335extern void xfs_bmbt_to_bmdr(xfs_bmbt_block_t *, int, xfs_bmdr_block_t *, int); 336extern int xfs_bmbt_update(struct xfs_btree_cur *, xfs_fileoff_t, 337 xfs_fsblock_t, xfs_filblks_t, xfs_exntst_t); 338 339#endif /* __KERNEL__ */ 340 341#endif /* __XFS_BMAP_BTREE_H__ */ 342