Closed Bug 1288881 Opened 8 years ago Closed 6 years ago

Handling of hasUncacheableProto produces incorrect results in GetProperty caches

Categories

(Core :: JavaScript Engine: JIT, defect, P3)

defect

Tracking

()

RESOLVED FIXED
mozilla60
Tracking Status
firefox-esr52 --- wontfix
firefox58 --- wontfix
firefox59 --- wontfix
firefox60 --- fixed

People

(Reporter: mismith, Assigned: mismith, Mentored)

References

Details

(Keywords: sec-audit, Whiteboard: [post-critsmash-triage][adv-main60-])

Attachments

(9 files, 16 obsolete files)

842 bytes, text/plain
Details
5.99 KB, patch
jandem
: review+
Details | Diff | Splinter Review
65.75 KB, patch
Details | Diff | Splinter Review
1.85 KB, patch
shu
: review+
Details | Diff | Splinter Review
966 bytes, patch
efaust
: review+
Details | Diff | Splinter Review
5.11 KB, patch
Details | Diff | Splinter Review
15.83 KB, patch
Details | Diff | Splinter Review
72.17 KB, patch
Details | Diff | Splinter Review
3.33 KB, patch
Details | Diff | Splinter Review
Attached file Test case (test.js) (obsolete) —
(On :Waldo's advice, I'm filing this bug as hidden initially.)

The attached test case demonstrates a correctness issue in the handling of the hasUncacheableProto flag in generated GetProperty cache stubs

When an object's prototype is changed, SetClassAndProto sets this flag on that object, if it is not a singleton, and on every non-singleton objects along the prototype chain, stopping when it hits the first non-native object in the chain. The object is reshaped the first time the flag is set. Subsequent prototype changes will skip over objects with this flag already set, but all objects in the chain will still be processed -- it does not stop propagation.

The flag's name is a bit misleading. It implies that prototype field of the object cannot be cached, which is true. The cache generation code in SharedIC/BaselineIC, IonMonkey, and CacheIR all follow this interpretation, traversing the prototype chain and emitting prototype guards for all objects with hasUncacheableProto set, stopping *before* the holder object is checked. This is insufficient, however, as the presence of this flag on the holder object invalidates an invariant that the caches rely on, that prototype changes below the holder in the prototype chain will propagate up and reshape the holder.

Consider the following prototype chain:



    +-----+
    |     |
x1  | a:1 |  (shape = 0x3, non-singleton, "uncacheable proto")
    |     |
    +--^--+
       |
    +--+--+
    |     |
x2  |     |  (shape = 0x2, singleton)
    |     |
    +--^--+
       |
    +--+--+
    |     |
x3  |     |  (shape = 0x1, singleton)
    |     |
    +-----+



When a cache generator encounters |x3.a|, it will guard that the property id is "a", guard on the shape of x3, guard on the shape of x1, and emit a slot read from |x1.a|. It will check hasUncacheableProperty on x3 and x2, but *not* on the holder of the property, x1, and thus will emit no prototype guards.

After |x3.__proto__ = {a:2}|, the prototype chain will become:



    +-----+
    |     |
x1  | a:1 |  (shape = 0x3, non-singleton, "uncacheable proto")
    |     |
    +--^--+
       |
    +--+--+
    |     |
x2  | a:2 |  (shape = 0x4, singleton)
    |     |
    +--^--+
       |
    +--+--+
    |     |
x3  |     |  (shape = 0x1, singleton)
    |     |
    +-----+



Note that x2 was reshaped but x1 was not, due to hasUncacheableProto having already been set on x1. |x3.a| *should* now return 2, read from |x2.a|. But the previously-generated cache stub will check that the id is "a" (yes), x3's shape is still 0x3 (yes), and then read 1 from |x1.a|. This is incorrect behavior. Fortunately, we do avoid a use-after-free issue as the GC keeps any pointer referenced by generated JitCode alive.

Running the attached test case with |js test.js| will produce input like the following (assuming js is built with DEBUG enabled):



