Last Comment Bug 476653 - TM: Crash [@ QuoteString]
: TM: Crash [@ QuoteString]
Status: VERIFIED FIXED
[sg:investigate]
: crash, testcase, verified1.9.1
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: x86 Mac OS X
: P2 critical (vote)
: ---
Assigned To: David Anderson [:dvander]
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on:
Blocks: jsfunfuzz 463478 463487 476192 477877 478481
  Show dependency treegraph
 
Reported: 2009-02-03 07:33 PST by Gary Kwong [:gkw] [:nth10sd]
Modified: 2011-06-13 10:01 PDT (History)
10 users (show)
sayrer: blocking1.9.1+
dveditz: wanted1.9.0.x-
bob: in‑testsuite+
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
gdb info (13.65 KB, text/plain)
2009-02-03 07:33 PST, Gary Kwong [:gkw] [:nth10sd]
no flags Details
verbose output (92.82 KB, text/plain)
2009-02-03 07:39 PST, Gary Kwong [:gkw] [:nth10sd]
no flags Details
proposed fix (6.25 KB, patch)
2009-02-11 20:44 PST, David Anderson [:dvander]
no flags Details | Diff | Splinter Review
proposed fix, v2 (5.54 KB, patch)
2009-02-14 09:49 PST, David Anderson [:dvander]
no flags Details | Diff | Splinter Review
proposed fix, v3 (6.38 KB, patch)
2009-02-19 13:18 PST, David Anderson [:dvander]
gal: review+
Details | Diff | Splinter Review
proposed fix, v4 (8.22 KB, patch)
2009-02-21 12:54 PST, David Anderson [:dvander]
dvander: review-
Details | Diff | Splinter Review
v5 (8.42 KB, patch)
2009-02-24 12:18 PST, David Anderson [:dvander]
gal: review+
Details | Diff | Splinter Review
v6 (9.04 KB, patch)
2009-02-24 19:15 PST, David Anderson [:dvander]
gal: review+
Details | Diff | Splinter Review
js1_8/extensions/regress-476653.js (2.34 KB, text/plain)
2009-03-03 11:13 PST, Bob Clary [:bc:]
no flags Details

Description User image Gary Kwong [:gkw] [:nth10sd] 2009-02-03 07:33:56 PST
Created attachment 360311 [details]
gdb info

for each (let x1 in ['']) 
for (i = 0; i < 1; ++i) {}
delete uneval;
for (i = 0; i < 1; ++i) {}
for each (let x in [new String('q'), '', /x/, '', /x/]) { for (var y = 0; y < 7; ++y) { if (y == 2 || y == 6) { setter = x; } } }
this.(z)

crashes TM opt at QuoteString at 0x00000000000ec000 and TM debug at the same location. Non-TM shells show this -- "typein:6: TypeError: XML filter is applied to non-XML value ({i:1, y:7, setter:/x/})"

Nominating security-sensitive because I do not know if a crash at 0x000ec000 is possibly exploitable.
Comment 1 User image Gary Kwong [:gkw] [:nth10sd] 2009-02-03 07:36:13 PST
Thanks jorendorff for helping me with this on IRC.
Comment 2 User image Gary Kwong [:gkw] [:nth10sd] 2009-02-03 07:39:29 PST
Created attachment 360312 [details]
verbose output
Comment 3 User image Gary Kwong [:gkw] [:nth10sd] 2009-02-03 07:52:14 PST
Related to bug 468324?
Comment 4 User image David Anderson [:dvander] 2009-02-03 08:14:24 PST
(gdb) p (JSClass*)str.u.chars
$8 = (JSClass *) 0x1b2000
(gdb) p *$
$9 = {
  name = 0x193fd6 "RegExp", 
  flags = 168296705, 
  addProperty = 0x19842 <JS_PropertyStub>, 
  delProperty = 0x19842 <JS_PropertyStub>, 
  getProperty = 0xdad30 <regexp_getProperty>, 
  setProperty = 0xdaec8 <regexp_setProperty>, 
  enumerate = 0x19850 <JS_EnumerateStub>, 
  resolve = 0x1985e <JS_ResolveStub>, 
  convert = 0x1986c <JS_ConvertStub>, 
  finalize = 0xdb3aa <regexp_finalize>, 
  getObjectOps = 0, 
  checkAccess = 0, 
  call = 0xde070 <regexp_call>, 
  construct = 0, 
  xdrObject = 0xdb448 <regexp_xdrObject>, 
  hasInstance = 0, 
  mark = 0xdb626 <regexp_trace>, 
  reserveSlots = 0
}
Comment 5 User image David Anderson [:dvander] 2009-02-07 23:46:44 PST
Example of what is breaking:

Trace #1 is built with an empty typemap.
Trace #1 is later executed again with a global, and thus its entry and exit typemaps loo like:

Entry #1: Object
Exit  #1: 

Later we get trace #2:

Entry #2: String
Exit  #2: Object

Exit #2 will be stitched to entry #1.  Now if js_ExecuteTree executes trace #2, we'll come out of exit #1, and exit_gslots < ngslots.  The typemap merging process then uses the outermost tree, which is wrong - the object gets tagged as a string.
Comment 6 User image David Anderson [:dvander] 2009-02-11 20:44:25 PST
Created attachment 361929 [details] [diff] [review]
proposed fix

