130509 2014-03-20 06:51:11 -0700 HashTable::add() works wrong when inserting of an empty value causes rehash 2014-03-20 21:34:26 -0700 1 1 1 Unclassified WebKit Web Template Framework 528+ (Nightly build) Unspecified Unspecified RESOLVED INVALID P2 Normal --- 1 mikhail.pozdnyakov mikhail.pozdnyakov andersca benjamin cmarcelo commit-queue darin mjs oldest_to_newest 992497 0 mikhail.pozdnyakov 2014-03-20 06:51:11 -0700 HashTable::rehash() always skips re-inserting of an empty entry, this causes wrong result of the parent HashTable::add() call i.e. map.add( empty value ).iterator.get() == nullptr. 992500 1 227288 mikhail.pozdnyakov 2014-03-20 07:16:45 -0700 Created attachment 227288 patch 992538 2 227288 darin 2014-03-20 09:09:11 -0700 Comment on attachment 227288 patch View in context: https://bugs.webkit.org/attachment.cgi?id=227288&action=review > Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp:158 > + ASSERT_TRUE(map.add(0, 0).iterator.get()); This doesn’t look right. We don’t support adding map entries where the key has the empty or deleted value. And 0 is the empty value from HashTraits<int>. So calling add(0, 0) is illegal and should cause an assertion in a debug build and undefined behavior in a release build. 992553 3 mikhail.pozdnyakov 2014-03-20 09:55:16 -0700 (In reply to comment #2) > (From update of attachment 227288 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=227288&action=review > > > Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp:158 > > + ASSERT_TRUE(map.add(0, 0).iterator.get()); > > This doesn’t look right. We don’t support adding map entries where the key has the empty or deleted value. And 0 is the empty value from HashTraits<int>. So calling add(0, 0) is illegal and should cause an assertion in a debug build and undefined behavior in a release build. Ah, I see. Thanks for clarification. Does it depend however on whether 'HashFunctions::safeToCompareToEmptyOrDeleted' is true or false? or we just never expect adding empty values? 992899 4 227288 darin 2014-03-20 21:34:12 -0700 Comment on attachment 227288 patch View in context: https://bugs.webkit.org/attachment.cgi?id=227288&action=review >>> Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp:158 >>> + ASSERT_TRUE(map.add(0, 0).iterator.get()); >> >> This doesn’t look right. We don’t support adding map entries where the key has the empty or deleted value. And 0 is the empty value from HashTraits<int>. So calling add(0, 0) is illegal and should cause an assertion in a debug build and undefined behavior in a release build. > > Ah, I see. Thanks for clarification. Does it depend however on whether 'HashFunctions::safeToCompareToEmptyOrDeleted' is true or false? or we just never expect adding empty values? No, it does not depend on that. The empty and deleted values are reserved values, and it’s illegal to use either of them as keys in the map. HashFunctions::safeToCompareToEmptyOrDeleted is used to control optimizations inside the HashTable template. If it’s false, the template uses a more complex scheme to avoid ever comparing empty and deleted values with the hash function. If it’s true, then the template generates simpler, more efficient code. I’m not sure I remembered that exactly right, but it’s something like that. 227288 2014-03-20 07:16:45 -0700 2014-03-20 21:34:12 -0700 patch bug130509 text/plain 3849 mikhail.pozdnyakov Y29tbWl0IGRhY2FlZjE2OWU1Y2NkYTk3M2UwMjYwYzdiOWFjYmVhYTUwNjc2NGYKQXV0aG9yOiBN aWtoYWlsIFBvemRueWFrb3YgPG1pa2hhaWwucG96ZG55YWtvdkBpbnRlbC5jb20+CkRhdGU6ICAg VGh1IE1hciAyMCAxNjoxNDoxNSAyMDE0ICswMjAwCgogICAgd2sxMzA1MDkKCmRpZmYgLS1naXQg YS9Tb3VyY2UvV1RGL0NoYW5nZUxvZyBiL1NvdXJjZS9XVEYvQ2hhbmdlTG9nCmluZGV4IDVjOGI1 OGEuLjE2OTlhZDggMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XVEYvQ2hhbmdlTG9nCisrKyBiL1NvdXJj ZS9XVEYvQ2hhbmdlTG9nCkBAIC0xLDMgKzEsMjAgQEAKKzIwMTQtMDMtMjAgIE1pa2hhaWwgUG96 ZG55YWtvdiAgPG1pa2hhaWwucG96ZG55YWtvdkBpbnRlbC5jb20+CisKKyAgICAgICAgSGFzaFRh YmxlOjphZGQoKSB3b3JrcyB3cm9uZyB3aGVuIGluc2VydGluZyBvZiBhbiBlbXB0eSB2YWx1ZSBj YXVzZXMgcmVoYXNoCisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNn aT9pZD0xMzA1MDkKKworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAg ICAgICBCZWZvcmUgdGhlIGNoYW5nZWQgSGFzaFRhYmxlOjpyZWhhc2goKSBhbHdheXMgcmV0dXJu ZWQgJ251bGxwdHInCisgICAgICAgIGlmIHRoZSBpbnB1dCBlbnRyeSBoYWQgYmVlbiBlbXB0eSwg dGhpcyBjYXVzZWQgd3JvbmcgcmVzdWx0IG9mIHRoZQorICAgICAgICBwYXJlbnQgSGFzaFRhYmxl OjphZGQoKSBjYWxsIGkuZS4KKworICAgICAgICBtYXAuYWRkKCBlbXB0eSB2YWx1ZSApLml0ZXJh dG9yLmdldCgpID09IG51bGxwdHIuCisKKyAgICAgICAgTm93IEhhc2hUYWJsZTo6cmVoYXNoKCkg aGFuZGxlcyBlbXB0eSBpbnB1dCBlbnRyaWVzLgorCisgICAgICAgICogd3RmL0hhc2hUYWJsZS5o OgorCiAyMDE0LTAzLTE4ICBDYXJsb3MgR2FyY2lhIENhbXBvcyAgPGNnYXJjaWFAaWdhbGlhLmNv bT4KIAogICAgICAgICBbR0xJQl0gQWRkIEdNYWluTG9vcFNvdXJjZSBjbGFzcyB0byB3cmFwIGlk bGUgYW5kIHRpbWVvdXQgc291cmNlcwpkaWZmIC0tZ2l0IGEvU291cmNlL1dURi93dGYvSGFzaFRh YmxlLmggYi9Tb3VyY2UvV1RGL3d0Zi9IYXNoVGFibGUuaAppbmRleCA1YTE3ZTBlLi4zYmM0NThj IDEwMDY0NAotLS0gYS9Tb3VyY2UvV1RGL3d0Zi9IYXNoVGFibGUuaAorKysgYi9Tb3VyY2UvV1RG L3d0Zi9IYXNoVGFibGUuaApAQCAtMTA5MSwxMCArMTA5MSw4IEBAIG5hbWVzcGFjZSBXVEYgewog CiAgICAgICAgIFZhbHVlKiBuZXdFbnRyeSA9IG51bGxwdHI7CiAgICAgICAgIGZvciAoaW50IGkg PSAwOyBpICE9IG9sZFRhYmxlU2l6ZTsgKytpKSB7Ci0gICAgICAgICAgICBpZiAoaXNFbXB0eU9y RGVsZXRlZEJ1Y2tldChvbGRUYWJsZVtpXSkpIHsKLSAgICAgICAgICAgICAgICBBU1NFUlQoJm9s ZFRhYmxlW2ldICE9IGVudHJ5KTsKKyAgICAgICAgICAgIGlmIChpc0VtcHR5T3JEZWxldGVkQnVj a2V0KG9sZFRhYmxlW2ldKSkKICAgICAgICAgICAgICAgICBjb250aW51ZTsKLSAgICAgICAgICAg IH0KIAogICAgICAgICAgICAgVmFsdWUqIHJlaW5zZXJ0ZWRFbnRyeSA9IHJlaW5zZXJ0KHN0ZDo6 bW92ZShvbGRUYWJsZVtpXSkpOwogICAgICAgICAgICAgaWYgKCZvbGRUYWJsZVtpXSA9PSBlbnRy eSkgewpAQCAtMTEwNSw2ICsxMTAzLDE2IEBAIG5hbWVzcGFjZSBXVEYgewogCiAgICAgICAgIG1f ZGVsZXRlZENvdW50ID0gMDsKIAorICAgICAgICAvLyBXZSBjb3VudCBvbiB0aGUgY29tcGlsZXIg dG8gb3B0aW1pemUgb3V0IHRoaXMgYnJhbmNoLgorICAgICAgICBpZiAoSGFzaEZ1bmN0aW9uczo6 c2FmZVRvQ29tcGFyZVRvRW1wdHlPckRlbGV0ZWQpIHsKKyAgICAgICAgICAgIGlmICghbmV3RW50 cnkgJiYgZW50cnkgJiYgaXNFbXB0eUJ1Y2tldCgqZW50cnkpKSB7CisgICAgICAgICAgICAgICAg Ly8gVGhlcmUgbXVzdCBiZSBhIGxlZnQgZW1wdHkgZW50cnksIGxldCdzIGZpbmQgaXQuCisgICAg ICAgICAgICAgICAgaXRlcmF0b3IgZmluZFJlc3VsdCA9IGZpbmQoRXh0cmFjdG9yOjpleHRyYWN0 KCplbnRyeSkpOworICAgICAgICAgICAgICAgIEFTU0VSVChmaW5kUmVzdWx0ICE9IGVuZCgpKTsK KyAgICAgICAgICAgICAgICBuZXdFbnRyeSA9IGZpbmRSZXN1bHQuZ2V0KCk7CisgICAgICAgICAg ICB9CisgICAgICAgIH0KKwogICAgICAgICBkZWFsbG9jYXRlVGFibGUob2xkVGFibGUsIG9sZFRh YmxlU2l6ZSk7CiAKICAgICAgICAgaW50ZXJuYWxDaGVja1RhYmxlQ29uc2lzdGVuY3koKTsKZGlm ZiAtLWdpdCBhL1Rvb2xzL0NoYW5nZUxvZyBiL1Rvb2xzL0NoYW5nZUxvZwppbmRleCAxYTFjN2Ji Li5kMzFmNTMzIDEwMDY0NAotLS0gYS9Ub29scy9DaGFuZ2VMb2cKKysrIGIvVG9vbHMvQ2hhbmdl TG9nCkBAIC0xLDMgKzEsMjEgQEAKKzIwMTQtMDMtMjAgIE1pa2hhaWwgUG96ZG55YWtvdiAgPG1p a2hhaWwucG96ZG55YWtvdkBpbnRlbC5jb20+CisKKyAgICAgICAgSGFzaFRhYmxlOjphZGQoKSB3 b3JrcyB3cm9uZyB3aGVuIGluc2VydGluZyBvZiBhbiBlbXB0eSB2YWx1ZSBjYXVzZXMgcmVoYXNo CisgICAgICAgIGh0dHBzOi8vYnVncy53ZWJraXQub3JnL3Nob3dfYnVnLmNnaT9pZD0xMzA1MDkK KworICAgICAgICBSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KKworICAgICAgICBCZWZvcmUg dGhlIGNoYW5nZWQgSGFzaFRhYmxlOjpyZWhhc2goKSBhbHdheXMgcmV0dXJuZWQgJ251bGxwdHIn CisgICAgICAgIGlmIHRoZSBpbnB1dCBlbnRyeSBoYWQgYmVlbiBlbXB0eSwgdGhpcyBjYXVzZWQg d3JvbmcgcmVzdWx0IG9mIHRoZQorICAgICAgICBwYXJlbnQgSGFzaFRhYmxlOjphZGQoKSBjYWxs IGkuZS4KKworICAgICAgICBtYXAuYWRkKCBlbXB0eSB2YWx1ZSApLml0ZXJhdG9yLmdldCgpID09 IG51bGxwdHIuCisKKyAgICAgICAgTm93IEhhc2hUYWJsZTo6cmVoYXNoKCkgaGFuZGxlcyBlbXB0 eSBpbnB1dCBlbnRyaWVzLgorCisgICAgICAgICogVGVzdFdlYktpdEFQSS9UZXN0cy9XVEYvSGFz aE1hcC5jcHA6CisgICAgICAgIChUZXN0V2ViS2l0QVBJOjpURVNUKTogQWRkZWQgYSB1bml0IHRl c3QuCisKIDIwMTQtMDMtMTkgIFNpbW9uIEZyYXNlciAgPHNpbW9uLmZyYXNlckBhcHBsZS5jb20+ CiAKICAgICAgICAgRXhwb3NlIHRleHQgYW5kIHBhZ2Ugem9vbSBpbiBXSzIgU1BJLCBhbmQgaG9v ayB0aGVtIHVwIGluIE1pbmlCcm93c2VyCmRpZmYgLS1naXQgYS9Ub29scy9UZXN0V2ViS2l0QVBJ L1Rlc3RzL1dURi9IYXNoTWFwLmNwcCBiL1Rvb2xzL1Rlc3RXZWJLaXRBUEkvVGVzdHMvV1RGL0hh c2hNYXAuY3BwCmluZGV4IGQwM2ZiOTUuLjgxMjFlZGQgMTAwNjQ0Ci0tLSBhL1Rvb2xzL1Rlc3RX ZWJLaXRBUEkvVGVzdHMvV1RGL0hhc2hNYXAuY3BwCisrKyBiL1Rvb2xzL1Rlc3RXZWJLaXRBUEkv VGVzdHMvV1RGL0hhc2hNYXAuY3BwCkBAIC0xNDgsNCArMTQ4LDE0IEBAIFRFU1QoV1RGX0hhc2hN YXAsIEluaXRpYWxpemVyTGlzdCkKICAgICBFWFBFQ1RfRVEoc3RkOjpzdHJpbmcoKSwgbWFwLmdl dCg1KSk7CiB9CiAKK3N0cnVjdCBUZXN0SW50SGFzaFRyYWl0cyA6IEhhc2hUcmFpdHM8aW50PiB7 CisgICAgc3RhdGljIGNvbnN0IHVuc2lnbmVkIG1pbmltdW1UYWJsZVNpemUgPSAxOworfTsKKwor VEVTVChXVEZfSGFzaE1hcCwgUmVoYXNoT25JbnNlcnRFbXB0eUVudHJ5KQoreworICAgIEhhc2hN YXA8aW50LCBpbnQsIERlZmF1bHRIYXNoPGludD46Okhhc2gsIFRlc3RJbnRIYXNoVHJhaXRzPiBt YXA7CisgICAgQVNTRVJUX1RSVUUobWFwLmFkZCgwLCAwKS5pdGVyYXRvci5nZXQoKSk7Cit9CisK IH0gLy8gbmFtZXNwYWNlIFRlc3RXZWJLaXRBUEkK