summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKent Overstreet <kmo@daterainc.com>2015-02-11 14:08:56 -0800
committerKent Overstreet <kmo@daterainc.com>2015-02-12 23:44:09 -0800
commitdfb3374c0079851846acfff5384c455d9d4308e7 (patch)
tree8b52eff2fa0b525d83b5edcc8677309ff32bc298
parentaee47560a6db649cec1e1b701faafb7a58e031c7 (diff)
bcache: Bkey format field offsets
Change-Id: I1e873cbd57043de3c07d3c798860b9c454d3134c
-rw-r--r--drivers/md/bcache/bkey.c118
-rw-r--r--drivers/md/bcache/bkey.h15
-rw-r--r--drivers/md/bcache/bset.c10
-rw-r--r--drivers/md/bcache/btree.c43
-rw-r--r--drivers/md/bcache/btree.h2
-rw-r--r--drivers/md/bcache/gc.c14
6 files changed, 145 insertions, 57 deletions
diff --git a/drivers/md/bcache/bkey.c b/drivers/md/bcache/bkey.c
index ead977cd458f..276d5b5ed2a1 100644
--- a/drivers/md/bcache/bkey.c
+++ b/drivers/md/bcache/bkey.c
@@ -60,11 +60,14 @@ static struct pack_state pack_state_init(const struct bkey_format *format,
__always_inline
static u64 get_inc_field(struct pack_state *state)
{
- unsigned bits = state->format->bits_per_field[state->field++];
+ unsigned bits = state->format->bits_per_field[state->field];
+ u64 offset = state->format->field_offset[state->field];
/* bits might be 0 - and if bits is 0, v will be 0 when we use mask */
u64 v = 0, mask = ~((~0ULL << 1) << (bits - 1));
+ state->field++;
+
if (bits >= state->shift) {
bits -= state->shift;
v = *state->p << bits;
@@ -78,13 +81,21 @@ static u64 get_inc_field(struct pack_state *state)
v |= *state->p >> state->shift;
}
- return v & mask;
+ return (v & mask) + offset;
}
__always_inline
static bool set_inc_field(struct pack_state *state, u64 v)
{
- unsigned bits = state->format->bits_per_field[state->field++];
+ unsigned bits = state->format->bits_per_field[state->field];
+ u64 offset = state->format->field_offset[state->field];
+
+ state->field++;
+
+ if (v < offset)
+ return false;
+
+ v -= offset;
if (fls64(v) > bits)
return false;
@@ -171,9 +182,17 @@ bool bkey_pack_pos(struct bkey_packed *out, struct bpos in,
}
__always_inline
-static void set_inc_field_lossy(struct pack_state *state, u64 v)
+static bool set_inc_field_lossy(struct pack_state *state, u64 v)
{
- unsigned bits = state->format->bits_per_field[state->field++];
+ unsigned bits = state->format->bits_per_field[state->field];
+ u64 offset = state->format->field_offset[state->field];
+
+ state->field++;
+
+ if (v < offset)
+ return false;
+
+ v -= offset;
v <<= 64 - bits;
v >>= 64 - bits;
@@ -190,6 +209,8 @@ static void set_inc_field_lossy(struct pack_state *state, u64 v)
state->shift -= bits;
*state->p |= v << state->shift;
}
+
+ return true;
}
/*
@@ -198,7 +219,7 @@ static void set_inc_field_lossy(struct pack_state *state, u64 v)
* legal to use a packed pos that isn't equivalent to the original pos,
* _provided_ it compares <= to the original pos.
*/
-void bkey_pack_pos_lossy(struct bkey_packed *out, struct bpos in,
+bool bkey_pack_pos_lossy(struct bkey_packed *out, struct bpos in,
const struct bkey_format *format)
{
struct pack_state state = pack_state_init(format, out);
@@ -208,63 +229,82 @@ void bkey_pack_pos_lossy(struct bkey_packed *out, struct bpos in,
out->format = KEY_FORMAT_LOCAL_BTREE;
out->type = KEY_TYPE_DELETED;
- set_inc_field_lossy(&state, in.inode);
- set_inc_field_lossy(&state, in.offset);
- set_inc_field_lossy(&state, in.snapshot);
+ return (set_inc_field_lossy(&state, in.inode) &&
+ set_inc_field_lossy(&state, in.offset) &&
+ set_inc_field_lossy(&state, in.snapshot));
}
-void bch_bkey_format_init(struct bkey_format *format)
+void bch_bkey_format_init(struct bkey_format_state *s)
{
- *format = (struct bkey_format) {
- .nr_fields = BKEY_NR_FIELDS,
- };
+ unsigned i;
+
+ for (i = 0; i < ARRAY_SIZE(s->field_min); i++)
+ s->field_min[i] = U64_MAX;
+
+ for (i = 0; i < ARRAY_SIZE(s->field_max); i++)
+ s->field_max[i] = 0;
}
-static void __bkey_format_add(struct bkey_format *format,
- unsigned *field, u64 v)
+static void __bkey_format_add(struct bkey_format_state *s,
+ unsigned field, u64 v)
{
- u8 *bits = &format->bits_per_field[(*field)++];
-
- *bits = max_t(unsigned, *bits, fls64(v));
+ s->field_min[field] = min(s->field_min[field], v);
+ s->field_max[field] = max(s->field_max[field], v);
}
/*
* Changes @format so that @k can be successfully packed with @format
*/
-void bch_bkey_format_add(struct bkey_format *format, struct bkey *k)
+void bch_bkey_format_add_key(struct bkey_format_state *s, struct bkey *k)
{
unsigned field = 0;
- __bkey_format_add(format, &field, k->p.inode);
- __bkey_format_add(format, &field, k->p.offset);
- __bkey_format_add(format, &field, k->p.snapshot);
- __bkey_format_add(format, &field, k->size);
- __bkey_format_add(format, &field, k->version);
+ __bkey_format_add(s, field++, k->p.inode);
+ __bkey_format_add(s, field++, k->p.offset);
+ __bkey_format_add(s, field++, k->p.snapshot);
+ __bkey_format_add(s, field++, k->size);
+ __bkey_format_add(s, field++, k->version);
EBUG_ON(field != BKEY_NR_FIELDS);
}
-void bch_bkey_format_done(struct bkey_format *format)
+void bch_bkey_format_add_pos(struct bkey_format_state *s, struct bpos p)
{
- unsigned i, bits = KEY_PACKED_BITS_START;
-
- for (i = 0; i < ARRAY_SIZE(format->bits_per_field); i++)
- bits += format->bits_per_field[i];
+ unsigned field = 0;
- format->key_u64s = DIV_ROUND_UP(bits, 64);
+ __bkey_format_add(s, field++, p.inode);
+ __bkey_format_add(s, field++, p.offset);
+ __bkey_format_add(s, field++, p.snapshot);
}
-struct bkey_format btree_keys_calc_format(struct btree_keys *b)
+struct bkey_format bch_bkey_format_done(struct bkey_format_state *s)
{
- struct bkey_format ret;
- struct btree_node_iter iter;
- struct bkey_tup tup;
-
- bch_bkey_format_init(&ret);
+ unsigned i, bits = KEY_PACKED_BITS_START;
+ struct bkey_format ret = {
+ .nr_fields = BKEY_NR_FIELDS,
+ };
- for_each_btree_node_key_unpack(b, &tup, &iter)
- bch_bkey_format_add(&ret, &tup.k);
+ /*
+ * Hack to make sure we can always repack keys in
+ * bch_insert_fixup_extent(), when trimming makes the offset smaller
+ */
+ s->field_min[BKEY_FIELD_OFFSET] =
+ max_t(s64, 0, s->field_min[BKEY_FIELD_OFFSET] - UINT_MAX);
+
+ /*
+ * Make sure we can always store a size of 0, also because of
+ * bch_insert_fixup_extent
+ */
+ s->field_min[BKEY_FIELD_SIZE] = 0;
+
+ for (i = 0; i < ARRAY_SIZE(s->field_min); i++) {
+ ret.field_offset[i] = min(s->field_min[i], s->field_max[i]);
+ ret.bits_per_field[i] = fls(s->field_max[i] -
+ ret.field_offset[i]);
+
+ bits += ret.bits_per_field[i];
+ }
- bch_bkey_format_done(&ret);
+ ret.key_u64s = DIV_ROUND_UP(bits, 64);
return ret;
}
diff --git a/drivers/md/bcache/bkey.h b/drivers/md/bcache/bkey.h
index bba9371457dc..666920d080f6 100644
--- a/drivers/md/bcache/bkey.h
+++ b/drivers/md/bcache/bkey.h
@@ -48,10 +48,15 @@ static inline void set_bkey_deleted(struct bkey *k)
struct btree_keys;
-void bch_bkey_format_init(struct bkey_format *);
-void bch_bkey_format_add(struct bkey_format *, struct bkey *);
-void bch_bkey_format_done(struct bkey_format *);
-struct bkey_format btree_keys_calc_format(struct btree_keys *);
+struct bkey_format_state {
+ u64 field_min[BKEY_NR_FIELDS];
+ u64 field_max[BKEY_NR_FIELDS];
+};
+
+void bch_bkey_format_init(struct bkey_format_state *);
+void bch_bkey_format_add_key(struct bkey_format_state *, struct bkey *);
+void bch_bkey_format_add_pos(struct bkey_format_state *, struct bpos);
+struct bkey_format bch_bkey_format_done(struct bkey_format_state *);
unsigned bkey_greatest_differing_bit(const struct bkey_format *,
const struct bkey_packed *,
@@ -269,7 +274,7 @@ static inline bool bkey_pack_key(struct bkey_packed *out, const struct bkey *in,
bool bkey_pack_pos(struct bkey_packed *, struct bpos,
const struct bkey_format *);
-void bkey_pack_pos_lossy(struct bkey_packed *, struct bpos,
+bool bkey_pack_pos_lossy(struct bkey_packed *, struct bpos,
const struct bkey_format *);
void bkey_unpack(struct bkey_i *, const struct bkey_format *,
const struct bkey_packed *);
diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c
index 6cc6c1730ab6..6f58fbf537d3 100644
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@ -529,8 +529,11 @@ void bch_bset_init_next(struct btree_keys *b, struct bset *i)
i->seq = b->set->data->seq;
i->format = b->set->data->format;
} else {
- bch_bkey_format_init(&b->set->data->format);
- bch_bkey_format_done(&b->set->data->format);
+ struct bkey_format_state s;
+
+ bch_bkey_format_init(&s);
+ b->set->data->format = bch_bkey_format_done(&s);
+
get_random_bytes(&i->seq, sizeof(uint64_t));
}
@@ -920,7 +923,8 @@ static struct bkey_packed *bset_search_tree(const struct bkey_format *format,
* packed_search and we'll just do more linear searching than we would
* have.
*/
- bkey_pack_pos_lossy(&packed_search, search, format);
+ if (!bkey_pack_pos_lossy(&packed_search, search, format))
+ return t->data->start;
while (1) {
if (likely(n << 4 < t->size)) {
diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c
index 203faaf5a377..9cfb8d830df8 100644
--- a/drivers/md/bcache/btree.c
+++ b/drivers/md/bcache/btree.c
@@ -1423,10 +1423,51 @@ struct btree *__btree_node_alloc_replacement(struct btree *b,
return n;
}
+void __bch_btree_calc_format(struct bkey_format_state *s, struct btree *b)
+{
+ struct btree_node_iter iter;
+ struct bkey_tup tup;
+
+ for_each_btree_node_key_unpack(&b->keys, &tup, &iter)
+ bch_bkey_format_add_key(s, &tup.k);
+
+ if (b->keys.ops->is_extents) {
+ /*
+ * Extents need special consideration because of
+ * bch_insert_fixup_extent() - they have to be modified in
+ * place, and successfully repack, when insert an overlapping
+ * extent:
+ */
+ bch_bkey_format_add_pos(s, b->key.k.p);
+
+ s->field_min[1] = max_t(s64, 0, s->field_min[1] - UINT_MAX);
+
+ /*
+ * If we span multiple inodes, need to be able to store an
+ * offset of 0:
+ */
+ if (s->field_min[0] != s->field_max[0])
+ s->field_min[1] = 0;
+
+ /* Make sure we can store a size of 0: */
+ s->field_min[3] = 0;
+ }
+}
+
+static struct bkey_format bch_btree_calc_format(struct btree *b)
+{
+ struct bkey_format_state s;
+
+ bch_bkey_format_init(&s);
+ __bch_btree_calc_format(&s, b);
+
+ return bch_bkey_format_done(&s);
+}
+
struct btree *btree_node_alloc_replacement(struct btree *b,
enum alloc_reserve reserve)
{
- struct bkey_format new_f = btree_keys_calc_format(&b->keys);
+ struct bkey_format new_f = bch_btree_calc_format(b);
if (!btree_node_format_fits(b, &new_f))
new_f = b->keys.set->data->format;
diff --git a/drivers/md/bcache/btree.h b/drivers/md/bcache/btree.h
index 6e57516369ac..a11f9741cf3f 100644
--- a/drivers/md/bcache/btree.h
+++ b/drivers/md/bcache/btree.h
@@ -338,6 +338,8 @@ static inline bool btree_node_format_fits(struct btree *b,
PAGE_SIZE << b->keys.page_order;
}
+void __bch_btree_calc_format(struct bkey_format_state *, struct btree *);
+
struct btree *__btree_node_alloc_replacement(struct btree *,
enum alloc_reserve,
struct bkey_format);
diff --git a/drivers/md/bcache/gc.c b/drivers/md/bcache/gc.c
index b3a90750d0c7..b252b91eb2fd 100644
--- a/drivers/md/bcache/gc.c
+++ b/drivers/md/bcache/gc.c
@@ -176,6 +176,7 @@ static void bch_coalesce_nodes(struct btree *old_nodes[GC_MERGE_NODES],
struct keylist keylist;
struct closure cl;
struct bpos saved_pos;
+ struct bkey_format_state format_state;
struct bkey_format new_format;
int ret;
@@ -206,17 +207,12 @@ static void bch_coalesce_nodes(struct btree *old_nodes[GC_MERGE_NODES],
trace_bcache_btree_gc_coalesce(parent, nr_old_nodes);
- bch_bkey_format_init(&new_format);
+ bch_bkey_format_init(&format_state);
- for (i = 0; i < nr_old_nodes; i++) {
- struct btree_node_iter iter;
- struct bkey_tup tup;
-
- for_each_btree_node_key_unpack(&old_nodes[i]->keys, &tup, &iter)
- bch_bkey_format_add(&new_format, &tup.k);
- }
+ for (i = 0; i < nr_old_nodes; i++)
+ __bch_btree_calc_format(&format_state, old_nodes[i]);
- bch_bkey_format_done(&new_format);
+ new_format = bch_bkey_format_done(&format_state);
for (i = 0; i < nr_old_nodes; i++)
if (!btree_node_format_fits(old_nodes[i], &new_format)) {