Closed Bug 759991 Opened 9 years ago Closed 9 years ago

Rekeying can trigger infinite loop


(Core :: JavaScript Engine, defect)

Not set





(Reporter: sfink, Assigned: terrence)




(1 file, 7 obsolete files)

Rekeying basically does

  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.
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'.
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.
Even bettererer: this removes the restriction on rekey that Key === Lookup.
Attached patch v0 (obsolete) — Splinter Review

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
Attachment #630721 - Flags: review?(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
Attached patch v1 (obsolete) — Splinter Review
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)
Comment on attachment 630737 [details] [diff] [review]

Sorry, this ends up in an infinite loop in lookup.  Looking into it now.
Attachment #630737 - Flags: review?(luke)
 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.
Attached patch v2 (obsolete) — Splinter Review
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)
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.
Fix up the fallibility stuff, and prevent putNew from invalidating Enumerations
Attachment #631096 - Flags: review?(luke)
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 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.
Attachment #630781 - Flags: review?(luke)
(In reply to Terrence Cole [:terrence] from comment #9)
> Regarding infallibility, as far as I know, I have never touched add(AddPtr).
I had forgotten how extensive that change was.  Nice cleanup, other than the bug I introduced.
Attachment #630781 - Attachment is obsolete: true
Attachment #631100 - Attachment is obsolete: true
Attachment #631096 - Attachment is obsolete: true
Attachment #631096 - Flags: review?(luke)
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 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+
Attached patch v5: With nits addressed. (obsolete) — Splinter Review
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:
Attachment #631459 - Attachment is obsolete: true
Attachment #631536 - Flags: review+
Duplicate of this bug: 756771
Doh!  I forgot that we are actually using rekeyFront: in testHashTable.cpp.
Attachment #631536 - Attachment is obsolete: true
Attachment #631928 - Flags: review+
Blocks: 763636
OS: Linux → All
Hardware: x86_64 → All
Target Milestone: --- → mozilla16
Version: unspecified → Trunk
Backed out in, relanded in - something needed a clobber, no way of knowing whether it was this.
Closed: 9 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.