fs/bcachefs/btree_iter.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "bkey_methods.h"
   5 #include "bkey_buf.h"
   6 #include "btree_cache.h"
   7 #include "btree_iter.h"
   8 #include "btree_key_cache.h"
   9 #include "btree_locking.h"
  10 #include "btree_update.h"
  11 #include "debug.h"
  12 #include "error.h"
  13 #include "extents.h"
  14 #include "journal.h"
  15 #include "recovery.h"
  16 #include "replicas.h"
  17 #include "subvolume.h"
  18 #include "trace.h"
  19
  20 #include <linux/prefetch.h>
  21
  22 static inline void btree_path_list_remove(struct btree_trans *, struct btree_path *);
  23 static inline void btree_path_list_add(struct btree_trans *, struct btree_path *,
  24                                        struct btree_path *);
  25
  26 static struct btree_path *btree_path_alloc(struct btree_trans *, struct btree_path *);
  27
  28 /*
  29  * Unlocks before scheduling
  30  * Note: does not revalidate iterator
  31  */
  32 static inline int bch2_trans_cond_resched(struct btree_trans *trans)
  33 {
  34         if (need_resched() || race_fault()) {
  35                 bch2_trans_unlock(trans);
  36                 schedule();
  37                 return bch2_trans_relock(trans) ? 0 : -EINTR;
  38         } else {
  39                 return 0;
  40         }
  41 }
  42
  43 static inline int __btree_path_cmp(const struct btree_path *l,
  44                                    enum btree_id        r_btree_id,
  45                                    bool                 r_cached,
  46                                    struct bpos          r_pos,
  47                                    unsigned             r_level)
  48 {
  49         /*
  50          * Must match lock ordering as defined by __bch2_btree_node_lock:
  51          */
  52         return   cmp_int(l->btree_id,   r_btree_id) ?:
  53                  cmp_int((int) l->cached,       (int) r_cached) ?:
  54                  bpos_cmp(l->pos,       r_pos) ?:
  55                 -cmp_int(l->level,      r_level);
  56 }
  57
  58 static inline int btree_path_cmp(const struct btree_path *l,
  59                                  const struct btree_path *r)
  60 {
  61         return __btree_path_cmp(l, r->btree_id, r->cached, r->pos, r->level);
  62 }
  63
  64 static inline struct bpos bkey_successor(struct btree_iter *iter, struct bpos p)
  65 {
  66         /* Are we iterating over keys in all snapshots? */
  67         if (iter->flags & BTREE_ITER_ALL_SNAPSHOTS) {
  68                 p = bpos_successor(p);
  69         } else {
  70                 p = bpos_nosnap_successor(p);
  71                 p.snapshot = iter->snapshot;
  72         }
  73
  74         return p;
  75 }
  76
  77 static inline struct bpos bkey_predecessor(struct btree_iter *iter, struct bpos p)
  78 {
  79         /* Are we iterating over keys in all snapshots? */
  80         if (iter->flags & BTREE_ITER_ALL_SNAPSHOTS) {
  81                 p = bpos_predecessor(p);
  82         } else {
  83                 p = bpos_nosnap_predecessor(p);
  84                 p.snapshot = iter->snapshot;
  85         }
  86
  87         return p;
  88 }
  89
  90 static inline bool is_btree_node(struct btree_path *path, unsigned l)
  91 {
  92         return l < BTREE_MAX_DEPTH &&
  93                 (unsigned long) path->l[l].b >= 128;
  94 }
  95
  96 static inline struct bpos btree_iter_search_key(struct btree_iter *iter)
  97 {
  98         struct bpos pos = iter->pos;
  99
 100         if ((iter->flags & BTREE_ITER_IS_EXTENTS) &&
 101             bkey_cmp(pos, POS_MAX))
 102                 pos = bkey_successor(iter, pos);
 103         return pos;
 104 }
 105
 106 static inline bool btree_path_pos_before_node(struct btree_path *path,
 107                                               struct btree *b)
 108 {
 109         return bpos_cmp(path->pos, b->data->min_key) < 0;
 110 }
 111
 112 static inline bool btree_path_pos_after_node(struct btree_path *path,
 113                                              struct btree *b)
 114 {
 115         return bpos_cmp(b->key.k.p, path->pos) < 0;
 116 }
 117
 118 static inline bool btree_path_pos_in_node(struct btree_path *path,
 119                                           struct btree *b)
 120 {
 121         return path->btree_id == b->c.btree_id &&
 122                 !btree_path_pos_before_node(path, b) &&
 123                 !btree_path_pos_after_node(path, b);
 124 }
 125
 126 /* Btree node locking: */
 127
 128 void bch2_btree_node_unlock_write(struct btree_trans *trans,
 129                         struct btree_path *path, struct btree *b)
 130 {
 131         bch2_btree_node_unlock_write_inlined(trans, path, b);
 132 }
 133
 134 void __bch2_btree_node_lock_write(struct btree_trans *trans, struct btree *b)
 135 {
 136         struct btree_path *linked;
 137         unsigned readers = 0;
 138
 139         trans_for_each_path(trans, linked)
 140                 if (linked->l[b->c.level].b == b &&
 141                     btree_node_read_locked(linked, b->c.level))
 142                         readers++;
 143
 144         /*
 145          * Must drop our read locks before calling six_lock_write() -
 146          * six_unlock() won't do wakeups until the reader count
 147          * goes to 0, and it's safe because we have the node intent
 148          * locked:
 149          */
 150         if (!b->c.lock.readers)
 151                 atomic64_sub(__SIX_VAL(read_lock, readers),
 152                              &b->c.lock.state.counter);
 153         else
 154                 this_cpu_sub(*b->c.lock.readers, readers);
 155
 156         six_lock_write(&b->c.lock, NULL, NULL);
 157
 158         if (!b->c.lock.readers)
 159                 atomic64_add(__SIX_VAL(read_lock, readers),
 160                              &b->c.lock.state.counter);
 161         else
 162                 this_cpu_add(*b->c.lock.readers, readers);
 163 }
 164
 165 bool __bch2_btree_node_relock(struct btree_trans *trans,
 166                               struct btree_path *path, unsigned level)
 167 {
 168         struct btree *b = btree_path_node(path, level);
 169         int want = __btree_lock_want(path, level);
 170
 171         if (!is_btree_node(path, level))
 172                 goto fail;
 173
 174         if (race_fault())
 175                 goto fail;
 176
 177         if (six_relock_type(&b->c.lock, want, path->l[level].lock_seq) ||
 178             (btree_node_lock_seq_matches(path, b, level) &&
 179              btree_node_lock_increment(trans, b, level, want))) {
 180                 mark_btree_node_locked(path, level, want);
 181                 return true;
 182         }
 183 fail:
 184         trace_btree_node_relock_fail(trans->fn, _RET_IP_,
 185                                      path->btree_id,
 186                                      &path->pos,
 187                                      (unsigned long) b,
 188                                      path->l[level].lock_seq,
 189                                      is_btree_node(path, level) ? b->c.lock.state.seq : 0);
 190         return false;
 191 }
 192
 193 bool bch2_btree_node_upgrade(struct btree_trans *trans,
 194                              struct btree_path *path, unsigned level)
 195 {
 196         struct btree *b = path->l[level].b;
 197
 198         if (!is_btree_node(path, level))
 199                 return false;
 200
 201         switch (btree_lock_want(path, level)) {
 202         case BTREE_NODE_UNLOCKED:
 203                 BUG_ON(btree_node_locked(path, level));
 204                 return true;
 205         case BTREE_NODE_READ_LOCKED:
 206                 BUG_ON(btree_node_intent_locked(path, level));
 207                 return bch2_btree_node_relock(trans, path, level);
 208         case BTREE_NODE_INTENT_LOCKED:
 209                 break;
 210         }
 211
 212         if (btree_node_intent_locked(path, level))
 213                 return true;
 214
 215         if (race_fault())
 216                 return false;
 217
 218         if (btree_node_locked(path, level)
 219             ? six_lock_tryupgrade(&b->c.lock)
 220             : six_relock_type(&b->c.lock, SIX_LOCK_intent, path->l[level].lock_seq))
 221                 goto success;
 222
 223         if (btree_node_lock_seq_matches(path, b, level) &&
 224             btree_node_lock_increment(trans, b, level, BTREE_NODE_INTENT_LOCKED)) {
 225                 btree_node_unlock(path, level);
 226                 goto success;
 227         }
 228
 229         return false;
 230 success:
 231         mark_btree_node_intent_locked(path, level);
 232         return true;
 233 }
 234
 235 static inline bool btree_path_get_locks(struct btree_trans *trans,
 236                                         struct btree_path *path,
 237                                         bool upgrade)
 238 {
 239         unsigned l = path->level;
 240         int fail_idx = -1;
 241
 242         do {
 243                 if (!btree_path_node(path, l))
 244                         break;
 245
 246                 if (!(upgrade
 247                       ? bch2_btree_node_upgrade(trans, path, l)
 248                       : bch2_btree_node_relock(trans, path, l)))
 249                         fail_idx = l;
 250
 251                 l++;
 252         } while (l < path->locks_want);
 253
 254         /*
 255          * When we fail to get a lock, we have to ensure that any child nodes
 256          * can't be relocked so bch2_btree_path_traverse has to walk back up to
 257          * the node that we failed to relock:
 258          */
 259         if (fail_idx >= 0) {
 260                 __bch2_btree_path_unlock(path);
 261                 btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
 262
 263                 do {
 264                         path->l[fail_idx].b = BTREE_ITER_NO_NODE_GET_LOCKS;
 265                         --fail_idx;
 266                 } while (fail_idx >= 0);
 267         }
 268
 269         if (path->uptodate == BTREE_ITER_NEED_RELOCK)
 270                 path->uptodate = BTREE_ITER_UPTODATE;
 271
 272         bch2_trans_verify_locks(trans);
 273
 274         return path->uptodate < BTREE_ITER_NEED_RELOCK;
 275 }
 276
 277 static struct bpos btree_node_pos(struct btree_bkey_cached_common *_b,
 278                                   bool cached)
 279 {
 280         return !cached
 281                 ? container_of(_b, struct btree, c)->key.k.p
 282                 : container_of(_b, struct bkey_cached, c)->key.pos;
 283 }
 284
 285 /* Slowpath: */
 286 bool __bch2_btree_node_lock(struct btree_trans *trans,
 287                             struct btree_path *path,
 288                             struct btree *b,
 289                             struct bpos pos, unsigned level,
 290                             enum six_lock_type type,
 291                             six_lock_should_sleep_fn should_sleep_fn, void *p,
 292                             unsigned long ip)
 293 {
 294         struct btree_path *linked;
 295         unsigned reason;
 296
 297         /* Check if it's safe to block: */
 298         trans_for_each_path(trans, linked) {
 299                 if (!linked->nodes_locked)
 300                         continue;
 301
 302                 /*
 303                  * Can't block taking an intent lock if we have _any_ nodes read
 304                  * locked:
 305                  *
 306                  * - Our read lock blocks another thread with an intent lock on
 307                  *   the same node from getting a write lock, and thus from
 308                  *   dropping its intent lock
 309                  *
 310                  * - And the other thread may have multiple nodes intent locked:
 311                  *   both the node we want to intent lock, and the node we
 312                  *   already have read locked - deadlock:
 313                  */
 314                 if (type == SIX_LOCK_intent &&
 315                     linked->nodes_locked != linked->nodes_intent_locked) {
 316                         reason = 1;
 317                         goto deadlock;
 318                 }
 319
 320                 if (linked->btree_id != path->btree_id) {
 321                         if (linked->btree_id < path->btree_id)
 322                                 continue;
 323
 324                         reason = 3;
 325                         goto deadlock;
 326                 }
 327
 328                 /*
 329                  * Within the same btree, non-cached paths come before cached
 330                  * paths:
 331                  */
 332                 if (linked->cached != path->cached) {
 333                         if (!linked->cached)
 334                                 continue;
 335
 336                         reason = 4;
 337                         goto deadlock;
 338                 }
 339
 340                 /*
 341                  * Interior nodes must be locked before their descendants: if
 342                  * another path has possible descendants locked of the node
 343                  * we're about to lock, it must have the ancestors locked too:
 344                  */
 345                 if (level > __fls(linked->nodes_locked)) {
 346                         reason = 5;
 347                         goto deadlock;
 348                 }
 349
 350                 /* Must lock btree nodes in key order: */
 351                 if (btree_node_locked(linked, level) &&
 352                     bpos_cmp(pos, btree_node_pos((void *) linked->l[level].b,
 353                                                  linked->cached)) <= 0) {
 354                         reason = 7;
 355                         goto deadlock;
 356                 }
 357         }
 358
 359         return btree_node_lock_type(trans, path, b, pos, level,
 360                                     type, should_sleep_fn, p);
 361 deadlock:
 362         trace_trans_restart_would_deadlock(trans->fn, ip,
 363                         trans->in_traverse_all, reason,
 364                         linked->btree_id,
 365                         linked->cached,
 366                         &linked->pos,
 367                         path->btree_id,
 368                         path->cached,
 369                         &pos);
 370         btree_trans_restart(trans);
 371         return false;
 372 }
 373
 374 /* Btree iterator locking: */
 375
 376 #ifdef CONFIG_BCACHEFS_DEBUG
 377
 378 static void bch2_btree_path_verify_locks(struct btree_path *path)
 379 {
 380         unsigned l;
 381
 382         if (!path->nodes_locked) {
 383                 BUG_ON(path->uptodate == BTREE_ITER_UPTODATE &&
 384                        btree_path_node(path, path->level));
 385                 return;
 386         }
 387
 388         for (l = 0; btree_path_node(path, l); l++)
 389                 BUG_ON(btree_lock_want(path, l) !=
 390                        btree_node_locked_type(path, l));
 391 }
 392
 393 void bch2_trans_verify_locks(struct btree_trans *trans)
 394 {
 395         struct btree_path *path;
 396
 397         trans_for_each_path(trans, path)
 398                 bch2_btree_path_verify_locks(path);
 399 }
 400 #else
 401 static inline void bch2_btree_path_verify_locks(struct btree_path *path) {}
 402 #endif
 403
 404 /* Btree path locking: */
 405
 406 /*
 407  * Only for btree_cache.c - only relocks intent locks
 408  */
 409 bool bch2_btree_path_relock_intent(struct btree_trans *trans,
 410                                    struct btree_path *path)
 411 {
 412         unsigned l;
 413
 414         for (l = path->level;
 415              l < path->locks_want && btree_path_node(path, l);
 416              l++) {
 417                 if (!bch2_btree_node_relock(trans, path, l)) {
 418                         __bch2_btree_path_unlock(path);
 419                         btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
 420                         trace_trans_restart_relock_path_intent(trans->fn, _RET_IP_,
 421                                                    path->btree_id, &path->pos);
 422                         btree_trans_restart(trans);
 423                         return false;
 424                 }
 425         }
 426
 427         return true;
 428 }
 429
 430 noinline __flatten
 431 static bool __bch2_btree_path_relock(struct btree_trans *trans,
 432                         struct btree_path *path, unsigned long trace_ip)
 433 {
 434         bool ret = btree_path_get_locks(trans, path, false);
 435
 436         if (!ret) {
 437                 trace_trans_restart_relock_path(trans->fn, trace_ip,
 438                                                 path->btree_id, &path->pos);
 439                 btree_trans_restart(trans);
 440         }
 441         return ret;
 442 }
 443
 444 static inline bool bch2_btree_path_relock(struct btree_trans *trans,
 445                         struct btree_path *path, unsigned long trace_ip)
 446 {
 447         return btree_node_locked(path, path->level)
 448                 ? true
 449                 : __bch2_btree_path_relock(trans, path, trace_ip);
 450 }
 451
 452 bool __bch2_btree_path_upgrade(struct btree_trans *trans,
 453                                struct btree_path *path,
 454                                unsigned new_locks_want)
 455 {
 456         struct btree_path *linked;
 457
 458         EBUG_ON(path->locks_want >= new_locks_want);
 459
 460         path->locks_want = new_locks_want;
 461
 462         if (btree_path_get_locks(trans, path, true))
 463                 return true;
 464
 465         /*
 466          * XXX: this is ugly - we'd prefer to not be mucking with other
 467          * iterators in the btree_trans here.
 468          *
 469          * On failure to upgrade the iterator, setting iter->locks_want and
 470          * calling get_locks() is sufficient to make bch2_btree_path_traverse()
 471          * get the locks we want on transaction restart.
 472          *
 473          * But if this iterator was a clone, on transaction restart what we did
 474          * to this iterator isn't going to be preserved.
 475          *
 476          * Possibly we could add an iterator field for the parent iterator when
 477          * an iterator is a copy - for now, we'll just upgrade any other
 478          * iterators with the same btree id.
 479          *
 480          * The code below used to be needed to ensure ancestor nodes get locked
 481          * before interior nodes - now that's handled by
 482          * bch2_btree_path_traverse_all().
 483          */
 484         if (!path->cached && !trans->in_traverse_all)
 485                 trans_for_each_path(trans, linked)
 486                         if (linked != path &&
 487                             linked->cached == path->cached &&
 488                             linked->btree_id == path->btree_id &&
 489                             linked->locks_want < new_locks_want) {
 490                                 linked->locks_want = new_locks_want;
 491                                 btree_path_get_locks(trans, linked, true);
 492                         }
 493
 494         return false;
 495 }
 496
 497 void __bch2_btree_path_downgrade(struct btree_path *path,
 498                                  unsigned new_locks_want)
 499 {
 500         unsigned l;
 501
 502         EBUG_ON(path->locks_want < new_locks_want);
 503
 504         path->locks_want = new_locks_want;
 505
 506         while (path->nodes_locked &&
 507                (l = __fls(path->nodes_locked)) >= path->locks_want) {
 508                 if (l > path->level) {
 509                         btree_node_unlock(path, l);
 510                 } else {
 511                         if (btree_node_intent_locked(path, l)) {
 512                                 six_lock_downgrade(&path->l[l].b->c.lock);
 513                                 path->nodes_intent_locked ^= 1 << l;
 514                         }
 515                         break;
 516                 }
 517         }
 518
 519         bch2_btree_path_verify_locks(path);
 520 }
 521
 522 void bch2_trans_downgrade(struct btree_trans *trans)
 523 {
 524         struct btree_path *path;
 525
 526         trans_for_each_path(trans, path)
 527                 bch2_btree_path_downgrade(path);
 528 }
 529
 530 /* Btree transaction locking: */
 531
 532 bool bch2_trans_relock(struct btree_trans *trans)
 533 {
 534         struct btree_path *path;
 535
 536         if (unlikely(trans->restarted))
 537                 return false;
 538
 539         trans_for_each_path(trans, path)
 540                 if (path->should_be_locked &&
 541                     !bch2_btree_path_relock(trans, path, _RET_IP_)) {
 542                         trace_trans_restart_relock(trans->fn, _RET_IP_,
 543                                         path->btree_id, &path->pos);
 544                         BUG_ON(!trans->restarted);
 545                         return false;
 546                 }
 547         return true;
 548 }
 549
 550 void bch2_trans_unlock(struct btree_trans *trans)
 551 {
 552         struct btree_path *path;
 553
 554         trans_for_each_path(trans, path)
 555                 __bch2_btree_path_unlock(path);
 556 }
 557
 558 /* Btree iterator: */
 559
 560 #ifdef CONFIG_BCACHEFS_DEBUG
 561
 562 static void bch2_btree_path_verify_cached(struct btree_trans *trans,
 563                                           struct btree_path *path)
 564 {
 565         struct bkey_cached *ck;
 566         bool locked = btree_node_locked(path, 0);
 567
 568         if (!bch2_btree_node_relock(trans, path, 0))
 569                 return;
 570
 571         ck = (void *) path->l[0].b;
 572         BUG_ON(ck->key.btree_id != path->btree_id ||
 573                bkey_cmp(ck->key.pos, path->pos));
 574
 575         if (!locked)
 576                 btree_node_unlock(path, 0);
 577 }
 578
 579 static void bch2_btree_path_verify_level(struct btree_trans *trans,
 580                                 struct btree_path *path, unsigned level)
 581 {
 582         struct btree_path_level *l;
 583         struct btree_node_iter tmp;
 584         bool locked;
 585         struct bkey_packed *p, *k;
 586         struct printbuf buf1 = PRINTBUF;
 587         struct printbuf buf2 = PRINTBUF;
 588         struct printbuf buf3 = PRINTBUF;
 589         const char *msg;
 590
 591         if (!bch2_debug_check_iterators)
 592                 return;
 593
 594         l       = &path->l[level];
 595         tmp     = l->iter;
 596         locked  = btree_node_locked(path, level);
 597
 598         if (path->cached) {
 599                 if (!level)
 600                         bch2_btree_path_verify_cached(trans, path);
 601                 return;
 602         }
 603
 604         if (!btree_path_node(path, level))
 605                 return;
 606
 607         if (!bch2_btree_node_relock(trans, path, level))
 608                 return;
 609
 610         BUG_ON(!btree_path_pos_in_node(path, l->b));
 611
 612         bch2_btree_node_iter_verify(&l->iter, l->b);
 613
 614         /*
 615          * For interior nodes, the iterator will have skipped past deleted keys:
 616          */
 617         p = level
 618                 ? bch2_btree_node_iter_prev(&tmp, l->b)
 619                 : bch2_btree_node_iter_prev_all(&tmp, l->b);
 620         k = bch2_btree_node_iter_peek_all(&l->iter, l->b);
 621
 622         if (p && bkey_iter_pos_cmp(l->b, p, &path->pos) >= 0) {
 623                 msg = "before";
 624                 goto err;
 625         }
 626
 627         if (k && bkey_iter_pos_cmp(l->b, k, &path->pos) < 0) {
 628                 msg = "after";
 629                 goto err;
 630         }
 631
 632         if (!locked)
 633                 btree_node_unlock(path, level);
 634         return;
 635 err:
 636         bch2_bpos_to_text(&buf1, path->pos);
 637
 638         if (p) {
 639                 struct bkey uk = bkey_unpack_key(l->b, p);
 640                 bch2_bkey_to_text(&buf2, &uk);
 641         } else {
 642                 pr_buf(&buf2, "(none)");
 643         }
 644
 645         if (k) {
 646                 struct bkey uk = bkey_unpack_key(l->b, k);
 647                 bch2_bkey_to_text(&buf3, &uk);
 648         } else {
 649                 pr_buf(&buf3, "(none)");
 650         }
 651
 652         panic("path should be %s key at level %u:\n"
 653               "path pos %s\n"
 654               "prev key %s\n"
 655               "cur  key %s\n",
 656               msg, level, buf1.buf, buf2.buf, buf3.buf);
 657 }
 658
 659 static void bch2_btree_path_verify(struct btree_trans *trans,
 660                                    struct btree_path *path)
 661 {
 662         struct bch_fs *c = trans->c;
 663         unsigned i;
 664
 665         EBUG_ON(path->btree_id >= BTREE_ID_NR);
 666
 667         for (i = 0; i < (!path->cached ? BTREE_MAX_DEPTH : 1); i++) {
 668                 if (!path->l[i].b) {
 669                         BUG_ON(!path->cached &&
 670                                c->btree_roots[path->btree_id].b->c.level > i);
 671                         break;
 672                 }
 673
 674                 bch2_btree_path_verify_level(trans, path, i);
 675         }
 676
 677         bch2_btree_path_verify_locks(path);
 678 }
 679
 680 void bch2_trans_verify_paths(struct btree_trans *trans)
 681 {
 682         struct btree_path *path;
 683
 684         trans_for_each_path(trans, path)
 685                 bch2_btree_path_verify(trans, path);
 686 }
 687
 688 static void bch2_btree_iter_verify(struct btree_iter *iter)
 689 {
 690         struct btree_trans *trans = iter->trans;
 691
 692         BUG_ON(iter->btree_id >= BTREE_ID_NR);
 693
 694         BUG_ON(!!(iter->flags & BTREE_ITER_CACHED) != iter->path->cached);
 695
 696         BUG_ON((iter->flags & BTREE_ITER_IS_EXTENTS) &&
 697                (iter->flags & BTREE_ITER_ALL_SNAPSHOTS));
 698
 699         BUG_ON(!(iter->flags & __BTREE_ITER_ALL_SNAPSHOTS) &&
 700                (iter->flags & BTREE_ITER_ALL_SNAPSHOTS) &&
 701                !btree_type_has_snapshots(iter->btree_id));
 702
 703         if (iter->update_path)
 704                 bch2_btree_path_verify(trans, iter->update_path);
 705         bch2_btree_path_verify(trans, iter->path);
 706 }
 707
 708 static void bch2_btree_iter_verify_entry_exit(struct btree_iter *iter)
 709 {
 710         BUG_ON((iter->flags & BTREE_ITER_FILTER_SNAPSHOTS) &&
 711                !iter->pos.snapshot);
 712
 713         BUG_ON(!(iter->flags & BTREE_ITER_ALL_SNAPSHOTS) &&
 714                iter->pos.snapshot != iter->snapshot);
 715
 716         BUG_ON(bkey_cmp(iter->pos, bkey_start_pos(&iter->k)) < 0 ||
 717                bkey_cmp(iter->pos, iter->k.p) > 0);
 718 }
 719
 720 static int bch2_btree_iter_verify_ret(struct btree_iter *iter, struct bkey_s_c k)
 721 {
 722         struct btree_trans *trans = iter->trans;
 723         struct btree_iter copy;
 724         struct bkey_s_c prev;
 725         int ret = 0;
 726
 727         if (!bch2_debug_check_iterators)
 728                 return 0;
 729
 730         if (!(iter->flags & BTREE_ITER_FILTER_SNAPSHOTS))
 731                 return 0;
 732
 733         if (bkey_err(k) || !k.k)
 734                 return 0;
 735
 736         BUG_ON(!bch2_snapshot_is_ancestor(trans->c,
 737                                           iter->snapshot,
 738                                           k.k->p.snapshot));
 739
 740         bch2_trans_iter_init(trans, &copy, iter->btree_id, iter->pos,
 741                              BTREE_ITER_NOPRESERVE|
 742                              BTREE_ITER_ALL_SNAPSHOTS);
 743         prev = bch2_btree_iter_prev(&copy);
 744         if (!prev.k)
 745                 goto out;
 746
 747         ret = bkey_err(prev);
 748         if (ret)
 749                 goto out;
 750
 751         if (!bkey_cmp(prev.k->p, k.k->p) &&
 752             bch2_snapshot_is_ancestor(trans->c, iter->snapshot,
 753                                       prev.k->p.snapshot) > 0) {
 754                 struct printbuf buf1 = PRINTBUF, buf2 = PRINTBUF;
 755
 756                 bch2_bkey_to_text(&buf1, k.k);
 757                 bch2_bkey_to_text(&buf2, prev.k);
 758
 759                 panic("iter snap %u\n"
 760                       "k    %s\n"
 761                       "prev %s\n",
 762                       iter->snapshot,
 763                       buf1.buf, buf2.buf);
 764         }
 765 out:
 766         bch2_trans_iter_exit(trans, &copy);
 767         return ret;
 768 }
 769
 770 void bch2_assert_pos_locked(struct btree_trans *trans, enum btree_id id,
 771                             struct bpos pos, bool key_cache)
 772 {
 773         struct btree_path *path;
 774         unsigned idx;
 775         struct printbuf buf = PRINTBUF;
 776
 777         trans_for_each_path_inorder(trans, path, idx) {
 778                 int cmp = cmp_int(path->btree_id, id) ?:
 779                         cmp_int(path->cached, key_cache);
 780
 781                 if (cmp > 0)
 782                         break;
 783                 if (cmp < 0)
 784                         continue;
 785
 786                 if (!(path->nodes_locked & 1) ||
 787                     !path->should_be_locked)
 788                         continue;
 789
 790                 if (!key_cache) {
 791                         if (bkey_cmp(pos, path->l[0].b->data->min_key) >= 0 &&
 792                             bkey_cmp(pos, path->l[0].b->key.k.p) <= 0)
 793                                 return;
 794                 } else {
 795                         if (!bkey_cmp(pos, path->pos))
 796                                 return;
 797                 }
 798         }
 799
 800         bch2_dump_trans_paths_updates(trans);
 801         bch2_bpos_to_text(&buf, pos);
 802
 803         panic("not locked: %s %s%s\n",
 804               bch2_btree_ids[id], buf.buf,
 805               key_cache ? " cached" : "");
 806 }
 807
 808 #else
 809
 810 static inline void bch2_btree_path_verify_level(struct btree_trans *trans,
 811                                                 struct btree_path *path, unsigned l) {}
 812 static inline void bch2_btree_path_verify(struct btree_trans *trans,
 813                                           struct btree_path *path) {}
 814 static inline void bch2_btree_iter_verify(struct btree_iter *iter) {}
 815 static inline void bch2_btree_iter_verify_entry_exit(struct btree_iter *iter) {}
 816 static inline int bch2_btree_iter_verify_ret(struct btree_iter *iter, struct bkey_s_c k) { return 0; }
 817
 818 #endif
 819
 820 /* Btree path: fixups after btree updates */
 821
 822 static void btree_node_iter_set_set_pos(struct btree_node_iter *iter,
 823                                         struct btree *b,
 824                                         struct bset_tree *t,
 825                                         struct bkey_packed *k)
 826 {
 827         struct btree_node_iter_set *set;
 828
 829         btree_node_iter_for_each(iter, set)
 830                 if (set->end == t->end_offset) {
 831                         set->k = __btree_node_key_to_offset(b, k);
 832                         bch2_btree_node_iter_sort(iter, b);
 833                         return;
 834                 }
 835
 836         bch2_btree_node_iter_push(iter, b, k, btree_bkey_last(b, t));
 837 }
 838
 839 static void __bch2_btree_path_fix_key_modified(struct btree_path *path,
 840                                                struct btree *b,
 841                                                struct bkey_packed *where)
 842 {
 843         struct btree_path_level *l = &path->l[b->c.level];
 844
 845         if (where != bch2_btree_node_iter_peek_all(&l->iter, l->b))
 846                 return;
 847
 848         if (bkey_iter_pos_cmp(l->b, where, &path->pos) < 0)
 849                 bch2_btree_node_iter_advance(&l->iter, l->b);
 850 }
 851
 852 void bch2_btree_path_fix_key_modified(struct btree_trans *trans,
 853                                       struct btree *b,
 854                                       struct bkey_packed *where)
 855 {
 856         struct btree_path *path;
 857
 858         trans_for_each_path_with_node(trans, b, path) {
 859                 __bch2_btree_path_fix_key_modified(path, b, where);
 860                 bch2_btree_path_verify_level(trans, path, b->c.level);
 861         }
 862 }
 863
 864 static void __bch2_btree_node_iter_fix(struct btree_path *path,
 865                                        struct btree *b,
 866                                        struct btree_node_iter *node_iter,
 867                                        struct bset_tree *t,
 868                                        struct bkey_packed *where,
 869                                        unsigned clobber_u64s,
 870                                        unsigned new_u64s)
 871 {
 872         const struct bkey_packed *end = btree_bkey_last(b, t);
 873         struct btree_node_iter_set *set;
 874         unsigned offset = __btree_node_key_to_offset(b, where);
 875         int shift = new_u64s - clobber_u64s;
 876         unsigned old_end = t->end_offset - shift;
 877         unsigned orig_iter_pos = node_iter->data[0].k;
 878         bool iter_current_key_modified =
 879                 orig_iter_pos >= offset &&
 880                 orig_iter_pos <= offset + clobber_u64s;
 881
 882         btree_node_iter_for_each(node_iter, set)
 883                 if (set->end == old_end)
 884                         goto found;
 885
 886         /* didn't find the bset in the iterator - might have to readd it: */
 887         if (new_u64s &&
 888             bkey_iter_pos_cmp(b, where, &path->pos) >= 0) {
 889                 bch2_btree_node_iter_push(node_iter, b, where, end);
 890                 goto fixup_done;
 891         } else {
 892                 /* Iterator is after key that changed */
 893                 return;
 894         }
 895 found:
 896         set->end = t->end_offset;
 897
 898         /* Iterator hasn't gotten to the key that changed yet: */
 899         if (set->k < offset)
 900                 return;
 901
 902         if (new_u64s &&
 903             bkey_iter_pos_cmp(b, where, &path->pos) >= 0) {
 904                 set->k = offset;
 905         } else if (set->k < offset + clobber_u64s) {
 906                 set->k = offset + new_u64s;
 907                 if (set->k == set->end)
 908                         bch2_btree_node_iter_set_drop(node_iter, set);
 909         } else {
 910                 /* Iterator is after key that changed */
 911                 set->k = (int) set->k + shift;
 912                 return;
 913         }
 914
 915         bch2_btree_node_iter_sort(node_iter, b);
 916 fixup_done:
 917         if (node_iter->data[0].k != orig_iter_pos)
 918                 iter_current_key_modified = true;
 919
 920         /*
 921          * When a new key is added, and the node iterator now points to that
 922          * key, the iterator might have skipped past deleted keys that should
 923          * come after the key the iterator now points to. We have to rewind to
 924          * before those deleted keys - otherwise
 925          * bch2_btree_node_iter_prev_all() breaks:
 926          */
 927         if (!bch2_btree_node_iter_end(node_iter) &&
 928             iter_current_key_modified &&
 929             b->c.level) {
 930                 struct bset_tree *t;
 931                 struct bkey_packed *k, *k2, *p;
 932
 933                 k = bch2_btree_node_iter_peek_all(node_iter, b);
 934
 935                 for_each_bset(b, t) {
 936                         bool set_pos = false;
 937
 938                         if (node_iter->data[0].end == t->end_offset)
 939                                 continue;
 940
 941                         k2 = bch2_btree_node_iter_bset_pos(node_iter, b, t);
 942
 943                         while ((p = bch2_bkey_prev_all(b, t, k2)) &&
 944                                bkey_iter_cmp(b, k, p) < 0) {
 945                                 k2 = p;
 946                                 set_pos = true;
 947                         }
 948
 949                         if (set_pos)
 950                                 btree_node_iter_set_set_pos(node_iter,
 951                                                             b, t, k2);
 952                 }
 953         }
 954 }
 955
 956 void bch2_btree_node_iter_fix(struct btree_trans *trans,
 957                               struct btree_path *path,
 958                               struct btree *b,
 959                               struct btree_node_iter *node_iter,
 960                               struct bkey_packed *where,
 961                               unsigned clobber_u64s,
 962                               unsigned new_u64s)
 963 {
 964         struct bset_tree *t = bch2_bkey_to_bset_inlined(b, where);
 965         struct btree_path *linked;
 966
 967         if (node_iter != &path->l[b->c.level].iter) {
 968                 __bch2_btree_node_iter_fix(path, b, node_iter, t,
 969                                            where, clobber_u64s, new_u64s);
 970
 971                 if (bch2_debug_check_iterators)
 972                         bch2_btree_node_iter_verify(node_iter, b);
 973         }
 974
 975         trans_for_each_path_with_node(trans, b, linked) {
 976                 __bch2_btree_node_iter_fix(linked, b,
 977                                            &linked->l[b->c.level].iter, t,
 978                                            where, clobber_u64s, new_u64s);
 979                 bch2_btree_path_verify_level(trans, linked, b->c.level);
 980         }
 981 }
 982
 983 /* Btree path level: pointer to a particular btree node and node iter */
 984
 985 static inline struct bkey_s_c __btree_iter_unpack(struct bch_fs *c,
 986                                                   struct btree_path_level *l,
 987                                                   struct bkey *u,
 988                                                   struct bkey_packed *k)
 989 {
 990         if (unlikely(!k)) {
 991                 /*
 992                  * signal to bch2_btree_iter_peek_slot() that we're currently at
 993                  * a hole
 994                  */
 995                 u->type = KEY_TYPE_deleted;
 996                 return bkey_s_c_null;
 997         }
 998
 999         return bkey_disassemble(l->b, k, u);
1000 }
1001
1002 static inline struct bkey_s_c btree_path_level_peek_all(struct bch_fs *c,
1003                                                         struct btree_path_level *l,
1004                                                         struct bkey *u)
1005 {
1006         return __btree_iter_unpack(c, l, u,
1007                         bch2_btree_node_iter_peek_all(&l->iter, l->b));
1008 }
1009
1010 static inline struct bkey_s_c btree_path_level_peek(struct btree_trans *trans,
1011                                                     struct btree_path *path,
1012                                                     struct btree_path_level *l,
1013                                                     struct bkey *u)
1014 {
1015         struct bkey_s_c k = __btree_iter_unpack(trans->c, l, u,
1016                         bch2_btree_node_iter_peek(&l->iter, l->b));
1017
1018         path->pos = k.k ? k.k->p : l->b->key.k.p;
1019         trans->paths_sorted = false;
1020         return k;
1021 }
1022
1023 static inline struct bkey_s_c btree_path_level_prev(struct btree_trans *trans,
1024                                                     struct btree_path *path,
1025                                                     struct btree_path_level *l,
1026                                                     struct bkey *u)
1027 {
1028         struct bkey_s_c k = __btree_iter_unpack(trans->c, l, u,
1029                         bch2_btree_node_iter_prev(&l->iter, l->b));
1030
1031         path->pos = k.k ? k.k->p : l->b->data->min_key;
1032         trans->paths_sorted = false;
1033         return k;
1034 }
1035
1036 static inline bool btree_path_advance_to_pos(struct btree_path *path,
1037                                              struct btree_path_level *l,
1038                                              int max_advance)
1039 {
1040         struct bkey_packed *k;
1041         int nr_advanced = 0;
1042
1043         while ((k = bch2_btree_node_iter_peek_all(&l->iter, l->b)) &&
1044                bkey_iter_pos_cmp(l->b, k, &path->pos) < 0) {
1045                 if (max_advance > 0 && nr_advanced >= max_advance)
1046                         return false;
1047
1048                 bch2_btree_node_iter_advance(&l->iter, l->b);
1049                 nr_advanced++;
1050         }
1051
1052         return true;
1053 }
1054
1055 /*
1056  * Verify that iterator for parent node points to child node:
1057  */
1058 static void btree_path_verify_new_node(struct btree_trans *trans,
1059                                        struct btree_path *path, struct btree *b)
1060 {
1061         struct bch_fs *c = trans->c;
1062         struct btree_path_level *l;
1063         unsigned plevel;
1064         bool parent_locked;
1065         struct bkey_packed *k;
1066
1067         if (!IS_ENABLED(CONFIG_BCACHEFS_DEBUG))
1068                 return;
1069
1070         if (trans->journal_replay_not_finished)
1071                 return;
1072
1073         plevel = b->c.level + 1;
1074         if (!btree_path_node(path, plevel))
1075                 return;
1076
1077         parent_locked = btree_node_locked(path, plevel);
1078
1079         if (!bch2_btree_node_relock(trans, path, plevel))
1080                 return;
1081
1082         l = &path->l[plevel];
1083         k = bch2_btree_node_iter_peek_all(&l->iter, l->b);
1084         if (!k ||
1085             bkey_deleted(k) ||
1086             bkey_cmp_left_packed(l->b, k, &b->key.k.p)) {
1087                 struct printbuf buf1 = PRINTBUF;
1088                 struct printbuf buf2 = PRINTBUF;
1089                 struct printbuf buf3 = PRINTBUF;
1090                 struct printbuf buf4 = PRINTBUF;
1091                 struct bkey uk = bkey_unpack_key(b, k);
1092
1093                 bch2_dump_btree_node(c, l->b);
1094                 bch2_bpos_to_text(&buf1, path->pos);
1095                 bch2_bkey_to_text(&buf2, &uk);
1096                 bch2_bpos_to_text(&buf3, b->data->min_key);
1097                 bch2_bpos_to_text(&buf3, b->data->max_key);
1098                 panic("parent iter doesn't point to new node:\n"
1099                       "iter pos %s %s\n"
1100                       "iter key %s\n"
1101                       "new node %s-%s\n",
1102                       bch2_btree_ids[path->btree_id],
1103                       buf1.buf, buf2.buf, buf3.buf, buf4.buf);
1104         }
1105
1106         if (!parent_locked)
1107                 btree_node_unlock(path, plevel);
1108 }
1109
1110 static inline void __btree_path_level_init(struct btree_path *path,
1111                                            unsigned level)
1112 {
1113         struct btree_path_level *l = &path->l[level];
1114
1115         bch2_btree_node_iter_init(&l->iter, l->b, &path->pos);
1116
1117         /*
1118          * Iterators to interior nodes should always be pointed at the first non
1119          * whiteout:
1120          */
1121         if (level)
1122                 bch2_btree_node_iter_peek(&l->iter, l->b);
1123 }
1124
1125 static inline void btree_path_level_init(struct btree_trans *trans,
1126                                          struct btree_path *path,
1127                                          struct btree *b)
1128 {
1129         BUG_ON(path->cached);
1130
1131         btree_path_verify_new_node(trans, path, b);
1132
1133         EBUG_ON(!btree_path_pos_in_node(path, b));
1134         EBUG_ON(b->c.lock.state.seq & 1);
1135
1136         path->l[b->c.level].lock_seq = b->c.lock.state.seq;
1137         path->l[b->c.level].b = b;
1138         __btree_path_level_init(path, b->c.level);
1139 }
1140
1141 /* Btree path: fixups after btree node updates: */
1142
1143 /*
1144  * A btree node is being replaced - update the iterator to point to the new
1145  * node:
1146  */
1147 void bch2_trans_node_add(struct btree_trans *trans, struct btree *b)
1148 {
1149         struct btree_path *path;
1150
1151         trans_for_each_path(trans, path)
1152                 if (!path->cached &&
1153                     btree_path_pos_in_node(path, b)) {
1154                         enum btree_node_locked_type t =
1155                                 btree_lock_want(path, b->c.level);
1156
1157                         if (path->nodes_locked &&
1158                             t != BTREE_NODE_UNLOCKED) {
1159                                 btree_node_unlock(path, b->c.level);
1160                                 six_lock_increment(&b->c.lock, (enum six_lock_type) t);
1161                                 mark_btree_node_locked(path, b->c.level, (enum six_lock_type) t);
1162                         }
1163
1164                         btree_path_level_init(trans, path, b);
1165                 }
1166 }
1167
1168 /*
1169  * A btree node has been modified in such a way as to invalidate iterators - fix
1170  * them:
1171  */
1172 void bch2_trans_node_reinit_iter(struct btree_trans *trans, struct btree *b)
1173 {
1174         struct btree_path *path;
1175
1176         trans_for_each_path_with_node(trans, b, path)
1177                 __btree_path_level_init(path, b->c.level);
1178 }
1179
1180 /* Btree path: traverse, set_pos: */
1181
1182 static int lock_root_check_fn(struct six_lock *lock, void *p)
1183 {
1184         struct btree *b = container_of(lock, struct btree, c.lock);
1185         struct btree **rootp = p;
1186
1187         return b == *rootp ? 0 : -1;
1188 }
1189
1190 static inline int btree_path_lock_root(struct btree_trans *trans,
1191                                        struct btree_path *path,
1192                                        unsigned depth_want,
1193                                        unsigned long trace_ip)
1194 {
1195         struct bch_fs *c = trans->c;
1196         struct btree *b, **rootp = &c->btree_roots[path->btree_id].b;
1197         enum six_lock_type lock_type;
1198         unsigned i;
1199
1200         EBUG_ON(path->nodes_locked);
1201
1202         while (1) {
1203                 b = READ_ONCE(*rootp);
1204                 path->level = READ_ONCE(b->c.level);
1205
1206                 if (unlikely(path->level < depth_want)) {
1207                         /*
1208                          * the root is at a lower depth than the depth we want:
1209                          * got to the end of the btree, or we're walking nodes
1210                          * greater than some depth and there are no nodes >=
1211                          * that depth
1212                          */
1213                         path->level = depth_want;
1214                         for (i = path->level; i < BTREE_MAX_DEPTH; i++)
1215                                 path->l[i].b = NULL;
1216                         return 1;
1217                 }
1218
1219                 lock_type = __btree_lock_want(path, path->level);
1220                 if (unlikely(!btree_node_lock(trans, path, b, SPOS_MAX,
1221                                               path->level, lock_type,
1222                                               lock_root_check_fn, rootp,
1223                                               trace_ip))) {
1224                         if (trans->restarted)
1225                                 return -EINTR;
1226                         continue;
1227                 }
1228
1229                 if (likely(b == READ_ONCE(*rootp) &&
1230                            b->c.level == path->level &&
1231                            !race_fault())) {
1232                         for (i = 0; i < path->level; i++)
1233                                 path->l[i].b = BTREE_ITER_NO_NODE_LOCK_ROOT;
1234                         path->l[path->level].b = b;
1235                         for (i = path->level + 1; i < BTREE_MAX_DEPTH; i++)
1236                                 path->l[i].b = NULL;
1237
1238                         mark_btree_node_locked(path, path->level, lock_type);
1239                         btree_path_level_init(trans, path, b);
1240                         return 0;
1241                 }
1242
1243                 six_unlock_type(&b->c.lock, lock_type);
1244         }
1245 }
1246
1247 noinline
1248 static int btree_path_prefetch(struct btree_trans *trans, struct btree_path *path)
1249 {
1250         struct bch_fs *c = trans->c;
1251         struct btree_path_level *l = path_l(path);
1252         struct btree_node_iter node_iter = l->iter;
1253         struct bkey_packed *k;
1254         struct bkey_buf tmp;
1255         unsigned nr = test_bit(BCH_FS_STARTED, &c->flags)
1256                 ? (path->level > 1 ? 0 :  2)
1257                 : (path->level > 1 ? 1 : 16);
1258         bool was_locked = btree_node_locked(path, path->level);
1259         int ret = 0;
1260
1261         bch2_bkey_buf_init(&tmp);
1262
1263         while (nr && !ret) {
1264                 if (!bch2_btree_node_relock(trans, path, path->level))
1265                         break;
1266
1267                 bch2_btree_node_iter_advance(&node_iter, l->b);
1268                 k = bch2_btree_node_iter_peek(&node_iter, l->b);
1269                 if (!k)
1270                         break;
1271
1272                 bch2_bkey_buf_unpack(&tmp, c, l->b, k);
1273                 ret = bch2_btree_node_prefetch(c, trans, path, tmp.k, path->btree_id,
1274                                                path->level - 1);
1275         }
1276
1277         if (!was_locked)
1278                 btree_node_unlock(path, path->level);
1279
1280         bch2_bkey_buf_exit(&tmp, c);
1281         return ret;
1282 }
1283
1284 static int btree_path_prefetch_j(struct btree_trans *trans, struct btree_path *path,
1285                                  struct btree_and_journal_iter *jiter)
1286 {
1287         struct bch_fs *c = trans->c;
1288         struct bkey_s_c k;
1289         struct bkey_buf tmp;
1290         unsigned nr = test_bit(BCH_FS_STARTED, &c->flags)
1291                 ? (path->level > 1 ? 0 :  2)
1292                 : (path->level > 1 ? 1 : 16);
1293         bool was_locked = btree_node_locked(path, path->level);
1294         int ret = 0;
1295
1296         bch2_bkey_buf_init(&tmp);
1297
1298         while (nr && !ret) {
1299                 if (!bch2_btree_node_relock(trans, path, path->level))
1300                         break;
1301
1302                 bch2_btree_and_journal_iter_advance(jiter);
1303                 k = bch2_btree_and_journal_iter_peek(jiter);
1304                 if (!k.k)
1305                         break;
1306
1307                 bch2_bkey_buf_reassemble(&tmp, c, k);
1308                 ret = bch2_btree_node_prefetch(c, trans, path, tmp.k, path->btree_id,
1309                                                path->level - 1);
1310         }
1311
1312         if (!was_locked)
1313                 btree_node_unlock(path, path->level);
1314
1315         bch2_bkey_buf_exit(&tmp, c);
1316         return ret;
1317 }
1318
1319 static noinline void btree_node_mem_ptr_set(struct btree_trans *trans,
1320                                             struct btree_path *path,
1321                                             unsigned plevel, struct btree *b)
1322 {
1323         struct btree_path_level *l = &path->l[plevel];
1324         bool locked = btree_node_locked(path, plevel);
1325         struct bkey_packed *k;
1326         struct bch_btree_ptr_v2 *bp;
1327
1328         if (!bch2_btree_node_relock(trans, path, plevel))
1329                 return;
1330
1331         k = bch2_btree_node_iter_peek_all(&l->iter, l->b);
1332         BUG_ON(k->type != KEY_TYPE_btree_ptr_v2);
1333
1334         bp = (void *) bkeyp_val(&l->b->format, k);
1335         bp->mem_ptr = (unsigned long)b;
1336
1337         if (!locked)
1338                 btree_node_unlock(path, plevel);
1339 }
1340
1341 static noinline int btree_node_iter_and_journal_peek(struct btree_trans *trans,
1342                                                      struct btree_path *path,
1343                                                      unsigned flags,
1344                                                      struct bkey_buf *out)
1345 {
1346         struct bch_fs *c = trans->c;
1347         struct btree_path_level *l = path_l(path);
1348         struct btree_and_journal_iter jiter;
1349         struct bkey_s_c k;
1350         int ret = 0;
1351
1352         __bch2_btree_and_journal_iter_init_node_iter(&jiter, c, l->b, l->iter, path->pos);
1353
1354         k = bch2_btree_and_journal_iter_peek(&jiter);
1355
1356         bch2_bkey_buf_reassemble(out, c, k);
1357
1358         if (flags & BTREE_ITER_PREFETCH)
1359                 ret = btree_path_prefetch_j(trans, path, &jiter);
1360
1361         bch2_btree_and_journal_iter_exit(&jiter);
1362         return ret;
1363 }
1364
1365 static __always_inline int btree_path_down(struct btree_trans *trans,
1366                                            struct btree_path *path,
1367                                            unsigned flags,
1368                                            unsigned long trace_ip)
1369 {
1370         struct bch_fs *c = trans->c;
1371         struct btree_path_level *l = path_l(path);
1372         struct btree *b;
1373         unsigned level = path->level - 1;
1374         enum six_lock_type lock_type = __btree_lock_want(path, level);
1375         struct bkey_buf tmp;
1376         int ret;
1377
1378         EBUG_ON(!btree_node_locked(path, path->level));
1379
1380         bch2_bkey_buf_init(&tmp);
1381
1382         if (unlikely(trans->journal_replay_not_finished)) {
1383                 ret = btree_node_iter_and_journal_peek(trans, path, flags, &tmp);
1384                 if (ret)
1385                         goto err;
1386         } else {
1387                 bch2_bkey_buf_unpack(&tmp, c, l->b,
1388                                  bch2_btree_node_iter_peek(&l->iter, l->b));
1389
1390                 if (flags & BTREE_ITER_PREFETCH) {
1391                         ret = btree_path_prefetch(trans, path);
1392                         if (ret)
1393                                 goto err;
1394                 }
1395         }
1396
1397         b = bch2_btree_node_get(trans, path, tmp.k, level, lock_type, trace_ip);
1398         ret = PTR_ERR_OR_ZERO(b);
1399         if (unlikely(ret))
1400                 goto err;
1401
1402         mark_btree_node_locked(path, level, lock_type);
1403         btree_path_level_init(trans, path, b);
1404
1405         if (likely(!trans->journal_replay_not_finished &&
1406                    tmp.k->k.type == KEY_TYPE_btree_ptr_v2) &&
1407             unlikely(b != btree_node_mem_ptr(tmp.k)))
1408                 btree_node_mem_ptr_set(trans, path, level + 1, b);
1409
1410         if (btree_node_read_locked(path, level + 1))
1411                 btree_node_unlock(path, level + 1);
1412         path->level = level;
1413
1414         bch2_btree_path_verify_locks(path);
1415 err:
1416         bch2_bkey_buf_exit(&tmp, c);
1417         return ret;
1418 }
1419
1420 static int btree_path_traverse_one(struct btree_trans *, struct btree_path *,
1421                                    unsigned, unsigned long);
1422
1423 static int bch2_btree_path_traverse_all(struct btree_trans *trans)
1424 {
1425         struct bch_fs *c = trans->c;
1426         struct btree_path *path, *prev;
1427         unsigned long trace_ip = _RET_IP_;
1428         int i, ret = 0;
1429
1430         if (trans->in_traverse_all)
1431                 return -EINTR;
1432
1433         trans->in_traverse_all = true;
1434 retry_all:
1435         prev = NULL;
1436         trans->restarted = false;
1437
1438         trans_for_each_path(trans, path)
1439                 path->should_be_locked = false;
1440
1441         btree_trans_sort_paths(trans);
1442
1443         trans_for_each_path_inorder_reverse(trans, path, i) {
1444                 if (prev) {
1445                         if (path->btree_id == prev->btree_id &&
1446                             path->locks_want < prev->locks_want)
1447                                 __bch2_btree_path_upgrade(trans, path, prev->locks_want);
1448                         else if (!path->locks_want && prev->locks_want)
1449                                 __bch2_btree_path_upgrade(trans, path, 1);
1450                 }
1451
1452                 prev = path;
1453         }
1454
1455         bch2_trans_unlock(trans);
1456         cond_resched();
1457
1458         if (unlikely(trans->memory_allocation_failure)) {
1459                 struct closure cl;
1460
1461                 closure_init_stack(&cl);
1462
1463                 do {
1464                         ret = bch2_btree_cache_cannibalize_lock(c, &cl);
1465                         closure_sync(&cl);
1466                 } while (ret);
1467         }
1468
1469         /* Now, redo traversals in correct order: */
1470         i = 0;
1471         while (i < trans->nr_sorted) {
1472                 path = trans->paths + trans->sorted[i];
1473
1474                 /*
1475                  * Traversing a path can cause another path to be added at about
1476                  * the same position:
1477                  */
1478                 if (path->uptodate) {
1479                         ret = btree_path_traverse_one(trans, path, 0, _THIS_IP_);
1480                         if (ret == -EINTR || ret == -ENOMEM)
1481                                 goto retry_all;
1482                         if (ret)
1483                                 goto err;
1484                 } else {
1485                         i++;
1486                 }
1487         }
1488
1489         /*
1490          * BTREE_ITER_NEED_RELOCK is ok here - if we called bch2_trans_unlock()
1491          * and relock(), relock() won't relock since path->should_be_locked
1492          * isn't set yet, which is all fine
1493          */
1494         trans_for_each_path(trans, path)
1495                 BUG_ON(path->uptodate >= BTREE_ITER_NEED_TRAVERSE);
1496 err:
1497         bch2_btree_cache_cannibalize_unlock(c);
1498
1499         trans->in_traverse_all = false;
1500
1501         trace_trans_traverse_all(trans->fn, trace_ip);
1502         return ret;
1503 }
1504
1505 static inline bool btree_path_good_node(struct btree_trans *trans,
1506                                         struct btree_path *path,
1507                                         unsigned l, int check_pos)
1508 {
1509         if (!is_btree_node(path, l) ||
1510             !bch2_btree_node_relock(trans, path, l))
1511                 return false;
1512
1513         if (check_pos < 0 && btree_path_pos_before_node(path, path->l[l].b))
1514                 return false;
1515         if (check_pos > 0 && btree_path_pos_after_node(path, path->l[l].b))
1516                 return false;
1517         return true;
1518 }
1519
1520 static void btree_path_set_level_up(struct btree_path *path)
1521 {
1522         btree_node_unlock(path, path->level);
1523         path->l[path->level].b = BTREE_ITER_NO_NODE_UP;
1524         path->level++;
1525         btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
1526 }
1527
1528 static void btree_path_set_level_down(struct btree_trans *trans,
1529                                       struct btree_path *path,
1530                                       unsigned new_level)
1531 {
1532         unsigned l;
1533
1534         path->level = new_level;
1535
1536         for (l = path->level + 1; l < BTREE_MAX_DEPTH; l++)
1537                 if (btree_lock_want(path, l) == BTREE_NODE_UNLOCKED)
1538                         btree_node_unlock(path, l);
1539
1540         btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
1541         bch2_btree_path_verify(trans, path);
1542 }
1543
1544 static inline unsigned btree_path_up_until_good_node(struct btree_trans *trans,
1545                                                      struct btree_path *path,
1546                                                      int check_pos)
1547 {
1548         unsigned i, l = path->level;
1549
1550         while (btree_path_node(path, l) &&
1551                !btree_path_good_node(trans, path, l, check_pos)) {
1552                 btree_node_unlock(path, l);
1553                 path->l[l].b = BTREE_ITER_NO_NODE_UP;
1554                 l++;
1555         }
1556
1557         /* If we need intent locks, take them too: */
1558         for (i = l + 1;
1559              i < path->locks_want && btree_path_node(path, i);
1560              i++)
1561                 if (!bch2_btree_node_relock(trans, path, i))
1562                         while (l <= i) {
1563                                 btree_node_unlock(path, l);
1564                                 path->l[l].b = BTREE_ITER_NO_NODE_UP;
1565                                 l++;
1566                         }
1567
1568         return l;
1569 }
1570
1571 /*
1572  * This is the main state machine for walking down the btree - walks down to a
1573  * specified depth
1574  *
1575  * Returns 0 on success, -EIO on error (error reading in a btree node).
1576  *
1577  * On error, caller (peek_node()/peek_key()) must return NULL; the error is
1578  * stashed in the iterator and returned from bch2_trans_exit().
1579  */
1580 static int btree_path_traverse_one(struct btree_trans *trans,
1581                                    struct btree_path *path,
1582                                    unsigned flags,
1583                                    unsigned long trace_ip)
1584 {
1585         unsigned depth_want = path->level;
1586         int ret = 0;
1587
1588         if (unlikely(trans->restarted)) {
1589                 ret = -EINTR;
1590                 goto out;
1591         }
1592
1593         /*
1594          * Ensure we obey path->should_be_locked: if it's set, we can't unlock
1595          * and re-traverse the path without a transaction restart:
1596          */
1597         if (path->should_be_locked) {
1598                 ret = bch2_btree_path_relock(trans, path, trace_ip) ? 0 : -EINTR;
1599                 goto out;
1600         }
1601
1602         if (path->cached) {
1603                 ret = bch2_btree_path_traverse_cached(trans, path, flags);
1604                 goto out;
1605         }
1606
1607         if (unlikely(path->level >= BTREE_MAX_DEPTH))
1608                 goto out;
1609
1610         path->level = btree_path_up_until_good_node(trans, path, 0);
1611
1612         /*
1613          * Note: path->nodes[path->level] may be temporarily NULL here - that
1614          * would indicate to other code that we got to the end of the btree,
1615          * here it indicates that relocking the root failed - it's critical that
1616          * btree_path_lock_root() comes next and that it can't fail
1617          */
1618         while (path->level > depth_want) {
1619                 ret = btree_path_node(path, path->level)
1620                         ? btree_path_down(trans, path, flags, trace_ip)
1621                         : btree_path_lock_root(trans, path, depth_want, trace_ip);
1622                 if (unlikely(ret)) {
1623                         if (ret == 1) {
1624                                 /*
1625                                  * No nodes at this level - got to the end of
1626                                  * the btree:
1627                                  */
1628                                 ret = 0;
1629                                 goto out;
1630                         }
1631
1632                         __bch2_btree_path_unlock(path);
1633                         path->level = depth_want;
1634
1635                         if (ret == -EIO)
1636                                 path->l[path->level].b =
1637                                         BTREE_ITER_NO_NODE_ERROR;
1638                         else
1639                                 path->l[path->level].b =
1640                                         BTREE_ITER_NO_NODE_DOWN;
1641                         goto out;
1642                 }
1643         }
1644
1645         path->uptodate = BTREE_ITER_UPTODATE;
1646 out:
1647         BUG_ON((ret == -EINTR) != !!trans->restarted);
1648         bch2_btree_path_verify(trans, path);
1649         return ret;
1650 }
1651
1652 int __must_check bch2_btree_path_traverse(struct btree_trans *trans,
1653                                           struct btree_path *path, unsigned flags)
1654 {
1655         if (path->uptodate < BTREE_ITER_NEED_RELOCK)
1656                 return 0;
1657
1658         return  bch2_trans_cond_resched(trans) ?:
1659                 btree_path_traverse_one(trans, path, flags, _RET_IP_);
1660 }
1661
1662 static void btree_path_copy(struct btree_trans *trans, struct btree_path *dst,
1663                             struct btree_path *src)
1664 {
1665         unsigned i, offset = offsetof(struct btree_path, pos);
1666
1667         memcpy((void *) dst + offset,
1668                (void *) src + offset,
1669                sizeof(struct btree_path) - offset);
1670
1671         for (i = 0; i < BTREE_MAX_DEPTH; i++)
1672                 if (btree_node_locked(dst, i))
1673                         six_lock_increment(&dst->l[i].b->c.lock,
1674                                            __btree_lock_want(dst, i));
1675
1676         trans->paths_sorted = false;
1677 }
1678
1679 static struct btree_path *btree_path_clone(struct btree_trans *trans, struct btree_path *src,
1680                                            bool intent)
1681 {
1682         struct btree_path *new = btree_path_alloc(trans, src);
1683
1684         btree_path_copy(trans, new, src);
1685         __btree_path_get(new, intent);
1686         return new;
1687 }
1688
1689 struct btree_path *__bch2_btree_path_make_mut(struct btree_trans *trans,
1690                          struct btree_path *path, bool intent)
1691 {
1692         __btree_path_put(path, intent);
1693         path = btree_path_clone(trans, path, intent);
1694         path->preserve = false;
1695 #ifdef CONFIG_BCACHEFS_DEBUG
1696         path->ip_allocated = _RET_IP_;
1697 #endif
1698         path->should_be_locked = false;
1699         return path;
1700 }
1701
1702 struct btree_path * __must_check
1703 __bch2_btree_path_set_pos(struct btree_trans *trans,
1704                           struct btree_path *path, struct bpos new_pos,
1705                           bool intent, int cmp)
1706 {
1707         unsigned l = path->level;
1708
1709         EBUG_ON(trans->restarted);
1710         EBUG_ON(!path->ref);
1711
1712         path = bch2_btree_path_make_mut(trans, path, intent);
1713
1714         path->pos               = new_pos;
1715         trans->paths_sorted     = false;
1716
1717         if (unlikely(path->cached)) {
1718                 btree_node_unlock(path, 0);
1719                 path->l[0].b = BTREE_ITER_NO_NODE_CACHED;
1720                 btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
1721                 goto out;
1722         }
1723
1724         l = btree_path_up_until_good_node(trans, path, cmp);
1725
1726         if (btree_path_node(path, l)) {
1727                 BUG_ON(!btree_node_locked(path, l));
1728                 /*
1729                  * We might have to skip over many keys, or just a few: try
1730                  * advancing the node iterator, and if we have to skip over too
1731                  * many keys just reinit it (or if we're rewinding, since that
1732                  * is expensive).
1733                  */
1734                 if (cmp < 0 ||
1735                     !btree_path_advance_to_pos(path, &path->l[l], 8))
1736                         __btree_path_level_init(path, l);
1737         }
1738
1739         if (l != path->level) {
1740                 btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
1741                 __bch2_btree_path_unlock(path);
1742         }
1743 out:
1744         bch2_btree_path_verify(trans, path);
1745         return path;
1746 }
1747
1748 /* Btree path: main interface: */
1749
1750 static struct btree_path *have_path_at_pos(struct btree_trans *trans, struct btree_path *path)
1751 {
1752         struct btree_path *next;
1753
1754         next = prev_btree_path(trans, path);
1755         if (next && !btree_path_cmp(next, path))
1756                 return next;
1757
1758         next = next_btree_path(trans, path);
1759         if (next && !btree_path_cmp(next, path))
1760                 return next;
1761
1762         return NULL;
1763 }
1764
1765 static struct btree_path *have_node_at_pos(struct btree_trans *trans, struct btree_path *path)
1766 {
1767         struct btree_path *next;
1768
1769         next = prev_btree_path(trans, path);
1770         if (next && next->level == path->level && path_l(next)->b == path_l(path)->b)
1771                 return next;
1772
1773         next = next_btree_path(trans, path);
1774         if (next && next->level == path->level && path_l(next)->b == path_l(path)->b)
1775                 return next;
1776
1777         return NULL;
1778 }
1779
1780 static inline void __bch2_path_free(struct btree_trans *trans, struct btree_path *path)
1781 {
1782         __bch2_btree_path_unlock(path);
1783         btree_path_list_remove(trans, path);
1784         trans->paths_allocated &= ~(1ULL << path->idx);
1785 }
1786
1787 void bch2_path_put(struct btree_trans *trans, struct btree_path *path, bool intent)
1788 {
1789         struct btree_path *dup;
1790
1791         EBUG_ON(trans->paths + path->idx != path);
1792         EBUG_ON(!path->ref);
1793
1794         if (!__btree_path_put(path, intent))
1795                 return;
1796
1797         /*
1798          * Perhaps instead we should check for duplicate paths in traverse_all:
1799          */
1800         if (path->preserve &&
1801             (dup = have_path_at_pos(trans, path))) {
1802                 dup->preserve = true;
1803                 path->preserve = false;
1804                 goto free;
1805         }
1806
1807         if (!path->preserve &&
1808             (dup = have_node_at_pos(trans, path)))
1809                 goto free;
1810         return;
1811 free:
1812         if (path->should_be_locked &&
1813             !btree_node_locked(dup, path->level))
1814                 return;
1815
1816         dup->should_be_locked |= path->should_be_locked;
1817         __bch2_path_free(trans, path);
1818 }
1819
1820 void bch2_trans_updates_to_text(struct printbuf *buf, struct btree_trans *trans)
1821 {
1822         struct btree_insert_entry *i;
1823
1824         pr_buf(buf, "transaction updates for %s journal seq %llu",
1825                trans->fn, trans->journal_res.seq);
1826         pr_newline(buf);
1827         pr_indent_push(buf, 2);
1828
1829         trans_for_each_update(trans, i) {
1830                 struct bkey_s_c old = { &i->old_k, i->old_v };
1831
1832                 pr_buf(buf, "update: btree=%s cached=%u %pS",
1833                        bch2_btree_ids[i->btree_id],
1834                        i->cached,
1835                        (void *) i->ip_allocated);
1836                 pr_newline(buf);
1837
1838                 pr_buf(buf, "  old ");
1839                 bch2_bkey_val_to_text(buf, trans->c, old);
1840                 pr_newline(buf);
1841
1842                 pr_buf(buf, "  new ");
1843                 bch2_bkey_val_to_text(buf, trans->c, bkey_i_to_s_c(i->k));
1844                 pr_newline(buf);
1845         }
1846
1847         pr_indent_pop(buf, 2);
1848 }
1849
1850 noinline __cold
1851 void bch2_dump_trans_updates(struct btree_trans *trans)
1852 {
1853         struct printbuf buf = PRINTBUF;
1854
1855         bch2_trans_updates_to_text(&buf, trans);
1856         bch_err(trans->c, "%s", buf.buf);
1857         printbuf_exit(&buf);
1858 }
1859
1860 noinline __cold
1861 void bch2_dump_trans_paths_updates(struct btree_trans *trans)
1862 {
1863         struct btree_path *path;
1864         struct printbuf buf = PRINTBUF;
1865         unsigned idx;
1866
1867         btree_trans_sort_paths(trans);
1868
1869         trans_for_each_path_inorder(trans, path, idx) {
1870                 printbuf_reset(&buf);
1871
1872                 bch2_bpos_to_text(&buf, path->pos);
1873
1874                 printk(KERN_ERR "path: idx %u ref %u:%u%s%s btree=%s l=%u pos %s locks %u %pS\n",
1875                        path->idx, path->ref, path->intent_ref,
1876                        path->should_be_locked ? " S" : "",
1877                        path->preserve ? " P" : "",
1878                        bch2_btree_ids[path->btree_id],
1879                        path->level,
1880                        buf.buf,
1881                        path->nodes_locked,
1882 #ifdef CONFIG_BCACHEFS_DEBUG
1883                        (void *) path->ip_allocated
1884 #else
1885                        NULL
1886 #endif
1887                        );
1888         }
1889
1890         printbuf_exit(&buf);
1891
1892         bch2_dump_trans_updates(trans);
1893 }
1894
1895 static struct btree_path *btree_path_alloc(struct btree_trans *trans,
1896                                            struct btree_path *pos)
1897 {
1898         struct btree_path *path;
1899         unsigned idx;
1900
1901         if (unlikely(trans->paths_allocated ==
1902                      ~((~0ULL << 1) << (BTREE_ITER_MAX - 1)))) {
1903                 bch2_dump_trans_paths_updates(trans);
1904                 panic("trans path oveflow\n");
1905         }
1906
1907         idx = __ffs64(~trans->paths_allocated);
1908         trans->paths_allocated |= 1ULL << idx;
1909
1910         path = &trans->paths[idx];
1911
1912         path->idx               = idx;
1913         path->ref               = 0;
1914         path->intent_ref        = 0;
1915         path->nodes_locked      = 0;
1916         path->nodes_intent_locked = 0;
1917
1918         btree_path_list_add(trans, pos, path);
1919         return path;
1920 }
1921
1922 struct btree_path *bch2_path_get(struct btree_trans *trans,
1923                                  enum btree_id btree_id, struct bpos pos,
1924                                  unsigned locks_want, unsigned level,
1925                                  unsigned flags)
1926 {
1927         struct btree_path *path, *path_pos = NULL;
1928         bool cached = flags & BTREE_ITER_CACHED;
1929         bool intent = flags & BTREE_ITER_INTENT;
1930         int i;
1931
1932         BUG_ON(trans->restarted);
1933         bch2_trans_verify_locks(trans);
1934
1935         btree_trans_sort_paths(trans);
1936
1937         btree_trans_sort_paths(trans);
1938
1939         trans_for_each_path_inorder(trans, path, i) {
1940                 if (__btree_path_cmp(path,
1941                                      btree_id,
1942                                      cached,
1943                                      pos,
1944                                      level) > 0)
1945                         break;
1946
1947                 path_pos = path;
1948         }
1949
1950         if (path_pos &&
1951             path_pos->cached    == cached &&
1952             path_pos->btree_id  == btree_id &&
1953             path_pos->level     == level) {
1954                 __btree_path_get(path_pos, intent);
1955                 path = bch2_btree_path_set_pos(trans, path_pos, pos, intent);
1956         } else {
1957                 path = btree_path_alloc(trans, path_pos);
1958                 path_pos = NULL;
1959
1960                 __btree_path_get(path, intent);
1961                 path->pos                       = pos;
1962                 path->btree_id                  = btree_id;
1963                 path->cached                    = cached;
1964                 path->uptodate                  = BTREE_ITER_NEED_TRAVERSE;
1965                 path->should_be_locked          = false;
1966                 path->level                     = level;
1967                 path->locks_want                = locks_want;
1968                 path->nodes_locked              = 0;
1969                 path->nodes_intent_locked       = 0;
1970                 for (i = 0; i < ARRAY_SIZE(path->l); i++)
1971                         path->l[i].b            = BTREE_ITER_NO_NODE_INIT;
1972 #ifdef CONFIG_BCACHEFS_DEBUG
1973                 path->ip_allocated              = _RET_IP_;
1974 #endif
1975                 trans->paths_sorted             = false;
1976         }
1977
1978         if (!(flags & BTREE_ITER_NOPRESERVE))
1979                 path->preserve = true;
1980
1981         if (path->intent_ref)
1982                 locks_want = max(locks_want, level + 1);
1983
1984         /*
1985          * If the path has locks_want greater than requested, we don't downgrade
1986          * it here - on transaction restart because btree node split needs to
1987          * upgrade locks, we might be putting/getting the iterator again.
1988          * Downgrading iterators only happens via bch2_trans_downgrade(), after
1989          * a successful transaction commit.
1990          */
1991
1992         locks_want = min(locks_want, BTREE_MAX_DEPTH);
1993         if (locks_want > path->locks_want) {
1994                 path->locks_want = locks_want;
1995                 btree_path_get_locks(trans, path, true);
1996         }
1997
1998         return path;
1999 }
2000
2001 inline struct bkey_s_c bch2_btree_path_peek_slot(struct btree_path *path, struct bkey *u)
2002 {
2003
2004         struct bkey_s_c k;
2005
2006         if (!path->cached) {
2007                 struct btree_path_level *l = path_l(path);
2008                 struct bkey_packed *_k;
2009
2010                 EBUG_ON(path->uptodate != BTREE_ITER_UPTODATE);
2011
2012                 _k = bch2_btree_node_iter_peek_all(&l->iter, l->b);
2013                 k = _k ? bkey_disassemble(l->b, _k, u) : bkey_s_c_null;
2014
2015                 EBUG_ON(k.k && bkey_deleted(k.k) && bpos_cmp(k.k->p, path->pos) == 0);
2016
2017                 if (!k.k || bpos_cmp(path->pos, k.k->p))
2018                         goto hole;
2019         } else {
2020                 struct bkey_cached *ck = (void *) path->l[0].b;
2021
2022                 EBUG_ON(ck &&
2023                         (path->btree_id != ck->key.btree_id ||
2024                          bkey_cmp(path->pos, ck->key.pos)));
2025
2026                 /* BTREE_ITER_CACHED_NOFILL|BTREE_ITER_CACHED_NOCREATE? */
2027                 if (unlikely(!ck || !ck->valid))
2028                         return bkey_s_c_null;
2029
2030                 EBUG_ON(path->uptodate != BTREE_ITER_UPTODATE);
2031
2032                 *u = ck->k->k;
2033                 k = bkey_i_to_s_c(ck->k);
2034         }
2035
2036         return k;
2037 hole:
2038         bkey_init(u);
2039         u->p = path->pos;
2040         return (struct bkey_s_c) { u, NULL };
2041 }
2042
2043 /* Btree iterators: */
2044
2045 int __must_check
2046 __bch2_btree_iter_traverse(struct btree_iter *iter)
2047 {
2048         return bch2_btree_path_traverse(iter->trans, iter->path, iter->flags);
2049 }
2050
2051 int __must_check
2052 bch2_btree_iter_traverse(struct btree_iter *iter)
2053 {
2054         int ret;
2055
2056         iter->path = bch2_btree_path_set_pos(iter->trans, iter->path,
2057                                         btree_iter_search_key(iter),
2058                                         iter->flags & BTREE_ITER_INTENT);
2059
2060         ret = bch2_btree_path_traverse(iter->trans, iter->path, iter->flags);
2061         if (ret)
2062                 return ret;
2063
2064         iter->path->should_be_locked = true;
2065         return 0;
2066 }
2067
2068 /* Iterate across nodes (leaf and interior nodes) */
2069
2070 struct btree *bch2_btree_iter_peek_node(struct btree_iter *iter)
2071 {
2072         struct btree_trans *trans = iter->trans;
2073         struct btree *b = NULL;
2074         int ret;
2075
2076         EBUG_ON(iter->path->cached);
2077         bch2_btree_iter_verify(iter);
2078
2079         ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
2080         if (ret)
2081                 goto err;
2082
2083         b = btree_path_node(iter->path, iter->path->level);
2084         if (!b)
2085                 goto out;
2086
2087         BUG_ON(bpos_cmp(b->key.k.p, iter->pos) < 0);
2088
2089         bkey_init(&iter->k);
2090         iter->k.p = iter->pos = b->key.k.p;
2091
2092         iter->path = bch2_btree_path_set_pos(trans, iter->path, b->key.k.p,
2093                                         iter->flags & BTREE_ITER_INTENT);
2094         iter->path->should_be_locked = true;
2095         BUG_ON(iter->path->uptodate);
2096 out:
2097         bch2_btree_iter_verify_entry_exit(iter);
2098         bch2_btree_iter_verify(iter);
2099
2100         return b;
2101 err:
2102         b = ERR_PTR(ret);
2103         goto out;
2104 }
2105
2106 struct btree *bch2_btree_iter_next_node(struct btree_iter *iter)
2107 {
2108         struct btree_trans *trans = iter->trans;
2109         struct btree_path *path = iter->path;
2110         struct btree *b = NULL;
2111         int ret;
2112
2113         BUG_ON(trans->restarted);
2114         EBUG_ON(iter->path->cached);
2115         bch2_btree_iter_verify(iter);
2116
2117         /* already at end? */
2118         if (!btree_path_node(path, path->level))
2119                 return NULL;
2120
2121         /* got to end? */
2122         if (!btree_path_node(path, path->level + 1)) {
2123                 btree_path_set_level_up(path);
2124                 return NULL;
2125         }
2126
2127         if (!bch2_btree_node_relock(trans, path, path->level + 1)) {
2128                 __bch2_btree_path_unlock(path);
2129                 path->l[path->level].b = BTREE_ITER_NO_NODE_GET_LOCKS;
2130                 path->l[path->level + 1].b = BTREE_ITER_NO_NODE_GET_LOCKS;
2131                 btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
2132                 trace_trans_restart_relock_next_node(trans->fn, _THIS_IP_,
2133                                            path->btree_id, &path->pos);
2134                 btree_trans_restart(trans);
2135                 ret = -EINTR;
2136                 goto err;
2137         }
2138
2139         b = btree_path_node(path, path->level + 1);
2140
2141         if (!bpos_cmp(iter->pos, b->key.k.p)) {
2142                 btree_node_unlock(path, path->level);
2143                 path->l[path->level].b = BTREE_ITER_NO_NODE_UP;
2144                 path->level++;
2145         } else {
2146                 /*
2147                  * Haven't gotten to the end of the parent node: go back down to
2148                  * the next child node
2149                  */
2150                 path = iter->path =
2151                         bch2_btree_path_set_pos(trans, path, bpos_successor(iter->pos),
2152                                            iter->flags & BTREE_ITER_INTENT);
2153
2154                 btree_path_set_level_down(trans, path, iter->min_depth);
2155
2156                 ret = bch2_btree_path_traverse(trans, path, iter->flags);
2157                 if (ret)
2158                         goto err;
2159
2160                 b = path->l[path->level].b;
2161         }
2162
2163         bkey_init(&iter->k);
2164         iter->k.p = iter->pos = b->key.k.p;
2165
2166         iter->path = bch2_btree_path_set_pos(trans, iter->path, b->key.k.p,
2167                                         iter->flags & BTREE_ITER_INTENT);
2168         iter->path->should_be_locked = true;
2169         BUG_ON(iter->path->uptodate);
2170 out:
2171         bch2_btree_iter_verify_entry_exit(iter);
2172         bch2_btree_iter_verify(iter);
2173
2174         return b;
2175 err:
2176         b = ERR_PTR(ret);
2177         goto out;
2178 }
2179
2180 /* Iterate across keys (in leaf nodes only) */
2181
2182 inline bool bch2_btree_iter_advance(struct btree_iter *iter)
2183 {
2184         if (likely(!(iter->flags & BTREE_ITER_ALL_LEVELS))) {
2185                 struct bpos pos = iter->k.p;
2186                 bool ret = (iter->flags & BTREE_ITER_ALL_SNAPSHOTS
2187                             ? bpos_cmp(pos, SPOS_MAX)
2188                             : bkey_cmp(pos, SPOS_MAX)) != 0;
2189
2190                 if (ret && !(iter->flags & BTREE_ITER_IS_EXTENTS))
2191                         pos = bkey_successor(iter, pos);
2192                 bch2_btree_iter_set_pos(iter, pos);
2193                 return ret;
2194         } else {
2195                 if (!btree_path_node(iter->path, iter->path->level))
2196                         return true;
2197
2198                 iter->advanced = true;
2199                 return false;
2200         }
2201 }
2202
2203 inline bool bch2_btree_iter_rewind(struct btree_iter *iter)
2204 {
2205         struct bpos pos = bkey_start_pos(&iter->k);
2206         bool ret = (iter->flags & BTREE_ITER_ALL_SNAPSHOTS
2207                     ? bpos_cmp(pos, POS_MIN)
2208                     : bkey_cmp(pos, POS_MIN)) != 0;
2209
2210         if (ret && !(iter->flags & BTREE_ITER_IS_EXTENTS))
2211                 pos = bkey_predecessor(iter, pos);
2212         bch2_btree_iter_set_pos(iter, pos);
2213         return ret;
2214 }
2215
2216 static noinline
2217 struct bkey_i *__bch2_btree_trans_peek_updates(struct btree_iter *iter)
2218 {
2219         struct btree_insert_entry *i;
2220         struct bkey_i *ret = NULL;
2221
2222         trans_for_each_update(iter->trans, i) {
2223                 if (i->btree_id < iter->btree_id)
2224                         continue;
2225                 if (i->btree_id > iter->btree_id)
2226                         break;
2227                 if (bpos_cmp(i->k->k.p, iter->path->pos) < 0)
2228                         continue;
2229                 if (i->key_cache_already_flushed)
2230                         continue;
2231                 if (!ret || bpos_cmp(i->k->k.p, ret->k.p) < 0)
2232                         ret = i->k;
2233         }
2234
2235         return ret;
2236 }
2237
2238 static inline struct bkey_i *btree_trans_peek_updates(struct btree_iter *iter)
2239 {
2240         return iter->flags & BTREE_ITER_WITH_UPDATES
2241                 ? __bch2_btree_trans_peek_updates(iter)
2242                 : NULL;
2243 }
2244
2245 static noinline
2246 struct bkey_s_c btree_trans_peek_slot_journal(struct btree_trans *trans,
2247                                               struct btree_iter *iter)
2248 {
2249         struct bkey_i *k = bch2_journal_keys_peek_slot(trans->c, iter->btree_id,
2250                                                        iter->path->level,
2251                                                        iter->path->pos);
2252
2253         if (k) {
2254                 iter->k = k->k;
2255                 return bkey_i_to_s_c(k);
2256         } else {
2257                 return bkey_s_c_null;
2258         }
2259 }
2260
2261 static noinline
2262 struct bkey_s_c btree_trans_peek_journal(struct btree_trans *trans,
2263                                          struct btree_iter *iter,
2264                                          struct bkey_s_c k)
2265 {
2266         struct bkey_i *next_journal =
2267                 bch2_journal_keys_peek_upto(trans->c, iter->btree_id, 0,
2268                                 iter->path->pos,
2269                                 k.k ? k.k->p : iter->path->l[0].b->key.k.p);
2270
2271         if (next_journal) {
2272                 iter->k = next_journal->k;
2273                 k = bkey_i_to_s_c(next_journal);
2274         }
2275
2276         return k;
2277 }
2278
2279 /*
2280  * Checks btree key cache for key at iter->pos and returns it if present, or
2281  * bkey_s_c_null:
2282  */
2283 static noinline
2284 struct bkey_s_c btree_trans_peek_key_cache(struct btree_iter *iter, struct bpos pos)
2285 {
2286         struct btree_trans *trans = iter->trans;
2287         struct bch_fs *c = trans->c;
2288         struct bkey u;
2289         int ret;
2290
2291         if (!bch2_btree_key_cache_find(c, iter->btree_id, pos))
2292                 return bkey_s_c_null;
2293
2294         if (!iter->key_cache_path)
2295                 iter->key_cache_path = bch2_path_get(trans, iter->btree_id, pos,
2296                                                      iter->flags & BTREE_ITER_INTENT, 0,
2297                                                      iter->flags|BTREE_ITER_CACHED);
2298
2299         iter->key_cache_path = bch2_btree_path_set_pos(trans, iter->key_cache_path, pos,
2300                                         iter->flags & BTREE_ITER_INTENT);
2301
2302         ret = bch2_btree_path_traverse(trans, iter->key_cache_path, iter->flags|BTREE_ITER_CACHED);
2303         if (unlikely(ret))
2304                 return bkey_s_c_err(ret);
2305
2306         iter->key_cache_path->should_be_locked = true;
2307
2308         return bch2_btree_path_peek_slot(iter->key_cache_path, &u);
2309 }
2310
2311 static struct bkey_s_c __bch2_btree_iter_peek(struct btree_iter *iter, struct bpos search_key)
2312 {
2313         struct btree_trans *trans = iter->trans;
2314         struct bkey_i *next_update;
2315         struct bkey_s_c k, k2;
2316         int ret;
2317
2318         EBUG_ON(iter->path->cached || iter->path->level);
2319         bch2_btree_iter_verify(iter);
2320
2321         while (1) {
2322                 iter->path = bch2_btree_path_set_pos(trans, iter->path, search_key,
2323                                         iter->flags & BTREE_ITER_INTENT);
2324
2325                 ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
2326                 if (unlikely(ret)) {
2327                         /* ensure that iter->k is consistent with iter->pos: */
2328                         bch2_btree_iter_set_pos(iter, iter->pos);
2329                         k = bkey_s_c_err(ret);
2330                         goto out;
2331                 }
2332
2333                 iter->path->should_be_locked = true;
2334
2335                 k = btree_path_level_peek_all(trans->c, &iter->path->l[0], &iter->k);
2336
2337                 if (unlikely(iter->flags & BTREE_ITER_WITH_KEY_CACHE) &&
2338                     k.k &&
2339                     (k2 = btree_trans_peek_key_cache(iter, k.k->p)).k) {
2340                         ret = bkey_err(k2);
2341                         if (ret) {
2342                                 k = k2;
2343                                 bch2_btree_iter_set_pos(iter, iter->pos);
2344                                 goto out;
2345                         }
2346
2347                         k = k2;
2348                         iter->k = *k.k;
2349                 }
2350
2351                 if (unlikely(iter->flags & BTREE_ITER_WITH_JOURNAL))
2352                         k = btree_trans_peek_journal(trans, iter, k);
2353
2354                 next_update = btree_trans_peek_updates(iter);
2355
2356                 if (next_update &&
2357                     bpos_cmp(next_update->k.p,
2358                              k.k ? k.k->p : iter->path->l[0].b->key.k.p) <= 0) {
2359                         iter->k = next_update->k;
2360                         k = bkey_i_to_s_c(next_update);
2361                 }
2362
2363                 if (k.k && bkey_deleted(k.k)) {
2364                         /*
2365                          * If we've got a whiteout, and it's after the search
2366                          * key, advance the search key to the whiteout instead
2367                          * of just after the whiteout - it might be a btree
2368                          * whiteout, with a real key at the same position, since
2369                          * in the btree deleted keys sort before non deleted.
2370                          */
2371                         search_key = bpos_cmp(search_key, k.k->p)
2372                                 ? k.k->p
2373                                 : bpos_successor(k.k->p);
2374                         continue;
2375                 }
2376
2377                 if (likely(k.k)) {
2378                         break;
2379                 } else if (likely(bpos_cmp(iter->path->l[0].b->key.k.p, SPOS_MAX))) {
2380                         /* Advance to next leaf node: */
2381                         search_key = bpos_successor(iter->path->l[0].b->key.k.p);
2382                 } else {
2383                         /* End of btree: */
2384                         bch2_btree_iter_set_pos(iter, SPOS_MAX);
2385                         k = bkey_s_c_null;
2386                         goto out;
2387                 }
2388         }
2389 out:
2390         bch2_btree_iter_verify(iter);
2391
2392         return k;
2393 }
2394
2395 /**
2396  * bch2_btree_iter_peek: returns first key greater than or equal to iterator's
2397  * current position
2398  */
2399 struct bkey_s_c bch2_btree_iter_peek_upto(struct btree_iter *iter, struct bpos end)
2400 {
2401         struct btree_trans *trans = iter->trans;
2402         struct bpos search_key = btree_iter_search_key(iter);
2403         struct bkey_s_c k;
2404         struct bpos iter_pos;
2405         int ret;
2406
2407         EBUG_ON(iter->flags & BTREE_ITER_ALL_LEVELS);
2408
2409         if (iter->update_path) {
2410                 bch2_path_put(trans, iter->update_path,
2411                               iter->flags & BTREE_ITER_INTENT);
2412                 iter->update_path = NULL;
2413         }
2414
2415         bch2_btree_iter_verify_entry_exit(iter);
2416
2417         while (1) {
2418                 k = __bch2_btree_iter_peek(iter, search_key);
2419                 if (!k.k || bkey_err(k))
2420                         goto out;
2421
2422                 /*
2423                  * iter->pos should be mononotically increasing, and always be
2424                  * equal to the key we just returned - except extents can
2425                  * straddle iter->pos:
2426                  */
2427                 if (!(iter->flags & BTREE_ITER_IS_EXTENTS))
2428                         iter_pos = k.k->p;
2429                 else if (bkey_cmp(bkey_start_pos(k.k), iter->pos) > 0)
2430                         iter_pos = bkey_start_pos(k.k);
2431                 else
2432                         iter_pos = iter->pos;
2433
2434                 if (bkey_cmp(iter_pos, end) > 0) {
2435                         bch2_btree_iter_set_pos(iter, end);
2436                         k = bkey_s_c_null;
2437                         goto out;
2438                 }
2439
2440                 if (iter->update_path &&
2441                     bkey_cmp(iter->update_path->pos, k.k->p)) {
2442                         bch2_path_put(trans, iter->update_path,
2443                                       iter->flags & BTREE_ITER_INTENT);
2444                         iter->update_path = NULL;
2445                 }
2446
2447                 if ((iter->flags & BTREE_ITER_FILTER_SNAPSHOTS) &&
2448                     (iter->flags & BTREE_ITER_INTENT) &&
2449                     !(iter->flags & BTREE_ITER_IS_EXTENTS) &&
2450                     !iter->update_path) {
2451                         struct bpos pos = k.k->p;
2452
2453                         if (pos.snapshot < iter->snapshot) {
2454                                 search_key = bpos_successor(k.k->p);
2455                                 continue;
2456                         }
2457
2458                         pos.snapshot = iter->snapshot;
2459
2460                         /*
2461                          * advance, same as on exit for iter->path, but only up
2462                          * to snapshot
2463                          */
2464                         __btree_path_get(iter->path, iter->flags & BTREE_ITER_INTENT);
2465                         iter->update_path = iter->path;
2466
2467                         iter->update_path = bch2_btree_path_set_pos(trans,
2468                                                 iter->update_path, pos,
2469                                                 iter->flags & BTREE_ITER_INTENT);
2470                 }
2471
2472                 /*
2473                  * We can never have a key in a leaf node at POS_MAX, so
2474                  * we don't have to check these successor() calls:
2475                  */
2476                 if ((iter->flags & BTREE_ITER_FILTER_SNAPSHOTS) &&
2477                     !bch2_snapshot_is_ancestor(trans->c,
2478                                                iter->snapshot,
2479                                                k.k->p.snapshot)) {
2480                         search_key = bpos_successor(k.k->p);
2481                         continue;
2482                 }
2483
2484                 if (bkey_whiteout(k.k) &&
2485                     !(iter->flags & BTREE_ITER_ALL_SNAPSHOTS)) {
2486                         search_key = bkey_successor(iter, k.k->p);
2487                         continue;
2488                 }
2489
2490                 break;
2491         }
2492
2493         iter->pos = iter_pos;
2494
2495         iter->path = bch2_btree_path_set_pos(trans, iter->path, k.k->p,
2496                                 iter->flags & BTREE_ITER_INTENT);
2497         BUG_ON(!iter->path->nodes_locked);
2498 out:
2499         if (iter->update_path) {
2500                 if (unlikely(!bch2_btree_path_relock(trans, iter->update_path, _THIS_IP_))) {
2501                         k = bkey_s_c_err(-EINTR);
2502                 } else {
2503                         BUG_ON(!(iter->update_path->nodes_locked & 1));
2504                         iter->update_path->should_be_locked = true;
2505                 }
2506         }
2507         iter->path->should_be_locked = true;
2508
2509         if (!(iter->flags & BTREE_ITER_ALL_SNAPSHOTS))
2510                 iter->pos.snapshot = iter->snapshot;
2511
2512         ret = bch2_btree_iter_verify_ret(iter, k);
2513         if (unlikely(ret)) {
2514                 bch2_btree_iter_set_pos(iter, iter->pos);
2515                 k = bkey_s_c_err(ret);
2516         }
2517
2518         bch2_btree_iter_verify_entry_exit(iter);
2519
2520         return k;
2521 }
2522
2523 /**
2524  * bch2_btree_iter_peek_all_levels: returns the first key greater than or equal
2525  * to iterator's current position, returning keys from every level of the btree.
2526  * For keys at different levels of the btree that compare equal, the key from
2527  * the lower level (leaf) is returned first.
2528  */
2529 struct bkey_s_c bch2_btree_iter_peek_all_levels(struct btree_iter *iter)
2530 {
2531         struct btree_trans *trans = iter->trans;
2532         struct bkey_s_c k;
2533         int ret;
2534
2535         EBUG_ON(iter->path->cached);
2536         bch2_btree_iter_verify(iter);
2537         BUG_ON(iter->path->level < iter->min_depth);
2538         BUG_ON(!(iter->flags & BTREE_ITER_ALL_SNAPSHOTS));
2539         EBUG_ON(!(iter->flags & BTREE_ITER_ALL_LEVELS));
2540
2541         while (1) {
2542                 iter->path = bch2_btree_path_set_pos(trans, iter->path, iter->pos,
2543                                         iter->flags & BTREE_ITER_INTENT);
2544
2545                 ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
2546                 if (unlikely(ret)) {
2547                         /* ensure that iter->k is consistent with iter->pos: */
2548                         bch2_btree_iter_set_pos(iter, iter->pos);
2549                         k = bkey_s_c_err(ret);
2550                         goto out;
2551                 }
2552
2553                 /* Already at end? */
2554                 if (!btree_path_node(iter->path, iter->path->level)) {
2555                         k = bkey_s_c_null;
2556                         goto out;
2557                 }
2558
2559                 k = btree_path_level_peek_all(trans->c,
2560                                 &iter->path->l[iter->path->level], &iter->k);
2561
2562                 /* Check if we should go up to the parent node: */
2563                 if (!k.k ||
2564                     (iter->advanced &&
2565                      !bpos_cmp(path_l(iter->path)->b->key.k.p, iter->pos))) {
2566                         iter->pos = path_l(iter->path)->b->key.k.p;
2567                         btree_path_set_level_up(iter->path);
2568                         iter->advanced = false;
2569                         continue;
2570                 }
2571
2572                 /*
2573                  * Check if we should go back down to a leaf:
2574                  * If we're not in a leaf node, we only return the current key
2575                  * if it exactly matches iter->pos - otherwise we first have to
2576                  * go back to the leaf:
2577                  */
2578                 if (iter->path->level != iter->min_depth &&
2579                     (iter->advanced ||
2580                      !k.k ||
2581                      bpos_cmp(iter->pos, k.k->p))) {
2582                         btree_path_set_level_down(trans, iter->path, iter->min_depth);
2583                         iter->pos = bpos_successor(iter->pos);
2584                         iter->advanced = false;
2585                         continue;
2586                 }
2587
2588                 /* Check if we should go to the next key: */
2589                 if (iter->path->level == iter->min_depth &&
2590                     iter->advanced &&
2591                     k.k &&
2592                     !bpos_cmp(iter->pos, k.k->p)) {
2593                         iter->pos = bpos_successor(iter->pos);
2594                         iter->advanced = false;
2595                         continue;
2596                 }
2597
2598                 if (iter->advanced &&
2599                     iter->path->level == iter->min_depth &&
2600                     bpos_cmp(k.k->p, iter->pos))
2601                         iter->advanced = false;
2602
2603                 BUG_ON(iter->advanced);
2604                 BUG_ON(!k.k);
2605                 break;
2606         }
2607
2608         iter->pos = k.k->p;
2609 out:
2610         iter->path->should_be_locked = true;
2611         bch2_btree_iter_verify(iter);
2612
2613         return k;
2614 }
2615
2616 /**
2617  * bch2_btree_iter_next: returns first key greater than iterator's current
2618  * position
2619  */
2620 struct bkey_s_c bch2_btree_iter_next(struct btree_iter *iter)
2621 {
2622         if (!bch2_btree_iter_advance(iter))
2623                 return bkey_s_c_null;
2624
2625         return bch2_btree_iter_peek(iter);
2626 }
2627
2628 /**
2629  * bch2_btree_iter_peek_prev: returns first key less than or equal to
2630  * iterator's current position
2631  */
2632 struct bkey_s_c bch2_btree_iter_peek_prev(struct btree_iter *iter)
2633 {
2634         struct btree_trans *trans = iter->trans;
2635         struct bpos search_key = iter->pos;
2636         struct btree_path *saved_path = NULL;
2637         struct bkey_s_c k;
2638         struct bkey saved_k;
2639         const struct bch_val *saved_v;
2640         int ret;
2641
2642         EBUG_ON(iter->path->cached || iter->path->level);
2643         EBUG_ON(iter->flags & BTREE_ITER_WITH_UPDATES);
2644
2645         if (iter->flags & BTREE_ITER_WITH_JOURNAL)
2646                 return bkey_s_c_err(-EIO);
2647
2648         bch2_btree_iter_verify(iter);
2649         bch2_btree_iter_verify_entry_exit(iter);
2650
2651         if (iter->flags & BTREE_ITER_FILTER_SNAPSHOTS)
2652                 search_key.snapshot = U32_MAX;
2653
2654         while (1) {
2655                 iter->path = bch2_btree_path_set_pos(trans, iter->path, search_key,
2656                                                 iter->flags & BTREE_ITER_INTENT);
2657
2658                 ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
2659                 if (unlikely(ret)) {
2660                         /* ensure that iter->k is consistent with iter->pos: */
2661                         bch2_btree_iter_set_pos(iter, iter->pos);
2662                         k = bkey_s_c_err(ret);
2663                         goto out;
2664                 }
2665
2666                 k = btree_path_level_peek(trans, iter->path,
2667                                           &iter->path->l[0], &iter->k);
2668                 if (!k.k ||
2669                     ((iter->flags & BTREE_ITER_IS_EXTENTS)
2670                      ? bpos_cmp(bkey_start_pos(k.k), search_key) >= 0
2671                      : bpos_cmp(k.k->p, search_key) > 0))
2672                         k = btree_path_level_prev(trans, iter->path,
2673                                                   &iter->path->l[0], &iter->k);
2674
2675                 if (likely(k.k)) {
2676                         if (iter->flags & BTREE_ITER_FILTER_SNAPSHOTS) {
2677                                 if (k.k->p.snapshot == iter->snapshot)
2678                                         goto got_key;
2679
2680                                 /*
2681                                  * If we have a saved candidate, and we're no
2682                                  * longer at the same _key_ (not pos), return
2683                                  * that candidate
2684                                  */
2685                                 if (saved_path && bkey_cmp(k.k->p, saved_k.p)) {
2686                                         bch2_path_put(trans, iter->path,
2687                                                       iter->flags & BTREE_ITER_INTENT);
2688                                         iter->path = saved_path;
2689                                         saved_path = NULL;
2690                                         iter->k = saved_k;
2691                                         k.v     = saved_v;
2692                                         goto got_key;
2693                                 }
2694
2695                                 if (bch2_snapshot_is_ancestor(iter->trans->c,
2696                                                               iter->snapshot,
2697                                                               k.k->p.snapshot)) {
2698                                         if (saved_path)
2699                                                 bch2_path_put(trans, saved_path,
2700                                                       iter->flags & BTREE_ITER_INTENT);
2701                                         saved_path = btree_path_clone(trans, iter->path,
2702                                                                 iter->flags & BTREE_ITER_INTENT);
2703                                         saved_k = *k.k;
2704                                         saved_v = k.v;
2705                                 }
2706
2707                                 search_key = bpos_predecessor(k.k->p);
2708                                 continue;
2709                         }
2710 got_key:
2711                         if (bkey_whiteout(k.k) &&
2712                             !(iter->flags & BTREE_ITER_ALL_SNAPSHOTS)) {
2713                                 search_key = bkey_predecessor(iter, k.k->p);
2714                                 if (iter->flags & BTREE_ITER_FILTER_SNAPSHOTS)
2715                                         search_key.snapshot = U32_MAX;
2716                                 continue;
2717                         }
2718
2719                         break;
2720                 } else if (likely(bpos_cmp(iter->path->l[0].b->data->min_key, POS_MIN))) {
2721                         /* Advance to previous leaf node: */
2722                         search_key = bpos_predecessor(iter->path->l[0].b->data->min_key);
2723                 } else {
2724                         /* Start of btree: */
2725                         bch2_btree_iter_set_pos(iter, POS_MIN);
2726                         k = bkey_s_c_null;
2727                         goto out;
2728                 }
2729         }
2730
2731         EBUG_ON(bkey_cmp(bkey_start_pos(k.k), iter->pos) > 0);
2732
2733         /* Extents can straddle iter->pos: */
2734         if (bkey_cmp(k.k->p, iter->pos) < 0)
2735                 iter->pos = k.k->p;
2736
2737         if (iter->flags & BTREE_ITER_FILTER_SNAPSHOTS)
2738                 iter->pos.snapshot = iter->snapshot;
2739 out:
2740         if (saved_path)
2741                 bch2_path_put(trans, saved_path, iter->flags & BTREE_ITER_INTENT);
2742         iter->path->should_be_locked = true;
2743
2744         bch2_btree_iter_verify_entry_exit(iter);
2745         bch2_btree_iter_verify(iter);
2746
2747         return k;
2748 }
2749
2750 /**
2751  * bch2_btree_iter_prev: returns first key less than iterator's current
2752  * position
2753  */
2754 struct bkey_s_c bch2_btree_iter_prev(struct btree_iter *iter)
2755 {
2756         if (!bch2_btree_iter_rewind(iter))
2757                 return bkey_s_c_null;
2758
2759         return bch2_btree_iter_peek_prev(iter);
2760 }
2761
2762 struct bkey_s_c bch2_btree_iter_peek_slot(struct btree_iter *iter)
2763 {
2764         struct btree_trans *trans = iter->trans;
2765         struct bpos search_key;
2766         struct bkey_s_c k;
2767         int ret;
2768
2769         bch2_btree_iter_verify(iter);
2770         bch2_btree_iter_verify_entry_exit(iter);
2771         EBUG_ON(iter->flags & BTREE_ITER_ALL_LEVELS);
2772         EBUG_ON(iter->path->level && (iter->flags & BTREE_ITER_WITH_KEY_CACHE));
2773
2774         /* extents can't span inode numbers: */
2775         if ((iter->flags & BTREE_ITER_IS_EXTENTS) &&
2776             unlikely(iter->pos.offset == KEY_OFFSET_MAX)) {
2777                 if (iter->pos.inode == KEY_INODE_MAX)
2778                         return bkey_s_c_null;
2779
2780                 bch2_btree_iter_set_pos(iter, bpos_nosnap_successor(iter->pos));
2781         }
2782
2783         search_key = btree_iter_search_key(iter);
2784         iter->path = bch2_btree_path_set_pos(trans, iter->path, search_key,
2785                                         iter->flags & BTREE_ITER_INTENT);
2786
2787         ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
2788         if (unlikely(ret))
2789                 return bkey_s_c_err(ret);
2790
2791         if ((iter->flags & BTREE_ITER_CACHED) ||
2792             !(iter->flags & (BTREE_ITER_IS_EXTENTS|BTREE_ITER_FILTER_SNAPSHOTS))) {
2793                 struct bkey_i *next_update;
2794
2795                 if ((next_update = btree_trans_peek_updates(iter)) &&
2796                     !bpos_cmp(next_update->k.p, iter->pos)) {
2797                         iter->k = next_update->k;
2798                         k = bkey_i_to_s_c(next_update);
2799                         goto out;
2800                 }
2801
2802                 if (unlikely(iter->flags & BTREE_ITER_WITH_JOURNAL) &&
2803                     (k = btree_trans_peek_slot_journal(trans, iter)).k)
2804                         goto out;
2805
2806                 if (unlikely(iter->flags & BTREE_ITER_WITH_KEY_CACHE) &&
2807                     (k = btree_trans_peek_key_cache(iter, iter->pos)).k) {
2808                         if (!bkey_err(k))
2809                                 iter->k = *k.k;
2810                         goto out;
2811                 }
2812
2813                 k = bch2_btree_path_peek_slot(iter->path, &iter->k);
2814         } else {
2815                 struct bpos next;
2816
2817                 EBUG_ON(iter->path->level);
2818
2819                 if (iter->flags & BTREE_ITER_INTENT) {
2820                         struct btree_iter iter2;
2821                         struct bpos end = iter->pos;
2822
2823                         if (iter->flags & BTREE_ITER_IS_EXTENTS)
2824                                 end.offset = U64_MAX;
2825
2826                         bch2_trans_copy_iter(&iter2, iter);
2827                         k = bch2_btree_iter_peek_upto(&iter2, end);
2828
2829                         if (k.k && !bkey_err(k)) {
2830                                 iter->k = iter2.k;
2831                                 k.k = &iter->k;
2832                         }
2833                         bch2_trans_iter_exit(trans, &iter2);
2834                 } else {
2835                         struct bpos pos = iter->pos;
2836
2837                         k = bch2_btree_iter_peek(iter);
2838                         iter->pos = pos;
2839                 }
2840
2841                 if (unlikely(bkey_err(k)))
2842                         return k;
2843
2844                 next = k.k ? bkey_start_pos(k.k) : POS_MAX;
2845
2846                 if (bkey_cmp(iter->pos, next) < 0) {
2847                         bkey_init(&iter->k);
2848                         iter->k.p = iter->pos;
2849
2850                         if (iter->flags & BTREE_ITER_IS_EXTENTS) {
2851                                 bch2_key_resize(&iter->k,
2852                                                 min_t(u64, KEY_SIZE_MAX,
2853                                                       (next.inode == iter->pos.inode
2854                                                        ? next.offset
2855                                                        : KEY_OFFSET_MAX) -
2856                                                       iter->pos.offset));
2857                                 EBUG_ON(!iter->k.size);
2858                         }
2859
2860                         k = (struct bkey_s_c) { &iter->k, NULL };
2861                 }
2862         }
2863 out:
2864         iter->path->should_be_locked = true;
2865
2866         bch2_btree_iter_verify_entry_exit(iter);
2867         bch2_btree_iter_verify(iter);
2868         ret = bch2_btree_iter_verify_ret(iter, k);
2869         if (unlikely(ret))
2870                 return bkey_s_c_err(ret);
2871
2872         return k;
2873 }
2874
2875 struct bkey_s_c bch2_btree_iter_next_slot(struct btree_iter *iter)
2876 {
2877         if (!bch2_btree_iter_advance(iter))
2878                 return bkey_s_c_null;
2879
2880         return bch2_btree_iter_peek_slot(iter);
2881 }
2882
2883 struct bkey_s_c bch2_btree_iter_prev_slot(struct btree_iter *iter)
2884 {
2885         if (!bch2_btree_iter_rewind(iter))
2886                 return bkey_s_c_null;
2887
2888         return bch2_btree_iter_peek_slot(iter);
2889 }
2890
2891 /* new transactional stuff: */
2892
2893 #ifdef CONFIG_BCACHEFS_DEBUG
2894 static void btree_trans_verify_sorted_refs(struct btree_trans *trans)
2895 {
2896         struct btree_path *path;
2897         unsigned i;
2898
2899         BUG_ON(trans->nr_sorted != hweight64(trans->paths_allocated));
2900
2901         trans_for_each_path(trans, path) {
2902                 BUG_ON(path->sorted_idx >= trans->nr_sorted);
2903                 BUG_ON(trans->sorted[path->sorted_idx] != path->idx);
2904         }
2905
2906         for (i = 0; i < trans->nr_sorted; i++) {
2907                 unsigned idx = trans->sorted[i];
2908
2909                 EBUG_ON(!(trans->paths_allocated & (1ULL << idx)));
2910                 BUG_ON(trans->paths[idx].sorted_idx != i);
2911         }
2912 }
2913
2914 static void btree_trans_verify_sorted(struct btree_trans *trans)
2915 {
2916         struct btree_path *path, *prev = NULL;
2917         unsigned i;
2918
2919         trans_for_each_path_inorder(trans, path, i) {
2920                 if (prev && btree_path_cmp(prev, path) > 0) {
2921                         bch2_dump_trans_paths_updates(trans);
2922                         panic("trans paths out of order!\n");
2923                 }
2924                 prev = path;
2925         }
2926 }
2927 #else
2928 static inline void btree_trans_verify_sorted_refs(struct btree_trans *trans) {}
2929 static inline void btree_trans_verify_sorted(struct btree_trans *trans) {}
2930 #endif
2931
2932 void __bch2_btree_trans_sort_paths(struct btree_trans *trans)
2933 {
2934         int i, l = 0, r = trans->nr_sorted, inc = 1;
2935         bool swapped;
2936
2937         btree_trans_verify_sorted_refs(trans);
2938
2939         if (trans->paths_sorted)
2940                 goto out;
2941
2942         /*
2943          * Cocktail shaker sort: this is efficient because iterators will be
2944          * mostly sorteda.
2945          */
2946         do {
2947                 swapped = false;
2948
2949                 for (i = inc > 0 ? l : r - 2;
2950                      i + 1 < r && i >= l;
2951                      i += inc) {
2952                         if (btree_path_cmp(trans->paths + trans->sorted[i],
2953                                            trans->paths + trans->sorted[i + 1]) > 0) {
2954                                 swap(trans->sorted[i], trans->sorted[i + 1]);
2955                                 trans->paths[trans->sorted[i]].sorted_idx = i;
2956                                 trans->paths[trans->sorted[i + 1]].sorted_idx = i + 1;
2957                                 swapped = true;
2958                         }
2959                 }
2960
2961                 if (inc > 0)
2962                         --r;
2963                 else
2964                         l++;
2965                 inc = -inc;
2966         } while (swapped);
2967
2968         trans->paths_sorted = true;
2969 out:
2970         btree_trans_verify_sorted(trans);
2971 }
2972
2973 static inline void btree_path_list_remove(struct btree_trans *trans,
2974                                           struct btree_path *path)
2975 {
2976         unsigned i;
2977
2978         EBUG_ON(path->sorted_idx >= trans->nr_sorted);
2979 #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
2980         trans->nr_sorted--;
2981         memmove_u64s_down_small(trans->sorted + path->sorted_idx,
2982                                 trans->sorted + path->sorted_idx + 1,
2983                                 DIV_ROUND_UP(trans->nr_sorted - path->sorted_idx, 8));
2984 #else
2985         array_remove_item(trans->sorted, trans->nr_sorted, path->sorted_idx);
2986 #endif
2987         for (i = path->sorted_idx; i < trans->nr_sorted; i++)
2988                 trans->paths[trans->sorted[i]].sorted_idx = i;
2989
2990         path->sorted_idx = U8_MAX;
2991 }
2992
2993 static inline void btree_path_list_add(struct btree_trans *trans,
2994                                        struct btree_path *pos,
2995                                        struct btree_path *path)
2996 {
2997         unsigned i;
2998
2999         path->sorted_idx = pos ? pos->sorted_idx + 1 : trans->nr_sorted;
3000
3001 #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
3002         memmove_u64s_up_small(trans->sorted + path->sorted_idx + 1,
3003                               trans->sorted + path->sorted_idx,
3004                               DIV_ROUND_UP(trans->nr_sorted - path->sorted_idx, 8));
3005         trans->nr_sorted++;
3006         trans->sorted[path->sorted_idx] = path->idx;
3007 #else
3008         array_insert_item(trans->sorted, trans->nr_sorted, path->sorted_idx, path->idx);
3009 #endif
3010
3011         for (i = path->sorted_idx; i < trans->nr_sorted; i++)
3012                 trans->paths[trans->sorted[i]].sorted_idx = i;
3013
3014         btree_trans_verify_sorted_refs(trans);
3015 }
3016
3017 void bch2_trans_iter_exit(struct btree_trans *trans, struct btree_iter *iter)
3018 {
3019         if (iter->path)
3020                 bch2_path_put(trans, iter->path,
3021                               iter->flags & BTREE_ITER_INTENT);
3022         if (iter->update_path)
3023                 bch2_path_put(trans, iter->update_path,
3024                               iter->flags & BTREE_ITER_INTENT);
3025         if (iter->key_cache_path)
3026                 bch2_path_put(trans, iter->key_cache_path,
3027                               iter->flags & BTREE_ITER_INTENT);
3028         iter->path = NULL;
3029         iter->update_path = NULL;
3030         iter->key_cache_path = NULL;
3031 }
3032
3033 static void __bch2_trans_iter_init(struct btree_trans *trans,
3034                                    struct btree_iter *iter,
3035                                    enum btree_id btree_id, struct bpos pos,
3036                                    unsigned locks_want,
3037                                    unsigned depth,
3038                                    unsigned flags)
3039 {
3040         EBUG_ON(trans->restarted);
3041
3042         if (flags & BTREE_ITER_ALL_LEVELS)
3043                 flags |= BTREE_ITER_ALL_SNAPSHOTS|__BTREE_ITER_ALL_SNAPSHOTS;
3044
3045         if (!(flags & (BTREE_ITER_ALL_SNAPSHOTS|BTREE_ITER_NOT_EXTENTS)) &&
3046             btree_node_type_is_extents(btree_id))
3047                 flags |= BTREE_ITER_IS_EXTENTS;
3048
3049         if (!(flags & __BTREE_ITER_ALL_SNAPSHOTS) &&
3050             !btree_type_has_snapshots(btree_id))
3051                 flags &= ~BTREE_ITER_ALL_SNAPSHOTS;
3052
3053         if (!(flags & BTREE_ITER_ALL_SNAPSHOTS) &&
3054             btree_type_has_snapshots(btree_id))
3055                 flags |= BTREE_ITER_FILTER_SNAPSHOTS;
3056
3057         if (trans->journal_replay_not_finished)
3058                 flags |= BTREE_ITER_WITH_JOURNAL;
3059
3060         iter->trans     = trans;
3061         iter->path      = NULL;
3062         iter->update_path = NULL;
3063         iter->key_cache_path = NULL;
3064         iter->btree_id  = btree_id;
3065         iter->min_depth = depth;
3066         iter->flags     = flags;
3067         iter->snapshot  = pos.snapshot;
3068         iter->pos       = pos;
3069         iter->k.type    = KEY_TYPE_deleted;
3070         iter->k.p       = pos;
3071         iter->k.size    = 0;
3072
3073         iter->path = bch2_path_get(trans, btree_id, iter->pos,
3074                                    locks_want, depth, flags);
3075 }
3076
3077 void bch2_trans_iter_init(struct btree_trans *trans,
3078                           struct btree_iter *iter,
3079                           unsigned btree_id, struct bpos pos,
3080                           unsigned flags)
3081 {
3082         if (!btree_id_cached(trans->c, btree_id)) {
3083                 flags &= ~BTREE_ITER_CACHED;
3084                 flags &= ~BTREE_ITER_WITH_KEY_CACHE;
3085         } else if (!(flags & BTREE_ITER_CACHED))
3086                 flags |= BTREE_ITER_WITH_KEY_CACHE;
3087
3088         __bch2_trans_iter_init(trans, iter, btree_id, pos,
3089                                0, 0, flags);
3090 }
3091
3092 void bch2_trans_node_iter_init(struct btree_trans *trans,
3093                                struct btree_iter *iter,
3094                                enum btree_id btree_id,
3095                                struct bpos pos,
3096                                unsigned locks_want,
3097                                unsigned depth,
3098                                unsigned flags)
3099 {
3100         __bch2_trans_iter_init(trans, iter, btree_id, pos, locks_want, depth,
3101                                BTREE_ITER_NOT_EXTENTS|
3102                                __BTREE_ITER_ALL_SNAPSHOTS|
3103                                BTREE_ITER_ALL_SNAPSHOTS|
3104                                flags);
3105         BUG_ON(iter->path->locks_want    < min(locks_want, BTREE_MAX_DEPTH));
3106         BUG_ON(iter->path->level        != depth);
3107         BUG_ON(iter->min_depth          != depth);
3108 }
3109
3110 void bch2_trans_copy_iter(struct btree_iter *dst, struct btree_iter *src)
3111 {
3112         *dst = *src;
3113         if (src->path)
3114                 __btree_path_get(src->path, src->flags & BTREE_ITER_INTENT);
3115         if (src->update_path)
3116                 __btree_path_get(src->update_path, src->flags & BTREE_ITER_INTENT);
3117         dst->key_cache_path = NULL;
3118 }
3119
3120 void *bch2_trans_kmalloc(struct btree_trans *trans, size_t size)
3121 {
3122         size_t new_top = trans->mem_top + size;
3123         void *p;
3124
3125         if (new_top > trans->mem_bytes) {
3126                 size_t old_bytes = trans->mem_bytes;
3127                 size_t new_bytes = roundup_pow_of_two(new_top);
3128                 void *new_mem;
3129
3130                 WARN_ON_ONCE(new_bytes > BTREE_TRANS_MEM_MAX);
3131
3132                 new_mem = krealloc(trans->mem, new_bytes, GFP_NOFS);
3133                 if (!new_mem && new_bytes <= BTREE_TRANS_MEM_MAX) {
3134                         new_mem = mempool_alloc(&trans->c->btree_trans_mem_pool, GFP_KERNEL);
3135                         new_bytes = BTREE_TRANS_MEM_MAX;
3136                         kfree(trans->mem);
3137                 }
3138
3139                 if (!new_mem)
3140                         return ERR_PTR(-ENOMEM);
3141
3142                 trans->mem = new_mem;
3143                 trans->mem_bytes = new_bytes;
3144
3145                 if (old_bytes) {
3146                         trace_trans_restart_mem_realloced(trans->fn, _RET_IP_, new_bytes);
3147                         btree_trans_restart(trans);
3148                         return ERR_PTR(-EINTR);
3149                 }
3150         }
3151
3152         p = trans->mem + trans->mem_top;
3153         trans->mem_top += size;
3154         memset(p, 0, size);
3155         return p;
3156 }
3157
3158 /**
3159  * bch2_trans_begin() - reset a transaction after a interrupted attempt
3160  * @trans: transaction to reset
3161  *
3162  * While iterating over nodes or updating nodes a attempt to lock a btree
3163  * node may return EINTR when the trylock fails. When this occurs
3164  * bch2_trans_begin() should be called and the transaction retried.
3165  */
3166 void bch2_trans_begin(struct btree_trans *trans)
3167 {
3168         struct btree_insert_entry *i;
3169         struct btree_path *path;
3170
3171         trans_for_each_update(trans, i)
3172                 __btree_path_put(i->path, true);
3173
3174         memset(&trans->journal_res, 0, sizeof(trans->journal_res));
3175         trans->extra_journal_res        = 0;
3176         trans->nr_updates               = 0;
3177         trans->mem_top                  = 0;
3178
3179         trans->hooks                    = NULL;
3180         trans->extra_journal_entries.nr = 0;
3181
3182         if (trans->fs_usage_deltas) {
3183                 trans->fs_usage_deltas->used = 0;
3184                 memset((void *) trans->fs_usage_deltas +
3185                        offsetof(struct replicas_delta_list, memset_start), 0,
3186                        (void *) &trans->fs_usage_deltas->memset_end -
3187                        (void *) &trans->fs_usage_deltas->memset_start);
3188         }
3189
3190         trans_for_each_path(trans, path) {
3191                 path->should_be_locked = false;
3192
3193                 /*
3194                  * If the transaction wasn't restarted, we're presuming to be
3195                  * doing something new: dont keep iterators excpt the ones that
3196                  * are in use - except for the subvolumes btree:
3197                  */
3198                 if (!trans->restarted && path->btree_id != BTREE_ID_subvolumes)
3199                         path->preserve = false;
3200
3201                 /*
3202                  * XXX: we probably shouldn't be doing this if the transaction
3203                  * was restarted, but currently we still overflow transaction
3204                  * iterators if we do that
3205                  */
3206                 if (!path->ref && !path->preserve)
3207                         __bch2_path_free(trans, path);
3208                 else
3209                         path->preserve = false;
3210         }
3211
3212         bch2_trans_cond_resched(trans);
3213
3214         if (trans->restarted)
3215                 bch2_btree_path_traverse_all(trans);
3216
3217         trans->restarted = false;
3218 }
3219
3220 static void bch2_trans_alloc_paths(struct btree_trans *trans, struct bch_fs *c)
3221 {
3222         size_t paths_bytes      = sizeof(struct btree_path) * BTREE_ITER_MAX;
3223         size_t updates_bytes    = sizeof(struct btree_insert_entry) * BTREE_ITER_MAX;
3224         void *p = NULL;
3225
3226         BUG_ON(trans->used_mempool);
3227
3228 #ifdef __KERNEL__
3229         p = this_cpu_xchg(c->btree_paths_bufs->path , NULL);
3230 #endif
3231         if (!p)
3232                 p = mempool_alloc(&trans->c->btree_paths_pool, GFP_NOFS);
3233
3234         trans->paths            = p; p += paths_bytes;
3235         trans->updates          = p; p += updates_bytes;
3236 }
3237
3238 void __bch2_trans_init(struct btree_trans *trans, struct bch_fs *c,
3239                        unsigned expected_nr_iters,
3240                        size_t expected_mem_bytes,
3241                        const char *fn)
3242         __acquires(&c->btree_trans_barrier)
3243 {
3244         memset(trans, 0, sizeof(*trans));
3245         trans->c                = c;
3246         trans->fn               = fn;
3247         trans->journal_replay_not_finished =
3248                 !test_bit(JOURNAL_REPLAY_DONE, &c->journal.flags);
3249
3250         bch2_trans_alloc_paths(trans, c);
3251
3252         if (expected_mem_bytes) {
3253                 expected_mem_bytes = roundup_pow_of_two(expected_mem_bytes);
3254                 trans->mem = kmalloc(expected_mem_bytes, GFP_KERNEL);
3255
3256                 if (!unlikely(trans->mem)) {
3257                         trans->mem = mempool_alloc(&c->btree_trans_mem_pool, GFP_KERNEL);
3258                         trans->mem_bytes = BTREE_TRANS_MEM_MAX;
3259                 } else {
3260                         trans->mem_bytes = expected_mem_bytes;
3261                 }
3262         }
3263
3264         trans->srcu_idx = srcu_read_lock(&c->btree_trans_barrier);
3265
3266         if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG_TRANSACTIONS)) {
3267                 trans->pid = current->pid;
3268                 mutex_lock(&c->btree_trans_lock);
3269                 list_add(&trans->list, &c->btree_trans_list);
3270                 mutex_unlock(&c->btree_trans_lock);
3271         }
3272 }
3273
3274 static void check_btree_paths_leaked(struct btree_trans *trans)
3275 {
3276 #ifdef CONFIG_BCACHEFS_DEBUG
3277         struct bch_fs *c = trans->c;
3278         struct btree_path *path;
3279
3280         trans_for_each_path(trans, path)
3281                 if (path->ref)
3282                         goto leaked;
3283         return;
3284 leaked:
3285         bch_err(c, "btree paths leaked from %s!", trans->fn);
3286         trans_for_each_path(trans, path)
3287                 if (path->ref)
3288                         printk(KERN_ERR "  btree %s %pS\n",
3289                                bch2_btree_ids[path->btree_id],
3290                                (void *) path->ip_allocated);
3291         /* Be noisy about this: */
3292         bch2_fatal_error(c);
3293 #endif
3294 }
3295
3296 void bch2_trans_exit(struct btree_trans *trans)
3297         __releases(&c->btree_trans_barrier)
3298 {
3299         struct btree_insert_entry *i;
3300         struct bch_fs *c = trans->c;
3301
3302         bch2_trans_unlock(trans);
3303
3304         trans_for_each_update(trans, i)
3305                 __btree_path_put(i->path, true);
3306         trans->nr_updates               = 0;
3307
3308         check_btree_paths_leaked(trans);
3309
3310         if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG_TRANSACTIONS)) {
3311                 mutex_lock(&c->btree_trans_lock);
3312                 list_del(&trans->list);
3313                 mutex_unlock(&c->btree_trans_lock);
3314         }
3315
3316         srcu_read_unlock(&c->btree_trans_barrier, trans->srcu_idx);
3317
3318         bch2_journal_preres_put(&c->journal, &trans->journal_preres);
3319
3320         kfree(trans->extra_journal_entries.data);
3321
3322         if (trans->fs_usage_deltas) {
3323                 if (trans->fs_usage_deltas->size + sizeof(trans->fs_usage_deltas) ==
3324                     REPLICAS_DELTA_LIST_MAX)
3325                         mempool_free(trans->fs_usage_deltas,
3326                                      &c->replicas_delta_pool);
3327                 else
3328                         kfree(trans->fs_usage_deltas);
3329         }
3330
3331         if (trans->mem_bytes == BTREE_TRANS_MEM_MAX)
3332                 mempool_free(trans->mem, &c->btree_trans_mem_pool);
3333         else
3334                 kfree(trans->mem);
3335
3336 #ifdef __KERNEL__
3337         /*
3338          * Userspace doesn't have a real percpu implementation:
3339          */
3340         trans->paths = this_cpu_xchg(c->btree_paths_bufs->path, trans->paths);
3341 #endif
3342
3343         if (trans->paths)
3344                 mempool_free(trans->paths, &c->btree_paths_pool);
3345
3346         trans->mem      = (void *) 0x1;
3347         trans->paths    = (void *) 0x1;
3348 }
3349
3350 static void __maybe_unused
3351 bch2_btree_path_node_to_text(struct printbuf *out,
3352                              struct btree_bkey_cached_common *_b,
3353                              bool cached)
3354 {
3355         pr_buf(out, "    l=%u %s:",
3356                _b->level, bch2_btree_ids[_b->btree_id]);
3357         bch2_bpos_to_text(out, btree_node_pos(_b, cached));
3358 }
3359
3360 #ifdef CONFIG_BCACHEFS_DEBUG_TRANSACTIONS
3361 static bool trans_has_locks(struct btree_trans *trans)
3362 {
3363         struct btree_path *path;
3364
3365         trans_for_each_path(trans, path)
3366                 if (path->nodes_locked)
3367                         return true;
3368         return false;
3369 }
3370 #endif
3371
3372 void bch2_btree_trans_to_text(struct printbuf *out, struct bch_fs *c)
3373 {
3374 #ifdef CONFIG_BCACHEFS_DEBUG_TRANSACTIONS
3375         struct btree_trans *trans;
3376         struct btree_path *path;
3377         struct btree *b;
3378         static char lock_types[] = { 'r', 'i', 'w' };
3379         unsigned l;
3380
3381         mutex_lock(&c->btree_trans_lock);
3382         list_for_each_entry(trans, &c->btree_trans_list, list) {
3383                 if (!trans_has_locks(trans))
3384                         continue;
3385
3386                 pr_buf(out, "%i %s\n", trans->pid, trans->fn);
3387
3388                 trans_for_each_path(trans, path) {
3389                         if (!path->nodes_locked)
3390                                 continue;
3391
3392                         pr_buf(out, "  path %u %c l=%u %s:",
3393                                path->idx,
3394                                path->cached ? 'c' : 'b',
3395                                path->level,
3396                                bch2_btree_ids[path->btree_id]);
3397                         bch2_bpos_to_text(out, path->pos);
3398                         pr_buf(out, "\n");
3399
3400                         for (l = 0; l < BTREE_MAX_DEPTH; l++) {
3401                                 if (btree_node_locked(path, l)) {
3402                                         pr_buf(out, "    %s l=%u ",
3403                                                btree_node_intent_locked(path, l) ? "i" : "r", l);
3404                                         bch2_btree_path_node_to_text(out,
3405                                                         (void *) path->l[l].b,
3406                                                         path->cached);
3407                                         pr_buf(out, "\n");
3408                                 }
3409                         }
3410                 }
3411
3412                 b = READ_ONCE(trans->locking);
3413                 if (b) {
3414                         path = &trans->paths[trans->locking_path_idx];
3415                         pr_buf(out, "  locking path %u %c l=%u %c %s:",
3416                                trans->locking_path_idx,
3417                                path->cached ? 'c' : 'b',
3418                                trans->locking_level,
3419                                lock_types[trans->locking_lock_type],
3420                                bch2_btree_ids[trans->locking_btree_id]);
3421                         bch2_bpos_to_text(out, trans->locking_pos);
3422
3423                         pr_buf(out, " node ");
3424                         bch2_btree_path_node_to_text(out,
3425                                         (void *) b, path->cached);
3426                         pr_buf(out, "\n");
3427                 }
3428         }
3429         mutex_unlock(&c->btree_trans_lock);
3430 #endif
3431 }
3432
3433 void bch2_fs_btree_iter_exit(struct bch_fs *c)
3434 {
3435         if (c->btree_trans_barrier_initialized)
3436                 cleanup_srcu_struct(&c->btree_trans_barrier);
3437         mempool_exit(&c->btree_trans_mem_pool);
3438         mempool_exit(&c->btree_paths_pool);
3439 }
3440
3441 int bch2_fs_btree_iter_init(struct bch_fs *c)
3442 {
3443         unsigned nr = BTREE_ITER_MAX;
3444         int ret;
3445
3446         INIT_LIST_HEAD(&c->btree_trans_list);
3447         mutex_init(&c->btree_trans_lock);
3448
3449         ret   = mempool_init_kmalloc_pool(&c->btree_paths_pool, 1,
3450                         sizeof(struct btree_path) * nr +
3451                         sizeof(struct btree_insert_entry) * nr) ?:
3452                 mempool_init_kmalloc_pool(&c->btree_trans_mem_pool, 1,
3453                                           BTREE_TRANS_MEM_MAX) ?:
3454                 init_srcu_struct(&c->btree_trans_barrier);
3455         if (!ret)
3456                 c->btree_trans_barrier_initialized = true;
3457         return ret;
3458 }