Subject: Re: New hash algorithm - FNV - for use in the kernel
To: Jonathan Stone <jonathan@DSG.Stanford.EDU>
From: David Laight <David.Laight@btinternet.com>
Date: 11/28/2001 10:21:29
> >This is NFS, all the implementations are clones of each other,
> >I'd guess that there is little difference between the implementations.
> Huh? Rick Macklem's implementation (the basis of the 4.3BSD-Reno NFS)
> is not exactly a clone of Sun's. Nor is Linux. Implemented from the
> specs, yes; and from talking to other implementations, yes; but
> *not* the same codebase. For quite obvious reasons.
Yes - I didn't quite say what I meant....
NFS clients expect NFS file handles to be valid after a reboot of
the server (yes, I know, this isn't always possible and is a right
pain but...) so the file handle is constructed from a reference
to the file system, and a reference to the file within that system.
The former is (often) the major/minor number - but is of little interest
for hashing, the latter the inode number and inode use count (actually
the file handle from the lower filesystem)
For NFS V1 (I think it's V1) the NFS spec defines the length of the
file handle, the number of ways the above information can be stashed
in the available space is limited...
Clearly the only 'important' piece here for hashing purposes is the
inode number from the underlying filesystem. These are very likely
to be a dense range of integers. Inodeless filesystems have trouble
generating the persistent file references that NFS expects...
In practise a 32 bit sum over the NFS file handle is probably quick
and safe. Finish off with 'sum += sum >> 16' for good measure then
mask with the table size - a division here will kill performance!