git.oblomov.eu Git - linux-2.6/blob - fs/xfs/xfs_btree.h

   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 #ifndef __XFS_BTREE_H__
  19 #define __XFS_BTREE_H__
  20
  21 struct xfs_buf;
  22 struct xfs_bmap_free;
  23 struct xfs_inode;
  24 struct xfs_mount;
  25 struct xfs_trans;
  26
  27 extern kmem_zone_t      *xfs_btree_cur_zone;
  28
  29 /*
  30  * This nonsense is to make -wlint happy.
  31  */
  32 #define XFS_LOOKUP_EQ   ((xfs_lookup_t)XFS_LOOKUP_EQi)
  33 #define XFS_LOOKUP_LE   ((xfs_lookup_t)XFS_LOOKUP_LEi)
  34 #define XFS_LOOKUP_GE   ((xfs_lookup_t)XFS_LOOKUP_GEi)
  35
  36 #define XFS_BTNUM_BNO   ((xfs_btnum_t)XFS_BTNUM_BNOi)
  37 #define XFS_BTNUM_CNT   ((xfs_btnum_t)XFS_BTNUM_CNTi)
  38 #define XFS_BTNUM_BMAP  ((xfs_btnum_t)XFS_BTNUM_BMAPi)
  39 #define XFS_BTNUM_INO   ((xfs_btnum_t)XFS_BTNUM_INOi)
  40
  41 /*
  42  * Short form header: space allocation btrees.
  43  */
  44 typedef struct xfs_btree_sblock {
  45         __be32          bb_magic;       /* magic number for block type */
  46         __be16          bb_level;       /* 0 is a leaf */
  47         __be16          bb_numrecs;     /* current # of data records */
  48         __be32          bb_leftsib;     /* left sibling block or NULLAGBLOCK */
  49         __be32          bb_rightsib;    /* right sibling block or NULLAGBLOCK */
  50 } xfs_btree_sblock_t;
  51
  52 /*
  53  * Long form header: bmap btrees.
  54  */
  55 typedef struct xfs_btree_lblock {
  56         __be32          bb_magic;       /* magic number for block type */
  57         __be16          bb_level;       /* 0 is a leaf */
  58         __be16          bb_numrecs;     /* current # of data records */
  59         __be64          bb_leftsib;     /* left sibling block or NULLDFSBNO */
  60         __be64          bb_rightsib;    /* right sibling block or NULLDFSBNO */
  61 } xfs_btree_lblock_t;
  62
  63 /*
  64  * Combined header and structure, used by common code.
  65  */
  66 typedef struct xfs_btree_block {
  67         __be32          bb_magic;       /* magic number for block type */
  68         __be16          bb_level;       /* 0 is a leaf */
  69         __be16          bb_numrecs;     /* current # of data records */
  70         union {
  71                 struct {
  72                         __be32          bb_leftsib;
  73                         __be32          bb_rightsib;
  74                 } s;                    /* short form pointers */
  75                 struct  {
  76                         __be64          bb_leftsib;
  77                         __be64          bb_rightsib;
  78                 } l;                    /* long form pointers */
  79         } bb_u;                         /* rest */
  80 } xfs_btree_block_t;
  81
  82 /*
  83  * Generic key, ptr and record wrapper structures.
  84  *
  85  * These are disk format structures, and are converted where necessary
  86  * by the btree specific code that needs to interpret them.
  87  */
  88 union xfs_btree_ptr {
  89         __be32                  s;      /* short form ptr */
  90         __be64                  l;      /* long form ptr */
  91 };
  92
  93 union xfs_btree_key {
  94         xfs_bmbt_key_t          bmbt;
  95         xfs_bmdr_key_t          bmbr;   /* bmbt root block */
  96         xfs_alloc_key_t         alloc;
  97         xfs_inobt_key_t         inobt;
  98 };
  99
 100 union xfs_btree_rec {
 101         xfs_bmbt_rec_t          bmbt;
 102         xfs_bmdr_rec_t          bmbr;   /* bmbt root block */
 103         xfs_alloc_rec_t         alloc;
 104         xfs_inobt_rec_t         inobt;
 105 };
 106
 107 /*
 108  * For logging record fields.
 109  */
 110 #define XFS_BB_MAGIC            0x01
 111 #define XFS_BB_LEVEL            0x02
 112 #define XFS_BB_NUMRECS          0x04
 113 #define XFS_BB_LEFTSIB          0x08
 114 #define XFS_BB_RIGHTSIB         0x10
 115 #define XFS_BB_NUM_BITS         5
 116 #define XFS_BB_ALL_BITS         ((1 << XFS_BB_NUM_BITS) - 1)
 117
 118 /*
 119  * Magic numbers for btree blocks.
 120  */
 121 extern const __uint32_t xfs_magics[];
 122
 123 /*
 124  * Generic stats interface
 125  */
 126 #define __XFS_BTREE_STATS_INC(type, stat) \
 127         XFS_STATS_INC(xs_ ## type ## _2_ ## stat)
 128 #define XFS_BTREE_STATS_INC(cur, stat)  \
 129 do {    \
 130         switch (cur->bc_btnum) {  \
 131         case XFS_BTNUM_BNO: __XFS_BTREE_STATS_INC(abtb, stat); break;   \
 132         case XFS_BTNUM_CNT: __XFS_BTREE_STATS_INC(abtc, stat); break;   \
 133         case XFS_BTNUM_BMAP: __XFS_BTREE_STATS_INC(bmbt, stat); break;  \
 134         case XFS_BTNUM_INO: __XFS_BTREE_STATS_INC(ibt, stat); break;    \
 135         case XFS_BTNUM_MAX: ASSERT(0); /* fucking gcc */ ; break;       \
 136         }       \
 137 } while (0)
 138
 139 #define __XFS_BTREE_STATS_ADD(type, stat, val) \
 140         XFS_STATS_ADD(xs_ ## type ## _2_ ## stat, val)
 141 #define XFS_BTREE_STATS_ADD(cur, stat, val)  \
 142 do {    \
 143         switch (cur->bc_btnum) {  \
 144         case XFS_BTNUM_BNO: __XFS_BTREE_STATS_ADD(abtb, stat, val); break; \
 145         case XFS_BTNUM_CNT: __XFS_BTREE_STATS_ADD(abtc, stat, val); break; \
 146         case XFS_BTNUM_BMAP: __XFS_BTREE_STATS_ADD(bmbt, stat, val); break; \
 147         case XFS_BTNUM_INO: __XFS_BTREE_STATS_ADD(ibt, stat, val); break; \
 148         case XFS_BTNUM_MAX: ASSERT(0); /* fucking gcc */ ; break;       \
 149         }       \
 150 } while (0)
 151
 152 #define XFS_BTREE_MAXLEVELS     8       /* max of all btrees */
 153
 154 struct xfs_btree_ops {
 155         /* size of the key and record structures */
 156         size_t  key_len;
 157         size_t  rec_len;
 158
 159         /* cursor operations */
 160         struct xfs_btree_cur *(*dup_cursor)(struct xfs_btree_cur *);
 161         void    (*update_cursor)(struct xfs_btree_cur *src,
 162                                  struct xfs_btree_cur *dst);
 163
 164         /* update btree root pointer */
 165         void    (*set_root)(struct xfs_btree_cur *cur,
 166                                 union xfs_btree_ptr *nptr, int level_change);
 167         int     (*kill_root)(struct xfs_btree_cur *cur, struct xfs_buf *bp,
 168                                 int level, union xfs_btree_ptr *newroot);
 169
 170         /* block allocation / freeing */
 171         int     (*alloc_block)(struct xfs_btree_cur *cur,
 172                                union xfs_btree_ptr *start_bno,
 173                                union xfs_btree_ptr *new_bno,
 174                                int length, int *stat);
 175         int     (*free_block)(struct xfs_btree_cur *cur, struct xfs_buf *bp);
 176
 177         /* update last record information */
 178         void    (*update_lastrec)(struct xfs_btree_cur *cur,
 179                                   struct xfs_btree_block *block,
 180                                   union xfs_btree_rec *rec,
 181                                   int ptr, int reason);
 182
 183         /* records in block/level */
 184         int     (*get_minrecs)(struct xfs_btree_cur *cur, int level);
 185         int     (*get_maxrecs)(struct xfs_btree_cur *cur, int level);
 186
 187         /* records on disk.  Matter for the root in inode case. */
 188         int     (*get_dmaxrecs)(struct xfs_btree_cur *cur, int level);
 189
 190         /* init values of btree structures */
 191         void    (*init_key_from_rec)(union xfs_btree_key *key,
 192                                      union xfs_btree_rec *rec);
 193         void    (*init_rec_from_key)(union xfs_btree_key *key,
 194                                      union xfs_btree_rec *rec);
 195         void    (*init_rec_from_cur)(struct xfs_btree_cur *cur,
 196                                      union xfs_btree_rec *rec);
 197         void    (*init_ptr_from_cur)(struct xfs_btree_cur *cur,
 198                                      union xfs_btree_ptr *ptr);
 199
 200         /* difference between key value and cursor value */
 201         __int64_t (*key_diff)(struct xfs_btree_cur *cur,
 202                               union xfs_btree_key *key);
 203
 204 #ifdef DEBUG
 205         /* check that k1 is lower than k2 */
 206         int     (*keys_inorder)(struct xfs_btree_cur *cur,
 207                                 union xfs_btree_key *k1,
 208                                 union xfs_btree_key *k2);
 209
 210         /* check that r1 is lower than r2 */
 211         int     (*recs_inorder)(struct xfs_btree_cur *cur,
 212                                 union xfs_btree_rec *r1,
 213                                 union xfs_btree_rec *r2);
 214 #endif
 215
 216         /* btree tracing */
 217 #ifdef XFS_BTREE_TRACE
 218         void            (*trace_enter)(struct xfs_btree_cur *, const char *,
 219                                        char *, int, int, __psunsigned_t,
 220                                        __psunsigned_t, __psunsigned_t,
 221                                        __psunsigned_t, __psunsigned_t,
 222                                        __psunsigned_t, __psunsigned_t,
 223                                        __psunsigned_t, __psunsigned_t,
 224                                        __psunsigned_t, __psunsigned_t);
 225         void            (*trace_cursor)(struct xfs_btree_cur *, __uint32_t *,
 226                                         __uint64_t *, __uint64_t *);
 227         void            (*trace_key)(struct xfs_btree_cur *,
 228                                      union xfs_btree_key *, __uint64_t *,
 229                                      __uint64_t *);
 230         void            (*trace_record)(struct xfs_btree_cur *,
 231                                         union xfs_btree_rec *, __uint64_t *,
 232                                         __uint64_t *, __uint64_t *);
 233 #endif
 234 };
 235
 236 /*
 237  * Reasons for the update_lastrec method to be called.
 238  */
 239 #define LASTREC_UPDATE  0
 240 #define LASTREC_INSREC  1
 241 #define LASTREC_DELREC  2
 242
 243
 244 /*
 245  * Btree cursor structure.
 246  * This collects all information needed by the btree code in one place.
 247  */
 248 typedef struct xfs_btree_cur
 249 {
 250         struct xfs_trans        *bc_tp; /* transaction we're in, if any */
 251         struct xfs_mount        *bc_mp; /* file system mount struct */
 252         const struct xfs_btree_ops *bc_ops;
 253         uint                    bc_flags; /* btree features - below */
 254         union {
 255                 xfs_alloc_rec_incore_t  a;
 256                 xfs_bmbt_irec_t         b;
 257                 xfs_inobt_rec_incore_t  i;
 258         }               bc_rec;         /* current insert/search record value */
 259         struct xfs_buf  *bc_bufs[XFS_BTREE_MAXLEVELS];  /* buf ptr per level */
 260         int             bc_ptrs[XFS_BTREE_MAXLEVELS];   /* key/record # */
 261         __uint8_t       bc_ra[XFS_BTREE_MAXLEVELS];     /* readahead bits */
 262 #define XFS_BTCUR_LEFTRA        1       /* left sibling has been read-ahead */
 263 #define XFS_BTCUR_RIGHTRA       2       /* right sibling has been read-ahead */
 264         __uint8_t       bc_nlevels;     /* number of levels in the tree */
 265         __uint8_t       bc_blocklog;    /* log2(blocksize) of btree blocks */
 266         xfs_btnum_t     bc_btnum;       /* identifies which btree type */
 267         union {
 268                 struct {                        /* needed for BNO, CNT, INO */
 269                         struct xfs_buf  *agbp;  /* agf/agi buffer pointer */
 270                         xfs_agnumber_t  agno;   /* ag number */
 271                 } a;
 272                 struct {                        /* needed for BMAP */
 273                         struct xfs_inode *ip;   /* pointer to our inode */
 274                         struct xfs_bmap_free *flist;    /* list to free after */
 275                         xfs_fsblock_t   firstblock;     /* 1st blk allocated */
 276                         int             allocated;      /* count of alloced */
 277                         short           forksize;       /* fork's inode space */
 278                         char            whichfork;      /* data or attr fork */
 279                         char            flags;          /* flags */
 280 #define XFS_BTCUR_BPRV_WASDEL   1                       /* was delayed */
 281                 } b;
 282         }               bc_private;     /* per-btree type data */
 283 } xfs_btree_cur_t;
 284
 285 /* cursor flags */
 286 #define XFS_BTREE_LONG_PTRS             (1<<0)  /* pointers are 64bits long */
 287 #define XFS_BTREE_ROOT_IN_INODE         (1<<1)  /* root may be variable size */
 288 #define XFS_BTREE_LASTREC_UPDATE        (1<<2)  /* track last rec externally */
 289
 290
 291 #define XFS_BTREE_NOERROR       0
 292 #define XFS_BTREE_ERROR         1
 293
 294 /*
 295  * Convert from buffer to btree block header.
 296  */
 297 #define XFS_BUF_TO_BLOCK(bp)    ((xfs_btree_block_t *)XFS_BUF_PTR(bp))
 298 #define XFS_BUF_TO_LBLOCK(bp)   ((xfs_btree_lblock_t *)XFS_BUF_PTR(bp))
 299 #define XFS_BUF_TO_SBLOCK(bp)   ((xfs_btree_sblock_t *)XFS_BUF_PTR(bp))
 300
 301
 302 /*
 303  * Check that long form block header is ok.
 304  */
 305 int                                     /* error (0 or EFSCORRUPTED) */
 306 xfs_btree_check_lblock(
 307         struct xfs_btree_cur    *cur,   /* btree cursor */
 308         struct xfs_btree_lblock *block, /* btree long form block pointer */
 309         int                     level,  /* level of the btree block */
 310         struct xfs_buf          *bp);   /* buffer containing block, if any */
 311
 312 /*
 313  * Check that block header is ok.
 314  */
 315 int
 316 xfs_btree_check_block(
 317         struct xfs_btree_cur    *cur,   /* btree cursor */
 318         struct xfs_btree_block  *block, /* generic btree block pointer */
 319         int                     level,  /* level of the btree block */
 320         struct xfs_buf          *bp);   /* buffer containing block, if any */
 321
 322 /*
 323  * Check that (long) pointer is ok.
 324  */
 325 int                                     /* error (0 or EFSCORRUPTED) */
 326 xfs_btree_check_lptr(
 327         struct xfs_btree_cur    *cur,   /* btree cursor */
 328         xfs_dfsbno_t            ptr,    /* btree block disk address */
 329         int                     level); /* btree block level */
 330
 331 /*
 332  * Delete the btree cursor.
 333  */
 334 void
 335 xfs_btree_del_cursor(
 336         xfs_btree_cur_t         *cur,   /* btree cursor */
 337         int                     error); /* del because of error */
 338
 339 /*
 340  * Duplicate the btree cursor.
 341  * Allocate a new one, copy the record, re-get the buffers.
 342  */
 343 int                                     /* error */
 344 xfs_btree_dup_cursor(
 345         xfs_btree_cur_t         *cur,   /* input cursor */
 346         xfs_btree_cur_t         **ncur);/* output cursor */
 347
 348 /*
 349  * Get a buffer for the block, return it with no data read.
 350  * Long-form addressing.
 351  */
 352 struct xfs_buf *                                /* buffer for fsbno */
 353 xfs_btree_get_bufl(
 354         struct xfs_mount        *mp,    /* file system mount point */
 355         struct xfs_trans        *tp,    /* transaction pointer */
 356         xfs_fsblock_t           fsbno,  /* file system block number */
 357         uint                    lock);  /* lock flags for get_buf */
 358
 359 /*
 360  * Get a buffer for the block, return it with no data read.
 361  * Short-form addressing.
 362  */
 363 struct xfs_buf *                                /* buffer for agno/agbno */
 364 xfs_btree_get_bufs(
 365         struct xfs_mount        *mp,    /* file system mount point */
 366         struct xfs_trans        *tp,    /* transaction pointer */
 367         xfs_agnumber_t          agno,   /* allocation group number */
 368         xfs_agblock_t           agbno,  /* allocation group block number */
 369         uint                    lock);  /* lock flags for get_buf */
 370
 371 /*
 372  * Check for the cursor referring to the last block at the given level.
 373  */
 374 int                                     /* 1=is last block, 0=not last block */
 375 xfs_btree_islastblock(
 376         xfs_btree_cur_t         *cur,   /* btree cursor */
 377         int                     level); /* level to check */
 378
 379 /*
 380  * Compute first and last byte offsets for the fields given.
 381  * Interprets the offsets table, which contains struct field offsets.
 382  */
 383 void
 384 xfs_btree_offsets(
 385         __int64_t               fields, /* bitmask of fields */
 386         const short             *offsets,/* table of field offsets */
 387         int                     nbits,  /* number of bits to inspect */
 388         int                     *first, /* output: first byte offset */
 389         int                     *last); /* output: last byte offset */
 390
 391 /*
 392  * Get a buffer for the block, return it read in.
 393  * Long-form addressing.
 394  */
 395 int                                     /* error */
 396 xfs_btree_read_bufl(
 397         struct xfs_mount        *mp,    /* file system mount point */
 398         struct xfs_trans        *tp,    /* transaction pointer */
 399         xfs_fsblock_t           fsbno,  /* file system block number */
 400         uint                    lock,   /* lock flags for read_buf */
 401         struct xfs_buf          **bpp,  /* buffer for fsbno */
 402         int                     refval);/* ref count value for buffer */
 403
 404 /*
 405  * Get a buffer for the block, return it read in.
 406  * Short-form addressing.
 407  */
 408 int                                     /* error */
 409 xfs_btree_read_bufs(
 410         struct xfs_mount        *mp,    /* file system mount point */
 411         struct xfs_trans        *tp,    /* transaction pointer */
 412         xfs_agnumber_t          agno,   /* allocation group number */
 413         xfs_agblock_t           agbno,  /* allocation group block number */
 414         uint                    lock,   /* lock flags for read_buf */
 415         struct xfs_buf          **bpp,  /* buffer for agno/agbno */
 416         int                     refval);/* ref count value for buffer */
 417
 418 /*
 419  * Read-ahead the block, don't wait for it, don't return a buffer.
 420  * Long-form addressing.
 421  */
 422 void                                    /* error */
 423 xfs_btree_reada_bufl(
 424         struct xfs_mount        *mp,    /* file system mount point */
 425         xfs_fsblock_t           fsbno,  /* file system block number */
 426         xfs_extlen_t            count); /* count of filesystem blocks */
 427
 428 /*
 429  * Read-ahead the block, don't wait for it, don't return a buffer.
 430  * Short-form addressing.
 431  */
 432 void                                    /* error */
 433 xfs_btree_reada_bufs(
 434         struct xfs_mount        *mp,    /* file system mount point */
 435         xfs_agnumber_t          agno,   /* allocation group number */
 436         xfs_agblock_t           agbno,  /* allocation group block number */
 437         xfs_extlen_t            count); /* count of filesystem blocks */
 438
 439 /*
 440  * Set the buffer for level "lev" in the cursor to bp, releasing
 441  * any previous buffer.
 442  */
 443 void
 444 xfs_btree_setbuf(
 445         xfs_btree_cur_t         *cur,   /* btree cursor */
 446         int                     lev,    /* level in btree */
 447         struct xfs_buf          *bp);   /* new buffer to set */
 448
 449
 450 /*
 451  * Common btree core entry points.
 452  */
 453 int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
 454 int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
 455 int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
 456 int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
 457 int xfs_btree_new_iroot(struct xfs_btree_cur *, int *, int *);
 458 int xfs_btree_kill_iroot(struct xfs_btree_cur *);
 459 int xfs_btree_insert(struct xfs_btree_cur *, int *);
 460 int xfs_btree_delete(struct xfs_btree_cur *, int *);
 461 int xfs_btree_get_rec(struct xfs_btree_cur *, union xfs_btree_rec **, int *);
 462
 463 /*
 464  * Internal btree helpers also used by xfs_bmap.c.
 465  */
 466 void xfs_btree_log_block(struct xfs_btree_cur *, struct xfs_buf *, int);
 467 void xfs_btree_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, int);
 468
 469 /*
 470  * Helpers.
 471  */
 472 static inline int xfs_btree_get_numrecs(struct xfs_btree_block *block)
 473 {
 474         return be16_to_cpu(block->bb_numrecs);
 475 }
 476
 477 static inline void xfs_btree_set_numrecs(struct xfs_btree_block *block,
 478                 __uint16_t numrecs)
 479 {
 480         block->bb_numrecs = cpu_to_be16(numrecs);
 481 }
 482
 483 static inline int xfs_btree_get_level(struct xfs_btree_block *block)
 484 {
 485         return be16_to_cpu(block->bb_level);
 486 }
 487
 488
 489 /*
 490  * Min and max functions for extlen, agblock, fileoff, and filblks types.
 491  */
 492 #define XFS_EXTLEN_MIN(a,b)     min_t(xfs_extlen_t, (a), (b))
 493 #define XFS_EXTLEN_MAX(a,b)     max_t(xfs_extlen_t, (a), (b))
 494 #define XFS_AGBLOCK_MIN(a,b)    min_t(xfs_agblock_t, (a), (b))
 495 #define XFS_AGBLOCK_MAX(a,b)    max_t(xfs_agblock_t, (a), (b))
 496 #define XFS_FILEOFF_MIN(a,b)    min_t(xfs_fileoff_t, (a), (b))
 497 #define XFS_FILEOFF_MAX(a,b)    max_t(xfs_fileoff_t, (a), (b))
 498 #define XFS_FILBLKS_MIN(a,b)    min_t(xfs_filblks_t, (a), (b))
 499 #define XFS_FILBLKS_MAX(a,b)    max_t(xfs_filblks_t, (a), (b))
 500
 501 #define XFS_FSB_SANITY_CHECK(mp,fsb)    \
 502         (XFS_FSB_TO_AGNO(mp, fsb) < mp->m_sb.sb_agcount && \
 503                 XFS_FSB_TO_AGBNO(mp, fsb) < mp->m_sb.sb_agblocks)
 504
 505 #endif  /* __XFS_BTREE_H__ */