557914 - Remove gcIteratorTable

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andreas Gal :gal]

bug 341821 introduced gcIteratorTable with a big fat slow lock around it. We register all iterators in it. This is lame. Its really only needed for generators with custom scripted close hooks (see testcase in the bug).

Comment 1

[Andreas Gal :gal]

/* Finalize iterator states before the objects they iterate over. */
CloseNativeIterators(cx);

Comment 2

[Andreas Gal :gal]

bug 341821 mentions this test case as rationale for introducing the closeable iterator table:

function make_iterator()
{
    var iter = (function() { yield 0; })();
    iter.close = make_iterator;
    alert(1);
}

make_iterator();

gc();

However, this test case:
- never gets registered as a closeable iterator (because its a generator)
- the generator close hook is never called at all

Comment 3

[Jeff Walden [:Waldo]]

We removed that functionality in a later bug -- close isn't called if the generator goes away due to GC.

Comment 4

[Andreas Gal :gal]

We never register generators in that table. close() is only called from JSOP_ENDITER. I am adding a ENUMERATE_DESTROY call from a iterator_finalize hook. This is a minimal change in behavior and shouldn't confuse xpconnect (here is hoping).

Comment 5

[Andreas Gal :gal]

Attachment: patch

Comment 6

[Andreas Gal :gal]

I checked what xpconnect is doing under ENUMERATE_DESTROY. It just does reference counting and memory freeing, nothing that this change will break.

Comment 7

[Brendan Eich [:brendan]]

    TIMESTAMP(gcTimer.startSweep);
    js_SweepAtomState(cx);

    /* Finalize iterator states before the objects they iterate over. */
    CloseNativeIterators(cx);

    /* Finalize watch points associated with unreachable objects. */
    js_SweepWatchPoints(cx);

...

I don't see how XPConnect could care about where in the sweep phase it's called.

Order may change but if we have any bugs to do with finalization order, let's find them.

/be

Comment 8

[Andreas Gal :gal]

http://hg.mozilla.org/tracemonkey/rev/687d1e4c213e

Comment 9

[Andreas Gal :gal]

Alright, here we get bitten:

Testcase:

var iter = Iterator({});
for (var i = 0; i != 10*1000; ++i)
  iter[i] = i;

