Bug 19044 – SquirrelFish: Bogus values enter evaluation when closing over scope with parameter and var with same name

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Oliver Hunt]

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

[Oliver Hunt]

Created attachment 21124 [details]
Testcase

[Geoffrey Garen]

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.

[Cameron Zwarich (cpst)]

(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.

[Geoffrey Garen]

> > 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.

[Cameron Zwarich (cpst)]

(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.

[Geoffrey Garen]

> Except that's wrong, because it still has the wrong behaviour with f.arguments.

Can you elaborate on this?

[Cameron Zwarich (cpst)]

(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.

[Cameron Zwarich (cpst)]

Created attachment 21129 [details]
Proposed patch

[Geoffrey Garen]

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.

[Cameron Zwarich (cpst)]

(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?

[Cameron Zwarich (cpst)]

I tried using a HashSet<UString::Rep*>, but for some reason it causes an intermittent timeout in/js/gmail-re-re.html.

[Geoffrey Garen]

> 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.

[Maciej Stachowiak]

I realized a similar bug can happen with duplicate parameter names, and only Geoff's suggestion, not Cameron's patch, will fix that case.

[Maciej Stachowiak]

Created attachment 21199 [details]
geoff's suggested fix plus tests

[Oliver Hunt]

Comment on attachment 21199 [details]
geoff's suggested fix plus tests

r=me, assuming perf is good.

[Oliver Hunt]

Landed r33516