btree_iter.c 87.7 KB
Newer Older
1 2 3 4
// SPDX-License-Identifier: GPL-2.0

#include "bcachefs.h"
#include "bkey_methods.h"
5
#include "bkey_buf.h"
6 7
#include "btree_cache.h"
#include "btree_iter.h"
8
#include "btree_journal_iter.h"
9
#include "btree_key_cache.h"
10
#include "btree_locking.h"
11
#include "btree_update.h"
12
#include "debug.h"
13
#include "error.h"
14
#include "extents.h"
15
#include "journal.h"
16
#include "journal_io.h"
17
#include "replicas.h"
18
#include "snapshot.h"
19 20
#include "trace.h"

21
#include <linux/random.h>
22 23
#include <linux/prefetch.h>

Kent Overstreet's avatar
Kent Overstreet committed
24
static inline void btree_path_list_remove(struct btree_trans *, struct btree_path *);
25 26
static inline void btree_path_list_add(struct btree_trans *,
			btree_path_idx_t, btree_path_idx_t);
Kent Overstreet's avatar
Kent Overstreet committed
27

28 29
static inline unsigned long btree_iter_ip_allocated(struct btree_iter *iter)
{
30
#ifdef TRACK_PATH_ALLOCATED
31 32 33 34 35 36
	return iter->ip_allocated;
#else
	return 0;
#endif
}

37
static btree_path_idx_t btree_path_alloc(struct btree_trans *, btree_path_idx_t);
38
static void bch2_trans_srcu_lock(struct btree_trans *);
Kent Overstreet's avatar
Kent Overstreet committed
39 40 41 42 43 44

static inline int __btree_path_cmp(const struct btree_path *l,
				   enum btree_id	r_btree_id,
				   bool			r_cached,
				   struct bpos		r_pos,
				   unsigned		r_level)
45
{
46 47 48
	/*
	 * Must match lock ordering as defined by __bch2_btree_node_lock:
	 */
Kent Overstreet's avatar
Kent Overstreet committed
49
	return   cmp_int(l->btree_id,	r_btree_id) ?:
50
		 cmp_int((int) l->cached,	(int) r_cached) ?:
Kent Overstreet's avatar
Kent Overstreet committed
51 52 53 54 55 56 57 58
		 bpos_cmp(l->pos,	r_pos) ?:
		-cmp_int(l->level,	r_level);
}

static inline int btree_path_cmp(const struct btree_path *l,
				 const struct btree_path *r)
{
	return __btree_path_cmp(l, r->btree_id, r->cached, r->pos, r->level);
59 60
}

61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
static inline struct bpos bkey_successor(struct btree_iter *iter, struct bpos p)
{
	/* Are we iterating over keys in all snapshots? */
	if (iter->flags & BTREE_ITER_ALL_SNAPSHOTS) {
		p = bpos_successor(p);
	} else {
		p = bpos_nosnap_successor(p);
		p.snapshot = iter->snapshot;
	}

	return p;
}

static inline struct bpos bkey_predecessor(struct btree_iter *iter, struct bpos p)
{
	/* Are we iterating over keys in all snapshots? */
	if (iter->flags & BTREE_ITER_ALL_SNAPSHOTS) {
		p = bpos_predecessor(p);
	} else {
		p = bpos_nosnap_predecessor(p);
		p.snapshot = iter->snapshot;
	}

	return p;
}

87
static inline struct bpos btree_iter_search_key(struct btree_iter *iter)
88
{
89
	struct bpos pos = iter->pos;
90

91
	if ((iter->flags & BTREE_ITER_IS_EXTENTS) &&
92
	    !bkey_eq(pos, POS_MAX))
93
		pos = bkey_successor(iter, pos);
94
	return pos;
95 96
}

Kent Overstreet's avatar
Kent Overstreet committed
97
static inline bool btree_path_pos_before_node(struct btree_path *path,
98 99
					      struct btree *b)
{
100
	return bpos_lt(path->pos, b->data->min_key);
101 102
}

Kent Overstreet's avatar
Kent Overstreet committed
103
static inline bool btree_path_pos_after_node(struct btree_path *path,
104 105
					     struct btree *b)
{
106
	return bpos_gt(path->pos, b->key.k.p);
107 108
}

Kent Overstreet's avatar
Kent Overstreet committed
109
static inline bool btree_path_pos_in_node(struct btree_path *path,
110 111
					  struct btree *b)
{
Kent Overstreet's avatar
Kent Overstreet committed
112 113 114
	return path->btree_id == b->c.btree_id &&
		!btree_path_pos_before_node(path, b) &&
		!btree_path_pos_after_node(path, b);
115 116
}

117 118 119 120
/* Btree iterator: */

#ifdef CONFIG_BCACHEFS_DEBUG

Kent Overstreet's avatar
Kent Overstreet committed
121 122
static void bch2_btree_path_verify_cached(struct btree_trans *trans,
					  struct btree_path *path)
123 124
{
	struct bkey_cached *ck;
Kent Overstreet's avatar
Kent Overstreet committed
125
	bool locked = btree_node_locked(path, 0);
126

Kent Overstreet's avatar
Kent Overstreet committed
127
	if (!bch2_btree_node_relock(trans, path, 0))
128 129
		return;

Kent Overstreet's avatar
Kent Overstreet committed
130 131
	ck = (void *) path->l[0].b;
	BUG_ON(ck->key.btree_id != path->btree_id ||
132
	       !bkey_eq(ck->key.pos, path->pos));
133 134

	if (!locked)
135
		btree_node_unlock(trans, path, 0);
136 137
}

Kent Overstreet's avatar
Kent Overstreet committed
138 139
static void bch2_btree_path_verify_level(struct btree_trans *trans,
				struct btree_path *path, unsigned level)
140
{
Kent Overstreet's avatar
Kent Overstreet committed
141
	struct btree_path_level *l;
142 143
	struct btree_node_iter tmp;
	bool locked;
144
	struct bkey_packed *p, *k;
145 146 147
	struct printbuf buf1 = PRINTBUF;
	struct printbuf buf2 = PRINTBUF;
	struct printbuf buf3 = PRINTBUF;
148
	const char *msg;
149

150
	if (!bch2_debug_check_iterators)
151 152
		return;

Kent Overstreet's avatar
Kent Overstreet committed
153
	l	= &path->l[level];
154
	tmp	= l->iter;
Kent Overstreet's avatar
Kent Overstreet committed
155
	locked	= btree_node_locked(path, level);
156

Kent Overstreet's avatar
Kent Overstreet committed
157
	if (path->cached) {
158
		if (!level)
Kent Overstreet's avatar
Kent Overstreet committed
159
			bch2_btree_path_verify_cached(trans, path);
160 161 162
		return;
	}

Kent Overstreet's avatar
Kent Overstreet committed
163
	if (!btree_path_node(path, level))
164 165
		return;

166
	if (!bch2_btree_node_relock_notrace(trans, path, level))
167 168
		return;

Kent Overstreet's avatar
Kent Overstreet committed
169
	BUG_ON(!btree_path_pos_in_node(path, l->b));
170 171

	bch2_btree_node_iter_verify(&l->iter, l->b);
172 173

	/*
174
	 * For interior nodes, the iterator will have skipped past deleted keys:
175
	 */
176
	p = level
177
		? bch2_btree_node_iter_prev(&tmp, l->b)
178 179
		: bch2_btree_node_iter_prev_all(&tmp, l->b);
	k = bch2_btree_node_iter_peek_all(&l->iter, l->b);
180

Kent Overstreet's avatar
Kent Overstreet committed
181
	if (p && bkey_iter_pos_cmp(l->b, p, &path->pos) >= 0) {
182 183
		msg = "before";
		goto err;
184 185
	}

Kent Overstreet's avatar
Kent Overstreet committed
186
	if (k && bkey_iter_pos_cmp(l->b, k, &path->pos) < 0) {
187 188 189
		msg = "after";
		goto err;
	}
190

191
	if (!locked)
192
		btree_node_unlock(trans, path, level);
193 194
	return;
err:
195
	bch2_bpos_to_text(&buf1, path->pos);
196 197 198

	if (p) {
		struct bkey uk = bkey_unpack_key(l->b, p);
199

200 201
		bch2_bkey_to_text(&buf2, &uk);
	} else {
202
		prt_printf(&buf2, "(none)");
203
	}
204

205 206
	if (k) {
		struct bkey uk = bkey_unpack_key(l->b, k);
207

208 209
		bch2_bkey_to_text(&buf3, &uk);
	} else {
210
		prt_printf(&buf3, "(none)");
211
	}
212

Kent Overstreet's avatar
Kent Overstreet committed
213 214
	panic("path should be %s key at level %u:\n"
	      "path pos %s\n"
215 216
	      "prev key %s\n"
	      "cur  key %s\n",
217
	      msg, level, buf1.buf, buf2.buf, buf3.buf);
218 219
}

Kent Overstreet's avatar
Kent Overstreet committed
220 221
static void bch2_btree_path_verify(struct btree_trans *trans,
				   struct btree_path *path)
222
{
223
	struct bch_fs *c = trans->c;
224
	unsigned i;
225

Kent Overstreet's avatar
Kent Overstreet committed
226 227 228 229
	EBUG_ON(path->btree_id >= BTREE_ID_NR);

	for (i = 0; i < (!path->cached ? BTREE_MAX_DEPTH : 1); i++) {
		if (!path->l[i].b) {
230
			BUG_ON(!path->cached &&
231
			       bch2_btree_id_root(c, path->btree_id)->b->c.level > i);
Kent Overstreet's avatar
Kent Overstreet committed
232 233 234 235 236 237 238 239 240 241 242 243
			break;
		}

		bch2_btree_path_verify_level(trans, path, i);
	}

	bch2_btree_path_verify_locks(path);
}

void bch2_trans_verify_paths(struct btree_trans *trans)
{
	struct btree_path *path;
244
	unsigned iter;
Kent Overstreet's avatar
Kent Overstreet committed
245

246
	trans_for_each_path(trans, path, iter)
Kent Overstreet's avatar
Kent Overstreet committed
247 248 249 250 251 252 253 254 255
		bch2_btree_path_verify(trans, path);
}

static void bch2_btree_iter_verify(struct btree_iter *iter)
{
	struct btree_trans *trans = iter->trans;

	BUG_ON(iter->btree_id >= BTREE_ID_NR);

256
	BUG_ON(!!(iter->flags & BTREE_ITER_CACHED) != btree_iter_path(trans, iter)->cached);
257

258 259 260
	BUG_ON((iter->flags & BTREE_ITER_IS_EXTENTS) &&
	       (iter->flags & BTREE_ITER_ALL_SNAPSHOTS));

261
	BUG_ON(!(iter->flags & BTREE_ITER_SNAPSHOT_FIELD) &&
262
	       (iter->flags & BTREE_ITER_ALL_SNAPSHOTS) &&
263
	       !btree_type_has_snapshot_field(iter->btree_id));
264

265
	if (iter->update_path)
266 267
		bch2_btree_path_verify(trans, &trans->paths[iter->update_path]);
	bch2_btree_path_verify(trans, btree_iter_path(trans, iter));
268 269
}

270 271
static void bch2_btree_iter_verify_entry_exit(struct btree_iter *iter)
{
272 273 274
	BUG_ON((iter->flags & BTREE_ITER_FILTER_SNAPSHOTS) &&
	       !iter->pos.snapshot);

275 276 277
	BUG_ON(!(iter->flags & BTREE_ITER_ALL_SNAPSHOTS) &&
	       iter->pos.snapshot != iter->snapshot);

278 279
	BUG_ON(bkey_lt(iter->pos, bkey_start_pos(&iter->k)) ||
	       bkey_gt(iter->pos, iter->k.p));
280 281
}

282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302
static int bch2_btree_iter_verify_ret(struct btree_iter *iter, struct bkey_s_c k)
{
	struct btree_trans *trans = iter->trans;
	struct btree_iter copy;
	struct bkey_s_c prev;
	int ret = 0;

	if (!bch2_debug_check_iterators)
		return 0;

	if (!(iter->flags & BTREE_ITER_FILTER_SNAPSHOTS))
		return 0;

	if (bkey_err(k) || !k.k)
		return 0;

	BUG_ON(!bch2_snapshot_is_ancestor(trans->c,
					  iter->snapshot,
					  k.k->p.snapshot));

	bch2_trans_iter_init(trans, &copy, iter->btree_id, iter->pos,
303
			     BTREE_ITER_NOPRESERVE|
304 305 306 307 308 309 310 311 312
			     BTREE_ITER_ALL_SNAPSHOTS);
	prev = bch2_btree_iter_prev(&copy);
	if (!prev.k)
		goto out;

	ret = bkey_err(prev);
	if (ret)
		goto out;

313
	if (bkey_eq(prev.k->p, k.k->p) &&
314 315
	    bch2_snapshot_is_ancestor(trans->c, iter->snapshot,
				      prev.k->p.snapshot) > 0) {
316
		struct printbuf buf1 = PRINTBUF, buf2 = PRINTBUF;
317

318 319
		bch2_bkey_to_text(&buf1, k.k);
		bch2_bkey_to_text(&buf2, prev.k);
320 321 322 323 324

		panic("iter snap %u\n"
		      "k    %s\n"
		      "prev %s\n",
		      iter->snapshot,
325
		      buf1.buf, buf2.buf);
326 327 328 329 330 331
	}
out:
	bch2_trans_iter_exit(trans, &copy);
	return ret;
}

332 333 334 335
void bch2_assert_pos_locked(struct btree_trans *trans, enum btree_id id,
			    struct bpos pos, bool key_cache)
{
	struct btree_path *path;
336
	struct trans_for_each_path_inorder_iter iter;
337
	struct printbuf buf = PRINTBUF;
338

339 340
	btree_trans_sort_paths(trans);

341
	trans_for_each_path_inorder(trans, path, iter) {
342 343 344 345 346 347 348 349
		int cmp = cmp_int(path->btree_id, id) ?:
			cmp_int(path->cached, key_cache);

		if (cmp > 0)
			break;
		if (cmp < 0)
			continue;

350
		if (!btree_node_locked(path, 0) ||
351 352 353 354
		    !path->should_be_locked)
			continue;

		if (!key_cache) {
355 356
			if (bkey_ge(pos, path->l[0].b->data->min_key) &&
			    bkey_le(pos, path->l[0].b->key.k.p))
357 358
				return;
		} else {
359
			if (bkey_eq(pos, path->pos))
360 361 362 363 364
				return;
		}
	}

	bch2_dump_trans_paths_updates(trans);
365 366
	bch2_bpos_to_text(&buf, pos);

367
	panic("not locked: %s %s%s\n",
368
	      bch2_btree_id_str(id), buf.buf,
369 370 371
	      key_cache ? " cached" : "");
}

372 373
#else

Kent Overstreet's avatar
Kent Overstreet committed
374 375 376 377
static inline void bch2_btree_path_verify_level(struct btree_trans *trans,
						struct btree_path *path, unsigned l) {}
static inline void bch2_btree_path_verify(struct btree_trans *trans,
					  struct btree_path *path) {}
378
static inline void bch2_btree_iter_verify(struct btree_iter *iter) {}
379
static inline void bch2_btree_iter_verify_entry_exit(struct btree_iter *iter) {}
380
static inline int bch2_btree_iter_verify_ret(struct btree_iter *iter, struct bkey_s_c k) { return 0; }
381

382 383
#endif

Kent Overstreet's avatar
Kent Overstreet committed
384 385
/* Btree path: fixups after btree updates */

386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402
static void btree_node_iter_set_set_pos(struct btree_node_iter *iter,
					struct btree *b,
					struct bset_tree *t,
					struct bkey_packed *k)
{
	struct btree_node_iter_set *set;

	btree_node_iter_for_each(iter, set)
		if (set->end == t->end_offset) {
			set->k = __btree_node_key_to_offset(b, k);
			bch2_btree_node_iter_sort(iter, b);
			return;
		}

	bch2_btree_node_iter_push(iter, b, k, btree_bkey_last(b, t));
}

Kent Overstreet's avatar
Kent Overstreet committed
403
static void __bch2_btree_path_fix_key_modified(struct btree_path *path,
404 405
					       struct btree *b,
					       struct bkey_packed *where)
406
{
Kent Overstreet's avatar
Kent Overstreet committed
407
	struct btree_path_level *l = &path->l[b->c.level];
408

409 410 411
	if (where != bch2_btree_node_iter_peek_all(&l->iter, l->b))
		return;

Kent Overstreet's avatar
Kent Overstreet committed
412
	if (bkey_iter_pos_cmp(l->b, where, &path->pos) < 0)
413
		bch2_btree_node_iter_advance(&l->iter, l->b);
414 415
}

Kent Overstreet's avatar
Kent Overstreet committed
416
void bch2_btree_path_fix_key_modified(struct btree_trans *trans,
417 418 419
				      struct btree *b,
				      struct bkey_packed *where)
{
Kent Overstreet's avatar
Kent Overstreet committed
420
	struct btree_path *path;
421
	unsigned i;
422

423
	trans_for_each_path_with_node(trans, b, path, i) {
Kent Overstreet's avatar
Kent Overstreet committed
424 425
		__bch2_btree_path_fix_key_modified(path, b, where);
		bch2_btree_path_verify_level(trans, path, b->c.level);
426 427 428
	}
}

Kent Overstreet's avatar
Kent Overstreet committed
429 430 431 432 433 434 435
static void __bch2_btree_node_iter_fix(struct btree_path *path,
				       struct btree *b,
				       struct btree_node_iter *node_iter,
				       struct bset_tree *t,
				       struct bkey_packed *where,
				       unsigned clobber_u64s,
				       unsigned new_u64s)