js_CallTree now links guards together as it unwinds deeply nested guards.  LeaveTree uses this to construct the correct order of global typemaps.
Comment 7 User image Andreas Gal :gal 2009-02-13 15:12:50 PST
On a second mental iteration over this approach I start to really dislike mucking with guards once they have been written to the code cache. Eventually we want to place them into the native code area, which will be write-protected. David, could we achieve the same thing by writing out the current types of all know globals into FrameInfo, which we write into the cache and then point to from the rp stack? When we exit we walk the rp stack backwards and collect all globals along the way. What do you think?
Comment 8 User image David Anderson [:dvander] 2009-02-13 16:08:39 PST
There isn't guaranteed to be anything on the call stack.
Comment 9 User image Andreas Gal :gal 2009-02-13 16:22:46 PST
Right. So what we really need is linking stuff on the machine callstack. We
could do realloc and a buffer in InterpStruct that grows if needed and then is
deallocated.
Comment 10 User image David Anderson [:dvander] 2009-02-13 16:32:52 PST
What happens if realloc() fails?  That's what I was worried about - it's not infallible, but the solution has to be.
Comment 11 User image David Anderson [:dvander] 2009-02-13 16:40:10 PST
I don't think this solution is too problematic - if and when we move guards to unwritable pages, we can keep a separate guard buffer and have guards point into that.
Comment 12 User image Andreas Gal :gal 2009-02-13 16:46:31 PST
We don't have any good recovery for out-of-memory malloc anyway. If that happens we die in an arbitrary number of places right now (not saying we should add another one, but still).
Comment 13 User image Andreas Gal :gal 2009-02-13 16:47:47 PST
Could js_CallTree maybe reconstruct the global type map on the fly instead of recording the guards and post-process? We can tell in the innermost js_CallTree already that ngslots < than what it should be.
Comment 14 User image David Anderson [:dvander] 2009-02-13 17:05:41 PST
Yup, that sounds good.  I'll hack up a new patch.
Comment 15 User image David Anderson [:dvander] 2009-02-14 09:49:16 PST
Created attachment 362410 [details] [diff] [review]
proposed fix, v2

avoids touching guards
Comment 16 User image Andreas Gal :gal 2009-02-17 12:22:36 PST
Comment on attachment 362410 [details] [diff] [review]
proposed fix, v2

I like this a lot better than v1. Did you check whether this impacts performance?
Comment 17 User image Andreas Gal :gal 2009-02-17 12:53:17 PST
No perf impact. Please push to TM.
Comment 18 User image Andreas Gal :gal 2009-02-17 12:55:21 PST
Comment on attachment 362410 [details] [diff] [review]
proposed fix, v2

Have to verify that this place nicely with LeaveTree.
Comment 19 User image Andreas Gal :gal 2009-02-17 13:16:30 PST
The patch needs some additional code to leave breadcrumbs behind that allow LeaveTree to write back the state early, before js_CallTree unwinds. We can use on-stack data structures for this. If js_CallTree unwinds itself, it reads the data. Otherwise LeaveTree. We should probably check for the unwinding in the innermost guard case only, saving repeated checks at every level.
Comment 20 User image David Anderson [:dvander] 2009-02-19 13:18:28 PST
Created attachment 363184 [details] [diff] [review]
proposed fix, v3

Following comment #19, this patch handles the early LeaveTree case by using a stack of TreeInfos.  I took the opportunity to clean up the prior patch by using the same stack in js_CallTree, when it first begins unwinding.
Comment 21 User image Andreas Gal :gal 2009-02-19 13:26:42 PST
Comment on attachment 363184 [details] [diff] [review]
proposed fix, v3

