Bug 29118 - StringHash support searching for empty/null strings rather than requiring callers to explicitly check
Summary: StringHash support searching for empty/null strings rather than requiring cal...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: WebCore Misc. (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Kent Tamura
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2009-09-09 23:17 PDT by Kent Tamura
Modified: 2009-11-09 17:46 PST (History)
4 users (show)

See Also:


Attachments
Proposed patch (8.07 KB, patch)
2009-09-09 23:32 PDT, Kent Tamura
abarth: review-
Details | Formatted Diff | Diff
Proposed patch (rev.2) (1.52 KB, patch)
2009-10-19 23:59 PDT, Kent Tamura
eric: review+
eric: commit-queue-
Details | Formatted Diff | Diff
Proposed patch (rev.3) (1.52 KB, patch)
2009-10-21 00:42 PDT, Kent Tamura
no flags Details | Formatted Diff | Diff
Proposed patch (rev.4) (1.54 KB, patch)
2009-11-05 20:26 PST, Kent Tamura
darin: review-
Details | Formatted Diff | Diff
Proposed patch (rev.5) (1.53 KB, patch)
2009-11-08 18:32 PST, Kent Tamura
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Kent Tamura 2009-09-09 23:17:10 PDT
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.
Comment 1 Kent Tamura 2009-09-09 23:32:12 PDT
Created attachment 39324 [details]
Proposed patch
Comment 2 Darin Adler 2009-09-10 07:16:15 PDT
Comment on attachment 39324 [details]
Proposed patch

I don't see the point of this. What's the benefit of this change?
Comment 3 Kent Tamura 2009-09-10 08:45:09 PDT
(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.
Comment 4 Kent Tamura 2009-09-10 09:05:15 PDT
(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.
Comment 5 Darin Adler 2009-09-10 09:16:54 PDT
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.
Comment 6 Kent Tamura 2009-09-10 18:52:37 PDT
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
Comment 7 Darin Adler 2009-09-11 11:20:57 PDT
Lets get a comment from Maciej.
Comment 8 Eric Seidel (no email) 2009-09-23 10:54:40 PDT
Please email Maciej directly, since he tends to be busy, and has not replied in the bug in 12 days.
Comment 9 Maciej Stachowiak 2009-09-24 22:24:55 PDT
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?
Comment 10 Maciej Stachowiak 2009-09-24 22:27:11 PDT
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.
Comment 11 Kent Tamura 2009-09-29 00:06:58 PDT
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.
Comment 12 Adam Barth 2009-10-13 13:27:53 PDT
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.
Comment 13 Kent Tamura 2009-10-19 23:59:42 PDT
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 :-)
Comment 14 Eric Seidel (no email) 2009-10-20 12:07:01 PDT
Comment on attachment 41487 [details]
Proposed patch (rev.2)

Extra newline in ChangeLog.  Otherwise this looks fine.
Comment 15 Kent Tamura 2009-10-21 00:42:42 PDT
Created attachment 41552 [details]
Proposed patch (rev.3)

- Remove a blank line
- "doesn't" -> "don't" in the comment
Comment 16 Eric Seidel (no email) 2009-11-04 10:05:31 PST
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!)
Comment 17 Kent Tamura 2009-11-05 20:26:43 PST
Created attachment 42625 [details]
Proposed patch (rev.4)

- Updated the comment

Correcting my English is very helpful.  Thanks!
Comment 18 Darin Adler 2009-11-06 11:22:23 PST
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.
Comment 19 Kent Tamura 2009-11-08 18:32:50 PST
Created attachment 42725 [details]
Proposed patch (rev.5)

- Fixed the garbled text ;-)
Comment 20 WebKit Commit Bot 2009-11-09 17:46:20 PST
Comment on attachment 42725 [details]
Proposed patch (rev.5)

Clearing flags on attachment: 42725

Committed r50702: <http://trac.webkit.org/changeset/50702>
Comment 21 WebKit Commit Bot 2009-11-09 17:46:25 PST
All reviewed patches have been landed.  Closing bug.