436 437 438 439 440
{
	const struct bkey_packed *end = btree_bkey_last(b, t);
	struct btree_node_iter_set *set;
	unsigned offset = __btree_node_key_to_offset(b, where);
	int shift = new_u64s - clobber_u64s;
441
	unsigned old_end = t->end_offset - shift;
442 443 444 445
	unsigned orig_iter_pos = node_iter->data[0].k;
	bool iter_current_key_modified =
		orig_iter_pos >= offset &&
		orig_iter_pos <= offset + clobber_u64s;
446 447 448 449 450 451 452

	btree_node_iter_for_each(node_iter, set)
		if (set->end == old_end)
			goto found;

	/* didn't find the bset in the iterator - might have to readd it: */
	if (new_u64s &&
Kent Overstreet's avatar
Kent Overstreet committed
453
	    bkey_iter_pos_cmp(b, where, &path->pos) >= 0) {
454
		bch2_btree_node_iter_push(node_iter, b, where, end);
455 456 457
		goto fixup_done;
	} else {
		/* Iterator is after key that changed */
458
		return;
459 460
	}
found:
461
	set->end = t->end_offset;
462 463 464

	/* Iterator hasn't gotten to the key that changed yet: */
	if (set->k < offset)
465
		return;
466 467

	if (new_u64s &&
Kent Overstreet's avatar
Kent Overstreet committed
468
	    bkey_iter_pos_cmp(b, where, &path->pos) >= 0) {
469 470 471 472 473 474
		set->k = offset;
	} else if (set->k < offset + clobber_u64s) {
		set->k = offset + new_u64s;
		if (set->k == set->end)
			bch2_btree_node_iter_set_drop(node_iter, set);
	} else {
475
		/* Iterator is after key that changed */
476
		set->k = (int) set->k + shift;
477
		return;
478 479 480
	}

	bch2_btree_node_iter_sort(node_iter, b);
481 482 483
fixup_done:
	if (node_iter->data[0].k != orig_iter_pos)
		iter_current_key_modified = true;
484

485
	/*
486 487 488
	 * When a new key is added, and the node iterator now points to that
	 * key, the iterator might have skipped past deleted keys that should
	 * come after the key the iterator now points to. We have to rewind to
489 490
	 * before those deleted keys - otherwise
	 * bch2_btree_node_iter_prev_all() breaks:
491
	 */
492
	if (!bch2_btree_node_iter_end(node_iter) &&
493
	    iter_current_key_modified &&
494
	    b->c.level) {
495 496 497
		struct bkey_packed *k, *k2, *p;

		k = bch2_btree_node_iter_peek_all(node_iter, b);
498 499

		for_each_bset(b, t) {
500 501 502
			bool set_pos = false;

			if (node_iter->data[0].end == t->end_offset)
503 504
				continue;

505 506 507 508 509 510
			k2 = bch2_btree_node_iter_bset_pos(node_iter, b, t);

			while ((p = bch2_bkey_prev_all(b, t, k2)) &&
			       bkey_iter_cmp(b, k, p) < 0) {
				k2 = p;
				set_pos = true;
511
			}
512 513 514 515

			if (set_pos)
				btree_node_iter_set_set_pos(node_iter,
							    b, t, k2);
516 517 518 519
		}
	}
}

520
void bch2_btree_node_iter_fix(struct btree_trans *trans,
Kent Overstreet's avatar
Kent Overstreet committed
521
			      struct btree_path *path,
522 523 524 525 526
			      struct btree *b,
			      struct btree_node_iter *node_iter,
			      struct bkey_packed *where,
			      unsigned clobber_u64s,
			      unsigned new_u64s)
527
{
528
	struct bset_tree *t = bch2_bkey_to_bset_inlined(b, where);
Kent Overstreet's avatar
Kent Overstreet committed
529
	struct btree_path *linked;
530
	unsigned i;
531

Kent Overstreet's avatar
Kent Overstreet committed
532 533
	if (node_iter != &path->l[b->c.level].iter) {
		__bch2_btree_node_iter_fix(path, b, node_iter, t,
534
					   where, clobber_u64s, new_u64s);
535

536
		if (bch2_debug_check_iterators)
537
			bch2_btree_node_iter_verify(node_iter, b);
538
	}
539

540
	trans_for_each_path_with_node(trans, b, linked, i) {
541
		__bch2_btree_node_iter_fix(linked, b,
542 543
					   &linked->l[b->c.level].iter, t,
					   where, clobber_u64s, new_u64s);
Kent Overstreet's avatar
Kent Overstreet committed
544
		bch2_btree_path_verify_level(trans, linked, b->c.level);
545
	}
546 547
}

Kent Overstreet's avatar
Kent Overstreet committed
548 549 550 551
/* Btree path level: pointer to a particular btree node and node iter */

static inline struct bkey_s_c __btree_iter_unpack(struct bch_fs *c,
						  struct btree_path_level *l,
552 553 554 555 556 557 558 559
						  struct bkey *u,
						  struct bkey_packed *k)
{
	if (unlikely(!k)) {
		/*
		 * signal to bch2_btree_iter_peek_slot() that we're currently at
		 * a hole
		 */
560
		u->type = KEY_TYPE_deleted;
561 562 563
		return bkey_s_c_null;
	}

564
	return bkey_disassemble(l->b, k, u);
565 566
}

Kent Overstreet's avatar
Kent Overstreet committed
567 568 569
static inline struct bkey_s_c btree_path_level_peek_all(struct bch_fs *c,
							struct btree_path_level *l,
							struct bkey *u)
570
{
Kent Overstreet's avatar
Kent Overstreet committed
571
	return __btree_iter_unpack(c, l, u,
572 573 574
			bch2_btree_node_iter_peek_all(&l->iter, l->b));
}

Kent Overstreet's avatar
Kent Overstreet committed
575 576 577 578
static inline struct bkey_s_c btree_path_level_peek(struct btree_trans *trans,
						    struct btree_path *path,
						    struct btree_path_level *l,
						    struct bkey *u)
579
{
Kent Overstreet's avatar
Kent Overstreet committed
580
	struct bkey_s_c k = __btree_iter_unpack(trans->c, l, u,
581
			bch2_btree_node_iter_peek(&l->iter, l->b));
582

Kent Overstreet's avatar
Kent Overstreet committed
583 584
	path->pos = k.k ? k.k->p : l->b->key.k.p;
	trans->paths_sorted = false;
585
	bch2_btree_path_verify_level(trans, path, l - path->l);
586
	return k;
587 588
}

Kent Overstreet's avatar
Kent Overstreet committed
589 590 591 592
static inline struct bkey_s_c btree_path_level_prev(struct btree_trans *trans,
						    struct btree_path *path,
						    struct btree_path_level *l,
						    struct bkey *u)
593
{
Kent Overstreet's avatar
Kent Overstreet committed
594
	struct bkey_s_c k = __btree_iter_unpack(trans->c, l, u,
595
			bch2_btree_node_iter_prev(&l->iter, l->b));
596

Kent Overstreet's avatar
Kent Overstreet committed
597 598
	path->pos = k.k ? k.k->p : l->b->data->min_key;
	trans->paths_sorted = false;
599
	bch2_btree_path_verify_level(trans, path, l - path->l);
600
	return k;
601 602
}

Kent Overstreet's avatar
Kent Overstreet committed
603 604
static inline bool btree_path_advance_to_pos(struct btree_path *path,
					     struct btree_path_level *l,
605
					     int max_advance)
606
{
607 608 609 610
	struct bkey_packed *k;
	int nr_advanced = 0;

	while ((k = bch2_btree_node_iter_peek_all(&l->iter, l->b)) &&
Kent Overstreet's avatar
Kent Overstreet committed
611
	       bkey_iter_pos_cmp(l->b, k, &path->pos) < 0) {
612 613 614 615 616 617 618 619
		if (max_advance > 0 && nr_advanced >= max_advance)
			return false;

		bch2_btree_node_iter_advance(&l->iter, l->b);
		nr_advanced++;
	}

	return true;
620 621
}

Kent Overstreet's avatar
Kent Overstreet committed
622
static inline void __btree_path_level_init(struct btree_path *path,
623
					   unsigned level)
624
{
Kent Overstreet's avatar
Kent Overstreet committed
625
	struct btree_path_level *l = &path->l[level];
626

Kent Overstreet's avatar
Kent Overstreet committed
627
	bch2_btree_node_iter_init(&l->iter, l->b, &path->pos);
628

629 630 631 632 633 634
	/*
	 * Iterators to interior nodes should always be pointed at the first non
	 * whiteout:
	 */
	if (level)
		bch2_btree_node_iter_peek(&l->iter, l->b);
635 636
}

637 638 639
void bch2_btree_path_level_init(struct btree_trans *trans,
				struct btree_path *path,
				struct btree *b)
640
{
Kent Overstreet's avatar
Kent Overstreet committed
641
	BUG_ON(path->cached);
642

Kent Overstreet's avatar
Kent Overstreet committed
643
	EBUG_ON(!btree_path_pos_in_node(path, b));
644

645
	path->l[b->c.level].lock_seq = six_lock_seq(&b->c.lock);
Kent Overstreet's avatar
Kent Overstreet committed
646 647
	path->l[b->c.level].b = b;
	__btree_path_level_init(path, b->c.level);
648 649
}

Kent Overstreet's avatar
Kent Overstreet committed
650 651
/* Btree path: fixups after btree node updates: */

652 653 654 655 656 657 658 659 660 661
static void bch2_trans_revalidate_updates_in_node(struct btree_trans *trans, struct btree *b)
{
	struct bch_fs *c = trans->c;

	trans_for_each_update(trans, i)
		if (!i->cached &&
		    i->level	== b->c.level &&
		    i->btree_id	== b->c.btree_id &&
		    bpos_cmp(i->k->k.p, b->data->min_key) >= 0 &&
		    bpos_cmp(i->k->k.p, b->data->max_key) <= 0) {
662
			i->old_v = bch2_btree_path_peek_slot(trans->paths + i->path, &i->old_k).v;
663 664 665 666 667 668 669 670 671 672 673 674 675 676

			if (unlikely(trans->journal_replay_not_finished)) {
				struct bkey_i *j_k =
					bch2_journal_keys_peek_slot(c, i->btree_id, i->level,
								    i->k->k.p);

				if (j_k) {
					i->old_k = j_k->k;
					i->old_v = &j_k->v;
				}
			}
		}
}

677 678 679 680
/*
 * A btree node is being replaced - update the iterator to point to the new
 * node:
 */
681 682 683
void bch2_trans_node_add(struct btree_trans *trans,
			 struct btree_path *path,
			 struct btree *b)
684
{
685
	struct btree_path *prev;
686

687 688 689 690 691 692 693 694 695 696
	BUG_ON(!btree_path_pos_in_node(path, b));

	while ((prev = prev_btree_path(trans, path)) &&
	       btree_path_pos_in_node(prev, b))
		path = prev;

	for (;
	     path && btree_path_pos_in_node(path, b);
	     path = next_btree_path(trans, path))
		if (path->uptodate == BTREE_ITER_UPTODATE && !path->cached) {
697 698
			enum btree_node_locked_type t =
				btree_lock_want(path, b->c.level);
699

700
			if (t != BTREE_NODE_UNLOCKED) {
701
				btree_node_unlock(trans, path, b->c.level);
702
				six_lock_increment(&b->c.lock, (enum six_lock_type) t);
703
				mark_btree_node_locked(trans, path, b->c.level, t);
704 705
			}

706
			bch2_btree_path_level_init(trans, path, b);
707
		}
708 709

	bch2_trans_revalidate_updates_in_node(trans, b);
710 711 712 713 714 715
}

/*
 * A btree node has been modified in such a way as to invalidate iterators - fix
 * them:
 */
716
void bch2_trans_node_reinit_iter(struct btree_trans *trans, struct btree *b)
717
{
Kent Overstreet's avatar
Kent Overstreet committed
718
	struct btree_path *path;
719
	unsigned i;
720

721
	trans_for_each_path_with_node(trans, b, path, i)
Kent Overstreet's avatar
Kent Overstreet committed
722
		__btree_path_level_init(path, b->c.level);
723 724

	bch2_trans_revalidate_updates_in_node(trans, b);
725 726
}

Kent Overstreet's avatar
Kent Overstreet committed
727 728 729 730
/* Btree path: traverse, set_pos: */

static inline int btree_path_lock_root(struct btree_trans *trans,
				       struct btree_path *path,
731 732
				       unsigned depth_want,
				       unsigned long trace_ip)
733
{
734
	struct bch_fs *c = trans->c;
735
	struct btree *b, **rootp = &bch2_btree_id_root(c, path->btree_id)->b;
736 737
	enum six_lock_type lock_type;
	unsigned i;
738
	int ret;
739

Kent Overstreet's avatar
Kent Overstreet committed
740
	EBUG_ON(path->nodes_locked);
741 742

	while (1) {
743
		b = READ_ONCE(*rootp);
Kent Overstreet's avatar
Kent Overstreet committed
744
		path->level = READ_ONCE(b->c.level);
745

Kent Overstreet's avatar
Kent Overstreet committed
746
		if (unlikely(path->level < depth_want)) {
747 748 749 750 751 752
			/*
			 * the root is at a lower depth than the depth we want:
			 * got to the end of the btree, or we're walking nodes
			 * greater than some depth and there are no nodes >=
			 * that depth
			 */
Kent Overstreet's avatar
Kent Overstreet committed
753 754 755
			path->level = depth_want;
			for (i = path->level; i < BTREE_MAX_DEPTH; i++)
				path->l[i].b = NULL;
756
			return 1;
757 758
		}

Kent Overstreet's avatar
Kent Overstreet committed
759
		lock_type = __btree_lock_want(path, path->level);
760 761
		ret = btree_node_lock(trans, path, &b->c,
				      path->level, lock_type, trace_ip);
762 763 764 765 766 767
		if (unlikely(ret)) {
			if (bch2_err_matches(ret, BCH_ERR_lock_fail_root_changed))
				continue;
			if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
				return ret;
			BUG();
768
		}
769

770
		if (likely(b == READ_ONCE(*rootp) &&
Kent Overstreet's avatar
Kent Overstreet committed
771
			   b->c.level == path->level &&
772
			   !race_fault())) {
Kent Overstreet's avatar
Kent Overstreet committed
773
			for (i = 0; i < path->level; i++)
774
				path->l[i].b = ERR_PTR(-BCH_ERR_no_btree_node_lock_root);
Kent Overstreet's avatar
Kent Overstreet committed
775 776 777 778
			path->l[path->level].b = b;
			for (i = path->level + 1; i < BTREE_MAX_DEPTH; i++)
				path->l[i].b = NULL;

779 780
			mark_btree_node_locked(trans, path, path->level,
					       (enum btree_node_locked_type) lock_type);
781
			bch2_btree_path_level_init(trans, path, b);
782 783 784
			return 0;
		}

785
		six_unlock_type(&b->c.lock, lock_type);
786 787 788 789
	}
}

noinline
Kent Overstreet's avatar
Kent Overstreet committed
790
static int btree_path_prefetch(struct btree_trans *trans, struct btree_path *path)
791
{
792
	struct bch_fs *c = trans->c;
Kent Overstreet's avatar
Kent Overstreet committed
793
	struct btree_path_level *l = path_l(path);
794 795
	struct btree_node_iter node_iter = l->iter;
	struct bkey_packed *k;
796
	struct bkey_buf tmp;
797
	unsigned nr = test_bit(BCH_FS_started, &c->flags)
Kent Overstreet's avatar
Kent Overstreet committed
798 799 800
		? (path->level > 1 ? 0 :  2)
		: (path->level > 1 ? 1 : 16);
	bool was_locked = btree_node_locked(path, path->level);
801
	int ret = 0;
802

803 804
	bch2_bkey_buf_init(&tmp);

805
	while (nr-- && !ret) {
Kent Overstreet's avatar
Kent Overstreet committed
806
		if (!bch2_btree_node_relock(trans, path, path->level))
807
			break;
808 809 810 811 812 813

		bch2_btree_node_iter_advance(&node_iter, l->b);
		k = bch2_btree_node_iter_peek(&node_iter, l->b);
		if (!k)
			break;

814
		bch2_bkey_buf_unpack(&tmp, c, l->b, k);
815
		ret = bch2_btree_node_prefetch(trans, path, tmp.k, path->btree_id,
Kent Overstreet's avatar
Kent Overstreet committed
816
					       path->level - 1);
817 818 819
	}

	if (!was_locked)
820
		btree_node_unlock(trans, path, path->level);
821 822

	bch2_bkey_buf_exit(&tmp, c);
823
	return ret;
824 825
}

826 827 828 829 830 831
static int btree_path_prefetch_j(struct btree_trans *trans, struct btree_path *path,
				 struct btree_and_journal_iter *jiter)
{
	struct bch_fs *c = trans->c;
	struct bkey_s_c k;
	struct bkey_buf tmp;
832
	unsigned nr = test_bit(BCH_FS_started, &c->flags)
833 834 835 836 837 838 839
		? (path->level > 1 ? 0 :  2)
		: (path->level > 1 ? 1 : 16);
	bool was_locked = btree_node_locked(path, path->level);
	int ret = 0;

	bch2_bkey_buf_init(&tmp);

840
	while (nr-- && !ret) {
841 842 843 844 845 846 847 848 849
		if (!bch2_btree_node_relock(trans, path, path->level))
			break;

		bch2_btree_and_journal_iter_advance(jiter);
		k = bch2_btree_and_journal_iter_peek(jiter);
		if (!k.k)
			break;

		bch2_bkey_buf_reassemble(&tmp, c, k);
850
		ret = bch2_btree_node_prefetch(trans, path, tmp.k, path->btree_id,
851 852 853 854
					       path->level - 1);
	}

	if (!was_locked)
855
		btree_node_unlock(trans, path, path->level);
856 857 858 859 860

	bch2_bkey_buf_exit(&tmp, c);
	return ret;
}