===== x0 =====
object 0x7fac36278120 from global 0x7fac36276060 [global]
class 0x1645780 Object
flags: delegate new_type_unknown inDictionaryMode hasShapeTable
proto <Object at 0x7fac36278040>
properties:

===== x1 =====
object 0x7fac36277280 from global 0x7fac36276060 [global]
class 0x1645780 Object
flags: has_uncacheable_proto
proto <Object at 0x7fac36278120>
properties:
    ((js::Shape*) 0x7fac36298268) enumerate JSString* (0x7fac36200940) = Latin1Char * (0x7fac36200948) = "a"
: slot 0 = 1

===== x2 =====
object 0x7fac36278140 from global 0x7fac36276060 [global]
class 0x1645780 Object
flags: delegate inDictionaryMode hasShapeTable
proto <Object at 0x7fac36277280>
properties:

===== x3 =====
object 0x7fac36278160 from global 0x7fac36276060 [global]
class 0x1645780 Object
flags: inDictionaryMode hasShapeTable
proto <Object at 0x7fac36278140>
properties:

result: pass



Here, "result: pass" indicates that the read from |x3.a| produced the expected result, because the JIT and caches did not activate. Forcing Baseline (js --baseline-eager --no-ion test.js) or IonMonkey (js --ion-eager --ion-shared-stubs=off --no-threads test.js) to activate and generate caches will produce an incorrect result, printing "result: fail" as the last line.

Patches to follow...
Assignee: nobody → mismith
Status: NEW → ASSIGNED
Adding a debug option to js-shell to test without CacheIR enabled. Not essential.
Here is the fix for the correctness issue in the JIT cache generators. I've left extensive comments as this was a hairy issue to track down. I could probably have merged the versions of GeneratePrototypeGuards in IonCaches.cpp and CacheIR.cpp, but since that would require introducing some sort of new abstraction and CacheIR will eventually replace IonCaches anyway, I kept them separate.

There are other places in the code where hasUncacheableProto is handled incorrectly, but I don't believe any are correctness issues, just unnecessary checks or not being as efficient as we could be. I will follow up with an additional patch to address those.

