1 files changed, 72 insertions, 19 deletions

diff --git a/fs/bcachefs/btree_update_leaf.c b/fs/bcachefs/btree_update_leaf.c
index c0a84153ecda..d1b153805973 100644
--- a/fs/bcachefs/btree_update_leaf.c
+++ b/fs/bcachefs/btree_update_leaf.c
@@ -19,6 +19,26 @@
 #include <linux/sort.h>
 #include <trace/events/bcachefs.h>
 
+static inline bool same_leaf_as_prev(struct btree_trans *trans,
+				     unsigned sorted_idx)
+{
+	struct btree_insert_entry *i = trans->updates +
+		trans->updates_sorted[sorted_idx];
+	struct btree_insert_entry *prev = sorted_idx
+		? trans->updates + trans->updates_sorted[sorted_idx - 1]
+		: NULL;
+
+	return !i->deferred &&
+		prev &&
+		i->iter->l[0].b == prev->iter->l[0].b;
+}
+
+#define trans_for_each_update_sorted(_trans, _i, _iter)			\
+	for (iter = 0;							\
+	     _iter < _trans->nr_updates &&				\
+	     (_i = _trans->updates + _trans->updates_sorted[_iter], 1);	\
+	     _iter++)
+
 inline void bch2_btree_node_lock_for_insert(struct bch_fs *c, struct btree *b,
 					    struct btree_iter *iter)
 {
@@ -36,20 +56,21 @@ inline void bch2_btree_node_lock_for_insert(struct bch_fs *c, struct btree *b,
 		bch2_btree_init_next(c, b, iter);
 }
 
-static void btree_trans_lock_write(struct bch_fs *c, struct btree_trans *trans)
+static void btree_trans_lock_write(struct btree_trans *trans, bool lock)
 {
+	struct bch_fs *c = trans->c;
 	struct btree_insert_entry *i;
+	unsigned iter;
 
-	trans_for_each_update_leaf(trans, i)
-		bch2_btree_node_lock_for_insert(c, i->iter->l[0].b, i->iter);
-}
-
-static void btree_trans_unlock_write(struct btree_trans *trans)
-{
-	struct btree_insert_entry *i;
+	trans_for_each_update_sorted(trans, i, iter) {
+		if (same_leaf_as_prev(trans, iter))
+			continue;
 
-	trans_for_each_update_leaf(trans, i)
-		bch2_btree_node_unlock_write(i->iter->l[0].b, i->iter);
+		if (lock)
+			bch2_btree_node_lock_for_insert(c, i->iter->l[0].b, i->iter);
+		else
+			bch2_btree_node_unlock_write(i->iter->l[0].b, i->iter);
+	}
 }
 
 static inline int btree_trans_cmp(struct btree_insert_entry l,
@@ -59,6 +80,30 @@ static inline int btree_trans_cmp(struct btree_insert_entry l,
 		btree_iter_cmp(l.iter, r.iter);
 }
 
+static inline void btree_trans_sort_updates(struct btree_trans *trans)
+{
+	struct btree_insert_entry *l, *r;
+	unsigned nr = 0, pos;
+
+	trans_for_each_update(trans, l) {
+		for (pos = 0; pos < nr; pos++) {
+			r = trans->updates + trans->updates_sorted[pos];
+
+			if (btree_trans_cmp(*l, *r) <= 0)
+				break;
+		}
+
+		memmove(&trans->updates_sorted[pos + 1],
+			&trans->updates_sorted[pos],
+			(nr - pos) * sizeof(trans->updates_sorted[0]));
+
+		trans->updates_sorted[pos] = l - trans->updates;
+		nr++;
+	}
+
+	BUG_ON(nr != trans->nr_updates);
+}
+
 /* Inserting into a given leaf node (last stage of insert): */
 
 /* Handle overwrites and do insert, for non extents: */
@@ -488,12 +533,12 @@ static int btree_trans_check_can_insert(struct btree_trans *trans,
 					struct btree_insert_entry **stopped_at)
 {
 	struct btree_insert_entry *i;
-	unsigned u64s = 0;
+	unsigned iter, u64s = 0;
 	int ret;
 
-	trans_for_each_update_iter(trans, i) {
+	trans_for_each_update_sorted(trans, i, iter) {
 		/* Multiple inserts might go to same leaf: */
-		if (!same_leaf_as_prev(trans, i))
+		if (!same_leaf_as_prev(trans, iter))
 			u64s = 0;
 
 		u64s += i->k->k.u64s;
@@ -579,7 +624,13 @@ static inline int do_btree_insert_at(struct btree_trans *trans,
 		btree_insert_entry_checks(trans, i);
 	bch2_btree_trans_verify_locks(trans);
 
-	btree_trans_lock_write(c, trans);
+	/*
+	 * No more updates can be added - sort updates so we can take write
+	 * locks in the correct order:
+	 */
+	btree_trans_sort_updates(trans);
+
+	btree_trans_lock_write(trans, true);
 
 	if (race_fault()) {
 		ret = -EINTR;
@@ -597,8 +648,7 @@ static inline int do_btree_insert_at(struct btree_trans *trans,
 		goto out;
 
 	trans_for_each_update_iter(trans, i) {
-		if (i->deferred ||
-		    !btree_node_type_needs_gc(i->iter->btree_id))
+		if (!btree_node_type_needs_gc(i->iter->btree_id))
 			continue;
 
 		if (!fs_usage) {
@@ -664,7 +714,7 @@ out:
 	       (trans->flags & BTREE_INSERT_JOURNAL_RESERVED) &&
 	       trans->journal_res.ref);
 
-	btree_trans_unlock_write(trans);
+	btree_trans_lock_write(trans, false);
 
 	if (fs_usage) {
 		bch2_fs_usage_scratch_put(c, fs_usage);
@@ -816,6 +866,7 @@ static int __bch2_trans_commit(struct btree_trans *trans,
 {
 	struct bch_fs *c = trans->c;
 	struct btree_insert_entry *i;
+	unsigned iter;
 	int ret;
 
 	trans_for_each_update_iter(trans, i) {
@@ -837,8 +888,10 @@ static int __bch2_trans_commit(struct btree_trans *trans,
 	if (trans->flags & BTREE_INSERT_NOUNLOCK)
 		trans->nounlock = true;
 
-	trans_for_each_update_leaf(trans, i)
-		bch2_foreground_maybe_merge(c, i->iter, 0, trans->flags);
+	trans_for_each_update_sorted(trans, i, iter)
+		if (!same_leaf_as_prev(trans, iter))
+			bch2_foreground_maybe_merge(c, i->iter,
+						    0, trans->flags);
 
 	trans->nounlock = false;