bcachefs: New transaction infrastructure

Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>

5 files changed, 428 insertions, 21 deletions

diff --git a/fs/bcachefs/btree_iter.c b/fs/bcachefs/btree_iter.c
index 8e7907aafd4d..c34d93747ec6 100644
--- a/fs/bcachefs/btree_iter.c
+++ b/fs/bcachefs/btree_iter.c
@@ -1555,6 +1555,7 @@ void bch2_btree_iter_unlink(struct btree_iter *iter)
 	for_each_linked_btree_iter(iter, linked)
 		if (linked->next == iter) {
 			linked->next = iter->next;
+			iter->next = iter;
 			return;
 		}
 
@@ -1571,8 +1572,9 @@ void bch2_btree_iter_link(struct btree_iter *iter, struct btree_iter *new)
 	if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG)) {
 		unsigned nr_iters = 0;
 
-		for_each_btree_iter(iter, new)
-			nr_iters++;
+		for_each_btree_iter(new, iter)
+			if (iter->btree_id == new->btree_id)
+				nr_iters++;
 
 		BUG_ON(nr_iters > SIX_LOCK_MAX_RECURSE);
 	}
@@ -1590,3 +1592,262 @@ void bch2_btree_iter_copy(struct btree_iter *dst, struct btree_iter *src)
 			six_lock_increment(&dst->l[i].b->lock,
 					   __btree_lock_want(dst, i));
 }
