bcachefs: kill bch2_journal_entries_free()
PATCH 1/4 bcachefs: kill bch2_journal_entries_free()
--- fs/bcachefs/btree_journal_iter.c | 17 ++++++----------- fs/bcachefs/btree_journal_iter.h | 2 -- 2 files changed, 6 insertions(+), 13 deletions(-)
fs/bcachefs/btree_journal_iter.c +6 -11
@@ -527,16 +527,6 @@ void bch2_btree_and_journal_iter_init_node_iter(struct btree_trans *trans,/* sort and dedup all keys in the journal: */ -void bch2_journal_entries_free (struct bch_fs *c) -{ -struct journal_replay **i; -struct genradix_iter iter; - -genradix_for_each (&c->journal_entries, iter, i) -kvfree (*i); -genradix_free (&c->journal_entries); -} -/* * When keys compare equal, oldest compares first: */
@@ -569,7 +559,12 @@ void bch2_journal_keys_put(struct bch_fs *c) keys->data =NULL ; keys->nr = keys->gap = keys->size =0 ; -bch2_journal_entries_free (c); +struct journal_replay **i; +struct genradix_iter iter; + +genradix_for_each (&c->journal_entries, iter, i) +kvfree (*i); +genradix_free (&c->journal_entries); }static void __journal_keys_sort (struct journal_keys *keys)
fs/bcachefs/btree_journal_iter.h +0 -2
@@ -81,8 +81,6 @@ static inline void bch2_journal_keys_put_initial(struct bch_fs *c) c->journal_keys.initial_ref_held = false; } -void bch2_journal_entries_free (struct bch_fs *); -int bch2_journal_keys_sort (struct bch_fs *); void bch2_shoot_down_journal_keys(struct bch_fs *, enum btree_id,
Signature · 1 line
2.45.2
PATCH 2/4 bcachefs: journal keys: sort keys for interior nodes first
There's an unavoidable issue with btree lookups when we're overlaying journal keys and the journal has many deletions for keys present in the btree - peek operations will have to iterate over all those deletions to find the next live key to return.
This is mainly a problem for lookups in interior nodes, if we have to traverse to a leaf. Looking up an insert position in a leaf (for journal replay) doesn't have to find the next live key, but walking down the btree does.
So to ameloriate this, change journal key sort ordering so that we replay keys from roots and interior nodes first.
--- fs/bcachefs/btree_journal_iter.c | 10 ++++------ fs/bcachefs/btree_journal_iter.h | 13 ++++++++++--- 2 files changed, 14 insertions(+), 9 deletions(-)
fs/bcachefs/btree_journal_iter.c +4 -6
@@ -172,9 +172,8 @@ static void journal_iter_verify(struct journal_iter *iter)if (iter->idx < keys->size) {struct journal_key *k = keys->data + iter->idx; -int cmp =cmp_int (k->btree_id, iter->btree_id) ?: -cmp_int (k->level, iter->level); -BUG_ON (cmp <0 ); +int cmp =__journal_key_btree_cmp (iter->btree_id, iter->level, k); +BUG_ON (cmp >0 ); } }
@@ -365,9 +364,8 @@ static struct bkey_s_c bch2_journal_iter_peek(struct journal_iter *iter)while (iter->idx < iter->keys->size) {struct journal_key *k = iter->keys->data + iter->idx; -int cmp =cmp_int (k->btree_id, iter->btree_id) ?: -cmp_int (k->level, iter->level); -if (cmp >0 ) +int cmp =__journal_key_btree_cmp (iter->btree_id, iter->level, k); +if (cmp <0 )break ;BUG_ON (cmp);
fs/bcachefs/btree_journal_iter.h +10 -3
@@ -28,14 +28,21 @@ struct btree_and_journal_iter {bool prefetch; }; +static inline int __journal_key_btree_cmp (enum btree_id l_btree_id, +unsigned l_level, +const struct journal_key *r) +{ +return -cmp_int (l_level, r->level) ?: +cmp_int (l_btree_id, r->btree_id); +} +static inline int __journal_key_cmp (enum btree_id l_btree_id,unsigned l_level,struct bpos l_pos,const struct journal_key *r) { -return (cmp_int (l_btree_id, r->btree_id) ?: -cmp_int (l_level, r->level) ?: -bpos_cmp (l_pos, r->k->k.p)); +return __journal_key_btree_cmp (l_btree_id, l_level, r) ?: +bpos_cmp (l_pos, r->k->k.p); }static inline int journal_key_cmp (const struct journal_key *l,const struct journal_key *r)
Signature · 1 line
2.45.2
PATCH 3/4 bcachefs: btree_and_journal_iter: don't iterate over too many whiteouts when prefetching
In reply to Kent OverstreetTo help ameloriate issues with peek operations having to skip over deletions in the journal - just bail out if all we're doing is prefetching btree nodes.
Since btree node prefetching runs every time we iterate to a new node, and has to sequentially scan ahead, this avoids another O(n^2).
--- fs/bcachefs/btree_iter.c | 2 ++ fs/bcachefs/btree_journal_iter.c | 9 ++++++++- fs/bcachefs/btree_journal_iter.h | 1 + 3 files changed, 11 insertions(+), 1 deletion(-)
fs/bcachefs/btree_iter.c +2 -0
@@ -825,6 +825,8 @@ static int btree_path_prefetch_j(struct btree_trans *trans, struct btree_path *pbch2_bkey_buf_init (&tmp); + jiter->fail_if_too_many_whiteouts = true; +while (nr-- && !ret) {if (!bch2_btree_node_relock (trans, path, path->level))break ;
fs/bcachefs/btree_journal_iter.c +8 -1
@@ -426,6 +426,7 @@ static void btree_and_journal_iter_prefetch(struct btree_and_journal_iter *_iter : (level > 1 ? 1 : 16); iter.prefetch = false; + iter.fail_if_too_many_whiteouts = true;bch2_bkey_buf_init (&tmp);while (nr--) {
@@ -444,12 +445,18 @@ static void btree_and_journal_iter_prefetch(struct btree_and_journal_iter *_iterstruct bkey_s_c bch2_btree_and_journal_iter_peek (struct btree_and_journal_iter *iter) {struct bkey_s_c btree_k, journal_k = bkey_s_c_null, ret; +size_t iters =0 ;if (iter->prefetch && iter->journal.level)btree_and_journal_iter_prefetch (iter); -again: +if (iter->at_end)return bkey_s_c_null; +again: + iters++; + +if (iters >20 && iter->fail_if_too_many_whiteouts) +return bkey_s_c_null;while ((btree_k =bch2_journal_iter_peek_btree (iter)).k &&bpos_lt (btree_k.k->p, iter->pos))
fs/bcachefs/btree_journal_iter.h +1 -0
@@ -26,6 +26,7 @@ struct btree_and_journal_iter {struct bpos pos;bool at_end;bool prefetch; +bool fail_if_too_many_whiteouts; }; static inline int __journal_key_btree_cmp(enum btree_id l_btree_id,
Signature · 1 line
2.45.2
PATCH 4/4 bcachefs: fix O(n^2) issue with whiteouts in journal keys
In reply to Kent OverstreetThe journal_keys array can't be substantially modified after we go RW, because lookups need to be able to check it locklessly - thus we're limited on what we can do when a key in the journal has been overwritten.
This is a problem when there's many overwrites to skip over for peek() operations. To fix this, add tracking of ranges of overwrites: we create a range entry when there's more than one contiguous whiteout.
--- fs/bcachefs/bcachefs.h | 23 +--- fs/bcachefs/btree_journal_iter.c | 156 ++++++++++++++++++++++--- fs/bcachefs/btree_journal_iter.h | 2 + fs/bcachefs/btree_journal_iter_types.h | 36 ++++++ fs/bcachefs/super.c | 3 +- 5 files changed, 179 insertions(+), 41 deletions(-) create mode 100644 fs/bcachefs/btree_journal_iter_types.h
fs/bcachefs/bcachefs.h +1 -22
@@ -205,6 +205,7 @@#include <linux/zstd.h> #include "bcachefs_format.h" +#include "btree_journal_iter_types.h" #include "disk_accounting_types.h" #include "errcode.h" #include "fifo.h"
@@ -658,28 +659,6 @@ struct journal_seq_blacklist_table { } entries[]; }; -struct journal_keys { -/* must match layout in darray_types.h */ -size_t nr, size; -struct journal_key { -u64 journal_seq; -u32 journal_offset; -enum btree_id btree_id:8 ; -unsigned level:8 ; -bool allocated; -bool overwritten; -struct bkey_i *k; - } *data; -/* -* Gap buffer: instead of all the empty space in the array being at the -* end of the buffer - from @nr to @size - the empty space is at @gap. -* This means that sequential insertions are O(n) instead of O(n^2). -*/ -size_t gap; -atomic_t ref; -bool initial_ref_held; -}; -struct btree_trans_buf {struct btree_trans *trans; };
fs/bcachefs/btree_journal_iter.c +139 -17
255 lines not on this page · raw message
fs/bcachefs/btree_journal_iter.h +2 -0
@@ -97,4 +97,6 @@ void bch2_shoot_down_journal_keys(struct bch_fs *, enum btree_id,void bch2_journal_keys_dump (struct bch_fs *); +void bch2_fs_journal_keys_init (struct bch_fs *); +#endif /* _BCACHEFS_BTREE_JOURNAL_ITER_H */
fs/bcachefs/btree_journal_iter_types.h new file +36 -0
@@ -0,0 +1,36 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _BCACHEFS_BTREE_JOURNAL_ITER_TYPES_H +#define _BCACHEFS_BTREE_JOURNAL_ITER_TYPES_H + +struct journal_key_range_overwritten { +size_t start, end; +}; + +struct journal_key { +u64 journal_seq; +u32 journal_offset; +enum btree_id btree_id:8 ; +unsigned level:8 ; +bool allocated; +bool overwritten; +struct journal_key_range_overwritten __rcu * + overwritten_range; +struct bkey_i *k; +}; + +struct journal_keys { +/* must match layout in darray_types.h */ +size_t nr, size; +struct journal_key *data; +/* +* Gap buffer: instead of all the empty space in the array being at the +* end of the buffer - from @nr to @size - the empty space is at @gap. +* This means that sequential insertions are O(n) instead of O(n^2). +*/ +size_t gap; +atomic_t ref; +bool initial_ref_held; +struct mutex overwrite_lock; +}; + +#endif /* _BCACHEFS_BTREE_JOURNAL_ITER_TYPES_H */
fs/bcachefs/super.c +1 -2
@@ -773,8 +773,6 @@ static struct bch_fs *bch2_fs_alloc(struct bch_sb *sb, struct bch_opts opts)init_rwsem (&c->gc_lock);mutex_init (&c->gc_gens_lock); -atomic_set (&c->journal_keys.ref,1 ); - c->journal_keys.initial_ref_held = true;for (i =0 ; i <BCH_TIME_STAT_NR ; i++)bch2_time_stats_init (&c->times[i]);
@@ -784,6 +782,7 @@ static struct bch_fs *bch2_fs_alloc(struct bch_sb *sb, struct bch_opts opts)bch2_fs_btree_key_cache_init_early (&c->btree_key_cache);bch2_fs_btree_iter_init_early (c);bch2_fs_btree_interior_update_init_early (c); +bch2_fs_journal_keys_init (c);bch2_fs_allocator_background_init (c);bch2_fs_allocator_foreground_init (c);bch2_fs_rebalance_init (c);
Signature · 1 line
2.45.2