summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--drivers/md/bcache/bset.c158
-rw-r--r--drivers/md/bcache/bset.h17
-rw-r--r--drivers/md/bcache/btree_cache.c2
3 files changed, 94 insertions, 83 deletions
diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c
index ff66e190798d..7e77e23895ee 100644
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@ -296,6 +296,10 @@ struct bkey_float {
unsigned mantissa:BKEY_MANTISSA_BITS;
} __packed;
+struct ro_aux_tree {
+ struct bkey_float _d[0];
+};
+
/*
* BSET_CACHELINE was originally intended to match the hardware cacheline size -
* it used to be 64, but I realized the lookup code would touch slightly less
@@ -334,29 +338,66 @@ static inline size_t btree_aux_data_u64s(struct btree_keys *b)
return btree_aux_data_bytes(b) / sizeof(u64);
}
-static u16 bset_aux_tree_buf_end(const struct bset_tree *t)
+static unsigned bset_aux_tree_buf_end(const struct bset_tree *t)
{
- return t->prev_offset + DIV_ROUND_UP(t->size, 8);
+ BUG_ON(t->aux_data_offset == U16_MAX);
+
+ switch (bset_aux_tree_type(t)) {
+ case BSET_NO_AUX_TREE:
+ return t->aux_data_offset;
+ case BSET_RO_AUX_TREE:
+ return t->aux_data_offset +
+ DIV_ROUND_UP((sizeof(struct bkey_float) +
+ sizeof(u8)) * t->size, 8);
+ case BSET_RW_AUX_TREE:
+ return t->aux_data_offset +
+ DIV_ROUND_UP(sizeof(u8) * t->size, 8);
+ default:
+ BUG();
+ }
}
-static u16 bset_aux_tree_buf_start(const struct btree_keys *b,
- const struct bset_tree *t)
+static unsigned bset_aux_tree_buf_start(const struct btree_keys *b,
+ const struct bset_tree *t)
{
return t == b->set
? DIV_ROUND_UP(b->unpack_fn_len, 8)
: bset_aux_tree_buf_end(t - 1);
}
-static struct bkey_float *bset_tree(const struct btree_keys *b,
- const struct bset_tree *t)
+static void *__aux_tree_base(const struct btree_keys *b,
+ const struct bset_tree *t)
+{
+ return b->aux_data + t->aux_data_offset * 8;
+}
+
+static struct ro_aux_tree *ro_aux_tree_base(const struct btree_keys *b,
+ const struct bset_tree *t)
{
- return (void *) (((u64 *) b->aux_data) + t->tree_offset);
+ EBUG_ON(bset_aux_tree_type(t) != BSET_RO_AUX_TREE);
+
+ return __aux_tree_base(b, t);
+}
+
+static u8 *ro_aux_tree_prev(const struct btree_keys *b,
+ const struct bset_tree *t)
+{
+ EBUG_ON(bset_aux_tree_type(t) != BSET_RO_AUX_TREE);
+
+ return __aux_tree_base(b, t) + t->size * sizeof(struct bkey_float);
}
-static u8 *bset_prev(const struct btree_keys *b,
- const struct bset_tree *t)
+static struct bkey_float *bkey_float_get(struct ro_aux_tree *b,
+ unsigned idx)
{
- return (void *) (((u64 *) b->aux_data) + t->prev_offset);
+ return &b->_d[idx];
+}
+
+static struct bkey_float *bkey_float(const struct btree_keys *b,
+ const struct bset_tree *t,
+ unsigned idx)
+{
+ return bkey_float_get(ro_aux_tree_base(b, t), idx);
}
static void bset_aux_tree_verify(struct btree_keys *b)
@@ -365,31 +406,14 @@ static void bset_aux_tree_verify(struct btree_keys *b)
struct bset_tree *t;
for_each_bset(b, t) {
- if (t->tree_offset == U16_MAX)
+ if (t->aux_data_offset == U16_MAX)
continue;
BUG_ON(t != b->set &&
- (t[-1].tree_offset == U16_MAX ||
- t[-1].prev_offset == U16_MAX));
-
- BUG_ON(t->tree_offset < bset_aux_tree_buf_start(b, t));
-
- switch (bset_aux_tree_type(t)) {
- case BSET_NO_AUX_TREE:
- BUG_ON((void *) bset_prev(b, t) !=
- (void *) bset_tree(b, t));
- break;
- case BSET_RO_AUX_TREE:
- BUG_ON((void *) bset_prev(b, t) <
- (void *) (bset_tree(b, t) + t->size));
- break;
- case BSET_RW_AUX_TREE:
- BUG_ON((void *) bset_tree(b, t) !=
- (void *) bset_prev(b, t));
- BUG_ON(t != bset_tree_last(b));
- break;
- }
+ t[-1].aux_data_offset == U16_MAX);
+ BUG_ON(t->aux_data_offset < bset_aux_tree_buf_start(b, t));
+ BUG_ON(t->aux_data_offset > btree_aux_data_u64s(b));
BUG_ON(bset_aux_tree_buf_end(t) > btree_aux_data_u64s(b));
}
#endif
@@ -634,13 +658,23 @@ static unsigned bkey_to_cacheline_offset(struct bset_tree *t,
static struct bkey_packed *tree_to_bkey(const struct btree_keys *b,
struct bset_tree *t, unsigned j)
{
- return cacheline_to_bkey(t, to_inorder(j, t), bset_tree(b, t)[j].m);
+ return cacheline_to_bkey(t, to_inorder(j, t), bkey_float(b, t, j)->m);
}
static struct bkey_packed *tree_to_prev_bkey(struct btree_keys *b,
struct bset_tree *t, unsigned j)
{
- return (void *) (((u64 *) tree_to_bkey(b, t, j)) - bset_prev(b, t)[j]);
+ unsigned prev_u64s = ro_aux_tree_prev(b, t)[j];
+
+ return (void *) (tree_to_bkey(b, t, j)->_data - prev_u64s);
+}
+
+static u8 *rw_aux_tree(const struct btree_keys *b,
+ const struct bset_tree *t)
+{
+ EBUG_ON(bset_aux_tree_type(t) != BSET_RW_AUX_TREE);
+
+ return __aux_tree_base(b, t);
}
/*
@@ -651,7 +685,7 @@ static struct bkey_packed *table_to_bkey(const struct btree_keys *b,
struct bset_tree *t,
unsigned cacheline)
{
- return cacheline_to_bkey(t, cacheline, bset_prev(b, t)[cacheline]);
+ return cacheline_to_bkey(t, cacheline, rw_aux_tree(b, t)[cacheline]);
}
static inline unsigned bfloat_mantissa(const struct bkey_packed *k,
@@ -680,7 +714,7 @@ static inline unsigned bfloat_mantissa(const struct bkey_packed *k,
static void make_bfloat(struct btree_keys *b,
struct bset_tree *t, unsigned j)
{
- struct bkey_float *f = bset_tree(b, t) + j;
+ struct bkey_float *f = bkey_float(b, t, j);
struct bkey_packed *m = tree_to_bkey(b, t, j);
struct bkey_packed *p = tree_to_prev_bkey(b, t, j);
@@ -780,19 +814,18 @@ static unsigned __bset_tree_capacity(struct btree_keys *b, struct bset_tree *t)
{
bset_aux_tree_verify(b);
- return btree_aux_data_u64s(b) - t->tree_offset;
+ return btree_aux_data_bytes(b) - t->aux_data_offset * sizeof(u64);
}
static unsigned bset_ro_tree_capacity(struct btree_keys *b, struct bset_tree *t)
{
+
return __bset_tree_capacity(b, t) /
(sizeof(struct bkey_float) + sizeof(u8));
}
static unsigned bset_rw_tree_capacity(struct btree_keys *b, struct bset_tree *t)
{
- EBUG_ON(t->prev_offset != t->tree_offset);
-
return __bset_tree_capacity(b, t) / sizeof(u8);
}
@@ -811,7 +844,7 @@ static void bch_bset_lookup_table_add_entries(struct btree_keys *b,
if (t->size == bset_rw_tree_capacity(b, t))
return;
- bset_prev(b, t)[t->size] =
+ rw_aux_tree(b, t)[t->size] =
bkey_to_cacheline_offset(t, t->size, k);
t->size++;
}
@@ -819,9 +852,9 @@ static void bch_bset_lookup_table_add_entries(struct btree_keys *b,
static void __build_rw_aux_tree(struct btree_keys *b, struct bset_tree *t)
{
- bset_prev(b, t)[0] = bkey_to_cacheline_offset(t, 0, t->data->start);
t->size = 1;
t->extra = BSET_RW_AUX_TREE_VAL;
+ rw_aux_tree(b, t)[0] = bkey_to_cacheline_offset(t, 0, t->data->start);
bch_bset_lookup_table_add_entries(b, t);
}
@@ -837,13 +870,9 @@ retry:
if (t->size < 2) {
t->size = 0;
t->extra = BSET_NO_AUX_TREE_VAL;
- t->prev_offset = t->tree_offset;
return;
}
- t->prev_offset = t->tree_offset +
- DIV_ROUND_UP(t->size * sizeof(struct bkey_float), 8);
-
t->extra = (t->size - rounddown_pow_of_two(t->size - 1)) << 1;
/* First we figure out where the first key in each cacheline is */
@@ -858,8 +887,9 @@ retry:
goto retry;
}
- bset_prev(b, t)[j] = prev->u64s;
- bset_tree(b, t)[j].m = bkey_to_cacheline_offset(t, cacheline++, k);
+ ro_aux_tree_prev(b, t)[j] = prev->u64s;
+ bkey_float(b, t, j)->m =
+ bkey_to_cacheline_offset(t, cacheline++, k);
BUG_ON(tree_to_prev_bkey(b, t, j) != prev);
BUG_ON(tree_to_bkey(b, t, j) != k);
@@ -880,21 +910,15 @@ retry:
static void bset_alloc_tree(struct btree_keys *b, struct bset_tree *t)
{
struct bset_tree *i;
- u16 offset;
for (i = b->set; i != t; i++)
BUG_ON(bset_has_rw_aux_tree(i));
bch_bset_set_no_aux_tree(b, t);
- offset = bset_aux_tree_buf_start(b, t);
-
/* round up to next cacheline: */
- offset = round_up(offset, SMP_CACHE_BYTES / sizeof(u64));
- BUG_ON(offset > btree_aux_data_u64s(b));
-
- t->tree_offset = offset;
- t->prev_offset = offset;
+ t->aux_data_offset = round_up(bset_aux_tree_buf_start(b, t),
+ SMP_CACHE_BYTES / sizeof(u64));
bset_aux_tree_verify(b);
}
@@ -1114,7 +1138,7 @@ static void bch_bset_fix_lookup_table(struct btree_keys *b,
(struct bkey_packed *) ((u64 *) where + clobber_u64s))
new_offset = __bkey_to_cacheline_offset(t, j, where);
else
- new_offset = (int) bset_prev(b, t)[j] + shift;
+ new_offset = (int) rw_aux_tree(b, t)[j] + shift;
if (new_offset > 7) {
k = table_to_bkey(b, t, j - 1);
@@ -1132,7 +1156,7 @@ static void bch_bset_fix_lookup_table(struct btree_keys *b,
}
BUG_ON(new_offset > U8_MAX);
- bset_prev(b, t)[j] = new_offset;
+ rw_aux_tree(b, t)[j] = new_offset;
}
bch_bset_lookup_table_add_entries(b, t);
@@ -1264,16 +1288,16 @@ static struct bkey_packed *bset_search_tree(const struct btree_keys *b,
struct bpos search,
const struct bkey_packed *packed_search)
{
- struct bkey_float *tree = bset_tree(b, t);
- struct bkey_float *f = &tree[1];
+ struct ro_aux_tree *base = ro_aux_tree_base(b, t);
+ struct bkey_float *f = bkey_float_get(base, 1);
+ void *p;
unsigned inorder, n = 1;
while (1) {
if (likely(n << 4 < t->size)) {
- prefetch(&tree[n << 4]);
+ p = bkey_float_get(base, n << 4);
+ prefetch(p);
} else if (n << 3 < t->size) {
- void *p;
-
inorder = to_inorder(n, t);
p = cacheline_to_bkey(t, inorder, 0);
#ifdef CONFIG_X86_64
@@ -1294,7 +1318,7 @@ static struct bkey_packed *bset_search_tree(const struct btree_keys *b,
} else if (n >= t->size)
break;
- f = &tree[n];
+ f = bkey_float_get(base, n);
if (packed_search &&
likely(f->exponent < BFLOAT_FAILED))
@@ -1315,7 +1339,8 @@ static struct bkey_packed *bset_search_tree(const struct btree_keys *b,
return cacheline_to_bkey(t, inorder, f->m);
} else {
if (--inorder) {
- f = &tree[inorder_prev(n >> 1, t->size)];
+ n = inorder_prev(n >> 1, t->size);
+ f = bkey_float_get(base, n);
return cacheline_to_bkey(t, inorder, f->m);
} else
return t->data->start;
@@ -1706,12 +1731,10 @@ void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *stats)
stats->sets[type].bytes += le16_to_cpu(t->data->u64s) * sizeof(u64);
if (bset_has_ro_aux_tree(t)) {
- struct bkey_float *tree = bset_tree(b, t);
-
stats->floats += t->size - 1;
for (j = 1; j < t->size; j++)
- switch (tree[j].exponent) {
+ switch (bkey_float(b, t, j)->exponent) {
case BFLOAT_FAILED_UNPACKED:
stats->failed_unpacked++;
break;
@@ -1730,7 +1753,6 @@ int bch_bkey_print_bfloat(struct btree_keys *b, struct bkey_packed *k,
char *buf, size_t size)
{
struct bset_tree *t = bch_bkey_to_bset(b, k);
- struct bkey_float *tree = bset_tree(b, t);
struct bkey_packed *l, *r, *p;
struct bkey uk, up;
char buf1[200], buf2[200];
@@ -1746,7 +1768,7 @@ int bch_bkey_print_bfloat(struct btree_keys *b, struct bkey_packed *k,
if (j &&
j < t->size &&
k == tree_to_bkey(b, t, j))
- switch (tree[j].exponent) {
+ switch (bkey_float(b, t, j)->exponent) {
case BFLOAT_FAILED_UNPACKED:
uk = bkey_unpack_key(b, k);
return scnprintf(buf, size,
diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h
index 64e6014fd860..7517aeb08cf9 100644
--- a/drivers/md/bcache/bset.h
+++ b/drivers/md/bcache/bset.h
@@ -163,17 +163,7 @@ struct bset_tree {
/* function of size - precalculated for to_inorder() */
u16 extra;
- u16 tree_offset;
-
- /*
- * The nodes in the bset tree point to specific keys - this
- * array holds the sizes of the previous key.
- *
- * Conceptually it's a member of struct bkey_float, but we want
- * to keep bkey_float to 4 bytes and prev isn't used in the fast
- * path.
- */
- u16 prev_offset;
+ u16 aux_data_offset;
/* copy of the last key in the set */
struct bkey_packed end;
@@ -193,7 +183,7 @@ enum bset_aux_tree_type {
#define BSET_NO_AUX_TREE_VAL (U16_MAX)
#define BSET_RW_AUX_TREE_VAL (U16_MAX - 1)
-static inline enum bset_aux_tree_type bset_aux_tree_type(struct bset_tree *t)
+static inline enum bset_aux_tree_type bset_aux_tree_type(const struct bset_tree *t)
{
switch (t->extra) {
case BSET_NO_AUX_TREE_VAL:
@@ -341,8 +331,7 @@ static inline void bch_bset_set_no_aux_tree(struct btree_keys *b,
for (; t < b->set + ARRAY_SIZE(b->set); t++) {
t->size = 0;
t->extra = BSET_NO_AUX_TREE_VAL;
- t->tree_offset = U16_MAX;
- t->prev_offset = U16_MAX;
+ t->aux_data_offset = U16_MAX;
}
}
diff --git a/drivers/md/bcache/btree_cache.c b/drivers/md/bcache/btree_cache.c
index d93465901c00..5c3e2a65a618 100644
--- a/drivers/md/bcache/btree_cache.c
+++ b/drivers/md/bcache/btree_cache.c
@@ -678,7 +678,7 @@ retry:
prefetch(b->keys.aux_data);
for_each_bset(&b->keys, t)
- prefetch((u64 *) b->keys.aux_data + t->tree_offset);
+ prefetch((u64 *) b->keys.aux_data + t->aux_data_offset);
/* avoid atomic set bit if it's not needed: */
if (btree_node_accessed(b))
generated by cgit v1.2.3 (git 2.46.0) at 2025-07-31 21:05:32 +0000