98627 2012-10-07 19:59:55 -0700 Using float/double as WTF hash table key is unreliable. 2022-07-21 13:21:48 -0700 1 1 1 Unclassified WebKit Web Template Framework 528+ (Nightly build) Unspecified Unspecified RESOLVED FIXED P2 Normal --- 1 kling kling andersca benjamin darin ggaren webkit.review.bot oldest_to_newest 736466 0 kling 2012-10-07 19:59:55 -0700 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. 736471 1 167498 kling 2012-10-07 20:11:22 -0700 Created attachment 167498 Proposed patch 736475 2 167498 ggaren 2012-10-07 20:30:31 -0700 Comment on attachment 167498 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". 736489 3 kling 2012-10-07 21:35:19 -0700 (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. 736683 4 kling 2012-10-08 07:44:59 -0700 Committed r130639: <http://trac.webkit.org/changeset/130639> 737269 5 darin 2012-10-08 17:48:18 -0700 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. 1885779 6 ap 2022-07-21 13:21:48 -0700 *** Bug 26334 has been marked as a duplicate of this bug. *** 167498 2012-10-07 20:11:22 -0700 2012-10-07 20:30:31 -0700 Proposed patch bug-98627.diff text/plain 3861 kling ZGlmZiAtLWdpdCBhL1NvdXJjZS9XVEYvQ2hhbmdlTG9nIGIvU291cmNlL1dURi9DaGFuZ2VMb2cK aW5kZXggNzBmZjA2NC4uMzIzMzUwMCAxMDA2NDQKLS0tIGEvU291cmNlL1dURi9DaGFuZ2VMb2cK KysrIGIvU291cmNlL1dURi9DaGFuZ2VMb2cKQEAgLTEsMyArMSwyMCBAQAorMjAxMi0xMC0wNyAg QW5kcmVhcyBLbGluZyAgPGtsaW5nQHdlYmtpdC5vcmc+CisKKyAgICAgICAgVXNpbmcgZmxvYXQv ZG91YmxlIGFzIFdURiBoYXNoIHRhYmxlIGtleSBpcyB1bnJlbGlhYmxlLgorICAgICAgICA8aHR0 cDovL3dlYmtpdC5vcmcvYi85ODYyNz4KKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9P UFMhKS4KKworICAgICAgICBDaGFuZ2UgRmxvYXRIYXNoOjplcXVhbCgpIHRvIGRvIGEgYml0d2lz ZSBjb21wYXJlIGluc3RlYWQgb2YgYSBsb2dpY2FsIGNvbXBhcmUuCisgICAgICAgIFRoaXMgZml4 ZXMgYSBwcm9ibGVtIHdoZXJlIHRoZSBrZXlzIHdpdGggZGlmZmVyZW50IGJpbmFyeSByZXByZXNl bnRhdGlvbiBidXQgdGhlCisgICAgICAgIHNhbWUgbG9naWNhbCB2YWx1ZSAoZS5nIDAgYW5kIC0w KSBjb3VsZCBibG9jayBlYWNoIG90aGVyIGZyb20gYmVpbmcgZm91bmQgaWYgdGhleQorICAgICAg ICBlbmRlZCB1cCBpbiB0aGUgc2FtZSBoYXNoIGJ1Y2tldC4KKworICAgICAgICAqIHd0Zi9IYXNo RnVuY3Rpb25zLmg6CisgICAgICAgIChGbG9hdEhhc2gpOgorICAgICAgICAoV1RGOjpGbG9hdEhh c2g6Omhhc2gpOgorICAgICAgICAoV1RGOjpGbG9hdEhhc2g6OmVxdWFsKToKKwogMjAxMi0xMC0w NyAgQ2FpbyBNYXJjZWxvIGRlIE9saXZlaXJhIEZpbGhvICA8Y2Fpby5vbGl2ZWlyYUBvcGVuYm9z c2Eub3JnPgogCiAgICAgICAgIFJlbmFtZSBmaXJzdC9zZWNvbmQgdG8ga2V5L3ZhbHVlIGluIEhh c2hNYXAgaXRlcmF0b3JzCmRpZmYgLS1naXQgYS9Tb3VyY2UvV1RGL3d0Zi9IYXNoRnVuY3Rpb25z LmggYi9Tb3VyY2UvV1RGL3d0Zi9IYXNoRnVuY3Rpb25zLmgKaW5kZXggZWIxYjJmMC4uZGQwYTlh YSAxMDA2NDQKLS0tIGEvU291cmNlL1dURi93dGYvSGFzaEZ1bmN0aW9ucy5oCisrKyBiL1NvdXJj ZS9XVEYvd3RmL0hhc2hGdW5jdGlvbnMuaApAQCAtMTA1LDE2ICsxMDUsMTUgQEAgbmFtZXNwYWNl IFdURiB7CiAgICAgfTsKIAogICAgIHRlbXBsYXRlPHR5cGVuYW1lIFQ+IHN0cnVjdCBGbG9hdEhh c2ggeworICAgICAgICB0eXBlZGVmIHR5cGVuYW1lIEludFR5cGVzPHNpemVvZihUKT46OlVuc2ln bmVkVHlwZSBGbGF0dGVuZWRUeXBlOwogICAgICAgICBzdGF0aWMgdW5zaWduZWQgaGFzaChUIGtl eSkKICAgICAgICAgewotICAgICAgICAgICAgdW5pb24gewotICAgICAgICAgICAgICAgIFQga2V5 OwotICAgICAgICAgICAgICAgIHR5cGVuYW1lIEludFR5cGVzPHNpemVvZihUKT46OlVuc2lnbmVk VHlwZSBiaXRzOwotICAgICAgICAgICAgfSB1OwotICAgICAgICAgICAgdS5rZXkgPSBrZXk7Ci0g ICAgICAgICAgICByZXR1cm4gaW50SGFzaCh1LmJpdHMpOworICAgICAgICAgICAgcmV0dXJuIGlu dEhhc2goYml0d2lzZV9jYXN0PEZsYXR0ZW5lZFR5cGU+KGtleSkpOworICAgICAgICB9CisgICAg ICAgIHN0YXRpYyBib29sIGVxdWFsKFQgYSwgVCBiKQorICAgICAgICB7CisgICAgICAgICAgICBy ZXR1cm4gYml0d2lzZV9jYXN0PEZsYXR0ZW5lZFR5cGU+KGEpID09IGJpdHdpc2VfY2FzdDxGbGF0 dGVuZWRUeXBlPihiKTsKICAgICAgICAgfQotICAgICAgICBzdGF0aWMgYm9vbCBlcXVhbChUIGEs IFQgYikgeyByZXR1cm4gYSA9PSBiOyB9CiAgICAgICAgIHN0YXRpYyBjb25zdCBib29sIHNhZmVU b0NvbXBhcmVUb0VtcHR5T3JEZWxldGVkID0gdHJ1ZTsKICAgICB9OwogCmRpZmYgLS1naXQgYS9U b29scy9DaGFuZ2VMb2cgYi9Ub29scy9DaGFuZ2VMb2cKaW5kZXggYWE3ZGJlNi4uYjEyMTdiYyAx MDA2NDQKLS0tIGEvVG9vbHMvQ2hhbmdlTG9nCisrKyBiL1Rvb2xzL0NoYW5nZUxvZwpAQCAtMSwz ICsxLDE3IEBACisyMDEyLTEwLTA3ICBBbmRyZWFzIEtsaW5nICA8a2xpbmdAd2Via2l0Lm9yZz4K KworICAgICAgICBVc2luZyBmbG9hdC9kb3VibGUgYXMgV1RGIGhhc2ggdGFibGUga2V5IGlzIHVu cmVsaWFibGUuCisgICAgICAgIDxodHRwOi8vd2Via2l0Lm9yZy9iLzk4NjI3PgorCisgICAgICAg IFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIEFkZCBhIHRlc3QgY2FzZSBj aGVja2luZyB0aGF0IHVzaW5nIGRvdWJsZSBhcyB0aGUgaGFzaCB0YWJsZSBrZXkgdHlwZSB3b24n dAorICAgICAgICBoYXZlIHByb2JsZW1zIGRpc3Rpbmd1aXNoaW5nIGJldHdlZW4ga2V5cyB0aGF0 IGFyZSBjb25zaWRlcmVkIGVxdWFsIGJ5IG9wZXJhdG9yPT0KKyAgICAgICAgYnV0IGhhdmUgZGlm ZmVyZW50IGJpbmFyeSByZXByZXNlbnRhdGlvbnMuCisKKyAgICAgICAgKiBUZXN0V2ViS2l0QVBJ L1Rlc3RzL1dURi9IYXNoTWFwLmNwcDoKKyAgICAgICAgKFRlc3REb3VibGVIYXNoVHJhaXRzKToK KwogMjAxMi0xMC0wNyAgQ2FpbyBNYXJjZWxvIGRlIE9saXZlaXJhIEZpbGhvICA8Y2Fpby5vbGl2 ZWlyYUBvcGVuYm9zc2Eub3JnPgogCiAgICAgICAgIFJlbmFtZSBmaXJzdC9zZWNvbmQgdG8ga2V5 L3ZhbHVlIGluIEhhc2hNYXAgaXRlcmF0b3JzCmRpZmYgLS1naXQgYS9Ub29scy9UZXN0V2ViS2l0 QVBJL1Rlc3RzL1dURi9IYXNoTWFwLmNwcCBiL1Rvb2xzL1Rlc3RXZWJLaXRBUEkvVGVzdHMvV1RG L0hhc2hNYXAuY3BwCmluZGV4IGI5ZjRjMWYuLmUyNThmZDMgMTAwNjQ0Ci0tLSBhL1Rvb2xzL1Rl c3RXZWJLaXRBUEkvVGVzdHMvV1RGL0hhc2hNYXAuY3BwCisrKyBiL1Rvb2xzL1Rlc3RXZWJLaXRB UEkvVGVzdHMvV1RGL0hhc2hNYXAuY3BwCkBAIC00OSw0ICs0OSwzMCBAQCBURVNUKFdURiwgSGFz aFRhYmxlSXRlcmF0b3JDb21wYXJpc29uKQogICAgIEFTU0VSVF9GQUxTRShtYXAuZW5kKCkgPT0g YmVnaW4pOwogfQogCitzdHJ1Y3QgVGVzdERvdWJsZUhhc2hUcmFpdHMgOiBIYXNoVHJhaXRzPGRv dWJsZT4geworICAgIHN0YXRpYyBjb25zdCBpbnQgbWluaW11bVRhYmxlU2l6ZSA9IDg7Cit9Owor Cit0eXBlZGVmIEhhc2hNYXA8ZG91YmxlLCBpbnQ2NF90LCBEZWZhdWx0SGFzaDxkb3VibGU+OjpI YXNoLCBUZXN0RG91YmxlSGFzaFRyYWl0cz4gRG91YmxlSGFzaE1hcDsKKworVEVTVChXVEYsIERv dWJsZUhhc2hDb2xsaXNpb25zKQoreworICAgIC8vIFRoZSAiY2xvYmJlciIga2V5IGhlcmUgaXMg b25lIHRoYXQgZW5kcyB1cCBzdGVhbGluZyB0aGUgYnVja2V0IHRoYXQgdGhlIC0wIGtleQorICAg IC8vIG9yaWdpbmFsbHkgd2FudHMgdG8gYmUgaW4uIFRoaXMgbWFrZXMgdGhlIDAgYW5kIC0wIGtl eXMgY29sbGlkZSBhbmQgdGhlIHRlc3QgdGhlbgorICAgIC8vIGZhaWxzIHVubGVzcyB0aGUgRmxv YXRIYXNoOjplcXVhbHMoKSBpbXBsZW1lbnRhdGlvbiBjYW4gZGlzdGluZ3Vpc2ggdGhlbS4KKyAg ICBjb25zdCBkb3VibGUgY2xvYmJlcktleSA9IDY7CisgICAgY29uc3QgZG91YmxlIHplcm9LZXkg PSAwOworICAgIGNvbnN0IGRvdWJsZSBuZWdhdGl2ZVplcm9LZXkgPSAtemVyb0tleTsKKworICAg IERvdWJsZUhhc2hNYXAgbWFwOworCisgICAgbWFwLmFkZChjbG9iYmVyS2V5LCAxKTsKKyAgICBt YXAuYWRkKHplcm9LZXksIDIpOworICAgIG1hcC5hZGQobmVnYXRpdmVaZXJvS2V5LCAzKTsKKwor ICAgIEFTU0VSVF9FUShtYXAuZ2V0KGNsb2JiZXJLZXkpLCAxKTsKKyAgICBBU1NFUlRfRVEobWFw LmdldCh6ZXJvS2V5KSwgMik7CisgICAgQVNTRVJUX0VRKG1hcC5nZXQobmVnYXRpdmVaZXJvS2V5 KSwgMyk7Cit9CisKIH0gLy8gbmFtZXNwYWNlIFRlc3RXZWJLaXRBUEkK