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
Attachment:
signature.asc
Description: OpenPGP digital signature
