text: /*
   * 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. 
   */
  
  #pragma once
  
  #include <algorithm>
  #include <wtf/PageAllocation.h>
  #include <wtf/PageBlock.h>
  
  namespace WTF {
  
  #define MINIMUM_BUMP_POOL_SIZE 0x1000
  
  class BumpPointerPool {
      WTF_MAKE_FAST_ALLOCATED;
  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_WITH_SECURITY_IMPLICATION(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_WITH_SECURITY_IMPLICATION(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_WITH_SECURITY_IMPLICATION(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 {
      WTF_MAKE_FAST_ALLOCATED;
  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;
  