linux-ext4 - Re: [ext2] Mislabeled quadratic probing?

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: <ec430a38-9458-343e-5c0f-a4a74474ddb0@gmail.com>
Date:   Sun, 30 Jul 2017 21:40:29 -0400
From:   Sean Anderson <seanga2@...il.com>
To:     Matthew Wilcox <willy@...radead.org>
Cc:     linux-fsdevel <linux-fsdevel@...r.kernel.org>, jack@...e.com,
        tytso@....edu, adilger.kernel@...ger.ca, linux-ext4@...r.kernel.org
Subject: Re: [ext2] Mislabeled quadratic probing?

> The biggest danger I see here is that we're only going to test 32
> groups before falling back to linear probing (we'll shift the single
> '1' bit out of 'i' in 32 steps).  That might be a performance problem,
> but it should hit quite rarely.

Actually, because the loop condition is `i < ngroups`, we test even less
than that . For example, on a 1T disk with 4K blocks there are 8192
block groups, and the maximum iterations are 13. It seems then that
simply creating a directory and creating at least 15 files and writing
at least 128M between each would cause a fall back to a linear search.
This doesn't seem all that uncommon of use case: any directory over 2GB
or so with many files would be susceptible.

Download attachment "signature.asc" of type "application/pgp-signature" (619 bytes)