476653 - TM: Crash [@ QuoteString]

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: 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

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Thanks jorendorff for helping me with this on IRC.

Comment 2

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: verbose output

Comment 3

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Related to bug 468324?

Comment 4

[David Anderson [:dvander] - inactive, e-mail if emergency]

(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

[David Anderson [:dvander] - inactive, e-mail if emergency]

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

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: 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

[Andreas Gal :gal]

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

[David Anderson [:dvander] - inactive, e-mail if emergency]

There isn't guaranteed to be anything on the call stack.

Comment 9

[Andreas Gal :gal]

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

[David Anderson [:dvander] - inactive, e-mail if emergency]

What happens if realloc() fails?  That's what I was worried about - it's not infallible, but the solution has to be.

Comment 11

[David Anderson [:dvander] - inactive, e-mail if emergency]

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

[Andreas Gal :gal]

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

[Andreas Gal :gal]

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

[David Anderson [:dvander] - inactive, e-mail if emergency]

Yup, that sounds good.  I'll hack up a new patch.

Comment 15

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: proposed fix, v2

avoids touching guards

Comment 16

[Andreas Gal :gal]

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

[Andreas Gal :gal]

No perf impact. Please push to TM.

Comment 18

[Andreas Gal :gal]

Comment on attachment 362410 [details] [diff] [review]
proposed fix, v2

Have to verify that this place nicely with LeaveTree.

Comment 19

[Andreas Gal :gal]

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

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: 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

[Andreas Gal :gal]

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

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: 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

[David Anderson [:dvander] - inactive, e-mail if emergency]

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

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: v5

This should be enough to fix the issue in the prior comment.  There was already a bidirectional relationship because of dependentTrees.

Comment 25

[Andreas Gal :gal]

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

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: 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

[Andreas Gal :gal]

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

[David Anderson [:dvander] - inactive, e-mail if emergency]

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 29

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/0d0489b3e4b7

Comment 30

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/c146502dc7cb

Comment 31

[Bob Clary [:bc] (inactive)]

Attachment: 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

[Bob Clary [:bc] (inactive)]

verified 1.9.1, 1.9.2

Comment 33

[Bob Clary [:bc] (inactive)]

test checked into 1.9.0, 1.9.1, 1.9.2, tracemonkey. 1.9.3 will get picked up in the next merge.