939993 - GenerationalGC: HashMap AddPtr API abuse misplaces hash table entries

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jim Blandy :jimb]

Attachment: assert-AddPtr-matches-Lookup.patch

The attached patch adds an assertion to js/public/HashTable.h that fails when running js/src/jit-test/tests/auto-regress/bug605011.js with a shell build with --enable-exact-rooting --enable-gcgenerational on 64-bit Linux. [deep breath]

I haven't debugged it, but the effect will be that some hashmap entry will simply disappear - which seems like it could have serious consequences.

This resembles bug 908709, but I've reproduced it in changeset d58ab6f6ca0a (Nov 17 2013).

js::HashMap::AddPtr is a typedef for js::HashTable::AddPtr, which contains a pointer to a specific hash table entry (via its Ptr base class), but also caches the hash value of the key that was passed to lookupForAdd so that we don't need to recompute it if we decide to actually insert an entry.

js::HashTable assumes, if obtain an AddPtr by looking up a given key, then any subsequent insertion with that AddPtr will be with the same key - that is, it assumes that the cached hash value is correct. The attached patch simply asserts that this is so, by re-hashing the key every time.

Evidently, generational GC is causing a key to change between the time we produce the AddPtr and the time we insert the entry. This will make the inserted entry effectively disappear. (Resizing the table *might* make it visible again; I haven't checked.)

Comment 1

[Jon Coppeard (:jonco)]

Attachment: bug939993-hashtable-add-assert

There's a couple of places where we use an AddPtr after a potential GC and where the hash is based on a object that may have moved.

In these cases we should detect it and not use the AddPtr.

Comment 2

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8334126 [details] [diff] [review]
bug939993-hashtable-add-assert

Review of attachment 8334126 [details] [diff] [review]:
-----------------------------------------------------------------

This is ok. I keep trying to think of a more general way of doing this. Like

  bool relookupOrAdd(prevGCNumber, currentGCNumber, AddPtr &p, const Lookup &l, const T &t);

or

  bool relookupOrAdd(AddPtr &p, const Lookup &l, const T &t, bool nogcs);
  relookupOrAdd(p, lookup, value, prevnum == cx->zone()->gcNumber);

For the comments, it's "occurred". :-)

Comment 3

[Jim Blandy :jimb]

You could certainly protect the HashMap behind accessors that provided their own AddPtr type and did the appropriate checks.

Comment 4

[Jim Blandy :jimb]

That was written poorly. What I meant was:

Instead of using HashMap directly, you could define your own map type that uses HashMap internally, and provides a similar public interface --- except that its analog to AddPtr would do the appropriate checks.

Comment 5

[Jeff Walden [:Waldo]]

The public API of HashMap and friends is huge.  If you were to go to that much trouble, some sort of traits thing that let the instantiator of the HashMap notify the map that something meaningful changed -- to invalidate in-flight AddPtrs -- would be far safer, I think.

I'd go with the expedient solution for now, given we now have a modicum of assertion coverage for this sort of issue.

Comment 6

[Jon Coppeard (:jonco)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/1b720320ccf4

Comment 7

[Ed Morley [:emorley]]

Unfortunately this and the other bugs in https://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?changeset=db0f8a5eeb33 have been backed out for causing rootanalysis assertions, eg:
https://tbpl.mozilla.org/php/getParsedLog.php?id=30835010&tree=Mozilla-Inbound

Backout:
https://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?changeset=05a0228c2caa

(For quick relanding, I recommend the third party qbackout extension and '--apply' mode)

Comment 8

[Jon Coppeard (:jonco)]

Attachment: bug939993

So the problem with the previous patch was that it checked the gc number for the zone rather than the runtime, and generational GC applies to all zones even when not all zones are being collected.

I added methods to the context classes that made it a bit more clear what's actually going on here.

Comment 9

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8335704 [details] [diff] [review]
bug939993

Review of attachment 8335704 [details] [diff] [review]:
-----------------------------------------------------------------

We'll need to change some names when we implement compacting, non-generational GC, but good enough for now.

Comment 10

[Jon Coppeard (:jonco)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/1469f9e856c0

Comment 11

[Ryan VanderMeulen (PTO, back July 27)]

Backed out for SM rootanalysis crashes.
https://hg.mozilla.org/integration/mozilla-inbound/rev/556a2db58cad

https://tbpl.mozilla.org/php/getParsedLog.php?id=30893419&tree=Mozilla-Inbound

Comment 12

[Jon Coppeard (:jonco)]

What I said in comment 8 was incorrect and also not the cause of the failures, despite the patch passing on try.

Comment 13

[Jon Coppeard (:jonco)]

Attachment: hashtable-add-assert

It turns out that almost everywhere we use relookupOrAdd() has this problem with GGC, although only a couple of them were were triggering the assertion when running our tests.

Here's a patch to add a helper object that does the job of calling lookupForAdd() and then either relookupOrAdd() or putNew() depending on whether a GC happened in the meantime.  I've used this in all appropriate places.

I put it in its own header file because I didn't know where the best place was - a better suggestion would be appreciated.

Comment 14

[Jim Blandy :jimb]

Nice work!

Comment 15

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8336488 [details] [diff] [review]
hashtable-add-assert

Review of attachment 8336488 [details] [diff] [review]:
-----------------------------------------------------------------

I wish there were a nice way to make a better API for this, but I can't think of one.

::: js/src/jshashutil.h
@@ +11,5 @@
> +
> +namespace js {
> +
> +/*
> + * Used to add entires to a js::HashMap or HashSet where the key depends on a GC

*entries

Comment 16

[Jon Coppeard (:jonco)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/042ab55b8476

Comment 17

[Carsten Book [:Tomcat]]

had to backout this change in https://hg.mozilla.org/integration/mozilla-inbound/rev/dc27d67ceda7 for Spidermonkey rootanalysis orange like https://tbpl.mozilla.org/php/getParsedLog.php?id=31040936&tree=Mozilla-Inbound 

also via irc:
< jonco> Tomcat|sheriffduty: actually… this depends on bug 927204, which has been backed out

Comment 18

[Jon Coppeard (:jonco)]

The only part of this causing the failures in rootanalysis builds is the assert.  We're about to replace the rootanalysis build anyway (bug 927204), so I'm going to split this patch in two and land the fixes first.  Then, when the rootanalysis build has been replaced we can land the assert itself.

Comment 19

[Jon Coppeard (:jonco)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e7e1771dd294

Comment 20

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/e7e1771dd294

Comment 21

[Jon Coppeard (:jonco)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/72c344b0e588

Comment 22

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/72c344b0e588