Re: [ext2] Mislabeled quadratic probing?

From
Sean Anderson <seanga2@gmail.com>
Date
2017-07-31 01:40:32
Also in
linux-fsdevel
Reply to
Matthew Wilcox, 2017-07-30
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.

Attachments

Thread (3 messages) 3 messages, 3 authors, last reply 2017-07-31
Keyboard shortcuts
hback out one level
jnext message in thread / next series-diff position
kprevious message in thread / previous series-diff position
ldrill in
Escclose help / fold thread tree
?toggle this help