The Tor Browser / file revision

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