[ext2] Mislabeled quadratic probing?

From
Sean Anderson <seanga2@gmail.com>
Date
2017-07-29 14:24:39
Hi,

I was reading through the ext2 inode allocation code, and found the
following snippet in fs/ext2/ialloc.c:find_group_other

/*
 * Use a quadratic hash to find a group with a free inode and some
 * free blocks.
 */
for (i = 1; i < ngroups; i <<= 1) {
        group += i;
        if (group >= ngroups)
                group -= ngroups;
        desc = ext2_get_group_desc (sb, group, NULL);
        if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&
                        le16_to_cpu(desc->bg_free_blocks_count))
                goto found;
}

As I understand it, quadratic probing starting at a hash H would try
positions H+1, H+4, H+9, H+16, H+25, etc. Here, however, the algorithm
appears to try positions H+1, H+3, H+7, H+15, H+31, etc., which appears
to be some form of exponential probing. I was unable to find the patch
which introduced this code, but it appears that it was introduced in
v2.4.14.3, and before that linear probing was used. Clearly, this code
works, and I can't really find any compelling arguments to switch to
quadratic probing proper. I suspect it was done this way to avoid a
multiply or an extra subtract on every loop. Can anyone shed some light
on the choice (and apparent mislabel) of this algorithm?

	--Sean

Attachments

Thread (4 messages) 4 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