X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=libbcachefs%2Fbtree_iter.h;h=f7a73619c85b2ff00680e10c95a952bcfebb7c7c;hb=d2a118d921dfdf43adfa37aed1d9df62925bda66;hp=c05b2dac1726d157cfdcb74eb8779ca02c8c36c4;hpb=133dfeb64843af65a018be770eb005363ca59bd9;p=bcachefs-tools-debian

diff --git a/libbcachefs/btree_iter.h b/libbcachefs/btree_iter.h
index c05b2da..f7a7361 100644
--- a/libbcachefs/btree_iter.h
+++ b/libbcachefs/btree_iter.h
@@ -1,8 +1,7 @@
+/* SPDX-License-Identifier: GPL-2.0 */
 #ifndef _BCACHEFS_BTREE_ITER_H
 #define _BCACHEFS_BTREE_ITER_H
 
-#include <linux/dynamic_fault.h>
-
 #include "bset.h"
 #include "btree_types.h"
 
@@ -18,10 +17,23 @@ static inline struct btree *btree_iter_node(struct btree_iter *iter,
 	return level < BTREE_MAX_DEPTH ? iter->l[level].b : NULL;
 }
 
+static inline bool btree_node_lock_seq_matches(const struct btree_iter *iter,
+					const struct btree *b, unsigned level)
+{
+	/*
+	 * We don't compare the low bits of the lock sequence numbers because
+	 * @iter might have taken a write lock on @b, and we don't want to skip
+	 * the linked iterator if the sequence numbers were equal before taking
+	 * that write lock. The lock sequence number is incremented by taking
+	 * and releasing write locks and is even when unlocked:
+	 */
+	return iter->l[level].lock_seq >> 1 == b->c.lock.state.seq >> 1;
+}
+
 static inline struct btree *btree_node_parent(struct btree_iter *iter,
 					      struct btree *b)
 {
-	return btree_iter_node(iter, b->level + 1);
+	return btree_iter_node(iter, b->c.level + 1);
 }
 
 static inline bool btree_trans_has_multiple_iters(const struct btree_trans *trans)
@@ -36,6 +48,11 @@ static inline int btree_iter_err(const struct btree_iter *iter)
 
 /* Iterate over iters within a transaction: */
 
+#define trans_for_each_iter_all(_trans, _iter)				\
+	for (_iter = (_trans)->iters;					\
+	     _iter < (_trans)->iters + (_trans)->nr_iters;		\
+	     _iter++)
+
 static inline struct btree_iter *
 __trans_next_iter(struct btree_trans *trans, unsigned idx)
 {
@@ -56,30 +73,20 @@ __trans_next_iter(struct btree_trans *trans, unsigned idx)
 static inline bool __iter_has_node(const struct btree_iter *iter,
 				   const struct btree *b)
 {
-	/*
-	 * We don't compare the low bits of the lock sequence numbers because
-	 * @iter might have taken a write lock on @b, and we don't want to skip
-	 * the linked iterator if the sequence numbers were equal before taking
-	 * that write lock. The lock sequence number is incremented by taking
-	 * and releasing write locks and is even when unlocked:
-	 */
-
-	return iter->l[b->level].b == b &&
-		iter->l[b->level].lock_seq >> 1 == b->lock.state.seq >> 1;
+	return iter->l[b->c.level].b == b &&
+		btree_node_lock_seq_matches(iter, b, b->c.level);
 }
 
 static inline struct btree_iter *
 __trans_next_iter_with_node(struct btree_trans *trans, struct btree *b,
 			    unsigned idx)
 {
-	EBUG_ON(idx < trans->nr_iters && trans->iters[idx].idx != idx);
+	struct btree_iter *iter = __trans_next_iter(trans, idx);
 
-	for (; idx < trans->nr_iters; idx++)
-		if ((trans->iters_linked & (1ULL << idx)) &&
-		    __iter_has_node(&trans->iters[idx], b))
-			return &trans->iters[idx];
+	while (iter && !__iter_has_node(iter, b))
+		iter = __trans_next_iter(trans, iter->idx + 1);
 
-	return NULL;
+	return iter;
 }
 
 #define trans_for_each_iter_with_node(_trans, _b, _iter)		\
@@ -89,34 +96,34 @@ __trans_next_iter_with_node(struct btree_trans *trans, struct btree *b,
 						 (_iter)->idx + 1))
 
 #ifdef CONFIG_BCACHEFS_DEBUG
-void bch2_btree_iter_verify(struct btree_iter *, struct btree *);
+void bch2_btree_trans_verify_iters(struct btree_trans *, struct btree *);
 void bch2_btree_trans_verify_locks(struct btree_trans *);
 #else
