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 * This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #ifndef vm_SavedStacks_h 8 #define vm_SavedStacks_h 9 10 #include "mozilla/Attributes.h" 11 #include "mozilla/FastBernoulliTrial.h" 12 #include "mozilla/Maybe.h" 13 14 #include "js/HashTable.h" 15 #include "js/Wrapper.h" 16 #include "vm/JSContext.h" 17 #include "vm/SavedFrame.h" 18 #include "vm/Stack.h" 19 20 namespace JS { 21 enum class SavedFrameSelfHosted; 22 } 23 24 namespace js { 25 26 // # Saved Stacks 27 // 28 // The `SavedStacks` class provides a compact way to capture and save JS stacks 29 // as `SavedFrame` `JSObject` subclasses. A single `SavedFrame` object 30 // represents one frame that was on the stack, and has a strong reference to its 31 // parent `SavedFrame` (the next youngest frame). This reference is null when 32 // the `SavedFrame` object is the oldest frame that was on the stack. 33 // 34 // This comment documents implementation. For usage documentation, see the 35 // `js/src/doc/SavedFrame/SavedFrame.md` file and relevant `SavedFrame` 36 // functions in `js/src/jsapi.h`. 37 // 38 // ## Compact 39 // 40 // Older saved stack frame tails are shared via hash consing, to deduplicate 41 // structurally identical data. `SavedStacks` contains a hash table of weakly 42 // held `SavedFrame` objects, and when the owning compartment is swept, it 43 // removes entries from this table that aren't held alive in any other way. When 44 // saving new stacks, we use this table to find pre-existing `SavedFrame` 45 // objects. If such an object is already extant, it is reused; otherwise a new 46 // `SavedFrame` is allocated and inserted into the table. 47 // 48 // Naive | Hash Consing 49 // --------------+------------------ 50 // c -> b -> a | c -> b -> a 51 // | ^ 52 // d -> b -> a | d ---| 53 // | | 54 // e -> b -> a | e ---' 55 // 56 // This technique is effective because of the nature of the events that trigger 57 // capturing the stack. Currently, these events consist primarily of `JSObject` 58 // allocation (when an observing `Debugger` has such tracking), `Promise` 59 // settlement, and `Error` object creation. While these events may occur many 60 // times, they tend to occur only at a few locations in the JS source. For 61 // example, if we enable Object allocation tracking and run the esprima 62 // JavaScript parser on its own JavaScript source, there are approximately 54700 63 // total `Object` allocations, but just ~1400 unique JS stacks at allocation 64 // time. There's only ~200 allocation sites if we capture only the youngest 65 // stack frame. 66 // 67 // ## Security and Wrappers 68 // 69 // We save every frame on the stack, regardless of whether the `SavedStack`'s 70 // compartment's principals subsume the frame's compartment's principals or 71 // not. This gives us maximum flexibility down the line when accessing and 72 // presenting captured stacks, but at the price of some complication involved in 73 // preventing the leakage of privileged stack frames to unprivileged callers. 74 // 75 // When a `SavedFrame` method or accessor is called, we compare the caller's 76 // compartment's principals to each `SavedFrame`'s captured principals. We avoid 77 // using the usual `CallNonGenericMethod` and `nativeCall` machinery which 78 // enters the `SavedFrame` object's compartment before we can check these 79 // principals, because we need access to the original caller's compartment's 80 // principals (unlike other `CallNonGenericMethod` users) to determine what view 81 // of the stack to present. Instead, we take a similar approach to that used by 82 // DOM methods, and manually unwrap wrappers until we get the underlying 83 // `SavedFrame` object, find the first `SavedFrame` in its stack whose captured 84 // principals are subsumed by the caller's principals, access the reserved slots 85 // we care about, and then rewrap return values as necessary. 86 // 87 // Consider the following diagram: 88 // 89 // Content Compartment 90 // +---------------------------------------+ 91 // | | 92 // | +------------------------+ | 93 // Chrome Compartment | | | | 94 // +--------------------+ | | SavedFrame C (content) | | 95 // | | | | | | 96 // | +--------------+ +------------------------+ | 97 // | | | ^ | 98 // | var x -----> | Xray Wrapper |-----. | | 99 // | | | | | | 100 // | +--------------+ | +------------------------+ | 101 // | | | | | | | 102 // | +--------------+ | | SavedFrame B (content) | | 103 // | | | | | | | 104 // | var y -----> | CCW (waived) |--. | +------------------------+ | 105 // | | | | | ^ | 106 // | +--------------+ | | | | 107 // | | | | | | | 108 // +--------------------+ | | | +------------------------+ | 109 // | | '-> | | | 110 // | | | SavedFrame A (chrome) | | 111 // | '----> | | | 112 // | +------------------------+ | 113 // | ^ | 114 // | | | 115 // | var z -----' | 116 // | | 117 // +---------------------------------------+ 118 // 119 // CCW is a plain cross-compartment wrapper, yielded by waiving Xray vision. A 120 // is the youngest `SavedFrame` and represents a frame that was from the chrome 121 // compartment, while B and C are from frames from the content compartment. C is 122 // the oldest frame. 123 // 124 // Note that it is always safe to waive an Xray around a SavedFrame object, 125 // because SavedFrame objects and the SavedFrame prototype are always frozen you 126 // will never run untrusted code. 127 // 128 // Depending on who the caller is, the view of the stack will be different, and 129 // is summarized in the table below. 130 // 131 // Var | View 132 // -----+------------ 133 // x | A -> B -> C 134 // y, z | B -> C 135 // 136 // In the case of x, the `SavedFrame` accessors are called with an Xray wrapper 137 // around the `SavedFrame` object as the `this` value, and the chrome 138 // compartment as the cx's current principals. Because the chrome compartment's 139 // principals subsume both itself and the content compartment's principals, x 140 // has the complete view of the stack. 141 // 142 // In the case of y, the cross-compartment machinery automatically enters the 143 // content compartment, and calls the `SavedFrame` accessors with the wrapped 144 // `SavedFrame` object as the `this` value. Because the cx's current compartment 145 // is the content compartment, and the content compartment's principals do not 146 // subsume the chrome compartment's principals, it can only see the B and C 147 // frames. 148 // 149 // In the case of z, the `SavedFrame` accessors are called with the `SavedFrame` 150 // object in the `this` value, and the content compartment as the cx's current 151 // compartment. Similar to the case of y, only the B and C frames are exposed 152 // because the cx's current compartment's principals do not subsume A's captured 153 // principals. 154 155 class SavedStacks { 156 friend class SavedFrame; 157 friend bool JS::ubi::ConstructSavedFrameStackSlow( 158 JSContext* cx, JS::ubi::StackFrame& ubiFrame, 159 MutableHandleObject outSavedFrameStack); 160 161 public: SavedStacks()162 SavedStacks() 163 : frames(), 164 bernoulliSeeded(false), 165 bernoulli(1.0, 0x59fdad7f6b4cc573, 0x91adf38db96a9354), 166 creatingSavedFrame(false) {} 167 168 [[nodiscard]] bool saveCurrentStack( 169 JSContext* cx, MutableHandleSavedFrame frame, 170 JS::StackCapture&& capture = JS::StackCapture(JS::AllFrames())); 171 [[nodiscard]] bool copyAsyncStack( 172 JSContext* cx, HandleObject asyncStack, HandleString asyncCause, 173 MutableHandleSavedFrame adoptedStack, 174 const mozilla::Maybe<size_t>& maxFrameCount); 175 void traceWeak(JSTracer* trc); 176 void trace(JSTracer* trc); 177 uint32_t count(); 178 void clear(); 179 void chooseSamplingProbability(JS::Realm* realm); 180 181 // Set the sampling random number generator's state to |state0| and 182 // |state1|. One or the other must be non-zero. See the comments for 183 // mozilla::non_crypto::XorShift128PlusRNG::setState for details. setRNGState(uint64_t state0,uint64_t state1)184 void setRNGState(uint64_t state0, uint64_t state1) { 185 bernoulli.setRandomState(state0, state1); 186 } 187 188 size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf); 189 190 // An alloction metadata builder that marks cells with the JavaScript stack 191 // at which they were allocated. 192 struct MetadataBuilder : public AllocationMetadataBuilder { MetadataBuilderMetadataBuilder193 MetadataBuilder() : AllocationMetadataBuilder() {} 194 virtual JSObject* build(JSContext* cx, HandleObject obj, 195 AutoEnterOOMUnsafeRegion& oomUnsafe) const override; 196 }; 197 198 static const MetadataBuilder metadataBuilder; 199 200 private: 201 SavedFrame::Set frames; 202 bool bernoulliSeeded; 203 mozilla::FastBernoulliTrial bernoulli; 204 bool creatingSavedFrame; 205 206 // Similar to mozilla::ReentrancyGuard, but instead of asserting against 207 // reentrancy, just change the behavior of SavedStacks::saveCurrentStack to 208 // return a nullptr SavedFrame. 209 struct MOZ_RAII AutoReentrancyGuard { 210 SavedStacks& stacks; 211 AutoReentrancyGuardAutoReentrancyGuard212 explicit AutoReentrancyGuard(SavedStacks& stacks) : stacks(stacks) { 213 stacks.creatingSavedFrame = true; 214 } 215 ~AutoReentrancyGuardAutoReentrancyGuard216 ~AutoReentrancyGuard() { stacks.creatingSavedFrame = false; } 217 }; 218 219 [[nodiscard]] bool insertFrames(JSContext* cx, MutableHandleSavedFrame frame, 220 JS::StackCapture&& capture); 221 [[nodiscard]] bool adoptAsyncStack( 222 JSContext* cx, MutableHandleSavedFrame asyncStack, HandleAtom asyncCause, 223 const mozilla::Maybe<size_t>& maxFrameCount); 224 [[nodiscard]] bool checkForEvalInFramePrev( 225 JSContext* cx, MutableHandle<SavedFrame::Lookup> lookup); 226 SavedFrame* getOrCreateSavedFrame(JSContext* cx, 227 Handle<SavedFrame::Lookup> lookup); 228 SavedFrame* createFrameFromLookup(JSContext* cx, 229 Handle<SavedFrame::Lookup> lookup); 230 void setSamplingProbability(double probability); 231 232 // Cache for memoizing PCToLineNumber lookups. 233 234 struct PCKey { PCKeyPCKey235 PCKey(JSScript* script, jsbytecode* pc) : script(script), pc(pc) {} 236 237 HeapPtr<JSScript*> script; 238 jsbytecode* pc; 239 tracePCKey240 void trace(JSTracer* trc) { /* PCKey is weak. */ 241 } traceWeakPCKey242 bool traceWeak(JSTracer* trc) { 243 return TraceWeakEdge(trc, &script, "traceWeak"); 244 } 245 }; 246 247 public: 248 struct LocationValue { LocationValueLocationValue249 LocationValue() : source(nullptr), sourceId(0), line(0), column(0) {} LocationValueLocationValue250 LocationValue(JSAtom* source, uint32_t sourceId, size_t line, 251 uint32_t column) 252 : source(source), sourceId(sourceId), line(line), column(column) {} 253 traceLocationValue254 void trace(JSTracer* trc) { 255 TraceNullableEdge(trc, &source, "SavedStacks::LocationValue::source"); 256 } 257 traceWeakLocationValue258 bool traceWeak(JSTracer* trc) { 259 MOZ_ASSERT(source); 260 // TODO: Bug 1501334: IsAboutToBeFinalized doesn't work for atoms. 261 // Otherwise we should assert TraceWeakEdge always returns true; 262 return TraceWeakEdge(trc, &source, "traceWeak"); 263 } 264 265 HeapPtr<JSAtom*> source; 266 uint32_t sourceId; 267 size_t line; 268 uint32_t column; 269 }; 270 271 private: 272 struct PCLocationHasher : public DefaultHasher<PCKey> { 273 using ScriptPtrHasher = DefaultHasher<JSScript*>; 274 using BytecodePtrHasher = DefaultHasher<jsbytecode*>; 275 hashPCLocationHasher276 static HashNumber hash(const PCKey& key) { 277 return mozilla::AddToHash(ScriptPtrHasher::hash(key.script), 278 BytecodePtrHasher::hash(key.pc)); 279 } 280 matchPCLocationHasher281 static bool match(const PCKey& l, const PCKey& k) { 282 return ScriptPtrHasher::match(l.script, k.script) && 283 BytecodePtrHasher::match(l.pc, k.pc); 284 } 285 }; 286 287 // We eagerly Atomize the script source stored in LocationValue because 288 // wasm does not always have a JSScript and the source might not be 289 // available when we need it later. However, since the JSScript does not 290 // actually hold this atom, we have to trace it strongly to keep it alive. 291 // Thus, it takes two GC passes to fully clean up this table: the first GC 292 // removes the dead script; the second will clear out the source atom since 293 // it is no longer held by the table. 294 using PCLocationMap = 295 GCHashMap<PCKey, LocationValue, PCLocationHasher, SystemAllocPolicy>; 296 PCLocationMap pcLocationMap; 297 298 [[nodiscard]] bool getLocation(JSContext* cx, const FrameIter& iter, 299 MutableHandle<LocationValue> locationp); 300 }; 301 302 template <typename Wrapper> 303 struct WrappedPtrOperations<SavedStacks::LocationValue, Wrapper> { 304 JSAtom* source() const { return loc().source; } 305 uint32_t sourceId() const { return loc().sourceId; } 306 size_t line() const { return loc().line; } 307 uint32_t column() const { return loc().column; } 308 309 private: 310 const SavedStacks::LocationValue& loc() const { 311 return static_cast<const Wrapper*>(this)->get(); 312 } 313 }; 314 315 template <typename Wrapper> 316 struct MutableWrappedPtrOperations<SavedStacks::LocationValue, Wrapper> 317 : public WrappedPtrOperations<SavedStacks::LocationValue, Wrapper> { 318 void setSource(JSAtom* v) { loc().source = v; } 319 void setSourceId(uint32_t v) { loc().sourceId = v; } 320 void setLine(size_t v) { loc().line = v; } 321 void setColumn(uint32_t v) { loc().column = v; } 322 323 private: 324 SavedStacks::LocationValue& loc() { 325 return static_cast<Wrapper*>(this)->get(); 326 } 327 }; 328 329 JS::UniqueChars BuildUTF8StackString(JSContext* cx, JSPrincipals* principals, 330 HandleObject stack); 331 332 uint32_t FixupColumnForDisplay(uint32_t column); 333 334 js::SavedFrame* UnwrapSavedFrame(JSContext* cx, JSPrincipals* principals, 335 HandleObject obj, 336 JS::SavedFrameSelfHosted selfHosted, 337 bool& skippedAsync); 338 339 } /* namespace js */ 340 341 #endif /* vm_SavedStacks_h */ 342