Bug 98627 - Using float/double as WTF hash table key is unreliable.
Summary: Using float/double as WTF hash table key is unreliable.
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Andreas Kling
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2012-10-07 19:59 PDT by Andreas Kling
Modified: 2012-10-08 17:48 PDT (History)
5 users (show)

See Also:


Attachments
Proposed patch (3.77 KB, patch)
2012-10-07 20:11 PDT, Andreas Kling
ggaren: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andreas Kling 2012-10-07 19:59:55 PDT
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.
Comment 1 Andreas Kling 2012-10-07 20:11:22 PDT
Created attachment 167498 [details]
Proposed patch
Comment 2 Geoffrey Garen 2012-10-07 20:30:31 PDT
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".
Comment 3 Andreas Kling 2012-10-07 21:35:19 PDT
(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.
Comment 4 Andreas Kling 2012-10-08 07:44:59 PDT
Committed r130639: <http://trac.webkit.org/changeset/130639>
Comment 5 Darin Adler 2012-10-08 17:48:18 PDT
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.