+
+/* new transactional stuff: */
+
+static void btree_trans_verify(struct btree_trans *trans)
+{
+	unsigned i;
+
+	for (i = 0; i < trans->nr_iters; i++) {
+		struct btree_iter *iter = &trans->iters[i];
+
+		BUG_ON(btree_iter_linked(iter) !=
+		       ((trans->iters_linked & (1 << i)) &&
+			!is_power_of_2(trans->iters_linked)));
+	}
+}
+
+void bch2_trans_iter_free(struct btree_trans *trans,
+			  struct btree_iter *iter)
+{
+	unsigned idx;
+
+	for (idx = 0; idx < trans->nr_iters; idx++)
+		if (&trans->iters[idx] == iter)
+			goto found;
+	BUG();
+found:
+	BUG_ON(!(trans->iters_linked & (1U << idx)));
+
+	trans->iters_live	&= ~(1U << idx);
+	trans->iters_linked	&= ~(1U << idx);
+	bch2_btree_iter_unlink(iter);
+}
+
+static int btree_trans_realloc_iters(struct btree_trans *trans)
+{
+	struct btree_iter *new_iters;
+	unsigned i;
+
+	bch2_trans_unlock(trans);
+
+	new_iters = kmalloc(sizeof(struct btree_iter) * BTREE_ITER_MAX,
+			    GFP_NOFS);
+	if (!new_iters)
+		return -ENOMEM;
+
+	memcpy(new_iters, trans->iters,
+	       sizeof(struct btree_iter) * trans->nr_iters);
+	trans->iters = new_iters;
+
+	for (i = 0; i < trans->nr_iters; i++)
+		trans->iters[i].next = &trans->iters[i];
+
+	if (trans->iters_linked) {
+		unsigned first_linked = __ffs(trans->iters_linked);
+
+		for (i = first_linked + 1; i < trans->nr_iters; i++)
+			if (trans->iters_linked & (1 << i))
+				bch2_btree_iter_link(&trans->iters[first_linked],
+						     &trans->iters[i]);
+	}
+
+	btree_trans_verify(trans);
+
+	return trans->iters_live ? -EINTR : 0;
+}
+
+int bch2_trans_preload_iters(struct btree_trans *trans)
+{
+	if (trans->iters != trans->iters_onstack)
+		return 0;
+
+	return btree_trans_realloc_iters(trans);
+}
+
+static struct btree_iter *__btree_trans_get_iter(struct btree_trans *trans,
+						 unsigned btree_id,
+						 unsigned flags, u64 iter_id)
+{
+	struct btree_iter *iter;
+	int idx;
+
+	BUG_ON(trans->nr_iters > BTREE_ITER_MAX);
+
+	for (idx = 0; idx < trans->nr_iters; idx++)
+		if (trans->iter_ids[idx] == iter_id)
+			goto found;
+	idx = -1;
+found:
+	if (idx < 0) {
+		idx = ffz(trans->iters_linked);
+		if (idx < trans->nr_iters)
+			goto got_slot;
+
+		BUG_ON(trans->nr_iters == BTREE_ITER_MAX);
+
+		if (trans->iters == trans->iters_onstack &&
+		    trans->nr_iters == ARRAY_SIZE(trans->iters_onstack)) {
+			int ret = btree_trans_realloc_iters(trans);
+			if (ret)
+				return ERR_PTR(ret);
+		}
+
+		idx = trans->nr_iters++;
+got_slot:
+		trans->iter_ids[idx] = iter_id;
+		iter = &trans->iters[idx];
+
+		bch2_btree_iter_init(iter, trans->c, btree_id, POS_MIN, flags);
+	} else {
+		iter = &trans->iters[idx];
+
+		BUG_ON(iter->btree_id != btree_id);
+		BUG_ON((iter->flags ^ flags) &
+		       (BTREE_ITER_SLOTS|BTREE_ITER_IS_EXTENTS));
+
+		iter->flags &= ~(BTREE_ITER_INTENT|BTREE_ITER_PREFETCH);
+		iter->flags |= flags & (BTREE_ITER_INTENT|BTREE_ITER_PREFETCH);
+	}
+
+	BUG_ON(trans->iters_live & (1 << idx));
+	trans->iters_live |= 1 << idx;
+
+	if (trans->iters_linked &&
+	    !(trans->iters_linked & (1 << idx)))
+		bch2_btree_iter_link(&trans->iters[__ffs(trans->iters_linked)],
+				     iter);
+
+	trans->iters_linked |= 1 << idx;
+
+	btree_trans_verify(trans);
+
+	return iter;
+}
+
+struct btree_iter *__bch2_trans_get_iter(struct btree_trans *trans,
+					 enum btree_id btree_id,
+					 struct bpos pos, unsigned flags,
+					 u64 iter_id)
+{
+	struct btree_iter *iter =
+		__btree_trans_get_iter(trans, btree_id, flags, iter_id);
+
+	if (!IS_ERR(iter))
+		bch2_btree_iter_set_pos(iter, pos);
+	return iter;
+}
+
+struct btree_iter *__bch2_trans_copy_iter(struct btree_trans *trans,
+					  struct btree_iter *src,
+					  u64 iter_id)
+{
+	struct btree_iter *iter =
+		__btree_trans_get_iter(trans, src->btree_id,
+				       src->flags, iter_id);
+
+	if (!IS_ERR(iter))
+		bch2_btree_iter_copy(iter, src);
+	return iter;
+}
+
+void *bch2_trans_kmalloc(struct btree_trans *trans,
+			 size_t size)
+{
+	void *ret;
+
+	if (trans->mem_top + size > trans->mem_bytes) {
+		size_t old_bytes = trans->mem_bytes;
+		size_t new_bytes = roundup_pow_of_two(trans->mem_top + size);
+		void *new_mem = krealloc(trans->mem, new_bytes, GFP_NOFS);
+
+		if (!new_mem)
+			return ERR_PTR(-ENOMEM);
+
+		trans->mem = new_mem;
+		trans->mem_bytes = new_bytes;
+
+		if (old_bytes)
+			return ERR_PTR(-EINTR);
+	}
+
+	ret = trans->mem + trans->mem_top;
+	trans->mem_top += size;
+	return ret;
+}
+
+int bch2_trans_unlock(struct btree_trans *trans)
+{
+	unsigned iters = trans->iters_linked;
+	int ret = 0;
+
+	while (iters) {
+		unsigned idx = __ffs(iters);
+		struct btree_iter *iter = &trans->iters[idx];
+
+		if (iter->flags & BTREE_ITER_ERROR)
+			ret = -EIO;
+
+		__bch2_btree_iter_unlock(iter);
+		iters ^= 1 << idx;
+	}
+
+	return ret;
+}
+
+void bch2_trans_begin(struct btree_trans *trans)
+{
+	unsigned idx;
+
+	btree_trans_verify(trans);
+
+	/*
+	 * On transaction restart, the transaction isn't required to allocate
+	 * all the same iterators it on the last iteration:
+	 *
+	 * Unlink any iterators it didn't use this iteration, assuming it got
+	 * further (allocated an iter with a higher idx) than where the iter
+	 * was originally allocated:
+	 */
+	if (!trans->iters_live)
+		return;
+
+	while (trans->iters_linked &&
+	       (idx = __fls(trans->iters_linked)) >
+	       __fls(trans->iters_live)) {
+		trans->iters_linked ^= 1 << idx;
+		bch2_btree_iter_unlink(&trans->iters[idx]);
+	}
+
+	trans->iters_live	= 0;
+	trans->nr_updates	= 0;
+	trans->mem_top		= 0;
+
+	btree_trans_verify(trans);
+}
+
+void bch2_trans_init(struct btree_trans *trans, struct bch_fs *c)
+{
+	trans->c		= c;
+	trans->nr_iters		= 0;
+	trans->iters_live	= 0;
+	trans->iters_linked	= 0;
+	trans->nr_updates	= 0;
+	trans->mem_top		= 0;
+	trans->mem_bytes	= 0;
+	trans->mem		= NULL;
+	trans->iters		= trans->iters_onstack;
+}
+
+int bch2_trans_exit(struct btree_trans *trans)
+{
+	int ret = bch2_trans_unlock(trans);
+
+	kfree(trans->mem);
+	if (trans->iters != trans->iters_onstack)
+		kfree(trans->iters);
+	trans->mem	= (void *) 0x1;
+	trans->iters	= (void *) 0x1;
+	return ret;
+}
diff --git a/fs/bcachefs/btree_iter.h b/fs/bcachefs/btree_iter.h
index 5db1cc581f56..02ec6d59a10e 100644
--- a/fs/bcachefs/btree_iter.h
+++ b/fs/bcachefs/btree_iter.h
@@ -269,4 +269,47 @@ static inline int btree_iter_err(struct bkey_s_c k)
 	return PTR_ERR_OR_ZERO(k.k);
 }
 
