summaryrefslogtreecommitdiff
path: root/js/src/vm/SavedStacks.h
blob: 3ea6c408741592cbbade696b73be166b59e9e619 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef vm_SavedStacks_h
#define vm_SavedStacks_h

#include "mozilla/Attributes.h"
#include "mozilla/FastBernoulliTrial.h"

#include "jscntxt.h"
#include "jsmath.h"
#include "jswrapper.h"
#include "js/HashTable.h"
#include "vm/SavedFrame.h"
#include "vm/Stack.h"

namespace js {

// # Saved Stacks
//
// The `SavedStacks` class provides a compact way to capture and save JS stacks
// as `SavedFrame` `JSObject` subclasses. A single `SavedFrame` object
// represents one frame that was on the stack, and has a strong reference to its
// parent `SavedFrame` (the next youngest frame). This reference is null when
// the `SavedFrame` object is the oldest frame that was on the stack.
//
// This comment documents implementation. For usage documentation, see the
// `js/src/doc/SavedFrame/SavedFrame.md` file and relevant `SavedFrame`
// functions in `js/src/jsapi.h`.
//
// ## Compact
//
// Older saved stack frame tails are shared via hash consing, to deduplicate
// structurally identical data. `SavedStacks` contains a hash table of weakly
// held `SavedFrame` objects, and when the owning compartment is swept, it
// removes entries from this table that aren't held alive in any other way. When
// saving new stacks, we use this table to find pre-existing `SavedFrame`
// objects. If such an object is already extant, it is reused; otherwise a new
// `SavedFrame` is allocated and inserted into the table.
//
//    Naive         |   Hash Consing
//    --------------+------------------
//    c -> b -> a   |   c -> b -> a
//                  |        ^
//    d -> b -> a   |   d ---|
//                  |        |
//    e -> b -> a   |   e ---'
//
// This technique is effective because of the nature of the events that trigger
// capturing the stack. Currently, these events consist primarily of `JSObject`
// allocation (when an observing `Debugger` has such tracking), `Promise`
// settlement, and `Error` object creation. While these events may occur many
// times, they tend to occur only at a few locations in the JS source. For
// example, if we enable Object allocation tracking and run the esprima
// JavaScript parser on its own JavaScript source, there are approximately 54700
// total `Object` allocations, but just ~1400 unique JS stacks at allocation
// time. There's only ~200 allocation sites if we capture only the youngest
// stack frame.
//
// ## Security and Wrappers
//
// We save every frame on the stack, regardless of whether the `SavedStack`'s
// compartment's principals subsume the frame's compartment's principals or
// not. This gives us maximum flexibility down the line when accessing and
// presenting captured stacks, but at the price of some complication involved in
// preventing the leakage of privileged stack frames to unprivileged callers.
//
// When a `SavedFrame` method or accessor is called, we compare the caller's
// compartment's principals to each `SavedFrame`'s captured principals. We avoid
// using the usual `CallNonGenericMethod` and `nativeCall` machinery which
// enters the `SavedFrame` object's compartment before we can check these
// principals, because we need access to the original caller's compartment's
// principals (unlike other `CallNonGenericMethod` users) to determine what view
// of the stack to present. Instead, we take a similar approach to that used by
// DOM methods, and manually unwrap wrappers until we get the underlying
// `SavedFrame` object, find the first `SavedFrame` in its stack whose captured
// principals are subsumed by the caller's principals, access the reserved slots
// we care about, and then rewrap return values as necessary.
//
// Consider the following diagram:
//
//                                              Content Compartment
//                                    +---------------------------------------+
//                                    |                                       |
//                                    |           +------------------------+  |
//      Chrome Compartment            |           |                        |  |
//    +--------------------+          |           | SavedFrame C (content) |  |
//    |                    |          |           |                        |  |
//    |                  +--------------+         +------------------------+  |
//    |                  |              |                    ^                |
//    |     var x -----> | Xray Wrapper |-----.              |                |
//    |                  |              |     |              |                |
//    |                  +--------------+     |   +------------------------+  |
//    |                    |          |       |   |                        |  |
//    |                  +--------------+     |   | SavedFrame B (content) |  |
//    |                  |              |     |   |                        |  |
//    |     var y -----> | CCW (waived) |--.  |   +------------------------+  |
//    |                  |              |  |  |              ^                |
//    |                  +--------------+  |  |              |                |
//    |                    |          |    |  |              |                |
//    +--------------------+          |    |  |   +------------------------+  |
//                                    |    |  '-> |                        |  |
//                                    |    |      | SavedFrame A (chrome)  |  |
//                                    |    '----> |                        |  |
//                                    |           +------------------------+  |
//                                    |                      ^                |
//                                    |                      |                |
//                                    |           var z -----'                |
//                                    |                                       |
//                                    +---------------------------------------+
//
// CCW is a plain cross-compartment wrapper, yielded by waiving Xray vision. A
// is the youngest `SavedFrame` and represents a frame that was from the chrome
// compartment, while B and C are from frames from the content compartment. C is
// the oldest frame.
//
// Note that it is always safe to waive an Xray around a SavedFrame object,
// because SavedFrame objects and the SavedFrame prototype are always frozen you
// will never run untrusted code.
//
// Depending on who the caller is, the view of the stack will be different, and
// is summarized in the table below.
//
//    Var  | View
//    -----+------------
//    x    | A -> B -> C
//    y, z | B -> C
//
// In the case of x, the `SavedFrame` accessors are called with an Xray wrapper
// around the `SavedFrame` object as the `this` value, and the chrome
// compartment as the cx's current principals. Because the chrome compartment's
// principals subsume both itself and the content compartment's principals, x
// has the complete view of the stack.
//
// In the case of y, the cross-compartment machinery automatically enters the
// content compartment, and calls the `SavedFrame` accessors with the wrapped
// `SavedFrame` object as the `this` value. Because the cx's current compartment
// is the content compartment, and the content compartment's principals do not
// subsume the chrome compartment's principals, it can only see the B and C
// frames.
//
// In the case of z, the `SavedFrame` accessors are called with the `SavedFrame`
// object in the `this` value, and the content compartment as the cx's current
// compartment. Similar to the case of y, only the B and C frames are exposed
// because the cx's current compartment's principals do not subsume A's captured
// principals.

class SavedStacks {
    friend class SavedFrame;
    friend bool JS::ubi::ConstructSavedFrameStackSlow(JSContext* cx,
                                                      JS::ubi::StackFrame& ubiFrame,
                                                      MutableHandleObject outSavedFrameStack);

