1 // Copyright 2014 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "config.h"
6 #include "platform/heap/CallbackStack.h"
7
8 #include "platform/heap/Heap.h"
9
10 namespace blink {
11
12 class CallbackStack::Block {
13 public:
Block(Block * next)14 explicit Block(Block* next)
15 : m_limit(&(m_buffer[blockSize]))
16 , m_current(&(m_buffer[0]))
17 , m_next(next)
18 {
19 clearUnused();
20 }
21
~Block()22 ~Block()
23 {
24 clearUnused();
25 }
26
clear()27 void clear()
28 {
29 m_current = &m_buffer[0];
30 m_next = 0;
31 clearUnused();
32 }
33
next() const34 Block* next() const { return m_next; }
setNext(Block * next)35 void setNext(Block* next) { m_next = next; }
36
isEmptyBlock() const37 bool isEmptyBlock() const
38 {
39 return m_current == &(m_buffer[0]);
40 }
41
size() const42 size_t size() const
43 {
44 return blockSize - (m_limit - m_current);
45 }
46
allocateEntry()47 Item* allocateEntry()
48 {
49 if (m_current < m_limit)
50 return m_current++;
51 return 0;
52 }
53
pop()54 Item* pop()
55 {
56 if (isEmptyBlock())
57 return 0;
58 return --m_current;
59 }
60
invokeEphemeronCallbacks(Visitor * visitor)61 void invokeEphemeronCallbacks(Visitor* visitor)
62 {
63 // This loop can tolerate entries being added by the callbacks after
64 // iteration starts.
65 for (unsigned i = 0; m_buffer + i < m_current; i++) {
66 Item& item = m_buffer[i];
67
68 // We don't need to check for orphaned pages when popping an ephemeron
69 // callback since the callback is only pushed after the object containing
70 // it has been traced. There are basically three cases to consider:
71 // 1. Member<EphemeronCollection>
72 // 2. EphemeronCollection is part of a containing object
73 // 3. EphemeronCollection is a value object in a collection
74 //
75 // Ad. 1. In this case we push the start of the ephemeron on the
76 // marking stack and do the orphaned page check when popping it off
77 // the marking stack.
78 // Ad. 2. The containing object cannot be on an orphaned page since
79 // in that case we wouldn't have traced its parts. This also means
80 // the ephemeron collection is not on the orphaned page.
81 // Ad. 3. Is the same as 2. The collection containing the ephemeron
82 // collection as a value object cannot be on an orphaned page since
83 // it would not have traced its values in that case.
84 item.call(visitor);
85 }
86 }
87
88 #if ENABLE(ASSERT)
hasCallbackForObject(const void * object)89 bool hasCallbackForObject(const void* object)
90 {
91 for (unsigned i = 0; m_buffer + i < m_current; i++) {
92 Item* item = &m_buffer[i];
93 if (item->object() == object)
94 return true;
95 }
96 return false;
97 }
98 #endif
99
100 private:
clearUnused()101 void clearUnused()
102 {
103 #if ENABLE(ASSERT)
104 for (size_t i = 0; i < blockSize; i++)
105 m_buffer[i] = Item(0, 0);
106 #endif
107 }
108
109 Item m_buffer[blockSize];
110 Item* m_limit;
111 Item* m_current;
112 Block* m_next;
113 };
114
CallbackStack()115 CallbackStack::CallbackStack() : m_first(new Block(0)), m_last(m_first)
116 {
117 }
118
~CallbackStack()119 CallbackStack::~CallbackStack()
120 {
121 clear();
122 delete m_first;
123 m_first = 0;
124 m_last = 0;
125 }
126
clear()127 void CallbackStack::clear()
128 {
129 Block* next;
130 for (Block* current = m_first->next(); current; current = next) {
131 next = current->next();
132 delete current;
133 }
134 m_first->clear();
135 m_last = m_first;
136 }
137
isEmpty() const138 bool CallbackStack::isEmpty() const
139 {
140 return hasJustOneBlock() && m_first->isEmptyBlock();
141 }
142
takeBlockFrom(CallbackStack * other)143 void CallbackStack::takeBlockFrom(CallbackStack* other)
144 {
145 // We assume the stealing stack is empty.
146 ASSERT(isEmpty());
147
148 if (other->isEmpty())
149 return;
150
151 if (other->hasJustOneBlock()) {
152 swap(other);
153 return;
154 }
155
156 // Delete our block and steal the first one from other.
157 delete m_first;
158 m_first = other->m_first;
159 other->m_first = m_first->next();
160 m_first->setNext(0);
161 m_last = m_first;
162 }
163
allocateEntry()164 CallbackStack::Item* CallbackStack::allocateEntry()
165 {
166 if (Item* item = m_first->allocateEntry())
167 return item;
168 m_first = new Block(m_first);
169 return m_first->allocateEntry();
170 }
171
pop()172 CallbackStack::Item* CallbackStack::pop()
173 {
174 Item* item = m_first->pop();
175 while (!item) {
176 if (hasJustOneBlock()) {
177 #if ENABLE(ASSERT)
178 m_first->clear();
179 #endif
180 return 0;
181 }
182 Block* next = m_first->next();
183 delete m_first;
184 m_first = next;
185 item = m_first->pop();
186 }
187 return item;
188 }
189
invokeEphemeronCallbacks(Visitor * visitor)190 void CallbackStack::invokeEphemeronCallbacks(Visitor* visitor)
191 {
192 // The first block is the only one where new ephemerons are added, so we
193 // call the callbacks on that last, to catch any new ephemerons discovered
194 // in the callbacks.
195 // However, if enough ephemerons were added, we may have a new block that
196 // has been prepended to the chain. This will be very rare, but we can
197 // handle the situation by starting again and calling all the callbacks
198 // on the prepended blocks.
199 Block* from = 0;
200 Block* upto = 0;
201 while (from != m_first) {
202 upto = from;
203 from = m_first;
204 invokeOldestCallbacks(from, upto, visitor);
205 }
206 }
207
invokeOldestCallbacks(Block * from,Block * upto,Visitor * visitor)208 void CallbackStack::invokeOldestCallbacks(Block* from, Block* upto, Visitor* visitor)
209 {
210 if (from == upto)
211 return;
212 ASSERT(from);
213 // Recurse first (blockSize at a time) so we get to the newly added entries last.
214 invokeOldestCallbacks(from->next(), upto, visitor);
215 from->invokeEphemeronCallbacks(visitor);
216 }
217
sizeExceeds(size_t minSize) const218 bool CallbackStack::sizeExceeds(size_t minSize) const
219 {
220 Block* current = m_first;
221 for (size_t size = m_first->size(); size < minSize; size += current->size()) {
222 if (!current->next())
223 return false;
224 current = current->next();
225 }
226 return true;
227 }
228
append(CallbackStack * other)229 void CallbackStack::append(CallbackStack* other)
230 {
231 ASSERT(!m_last->next());
232 ASSERT(!other->m_last->next());
233 m_last->setNext(other->m_first);
234 m_last = other->m_last;
235 // After append, we mark |other| as ill-formed by clearing its pointers.
236 other->m_first = 0;
237 other->m_last = 0;
238 }
239
hasJustOneBlock() const240 bool CallbackStack::hasJustOneBlock() const
241 {
242 return !m_first->next();
243 }
244
swap(CallbackStack * other)245 void CallbackStack::swap(CallbackStack* other)
246 {
247 Block* tmp = m_first;
248 m_first = other->m_first;
249 other->m_first = tmp;
250 tmp = m_last;
251 m_last = other->m_last;
252 other->m_last = tmp;
253 }
254
255 #if ENABLE(ASSERT)
hasCallbackForObject(const void * object)256 bool CallbackStack::hasCallbackForObject(const void* object)
257 {
258 for (Block* current = m_first; current; current = current->next()) {
259 if (current->hasCallbackForObject(object))
260 return true;
261 }
262 return false;
263 }
264 #endif
265
266 }
267