-static inline void bch2_btree_iter_verify(struct btree_iter *iter,
-					  struct btree *b) {}
+static inline void bch2_btree_trans_verify_iters(struct btree_trans *trans,
+						 struct btree *b) {}
 static inline void bch2_btree_trans_verify_locks(struct btree_trans *iter) {}
 #endif
 
+void bch2_btree_iter_fix_key_modified(struct btree_iter *, struct btree *,
+					   struct bkey_packed *);
 void bch2_btree_node_iter_fix(struct btree_iter *, struct btree *,
 			      struct btree_node_iter *, struct bkey_packed *,
 			      unsigned, unsigned);
 
-int bch2_btree_iter_unlock(struct btree_iter *);
-
-bool bch2_btree_trans_relock(struct btree_trans *);
-void bch2_btree_trans_unlock(struct btree_trans *);
+bool bch2_btree_iter_relock(struct btree_iter *, bool);
+bool bch2_trans_relock(struct btree_trans *);
+void bch2_trans_unlock(struct btree_trans *);
 
 bool __bch2_btree_iter_upgrade(struct btree_iter *, unsigned);
 bool __bch2_btree_iter_upgrade_nounlock(struct btree_iter *, unsigned);
 
 static inline bool bch2_btree_iter_upgrade(struct btree_iter *iter,
-					   unsigned new_locks_want,
-					   bool may_drop_locks)
+					   unsigned new_locks_want)
 {
 	new_locks_want = min(new_locks_want, BTREE_MAX_DEPTH);
 
 	return iter->locks_want < new_locks_want
-		? (may_drop_locks
+		? (!iter->trans->nounlock
 		   ? __bch2_btree_iter_upgrade(iter, new_locks_want)
 		   : __bch2_btree_iter_upgrade_nounlock(iter, new_locks_want))
 		: iter->uptodate <= BTREE_ITER_NEED_PEEK;
@@ -130,81 +137,67 @@ static inline void bch2_btree_iter_downgrade(struct btree_iter *iter)
 		__bch2_btree_iter_downgrade(iter, 0);
 }
 
+void bch2_trans_downgrade(struct btree_trans *);
+
 void bch2_btree_iter_node_replace(struct btree_iter *, struct btree *);
 void bch2_btree_iter_node_drop(struct btree_iter *, struct btree *);
 
 void bch2_btree_iter_reinit_node(struct btree_iter *, struct btree *);
 
-int __must_check bch2_btree_iter_traverse(struct btree_iter *);
+int __must_check __bch2_btree_iter_traverse(struct btree_iter *);
+
+static inline int __must_check
+bch2_btree_iter_traverse(struct btree_iter *iter)
+{
+	return iter->uptodate >= BTREE_ITER_NEED_RELOCK
+		? __bch2_btree_iter_traverse(iter)
+		: 0;
+}
+
 int bch2_btree_iter_traverse_all(struct btree_trans *);
 
 struct btree *bch2_btree_iter_peek_node(struct btree_iter *);
-struct btree *bch2_btree_iter_next_node(struct btree_iter *, unsigned);
+struct btree *bch2_btree_iter_next_node(struct btree_iter *);
 
 struct bkey_s_c bch2_btree_iter_peek(struct btree_iter *);
 struct bkey_s_c bch2_btree_iter_next(struct btree_iter *);
+
+struct bkey_s_c bch2_btree_iter_peek_with_updates(struct btree_iter *);
+struct bkey_s_c bch2_btree_iter_next_with_updates(struct btree_iter *);
+
+struct bkey_s_c bch2_btree_iter_peek_prev(struct btree_iter *);
 struct bkey_s_c bch2_btree_iter_prev(struct btree_iter *);
 
 struct bkey_s_c bch2_btree_iter_peek_slot(struct btree_iter *);
 struct bkey_s_c bch2_btree_iter_next_slot(struct btree_iter *);
 
+struct bkey_s_c bch2_btree_iter_peek_cached(struct btree_iter *);
+
 void bch2_btree_iter_set_pos_same_leaf(struct btree_iter *, struct bpos);
+void __bch2_btree_iter_set_pos(struct btree_iter *, struct bpos, bool);
 void bch2_btree_iter_set_pos(struct btree_iter *, struct bpos);
 
-static inline struct bpos btree_type_successor(enum btree_id id,
-					       struct bpos pos)
+/* Sort order for locking btree iterators: */
+static inline int btree_iter_lock_cmp(const struct btree_iter *l,
+				      const struct btree_iter *r)
 {
-	if (id == BTREE_ID_INODES) {
-		pos.inode++;
-		pos.offset = 0;
-	} else if (id != BTREE_ID_EXTENTS) {
-		pos = bkey_successor(pos);
-	}
-
-	return pos;
+	return   cmp_int(l->btree_id, r->btree_id) ?:
+		-cmp_int(btree_iter_is_cached(l), btree_iter_is_cached(r)) ?:
+		 bkey_cmp(l->pos, r->pos);
 }
 
-static inline struct bpos btree_type_predecessor(enum btree_id id,
-					       struct bpos pos)
-{
-	if (id == BTREE_ID_INODES) {
-		--pos.inode;
-		pos.offset = 0;
-	} else /* if (id != BTREE_ID_EXTENTS) */ {
-		pos = bkey_predecessor(pos);
-	}
-
-	return pos;
-}
-
-static inline int __btree_iter_cmp(enum btree_id id,
-				   struct bpos pos,
-				   const struct btree_iter *r)
-{
-	if (id != r->btree_id)
-		return id < r->btree_id ? -1 : 1;
-	return bkey_cmp(pos, r->pos);
-}
-
-static inline int btree_iter_cmp(const struct btree_iter *l,
-				 const struct btree_iter *r)
-{
-	return __btree_iter_cmp(l->btree_id, l->pos, r);
-}
-
-int bch2_trans_unlock(struct btree_trans *);
-
 /*
  * Unlocks before scheduling
  * Note: does not revalidate iterator
  */
-static inline void bch2_trans_cond_resched(struct btree_trans *trans)
+static inline int bch2_trans_cond_resched(struct btree_trans *trans)
 {
-	if (need_resched()) {
+	if (need_resched() || race_fault()) {
 		bch2_trans_unlock(trans);
 		schedule();
-	} else if (race_fault()) {
-		bch2_trans_unlock(trans);
+		return bch2_trans_relock(trans) ? 0 : -EINTR;
+	} else {
+		return 0;
 	}
 }
 
@@ -214,7 +207,7 @@ static inline void bch2_trans_cond_resched(struct btree_trans *trans)
 				_start, _locks_want, _depth, _flags),	\
 	     _b = bch2_btree_iter_peek_node(_iter);			\
 	     (_b);							\
-	     (_b) = bch2_btree_iter_next_node(_iter, _depth))
+	     (_b) = bch2_btree_iter_next_node(_iter))
 
 #define for_each_btree_node(_trans, _iter, _btree_id, _start,		\
 			    _flags, _b)					\
