1299107 - Share more shapes across compartments

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

Bug 1295967 allowed us to share Shapes and BaseShapes across compartments. While this works, especially for BaseShapes, there's a problem with Shapes: the InitialShapeSet hands out initial shapes based on the proto, and if that proto is non-null we can't share these shapes (because objects belong to a single compartment).

However, in most cases the proto is one of Object.prototype, Function.prototype, etc, and we can do better: if the proto is one of these builtin prototypes, and the prototype chain was not modified, I think we can store the JSProtoKey instead of the TaggedProto (in the InitialShapeSet) and share these shapes.

According to about:memory, this wins at least 400 KB per content process (shape memory goes from ~1.4 MB -> ~1.0 MB) and ~1.7 MB for the parent process.

Note that we do see an increase in BaseShapes and ShapeTables, that's because we allocate a ShapeTable (and an owned BaseShape) when we do more than X lookups, so when we share shape trees we reach this faster.

Content process, shapes before:

│  │   │  ├──1,452,680 B (04.35%) -- shapes
│  │   │  │  ├──1,171,624 B (03.51%) -- gc-heap
│  │   │  │  │  ├──1,032,192 B (03.09%) ── tree
│  │   │  │  │  ├────118,600 B (00.35%) ── dict
│  │   │  │  │  └─────20,832 B (00.06%) ── base
│  │   │  │  └────281,056 B (00.84%) -- malloc-heap
│  │   │  │       ├──133,472 B (00.40%) ── tree-tables
│  │   │  │       ├───99,008 B (00.30%) ── tree-kids
│  │   │  │       └───48,576 B (00.15%) ── dict-tables

│  │   │  ├────106,496 B (00.32%) ── shape-tables

After:

│  │   │  ├──1,044,520 B (03.16%) -- shapes
│  │   │  │  ├────737,160 B (02.23%) -- gc-heap
│  │   │  │  │    ├──593,760 B (01.80%) ── tree
│  │   │  │  │    ├──118,600 B (00.36%) ── dict
│  │   │  │  │    └───24,800 B (00.08%) ── base
│  │   │  │  └────307,360 B (00.93%) -- malloc-heap
│  │   │  │       ├──180,832 B (00.55%) ── tree-tables
│  │   │  │       ├───77,824 B (00.24%) ── tree-kids
│  │   │  │       └───48,704 B (00.15%) ── dict-tables

│  │   │  ├─────73,728 B (00.22%) ── shape-tables


Parent process before:

│  ├───7,753,080 B (13.52%) -- shapes
│  │   ├──6,035,256 B (10.53%) -- gc-heap
│  │   │  ├──4,871,272 B (08.50%) ── tree
│  │   │  ├──1,014,992 B (01.77%) ── dict
│  │   │  └────148,992 B (00.26%) ── base
│  │   └──1,717,824 B (03.00%) -- malloc-heap
│  │      ├────885,056 B (01.54%) ── tree-tables
│  │      ├────456,480 B (00.80%) ── tree-kids
│  │      └────376,288 B (00.66%) ── dict-tables

│  ├─────560,128 B (00.98%) ── shape-tables

Parent process after:

│  ├───6,029,528 B (10.87%) -- shapes
│  │   ├──4,401,496 B (07.94%) -- gc-heap
│  │   │  ├──3,234,088 B (05.83%) ── tree
│  │   │  ├──1,014,992 B (01.83%) ── dict
│  │   │  └────152,416 B (00.27%) ── base
│  │   └──1,628,032 B (02.94%) -- malloc-heap
│  │      ├────913,440 B (01.65%) ── tree-tables
│  │      ├────377,312 B (00.68%) ── dict-tables
│  │      └────337,280 B (00.61%) ── tree-kids

│  ├─────449,536 B (00.81%) ── shape-tables

Comment 1

[Jan de Mooij [:jandem]]

The numbers in comment 0 are for a mostly-empty content process (4 processes, example.com open in 2 tabs, I clicked minimize memory 3 times).

Comment 2

[Jan de Mooij [:jandem]]

Attachment: Patch

Waldo, can you think of any potential correctness issues here?

Comment 3

[Jeff Walden [:Waldo]]

Comment on attachment 8786305 [details] [diff] [review]
Patch

