summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKent Overstreet <kent.overstreet@gmail.com>2016-07-21 16:52:27 -0800
committerKent Overstreet <kent.overstreet@gmail.com>2016-07-30 01:13:52 -0800
commit942a8988055dafee337a3d138e1d6190d36a4a63 (patch)
tree838b2e291378e4a767650b9e9958780b026ca0c9
parent2ed905b595ebeb0b2a741a08258fbc91f66b1061 (diff)
bcache: kill btree_node_iter->used
-rw-r--r--drivers/md/bcache/bset.c160
-rw-r--r--drivers/md/bcache/bset.h62
-rw-r--r--drivers/md/bcache/btree_io.c10
-rw-r--r--drivers/md/bcache/extents.c18
-rw-r--r--drivers/md/bcache/extents.h8
-rw-r--r--drivers/md/bcache/util.h18
6 files changed, 190 insertions, 86 deletions
diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c
index b76b6b9a2d3e..cae3b1f02f41 100644
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@ -20,6 +20,11 @@
#include "alloc_types.h"
#include <trace/events/bcache.h>
+static inline bool btree_node_iter_set_cmp(struct btree_node_iter *,
+ struct btree_keys *,
+ struct btree_node_iter_set,
+ struct btree_node_iter_set);
+
struct bset_tree *bch_bkey_to_bset(struct btree_keys *b, struct bkey_packed *k)
{
struct bset_tree *t;
@@ -162,11 +167,6 @@ static void bch_btree_node_iter_next_check(struct btree_node_iter *iter,
}
}
-static inline bool btree_node_iter_cmp(struct btree_node_iter *,
- struct btree_keys *,
- struct btree_node_iter_set,
- struct btree_node_iter_set);
-
void bch_btree_node_iter_verify(struct btree_node_iter *iter,
struct btree_keys *b)
{
@@ -174,11 +174,10 @@ void bch_btree_node_iter_verify(struct btree_node_iter *iter,
struct bset_tree *t;
struct bkey_packed *k;
- BUG_ON(iter->used > MAX_BSETS);
-
btree_node_iter_for_each(iter, set) {
- BUG_ON(set + 1 < iter->data + iter->used &&
- btree_node_iter_cmp(iter, b, set[0], set[1]));
+ BUG_ON(set + 1 < iter->data + MAX_BSETS &&
+ set[1].k != set[1].end &&
+ btree_node_iter_set_cmp(iter, b, set[0], set[1]));
k = __btree_node_offset_to_key(b, set->k);
t = bch_bkey_to_bset(b, k);
@@ -1231,10 +1230,10 @@ static struct bkey_packed *bch_bset_search(struct btree_keys *b,
/* Btree node iterator */
-static inline bool __btree_node_iter_cmp(struct btree_node_iter *iter,
- struct btree_keys *b,
- struct bkey_packed *l,
- struct bkey_packed *r)
+static inline bool btree_node_iter_cmp(struct btree_keys *b,
+ bool is_extents,
+ struct bkey_packed *l,
+ struct bkey_packed *r)
{
s64 c = bkey_cmp_packed(&b->format, l, r);
@@ -1247,7 +1246,7 @@ static inline bool __btree_node_iter_cmp(struct btree_node_iter *iter,
* deleted keys have to sort last.
*/
return c ? c > 0
- : iter->is_extents
+ : is_extents
? bkey_deleted(l) > bkey_deleted(r)
: bkey_deleted(l) < bkey_deleted(r);
}
@@ -1255,21 +1254,29 @@ static inline bool __btree_node_iter_cmp(struct btree_node_iter *iter,
/*
* Returns true if l > r:
*/
-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)
+static inline bool btree_node_iter_set_cmp(struct btree_node_iter *iter,
+ struct btree_keys *b,
+ struct btree_node_iter_set l,
+ struct btree_node_iter_set r)
{
- return __btree_node_iter_cmp(iter, b,
+ return btree_node_iter_cmp(b, iter->is_extents,
__btree_node_offset_to_key(b, l.k),
__btree_node_offset_to_key(b, r.k));
}
+#define btree_node_iter_cmp_heap(_l, _r) \
+ (btree_node_iter_cmp(b, (iter)->is_extents, \
+ __btree_node_offset_to_key(b, (_l).k), \
+ __btree_node_offset_to_key(b, (_r).k)))
+
void bch_btree_node_iter_push(struct btree_node_iter *iter,
struct btree_keys *b,
const struct bkey_packed *k,
const struct bkey_packed *end)
{
+ EBUG_ON(iter->data[MAX_BSETS - 1].k !=
+ iter->data[MAX_BSETS - 1].end);
+
if (k != end) {
struct btree_node_iter_set *pos, n =
((struct btree_node_iter_set) {
@@ -1278,12 +1285,15 @@ void bch_btree_node_iter_push(struct btree_node_iter *iter,
});
btree_node_iter_for_each(iter, pos)
- if (!btree_node_iter_cmp(iter, b, n, *pos))
+ if (!btree_node_iter_set_cmp(iter, b, n, *pos))
break;
- memmove(pos + 1, pos,
- (void *) (iter->data + iter->used) - (void *) pos);
- iter->used++;
+ EBUG_ON(pos >= iter->data + MAX_BSETS);
+
+ memmove(&pos[1],
+ &pos[0],
+ (iter->data + MAX_BSETS - (pos + 1)) *
+ sizeof(struct btree_node_iter_set));
*pos = n;
}
}
@@ -1387,8 +1397,6 @@ struct bkey_packed *bch_btree_node_iter_bset_pos(struct btree_node_iter *iter,
unsigned end = __btree_node_key_to_offset(b, bset_bkey_last(i));
struct btree_node_iter_set *set;
- BUG_ON(iter->used > MAX_BSETS);
-
btree_node_iter_for_each(iter, set)
if (set->end == end)
return __btree_node_offset_to_key(b, set->k);
@@ -1402,11 +1410,10 @@ static inline void btree_node_iter_sift(struct btree_node_iter *iter,
{
unsigned i;
- BUG_ON(iter->used > MAX_BSETS);
-
for (i = start;
- i + 1 < iter->used &&
- btree_node_iter_cmp(iter, b, iter->data[i], iter->data[i + 1]);
+ i + 1 < MAX_BSETS &&
+ iter->data[i + 1].k != iter->data[i + 1].end &&
+ btree_node_iter_set_cmp(iter, b, iter->data[i], iter->data[i + 1]);
i++)
swap(iter->data[i], iter->data[i + 1]);
}
@@ -1416,9 +1423,7 @@ void bch_btree_node_iter_sort(struct btree_node_iter *iter,
{
int i;
- BUG_ON(iter->used > MAX_BSETS);
-
- for (i = iter->used - 1; i >= 0; --i)
+ for (i = MAX_BSETS - 1; i >= 0; --i)
btree_node_iter_sift(iter, b, i);
}
EXPORT_SYMBOL(bch_btree_node_iter_sort);
@@ -1436,11 +1441,16 @@ void bch_btree_node_iter_advance(struct btree_node_iter *iter,
iter->data->k += __bch_btree_node_iter_peek_all(iter, b)->u64s;
- BUG_ON(iter->data->k > iter->data->end);
+ EBUG_ON(iter->data->k > iter->data->end);
if (iter->data->k == iter->data->end) {
- BUG_ON(iter->used == 0);
- iter->data[0] = iter->data[--iter->used];
+ struct btree_node_iter_set tmp = iter->data[0];
+
+ memmove(&iter->data[0],
+ &iter->data[1],
+ sizeof(iter->data[0]) * (MAX_BSETS - 1));
+
+ iter->data[MAX_BSETS - 1] = tmp;
}
btree_node_iter_sift(iter, b, 0);
@@ -1474,7 +1484,7 @@ found:
if (k &&
(!prev ||
- __btree_node_iter_cmp(iter, b, k, prev))) {
+ btree_node_iter_cmp(b, iter->is_extents, k, prev))) {
prev = k;
prev_set = i;
prev_t = t;
@@ -1507,6 +1517,49 @@ EXPORT_SYMBOL(bch_btree_node_iter_peek_unpack);
/* Mergesort */
+void bch_btree_node_iter_large_push(struct btree_node_iter_large *iter,
+ struct btree_keys *b,
+ const struct bkey_packed *k,
+ const struct bkey_packed *end)
+{
+ if (k != end) {
+ struct btree_node_iter_set n =
+ ((struct btree_node_iter_set) {
+ __btree_node_key_to_offset(b, k),
+ __btree_node_key_to_offset(b, end)
+ });
+
+ __heap_add(iter, n, btree_node_iter_cmp_heap);
+ }
+}
+
+void bch_btree_node_iter_large_init(struct btree_node_iter_large *iter,
+ struct btree_keys *b)
+{
+ struct bset_tree *t;
+
+ iter->used = 0;
+
+ for (t = b->set; t <= b->set + b->nsets; t++)
+ bch_btree_node_iter_large_push(iter, b,
+ t->data->start,
+ bset_bkey_last(t->data));
+}
+
+void bch_btree_node_iter_large_advance(struct btree_node_iter_large *iter,
+ struct btree_keys *b)
+{
+ iter->data->k += __btree_node_offset_to_key(b, iter->data->k)->u64s;
+
+ EBUG_ON(!iter->used);
+ EBUG_ON(iter->data->k > iter->data->end);
+
+ if (iter->data->k == iter->data->end)
+ heap_del(iter, 0, btree_node_iter_cmp_heap);
+ else
+ heap_sift(iter, 0, btree_node_iter_cmp_heap);
+}
+
void bch_bset_sort_state_free(struct bset_sort_state *state)
{
mempool_exit(&state->pool);
@@ -1528,12 +1581,12 @@ EXPORT_SYMBOL(bch_bset_sort_state_init);
/* No repacking: */
static struct btree_nr_keys btree_mergesort_simple(struct btree_keys *b,
- struct bset *bset,
- struct btree_node_iter *iter)
+ struct bset *bset,
+ struct btree_node_iter_large *iter)
{
struct bkey_packed *in, *out = bset->start;
- while ((in = bch_btree_node_iter_next_all(iter, b))) {
+ while ((in = bch_btree_node_iter_large_next_all(iter, b))) {
if (!bkey_deleted(in)) {
/* XXX: need better bkey_copy */
memcpy(out, in, bkey_bytes(in));
@@ -1549,7 +1602,7 @@ static struct btree_nr_keys btree_mergesort_simple(struct btree_keys *b,
static struct btree_nr_keys btree_mergesort(struct btree_keys *dst,
struct bset *dst_set,
struct btree_keys *src,
- struct btree_node_iter *iter,
+ struct btree_node_iter_large *iter,
ptr_filter_fn filter)
{
struct bkey_format *in_f = &src->format;
@@ -1562,7 +1615,7 @@ static struct btree_nr_keys btree_mergesort(struct btree_keys *dst,
memset(&nr, 0, sizeof(nr));
- while ((in = bch_btree_node_iter_next_all(iter, src))) {
+ while ((in = bch_btree_node_iter_large_next_all(iter, src))) {
if (bkey_deleted(in))
continue;
@@ -1585,10 +1638,10 @@ static struct btree_nr_keys btree_mergesort(struct btree_keys *dst,
/* Sort, repack, and merge extents */
static struct btree_nr_keys btree_mergesort_extents(struct btree_keys *dst,
- struct bset *dst_set,
- struct btree_keys *src,
- struct btree_node_iter *iter,
- ptr_filter_fn filter)
+ struct bset *dst_set,
+ struct btree_keys *src,
+ struct btree_node_iter_large *iter,
+ ptr_filter_fn filter)
{
struct bkey_format *in_f = &src->format;
struct bkey_format *out_f = &dst->format;
@@ -1600,7 +1653,7 @@ static struct btree_nr_keys btree_mergesort_extents(struct btree_keys *dst,
memset(&nr, 0, sizeof(nr));
- while ((k = bch_btree_node_iter_next_all(iter, src))) {
+ while ((k = bch_btree_node_iter_large_next_all(iter, src))) {
if (bkey_deleted(k))
continue;
@@ -1652,22 +1705,21 @@ static struct btree_nr_keys btree_mergesort_extents(struct btree_keys *dst,
}
struct btree_nr_keys bch_sort_bsets(struct bset *dst, struct btree_keys *b,
- unsigned from, struct btree_node_iter *iter,
- btree_keys_sort_fn sort,
- struct bset_sort_state *state)
+ unsigned from, struct btree_node_iter_large *iter,
+ btree_keys_sort_fn sort, struct bset_sort_state *state)
{
u64 start_time = local_clock();
- struct btree_node_iter _iter;
+ struct btree_node_iter_large _iter;
struct btree_nr_keys nr;
if (!iter) {
struct bset_tree *t;
iter = &_iter;
- __bch_btree_node_iter_init(iter, b);
+ __bch_btree_node_iter_large_init(iter, b);
for (t = b->set + from; t <= b->set + b->nsets; t++)
- bch_btree_node_iter_push(iter, b,
+ bch_btree_node_iter_large_push(iter, b,
t->data->start,
bset_bkey_last(t->data));
}
@@ -1702,10 +1754,10 @@ void bch_btree_sort_into(struct btree_keys *dst,
struct bset_sort_state *state)
{
u64 start_time = local_clock();
- struct btree_node_iter iter;
+ struct btree_node_iter_large iter;
struct btree_nr_keys nr;
- bch_btree_node_iter_init_from_start(&iter, src);
+ bch_btree_node_iter_large_init(&iter, src);
if (!dst->ops->is_extents)
nr = btree_mergesort(dst, dst->set->data,
diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h
index 46798c19e4bf..df13473506ab 100644
--- a/drivers/md/bcache/bset.h
+++ b/drivers/md/bcache/bset.h
@@ -443,7 +443,6 @@ static inline enum bch_extent_overlap bch_extent_overlap(const struct bkey *k,
struct btree_node_iter {
u8 is_extents;
- u16 used;
struct btree_node_iter_set {
u16 k, end;
@@ -453,8 +452,8 @@ struct btree_node_iter {
static inline void __bch_btree_node_iter_init(struct btree_node_iter *iter,
struct btree_keys *b)
{
- iter->used = 0;
iter->is_extents = b->ops->is_extents;
+ memset(iter->data, 0, sizeof(iter->data));
}
void bch_btree_node_iter_push(struct btree_node_iter *, struct btree_keys *,
@@ -473,12 +472,13 @@ void bch_btree_node_iter_advance(struct btree_node_iter *, struct btree_keys *);
#define btree_node_iter_for_each(_iter, _set) \
for (_set = (_iter)->data; \
- _set < (_iter)->data + (_iter)->used; \
+ _set < (_iter)->data + MAX_BSETS && \
+ _set->k != _set->end; \
_set++)
static inline bool bch_btree_node_iter_end(struct btree_node_iter *iter)
{
- return !iter->used;
+ return iter->data[0].k == iter->data[0].end;
}
static inline u16
@@ -558,6 +558,55 @@ struct bkey_s_c bch_btree_node_iter_peek_unpack(struct btree_node_iter *,
/* Sorting */
+struct btree_node_iter_large {
+ u8 is_extents;
+ u16 used;
+
+ struct btree_node_iter_set data[MAX_BSETS];
+};
+
+static inline void
+__bch_btree_node_iter_large_init(struct btree_node_iter_large *iter,
+ struct btree_keys *b)
+{
+ iter->used = 0;
+ iter->is_extents = b->ops->is_extents;
+}
+
+void bch_btree_node_iter_large_advance(struct btree_node_iter_large *,
+ struct btree_keys *);
+
+void bch_btree_node_iter_large_push(struct btree_node_iter_large *,
+ struct btree_keys *,
+ const struct bkey_packed *,
+ const struct bkey_packed *);
+
+static inline bool bch_btree_node_iter_large_end(struct btree_node_iter_large *iter)
+{
+ return !iter->used;
+}
+
+static inline struct bkey_packed *
+bch_btree_node_iter_large_peek_all(struct btree_node_iter_large *iter,
+ struct btree_keys *b)
+{
+ return bch_btree_node_iter_large_end(iter)
+ ? NULL
+ : __btree_node_offset_to_key(b, iter->data->k);
+}
+
+static inline struct bkey_packed *
+bch_btree_node_iter_large_next_all(struct btree_node_iter_large *iter,
+ struct btree_keys *b)
+{
+ struct bkey_packed *ret = bch_btree_node_iter_large_peek_all(iter, b);
+
+ if (ret)
+ bch_btree_node_iter_large_advance(iter, b);
+
+ return ret;
+}
+
struct bset_sort_state {
mempool_t pool;
@@ -568,15 +617,14 @@ struct bset_sort_state {
};
typedef struct btree_nr_keys (*btree_keys_sort_fn)(struct btree_keys *,
- struct bset *,
- struct btree_node_iter *);
+ struct bset *, struct btree_node_iter_large *);
void bch_bset_sort_state_free(struct bset_sort_state *);
int bch_bset_sort_state_init(struct bset_sort_state *, unsigned,
struct time_stats *times);
struct btree_nr_keys bch_sort_bsets(struct bset *, struct btree_keys *,
- unsigned, struct btree_node_iter *,
+ unsigned, struct btree_node_iter_large *,
btree_keys_sort_fn,
struct bset_sort_state *);
diff --git a/drivers/md/bcache/btree_io.c b/drivers/md/bcache/btree_io.c
index 57c283e5d371..2e362003a44d 100644
--- a/drivers/md/bcache/btree_io.c
+++ b/drivers/md/bcache/btree_io.c
@@ -17,7 +17,7 @@
static void btree_node_sort(struct cache_set *c, struct btree *b,
struct btree_iter *iter, unsigned from,
- struct btree_node_iter *node_iter,
+ struct btree_node_iter_large *node_iter,
btree_keys_sort_fn sort, bool is_write_locked)
{
struct btree_node *out;
@@ -262,12 +262,12 @@ void bch_btree_node_read_done(struct cache_set *c, struct btree *b,
{
struct btree_node_entry *bne;
struct bset *i = &b->data->keys;
- struct btree_node_iter *iter;
+ struct btree_node_iter_large *iter;
const char *err;
int ret;
iter = mempool_alloc(&c->fill_iter, GFP_NOIO);
- __bch_btree_node_iter_init(iter, &b->keys);
+ __bch_btree_node_iter_large_init(iter, &b->keys);
err = "dynamic fault";
if (bch_meta_read_fault("btree"))
@@ -354,8 +354,8 @@ void bch_btree_node_read_done(struct cache_set *c, struct btree *b,
if (ret)
continue;
- bch_btree_node_iter_push(iter, &b->keys,
- i->start, bset_bkey_last(i));
+ bch_btree_node_iter_large_push(iter, &b->keys,
+ i->start, bset_bkey_last(i));
}
err = "corrupted btree";
diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c
index d8b2f7797a70..10ce62fb673b 100644
--- a/drivers/md/bcache/extents.c
+++ b/drivers/md/bcache/extents.c
@@ -23,7 +23,7 @@
static bool __bch_extent_normalize(struct cache_set *, struct bkey_s, bool);
-static void sort_key_next(struct btree_node_iter *iter,
+static void sort_key_next(struct btree_node_iter_large *iter,
struct btree_keys *b,
struct btree_node_iter_set *i)
{
@@ -49,7 +49,7 @@ static void sort_key_next(struct btree_node_iter *iter,
_c ? _c > 0 : (l).k > (r).k; \
})
-static inline bool should_drop_next_key(struct btree_node_iter *iter,
+static inline bool should_drop_next_key(struct btree_node_iter_large *iter,
struct btree_keys *b)
{
const struct bkey_format *f = &b->format;
@@ -76,8 +76,8 @@ static inline bool should_drop_next_key(struct btree_node_iter *iter,
}
struct btree_nr_keys bch_key_sort_fix_overlapping(struct btree_keys *b,
- struct bset *bset,
- struct btree_node_iter *iter)
+ struct bset *bset,
+ struct btree_node_iter_large *iter)
{
struct bkey_packed *out = bset->start;
struct btree_nr_keys nr;
@@ -86,7 +86,7 @@ struct btree_nr_keys bch_key_sort_fix_overlapping(struct btree_keys *b,
heap_resort(iter, key_sort_cmp);
- while (!bch_btree_node_iter_end(iter)) {
+ while (!bch_btree_node_iter_large_end(iter)) {
if (!should_drop_next_key(iter, b)) {
struct bkey_packed *k =
__btree_node_offset_to_key(b, iter->data->k);
@@ -679,13 +679,13 @@ static void extent_save(struct btree_keys *b, struct btree_node_iter *iter,
_c ? _c > 0 : (l).k < (r).k; \
})
-static inline void extent_sort_sift(struct btree_node_iter *iter,
+static inline void extent_sort_sift(struct btree_node_iter_large *iter,
struct btree_keys *b, size_t i)
{
heap_sift(iter, i, extent_sort_cmp);
}
-static inline void extent_sort_next(struct btree_node_iter *iter,
+static inline void extent_sort_next(struct btree_node_iter_large *iter,
struct btree_keys *b,
struct btree_node_iter_set *i)
{
@@ -723,7 +723,7 @@ static struct bkey_packed *extent_sort_append(struct btree_keys *b,
struct btree_nr_keys bch_extent_sort_fix_overlapping(struct btree_keys *b,
struct bset *bset,
- struct btree_node_iter *iter)
+ struct btree_node_iter_large *iter)
{
struct bkey_format *f = &b->format;
struct btree_node_iter_set *_l = iter->data, *_r;
@@ -736,7 +736,7 @@ struct btree_nr_keys bch_extent_sort_fix_overlapping(struct btree_keys *b,
heap_resort(iter, extent_sort_cmp);
- while (!bch_btree_node_iter_end(iter)) {
+ while (!bch_btree_node_iter_large_end(iter)) {
lk = __btree_node_offset_to_key(b, _l->k);
if (iter->used == 1) {
diff --git a/drivers/md/bcache/extents.h b/drivers/md/bcache/extents.h
index ee74bfeea3a5..eab98760cd9c 100644
--- a/drivers/md/bcache/extents.h
+++ b/drivers/md/bcache/extents.h
@@ -12,11 +12,11 @@ struct btree_insert_trans;
struct btree_trans_entry;
struct btree_nr_keys bch_key_sort_fix_overlapping(struct btree_keys *,
- struct bset *,
- struct btree_node_iter *);
+ struct bset *,
+ struct btree_node_iter_large *);
struct btree_nr_keys bch_extent_sort_fix_overlapping(struct btree_keys *,
- struct bset *,
- struct btree_node_iter *);
+ struct bset *,
+ struct btree_node_iter_large *);
enum btree_insert_ret
bch_insert_fixup_key(struct btree_insert_trans *,
diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h
index 188630b418ed..82e5f3ef6048 100644
--- a/drivers/md/bcache/util.h
+++ b/drivers/md/bcache/util.h
@@ -116,16 +116,20 @@ do { \
} \
} while (0)
+#define __heap_add(h, d, cmp) \
+do { \
+ size_t _i = (h)->used++; \
+ (h)->data[_i] = d; \
+ \
+ heap_sift_down(h, _i, cmp); \
+ heap_sift(h, _i, cmp); \
+} while (0)
+
#define heap_add(h, d, cmp) \
({ \
bool _r = !heap_full(h); \
- if (_r) { \
- size_t _i = (h)->used++; \
- (h)->data[_i] = d; \
- \
- heap_sift_down(h, _i, cmp); \
- heap_sift(h, _i, cmp); \
- } \
+ if (_r) \
+ __heap_add(h, d, cmp); \
_r; \
})