* [PATCH 1/3] fs/ntfs3: Limit binary search table size
2021-09-02 15:40 [PATCH 0/3] fs/ntfs3: Make entry binary search faster Kari Argillander
@ 2021-09-02 15:40 ` Kari Argillander
2021-09-02 15:40 ` [PATCH 2/3] fs/ntfs3: Make binary search to search smaller chunks in beginning Kari Argillander
` (2 subsequent siblings)
3 siblings, 0 replies; 5+ messages in thread
From: Kari Argillander @ 2021-09-02 15:40 UTC (permalink / raw)
To: Konstantin Komarov, ntfs3; +Cc: Kari Argillander, linux-kernel, Joe Perches
Current binary search allocates memory for table and fill whole table
before we start actual binary search. This is quite inefficient because
table fill will always be O(n). Also if table is huge we need to
reallocate memory which is costly.
This implementation use just stack memory and always when table is full
we will check if last element is <= and if not start table fill again.
The idea was that it would be same cost as table reallocation.
Signed-off-by: Kari Argillander <kari.argillander@gmail.com>
---
fs/ntfs3/index.c | 110 ++++++++++++++++++-----------------------------
1 file changed, 41 insertions(+), 69 deletions(-)
diff --git a/fs/ntfs3/index.c b/fs/ntfs3/index.c
index 0daca9adc54c..8bac9d20e7e3 100644
--- a/fs/ntfs3/index.c
+++ b/fs/ntfs3/index.c
@@ -678,98 +678,70 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
u32 off = le32_to_cpu(hdr->de_off);
#ifdef NTFS3_INDEX_BINARY_SEARCH
- int max_idx = 0, fnd, min_idx;
- int nslots = 64;
- u16 *offs;
+ struct NTFS_DE *found = NULL;
+ int min_idx = 0, mid_idx, max_idx = 0;
+ int diff2;
+ u16 offs[64];
if (end > 0x10000)
goto next;
- offs = kmalloc(sizeof(u16) * nslots, GFP_NOFS);
- if (!offs)
- goto next;
+fill_table:
+ if (off + sizeof(struct NTFS_DE) > end)
+ return NULL;
- /* Use binary search algorithm. */
-next1:
- if (off + sizeof(struct NTFS_DE) > end) {
- e = NULL;
- goto out1;
- }
e = Add2Ptr(hdr, off);
e_size = le16_to_cpu(e->size);
- if (e_size < sizeof(struct NTFS_DE) || off + e_size > end) {
- e = NULL;
- goto out1;
- }
-
- if (max_idx >= nslots) {
- u16 *ptr;
- int new_slots = ALIGN(2 * nslots, 8);
-
- ptr = kmalloc(sizeof(u16) * new_slots, GFP_NOFS);
- if (ptr)
- memcpy(ptr, offs, sizeof(u16) * max_idx);
- kfree(offs);
- offs = ptr;
- nslots = new_slots;
- if (!ptr)
- goto next;
- }
-
- /* Store entry table. */
- offs[max_idx] = off;
+ if (e_size < sizeof(struct NTFS_DE) || off + e_size > end)
+ return NULL;
if (!de_is_last(e)) {
+ offs[max_idx] = off;
off += e_size;
- max_idx += 1;
- goto next1;
- }
- /*
- * Table of pointers is created.
- * Use binary search to find entry that is <= to the search value.
- */
- fnd = -1;
- min_idx = 0;
+ max_idx++;
+ if (max_idx < ARRAY_SIZE(offs))
+ goto fill_table;
- while (min_idx <= max_idx) {
- int mid_idx = min_idx + ((max_idx - min_idx) >> 1);
- int diff2;
-
- e = Add2Ptr(hdr, offs[mid_idx]);
+ max_idx--;
+ }
- e_key_len = le16_to_cpu(e->key_size);
+binary_search:
+ e_key_len = le16_to_cpu(e->key_size);
- diff2 = (*cmp)(key, key_len, e + 1, e_key_len, ctx);
+ diff2 = (*cmp)(key, key_len, e + 1, e_key_len, ctx);
+ if (diff2 > 0) {
+ if (found) {
+ min_idx = mid_idx + 1;
+ } else {
+ if (de_is_last(e))
+ return NULL;
- if (!diff2) {
- *diff = 0;
- goto out1;
+ max_idx = 0;
+ goto fill_table;
}
-
- if (diff2 < 0) {
+ } else if (diff2 < 0) {
+ if (found)
max_idx = mid_idx - 1;
- fnd = mid_idx;
- if (!fnd)
- break;
- } else {
- min_idx = mid_idx + 1;
- }
- }
+ else
+ max_idx--;
- if (fnd == -1) {
- e = NULL;
- goto out1;
+ found = e;
+ } else {
+ *diff = 0;
+ return e;
}
- *diff = -1;
- e = Add2Ptr(hdr, offs[fnd]);
+ if (min_idx > max_idx) {
+ *diff = -1;
+ return found;
+ }
-out1:
- kfree(offs);
+ mid_idx = (min_idx + max_idx) >> 1;
+ e = Add2Ptr(hdr, offs[mid_idx]);
- return e;
+ goto binary_search;
#endif
next:
--
2.25.1
^ permalink raw reply related [flat|nested] 5+ messages in thread* [PATCH 2/3] fs/ntfs3: Make binary search to search smaller chunks in beginning
2021-09-02 15:40 [PATCH 0/3] fs/ntfs3: Make entry binary search faster Kari Argillander
2021-09-02 15:40 ` [PATCH 1/3] fs/ntfs3: Limit binary search table size Kari Argillander
@ 2021-09-02 15:40 ` Kari Argillander
2021-09-02 15:40 ` [PATCH 3/3] fs/ntfs3: Always use binary search with entry search Kari Argillander
2021-09-13 16:55 ` [PATCH 0/3] fs/ntfs3: Make entry binary search faster Konstantin Komarov
3 siblings, 0 replies; 5+ messages in thread
From: Kari Argillander @ 2021-09-02 15:40 UTC (permalink / raw)
To: Konstantin Komarov, ntfs3; +Cc: Kari Argillander, linux-kernel, Joe Perches
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@gmail.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
^ permalink raw reply related [flat|nested] 5+ messages in thread* [PATCH 3/3] fs/ntfs3: Always use binary search with entry search
2021-09-02 15:40 [PATCH 0/3] fs/ntfs3: Make entry binary search faster Kari Argillander
2021-09-02 15:40 ` [PATCH 1/3] fs/ntfs3: Limit binary search table size Kari Argillander
2021-09-02 15:40 ` [PATCH 2/3] fs/ntfs3: Make binary search to search smaller chunks in beginning Kari Argillander
@ 2021-09-02 15:40 ` Kari Argillander
2021-09-13 16:55 ` [PATCH 0/3] fs/ntfs3: Make entry binary search faster Konstantin Komarov
3 siblings, 0 replies; 5+ messages in thread
From: Kari Argillander @ 2021-09-02 15:40 UTC (permalink / raw)
To: Konstantin Komarov, ntfs3; +Cc: Kari Argillander, linux-kernel, Joe Perches
We do not have any reason to keep old linear search in. Before this was
used for error path or if table was so big that it cannot be allocated.
Current binary search implementation won't need error path. Remove old
references to linear entry search.
Signed-off-by: Kari Argillander <kari.argillander@gmail.com>
---
fs/ntfs3/index.c | 50 ++++++------------------------------------------
fs/ntfs3/ntfs.h | 3 ---
2 files changed, 6 insertions(+), 47 deletions(-)
diff --git a/fs/ntfs3/index.c b/fs/ntfs3/index.c
index e336d5645628..9f79cff7d09e 100644
--- a/fs/ntfs3/index.c
+++ b/fs/ntfs3/index.c
@@ -672,22 +672,16 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
const struct INDEX_HDR *hdr, const void *key,
size_t key_len, const void *ctx, int *diff)
{
- struct NTFS_DE *e;
+ struct NTFS_DE *e, *found = NULL;
NTFS_CMP_FUNC cmp = indx->cmp;
+ int min_idx = 0, mid_idx, max_idx = 0;
+ int diff2;
+ int table_size = 8;
u32 e_size, e_key_len;
u32 end = le32_to_cpu(hdr->used);
u32 off = le32_to_cpu(hdr->de_off);
-
-#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[128];
- if (end > 0x10000)
- goto next;
-
fill_table:
if (off + sizeof(struct NTFS_DE) > end)
return NULL;
@@ -721,7 +715,8 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
return NULL;
max_idx = 0;
- table_size = min(table_size * 2, 128);
+ table_size = min(table_size * 2,
+ (int)ARRAY_SIZE(offs));
goto fill_table;
}
} else if (diff2 < 0) {
@@ -745,39 +740,6 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
e = Add2Ptr(hdr, offs[mid_idx]);
goto binary_search;
-#endif
-
-next:
- /*
- * Entries index are sorted.
- * Enumerate all entries until we find entry
- * that is <= to the search value.
- */
- if (off + sizeof(struct NTFS_DE) > end)
- return NULL;
-
- e = Add2Ptr(hdr, off);
- e_size = le16_to_cpu(e->size);
-
- if (e_size < sizeof(struct NTFS_DE) || off + e_size > end)
- return NULL;
-
- off += e_size;
-
- e_key_len = le16_to_cpu(e->key_size);
-
- *diff = (*cmp)(key, key_len, e + 1, e_key_len, ctx);
- if (!*diff)
- return e;
-
- if (*diff <= 0)
- return e;
-
- if (de_is_last(e)) {
- *diff = 1;
- return e;
- }
- goto next;
}
/*
diff --git a/fs/ntfs3/ntfs.h b/fs/ntfs3/ntfs.h
index 6bb3e595263b..a7e1b7cc7a14 100644
--- a/fs/ntfs3/ntfs.h
+++ b/fs/ntfs3/ntfs.h
@@ -12,9 +12,6 @@
/* TODO: Check 4K MFT record and 512 bytes cluster. */
-/* Activate this define to use binary search in indexes. */
-#define NTFS3_INDEX_BINARY_SEARCH
-
/* Check each run for marked clusters. */
#define NTFS3_CHECK_FREE_CLST
--
2.25.1
^ permalink raw reply related [flat|nested] 5+ messages in thread* Re: [PATCH 0/3] fs/ntfs3: Make entry binary search faster
2021-09-02 15:40 [PATCH 0/3] fs/ntfs3: Make entry binary search faster Kari Argillander
` (2 preceding siblings ...)
2021-09-02 15:40 ` [PATCH 3/3] fs/ntfs3: Always use binary search with entry search Kari Argillander
@ 2021-09-13 16:55 ` Konstantin Komarov
3 siblings, 0 replies; 5+ messages in thread
From: Konstantin Komarov @ 2021-09-13 16:55 UTC (permalink / raw)
To: Kari Argillander, ntfs3; +Cc: linux-kernel, Joe Perches
On 02.09.2021 18:40, Kari Argillander wrote:
> This series will make binary search faster with removing the need of
> allocations. We will only use stack memory. This will also make possible
> to remove linear search completely.
>
> It is good also point out that full binary search not quite fit with
> entry search because entrys are not always same size. This why we first
> need linear table fill algorithm. My implementation try to use the fact
> that we should not linear fill full table before not doing any checking
> of the entrys. It is example 50/50 change if we are in middle that entry
> is in first half. So it is very inefficient to fill table after we are
> middle point.
>
> We could also predict how many entrys there is and use this information,
> but I did not do that in this point. I'm more than happy to improve this
> more if someone has ideas.
>
> I have tested this with xfstests and did not see regressions. Checkpatch
> and build tests for every patch have been done. I haven't done major
> bench marking with this one. Idea that this is better is just my two
> cent. Paragon has hopefully done bencmarking with old binary search
> compared to linear search? I'm quite certain that this will win old
> binary search algorithm because no need for allocations.
>
> Thanks Joe for let me notice this improvement.
>
> Kari Argillander (3):
> fs/ntfs3: Limit binary search table size
> fs/ntfs3: Make binary search to search smaller chunks in beginning
> fs/ntfs3: Always use binary search with entry search
>
> fs/ntfs3/index.c | 153 ++++++++++++++---------------------------------
> fs/ntfs3/ntfs.h | 3 -
> 2 files changed, 45 insertions(+), 111 deletions(-)
>
>
> base-commit: d3624466b56dd5b1886c1dff500525b544c19c83
>
Hi Joe, Kari!
Applied, thanks!
^ permalink raw reply [flat|nested] 5+ messages in thread