| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (C) 2010 Apple Inc. All rights reserved. | |
| 3 * | |
| 4 * Redistribution and use in source and binary forms, with or without | |
| 5 * modification, are permitted provided that the following conditions | |
| 6 * are met: | |
| 7 * 1. Redistributions of source code must retain the above copyright | |
| 8 * notice, this list of conditions and the following disclaimer. | |
| 9 * 2. Redistributions in binary form must reproduce the above copyright | |
| 10 * notice, this list of conditions and the following disclaimer in the | |
| 11 * documentation and/or other materials provided with the distribution. | |
| 12 * | |
| 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY | |
| 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
| 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
| 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR | |
| 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | |
| 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | |
| 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | |
| 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | |
| 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
| 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
| 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| 24 */ | |
| 25 | |
| 26 #ifndef BumpPointerAllocator_h | |
| 27 #define BumpPointerAllocator_h | |
| 28 | |
| 29 #include <algorithm> | |
| 30 #include <wtf/PageAllocation.h> | |
| 31 #include <wtf/PageBlock.h> | |
| 32 | |
| 33 namespace WTF { | |
| 34 | |
| 35 #define MINIMUM_BUMP_POOL_SIZE 0x1000 | |
| 36 | |
| 37 class BumpPointerPool { | |
| 38 public: | |
| 39 // ensureCapacity will check whether the current pool has capacity to | |
| 40 // allocate 'size' bytes of memory If it does not, it will attempt to | |
| 41 // allocate a new pool (which will be added to this one in a chain). | |
| 42 // | |
| 43 // If allocation fails (out of memory) this method will return null. | |
| 44 // If the return value is non-null, then callers should update any | |
| 45 // references they have to this current (possibly full) BumpPointerPool | |
| 46 // to instead point to the newly returned BumpPointerPool. | |
| 47 BumpPointerPool* ensureCapacity(size_t size) | |
| 48 { | |
| 49 void* allocationEnd = static_cast<char*>(m_current) + size; | |
| 50 ASSERT(allocationEnd > m_current); // check for overflow | |
| 51 if (allocationEnd <= static_cast<void*>(this)) | |
| 52 return this; | |
| 53 return ensureCapacityCrossPool(this, size); | |
| 54 } | |
| 55 | |
| 56 // alloc should only be called after calling ensureCapacity; as such | |
| 57 // alloc will never fail. | |
| 58 void* alloc(size_t size) | |
| 59 { | |
| 60 void* current = m_current; | |
| 61 void* allocationEnd = static_cast<char*>(current) + size; | |
| 62 ASSERT(allocationEnd > current); // check for overflow | |
| 63 ASSERT(allocationEnd <= static_cast<void*>(this)); | |
| 64 m_current = allocationEnd; | |
| 65 return current; | |
| 66 } | |
| 67 | |
| 68 // The dealloc method releases memory allocated using alloc. Memory | |
| 69 // must be released in a LIFO fashion, e.g. if the client calls alloc | |
| 70 // four times, returning pointer A, B, C, D, then the only valid order | |
| 71 // in which these may be deallocaed is D, C, B, A. | |
| 72 // | |
| 73 // The client may optionally skip some deallocations. In the example | |
| 74 // above, it would be valid to only explicitly dealloc C, A (D being | |
| 75 // dealloced along with C, B along with A). | |
| 76 // | |
| 77 // If pointer was not allocated from this pool (or pools) then dealloc | |
| 78 // will CRASH(). Callers should update any references they have to | |
| 79 // this current BumpPointerPool to instead point to the returned | |
| 80 // BumpPointerPool. | |
| 81 BumpPointerPool* dealloc(void* position) | |
| 82 { | |
| 83 if ((position >= m_start) && (position <= static_cast<void*>(this))) { | |
| 84 ASSERT(position <= m_current); | |
| 85 m_current = position; | |
| 86 return this; | |
| 87 } | |
| 88 return deallocCrossPool(this, position); | |
| 89 } | |
| 90 | |
| 91 private: | |
| 92 // Placement operator new, returns the last 'size' bytes of allocation for u
se as this. | |
| 93 void* operator new(size_t size, const PageAllocation& allocation) | |
| 94 { | |
| 95 ASSERT(size < allocation.size()); | |
| 96 return reinterpret_cast<char*>(reinterpret_cast<intptr_t>(allocation.bas
e()) + allocation.size()) - size; | |
| 97 } | |
| 98 | |
| 99 BumpPointerPool(const PageAllocation& allocation) | |
| 100 : m_current(allocation.base()) | |
| 101 , m_start(allocation.base()) | |
| 102 , m_next(0) | |
| 103 , m_previous(0) | |
| 104 , m_allocation(allocation) | |
| 105 { | |
| 106 } | |
| 107 | |
| 108 static BumpPointerPool* create(size_t minimumCapacity = 0) | |
| 109 { | |
| 110 // Add size of BumpPointerPool object, check for overflow. | |
| 111 minimumCapacity += sizeof(BumpPointerPool); | |
| 112 if (minimumCapacity < sizeof(BumpPointerPool)) | |
| 113 return 0; | |
| 114 | |
| 115 size_t poolSize = std::max(static_cast<size_t>(MINIMUM_BUMP_POOL_SIZE),
WTF::pageSize()); | |
| 116 while (poolSize < minimumCapacity) { | |
| 117 poolSize <<= 1; | |
| 118 // The following if check relies on MINIMUM_BUMP_POOL_SIZE being a p
ower of 2! | |
| 119 ASSERT(!(MINIMUM_BUMP_POOL_SIZE & (MINIMUM_BUMP_POOL_SIZE - 1))); | |
| 120 if (!poolSize) | |
| 121 return 0; | |
| 122 } | |
| 123 | |
| 124 PageAllocation allocation = PageAllocation::allocate(poolSize); | |
| 125 if (!!allocation) | |
| 126 return new (allocation) BumpPointerPool(allocation); | |
| 127 return 0; | |
| 128 } | |
| 129 | |
| 130 void shrink() | |
| 131 { | |
| 132 ASSERT(!m_previous); | |
| 133 m_current = m_start; | |
| 134 while (m_next) { | |
| 135 BumpPointerPool* nextNext = m_next->m_next; | |
| 136 m_next->destroy(); | |
| 137 m_next = nextNext; | |
| 138 } | |
| 139 } | |
| 140 | |
| 141 void destroy() | |
| 142 { | |
| 143 m_allocation.deallocate(); | |
| 144 } | |
| 145 | |
| 146 static BumpPointerPool* ensureCapacityCrossPool(BumpPointerPool* previousPoo
l, size_t size) | |
| 147 { | |
| 148 // The pool passed should not have capacity, so we'll start with the nex
t one. | |
| 149 ASSERT(previousPool); | |
| 150 ASSERT((static_cast<char*>(previousPool->m_current) + size) > previousPo
ol->m_current); // check for overflow | |
| 151 ASSERT((static_cast<char*>(previousPool->m_current) + size) > static_cas
t<void*>(previousPool)); | |
| 152 BumpPointerPool* pool = previousPool->m_next; | |
| 153 | |
| 154 while (true) { | |
| 155 if (!pool) { | |
| 156 // We've run to the end; allocate a new pool. | |
| 157 pool = BumpPointerPool::create(size); | |
| 158 previousPool->m_next = pool; | |
| 159 pool->m_previous = previousPool; | |
| 160 return pool; | |
| 161 } | |
| 162 | |
| 163 // | |
| 164 void* current = pool->m_current; | |
| 165 void* allocationEnd = static_cast<char*>(current) + size; | |
| 166 ASSERT(allocationEnd > current); // check for overflow | |
| 167 if (allocationEnd <= static_cast<void*>(pool)) | |
| 168 return pool; | |
| 169 } | |
| 170 } | |
| 171 | |
| 172 static BumpPointerPool* deallocCrossPool(BumpPointerPool* pool, void* positi
on) | |
| 173 { | |
| 174 // Should only be called if position is not in the current pool. | |
| 175 ASSERT((position < pool->m_start) || (position > static_cast<void*>(pool
))); | |
| 176 | |
| 177 while (true) { | |
| 178 // Unwind the current pool to the start, move back in the chain to t
he previous pool. | |
| 179 pool->m_current = pool->m_start; | |
| 180 pool = pool->m_previous; | |
| 181 | |
| 182 // position was nowhere in the chain! | |
| 183 if (!pool) | |
| 184 CRASH(); | |
| 185 | |
| 186 if ((position >= pool->m_start) && (position <= static_cast<void*>(p
ool))) { | |
| 187 ASSERT(position <= pool->m_current); | |
| 188 pool->m_current = position; | |
| 189 return pool; | |
| 190 } | |
| 191 } | |
| 192 } | |
| 193 | |
| 194 void* m_current; | |
| 195 void* m_start; | |
| 196 BumpPointerPool* m_next; | |
| 197 BumpPointerPool* m_previous; | |
| 198 PageAllocation m_allocation; | |
| 199 | |
| 200 friend class BumpPointerAllocator; | |
| 201 }; | |
| 202 | |
| 203 // A BumpPointerAllocator manages a set of BumpPointerPool objects, which | |
| 204 // can be used for LIFO (stack like) allocation. | |
| 205 // | |
| 206 // To begin allocating using this class call startAllocator(). The result | |
| 207 // of this method will be null if the initial pool allocation fails, or a | |
| 208 // pointer to a BumpPointerPool object that can be used to perform | |
| 209 // allocations. Whilst running no memory will be released until | |
| 210 // stopAllocator() is called. At this point all allocations made through | |
| 211 // this allocator will be reaped, and underlying memory may be freed. | |
| 212 // | |
| 213 // (In practice we will still hold on to the initial pool to allow allocation | |
| 214 // to be quickly restared, but aditional pools will be freed). | |
| 215 // | |
| 216 // This allocator is non-renetrant, it is encumbant on the clients to ensure | |
| 217 // startAllocator() is not called again until stopAllocator() has been called. | |
| 218 class BumpPointerAllocator { | |
| 219 public: | |
| 220 BumpPointerAllocator() | |
| 221 : m_head(0) | |
| 222 { | |
| 223 } | |
| 224 | |
| 225 ~BumpPointerAllocator() | |
| 226 { | |
| 227 if (m_head) | |
| 228 m_head->destroy(); | |
| 229 } | |
| 230 | |
| 231 BumpPointerPool* startAllocator() | |
| 232 { | |
| 233 if (!m_head) | |
| 234 m_head = BumpPointerPool::create(); | |
| 235 return m_head; | |
| 236 } | |
| 237 | |
| 238 void stopAllocator() | |
| 239 { | |
| 240 if (m_head) | |
| 241 m_head->shrink(); | |
| 242 } | |
| 243 | |
| 244 private: | |
| 245 BumpPointerPool* m_head; | |
| 246 }; | |
| 247 | |
| 248 } | |
| 249 | |
| 250 using WTF::BumpPointerAllocator; | |
| 251 | |
| 252 #endif // BumpPointerAllocator_h | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 14238015:
Move Source/WTF/wtf to Source/wtf (Closed)
Base URL: svn://svn.chromium.org/blink/trunk