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