Unstoppable too long execution with Array methods

RESOLVED FIXED

Status

()

RESOLVED FIXED
13 years ago
11 years ago

People

(Reporter: igor, Assigned: igor)

Tracking

Trunk
x86
Linux
Points:
---
Dependency tree / graph
Bug Flags:
blocking1.8b5 -
in-testsuite -

Firefox Tracking Flags

(Not tracked)

Details

(URL)

Attachments

(1 attachment, 7 obsolete attachments)

(Assignee)

Description

13 years ago
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.
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
Flags: blocking1.8b5?

Comment 2

13 years ago
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.
Flags: blocking1.8b5? → blocking1.8b5-

Updated

13 years ago
Blocks: 334935

Updated

12 years ago
Blocks: 351449

Updated

12 years ago
No longer blocks: 351449
(Assignee)

Comment 3

12 years ago
Created attachment 237516 [details] [diff] [review]
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.
Assignee: general → igor.bukanov
Status: NEW → ASSIGNED
Attachment #237516 - Flags: superreview?(brendan)
Attachment #237516 - Flags: review?(mrbkap)
(Assignee)

Updated

12 years ago
Summary: Unstoppable too long execution with Array.forEach → Unstoppable too long execution with Array methods
(Assignee)

Updated

12 years ago
Blocks: 253325
(Assignee)

Comment 4

12 years ago
Created attachment 237720 [details] [diff] [review]
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.
Attachment #237516 - Attachment is obsolete: true
Attachment #237720 - Flags: superreview?(brendan)
Attachment #237720 - Flags: review?(mrbkap)
Attachment #237516 - Flags: superreview?(brendan)
Attachment #237516 - Flags: review?(mrbkap)
Brian's been working on regexp monitoring and optimization, he should have a look too.  Thanks,

/be

Comment 6

12 years ago
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).
(Assignee)

Comment 7

12 years ago
Created attachment 240008 [details] [diff] [review]
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.
Attachment #237720 - Attachment is obsolete: true
Attachment #240008 - Flags: superreview?(mrbkap)
Attachment #240008 - Flags: review?(brendan)
Attachment #237720 - Flags: superreview?(brendan)
Attachment #237720 - Flags: review?(mrbkap)
(Assignee)

Updated

12 years ago
Attachment #240008 - Flags: review?(crowder)

Comment 8

12 years ago
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

12 years ago
Comment on attachment 240008 [details] [diff] [review]
Implementation v3

In any case, r+ from me for the regexp piece.
Attachment #240008 - Flags: review?(crowder) → review+
(Assignee)

Comment 10

12 years ago
Created attachment 243827 [details] [diff] [review]
Implementation v4

The update to bring the patch in sync with CVS head.
Attachment #240008 - Attachment is obsolete: true
Attachment #243827 - Flags: review?(brendan)
Attachment #240008 - Flags: superreview?(mrbkap)
Attachment #240008 - Flags: review?(brendan)
(Assignee)

Comment 11

12 years ago
Created attachment 243828 [details] [diff] [review]
Implementation v5

In this version I removed JSOW_LIGHT_JUMP to reflect comment 8.
Attachment #243827 - Attachment is obsolete: true
Attachment #243828 - Flags: review?(brendan)
Attachment #243827 - Flags: review?(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

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

Also s/reachs/reaches/.
(Assignee)

Comment 14

12 years ago
Created attachment 249270 [details] [diff] [review]
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.
Attachment #243828 - Attachment is obsolete: true
Attachment #249270 - Flags: review?(brendan)
Attachment #243828 - Flags: review?(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
(Assignee)

Comment 16

12 years ago
Created attachment 249323 [details] [diff] [review]
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.
Attachment #249270 - Attachment is obsolete: true
Attachment #249323 - Flags: review?(brendan)
Attachment #249270 - Flags: review?(brendan)
Comment on attachment 249323 [details] [diff] [review]
Implementation v7

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

/be
Attachment #249323 - Flags: review?(brendan) → review+
(Assignee)

Comment 18

12 years ago
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. 
(Assignee)

Comment 19

12 years ago
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
Status: ASSIGNED → RESOLVED
Last Resolved: 12 years ago
Resolution: --- → FIXED

Comment 20

12 years ago
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

Updated

12 years ago
Depends on: 364670
I backed out the committed patch after confirming that it broke gmail (for me at least).

/be
Status: RESOLVED → REOPENED
Resolution: FIXED → ---

Updated

12 years ago
No longer depends on: 364670
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

12 years ago
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.
(Assignee)

Comment 24

12 years ago
Created attachment 249485 [details] [diff] [review]
Implementation v8

Too bad I had to spend a day to find a stupid missed "!" in jsregexp.c :(((
Attachment #249323 - Attachment is obsolete: true
Attachment #249485 - Flags: review?(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
Attachment #249485 - Flags: review?(brendan) → review+
(Assignee)

Updated

12 years ago
Blocks: 364773
(Assignee)

Updated

12 years ago
Blocks: 364776
(Assignee)

Comment 26

12 years ago
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
Status: REOPENED → RESOLVED
Last Resolved: 12 years ago12 years ago
Resolution: --- → FIXED

Updated

12 years ago
Flags: in-testsuite-
You need to log in before you can comment on or make changes to this bug.