>diff -r 4cf75fc4d196 js/src/jsbuiltins.cpp
>--- a/js/src/jsbuiltins.cpp    Thu Feb 19 09:33:37 2009 +0100
>+++ b/js/src/jsbuiltins.cpp    Thu Feb 19 16:18:07 2009 -0500
>@@ -191,9 +191,14 @@
> js_CallTree(InterpState* state, Fragment* f)
> {
>     union { NIns *code; GuardRecord* (FASTCALL *func)(InterpState*, Fragment*); } u;
>+    TreeCallInfo tci;
> 
>     u.code = f->code();
>     JS_ASSERT(u.code);

A comment here why we do this would be nice.

>+
>+    tci.ti = (TreeInfo*)f->vmprivate;
>+    tci.next = state->treeCalls;
>+    state->treeCalls = &tci;
> 
>     GuardRecord* rec;
> #if defined(JS_NO_FASTCALL) && defined(NANOJIT_IA32)
>@@ -211,6 +216,11 @@
>             state->lastTreeCallGuard = lr;
>             FrameInfo** rp = (FrameInfo**)state->rp;
>             state->rpAtLastTreeCall = rp + lr->calldepth;
>+            bool bailed = state->lastTreeExitGuard->exitType == STATUS_EXIT &&
>+                          (state->cx->builtinStatus & JSBUILTIN_BAILED);
>+            /* If this isn't a failed builtin, reconstruct the global typemap. */
>+            if (!bailed)
>+                js_ReconstructGlobalTypes(state, state->lastTreeExitGuard);
>         }
>     } else {
>         /* If the tree exits on a regular (non-nested) guard, keep updating lastTreeExitGuard
>@@ -218,6 +228,9 @@
>            non-nested guard we encountered, which is the innermost loop or branch guard. */
>         state->lastTreeExitGuard = lr;
>     }
>+
>+    JS_ASSERT(state->treeCalls == &tci);
>+    state->treeCalls = tci.next;
> 
>     return lr;
> }
>diff -r 4cf75fc4d196 js/src/jstracer.cpp
>--- a/js/src/jstracer.cpp    Thu Feb 19 09:33:37 2009 +0100
>+++ b/js/src/jstracer.cpp    Thu Feb 19 16:18:07 2009 -0500
>@@ -3851,6 +3851,9 @@
>     state.lastTreeExitGuard = NULL;
>     state.lastTreeCallGuard = NULL;
>     state.rpAtLastTreeCall = NULL;
>+    state.globalTypeMap = (uint8*)alloca(ngslots * sizeof(uint8));
>+    state.ngslots = ngslots;
>+    state.treeCalls = NULL;
> 
>     /* Make sure the global object is sane. */
>     JS_ASSERT(!ngslots || (OBJ_SHAPE(JS_GetGlobalForObject(cx, cx->fp->scopeChain)) == ti->globalShape));
>@@ -4110,16 +4113,29 @@
>     uint16* gslots = outermostTree->globalSlots->data();
>     unsigned ngslots = outermostTree->globalSlots->length();
>     JS_ASSERT(ngslots == outermostTree->nGlobalTypes());
>-    unsigned exit_gslots = innermost->numGlobalSlots;
>-    JS_ASSERT(exit_gslots <= ngslots);
>-    uint8* globalTypeMap = getGlobalTypeMap(innermost);
>-    if (exit_gslots < ngslots)
>-        mergeTypeMaps(&globalTypeMap, &exit_gslots, outermostTree->globalTypeMap(), ngslots,
>-                      (uint8*)alloca(sizeof(uint8) * ngslots));
>-    JS_ASSERT(exit_gslots == outermostTree->globalSlots->length());
>+    uint8* globalTypeMap = state.globalTypeMap;
>+    unsigned exit_ngslots;
>+
>+    /* If there are tree calls, there must be a bailed exit. */
>+    JS_ASSERT(!state.treeCalls || innermost->exitType == DEEP_BAIL_EXIT);
>+
>+    /* Are there enough globals? This is the ideal fast path. */
>+    if (innermost->numGlobalSlots == ngslots) {
>+        globalTypeMap = getGlobalTypeMap(innermost);
>+        exit_ngslots = ngslots;
>+    /* For deep bail exits, or exits that weren't nested, reconstruct global types now. */
>+    } else if (innermost->exitType == DEEP_BAIL_EXIT || state.lastTreeCallGuard == NULL) {
>+        js_ReconstructGlobalTypes(&state, innermost);
>+        exit_ngslots = state.exit_ngslots;
>+    } else {
>+        /* Typemap was reconstructed in js_CallTree */
>+        exit_ngslots = state.exit_ngslots;
>+    }
>+    JS_ASSERT(exit_ngslots == outermostTree->nGlobalTypes());
>+    JS_ASSERT(exit_ngslots == ngslots);
> 
>     /* write back interned globals */
>-    FlushNativeGlobalFrame(cx, exit_gslots, gslots, globalTypeMap, state.global);
>+    FlushNativeGlobalFrame(cx, exit_ngslots, gslots, globalTypeMap, state.global);
>     JS_ASSERT(*(uint64*)&state.global[STOBJ_NSLOTS(state.globalObj)] == 0xdeadbeefdeadbeefLL);
> 
>     /* write back native stack frame */
>@@ -4146,6 +4162,48 @@
> #endif
> 
>     state.innermost = innermost;
>+}
>+
>+static void
>+CopyMissingGlobals(uint8* destTypeMap,
>+                   unsigned& nDestTypes,
>+                   uint8* srcTypeMap,
>+                   unsigned nSrcTypes)
>+{
>+    if (nSrcTypes > nDestTypes) {
>+        memcpy(destTypeMap + nDestTypes, srcTypeMap + nDestTypes, nSrcTypes - nDestTypes);
>+        nDestTypes = nSrcTypes;
>+    }
>+}
>+
>+void
>+js_ReconstructGlobalTypes(InterpState* state, VMSideExit* innermost)
>+{
>+    TreeCallInfo* tci;
>+    TreeInfo* ti = (TreeInfo*)innermost->from->root->vmprivate;
>+    uint8* typeMap = state->globalTypeMap;
>+
>+    /* Work from the innermost guard all the way to the outermost tree. */
>+    state->exit_ngslots = 0;
>+    CopyMissingGlobals(typeMap, state->exit_ngslots, getGlobalTypeMap(innermost),
>+                       innermost->numGlobalSlots);
>+    if (state->exit_ngslots == state->ngslots)
>+        return;
>+    CopyMissingGlobals(typeMap, state->exit_ngslots, ti->globalTypeMap(), ti->nGlobalTypes());
>+    if (state->exit_ngslots == state->ngslots)
>+        return;
>+    /* Process the inner nested guards */
>+    tci = state->treeCalls;
>+    while (tci != NULL) {
>+        ti = tci->ti;
>+        CopyMissingGlobals(typeMap, state->exit_ngslots, ti->globalTypeMap(), ti->nGlobalTypes());
>+        if (state->exit_ngslots == state->ngslots)
>+            return;
>+        tci = tci->next;
>+    }
>+    /* Process the outermost tree */
>+    ti = state->outermostTree;
>+    CopyMissingGlobals(typeMap, state->exit_ngslots, ti->globalTypeMap(), ti->nGlobalTypes());
> }
> 
> JS_REQUIRES_STACK bool
>diff -r 4cf75fc4d196 js/src/jstracer.h
>--- a/js/src/jstracer.h    Thu Feb 19 09:33:37 2009 +0100
>+++ b/js/src/jstracer.h    Thu Feb 19 16:18:07 2009 -0500
>@@ -313,6 +313,11 @@
>     }
> };
> 
>+struct TreeCallInfo {
>+    TreeInfo*       ti;
>+    TreeCallInfo*   next;
>+};
>+
> #if defined(JS_JIT_SPEW) && (defined(NANOJIT_IA32) || (defined(NANOJIT_AMD64) && defined(__GNUC__)))
> # define EXECUTE_TREE_TIMER
> #endif
>@@ -337,6 +342,10 @@
>     VMSideExit** innermostNestedGuardp;
>     void*          stackMark;
>     VMSideExit*    innermost;
>+    unsigned       ngslots;
>+    uint8*         globalTypeMap;
>+    unsigned       exit_ngslots;
>+    TreeCallInfo*  treeCalls;
> #ifdef EXECUTE_TREE_TIMER
>     uint64         startTime;
> #endif
>@@ -622,6 +631,9 @@
> extern JSObject *
> js_GetBuiltinFunction(JSContext *cx, uintN index);
> 
>+extern void
>+js_ReconstructGlobalTypes(InterpState* state, VMSideExit* innermost);
>+
> #else  /* !JS_TRACER */
> 
> #define TRACE_0(x)              ((void)0)
Comment 22 User image David Anderson [:dvander] 2009-02-21 12:54:34 PST
Created attachment 363499 [details] [diff] [review]
proposed fix, v4

