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

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "alloc_foreground.h"
   5 #include "bkey_methods.h"
   6 #include "btree_cache.h"
   7 #include "btree_gc.h"
   8 #include "btree_update.h"
   9 #include "btree_update_interior.h"
  10 #include "btree_io.h"
  11 #include "btree_iter.h"
  12 #include "btree_locking.h"
  13 #include "buckets.h"
  14 #include "extents.h"
  15 #include "journal.h"
  16 #include "journal_reclaim.h"
  17 #include "keylist.h"
  18 #include "replicas.h"
  19 #include "super-io.h"
  20
  21 #include <linux/random.h>
  22 #include <trace/events/bcachefs.h>
  23
  24 static void btree_node_will_make_reachable(struct btree_update *,
  25                                            struct btree *);
  26 static void btree_update_drop_new_node(struct bch_fs *, struct btree *);
  27
  28 /* Debug code: */
  29
  30 static void btree_node_interior_verify(struct btree *b)
  31 {
  32         struct btree_node_iter iter;
  33         struct bkey_packed *k;
  34
  35         BUG_ON(!b->level);
  36
  37         bch2_btree_node_iter_init(&iter, b, &b->key.k.p);
  38 #if 1
  39         BUG_ON(!(k = bch2_btree_node_iter_peek(&iter, b)) ||
  40                bkey_cmp_left_packed(b, k, &b->key.k.p));
  41
  42         BUG_ON((bch2_btree_node_iter_advance(&iter, b),
  43                 !bch2_btree_node_iter_end(&iter)));
  44 #else
  45         const char *msg;
  46
  47         msg = "not found";
  48         k = bch2_btree_node_iter_peek(&iter, b);
  49         if (!k)
  50                 goto err;
  51
  52         msg = "isn't what it should be";
  53         if (bkey_cmp_left_packed(b, k, &b->key.k.p))
  54                 goto err;
  55
  56         bch2_btree_node_iter_advance(&iter, b);
  57
  58         msg = "isn't last key";
  59         if (!bch2_btree_node_iter_end(&iter))
  60                 goto err;
  61         return;
  62 err:
  63         bch2_dump_btree_node(b);
  64         printk(KERN_ERR "last key %llu:%llu %s\n", b->key.k.p.inode,
  65                b->key.k.p.offset, msg);
  66         BUG();
  67 #endif
  68 }
  69
  70 /* Calculate ideal packed bkey format for new btree nodes: */
  71
  72 void __bch2_btree_calc_format(struct bkey_format_state *s, struct btree *b)
  73 {
  74         struct bkey_packed *k;
  75         struct bset_tree *t;
  76         struct bkey uk;
  77
  78         bch2_bkey_format_add_pos(s, b->data->min_key);
  79
  80         for_each_bset(b, t)
  81                 bset_tree_for_each_key(b, t, k)
  82                         if (!bkey_whiteout(k)) {
  83                                 uk = bkey_unpack_key(b, k);
  84                                 bch2_bkey_format_add_key(s, &uk);
  85                         }
  86 }
  87
  88 static struct bkey_format bch2_btree_calc_format(struct btree *b)
  89 {
  90         struct bkey_format_state s;
  91
  92         bch2_bkey_format_init(&s);
  93         __bch2_btree_calc_format(&s, b);
  94
  95         return bch2_bkey_format_done(&s);
  96 }
  97
  98 static size_t btree_node_u64s_with_format(struct btree *b,
  99                                           struct bkey_format *new_f)
 100 {
 101         struct bkey_format *old_f = &b->format;
 102
 103         /* stupid integer promotion rules */
 104         ssize_t delta =
 105             (((int) new_f->key_u64s - old_f->key_u64s) *
 106              (int) b->nr.packed_keys) +
 107             (((int) new_f->key_u64s - BKEY_U64s) *
 108              (int) b->nr.unpacked_keys);
 109
 110         BUG_ON(delta + b->nr.live_u64s < 0);
 111
 112         return b->nr.live_u64s + delta;
 113 }
 114
 115 /**
 116  * btree_node_format_fits - check if we could rewrite node with a new format
 117  *
 118  * This assumes all keys can pack with the new format -- it just checks if
 119  * the re-packed keys would fit inside the node itself.
 120  */
 121 bool bch2_btree_node_format_fits(struct bch_fs *c, struct btree *b,
 122                                  struct bkey_format *new_f)
 123 {
 124         size_t u64s = btree_node_u64s_with_format(b, new_f);
 125
 126         return __vstruct_bytes(struct btree_node, u64s) < btree_bytes(c);
 127 }
 128
 129 /* Btree node freeing/allocation: */
 130
 131 static bool btree_key_matches(struct bch_fs *c,
 132                               struct bkey_s_c l,
 133                               struct bkey_s_c r)
 134 {
 135         struct bkey_ptrs_c ptrs1 = bch2_bkey_ptrs_c(l);
 136         struct bkey_ptrs_c ptrs2 = bch2_bkey_ptrs_c(r);
 137         const struct bch_extent_ptr *ptr1, *ptr2;
 138
 139         bkey_for_each_ptr(ptrs1, ptr1)
 140                 bkey_for_each_ptr(ptrs2, ptr2)
 141                         if (ptr1->dev == ptr2->dev &&
 142                             ptr1->gen == ptr2->gen &&
 143                             ptr1->offset == ptr2->offset)
 144                                 return true;
 145
 146         return false;
 147 }
 148
 149 /*
 150  * We're doing the index update that makes @b unreachable, update stuff to
 151  * reflect that:
 152  *
 153  * Must be called _before_ btree_update_updated_root() or
 154  * btree_update_updated_node:
 155  */
 156 static void bch2_btree_node_free_index(struct btree_update *as, struct btree *b,
 157                                        struct bkey_s_c k,
 158                                        struct bch_fs_usage *stats)
 159 {
 160         struct bch_fs *c = as->c;
 161         struct pending_btree_node_free *d;
 162
 163         for (d = as->pending; d < as->pending + as->nr_pending; d++)
 164                 if (!bkey_cmp(k.k->p, d->key.k.p) &&
 165                     btree_key_matches(c, k, bkey_i_to_s_c(&d->key)))
 166                         goto found;
 167         BUG();
 168 found:
 169         BUG_ON(d->index_update_done);
 170         d->index_update_done = true;
 171
 172         /*
 173          * We're dropping @k from the btree, but it's still live until the
 174          * index update is persistent so we need to keep a reference around for
 175          * mark and sweep to find - that's primarily what the
 176          * btree_node_pending_free list is for.
 177          *
 178          * So here (when we set index_update_done = true), we're moving an
 179          * existing reference to a different part of the larger "gc keyspace" -
 180          * and the new position comes after the old position, since GC marks
 181          * the pending free list after it walks the btree.
 182          *
 183          * If we move the reference while mark and sweep is _between_ the old
 184          * and the new position, mark and sweep will see the reference twice
 185          * and it'll get double accounted - so check for that here and subtract
 186          * to cancel out one of mark and sweep's markings if necessary:
 187          */
 188
 189         if (gc_pos_cmp(c->gc_pos, b
 190                        ? gc_pos_btree_node(b)
 191                        : gc_pos_btree_root(as->btree_id)) >= 0 &&
 192             gc_pos_cmp(c->gc_pos, gc_phase(GC_PHASE_PENDING_DELETE)) < 0)
 193                 bch2_mark_key_locked(c, bkey_i_to_s_c(&d->key),
 194                               0, 0, NULL, 0,
 195                               BTREE_TRIGGER_OVERWRITE|
 196                               BTREE_TRIGGER_GC);
 197 }
 198
 199 static void __btree_node_free(struct bch_fs *c, struct btree *b)
 200 {
 201         trace_btree_node_free(c, b);
 202
 203         BUG_ON(btree_node_dirty(b));
 204         BUG_ON(btree_node_need_write(b));
 205         BUG_ON(b == btree_node_root(c, b));
 206         BUG_ON(b->ob.nr);
 207         BUG_ON(!list_empty(&b->write_blocked));
 208         BUG_ON(b->will_make_reachable);
 209
 210         clear_btree_node_noevict(b);
 211
 212         bch2_btree_node_hash_remove(&c->btree_cache, b);
 213
 214         mutex_lock(&c->btree_cache.lock);
 215         list_move(&b->list, &c->btree_cache.freeable);
 216         mutex_unlock(&c->btree_cache.lock);
 217 }
 218
 219 void bch2_btree_node_free_never_inserted(struct bch_fs *c, struct btree *b)
 220 {
 221         struct open_buckets ob = b->ob;
 222
 223         btree_update_drop_new_node(c, b);
 224
 225         b->ob.nr = 0;
 226
 227         clear_btree_node_dirty(b);
 228
 229         btree_node_lock_type(c, b, SIX_LOCK_write);
 230         __btree_node_free(c, b);
 231         six_unlock_write(&b->lock);
 232
 233         bch2_open_buckets_put(c, &ob);
 234 }
 235
 236 void bch2_btree_node_free_inmem(struct bch_fs *c, struct btree *b,
 237                                 struct btree_iter *iter)
 238 {
 239         struct btree_iter *linked;
 240
 241         trans_for_each_iter(iter->trans, linked)
 242                 BUG_ON(linked->l[b->level].b == b);
 243
 244         /*
 245          * Is this a node that isn't reachable on disk yet?
 246          *
 247          * Nodes that aren't reachable yet have writes blocked until they're
 248          * reachable - now that we've cancelled any pending writes and moved
 249          * things waiting on that write to wait on this update, we can drop this
 250          * node from the list of nodes that the other update is making
 251          * reachable, prior to freeing it:
 252          */
 253         btree_update_drop_new_node(c, b);
 254
 255         six_lock_write(&b->lock);
 256         __btree_node_free(c, b);
 257         six_unlock_write(&b->lock);
 258         six_unlock_intent(&b->lock);
 259 }
 260
 261 static void bch2_btree_node_free_ondisk(struct bch_fs *c,
 262                         struct pending_btree_node_free *pending,
 263                         u64 journal_seq)
 264 {
 265         BUG_ON(!pending->index_update_done);
 266
 267         bch2_mark_key(c, bkey_i_to_s_c(&pending->key),
 268                       0, 0, NULL, journal_seq, BTREE_TRIGGER_OVERWRITE);
 269
 270         if (gc_visited(c, gc_phase(GC_PHASE_PENDING_DELETE)))
 271                 bch2_mark_key(c, bkey_i_to_s_c(&pending->key),
 272                               0, 0, NULL, journal_seq,
 273                               BTREE_TRIGGER_OVERWRITE|
 274                               BTREE_TRIGGER_GC);
 275 }
 276
 277 static struct btree *__bch2_btree_node_alloc(struct bch_fs *c,
 278                                              struct disk_reservation *res,
 279                                              struct closure *cl,
 280                                              unsigned flags)
 281 {
 282         struct write_point *wp;
 283         struct btree *b;
 284         BKEY_PADDED(k) tmp;
 285         struct open_buckets ob = { .nr = 0 };
 286         struct bch_devs_list devs_have = (struct bch_devs_list) { 0 };
 287         unsigned nr_reserve;
 288         enum alloc_reserve alloc_reserve;
 289
 290         if (flags & BTREE_INSERT_USE_ALLOC_RESERVE) {
 291                 nr_reserve      = 0;
 292                 alloc_reserve   = RESERVE_ALLOC;
 293         } else if (flags & BTREE_INSERT_USE_RESERVE) {
 294                 nr_reserve      = BTREE_NODE_RESERVE / 2;
 295                 alloc_reserve   = RESERVE_BTREE;
 296         } else {
 297                 nr_reserve      = BTREE_NODE_RESERVE;
 298                 alloc_reserve   = RESERVE_NONE;
 299         }
 300
 301         mutex_lock(&c->btree_reserve_cache_lock);
 302         if (c->btree_reserve_cache_nr > nr_reserve) {
 303                 struct btree_alloc *a =
 304                         &c->btree_reserve_cache[--c->btree_reserve_cache_nr];
 305
 306                 ob = a->ob;
 307                 bkey_copy(&tmp.k, &a->k);
 308                 mutex_unlock(&c->btree_reserve_cache_lock);
 309                 goto mem_alloc;
 310         }
 311         mutex_unlock(&c->btree_reserve_cache_lock);
 312
 313 retry:
 314         wp = bch2_alloc_sectors_start(c, c->opts.foreground_target, 0,
 315                                       writepoint_ptr(&c->btree_write_point),
 316                                       &devs_have,
 317                                       res->nr_replicas,
 318                                       c->opts.metadata_replicas_required,
 319                                       alloc_reserve, 0, cl);
 320         if (IS_ERR(wp))
 321                 return ERR_CAST(wp);
 322
 323         if (wp->sectors_free < c->opts.btree_node_size) {
 324                 struct open_bucket *ob;
 325                 unsigned i;
 326
 327                 open_bucket_for_each(c, &wp->ptrs, ob, i)
 328                         if (ob->sectors_free < c->opts.btree_node_size)
 329                                 ob->sectors_free = 0;
 330
 331                 bch2_alloc_sectors_done(c, wp);
 332                 goto retry;
 333         }
 334
 335         if (c->sb.features & (1ULL << BCH_FEATURE_btree_ptr_v2))
 336                 bkey_btree_ptr_v2_init(&tmp.k);
 337         else
 338                 bkey_btree_ptr_init(&tmp.k);
 339
 340         bch2_alloc_sectors_append_ptrs(c, wp, &tmp.k, c->opts.btree_node_size);
 341
 342         bch2_open_bucket_get(c, wp, &ob);
 343         bch2_alloc_sectors_done(c, wp);
 344 mem_alloc:
 345         b = bch2_btree_node_mem_alloc(c);
 346
 347         /* we hold cannibalize_lock: */
 348         BUG_ON(IS_ERR(b));
 349         BUG_ON(b->ob.nr);
 350
 351         bkey_copy(&b->key, &tmp.k);
 352         b->ob = ob;
 353
 354         return b;
 355 }
 356
 357 static struct btree *bch2_btree_node_alloc(struct btree_update *as, unsigned level)
 358 {
 359         struct bch_fs *c = as->c;
 360         struct btree *b;
 361         int ret;
 362
 363         BUG_ON(level >= BTREE_MAX_DEPTH);
 364         BUG_ON(!as->reserve->nr);
 365
 366         b = as->reserve->b[--as->reserve->nr];
 367
 368         set_btree_node_accessed(b);
 369         set_btree_node_dirty(b);
 370         set_btree_node_need_write(b);
 371
 372         bch2_bset_init_first(b, &b->data->keys);
 373         b->level        = level;
 374         b->btree_id     = as->btree_id;
 375
 376         memset(&b->nr, 0, sizeof(b->nr));
 377         b->data->magic = cpu_to_le64(bset_magic(c));
 378         b->data->flags = 0;
 379         SET_BTREE_NODE_ID(b->data, as->btree_id);
 380         SET_BTREE_NODE_LEVEL(b->data, level);
 381         b->data->ptr = bch2_bkey_ptrs_c(bkey_i_to_s_c(&b->key)).start->ptr;
 382
 383         if (b->key.k.type == KEY_TYPE_btree_ptr_v2) {
 384                 struct bkey_i_btree_ptr_v2 *bp = bkey_i_to_btree_ptr_v2(&b->key);
 385
 386                 bp->v.mem_ptr           = 0;
 387                 bp->v.seq               = b->data->keys.seq;
 388                 bp->v.sectors_written   = 0;
 389                 bp->v.sectors           = cpu_to_le16(c->opts.btree_node_size);
 390         }
 391
 392         if (c->sb.features & (1ULL << BCH_FEATURE_new_extent_overwrite))
 393                 SET_BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data, true);
 394
 395         if (btree_node_is_extents(b) &&
 396             !BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data))
 397                 set_btree_node_old_extent_overwrite(b);
 398
 399         bch2_btree_build_aux_trees(b);
 400
 401         btree_node_will_make_reachable(as, b);
 402
 403         ret = bch2_btree_node_hash_insert(&c->btree_cache, b, level, as->btree_id);
 404         BUG_ON(ret);
 405
 406         trace_btree_node_alloc(c, b);
 407         return b;
 408 }
 409
 410 static void btree_set_min(struct btree *b, struct bpos pos)
 411 {
 412         if (b->key.k.type == KEY_TYPE_btree_ptr_v2)
 413                 bkey_i_to_btree_ptr_v2(&b->key)->v.min_key = pos;
 414         b->data->min_key = pos;
 415 }
 416
 417 static void btree_set_max(struct btree *b, struct bpos pos)
 418 {
 419         b->key.k.p = pos;
 420         b->data->max_key = pos;
 421 }
 422
 423 struct btree *__bch2_btree_node_alloc_replacement(struct btree_update *as,
 424                                                   struct btree *b,
 425                                                   struct bkey_format format)
 426 {
 427         struct btree *n;
 428
 429         n = bch2_btree_node_alloc(as, b->level);
 430
 431         SET_BTREE_NODE_SEQ(n->data, BTREE_NODE_SEQ(b->data) + 1);
 432
 433         btree_set_min(n, b->data->min_key);
 434         btree_set_max(n, b->data->max_key);
 435
 436         n->data->format         = format;
 437         btree_node_set_format(n, format);
 438
 439         bch2_btree_sort_into(as->c, n, b);
 440
 441         btree_node_reset_sib_u64s(n);
 442
 443         n->key.k.p = b->key.k.p;
 444         return n;
 445 }
 446
 447 static struct btree *bch2_btree_node_alloc_replacement(struct btree_update *as,
 448                                                        struct btree *b)
 449 {
 450         struct bkey_format new_f = bch2_btree_calc_format(b);
 451
 452         /*
 453          * The keys might expand with the new format - if they wouldn't fit in
 454          * the btree node anymore, use the old format for now:
 455          */
 456         if (!bch2_btree_node_format_fits(as->c, b, &new_f))
 457                 new_f = b->format;
 458
 459         return __bch2_btree_node_alloc_replacement(as, b, new_f);
 460 }
 461
 462 static struct btree *__btree_root_alloc(struct btree_update *as, unsigned level)
 463 {
 464         struct btree *b = bch2_btree_node_alloc(as, level);
 465
 466         btree_set_min(b, POS_MIN);
 467         btree_set_max(b, POS_MAX);
 468         b->data->format = bch2_btree_calc_format(b);
 469
 470         btree_node_set_format(b, b->data->format);
 471         bch2_btree_build_aux_trees(b);
 472
 473         six_unlock_write(&b->lock);
 474
 475         return b;
 476 }
 477
 478 static void bch2_btree_reserve_put(struct bch_fs *c, struct btree_reserve *reserve)
 479 {
 480         bch2_disk_reservation_put(c, &reserve->disk_res);
 481
 482         mutex_lock(&c->btree_reserve_cache_lock);
 483
 484         while (reserve->nr) {
 485                 struct btree *b = reserve->b[--reserve->nr];
 486
 487                 six_unlock_write(&b->lock);
 488
 489                 if (c->btree_reserve_cache_nr <
 490                     ARRAY_SIZE(c->btree_reserve_cache)) {
 491                         struct btree_alloc *a =
 492                                 &c->btree_reserve_cache[c->btree_reserve_cache_nr++];
 493
 494                         a->ob = b->ob;
 495                         b->ob.nr = 0;
 496                         bkey_copy(&a->k, &b->key);
 497                 } else {
 498                         bch2_open_buckets_put(c, &b->ob);
 499                 }
 500
 501                 btree_node_lock_type(c, b, SIX_LOCK_write);
 502                 __btree_node_free(c, b);
 503                 six_unlock_write(&b->lock);
 504
 505                 six_unlock_intent(&b->lock);
 506         }
 507
 508         mutex_unlock(&c->btree_reserve_cache_lock);
 509
 510         mempool_free(reserve, &c->btree_reserve_pool);
 511 }
 512
 513 static struct btree_reserve *bch2_btree_reserve_get(struct bch_fs *c,
 514                                                     unsigned nr_nodes,
 515                                                     unsigned flags,
 516                                                     struct closure *cl)
 517 {
 518         struct btree_reserve *reserve;
 519         struct btree *b;
 520         struct disk_reservation disk_res = { 0, 0 };
 521         unsigned sectors = nr_nodes * c->opts.btree_node_size;
 522         int ret, disk_res_flags = 0;
 523
 524         if (flags & BTREE_INSERT_NOFAIL)
 525                 disk_res_flags |= BCH_DISK_RESERVATION_NOFAIL;
 526
 527         /*
 528          * This check isn't necessary for correctness - it's just to potentially
 529          * prevent us from doing a lot of work that'll end up being wasted:
 530          */
 531         ret = bch2_journal_error(&c->journal);
 532         if (ret)
 533                 return ERR_PTR(ret);
 534
 535         if (bch2_disk_reservation_get(c, &disk_res, sectors,
 536                                       c->opts.metadata_replicas,
 537                                       disk_res_flags))
 538                 return ERR_PTR(-ENOSPC);
 539
 540         BUG_ON(nr_nodes > BTREE_RESERVE_MAX);
 541
 542         /*
 543          * Protects reaping from the btree node cache and using the btree node
 544          * open bucket reserve:
 545          */
 546         ret = bch2_btree_cache_cannibalize_lock(c, cl);
 547         if (ret) {
 548                 bch2_disk_reservation_put(c, &disk_res);
 549                 return ERR_PTR(ret);
 550         }
 551
 552         reserve = mempool_alloc(&c->btree_reserve_pool, GFP_NOIO);
 553
 554         reserve->disk_res = disk_res;
 555         reserve->nr = 0;
 556
 557         while (reserve->nr < nr_nodes) {
 558                 b = __bch2_btree_node_alloc(c, &disk_res,
 559                                             flags & BTREE_INSERT_NOWAIT
 560                                             ? NULL : cl, flags);
 561                 if (IS_ERR(b)) {
 562                         ret = PTR_ERR(b);
 563                         goto err_free;
 564                 }
 565
 566                 ret = bch2_mark_bkey_replicas(c, bkey_i_to_s_c(&b->key));
 567                 if (ret)
 568                         goto err_free;
 569
 570                 reserve->b[reserve->nr++] = b;
 571         }
 572
 573         bch2_btree_cache_cannibalize_unlock(c);
 574         return reserve;
 575 err_free:
 576         bch2_btree_reserve_put(c, reserve);
 577         bch2_btree_cache_cannibalize_unlock(c);
 578         trace_btree_reserve_get_fail(c, nr_nodes, cl);
 579         return ERR_PTR(ret);
 580 }
 581
 582 /* Asynchronous interior node update machinery */
 583
 584 static void __bch2_btree_update_free(struct btree_update *as)
 585 {
 586         struct bch_fs *c = as->c;
 587
 588         bch2_journal_preres_put(&c->journal, &as->journal_preres);
 589
 590         bch2_journal_pin_drop(&c->journal, &as->journal);
 591         bch2_journal_pin_flush(&c->journal, &as->journal);
 592
 593         BUG_ON((as->nr_new_nodes || as->nr_pending) &&
 594                !bch2_journal_error(&c->journal));;
 595
 596         if (as->reserve)
 597                 bch2_btree_reserve_put(c, as->reserve);
 598
 599         list_del(&as->list);
 600
 601         closure_debug_destroy(&as->cl);
 602         mempool_free(as, &c->btree_interior_update_pool);
 603
 604         closure_wake_up(&c->btree_interior_update_wait);
 605 }
 606
 607 static void bch2_btree_update_free(struct btree_update *as)
 608 {
 609         struct bch_fs *c = as->c;
 610
 611         mutex_lock(&c->btree_interior_update_lock);
 612         __bch2_btree_update_free(as);
 613         mutex_unlock(&c->btree_interior_update_lock);
 614 }
 615
 616 static void btree_update_nodes_reachable(struct btree_update *as, u64 seq)
 617 {
 618         struct bch_fs *c = as->c;
 619
 620         while (as->nr_new_nodes) {
 621                 struct btree *b = as->new_nodes[--as->nr_new_nodes];
 622
 623                 BUG_ON(b->will_make_reachable != (unsigned long) as);
 624                 b->will_make_reachable = 0;
 625
 626                 /*
 627                  * b->will_make_reachable prevented it from being written, so
 628                  * write it now if it needs to be written:
 629                  */
 630                 btree_node_lock_type(c, b, SIX_LOCK_read);
 631                 bch2_btree_node_write_cond(c, b, btree_node_need_write(b));
 632                 six_unlock_read(&b->lock);
 633         }
 634
 635         while (as->nr_pending)
 636                 bch2_btree_node_free_ondisk(c, &as->pending[--as->nr_pending],
 637                                             seq);
 638 }
 639
 640 static void btree_update_nodes_written(struct closure *cl)
 641 {
 642         struct btree_update *as = container_of(cl, struct btree_update, cl);
 643         struct journal_res res = { 0 };
 644         struct bch_fs *c = as->c;
 645         struct btree *b;
 646         struct bset *i;
 647         struct bkey_i *k;
 648         unsigned journal_u64s = 0;
 649         int ret;
 650
 651         /*
 652          * We did an update to a parent node where the pointers we added pointed
 653          * to child nodes that weren't written yet: now, the child nodes have
 654          * been written so we can write out the update to the interior node.
 655          */
 656         mutex_lock(&c->btree_interior_update_lock);
 657         as->nodes_written = true;
 658 again:
 659         as = list_first_entry_or_null(&c->btree_interior_updates_unwritten,
 660                                       struct btree_update, unwritten_list);
 661         if (!as || !as->nodes_written) {
 662                 mutex_unlock(&c->btree_interior_update_lock);
 663                 return;
 664         }
 665
 666         b = as->b;
 667         if (b && !six_trylock_intent(&b->lock)) {
 668                 mutex_unlock(&c->btree_interior_update_lock);
 669                 btree_node_lock_type(c, b, SIX_LOCK_intent);
 670                 six_unlock_intent(&b->lock);
 671                 mutex_lock(&c->btree_interior_update_lock);
 672                 goto again;
 673         }
 674
 675         list_del(&as->unwritten_list);
 676
 677         journal_u64s = 0;
 678
 679         if (as->mode != BTREE_INTERIOR_UPDATING_ROOT)
 680                 for_each_keylist_key(&as->parent_keys, k)
 681                         journal_u64s += jset_u64s(k->k.u64s);
 682
 683         ret = bch2_journal_res_get(&c->journal, &res, journal_u64s,
 684                                    JOURNAL_RES_GET_RESERVED);
 685         if (ret) {
 686                 BUG_ON(!bch2_journal_error(&c->journal));
 687                 /* can't unblock btree writes */
 688                 goto free_update;
 689         }
 690
 691         if (as->mode != BTREE_INTERIOR_UPDATING_ROOT)
 692                 for_each_keylist_key(&as->parent_keys, k)
 693                         bch2_journal_add_entry(&c->journal, &res,
 694                                                BCH_JSET_ENTRY_btree_keys,
 695                                                as->btree_id,
 696                                                as->level,
 697                                                k, k->k.u64s);
 698
 699         switch (as->mode) {
 700         case BTREE_INTERIOR_NO_UPDATE:
 701                 BUG();
 702         case BTREE_INTERIOR_UPDATING_NODE:
 703                 /* @b is the node we did the final insert into: */
 704                 BUG_ON(!res.ref);
 705
 706                 six_lock_write(&b->lock);
 707                 list_del(&as->write_blocked_list);
 708
 709                 i = btree_bset_last(b);
 710                 i->journal_seq = cpu_to_le64(
 711                         max(res.seq,
 712                             le64_to_cpu(i->journal_seq)));
 713
 714                 bch2_btree_add_journal_pin(c, b, res.seq);
 715                 six_unlock_write(&b->lock);
 716                 break;
 717
 718         case BTREE_INTERIOR_UPDATING_AS:
 719                 BUG_ON(b);
 720                 break;
 721
 722         case BTREE_INTERIOR_UPDATING_ROOT: {
 723                 struct btree_root *r = &c->btree_roots[as->btree_id];
 724
 725                 BUG_ON(b);
 726
 727                 mutex_lock(&c->btree_root_lock);
 728                 bkey_copy(&r->key, as->parent_keys.keys);
 729                 r->level = as->level;
 730                 r->alive = true;
 731                 c->btree_roots_dirty = true;
 732                 mutex_unlock(&c->btree_root_lock);
 733                 break;
 734         }
 735         }
 736
 737         bch2_journal_pin_drop(&c->journal, &as->journal);
 738
 739         bch2_journal_res_put(&c->journal, &res);
 740         bch2_journal_preres_put(&c->journal, &as->journal_preres);
 741
 742         /* Do btree write after dropping journal res: */
 743         if (b) {
 744                 /*
 745                  * b->write_blocked prevented it from being written, so
 746                  * write it now if it needs to be written:
 747                  */
 748                 btree_node_write_if_need(c, b, SIX_LOCK_intent);
 749                 six_unlock_intent(&b->lock);
 750         }
 751
 752         btree_update_nodes_reachable(as, res.seq);
 753 free_update:
 754         __bch2_btree_update_free(as);
 755         /*
 756          * for flush_held_btree_writes() waiting on updates to flush or
 757          * nodes to be writeable:
 758          */
 759         closure_wake_up(&c->btree_interior_update_wait);
 760         goto again;
 761 }
 762
 763 /*
 764  * We're updating @b with pointers to nodes that haven't finished writing yet:
 765  * block @b from being written until @as completes
 766  */
 767 static void btree_update_updated_node(struct btree_update *as, struct btree *b)
 768 {
 769         struct bch_fs *c = as->c;
 770
 771         mutex_lock(&c->btree_interior_update_lock);
 772         list_add_tail(&as->unwritten_list, &c->btree_interior_updates_unwritten);
 773
 774         BUG_ON(as->mode != BTREE_INTERIOR_NO_UPDATE);
 775         BUG_ON(!btree_node_dirty(b));
 776
 777         as->mode        = BTREE_INTERIOR_UPDATING_NODE;
 778         as->b           = b;
 779         as->level       = b->level;
 780         list_add(&as->write_blocked_list, &b->write_blocked);
 781
 782         mutex_unlock(&c->btree_interior_update_lock);
 783 }
 784
 785 static void btree_update_reparent(struct btree_update *as,
 786                                   struct btree_update *child)
 787 {
 788         struct bch_fs *c = as->c;
 789
 790         lockdep_assert_held(&c->btree_interior_update_lock);
 791
 792         child->b = NULL;
 793         child->mode = BTREE_INTERIOR_UPDATING_AS;
 794
 795         /*
 796          * When we write a new btree root, we have to drop our journal pin
 797          * _before_ the new nodes are technically reachable; see
 798          * btree_update_nodes_written().
 799          *
 800          * This goes for journal pins that are recursively blocked on us - so,
 801          * just transfer the journal pin to the new interior update so
 802          * btree_update_nodes_written() can drop it.
 803          */
 804         bch2_journal_pin_copy(&c->journal, &as->journal, &child->journal, NULL);
 805         bch2_journal_pin_drop(&c->journal, &child->journal);
 806 }
 807
 808 static void btree_update_updated_root(struct btree_update *as, struct btree *b)
 809 {
 810         struct bch_fs *c = as->c;
 811
 812         BUG_ON(as->mode != BTREE_INTERIOR_NO_UPDATE);
 813         BUG_ON(!bch2_keylist_empty(&as->parent_keys));
 814
 815         mutex_lock(&c->btree_interior_update_lock);
 816         list_add_tail(&as->unwritten_list, &c->btree_interior_updates_unwritten);
 817
 818         as->mode        = BTREE_INTERIOR_UPDATING_ROOT;
 819         as->level       = b->level;
 820         bch2_keylist_add(&as->parent_keys, &b->key);
 821         mutex_unlock(&c->btree_interior_update_lock);
 822 }
 823
 824 static void btree_node_will_make_reachable(struct btree_update *as,
 825                                            struct btree *b)
 826 {
 827         struct bch_fs *c = as->c;
 828
 829         mutex_lock(&c->btree_interior_update_lock);
 830         BUG_ON(as->nr_new_nodes >= ARRAY_SIZE(as->new_nodes));
 831         BUG_ON(b->will_make_reachable);
 832
 833         as->new_nodes[as->nr_new_nodes++] = b;
 834         b->will_make_reachable = 1UL|(unsigned long) as;
 835
 836         closure_get(&as->cl);
 837         mutex_unlock(&c->btree_interior_update_lock);
 838 }
 839
 840 static void btree_update_drop_new_node(struct bch_fs *c, struct btree *b)
 841 {
 842         struct btree_update *as;
 843         unsigned long v;
 844         unsigned i;
 845
 846         mutex_lock(&c->btree_interior_update_lock);
 847         v = xchg(&b->will_make_reachable, 0);
 848         as = (struct btree_update *) (v & ~1UL);
 849
 850         if (!as) {
 851                 mutex_unlock(&c->btree_interior_update_lock);
 852                 return;
 853         }
 854
 855         for (i = 0; i < as->nr_new_nodes; i++)
 856                 if (as->new_nodes[i] == b)
 857                         goto found;
 858
 859         BUG();
 860 found:
 861         array_remove_item(as->new_nodes, as->nr_new_nodes, i);
 862         mutex_unlock(&c->btree_interior_update_lock);
 863
 864         if (v & 1)
 865                 closure_put(&as->cl);
 866 }
 867
 868 static void btree_interior_update_add_node_reference(struct btree_update *as,
 869                                                      struct btree *b)
 870 {
 871         struct bch_fs *c = as->c;
 872         struct pending_btree_node_free *d;
 873
 874         mutex_lock(&c->btree_interior_update_lock);
 875
 876         /* Add this node to the list of nodes being freed: */
 877         BUG_ON(as->nr_pending >= ARRAY_SIZE(as->pending));
 878
 879         d = &as->pending[as->nr_pending++];
 880         d->index_update_done    = false;
 881         d->seq                  = b->data->keys.seq;
 882         d->btree_id             = b->btree_id;
 883         d->level                = b->level;
 884         bkey_copy(&d->key, &b->key);
 885
 886         mutex_unlock(&c->btree_interior_update_lock);
 887 }
 888
 889 /*
 890  * @b is being split/rewritten: it may have pointers to not-yet-written btree
 891  * nodes and thus outstanding btree_updates - redirect @b's
 892  * btree_updates to point to this btree_update:
 893  */
 894 void bch2_btree_interior_update_will_free_node(struct btree_update *as,
 895                                                struct btree *b)
 896 {
 897         struct bch_fs *c = as->c;
 898         struct btree_update *p, *n;
 899         struct btree_write *w;
 900
 901         set_btree_node_dying(b);
 902
 903         if (btree_node_fake(b))
 904                 return;
 905
 906         btree_interior_update_add_node_reference(as, b);
 907
 908         mutex_lock(&c->btree_interior_update_lock);
 909
 910         /*
 911          * Does this node have any btree_update operations preventing
 912          * it from being written?
 913          *
 914          * If so, redirect them to point to this btree_update: we can
 915          * write out our new nodes, but we won't make them visible until those
 916          * operations complete
 917          */
 918         list_for_each_entry_safe(p, n, &b->write_blocked, write_blocked_list) {
 919                 list_del(&p->write_blocked_list);
 920                 btree_update_reparent(as, p);
 921
 922                 /*
 923                  * for flush_held_btree_writes() waiting on updates to flush or
 924                  * nodes to be writeable:
 925                  */
 926                 closure_wake_up(&c->btree_interior_update_wait);
 927         }
 928
 929         clear_btree_node_dirty(b);
 930         clear_btree_node_need_write(b);
 931
 932         /*
 933          * Does this node have unwritten data that has a pin on the journal?
 934          *
 935          * If so, transfer that pin to the btree_update operation -
 936          * note that if we're freeing multiple nodes, we only need to keep the
 937          * oldest pin of any of the nodes we're freeing. We'll release the pin
 938          * when the new nodes are persistent and reachable on disk:
 939          */
 940         w = btree_current_write(b);
 941         bch2_journal_pin_copy(&c->journal, &as->journal, &w->journal, NULL);
 942         bch2_journal_pin_drop(&c->journal, &w->journal);
 943
 944         w = btree_prev_write(b);
 945         bch2_journal_pin_copy(&c->journal, &as->journal, &w->journal, NULL);
 946         bch2_journal_pin_drop(&c->journal, &w->journal);
 947
 948         mutex_unlock(&c->btree_interior_update_lock);
 949 }
 950
 951 void bch2_btree_update_done(struct btree_update *as)
 952 {
 953         BUG_ON(as->mode == BTREE_INTERIOR_NO_UPDATE);
 954
 955         bch2_btree_reserve_put(as->c, as->reserve);
 956         as->reserve = NULL;
 957
 958         continue_at(&as->cl, btree_update_nodes_written, system_freezable_wq);
 959 }
 960
 961 struct btree_update *
 962 bch2_btree_update_start(struct bch_fs *c, enum btree_id id,
 963                         unsigned nr_nodes, unsigned flags,
 964                         struct closure *cl)
 965 {
 966         struct btree_reserve *reserve;
 967         struct btree_update *as;
 968         int ret;
 969
 970         reserve = bch2_btree_reserve_get(c, nr_nodes, flags, cl);
 971         if (IS_ERR(reserve))
 972                 return ERR_CAST(reserve);
 973
 974         as = mempool_alloc(&c->btree_interior_update_pool, GFP_NOIO);
 975         memset(as, 0, sizeof(*as));
 976         closure_init(&as->cl, NULL);
 977         as->c           = c;
 978         as->mode        = BTREE_INTERIOR_NO_UPDATE;
 979         as->btree_id    = id;
 980         as->reserve     = reserve;
 981         INIT_LIST_HEAD(&as->write_blocked_list);
 982
 983         bch2_keylist_init(&as->parent_keys, as->inline_keys);
 984
 985         ret = bch2_journal_preres_get(&c->journal, &as->journal_preres,
 986                                  jset_u64s(BKEY_BTREE_PTR_U64s_MAX) * 3, 0);
 987         if (ret) {
 988                 bch2_btree_reserve_put(c, reserve);
 989                 closure_debug_destroy(&as->cl);
 990                 mempool_free(as, &c->btree_interior_update_pool);
 991                 return ERR_PTR(ret);
 992         }
 993
 994         mutex_lock(&c->btree_interior_update_lock);
 995         list_add_tail(&as->list, &c->btree_interior_update_list);
 996         mutex_unlock(&c->btree_interior_update_lock);
 997
 998         return as;
 999 }