+/* new multiple iterator interface: */
+
+int bch2_trans_preload_iters(struct btree_trans *);
+void bch2_trans_iter_free(struct btree_trans *,
+				struct btree_iter *);
+
+struct btree_iter *__bch2_trans_get_iter(struct btree_trans *, enum btree_id,
+					 struct bpos, unsigned, u64);
+struct btree_iter *__bch2_trans_copy_iter(struct btree_trans *,
+					  struct btree_iter *, u64);
+
+static __always_inline u64 __btree_iter_id(void)
+{
+	u64 ret = 0;
+
+	ret <<= 32;
+	ret |= _RET_IP_ & U32_MAX;
+	ret <<= 32;
+	ret |= _THIS_IP_ & U32_MAX;
+	return ret;
+}
+
+static __always_inline struct btree_iter *
+bch2_trans_get_iter(struct btree_trans *trans, enum btree_id btree_id,
+		    struct bpos pos, unsigned flags)
+{
+	return __bch2_trans_get_iter(trans, btree_id, pos, flags,
+				     __btree_iter_id());
+}
+
+static __always_inline struct btree_iter *
+bch2_trans_copy_iter(struct btree_trans *trans, struct btree_iter *src)
+{
+
+	return __bch2_trans_copy_iter(trans, src, __btree_iter_id());
+}
+
+void *bch2_trans_kmalloc(struct btree_trans *, size_t);
+int bch2_trans_unlock(struct btree_trans *);
+void bch2_trans_begin(struct btree_trans *);
+void bch2_trans_init(struct btree_trans *, struct bch_fs *);
+int bch2_trans_exit(struct btree_trans *);
+
 #endif /* _BCACHEFS_BTREE_ITER_H */
