351413 - Unbounded recursion during let block cloning

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

js_GetScopeChain from js/src/jsinterp.c uses recursive helper function CloneBlockChain to clone let blocks. The function does not check for C recursion depth. Thus a C stack overflow is possible with nested let blocks.

Comment 1

[Igor Bukanov]

Attachment: Fix v1

The fix replaces the recursion by a loop that set the parent slot of the cloned child after cloning the parent. The only complexity comes from the need to GC protect the child during parent's cloning.

Comment 2

[Igor Bukanov]

Attachment: Test case for jsshell

The test requires manual testing as it must know about maximum C stack depth. The reason for this is that the parser already recursive. Thus to trigger a stack overflow one has to call a function with nested let blocks from already low stack.

So here is results from my Ubuntu Linux 6.06 laptop:

~/m/trunk/mozilla/js/src> ulimit -s
8192
~/m/trunk/mozilla/js/src> ./Linux_All_OPT.OBJ/js -S $((8170 * 1024)) ~/s/test351413.js 
Maximum amount of let nesting that the C stack limit allows: 3987
Maximum callAfterConsumingCStack level: 12441
Segmentation fault

Note that it is important to find a value to pass to -S that is sufficiently close to the real limit so recursion through block cloning would have a chance to reach the limit. On the other hand the value should not be too close to the limit to give some space for the interpreter.

After the patch:
~/m/trunk/mozilla/js/src> ulimit -s
8192
~/m/trunk/mozilla/js/src> ./Linux_All_OPT.OBJ/js -S $((8170 * 1024)) ~/s/test351413.js 
Maximum amount of let nesting that the C stack limit allows: 3987
Maximum callAfterConsumingCStack level: 12441
true

Comment 3

[Brendan Eich [:brendan]]

Comment on attachment 236805 [details] [diff] [review]
Fix v1

Only nit-level thoughts, below.  r=me with changes you agree with.

>+        cursor = js_CloneBlockObject(cx, cursor, parent ? NULL : fp->scopeChain,
>+                                     fp);

This could just pass fp->scopeChain as the third argument, to save cycles and some small amount of code, since the NULL parent value will cause a default parent computation and assignment, and it will soon be overwritten by OBJ_SET_PARENT.

>+            OBJ_SET_PARENT(cx, clonedChild, cursor);

In single-threaded newborn settings, I have been using

    clonedChild->slots[JSSLOT_PARENT] = OBJECT_TO_JSVAL(cursor);

and the like.  We know the clonedChild can't be reached by other threads, so we may as well save cycles and minor code space again.

/be

Comment 4

[Igor Bukanov]

Attachment: Fix v1b

Patch to commit with nits addressed and comments added.

Comment 5

[Brendan Eich [:brendan]]

Comment on attachment 236850 [details] [diff] [review]
Fix v1b

>? x.diff
>Index: js.c
>===================================================================
>RCS file: /cvsroot/mozilla/js/src/js.c,v
>retrieving revision 3.122
>diff -U7 -p -r3.122 js.c
>--- js.c	22 Aug 2006 22:42:56 -0000	3.122
>+++ js.c	5 Sep 2006 20:37:23 -0000
>@@ -683,14 +683,15 @@ Print(JSContext *cx, JSObject *obj, uint
>         if (!str)
>             return JS_FALSE;
>         fprintf(gOutFile, "%s%s", i ? " " : "", JS_GetStringBytes(str));
>     }
>     n++;
>     if (n)
>         fputc('\n', gOutFile);
>+    fflush(gOutFile);
>     return JS_TRUE;
> }
> 
> static JSBool
> Help(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval);
> 
> static JSBool

Separate bug?  This seems suboptimal, it's ok if there's no better way to set line buffering.

