Received-SPF: pass (google.com: domain of linux-ext4-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Zhang Yi <yi.zhang@huaweicloud.com>
To:     linux-ext4@vger.kernel.org
Cc:     tytso@mit.edu, adilger.kernel@dilger.ca, jack@suse.cz,
        yi.zhang@huawei.com, yi.zhang@huaweicloud.com,
        chengzhihao1@huawei.com, yukuai3@huawei.com
Subject: [RFC PATCH 13/16] ext4: calculate the worst extent blocks needed of a delalloc es entry
Date:   Thu, 24 Aug 2023 17:26:16 +0800
Message-Id: <20230824092619.1327976-14-yi.zhang@huaweicloud.com>
In-Reply-To: <20230824092619.1327976-1-yi.zhang@huaweicloud.com>
References: <20230824092619.1327976-1-yi.zhang@huaweicloud.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

From: Zhang Yi <yi.zhang@huawei.com>

Add a new helper to calculate the worst case of extent blocks that
needed while mapping a new delalloc extent_status entry. In the worst
case, one delay data block consumes one extent enrty, the worst extent
blocks should be 'leaf blocks + index blocks + (max depth - depth
increasing costs)'. The detailed calculation formula is:

        / DIV_ROUND_UP(da_blocks, ext_per_block);  (i = 0)
 f(i) =
        \ DIV_ROUND_UP(f(i-1), idx_per_block);     (0 < i < max_depth)

 SUM = f(0) + .. + f(n) + max_depth - n - 1;  (0 <= n < max_depth, f(n) > 0)

For example:
On the default 4k block size, the default ext_per_block and
idx_per_block are 340. (1) If we map 50 length of blocks, the worst
entent block is DIV_ROUND_UP(50, 340) + EXT4_MAX_EXTENT_DEPTH - 1 = 5,
(2) if we map 500 length of blocks, the worst extent block is
DIV_ROUND_UP(500, 340) + DIV_ROUND_UP(DIV_ROUND_UP(500, 340), 340) +
EXT4_MAX_EXTENT_DEPTH - 2 = 6, and so on. It is a preparation for
reserving meta blocks of delalloc.

Signed-off-by: Zhang Yi <yi.zhang@huawei.com>
---
 fs/ext4/ext4.h    |  2 ++
 fs/ext4/extents.c | 28 ++++++++++++++++++++++++++++
 2 files changed, 30 insertions(+)

diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index 3e0a39653469..11813382fbcc 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -3699,6 +3699,8 @@ extern int ext4_swap_extents(handle_t *handle, struct inode *inode1,
 			     ext4_lblk_t lblk2,  ext4_lblk_t count,
 			     int mark_unwritten,int *err);
 extern int ext4_clu_mapped(struct inode *inode, ext4_lblk_t lclu);
+extern unsigned int ext4_map_worst_ext_blocks(struct inode *inode,
+					      unsigned int len);
 extern int ext4_datasem_ensure_credits(handle_t *handle, struct inode *inode,
 				       int check_cred, int restart_cred,
 				       int revoke_cred);
diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index 592383effe80..43c251a42144 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -5797,6 +5797,34 @@ int ext4_clu_mapped(struct inode *inode, ext4_lblk_t lclu)
 	return err ? err : mapped;
 }
 
+/*
+ * Calculate the worst case of extents blocks needed while mapping 'len'
+ * data blocks.
+ */
+unsigned int ext4_map_worst_ext_blocks(struct inode *inode, unsigned int len)
+{
+	unsigned int ext_blocks = 0;
+	int max_entries;
+	int depth, max_depth;
+
+	if (!len)
+		return 0;
+
+	max_entries = ext4_ext_space_block(inode, 0);
+	max_depth = EXT4_MAX_EXTENT_DEPTH;
+
+	for (depth = 0; depth < max_depth; depth++) {
+		len = DIV_ROUND_UP(len, max_entries);
+		ext_blocks += len;
+		if (len == 1)
+			break;
+		if (depth == 0)
+			max_entries = ext4_ext_space_block_idx(inode, 0);
+	}
+
+	return ext_blocks + max_depth - depth - 1;
+}
+
 /*
  * Updates physical block address and unwritten status of extent
  * starting at lblk start and of len. If such an extent doesn't exist,
-- 
2.39.2