419537 - Array thread-safety restoration

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Brian Crowder]

Attachment: WIP, v.01

This patch is required for future array thread-safety work.

Comment 1

[Brendan Eich [:brendan]]

I don't believe this is required, and I think it hurts perf. We need a sound theory of thread safety first, then patching. I will help, but probably after tomorrow's freeze. We can get approval after the freeze for the right patch, I'm sure.

This bug should be morphed into "Array thread safety restoration" -- crowder, can you do the deed? Thanks,

/be

Comment 2

[Mike Shaver (:shaver emeritus)]

I believe that it's required, so that the sampling of, f.e., obj->map->ops->lookupProperty and then subsequent call, as via OBJ_LOOKUP_PROPERTY on a necessarily unlocked object, can't race with a slowifying mutation that changes ops.  I would love (*love*) to be mistaken in that belief, though, because I agree that it's likely to ding perf a little.

The theory of threadsafety that crowder and I developed was:

- need to unify ops and class to avoid distributing sample-vs-operate races throughout the codebase, since we don't want to require locking to precede OBJ_GET_CLASS and span to dependent operations;

- OBJ_IS_DENSE_ARRAY would need to lock when indicating that it's true, again so that the operation that follows and depends on obj's denseness can't race badly with a slowification in another thread;

- ops and appropriate array natives (plus 419152's fast path in [SG]ETELEM!) would need to hold the resulting denseness-test lock until they've sampled or mutated dslots and rendered themselves safe from racing mutation.

Comment 3

[Brendan Eich [:brendan]]

I have a different and much simpler proposal that has zero risk to ST benchmark results: don't share dense arrays among threads. Force them to be sparse as they cross the inter-thread barrier, just as we force dependent and mutable strings to be flat and immutable. See js_FinishSharingTitle in jslock.c.

/be

Comment 5

[Jason Orendorff [:jorendorff]]

Even though this has useful discussion, duping back to bug 417501 because it's mentioned by number in jsarray.cpp.

Comment 6

[Jason Orendorff [:jorendorff]]

This is not really the same thing as 417501.  That bug is about a very specific problem, but that isn't the only problem with sharing arrays across threads.

This situation is ugly.  Let's resolve it one way or the other.

To fix this, comment 3 would be the way to go.  Spelling it out a bit:

1. Do not give dense arrays titles.  Do not add double-checks or locking to dense array code.
2. In js_FinishSharingTitle, when the object being shared has a dense array in a slot, slowify that array. (Avoid racing with a third thread here--tricky.)
3. (extra credit) Add a new API, JS_MakeArrayThreadSafe, analogous to JS_MakeStringImmutable (which seems misnamed to me), for when C/C++ code might share the array across a thread boundary.

Bug 417501 would be fixed in passing.

But. If embedders can do without this object-sharing feature of JS_THREADSAFE, we should dump it, rid ourselves of some recurring migraines, and likely score a nice speedup.

Set aside dense arrays for a second. AFAICT we take no locks on trace. A thread executing JIT code can read an object owned by another thread. There are obvious races here, e.g. between a shape guard and the following slot read. By making ShareTitle change the shared object's shape, we might arrange for the JIT to bail off trace and preserve correctness when it stumbles across an unexpectedly shared object. Do we do this? If so, I didn't find it; if not, fine. My sense (please correct me) is that we don't want to support threads sharing objects at all, much less under the JIT, and we want to work toward a world where --enable/disable-threadsafe affects at most jsgc.

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #6)
> This is not really the same thing as 417501.

Thanks for catching this.

> To fix this, comment 3 would be the way to go.

Yes, that's what I said ;-). Great to see this bug get attention. Are you gonna grab assignment, or should someone else?

> Spelling it out a bit:
> 
> 1. Do not give dense arrays titles.

We should arrange things so dense arrays don't even have maps. Different bug, not sure it's on file. Anyone know?

> Do not add double-checks or locking to dense array code.

Amen.

> 2. In js_FinishSharingTitle, when the object being shared has a dense array in
> a slot, slowify that array. (Avoid racing with a third thread here--tricky.)

Yes, js_MakeArraySlow needs work. It could use js_CompareAndSwap to fight to update the map, loser frees its scope and retries... Such races are likely rare.

> 3. (extra credit) Add a new API, JS_MakeArrayThreadSafe, analogous to
> JS_MakeStringImmutable (which seems misnamed to me), for when C/C++ code might
> share the array across a thread boundary.

We should rather change the API so everything's thread local (in a thread-local GC heap) and becomes shared only when an API is called or when one goes through the title-sharing barrier.

JS_MakeStringImmutable is not just about MT access. It guarantees NUL backstop and no reallocs of chars.

> But. If embedders can do without this object-sharing feature of JS_THREADSAFE,
> we should dump it, rid ourselves of some recurring migraines, and likely score
> a nice speedup.

There are valid use-cases for multi-threaded objects, but they are exceptional and they should pay an API and barrier penalty.

> My sense (please correct me) is that we don't want to support threads
> sharing objects at all, much less under the JIT, and we want to work toward a
> world where --enable/disable-threadsafe affects at most jsgc.

The original idea with the JIT is that the compiled trace runs to completion, does not yield its request, so can assume single-threaded ownership of its objects. We didn't follow through on this beyond checking that the global object is single-thread-owned (see top of js_RecordLoopEdge).

I do not believe we should ban all multi-threaded GC-things. Rather, we should penalize them. If we give them unique shapes then the recorder can check for ST objects, abort if so, otherwise shape guard FTW.

/be

Comment 8

[Igor Bukanov]

(In reply to comment #7)
> There are valid use-cases for multi-threaded objects, but they are exceptional
> and they should pay an API and barrier penalty.

The problem with the current API is that it assumes that *any* object can be shared between threads. The life would be mush easier if only sealed read-only objects or objects specially marked at birth could be shared. Alternatively the engine could also provide special proxies that the embedding could use to share objects between threads.

Comment 9

[Jason Orendorff [:jorendorff]]

(In reply to comment #7)

> > To fix this, comment 3 would be the way to go.
> 
> Yes, that's what I said ;-). Great to see this bug get attention. Are you
> gonna grab assignment, or should someone else?

I'll take this eventually.  Leaving it unassigned for now in case someone gets inspired.

> JS_MakeStringImmutable is not just about MT access. It guarantees NUL backstop
> and no reallocs of chars.

Ah, thanks.

> > My sense (please correct me) is that we don't want to support threads
> > sharing objects at all, much less under the JIT, and we want to work toward a
> > world where --enable/disable-threadsafe affects at most jsgc.
> 
> The original idea with the JIT is that the compiled trace runs to completion,
> does not yield its request, so can assume single-threaded ownership of its
> objects. We didn't follow through on this beyond checking that the global
> object is single-thread-owned (see top of js_RecordLoopEdge).

Yes, I saw that, but for some reason didn't see the grander plan.

(Right now a trace can yield its request, bug 480301, but we have to fix that anyway...)

> I do not believe we should ban all multi-threaded GC-things. Rather, we should
> penalize them. If we give them unique shapes then the recorder can check for
> ST objects, abort if so, otherwise shape guard FTW.

This is a good idea!  I think it needs a separate bug, which I would file, but my baby just woke up...

Comment 10

[Jason Orendorff [:jorendorff]]

Filed bug 485988.

Comment 11

[Brian Crowder]

Mass unowning JS bugs...  I'm not likely to be able to move these forward.

Comment 12

[Jason Orendorff [:jorendorff]]

Our GVAR and UPVAR optimizations make the fix outlined in comment 6 insufficient for embeddings that share a global or closures across racing threads. Those instructions read properties of global/Call/Block objects without passing through FinishSharingTitle.

In fact I think we have a separate bug where GVAR could race with another thread resizing the global object.

And I think we have another separate bug where we'll run JIT code in multiple threads running against the same global, something I thought we tried to avoid in the tracer.

Comment 13

[Brendan Eich [:brendan]]

Sharing mutable globals and closures across threads is nuts. Certainly we should firewall better but we should not support these insane combinations.

> In fact I think we have a separate bug where GVAR could race with another
> thread resizing the global object.

How is this a problem? GVAR memoizes slots of permanent (non-configurable) global variables. Resizing doesn't matter. Clearing could, but that would be nuts.

jstracer.cpp checks:

    if (cx->fp->scopeChain->getGlobal()->scope()->title.ownercx != cx) {
        AbortRecording(cx, "Global object not owned by this context");
        return MONITOR_NOT_RECORDING; /* we stay away from shared global objects */
    }

in TraceRecorder::recordLoopEdge. Is this enough?

/be

Comment 14

[Mike Shaver (:shaver emeritus)]

Can't resizing mean that the old dslots address becomes invalid, due to a copying realloc?

Comment 15

[Brendan Eich [:brendan]]

GVAR ops don't stash dslots copies, they only memoize slot numbers, and in thread local (JSStackFrame.slots) storage. The actual dslots dereferencing is done only at runtime, by obj->getSlotMT(cx, slot).

This is all crazyland, though -- don't share mutable globals among threads!

/be

Comment 16

[Mike Shaver (:shaver emeritus)]

Sure, but the running GVAR will sample dslots, and then the other thread reallocs it, and then GVAR derefs based on the sampled address.  We're talking about a race, not invalidation of GVAR's data, right?

I concur with the crazyland diagnosis, though.

Comment 17

[Brendan Eich [:brendan]]

(In reply to comment #16)
> Sure, but the running GVAR will sample dslots, and then the other thread
> reallocs it, and then GVAR derefs based on the sampled address.

No. Please to be reading the code:

BEGIN_CASE(JSOP_GETGVAR)
BEGIN_CASE(JSOP_CALLGVAR)
    slot = GET_SLOTNO(regs.pc);
    JS_ASSERT(slot < GlobalVarCount(fp));
    METER_SLOT_OP(op, slot);
    lval = fp->slots[slot];
    if (JSVAL_IS_NULL(lval)) {
        op = (op == JSOP_GETGVAR) ? JSOP_NAME : JSOP_CALLNAME;
        DO_OP();
    }
    JS_ASSERT(fp->varobj(cx) == cx->activeCallStack()->getInitialVarObj());
    obj = cx->activeCallStack()->getInitialVarObj();
    slot = JSVAL_TO_INT(lval);
    rval = obj->getSlotMT(cx, slot);
    PUSH_OPND(rval);
    if (op == JSOP_CALLGVAR)
        PUSH_OPND(JSVAL_NULL);
END_CASE(JSOP_GETGVAR)

and (jsobjinlines.h):

inline jsval
JSObject::getSlotMT(JSContext *cx, uintN slot)
{
#ifdef JS_THREADSAFE
    /*
     * If thread-safe, define a getSlotMT() that bypasses, for a native
     * object, the lock-free "fast path" test of
     * (obj->scope()->ownercx == cx), to avoid needlessly switching from
     * lock-free to lock-full scope when doing GC on a different context
     * from the last one to own the scope.  The caller in this case is
     * probably a JSClass.mark function, e.g., fun_mark, or maybe a
     * finalizer.
     */
    OBJ_CHECK_SLOT(this, slot);
    return (scope()->title.ownercx == cx)
           ? this->lockedGetSlot(slot)
           : js_GetSlotThreadSafe(cx, this, slot);
#else
    return this->lockedGetSlot(slot);
#endif
}

and (jslock.cpp) js_GetSlotThreadSafe.

/be

Comment 18

[Brendan Eich [:brendan]]

https://developer.mozilla.org/En/SpiderMonkey/Internals/Thread_Safety covers the barrier-free (GC macro-barrier via request model) title stuff.

/be

Comment 19

[Mike Shaver (:shaver emeritus)]

Because shut up, that's why!

Comment 20

[Brendan Eich [:brendan]]

Shaver: I did not mean to give offense -- or were you talking to someone else?

Chatting on IRC more, in light of bug 558861 and bug 558866 especially, we should not be doing more than minimal patching for the ST-only native objects. This bug is about dense arrays, though, which are non-native.

What came out on IRC but really from jorendorff debugging was that while it would be ok to slowify for the interpreter, the JIT doesn't emit code to unlock or do anything like js_[GS]etSlotThreadSafe. Nor should it.

So I think we should WONTFIX this bug and get on with the ST-only natives that can (if they consent) become MT proxies work.

sayrer made this point of order on IRC, which should have saved us time, but we had a few mysteries to solve (why the test didn't hit the breakpoint -- JIT or fat fingers -- and maybe another one I'm forgetting). It's fine to get greater understanding of the problem. But we don't want *any* solution, especially one that will slow down the JIT.

/be

Comment 21

[Mike Shaver (:shaver emeritus)]

I was making fun of myself for not understanding what I was talking about.  It all rots so quickly.  :-P

Comment 22

[Robert Sayre]

(In reply to comment #20)
> 
> So I think we should WONTFIX this bug and get on with the ST-only natives that
> can (if they consent) become MT proxies work.

Yes, this bug is a WONTFIX. We already have other bugs filed to achieve similar goals in different ways.