744261 - Expand hash table only when adding a new entry

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[William Maddox]

Growing the property hash table of an object while enumerating the properties of the object may result in an anomalous sequence of values, due to rehashing.  A programmer aware of this will be careful to avoid adding new properties during the enumeration.  Unfortunately, we expand the table in 'add()' whenever it is at or above the target load factor, regardless of whether we are defining a new property, or simply updating the value of an existing one.  It is thus possible for a grow/rehash anomaly to occur while merely updating the *value* of an existing property during enumeration.

We should expand the hash table only when adding new properties.

Comment 1

[William Maddox]

This is probably the underlying cause of bug 513016.

Comment 2

[William Maddox]

Attachment: Grow/rehash only after adding a new element

Asking Ruchi for feedback as I know she's working on another issue affecting hash tables at the moment.

Comment 3

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 613829 [details] [diff] [review]
Grow/rehash only after adding a new element

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

::: core/avmplusHashtable.cpp
@@ +103,5 @@
>              WBATOM(gc, atomContainer, &atoms[i], name);
>              m_size++;
> +            //atoms[i+1] = value;
> +            WBATOM(gc, atomContainer, &atoms[i+1], value);
> +            if (isFull()) grow(toplevel);

Isn't this changing the growth policy slightly in that it grows immediately after an addition that filled the table, rather than waiting until the next addition to do the growth?  (And thus is wasting space on the corner cases where the filling-addition was also the final one?)

Comment 4

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 613829 [details] [diff] [review]
Grow/rehash only after adding a new element

(fixing typo in Bill's "F?" request)

Comment 5

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 613829 [details] [diff] [review]
Grow/rehash only after adding a new element

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

::: core/avmplusHashtable.cpp
@@ +101,1 @@
>              AvmAssert(!isFull());

You need to kill off this assertion if you land this change.

Comment 6

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 613829 [details] [diff] [review]
Grow/rehash only after adding a new element

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

::: core/avmplusHashtable.cpp
@@ +101,1 @@
>              AvmAssert(!isFull());

or wait, no, the assertion stays, as it should.  (Sorry, jumped the gun a little there.)

Comment 7

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 613829 [details] [diff] [review]
Grow/rehash only after adding a new element

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

::: core/avmplusHashtable.cpp
@@ +103,5 @@
>              WBATOM(gc, atomContainer, &atoms[i], name);
>              m_size++;
> +            //atoms[i+1] = value;
> +            WBATOM(gc, atomContainer, &atoms[i+1], value);
> +            if (isFull()) grow(toplevel);

I tried revising the growth mechanism myself to delay the resize until after we've confirmed that we need to add a new entry and the table is full, but the problem is that find() requires at least one empty entry to exist in order for its loop to terminate.

I do realize that the previous policy was wasteful in a different manner.

So its not wrong to revise the policy in the manner that Bill suggests.  Switching my review to R+.

Comment 8

[Ruchi Lohani]

Comment on attachment 613829 [details] [diff] [review]
Grow/rehash only after adding a new element

I am wondering if we need to have InlineHashtable::grow() as protected or should it really be private?

Comment 9

[Ruchi Lohani]

(In reply to Ruchi Lohani from comment #8)
> Comment on attachment 613829 [details] [diff] [review]
> Grow/rehash only after adding a new element
> 
> I am wondering if we need to have InlineHashtable::grow() as protected or
> should it really be private?

Ignore my comment #8. Weak tables are all friend of InlineHashtable.

Comment 10

[Tamarin Bot]

changeset: 7351:10c0845dcc1d
user:      William Maddox <[e-mail]>
summary:   Bug 744261 - Expand hash table only when adding a new entry (r=fklockii)

http://hg.mozilla.org/tamarin-redux/rev/10c0845dcc1d

Comment 11

[William Maddox]

It has been reported that this change causes a storage leak.  By moving the grow() call into InlineHashTable::put() just after adding an element, we now assure that the table is never full upon return from WeakValueHashtable::add().  As a result, the test for isFull() at the beginning of WeakValueHashtable::add() cannot succeed, and prune() will never be called.  Likewise for WeakKeyHashtable.

Instead, we must invoke prune() from within put(), immediately prior to the call to grow(), as was done previously.

Comment 12

[William Maddox]

The leak is believed to be the cause of WE 3225260.

Comment 13

[William Maddox]

Attachment: Proposed fix for storage leak

Instead of pushing the grow() down into the put(), put() now returns a boolean status indicating whether a new element was allocated.  If so, the caller is responsible for calling grow(), as well as any necessary pruning of weak entries.

Comment 14

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 644178 [details] [diff] [review]
Proposed fix for storage leak

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

Really good catch!  Wish my earlier review had caught it.  :(

I wonder if some of the leaks I am currently investigating are going to be resolved by this patch.  Can't hurt to try, right?  :)

::: core/avmplusHashtable.cpp
@@ +662,5 @@
>      /*virtual*/ void WeakKeyHashtable::add(Atom key, Atom value, Toplevel* toplevel)
>      {
> +        if (ht.put(getKey(key), value)) {
> +            if (ht.isFull()) {
> +                prune();

Wait, should you first check if the pruning successfully got us some free space before calling ht.grow(toplevel) ?

@@ +740,5 @@
>              value = AvmCore::genericObjectToAtom(wf);
>          }
> +        if (ht.put(key, value)) {
> +            if (ht.isFull()) {
> +                prune();

Likewise as above, should you check if pruning got some free space before calling ht.grow(toplevel) ?

::: core/avmplusHashtable.h
@@ +258,5 @@
>          };
>      
>          bool hasDeletedItems() const;
>          void setCapacity(uint32_t cap);
> +        bool put(Atom name, Atom value);

Please add documentation comment with the meaning of the return value.  Your explanation from comment 13 should suffice.

Comment 15

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 644178 [details] [diff] [review]
Proposed fix for storage leak

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

::: core/avmplusHashtable.cpp
@@ +663,5 @@
>      {
> +        if (ht.put(getKey(key), value)) {
> +            if (ht.isFull()) {
> +                prune();
> +                ht.grow(toplevel);

(Bugzilla's splinter->comment conversion omits trailing lines, so I'm just throwing this comment on to provide more context for my earlier comment about checking whether prune freed up some room before growing.)

Comment 16

[William Maddox]

(In reply to Felix S Klock II from comment #14)

> > +        if (ht.put(getKey(key), value)) {
> > +            if (ht.isFull()) {
> > +                prune();
> 
> Wait, should you first check if the pruning successfully got us some free
> space before calling ht.grow(toplevel) ?

Pruning simply marks the dead entries as DELETED, and does nothing to account for the recoverable space other than to note that the table contains deleted entries.
Instead, grow() is responsible for determining whether growth is actually needed, and takes the presence of deleted items into account.  The 'prune(); grow()' idiom also follows the logic prior to the patch in attachment 613829 [details] [diff] [review].  See this comment
in grow():
   // If we have deleted slots, we don't grow our HT because our rehash will 
   // clear out spots for us.

Comment 17

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to William Maddox from comment #16)

Oh okay.  Sorry, I should have dove in more deeply first.

Anyway, looks good.

Comment 18

[Tamarin Bot]

changeset: 7501:af191ec43460
user:      William Maddox <[e-mail]>
summary:   Bug 744261: Correct weak hashtable storage leak introduced by the original fix

http://hg.mozilla.org/tamarin-redux/rev/af191ec43460