| /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- |
| * vim: set ts=8 sts=4 et sw=4 tw=99: |
| * |
| * ***** BEGIN LICENSE BLOCK ***** |
| * Copyright (C) 2010 Apple Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY |
| * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
| * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| * |
| * ***** END LICENSE BLOCK ***** */ |
| |
| #ifndef yarr_BumpPointerAllocator_h |
| #define yarr_BumpPointerAllocator_h |
| |
| #include "PageAllocation.h" |
| |
| namespace WTF { |
| |
| #if defined(STARBOARD) |
| #define MINIMUM_BUMP_POOL_SIZE SB_MEMORY_PAGE_SIZE |
| #elif WTF_CPU_SPARC |
| #define MINIMUM_BUMP_POOL_SIZE 0x2000 |
| #elif WTF_CPU_IA64 |
| #define MINIMUM_BUMP_POOL_SIZE 0x4000 |
| #else |
| #define MINIMUM_BUMP_POOL_SIZE 0x1000 |
| #endif |
| |
| class BumpPointerPool { |
| public: |
| // ensureCapacity will check whether the current pool has capacity to |
| // allocate 'size' bytes of memory If it does not, it will attempt to |
| // allocate a new pool (which will be added to this one in a chain). |
| // |
| // If allocation fails (out of memory) this method will return null. |
| // If the return value is non-null, then callers should update any |
| // references they have to this current (possibly full) BumpPointerPool |
| // to instead point to the newly returned BumpPointerPool. |
| BumpPointerPool* ensureCapacity(size_t size) |
| { |
| void* allocationEnd = static_cast<char*>(m_current) + size; |
| ASSERT(allocationEnd > m_current); // check for overflow |
| if (allocationEnd <= static_cast<void*>(this)) |
| return this; |
| return ensureCapacityCrossPool(this, size); |
| } |
| |
| // alloc should only be called after calling ensureCapacity; as such |
| // alloc will never fail. |
| void* alloc(size_t size) |
| { |
| void* current = m_current; |
| void* allocationEnd = static_cast<char*>(current) + size; |
| ASSERT(allocationEnd > current); // check for overflow |
| ASSERT(allocationEnd <= static_cast<void*>(this)); |
| m_current = allocationEnd; |
| return current; |
| } |
| |
| // The dealloc method releases memory allocated using alloc. Memory |
| // must be released in a LIFO fashion, e.g. if the client calls alloc |
| // four times, returning pointer A, B, C, D, then the only valid order |
| // in which these may be deallocaed is D, C, B, A. |
| // |
| // The client may optionally skip some deallocations. In the example |
| // above, it would be valid to only explicitly dealloc C, A (D being |
| // dealloced along with C, B along with A). |
| // |
| // If pointer was not allocated from this pool (or pools) then dealloc |
| // will CRASH(). Callers should update any references they have to |
| // this current BumpPointerPool to instead point to the returned |
| // BumpPointerPool. |
| BumpPointerPool* dealloc(void* position) |
| { |
| if ((position >= m_start) && (position <= static_cast<void*>(this))) { |
| ASSERT(position <= m_current); |
| m_current = position; |
| return this; |
| } |
| return deallocCrossPool(this, position); |
| } |
| |
| size_t sizeOfNonHeapData() const |
| { |
| ASSERT(!m_previous); |
| size_t n = 0; |
| const BumpPointerPool *curr = this; |
| while (curr) { |
| n += m_allocation.size(); |
| curr = curr->m_next; |
| } |
| return n; |
| } |
| |
| private: |
| // Placement operator new, returns the last 'size' bytes of allocation for use as this. |
| void* operator new(size_t size, const PageAllocation& allocation) |
| { |
| ASSERT(size < allocation.size()); |
| return reinterpret_cast<char*>(reinterpret_cast<intptr_t>(allocation.base()) + allocation.size()) - size; |
| } |
| |
| BumpPointerPool(const PageAllocation& allocation) |
| : m_current(allocation.base()) |
| , m_start(allocation.base()) |
| , m_next(0) |
| , m_previous(0) |
| , m_allocation(allocation) |
| { |
| } |
| |
| static BumpPointerPool* create(size_t minimumCapacity = 0) |
| { |
| // Add size of BumpPointerPool object, check for overflow. |
| minimumCapacity += sizeof(BumpPointerPool); |
| if (minimumCapacity < sizeof(BumpPointerPool)) |
| return 0; |
| |
| size_t poolSize = MINIMUM_BUMP_POOL_SIZE; |
| while (poolSize < minimumCapacity) { |
| poolSize <<= 1; |
| // The following if check relies on MINIMUM_BUMP_POOL_SIZE being a power of 2! |
| ASSERT(!(MINIMUM_BUMP_POOL_SIZE & (MINIMUM_BUMP_POOL_SIZE - 1))); |
| if (!poolSize) |
| return 0; |
| } |
| |
| PageAllocation allocation = PageAllocation::allocate(poolSize); |
| if (!!allocation) |
| return new(allocation) BumpPointerPool(allocation); |
| return 0; |
| } |
| |
| void shrink() |
| { |
| ASSERT(!m_previous); |
| m_current = m_start; |
| while (m_next) { |
| BumpPointerPool* nextNext = m_next->m_next; |
| m_next->destroy(); |
| m_next = nextNext; |
| } |
| } |
| |
| void destroy() |
| { |
| m_allocation.deallocate(); |
| } |
| |
| static BumpPointerPool* ensureCapacityCrossPool(BumpPointerPool* previousPool, size_t size) |
| { |
| // The pool passed should not have capacity, so we'll start with the next one. |
| ASSERT(previousPool); |
| ASSERT((static_cast<char*>(previousPool->m_current) + size) > previousPool->m_current); // check for overflow |
| ASSERT((static_cast<char*>(previousPool->m_current) + size) > static_cast<void*>(previousPool)); |
| BumpPointerPool* pool = previousPool->m_next; |
| |
| while (true) { |
| if (!pool) { |
| // We've run to the end; allocate a new pool. |
| pool = BumpPointerPool::create(size); |
| previousPool->m_next = pool; |
| pool->m_previous = previousPool; |
| return pool; |
| } |
| |
| // |
| void* current = pool->m_current; |
| void* allocationEnd = static_cast<char*>(current) + size; |
| ASSERT(allocationEnd > current); // check for overflow |
| if (allocationEnd <= static_cast<void*>(pool)) |
| return pool; |
| } |
| } |
| |
| static BumpPointerPool* deallocCrossPool(BumpPointerPool* pool, void* position) |
| { |
| // Should only be called if position is not in the current pool. |
| ASSERT((position < pool->m_start) || (position > static_cast<void*>(pool))); |
| |
| while (true) { |
| // Unwind the current pool to the start, move back in the chain to the previous pool. |
| pool->m_current = pool->m_start; |
| pool = pool->m_previous; |
| |
| // position was nowhere in the chain! |
| if (!pool) |
| CRASH(); |
| |
| if ((position >= pool->m_start) && (position <= static_cast<void*>(pool))) { |
| ASSERT(position <= pool->m_current); |
| pool->m_current = position; |
| return pool; |
| } |
| } |
| } |
| |
| void* m_current; |
| void* m_start; |
| BumpPointerPool* m_next; |
| BumpPointerPool* m_previous; |
| PageAllocation m_allocation; |
| |
| friend class BumpPointerAllocator; |
| }; |
| |
| // A BumpPointerAllocator manages a set of BumpPointerPool objects, which |
| // can be used for LIFO (stack like) allocation. |
| // |
| // To begin allocating using this class call startAllocator(). The result |
| // of this method will be null if the initial pool allocation fails, or a |
| // pointer to a BumpPointerPool object that can be used to perform |
| // allocations. Whilst running no memory will be released until |
| // stopAllocator() is called. At this point all allocations made through |
| // this allocator will be reaped, and underlying memory may be freed. |
| // |
| // (In practice we will still hold on to the initial pool to allow allocation |
| // to be quickly restared, but aditional pools will be freed). |
| // |
| // This allocator is non-renetrant, it is encumbant on the clients to ensure |
| // startAllocator() is not called again until stopAllocator() has been called. |
| class BumpPointerAllocator { |
| public: |
| BumpPointerAllocator() |
| : m_head(0) |
| { |
| } |
| |
| ~BumpPointerAllocator() |
| { |
| if (m_head) |
| m_head->destroy(); |
| } |
| |
| BumpPointerPool* startAllocator() |
| { |
| if (!m_head) |
| m_head = BumpPointerPool::create(); |
| return m_head; |
| } |
| |
| void stopAllocator() |
| { |
| if (m_head) |
| m_head->shrink(); |
| } |
| |
| size_t sizeOfNonHeapData() const |
| { |
| return m_head ? m_head->sizeOfNonHeapData() : 0; |
| } |
| |
| private: |
| BumpPointerPool* m_head; |
| }; |
| |
| } |
| |
| using WTF::BumpPointerAllocator; |
| |
| #endif /* yarr_BumpPointerAllocator_h */ |