861
static noinline void btree_node_mem_ptr_set(struct btree_trans *trans,
Kent Overstreet's avatar
Kent Overstreet committed
862
					    struct btree_path *path,
863 864
					    unsigned plevel, struct btree *b)
{
Kent Overstreet's avatar
Kent Overstreet committed
865 866
	struct btree_path_level *l = &path->l[plevel];
	bool locked = btree_node_locked(path, plevel);
867 868 869
	struct bkey_packed *k;
	struct bch_btree_ptr_v2 *bp;

Kent Overstreet's avatar
Kent Overstreet committed
870
	if (!bch2_btree_node_relock(trans, path, plevel))
871 872 873 874 875 876 877 878 879
		return;

	k = bch2_btree_node_iter_peek_all(&l->iter, l->b);
	BUG_ON(k->type != KEY_TYPE_btree_ptr_v2);

	bp = (void *) bkeyp_val(&l->b->format, k);
	bp->mem_ptr = (unsigned long)b;

	if (!locked)
880
		btree_node_unlock(trans, path, plevel);
881 882
}

883 884 885 886 887 888 889 890 891 892 893
static noinline int btree_node_iter_and_journal_peek(struct btree_trans *trans,
						     struct btree_path *path,
						     unsigned flags,
						     struct bkey_buf *out)
{
	struct bch_fs *c = trans->c;
	struct btree_path_level *l = path_l(path);
	struct btree_and_journal_iter jiter;
	struct bkey_s_c k;
	int ret = 0;

894
	__bch2_btree_and_journal_iter_init_node_iter(trans, &jiter, l->b, l->iter, path->pos);
895 896 897 898 899

	k = bch2_btree_and_journal_iter_peek(&jiter);

	bch2_bkey_buf_reassemble(out, c, k);

900 901
	if ((flags & BTREE_ITER_PREFETCH) &&
	    c->opts.btree_node_prefetch)
902 903 904 905 906 907
		ret = btree_path_prefetch_j(trans, path, &jiter);

	bch2_btree_and_journal_iter_exit(&jiter);
	return ret;
}

Kent Overstreet's avatar
Kent Overstreet committed
908 909 910
static __always_inline int btree_path_down(struct btree_trans *trans,
					   struct btree_path *path,
					   unsigned flags,
911
					   unsigned long trace_ip)
912
{
913
	struct bch_fs *c = trans->c;
Kent Overstreet's avatar
Kent Overstreet committed
914
	struct btree_path_level *l = path_l(path);
915
	struct btree *b;
Kent Overstreet's avatar
Kent Overstreet committed
916 917
	unsigned level = path->level - 1;
	enum six_lock_type lock_type = __btree_lock_want(path, level);
918 919
	struct bkey_buf tmp;
	int ret;
920

Kent Overstreet's avatar
Kent Overstreet committed
921
	EBUG_ON(!btree_node_locked(path, path->level));
922

923
	bch2_bkey_buf_init(&tmp);
924 925 926 927 928 929

	if (unlikely(trans->journal_replay_not_finished)) {
		ret = btree_node_iter_and_journal_peek(trans, path, flags, &tmp);
		if (ret)
			goto err;
	} else {
930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945
		struct bkey_packed *k = bch2_btree_node_iter_peek(&l->iter, l->b);
		if (!k) {
			struct printbuf buf = PRINTBUF;

			prt_str(&buf, "node not found at pos ");
			bch2_bpos_to_text(&buf, path->pos);
			prt_str(&buf, " within parent node ");
			bch2_bkey_val_to_text(&buf, c, bkey_i_to_s_c(&l->b->key));

			bch2_fs_fatal_error(c, "%s", buf.buf);
			printbuf_exit(&buf);
			ret = -BCH_ERR_btree_need_topology_repair;
			goto err;
		}

		bch2_bkey_buf_unpack(&tmp, c, l->b, k);
946

947 948
		if ((flags & BTREE_ITER_PREFETCH) &&
		    c->opts.btree_node_prefetch) {
949 950 951 952 953
			ret = btree_path_prefetch(trans, path);
			if (ret)
				goto err;
		}
	}
954

Kent Overstreet's avatar
Kent Overstreet committed
955
	b = bch2_btree_node_get(trans, path, tmp.k, level, lock_type, trace_ip);
956 957 958
	ret = PTR_ERR_OR_ZERO(b);
	if (unlikely(ret))
		goto err;
959

960 961
	if (likely(!trans->journal_replay_not_finished &&
		   tmp.k->k.type == KEY_TYPE_btree_ptr_v2) &&
962
	    unlikely(b != btree_node_mem_ptr(tmp.k)))
Kent Overstreet's avatar
Kent Overstreet committed
963
		btree_node_mem_ptr_set(trans, path, level + 1, b);
964

Kent Overstreet's avatar
Kent Overstreet committed
965
	if (btree_node_read_locked(path, level + 1))
966
		btree_node_unlock(trans, path, level + 1);
967

968 969
	mark_btree_node_locked(trans, path, level,
			       (enum btree_node_locked_type) lock_type);
Kent Overstreet's avatar
Kent Overstreet committed
970
	path->level = level;
971
	bch2_btree_path_level_init(trans, path, b);
972

Kent Overstreet's avatar
Kent Overstreet committed
973
	bch2_btree_path_verify_locks(path);
974 975 976
err:
	bch2_bkey_buf_exit(&tmp, c);
	return ret;
977 978
}

979
static int bch2_btree_path_traverse_all(struct btree_trans *trans)
980
{
981
	struct bch_fs *c = trans->c;
982
	struct btree_path *path;
983
	unsigned long trace_ip = _RET_IP_;
984 985
	unsigned i;
	int ret = 0;
986

987
	if (trans->in_traverse_all)
988
		return -BCH_ERR_transaction_restart_in_traverse_all;
989 990 991

	trans->in_traverse_all = true;
retry_all:
992
	trans->restarted = 0;
993
	trans->last_restarted_ip = 0;
994

995
	trans_for_each_path(trans, path, i)
Kent Overstreet's avatar
Kent Overstreet committed
996
		path->should_be_locked = false;
997

Kent Overstreet's avatar
Kent Overstreet committed
998
	btree_trans_sort_paths(trans);
999

1000
	bch2_trans_unlock(trans);
1001
	cond_resched();
1002

1003
	if (unlikely(trans->memory_allocation_failure)) {
1004 1005 1006 1007 1008
		struct closure cl;

		closure_init_stack(&cl);

		do {
1009
			ret = bch2_btree_cache_cannibalize_lock(trans, &cl);
1010 1011 1012 1013 1014
			closure_sync(&cl);
		} while (ret);
	}

	/* Now, redo traversals in correct order: */
1015 1016
	i = 0;
	while (i < trans->nr_sorted) {
1017
		btree_path_idx_t idx = trans->sorted[i];
1018

1019 1020 1021 1022
		/*
		 * Traversing a path can cause another path to be added at about
		 * the same position:
		 */
1023 1024 1025 1026
		if (trans->paths[idx].uptodate) {
			__btree_path_get(&trans->paths[idx], false);
			ret = bch2_btree_path_traverse_one(trans, idx, 0, _THIS_IP_);
			__btree_path_put(&trans->paths[idx], false);
1027

1028
			if (bch2_err_matches(ret, BCH_ERR_transaction_restart) ||
1029
			    bch2_err_matches(ret, ENOMEM))
1030
				goto retry_all;
1031 1032
			if (ret)
				goto err;
1033
		} else {
1034
			i++;
1035
		}
1036
	}
1037 1038

	/*
1039 1040
	 * We used to assert that all paths had been traversed here
	 * (path->uptodate < BTREE_ITER_NEED_TRAVERSE); however, since
1041
	 * path->should_be_locked is not set yet, we might have unlocked and
1042
	 * then failed to relock a path - that's fine.
1043
	 */
1044
err:
1045
	bch2_btree_cache_cannibalize_unlock(trans);
1046

1047 1048
	trans->in_traverse_all = false;

1049
	trace_and_count(c, trans_traverse_all, trans, trace_ip);
1050
	return ret;
1051
}
1052

1053 1054
static inline bool btree_path_check_pos_in_node(struct btree_path *path,
						unsigned l, int check_pos)
1055
{
Kent Overstreet's avatar
Kent Overstreet committed
1056
	if (check_pos < 0 && btree_path_pos_before_node(path, path->l[l].b))
1057
		return false;
Kent Overstreet's avatar
Kent Overstreet committed
1058
	if (check_pos > 0 && btree_path_pos_after_node(path, path->l[l].b))
1059 1060 1061 1062
		return false;
	return true;
}

1063 1064 1065 1066 1067 1068 1069 1070 1071
static inline bool btree_path_good_node(struct btree_trans *trans,
					struct btree_path *path,
					unsigned l, int check_pos)
{
	return is_btree_node(path, l) &&
		bch2_btree_node_relock(trans, path, l) &&
		btree_path_check_pos_in_node(path, l, check_pos);
}

1072 1073 1074 1075 1076 1077 1078 1079 1080 1081
static void btree_path_set_level_down(struct btree_trans *trans,
				      struct btree_path *path,
				      unsigned new_level)
{
	unsigned l;

	path->level = new_level;

	for (l = path->level + 1; l < BTREE_MAX_DEPTH; l++)
		if (btree_lock_want(path, l) == BTREE_NODE_UNLOCKED)
1082
			btree_node_unlock(trans, path, l);
1083 1084 1085 1086 1087

	btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
	bch2_btree_path_verify(trans, path);
}

1088 1089 1090
static noinline unsigned __btree_path_up_until_good_node(struct btree_trans *trans,
							 struct btree_path *path,
							 int check_pos)
1091
{
1092
	unsigned i, l = path->level;
1093
again:
Kent Overstreet's avatar
Kent Overstreet committed
1094
	while (btree_path_node(path, l) &&
1095 1096
	       !btree_path_good_node(trans, path, l, check_pos))
		__btree_path_set_level_up(trans, path, l++);
1097

1098 1099 1100 1101
	/* If we need intent locks, take them too: */
	for (i = l + 1;
	     i < path->locks_want && btree_path_node(path, i);
	     i++)
1102
		if (!bch2_btree_node_relock(trans, path, i)) {
1103 1104
			while (l <= i)
				__btree_path_set_level_up(trans, path, l++);
1105 1106
			goto again;
		}
1107

1108 1109 1110
	return l;
}

1111 1112 1113 1114 1115 1116 1117 1118 1119 1120
static inline unsigned btree_path_up_until_good_node(struct btree_trans *trans,
						     struct btree_path *path,
						     int check_pos)
{
	return likely(btree_node_locked(path, path->level) &&
		      btree_path_check_pos_in_node(path, path->level, check_pos))
		? path->level
		: __btree_path_up_until_good_node(trans, path, check_pos);
}

1121 1122 1123 1124 1125 1126 1127
/*
 * This is the main state machine for walking down the btree - walks down to a
 * specified depth
 *
 * Returns 0 on success, -EIO on error (error reading in a btree node).
 *
 * On error, caller (peek_node()/peek_key()) must return NULL; the error is
1128
 * stashed in the iterator and returned from bch2_trans_exit().
1129
 */
1130
int bch2_btree_path_traverse_one(struct btree_trans *trans,
1131
				 btree_path_idx_t path_idx,
1132 1133
				 unsigned flags,
				 unsigned long trace_ip)
1134
{
1135
	struct btree_path *path = &trans->paths[path_idx];
1136
	unsigned depth_want = path->level;
1137
	int ret = -((int) trans->restarted);
1138

1139
	if (unlikely(ret))
1140 1141
		goto out;

1142 1143 1144
	if (unlikely(!trans->srcu_held))
		bch2_trans_srcu_lock(trans);

1145
	/*
Kent Overstreet's avatar
Kent Overstreet committed
1146 1147
	 * Ensure we obey path->should_be_locked: if it's set, we can't unlock
	 * and re-traverse the path without a transaction restart:
1148
	 */
Kent Overstreet's avatar
Kent Overstreet committed
1149
	if (path->should_be_locked) {
1150
		ret = bch2_btree_path_relock(trans, path, trace_ip);
1151 1152 1153
		goto out;
	}

Kent Overstreet's avatar
Kent Overstreet committed
1154 1155
	if (path->cached) {
		ret = bch2_btree_path_traverse_cached(trans, path, flags);
1156 1157
		goto out;
	}
1158

1159 1160
	path = &trans->paths[path_idx];

Kent Overstreet's avatar
Kent Overstreet committed
1161
	if (unlikely(path->level >= BTREE_MAX_DEPTH))
1162
		goto out_uptodate;
1163

Kent Overstreet's avatar
Kent Overstreet committed
1164
	path->level = btree_path_up_until_good_node(trans, path, 0);
1165
	unsigned max_level = path->level;
1166

1167 1168 1169
	EBUG_ON(btree_path_node(path, path->level) &&
		!btree_node_locked(path, path->level));

1170
	/*
Kent Overstreet's avatar
Kent Overstreet committed
1171
	 * Note: path->nodes[path->level] may be temporarily NULL here - that
1172 1173
	 * would indicate to other code that we got to the end of the btree,
	 * here it indicates that relocking the root failed - it's critical that
Kent Overstreet's avatar
Kent Overstreet committed
1174
	 * btree_path_lock_root() comes next and that it can't fail
1175
	 */
Kent Overstreet's avatar
Kent Overstreet committed
1176 1177 1178 1179
	while (path->level > depth_want) {
		ret = btree_path_node(path, path->level)
			? btree_path_down(trans, path, flags, trace_ip)
			: btree_path_lock_root(trans, path, depth_want, trace_ip);
1180
		if (unlikely(ret)) {
1181 1182
			if (ret == 1) {
				/*
1183 1184
				 * No nodes at this level - got to the end of
				 * the btree:
1185 1186 1187 1188
				 */
				ret = 0;
				goto out;
			}
1189

1190
			__bch2_btree_path_unlock(trans, path);
Kent Overstreet's avatar
Kent Overstreet committed
1191
			path->level = depth_want;
1192
			path->l[path->level].b = ERR_PTR(ret);
1193
			goto out;
1194 1195
		}
	}
1196 1197 1198 1199 1200 1201 1202 1203 1204 1205

	if (unlikely(max_level > path->level)) {
		struct btree_path *linked;
		unsigned iter;

		trans_for_each_path_with_node(trans, path_l(path)->b, linked, iter)
			for (unsigned j = path->level + 1; j < max_level; j++)
				linked->l[j] = path->l[j];
	}

1206
out_uptodate:
Kent Overstreet's avatar
Kent Overstreet committed
1207
	path->uptodate = BTREE_ITER_UPTODATE;
1208
out:
1209 1210 1211 1212
	if (bch2_err_matches(ret, BCH_ERR_transaction_restart) != !!trans->restarted)
		panic("ret %s (%i) trans->restarted %s (%i)\n",
		      bch2_err_str(ret), ret,
		      bch2_err_str(trans->restarted), trans->restarted);
Kent Overstreet's avatar
Kent Overstreet committed
1213
	bch2_btree_path_verify(trans, path);
1214
	return ret;
1215 1216
}

1217
static inline void btree_path_copy(struct btree_trans *trans, struct btree_path *dst,
Kent Overstreet's avatar
Kent Overstreet committed
1218 1219 1220 1221 1222 1223 1224 1225
			    struct btree_path *src)
{
	unsigned i, offset = offsetof(struct btree_path, pos);

	memcpy((void *) dst + offset,
	       (void *) src + offset,
	       sizeof(struct btree_path) - offset);

1226 1227 1228 1229 1230 1231
	for (i = 0; i < BTREE_MAX_DEPTH; i++) {
		unsigned t = btree_node_locked_type(dst, i);

		if (t != BTREE_NODE_UNLOCKED)
			six_lock_increment(&dst->l[i].b->c.lock, t);
	}
Kent Overstreet's avatar
Kent Overstreet committed
1232 1233
}

1234 1235
static btree_path_idx_t btree_path_clone(struct btree_trans *trans, btree_path_idx_t src,
					 bool intent)
Kent Overstreet's avatar
Kent Overstreet committed
1236
{
1237 1238 1239
	btree_path_idx_t new = btree_path_alloc(trans, src);
	btree_path_copy(trans, trans->paths + new, trans->paths + src);
	__btree_path_get(trans->paths + new, intent);
1240 1241 1242
	return new;
}

1243
__flatten
1244 1245
btree_path_idx_t __bch2_btree_path_make_mut(struct btree_trans *trans,
			btree_path_idx_t path, bool intent, unsigned long ip)
1246
{
1247
	__btree_path_put(trans->paths + path, intent);
1248
	path = btree_path_clone(trans, path, intent);
1249
	trans->paths[path].preserve = false;
Kent Overstreet's avatar
Kent Overstreet committed
1250 1251 1252
	return path;
}

1253
btree_path_idx_t __must_check
Kent Overstreet's avatar
Kent Overstreet committed
1254
__bch2_btree_path_set_pos(struct btree_trans *trans,
1255 1256
			  btree_path_idx_t path_idx, struct bpos new_pos,
			  bool intent, unsigned long ip)
