On Monday January 6, torvalds@transmeta.com wrote:
>
> On 6 Jan 2003, Jeremy Fitzhardinge wrote:
> >
> > I think they have a different set of design requirements. They're both
> > designed to not only generate hashes, but make the hashes
> > cryptographically strong (ie, impossible to generate collisions with
> > less effort than brute force). They're naturally slower than a simple
> > hash, so you'd only use them if you need the stronger requirements.
>
> The filesystem hashes also have another design criteria: they need to
> reliably give the _same_ hash on different machines.
>
> In particular, the suggested hash_mem() thing is endian-unsafe, meaning
> that it will give different answers on an x86 than on a sparc CPU, for
> example. Which can be ok if the only thing you care about is some
> temporary hash, but is unacceptable for a lot of uses. The filesystem
> hashes (well, at least some of them) are also designed to hash out files
> on the disk, which means that they _have_ to be the same regardless of
> architecture, or you can't move disks between machines.
Not only endian-unsafe but also word-length-unsafe!
I certainly never imagined hash_mem would be a replacement for an
externally visible hash function such as those used by ext3. Rather I
was wondering if one of those used by ext3 would be a suitable
candidate for hash_mem, and found that they weren't convincingly
better.
>
> Quite frankly, I think the suggested hash_mem() is too special-cased to
> make any sense as a generic function. The endian problems means that it
> _isn't_ really generic anyway, and as such it might as well just be some
> internal nfs helper function rather than something in <linux/string.h>
>
That's a shame.... It fills a similar purpose to full_name_hash in
dcache.h. It might be nice to have just one function for internal
hashing of names.
The proposed hash_mem() seems slightly better than full_name_hash, and
much the same speed (Depending on how you measure it...)
Maybe full_name_hash et.al could be moved to linux/hash.h and I could
use that ...
My current preferred internal 'hash-a-string' function is:
static inline unsigned long hash_str(unsigned char *name, int bits, char term)
{
unsigned long hash = 0;
unsigned long l = 0;
int len = 0;
unsigned char c;
while (likely(c = *name++) && likely(c != term)) {
l = (l << 8) | c;
len++;
if ((len & (BITS_PER_LONG/8-1))==0)
hash = hash_long(hash^l, BITS_PER_LONG);
}
l = l << 8 ^ len;
return hash_long(hash^l, bits);
}
Given that we need to search for a terminator, using *(unsigned long*)
doesn't really help.
This hash_str could be used in place of the namei/dcache hashing, and
can be used where I need to hash a string.
Would anyone like to independantly compare it with:
c = *(const unsigned char *)name;
hash = init_name_hash();
do {
name++;
hash = partial_name_hash(c, hash);
c = *(const unsigned char *)name;
} while (c && (c != '/'));
which is the comparable function from namei.c
NeilBrown
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Tue Jan 07 2003 - 22:00:37 EST