fs/bcachefs/btree_iter.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 #ifndef _BCACHEFS_BTREE_ITER_H
   3 #define _BCACHEFS_BTREE_ITER_H
   4
   5 #include "bset.h"
   6 #include "btree_types.h"
   7 #include "trace.h"
   8
   9 void bch2_trans_updates_to_text(struct printbuf *, struct btree_trans *);
  10 void bch2_btree_path_to_text(struct printbuf *, struct btree_trans *, btree_path_idx_t);
  11 void bch2_trans_paths_to_text(struct printbuf *, struct btree_trans *);
  12 void bch2_dump_trans_updates(struct btree_trans *);
  13 void bch2_dump_trans_paths_updates(struct btree_trans *);
  14
  15 static inline int __bkey_err(const struct bkey *k)
  16 {
  17         return PTR_ERR_OR_ZERO(k);
  18 }
  19
  20 #define bkey_err(_k)    __bkey_err((_k).k)
  21
  22 static inline void __btree_path_get(struct btree_trans *trans, struct btree_path *path, bool intent)
  23 {
  24         unsigned idx = path - trans->paths;
  25
  26         EBUG_ON(idx >= trans->nr_paths);
  27         EBUG_ON(!test_bit(idx, trans->paths_allocated));
  28         if (unlikely(path->ref == U8_MAX)) {
  29                 bch2_dump_trans_paths_updates(trans);
  30                 panic("path %u refcount overflow\n", idx);
  31         }
  32
  33         path->ref++;
  34         path->intent_ref += intent;
  35         trace_btree_path_get_ll(trans, path);
  36 }
  37
  38 static inline bool __btree_path_put(struct btree_trans *trans, struct btree_path *path, bool intent)
  39 {
  40         EBUG_ON(path - trans->paths >= trans->nr_paths);
  41         EBUG_ON(!test_bit(path - trans->paths, trans->paths_allocated));
  42         EBUG_ON(!path->ref);
  43         EBUG_ON(!path->intent_ref && intent);
  44
  45         trace_btree_path_put_ll(trans, path);
  46         path->intent_ref -= intent;
  47         return --path->ref == 0;
  48 }
  49
  50 static inline void btree_path_set_dirty(struct btree_path *path,
  51                                         enum btree_path_uptodate u)
  52 {
  53         path->uptodate = max_t(unsigned, path->uptodate, u);
  54 }
  55
  56 static inline struct btree *btree_path_node(struct btree_path *path,
  57                                             unsigned level)
  58 {
  59         return level < BTREE_MAX_DEPTH ? path->l[level].b : NULL;
  60 }
  61
  62 static inline bool btree_node_lock_seq_matches(const struct btree_path *path,
  63                                         const struct btree *b, unsigned level)
  64 {
  65         return path->l[level].lock_seq == six_lock_seq(&b->c.lock);
  66 }
  67
  68 static inline struct btree *btree_node_parent(struct btree_path *path,
  69                                               struct btree *b)
  70 {
  71         return btree_path_node(path, b->c.level + 1);
  72 }
  73
  74 /* Iterate over paths within a transaction: */
  75
  76 void __bch2_btree_trans_sort_paths(struct btree_trans *);
  77
  78 static inline void btree_trans_sort_paths(struct btree_trans *trans)
  79 {
  80         if (!IS_ENABLED(CONFIG_BCACHEFS_DEBUG) &&
  81             trans->paths_sorted)
  82                 return;
  83         __bch2_btree_trans_sort_paths(trans);
  84 }
  85
  86 static inline unsigned long *trans_paths_nr(struct btree_path *paths)
  87 {
  88         return &container_of(paths, struct btree_trans_paths, paths[0])->nr_paths;
  89 }
  90
  91 static inline unsigned long *trans_paths_allocated(struct btree_path *paths)
  92 {
  93         unsigned long *v = trans_paths_nr(paths);
  94         return v - BITS_TO_LONGS(*v);
  95 }
  96
  97 #define trans_for_each_path_idx_from(_paths_allocated, _nr, _idx, _start)\
  98         for (_idx = _start;                                             \
  99              (_idx = find_next_bit(_paths_allocated, _nr, _idx)) < _nr; \
 100              _idx++)
 101
 102 static inline struct btree_path *
 103 __trans_next_path(struct btree_trans *trans, unsigned *idx)
 104 {
 105         unsigned long *w = trans->paths_allocated + *idx / BITS_PER_LONG;
 106         /*
 107          * Open coded find_next_bit(), because
 108          *  - this is fast path, we can't afford the function call
 109          *  - and we know that nr_paths is a multiple of BITS_PER_LONG,
 110          */
 111         while (*idx < trans->nr_paths) {
 112                 unsigned long v = *w >> (*idx & (BITS_PER_LONG - 1));
 113                 if (v) {
 114                         *idx += __ffs(v);
 115                         return trans->paths + *idx;
 116                 }
 117
 118                 *idx += BITS_PER_LONG;
 119                 *idx &= ~(BITS_PER_LONG - 1);
 120                 w++;
 121         }
 122
 123         return NULL;
 124 }
 125
 126 /*
 127  * This version is intended to be safe for use on a btree_trans that is owned by
 128  * another thread, for bch2_btree_trans_to_text();
 129  */
 130 #define trans_for_each_path_from(_trans, _path, _idx, _start)           \
 131         for (_idx = _start;                                             \
 132              (_path = __trans_next_path((_trans), &_idx));              \
 133              _idx++)
 134
 135 #define trans_for_each_path(_trans, _path, _idx)                        \
 136         trans_for_each_path_from(_trans, _path, _idx, 1)
 137
 138 static inline struct btree_path *next_btree_path(struct btree_trans *trans, struct btree_path *path)
 139 {
 140         unsigned idx = path ? path->sorted_idx + 1 : 0;
 141
 142         EBUG_ON(idx > trans->nr_sorted);
 143
 144         return idx < trans->nr_sorted
 145                 ? trans->paths + trans->sorted[idx]
 146                 : NULL;
 147 }
 148
 149 static inline struct btree_path *prev_btree_path(struct btree_trans *trans, struct btree_path *path)
 150 {
 151         unsigned idx = path ? path->sorted_idx : trans->nr_sorted;
 152
 153         return idx
 154                 ? trans->paths + trans->sorted[idx - 1]
 155                 : NULL;
 156 }
 157
 158 #define trans_for_each_path_idx_inorder(_trans, _iter)                  \
 159         for (_iter = (struct trans_for_each_path_inorder_iter) { 0 };   \
 160              (_iter.path_idx = trans->sorted[_iter.sorted_idx],         \
 161               _iter.sorted_idx < (_trans)->nr_sorted);                  \
 162              _iter.sorted_idx++)
 163
 164 struct trans_for_each_path_inorder_iter {
 165         btree_path_idx_t        sorted_idx;
 166         btree_path_idx_t        path_idx;
 167 };
 168
 169 #define trans_for_each_path_inorder(_trans, _path, _iter)               \
 170         for (_iter = (struct trans_for_each_path_inorder_iter) { 0 };   \
 171              (_iter.path_idx = trans->sorted[_iter.sorted_idx],         \
 172               _path = (_trans)->paths + _iter.path_idx,                 \
 173               _iter.sorted_idx < (_trans)->nr_sorted);                  \
 174              _iter.sorted_idx++)
 175
 176 #define trans_for_each_path_inorder_reverse(_trans, _path, _i)          \
 177         for (_i = trans->nr_sorted - 1;                                 \
 178              ((_path) = (_trans)->paths + trans->sorted[_i]), (_i) >= 0;\
 179              --_i)
 180
 181 static inline bool __path_has_node(const struct btree_path *path,
 182                                    const struct btree *b)
 183 {
 184         return path->l[b->c.level].b == b &&
 185                 btree_node_lock_seq_matches(path, b, b->c.level);
 186 }
 187
 188 static inline struct btree_path *
 189 __trans_next_path_with_node(struct btree_trans *trans, struct btree *b,
 190                             unsigned *idx)
 191 {
 192         struct btree_path *path;
 193
 194         while ((path = __trans_next_path(trans, idx)) &&
 195                 !__path_has_node(path, b))
 196                (*idx)++;
 197
 198         return path;
 199 }
 200
 201 #define trans_for_each_path_with_node(_trans, _b, _path, _iter)         \
 202         for (_iter = 1;                                                 \
 203              (_path = __trans_next_path_with_node((_trans), (_b), &_iter));\
 204              _iter++)
 205
 206 btree_path_idx_t __bch2_btree_path_make_mut(struct btree_trans *, btree_path_idx_t,
 207                                             bool, unsigned long);
 208
 209 static inline btree_path_idx_t __must_check
 210 bch2_btree_path_make_mut(struct btree_trans *trans,
 211                          btree_path_idx_t path, bool intent,
 212                          unsigned long ip)
 213 {
 214         if (trans->paths[path].ref > 1 ||
 215             trans->paths[path].preserve)
 216                 path = __bch2_btree_path_make_mut(trans, path, intent, ip);
 217         trans->paths[path].should_be_locked = false;
 218         return path;
 219 }
 220
 221 btree_path_idx_t __must_check
 222 __bch2_btree_path_set_pos(struct btree_trans *, btree_path_idx_t,
 223                           struct bpos, bool, unsigned long);
 224
 225 static inline btree_path_idx_t __must_check
 226 bch2_btree_path_set_pos(struct btree_trans *trans,
 227                         btree_path_idx_t path, struct bpos new_pos,
 228                         bool intent, unsigned long ip)
 229 {
 230         return !bpos_eq(new_pos, trans->paths[path].pos)
 231                 ? __bch2_btree_path_set_pos(trans, path, new_pos, intent, ip)
 232                 : path;
 233 }
 234
 235 int __must_check bch2_btree_path_traverse_one(struct btree_trans *,
 236                                               btree_path_idx_t,
 237                                               unsigned, unsigned long);
 238
 239 static inline void bch2_trans_verify_not_unlocked_or_in_restart(struct btree_trans *);
 240
 241 static inline int __must_check bch2_btree_path_traverse(struct btree_trans *trans,
 242                                           btree_path_idx_t path, unsigned flags)
 243 {
 244         bch2_trans_verify_not_unlocked_or_in_restart(trans);
 245
 246         if (trans->paths[path].uptodate < BTREE_ITER_NEED_RELOCK)
 247                 return 0;
 248
 249         return bch2_btree_path_traverse_one(trans, path, flags, _RET_IP_);
 250 }
 251
 252 btree_path_idx_t bch2_path_get(struct btree_trans *, enum btree_id, struct bpos,
 253                                  unsigned, unsigned, unsigned, unsigned long);
 254 btree_path_idx_t bch2_path_get_unlocked_mut(struct btree_trans *, enum btree_id,
 255                                             unsigned, struct bpos);
 256
 257 struct bkey_s_c bch2_btree_path_peek_slot(struct btree_path *, struct bkey *);
 258
 259 /*
 260  * bch2_btree_path_peek_slot() for a cached iterator might return a key in a
 261  * different snapshot:
 262  */
 263 static inline struct bkey_s_c bch2_btree_path_peek_slot_exact(struct btree_path *path, struct bkey *u)
 264 {
 265         struct bkey_s_c k = bch2_btree_path_peek_slot(path, u);
 266
 267         if (k.k && bpos_eq(path->pos, k.k->p))
 268                 return k;
 269
 270         bkey_init(u);
 271         u->p = path->pos;
 272         return (struct bkey_s_c) { u, NULL };
 273 }
 274
 275 struct bkey_i *bch2_btree_journal_peek_slot(struct btree_trans *,
 276                                         struct btree_iter *, struct bpos);
 277
 278 void bch2_btree_path_level_init(struct btree_trans *, struct btree_path *, struct btree *);
 279
 280 int __bch2_trans_mutex_lock(struct btree_trans *, struct mutex *);
 281
 282 static inline int bch2_trans_mutex_lock(struct btree_trans *trans, struct mutex *lock)
 283 {
 284         return mutex_trylock(lock)
 285                 ? 0
 286                 : __bch2_trans_mutex_lock(trans, lock);
 287 }
 288
 289 #ifdef CONFIG_BCACHEFS_DEBUG
 290 void bch2_trans_verify_paths(struct btree_trans *);
 291 void bch2_assert_pos_locked(struct btree_trans *, enum btree_id, struct bpos);
 292 #else
 293 static inline void bch2_trans_verify_paths(struct btree_trans *trans) {}
 294 static inline void bch2_assert_pos_locked(struct btree_trans *trans, enum btree_id id,
 295                                           struct bpos pos) {}
 296 #endif
 297
 298 void bch2_btree_path_fix_key_modified(struct btree_trans *trans,
 299                                       struct btree *, struct bkey_packed *);
 300 void bch2_btree_node_iter_fix(struct btree_trans *trans, struct btree_path *,
 301                               struct btree *, struct btree_node_iter *,
 302                               struct bkey_packed *, unsigned, unsigned);
 303
 304 int bch2_btree_path_relock_intent(struct btree_trans *, struct btree_path *);
 305
 306 void bch2_path_put(struct btree_trans *, btree_path_idx_t, bool);
 307
 308 int bch2_trans_relock(struct btree_trans *);
 309 int bch2_trans_relock_notrace(struct btree_trans *);
 310 void bch2_trans_unlock(struct btree_trans *);
 311 void bch2_trans_unlock_long(struct btree_trans *);
 312
 313 static inline int trans_was_restarted(struct btree_trans *trans, u32 restart_count)
 314 {
 315         return restart_count != trans->restart_count
 316                 ? -BCH_ERR_transaction_restart_nested
 317                 : 0;
 318 }
 319
 320 void __noreturn bch2_trans_restart_error(struct btree_trans *, u32);
 321
 322 static inline void bch2_trans_verify_not_restarted(struct btree_trans *trans,
 323                                                    u32 restart_count)
 324 {
 325         if (trans_was_restarted(trans, restart_count))
 326                 bch2_trans_restart_error(trans, restart_count);
 327 }
 328
 329 void __noreturn bch2_trans_unlocked_or_in_restart_error(struct btree_trans *);
 330
 331 static inline void bch2_trans_verify_not_unlocked_or_in_restart(struct btree_trans *trans)
 332 {
 333         if (trans->restarted || !trans->locked)
 334                 bch2_trans_unlocked_or_in_restart_error(trans);
 335 }
 336
 337 __always_inline
 338 static int btree_trans_restart_ip(struct btree_trans *trans, int err, unsigned long ip)
 339 {
 340         BUG_ON(err <= 0);
 341         BUG_ON(!bch2_err_matches(-err, BCH_ERR_transaction_restart));
 342
 343         trans->restarted = err;
 344         trans->last_restarted_ip = ip;
 345 #ifdef CONFIG_BCACHEFS_DEBUG
 346         darray_exit(&trans->last_restarted_trace);
 347         bch2_save_backtrace(&trans->last_restarted_trace, current, 0, GFP_NOWAIT);
 348 #endif
 349         return -err;
 350 }
 351
 352 __always_inline
 353 static int btree_trans_restart(struct btree_trans *trans, int err)
 354 {
 355         return btree_trans_restart_ip(trans, err, _THIS_IP_);
 356 }
 357
 358 static inline int trans_maybe_inject_restart(struct btree_trans *trans, unsigned long ip)
 359 {
 360 #ifdef CONFIG_BCACHEFS_INJECT_TRANSACTION_RESTARTS
 361         if (!(ktime_get_ns() & ~(~0ULL << min(63, (10 + trans->restart_count_this_trans))))) {
 362                 trace_and_count(trans->c, trans_restart_injected, trans, ip);
 363                 return btree_trans_restart_ip(trans,
 364                                         BCH_ERR_transaction_restart_fault_inject, ip);
 365         }
 366 #endif
 367         return 0;
 368 }
 369
 370 bool bch2_btree_node_upgrade(struct btree_trans *,
 371                              struct btree_path *, unsigned);
 372
 373 void __bch2_btree_path_downgrade(struct btree_trans *, struct btree_path *, unsigned);
 374
 375 static inline void bch2_btree_path_downgrade(struct btree_trans *trans,
 376                                              struct btree_path *path)
 377 {
 378         unsigned new_locks_want = path->level + !!path->intent_ref;
 379
 380         if (path->locks_want > new_locks_want)
 381                 __bch2_btree_path_downgrade(trans, path, new_locks_want);
 382 }
 383
 384 void bch2_trans_downgrade(struct btree_trans *);
 385
 386 void bch2_trans_node_add(struct btree_trans *trans, struct btree_path *, struct btree *);
 387 void bch2_trans_node_drop(struct btree_trans *trans, struct btree *);
 388 void bch2_trans_node_reinit_iter(struct btree_trans *, struct btree *);
 389
 390 int __must_check __bch2_btree_iter_traverse(struct btree_iter *iter);
 391 int __must_check bch2_btree_iter_traverse(struct btree_iter *);
 392
 393 struct btree *bch2_btree_iter_peek_node(struct btree_iter *);
 394 struct btree *bch2_btree_iter_peek_node_and_restart(struct btree_iter *);
 395 struct btree *bch2_btree_iter_next_node(struct btree_iter *);
 396
 397 struct bkey_s_c bch2_btree_iter_peek_max(struct btree_iter *, struct bpos);
 398 struct bkey_s_c bch2_btree_iter_next(struct btree_iter *);
 399
 400 static inline struct bkey_s_c bch2_btree_iter_peek(struct btree_iter *iter)
 401 {
 402         return bch2_btree_iter_peek_max(iter, SPOS_MAX);
 403 }
 404
 405 struct bkey_s_c bch2_btree_iter_peek_prev_min(struct btree_iter *, struct bpos);
 406
 407 static inline struct bkey_s_c bch2_btree_iter_peek_prev(struct btree_iter *iter)
 408 {
 409         return bch2_btree_iter_peek_prev_min(iter, POS_MIN);
 410 }
 411
 412 struct bkey_s_c bch2_btree_iter_prev(struct btree_iter *);
 413
 414 struct bkey_s_c bch2_btree_iter_peek_slot(struct btree_iter *);
 415 struct bkey_s_c bch2_btree_iter_next_slot(struct btree_iter *);
 416 struct bkey_s_c bch2_btree_iter_prev_slot(struct btree_iter *);
 417
 418 bool bch2_btree_iter_advance(struct btree_iter *);
 419 bool bch2_btree_iter_rewind(struct btree_iter *);
 420
 421 static inline void __bch2_btree_iter_set_pos(struct btree_iter *iter, struct bpos new_pos)
 422 {
 423         iter->k.type = KEY_TYPE_deleted;
 424         iter->k.p.inode         = iter->pos.inode       = new_pos.inode;
 425         iter->k.p.offset        = iter->pos.offset      = new_pos.offset;
 426         iter->k.p.snapshot      = iter->pos.snapshot    = new_pos.snapshot;
 427         iter->k.size = 0;
 428 }
 429
 430 static inline void bch2_btree_iter_set_pos(struct btree_iter *iter, struct bpos new_pos)
 431 {
 432         struct btree_trans *trans = iter->trans;
 433
 434         if (unlikely(iter->update_path))
 435                 bch2_path_put(trans, iter->update_path,
 436                               iter->flags & BTREE_ITER_intent);
 437         iter->update_path = 0;
 438
 439         if (!(iter->flags & BTREE_ITER_all_snapshots))
 440                 new_pos.snapshot = iter->snapshot;
 441
 442         __bch2_btree_iter_set_pos(iter, new_pos);
 443 }
 444
 445 static inline void bch2_btree_iter_set_pos_to_extent_start(struct btree_iter *iter)
 446 {
 447         BUG_ON(!(iter->flags & BTREE_ITER_is_extents));
 448         iter->pos = bkey_start_pos(&iter->k);
 449 }
 450
 451 static inline void bch2_btree_iter_set_snapshot(struct btree_iter *iter, u32 snapshot)
 452 {
 453         struct bpos pos = iter->pos;
 454
 455         iter->snapshot = snapshot;
 456         pos.snapshot = snapshot;
 457         bch2_btree_iter_set_pos(iter, pos);
 458 }
 459
 460 void bch2_trans_iter_exit(struct btree_trans *, struct btree_iter *);
 461
 462 static inline unsigned bch2_btree_iter_flags(struct btree_trans *trans,
 463                                              unsigned btree_id,
 464                                              unsigned level,
 465                                              unsigned flags)
 466 {
 467         if (level || !btree_id_cached(trans->c, btree_id)) {
 468                 flags &= ~BTREE_ITER_cached;
 469                 flags &= ~BTREE_ITER_with_key_cache;
 470         } else if (!(flags & BTREE_ITER_cached))
 471                 flags |= BTREE_ITER_with_key_cache;
 472
 473         if (!(flags & (BTREE_ITER_all_snapshots|BTREE_ITER_not_extents)) &&
 474             btree_id_is_extents(btree_id))
 475                 flags |= BTREE_ITER_is_extents;
 476
 477         if (!(flags & BTREE_ITER_snapshot_field) &&
 478             !btree_type_has_snapshot_field(btree_id))
 479                 flags &= ~BTREE_ITER_all_snapshots;
 480
 481         if (!(flags & BTREE_ITER_all_snapshots) &&
 482             btree_type_has_snapshots(btree_id))
 483                 flags |= BTREE_ITER_filter_snapshots;
 484
 485         if (trans->journal_replay_not_finished)
 486                 flags |= BTREE_ITER_with_journal;
 487
 488         return flags;
 489 }
 490
 491 static inline void bch2_trans_iter_init_common(struct btree_trans *trans,
 492                                           struct btree_iter *iter,
 493                                           unsigned btree_id, struct bpos pos,
 494                                           unsigned locks_want,
 495                                           unsigned depth,
 496                                           unsigned flags,
 497                                           unsigned long ip)
 498 {
 499         iter->trans             = trans;
 500         iter->update_path       = 0;
 501         iter->key_cache_path    = 0;
 502         iter->btree_id          = btree_id;
 503         iter->min_depth         = 0;
 504         iter->flags             = flags;
 505         iter->snapshot          = pos.snapshot;
 506         iter->pos               = pos;
 507         iter->k                 = POS_KEY(pos);
 508         iter->journal_idx       = 0;
 509 #ifdef CONFIG_BCACHEFS_DEBUG
 510         iter->ip_allocated = ip;
 511 #endif
 512         iter->path = bch2_path_get(trans, btree_id, iter->pos,
 513                                    locks_want, depth, flags, ip);
 514 }
 515
 516 void bch2_trans_iter_init_outlined(struct btree_trans *, struct btree_iter *,
 517                           enum btree_id, struct bpos, unsigned);
 518
 519 static inline void bch2_trans_iter_init(struct btree_trans *trans,
 520                           struct btree_iter *iter,
 521                           unsigned btree_id, struct bpos pos,
 522                           unsigned flags)
 523 {
 524         if (__builtin_constant_p(btree_id) &&
 525             __builtin_constant_p(flags))
 526                 bch2_trans_iter_init_common(trans, iter, btree_id, pos, 0, 0,
 527                                 bch2_btree_iter_flags(trans, btree_id, 0, flags),
 528                                 _THIS_IP_);
 529         else
 530                 bch2_trans_iter_init_outlined(trans, iter, btree_id, pos, flags);
 531 }
 532
 533 void bch2_trans_node_iter_init(struct btree_trans *, struct btree_iter *,
 534                                enum btree_id, struct bpos,
 535                                unsigned, unsigned, unsigned);
 536 void bch2_trans_copy_iter(struct btree_iter *, struct btree_iter *);
 537
 538 void bch2_set_btree_iter_dontneed(struct btree_iter *);
 539
 540 void *__bch2_trans_kmalloc(struct btree_trans *, size_t);
 541
 542 /**
 543  * bch2_trans_kmalloc - allocate memory for use by the current transaction
 544  *
 545  * Must be called after bch2_trans_begin, which on second and further calls
 546  * frees all memory allocated in this transaction
 547  */
 548 static inline void *bch2_trans_kmalloc(struct btree_trans *trans, size_t size)
 549 {
 550         size = roundup(size, 8);
 551
 552         if (likely(trans->mem_top + size <= trans->mem_bytes)) {
 553                 void *p = trans->mem + trans->mem_top;
 554
 555                 trans->mem_top += size;
 556                 memset(p, 0, size);
 557                 return p;
 558         } else {
 559                 return __bch2_trans_kmalloc(trans, size);
 560         }
 561 }
 562
 563 static inline void *bch2_trans_kmalloc_nomemzero(struct btree_trans *trans, size_t size)
 564 {
 565         size = round_up(size, 8);
 566
 567         if (likely(trans->mem_top + size <= trans->mem_bytes)) {
 568                 void *p = trans->mem + trans->mem_top;
 569
 570                 trans->mem_top += size;
 571                 return p;
 572         } else {
 573                 return __bch2_trans_kmalloc(trans, size);
 574         }
 575 }
 576
 577 static inline struct bkey_s_c __bch2_bkey_get_iter(struct btree_trans *trans,
 578                                 struct btree_iter *iter,
 579                                 unsigned btree_id, struct bpos pos,
 580                                 unsigned flags, unsigned type)
 581 {
 582         struct bkey_s_c k;
 583
 584         bch2_trans_iter_init(trans, iter, btree_id, pos, flags);
 585         k = bch2_btree_iter_peek_slot(iter);
 586
 587         if (!bkey_err(k) && type && k.k->type != type)
 588                 k = bkey_s_c_err(-BCH_ERR_ENOENT_bkey_type_mismatch);
 589         if (unlikely(bkey_err(k)))
 590                 bch2_trans_iter_exit(trans, iter);
 591         return k;
 592 }
 593
 594 static inline struct bkey_s_c bch2_bkey_get_iter(struct btree_trans *trans,
 595                                 struct btree_iter *iter,
 596                                 unsigned btree_id, struct bpos pos,
 597                                 unsigned flags)
 598 {
 599         return __bch2_bkey_get_iter(trans, iter, btree_id, pos, flags, 0);
 600 }
 601
 602 #define bch2_bkey_get_iter_typed(_trans, _iter, _btree_id, _pos, _flags, _type)\
 603         bkey_s_c_to_##_type(__bch2_bkey_get_iter(_trans, _iter,                 \
 604                                        _btree_id, _pos, _flags, KEY_TYPE_##_type))
 605
 606 static inline void __bkey_val_copy(void *dst_v, unsigned dst_size, struct bkey_s_c src_k)
 607 {
 608         unsigned b = min_t(unsigned, dst_size, bkey_val_bytes(src_k.k));
 609         memcpy(dst_v, src_k.v, b);
 610         if (unlikely(b < dst_size))
 611                 memset(dst_v + b, 0, dst_size - b);
 612 }
 613
 614 #define bkey_val_copy(_dst_v, _src_k)                                   \
 615 do {                                                                    \
 616         BUILD_BUG_ON(!__typecheck(*_dst_v, *_src_k.v));                 \
 617         __bkey_val_copy(_dst_v, sizeof(*_dst_v), _src_k.s_c);           \
 618 } while (0)
 619
 620 static inline int __bch2_bkey_get_val_typed(struct btree_trans *trans,
 621                                 unsigned btree_id, struct bpos pos,
 622                                 unsigned flags, unsigned type,
 623                                 unsigned val_size, void *val)
 624 {
 625         struct btree_iter iter;
 626         struct bkey_s_c k = __bch2_bkey_get_iter(trans, &iter, btree_id, pos, flags, type);
 627         int ret = bkey_err(k);
 628         if (!ret) {
 629                 __bkey_val_copy(val, val_size, k);
 630                 bch2_trans_iter_exit(trans, &iter);
 631         }
 632
 633         return ret;
 634 }
 635
 636 #define bch2_bkey_get_val_typed(_trans, _btree_id, _pos, _flags, _type, _val)\
 637         __bch2_bkey_get_val_typed(_trans, _btree_id, _pos, _flags,      \
 638                                   KEY_TYPE_##_type, sizeof(*_val), _val)
 639
 640 void bch2_trans_srcu_unlock(struct btree_trans *);
 641
 642 u32 bch2_trans_begin(struct btree_trans *);
 643
 644 #define __for_each_btree_node(_trans, _iter, _btree_id, _start,                 \
 645                               _locks_want, _depth, _flags, _b, _do)             \
 646 ({                                                                              \
 647         bch2_trans_begin((_trans));                                             \
 648                                                                                 \
 649         struct btree_iter _iter;                                                \
 650         bch2_trans_node_iter_init((_trans), &_iter, (_btree_id),                \
 651                                   _start, _locks_want, _depth, _flags);         \
 652         int _ret3 = 0;                                                          \
 653         do {                                                                    \
 654                 _ret3 = lockrestart_do((_trans), ({                             \
 655                         struct btree *_b = bch2_btree_iter_peek_node(&_iter);   \
 656                         if (!_b)                                                \
 657                                 break;                                          \
 658                                                                                 \
 659                         PTR_ERR_OR_ZERO(_b) ?: (_do);                           \
 660                 })) ?:                                                          \
 661                 lockrestart_do((_trans),                                        \
 662                         PTR_ERR_OR_ZERO(bch2_btree_iter_next_node(&_iter)));    \
 663         } while (!_ret3);                                                       \
 664                                                                                 \
 665         bch2_trans_iter_exit((_trans), &(_iter));                               \
 666         _ret3;                                                                  \
 667 })
 668
 669 #define for_each_btree_node(_trans, _iter, _btree_id, _start,           \
 670                             _flags, _b, _do)                            \
 671         __for_each_btree_node(_trans, _iter, _btree_id, _start, \
 672                               0, 0, _flags, _b, _do)
 673
 674 static inline struct bkey_s_c bch2_btree_iter_peek_prev_type(struct btree_iter *iter,
 675                                                              unsigned flags)
 676 {
 677         return  flags & BTREE_ITER_slots      ? bch2_btree_iter_peek_slot(iter) :
 678                                                 bch2_btree_iter_peek_prev(iter);
 679 }
 680
 681 static inline struct bkey_s_c bch2_btree_iter_peek_type(struct btree_iter *iter,
 682                                                         unsigned flags)
 683 {
 684         return  flags & BTREE_ITER_slots      ? bch2_btree_iter_peek_slot(iter) :
 685                                                 bch2_btree_iter_peek(iter);
 686 }
 687
 688 static inline struct bkey_s_c bch2_btree_iter_peek_max_type(struct btree_iter *iter,
 689                                                              struct bpos end,
 690                                                              unsigned flags)
 691 {
 692         if (!(flags & BTREE_ITER_slots))
 693                 return bch2_btree_iter_peek_max(iter, end);
 694
 695         if (bkey_gt(iter->pos, end))
 696                 return bkey_s_c_null;
 697
 698         return bch2_btree_iter_peek_slot(iter);
 699 }
 700
 701 int __bch2_btree_trans_too_many_iters(struct btree_trans *);
 702
 703 static inline int btree_trans_too_many_iters(struct btree_trans *trans)
 704 {
 705         if (bitmap_weight(trans->paths_allocated, trans->nr_paths) > BTREE_ITER_NORMAL_LIMIT - 8)
 706                 return __bch2_btree_trans_too_many_iters(trans);
 707
 708         return 0;
 709 }
 710
 711 /*
 712  * goto instead of loop, so that when used inside for_each_btree_key2()
 713  * break/continue work correctly
 714  */
 715 #define lockrestart_do(_trans, _do)                                     \
 716 ({                                                                      \
 717         __label__ transaction_restart;                                  \
 718         u32 _restart_count;                                             \
 719         int _ret2;                                                      \
 720 transaction_restart:                                                    \
 721         _restart_count = bch2_trans_begin(_trans);                      \
 722         _ret2 = (_do);                                                  \
 723                                                                         \
 724         if (bch2_err_matches(_ret2, BCH_ERR_transaction_restart))       \
 725                 goto transaction_restart;                               \
 726                                                                         \
 727         if (!_ret2)                                                     \
 728                 bch2_trans_verify_not_restarted(_trans, _restart_count);\
 729         _ret2;                                                          \
 730 })
 731
 732 /*
 733  * nested_lockrestart_do(), nested_commit_do():
 734  *
 735  * These are like lockrestart_do() and commit_do(), with two differences:
 736  *
 737  *  - We don't call bch2_trans_begin() unless we had a transaction restart
 738  *  - We return -BCH_ERR_transaction_restart_nested if we succeeded after a
 739  *  transaction restart
 740  */
 741 #define nested_lockrestart_do(_trans, _do)                              \
 742 ({                                                                      \
 743         u32 _restart_count, _orig_restart_count;                        \
 744         int _ret2;                                                      \
 745                                                                         \
 746         _restart_count = _orig_restart_count = (_trans)->restart_count; \
 747                                                                         \
 748         while (bch2_err_matches(_ret2 = (_do), BCH_ERR_transaction_restart))\
 749                 _restart_count = bch2_trans_begin(_trans);              \
 750                                                                         \
 751         if (!_ret2)                                                     \
 752                 bch2_trans_verify_not_restarted(_trans, _restart_count);\
 753                                                                         \
 754         _ret2 ?: trans_was_restarted(_trans, _orig_restart_count);              \
 755 })
 756
 757 #define for_each_btree_key_max_continue(_trans, _iter,                  \
 758                                          _end, _flags, _k, _do)         \
 759 ({                                                                      \
 760         struct bkey_s_c _k;                                             \
 761         int _ret3 = 0;                                                  \
 762                                                                         \
 763         do {                                                            \
 764                 _ret3 = lockrestart_do(_trans, ({                       \
 765                         (_k) = bch2_btree_iter_peek_max_type(&(_iter),  \
 766                                                 _end, (_flags));        \
 767                         if (!(_k).k)                                    \
 768                                 break;                                  \
 769                                                                         \
 770                         bkey_err(_k) ?: (_do);                          \
 771                 }));                                                    \
 772         } while (!_ret3 && bch2_btree_iter_advance(&(_iter)));          \
 773                                                                         \
 774         bch2_trans_iter_exit((_trans), &(_iter));                       \
 775         _ret3;                                                          \
 776 })
 777
 778 #define for_each_btree_key_continue(_trans, _iter, _flags, _k, _do)     \
 779         for_each_btree_key_max_continue(_trans, _iter, SPOS_MAX, _flags, _k, _do)
 780
 781 #define for_each_btree_key_max(_trans, _iter, _btree_id,                \
 782                                 _start, _end, _flags, _k, _do)          \
 783 ({                                                                      \
 784         bch2_trans_begin(trans);                                        \
 785                                                                         \
 786         struct btree_iter _iter;                                        \
 787         bch2_trans_iter_init((_trans), &(_iter), (_btree_id),           \
 788                              (_start), (_flags));                       \
 789                                                                         \
 790         for_each_btree_key_max_continue(_trans, _iter, _end, _flags, _k, _do);\
 791 })
 792
 793 #define for_each_btree_key(_trans, _iter, _btree_id,                    \
 794                            _start, _flags, _k, _do)                     \
 795         for_each_btree_key_max(_trans, _iter, _btree_id, _start,        \
 796                                  SPOS_MAX, _flags, _k, _do)
 797
 798 #define for_each_btree_key_reverse(_trans, _iter, _btree_id,            \
 799                                    _start, _flags, _k, _do)             \
 800 ({                                                                      \
 801         struct btree_iter _iter;                                        \
 802         struct bkey_s_c _k;                                             \
 803         int _ret3 = 0;                                                  \
 804                                                                         \
 805         bch2_trans_iter_init((_trans), &(_iter), (_btree_id),           \
 806                              (_start), (_flags));                       \
 807                                                                         \
 808         do {                                                            \
 809                 _ret3 = lockrestart_do(_trans, ({                       \
 810                         (_k) = bch2_btree_iter_peek_prev_type(&(_iter), \
 811                                                         (_flags));      \
 812                         if (!(_k).k)                                    \
 813                                 break;                                  \
 814                                                                         \
 815                         bkey_err(_k) ?: (_do);                          \
 816                 }));                                                    \
 817         } while (!_ret3 && bch2_btree_iter_rewind(&(_iter)));           \
 818                                                                         \
 819         bch2_trans_iter_exit((_trans), &(_iter));                       \
 820         _ret3;                                                          \
 821 })
 822
 823 #define for_each_btree_key_commit(_trans, _iter, _btree_id,             \
 824                                   _start, _iter_flags, _k,              \
 825                                   _disk_res, _journal_seq, _commit_flags,\
 826                                   _do)                                  \
 827         for_each_btree_key(_trans, _iter, _btree_id, _start, _iter_flags, _k,\
 828                             (_do) ?: bch2_trans_commit(_trans, (_disk_res),\
 829                                         (_journal_seq), (_commit_flags)))
 830
 831 #define for_each_btree_key_reverse_commit(_trans, _iter, _btree_id,     \
 832                                   _start, _iter_flags, _k,              \
 833                                   _disk_res, _journal_seq, _commit_flags,\
 834                                   _do)                                  \
 835         for_each_btree_key_reverse(_trans, _iter, _btree_id, _start, _iter_flags, _k,\
 836                             (_do) ?: bch2_trans_commit(_trans, (_disk_res),\
 837                                         (_journal_seq), (_commit_flags)))
 838
 839 #define for_each_btree_key_max_commit(_trans, _iter, _btree_id, \
 840                                   _start, _end, _iter_flags, _k,        \
 841                                   _disk_res, _journal_seq, _commit_flags,\
 842                                   _do)                                  \
 843         for_each_btree_key_max(_trans, _iter, _btree_id, _start, _end, _iter_flags, _k,\
 844                             (_do) ?: bch2_trans_commit(_trans, (_disk_res),\
 845                                         (_journal_seq), (_commit_flags)))
 846
 847 struct bkey_s_c bch2_btree_iter_peek_and_restart_outlined(struct btree_iter *);
 848
 849 #define for_each_btree_key_max_norestart(_trans, _iter, _btree_id,      \
 850                            _start, _end, _flags, _k, _ret)              \
 851         for (bch2_trans_iter_init((_trans), &(_iter), (_btree_id),      \
 852                                   (_start), (_flags));                  \
 853              (_k) = bch2_btree_iter_peek_max_type(&(_iter), _end, _flags),\
 854              !((_ret) = bkey_err(_k)) && (_k).k;                        \
 855              bch2_btree_iter_advance(&(_iter)))
 856
 857 #define for_each_btree_key_max_continue_norestart(_iter, _end, _flags, _k, _ret)\
 858         for (;                                                                  \
 859              (_k) = bch2_btree_iter_peek_max_type(&(_iter), _end, _flags),      \
 860              !((_ret) = bkey_err(_k)) && (_k).k;                                \
 861              bch2_btree_iter_advance(&(_iter)))
 862
 863 #define for_each_btree_key_norestart(_trans, _iter, _btree_id,          \
 864                            _start, _flags, _k, _ret)                    \
 865         for_each_btree_key_max_norestart(_trans, _iter, _btree_id, _start,\
 866                                           SPOS_MAX, _flags, _k, _ret)
 867
 868 #define for_each_btree_key_reverse_norestart(_trans, _iter, _btree_id,  \
 869                                              _start, _flags, _k, _ret)  \
 870         for (bch2_trans_iter_init((_trans), &(_iter), (_btree_id),      \
 871                                   (_start), (_flags));                  \
 872              (_k) = bch2_btree_iter_peek_prev_type(&(_iter), _flags),   \
 873              !((_ret) = bkey_err(_k)) && (_k).k;                        \
 874              bch2_btree_iter_rewind(&(_iter)))
 875
 876 #define for_each_btree_key_continue_norestart(_iter, _flags, _k, _ret)  \
 877         for_each_btree_key_max_continue_norestart(_iter, SPOS_MAX, _flags, _k, _ret)
 878
 879 /*
 880  * This should not be used in a fastpath, without first trying _do in
 881  * nonblocking mode - it will cause excessive transaction restarts and
 882  * potentially livelocking:
 883  */
 884 #define drop_locks_do(_trans, _do)                                      \
 885 ({                                                                      \
 886         bch2_trans_unlock(_trans);                                      \
 887         (_do) ?: bch2_trans_relock(_trans);                             \
 888 })
 889
 890 #define allocate_dropping_locks_errcode(_trans, _do)                    \
 891 ({                                                                      \
 892         gfp_t _gfp = GFP_NOWAIT|__GFP_NOWARN;                           \
 893         int _ret = _do;                                                 \
 894                                                                         \
 895         if (bch2_err_matches(_ret, ENOMEM)) {                           \
 896                 _gfp = GFP_KERNEL;                                      \
 897                 _ret = drop_locks_do(_trans, _do);                      \
 898         }                                                               \
 899         _ret;                                                           \
 900 })
 901
 902 #define allocate_dropping_locks(_trans, _ret, _do)                      \
 903 ({                                                                      \
 904         gfp_t _gfp = GFP_NOWAIT|__GFP_NOWARN;                           \
 905         typeof(_do) _p = _do;                                           \
 906                                                                         \
 907         _ret = 0;                                                       \
 908         if (unlikely(!_p)) {                                            \
 909                 _gfp = GFP_KERNEL;                                      \
 910                 _ret = drop_locks_do(_trans, ((_p = _do), 0));          \
 911         }                                                               \
 912         _p;                                                             \
 913 })
 914
 915 #define bch2_trans_run(_c, _do)                                         \
 916 ({                                                                      \
 917         struct btree_trans *trans = bch2_trans_get(_c);                 \
 918         int _ret = (_do);                                               \
 919         bch2_trans_put(trans);                                          \
 920         _ret;                                                           \
 921 })
 922
 923 #define bch2_trans_do(_c, _do)  bch2_trans_run(_c, lockrestart_do(trans, _do))
 924
 925 struct btree_trans *__bch2_trans_get(struct bch_fs *, unsigned);
 926 void bch2_trans_put(struct btree_trans *);
 927
 928 bool bch2_current_has_btree_trans(struct bch_fs *);
 929
 930 extern const char *bch2_btree_transaction_fns[BCH_TRANSACTIONS_NR];
 931 unsigned bch2_trans_get_fn_idx(const char *);
 932
 933 #define bch2_trans_get(_c)                                              \
 934 ({                                                                      \
 935         static unsigned trans_fn_idx;                                   \
 936                                                                         \
 937         if (unlikely(!trans_fn_idx))                                    \
 938                 trans_fn_idx = bch2_trans_get_fn_idx(__func__);         \
 939         __bch2_trans_get(_c, trans_fn_idx);                             \
 940 })
 941
 942 void bch2_btree_trans_to_text(struct printbuf *, struct btree_trans *);
 943
 944 void bch2_fs_btree_iter_exit(struct bch_fs *);
 945 void bch2_fs_btree_iter_init_early(struct bch_fs *);
 946 int bch2_fs_btree_iter_init(struct bch_fs *);
 947
 948 #endif /* _BCACHEFS_BTREE_ITER_H */