Bug 19044 - SquirrelFish: Bogus values enter evaluation when closing over scope with parameter and var with same name
Summary: SquirrelFish: Bogus values enter evaluation when closing over scope with para...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Mac OS X 10.5
: P1 Blocker
Assignee: Maciej Stachowiak
URL: http://blog.wired.com/games/2008/05/f...
Keywords:
Depends on:
Blocks:
 
Reported: 2008-05-14 05:19 PDT by Oliver Hunt
Modified: 2008-05-16 02:52 PDT (History)
3 users (show)

See Also:


Attachments
Testcase (202 bytes, text/html)
2008-05-14 06:05 PDT, Oliver Hunt
no flags Details
Proposed patch (1.58 KB, patch)
2008-05-14 12:00 PDT, Cameron Zwarich (cpst)
ggaren: review-
Details | Formatted Diff | Diff
geoff's suggested fix plus tests (6.18 KB, patch)
2008-05-16 02:15 PDT, Maciej Stachowiak
oliver: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Oliver Hunt 2008-05-14 05:19:18 PDT
Crash occurs with back trace
#0  0x00505437 in KJS::JSValue::toObject (this=0x0, exec=0xbfffde14) at value.h:523
#1  0x00491273 in functionProtoFuncApply (exec=0xbfffde14, thisObj=0x1a7dc220, args=@0xbfffd090) at function_object.cpp:91
#2  0x0046a8ea in KJS::PrototypeFunction::callAsFunction (this=0x1a4b00a0, exec=0xbfffde14, thisObj=0x1a7dc220, args=@0xbfffd090) at function.cpp:747
#3  0x00520f12 in KJS::Machine::privateExecute (this=0x572960, flag=KJS::Machine::Normal, exec=0xbfffde14, registerFile=0x1a6d9530, r=0x1c73a450, scopeChain=0x1a622820, codeBlock=0x1a9f6a90, exception=0xbfffdecc) at /Volumes/Data/git/WebKit/OpenSource/JavaScriptCore/VM/Machine.cpp:1764
#4  0x005228fd in KJS::Machine::execute (this=0x572960, functionBodyNode=0x1a634c80, exec=0x1915e1e0, function=0x1a7dc180, thisObj=0x1a7dc340, args=@0xbfffdf64, registerFileStack=0x1919c218, scopeChain=0x1a622820, exception=0xbfffdecc) at /Volumes/Data/git/WebKit/OpenSource/JavaScriptCore/VM/Machine.cpp:663
#5  0x004766fb in KJS::FunctionImp::callAsFunction (this=0x1a7dc180, exec=0x1915e1e0, thisObj=0x1a7dc340, args=@0xbfffdf64) at function.cpp:90
#6  0x0048f1eb in KJS::JSObject::call (this=0x1a7dc180, exec=0x1915e1e0, thisObj=0x1a7dc340, args=@0xbfffdf64) at object.cpp:99
#7  0x02c75162 in WebCore::JSAbstractEventListener::handleEvent (this=0x1a64fd40, ele=0x1c7bd0e0, isWindowEvent=false) at /Volumes/Data/git/WebKit/OpenSource/WebCore/bindings/js/kjs_events.cpp:100
...
21 instructions; 320 bytes at 0x1a9f6a90; 2 locals (2 parameters); 42 temporaries

[   0] resolve		 tr0, __method(@id0)
[   3] get_by_id	 tr1, tr0, apply(@id1)
[   7] resolve		 tr13, object(@id2)
[  10] new_array	 tr15
[  12] mov		 tr16, lr1
[  15] jtrue		 tr16, 8(->25)
[  18] resolve		 tr17, window(@id3)
[  21] get_by_id	 tr16, tr17, event(@id4)
[  25] put_by_index	 tr15, 0, tr16
[  29] load		 tr16, 1(@k0)		
[  32] put_by_id	 tr15, length(@id5), tr16
[  36] get_by_id	 tr16, tr15, concat(@id6)
[  40] resolve		 tr28, args(@id7)
[  43] call		 tr15, tr16, tr15, 27, 2
[  49] get_by_id	 tr16, tr15, concat(@id6)
[  53] resolve_func	 tr28, tr29, $A(@id8)
[  57] resolve		 tr41, arguments(@id9)
[  60] call		 tr28, tr29, tr28, 40, 2
[  66] call		 tr14, tr16, tr15, 27, 2
[  72] call		 tr0, tr1, tr0, 12, 3
[  78] ret		 tr0

Identifiers:
  id0 = __method
  id1 = apply
  id2 = object
  id3 = window
  id4 = event
  id5 = length
  id6 = concat
  id7 = args
  id8 = $A
  id9 = arguments

Constants:
  k0 = 1

