Mathematically, the function is attempting to do what a normal hash function aims to do: collision-avoidance, maximizing spread, predictability-avoidance etc.....hash function is always a many-to-one function, as it compressed a lot of computation space into smaller space.....while at the same time trying to avoid having output being correlated with the input...ie, achieving pseudo-randomness in its mapping. Anyway....I am not a mathematician....esp "Golden Ratio"....one man's focus in another's confusion.... Computation-wise, it is trying to do the above calculation in the fastest way: meaning avoiding multiplication and division....and maximizing on bit-shifting... so doing a disassembly: 273145 ffffffff810e6050 <hash>: 273146 ffffffff810e6050: 55 push %rbp 273147 ffffffff810e6051: 48 89 e5 mov %rsp,%rbp 273148 ffffffff810e6054: e8 27 aa f2 ff callq ffffffff81010a80 <mcount> 273149 ffffffff810e6059: 48 b8 01 00 fc ff ff mov $0x9e37fffffffc0001,%rax 273150 ffffffff810e6060: ff 37 9e 273151 ffffffff810e6063: 8b 0d 9b 27 57 00 mov 0x57279b(%rip),%ecx # ffffffff81658804 <i_hash_shift> 273152 ffffffff810e6069: 48 0f af fe imul %rsi,%rdi 273153 ffffffff810e606d: 48 8d 14 06 lea (%rsi,%rax,1),%rdx 273154 ffffffff810e6071: 48 c1 ea 06 shr $0x6,%rdx 273155 ffffffff810e6075: 48 31 d7 xor %rdx,%rdi 273156 ffffffff810e6078: 48 31 f8 xor %rdi,%rax 273157 ffffffff810e607b: 48 d3 e8 shr %cl,%rax 273158 ffffffff810e607e: 48 31 f8 xor %rdi,%rax 273159 ffffffff810e6081: 23 05 79 27 57 00 and 0x572779(%rip),%eax # ffffffff81658800 <i_hash_mask> 273160 ffffffff810e6087: c9 leaveq 273161 ffffffff810e6088: c3 retq I think the present "hash()" function still have way to improve itself..... For example, this one does not have any multiplication: http://burtleburtle.net/bob/hash/doobs.html Good to question the kernel basics once in a while Onkar!!!!! On Sat, Apr 10, 2010 at 12:40 AM, Onkar Mahajan <kern.devel@xxxxxxxxx> wrote: > Why is the hash calculated like this ? > > static unsigned long hash(struct super_block *sb, unsigned long hashval) > { > unsigned long tmp; > > tmp = (hashval * (unsigned long)sb) ^ (GOLDEN_RATIO_PRIME + hashval) / > L1_CACHE_BYTES; > tmp = tmp ^ ((tmp ^ GOLDEN_RATIO_PRIME) >> I_HASHBITS); > return tmp & I_HASHMASK; > } > > > Regards, > Onkar > -- Regards, Peter Teoh -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
