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                 return ERR_PTR(-EINTR);
 653
 654         b = bch2_btree_node_mem_alloc(c);
 655         if (IS_ERR(b))
 656                 return b;
 657
 658         bkey_copy(&b->key, k);
 659         if (bch2_btree_node_hash_insert(bc, b, level, btree_id)) {
 660                 /* raced with another fill: */
 661
 662                 /* mark as unhashed... */
 663                 b->hash_val = 0;
 664
 665                 mutex_lock(&bc->lock);
 666                 list_add(&b->list, &bc->freeable);
 667                 mutex_unlock(&bc->lock);
 668
 669                 six_unlock_write(&b->c.lock);
 670                 six_unlock_intent(&b->c.lock);
 671                 return NULL;
 672         }
 673
 674         set_btree_node_read_in_flight(b);
 675
 676         six_unlock_write(&b->c.lock);
 677         seq = b->c.lock.state.seq;
 678         six_unlock_intent(&b->c.lock);
 679
 680         /* Unlock before doing IO: */
 681         if (iter && sync)
 682                 bch2_trans_unlock(iter->trans);
 683
 684         bch2_btree_node_read(c, b, sync);
 685
 686         if (!sync)
 687                 return NULL;
 688
 689         /*
 690          * XXX: this will probably always fail because btree_iter_relock()
 691          * currently fails for iterators that aren't pointed at a valid btree
 692          * node
 693          */
 694         if (iter &&
 695             (!bch2_trans_relock(iter->trans) ||
 696              !bch2_btree_iter_relock(iter, _THIS_IP_)))
 697                 return ERR_PTR(-EINTR);
 698
 699         if (!six_relock_type(&b->c.lock, lock_type, seq))
 700                 return ERR_PTR(-EINTR);
 701
 702         return b;
 703 }
 704
 705 static int lock_node_check_fn(struct six_lock *lock, void *p)
 706 {
 707         struct btree *b = container_of(lock, struct btree, c.lock);
 708         const struct bkey_i *k = p;
 709
 710         return b->hash_val == btree_ptr_hash_val(k) ? 0 : -1;
 711 }
 712
 713 static noinline void btree_bad_header(struct bch_fs *c, struct btree *b)
 714 {
 715         char buf1[200], buf2[100], buf3[100];
 716
 717         if (!test_bit(BCH_FS_INITIAL_GC_DONE, &c->flags))
 718                 return;
 719
 720         bch2_bkey_val_to_text(&PBUF(buf1), c, bkey_i_to_s_c(&b->key));
 721         bch2_bpos_to_text(&PBUF(buf3), b->data->max_key);
 722
 723         bch2_fs_inconsistent(c, "btree node header doesn't match ptr\n"
 724                              "btree %s level %u\n"
 725                              "ptr: %s\n"
 726                              "header: btree %s level %llu\n"
 727                              "min %s max %s\n",
 728                              bch2_btree_ids[b->c.btree_id], b->c.level,
 729                              buf1,
 730                              bch2_btree_ids[BTREE_NODE_ID(b->data)],
 731                              BTREE_NODE_LEVEL(b->data),
 732                              buf2, buf3);
 733 }
 734
 735 static inline void btree_check_header(struct bch_fs *c, struct btree *b)
 736 {
 737         if (b->c.btree_id != BTREE_NODE_ID(b->data) ||
 738             b->c.level != BTREE_NODE_LEVEL(b->data) ||
 739             bpos_cmp(b->data->max_key, b->key.k.p) ||
 740             (b->key.k.type == KEY_TYPE_btree_ptr_v2 &&
 741              bpos_cmp(b->data->min_key,
 742                       bkey_i_to_btree_ptr_v2(&b->key)->v.min_key)))
 743                 btree_bad_header(c, b);
 744 }
 745
 746 /**
 747  * bch_btree_node_get - find a btree node in the cache and lock it, reading it
 748  * in from disk if necessary.
 749  *
 750  * If IO is necessary and running under generic_make_request, returns -EAGAIN.
 751  *
 752  * The btree node will have either a read or a write lock held, depending on
 753  * the @write parameter.
 754  */
 755 struct btree *bch2_btree_node_get(struct bch_fs *c, struct btree_iter *iter,
 756                                   const struct bkey_i *k, unsigned level,
 757                                   enum six_lock_type lock_type,
 758                                   unsigned long trace_ip)
 759 {
 760         struct btree_cache *bc = &c->btree_cache;
 761         struct btree *b;
 762         struct bset_tree *t;
 763
 764         EBUG_ON(level >= BTREE_MAX_DEPTH);
 765
 766         b = btree_node_mem_ptr(k);
 767         if (b)
 768                 goto lock_node;
 769 retry:
 770         b = btree_cache_find(bc, k);
 771         if (unlikely(!b)) {
 772                 /*
 773                  * We must have the parent locked to call bch2_btree_node_fill(),
 774                  * else we could read in a btree node from disk that's been
 775                  * freed:
 776                  */
 777                 b = bch2_btree_node_fill(c, iter, k, iter->btree_id,
 778                                          level, lock_type, true);
 779
 780                 /* We raced and found the btree node in the cache */
 781                 if (!b)
 782                         goto retry;
 783
 784                 if (IS_ERR(b))
 785                         return b;
 786         } else {
 787 lock_node:
 788                 /*
 789                  * There's a potential deadlock with splits and insertions into
 790                  * interior nodes we have to avoid:
 791                  *
 792                  * The other thread might be holding an intent lock on the node
 793                  * we want, and they want to update its parent node so they're
 794                  * going to upgrade their intent lock on the parent node to a
 795                  * write lock.
 796                  *
 797                  * But if we're holding a read lock on the parent, and we're
 798                  * trying to get the intent lock they're holding, we deadlock.
 799                  *
 800                  * So to avoid this we drop the read locks on parent nodes when
 801                  * we're starting to take intent locks - and handle the race.
 802                  *
 803                  * The race is that they might be about to free the node we
 804                  * want, and dropping our read lock on the parent node lets them
 805                  * update the parent marking the node we want as freed, and then
 806                  * free it:
 807                  *
 808                  * To guard against this, btree nodes are evicted from the cache
 809                  * when they're freed - and b->hash_val is zeroed out, which we
 810                  * check for after we lock the node.
 811                  *
 812                  * Then, bch2_btree_node_relock() on the parent will fail - because
 813                  * the parent was modified, when the pointer to the node we want
 814                  * was removed - and we'll bail out:
 815                  */
 816                 if (btree_node_read_locked(iter, level + 1))
 817                         btree_node_unlock(iter, level + 1);
 818
 819                 if (!btree_node_lock(b, k->k.p, level, iter, lock_type,
 820                                      lock_node_check_fn, (void *) k, trace_ip)) {
 821                         if (b->hash_val != btree_ptr_hash_val(k))
 822                                 goto retry;
 823                         return ERR_PTR(-EINTR);
 824                 }
 825
 826                 if (unlikely(b->hash_val != btree_ptr_hash_val(k) ||
 827                              b->c.level != level ||
 828                              race_fault())) {
 829                         six_unlock_type(&b->c.lock, lock_type);
 830                         if (bch2_btree_node_relock(iter, level + 1))
 831                                 goto retry;
 832
 833                         trace_trans_restart_btree_node_reused(iter->trans->ip,
 834                                                               trace_ip,
 835                                                               iter->btree_id,
 836                                                               &iter->real_pos);
 837                         return ERR_PTR(-EINTR);
 838                 }
 839         }
 840
 841         if (unlikely(btree_node_read_in_flight(b))) {
 842                 u32 seq = b->c.lock.state.seq;
 843
 844                 six_unlock_type(&b->c.lock, lock_type);
 845                 bch2_trans_unlock(iter->trans);
 846
 847                 bch2_btree_node_wait_on_read(b);
 848
 849                 /*
 850                  * XXX: check if this always fails - btree_iter_relock()
 851                  * currently fails for iterators that aren't pointed at a valid
 852                  * btree node
 853                  */
 854                 if (iter &&
 855                     (!bch2_trans_relock(iter->trans) ||
 856                      !bch2_btree_iter_relock(iter, _THIS_IP_)))
 857                         return ERR_PTR(-EINTR);
 858
 859                 if (!six_relock_type(&b->c.lock, lock_type, seq))
 860                         goto retry;
 861         }
 862
 863         prefetch(b->aux_data);
 864
 865         for_each_bset(b, t) {
 866                 void *p = (u64 *) b->aux_data + t->aux_data_offset;
 867
 868                 prefetch(p + L1_CACHE_BYTES * 0);
 869                 prefetch(p + L1_CACHE_BYTES * 1);
 870                 prefetch(p + L1_CACHE_BYTES * 2);
 871         }
 872
 873         /* avoid atomic set bit if it's not needed: */
 874         if (!btree_node_accessed(b))
 875                 set_btree_node_accessed(b);
 876
 877         if (unlikely(btree_node_read_error(b))) {
 878                 six_unlock_type(&b->c.lock, lock_type);
 879                 return ERR_PTR(-EIO);
 880         }
 881
 882         EBUG_ON(b->c.btree_id != iter->btree_id);
 883         EBUG_ON(BTREE_NODE_LEVEL(b->data) != level);
 884         btree_check_header(c, b);
 885
 886         return b;
 887 }
 888
 889 struct btree *bch2_btree_node_get_noiter(struct bch_fs *c,
 890                                          const struct bkey_i *k,
 891                                          enum btree_id btree_id,
 892                                          unsigned level,
 893                                          bool nofill)
 894 {
 895         struct btree_cache *bc = &c->btree_cache;
 896         struct btree *b;
 897         struct bset_tree *t;
 898         int ret;
 899
 900         EBUG_ON(level >= BTREE_MAX_DEPTH);
 901
 902         b = btree_node_mem_ptr(k);
 903         if (b)
 904                 goto lock_node;
 905 retry:
 906         b = btree_cache_find(bc, k);
 907         if (unlikely(!b)) {
 908                 if (nofill)
 909                         goto out;
 910
 911                 b = bch2_btree_node_fill(c, NULL, k, btree_id,
 912                                          level, SIX_LOCK_read, true);
 913
 914                 /* We raced and found the btree node in the cache */
 915                 if (!b)
 916                         goto retry;
 917
 918                 if (IS_ERR(b) &&
 919                     !bch2_btree_cache_cannibalize_lock(c, NULL))
 920                         goto retry;
 921
 922                 if (IS_ERR(b))
 923                         goto out;
 924         } else {
 925 lock_node:
 926                 ret = six_lock_read(&b->c.lock, lock_node_check_fn, (void *) k);
 927                 if (ret)
 928                         goto retry;
 929
 930                 if (unlikely(b->hash_val != btree_ptr_hash_val(k) ||
 931                              b->c.btree_id != btree_id ||
 932                              b->c.level != level)) {
 933                         six_unlock_read(&b->c.lock);
 934                         goto retry;
 935                 }
 936         }
 937
 938         /* XXX: waiting on IO with btree locks held: */
 939         __bch2_btree_node_wait_on_read(b);
 940
 941         prefetch(b->aux_data);
 942
 943         for_each_bset(b, t) {
 944                 void *p = (u64 *) b->aux_data + t->aux_data_offset;
 945
 946                 prefetch(p + L1_CACHE_BYTES * 0);
 947                 prefetch(p + L1_CACHE_BYTES * 1);
 948                 prefetch(p + L1_CACHE_BYTES * 2);
 949         }
 950
 951         /* avoid atomic set bit if it's not needed: */
 952         if (!btree_node_accessed(b))
 953                 set_btree_node_accessed(b);
 954
 955         if (unlikely(btree_node_read_error(b))) {
 956                 six_unlock_read(&b->c.lock);
 957                 b = ERR_PTR(-EIO);
 958                 goto out;
 959         }
 960
 961         EBUG_ON(b->c.btree_id != btree_id);
 962         EBUG_ON(BTREE_NODE_LEVEL(b->data) != level);
 963         btree_check_header(c, b);
 964 out:
 965         bch2_btree_cache_cannibalize_unlock(c);
 966         return b;
 967 }
 968
 969 void bch2_btree_node_prefetch(struct bch_fs *c, struct btree_iter *iter,
 970                               const struct bkey_i *k,
 971                               enum btree_id btree_id, unsigned level)
 972 {
 973         struct btree_cache *bc = &c->btree_cache;
 974         struct btree *b;
 975
 976         BUG_ON(iter && !btree_node_locked(iter, level + 1));
 977         BUG_ON(level >= BTREE_MAX_DEPTH);
 978
 979         b = btree_cache_find(bc, k);
 980         if (b)
 981                 return;
 982
 983         bch2_btree_node_fill(c, iter, k, btree_id, level, SIX_LOCK_read, false);
 984 }
 985
 986 void bch2_btree_node_evict(struct bch_fs *c, const struct bkey_i *k)
 987 {
 988         struct btree_cache *bc = &c->btree_cache;
 989         struct btree *b;
 990
 991         b = btree_cache_find(bc, k);
 992         if (!b)
 993                 return;
 994 wait_on_io:
 995         /* not allowed to wait on io with btree locks held: */
 996
 997         /* XXX we're called from btree_gc which will be holding other btree
 998          * nodes locked
 999          * */
1000         __bch2_btree_node_wait_on_read(b);
1001         __bch2_btree_node_wait_on_write(b);
1002
1003         six_lock_intent(&b->c.lock, NULL, NULL);
1004         six_lock_write(&b->c.lock, NULL, NULL);
1005
1006         if (btree_node_dirty(b)) {
1007                 __bch2_btree_node_write(c, b, false);
1008                 six_unlock_write(&b->c.lock);
1009                 six_unlock_intent(&b->c.lock);
1010                 goto wait_on_io;
1011         }
1012
1013         BUG_ON(btree_node_dirty(b));
1014
1015         mutex_lock(&bc->lock);
1016         btree_node_data_free(c, b);
1017         bch2_btree_node_hash_remove(bc, b);
1018         mutex_unlock(&bc->lock);
1019
1020         six_unlock_write(&b->c.lock);
1021         six_unlock_intent(&b->c.lock);
1022 }
1023
1024 void bch2_btree_node_to_text(struct printbuf *out, struct bch_fs *c,
1025                              struct btree *b)
1026 {
1027         const struct bkey_format *f = &b->format;
1028         struct bset_stats stats;
1029
1030         memset(&stats, 0, sizeof(stats));
1031
1032         bch2_btree_keys_stats(b, &stats);
1033
1034         pr_buf(out, "l %u ", b->c.level);
1035         bch2_bpos_to_text(out, b->data->min_key);
1036         pr_buf(out, " - ");
1037         bch2_bpos_to_text(out, b->data->max_key);
1038         pr_buf(out, ":\n"
1039                "    ptrs: ");
1040         bch2_val_to_text(out, c, bkey_i_to_s_c(&b->key));
1041
1042         pr_buf(out, "\n"
1043                "    format: u64s %u fields %u %u %u %u %u\n"
1044                "    unpack fn len: %u\n"
1045                "    bytes used %zu/%zu (%zu%% full)\n"
1046                "    sib u64s: %u, %u (merge threshold %u)\n"
1047                "    nr packed keys %u\n"
1048                "    nr unpacked keys %u\n"
1049                "    floats %zu\n"
1050                "    failed unpacked %zu\n",
1051                f->key_u64s,
1052                f->bits_per_field[0],
1053                f->bits_per_field[1],
1054                f->bits_per_field[2],
1055                f->bits_per_field[3],
1056                f->bits_per_field[4],
1057                b->unpack_fn_len,
1058                b->nr.live_u64s * sizeof(u64),
1059                btree_bytes(c) - sizeof(struct btree_node),
1060                b->nr.live_u64s * 100 / btree_max_u64s(c),
1061                b->sib_u64s[0],
1062                b->sib_u64s[1],
1063                c->btree_foreground_merge_threshold,
1064                b->nr.packed_keys,
1065                b->nr.unpacked_keys,
1066                stats.floats,
1067                stats.failed);
1068 }
1069
1070 void bch2_btree_cache_to_text(struct printbuf *out, struct bch_fs *c)
1071 {
1072         pr_buf(out, "nr nodes:\t\t%u\n", c->btree_cache.used);
1073         pr_buf(out, "nr dirty:\t\t%u\n", atomic_read(&c->btree_cache.dirty));
1074         pr_buf(out, "cannibalize lock:\t%p\n", c->btree_cache.alloc_lock);
1075 }