Bug 119657 – JSC: Change StackIterator to not require writes to the JS stack

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Mark Lam]

1. Introduced a StackIterator::FrameReader class to reify inlined frames into its own buffer.  This enables the StackIterator to not write to the JS stack when iterating it.
2. Refactor the code to read better with this new idiom.
3. Fixed the StackIterator::Frame::arguments() method to use the inlined frame version of Arguments::create() and Arguments::tearOff() when the current frame is an inlined frame.

Haven't determined yet if (3) is a bug in the current implementation, or if the fact that the inlined frames have been reified would make the non-inline versions of Arguments work fine.

Patch coming soon.

[Mark Lam]

Created attachment 208481 [details]
the patch.

[EFL EWS Bot]

Comment on attachment 208481 [details]
the patch.

Attachment 208481 [details] did not pass efl-wk2-ews (efl-wk2):
Output: http://webkit-queues.appspot.com/results/1410561

[EFL EWS Bot]

Comment on attachment 208481 [details]
the patch.

Attachment 208481 [details] did not pass efl-ews (efl):
Output: http://webkit-queues.appspot.com/results/1350794

[Geoffrey Garen]

Comment on attachment 208481 [details]
the patch.

View in context: https://bugs.webkit.org/attachment.cgi?id=208481&action=review

Another option is a callback-based API, which passes the values in each frame as arguments to a callback function. That would allow you to eliminate all if this "reify and store physical frame" logic.

I thought we had agreed on that design. What changed?

> Source/JavaScriptCore/interpreter/StackIterator.cpp:50
> +inline StackIterator::FrameReader* StackIterator::FrameReader::fromReaderFrame(StackIterator::Frame* frame)
> +{
> +    ASSERT(frame->isReaderFrame());
> +    ASSERT(!OBJECT_OFFSETOF(StackIterator::FrameReader, m_scratchRegisters));
> +    Register* reg = reinterpret_cast<Register*>(frame);
> +    reg = &reg[-JSStack::CallFrameHeaderSize];
> +    return reinterpret_cast<StackIterator::FrameReader*>(reg);
> +}

It's really not good to establish binary equivalence constraints between classes like this.

> Source/JavaScriptCore/interpreter/StackIterator.h:46
> +    static Frame* create(JSC::Register* callFrameBase) { return reinterpret_cast<Frame*>(callFrameBase); }

Ditto.

> Source/JavaScriptCore/interpreter/StackIterator.h:67
>      CallFrame* callFrame() { return reinterpret_cast<CallFrame*>(this); }

Ditto.

[Mark Lam]