Kent Overstreet's avatar
Kent Overstreet committed
1257
{
1258
	int cmp = bpos_cmp(new_pos, trans->paths[path_idx].pos);
1259

1260
	bch2_trans_verify_not_in_restart(trans);
1261
	EBUG_ON(!trans->paths[path_idx].ref);
Kent Overstreet's avatar
Kent Overstreet committed
1262

1263
	path_idx = bch2_btree_path_make_mut(trans, path_idx, intent, ip);
Kent Overstreet's avatar
Kent Overstreet committed
1264

1265
	struct btree_path *path = trans->paths + path_idx;
Kent Overstreet's avatar
Kent Overstreet committed
1266 1267 1268 1269
	path->pos		= new_pos;
	trans->paths_sorted	= false;

	if (unlikely(path->cached)) {
1270
		btree_node_unlock(trans, path, 0);
1271
		path->l[0].b = ERR_PTR(-BCH_ERR_no_btree_node_up);
Kent Overstreet's avatar
Kent Overstreet committed
1272 1273 1274 1275
		btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
		goto out;
	}

1276
	unsigned level = btree_path_up_until_good_node(trans, path, cmp);
Kent Overstreet's avatar
Kent Overstreet committed
1277

1278 1279 1280 1281
	if (btree_path_node(path, level)) {
		struct btree_path_level *l = &path->l[level];

		BUG_ON(!btree_node_locked(path, level));
Kent Overstreet's avatar
Kent Overstreet committed
1282 1283 1284 1285 1286 1287 1288
		/*
		 * We might have to skip over many keys, or just a few: try
		 * advancing the node iterator, and if we have to skip over too
		 * many keys just reinit it (or if we're rewinding, since that
		 * is expensive).
		 */
		if (cmp < 0 ||
1289 1290 1291 1292 1293 1294 1295 1296 1297
		    !btree_path_advance_to_pos(path, l, 8))
			bch2_btree_node_iter_init(&l->iter, l->b, &path->pos);

		/*
		 * Iterators to interior nodes should always be pointed at the first non
		 * whiteout:
		 */
		if (unlikely(level))
			bch2_btree_node_iter_peek(&l->iter, l->b);
Kent Overstreet's avatar
Kent Overstreet committed
1298 1299
	}

1300
	if (unlikely(level != path->level)) {
Kent Overstreet's avatar
Kent Overstreet committed
1301
		btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
1302
		__bch2_btree_path_unlock(trans, path);
1303
	}
Kent Overstreet's avatar
Kent Overstreet committed
1304 1305
out:
	bch2_btree_path_verify(trans, path);
1306
	return path_idx;
Kent Overstreet's avatar
Kent Overstreet committed
1307 1308 1309 1310 1311 1312
}

/* Btree path: main interface: */

static struct btree_path *have_path_at_pos(struct btree_trans *trans, struct btree_path *path)
{
1313
	struct btree_path *sib;
Kent Overstreet's avatar
Kent Overstreet committed
1314

1315 1316 1317
	sib = prev_btree_path(trans, path);
	if (sib && !btree_path_cmp(sib, path))
		return sib;
Kent Overstreet's avatar
Kent Overstreet committed
1318

1319 1320 1321
	sib = next_btree_path(trans, path);
	if (sib && !btree_path_cmp(sib, path))
		return sib;
Kent Overstreet's avatar
Kent Overstreet committed
1322 1323 1324 1325

	return NULL;
}

1326
static struct btree_path *have_node_at_pos(struct btree_trans *trans, struct btree_path *path)
Kent Overstreet's avatar
Kent Overstreet committed
1327
{
1328
	struct btree_path *sib;
Kent Overstreet's avatar
Kent Overstreet committed
1329

1330 1331 1332
	sib = prev_btree_path(trans, path);
	if (sib && sib->level == path->level && path_l(sib)->b == path_l(path)->b)
		return sib;
Kent Overstreet's avatar
Kent Overstreet committed
1333

1334 1335 1336
	sib = next_btree_path(trans, path);
	if (sib && sib->level == path->level && path_l(sib)->b == path_l(path)->b)
		return sib;
Kent Overstreet's avatar
Kent Overstreet committed
1337

1338
	return NULL;
Kent Overstreet's avatar
Kent Overstreet committed
1339 1340
}

1341
static inline void __bch2_path_free(struct btree_trans *trans, btree_path_idx_t path)
1342
{
1343 1344 1345
	__bch2_btree_path_unlock(trans, trans->paths + path);
	btree_path_list_remove(trans, trans->paths + path);
	__clear_bit(path, trans->paths_allocated);
1346 1347
}

1348
void bch2_path_put(struct btree_trans *trans, btree_path_idx_t path_idx, bool intent)
Kent Overstreet's avatar
Kent Overstreet committed
1349
{
1350
	struct btree_path *path = trans->paths + path_idx, *dup;
Kent Overstreet's avatar
Kent Overstreet committed
1351 1352 1353 1354

	if (!__btree_path_put(path, intent))
		return;

1355 1356 1357 1358 1359 1360
	dup = path->preserve
		? have_path_at_pos(trans, path)
		: have_node_at_pos(trans, path);

	if (!dup && !(!path->preserve && !is_btree_node(path, path->level)))
		return;
Kent Overstreet's avatar
Kent Overstreet committed
1361

1362
	if (path->should_be_locked &&
1363
	    !trans->restarted &&
1364
	    (!dup || !bch2_btree_path_relock_norestart(trans, dup)))
1365 1366
		return;

1367 1368 1369 1370 1371
	if (dup) {
		dup->preserve		|= path->preserve;
		dup->should_be_locked	|= path->should_be_locked;
	}

1372
	__bch2_path_free(trans, path_idx);
Kent Overstreet's avatar
Kent Overstreet committed
1373 1374
}

1375
static void bch2_path_put_nokeep(struct btree_trans *trans, btree_path_idx_t path,
1376 1377
				 bool intent)
{
1378
	if (!__btree_path_put(trans->paths + path, intent))
1379 1380 1381 1382 1383
		return;

	__bch2_path_free(trans, path);
}

1384 1385 1386 1387
void __noreturn bch2_trans_restart_error(struct btree_trans *trans, u32 restart_count)
{
	panic("trans->restart_count %u, should be %u, last restarted by %pS\n",
	      trans->restart_count, restart_count,
1388
	      (void *) trans->last_begin_ip);
1389 1390 1391 1392 1393 1394 1395 1396 1397
}

void __noreturn bch2_trans_in_restart_error(struct btree_trans *trans)
{
	panic("in transaction restart: %s, last restarted by %pS\n",
	      bch2_err_str(trans->restarted),
	      (void *) trans->last_restarted_ip);
}

1398
noinline __cold
1399
void bch2_trans_updates_to_text(struct printbuf *buf, struct btree_trans *trans)
Kent Overstreet's avatar
Kent Overstreet committed
1400
{
1401
	prt_printf(buf, "transaction updates for %s journal seq %llu\n",
1402
	       trans->fn, trans->journal_res.seq);
1403
	printbuf_indent_add(buf, 2);
1404 1405 1406 1407

	trans_for_each_update(trans, i) {
		struct bkey_s_c old = { &i->old_k, i->old_v };

1408
		prt_printf(buf, "update: btree=%s cached=%u %pS\n",
1409
		       bch2_btree_id_str(i->btree_id),
1410 1411 1412
		       i->cached,
		       (void *) i->ip_allocated);

1413
		prt_printf(buf, "  old ");
1414
		bch2_bkey_val_to_text(buf, trans->c, old);
1415
		prt_newline(buf);
1416

1417
		prt_printf(buf, "  new ");
1418
		bch2_bkey_val_to_text(buf, trans->c, bkey_i_to_s_c(i->k));
1419
		prt_newline(buf);
1420 1421
	}

1422 1423 1424 1425
	for (struct jset_entry *e = trans->journal_entries;
	     e != btree_trans_journal_entries_top(trans);
	     e = vstruct_next(e))
		bch2_journal_entry_to_text(buf, trans->c, e);
1426

1427
	printbuf_indent_sub(buf, 2);
1428 1429 1430 1431 1432 1433 1434 1435
}

noinline __cold
void bch2_dump_trans_updates(struct btree_trans *trans)
{
	struct printbuf buf = PRINTBUF;

	bch2_trans_updates_to_text(&buf, trans);
1436
	bch2_print_string_as_lines(KERN_ERR, buf.buf);
1437
	printbuf_exit(&buf);
1438 1439
}

1440
static void bch2_btree_path_to_text_short(struct printbuf *out, struct btree_trans *trans, btree_path_idx_t path_idx)
1441
{
1442 1443
	struct btree_path *path = trans->paths + path_idx;

1444
	prt_printf(out, "path: idx %2u ref %u:%u %c %c %c btree=%s l=%u pos ",
1445
		   path_idx, path->ref, path->intent_ref,
1446 1447
		   path->preserve ? 'P' : ' ',
		   path->should_be_locked ? 'S' : ' ',
1448
		   path->cached ? 'C' : 'B',
1449
		   bch2_btree_id_str(path->btree_id),
1450 1451 1452
		   path->level);
	bch2_bpos_to_text(out, path->pos);

1453
#ifdef TRACK_PATH_ALLOCATED
1454 1455
	prt_printf(out, " %pS", (void *) path->ip_allocated);
#endif
1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480
}

static const char *btree_node_locked_str(enum btree_node_locked_type t)
{
	switch (t) {
	case BTREE_NODE_UNLOCKED:
		return "unlocked";
	case BTREE_NODE_READ_LOCKED:
		return "read";
	case BTREE_NODE_INTENT_LOCKED:
		return "intent";
	case BTREE_NODE_WRITE_LOCKED:
		return "write";
	default:
		return NULL;
	}
}

void bch2_btree_path_to_text(struct printbuf *out, struct btree_trans *trans, btree_path_idx_t path_idx)
{
	bch2_btree_path_to_text_short(out, trans, path_idx);

	struct btree_path *path = trans->paths + path_idx;

	prt_printf(out, " uptodate %u locks_want %u", path->uptodate, path->locks_want);
1481
	prt_newline(out);
1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496

	printbuf_indent_add(out, 2);
	for (unsigned l = 0; l < BTREE_MAX_DEPTH; l++) {
		prt_printf(out, "l=%u locks %s seq %u node ", l,
			   btree_node_locked_str(btree_node_locked_type(path, l)),
			   path->l[l].lock_seq);

		int ret = PTR_ERR_OR_ZERO(path->l[l].b);
		if (ret)
			prt_str(out, bch2_err_str(ret));
		else
			prt_printf(out, "%px", path->l[l].b);
		prt_newline(out);
	}
	printbuf_indent_sub(out, 2);
1497 1498
}

1499
static noinline __cold
1500 1501
void __bch2_trans_paths_to_text(struct printbuf *out, struct btree_trans *trans,
				bool nosort)
1502
{
1503
	struct trans_for_each_path_inorder_iter iter;
Kent Overstreet's avatar
Kent Overstreet committed
1504

1505 1506
	if (!nosort)
		btree_trans_sort_paths(trans);
Kent Overstreet's avatar
Kent Overstreet committed
1507

1508 1509 1510 1511
	trans_for_each_path_idx_inorder(trans, iter) {
		bch2_btree_path_to_text_short(out, trans, iter.path_idx);
		prt_newline(out);
	}
1512
}
1513

1514 1515 1516 1517 1518
noinline __cold
void bch2_trans_paths_to_text(struct printbuf *out, struct btree_trans *trans)
{
	__bch2_trans_paths_to_text(out, trans, false);
}
1519

1520
static noinline __cold
1521 1522 1523 1524 1525
void __bch2_dump_trans_paths_updates(struct btree_trans *trans, bool nosort)
{
	struct printbuf buf = PRINTBUF;

	__bch2_trans_paths_to_text(&buf, trans, nosort);
1526
	bch2_trans_updates_to_text(&buf, trans);
Kent Overstreet's avatar
Kent Overstreet committed
1527

1528
	bch2_print_string_as_lines(KERN_ERR, buf.buf);
1529
	printbuf_exit(&buf);
Kent Overstreet's avatar
Kent Overstreet committed
1530 1531
}

1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542
noinline __cold
void bch2_dump_trans_paths_updates(struct btree_trans *trans)
{
	__bch2_dump_trans_paths_updates(trans, false);
}

noinline __cold
static void bch2_trans_update_max_paths(struct btree_trans *trans)
{
	struct btree_transaction_stats *s = btree_trans_stats(trans);
	struct printbuf buf = PRINTBUF;
1543
	size_t nr = bitmap_weight(trans->paths_allocated, trans->nr_paths);
1544 1545 1546 1547 1548

	bch2_trans_paths_to_text(&buf, trans);

	if (!buf.allocation_failure) {
		mutex_lock(&s->lock);
1549 1550
		if (nr > s->nr_max_paths) {
			s->nr_max_paths = nr;
1551 1552 1553 1554 1555 1556 1557
			swap(s->max_paths_text, buf.buf);
		}
		mutex_unlock(&s->lock);
	}

	printbuf_exit(&buf);

1558
	trans->nr_paths_max = nr;
1559 1560
}

1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576
noinline __cold
int __bch2_btree_trans_too_many_iters(struct btree_trans *trans)
{
	if (trace_trans_restart_too_many_iters_enabled()) {
		struct printbuf buf = PRINTBUF;

		bch2_trans_paths_to_text(&buf, trans);
		trace_trans_restart_too_many_iters(trans, _THIS_IP_, buf.buf);
		printbuf_exit(&buf);
	}

	count_event(trans->c, trans_restart_too_many_iters);

	return btree_trans_restart(trans, BCH_ERR_transaction_restart_too_many_iters);
}

1577 1578 1579
static noinline void btree_path_overflow(struct btree_trans *trans)
{
	bch2_dump_trans_paths_updates(trans);
1580 1581 1582 1583 1584 1585 1586
	bch_err(trans->c, "trans path overflow");
}

static noinline void btree_paths_realloc(struct btree_trans *trans)
{
	unsigned nr = trans->nr_paths * 2;

1587
	void *p = kvzalloc(BITS_TO_LONGS(nr) * sizeof(unsigned long) +
1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620
			  sizeof(struct btree_trans_paths) +
			  nr * sizeof(struct btree_path) +
			  nr * sizeof(btree_path_idx_t) + 8 +
			  nr * sizeof(struct btree_insert_entry), GFP_KERNEL|__GFP_NOFAIL);

	unsigned long *paths_allocated = p;
	memcpy(paths_allocated, trans->paths_allocated, BITS_TO_LONGS(trans->nr_paths) * sizeof(unsigned long));
	p += BITS_TO_LONGS(nr) * sizeof(unsigned long);

	p += sizeof(struct btree_trans_paths);
	struct btree_path *paths = p;
	*trans_paths_nr(paths) = nr;
	memcpy(paths, trans->paths, trans->nr_paths * sizeof(struct btree_path));
	p += nr * sizeof(struct btree_path);

	btree_path_idx_t *sorted = p;
	memcpy(sorted, trans->sorted, trans->nr_sorted * sizeof(btree_path_idx_t));
	p += nr * sizeof(btree_path_idx_t) + 8;

	struct btree_insert_entry *updates = p;
	memcpy(updates, trans->updates, trans->nr_paths * sizeof(struct btree_insert_entry));

	unsigned long *old = trans->paths_allocated;

	rcu_assign_pointer(trans->paths_allocated,	paths_allocated);
	rcu_assign_pointer(trans->paths,		paths);
	rcu_assign_pointer(trans->sorted,		sorted);
	rcu_assign_pointer(trans->updates,		updates);

	trans->nr_paths		= nr;

	if (old != trans->_paths_allocated)
		kfree_rcu_mightsleep(old);
1621 1622
}

1623 1624
static inline btree_path_idx_t btree_path_alloc(struct btree_trans *trans,
						btree_path_idx_t pos)
Kent Overstreet's avatar
Kent Overstreet committed
1625
{
1626
	btree_path_idx_t idx = find_first_zero_bit(trans->paths_allocated, trans->nr_paths);
Kent Overstreet's avatar
Kent Overstreet committed
1627

1628 1629 1630 1631 1632 1633 1634 1635
	if (unlikely(idx == trans->nr_paths)) {
		if (trans->nr_paths == BTREE_ITER_MAX) {
			btree_path_overflow(trans);
			return 0;
		}

		btree_paths_realloc(trans);
	}
Kent Overstreet's avatar
Kent Overstreet committed
1636

1637 1638 1639 1640
	/*
	 * Do this before marking the new path as allocated, since it won't be
	 * initialized yet:
	 */
1641
	if (unlikely(idx > trans->nr_paths_max))
1642 1643
		bch2_trans_update_max_paths(trans);

1644
	__set_bit(idx, trans->paths_allocated);
Kent Overstreet's avatar
Kent Overstreet committed
1645

1646
	struct btree_path *path = &trans->paths[idx];
Kent Overstreet's avatar
Kent Overstreet committed
1647 1648 1649 1650
	path->ref		= 0;
	path->intent_ref	= 0;
	path->nodes_locked	= 0;

1651
	btree_path_list_add(trans, pos, idx);
1652
	trans->paths_sorted = false;
1653
	return idx;
Kent Overstreet's avatar
Kent Overstreet committed
1654 1655
}

1656 1657 1658 1659
btree_path_idx_t bch2_path_get(struct btree_trans *trans,
			     enum btree_id btree_id, struct bpos pos,
			     unsigned locks_want, unsigned level,
			     unsigned flags, unsigned long ip)
