553671 - in js_GC: remove (most) goto-based control flow

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Julian Seward [:jseward]]

The top level garbage collector routine

  js_GC(JSContext *cx, JSGCInvocationKind gckind)

uses gotos to jump back and forth.  This leads to, effectively, three
loops, one of which has two entry points.

This is hard to follow, and gets in the way of trying to cleanly
separate the thread-rendezvous logic from the core garbage collection
code.

The condensed control flow graph is shown below.  Each block AA, BB,
etc, is a single-entry-single-exit region and so can be treated as
atomic for the purposes of CFG refactoring.



void
js_GC(JSContext *cx, JSGCInvocationKind gckind)
{
    AA

  restart_at_beginning:
    BB
    if (gckind == GC_SET_SLOT_REQUEST) {
        CC
        if (rt->gcLevel == 1 && !rt->gcPoke && !rt->gcIsNeeded)
            goto done_running;
        DD
        goto restart_at_beginning;
    }
    EE
#ifdef JS_TRACER
    if (JS_ON_TRACE(cx))
        goto out;
#endif
    QQ
  restart:
    FF

#ifdef JS_TRACER
  out:
#endif
    GG
    if (!JS_ON_TRACE(cx) && (rt->gcLevel > 1 || rt->gcPoke)) {
        HH
        goto restart;
    }
    II
  done_running:
    JJ
    if (gckind != GC_SET_SLOT_REQUEST && (callback = rt->gcCallback)) {
        KK
        if (!(gckind & GC_KEEP_ATOMS)) {
            LL
            if (gckind == GC_LAST_CONTEXT && rt->gcPoke)
                goto restart_at_beginning;
         } else {
            MM
        }
        NN
    }
    OO
}

Comment 1

[Julian Seward [:jseward]]

Attachment: patch v1, against 39518:35030f4db298

Comment 2

[Julian Seward [:jseward]]

(In reply to comment #1)
> Created an attachment (id=435604) [details]
> patch v1, against 39518:35030f4db298

Initial version of patch, which unfortunately does not apply to tip
any more.  Will refresh.

What it does:

* Lift out the code that does the actual work of GC into a new
  function, js_GC_WRK.

* gets rid of the labels 'restart', 'out' and 'done_running',
  replacing it with structured control flow, and two new booleans
  'do_GC' and 'do_call_GC_WRK'.

  One label, 'restart_at_beginning', remains.  This is relatively
  harmless and was left in because replacing it with a loop would have
  required indenting the entirety of js_GC one level more.

* The transformation was done mechanically.  Single-entry-single-exit
  control flow regions were identified, and each line of js_GC
  assigned to one such region.  Then I drew the CFG of these SISE
  regions, added minimal booleans to get rid of the labels and the
  dual-entry-point loop, and rearranged the regions accordingly.

* js/src/test results for a JS_THREADSAFE + JS_TRACER build are
  unchanged.

The top level of js_GC now looks like this:

  js_GC()
  {
     // a few initial checks

    restart_at_beginning:
     
     while (1) {
        // stuff which I _think_ is rendezvous logic
        // sets do_GC to true or false
     }

     if (do_GC) {
        // stuff to do with stats and propcache flushing
        // actually call do_GC_WRK
     }

     // a short code (postamble?) which decides if we need to start
     // over
     if (start_over)
         goto restart_at_beginning
  }

Comment 3

[Julian Seward [:jseward]]

Attachment: patch v2, rebased to 39595:181ef94693d5

Comment 4

[Nicholas Nethercote [inactive]]

Nice work!

>   One label, 'restart_at_beginning', remains.  This is relatively
>   harmless and was left in because replacing it with a loop would have
>   required indenting the entirety of js_GC one level more.

I vote for making it a normal loop.  Easier to read and harder to subvert later on.
 
> * The transformation was done mechanically.

I assume that means you did it by hand, but following a mechanical process.

Comment 5

[Brendan Eich [:brendan]]

Does WRK stand for something? Otherwise (or anyway) please avoid _ in the middle, and with C++ or even C statics, no need for js_ in the front. I'll leave it to Jason to finalize the name. Looks like a good cleanup -- js_GC gradually turned into old Unix namei (the pathname lookup function, a goto swamp in its day).

/be

Comment 6

[Julian Seward [:jseward]]

(In reply to comment #5)
> Does WRK stand for something?

"worker"; no strong preference.  I was merely after a name that
denoted the function that really does the work of gc, as opposed
to js_GC, which is now limited to the synch/coordination logic.

Comment 7

[Brendan Eich [:brendan]]

Traditionally we would use DoGC, GCHelper, or perhaps best: just a static function named "GC".

/be

Comment 8

[Nicholas Nethercote [inactive]]

"_WRK" is a Julian special, the Valgrind codebase is littered with them :)

Comment 9

[Brendan Eich [:brendan]]

Now "_WRK" is horrid ;-). But it could be read as hax0r for "wreck" -- doesn't make up for the extra _ but it helps.

We probably want an OOP-style GC class, or GCHeap, to hold all the rt->gcFoo members. Then we could have public and private GC (sub-)methods.

/be

Comment 10

[Andreas Gal :gal]

Look at WebKit's Collector.cpp. They have a template class that gets instantiated per GCThing type. I like that approach a lot.

Comment 11

[Jason Orendorff [:jorendorff]]

