bernsteinbear.com
this repo has no description
1/* Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com) */
2#pragma once
3
4#include <cstring>
5
6#include "bytecode.h"
7#include "globals.h"
8#include "handles-decl.h"
9#include "objects.h"
10
11namespace py {
12
13// TryBlock contains the unmarshaled block stack information.
14//
15// Block stack entries are encoded and stored on the stack as a single
16// SmallInt using the following format:
17//
18// Name Size Description
19// ----------------------------------------------------
20// (kSmallIntTag 1)
21// Kind 1 The kind of block this entry represents.
22// Handler 30 Where to jump to find the handler
23// Level 32 Value stack level to pop to
24class TryBlock {
25 public:
26 // cpython stores the opcode that pushed the block as the block kind, but only
27 // 4 opcodes actually push blocks. Store the same information with fewer bits.
28 enum Kind {
29 kExceptHandler,
30 kFinally,
31 };
32
33 explicit TryBlock(RawObject value) {
34 DCHECK(value.isSmallInt(), "expected small integer");
35 value_ = value.raw();
36 }
37
38 TryBlock(Kind kind, word handler, word level) {
39 DCHECK((handler & ~kHandlerMask) == 0, "handler too big");
40 DCHECK((level & ~kLevelMask) == 0, "level too big");
41 value_ = static_cast<uword>(kind) << kKindOffset |
42 handler << kHandlerOffset | level << kLevelOffset;
43 }
44
45 RawObject asSmallInt() const;
46
47 Kind kind() const;
48
49 word handler() const;
50
51 word level() const;
52
53 static const int kKindOffset = RawObject::kSmallIntTagBits;
54 static const int kKindSize = 1;
55 static const uword kKindMask = (1 << kKindSize) - 1;
56
57 static const int kHandlerOffset = kKindOffset + kKindSize; // 9
58 static const int kHandlerSize = 30;
59 static const uword kHandlerMask = (uword{1} << kHandlerSize) - 1;
60
61 static const int kLevelOffset = kHandlerOffset + kHandlerSize; // 39
62 static const int kLevelSize = 32;
63 static const uword kLevelMask = (uword{1} << kLevelSize) - 1;
64
65 static const int kSize = kLevelOffset + kLevelSize;
66
67 static_assert(kSize <= kBitsPerWord, "TryBlock must fit into a word");
68
69 private:
70 uword value_;
71};
72
73// A stack frame.
74//
75// Prior to a function call, the stack will look like
76//
77// Function
78// Arg 0
79// ...
80// Arg N
81// <- Top of stack / lower memory addresses
82//
83// The function prologue is responsible for reserving space for local variables
84// and pushing other frame metadata needed by the interpreter onto the stack.
85// After the prologue, and immediately before the interpreter is re-invoked,
86// the stack looks like:
87//
88// Implicit Globals[1]
89// Function
90// Arg 0 <------------------------------------------------+
91// ... |
92// Arg N |
93// Locals 0 |
94// ... |
95// Locals N |
96// +-------------------------------+ Frame (fixed size) |
97// |+----------------+ BlockStack | |
98// || Blockstack top | | |
99// || . | ^ | |
100// || . | | | |
101// || . entries | | growth | |
102// |+----------------+ | |
103// | Blockstack Depth/Return Mode | |
104// | Locals Offset ----------------|----------------------+
105// | Virtual PC |
106// | Previous frame ptr |<-+ <--Frame pointer
107// +-------------------------------+
108// . .
109// . | growth .
110// . Value stack | .
111// . v .
112// +...............................+
113//
114// [1] Only available for non-optimized functions started via
115// `Thread::runClassFunction()` or `Thread::exec()`. for example, module- and
116// class-body function.
117//
118//
119// Implicit Globals
120// ================
121// Python code started via `Thread::runClassFunction()` or `Thread::exec()`
122// which is used for things like module- and class-bodies or `eval()` may store
123// their local variables in arbitrary mapping objects. In this case the
124// functions will have the OPTIMIZED and NEWLOCALS flags cleared and the
125// bytecode will use STORE_NAME/LOAD_NAME rather than STORE_FAST/LOAD_FAST.
126//
127// We use the term implicit globals in accordance with the Python language
128// reference. Note that CPython code and APIs often use the term "locals"
129// instead. We do not use that term to avoid confusion with fast locals.
130//
131// In our system the implicit globals part of the frame only exists for
132// functions that use them. It may contain an arbitrary mapping or `None`.
133// `None` is a performance optimization in our system. It indicates that we
134// directly write into the globals / `function().moduleObject()` instead of
135// using the `implicitGlobals()` this way we can skip setting up a `ModuleProxy`
136// object for this case and avoid the extra indirection.
137class Frame {
138 public:
139 enum ReturnMode {
140 kNormal = 0,
141 kExitRecursiveInterpreter = 1 << 0,
142 kProfilerReturn = 1 << 1,
143 kJitReturn = 1 << 2,
144 };
145
146 // Returns true if this frame is for a built-in or extension function. This
147 // means no bytecode exists and functions like virtualPC() or caches() must
148 // not be used.
149 bool isNative();
150
151 // Function arguments, local variables, cell variables, and free variables
152 RawObject local(word idx);
153 void setLocal(word idx, RawObject value);
154
155 RawObject localWithReverseIndex(word reverse_idx);
156 void setLocalWithReverseIndex(word reverse_idx, RawObject value);
157
158 RawFunction function();
159
160 word blockStackDepthReturnMode();
161 void setBlockStackDepthReturnMode(word value);
162
163 bool blockStackEmpty();
164 TryBlock blockStackPeek();
165 TryBlock blockStackPop();
166 void blockStackPush(TryBlock block);
167
168 void addReturnMode(word mode);
169 word returnMode();
170
171 // Index in the bytecode array of the next instruction to be executed.
172 word virtualPC();
173 void setVirtualPC(word pc);
174
175 word localsOffset();
176 void setLocalsOffset(word locals_offset);
177
178 // Index in the bytecode array of the instruction currently being executed.
179 word currentPC();
180
181 // The implicit globals namespace. This is only available when the
182 // code does not have OPTIMIZED and NEWLOCALS flags set. See the class
183 // comment for details.
184 RawObject implicitGlobals();
185
186 RawMutableBytes bytecode();
187 void setBytecode(RawMutableBytes bytecode);
188
189 RawObject caches();
190 void setCaches(RawObject caches);
191
192 RawObject code();
193
194 // A pointer to the previous frame or nullptr if this is the first frame
195 Frame* previousFrame();
196 void setPreviousFrame(Frame* frame);
197
198 // Returns a pointer to the end of the frame including locals / parameters.
199 RawObject* frameEnd() {
200 // The locals() pointer points at the first local, so we need + 1 to skip
201 // the first local and another +1 to skip the function reference before.
202 return locals() + kFunctionOffsetFromLocals + 1;
203 }
204
205 bool isSentinel();
206
207 // Versions of valueStackTop() and popValue() for a Frame that's had
208 // stashStackSize() called on it.
209 RawObject* stashedValueStackTop();
210 word stashedStackSize();
211 RawObject stashedPopValue();
212
213 // Encode value stack size into the "previous frame" field. This
214 // representation is used for paused GeneratorFrame objects on the heap.
215 void stashStackSize(word size);
216
217 // Compute the total space required for a frame object
218 static word allocationSize(RawObject code);
219
220 // Returns nullptr if the frame is well formed, otherwise an error message.
221 const char* isInvalid();
222
223 static const int kMaxBlockStackDepth = 20;
224
225 static const int kBytecodeOffset = 0;
226 static const int kCachesOffset = kBytecodeOffset + kPointerSize;
227 static const int kPreviousFrameOffset = kCachesOffset + kPointerSize;
228 static const int kVirtualPCOffset = kPreviousFrameOffset + kPointerSize;
229 static const int kLocalsOffsetOffset = kVirtualPCOffset + kPointerSize;
230 static const int kBlockStackDepthReturnModeOffset =
231 kLocalsOffsetOffset + kPointerSize;
232 static const int kBlockStackOffset =
233 kBlockStackDepthReturnModeOffset + kPointerSize;
234 static const int kSize =
235 kBlockStackOffset + (kMaxBlockStackDepth * kPointerSize);
236
237 static_assert(RawGeneratorFrame::kFrameSize == kSize, "frame size mismatch");
238 // For stashed frames we save the stack size in previous frame offset.
239 static_assert(RawGeneratorFrame::kStackSizeFrameOffset ==
240 kPreviousFrameOffset,
241 "previous frame / stack size mismatch");
242
243 static const int kFunctionOffsetFromLocals = 0;
244 static const int kImplicitGlobalsOffsetFromLocals = 1;
245
246 // A large PC value represents finished generators. It must be an even number
247 // to fit the constraints of `setVirtualPC()`/`virtualPD()`.
248 static const word kFinishedGeneratorPC = RawSmallInt::kMaxValue - 1;
249
250 static const int kBlockStackDepthBits = 32;
251 static const word kBlockStackDepthMask =
252 (word{1} << kBlockStackDepthBits) - 1;
253 static const word kReturnModeOffset = 32;
254
255 // Returns a pointer to the "begin" of where the arguments + locals are stored
256 // on the stack. For example local 0 can be found at `locals()[-1]` local 1
257 // at `locals()[-2]`.
258 RawObject* locals();
259
260 private:
261 uword address();
262 RawObject at(int offset);
263 void atPut(int offset, RawObject value);
264
265 DISALLOW_COPY_AND_ASSIGN(Frame);
266};
267
268class FrameVisitor {
269 public:
270 virtual bool visit(Frame* frame) = 0;
271 virtual ~FrameVisitor() = default;
272};
273
274class Arguments {
275 public:
276 Arguments() = default;
277 Arguments(Frame* frame) : locals_(frame->locals()) {}
278
279 RawObject get(word n) const { return *(locals_ - n - 1); }
280
281 protected:
282 RawObject* locals_;
283};
284
285RawObject frameLocals(Thread* thread, Frame* frame);
286
287inline bool Frame::isNative() {
288 return !code().isCode() || RawCode::cast(code()).isNative();
289}
290
291inline uword Frame::address() { return reinterpret_cast<uword>(this); }
292
293inline RawObject Frame::at(int offset) {
294 return *reinterpret_cast<RawObject*>(address() + offset);
295}
296
297inline void Frame::atPut(int offset, RawObject value) {
298 *reinterpret_cast<RawObject*>(address() + offset) = value;
299}
300
301inline word Frame::blockStackDepthReturnMode() {
302 return RawSmallInt::cast(at(kBlockStackDepthReturnModeOffset))
303 .asReinterpretedWord();
304}
305
306inline void Frame::setBlockStackDepthReturnMode(word value) {
307 atPut(kBlockStackDepthReturnModeOffset,
308 RawSmallInt::fromReinterpretedWord(value));
309}
310
311inline bool Frame::blockStackEmpty() {
312 return (blockStackDepthReturnMode() & kBlockStackDepthMask) == 0;
313}
314
315inline TryBlock Frame::blockStackPeek() {
316 word depth = blockStackDepthReturnMode() & kBlockStackDepthMask;
317 DCHECK(depth > 0, "cannot peek into empty blockstack");
318 return TryBlock(at(kBlockStackOffset + depth - kPointerSize));
319}
320
321inline TryBlock Frame::blockStackPop() {
322 word new_depth_return_mode = blockStackDepthReturnMode() - kPointerSize;
323 word new_depth = new_depth_return_mode & kBlockStackDepthMask;
324 DCHECK(new_depth >= 0, "block stack underflow");
325 TryBlock result(at(kBlockStackOffset + new_depth));
326 setBlockStackDepthReturnMode(new_depth_return_mode);
327 return result;
328}
329
330inline void Frame::blockStackPush(TryBlock block) {
331 word depth_return_mode = blockStackDepthReturnMode();
332 word depth = depth_return_mode & kBlockStackDepthMask;
333 DCHECK(depth < kMaxBlockStackDepth * kPointerSize, "block stack overflow");
334 atPut(kBlockStackOffset + depth, block.asSmallInt());
335 setBlockStackDepthReturnMode(depth_return_mode + kPointerSize);
336}
337
338inline void Frame::addReturnMode(word mode) {
339 DCHECK(!isNative(), "Cannot set return mode on native frames");
340 word blockstack_depth_return_mode = blockStackDepthReturnMode();
341 setBlockStackDepthReturnMode(blockstack_depth_return_mode |
342 (mode << kReturnModeOffset));
343}
344
345inline word Frame::returnMode() {
346 return static_cast<ReturnMode>(blockStackDepthReturnMode() >>
347 kReturnModeOffset);
348}
349
350inline RawFunction Frame::function() {
351 DCHECK(previousFrame() != nullptr, "must not be called on initial frame");
352 return RawFunction::cast(*(locals() + kFunctionOffsetFromLocals));
353}
354
355inline word Frame::virtualPC() {
356 return RawSmallInt::cast(at(kVirtualPCOffset)).asReinterpretedWord();
357}
358
359inline void Frame::setVirtualPC(word pc) {
360 // We re-interpret the PC value as a small int. This works because it must
361 // be an even number and naturally has the lowest bit cleared.
362 atPut(kVirtualPCOffset, RawSmallInt::fromReinterpretedWord(pc));
363}
364
365inline word Frame::localsOffset() {
366 return RawSmallInt::cast(at(kLocalsOffsetOffset)).asReinterpretedWord();
367}
368
369inline void Frame::setLocalsOffset(word locals_offset) {
370 atPut(kLocalsOffsetOffset, RawSmallInt::fromReinterpretedWord(locals_offset));
371}
372
373inline word Frame::currentPC() {
374 return RawSmallInt::cast(at(kVirtualPCOffset)).asReinterpretedWord() -
375 kCodeUnitSize;
376}
377
378inline RawObject Frame::implicitGlobals() {
379 DCHECK(previousFrame() != nullptr, "must not be called on initial frame");
380 DCHECK(!function().hasOptimizedOrNewlocals(),
381 "implicit globals not available");
382 // Thread::exec() and Thread::runClassFunction() place implicit globals there.
383 return *(locals() + kImplicitGlobalsOffsetFromLocals);
384}
385
386inline RawObject Frame::code() { return function().code(); }
387
388inline RawObject* Frame::locals() {
389 return reinterpret_cast<RawObject*>(reinterpret_cast<char*>(this) +
390 localsOffset());
391}
392
393inline RawObject Frame::local(word idx) {
394 DCHECK_INDEX(idx, function().totalLocals());
395 return *(locals() - idx - 1);
396}
397
398inline RawObject Frame::localWithReverseIndex(word reverse_idx) {
399 DCHECK_INDEX(reverse_idx, function().totalLocals());
400 RawObject* locals_end = reinterpret_cast<RawObject*>(address() + kSize);
401 return locals_end[reverse_idx];
402}
403
404inline void Frame::setLocal(word idx, RawObject value) {
405 DCHECK_INDEX(idx, function().totalLocals());
406 *(locals() - idx - 1) = value;
407}
408
409inline void Frame::setLocalWithReverseIndex(word reverse_idx, RawObject value) {
410 DCHECK_INDEX(reverse_idx, function().totalLocals());
411 RawObject* locals_end = reinterpret_cast<RawObject*>(address() + kSize);
412 locals_end[reverse_idx] = value;
413}
414
415inline RawObject Frame::caches() { return at(kCachesOffset); }
416
417inline void Frame::setCaches(RawObject caches) { atPut(kCachesOffset, caches); }
418
419inline RawMutableBytes Frame::bytecode() {
420 return RawMutableBytes::cast(at(kBytecodeOffset));
421}
422
423inline void Frame::setBytecode(RawMutableBytes bytecode) {
424 atPut(kBytecodeOffset, bytecode);
425}
426
427inline Frame* Frame::previousFrame() {
428 RawObject frame = at(kPreviousFrameOffset);
429 return static_cast<Frame*>(RawSmallInt::cast(frame).asAlignedCPtr());
430}
431
432inline void Frame::setPreviousFrame(Frame* frame) {
433 atPut(kPreviousFrameOffset,
434 RawSmallInt::fromAlignedCPtr(reinterpret_cast<void*>(frame)));
435}
436
437inline bool Frame::isSentinel() {
438 // This is the same as `previousFrame() == nullptr` but will not fail
439 // assertion checks if the field is not a SmallInt.
440 return at(kPreviousFrameOffset) == RawSmallInt::fromWord(0);
441}
442
443inline RawObject* Frame::stashedValueStackTop() {
444 word depth = RawSmallInt::cast(at(kPreviousFrameOffset)).value();
445 return reinterpret_cast<RawObject*>(this) - depth;
446}
447
448inline RawObject Frame::stashedPopValue() {
449 RawObject result = *stashedValueStackTop();
450 // valueStackTop() contains the stack depth as a RawSmallInt rather than a
451 // pointer, so decrement it by 1.
452 word depth = RawSmallInt::cast(at(kPreviousFrameOffset)).value();
453 atPut(kPreviousFrameOffset, RawSmallInt::fromWord(depth - 1));
454 return result;
455}
456
457inline void Frame::stashStackSize(word size) {
458 atPut(kPreviousFrameOffset, RawSmallInt::fromWord(size));
459}
460
461inline RawObject TryBlock::asSmallInt() const {
462 RawObject obj{value_};
463 DCHECK(obj.isSmallInt(), "expected small integer");
464 return obj;
465}
466
467inline TryBlock::Kind TryBlock::kind() const {
468 return static_cast<Kind>((value_ >> kKindOffset) & kKindMask);
469}
470
471inline word TryBlock::handler() const {
472 return (value_ >> kHandlerOffset) & kHandlerMask;
473}
474
475inline word TryBlock::level() const {
476 return (value_ >> kLevelOffset) & kLevelMask;
477}
478
479} // namespace py