Creative Hash Functions
By sommerfeld on Oct 18, 2005
Because of poor paren placement, the OUTBOUND_HASH_V6 macro in sadb.h
computes a hash value of:
x\^x\^x\^xwas 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:
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.