  public:
    SavedStacks()
      : frames(),
        bernoulliSeeded(false),
        bernoulli(1.0, 0x59fdad7f6b4cc573, 0x91adf38db96a9354),
        creatingSavedFrame(false)
    { }

    MOZ_MUST_USE bool init();
    bool initialized() const { return frames.initialized(); }
    MOZ_MUST_USE bool saveCurrentStack(JSContext* cx, MutableHandleSavedFrame frame,
                                       JS::StackCapture&& capture = JS::StackCapture(JS::AllFrames()));
    MOZ_MUST_USE bool copyAsyncStack(JSContext* cx, HandleObject asyncStack,
                                     HandleString asyncCause,
                                     MutableHandleSavedFrame adoptedStack,
                                     uint32_t maxFrameCount = 0);
    void sweep();
    void trace(JSTracer* trc);
    uint32_t count();
    void clear();
    void chooseSamplingProbability(JSCompartment*);

    // Set the sampling random number generator's state to |state0| and
    // |state1|. One or the other must be non-zero. See the comments for
    // mozilla::non_crypto::XorShift128PlusRNG::setState for details.
    void setRNGState(uint64_t state0, uint64_t state1) { bernoulli.setRandomState(state0, state1); }

    size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);

    // An alloction metadata builder that marks cells with the JavaScript stack
    // at which they were allocated.
    struct MetadataBuilder : public AllocationMetadataBuilder {
        MetadataBuilder() : AllocationMetadataBuilder() { }
        virtual JSObject* build(JSContext *cx, HandleObject obj,
                                AutoEnterOOMUnsafeRegion& oomUnsafe) const override;
    };

    static const MetadataBuilder metadataBuilder;

  private:
    SavedFrame::Set frames;
    bool bernoulliSeeded;
    mozilla::FastBernoulliTrial bernoulli;
    bool creatingSavedFrame;

    // Similar to mozilla::ReentrancyGuard, but instead of asserting against
    // reentrancy, just change the behavior of SavedStacks::saveCurrentStack to
    // return a nullptr SavedFrame.
    struct MOZ_RAII AutoReentrancyGuard {
        MOZ_DECL_USE_GUARD_OBJECT_NOTIFIER;
        SavedStacks& stacks;