(In reply to comment #4)
> (From update of attachment 208481 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=208481&action=review
> 
> Another option is a callback-based API, which passes the values in each frame as arguments to a callback function. That would allow you to eliminate all if this "reify and store physical frame" logic.
> 
> I thought we had agreed on that design. What changed?

Nothing's changed yet.  We also agreed that I can pass a struct (e.g. the FrameReader in this case, or its internal scratch frame) in the callback function instead of passing a long list of parameters to the callback.  This patch is just a step towards that.  With the callback function, I still need to reify the inline frames into some local memory before passing that to the callback.  In this case, that local memory is collated in the FrameReader's scratch frame.

This patch deals with the "don't write to the stack" part.  I'll deal with the "use a callback function" part in a separate patch.

> > Source/JavaScriptCore/interpreter/StackIterator.cpp:50
> > +inline StackIterator::FrameReader* StackIterator::FrameReader::fromReaderFrame(StackIterator::Frame* frame)
> > +{
> > +    ASSERT(frame->isReaderFrame());
> > +    ASSERT(!OBJECT_OFFSETOF(StackIterator::FrameReader, m_scratchRegisters));
> > +    Register* reg = reinterpret_cast<Register*>(frame);
> > +    reg = &reg[-JSStack::CallFrameHeaderSize];
> > +    return reinterpret_cast<StackIterator::FrameReader*>(reg);
> > +}
> 
> It's really not good to establish binary equivalence constraints between classes like this.
>
> > Source/JavaScriptCore/interpreter/StackIterator.h:46
> > +    static Frame* create(JSC::Register* callFrameBase) { return reinterpret_cast<Frame*>(callFrameBase); }
> 
> Ditto.
> 
> > Source/JavaScriptCore/interpreter/StackIterator.h:67
> >      CallFrame* callFrame() { return reinterpret_cast<CallFrame*>(this); }
> 
> Ditto.

There's a small difference here.  By "binary equivalence constraints", I believe your concerns are the following:
1. The shape of 2 classes may get out of sync.
2. The assumptions made by 1 class about the semantics of the other may get out of outdated.

Let me address those concerns.  I submit to you that the design in this patch is not any more fragile on these 2 issues than any regular C++ inheritance.  Here's why:

1. Regarding your last 2 ditto comments regarding the StackIterator::Frame::create():

    By definition StackIterator::Frame inherits from CallFrame.  Hence, whatever this / base pointer the CalFrame implementation uses, this is the same this / base pointer that StackIterator::Frame should use.  StackIterator::Frame is a strict subclass of CallFrame, and does not add fields to the frame.  There is no issue with the shape getting out of sync.

    What StackIterator::Frame adds is some overloaded functions to get info about the CallFrame.  These functions use CallFrame methods to do its work.  This is no different than how a C++ subclass calls its parent's methods to do more specialized work.

2. Regarding FrameReader::fromReaderFrame():

    I'm basically embedding 1 instance of the CallFrameHeader into the FrameReader.  If the CallFrame was a normal struct, I would have expressed the FrameReader as:

        struct FrameReader {
            struct CallFrame m_scratchFrame;
            CallFrame* m_physicalFrame;
        };

    and the above converter function would be expressed as:

        inline StackIterator::FrameReader* StackIterator::FrameReader::fromReaderFrame(StackIterator::Frame* frame)
        {
            ASSERT(frame->isReaderFrame());
            uint8_t* scratchFrameBase = reinterpret_cast<uint8_t*>(m_scratchFrame);
            uint8_t *readerBase = scratchFrameBase - OBJECT_OFFSETOF(StackIterator::FrameReader, m_scratchFrame);
            return reinterpret_cast<StackIterator::FrameReader*>(readerBase);
        }

    But because the CallFrameHeader is an array of Registers, I should have expressed fromReaderFrame() differently.  I agree that the implementation in the patch is not the best.  Perhaps a better expression of that function would be:

        struct FrameReader {
            Register m_scratchRegisters[JSStack::CallFrameHeaderSize];
            CallFrame* m_physicalFrame;
        };

        inline StackIterator::FrameReader* StackIterator::FrameReader::fromReaderFrame(StackIterator::Frame* frame)
        {
            ASSERT(frame->isReaderFrame());
            uint8_t* scratchFrameBase = reinterpret_cast<uint8_t*>(&frame[-JSStack::CallFrameHeaderSize]);
            uint8_t *readerBase = scratchFrameBase - OBJECT_OFFSETOF(StackIterator::FrameReader, m_scratchRegisters);
            return reinterpret_cast<StackIterator::FrameReader*>(readerBase);
        }

    The only "special" knowledge I make use of here is that the CallFrame base pointer points to the address pass the end of the CallFrameHeader rather than to the start of the CallFrameHeader.  I make no assumptions about the binary organization of the CallFrame internals.  All frame data accesses go through CallFrame methods.  Hence, I don't think "binary equivalence constraints" fragility is an issue here.

    The alternative to this is to make StackIterator::Frame not a subclass of CallFrame, and have FrameReader embed StackIterator::Frame explicitly instead.  What that buys us is not needing the one "special" knowledge above.

Here are the pros and cons of the approach in this patch as well as the alternative:

1. Subclass approach: StackIterator::Frame extends CallFrame (what this patch and the pre-existing StackIterator does)

    Pros:
    1. can use CallFrame methods because they are superclass methods.  Don't have to replicate them in StackIterator::Frame.
    2. automatically inherit any new methods that is added to CallFrame.
    3. no need to copy frame data from the CallFrame to the StackIterator::Frame for non-inlined frames.  Client code can access only the frames it cares about, and only the frame data it cares about. 

    Cons:
    1. the StackIterator has special knowledge that our JS stack's call frame base pointer points to the end of the CallFrameHeader rather than to the start of it.
    2. the StackIterator::Frame is not physically isolated from the actual JS stack CallFrame when the clients access frame info via the iterator.
        Hence, malicious or buggy client code can alter the on-stack CallFrame by modifying the frame the iterator points to.  

2. Isolated class approach: StackIterator::Frame will be completely isolated from CallFrame (the alternative)

    Pros:
    1. if we ever change the CallFrame's base pointer to point to the start of the CallFrameHeader instead of its end, we won't have to update the StackIterator.
    2. malicious or buggy code can track the stack iterator but not the on-stack CallFrame.

    Cons:
    1. Have to replicate (create analogous methods of) all relevant CallFrame methods in the StackIterator::Frame class.
    2. If clients of the iterator need to access new info about the CallFrame, we will need to update the StackIterator::Frame() with an analog of the new CallFrame method.
    3. Need to copy all of the CallFrame's data into the StackIterator::Frame on every iteration even if the client code only needs some of the frame or does not care about certain frames.

Based on the above, my thinking is that for the "subclass approach", cons 1 is highly unlikely.  If that happens, lots of llint and JIT code will break all over.  The StackIterator will be the least of our worries.  Since the iterator is not used by untrusted code, cons 2 is not an issue for malicious code.  As for buggy code, that is a possible concern but I think this is a small one.

As for the "isolated class approach", the cons 1 is more upfront work but, granted, it may be a 1 time cost.  Cons 2 is unlikely as we won't be adding new query methods to the CallFrame often.  Cons 3 will cost us a small performance penalty every time the StackIterator is used, though it could be insignificant.  I haven't measured it yet.

In summary, I think the above explains why I don't believe we have a "binary equivalence constraints" issue here, and also argues for why the existing "subclass approach" of implementing the StackIterator::Frame is beneficial without significant cons.  Is there any additional concern or downside to my approach that I am missing?

Thanks.

[Geoffrey Garen]

Comment on attachment 208481 [details]
the patch.

In C++ code, I'd like CallFrame to be the only class that encodes the layout of the JavaScript stack in memory. It's OK if other classes add features on top of CallFrame. But they should access those features through the CallFrame abstraction, instead of doing direct memory reads and pointer accesses relative to a casted CallFrame pointer.

These parts of your patch don't meet this goal:

- StackIterator::FrameReader::fromReaderFrame
    - reinterpret_casts between Frame* and Register*
    - reinterpret_casts between Register* and FrameReader*
    - Uses manual pointer math to calculate the "beginning" of the stack frame.

I put "beginning" in quotes because, once Michael is finished reversing the stack, this code, due to its fragile design, will no longer access the true beginning, and will get the wrong answer.

- FrameReader::m_scratchRegisters
    - Attempts a bitwise copy of the CallFrame in memory

I say "attempts" because, once Michael is finished, StackIterator::FrameReader::frame() will likely get the wrong answer.

- StackIterator::Frame
    - publicly inherits from CallFrame
    - create() function reinterpret_casts between CallFrame* and Frame*

Public inheritance communicates an "is a" relationship. A StackIterator::Frame is *not* a CallFrame, since it represents data that might have come from a CallFrame, or might have come from a logically inlined function that corresponds to no physical CallFrame.

What I'd like to see instead is for the iterator class to hold a CallFrame*, a "next action" indicator, which tells you if your next action should be to go to the next inlined function, or to go to the next CallFrame, and a normal struct/class that contains the data we care about -- JSFunction*, CodeBlock*, etc. Incrementing the iterator should use the "next action" indicator to decide what to do, decode the relevant information into the struct/class, and update the "next action" indicator. (A "last action" indicator would be a fine equivalent, if that works better.)

Later, the transition to a callback-based API can remove the "next action" indicator, since it will be implicit based on control flow on the stack, and can pass a reference to the struct/class, allocated on the stack, to the callback function.

[Mark Lam]

Created attachment 209830 [details]
patch 2: StackIterator::Frame is its own class (no longer dependent on CallFrame). 

With patch 2, StackIterator::Frame no longer inherits from CallFrame.  The current CallFrame* is stored in the embedded StackIterator::Frame's m_callFrame (because it's needed there) instead of having a second copy of that pointer in StackIterator.

This implementation did not add an explicit "next action" indicator.  Instead, it relies on a readFrame() function that knows how to extract info from the current frame.  To determine how to get the caller / next frame, we check if the current frame is an inlined frame.  If the current frame is inlined, then the next frame is determined by the physical frame, and the caller's CodeOrigin (see StackIterator::updateFrame()).  The current implementation allows us to always read the first frame without prior knowledge about whether it is an inlined frame or not.  In essence, the current CallFrame* in conjunction with the current inlined frame info (InlineCallFrame*) is kind of like a "last action" indicator.

This implementation has passed the following layout tests (on a debug build) with no regression:
fast/js fast/regex fast/workers ietestcenter/JavaScript sputnik workers inspector http/tests/inspector http/tests/security http/tests/workers

Will run the full layout tests later.  The javascriptcore tests also ran with no regression.

This implementation has been run on the jsc benchmarks with no performance regression.  I will attached the results of the 2 benchmark runs shortly.

[WebKit Commit Bot]

Attachment 209830 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source/JavaScriptCore/GNUmakefile.list.am', u'Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj', u'Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj.filters', u'Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj', u'Source/JavaScriptCore/interpreter/CallFrame.h', u'Source/JavaScriptCore/interpreter/StackIterator.cpp', u'Source/JavaScriptCore/interpreter/StackIterator.h', u'Source/JavaScriptCore/interpreter/StackIteratorPrivate.h']" exit_code: 1
Source/JavaScriptCore/ChangeLog:31:  Line contains tab character.  [whitespace/tab] [5]
Source/JavaScriptCore/interpreter/StackIterator.h:157:  Line contains only semicolon. If this should be an empty statement, use { } instead.  [whitespace/semicolon] [5]
Total errors found: 2 in 6 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Mark Lam]

