Bug 98627 – Using float/double as WTF hash table key is unreliable.

• Status: RESOLVED
• Resolution: FIXED
• Component: Web Template Framework

[Andreas Kling]

There's a flaw in the way WTF::FloatHash is implemented, hash() hashes the raw underlying bits of the key value, but equal() compares using the regular float/double operator==.

Since there are multiple ways to represent the same value in floating point format, we can end up with values that hash() to different results, yet are equal according to equal(). I first discovered this problem when lowering the default minimum table size of WTF hash tables. One unlucky HashMap<double, whatever> got zero (0) and signed zero (-0) values in the same bucket, and hence the first one got picked every time by lookup of both keys since equal() would return true for either one of them.

I propose that we fix this by making FloatHash::equal() do a bitwise compare instead.

[Andreas Kling]

Created attachment 167498 [details]
Proposed patch

[Geoffrey Garen]

Comment on attachment 167498 [details]
Proposed patch

View in context: https://bugs.webkit.org/attachment.cgi?id=167498&action=review

r=me

Do we need to test positive infinity vs negative infinity? How about NaN?

I guessed that the errors caused by your size=8 patch would be due to smoking out bugs in cases of collisions. I'm surprised by how many bugs there were!

Perhaps it's worth doing a test run where you artificially make the first level hash for all hash tables ==0, just in case there are more issues like this.

> Source/WTF/wtf/HashFunctions.h:108
> +        typedef typename IntTypes<sizeof(T)>::UnsignedType FlattenedType;

FWIW, I usually call a type like this "Bits".

[Andreas Kling]

(In reply to comment #2)
> I guessed that the errors caused by your size=8 patch would be due to smoking out bugs in cases of collisions. I'm surprised by how many bugs there were!
> 
> Perhaps it's worth doing a test run where you artificially make the first level hash for all hash tables ==0, just in case there are more issues like this.

Good idea, I'm gonna do exactly that.

> > Source/WTF/wtf/HashFunctions.h:108
> > +        typedef typename IntTypes<sizeof(T)>::UnsignedType FlattenedType;
> 
> FWIW, I usually call a type like this "Bits".

Will tweak before landing.

[Andreas Kling]

Committed r130639: <http://trac.webkit.org/changeset/130639>

[Darin Adler]

Fantastic. I was worrying about this issue in the back of my mind for a long time. Really happy that it’s this easy to fix. Fix looks elegant too.

[Alexey Proskuryakov]

*** Bug 26334 has been marked as a duplicate of this bug. ***