summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKent Overstreet <kent.overstreet@gmail.com>2016-10-24 15:33:55 -0800
committerKent Overstreet <kent.overstreet@gmail.com>2016-11-13 13:56:15 -0900
commit3d3859ff66e1e5f244f9fcee98cb71682e435dce (patch)
treeef86fc3e044ad9726ab06429a834e02dcc8f5b3a
parent4a8be6c98358a1d67a9771efa1186b7d11b66c90 (diff)
bcache: avoid creating whiteouts unnecessarily
still need to do this for extents
-rw-r--r--drivers/md/bcache/bset.c97
-rw-r--r--drivers/md/bcache/bset.h5
-rw-r--r--drivers/md/bcache/btree_iter.c19
-rw-r--r--drivers/md/bcache/btree_iter.h2
-rw-r--r--drivers/md/bcache/btree_update.c15
-rw-r--r--drivers/md/bcache/extents.c10
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();