fs/xfs/libxfs/xfs_btree.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 /*
   3  * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
   4  * All Rights Reserved.
   5  */
   6 #ifndef __XFS_BTREE_H__
   7 #define __XFS_BTREE_H__
   8
   9 struct xfs_buf;
  10 struct xfs_inode;
  11 struct xfs_mount;
  12 struct xfs_trans;
  13 struct xfs_ifork;
  14 struct xfs_perag;
  15
  16 extern kmem_zone_t      *xfs_btree_cur_zone;
  17
  18 /*
  19  * Generic key, ptr and record wrapper structures.
  20  *
  21  * These are disk format structures, and are converted where necessary
  22  * by the btree specific code that needs to interpret them.
  23  */
  24 union xfs_btree_ptr {
  25         __be32                  s;      /* short form ptr */
  26         __be64                  l;      /* long form ptr */
  27 };
  28
  29 /*
  30  * The in-core btree key.  Overlapping btrees actually store two keys
  31  * per pointer, so we reserve enough memory to hold both.  The __*bigkey
  32  * items should never be accessed directly.
  33  */
  34 union xfs_btree_key {
  35         struct xfs_bmbt_key             bmbt;
  36         xfs_bmdr_key_t                  bmbr;   /* bmbt root block */
  37         xfs_alloc_key_t                 alloc;
  38         struct xfs_inobt_key            inobt;
  39         struct xfs_rmap_key             rmap;
  40         struct xfs_rmap_key             __rmap_bigkey[2];
  41         struct xfs_refcount_key         refc;
  42 };
  43
  44 union xfs_btree_rec {
  45         struct xfs_bmbt_rec             bmbt;
  46         xfs_bmdr_rec_t                  bmbr;   /* bmbt root block */
  47         struct xfs_alloc_rec            alloc;
  48         struct xfs_inobt_rec            inobt;
  49         struct xfs_rmap_rec             rmap;
  50         struct xfs_refcount_rec         refc;
  51 };
  52
  53 /*
  54  * This nonsense is to make -wlint happy.
  55  */
  56 #define XFS_LOOKUP_EQ   ((xfs_lookup_t)XFS_LOOKUP_EQi)
  57 #define XFS_LOOKUP_LE   ((xfs_lookup_t)XFS_LOOKUP_LEi)
  58 #define XFS_LOOKUP_GE   ((xfs_lookup_t)XFS_LOOKUP_GEi)
  59
  60 #define XFS_BTNUM_BNO   ((xfs_btnum_t)XFS_BTNUM_BNOi)
  61 #define XFS_BTNUM_CNT   ((xfs_btnum_t)XFS_BTNUM_CNTi)
  62 #define XFS_BTNUM_BMAP  ((xfs_btnum_t)XFS_BTNUM_BMAPi)
  63 #define XFS_BTNUM_INO   ((xfs_btnum_t)XFS_BTNUM_INOi)
  64 #define XFS_BTNUM_FINO  ((xfs_btnum_t)XFS_BTNUM_FINOi)
  65 #define XFS_BTNUM_RMAP  ((xfs_btnum_t)XFS_BTNUM_RMAPi)
  66 #define XFS_BTNUM_REFC  ((xfs_btnum_t)XFS_BTNUM_REFCi)
  67
  68 uint32_t xfs_btree_magic(int crc, xfs_btnum_t btnum);
  69
  70 /*
  71  * For logging record fields.
  72  */
  73 #define XFS_BB_MAGIC            (1 << 0)
  74 #define XFS_BB_LEVEL            (1 << 1)
  75 #define XFS_BB_NUMRECS          (1 << 2)
  76 #define XFS_BB_LEFTSIB          (1 << 3)
  77 #define XFS_BB_RIGHTSIB         (1 << 4)
  78 #define XFS_BB_BLKNO            (1 << 5)
  79 #define XFS_BB_LSN              (1 << 6)
  80 #define XFS_BB_UUID             (1 << 7)
  81 #define XFS_BB_OWNER            (1 << 8)
  82 #define XFS_BB_NUM_BITS         5
  83 #define XFS_BB_ALL_BITS         ((1 << XFS_BB_NUM_BITS) - 1)
  84 #define XFS_BB_NUM_BITS_CRC     9
  85 #define XFS_BB_ALL_BITS_CRC     ((1 << XFS_BB_NUM_BITS_CRC) - 1)
  86
  87 /*
  88  * Generic stats interface
  89  */
  90 #define XFS_BTREE_STATS_INC(cur, stat)  \
  91         XFS_STATS_INC_OFF((cur)->bc_mp, (cur)->bc_statoff + __XBTS_ ## stat)
  92 #define XFS_BTREE_STATS_ADD(cur, stat, val)     \
  93         XFS_STATS_ADD_OFF((cur)->bc_mp, (cur)->bc_statoff + __XBTS_ ## stat, val)
  94
  95 #define XFS_BTREE_MAXLEVELS     9       /* max of all btrees */
  96
  97 struct xfs_btree_ops {
  98         /* size of the key and record structures */
  99         size_t  key_len;
 100         size_t  rec_len;
 101
 102         /* cursor operations */
 103         struct xfs_btree_cur *(*dup_cursor)(struct xfs_btree_cur *);
 104         void    (*update_cursor)(struct xfs_btree_cur *src,
 105                                  struct xfs_btree_cur *dst);
 106
 107         /* update btree root pointer */
 108         void    (*set_root)(struct xfs_btree_cur *cur,
 109                             union xfs_btree_ptr *nptr, int level_change);
 110
 111         /* block allocation / freeing */
 112         int     (*alloc_block)(struct xfs_btree_cur *cur,
 113                                union xfs_btree_ptr *start_bno,
 114                                union xfs_btree_ptr *new_bno,
 115                                int *stat);
 116         int     (*free_block)(struct xfs_btree_cur *cur, struct xfs_buf *bp);
 117
 118         /* update last record information */
 119         void    (*update_lastrec)(struct xfs_btree_cur *cur,
 120                                   struct xfs_btree_block *block,
 121                                   union xfs_btree_rec *rec,
 122                                   int ptr, int reason);
 123
 124         /* records in block/level */
 125         int     (*get_minrecs)(struct xfs_btree_cur *cur, int level);
 126         int     (*get_maxrecs)(struct xfs_btree_cur *cur, int level);
 127
 128         /* records on disk.  Matter for the root in inode case. */
 129         int     (*get_dmaxrecs)(struct xfs_btree_cur *cur, int level);
 130
 131         /* init values of btree structures */
 132         void    (*init_key_from_rec)(union xfs_btree_key *key,
 133                                      union xfs_btree_rec *rec);
 134         void    (*init_rec_from_cur)(struct xfs_btree_cur *cur,
 135                                      union xfs_btree_rec *rec);
 136         void    (*init_ptr_from_cur)(struct xfs_btree_cur *cur,
 137                                      union xfs_btree_ptr *ptr);
 138         void    (*init_high_key_from_rec)(union xfs_btree_key *key,
 139                                           union xfs_btree_rec *rec);
 140
 141         /* difference between key value and cursor value */
 142         int64_t (*key_diff)(struct xfs_btree_cur *cur,
 143                               union xfs_btree_key *key);
 144
 145         /*
 146          * Difference between key2 and key1 -- positive if key1 > key2,
 147          * negative if key1 < key2, and zero if equal.
 148          */
 149         int64_t (*diff_two_keys)(struct xfs_btree_cur *cur,
 150                                    union xfs_btree_key *key1,
 151                                    union xfs_btree_key *key2);
 152
 153         const struct xfs_buf_ops        *buf_ops;
 154
 155         /* check that k1 is lower than k2 */
 156         int     (*keys_inorder)(struct xfs_btree_cur *cur,
 157                                 union xfs_btree_key *k1,
 158                                 union xfs_btree_key *k2);
 159
 160         /* check that r1 is lower than r2 */
 161         int     (*recs_inorder)(struct xfs_btree_cur *cur,
 162                                 union xfs_btree_rec *r1,
 163                                 union xfs_btree_rec *r2);
 164 };
 165
 166 /*
 167  * Reasons for the update_lastrec method to be called.
 168  */
 169 #define LASTREC_UPDATE  0
 170 #define LASTREC_INSREC  1
 171 #define LASTREC_DELREC  2
 172
 173
 174 union xfs_btree_irec {
 175         struct xfs_alloc_rec_incore     a;
 176         struct xfs_bmbt_irec            b;
 177         struct xfs_inobt_rec_incore     i;
 178         struct xfs_rmap_irec            r;
 179         struct xfs_refcount_irec        rc;
 180 };
 181
 182 /* Per-AG btree information. */
 183 struct xfs_btree_cur_ag {
 184         struct xfs_perag        *pag;
 185         union {
 186                 struct xfs_buf          *agbp;
 187                 struct xbtree_afakeroot *afake; /* for staging cursor */
 188         };
 189         union {
 190                 struct {
 191                         unsigned long nr_ops;   /* # record updates */
 192                         int     shape_changes;  /* # of extent splits */
 193                 } refc;
 194                 struct {
 195                         bool    active;         /* allocation cursor state */
 196                 } abt;
 197         };
 198 };
 199
 200 /* Btree-in-inode cursor information */
 201 struct xfs_btree_cur_ino {
 202         struct xfs_inode                *ip;
 203         struct xbtree_ifakeroot         *ifake; /* for staging cursor */
 204         int                             allocated;
 205         short                           forksize;
 206         char                            whichfork;
 207         char                            flags;
 208 /* We are converting a delalloc reservation */
 209 #define XFS_BTCUR_BMBT_WASDEL           (1 << 0)
 210
 211 /* For extent swap, ignore owner check in verifier */
 212 #define XFS_BTCUR_BMBT_INVALID_OWNER    (1 << 1)
 213 };
 214
 215 /*
 216  * Btree cursor structure.
 217  * This collects all information needed by the btree code in one place.
 218  */
 219 typedef struct xfs_btree_cur
 220 {
 221         struct xfs_trans        *bc_tp; /* transaction we're in, if any */
 222         struct xfs_mount        *bc_mp; /* file system mount struct */
 223         const struct xfs_btree_ops *bc_ops;
 224         uint                    bc_flags; /* btree features - below */
 225         union xfs_btree_irec    bc_rec; /* current insert/search record value */
 226         struct xfs_buf  *bc_bufs[XFS_BTREE_MAXLEVELS];  /* buf ptr per level */
 227         int             bc_ptrs[XFS_BTREE_MAXLEVELS];   /* key/record # */
 228         uint8_t         bc_ra[XFS_BTREE_MAXLEVELS];     /* readahead bits */
 229 #define XFS_BTCUR_LEFTRA        1       /* left sibling has been read-ahead */
 230 #define XFS_BTCUR_RIGHTRA       2       /* right sibling has been read-ahead */
 231         uint8_t         bc_nlevels;     /* number of levels in the tree */
 232         uint8_t         bc_blocklog;    /* log2(blocksize) of btree blocks */
 233         xfs_btnum_t     bc_btnum;       /* identifies which btree type */
 234         int             bc_statoff;     /* offset of btre stats array */
 235
 236         /*
 237          * Short btree pointers need an agno to be able to turn the pointers
 238          * into physical addresses for IO, so the btree cursor switches between
 239          * bc_ino and bc_ag based on whether XFS_BTREE_LONG_PTRS is set for the
 240          * cursor.
 241          */
 242         union {
 243                 struct xfs_btree_cur_ag bc_ag;
 244                 struct xfs_btree_cur_ino bc_ino;
 245         };
 246 } xfs_btree_cur_t;
 247
 248 /* cursor flags */
 249 #define XFS_BTREE_LONG_PTRS             (1<<0)  /* pointers are 64bits long */
 250 #define XFS_BTREE_ROOT_IN_INODE         (1<<1)  /* root may be variable size */
 251 #define XFS_BTREE_LASTREC_UPDATE        (1<<2)  /* track last rec externally */
 252 #define XFS_BTREE_CRC_BLOCKS            (1<<3)  /* uses extended btree blocks */
 253 #define XFS_BTREE_OVERLAPPING           (1<<4)  /* overlapping intervals */
 254 /*
 255  * The root of this btree is a fakeroot structure so that we can stage a btree
 256  * rebuild without leaving it accessible via primary metadata.  The ops struct
 257  * is dynamically allocated and must be freed when the cursor is deleted.
 258  */
 259 #define XFS_BTREE_STAGING               (1<<5)
 260
 261
 262 #define XFS_BTREE_NOERROR       0
 263 #define XFS_BTREE_ERROR         1
 264
 265 /*
 266  * Convert from buffer to btree block header.
 267  */
 268 #define XFS_BUF_TO_BLOCK(bp)    ((struct xfs_btree_block *)((bp)->b_addr))
 269
 270 /*
 271  * Internal long and short btree block checks.  They return NULL if the
 272  * block is ok or the address of the failed check otherwise.
 273  */
 274 xfs_failaddr_t __xfs_btree_check_lblock(struct xfs_btree_cur *cur,
 275                 struct xfs_btree_block *block, int level, struct xfs_buf *bp);
 276 xfs_failaddr_t __xfs_btree_check_sblock(struct xfs_btree_cur *cur,
 277                 struct xfs_btree_block *block, int level, struct xfs_buf *bp);
 278
 279 /*
 280  * Check that block header is ok.
 281  */
 282 int
 283 xfs_btree_check_block(
 284         struct xfs_btree_cur    *cur,   /* btree cursor */
 285         struct xfs_btree_block  *block, /* generic btree block pointer */
 286         int                     level,  /* level of the btree block */
 287         struct xfs_buf          *bp);   /* buffer containing block, if any */
 288
 289 /*
 290  * Check that (long) pointer is ok.
 291  */
 292 bool                                    /* error (0 or EFSCORRUPTED) */
 293 xfs_btree_check_lptr(
 294         struct xfs_btree_cur    *cur,   /* btree cursor */
 295         xfs_fsblock_t           fsbno,  /* btree block disk address */
 296         int                     level); /* btree block level */
 297
 298 /*
 299  * Check that (short) pointer is ok.
 300  */
 301 bool                                    /* error (0 or EFSCORRUPTED) */
 302 xfs_btree_check_sptr(
 303         struct xfs_btree_cur    *cur,   /* btree cursor */
 304         xfs_agblock_t           agbno,  /* btree block disk address */
 305         int                     level); /* btree block level */
 306
 307 /*
 308  * Delete the btree cursor.
 309  */
 310 void
 311 xfs_btree_del_cursor(
 312         xfs_btree_cur_t         *cur,   /* btree cursor */
 313         int                     error); /* del because of error */
 314
 315 /*
 316  * Duplicate the btree cursor.
 317  * Allocate a new one, copy the record, re-get the buffers.
 318  */
 319 int                                     /* error */
 320 xfs_btree_dup_cursor(
 321         xfs_btree_cur_t         *cur,   /* input cursor */
 322         xfs_btree_cur_t         **ncur);/* output cursor */
 323
 324 /*
 325  * Compute first and last byte offsets for the fields given.
 326  * Interprets the offsets table, which contains struct field offsets.
 327  */
 328 void
 329 xfs_btree_offsets(
 330         int64_t                 fields, /* bitmask of fields */
 331         const short             *offsets,/* table of field offsets */
 332         int                     nbits,  /* number of bits to inspect */
 333         int                     *first, /* output: first byte offset */
 334         int                     *last); /* output: last byte offset */
 335
 336 /*
 337  * Get a buffer for the block, return it read in.
 338  * Long-form addressing.
 339  */
 340 int                                     /* error */
 341 xfs_btree_read_bufl(
 342         struct xfs_mount        *mp,    /* file system mount point */
 343         struct xfs_trans        *tp,    /* transaction pointer */
 344         xfs_fsblock_t           fsbno,  /* file system block number */
 345         struct xfs_buf          **bpp,  /* buffer for fsbno */
 346         int                     refval, /* ref count value for buffer */
 347         const struct xfs_buf_ops *ops);
 348
 349 /*
 350  * Read-ahead the block, don't wait for it, don't return a buffer.
 351  * Long-form addressing.
 352  */
 353 void                                    /* error */
 354 xfs_btree_reada_bufl(
 355         struct xfs_mount        *mp,    /* file system mount point */
 356         xfs_fsblock_t           fsbno,  /* file system block number */
 357         xfs_extlen_t            count,  /* count of filesystem blocks */
 358         const struct xfs_buf_ops *ops);
 359
 360 /*
 361  * Read-ahead the block, don't wait for it, don't return a buffer.
 362  * Short-form addressing.
 363  */
 364 void                                    /* error */
 365 xfs_btree_reada_bufs(
 366         struct xfs_mount        *mp,    /* file system mount point */
 367         xfs_agnumber_t          agno,   /* allocation group number */
 368         xfs_agblock_t           agbno,  /* allocation group block number */
 369         xfs_extlen_t            count,  /* count of filesystem blocks */
 370         const struct xfs_buf_ops *ops);
 371
 372 /*
 373  * Initialise a new btree block header
 374  */
 375 void
 376 xfs_btree_init_block(
 377         struct xfs_mount *mp,
 378         struct xfs_buf  *bp,
 379         xfs_btnum_t     btnum,
 380         __u16           level,
 381         __u16           numrecs,
 382         __u64           owner);
 383
 384 void
 385 xfs_btree_init_block_int(
 386         struct xfs_mount        *mp,
 387         struct xfs_btree_block  *buf,
 388         xfs_daddr_t             blkno,
 389         xfs_btnum_t             btnum,
 390         __u16                   level,
 391         __u16                   numrecs,
 392         __u64                   owner,
 393         unsigned int            flags);
 394
 395 /*
 396  * Common btree core entry points.
 397  */
 398 int xfs_btree_increment(struct xfs_btree_cur *, int, int *);
 399 int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
 400 int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
 401 int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
 402 int xfs_btree_new_iroot(struct xfs_btree_cur *, int *, int *);
 403 int xfs_btree_insert(struct xfs_btree_cur *, int *);
 404 int xfs_btree_delete(struct xfs_btree_cur *, int *);
 405 int xfs_btree_get_rec(struct xfs_btree_cur *, union xfs_btree_rec **, int *);
 406 int xfs_btree_change_owner(struct xfs_btree_cur *cur, uint64_t new_owner,
 407                            struct list_head *buffer_list);
 408
 409 /*
 410  * btree block CRC helpers
 411  */
 412 void xfs_btree_lblock_calc_crc(struct xfs_buf *);
 413 bool xfs_btree_lblock_verify_crc(struct xfs_buf *);
 414 void xfs_btree_sblock_calc_crc(struct xfs_buf *);
 415 bool xfs_btree_sblock_verify_crc(struct xfs_buf *);
 416
 417 /*
 418  * Internal btree helpers also used by xfs_bmap.c.
 419  */
 420 void xfs_btree_log_block(struct xfs_btree_cur *, struct xfs_buf *, int);
 421 void xfs_btree_log_recs(struct xfs_btree_cur *, struct xfs_buf *, int, int);
 422
 423 /*
 424  * Helpers.
 425  */
 426 static inline int xfs_btree_get_numrecs(struct xfs_btree_block *block)
 427 {
 428         return be16_to_cpu(block->bb_numrecs);
 429 }
 430
 431 static inline void xfs_btree_set_numrecs(struct xfs_btree_block *block,
 432                 uint16_t numrecs)
 433 {
 434         block->bb_numrecs = cpu_to_be16(numrecs);
 435 }
 436
 437 static inline int xfs_btree_get_level(struct xfs_btree_block *block)
 438 {
 439         return be16_to_cpu(block->bb_level);
 440 }
 441
 442
 443 /*
 444  * Min and max functions for extlen, agblock, fileoff, and filblks types.
 445  */
 446 #define XFS_EXTLEN_MIN(a,b)     min_t(xfs_extlen_t, (a), (b))
 447 #define XFS_EXTLEN_MAX(a,b)     max_t(xfs_extlen_t, (a), (b))
 448 #define XFS_AGBLOCK_MIN(a,b)    min_t(xfs_agblock_t, (a), (b))
 449 #define XFS_AGBLOCK_MAX(a,b)    max_t(xfs_agblock_t, (a), (b))
 450 #define XFS_FILEOFF_MIN(a,b)    min_t(xfs_fileoff_t, (a), (b))
 451 #define XFS_FILEOFF_MAX(a,b)    max_t(xfs_fileoff_t, (a), (b))
 452 #define XFS_FILBLKS_MIN(a,b)    min_t(xfs_filblks_t, (a), (b))
 453 #define XFS_FILBLKS_MAX(a,b)    max_t(xfs_filblks_t, (a), (b))
 454
 455 xfs_failaddr_t xfs_btree_sblock_v5hdr_verify(struct xfs_buf *bp);
 456 xfs_failaddr_t xfs_btree_sblock_verify(struct xfs_buf *bp,
 457                 unsigned int max_recs);
 458 xfs_failaddr_t xfs_btree_lblock_v5hdr_verify(struct xfs_buf *bp,
 459                 uint64_t owner);
 460 xfs_failaddr_t xfs_btree_lblock_verify(struct xfs_buf *bp,
 461                 unsigned int max_recs);
 462
 463 uint xfs_btree_compute_maxlevels(uint *limits, unsigned long len);
 464 unsigned long long xfs_btree_calc_size(uint *limits, unsigned long long len);
 465
 466 /*
 467  * Return codes for the query range iterator function are 0 to continue
 468  * iterating, and non-zero to stop iterating.  Any non-zero value will be
 469  * passed up to the _query_range caller.  The special value -ECANCELED can be
 470  * used to stop iteration, because _query_range never generates that error
 471  * code on its own.
 472  */
 473 typedef int (*xfs_btree_query_range_fn)(struct xfs_btree_cur *cur,
 474                 union xfs_btree_rec *rec, void *priv);
 475
 476 int xfs_btree_query_range(struct xfs_btree_cur *cur,
 477                 union xfs_btree_irec *low_rec, union xfs_btree_irec *high_rec,
 478                 xfs_btree_query_range_fn fn, void *priv);
 479 int xfs_btree_query_all(struct xfs_btree_cur *cur, xfs_btree_query_range_fn fn,
 480                 void *priv);
 481
 482 typedef int (*xfs_btree_visit_blocks_fn)(struct xfs_btree_cur *cur, int level,
 483                 void *data);
 484 /* Visit record blocks. */
 485 #define XFS_BTREE_VISIT_RECORDS         (1 << 0)
 486 /* Visit leaf blocks. */
 487 #define XFS_BTREE_VISIT_LEAVES          (1 << 1)
 488 /* Visit all blocks. */
 489 #define XFS_BTREE_VISIT_ALL             (XFS_BTREE_VISIT_RECORDS | \
 490                                          XFS_BTREE_VISIT_LEAVES)
 491 int xfs_btree_visit_blocks(struct xfs_btree_cur *cur,
 492                 xfs_btree_visit_blocks_fn fn, unsigned int flags, void *data);
 493
 494 int xfs_btree_count_blocks(struct xfs_btree_cur *cur, xfs_extlen_t *blocks);
 495
 496 union xfs_btree_rec *xfs_btree_rec_addr(struct xfs_btree_cur *cur, int n,
 497                 struct xfs_btree_block *block);
 498 union xfs_btree_key *xfs_btree_key_addr(struct xfs_btree_cur *cur, int n,
 499                 struct xfs_btree_block *block);
 500 union xfs_btree_key *xfs_btree_high_key_addr(struct xfs_btree_cur *cur, int n,
 501                 struct xfs_btree_block *block);
 502 union xfs_btree_ptr *xfs_btree_ptr_addr(struct xfs_btree_cur *cur, int n,
 503                 struct xfs_btree_block *block);
 504 int xfs_btree_lookup_get_block(struct xfs_btree_cur *cur, int level,
 505                 union xfs_btree_ptr *pp, struct xfs_btree_block **blkp);
 506 struct xfs_btree_block *xfs_btree_get_block(struct xfs_btree_cur *cur,
 507                 int level, struct xfs_buf **bpp);
 508 bool xfs_btree_ptr_is_null(struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr);
 509 int64_t xfs_btree_diff_two_ptrs(struct xfs_btree_cur *cur,
 510                                 const union xfs_btree_ptr *a,
 511                                 const union xfs_btree_ptr *b);
 512 void xfs_btree_get_sibling(struct xfs_btree_cur *cur,
 513                            struct xfs_btree_block *block,
 514                            union xfs_btree_ptr *ptr, int lr);
 515 void xfs_btree_get_keys(struct xfs_btree_cur *cur,
 516                 struct xfs_btree_block *block, union xfs_btree_key *key);
 517 union xfs_btree_key *xfs_btree_high_key_from_key(struct xfs_btree_cur *cur,
 518                 union xfs_btree_key *key);
 519 int xfs_btree_has_record(struct xfs_btree_cur *cur, union xfs_btree_irec *low,
 520                 union xfs_btree_irec *high, bool *exists);
 521 bool xfs_btree_has_more_records(struct xfs_btree_cur *cur);
 522 struct xfs_ifork *xfs_btree_ifork_ptr(struct xfs_btree_cur *cur);
 523
 524 /* Does this cursor point to the last block in the given level? */
 525 static inline bool
 526 xfs_btree_islastblock(
 527         xfs_btree_cur_t         *cur,
 528         int                     level)
 529 {
 530         struct xfs_btree_block  *block;
 531         struct xfs_buf          *bp;
 532
 533         block = xfs_btree_get_block(cur, level, &bp);
 534         ASSERT(block && xfs_btree_check_block(cur, block, level, bp) == 0);
 535
 536         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
 537                 return block->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK);
 538         return block->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK);
 539 }
 540
 541 void xfs_btree_set_ptr_null(struct xfs_btree_cur *cur,
 542                 union xfs_btree_ptr *ptr);
 543 int xfs_btree_get_buf_block(struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr,
 544                 struct xfs_btree_block **block, struct xfs_buf **bpp);
 545 void xfs_btree_set_sibling(struct xfs_btree_cur *cur,
 546                 struct xfs_btree_block *block, union xfs_btree_ptr *ptr,
 547                 int lr);
 548 void xfs_btree_init_block_cur(struct xfs_btree_cur *cur,
 549                 struct xfs_buf *bp, int level, int numrecs);
 550 void xfs_btree_copy_ptrs(struct xfs_btree_cur *cur,
 551                 union xfs_btree_ptr *dst_ptr,
 552                 const union xfs_btree_ptr *src_ptr, int numptrs);
 553 void xfs_btree_copy_keys(struct xfs_btree_cur *cur,
 554                 union xfs_btree_key *dst_key, union xfs_btree_key *src_key,
 555                 int numkeys);
 556
 557 #endif  /* __XFS_BTREE_H__ */