1/*
2 * Copyright (C) 2011-2018 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#pragma once
27
28#include <limits.h>
29#include <wtf/HashMap.h>
30#include <wtf/PrintStream.h>
31#include <wtf/StdLibExtras.h>
32#include <wtf/Vector.h>
33
34namespace JSC {
35
36class CodeBlock;
37struct DumpContext;
38struct InlineCallFrame;
39
40class CodeOrigin {
41public:
42 CodeOrigin()
43#if CPU(ADDRESS64)
44 : m_compositeValue(buildCompositeValue(nullptr, s_invalidBytecodeIndex))
45#else
46 : m_bytecodeIndex(s_invalidBytecodeIndex)
47 , m_inlineCallFrame(nullptr)
48#endif
49 {
50 }
51
52 CodeOrigin(WTF::HashTableDeletedValueType)
53#if CPU(ADDRESS64)
54 : m_compositeValue(buildCompositeValue(deletedMarker(), s_invalidBytecodeIndex))
55#else
56 : m_bytecodeIndex(s_invalidBytecodeIndex)
57 , m_inlineCallFrame(deletedMarker())
58#endif
59 {
60 }
61
62 explicit CodeOrigin(unsigned bytecodeIndex, InlineCallFrame* inlineCallFrame = nullptr)
63#if CPU(ADDRESS64)
64 : m_compositeValue(buildCompositeValue(inlineCallFrame, bytecodeIndex))
65#else
66 : m_bytecodeIndex(bytecodeIndex)
67 , m_inlineCallFrame(inlineCallFrame)
68#endif
69 {
70 ASSERT(bytecodeIndex < s_invalidBytecodeIndex);
71#if CPU(ADDRESS64)
72 ASSERT(!(bitwise_cast<uintptr_t>(inlineCallFrame) & ~s_maskCompositeValueForPointer));
73#endif
74 }
75
76#if CPU(ADDRESS64)
77 CodeOrigin& operator=(const CodeOrigin& other)
78 {
79 if (this != &other) {
80 if (UNLIKELY(isOutOfLine()))
81 delete outOfLineCodeOrigin();
82
83 if (UNLIKELY(other.isOutOfLine()))
84 m_compositeValue = buildCompositeValue(other.inlineCallFrame(), other.bytecodeIndex());
85 else
86 m_compositeValue = other.m_compositeValue;
87 }
88 return *this;
89 }
90 CodeOrigin& operator=(CodeOrigin&& other)
91 {
92 if (this != &other) {
93 if (UNLIKELY(isOutOfLine()))
94 delete outOfLineCodeOrigin();
95
96 m_compositeValue = std::exchange(other.m_compositeValue, 0);
97 }
98 return *this;
99 }
100
101 CodeOrigin(const CodeOrigin& other)
102 {
103 // We don't use the member initializer list because it would not let us optimize the common case where there is no out-of-line storage
104 // (in which case we don't have to extract the components of the composite value just to reassemble it).
105 if (UNLIKELY(other.isOutOfLine()))
106 m_compositeValue = buildCompositeValue(other.inlineCallFrame(), other.bytecodeIndex());
107 else
108 m_compositeValue = other.m_compositeValue;
109 }
110 CodeOrigin(CodeOrigin&& other)
111 : m_compositeValue(std::exchange(other.m_compositeValue, 0))
112 {
113 }
114
115 ~CodeOrigin()
116 {
117 if (UNLIKELY(isOutOfLine()))
118 delete outOfLineCodeOrigin();
119 }
120#endif
121
122 bool isSet() const
123 {
124#if CPU(ADDRESS64)
125 return !(m_compositeValue & s_maskIsBytecodeIndexInvalid);
126#else
127 return m_bytecodeIndex != s_invalidBytecodeIndex;
128#endif
129 }
130 explicit operator bool() const { return isSet(); }
131
132 bool isHashTableDeletedValue() const
133 {
134#if CPU(ADDRESS64)
135 return !isSet() && (m_compositeValue & s_maskCompositeValueForPointer);
136#else
137 return m_bytecodeIndex == s_invalidBytecodeIndex && !!m_inlineCallFrame;
138#endif
139 }
140
141 // The inline depth is the depth of the inline stack, so 1 = not inlined,
142 // 2 = inlined one deep, etc.
143 unsigned inlineDepth() const;
144
145 // If the code origin corresponds to inlined code, gives you the heap object that
146 // would have owned the code if it had not been inlined. Otherwise returns 0.
147 CodeBlock* codeOriginOwner() const;
148
149 int stackOffset() const;
150
151 unsigned hash() const;
152 bool operator==(const CodeOrigin& other) const;
153 bool operator!=(const CodeOrigin& other) const { return !(*this == other); }
154
155 // This checks if the two code origins correspond to the same stack trace snippets,
156 // but ignore whether the InlineCallFrame's are identical.
157 bool isApproximatelyEqualTo(const CodeOrigin& other, InlineCallFrame* terminal = nullptr) const;
158
159 unsigned approximateHash(InlineCallFrame* terminal = nullptr) const;
160
161 template <typename Function>
162 void walkUpInlineStack(const Function&);
163
164 // Get the inline stack. This is slow, and is intended for debugging only.
165 Vector<CodeOrigin> inlineStack() const;
166
167 JS_EXPORT_PRIVATE void dump(PrintStream&) const;
168 void dumpInContext(PrintStream&, DumpContext*) const;
169
170 unsigned bytecodeIndex() const
171 {
172#if CPU(ADDRESS64)
173 if (!isSet())
174 return s_invalidBytecodeIndex;
175 if (UNLIKELY(isOutOfLine()))
176 return outOfLineCodeOrigin()->bytecodeIndex;
177 return m_compositeValue >> (64 - s_freeBitsAtTop);
178#else
179 return m_bytecodeIndex;
180#endif
181 }
182
183 InlineCallFrame* inlineCallFrame() const
184 {
185#if CPU(ADDRESS64)
186 if (UNLIKELY(isOutOfLine()))
187 return outOfLineCodeOrigin()->inlineCallFrame;
188 return bitwise_cast<InlineCallFrame*>(m_compositeValue & s_maskCompositeValueForPointer);
189#else
190 return m_inlineCallFrame;
191#endif
192 }
193
194private:
195 static constexpr unsigned s_invalidBytecodeIndex = UINT_MAX;
196
197#if CPU(ADDRESS64)
198 static constexpr uintptr_t s_maskIsOutOfLine = 1;
199 static constexpr uintptr_t s_maskIsBytecodeIndexInvalid = 2;
200
201 struct OutOfLineCodeOrigin {
202 WTF_MAKE_FAST_ALLOCATED;
203 public:
204 InlineCallFrame* inlineCallFrame;
205 unsigned bytecodeIndex;
206
207 OutOfLineCodeOrigin(InlineCallFrame* inlineCallFrame, unsigned bytecodeIndex)
208 : inlineCallFrame(inlineCallFrame)
209 , bytecodeIndex(bytecodeIndex)
210 {
211 }
212 };
213
214 bool isOutOfLine() const
215 {
216 return m_compositeValue & s_maskIsOutOfLine;
217 }
218 OutOfLineCodeOrigin* outOfLineCodeOrigin() const
219 {
220 ASSERT(isOutOfLine());
221 return bitwise_cast<OutOfLineCodeOrigin*>(m_compositeValue & s_maskCompositeValueForPointer);
222 }
223#endif
224
225 static InlineCallFrame* deletedMarker()
226 {
227 auto value = static_cast<uintptr_t>(1 << 3);
228#if CPU(ADDRESS64)
229 ASSERT(value & s_maskCompositeValueForPointer);
230 ASSERT(!(value & ~s_maskCompositeValueForPointer));
231#endif
232 return bitwise_cast<InlineCallFrame*>(value);
233 }
234
235#if CPU(ADDRESS64)
236 static constexpr unsigned s_freeBitsAtTop = 64 - WTF_CPU_EFFECTIVE_ADDRESS_WIDTH;
237 static constexpr uintptr_t s_maskCompositeValueForPointer = ((1ULL << WTF_CPU_EFFECTIVE_ADDRESS_WIDTH) - 1) & ~(8ULL - 1);
238 static uintptr_t buildCompositeValue(InlineCallFrame* inlineCallFrame, unsigned bytecodeIndex)
239 {
240 if (bytecodeIndex == s_invalidBytecodeIndex)
241 return bitwise_cast<uintptr_t>(inlineCallFrame) | s_maskIsBytecodeIndexInvalid;
242
243 if (UNLIKELY(bytecodeIndex >= 1 << s_freeBitsAtTop)) {
244 auto* outOfLine = new OutOfLineCodeOrigin(inlineCallFrame, bytecodeIndex);
245 return bitwise_cast<uintptr_t>(outOfLine) | s_maskIsOutOfLine;
246 }
247
248 uintptr_t encodedBytecodeIndex = static_cast<uintptr_t>(bytecodeIndex) << (64 - s_freeBitsAtTop);
249 ASSERT(!(encodedBytecodeIndex & bitwise_cast<uintptr_t>(inlineCallFrame)));
250 return encodedBytecodeIndex | bitwise_cast<uintptr_t>(inlineCallFrame);
251 }
252
253 // The bottom bit indicates whether to look at an out-of-line implementation (because of a bytecode index which is too big for us to store).
254 // The next bit indicates whether this is an invalid bytecode (which depending on the InlineCallFrame* can either indicate an unset CodeOrigin,
255 // or a deletion marker for a hash table).
256 // The next bit is free
257 // The next 64-s_freeBitsAtTop-3 are the InlineCallFrame* or the OutOfLineCodeOrigin*
258 // Finally the last s_freeBitsAtTop are the bytecodeIndex if it is inline
259 uintptr_t m_compositeValue;
260#else
261 unsigned m_bytecodeIndex;
262 InlineCallFrame* m_inlineCallFrame;
263#endif
264};
265
266inline unsigned CodeOrigin::hash() const
267{
268 return WTF::IntHash<unsigned>::hash(bytecodeIndex()) +
269 WTF::PtrHash<InlineCallFrame*>::hash(inlineCallFrame());
270}
271
272inline bool CodeOrigin::operator==(const CodeOrigin& other) const
273{
274#if CPU(ADDRESS64)
275 if (m_compositeValue == other.m_compositeValue)
276 return true;
277#endif
278 return bytecodeIndex() == other.bytecodeIndex()
279 && inlineCallFrame() == other.inlineCallFrame();
280}
281
282struct CodeOriginHash {
283 static unsigned hash(const CodeOrigin& key) { return key.hash(); }
284 static bool equal(const CodeOrigin& a, const CodeOrigin& b) { return a == b; }
285 static const bool safeToCompareToEmptyOrDeleted = true;
286};
287
288struct CodeOriginApproximateHash {
289 static unsigned hash(const CodeOrigin& key) { return key.approximateHash(); }
290 static bool equal(const CodeOrigin& a, const CodeOrigin& b) { return a.isApproximatelyEqualTo(b); }
291 static const bool safeToCompareToEmptyOrDeleted = true;
292};
293
294} // namespace JSC
295
296namespace WTF {
297
298template<typename T> struct DefaultHash;
299template<> struct DefaultHash<JSC::CodeOrigin> {
300 typedef JSC::CodeOriginHash Hash;
301};
302
303template<typename T> struct HashTraits;
304template<> struct HashTraits<JSC::CodeOrigin> : SimpleClassHashTraits<JSC::CodeOrigin> {
305 static const bool emptyValueIsZero = false;
306};
307
308} // namespace WTF
309