759991 - Rekeying can trigger infinite loop

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

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

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

[Luke Wagner [:luke]]

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

[Luke Wagner [:luke]]

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

[Luke Wagner [:luke]]

Even bettererer: this removes the restriction on rekey that Key === Lookup.

Comment 4

[Terrence Cole [:terrence]]

Attachment: 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?

Comment 5

[Luke Wagner [:luke]]

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
?

Comment 6

[Terrence Cole [:terrence]]

Attachment: 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.

Comment 7

[Terrence Cole [:terrence]]

Comment on attachment 630737 [details] [diff] [review]
v1

Sorry, this ends up in an infinite loop in lookup.  Looking into it now.

Comment 8

[Luke Wagner [:luke]]

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.

Comment 9

[Terrence Cole [:terrence]]

Attachment: 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.

Comment 10

[Luke Wagner [:luke]]

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.

Comment 11

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

Attachment: Fix infinite loop in rekeyFront with fully collided Table

Fix up the fallibility stuff, and prevent putNew from invalidating Enumerations

Comment 12

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

Attachment: 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

[Luke Wagner [:luke]]

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.

Comment 14

[Luke Wagner [:luke]]

(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

Comment 15

[Terrence Cole [:terrence]]

I had forgotten how extensive that change was.  Nice cleanup, other than the bug I introduced.

Comment 16

[Terrence Cole [:terrence]]

Attachment: 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.

Comment 17

[Luke Wagner [:luke]]

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.

Comment 18

[Terrence Cole [:terrence]]

Attachment: 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

Comment 20

[Terrence Cole [:terrence]]

Attachment: v6: Updated testHashTable.cpp

Doh!  I forgot that we are actually using rekeyFront: in testHashTable.cpp.

Comment 21

[Terrence Cole [:terrence]]

New try run is up at:
https://tbpl.mozilla.org/?tree=Try&rev=184d0aa0c1b4

Comment 22

[Terrence Cole [:terrence]]

This looks ready:
https://hg.mozilla.org/integration/mozilla-inbound/rev/ecbe3c75551d

Comment 23

[Phil Ringnalda (:philor)]

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.

Comment 24

[Graeme McCutcheon [:graememcc]]

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