summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--fs/bcachefs/btree_iter.c41
-rw-r--r--fs/bcachefs/btree_iter.h3
-rw-r--r--fs/bcachefs/btree_types.h2
-rw-r--r--fs/bcachefs/btree_update.h16
-rw-r--r--fs/bcachefs/btree_update_leaf.c91
-rw-r--r--fs/bcachefs/super.c7
6 files changed, 112 insertions, 48 deletions
diff --git a/fs/bcachefs/btree_iter.c b/fs/bcachefs/btree_iter.c
index a28d2dd7d5b3..67404e505c68 100644
--- a/fs/bcachefs/btree_iter.c
+++ b/fs/bcachefs/btree_iter.c
@@ -1671,7 +1671,10 @@ int bch2_trans_iter_free_on_commit(struct btree_trans *trans,
static int bch2_trans_realloc_iters(struct btree_trans *trans,
unsigned new_size)
{
- void *new_iters, *new_updates;
+ void *new_iters, *new_updates, *new_sorted;
+ size_t iters_bytes;
+ size_t updates_bytes;
+ size_t sorted_bytes;
new_size = roundup_pow_of_two(new_size);
@@ -1684,9 +1687,13 @@ static int bch2_trans_realloc_iters(struct btree_trans *trans,
bch2_trans_unlock(trans);
- new_iters = kmalloc(sizeof(struct btree_iter) * new_size +
- sizeof(struct btree_insert_entry) * (new_size + 4),
- GFP_NOFS);
+ iters_bytes = sizeof(struct btree_iter) * new_size;
+ updates_bytes = sizeof(struct btree_insert_entry) * (new_size + 4);
+ sorted_bytes = sizeof(u8) * (new_size + 4);
+
+ new_iters = kmalloc(iters_bytes +
+ updates_bytes +
+ sorted_bytes, GFP_NOFS);
if (new_iters)
goto success;
@@ -1695,7 +1702,8 @@ static int bch2_trans_realloc_iters(struct btree_trans *trans,
trans->used_mempool = true;
success:
- new_updates = new_iters + sizeof(struct btree_iter) * new_size;
+ new_updates = new_iters + iters_bytes;
+ new_sorted = new_updates + updates_bytes;
memcpy(new_iters, trans->iters,
sizeof(struct btree_iter) * trans->nr_iters);
@@ -1710,9 +1718,10 @@ success:
if (trans->iters != trans->iters_onstack)
kfree(trans->iters);
- trans->iters = new_iters;
- trans->updates = new_updates;
- trans->size = new_size;
+ trans->iters = new_iters;
+ trans->updates = new_updates;
+ trans->updates_sorted = new_sorted;
+ trans->size = new_size;
if (trans->iters_live) {
trace_trans_restart_iters_realloced(trans->ip, trans->size);
@@ -1957,6 +1966,7 @@ void bch2_trans_init(struct btree_trans *trans, struct bch_fs *c,
trans->size = ARRAY_SIZE(trans->iters_onstack);
trans->iters = trans->iters_onstack;
trans->updates = trans->updates_onstack;
+ trans->updates_sorted = trans->updates_sorted_onstack;
trans->fs_usage_deltas = NULL;
if (expected_nr_iters > trans->size)
@@ -1981,3 +1991,18 @@ int bch2_trans_exit(struct btree_trans *trans)
return trans->error ? -EIO : 0;
}
+
+void bch2_fs_btree_iter_exit(struct bch_fs *c)
+{
+ mempool_exit(&c->btree_iters_pool);
+}
+
+int bch2_fs_btree_iter_init(struct bch_fs *c)
+{
+ unsigned nr = BTREE_ITER_MAX;
+
+ return mempool_init_kmalloc_pool(&c->btree_iters_pool, 1,
+ sizeof(struct btree_iter) * nr +
+ sizeof(struct btree_insert_entry) * (nr + 4) +
+ sizeof(u8) * (nr + 4));
+}
diff --git a/fs/bcachefs/btree_iter.h b/fs/bcachefs/btree_iter.h
index 249df21b9a97..9de84ae79481 100644
--- a/fs/bcachefs/btree_iter.h
+++ b/fs/bcachefs/btree_iter.h
@@ -303,4 +303,7 @@ void *bch2_trans_kmalloc(struct btree_trans *, size_t);
void bch2_trans_init(struct btree_trans *, struct bch_fs *, unsigned, size_t);
int bch2_trans_exit(struct btree_trans *);
+void bch2_fs_btree_iter_exit(struct bch_fs *);
+int bch2_fs_btree_iter_init(struct bch_fs *);
+
#endif /* _BCACHEFS_BTREE_ITER_H */
diff --git a/fs/bcachefs/btree_types.h b/fs/bcachefs/btree_types.h
index f4e1bfe129a0..431a29f61e25 100644
--- a/fs/bcachefs/btree_types.h
+++ b/fs/bcachefs/btree_types.h
@@ -291,6 +291,7 @@ struct btree_trans {
struct btree_iter *iters;
struct btree_insert_entry *updates;
+ u8 *updates_sorted;
/* update path: */
struct journal_res journal_res;
@@ -302,6 +303,7 @@ struct btree_trans {
struct btree_iter iters_onstack[2];
struct btree_insert_entry updates_onstack[6];
+ u8 updates_sorted_onstack[6];
struct replicas_delta_list *fs_usage_deltas;
};
diff --git a/fs/bcachefs/btree_update.h b/fs/bcachefs/btree_update.h
index 08c17477e76c..09ee501ca329 100644
--- a/fs/bcachefs/btree_update.h
+++ b/fs/bcachefs/btree_update.h
@@ -140,18 +140,6 @@ struct btree_insert_entry *bch2_trans_update(struct btree_trans *,
_ret; \
})
-/*
- * We sort transaction entries so that if multiple iterators point to the same
- * leaf node they'll be adjacent:
- */
-static inline bool same_leaf_as_prev(struct btree_trans *trans,
- struct btree_insert_entry *i)
-{
- return i != trans->updates &&
- !i->deferred &&
- i[0].iter->l[0].b == i[-1].iter->l[0].b;
-}
-
#define __trans_next_update(_trans, _i, _filter) \
({ \
while ((_i) < (_trans)->updates + (_trans->nr_updates) && !(_filter))\
@@ -171,8 +159,4 @@ static inline bool same_leaf_as_prev(struct btree_trans *trans,
#define trans_for_each_update_iter(trans, i) \
__trans_for_each_update(trans, i, !(i)->deferred)
-#define trans_for_each_update_leaf(trans, i) \
- __trans_for_each_update(trans, i, !(i)->deferred && \
- !same_leaf_as_prev(trans, i))
-
#endif /* _BCACHEFS_BTREE_UPDATE_H */
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;
diff --git a/fs/bcachefs/super.c b/fs/bcachefs/super.c
index bd4b3188be53..4145832f4856 100644
--- a/fs/bcachefs/super.c
+++ b/fs/bcachefs/super.c
@@ -494,6 +494,7 @@ static void bch2_fs_free(struct bch_fs *c)
bch2_fs_ec_exit(c);
bch2_fs_encryption_exit(c);
bch2_fs_io_exit(c);
+ bch2_fs_btree_iter_exit(c);
bch2_fs_btree_cache_exit(c);
bch2_fs_journal_exit(&c->journal);
bch2_io_clock_exit(&c->io_clock[WRITE]);
@@ -505,7 +506,6 @@ static void bch2_fs_free(struct bch_fs *c)
free_percpu(c->usage[0]);
kfree(c->usage_base);
free_percpu(c->pcpu);
- mempool_exit(&c->btree_iters_pool);
mempool_exit(&c->btree_bounce_pool);
bioset_exit(&c->btree_bio);
mempool_exit(&c->btree_interior_update_pool);
@@ -758,15 +758,12 @@ static struct bch_fs *bch2_fs_alloc(struct bch_sb *sb, struct bch_opts opts)
!(c->pcpu = alloc_percpu(struct bch_fs_pcpu)) ||
mempool_init_kvpmalloc_pool(&c->btree_bounce_pool, 1,
btree_bytes(c)) ||
- mempool_init_kmalloc_pool(&c->btree_iters_pool, 1,
- sizeof(struct btree_iter) * BTREE_ITER_MAX +
- sizeof(struct btree_insert_entry) *
- (BTREE_ITER_MAX + 4)) ||
bch2_io_clock_init(&c->io_clock[READ]) ||
bch2_io_clock_init(&c->io_clock[WRITE]) ||
bch2_fs_journal_init(&c->journal) ||
bch2_fs_replicas_init(c) ||
bch2_fs_btree_cache_init(c) ||
+ bch2_fs_btree_iter_init(c) ||
bch2_fs_io_init(c) ||
bch2_fs_encryption_init(c) ||
bch2_fs_compress_init(c) ||
generated by cgit v1.2.3 (git 2.46.0) at 2025-07-01 16:32:14 +0000