@@ -224,104 +217,99 @@ static inline void bch2_trans_cond_resched(struct btree_trans *trans)
 static inline struct bkey_s_c __bch2_btree_iter_peek(struct btree_iter *iter,
 						     unsigned flags)
 {
-	return flags & BTREE_ITER_SLOTS
-		? bch2_btree_iter_peek_slot(iter)
-		: bch2_btree_iter_peek(iter);
+	if ((flags & BTREE_ITER_TYPE) == BTREE_ITER_CACHED)
+		return bch2_btree_iter_peek_cached(iter);
+	else
+		return flags & BTREE_ITER_SLOTS
+			? bch2_btree_iter_peek_slot(iter)
+			: bch2_btree_iter_peek(iter);
 }
 
 static inline struct bkey_s_c __bch2_btree_iter_next(struct btree_iter *iter,
 						     unsigned flags)
 {
-	bch2_trans_cond_resched(iter->trans);
-
 	return flags & BTREE_ITER_SLOTS
 		? bch2_btree_iter_next_slot(iter)
 		: bch2_btree_iter_next(iter);
 }
 
-#define for_each_btree_key(_trans, _iter, _btree_id,  _start, _flags, _k)\
-	for (iter = bch2_trans_get_iter((_trans), (_btree_id),		\
-					(_start), (_flags)),		\
-	     (_k) = __bch2_btree_iter_peek(_iter, _flags);		\
-	     !IS_ERR_OR_NULL((_k).k);					\
-	     (_k) = __bch2_btree_iter_next(_iter, _flags))
-
-#define for_each_btree_key_continue(_iter, _flags, _k)			\
-	for ((_k) = __bch2_btree_iter_peek(_iter, _flags);		\
-	     !IS_ERR_OR_NULL((_k).k);					\
-	     (_k) = __bch2_btree_iter_next(_iter, _flags))
-
 static inline int bkey_err(struct bkey_s_c k)
 {
 	return PTR_ERR_OR_ZERO(k.k);
 }
 