Created attachment 209831 [details]
patch 2: benchmark run 1

[Mark Lam]

Created attachment 209832 [details]
patch 2: benchmark run 2

[Mark Lam]

(In reply to comment #8)
> Source/JavaScriptCore/ChangeLog:31:  Line contains tab character.  [whitespace/tab] [5]

Oops.  Will fix before landing.

> Source/JavaScriptCore/interpreter/StackIterator.h:157:  Line contains only semicolon. If this should be an empty statement, use { } instead.  [whitespace/semicolon] [5]

This one is because of the need for a #if ENABLE(DFG_JIT) check around one of the expressions terms.

[Geoffrey Garen]

Comment on attachment 209830 [details]
patch 2: StackIterator::Frame is its own class (no longer dependent on CallFrame). 

View in context: https://bugs.webkit.org/attachment.cgi?id=209830&action=review

Looking better, but would still benefit from refinement.

> Source/JavaScriptCore/interpreter/StackIterator.cpp:66
>  void StackIterator::gotoNextFrame()

This should be called "gotoNextFrameWithFilter".

> Source/JavaScriptCore/interpreter/StackIterator.cpp:107
> +    // Hence, we're not at not an inlined frame.

Please remove the second "not".

> Source/JavaScriptCore/interpreter/StackIterator.cpp:136
> +    // Else, we're in an inlined frame.

This comment says exactly what the line of code below it says, so you should remove it.

> Source/JavaScriptCore/interpreter/StackIterator.cpp:144
> +    m_frame.m_argumentCount = callFrame->argumentCountIncludingThis();

If you're going to store argumentCountIncludingThis, you should call it argumentCountIncludingThis. argumentCount is a term of art for the count excluding the implicit 'this' argument.

> Source/JavaScriptCore/interpreter/StackIterator.cpp:195
> +        // frame would work just fine.

I don't understand what "Setting it to the physical frame would work just fine" means. Is that what you're doing here?

> Source/JavaScriptCore/interpreter/StackIterator.cpp:204
> +void StackIterator::updateFrame()

This should be called "gotoNextFrame".

> Source/JavaScriptCore/interpreter/StackIterator.h:98
> +        InlineCallFrame* m_inlinedFrameInfo;

It is bad when one thing becomes two.

Let's call this InlineCallFrame* "m_inlineCallFrame".

> Source/JavaScriptCore/interpreter/StackIterator.h:114
> +    inline bool operator==(Frame*);
> +    bool operator!=(Frame* frame) { return !(*this == frame); }

This is weird API. StackIterators should compare against StackIterators, not Frame pointers.

[Mark Lam]

Created attachment 209946 [details]
patch 3: applied Geoff's refinement suggestions.

Thanks for the review.  Geoff's refinement suggestions have been applied in patch 3.  Please take another look.

[WebKit Commit Bot]

Attachment 209946 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source/JavaScriptCore/GNUmakefile.list.am', u'Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj', u'Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj.filters', u'Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj', u'Source/JavaScriptCore/interpreter/CallFrame.cpp', u'Source/JavaScriptCore/interpreter/CallFrame.h', u'Source/JavaScriptCore/interpreter/StackIterator.cpp', u'Source/JavaScriptCore/interpreter/StackIterator.h', u'Source/JavaScriptCore/interpreter/StackIteratorPrivate.h']" exit_code: 1
Source/JavaScriptCore/interpreter/StackIterator.h:153:  Line contains only semicolon. If this should be an empty statement, use { } instead.  [whitespace/semicolon] [5]
Total errors found: 1 in 7 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Geoffrey Garen]