Finally, I believe "hasUncacheableProto" should be given a better name, but I'm not sure exactly what it should be - something like "protoChainReshapingDisabled"?
Flags: needinfo?(jdemooij)
Flags: needinfo?(efaustbmo)
Attachment #8774007 - Flags: review?(jdemooij)
Attachment #8774007 - Flags: review?(efaustbmo)
I'd also like to integrate the test case into the jit-tests, but I don't know how to ensure it'll get run with both |--baseline-eager --no-ion| and |--ion-eager --ion-shared-stubs=off --no-threads| to fully test it.
CCing a few interested parties. Also setting Core JS sec so we can get this twiddled properly when we can.
Group: javascript-core-security
(In reply to Michael Smith [:mismith] from comment #4)
> I'd also like to integrate the test case into the jit-tests, but I don't
> know how to ensure it'll get run with both |--baseline-eager --no-ion| and
> |--ion-eager --ion-shared-stubs=off --no-threads| to fully test it.

The tests get run with the --tbpl flag on treeherder. That flag enables the following 7 configurations:

https://dxr.mozilla.org/mozilla-central/source/js/src/tests/lib/tests.py#15-23

You can add a flag for a specific test by adding a header to the test like:
// |jit-test| --ion-shared-stubs=off
The security implications aren't clear to the triage team. We're going to call this "sec-audit" and not worry about it too much because there's a patch and it looks well on its way to being fixed anyway.

If this is a bad security problem that needs to be fixed on earlier branches please clear the sec-audit keyword with an explanation so we can re-rate it and make sure it gets backported as necessary.
Keywords: sec-audit
Group: core-security
Hi Daniel,

I don't believe it truly poses a security issue, but at the time it smelled like something that could potentially be one, since it involves generated native code accessing the wrong area of memory. However, the GC should always be keeping the object alive while it's referenced from a JIT stub, mitigating a use-after-free.

We marked this as hidden just in case until it can get a closer review from someone with more experience in this subsystem.
Flags: needinfo?(jdemooij)
Flags: needinfo?(efaustbmo)
Status: I've since found other issues in this area and am working on a better solution / overhaul of how we handle proto chain reshaping.
Attachment #8774007 - Attachment is obsolete: true
Attachment #8774007 - Flags: review?(jdemooij)
Attachment #8774007 - Flags: review?(efaustbmo)
Comment on attachment 8774004 [details] [diff] [review]
Part 1: Add js-shell option to disable CacheIR stubs

I've also moved the CacheIR stub flag patch out to bug 1292659.
Attachment #8774004 - Attachment is obsolete: true
Attachment #8774004 - Flags: review?(jdemooij)
Okay, I've attached the seven-part patch set (phew!) that I've been working on for this. Patches 1-6 lay some groundwork and patch 7 is the one that directly addresses the UNCACHEABLE_PROTO issue.

My approach is to remove UNCACHEABLE_PROTO and replace it with two mechanisms: shape lineage rewrites and a holder nonce hidden property.

When cache holder guards need to be invalidated -- when a property is shadowed or a prototype is mutated -- converting to dictionary mode and reshaping was previously the only tool we had to trigger an invalidation. UNCACHEABLE_PROTO existed to avoid the dictionary mode conversion by reshaping via a flag set; the idea was that the inline caches would then see this flag and generate extra prototype guards where necessary. However, as it turns out, handling that guard generation both correctly and efficiently is quite difficult and convoluted. Also, other parts of the engine depend on the (currently incorrect) assumption that an object's shape determines its prototype. Tracking down and auditing these instances is hard, and I've come to the conclusion that it would be better to simply make that assumption correct again.

So, step 1: in SetClassAndProto, for the object whose prototype is directly mutated, replace its shape lineage with the lineage it would have been given if its original prototype had been the new prototype. This is generalized from (and subsumes) the mechanism in ReshapeForAllocKind, which finds the initialShape corresponding to the new class and prototype and then attaches the correct shape for each object property. At worst this is equivalent to a dictionary mode conversion, which currently always happens for singletons. For non-singletons, subsequent prototype changes on similar objects will reuse the cached immutable shapes from the shape tree, making this more efficient.

Step 2 is to invalidate holder guards on all upstream objects in the prototype chain without resorting to dictionary mode conversions. I iterated through several alternative approaches to this problem: adding group guards on everything, adding a new "cloned" shape type, adding a mechanism similar to TaggedProto for shapes. The solution I've arrived on is to attach a hidden "nonce" or generation count property to objects whose holder guards need to be invalidated. This first causes the object's shape to change, invalidating stubs which guarded on its shape in the same way that UNCACHEABLE_PROTO does. But instead of an arbitrarily-long series of prototype guards, subsequently-generated caches which guard on this object as a holder only need to emit a single extra check on the object's hidden nonce property. When an object's holder guards need to be invalidated for a second time and beyond, the nonce property value is simply incremented. This mechanism can support up to 2^63 holder guard invalidations per object, at which point the object is simply converted to dictionary mode. (For reference, telemetry data indicates most compartments either experience 0 or 2 prototype mutations within their lifetime: https://telemetry.mozilla.org/new-pipeline/dist.html#!cumulative=0&end_date=2016-08-02&keys=__none__!__none__!__none__&max_channel_version=beta%252F49&measure=SIMPLE_MEASURES_JS_SETPROTO&min_channel_version=null&product=Firefox&sanitize=1&sort_keys=submissions&start_date=2016-08-02&table=0&trim=1&use_submission_date=0)

In addition to replacing the UNCACHEABLE_PROTO mechanism, I've also used this to replace shadowingShapeChange which required a dictionary mode conversion on any object with a property that became shadowed downstream on a prototype chain.

At the moment this eats a bit of a decrease in the Octane gbemu score. This is because the Baseline ICs are temporarily set to not generate caches for any prototype chain containing an object with a holder nonce. Commenting that bit out eliminates the Octane regression, and after receiving feedback on this approach I can go back and add support for this to all the Baseline caches. This should end up being a performance win in the end, especially as we save on dictionary mode conversions from shadowing shape changes.
Flags: needinfo?(jdemooij)
Flags: needinfo?(efaustbmo)
Attachment #8785062 - Flags: review-
Comment 19 is private: false
Rebasing to keep up with the frontend changes that just landed...
Comment on attachment 8785500 [details] [diff] [review]
Part 1: Add mechanism to store up to 48 bits of private data in a Value

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

Remove setRawBits and RawValue from this patch and r=nbp.

::: js/public/Value.h
@@ +928,5 @@
> +    jsval_layout l;
> +
> +    // On 64-bit platforms, we can simply store the 48-bit uint directly without
> +    // risking tag confusion.
> +    l.asBits = ui;

nit: On an optimized build, nothing would prevent us from forging JS Values.  I suggest to either zero the upper part, or use a MOZ_RELEASE_ASSERT.

I think zeroing the upper part is probably the easiest, and the most condensed asm-code-wise.

  l.asBits = ui << 16 >> 16;

@@ +1353,5 @@
>      uint64_t asRawBits() const {
>          return data.asBits;
>      }
> +    void setRawBits(uint64_t bits) {
> +        data.asBits = bits;

Remove this function, as well as RawValue(uint64_t).
I would prefer the code in part 4 to use a cast, than adding such methods as part of JS::Value interface.
Attachment #8785500 - Flags: review?(nicolas.b.pierron) → review+
Comment on attachment 8785502 [details] [diff] [review]
Part 3: Expand coverage of Value-comparison functions in MacroAssembler

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

r+ with nits and possible ARM fun

::: js/src/jit/arm/MacroAssembler-arm.cpp
@@ +5303,5 @@
> +    } else {
> +        branch32(Assembler::NotEqual, lhs, Imm32(jv.s.payload.i32),
> +                 cond == Equal ? &done : label);
> +    }
> +    branch32(cond, Address(lhs.base, lhs.offset + sizeof(uint32_t)), Imm32(jv.s.tag), label);

NUNBOX32_TYPE_OFFSET

@@ +5318,5 @@
> +
> +    Label done;
> +
> +    if (cond == Equal)
> +        branch32(Assembler::NotEqual, lhs, rhs.payloadReg(), &done);

Because ARM has conditionally executed instructions, it is possible to write both paths (using ma_* functions) with only one branch instruction (to label). That would be faster and use less code.

If that sounds fun to you, it would be useful to implement! That same sample then likely applies in other parts of the codebase as well...

@@ +5321,5 @@
> +    if (cond == Equal)
> +        branch32(Assembler::NotEqual, lhs, rhs.payloadReg(), &done);
> +    else
> +        branch32(Assembler::NotEqual, lhs, rhs.payloadReg(), label);
> +    branch32(cond, Address(lhs.base, lhs.offset + sizeof(uint32_t)), rhs.typeReg(), label);

NUNBOX32_TYPE_OFFSET

::: js/src/jit/mips32/MacroAssembler-mips32.cpp
@@ +2227,5 @@
> +
> +    ScratchRegisterScope scratch(*this);
> +    moveData(rhs, scratch);
> +
> +    Address lhsTag(lhs.base, lhs.offset + sizeof(uint32_t));

NUNBOX32_TYPE_OFFSET

@@ +2255,5 @@
> +    if (cond == Equal)
> +        branch32(Assembler::NotEqual, lhs, rhs.payloadReg(), &done);
> +    else
> +        branch32(Assembler::NotEqual, lhs, rhs.payloadReg(), label);
> +    branch32(cond, Address(lhs.base, lhs.offset + sizeof(uint32_t)), rhs.typedReg(), label);

NUNBOX32_TYPE_OFFSET (for some reason mips32 uses TAG_OFFSET, but they're the same thing.)

::: js/src/jit/x64/MacroAssembler-x64.cpp
@@ +600,5 @@
> +    ScratchRegisterScope scratch(*this);
> +    MOZ_ASSERT(lhs.base != scratch);
> +    moveValue(rhs, scratch);
> +    cmpPtr(lhs, scratch);
> +    j(cond, label);

Above two instructions normally written as branchPtr(). j() is pretty rare.

::: js/src/jit/x86/MacroAssembler-x86.cpp
@@ +506,5 @@
> +        cmpPtr(lhs, ImmGCPtr(reinterpret_cast<gc::Cell*>(rhs.toGCThing())));
> +    else
> +        cmpPtr(lhs, ImmWord(jv.s.payload.i32));
> +
> +    Address lhsTag(lhs.base, lhs.offset + sizeof(uint32_t));

NUNBOX32_TYPE_OFFSET

@@ +509,5 @@
> +
> +    Address lhsTag(lhs.base, lhs.offset + sizeof(uint32_t));
> +    if (cond == Equal) {
> +        Label done;
> +        j(NotEqual, &done);

Is there any way to move this j() in with the cmpPtr()s above, so we can use branchPtr()?

@@ +512,5 @@
> +        Label done;
> +        j(NotEqual, &done);
> +        {
> +            cmp32(lhsTag, Imm32(jv.s.tag));
> +            j(Equal, label);

branch32()

@@ +519,5 @@
> +    } else {
> +        j(NotEqual, label);
> +
> +        cmp32(lhsTag, Imm32(jv.s.tag));
> +        j(NotEqual, label);

branch32()

@@ +536,5 @@
> +    if (cond == Equal)
> +        branch32(Assembler::NotEqual, lhs, rhs.payloadReg(), &done);
> +    else
> +        branch32(Assembler::NotEqual, lhs, rhs.payloadReg(), label);
> +    branch32(cond, Address(lhs.base, lhs.offset + sizeof(uint32_t)),

NUNBOX32_TYPE_OFFSET
Attachment #8785502 - Flags: review?(sstangl) → review+
(In reply to Michael Smith [:mismith] from comment #18)

General approach SGTM, thanks for working on this. The nonce thing is elegant and I like it more than the original TaggedProto-inspired idea.

> This mechanism can support up to 2^63 holder guard invalidations per object, at
> which point the object is simply converted to dictionary mode.

So this became 2^48 now? I think I would have gone with Int32Value or maybe DoubleValue, so you can represent integers up to Number.MAX_SAFE_INTEGER [0] (2^53 - 1, an even bigger space than 2^48), without changing Value.h. Am I missing something?

[0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER
Flags: needinfo?(jdemooij)
Comment on attachment 8785503 [details] [diff] [review]
Part 4: Extend CacheIR to support 64-bit fields, including Value fields

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

Nice.

::: js/public/Value.h
@@ +262,5 @@
>          JSValueTag tag;
>      } s;
>      double asDouble;
>      void* asPtr;
> +    MOZ_IMPLICIT jsval_layout(long unsigned int bits) : asBits(bits) {}

I'd make this |explicit| instead of MOZ_IMPLICIT, it's not used that much and when it is used, it's in code where I'd prefer seeing the explicit conversions.

Also, "long unsigned int" is confusing, just use |uint64_t bits|, it's shorter and clearer.

::: js/src/jit/BaselineCacheIR.cpp
@@ +1262,5 @@
>  jit::TraceBaselineCacheIRStub(JSTracer* trc, ICStub* stub, const CacheIRStubInfo* stubInfo)
>  {
>      uint32_t field = 0;
> +    size_t offset = 0;
> +    StubField::FieldType fieldType;

Nit: move fieldType inside the loop, StubField::FieldType fieldType = ...;

::: js/src/jit/CacheIR.h
@@ +124,3 @@
>          Limit
>      };
> +    static const FieldType First64BitField = FieldType::RawUint64;

Nit: I'd add it to the enum:

  First64BitField = RawUint64,

When someone adds a new enum value, that also makes it more obvious they have to change this value as well.

@@ +134,3 @@
>  
> +    static inline uint8_t fieldSize(FieldType fieldType) {
> +        return isWord(fieldType) ? 1 : sizeof(uint64_t) / sizeof(uintptr_t);

Nit: put parens around the division so there's no room for confusion about the precedence.
Attachment #8785503 - Flags: review?(jdemooij) → review+
Attachment #8785505 - Flags: review?(jdemooij) → review+
I am impressed by this bug.
Comment on attachment 8785507 [details] [diff] [review]
Part 8: Make LexicalEnvironmentObject::clone aware of holder nonces

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

::: js/src/vm/EnvironmentObject.cpp
@@ +976,5 @@
> +    // that |copy| has the same shape. And it may have given it an additional
> +    // holder nonce property which |copy| won't have room for, so we stop
> +    // copying slots at the environment shape's slot.
> +    uint32_t lastSlot = env->scope().environmentShape()->slot();
> +    MOZ_ASSERT(lastSlot + 1 == copy->slotSpan());

Maybe also assert that env's slotSpan() >= copy->slotSpan(). Where is the nonce kept? Does it count as a slotful property or something?
Attachment #8785507 - Flags: review?(shu) → review+
(In reply to Jan de Mooij [:jandem] from comment #32)
> > This mechanism can support up to 2^63 holder guard invalidations per object, at
> > which point the object is simply converted to dictionary mode.
> 
> So this became 2^48 now? I think I would have gone with Int32Value or maybe
> DoubleValue, so you can represent integers up to Number.MAX_SAFE_INTEGER [0]
> (2^53 - 1, an even bigger space than 2^48), without changing Value.h. Am I
> missing something?

Yes, see comment 19.
(In reply to Nicolas B. Pierron [:nbp] from comment #36)
> Yes, see comment 19.

I don't see how that's related. I'm just suggesting to store a DoubleValue, similar to how we store JS numbers.
Priority: -- → P3
Attachment #8785509 - Flags: review?(efaustbmo) → review+
Comment on attachment 8785504 [details] [diff] [review]
Part 5: Add flag for properties thrown away on dictionary mode conversion

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

OK, I believe this, I think,
Attachment #8785504 - Flags: review?(efaustbmo) → review+
(In reply to Jan de Mooij [:jandem] from comment #33)
> Also, "long unsigned int" is confusing, just use |uint64_t bits|, it's
> shorter and clearer.

Oops, thanks. Not sure how that slipped in there.

(In reply to Shu-yu Guo [:shu] from comment #35)
> Maybe also assert that env's slotSpan() >= copy->slotSpan().

Okay, I'll add that in.

(In reply to Shu-yu Guo [:shu] from comment #35)
> Where is the nonce kept? Does it count as a slotful property or something?

Yes, the nonce consumes one of the object's slots. Its key is a symbol that is only accessible to engine internals.(In reply to Jan de Mooij [:jandem] from comment #32)
> (In reply to Michael Smith [:mismith] from comment #18)

> So this became 2^48 now? I think I would have gone with Int32Value or maybe
> DoubleValue, so you can represent integers up to Number.MAX_SAFE_INTEGER [0]
> (2^53 - 1, an even bigger space than 2^48), without changing Value.h. Am I
> missing something?

Nope, I just hadn't thought of doing it that way! Will give it a try.
We should get this rebased and landed, NIing myself as a reminder to figure out who to best do that. Volunteers welcome, of course.
Flags: needinfo?(shu)
I should take this probably.
Flags: needinfo?(shu)
Flags: needinfo?(jdemooij)
Flags: needinfo?(efaustbmo)
Moving along with updating this patch set. The original Part 4 has already been integrated into CacheIR, so I'm dropping it from here.
Attachment #8785503 - Attachment is obsolete: true
Attachment #8785504 - Attachment is obsolete: true
Flags: needinfo?(jdemooij)
Is this fixed now?
Flags: needinfo?(tcampbell)
The sec bug is fixed in Nightly (FF 60) due to Bug 1438086. I think it can just ride the trains. This issue doesn't lead to any type confusion, just stale prototype links.

On the other hand, there is some interesting work here to explore for around shape teleporting alternatives that I don't want to lose. I'm going to close this as fixed, but leave a ni? for myself to come by in the future and create a new bug to experiment with the ideas. (I also have a couple other alternatives in mind to try out..)
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla60
Group: javascript-core-security → core-security-release
Flags: needinfo?(tcampbell)
Flags: qe-verify-
Whiteboard: [post-critsmash-triage]
Whiteboard: [post-critsmash-triage] → [post-critsmash-triage][adv-main60-]
Group: core-security-release
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: