bcache: compact whiteouts more aggressively

6 files changed, 130 insertions, 45 deletions

diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c
index 11b5a2b1547d..4bee8ad1a956 100644
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@ -109,21 +109,18 @@ void bch_dump_bucket(struct btree_keys *b)
 
 void __bch_verify_btree_nr_keys(struct btree_keys *b)
 {
-	struct btree_node_iter iter;
+	unsigned i;
 	struct bkey_packed *k;
-	unsigned u64s = 0, packed = 0, unpacked = 0;
+	struct btree_nr_keys nr = { 0 };
 
-	for_each_btree_node_key(b, k, &iter) {
-		u64s += k->u64s;
-		if (bkey_packed(k))
-			packed++;
-		else
-			unpacked++;
-	}
+	for (i = 0; i <= b->nsets; i++)
+		for (k = b->set[i].data->start;
+		     k != bset_bkey_last(b->set[i].data);
+		     k = bkey_next(k))
+			if (!bkey_deleted(k))
+				btree_keys_account_key_add(&nr, i, k);
 
-	BUG_ON(b->nr.live_u64s		!= u64s);
-	BUG_ON(b->nr.packed_keys	!= packed);
-	BUG_ON(b->nr.unpacked_keys	!= unpacked);
+	BUG_ON(memcmp(&nr, &b->nr, sizeof(nr)));
 }
 
 static void bch_btree_node_iter_next_check(struct btree_node_iter *iter,
@@ -697,8 +694,6 @@ static void bset_alloc_tree(struct btree_keys *b, struct bset_tree *t)
 /* Only valid for the last bset: */
 static unsigned bset_tree_capacity(struct btree_keys *b, struct bset_tree *t)
 {
-	EBUG_ON(t != bset_tree_last(b));
-
 	return b->set->tree + btree_keys_cachelines(b) - t->tree;
 }
 
@@ -739,9 +734,9 @@ void bch_bset_init_next(struct btree_keys *b, struct bset *i)
 }
 EXPORT_SYMBOL(bch_bset_init_next);
 