Kent Overstreet's avatar
Kent Overstreet committed
1660
{
1661
	struct btree_path *path;
1662 1663
	bool cached = flags & BTREE_ITER_CACHED;
	bool intent = flags & BTREE_ITER_INTENT;
1664
	struct trans_for_each_path_inorder_iter iter;
1665
	btree_path_idx_t path_pos = 0, path_idx;
Kent Overstreet's avatar
Kent Overstreet committed
1666

1667
	bch2_trans_verify_not_in_restart(trans);
1668 1669
	bch2_trans_verify_locks(trans);

1670
	btree_trans_sort_paths(trans);
Kent Overstreet's avatar
Kent Overstreet committed
1671

1672
	trans_for_each_path_inorder(trans, path, iter) {
1673 1674 1675 1676 1677 1678
		if (__btree_path_cmp(path,
				     btree_id,
				     cached,
				     pos,
				     level) > 0)
			break;
Kent Overstreet's avatar
Kent Overstreet committed
1679

1680
		path_pos = iter.path_idx;
Kent Overstreet's avatar
Kent Overstreet committed
1681 1682
	}

1683
	if (path_pos &&
1684 1685 1686 1687
	    trans->paths[path_pos].cached	== cached &&
	    trans->paths[path_pos].btree_id	== btree_id &&
	    trans->paths[path_pos].level	== level) {
		__btree_path_get(trans->paths + path_pos, intent);
1688 1689
		path_idx = bch2_btree_path_set_pos(trans, path_pos, pos, intent, ip);
		path = trans->paths + path_idx;
Kent Overstreet's avatar
Kent Overstreet committed
1690
	} else {
1691 1692
		path_idx = btree_path_alloc(trans, path_pos);
		path = trans->paths + path_idx;
Kent Overstreet's avatar
Kent Overstreet committed
1693 1694 1695 1696 1697 1698 1699 1700 1701 1702

		__btree_path_get(path, intent);
		path->pos			= pos;
		path->btree_id			= btree_id;
		path->cached			= cached;
		path->uptodate			= BTREE_ITER_NEED_TRAVERSE;
		path->should_be_locked		= false;
		path->level			= level;
		path->locks_want		= locks_want;
		path->nodes_locked		= 0;
1703
		for (unsigned i = 0; i < ARRAY_SIZE(path->l); i++)
1704
			path->l[i].b		= ERR_PTR(-BCH_ERR_no_btree_node_init);
1705
#ifdef TRACK_PATH_ALLOCATED
1706
		path->ip_allocated		= ip;
Kent Overstreet's avatar
Kent Overstreet committed
1707 1708 1709 1710
#endif
		trans->paths_sorted		= false;
	}

1711 1712 1713
	if (!(flags & BTREE_ITER_NOPRESERVE))
		path->preserve = true;

Kent Overstreet's avatar
Kent Overstreet committed
1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725
	if (path->intent_ref)
		locks_want = max(locks_want, level + 1);

	/*
	 * If the path has locks_want greater than requested, we don't downgrade
	 * it here - on transaction restart because btree node split needs to
	 * upgrade locks, we might be putting/getting the iterator again.
	 * Downgrading iterators only happens via bch2_trans_downgrade(), after
	 * a successful transaction commit.
	 */

	locks_want = min(locks_want, BTREE_MAX_DEPTH);
1726
	if (locks_want > path->locks_want)
1727
		bch2_btree_path_upgrade_noupgrade_sibs(trans, path, locks_want, NULL);
Kent Overstreet's avatar
Kent Overstreet committed
1728

1729
	return path_idx;
Kent Overstreet's avatar
Kent Overstreet committed
1730 1731
}

1732
struct bkey_s_c bch2_btree_path_peek_slot(struct btree_path *path, struct bkey *u)
Kent Overstreet's avatar
Kent Overstreet committed
1733 1734
{

1735 1736
	struct btree_path_level *l = path_l(path);
	struct bkey_packed *_k;
Kent Overstreet's avatar
Kent Overstreet committed
1737 1738
	struct bkey_s_c k;

1739 1740
	if (unlikely(!l->b))
		return bkey_s_c_null;
1741

1742 1743
	EBUG_ON(path->uptodate != BTREE_ITER_UPTODATE);
	EBUG_ON(!btree_node_locked(path, path->level));
Kent Overstreet's avatar
Kent Overstreet committed
1744

1745
	if (!path->cached) {
1746
		_k = bch2_btree_node_iter_peek_all(&l->iter, l->b);
Kent Overstreet's avatar
Kent Overstreet committed
1747 1748
		k = _k ? bkey_disassemble(l->b, _k, u) : bkey_s_c_null;

1749
		EBUG_ON(k.k && bkey_deleted(k.k) && bpos_eq(k.k->p, path->pos));
Kent Overstreet's avatar
Kent Overstreet committed
1750

1751
		if (!k.k || !bpos_eq(path->pos, k.k->p))
Kent Overstreet's avatar
Kent Overstreet committed
1752 1753 1754 1755
			goto hole;
	} else {
		struct bkey_cached *ck = (void *) path->l[0].b;

1756 1757
		EBUG_ON(ck &&
			(path->btree_id != ck->key.btree_id ||
1758
			 !bkey_eq(path->pos, ck->key.pos)));
1759 1760
		if (!ck || !ck->valid)
			return bkey_s_c_null;
Kent Overstreet's avatar
Kent Overstreet committed
1761

1762
		*u = ck->k->k;
Kent Overstreet's avatar
Kent Overstreet committed
1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774
		k = bkey_i_to_s_c(ck->k);
	}

	return k;
hole:
	bkey_init(u);
	u->p = path->pos;
	return (struct bkey_s_c) { u, NULL };
}

/* Btree iterators: */

1775 1776 1777
int __must_check
__bch2_btree_iter_traverse(struct btree_iter *iter)
{
1778
	return bch2_btree_path_traverse(iter->trans, iter->path, iter->flags);
1779 1780
}

1781 1782 1783
int __must_check
bch2_btree_iter_traverse(struct btree_iter *iter)
{
1784
	struct btree_trans *trans = iter->trans;
1785 1786
	int ret;

1787
	iter->path = bch2_btree_path_set_pos(trans, iter->path,
Kent Overstreet's avatar
Kent Overstreet committed
1788
					btree_iter_search_key(iter),
1789 1790
					iter->flags & BTREE_ITER_INTENT,
					btree_iter_ip_allocated(iter));
1791

1792
	ret = bch2_btree_path_traverse(iter->trans, iter->path, iter->flags);
1793 1794 1795
	if (ret)
		return ret;

1796 1797 1798
	struct btree_path *path = btree_iter_path(trans, iter);
	if (btree_path_node(path, path->level))
		btree_path_set_should_be_locked(path);
1799
	return 0;
1800 1801
}

1802 1803 1804 1805
/* Iterate across nodes (leaf and interior nodes) */

struct btree *bch2_btree_iter_peek_node(struct btree_iter *iter)
{
1806
	struct btree_trans *trans = iter->trans;
1807
	struct btree *b = NULL;
1808 1809
	int ret;

1810
	EBUG_ON(trans->paths[iter->path].cached);
1811
	bch2_btree_iter_verify(iter);
1812

1813
	ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
1814
	if (ret)
1815
		goto err;
1816

1817 1818
	struct btree_path *path = btree_iter_path(trans, iter);
	b = btree_path_node(path, path->level);
1819
	if (!b)
1820
		goto out;
1821

1822
	BUG_ON(bpos_lt(b->key.k.p, iter->pos));
1823

1824
	bkey_init(&iter->k);
Kent Overstreet's avatar
Kent Overstreet committed
1825
	iter->k.p = iter->pos = b->key.k.p;
1826

1827
	iter->path = bch2_btree_path_set_pos(trans, iter->path, b->key.k.p,
1828 1829
					iter->flags & BTREE_ITER_INTENT,
					btree_iter_ip_allocated(iter));
1830
	btree_path_set_should_be_locked(btree_iter_path(trans, iter));
1831 1832 1833
out:
	bch2_btree_iter_verify_entry_exit(iter);
	bch2_btree_iter_verify(iter);
1834

1835
	return b;
1836 1837 1838
err:
	b = ERR_PTR(ret);
	goto out;
1839 1840
}

1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851
struct btree *bch2_btree_iter_peek_node_and_restart(struct btree_iter *iter)
{
	struct btree *b;

	while (b = bch2_btree_iter_peek_node(iter),
	       bch2_err_matches(PTR_ERR_OR_ZERO(b), BCH_ERR_transaction_restart))
		bch2_trans_begin(iter->trans);

	return b;
}

1852
struct btree *bch2_btree_iter_next_node(struct btree_iter *iter)
1853
{
Kent Overstreet's avatar
Kent Overstreet committed
1854
	struct btree_trans *trans = iter->trans;
1855
	struct btree *b = NULL;
1856 1857
	int ret;

1858
	EBUG_ON(trans->paths[iter->path].cached);
1859
	bch2_trans_verify_not_in_restart(trans);
1860
	bch2_btree_iter_verify(iter);
1861

1862 1863
	struct btree_path *path = btree_iter_path(trans, iter);

1864
	/* already at end? */
Kent Overstreet's avatar
Kent Overstreet committed
1865
	if (!btree_path_node(path, path->level))
1866
		return NULL;
1867

1868 1869
	/* got to end? */
	if (!btree_path_node(path, path->level + 1)) {
1870
		btree_path_set_level_up(trans, path);
1871 1872
		return NULL;
	}
1873

1874
	if (!bch2_btree_node_relock(trans, path, path->level + 1)) {
1875
		__bch2_btree_path_unlock(trans, path);
1876 1877
		path->l[path->level].b		= ERR_PTR(-BCH_ERR_no_btree_node_relock);
		path->l[path->level + 1].b	= ERR_PTR(-BCH_ERR_no_btree_node_relock);
1878
		btree_path_set_dirty(path, BTREE_ITER_NEED_TRAVERSE);
1879
		trace_and_count(trans->c, trans_restart_relock_next_node, trans, _THIS_IP_, path);
1880
		ret = btree_trans_restart(trans, BCH_ERR_transaction_restart_relock);
1881
		goto err;
1882
	}
1883

1884
	b = btree_path_node(path, path->level + 1);
1885

1886
	if (bpos_eq(iter->pos, b->key.k.p)) {
1887
		__btree_path_set_level_up(trans, path, path->level++);
1888
	} else {
1889 1890 1891 1892
		/*
		 * Haven't gotten to the end of the parent node: go back down to
		 * the next child node
		 */
1893 1894 1895 1896
		iter->path = bch2_btree_path_set_pos(trans, iter->path,
					bpos_successor(iter->pos),
					iter->flags & BTREE_ITER_INTENT,
					btree_iter_ip_allocated(iter));
1897

1898
		path = btree_iter_path(trans, iter);
1899
		btree_path_set_level_down(trans, path, iter->min_depth);
1900

1901
		ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
1902 1903
		if (ret)
			goto err;
1904

1905
		path = btree_iter_path(trans, iter);
Kent Overstreet's avatar
Kent Overstreet committed
1906
		b = path->l[path->level].b;
1907 1908
	}

1909
	bkey_init(&iter->k);
Kent Overstreet's avatar
Kent Overstreet committed
1910
	iter->k.p = iter->pos = b->key.k.p;
1911

1912
	iter->path = bch2_btree_path_set_pos(trans, iter->path, b->key.k.p,
1913 1914
					iter->flags & BTREE_ITER_INTENT,
					btree_iter_ip_allocated(iter));
1915 1916
	btree_path_set_should_be_locked(btree_iter_path(trans, iter));
	EBUG_ON(btree_iter_path(trans, iter)->uptodate);
1917 1918 1919
out:
	bch2_btree_iter_verify_entry_exit(iter);
	bch2_btree_iter_verify(iter);
1920

1921
	return b;
1922 1923 1924
err:
	b = ERR_PTR(ret);
	goto out;
1925 1926 1927 1928
}

/* Iterate across keys (in leaf nodes only) */

1929
inline bool bch2_btree_iter_advance(struct btree_iter *iter)
1930
{
1931 1932 1933 1934
	struct bpos pos = iter->k.p;
	bool ret = !(iter->flags & BTREE_ITER_ALL_SNAPSHOTS
		     ? bpos_eq(pos, SPOS_MAX)
		     : bkey_eq(pos, SPOS_MAX));
1935

1936 1937 1938 1939
	if (ret && !(iter->flags & BTREE_ITER_IS_EXTENTS))
		pos = bkey_successor(iter, pos);
	bch2_btree_iter_set_pos(iter, pos);
	return ret;
1940 1941
}

1942
inline bool bch2_btree_iter_rewind(struct btree_iter *iter)
1943 1944
{
	struct bpos pos = bkey_start_pos(&iter->k);
1945 1946 1947
	bool ret = !(iter->flags & BTREE_ITER_ALL_SNAPSHOTS
		     ? bpos_eq(pos, POS_MIN)
		     : bkey_eq(pos, POS_MIN));
1948

1949
	if (ret && !(iter->flags & BTREE_ITER_IS_EXTENTS))
1950
		pos = bkey_predecessor(iter, pos);
1951
	bch2_btree_iter_set_pos(iter, pos);
1952
	return ret;
1953 1954
}

1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970
static noinline
void bch2_btree_trans_peek_prev_updates(struct btree_trans *trans, struct btree_iter *iter,
					struct bkey_s_c *k)
{
	struct bpos end = path_l(btree_iter_path(trans, iter))->b->data->min_key;

	trans_for_each_update(trans, i)
		if (!i->key_cache_already_flushed &&
		    i->btree_id == iter->btree_id &&
		    bpos_le(i->k->k.p, iter->pos) &&
		    bpos_ge(i->k->k.p, k->k ? k->k->p : end)) {
			iter->k = i->k->k;
			*k = bkey_i_to_s_c(i->k);
		}
}

1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987
static noinline
void bch2_btree_trans_peek_updates(struct btree_trans *trans, struct btree_iter *iter,
				   struct bkey_s_c *k)
{
	struct btree_path *path = btree_iter_path(trans, iter);
	struct bpos end = path_l(path)->b->key.k.p;

	trans_for_each_update(trans, i)
		if (!i->key_cache_already_flushed &&
		    i->btree_id == iter->btree_id &&
		    bpos_ge(i->k->k.p, path->pos) &&
		    bpos_le(i->k->k.p, k->k ? k->k->p : end)) {
			iter->k = i->k->k;
			*k = bkey_i_to_s_c(i->k);
		}
}

1988
static noinline
1989 1990
void bch2_btree_trans_peek_slot_updates(struct btree_trans *trans, struct btree_iter *iter,
					struct bkey_s_c *k)
1991
{
1992 1993 1994 1995 1996 1997 1998
	trans_for_each_update(trans, i)
		if (!i->key_cache_already_flushed &&
		    i->btree_id == iter->btree_id &&
		    bpos_eq(i->k->k.p, iter->pos)) {
			iter->k = i->k->k;
			*k = bkey_i_to_s_c(i->k);
		}
1999 2000
}

2001 2002 2003
static struct bkey_i *bch2_btree_journal_peek(struct btree_trans *trans,
					      struct btree_iter *iter,
					      struct bpos end_pos)
2004
{
2005 2006
	struct btree_path *path = btree_iter_path(trans, iter);

2007
	return bch2_journal_keys_peek_upto(trans->c, iter->btree_id,
2008 2009
					   path->level,
					   path->pos,
2010 2011
					   end_pos,
					   &iter->journal_idx);
2012 2013
}

2014 2015 2016 2017
static noinline
struct bkey_s_c btree_trans_peek_slot_journal(struct btree_trans *trans,
					      struct btree_iter *iter)
{
2018 2019
	struct btree_path *path = btree_iter_path(trans, iter);
	struct bkey_i *k = bch2_btree_journal_peek(trans, iter, path->pos);
2020

2021
	if (k) {
2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033
		iter->k = k->k;
		return bkey_i_to_s_c(k);
	} else {
		return bkey_s_c_null;
	}
}

static noinline
struct bkey_s_c btree_trans_peek_journal(struct btree_trans *trans,
					 struct btree_iter *iter,
					 struct bkey_s_c k)
{
2034
	struct btree_path *path = btree_iter_path(trans, iter);
2035
	struct bkey_i *next_journal =
2036
		bch2_btree_journal_peek(trans, iter,
2037
				k.k ? k.k->p : path_l(path)->b->key.k.p);
2038

2039
	if (next_journal) {
2040 2041 2042 2043 2044 2045 2046
		iter->k = next_journal->k;
		k = bkey_i_to_s_c(next_journal);
	}

	return k;
}

2047 2048 2049 2050 2051
/*
 * Checks btree key cache for key at iter->pos and returns it if present, or
 * bkey_s_c_null:
 */
static noinline
2052
struct bkey_s_c btree_trans_peek_key_cache(struct btree_iter *iter, struct bpos pos)
2053 2054 2055 2056
{
	struct btree_trans *trans = iter->trans;
	struct bch_fs *c = trans->c;
	struct bkey u;
2057
	struct bkey_s_c k;
2058 2059
	int ret;

2060 2061 2062 2063
	if ((iter->flags & BTREE_ITER_KEY_CACHE_FILL) &&
	    bpos_eq(iter->pos, pos))
		return bkey_s_c_null;

2064 2065 2066 2067
	if (!bch2_btree_key_cache_find(c, iter->btree_id, pos))
		return bkey_s_c_null;

	if (!iter->key_cache_path)
2068
		iter->key_cache_path = bch2_path_get(trans, iter->btree_id, pos,
2069
						     iter->flags & BTREE_ITER_INTENT, 0,
2070
						     iter->flags|BTREE_ITER_CACHED|
2071 2072
						     BTREE_ITER_CACHED_NOFILL,
						     _THIS_IP_);
2073

2074
	iter->key_cache_path = bch2_btree_path_set_pos(trans, iter->key_cache_path, pos,
2075 2076
					iter->flags & BTREE_ITER_INTENT,
					btree_iter_ip_allocated(iter));
2077

2078
	ret =   bch2_btree_path_traverse(trans, iter->key_cache_path,
2079
					 iter->flags|BTREE_ITER_CACHED) ?:
2080
		bch2_btree_path_relock(trans, btree_iter_path(trans, iter), _THIS_IP_);
2081 2082 2083
	if (unlikely(ret))
		return bkey_s_c_err(ret);

2084
	btree_path_set_should_be_locked(trans->paths + iter->key_cache_path);
2085

2086
	k = bch2_btree_path_peek_slot(trans->paths + iter->key_cache_path, &u);
2087 2088 2089 2090 2091
	if (k.k && !bkey_err(k)) {
		iter->k = u;
		k.k = &iter->k;
	}
	return k;
2092 2093
}

