Rekeying can trigger infinite loop

RESOLVED FIXED in mozilla16

Status

()

Core
JavaScript Engine
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: sfink, Assigned: terrence)

Tracking

Trunk
mozilla16
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 7 obsolete attachments)

(Reporter)

Description

5 years ago
Rekeying basically does

  remove(entry);
  add(lookup, entry);

and then when a full enumeration is complete, it checks for under/overflow.

But it can overflow during the enumeration, which will result in an infinite loop when attempting to find a place to add a rekeyed entry. add() can use up a table slot.

I'm not sure what the fix is, since rebuilding the table mid-enumeration is going to scrozzle the Enum.

My current workaround is to modify rekeyFront() to return a boolean indicating whether it is overloaded. If so, I restart the enumeration (rekeying an entry is idempotent). I would prefer an alternative solution.

See also bug 758362, which isn't really related other than being another rekeying problem.

Comment 1

5 years ago
Good point!  The fatal assumption is that, if we remove an entry, then add will always be able to, at the very least, use that entry, so we can't run out of space and iloop.  The problem is that lookupForAdd can't stop as soon as it finds a free entry: if the collision bit is set, it has to keep looking because (in the general case) *maybe* the element is already in the table further down the collision chain.

I think the right fix here is to add a new 'add' path for adding an element when you know it isn't already present.  With that information, lookup can stop the first time it finds a removed element with the collision bit set thereby avoiding the iloop problem above.

We actually already have a helper, putNew, currently implemented in terms of lookupForAdd+addwith that I believe has exactly the semantics we'd want, so we can just re-implement that and have rekey use putNew.  As a bonus, putNew will now offer a speed bonus over plain 'add'.

Comment 2

5 years ago
Bill just pointed out that, even better than being able to stop on the first removed entry, we don't even need to call 'match' on intermediate entries since we know they will return false.  Better still, we already have an algorithm for that: findFreeEntry.

Comment 3

5 years ago
Even bettererer: this removes the restriction on rekey that Key === Lookup.
(Assignee)

Comment 4

5 years ago
Created attachment 630721 [details] [diff] [review]
v0

https://tbpl.mozilla.org/?tree=Try&rev=3fa482d8ea36

This fixes the infinite loop I was hitting in GenerationalGC.  Steve, could you try using this with MovingGC to see if it also works there?
Assignee: general → terrence
Status: NEW → ASSIGNED
Attachment #630721 - Flags: review?(luke)

Comment 5

5 years ago
IIUC, Hash{Map,Set}::lookupNewForAdd is only used inside Hash{Map,Set}::putNew.  Could you instead just:
 1. rename HashTable::addNew to HashTable::putNew
 2. have Hash{Map,Set}::putNew call HashTable::putNew
?
(Assignee)

Comment 6

5 years ago
Created attachment 630737 [details] [diff] [review]
v1

Thank you, that is indeed much cleaner.  The only reservation I have now is that the failure condition for putNew with an already present key is an infinite loop instead of an assertion failure.  Given that we don't currently have any known putNew bugs, this is probably acceptable, given that the bug will still be detected.
Attachment #630721 - Attachment is obsolete: true
Attachment #630721 - Flags: review?(luke)
Attachment #630737 - Flags: review?(luke)
(Assignee)

Comment 7

5 years ago
Comment on attachment 630737 [details] [diff] [review]
v1

Sorry, this ends up in an infinite loop in lookup.  Looking into it now.
Attachment #630737 - Flags: review?(luke)

Comment 8

5 years ago
Also:
 1. I think you can remove the add(const Lookup &, const Entry &) overload (which was added for rekey)
 2. I happened to notice that the add(AddPtr&) overload still always returns 'true' thus making 'add' infallible.  I thought we fixed all this?  We need to (re)fix this.
(Assignee)

Comment 9

5 years ago
Created attachment 630781 [details] [diff] [review]
v2

putNew(Lookup, T) needed a checkOverflow(), like in add(AddPtr).

