364776 - Common operation counter

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P3)

Description

[Igor Bukanov]

The bug 310405 introduces a special counter to prevent DOS through long-running loops in a native code. When the counter reaches a certain limit, the branch callback is called. But this adds a parallel infrastructure to branch counting code in the interpreter.

Thus the idea is to integrate both counters into single code. This would allow to avoid calling branch callback on each and every jump in the bytecode. 

The only problem is that less frequent callback calls may break embeddings that depends on the frequency for, for example, scheduling GC.

Comment 1

[Brian Crowder]

Since a bug that depends on this has a blocking1.9? also.

Comment 2

[Brian Crowder]

Not convinced this one of 398086 should block, but Igor (or Brendan?) should make the call.  I'm wildly guessing at P5 for both, if they do?

Comment 3

[Mike Schroepfer]

Seems like if this causes a hang (due to the blocked bug) in a common site we should try and fix...

Comment 4

[Mike Schroepfer]

Hmm - blocked bug doesn't seem so bad because the site seems to have broken js...

Comment 5

[Igor Bukanov]

Attachment: v 0.5

A backup of a prototype.

Comment 6

[Brian Crowder]

I don't have statistics to prove it, but I think this is an important perf-bug.  Raising priority (and wondering why I judged it a P5 before).  Igor, I'd be glad to help out, if you want a hand with driving this through?  This should be doable with low-risk to firefox (since we run the slow-script timer based on wall-clock time).

Comment 7

[Igor Bukanov]

Attachment: v1 - JS engine changes

The new patch adds new operation callback API and a bridges the branch callback to them. The patch allows for an embedding to set an operation limit. When the operation counter reaches the limit, the callback is invoked.

It turned that using the operation counter in the interpreter loop is very sensitive to the code complexity of the operation limit checks. To minimize them the patch changes the operation counting to run from the limit towards 0.

Comment 8

[Igor Bukanov]

