linux-ext4 - [RFC PATCH 13/16] ext4: calculate the worst extent blocks needed of a delalloc es entry

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20230824092619.1327976-14-yi.zhang@huaweicloud.com>
Date:   Thu, 24 Aug 2023 17:26:16 +0800
From:   Zhang Yi <yi.zhang@...weicloud.com>
To:     linux-ext4@...r.kernel.org
Cc:     tytso@....edu, adilger.kernel@...ger.ca, jack@...e.cz,
        yi.zhang@...wei.com, yi.zhang@...weicloud.com,
        chengzhihao1@...wei.com, yukuai3@...wei.com
Subject: [RFC PATCH 13/16] ext4: calculate the worst extent blocks needed of a delalloc es entry

From: Zhang Yi <yi.zhang@...wei.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@...wei.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