[PATCH 03/27] ext4: add KUnit tests for ext4_ext_split() leaf and index splitting

["Theodore Ts'o" <tytso@mit.edu>]

Commit 7831b3664109 ("ext4: add KUnit tests for fs/ext4/extents.c")
updated both block-allocation paths in ext4_ext_split() to call
ext4_ext_getblk() and noted node splitting in the commit message, but
none of the test cases in fs/ext4/extents-test.c actually reached
ext4_ext_split(). In test_insert_extent_grow_and_merge_up(), inserting a
5th extent into a full depth-0 root triggers ext4_ext_grow_indepth(),
moving the 4 extents into an external leaf block with eh_max == 340 and
returning from ext4_ext_create_new_leaf() without splitting.

Add two KUnit test cases to exercise ext4_ext_split() across leaf and
intermediate index levels:

- test_insert_extent_leaf_split(): fills a depth-1 external leaf block
  to capacity (340 extents), inserts in the middle to trigger a leaf
  split that moves tail extents into a new leaf block, and then fills
  the second leaf and appends past its end to exercise the m == 0
  leaf-addition path.
- test_insert_extent_index_split(): exercises depth 1 -> 2 tree growth
  followed by leaf splitting via the repeat loop in
  ext4_ext_create_new_leaf(), and then clamps the depth-1 index block's
  eh_max to exercise simultaneous leaf and intermediate index block
  splitting (k == 1) in ext4_ext_split().

Fixes: 7831b3664109 ("ext4: add KUnit tests for fs/ext4/extents.c")
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 fs/ext4/extents-test.c | 206 +++++++++++++++++++++++++++++++++++++++--
 fs/ext4/move_extent.c  |   5 +
 2 files changed, 203 insertions(+), 8 deletions(-)

diff --git a/fs/ext4/extents-test.c b/fs/ext4/extents-test.c
index 705648186218..47ddeb94e2bf 100644
--- a/fs/ext4/extents-test.c
+++ b/fs/ext4/extents-test.c
@@ -1584,6 +1584,198 @@ static void test_insert_extent_grow_and_merge_up(struct kunit *test)
 	KUNIT_EXPECT_EQ(test, ext4_ext_get_actual_len(&ex[0]), 12);
 }
 
