src/third_party/WebKit/Source/WTF/wtf/BumpPointerAllocator.h

/*
 * 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. 
 */

#ifndef BumpPointerAllocator_h
#define BumpPointerAllocator_h

#include <algorithm>
#include <wtf/PageAllocation.h>
#include <wtf/PageBlock.h>

namespace WTF {

#define MINIMUM_BUMP_POOL_SIZE 0x1000

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);
    }

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 = std::max(static_cast<size_t>(MINIMUM_BUMP_POOL_SIZE), WTF::pageSize());
        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();
    }

private:
    BumpPointerPool* m_head;
};

}

using WTF::BumpPointerAllocator;

#endif // BumpPointerAllocator_h