diff options
author | Kent Overstreet <kent.overstreet@gmail.com> | 2016-10-24 15:33:55 -0800 |
---|---|---|
committer | Kent Overstreet <kent.overstreet@gmail.com> | 2016-11-13 13:56:15 -0900 |
commit | 3d3859ff66e1e5f244f9fcee98cb71682e435dce (patch) | |
tree | ef86fc3e044ad9726ab06429a834e02dcc8f5b3a | |
parent | 4a8be6c98358a1d67a9771efa1186b7d11b66c90 (diff) |
bcache: avoid creating whiteouts unnecessarily
still need to do this for extents
-rw-r--r-- | drivers/md/bcache/bset.c | 97 | ||||
-rw-r--r-- | drivers/md/bcache/bset.h | 5 | ||||
-rw-r--r-- | drivers/md/bcache/btree_iter.c | 19 | ||||
-rw-r--r-- | drivers/md/bcache/btree_iter.h | 2 | ||||
-rw-r--r-- | drivers/md/bcache/btree_update.c | 15 | ||||
-rw-r--r-- | drivers/md/bcache/extents.c | 10 |
6 files changed, 76 insertions, 72 deletions
diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c index 6f2efcc5ff54..88ce99ee2e02 100644 --- a/drivers/md/bcache/bset.c +++ b/drivers/md/bcache/bset.c @@ -506,7 +506,7 @@ void inorder_test(void) static struct bkey_packed *cacheline_to_bkey(struct bset_tree *t, unsigned cacheline, - unsigned offset) + int offset) { return ((void *) t->data) + cacheline * BSET_CACHELINE + offset * 8; } @@ -872,41 +872,49 @@ EXPORT_SYMBOL(bch_bset_fix_invalidated_key); static void bch_bset_fix_lookup_table(struct btree_keys *b, struct bset_tree *t, - struct bkey_packed *k) + struct bkey_packed *where, + int shift) { - unsigned shift = k->u64s; - unsigned j = bkey_to_cacheline(t, k); + struct bkey_packed *k; + unsigned j; BUG_ON(bset_has_aux_tree(t)); - if (bset_aux_tree_type(t) == BSET_AUX_TREE_NONE) + if (bset_aux_tree_type(t) != BSET_HAS_UNWRITTEN_TABLE) return; - /* k is the key we just inserted; we need to find the entry in the - * lookup table for the first key that is strictly greater than k: - * it's either k's cacheline or the next one - */ - while (j < t->size && - table_to_bkey(t, j) <= k) + /* Find first entry in the lookup table strictly greater than where: */ + j = bkey_to_cacheline(t, where); + while (j < t->size && table_to_bkey(t, j) <= where) j++; + BUG_ON(!j); + /* Adjust all the lookup table entries, and find a new key for any that * have gotten too big */ for (; j < t->size; j++) { /* Avoid overflow - might temporarily be larger than a u8 */ - unsigned p = (unsigned) t->prev[j] + shift; + int new_offset = (int) t->prev[j] + shift; - if (p > 7) { - k = table_to_bkey(t, j - 1); + if (new_offset < 0 || + new_offset > 7) { + k = new_offset < 0 + ? cacheline_to_bkey(t, j, new_offset) + : table_to_bkey(t, j - 1); - while (k < cacheline_to_bkey(t, j, 0)) + while (k < cacheline_to_bkey(t, j, 0)) { k = bkey_next(k); + if (k == bset_bkey_last(t->data)) { + t->size = j; + return; + } + } - p = bkey_to_cacheline_offset(t, j, k); + new_offset = bkey_to_cacheline_offset(t, j, k); } - t->prev[j] = p; + t->prev[j] = new_offset; } BUG_ON(t->size > bset_tree_capacity(b, t)); @@ -979,7 +987,7 @@ struct bkey_packed *bch_bset_insert(struct btree_keys *b, memcpy(bkeyp_val(f, where), &insert->v, bkeyp_val_bytes(f, src)); - bch_bset_fix_lookup_table(b, t, where); + bch_bset_fix_lookup_table(b, t, where, where->u64s); if (!bkey_is_whiteout(&insert->k)) btree_keys_account_key_add(&b->nr, b->nsets, src); @@ -990,53 +998,50 @@ struct bkey_packed *bch_bset_insert(struct btree_keys *b, } /* @where must compare equal to @insert */ -bool bch_bset_try_overwrite(struct btree_keys *b, - struct btree_node_iter *iter, - struct bset_tree *t, - struct bkey_packed *where, - struct bkey_i *insert) +int bch_bset_overwrite(struct btree_keys *b, + struct btree_node_iter *iter, + struct bkey_packed *where, + struct bkey_i *insert) { struct bkey_format *f = &b->format; + struct bset_tree *t = bset_tree_last(b); + struct bset *i = t->data; struct bkey_packed packed, *src = bkey_to_packed(insert); - - EBUG_ON(bkey_cmp_left_packed(f, where, insert->k.p)); - EBUG_ON(bkey_deleted(where)); + int shift; /* - * If insert is a deletion overwriting is handled by - * bch_btree_bset_insert_key(), since in that case we're replacing a non - * deleted key with a deleted key and we have to fix iterators: + * we know where isn't a deleted key, because if it was the iterator + * would have skipped past it: */ - if (bkey_deleted(&insert->k)) - return false; - - if (t != bset_tree_last(b)) - return false; - - if (where->u64s == src->u64s) - goto overwrite; - - if (!bkey_pack_key(&packed, &insert->k, f)) - return false; + EBUG_ON(bkey_cmp_left_packed(f, where, insert->k.p)); + EBUG_ON(bkey_deleted(where)); - src = &packed; - if (where->u64s == src->u64s) - goto overwrite; + if (bkey_pack_key(&packed, &insert->k, f)) + src = &packed; - return false; -overwrite: if (!bkey_packed_is_whiteout(b, where)) btree_keys_account_key_drop(&b->nr, b->nsets, where); if (!bkey_is_whiteout(&insert->k)) btree_keys_account_key_add(&b->nr, b->nsets, src); + + shift = src->u64s - where->u64s; + if (shift) { + memmove(where->_data + src->u64s, + bkey_next(where), + (void *) bset_bkey_last(i) - (void *) bkey_next(where)); + le16_add_cpu(&i->u64s, shift); + } + memcpy(where, src, bkeyp_key_bytes(f, src)); memcpy(bkeyp_val(f, where), &insert->v, bkeyp_val_bytes(f, src)); + bch_bset_fix_lookup_table(b, t, where, shift); + bch_verify_key_order(b, iter, where); bch_verify_btree_nr_keys(b); - return true; + return shift; } /* Lookup */ diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h index f020bf9745af..8208c05eadd8 100644 --- a/drivers/md/bcache/bset.h +++ b/drivers/md/bcache/bset.h @@ -325,9 +325,8 @@ void bch_bset_fix_invalidated_key(struct btree_keys *, struct bset_tree *, struct bkey_packed *bch_bset_insert(struct btree_keys *, struct btree_node_iter *, struct bkey_i *); -bool bch_bset_try_overwrite(struct btree_keys *, struct btree_node_iter *, - struct bset_tree *, struct bkey_packed *, - struct bkey_i *); +int bch_bset_overwrite(struct btree_keys *, struct btree_node_iter *, + struct bkey_packed *, struct bkey_i *); /* Bkey utility code */ diff --git a/drivers/md/bcache/btree_iter.c b/drivers/md/bcache/btree_iter.c index 980fd645734a..74bc00cb3b5a 100644 --- a/drivers/md/bcache/btree_iter.c +++ b/drivers/md/bcache/btree_iter.c @@ -246,20 +246,19 @@ static void __bch_btree_node_iter_fix(struct btree_iter *iter, struct btree_node_iter *node_iter, struct bset_tree *t, struct bkey_packed *where, - bool overwrote) + int shift) { struct bkey_format *f = &b->format; const struct bkey_packed *end = bset_bkey_last(t->data); struct btree_node_iter_set *set; - unsigned shift = overwrote ? 0 : where->u64s; unsigned offset = __btree_node_key_to_offset(b, where); - unsigned old_end = __btree_node_key_to_offset(b, end) - shift; + unsigned old_end = (int) __btree_node_key_to_offset(b, end) - shift; bool iter_pos_before_new = btree_iter_pos_cmp_packed(f, iter->pos, where, iter->is_extents); btree_node_iter_for_each(node_iter, set) if (set->end == old_end) { - set->end += shift; + set->end = (int) set->end + shift; /* * When we inserted at @where, the key we inserted - the @@ -277,8 +276,8 @@ static void __bch_btree_node_iter_fix(struct btree_iter *iter, if (set->k >= offset) { if (iter_pos_before_new) set->k = offset; - else - set->k += shift; + else if (shift > 0 || set->k > offset) + set->k = (int) set->k + shift; } /* @@ -306,23 +305,23 @@ void bch_btree_node_iter_fix(struct btree_iter *iter, struct btree_node_iter *node_iter, struct bset_tree *t, struct bkey_packed *where, - bool overwrote) + int shift) { struct btree_iter *linked; if (node_iter != &iter->node_iters[b->level]) __bch_btree_node_iter_fix(iter, &b->keys, node_iter, - t, where, overwrote); + t, where, shift); if (iter->nodes[b->level] == b) __bch_btree_node_iter_fix(iter, &b->keys, &iter->node_iters[b->level], - t, where, overwrote); + t, where, shift); for_each_linked_btree_node(iter, b, linked) __bch_btree_node_iter_fix(linked, &b->keys, &linked->node_iters[b->level], - t, where, overwrote); + t, where, shift); bch_btree_iter_verify(iter, b); } diff --git a/drivers/md/bcache/btree_iter.h b/drivers/md/bcache/btree_iter.h index 9539734fdadc..18383c8b217a 100644 --- a/drivers/md/bcache/btree_iter.h +++ b/drivers/md/bcache/btree_iter.h @@ -123,7 +123,7 @@ static inline void bch_btree_iter_verify(struct btree_iter *iter, void bch_btree_node_iter_fix(struct btree_iter *, struct btree *, struct btree_node_iter *, struct bset_tree *, - struct bkey_packed *, bool); + struct bkey_packed *, int); bool bch_btree_iter_upgrade(struct btree_iter *); int bch_btree_iter_unlock(struct btree_iter *); diff --git a/drivers/md/bcache/btree_update.c b/drivers/md/bcache/btree_update.c index 515e1355e8cb..8fb06fc14f86 100644 --- a/drivers/md/bcache/btree_update.c +++ b/drivers/md/bcache/btree_update.c @@ -660,7 +660,7 @@ void bch_btree_bset_insert(struct btree_iter *iter, bch_btree_node_iter_fix(iter, b, node_iter, bset_tree_last(&b->keys), - where, false); + where, where->u64s); } /* Handle overwrites and do insert, for non extents: */ @@ -677,8 +677,12 @@ void bch_btree_bset_insert_key(struct btree_iter *iter, if (k && !bkey_cmp_packed(f, k, &insert->k)) { t = bch_bkey_to_bset(&b->keys, k); - if (bch_bset_try_overwrite(&b->keys, node_iter, t, k, insert)) { - bch_btree_iter_verify(iter, b); + if (t == bset_tree_last(&b->keys)) { + int shift = bch_bset_overwrite(&b->keys, + node_iter, k, insert); + if (shift || bkey_deleted(&insert->k)) + bch_btree_node_iter_fix(iter, b, node_iter, + t, k, shift); return; } @@ -687,10 +691,7 @@ void bch_btree_bset_insert_key(struct btree_iter *iter, t - b->keys.set, k); k->type = KEY_TYPE_DELETED; - bch_btree_node_iter_fix(iter, b, node_iter, t, k, true); - - if (t == bset_tree_last(&b->keys) && bkey_deleted(&insert->k)) - return; + bch_btree_node_iter_fix(iter, b, node_iter, t, k, 0); } bch_btree_bset_insert(iter, b, node_iter, insert); diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c index 5558c97d1a2a..90f3a0fff788 100644 --- a/drivers/md/bcache/extents.c +++ b/drivers/md/bcache/extents.c @@ -1414,7 +1414,7 @@ bch_insert_fixup_extent(struct btree_insert *trans, * auxiliary tree. */ bch_bset_fix_invalidated_key(&b->keys, t, _k); - bch_btree_node_iter_fix(iter, b, node_iter, t, _k, true); + bch_btree_node_iter_fix(iter, b, node_iter, t, _k, 0); break; case BCH_EXTENT_OVERLAP_ALL: { @@ -1456,7 +1456,7 @@ bch_insert_fixup_extent(struct btree_insert *trans, } else { bch_bset_fix_invalidated_key(&b->keys, t, _k); bch_btree_node_iter_fix(iter, b, node_iter, t, - _k, true); + _k, 0); } break; @@ -2183,7 +2183,7 @@ static bool extent_merge_one_overlapping(struct btree_iter *iter, uk.p = new_pos; extent_save(&b->keys, node_iter, k, &uk); bch_bset_fix_invalidated_key(&b->keys, t, k); - bch_btree_node_iter_fix(iter, b, node_iter, t, k, true); + bch_btree_node_iter_fix(iter, b, node_iter, t, k, 0); return true; } } @@ -2323,7 +2323,7 @@ static bool bch_extent_merge_inline(struct btree_iter *iter, bch_btree_iter_set_pos_same_leaf(iter, li.k.k.p); bch_btree_node_iter_fix(iter, iter->nodes[0], node_iter, - t, m, true); + t, m, 0); if (!back_merge) bkey_copy(packed_to_bkey(l), &li.k); @@ -2339,7 +2339,7 @@ static bool bch_extent_merge_inline(struct btree_iter *iter, extent_i_save(b, node_iter, m, &li.k); bch_btree_node_iter_fix(iter, iter->nodes[0], node_iter, - t, m, true); + t, m, 0); return true; default: BUG(); |