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