(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...

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"?

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.

(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.

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.

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.

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.

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.

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.

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

(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

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.

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?

(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.

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,

(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.

I should take this probably.

Rebasing in progress

Continue rebasing patches.

Moving along with updating this patch set. The original Part 4 has already been integrated into CacheIR, so I'm dropping it from here.

Is this fixed now?

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..)