Closed Bug 939993 Opened 8 years ago Closed 8 years ago

GenerationalGC: HashMap AddPtr API abuse misplaces hash table entries


(Core :: JavaScript Engine, defect)

Not set



Tracking Status
firefox28 --- fixed


(Reporter: jimb, Assigned: jonco)




(1 file, 3 obsolete files)

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.)
Assignee: nobody → jcoppeard
Attached patch bug939993-hashtable-add-assert (obsolete) — Splinter Review
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.
Attachment #8334062 - Attachment is obsolete: true
Attachment #8334126 - Flags: review?(sphink)
Comment on attachment 8334126 [details] [diff] [review]

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);


  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". :-)
Attachment #8334126 - Flags: review?(sphink) → review+
You could certainly protect the HashMap behind accessors that provided their own AddPtr type and did the appropriate checks.
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.
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.
Unfortunately this and the other bugs in have been backed out for causing rootanalysis assertions, eg:


(For quick relanding, I recommend the third party qbackout extension and '--apply' mode)
Attached patch bug939993 (obsolete) — Splinter Review
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.
Attachment #8334126 - Attachment is obsolete: true
Attachment #8335704 - Flags: review?(sphink)
Comment on attachment 8335704 [details] [diff] [review]

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.
Attachment #8335704 - Flags: review?(sphink) → review+
What I said in comment 8 was incorrect and also not the cause of the failures, despite the patch passing on try.
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.
Attachment #8335704 - Attachment is obsolete: true
Attachment #8336488 - Flags: review?(sphink)
Nice work!
Comment on attachment 8336488 [details] [diff] [review]

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

Attachment #8336488 - Flags: review?(sphink) → review+
had to backout this change in for Spidermonkey rootanalysis orange like 

also via irc:
< jonco> Tomcat|sheriffduty: actually… this depends on bug 927204, which has been backed out
Depends on: 927204
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.
Whiteboard: [leave open]
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla28
Flags: in-testsuite?
You need to log in before you can comment on or make changes to this bug.