310405 - Unstoppable too long execution with Array methods

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

Consider the following JS:

Array(0xFFFFFFFF).forEach(Math.sin);

Perhaps a fast computer could execute it within 10 minutes, but on 400 MHz
laptop with recent firefox build from CVS head it would probably take 5 hours or
so. 

The problem is that the browser does not suggest to terminate the long running
script.

Comment 1

[Brendan Eich [:brendan]]

Argh, do we care about this and similar DOS opportunities?  It has always been
possible to write a regexp that takes exponential time backtracking, and there's
no branch callback from the backtracking code.

We would need branch callbacks, amortized appropriately, from at least the array
looping methods, regexp backtracking, and toSource methods.  Anything else
obvious to add to this list/

/be

Comment 2

[Asa Dotzler [:asa]]

We're minusing a lot more severe issues than this. It sounds like we have
similar DOS problems here. If you guys come up with a low-risk patch, please
request approval and we'll consider the patch.

Comment 3

[Igor Bukanov]

Attachment: Implementation v1

The main idea behind the patch is to count "heavy" operations like memory allocation and property access without calling the branch callback and then check the counter at various GC-safe points like loop body of array methods. 

Ideally it would be nice to merge this with the branch checks in the regexp code and the interpreter, add API to adjust the frequency of calls to  the branch callback etc., but even in the current form the patch should stop all those DOS via array methods.

Comment 4

[Igor Bukanov]

Attachment: Implementation v2

This version extends the patch to use in jsregexp.c the new counting macros. The patch adds counter update to PushBackTrackState and changes CHECK_BRANCH to use JS_CHECK_OPERATION_LIMIT.

Comment 5

[Brendan Eich [:brendan]]

Brian's been working on regexp monitoring and optimization, he should have a look too.  Thanks,

/be

Comment 6

[Brian Crowder]

This will conflict with my patch to bug 351487, but the conflicts will be easy to resolve.  If/when this makes it to the trunk, I will update my patch there.  Regexp may benefit nicely from this concept of weighted operations as we start adding things like Perl's success/fail cache for exponential expressions (turning on the cache will potentially be a very expensive operation).

Comment 7

[Igor Bukanov]

Attachment: Implementation v3

This is an update to sync the patch with CVS head where I tried to preserve in jsregexp.c the same callback calling frequency as one defined on the trunk. That caused an inflation in weights, so not to worry about an overflow of the counter I put there an explicit overflow detection. 

Note that the main idea behind the patch is not to weighted counter, but rather to separate the counter update and checks. That allows to update the counter at places where, for example, calling callback is not GC-safe.

Comment 8

[Brian Crowder]

Preserving the same callback frequency as what is defined on the trunk isn't critical, as long as it's still dramatically less than what was happening before (several hundred thousand checks a second).  If if simplifies your patch to abandon that, I'm all for it (ie., saves you from having to do the overflow checking?).  There's no reason that the backtracking here couldn't be weighted similarly to the JSOW_JUMP in your original implementation; I think it will still be a huge savings, and it seems like it would be nice not to have to do the overflow checking inside of tight-loops, if we can help it?

Comment 9

[Brian Crowder]

Comment on attachment 240008 [details] [diff] [review]
Implementation v3

In any case, r+ from me for the regexp piece.

Comment 10

[Igor Bukanov]

Attachment: Implementation v4

The update to bring the patch in sync with CVS head.

Comment 11

[Igor Bukanov]

Attachment: Implementation v5

In this version I removed JSOW_LIGHT_JUMP to reflect comment 8.

Comment 12

[Brendan Eich [:brendan]]

Comment on attachment 243828 [details] [diff] [review]
Implementation v5


>+/*
>+ * Update operration counter according the specified weight. This never calls
>+ * any API.

s/operration/operation/

and might say "This macro does not call the branch callback" or that plus " or any API."

>+/*
>+ * Update operration counter and check the branch callback when it reachs the
>+ * limit. This can run the full GC and arbitrary scripts via generator close
>+ * hooks.
>+ * Return true if it is OK to continue and false otherwise.

s/operration/operation

and "This macro" for "This" again.  Pull up the "Return true ..." final sentence unless it really needs to be a separate paragraph (in which case, add an empty comment-line in between).

>+ */
>+#define JS_CHECK_OPERATION_LIMIT(cx, weight)                                  \
>+    (JS_COUNT_OPERATION(cx, weight),                                          \
>+     (JS_BIT(31) & (cx)->operationCounter) == 0 ||                            \
>+     js_ResetOperationCounter(cx))