Regarding infallibility, as far as I know, I have never touched add(AddPtr).  It seems like it (and putNew) should be able to fail if checkOverloaded() fails and then findFreeEntry does not find a free entry.  I'm actually glad you mentioned it, because I had been working under the assumption that I was missing something subtle.
Attachment #630737 - Attachment is obsolete: true
Attachment #630781 - Flags: review?(luke)

Comment 10

5 years ago
Well, add(AddPtr) used to be able to oom.  I think we need to fix that.
Also, if putNew is exposed via Hash{Map,Set}::putNew then it can fail also.
(Reporter)

Comment 11

5 years ago
Created attachment 631096 [details] [diff] [review]
Fix infinite loop in rekeyFront with fully collided Table

Fix up the fallibility stuff, and prevent putNew from invalidating Enumerations
Attachment #631096 - Flags: review?(luke)
(Reporter)

Comment 12

5 years ago
Created attachment 631100 [details] [diff] [review]
Implement findNewEntry for addNew

Note that the fix in this bug depends on earlier changes that Terrence made to add the findNewEntry thing. I'm attaching it here for reference; I'm not sure what the status of it is. (I had to pull it out to apply this stuff to m-i, since Holly is a little too broken to use as a testbed.)

Comment 13

5 years ago
Comment on attachment 631096 [details] [diff] [review]
Fix infinite loop in rekeyFront with fully collided Table

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

Thanks for fixing the oom problem Steve!  I'm a bit confused by all the patches here...

::: js/public/HashTable.h
@@ +245,3 @@
>              if (added) {
> +                if (!table.checkOverloaded())
> +                    return false;

IIUC, if table.checkOverloaded fails, the hash table can be left w/o any free slots, leading to an iloop on the next lookupForAdd.  Thus, any caller that does rekey must use the fallible endEnumeration: ~Enum() swallows the error since it has no way to report.  Thus, I think we should replace the "if (added)" in ~Enum() to "JS_ASSERT(!added)".

@@ +618,5 @@
>          destroyTable(*this, oldTable, oldCap);
>          return true;
>      }
>  
> +    bool addNew(const Lookup &l, const Entry &e)

Can you rename this to putNew and remove the putNew below?  That is, it is almost identical to putNew except it does "return checkOverloaded", which is right, whereas putNew returns whether any elements were added which requires callers to checkOverloaded.

@@ +790,1 @@
>                  /* Preserve the validity of |p.entry|. */

nit: can you put the comment above the if so that there are no curlies?

@@ +1230,5 @@
>  
>      /* Like put, but assert that the given key is not already present. */
>      bool putNew(const Key &k, const Value &v) {
> +        if (impl.putNew(k, Entry(k, v)))
> +            return impl.checkOverloaded();

So with the putNew change above, this can just be "return impl.putNew(...)", x2 below.

Updated

5 years ago
Attachment #630781 - Flags: review?(luke)

Comment 14

5 years ago
(In reply to Terrence Cole [:terrence] from comment #9)
> Regarding infallibility, as far as I know, I have never touched add(AddPtr).

http://hg.mozilla.org/mozilla-central/diff/c9024bcb8da0/js/public/HashTable.h#l1.396
(Assignee)

Comment 15

5 years ago
I had forgotten how extensive that change was.  Nice cleanup, other than the bug I introduced.
(Assignee)

Updated

5 years ago
Attachment #630781 - Attachment is obsolete: true
(Assignee)

Updated

5 years ago
Attachment #631100 - Attachment is obsolete: true
(Assignee)

Updated

5 years ago
Attachment #631096 - Attachment is obsolete: true
Attachment #631096 - Flags: review?(luke)
(Assignee)

Comment 16

5 years ago
Created attachment 631459 [details] [diff] [review]
v4: Squashed and combined with feedback addressed.

I'm going to tag Steve back out for this round, since he's out of the office this Friday.

This is mostly a squashed and combined version of our patches, but I also reworked how the checkOverloaded status gets sent back.  What we really have is 3 states, not 4, so I think an enum is better than 2 bools for this usage.
Attachment #631459 - Flags: review?(luke)

Comment 17

5 years ago
Comment on attachment 631459 [details] [diff] [review]
v4: Squashed and combined with feedback addressed.

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

Great!  Some simple nits:

::: js/public/HashTable.h
@@ +546,5 @@
>              }
>          }
>      }
>  
> +    enum RebuildStatus { TableSizeOkay, TableRebuilt, TableRebuildFailed };

