76233 - deadlock between regular expressions and GC

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[itaj sherman]

in my application i'm running a few JS threads simultaneously running the same 
script.
the script that made that problem occure is using regular expressions and 
creates many strings (so GC is activated many times).

when running this script i always got deadlocked very fast.

i run the script on 10 threads simultaneously, when the deadlock occured i 
breaked my debugger and looked at the threads' status:

in my application i have a native Sleep() function that can be called by the JS 
script, this function is wrapped by JS_EndRequest() and JS_BeginRequest(), so 
GC can be activated in the idle time.
8 of the threads where inside that function waiting on the PR_WaitCondVar() 
inside JS_BeginRequest().
the 2 other threads are:

1) the thread that was holding them 8 was in GC, because it went out of memory.
this is the stack of that thread:

PR_WaitCondVar(PRCondVar * 0x022f21a0, unsigned int 4294967295) line 34
js_GC(JSContext * 0x02a6c660, unsigned int 1) line 1077 + 17 bytes
js_AllocGCThing(JSContext * 0x02a6c660, unsigned int 1) line 508 + 11 bytes
js_NewString(JSContext * 0x02a6c660, unsigned short * 0x03c8d774, unsigned int 
2, unsigned int 0) line 2241 + 15 bytes
js_NewStringCopyN(JSContext * 0x02a6c660, const unsigned short * 0x03bcfa24, 
unsigned int 2, unsigned int 0) line 2292 + 21 bytes
js_ExecuteRegExp(JSContext * 0x02a6c660, JSRegExp * 0x023ac55c, JSString * 
0x041b6370, unsigned int * 0x032ddc98, int 0, long * 0x032dde70) line 2148 + 19 
bytes
regexp_exec_sub(JSContext * 0x02a6c660, JSObject * 0x01b4f990, unsigned int 1, 
long * 0x04348ab0, int 0, long * 0x032dde70) line 2739 + 29 bytes
regexp_exec(JSContext * 0x02a6c660, JSObject * 0x01b4f990, unsigned int 1, long 
* 0x04348ab0, long * 0x032dde70) line 2751 + 27 bytes
js_Invoke(JSContext * 0x02a6c660, unsigned int 1, unsigned int 0) line 813 + 26 
bytes
js_Interpret(JSContext * 0x02a6c660, long * 0x032ded58) line 2706 + 15 bytes
js_Execute(JSContext * 0x02a6c660, JSObject * 0x02a76178, JSScript * 
0x032decb4, JSStackFrame * 0x00000000, unsigned int 0, long * 0x032ded58) line 
992 + 13 bytes
JS_ExecuteScript(JSContext * 0x02a6c660, JSObject * 0x02a76178, JSScript * 
0x032decb4, long * 0x032ded58) line 3183 + 25 bytes
JS_ExecuteScriptPart(JSContext * 0x02a6c660, JSObject * 0x02a76178, JSScript * 
0x01b38168, int 1, long * 0x032ded58) line 3217 + 21 bytes
CWLJSThread::ExecScript(unsigned long 9) line 877 + 42 bytes
CLoadThreadInstanceScript::runJScript() line 181 + 18 bytes

what i also found out is that:
- inside regexp_exec_sub() there is a call for JS_LOCK_OBJ(cx, obj). so the 
JSObject at address 0x01b4f990 is locked when js_GC() is called.
- in js_GC() the position was on:
	while (rt->requestCount > 0)
		JS_AWAIT_REQUEST_DONE(rt);
and the value of rt->requestCount was 1

2) the only thread that was after a JS_BeginRequest() was holding the GC in the 
above thread.
this is the stack of that thread:

PR_WaitCondVar(PRCondVar * 0x022f2884, unsigned int 4294967295) line 34
js_SuspendThread(JSThinLock * 0x01aba084) line 864 + 14 bytes
js_Enqueue(JSThinLock * 0x01aba084, long 4314) line 905 + 9 bytes
js_Lock(JSThinLock * 0x01aba084, long 4314) line 938 + 13 bytes
js_LockScope(JSContext * 0x02a8c298, JSScope * 0x01aba05c) line 995 + 13 bytes
js_LockObj(JSContext * 0x02a8c298, JSObject * 0x01b4f990) line 1079 + 13 bytes
js_Interpret(JSContext * 0x02a8c298, long * 0x033ded58) line 2540 + 384 bytes
js_Execute(JSContext * 0x02a8c298, JSObject * 0x02a76b28, JSScript * 
0x033decb4, JSStackFrame * 0x00000000, unsigned int 0, long * 0x033ded58) line 
992 + 13 bytes
JS_ExecuteScript(JSContext * 0x02a8c298, JSObject * 0x02a76b28, JSScript * 
0x033decb4, long * 0x033ded58) line 3183 + 25 bytes
JS_ExecuteScriptPart(JSContext * 0x02a8c298, JSObject * 0x02a76b28, JSScript * 
0x01b38168, int 1, long * 0x033ded58) line 3217 + 21 bytes
CWLJSThread::ExecScript(unsigned long 12) line 877 + 42 bytes
CLoadThreadInstanceScript::runJScript() line 181 + 18 bytes

the script here was trying to access the same reqular expression JSObject at 
address 0x01b4f990, and was waiting for it to be unlocked (in the 
PR_WaitCondVar) - but it is deadlocked.

... i hope the description was understandable.

itaj

Comment 1

[Phil Schwartau]

cc'ing Brendan - 

Comment 2

[itaj sherman]

oops,

i said that the JSObject* was deadlocked, but i couldn't know that, and it was 
probabely not right.
i changed the script to use 'new RegExp()' instead of literal reg exp. then i 
found out that it still gets deadlocked, although the JSObject* are not the 
same in the two threads.
but the JSScope* of these JSObject* was the same - maybe the JSScope* is 
deadlocked. (i've seen that js_LockObj() invokes js_LockScope() )
or maybe something else.
but something there is deadlocked.

itaj

Comment 3

[Brendan Eich [:brendan]]

Hoping this was fixed last week.  More in a bit.

/be

Comment 4

[Brendan Eich [:brendan]]

The bug here is in jsregexp.c, and it's ancient.  It's never a good idea to hold
a JSObject locked and then acquire some other "lock" -- object locks should be
held for short critical sections, and generally are.  But a regexp execution
could take a long time, and likely allocates strings (requiring the GC lock).

This was not fixed lastweek.  It should be fixed for 0.9.  Patch coming up.

/be

Comment 5

[Brendan Eich [:brendan]]

Attachment: proposed fix

Comment 6

[Patrick C. Beard]

r=beard (FWIW)

Comment 7

[Brendan Eich [:brendan]]

I would like to fix this in 0.9.  Deadlock serious, fix in hand.

/be

Comment 8

[Mike Shaver (:shaver emeritus)]

Can we rename js_DestroyRegexp to js_DropRegexp or something that makes it more
clear that it's not necessarily going to destroy anything?

Other than that, sr=shaver.

Comment 9

[Brendan Eich [:brendan]]

I'll fix up names when I fix bug 76717 for 0.9.1.  For 0.9, I'd like to get the
patch as reviewed in.

/be

Comment 10

[Mike Shaver (:shaver emeritus)]

I'll buy that.

sr=shaver

Comment 11

[Asa Dotzler [:asa]]

a=asa for checkin to 0.9

Comment 12

[Brendan Eich [:brendan]]

Fix checked in.

/be

Comment 13

[Phil Schwartau]

Marking Verified -