(In reply to comment #9)
> We probably want an OOP-style GC class, or GCHeap, to hold all the rt->gcFoo
> members. Then we could have public and private GC (sub-)methods.

Filed bug 556324 for this.

The template approach sounds good too, offhand, and they're not mutually exclusive; you can have

  class GCHeap {
      GCAllocator<JSString> strings;
      GCAllocator<JSObject> objects;
      GCAllocator<jsdouble> doubles;

  public:
      JSString *allocString() { return strings.allocate(); }
      JSObject *allocObject() { return objects.allocate(); }
      jsdouble *allocDouble() { return doubles.allocate(); }
      ...
  };

The top-level GCHeap class is going to be important when we do per-tab GC.

Comment 12

[Julian Seward [:jseward]]

(In reply to comment #10)
Where?  I looked through JavaScriptCore/runtime/Collector.{h,cpp}
but didn't see any template classes; just a bit of word-size
parameterisation in the header file.

Comment 13

[Nicholas Nethercote [inactive]]

Is this mention of templates a red herring?  AFAICT, Julian merely split one oh-my-god-ugly function into two not-so-ugly functions, and there's no mention of types or anything.

Julian, I'd just resubmit the patch with js_GC_WRK renamed as DoGC, GCHelper or GC, a la comment 7.

Comment 14

[Andreas Gal :gal]

Yeah, we were just bikeshedding other GC reorganizations. Wasn't meant to slow down this patch.

Comment 15

[Jason Orendorff [:jorendorff]]

Please rename js_GC_WRK() to GC().

Note that the js_ prefix is (supposed to be) reserved for names declared in
header files, thus visible to other .cpp files within js/src.

Instead of '/*OUT*/struct GCTimer *gcTimer'
please make the argument 'GCTimer *gcTimer'.

I want to think over the rest some more. I'm not sure what you've got is the
best interpretation of the gotos; I think you might be able to remove the gotos
and make the code say what it means without adding quite so many booleans. A
boolean that switches a later if-statement is like a delayed goto. It *can* be
easier for the reader to cope with, but the code has to be readable in the
first place. Note that we already have about 3 different JSRuntime fields that
mean "yeah! let's do it again!"...

If you'd like to commit and push just the part that factors out the GC function, please do so, r=me, and post a new patch for the rest.

Comment 16

[Julian Seward [:jseward]]

Thanks for the feedback.

> A boolean that switches a later if-statement is like a delayed goto.

Yes.  The refactoring doesn't get rid of any of the control-flow
complexity, since that has to do with the underlying logic.  It does
localise it more, though.  Jumps back and forth over the main body of
the function are really undesirable.

> I think you might be able to remove the gotos

That would be nice, but I couldn't see how.  Here's what I did.

There are two main transformations.  Firstly:

    EE
    if (JS_ON_TRACE(cx))
        goto out;
    QQ
  restart:
    FF
  out:
    GG
    if (!JS_ON_TRACE(cx) && (rt->gcLevel > 1 || rt->gcPoke)) {
        HH
        goto restart;
    }
    II

the path  restart: - FF - GG - HH - goto restart  forms a loop.
Problem is it can be entered either at FF by falling through from QQ,
or at GG.  Loops with multiple entry points can't be expressed using
structured control flow without either adding steering booleans, or
duplicating some of the blocks, and I didn't want to do the latter.
Eventually I arrived at

    EE
    if (JS_ON_TRACE(cx)) {
       doFF = false
    } else {
       doFF = true
       QQ
    }
    while (1) {
       if (doFF) FF
       GG
       if (!(!JS_ON_TRACE(cx) && (rt->gcLevel > 1 || rt->gcPoke))) break;
       HH
       doFF = true
    }
    II

where doFF was renamed to 'do_call_GC_WRK' and FF is the call to the
helper.

That makes EE .. II be a single-entry-single-exit block.  The other
main transformation was:

    AA
  restart_at_beginning:
    BB
    if (gckind == GC_SET_SLOT_REQUEST) {
        CC
        if (rt->gcLevel == 1 && !rt->gcPoke && !rt->gcIsNeeded)
            goto done_running;
        DD
        goto restart_at_beginning;
    }
    EE-through-II

becomes

    AA
  restart_at_beginning:
    while (1) {
       BB
       if (!(gckind == GC_SET_SLOT_REQUEST)) {
          doEEII = true
          break
       }
       CC
       if (rt->gcLevel == 1 && !rt->gcPoke && !rt->gcIsNeeded) {
          doEEII = false
          break
       }
       DD
    }
    if (doEEII) {
       EE-through-II
    }

where doEEII is 'do_GC' in the patch.

Comment 17

[Jason Orendorff [:jorendorff]]

Stealing. I started tinkering with this, and once the code is factored a little better, it starts to look like we have a bug or two.

In particular, the behavior when gckind == GC_SET_SLOT_REQUEST and we discover (after handling slot requests) that we need GC seems buggy to me.  We set gckind=GC_LOCK_HELD and goto restart_at_beginning. But doesn't this mean we'll never release the gc lock?

Working on a stack of patches for this. It'll be up today.

Comment 18

[Brendan Eich [:brendan]]

(In reply to comment #17)
> Stealing. I started tinkering with this, and once the code is factored a little
> better, it starts to look like we have a bug or two.

One, or two?

> In particular, the behavior when gckind == GC_SET_SLOT_REQUEST and we discover
> (after handling slot requests) that we need GC seems buggy to me.  We set
> gckind=GC_LOCK_HELD and goto restart_at_beginning. But doesn't this mean we'll
> never release the gc lock?

No. See js_SetProtoOrParent, which calls

            js_GC(cx, GC_SET_SLOT_REQUEST);

and with the GC lock held, and note that (jsgc.h)

    GC_SET_SLOT_REQUEST = GC_LOCK_HELD | 1,

This is all a bit too magical, fair point.

Any other bugs?

/be

Comment 19

[Jason Orendorff [:jorendorff]]

(In reply to comment #18)
>     GC_SET_SLOT_REQUEST = GC_LOCK_HELD | 1,
> This is all a bit too magical, fair point.

Ah! It's not really too magical, except in conjunction with js_GC being really really long and full of gotos. :-)

> Any other bugs?

Nope! I've seen a lot of what *looked* like bugs, but so far they all turn out to be OK on closer examination. Still looking.

Comment 20

[Jason Orendorff [:jorendorff]]

Attachment: part 1, extract GC() from js_GC() - v1

Comment 21

[Jason Orendorff [:jorendorff]]

Attachment: part 2, extract PreGCCleanup() from js_GC() and get rid of 'goto out;' - v1

Comment 22

[Jason Orendorff [:jorendorff]]

Attachment: part 3, extract FireGCBegin() and FireGCEnd() from js_GC() - v1

Comment 23

[Jason Orendorff [:jorendorff]]

Attachment: part 4, RAII for JS_{LOCK,UNLOCK}_GC and JS_{KEEP,UNKEEP}_ATOMS

In the case of JSCompiler, there's technically a change in semantics here. Instead of taking effect at init() time, the JS_KEEP_ATOMS will now happen in JSCompiler::JSCompiler(). I think this is harmless considering what JS_KEEP_ATOMS does and that in each place where a JSCompiler is used, a call to init() follows right away.

Comment 24

[Jason Orendorff [:jorendorff]]

Attachment: part 5, extract GCUntilDone() from js_GC()

Comment 25

[Jason Orendorff [:jorendorff]]

Attachment: part 6, rewrite GCUntilDone() to get rid of the goto

Here I have to use a "steering boolean", but the function is so short that it's fairly obvious what's going on.

Comment 26

[Andreas Gal :gal]

Comment on attachment 436832 [details] [diff] [review]
part 5, extract GCUntilDone() from js_GC()

I really don't like the goto back into the middle of the block (restart). Any way to make that more elegant?

Comment 27

[Jason Orendorff [:jorendorff]]

Andreas: See the next patch!

...I was just about ready to post patch 7, but I found a bug in it, so I think I'll stop for the night.

Comment 28

[Luke Wagner [:luke]]

Comment on attachment 436831 [details] [diff] [review]
part 4, RAII for JS_{LOCK,UNLOCK}_GC and JS_{KEEP,UNKEEP}_ATOMS

Looks clean; I especially like the addition and use of js::Conditionally.

>+class AutoKeepAtoms {
>+    JSRuntime *rt;
>+  public:
>+    explicit AutoKeepAtoms(JSRuntime *rt) : rt(rt) { JS_KEEP_ATOMS(rt); }
>+    ~AutoKeepAtoms() { JS_UNKEEP_ATOMS(rt); }
>+};

Is there a reason to give AutoKeepAtoms an explicit constructor but not AutoLockGC/AutoUnlockGC?

>+                {
>+                    /*
>+                     * Make sure that the GC from another thread respects
>+                     * GC_KEEP_ATOMS.
>+                     */
>+                    Conditionally<AutoKeepAtoms> keepIf(gckind & GC_KEEP_ATOMS, rt);
[snip]
>+                }
>                 rt->requestCount += requestDebit;
>             }

(In js_GC) Is there an invariant involving rt->requestCount and whether or not atoms are kept?  If not, perhaps you could drop the new block.

r+, whichever way you decide to go with these.

Comment 29

[Jeff Walden [:Waldo]]

Comment on attachment 436829 [details] [diff] [review]
part 2, extract PreGCCleanup() from js_GC() and get rid of 'goto out;' - v1

>diff --git a/js/src/jsgc.cpp b/js/src/jsgc.cpp

>+    {
>+        JSContext *iter = NULL, *acx;
>+        while ((acx = js_ContextIterator(rt, JS_TRUE, &iter)) != NULL)
>+            acx->purge();
>+    }

JSContext *iter = NULL;
while (JSContext *acx = js_ContextIterator(rt, JS_TRUE, &iter))
    acx->purge();

Comment 30

[Jeff Walden [:Waldo]]

Comment on attachment 436828 [details] [diff] [review]
part 1, extract GC() from js_GC() - v1

This patch and the GCTIMER gunk is an argument for making a GC class member of JSContext through which implicit arguments can be passed, eventually, but not here and now, of course.


>diff --git a/js/src/jsgc.cpp b/js/src/jsgc.cpp

> /*
>+ * Perform mark-and-sweep GC.
>+ *
>+ * In a JS_THREADSAFE build, the calling thread must be rt->gcThread and each
>+ * other thread must be either outside all requests or blocked waiting for GC
>+ * to finish. Note that the caller does not hold rt->gcLock.
>+ */

Can you assert that first requirement?


>+static void
>+GC(JSContext *cx, JSGCInvocationKind gckind  GCTIMER_PARAM)
>+{
>+    JSRuntime *rt = cx->runtime;
>+    JSTracer trc;
>+    JSGCArena *emptyArenas, *a, **ap;

These should be moved to point of first use, and at least some can be loop-scoped too.

>+#ifdef JS_GCMETER
>+    uint32 nlivearenas, nkilledarenas, nthings;
>+#endif

I'm not sure the code's improved by moving these nearer first use; if you want to leave them at time I'm fine with it.

Comment 31

[Jeff Walden [:Waldo]]

Comment on attachment 436830 [details] [diff] [review]
part 3, extract FireGCBegin() and FireGCEnd() from js_GC() - v1

>diff --git a/js/src/jsgc.cpp b/js/src/jsgc.cpp

>+static bool
>+FireGCBegin(JSContext *cx, JSGCInvocationKind gckind)
>+{
>+    JSRuntime *rt = cx->runtime;
>+    JSGCCallback callback = rt->gcCallback;
>+
>+    /*
>+     * Let the API user decide to defer a GC if it wants to (unless this
>+     * is the last context).  Invoke the callback regardless. Sample the
>+     * callback in case we are freely racing with a JS_SetGCCallback{,RT} on
>+     * another thread.
>+     */
>+    if (gckind != GC_SET_SLOT_REQUEST && callback) {
>+        JSBool ok;

bool

Comment 32

[Jeff Walden [:Waldo]]

I wish I could come up with better names indicating that the callback is called, for the purpose of restarting or vetoing GC, but nothing springs to mind.  ShouldGC and ShouldGCAgain are plausible but don't really indicate callback-callingness, unfortunately.  Better ideas welcome.

Comment 33

[Andreas Gal :gal]

Comment on attachment 436832 [details] [diff] [review]
part 5, extract GCUntilDone() from js_GC()


This is some hairy stuff. Make sure igor is cc-ed on the bug and takes a look too (maybe once the patches are all lined up the total diff against the original).

Comment 34

[Andreas Gal :gal]

Comment on attachment 436834 [details] [diff] [review]
part 6, rewrite GCUntilDone() to get rid of the goto

the firstRun stuff is really weird. Maybe a block around a loop for the unlock and then a PreGCCleanup and timestamp followed by a loop that does the GC call? Up to you. This is already a lot cleaner than before for sure though.

Comment 35

[Jason Orendorff [:jorendorff]]

(In reply to comment #33)
> > /*
> >+ * Perform mark-and-sweep GC.
> >+ *
> >+ * In a JS_THREADSAFE build, the calling thread must be rt->gcThread and each
> >+ * other thread must be either outside all requests or blocked waiting for GC
> >+ * to finish. Note that the caller does not hold rt->gcLock.
> >+ */
> 
> Can you assert that first requirement?

rt->gcLock is just a PRLock, so no, not without considerably increasing the amount of mischief I'm getting into here. I would much rather assert than comment that. Followup bug?

> I'm not sure the code's improved by moving these nearer first use; if you want
> to leave them at time I'm fine with it.

I moved them; those variables are only used in a smallish chunk of code in GC.

> >+        JSBool ok;
>
> bool

JSBool is the return type of the callback, though. I kept it.

Comment 36

[Jason Orendorff [:jorendorff]]

(In reply to comment #28)
> Is there a reason to give AutoKeepAtoms an explicit constructor but not
> AutoLockGC/AutoUnlockGC?

Nope. I'll change them all to be explicit.

> (In js_GC) Is there an invariant involving rt->requestCount and whether or not
> atoms are kept?  If not, perhaps you could drop the new block.

Good suggestion. I'll drop the block.

As I see it, invariants regarding these variables only apply once we release rt->gcLock (a few lines below that code).

Comment 37

[Jason Orendorff [:jorendorff]]

(In reply to comment #34)
> (From update of attachment 436834 [details] [diff] [review])
> the firstRun stuff is really weird. Maybe a block around a loop for the unlock
> and then a PreGCCleanup and timestamp followed by a loop that does the GC call

A single AutoUnlockGC wouldn't do the trick, because we have to hold the gcLock when testing the loop condition.

With a small amount of repetition, we can do either of these:

static void
GCUntilDone(JSContext *cx, JSGCInvocationKind gckind  GCTIMER_PARAM)
{
    JS_ASSERT_NOT_ON_TRACE(cx);
    JSRuntime *rt = cx->runtime;

    rt->gcLevel = 1;
    rt->gcPoke = JS_FALSE;
    {
        AutoUnlockGC unlock(rt);
        PreGCCleanup(cx, gckind);
        TIMESTAMP(gcTimer.startMark);
        GC(cx, gckind  GCTIMER_ARG);
    }

    // GC again if:
    //   - another thread, not in a request, called js_GC
    //   - js_GC was called recursively
    //   - a finalizer called js_RemoveRoot or js_UnlockGCThingRT.
    while (rt->gcLevel > 1 || rt->gcPoke || rt->gcIsNeeded) {
        rt->gcLevel = 1;
        rt->gcPoke = JS_FALSE;

        AutoUnlockGC unlock(rt);
        GC(cx, gckind  GCTIMER_ARG);
    }
}

static void
GCUntilDone(JSContext *cx, JSGCInvocationKind gckind  GCTIMER_PARAM)
{
    JS_ASSERT_NOT_ON_TRACE(cx);
    JSRuntime *rt = cx->runtime;

    rt->gcLevel = 1;
    rt->gcPoke = JS_FALSE;
    JS_UNLOCK_GC(rt);
    PreGCCleanup(cx, gckind);
    TIMESTAMP(gcTimer.startMark);

    for (;;) {
        GC(cx, gckind  GCTIMER_ARG);
        JS_LOCK_GC(rt);

        // GC again if:
        //   - another thread, not in a request, called js_GC
        //   - js_GC was called recursively
        //   - a finalizer called js_RemoveRoot or js_UnlockGCThingRT.
        if (rt->gcLevel == 1 && !rt->gcPoke && !rt->gcIsNeeded)
            break;
        rt->gcLevel = 1;
        rt->gcPoke = JS_FALSE;

        JS_UNLOCK_GC(rt);
    }
}

...but I think I like the firstRun style better, since it avoids duplication of code and shows exactly how the first run differs from subsequent runs.

Comment 38

[Jason Orendorff [:jorendorff]]

Part 1: http://hg.mozilla.org/tracemonkey/rev/0572716d8e61
Part 1 review comments: http://hg.mozilla.org/tracemonkey/rev/66300e46f562
Part 2: http://hg.mozilla.org/tracemonkey/rev/5f848272c9b4
Part 3: http://hg.mozilla.org/tracemonkey/rev/60322feb630f
Part 4: http://hg.mozilla.org/tracemonkey/rev/428857f6bd48
Part 5: http://hg.mozilla.org/tracemonkey/rev/0bbd1a88dae2
Part 6: http://hg.mozilla.org/tracemonkey/rev/7b71fdd8d8cb

Comment 39

[Jason Orendorff [:jorendorff]]

Following up on comment 19: I filed bug 558150 (which might not even be a bug) and bug 558181 (which is also pretty minor). I didn't find any serious bugs.

Comment 40

[Jason Orendorff [:jorendorff]]

Attachment: part 7, extract BeginGCSession() and EndGCSession() from js_GC() - v1

Comment 41

[Jason Orendorff [:jorendorff]]

Attachment: part 8, reimplement promotion of GC_SET_SLOT_REQUEST to GC_LOCK_HELD and get rid of 'goto done_running;'

This eliminates a 'goto restart_at_beginning;' jump by duplicating the code that it would re-execute. It turns out to be just 6 lines now that the code is factored into functions. (diffstat says this patch removes 39 lines and adds 30, a net win.)

Comment 42

[Jason Orendorff [:jorendorff]]

Attachment: part 9, extract ProcessSetSlotRequests() from js_GC() - v1

Part 8 is the tricky bit; this is the grunt work of moving the new code into its own function.

Comment 43

[Jason Orendorff [:jorendorff]]

Attachment: part 10, get rid of 'goto restart_at_beginning;'

No change in behavior is intended.

I wrote

  for(;;) {
      if (!FireGCBegin(...))
          return;
      ...
      if (FireGCEnd(...))
          break;
  }

instead of

  do {
      if (!FireGCBegin(...))
          return;
      ...
  } while (!FireGCEnd(...));

because I like the aesthetic balance for FireGCBegin and FireGCEnd both being called in the loop. If you think that's dumb, I'll change it. :-)

Comment 44

[Jason Orendorff [:jorendorff]]

Attachment: part 11, refactor GCTimer - v1

Actually, no change in behavior is intended in any of these.

Comment 45

[Luke Wagner [:luke]]

Comment on attachment 437991 [details] [diff] [review]
part 10, get rid of 'goto restart_at_beginning;'

Nice work

Comment 46

[Jason Orendorff [:jorendorff]]

Attachment: part 12, handle GC_KEEP_ATOMS more directly - v1

This one is subtler. I think we can handle GC_KEEP_ATOMS with a single line of code in js_GC(). If that's correct, we can eliminate the gckind parameter to a few functions, including GC().

I deleted this comment in GC():

-        /*
-         * Query rt->gcKeepAtoms only when we know that all other threads are
-         * suspended, see bug 541790.
-         */

because I think the cleanup has rendered it too obvious to warrant comment. Now the whole body of GC happens with other threads suspended. There seems no need to call out this particular line of code as depending on that. The danger that someone might rearrange a few lines of code and reintroduce bug 541790 is essentially gone.

I'll be happy to put the comment back if you disagree, of course.

Comment 47

[Luke Wagner [:luke]]

Comment on attachment 437995 [details] [diff] [review]
part 11, refactor GCTimer - v1

Looks good, although 1E6 does look an awful lot like IE6...

Comment 48

[Brendan Eich [:brendan]]

(In reply to comment #47)
> (From update of attachment 437995 [details] [diff] [review])
> Looks good, although 1E6 does look an awful lot like IE6...

1e6 is best ;-).

/be

Comment 49

[Igor Bukanov]

Sorry for the review delay - I will do it on Tuesday.

Comment 50

[Igor Bukanov]

(In reply to comment #40)
> Created an attachment (id=437972) [details]
> part 7, extract BeginGCSession() and EndGCSession() from js_GC() - v1

I am not sure that this is the right approach. Setting the parent and proto is not a GC operation even if it was implemented like that. For example, the proto operation does not delegate its job to another thread while the js_GC asks already running GC to do the job again. Also setting proto cannot be canceled from the GC callback. And that operation does not need to repeat.

So those differences suggest to try other approaches rather than generalizing a specific hack. For example, we could try to implement a common infrastructure to allow for one thread to wait until all other threads suspends their requests. For example, JS_BeginRequest does:

    while (rt->gcLevel > 0)
        JS_AWAIT_GC_DONE(rt);
 
If we can replace that with something like

    while (rt->onlyOneRunningRequest)
        JS_AWAIT_GC_DONE(rt);

then we can use that onlyOneRunningRequest mode to implement both the GC and the slot mutation. 

Another possibility is taking the GC LOCK while doing the parent/proto slot mutation whenever we discover an object not owned by other thread.

Thoughts?

Comment 51

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/0572716d8e61

Comment 52

[Robert Sayre]

igor, jwalden, let's review these. they're small.

Comment 53

[Robert Sayre]

oh, I see unanswered questions, sorry.

Comment 54

[Jason Orendorff [:jorendorff]]

(In reply to comment #50)
> So those differences suggest to try other approaches rather than generalizing a
> specific hack.

I agree, and I spent a lot of time looking for ways to do that. All the patches in this bug are intended to help get us there.

Ultimately, I'd like js_GC to look like this:

    void js_GC(JSContext *cx) {
        AutoLockGC lock(cx->runtime);
        cx->runtime->forceGC = 1;  // ask for some work to be done
        ProcessTasks(cx);  // note: no arguments indicating what work to do
    }

    void js_LastDitchGC(JSContext *cx) {
        AutoLockGC lock(cx->runtime);
        AutoKeepAtoms keep(cx->runtime);
        cx->runtime->forceGC = 1;
        ProcessTasks(cx);
    }

    void js_LastContextGC(JSContext *cx) {
        AutoLockGC lock(cx->runtime);
        cx->runtime->forceGC = 1;
        cx->runtime->lastContextGC = 1;
        ProcessTasks(cx);
    }

And js_SetProtoOrParent would do this:

        ...
        AutoLockGC lock(cx->runtime);
        ssr.next = cx->runtime->tasks.add(&ssr);  // linked list of tasks
        ProcessTasks(cx);

ProcessTasks would wait for all requests to end, do all requested work, regardless of which thread requested it, and then let the suspended requests resume.  I like this because its correctness seems more obvious--convincing myself our current stuff was correct took a long time.

I stopped short of that in this bug because it's hard to do without changing API behavior, namely the GC hook. I think we should replace that API with something that better fits the use cases, but I wanted to get through this bug without changing behavior.

But having one function to stop the world and a separate function to resume seems like a good idea to me anyway. The end result of this stack of patches is that js_GC is 50 lines long and says what it means. We can keep going from there.

Comment 55

[Brendan Eich [:brendan]]

Comment 54 is hawt. :-|

/be

Comment 56

[Jeff Walden [:Waldo]]

Comment on attachment 437989 [details] [diff] [review]
part 9, extract ProcessSetSlotRequests() from js_GC() - v1

ProcessSetSlotRequest and ProcessSetSlotRequests are insufficiently different names at a glance.  Add Single/One or All to one of the methods?

Tangential, perhaps followup territory, but the *SetSlotRequest name is kind of wordy and vague.  Not sure what a better name would be; maybe it becomes simpler when we get rid of the parent concept altogether sometime.


>diff --git a/js/src/jsgc.cpp b/js/src/jsgc.cpp

>+    while (JSSetSlotRequest *ssr = rt->setSlotRequests) {
>+        rt->setSlotRequests = ssr->next;
>+        AutoUnlockGC unlock(rt);
>+        ssr->next = NULL;
>+        ProcessSetSlotRequest(cx, ssr);
>+    }

You can push the AutoUnlockGC and next-nulling into ProcessSetSlotRequest, right?  Seems better to abstract those details into the request-processing code than to require such knowledge from the caller.

Comment 57

[Igor Bukanov]

(In reply to comment #54)
> ProcessTasks would wait for all requests to end, do all requested work,
> regardless of which thread requested it, and then let the suspended requests
> resume. 

It cannot be that simple since js_GC must be able to check if there is already a GC task submitted and delegate the job to it while the parent slot setter should always run. That is, the pseudo code for js_GC barring the bugs is:

    lock_gc();
    if (serialized_task_is_running) {
        if (serialized_task_is_gc) {
            tell_that_task_to_do_more_gc;
            return;
        }
        wait_until_the_serialized_task_finishes;
    }
    start_serialization_task();
    unlock_gc();

    mark_and_sweep;

    lock_gc();
    stop_serialization_task();
    unlock_gc();
 
while the parent setter looks like:

    lock_gc();
    if (serialized_task_is_running) {
        wait_until_the_serialized_task_finishes;
    }
    start_serialization_task();
    unlock_gc();

    set_parent;

    lock_gc();
    stop_serialization_task();
    unlock_gc();

So how that is going to be refactored?

Comment 58

[Igor Bukanov]

(In reply to comment #57)
> That is, the pseudo code for js_GC barring the bugs is:
> 
>     lock_gc();
>     if (serialized_task_is_running) {
>         if (serialized_task_is_gc) {
>             tell_that_task_to_do_more_gc;
>             return;
>         }
>         wait_until_the_serialized_task_finishes;
>     }
>     start_serialization_task();
>     unlock_gc();
> 
>     mark_and_sweep;
> 
>     lock_gc();
>     stop_serialization_task();
>     unlock_gc();

That is wrong, the correct version for the GC is:

    lock_gc();
    if (serialized_task_is_running) {
        if (serialized_task_is_gc) {
            tell_that_task_to_do_more_gc;
            wait_until_the_serialized_task_finishes;
            return;
        }
        wait_until_the_serialized_task_finishes;
    }
    start_serialization_task();
    unlock_gc();

    mark_and_sweep;

    lock_gc();
    stop_serialization_task();
    unlock_gc();

Comment 59

[Jason Orendorff [:jorendorff]]

> So how that is going to be refactored?

The serialization-task thread will simply loop until there are no more tasks, like this:

    AutoLockGC lock;
    while (rt->forceGC || rt->tasks) {
        while (take a task from rt->tasks) {
            AutoUnlockGC unlock;
            do the task;
        }
        if (rt->forceGC) {
            rt->forceGC = 0;
            AutoUnlockGC unlock;
            GC();
        }
    }

Won't that work as desired?

Comment 60

[Jason Orendorff [:jorendorff]]

The code in comment 59 neglects the lastContextGC flag, but that seems easy enough to add back.

Comment 61

[Igor Bukanov]

(In reply to comment #59)
>     AutoLockGC lock;
>     while (rt->forceGC || rt->tasks) {
>         while (take a task from rt->tasks) {
>             AutoUnlockGC unlock;
>             do the task;
>         }
>         if (rt->forceGC) {
>             rt->forceGC = 0;
>             AutoUnlockGC unlock;
>             GC();
>         }
>     }

Hm, but how the above code asks the GC already started on another thread to do the job?

Comment 62

[Jason Orendorff [:jorendorff]]

Comment 54 says:

    void js_GC(JSContext *cx) {
        AutoLockGC lock(cx->runtime);
        cx->runtime->forceGC = 1;  // ask for some work to be done
        ProcessTasks(cx);  // note: no arguments indicating what work to do
    }

Suppose thread 2 calls this while thread 1 has already started GC and is running the code in comment 59.

Then here's what will happen: thread 2 will set forceGC, then block in ProcessTasks waiting for thread 1 to finish.  Thread 1 will detect that forceGC has been set again, and instead of exiting the while loop, it'll do more GC before signaling for the other threads to resume.

Comment 63

[Igor Bukanov]

(In reply to comment #62)
> Then here's what will happen: thread 2 will set forceGC, then block in
> ProcessTasks waiting for thread 1 to finish.  Thread 1 will detect that forceGC
> has been set again, and instead of exiting the while loop, it'll do more GC
> before signaling for the other threads to resume.

Currently any thread calling js_GC when the GC is running will trigger another run of the GC. So to preserve that semantics we would need not a boolean flag but rather a counter. 

On another hand that semantics is not that useful given that the enforced request model as even js_RemoveRoot waits for the GC to finish. As such another thread cannot create a garbage while the GC is running so asking for more GC cycles is counter-productive.

This suggests to change the GC so calls to js_GC from other threads would just wait the GC is running somewhere without triggering extra GC runs. 

Yet another observation is that we can implement the last ditch GC using js_GC via code like:

js_LastDicthGC(cx)
{
    JSAutoKeepAtoms keepAtoms(cx->runtime);
    AutoSaveWeakRoots weakRoots(cx);
    js_GC(GC_LOCK_HELD);
}

Given the complexity of the GC we can afford an extra atomic increment and an extra copiing of weak roots compared with the current code.

Also we can eliminate GC_LAST_CONTEXT since the GC can just check if rt->state is JSRTS_LANDING. 

With this changes refactoring the GC would be much simpler.

Comment 64

[Igor Bukanov]

(In reply to comment #63)
> 
> js_LastDicthGC(cx)
> {
>     JSAutoKeepAtoms keepAtoms(cx->runtime);
>     AutoSaveWeakRoots weakRoots(cx);
>     js_GC(GC_LOCK_HELD);
> }

Note that this will remove the need to do saving of weak roots during callback calls etc.

Comment 65

[Igor Bukanov]

Also we should do other work in another bug. The current code has removed most of the goto in the GC fulfilling the title promise.

Comment 66

[Jason Orendorff [:jorendorff]]

Igor, I'm confused about the situation in this bug. I posted a whole stack of patches here, and every patch got review except the three I put in your queue. I think our discussion in this bug has been good, but to me, it seems like we're talking about future changes that lie beyond the scope of this bug--plans that reinforce the need for the patches already in your queue. What remains that's holding up review on these patches?

When you suggest doing further work in another bug, do you mean we should close this bug and throw away the remaining patches? Three of those already have review, but they depend on the patches you haven't reviewed.

The new bug you've filed, but 560471, is a great idea. I'm totally in favor. But it's a little frustrating to me that the patch there duplicates a lot of the work in part 12 here, a patch that's been in your review queue for over a week.

> The current code has removed most
> of the goto in the GC fulfilling the title promise.

The remaining patches remove all the gotos. Why not follow through with that?

Comment 67

[Jeff Walden [:Waldo]]

(In reply to comment #63)
> Currently any thread calling js_GC when the GC is running will trigger another
> run of the GC. So to preserve that semantics we would need not a boolean flag
> but rather a counter. 

I don't think we should saddle ourselves with the task of emulating every latent interaction detail of inherently non-deterministic APIs like GC.  In particular, the idea of doing doing a rescan that will collect almost no garbage seems to have little value.

> Given the complexity of the GC we can afford an extra atomic increment and an
> extra copiing of weak roots compared with the current code.

But as this bug's patches demonstrate, the cost here isn't a runtime cost but a complexity cost.  If we can avoid complexity here, even if it doesn't show up in profiles, I think we should.

Comment 68

[Igor Bukanov]

(In reply to comment #66)
> Igor, I'm confused about the situation in this bug. I posted a whole stack of
> patches here, and every patch got review except the three I put in your queue.
> I think our discussion in this bug has been good, but to me, it seems like
> we're talking about future changes that lie beyond the scope of this bug--plans
> that reinforce the need for the patches already in your queue. What remains
> that's holding up review on these patches?

Sorry for a late review, but all gotos can be removed with simpler approach than the one suggested in the bug and it took me a while to realize that. Also consider that the final patch still contain GC_SET_SLOT_REQUEST checks that are spread among small functions that is harder to follow IMO.


> 
> When you suggest doing further work in another bug, do you mean we should close
> this bug and throw away the remaining patches? Three of those already have
> review, but they depend on the patches you haven't reviewed.
> 
> The new bug you've filed, but 560471, is a great idea. I'm totally in favor.
> But it's a little frustrating to me that the patch there duplicates a lot of
> the work in part 12 here, a patch that's been in your review queue for over a
> week.
> 
> > The current code has removed most
> > of the goto in the GC fulfilling the title promise.
> 
> The remaining patches remove all the gotos. Why not follow through with that?

Comment 69

[Andreas Gal :gal]

I don't see any reason why we can't do further improvements on top of this patch, once it has landed.

Comment 70

[Igor Bukanov]

(In reply to comment #69)
> I don't see any reason why we can't do further improvements on top of this
> patch, once it has landed.

Because another approach diverges from the the suggested one approximately at the current TM tip level. Farther improvements would mean backing out the landed patches first and taking another direction.

Comment 71

[Andreas Gal :gal]

I am sorry, but I have to disagree. We have a sequence of patches at hand, reviewed by a half dozen people, that make the current code cleaner and easier to follow. I think we can do alternative experiments after landing.

This bug reminds me of Gregor's 100 comment bug that we finally closed last week. After making him run around in circles for months he ended up committing essentially the original 20-liner he proposed months ago. That was not an efficient use of his time.

jorendorff invested significant time refactoring the code and in my eyes it looks a lot better. Other people spent time understanding the refactoring. I think we should apply his patches, and take further improvements from there, instead of stalling him pending potential future solutions that are not at hand and have no review.

Comment 72

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

(In reply to comment #70)
> (In reply to comment #69)
> > I don't see any reason why we can't do further improvements on top of this
> > patch, once it has landed.
> 
> Because another approach diverges from the the suggested one approximately at
> the current TM tip level. Farther improvements would mean backing out the
> landed patches first and taking another direction.

Is it generally agreed that suggested one is superior, and that we should spend the time in the near term (including tracking the trunk) to implement it?  If you want to make a case for a different approach, that's fine to do, but I don't think it's respectful to block the requested review on it; that's not why review is being requested, and -- as in gregor's bug -- the patch here is a strict improvement.  You can ask Jason if he prefers to pursue your direction rather than the one here that is ready to commit once you perform the requested review, but in this case it seems pretty clear.  If it means that the patch in another bug is based on a backout of one of these, then that doesn't seem like it adds a lot of burden to the future author.

Comment 73

[Igor Bukanov]

(In reply to comment #72)
> Is it generally agreed that suggested one is superior, and that we should spend
> the time in the near term (including tracking the trunk) to implement it?  If
> you want to make a case for a different approach, that's fine to do, but I
> don't think it's respectful to block the requested review on it; that's not why
> review is being requested, and -- as in gregor's bug -- the patch here is a
> strict improvement.

That is what I disagree with. The end result with the proposed patches introduces a lot of small functions that still contains quite a few if conditions that is hard to follow IMO. But that is my personal opinion and if in general it is agreed that the proposed changes are the preferred solution, than somebody else should review the patches.

Comment 74

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Why can you not do the review?  I don't understand.  (In fact, I thought you _had_ reviewed, which is how you discovered the small functions that you dislike.)

Comment 75

[Igor Bukanov]

(In reply to comment #74)
> Why can you not do the review?

The patches that I have been asked to review looks reasonable from functionality point of view. But I disagree with the structure of js_GC and friends that results from these and other patches. So my review is biased against that structure and will results in suggestions (like that bug 560471) that are incompatible with already reviewed patches build on top of these resulting in more work for everybody.

Comment 76

[Robert Sayre]

> But I disagree with the structure of js_GC and friends that results from these and other patches

Jason wrote a huge 12 part patch that untangles a nasty nest of gotos that's been there for *years*. It's not code that would get a positive review these days.

We should check it in and keep iterating.

Comment 77

[Brendan Eich [:brendan]]

Let's not go on about gotos, they can surely make for hard-to-maintain code, but so can other things including if-then-else random logic.

Also, jorendorff did to jseward's original patch in this bug an analogous better-is-friend-of-good thing that igor arguably intends. Let's not assume bad intent; but I want to raise the best-is-enemy-of-good problem, which can hurt us too, and which seems to be an ongoing issue re: the GC.

With Mercurial we can afford a bit more back-and-forth in patching code, so long as we all agree on design decisions. We should not try to hold up partial progress for longer-term progress that can be done stepwise, even with some backward steps.

Proof that this series makes progress: rebasing Igor's patch for bug 560471 makes that patch smaller, not larger.

So on balance, this bug's patch series should go in, and followup bugs should simplify the logic. With that, I'll r+ based on comment 75.

/be

Comment 78

[Brendan Eich [:brendan]]

Comment on attachment 437972 [details] [diff] [review]
part 7, extract BeginGCSession() and EndGCSession() from js_GC() - v1

>+    /*
>+     * If this thread is already the GC thread, we have reentered
>+     * js_GC. Bumping rt->gcLevel above ensures that another GC cycle will
>+     * happen after the current one.

Nit: rewrap to consistent wrapmargin.

/be

Comment 79

[Jason Orendorff [:jorendorff]]

http://hg.mozilla.org/tracemonkey/rev/c9e100d0d826 - part 7
http://hg.mozilla.org/tracemonkey/rev/b70bbdf422c1 - part 8
http://hg.mozilla.org/tracemonkey/rev/5c62b43a93cd - part 9
http://hg.mozilla.org/tracemonkey/rev/3a902c4e89d8 - part 10
http://hg.mozilla.org/tracemonkey/rev/c6c7a9345409 - part 11
http://hg.mozilla.org/tracemonkey/rev/22d5eaa2724e - part 12
http://hg.mozilla.org/tracemonkey/rev/3b06e9fbbf2e - Merge.

Comment 80

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/c9e100d0d826