linux-kernel - [PATCH 0/3] fs/ntfs3: Make entry binary search faster

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-next>] [day] [month] [year] [list]

Date:   Thu,  2 Sep 2021 18:40:47 +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 0/3] fs/ntfs3: Make entry binary search faster

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
-- 
2.25.1