487039 - Name cache does not detect prototype mutations

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Igor Bukanov]

As Jim Blandy reported in 
http://groups.google.com/group/mozilla.dev.tech.js-engine/browse_thread/thread/a80d3b63fc1f0f2e# , the property cache, when used to look up names on a scope chain with at least 2 native objects, may not detect additions of the properties for the prototype object and return wrong results for the name lookup.

For example, consider the following example for js shell:

this.x = 0;
var a = evalcx("this");
var b = {__proto__: a, a: a };

var r = evalcx("("+function() {
        for (var i = 0; i != 2; ++i) {
            var f = x;
            if (i == 0) {
                a.x = 1;
            }
        }
        return f;
    }+")()", b);

if (b.x !== r)
    throw "Cache inconsistency: expected="+b.x+" actual="+r;

Here the first evalcx is used to create a new global object. This global object is used as a prototype for the object b. Then the second evalcx executes function with b on the scope chain so we have 2 native objects there, b and the original global object.

When inside this second evalcx the interpreter executes var f = x for the first time, it finds the property x in the original global object, the parent of b. It caches the result recording shapes of both b and the original global in the cache. 

Then the interpreter executes a.x = 1. The code for this assignment tries to mutate shapes of all parent and proto objects reachanble from a. But since "a" comes from the first evalcx, these mutations not touch the shape of the original global. Thus, when the interpreter executes f = x, it would detect that the cache is still valid missing addition of the new property to b's prototype.

A similar setup can be created in the browser using event handlers (they have DOM objects on the scope chain) and objects created in iframes (they have unrelated globals).

Comment 1

[Igor Bukanov]

A simple way to solve this bug is to disable caching of names comming from the scope chains with multiple natives. I.e. the cache should only store the first native after the block, call and with objects on the prototype chain. The upper natives should be ignored.

This will penalize event handlers defined in various onsomething attributes, but caching for those probably affect only very synthetic tests.

Comment 2

[Igor Bukanov]

Multiple natives at the tail of the prototype chain can be simulated using eval(source, obj). This form of the eval creates a with object wrapper around obj and adds it to the scope chain before evaluating the source. Compared with the with statement, it does not disable the property cache. It allows to expose the bug in a different way via adding the property to the prototype of the obj like in:

this.x = 0;

var foreign = evalcx("this;");   
var obj = { __proto__: foreign };

var r = eval("("+f+")()", obj);
assertEq(r, 1);

function f()
{
    __proto__;
    for (var i = 0; i != 2; ++i) {
        var r = x;
        if (i == 0)
            foreign.x = 1;
    }
    return r;
}

When executed, the example generates:

/home/igor/s/x2.js:7: TypeError: Assertion failed: got 0, expected 1

A simple way to fix this form of the bug is to change js_FindPropertyHelper so it would never put anything to the property cache after it hits an object on the scope chain where ops->lookupProperty != js_LookupProperty. Cuurrently, if the parent of such object has the default js_LookupProperty, then the cache is still used.

Comment 3

[Robert Sayre]

is this a regression?

Comment 4

[Igor Bukanov]

