637993 - GCHashtable should guard against rehash during iteration

Status: RESOLVED FIXED

(Tamarin Graveyard :: Garbage Collection (mmGC), defect, P3)

Description

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

At least one iterative loop over GCHashtable has potential to rehash the table before the iteration is complete.  I don't know of cases where this is desired behavior.  It does not cost much to guard against it, even via DEBUG-only state.

Will be posting patch shortly.

Comment 1

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

Attachment: patch. too aggressive?

Comment 2

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

Attachment: fixed patch. Still aggressive.

Comment 3

[Tommy Reilly]

Seems pretty intrusive, couldn't we just have an "numInteratorsActive" count in the HT and assert that no iterators are active in rehash?

Comment 4

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

(In reply to comment #3)
> Seems pretty intrusive, couldn't we just have an "numInteratorsActive" count in
> the HT and assert that no iterators are active in rehash?

How would you know when to decrement the numIteratorsActive count?

Would it be based on an iteration reaching the end of the table?  Or are you thinking that the numIteratorsActive count would get decremented in the Iterator's destructor?  (Either of the two options strikes me as more fragile than what I was suggesting in my patch.)

Comment 5

[Tommy Reilly]

Comment on attachment 516301 [details] [diff] [review]
fixed patch.  Still aggressive.

I think the ops should be zero'd in the dtor not incremented.   Its kinda academic since it will be poisoned if its a heap allocation but its a good convention to follow since it allows a GCHashtable to be used in a RCObject.

Comment 6

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

(In reply to comment #4)
> (In reply to comment #3)
> > Seems pretty intrusive, couldn't we just have an "numInteratorsActive" count in
> > the HT and assert that no iterators are active in rehash?
> 
> How would you know when to decrement the numIteratorsActive count?
> 
> Would it be based on an iteration reaching the end of the table?  Or are you
> thinking that the numIteratorsActive count would get decremented in the
> Iterator's destructor?  (Either of the two options strikes me as more fragile
> than what I was suggesting in my patch.)

Tommy and I discussed offline.

Summary: these options aren't that much more fragile, as long as one puts the checks into all the places where I currently am incrementing numIteratorsActiveCount.  But only doing the assert in rehash alone (ie. the grow() method) misses the point, as it won't catch programming mistakes as often.

Comment 7

[Lars T Hansen]

Comment on attachment 516301 [details] [diff] [review]
fixed patch.  Still aggressive.

Seems reasonable and safe.  Presumably aggressiveness would be reduced by moving increments of the timestamp further into conditions where bad things are actually about to happen.  I like the current trade-off.  Agree that having a count of active iterators would lead to better assertions because the execution of an unsafe operation would trigger the assert immediately, this leads to good blame assignment, whereas what you have here has poor blame assignment.

Comment 8

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

Attachment: selftest for this bug

A selftest.  It covers the cases of add and remove.

Comment 9

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

Attachment: fix: guards by counting active Iterators for each table.

patch v3: this one counts the "active" iterators, like Tommy suggested.

I should have mentioned on attachment 534554 [details] [diff] [review]: the point of the last test in that file, rehash_during_iteration_assert_fails_2, is to make clear a distinction between the approach in attachment 516301 [details] [diff] [review] (v2 of this patch) and this attachment (v3): if the Iterator is still in scope but never going to be used again, we'll still assert in response to a modification to the hashtable.

This came up in particular in the GC.cpp source code: in GC::ClearUnmarkedWeakRefs, I had to restrict the scope of the weakRefs iterator so that it will be destructed before weakRefs.prune() is invoked.  That's part of the attached patch.

Comment 10

[Tamarin Bot]

changeset: 6344:bdb968fd2df6
user:      Felix S Klock II <[e-mail]>
summary:   Bug 637993: Ensure no active iterators when may rehash GCHashtable (r=treilly, sr=lhansen).

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

Comment 11

[Tamarin Bot]

changeset: 6345:5d7bd9d8f8fa
user:      Felix S Klock II <[e-mail]>
summary:   Bug 637993: selftest with explicit tests for should-assert cases (r=treilly, sr=lhansen).

http://hg.mozilla.org/tamarin-redux/rev/5d7bd9d8f8fa

Comment 12

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

(whoops, still need to push to tr-serrano)

Comment 13

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

Pushed to TR-serrano rev 6282:2f7d6ce4b108

http://asteam.corp.adobe.com/hg/tamarin-redux-serrano/rev/2f7d6ce4b108

Comment 14

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

(I conciously chose not to port the selftest because its too much of a pain to add new selftests to the code base, and it won't be a big deal for the selftest to wait until Anza.)

((See also Bug 604347 ... there are rumblings that it may get ported to TR-serrano; if that happens, then I/we should reconsider the above choice.))

Comment 15

[Brent Baker]

(In reply to comment #14)
> (I conciously chose not to port the selftest because its too much of a pain
> to add new selftests to the code base, and it won't be a big deal for the
> selftest to wait until Anza.)
> 
> ((See also Bug 604347 ... there are rumblings that it may get ported to
> TR-serrano; if that happens, then I/we should reconsider the above choice.))

Selftest changes to make it easy to author selftests have been merged into the serrano branch:
 tamarin-redux-serrano/rev/63df5389b295

Comment 16

[Brent Baker]

Selftest pushed to tr-serrano:

tamarin-redux-serrano brbaker$ hg log -r 0db93a718dcc
changeset:   6295:0db93a718dcc
tag:         tip
user:        Felix S Klock II <[e-mail]>
date:        Mon May 23 13:58:00 2011 -0400
summary:     Bug 637993: selftest with explicit tests for should-assert cases (r=treilly, sr=lhansen).

Comment 17

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

This revision should probably have been associated with this Bug ticket, but unfortunately was not.

  changeset: 6353:fed12375eb1f 
  user:      Tommy Reilly <[e-mail]>
  summary:   Fix iterator assert in blacklist code with extra braces (r=felix) 
  http://hg.mozilla.org/tamarin-redux/rev/fed12375eb1f

Comment 18

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

Pushed to Serrano as well, after I discovered the shell selftests are failing after you enable-heap-graph.

  tamarin-redux-serrano
  changeset: 6319:ea5e66f1e9a9 
  user:      Felix S Klock II <[e-mail]>
  summary:   Bug 637993: Fix iterator assert in blacklist code with extra braces (code=treilly, r=fklockii).
  http://asteam.corp.adobe.com/hg/tamarin-redux-serrano/rev/ea5e66f1e9a9

Comment 19

[Tamarin Bot]

changeset: 6510:8f2b3de537f3
user:      Felix S Klock II <[e-mail]>
summary:   Bug 637993: fix build with MMGC_WEAKREF_PROFILER enabled (r=fklockii).

http://hg.mozilla.org/tamarin-redux/rev/8f2b3de537f3