569735 - TM: suppress deleted properties during iteration

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Andreas Gal :gal]

The web wants it, sadly.

Comment 1

[Jeff Walden [:Waldo]]

You mean one page wants it, so far.  One page is not enough basis to make a judgment, in my opinion.  I'd like to see multiple different sites, run by multiple different people, with varying rates of updates (so it's difficult to encourage people to fix them), before we declare failure here.

Comment 2

[Robert Sayre]

We're taking on quite enough risk with this release, I think. We can always try again later.

And, really, who cares? It doesn't seem like such a big deal.

Comment 3

[Andreas Gal :gal]

I can do this with a simple and cheap write barrier. If a thread deletes a property all currently pending iterations on the same thread will suppress it. Patch in a bit.

Comment 4

[Brendan Eich [:brendan]]

I've been around this block before. My gut says that site is the tip of the iceberg.

The problem is that all browsers suppress deletions. The spec matches reality on this point. So we are in an all-pain/no-gain setting: lose market share due to "site doesn't work" dinging Firefox 4 adoption at the margins, while competition (old versions and new) along with all extant Firefox downrev releases work on the sites, plural (it's not going to be only one).

So we should keep tracking dups for a while, but Andreas is developing a patch. We'll get more signal from m-c. If I'm right, it will just confirm that we need the patch. Let's not waste too much time on this windmill-tilting-at exercise, though.

/be

Comment 5

[Andreas Gal :gal]

Attachment: patch

Comment 6

[Andreas Gal :gal]

Attachment: patch

Comment 7

[Andreas Gal :gal]

Attachment: patch

Comment 8

[Brendan Eich [:brendan]]

Comment on attachment 448896 [details] [diff] [review]
patch

>+JSIdArrayToIterator(JSContext *cx, JSObject *obj, uintN flags, JSIdArray *ida, jsval *vp)
> {
>     JSObject *iterobj = NewIteratorObject(cx, flags);
>     if (!iterobj)
>         return false;
> 
>     *vp = OBJECT_TO_JSVAL(iterobj);
> 
>-    NativeIterator *ni = NativeIterator::allocate(cx, flags, NULL, 0, 0,
>+    NativeIterator *ni = NativeIterator::allocate(cx, obj, flags, NULL, 0, 0,
>                                                   ida->vector, ida->length);
>     if (!ni)
>         return false;
> 
>     iterobj->setNativeIterator(ni);
>+
>+    RegisterEnumerator(cx, iterobj, ni);
>+
>     return true;

Too spacey -- how about crunching return true; and RegisterEnumerator.

Also make RegisterEnumerator inline maybe? Did any for-in sensitive benchmarks notice this patch? The "depth of field" chrome experiment deletes (from a different object than the one being enumerated) while enumerating.

>@@ -455,16 +471,19 @@ GetIterator(JSContext *cx, JSObject *obj
>             JSObject *iterobj = *hp;
>             if (iterobj) {
>                 NativeIterator *ni = iterobj->getNativeIterator();
>                 if (ni->shapes_key == key &&
>                     ni->shapes_length == shapes.length() &&
>                     Compare(ni->shapes_array, shapes.begin(), ni->shapes_length)) {
>                     *vp = OBJECT_TO_JSVAL(iterobj);
>                     *hp = ni->next;
>+
>+                    RegisterEnumerator(cx, iterobj, ni);
>+
>                     return true;

Ditto on crunching return with previous non-blank line. Crunchy!

>@@ -481,16 +500,19 @@ GetIterator(JSContext *cx, JSObject *obj
>     /* Store in *vp to protect it from GC (callers must root vp). */
>     *vp = OBJECT_TO_JSVAL(iterobj);
> 
>     NativeIterator *ni = Snapshot(cx, obj, flags, shapes.begin(), shapes.length(), key);
>     if (!ni)
>         return false;
> 
>     iterobj->setNativeIterator(ni);
>+
>+    RegisterEnumerator(cx, iterobj, ni);
>+
>     return true;

Ditto.

>@@ -622,18 +644,24 @@ js_CloseIterator(JSContext *cx, jsval v)
> 
>     cx->iterValue = JSVAL_HOLE;
> 
>     JS_ASSERT(!JSVAL_IS_PRIMITIVE(v));
>     obj = JSVAL_TO_OBJECT(v);
>     clasp = obj->getClass();
> 
>     if (clasp == &js_IteratorClass.base) {
>+        /* Remove enumerators from the active list. */
>+        NativeIterator *ni = obj->getNativeIterator();
>+        if (ni->flags & JSITER_ENUMERATE) {
>+            JSThreadData *data = JS_THREAD_DATA(cx);
>+            JS_ASSERT(data->enumerators == obj);
>+            data->enumerators = ni->next;
>+        }
>         /* Cache the iterator object if possible. */

Need a blank line (one of the ones you crunched, from your bogus crunched lines bank :-P) before the comment here.

Bug: you are assuming LIFO Register/Close for nested loops but it just ain't so. Consider exception causing control to unwind without closing. Consider also turn-taking with multiple contexts on the thread. You will have to search and delete:

..        if (ni->flags & JSITER_ENUMERATE) {
..            JSThreadData *data = JS_THREAD_DATA(cx);
..            JSObject **objp = &data->enumerators;
..            while (*objp != obj)
..                objp = &obj2ni(obj)->next; // what is obj2ni?
..            *objp = ni->next;
..        }

>+++ b/js/src/jsobj.h
>@@ -195,16 +195,19 @@ struct JSObjectMap {
> private:
>     /* No copy or assignment semantics. */
>     JSObjectMap(JSObjectMap &);
>     void operator=(JSObjectMap &);
> };
> 
> struct NativeIterator;
> 
>+void
>+js_SuppressDeletedProperty(JSContext *cx, JSObject *obj, jsid id);
>+

Expedient here rather than jsiter.h and we don't want a dependency. OTOH we have jsobjinlines.h and it already includes jsiter.h. More below.

>@@ -650,17 +653,20 @@ struct JSObject {
>     }
> 
>     JSBool setAttributes(JSContext *cx, jsid id, JSProperty *prop,
>                          uintN *attrsp) {
>         return map->ops->setAttributes(cx, this, id, prop, attrsp);
>     }
> 
>     JSBool deleteProperty(JSContext *cx, jsid id, jsval *rval) {
>-        return map->ops->deleteProperty(cx, this, id, rval);
>+        JSBool ok = map->ops->deleteProperty(cx, this, id, rval);
>+        if (ok)
>+            js_SuppressDeletedProperty(cx, this, id);
>+        return ok;
>     }

Is this really the funnel? No one calls obj->map->ops->deleteProperty directly, e.g.? OTOH, do we need this for non-natives (including dense arrays) or only for natives? If the latter then you could declare js_SuppressDP in jsiter.h and use it from jsobj.cpp:js_DeleteProperty.

/be

Comment 9

[Andreas Gal :gal]

Attachment: patch

Comment 10

[Brendan Eich [:brendan]]

Comment on attachment 448911 [details] [diff] [review]
patch

>@@ -5292,22 +5293,25 @@ js_DeleteProperty(JSContext *cx, JSObjec
>     }
> 
>     /* XXXbe called with obj locked */
>     if (!obj->getClass()->delProperty(cx, obj, SPROP_USERID(sprop), rval)) {
>         obj->dropProperty(cx, prop);
>         return JS_FALSE;
>     }
> 
>+    js_SuppressDeletedProperty(cx, obj, id);
>+
>     scope = obj->scope();
>     if (SPROP_HAS_VALID_SLOT(sprop, scope))
>         GC_POKE(cx, obj->lockedGetSlot(sprop->slot));
> 
>     ok = scope->removeProperty(cx, id);
>     obj->dropProperty(cx, prop);
>+
>     return ok;

You call js_SuppressDP at the bottom of array_DeleteProperty, so do it here just before the return ok, and how about only if ok (if error we can't assume id was removed).

Document the fact that we don't unshadow proto properties when delete of an own property suppresses the id. Also that we do not suppress deleted proto properties at all. Fess up in full! ;-)

/be

Comment 11

[Andreas Gal :gal]

Attachment: patch

Comment 12

[Brendan Eich [:brendan]]

Comment on attachment 448917 [details] [diff] [review]
patch

>@@ -622,18 +641,25 @@ js_CloseIterator(JSContext *cx, jsval v)
> 
>     cx->iterValue = JSVAL_HOLE;
> 
>     JS_ASSERT(!JSVAL_IS_PRIMITIVE(v));
>     obj = JSVAL_TO_OBJECT(v);
>     clasp = obj->getClass();
> 
>     if (clasp == &js_IteratorClass.base) {
>+        /* Remove enumerators from the active list. */

Add ", which is a stack" to this comment.

r=me with that.

/be

Comment 13

[Boris Zbarsky [:bzbarsky]]

Just out of curiosity, which page does comment 1 refer to?

Comment 14

[Brendan Eich [:brendan]]

(In reply to comment #13)
> Just out of curiosity, which page does comment 1 refer to?

Bug 569516. Needs to be confirmed as caused by fastiterators still.

/be

Comment 15

[Andreas Gal :gal]

http://hg.mozilla.org/tracemonkey/rev/96dbe8a784f1

Comment 16

[Boris Zbarsky [:bzbarsky]]

Oh, it's confirmed as caused by fastiterators.  Needs to be confirmed as being caused by deletes, perhaps.

Comment 17

[Andreas Gal :gal]

Backed out.

http://hg.mozilla.org/tracemonkey/rev/2fe89784cf66

Comment 18

[Andreas Gal :gal]

Nasty. The enumerator list contains a GC-ed object.

CPU: x86
     GenuineIntel family 6 model 23 stepping 8
     1 CPU

Crash reason:  SIGSEGV
Crash address: 0xdadadadc

Thread 0 (crashed)
 0  libmozjs.so!JSObject::getPrivate [jsobj.h:0a5778b1355b : 391 + 0xb]
    eip = 0x00750a3b   esp = 0xbfa76f20   ebp = 0xbfa76f48   ebx = 0x00967d50
    esi = 0xb5cf51e0   edi = 0xb160c600   eax = 0xdadadad8   ecx = 0x00967d50
    edx = 0x0b0da8f0   efl = 0x00010286
    Found by: given as instruction pointer in context
 1  libmozjs.so!JSObject::getNativeIterator [jsobjinlines.h:0a5778b1355b : 399 + 0xa]
    eip = 0x007df081   esp = 0xbfa76f50   ebp = 0xbfa76f58   ebx = 0x00967d50
    esi = 0xb5cf51e0   edi = 0xb160c600
    Found by: call frame info
 2  libmozjs.so!js_SuppressDeletedProperty [jsiter.cpp:0a5778b1355b : 691 + 0xa]
    eip = 0x007dc8d9   esp = 0xbfa76f60   ebp = 0xbfa76fd8   ebx = 0x00967d50
    esi = 0xb5cf51e0   edi = 0xb160c600
    Found by: call frame info
 3  libmozjs.so!js_DeleteProperty [jsobj.cpp:0a5778b1355b : 5337 + 0x1e]
    eip = 0x007f21f4   esp = 0xbfa76fe0   ebp = 0xbfa77028   ebx = 0x00967d50
    esi = 0xb5cf51e0   edi = 0xb160c600
    Found by: call frame info
 4  libmozjs.so!JSObject::deleteProperty [jsobj.h:0a5778b1355b : 658 + 0x26]
    eip = 0x0074f53d   esp = 0xbfa77030   ebp = 0xbfa77048   ebx = 0x00967d50
    esi = 0xb5cf51e0   edi = 0xb160c600
    Found by: call frame info

Comment 19

[Andreas Gal :gal]

Attachment: patch

The enumerators stack can get out of balance in two cases:
- OOM doesn't properly unwind and doesn't close iterators, so we leave the iterator object on cx->enumerators
- generators might start an iteration, which is not symmetrical

2 simple fixes for both problems:
- restore the pre-state of cx->enumerators around every js_Interpret call, which fixes unclean unwind
- in case of generators store cx->enumerators in JSGenerator, and use that one as the stack while the generator executes

I also moved the stack into the context (instead of the thread). This seems saner.

Comment 20

[Andreas Gal :gal]

Note: I never mark cx->enumerators. Otherwise dead objects should not be on that list. Thats a bug (this goes for both, cx->enumerators and gen->enumerators).

Comment 21

[Brendan Eich [:brendan]]

Comment on attachment 449107 [details] [diff] [review]
patch

>@@ -990,18 +1076,26 @@ SendToGenerator(JSContext *cx, JSGenerat
>         if (genfp->argsobj)
>             JSVAL_TO_OBJECT(fp->argsobj)->setPrivate(fp);
>         gen->liveFrame = fp;
>         (void)cx->enterGenerator(gen); /* OOM check above. */
> 
>         /* Officially push |fp|. |frame|'s destructor pops. */
>         cx->stack().pushExecuteFrame(cx, frame, gen->savedRegs, NULL);
> 
>+        /* Swap the enumerators stack for the generator's stack. */
>+        JSObject *enumerators = cx->enumerators;
>+        cx->enumerators = gen->enumerators;
>+
>         ok = js_Interpret(cx);
> 
>+        /* Restore the original enumerators stack. */
>+        gen->enumerators = cx->enumerators;
>+        cx->enumerators = enumerators;

Use an AutoEnumeratorsStackBalance inside a braced block here.

Rename AutoEnumeratorsStackBalance to AutoPreserveEnumerators, before my head explodes!

The DOM does sometimes snake control flow across contexts (via an addProperty hook, IIRC), but let's trust that no callee deletes from an object being for-in-enumerated by the caller.

r=me with nits above addressed.

/be

Comment 22

[Andreas Gal :gal]

The code in jsiter is different and has to switch to the generator's stack and then switch back. So I can't use the same AutoPreserveEnumerators there. Plus, that class isn't visible in jsiter (its in jsinterp). Should I write a single use auto class or leave it as is?

Comment 23

[Brendan Eich [:brendan]]

May not be worth it -- I was hoping for reuse of an AutoPreserveEnumerators that was extended to swap in a new list and swap it out on destruction but it looks like a different beast. Single use auto helper is pointless. Ok, just the name change please.

/be

Comment 24

[Andreas Gal :gal]

http://hg.mozilla.org/tracemonkey/rev/c607dfb41475

Comment 25

[Igor Bukanov]

(In reply to comment #20)
> Note: I never mark cx->enumerators. Otherwise dead objects should not be on
> that list. Thats a bug (this goes for both, cx->enumerators and
> gen->enumerators).

It would be nice to assert that cx->enumerators is marked to prevent the bugs from appearing. I can file another bug on that if necessary.

Comment 26

[Igor Bukanov]

The landed patch does not call js_SuppressDeletedProperty for the typed arrays. Is it intentional?

Comment 27

[Igor Bukanov]

The patch does not check for enumerators in DeleteArrayElement for the dense arrays. So the output for the following script:

var a = [0, 1];
for (var i in a) {
    print(i);
    a.pop();
}

is 0, 1 while for 

var a = [0, 1];
for (var i in a) {
    print(i);
    delete a[1];
}

it is just 0.

Comment 28

[Brendan Eich [:brendan]]

(In reply to comment #26)
> The landed patch does not call js_SuppressDeletedProperty for the typed arrays.
> Is it intentional?

Typed arrays are "sealed" in ES5 sense (not old SpiderMonkey/Rhino sense, which ES5 calls frozen): you can't delete a typed array element, or extend the array with ad-hoc properties; you can read and write existing elements.

Comment 27 looks like a bug -- good catch! File separately at this point.

/be

Comment 29

[Igor Bukanov]

Consider the following test case that deletes and restores a property under enumeration:

var obj = {a: 0, b: 1};
var properties = [];
for (var i in obj) {
    properties.push(i);
    delete obj.b;
    obj.b = 2;
}

print(properties);

Prior to the fast iterator change the output was 'a,b' since older iteration checked for deleted properties when checking for the next iteration. Chrome, MSIE 8 and Opera give the same output. 

This bug changes the output to be just 'a'. So there is still incompatibility. But I have no idea how important it could be.

Comment 30

[Andreas Gal :gal]

#29: The spec doesn't speak about reviving properties. Both behaviors are allowed.

Comment 31

[Brendan Eich [:brendan]]

(In reply to comment #30)
> #29: The spec doesn't speak about reviving properties. Both behaviors are
> allowed.

That's really beside the point once you swallow deleted property suppression -- the spec is way underspecified, but the de-facto standard is what matters.

What's more, we had to re-implement deleted property suppression due to de-facto breakage (as Waldo pointed out, we could wait for more evidence, but we had at least one case in bug 569516), not due to qualms about de-jure spec violation. We were valiantly willing to flout the spec on the delete-suppression point; it was "just theory". But practice did not cooperate.

So the spec's not the thing. Making an incompatible change that breaks something is the concern. Comment 29 raises an instance, it's worth considering.

/be

Comment 32

[Andreas Gal :gal]

Well its not that clear cut. The test case in #29 clearly shows that we used to be out of compliance with ES5 (and so are Chrome, MSIE 8 and Opera it seems).

var obj = {a: 0, b: 1, c: 2};
var properties = [];
for (var i in obj) {
    properties.push(i);
    delete obj.b;
    obj.b = 2;
}

results in a,b,c prior to snapshot-ing. Thats a clear violation of the spec since we are not enumerating in property creation order. b was deleted and re-added. It should appear at the end.

With the current code we output a,c which is different than before, but not a spec violation.

Comment 33

[Brendan Eich [:brendan]]

> Thats a clear violation of the spec since we are not enumerating in property
> creation order.

No, see ES5 12.6.4 -- the spec says *nothing* about property creation order. Creation order is a de-facto standard, a fuzzy one at that (doesn't apply to arrays, may not apply to delete and immediate re-add as you noticed).

/be

Comment 34

[Andreas Gal :gal]

Ok, so whats the plan then?

Comment 35

[Igor Bukanov]

(In reply to comment #34)
> Ok, so whats the plan then?

In the worst case we would need to check for the deleted properties when doing iterNext. It can be build on top of the current patch where  js_SuppressDeletedProperty will flag the iterator as a slow one and iterNext will check for flag.

Comment 36

[Andreas Gal :gal]

I am not opposed to that, but I think this patch fixes the known problems we saw, so we should file a new bug, and find someone to do it. I am off in wrapper land and don't really want to work on this.

Comment 37

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/c607dfb41475