503080 - Remove prototype-scope-sharing

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jason Orendorff [:jorendorff]]

Empty native objects share their prototype's scope. This means an object's shape alone does not determine its layout (bug 501986) or what own properties it has (bug 502914). It also has consequences for property cache entries that have a protoIndex (bug 501690).

I expect there are more bugs in those areas but rather than hunt them, I want to remove this feature and make shape determine layout. If empty objects share a prototype, they can still all share a scope, but it should have a different shape from the prototype.

In bug 497789, Brendan aims to make shape cover the prototype chain. I think that effort is orthogonal to this smaller one, though the two patches will touch some of the same code.

Comment 1

[Brendan Eich [:brendan]]

I'd prefer the simplest fix for this bug, to spot-fix and to avoid conflicts:

12345678901234567890123456789012345678901234567890123456789012345678901234567890
#define OBJ_SHAPE(obj)                  ((OBJ_SCOPE(obj)->object == obj)      \
                                         ? OBJ_SCOPE(obj)->shape : 0)

Provided this is a spot-fix. Is it?

/be

Comment 2

[Brendan Eich [:brendan]]

I see naked scope->shape uses and defs in *.cpp but at a glance the uses seem well-guarded by scope->lastProp or equivalent (i.e., the scope is not empty). But is that enough? It must be if the scope is for a proto with own scope in which we found the id'ed prop.

/be

Comment 3

[Brendan Eich [:brendan]]

Making empty objects share a scope other than their prototype will require new sharing machinery (where would this scope be found?) and it costs more than the well-predicted target-in-pipeline (minor cycle penalty on mispredict) proposed OBJ_SHAPE revision.

/be

Comment 4

[Jason Orendorff [:jorendorff]]