-void bch_bset_build_written_tree(struct btree_keys *b)
+void bch_bset_build_written_tree(struct btree_keys *b,
+				 struct bset_tree *t)
 {
-	struct bset_tree *t = bset_tree_last(b);
 	struct bkey_packed *prev = NULL, *k = t->data->start;
 	unsigned j, cacheline = 1;
 
@@ -987,7 +982,7 @@ struct bkey_packed *bch_bset_insert(struct btree_keys *b,
 	bch_bset_fix_lookup_table(b, t, where);
 
 	if (!bkey_deleted(src))
-		btree_keys_account_key_add(&b->nr, src);
+		btree_keys_account_key_add(&b->nr, b->nsets, src);
 
 	bch_verify_key_order(b, iter, where);
 	bch_verify_btree_nr_keys(b);
@@ -1007,6 +1002,11 @@ bool bch_bset_try_overwrite(struct btree_keys *b,
 	EBUG_ON(bkey_cmp_left_packed(f, where, insert->k.p));
 	EBUG_ON(bkey_deleted(where));
 
+	/*
+	 * 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:
+	 */
 	if (bkey_deleted(&insert->k))
 		return false;
 
@@ -1026,9 +1026,9 @@ bool bch_bset_try_overwrite(struct btree_keys *b,
 	return false;
 overwrite:
 	if (!bkey_deleted(where))
-		btree_keys_account_key_drop(&b->nr, where);
+		btree_keys_account_key_drop(&b->nr, t - b->set, where);
 	if (!bkey_deleted(src))
-		btree_keys_account_key_add(&b->nr, src);
+		btree_keys_account_key_add(&b->nr, t - b->set, src);
 	memcpy(where, src,
 	       bkeyp_key_bytes(f, src));
 	memcpy(bkeyp_val(f, where), &insert->v,
@@ -1542,10 +1542,13 @@ EXPORT_SYMBOL(bch_bset_sort_state_init);
 
 /* No repacking: */
 static struct btree_nr_keys btree_mergesort_simple(struct btree_keys *b,
+						   unsigned from,
 						   struct bset *bset,
 						   struct btree_node_iter *iter)
 {
 	struct bkey_packed *in, *out = bset->start;
+	struct btree_nr_keys ret = b->nr;
+	unsigned i;
 
 	while ((in = bch_btree_node_iter_next_all(iter, b))) {
 		if (!bkey_deleted(in)) {
@@ -1556,7 +1559,13 @@ static struct btree_nr_keys btree_mergesort_simple(struct btree_keys *b,
 	}
 
 	bset->u64s = cpu_to_le16((u64 *) out - bset->_data);
-	return b->nr;
+
+	for (i = from + 1; i < MAX_BSETS; i++) {
+		ret.bset_u64s[from] += ret.bset_u64s[i];
+		ret.bset_u64s[i] = 0;
+	}
+
+	return ret;
 }
 
 /* Sort + repack in a new format: */
@@ -1586,7 +1595,7 @@ static struct btree_nr_keys btree_mergesort(struct btree_keys *dst,
 		else
 			bkey_unpack((void *) out, in_f, in);
 
-		btree_keys_account_key_add(&nr, out);
+		btree_keys_account_key_add(&nr, 0, out);
 		out = bkey_next(out);
 
 		BUG_ON((void *) out >
@@ -1641,7 +1650,7 @@ static struct btree_nr_keys btree_mergesort_extents(struct btree_keys *dst,
 		if (prev) {
 			bkey_pack(prev, (void *) prev, out_f);
 
-			btree_keys_account_key_add(&nr, prev);
+			btree_keys_account_key_add(&nr, 0, prev);
 			prev = bkey_next(prev);
 		} else {
 			prev = dst_set->start;
@@ -1655,7 +1664,7 @@ static struct btree_nr_keys btree_mergesort_extents(struct btree_keys *dst,
 
 	if (prev) {
 		bkey_pack(prev, (void *) prev, out_f);
-		btree_keys_account_key_add(&nr, prev);
+		btree_keys_account_key_add(&nr, 0, prev);
 		out = bkey_next(prev);
 	} else {
 		out = dst_set->start;
@@ -1697,7 +1706,7 @@ struct btree_nr_keys bch_sort_bsets(struct bset *dst, struct btree_keys *b,
 	else if (b->ops->is_extents && !from)
 		nr = btree_mergesort_extents(b, dst, b, iter, NULL);
 	else
-		nr = btree_mergesort_simple(b, dst, iter);
+		nr = btree_mergesort_simple(b, from, dst, iter);
 
 	if (!from)
 		bch_time_stats_update(state->time, start_time);
@@ -1744,6 +1753,56 @@ void bch_btree_sort_into(struct btree_keys *dst,
 	bch_verify_btree_nr_keys(dst);
 }
 
+bool bch_maybe_compact_deleted_keys(struct btree_keys *b)
+{
+	struct bset_tree *t, *rebuild_from = NULL;
+	bool last_set_has_aux_tree = bset_has_aux_tree(bset_tree_last(b));
+	unsigned idx;
+
+	for (idx = 0; idx <= b->nsets; idx++) {
+		struct bset *i = b->set[idx].data;
+		struct bkey_packed *k, *n, *out = i->start;
+
+		if (b->nr.bset_u64s[idx] * 4 > le16_to_cpu(i->u64s) * 3)
+			continue;
+
+		/*
+		 * We cannot drop deleted keys from the last bset, if it hasn't
+		 * been written yet - we may need that whiteout on disk:
+		 *
+		 * XXX unless they're extents, if we fix assertions elsewhere
+		 */
+		if (idx == b->nsets && !last_set_has_aux_tree)
+			break;
+
+		for (k = i->start; k != bset_bkey_last(i); k = n) {
+			n = bkey_next(k);
+
+			if (!bkey_deleted(k)) {
+				memmove(out, k, bkey_bytes(k));
+				out = bkey_next(out);
+			}
+		}
+
+		i->u64s = cpu_to_le16((u64 *) out - i->_data);
+
+		if (!rebuild_from)
+			rebuild_from = &b->set[idx];
+	}
+
+	if (!rebuild_from)
+		return false;
+
+	for (t = rebuild_from; t <= b->set + b->nsets; t++) {
+		if (t == bset_tree_last(b) && !last_set_has_aux_tree)
+			bch_bset_build_unwritten_tree(b);
+		else
+			bch_bset_build_written_tree(b, t);
+	}
+
+	return true;
+}
+
 void bch_btree_keys_stats(struct btree_keys *b, struct bset_stats *stats)
 {
 	unsigned i;
diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h
index 3cd5f41244f1..23c3561b34d8 100644
--- a/drivers/md/bcache/bset.h
+++ b/drivers/md/bcache/bset.h
@@ -242,6 +242,7 @@ struct btree_nr_keys {
 	 * units of u64s
 	 */
 	u16			live_u64s;
+	u16			bset_u64s[MAX_BSETS];
 
 	/* live keys only: */
 	u16			packed_keys;
@@ -317,7 +318,7 @@ void bch_btree_keys_init(struct btree_keys *, const struct btree_keys_ops *,
 
 void bch_bset_init_first(struct btree_keys *, struct bset *);
 void bch_bset_init_next(struct btree_keys *, struct bset *);
-void bch_bset_build_written_tree(struct btree_keys *);
+void bch_bset_build_written_tree(struct btree_keys *, struct bset_tree *);
 void bch_bset_fix_invalidated_key(struct btree_keys *, struct bset_tree *,
 				  struct bkey_packed *);
 
@@ -329,20 +330,23 @@ bool bch_bset_try_overwrite(struct btree_keys *, struct btree_node_iter *,
 			    struct bkey_i *);
 
 static inline void btree_keys_account_key(struct btree_nr_keys *n,
+					  unsigned bset,
 					  struct bkey_packed *k,
 					  int sign)
 {
-	n->live_u64s += k->u64s * sign;
+	n->live_u64s		+= k->u64s * sign;
+	n->bset_u64s[bset]	+= k->u64s * sign;
+
 	if (bkey_packed(k))
-		n->packed_keys += sign;
+		n->packed_keys	+= sign;
 	else
 		n->unpacked_keys += sign;
 }
 
-#define btree_keys_account_key_add(_b, _k)			\
-	btree_keys_account_key(_b, _k, 1)
-#define btree_keys_account_key_drop(_b, _k)			\
-	btree_keys_account_key(_b, _k, -1)
+#define btree_keys_account_key_add(_nr, _bset_idx, _k)		\
+	btree_keys_account_key(_nr, _bset_idx, _k, 1)
+#define btree_keys_account_key_drop(_nr, _bset_idx, _k)	\
+	btree_keys_account_key(_nr, _bset_idx, _k, -1)
 
 /* Bkey utility code */
 
@@ -586,6 +590,8 @@ void bch_btree_sort_lazy(struct btree_keys *, struct bset_sort_state *);
 void bch_btree_sort_into(struct btree_keys *, struct btree_keys *,
 			 ptr_filter_fn, struct bset_sort_state *);
 
+bool bch_maybe_compact_deleted_keys(struct btree_keys *);
+
 struct bset_stats {
 	struct {
 		size_t nr, bytes;
diff --git a/drivers/md/bcache/btree_gc.c b/drivers/md/bcache/btree_gc.c
index 4f4b8c14fefc..1edca3e37b5d 100644
--- a/drivers/md/bcache/btree_gc.c
+++ b/drivers/md/bcache/btree_gc.c
@@ -432,13 +432,16 @@ void bch_gc(struct cache_set *c)
 
 static void recalc_packed_keys(struct btree *b)
 {
-	struct btree_node_iter iter;
 	struct bkey_packed *k;
 
 	memset(&b->keys.nr, 0, sizeof(b->keys.nr));
 
-	for_each_btree_node_key(&b->keys, k, &iter)
-		btree_keys_account_key_add(&b->keys.nr, k);
+	BUG_ON(b->keys.nsets);
+
+	for (k = b->keys.set[0].data->start;
+	     k != bset_bkey_last(b->keys.set[0].data);
+	     k = bkey_next(k))
+		btree_keys_account_key_add(&b->keys.nr, 0, k);
 }
 
 static void bch_coalesce_nodes(struct btree *old_nodes[GC_MERGE_NODES],
diff --git a/drivers/md/bcache/btree_io.c b/drivers/md/bcache/btree_io.c
index d1bfc38c47dc..c343811d9bc9 100644
--- a/drivers/md/bcache/btree_io.c
+++ b/drivers/md/bcache/btree_io.c
@@ -75,7 +75,7 @@ static void btree_node_sort(struct cache_set *c, struct btree *b,
 
 	b->keys.nsets = from;
 	b->keys.nr = nr;
-	bch_bset_build_written_tree(&b->keys);
+	bch_bset_build_written_tree(&b->keys, &b->keys.set[from]);
 
 	if (!is_write_locked)
 		__btree_node_unlock_write(b, iter);
@@ -123,7 +123,7 @@ static bool btree_node_compact(struct cache_set *c, struct btree *b,
 
 nosort:
 	__btree_node_lock_write(b, iter);
-	bch_bset_build_written_tree(&b->keys);
+	bch_bset_build_written_tree(&b->keys, bset_tree_last(&b->keys));
 	__btree_node_unlock_write(b, iter);
 	return false;
 sort:
diff --git a/drivers/md/bcache/btree_update.c b/drivers/md/bcache/btree_update.c
index 55b631eb21e6..8693f50f9ce5 100644
--- a/drivers/md/bcache/btree_update.c
+++ b/drivers/md/bcache/btree_update.c
@@ -683,7 +683,8 @@ void bch_btree_bset_insert_key(struct btree_iter *iter,
 		}
 
 		k->type = KEY_TYPE_DELETED;
-		btree_keys_account_key_drop(&b->keys.nr, k);
+		btree_keys_account_key_drop(&b->keys.nr,
+					    t - b->keys.set, k);
 		bch_btree_node_iter_fix(iter, b, node_iter, t, k, true);
 
 		if (t == bset_tree_last(&b->keys) && bkey_deleted(&insert->k))
@@ -1146,6 +1147,9 @@ bch_btree_insert_keys_interior(struct btree *b,
 
 	btree_interior_update_updated_btree(iter->c, as, b);
 
+	if (bch_maybe_compact_deleted_keys(&b->keys))
+		bch_btree_iter_reinit_node(iter, b);
+
 	btree_node_unlock_write(b, iter);
 
 	btree_node_interior_verify(b);
@@ -1197,15 +1201,17 @@ static struct btree *__btree_split_node(struct btree_iter *iter, struct btree *n
 	set2->u64s = cpu_to_le16((u64 *) bset_bkey_last(set1) - (u64 *) k);
 	set1->u64s = cpu_to_le16(le16_to_cpu(set1->u64s) - le16_to_cpu(set2->u64s));
 
-	n2->keys.nr.live_u64s = le16_to_cpu(set2->u64s);
+	n2->keys.nr.live_u64s		= le16_to_cpu(set2->u64s);
+	n2->keys.nr.bset_u64s[0]	= le16_to_cpu(set2->u64s);
 	n2->keys.nr.packed_keys
 		= n1->keys.nr.packed_keys - nr_packed;
 	n2->keys.nr.unpacked_keys
 		= n1->keys.nr.unpacked_keys - nr_unpacked;
 
-	n1->keys.nr.live_u64s = le16_to_cpu(set1->u64s);
-	n1->keys.nr.packed_keys = nr_packed;
-	n1->keys.nr.unpacked_keys = nr_unpacked;
+	n1->keys.nr.live_u64s		= le16_to_cpu(set1->u64s);
+	n1->keys.nr.bset_u64s[0]	= le16_to_cpu(set1->u64s);
+	n1->keys.nr.packed_keys		= nr_packed;
+	n1->keys.nr.unpacked_keys	= nr_unpacked;
 
 	BUG_ON(!set1->u64s);
 	BUG_ON(!set2->u64s);
@@ -1519,11 +1525,21 @@ btree_insert_key(struct btree_insert *trans,
 	struct btree_iter *iter = insert->iter;
 	struct btree *b = iter->nodes[0];
 	enum btree_insert_ret ret;
+	int old_u64s = le16_to_cpu(btree_bset_last(b)->u64s);
+	int old_live_u64s = b->keys.nr.live_u64s;
+	int live_u64s_added, u64s_added;
 
 	ret = !b->keys.ops->is_extents
 		? bch_insert_fixup_key(trans, insert, res)
 		: bch_insert_fixup_extent(trans, insert, res);
 
+	live_u64s_added = (int) b->keys.nr.live_u64s - old_live_u64s;
+	u64s_added = (int) le16_to_cpu(btree_bset_last(b)->u64s) - old_u64s;
+
+	if (u64s_added > live_u64s_added &&
+	    bch_maybe_compact_deleted_keys(&b->keys))
+		bch_btree_iter_reinit_node(iter, b);
+
 	trace_bcache_btree_insert_key(b, insert->k);
 	return ret;
 }
diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c
index 274b1685c353..8dbe25c2ebbd 100644
--- a/drivers/md/bcache/extents.c
+++ b/drivers/md/bcache/extents.c
@@ -93,7 +93,7 @@ struct btree_nr_keys bch_key_sort_fix_overlapping(struct btree_keys *b,
 
 			/* XXX: need better bkey_copy */
 			memcpy(out, k, bkey_bytes(k));
-			btree_keys_account_key_add(&nr, out);
+			btree_keys_account_key_add(&nr, 0, out);
 			out = bkey_next(out);
 		}
 
@@ -775,7 +775,7 @@ static void extent_sort_append(struct btree_keys *b,
 	if (*prev) {
 		bkey_pack(*prev, (void *) *prev, f);
 
-		btree_keys_account_key_add(nr, *prev);
+		btree_keys_account_key_add(nr, 0, *prev);
 		*prev = bkey_next(*prev);
 	} else {
 		*prev = start;
@@ -875,7 +875,7 @@ struct btree_nr_keys bch_extent_sort_fix_overlapping(struct btree_keys *b,
 
 	if (prev) {
 		bkey_pack(prev, (void *) prev, f);
-		btree_keys_account_key_add(&nr, prev);
+		btree_keys_account_key_add(&nr, 0, prev);
 		out = bkey_next(prev);
 	} else {
 		out = bset->start;
@@ -1421,7 +1421,8 @@ bch_insert_fixup_extent(struct btree_insert *trans,
 
 			/* The insert key completely covers k, invalidate k */
 			if (!bkey_deleted(_k))
-				btree_keys_account_key_drop(&b->keys.nr, _k);
+				btree_keys_account_key_drop(&b->keys.nr,
+							t - b->keys.set, _k);
 
 			bch_drop_subtract(iter, k, &stats);
 			k.k->p = bkey_start_pos(&insert->k->k);