Home | History | Annotate | Download | only in heap 
      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:
     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 
    100 private:
    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 
    115 CallbackStack::CallbackStack() : m_first(new Block(0)), m_last(m_first)
    116 {
    117 }
    118 
    119 CallbackStack::~CallbackStack()
    120 {
    121     clear();
    122     delete m_first;
    123     m_first = 0;
    124     m_last = 0;
    125 }
    126 
    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 
    138 bool CallbackStack::isEmpty() const
    139 {
    140     return hasJustOneBlock() && m_first->isEmptyBlock();
    141 }
    142 
    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 
    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 
    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 
    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 
    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 
    218 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 
    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 
    240 bool CallbackStack::hasJustOneBlock() const
    241 {
    242     return !m_first->next();
    243 }
    244 
    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)
    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