bcachefs: Cleanup redundant snapshot nodesbcachefs-garbage

Signed-off-by: Hunter Shaffer <huntershaffer182456@gmail.com>

2 files changed, 100 insertions, 21 deletions

diff --git a/fs/bcachefs/bcachefs_format.h b/fs/bcachefs/bcachefs_format.h
index 20e96daf9ca1..f17238be494c 100644
--- a/fs/bcachefs/bcachefs_format.h
+++ b/fs/bcachefs/bcachefs_format.h
@@ -1150,6 +1150,7 @@ struct bch_snapshot {
 	__le32			parent;
 	__le32			children[2];
 	__le32			subvol;
+	/* corresponds to a bch_snapshot_tree in BTREE_ID_snapshot_trees */
 	__le32			tree;
 	__le32			depth;
 	__le32			skip[3];
diff --git a/fs/bcachefs/subvolume.c b/fs/bcachefs/subvolume.c
index 571cb2809c88..ff7bc6f70f9a 100644
--- a/fs/bcachefs/subvolume.c
+++ b/fs/bcachefs/subvolume.c
@@ -127,13 +127,19 @@ err:
 	return ret;
 }
 
+static inline void normalize_snapshot_child_pointers(struct bch_snapshot *s)
+{
+	if (le32_to_cpu(s->children[0]) < le32_to_cpu(s->children[1]))
+		swap(s->children[0], s->children[1]);
+}
+
 static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
 {
 	struct bch_fs *c = trans->c;
 	struct btree_iter iter, p_iter = (struct btree_iter) { NULL };
 	struct btree_iter tree_iter = (struct btree_iter) { NULL };
 	struct bkey_s_c_snapshot s;
-	u32 parent_id;
+	u32 parent_id, child_id;
 	unsigned i;
 	int ret = 0;
 
@@ -146,8 +152,10 @@ static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
 	if (ret)
 		goto err;
 
-	BUG_ON(!BCH_SNAPSHOT_DELETED(s.v));
+	BUG_ON(s.v->children[1]);
+
 	parent_id = le32_to_cpu(s.v->parent);
+	child_id = le32_to_cpu(s.v->children[0]);
 
 	if (parent_id) {
 		struct bkey_i_snapshot *parent;
@@ -156,27 +164,42 @@ static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
 				     BTREE_ID_snapshots, POS(0, parent_id),
 				     0, snapshot);
 		ret = PTR_ERR_OR_ZERO(parent);
-		if (unlikely(ret)) {
-			bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
-						"missing snapshot %u", parent_id);
+		bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
+					"missing snapshot %u", parent_id);
+		if (unlikely(ret))
 			goto err;
-		}
 
+		/* find entry in parent->children for node being deleted */
 		for (i = 0; i < 2; i++)
 			if (le32_to_cpu(parent->v.children[i]) == id)
 				break;
 
-		if (i == 2)
-			bch_err(c, "snapshot %u missing child pointer to %u",
-				parent_id, id);
-		else
-			parent->v.children[i] = 0;
+		if (bch2_fs_inconsistent_on(i == 2, c,
+					"snapshot %u missing child pointer to %u",
+					parent_id, id))
+			goto err;
 
