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