Skip to contentSkip to conversation

bcachefs: bcachefs_metadata_version_inode_depth

PATCH New Kent Overstreet 1 participant 1 message Dec 1, 2024

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bcachefs: bcachefs_metadata_version_inode_depth

This adds a new inode field, bi_depth, for directory inodes: this allows us to make the check_directory_structure pass much more efficient.

Currently, to ensure the filesystem is fully connect and has no loops, for every directory we follow backpointers until we find the root. But by adding a depth counter, it sufficies to only check the parent of each directory, and check that the parent's bi_depth is smaller.

(fsck doesn't require that bi_depth = parent->bi_depth + 1; if a rename causes bi_depth off, but the chain to the root is still strictly decreasing, then the algorithm still works and there's no need for fsck to fixup the bi_depth fields).

We've already checked backpointers, so we know that every directory (excluding the root)has a valid parent: if bi_depth is always decreasing, every chain must terminate, and terminate at the root directory.

bi_depth will not necessarily be correct when fsck runs, due to directory renames - we can't change bi_depth on every child directory when renaming a directory. That's ok; fsck will silently fix the bi_depth field as needed, and future fsck runs will be much faster.

---
 fs/bcachefs/bcachefs_format.h |  3 +-
 fs/bcachefs/fs-common.c       | 13 +++++
 fs/bcachefs/fsck.c            | 91 ++++++++++++++++++++++++++++-------
 fs/bcachefs/inode.h           | 14 ++++++
 fs/bcachefs/inode_format.h    |  3 +-
 5 files changed, 104 insertions(+), 20 deletions(-)
fs/bcachefs/bcachefs_format.h +2 -1
index c6cc2690aa26..f140c3366e65 100644
@@ -681,7 +681,8 @@ struct bch_sb_field_ext {
 	x(inode_has_child_snapshots,	BCH_VERSION(1, 13))		\
 	x(backpointer_bucket_gen,	BCH_VERSION(1, 14))		\
 	x(disk_accounting_big_endian,	BCH_VERSION(1, 15))		\
-	x(reflink_p_may_update_opts,	BCH_VERSION(1, 16))
+	x(reflink_p_may_update_opts,	BCH_VERSION(1, 16))		\
+	x(inode_depth,			BCH_VERSION(1, 17))
 
 enum bcachefs_metadata_version {
 	bcachefs_metadata_version_min = 9,
fs/bcachefs/fs-common.c +13 -0
index dcaa47f68f31..d2966b670633 100644
@@ -172,6 +172,10 @@ int bch2_create_trans(struct btree_trans *trans,
 		new_inode->bi_dir_offset	= dir_offset;
 	}
 
+	if (S_ISDIR(mode) &&
+	    !new_inode->bi_subvol)
+		new_inode->bi_depth = dir_u->bi_depth + 1;
+
 	inode_iter.flags &= ~BTREE_ITER_all_snapshots;
 	bch2_btree_iter_set_snapshot(&inode_iter, snapshot);
 
@@ -512,6 +516,15 @@ int bch2_rename_trans(struct btree_trans *trans,
 		dst_dir_u->bi_nlink++;
 	}
 
+	if (S_ISDIR(src_inode_u->bi_mode) &&
+	    !src_inode_u->bi_subvol)
+		src_inode_u->bi_depth = dst_dir_u->bi_depth + 1;
+
+	if (mode == BCH_RENAME_EXCHANGE &&
+	    S_ISDIR(dst_inode_u->bi_mode) &&
+	    !dst_inode_u->bi_subvol)
+		dst_inode_u->bi_depth = src_dir_u->bi_depth + 1;
+
 	if (dst_inum.inum && is_subdir_for_nlink(dst_inode_u)) {
 		dst_dir_u->bi_nlink--;
 		src_dir_u->bi_nlink += mode == BCH_RENAME_EXCHANGE;
fs/bcachefs/fsck.c +73 -18

166 lines not on this page · raw message

fs/bcachefs/inode.h +14 -0
index 927c875976da..5bca6950f20e 100644
@@ -219,6 +219,20 @@ static inline u32 bch2_inode_flags(struct bkey_s_c k)
 	}
 }
 
+static inline unsigned bkey_inode_mode(struct bkey_s_c k)
+{
+	switch (k.k->type) {
+	case KEY_TYPE_inode:
+		return le16_to_cpu(bkey_s_c_to_inode(k).v->bi_mode);
+	case KEY_TYPE_inode_v2:
+		return le16_to_cpu(bkey_s_c_to_inode_v2(k).v->bi_mode);
+	case KEY_TYPE_inode_v3:
+		return INODEv3_MODE(bkey_s_c_to_inode_v3(k).v);
+	default:
+		return 0;
+	}
+}
+
 /* i_nlink: */
 
 static inline unsigned nlink_bias(umode_t mode)
fs/bcachefs/inode_format.h +2 -1
index 7928d0c6954f..be1e747629d2 100644
@@ -101,7 +101,8 @@ struct bch_inode_generation {
 	x(bi_dir_offset,		64)	\
 	x(bi_subvol,			32)	\
 	x(bi_parent_subvol,		32)	\
-	x(bi_nocow,			8)
+	x(bi_nocow,			8)	\
+	x(bi_depth,			32)
 
 /* subset of BCH_INODE_FIELDS */
 #define BCH_INODE_OPTS()			\
Signature · 1 line
2.45.2