diff options
author | Kent Overstreet <kent.overstreet@gmail.com> | 2016-11-05 06:13:25 -0800 |
---|---|---|
committer | Kent Overstreet <kent.overstreet@gmail.com> | 2017-01-18 21:40:52 -0900 |
commit | 81dc24bfc42e614c8abe5137904771acf4498f02 (patch) | |
tree | f17ff21adf4ebead8bae040f2c7b92769476940f | |
parent | e629154070766ca8c23642f38e4a404be1a89046 (diff) |
bcache: refactored/fixed bch_btree_node_iter_prev_all()
Also more btree node iter assertions
-rw-r--r-- | drivers/md/bcache/bset.c | 198 | ||||
-rw-r--r-- | drivers/md/bcache/bset.h | 48 | ||||
-rw-r--r-- | drivers/md/bcache/btree_io.c | 4 |
3 files changed, 141 insertions, 109 deletions
diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c index 5113ae96b5a1..3cba1381d58f 100644 --- a/drivers/md/bcache/bset.c +++ b/drivers/md/bcache/bset.c @@ -48,22 +48,6 @@ struct bset_tree *bch_bkey_to_bset(struct btree_keys *b, struct bkey_packed *k) * by the time we actually do the insert will all be deleted. */ -#ifdef CONFIG_BCACHE_DEBUG - -static bool keys_out_of_order(const struct bkey_format *f, - const struct bkey_packed *prev, - const struct bkey_packed *next, - bool is_extents) -{ - struct bkey nextu = bkey_unpack_key(f, next); - - return bkey_cmp_left_packed(f, prev, bkey_start_pos(&nextu)) > 0 || - ((is_extents - ? !bkey_deleted(next) - : !bkey_deleted(prev)) && - !bkey_cmp_packed(f, prev, next)); -} - void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned set) { struct bkey_format *f = &b->format; @@ -107,6 +91,41 @@ void bch_dump_bucket(struct btree_keys *b) console_unlock(); } +void bch_dump_btree_node_iter(struct btree_keys *b, + struct btree_node_iter *iter) +{ + struct btree_node_iter_set *set; + + printk(KERN_ERR "btree node iter with %u sets:\n", b->nsets + 1); + + btree_node_iter_for_each(iter, set) { + struct bkey_packed *k = __btree_node_offset_to_key(b, set->k); + struct bset_tree *t = bch_bkey_to_bset(b, k); + struct bkey uk = bkey_unpack_key(&b->format, k); + char buf[100]; + + bch_bkey_to_text(buf, sizeof(buf), &uk); + printk(KERN_ERR "set %zu key %zi/%u: %s\n", t - b->set, + k->_data - t->data->_data, t->data->u64s, buf); + } +} + +#ifdef CONFIG_BCACHE_DEBUG + +static bool keys_out_of_order(const struct bkey_format *f, + const struct bkey_packed *prev, + const struct bkey_packed *next, + bool is_extents) +{ + struct bkey nextu = bkey_unpack_key(f, next); + + return bkey_cmp_left_packed(f, prev, bkey_start_pos(&nextu)) > 0 || + ((is_extents + ? !bkey_deleted(next) + : !bkey_deleted(prev)) && + !bkey_cmp_packed(f, prev, next)); +} + void __bch_verify_btree_nr_keys(struct btree_keys *b) { unsigned i; @@ -145,30 +164,36 @@ 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) { struct btree_node_iter_set *set; struct bset_tree *t; - struct bkey_packed *k; + struct bkey_packed *k, *first; 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])); + if (!iter->used) + return; + btree_node_iter_for_each(iter, set) { k = __btree_node_offset_to_key(b, set->k); t = bch_bkey_to_bset(b, k); BUG_ON(__btree_node_offset_to_key(b, set->end) != bset_bkey_last(t->data)); + + BUG_ON(set + 1 < iter->data + iter->used && + btree_node_iter_cmp(iter, b, set[0], set[1]) > 0); } + + first = __btree_node_offset_to_key(b, iter->data[0].k); + + for (t = b->set; t <= b->set + b->nsets; t++) + if (bch_btree_node_iter_bset_pos(iter, b, t->data) == + bset_bkey_last(t->data) && + (k = bkey_prev_all(t, bset_bkey_last(t->data)))) + BUG_ON(__btree_node_iter_cmp(iter, b, k, first) > 0); } void bch_verify_key_order(struct btree_keys *b, @@ -737,6 +762,8 @@ static void bch_bset_build_unwritten_tree(struct btree_keys *b) void bch_bset_init_first(struct btree_keys *b, struct bset *i) { + BUG_ON(b->nsets); + b->set[0].data = i; memset(i, 0, sizeof(*i)); get_random_bytes(&i->seq, sizeof(i->seq)); @@ -748,6 +775,8 @@ EXPORT_SYMBOL(bch_bset_init_first); void bch_bset_init_next(struct btree_keys *b, struct bset *i) { + BUG_ON(b->nsets + 1 == MAX_BSETS); + b->set[++b->nsets].data = i; memset(i, 0, sizeof(*i)); i->seq = b->set->data->seq; @@ -830,7 +859,7 @@ static struct bkey_packed *__bkey_prev(struct bset_tree *t, struct bkey_packed * p = bset_has_aux_tree(t) ? tree_to_bkey(t, inorder_to_tree(j, t)) : table_to_bkey(t, j); - } while (p == k); + } while (p >= k); return p; } @@ -1265,51 +1294,6 @@ 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) -{ - s64 c = bkey_cmp_packed(&b->format, l, r); - - /* - * For non extents, when keys compare equal the deleted keys have to - * come first - so that bch_btree_node_iter_next_check() can detect - * duplicate nondeleted keys (and possibly other reasons?) - * - * For extents, bkey_deleted() is used as a proxy for k->size == 0, so - * deleted keys have to sort last. - */ - return c ? c > 0 - : iter->is_extents - ? bkey_deleted(l) > bkey_deleted(r) - : bkey_deleted(l) < bkey_deleted(r); -} - -/* - * 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) -{ - return __btree_node_iter_cmp(iter, b, - __btree_node_offset_to_key(b, l.k), - __btree_node_offset_to_key(b, r.k)); -} - -static 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) -{ - if (k != end) - iter->data[iter->used++] = (struct btree_node_iter_set) { - __btree_node_key_to_offset(b, k), - __btree_node_key_to_offset(b, end) - }; -} void bch_btree_node_iter_push(struct btree_node_iter *iter, struct btree_keys *b, const struct bkey_packed *k, @@ -1323,8 +1307,8 @@ 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)) - break; + if (btree_node_iter_cmp(iter, b, n, *pos) <= 0) + break; memmove(pos + 1, pos, (void *) (iter->data + iter->used) - (void *) pos); @@ -1380,6 +1364,8 @@ void bch_btree_node_iter_init(struct btree_node_iter *iter, struct bset_tree *t; struct bkey_packed p, *packed_search, *lossy_packed_search; + BUG_ON(b->nsets + 1 > MAX_BSETS); + switch (bkey_pack_pos_lossy(&p, search, &b->format)) { case BKEY_PACK_POS_EXACT: packed_search = &p; @@ -1453,7 +1439,7 @@ static inline void btree_node_iter_sift(struct btree_node_iter *iter, for (i = start; i + 1 < iter->used && - btree_node_iter_cmp(iter, b, iter->data[i], iter->data[i + 1]); + btree_node_iter_cmp(iter, b, iter->data[i], iter->data[i + 1]) > 0; i++) swap(iter->data[i], iter->data[i + 1]); } @@ -1462,7 +1448,9 @@ static inline void btree_node_iter_sort_two(struct btree_node_iter *iter, struct btree_keys *b, unsigned first) { - if (btree_node_iter_cmp(iter, b, iter->data[first], iter->data[first + 1])) + if (btree_node_iter_cmp(iter, b, + iter->data[first], + iter->data[first + 1]) > 0) swap(iter->data[first], iter->data[first + 1]); } @@ -1514,45 +1502,49 @@ void bch_btree_node_iter_advance(struct btree_node_iter *iter, struct bkey_packed *bch_btree_node_iter_prev_all(struct btree_node_iter *iter, struct btree_keys *b) { - struct bkey_packed *prev = NULL; - struct btree_node_iter_set *i, *prev_set = NULL; - struct bset_tree *t, *prev_t = NULL; - struct bkey_packed *k; - - for (t = b->set; t <= b->set + b->nsets; t++) { - btree_node_iter_for_each(iter, i) { - k = __btree_node_offset_to_key(b, i->k); - - if (k >= t->data->start && k < bset_bkey_last(t->data)) - goto found; - } + struct bkey_packed *k, *prev = NULL; + struct btree_node_iter_set *set; + struct bset_tree *t; + struct bset *prev_i; + unsigned end; - k = bset_bkey_last(t->data); - i = NULL; -found: - k = bkey_prev_all(t, k); + bch_btree_node_iter_verify(iter, b); + for (t = b->set; t <= b->set + b->nsets; t++) { + k = bkey_prev_all(t, + bch_btree_node_iter_bset_pos(iter, b, t->data)); if (k && - (!prev || - __btree_node_iter_cmp(iter, b, k, prev))) { + (!prev || __btree_node_iter_cmp(iter, b, k, prev) > 0)) { prev = k; - prev_set = i; - prev_t = t; + prev_i = t->data; } } if (!prev) return NULL; - if (prev_set) { - prev_set->k -= prev->u64s; - bch_btree_node_iter_sort(iter, b); - } else { - bch_btree_node_iter_push(iter, b, prev, - bset_bkey_last(prev_t->data)); - } + /* + * We're manually memmoving instead of just calling sort() to ensure the + * prev we picked ends up in slot 0 - sort won't necessarily put it + * there because of duplicate deleted keys: + */ + end = __btree_node_key_to_offset(b, bset_bkey_last(prev_i)); + btree_node_iter_for_each(iter, set) + if (set->end == end) { + memmove(&iter->data[1], + &iter->data[0], + (void *) set - (void *) &iter->data[0]); + goto out; + } - return bch_btree_node_iter_peek_all(iter, b); + memmove(&iter->data[1], + &iter->data[0], + (void *) &iter->data[iter->used] - (void *) &iter->data[0]); + iter->used++; +out: + iter->data[0].k = __btree_node_key_to_offset(b, prev); + iter->data[0].end = end; + return prev; } struct bkey_packed *bch_btree_node_iter_prev(struct btree_node_iter *iter, diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h index f4a172a306b4..6e33fe6b5b98 100644 --- a/drivers/md/bcache/bset.h +++ b/drivers/md/bcache/bset.h @@ -481,6 +481,46 @@ __btree_node_offset_to_key(struct btree_keys *b, u16 k) return (void *) ((u64 *) b->set->data + k); } +static inline int __btree_node_iter_cmp(struct btree_node_iter *iter, + struct btree_keys *b, + struct bkey_packed *l, + struct bkey_packed *r) +{ + /* + * For non extents, when keys compare equal the deleted keys have to + * come first - so that bch_btree_node_iter_next_check() can detect + * duplicate nondeleted keys (and possibly other reasons?) + * + * For extents, bkey_deleted() is used as a proxy for k->size == 0, so + * deleted keys have to sort last. + */ + return bkey_cmp_packed(&b->format, l, r) ?: iter->is_extents + ? (int) bkey_deleted(l) - (int) bkey_deleted(r) + : (int) bkey_deleted(r) - (int) bkey_deleted(l); +} + +static inline int 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) +{ + return __btree_node_iter_cmp(iter, b, + __btree_node_offset_to_key(b, l.k), + __btree_node_offset_to_key(b, r.k)); +} + +static inline 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) +{ + if (k != end) + iter->data[iter->used++] = (struct btree_node_iter_set) { + __btree_node_key_to_offset(b, k), + __btree_node_key_to_offset(b, end) + }; +} + static inline struct bkey_packed * __bch_btree_node_iter_peek_all(struct btree_node_iter *iter, struct btree_keys *b) @@ -625,10 +665,12 @@ int bch_bkey_print_bfloat(struct btree_keys *, struct bkey_packed *, /* Debug stuff */ -#ifdef CONFIG_BCACHE_DEBUG - void bch_dump_bset(struct btree_keys *, struct bset *, unsigned); void bch_dump_bucket(struct btree_keys *); +void bch_dump_btree_node_iter(struct btree_keys *, struct btree_node_iter *); + +#ifdef CONFIG_BCACHE_DEBUG + void __bch_verify_btree_nr_keys(struct btree_keys *); void bch_btree_node_iter_verify(struct btree_node_iter *, struct btree_keys *); void bch_verify_key_order(struct btree_keys *, struct btree_node_iter *, @@ -636,8 +678,6 @@ void bch_verify_key_order(struct btree_keys *, struct btree_node_iter *, #else -static inline void bch_dump_bset(struct btree_keys *b, struct bset *i, unsigned set) {} -static inline void bch_dump_bucket(struct btree_keys *b) {} static inline void __bch_verify_btree_nr_keys(struct btree_keys *b) {} static inline void bch_btree_node_iter_verify(struct btree_node_iter *iter, struct btree_keys *b) {} diff --git a/drivers/md/bcache/btree_io.c b/drivers/md/bcache/btree_io.c index 1033232307f4..d28c768a1d8b 100644 --- a/drivers/md/bcache/btree_io.c +++ b/drivers/md/bcache/btree_io.c @@ -365,8 +365,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_push(iter, &b->keys, + i->start, bset_bkey_last(i)); } err = "corrupted btree"; |