(In reply to comment #1)
> Provided this is a spot-fix. Is it?

The corresponding parts of the JIT would also need to be changed.

It's the underlying complexity I'm after. Not counting assertions there are maybe 25 places where (scope->object == obj) is tested. I'd like to get rid of those.

(In reply to comment #3)
> Making empty objects share a scope other than their prototype will require new
> sharing machinery (where would this scope be found?)

It could be found by looking on the prototype's scope: since in this scheme nonempty scopes would never be shared, each nonempty scope could have a pointer to the empty scope from which it was made, a shareable empty scope with the same ops and number of reserved slots.  (This pointer could fit in a union with nrefs, which in a nonempty scope would be redundant.)

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> (In reply to comment #1)
> It could be found by looking on the prototype's scope: since in this scheme
> nonempty scopes would never be shared, each nonempty scope could have a pointer
> to the empty scope from which it was made, a shareable empty scope with the
> same ops and number of reserved slots.  (This pointer could fit in a union with
> nrefs, which in a nonempty scope would be redundant.)

With null lastProp and zero entryCount discriminating the union? I'd buy that for a dollar! Go strong, r? me any time. Thanks,

/be

Comment 6

[Jason Orendorff [:jorendorff]]

(In reply to comment #5)

It looked promising, but alas the scope-sharing code also uses nrefs.

Possibilities from here:

0. Just do what comment 1 says.

1. Make the scope-sharing code not use nrefs. Move that implementation detail into JSTitle somehow. (I don't know how.)

2. Just make JSScope one word bigger for the emptyScope pointer.

3. Like #2, but offset the bloat by getting rid of JSScope::object or JSScope::freeslot. I think either or both could be eliminated, with some though. The hash table is 4 words too; if most objects do not need one (and have we re-tuned SCOPE_HASH_THRESHOLD since the property cache and JIT?), we could save 3 words there.

Regardless of what choice is made here, I am now worried about bug 501986 being patched in time; I'll post there next.

Comment 7

[Brendan Eich [:brendan]]

Let's get rid of JSScope::object (I was assuming it would go in the patch for this bug). It's no longer necessary once scopes aren't shared between unmutated newborn objects and their prototypes or grand-protos, etc.

The title is mislocated in scope when it should be in multi-thread-accessible objects and only in such objects. Moving it leaves a scope representing a particular shape, which suggests both much more aggressive thread-local sharing of scopes (as shape structures -- JSShape not JSScope), and also suggests GC memory management of scopes. This is for other bugs (please file and block the make-over bug), but it could shrink the size of a scope further.

Some objects need a mutable hash, though, and won't fit into a shared shape tree. Such dictionary objects should be special cases (see bug 473228).

/be

Comment 8

[Jason Orendorff [:jorendorff]]

(In reply to comment #7)
> Let's get rid of JSScope::object (I was assuming it would go in the patch for
> this bug). It's no longer necessary once scopes aren't shared between unmutated
> newborn objects and their prototypes or grand-protos, etc.

As it turns out JSScope::object is used in scope-sharing too (the js_MakeStringImmutable business).

Not sure what to do now.

Comment 9

[Jason Orendorff [:jorendorff]]

Well, I'm going to implement a patch for approach #2 in comment 6.  Once I have something working we can worry about fixing the bloat.

Comment 10

[Jason Orendorff [:jorendorff]]

Attachment: WIP 1

Minimal first step.

- Bloat JSScope by a word, emptyScope.

- Give new objects an empty scope.

Passes js/tests and trace-test.js.  No measurable change on bench.sh, but I think something in here is making createMandelSet not trace.

TODO:

- Fix whatever's hurting createMandelSet.

- See about having Block clones and maybe Function clones share their parent's scope.  In the case of Block clones that scope is nonempty; my aim would be for the sharing to actually mean these objects have the same own properties!

- Look at the cost of getEmptyScope and the cost of actually searching empty scopes (which I guess we do, with the patch). On trace we could eliminate getEmptyScope for plain Objects, Arrays, and Functions by embedding the empty scope in the trace.

- Eliminate the extra scope->object==obj checks everywhere and possibly other safety checks.

- Eliminate the bloat.

Looks like a lot, but I'm happier having a WIP that runs...

Comment 11

[Igor Bukanov]

(In reply to comment #10)
> - Look at the cost of getEmptyScope and the cost of actually searching empty
> scopes (which I guess we do, with the patch). On trace we could eliminate
> getEmptyScope for plain Objects, Arrays, and Functions by embedding the empty
> scope in the trace.

Ideally the empty scope should be allocated together with JSClass. But that would mean some API changes. So an alternative is to have a some kind of a fast lock-less hash for that. For example, some JS classes has prototype index. We can use that to have a scope table for those classes.

Comment 12

[Jason Orendorff [:jorendorff]]

The WIP 1 patch has a severe bug that is closely related to bug 503860.  I don't yet know how to fix it.

Comment 13

[Jason Orendorff [:jorendorff]]

Attachment: WIP 2

Fixes the bug in WIP 1 without fixing bug 503860.

I changed it so that even a shared scope can have a (nonnull) emptyScope. It's simpler that way and (temporarily) more correct.  But once bug 503860 is fixed, I will re-add the assertion in createEmptyScope() that this->object is nonnull.

Comment 14

[Jason Orendorff [:jorendorff]]

Attachment: v3

This fixes and includes tests for bug 501986 and bug 501690.

Bloats JSScope by a word. With this patch, scope->object is used in 3 places:

- JSScope::owned() { return object != NULL; } This use could easily
  be reduced to a single bit in JSScope::flags.
- js_MakeScopeShapeUnique (probably easy to remove)
- FinishSharingTitle, in jslock.cpp (Harder to remove, but in the future we want sharing to be object-granularity; see also bug 504227.)

So I want to land this, to fix the crashers and avoid bitrotting; and recover the word of bloat in bug 504227.

Comment 15

[Brendan Eich [:brendan]]

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

>@@ -403,18 +402,18 @@ js_NewNullClosure(JSContext* cx, JSObjec
> 
>     JSFunction *fun = (JSFunction*) funobj;
>     JS_ASSERT(GET_FUNCTION_PRIVATE(cx, funobj) == fun);
> 
>     JSObject* closure = js_NewGCObject(cx, GCX_OBJECT);
>     if (!closure)
>         return NULL;
> 
>-    OBJ_SCOPE(proto)->hold();
>-    closure->map = proto->map;
>+    JSScope *scope = OBJ_SCOPE(proto)->getEmptyScope(cx, &js_FunctionClass);

OOM check here.

>+    kshape = (jsuword) -1;

Suggest s/NOT_ADDING/NO_SHAPE/, or make an alias NO_SHAPE, and use it here.

>-    if (kshape == 0) {
>+    if (kshape == (jsuword) -1) {

And here.

>     /*
>      * Special-case cloning the innermost block; this doesn't have enough in
>      * common with subsequent steps to include in the loop.
>      *
>+     * js_CloneBlockObject leaves the clone's parent slot uninitialized.  We
>+     * populate it below.

French spacing red alert!

>+#define NOT_ADDING              (jsuword(-1))

static const is the new #define?

> js_DefineNativeProperty(JSContext *cx, JSObject *obj, jsid id, jsval value,
>                         JSPropertyOp getter, JSPropertyOp setter, uintN attrs,
>                         uintN flags, intN shortid, JSProperty **propp,
>                         uintN defineHow /* = 0 */)
> {
>     JSClass *clasp;
>     JSScope *scope;
>     JSScopeProperty *sprop;
>-    bool added;
> 
>     JS_ASSERT((defineHow & ~(JSDNP_CACHE_RESULT | JSDNP_DONT_PURGE)) == 0);
>     js_LeaveTraceIfGlobalObject(cx, obj);
> 
>     /* Convert string indices to integers if appropriate. */
>     id = js_CheckForStringIndex(id);
> 
> #if JS_HAS_GETTER_SETTER
>@@ -3715,45 +3726,48 @@ js_DefineNativeProperty(JSContext *cx, J
>     /* Use the object's class getter and setter by default. */
>     clasp = LOCKED_OBJ_GET_CLASS(obj);
>     if (!getter)
>         getter = clasp->getProperty;
>     if (!setter)
>         setter = clasp->setProperty;
> 
>     /* Get obj's own scope if it has one, or create a new one for obj. */
>+    jsuword shapeBefore;

Slightly better diff and goto-unaware "maintenance" (i.e., someone comes along and pulls the assignment up to initialize this decl) defense to put the decl where bool added was?

>+    shapeBefore = OBJ_SHAPE(obj);
>     scope = js_GetMutableScope(cx, obj);
>     if (!scope)
>         goto error;
> 
>-    added = false;
>+    jsuword shapeBeforeAdd;

Ditto, I think.

>@@ -4534,26 +4551,28 @@ js_SetPropertyHelper(JSContext *cx, JSOb
>             sprop = NULL;
>         }
> #ifdef __GNUC__ /* suppress bogus gcc warnings */
>     } else {
>         scope = NULL;
> #endif
>     }
> 
>-    added = false;
>+    jsuword shapeBeforeAdd;
>+    shapeBeforeAdd = NOT_ADDING;

Ditto again.

We used to use the before-shape approach, but Igor changed it due to the setter having potentially any effects, including a GC. I'm making shape regen conditional on overflow in the bug 497789 patch (which will feel major conflict pain from this patch, sucks to be me! but you should go first, your patch helps). Until then, is this really safe?

> #define OBJ_IS_CLONED_BLOCK(obj)                                              \
>-    (OBJ_SCOPE(obj)->object != (obj))
>+    (OBJ_GET_PROTO(BOGUS_CX, obj) != NULL)

No BOGUS_CX please -- obj->fslots[JSSLOT_PROTO] != JSVAL_NULL would be best here I think, but note STOBJ_SET_SLOT below:

> #define OBJ_BLOCK_COUNT(cx,obj)                                               \
>     (OBJ_SCOPE(obj)->entryCount)
> #define OBJ_BLOCK_DEPTH(cx,obj)                                               \
>     JSVAL_TO_INT(STOBJ_GET_SLOT(obj, JSSLOT_BLOCK_DEPTH))
> #define OBJ_SET_BLOCK_DEPTH(cx,obj,depth)                                     \
>     STOBJ_SET_SLOT(obj, JSSLOT_BLOCK_DEPTH, INT_TO_JSVAL(depth))

Could do likewise. The macrology cleanup bug (should take in C++ inline method upgrades) is bug 416058. Feel free to steal.

>+JSScope::createEmptyScope(JSContext *cx, JSClass *clasp)
>+{
>+    JS_ASSERT(!emptyScope);
>+
>+    JSScope *scope = (JSScope *) JS_malloc(cx, sizeof(JSScope));
>+    if (!scope)
>+        return NULL;
>+
>+    scope->map.ops = map.ops;
>+    scope->object = NULL;
>+
>+    /*
>+     * This scope holds a reference to the new empty scope. The caller,

s/The caller/Our *only* caller/

Looks pretty great otherwise. r+ with above addressed, really the non-nit issue of setter forcing GC.

/be

Comment 16

[Jason Orendorff [:jorendorff]]

Attachment: v4

As discussed on IRC, the shapeBeforeAdd stuff was not at all safe against a misbehaving addProperty hook.  I reverted to igor's version and wrote some moderately gross code to figure out the most likely shape-before-add. Interdiff should work betwen v3 and v4.

Comment 17

[Brendan Eich [:brendan]]

(In reply to comment #15)
> ... the non-nit issue of setter forcing GC.

s/setter/addProperty/ of course.

/be

Comment 18

[Brendan Eich [:brendan]]

Comment on attachment 389070 [details] [diff] [review]
v4

>+/*
>+ * If an object is "similar" to its prototype, it can share OBJ_SCOPE(proto)->emptyScope.
>+ * Similar objects have the same JSObjectOps and the same private and reserved slots.
>+ *
>+ * We assume that if prototype and object are of the same class, they always

s/prototype and object/proto and obj/

or else "the object and its prototype", but formal names win.

>+ * have the same number of computed reserved slots (returned via
>+ * clasp->reserveSlots). This is true for builtin classes (except Block, and
>+ * for this reason among others Blocks must never be exposed to scripts).
>+ *
>+ * Otherwise, prototype and object classes must have the same (null or not)
>+ * reserveSlots hook.
>+ */
>+static inline bool
>+js_ObjectIsSimilarToProto(JSContext *cx, JSObject *obj, JSObjectOps *ops, JSClass *clasp,
>+                          JSObject *proto)

Why not break new ground by making this an inline JSObject method? If you are targeting the 1.9.1 branch you'll need #ifdef __cpluscplus in any event for liveconnect on lame platforms that lack inline.

Is the "similar" condition still valid? It was based on reasoning about slots lining up between obj and proto for non-JSPROP_SHARED properties, in case of a set (not get) shadowing the proto-prop and writing to its slot in the direct obj. But as you've pointed out re: shapes, different classes might have different resolve or addProperty customizations, which could wreck assumptions here.

/be

Comment 19

[Jason Orendorff [:jorendorff]]

(In reply to comment #18)
> Why not break new ground by making this an inline JSObject method? If you are
> targeting the 1.9.1 branch you'll need #ifdef __cpluscplus in any event for
> liveconnect on lame platforms that lack inline.

I can just change that to JS_INLINE for 1.9.1.  A method would be a bit harder to backport.

Bug 498488 will turn several macros into JSObject methods.

I'm not sure this one should be a method though. It's a style question. This function has more to do with the property cache than JSObject itself. I'm OK with an occasional plain old function.

> Is the "similar" condition still valid? [...]
>    [...] as you've pointed out re: shapes, different classes might have
> different resolve or addProperty customizations, which could wreck
> assumptions here.

Was it valid before?  I thought that was a preexisting bug; if so, I'll fix, but in a separate bug (not slated for landing in 1.9.1).

Comment 20

[Brendan Eich [:brendan]]

(In reply to comment #19)
> I can just change that to JS_INLINE for 1.9.1.  A method would be a bit harder
> to backport.
> 
> Bug 498488 will turn several macros into JSObject methods.

Cool, thanks.

> I'm not sure this one should be a method though. It's a style question. This
> function has more to do with the property cache than JSObject itself.

See bug 500431.

> I'm OK with an occasional plain old function.

Ok for now.

> > Is the "similar" condition still valid? [...]
> >    [...] as you've pointed out re: shapes, different classes might have
> > different resolve or addProperty customizations, which could wreck
> > assumptions here.
> 
> Was it valid before?

Oh by no means!

> I thought that was a preexisting bug; if so, I'll fix,
> but in a separate bug (not slated for landing in 1.9.1).

Sure. Cite it in a FIXME: comment. I'll r+ now.

/be

Comment 21

[Jason Orendorff [:jorendorff]]

The FIXME comment cites bug 505523.

Rebasing this to tip caused a nasty regression, due to a conflict with bug 504478, resolved thus:

-    if (IS_GC_MARKING_TRACER(trc)) {
-        /* Check whether we should shrink the object's slots. */
+    if (scope->owned() && IS_GC_MARKING_TRACER(trc)) {
+        /*
+         * Check whether we should shrink the object's slots. Skip this check
+         * if the scope is shared, since for Block objects and flat closures
+         * that share their scope, scope->freeslot can be an underestimate.
+         */
         size_t slots = scope->freeslot;
         if (STOBJ_NSLOTS(obj) != slots)
             js_ShrinkSlots(cx, obj, slots);
     }

Before this patch, in those particular cases the scope was shared with a proto, and the check was skipped due to other logic.

Comment 22

[Jason Orendorff [:jorendorff]]

http://hg.mozilla.org/tracemonkey/rev/3915e2d2c748

Comment 23

[Jason Orendorff [:jorendorff]]

Quick followup to fix a memory leak found by sewardj.

http://hg.mozilla.org/tracemonkey/rev/8e334d4b4d36

Comment 25

[Mike Beltzner [:beltzner, not reading bugmail]]

There are two bugs that were nominated for blocking 1.9.1.x which ended up being fixed by this bug:

 bug 503620
 bug 501690

The patch on this bug is pretty large, and I worry about taking it on the branch. What are the chances of minimal branch fixes for those issues? Or how can we gain confidence about this patch?

Comment 26

[Jason Orendorff [:jorendorff]]

(In reply to comment #25)
> There are two bugs that were nominated for blocking 1.9.1.x which ended up
> being fixed by this bug:

Three, if you count bug 501986.

> What are the chances of minimal branch fixes for those issues?

In bug 501986 there is a minimal patch. I don't know if it fixes bug 503620 and bug 501690.

> Or how can we gain confidence about this patch?

Well, the tests seem to be passing. It looks like our options include (a) additional reviews; and (b) getting the patch into a branch where it will get more QA.

I don't know if (b) is an option at this point or what the target branch would be.

As for code reviews, perhaps igor, bz, or gal would be willing. (Who else is familiar enough with the property cache?)

Comment 27

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/3915e2d2c748

Comment 28

[Bob Clary [:bc] (inactive)]

trace-test testBug501690|testObjectVsPrototype