1000
1001 /* Btree root updates: */
1002
1003 static void __bch2_btree_set_root_inmem(struct bch_fs *c, struct btree *b)
1004 {
1005         /* Root nodes cannot be reaped */
1006         mutex_lock(&c->btree_cache.lock);
1007         list_del_init(&b->list);
1008         mutex_unlock(&c->btree_cache.lock);
1009
1010         mutex_lock(&c->btree_root_lock);
1011         BUG_ON(btree_node_root(c, b) &&
1012                (b->level < btree_node_root(c, b)->level ||
1013                 !btree_node_dying(btree_node_root(c, b))));
1014
1015         btree_node_root(c, b) = b;
1016         mutex_unlock(&c->btree_root_lock);
1017
1018         bch2_recalc_btree_reserve(c);
1019 }
1020
1021 static void bch2_btree_set_root_inmem(struct btree_update *as, struct btree *b)
1022 {
1023         struct bch_fs *c = as->c;
1024         struct btree *old = btree_node_root(c, b);
1025         struct bch_fs_usage *fs_usage;
1026
1027         __bch2_btree_set_root_inmem(c, b);
1028
1029         mutex_lock(&c->btree_interior_update_lock);
1030         percpu_down_read(&c->mark_lock);
1031         fs_usage = bch2_fs_usage_scratch_get(c);
1032
1033         bch2_mark_key_locked(c, bkey_i_to_s_c(&b->key),
1034                       0, 0, fs_usage, 0,
1035                       BTREE_TRIGGER_INSERT);
1036         if (gc_visited(c, gc_pos_btree_root(b->btree_id)))
1037                 bch2_mark_key_locked(c, bkey_i_to_s_c(&b->key),
1038                                      0, 0, NULL, 0,
1039                                      BTREE_TRIGGER_INSERT|
1040                                      BTREE_TRIGGER_GC);
1041
1042         if (old && !btree_node_fake(old))
1043                 bch2_btree_node_free_index(as, NULL,
1044                                            bkey_i_to_s_c(&old->key),
1045                                            fs_usage);
1046         bch2_fs_usage_apply(c, fs_usage, &as->reserve->disk_res, 0);
1047
1048         bch2_fs_usage_scratch_put(c, fs_usage);
1049         percpu_up_read(&c->mark_lock);
1050         mutex_unlock(&c->btree_interior_update_lock);
1051 }
1052
1053 /**
1054  * bch_btree_set_root - update the root in memory and on disk
1055  *
1056  * To ensure forward progress, the current task must not be holding any
1057  * btree node write locks. However, you must hold an intent lock on the
1058  * old root.
1059  *
1060  * Note: This allocates a journal entry but doesn't add any keys to
1061  * it.  All the btree roots are part of every journal write, so there
1062  * is nothing new to be done.  This just guarantees that there is a
1063  * journal write.
1064  */
1065 static void bch2_btree_set_root(struct btree_update *as, struct btree *b,
1066                                 struct btree_iter *iter)
1067 {
1068         struct bch_fs *c = as->c;
1069         struct btree *old;
1070
1071         trace_btree_set_root(c, b);
1072         BUG_ON(!b->written &&
1073                !test_bit(BCH_FS_HOLD_BTREE_WRITES, &c->flags));
1074
1075         old = btree_node_root(c, b);
1076
1077         /*
1078          * Ensure no one is using the old root while we switch to the
1079          * new root:
1080          */
1081         bch2_btree_node_lock_write(old, iter);
1082
1083         bch2_btree_set_root_inmem(as, b);
1084
1085         btree_update_updated_root(as, b);
1086
1087         /*
1088          * Unlock old root after new root is visible:
1089          *
1090          * The new root isn't persistent, but that's ok: we still have
1091          * an intent lock on the new root, and any updates that would
1092          * depend on the new root would have to update the new root.
1093          */
1094         bch2_btree_node_unlock_write(old, iter);
1095 }
1096
1097 /* Interior node updates: */
1098
1099 static void bch2_insert_fixup_btree_ptr(struct btree_update *as, struct btree *b,
1100                                         struct btree_iter *iter,
1101                                         struct bkey_i *insert,
1102                                         struct btree_node_iter *node_iter)
1103 {
1104         struct bch_fs *c = as->c;
1105         struct bch_fs_usage *fs_usage;
1106         struct bkey_packed *k;
1107         struct bkey tmp;
1108
1109         BUG_ON(insert->k.u64s > bch_btree_keys_u64s_remaining(c, b));
1110
1111         mutex_lock(&c->btree_interior_update_lock);
1112         percpu_down_read(&c->mark_lock);
1113         fs_usage = bch2_fs_usage_scratch_get(c);
1114
1115         bch2_mark_key_locked(c, bkey_i_to_s_c(insert),
1116                              0, 0, fs_usage, 0,
1117                              BTREE_TRIGGER_INSERT);
1118
1119         if (gc_visited(c, gc_pos_btree_node(b)))
1120                 bch2_mark_key_locked(c, bkey_i_to_s_c(insert),
1121                                      0, 0, NULL, 0,
1122                                      BTREE_TRIGGER_INSERT|
1123                                      BTREE_TRIGGER_GC);
1124
1125         while ((k = bch2_btree_node_iter_peek_all(node_iter, b)) &&
1126                bkey_iter_pos_cmp(b, k, &insert->k.p) < 0)
1127                 bch2_btree_node_iter_advance(node_iter, b);
1128
1129         /*
1130          * If we're overwriting, look up pending delete and mark so that gc
1131          * marks it on the pending delete list:
1132          */
1133         if (k && !bkey_cmp_packed(b, k, &insert->k))
1134                 bch2_btree_node_free_index(as, b,
1135                                            bkey_disassemble(b, k, &tmp),
1136                                            fs_usage);
1137
1138         bch2_fs_usage_apply(c, fs_usage, &as->reserve->disk_res, 0);
1139
1140         bch2_fs_usage_scratch_put(c, fs_usage);
1141         percpu_up_read(&c->mark_lock);
1142         mutex_unlock(&c->btree_interior_update_lock);
1143
1144         bch2_btree_bset_insert_key(iter, b, node_iter, insert);
1145         set_btree_node_dirty(b);
1146         set_btree_node_need_write(b);
1147 }
1148
1149 /*
1150  * Move keys from n1 (original replacement node, now lower node) to n2 (higher
1151  * node)
1152  */
1153 static struct btree *__btree_split_node(struct btree_update *as,
1154                                         struct btree *n1,
1155                                         struct btree_iter *iter)
1156 {
1157         size_t nr_packed = 0, nr_unpacked = 0;
1158         struct btree *n2;
1159         struct bset *set1, *set2;
1160         struct bkey_packed *k, *prev = NULL;
1161
1162         n2 = bch2_btree_node_alloc(as, n1->level);
1163
1164         n2->data->max_key       = n1->data->max_key;
1165         n2->data->format        = n1->format;
1166         SET_BTREE_NODE_SEQ(n2->data, BTREE_NODE_SEQ(n1->data));
1167         n2->key.k.p = n1->key.k.p;
1168
1169         btree_node_set_format(n2, n2->data->format);
1170
1171         set1 = btree_bset_first(n1);
1172         set2 = btree_bset_first(n2);
1173
1174         /*
1175          * Has to be a linear search because we don't have an auxiliary
1176          * search tree yet
1177          */
1178         k = set1->start;
1179         while (1) {
1180                 struct bkey_packed *n = bkey_next_skip_noops(k, vstruct_last(set1));
1181
1182                 if (n == vstruct_last(set1))
1183                         break;
1184                 if (k->_data - set1->_data >= (le16_to_cpu(set1->u64s) * 3) / 5)
1185                         break;
1186
1187                 if (bkey_packed(k))
1188                         nr_packed++;
1189                 else
1190                         nr_unpacked++;
1191
1192                 prev = k;
1193                 k = n;
1194         }
1195
1196         BUG_ON(!prev);
1197
1198         btree_set_max(n1, bkey_unpack_pos(n1, prev));
1199         btree_set_min(n2, bkey_successor(n1->key.k.p));
1200
1201         set2->u64s = cpu_to_le16((u64 *) vstruct_end(set1) - (u64 *) k);
1202         set1->u64s = cpu_to_le16(le16_to_cpu(set1->u64s) - le16_to_cpu(set2->u64s));
1203
1204         set_btree_bset_end(n1, n1->set);
1205         set_btree_bset_end(n2, n2->set);
1206
1207         n2->nr.live_u64s        = le16_to_cpu(set2->u64s);
1208         n2->nr.bset_u64s[0]     = le16_to_cpu(set2->u64s);
1209         n2->nr.packed_keys      = n1->nr.packed_keys - nr_packed;
1210         n2->nr.unpacked_keys    = n1->nr.unpacked_keys - nr_unpacked;
1211
1212         n1->nr.live_u64s        = le16_to_cpu(set1->u64s);
1213         n1->nr.bset_u64s[0]     = le16_to_cpu(set1->u64s);
1214         n1->nr.packed_keys      = nr_packed;
1215         n1->nr.unpacked_keys    = nr_unpacked;
1216
1217         BUG_ON(!set1->u64s);
1218         BUG_ON(!set2->u64s);
1219
1220         memcpy_u64s(set2->start,
1221                     vstruct_end(set1),
1222                     le16_to_cpu(set2->u64s));
1223
1224         btree_node_reset_sib_u64s(n1);
1225         btree_node_reset_sib_u64s(n2);
1226
1227         bch2_verify_btree_nr_keys(n1);
1228         bch2_verify_btree_nr_keys(n2);
1229
1230         if (n1->level) {
1231                 btree_node_interior_verify(n1);
1232                 btree_node_interior_verify(n2);
1233         }
1234
1235         return n2;
1236 }
1237
1238 /*
1239  * For updates to interior nodes, we've got to do the insert before we split
1240  * because the stuff we're inserting has to be inserted atomically. Post split,
1241  * the keys might have to go in different nodes and the split would no longer be
1242  * atomic.
1243  *
1244  * Worse, if the insert is from btree node coalescing, if we do the insert after
1245  * we do the split (and pick the pivot) - the pivot we pick might be between
1246  * nodes that were coalesced, and thus in the middle of a child node post
1247  * coalescing:
1248  */
1249 static void btree_split_insert_keys(struct btree_update *as, struct btree *b,
1250                                     struct btree_iter *iter,
1251                                     struct keylist *keys)
1252 {
1253         struct btree_node_iter node_iter;
1254         struct bkey_i *k = bch2_keylist_front(keys);
1255         struct bkey_packed *src, *dst, *n;
1256         struct bset *i;
1257
1258         BUG_ON(btree_node_type(b) != BKEY_TYPE_BTREE);
1259
1260         bch2_btree_node_iter_init(&node_iter, b, &k->k.p);
1261
1262         while (!bch2_keylist_empty(keys)) {
1263                 k = bch2_keylist_front(keys);
1264
1265                 BUG_ON(bch_keylist_u64s(keys) >
1266                        bch_btree_keys_u64s_remaining(as->c, b));
1267                 BUG_ON(bkey_cmp(k->k.p, b->data->min_key) < 0);
1268                 BUG_ON(bkey_cmp(k->k.p, b->data->max_key) > 0);
1269
1270                 bch2_insert_fixup_btree_ptr(as, b, iter, k, &node_iter);
1271                 bch2_keylist_pop_front(keys);
1272         }
1273
1274         /*
1275          * We can't tolerate whiteouts here - with whiteouts there can be
1276          * duplicate keys, and it would be rather bad if we picked a duplicate
1277          * for the pivot:
1278          */
1279         i = btree_bset_first(b);
1280         src = dst = i->start;
1281         while (src != vstruct_last(i)) {
1282                 n = bkey_next_skip_noops(src, vstruct_last(i));
1283                 if (!bkey_deleted(src)) {
1284                         memmove_u64s_down(dst, src, src->u64s);
1285                         dst = bkey_next(dst);
1286                 }
1287                 src = n;
1288         }
1289
1290         i->u64s = cpu_to_le16((u64 *) dst - i->_data);
1291         set_btree_bset_end(b, b->set);
1292
1293         BUG_ON(b->nsets != 1 ||
1294                b->nr.live_u64s != le16_to_cpu(btree_bset_first(b)->u64s));
1295
1296         btree_node_interior_verify(b);
1297 }
1298
1299 static void btree_split(struct btree_update *as, struct btree *b,
1300                         struct btree_iter *iter, struct keylist *keys,
1301                         unsigned flags)
1302 {
1303         struct bch_fs *c = as->c;
1304         struct btree *parent = btree_node_parent(iter, b);
1305         struct btree *n1, *n2 = NULL, *n3 = NULL;
1306         u64 start_time = local_clock();
1307
1308         BUG_ON(!parent && (b != btree_node_root(c, b)));
1309         BUG_ON(!btree_node_intent_locked(iter, btree_node_root(c, b)->level));
1310
1311         bch2_btree_interior_update_will_free_node(as, b);
1312
1313         n1 = bch2_btree_node_alloc_replacement(as, b);
1314
1315         if (keys)
1316                 btree_split_insert_keys(as, n1, iter, keys);
1317
1318         if (bset_u64s(&n1->set[0]) > BTREE_SPLIT_THRESHOLD(c)) {
1319                 trace_btree_split(c, b);
1320
1321                 n2 = __btree_split_node(as, n1, iter);
1322
1323                 bch2_btree_build_aux_trees(n2);
1324                 bch2_btree_build_aux_trees(n1);
1325                 six_unlock_write(&n2->lock);
1326                 six_unlock_write(&n1->lock);
1327
1328                 bch2_btree_node_write(c, n2, SIX_LOCK_intent);
1329
1330                 /*
1331                  * Note that on recursive parent_keys == keys, so we
1332                  * can't start adding new keys to parent_keys before emptying it
1333                  * out (which we did with btree_split_insert_keys() above)
1334                  */
1335                 bch2_keylist_add(&as->parent_keys, &n1->key);
1336                 bch2_keylist_add(&as->parent_keys, &n2->key);
1337
1338                 if (!parent) {
1339                         /* Depth increases, make a new root */
1340                         n3 = __btree_root_alloc(as, b->level + 1);
1341
1342                         n3->sib_u64s[0] = U16_MAX;
1343                         n3->sib_u64s[1] = U16_MAX;
1344
1345                         btree_split_insert_keys(as, n3, iter, &as->parent_keys);
1346
1347                         bch2_btree_node_write(c, n3, SIX_LOCK_intent);
1348                 }
1349         } else {
1350                 trace_btree_compact(c, b);
1351
1352                 bch2_btree_build_aux_trees(n1);
1353                 six_unlock_write(&n1->lock);
1354
1355                 if (parent)
1356                         bch2_keylist_add(&as->parent_keys, &n1->key);
1357         }
1358
1359         bch2_btree_node_write(c, n1, SIX_LOCK_intent);
1360
1361         /* New nodes all written, now make them visible: */
1362
1363         if (parent) {
1364                 /* Split a non root node */
1365                 bch2_btree_insert_node(as, parent, iter, &as->parent_keys, flags);
1366         } else if (n3) {
1367                 bch2_btree_set_root(as, n3, iter);
1368         } else {
1369                 /* Root filled up but didn't need to be split */
1370                 bch2_btree_set_root(as, n1, iter);
1371         }
1372
1373         bch2_open_buckets_put(c, &n1->ob);
1374         if (n2)
1375                 bch2_open_buckets_put(c, &n2->ob);
1376         if (n3)
1377                 bch2_open_buckets_put(c, &n3->ob);
1378
1379         /* Successful split, update the iterator to point to the new nodes: */
1380
1381         six_lock_increment(&b->lock, SIX_LOCK_intent);
1382         bch2_btree_iter_node_drop(iter, b);
1383         if (n3)
1384                 bch2_btree_iter_node_replace(iter, n3);
1385         if (n2)
1386                 bch2_btree_iter_node_replace(iter, n2);
1387         bch2_btree_iter_node_replace(iter, n1);
1388
1389         /*
1390          * The old node must be freed (in memory) _before_ unlocking the new
1391          * nodes - else another thread could re-acquire a read lock on the old
1392          * node after another thread has locked and updated the new node, thus
1393          * seeing stale data:
1394          */
1395         bch2_btree_node_free_inmem(c, b, iter);
1396
1397         if (n3)
1398                 six_unlock_intent(&n3->lock);
1399         if (n2)
1400                 six_unlock_intent(&n2->lock);
1401         six_unlock_intent(&n1->lock);
1402
1403         bch2_btree_trans_verify_locks(iter->trans);
1404
1405         bch2_time_stats_update(&c->times[BCH_TIME_btree_node_split],
1406                                start_time);
1407 }
1408
1409 static void
1410 bch2_btree_insert_keys_interior(struct btree_update *as, struct btree *b,
1411                                 struct btree_iter *iter, struct keylist *keys)
1412 {
1413         struct btree_iter *linked;
1414         struct btree_node_iter node_iter;
1415         struct bkey_i *insert = bch2_keylist_front(keys);
1416         struct bkey_packed *k;
1417
1418         /* Don't screw up @iter's position: */
1419         node_iter = iter->l[b->level].iter;
1420
1421         /*
1422          * btree_split(), btree_gc_coalesce() will insert keys before
1423          * the iterator's current position - they know the keys go in
1424          * the node the iterator points to:
1425          */
1426         while ((k = bch2_btree_node_iter_prev_all(&node_iter, b)) &&
1427                (bkey_cmp_packed(b, k, &insert->k) >= 0))
1428                 ;
1429
1430         for_each_keylist_key(keys, insert)
1431                 bch2_insert_fixup_btree_ptr(as, b, iter, insert, &node_iter);
1432
1433         btree_update_updated_node(as, b);
1434
1435         trans_for_each_iter_with_node(iter->trans, b, linked)
1436                 bch2_btree_node_iter_peek(&linked->l[b->level].iter, b);
1437
1438         bch2_btree_trans_verify_iters(iter->trans, b);
1439 }
1440
1441 /**
1442  * bch_btree_insert_node - insert bkeys into a given btree node
1443  *
1444  * @iter:               btree iterator
1445  * @keys:               list of keys to insert
1446  * @hook:               insert callback
1447  * @persistent:         if not null, @persistent will wait on journal write
1448  *
1449  * Inserts as many keys as it can into a given btree node, splitting it if full.
1450  * If a split occurred, this function will return early. This can only happen
1451  * for leaf nodes -- inserts into interior nodes have to be atomic.
1452  */
1453 void bch2_btree_insert_node(struct btree_update *as, struct btree *b,
1454                             struct btree_iter *iter, struct keylist *keys,
1455                             unsigned flags)
1456 {
1457         struct bch_fs *c = as->c;
1458         int old_u64s = le16_to_cpu(btree_bset_last(b)->u64s);
1459         int old_live_u64s = b->nr.live_u64s;
1460         int live_u64s_added, u64s_added;
1461
1462         BUG_ON(!btree_node_intent_locked(iter, btree_node_root(c, b)->level));
1463         BUG_ON(!b->level);
1464         BUG_ON(!as || as->b);
1465         bch2_verify_keylist_sorted(keys);
1466
1467         if (as->must_rewrite)
1468                 goto split;
1469
1470         bch2_btree_node_lock_for_insert(c, b, iter);
1471
1472         if (!bch2_btree_node_insert_fits(c, b, bch_keylist_u64s(keys))) {
1473                 bch2_btree_node_unlock_write(b, iter);
1474                 goto split;
1475         }
1476
1477         bch2_btree_insert_keys_interior(as, b, iter, keys);
1478
1479         live_u64s_added = (int) b->nr.live_u64s - old_live_u64s;
1480         u64s_added = (int) le16_to_cpu(btree_bset_last(b)->u64s) - old_u64s;
1481
1482         if (b->sib_u64s[0] != U16_MAX && live_u64s_added < 0)
1483                 b->sib_u64s[0] = max(0, (int) b->sib_u64s[0] + live_u64s_added);
1484         if (b->sib_u64s[1] != U16_MAX && live_u64s_added < 0)
1485                 b->sib_u64s[1] = max(0, (int) b->sib_u64s[1] + live_u64s_added);
1486
1487         if (u64s_added > live_u64s_added &&
1488             bch2_maybe_compact_whiteouts(c, b))
1489                 bch2_btree_iter_reinit_node(iter, b);
1490
1491         bch2_btree_node_unlock_write(b, iter);
1492
1493         btree_node_interior_verify(b);
1494
1495         /*
1496          * when called from the btree_split path the new nodes aren't added to
1497          * the btree iterator yet, so the merge path's unlock/wait/relock dance
1498          * won't work:
1499          */
1500         bch2_foreground_maybe_merge(c, iter, b->level,
1501                                     flags|BTREE_INSERT_NOUNLOCK);
1502         return;
1503 split:
1504         btree_split(as, b, iter, keys, flags);
1505 }
1506
1507 int bch2_btree_split_leaf(struct bch_fs *c, struct btree_iter *iter,
1508                           unsigned flags)
1509 {
1510         struct btree_trans *trans = iter->trans;
1511         struct btree *b = iter_l(iter)->b;
1512         struct btree_update *as;
1513         struct closure cl;
1514         int ret = 0;
1515         struct btree_iter *linked;
1516
1517         /*
1518          * We already have a disk reservation and open buckets pinned; this
1519          * allocation must not block:
1520          */
1521         trans_for_each_iter(trans, linked)
1522                 if (linked->btree_id == BTREE_ID_EXTENTS)
1523                         flags |= BTREE_INSERT_USE_RESERVE;
1524
1525         closure_init_stack(&cl);
1526
1527         /* Hack, because gc and splitting nodes doesn't mix yet: */
1528         if (!(flags & BTREE_INSERT_GC_LOCK_HELD) &&
1529             !down_read_trylock(&c->gc_lock)) {
1530                 if (flags & BTREE_INSERT_NOUNLOCK)
1531                         return -EINTR;
1532
1533                 bch2_trans_unlock(trans);
1534                 down_read(&c->gc_lock);
1535
1536                 if (!bch2_trans_relock(trans))
1537                         ret = -EINTR;
1538         }
1539
1540         /*
1541          * XXX: figure out how far we might need to split,
1542          * instead of locking/reserving all the way to the root:
1543          */
1544         if (!bch2_btree_iter_upgrade(iter, U8_MAX)) {
1545                 trace_trans_restart_iter_upgrade(trans->ip);
1546                 ret = -EINTR;
1547                 goto out;
1548         }
1549
1550         as = bch2_btree_update_start(c, iter->btree_id,
1551                 btree_update_reserve_required(c, b), flags,
1552                 !(flags & BTREE_INSERT_NOUNLOCK) ? &cl : NULL);
1553         if (IS_ERR(as)) {
1554                 ret = PTR_ERR(as);
1555                 if (ret == -EAGAIN) {
1556                         BUG_ON(flags & BTREE_INSERT_NOUNLOCK);
1557                         bch2_trans_unlock(trans);
1558                         ret = -EINTR;
1559                 }
1560                 goto out;
1561         }
1562
1563         btree_split(as, b, iter, NULL, flags);
1564         bch2_btree_update_done(as);
1565
1566         /*
1567          * We haven't successfully inserted yet, so don't downgrade all the way
1568          * back to read locks;
1569          */
1570         __bch2_btree_iter_downgrade(iter, 1);
1571 out:
1572         if (!(flags & BTREE_INSERT_GC_LOCK_HELD))
1573                 up_read(&c->gc_lock);
1574         closure_sync(&cl);
1575         return ret;
1576 }
1577
1578 void __bch2_foreground_maybe_merge(struct bch_fs *c,
1579                                    struct btree_iter *iter,
1580                                    unsigned level,
1581                                    unsigned flags,
1582                                    enum btree_node_sibling sib)
1583 {
1584         struct btree_trans *trans = iter->trans;
1585         struct btree_update *as;
1586         struct bkey_format_state new_s;
1587         struct bkey_format new_f;
1588         struct bkey_i delete;
1589         struct btree *b, *m, *n, *prev, *next, *parent;
1590         struct closure cl;
1591         size_t sib_u64s;
1592         int ret = 0;
1593
1594         BUG_ON(!btree_node_locked(iter, level));
1595
1596         closure_init_stack(&cl);
1597 retry:
1598         BUG_ON(!btree_node_locked(iter, level));
1599
1600         b = iter->l[level].b;
1601
1602         parent = btree_node_parent(iter, b);
1603         if (!parent)
1604                 goto out;
1605
1606         if (b->sib_u64s[sib] > BTREE_FOREGROUND_MERGE_THRESHOLD(c))
1607                 goto out;
1608
1609         /* XXX: can't be holding read locks */
1610         m = bch2_btree_node_get_sibling(c, iter, b, sib);
1611         if (IS_ERR(m)) {
1612                 ret = PTR_ERR(m);
1613                 goto err;
1614         }
1615
1616         /* NULL means no sibling: */
1617         if (!m) {
1618                 b->sib_u64s[sib] = U16_MAX;
1619                 goto out;
1620         }
1621
1622         if (sib == btree_prev_sib) {
1623                 prev = m;
1624                 next = b;
1625         } else {
1626                 prev = b;
1627                 next = m;
1628         }
1629
1630         bch2_bkey_format_init(&new_s);
1631         __bch2_btree_calc_format(&new_s, b);
1632         __bch2_btree_calc_format(&new_s, m);
1633         new_f = bch2_bkey_format_done(&new_s);
1634
1635         sib_u64s = btree_node_u64s_with_format(b, &new_f) +
1636                 btree_node_u64s_with_format(m, &new_f);
1637
1638         if (sib_u64s > BTREE_FOREGROUND_MERGE_HYSTERESIS(c)) {
1639                 sib_u64s -= BTREE_FOREGROUND_MERGE_HYSTERESIS(c);
1640                 sib_u64s /= 2;
1641                 sib_u64s += BTREE_FOREGROUND_MERGE_HYSTERESIS(c);
1642         }
1643
1644         sib_u64s = min(sib_u64s, btree_max_u64s(c));
1645         b->sib_u64s[sib] = sib_u64s;
1646
1647         if (b->sib_u64s[sib] > BTREE_FOREGROUND_MERGE_THRESHOLD(c)) {
1648                 six_unlock_intent(&m->lock);
1649                 goto out;
1650         }
1651
1652         /* We're changing btree topology, doesn't mix with gc: */
1653         if (!(flags & BTREE_INSERT_GC_LOCK_HELD) &&
1654             !down_read_trylock(&c->gc_lock))
1655                 goto err_cycle_gc_lock;
1656
1657         if (!bch2_btree_iter_upgrade(iter, U8_MAX)) {
1658                 ret = -EINTR;
1659                 goto err_unlock;
1660         }
1661
1662         as = bch2_btree_update_start(c, iter->btree_id,
1663                          btree_update_reserve_required(c, parent) + 1,
1664                          BTREE_INSERT_NOFAIL|
1665                          BTREE_INSERT_USE_RESERVE,
1666                          !(flags & BTREE_INSERT_NOUNLOCK) ? &cl : NULL);
1667         if (IS_ERR(as)) {
1668                 ret = PTR_ERR(as);
1669                 goto err_unlock;
1670         }
1671
1672         trace_btree_merge(c, b);
1673
1674         bch2_btree_interior_update_will_free_node(as, b);
1675         bch2_btree_interior_update_will_free_node(as, m);
1676
1677         n = bch2_btree_node_alloc(as, b->level);
1678
1679         btree_set_min(n, prev->data->min_key);
1680         btree_set_max(n, next->data->max_key);
1681         n->data->format         = new_f;
1682
1683         btree_node_set_format(n, new_f);
1684
1685         bch2_btree_sort_into(c, n, prev);
1686         bch2_btree_sort_into(c, n, next);
1687
1688         bch2_btree_build_aux_trees(n);
1689         six_unlock_write(&n->lock);
1690
1691         bkey_init(&delete.k);
1692         delete.k.p = prev->key.k.p;
1693         bch2_keylist_add(&as->parent_keys, &delete);
1694         bch2_keylist_add(&as->parent_keys, &n->key);
1695
1696         bch2_btree_node_write(c, n, SIX_LOCK_intent);
1697
1698         bch2_btree_insert_node(as, parent, iter, &as->parent_keys, flags);
1699
1700         bch2_open_buckets_put(c, &n->ob);
1701
1702         six_lock_increment(&b->lock, SIX_LOCK_intent);
1703         bch2_btree_iter_node_drop(iter, b);
1704         bch2_btree_iter_node_drop(iter, m);
1705
1706         bch2_btree_iter_node_replace(iter, n);
1707
1708         bch2_btree_trans_verify_iters(trans, n);
1709
1710         bch2_btree_node_free_inmem(c, b, iter);
1711         bch2_btree_node_free_inmem(c, m, iter);
1712
1713         six_unlock_intent(&n->lock);
1714
1715         bch2_btree_update_done(as);
1716
1717         if (!(flags & BTREE_INSERT_GC_LOCK_HELD))
1718                 up_read(&c->gc_lock);
1719 out:
1720         bch2_btree_trans_verify_locks(trans);
1721
1722         /*
1723          * Don't downgrade locks here: we're called after successful insert,
1724          * and the caller will downgrade locks after a successful insert
1725          * anyways (in case e.g. a split was required first)
1726          *
1727          * And we're also called when inserting into interior nodes in the
1728          * split path, and downgrading to read locks in there is potentially
1729          * confusing:
1730          */
1731         closure_sync(&cl);
1732         return;
1733
1734 err_cycle_gc_lock:
1735         six_unlock_intent(&m->lock);
1736
1737         if (flags & BTREE_INSERT_NOUNLOCK)
1738                 goto out;
1739
1740         bch2_trans_unlock(trans);
1741
1742         down_read(&c->gc_lock);
1743         up_read(&c->gc_lock);
1744         ret = -EINTR;
1745         goto err;
1746
1747 err_unlock:
1748         six_unlock_intent(&m->lock);
1749         if (!(flags & BTREE_INSERT_GC_LOCK_HELD))
1750                 up_read(&c->gc_lock);
1751 err:
1752         BUG_ON(ret == -EAGAIN && (flags & BTREE_INSERT_NOUNLOCK));
1753
1754         if ((ret == -EAGAIN || ret == -EINTR) &&
1755             !(flags & BTREE_INSERT_NOUNLOCK)) {
1756                 bch2_trans_unlock(trans);
1757                 closure_sync(&cl);
1758                 ret = bch2_btree_iter_traverse(iter);
1759                 if (ret)
1760                         goto out;
1761
1762                 goto retry;
1763         }
1764
1765         goto out;
1766 }
1767
1768 static int __btree_node_rewrite(struct bch_fs *c, struct btree_iter *iter,
1769                                 struct btree *b, unsigned flags,
1770                                 struct closure *cl)
1771 {
1772         struct btree *n, *parent = btree_node_parent(iter, b);
1773         struct btree_update *as;
1774
1775         as = bch2_btree_update_start(c, iter->btree_id,
1776                 (parent
1777                  ? btree_update_reserve_required(c, parent)
1778                  : 0) + 1,
1779                 flags, cl);
1780         if (IS_ERR(as)) {
1781                 trace_btree_gc_rewrite_node_fail(c, b);
1782                 return PTR_ERR(as);
1783         }
1784
1785         bch2_btree_interior_update_will_free_node(as, b);
1786
1787         n = bch2_btree_node_alloc_replacement(as, b);
1788
1789         bch2_btree_build_aux_trees(n);
1790         six_unlock_write(&n->lock);
1791
1792         trace_btree_gc_rewrite_node(c, b);
1793
1794         bch2_btree_node_write(c, n, SIX_LOCK_intent);
1795
1796         if (parent) {
1797                 bch2_keylist_add(&as->parent_keys, &n->key);
1798                 bch2_btree_insert_node(as, parent, iter, &as->parent_keys, flags);
1799         } else {
1800                 bch2_btree_set_root(as, n, iter);
1801         }
1802
1803         bch2_open_buckets_put(c, &n->ob);
1804
1805         six_lock_increment(&b->lock, SIX_LOCK_intent);
1806         bch2_btree_iter_node_drop(iter, b);
1807         bch2_btree_iter_node_replace(iter, n);
1808         bch2_btree_node_free_inmem(c, b, iter);
1809         six_unlock_intent(&n->lock);
1810
1811         bch2_btree_update_done(as);
1812         return 0;
1813 }
1814
1815 /**
1816  * bch_btree_node_rewrite - Rewrite/move a btree node
1817  *
1818  * Returns 0 on success, -EINTR or -EAGAIN on failure (i.e.
1819  * btree_check_reserve() has to wait)
1820  */
1821 int bch2_btree_node_rewrite(struct bch_fs *c, struct btree_iter *iter,
1822                             __le64 seq, unsigned flags)
1823 {
1824         struct btree_trans *trans = iter->trans;
1825         struct closure cl;
1826         struct btree *b;
1827         int ret;
1828
1829         flags |= BTREE_INSERT_NOFAIL;
1830
1831         closure_init_stack(&cl);
1832
1833         bch2_btree_iter_upgrade(iter, U8_MAX);
1834
1835         if (!(flags & BTREE_INSERT_GC_LOCK_HELD)) {
1836                 if (!down_read_trylock(&c->gc_lock)) {
1837                         bch2_trans_unlock(trans);
1838                         down_read(&c->gc_lock);
1839                 }
1840         }
1841
1842         while (1) {
1843                 ret = bch2_btree_iter_traverse(iter);
1844                 if (ret)
1845                         break;
1846
1847                 b = bch2_btree_iter_peek_node(iter);
1848                 if (!b || b->data->keys.seq != seq)
1849                         break;
1850
1851                 ret = __btree_node_rewrite(c, iter, b, flags, &cl);
1852                 if (ret != -EAGAIN &&
1853                     ret != -EINTR)
1854                         break;
1855
1856                 bch2_trans_unlock(trans);
1857                 closure_sync(&cl);
1858         }
1859
1860         bch2_btree_iter_downgrade(iter);
1861
1862         if (!(flags & BTREE_INSERT_GC_LOCK_HELD))
1863                 up_read(&c->gc_lock);
1864
1865         closure_sync(&cl);
1866         return ret;
1867 }
1868
1869 static void __bch2_btree_node_update_key(struct bch_fs *c,
1870                                          struct btree_update *as,
1871                                          struct btree_iter *iter,
1872                                          struct btree *b, struct btree *new_hash,
1873                                          struct bkey_i *new_key)
1874 {
1875         struct btree *parent;
1876         int ret;
1877
1878         /*
1879          * Two corner cases that need to be thought about here:
1880          *
1881          * @b may not be reachable yet - there might be another interior update
1882          * operation waiting on @b to be written, and we're gonna deliver the
1883          * write completion to that interior update operation _before_
1884          * persisting the new_key update
1885          *
1886          * That ends up working without us having to do anything special here:
1887          * the reason is, we do kick off (and do the in memory updates) for the
1888          * update for @new_key before we return, creating a new interior_update
1889          * operation here.
1890          *
1891          * The new interior update operation here will in effect override the
1892          * previous one. The previous one was going to terminate - make @b
1893          * reachable - in one of two ways:
1894          * - updating the btree root pointer
1895          *   In that case,
1896          *   no, this doesn't work. argh.
1897          */
1898
1899         if (b->will_make_reachable)
1900                 as->must_rewrite = true;
1901
1902         btree_interior_update_add_node_reference(as, b);
1903
1904         /*
1905          * XXX: the rest of the update path treats this like we're actually
1906          * inserting a new node and deleting the existing node, so the
1907          * reservation needs to include enough space for @b
1908          *
1909          * that is actually sketch as fuck though and I am surprised the code
1910          * seems to work like that, definitely need to go back and rework it
1911          * into something saner.
1912          *
1913          * (I think @b is just getting double counted until the btree update
1914          * finishes and "deletes" @b on disk)
1915          */
1916         ret = bch2_disk_reservation_add(c, &as->reserve->disk_res,
1917                         c->opts.btree_node_size *
1918                         bch2_bkey_nr_ptrs(bkey_i_to_s_c(new_key)),
1919                         BCH_DISK_RESERVATION_NOFAIL);
1920         BUG_ON(ret);
1921
1922         parent = btree_node_parent(iter, b);
1923         if (parent) {
1924                 if (new_hash) {
1925                         bkey_copy(&new_hash->key, new_key);
1926                         ret = bch2_btree_node_hash_insert(&c->btree_cache,
1927                                         new_hash, b->level, b->btree_id);
1928                         BUG_ON(ret);
1929                 }
1930
1931                 bch2_keylist_add(&as->parent_keys, new_key);
1932                 bch2_btree_insert_node(as, parent, iter, &as->parent_keys, 0);
1933
1934                 if (new_hash) {
1935                         mutex_lock(&c->btree_cache.lock);
1936                         bch2_btree_node_hash_remove(&c->btree_cache, new_hash);
1937
1938                         bch2_btree_node_hash_remove(&c->btree_cache, b);
1939
1940                         bkey_copy(&b->key, new_key);
1941                         ret = __bch2_btree_node_hash_insert(&c->btree_cache, b);
1942                         BUG_ON(ret);
1943                         mutex_unlock(&c->btree_cache.lock);
1944                 } else {
1945                         bkey_copy(&b->key, new_key);
1946                 }
1947         } else {
1948                 struct bch_fs_usage *fs_usage;
1949
1950                 BUG_ON(btree_node_root(c, b) != b);
1951
1952                 bch2_btree_node_lock_write(b, iter);
1953
1954                 mutex_lock(&c->btree_interior_update_lock);
1955                 percpu_down_read(&c->mark_lock);
1956                 fs_usage = bch2_fs_usage_scratch_get(c);
1957
1958                 bch2_mark_key_locked(c, bkey_i_to_s_c(new_key),
1959                               0, 0, fs_usage, 0,
1960                               BTREE_TRIGGER_INSERT);
1961                 if (gc_visited(c, gc_pos_btree_root(b->btree_id)))
1962                         bch2_mark_key_locked(c, bkey_i_to_s_c(new_key),
1963                                              0, 0, NULL, 0,
1964                                              BTREE_TRIGGER_INSERT||
1965                                              BTREE_TRIGGER_GC);
1966
1967                 bch2_btree_node_free_index(as, NULL,
1968                                            bkey_i_to_s_c(&b->key),
1969                                            fs_usage);
1970                 bch2_fs_usage_apply(c, fs_usage, &as->reserve->disk_res, 0);
1971
1972                 bch2_fs_usage_scratch_put(c, fs_usage);
1973                 percpu_up_read(&c->mark_lock);
1974                 mutex_unlock(&c->btree_interior_update_lock);
1975
1976                 if (btree_ptr_hash_val(new_key) != b->hash_val) {
1977                         mutex_lock(&c->btree_cache.lock);
1978                         bch2_btree_node_hash_remove(&c->btree_cache, b);
1979
1980                         bkey_copy(&b->key, new_key);
1981                         ret = __bch2_btree_node_hash_insert(&c->btree_cache, b);
1982                         BUG_ON(ret);
1983                         mutex_unlock(&c->btree_cache.lock);
1984                 } else {
1985                         bkey_copy(&b->key, new_key);
1986                 }
1987
1988                 btree_update_updated_root(as, b);
1989                 bch2_btree_node_unlock_write(b, iter);
1990         }
1991
1992         bch2_btree_update_done(as);
1993 }
1994
1995 int bch2_btree_node_update_key(struct bch_fs *c, struct btree_iter *iter,
1996                                struct btree *b,
1997                                struct bkey_i *new_key)
1998 {
1999         struct btree *parent = btree_node_parent(iter, b);
2000         struct btree_update *as = NULL;
2001         struct btree *new_hash = NULL;
2002         struct closure cl;
2003         int ret;
2004
2005         closure_init_stack(&cl);
2006
2007         if (!bch2_btree_iter_upgrade(iter, U8_MAX))
2008                 return -EINTR;
2009
2010         if (!down_read_trylock(&c->gc_lock)) {
2011                 bch2_trans_unlock(iter->trans);
2012                 down_read(&c->gc_lock);
2013
2014                 if (!bch2_trans_relock(iter->trans)) {
2015                         ret = -EINTR;
2016                         goto err;
2017                 }
2018         }
2019
2020         /*
2021          * check btree_ptr_hash_val() after @b is locked by
2022          * btree_iter_traverse():
2023          */
2024         if (btree_ptr_hash_val(new_key) != b->hash_val) {
2025                 /* bch2_btree_reserve_get will unlock */
2026                 ret = bch2_btree_cache_cannibalize_lock(c, &cl);
2027                 if (ret) {
2028                         bch2_trans_unlock(iter->trans);
2029                         up_read(&c->gc_lock);
2030                         closure_sync(&cl);
2031                         down_read(&c->gc_lock);
2032
2033                         if (!bch2_trans_relock(iter->trans)) {
2034                                 ret = -EINTR;
2035                                 goto err;
2036                         }
2037                 }
2038
2039                 new_hash = bch2_btree_node_mem_alloc(c);
2040         }
2041
2042         as = bch2_btree_update_start(c, iter->btree_id,
2043                 parent ? btree_update_reserve_required(c, parent) : 0,
2044                 BTREE_INSERT_NOFAIL|
2045                 BTREE_INSERT_USE_RESERVE|
2046                 BTREE_INSERT_USE_ALLOC_RESERVE,
2047                 &cl);
2048
2049         if (IS_ERR(as)) {
2050                 ret = PTR_ERR(as);
2051                 if (ret == -EAGAIN)
2052                         ret = -EINTR;
2053
2054                 if (ret != -EINTR)
2055                         goto err;
2056
2057                 bch2_trans_unlock(iter->trans);
2058                 up_read(&c->gc_lock);
2059                 closure_sync(&cl);
2060                 down_read(&c->gc_lock);
2061
2062                 if (!bch2_trans_relock(iter->trans))
2063                         goto err;
2064         }
2065
2066         ret = bch2_mark_bkey_replicas(c, bkey_i_to_s_c(new_key));
2067         if (ret)
2068                 goto err_free_update;
2069
2070         __bch2_btree_node_update_key(c, as, iter, b, new_hash, new_key);
2071
2072         bch2_btree_iter_downgrade(iter);
2073 err:
2074         if (new_hash) {
2075                 mutex_lock(&c->btree_cache.lock);
2076                 list_move(&new_hash->list, &c->btree_cache.freeable);
2077                 mutex_unlock(&c->btree_cache.lock);
2078
2079                 six_unlock_write(&new_hash->lock);
2080                 six_unlock_intent(&new_hash->lock);
2081         }
2082         up_read(&c->gc_lock);
2083         closure_sync(&cl);
2084         return ret;
2085 err_free_update:
2086         bch2_btree_update_free(as);
2087         goto err;
2088 }
2089
2090 /* Init code: */
2091
2092 /*
2093  * Only for filesystem bringup, when first reading the btree roots or allocating
2094  * btree roots when initializing a new filesystem:
2095  */
2096 void bch2_btree_set_root_for_read(struct bch_fs *c, struct btree *b)
2097 {
2098         BUG_ON(btree_node_root(c, b));
2099
2100         __bch2_btree_set_root_inmem(c, b);
2101 }
2102
2103 void bch2_btree_root_alloc(struct bch_fs *c, enum btree_id id)
2104 {
2105         struct closure cl;
2106         struct btree *b;
2107         int ret;
2108
2109         closure_init_stack(&cl);
2110
2111         do {
2112                 ret = bch2_btree_cache_cannibalize_lock(c, &cl);
2113                 closure_sync(&cl);
2114         } while (ret);
2115
2116         b = bch2_btree_node_mem_alloc(c);
2117         bch2_btree_cache_cannibalize_unlock(c);
2118
2119         set_btree_node_fake(b);
2120         b->level        = 0;
2121         b->btree_id     = id;
2122
2123         bkey_btree_ptr_init(&b->key);
2124         b->key.k.p = POS_MAX;
2125         *((u64 *) bkey_i_to_btree_ptr(&b->key)->v.start) = U64_MAX - id;
2126
2127         bch2_bset_init_first(b, &b->data->keys);
2128         bch2_btree_build_aux_trees(b);
2129
2130         b->data->flags = 0;
2131         btree_set_min(b, POS_MIN);
2132         btree_set_max(b, POS_MAX);
2133         b->data->format = bch2_btree_calc_format(b);
2134         btree_node_set_format(b, b->data->format);
2135
2136         ret = bch2_btree_node_hash_insert(&c->btree_cache, b, b->level, b->btree_id);
2137         BUG_ON(ret);
2138
2139         __bch2_btree_set_root_inmem(c, b);
2140
2141         six_unlock_write(&b->lock);
2142         six_unlock_intent(&b->lock);
2143 }
2144
2145 ssize_t bch2_btree_updates_print(struct bch_fs *c, char *buf)
2146 {
2147         struct printbuf out = _PBUF(buf, PAGE_SIZE);
2148         struct btree_update *as;
2149
2150         mutex_lock(&c->btree_interior_update_lock);
2151         list_for_each_entry(as, &c->btree_interior_update_list, list)
2152                 pr_buf(&out, "%p m %u w %u r %u j %llu\n",
2153                        as,
2154                        as->mode,
2155                        as->nodes_written,
2156                        atomic_read(&as->cl.remaining) & CLOSURE_REMAINING_MASK,
2157                        as->journal.seq);
2158         mutex_unlock(&c->btree_interior_update_lock);
2159
2160         return out.pos - buf;
2161 }
2162
2163 size_t bch2_btree_interior_updates_nr_pending(struct bch_fs *c)
2164 {
2165         size_t ret = 0;
2166         struct list_head *i;
2167
2168         mutex_lock(&c->btree_interior_update_lock);
2169         list_for_each(i, &c->btree_interior_update_list)
2170                 ret++;
2171         mutex_unlock(&c->btree_interior_update_lock);
2172
2173         return ret;
2174 }