1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 *
4 * Copyright 2019 Mozilla Foundation
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 #ifndef wasm_gc_h
20 #define wasm_gc_h
21
22 #include "mozilla/BinarySearch.h"
23
24 #include "jit/MacroAssembler.h" // For ABIArgIter
25 #include "js/AllocPolicy.h"
26 #include "js/Vector.h"
27 #include "util/Memory.h"
28
29 namespace js {
30
31 namespace jit {
32 class MacroAssembler;
33 } // namespace jit
34
35 namespace wasm {
36
37 using namespace js::jit;
38
39 // Definitions for stackmaps.
40
41 using ExitStubMapVector = Vector<bool, 32, SystemAllocPolicy>;
42
43 struct StackMap final {
44 // A StackMap is a bit-array containing numMappedWords bits, one bit per
45 // word of stack. Bit index zero is for the lowest addressed word in the
46 // range.
47 //
48 // This is a variable-length structure whose size must be known at creation
49 // time.
50 //
51 // Users of the map will know the address of the wasm::Frame that is covered
52 // by this map. In order that they can calculate the exact address range
53 // covered by the map, the map also stores the offset, from the highest
54 // addressed word of the map, of the embedded wasm::Frame. This is an
55 // offset down from the highest address, rather than up from the lowest, so
56 // as to limit its range to 11 bits, where
57 // 11 == ceil(log2(MaxParams * sizeof-biggest-param-type-in-words))
58 //
59 // The stackmap may also cover a DebugFrame (all DebugFrames get a map). If
60 // so that can be noted, since users of the map need to trace pointers in a
61 // DebugFrame.
62 //
63 // Finally, for sanity checking only, for stackmaps associated with a wasm
64 // trap exit stub, the number of words used by the trap exit stub save area
65 // is also noted. This is used in Instance::traceFrame to check that the
66 // TrapExitDummyValue is in the expected place in the frame.
67
68 // The total number of stack words covered by the map ..
69 uint32_t numMappedWords : 30;
70
71 // .. of which this many are "exit stub" extras
72 uint32_t numExitStubWords : 6;
73
74 // Where is Frame* relative to the top? This is an offset in words.
75 uint32_t frameOffsetFromTop : 11;
76
77 // Notes the presence of a DebugFrame. The DebugFrame may or may not contain
78 // GC-managed data but always gets a stackmap, as computing whether a stack
79 // map is definitively needed is brittle and ultimately not a worthwhile
80 // optimization.
81 uint32_t hasDebugFrame : 1;
82
83 private:
84 static constexpr uint32_t maxMappedWords = (1 << 30) - 1;
85 static constexpr uint32_t maxExitStubWords = (1 << 6) - 1;
86 static constexpr uint32_t maxFrameOffsetFromTop = (1 << 11) - 1;
87
88 uint32_t bitmap[1];
89
StackMapfinal90 explicit StackMap(uint32_t numMappedWords)
91 : numMappedWords(numMappedWords),
92 numExitStubWords(0),
93 frameOffsetFromTop(0),
94 hasDebugFrame(0) {
95 const uint32_t nBitmap = calcNBitmap(numMappedWords);
96 memset(bitmap, 0, nBitmap * sizeof(bitmap[0]));
97 }
98
99 public:
createfinal100 static StackMap* create(uint32_t numMappedWords) {
101 uint32_t nBitmap = calcNBitmap(numMappedWords);
102 char* buf =
103 (char*)js_malloc(sizeof(StackMap) + (nBitmap - 1) * sizeof(bitmap[0]));
104 if (!buf) {
105 return nullptr;
106 }
107 return ::new (buf) StackMap(numMappedWords);
108 }
109
destroyfinal110 void destroy() { js_free((char*)this); }
111
112 // Record the number of words in the map used as a wasm trap exit stub
113 // save area. See comment above.
setExitStubWordsfinal114 void setExitStubWords(uint32_t nWords) {
115 MOZ_ASSERT(numExitStubWords == 0);
116 MOZ_RELEASE_ASSERT(nWords <= maxExitStubWords);
117 MOZ_ASSERT(nWords <= numMappedWords);
118 numExitStubWords = nWords;
119 }
120
121 // Record the offset from the highest-addressed word of the map, that the
122 // wasm::Frame lives at. See comment above.
setFrameOffsetFromTopfinal123 void setFrameOffsetFromTop(uint32_t nWords) {
124 MOZ_ASSERT(frameOffsetFromTop == 0);
125 MOZ_RELEASE_ASSERT(nWords <= maxFrameOffsetFromTop);
126 MOZ_ASSERT(frameOffsetFromTop < numMappedWords);
127 frameOffsetFromTop = nWords;
128 }
129
130 // If the frame described by this StackMap includes a DebugFrame, call here to
131 // record that fact.
setHasDebugFramefinal132 void setHasDebugFrame() {
133 MOZ_ASSERT(hasDebugFrame == 0);
134 hasDebugFrame = 1;
135 }
136
setBitfinal137 inline void setBit(uint32_t bitIndex) {
138 MOZ_ASSERT(bitIndex < numMappedWords);
139 uint32_t wordIndex = bitIndex / wordsPerBitmapElem;
140 uint32_t wordOffset = bitIndex % wordsPerBitmapElem;
141 bitmap[wordIndex] |= (1 << wordOffset);
142 }
143
getBitfinal144 inline uint32_t getBit(uint32_t bitIndex) const {
145 MOZ_ASSERT(bitIndex < numMappedWords);
146 uint32_t wordIndex = bitIndex / wordsPerBitmapElem;
147 uint32_t wordOffset = bitIndex % wordsPerBitmapElem;
148 return (bitmap[wordIndex] >> wordOffset) & 1;
149 }
150
151 private:
152 static constexpr uint32_t wordsPerBitmapElem = sizeof(bitmap[0]) * 8;
153
calcNBitmapfinal154 static uint32_t calcNBitmap(uint32_t numMappedWords) {
155 MOZ_RELEASE_ASSERT(numMappedWords <= maxMappedWords);
156 uint32_t nBitmap =
157 (numMappedWords + wordsPerBitmapElem - 1) / wordsPerBitmapElem;
158 return nBitmap == 0 ? 1 : nBitmap;
159 }
160 };
161
162 // This is the expected size for a map that covers 32 or fewer words.
163 static_assert(sizeof(StackMap) == 12, "wasm::StackMap has unexpected size");
164
165 class StackMaps {
166 public:
167 // A Maplet holds a single code-address-to-map binding. Note that the
168 // code address is the lowest address of the instruction immediately
169 // following the instruction of interest, not of the instruction of
170 // interest itself. In practice (at least for the Wasm Baseline compiler)
171 // this means that |nextInsnAddr| points either immediately after a call
172 // instruction, after a trap instruction or after a no-op.
173 struct Maplet {
174 uint8_t* nextInsnAddr;
175 StackMap* map;
MapletMaplet176 Maplet(uint8_t* nextInsnAddr, StackMap* map)
177 : nextInsnAddr(nextInsnAddr), map(map) {}
offsetByMaplet178 void offsetBy(uintptr_t delta) { nextInsnAddr += delta; }
179 bool operator<(const Maplet& other) const {
180 return uintptr_t(nextInsnAddr) < uintptr_t(other.nextInsnAddr);
181 }
182 };
183
184 private:
185 bool sorted_;
186 Vector<Maplet, 0, SystemAllocPolicy> mapping_;
187
188 public:
StackMaps()189 StackMaps() : sorted_(false) {}
~StackMaps()190 ~StackMaps() {
191 for (auto& maplet : mapping_) {
192 maplet.map->destroy();
193 maplet.map = nullptr;
194 }
195 }
add(uint8_t * nextInsnAddr,StackMap * map)196 [[nodiscard]] bool add(uint8_t* nextInsnAddr, StackMap* map) {
197 MOZ_ASSERT(!sorted_);
198 return mapping_.append(Maplet(nextInsnAddr, map));
199 }
add(const Maplet & maplet)200 [[nodiscard]] bool add(const Maplet& maplet) {
201 return add(maplet.nextInsnAddr, maplet.map);
202 }
clear()203 void clear() {
204 for (auto& maplet : mapping_) {
205 maplet.nextInsnAddr = nullptr;
206 maplet.map = nullptr;
207 }
208 mapping_.clear();
209 }
empty()210 bool empty() const { return mapping_.empty(); }
length()211 size_t length() const { return mapping_.length(); }
getRef(size_t i)212 Maplet* getRef(size_t i) { return &mapping_[i]; }
get(size_t i)213 Maplet get(size_t i) const { return mapping_[i]; }
move(size_t i)214 Maplet move(size_t i) {
215 Maplet m = mapping_[i];
216 mapping_[i].map = nullptr;
217 return m;
218 }
offsetBy(uintptr_t delta)219 void offsetBy(uintptr_t delta) {
220 for (auto& maplet : mapping_) maplet.offsetBy(delta);
221 }
sort()222 void sort() {
223 MOZ_ASSERT(!sorted_);
224 std::sort(mapping_.begin(), mapping_.end());
225 sorted_ = true;
226 }
findMap(uint8_t * nextInsnAddr)227 const StackMap* findMap(uint8_t* nextInsnAddr) const {
228 struct Comparator {
229 int operator()(Maplet aVal) const {
230 if (uintptr_t(mTarget) < uintptr_t(aVal.nextInsnAddr)) {
231 return -1;
232 }
233 if (uintptr_t(mTarget) > uintptr_t(aVal.nextInsnAddr)) {
234 return 1;
235 }
236 return 0;
237 }
238 explicit Comparator(const uint8_t* aTarget) : mTarget(aTarget) {}
239 const uint8_t* mTarget;
240 };
241
242 size_t result;
243 if (mozilla::BinarySearchIf(mapping_, 0, mapping_.length(),
244 Comparator(nextInsnAddr), &result)) {
245 return mapping_[result].map;
246 }
247
248 return nullptr;
249 }
250 };
251
252 // Supporting code for creation of stackmaps.
253
254 // StackArgAreaSizeUnaligned returns the size, in bytes, of the stack arg area
255 // size needed to pass |argTypes|, excluding any alignment padding beyond the
256 // size of the area as a whole. The size is as determined by the platforms
257 // native ABI.
258 //
259 // StackArgAreaSizeAligned returns the same, but rounded up to the nearest 16
260 // byte boundary.
261 //
262 // Note, StackArgAreaSize{Unaligned,Aligned}() must process all the arguments
263 // in order to take into account all necessary alignment constraints. The
264 // signature must include any receiver argument -- in other words, it must be
265 // the complete native-ABI-level call signature.
266 template <class T>
StackArgAreaSizeUnaligned(const T & argTypes)267 static inline size_t StackArgAreaSizeUnaligned(const T& argTypes) {
268 WasmABIArgIter<const T> i(argTypes);
269 while (!i.done()) {
270 i++;
271 }
272 return i.stackBytesConsumedSoFar();
273 }
274
StackArgAreaSizeUnaligned(const SymbolicAddressSignature & saSig)275 static inline size_t StackArgAreaSizeUnaligned(
276 const SymbolicAddressSignature& saSig) {
277 // WasmABIArgIter::ABIArgIter wants the items to be iterated over to be
278 // presented in some type that has methods length() and operator[]. So we
279 // have to wrap up |saSig|'s array of types in this API-matching class.
280 class MOZ_STACK_CLASS ItemsAndLength {
281 const MIRType* items_;
282 size_t length_;
283
284 public:
285 ItemsAndLength(const MIRType* items, size_t length)
286 : items_(items), length_(length) {}
287 size_t length() const { return length_; }
288 MIRType operator[](size_t i) const { return items_[i]; }
289 };
290
291 // Assert, at least crudely, that we're not accidentally going to run off
292 // the end of the array of types, nor into undefined parts of it, while
293 // iterating.
294 MOZ_ASSERT(saSig.numArgs <
295 sizeof(saSig.argTypes) / sizeof(saSig.argTypes[0]));
296 MOZ_ASSERT(saSig.argTypes[saSig.numArgs] == MIRType::None /*the end marker*/);
297
298 ItemsAndLength itemsAndLength(saSig.argTypes, saSig.numArgs);
299 return StackArgAreaSizeUnaligned(itemsAndLength);
300 }
301
AlignStackArgAreaSize(size_t unalignedSize)302 static inline size_t AlignStackArgAreaSize(size_t unalignedSize) {
303 return AlignBytes(unalignedSize, 16u);
304 }
305
306 template <class T>
StackArgAreaSizeAligned(const T & argTypes)307 static inline size_t StackArgAreaSizeAligned(const T& argTypes) {
308 return AlignStackArgAreaSize(StackArgAreaSizeUnaligned(argTypes));
309 }
310
311 // A stackmap creation helper. Create a stackmap from a vector of booleans.
312 // The caller owns the resulting stackmap.
313
314 using StackMapBoolVector = Vector<bool, 128, SystemAllocPolicy>;
315
316 wasm::StackMap* ConvertStackMapBoolVectorToStackMap(
317 const StackMapBoolVector& vec, bool hasRefs);
318
319 // Generate a stackmap for a function's stack-overflow-at-entry trap, with
320 // the structure:
321 //
322 // <reg dump area>
323 // | ++ <space reserved before trap, if any>
324 // | ++ <space for Frame>
325 // | ++ <inbound arg area>
326 // | |
327 // Lowest Addr Highest Addr
328 //
329 // The caller owns the resulting stackmap. This assumes a grow-down stack.
330 //
331 // For non-debug builds, if the stackmap would contain no pointers, no
332 // stackmap is created, and nullptr is returned. For a debug build, a
333 // stackmap is always created and returned.
334 //
335 // The "space reserved before trap" is the space reserved by
336 // MacroAssembler::wasmReserveStackChecked, in the case where the frame is
337 // "small", as determined by that function.
338 [[nodiscard]] bool CreateStackMapForFunctionEntryTrap(
339 const ArgTypeVector& argTypes, const MachineState& trapExitLayout,
340 size_t trapExitLayoutWords, size_t nBytesReservedBeforeTrap,
341 size_t nInboundStackArgBytes, wasm::StackMap** result);
342
343 // At a resumable wasm trap, the machine's registers are saved on the stack by
344 // (code generated by) GenerateTrapExit(). This function writes into |args| a
345 // vector of booleans describing the ref-ness of the saved integer registers.
346 // |args[0]| corresponds to the low addressed end of the described section of
347 // the save area.
348 [[nodiscard]] bool GenerateStackmapEntriesForTrapExit(
349 const ArgTypeVector& args, const MachineState& trapExitLayout,
350 const size_t trapExitLayoutNumWords, ExitStubMapVector* extras);
351
352 // Shared write barrier code.
353 //
354 // A barriered store looks like this:
355 //
356 // Label skipPreBarrier;
357 // EmitWasmPreBarrierGuard(..., &skipPreBarrier);
358 // <COMPILER-SPECIFIC ACTIONS HERE>
359 // EmitWasmPreBarrierCall(...);
360 // bind(&skipPreBarrier);
361 //
362 // <STORE THE VALUE IN MEMORY HERE>
363 //
364 // Label skipPostBarrier;
365 // <COMPILER-SPECIFIC ACTIONS HERE>
366 // EmitWasmPostBarrierGuard(..., &skipPostBarrier);
367 // <CALL POST-BARRIER HERE IN A COMPILER-SPECIFIC WAY>
368 // bind(&skipPostBarrier);
369 //
370 // The actions are divided up to allow other actions to be placed between them,
371 // such as saving and restoring live registers. The postbarrier call invokes
372 // C++ and will kill all live registers.
373
374 // Before storing a GC pointer value in memory, skip to `skipBarrier` if the
375 // prebarrier is not needed. Will clobber `scratch`.
376 //
377 // It is OK for `tls` and `scratch` to be the same register.
378
379 void EmitWasmPreBarrierGuard(MacroAssembler& masm, Register tls,
380 Register scratch, Register valueAddr,
381 Label* skipBarrier);
382
383 // Before storing a GC pointer value in memory, call out-of-line prebarrier
384 // code. This assumes `PreBarrierReg` contains the address that will be updated.
385 // On ARM64 it also assums that x28 (the PseudoStackPointer) has the same value
386 // as SP. `PreBarrierReg` is preserved by the barrier function. Will clobber
387 // `scratch`.
388 //
389 // It is OK for `tls` and `scratch` to be the same register.
390
391 void EmitWasmPreBarrierCall(MacroAssembler& masm, Register tls,
392 Register scratch, Register valueAddr);
393
394 // After storing a GC pointer value in memory, skip to `skipBarrier` if a
395 // postbarrier is not needed. If the location being set is in an heap-allocated
396 // object then `object` must reference that object; otherwise it should be None.
397 // The value that was stored is `setValue`. Will clobber `otherScratch` and
398 // will use other available scratch registers.
399 //
400 // `otherScratch` cannot be a designated scratch register.
401
402 void EmitWasmPostBarrierGuard(MacroAssembler& masm,
403 const Maybe<Register>& object,
404 Register otherScratch, Register setValue,
405 Label* skipBarrier);
406
407 #ifdef DEBUG
408 // Check whether |nextPC| is a valid code address for a stackmap created by
409 // this compiler.
410 bool IsValidStackMapKey(bool debugEnabled, const uint8_t* nextPC);
411 #endif
412
413 } // namespace wasm
414 } // namespace js
415
416 #endif // wasm_gc_h
417