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