1/*
2 * Copyright (C) 2016-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#include "config.h"
27#include "PCToCodeOriginMap.h"
28
29#if ENABLE(JIT)
30
31#include "B3PCToOriginMap.h"
32#include "DFGNode.h"
33#include "LinkBuffer.h"
34#include <wtf/Optional.h>
35
36#if COMPILER(MSVC)
37// See https://msdn.microsoft.com/en-us/library/4wz07268.aspx
38#pragma warning(disable: 4333)
39#endif
40
41namespace JSC {
42
43namespace {
44
45class DeltaCompressionBuilder {
46public:
47 DeltaCompressionBuilder(size_t maxSize)
48 : m_offset(0)
49 , m_maxSize(maxSize)
50 {
51 m_buffer = static_cast<uint8_t*>(fastMalloc(m_maxSize));
52 }
53
54 template <typename T>
55 void write(T item)
56 {
57 RELEASE_ASSERT(m_offset + sizeof(T) <= m_maxSize);
58 static constexpr uint8_t mask = std::numeric_limits<uint8_t>::max();
59 for (unsigned i = 0; i < sizeof(T); i++) {
60 *(m_buffer + m_offset) = static_cast<uint8_t>(item & mask);
61 item = item >> (sizeof(uint8_t) * 8);
62 m_offset += 1;
63 }
64 }
65
66 uint8_t* m_buffer;
67 size_t m_offset;
68 size_t m_maxSize;
69};
70
71class DeltaCompresseionReader {
72public:
73 DeltaCompresseionReader(uint8_t* buffer, size_t size)
74 : m_buffer(buffer)
75 , m_size(size)
76 , m_offset(0)
77 { }
78
79 template <typename T>
80 T read()
81 {
82 RELEASE_ASSERT(m_offset + sizeof(T) <= m_size);
83 T result = 0;
84 for (unsigned i = 0; i < sizeof(T); i++) {
85 uint8_t bitsAsInt8 = *(m_buffer + m_offset);
86 T bits = static_cast<T>(bitsAsInt8);
87 bits = bits << (sizeof(uint8_t) * 8 * i);
88 result |= bits;
89 m_offset += 1;
90 }
91 return result;
92 }
93
94private:
95 uint8_t* m_buffer;
96 size_t m_size;
97 size_t m_offset;
98};
99
100} // anonymous namespace
101
102PCToCodeOriginMapBuilder::PCToCodeOriginMapBuilder(VM& vm)
103 : m_vm(vm)
104 , m_shouldBuildMapping(vm.shouldBuilderPCToCodeOriginMapping())
105{ }
106
107PCToCodeOriginMapBuilder::PCToCodeOriginMapBuilder(PCToCodeOriginMapBuilder&& other)
108 : m_vm(other.m_vm)
109 , m_codeRanges(WTFMove(other.m_codeRanges))
110 , m_shouldBuildMapping(other.m_shouldBuildMapping)
111{ }
112
113#if ENABLE(FTL_JIT)
114PCToCodeOriginMapBuilder::PCToCodeOriginMapBuilder(VM& vm, B3::PCToOriginMap&& b3PCToOriginMap)
115 : m_vm(vm)
116 , m_shouldBuildMapping(vm.shouldBuilderPCToCodeOriginMapping())
117{
118 if (!m_shouldBuildMapping)
119 return;
120
121 for (const B3::PCToOriginMap::OriginRange& originRange : b3PCToOriginMap.ranges()) {
122 DFG::Node* node = bitwise_cast<DFG::Node*>(originRange.origin.data());
123 if (node)
124 appendItem(originRange.label, node->origin.semantic);
125 else
126 appendItem(originRange.label, PCToCodeOriginMapBuilder::defaultCodeOrigin());
127 }
128}
129#endif
130
131void PCToCodeOriginMapBuilder::appendItem(MacroAssembler::Label label, const CodeOrigin& codeOrigin)
132{
133 if (!m_shouldBuildMapping)
134 return;
135
136 if (m_codeRanges.size()) {
137 if (m_codeRanges.last().end == label)
138 return;
139 m_codeRanges.last().end = label;
140 if (m_codeRanges.last().codeOrigin == codeOrigin || !codeOrigin)
141 return;
142 }
143
144 m_codeRanges.append(CodeRange{label, label, codeOrigin});
145}
146
147
148static constexpr uint8_t sentinelPCDelta = 0;
149static constexpr int8_t sentinelBytecodeDelta = 0;
150
151PCToCodeOriginMap::PCToCodeOriginMap(PCToCodeOriginMapBuilder&& builder, LinkBuffer& linkBuffer)
152{
153 RELEASE_ASSERT(builder.didBuildMapping());
154
155 if (!builder.m_codeRanges.size()) {
156 m_pcRangeStart = std::numeric_limits<uintptr_t>::max();
157 m_pcRangeEnd = std::numeric_limits<uintptr_t>::max();
158
159 m_compressedPCBufferSize = 0;
160 m_compressedPCs = nullptr;
161
162 m_compressedCodeOriginsSize = 0;
163 m_compressedCodeOrigins = nullptr;
164
165 return;
166 }
167
168 // We do a final touch-up on the last range here because of how we generate the table.
169 // The final range (if non empty) would be ignored if we didn't append any (arbitrary)
170 // range as the last item of the vector.
171 PCToCodeOriginMapBuilder::CodeRange& last = builder.m_codeRanges.last();
172 if (!(last.start == last.end))
173 builder.m_codeRanges.append(PCToCodeOriginMapBuilder::CodeRange{ last.end, last.end, last.codeOrigin }); // This range will never actually be found, but it ensures the real last range is found.
174
175 DeltaCompressionBuilder pcCompressor((sizeof(uintptr_t) + sizeof(uint8_t)) * builder.m_codeRanges.size());
176 void* lastPCValue = nullptr;
177 auto buildPCTable = [&] (void* pcValue) {
178 RELEASE_ASSERT(pcValue > lastPCValue);
179 uintptr_t delta = bitwise_cast<uintptr_t>(pcValue) - bitwise_cast<uintptr_t>(lastPCValue);
180 RELEASE_ASSERT(delta != sentinelPCDelta);
181 lastPCValue = pcValue;
182 if (delta > std::numeric_limits<uint8_t>::max()) {
183 pcCompressor.write<uint8_t>(sentinelPCDelta);
184 pcCompressor.write<uintptr_t>(delta);
185 return;
186 }
187
188 pcCompressor.write<uint8_t>(static_cast<uint8_t>(delta));
189 };
190
191 DeltaCompressionBuilder codeOriginCompressor((sizeof(intptr_t) + sizeof(int8_t) + sizeof(int8_t) + sizeof(InlineCallFrame*)) * builder.m_codeRanges.size());
192 CodeOrigin lastCodeOrigin(BytecodeIndex(0));
193 auto buildCodeOriginTable = [&] (const CodeOrigin& codeOrigin) {
194 intptr_t delta = static_cast<intptr_t>(codeOrigin.bytecodeIndex().offset()) - static_cast<intptr_t>(lastCodeOrigin.bytecodeIndex().offset());
195 lastCodeOrigin = codeOrigin;
196 if (delta > std::numeric_limits<int8_t>::max() || delta < std::numeric_limits<int8_t>::min() || delta == sentinelBytecodeDelta) {
197 codeOriginCompressor.write<int8_t>(sentinelBytecodeDelta);
198 codeOriginCompressor.write<intptr_t>(delta);
199 } else
200 codeOriginCompressor.write<int8_t>(static_cast<int8_t>(delta));
201
202 int8_t hasInlineCallFrameByte = codeOrigin.inlineCallFrame() ? 1 : 0;
203 codeOriginCompressor.write<int8_t>(hasInlineCallFrameByte);
204 if (hasInlineCallFrameByte)
205 codeOriginCompressor.write<uintptr_t>(bitwise_cast<uintptr_t>(codeOrigin.inlineCallFrame()));
206 };
207
208 m_pcRangeStart = linkBuffer.locationOf<NoPtrTag>(builder.m_codeRanges.first().start).dataLocation<uintptr_t>();
209 m_pcRangeEnd = linkBuffer.locationOf<NoPtrTag>(builder.m_codeRanges.last().end).dataLocation<uintptr_t>();
210 m_pcRangeEnd -= 1;
211
212 for (unsigned i = 0; i < builder.m_codeRanges.size(); i++) {
213 PCToCodeOriginMapBuilder::CodeRange& codeRange = builder.m_codeRanges[i];
214 void* start = linkBuffer.locationOf<NoPtrTag>(codeRange.start).dataLocation();
215 void* end = linkBuffer.locationOf<NoPtrTag>(codeRange.end).dataLocation();
216 ASSERT(m_pcRangeStart <= bitwise_cast<uintptr_t>(start));
217 ASSERT(m_pcRangeEnd >= bitwise_cast<uintptr_t>(end) - 1);
218 if (start == end)
219 ASSERT(i == builder.m_codeRanges.size() - 1);
220 if (i > 0)
221 ASSERT(linkBuffer.locationOf<NoPtrTag>(builder.m_codeRanges[i - 1].end).dataLocation() == start);
222
223 buildPCTable(start);
224 buildCodeOriginTable(codeRange.codeOrigin);
225 }
226
227 m_compressedPCBufferSize = pcCompressor.m_offset;
228 m_compressedPCs = static_cast<uint8_t*>(fastRealloc(pcCompressor.m_buffer, m_compressedPCBufferSize));
229
230 m_compressedCodeOriginsSize = codeOriginCompressor.m_offset;
231 m_compressedCodeOrigins = static_cast<uint8_t*>(fastRealloc(codeOriginCompressor.m_buffer, m_compressedCodeOriginsSize));
232}
233
234PCToCodeOriginMap::~PCToCodeOriginMap()
235{
236 if (m_compressedPCs)
237 fastFree(m_compressedPCs);
238 if (m_compressedCodeOrigins)
239 fastFree(m_compressedCodeOrigins);
240}
241
242double PCToCodeOriginMap::memorySize()
243{
244 double size = 0;
245 size += m_compressedPCBufferSize;
246 size += m_compressedCodeOriginsSize;
247 return size;
248}
249
250Optional<CodeOrigin> PCToCodeOriginMap::findPC(void* pc) const
251{
252 uintptr_t pcAsInt = bitwise_cast<uintptr_t>(pc);
253 if (!(m_pcRangeStart <= pcAsInt && pcAsInt <= m_pcRangeEnd))
254 return WTF::nullopt;
255
256 uintptr_t currentPC = 0;
257 BytecodeIndex currentBytecodeIndex = BytecodeIndex(0);
258 InlineCallFrame* currentInlineCallFrame = nullptr;
259
260 DeltaCompresseionReader pcReader(m_compressedPCs, m_compressedPCBufferSize);
261 DeltaCompresseionReader codeOriginReader(m_compressedCodeOrigins, m_compressedCodeOriginsSize);
262 while (true) {
263 uintptr_t previousPC = currentPC;
264 {
265 uint8_t value = pcReader.read<uint8_t>();
266 uintptr_t delta;
267 if (value == sentinelPCDelta)
268 delta = pcReader.read<uintptr_t>();
269 else
270 delta = value;
271 currentPC += delta;
272 }
273
274 CodeOrigin previousOrigin = CodeOrigin(currentBytecodeIndex, currentInlineCallFrame);
275 {
276 int8_t value = codeOriginReader.read<int8_t>();
277 intptr_t delta;
278 if (value == sentinelBytecodeDelta)
279 delta = codeOriginReader.read<intptr_t>();
280 else
281 delta = static_cast<intptr_t>(value);
282
283 currentBytecodeIndex = BytecodeIndex(static_cast<intptr_t>(currentBytecodeIndex.offset()) + delta);
284
285 int8_t hasInlineFrame = codeOriginReader.read<int8_t>();
286 ASSERT(hasInlineFrame == 0 || hasInlineFrame == 1);
287 if (hasInlineFrame)
288 currentInlineCallFrame = bitwise_cast<InlineCallFrame*>(codeOriginReader.read<uintptr_t>());
289 else
290 currentInlineCallFrame = nullptr;
291 }
292
293 if (previousPC) {
294 uintptr_t startOfRange = previousPC;
295 // We subtract 1 because we generate end points inclusively in this table, even though we are interested in ranges of the form: [previousPC, currentPC)
296 uintptr_t endOfRange = currentPC - 1;
297 if (startOfRange <= pcAsInt && pcAsInt <= endOfRange)
298 return Optional<CodeOrigin>(previousOrigin); // We return previousOrigin here because CodeOrigin's are mapped to the startValue of the range.
299 }
300 }
301
302 RELEASE_ASSERT_NOT_REACHED();
303 return WTF::nullopt;
304}
305
306} // namespace JSC
307
308#endif // ENABLE(JIT)
309