        explicit AutoReentrancyGuard(SavedStacks& stacks MOZ_GUARD_OBJECT_NOTIFIER_PARAM)
            : stacks(stacks)
        {
            MOZ_GUARD_OBJECT_NOTIFIER_INIT;
            stacks.creatingSavedFrame = true;
        }

        ~AutoReentrancyGuard()
        {
            stacks.creatingSavedFrame = false;
        }
    };

    MOZ_MUST_USE bool insertFrames(JSContext* cx, FrameIter& iter,
                                   MutableHandleSavedFrame frame,
                                   JS::StackCapture&& capture);
    MOZ_MUST_USE bool adoptAsyncStack(JSContext* cx, HandleSavedFrame asyncStack,
                                      HandleString asyncCause,
                                      MutableHandleSavedFrame adoptedStack,
                                      uint32_t maxFrameCount);
    SavedFrame* getOrCreateSavedFrame(JSContext* cx, SavedFrame::HandleLookup lookup);
    SavedFrame* createFrameFromLookup(JSContext* cx, SavedFrame::HandleLookup lookup);

    // Cache for memoizing PCToLineNumber lookups.

    struct PCKey {
        PCKey(JSScript* script, jsbytecode* pc) : script(script), pc(pc) { }

        HeapPtr<JSScript*> script;
        jsbytecode* pc;

        void trace(JSTracer* trc) { /* PCKey is weak. */ }
        bool needsSweep() { return IsAboutToBeFinalized(&script); }
    };

  public:
    struct LocationValue {
        LocationValue() : source(nullptr), line(0), column(0) { }
        LocationValue(JSAtom* source, size_t line, uint32_t column)
            : source(source), line(line), column(column)
        { }

        void trace(JSTracer* trc) {
            TraceNullableEdge(trc, &source, "SavedStacks::LocationValue::source");
        }

        bool needsSweep() {
            // LocationValue is always held strongly, but in a weak map.
            // Assert that it has been marked already, but allow it to be
            // ejected from the map when the key dies.
            MOZ_ASSERT(source);
            MOZ_ASSERT(!IsAboutToBeFinalized(&source));
            return true;
        }

        HeapPtr<JSAtom*> source;
        size_t line;
        uint32_t column;
    };

  private:
    struct PCLocationHasher : public DefaultHasher<PCKey> {
        using ScriptPtrHasher = DefaultHasher<JSScript*>;
        using BytecodePtrHasher = DefaultHasher<jsbytecode*>;

        static HashNumber hash(const PCKey& key) {
            return mozilla::AddToHash(ScriptPtrHasher::hash(key.script),
                                      BytecodePtrHasher::hash(key.pc));
        }

        static bool match(const PCKey& l, const PCKey& k) {
            return ScriptPtrHasher::match(l.script, k.script) &&
                   BytecodePtrHasher::match(l.pc, k.pc);
        }
    };

    // We eagerly Atomize the script source stored in LocationValue because
    // wasm does not always have a JSScript and the source might not be
    // available when we need it later. However, since the JSScript does not
    // actually hold this atom, we have to trace it strongly to keep it alive.
    // Thus, it takes two GC passes to fully clean up this table: the first GC
    // removes the dead script; the second will clear out the source atom since
    // it is no longer held by the table.
    using PCLocationMap = GCHashMap<PCKey, LocationValue, PCLocationHasher, SystemAllocPolicy>;
    PCLocationMap pcLocationMap;

    MOZ_MUST_USE bool getLocation(JSContext* cx, const FrameIter& iter,
                                  MutableHandle<LocationValue> locationp);
};

template <typename Wrapper>
struct WrappedPtrOperations<SavedStacks::LocationValue, Wrapper>
{
    JSAtom* source() const { return loc().source; }
    size_t line() const { return loc().line; }
    uint32_t column() const { return loc().column; }

  private:
    const SavedStacks::LocationValue& loc() const {
        return static_cast<const Wrapper*>(this)->get();
    }
};

template <typename Wrapper>
struct MutableWrappedPtrOperations<SavedStacks::LocationValue, Wrapper>
    : public WrappedPtrOperations<SavedStacks::LocationValue, Wrapper>
{
    void setSource(JSAtom* v) { loc().source = v; }
    void setLine(size_t v) { loc().line = v; }
    void setColumn(uint32_t v) { loc().column = v; }

  private:
    SavedStacks::LocationValue& loc() {
        return static_cast<Wrapper*>(this)->get();
    }
};

UTF8CharsZ
BuildUTF8StackString(JSContext* cx, HandleObject stack);

} /* namespace js */

#endif /* vm_SavedStacks_h */