bcachefs: Improve bch2_insert_snapshot_whiteouts()

This rewrite bch2_insert_snapshot_whiteouts() to be simpler and more
efficient: we factor out get_snapshot_overwrites(), which no longer
iterates in reverse order.

Also, the new code builds up the list of required new whiteouts all at
once, and then starts a new transaction if there's too many whiteouts to
insert - meaning, it can now run incrementally.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

2 files changed, 118 insertions, 41 deletions

diff --git a/fs/bcachefs/btree_update.c b/fs/bcachefs/btree_update.c
index f52ab2473ab4..2004f8dacc97 100644
--- a/fs/bcachefs/btree_update.c
+++ b/fs/bcachefs/btree_update.c
@@ -123,65 +123,132 @@ static int need_whiteout_for_snapshot(struct btree_trans *trans,
 	return ret;
 }
 
+static int get_snapshot_overwrites(struct btree_trans *trans,
+				   enum btree_id btree,
+				   struct bpos pos,
+				   snapshot_id_list *overwrites)
+{
+	struct bch_fs *c = trans->c;
+	struct btree_iter iter;
+	struct bkey_s_c k;
+	snapshot_id_list overwrites2;
+	u32 *i;
+	int ret = 0;
+
+	darray_init(overwrites);
+	darray_init(&overwrites2);
+
+	for_each_btree_key_norestart(trans, iter, btree,
+				     SPOS(pos.inode, pos.offset, 0),
+				     BTREE_ITER_ALL_SNAPSHOTS, k, ret) {
+		if (bpos_ge(k.k->p, pos))
+			break;
+
+		if (bch2_snapshot_is_ancestor(c, k.k->p.snapshot, pos.snapshot)) {
+			ret = snapshot_list_add(c, &overwrites2, k.k->p.snapshot);
+			if (ret)
+				break;
+		}
+	}
+	bch2_trans_iter_exit(trans, &iter);
+
+	if (ret)
+		goto err;
+
+	darray_for_each(overwrites2, i)
+		if (!snapshot_list_has_ancestor2(c, &overwrites2, *i)) {
+			ret = snapshot_list_add(c, overwrites, *i);
+			if (ret)
+				goto err;
+		}
+
+	*overwrites = overwrites2;
+out:
+	darray_exit(&overwrites2);
+	return ret;
+err:
+	darray_exit(overwrites);
+	goto out;
+}
+
 int __bch2_insert_snapshot_whiteouts(struct btree_trans *trans,
-				   enum btree_id id,
+				   enum btree_id btree,
 				   struct bpos old_pos,
 				   struct bpos new_pos)
 {
 	struct bch_fs *c = trans->c;
-	struct btree_iter old_iter, new_iter = {};
-	struct bkey_s_c old_k, new_k;
-	snapshot_id_list s;
-	struct bkey_i *update;
+	snapshot_id_list old_overwrites, new_overwrites, updates;
+	bool began_transaction = false;
+	u32 *i;
 	int ret = 0;
 
 	if (!bch2_snapshot_has_children(c, old_pos.snapshot))
 		return 0;
 
-	darray_init(&s);
+	darray_init(&old_overwrites);
+	darray_init(&new_overwrites);
+	darray_init(&updates);
 
-	bch2_trans_iter_init(trans, &old_iter, id, old_pos,
-			     BTREE_ITER_not_extents|
-			     BTREE_ITER_all_snapshots);
-	while ((old_k = bch2_btree_iter_prev(trans, &old_iter)).k &&
-	       !(ret = bkey_err(old_k)) &&
-	       bkey_eq(old_pos, old_k.k->p)) {
-		struct bpos whiteout_pos =
-			SPOS(new_pos.inode, new_pos.offset, old_k.k->p.snapshot);
-
-		if (!bch2_snapshot_is_ancestor(c, old_k.k->p.snapshot, old_pos.snapshot) ||
-		    snapshot_list_has_ancestor(c, &s, old_k.k->p.snapshot))
-			continue;
-
-		new_k = bch2_bkey_get_iter(trans, &new_iter, id, whiteout_pos,
-					   BTREE_ITER_not_extents|
-					   BTREE_ITER_intent);
-		ret = bkey_err(new_k);
-		if (ret)
-			break;
+	ret =   get_snapshot_overwrites(trans, btree, old_pos, &old_overwrites) ?:
+		get_snapshot_overwrites(trans, btree, new_pos, &new_overwrites);
+	if (ret)
+		goto err;
 
-		if (new_k.k->type == KEY_TYPE_deleted) {
-			update = bch2_trans_kmalloc(trans, sizeof(struct bkey_i));
-			ret = PTR_ERR_OR_ZERO(update);
+	darray_for_each(old_overwrites, i)
+		if (!snapshot_list_has_ancestor(c, &new_overwrites, *i)) {
+			ret = darray_push(&updates, *i);
 			if (ret)
-				break;
+				goto err;
+		}
 
-			bkey_init(&update->k);
-			update->k.p		= whiteout_pos;
-			update->k.type		= KEY_TYPE_whiteout;
+	if (updates.nr > 4) {
+		bch2_trans_begin(trans);
+		began_transaction = true;
+	}
 
-			ret = bch2_trans_update(trans, &new_iter, update,
-						BTREE_UPDATE_internal_snapshot_node);
+	darray_for_each(updates, i) {
+		struct btree_iter iter;
+		struct bkey_i *update;
+
+		bch2_trans_iter_init(trans, &iter, btree,
+				     SPOS(new_pos.inode, new_pos.offset, *i),
+				     BTREE_ITER_NOT_EXTENTS|
+				     BTREE_ITER_INTENT);
+		update = bch2_trans_kmalloc(trans, sizeof(struct bkey_i));
+		ret = PTR_ERR_OR_ZERO(update);
+		if (ret) {
+			bch2_trans_iter_exit(trans, &iter);
+			goto err;
 		}
-		bch2_trans_iter_exit(trans, &new_iter);
 
-		ret = snapshot_list_add(c, &s, old_k.k->p.snapshot);
+		bkey_init(&update->k);
+		update->k.p		= iter.pos;
+		update->k.type		= KEY_TYPE_whiteout;
+
+		ret   = bch2_btree_iter_traverse(&iter) ?:
+			bch2_trans_update(trans, &iter, update,
+					  BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE) ?:
+			(began_transaction && trans->nr_updates > 4
+			 ? bch2_trans_commit(trans, NULL, NULL, BTREE_INSERT_NOFAIL) : 0);
+
+		bch2_trans_iter_exit(trans, &iter);
+
 		if (ret)
-			break;
+			goto err;
 	}
-	bch2_trans_iter_exit(trans, &new_iter);
-	bch2_trans_iter_exit(trans, &old_iter);
-	darray_exit(&s);
+
+	if (began_transaction && trans->nr_updates) {
+		ret = bch2_trans_commit(trans, NULL, NULL, BTREE_INSERT_NOFAIL);
+		if (ret)
+			goto err;
+	}
+
+	if (began_transaction)
+		ret = -BCH_ERR_transaction_restart_nested;
+err:
+	darray_exit(&updates);
+	darray_exit(&new_overwrites);
+	darray_exit(&old_overwrites);
 
 	return ret;
 }
diff --git a/fs/bcachefs/snapshot.h b/fs/bcachefs/snapshot.h
index 81180181d7c9..7c8425c6a65b 100644
--- a/fs/bcachefs/snapshot.h
+++ b/fs/bcachefs/snapshot.h
@@ -199,9 +199,19 @@ static inline bool snapshot_list_has_ancestor(struct bch_fs *c, snapshot_id_list
 	return false;
 }
 
+static inline bool snapshot_list_has_ancestor2(struct bch_fs *c, snapshot_id_list *s, u32 id)
+{
+	u32 *i;
+
+	darray_for_each(*s, i)
+		if (*i > id && bch2_snapshot_is_ancestor(c, id, *i))
+			return true;
+	return false;
+}
+
 static inline int snapshot_list_add(struct bch_fs *c, snapshot_id_list *s, u32 id)
 {
-	BUG_ON(snapshot_list_has_id(s, id));
+	EBUG_ON(snapshot_list_has_id(s, id));
 	int ret = darray_push(s, id);
 	if (ret)
 		bch_err(c, "error reallocating snapshot_id_list (size %zu)", s->size);