Great idea.  Nit: since can the names be:
 NotOverloaded, Rehashed, RehashFailed
?  (My reasoning is that (1) we use "rehash" in other places and (2) it is not the "size" that is ok so much as the "load".)

@@ +726,3 @@
>                  p.entry = &findFreeEntry(p.keyHash);
> +            else if (status == TableRebuildFailed)
> +                return false;

Even though this is as correct, it would look a little nicer to me if this was:

  RebuildStatus status = checkOverloaded();
  if (status == RehashFailed)
      return false;
  if (status == Rehashed)
      p.entry = &findFreeEntry(p.keyHash);

@@ +754,5 @@
>          p.entry->t = t;
>          return true;
>      }
>  
> +    bool putNew(const Lookup &l, const T &t, bool checkOverload = true)

Ohh, I think I was missing this detail handled by the checkOverload parameter above; I see now; good idea.

@@ +771,5 @@
> +            RebuildStatus status = checkOverloaded();
> +            if (status == TableRebuilt)
> +                entry = &findFreeEntry(keyHash);
> +            else if (status == TableRebuildFailed)
> +                return false;

Since prepareHash/findFreeEntry do not change overloaded-ness, perhaps this overloaded check could be hoisted above them.  This would avoid the complexity of re-looking up the entry (which add(AddPtr&) has to do b/c the entry pointer is an outparam.

With that hoisting, then we could just create two functions:

putNewInfallible(), which doesn't check and is called by rekey
putNew() which checks overload, then calls putNewInfallible.

Then, rekey won't need to (void) the return b/c putNewInfallible has a void return value.
Attachment #631459 - Flags: review?(luke) → review+
(Assignee)

Comment 18

5 years ago
Created attachment 631536 [details] [diff] [review]
v5: With nits addressed.

Thanks for the good RebuildStatus names.  I put ~5 layers of paint on that shed before I gave up in frustration.  Also, excellent spot on factoring out the checkOverloaded: much prettier than a bool parameter.

And I'm actually going to follow my "No HashTable push without a Try run" rule for once:
https://tbpl.mozilla.org/?tree=Try&rev=c818c54526cf
Attachment #631459 - Attachment is obsolete: true
Attachment #631536 - Flags: review+

Updated

5 years ago
Duplicate of this bug: 756771
(Assignee)

Comment 20

5 years ago
Created attachment 631928 [details] [diff] [review]
v6: Updated testHashTable.cpp

Doh!  I forgot that we are actually using rekeyFront: in testHashTable.cpp.
Attachment #631536 - Attachment is obsolete: true
Attachment #631928 - Flags: review+
(Assignee)

Comment 21

5 years ago
New try run is up at:
https://tbpl.mozilla.org/?tree=Try&rev=184d0aa0c1b4
(Assignee)

Updated

5 years ago
Blocks: 763636
(Assignee)

Comment 22

5 years ago
This looks ready:
https://hg.mozilla.org/integration/mozilla-inbound/rev/ecbe3c75551d
(Assignee)

Updated

5 years ago
OS: Linux → All
Hardware: x86_64 → All
Target Milestone: --- → mozilla16
Version: unspecified → Trunk
Backed out in https://hg.mozilla.org/integration/mozilla-inbound/rev/038ab46bfb08, relanded in https://hg.mozilla.org/integration/mozilla-inbound/rev/e128263f45f4 - something needed a clobber, no way of knowing whether it was this.
https://hg.mozilla.org/mozilla-central/rev/e128263f45f4
Status: ASSIGNED → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.