Last Comment Bug 460336 - TM: Traceable native Array_p_join can reenter interpreter
: TM: Traceable native Array_p_join can reenter interpreter
Status: RESOLVED WORKSFORME
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Other Branch
: All All
: -- normal (vote)
: ---
Assigned To: Jason Orendorff [:jorendorff]
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on: deepbail
Blocks:
  Show dependency treegraph
 
Reported: 2008-10-16 14:18 PDT by Jason Orendorff [:jorendorff]
Modified: 2009-02-03 16:43 PST (History)
8 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
v1 (4.09 KB, patch)
2008-10-27 17:51 PDT, Jason Orendorff [:jorendorff]
brendan: review-
Details | Diff | Splinter Review

Description Jason Orendorff [:jorendorff] 2008-10-16 14:18:38 PDT
The script below reenters the interpreter on trace. It calls bad.toString from Array.prototype.join.

// if you change this to HOTLOOP - 1, the second loop deep-aborts
var N = tracemonkey.HOTLOOP;

function test_join() {
  var bad = {
    toString: function() {
      print("bad to call this on trace!");
      return "y";
    }
  };

  var arrays = []
  for (var i = 0; i < N; i++)
    arrays.push(["x", "y", "z", "z", "y"]);
  arrays.push(["x", "y", "z", "z", bad]);

  var s;
  for (var i = 0; i < arrays.length; i++)
    s = arrays[i].join('');
  return s;
}

print(test_join());
Comment 1 Andreas Gal :gal 2008-10-16 16:28:55 PDT
I guess the proper way to solve this would be to implement join in script, then we can trace the loop as long we don't have to invoke toString (which right now would just side-exit and bail to the interpreter).
Comment 2 Brendan Eich [:brendan] 2008-10-16 16:33:43 PDT
(In reply to comment #1)
> I guess the proper way to solve this would be to implement join in script, then
> we can trace the loop as long we don't have to invoke toString (which right now
> would just side-exit and bail to the interpreter).

Someone please try this and benchmark a bit -- we could actually win on common  join cases and gain the memory-safe self-hosted-implementation benefit.