Why not initialize cx->operationCounter = JSOW_BRANCH_CALLBACK to avoid a first-time firing of that callback?

Have you benchmarked to make sure this doesn't ding Ts, Txul, Tp?  Would be good to get up-to-date perf data.

/be

Comment 13

[Jeff Walden [:Waldo]]

(In reply to comment #12)
> >+ * Update operration counter and check the branch callback when it reachs the

Also s/reachs/reaches/.

Comment 14

[Igor Bukanov]

Attachment: Implementation v6

The patch update that, besides syncing with the trunk and addressing the nits, makes the counter to grow from 0 and call the callback when it reaches the limit. In this way the memset(cx, 0) in NewContext sets the counter to 0 avoiding the early callback call.

Comment 15

[Brendan Eich [:brendan]]

Comment on attachment 249270 [details] [diff] [review]
Implementation v6

>+/*
>+ * The implementation of JS_COUNT_OPERATION macro bellow assumes that
>+ * JSOW_BRANCH_CALLBACK is a power of 2 to ensures that an unsigned int
>+ * overflow does not bring the counter bellow JSOW_BRANCH_CALLBACK limit.

s/bellow/below/g
s/power of 2/power of two/

>+#define JS_COUNT_OPERATION(cx, weight)                                        \
>+    ((void)(JS_ASSERT((weight) > 0),                                          \
>+            JS_ASSERT((weight) <= JSOW_BRANCH_CALLBACK),                      \
>+            (cx)->operationCounter = (((cx)->operationCounter + (weight)) |   \
>+                                      (JSOW_BRANCH_CALLBACK &                 \
>+                                       (cx)->operationCounter))))

Why mask the overflow bit (JSOW_BRANCH_CALLBACK & cx->operationCounter), instead of just letting the counter grow to be >= JSOW_BRANCH_CALLBACK?  If the counter overflows from a large value in unsigned 32 bits, it will wrap past 0 and end up being  a number < JSOW_BRANCH_CALLBACK, so the bit won't be set.  Other weights may or may not sum to a number for which that bit is set, too.  So I don't see how this scheme can detect 32-bit overflow.  What am I missing?

/be

Comment 16

[Igor Bukanov]

Attachment: Implementation v7

The version addresses the nit and fixes my stupid blunder in the code that was supposed to prevent an overflow reset.

The new patch uses:

#define JS_COUNT_OPERATION(cx, weight)                                        \
    ((void)(JS_ASSERT((weight) > 0),                                          \
            JS_ASSERT((weight) <= JSOW_BRANCH_CALLBACK),                      \
            (cx)->operationCounter = (((cx)->operationCounter + (weight)) |   \
                                      (~(JSOW_BRANCH_CALLBACK - 1) &          \
                                       (cx)->operationCounter))))

Since JSOW_BRANCH_CALLBACK is 2^n, ~(JSOW_BRANCH_CALLBACK - 1) & x is (x >> n) << n. Thus, after the counter update, any bit in position n or higher will remain set. That, in turn, preserves operationCounter >=  JSOW_BRANCH_CALLBACK.

Comment 17

[Brendan Eich [:brendan]]

Comment on attachment 249323 [details] [diff] [review]
Implementation v7

Any measurable performance consequences with micro- or macro-benchmarks?

/be

Comment 18

[Igor Bukanov]

The patch does not affect the browser startup time. It only visible for a test case like:

<html><body><script>

function test(N) {
  var a = [];
  for (var i = 0; i != N; ++i) {
    a.push(""+i);
  }
  var now = Date.now;
  var t = now();
  a.sort();
  t = now() - t;
  return t;
}

var time = test(300*1000);
document.write("Run time: <i>"+time+"ms</i>");
</script></body></html>

Here the sorting an array of 3e5 strings increased from 305 to 314 ms on my PentiumM 1.1GHz laptop with an optimized build under Ubuntu 6.10. This is hardly suprising as GC does run during the loop  and its take time to scan 3e5 rooted strings. 

Comment 19

[Igor Bukanov]

I committed the patch from comment 16 to the trunk:

Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.297; previous revision: 3.296
done
Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.102; previous revision: 3.101
done
Checking in jscntxt.c;
/cvsroot/mozilla/js/src/jscntxt.c,v  <--  jscntxt.c
new revision: 3.95; previous revision: 3.94
done
Checking in jscntxt.h;
/cvsroot/mozilla/js/src/jscntxt.h,v  <--  jscntxt.h
new revision: 3.131; previous revision: 3.130
done
Checking in jsgc.c;
/cvsroot/mozilla/js/src/jsgc.c,v  <--  jsgc.c
new revision: 3.193; previous revision: 3.192
done
Checking in jsobj.c;
/cvsroot/mozilla/js/src/jsobj.c,v  <--  jsobj.c
new revision: 3.309; previous revision: 3.308
done
Checking in jsregexp.c;
/cvsroot/mozilla/js/src/jsregexp.c,v  <--  jsregexp.c
new revision: 3.129; previous revision: 3.128
done
Checking in jsscope.c;
/cvsroot/mozilla/js/src/jsscope.c,v  <--  jsscope.c
new revision: 3.53; previous revision: 3.52
done

Comment 20

[-fullmetaljacket-]

sorry if this is spam, but checkin for this appears to have broken a couple of extensions:
Console2
Gmail Notify
Adblock Plus
and Google Toolbar

See forum thread:
http://forums.mozillazine.org/viewtopic.php?p=2662949#2662949

Comment 21

[Brendan Eich [:brendan]]

I backed out the committed patch after confirming that it broke gmail (for me at least).

/be

Comment 22

[Arie Paap [:wildmyron]]

For reference, some other minor things broke when this patch landed

1) Entering bookmark keywords in the urlbar
2) Adding bookmark keywords to existing bookmarks
2) right click -> save link as... broken for files
3) the text "Use password manager to remember this password." is missing from the proxy authentication dialog
4) Recently closed tabs

Is it worth me exploring this build further or are all these little things likely to be caused by the same problem with the patch?

Comment 23

[aja+bugzilla]

FWIW, another thing fixed by this backout:

about:<anything> and generally URLs without profile prefix (e.g. google.com vs. http://google.com) would do nothing when entered in address bar.

Comment 24

[Igor Bukanov]

Attachment: Implementation v8

Too bad I had to spend a day to find a stupid missed "!" in jsregexp.c :(((

Comment 25

[Brendan Eich [:brendan]]

Comment on attachment 249485 [details] [diff] [review]
Implementation v8

Need testing of all regressed pages/apps/extensions before re-landing to make sure this was the only problem. I'm still ok with the code, a bit worried about the overhead, more worried that a long-script dialog will kill gmail now where it would not before.

/be

Comment 26

[Igor Bukanov]

I committed the patch from the comment 24 to the trunk:

Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.300; previous revision: 3.299
done
Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.104; previous revision: 3.103
done
Checking in jscntxt.c;
/cvsroot/mozilla/js/src/jscntxt.c,v  <--  jscntxt.c
new revision: 3.97; previous revision: 3.96
done
Checking in jscntxt.h;
/cvsroot/mozilla/js/src/jscntxt.h,v  <--  jscntxt.h
new revision: 3.133; previous revision: 3.132
done
Checking in jsgc.c;
/cvsroot/mozilla/js/src/jsgc.c,v  <--  jsgc.c
new revision: 3.195; previous revision: 3.194
done
Checking in jsobj.c;
/cvsroot/mozilla/js/src/jsobj.c,v  <--  jsobj.c
new revision: 3.311; previous revision: 3.310
done
Checking in jsregexp.c;
/cvsroot/mozilla/js/src/jsregexp.c,v  <--  jsregexp.c
new revision: 3.131; previous revision: 3.130
done
Checking in jsscope.c;
/cvsroot/mozilla/js/src/jsscope.c,v  <--  jsscope.c
new revision: 3.55; previous revision: 3.54
done