Why count the hash value in this way?
hi all: In the function of link_path_walk() , it counts the hash value of the compoent of the pathname. Why "(prevhash + (c <<4) + (c >> 4))*11;"? Thank you. http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L779 809 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L809> c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c> = *(const unsigned char *)name <http://lxr.oss.org.cn/ident?v=2.6.16;i=name>;810 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L810> 811 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L811> hash <http://lxr.oss.org.cn/ident?v=2.6.16;i=hash> = init_name_hash <http://lxr.oss.org.cn/ident?v=2.6.16;i=init_name_hash>();812 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L812> do {813 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L813> name <http://lxr.oss.org.cn/ident?v=2.6.16;i=name>++;814 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L814> hash <http://lxr.oss.org.cn/ident?v=2.6.16;i=hash> = partial_name_hash <http://lxr.oss.org.cn/ident?v=2.6.16;i=partial_name_hash>(c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c>, hash <http://lxr.oss.org.cn/ident?v=2.6.16;i=hash>);815 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L815> c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c> = *(const unsigned char *)name <http://lxr.oss.org.cn/ident?v=2.6.16;i=name>;816 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L816> } while (c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c> && (c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c> != *'/'*));817 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L817> this.len <http://lxr.oss.org.cn/ident?v=2.6.16;i=len> = name <http://lxr.oss.org.cn/ident?v=2.6.16;i=name> - (const char *) this.name <http://lxr.oss.org.cn/ident?v=2.6.16;i=name>; */* Name hashing routines. Initial hash value */* 49 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L49> */* Hash courtesy of the R5 hash in reiserfs modulo sign bits */* 50 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L50> #define init_name_hash <http://lxr.oss.org.cn/ident?v=2.6.16;i=init_name_hash>() 0 51 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L51> 52 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L52> */* partial hash update function. Assume roughly 4 bits per character */* 53 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L53> static inline unsigned long 54 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L54> partial_name_hash <http://lxr.oss.org.cn/ident?v=2.6.16;i=partial_name_hash>(unsigned long c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c>, unsigned long prevhash) 55 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L55> { 56 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L56> return (prevhash + (c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c> << 4) + (c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c> >> 4)) * 11; 57 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L57> }
On Sun, Aug 04, 2013 at 05:38:55PM +0800, lx wrote:
hi all: In the function of link_path_walk() , it counts the hash value of the compoent of the pathname. Why "(prevhash + (c <<4) + (c >> 4))*11;"?
In the code you quoted it says: /* Hash courtesy of the R5 hash in reiserfs modulo sign bits */ A bit of googling led me to this[1] page, where it says: r5 - This hash is a modified version of rupasov hash. It is used by default and it is better to stick here until you have to support huge directories and unusual file-name patterns. and: rupasov - This hash is invented by Yury Yu. Rupasov. It is fast and preserves locality, mapping lexicographically close file names to the close hash values. Never use it, as it has a high probability of hash collisions. [1] https://reiser4.wiki.kernel.org/index.php/Mount Reading the ReiserFS code and/or mailing lists might give you a clue about how the R5 hash was designed. HTH, Jonathan Neuschäfer
participants (2)
-
Jonathan Neuschäfer -
lx