103042 - O(n**2) arena allocation in jsscan.c on long string literals

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Brendan Eich [:brendan]]

See the URL.  Fix coming up.

/be

Comment 1

[Brendan Eich [:brendan]]

Attachment: proposed fix, please review

Comment 2

[Mike Shaver (:shaver emeritus)]

Comment on attachment 51994 [details] [diff] [review]
proposed fix, please review

>     if (!base) {
>-	JS_ARENA_ALLOCATE_CAST(base, jschar *, pool, tbincr);
>+        tbsize = TBMIN * sizeof(jschar);
>+        length = TBMIN;
>+        JS_ARENA_ALLOCATE_CAST(base, jschar *, pool, tbsize);
>     } else {
>-	tbsize = (size_t)(length * sizeof(jschar));
>-	JS_ARENA_GROW_CAST(base, jschar *, pool, tbsize, tbincr);
>+        length = PTRDIFF(tb->limit, base, jschar);
>+        tbsize = length * sizeof(jschar);
>+        length <<= 1;
>+        JS_ARENA_GROW_CAST(base, jschar *, pool, tbsize, tbsize);
>     }
>     if (!base) {
> 	JS_ReportOutOfMemory(cx);
> 	return JS_FALSE;
>     }
>     tb->base = base;
>-    tb->limit = base + length + length + TBINCR;
>+    tb->limit = base + length;

So based on my reading of this, we never really grow, and we might well
crash, since limit overstates the allocation.

Shouldn't we be shifting length before we use it to compute tbsize for
reallocation?

Comment 3

[Brendan Eich [:brendan]]

shaver, give me some credit here!  Note that the patch passes tbsize and the
size and incr parameters (final two) to JS_ARENA_GROW_CAST, which has the direct
effect of doubling the current allocation size.  We update length after
computing tbsize for this reason.  Both tbsize+tbsize and length<<=1 double the
byte- and jschar-reckoned "sizes", and in the right order.

/be

Comment 4

[Mike Shaver (:shaver emeritus)]

Comment on attachment 51994 [details] [diff] [review]
proposed fix, please review

I hate being stupid.  You're right, of course.

sr=shaver

Comment 5

[Brendan Eich [:brendan]]

waterson, this was the patch I mentioned, that might help reduce the bloatblame
attributed (due to dlsym limitations) to js_MatchToken.

Anyone -- I need an r=, I'd like to get this patch in.

/be

Comment 6

[John Bandhauer]

Comment on attachment 51994 [details] [diff] [review]
proposed fix, please review

r=jband

Comment 7

[Brendan Eich [:brendan]]

Fix is in.

/be

Comment 8

[Phil Schwartau]

Marking Verified -