xfs/libxfs/xfs_btree.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 /*
0003  * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
0004  * All Rights Reserved.
0005  */
0006 #ifndef __XFS_BTREE_H__
0007 #define __XFS_BTREE_H__
0008
0009 struct xfs_buf;
0010 struct xfs_inode;
0011 struct xfs_mount;
0012 struct xfs_trans;
0013 struct xfs_ifork;
0014 struct xfs_perag;
0015
0016 /*
0017  * Generic key, ptr and record wrapper structures.
0018  *
0019  * These are disk format structures, and are converted where necessary
0020  * by the btree specific code that needs to interpret them.
0021  */
0022 union xfs_btree_ptr {
0023     __be32          s;  /* short form ptr */
0024     __be64          l;  /* long form ptr */
0025 };
0026
0027 /*
0028  * The in-core btree key.  Overlapping btrees actually store two keys
0029  * per pointer, so we reserve enough memory to hold both.  The __*bigkey
0030  * items should never be accessed directly.
0031  */
0032 union xfs_btree_key {
0033     struct xfs_bmbt_key     bmbt;
0034     xfs_bmdr_key_t          bmbr;   /* bmbt root block */
0035     xfs_alloc_key_t         alloc;
0036     struct xfs_inobt_key        inobt;
0037     struct xfs_rmap_key     rmap;
0038     struct xfs_rmap_key     __rmap_bigkey[2];
0039     struct xfs_refcount_key     refc;
0040 };
0041
0042 union xfs_btree_rec {
0043     struct xfs_bmbt_rec     bmbt;
0044     xfs_bmdr_rec_t          bmbr;   /* bmbt root block */
0045     struct xfs_alloc_rec        alloc;
0046     struct xfs_inobt_rec        inobt;
0047     struct xfs_rmap_rec     rmap;
0048     struct xfs_refcount_rec     refc;
0049 };
0050
0051 /*
0052  * This nonsense is to make -wlint happy.
0053  */
0054 #define XFS_LOOKUP_EQ   ((xfs_lookup_t)XFS_LOOKUP_EQi)
0055 #define XFS_LOOKUP_LE   ((xfs_lookup_t)XFS_LOOKUP_LEi)
0056 #define XFS_LOOKUP_GE   ((xfs_lookup_t)XFS_LOOKUP_GEi)
0057
0058 #define XFS_BTNUM_BNO   ((xfs_btnum_t)XFS_BTNUM_BNOi)
0059 #define XFS_BTNUM_CNT   ((xfs_btnum_t)XFS_BTNUM_CNTi)
0060 #define XFS_BTNUM_BMAP  ((xfs_btnum_t)XFS_BTNUM_BMAPi)
0061 #define XFS_BTNUM_INO   ((xfs_btnum_t)XFS_BTNUM_INOi)
0062 #define XFS_BTNUM_FINO  ((xfs_btnum_t)XFS_BTNUM_FINOi)
0063 #define XFS_BTNUM_RMAP  ((xfs_btnum_t)XFS_BTNUM_RMAPi)
0064 #define XFS_BTNUM_REFC  ((xfs_btnum_t)XFS_BTNUM_REFCi)
0065
0066 uint32_t xfs_btree_magic(int crc, xfs_btnum_t btnum);
0067
0068 /*
0069  * For logging record fields.
0070  */
0071 #define XFS_BB_MAGIC        (1u << 0)
0072 #define XFS_BB_LEVEL        (1u << 1)
0073 #define XFS_BB_NUMRECS      (1u << 2)
0074 #define XFS_BB_LEFTSIB      (1u << 3)
0075 #define XFS_BB_RIGHTSIB     (1u << 4)
0076 #define XFS_BB_BLKNO        (1u << 5)
0077 #define XFS_BB_LSN      (1u << 6)
0078 #define XFS_BB_UUID     (1u << 7)
0079 #define XFS_BB_OWNER        (1u << 8)
0080 #define XFS_BB_NUM_BITS     5
0081 #define XFS_BB_ALL_BITS     ((1u << XFS_BB_NUM_BITS) - 1)
0082 #define XFS_BB_NUM_BITS_CRC 9
0083 #define XFS_BB_ALL_BITS_CRC ((1u << XFS_BB_NUM_BITS_CRC) - 1)
0084
0085 /*
0086  * Generic stats interface
0087  */
0088 #define XFS_BTREE_STATS_INC(cur, stat)  \
0089     XFS_STATS_INC_OFF((cur)->bc_mp, (cur)->bc_statoff + __XBTS_ ## stat)
0090 #define XFS_BTREE_STATS_ADD(cur, stat, val) \
0091     XFS_STATS_ADD_OFF((cur)->bc_mp, (cur)->bc_statoff + __XBTS_ ## stat, val)
0092
0093 struct xfs_btree_ops {
0094     /* size of the key and record structures */
0095     size_t  key_len;
0096     size_t  rec_len;
0097
0098     /* cursor operations */
0099     struct xfs_btree_cur *(*dup_cursor)(struct xfs_btree_cur *);
0100     void    (*update_cursor)(struct xfs_btree_cur *src,
0101                  struct xfs_btree_cur *dst);
0102
0103     /* update btree root pointer */
0104     void    (*set_root)(struct xfs_btree_cur *cur,
0105                 const union xfs_btree_ptr *nptr, int level_change);
0106
0107     /* block allocation / freeing */
0108     int (*alloc_block)(struct xfs_btree_cur *cur,
0109                    const union xfs_btree_ptr *start_bno,
0110                    union xfs_btree_ptr *new_bno,
0111                    int *stat);
0112     int (*free_block)(struct xfs_btree_cur *cur, struct xfs_buf *bp);
0113
0114     /* update last record information */
0115     void    (*update_lastrec)(struct xfs_btree_cur *cur,
0116                   const struct xfs_btree_block *block,
0117                   const union xfs_btree_rec *rec,
0118                   int ptr, int reason);
0119
0120     /* records in block/level */
0121     int (*get_minrecs)(struct xfs_btree_cur *cur, int level);
0122     int (*get_maxrecs)(struct xfs_btree_cur *cur, int level);
0123
0124     /* records on disk.  Matter for the root in inode case. */
0125     int (*get_dmaxrecs)(struct xfs_btree_cur *cur, int level);
0126
0127     /* init values of btree structures */
0128     void    (*init_key_from_rec)(union xfs_btree_key *key,
0129                      const union xfs_btree_rec *rec);
0130     void    (*init_rec_from_cur)(struct xfs_btree_cur *cur,
0131                      union xfs_btree_rec *rec);
0132     void    (*init_ptr_from_cur)(struct xfs_btree_cur *cur,
0133                      union xfs_btree_ptr *ptr);
0134     void    (*init_high_key_from_rec)(union xfs_btree_key *key,
0135                       const union xfs_btree_rec *rec);
0136
0137     /* difference between key value and cursor value */
0138     int64_t (*key_diff)(struct xfs_btree_cur *cur,
0139                 const union xfs_btree_key *key);
0140
0141     /*
0142      * Difference between key2 and key1 -- positive if key1 > key2,
0143      * negative if key1 < key2, and zero if equal.
0144      */
0145     int64_t (*diff_two_keys)(struct xfs_btree_cur *cur,
0146                  const union xfs_btree_key *key1,
0147                  const union xfs_btree_key *key2);
0148
0149     const struct xfs_buf_ops    *buf_ops;
0150
0151     /* check that k1 is lower than k2 */
0152     int (*keys_inorder)(struct xfs_btree_cur *cur,
0153                 const union xfs_btree_key *k1,
0154                 const union xfs_btree_key *k2);
0155
0156     /* check that r1 is lower than r2 */
0157     int (*recs_inorder)(struct xfs_btree_cur *cur,
0158                 const union xfs_btree_rec *r1,
0159                 const union xfs_btree_rec *r2);
0160 };
0161
0162 /*
0163  * Reasons for the update_lastrec method to be called.
0164  */
0165 #define LASTREC_UPDATE  0
0166 #define LASTREC_INSREC  1
0167 #define LASTREC_DELREC  2
0168
0169
0170 union xfs_btree_irec {
0171     struct xfs_alloc_rec_incore a;
0172     struct xfs_bmbt_irec        b;
0173     struct xfs_inobt_rec_incore i;
0174     struct xfs_rmap_irec        r;
0175     struct xfs_refcount_irec    rc;
0176 };
0177
0178 /* Per-AG btree information. */
0179 struct xfs_btree_cur_ag {
0180     struct xfs_perag        *pag;
0181     union {
0182         struct xfs_buf      *agbp;
0183         struct xbtree_afakeroot *afake; /* for staging cursor */
0184     };
0185     union {
0186         struct {
0187             unsigned int    nr_ops; /* # record updates */
0188             unsigned int    shape_changes;  /* # of extent splits */
0189         } refc;
0190         struct {
0191             bool        active; /* allocation cursor state */
0192         } abt;
0193     };
0194 };
0195
0196 /* Btree-in-inode cursor information */
0197 struct xfs_btree_cur_ino {
0198     struct xfs_inode        *ip;
0199     struct xbtree_ifakeroot     *ifake; /* for staging cursor */
0200     int             allocated;
0201     short               forksize;
0202     char                whichfork;
0203     char                flags;
0204 /* We are converting a delalloc reservation */
0205 #define XFS_BTCUR_BMBT_WASDEL       (1 << 0)
0206
0207 /* For extent swap, ignore owner check in verifier */
0208 #define XFS_BTCUR_BMBT_INVALID_OWNER    (1 << 1)
0209 };
0210
0211 struct xfs_btree_level {
0212     /* buffer pointer */
0213     struct xfs_buf      *bp;
0214
0215     /* key/record number */
0216     uint16_t        ptr;
0217
0218     /* readahead info */
0219 #define XFS_BTCUR_LEFTRA    (1 << 0) /* left sibling has been read-ahead */
0220 #define XFS_BTCUR_RIGHTRA   (1 << 1) /* right sibling has been read-ahead */
0221     uint16_t        ra;
0222 };
0223
0224 /*
0225  * Btree cursor structure.
0226  * This collects all information needed by the btree code in one place.
0227  */
0228 struct xfs_btree_cur
0229 {
0230     struct xfs_trans    *bc_tp; /* transaction we're in, if any */
0231     struct xfs_mount    *bc_mp; /* file system mount struct */
0232     const struct xfs_btree_ops *bc_ops;
0233     struct kmem_cache   *bc_cache; /* cursor cache */
0234     unsigned int        bc_flags; /* btree features - below */
0235     xfs_btnum_t     bc_btnum; /* identifies which btree type */
0236     union xfs_btree_irec    bc_rec; /* current insert/search record value */
0237     uint8_t         bc_nlevels; /* number of levels in the tree */
0238     uint8_t         bc_maxlevels; /* maximum levels for this btree type */
0239     int         bc_statoff; /* offset of btree stats array */
0240
0241     /*
0242      * Short btree pointers need an agno to be able to turn the pointers
0243      * into physical addresses for IO, so the btree cursor switches between
0244      * bc_ino and bc_ag based on whether XFS_BTREE_LONG_PTRS is set for the
0245      * cursor.
0246      */
0247     union {
0248         struct xfs_btree_cur_ag bc_ag;
0249         struct xfs_btree_cur_ino bc_ino;
0250     };
0251
0252     /* Must be at the end of the struct! */
0253     struct xfs_btree_level  bc_levels[];
0254 };
0255
0256 /*
0257  * Compute the size of a btree cursor that can handle a btree of a given
0258  * height.  The bc_levels array handles node and leaf blocks, so its size
0259  * is exactly nlevels.
0260  */
0261 static inline size_t
0262 xfs_btree_cur_sizeof(unsigned int nlevels)
0263 {
0264     return struct_size((struct xfs_btree_cur *)NULL, bc_levels, nlevels);
0265 }
0266
0267 /* cursor flags */
0268 #define XFS_BTREE_LONG_PTRS     (1<<0)  /* pointers are 64bits long */
0269 #define XFS_BTREE_ROOT_IN_INODE     (1<<1)  /* root may be variable size */
0270 #define XFS_BTREE_LASTREC_UPDATE    (1<<2)  /* track last rec externally */
0271 #define XFS_BTREE_CRC_BLOCKS        (1<<3)  /* uses extended btree blocks */
0272 #define XFS_BTREE_OVERLAPPING       (1<<4)  /* overlapping intervals */
0273 /*
0274  * The root of this btree is a fakeroot structure so that we can stage a btree
0275  * rebuild without leaving it accessible via primary metadata.  The ops struct
0276  * is dynamically allocated and must be freed when the cursor is deleted.
0277  */
0278 #define XFS_BTREE_STAGING       (1<<5)
0279
0280 #define XFS_BTREE_NOERROR   0
0281 #define XFS_BTREE_ERROR     1
0282
0283 /*
0284  * Convert from buffer to btree block header.
0285  */
0286 #define XFS_BUF_TO_BLOCK(bp)    ((struct xfs_btree_block *)((bp)->b_addr))
0287
0288 /*
0289  * Internal long and short btree block checks.  They return NULL if the
0290  * block is ok or the address of the failed check otherwise.
0291  */
0292 xfs_failaddr_t __xfs_btree_check_lblock(struct xfs_btree_cur *cur,
0293         struct xfs_btree_block *block, int level, struct xfs_buf *bp);
0294 xfs_failaddr_t __xfs_btree_check_sblock(struct xfs_btree_cur *cur,
0295         struct xfs_btree_block *block, int level, struct xfs_buf *bp);
0296
0297 /*
0298  * Check that block header is ok.
0299  */
0300 int
0301 xfs_btree_check_block(
0302     struct xfs_btree_cur    *cur,   /* btree cursor */
0303     struct xfs_btree_block  *block, /* generic btree block pointer */
0304     int         level,  /* level of the btree block */
0305     struct xfs_buf      *bp);   /* buffer containing block, if any */
0306
0307 /*
0308  * Check that (long) pointer is ok.
0309  */
0310 bool                    /* error (0 or EFSCORRUPTED) */
0311 xfs_btree_check_lptr(
0312     struct xfs_btree_cur    *cur,   /* btree cursor */
0313     xfs_fsblock_t       fsbno,  /* btree block disk address */
0314     int         level); /* btree block level */
0315
0316 /*
0317  * Check that (short) pointer is ok.
0318  */
0319 bool                    /* error (0 or EFSCORRUPTED) */
0320 xfs_btree_check_sptr(
0321     struct xfs_btree_cur    *cur,   /* btree cursor */
0322     xfs_agblock_t       agbno,  /* btree block disk address */
0323     int         level); /* btree block level */
0324
0325 /*
0326  * Delete the btree cursor.
0327  */
0328 void
0329 xfs_btree_del_cursor(
0330     struct xfs_btree_cur    *cur,   /* btree cursor */
0331     int         error); /* del because of error */
0332
0333 /*
0334  * Duplicate the btree cursor.
0335  * Allocate a new one, copy the record, re-get the buffers.
0336  */
0337 int                 /* error */
0338 xfs_btree_dup_cursor(
0339     struct xfs_btree_cur        *cur,   /* input cursor */
0340     struct xfs_btree_cur        **ncur);/* output cursor */
0341
0342 /*
0343  * Compute first and last byte offsets for the fields given.
0344  * Interprets the offsets table, which contains struct field offsets.
0345  */
0346 void
0347 xfs_btree_offsets(
0348     uint32_t        fields, /* bitmask of fields */
0349     const short     *offsets,/* table of field offsets */
0350     int         nbits,  /* number of bits to inspect */
0351     int         *first, /* output: first byte offset */
0352     int         *last); /* output: last byte offset */
0353
0354 /*
0355  * Get a buffer for the block, return it read in.
0356  * Long-form addressing.
0357  */
0358 int                 /* error */
0359 xfs_btree_read_bufl(
0360     struct xfs_mount    *mp,    /* file system mount point */
0361     struct xfs_trans    *tp,    /* transaction pointer */
0362     xfs_fsblock_t       fsbno,  /* file system block number */
0363     struct xfs_buf      **bpp,  /* buffer for fsbno */
0364     int         refval, /* ref count value for buffer */
0365     const struct xfs_buf_ops *ops);
0366
0367 /*
0368  * Read-ahead the block, don't wait for it, don't return a buffer.
0369  * Long-form addressing.
0370  */
0371 void                    /* error */
0372 xfs_btree_reada_bufl(
0373     struct xfs_mount    *mp,    /* file system mount point */
0374     xfs_fsblock_t       fsbno,  /* file system block number */
0375     xfs_extlen_t        count,  /* count of filesystem blocks */
0376     const struct xfs_buf_ops *ops);
0377
0378 /*
0379  * Read-ahead the block, don't wait for it, don't return a buffer.
0380  * Short-form addressing.
0381  */
0382 void                    /* error */
0383 xfs_btree_reada_bufs(
0384     struct xfs_mount    *mp,    /* file system mount point */
0385     xfs_agnumber_t      agno,   /* allocation group number */
0386     xfs_agblock_t       agbno,  /* allocation group block number */
0387     xfs_extlen_t        count,  /* count of filesystem blocks */
0388     const struct xfs_buf_ops *ops);
0389
0390 /*
0391  * Initialise a new btree block header
0392  */
0393 void
0394 xfs_btree_init_block(
0395     struct xfs_mount *mp,
0396     struct xfs_buf  *bp,
0397     xfs_btnum_t btnum,
0398     __u16       level,
0399     __u16       numrecs,
0400     __u64       owner);
0401
0402 void
0403 xfs_btree_init_block_int(
0404     struct xfs_mount    *mp,
0405     struct xfs_btree_block  *buf,
0406     xfs_daddr_t     blkno,
0407     xfs_btnum_t     btnum,
0408     __u16           level,
0409     __u16           numrecs,
0410     __u64           owner,
0411     unsigned int        flags);
0412
0413 /*
0414  * Common btree core entry points.
0415  */
0416 int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
0417 int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
0418 int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
0419 int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
0420 int xfs_btree_new_iroot(struct xfs_btree_cur *, int *, int *);
0421 int xfs_btree_insert(struct xfs_btree_cur *, int *);
0422 int xfs_btree_delete(struct xfs_btree_cur *, int *);
0423 int xfs_btree_get_rec(struct xfs_btree_cur *, union xfs_btree_rec **, int *);
0424 int xfs_btree_change_owner(struct xfs_btree_cur *cur, uint64_t new_owner,
0425                struct list_head *buffer_list);
0426
0427 /*
0428  * btree block CRC helpers
0429  */
0430 void xfs_btree_lblock_calc_crc(struct xfs_buf *);
0431 bool xfs_btree_lblock_verify_crc(struct xfs_buf *);
0432 void xfs_btree_sblock_calc_crc(struct xfs_buf *);
0433 bool xfs_btree_sblock_verify_crc(struct xfs_buf *);
0434
0435 /*
0436  * Internal btree helpers also used by xfs_bmap.c.
0437  */
0438 void xfs_btree_log_block(struct xfs_btree_cur *, struct xfs_buf *, uint32_t);
0439 void xfs_btree_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, int);
0440
0441 /*
0442  * Helpers.
0443  */
0444 static inline int xfs_btree_get_numrecs(const struct xfs_btree_block *block)
0445 {
0446     return be16_to_cpu(block->bb_numrecs);
0447 }
0448
0449 static inline void xfs_btree_set_numrecs(struct xfs_btree_block *block,
0450         uint16_t numrecs)
0451 {
0452     block->bb_numrecs = cpu_to_be16(numrecs);
0453 }
0454
0455 static inline int xfs_btree_get_level(const struct xfs_btree_block *block)
0456 {
0457     return be16_to_cpu(block->bb_level);
0458 }
0459
0460
0461 /*
0462  * Min and max functions for extlen, agblock, fileoff, and filblks types.
0463  */
0464 #define XFS_EXTLEN_MIN(a,b) min_t(xfs_extlen_t, (a), (b))
0465 #define XFS_EXTLEN_MAX(a,b) max_t(xfs_extlen_t, (a), (b))
0466 #define XFS_AGBLOCK_MIN(a,b)    min_t(xfs_agblock_t, (a), (b))
0467 #define XFS_AGBLOCK_MAX(a,b)    max_t(xfs_agblock_t, (a), (b))
0468 #define XFS_FILEOFF_MIN(a,b)    min_t(xfs_fileoff_t, (a), (b))
0469 #define XFS_FILEOFF_MAX(a,b)    max_t(xfs_fileoff_t, (a), (b))
0470 #define XFS_FILBLKS_MIN(a,b)    min_t(xfs_filblks_t, (a), (b))
0471 #define XFS_FILBLKS_MAX(a,b)    max_t(xfs_filblks_t, (a), (b))
0472
0473 xfs_failaddr_t xfs_btree_sblock_v5hdr_verify(struct xfs_buf *bp);
0474 xfs_failaddr_t xfs_btree_sblock_verify(struct xfs_buf *bp,
0475         unsigned int max_recs);
0476 xfs_failaddr_t xfs_btree_lblock_v5hdr_verify(struct xfs_buf *bp,
0477         uint64_t owner);
0478 xfs_failaddr_t xfs_btree_lblock_verify(struct xfs_buf *bp,
0479         unsigned int max_recs);
0480
0481 unsigned int xfs_btree_compute_maxlevels(const unsigned int *limits,
0482         unsigned long long records);
0483 unsigned long long xfs_btree_calc_size(const unsigned int *limits,
0484         unsigned long long records);
0485 unsigned int xfs_btree_space_to_height(const unsigned int *limits,
0486         unsigned long long blocks);
0487
0488 /*
0489  * Return codes for the query range iterator function are 0 to continue
0490  * iterating, and non-zero to stop iterating.  Any non-zero value will be
0491  * passed up to the _query_range caller.  The special value -ECANCELED can be
0492  * used to stop iteration, because _query_range never generates that error
0493  * code on its own.
0494  */
0495 typedef int (*xfs_btree_query_range_fn)(struct xfs_btree_cur *cur,
0496         const union xfs_btree_rec *rec, void *priv);
0497
0498 int xfs_btree_query_range(struct xfs_btree_cur *cur,
0499         const union xfs_btree_irec *low_rec,
0500         const union xfs_btree_irec *high_rec,
0501         xfs_btree_query_range_fn fn, void *priv);
0502 int xfs_btree_query_all(struct xfs_btree_cur *cur, xfs_btree_query_range_fn fn,
0503         void *priv);
0504
0505 typedef int (*xfs_btree_visit_blocks_fn)(struct xfs_btree_cur *cur, int level,
0506         void *data);
0507 /* Visit record blocks. */
0508 #define XFS_BTREE_VISIT_RECORDS     (1 << 0)
0509 /* Visit leaf blocks. */
0510 #define XFS_BTREE_VISIT_LEAVES      (1 << 1)
0511 /* Visit all blocks. */
0512 #define XFS_BTREE_VISIT_ALL     (XFS_BTREE_VISIT_RECORDS | \
0513                      XFS_BTREE_VISIT_LEAVES)
0514 int xfs_btree_visit_blocks(struct xfs_btree_cur *cur,
0515         xfs_btree_visit_blocks_fn fn, unsigned int flags, void *data);
0516
0517 int xfs_btree_count_blocks(struct xfs_btree_cur *cur, xfs_extlen_t *blocks);
0518
0519 union xfs_btree_rec *xfs_btree_rec_addr(struct xfs_btree_cur *cur, int n,
0520         struct xfs_btree_block *block);
0521 union xfs_btree_key *xfs_btree_key_addr(struct xfs_btree_cur *cur, int n,
0522         struct xfs_btree_block *block);
0523 union xfs_btree_key *xfs_btree_high_key_addr(struct xfs_btree_cur *cur, int n,
0524         struct xfs_btree_block *block);
0525 union xfs_btree_ptr *xfs_btree_ptr_addr(struct xfs_btree_cur *cur, int n,
0526         struct xfs_btree_block *block);
0527 int xfs_btree_lookup_get_block(struct xfs_btree_cur *cur, int level,
0528         const union xfs_btree_ptr *pp, struct xfs_btree_block **blkp);
0529 struct xfs_btree_block *xfs_btree_get_block(struct xfs_btree_cur *cur,
0530         int level, struct xfs_buf **bpp);
0531 bool xfs_btree_ptr_is_null(struct xfs_btree_cur *cur,
0532         const union xfs_btree_ptr *ptr);
0533 int64_t xfs_btree_diff_two_ptrs(struct xfs_btree_cur *cur,
0534                 const union xfs_btree_ptr *a,
0535                 const union xfs_btree_ptr *b);
0536 void xfs_btree_get_sibling(struct xfs_btree_cur *cur,
0537                struct xfs_btree_block *block,
0538                union xfs_btree_ptr *ptr, int lr);
0539 void xfs_btree_get_keys(struct xfs_btree_cur *cur,
0540         struct xfs_btree_block *block, union xfs_btree_key *key);
0541 union xfs_btree_key *xfs_btree_high_key_from_key(struct xfs_btree_cur *cur,
0542         union xfs_btree_key *key);
0543 int xfs_btree_has_record(struct xfs_btree_cur *cur,
0544         const union xfs_btree_irec *low,
0545         const union xfs_btree_irec *high, bool *exists);
0546 bool xfs_btree_has_more_records(struct xfs_btree_cur *cur);
0547 struct xfs_ifork *xfs_btree_ifork_ptr(struct xfs_btree_cur *cur);
0548
0549 /* Does this cursor point to the last block in the given level? */
0550 static inline bool
0551 xfs_btree_islastblock(
0552     struct xfs_btree_cur    *cur,
0553     int         level)
0554 {
0555     struct xfs_btree_block  *block;
0556     struct xfs_buf      *bp;
0557
0558     block = xfs_btree_get_block(cur, level, &bp);
0559     ASSERT(block && xfs_btree_check_block(cur, block, level, bp) == 0);
0560
0561     if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
0562         return block->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK);
0563     return block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK);
0564 }
0565
0566 void xfs_btree_set_ptr_null(struct xfs_btree_cur *cur,
0567         union xfs_btree_ptr *ptr);
0568 int xfs_btree_get_buf_block(struct xfs_btree_cur *cur,
0569         const union xfs_btree_ptr *ptr, struct xfs_btree_block **block,
0570         struct xfs_buf **bpp);
0571 void xfs_btree_set_sibling(struct xfs_btree_cur *cur,
0572         struct xfs_btree_block *block, const union xfs_btree_ptr *ptr,
0573         int lr);
0574 void xfs_btree_init_block_cur(struct xfs_btree_cur *cur,
0575         struct xfs_buf *bp, int level, int numrecs);
0576 void xfs_btree_copy_ptrs(struct xfs_btree_cur *cur,
0577         union xfs_btree_ptr *dst_ptr,
0578         const union xfs_btree_ptr *src_ptr, int numptrs);
0579 void xfs_btree_copy_keys(struct xfs_btree_cur *cur,
0580         union xfs_btree_key *dst_key,
0581         const union xfs_btree_key *src_key, int numkeys);
0582
0583 static inline struct xfs_btree_cur *
0584 xfs_btree_alloc_cursor(
0585     struct xfs_mount    *mp,
0586     struct xfs_trans    *tp,
0587     xfs_btnum_t     btnum,
0588     uint8_t         maxlevels,
0589     struct kmem_cache   *cache)
0590 {
0591     struct xfs_btree_cur    *cur;
0592
0593     cur = kmem_cache_zalloc(cache, GFP_NOFS | __GFP_NOFAIL);
0594     cur->bc_tp = tp;
0595     cur->bc_mp = mp;
0596     cur->bc_btnum = btnum;
0597     cur->bc_maxlevels = maxlevels;
0598     cur->bc_cache = cache;
0599
0600     return cur;
0601 }
0602
0603 int __init xfs_btree_init_cur_caches(void);
0604 void xfs_btree_destroy_cur_caches(void);
0605
0606 #endif  /* __XFS_BTREE_H__ */