linux-kernel - [PATCH 2/3] fs/ntfs3: Make binary search to search smaller chunks in beginning

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]

Date:   Thu,  2 Sep 2021 18:40:49 +0300
From:   Kari Argillander <kari.argillander@...il.com>
To:     Konstantin Komarov <almaz.alexandrovich@...agon-software.com>,
        ntfs3@...ts.linux.dev
Cc:     Kari Argillander <kari.argillander@...il.com>,
        linux-kernel@...r.kernel.org, Joe Perches <joe@...ches.com>
Subject: [PATCH 2/3] fs/ntfs3: Make binary search to search smaller chunks in beginning

We could try to optimize algorithm to first fill just small table and
after that use bigger table all the way up to ARRAY_SIZE(offs). This
way we can use bigger search array, but not lose benefits with entry
count smaller < ARRAY_SIZE(offs).

Signed-off-by: Kari Argillander <kari.argillander@...il.com>
---
 fs/ntfs3/index.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/fs/ntfs3/index.c b/fs/ntfs3/index.c
index 8bac9d20e7e3..e336d5645628 100644
--- a/fs/ntfs3/index.c
+++ b/fs/ntfs3/index.c
@@ -8,6 +8,7 @@
 #include <linux/blkdev.h>
 #include <linux/buffer_head.h>
 #include <linux/fs.h>
+#include <linux/kernel.h>
 #include <linux/nls.h>
 
 #include "debug.h"
@@ -680,8 +681,9 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
 #ifdef NTFS3_INDEX_BINARY_SEARCH
 	struct NTFS_DE *found = NULL;
 	int min_idx = 0, mid_idx, max_idx = 0;
+	int table_size = 8;
 	int diff2;
-	u16 offs[64];
+	u16 offs[128];
 
 	if (end > 0x10000)
 		goto next;
@@ -701,7 +703,7 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
 		off += e_size;
 
 		max_idx++;
-		if (max_idx < ARRAY_SIZE(offs))
+		if (max_idx < table_size)
 			goto fill_table;
 
 		max_idx--;
@@ -719,6 +721,7 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
 				return NULL;
 
 			max_idx = 0;
+			table_size = min(table_size * 2, 128);
 			goto fill_table;
 		}
 	} else if (diff2 < 0) {
-- 
2.25.1