1/*
2 * Copyright (C) 2016 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 "HeapSnapshot.h"
28
29#include "JSCInlines.h"
30#include <wtf/Optional.h>
31
32namespace JSC {
33
34HeapSnapshot::HeapSnapshot(HeapSnapshot* previousSnapshot)
35 : m_previous(previousSnapshot)
36{
37}
38
39HeapSnapshot::~HeapSnapshot()
40{
41}
42
43void HeapSnapshot::appendNode(const HeapSnapshotNode& node)
44{
45 ASSERT(!m_finalized);
46 ASSERT(!m_previous || !m_previous->nodeForCell(node.cell));
47
48 m_nodes.append(node);
49 m_filter.add(bitwise_cast<uintptr_t>(node.cell));
50}
51
52void HeapSnapshot::sweepCell(JSCell* cell)
53{
54 ASSERT(cell);
55
56 if (m_finalized && !m_filter.ruleOut(bitwise_cast<uintptr_t>(cell))) {
57 ASSERT_WITH_MESSAGE(!isEmpty(), "Our filter should have ruled us out if we are empty.");
58 unsigned start = 0;
59 unsigned end = m_nodes.size();
60 while (start != end) {
61 unsigned middle = start + ((end - start) / 2);
62 HeapSnapshotNode& node = m_nodes[middle];
63 if (cell == node.cell) {
64 // Cells should always have 0 as low bits.
65 // Mark this cell for removal by setting the low bit.
66 ASSERT(!(reinterpret_cast<intptr_t>(node.cell) & CellToSweepTag));
67 node.cell = reinterpret_cast<JSCell*>(reinterpret_cast<intptr_t>(node.cell) | CellToSweepTag);
68 m_hasCellsToSweep = true;
69 return;
70 }
71 if (cell < node.cell)
72 end = middle;
73 else
74 start = middle + 1;
75 }
76 }
77
78 if (m_previous)
79 m_previous->sweepCell(cell);
80}
81
82void HeapSnapshot::shrinkToFit()
83{
84 if (m_finalized && m_hasCellsToSweep) {
85 m_filter.reset();
86 m_nodes.removeAllMatching(
87 [&] (const HeapSnapshotNode& node) -> bool {
88 bool willRemoveCell = bitwise_cast<intptr_t>(node.cell) & CellToSweepTag;
89 if (!willRemoveCell)
90 m_filter.add(bitwise_cast<uintptr_t>(node.cell));
91 return willRemoveCell;
92 });
93 m_nodes.shrinkToFit();
94 m_hasCellsToSweep = false;
95 }
96
97 if (m_previous)
98 m_previous->shrinkToFit();
99}
100
101void HeapSnapshot::finalize()
102{
103 ASSERT(!m_finalized);
104 m_finalized = true;
105
106 // Nodes are appended to the snapshot in identifier order.
107 // Now that we have the complete list of nodes we will sort
108 // them in a different order. Remember the range of identifiers
109 // in this snapshot.
110 if (!isEmpty()) {
111 m_firstObjectIdentifier = m_nodes.first().identifier;
112 m_lastObjectIdentifier = m_nodes.last().identifier;
113 }
114
115 std::sort(m_nodes.begin(), m_nodes.end(), [] (const HeapSnapshotNode& a, const HeapSnapshotNode& b) {
116 return a.cell < b.cell;
117 });
118
119#ifndef NDEBUG
120 // Assert there are no duplicates or nullptr cells.
121 JSCell* previousCell = nullptr;
122 for (auto& node : m_nodes) {
123 ASSERT(node.cell);
124 ASSERT(!(reinterpret_cast<intptr_t>(node.cell) & CellToSweepTag));
125 if (node.cell == previousCell) {
126 dataLog("Seeing same cell twice: ", RawPointer(previousCell), "\n");
127 ASSERT(node.cell != previousCell);
128 }
129 previousCell = node.cell;
130 }
131#endif
132}
133
134Optional<HeapSnapshotNode> HeapSnapshot::nodeForCell(JSCell* cell)
135{
136 ASSERT(m_finalized);
137
138 if (!m_filter.ruleOut(bitwise_cast<uintptr_t>(cell))) {
139 ASSERT_WITH_MESSAGE(!isEmpty(), "Our filter should have ruled us out if we are empty.");
140 unsigned start = 0;
141 unsigned end = m_nodes.size();
142 while (start != end) {
143 unsigned middle = start + ((end - start) / 2);
144 HeapSnapshotNode& node = m_nodes[middle];
145 if (cell == node.cell)
146 return Optional<HeapSnapshotNode>(node);
147 if (cell < node.cell)
148 end = middle;
149 else
150 start = middle + 1;
151 }
152 }
153
154 if (m_previous)
155 return m_previous->nodeForCell(cell);
156
157 return WTF::nullopt;
158}
159
160Optional<HeapSnapshotNode> HeapSnapshot::nodeForObjectIdentifier(unsigned objectIdentifier)
161{
162 if (isEmpty()) {
163 if (m_previous)
164 return m_previous->nodeForObjectIdentifier(objectIdentifier);
165 return WTF::nullopt;
166 }
167
168 if (objectIdentifier > m_lastObjectIdentifier)
169 return WTF::nullopt;
170
171 if (objectIdentifier < m_firstObjectIdentifier) {
172 if (m_previous)
173 return m_previous->nodeForObjectIdentifier(objectIdentifier);
174 return WTF::nullopt;
175 }
176
177 for (auto& node : m_nodes) {
178 if (node.identifier == objectIdentifier)
179 return Optional<HeapSnapshotNode>(node);
180 }
181
182 return WTF::nullopt;
183}
184
185} // namespace JSC
186