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
10namespace blink {
11
12class CallbackStack::Block {
13public:
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
22    ~Block()
23    {
24        clearUnused();
25    }
26
27    void clear()
28    {
29        m_current = &m_buffer[0];
30        m_next = 0;
31        clearUnused();
32    }
33
34    Block* next() const { return m_next; }
35    void setNext(Block* next) { m_next = next; }
36
37    bool isEmptyBlock() const
38    {
39        return m_current == &(m_buffer[0]);
40    }
41
42    size_t size() const
43    {
44        return blockSize - (m_limit - m_current);
45    }
46
47    Item* allocateEntry()
48    {
49        if (m_current < m_limit)
50            return m_current++;
51        return 0;
52    }
53
54    Item* pop()
55    {
56        if (isEmptyBlock())
57            return 0;
58        return --m_current;
59    }
60
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)
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
100private:
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
115CallbackStack::CallbackStack() : m_first(new Block(0)), m_last(m_first)
116{
117}
118
119CallbackStack::~CallbackStack()
120{
121    clear();
122    delete m_first;
123    m_first = 0;
124    m_last = 0;
125}
126
127void 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
138bool CallbackStack::isEmpty() const
139{
140    return hasJustOneBlock() && m_first->isEmptyBlock();
141}
142
143void 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
164CallbackStack::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
172CallbackStack::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
190void 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
208void 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
218bool 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
229void 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
240bool CallbackStack::hasJustOneBlock() const
241{
242    return !m_first->next();
243}
244
245void 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)
256bool 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