bcache: avoid creating whiteouts unnecessarily

still need to do this for extents

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();