2094
static struct bkey_s_c __bch2_btree_iter_peek(struct btree_iter *iter, struct bpos search_key)
2095
{
Kent Overstreet's avatar
Kent Overstreet committed
2096
	struct btree_trans *trans = iter->trans;
2097
	struct bkey_s_c k, k2;
2098
	int ret;
2099

2100
	EBUG_ON(btree_iter_path(trans, iter)->cached);
2101
	bch2_btree_iter_verify(iter);
2102 2103

	while (1) {
2104 2105
		struct btree_path_level *l;

2106
		iter->path = bch2_btree_path_set_pos(trans, iter->path, search_key,
2107 2108
					iter->flags & BTREE_ITER_INTENT,
					btree_iter_ip_allocated(iter));
2109

2110
		ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
2111 2112 2113 2114 2115 2116
		if (unlikely(ret)) {
			/* ensure that iter->k is consistent with iter->pos: */
			bch2_btree_iter_set_pos(iter, iter->pos);
			k = bkey_s_c_err(ret);
			goto out;
		}
2117

2118 2119
		struct btree_path *path = btree_iter_path(trans, iter);
		l = path_l(path);
2120 2121 2122 2123 2124 2125 2126 2127

		if (unlikely(!l->b)) {
			/* No btree nodes at requested level: */
			bch2_btree_iter_set_pos(iter, SPOS_MAX);
			k = bkey_s_c_null;
			goto out;
		}

2128
		btree_path_set_should_be_locked(path);
2129

2130
		k = btree_path_level_peek_all(trans->c, l, &iter->k);
2131

2132 2133 2134
		if (unlikely(iter->flags & BTREE_ITER_WITH_KEY_CACHE) &&
		    k.k &&
		    (k2 = btree_trans_peek_key_cache(iter, k.k->p)).k) {
2135 2136
			k = k2;
			ret = bkey_err(k);
2137 2138 2139 2140 2141 2142
			if (ret) {
				bch2_btree_iter_set_pos(iter, iter->pos);
				goto out;
			}
		}

2143 2144 2145
		if (unlikely(iter->flags & BTREE_ITER_WITH_JOURNAL))
			k = btree_trans_peek_journal(trans, iter, k);

2146 2147 2148
		if (unlikely((iter->flags & BTREE_ITER_WITH_UPDATES) &&
			     trans->nr_updates))
			bch2_btree_trans_peek_updates(trans, iter, &k);
2149

2150 2151 2152 2153 2154 2155 2156 2157
		if (k.k && bkey_deleted(k.k)) {
			/*
			 * If we've got a whiteout, and it's after the search
			 * key, advance the search key to the whiteout instead
			 * of just after the whiteout - it might be a btree
			 * whiteout, with a real key at the same position, since
			 * in the btree deleted keys sort before non deleted.
			 */
2158
			search_key = !bpos_eq(search_key, k.k->p)
2159 2160 2161 2162 2163
				? k.k->p
				: bpos_successor(k.k->p);
			continue;
		}

2164
		if (likely(k.k)) {
2165
			break;
2166
		} else if (likely(!bpos_eq(l->b->key.k.p, SPOS_MAX))) {
2167
			/* Advance to next leaf node: */
2168
			search_key = bpos_successor(l->b->key.k.p);
2169 2170
		} else {
			/* End of btree: */
2171 2172 2173 2174
			bch2_btree_iter_set_pos(iter, SPOS_MAX);
			k = bkey_s_c_null;
			goto out;
		}
2175
	}
2176 2177 2178 2179 2180 2181 2182
out:
	bch2_btree_iter_verify(iter);

	return k;
}

/**
2183 2184 2185 2186 2187 2188
 * bch2_btree_iter_peek_upto() - returns first key greater than or equal to
 * iterator's current position
 * @iter:	iterator to peek from
 * @end:	search limit: returns keys less than or equal to @end
 *
 * Returns:	key if found, or an error extractable with bkey_err().
2189
 */
2190
struct bkey_s_c bch2_btree_iter_peek_upto(struct btree_iter *iter, struct bpos end)
2191 2192 2193 2194
{
	struct btree_trans *trans = iter->trans;
	struct bpos search_key = btree_iter_search_key(iter);
	struct bkey_s_c k;
2195
	struct bpos iter_pos;
2196 2197
	int ret;

2198
	EBUG_ON((iter->flags & BTREE_ITER_FILTER_SNAPSHOTS) && bkey_eq(end, POS_MAX));
2199

2200
	if (iter->update_path) {
2201
		bch2_path_put_nokeep(trans, iter->update_path,
2202
				     iter->flags & BTREE_ITER_INTENT);
2203
		iter->update_path = 0;
2204 2205
	}

2206 2207 2208 2209
	bch2_btree_iter_verify_entry_exit(iter);

	while (1) {
		k = __bch2_btree_iter_peek(iter, search_key);
2210 2211 2212
		if (unlikely(!k.k))
			goto end;
		if (unlikely(bkey_err(k)))
2213
			goto out_no_locked;
2214

2215
		/*
2216 2217 2218 2219 2220 2221 2222 2223
		 * We need to check against @end before FILTER_SNAPSHOTS because
		 * if we get to a different inode that requested we might be
		 * seeing keys for a different snapshot tree that will all be
		 * filtered out.
		 *
		 * But we can't do the full check here, because bkey_start_pos()
		 * isn't monotonically increasing before FILTER_SNAPSHOTS, and
		 * that's what we check against in extents mode:
2224
		 */
2225 2226 2227
		if (unlikely(!(iter->flags & BTREE_ITER_IS_EXTENTS)
			     ? bkey_gt(k.k->p, end)
			     : k.k->p.inode > end.inode))
2228
			goto end;
2229

2230
		if (iter->update_path &&
2231 2232
		    !bkey_eq(trans->paths[iter->update_path].pos, k.k->p)) {
			bch2_path_put_nokeep(trans, iter->update_path,
2233
					     iter->flags & BTREE_ITER_INTENT);
2234
			iter->update_path = 0;
2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253
		}

		if ((iter->flags & BTREE_ITER_FILTER_SNAPSHOTS) &&
		    (iter->flags & BTREE_ITER_INTENT) &&
		    !(iter->flags & BTREE_ITER_IS_EXTENTS) &&
		    !iter->update_path) {
			struct bpos pos = k.k->p;

			if (pos.snapshot < iter->snapshot) {
				search_key = bpos_successor(k.k->p);
				continue;
			}

			pos.snapshot = iter->snapshot;

			/*
			 * advance, same as on exit for iter->path, but only up
			 * to snapshot
			 */
2254
			__btree_path_get(trans->paths + iter->path, iter->flags & BTREE_ITER_INTENT);
2255 2256
			iter->update_path = iter->path;

2257 2258
			iter->update_path = bch2_btree_path_set_pos(trans,
						iter->update_path, pos,
2259 2260
						iter->flags & BTREE_ITER_INTENT,
						_THIS_IP_);
2261
			ret = bch2_btree_path_traverse(trans, iter->update_path, iter->flags);
2262 2263 2264 2265
			if (unlikely(ret)) {
				k = bkey_s_c_err(ret);
				goto out_no_locked;
			}
2266 2267
		}

2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285
		/*
		 * We can never have a key in a leaf node at POS_MAX, so
		 * we don't have to check these successor() calls:
		 */
		if ((iter->flags & BTREE_ITER_FILTER_SNAPSHOTS) &&
		    !bch2_snapshot_is_ancestor(trans->c,
					       iter->snapshot,
					       k.k->p.snapshot)) {
			search_key = bpos_successor(k.k->p);
			continue;
		}

		if (bkey_whiteout(k.k) &&
		    !(iter->flags & BTREE_ITER_ALL_SNAPSHOTS)) {
			search_key = bkey_successor(iter, k.k->p);
			continue;
		}

2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300
		/*
		 * iter->pos should be mononotically increasing, and always be
		 * equal to the key we just returned - except extents can
		 * straddle iter->pos:
		 */
		if (!(iter->flags & BTREE_ITER_IS_EXTENTS))
			iter_pos = k.k->p;
		else
			iter_pos = bkey_max(iter->pos, bkey_start_pos(k.k));

		if (unlikely(!(iter->flags & BTREE_ITER_IS_EXTENTS)
			     ? bkey_gt(iter_pos, end)
			     : bkey_ge(iter_pos, end)))
			goto end;

2301 2302 2303
		break;
	}

2304
	iter->pos = iter_pos;
2305

2306
	iter->path = bch2_btree_path_set_pos(trans, iter->path, k.k->p,
2307 2308
				iter->flags & BTREE_ITER_INTENT,
				btree_iter_ip_allocated(iter));
2309

2310
	btree_path_set_should_be_locked(btree_iter_path(trans, iter));
2311
out_no_locked:
2312
	if (iter->update_path) {
2313
		ret = bch2_btree_path_relock(trans, trans->paths + iter->update_path, _THIS_IP_);
2314
		if (unlikely(ret))
2315
			k = bkey_s_c_err(ret);
2316
		else
2317
			btree_path_set_should_be_locked(trans->paths + iter->update_path);
2318 2319
	}

2320
	if (!(iter->flags & BTREE_ITER_ALL_SNAPSHOTS))
2321 2322
		iter->pos.snapshot = iter->snapshot;

2323 2324 2325 2326 2327
	ret = bch2_btree_iter_verify_ret(iter, k);
	if (unlikely(ret)) {
		bch2_btree_iter_set_pos(iter, iter->pos);
		k = bkey_s_c_err(ret);
	}
Kent Overstreet's avatar
Kent Overstreet committed
2328

2329
	bch2_btree_iter_verify_entry_exit(iter);
2330

2331
	return k;
2332 2333 2334 2335
end:
	bch2_btree_iter_set_pos(iter, end);
	k = bkey_s_c_null;
	goto out_no_locked;
2336 2337
}

2338
/**
2339
 * bch2_btree_iter_next() - returns first key greater than iterator's current
2340
 * position
2341 2342 2343
 * @iter:	iterator to peek from
 *
 * Returns:	key if found, or an error extractable with bkey_err().
2344
 */
2345 2346
struct bkey_s_c bch2_btree_iter_next(struct btree_iter *iter)
{
2347
	if (!bch2_btree_iter_advance(iter))
2348
		return bkey_s_c_null;
2349

2350
	return bch2_btree_iter_peek(iter);
2351 2352
}

2353
/**
2354
 * bch2_btree_iter_peek_prev() - returns first key less than or equal to
2355
 * iterator's current position
2356 2357 2358
 * @iter:	iterator to peek from
 *
 * Returns:	key if found, or an error extractable with bkey_err().
2359 2360
 */
struct bkey_s_c bch2_btree_iter_peek_prev(struct btree_iter *iter)
2361
{
Kent Overstreet's avatar
Kent Overstreet committed
2362
	struct btree_trans *trans = iter->trans;
2363
	struct bpos search_key = iter->pos;
2364
	struct bkey_s_c k;
2365 2366
	struct bkey saved_k;
	const struct bch_val *saved_v;
2367
	btree_path_idx_t saved_path = 0;
2368 2369
	int ret;

2370 2371
	EBUG_ON(btree_iter_path(trans, iter)->cached ||
		btree_iter_path(trans, iter)->level);
2372 2373

	if (iter->flags & BTREE_ITER_WITH_JOURNAL)
2374
		return bkey_s_c_err(-BCH_ERR_btree_iter_with_journal_not_supported);
2375

2376 2377 2378
	bch2_btree_iter_verify(iter);
	bch2_btree_iter_verify_entry_exit(iter);

2379 2380 2381
	if (iter->flags & BTREE_ITER_FILTER_SNAPSHOTS)
		search_key.snapshot = U32_MAX;

2382
	while (1) {
2383
		iter->path = bch2_btree_path_set_pos(trans, iter->path, search_key,
2384 2385
						iter->flags & BTREE_ITER_INTENT,
						btree_iter_ip_allocated(iter));
2386

2387
		ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
2388
		if (unlikely(ret)) {
2389 2390
			/* ensure that iter->k is consistent with iter->pos: */
			bch2_btree_iter_set_pos(iter, iter->pos);
2391
			k = bkey_s_c_err(ret);
2392
			goto out_no_locked;
2393
		}
2394

2395 2396 2397
		struct btree_path *path = btree_iter_path(trans, iter);

		k = btree_path_level_peek(trans, path, &path->l[0], &iter->k);
2398 2399
		if (!k.k ||
		    ((iter->flags & BTREE_ITER_IS_EXTENTS)
2400 2401
		     ? bpos_ge(bkey_start_pos(k.k), search_key)
		     : bpos_gt(k.k->p, search_key)))
2402
			k = btree_path_level_prev(trans, path, &path->l[0], &iter->k);
2403

2404 2405 2406 2407
		if (unlikely((iter->flags & BTREE_ITER_WITH_UPDATES) &&
			     trans->nr_updates))
			bch2_btree_trans_peek_prev_updates(trans, iter, &k);

2408
		if (likely(k.k)) {
2409 2410 2411 2412 2413 2414 2415 2416 2417
			if (iter->flags & BTREE_ITER_FILTER_SNAPSHOTS) {
				if (k.k->p.snapshot == iter->snapshot)
					goto got_key;

				/*
				 * If we have a saved candidate, and we're no
				 * longer at the same _key_ (not pos), return
				 * that candidate
				 */
2418
				if (saved_path && !bkey_eq(k.k->p, saved_k.p)) {
2419
					bch2_path_put_nokeep(trans, iter->path,
2420
						      iter->flags & BTREE_ITER_INTENT);
2421 2422
					iter->path = saved_path;
					saved_path = 0;
2423 2424 2425 2426 2427
					iter->k	= saved_k;
					k.v	= saved_v;
					goto got_key;
				}

2428
				if (bch2_snapshot_is_ancestor(trans->c,
2429 2430 2431
							      iter->snapshot,
							      k.k->p.snapshot)) {
					if (saved_path)
2432
						bch2_path_put_nokeep(trans, saved_path,
2433
						      iter->flags & BTREE_ITER_INTENT);
2434
					saved_path = btree_path_clone(trans, iter->path,
2435
								iter->flags & BTREE_ITER_INTENT);
2436
					path = btree_iter_path(trans, iter);
2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452
					saved_k = *k.k;
					saved_v = k.v;
				}

				search_key = bpos_predecessor(k.k->p);
				continue;
			}
got_key:
			if (bkey_whiteout(k.k) &&
			    !(iter->flags & BTREE_ITER_ALL_SNAPSHOTS)) {
				search_key = bkey_predecessor(iter, k.k->p);
				if (iter->flags & BTREE_ITER_FILTER_SNAPSHOTS)
					search_key.snapshot = U32_MAX;
				continue;
			}

2453
			btree_path_set_should_be_locked(path);
2454
			break;
2455
		} else if (likely(!bpos_eq(path->l[0].b->data->min_key, POS_MIN))) {
2456
			/* Advance to previous leaf node: */
2457
			search_key = bpos_predecessor(path->l[0].b->data->min_key);
2458 2459
		} else {
			/* Start of btree: */
2460
			bch2_btree_iter_set_pos(iter, POS_MIN);
2461
			k = bkey_s_c_null;
2462
			goto out_no_locked;
2463
		}
2464
	}
2465

2466
	EBUG_ON(bkey_gt(bkey_start_pos(k.k), iter->pos));
2467 2468

	/* Extents can straddle iter->pos: */
2469
	if (bkey_lt(k.k->p, iter->pos))
2470
		iter->pos = k.k->p;
2471 2472 2473

	if (iter->flags & BTREE_ITER_FILTER_SNAPSHOTS)
		iter->pos.snapshot = iter->snapshot;
2474
out_no_locked:
2475
	if (saved_path)
2476
		bch2_path_put_nokeep(trans, saved_path, iter->flags & BTREE_ITER_INTENT);
Kent Overstreet's avatar
Kent Overstreet committed
2477

2478 2479
	bch2_btree_iter_verify_entry_exit(iter);
	bch2_btree_iter_verify(iter);
Kent Overstreet's avatar
Kent Overstreet committed
2480

2481 2482 2483
	return k;
}

2484
/**
2485
 * bch2_btree_iter_prev() - returns first key less than iterator's current
2486
 * position
2487 2488 2489
 * @iter:	iterator to peek from
 *
 * Returns:	key if found, or an error extractable with bkey_err().
2490 2491 2492
 */
struct bkey_s_c bch2_btree_iter_prev(struct btree_iter *iter)
{
2493
	if (!bch2_btree_iter_rewind(iter))
2494
		return bkey_s_c_null;
2495

2496
	return bch2_btree_iter_peek_prev(iter);
2497 2498
}