Review of attachment 8786305 [details] [diff] [review]:
-----------------------------------------------------------------

Hooooooooo boy.  I have low confidence in being able to spot issues in this if they exist, exactly.  So there's that.

One possibility, however, does occur to me.  If in the process of creating Object.prototype, or Function.prototype, or any of those primordial prototypes, there's an error -- *generally* we won't fill in the reserved global slot with the prototype.  But I'm not sure this is 100% guaranteed.  It *used* to be, back in the good old days when Object/Function init was a single intermixt process as befitting the special nature of those two classes.  But it no longer is.

So if we had such an error, and we filled in those slots with a partially-initialized Object.prototype or whatever.  Could sharing by JSProtoKey in that case potentially cause shape optimizations based on that partial Object.prototype shape, to translate into mis-optimizations in compartments that *did* have the full Object.prototype shape?  Do we still have cases where a single shape-check on the original object, tells something about the properties on a prototype object?

My head is swimming a bit looking at this, and I should look at other requests rather than stare too much longer here.  Tell me how I'm crazy, please?

::: js/src/jit-test/tests/basic/globals-shared-shapes.js
@@ +4,5 @@
> +var g2 = newGlobal({sameZoneAs: g1});
> +
> +g1.eval("x1 = {foo: 1}");
> +g2.eval("x2 = {foo: 2}");
> +assertEq(g1.eval("shapeOf(x1)"), g2.eval("shapeOf(x2)"));

...I kind of have my doubts that this is totally and consistently and always correct if a GC hits at just the wrong time and moves stuff around.  Even if shapes aren't movable now (I thought only atoms and JSScripts were immovable, and rumor has it the latter is no longer true), that seems a bad idea to assume.  Add a shell builtin that returns true/false based on equality of shape pointers instead?

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Patch v2

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #3)
> ...I kind of have my doubts that this is totally and consistently and always
> correct if a GC hits at just the wrong time and moves stuff around.  Even if
> shapes aren't movable now (I thought only atoms and JSScripts were
> immovable, and rumor has it the latter is no longer true), that seems a bad
> idea to assume.  Add a shell builtin that returns true/false based on
> equality of shape pointers instead?

Fair enough. It's a bit unfortunate because this shell builtin has to unwrap both objects, to avoid confusion I called it unwrappedObjectsSameShape(obj1, obj2).

Comment 5

[Jan de Mooij [:jandem]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #3)
> So if we had such an error, and we filled in those slots with a
> partially-initialized Object.prototype or whatever.  Could sharing by
> JSProtoKey in that case potentially cause shape optimizations based on that
> partial Object.prototype shape, to translate into mis-optimizations in
> compartments that *did* have the full Object.prototype shape?  Do we still
> have cases where a single shape-check on the original object, tells
> something about the properties on a prototype object?

A shape guard on an object X tells us about the objects on X's prototype chain, but certainly not their properties (or else deleting a property from Object.prototype would reshape the world).

There is the ancient teleporting optimization, it works by guarding on (1) the receiver shape and (2) the holder's shape, and if these match we can be sure nothing on the prototype chain between these 2 objects shadowed the holder's property. Teleporting works because adding a shadowing property to object X reshapes everything up X's prototype chain, so the holder check would fail in that case.

I now realize there could be potential problems when we have, say, the following prototype chains:

 compartment 1: [] (shape 1) -> Array.prototype (shape 2) -> Object.prototype (shape 3) -> null
 compartment 2: [] (shape 1) -> Array.prototype (shape 4) -> Object.prototype (shape 3) -> null

Now if we get a property from Object.prototype, we'll guard the receiver has shape 1 and Object.prototype has shape 3, without guarding on Array.prototype's shape.

What saves us here atm is that IC stubs etc are not shared across compartments (and objects are wrapped when passed between compartments, so these shape guards will definitely fail), but this could become a problem when we add a runtime-wide property cache back (say, to  handle megamorphic property accesses). If this cache used teleporting, it would have to guard holder->compartment == cx->compartment.

It'd be really nice to remove teleporting (and/or fix bug 703164), so all this is no longer a problem, but it's not trivial as the JITs rely on it atm.

Thoughts?

Comment 6

[Jeff Walden [:Waldo]]

Comment on attachment 8786674 [details] [diff] [review]
Patch v2

Review of attachment 8786674 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/shell/js.cpp
@@ +3284,5 @@
>      return true;
>  }
>  
>  static bool
> +UnwrappedObjectsSameShape(JSContext* cx, unsigned argc, JS::Value* vp)