/be
Comment 3 Brendan Eich [:brendan] 2008-10-16 16:39:09 PDT
(In reply to comment #0)
>   for (var i = 0; i < N; i++)
>     arrays.push(["x", "y", "z", "z", "y"]);
>   arrays.push(["x", "y", "z", "z", bad]);
> 
>   var s;
>   for (var i = 0; i < arrays.length; i++)
>     s = arrays[i].join('');

Is there a shape guard bug here?

When we record with N = HOTLOOP, we see a dense array ["x", "y", "z", "z", "y"] as the receiver of the join method call. The property cache probe looks past the direct object (the dense array) and so does not guard on its non-existent (scope) shape. But we fail to guard on this fact. If we guarded that on-trace receivers had to be dense arrays, then we'd MISMATCH_EXIT back to the interpreter and call toString just fine.

I think this report should be about the above missing guard bug. I will take it but I invite others to steal it (ping me to make sure I don't have a queued patch to hand off). Thanks,

/be
Comment 4 Brendan Eich [:brendan] 2008-10-17 07:36:13 PDT
Oops, it's not the dense arrays (all of the arrays are dense), but the elements that matter here: going from string (primitive type) to object on trace when the recorder saw string should trigger a guard.

/be
Comment 5 Jason Orendorff [:jorendorff] 2008-10-17 08:16:49 PDT
(In reply to comment #1)
> I guess the proper way to solve this would be to implement join in script, then
> we can trace the loop as long we don't have to invoke toString (which right now
> would just side-exit and bail to the interpreter).

This seems to make string-fasta.js 52% slower, more details in a bit.
Comment 6 Jason Orendorff [:jorendorff] 2008-10-17 08:51:40 PDT
I used the implementation of Array.prototype.join below and the command line:

  TRACEMONKEY=verbose $JS -j -f join.js string-fasta.js

An obvious problem with the pure-JS join() is that we'll be using repeated calls to js_ConcatStrings instead of constructing a single string, but right now we're not even staying on trace.  The inner loop in join() gets traced early.  Then we try to trace an outer loop, and:

  abort: 3538: unsupported operand types for cmp
  Abort recording (line 7, pc 58): JSOP_EQ.

The culprit is the "ak == null" in this line:
  var R = (ak == null ? "" : "" + a0);

(At some point, I think our benchmark-driven special-casing in jstracer.cpp has to give way to a more comprehensive approach.  It seems like jstracer's record_JSOP_* methods should look more like the ECMA standard, e.g. http://bclary.com/2004/11/07/#a-11.9.3 , to the degree that the "if"s in the standard are checking for conditions that are trace-constant, like "if Type(x) is not Number".  I would love to get on that, maybe post-3.1.)


// join.js

function join(separator) {
    var n = this.length | 0;
    separator = (separator === void 0 ? "," : "" + separator);
    if (n == 0)
        return "";
    var a0 = this[0];
    var R = (ak == null ? "" : "" + a0);
    for (var k = 1; k != n; k++) {
        var ak = this[k];
        R += separator + (ak == null ? "" : "" + ak);
    }
    return R;
}

Array.prototype.join = join;

delete join;
Comment 7 Jason Orendorff [:jorendorff] 2008-10-17 10:21:02 PDT
With the version of join() below, we only lose 5.2% on string-fasta.

Also--I confirmed that this version, and presumably the previous version too, actually fixes the bug by aborting/falling off trace.

function join(separator) {
    var n = this.length >>> 0;  // ToUint32
    separator = (separator === void 0 ? "," : "" + separator);
    if (n == 0)
        return "";
    var a0 = this[0];
    var R = (a0 == null ? "" : "" + a0);
    for (var k = 1; k != n; k++) {
        var ak = this[k];
        R += separator + (ak == null ? "" : ak);
    }
    return R;
}

Array.prototype.join = join;

delete join;
Comment 8 Jason Orendorff [:jorendorff] 2008-10-24 09:11:38 PDT
Self-hosting this, and a bunch of other stuff, is a great thing to do a month or two down the road.  For now, I think we just add code in the C++ implementation to bail out if it finds an object in the array on trace.  Taking.
Comment 9 Jason Orendorff [:jorendorff] 2008-10-27 17:51:58 PDT
Created attachment 345030 [details] [diff] [review]
v1

Fix and test.  The assert at the top of js_Interpret is trying to check that we haven't been called from JITted code.  Otherwise this bug isn't really testable--reentering is bad but seems impossible to measure.
Comment 10 Jason Orendorff [:jorendorff] 2008-10-28 11:26:23 PDT
I think there are many other bugs like this one.  You could generate any number of cases that flunk the new assertion, just by looking at the source code of the builtins.  Any builtin that does something like OBJ_DEFAULT_VALUE could almost certainly trip this assertion.

Fixing them might be counterproductive, as we hope to make this safe soon.  But in the meantime, I don't know that we've discussed how dangerous reentering the interpreter might be.  Some JS stack frames that should be there aren't, so there are security implications.
Comment 11 Brendan Eich [:brendan] 2008-10-28 11:59:21 PDT
You had me at "memory safety" :-P -- no need to worry about missing frames (the JIT won't cross origin boundaries, so access checking won't go wrong, but that is cold comfort given the memory safety probs).

So yeah, we have discussed the danger but we haven't addressed it with a patch for bug 456511 yet. Let's talk about it today.

/be
Comment 12 Brendan Eich [:brendan] 2008-10-28 17:33:24 PDT
Comment on attachment 345030 [details] [diff] [review]
v1

>+    onTrace = JS_ON_TRACE(cx);
. . .
>             } else if (op == TO_STRING) {
>+                if (onTrace && !JSVAL_IS_PRIMITIVE(*rval)) {
>+                    /*
>+                     * Don't risk reentering the interpreter. In this special
>+                     * case we return false without reporting an error.
>+                     */
>+                    ok = JS_FALSE;
>+                    goto done;

This is a silent failure not only "on trace" as in executing a trace, but when recording, which is a breaking (and broken) semantic change.

>+                }
>                 str = js_ValueToString(cx, *rval);

What we really want is something lower, in 

>             } else {
>                 JS_ASSERT(op == TO_SOURCE);
>                 str = js_ValueToSource(cx, *rval);

toSource presents the same difficulty as toString.

>+function testArrayJoin() {
>+    var bad = {
>+        toString: function() {
>+            // Should bail off trace before getting here.
>+            return "y";
>+        }
>+    };
>+
>+    var arrays = []
>+    for (var i = 0; i < HOTLOOP; i++)
>+        arrays.push(["x", "y", "z", "z", "y"]);
>+    arrays.push(["x", "y", "z", "z", bad]);

So changing the loop limit to HOTLOOP - 1 should put bad on the recording path, and cause a silent failure from join that is not recoverable.

>+
>+    var s;
>+    for (var i = 0; i < arrays.length; i++)
>+        s = arrays[i].join('');
>+    return 'no assertion';
>+}
>+testArrayJoin.expected = 'no assertion';
>+test(testArrayJoin);
>+
> /* Keep these at the end so that we can see the summary after the trace-debug spew. */
> print("\npassed:", passes.length && passes.join(","));
> print("\nFAILED:", fails.length && fails.join(","));

Beware there's a test,

/* Keep this test last, since it screws up all for...in loops after it */
function testGlobalProtoAccess() {
    . . .

that wants to be last. It's already not last (again!) but easy to fix. It messes with shared state via global code. Possibly it could be rewritten to clean up after itself, at least in part.

You've got a better plan for guarding called builtins that unexpectedly enter the interpreter from a triggered trace, but I wanted to review and note some things here. I'll trivially fix trace-test.js but feel free to fiddle with testGlobalProtoAccess so it does not need to be last.

/be
Comment 13 Brendan Eich [:brendan] 2008-10-28 17:36:58 PDT
(In reply to comment #12)
> >                 str = js_ValueToString(cx, *rval);
> 
> What we really want is something lower, in 

Oops, cut off mid-sentence. What I was getting at is how js_TryMethod is the low-level place to add some defensive mechanism. Still not sure how best to defend, but we don't want to whack-a-mole up here in one part of one particular method among many.

> 
> >             } else {
> >                 JS_ASSERT(op == TO_SOURCE);
> >                 str = js_ValueToSource(cx, *rval);
> 
> toSource presents the same difficulty as toString.

js_ValueToSource tries toSource via js_TryMethod also.

/be
Comment 14 Brendan Eich [:brendan] 2008-10-28 17:45:31 PDT
Great result on only a 5.2% slowdown -- that's within striking distance.

(In reply to comment #8)
> Self-hosting this, and a bunch of other stuff, is a great thing to do a month
> or two down the road.  For now, I think we just add code in the C++
> implementation to bail out if it finds an object in the array on trace. 
> Taking.

So we don't lose this idea, could you please file a bug about self-hosting join at least? We should probably list a bunch of candidates to self-host.

/be
Comment 15 Jason Orendorff [:jorendorff] 2008-10-30 00:00:54 PDT
OK, filed bug 462300 on that.
Comment 16 Jason Orendorff [:jorendorff] 2008-12-09 08:45:18 PST
Bug 456511 (imacros) didn't fix this.  Changing to depend on bug 462027 instead.
Comment 17 Brendan Eich [:brendan] 2008-12-09 10:54:22 PST
456511 couldn't fix this, since it dealt only with implicit conversions (value to string or number, value to iterator) and scripted call-iterator-next.

With the upcoming patch for bug 465460 it might be possible to write an imacro that expands a native call followed by a loop to self-host callback invocation, as for lambda-replace. That might help here without taking the full self-hosting plunge now.

/be
Comment 18 Andreas Gal :gal 2009-02-03 16:43:45 PST
WFM with TM TIP (462027 landed). Please verify.

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