Bug 20340 - SegmentedVector segment allocations can lead to unsafe use of temporary registers
Summary: SegmentedVector segment allocations can lead to unsafe use of temporary regis...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Cameron Zwarich (cpst)
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2008-08-10 01:27 PDT by Cameron Zwarich (cpst)
Modified: 2008-12-01 23:25 PST (History)
4 users (show)

See Also:


Attachments
Proposed patch (14.38 KB, patch)
2008-08-10 05:07 PDT, Cameron Zwarich (cpst)
no flags Details | Formatted Diff | Diff
Revised proposed patch (15.66 KB, patch)
2008-08-10 07:37 PDT, Cameron Zwarich (cpst)
no flags Details | Formatted Diff | Diff
Diff showing alternative fix (7.66 KB, text/plain)
2008-08-11 11:26 PDT, Chris Brichford
no flags Details
Proposed patch to change interface of SegmentedVector (3.78 KB, patch)
2008-11-29 01:05 PST, Cameron Zwarich (cpst)
no flags Details | Formatted Diff | Diff
Proposed patch (6.92 KB, patch)
2008-12-01 03:17 PST, Cameron Zwarich (cpst)
oliver: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Cameron Zwarich (cpst) 2008-08-10 01:27:51 PDT
In many emitCode() methods for Node subclasses, there is code that looks like this:

RegisterID* temp = ...
return generator.emitOpcode(generator.finalDestination(dst), temp, ...);

If temp points at the first RegisterID in a segment of the SegmentedVector containing the RegisterIDs, then generator.finalDestination(dst) may free that RegisterID, deallocate the segment, then allocate a new segment and return the first RegisterID in that segment. However, temp is still passed as an argument to generator.emitOpcode(), so this is potentially unsafe if the new segment is not allocated in the same place as the old segment.

This was first mentioned by Chris Brichford on the webkit-dev mailing list: https://lists.webkit.org/pipermail/webkit-dev/2008-July/004533.html
Comment 1 Cameron Zwarich (cpst) 2008-08-10 04:49:14 PDT
The natural fix for this isn't very hard, but it is a bit ugly. In any correct emitCode() method, we will only have one unref'd temporary by the returning call to emit an opcode. Otherwise, there is an even worse correctness issue. In this case, the call to generator.finalDestination() can either take a second argument or leave it blank.

If it is left blank, then we could simply pass the unref'd temporary as the second argument.

If there is an argument, then it is either the temporary in question (in which case we are okay) or a ref'd register, which might not be a temporary. In this case, it seems we could just replace the second argument with our unref'd temporary and we'd be okay.

This should work, but the style seems sub-optimal.
Comment 2 Cameron Zwarich (cpst) 2008-08-10 05:07:41 PDT
Created attachment 22721 [details]
Proposed patch
Comment 3 Cameron Zwarich (cpst) 2008-08-10 05:33:42 PDT
Comment on attachment 22721 [details]
Proposed patch

This patch can cause more temporaries to be allocated than necessary, so I will try a slightly different approach.
Comment 4 Cameron Zwarich (cpst) 2008-08-10 07:37:36 PDT
Created attachment 22722 [details]
Revised proposed patch

This patch actually slightly improves the codegen of SunSpider, using one or two fewer temporaries for some functions.
Comment 5 Geoffrey Garen 2008-08-10 14:57:17 PDT
Is there a way to test this condition?
Comment 6 Cameron Zwarich (cpst) 2008-08-10 15:52:46 PDT
(In reply to comment #5)
> Is there a way to test this condition?

I was thinking about that myself. We could add some debugging machinery to SegmentedVector and RegisterID to allow tagging RegisterIDs by the segment in which they are allocated, just incrementing a counter each time. Other than that, I don't think there is a way to consistently expose this flaw.
Comment 7 Cameron Zwarich (cpst) 2008-08-11 00:53:38 PDT
Comment on attachment 22722 [details]
Revised proposed patch

I'll clear the review flag on this so I can implement some debug code for SegmentedVector.
Comment 8 Chris Brichford 2008-08-11 11:26:21 PDT
Created attachment 22729 [details]
Diff showing alternative fix

Attaching a diff showing an alternative fix.   Changes makeNewTemporary such that it never shrinks the SegmentedVector of RegisterID's.  The attached diff also contains a fix for a seperate bug.  The relevant changes for this bug are in CodeGenerator::makeNewTemporary and the various CodeGenerator constructors.
Comment 9 Cameron Zwarich (cpst) 2008-08-11 19:54:31 PDT
(In reply to comment #8)
> Created an attachment (id=22729) [edit]
> Diff showing alternative fix
> 
> Attaching a diff showing an alternative fix.   Changes makeNewTemporary such
> that it never shrinks the SegmentedVector of RegisterID's.  The attached diff
> also contains a fix for a seperate bug.  The relevant changes for this bug are
> in CodeGenerator::makeNewTemporary and the various CodeGenerator constructors.

That's a decent idea. I don't really like the idea of doing it in an ad-hoc way in CodeGenerator, so I'll modify SegmentedVector never shrink. Nothing ever explicitly shrinks one in the current code.
Comment 10 Geoffrey Garen 2008-11-25 18:15:26 PST
<rdar://problem/6402032>
Comment 11 Cameron Zwarich (cpst) 2008-11-29 00:37:56 PST
I am reassigning this to myself to match Radar. There are only two forms of resizing currently done for a SegmentedVector:

- the BytecodeGenerator reserves capacity for m_globals and m_parameters. We can just add a reserveCapacity() method to SegmentedVector. As a side note, this latter one should really be a Vector with a smaller capacity, as we do not pass out any parameter registers before we know the number of parameters.

- the Lexer now shrinks its identifier SegmentedVector to 0 in Lexer::clear(). We don't need to handle arbitrary shrinkage, so a clear() method makes more sense.

I will remove resize() as a public method and add these two in one patch, then in a followup patch I will actually make the change that causes SegmentedVector to never shrink, which should actually be fairly easy.
Comment 12 Cameron Zwarich (cpst) 2008-11-29 01:05:22 PST
Created attachment 25587 [details]
Proposed patch to change interface of SegmentedVector
Comment 13 Sam Weinig 2008-11-30 14:14:50 PST
Comment on attachment 25587 [details]
Proposed patch to change interface of SegmentedVector

> +        void clear()
> +        {
> +            if (m_size != 0)
> +                shrink(0);

It seem kind of silly to me to keep all the shrink logic just to handle shrink(0).  We should either move the shrink logic that we need to clear.

Otherwise, r=me.
Comment 14 Cameron Zwarich (cpst) 2008-12-01 01:09:08 PST
Comment on attachment 25587 [details]
Proposed patch to change interface of SegmentedVector

Landed in r38856. Sam, I addressed your comment, and I also did the same thing for grow() as I did for shrink(), since grow() is no longer used anywhere else.

Clearing review flag.
Comment 15 Cameron Zwarich (cpst) 2008-12-01 03:17:50 PST
Created attachment 25622 [details]
Proposed patch
Comment 16 Cameron Zwarich (cpst) 2008-12-01 23:25:02 PST
Landed in r38887.