+/*
+ * Verify ext4_ext_split() at depth 1 both when splitting a full leaf in the
+ * middle (moving tail extents to a newly allocated leaf block) and when
+ * appending past the end of a full leaf (m == 0).
+ */
+static void test_insert_extent_leaf_split(struct kunit *test)
+{
+	struct inode *inode = &k_ctx.k_ei->vfs_inode;
+	struct ext4_extent_header *eh = ext_inode_hdr(inode);
+	struct ext4_ext_path *path;
+	int i;
+
+	ext_reset_tree(inode);
+
+	/*
+	 * Insert 340 non-contiguous extents [i * 4, i * 4 + 2) @ 2000 + i * 4
+	 * to grow from depth 0 to depth 1 and completely fill the external
+	 * 4096-byte leaf block (eh_max = 340).
+	 */
+	for (i = 0; i < 340; i++) {
+		KUNIT_ASSERT_EQ_MSG(test,
+				    ext_insert_one(inode, i * 4, 2,
+						   2000 + i * 4, false, 0),
+				    0, "i=%d", i);
+	}
+	KUNIT_EXPECT_EQ(test, ext_depth(inode), 1);
+	KUNIT_EXPECT_EQ(test, le16_to_cpu(eh->eh_entries), 1);
+
+	/*
+	 * Insert [402, 403) @ 9000 in the middle of the full leaf between
+	 * [400, 402) and [404, 406): triggers ext4_ext_split() with m = 239,
+	 * moving [404..1358) into a newly allocated second leaf block.
+	 */
+	k_ctx.alloc_calls = 0;
+	KUNIT_ASSERT_EQ(test, ext_insert_one(inode, 402, 1, 9000, false, 0), 0);
+	KUNIT_EXPECT_EQ(test, k_ctx.alloc_calls, 1U);
+	KUNIT_EXPECT_EQ(test, ext_depth(inode), 1);
+	KUNIT_EXPECT_EQ(test, le16_to_cpu(eh->eh_entries), 2);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(EXT_FIRST_INDEX(eh)[0].ei_block), 0U);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(EXT_FIRST_INDEX(eh)[1].ei_block),
+			404U);
+	KUNIT_EXPECT_EQ(test, ext4_ext_check_inode(inode), 0);
+
+	path = ext4_find_extent(inode, 402, NULL, EXT4_EX_NOCACHE);
+	KUNIT_ASSERT_FALSE(test, IS_ERR_OR_NULL(path));
+	KUNIT_EXPECT_EQ(test, le16_to_cpu(path[1].p_hdr->eh_entries), 102);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(path[1].p_ext->ee_block), 402U);
+	KUNIT_EXPECT_EQ(test, ext4_ext_pblock(path[1].p_ext), 9000ULL);
+	ext4_free_ext_path(path);
+
+	path = ext4_find_extent(inode, 404, NULL, EXT4_EX_NOCACHE);
+	KUNIT_ASSERT_FALSE(test, IS_ERR_OR_NULL(path));
+	KUNIT_EXPECT_EQ(test, le16_to_cpu(path[1].p_hdr->eh_entries), 239);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(path[1].p_ext->ee_block), 404U);
+	KUNIT_EXPECT_EQ(test, ext4_ext_pblock(path[1].p_ext), 2404ULL);
+	ext4_free_ext_path(path);
+
+	/*
+	 * Fill the second leaf to capacity (239 + 101 = 340 entries), then
+	 * append [1764, 1766) @ 3764 past its end to exercise ext4_ext_split()
+	 * with m == 0 (adding a new leaf without moving existing entries).
+	 */
+	for (i = 340; i < 441; i++) {
+		KUNIT_ASSERT_EQ_MSG(test,
+				    ext_insert_one(inode, i * 4, 2,
+						   2000 + i * 4, false, 0),
+				    0, "i=%d", i);
+	}
+	k_ctx.alloc_calls = 0;
+	KUNIT_ASSERT_EQ(test, ext_insert_one(inode, 1764, 2, 3764, false, 0),
+			0);
+	KUNIT_EXPECT_EQ(test, k_ctx.alloc_calls, 1U);
+	KUNIT_EXPECT_EQ(test, ext_depth(inode), 1);
+	KUNIT_EXPECT_EQ(test, le16_to_cpu(eh->eh_entries), 3);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(EXT_FIRST_INDEX(eh)[2].ei_block),
+			1764U);
+
+	path = ext4_find_extent(inode, 1764, NULL, EXT4_EX_NOCACHE);
+	KUNIT_ASSERT_FALSE(test, IS_ERR_OR_NULL(path));
+	KUNIT_EXPECT_EQ(test, le16_to_cpu(path[1].p_hdr->eh_entries), 1);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(path[1].p_ext->ee_block), 1764U);
+	KUNIT_EXPECT_EQ(test, ext4_ext_pblock(path[1].p_ext), 3764ULL);
+	ext4_free_ext_path(path);
+}
+
+/*
+ * Verify multi-level tree growth from depth 1 -> 2 followed by leaf split
+ * (ext4_ext_create_new_leaf repeat loop), and intermediate index block
+ * splitting in ext4_ext_split() when both leaf and depth-1 index are full.
+ */
+static void test_insert_extent_index_split(struct kunit *test)
+{
+	struct inode *inode = &k_ctx.k_ei->vfs_inode;
+	struct ext4_extent_header *eh = ext_inode_hdr(inode);
+	struct ext4_extent_idx *idx;
+	struct ext4_ext_path *path;
+	struct buffer_head *bh;
+	int i;
+
+	ext_reset_tree(inode);
+
+	/*
+	 * Build a full depth-1 root index (eh_entries = eh_max = 4) pointing
+	 * to 4 full leaf blocks (eh_entries = eh_max = 2).
+	 */
+	eh->eh_depth = cpu_to_le16(1);
+	eh->eh_entries = cpu_to_le16(4);
+	eh->eh_max = cpu_to_le16(ext4_ext_space_root_idx_test(inode, 0));
+	idx = EXT_FIRST_INDEX(eh);
+
+	for (i = 0; i < 4; i++) {
+		struct ext4_extent_header *leaf_eh;
+		struct ext4_extent *ex;
+		ext4_lblk_t lblk = 10 + i * 10;
+
+		idx[i].ei_block = cpu_to_le32(lblk);
+		ext4_idx_store_pblock(&idx[i], EXT_META_BASE_PBLK + i);
+
+		bh = ext4_ext_getblk_stub(inode, EXT_META_BASE_PBLK + i,
+					  GFP_KERNEL);
+		KUNIT_ASSERT_NOT_NULL(test, bh);
+		leaf_eh = ext_block_hdr(bh);
+		leaf_eh->eh_magic = EXT4_EXT_MAGIC;
+		leaf_eh->eh_depth = 0;
+		leaf_eh->eh_entries = cpu_to_le16(2);
+		leaf_eh->eh_max = cpu_to_le16(2);
+		ex = EXT_FIRST_EXTENT(leaf_eh);
+		ex[0].ee_block = cpu_to_le32(lblk);
+		ex[0].ee_len = cpu_to_le16(2);
+		ext4_ext_store_pblock(&ex[0], 2000 + i * 10);
+		ex[1].ee_block = cpu_to_le32(lblk + 4);
+		ex[1].ee_len = cpu_to_le16(2);
+		ext4_ext_store_pblock(&ex[1], 2004 + i * 10);
+		brelse(bh);
+	}
+
+	/*
+	 * Inserting [48, 50) @ 2038 finds both leaf 3 and the root index full:
+	 * ext4_ext_grow_indepth() grows depth 1 -> 2, and the repeat loop in
+	 * ext4_ext_create_new_leaf() calls ext4_ext_split() at depth 1.
+	 */
+	k_ctx.alloc_calls = 0;
+	KUNIT_ASSERT_EQ(test, ext_insert_one(inode, 48, 2, 2038, false, 0), 0);
+	KUNIT_EXPECT_EQ(test, k_ctx.alloc_calls, 2U);
+	KUNIT_EXPECT_EQ(test, ext_depth(inode), 2);
+	KUNIT_EXPECT_EQ(test, le16_to_cpu(eh->eh_entries), 1);
+
+	/*
+	 * Clamp the depth-1 index block's eh_max to its current 5 entries so
+	 * inserting [12, 13) @ 9000 into full leaf 0 splits both leaf 0 and
+	 * the intermediate depth-1 index block (depth = 2, at = 0, k = 1).
+	 */
+	bh = ext4_ext_getblk_stub(inode, ext4_idx_pblock(EXT_FIRST_INDEX(eh)),
+				  GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, bh);
+	KUNIT_ASSERT_EQ(test, le16_to_cpu(ext_block_hdr(bh)->eh_entries), 5);
+	ext_block_hdr(bh)->eh_max = cpu_to_le16(5);
+	brelse(bh);
+
+	k_ctx.alloc_calls = 0;
+	KUNIT_ASSERT_EQ(test, ext_insert_one(inode, 12, 1, 9000, false, 0), 0);
+	KUNIT_EXPECT_EQ(test, k_ctx.alloc_calls, 2U);
+	KUNIT_EXPECT_EQ(test, ext_depth(inode), 2);
+	KUNIT_EXPECT_EQ(test, le16_to_cpu(eh->eh_entries), 2);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(EXT_FIRST_INDEX(eh)[0].ei_block),
+			10U);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(EXT_FIRST_INDEX(eh)[1].ei_block),
+			14U);
+	KUNIT_EXPECT_EQ(test, ext4_ext_check_inode(inode), 0);
+
+	path = ext4_find_extent(inode, 12, NULL, EXT4_EX_NOCACHE);
+	KUNIT_ASSERT_FALSE(test, IS_ERR_OR_NULL(path));
+	KUNIT_EXPECT_EQ(test, path->p_depth, 2);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(path[2].p_ext->ee_block), 12U);
+	KUNIT_EXPECT_EQ(test, ext4_ext_pblock(path[2].p_ext), 9000ULL);
+	ext4_free_ext_path(path);
+
+	path = ext4_find_extent(inode, 14, NULL, EXT4_EX_NOCACHE);
+	KUNIT_ASSERT_FALSE(test, IS_ERR_OR_NULL(path));
+	KUNIT_EXPECT_EQ(test, path->p_depth, 2);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(path[2].p_ext->ee_block), 14U);
+	KUNIT_EXPECT_EQ(test, ext4_ext_pblock(path[2].p_ext), 2004ULL);
+	ext4_free_ext_path(path);
+
+	path = ext4_find_extent(inode, 48, NULL, EXT4_EX_NOCACHE);
+	KUNIT_ASSERT_FALSE(test, IS_ERR_OR_NULL(path));
+	KUNIT_EXPECT_EQ(test, path->p_depth, 2);
+	KUNIT_EXPECT_EQ(test, le32_to_cpu(path[2].p_ext->ee_block), 48U);
+	KUNIT_EXPECT_EQ(test, ext4_ext_pblock(path[2].p_ext), 2038ULL);
+	ext4_free_ext_path(path);
+}
+
 /*
  * Verify ext4_ext_remove_space() for middle-of-extent hole punching, full
  * extent removal with left-scooting, and ext4_ext_truncate() tail removal.
@@ -2073,17 +2265,13 @@ static void test_swap_extents(struct kunit *test)
 	KUNIT_ASSERT_EQ(test, ext_insert_one(inode1, 10, 10, 100, false, 0), 0);
 	KUNIT_ASSERT_EQ(test, ext_insert_one(inode2, 10, 10, 200, false, 0), 0);
 
-	inode_lock(inode1);
-	inode_lock(inode2);
-	down_write(&EXT4_I(inode1)->i_data_sem);
-	down_write(&EXT4_I(inode2)->i_data_sem);
+	lock_two_nondirectories(inode1, inode2);
+	ext4_double_down_write_data_sem(inode1, inode2);
 
 	replaced = ext4_swap_extents(NULL, inode1, inode2, 12, 12, 5, 1, &err);
 
-	up_write(&EXT4_I(inode2)->i_data_sem);
-	up_write(&EXT4_I(inode1)->i_data_sem);
-	inode_unlock(inode2);
-	inode_unlock(inode1);
+	ext4_double_up_write_data_sem(inode1, inode2);
+	unlock_two_nondirectories(inode1, inode2);
 
 	KUNIT_EXPECT_EQ(test, err, 0);
 	KUNIT_EXPECT_EQ(test, replaced, 5);
@@ -2787,6 +2975,8 @@ static struct kunit_case extents_test_cases[] = {
 	KUNIT_CASE(test_can_extents_be_merged),
 	KUNIT_CASE(test_insert_extent_merge_and_nomerge),
 	KUNIT_CASE(test_insert_extent_grow_and_merge_up),
+	KUNIT_CASE(test_insert_extent_leaf_split),
+	KUNIT_CASE(test_insert_extent_index_split),
 	KUNIT_CASE(test_remove_space_tail_and_hole_punch),
 	KUNIT_CASE(test_remove_space_multilevel_collapse),
 	KUNIT_CASE(test_remove_space_bigalloc_partial_cluster),
diff --git a/fs/ext4/move_extent.c b/fs/ext4/move_extent.c
index 3329b7ad5dbd..d1405e763912 100644
--- a/fs/ext4/move_extent.c
+++ b/fs/ext4/move_extent.c
@@ -656,3 +656,8 @@ int ext4_move_extents(struct file *o_filp, struct file *d_filp, __u64 orig_blk,
 	unlock_two_nondirectories(orig_inode, donor_inode);
 	return ret;
 }
+
+#if IS_ENABLED(CONFIG_EXT4_KUNIT_TESTS)
+EXPORT_SYMBOL_FOR_EXT4_TEST(ext4_double_down_write_data_sem);
+EXPORT_SYMBOL_FOR_EXT4_TEST(ext4_double_up_write_data_sem);
+#endif
-- 
2.56.0.542.g3ef89b7020-goog