git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/btree_types.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 #ifndef _BCACHEFS_BTREE_TYPES_H
   3 #define _BCACHEFS_BTREE_TYPES_H
   4
   5 #include <linux/list.h>
   6 #include <linux/rhashtable.h>
   7 #include <linux/six.h>
   8
   9 #include "bkey_methods.h"
  10 #include "buckets_types.h"
  11 #include "journal_types.h"
  12
  13 struct open_bucket;
  14 struct btree_update;
  15 struct btree_trans;
  16
  17 #define MAX_BSETS               3U
  18
  19 struct btree_nr_keys {
  20
  21         /*
  22          * Amount of live metadata (i.e. size of node after a compaction) in
  23          * units of u64s
  24          */
  25         u16                     live_u64s;
  26         u16                     bset_u64s[MAX_BSETS];
  27
  28         /* live keys only: */
  29         u16                     packed_keys;
  30         u16                     unpacked_keys;
  31 };
  32
  33 struct bset_tree {
  34         /*
  35          * We construct a binary tree in an array as if the array
  36          * started at 1, so that things line up on the same cachelines
  37          * better: see comments in bset.c at cacheline_to_bkey() for
  38          * details
  39          */
  40
  41         /* size of the binary tree and prev array */
  42         u16                     size;
  43
  44         /* function of size - precalculated for to_inorder() */
  45         u16                     extra;
  46
  47         u16                     data_offset;
  48         u16                     aux_data_offset;
  49         u16                     end_offset;
  50
  51         struct bpos             max_key;
  52 };
  53
  54 struct btree_write {
  55         struct journal_entry_pin        journal;
  56 };
  57
  58 struct btree_alloc {
  59         struct open_buckets     ob;
  60         __BKEY_PADDED(k, BKEY_BTREE_PTR_VAL_U64s_MAX);
  61 };
  62
  63 struct btree_bkey_cached_common {
  64         struct six_lock         lock;
  65         u8                      level;
  66         u8                      btree_id;
  67 };
  68
  69 struct btree {
  70         struct btree_bkey_cached_common c;
  71
  72         struct rhash_head       hash;
  73         u64                     hash_val;
  74
  75         unsigned long           flags;
  76         u16                     written;
  77         u8                      nsets;
  78         u8                      nr_key_bits;
  79         u16                     version_ondisk;
  80
  81         struct bkey_format      format;
  82
  83         struct btree_node       *data;
  84         void                    *aux_data;
  85
  86         /*
  87          * Sets of sorted keys - the real btree node - plus a binary search tree
  88          *
  89          * set[0] is special; set[0]->tree, set[0]->prev and set[0]->data point
  90          * to the memory we have allocated for this btree node. Additionally,
  91          * set[0]->data points to the entire btree node as it exists on disk.
  92          */
  93         struct bset_tree        set[MAX_BSETS];
  94
  95         struct btree_nr_keys    nr;
  96         u16                     sib_u64s[2];
  97         u16                     whiteout_u64s;
  98         u8                      byte_order;
  99         u8                      unpack_fn_len;
 100
 101         /*
 102          * XXX: add a delete sequence number, so when bch2_btree_node_relock()
 103          * fails because the lock sequence number has changed - i.e. the
 104          * contents were modified - we can still relock the node if it's still
 105          * the one we want, without redoing the traversal
 106          */
 107
 108         /*
 109          * For asynchronous splits/interior node updates:
 110          * When we do a split, we allocate new child nodes and update the parent
 111          * node to point to them: we update the parent in memory immediately,
 112          * but then we must wait until the children have been written out before
 113          * the update to the parent can be written - this is a list of the
 114          * btree_updates that are blocking this node from being
 115          * written:
 116          */
 117         struct list_head        write_blocked;
 118
 119         /*
 120          * Also for asynchronous splits/interior node updates:
 121          * If a btree node isn't reachable yet, we don't want to kick off
 122          * another write - because that write also won't yet be reachable and
 123          * marking it as completed before it's reachable would be incorrect:
 124          */
 125         unsigned long           will_make_reachable;
 126
 127         struct open_buckets     ob;
 128
 129         /* lru list */
 130         struct list_head        list;
 131
 132         struct btree_write      writes[2];
 133
 134         /* Key/pointer for this btree node */
 135         __BKEY_PADDED(key, BKEY_BTREE_PTR_VAL_U64s_MAX);
 136 };
 137
 138 struct btree_cache {
 139         struct rhashtable       table;
 140         bool                    table_init_done;
 141         /*
 142          * We never free a struct btree, except on shutdown - we just put it on
 143          * the btree_cache_freed list and reuse it later. This simplifies the
 144          * code, and it doesn't cost us much memory as the memory usage is
 145          * dominated by buffers that hold the actual btree node data and those
 146          * can be freed - and the number of struct btrees allocated is
 147          * effectively bounded.
 148          *
 149          * btree_cache_freeable effectively is a small cache - we use it because
 150          * high order page allocations can be rather expensive, and it's quite
 151          * common to delete and allocate btree nodes in quick succession. It
 152          * should never grow past ~2-3 nodes in practice.
 153          */
 154         struct mutex            lock;
 155         struct list_head        live;
 156         struct list_head        freeable;
 157         struct list_head        freed;
 158
 159         /* Number of elements in live + freeable lists */
 160         unsigned                used;
 161         unsigned                reserve;
 162         atomic_t                dirty;
 163         struct shrinker         shrink;
 164
 165         /*
 166          * If we need to allocate memory for a new btree node and that
 167          * allocation fails, we can cannibalize another node in the btree cache
 168          * to satisfy the allocation - lock to guarantee only one thread does
 169          * this at a time:
 170          */
 171         struct task_struct      *alloc_lock;
 172         struct closure_waitlist alloc_wait;
 173 };
 174
 175 struct btree_node_iter {
 176         struct btree_node_iter_set {
 177                 u16     k, end;
 178         } data[MAX_BSETS];
 179 };
 180
 181 enum btree_iter_type {
 182         BTREE_ITER_KEYS,
 183         BTREE_ITER_NODES,
 184         BTREE_ITER_CACHED,
 185 };
 186
 187 #define BTREE_ITER_TYPE                 ((1 << 2) - 1)
 188
 189 /*
 190  * Iterate over all possible positions, synthesizing deleted keys for holes:
 191  */
 192 #define BTREE_ITER_SLOTS                (1 << 2)
 193 /*
 194  * Indicates that intent locks should be taken on leaf nodes, because we expect
 195  * to be doing updates:
 196  */
 197 #define BTREE_ITER_INTENT               (1 << 3)
 198 /*
 199  * Causes the btree iterator code to prefetch additional btree nodes from disk:
 200  */
 201 #define BTREE_ITER_PREFETCH             (1 << 4)
 202 /*
 203  * Indicates that this iterator should not be reused until transaction commit,
 204  * either because a pending update references it or because the update depends
 205  * on that particular key being locked (e.g. by the str_hash code, for hash
 206  * table consistency)
 207  */
 208 #define BTREE_ITER_KEEP_UNTIL_COMMIT    (1 << 5)
 209 /*
 210  * Used in bch2_btree_iter_traverse(), to indicate whether we're searching for
 211  * @pos or the first key strictly greater than @pos
 212  */
 213 #define BTREE_ITER_IS_EXTENTS           (1 << 6)
 214 #define BTREE_ITER_ERROR                (1 << 7)
 215 #define BTREE_ITER_SET_POS_AFTER_COMMIT (1 << 8)
 216 #define BTREE_ITER_CACHED_NOFILL        (1 << 9)
 217 #define BTREE_ITER_CACHED_NOCREATE      (1 << 10)
 218 #define BTREE_ITER_NOT_EXTENTS          (1 << 11)
 219
 220 enum btree_iter_uptodate {
 221         BTREE_ITER_UPTODATE             = 0,
 222         BTREE_ITER_NEED_PEEK            = 1,
 223         BTREE_ITER_NEED_RELOCK          = 2,
 224         BTREE_ITER_NEED_TRAVERSE        = 3,
 225 };
 226
 227 #define BTREE_ITER_NO_NODE_GET_LOCKS    ((struct btree *) 1)
 228 #define BTREE_ITER_NO_NODE_DROP         ((struct btree *) 2)
 229 #define BTREE_ITER_NO_NODE_LOCK_ROOT    ((struct btree *) 3)
 230 #define BTREE_ITER_NO_NODE_UP           ((struct btree *) 4)
 231 #define BTREE_ITER_NO_NODE_DOWN         ((struct btree *) 5)
 232 #define BTREE_ITER_NO_NODE_INIT         ((struct btree *) 6)
 233 #define BTREE_ITER_NO_NODE_ERROR        ((struct btree *) 7)
 234
 235 /*
 236  * @pos                 - iterator's current position
 237  * @level               - current btree depth
 238  * @locks_want          - btree level below which we start taking intent locks
 239  * @nodes_locked        - bitmask indicating which nodes in @nodes are locked
 240  * @nodes_intent_locked - bitmask indicating which locks are intent locks
 241  */
 242 struct btree_iter {
 243         struct btree_trans      *trans;
 244         struct bpos             pos;
 245         /* what we're searching for/what the iterator actually points to: */
 246         struct bpos             real_pos;
 247         struct bpos             pos_after_commit;
 248
 249         u16                     flags;
 250         u8                      idx;
 251
 252         enum btree_id           btree_id:4;
 253         enum btree_iter_uptodate uptodate:4;
 254         unsigned                level:4,
 255                                 min_depth:4,
 256                                 locks_want:4,
 257                                 nodes_locked:4,
 258                                 nodes_intent_locked:4;
 259
 260         struct btree_iter_level {
 261                 struct btree    *b;
 262                 struct btree_node_iter iter;
 263                 u32             lock_seq;
 264         }                       l[BTREE_MAX_DEPTH];
 265
 266         /*
 267          * Current unpacked key - so that bch2_btree_iter_next()/
 268          * bch2_btree_iter_next_slot() can correctly advance pos.
 269          */
 270         struct bkey             k;
 271         unsigned long           ip_allocated;
 272 };
 273
 274 static inline enum btree_iter_type
 275 btree_iter_type(const struct btree_iter *iter)
 276 {
 277         return iter->flags & BTREE_ITER_TYPE;
 278 }
 279
 280 static inline bool btree_iter_is_cached(const struct btree_iter *iter)
 281 {
 282         return btree_iter_type(iter) == BTREE_ITER_CACHED;
 283 }
 284
 285 static inline struct btree_iter_level *iter_l(struct btree_iter *iter)
 286 {
 287         return iter->l + iter->level;
 288 }
 289
 290 struct btree_key_cache {
 291         struct mutex            lock;
 292         struct rhashtable       table;
 293         bool                    table_init_done;
 294         struct list_head        freed;
 295         struct list_head        clean;
 296         struct list_head        dirty;
 297         struct shrinker         shrink;
 298
 299         size_t                  nr_freed;
 300         size_t                  nr_keys;
 301         size_t                  nr_dirty;
 302 };
 303
 304 struct bkey_cached_key {
 305         u32                     btree_id;
 306         struct bpos             pos;
 307 } __attribute__((packed, aligned(4)));
 308
 309 #define BKEY_CACHED_ACCESSED            0
 310 #define BKEY_CACHED_DIRTY               1
 311
 312 struct bkey_cached {
 313         struct btree_bkey_cached_common c;
 314
 315         unsigned long           flags;
 316         u8                      u64s;
 317         bool                    valid;
 318         u32                     btree_trans_barrier_seq;
 319         struct bkey_cached_key  key;
 320
 321         struct rhash_head       hash;
 322         struct list_head        list;
 323
 324         struct journal_preres   res;
 325         struct journal_entry_pin journal;
 326
 327         struct bkey_i           *k;
 328 };
 329
 330 struct btree_insert_entry {
 331         unsigned                trigger_flags;
 332         u8                      bkey_type;
 333         u8                      btree_id;
 334         u8                      level;
 335         unsigned                trans_triggers_run:1;
 336         unsigned                is_extent:1;
 337         struct bkey_i           *k;
 338         struct btree_iter       *iter;
 339 };
 340
 341 #ifndef CONFIG_LOCKDEP
 342 #define BTREE_ITER_MAX          64
 343 #else
 344 #define BTREE_ITER_MAX          32
 345 #endif
 346
 347 struct btree_trans {
 348         struct bch_fs           *c;
 349 #ifdef CONFIG_BCACHEFS_DEBUG
 350         struct list_head        list;
 351         struct btree            *locking;
 352         unsigned                locking_iter_idx;
 353         struct bpos             locking_pos;
 354         u8                      locking_btree_id;
 355         u8                      locking_level;
 356         pid_t                   pid;
 357 #endif
 358         unsigned long           ip;
 359         int                     srcu_idx;
 360
 361         u8                      nr_updates;
 362         u8                      nr_updates2;
 363         unsigned                used_mempool:1;
 364         unsigned                error:1;
 365         unsigned                nounlock:1;
 366         unsigned                in_traverse_all:1;
 367
 368         u64                     iters_linked;
 369         u64                     iters_live;
 370         u64                     iters_touched;
 371
 372         unsigned                mem_top;
 373         unsigned                mem_bytes;
 374         void                    *mem;
 375
 376         struct btree_iter       *iters;
 377         struct btree_insert_entry *updates;
 378         struct btree_insert_entry *updates2;
 379
 380         /* update path: */
 381         struct jset_entry       *extra_journal_entries;
 382         unsigned                extra_journal_entry_u64s;
 383         struct journal_entry_pin *journal_pin;
 384
 385         struct journal_res      journal_res;
 386         struct journal_preres   journal_preres;
 387         u64                     *journal_seq;
 388         struct disk_reservation *disk_res;
 389         unsigned                flags;
 390         unsigned                journal_u64s;
 391         unsigned                journal_preres_u64s;
 392         struct replicas_delta_list *fs_usage_deltas;
 393 };
 394
 395 #define BTREE_FLAG(flag)                                                \
 396 static inline bool btree_node_ ## flag(struct btree *b)                 \
 397 {       return test_bit(BTREE_NODE_ ## flag, &b->flags); }              \
 398                                                                         \
 399 static inline void set_btree_node_ ## flag(struct btree *b)             \
 400 {       set_bit(BTREE_NODE_ ## flag, &b->flags); }                      \
 401                                                                         \
 402 static inline void clear_btree_node_ ## flag(struct btree *b)           \
 403 {       clear_bit(BTREE_NODE_ ## flag, &b->flags); }
 404
 405 enum btree_flags {
 406         BTREE_NODE_read_in_flight,
 407         BTREE_NODE_read_error,
 408         BTREE_NODE_dirty,
 409         BTREE_NODE_need_write,
 410         BTREE_NODE_noevict,
 411         BTREE_NODE_write_idx,
 412         BTREE_NODE_accessed,
 413         BTREE_NODE_write_in_flight,
 414         BTREE_NODE_just_written,
 415         BTREE_NODE_dying,
 416         BTREE_NODE_fake,
 417         BTREE_NODE_need_rewrite,
 418         BTREE_NODE_never_write,
 419 };
 420
 421 BTREE_FLAG(read_in_flight);
 422 BTREE_FLAG(read_error);
 423 BTREE_FLAG(need_write);
 424 BTREE_FLAG(noevict);
 425 BTREE_FLAG(write_idx);
 426 BTREE_FLAG(accessed);
 427 BTREE_FLAG(write_in_flight);
 428 BTREE_FLAG(just_written);
 429 BTREE_FLAG(dying);
 430 BTREE_FLAG(fake);
 431 BTREE_FLAG(need_rewrite);
 432 BTREE_FLAG(never_write);
 433
 434 static inline struct btree_write *btree_current_write(struct btree *b)
 435 {
 436         return b->writes + btree_node_write_idx(b);
 437 }
 438
 439 static inline struct btree_write *btree_prev_write(struct btree *b)
 440 {
 441         return b->writes + (btree_node_write_idx(b) ^ 1);
 442 }
 443
 444 static inline struct bset_tree *bset_tree_last(struct btree *b)
 445 {
 446         EBUG_ON(!b->nsets);
 447         return b->set + b->nsets - 1;
 448 }
 449
 450 static inline void *
 451 __btree_node_offset_to_ptr(const struct btree *b, u16 offset)
 452 {
 453         return (void *) ((u64 *) b->data + 1 + offset);
 454 }
 455
 456 static inline u16
 457 __btree_node_ptr_to_offset(const struct btree *b, const void *p)
 458 {
 459         u16 ret = (u64 *) p - 1 - (u64 *) b->data;
 460
 461         EBUG_ON(__btree_node_offset_to_ptr(b, ret) != p);
 462         return ret;
 463 }
 464
 465 static inline struct bset *bset(const struct btree *b,
 466                                 const struct bset_tree *t)
 467 {
 468         return __btree_node_offset_to_ptr(b, t->data_offset);
 469 }
 470
 471 static inline void set_btree_bset_end(struct btree *b, struct bset_tree *t)
 472 {
 473         t->end_offset =
 474                 __btree_node_ptr_to_offset(b, vstruct_last(bset(b, t)));
 475 }
 476
 477 static inline void set_btree_bset(struct btree *b, struct bset_tree *t,
 478                                   const struct bset *i)
 479 {
 480         t->data_offset = __btree_node_ptr_to_offset(b, i);
 481         set_btree_bset_end(b, t);
 482 }
 483
 484 static inline struct bset *btree_bset_first(struct btree *b)
 485 {
 486         return bset(b, b->set);
 487 }
 488
 489 static inline struct bset *btree_bset_last(struct btree *b)
 490 {
 491         return bset(b, bset_tree_last(b));
 492 }
 493
 494 static inline u16
 495 __btree_node_key_to_offset(const struct btree *b, const struct bkey_packed *k)
 496 {
 497         return __btree_node_ptr_to_offset(b, k);
 498 }
 499
 500 static inline struct bkey_packed *
 501 __btree_node_offset_to_key(const struct btree *b, u16 k)
 502 {
 503         return __btree_node_offset_to_ptr(b, k);
 504 }
 505
 506 static inline unsigned btree_bkey_first_offset(const struct bset_tree *t)
 507 {
 508         return t->data_offset + offsetof(struct bset, _data) / sizeof(u64);
 509 }
 510
 511 #define btree_bkey_first(_b, _t)                                        \
 512 ({                                                                      \
 513         EBUG_ON(bset(_b, _t)->start !=                                  \
 514                 __btree_node_offset_to_key(_b, btree_bkey_first_offset(_t)));\
 515                                                                         \
 516         bset(_b, _t)->start;                                            \
 517 })
 518
 519 #define btree_bkey_last(_b, _t)                                         \
 520 ({                                                                      \
 521         EBUG_ON(__btree_node_offset_to_key(_b, (_t)->end_offset) !=     \
 522                 vstruct_last(bset(_b, _t)));                            \
 523                                                                         \
 524         __btree_node_offset_to_key(_b, (_t)->end_offset);               \
 525 })
 526
 527 static inline unsigned bset_u64s(struct bset_tree *t)
 528 {
 529         return t->end_offset - t->data_offset -
 530                 sizeof(struct bset) / sizeof(u64);
 531 }
 532
 533 static inline unsigned bset_dead_u64s(struct btree *b, struct bset_tree *t)
 534 {
 535         return bset_u64s(t) - b->nr.bset_u64s[t - b->set];
 536 }
 537
 538 static inline unsigned bset_byte_offset(struct btree *b, void *i)
 539 {
 540         return i - (void *) b->data;
 541 }
 542
 543 enum btree_node_type {
 544 #define x(kwd, val) BKEY_TYPE_##kwd = val,
 545         BCH_BTREE_IDS()
 546 #undef x
 547         BKEY_TYPE_btree,
 548 };
 549
 550 /* Type of a key in btree @id at level @level: */
 551 static inline enum btree_node_type __btree_node_type(unsigned level, enum btree_id id)
 552 {
 553         return level ? BKEY_TYPE_btree : (enum btree_node_type) id;
 554 }
 555
 556 /* Type of keys @b contains: */
 557 static inline enum btree_node_type btree_node_type(struct btree *b)
 558 {
 559         return __btree_node_type(b->c.level, b->c.btree_id);
 560 }
 561
 562 static inline bool btree_node_type_is_extents(enum btree_node_type type)
 563 {
 564         switch (type) {
 565         case BKEY_TYPE_extents:
 566         case BKEY_TYPE_reflink:
 567                 return true;
 568         default:
 569                 return false;
 570         }
 571 }
 572
 573 static inline bool btree_node_is_extents(struct btree *b)
 574 {
 575         return btree_node_type_is_extents(btree_node_type(b));
 576 }
 577
 578 static inline enum btree_node_type btree_iter_key_type(struct btree_iter *iter)
 579 {
 580         return __btree_node_type(iter->level, iter->btree_id);
 581 }
 582
 583 static inline bool btree_iter_is_extents(struct btree_iter *iter)
 584 {
 585         return btree_node_type_is_extents(btree_iter_key_type(iter));
 586 }
 587
 588 #define BTREE_NODE_TYPE_HAS_TRANS_TRIGGERS              \
 589         ((1U << BKEY_TYPE_extents)|                     \
 590          (1U << BKEY_TYPE_inodes)|                      \
 591          (1U << BKEY_TYPE_stripes)|                     \
 592          (1U << BKEY_TYPE_reflink)|                     \
 593          (1U << BKEY_TYPE_btree))
 594
 595 #define BTREE_NODE_TYPE_HAS_MEM_TRIGGERS                \
 596         ((1U << BKEY_TYPE_alloc)|                       \
 597          (1U << BKEY_TYPE_stripes))
 598
 599 #define BTREE_NODE_TYPE_HAS_TRIGGERS                    \
 600         (BTREE_NODE_TYPE_HAS_TRANS_TRIGGERS|            \
 601          BTREE_NODE_TYPE_HAS_MEM_TRIGGERS)
 602
 603 enum btree_trigger_flags {
 604         __BTREE_TRIGGER_NORUN,          /* Don't run triggers at all */
 605
 606         __BTREE_TRIGGER_INSERT,
 607         __BTREE_TRIGGER_OVERWRITE,
 608         __BTREE_TRIGGER_OVERWRITE_SPLIT,
 609
 610         __BTREE_TRIGGER_GC,
 611         __BTREE_TRIGGER_BUCKET_INVALIDATE,
 612         __BTREE_TRIGGER_NOATOMIC,
 613 };
 614
 615 #define BTREE_TRIGGER_NORUN             (1U << __BTREE_TRIGGER_NORUN)
 616
 617 #define BTREE_TRIGGER_INSERT            (1U << __BTREE_TRIGGER_INSERT)
 618 #define BTREE_TRIGGER_OVERWRITE         (1U << __BTREE_TRIGGER_OVERWRITE)
 619 #define BTREE_TRIGGER_OVERWRITE_SPLIT   (1U << __BTREE_TRIGGER_OVERWRITE_SPLIT)
 620
 621 #define BTREE_TRIGGER_GC                (1U << __BTREE_TRIGGER_GC)
 622 #define BTREE_TRIGGER_BUCKET_INVALIDATE (1U << __BTREE_TRIGGER_BUCKET_INVALIDATE)
 623 #define BTREE_TRIGGER_NOATOMIC          (1U << __BTREE_TRIGGER_NOATOMIC)
 624
 625 static inline bool btree_node_type_needs_gc(enum btree_node_type type)
 626 {
 627         return BTREE_NODE_TYPE_HAS_TRIGGERS & (1U << type);
 628 }
 629
 630 struct btree_root {
 631         struct btree            *b;
 632
 633         /* On disk root - see async splits: */
 634         __BKEY_PADDED(key, BKEY_BTREE_PTR_VAL_U64s_MAX);
 635         u8                      level;
 636         u8                      alive;
 637         s8                      error;
 638 };
 639
 640 /*
 641  * Optional hook that will be called just prior to a btree node update, when
 642  * we're holding the write lock and we know what key is about to be overwritten:
 643  */
 644
 645 enum btree_insert_ret {
 646         BTREE_INSERT_OK,
 647         /* leaf node needs to be split */
 648         BTREE_INSERT_BTREE_NODE_FULL,
 649         BTREE_INSERT_ENOSPC,
 650         BTREE_INSERT_NEED_MARK_REPLICAS,
 651         BTREE_INSERT_NEED_JOURNAL_RES,
 652         BTREE_INSERT_NEED_JOURNAL_RECLAIM,
 653 };
 654
 655 enum btree_gc_coalesce_fail_reason {
 656         BTREE_GC_COALESCE_FAIL_RESERVE_GET,
 657         BTREE_GC_COALESCE_FAIL_KEYLIST_REALLOC,
 658         BTREE_GC_COALESCE_FAIL_FORMAT_FITS,
 659 };
 660
 661 enum btree_node_sibling {
 662         btree_prev_sib,
 663         btree_next_sib,
 664 };
 665
 666 typedef struct btree_nr_keys (*sort_fix_overlapping_fn)(struct bset *,
 667                                                         struct btree *,
 668                                                         struct btree_node_iter *);
 669
 670 #endif /* _BCACHEFS_BTREE_TYPES_H */