linux-kernel - Re: [PATCH] dcache: better name hash function

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 26 Oct 2009 20:53:51 -0700
From:	Stephen Hemminger <shemminger@...tta.com>
To:	Eric Dumazet <eric.dumazet@...il.com>
Cc:	Al Viro <viro@...iv.linux.org.uk>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Octavian Purdila <opurdila@...acom.com>,
	netdev@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] dcache: better name hash function

On Tue, 27 Oct 2009 03:45:50 +0100
Eric Dumazet <eric.dumazet@...il.com> wrote:

> Stephen Hemminger <shemminger@...tta.com>, Al Viro a écrit :
> > --- a/include/linux/dcache.h	2009-10-26 14:58:45.220347300 -0700
> > +++ b/include/linux/dcache.h	2009-10-26 15:12:15.004160122 -0700
> > @@ -45,15 +45,28 @@ struct dentry_stat_t {
> >  };
> >  extern struct dentry_stat_t dentry_stat;
> >  
> > -/* Name hashing routines. Initial hash value */
> > -/* Hash courtesy of the R5 hash in reiserfs modulo sign bits */
> > -#define init_name_hash()		0
> > +/*
> > + * Fowler / Noll / Vo (FNV) Hash
> > + * see: http://www.isthe.com/chongo/tech/comp/fnv/
> > + */
> > +#ifdef CONFIG_64BIT
> > +#define FNV_PRIME  1099511628211ull
> > +#define FNV1_INIT  14695981039346656037ull
> > +#else
> > +#define FNV_PRIME  16777619u
> > +#define FNV1_INIT  2166136261u
> > +#endif
> > +
> > +#define init_name_hash()	FNV1_INIT
> >  
> > -/* partial hash update function. Assume roughly 4 bits per character */
> > +/* partial hash update function. */
> >  static inline unsigned long
> > -partial_name_hash(unsigned long c, unsigned long prevhash)
> > +partial_name_hash(unsigned char c, unsigned long prevhash)
> >  {
> > -	return (prevhash + (c << 4) + (c >> 4)) * 11;
> > +	prevhash ^= c;
> > +	prevhash *= FNV_PRIME;
> > +
> > +	return prevhash;
> >  }
> >  
> >  /*
> 
> OK, but thats strlen(name) X (long,long) multiplies.
> 
> I suspect you tested on recent x86_64 cpu.
> 
> Some arches might have slow multiplies, no ?
> 
> jhash() (and others) are optimized by compiler to use basic and fast operations.
> jhash operates on blocs of 12 chars per round, so it might be a pretty good choice once
> out-of-line (because its pretty large and full_name_hash() is now used by
> a lot of call sites)
> 
> Please provide your test program source, so that other can test on various arches.
> 
> Thanks

long on i386 is 32 bits so it is 32 bit multiply.  There is also an optimization
that uses shift and adds.




-- 

Download attachment "hashtest.tar.bz2" of type "application/x-bzip" (7585 bytes)