db/btblock.c

   1 /*
   2  * Copyright (c) 2000-2001,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
  19 #include <xfs/libxfs.h>
  20 #include "type.h"
  21 #include "faddr.h"
  22 #include "fprint.h"
  23 #include "field.h"
  24 #include "btblock.h"
  25 #include "print.h"
  26 #include "bit.h"
  27 #include "init.h"
  28
  29
  30 /*
  31  * Definition of the possible btree block layouts.
  32  */
  33 struct xfs_db_btree {
  34         size_t                  block_len;
  35         size_t                  key_len;
  36         size_t                  rec_len;
  37         size_t                  ptr_len;
  38 } btrees[] = {
  39         [/*0x424d415*/0] = { /* BMAP */
  40                 XFS_BTREE_LBLOCK_LEN,
  41                 sizeof(xfs_bmbt_key_t),
  42                 sizeof(xfs_bmbt_rec_t),
  43                 sizeof(__be64),
  44         },
  45         [/*0x4142544*/2] = { /* ABTB */
  46                 XFS_BTREE_SBLOCK_LEN,
  47                 sizeof(xfs_alloc_key_t),
  48                 sizeof(xfs_alloc_rec_t),
  49                 sizeof(__be32),
  50         },
  51         [/*0x4142544*/3] = { /* ABTC */
  52                 XFS_BTREE_SBLOCK_LEN,
  53                 sizeof(xfs_alloc_key_t),
  54                 sizeof(xfs_alloc_rec_t),
  55                 sizeof(__be32),
  56         },
  57         [/*0x4941425*/4] = { /* IABT */
  58                 XFS_BTREE_SBLOCK_LEN,
  59                 sizeof(xfs_inobt_key_t),
  60                 sizeof(xfs_inobt_rec_t),
  61                 sizeof(__be32),
  62         },
  63 };
  64
  65 /*
  66  * Find the right block defintion for a given ondisk block.
  67  *
  68  * We use the least significant bit of the magic number as index into
  69  * the array of block defintions.
  70  */
  71 #define block_to_bt(bb) \
  72         (&btrees[be32_to_cpu((bb)->bb_magic) & 0xf])
  73
  74 /* calculate max records.  Only for non-leaves. */
  75 static int
  76 btblock_maxrecs(struct xfs_db_btree *bt, int blocksize)
  77 {
  78         blocksize -= bt->block_len;
  79
  80         return blocksize / (bt->key_len + bt->ptr_len);
  81 }
  82
  83 /*
  84  * Get the number of keys in a btree block.
  85  *
  86  * Note: can also be used to get the number of ptrs because there are
  87  * always the same number of keys and ptrs in a block.
  88  */
  89 static int
  90 btblock_key_count(
  91         void                    *obj,
  92         int                     startoff)
  93 {
  94         struct xfs_btree_block  *block = obj;
  95
  96         ASSERT(startoff == 0);
  97
  98         if (block->bb_level == 0)
  99                 return 0;
 100         return be16_to_cpu(block->bb_numrecs);
 101 }
 102
 103 /*
 104  * Get the number of keys in a btree block.
 105  */
 106 static int
 107 btblock_rec_count(
 108         void                    *obj,
 109         int                     startoff)
 110 {
 111         struct xfs_btree_block  *block = obj;
 112
 113         ASSERT(startoff == 0);
 114
 115         if (block->bb_level != 0)
 116                 return 0;
 117         return be16_to_cpu(block->bb_numrecs);
 118 }
 119
 120 /*
 121  * Get the offset of the key at idx in a btree block.
 122  */
 123 static int
 124 btblock_key_offset(
 125         void                    *obj,
 126         int                     startoff,
 127         int                     idx)
 128 {
 129         struct xfs_btree_block  *block = obj;
 130         struct xfs_db_btree     *bt = block_to_bt(block);
 131         int                     offset;
 132
 133         ASSERT(startoff == 0);
 134         ASSERT(block->bb_level != 0);
 135
 136         offset = bt->block_len + (idx - 1) * bt->key_len;
 137         return bitize(offset);
 138 }
 139
 140 /*
 141  * Get the offset of the ptr at idx in a btree block.
 142  */
 143 static int
 144 btblock_ptr_offset(
 145         void                    *obj,
 146         int                     startoff,
 147         int                     idx)
 148 {
 149         struct xfs_btree_block  *block = obj;
 150         struct xfs_db_btree     *bt = block_to_bt(block);
 151         int                     offset;
 152         int                     maxrecs;
 153
 154         ASSERT(startoff == 0);
 155         ASSERT(block->bb_level != 0);
 156
 157         maxrecs = btblock_maxrecs(bt, mp->m_sb.sb_blocksize);
 158         offset = bt->block_len +
 159                         maxrecs * bt->key_len +
 160                         (idx - 1) * bt->ptr_len;
 161
 162         return bitize(offset);
 163 }
 164
 165 /*
 166  * Get the offset of the record at idx in a btree block.
 167  */
 168 static int
 169 btblock_rec_offset(
 170         void                    *obj,
 171         int                     startoff,
 172         int                     idx)
 173 {
 174         struct xfs_btree_block  *block = obj;
 175         struct xfs_db_btree     *bt = block_to_bt(block);
 176         int                     offset;
 177
 178         ASSERT(startoff == 0);
 179         ASSERT(block->bb_level == 0);
 180
 181         offset = bt->block_len + (idx - 1) * bt->rec_len;
 182         return bitize(offset);
 183 }
 184
 185 /*
 186  * Get the size of a btree block.
 187  */
 188 int
 189 btblock_size(
 190         void    *obj,
 191         int     startoff,
 192         int     idx)
 193 {
 194         return bitize(mp->m_sb.sb_blocksize);
 195 }
 196
 197
 198 /*
 199  * Bmap btree.
 200  */
 201
 202 const field_t   bmapbta_hfld[] = {
 203         { "", FLDT_BMAPBTA, OI(0), C1, 0, TYP_NONE },
 204         { NULL }
 205 };
 206 const field_t   bmapbtd_hfld[] = {
 207         { "", FLDT_BMAPBTD, OI(0), C1, 0, TYP_NONE },
 208         { NULL }
 209 };
 210
 211 #define OFF(f)  bitize(offsetof(struct xfs_btree_block, bb_ ## f))
 212 const field_t   bmapbta_flds[] = {
 213         { "magic", FLDT_UINT32X, OI(OFF(magic)), C1, 0, TYP_NONE },
 214         { "level", FLDT_UINT16D, OI(OFF(level)), C1, 0, TYP_NONE },
 215         { "numrecs", FLDT_UINT16D, OI(OFF(numrecs)), C1, 0, TYP_NONE },
 216         { "leftsib", FLDT_DFSBNO, OI(OFF(u.l.bb_leftsib)), C1, 0, TYP_BMAPBTA },
 217         { "rightsib", FLDT_DFSBNO, OI(OFF(u.l.bb_rightsib)), C1, 0, TYP_BMAPBTA },
 218         { "recs", FLDT_BMAPBTAREC, btblock_rec_offset, btblock_rec_count,
 219           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 220         { "keys", FLDT_BMAPBTAKEY, btblock_key_offset, btblock_key_count,
 221           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 222         { "ptrs", FLDT_BMAPBTAPTR, btblock_ptr_offset, btblock_key_count,
 223           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_BMAPBTA },
 224         { NULL }
 225 };
 226 const field_t   bmapbtd_flds[] = {
 227         { "magic", FLDT_UINT32X, OI(OFF(magic)), C1, 0, TYP_NONE },
 228         { "level", FLDT_UINT16D, OI(OFF(level)), C1, 0, TYP_NONE },
 229         { "numrecs", FLDT_UINT16D, OI(OFF(numrecs)), C1, 0, TYP_NONE },
 230         { "leftsib", FLDT_DFSBNO, OI(OFF(u.l.bb_leftsib)), C1, 0, TYP_BMAPBTD },
 231         { "rightsib", FLDT_DFSBNO, OI(OFF(u.l.bb_rightsib)), C1, 0, TYP_BMAPBTD },
 232         { "recs", FLDT_BMAPBTDREC, btblock_rec_offset, btblock_rec_count,
 233           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 234         { "keys", FLDT_BMAPBTDKEY, btblock_key_offset, btblock_key_count,
 235           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 236         { "ptrs", FLDT_BMAPBTDPTR, btblock_ptr_offset, btblock_key_count,
 237           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_BMAPBTD },
 238         { NULL }
 239 };
 240 #undef OFF
 241
 242 #define KOFF(f) bitize(offsetof(xfs_bmbt_key_t, br_ ## f))
 243 const field_t   bmapbta_key_flds[] = {
 244         { "startoff", FLDT_DFILOFFA, OI(KOFF(startoff)), C1, 0, TYP_ATTR },
 245         { NULL }
 246 };
 247 const field_t   bmapbtd_key_flds[] = {
 248         { "startoff", FLDT_DFILOFFD, OI(KOFF(startoff)), C1, 0, TYP_INODATA },
 249         { NULL }
 250 };
 251 #undef KOFF
 252
 253 #ifndef XFS_NATIVE_HOST
 254
 255 #define BMBT_EXNTFLAG_BITOFF    0
 256 #define BMBT_STARTOFF_BITOFF    (BMBT_EXNTFLAG_BITOFF + BMBT_EXNTFLAG_BITLEN)
 257 #define BMBT_STARTBLOCK_BITOFF  (BMBT_STARTOFF_BITOFF + BMBT_STARTOFF_BITLEN)
 258 #define BMBT_BLOCKCOUNT_BITOFF  \
 259         (BMBT_STARTBLOCK_BITOFF + BMBT_STARTBLOCK_BITLEN)
 260
 261 #else
 262
 263 #define BMBT_EXNTFLAG_BITOFF    63
 264 #define BMBT_STARTOFF_BITOFF    (BMBT_EXNTFLAG_BITOFF - BMBT_STARTOFF_BITLEN)
 265 #define BMBT_STARTBLOCK_BITOFF  85 /* 128 - 43 (other 9 is in first word) */
 266 #define BMBT_BLOCKCOUNT_BITOFF  64 /* Start of second 64 bit container */
 267
 268 #endif /* XFS_NATIVE_HOST */
 269
 270 const field_t   bmapbta_rec_flds[] = {
 271         { "startoff", FLDT_CFILEOFFA, OI(BMBT_STARTOFF_BITOFF), C1, 0,
 272           TYP_ATTR },
 273         { "startblock", FLDT_CFSBLOCK, OI(BMBT_STARTBLOCK_BITOFF), C1, 0,
 274           TYP_ATTR },
 275         { "blockcount", FLDT_CEXTLEN, OI(BMBT_BLOCKCOUNT_BITOFF), C1, 0,
 276           TYP_NONE },
 277         { "extentflag", FLDT_CEXTFLG, OI(BMBT_EXNTFLAG_BITOFF), C1, 0,
 278           TYP_NONE },
 279         { NULL }
 280 };
 281 const field_t   bmapbtd_rec_flds[] = {
 282         { "startoff", FLDT_CFILEOFFD, OI(BMBT_STARTOFF_BITOFF), C1, 0,
 283           TYP_INODATA },
 284         { "startblock", FLDT_CFSBLOCK, OI(BMBT_STARTBLOCK_BITOFF), C1, 0,
 285           TYP_INODATA },
 286         { "blockcount", FLDT_CEXTLEN, OI(BMBT_BLOCKCOUNT_BITOFF), C1, 0,
 287           TYP_NONE },
 288         { "extentflag", FLDT_CEXTFLG, OI(BMBT_EXNTFLAG_BITOFF), C1, 0,
 289           TYP_NONE },
 290         { NULL }
 291 };
 292
 293
 294 /*
 295  * Inode allocation btree.
 296  */
 297
 298 const field_t   inobt_hfld[] = {
 299         { "", FLDT_INOBT, OI(0), C1, 0, TYP_NONE },
 300         { NULL }
 301 };
 302
 303 #define OFF(f)  bitize(offsetof(struct xfs_btree_block, bb_ ## f))
 304 const field_t   inobt_flds[] = {
 305         { "magic", FLDT_UINT32X, OI(OFF(magic)), C1, 0, TYP_NONE },
 306         { "level", FLDT_UINT16D, OI(OFF(level)), C1, 0, TYP_NONE },
 307         { "numrecs", FLDT_UINT16D, OI(OFF(numrecs)), C1, 0, TYP_NONE },
 308         { "leftsib", FLDT_AGBLOCK, OI(OFF(u.s.bb_leftsib)), C1, 0, TYP_INOBT },
 309         { "rightsib", FLDT_AGBLOCK, OI(OFF(u.s.bb_rightsib)), C1, 0, TYP_INOBT },
 310         { "recs", FLDT_INOBTREC, btblock_rec_offset, btblock_rec_count,
 311           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 312         { "keys", FLDT_INOBTKEY, btblock_key_offset, btblock_key_count,
 313           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 314         { "ptrs", FLDT_INOBTPTR, btblock_ptr_offset, btblock_key_count,
 315           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_INOBT },
 316         { NULL }
 317 };
 318 #undef OFF
 319
 320 #define KOFF(f) bitize(offsetof(xfs_inobt_key_t, ir_ ## f))
 321 const field_t   inobt_key_flds[] = {
 322         { "startino", FLDT_AGINO, OI(KOFF(startino)), C1, 0, TYP_INODE },
 323         { NULL }
 324 };
 325 #undef KOFF
 326
 327 #define ROFF(f) bitize(offsetof(xfs_inobt_rec_t, ir_ ## f))
 328 const field_t   inobt_rec_flds[] = {
 329         { "startino", FLDT_AGINO, OI(ROFF(startino)), C1, 0, TYP_INODE },
 330         { "freecount", FLDT_INT32D, OI(ROFF(freecount)), C1, 0, TYP_NONE },
 331         { "free", FLDT_INOFREE, OI(ROFF(free)), C1, 0, TYP_NONE },
 332         { NULL }
 333 };
 334 #undef ROFF
 335
 336
 337 /*
 338  * Allocation btrees.
 339  */
 340 const field_t   bnobt_hfld[] = {
 341         { "", FLDT_BNOBT, OI(0), C1, 0, TYP_NONE },
 342         { NULL }
 343 };
 344
 345 #define OFF(f)  bitize(offsetof(struct xfs_btree_block, bb_ ## f))
 346 const field_t   bnobt_flds[] = {
 347         { "magic", FLDT_UINT32X, OI(OFF(magic)), C1, 0, TYP_NONE },
 348         { "level", FLDT_UINT16D, OI(OFF(level)), C1, 0, TYP_NONE },
 349         { "numrecs", FLDT_UINT16D, OI(OFF(numrecs)), C1, 0, TYP_NONE },
 350         { "leftsib", FLDT_AGBLOCK, OI(OFF(u.s.bb_leftsib)), C1, 0, TYP_BNOBT },
 351         { "rightsib", FLDT_AGBLOCK, OI(OFF(u.s.bb_rightsib)), C1, 0, TYP_BNOBT },
 352         { "recs", FLDT_BNOBTREC, btblock_rec_offset, btblock_rec_count,
 353           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 354         { "keys", FLDT_BNOBTKEY, btblock_key_offset, btblock_key_count,
 355           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 356         { "ptrs", FLDT_BNOBTPTR, btblock_ptr_offset, btblock_key_count,
 357           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_BNOBT },
 358         { NULL }
 359 };
 360 #undef OFF
 361
 362 #define KOFF(f) bitize(offsetof(xfs_alloc_key_t, ar_ ## f))
 363 const field_t   bnobt_key_flds[] = {
 364         { "startblock", FLDT_AGBLOCK, OI(KOFF(startblock)), C1, 0, TYP_DATA },
 365         { "blockcount", FLDT_EXTLEN, OI(KOFF(blockcount)), C1, 0, TYP_NONE },
 366         { NULL }
 367 };
 368 #undef KOFF
 369
 370 #define ROFF(f) bitize(offsetof(xfs_alloc_rec_t, ar_ ## f))
 371 const field_t   bnobt_rec_flds[] = {
 372         { "startblock", FLDT_AGBLOCK, OI(ROFF(startblock)), C1, 0, TYP_DATA },
 373         { "blockcount", FLDT_EXTLEN, OI(ROFF(blockcount)), C1, 0, TYP_NONE },
 374         { NULL }
 375 };
 376 #undef ROFF
 377
 378 const field_t   cntbt_hfld[] = {
 379         { "", FLDT_CNTBT, OI(0), C1, 0, TYP_NONE },
 380         { NULL }
 381 };
 382
 383 #define OFF(f)  bitize(offsetof(struct xfs_btree_block, bb_ ## f))
 384 const field_t   cntbt_flds[] = {
 385         { "magic", FLDT_UINT32X, OI(OFF(magic)), C1, 0, TYP_NONE },
 386         { "level", FLDT_UINT16D, OI(OFF(level)), C1, 0, TYP_NONE },
 387         { "numrecs", FLDT_UINT16D, OI(OFF(numrecs)), C1, 0, TYP_NONE },
 388         { "leftsib", FLDT_AGBLOCK, OI(OFF(u.s.bb_leftsib)), C1, 0, TYP_CNTBT },
 389         { "rightsib", FLDT_AGBLOCK, OI(OFF(u.s.bb_rightsib)), C1, 0, TYP_CNTBT },
 390         { "recs", FLDT_CNTBTREC, btblock_rec_offset, btblock_rec_count,
 391           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 392         { "keys", FLDT_CNTBTKEY, btblock_key_offset, btblock_key_count,
 393           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_NONE },
 394         { "ptrs", FLDT_CNTBTPTR, btblock_ptr_offset, btblock_key_count,
 395           FLD_ARRAY|FLD_ABASE1|FLD_COUNT|FLD_OFFSET, TYP_CNTBT },
 396         { NULL }
 397 };
 398 #undef OFF
 399
 400 #define KOFF(f) bitize(offsetof(xfs_alloc_key_t, ar_ ## f))
 401 const field_t   cntbt_key_flds[] = {
 402         { "blockcount", FLDT_EXTLEN, OI(KOFF(blockcount)), C1, 0, TYP_NONE },
 403         { "startblock", FLDT_AGBLOCK, OI(KOFF(startblock)), C1, 0, TYP_DATA },
 404         { NULL }
 405 };
 406 #undef KOFF
 407
 408 #define ROFF(f) bitize(offsetof(xfs_alloc_rec_t, ar_ ## f))
 409 const field_t   cntbt_rec_flds[] = {
 410         { "startblock", FLDT_AGBLOCK, OI(ROFF(startblock)), C1, 0, TYP_DATA },
 411         { "blockcount", FLDT_EXTLEN, OI(ROFF(blockcount)), C1, 0, TYP_NONE },
 412         { NULL }
 413 };
 414 #undef ROFF