2499
struct bkey_s_c bch2_btree_iter_peek_slot(struct btree_iter *iter)
2500
{
2501
	struct btree_trans *trans = iter->trans;
2502
	struct bpos search_key;
2503
	struct bkey_s_c k;
2504 2505
	int ret;

2506 2507
	bch2_btree_iter_verify(iter);
	bch2_btree_iter_verify_entry_exit(iter);
2508
	EBUG_ON(btree_iter_path(trans, iter)->level && (iter->flags & BTREE_ITER_WITH_KEY_CACHE));
2509

2510 2511
	/* extents can't span inode numbers: */
	if ((iter->flags & BTREE_ITER_IS_EXTENTS) &&
2512
	    unlikely(iter->pos.offset == KEY_OFFSET_MAX)) {
2513 2514
		if (iter->pos.inode == KEY_INODE_MAX)
			return bkey_s_c_null;
2515

2516 2517
		bch2_btree_iter_set_pos(iter, bpos_nosnap_successor(iter->pos));
	}
2518

2519
	search_key = btree_iter_search_key(iter);
2520
	iter->path = bch2_btree_path_set_pos(trans, iter->path, search_key,
2521 2522
					iter->flags & BTREE_ITER_INTENT,
					btree_iter_ip_allocated(iter));
2523

2524
	ret = bch2_btree_path_traverse(trans, iter->path, iter->flags);
2525 2526 2527 2528
	if (unlikely(ret)) {
		k = bkey_s_c_err(ret);
		goto out_no_locked;
	}
2529

2530 2531
	if ((iter->flags & BTREE_ITER_CACHED) ||
	    !(iter->flags & (BTREE_ITER_IS_EXTENTS|BTREE_ITER_FILTER_SNAPSHOTS))) {
2532
		k = bkey_s_c_null;
2533

2534 2535 2536 2537 2538
		if (unlikely((iter->flags & BTREE_ITER_WITH_UPDATES) &&
			     trans->nr_updates)) {
			bch2_btree_trans_peek_slot_updates(trans, iter, &k);
			if (k.k)
				goto out;
2539 2540
		}

2541 2542 2543 2544
		if (unlikely(iter->flags & BTREE_ITER_WITH_JOURNAL) &&
		    (k = btree_trans_peek_slot_journal(trans, iter)).k)
			goto out;

2545
		if (unlikely(iter->flags & BTREE_ITER_WITH_KEY_CACHE) &&
2546
		    (k = btree_trans_peek_key_cache(iter, iter->pos)).k) {
2547
			if (!bkey_err(k))
2548
				iter->k = *k.k;
2549 2550
			/* We're not returning a key from iter->path: */
			goto out_no_locked;
2551 2552
		}

2553
		k = bch2_btree_path_peek_slot(trans->paths + iter->path, &iter->k);
2554 2555
		if (unlikely(!k.k))
			goto out_no_locked;
2556 2557
	} else {
		struct bpos next;
2558 2559 2560 2561
		struct bpos end = iter->pos;

		if (iter->flags & BTREE_ITER_IS_EXTENTS)
			end.offset = U64_MAX;
2562

2563
		EBUG_ON(btree_iter_path(trans, iter)->level);
2564

2565
		if (iter->flags & BTREE_ITER_INTENT) {
Kent Overstreet's avatar
Kent Overstreet committed
2566
			struct btree_iter iter2;
2567

Kent Overstreet's avatar
Kent Overstreet committed
2568
			bch2_trans_copy_iter(&iter2, iter);
2569
			k = bch2_btree_iter_peek_upto(&iter2, end);
2570

Kent Overstreet's avatar
Kent Overstreet committed
2571
			if (k.k && !bkey_err(k)) {
2572
				swap(iter->key_cache_path, iter2.key_cache_path);
Kent Overstreet's avatar
Kent Overstreet committed
2573 2574 2575 2576
				iter->k = iter2.k;
				k.k = &iter->k;
			}
			bch2_trans_iter_exit(trans, &iter2);
2577 2578 2579
		} else {
			struct bpos pos = iter->pos;

2580
			k = bch2_btree_iter_peek_upto(iter, end);
2581 2582 2583 2584
			if (unlikely(bkey_err(k)))
				bch2_btree_iter_set_pos(iter, pos);
			else
				iter->pos = pos;
2585
		}
2586 2587

		if (unlikely(bkey_err(k)))
2588
			goto out_no_locked;
2589 2590 2591

		next = k.k ? bkey_start_pos(k.k) : POS_MAX;

2592
		if (bkey_lt(iter->pos, next)) {
2593 2594
			bkey_init(&iter->k);
			iter->k.p = iter->pos;
2595 2596 2597 2598 2599 2600 2601 2602 2603 2604

			if (iter->flags & BTREE_ITER_IS_EXTENTS) {
				bch2_key_resize(&iter->k,
						min_t(u64, KEY_SIZE_MAX,
						      (next.inode == iter->pos.inode
						       ? next.offset
						       : KEY_OFFSET_MAX) -
						      iter->pos.offset));
				EBUG_ON(!iter->k.size);
			}
2605 2606 2607

			k = (struct bkey_s_c) { &iter->k, NULL };
		}
2608
	}
2609
out:
2610
	btree_path_set_should_be_locked(btree_iter_path(trans, iter));
2611
out_no_locked:
2612 2613
	bch2_btree_iter_verify_entry_exit(iter);
	bch2_btree_iter_verify(iter);
2614 2615 2616
	ret = bch2_btree_iter_verify_ret(iter, k);
	if (unlikely(ret))
		return bkey_s_c_err(ret);
2617

2618
	return k;
2619 2620 2621 2622
}

struct bkey_s_c bch2_btree_iter_next_slot(struct btree_iter *iter)
{
2623
	if (!bch2_btree_iter_advance(iter))
2624
		return bkey_s_c_null;
2625

2626
	return bch2_btree_iter_peek_slot(iter);
2627 2628
}

2629 2630
struct bkey_s_c bch2_btree_iter_prev_slot(struct btree_iter *iter)
{
2631
	if (!bch2_btree_iter_rewind(iter))
2632 2633 2634 2635 2636
		return bkey_s_c_null;

	return bch2_btree_iter_peek_slot(iter);
}

2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648
struct bkey_s_c bch2_btree_iter_peek_and_restart_outlined(struct btree_iter *iter)
{
	struct bkey_s_c k;

	while (btree_trans_too_many_iters(iter->trans) ||
	       (k = bch2_btree_iter_peek_type(iter, iter->flags),
		bch2_err_matches(bkey_err(k), BCH_ERR_transaction_restart)))
		bch2_trans_begin(iter->trans);

	return k;
}

2649 2650
/* new transactional stuff: */

2651 2652 2653
#ifdef CONFIG_BCACHEFS_DEBUG
static void btree_trans_verify_sorted_refs(struct btree_trans *trans)
{
Kent Overstreet's avatar
Kent Overstreet committed
2654
	struct btree_path *path;
2655 2656
	unsigned i;

2657
	BUG_ON(trans->nr_sorted != bitmap_weight(trans->paths_allocated, trans->nr_paths) - 1);
2658

2659
	trans_for_each_path(trans, path, i) {
Kent Overstreet's avatar
Kent Overstreet committed
2660
		BUG_ON(path->sorted_idx >= trans->nr_sorted);
2661
		BUG_ON(trans->sorted[path->sorted_idx] != i);
2662 2663 2664 2665 2666
	}

	for (i = 0; i < trans->nr_sorted; i++) {
		unsigned idx = trans->sorted[i];

2667
		BUG_ON(!test_bit(idx, trans->paths_allocated));
Kent Overstreet's avatar
Kent Overstreet committed
2668
		BUG_ON(trans->paths[idx].sorted_idx != i);
2669 2670 2671 2672 2673
	}
}

static void btree_trans_verify_sorted(struct btree_trans *trans)
{
Kent Overstreet's avatar
Kent Overstreet committed
2674
	struct btree_path *path, *prev = NULL;
2675
	struct trans_for_each_path_inorder_iter iter;
2676

2677 2678 2679
	if (!bch2_debug_check_iterators)
		return;

2680
	trans_for_each_path_inorder(trans, path, iter) {
2681
		if (prev && btree_path_cmp(prev, path) > 0) {
2682
			__bch2_dump_trans_paths_updates(trans, true);
2683 2684
			panic("trans paths out of order!\n");
		}
Kent Overstreet's avatar
Kent Overstreet committed
2685
		prev = path;
2686 2687
	}
}
2688 2689 2690 2691
#else
static inline void btree_trans_verify_sorted_refs(struct btree_trans *trans) {}
static inline void btree_trans_verify_sorted(struct btree_trans *trans) {}
#endif
2692

2693
void __bch2_btree_trans_sort_paths(struct btree_trans *trans)
2694 2695 2696 2697
{
	int i, l = 0, r = trans->nr_sorted, inc = 1;
	bool swapped;

2698 2699 2700 2701 2702
	btree_trans_verify_sorted_refs(trans);

	if (trans->paths_sorted)
		goto out;

2703 2704
	/*
	 * Cocktail shaker sort: this is efficient because iterators will be
2705
	 * mostly sorted.
2706 2707 2708 2709 2710 2711 2712
	 */
	do {
		swapped = false;

		for (i = inc > 0 ? l : r - 2;
		     i + 1 < r && i >= l;
		     i += inc) {
Kent Overstreet's avatar
Kent Overstreet committed
2713 2714
			if (btree_path_cmp(trans->paths + trans->sorted[i],
					   trans->paths + trans->sorted[i + 1]) > 0) {
2715
				swap(trans->sorted[i], trans->sorted[i + 1]);
Kent Overstreet's avatar
Kent Overstreet committed
2716 2717
				trans->paths[trans->sorted[i]].sorted_idx = i;
				trans->paths[trans->sorted[i + 1]].sorted_idx = i + 1;
2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728
				swapped = true;
			}
		}

		if (inc > 0)
			--r;
		else
			l++;
		inc = -inc;
	} while (swapped);

Kent Overstreet's avatar
Kent Overstreet committed
2729
	trans->paths_sorted = true;
2730
out:
2731 2732 2733
	btree_trans_verify_sorted(trans);
}

Kent Overstreet's avatar
Kent Overstreet committed
2734 2735
static inline void btree_path_list_remove(struct btree_trans *trans,
					  struct btree_path *path)
2736
{
Kent Overstreet's avatar
Kent Overstreet committed
2737
	EBUG_ON(path->sorted_idx >= trans->nr_sorted);
2738 2739
#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
	trans->nr_sorted--;
Kent Overstreet's avatar
Kent Overstreet committed
2740 2741
	memmove_u64s_down_small(trans->sorted + path->sorted_idx,
				trans->sorted + path->sorted_idx + 1,
2742 2743
				DIV_ROUND_UP(trans->nr_sorted - path->sorted_idx,
					     sizeof(u64) / sizeof(btree_path_idx_t)));
2744
#else
Kent Overstreet's avatar
Kent Overstreet committed
2745
	array_remove_item(trans->sorted, trans->nr_sorted, path->sorted_idx);
2746
#endif
2747
	for (unsigned i = path->sorted_idx; i < trans->nr_sorted; i++)
Kent Overstreet's avatar
Kent Overstreet committed
2748
		trans->paths[trans->sorted[i]].sorted_idx = i;
2749 2750
}

Kent Overstreet's avatar
Kent Overstreet committed
2751
static inline void btree_path_list_add(struct btree_trans *trans,
2752 2753
				       btree_path_idx_t pos,
				       btree_path_idx_t path_idx)
2754
{
2755
	struct btree_path *path = trans->paths + path_idx;
2756

2757
	path->sorted_idx = pos ? trans->paths[pos].sorted_idx + 1 : trans->nr_sorted;
2758 2759

#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
Kent Overstreet's avatar
Kent Overstreet committed
2760 2761
	memmove_u64s_up_small(trans->sorted + path->sorted_idx + 1,
			      trans->sorted + path->sorted_idx,
2762 2763
			      DIV_ROUND_UP(trans->nr_sorted - path->sorted_idx,
					   sizeof(u64) / sizeof(btree_path_idx_t)));
2764
	trans->nr_sorted++;
2765
	trans->sorted[path->sorted_idx] = path_idx;
2766
#else
2767
	array_insert_item(trans->sorted, trans->nr_sorted, path->sorted_idx, path_idx);
2768 2769
#endif

2770
	for (unsigned i = path->sorted_idx; i < trans->nr_sorted; i++)
Kent Overstreet's avatar
Kent Overstreet committed
2771
		trans->paths[trans->sorted[i]].sorted_idx = i;
2772

2773
	btree_trans_verify_sorted_refs(trans);
2774 2775
}

Kent Overstreet's avatar
Kent Overstreet committed
2776
void bch2_trans_iter_exit(struct btree_trans *trans, struct btree_iter *iter)
2777
{
2778
	if (iter->update_path)
2779
		bch2_path_put_nokeep(trans, iter->update_path,
2780
			      iter->flags & BTREE_ITER_INTENT);
2781
	if (iter->path)
2782
		bch2_path_put(trans, iter->path,
2783
			      iter->flags & BTREE_ITER_INTENT);
2784
	if (iter->key_cache_path)
2785
		bch2_path_put(trans, iter->key_cache_path,
2786
			      iter->flags & BTREE_ITER_INTENT);
2787 2788 2789 2790
	iter->path		= 0;
	iter->update_path	= 0;
	iter->key_cache_path	= 0;
	iter->trans		= NULL;
2791 2792
}

2793 2794 2795 2796 2797 2798
void bch2_trans_iter_init_outlined(struct btree_trans *trans,
			  struct btree_iter *iter,
			  enum btree_id btree_id, struct bpos pos,
			  unsigned flags)
{
	bch2_trans_iter_init_common(trans, iter, btree_id, pos, 0, 0,
2799 2800
			       bch2_btree_iter_flags(trans, btree_id, flags),
			       _RET_IP_);
2801 2802
}

Kent Overstreet's avatar
Kent Overstreet committed
2803 2804 2805 2806 2807 2808 2809
void bch2_trans_node_iter_init(struct btree_trans *trans,
			       struct btree_iter *iter,
			       enum btree_id btree_id,
			       struct bpos pos,
			       unsigned locks_want,
			       unsigned depth,
			       unsigned flags)
2810
{
2811
	flags |= BTREE_ITER_NOT_EXTENTS;
2812
	flags |= BTREE_ITER_SNAPSHOT_FIELD;
2813
	flags |= BTREE_ITER_ALL_SNAPSHOTS;
2814 2815

	bch2_trans_iter_init_common(trans, iter, btree_id, pos, locks_want, depth,
2816 2817
			       __bch2_btree_iter_flags(trans, btree_id, flags),
			       _RET_IP_);
2818 2819 2820

	iter->min_depth	= depth;

2821 2822 2823 2824
	struct btree_path *path = btree_iter_path(trans, iter);
	BUG_ON(path->locks_want	 < min(locks_want, BTREE_MAX_DEPTH));
	BUG_ON(path->level	!= depth);
	BUG_ON(iter->min_depth	!= depth);
Kent Overstreet's avatar
Kent Overstreet committed
2825
}
2826

Kent Overstreet's avatar
Kent Overstreet committed
2827 2828
void bch2_trans_copy_iter(struct btree_iter *dst, struct btree_iter *src)
{
2829 2830
	struct btree_trans *trans = src->trans;

Kent Overstreet's avatar
Kent Overstreet committed
2831
	*dst = *src;
2832 2833 2834
#ifdef TRACK_PATH_ALLOCATED
	dst->ip_allocated = _RET_IP_;
#endif
Kent Overstreet's avatar
Kent Overstreet committed
2835
	if (src->path)
2836
		__btree_path_get(trans->paths + src->path, src->flags & BTREE_ITER_INTENT);
2837
	if (src->update_path)
2838 2839
		__btree_path_get(trans->paths + src->update_path, src->flags & BTREE_ITER_INTENT);
	dst->key_cache_path = 0;
2840 2841
}

2842
void *__bch2_trans_kmalloc(struct btree_trans *trans, size_t size)
2843
{
2844
	struct bch_fs *c = trans->c;
2845
	unsigned new_top = trans->mem_top + size;
2846 2847
	unsigned old_bytes = trans->mem_bytes;
	unsigned new_bytes = roundup_pow_of_two(new_top);
2848
	int ret;
2849
	void *new_mem;
2850 2851
	void *p;

2852
	WARN_ON_ONCE(new_bytes > BTREE_TRANS_MEM_MAX);
2853

2854
	struct btree_transaction_stats *s = btree_trans_stats(trans);
2855
	s->max_mem = max(s->max_mem, new_bytes);
2856

2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881
	if (trans->used_mempool) {
		if (trans->mem_bytes >= new_bytes)
			goto out_change_top;

		/* No more space from mempool item, need malloc new one */
		new_mem = kmalloc(new_bytes, GFP_NOWAIT|__GFP_NOWARN);
		if (unlikely(!new_mem)) {
			bch2_trans_unlock(trans);

			new_mem = kmalloc(new_bytes, GFP_KERNEL);
			if (!new_mem)
				return ERR_PTR(-BCH_ERR_ENOMEM_trans_kmalloc);

			ret = bch2_trans_relock(trans);
			if (ret) {
				kfree(new_mem);
				return ERR_PTR(ret);
			}
		}
		memcpy(new_mem, trans->mem, trans->mem_top);
		trans->used_mempool = false;
		mempool_free(trans->mem, &c->btree_trans_mem_pool);
		goto out_new_mem;
	}

2882 2883 2884 2885 2886 2887
	new_mem = krealloc(trans->mem, new_bytes, GFP_NOWAIT|__GFP_NOWARN);
	if (unlikely(!new_mem)) {
		bch2_trans_unlock(trans);

		new_mem = krealloc(trans->mem, new_bytes, GFP_KERNEL);
		if (!new_mem && new_bytes <= BTREE_TRANS_MEM_MAX) {
2888
			new_mem = mempool_alloc(&c->btree_trans_mem_pool, GFP_KERNEL);
2889
			new_bytes = BTREE_TRANS_MEM_MAX;
2890 2891
			memcpy(new_mem, trans->mem, trans->mem_top);
			trans->used_mempool = true;
2892 2893
			kfree(trans->mem);
		}
2894

2895 2896 2897 2898 2899 2900 2901 2902 2903 2904
		if (!new_mem)
			return ERR_PTR(-BCH_ERR_ENOMEM_trans_kmalloc);

		trans->mem = new_mem;
		trans->mem_bytes = new_bytes;

		ret = bch2_trans_relock(trans);
		if (ret)
			return ERR_PTR(ret);
	}
2905
out_new_mem:
2906 2907
	trans->mem = new_mem;
	trans->mem_bytes = new_bytes;
2908

2909
	if (old_bytes) {
2910
		trace_and_count(c, trans_restart_mem_realloced, trans, _RET_IP_, new_bytes);
2911
		return ERR_PTR(btree_trans_restart(trans, BCH_ERR_transaction_restart_mem_realloced));
2912
	}
2913
out_change_top:
2914
	p = trans->mem + trans->mem_top;
2915
	trans->mem_top += size;
2916
	memset(p, 0, size);
2917
	return p;
2918 2919
}

2920 2921 2922 2923 2924 2925 2926
static inline void check_srcu_held_too_long(struct btree_trans *trans)
{
	WARN(trans->srcu_held && time_after(jiffies, trans->srcu_lock_time + HZ * 10),
	     "btree trans held srcu lock (delaying memory reclaim) for %lu seconds",
	     (jiffies - trans->srcu_lock_time) / HZ);
}

2927
void bch2_trans_srcu_unlock(struct btree_trans *trans)
2928
{
2929 2930 2931
	if (trans->srcu_held) {
		struct bch_fs *c = trans->c;
		struct btree_path *path;
2932
		unsigned i;
2933

2934
		trans_for_each_path(trans, path, i)
2935 2936
			if (path->cached && !btree_node_locked(path, 0))
				path->l[0].b = ERR_PTR(-BCH_ERR_no_btree_node_srcu_reset);
2937

2938
		check_srcu_held_too_long(trans);
2939 2940 2941 2942 2943
		srcu_read_unlock(&c->btree_trans_barrier, trans->srcu_idx);
		trans->srcu_held = false;
	}
}

