diff -r 000000000000 -r 6474c204b198 js/src/yarr/BumpPointerAllocator.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/yarr/BumpPointerAllocator.h Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,276 @@ +/* -*- 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 "yarr/PageAllocation.h" + +namespace WTF { + +#if 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(m_current) + size; + ASSERT(allocationEnd > m_current); // check for overflow + if (allocationEnd <= static_cast(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(current) + size; + ASSERT(allocationEnd > current); // check for overflow + ASSERT(allocationEnd <= static_cast(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(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(reinterpret_cast(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(previousPool->m_current) + size) > previousPool->m_current); // check for overflow + ASSERT((static_cast(previousPool->m_current) + size) > static_cast(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(current) + size; + ASSERT(allocationEnd > current); // check for overflow + if (allocationEnd <= static_cast(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(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(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 */