Add ability to generate a Heap Snapshot
[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 }
49
50 void HeapSnapshot::sweepCell(JSCell* cell)
51 {
52     ASSERT(cell);
53
54     if (m_finalized && !isEmpty()) {
55         unsigned start = 0;
56         unsigned end = m_nodes.size();
57         while (start != end) {
58             unsigned middle = start + ((end - start) / 2);
59             HeapSnapshotNode& node = m_nodes[middle];
60             if (cell == node.cell) {
61                 // Cells should always have 0 as low bits.
62                 // Mark this cell for removal by setting the low bit.
63                 ASSERT(!(reinterpret_cast<intptr_t>(node.cell) & CellToSweepTag));
64                 node.cell = reinterpret_cast<JSCell*>(reinterpret_cast<intptr_t>(node.cell) | CellToSweepTag);
65                 m_hasCellsToSweep = true;
66                 return;
67             }
68             if (cell < node.cell)
69                 end = middle;
70             else
71                 start = middle + 1;
72         }
73     }
74
75     if (m_previous)
76         m_previous->sweepCell(cell);
77 }
78
79 void HeapSnapshot::shrinkToFit()
80 {
81     if (m_finalized && m_hasCellsToSweep) {
82         m_nodes.removeAllMatching(
83             [&] (const HeapSnapshotNode& node) -> bool {
84                 return reinterpret_cast<intptr_t>(node.cell) & CellToSweepTag;
85             });
86         m_nodes.shrinkToFit();
87         m_hasCellsToSweep = false;
88     }
89
90     if (m_previous)
91         m_previous->shrinkToFit();
92 }
93
94 void HeapSnapshot::finalize()
95 {
96     ASSERT(!m_finalized);
97     m_finalized = true;
98
99     // Nodes are appended to the snapshot in identifier order.
100     // Now that we have the complete list of nodes we will sort
101     // them in a different order. Remember the range of identifiers
102     // in this snapshot.
103     if (!isEmpty()) {
104         m_firstObjectIdentifier = m_nodes.first().identifier;
105         m_lastObjectIdentifier = m_nodes.last().identifier;
106     }
107
108     std::sort(m_nodes.begin(), m_nodes.end(), [] (const HeapSnapshotNode& a, const HeapSnapshotNode& b) {
109         return a.cell < b.cell;
110     });
111
112 #ifndef NDEBUG
113     // Assert there are no duplicates or nullptr cells.
114     JSCell* previousCell = nullptr;
115     for (auto& node : m_nodes) {
116         ASSERT(node.cell);
117         ASSERT(!(reinterpret_cast<intptr_t>(node.cell) & CellToSweepTag));
118         if (previousCell)
119             ASSERT(node.cell != previousCell);
120         previousCell = node.cell;
121     }
122 #endif
123 }
124
125 Optional<HeapSnapshotNode> HeapSnapshot::nodeForCell(JSCell* cell)
126 {
127     ASSERT(m_finalized);
128
129     if (!isEmpty()) {
130         unsigned start = 0;
131         unsigned end = m_nodes.size();
132         while (start != end) {
133             unsigned middle = start + ((end - start) / 2);
134             HeapSnapshotNode& node = m_nodes[middle];
135             if (cell == node.cell)
136                 return Optional<HeapSnapshotNode>(node);
137             if (cell < node.cell)
138                 end = middle;
139             else
140                 start = middle + 1;
141         }
142     }
143
144     if (m_previous)
145         return m_previous->nodeForCell(cell);
146
147     return Nullopt;
148 }
149
150 Optional<HeapSnapshotNode> HeapSnapshot::nodeForObjectIdentifier(unsigned objectIdentifier)
151 {
152     if (isEmpty()) {
153         if (m_previous)
154             return m_previous->nodeForObjectIdentifier(objectIdentifier);
155         return Nullopt;
156     }
157
158     if (objectIdentifier > m_lastObjectIdentifier)
159         return Nullopt;
160
161     if (objectIdentifier < m_firstObjectIdentifier) {
162         if (m_previous)
163             return m_previous->nodeForObjectIdentifier(objectIdentifier);
164         return Nullopt;
165     }
166
167     for (auto& node : m_nodes) {
168         if (node.identifier == objectIdentifier)
169             return Optional<HeapSnapshotNode>(node);
170     }
171
172     return Nullopt;
173 }
174
175 } // namespace JSC