Once again this is basically a totally different patch.  As discussed on IRC, this still wasn't enough.  math-partial-sums exposes a case where two trees linked together can both specialize to new globals at different points in time, creating a typemap disparity.  

This patch recursively updates all "friend" trees (trees linked together via tree calls or multitree stitching) with new global types.  

Luckily, this also removes the need to backtrack up the js_CallTree stack, since now the innermost guard and innermost tree, when combined, are guaranteed to contain a complete typemap.
Comment 23 User image David Anderson [:dvander] 2009-02-21 13:01:48 PST
Comment on attachment 363499 [details] [diff] [review]
proposed fix, v4

Whoops, turns out that dependent/linkedTrees doesn't learn about fragments that get trashed.  Will have to address that.
Comment 24 User image David Anderson [:dvander] 2009-02-24 12:18:15 PST
Created attachment 363938 [details] [diff] [review]
v5

This should be enough to fix the issue in the prior comment.  There was already a bidirectional relationship because of dependentTrees.
Comment 25 User image Andreas Gal :gal 2009-02-24 16:13:25 PST
Comment on attachment 363938 [details] [diff] [review]
v5

>diff -r 42acafcdae02 js/src/jstracer.cpp
>--- a/js/src/jstracer.cpp	Mon Feb 23 17:31:02 2009 -0600
>+++ b/js/src/jstracer.cpp	Tue Feb 24 15:13:17 2009 -0500
>@@ -1178,6 +1178,29 @@
>     *plength = clength;
> }
> 
>+/* Specializes a tree to any missing globals, including any dependent trees. */
>+static void
>+specializeTreesToMissingGlobals(JSContext* cx, TreeInfo* root)
>+{
>+    TreeInfo* ti = root;
>+
>+    ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
>+    JS_ASSERT(ti->globalSlots->length() == ti->typeMap.length() - ti->nStackTypes);
>+   
>+    for (unsigned i = 0; i < root->dependentTrees.length(); i++) {
>+        ti = (TreeInfo*)root->dependentTrees.data()[i]->vmprivate;
>+        /* ti can be NULL if we hit the recording tree in emitTreeCall; this is harmless. */

One comment about ti above both loops?

>+        if (ti && ti->nGlobalTypes() < ti->globalSlots->length())
>+            specializeTreesToMissingGlobals(cx, ti);
>+    }
>+    for (unsigned i = 0; i < root->linkedTrees.length(); i++) {
>+        ti = (TreeInfo*)root->linkedTrees.data()[i]->vmprivate;
>+        /* ti can be NULL if we hit the recording tree in emitTreeCall; this is harmless. */
>+        if (ti && ti->nGlobalTypes() < ti->globalSlots->length())
>+            specializeTreesToMissingGlobals(cx, ti);
>+    }
>+}
>+
> static void
> js_TrashTree(JSContext* cx, Fragment* f);
> 
>@@ -1232,11 +1255,8 @@
>     globalObj_ins = addName(lir->insLoad(LIR_ldp, lirbuf->state, offsetof(InterpState, globalObj)), "globalObj");
> 
>     /* If we came from exit, we might not have enough global types. */
>-    if (ti->globalSlots->length() > ti->nGlobalTypes()) {
>-        ti->typeMap.captureMissingGlobalTypes(cx,
>-                                              *(ti->globalSlots),
>-                                              ti->nStackTypes);
>-    }
>+    if (ti->globalSlots->length() > ti->nGlobalTypes())
>+        specializeTreesToMissingGlobals(cx, ti);
> 
>     /* read into registers all values on the stack and all globals we know so far */
>     import(treeInfo, lirbuf->sp, stackSlots, ngslots, callDepth, typeMap);
>@@ -1639,6 +1659,7 @@
> {
>     uint8* mp_base = mp;
>     FORALL_GLOBAL_SLOTS(cx, ngslots, gslots,
>+        debug_only_v(printf("%s%u=", vpname, vpnum);)
>         NativeToValue(cx, *vp, *mp, np + gslots[n]);
>         ++mp;
>     );
>@@ -2507,6 +2528,7 @@
>     frago->assm()->patch(exit);
> 
>     stableTree->dependentTrees.addUnique(exit->from->root);
>+    ((TreeInfo*)exit->from->root->vmprivate)->linkedTrees.addUnique(stableFrag);
> 
>     return true;
> }
>@@ -2588,6 +2610,7 @@
>             debug_only_v(printf("Joining type-unstable trace to target fragment %p.\n", (void*)peer);)
>             stable = true;
>             ((TreeInfo*)peer->vmprivate)->dependentTrees.addUnique(fragment->root);
>+            treeInfo->linkedTrees.addUnique(peer);
>         }
> 
>         compile(tm);
>@@ -2601,6 +2624,10 @@
>         return false;
> 
>     joinEdgesToEntry(fragmento, peer_root);
>+
>+    debug_only_v(printf("updating specializations on dependent and linked trees\n"))
>+    if (fragment->vmprivate != NULL)
>+        specializeTreesToMissingGlobals(cx, (TreeInfo*)fragment->vmprivate);
> 
>     debug_only_v(printf("recording completed at %s:%u@%u via closeLoop\n",
>                         cx->fp->script->filename,
>@@ -2707,7 +2734,15 @@
>     if (tm->fragmento->assm()->error() != nanojit::None)
>         return;
> 
>+    /* Note: this must always be done, in case we added new globals on trace and haven't yet 
>+       propagated those to linked and dependent trees. */
>     joinEdgesToEntry(tm->fragmento, getLoop(tm, fragment->root->ip, treeInfo->globalShape));
>+
>+    /* Note: this must always be done, in case we added new globals on trace and haven't yet 
>+       propagated those to linked and dependent trees. */

Comment twice?

>+    debug_only_v(printf("updating specializations on dependent and linked trees\n"))
>+    if (fragment->vmprivate != NULL)
>+        specializeTreesToMissingGlobals(cx, (TreeInfo*)fragment->vmprivate);

Why vmprivate != NULL? Always use fragment->root == fragment to find root fragments. Why would vmprivate be NULL here?

> 
>     debug_only_v(printf("recording completed at %s:%u@%u via endLoop\n",
>                         cx->fp->script->filename,
>@@ -2776,6 +2811,7 @@
>     guard(true, lir->ins2(LIR_eq, ret, INS_CONSTPTR(exit)), NESTED_EXIT);
>     /* Register us as a dependent tree of the inner tree. */
>     ((TreeInfo*)inner->vmprivate)->dependentTrees.addUnique(fragment->root);
>+    treeInfo->linkedTrees.addUnique(inner);
> }
> 
> /* Add a if/if-else control-flow merge point to the list of known merge points. */
>@@ -3382,9 +3418,10 @@
>             /* Capture missing globals on both trees and link the fragments together. */
>             if (from != f) {
>                 ti->dependentTrees.addUnique(from);
>-                ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
>-            }
>-            from_ti->typeMap.captureMissingGlobalTypes(cx, *from_ti->globalSlots, from_ti->nStackTypes);
>+                from_ti->linkedTrees.addUnique(f);
>+            }
>+            if (ti->nGlobalTypes() < ti->globalSlots->length())
>+                specializeTreesToMissingGlobals(cx, ti);
>             exit->target = f;
>             tm->fragmento->assm()->patch(exit);
>             /* Now erase this exit from the unstable exit list. */
>@@ -3712,7 +3749,7 @@
>         debug_only_v(printf("checking nested types %p: ", (void*)f);)
> 
>         if (ngslots > ti->nGlobalTypes())
>-            ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
>+            specializeTreesToMissingGlobals(cx, ti);
> 
>         uint8* m = ti->typeMap.data();
> 
>@@ -3767,7 +3804,7 @@
>     JS_ASSERT(ti->nStackTypes == js_NativeStackSlots(cx, 0));
> 
>     if (ngslots > ti->nGlobalTypes())
>-        ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
>+        specializeTreesToMissingGlobals(cx, ti);
> 
>     uint8* m = ti->typeMap.data();
> 
>@@ -4099,16 +4136,28 @@
>     uint16* gslots = outermostTree->globalSlots->data();
>     unsigned ngslots = outermostTree->globalSlots->length();
>     JS_ASSERT(ngslots == outermostTree->nGlobalTypes());
>-    unsigned exit_gslots = innermost->numGlobalSlots;
>-    JS_ASSERT(exit_gslots <= ngslots);
>-    uint8* globalTypeMap = getGlobalTypeMap(innermost);
>-    if (exit_gslots < ngslots)
>-        mergeTypeMaps(&globalTypeMap, &exit_gslots, outermostTree->globalTypeMap(), ngslots,
>-                      (uint8*)alloca(sizeof(uint8) * ngslots));
>-    JS_ASSERT(exit_gslots == outermostTree->globalSlots->length());
>+    uint8* globalTypeMap;
>+
>+    /* Are there enough globals? This is the ideal fast path. */
>+    if (innermost->numGlobalSlots == ngslots) {
>+        globalTypeMap = getGlobalTypeMap(innermost);
>+    /* Otherwise, merge the typemap of the innermost entry and exit together.  This should always
>+       work because it is invalid for nested trees or linked trees to have incompatible types.
>+       Thus, whenever a new global type is lazily added into a tree, all dependent and linked
>+       trees are immediately specialized (see bug 476653). */

Indentation. And move comment into the else block or above the if/else.

>+    } else {
>+        TreeInfo* ti = (TreeInfo*)innermost->from->root->vmprivate;
>+        JS_ASSERT(ti->nGlobalTypes() == ngslots);
>+        JS_ASSERT(ti->nGlobalTypes() > innermost->numGlobalSlots);
>+        globalTypeMap = (uint8*)alloca(ngslots * sizeof(uint8));
>+        memcpy(globalTypeMap, getGlobalTypeMap(innermost), innermost->numGlobalSlots);
>+        memcpy(globalTypeMap + innermost->numGlobalSlots,
>+               ti->globalTypeMap() + innermost->numGlobalSlots,
>+               ti->nGlobalTypes() - innermost->numGlobalSlots);
>+    }
> 
>     /* write back interned globals */
>-    FlushNativeGlobalFrame(cx, exit_gslots, gslots, globalTypeMap, state.global);
>+    FlushNativeGlobalFrame(cx, ngslots, gslots, globalTypeMap, state.global);
>     JS_ASSERT(*(uint64*)&state.global[STOBJ_NSLOTS(state.globalObj)] == 0xdeadbeefdeadbeefLL);
> 
>     /* write back native stack frame */
>diff -r 42acafcdae02 js/src/jstracer.h
>--- a/js/src/jstracer.h	Mon Feb 23 17:31:02 2009 -0600
>+++ b/js/src/jstracer.h	Tue Feb 24 15:13:17 2009 -0500
>@@ -308,7 +308,10 @@
>     unsigned                nStackTypes;
>     uint32                  globalShape;
>     SlotList*               globalSlots;
>+    /* Dependent trees must be trashed if this tree dies, and updated on missing global types */
>     Queue<nanojit::Fragment*> dependentTrees;
>+    /* Linked trees must be updated on missing global types, but are not dependent */
>+    Queue<nanojit::Fragment*> linkedTrees;
>     unsigned                branchCount;
>     Queue<VMSideExit*>      sideExits;
>     UnstableExit*           unstableExits;

r+ with formating nits as appropriate, plus an explanation of why you check ->vmprivate there.
Comment 26 User image David Anderson [:dvander] 2009-02-24 19:15:12 PST
Created attachment 364021 [details] [diff] [review]
v6

Graydon pointed me to two intensive scripts that broke this patch.  I used fragment instead of fragment->root in a few places.  In addition, it's necessary to walk the dependency graph when updating in lazilyImportGlobalSlots().
Comment 27 User image Andreas Gal :gal 2009-02-24 19:39:41 PST
Comment on attachment 364021 [details] [diff] [review]
v6

>diff -r 393a83c4c7a2 js/src/jstracer.cpp
>--- a/js/src/jstracer.cpp	Tue Feb 24 15:26:59 2009 -0500
>+++ b/js/src/jstracer.cpp	Tue Feb 24 22:09:33 2009 -0500
>@@ -1178,6 +1178,29 @@
>     *plength = clength;
> }
> 
>+/* Specializes a tree to any missing globals, including any dependent trees. */
>+static void
>+specializeTreesToMissingGlobals(JSContext* cx, TreeInfo* root)
>+{
>+    TreeInfo* ti = root;
>+
>+    ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
>+    JS_ASSERT(ti->globalSlots->length() == ti->typeMap.length() - ti->nStackTypes);
>+   
>+    for (unsigned i = 0; i < root->dependentTrees.length(); i++) {
>+        ti = (TreeInfo*)root->dependentTrees.data()[i]->vmprivate;
>+        /* ti can be NULL if we hit the recording tree in emitTreeCall; this is harmless. */

Why say ...

>+        if (ti && ti->nGlobalTypes() < ti->globalSlots->length())
>+            specializeTreesToMissingGlobals(cx, ti);
>+    }
>+    for (unsigned i = 0; i < root->linkedTrees.length(); i++) {
>+        ti = (TreeInfo*)root->linkedTrees.data()[i]->vmprivate;
>+        /* ti can be NULL if we hit the recording tree in emitTreeCall; this is harmless. */

... it twice? :)

>+        if (ti && ti->nGlobalTypes() < ti->globalSlots->length())
>+            specializeTreesToMissingGlobals(cx, ti);



>+    }
>+}
>+
> static void
> js_TrashTree(JSContext* cx, Fragment* f);
> 
>@@ -1232,11 +1255,8 @@
>     globalObj_ins = addName(lir->insLoad(LIR_ldp, lirbuf->state, offsetof(InterpState, globalObj)), "globalObj");
> 
>     /* If we came from exit, we might not have enough global types. */
>-    if (ti->globalSlots->length() > ti->nGlobalTypes()) {
>-        ti->typeMap.captureMissingGlobalTypes(cx,
>-                                              *(ti->globalSlots),
>-                                              ti->nStackTypes);
>-    }
>+    if (ti->globalSlots->length() > ti->nGlobalTypes())
>+        specializeTreesToMissingGlobals(cx, ti);
> 
>     /* read into registers all values on the stack and all globals we know so far */
>     import(treeInfo, lirbuf->sp, stackSlots, ngslots, callDepth, typeMap);
>@@ -1639,6 +1659,7 @@
> {
>     uint8* mp_base = mp;
>     FORALL_GLOBAL_SLOTS(cx, ngslots, gslots,
>+        debug_only_v(printf("%s%u=", vpname, vpnum);)
>         NativeToValue(cx, *vp, *mp, np + gslots[n]);
>         ++mp;
>     );
>@@ -1819,12 +1840,14 @@
>         return true; /* we already have it */
>     unsigned index = treeInfo->globalSlots->length();
>     /* Add the slot to the list of interned global slots. */
>+    JS_ASSERT(treeInfo->nGlobalTypes() == treeInfo->globalSlots->length());
>     treeInfo->globalSlots->add(slot);
>     uint8 type = getCoercedType(*vp);
>     if ((type == JSVAL_INT) && oracle.isGlobalSlotUndemotable(cx, slot))
>         type = JSVAL_DOUBLE;
>     treeInfo->typeMap.add(type);
>     import(gp_ins, slot*sizeof(double), vp, type, "global", index, NULL);
>+    specializeTreesToMissingGlobals(cx, treeInfo);
>     return true;
> }
> 
>@@ -2507,6 +2530,7 @@
>     frago->assm()->patch(exit);
> 
>     stableTree->dependentTrees.addUnique(exit->from->root);
>+    ((TreeInfo*)exit->from->root->vmprivate)->linkedTrees.addUnique(stableFrag);
> 
>     return true;
> }
>@@ -2588,6 +2612,7 @@
>             debug_only_v(printf("Joining type-unstable trace to target fragment %p.\n", (void*)peer);)
>             stable = true;
>             ((TreeInfo*)peer->vmprivate)->dependentTrees.addUnique(fragment->root);
>+            treeInfo->linkedTrees.addUnique(peer);
>         }
> 
>         compile(tm);
>@@ -2601,6 +2626,10 @@
>         return false;
> 
>     joinEdgesToEntry(fragmento, peer_root);
>+
>+    debug_only_v(printf("updating specializations on dependent and linked trees\n"))
>+    if (fragment->root->vmprivate)
>+        specializeTreesToMissingGlobals(cx, (TreeInfo*)fragment->root->vmprivate);
> 
>     debug_only_v(printf("recording completed at %s:%u@%u via closeLoop\n",
>                         cx->fp->script->filename,
>@@ -2707,7 +2736,15 @@
>     if (tm->fragmento->assm()->error() != nanojit::None)
>         return;
> 
>+    /* Note: this must always be done, in case we added new globals on trace and haven't yet 
>+       propagated those to linked and dependent trees. */

Really, we don't want to 

>     joinEdgesToEntry(tm->fragmento, getLoop(tm, fragment->root->ip, treeInfo->globalShape));
>+
>+    /* Note: this must always be done, in case we added new globals on trace and haven't yet 
>+       propagated those to linked and dependent trees. */

say this twice either :)

>+    debug_only_v(printf("updating specializations on dependent and linked trees\n"))
>+    if (fragment->root->vmprivate)
>+        specializeTreesToMissingGlobals(cx, (TreeInfo*)fragment->root->vmprivate);
> 
>     debug_only_v(printf("recording completed at %s:%u@%u via endLoop\n",
>                         cx->fp->script->filename,
>@@ -2776,6 +2813,7 @@
>     guard(true, lir->ins2(LIR_eq, ret, INS_CONSTPTR(exit)), NESTED_EXIT);
>     /* Register us as a dependent tree of the inner tree. */
>     ((TreeInfo*)inner->vmprivate)->dependentTrees.addUnique(fragment->root);
>+    treeInfo->linkedTrees.addUnique(inner);

Maybe add a helper function for this? We always do this together.

> }
> 
> /* Add a if/if-else control-flow merge point to the list of known merge points. */
>@@ -3382,9 +3420,10 @@
>             /* Capture missing globals on both trees and link the fragments together. */
>             if (from != f) {
>                 ti->dependentTrees.addUnique(from);
>-                ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
>-            }
>-            from_ti->typeMap.captureMissingGlobalTypes(cx, *from_ti->globalSlots, from_ti->nStackTypes);
>+                from_ti->linkedTrees.addUnique(f);
>+            }
>+            if (ti->nGlobalTypes() < ti->globalSlots->length())
>+                specializeTreesToMissingGlobals(cx, ti);
>             exit->target = f;
>             tm->fragmento->assm()->patch(exit);
>             /* Now erase this exit from the unstable exit list. */
>@@ -3713,7 +3752,7 @@
>         debug_only_v(printf("checking nested types %p: ", (void*)f);)
> 
>         if (ngslots > ti->nGlobalTypes())
>-            ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
>+            specializeTreesToMissingGlobals(cx, ti);
> 
>         uint8* m = ti->typeMap.data();
> 
>@@ -3768,7 +3807,7 @@
>     JS_ASSERT(ti->nStackTypes == js_NativeStackSlots(cx, 0));
> 
>     if (ngslots > ti->nGlobalTypes())
>-        ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
>+        specializeTreesToMissingGlobals(cx, ti);
> 
>     uint8* m = ti->typeMap.data();
> 
>@@ -4100,16 +4139,28 @@
>     uint16* gslots = outermostTree->globalSlots->data();
>     unsigned ngslots = outermostTree->globalSlots->length();
>     JS_ASSERT(ngslots == outermostTree->nGlobalTypes());
>-    unsigned exit_gslots = innermost->numGlobalSlots;
>-    JS_ASSERT(exit_gslots <= ngslots);
>-    uint8* globalTypeMap = getGlobalTypeMap(innermost);
>-    if (exit_gslots < ngslots)
>-        mergeTypeMaps(&globalTypeMap, &exit_gslots, outermostTree->globalTypeMap(), ngslots,
>-                      (uint8*)alloca(sizeof(uint8) * ngslots));
>-    JS_ASSERT(exit_gslots == outermostTree->globalSlots->length());
>+    uint8* globalTypeMap;
>+
>+    /* Are there enough globals? This is the ideal fast path. */
>+    if (innermost->numGlobalSlots == ngslots) {
>+        globalTypeMap = getGlobalTypeMap(innermost);
>+    /* Otherwise, merge the typemap of the innermost entry and exit together.  This should always
>+       work because it is invalid for nested trees or linked trees to have incompatible types.
>+       Thus, whenever a new global type is lazily added into a tree, all dependent and linked
>+       trees are immediately specialized (see bug 476653). */
>+    } else {
>+        TreeInfo* ti = (TreeInfo*)innermost->from->root->vmprivate;
>+        JS_ASSERT(ti->nGlobalTypes() == ngslots);
>+        JS_ASSERT(ti->nGlobalTypes() > innermost->numGlobalSlots);
>+        globalTypeMap = (uint8*)alloca(ngslots * sizeof(uint8));
>+        memcpy(globalTypeMap, getGlobalTypeMap(innermost), innermost->numGlobalSlots);
>+        memcpy(globalTypeMap + innermost->numGlobalSlots,
>+               ti->globalTypeMap() + innermost->numGlobalSlots,
>+               ti->nGlobalTypes() - innermost->numGlobalSlots);
>+    }
> 
>     /* write back interned globals */
>-    FlushNativeGlobalFrame(cx, exit_gslots, gslots, globalTypeMap, state.global);
>+    FlushNativeGlobalFrame(cx, ngslots, gslots, globalTypeMap, state.global);
>     JS_ASSERT(*(uint64*)&state.global[STOBJ_NSLOTS(state.globalObj)] == 0xdeadbeefdeadbeefLL);
> 
>     /* write back native stack frame */
>diff -r 393a83c4c7a2 js/src/jstracer.h
>--- a/js/src/jstracer.h	Tue Feb 24 15:26:59 2009 -0500
>+++ b/js/src/jstracer.h	Tue Feb 24 22:09:33 2009 -0500
>@@ -308,7 +308,10 @@
>     unsigned                nStackTypes;
>     uint32                  globalShape;
>     SlotList*               globalSlots;
>+    /* Dependent trees must be trashed if this tree dies, and updated on missing global types */
>     Queue<nanojit::Fragment*> dependentTrees;
>+    /* Linked trees must be updated on missing global types, but are not dependent */
>+    Queue<nanojit::Fragment*> linkedTrees;
>     unsigned                branchCount;
>     Queue<VMSideExit*>      sideExits;
>     UnstableExit*           unstableExits;
Comment 28 User image David Anderson [:dvander] 2009-02-24 19:56:23 PST
Pushed as changeset: http://hg.mozilla.org/tracemonkey/rev/0d0489b3e4b7

Addressed nits except for moving the tree linking into a helper - will save that for a follow-up patch.  Each of those little snippets is a little different (in some cases vmprivate is still NULL).  If this bakes on the tree okay I'll spend more time prettying that up.
Comment 31 User image Bob Clary [:bc:] 2009-03-03 11:13:59 PST
Created attachment 365251 [details]
js1_8/extensions/regress-476653.js

note the jit(true) call was necessary to reproduce the bug. simply calling the shell with -j wasn't sufficient.
Comment 32 User image Bob Clary [:bc:] 2009-03-12 01:38:38 PDT
verified 1.9.1, 1.9.2
Comment 33 User image Bob Clary [:bc:] 2010-02-22 11:26:17 PST
test checked into 1.9.0, 1.9.1, 1.9.2, tracemonkey. 1.9.3 will get picked up in the next merge.

Note You need to log in before you can comment on or make changes to this bug.