Bug 29118 – StringHash support searching for empty/null strings rather than requiring callers to explicitly check

• Status: RESOLVED
• Resolution: FIXED
• Component: WebCore Misc.

[Kent Tamura]

Some functions in StringHash.h don't handle cases that StringImpl* is NULL.
So, for example,

   HashMap<String, xxx, StringHash> map;
   ...
   map.contains(String());

This code crashes.

I don't know if this makes real crashes in WebKit browsers.

[Kent Tamura]

Created attachment 39324 [details]
Proposed patch

[Darin Adler]

Comment on attachment 39324 [details]
Proposed patch

I don't see the point of this. What's the benefit of this change?

[Kent Tamura]

(In reply to comment #2)
> (From update of attachment 39324 [details])
> I don't see the point of this. What's the benefit of this change?

With the patch, we don't need to worry about nullness of String instances for map keys.  A concrete example is here: https://bugs.webkit.org/attachment.cgi?id=39342&action=review
This code treats an attribute value String as a map key.
If we use String for a map key type, we expect we can use arbitrary instances of String for keys.  However, null String makes crash.

The current StringHash implementation is inconsistent.  equal() function handles null Strings though hash() function doesn't.

[Kent Tamura]

(In reply to comment #3)
Simply saying, we need to write null-check for String-key maps for now in order to avoid crash.
  HashMap<String, xxx, StringHash> map;
  ...
  if (!str.isNull() && map.contais(str)) ...
We can remove "!str.isNull() &&" with this patch.

Null strings can not be a registered key even with the patch.  I think it's ok.

[Darin Adler]

Comment on attachment 39324 [details]
Proposed patch

We made this tradeoff when designing the hash tables in the first place. This change adds a null check branch to all maps with string keys. So the tradeoff is an extra branch in the code path for maps where the key is known to not be null. Is that the right tradeoff? I'd like to hear Maciej's thoughts on this.

[Kent Tamura]

We have some choices:
 a) No code change
    - add a comment about no null-String support
    - add assertion for null String
 b) Add support for null strings to StringHash
 c) Add new hash function classes with null String support; StringHashWithNull, CaseFoldingHashWithNull

[Darin Adler]

Lets get a comment from Maciej.

[Eric Seidel (no email)]

Please email Maciej directly, since he tends to be busy, and has not replied in the bug in 12 days.

[Maciej Stachowiak]

It seems like a tradeoff of performance (potentially) vs slightly easier to use API. It's hard to say offhand which is better. Do we have any testing to determine if this change has performance impact?

[Maciej Stachowiak]

Also, is there a count or estimate of how many null checks we could remove if we made this StringHash change? That would show the potential benefit.

[Kent Tamura]

I checked some instances of HashMap<String, ...>.  I couldn't find any instances for which we can remove null-checks.
 - Many of them had no null-checks.  I'm not sure whether they actually needed no null-checks.
 - Some of them had null-checks, but we can not remove them because the strings are used not only for HashMap keys.

[Adam Barth]

Comment on attachment 39324 [details]
Proposed patch

I like the part of this change that removes a bunch of copy-paste code having to do with avalanches.  It seems like we can unblock this bug with:

1) Benchmarks that show this change doesn't slow us down too much.
2) Examples of crashes that this change fixes.

Until we get this data, this patch isn't really suitable for reviewing.  Feel free to re-nominate when you provide the data.

[Kent Tamura]

Created attachment 41487 [details]
Proposed patch (rev.2)

> 1) Benchmarks that show this change doesn't slow us down too much.

What's a good way to have benchmarks of WebKit?

> 2) Examples of crashes that this change fixes.

I couldn't find examples in the existing code.
Comment #3 is the only example.


Anyway, I minimized the patch.
I'll satisfy myself of it :-)

[Eric Seidel (no email)]

Comment on attachment 41487 [details]
Proposed patch (rev.2)

Extra newline in ChangeLog.  Otherwise this looks fine.

[Kent Tamura]

Created attachment 41552 [details]
Proposed patch (rev.3)

- Remove a blank line
- "doesn't" -> "don't" in the comment

[Eric Seidel (no email)]

Comment on attachment 41552 [details]
Proposed patch (rev.3)

+    // hash() functions of StringHash and CaseFoldingHash don't support for
+    // null strings. get(), contains(), add() of HashMap<String,..., StringHash>
+    // for null strings cause null-pointer dereference.

So I would re-write this as:

The hash() functions on StringHash and CaseFoldingHash do not support null strings.  get(), contains() and add() on HashMap<String, ... , StringHash> cause a null-pointer dereference when passed null strings.

It's close as is, but doesn't quite flow as english.  (Although it flows *way* better than any attempt of mine to write japanese!)

[Kent Tamura]

Created attachment 42625 [details]
Proposed patch (rev.4)

- Updated the comment

Correcting my English is very helpful.  Thanks!

[Darin Adler]

Comment on attachment 42625 [details]
Proposed patch (rev.4)

> +    // hbThe ash() functions on StringHash and CaseFoldingHash do not support

Note the garbled text at the beginning of this comment.

[Kent Tamura]

Created attachment 42725 [details]
Proposed patch (rev.5)

- Fixed the garbled text ;-)

[WebKit Commit Bot]

Comment on attachment 42725 [details]
Proposed patch (rev.5)

Clearing flags on attachment: 42725

Committed r50702: <http://trac.webkit.org/changeset/50702>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.