2944
static void bch2_trans_srcu_lock(struct btree_trans *trans)
2945 2946 2947 2948 2949 2950
{
	if (!trans->srcu_held) {
		trans->srcu_idx = srcu_read_lock(&trans->c->btree_trans_barrier);
		trans->srcu_lock_time	= jiffies;
		trans->srcu_held = true;
	}
2951 2952
}

2953
/**
2954
 * bch2_trans_begin() - reset a transaction after a interrupted attempt
2955 2956
 * @trans: transaction to reset
 *
2957 2958
 * Returns:	current restart counter, to be used with trans_was_restarted()
 *
2959 2960 2961
 * While iterating over nodes or updating nodes a attempt to lock a btree node
 * may return BCH_ERR_transaction_restart when the trylock fails. When this
 * occurs bch2_trans_begin() should be called and the transaction retried.
2962
 */
2963
u32 bch2_trans_begin(struct btree_trans *trans)
2964
{
Kent Overstreet's avatar
Kent Overstreet committed
2965
	struct btree_path *path;
2966
	unsigned i;
2967
	u64 now;
2968

2969
	bch2_trans_reset_updates(trans);
2970

2971
	trans->restart_count++;
2972
	trans->mem_top			= 0;
2973
	trans->journal_entries		= NULL;
2974

2975
	trans_for_each_path(trans, path, i) {
2976 2977
		path->should_be_locked = false;

2978 2979 2980 2981 2982 2983 2984 2985
		/*
		 * If the transaction wasn't restarted, we're presuming to be
		 * doing something new: dont keep iterators excpt the ones that
		 * are in use - except for the subvolumes btree:
		 */
		if (!trans->restarted && path->btree_id != BTREE_ID_subvolumes)
			path->preserve = false;

Kent Overstreet's avatar
Kent Overstreet committed
2986 2987 2988 2989 2990 2991
		/*
		 * XXX: we probably shouldn't be doing this if the transaction
		 * was restarted, but currently we still overflow transaction
		 * iterators if we do that
		 */
		if (!path->ref && !path->preserve)
2992
			__bch2_path_free(trans, i);
Kent Overstreet's avatar
Kent Overstreet committed
2993
		else
2994
			path->preserve = false;
Kent Overstreet's avatar
Kent Overstreet committed
2995 2996
	}

2997
	now = local_clock();
2998 2999 3000 3001 3002 3003

	if (!IS_ENABLED(CONFIG_BCACHEFS_NO_LATENCY_ACCT) &&
	    time_after64(now, trans->last_begin_time + 10))
		__bch2_time_stats_update(&btree_trans_stats(trans)->duration,
					 trans->last_begin_time, now);

3004 3005
	if (!trans->restarted &&
	    (need_resched() ||
3006
	     time_after64(now, trans->last_begin_time + BTREE_TRANS_MAX_LOCK_HOLD_TIME_NS))) {
3007
		drop_locks_do(trans, (cond_resched(), 0));
3008
		now = local_clock();
3009
	}
3010
	trans->last_begin_time = now;
3011

3012 3013 3014
	if (unlikely(trans->srcu_held &&
		     time_after(jiffies, trans->srcu_lock_time + msecs_to_jiffies(10))))
		bch2_trans_srcu_unlock(trans);
3015

3016
	trans->last_begin_ip = _RET_IP_;
3017
	if (trans->restarted) {
Kent Overstreet's avatar
Kent Overstreet committed
3018
		bch2_btree_path_traverse_all(trans);
3019 3020
		trans->notrace_relock_fail = false;
	}
3021

3022 3023 3024
	return trans->restart_count;
}

3025
const char *bch2_btree_transaction_fns[BCH_TRANSACTIONS_NR] = { "(unknown)" };
3026 3027

unsigned bch2_trans_get_fn_idx(const char *fn)
3028
{
3029
	for (unsigned i = 0; i < ARRAY_SIZE(bch2_btree_transaction_fns); i++)
3030 3031 3032
		if (!bch2_btree_transaction_fns[i] ||
		    bch2_btree_transaction_fns[i] == fn) {
			bch2_btree_transaction_fns[i] = fn;
3033 3034 3035 3036
			return i;
		}

	pr_warn_once("BCH_TRANSACTIONS_NR not big enough!");
3037
	return 0;
3038 3039
}

3040
struct btree_trans *__bch2_trans_get(struct bch_fs *c, unsigned fn_idx)
3041
	__acquires(&c->btree_trans_barrier)
3042
{
3043
	struct btree_trans *trans;
3044

3045 3046 3047
	if (IS_ENABLED(__KERNEL__)) {
		trans = this_cpu_xchg(c->btree_trans_bufs->trans, NULL);
		if (trans) {
3048
			memset(trans, 0, offsetof(struct btree_trans, list));
3049 3050 3051
			goto got_trans;
		}
	}
3052

3053
	trans = mempool_alloc(&c->btree_trans_pool, GFP_NOFS);
3054
	memset(trans, 0, sizeof(*trans));
3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085
	closure_init_stack(&trans->ref);

	seqmutex_lock(&c->btree_trans_lock);
	if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG)) {
		struct btree_trans *pos;
		pid_t pid = current->pid;

		trans->locking_wait.task = current;

		list_for_each_entry(pos, &c->btree_trans_list, list) {
			struct task_struct *pos_task = READ_ONCE(pos->locking_wait.task);
			/*
			 * We'd much prefer to be stricter here and completely
			 * disallow multiple btree_trans in the same thread -
			 * but the data move path calls bch2_write when we
			 * already have a btree_trans initialized.
			 */
			BUG_ON(pos_task &&
			       pid == pos_task->pid &&
			       bch2_trans_locked(pos));

			if (pos_task && pid < pos_task->pid) {
				list_add_tail(&trans->list, &pos->list);
				goto list_add_done;
			}
		}
	}
	list_add_tail(&trans->list, &c->btree_trans_list);
list_add_done:
	seqmutex_unlock(&c->btree_trans_lock);
got_trans:
3086
	trans->c		= c;
3087
	trans->last_begin_time	= local_clock();
3088
	trans->fn_idx		= fn_idx;
3089
	trans->locking_wait.task = current;
3090
	trans->journal_replay_not_finished =
3091 3092
		unlikely(!test_bit(JOURNAL_REPLAY_DONE, &c->journal.flags)) &&
		atomic_inc_not_zero(&c->journal_keys.ref);
3093
	trans->nr_paths		= ARRAY_SIZE(trans->_paths);
3094 3095 3096
	trans->paths_allocated	= trans->_paths_allocated;
	trans->sorted		= trans->_sorted;
	trans->paths		= trans->_paths;
3097
	trans->updates		= trans->_updates;
3098

3099
	*trans_paths_nr(trans->paths) = BTREE_ITER_INITIAL;
3100

3101 3102
	trans->paths_allocated[0] = 1;

3103 3104
	if (fn_idx < BCH_TRANSACTIONS_NR) {
		trans->fn = bch2_btree_transaction_fns[fn_idx];
3105

3106
		struct btree_transaction_stats *s = &c->btree_transaction_stats[fn_idx];
3107

3108 3109 3110 3111 3112 3113
		if (s->max_mem) {
			unsigned expected_mem_bytes = roundup_pow_of_two(s->max_mem);

			trans->mem = kmalloc(expected_mem_bytes, GFP_KERNEL);
			if (likely(trans->mem))
				trans->mem_bytes = expected_mem_bytes;
3114
		}
3115

3116
		trans->nr_paths_max = s->nr_max_paths;
3117
		trans->journal_entries_size = s->journal_entries_size;
3118
	}
3119

3120
	trans->srcu_idx		= srcu_read_lock(&c->btree_trans_barrier);
3121
	trans->srcu_lock_time	= jiffies;
3122
	trans->srcu_held	= true;
3123
	return trans;
3124 3125
}

Kent Overstreet's avatar
Kent Overstreet committed
3126 3127 3128 3129 3130
static void check_btree_paths_leaked(struct btree_trans *trans)
{
#ifdef CONFIG_BCACHEFS_DEBUG
	struct bch_fs *c = trans->c;
	struct btree_path *path;
3131
	unsigned i;
Kent Overstreet's avatar
Kent Overstreet committed
3132

3133
	trans_for_each_path(trans, path, i)
Kent Overstreet's avatar
Kent Overstreet committed
3134 3135 3136 3137
		if (path->ref)
			goto leaked;
	return;
leaked:
3138
	bch_err(c, "btree paths leaked from %s!", trans->fn);
3139
	trans_for_each_path(trans, path, i)
Kent Overstreet's avatar
Kent Overstreet committed
3140 3141
		if (path->ref)
			printk(KERN_ERR "  btree %s %pS\n",
3142
			       bch2_btree_id_str(path->btree_id),
Kent Overstreet's avatar
Kent Overstreet committed
3143 3144 3145 3146 3147 3148
			       (void *) path->ip_allocated);
	/* Be noisy about this: */
	bch2_fatal_error(c);
#endif
}

3149
void bch2_trans_put(struct btree_trans *trans)
3150
	__releases(&c->btree_trans_barrier)
3151
{
3152 3153
	struct bch_fs *c = trans->c;

3154
	bch2_trans_unlock(trans);
3155

Kent Overstreet's avatar
Kent Overstreet committed
3156
	trans_for_each_update(trans, i)
3157
		__btree_path_put(trans->paths + i->path, true);
3158 3159
	trans->nr_updates	= 0;
	trans->locking_wait.task = NULL;
3160

Kent Overstreet's avatar
Kent Overstreet committed
3161
	check_btree_paths_leaked(trans);
3162

3163 3164
	if (trans->srcu_held) {
		check_srcu_held_too_long(trans);
3165
		srcu_read_unlock(&c->btree_trans_barrier, trans->srcu_idx);
3166
	}
3167

3168 3169 3170 3171
	if (trans->fs_usage_deltas) {
		if (trans->fs_usage_deltas->size + sizeof(trans->fs_usage_deltas) ==
		    REPLICAS_DELTA_LIST_MAX)
			mempool_free(trans->fs_usage_deltas,
Kent Overstreet's avatar
Kent Overstreet committed
3172
				     &c->replicas_delta_pool);
3173 3174 3175
		else
			kfree(trans->fs_usage_deltas);
	}
3176

3177 3178 3179
	if (unlikely(trans->journal_replay_not_finished))
		bch2_journal_keys_put(c);

3180 3181 3182 3183 3184
	unsigned long *paths_allocated = trans->paths_allocated;
	trans->paths_allocated	= NULL;
	trans->paths		= NULL;

	if (paths_allocated != trans->_paths_allocated)
3185
		kvfree_rcu_mightsleep(paths_allocated);
3186

3187
	if (trans->used_mempool)
Kent Overstreet's avatar
Kent Overstreet committed
3188
		mempool_free(trans->mem, &c->btree_trans_mem_pool);
3189 3190
	else
		kfree(trans->mem);
3191

3192 3193 3194
	/* Userspace doesn't have a real percpu implementation: */
	if (IS_ENABLED(__KERNEL__))
		trans = this_cpu_xchg(c->btree_trans_bufs->trans, trans);
3195 3196 3197 3198 3199 3200 3201 3202

	if (trans) {
		closure_sync(&trans->ref);

		seqmutex_lock(&c->btree_trans_lock);
		list_del(&trans->list);
		seqmutex_unlock(&c->btree_trans_lock);

3203
		mempool_free(trans, &c->btree_trans_pool);
3204
	}
3205
}
3206

3207
static void __maybe_unused
3208 3209
bch2_btree_bkey_cached_common_to_text(struct printbuf *out,
				      struct btree_bkey_cached_common *b)
3210
{
3211 3212 3213 3214 3215 3216
	struct six_lock_count c = six_lock_counts(&b->lock);
	struct task_struct *owner;
	pid_t pid;

	rcu_read_lock();
	owner = READ_ONCE(b->lock.owner);
3217
	pid = owner ? owner->pid : 0;
3218 3219
	rcu_read_unlock();

3220
	prt_printf(out, "\t%px %c l=%u %s:", b, b->cached ? 'c' : 'b',
3221
		   b->level, bch2_btree_id_str(b->btree_id));
3222
	bch2_bpos_to_text(out, btree_node_pos(b));
3223

3224
	prt_printf(out, "\t locks %u:%u:%u held by pid %u",
3225
		   c.n[0], c.n[1], c.n[2], pid);
3226 3227
}

3228
void bch2_btree_trans_to_text(struct printbuf *out, struct btree_trans *trans)
3229
{
3230
	struct btree_bkey_cached_common *b;
3231
	static char lock_types[] = { 'r', 'i', 'w' };
3232
	struct task_struct *task = READ_ONCE(trans->locking_wait.task);
3233
	unsigned l, idx;
3234

3235 3236 3237
	/* before rcu_read_lock(): */
	bch2_printbuf_make_room(out, 4096);

3238 3239 3240 3241 3242
	if (!out->nr_tabstops) {
		printbuf_tabstop_push(out, 16);
		printbuf_tabstop_push(out, 32);
	}

3243
	prt_printf(out, "%i %s\n", task ? task->pid : 0, trans->fn);
3244

3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256
	/* trans->paths is rcu protected vs. freeing */
	rcu_read_lock();
	out->atomic++;

	struct btree_path *paths = rcu_dereference(trans->paths);
	if (!paths)
		goto out;

	unsigned long *paths_allocated = trans_paths_allocated(paths);

	trans_for_each_path_idx_from(paths_allocated, *trans_paths_nr(paths), idx, 1) {
		struct btree_path *path = paths + idx;
3257 3258
		if (!path->nodes_locked)
			continue;
3259

3260
		prt_printf(out, "  path %u %c l=%u %s:",
3261
		       idx,
3262 3263
		       path->cached ? 'c' : 'b',
		       path->level,
3264
		       bch2_btree_id_str(path->btree_id));
3265
		bch2_bpos_to_text(out, path->pos);
3266
		prt_newline(out);
3267 3268

		for (l = 0; l < BTREE_MAX_DEPTH; l++) {
3269
			if (btree_node_locked(path, l) &&
3270
			    !IS_ERR_OR_NULL(b = (void *) READ_ONCE(path->l[l].b))) {
3271 3272
				prt_printf(out, "    %c l=%u ",
					   lock_types[btree_node_locked_type(path, l)], l);
3273 3274
				bch2_btree_bkey_cached_common_to_text(out, b);
				prt_newline(out);
3275 3276
			}
		}
3277
	}
3278

3279 3280
	b = READ_ONCE(trans->locking);
	if (b) {
3281 3282
		prt_printf(out, "  blocked for %lluus on\n",
			   div_u64(local_clock() - trans->locking_wait.start_time, 1000));
3283 3284 3285
		prt_printf(out, "    %c", lock_types[trans->locking_wait.lock_want]);
		bch2_btree_bkey_cached_common_to_text(out, b);
		prt_newline(out);
3286
	}
3287 3288 3289
out:
	--out->atomic;
	rcu_read_unlock();
3290 3291
}

3292 3293
void bch2_fs_btree_iter_exit(struct bch_fs *c)
{
3294
	struct btree_transaction_stats *s;
3295 3296 3297
	struct btree_trans *trans;
	int cpu;

3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313
	if (c->btree_trans_bufs)
		for_each_possible_cpu(cpu) {
			struct btree_trans *trans =
				per_cpu_ptr(c->btree_trans_bufs, cpu)->trans;

			if (trans) {
				closure_sync(&trans->ref);

				seqmutex_lock(&c->btree_trans_lock);
				list_del(&trans->list);
				seqmutex_unlock(&c->btree_trans_lock);
			}
			kfree(trans);
		}
	free_percpu(c->btree_trans_bufs);

3314 3315 3316 3317
	trans = list_first_entry_or_null(&c->btree_trans_list, struct btree_trans, list);
	if (trans)
		panic("%s leaked btree_trans\n", trans->fn);

3318 3319
	for (s = c->btree_transaction_stats;
	     s < c->btree_transaction_stats + ARRAY_SIZE(c->btree_transaction_stats);
3320 3321
	     s++) {
		kfree(s->max_paths_text);
3322
		bch2_time_stats_exit(&s->lock_hold_times);
3323
	}
3324

3325 3326
	if (c->btree_trans_barrier_initialized)
		cleanup_srcu_struct(&c->btree_trans_barrier);
3327
	mempool_exit(&c->btree_trans_mem_pool);
3328
	mempool_exit(&c->btree_trans_pool);
3329 3330
}

3331
void bch2_fs_btree_iter_init_early(struct bch_fs *c)
3332
{
3333
	struct btree_transaction_stats *s;
3334

3335 3336
	for (s = c->btree_transaction_stats;
	     s < c->btree_transaction_stats + ARRAY_SIZE(c->btree_transaction_stats);
3337
	     s++) {
3338
		bch2_time_stats_init(&s->duration);
3339
		bch2_time_stats_init(&s->lock_hold_times);
3340 3341
		mutex_init(&s->lock);
	}
3342

3343
	INIT_LIST_HEAD(&c->btree_trans_list);
3344
	seqmutex_init(&c->btree_trans_lock);
3345 3346 3347 3348 3349
}

int bch2_fs_btree_iter_init(struct bch_fs *c)
{
	int ret;
3350

3351 3352 3353 3354 3355 3356
	c->btree_trans_bufs = alloc_percpu(struct btree_trans_buf);
	if (!c->btree_trans_bufs)
		return -ENOMEM;

	ret   = mempool_init_kmalloc_pool(&c->btree_trans_pool, 1,
					  sizeof(struct btree_trans)) ?:
3357
		mempool_init_kmalloc_pool(&c->btree_trans_mem_pool, 1,
3358 3359 3360 3361 3362
					  BTREE_TRANS_MEM_MAX) ?:
		init_srcu_struct(&c->btree_trans_barrier);
	if (!ret)
		c->btree_trans_barrier_initialized = true;
	return ret;
3363
}