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.

Comments:

Why OUTBOUND_HASH_V{4,6} are macros at all?
static inline function is obviously much better for this:
- typechecking;
- visible at the debugger level;
- free of unintended side-effects (classical OUTBOUND_HASH_V6(sabd, addr++));
- doesn't require silly extra parentheses around arguments.

Posted by nikita on October 18, 2005 at 11:18 PM EDT #

Post a Comment:
  • HTML Syntax: NOT allowed
About

sommerfeld

Search

Top Tags
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today