Bill Sommerfeld's Weblog

Creative Hash Functions Take a quick look at this macro definition.   Did you spot the bug?

Because of poor paren placement, the OUTBOUND_HASH_V6 macro in sadb.h
computes a hash value of:

        *x^(*x+1)^(*x+2)^(*x+3)

when:

        x[0]^x[1]^x[2]^x[3]

was intended, with the result that only a small number of outbound hash buckets are ever used.  Half end up in bucket 0.  All hash values have two low order bits of zero, then (going upwards) zero or more 1 bits, and then all zeros until the top of the word.  Distribution looks like:

value:         occurances

       0         2147483648

       4         1073741824

       c          536870912

      1c          268435456

...

1ffffffc                 16

3ffffffc                  8

7ffffffc                  4

fffffffc                  4

needless to say, this distribution is awful, with only 31 unique hash values, and with 50% of entries in one bucket, and with 99% of hits in only 7 buckets. 

Discovered this shortly before 10:30 this morning; filed bug 6338289; tested fix on x86 and sparc, code reviewed, and integrated into the development sources by 5:50pm this afternoon. 

UPDATE: In response to a comment: Yes, inline functions would be better here, but the compiler version we used during solaris 9 development didn't support them in C.    If we're going to revisit this code, a more likely mini-project here is to find all the various places within IP where we compute hash functions based on a protocol address, find the best one, and make that a common one used by all the address-based hash functions, possibly tossing in a key or equivalent as a defense against hash-bucket-clogging attacks.

(2005-10-18 17:39:44.0) Permalink Comments [1]