Currently scripts can go into infinite loops and we never recover from it. Suggested solution: Set an alarm signal and modify the JIT code from the signal handler to side-exit on the loop-guard (LIR_loop/LIR_x).

(In reply to comment #0) > Set an alarm signal and modify the JIT code from the signal handler to > side-exit on the loop-guard (LIR_loop/LIR_x). Is it sound given that it is unknown where the native PC is? Or is the idea to modify any jump in the code to jump to a timeout handler? Still if the native jump offset would touch the cache line boundary, then such patching could not be done atomically without much extra efforts. For example, like turning the execute bit for the JIt code off, replacing the generated code in the signal handler for the page fault, and resuming execution after that. I think more sound alternative would be to suspend the thread executing JIT code, recover the native PC from the register image of the suspended thread and then patch the PC to point to the timeout handler code.

Each iteration of the loop goes past the loop tails (LIR_x/LIR_loop), which technically speaking are guards, so the stack state is clean (registers don't contain anything, everything is in memory, we know how to restore the interpreter state from here). We can change these branches to jump out of the loop. Or in the alternative we can insert a branch at the top of the loop out of it. As a third alternative we can simply change around arbitrary branches in the loop since every branch is always re-executed by the interpreter (re-evaluated and then re-executed). Since GC trashes the code cache anyway, just making all guards you can find fail would be sufficient.

(In reply to comment #2) > We can change these branches to jump out of the loop. Or in the alternative we > can insert a branch at the top of the loop out of it. As a third alternative we > can simply change around arbitrary branches in the loop since every branch is > always re-executed by the interpreter (re-evaluated and then re-executed). Currently the operation callback allows to resume the interpretation if desired. To support that it would be necessary to restart the interpreter from the interrupted state. So making sure that the jump comes from a known place with a known interpreter state is important to recover the state. From that point of view the second or the first alternatives are preferable. > Since GC trashes the code cache anyway, just making all guards you can find fail would be sufficient. Mutating the code from the GC is very different from mutating the code from another thread or a signal handler. The GC stops all the threads but the signal handler would try to patch the currently executing code. So at least suspending the thread is a must.

(In reply to comment #3) > Currently the operation callback allows to resume the interpretation if > desired. To support that it would be necessary to restart the interpreter from > the interrupted state. So making sure that the jump comes from a known place > with a known interpreter state is important to recover the state. From that > point of view the second or the first alternatives are preferable. This seems doable. Could we insert a call to a FASTCALL builtin (jsbuiltins.cpp, builtins.tbl) that calls the operation callback? We'd leave the code patched to call the builtin every time, but that could be the price of running too long. The builtin could amortize calls using the op counter. > > Since GC trashes the code cache anyway, just making all guards you can find > fail would be sufficient. > > Mutating the code from the GC is very different from mutating the code from > another thread or a signal handler. The GC stops all the threads but the signal > handler would try to patch the currently executing code. So at least suspending > the thread is a must. TraceMonkey keeps its trace recordings and code cache in JSThread, so no locking and no cross-thread sharing. So no need for stop-all-threads. /be

(In reply to comment #4) > TraceMonkey keeps its trace recordings and code cache in JSThread, so no > locking and no cross-thread sharing. So no need for stop-all-threads. The cross-thread sharing is not an issue here. The problem is to ensure the atomic code patching so a CPU would not see halve-patched jump because the jump offset covers the cache line boundary. A simple way to ensure that is to suspend the thread that executes the long-running code.

That sounds good in general. For the main thread, with signals at least, memory is coherent. And the main thread is where we need this defense, as the DOM is main-thread-only (DOMOperationCallback). This is the short term priority. /be

(In reply to comment #4) > This seems doable. Could we insert a call to a FASTCALL builtin > (jsbuiltins.cpp, builtins.tbl) that calls the operation callback? We'd leave > the code patched to call the builtin every time, but that could be the price of > running too long. If it would be possible to transfer the state from the JITed code back into the interpreter, it would allow to attach the JS debugger to it in the same way as it is possible currently on the mainline. So unless it would require way too much efforts, I would prefer to spend time to ensure the possibility of switching-off the JIT on-fly.

(In reply to comment #6) > For the main thread, with signals at least, memory is coherent. From the past experience with signals the best way to deal with them is to avoid them. Plus what is wrong with creating a watch dog thread that would suspend the main thread, then do its job, then restart the main thread? Yes, the would be issues with ensuring that the thread terminates when the runtime is destroyed, this is doable in a portable way.

As long we find a way to preempt the currently running tree everything else is pretty much downhill. We could also insert an int3 breakpoint at the loop entry. That shouldn't interfere with asynchronous fetch & decode since its just 1 byte.

Another slightly create approach would be to suspend the thread and then walk it to the nearest guard "by hand" through single-stepping. Once at the guard we are automatically in a safe-point and we can divert pc to the guard exit stub, have it recover the interpreter state, and the tree is preempted.

Tension between wanting some watchdog on content scripts for alpha 2 (where the TM JIT will be pref'ed off but people can use about:config to turn it on), and wanting a general solution for a3/b1. Can we have ultra-short- and longer-term wins? Igor: agree about signals. IIRC Ken Thompson said once that they were meant to be either fatal, or ignored, and attempts to give them resumption semantics ever since have been unsatisfying (or doomed). Still, POSIX says... /be

Yet another issue to consider is that currently the GC is scheduled from the operation callback. Unless the JITed code survives the GC, supporting that requires to be able to restart the interpreter from the point where JITed code triggered the callback.

Here is the current plan: 1. Replace the operation counter by a flag that would be set from a watchdog thread after a JSContext spends too much time in begin/endrequest pair. This alone would allow to remove the code that increases the operation counter with arbitrary weights and address the bug 410655. 2. Detect if the long running JS thread executes inside JITed code. It would be nice to be able to do that via recovery of the native PC of the thread and checking where it points. It would allow, for example, to modify only the nearest jump in the JIted bytecode or avoid patching the code at all via direct PC modification in the suspended thread image. 3. Try to implement the restart of the interpreter from the point where JITed codes stopped. If that would work, then the problem is solved. If that would not work without too much efforts, then it would be necessary to ensure that the JITed code survives the GC or any other operation that can be executed currently from the branch callback.

Just wanted to CC myself here and point out that the DOM threads use the operation callback to suspend/resume long-running JS when navigating away from a page and back. So, for instance, turning tracing on by default will break that feature until a fix lands.

Igor, any updates here?

(In reply to comment #15) > Igor, any updates here? My current plan is to reimplement the operation counting in the traced code as a safe backup plan. With the bug 453157 addressed it should not be particularly heavy. Father optimizations like code mutations or forced PC change can be implemented later.

yeah, if the flag is on the context, then the address to check is trace-constant and should be a pretty cheap guard.

Any added counter increment/mask/test/branch is going to hurt the bitops-*.js SunSpider tests. It's also just not needed for those. Is Plan A (watchdog thread) really hard? Help is available on #jsapi for jstracer and nanojit hardness. /be

The watchdog thread is the plan, AIUI. The trace-emitted code would just check to see if the flag was set (I presume as part of the existing end-of-loop guard condition). The watchdog thread would set the flag when it expired, and then later on we can change the watchdog's action to patch the jump target or whatever.

Ok -- still gonna hurt. Let's find out how much. Andreas may be able to help us get to plan A (capital A), which involves no pessimistic flag checking while on trace. /be

(In reply to comment #19) > The watchdog thread would set the flag when it expired, and then > later on we can change the watchdog's action to patch the jump target or > whatever. That is exactly the idea. Suppose currently the generated code contains a backward jump. Then the minimal approach would be to modify that code to have if (cx->someFlag) { if (!callCallback()) goto error; } jmp some_location; where someFlag is set from a watchdog thread. The smart way with code patching is to duplicate the jump so the code looks like: jmp some_location; ... flag_check: if (cx->someFlag) { if (!callCallback()) goto error; } jmp some_location; Then the watchdog thread can patch the first jump to turn the whole code into: jmp flag_check; ... flag_check: if (cx->someFlag) { if (!callCallback()) goto error; } jmp some_location; So the minimal approach is just a step towards implementing the patching schema with no temporary throw-away solutions.

About plans: I am traveling this week so the minimal solution would probably be implemented during the next week. If this is too late, feel free to grab this bug in the mean time.

blocking1.9.1+ per triage w/ Brendan, Andreas, and danderson.

Here is yet another problem with calling operation callback from the jited code. In the browser workers threads use the callback to suspend the current request. That means that the main thread can do the full GC. This effectively means that calling operation callback should terminate the current trace and transfer the control back to the interpreter.

Same mechanism. We need a flag that can be set that causes JIT code to terminate. This flag can be virtual (flipping all tail branches from never-exit to always-exit), or an actual flag we check at every iteration (slow but easy to implement).

I'm grumpy about any mandatory overhead on JITed code from pessimistic APIs. Thread scheduling can be done preemptively with web workers, iloop detection likewise. GC self-scheduling is a different topic, we should not abuse the op callback for that if we can do better (do work from the allocator). We're trying to avoid being slower than V8 and SFX and every bit helps. /be

(In reply to comment #26) > I'm grumpy about any mandatory overhead on JITed code from pessimistic APIs. > Thread scheduling can be done preemptively with web workers, iloop detection > likewise. GC self-scheduling is a different topic, we should not abuse the op > callback for that if we can do better (do work from the allocator). I very much agree that the callback should only be used to stop ill-looping scripts. The bug 455548 and bug 453432 should allow for that. But then to stop such scripts it still will be necessary either to direct their execution to exit branch via a flag that they would check (like cx->operationCount < 0) or mutate all their tail branches indeed.

Graydon has been poking around in nanojit as of late. Maybe he has some comments on this.

Igor, are you actively working on this? I have time to work on this/help you out.

I tested the perf impact of adding a guard on a 'callbackPending' context field to every back edge (LIR_loop). All SunSpider tests were essentially unaffected, except access-fannkuch, which was 2x as slow, giving a total slowdown on 1.05x on the suite.

It looks like the machinery in my perf test patch and bug 453157 provide most of what's needed for a basic implementation of script timeouts. One particularly simple solution is to set the timeout so that the browser is notified about as often as it is now, and otherwise leave the browser timeout code as it is (maintaining its own separate timer to decide when to actually halt the script). I did a quick test and found that DOMOperationCallback gets called with a median interval of .033 seconds on my machine. Otherwise we would have to rewrite the browser code that initiates scripts to also start a timer on the context, and also arrange to halt the timer when the script finishes. This doesn't seem very hard but is certainly more work. Another thing I started wondering about is how the timer will interact with other delays, like the cycle collector. Will that kind of pause make it look like the script has timed out when it really hasn't? Do we need to create a mechanism that can has the effect of more accurately measuring the duration that the script has actually been running? This could be done by "pausing" the timer when the script calls out to CC or any other long-running external function. I don't think that's too hard either but I'm pretty sure it would require modifications to the design of the patch in bug 453157. If we would like a working solution for b1, I might recommend just jitting the existing operationCount instrumentation into loop exits along the lines of my patch here. I'd guess it would cost about 5-20% in perf but should be very quick to implement.

I don't think Brendan will like 5-10% perf hit.

(In reply to comment #32) > I don't think Brendan will like 5-10% perf hit. To avoid performance hit it is must to avoid calling GC and JS_SuspendRequest in the operation callback. With these 2 removed the callback frequency will go down to 15-30 seconds instead of the current 0.1 or so. Then after mutating the code it would not be necessary to restore it back to gain the performance. Moreover, with such long pause a solution can be simply to enumerate all the traces that exists for the current thread and patch their trailing backward jump to point to the callback calling code. Or, even simpler, if the JS would never be allowed to run more then given amount time, to direct the jumps top the terminating code and then call the GC.

(In reply to comment #29) > Igor, are you actively working on this? I have time to work on this/help you > out. No, I focus on bug 455548 to minimize the number of things the callback is doing.

Well, this seems to do the trick, with minimal SunSpider regression inside the browser (I'll put the comparison in another attachment). This goes on top of the watchdog patch from bug 453157.

This is just a migration and refresh of the patch I posted in Bug 453157. It depends on that bug's watchdog timer thread to work properly. I have it functioning in a firefox build here, seems able to interrupt compiled infinite loops and whatnot.

It occurred to me to check -- now that we're expecting asynchronous notification from a watchdog thread anyways -- whether it's particularly expensive to just *read* the context operation count variable at the bottom of each loop and do a conditional branch exit, rather than this hot-patching of an unconditional branch. Turns out I can't measure any speed difference at all. At least not on my machine, on sunspider. IOW, the patch attached here works just as well, is smaller and more comprehensible, and lets me back out all the complexity associated with patching code while running. Personally, I'd prefer to land this variant (and subsequently back out the other changes). Any opinions?

As described in the "simpler approach" patch above, this followup would back out the unwelcome parts of the prep work in revs 9d4c8de84579 and 040e5ac010b1.

Comment on attachment 347865 [details] [diff] [review] connect watchdog to tracer code-patching system >+++ tracemonkey.d6d01dc92b3b/js/src/jsbuiltins.cpp 2008-11-12 14:36:43.000000000 -0800 > js_CallTree(InterpState* state, Fragment* f) > { ... > GuardRecord* rec; >+#if !JS_HAS_OPERATION_COUNT >+ JS_LOCK_GC(state->cx->runtime); >+ JS_TRACE_MONITOR(state->cx).traceDepth++; >+ JS_UNLOCK_GC(state->cx->runtime); >+#endif This still does not allow to use an event-based approach for JS_TriggerOperationCallback. If the latter is called right before js_CallTree enters the lock, the code would not patch the trace. Thus this call to JS_TriggerOperationCallback will be lost. It is OK with periodic calls to JS_TriggerOperationCallback, but this is exactly the thing that prevents utilizing DOM workers with maximum efficiency. The remedy should be simple here: the code should just query if the operationCount is 0 after the lock and return to the interpreter and/or call the operation callback itself.

Comment on attachment 347885 [details] [diff] [review] much simpler and less horrifying approach >diff -r a9f1d3e6b7b6 js/src/jstracer.cpp >--- a/js/src/jstracer.cpp Wed Nov 12 12:40:45 2008 -0800 >+++ b/js/src/jstracer.cpp Wed Nov 12 16:17:36 2008 -0800 >@@ -2246,6 +2246,12 @@ > compile(fragmento); > } else { > exit->target = fragment->root; >+ exit->exitType = TIMEOUT_EXIT; >+ lir->insGuard(LIR_xt, >+ lir->ins_eq0(lir->insLoad(LIR_ld, >+ cx_ins, >+ offsetof(JSContext, operationCount))), >+ exitIns); > fragment->lastIns = lir->insGuard(LIR_loop, lir->insImm(1), exitIns); > compile(fragmento); > } I guess for the maximum efficiency the patch should make operationCount the first field in JSContext. Then the machine code would just dereference cx, not cx + offset, presumably generating less code.

(In reply to comment #41) > I guess for the maximum efficiency the patch should make operationCount the > first field in JSContext. Then the machine code would just dereference cx, not > cx + offset, presumably generating less code. Also should the type for operationCount be word, not int32, for maximum effects on 64bit CPUs?

(In reply to comment #38) > -- whether it's particularly > expensive to just *read* the context operation count variable at the bottom of > each loop and do a conditional branch exit, rather than this hot-patching of an > unconditional branch. I would also very much prefer the simplicity of this approach, but what about the comment 30? And how this affects performance of the simplest possible benchmark like: function f(N) { for (var i = 0; i != N; ++i); return i; } f(1000*1000); //warmup the tracer var time = Date.now(); f(10*1000*1000); print("Test time:"+Date.now() - time);

Ugh, that'll teach me to read the entire bug before barging in! Of course my patch above is identical to dmandelin's (except slightly messier). Sigh. Well, having fiddled with this for over a week now, I've come back to where dmandelin started, but now I'm looking at his number (which I can reproduce) and wondering if it's all been worthwhile: the alternative (patching jumps) is really quite intrusive, and the performance hit is only really significant (the 5-7% range) on tiny loops like the above. On sunspider it's ... at best 1%. I suppose we can use either. If it were up to my taste, I'd take the hit and avoid playing with code patching. But that is in violation of The One True Rule. So I guess patching it is.

Whats the perf impact on regular expression code? (which also need timeouts) Just curious.

(In reply to comment #45) > Whats the perf impact on regular expression code? (which also need timeouts) > Just curious. Mechanism isn't adapted to regexes yet. They have different side exit structures. I'll incorporate them once we've actually chosen a mechanism.

Igor correctly identified a race (non-fatal, but still) in the watchdog code-patching variant. This patch updates it, and refreshes to the newest version of the watchdog thread patch in bug 453157. Still not clear on which of these two to actually commit.

Comment on attachment 348130 [details] [diff] [review] update to watchdog jit that corrects for race igor identified >diff --git a/js/src/jsbuiltins.cpp b/js/src/jsbuiltins.cpp >+#if !JS_HAS_OPERATION_COUNT >+ JS_LOCK_GC(state->cx->runtime); >+ JS_TRACE_MONITOR(state->cx).traceDepth++; >+ /* >+ * We re-check the operation count ourselves here in case we raced with >+ * JS_TriggerOperationCallback, and it cleared the operation count in >+ * between the last time we checked and the time we just incremented the >+ * trace depth above. >+ */ Nit: a blank line before multiline comment. >diff --git a/js/src/jstracer.cpp b/js/src/jstracer.cpp ... >+#if !JS_HAS_OPERATION_COUNT >+ JS_LOCK_GC(cx->runtime); >+ tm->traceDepth++; >+ /* >+ * We re-check the operation count ourselves here in case we raced with >+ * JS_TriggerOperationCallback, and it cleared the operation count in >+ * between the last time we checked and the time we just incremented the >+ * trace depth above. >+ */ Nit: a blank line before multiline comment. r+ with the nits addressed.

This patch is the patch from the comment 38 with JSContext.operationCount moved to the first place in JSContext to to make the generated code as light as possible. Would lir->insLoad(LIR_ld, cx_ins, 0) optimize for zero offset? To Graydon: could you benchmark this as well? For some reason I am having way too much noise on 64-bit Linux box to have any conclusion.

Igor: shifting the location of the field around does not make a measurable difference. But in the process of checking this, I did more careful comparisons of timing, and found something quite disappointing: all the locking in the code-patching approach causes a significantly worse slowdown still. On the order of 5%. It appears cheaper all around to use the original, simpler approach. Unless we can come up with some kind of lockless way of modifying the fragments, which I'm having a hard time picturing. Perhaps we could lock every other code path that every modifies the fragmento? I can try developing such an alternative.

Ugh, I take that back. The fragmento is accessed all over the place. Locking all possible mutators would be quite a complex patch. I'm voting for the simpler patch. This bug is high priority and it's going on way too long. (Also we're still blocking on bug 453157 landing. It's the more serious one!)

We should use the simpler patch and avoid patching. We don't need to reorganize fields in JSContext so long as the operationFoo one is close to the front. The cx is in a reg on loop edge (we may optimize that away, but not soon), and Andreas is probably right that on a small or medium traces the load is hitting an L1 cache line. /be

We might move the operationFoo member to make sure it's not in a suboptimal cache line, at most. We shouldn't move it to be first. /be

Just to confirm that "what gets committed got reviewed", this is the version I have in mind. It's mostly identical to dmandelin's initial patch, and appears to have the least performance impact (when coupled with the watchdog timer thread) of any combination tried.

Comment on attachment 348270 [details] [diff] [review] slightly cleaned up, proposed final variant >diff -r 23121402a8be js/src/jstracer.cpp >--- a/js/src/jstracer.cpp Fri Nov 14 15:09:33 2008 -0800 >+++ b/js/src/jstracer.cpp Fri Nov 14 15:37:15 2008 -0800 >@@ -2300,6 +2300,10 @@ > compile(fragmento); > } else { > exit->target = fragment->root; >+ exit->exitType = TIMEOUT_EXIT; >+ guard(false, lir->ins_eq0(lir->insLoadi(cx_ins, >+ offsetof(JSContext, operationCount))), >+ exitIns); Drive-by nit: with overflowing args, please put each on its own line underhanging at the same starting column. Thanks, /be

Comment on attachment 348270 [details] [diff] [review] slightly cleaned up, proposed final variant IIRC operationCount is decreased so that it goes to zero or below, or was. Is the watchdog thread just zero'ing now? If so, this is good. If not, then you want the LIR_gt 0 guard that dmandelin's patch used. /be

Comment on attachment 348270 [details] [diff] [review] slightly cleaned up, proposed final variant operationCount is a totally misleading name. As long it is a boolean, r=me but please rename.

Comment on attachment 348270 [details] [diff] [review] slightly cleaned up, proposed final variant From the patch in the watchdog bug it looks like the eq0 guard is good, but only #if !JS_OPERATION_COUNT. Do we need that #if around a #error before this function? /be

It's still a count of operations when used w/o the watchdog timer thread; it becomes a boolean flag when used with the timer thread. It's conditional on #ifdef JS_HAS_OPERATION_COUNT. I don't think I need to #error if !JS_HAS_OPERATION_COUNT, but I can guard this code on it and omit it when there won't be a watchdog thread either way. People will still sometimes want to build w/o threads, I imagine.

Pushed to tracemonkey in revision 94ac046a4332, with appropriate ifdef guards so at the moment it's inert.Still needs Andrei's patch to make it spring into action.

(In reply to comment #52) > We should use the simpler patch and avoid patching. > > We don't need to reorganize fields in JSContext so long as the operationFoo one > is close to the front. I assume that at least on some architectures dereferencing cx generates smaller code than dereferencing cx[wordOffset]. Thus the idea of moving the flag to the first place to save potentially on code cache.

(In reply to comment #61) > I assume that at least on some architectures dereferencing cx generates smaller > code than dereferencing cx[wordOffset]. Thus the idea of moving the flag to the > first place to save potentially on code cache. That could save a byte, but only at the very bottom of the trace. It's hard to imagine it would matter, but so long as the ugliness of moving cx->links away from offset 0 is not worse in code size, then *maybe*. But what are the effects of moving links away from offset 0? /be

(In reply to comment #62) > That could save a byte, but only at the very bottom of the trace. Plus it would safe a byte in the interpreter for each branch opcode and in other places that checks the flag for the price of increasing the size of code that access cx->links. This is less frequent code-wise and much less frequent execution-wise.

Ok, let's try the 0-offset patch. We can land in tracemonkey now that http://hg.mozilla.org/tracemonkey/rev/94ac046a4332 is in. Igor, do you want to get request review? The only thing I'd like is a macro analogous to CX_FROM_THREAD_LINKS (wish I had not pluralized LINK there; do not feel compelled to imitate, and do feel free to fix both macros to use LINK singuar ;-). /be

please resolve fixed this bug after patch landed in mozilla-central. Thanks.

Andreas; does this need landing in both t-m and m-c?

I believe the patch here was sufficiently merged on 11/15/2008. http://hg.mozilla.org/mozilla-central/pushloghtml?startdate=11%2F15%2F2008&enddate=11%2F16%2F2008 Graydon, please reopen if this is incorrect.

Code patching machinery backed out in TM revision e0a276494293. This is just tidying up from the approach that turned out not to work; it was dead code. No need to reopen the bug.