>Index: jsinterp.c
>===================================================================
>RCS file: /cvsroot/mozilla/js/src/jsinterp.c,v
>retrieving revision 3.279
>diff -U7 -p -r3.279 jsinterp.c
>--- jsinterp.c	3 Sep 2006 07:08:24 -0000	3.279
>+++ jsinterp.c	5 Sep 2006 20:37:24 -0000
>@@ -459,55 +459,75 @@ js_GetLocalVariable(JSContext *cx, JSObj
> 
> JSBool
> js_SetLocalVariable(JSContext *cx, JSObject *obj, jsval id, jsval *vp)
> {
>     return JS_TRUE;
> }
> 
>-/*
>- * Recursive helper to convert a compile-time block chain to a runtime block
>- * scope chain prefix.  Each cloned block object is safe from GC by virtue of
>- * the object newborn root.  This root cannot be displaced by arbitrary code
>- * called from within js_NewObject, because we pass non-null proto and parent
>- * arguments (so js_NewObject won't call js_GetClassPrototype).
>- */
>-static JSObject *
>-CloneBlockChain(JSContext *cx, JSStackFrame *fp, JSObject *obj)
>-{
>-    JSObject *parent;
>-
>-    parent = OBJ_GET_PARENT(cx, obj);
>-    if (!parent) {
>-        parent = fp->scopeChain;
>-    } else {
>-        parent = CloneBlockChain(cx, fp, parent);
>-        if (!parent)
>-            return NULL;
>-        fp->scopeChain = parent;
>-    }
>-    return js_CloneBlockObject(cx, obj, parent, fp);
>-}

Recursion sure is pretty compared to the alternative :-P.  Reminds me of a book I've been asked to write a chapter for, "Beautiful Code".  My initial thought is that designs and Math may be beautiful, but real code that actually defends against errors, etc., is not.

Thanks, r=me again.

This is safe for 1.8.1 after a bit of baking on the trunk, so nominating now.  We defend elsewhere against stack overflow D.O.S. attacks, either by stack address monitoring, or by converting to iterative algorithms, as here.

/be

Comment 6

[Igor Bukanov]

Attachment: Fix v1c

That js.c change was a debug hack that slipped into the patch. So here is the real patch.

Comment 7

[Igor Bukanov]

I committed the patch from comment 6 to the trunk:

Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.280; previous revision: 3.279
done

Comment 8

[Igor Bukanov]

> Recursion sure is pretty compared to the alternative :-P. 

But that is unfair comparison! What the patch shows is that replacing O(n)-in-space algorithm by O(1)-in-space one brings complexity. Such complexity when expressed in C looks more messy indeed, but what is prettier, insertion sort or heap sort? 

> I've been asked to write a chapter for, "Beautiful Code".  My initial thought
> is that designs and Math may be beautiful, but real code that actually defends
> against errors, etc., is not.

If an initial "beautiful" design does not account for errors, then it not even a design IMO. Which also reminds me about "ugly is beautiful" from Wheels novel by Arthur Hailey. The idea is that a thing may look initially ugly but if it is absolutely functional while fulfilling its design goals then it becomes beauty.  

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #8)
> Such complexity
> when expressed in C looks more messy indeed, but what is prettier, insertion
> sort or heap sort? 

Heap, of course :-P.

> If an initial "beautiful" design does not account for errors, then it not even
> a design IMO. Which also reminds me about "ugly is beautiful" from Wheels novel
> by Arthur Hailey. The idea is that a thing may look initially ugly but if it is
> absolutely functional while fulfilling its design goals then it becomes beauty. 

I quite agree.  Trick is to say this in a dozen pages in a way that convinces the unconverted who want to bask in Platonic truth and beauty.  Thanks for the Haley reference (I haven't read that one).

/be

Comment 10

[Blake Kaplan (:mrbkap) (inactive)]

This will need the fix for bug 351606 as well.

Comment 11

[Igor Bukanov]

Attachment: Version for 1.8.1 with fix from bug 351606

This is the initial patch plus the regression fix from bug 351606.

Comment 12

[Mike Schroepfer]

Comment on attachment 237318 [details] [diff] [review]
Version for 1.8.1 with fix from bug 351606

a=schrep for drivers.

Comment 13

[Igor Bukanov]

I committed the patch from comment 11 to MOZILLA_1_8_BRANCH

Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.181.2.56; previous revision: 3.181.2.55
done