364657 - js_Get/SetProperty()'s sprop local not GC safe.

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Johnny Stenback (:jst)]

This came out of my investigation into bug 337716 which looks like a crash bug due to JS objects being GC'd while we're using them. But after hacking around that problem I then ran into this problem which is that I hit an assertion in OBJ_CHECK_SLOT() from js_SetProperty(). The assertion is about us setting a property past the end of the allocated slots. This happens when setting the "location" property of an iframe's global object which can trigger JS_ClearScope() on the object and then also trigger the GC which can reclaim the JSScopeProperty in question. When this happens, the local JSScopeProperty pointer in the js_SetProperty() on the stack is no longer valid and once we unroll and try to use the sprop local we'll either touch deleted memory, or re-initialized memory as it is in the cases I've been able to catch in the debugger.

Brendan claims js_GetProperty() suffers from the same problem too. Marking security sensitive as this can potentially be used to reference deleted memory.

Comment 1

[Brendan Eich [:brendan]]

Painful. Forgot about a getter or setter calling JS_ClearScope on the object in question (a window, they're they only kind clear-scoped) and then forcing a GC.

/be

Comment 2

[Brendan Eich [:brendan]]

Attachment: fix, v1

Johnny, please test and feel free to review.  I open coded the fix and expanded js_GetProperty code into the interpreter a bit more, but I'd like to at least macro-ize so the rt->gcNumber sample test and sprop validation aren't cut-n-pasted all over.  But here's a patch for testing and initial review.

/be

Comment 3

[Igor Bukanov]

Comment on attachment 249488 [details] [diff] [review]
fix, v1

Where is the code to increase gcNumber? 

Another suggestion is to read the counter when the object is locked. Although it does not matter due to cooperative GC, it would feel better. 

Yet another idea is to introduce a local root for sprop. That may even result in a smaller patch.

I will review the patch in details on Saturday.

Comment 4

[Brendan Eich [:brendan]]

(In reply to comment #3)
> (From update of attachment 249488 [details] [diff] [review] [edit])
> Where is the code to increase gcNumber? 

Already there:

$ grep -n gcNumber jsgc.c
2871:    rt->gcNumber++;

> Another suggestion is to read the counter when the object is locked. Although
> it does not matter due to cooperative GC, it would feel better. 

I want to minimize critical sections.  The request model guarantees that the GC is not racing with any request, and can only nest on the current thread's stack.  And object locks are many and cannot synchronize reads and writes of the runtime-wide gcNumber member.

> Yet another idea is to introduce a local root for sprop. That may even result
> in a smaller patch.

This is not desired.  We do not want to keep the old sprop alive and use its slot, and we are not guaranteed that its slot will be invalid according to SPROP_HAS_VALID_SLOT after the JS_ClearScope and GC nesting in the getter or setter.  If we keep the old sprop alive, its slot may be in range for the new and different ordered set of properties in the object's scope, after the getter or setter has cleared that scope and repopulated it with standard properties.

We really must check both sprop == SCOPE_GET_PROPERY(scope, id) && sprop->slot == slot to be sure.  The first condition could be true even after JS_ClearScope followed by GC, if sprop's memory was recycled and mapped to the same id; the latter would be false unless the same slot was allocated to the new incarnation of sprop/id.

If both sprop == SCOPE_GET_PROPERY(scope, id) && sprop->slot == slot are true, and if SPROP_HAS_VALID_SLOT(sprop, scope), then we may as well store the fresh value in the object's slot.  Either this sprop was not collected (implying that the scope was not cleared), or it came back at the same id and slot (if not attrs, flags, and other state stored in the sprop and used as part of the hash key for rt->propertyTree), and we can't tell that sprop has been reincarnated without adding a generation number per sprop, which is a waste of space in general.

/be

Comment 5

[Brendan Eich [:brendan]]

It's true that if we had a way to root sprop local variables (otherwise not needed), we could test just sprop == SCOPE_GET_PROPERTY(scope, id) after noticing that rt->gcNumber changed, and if false, know that the slot was recycled or freed, and that we should not store the fresh value in it.

One thought I had was to allow any thread to set a SPROP_PINNED flag in sprop->flags, from any request.  Since sprops are immutable when the GC is not running, apart from certain flags (SPROP_MARK, SPROP_IS_DUPLICATE), and those flags are guaranteed to be set either by the GC (SPROP_MARK), or by the compiler which may be racing in many different threads, this seems possible.  Two issues:

1.  SPROP_IS_DUPLICATE may be set in racy fashion, but without loss of data, by two or more threads compiling the same function f(a, a) {} definition, e.g.  Adding another path that wants to set a flag is not thread-safe and could lose data.

In the present bug's case, we know that the object whose getter or setter is calling JS_ClearScope is not a function object, but sprops are shared in the property tree among different classes of object, just based on ordered set of property tree node labels (id, slot, attrs, most flags, etc.).  Still, it is unlikely that a window object could share the same sprops in an ancestor line of the property tree with a function having duplicate parameters.

2.  The get and set cases in jsinterp.c and jsobj.c would have to set and clear the flag in the runtime-shared sprop.  Setting may be safe based on the fragile reasoning about issue 1, just above.  But clearing is just not thread-safe.

So any rooting mechanism for sprops would be another ad-hoc invention such as JSTempValueRooter.  This seems unwarranted if the approach in the patch suffices.  Incrementing rt->gcNumber must be cheaper than managing another root set addition and removal, and it optimizes for the common case where the getter or setter does not JS_ClearScope.

In 1.9, soon, I would like to optimize the interpreter further, to avoid the costly (albeit short) branch-tests in the common get/set case required to handle properties with stub (null) vs. non-stub (non-null) getters and setters.  Only the latter will need to beware JS_ClearScope.  So apart from better code sharing or macrology, the approach in the patch here still seems best.  Thoughts welcome as usual.

/be

Comment 6

[Brendan Eich [:brendan]]

(In reply to comment #5)
> One thought I had was to allow any thread to set a SPROP_PINNED flag in
> sprop->flags, from any request.  Since sprops are immutable when the GC is not
> running, apart from certain flags (SPROP_MARK, SPROP_IS_DUPLICATE), and those
> flags are guaranteed to be set either by the GC (SPROP_MARK),

Of course, SPROP_MARK is set and cleared only by the GC, which runs when all requests are ended or suspended, so it's not one of the "certain flags" "apart" from which sprop flags are immutable. Only SPROP_IS_DUPLICATE may be set racily but without data loss.

> 2.  The get and set cases in jsinterp.c and jsobj.c would have to set and clear
> the flag in the runtime-shared sprop.

Another unclear wording instance: "set and clear the flag" here refers to the hypothetical SPROP_PINNED flag.

/be

Comment 7

[Igor Bukanov]

(In reply to comment #5)
> It's true that if we had a way to root sprop local variables (otherwise not
> needed), we could test just sprop == SCOPE_GET_PROPERTY(scope, id) after
> noticing that rt->gcNumber changed, and if false, know that the slot was
> recycled or freed, and that we should not store the fresh value in it.

With a temporray root for sprop GC can set a flag SPROP_DELETED to indicate that the property only survived GC due to its presence in a temporary root. Then checking for this single flag would be enough. Alternatively sprop->id can be cleared so the atom the property points to can be collected. 

Comment 8

[Igor Bukanov]

(In reply to comment #5)
> So any rooting mechanism for sprops would be another ad-hoc invention such as
> JSTempValueRooter.  This seems unwarranted if the approach in the patch
> suffices.  Incrementing rt->gcNumber must be cheaper than managing another root
> set addition and removal, and it optimizes for the common case where the getter
> or setter does not JS_ClearScope.

Why local roots are add hoc? IMO this is a proper way to tell GC that a particular GC-controlled memory is used on C stack. Given that GC can clear sprop without freeing its memory if it is in a local root, the total code size overhead would be adding/removing sprop to a linked list (3 assignments) and a check for a removed sprop. Surely it is bigger then accessing/checking the generation number, but then with the extra checks after checking for generation number  the code size is on the same scale.

Comment 9

[Igor Bukanov]

Comment on attachment 249488 [details] [diff] [review]
fix, v1

>                 JS_UNLOCK_SCOPE(cx, scope_);                                  \
>+                sample_ = rt->gcNumber;                                       \
>                 ok = SPROP_GET(cx, sprop, obj, obj, vp);                      \
>                 JS_LOCK_SCOPE(cx, scope_);                                    \
>-                if (ok && SPROP_HAS_VALID_SLOT(sprop, scope_))                \
>+                if (ok &&                                                     \
>+                    (rt->gcNumber == sample_ ||                               \
>+                     (sprop == SCOPE_GET_PROPERTY(scope_, id) &&              \
>+                      sprop->slot == slot)) &&                                \
>+                    SPROP_HAS_VALID_SLOT(sprop, scope_)) {                    \
>                     LOCKED_OBJ_SET_SLOT(obj, slot, *(vp));                    \
>+                }                                                             \

Since a full GC can happen here, that GC with a "help" of a close hook can collect id when id comes from interning a string for various elem bytecodes.

Comment 10

[Brendan Eich [:brendan]]

(In reply to comment #7)
> (In reply to comment #5)
> > It's true that if we had a way to root sprop local variables (otherwise not
> > needed), we could test just sprop == SCOPE_GET_PROPERTY(scope, id) after
> > noticing that rt->gcNumber changed, and if false, know that the slot was
> > recycled or freed, and that we should not store the fresh value in it.
> 
> With a temporray root for sprop GC can set a flag SPROP_DELETED to indicate
> that the property only survived GC due to its presence in a temporary root.

If the sprop survives GC but its ancestors do not, it will be reparented to the top  level of rt->propertyTree and possibly shared by other objects whose ordered sets of properties begin with a property matching its label (id, etc.).  Remember this is a shared, mostly-lock-free data structure.

> Then checking for this single flag would be enough. Alternatively sprop->id can
> be cleared so the atom the property points to can be collected. 

Then the sprop would have to be rehashed if it was in the top ply of the tree, or in another level that had a hash table (see bug 335700).

We should not bend the property tree code around this hard case.  The penalty should be imposed locally, on the get or set code that (a) has a real getter or setter to call; (b) notices that GC ran during the get or set.  We could refine this further to detect JS_ClearScope, since that is required for the bug to bite along with GC, but it's overkill.

/be

Comment 11

[Igor Bukanov]

(In reply to comment #8)
> (In reply to comment #5)
> > So any rooting mechanism for sprops would be another ad-hoc invention such as
> > JSTempValueRooter.  This seems unwarranted if the approach in the patch
> > suffices.  Incrementing rt->gcNumber must be cheaper than managing another root
> > set addition and removal, and it optimizes for the common case where the getter
> > or setter does not JS_ClearScope.
> 
> Why local roots are add hoc? IMO this is a proper way to tell GC that a
> particular GC-controlled memory is used on C stack. Given that GC can clear
> sprop without freeing its memory if it is in a local root, the total code size
> overhead would be adding/removing sprop to a linked list (3 assignments) and a
> check for a removed sprop. Surely it is bigger then accessing/checking the
> generation number, but then with the extra checks after checking for generation
> number  the code size is on the same scale.

For interpreter.c part of the patch the local root can be just a sprop field in JSStackFrame. Then for that part of the patch the rooting would require just 2 assigns like fp->sprop = sprop; ... fp->sprop = NULL; In fact the second clear can be skipped if GC can recognize that the frame pc does not point to GET_PROP  etc. bytecodes and ignore fp->sprop in that case.  

Comment 12

[Brendan Eich [:brendan]]

(In reply to comment #8)
> (In reply to comment #5)
> > So any rooting mechanism for sprops would be another ad-hoc invention such as
> > JSTempValueRooter.  This seems unwarranted if the approach in the patch
> > suffices.  Incrementing rt->gcNumber must be cheaper than managing another root
> > set addition and removal, and it optimizes for the common case where the getter
> > or setter does not JS_ClearScope.
> 
> Why local roots are add hoc? IMO this is a proper way to tell GC that a
> particular GC-controlled memory is used on C stack.

Because almost all gets and sets never clear scope and then GC, it is a cost that should not be imposed on every get and set that has a non-null getter or setter.

> Given that GC can clear
> sprop without freeing its memory if it is in a local root,

Not if it leaves sprop in the property tree, liable to be shared.

> the total code size
> overhead would be adding/removing sprop to a linked list (3 assignments) and a
> check for a removed sprop. Surely it is bigger then accessing/checking the
> generation number, but then with the extra checks after checking for generation
> number  the code size is on the same scale.

The code size is not the first concern -- the runtime cost imposed on every get or set in the scheme you propose is.  The patch minimizes extra checking to the very rare hard case of a clearscope+gc from a getter or setter.

The critical path must be kept short, not lengthened for a once-in-a-blue-moon bad scenario, if we can detect that scenario and cope in code that's off of the critical path.

As noted, the null (stub) getter and setter cases should be separated for even better performance.  Currently too many critical paths in SpiderMonkey have to handle all cases, including rare or just less likely ones.  We need to move away from this perf-killing architecture, not build on it.

/be

Comment 13

[Igor Bukanov]

(In reply to comment #10)
> If the sprop survives GC but its ancestors do not, it will be reparented to the
> top  level of rt->propertyTree and possibly shared by other objects whose
> ordered sets of properties begin with a property matching its label (id, etc.).
>  Remember this is a shared, mostly-lock-free data structure.

But the nature of this bug is that GC frees sprop. If sprop survives GC, then the bug can not happen, right?

My suggestion is to put sprop into a local root so GC instead of freeing its memory would put a flag like "dead" it it. Then the flag can be checked to detect the release property.

Comment 14

[Brendan Eich [:brendan]]

fp->sprop is good and minimal, but I'd still rather not mess with it.  For one thing it's two stores to issue and retire, plus whatever code is generated on account of the two assignments (synthesizing NULL, etc.).  For another, the stack frame is already too big.  Another idea for winning perf lost over the years is to split it into the minimal frame needed by functions that don't use arguments, sharp variables, etc..  Would like to avoid sprop in that minimal struct.

Again we are suffering from a hard case "tail" that is "wagging the dog".

(In reply to comment #9)
> Since a full GC can happen here, that GC with a "help" of a close hook can
> collect id when id comes from interning a string for various elem bytecodes. 

Good point, but easily fixed by storing the computed id on the stack over top of the non-string operand that was converted and interned.  New patch next.

/be

Comment 15

[Igor Bukanov]

(In reply to comment #14)
> fp->sprop is good and minimal, but I'd still rather not mess with it.og".
...
> 
> (In reply to comment #9)
> > Since a full GC can happen here, that GC with a "help" of a close hook can
> > collect id when id comes from interning a string for various elem bytecodes. 
> 
> Good point, but easily fixed by storing the computed id on the stack over top
> of the non-string operand that was converted and interned.  New patch next.

Instead of storing ID what about storing sprop itself there and teaching GC to detect it based on stored PC? Then the local root comes for free.

> 
> /be
> 

Comment 16

[Brendan Eich [:brendan]]

(In reply to comment #13)
> (In reply to comment #10)
> > If the sprop survives GC but its ancestors do not, it will be reparented to the
> > top  level of rt->propertyTree and possibly shared by other objects whose
> > ordered sets of properties begin with a property matching its label (id, etc.).
> >  Remember this is a shared, mostly-lock-free data structure.
> 
> But the nature of this bug is that GC frees sprop. If sprop survives GC, then
> the bug can not happen, right?

It's worse -- the sprop in the case jst debugged was recycled for the same object, but a different slot.

You're right that a brute force solution would protect sprop while ensuring that it is not shared via the propertyTree if collected.  That's costly enough for this odd hard case that I'd rather use a more subtle fix.  Avoiding dereferencing freed memory is not the issue if we can protect id and rehash if gcNumber changed.

/be

Comment 17

[Brendan Eich [:brendan]]

(In reply to comment #15)
> (In reply to comment #14)
> > Good point, but easily fixed by storing the computed id on the stack over top
> > of the non-string operand that was converted and interned.  New patch next.
> 
> Instead of storing ID what about storing sprop itself there and teaching GC to
> detect it based on stored PC? Then the local root comes for free.

Would require tagging sprop as jsval, and again there's no resign to generalize the fix to an unusual bug.  We don't need to stack sprops otherwise.  Protecting the computed id is probably necessary anyway, now that I look at the code: it is assuming only last-ditch (keepAtoms) GCs could nest after a computed property name has been interned but before it is used in the post-getter/setter code that stores the slot.

/be

Comment 18

[Brendan Eich [:brendan]]

(In reply to comment #17)
> Would require tagging sprop as jsval, and again there's no resign to 

Er, "reason".

/be

Comment 19

[Igor Bukanov]

(In reply to comment #17)
> now that I look at the
> code: it is assuming only last-ditch (keepAtoms) GCs could nest after

You mean that the code assumes that only the last-ditch can happen when in fact a full GC can happen?

Comment 20

[Brendan Eich [:brendan]]

Attachment: fix, v2

Comment 21

[Brendan Eich [:brendan]]

(In reply to comment #19)
> (In reply to comment #17)
> > now that I look at the
> > code: it is assuming only last-ditch (keepAtoms) GCs could nest after
> 
> You mean that the code assumes that only the last-ditch can happen when in fact
> a full GC can happen?

Indeed!  This bug brought it to light, but the CHECK_ELEMENT_ID macro and other calls that reach InternStringElementId and then call a getter or setter are all vulnerable, if the getter or setter can force a full GC.

/be

Comment 22

[Igor Bukanov]

(In reply to comment #17)
> Protecting the computed id is probably necessary anyway

The current code does not access the computed id after get_property call. But the patch needs it after a potential getter/setter for checking the property so the patch has to either protect the id or regenerate it from the original jsval. 

Comment 23

[Igor Bukanov]

>    if (n < 0 && ATOM_KEY(atom) != idval)
>        cx->fp->sp[n] = ATOM_KEY(atom);

But that would protect the string key, not the atom itself. Thus the atom still  can be removed from all the properties in a close hook.  

Comment 24

[Brendan Eich [:brendan]]

(In reply to comment #22)
> (In reply to comment #17)
> > Protecting the computed id is probably necessary anyway
> 
> The current code does not access the computed id after get_property call.

Right, as far as I can see.  Still hanging by a thread, but no pre-existing hazard.

> But
> the patch needs it after a potential getter/setter for checking the property so
> the patch has to either protect the id or regenerate it from the original
> jsval.

Regenerate, sigh.

/be

Comment 25

[Brendan Eich [:brendan]]

(In reply to comment #24)
> Regenerate, sigh.

Note that this is only for the harder case of computed element id.  The JOF_NAME and JOF_PROP opcodes do not need to protect atom, as it's protected by the current script's atomPool.  The JOF_ELEM case where the element id is an int also needs no special care.

Still want to minimize cost to the normal get/set case.

/be

Comment 26

[Brendan Eich [:brendan]]

Igor, great to have you here to exchange comments with :-).

I've been focusing on jsinterp.c, but the jsobj.c code in the patch can't tell whether its id parameter was computed.  In general such code (JSObjectOps method implementations) require callers to protect GC-able data structures passed via jsid and other types.  We'll have to look at jsapi.c to make sure this is the case; it may not be.

Having to root atoms in LIFO fashion during API calls will be a big change.  Lots of code assumes atoms are safe due to the last ditch GC not collecting them.  But getters and setters can force a full GC.  This is a problem for more code than what the current patch touches.

/be

Comment 27

[Igor Bukanov]

(In reply to comment #26)
> Having to root atoms in LIFO fashion during API calls will be a big change. 
> Lots of code assumes atoms are safe due to the last ditch GC not collecting
> them.  But getters and setters can force a full GC.  This is a problem for more
> code than what the current patch touches.

What about just disabling collecting sprop and atoms during getter/setter invocation as a temporary measure? 

Comment 28

[Brendan Eich [:brendan]]

(In reply to comment #27)
> (In reply to comment #26)
> > Having to root atoms in LIFO fashion during API calls will be a big change. 
> > Lots of code assumes atoms are safe due to the last ditch GC not collecting
> > them.  But getters and setters can force a full GC.  This is a problem for more
> > code than what the current patch touches.
> 
> What about just disabling collecting sprop and atoms during getter/setter
> invocation as a temporary measure? 

Yeah, I was just gonna say that.  Much simpler, but it will penalize some getter and setter calls.  I hope only the calls to real JS functions (where the sprop has JSPROP_GETTER or JSPROP_SETTER in its attrs).  The truly-native JSPropertyOp getters and setters should not force a full GC.  In other words, elevate and then drop a cx->inGetOrSet counter only in js_InternalGetOrSet.

If we can make this rule stick we can keep some paths fast.

jst, was the setter in question a JSPropertyOp-signature one, or a JSNative one flagged by JSPROP_SETTER in sprop->attrs?

/be

Comment 29

[Brendan Eich [:brendan]]

(In reply to comment #28)
> jst, was the setter in question a JSPropertyOp-signature one, or a JSNative one
> flagged by JSPROP_SETTER in sprop->attrs?

I meant "or a JSObject one" -- JSPROP_SETTER in sprop->attrs means sprop->setter is of type (JSObject *), pointed to a native or interpreted function object.

/be

Comment 30

[Igor Bukanov]

(In reply to comment #28)
> but it will penalize some
> getter and setter calls.  I hope only the calls to real JS functions (where the
> sprop has JSPROP_GETTER or JSPROP_SETTER in its attrs).  The truly-native
> JSPropertyOp getters and setters should not force a full GC.

For debugging purposes it should be enforced through an assert. That is, no interpreter nesting or (maybe) GC calls should be allowed from a native getter. In fact, it would be nice to have such enforcement code in an optimized build for a while to ensure test coverage.

Comment 31

[Brendan Eich [:brendan]]

Attachment: alterna-fix as suggested

I think __GNUC__ will give us enough coverage (Mac OS X, Linux).  If you like this patch, I'll put it in a cover bug and land it.

/be

Comment 32

[Igor Bukanov]

Comment on attachment 249528 [details] [diff] [review]
alterna-fix as suggested

>+    js_SweepScopeProperties(rt, cx->inGetOrSetLevel != 0);

sprop collection should be disabled if inGetOrSetLevel != 0 in any context. r+ with that fixed.

Comment 33

[Igor Bukanov]

(In reply to comment #32)
> (From update of attachment 249528 [details] [diff] [review] [edit])
> >+    js_SweepScopeProperties(rt, cx->inGetOrSetLevel != 0);
> 
> sprop collection should be disabled if inGetOrSetLevel != 0 in any context. r+
> with that fixed. 

Which raises a question: what is better, per context counter with a faster code or a per runtime counter using atomic_increment with a smaller JSContext?

Comment 34

[Brendan Eich [:brendan]]

(In reply to comment #33)
> (In reply to comment #32)
> > (From update of attachment 249528 [details] [diff] [review] [edit] [edit])
> > >+    js_SweepScopeProperties(rt, cx->inGetOrSetLevel != 0);
> > 
> > sprop collection should be disabled if inGetOrSetLevel != 0 in any context. r+
> > with that fixed. 
> 
> Which raises a question: what is better, per context counter with a faster code
> or a per runtime counter using atomic_increment with a smaller JSContext?

GC can nest on the current request only when other threads end or suspend their requests.  If we do not allow suspending from within a getter or setter function, we don't need to check other contexts' inGetOrSetLevel.

/be

Comment 35

[Igor Bukanov]

(In reply to comment #34)
> GC can nest on the current request only when other threads end or suspend their
> requests.  If we do not allow suspending from within a getter or setter
> function, we don't need to check other contexts' inGetOrSetLevel.

Here is a scenario: thread A executes a full GC in a getter. That triggers a close hook which allocates a lot of garbage and shows an alert or other activity that suspends the current thread.  Then another thread calls GC.

In fact, one do not need many threads since a close hook can run arbitrary code. So to defeat the sprop/atom protection in FF the hook would just need to call code that causes allocation of nested JSContext.

Comment 36

[Johnny Stenback (:jst)]

Fix v1 does fix the problem I was seeing, but the alterna-fix patch gives me a JS assert when running my testcase. The assert is

Assertion failure: cx->inNativeGetOrSetLevel == 0, at ../../../mozilla/js/src/jsapi.c:1909

cx-inNativeGetOrSetLevel is 2 in my case.

Comment 37

[Brendan Eich [:brendan]]

(In reply to comment #36)
> Fix v1 does fix the problem I was seeing, but the alterna-fix patch gives me a
> JS assert when running my testcase. The assert is
> 
> Assertion failure: cx->inNativeGetOrSetLevel == 0, at
> ../../../mozilla/js/src/jsapi.c:1909
> 
> cx-inNativeGetOrSetLevel is 2 in my case.

What's on the stack, top 10 frames or so (at least to the native getter or setter that's bumped cx->inNativeGetOrSetLevel to 2 -- would be good to see the entire stack to find who bumped it to 1)?

/be

Comment 38

[Johnny Stenback (:jst)]

Attachment: Complete stack for the assertion.

Comment 39

[Brendan Eich [:brendan]]

Attachment: better fix

Igor's good suggestion of a rooting mechanism combined with common subroutining and fast-path special casing, plus important fixes to mark sprop->id when marking sprop (the macrology was bogus; see new MARK_ID called from MARK_SCOPE_PROPERTY).

Mac OS X gcc 4.0.1 -Os non-JS_THREADSAFE build shows 1968 byte reduction with this patch.

/be

Comment 40

[Brendan Eich [:brendan]]

Attachment: better fix, v2

Tighten up conditioning and add assertion for LOCKED_OBJ_SET_SLOT after getter or setter call-out.

/be

Comment 41

[Brendan Eich [:brendan]]

Attachment: better fix, v2a

Couple of bogus (uintN) casts crept in somehow.

/be

Comment 42

[Brendan Eich [:brendan]]

jst, lemme know if this doesn't cure all ills.

/be

Comment 43

[Igor Bukanov]

Comment on attachment 250183 [details] [diff] [review]
better fix, v2a

>+typedef struct JSTempSpropRooter {
>+    JSTempValueRooter   base;
>+    JSScopeProperty     *sprop;
>+} JSTempSpropRooter;

A quick observation before a full review. Why not to use JSTempSpropRooter.count == -3 for sprop? In this way copying js_TempSpropMarker to the stack would be avoided and GC can call MARK_SCOPE directly.

Comment 44

[Brendan Eich [:brendan]]

Attachment: better fix, v2b

Why not indeed?  Also #defined the magic negative count values.

/be

Comment 45

[Brendan Eich [:brendan]]

Attachment: better fix, v3

The JSScopeProperty marking code was still incorrectly factored.

/be

Comment 46

[Brendan Eich [:brendan]]

Attachment: better fix, v3a

English nit-picking in recent change, plus vim modelines.

/be

Comment 47

[Brendan Eich [:brendan]]

Attachment: better fix, v4

jst's testing showed that we can't just sample and compare rt->gcNumber -- we really do need a scope generation number (or aggregated proxy, but there's spare space in JSScope for a per-scope counter).

/be

Comment 48

[Johnny Stenback (:jst)]

Comment on attachment 250236 [details] [diff] [review]
better fix, v4

This one I haven't been able to make crash or assert yet. Looks good so far!

Comment 49

[Brendan Eich [:brendan]]

Note how scope->generation is *not* incremented by js_RemoveScopeProperty, only by js_ClearScope. This is safe because we never free slots -- a known design flaw that can lead to asymptotic slots vector growth (set-property/delete in a loop). I'll comment on this in the code and attach a final patch, unless review provokes further changes.

/be

Comment 50

[Igor Bukanov]

Comment on attachment 250236 [details] [diff] [review]
better fix, v4

The patch is OK besides the obvious problem of 16-bit overflow with the generation number if somebody can figure out how to call ClearScope 64K times. 

So instead of generation number in the scope what about GC communicating  back the fact that the scope was collected? That is, instead of marking the scope stored in tvr the GC can set tvr.scope to null if it is not marked by other means. Then js_NativeGet can check for tvr.scope == null to detect removed properties.

Comment 51

[Brendan Eich [:brendan]]

(In reply to comment #50)
> (From update of attachment 250236 [details] [diff] [review])
> The patch is OK besides the obvious problem of 16-bit overflow with the
> generation number if somebody can figure out how to call ClearScope 64K times.

Yes, I thought about that and considered a wrap-detector scheme that does something to compensate, but it's simply not possible in Firefox to have such a bad getter or setter (jst correct me if I'm wrong).

For general purposes, it would be better to have absolute certainty than an unquantified judgment that such insance API abusage is "unlikely".  But we don't check for lots of API abusage, and I'd rather keep the code simple.
 
> So instead of generation number in the scope what about GC communicating  back
> the fact that the scope was collected? That is, instead of marking the scope
> stored in tvr the GC can set tvr.scope to null if it is not marked by other
> means.

This seems to require an O(M*N) search of context tvr chains of total length M crossed with N to-be-swept sprops -- wouldn't it?

/be

Comment 52

[Johnny Stenback (:jst)]

(In reply to comment #51)
[...]
> Yes, I thought about that and considered a wrap-detector scheme that does
> something to compensate, but it's simply not possible in Firefox to have such a
> bad getter or setter (jst correct me if I'm wrong).

I do believe that to be correct. The only way that could be triggered would be if someone had 64k window objects and managed to trigger JS_ClearScope on all of them with a modal dialog (or equivalent) on the stack. *Very* unlikely.

Comment 53

[Igor Bukanov]

(In reply to comment #51)
> > That is, instead of marking the scope
> > stored in tvr the GC can set tvr.scope to null if it is not marked by other
> > means.
> 
> This seems to require an O(M*N) search of context tvr chains of total length M
> crossed with N to-be-swept sprops -- wouldn't it?

It should be O(M) since after the scope marking phase the GC can walk the tvr chain again and set tvr.sprop to null for all unmarked properties.

Comment 54

[Brendan Eich [:brendan]]

(In reply to comment #52)
> I do believe that to be correct. The only way that could be triggered would be
> if someone had 64k window objects and managed to trigger JS_ClearScope on all
> of them with a modal dialog (or equivalent) on the stack. *Very* unlikely.

The generation number is per-scope, so you would have to cause 64K JS_ClearScope calls on one object from a given getter or setter.  Our embedding can't do that, AFAIK, since setting location.href or whatever has immediate effect only once. But I'm not sure that's right.

(In reply to comment #53)
> It should be O(M) since after the scope marking phase the GC can walk the tvr
> chain again and set tvr.sprop to null for all unmarked properties.

Good point.  This has the virtue of certainty, and it will make for faster code in js_NativeGet and js_NativeSet.  Thanks, new patch shortly.

/be

Comment 55

[Igor Bukanov]

It seems the generation number is still required to support ClearScope without GC call. Otherwise how one would know that the sprop was note detached from the object?

Comment 56

[Brendan Eich [:brendan]]

(In reply to comment #54)
> (In reply to comment #53)
> > It should be O(M) since after the scope marking phase the GC can walk the tvr
> > chain again and set tvr.sprop to null for all unmarked properties.
> 
> Good point.  This has the virtue of certainty, and it will make for faster code
> in js_NativeGet and js_NativeSet.  Thanks, new patch shortly.

Ah, but this is not enough.  As jst's testing showed (comment 47) that we have to detect JS_ClearScope without a GC -- and that requires both marking to preserve the sprop's address-identity and SCOPE_GET_PROPERTY(scope, sprop->id) == sprop to be sure it's still in the scope.  The generation number is an optimization on top of this, and ignoring wraparound it only speeds up the js_NativeGet/Set flow for the common cases where the slot is in range, and there was no JS_ClearScope.

I'll land the current patch under cover of a bug about improving get/set perf.

/be

Comment 57

[Brendan Eich [:brendan]]

See bug 365851.

/be

Comment 58

[Igor Bukanov]

(In reply to comment #56)
> Ah, but this is not enough.  As jst's testing showed (comment 47) that we have
> to detect JS_ClearScope without a GC -- and that requires both marking to
> preserve the sprop's address-identity and SCOPE_GET_PROPERTY(scope, sprop->id)
> == sprop to be sure it's still in the scope.

Here is another schema without the generation number. ClearScope should set a
flag  in sprop that sprop was cleared. During GC the flag would be reset for
marked sprop while unmarked tvr.scope are cleared. Thus the code in NativeGet
would need to check for tvr.sprop != null && sprop.NoDeleteFlag for a quick
100% reliable quick test.

Comment 59

[Igor Bukanov]

(In reply to comment #58)
> Here is another schema without the generation number. ClearScope should set a
> flag  in sprop that sprop was cleared. During GC the flag would be reset for
> marked sprop while unmarked tvr.scope are cleared. Thus the code in NativeGet
> would need to check for tvr.sprop != null && sprop.NoDeleteFlag for a quick
> 100% reliable quick test.

That was not right. Here is the proper schema. ClearScope mark all removed sprop  with a flag. Then during GC the flag should be cleared for all marked properties that are not in tvr set. For marked properties on the tvr list the flag should be kept. For unmarked properties tvr.sprop should be cleared as an optimization. Then  the quick test in sprop is indeed tvr.sprop != null && sprop.NoDeleteFlag.   

Comment 60

[Brendan Eich [:brendan]]

(In reply to comment #58)
> (In reply to comment #56)
> > Ah, but this is not enough.  As jst's testing showed (comment 47) that we have
> > to detect JS_ClearScope without a GC -- and that requires both marking to
> > preserve the sprop's address-identity and SCOPE_GET_PROPERTY(scope, sprop->id)
> > == sprop to be sure it's still in the scope.
> 
> Here is another schema without the generation number. ClearScope should set a
> flag  in sprop that sprop was cleared.

This is not thread-safe as noted in comment 5.  The |= could race with another thread setting SPROP_IS_DUPLICATE (unlikely, but possible and more important: exploitable).

Also, this requires JS_ClearScope (js_ClearScope actually) to walk the ancestor line in rt->propertyTree, which is not a big cost, but O(N) in number of sprops in the object's scope.

> During GC the flag would be reset for
> marked sprop while unmarked tvr.scope are cleared. Thus the code in NativeGet
> would need to check for tvr.sprop != null && sprop.NoDeleteFlag for a quick
> 100% reliable quick test.

I claim the generation wraparound problem has probability 0 -- looking for jst to prove this better.

The generation test looks cheaper to me than tvr.u.sprop && !(sprop->flags & ...).

Igor, I pinged you for re-stamp of review to the same patch in bug 365851.

/be

Comment 61

[Igor Bukanov]

And here even simpler generation-less proposal. Instead of the generation number scope is extended with a single flag that ClearScope sets. Then the flag is reset in GC and all unmerked tvr.sprop are set to null but all tvr with marked scope are mutated (perhaps via changing tvr.count) to indicate that GC was run. Then the quick test is to check for scope.NotClearedFlag && !tvr.GC_DID_RUN. 

Comment 62

[Johnny Stenback (:jst)]

(In reply to comment #54)
> The generation number is per-scope, so you would have to cause 64K
> JS_ClearScope calls on one object from a given getter or setter.  Our embedding
> can't do that, AFAIK, since setting location.href or whatever has immediate
> effect only once. But I'm not sure that's right.

Actually, I don't think you can cause even one JS_ClearScope call from a getter or setter unless you're working with modal dialogs or nesting other modal things (i.e. synchronous XMLHttpRequests) in an onbeforeunload handler. With modal dialogs you can't nest any more, and with synchronous XMLHttpRequests you'd blow the stack way before you'd get to 64k nested synchronous requests (unless your JS stack depth protection kills this before we blow the C runtime stack). So yeah, AFAICT this is still safe.

Comment 63

[Brendan Eich [:brendan]]

Comment 61 seems sound at a glance, but it sure looks more complicated, and there is still a && (two tests) added to the common path, where the left operand of && is likely to be true most of the time, so the right will have to be tested.  The generation number scheme has a load and compare, predicted true (I hope -- should use JS_LIKELY).

/be

Comment 64

[Brendan Eich [:brendan]]

Attachment: better fix, v4a

scope->generation must be incremented when removing a property whose slot indexes the last jsval in scope->object->slots, which is about to be freed and liable to be reallocated to a different property.

/be

Comment 65

[Igor Bukanov]

(In reply to comment #64)
> scope->generation must be incremented when removing a property whose slot
> indexes the last jsval in scope->object->slots, which is about to be freed and
> liable to be reallocated to a different property.

Now the overflow is trivial to get: the script should just constantly add and remove properties. To fix that I suggest to add a 32-bit generation counter to JSRuntime. Although I suspect that with delete/add even that can be overflown on a fast computer, but for that a user has to press the continue in the slow script dialog many times.

Comment 66

[Igor Bukanov]

(In reply to comment #63)
> Comment 61 seems sound at a glance, but it sure looks more complicated, and
> there is still a && (two tests) added to the common path, where the left
> operand of && is likely to be true most of the time, so the right will have to
> be tested.  The generation number scheme has a load and compare, predicted true
> (I hope -- should use JS_LIKELY).

For the tests one can use &, not && since detecting that GC has run or a property was deleted from the scope are independent and can be done in any order. So there is one branch and 2 loads exactly as in the counter case where the counter has to be loaded twice.

Comment 67

[Igor Bukanov]

(In reply to comment #64)
> Created an attachment (id=250421) [details]
> better fix, v4a
> 
> scope->generation must be incremented when removing a property whose slot
> indexes the last jsval in scope->object->slots, which is about to be freed and
> liable to be reallocated to a different property.

Should any delete increase the counter to ensure that a slot for a deleted property is not re-populated?

Comment 68

[Brendan Eich [:brendan]]

(In reply to comment #67)
> Should any delete increase the counter to ensure that a slot for a deleted
> property is not re-populated?

I didn't want to comment too clearly about it till the patch is distributed, but we don't need to do that for deletes other than of the last slot, at the moment. Would like to assert that this is the case; not sure how.

Again not a problem in Gecko, but a rogue getter or setter that deleted and re-added the last-slot property 64K times would wrap, resulting in the last prop added having its slot overwritten by the deleted prop's value.  No memory error, but a hard case.

/be

Comment 69

[Brendan Eich [:brendan]]

Of course, the rogue could not add after the 64K'th delete, leaving us potentially storing into free memory. Back to the drawing board.

/be

Comment 70

[Igor Bukanov]

(In reply to comment #68)
> Again not a problem in Gecko, but a rogue getter or setter that deleted and
> re-added the last-slot property 64K times would wrap, resulting in the last
> prop added having its slot overwritten by the deleted prop's value.  No memory
> error, but a hard case.

It can be a bad error since it would allow a script from one page to put objects into document coming from a different location. One do not need a getter for that, just a close hook executed at the right moment through GC triggered by a trusted getter. Thus I suggest a global 32-bit counter increased on any delete of sprop from a scope.

Comment 71

[Brendan Eich [:brendan]]

Attachment: better fix, v4b

Are we there yet? ;-)

/be

Comment 72

[Igor Bukanov]

Comment on attachment 250495 [details] [diff] [review]
better fix, v4b

>+    if (SPROP_HAS_VALID_SLOT(sprop, scope)) {
>         js_FreeSlot(cx, scope->object, sprop->slot);
>+        JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
>+    }

AFAIK there is no need to use JS_ATOMIC_INCREMENT as we are inside a lock here. But I can miss something and besides this possibly wrong optimization opportunity  I do not have any issues with the patch :)

Comment 73

[Brendan Eich [:brendan]]

(In reply to comment #72)
> AFAIK there is no need to use JS_ATOMIC_INCREMENT as we are inside a lock here.
> But I can miss something and besides this possibly wrong optimization
> opportunity  I do not have any issues with the patch :)

No, we have to use an atomic increment op here, because the runtime is shared among threads that may not be interlocking gets or sets on the same scope.  The propertyRemovals "capability" is truly process-wide.  So there could be races to load, increment, and store cx->runtime->propertyRemovals leading to its value not changing from one thread's sample of it.

Still, this scheme should optimize away rehashing (the consequent for when the sample disagrees, SCOPE_GET_PROPERTY(scope, sprop->id) == sprop) in most cases.

/be

Comment 74

[Brendan Eich [:brendan]]

Fixed on trunk -- see bug 365851 comment 3.

/be

Comment 75

[Brendan Eich [:brendan]]

Attachment: 1.8 branch patch

Easy backport: cvs join with one conflict fixed by hand.

/be

Comment 76

[Brendan Eich [:brendan]]

Attachment: 1.8 branch patch, updated

Includes a missed use-case for MARK_ID in jsobj.c.

/be

Comment 77

[Brendan Eich [:brendan]]

Attachment: 1.8.0 branch patch

Required resolving conflicts in four files, so asking for igor to re-review.  My diff (interdiff crapped out) of this patch and the 1.8 branch patch looks good to me, FWIW.

/be

Comment 78

[Jay Patel [:jay]]

Comment on attachment 250527 [details] [diff] [review]
1.8 branch patch, updated

Approved for 1.8 branch, a=jay for drivers.  Let's get this landed and tested early... and then land on the 1.8.0 branch as well after that patch is reviewed.

Comment 79

[Brendan Eich [:brendan]]

Checked in under cover of bug 36851 (which lacks approvals, hrm):

Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.214.2.34; previous revision: 3.214.2.33
done
Checking in jscntxt.c;
/cvsroot/mozilla/js/src/jscntxt.c,v  <--  jscntxt.c
new revision: 3.60.4.11; previous revision: 3.60.4.10
done
Checking in jscntxt.h;
/cvsroot/mozilla/js/src/jscntxt.h,v  <--  jscntxt.h
new revision: 3.80.4.20; previous revision: 3.80.4.19
done
Checking in jsdbgapi.c;
/cvsroot/mozilla/js/src/jsdbgapi.c,v  <--  jsdbgapi.c
new revision: 3.56.2.15; previous revision: 3.56.2.14
done
Checking in jsgc.c;
/cvsroot/mozilla/js/src/jsgc.c,v  <--  jsgc.c
new revision: 3.104.2.31; previous revision: 3.104.2.30
done
Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.181.2.80; previous revision: 3.181.2.79
done
Checking in jsobj.c;
/cvsroot/mozilla/js/src/jsobj.c,v  <--  jsobj.c
new revision: 3.208.2.47; previous revision: 3.208.2.46
done
Checking in jsobj.h;
/cvsroot/mozilla/js/src/jsobj.h,v  <--  jsobj.h
new revision: 3.39.4.9; previous revision: 3.39.4.8
done
Checking in jsscope.c;
/cvsroot/mozilla/js/src/jsscope.c,v  <--  jsscope.c
new revision: 3.45.20.4; previous revision: 3.45.20.3
done
Checking in jsscope.h;
/cvsroot/mozilla/js/src/jsscope.h,v  <--  jsscope.h
new revision: 3.38.4.2; previous revision: 3.38.4.1
done

/be

Comment 80

[Jay Patel [:jay]]

Comment on attachment 250528 [details] [diff] [review]
1.8.0 branch patch

Approved for 1.8.0 branch, a=jay for drivers.

Comment 81

[Johnny Stenback (:jst)]

1.8.0 branch patch checked in.