Add Optional to Forward.h.
[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 #include <wtf/Optional.h>
31
32 namespace JSC {
33
34 HeapSnapshot::HeapSnapshot(HeapSnapshot* previousSnapshot)
35     : m_previous(previousSnapshot)
36 {
37 }
38
39 HeapSnapshot::~HeapSnapshot()
40 {
41 }
42
43 void 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
52 void 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
82 void 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
101 void 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
134 Optional<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
160 Optional<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