TM: Crash [@ QuoteString]

VERIFIED FIXED

Status

()

Core
JavaScript Engine
P2
critical
VERIFIED FIXED
8 years ago
6 years ago

People

(Reporter: gkw, Assigned: dvander)

Tracking

(Blocks: 1 bug, {crash, testcase, verified1.9.1})

Trunk
x86
Mac OS X
crash, testcase, verified1.9.1
Points:
---
Dependency tree / graph
Bug Flags:
blocking1.9.1 +
wanted1.9.0.x -
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [sg:investigate], crash signature)

Attachments

(4 attachments, 5 obsolete attachments)

(Reporter)

Description

8 years ago
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.
Flags: blocking1.9.1?
(Reporter)

Comment 1

8 years ago
Thanks jorendorff for helping me with this on IRC.
Whiteboard: [sg:investigate]
(Reporter)

Comment 2

8 years ago
Created attachment 360312 [details]
verbose output
(Reporter)

Comment 3

8 years ago
Related to bug 468324?
(Assignee)

Comment 4

8 years ago
(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
}

Updated

8 years ago
Flags: blocking1.9.1? → blocking1.9.1+
Priority: -- → P2

Updated

8 years ago
Assignee: general → dmandelin

Updated

8 years ago
Assignee: dmandelin → danderson
(Assignee)

Comment 5

8 years ago
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.
(Assignee)

Comment 6

8 years ago
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.
Attachment #361929 - Flags: review?(gal)

Updated

8 years ago
Blocks: 478481

Comment 7

8 years ago
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?
No longer blocks: 478481
(Assignee)

Comment 8

8 years ago
There isn't guaranteed to be anything on the call stack.
Blocks: 478481

Comment 9

8 years ago
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.
(Assignee)

Comment 10

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

Comment 11

8 years ago
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

8 years ago
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

8 years ago
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.
(Assignee)

Comment 14

8 years ago
Yup, that sounds good.  I'll hack up a new patch.
(Assignee)

Comment 15

8 years ago
Created attachment 362410 [details] [diff] [review]
proposed fix, v2

avoids touching guards
Attachment #361929 - Attachment is obsolete: true
Attachment #362410 - Flags: review?(gal)
Attachment #361929 - Flags: review?(gal)

Updated

8 years ago
Attachment #362410 - Flags: review?(gal) → review+

Comment 16

8 years ago
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

8 years ago
No perf impact. Please push to TM.

Comment 18

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

Have to verify that this place nicely with LeaveTree.
Attachment #362410 - Flags: review+

Comment 19

8 years ago
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.
(Assignee)

Comment 20

8 years ago
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.
Attachment #362410 - Attachment is obsolete: true
Attachment #363184 - Flags: review?(gal)

Updated

8 years ago
Attachment #363184 - Flags: review?(gal) → review+

Comment 21

8 years ago
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)
(Assignee)

Comment 22

8 years ago
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.
Attachment #363184 - Attachment is obsolete: true
Attachment #363499 - Flags: review?(gal)
(Assignee)

Comment 23

8 years ago
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.
Attachment #363499 - Flags: review?(gal) → review-

Updated

8 years ago
Blocks: 463478

Updated

8 years ago
Blocks: 463487
(Assignee)

Comment 24

8 years ago
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.
Attachment #363499 - Attachment is obsolete: true
Attachment #363938 - Flags: review?(gal)

Comment 25

8 years ago
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.
Attachment #363938 - Flags: review?(gal) → review+
(Assignee)

Comment 26

8 years ago
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().
Attachment #363938 - Attachment is obsolete: true
Attachment #364021 - Flags: review?(gal)

Comment 27

8 years ago
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;
Attachment #364021 - Flags: review?(gal) → review+
(Assignee)

Comment 28

8 years ago
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

8 years ago
http://hg.mozilla.org/mozilla-central/rev/0d0489b3e4b7
Status: NEW → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED

Comment 30

8 years ago
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/c146502dc7cb
Keywords: fixed1.9.1

Comment 31

8 years ago
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.

Updated

8 years ago
Flags: in-testsuite+

Comment 32

8 years ago
verified 1.9.1, 1.9.2
Status: RESOLVED → VERIFIED
Keywords: fixed1.9.1 → verified1.9.1
(Reporter)

Updated

8 years ago
Blocks: 477877
(Reporter)

Updated

8 years ago
Blocks: 476192
Group: core-security
Flags: wanted1.9.0.x-

Comment 33

7 years ago
test checked into 1.9.0, 1.9.1, 1.9.2, tracemonkey. 1.9.3 will get picked up in the next merge.
Crash Signature: [@ QuoteString]
You need to log in before you can comment on or make changes to this bug.