-		if (le32_to_cpu(parent->v.children[0]) <
-		    le32_to_cpu(parent->v.children[1]))
-			swap(parent->v.children[0],
-			     parent->v.children[1]);
-	} else {
+		parent->v.children[i] = le32_to_cpu(child_id);
+
+		normalize_snapshot_child_pointers(&parent->v);
+	}
+
+	if (child_id) {
+		struct bkey_i_snapshot *child;
+
+		child = bch2_bkey_get_mut_typed(trans, &p_iter,
+				     BTREE_ID_snapshots, POS(0, child_id),
+				     0, snapshot);
+		ret = PTR_ERR_OR_ZERO(child);
+		bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
+					"missing snapshot %u", child_id);
+		if (unlikely(ret))
+			goto err;
+
+		child->v.parent = cpu_to_le32(parent_id);
+	}
+
+	if (!parent_id) {
 		/*
 		 * We're deleting the root of a snapshot tree: update the
 		 * snapshot_tree entry to point to the new root, or delete it if
@@ -360,6 +383,12 @@ int bch2_snapshot_node_create(struct btree_trans *trans, u32 parent,
  *
  * also: unlinked inode in internal snapshot appears to not be getting deleted
  * correctly if inode doesn't exist in leaf snapshots
+ *
+ * solution:
+ *
+ * for a key in an interior snapshot node that needs work to be done that
+ * requires it to be mutated: iterate over all descendent leaf nodes and copy
+ * that key to snapshot leaf nodes, where we can mutate it
  */
 
 static int snapshot_delete_key(struct btree_trans *trans,
@@ -381,6 +410,38 @@ static int snapshot_delete_key(struct btree_trans *trans,
 		return bch2_btree_delete_at(trans, iter,
 					    BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
 	} else {
+		/*
+		 * When we have a linear chain of snapshot nodes, we consider
+		 * those to form an equivalence class: we're going to collapse
+		 * them all down to a single node, and keep the leaf-most node -
+		 * which has the same id as the equivalence class id.
+		 *
+		 * If there are multiple keys in different snapshots at the same
+		 * position, we're only going to keep the one in the newest
+		 * snapshot - the rest have been overwritten and are redundant,
+		 * and for the key we're going to keep we need to move it to the
+		 * equivalance class ID if it's not there already.
+		 */
+		if (equiv != k.k->p.snapshot) {
+			struct bkey_i *new = bch2_bkey_make_mut_noupdate(trans, k);
+			int ret;
+
+			ret = PTR_ERR_OR_ZERO(new);
+			if (ret)
+				return ret;
+
+			new->k.p.snapshot = equiv;
+
+			ret = __bch2_btree_insert(trans, iter->btree_id, new,
+						  BTREE_TRIGGER_NORUN|
+						  BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE) ?:
+				bch2_btree_delete_at(trans, iter,
+						     BTREE_TRIGGER_NORUN|
+						     BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
+			if (ret)
+				return ret;
+		}
+
 		return snapshot_list_add(c, equiv_seen, equiv);
 	}
 }
@@ -474,7 +535,7 @@ int bch2_delete_dead_snapshots(struct bch_fs *c)
 	bch2_trans_iter_exit(&trans, &iter);
 
 	if (ret) {
-		bch_err(c, "error walking snapshots: %s", bch2_err_str(ret));
+		bch_err_msg(c, ret, "walking snapshots");
 		goto err;
 	}
 
@@ -494,17 +555,34 @@ int bch2_delete_dead_snapshots(struct bch_fs *c)
 		darray_exit(&equiv_seen);
 
 		if (ret) {
-			bch_err(c, "error deleting snapshot keys: %s", bch2_err_str(ret));
+			bch_err_msg(c, ret, "deleting keys from dying snapshots");
 			goto err;
 		}
 	}
 
+	for_each_btree_key(&trans, iter, BTREE_ID_snapshots,
+			   POS_MIN, 0, k, ret) {
+		u32 snapshot = k.k->p.offset;
+		u32 equiv = bch2_snapshot_equiv(c, snapshot);
+
+		if (equiv != snapshot) {
+			ret = commit_do(&trans, NULL, NULL, 0,
+				bch2_snapshot_node_delete(&trans, snapshot));
+			if (ret) {
+				bch_err_msg(c, ret, "deleting snapshot %u", snapshot);
+				goto err;
+			}
+		}
+	}
+	bch2_trans_iter_exit(&trans, &iter);
+
 	for (i = 0; i < deleted.nr; i++) {
+		u32 node_to_delete = deleted.data[i];
+
 		ret = commit_do(&trans, NULL, NULL, 0,
-			bch2_snapshot_node_delete(&trans, deleted.data[i]));
+			bch2_snapshot_node_delete(&trans, node_to_delete));
 		if (ret) {
-			bch_err(c, "error deleting snapshot %u: %s",
-				deleted.data[i], bch2_err_str(ret));
+			bch_err_msg(c, ret, "deleting snapshot %u", node_to_delete);
 			goto err;
 		}
 	}