• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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