Comment on attachment 209946 [details]
patch 3: applied Geoff's refinement suggestions.

View in context: https://bugs.webkit.org/attachment.cgi?id=209946&action=review

r=me with two changes below.

> Source/JavaScriptCore/interpreter/StackIterator.cpp:98
> +const StackIterator& StackIterator::end()
> +{
> +    DEFINE_STATIC_LOCAL(StackIterator, endIter, (0, 0));
> +    return endIter;

There are lots of problems with using a static for an iterator end value.

(1) Fragments the heap.

(2) Not thread-safe.

(3) Prevents the compiler from optimizing, because it turns a constant into a load from the heap.

Please turn this into a normal return of a value before landing.

> Source/JavaScriptCore/interpreter/StackIterator.h:147
> +    if (this == &other)
> +        return true;

This extra branch is a pessimization, since it's false until the very last iteration. Please remove it before landing.

[Mark Lam]

Created attachment 209999 [details]
patch 4: StackIterator::end() returns a value instead of a ref + removed pessimization in operator==().

Uploading patch 4 so that it is the patch of record for the benchmark results I will upload shortly.

The only reason I had StackIterator::end() return a reference to a static instead a value in the first place is because I was previously concerned that end() being tested continually in for loop termination tests may perturb performance negatively.  I ran 2 runs of the jsc benchmarks comparing StackIterator::end() returning a reference vs returning a value.  The only benchmark that consistently show a regression (from this small sample of 2 runs) is:

JSRegress (run 1):
   adapt-to-double-divide                                           21.4066+-0.0252     !     21.5173+-0.0582        ! definitely 1.0052x slower
   ...
   <geometric> *                                                    14.3499+-0.2221           14.3442+-0.2387          might be 1.0004x faster

JSRegress (run 2):
   adapt-to-double-divide                                           21.3965+-0.0238     !     21.5738+-0.0729        ! definitely 1.0083x slower
   ...
   <geometric> *                                                    14.3521+-0.2246     ?     14.3531+-0.2228        ? might be 1.0001x slower

However, the overall results shows it to be insignificant.  I will land this patch with StackIterator::end() returning a value.  FYI, the layout tests shows no regression when run with a release build.

[Mark Lam]

Created attachment 210000 [details]
patch 4: benchmark run 1 comparing StackIterator::end() returning a reference vs a value.

[Mark Lam]

Created attachment 210001 [details]
patch 4: benchmark run 2 comparing StackIterator::end() returning a reference vs a value.

[Mark Lam]

Thanks for the review.  Landed in r154821: <http://trac.webkit.org/r154821>.

[WebKit Commit Bot]

Re-opened since this is blocked by bug 120481

[Mark Lam]

(In reply to comment #20)
> Re-opened since this is blocked by bug 120481

bug 120481 has been fixed.