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

   1
   2 #include "bcachefs.h"
   3 #include "bkey_methods.h"
   4 #include "btree_cache.h"
   5 #include "btree_iter.h"
   6 #include "btree_locking.h"
   7 #include "debug.h"
   8 #include "extents.h"
   9
  10 #include <linux/prefetch.h>
  11 #include <trace/events/bcachefs.h>
  12
  13 static inline struct bkey_s_c __btree_iter_peek_all(struct btree_iter *,
  14                                                     struct btree_iter_level *,
  15                                                     struct bkey *);
  16
  17 #define BTREE_ITER_NOT_END      ((struct btree *) 1)
  18
  19 static inline bool is_btree_node(struct btree_iter *iter, unsigned l)
  20 {
  21         return iter->l[l].b && iter->l[l].b != BTREE_ITER_NOT_END;
  22 }
  23
  24 /* Btree node locking: */
  25
  26 /*
  27  * Updates the saved lock sequence number, so that bch2_btree_node_relock() will
  28  * succeed:
  29  */
  30 void bch2_btree_node_unlock_write(struct btree *b, struct btree_iter *iter)
  31 {
  32         struct btree_iter *linked;
  33
  34         EBUG_ON(iter->l[b->level].b != b);
  35         EBUG_ON(iter->lock_seq[b->level] + 1 != b->lock.state.seq);
  36
  37         for_each_linked_btree_node(iter, b, linked)
  38                 linked->lock_seq[b->level] += 2;
  39
  40         iter->lock_seq[b->level] += 2;
  41
  42         six_unlock_write(&b->lock);
  43 }
  44
  45 void bch2_btree_node_lock_write(struct btree *b, struct btree_iter *iter)
  46 {
  47         struct btree_iter *linked;
  48         unsigned readers = 0;
  49
  50         EBUG_ON(iter->l[b->level].b != b);
  51         EBUG_ON(iter->lock_seq[b->level] != b->lock.state.seq);
  52
  53         if (six_trylock_write(&b->lock))
  54                 return;
  55
  56         for_each_linked_btree_iter(iter, linked)
  57                 if (linked->l[b->level].b == b &&
  58                     btree_node_read_locked(linked, b->level))
  59                         readers++;
  60
  61         if (likely(!readers)) {
  62                 six_lock_write(&b->lock);
  63         } else {
  64                 /*
  65                  * Must drop our read locks before calling six_lock_write() -
  66                  * six_unlock() won't do wakeups until the reader count
  67                  * goes to 0, and it's safe because we have the node intent
  68                  * locked:
  69                  */
  70                 atomic64_sub(__SIX_VAL(read_lock, readers),
  71                              &b->lock.state.counter);
  72                 six_lock_write(&b->lock);
  73                 atomic64_add(__SIX_VAL(read_lock, readers),
  74                              &b->lock.state.counter);
  75         }
  76 }
  77
  78 bool __bch2_btree_node_relock(struct btree_iter *iter, unsigned level)
  79 {
  80         struct btree_iter *linked;
  81         struct btree *b = iter->l[level].b;
  82         int want = btree_lock_want(iter, level);
  83         int have = btree_node_locked_type(iter, level);
  84
  85         if (want == have)
  86                 return true;
  87
  88         if (!is_btree_node(iter, level))
  89                 return false;
  90
  91         if (race_fault())
  92                 return false;
  93
  94         if (have != BTREE_NODE_UNLOCKED
  95             ? six_trylock_convert(&b->lock, have, want)
  96             : six_relock_type(&b->lock, want, iter->lock_seq[level]))
  97                 goto success;
  98
  99         for_each_linked_btree_iter(iter, linked)
 100                 if (linked->l[level].b == b &&
 101                     btree_node_locked_type(linked, level) == want &&
 102                     iter->lock_seq[level] == b->lock.state.seq) {
 103                         btree_node_unlock(iter, level);
 104                         six_lock_increment(&b->lock, want);
 105                         goto success;
 106                 }
 107
 108         return false;
 109 success:
 110         mark_btree_node_unlocked(iter, level);
 111         mark_btree_node_locked(iter, level, want);
 112         return true;
 113 }
 114
 115 bool bch2_btree_iter_relock(struct btree_iter *iter)
 116 {
 117         unsigned l;
 118
 119         for (l = iter->level;
 120              l < max_t(unsigned, iter->locks_want, 1) && iter->l[l].b;
 121              l++)
 122                 if (!bch2_btree_node_relock(iter, l)) {
 123                         btree_iter_set_dirty(iter, BTREE_ITER_NEED_TRAVERSE);
 124                         return false;
 125                 }
 126
 127         if (iter->uptodate == BTREE_ITER_NEED_RELOCK)
 128                 iter->uptodate = BTREE_ITER_NEED_PEEK;
 129         return true;
 130 }
 131
 132 /* Slowpath: */
 133 bool __bch2_btree_node_lock(struct btree *b, struct bpos pos,
 134                            unsigned level,
 135                            struct btree_iter *iter,
 136                            enum six_lock_type type)
 137 {
 138         struct btree_iter *linked;
 139
 140         /* Can't have children locked before ancestors: */
 141         EBUG_ON(iter->nodes_locked && level > __ffs(iter->nodes_locked));
 142
 143         /*
 144          * Can't hold any read locks while we block taking an intent lock - see
 145          * below for reasoning, and we should have already dropped any read
 146          * locks in the current iterator
 147          */
 148         EBUG_ON(type == SIX_LOCK_intent &&
 149                 iter->nodes_locked != iter->nodes_intent_locked);
 150
 151         for_each_linked_btree_iter(iter, linked)
 152                 if (linked->l[level].b == b &&
 153                     btree_node_locked_type(linked, level) == type) {
 154                         six_lock_increment(&b->lock, type);
 155                         return true;
 156                 }
 157
 158         /*
 159          * Must lock btree nodes in key order - this case hapens when locking
 160          * the prev sibling in btree node merging:
 161          */
 162         if (iter->nodes_locked &&
 163             __ffs(iter->nodes_locked) == level &&
 164             __btree_iter_cmp(iter->btree_id, pos, iter))
 165                 return false;
 166
 167         for_each_linked_btree_iter(iter, linked) {
 168                 if (!linked->nodes_locked)
 169                         continue;
 170
 171                 /*
 172                  * Can't block taking an intent lock if we have _any_ nodes read
 173                  * locked:
 174                  *
 175                  * - Our read lock blocks another thread with an intent lock on
 176                  *   the same node from getting a write lock, and thus from
 177                  *   dropping its intent lock
 178                  *
 179                  * - And the other thread may have multiple nodes intent locked:
 180                  *   both the node we want to intent lock, and the node we
 181                  *   already have read locked - deadlock:
 182                  */
 183                 if (type == SIX_LOCK_intent &&
 184                     linked->nodes_locked != linked->nodes_intent_locked) {
 185                         linked->locks_want = max_t(unsigned,
 186                                                    linked->locks_want,
 187                                                    iter->locks_want);
 188                         return false;
 189                 }
 190
 191                 /* We have to lock btree nodes in key order: */
 192                 if (__btree_iter_cmp(iter->btree_id, pos, linked) < 0)
 193                         return false;
 194
 195                 /*
 196                  * Interior nodes must be locked before their descendants: if
 197                  * another iterator has possible descendants locked of the node
 198                  * we're about to lock, it must have the ancestors locked too:
 199                  */
 200                 if (linked->btree_id == iter->btree_id &&
 201                     level > __fls(linked->nodes_locked)) {
 202                         linked->locks_want = max_t(unsigned,
 203                                                    linked->locks_want,
 204                                                    iter->locks_want);
 205                         return false;
 206                 }
 207         }
 208
 209         six_lock_type(&b->lock, type);
 210         return true;
 211 }
 212
 213 /* Btree iterator locking: */
 214
 215 static void btree_iter_drop_extra_locks(struct btree_iter *iter)
 216 {
 217         unsigned l;
 218
 219         while (iter->nodes_locked &&
 220                (l = __fls(iter->nodes_locked)) > iter->locks_want) {
 221                 if (l > iter->level) {
 222                         btree_node_unlock(iter, l);
 223                 } else {
 224                         if (btree_node_intent_locked(iter, l)) {
 225                                 six_lock_downgrade(&iter->l[l].b->lock);
 226                                 iter->nodes_intent_locked ^= 1 << l;
 227                         }
 228                         break;
 229                 }
 230         }
 231 }
 232
 233 bool __bch2_btree_iter_set_locks_want(struct btree_iter *iter,
 234                                      unsigned new_locks_want)
 235 {
 236         struct btree_iter *linked;
 237
 238         /* Drop locks we don't want anymore: */
 239         if (new_locks_want < iter->locks_want)
 240                 for_each_linked_btree_iter(iter, linked)
 241                         if (linked->locks_want > new_locks_want) {
 242                                 linked->locks_want = max_t(unsigned, 1,
 243                                                            new_locks_want);
 244                                 btree_iter_drop_extra_locks(linked);
 245                         }
 246
 247         iter->locks_want = new_locks_want;
 248         btree_iter_drop_extra_locks(iter);
 249
 250         if (bch2_btree_iter_relock(iter))
 251                 return true;
 252
 253         /*
 254          * Just an optimization: ancestor nodes must be locked before child
 255          * nodes, so set locks_want on iterators that might lock ancestors
 256          * before us to avoid getting -EINTR later:
 257          */
 258         for_each_linked_btree_iter(iter, linked)
 259                 if (linked->btree_id == iter->btree_id &&
 260                     btree_iter_cmp(linked, iter) <= 0)
 261                         linked->locks_want = max_t(unsigned, linked->locks_want,
 262                                                    new_locks_want);
 263         return false;
 264 }
 265
 266 static void __bch2_btree_iter_unlock(struct btree_iter *iter)
 267 {
 268         btree_iter_set_dirty(iter, BTREE_ITER_NEED_RELOCK);
 269
 270         while (iter->nodes_locked)
 271                 btree_node_unlock(iter, __ffs(iter->nodes_locked));
 272 }
 273
 274 int bch2_btree_iter_unlock(struct btree_iter *iter)
 275 {
 276         struct btree_iter *linked;
 277
 278         for_each_linked_btree_iter(iter, linked)
 279                 __bch2_btree_iter_unlock(linked);
 280         __bch2_btree_iter_unlock(iter);
 281
 282         return iter->flags & BTREE_ITER_ERROR ? -EIO : 0;
 283 }
 284
 285 /* Btree iterator: */
 286
 287 #ifdef CONFIG_BCACHEFS_DEBUG
 288
 289 static void __bch2_btree_iter_verify(struct btree_iter *iter,
 290                                      struct btree *b)
 291 {
 292         struct btree_iter_level *l = &iter->l[b->level];
 293         struct btree_node_iter tmp = l->iter;
 294         struct bkey_packed *k;
 295
 296         bch2_btree_node_iter_verify(&l->iter, b);
 297
 298         /*
 299          * For interior nodes, the iterator will have skipped past
 300          * deleted keys:
 301          */
 302         k = b->level
 303                 ? bch2_btree_node_iter_prev(&tmp, b)
 304                 : bch2_btree_node_iter_prev_all(&tmp, b);
 305         if (k && btree_iter_pos_cmp_packed(b, &iter->pos, k,
 306                                 iter->flags & BTREE_ITER_IS_EXTENTS)) {
 307                 char buf[100];
 308                 struct bkey uk = bkey_unpack_key(b, k);
 309
 310                 bch2_bkey_to_text(buf, sizeof(buf), &uk);
 311                 panic("prev key should be before after pos:\n%s\n%llu:%llu\n",
 312                       buf, iter->pos.inode, iter->pos.offset);
 313         }
 314
 315         k = bch2_btree_node_iter_peek_all(&l->iter, b);
 316         if (k && !btree_iter_pos_cmp_packed(b, &iter->pos, k,
 317                                 iter->flags & BTREE_ITER_IS_EXTENTS)) {
 318                 char buf[100];
 319                 struct bkey uk = bkey_unpack_key(b, k);
 320
 321                 bch2_bkey_to_text(buf, sizeof(buf), &uk);
 322                 panic("next key should be before iter pos:\n%llu:%llu\n%s\n",
 323                       iter->pos.inode, iter->pos.offset, buf);
 324         }
 325 }
 326
 327 void bch2_btree_iter_verify(struct btree_iter *iter, struct btree *b)
 328 {
 329         struct btree_iter *linked;
 330
 331         if (iter->l[b->level].b == b)
 332                 __bch2_btree_iter_verify(iter, b);
 333
 334         for_each_linked_btree_node(iter, b, linked)
 335                 __bch2_btree_iter_verify(iter, b);
 336 }
 337
 338 #endif
 339
 340 static void __bch2_btree_node_iter_fix(struct btree_iter *iter,
 341                                       struct btree *b,
 342                                       struct btree_node_iter *node_iter,
 343                                       struct bset_tree *t,
 344                                       struct bkey_packed *where,
 345                                       unsigned clobber_u64s,
 346                                       unsigned new_u64s)
 347 {
 348         const struct bkey_packed *end = btree_bkey_last(b, t);
 349         struct btree_node_iter_set *set;
 350         unsigned offset = __btree_node_key_to_offset(b, where);
 351         int shift = new_u64s - clobber_u64s;
 352         unsigned old_end = (int) __btree_node_key_to_offset(b, end) - shift;
 353
 354         btree_node_iter_for_each(node_iter, set)
 355                 if (set->end == old_end)
 356                         goto found;
 357
 358         /* didn't find the bset in the iterator - might have to readd it: */
 359         if (new_u64s &&
 360             btree_iter_pos_cmp_packed(b, &iter->pos, where,
 361                                       iter->flags & BTREE_ITER_IS_EXTENTS)) {
 362                 bch2_btree_node_iter_push(node_iter, b, where, end);
 363
 364                 if (!b->level &&
 365                     node_iter == &iter->l[0].iter)
 366                         bkey_disassemble(b,
 367                                 bch2_btree_node_iter_peek_all(node_iter, b),
 368                                 &iter->k);
 369         }
 370         return;
 371 found:
 372         set->end = (int) set->end + shift;
 373
 374         /* Iterator hasn't gotten to the key that changed yet: */
 375         if (set->k < offset)
 376                 return;
 377
 378         if (new_u64s &&
 379             btree_iter_pos_cmp_packed(b, &iter->pos, where,
 380                                 iter->flags & BTREE_ITER_IS_EXTENTS)) {
 381                 set->k = offset;
 382         } else if (set->k < offset + clobber_u64s) {
 383                 set->k = offset + new_u64s;
 384                 if (set->k == set->end)
 385                         bch2_btree_node_iter_set_drop(node_iter, set);
 386         } else {
 387                 set->k = (int) set->k + shift;
 388                 goto iter_current_key_not_modified;
 389         }
 390
 391         bch2_btree_node_iter_sort(node_iter, b);
 392         if (!b->level && node_iter == &iter->l[0].iter)
 393                 __btree_iter_peek_all(iter, &iter->l[0], &iter->k);
 394 iter_current_key_not_modified:
 395
 396         /*
 397          * Interior nodes are special because iterators for interior nodes don't
 398          * obey the usual invariants regarding the iterator position:
 399          *
 400          * We may have whiteouts that compare greater than the iterator
 401          * position, and logically should be in the iterator, but that we
 402          * skipped past to find the first live key greater than the iterator
 403          * position. This becomes an issue when we insert a new key that is
 404          * greater than the current iterator position, but smaller than the
 405          * whiteouts we've already skipped past - this happens in the course of
 406          * a btree split.
 407          *
 408          * We have to rewind the iterator past to before those whiteouts here,
 409          * else bkey_node_iter_prev() is not going to work and who knows what
 410          * else would happen. And we have to do it manually, because here we've
 411          * already done the insert and the iterator is currently inconsistent:
 412          *
 413          * We've got multiple competing invariants, here - we have to be careful
 414          * about rewinding iterators for interior nodes, because they should
 415          * always point to the key for the child node the btree iterator points
 416          * to.
 417          */
 418         if (b->level && new_u64s && !bkey_deleted(where) &&
 419             btree_iter_pos_cmp_packed(b, &iter->pos, where,
 420                                 iter->flags & BTREE_ITER_IS_EXTENTS)) {
 421                 struct bset_tree *t;
 422                 struct bkey_packed *k;
 423
 424                 for_each_bset(b, t) {
 425                         if (bch2_bkey_to_bset(b, where) == t)
 426                                 continue;
 427
 428                         k = bch2_bkey_prev_all(b, t,
 429                                 bch2_btree_node_iter_bset_pos(node_iter, b, t));
 430                         if (k &&
 431                             __btree_node_iter_cmp(node_iter, b,
 432                                                   k, where) > 0) {
 433                                 struct btree_node_iter_set *set;
 434                                 unsigned offset =
 435                                         __btree_node_key_to_offset(b, bkey_next(k));
 436
 437                                 btree_node_iter_for_each(node_iter, set)
 438                                         if (set->k == offset) {
 439                                                 set->k = __btree_node_key_to_offset(b, k);
 440                                                 bch2_btree_node_iter_sort(node_iter, b);
 441                                                 goto next_bset;
 442                                         }
 443
 444                                 bch2_btree_node_iter_push(node_iter, b, k,
 445                                                 btree_bkey_last(b, t));
 446                         }
 447 next_bset:
 448                         t = t;
 449                 }
 450         }
 451 }
 452
 453 void bch2_btree_node_iter_fix(struct btree_iter *iter,
 454                              struct btree *b,
 455                              struct btree_node_iter *node_iter,
 456                              struct bset_tree *t,
 457                              struct bkey_packed *where,
 458                              unsigned clobber_u64s,
 459                              unsigned new_u64s)
 460 {
 461         struct btree_iter *linked;
 462
 463         if (node_iter != &iter->l[b->level].iter)
 464                 __bch2_btree_node_iter_fix(iter, b, node_iter, t,
 465                                           where, clobber_u64s, new_u64s);
 466
 467         if (iter->l[b->level].b == b)
 468                 __bch2_btree_node_iter_fix(iter, b,
 469                                           &iter->l[b->level].iter, t,
 470                                           where, clobber_u64s, new_u64s);
 471
 472         for_each_linked_btree_node(iter, b, linked)
 473                 __bch2_btree_node_iter_fix(linked, b,
 474                                           &linked->l[b->level].iter, t,
 475                                           where, clobber_u64s, new_u64s);
 476
 477         /* interior node iterators are... special... */
 478         if (!b->level)
 479                 bch2_btree_iter_verify(iter, b);
 480 }
 481
 482 static inline struct bkey_s_c __btree_iter_unpack(struct btree_iter *iter,
 483                                                   struct btree_iter_level *l,
 484                                                   struct bkey *u,
 485                                                   struct bkey_packed *k)
 486 {
 487         struct bkey_s_c ret;
 488
 489         if (unlikely(!k)) {
 490                 /*
 491                  * signal to bch2_btree_iter_peek_slot() that we're currently at
 492                  * a hole
 493                  */
 494                 u->type = KEY_TYPE_DELETED;
 495                 return bkey_s_c_null;
 496         }
 497
 498         ret = bkey_disassemble(l->b, k, u);
 499
 500         if (debug_check_bkeys(iter->c))
 501                 bch2_bkey_debugcheck(iter->c, l->b, ret);
 502
 503         return ret;
 504 }
 505
 506 /* peek_all() doesn't skip deleted keys */
 507 static inline struct bkey_s_c __btree_iter_peek_all(struct btree_iter *iter,
 508                                                     struct btree_iter_level *l,
 509                                                     struct bkey *u)
 510 {
 511         return __btree_iter_unpack(iter, l, u,
 512                         bch2_btree_node_iter_peek_all(&l->iter, l->b));
 513 }
 514
 515 static inline struct bkey_s_c __btree_iter_peek(struct btree_iter *iter,
 516                                                 struct btree_iter_level *l)
 517 {
 518         return __btree_iter_unpack(iter, l, &iter->k,
 519                         bch2_btree_node_iter_peek(&l->iter, l->b));
 520 }
 521
 522 static inline void __btree_iter_advance(struct btree_iter_level *l)
 523 {
 524         bch2_btree_node_iter_advance(&l->iter, l->b);
 525 }
 526
 527 /*
 528  * Verify that iterator for parent node points to child node:
 529  */
 530 static void btree_iter_verify_new_node(struct btree_iter *iter, struct btree *b)
 531 {
 532         struct btree_iter_level *l;
 533         unsigned plevel;
 534         bool parent_locked;
 535         struct bkey_packed *k;
 536
 537         if (!IS_ENABLED(CONFIG_BCACHEFS_DEBUG))
 538                 return;
 539
 540         plevel = b->level + 1;
 541         if (!btree_iter_node(iter, plevel))
 542                 return;
 543
 544         parent_locked = btree_node_locked(iter, plevel);
 545
 546         if (!bch2_btree_node_relock(iter, plevel))
 547                 return;
 548
 549         l = &iter->l[plevel];
 550         k = bch2_btree_node_iter_peek_all(&l->iter, l->b);
 551         if (!k ||
 552             bkey_deleted(k) ||
 553             bkey_cmp_left_packed(l->b, k, &b->key.k.p)) {
 554                 char buf[100];
 555                 struct bkey uk = bkey_unpack_key(b, k);
 556
 557                 bch2_bkey_to_text(buf, sizeof(buf), &uk);
 558                 panic("parent iter doesn't point to new node:\n%s\n%llu:%llu\n",
 559                       buf, b->key.k.p.inode, b->key.k.p.offset);
 560         }
 561
 562         if (!parent_locked)
 563                 btree_node_unlock(iter, b->level + 1);
 564 }
 565
 566 /* Returns true if @k is after iterator position @pos */
 567 static inline bool btree_iter_pos_cmp(struct btree_iter *iter,
 568                                       const struct bkey *k)
 569 {
 570         int cmp = bkey_cmp(k->p, iter->pos);
 571
 572         return cmp > 0 ||
 573                 (cmp == 0 &&
 574                  !(iter->flags & BTREE_ITER_IS_EXTENTS) && !bkey_deleted(k));
 575 }
 576
 577 static inline bool btree_iter_pos_after_node(struct btree_iter *iter,
 578                                              struct btree *b)
 579 {
 580         return !btree_iter_pos_cmp(iter, &b->key.k);
 581 }
 582
 583 static inline bool btree_iter_pos_in_node(struct btree_iter *iter,
 584                                           struct btree *b)
 585 {
 586         return iter->btree_id == b->btree_id &&
 587                 bkey_cmp(iter->pos, b->data->min_key) >= 0 &&
 588                 !btree_iter_pos_after_node(iter, b);
 589 }
 590
 591 static inline void __btree_iter_init(struct btree_iter *iter,
 592                                      struct btree *b)
 593 {
 594         struct btree_iter_level *l = &iter->l[b->level];
 595
 596         bch2_btree_node_iter_init(&l->iter, b, iter->pos,
 597                                   iter->flags & BTREE_ITER_IS_EXTENTS,
 598                                   btree_node_is_extents(b));
 599
 600         /* Skip to first non whiteout: */
 601         if (b->level)
 602                 bch2_btree_node_iter_peek(&l->iter, b);
 603 }
 604
 605 static inline void btree_iter_node_set(struct btree_iter *iter,
 606                                        struct btree *b)
 607 {
 608         btree_iter_verify_new_node(iter, b);
 609
 610         EBUG_ON(!btree_iter_pos_in_node(iter, b));
 611         EBUG_ON(b->lock.state.seq & 1);
 612
 613         iter->lock_seq[b->level] = b->lock.state.seq;
 614         iter->l[b->level].b = b;
 615         __btree_iter_init(iter, b);
 616 }
 617
 618 /*
 619  * A btree node is being replaced - update the iterator to point to the new
 620  * node:
 621  */
 622 bool bch2_btree_iter_node_replace(struct btree_iter *iter, struct btree *b)
 623 {
 624         struct btree_iter *linked;
 625
 626         for_each_linked_btree_iter(iter, linked)
 627                 if (btree_iter_pos_in_node(linked, b)) {
 628                         /*
 629                          * bch2_btree_iter_node_drop() has already been called -
 630                          * the old node we're replacing has already been
 631                          * unlocked and the pointer invalidated
 632                          */
 633                         BUG_ON(btree_node_locked(linked, b->level));
 634
 635                         /*
 636                          * If @linked wants this node read locked, we don't want
 637                          * to actually take the read lock now because it's not
 638                          * legal to hold read locks on other nodes while we take
 639                          * write locks, so the journal can make forward
 640                          * progress...
 641                          *
 642                          * Instead, btree_iter_node_set() sets things up so
 643                          * bch2_btree_node_relock() will succeed:
 644                          */
 645
 646                         if (btree_want_intent(linked, b->level)) {
 647                                 six_lock_increment(&b->lock, SIX_LOCK_intent);
 648                                 mark_btree_node_intent_locked(linked, b->level);
 649                         }
 650
 651                         btree_iter_node_set(linked, b);
 652                 }
 653
 654         if (!btree_iter_pos_in_node(iter, b)) {
 655                 six_unlock_intent(&b->lock);
 656                 return false;
 657         }
 658
 659         mark_btree_node_intent_locked(iter, b->level);
 660         btree_iter_node_set(iter, b);
 661         return true;
 662 }
 663
 664 void bch2_btree_iter_node_drop_linked(struct btree_iter *iter, struct btree *b)
 665 {
 666         struct btree_iter *linked;
 667
 668         for_each_linked_btree_iter(iter, linked)
 669                 bch2_btree_iter_node_drop(linked, b);
 670 }
 671
 672 void bch2_btree_iter_node_drop(struct btree_iter *iter, struct btree *b)
 673 {
 674         unsigned level = b->level;
 675
 676         if (iter->l[level].b == b) {
 677                 btree_iter_set_dirty(iter, BTREE_ITER_NEED_TRAVERSE);
 678                 btree_node_unlock(iter, level);
 679                 iter->l[level].b = BTREE_ITER_NOT_END;
 680         }
 681 }
 682
 683 /*
 684  * A btree node has been modified in such a way as to invalidate iterators - fix
 685  * them:
 686  */
 687 void bch2_btree_iter_reinit_node(struct btree_iter *iter, struct btree *b)
 688 {
 689         struct btree_iter *linked;
 690
 691         for_each_linked_btree_node(iter, b, linked)
 692                 __btree_iter_init(linked, b);
 693         __btree_iter_init(iter, b);
 694 }
 695
 696 static inline int btree_iter_lock_root(struct btree_iter *iter,
 697                                        unsigned depth_want)
 698 {
 699         struct bch_fs *c = iter->c;
 700         struct btree *b;
 701         enum six_lock_type lock_type;
 702         unsigned i;
 703
 704         EBUG_ON(iter->nodes_locked);
 705
 706         while (1) {
 707                 b = READ_ONCE(c->btree_roots[iter->btree_id].b);
 708                 iter->level = READ_ONCE(b->level);
 709
 710                 if (unlikely(iter->level < depth_want)) {
 711                         /*
 712                          * the root is at a lower depth than the depth we want:
 713                          * got to the end of the btree, or we're walking nodes
 714                          * greater than some depth and there are no nodes >=
 715                          * that depth
 716                          */
 717                         iter->level = depth_want;
 718                         iter->l[iter->level].b = NULL;
 719                         return 0;
 720                 }
 721
 722                 lock_type = btree_lock_want(iter, iter->level);
 723                 if (unlikely(!btree_node_lock(b, POS_MAX, iter->level,
 724                                               iter, lock_type)))
 725                         return -EINTR;
 726
 727                 if (likely(b == c->btree_roots[iter->btree_id].b &&
 728                            b->level == iter->level &&
 729                            !race_fault())) {
 730                         for (i = 0; i < iter->level; i++)
 731                                 iter->l[i].b = BTREE_ITER_NOT_END;
 732                         iter->l[iter->level].b = b;
 733
 734                         mark_btree_node_locked(iter, iter->level, lock_type);
 735                         btree_iter_node_set(iter, b);
 736                         return 0;
 737
 738                 }
 739
 740                 six_unlock_type(&b->lock, lock_type);
 741         }
 742 }
 743
 744 noinline
 745 static void btree_iter_prefetch(struct btree_iter *iter)
 746 {
 747         struct btree_iter_level *l = &iter->l[iter->level];
 748         struct btree_node_iter node_iter = l->iter;
 749         struct bkey_packed *k;
 750         BKEY_PADDED(k) tmp;
 751         unsigned nr = iter->level > 1 ? 1 : 8;
 752         bool was_locked = btree_node_locked(iter, iter->level);
 753
 754         while (nr) {
 755                 if (!bch2_btree_node_relock(iter, iter->level))
 756                         return;
 757
 758                 bch2_btree_node_iter_advance(&node_iter, l->b);
 759                 k = bch2_btree_node_iter_peek(&node_iter, l->b);
 760                 if (!k)
 761                         break;
 762
 763                 bch2_bkey_unpack(l->b, &tmp.k, k);
 764                 bch2_btree_node_prefetch(iter->c, &tmp.k,
 765                                          iter->level - 1,
 766                                          iter->btree_id);
 767         }
 768
 769         if (!was_locked)
 770                 btree_node_unlock(iter, iter->level);
 771 }
 772
 773 static inline int btree_iter_down(struct btree_iter *iter)
 774 {
 775         struct btree_iter_level *l = &iter->l[iter->level];
 776         struct btree *b;
 777         unsigned level = iter->level - 1;
 778         enum six_lock_type lock_type = btree_lock_want(iter, level);
 779         BKEY_PADDED(k) tmp;
 780
 781         BUG_ON(!btree_node_locked(iter, iter->level));
 782
 783         bch2_bkey_unpack(l->b, &tmp.k,
 784                          bch2_btree_node_iter_peek(&l->iter, l->b));
 785
 786         b = bch2_btree_node_get(iter->c, iter, &tmp.k, level, lock_type);
 787         if (unlikely(IS_ERR(b)))
 788                 return PTR_ERR(b);
 789
 790         mark_btree_node_locked(iter, level, lock_type);
 791         btree_iter_node_set(iter, b);
 792
 793         if (iter->flags & BTREE_ITER_PREFETCH)
 794                 btree_iter_prefetch(iter);
 795
 796         iter->level = level;
 797
 798         return 0;
 799 }
 800
 801 static void btree_iter_up(struct btree_iter *iter)
 802 {
 803         btree_node_unlock(iter, iter->level++);
 804 }
 805
 806 int __must_check __bch2_btree_iter_traverse(struct btree_iter *);
 807
 808 static int btree_iter_traverse_error(struct btree_iter *iter, int ret)
 809 {
 810         struct bch_fs *c = iter->c;
 811         struct btree_iter *linked, *sorted_iters, **i;
 812 retry_all:
 813         bch2_btree_iter_unlock(iter);
 814
 815         if (ret != -ENOMEM && ret != -EINTR)
 816                 goto io_error;
 817
 818         if (ret == -ENOMEM) {
 819                 struct closure cl;
 820
 821                 closure_init_stack(&cl);
 822
 823                 do {
 824                         ret = bch2_btree_cache_cannibalize_lock(c, &cl);
 825                         closure_sync(&cl);
 826                 } while (ret);
 827         }
 828
 829         /*
 830          * Linked iters are normally a circular singly linked list - break cycle
 831          * while we sort them:
 832          */
 833         linked = iter->next;
 834         iter->next = NULL;
 835         sorted_iters = NULL;
 836
 837         while (linked) {
 838                 iter = linked;
 839                 linked = linked->next;
 840
 841                 i = &sorted_iters;
 842                 while (*i && btree_iter_cmp(iter, *i) > 0)
 843                         i = &(*i)->next;
 844
 845                 iter->next = *i;
 846                 *i = iter;
 847         }
 848
 849         /* Make list circular again: */
 850         iter = sorted_iters;
 851         while (iter->next)
 852                 iter = iter->next;
 853         iter->next = sorted_iters;
 854
 855         /* Now, redo traversals in correct order: */
 856
 857         iter = sorted_iters;
 858         do {
 859 retry:
 860                 ret = __bch2_btree_iter_traverse(iter);
 861                 if (unlikely(ret)) {
 862                         if (ret == -EINTR)
 863                                 goto retry;
 864                         goto retry_all;
 865                 }
 866
 867                 iter = iter->next;
 868         } while (iter != sorted_iters);
 869
 870         ret = btree_iter_linked(iter) ? -EINTR : 0;
 871 out:
 872         bch2_btree_cache_cannibalize_unlock(c);
 873         return ret;
 874 io_error:
 875         BUG_ON(ret != -EIO);
 876
 877         iter->flags |= BTREE_ITER_ERROR;
 878         iter->l[iter->level].b = NULL;
 879         goto out;
 880 }
 881
 882 /*
 883  * This is the main state machine for walking down the btree - walks down to a
 884  * specified depth
 885  *
 886  * Returns 0 on success, -EIO on error (error reading in a btree node).
 887  *
 888  * On error, caller (peek_node()/peek_key()) must return NULL; the error is
 889  * stashed in the iterator and returned from bch2_btree_iter_unlock().
 890  */
 891 int __must_check __bch2_btree_iter_traverse(struct btree_iter *iter)
 892 {
 893         unsigned depth_want = iter->level;
 894
 895         if (unlikely(!iter->l[iter->level].b))
 896                 return 0;
 897
 898         iter->flags &= ~BTREE_ITER_AT_END_OF_LEAF;
 899
 900         /* make sure we have all the intent locks we need - ugh */
 901         if (unlikely(iter->l[iter->level].b &&
 902                      iter->level + 1 < iter->locks_want)) {
 903                 unsigned i;
 904
 905                 for (i = iter->level + 1;
 906                      i < iter->locks_want && iter->l[i].b;
 907                      i++)
 908                         if (!bch2_btree_node_relock(iter, i)) {
 909                                 while (iter->level < BTREE_MAX_DEPTH &&
 910                                        iter->l[iter->level].b &&
 911                                        iter->level + 1 < iter->locks_want)
 912                                         btree_iter_up(iter);
 913                                 break;
 914                         }
 915         }
 916
 917         /*
 918          * If the current node isn't locked, go up until we have a locked node
 919          * or run out of nodes:
 920          */
 921         while (btree_iter_node(iter, iter->level) &&
 922                !(is_btree_node(iter, iter->level) &&
 923                  bch2_btree_node_relock(iter, iter->level) &&
 924
 925                  /*
 926                   * XXX: correctly using BTREE_ITER_UPTODATE should make
 927                   * comparing iter->pos against node's key unnecessary
 928                   */
 929                  btree_iter_pos_in_node(iter, iter->l[iter->level].b)))
 930                 btree_iter_up(iter);
 931
 932         /*
 933          * If we've got a btree node locked (i.e. we aren't about to relock the
 934          * root) - advance its node iterator if necessary:
 935          *
 936          * XXX correctly using BTREE_ITER_UPTODATE should make this unnecessary
 937          */
 938         if (btree_iter_node(iter, iter->level)) {
 939                 struct btree_iter_level *l = &iter->l[iter->level];
 940                 struct bkey_s_c k;
 941                 struct bkey u;
 942
 943                 while ((k = __btree_iter_peek_all(iter, l, &u)).k &&
 944                        !btree_iter_pos_cmp(iter, k.k))
 945                         __btree_iter_advance(l);
 946         }
 947
 948         /*
 949          * Note: iter->nodes[iter->level] may be temporarily NULL here - that
 950          * would indicate to other code that we got to the end of the btree,
 951          * here it indicates that relocking the root failed - it's critical that
 952          * btree_iter_lock_root() comes next and that it can't fail
 953          */
 954         while (iter->level > depth_want) {
 955                 int ret = btree_iter_node(iter, iter->level)
 956                         ? btree_iter_down(iter)
 957                         : btree_iter_lock_root(iter, depth_want);
 958                 if (unlikely(ret)) {
 959                         iter->level = depth_want;
 960                         iter->l[iter->level].b = BTREE_ITER_NOT_END;
 961                         return ret;
 962                 }
 963         }
 964
 965         iter->uptodate = BTREE_ITER_NEED_PEEK;
 966         return 0;
 967 }
 968
 969 int __must_check bch2_btree_iter_traverse(struct btree_iter *iter)
 970 {
 971         int ret;
 972
 973         if (iter->uptodate < BTREE_ITER_NEED_RELOCK)
 974                 return 0;
 975
 976         ret = __bch2_btree_iter_traverse(iter);
 977         if (unlikely(ret))
 978                 ret = btree_iter_traverse_error(iter, ret);
 979
 980         return ret;
 981 }
 982
 983 /* Iterate across nodes (leaf and interior nodes) */
 984
 985 struct btree *bch2_btree_iter_peek_node(struct btree_iter *iter)
 986 {
 987         struct btree *b;
 988         int ret;
 989
 990         EBUG_ON(iter->flags & BTREE_ITER_IS_EXTENTS);
 991
 992         ret = bch2_btree_iter_traverse(iter);
 993         if (ret)
 994                 return ERR_PTR(ret);
 995
 996         b = iter->l[iter->level].b;
 997
 998         if (b) {
 999                 EBUG_ON(bkey_cmp(b->key.k.p, iter->pos) < 0);
1000                 iter->pos = b->key.k.p;
1001         }
1002
1003         return b;
1004 }
1005
1006 struct btree *bch2_btree_iter_next_node(struct btree_iter *iter, unsigned depth)
1007 {
1008         struct btree *b;
1009         int ret;
1010
1011         EBUG_ON(iter->flags & BTREE_ITER_IS_EXTENTS);
1012
1013         btree_iter_up(iter);
1014
1015         if (!btree_iter_node(iter, iter->level))
1016                 return NULL;
1017
1018         /* parent node usually won't be locked: redo traversal if necessary */
1019         btree_iter_set_dirty(iter, BTREE_ITER_NEED_TRAVERSE);
1020         ret = bch2_btree_iter_traverse(iter);
1021         if (ret)
1022                 return NULL;
1023
1024         b = iter->l[iter->level].b;
1025         if (!b)
1026                 return b;
1027
1028         if (bkey_cmp(iter->pos, b->key.k.p) < 0) {
1029                 /* Haven't gotten to the end of the parent node: */
1030
1031                 /* ick: */
1032                 iter->pos       = iter->btree_id == BTREE_ID_INODES
1033                         ? btree_type_successor(iter->btree_id, iter->pos)
1034                         : bkey_successor(iter->pos);
1035                 iter->level     = depth;
1036
1037                 btree_iter_set_dirty(iter, BTREE_ITER_NEED_TRAVERSE);
1038                 ret = bch2_btree_iter_traverse(iter);
1039                 if (ret)
1040                         return NULL;
1041
1042                 b = iter->l[iter->level].b;
1043         }
1044
1045         iter->pos = b->key.k.p;
1046
1047         return b;
1048 }
1049
1050 /* Iterate across keys (in leaf nodes only) */
1051
1052 void bch2_btree_iter_set_pos_same_leaf(struct btree_iter *iter, struct bpos new_pos)
1053 {
1054         struct btree_iter_level *l = &iter->l[0];
1055         struct bkey_packed *k;
1056
1057         EBUG_ON(iter->level != 0);
1058         EBUG_ON(bkey_cmp(new_pos, iter->pos) < 0);
1059         EBUG_ON(!btree_node_locked(iter, 0));
1060         EBUG_ON(bkey_cmp(new_pos, l->b->key.k.p) > 0);
1061
1062         iter->pos = new_pos;
1063         btree_iter_set_dirty(iter, BTREE_ITER_NEED_PEEK);
1064
1065         while ((k = bch2_btree_node_iter_peek_all(&l->iter, l->b)) &&
1066                !btree_iter_pos_cmp_packed(l->b, &iter->pos, k,
1067                                           iter->flags & BTREE_ITER_IS_EXTENTS))
1068                 __btree_iter_advance(l);
1069
1070         if (!k && btree_iter_pos_after_node(iter, l->b)) {
1071                 btree_iter_set_dirty(iter, BTREE_ITER_NEED_TRAVERSE);
1072                 iter->flags |= BTREE_ITER_AT_END_OF_LEAF;
1073         }
1074 }
1075
1076 void bch2_btree_iter_set_pos(struct btree_iter *iter, struct bpos new_pos)
1077 {
1078         EBUG_ON(bkey_cmp(new_pos, iter->pos) < 0); /* XXX handle this */
1079         iter->pos = new_pos;
1080
1081         btree_iter_set_dirty(iter, BTREE_ITER_NEED_TRAVERSE);
1082 }
1083
1084 struct bkey_s_c bch2_btree_iter_peek(struct btree_iter *iter)
1085 {
1086         struct btree_iter_level *l = &iter->l[0];
1087         struct bkey_s_c k;
1088         int ret;
1089
1090         EBUG_ON(!!(iter->flags & BTREE_ITER_IS_EXTENTS) !=
1091                 (iter->btree_id == BTREE_ID_EXTENTS));
1092         EBUG_ON(iter->flags & BTREE_ITER_SLOTS);
1093
1094         if (iter->uptodate == BTREE_ITER_UPTODATE) {
1095                 struct bkey_packed *k =
1096                         __bch2_btree_node_iter_peek_all(&l->iter, l->b);
1097                 struct bkey_s_c ret = {
1098                         .k = &iter->k,
1099                         .v = bkeyp_val(&l->b->format, k)
1100                 };
1101
1102                 EBUG_ON(!btree_node_locked(iter, 0));
1103
1104                 if (debug_check_bkeys(iter->c))
1105                         bch2_bkey_debugcheck(iter->c, l->b, ret);
1106                 return ret;
1107         }
1108
1109         if (iter->uptodate == BTREE_ITER_END)
1110                 return bkey_s_c_null;
1111
1112         while (1) {
1113                 ret = bch2_btree_iter_traverse(iter);
1114                 if (unlikely(ret))
1115                         return bkey_s_c_err(ret);
1116
1117                 k = __btree_iter_peek(iter, l);
1118                 if (likely(k.k))
1119                         break;
1120
1121                 /* got to the end of the leaf, iterator needs to be traversed: */
1122                 iter->pos = l->b->key.k.p;
1123                 if (!bkey_cmp(iter->pos, POS_MAX)) {
1124                         iter->uptodate = BTREE_ITER_END;
1125                         return bkey_s_c_null;
1126                 }
1127
1128                 iter->pos = btree_type_successor(iter->btree_id, iter->pos);
1129                 iter->uptodate = BTREE_ITER_NEED_TRAVERSE;
1130         }
1131
1132         /*
1133          * iter->pos should always be equal to the key we just
1134          * returned - except extents can straddle iter->pos:
1135          */
1136         if (!(iter->flags & BTREE_ITER_IS_EXTENTS) ||
1137             bkey_cmp(bkey_start_pos(k.k), iter->pos) > 0)
1138                 iter->pos = bkey_start_pos(k.k);
1139
1140         iter->uptodate = BTREE_ITER_UPTODATE;
1141         return k;
1142 }
1143
1144 static noinline
1145 struct bkey_s_c bch2_btree_iter_peek_next_leaf(struct btree_iter *iter)
1146 {
1147         struct btree_iter_level *l = &iter->l[0];
1148
1149         iter->pos = l->b->key.k.p;
1150         if (!bkey_cmp(iter->pos, POS_MAX)) {
1151                 iter->uptodate = BTREE_ITER_END;
1152                 return bkey_s_c_null;
1153         }
1154
1155         iter->pos = btree_type_successor(iter->btree_id, iter->pos);
1156         iter->uptodate = BTREE_ITER_NEED_TRAVERSE;
1157
1158         return bch2_btree_iter_peek(iter);
1159 }
1160
1161 struct bkey_s_c bch2_btree_iter_next(struct btree_iter *iter)
1162 {
1163         struct btree_iter_level *l = &iter->l[0];
1164         struct bkey_packed *p;
1165         struct bkey_s_c k;
1166
1167         EBUG_ON(!!(iter->flags & BTREE_ITER_IS_EXTENTS) !=
1168                 (iter->btree_id == BTREE_ID_EXTENTS));
1169         EBUG_ON(iter->flags & BTREE_ITER_SLOTS);
1170
1171         if (unlikely(iter->uptodate != BTREE_ITER_UPTODATE)) {
1172                 k = bch2_btree_iter_peek(iter);
1173                 if (IS_ERR_OR_NULL(k.k))
1174                         return k;
1175         }
1176
1177         do {
1178                 __btree_iter_advance(l);
1179                 p = bch2_btree_node_iter_peek_all(&l->iter, l->b);
1180                 if (unlikely(!p))
1181                         return bch2_btree_iter_peek_next_leaf(iter);
1182         } while (bkey_deleted(p));
1183
1184         k = __btree_iter_unpack(iter, l, &iter->k, p);
1185
1186         EBUG_ON(bkey_cmp(bkey_start_pos(k.k), iter->pos) < 0);
1187         iter->pos = bkey_start_pos(k.k);
1188         return k;
1189 }
1190
1191 static inline struct bkey_s_c
1192 __bch2_btree_iter_peek_slot(struct btree_iter *iter)
1193 {
1194         struct btree_iter_level *l = &iter->l[0];
1195         struct bkey_s_c k;
1196         struct bkey n;
1197         int ret;
1198
1199 recheck:
1200         while ((k = __btree_iter_peek_all(iter, l, &iter->k)).k &&
1201                bkey_deleted(k.k) &&
1202                bkey_cmp(bkey_start_pos(k.k), iter->pos) == 0)
1203                 __btree_iter_advance(l);
1204
1205         if (k.k && bkey_cmp(bkey_start_pos(k.k), iter->pos) <= 0) {
1206                 EBUG_ON(bkey_cmp(k.k->p, iter->pos) < 0);
1207                 EBUG_ON(bkey_deleted(k.k));
1208                 iter->uptodate = BTREE_ITER_UPTODATE;
1209                 return k;
1210         }
1211
1212         /*
1213          * If we got to the end of the node, check if we need to traverse to the
1214          * next node:
1215          */
1216         if (unlikely(!k.k && btree_iter_pos_after_node(iter, l->b))) {
1217                 btree_iter_set_dirty(iter, BTREE_ITER_NEED_TRAVERSE);
1218                 ret = bch2_btree_iter_traverse(iter);
1219                 if (unlikely(ret))
1220                         return bkey_s_c_err(ret);
1221
1222                 goto recheck;
1223         }
1224
1225         /* hole */
1226         bkey_init(&n);
1227         n.p = iter->pos;
1228
1229         if (iter->flags & BTREE_ITER_IS_EXTENTS) {
1230                 if (n.p.offset == KEY_OFFSET_MAX) {
1231                         if (n.p.inode == KEY_INODE_MAX) {
1232                                 iter->uptodate = BTREE_ITER_END;
1233                                 return bkey_s_c_null;
1234                         }
1235
1236                         iter->pos = bkey_successor(iter->pos);
1237                         goto recheck;
1238                 }
1239
1240                 if (!k.k)
1241                         k.k = &l->b->key.k;
1242
1243                 bch2_key_resize(&n,
1244                                 min_t(u64, KEY_SIZE_MAX,
1245                                       (k.k->p.inode == n.p.inode
1246                                        ? bkey_start_offset(k.k)
1247                                        : KEY_OFFSET_MAX) -
1248                                       n.p.offset));
1249
1250                 EBUG_ON(!n.size);
1251         }
1252
1253         iter->k = n;
1254         iter->uptodate = BTREE_ITER_UPTODATE;
1255         return (struct bkey_s_c) { &iter->k, NULL };
1256 }
1257
1258 struct bkey_s_c bch2_btree_iter_peek_slot(struct btree_iter *iter)
1259 {
1260         struct btree_iter_level *l = &iter->l[0];
1261         int ret;
1262
1263         EBUG_ON(!!(iter->flags & BTREE_ITER_IS_EXTENTS) !=
1264                 (iter->btree_id == BTREE_ID_EXTENTS));
1265         EBUG_ON(!(iter->flags & BTREE_ITER_SLOTS));
1266
1267         if (iter->uptodate == BTREE_ITER_UPTODATE) {
1268                 struct bkey_s_c ret = { .k = &iter->k };;
1269
1270                 if (!bkey_deleted(&iter->k))
1271                         ret.v = bkeyp_val(&l->b->format,
1272                                 __bch2_btree_node_iter_peek_all(&l->iter, l->b));
1273
1274                 EBUG_ON(!btree_node_locked(iter, 0));
1275
1276                 if (debug_check_bkeys(iter->c))
1277                         bch2_bkey_debugcheck(iter->c, l->b, ret);
1278                 return ret;
1279         }
1280
1281         if (iter->uptodate == BTREE_ITER_END)
1282                 return bkey_s_c_null;
1283
1284         ret = bch2_btree_iter_traverse(iter);
1285         if (unlikely(ret))
1286                 return bkey_s_c_err(ret);
1287
1288         return __bch2_btree_iter_peek_slot(iter);
1289 }
1290
1291 struct bkey_s_c bch2_btree_iter_next_slot(struct btree_iter *iter)
1292 {
1293         iter->pos = btree_type_successor(iter->btree_id, iter->k.p);
1294
1295         if (unlikely(iter->uptodate != BTREE_ITER_UPTODATE)) {
1296                 /*
1297                  * XXX: when we just need to relock we should be able to avoid
1298                  * calling traverse, but we need to kill BTREE_ITER_NEED_PEEK
1299                  * for that to work
1300                  */
1301                 btree_iter_set_dirty(iter, BTREE_ITER_NEED_TRAVERSE);
1302
1303                 return bch2_btree_iter_peek_slot(iter);
1304         }
1305
1306         if (!bkey_deleted(&iter->k))
1307                 __btree_iter_advance(&iter->l[0]);
1308
1309         return __bch2_btree_iter_peek_slot(iter);
1310 }
1311
1312 void __bch2_btree_iter_init(struct btree_iter *iter, struct bch_fs *c,
1313                             enum btree_id btree_id, struct bpos pos,
1314                             unsigned locks_want, unsigned depth,
1315                             unsigned flags)
1316 {
1317         unsigned i;
1318
1319         EBUG_ON(depth >= BTREE_MAX_DEPTH);
1320         EBUG_ON(locks_want > BTREE_MAX_DEPTH);
1321
1322         iter->c                         = c;
1323         iter->pos                       = pos;
1324         bkey_init(&iter->k);
1325         iter->k.p                       = pos;
1326         iter->flags                     = flags;
1327         iter->uptodate                  = BTREE_ITER_NEED_TRAVERSE;
1328         iter->btree_id                  = btree_id;
1329         iter->level                     = depth;
1330         iter->locks_want                = locks_want;
1331         iter->nodes_locked              = 0;
1332         iter->nodes_intent_locked       = 0;
1333         for (i = 0; i < ARRAY_SIZE(iter->l); i++)
1334                 iter->l[i].b            = NULL;
1335         iter->l[iter->level].b          = BTREE_ITER_NOT_END;
1336         iter->next                      = iter;
1337
1338         if (unlikely((flags & BTREE_ITER_IS_EXTENTS) &&
1339                      !bkey_cmp(pos, POS_MAX)))
1340                 iter->uptodate = BTREE_ITER_END;
1341
1342         prefetch(c->btree_roots[btree_id].b);
1343 }
1344
1345 void bch2_btree_iter_unlink(struct btree_iter *iter)
1346 {
1347         struct btree_iter *linked;
1348
1349         __bch2_btree_iter_unlock(iter);
1350
1351         if (!btree_iter_linked(iter))
1352                 return;
1353
1354         for_each_linked_btree_iter(iter, linked) {
1355
1356                 if (linked->next == iter) {
1357                         linked->next = iter->next;
1358                         return;
1359                 }
1360         }
1361
1362         BUG();
1363 }
1364
1365 void bch2_btree_iter_link(struct btree_iter *iter, struct btree_iter *new)
1366 {
1367         BUG_ON(btree_iter_linked(new));
1368
1369         new->next = iter->next;
1370         iter->next = new;
1371
1372         if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG)) {
1373                 unsigned nr_iters = 1;
1374
1375                 for_each_linked_btree_iter(iter, new)
1376                         nr_iters++;
1377
1378                 BUG_ON(nr_iters > SIX_LOCK_MAX_RECURSE);
1379         }
1380 }
1381
1382 void bch2_btree_iter_copy(struct btree_iter *dst, struct btree_iter *src)
1383 {
1384         __bch2_btree_iter_unlock(dst);
1385         memcpy(dst, src, offsetof(struct btree_iter, next));
1386         dst->nodes_locked = dst->nodes_intent_locked = 0;
1387         dst->uptodate = BTREE_ITER_NEED_RELOCK;
1388 }