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