(In reply to comment #3)
> is this a regression?

This a regression from 1.8. That is, the same bug exists on 1.9.0 as well.

Comment 5

[Igor Bukanov]

Attachment: v1 (work in progress)

The patch is untested work in the progress. It does the following:

1. It enables the name cache only if non-globals from the scope chain comes from known white-listed classes. This is based on the patch from the bug 469237 comment 66. But compared with that patch the code does not enable the cache if property comes from the first non-white-listed object that is not a global object. That is, it does not enable cache for dom event handlers defined via HTML attributes like in onevent="script code". This could be reconsidered, but for now code simplicity wins.

2. It removes property cache disable/enable code for with blocks. The above white-listening reliably filter-out the With objects including the cases when they comes from closures (which is not done currently).

3. It creates Call objects with null prototype using js_NewObjectWithGivenProto to avoid the need to create always empty Call prototype.

Comment 6

[Igor Bukanov]

Attachment: v2

The new version fixes some (bad) typos and passes shell tests. I also observed no changes with performance numbers in sunspider and trace-test.js benchmarks.

For details of the patch, see comment 5.

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #0)
> A similar setup can be created in the browser using event handlers (they have
> DOM objects on the scope chain)

But all the non-terminal scope chain objects have the same global object as parent. Isn't it a necessary condition for this bug to have two globals that terminate parent-linked chains of objects linked along an active scope chain's parent and proto chains?

> and objects created in iframes (they have
> unrelated globals).

This is indeed an issue. Fortunately it's rare to have such scrambled scopes, I know of no reports from Fx3.0.x.

/be

Comment 8

[Brendan Eich [:brendan]]

(In reply to comment #1)
> A simple way to solve this bug is to disable caching of names comming from the
> scope chains with multiple natives. I.e. the cache should only store the first
> native after the block, call and with objects on the prototype chain. The upper
> natives should be ignored.
> 
> This will penalize event handlers defined in various onsomething attributes,
> but caching for those probably affect only very synthetic tests.

If the answer to the question in comment 7, first paragraph, is "yes", then a less restrictive fix would avoid caching any natives along a scope chain whose prototypes lead to other globals than the one at the end of the active scope chain.

/be

Comment 9

[Igor Bukanov]

(In reply to comment #7)
> But all the non-terminal scope chain objects have the same global object as
> parent. Isn't it a necessary condition for this bug to have two globals that
> terminate parent-linked chains of objects linked along an active scope chain's
> parent and proto chains?

No: all iframe prototypes are indeed rooted in the top window, but that tree can be arbitrary. The bug would happen if one picks any 2 nodes from different branches of this tree.

Comment 10

[Brendan Eich [:brendan]]

(In reply to comment #9)
> (In reply to comment #7)
> No: all iframe prototypes are indeed rooted in the top window, but that tree
> can be arbitrary. The bug would happen if one picks any 2 nodes from different
> branches of this tree.

I don't see how -- can you show a testcase?

The parent and proto chains are lists. The combination for a single global object regime forms a lattice with one top object to reshape if it contains a shadowed property.

When I designed this, I knew 'with' could easily make lattices with two tops, so I disabled the cache inside with.

It would be great to improve this. But first I need to understand how in a single iframe, with all sub-objects' parent chains leading back to the iframe, the current code fails.

/be

Comment 11

[Igor Bukanov]

Attachment: html test case

Here is HTML example demonstrating the bug. It does not use iframes but relies on the fact that for dom event handlers the scope chain includes the element, document and window.

The example contains:

<div onclick="for (var s,i=0; i!=2; ++i) { s=x; __proto__.x=2;} show(__proto__, s)">
...
<script>
document.x = 1;

Here due to hashing s is set to 1 again on the second loop iteration, the value coming from document. The shape change from __proto__.x = 2 is not propagated to document as it is neither on the scope nor prototype chains of the prototype of DIV html element.

Note that here all the prototype chains ends with Object.prototype and all the __parent__ chains ends in window.

Comment 12

[Brendan Eich [:brendan]]

Can you show a testcase that does not use __proto__? I did not consider it enough in designing the property cache (obvious from all the mutable __proto__ cases I missed! But here is a case with only a read using __proto__). To keep sanity and future-proofing we should fix this bug, but I regret __proto__ and claim that without it, the cache gives correct results.

Lacking __proto__, one might write constructor.prototype instead. Changing the test to use constructor.prototype shows correct results, per my hypothesis.

/be

Comment 13

[Igor Bukanov]

Attachment: html test case without __proto__

Here is a version of the previous example where I replaced __proto__ with Object.prototype, the end of the prototype chain for HTML element objects, document and window.

Comment 14

[Igor Bukanov]

(In reply to comment #12)
> but I regret __proto__ 

I do not see a problem with read-only __proto__. In most cases it can be used to access the objects that are accessible in other ways in any case (constructor.prototype indeed).

__parent__ is much worse in that respect. It makes each and every object bigger due to the space to hold __parent__ value. Without __parent__ such space would only be necessary for objects that can present on the scope chain or functions. Moreover, __parent__ leaks the scope chain which makes it hard to use a special-purpose runtime entities to optimize the name lookup, not real objects.

Comment 15

[Brendan Eich [:brendan]]

You're right, __proto__ is not a problem for this bug.

Not to worry, I regret __parent__ as well (not just the read-only reflection but the fixed slot in every object). However, it is used in objects other than DOM nodes and function objects, but see bug 476950. It's currently required to find the "object principals" for any object.

Also, I thought the intrinsic scope link was important to the cache, and this bug shows that it's not. An extrinsic scope chain link would work too, provided all the objects on the scope chain were unnameable (as Block and Call objects are) except for the last object. I'll review later today.

/be

Comment 16

[Igor Bukanov]

Attachment: v3

The new version of the patch removes no longer useful pcDisabledSave flags. With the patch the interpreter does not disable/enable the cache for with blocks.

Comment 17

[Brendan Eich [:brendan]]

In recollecting the cache design process, which was mostly a lot of thinking whereever I could find quiet, I definitely had a lexically scoped model in mind, except of course for the global. The lattice (kind of a "rook digraph") of proto and parent chains has no links in from variables like document, until you get to the global (window in the DOM) object. So no one can "reach behind" the shadowing detection logic.

It's great to get rid of the 'with' disabling -- that was obviously necessary in Firefox 3.0 era given the miscalculation about lexical frames all the way to the top level.

/be

Comment 18

[Brendan Eich [:brendan]]

Comment on attachment 373336 [details] [diff] [review]
v3

>-JSObject *
>-js_InitCallClass(JSContext *cx, JSObject *obj)
>-{
>-    JSObject *proto;
>-
>-    proto = JS_InitClass(cx, obj, NULL, &js_CallClass, NULL, 0,
>-                         NULL, NULL, NULL, NULL);

Great to see this go -- should have removed it all when call_props went away.

>+            goto do_return;

goto out is canonical -- do_ is handy to prefix labels thereby avoiding "readability collisions" with related and otherwise (I mean without the prefix) identical non-label identifiers (no actual collisions), but do_return seems overlong and not accurate (enough to be worth the lenght) here.

r=me with that nit picked, thanks.

/be

Comment 19

[Igor Bukanov]

Attachment: v3

The new version updates the patch to the trunk (a simple merge was necessary due to back out from the bug 487204) plus I changed the "do_return" label to the canonical "out" name. I wonder why I have not used it in the first place?

Comment 20

[Igor Bukanov]

renominating this bug as 1.9.1 blocker:

The patch here allows to address the bug 488414 with much simpler way. In particular, it allows to remove JSPropertyCache.disabled and the code to synchronize the thread-local JSPropertyCache.disabled with the global disabled state of the cache due to shape overflow. Without this patch that code would require regression-prone alterations to address the bug 488414.

Comment 21

[Igor Bukanov]

http://hg.mozilla.org/tracemonkey/rev/1b3a286e71a1

Comment 22

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/1b3a286e71a1

Comment 23

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/8775e6d1772f

Comment 24

[Henrik Skupin [:whimboo][⌚️UTC+2]]

Verified fixed with the testcase in comment 0 and a trunk and 1.9.1 debug build:

Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.2a1pre)
Gecko/20090522 Minefield/3.6a1pre ID:20090522133810

Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1pre)
Gecko/20090522 Shiretoko/3.5pre ID:20090522153422

Comment 25

[Igor Bukanov]

Attachment: 1.9.0 patch

This is what I am testing

Comment 26

[Igor Bukanov]

Attachment: 1.9.0 patch

The new version avoids inline function as 1.9.0 is C code.

Comment 27

[Igor Bukanov]

Attachment: diff between 1.9.1 and 1.9.0 patches

Most of differences in the patches comes from the lack of js_DeclEnvClass on the 1.9.0 branch and avoiding inline function in js_FindPropertyHelper. Another source of important changes is that currently the 1.9.0 tip in couple of places wrongfully uses !js_FindPropertyHelper, not js_FindPropertyHelper < 0, to check for errors. Now, since the patch makes js_FindPropertyHelper to return false, those places are auto-corrected and does not need patching.

Comment 28

[Igor Bukanov]

Attachment: 1.

Comment 29

[Igor Bukanov]

Attachment: 1.9.0 patch

Here is the right patch.

Comment 30

[Igor Bukanov]

Attachment: plain diff between 1.9.1 and 1.9.0 patches

Comment 31

[Brendan Eich [:brendan]]

Comment on attachment 439857 [details]
plain diff between 1.9.1 and 1.9.0 patches

Old on left is better (USENET tradition), also grep '^[<>] [-+]' helps, but thanks for this.

/be

Comment 32

[Brendan Eich [:brendan]]

Comment on attachment 439855 [details] [diff] [review]
1.9.0 patch

Minimal, but I would have preferred to make js_FindPropertyHelper look more like it does in newer branches/trunk -- this would entail adding an IsCacheableNonGlobalScope inline helper.

Up to you, just curious if you think it is worth doing.

/be