(gdb) r x.js
Starting program: /Users/gal/workspace/tracemonkey-repository/js/src/Darwin_DBG.OBJ/js x.js
Reading symbols for shared libraries . done

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: 13 at address: 0x0000000000000000
0x0000000100193fd1 in JSObject::isXML (this=0x1003bb240) at jsxml.h:230
230	    return map->ops == &js_XMLObjectOps;
(gdb) p map
$1 = (JSObjectMap *) 0xdadadadadadadada
(gdb) up
#1  0x00000001000a67a0 in CloseNativeIterator (cx=0x10088b400, iterobj=0x1003bb280) at ../jsiter.cpp:114
warning: Source file is more recent than executable.
114	        if ((flags & JSITER_FOREACH) && OBJECT_IS_XML(cx, iterable)) {
(gdb) list
109	    /* Protect against failure to fully initialize obj. */
110	    iterable = iterobj->getParent();
111	    if (iterable) {
112	#if JS_HAS_XML_SUPPORT
113	        uintN flags = JSVAL_TO_INT(iterobj->getSlot(JSSLOT_ITER_FLAGS));
114	        if ((flags & JSITER_FOREACH) && OBJECT_IS_XML(cx, iterable)) {
115	            js_EnumerateXMLValues(cx, iterable, JSENUMERATE_DESTROY, &state,
116	                                  NULL, NULL);
117	        } else
118	#endif
(gdb)

Comment 10

[Andreas Gal :gal]

The object we iterate over was already destroyed by the GC by the time we try to destroy the iterator, which involves calling hooks on the object. Very bad API design here. There has to be a way to fix this.

Comment 11

[Andreas Gal :gal]

Backed out for a bit until I have a fix.

http://hg.mozilla.org/tracemonkey/rev/23e71fa6bd6e

Comment 12

[Andreas Gal :gal]

Attachment: disgusting patch to fix a nasty bug in a really broken protocol

Comment 13

[Andreas Gal :gal]

This bypasses the new_enumerate hook for destroy so I don't think thats going to fly. Our API is broken broken broken.

Comment 14

[Andreas Gal :gal]

Note: I can't cache the enumerate op directly because its a function pointer, and function pointers are sometimes not word-aligned (at least on x86).

Comment 15

[Brendan Eich [:brendan]]

We are repeating history, the curse of those who ignore it.

The iterator object holds its iteratee via the parent slot. Finalization does not order objects by their slot dependencies, so we have to either (a) insert an extra (sub-)phase for iterators, as the gcIteratorTable did prior to this bug's patch; or (b) keep the parent alive even when the child iterator object dies, but that may require an extra GC at shutdown to finalize everything.

This is an old problem.

/be

Comment 16

[Brendan Eich [:brendan]]

Blame to fur for the design; I went along, it was 1997 or early 1998.

/be

Comment 17

[Andreas Gal :gal]

Attachment: patch

Add a new finalizable type (FINALIZE_ITER) and finalize those objects first. This adds another clasp comparison in NewGCObject to the already existing function/object distinction. This has to be optimized. I will file a dependent bug (I checked that this doesn't slow anything down because we are already pretty suboptimal there).

Comment 18

[Igor Bukanov]

(In reply to comment #0)
>  Its really only needed for
> generators with custom scripted close hooks (see testcase in the bug).

Now, it is necessary for a generic iterator due to deficiency of the enumeration protocol. The iterator object holds the enumeration state variable. To destroy it the enumeration api needs the the original object that created the enumeration. This requires to make sure that the original object is finalized after the iterator object.

Comment 19

[Andreas Gal :gal]

Yes, the patch is addressing that issue. Please look at it.

Comment 20

[Andreas Gal :gal]

Igor, comment #18 is addressed by the patch. The patch is ready for review. Iterator objects are allocated in separate GC arenas which I sweep first, so the object is still valid and the iterator can be destroyed despite the API shortcoming.

Comment 21

[Brendan Eich [:brendan]]

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

>+static void
>+CloseNativeIterator(JSContext *cx, JSObject *iterobj)
> {
>     jsval state;
>     JSObject *iterable;
> 
>     JS_ASSERT(iterobj->getClass() == &js_IteratorClass);
> 
>-    /* Avoid double work if js_CloseNativeIterator was called on obj. */
>+    /* Avoid double work if CloseNativeIterator was called on obj. */
>     state = iterobj->getSlot(JSSLOT_ITER_STATE);
>     if (JSVAL_IS_NULL(state))
>         return;

This should move to iter_finalize, since it cannot happen when CloseNativeIterator is called from js_CloseIterator but it can from the finalizer in exactly the js_CloseIterator-called-from-end-of-for-in-loop case.

>@@ -134,35 +140,33 @@ iterator_trace(JSTracer *trc, JSObject *
> }
> 
> JSClass js_IteratorClass = {
>     "Iterator",
>     JSCLASS_HAS_RESERVED_SLOTS(2) | /* slots for state and flags */
>     JSCLASS_HAS_CACHED_PROTO(JSProto_Iterator) |
>     JSCLASS_MARK_IS_TRACE,
>     JS_PropertyStub,  JS_PropertyStub,  JS_PropertyStub,  JS_PropertyStub,
>-    JS_EnumerateStub, JS_ResolveStub,   JS_ConvertStub,   NULL,
>+    JS_EnumerateStub, JS_ResolveStub,   JS_ConvertStub,   iterator_finalize,
>     NULL,             NULL,            NULL,            NULL,
>     NULL,             NULL,            JS_CLASS_TRACE(iterator_trace), NULL

Bonus points for pulling in the third and fourth "columns" on the two lines starting with JS_PropertyStub, by one space each, so things line up along all columns.

>@@ -2855,17 +2855,19 @@ js_NewObjectWithGivenProto(JSContext *cx
> #ifdef DEBUG
>         if (obj) {
>             memset((uint8 *) obj + sizeof(JSObject), JS_FREE_PATTERN,
>                    sizeof(JSFunction) - sizeof(JSObject));
>         }
> #endif
>     } else {
>         JS_ASSERT(!objectSize || objectSize == sizeof(JSObject));
>-        obj = js_NewGCObject(cx);
>+        obj = (clasp == &js_IteratorClass)
>+            ? js_NewGCIter(cx)
>+            : js_NewGCObject(cx);

Ouch. Is this not going to light up shark? I guess you have a separate patch to get rid of the cost.

/be

Comment 22

[Igor Bukanov]

(In reply to comment #20)
> Igor, comment #18 is addressed by the patch. The patch is ready for review.
> Iterator objects are allocated in separate GC arenas which I sweep first, so
> the object is still valid and the iterator can be destroyed despite the API
> shortcoming.

My wish is for another enumeration API that would remove the need for any constrains of the finalization order and help ensure proper ES semantics while minimizing the overhead. So spending efforts on better workarounds around protocol deficiencies in non-performance critical code could be counterproductive unless we get simpler code etc.

Comment 23

[Brendan Eich [:brendan]]

Yeah, we all want the new, new thing. Andreas said he will work on it. But this bug's patch is working around protocol deficiencies in performance-critical code, because the locked iterator table costs us significantly on t/string-fasta.js.

Let's get this fixed in steps: locked GC table removal now, better protocol soon (but not immediately) after.

/be

Comment 24

[Andreas Gal :gal]

Attachment: patch

Comment 25

[Andreas Gal :gal]

> >     } else {
> >         JS_ASSERT(!objectSize || objectSize == sizeof(JSObject));
> >-        obj = js_NewGCObject(cx);
> >+        obj = (clasp == &js_IteratorClass)
> >+            ? js_NewGCIter(cx)
> >+            : js_NewGCObject(cx);
> 
> Ouch. Is this not going to light up shark? I guess you have a separate patch to
> get rid of the cost.

I have a separate patch to win this back (and then some). The patch has review and is ready to land but blocked by this patch.

Comment 26

[Andreas Gal :gal]

It is not true that state can't be NULL on the normal path.

#0  0x000000010013fa81 in JS_Assert (s=0x1001d5738 "state != JSVAL_NULL", file=0x1001d566a "../jsiter.cpp", ln=101) at ../jsutil.cpp:76
#1  0x00000001000a5fbf in CloseNativeIterator (cx=0x10088b400, iterobj=0x1003c3000) at ../jsiter.cpp:101
#2  0x00000001000a6d92 in js_CloseIterator (cx=0x10088b400, v=4298911744) at ../jsiter.cpp:453
#3  0x000000010007ff98 in js_Interpret (cx=0x10088b400) at jsops.cpp:495
#4  0x00000001000a3aa3 in js_Execute () at jsinterp.cpp:1104
#5  0x0000000100011f51 in JS_ExecuteScript (cx=0x10088b400, obj=0x1003bd000, script=0x100960000, rval=0x0) at ../jsapi.cpp:4825
#6  0x000000010000a2d8 in Process (cx=0x10088b400, obj=0x1003bd000, filename=0x7fff5fbffa15 "imacro_asm.js", forceTTY=0) at ../../shell/js.cpp:449
#7  0x000000010000af18 in ProcessArgs (cx=0x10088b400, obj=0x1003bd000, argv=0x7fff5fbff8c0, argc=2) at ../../shell/js.cpp:863
#8  0x000000010000b093 in main (argc=2, argv=0x7fff5fbff8c0, envp=0x7fff5fbff8d8) at ../../shell/js.cpp:5019

Comment 27

[Andreas Gal :gal]

Attachment: patch

Comment 28

[Brendan Eich [:brendan]]

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

Sorry, forgot that fur's old-new enumerate protocol eagerly nulls state if JSENUMERATE_NEXT exhausts the iterator. This is yet another wrinkle to revisit and perhaps smooth out in the new new thing.

/be

Comment 29

[Andreas Gal :gal]

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

Comment 30

[Igor Bukanov]

(In reply to comment #23)
> But this
> bug's patch is working around protocol deficiencies in performance-critical
> code

Sure - I did not mean to object against the match since it nicely makes thinks simpler and faster. It is just a had a hectic few last days and did not have time for anything but short emails.

Comment 31

[Igor Bukanov]

(In reply to comment #29)
> http://hg.mozilla.org/tracemonkey/

http://hg.mozilla.org/tracemonkey/rev/121debb9ff3d

Comment 32

[Igor Bukanov]

(In reply to comment #27)
> Created an attachment (id=438282) [details]
> patch

It seems that passing the finalization kind, not the allocation size, to NewObject would avoid any slowdown there even without inlining.

Comment 33

[Brendan Eich [:brendan]]

Also

http://hg.mozilla.org/tracemonkey/rev/9bf9c6e72fe2

/be

Comment 34

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/687d1e4c213e