Register frame: 

----------------------------------------
     use      |   address  |    value   
----------------------------------------
[call frame]  | 0x1c73a420 |        0x0 
[call frame]  | 0x1c73a424 |        0x4 
[call frame]  | 0x1c73a428 |        0x0 
[call frame]  | 0x1c73a42c |        0x0 
[call frame]  | 0x1c73a430 |        0x0 
[call frame]  | 0x1c73a434 |        0xa 
[call frame]  | 0x1c73a438 |        0x2 
[call frame]  | 0x1c73a43c |        0x0 
[call frame]  | 0x1c73a440 | 0x1a7dc180 
[call frame]  | 0x1c73a444 | 0x1a4be840 
----------------------------------------
[param]       | 0x1c73a448 | 0x1a7dc340 
[param]       | 0x1c73a44c | 0x1a4be860 
----------------------------------------
[temp]        | 0x1c73a450 | 0x1a7dc220 
[temp]        | 0x1c73a454 | 0x1a4b00a0 
[temp]        | 0x1c73a458 |        0x0 
[temp]        | 0x1c73a45c |        0x0 
[temp]        | 0x1c73a460 |        0x0 
[temp]        | 0x1c73a464 |        0x0 
[temp]        | 0x1c73a468 |        0x0 
[temp]        | 0x1c73a46c |        0x0 
[temp]        | 0x1c73a470 |        0x0 
[temp]        | 0x1c73a474 |        0x0 
[temp]        | 0x1c73a478 |        0x0 
[temp]        | 0x1c73a47c |        0x0 
[temp]        | 0x1c73a480 | 0x1a7dc220 
[temp]        | 0x1c73a484 |        0x0 
[temp]        | 0x1c73a488 | 0x1a4be500 
[temp]        | 0x1c73a48c | 0x1a4be780 
[temp]        | 0x1c73a490 | 0x1a4be7a0 
[temp]        | 0x1c73a494 |        0x0 
[temp]        | 0x1c73a498 |        0x0 
[temp]        | 0x1c73a49c |        0x0 
[temp]        | 0x1c73a4a0 |        0x0 
[temp]        | 0x1c73a4a4 |        0x0 
[temp]        | 0x1c73a4a8 |        0x0 
[temp]        | 0x1c73a4ac |        0x0 
[temp]        | 0x1c73a4b0 |        0x0 
[temp]        | 0x1c73a4b4 |        0x0 
[temp]        | 0x1c73a4b8 |        0x0 
[temp]        | 0x1c73a4bc | 0x1a4be780 
[temp]        | 0x1c73a4c0 | 0x1a4be520 
[temp]        | 0x1c73a4c4 | 0x1a4b49a0 
[temp]        | 0x1c73a4c8 | 0x1a9f6a90 
[temp]        | 0x1c73a4cc | 0x1c7a25b8 
[temp]        | 0x1c73a4d0 | 0x1a622820 
[temp]        | 0x1c73a4d4 |        0xc 
[temp]        | 0x1c73a4d8 |       0x1c 
[temp]        | 0x1c73a4dc |       0x28 
[temp]        | 0x1c73a4e0 |        0x2 
[temp]        | 0x1c73a4e4 |        0x0 
[temp]        | 0x1c73a4e8 | 0x1a4b49a0 
[temp]        | 0x1c73a4ec |        0x0 
[temp]        | 0x1c73a4f0 | 0x1a4b0000 
[temp]        | 0x1c73a4f4 | 0x1a4be760 
$10 = void
Comment 1 Oliver Hunt 2008-05-14 06:05:55 PDT
Created attachment 21124 [details]
Testcase
Comment 2 Geoffrey Garen 2008-05-14 09:12:14 PDT
I believe the error is in JSActivation::copyRegisters:

    int numRegisters = symbolTable().size();

In the case of duplicate entries, the symbol table's size will not equal the number of local registers. I believe the correct behavior is to set numRegisters to CodeBlock::numLocals instead.