diff --git a/fs/bcachefs/btree_types.h b/fs/bcachefs/btree_types.h
index daa648c639d3..ebe71de39705 100644
--- a/fs/bcachefs/btree_types.h
+++ b/fs/bcachefs/btree_types.h
@@ -253,6 +253,39 @@ struct btree_iter {
 	struct btree_iter	*next;
 };
 
+#define BTREE_ITER_MAX		8
+
+struct btree_insert_entry {
+	struct btree_iter *iter;
+	struct bkey_i	*k;
+	unsigned	extra_res;
+	/*
+	 * true if entire key was inserted - can only be false for
+	 * extents
+	 */
+	bool		done;
+};
+
+struct btree_trans {
+	struct bch_fs		*c;
+
+	u8			nr_iters;
+	u8			iters_live;
+	u8			iters_linked;
+	u8			nr_updates;
+
+	unsigned		mem_top;
+	unsigned		mem_bytes;
+	void			*mem;
+
+	struct btree_iter	*iters;
+	u64			iter_ids[BTREE_ITER_MAX];
+
+	struct btree_insert_entry updates[BTREE_ITER_MAX];
+
+	struct btree_iter	iters_onstack[2];
+};
+
 #define BTREE_FLAG(flag)						\
 static inline bool btree_node_ ## flag(struct btree *b)			\
 {	return test_bit(BTREE_NODE_ ## flag, &b->flags); }		\
diff --git a/fs/bcachefs/btree_update.h b/fs/bcachefs/btree_update.h
index aac97958cc3b..5e47d4cd7c48 100644
--- a/fs/bcachefs/btree_update.h
+++ b/fs/bcachefs/btree_update.h
@@ -27,16 +27,7 @@ struct btree_insert {
 	bool			did_work;
 
 	unsigned short		nr;
-	struct btree_insert_entry {
-		struct btree_iter *iter;
-		struct bkey_i	*k;
-		unsigned	extra_res;
-		/*
-		 * true if entire key was inserted - can only be false for
-		 * extents
-		 */
-		bool		done;
-	}			*entries;
+	struct btree_insert_entry  *entries;
 };
 
 int __bch2_btree_insert_at(struct btree_insert *);
@@ -149,4 +140,31 @@ int bch2_btree_node_rewrite(struct bch_fs *c, struct btree_iter *,
 int bch2_btree_node_update_key(struct bch_fs *, struct btree_iter *,
 			       struct btree *, struct bkey_i_extent *);
 
+/* new transactional interface: */
+
+void bch2_trans_update(struct btree_trans *, struct btree_iter *,
+			     struct bkey_i *, unsigned);
+int bch2_trans_commit(struct btree_trans *,
+		      struct disk_reservation *,
+		      struct extent_insert_hook *,
+		      u64 *, unsigned);
+
+#define bch2_trans_do(_c, _journal_seq, _flags, _do)			\
+({									\
+	struct btree_trans trans;					\
+	int _ret;							\
+									\
+	bch2_trans_init(&trans, (_c));					\
+									\
+	do {								\
+		bch2_trans_begin(&trans);				\
+									\
+		_ret = (_do) ?:	bch2_trans_commit(&trans, NULL, NULL,	\
+					(_journal_seq), (_flags));	\
+	} while (_ret == -EINTR);					\
+									\
+	bch2_trans_exit(&trans);					\
+	_ret;								\
+})
+
 #endif /* _BCACHEFS_BTREE_UPDATE_H */
diff --git a/fs/bcachefs/btree_update_leaf.c b/fs/bcachefs/btree_update_leaf.c
index 588a1997e5ee..3ee6beb3c771 100644
--- a/fs/bcachefs/btree_update_leaf.c
+++ b/fs/bcachefs/btree_update_leaf.c
@@ -309,8 +309,10 @@ static inline int do_btree_insert_at(struct btree_insert *trans,
 	unsigned u64s;
 	int ret;
 
-	trans_for_each_entry(trans, i)
+	trans_for_each_entry(trans, i) {
 		BUG_ON(i->done);
+		BUG_ON(i->iter->uptodate >= BTREE_ITER_NEED_RELOCK);
+	}
 
 	u64s = 0;
 	trans_for_each_entry(trans, i)
@@ -398,6 +400,17 @@ out:
 	return ret;
 }
 
+static inline void btree_insert_entry_checks(struct bch_fs *c,
+					     struct btree_insert_entry *i)
+{
+	BUG_ON(i->iter->level);
+	BUG_ON(bkey_cmp(bkey_start_pos(&i->k->k), i->iter->pos));
+	BUG_ON(debug_check_bkeys(c) &&
+	       !bkey_deleted(&i->k->k) &&
+	       bch2_bkey_invalid(c, i->iter->btree_id,
+				 bkey_i_to_s_c(i->k)));
+}
+
 /**
  * __bch_btree_insert_at - insert keys at given iterator positions
  *
@@ -418,20 +431,16 @@ int __bch2_btree_insert_at(struct btree_insert *trans)
 	unsigned flags;
 	int ret;
 
+	BUG_ON(!trans->nr);
+
 	for_each_btree_iter(trans->entries[0].iter, linked)
 		bch2_btree_iter_verify_locks(linked);
 
 	/* for the sake of sanity: */
 	BUG_ON(trans->nr > 1 && !(trans->flags & BTREE_INSERT_ATOMIC));
 
-	trans_for_each_entry(trans, i) {
-		BUG_ON(i->iter->level);
-		BUG_ON(bkey_cmp(bkey_start_pos(&i->k->k), i->iter->pos));
-		BUG_ON(debug_check_bkeys(c) &&
-		       !bkey_deleted(&i->k->k) &&
-		       bch2_bkey_invalid(c, i->iter->btree_id,
-					 bkey_i_to_s_c(i->k)));
-	}
+	trans_for_each_entry(trans, i)
+		btree_insert_entry_checks(c, i);
 
 	bubble_sort(trans->entries, trans->nr, btree_trans_cmp);
 
@@ -555,6 +564,49 @@ err:
 	goto out;
 }
 
+void bch2_trans_update(struct btree_trans *trans,
+		       struct btree_iter *iter,
+		       struct bkey_i *k,
+		       unsigned extra_journal_res)
+{
+	struct btree_insert_entry *i;
+
+	BUG_ON(trans->nr_updates >= ARRAY_SIZE(trans->updates));
+
+	i = &trans->updates[trans->nr_updates++];
+
+	*i = (struct btree_insert_entry) {
+		.iter	= iter,
+		.k		= k,
+		.extra_res	= extra_journal_res,
+	};
+
+	btree_insert_entry_checks(trans->c, i);
+}
+
+int bch2_trans_commit(struct btree_trans *trans,
+		      struct disk_reservation *disk_res,
+		      struct extent_insert_hook *hook,
+		      u64 *journal_seq,
+		      unsigned flags)
+{
+	struct btree_insert insert = {
+		.c		= trans->c,
+		.disk_res	= disk_res,
+		.journal_seq	= journal_seq,
+		.flags		= flags,
+		.nr		= trans->nr_updates,
+		.entries	= trans->updates,
+	};
+
+	if (!trans->nr_updates)
+		return 0;
+
+	trans->nr_updates = 0;
+
+	return __bch2_btree_insert_at(&insert);
+}
+
 int bch2_btree_delete_at(struct btree_iter *iter, unsigned flags)
 {
 	struct bkey_i k;