I'd add "Have" into the function/JS shell name.

@@ +3296,5 @@
> +    RootedObject obj1(cx, UncheckedUnwrap(&args[0].toObject()));
> +    RootedObject obj2(cx, UncheckedUnwrap(&args[1].toObject()));
> +
> +    if (!obj1->is<ShapedObject>() || !obj2->is<ShapedObject>()) {
> +        JS_ReportError(cx, "object does not have a Shape");

Could check both and indicate "first argument", "second argument", "neither argument", but this works fine enough.

Comment 7

[Jeff Walden [:Waldo]]

(In reply to Jan de Mooij [:jandem] from comment #5)
> I now realize there could be potential problems when we have, say, the
> following prototype chains:
> 
>  compartment 1: [] (shape 1) -> Array.prototype (shape 2) ->
> Object.prototype (shape 3) -> null
>  compartment 2: [] (shape 1) -> Array.prototype (shape 4) ->
> Object.prototype (shape 3) -> null
> 
> Now if we get a property from Object.prototype, we'll guard the receiver has
> shape 1 and Object.prototype has shape 3, without guarding on
> Array.prototype's shape.

Yeah, handwave handwave this is what I meant handwave handwave.

> What saves us here atm is that IC stubs etc are not shared across
> compartments (and objects are wrapped when passed between compartments, so
> these shape guards will definitely fail)

Ah, good.  Sounds like we can carry on.

>, but this could become a problem
> when we add a runtime-wide property cache back (say, to  handle megamorphic
> property accesses). If this cache used teleporting, it would have to guard
> holder->compartment == cx->compartment.
> 
> It'd be really nice to remove teleporting (and/or fix bug 703164), so all
> this is no longer a problem, but it's not trivial as the JITs rely on it atm.
> 
> Thoughts?

Concur.  And, um, no *precise* thoughts on that, exactly.

Comment 8

[Jan de Mooij [:jandem]]

Michael, this doesn't conflict with your work, right? I don't think it does, but just want to make sure you're aware of it.

We definitely need a big comment in Shape.h to document how Shapes and prototypes interact.

Comment 9

[Jan de Mooij [:jandem]]

Attachment: Patch v3

The previous patch made us use a different shape in some cases after __proto__ changes, not really a correctness problem but it failed a same-shape assert for template objects.

This version is both more efficient and (I think) simpler: now we always store an entry with the TaggedProto, as before, and only if this entry doesn't exist we try to do a lookup based on the JSProtoKey.

Comment 10

[Jeff Walden [:Waldo]]

Comment on attachment 8790257 [details] [diff] [review]
Patch v3

Review of attachment 8790257 [details] [diff] [review]:
-----------------------------------------------------------------

This patch is so horrifying.

::: js/src/vm/Shape.cpp
@@ +1480,5 @@
>      return shape;
>  }
>  
> +static bool
> +IsOriginalProto(GlobalObject* global, JSObject* proto, JSProtoKey key)

It occurs to me reading this again, that global/key coherently define half of the thing |proto| is being compared to, so the two parameters should be adjacent.  Move |proto| to the end?

Additionally, things are gonna be Sad if |proto| is null.  Make it |JSObject& proto| so the null-state needn't be considered.

@@ +1497,5 @@
> +    if (!protoProto || global->getPrototype(JSProto_Object) != ObjectValue(*protoProto))
> +        return false;
> +
> +    MOZ_ASSERT(!protoProto->staticPrototype());
> +    MOZ_ASSERT(protoProto->staticPrototypeIsImmutable());

Let's do this, so the exact reasons for this are clearer:

    MOZ_ASSERT(protoProto->staticPrototypeIsImmutable(),
               "protoProto should be Object.prototype, whose prototype is "
               "immutable");
    MOZ_ASSERT(protoProto->staticPrototype() == nullptr,
               "Object.prototype must have null prototype");

I somewhat prefer the immutable-prototype assert first -- so few objects have this property, that encountering one semi-naturally suggests Object.prototype is being encountered, and that makes the second assert more expected, when reading the code.

@@ +1502,5 @@
> +    return true;
> +}
> +
> +static JSProtoKey
> +GetInitialShapeProtoKey(ExclusiveContext* cx, TaggedProto proto)

