summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKent Overstreet <kmo@daterainc.com>2015-02-10 18:17:37 -0800
committerKent Overstreet <kmo@daterainc.com>2015-02-12 23:44:05 -0800
commitb2961fdc4ad5b3279983c334ad8ba2068b0cbf68 (patch)
tree7eddb274a650937c313abc2c6996bda88d599bc7
parentdd9cb23bbc5ad1042c1533c70440a10f1d1c9212 (diff)
bcache: Pointer compression for btree_node_iter
Change-Id: Iad777ebaec333070b5d5bcd776da6a282dd96792
-rw-r--r--drivers/md/bcache/bset.c53
-rw-r--r--drivers/md/bcache/bset.h37
-rw-r--r--drivers/md/bcache/btree.c3
-rw-r--r--drivers/md/bcache/extents.c55
4 files changed, 98 insertions, 50 deletions
diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c
index 32185bfb6f23..7c9056678b55 100644
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@ -640,21 +640,23 @@ static void verify_insert_pos(struct btree_keys *b,
* @top must be in the last bset.
*/
static void bch_btree_node_iter_fix(struct btree_node_iter *iter,
+ struct btree_keys *b,
const struct bkey_packed *where)
{
struct btree_node_iter_set *set;
- u64 n = where->u64s;
+ unsigned offset = __btree_node_key_to_offset(b, where);
+ unsigned shift = where->u64s;
BUG_ON(iter->used > MAX_BSETS);
for (set = iter->data;
set < iter->data + iter->used;
set++)
- if (set->end >= where) {
- set->end = (void *) ((u64 *) set->end + n);
+ if (set->end >= offset) {
+ set->end += shift;
- if (set->k >= where)
- set->k = (void *) ((u64 *) set->k + n);
+ if (set->k >= offset)
+ set->k += shift;
break;
}
}
@@ -775,7 +777,7 @@ void bch_bset_insert(struct btree_keys *b,
struct bset_tree *t = bset_tree_last(b);
struct bset *i = t->data;
struct bkey_packed *prev = NULL;
- struct bkey_packed *where = bch_btree_node_iter_bset_pos(iter, i) ?:
+ struct bkey_packed *where = bch_btree_node_iter_bset_pos(iter, b, i) ?:
bset_bkey_last(i);
struct bkey_packed packed, *src;
BKEY_PADDED(k) tmp;
@@ -858,7 +860,7 @@ void bch_bset_insert(struct btree_keys *b,
b->nr_live_u64s += src->u64s;
bch_bset_fix_lookup_table(b, t, where);
- bch_btree_node_iter_fix(iter, where);
+ bch_btree_node_iter_fix(iter, b, where);
bch_btree_node_iter_verify(iter, b);
}
@@ -1034,10 +1036,12 @@ static struct bkey_packed *bch_bset_search(struct btree_keys *b,
static inline bool btree_node_iter_cmp(struct btree_node_iter *iter,
struct btree_keys *b,
- struct btree_node_iter_set l,
- struct btree_node_iter_set r)
+ struct btree_node_iter_set ls,
+ struct btree_node_iter_set rs)
{
- s64 c = bkey_cmp_packed(&b->set->data->format, l.k, r.k);
+ struct bkey_packed *l = __btree_node_offset_to_key(b, ls.k);
+ struct bkey_packed *r = __btree_node_offset_to_key(b, rs.k);
+ s64 c = bkey_cmp_packed(&b->set->data->format, l, r);
/*
* For non extents, when keys compare equal the deleted keys have to
@@ -1049,8 +1053,8 @@ static inline bool btree_node_iter_cmp(struct btree_node_iter *iter,
*/
return c ? c > 0
: iter->is_extents
- ? bkey_deleted(l.k) > bkey_deleted(r.k)
- : bkey_deleted(l.k) < bkey_deleted(r.k);
+ ? bkey_deleted(l) > bkey_deleted(r)
+ : bkey_deleted(l) < bkey_deleted(r);
}
void bch_btree_node_iter_push(struct btree_node_iter *iter,
@@ -1060,7 +1064,10 @@ void bch_btree_node_iter_push(struct btree_node_iter *iter,
{
if (k != end) {
struct btree_node_iter_set n =
- ((struct btree_node_iter_set) { k, end });
+ ((struct btree_node_iter_set) {
+ __btree_node_key_to_offset(b, k),
+ __btree_node_key_to_offset(b, end)
+ });
unsigned i;
for (i = 0;
@@ -1117,8 +1124,10 @@ void bch_btree_node_iter_init_from_start(struct btree_node_iter *iter,
EXPORT_SYMBOL(bch_btree_node_iter_init_from_start);
struct bkey_packed *bch_btree_node_iter_bset_pos(struct btree_node_iter *iter,
+ struct btree_keys *b,
struct bset *i)
{
+ unsigned end = __btree_node_key_to_offset(b, bset_bkey_last(i));
struct btree_node_iter_set *set;
BUG_ON(iter->used > MAX_BSETS);
@@ -1126,8 +1135,8 @@ struct bkey_packed *bch_btree_node_iter_bset_pos(struct btree_node_iter *iter,
for (set = iter->data;
set < iter->data + iter->used;
set++)
- if (bset_bkey_last(i) == set->end)
- return set->k;
+ if (end == set->end)
+ return __btree_node_offset_to_key(b, set->k);
return NULL;
}
@@ -1168,7 +1177,7 @@ EXPORT_SYMBOL(bch_btree_node_iter_sort);
void bch_btree_node_iter_advance(struct btree_node_iter *iter,
struct btree_keys *b)
{
- iter->data->k = bkey_next(iter->data->k);
+ iter->data->k += __bch_btree_node_iter_peek_all(iter, b)->u64s;
BUG_ON(iter->data->k > iter->data->end);
@@ -1199,7 +1208,8 @@ void bch_btree_node_iter_verify(struct btree_node_iter *iter,
for (t = b->set;
t <= b->set + b->nsets;
t++)
- if (set->end == bset_bkey_last(t->data))
+ if (__btree_node_offset_to_key(b, set->end) ==
+ bset_bkey_last(t->data))
goto next;
BUG();
next:
@@ -1212,13 +1222,14 @@ static void bch_btree_node_iter_next_check(struct btree_node_iter *iter,
struct bkey_packed *k)
{
const struct bkey_format *f = &b->set->data->format;
+ const struct bkey_packed *n = bch_btree_node_iter_peek_all(iter, b);
bkey_unpack_key(f, k);
- if (!bch_btree_node_iter_end(iter) &&
- keys_out_of_order(f, k, iter->data->k, iter->is_extents)) {
+ if (n &&
+ keys_out_of_order(f, k, n, iter->is_extents)) {
struct bkey ku = bkey_unpack_key(f, k);
- struct bkey nu = bkey_unpack_key(f, iter->data->k);
+ struct bkey nu = bkey_unpack_key(f, n);
char buf1[80], buf2[80];
bch_dump_bucket(b);
@@ -1231,7 +1242,7 @@ static void bch_btree_node_iter_next_check(struct btree_node_iter *iter,
struct bkey_packed *bch_btree_node_iter_next_all(struct btree_node_iter *iter,
struct btree_keys *b)
{
- struct bkey_packed *ret = bch_btree_node_iter_peek_all(iter);
+ struct bkey_packed *ret = bch_btree_node_iter_peek_all(iter, b);
if (ret) {
bch_btree_node_iter_advance(iter, b);
diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h
index 34b887b6b325..d22b034f50df 100644
--- a/drivers/md/bcache/bset.h
+++ b/drivers/md/bcache/bset.h
@@ -382,10 +382,10 @@ static inline enum bch_extent_overlap bch_extent_overlap(const struct bkey *k,
struct btree_node_iter {
u8 is_extents;
- unsigned used:24;
+ u16 used;
struct btree_node_iter_set {
- struct bkey_packed *k, *end;
+ u16 k, end;
} data[MAX_BSETS];
};
@@ -396,6 +396,7 @@ void bch_btree_node_iter_init(struct btree_node_iter *, struct btree_keys *,
void bch_btree_node_iter_init_from_start(struct btree_node_iter *,
struct btree_keys *);
struct bkey_packed *bch_btree_node_iter_bset_pos(struct btree_node_iter *,
+ struct btree_keys *,
struct bset *);
void bch_btree_node_iter_sort(struct btree_node_iter *, struct btree_keys *);
@@ -406,12 +407,34 @@ static inline bool bch_btree_node_iter_end(struct btree_node_iter *iter)
return !iter->used;
}
+static inline u16
+__btree_node_key_to_offset(struct btree_keys *b, const struct bkey_packed *k)
+{
+ size_t ret = (u64 *) k - (u64 *) b->set->data;
+ EBUG_ON(ret > U16_MAX);
+ return ret;
+}
+
+static inline struct bkey_packed *
+__btree_node_offset_to_key(struct btree_keys *b, u16 k)
+{
+ return (void *) ((u64 *) b->set->data + k);
+}
+
+static inline struct bkey_packed *
+__bch_btree_node_iter_peek_all(struct btree_node_iter *iter,
+ struct btree_keys *b)
+{
+ return __btree_node_offset_to_key(b, iter->data->k);
+}
+
static inline struct bkey_packed *
-bch_btree_node_iter_peek_all(struct btree_node_iter *iter)
+bch_btree_node_iter_peek_all(struct btree_node_iter *iter,
+ struct btree_keys *b)
{
return bch_btree_node_iter_end(iter)
? NULL
- : iter->data->k;
+ : __bch_btree_node_iter_peek_all(iter, b);
}
/* In debug mode, bch_btree_node_iter_next_all() does debug checks */
@@ -423,7 +446,7 @@ struct bkey_packed *bch_btree_node_iter_next_all(struct btree_node_iter *,
static inline struct bkey_packed *
bch_btree_node_iter_next_all(struct btree_node_iter *iter, struct btree_keys *b)
{
- struct bkey_packed *ret = bch_btree_node_iter_peek_all(iter);
+ struct bkey_packed *ret = bch_btree_node_iter_peek_all(iter, b);
if (ret)
bch_btree_node_iter_advance(iter, b);
@@ -449,7 +472,7 @@ bch_btree_node_iter_peek(struct btree_node_iter *iter, struct btree_keys *b)
{
struct bkey_packed *ret;
- while ((ret = bch_btree_node_iter_peek_all(iter)) &&
+ while ((ret = bch_btree_node_iter_peek_all(iter, b)) &&
bkey_deleted(ret))
bch_btree_node_iter_next_all(iter, b);
@@ -465,7 +488,7 @@ bch_btree_node_iter_peek_overlapping(struct btree_node_iter *iter,
struct bkey_packed *ret;
struct bkey u;
- while ((ret = bch_btree_node_iter_peek_all(iter)) &&
+ while ((ret = bch_btree_node_iter_peek_all(iter, b)) &&
(bkey_cmp_left_packed(f, ret, bkey_start_pos(end)) <= 0))
bch_btree_node_iter_next_all(iter, b);
diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c
index 465f7d1612b8..12dace3f0358 100644
--- a/drivers/md/bcache/btree.c
+++ b/drivers/md/bcache/btree.c
@@ -2259,7 +2259,8 @@ static inline struct bkey_s_c __btree_iter_peek_all(struct btree_iter *iter)
const struct bkey_format *f =
&iter->nodes[iter->level]->keys.set->data->format;
struct bkey_packed *k =
- bch_btree_node_iter_peek_all(&iter->node_iters[iter->level]);
+ bch_btree_node_iter_peek_all(&iter->node_iters[iter->level],
+ &iter->nodes[iter->level]->keys);
struct bkey_s_c ret;
if (!k)
diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c
index 278cd9d844d6..c4534db47ee3 100644
--- a/drivers/md/bcache/extents.c
+++ b/drivers/md/bcache/extents.c
@@ -28,9 +28,10 @@ static inline unsigned bkeyp_extent_ptrs(const struct bkey_format *f,
}
static void sort_key_next(struct btree_node_iter *iter,
+ struct btree_keys *b,
struct btree_node_iter_set *i)
{
- i->k = bkey_next(i->k);
+ i->k += __btree_node_offset_to_key(b, i->k)->u64s;
if (i->k == i->end)
*i = iter->data[--iter->used];
@@ -45,7 +46,9 @@ static void sort_key_next(struct btree_node_iter *iter,
*/
#define key_sort_cmp(l, r) \
({ \
- int _c = bkey_cmp_packed(&b->set->data->format, (l).k, (r).k); \
+ int _c = bkey_cmp_packed(&b->set->data->format, \
+ __btree_node_offset_to_key(b, (l).k), \
+ __btree_node_offset_to_key(b, (r).k)); \
\
_c ? _c > 0 : (l).k > (r).k; \
})
@@ -56,7 +59,7 @@ static inline bool should_drop_next_key(struct btree_node_iter *iter,
const struct bkey_format *f = &b->set->data->format;
struct btree_node_iter_set *l = iter->data, *r = iter->data + 1;
- if (bkey_deleted(l->k))
+ if (bkey_deleted(__btree_node_offset_to_key(b, l->k)))
return true;
if (iter->used < 2)
@@ -71,7 +74,9 @@ static inline bool should_drop_next_key(struct btree_node_iter *iter,
* comes first; so if l->k compares equal to r->k then l->k is older and
* should be dropped.
*/
- return !bkey_cmp_packed(f, l->k, r->k);
+ return !bkey_cmp_packed(f,
+ __btree_node_offset_to_key(b, l->k),
+ __btree_node_offset_to_key(b, r->k));
}
void bch_key_sort_fix_overlapping(struct btree_keys *b,
@@ -84,14 +89,16 @@ void bch_key_sort_fix_overlapping(struct btree_keys *b,
while (!bch_btree_node_iter_end(iter)) {
if (!should_drop_next_key(iter, b)) {
+ struct bkey_packed *k =
+ __btree_node_offset_to_key(b, iter->data->k);
+
/* XXX: need better bkey_copy */
//bkey_copy(out, iter->data->k);
- memcpy(out, iter->data->k,
- bkey_bytes(iter->data->k));
+ memcpy(out, k, bkey_bytes(k));
out = bkey_next(out);
}
- sort_key_next(iter, iter->data);
+ sort_key_next(iter, b, iter->data);
heap_sift(iter, 0, key_sort_cmp);
}
@@ -114,7 +121,7 @@ bool bch_insert_fixup_key(struct btree *b, struct bkey_i *insert,
BUG_ON(replace);
- while ((k = bch_btree_node_iter_peek_all(iter)) &&
+ while ((k = bch_btree_node_iter_peek_all(iter, &b->keys)) &&
(c = bkey_cmp_packed(f, k, &insert->k)) <= 0) {
if (!c && !bkey_deleted(k)) {
k->type = KEY_TYPE_DELETED;
@@ -607,8 +614,10 @@ static void extent_save(struct bkey_packed *dst, struct bkey *src,
#define extent_sort_cmp(l, r) \
({ \
const struct bkey_format *_f = &b->set->data->format; \
- struct bkey _ul = bkey_unpack_key(_f, (l).k); \
- struct bkey _ur = bkey_unpack_key(_f, (r).k); \
+ struct bkey _ul = bkey_unpack_key(_f, \
+ __btree_node_offset_to_key(b, (l).k)); \
+ struct bkey _ur = bkey_unpack_key(_f, \
+ __btree_node_offset_to_key(b, (r).k)); \
\
int _c = bkey_cmp(bkey_start_pos(&_ul), bkey_start_pos(&_ur)); \
_c ? _c > 0 : (l).k < (r).k; \
@@ -624,7 +633,7 @@ static inline void extent_sort_next(struct btree_node_iter *iter,
struct btree_keys *b,
struct btree_node_iter_set *i)
{
- sort_key_next(iter, i);
+ sort_key_next(iter, b, i);
heap_sift(iter, i - iter->data, extent_sort_cmp);
}
@@ -659,14 +668,16 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
{
struct bkey_format *f = &b->set->data->format;
struct btree_node_iter_set *_l = iter->data, *_r;
- struct bkey_packed *prev = NULL, *out = bset->start;
+ struct bkey_packed *prev = NULL, *out = bset->start, *lk, *rk;
struct bkey_tup l, r;
heap_resort(iter, extent_sort_cmp);
while (!bch_btree_node_iter_end(iter)) {
+ lk = __btree_node_offset_to_key(b, _l->k);
+
if (iter->used == 1) {
- out = extent_sort_append(b, out, &prev, _l->k);
+ out = extent_sort_append(b, out, &prev, lk);
extent_sort_next(iter, b, _l);
continue;
}
@@ -676,12 +687,14 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
extent_sort_cmp(_r[0], _r[1]))
_r++;
- bkey_disassemble(&l, f, _l->k);
- bkey_disassemble(&r, f, _r->k);
+ rk = __btree_node_offset_to_key(b, _r->k);
+
+ bkey_disassemble(&l, f, lk);
+ bkey_disassemble(&r, f, rk);
/* If current key and next key don't overlap, just append */
if (bkey_cmp(l.k.p, bkey_start_pos(&r.k)) <= 0) {
- out = extent_sort_append(b, out, &prev, _l->k);
+ out = extent_sort_append(b, out, &prev, lk);
extent_sort_next(iter, b, _l);
continue;
}
@@ -705,10 +718,10 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
if (_l->k > _r->k) {
/* l wins, trim r */
if (bkey_cmp(l.k.p, r.k.p) >= 0) {
- sort_key_next(iter, _r);
+ sort_key_next(iter, b, _r);
} else {
__bch_cut_front(l.k.p, bkey_tup_to_s(&r));
- extent_save(_r->k, &r.k, f);
+ extent_save(rk, &r.k, f);
}
extent_sort_sift(iter, b, _r - iter->data);
@@ -720,7 +733,7 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
bch_cut_back(bkey_start_pos(&r.k), &tmp.k.k);
__bch_cut_front(r.k.p, bkey_tup_to_s(&l));
- extent_save(_l->k, &l.k, f);
+ extent_save(lk, &l.k, f);
extent_sort_sift(iter, b, 0);
@@ -728,7 +741,7 @@ void bch_extent_sort_fix_overlapping(struct btree_keys *b,
bkey_to_packed(&tmp.k));
} else {
bch_cut_back(bkey_start_pos(&r.k), &l.k);
- extent_save(_l->k, &l.k, f);
+ extent_save(lk, &l.k, f);
}
}
@@ -1764,7 +1777,7 @@ static bool bch_extent_merge_inline(struct btree_keys *b,
* if we don't find this bset in the iterator we already got to
* the end of that bset, so start searching from the end.
*/
- k = bch_btree_node_iter_bset_pos(iter, t->data) ?:
+ k = bch_btree_node_iter_bset_pos(iter, b, t->data) ?:
bkey_prev(b, t, bset_bkey_last(t->data));
if (m == l) {