(In reply to comment #6)
> I don't have statistics to prove it, but I think this is an important perf-bug.

Consider a test case like:

function test()
{
    for (var i = 0; i != 1000*1000; ++i) {}
}

test();

On my 1.1 GHz Pentium-M laptop against an optimized build of js shell compiled with -Os option the best invocation time as reported by:

~> time ~/m/trunk/mozilla/js/src/Linux_All_OPT.OBJ/js test.js

was 137 ms. Commenting out the body of my_BranchCallback in js.c so it becomes essentially:

static JSBool
my_BranchCallback(JSContext *cx, JSScript *script)
{
    return JS_TRUE;
}
 
and invoking the shell as:

~> time ~/m/trunk/mozilla/js/src/Linux_All_OPT.OBJ/js -b 1 test.js

increased that time to 148 ms. So an empty branch callback added 8% of overhead.

Comment 9

[Igor Bukanov]

(In reply to comment #7)
> Created an attachment (id=293754) [details]
> It turned that using the operation counter in the interpreter loop is very
> sensitive to the code complexity of the operation limit checks. To minimize
> them the patch changes the operation counting to run from the limit towards 0.

For backward compatibility with JS_SetBranchCallback the patch uses the following code:

#define CHECK_BRANCH(len)                                                     \
    JS_BEGIN_MACRO                                                            \
        if (len <= 0 && (cx->operationCount -= JSOW_SCRIPT_JUMP) <= 0) {      \
            SAVE_SP_AND_PC(fp);                                               \
            ok = js_ResetOperationCount(cx);                                  \
            if (!ok)                                                          \
                goto out;                                                     \
        }                                                                     \
    JS_END_MACRO

In principle that check len <= 0 can be dropped as with the sufficiently high operation limit the CPU can predict that the condition is rarely true leading to smaller and faster code. But that would not be backward-compatible as then the branch callback will be called for forward jumps as well.

Comment 10

[Brian Crowder]

(In reply to comment #8)
> So an empty branch callback added 8% of overhead.

Ugh, huge.  And the branch callback in Firefox is -nowhere near- empty.  This is a great bug.

Comment 11

[Brendan Eich [:brendan]]

Comment on attachment 293754 [details] [diff] [review]
v1 - JS engine changes

> JS_SetBranchCallback(JSContext *cx, JSBranchCallback cb)
> {
>     JSBranchCallback oldcb;
> 
>-    oldcb = cx->branchCallback;
>-    cx->branchCallback = cb;
>+    oldcb = NULL;
>+    if (cx->operationCallback) {
>+#ifdef DEBUG
>+        fprintf(stderr,
>+"JS API usage error: call to JS_SetOperationCallback is followed by\n"
>+"invocation of deprecated JS_SetBranchCallback\n");
>+#endif
>+        JS_ASSERT(0);

Move oldcb null init here, since else sets oldcb:

>+    } else {
>+        oldcb = (JSBranchCallback) cx->operationCallbackClosure;
>+    }
>+    if (cb) {
>+        cx->operationCount = cx->operationLimit = JSOW_SCRIPT_JUMP;
>+        cx->operationCallback = NULL;
>+        cx->operationCallbackClosure = (void *) cb;

IIRC ISO C says void* and function pointer are not compatible. Suggest a union for the operationClosure (shorter name too), one arm is void* the other is JSBranchCallback for old time's sake.

>+/*
>+ * Deprecated. It is similar to

Suggest "Note well: JS_SetBranchCallback is deprecated. It is similar to" instead.

>+ *   JS_SetOperationCallback(cx, counter, 1000, NULL)
>+ * except the callback will not be called when the last frame is native

Here and elsewhere in the patch, s/last frame/top-most frame/.

>+             * Do not call the operation callback in the following moving loop
>              * to make it fast and unroot the cached results of toString

Need "to" before "unroot" to avoid split infinitive.

>+        /*
>+         * Support for the deprecated branch callback which can only be called

Suggest comma before "which" and s/can/may/

>+         * when the last frame has an associated script unless

s/last/top-most/ and a comma before unless.

>+ * Decrease the operation count according to the given operation weight and
>+ * call the operation callback when the count becomes 0 or negative. We
>+ * initialize the count initially to JSContext.operationLimit and use

Strike "initially" as redundant.

>+ * subtraction and compression with 0 to minimize code in this frequently

"compression with" should be "clamping against"? Not sure what you mean there.

>+ * used macro.
>+ *
>+ * This macro can run the full GC. Return true if it is OK to continue and
>+ * false otherwise.
>  */
>-JS_STATIC_ASSERT((JSOW_BRANCH_CALLBACK & (JSOW_BRANCH_CALLBACK - 1)) == 0);
>+#define JS_CHECK_OPERATION_LIMIT(cx, weight)                                  \
>+    (JS_CHECK_OPERARTION_WEIGHT(weight),                                      \

Note OPERARTION typo.

>+ * A version of JS_CHECK_OPERATION_LIMIT that just updates the operation count
>+ * without calling the operation callback or any other API. The macro resets

s/The macro/This macro/

>+ * the count to 0 when it becomes negative to prevent an overflow when the

s/an overflow/wrap-around/ I think -- neither "overflow" nor "underflow" is the right word at any rate.

>+ * The implementation of the above macros assumes subtracting weights twice
>+ * from a positive number does not overflow INT32_MIN.

s/overflow/wrap around/ again.

>+/* Relative operations weights. */
>+#define JSOW_JUMP                   1
>+#define JSOW_ALLOCATION             100
>+#define JSOW_LOOKUP_PROPERTY        5
>+#define JSOW_GET_PROPERTY           10
>+#define JSOW_SET_PROPERTY           20
>+#define JSOW_NEW_PROPERTY           200
>+#define JSOW_DELETE_PROPERTY        30
>+#define JSOW_ENTER_SHARP            1000
>+#define JSOW_SCRIPT_JUMP            1000

It would be awesome to write a calibration script for these.

/be

Comment 12

[Igor Bukanov]

Attachment: v2 - JS engine changes

The new version addresses the nits.

Comment 13

[Igor Bukanov]

Attachment: v1-v2 delta

Comment 14

[Igor Bukanov]

(In reply to comment #10)
> 
> Ugh, huge.  And the branch callback in Firefox is -nowhere near- empty.  This
> is a great bug.

In practice it is not that bad as the overhead is only relevant for tight numerical loops. For example, here is number of calls to the callback from the start of the browser:

1050   startup into a blank window
20123  gmail    
23126  yahoo    
32061  msn      
45685  bbc      
47168  shutdown

Comment 15

[Brendan Eich [:brendan]]

Comment on attachment 293828 [details] [diff] [review]
v2 - JS engine changes

>+ * Set the operation callback that the engine call periodically after

s/engine call/&s/

>+ * the internal operation count reaches the specified limit.
>+ *
>+ * When operationLimit is 1000, the callback will be called at least after
>+ * each backward jump in the interpreter. To minimize the overhead of
>+ * the callback invocation we suggest at least 1000*1000 as a value for
>+ * operationLimit.
>+ */
> extern JS_PUBLIC_API(void)
> JS_SetOperationCallback(JSContext *cx, JSOperationCallback callback,
>                         int32 operationLimit, void *closure);
> 
> extern JS_PUBLIC_API(void)
> JS_ClearOperationCallback(JSContext *cx);
> 
> extern JS_PUBLIC_API(void)
>@@ -2110,20 +2119,20 @@ JS_GetOperationCallback(JSContext *cx);
> 
> extern JS_PUBLIC_API(void *)
> JS_GetOperationCallbackClosure(JSContext *cx);
> 
> extern JS_PUBLIC_API(int32)
> JS_GetOperationLimit(JSContext *cx);
> 
> /*
>- * Deprecated. It is similar to
>+ * Note well: JS_SetBranchCallback is deprecated. It is similar to
>  *   JS_SetOperationCallback(cx, counter, 1000, NULL)

Blank (" *\n") line around the call, semicolon at end of call expression statement, for highest readability and code fidelity?

>+ * except the callback will not be called from a long-running native code when

Could use "that" after "except"

s/code/function/

>+ * the top-most frame is native and JSOPTION_NATIVE_BRANCH_CALLBACK is not set.

Should still line-wrap nicely with JSOPTION_... at end of next-to-last commented line of text.

> /*
>  * Update the value to be returned by JS_CStringsAreUTF8().  Once set,
>- * it can not be changed.  Must be called before the first call to 
>+ * it can not be changed.  Must be called before the first call to
>  * JS_NewRuntime.
>  */
> JS_PUBLIC_API(void)
> JS_SetCStringsAreUTF8();

No "French spacing" (double space after period) in modern comments. Could use "This API must" instead of "Must" to start last sentence.

>         if (!all_strings) {
>             /*
>              * Do not call the operation callback in the following moving loop
>-             * to make it fast and unroot the cached results of toString
>+             * to make it fast and to unroot the cached results of toString
>              * invocations before the callback has a chance to run the GC.

Something feels run-on still, so add a comma after "fast"?

>+         * Support for the deprecated branch callback. It may only be called

Nit: "be called only"

>+         * when the top-most frame has an associated script, unless
>          * JSOPTION_NATIVE_BRANCH_CALLBACK is set.

Could perhaps fit everything better and use fewer words without loss of clarity if

s/has an associated script/is scripted/

>+    union {
>+        void                *data;
>+        JSBranchCallback    branchCallback;
>+    }                   operationClosure;

Super-nit: typical style here would not indent operationClosure. Also could just-so indent union arm declarators by one space from the tab stop they missed, instead of to next virtual tab stop.

> #ifdef DEBUG
>     uint32              operationCallbackNesting;
> #endif

Follow-on nit: put a blank line before this #ifdef DEBUG paragraph.

Any calibration script ideas?

/be

Comment 16

[Igor Bukanov]

(In reply to comment #15)
> Any calibration script ideas?

It is not very useful as the branch callback compatibility requires that a backward jump weight should be a constant. As such script jump can correspond to arbitrary complex code.

On the other hand test to measure the relative expensiveness of other operations should be feasible, one would need to generate a long source of repeated operations corresponding to different weights and eval it.  

Comment 17

[Igor Bukanov]

Attachment: test case to measure the callback overhead

the test case measures the time it take for a loop like:

    for (var i = 0; i != 2000 * 1000; ++i) { }

to execute. It runs the test repeatedly and shows the best time.

Comment 18

[Igor Bukanov]

Attachment: v3

Sorry to bother again with a review, but in the new version I rewrote comments significantly noticeably trying to improve the text. But that may bring new abuses of English. 

I also added union JSOperationClosure as it seems this the only way to avoid ugly indentation. I hope this is not too heavy handed approach.

Comment 19

[Igor Bukanov]

Attachment: v2-v3 delta

Comment 20

[Brendan Eich [:brendan]]

Comment on attachment 293948 [details] [diff] [review]
v3

> /*
>  * Note well: JS_SetBranchCallback is deprecated. It is similar to
>+ *
>+ *   JS_SetOperationCallback(cx, counter, 1000, NULL);
>+ *
>+ * except that the callback will not be called from a long-running native
>+ * function when JSOPTION_NATIVE_BRANCH_CALLBACK is not set and the top-most
>+ * frame is native.

Only issue here is pronoun "It" refers to JS_SetBranchCallback, but "the callback" later in the same sentence refers to which callback, |counter| or the cb passed to JS_SetBranchCallback? Suggestion: use "callback" as the name of the actual parameter in the example this comment shows.

> /*
>+ * Update the value to be returned by JS_CStringsAreUTF8(). Once set, it
>+ * can not be changed. This API must be called before the first call to

s/can not/can never/

>+/*
>+ * The union that holds either the closure of the operation count callback or,
>+ * when JSContext.operationCallback is null, a function pointer to the
>+ * deprecated branch callback.

s/operation count callback/operation callback/ in first line, and rest should wrap better.

>+ */
>+typedef union JSOperationClosure {
>+    void                *data;
>+    JSBranchCallback    branchCallback;
>+} JSOperationClosure;

Nice, I should have suggested this.

/be

Comment 21

[Igor Bukanov]

Attachment: v4

Besides addressing the nits the new version disallows calls to JS_GetOperationLimit() when the callback is not set to avoid an extra if there and checks that JS_GetOperationCallbackClosure is not called when the branch callback is set. This should help to prevent bugs when one transition from the branch to operation callbacks.

Comment 22

[Igor Bukanov]

Attachment: v3-v4 delta

Comment 23

[Brendan Eich [:brendan]]

Comment on attachment 293974 [details] [diff] [review]
v4

> JS_PUBLIC_API(void *)
> JS_GetOperationCallbackClosure(JSContext *cx)
> {
>-    JS_ASSERT(cx->operationCallback);
>-    return cx->operationClosure.data;
>-}
>+#ifdef DEBUG
>+    if (!cx->operationCallback && cx->operationPrivate.branchCallback) {
>+        fprintf(stderr,
>+"JS API usage error: call to the deprecated JS_SetBranchCallback is followed\n"
>+"by invocation of JS_GetOperationCallbackClosure\n");

Could lose "the" before "deprecated", line-wrap string contents appropriately.

>+/*
>+ * Get the operation limit associated with the operation callback. The

s/The/This API/

>+ * function may be called only when the result of JS_GetOperationCallback(cx)
>+ * is not null.
>+ */
> extern JS_PUBLIC_API(int32)
> JS_GetOperationLimit(JSContext *cx);

r/a=me with these nits. Thanks again,

/be

Comment 24

[Igor Bukanov]

Attachment: v5

The new version removes operationCallbackClosure assuming that the callback can use JS_GetContextPrivate. To distinguish branch from the operation callback the code uses one bit from the operation limit field.

Partially I put the extra closure field in attempt to address the bug 408539 with an idea to use the context private for XPCConnect and replacing JS_GetContextPrivate with JS_GetOperationCallbackClosure in the rest od code. But as it was pointed out in bug 409109 comment 2 this would bring various compatibility issue.

Comment 25

[Igor Bukanov]

Attachment: v4-v5 delta

Comment 26

[Igor Bukanov]

Comment on attachment 294027 [details] [diff] [review]
v5

A new patch is comming that simplifies things for bug 409109.

Comment 27

[Igor Bukanov]

Attachment: v6

The new version allows to call JS_SetOperationLimit as long as the operation callback is set. It allows to simplify DOM callback implementation in bug 409109.

Comment 28

[Igor Bukanov]

Attachment: v5-v6 delta

Comment 29

[Brendan Eich [:brendan]]

Comment on attachment 294060 [details] [diff] [review]
v6

>+     * Flag indicating that the operation callback is set. When the flag is 0
>+     * but operationCallback is not null, operationCallback stores the
>+     * deprecated branch callback.

Nit: "deprecated" is overkill here, makes things wrap less nicely too. Just "... stores the branch callback"?

>+     */
>+    uint32              operationCallbackIsSet :    1;
>+    uint32              operationLimit         :    31;

Bitfields, should be ok on currently supported target archs. I was wondering about 64-bit targets where unsigned is a 64 bit type -- anyone know the ISO C chapter and verse?

/be

Comment 30

[Igor Bukanov]

(In reply to comment #29)
> Bitfields, should be ok on currently supported target archs. I was wondering
> about 64-bit targets where unsigned is a 64 bit type -- anyone know the ISO C
> chapter and verse?

I do not know a compiler that uses 64 bits for int type on 64-bit CPU. In fact compilers from Microsoft even for 64-bit Windows still define sizeof(long) = 4.

Comment 31

[Igor Bukanov]

Attachment: v6

The version with the last nit addressed. I also changed the comments for JS_SetOperationCallback to use 1e5, not 1e6 as a suggested value for the operation limit. The testing has shown that already with 1e5 or one callback invocation per 100 back jumps the overhead is sufficiently small.

I will check in this after a patch for bug 409109 will be approved. Without switching DOM to the operation callback the test case from comment 17 runs 10% slower rather than 17% faster.

Comment 32

[Igor Bukanov]

I checked in the patch from comment 31 to the CVS trunk:

http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&branch=HEAD&cvsroot=%2Fcvsroot&date=explicit&mindate=1198577520&maxdate=1198577577&who=igor%mir2.org

Comment 33

[Jesse Ruderman]

Backed out in an attempt to fix the Talos red (tgfx failures) that started around the time this was checked in.

Comment 34

[Bill Gianopoulos [:WG9s]]

(In reply to comment #33)
> Backed out in an attempt to fix the Talos red (tgfx failures) that started
> around the time this was checked in.
> 

I wonder if the talos red is actually a Talos issue and is caused by it NOT setting dom.max_script_run_time to 0 like mochitest does.

Comment 35

[Igor Bukanov]

(In reply to comment #33)
> Backed out in an attempt to fix the Talos red (tgfx failures) that started
> around the time this was checked in.

I suggest to check-in this patch again to verify that failures were caused by altered frequency of calling MaybeGC and other checks in the DOM callback that the patch from bug 409109 caused. 

Comment 36

[Igor Bukanov]

Attachment: v7

The new version makes sure that the relative frequency of the callback calls is not altered by the patch. I will file a separated bug to calibrate the numbers.

Comment 37

[Igor Bukanov]

Attachment: v6-v7 delta

Comment 38

[Igor Bukanov]

Attachment: v6-v7 delta for real

Comment 39

[Brendan Eich [:brendan]]

Comment on attachment 294634 [details] [diff] [review]
v7

Good enough if it gets rid of the talos red. Looking forward to that calibration bug.

/be

Comment 40

[Igor Bukanov]

I checked in the patch from comment 36 to the trunk:

http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&branch=HEAD&cvsroot=%2Fcvsroot&date=explicit&mindate=1199352319&maxdate=1199352541&who=igor%mir2.org

Comment 41

[Igor Bukanov]

The landing of the patch from comment 36 has not regressed Ts on boxset and all Firefox tinderboxes have gone with at least one green cycle. So I will check-in the patch for bug 409109.

Comment 42

[Bob Clary [:bc] (inactive)]

something like comment 17 would be appropriate for the js performance suite, but not for the js test suite. marking as in-testsuite- for now.