git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/btree_cache.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "bkey_buf.h"
   5 #include "btree_cache.h"
   6 #include "btree_io.h"
   7 #include "btree_iter.h"
   8 #include "btree_locking.h"
   9 #include "debug.h"
  10 #include "error.h"
  11
  12 #include <linux/prefetch.h>
  13 #include <linux/sched/mm.h>
  14 #include <trace/events/bcachefs.h>
  15
  16 struct lock_class_key bch2_btree_node_lock_key;
  17
  18 void bch2_recalc_btree_reserve(struct bch_fs *c)
  19 {
  20         unsigned i, reserve = 16;
  21
  22         if (!c->btree_roots[0].b)
  23                 reserve += 8;
  24
  25         for (i = 0; i < BTREE_ID_NR; i++)
  26                 if (c->btree_roots[i].b)
  27                         reserve += min_t(unsigned, 1,
  28                                          c->btree_roots[i].b->c.level) * 8;
  29
  30         c->btree_cache.reserve = reserve;
  31 }
  32
  33 static inline unsigned btree_cache_can_free(struct btree_cache *bc)
  34 {
  35         return max_t(int, 0, bc->used - bc->reserve);
  36 }
  37
  38 static void btree_node_data_free(struct bch_fs *c, struct btree *b)
  39 {
  40         struct btree_cache *bc = &c->btree_cache;
  41
  42         EBUG_ON(btree_node_write_in_flight(b));
  43
  44         kvpfree(b->data, btree_bytes(c));
  45         b->data = NULL;
  46 #ifdef __KERNEL__
  47         vfree(b->aux_data);
  48 #else
  49         munmap(b->aux_data, btree_aux_data_bytes(b));
  50 #endif
  51         b->aux_data = NULL;
  52
  53         bc->used--;
  54         list_move(&b->list, &bc->freed);
  55 }
  56
  57 static int bch2_btree_cache_cmp_fn(struct rhashtable_compare_arg *arg,
  58                                    const void *obj)
  59 {
  60         const struct btree *b = obj;
  61         const u64 *v = arg->key;
  62
  63         return b->hash_val == *v ? 0 : 1;
  64 }
  65
  66 static const struct rhashtable_params bch_btree_cache_params = {
  67         .head_offset    = offsetof(struct btree, hash),
  68         .key_offset     = offsetof(struct btree, hash_val),
  69         .key_len        = sizeof(u64),
  70         .obj_cmpfn      = bch2_btree_cache_cmp_fn,
  71 };
  72
  73 static int btree_node_data_alloc(struct bch_fs *c, struct btree *b, gfp_t gfp)
  74 {
  75         BUG_ON(b->data || b->aux_data);
  76
  77         b->data = kvpmalloc(btree_bytes(c), gfp);
  78         if (!b->data)
  79                 return -ENOMEM;
  80 #ifdef __KERNEL__
  81         b->aux_data = vmalloc_exec(btree_aux_data_bytes(b), gfp);
  82 #else
  83         b->aux_data = mmap(NULL, btree_aux_data_bytes(b),
  84                            PROT_READ|PROT_WRITE|PROT_EXEC,
  85                            MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
  86 #endif
  87         if (!b->aux_data) {
  88                 kvpfree(b->data, btree_bytes(c));
  89                 b->data = NULL;
  90                 return -ENOMEM;
  91         }
  92
  93         return 0;
  94 }
  95
  96 static struct btree *__btree_node_mem_alloc(struct bch_fs *c)
  97 {
  98         struct btree *b = kzalloc(sizeof(struct btree), GFP_KERNEL);
  99         if (!b)
 100                 return NULL;
 101
 102         bkey_btree_ptr_init(&b->key);
 103         __six_lock_init(&b->c.lock, "b->c.lock", &bch2_btree_node_lock_key);
 104         INIT_LIST_HEAD(&b->list);
 105         INIT_LIST_HEAD(&b->write_blocked);
 106         b->byte_order = ilog2(btree_bytes(c));
 107         return b;
 108 }
 109
 110 struct btree *__bch2_btree_node_mem_alloc(struct bch_fs *c)
 111 {
 112         struct btree_cache *bc = &c->btree_cache;
 113         struct btree *b = __btree_node_mem_alloc(c);
 114         if (!b)
 115                 return NULL;
 116
 117         if (btree_node_data_alloc(c, b, GFP_KERNEL)) {
 118                 kfree(b);
 119                 return NULL;
 120         }
 121
 122         bc->used++;
 123         list_add(&b->list, &bc->freeable);
 124         return b;
 125 }
 126
 127 /* Btree in memory cache - hash table */
 128
 129 void bch2_btree_node_hash_remove(struct btree_cache *bc, struct btree *b)
 130 {
 131         rhashtable_remove_fast(&bc->table, &b->hash, bch_btree_cache_params);
 132
 133         /* Cause future lookups for this node to fail: */
 134         b->hash_val = 0;
 135
 136         six_lock_wakeup_all(&b->c.lock);
 137 }
 138
 139 int __bch2_btree_node_hash_insert(struct btree_cache *bc, struct btree *b)
 140 {
 141         BUG_ON(b->hash_val);
 142         b->hash_val = btree_ptr_hash_val(&b->key);
 143
 144         return rhashtable_lookup_insert_fast(&bc->table, &b->hash,
 145                                              bch_btree_cache_params);
 146 }
 147
 148 int bch2_btree_node_hash_insert(struct btree_cache *bc, struct btree *b,
 149                                 unsigned level, enum btree_id id)
 150 {
 151         int ret;
 152
 153         b->c.level      = level;
 154         b->c.btree_id   = id;
 155
 156         if (level)
 157                 six_lock_pcpu_alloc(&b->c.lock);
 158         else
 159                 six_lock_pcpu_free_rcu(&b->c.lock);
 160
 161         mutex_lock(&bc->lock);
 162         ret = __bch2_btree_node_hash_insert(bc, b);
 163         if (!ret)
 164                 list_add(&b->list, &bc->live);
 165         mutex_unlock(&bc->lock);
 166
 167         return ret;
 168 }
 169
 170 __flatten
 171 static inline struct btree *btree_cache_find(struct btree_cache *bc,
 172                                      const struct bkey_i *k)
 173 {
 174         u64 v = btree_ptr_hash_val(k);
 175
 176         return rhashtable_lookup_fast(&bc->table, &v, bch_btree_cache_params);
 177 }
 178
 179 /*
 180  * this version is for btree nodes that have already been freed (we're not
 181  * reaping a real btree node)
 182  */
 183 static int __btree_node_reclaim(struct bch_fs *c, struct btree *b, bool flush)
 184 {
 185         struct btree_cache *bc = &c->btree_cache;
 186         int ret = 0;
 187
 188         lockdep_assert_held(&bc->lock);
 189 wait_on_io:
 190         if (b->flags & ((1U << BTREE_NODE_dirty)|
 191                         (1U << BTREE_NODE_read_in_flight)|
 192                         (1U << BTREE_NODE_write_in_flight))) {
 193                 if (!flush)
 194                         return -ENOMEM;
 195
 196                 /* XXX: waiting on IO with btree cache lock held */
 197                 bch2_btree_node_wait_on_read(b);
 198                 bch2_btree_node_wait_on_write(b);
 199         }
 200
 201         if (!six_trylock_intent(&b->c.lock))
 202                 return -ENOMEM;
 203
 204         if (!six_trylock_write(&b->c.lock))
 205                 goto out_unlock_intent;
 206
 207         /* recheck under lock */
 208         if (b->flags & ((1U << BTREE_NODE_read_in_flight)|
 209                         (1U << BTREE_NODE_write_in_flight))) {
 210                 if (!flush)
 211                         goto out_unlock;
 212                 six_unlock_write(&b->c.lock);
 213                 six_unlock_intent(&b->c.lock);
 214                 goto wait_on_io;
 215         }
 216
 217         if (btree_node_noevict(b))
 218                 goto out_unlock;
 219
 220         if (!btree_node_may_write(b))
 221                 goto out_unlock;
 222
 223         if (btree_node_dirty(b)) {
 224                 if (!flush ||
 225                     test_bit(BCH_FS_HOLD_BTREE_WRITES, &c->flags))
 226                         goto out_unlock;
 227                 /*
 228                  * Using the underscore version because we don't want to compact
 229                  * bsets after the write, since this node is about to be evicted
 230                  * - unless btree verify mode is enabled, since it runs out of
 231                  * the post write cleanup:
 232                  */
 233                 if (bch2_verify_btree_ondisk)
 234                         bch2_btree_node_write(c, b, SIX_LOCK_intent);
 235                 else
 236                         __bch2_btree_node_write(c, b, false);
 237
 238                 six_unlock_write(&b->c.lock);
 239                 six_unlock_intent(&b->c.lock);
 240                 goto wait_on_io;
 241         }
 242 out:
 243         if (b->hash_val && !ret)
 244                 trace_btree_node_reap(c, b);
 245         return ret;
 246 out_unlock:
 247         six_unlock_write(&b->c.lock);
 248 out_unlock_intent:
 249         six_unlock_intent(&b->c.lock);
 250         ret = -ENOMEM;
 251         goto out;
 252 }
 253
 254 static int btree_node_reclaim(struct bch_fs *c, struct btree *b)
 255 {
 256         return __btree_node_reclaim(c, b, false);
 257 }
 258
 259 static int btree_node_write_and_reclaim(struct bch_fs *c, struct btree *b)
 260 {
 261         return __btree_node_reclaim(c, b, true);
 262 }
 263
 264 static unsigned long bch2_btree_cache_scan(struct shrinker *shrink,
 265                                            struct shrink_control *sc)
 266 {
 267         struct bch_fs *c = container_of(shrink, struct bch_fs,
 268                                         btree_cache.shrink);
 269         struct btree_cache *bc = &c->btree_cache;
 270         struct btree *b, *t;
 271         unsigned long nr = sc->nr_to_scan;
 272         unsigned long can_free;
 273         unsigned long touched = 0;
 274         unsigned long freed = 0;
 275         unsigned i, flags;
 276
 277         if (bch2_btree_shrinker_disabled)
 278                 return SHRINK_STOP;
 279
 280         /* Return -1 if we can't do anything right now */
 281         if (sc->gfp_mask & __GFP_FS)
 282                 mutex_lock(&bc->lock);
 283         else if (!mutex_trylock(&bc->lock))
 284                 return -1;
 285
 286         flags = memalloc_nofs_save();
 287
 288         /*
 289          * It's _really_ critical that we don't free too many btree nodes - we
 290          * have to always leave ourselves a reserve. The reserve is how we
 291          * guarantee that allocating memory for a new btree node can always
 292          * succeed, so that inserting keys into the btree can always succeed and
 293          * IO can always make forward progress:
 294          */
 295         nr /= btree_pages(c);
 296         can_free = btree_cache_can_free(bc);
 297         nr = min_t(unsigned long, nr, can_free);
 298
 299         i = 0;
 300         list_for_each_entry_safe(b, t, &bc->freeable, list) {
 301                 touched++;
 302
 303                 if (freed >= nr)
 304                         break;
 305
 306                 if (++i > 3 &&
 307                     !btree_node_reclaim(c, b)) {
 308                         btree_node_data_free(c, b);
 309                         six_unlock_write(&b->c.lock);
 310                         six_unlock_intent(&b->c.lock);
 311                         freed++;
 312                 }
 313         }
 314 restart:
 315         list_for_each_entry_safe(b, t, &bc->live, list) {
 316                 touched++;
 317
 318                 if (freed >= nr) {
 319                         /* Save position */
 320                         if (&t->list != &bc->live)
 321                                 list_move_tail(&bc->live, &t->list);
 322                         break;
 323                 }
 324
 325                 if (!btree_node_accessed(b) &&
 326                     !btree_node_reclaim(c, b)) {
 327                         /* can't call bch2_btree_node_hash_remove under lock  */
 328                         freed++;
 329                         if (&t->list != &bc->live)
 330                                 list_move_tail(&bc->live, &t->list);
 331
 332                         btree_node_data_free(c, b);
 333                         mutex_unlock(&bc->lock);
 334
 335                         bch2_btree_node_hash_remove(bc, b);
 336                         six_unlock_write(&b->c.lock);
 337                         six_unlock_intent(&b->c.lock);
 338
 339                         if (freed >= nr)
 340                                 goto out;
 341
 342                         if (sc->gfp_mask & __GFP_FS)
 343                                 mutex_lock(&bc->lock);
 344                         else if (!mutex_trylock(&bc->lock))
 345                                 goto out;
 346                         goto restart;
 347                 } else
 348                         clear_btree_node_accessed(b);
 349         }
 350
 351         mutex_unlock(&bc->lock);
 352 out:
 353         memalloc_nofs_restore(flags);
 354         return (unsigned long) freed * btree_pages(c);
 355 }
 356
 357 static unsigned long bch2_btree_cache_count(struct shrinker *shrink,
 358                                             struct shrink_control *sc)
 359 {
 360         struct bch_fs *c = container_of(shrink, struct bch_fs,
 361                                         btree_cache.shrink);
 362         struct btree_cache *bc = &c->btree_cache;
 363
 364         if (bch2_btree_shrinker_disabled)
 365                 return 0;
 366
 367         return btree_cache_can_free(bc) * btree_pages(c);
 368 }
 369
 370 void bch2_fs_btree_cache_exit(struct bch_fs *c)
 371 {
 372         struct btree_cache *bc = &c->btree_cache;
 373         struct btree *b;
 374         unsigned i, flags;
 375
 376         if (bc->shrink.list.next)
 377                 unregister_shrinker(&bc->shrink);
 378
 379         /* vfree() can allocate memory: */
 380         flags = memalloc_nofs_save();
 381         mutex_lock(&bc->lock);
 382
 383         if (c->verify_data)
 384                 list_move(&c->verify_data->list, &bc->live);
 385
 386         kvpfree(c->verify_ondisk, btree_bytes(c));
 387
 388         for (i = 0; i < BTREE_ID_NR; i++)
 389                 if (c->btree_roots[i].b)
 390                         list_add(&c->btree_roots[i].b->list, &bc->live);
 391
 392         list_splice(&bc->freeable, &bc->live);
 393
 394         while (!list_empty(&bc->live)) {
 395                 b = list_first_entry(&bc->live, struct btree, list);
 396
 397                 BUG_ON(btree_node_read_in_flight(b) ||
 398                        btree_node_write_in_flight(b));
 399
 400                 if (btree_node_dirty(b))
 401                         bch2_btree_complete_write(c, b, btree_current_write(b));
 402                 clear_btree_node_dirty(c, b);
 403
 404                 btree_node_data_free(c, b);
 405         }
 406
 407         BUG_ON(atomic_read(&c->btree_cache.dirty));
 408
 409         while (!list_empty(&bc->freed)) {
 410                 b = list_first_entry(&bc->freed, struct btree, list);
 411                 list_del(&b->list);
 412                 six_lock_pcpu_free(&b->c.lock);
 413                 kfree(b);
 414         }
 415
 416         mutex_unlock(&bc->lock);
 417         memalloc_nofs_restore(flags);
 418
 419         if (bc->table_init_done)
 420                 rhashtable_destroy(&bc->table);
 421 }
 422
 423 int bch2_fs_btree_cache_init(struct bch_fs *c)
 424 {
 425         struct btree_cache *bc = &c->btree_cache;
 426         unsigned i;
 427         int ret = 0;
 428
 429         pr_verbose_init(c->opts, "");
 430
 431         ret = rhashtable_init(&bc->table, &bch_btree_cache_params);
 432         if (ret)
 433                 goto out;
 434
 435         bc->table_init_done = true;
 436
 437         bch2_recalc_btree_reserve(c);
 438
 439         for (i = 0; i < bc->reserve; i++)
 440                 if (!__bch2_btree_node_mem_alloc(c)) {
 441                         ret = -ENOMEM;
 442                         goto out;
 443                 }
 444
 445         list_splice_init(&bc->live, &bc->freeable);
 446
 447         mutex_init(&c->verify_lock);
 448
 449         bc->shrink.count_objects        = bch2_btree_cache_count;
 450         bc->shrink.scan_objects         = bch2_btree_cache_scan;
 451         bc->shrink.seeks                = 4;
 452         bc->shrink.batch                = btree_pages(c) * 2;
 453         ret = register_shrinker(&bc->shrink);
 454 out:
 455         pr_verbose_init(c->opts, "ret %i", ret);
 456         return ret;
 457 }
 458
 459 void bch2_fs_btree_cache_init_early(struct btree_cache *bc)
 460 {
 461         mutex_init(&bc->lock);
 462         INIT_LIST_HEAD(&bc->live);
 463         INIT_LIST_HEAD(&bc->freeable);
 464         INIT_LIST_HEAD(&bc->freed);
 465 }
 466
 467 /*
 468  * We can only have one thread cannibalizing other cached btree nodes at a time,
 469  * or we'll deadlock. We use an open coded mutex to ensure that, which a
 470  * cannibalize_bucket() will take. This means every time we unlock the root of
 471  * the btree, we need to release this lock if we have it held.
 472  */
 473 void bch2_btree_cache_cannibalize_unlock(struct bch_fs *c)
 474 {
 475         struct btree_cache *bc = &c->btree_cache;
 476
 477         if (bc->alloc_lock == current) {
 478                 trace_btree_node_cannibalize_unlock(c);
 479                 bc->alloc_lock = NULL;
 480                 closure_wake_up(&bc->alloc_wait);
 481         }
 482 }
 483
 484 int bch2_btree_cache_cannibalize_lock(struct bch_fs *c, struct closure *cl)
 485 {
 486         struct btree_cache *bc = &c->btree_cache;
 487         struct task_struct *old;
 488
 489         old = cmpxchg(&bc->alloc_lock, NULL, current);
 490         if (old == NULL || old == current)
 491                 goto success;
 492
 493         if (!cl) {
 494                 trace_btree_node_cannibalize_lock_fail(c);
 495                 return -ENOMEM;
 496         }
 497
 498         closure_wait(&bc->alloc_wait, cl);
 499
 500         /* Try again, after adding ourselves to waitlist */
 501         old = cmpxchg(&bc->alloc_lock, NULL, current);
 502         if (old == NULL || old == current) {
 503                 /* We raced */
 504                 closure_wake_up(&bc->alloc_wait);
 505                 goto success;
 506         }
 507
 508         trace_btree_node_cannibalize_lock_fail(c);
 509         return -EAGAIN;
 510
 511 success:
 512         trace_btree_node_cannibalize_lock(c);
 513         return 0;
 514 }
 515
 516 static struct btree *btree_node_cannibalize(struct bch_fs *c)
 517 {
 518         struct btree_cache *bc = &c->btree_cache;
 519         struct btree *b;
 520
 521         list_for_each_entry_reverse(b, &bc->live, list)
 522                 if (!btree_node_reclaim(c, b))
 523                         return b;
 524
 525         while (1) {
 526                 list_for_each_entry_reverse(b, &bc->live, list)
 527                         if (!btree_node_write_and_reclaim(c, b))
 528                                 return b;
 529
 530                 /*
 531                  * Rare case: all nodes were intent-locked.
 532                  * Just busy-wait.
 533                  */
 534                 WARN_ONCE(1, "btree cache cannibalize failed\n");
 535                 cond_resched();
 536         }
 537 }
 538
 539 struct btree *bch2_btree_node_mem_alloc(struct bch_fs *c)
 540 {
 541         struct btree_cache *bc = &c->btree_cache;
 542         struct btree *b;
 543         u64 start_time = local_clock();
 544         unsigned flags;
 545
 546         flags = memalloc_nofs_save();
 547         mutex_lock(&bc->lock);
 548
 549         /*
 550          * btree_free() doesn't free memory; it sticks the node on the end of
 551          * the list. Check if there's any freed nodes there:
 552          */
 553         list_for_each_entry(b, &bc->freeable, list)
 554                 if (!btree_node_reclaim(c, b))
 555                         goto got_node;
 556
 557         /*
 558          * We never free struct btree itself, just the memory that holds the on
 559          * disk node. Check the freed list before allocating a new one:
 560          */
 561         list_for_each_entry(b, &bc->freed, list)
 562                 if (!btree_node_reclaim(c, b))
 563                         goto got_node;
 564
 565         b = NULL;
 566 got_node:
 567         if (b)
 568                 list_del_init(&b->list);
 569         mutex_unlock(&bc->lock);
 570
 571         if (!b) {
 572                 b = __btree_node_mem_alloc(c);
 573                 if (!b)
 574                         goto err;
 575
 576                 BUG_ON(!six_trylock_intent(&b->c.lock));
 577                 BUG_ON(!six_trylock_write(&b->c.lock));
 578         }
 579
 580         if (!b->data) {
 581                 if (btree_node_data_alloc(c, b, __GFP_NOWARN|GFP_KERNEL))
 582                         goto err;
 583
 584                 mutex_lock(&bc->lock);
 585                 bc->used++;
 586                 mutex_unlock(&bc->lock);
 587         }
 588
 589         BUG_ON(btree_node_hashed(b));
 590         BUG_ON(btree_node_dirty(b));
 591         BUG_ON(btree_node_write_in_flight(b));
 592 out:
 593         b->flags                = 0;
 594         b->written              = 0;
 595         b->nsets                = 0;
 596         b->sib_u64s[0]          = 0;
 597         b->sib_u64s[1]          = 0;
 598         b->whiteout_u64s        = 0;
 599         bch2_btree_keys_init(b);
 600         set_btree_node_accessed(b);
 601
 602         bch2_time_stats_update(&c->times[BCH_TIME_btree_node_mem_alloc],
 603                                start_time);
 604
 605         memalloc_nofs_restore(flags);
 606         return b;
 607 err:
 608         mutex_lock(&bc->lock);
 609
 610         if (b) {
 611                 list_add(&b->list, &bc->freed);
 612                 six_unlock_write(&b->c.lock);
 613                 six_unlock_intent(&b->c.lock);
 614         }
 615
 616         /* Try to cannibalize another cached btree node: */
 617         if (bc->alloc_lock == current) {
 618                 b = btree_node_cannibalize(c);
 619                 list_del_init(&b->list);
 620                 mutex_unlock(&bc->lock);
 621
 622                 bch2_btree_node_hash_remove(bc, b);
 623
 624                 trace_btree_node_cannibalize(c);
 625                 goto out;
 626         }
 627
 628         mutex_unlock(&bc->lock);
 629         memalloc_nofs_restore(flags);
 630         return ERR_PTR(-ENOMEM);
 631 }
 632
 633 /* Slowpath, don't want it inlined into btree_iter_traverse() */
 634 static noinline struct btree *bch2_btree_node_fill(struct bch_fs *c,
 635                                 struct btree_iter *iter,
 636                                 const struct bkey_i *k,
 637                                 enum btree_id btree_id,
 638                                 unsigned level,
 639                                 enum six_lock_type lock_type,
 640                                 bool sync)
 641 {
 642         struct btree_cache *bc = &c->btree_cache;
 643         struct btree *b;
 644         u32 seq;
 645
 646         BUG_ON(level + 1 >= BTREE_MAX_DEPTH);
 647         /*
 648          * Parent node must be locked, else we could read in a btree node that's
 649          * been freed:
 650          */
 651         if (iter && !bch2_btree_node_relock(iter, level + 1)) {
 652                 btree_trans_restart(iter->trans);
 653                 return ERR_PTR(-EINTR);
 654         }
 655
 656         b = bch2_btree_node_mem_alloc(c);
 657         if (IS_ERR(b))
 658                 return b;
 659
 660         bkey_copy(&b->key, k);
 661         if (bch2_btree_node_hash_insert(bc, b, level, btree_id)) {
 662                 /* raced with another fill: */
 663
 664                 /* mark as unhashed... */
 665                 b->hash_val = 0;
 666
 667                 mutex_lock(&bc->lock);
 668                 list_add(&b->list, &bc->freeable);
 669                 mutex_unlock(&bc->lock);
 670
 671                 six_unlock_write(&b->c.lock);
 672                 six_unlock_intent(&b->c.lock);
 673                 return NULL;
 674         }
 675
 676         set_btree_node_read_in_flight(b);
 677
 678         six_unlock_write(&b->c.lock);
 679         seq = b->c.lock.state.seq;
 680         six_unlock_intent(&b->c.lock);
 681
 682         /* Unlock before doing IO: */
 683         if (iter && sync)
 684                 bch2_trans_unlock(iter->trans);
 685
 686         bch2_btree_node_read(c, b, sync);
 687
 688         if (!sync)
 689                 return NULL;
 690
 691         if (iter &&
 692             (!bch2_trans_relock(iter->trans) ||
 693              !bch2_btree_iter_relock_intent(iter))) {
 694                 BUG_ON(!iter->trans->restarted);
 695                 return ERR_PTR(-EINTR);
 696         }
 697
 698         if (!six_relock_type(&b->c.lock, lock_type, seq)) {
 699                 btree_trans_restart(iter->trans);
 700                 return ERR_PTR(-EINTR);
 701         }
 702
 703         return b;
 704 }
 705
 706 static int lock_node_check_fn(struct six_lock *lock, void *p)
 707 {
 708         struct btree *b = container_of(lock, struct btree, c.lock);
 709         const struct bkey_i *k = p;
 710
 711         return b->hash_val == btree_ptr_hash_val(k) ? 0 : -1;
 712 }
 713
 714 static noinline void btree_bad_header(struct bch_fs *c, struct btree *b)
 715 {
 716         char buf1[200], buf2[100], buf3[100];
 717
 718         if (!test_bit(BCH_FS_INITIAL_GC_DONE, &c->flags))
 719                 return;
 720
 721         bch2_bkey_val_to_text(&PBUF(buf1), c, bkey_i_to_s_c(&b->key));
 722         bch2_bpos_to_text(&PBUF(buf2), b->data->min_key);
 723         bch2_bpos_to_text(&PBUF(buf3), b->data->max_key);
 724
 725         bch2_fs_inconsistent(c, "btree node header doesn't match ptr\n"
 726                              "btree %s level %u\n"
 727                              "ptr: %s\n"
 728                              "header: btree %s level %llu\n"
 729                              "min %s max %s\n",
 730                              bch2_btree_ids[b->c.btree_id], b->c.level,
 731                              buf1,
 732                              bch2_btree_ids[BTREE_NODE_ID(b->data)],
 733                              BTREE_NODE_LEVEL(b->data),
 734                              buf2, buf3);
 735 }
 736
 737 static inline void btree_check_header(struct bch_fs *c, struct btree *b)
 738 {
 739         if (b->c.btree_id != BTREE_NODE_ID(b->data) ||
 740             b->c.level != BTREE_NODE_LEVEL(b->data) ||
 741             bpos_cmp(b->data->max_key, b->key.k.p) ||
 742             (b->key.k.type == KEY_TYPE_btree_ptr_v2 &&
 743              bpos_cmp(b->data->min_key,
 744                       bkey_i_to_btree_ptr_v2(&b->key)->v.min_key)))
 745                 btree_bad_header(c, b);
 746 }
 747
 748 /**
 749  * bch_btree_node_get - find a btree node in the cache and lock it, reading it
 750  * in from disk if necessary.
 751  *
 752  * If IO is necessary and running under generic_make_request, returns -EAGAIN.
 753  *
 754  * The btree node will have either a read or a write lock held, depending on
 755  * the @write parameter.
 756  */
 757 struct btree *bch2_btree_node_get(struct btree_trans *trans, struct btree_iter *iter,
 758                                   const struct bkey_i *k, unsigned level,
 759                                   enum six_lock_type lock_type,
 760                                   unsigned long trace_ip)
 761 {
 762         struct bch_fs *c = trans->c;
 763         struct btree_cache *bc = &c->btree_cache;
 764         struct btree *b;
 765         struct bset_tree *t;
 766
 767         EBUG_ON(level >= BTREE_MAX_DEPTH);
 768
 769         if (c->opts.btree_node_mem_ptr_optimization) {
 770                 b = btree_node_mem_ptr(k);
 771                 if (b)
 772                         goto lock_node;
 773         }
 774 retry:
 775         b = btree_cache_find(bc, k);
 776         if (unlikely(!b)) {
 777                 /*
 778                  * We must have the parent locked to call bch2_btree_node_fill(),
 779                  * else we could read in a btree node from disk that's been
 780                  * freed:
 781                  */
 782                 b = bch2_btree_node_fill(c, iter, k, iter->btree_id,
 783                                          level, lock_type, true);
 784
 785                 /* We raced and found the btree node in the cache */
 786                 if (!b)
 787                         goto retry;
 788
 789                 if (IS_ERR(b))
 790                         return b;
 791         } else {
 792 lock_node:
 793                 /*
 794                  * There's a potential deadlock with splits and insertions into
 795                  * interior nodes we have to avoid:
 796                  *
 797                  * The other thread might be holding an intent lock on the node
 798                  * we want, and they want to update its parent node so they're
 799                  * going to upgrade their intent lock on the parent node to a
 800                  * write lock.
 801                  *
 802                  * But if we're holding a read lock on the parent, and we're
 803                  * trying to get the intent lock they're holding, we deadlock.
 804                  *
 805                  * So to avoid this we drop the read locks on parent nodes when
 806                  * we're starting to take intent locks - and handle the race.
 807                  *
 808                  * The race is that they might be about to free the node we
 809                  * want, and dropping our read lock on the parent node lets them
 810                  * update the parent marking the node we want as freed, and then
 811                  * free it:
 812                  *
 813                  * To guard against this, btree nodes are evicted from the cache
 814                  * when they're freed - and b->hash_val is zeroed out, which we
 815                  * check for after we lock the node.
 816                  *
 817                  * Then, bch2_btree_node_relock() on the parent will fail - because
 818                  * the parent was modified, when the pointer to the node we want
 819                  * was removed - and we'll bail out:
 820                  */
 821                 if (btree_node_read_locked(iter, level + 1))
 822                         btree_node_unlock(iter, level + 1);
 823
 824                 if (!btree_node_lock(b, k->k.p, level, iter, lock_type,
 825                                      lock_node_check_fn, (void *) k, trace_ip)) {
 826                         if (!trans->restarted)
 827                                 goto retry;
 828                         return ERR_PTR(-EINTR);
 829                 }
 830
 831                 if (unlikely(b->hash_val != btree_ptr_hash_val(k) ||
 832                              b->c.level != level ||
 833                              race_fault())) {
 834                         six_unlock_type(&b->c.lock, lock_type);
 835                         if (bch2_btree_node_relock(iter, level + 1))
 836                                 goto retry;
 837
 838                         trace_trans_restart_btree_node_reused(trans->ip,
 839                                                               trace_ip,
 840                                                               iter->btree_id,
 841                                                               &iter->real_pos);
 842                         btree_trans_restart(trans);
 843                         return ERR_PTR(-EINTR);
 844                 }
 845         }
 846
 847         if (unlikely(btree_node_read_in_flight(b))) {
 848                 u32 seq = b->c.lock.state.seq;
 849
 850                 six_unlock_type(&b->c.lock, lock_type);
 851                 bch2_trans_unlock(trans);
 852
 853                 bch2_btree_node_wait_on_read(b);
 854
 855                 /*
 856                  * should_be_locked is not set on this iterator yet, so we need
 857                  * to relock it specifically:
 858                  */
 859                 if (iter &&
 860                     (!bch2_trans_relock(trans) ||
 861                      !bch2_btree_iter_relock_intent(iter))) {
 862                         BUG_ON(!trans->restarted);
 863                         return ERR_PTR(-EINTR);
 864                 }
 865
 866                 if (!six_relock_type(&b->c.lock, lock_type, seq))
 867                         goto retry;
 868         }
 869
 870         prefetch(b->aux_data);
 871
 872         for_each_bset(b, t) {
 873                 void *p = (u64 *) b->aux_data + t->aux_data_offset;
 874
 875                 prefetch(p + L1_CACHE_BYTES * 0);
 876                 prefetch(p + L1_CACHE_BYTES * 1);
 877                 prefetch(p + L1_CACHE_BYTES * 2);
 878         }
 879
 880         /* avoid atomic set bit if it's not needed: */
 881         if (!btree_node_accessed(b))
 882                 set_btree_node_accessed(b);
 883
 884         if (unlikely(btree_node_read_error(b))) {
 885                 six_unlock_type(&b->c.lock, lock_type);
 886                 return ERR_PTR(-EIO);
 887         }
 888
 889         EBUG_ON(b->c.btree_id != iter->btree_id);
 890         EBUG_ON(BTREE_NODE_LEVEL(b->data) != level);
 891         btree_check_header(c, b);
 892
 893         return b;
 894 }
 895
 896 struct btree *bch2_btree_node_get_noiter(struct bch_fs *c,
 897                                          const struct bkey_i *k,
 898                                          enum btree_id btree_id,
 899                                          unsigned level,
 900                                          bool nofill)
 901 {
 902         struct btree_cache *bc = &c->btree_cache;
 903         struct btree *b;
 904         struct bset_tree *t;
 905         int ret;
 906
 907         EBUG_ON(level >= BTREE_MAX_DEPTH);
 908
 909         if (c->opts.btree_node_mem_ptr_optimization) {
 910                 b = btree_node_mem_ptr(k);
 911                 if (b)
 912                         goto lock_node;
 913         }
 914 retry:
 915         b = btree_cache_find(bc, k);
 916         if (unlikely(!b)) {
 917                 if (nofill)
 918                         goto out;
 919
 920                 b = bch2_btree_node_fill(c, NULL, k, btree_id,
 921                                          level, SIX_LOCK_read, true);
 922
 923                 /* We raced and found the btree node in the cache */
 924                 if (!b)
 925                         goto retry;
 926
 927                 if (IS_ERR(b) &&
 928                     !bch2_btree_cache_cannibalize_lock(c, NULL))
 929                         goto retry;
 930
 931                 if (IS_ERR(b))
 932                         goto out;
 933         } else {
 934 lock_node:
 935                 ret = six_lock_read(&b->c.lock, lock_node_check_fn, (void *) k);
 936                 if (ret)
 937                         goto retry;
 938
 939                 if (unlikely(b->hash_val != btree_ptr_hash_val(k) ||
 940                              b->c.btree_id != btree_id ||
 941                              b->c.level != level)) {
 942                         six_unlock_read(&b->c.lock);
 943                         goto retry;
 944                 }
 945         }
 946
 947         /* XXX: waiting on IO with btree locks held: */
 948         __bch2_btree_node_wait_on_read(b);
 949
 950         prefetch(b->aux_data);
 951
 952         for_each_bset(b, t) {
 953                 void *p = (u64 *) b->aux_data + t->aux_data_offset;
 954
 955                 prefetch(p + L1_CACHE_BYTES * 0);
 956                 prefetch(p + L1_CACHE_BYTES * 1);
 957                 prefetch(p + L1_CACHE_BYTES * 2);
 958         }
 959
 960         /* avoid atomic set bit if it's not needed: */
 961         if (!btree_node_accessed(b))
 962                 set_btree_node_accessed(b);
 963
 964         if (unlikely(btree_node_read_error(b))) {
 965                 six_unlock_read(&b->c.lock);
 966                 b = ERR_PTR(-EIO);
 967                 goto out;
 968         }
 969
 970         EBUG_ON(b->c.btree_id != btree_id);
 971         EBUG_ON(BTREE_NODE_LEVEL(b->data) != level);
 972         btree_check_header(c, b);
 973 out:
 974         bch2_btree_cache_cannibalize_unlock(c);
 975         return b;
 976 }
 977
 978 int bch2_btree_node_prefetch(struct bch_fs *c, struct btree_iter *iter,
 979                              const struct bkey_i *k,
 980                              enum btree_id btree_id, unsigned level)
 981 {
 982         struct btree_cache *bc = &c->btree_cache;
 983         struct btree *b;
 984
 985         BUG_ON(iter && !btree_node_locked(iter, level + 1));
 986         BUG_ON(level >= BTREE_MAX_DEPTH);
 987
 988         b = btree_cache_find(bc, k);
 989         if (b)
 990                 return 0;
 991
 992         b = bch2_btree_node_fill(c, iter, k, btree_id, level, SIX_LOCK_read, false);
 993         return PTR_ERR_OR_ZERO(b);
 994 }
 995
 996 void bch2_btree_node_evict(struct bch_fs *c, const struct bkey_i *k)
 997 {
 998         struct btree_cache *bc = &c->btree_cache;
 999         struct btree *b;
1000
1001         b = btree_cache_find(bc, k);
1002         if (!b)
1003                 return;
1004 wait_on_io:
1005         /* not allowed to wait on io with btree locks held: */
1006
1007         /* XXX we're called from btree_gc which will be holding other btree
1008          * nodes locked
1009          * */
1010         __bch2_btree_node_wait_on_read(b);
1011         __bch2_btree_node_wait_on_write(b);
1012
1013         six_lock_intent(&b->c.lock, NULL, NULL);
1014         six_lock_write(&b->c.lock, NULL, NULL);
1015
1016         if (btree_node_dirty(b)) {
1017                 __bch2_btree_node_write(c, b, false);
1018                 six_unlock_write(&b->c.lock);
1019                 six_unlock_intent(&b->c.lock);
1020                 goto wait_on_io;
1021         }
1022
1023         BUG_ON(btree_node_dirty(b));
1024
1025         mutex_lock(&bc->lock);
1026         btree_node_data_free(c, b);
1027         bch2_btree_node_hash_remove(bc, b);
1028         mutex_unlock(&bc->lock);
1029
1030         six_unlock_write(&b->c.lock);
1031         six_unlock_intent(&b->c.lock);
1032 }
1033
1034 void bch2_btree_node_to_text(struct printbuf *out, struct bch_fs *c,
1035                              struct btree *b)
1036 {
1037         const struct bkey_format *f = &b->format;
1038         struct bset_stats stats;
1039
1040         memset(&stats, 0, sizeof(stats));
1041
1042         bch2_btree_keys_stats(b, &stats);
1043
1044         pr_buf(out, "l %u ", b->c.level);
1045         bch2_bpos_to_text(out, b->data->min_key);
1046         pr_buf(out, " - ");
1047         bch2_bpos_to_text(out, b->data->max_key);
1048         pr_buf(out, ":\n"
1049                "    ptrs: ");
1050         bch2_val_to_text(out, c, bkey_i_to_s_c(&b->key));
1051
1052         pr_buf(out, "\n"
1053                "    format: u64s %u fields %u %u %u %u %u\n"
1054                "    unpack fn len: %u\n"
1055                "    bytes used %zu/%zu (%zu%% full)\n"
1056                "    sib u64s: %u, %u (merge threshold %u)\n"
1057                "    nr packed keys %u\n"
1058                "    nr unpacked keys %u\n"
1059                "    floats %zu\n"
1060                "    failed unpacked %zu\n",
1061                f->key_u64s,
1062                f->bits_per_field[0],
1063                f->bits_per_field[1],
1064                f->bits_per_field[2],
1065                f->bits_per_field[3],
1066                f->bits_per_field[4],
1067                b->unpack_fn_len,
1068                b->nr.live_u64s * sizeof(u64),
1069                btree_bytes(c) - sizeof(struct btree_node),
1070                b->nr.live_u64s * 100 / btree_max_u64s(c),
1071                b->sib_u64s[0],
1072                b->sib_u64s[1],
1073                c->btree_foreground_merge_threshold,
1074                b->nr.packed_keys,
1075                b->nr.unpacked_keys,
1076                stats.floats,
1077                stats.failed);
1078 }
1079
1080 void bch2_btree_cache_to_text(struct printbuf *out, struct bch_fs *c)
1081 {
1082         pr_buf(out, "nr nodes:\t\t%u\n", c->btree_cache.used);
1083         pr_buf(out, "nr dirty:\t\t%u\n", atomic_read(&c->btree_cache.dirty));
1084         pr_buf(out, "cannibalize lock:\t%p\n", c->btree_cache.alloc_lock);
1085 }