+#define for_each_btree_key(_trans, _iter, _btree_id,			\
+			   _start, _flags, _k, _ret)			\
+	for ((_ret) = PTR_ERR_OR_ZERO((_iter) =				\
+			bch2_trans_get_iter((_trans), (_btree_id),	\
+					    (_start), (_flags))) ?:	\
+		      PTR_ERR_OR_ZERO(((_k) =				\
+			__bch2_btree_iter_peek(_iter, _flags)).k);	\
+	     !_ret && (_k).k;						\
+	     (_ret) = PTR_ERR_OR_ZERO(((_k) =				\
+			__bch2_btree_iter_next(_iter, _flags)).k))
+
+#define for_each_btree_key_continue(_iter, _flags, _k, _ret)		\
+	for ((_k) = __bch2_btree_iter_peek(_iter, _flags);		\
+	     !((_ret) = bkey_err(_k)) && (_k).k;			\
+	     (_k) = __bch2_btree_iter_next(_iter, _flags))
+
 /* new multiple iterator interface: */
 
-void bch2_trans_preload_iters(struct btree_trans *);
 int bch2_trans_iter_put(struct btree_trans *, struct btree_iter *);
 int bch2_trans_iter_free(struct btree_trans *, struct btree_iter *);
-int bch2_trans_iter_free_on_commit(struct btree_trans *, struct btree_iter *);
 
-void bch2_trans_unlink_iters(struct btree_trans *, u64);
+void bch2_trans_unlink_iters(struct btree_trans *);
 
 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 *);
+					 struct bpos, unsigned);
 
-static __always_inline u64 __btree_iter_id(void)
+static inline struct btree_iter *
+bch2_trans_get_iter(struct btree_trans *trans, enum btree_id btree_id,
+		    struct bpos pos, unsigned flags)
 {
-	u64 ret = 0;
+	struct btree_iter *iter =
+		__bch2_trans_get_iter(trans, btree_id, pos, flags);
 
-	ret <<= 32;
-	ret |= _RET_IP_ & U32_MAX;
-	ret <<= 32;
-	ret |= _THIS_IP_ & U32_MAX;
-	return ret;
+	if (!IS_ERR(iter))
+		iter->ip_allocated = _THIS_IP_;
+	return iter;
 }
 
-static __always_inline struct btree_iter *
-bch2_trans_get_iter(struct btree_trans *trans, enum btree_id btree_id,
-		    struct bpos pos, unsigned flags)
+struct btree_iter *__bch2_trans_copy_iter(struct btree_trans *,
+					struct btree_iter *);
+static inline struct btree_iter *
+bch2_trans_copy_iter(struct btree_trans *trans, struct btree_iter *src)
 {
-	return __bch2_trans_get_iter(trans, btree_id, pos, flags,
-				     __btree_iter_id());
+	struct btree_iter *iter =
+		__bch2_trans_copy_iter(trans, src);
+
+	if (!IS_ERR(iter))
+		iter->ip_allocated = _THIS_IP_;
+	return iter;
+
 }
 
 struct btree_iter *bch2_trans_get_node_iter(struct btree_trans *,
 				enum btree_id, struct bpos,
 				unsigned, unsigned, unsigned);
 
-void __bch2_trans_begin(struct btree_trans *);
+#define TRANS_RESET_NOTRAVERSE		(1 << 0)
+
+void bch2_trans_reset(struct btree_trans *, unsigned);
 
-static inline void bch2_trans_begin_updates(struct btree_trans *trans)
+static inline void bch2_trans_begin(struct btree_trans *trans)
 {
-	trans->nr_updates = 0;
+	return bch2_trans_reset(trans, 0);
 }
 
 void *bch2_trans_kmalloc(struct btree_trans *, size_t);
-void bch2_trans_init(struct btree_trans *, struct bch_fs *);
+void bch2_trans_init(struct btree_trans *, struct bch_fs *, unsigned, size_t);
 int bch2_trans_exit(struct btree_trans *);
 
-#ifdef TRACE_TRANSACTION_RESTARTS
-#define bch2_trans_begin(_trans)					\
-do {									\
-	if (is_power_of_2((_trans)->nr_restarts) &&			\
-	    (_trans)->nr_restarts >= 8)					\
-		pr_info("nr restarts: %zu", (_trans)->nr_restarts);	\
-									\
-	(_trans)->nr_restarts++;					\
-	__bch2_trans_begin(_trans);					\
-} while (0)
-#else
-#define bch2_trans_begin(_trans)	__bch2_trans_begin(_trans)
-#endif
+void bch2_btree_trans_to_text(struct printbuf *, struct bch_fs *);
 
-#ifdef TRACE_TRANSACTION_RESTARTS_ALL
-#define trans_restart(...) pr_info("transaction restart" __VA_ARGS__)
-#else
-#define trans_restart(...) no_printk("transaction restart" __VA_ARGS__)
-#endif
+void bch2_fs_btree_iter_exit(struct bch_fs *);
+int bch2_fs_btree_iter_init(struct bch_fs *);
 
 #endif /* _BCACHEFS_BTREE_ITER_H */