GetInitialShapeProtoKey(TaggedProto proto, ExclusiveContext* cx)

since this is infallible.

@@ +1506,5 @@
> +GetInitialShapeProtoKey(ExclusiveContext* cx, TaggedProto proto)
> +{
> +    if (proto.isObject() && proto.toObject()->hasStaticPrototype()) {
> +        GlobalObject* global = cx->global();
> +        JSObject* obj = proto.toObject();

With the IsOriginalProto signature changes, this should be a reference.

@@ +1548,4 @@
>      Rooted<TaggedProto> protoRoot(cx, proto);
> +    Shape* shape = nullptr;
> +    bool insertKey = false;
> +    mozilla::Maybe<DependentAddPtr<decltype(Zone::initialShapes)>> keyPointer;

I'd prefer decltype(cx->zone().initialShapes) because it documents exactly where this ethereal zone actually is found, and because I'm very slightly dubious (tho it's probably tilting at windmills) of decltype on static members being portable across all our compilers.

@@ +1552,2 @@
>  
> +    JSProtoKey key = GetInitialShapeProtoKey(cx, proto);

Using |proto| after having rooted it seems pretty dubious, or at least bad form.

@@ +1573,5 @@
> +        if (!shape)
> +            return nullptr;
> +    }
> +
> +    Lookup::ShapeProto shapeProto(protoRoot.get());

You're sure the .get() is necessary here?

@@ +1651,5 @@
>  #endif
>  
>      entry.shape = ReadBarrieredShape(shape);
>  
> +    JSProtoKey key = GetInitialShapeProtoKey(cx, TaggedProto(proto));

This block could use an explanatory comment by it, something like

"""
For certain prototypes -- namely, those of various builtin classes, keyed by JSProtoKey |key| -- there are two entries: one for a lookup via |proto|, and one for a lookup via |key|.  If this is such a prototype, also update the alternate |key|-keyed shape.
"""

Assuming I understand the ideas of any of this patch correctly and have correctly described it with not-incorrect descriptive text, that is.

I'd also like to see a comment like this tacked onto existing documentation somewhere more central, too, like by Zone::initialShapes's declaration.

@@ +1695,5 @@
>          shape->updateBaseShapeAfterMovingGC();
>  
>          // If the prototype has moved we have to rekey the entry.
>          InitialShapeEntry entry = e.front();
> +        if (entry.proto.proto().isObject() && IsForwarded(entry.proto.proto().toObject())) {

Aren't you missing two .proto() in both of these?

::: js/src/vm/Shape.h
@@ +1110,5 @@
> +    }
> +    template <typename T>
> +    bool match(const InitialShapeProto<T>& other) const {
> +        return key_ == other.key_ &&
> +               proto_.uniqueId() == other.proto_.unbarrieredGet().uniqueId();

I don't think I understand barriers enough to say that unbarrieredGet() is right here versus barriered get.  Find someone else to review this one weird line.

Comment 11

[Michael Smith [:mismith] (non-bmo mail: [e-mail])]

(In reply to Jan de Mooij [:jandem] from comment #8)
> Michael, this doesn't conflict with your work, right? I don't think it does,
> but just want to make sure you're aware of it.

Thanks for the heads up. On first read I don't think it does, but I'll give it a more thorough look tomorrow.

Comment 12

[Jan de Mooij [:jandem]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #10)
> > +        return key_ == other.key_ &&
> > +               proto_.uniqueId() == other.proto_.unbarrieredGet().uniqueId();
> 
> I don't think I understand barriers enough to say that unbarrieredGet() is
> right here versus barriered get.  Find someone else to review this one weird
> line.

This line I just moved from InitialShapeEntry::match, that function currently has:

  && lookup.proto.uniqueId() == key.proto.unbarrieredGet().uniqueId();

I rechecked with jonco on IRC, and it's safe to use unbarrieredGet here because the result doesn't escape, we're just doing an equality check.

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/82a35fbc660a
Share more shapes across compartments. r=Waldo

Comment 14

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/82a35fbc660a