b202824538c752567fcec5d898f85b16209f0e8a
[WebKit-https.git] / Source / JavaScriptCore / interpreter / ShadowChicken.cpp
1 /*
2  * Copyright (C) 2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "ShadowChicken.h"
28
29 #include "CodeBlock.h"
30 #include "JSCInlines.h"
31 #include "ShadowChickenInlines.h"
32 #include <wtf/ListDump.h>
33
34 namespace JSC {
35
36 static const bool verbose = false;
37
38 void ShadowChicken::Packet::dump(PrintStream& out) const
39 {
40     if (!*this) {
41         out.print("empty");
42         return;
43     }
44     
45     if (isPrologue()) {
46         out.print(
47             "{callee = ", RawPointer(callee), ", frame = ", RawPointer(frame), ", callerFrame = ",
48             RawPointer(callerFrame), "}");
49         return;
50     }
51     
52     if (isTail()) {
53         out.print("tail-packet:{frame = ", RawPointer(frame), "}");
54         return;
55     }
56     
57     ASSERT(isThrow());
58     out.print("throw");
59 }
60
61 void ShadowChicken::Frame::dump(PrintStream& out) const
62 {
63     out.print(
64         "{callee = ", RawPointer(callee), ", frame = ", RawPointer(frame), ", isTailDeleted = ",
65         isTailDeleted, "}");
66 }
67
68 ShadowChicken::ShadowChicken()
69     : m_logSize(Options::shadowChickenLogSize())
70 {
71     m_log = static_cast<Packet*>(fastZeroedMalloc(sizeof(Packet) * m_logSize));
72     m_logCursor = m_log;
73     m_logEnd = m_log + m_logSize;
74 }
75
76 ShadowChicken::~ShadowChicken()
77 {
78     fastFree(m_log);
79 }
80
81 void ShadowChicken::log(VM& vm, ExecState* exec, const Packet& packet)
82 {
83     update(vm, exec);
84     *m_logCursor++ = packet;
85 }
86
87 void ShadowChicken::update(VM&, ExecState* exec)
88 {
89     if (verbose) {
90         dataLog("Running update on: ", *this, "\n");
91         WTFReportBacktrace();
92     }
93     
94     const unsigned logCursorIndex = m_logCursor - m_log;
95     
96     // We need to figure out how to reconcile the current machine stack with our shadow stack. We do
97     // that by figuring out how much of the shadow stack to pop. We apply three different rules. The
98     // precise rule relies on the log. The log contains caller frames, which means that we know
99     // where we bottomed out after making any call. If we bottomed out but made no calls then 'exec'
100     // will tell us. That's why "highestPointSinceLastTime" will go no lower than exec. The third
101     // rule, based on comparing to the current real stack, is executed in a later loop.
102     CallFrame* highestPointSinceLastTime = exec;
103     for (unsigned i = logCursorIndex; i--;) {
104         Packet packet = m_log[i];
105         if (packet.isPrologue()) {
106             CallFrame* watermark;
107             if (i && m_log[i - 1].isTail())
108                 watermark = packet.frame;
109             else
110                 watermark = packet.callerFrame;
111             highestPointSinceLastTime = std::max(highestPointSinceLastTime, watermark);
112         }
113     }
114     
115     if (verbose)
116         dataLog("Highest point since last time: ", RawPointer(highestPointSinceLastTime), "\n");
117     
118     while (!m_stack.isEmpty() && (m_stack.last().frame < highestPointSinceLastTime || m_stack.last().isTailDeleted))
119         m_stack.removeLast();
120     
121     if (verbose)
122         dataLog("    Revised stack: ", listDump(m_stack), "\n");
123     
124     // It's possible that the top of stack is now tail-deleted. The stack no longer contains any
125     // frames below the log's high watermark. That means that we just need to look for the first
126     // occurence of a tail packet for the current stack top.
127     if (!m_stack.isEmpty()) {
128         ASSERT(!m_stack.last().isTailDeleted);
129         for (unsigned i = 0; i < logCursorIndex; ++i) {
130             Packet& packet = m_log[i];
131             if (packet.isTail() && packet.frame == m_stack.last().frame) {
132                 Frame& frame = m_stack.last();
133                 frame.thisValue = packet.thisValue;
134                 frame.scope = packet.scope;
135                 frame.codeBlock = packet.codeBlock;
136                 frame.callSiteIndex = packet.callSiteIndex;
137                 frame.isTailDeleted = true;
138                 break;
139             }
140         }
141     }
142
143     
144     if (verbose)
145         dataLog("    Revised stack: ", listDump(m_stack), "\n");
146     
147     // The log-based and exec-based rules require that ShadowChicken was enabled. The point of
148     // ShadowChicken is to give sensible-looking results even if we had not logged. This means that
149     // we need to reconcile the shadow stack and the real stack by actually looking at the real
150     // stack. This reconciliation allows the shadow stack to have extra tail-deleted frames, but it
151     // forbids it from diverging from the real stack on normal frames.
152     if (!m_stack.isEmpty()) {
153         Vector<Frame> stackRightNow;
154         StackVisitor::visit(
155             exec, [&] (StackVisitor& visitor) -> StackVisitor::Status {
156                 if (visitor->isInlinedFrame())
157                     return StackVisitor::Continue;
158                 if (visitor->isWasmFrame()) {
159                     // FIXME: Make shadow chicken work with Wasm.
160                     // https://bugs.webkit.org/show_bug.cgi?id=165441
161                     return StackVisitor::Continue;
162                 }
163
164                 bool isTailDeleted = false;
165                 // FIXME: Make shadow chicken work with Wasm.
166                 // https://bugs.webkit.org/show_bug.cgi?id=165441
167                 stackRightNow.append(Frame(jsCast<JSObject*>(visitor->callee()), visitor->callFrame(), isTailDeleted));
168                 return StackVisitor::Continue;
169             });
170         stackRightNow.reverse();
171         
172         if (verbose)
173             dataLog("    Stack right now: ", listDump(stackRightNow), "\n");
174         
175         unsigned shadowIndex = 0;
176         unsigned rightNowIndex = 0;
177         while (shadowIndex < m_stack.size() && rightNowIndex < stackRightNow.size()) {
178             if (m_stack[shadowIndex].isTailDeleted) {
179                 shadowIndex++;
180                 continue;
181             }
182
183             // We specifically don't use operator== here because we are using a less
184             // strict filter on equality of frames. For example, the scope pointer
185             // could change, but we wouldn't want to consider the frames different entities
186             // because of that because it's natural for the program to change scopes.
187             if (m_stack[shadowIndex].frame == stackRightNow[rightNowIndex].frame
188                 && m_stack[shadowIndex].callee == stackRightNow[rightNowIndex].callee) {
189                 shadowIndex++;
190                 rightNowIndex++;
191                 continue;
192             }
193             break;
194         }
195         m_stack.resize(shadowIndex);
196         
197         if (verbose)
198             dataLog("    Revised stack: ", listDump(m_stack), "\n");
199     }
200     
201     // It's possible that the top stack frame is actually lower than highestPointSinceLastTime.
202     // Account for that here.
203     highestPointSinceLastTime = nullptr;
204     for (unsigned i = m_stack.size(); i--;) {
205         if (!m_stack[i].isTailDeleted) {
206             highestPointSinceLastTime = m_stack[i].frame;
207             break;
208         }
209     }
210     
211     if (verbose)
212         dataLog("    Highest point since last time: ", RawPointer(highestPointSinceLastTime), "\n");
213     
214     // Set everything up so that we know where the top frame is in the log.
215     unsigned indexInLog = logCursorIndex;
216     
217     auto advanceIndexInLogTo = [&] (CallFrame* frame, JSObject* callee, CallFrame* callerFrame) -> bool {
218         if (verbose)
219             dataLog("    Advancing to frame = ", RawPointer(frame), " from indexInLog = ", indexInLog, "\n");
220         if (indexInLog > logCursorIndex) {
221             if (verbose)
222                 dataLog("    Bailing.\n");
223             return false;
224         }
225         
226         unsigned oldIndexInLog = indexInLog;
227         
228         while (indexInLog--) {
229             Packet packet = m_log[indexInLog];
230             
231             // If all callees opt into ShadowChicken, then this search will rapidly terminate when
232             // we find our frame. But if our frame's callee didn't emit a prologue packet because it
233             // didn't opt in, then we will keep looking backwards until we *might* find a different
234             // frame. If we've been given the callee and callerFrame as a filter, then it's unlikely
235             // that we will hit the wrong frame. But we don't always have that information.
236             //
237             // This means it's worth adding other filters. For example, we could track changes in
238             // stack size. Once we've seen a frame at some height, we're no longer interested in
239             // frames below that height. Also, we can break as soon as we see a frame higher than
240             // the one we're looking for.
241             // FIXME: Add more filters.
242             // https://bugs.webkit.org/show_bug.cgi?id=155685
243             
244             if (packet.isPrologue() && packet.frame == frame
245                 && (!callee || packet.callee == callee)
246                 && (!callerFrame || packet.callerFrame == callerFrame)) {
247                 if (verbose)
248                     dataLog("    Found at indexInLog = ", indexInLog, "\n");
249                 return true;
250             }
251         }
252         
253         // This is an interesting eventuality. We will see this if ShadowChicken was not
254         // consistently enabled. We have a choice between:
255         //
256         // - Leaving the log index at -1, which will prevent the log from being considered. This is
257         //   the most conservative. It means that we will not be able to recover tail-deleted frames
258         //   from anything that sits above a frame that didn't log a prologue packet. This means
259         //   that everyone who creates prologues must log prologue packets.
260         //
261         // - Restoring the log index to what it was before. This prevents us from considering
262         //   whether this frame has tail-deleted frames behind it, but that's about it. The problem
263         //   with this approach is that it might recover tail-deleted frames that aren't relevant.
264         //   I haven't thought about this too deeply, though.
265         //
266         // It seems like the latter option is less harmful, so that's what we do.
267         indexInLog = oldIndexInLog;
268         
269         if (verbose)
270             dataLog("    Didn't find it.\n");
271         return false;
272     };
273     
274     Vector<Frame> toPush;
275     StackVisitor::visit(
276         exec, [&] (StackVisitor& visitor) -> StackVisitor::Status {
277             if (visitor->isInlinedFrame()) {
278                 // FIXME: Handle inlining.
279                 // https://bugs.webkit.org/show_bug.cgi?id=155686
280                 return StackVisitor::Continue;
281             }
282
283             if (visitor->isWasmFrame()) {
284                 // FIXME: Make shadow chicken work with Wasm.
285                 return StackVisitor::Continue;
286             }
287
288             CallFrame* callFrame = visitor->callFrame();
289             if (verbose)
290                 dataLog("    Examining ", RawPointer(callFrame), "\n");
291             if (callFrame == highestPointSinceLastTime) {
292                 if (verbose)
293                     dataLog("    Bailing at ", RawPointer(callFrame), " because it's the highest point since last time.\n");
294                 return StackVisitor::Done;
295             }
296
297             bool foundFrame = advanceIndexInLogTo(callFrame, callFrame->jsCallee(), callFrame->callerFrame());
298             bool isTailDeleted = false;
299             JSScope* scope = nullptr;
300             CodeBlock* codeBlock = callFrame->codeBlock();
301             if (codeBlock && codeBlock->wasCompiledWithDebuggingOpcodes() && codeBlock->scopeRegister().isValid()) {
302                 scope = callFrame->scope(codeBlock->scopeRegister().offset());
303                 RELEASE_ASSERT(scope->inherits(JSScope::info()));
304             } else if (foundFrame) {
305                 scope = m_log[indexInLog].scope;
306                 if (scope)
307                     RELEASE_ASSERT(scope->inherits(JSScope::info()));
308             }
309             toPush.append(Frame(jsCast<JSObject*>(visitor->callee()), callFrame, isTailDeleted, callFrame->thisValue(), scope, codeBlock, callFrame->callSiteIndex()));
310
311             if (indexInLog < logCursorIndex
312                 // This condition protects us from the case where advanceIndexInLogTo didn't find
313                 // anything.
314                 && m_log[indexInLog].frame == toPush.last().frame) {
315                 if (verbose)
316                     dataLog("    Going to loop through to find tail deleted frames with indexInLog = ", indexInLog, " and push-stack top = ", toPush.last(), "\n");
317                 for (;;) {
318                     ASSERT(m_log[indexInLog].frame == toPush.last().frame);
319                     
320                     // Right now the index is pointing at a prologue packet of the last frame that
321                     // we pushed. Peek behind that packet to see if there is a tail packet. If there
322                     // is one then we know that there is a corresponding prologue packet that will
323                     // tell us about a tail-deleted frame.
324                     
325                     if (!indexInLog)
326                         break;
327                     Packet tailPacket = m_log[indexInLog - 1];
328                     if (!tailPacket.isTail()) {
329                         // Last frame that we recorded was not the outcome of a tail call. So, there
330                         // will not be any more deleted frames.
331                         // FIXME: We might want to have a filter here. Consider that this was a tail
332                         // marker for a tail call to something that didn't log anything. It should
333                         // be sufficient to give the tail marker a copy of the caller frame.
334                         // https://bugs.webkit.org/show_bug.cgi?id=155687
335                         break;
336                     }
337                     indexInLog--; // Skip over the tail packet.
338                     
339                     if (!advanceIndexInLogTo(tailPacket.frame, nullptr, nullptr)) {
340                         if (verbose)
341                             dataLog("Can't find prologue packet for tail: ", RawPointer(tailPacket.frame), "\n");
342                         // We were unable to locate the prologue packet for this tail packet.
343                         // This is rare but can happen in a situation like:
344                         // function foo() {
345                         //     ... call some deeply tail-recursive function, causing a random number of log processings.
346                         //     return bar(); // tail call
347                         // }
348                         break;
349                     }
350                     Packet packet = m_log[indexInLog];
351                     bool isTailDeleted = true;
352                     RELEASE_ASSERT(tailPacket.scope->inherits(JSScope::info()));
353                     toPush.append(Frame(packet.callee, packet.frame, isTailDeleted, tailPacket.thisValue, tailPacket.scope, tailPacket.codeBlock, tailPacket.callSiteIndex));
354                 }
355             }
356
357             return StackVisitor::Continue;
358         });
359
360     if (verbose)
361         dataLog("    Pushing: ", listDump(toPush), "\n");
362     
363     for (unsigned i = toPush.size(); i--;)
364         m_stack.append(toPush[i]);
365     
366     // We want to reset the log. There is a fun corner-case: there could be a tail marker at the end
367     // of this log. We could make that work by setting isTailDeleted on the top of stack, but that
368     // would require more corner cases in the complicated reconciliation code above. That code
369     // already knows how to handle a tail packet at the beginning, so we just leverage that here.
370     if (logCursorIndex && m_log[logCursorIndex - 1].isTail()) {
371         m_log[0] = m_log[logCursorIndex - 1];
372         m_logCursor = m_log + 1;
373     } else
374         m_logCursor = m_log;
375
376     if (verbose)
377         dataLog("    After pushing: ", *this, "\n");
378
379     // Remove tail frames until the number of tail deleted frames is small enough.
380     const unsigned maxTailDeletedFrames = Options::shadowChickenMaxTailDeletedFramesSize();
381     if (m_stack.size() > maxTailDeletedFrames) {
382         unsigned numberOfTailDeletedFrames = 0;
383         for (const Frame& frame : m_stack) {
384             if (frame.isTailDeleted)
385                 numberOfTailDeletedFrames++;
386         }
387         if (numberOfTailDeletedFrames > maxTailDeletedFrames) {
388             unsigned dstIndex = 0;
389             unsigned srcIndex = 0;
390             while (srcIndex < m_stack.size()) {
391                 Frame frame = m_stack[srcIndex++];
392                 if (numberOfTailDeletedFrames > maxTailDeletedFrames && frame.isTailDeleted) {
393                     numberOfTailDeletedFrames--;
394                     continue;
395                 }
396                 m_stack[dstIndex++] = frame;
397             }
398             m_stack.resize(dstIndex);
399         }
400     }
401
402     if (verbose)
403         dataLog("    After clean-up: ", *this, "\n");
404 }
405
406 void ShadowChicken::visitChildren(SlotVisitor& visitor)
407 {
408     for (unsigned i = m_logCursor - m_log; i--;) {
409         JSObject* callee = m_log[i].callee;
410         if (callee != Packet::tailMarker() && callee != Packet::throwMarker())
411             visitor.appendUnbarrieredReadOnlyPointer(callee);
412         if (callee != Packet::throwMarker())
413             visitor.appendUnbarrieredReadOnlyPointer(m_log[i].scope);
414         if (callee == Packet::tailMarker()) {
415             visitor.appendUnbarrieredValue(&m_log[i].thisValue);
416             visitor.appendUnbarrieredReadOnlyPointer(m_log[i].codeBlock);
417         }
418     }
419     
420     for (unsigned i = m_stack.size(); i--; ) {
421         Frame& frame = m_stack[i];
422         visitor.appendUnbarrieredValue(&frame.thisValue);
423         visitor.appendUnbarrieredReadOnlyPointer(frame.callee);
424         if (frame.scope)
425             visitor.appendUnbarrieredReadOnlyPointer(frame.scope);
426         if (frame.codeBlock)
427             visitor.appendUnbarrieredReadOnlyPointer(frame.codeBlock);
428     }
429 }
430
431 void ShadowChicken::reset()
432 {
433     m_logCursor = m_log;
434     m_stack.clear();
435 }
436
437 void ShadowChicken::dump(PrintStream& out) const
438 {
439     out.print("{stack = [", listDump(m_stack), "], log = [");
440     
441     CommaPrinter comma;
442     unsigned limit = static_cast<unsigned>(m_logCursor - m_log);
443     out.print("\n");
444     for (unsigned i = 0; i < limit; ++i)
445         out.print("\t", comma, m_log[i], "\n");
446     out.print("]}");
447 }
448
449 JSArray* ShadowChicken::functionsOnStack(ExecState* exec)
450 {
451     VM& vm = exec->vm();
452     auto scope = DECLARE_THROW_SCOPE(vm);
453     JSArray* result = constructEmptyArray(exec, 0);
454     RETURN_IF_EXCEPTION(scope, nullptr);
455
456     iterate(
457         vm, exec,
458         [&] (const Frame& frame) -> bool {
459             result->push(exec, frame.callee);
460             RELEASE_ASSERT(!scope.exception()); // This function is only called from tests.
461             return true;
462         });
463     
464     return result;
465 }
466
467 } // namespace JSC
468