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