There are other, more complicated ways to fix this. For example, codegen changes could ensure exact local register allocation, such that we packed all duplicates into the same slot. I had a patch to do that a while back.
Comment 3 Cameron Zwarich (cpst) 2008-05-14 10:36:21 PDT
(In reply to comment #2)
> I believe the error is in JSActivation::copyRegisters:
> 
>     int numRegisters = symbolTable().size();
> 
> In the case of duplicate entries, the symbol table's size will not equal the
> number of local registers. I believe the correct behavior is to set
> numRegisters to CodeBlock::numLocals instead.
> 
> There are other, more complicated ways to fix this. For example, codegen
> changes could ensure exact local register allocation, such that we packed all
> duplicates into the same slot. I had a patch to do that a while back.

I think the solution is simpler than this. We just shouldn't make a local variable for an identifier that also appears as a parameter.
Comment 4 Geoffrey Garen 2008-05-14 11:06:33 PDT
> > There are other, more complicated ways to fix this. For example, codegen
> > changes could ensure exact local register allocation, such that we packed all
> > duplicates into the same slot. I had a patch to do that a while back.
> 
> I think the solution is simpler than this. We just shouldn't make a local
> variable for an identifier that also appears as a parameter.

That's the more complicated solution I mentioned above: codegen changes to ensure exact register allocation.

Seems much easier just to change 

> >     int numRegisters = symbolTable().size();

to 

> >     int numRegisters = codeBlock->numLocals.
Comment 5 Cameron Zwarich (cpst) 2008-05-14 11:36:25 PDT
(In reply to comment #4)
> > > There are other, more complicated ways to fix this. For example, codegen
> > > changes could ensure exact local register allocation, such that we packed all
> > > duplicates into the same slot. I had a patch to do that a while back.
> > 
> > I think the solution is simpler than this. We just shouldn't make a local
> > variable for an identifier that also appears as a parameter.
> 
> That's the more complicated solution I mentioned above: codegen changes to
> ensure exact register allocation.
> 
> Seems much easier just to change 
> 
> > >     int numRegisters = symbolTable().size();
> 
> to 
> 
> > >     int numRegisters = codeBlock->numLocals.

Except that's wrong, because it still has the wrong behaviour with f.arguments.
Comment 6 Geoffrey Garen 2008-05-14 11:44:11 PDT
> Except that's wrong, because it still has the wrong behaviour with f.arguments.

Can you elaborate on this?
Comment 7 Cameron Zwarich (cpst) 2008-05-14 11:57:42 PDT
(In reply to comment #6)
> > Except that's wrong, because it still has the wrong behaviour with f.arguments.
> 
> Can you elaborate on this?

I thought that something like this would go wrong:

function f()
{
    g.arguments[0] = "PASS";
}

function g(a)
{
    var a = "FAIL";
    f();
    print(a);
}

g("PASS");

However, it seems that it doesn't cause a problem, so my apologies. Anyways, I have a patch that fixes the problem by changing codegen, so I'll post it.
Comment 8 Cameron Zwarich (cpst) 2008-05-14 12:00:58 PDT
Created attachment 21129 [details]
Proposed patch
Comment 9 Geoffrey Garen 2008-05-14 13:32:14 PDT
This algorithm is O(MxN), where M is the number of vars and N is the number of parameters. We try really hard to avoid algorithms like that, even in code that doesn't seem performance-critical, because such algorithms often come back to bite us.

I would worry especially about pages generated by obfuscaters, cross-compilers, and/or server-side scripts triggering pathological behavior at compile time.

If you want to go with the codegen solution, I think you should use a hashing technique instead.
Comment 10 Cameron Zwarich (cpst) 2008-05-14 13:38:55 PDT
(In reply to comment #9)
> This algorithm is O(MxN), where M is the number of vars and N is the number of
> parameters. We try really hard to avoid algorithms like that, even in code that
> doesn't seem performance-critical, because such algorithms often come back to
> bite us.
> 
> I would worry especially about pages generated by obfuscaters, cross-compilers,
> and/or server-side scripts triggering pathological behavior at compile time.
> 
> If you want to go with the codegen solution, I think you should use a hashing
> technique instead.

Yeah, I was worried about that. I guess it makes more sense to with the local storage resizing, at least for now. Is it always going to be correct?
Comment 11 Cameron Zwarich (cpst) 2008-05-14 15:05:12 PDT
I tried using a HashSet<UString::Rep*>, but for some reason it causes an intermittent timeout in/js/gmail-re-re.html.
Comment 12 Geoffrey Garen 2008-05-15 14:58:38 PDT
> I guess it makes more sense to with the local
> storage resizing, at least for now. Is it always going to be correct?

Yes, I think so.

JSActivation knows how to talk to a block of registers in order to get/set locals. copyRegisters() just moves the block of registers to a new location in memory: the behavior remains the same.
Comment 13 Maciej Stachowiak 2008-05-16 01:16:00 PDT
I realized a similar bug can happen with duplicate parameter names, and only Geoff's suggestion, not Cameron's patch, will fix that case.
Comment 14 Maciej Stachowiak 2008-05-16 02:15:07 PDT
Created attachment 21199 [details]
geoff's suggested fix plus tests
Comment 15 Oliver Hunt 2008-05-16 02:16:23 PDT
Comment on attachment 21199 [details]
geoff's suggested fix plus tests

r=me, assuming perf is good.
Comment 16 Oliver Hunt 2008-05-16 02:52:49 PDT
Landed r33516