fs/bcachefs/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
   8 #include "bkey_methods.h"
   9 #include "journal_types.h"
  10 #include "six.h"
  11
  12 struct open_bucket;
  13 struct btree_update;
  14
  15 #define MAX_BSETS               3U
  16
  17 struct btree_nr_keys {
  18
  19         /*
  20          * Amount of live metadata (i.e. size of node after a compaction) in
  21          * units of u64s
  22          */
  23         u16                     live_u64s;
  24         u16                     bset_u64s[MAX_BSETS];
  25
  26         /* live keys only: */
  27         u16                     packed_keys;
  28         u16                     unpacked_keys;
  29 };
  30
  31 struct bset_tree {
  32         /*
  33          * We construct a binary tree in an array as if the array
  34          * started at 1, so that things line up on the same cachelines
  35          * better: see comments in bset.c at cacheline_to_bkey() for
  36          * details
  37          */
  38
  39         /* size of the binary tree and prev array */
  40         u16                     size;
  41
  42         /* function of size - precalculated for to_inorder() */
  43         u16                     extra;
  44
  45         u16                     data_offset;
  46         u16                     aux_data_offset;
  47         u16                     end_offset;
  48
  49         struct bpos             max_key;
  50 };
  51
  52 struct btree_write {
  53         struct journal_entry_pin        journal;
  54         struct closure_waitlist         wait;
  55 };
  56
  57 struct btree_ob_ref {
  58         u8                      nr;
  59         u8                      refs[BCH_REPLICAS_MAX];
  60 };
  61
  62 struct btree_alloc {
  63         struct btree_ob_ref     ob;
  64         BKEY_PADDED(k);
  65 };
  66
  67 struct btree {
  68         /* Hottest entries first */
  69         struct rhash_head       hash;
  70
  71         /* Key/pointer for this btree node */
  72         __BKEY_PADDED(key, BKEY_BTREE_PTR_VAL_U64s_MAX);
  73
  74         struct six_lock         lock;
  75
  76         unsigned long           flags;
  77         u16                     written;
  78         u8                      level;
  79         u8                      btree_id;
  80         u8                      nsets;
  81         u8                      nr_key_bits;
  82
  83         struct bkey_format      format;
  84
  85         struct btree_node       *data;
  86         void                    *aux_data;
  87
  88         /*
  89          * Sets of sorted keys - the real btree node - plus a binary search tree
  90          *
  91          * set[0] is special; set[0]->tree, set[0]->prev and set[0]->data point
  92          * to the memory we have allocated for this btree node. Additionally,
  93          * set[0]->data points to the entire btree node as it exists on disk.
  94          */
  95         struct bset_tree        set[MAX_BSETS];
  96
  97         struct btree_nr_keys    nr;
  98         u16                     sib_u64s[2];
  99         u16                     whiteout_u64s;
 100         u16                     uncompacted_whiteout_u64s;
 101         u8                      page_order;
 102         u8                      unpack_fn_len;
 103
 104         /*
 105          * XXX: add a delete sequence number, so when bch2_btree_node_relock()
 106          * fails because the lock sequence number has changed - i.e. the
 107          * contents were modified - we can still relock the node if it's still
 108          * the one we want, without redoing the traversal
 109          */
 110
 111         /*
 112          * For asynchronous splits/interior node updates:
 113          * When we do a split, we allocate new child nodes and update the parent
 114          * node to point to them: we update the parent in memory immediately,
 115          * but then we must wait until the children have been written out before
 116          * the update to the parent can be written - this is a list of the
 117          * btree_updates that are blocking this node from being
 118          * written:
 119          */
 120         struct list_head        write_blocked;
 121
 122         /*
 123          * Also for asynchronous splits/interior node updates:
 124          * If a btree node isn't reachable yet, we don't want to kick off
 125          * another write - because that write also won't yet be reachable and
 126          * marking it as completed before it's reachable would be incorrect:
 127          */
 128         unsigned long           will_make_reachable;
 129
 130         struct btree_ob_ref     ob;
 131
 132         /* lru list */
 133         struct list_head        list;
 134
 135         struct btree_write      writes[2];
 136
 137 #ifdef CONFIG_BCACHEFS_DEBUG
 138         bool                    *expensive_debug_checks;
 139 #endif
 140 };
 141
 142 struct btree_cache {
 143         struct rhashtable       table;
 144         bool                    table_init_done;
 145         /*
 146          * We never free a struct btree, except on shutdown - we just put it on
 147          * the btree_cache_freed list and reuse it later. This simplifies the
 148          * code, and it doesn't cost us much memory as the memory usage is
 149          * dominated by buffers that hold the actual btree node data and those
 150          * can be freed - and the number of struct btrees allocated is
 151          * effectively bounded.
 152          *
 153          * btree_cache_freeable effectively is a small cache - we use it because
 154          * high order page allocations can be rather expensive, and it's quite
 155          * common to delete and allocate btree nodes in quick succession. It
 156          * should never grow past ~2-3 nodes in practice.
 157          */
 158         struct mutex            lock;
 159         struct list_head        live;
 160         struct list_head        freeable;
 161         struct list_head        freed;
 162
 163         /* Number of elements in live + freeable lists */
 164         unsigned                used;
 165         unsigned                reserve;
 166         struct shrinker         shrink;
 167
 168         /*
 169          * If we need to allocate memory for a new btree node and that
 170          * allocation fails, we can cannibalize another node in the btree cache
 171          * to satisfy the allocation - lock to guarantee only one thread does
 172          * this at a time:
 173          */
 174         struct task_struct      *alloc_lock;
 175         struct closure_waitlist alloc_wait;
 176 };
 177
 178 struct btree_node_iter {
 179         u8              is_extents;
 180
 181         struct btree_node_iter_set {
 182                 u16     k, end;
 183         } data[MAX_BSETS];
 184 };
 185
 186 enum btree_iter_type {
 187         BTREE_ITER_KEYS,
 188         BTREE_ITER_SLOTS,
 189         BTREE_ITER_NODES,
 190 };
 191
 192 #define BTREE_ITER_TYPE                 ((1 << 2) - 1)
 193
 194 #define BTREE_ITER_INTENT               (1 << 2)
 195 #define BTREE_ITER_PREFETCH             (1 << 3)
 196 /*
 197  * Used in bch2_btree_iter_traverse(), to indicate whether we're searching for
 198  * @pos or the first key strictly greater than @pos
 199  */
 200 #define BTREE_ITER_IS_EXTENTS           (1 << 4)
 201 /*
 202  * indicates we need to call bch2_btree_iter_traverse() to revalidate iterator:
 203  */
 204 #define BTREE_ITER_AT_END_OF_LEAF       (1 << 5)
 205 #define BTREE_ITER_ERROR                (1 << 6)
 206
 207 enum btree_iter_uptodate {
 208         BTREE_ITER_UPTODATE             = 0,
 209         BTREE_ITER_NEED_PEEK            = 1,
 210         BTREE_ITER_NEED_RELOCK          = 2,
 211         BTREE_ITER_NEED_TRAVERSE        = 3,
 212 };
 213
 214 /*
 215  * @pos                 - iterator's current position
 216  * @level               - current btree depth
 217  * @locks_want          - btree level below which we start taking intent locks
 218  * @nodes_locked        - bitmask indicating which nodes in @nodes are locked
 219  * @nodes_intent_locked - bitmask indicating which locks are intent locks
 220  */
 221 struct btree_iter {
 222         struct bch_fs           *c;
 223         struct bpos             pos;
 224
 225         u8                      flags;
 226         enum btree_iter_uptodate uptodate:4;
 227         enum btree_id           btree_id:4;
 228         unsigned                level:4,
 229                                 locks_want:4,
 230                                 nodes_locked:4,
 231                                 nodes_intent_locked:4;
 232
 233         struct btree_iter_level {
 234                 struct btree    *b;
 235                 struct btree_node_iter iter;
 236         }                       l[BTREE_MAX_DEPTH];
 237
 238         u32                     lock_seq[BTREE_MAX_DEPTH];
 239
 240         /*
 241          * Current unpacked key - so that bch2_btree_iter_next()/
 242          * bch2_btree_iter_next_slot() can correctly advance pos.
 243          */
 244         struct bkey             k;
 245
 246         /*
 247          * Circular linked list of linked iterators: linked iterators share
 248          * locks (e.g. two linked iterators may have the same node intent
 249          * locked, or read and write locked, at the same time), and insertions
 250          * through one iterator won't invalidate the other linked iterators.
 251          */
 252
 253         /* Must come last: */
 254         struct btree_iter       *next;
 255 };
 256
 257 #define BTREE_ITER_MAX          8
 258
 259 struct btree_insert_entry {
 260         struct btree_iter *iter;
 261         struct bkey_i   *k;
 262         unsigned        extra_res;
 263         /*
 264          * true if entire key was inserted - can only be false for
 265          * extents
 266          */
 267         bool            done;
 268 };
 269
 270 struct btree_trans {
 271         struct bch_fs           *c;
 272         size_t                  nr_restarts;
 273
 274         u8                      nr_iters;
 275         u8                      iters_live;
 276         u8                      iters_linked;
 277         u8                      nr_updates;
 278
 279         unsigned                mem_top;
 280         unsigned                mem_bytes;
 281         void                    *mem;
 282
 283         struct btree_iter       *iters;
 284         u64                     iter_ids[BTREE_ITER_MAX];
 285
 286         struct btree_insert_entry updates[BTREE_ITER_MAX];
 287
 288         struct btree_iter       iters_onstack[2];
 289 };
 290
 291 #define BTREE_FLAG(flag)                                                \
 292 static inline bool btree_node_ ## flag(struct btree *b)                 \
 293 {       return test_bit(BTREE_NODE_ ## flag, &b->flags); }              \
 294                                                                         \
 295 static inline void set_btree_node_ ## flag(struct btree *b)             \
 296 {       set_bit(BTREE_NODE_ ## flag, &b->flags); }                      \
 297                                                                         \
 298 static inline void clear_btree_node_ ## flag(struct btree *b)           \
 299 {       clear_bit(BTREE_NODE_ ## flag, &b->flags); }
 300
 301 enum btree_flags {
 302         BTREE_NODE_read_in_flight,
 303         BTREE_NODE_read_error,
 304         BTREE_NODE_dirty,
 305         BTREE_NODE_need_write,
 306         BTREE_NODE_noevict,
 307         BTREE_NODE_write_idx,
 308         BTREE_NODE_accessed,
 309         BTREE_NODE_write_in_flight,
 310         BTREE_NODE_just_written,
 311         BTREE_NODE_dying,
 312         BTREE_NODE_fake,
 313 };
 314
 315 BTREE_FLAG(read_in_flight);
 316 BTREE_FLAG(read_error);
 317 BTREE_FLAG(dirty);
 318 BTREE_FLAG(need_write);
 319 BTREE_FLAG(noevict);
 320 BTREE_FLAG(write_idx);
 321 BTREE_FLAG(accessed);
 322 BTREE_FLAG(write_in_flight);
 323 BTREE_FLAG(just_written);
 324 BTREE_FLAG(dying);
 325 BTREE_FLAG(fake);
 326
 327 static inline struct btree_write *btree_current_write(struct btree *b)
 328 {
 329         return b->writes + btree_node_write_idx(b);
 330 }
 331
 332 static inline struct btree_write *btree_prev_write(struct btree *b)
 333 {
 334         return b->writes + (btree_node_write_idx(b) ^ 1);
 335 }
 336
 337 static inline struct bset_tree *bset_tree_last(struct btree *b)
 338 {
 339         EBUG_ON(!b->nsets);
 340         return b->set + b->nsets - 1;
 341 }
 342
 343 static inline struct bset *bset(const struct btree *b,
 344                                 const struct bset_tree *t)
 345 {
 346         return (void *) b->data + t->data_offset * sizeof(u64);
 347 }
 348
 349 static inline struct bset *btree_bset_first(struct btree *b)
 350 {
 351         return bset(b, b->set);
 352 }
 353
 354 static inline struct bset *btree_bset_last(struct btree *b)
 355 {
 356         return bset(b, bset_tree_last(b));
 357 }
 358
 359 static inline u16
 360 __btree_node_key_to_offset(const struct btree *b, const struct bkey_packed *k)
 361 {
 362         size_t ret = (u64 *) k - (u64 *) b->data - 1;
 363
 364         EBUG_ON(ret > U16_MAX);
 365         return ret;
 366 }
 367
 368 static inline struct bkey_packed *
 369 __btree_node_offset_to_key(const struct btree *b, u16 k)
 370 {
 371         return (void *) ((u64 *) b->data + k + 1);
 372 }
 373
 374 #define btree_bkey_first(_b, _t)        (bset(_b, _t)->start)
 375
 376 #define btree_bkey_last(_b, _t)                                         \
 377 ({                                                                      \
 378         EBUG_ON(__btree_node_offset_to_key(_b, (_t)->end_offset) !=     \
 379                 vstruct_last(bset(_b, _t)));                            \
 380                                                                         \
 381         __btree_node_offset_to_key(_b, (_t)->end_offset);               \
 382 })
 383
 384 static inline void set_btree_bset_end(struct btree *b, struct bset_tree *t)
 385 {
 386         t->end_offset =
 387                 __btree_node_key_to_offset(b, vstruct_last(bset(b, t)));
 388         btree_bkey_last(b, t);
 389 }
 390
 391 static inline void set_btree_bset(struct btree *b, struct bset_tree *t,
 392                                   const struct bset *i)
 393 {
 394         t->data_offset = (u64 *) i - (u64 *) b->data;
 395
 396         EBUG_ON(bset(b, t) != i);
 397
 398         set_btree_bset_end(b, t);
 399 }
 400
 401 static inline unsigned bset_byte_offset(struct btree *b, void *i)
 402 {
 403         return i - (void *) b->data;
 404 }
 405
 406 /* Type of keys @b contains: */
 407 static inline enum bkey_type btree_node_type(struct btree *b)
 408 {
 409         return b->level ? BKEY_TYPE_BTREE : b->btree_id;
 410 }
 411
 412 static inline const struct bkey_ops *btree_node_ops(struct btree *b)
 413 {
 414         return &bch2_bkey_ops[btree_node_type(b)];
 415 }
 416
 417 static inline bool btree_node_has_ptrs(struct btree *b)
 418 {
 419         return btree_type_has_ptrs(btree_node_type(b));
 420 }
 421
 422 static inline bool btree_node_is_extents(struct btree *b)
 423 {
 424         return btree_node_type(b) == BKEY_TYPE_EXTENTS;
 425 }
 426
 427 struct btree_root {
 428         struct btree            *b;
 429
 430         struct btree_update     *as;
 431
 432         /* On disk root - see async splits: */
 433         __BKEY_PADDED(key, BKEY_BTREE_PTR_VAL_U64s_MAX);
 434         u8                      level;
 435         u8                      alive;
 436 };
 437
 438 /*
 439  * Optional hook that will be called just prior to a btree node update, when
 440  * we're holding the write lock and we know what key is about to be overwritten:
 441  */
 442
 443 struct btree_iter;
 444 struct btree_node_iter;
 445
 446 enum btree_insert_ret {
 447         BTREE_INSERT_OK,
 448         /* extent spanned multiple leaf nodes: have to traverse to next node: */
 449         BTREE_INSERT_NEED_TRAVERSE,
 450         /* write lock held for too long */
 451         BTREE_INSERT_NEED_RESCHED,
 452         /* leaf node needs to be split */
 453         BTREE_INSERT_BTREE_NODE_FULL,
 454         BTREE_INSERT_JOURNAL_RES_FULL,
 455         BTREE_INSERT_ENOSPC,
 456         BTREE_INSERT_NEED_GC_LOCK,
 457 };
 458
 459 struct extent_insert_hook {
 460         enum btree_insert_ret
 461         (*fn)(struct extent_insert_hook *, struct bpos, struct bpos,
 462               struct bkey_s_c, const struct bkey_i *);
 463 };
 464
 465 enum btree_gc_coalesce_fail_reason {
 466         BTREE_GC_COALESCE_FAIL_RESERVE_GET,
 467         BTREE_GC_COALESCE_FAIL_KEYLIST_REALLOC,
 468         BTREE_GC_COALESCE_FAIL_FORMAT_FITS,
 469 };
 470
 471 enum btree_node_sibling {
 472         btree_prev_sib,
 473         btree_next_sib,
 474 };
 475
 476 typedef struct btree_nr_keys (*sort_fix_overlapping_fn)(struct bset *,
 477                                                         struct btree *,
 478                                                         struct btree_node_iter *);
 479
 480 #endif /* _BCACHEFS_BTREE_TYPES_H */