linux-kernel - Re: [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-prev] [day] [month] [year] [list]

Message-ID: <d2636759-7809-e080-952a-b24123744eb1@paragon-software.com>
Date:   Mon, 13 Sep 2021 19:55:50 +0300
From:   Konstantin Komarov <almaz.alexandrovich@...agon-software.com>
To:     Kari Argillander <kari.argillander@...il.com>,
        <ntfs3@...ts.linux.dev>
CC:     <linux-kernel@...r.kernel.org>, Joe Perches <joe@...ches.com>
Subject: Re: [PATCH 0/3] fs/ntfs3: Make entry binary search faster



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!