bch2_bset_fix_lookup_table is too complicated to be easily understood,
the comment "l now > where" there is also incorrect when where ==
t->end_offset. This patch therefore refactor the function, the idea is
that when where >= rw_aux_tree(b, t)[t->size - 1].offset, we don't need
to adjust the rw aux tree.
Signed-off-by: Alan Huang <mmpgour...@gmail.com>
---
fs/bcachefs/bset.c | 116 +++++++++++++++++++++++++--------------------
1 file changed, 65 insertions(+), 51 deletions(-)
diff --git a/fs/bcachefs/bset.c b/fs/bcachefs/bset.c
index 1b66b2c7e018..c5fffed88c46 100644
--- a/fs/bcachefs/bset.c
+++ b/fs/bcachefs/bset.c
@@ -885,6 +885,34 @@ struct bkey_packed *bch2_bkey_prev_filter(struct btree *b,
/* Insert */
+static void rw_aux_tree_build_entry(struct btree *b,
+ struct bset_tree *t,
+ struct bkey_packed *start,
+ struct bkey_packed *end,
+ unsigned l)
+{
+ if (t->size < bset_rw_tree_capacity(b, t) &&
+ (void *) end - (void *) start > L1_CACHE_BYTES) {
+ struct bkey_packed *k = start;
+
+ while (1) {
+ k = bkey_p_next(k);
+ if (k == end)
+ break;
+
+ if ((void *) k - (void *) start >= L1_CACHE_BYTES) {
+ memmove(&rw_aux_tree(b, t)[l + 1],
+ &rw_aux_tree(b, t)[l],
+ (void *) &rw_aux_tree(b, t)[t->size] -
+ (void *) &rw_aux_tree(b, t)[l]);
+ t->size++;
+ rw_aux_tree_set(b, t, l, k);
+ break;
+ }
+ }
+ }
+}
+
static void bch2_bset_fix_lookup_table(struct btree *b,
struct bset_tree *t,
struct bkey_packed *_where,
@@ -899,34 +927,42 @@ static void bch2_bset_fix_lookup_table(struct btree *b,
if (!bset_has_rw_aux_tree(t))
return;
+ if (where > rw_aux_tree(b, t)[t->size - 1].offset) {
+build_entry:
+ rw_aux_tree_build_entry(b, t,
+ rw_aux_to_bkey(b, t, t->size - 1),
+ btree_bkey_last(b, t),
+ t->size);
+ return;
+ }
+
/* returns first entry >= where */
l = rw_aux_tree_bsearch(b, t, where);
- if (!l) /* never delete first entry */
- l++;
- else if (l < t->size &&
- where < t->end_offset &&
- rw_aux_tree(b, t)[l].offset == where)
- rw_aux_tree_set(b, t, l++, _where);
+ if (rw_aux_tree(b, t)[l].offset == where) {
+ if (!l) { /* never delete first entry */
+ l++;
+ } else if (where < t->end_offset) {
+ rw_aux_tree_set(b, t, l++, _where);
+ } else {
+ /* where == t->end_offset */
+ EBUG_ON(where > t->end_offset);
+ t->size--;
+ goto build_entry;
+ }
+ }
/* l now > where */
-
- for (j = l;
- j < t->size &&
- rw_aux_tree(b, t)[j].offset < where + clobber_u64s;
- j++)
- ;
-
- if (j < t->size &&
- rw_aux_tree(b, t)[j].offset + shift ==
- rw_aux_tree(b, t)[l - 1].offset)
- j++;
-
- memmove(&rw_aux_tree(b, t)[l],
- &rw_aux_tree(b, t)[j],
- (void *) &rw_aux_tree(b, t)[t->size] -
- (void *) &rw_aux_tree(b, t)[j]);
- t->size -= j - l;
+ EBUG_ON(l < t->size && rw_aux_tree(b, t)[l].offset <= where);
+ if (l < t->size &&
+ rw_aux_tree(b, t)[l].offset + shift ==
+ rw_aux_tree(b, t)[l - 1].offset) {
+ memmove(&rw_aux_tree(b, t)[l],
+ &rw_aux_tree(b, t)[l + 1],
+ (void *) &rw_aux_tree(b, t)[t->size] -
+ (void *) &rw_aux_tree(b, t)[l + 1]);
+ t->size -= 1;
+ }
for (j = l; j < t->size; j++)
rw_aux_tree(b, t)[j].offset += shift;
@@ -935,34 +971,12 @@ static void bch2_bset_fix_lookup_table(struct btree *b,
rw_aux_tree(b, t)[l].offset ==
rw_aux_tree(b, t)[l - 1].offset);
- if (t->size < bset_rw_tree_capacity(b, t) &&
- (l < t->size
- ? rw_aux_tree(b, t)[l].offset
- : t->end_offset) -
- rw_aux_tree(b, t)[l - 1].offset >
- L1_CACHE_BYTES / sizeof(u64)) {
- struct bkey_packed *start = rw_aux_to_bkey(b, t, l - 1);
- struct bkey_packed *end = l < t->size
- ? rw_aux_to_bkey(b, t, l)
- : btree_bkey_last(b, t);
- struct bkey_packed *k = start;
-
- while (1) {
- k = bkey_p_next(k);
- if (k == end)
- break;
-
- if ((void *) k - (void *) start >= L1_CACHE_BYTES) {
- memmove(&rw_aux_tree(b, t)[l + 1],
- &rw_aux_tree(b, t)[l],
- (void *) &rw_aux_tree(b, t)[t->size] -
- (void *) &rw_aux_tree(b, t)[l]);
- t->size++;
- rw_aux_tree_set(b, t, l, k);
- break;
- }
- }
- }
+ rw_aux_tree_build_entry(b, t,
+ rw_aux_to_bkey(b, t, l - 1),
+ l < t->size
+ ? rw_aux_to_bkey(b, t, l)
+ : btree_bkey_last(b, t),
+ l);
bch2_bset_verify_rw_aux_tree(b, t);
bset_aux_tree_verify(b);
--
2.45.2
