text: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   * vim: set ts=8 sts=4 et sw=4 tw=99:
   * This Source Code Form is subject to the terms of the Mozilla Public
   * License, v. 2.0. If a copy of the MPL was not distributed with this
   * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
  
  #ifndef ds_LifoAlloc_h
  #define ds_LifoAlloc_h
  
  #include "mozilla/Attributes.h"
  #include "mozilla/DebugOnly.h"
  #include "mozilla/MathAlgorithms.h"
  #include "mozilla/MemoryChecking.h"
  #include "mozilla/MemoryReporting.h"
  #include "mozilla/PodOperations.h"
  #include "mozilla/TemplateLib.h"
  #include "mozilla/TypeTraits.h"
  
  // This data structure supports stacky LIFO allocation (mark/release and
  // LifoAllocScope). It does not maintain one contiguous segment; instead, it
  // maintains a bunch of linked memory segments. In order to prevent malloc/free
  // thrashing, unused segments are deallocated when garbage collection occurs.
  
  #include "jsutil.h"
  
  namespace js {
  
  namespace detail {
  
  static const size_t LIFO_ALLOC_ALIGN = 8;
  
  MOZ_ALWAYS_INLINE
  char*
  AlignPtr(void* orig)
  {
      static_assert(mozilla::tl::FloorLog2<LIFO_ALLOC_ALIGN>::value ==
                    mozilla::tl::CeilingLog2<LIFO_ALLOC_ALIGN>::value,
                    "LIFO_ALLOC_ALIGN must be a power of two");
  
      char* result = (char*) ((uintptr_t(orig) + (LIFO_ALLOC_ALIGN - 1)) & (~LIFO_ALLOC_ALIGN + 1));
      MOZ_ASSERT(uintptr_t(result) % LIFO_ALLOC_ALIGN == 0);
      return result;
  }
  
  // Header for a chunk of memory wrangled by the LifoAlloc.
  class BumpChunk
  {
      char*       bump;          // start of the available data
      char*       limit;         // end of the data
      BumpChunk*  next_;         // the next BumpChunk
      size_t      bumpSpaceSize;  // size of the data area
  
      char* headerBase() { return reinterpret_cast<char*>(this); }
      char* bumpBase() const { return limit - bumpSpaceSize; }
  
      explicit BumpChunk(size_t bumpSpaceSize)
        : bump(reinterpret_cast<char*>(this) + sizeof(BumpChunk)),
          limit(bump + bumpSpaceSize),
          next_(nullptr), bumpSpaceSize(bumpSpaceSize)
      {
          MOZ_ASSERT(bump == AlignPtr(bump));
      }
  
      void setBump(void* ptr) {
          MOZ_ASSERT(bumpBase() <= ptr);
          MOZ_ASSERT(ptr <= limit);
  #if defined(DEBUG) || defined(MOZ_HAVE_MEM_CHECKS)
          char* prevBump = bump;
  #endif
          bump = static_cast<char*>(ptr);
  #ifdef DEBUG
          MOZ_ASSERT(contains(prevBump));
  
          // Clobber the now-free space.
          if (prevBump > bump)
              memset(bump, 0xcd, prevBump - bump);
  #endif
  
          // Poison/Unpoison memory that we just free'd/allocated.
  #if defined(MOZ_HAVE_MEM_CHECKS)
          if (prevBump > bump)
              MOZ_MAKE_MEM_NOACCESS(bump, prevBump - bump);
          else if (bump > prevBump)
              MOZ_MAKE_MEM_UNDEFINED(prevBump, bump - prevBump);
  #endif
      }
  
    public:
      BumpChunk* next() const { return next_; }
      void setNext(BumpChunk* succ) { next_ = succ; }
  
      size_t used() const { return bump - bumpBase(); }
  
      void* start() const { return bumpBase(); }
      void* end() const { return limit; }
  
      size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) {
          return mallocSizeOf(this);
      }
  
      size_t computedSizeOfIncludingThis() {
          return limit - headerBase();
      }
  
      void resetBump() {
          setBump(headerBase() + sizeof(BumpChunk));
      }
  
      void* mark() const { return bump; }
  
      void release(void* mark) {
          MOZ_ASSERT(contains(mark));
          MOZ_ASSERT(mark <= bump);
          setBump(mark);
      }
  
      bool contains(void* mark) const {
          return bumpBase() <= mark && mark <= limit;
      }
  
      bool canAlloc(size_t n);
  
      size_t unused() {
          return limit - AlignPtr(bump);
      }
  
      // Try to perform an allocation of size |n|, return null if not possible.
      MOZ_ALWAYS_INLINE
      void* tryAlloc(size_t n) {
          char* aligned = AlignPtr(bump);
          char* newBump = aligned + n;
  
          if (newBump > limit)
              return nullptr;
  
          // Check for overflow.
          if (MOZ_UNLIKELY(newBump < bump))
              return nullptr;
  
          MOZ_ASSERT(canAlloc(n)); // Ensure consistency between "can" and "try".
          setBump(newBump);
          return aligned;
      }
  
      static BumpChunk* new_(size_t chunkSize);
      static void delete_(BumpChunk* chunk);
  };
  
  } // namespace detail
  
  // LIFO bump allocator: used for phase-oriented and fast LIFO allocations.
  //
  // Note: |latest| is not necessary "last". We leave BumpChunks latent in the
  // chain after they've been released to avoid thrashing before a GC.
  class LifoAlloc
  {
      typedef detail::BumpChunk BumpChunk;
  
      BumpChunk*  first;
      BumpChunk*  latest;
      BumpChunk*  last;
      size_t      markCount;
      size_t      defaultChunkSize_;
      size_t      curSize_;
      size_t      peakSize_;
  
      void operator=(const LifoAlloc&) = delete;
      LifoAlloc(const LifoAlloc&) = delete;
  
      // Return a BumpChunk that can perform an allocation of at least size |n|
      // and add it to the chain appropriately.
      //
      // Side effect: if retval is non-null, |first| and |latest| are initialized
      // appropriately.
      BumpChunk* getOrCreateChunk(size_t n);
  
      void reset(size_t defaultChunkSize) {
          MOZ_ASSERT(mozilla::RoundUpPow2(defaultChunkSize) == defaultChunkSize);
          first = latest = last = nullptr;
          defaultChunkSize_ = defaultChunkSize;
          markCount = 0;
          curSize_ = 0;
      }
  
      // Append unused chunks to the end of this LifoAlloc.
      void appendUnused(BumpChunk* start, BumpChunk* end) {
          MOZ_ASSERT(start && end);
          if (last)
              last->setNext(start);
          else
              first = latest = start;
          last = end;
      }
  
      // Append used chunks to the end of this LifoAlloc. We act as if all the
      // chunks in |this| are used, even if they're not, so memory may be wasted.
      void appendUsed(BumpChunk* otherFirst, BumpChunk* otherLatest, BumpChunk* otherLast) {
          MOZ_ASSERT(otherFirst && otherLatest && otherLast);
          if (last)
              last->setNext(otherFirst);
          else
              first = otherFirst;
          latest = otherLatest;
          last = otherLast;
      }
  
      void incrementCurSize(size_t size) {
          curSize_ += size;
          if (curSize_ > peakSize_)
              peakSize_ = curSize_;
      }
      void decrementCurSize(size_t size) {
          MOZ_ASSERT(curSize_ >= size);
          curSize_ -= size;
      }
  
    public:
      explicit LifoAlloc(size_t defaultChunkSize)
        : peakSize_(0)
      {
          reset(defaultChunkSize);
      }
  
      // Steal allocated chunks from |other|.
      void steal(LifoAlloc* other) {
          MOZ_ASSERT(!other->markCount);
          MOZ_ASSERT(!latest);
  
          // Copy everything from |other| to |this| except for |peakSize_|, which
          // requires some care.
          size_t oldPeakSize = peakSize_;
          mozilla::PodAssign(this, other);
          peakSize_ = Max(oldPeakSize, curSize_);
  
          other->reset(defaultChunkSize_);
      }
  
      // Append all chunks from |other|. They are removed from |other|.
      void transferFrom(LifoAlloc* other);
  
      // Append unused chunks from |other|. They are removed from |other|.
      void transferUnusedFrom(LifoAlloc* other);
  
      ~LifoAlloc() { freeAll(); }
  
      size_t defaultChunkSize() const { return defaultChunkSize_; }
  
      // Frees all held memory.
      void freeAll();
  
      static const unsigned HUGE_ALLOCATION = 50 * 1024 * 1024;
      void freeAllIfHugeAndUnused() {
          if (markCount == 0 && curSize_ > HUGE_ALLOCATION)
              freeAll();
      }
  
      MOZ_ALWAYS_INLINE
      void* alloc(size_t n) {
          JS_OOM_POSSIBLY_FAIL();
  
          void* result;
          if (latest && (result = latest->tryAlloc(n)))
              return result;
  
          if (!getOrCreateChunk(n))
              return nullptr;
  
          // Since we just created a large enough chunk, this can't fail.
          result = latest->tryAlloc(n);
          MOZ_ASSERT(result);
          return result;
      }
  
      MOZ_ALWAYS_INLINE
      void* allocInfallible(size_t n) {
          if (void* result = alloc(n))
              return result;
          CrashAtUnhandlableOOM("LifoAlloc::allocInfallible");
          return nullptr;
      }
  
      // Ensures that enough space exists to satisfy N bytes worth of
      // allocation requests, not necessarily contiguous. Note that this does
      // not guarantee a successful single allocation of N bytes.
      MOZ_ALWAYS_INLINE
      bool ensureUnusedApproximate(size_t n) {
          size_t total = 0;
          for (BumpChunk* chunk = latest; chunk; chunk = chunk->next()) {
              total += chunk->unused();
              if (total >= n)
                  return true;
          }
          BumpChunk* latestBefore = latest;
          if (!getOrCreateChunk(n))
              return false;
          if (latestBefore)
              latest = latestBefore;
          return true;
      }
  
      template <typename T>
      T* newArray(size_t count) {
          static_assert(mozilla::IsPod<T>::value,
                        "T must be POD so that constructors (and destructors, "
                        "when the LifoAlloc is freed) need not be called");
          return newArrayUninitialized<T>(count);
      }
  
      // Create an array with uninitialized elements of type |T|.
      // The caller is responsible for initialization.
      template <typename T>
      T* newArrayUninitialized(size_t count) {
          size_t bytes;
          if (MOZ_UNLIKELY(!CalculateAllocSize<T>(count, &bytes)))
              return nullptr;
          return static_cast<T*>(alloc(bytes));
      }
  
      class Mark {
          BumpChunk* chunk;
          void* markInChunk;
          friend class LifoAlloc;
          Mark(BumpChunk* chunk, void* markInChunk) : chunk(chunk), markInChunk(markInChunk) {}
        public:
          Mark() : chunk(nullptr), markInChunk(nullptr) {}
      };
  
      Mark mark() {
          markCount++;
          return latest ? Mark(latest, latest->mark()) : Mark();
      }
  
      void release(Mark mark) {
          markCount--;
          if (!mark.chunk) {
              latest = first;
              if (latest)
                  latest->resetBump();
          } else {
              latest = mark.chunk;
              latest->release(mark.markInChunk);
          }
      }
  
      void releaseAll() {
          MOZ_ASSERT(!markCount);
          latest = first;
          if (latest)
              latest->resetBump();
      }
  
      // Get the total "used" (occupied bytes) count for the arena chunks.
      size_t used() const {
          size_t accum = 0;
          for (BumpChunk* chunk = first; chunk; chunk = chunk->next()) {
              accum += chunk->used();
              if (chunk == latest)
                  break;
          }
          return accum;
      }
  
      // Return true if the LifoAlloc does not currently contain any allocations.
      bool isEmpty() const {
          return !latest || !latest->used();
      }
  
      // Return the number of bytes remaining to allocate in the current chunk.
      // e.g. How many bytes we can allocate before needing a new block.
      size_t availableInCurrentChunk() const {
          if (!latest)
              return 0;
          return latest->unused();
      }
  
      // Get the total size of the arena chunks (including unused space).
      size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
          size_t n = 0;
          for (BumpChunk* chunk = first; chunk; chunk = chunk->next())
              n += chunk->sizeOfIncludingThis(mallocSizeOf);
          return n;
      }
  
      // Get the total size of the arena chunks (including unused space).
      size_t computedSizeOfExcludingThis() const {
          size_t n = 0;
          for (BumpChunk* chunk = first; chunk; chunk = chunk->next())
              n += chunk->computedSizeOfIncludingThis();
          return n;
      }
  
      // Like sizeOfExcludingThis(), but includes the size of the LifoAlloc itself.
      size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
          return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
      }
  
      // Get the peak size of the arena chunks (including unused space and
      // bookkeeping space).
      size_t peakSizeOfExcludingThis() const { return peakSize_; }
  
      // Doesn't perform construction; useful for lazily-initialized POD types.
      template <typename T>
      MOZ_ALWAYS_INLINE
      T* pod_malloc() {
          return static_cast<T*>(alloc(sizeof(T)));
      }
  
      JS_DECLARE_NEW_METHODS(new_, alloc, MOZ_ALWAYS_INLINE)
      JS_DECLARE_NEW_METHODS(newInfallible, allocInfallible, MOZ_ALWAYS_INLINE)
  
      // A mutable enumeration of the allocated data.
      class Enum
      {
          friend class LifoAlloc;
          friend class detail::BumpChunk;
  
          LifoAlloc* alloc_;  // The LifoAlloc being traversed.
          BumpChunk* chunk_;  // The current chunk.
          char* position_;    // The current position (must be within chunk_).
  
          // If there is not enough room in the remaining block for |size|,
          // advance to the next block and update the position.
          void ensureSpaceAndAlignment(size_t size) {
              MOZ_ASSERT(!empty());
              char* aligned = detail::AlignPtr(position_);
              if (aligned + size > chunk_->end()) {
                  chunk_ = chunk_->next();
                  position_ = static_cast<char*>(chunk_->start());
              } else {
                  position_ = aligned;
              }
              MOZ_ASSERT(uintptr_t(position_) + size <= uintptr_t(chunk_->end()));
          }
  
        public:
          explicit Enum(LifoAlloc& alloc)
            : alloc_(&alloc),
              chunk_(alloc.first),
              position_(static_cast<char*>(alloc.first ? alloc.first->start() : nullptr))
          {}
  
          // Return true if there are no more bytes to enumerate.
          bool empty() {
              return !chunk_ || (chunk_ == alloc_->latest && position_ >= chunk_->mark());
          }
  
          // Move the read position forward by the size of one T.
          template <typename T>
          void popFront() {
              popFront(sizeof(T));
          }
  
          // Move the read position forward by |size| bytes.
          void popFront(size_t size) {
              ensureSpaceAndAlignment(size);
              position_ = position_ + size;
          }
  
          // Update the bytes at the current position with a new value.
          template <typename T>
          void updateFront(const T& t) {
              ensureSpaceAndAlignment(sizeof(T));
              memmove(position_, &t, sizeof(T));
          }
  
          // Return a pointer to the item at the current position. This
          // returns a pointer to the inline storage, not a copy.
          template <typename T>
          T* get(size_t size = sizeof(T)) {
              ensureSpaceAndAlignment(size);
              return reinterpret_cast<T*>(position_);
          }
  
          // Return a Mark at the current position of the Enum.
          Mark mark() {
              alloc_->markCount++;
              return Mark(chunk_, position_);
          }
      };
  };
  
  class LifoAllocScope
  {
      LifoAlloc*      lifoAlloc;
      LifoAlloc::Mark mark;
      bool            shouldRelease;
      MOZ_DECL_USE_GUARD_OBJECT_NOTIFIER
  
    public:
      explicit LifoAllocScope(LifoAlloc* lifoAlloc
                              MOZ_GUARD_OBJECT_NOTIFIER_PARAM)
        : lifoAlloc(lifoAlloc),
          mark(lifoAlloc->mark()),
          shouldRelease(true)
      {
          MOZ_GUARD_OBJECT_NOTIFIER_INIT;
      }
  
      ~LifoAllocScope() {
          if (shouldRelease)
              lifoAlloc->release(mark);
      }
  
      LifoAlloc& alloc() {
          return *lifoAlloc;
      }
  
      void releaseEarly() {
          MOZ_ASSERT(shouldRelease);
          lifoAlloc->release(mark);
          shouldRelease = false;
      }
  };
  
  enum Fallibility {
      Fallible,
      Infallible
  };
  
  template <Fallibility fb>
  class LifoAllocPolicy
  {
      LifoAlloc& alloc_;
  
    public:
      MOZ_IMPLICIT LifoAllocPolicy(LifoAlloc& alloc)
        : alloc_(alloc)
      {}
      template <typename T>
      T* pod_malloc(size_t numElems) {
          size_t bytes;
          if (MOZ_UNLIKELY(!CalculateAllocSize<T>(numElems, &bytes)))
              return nullptr;
          void* p = fb == Fallible ? alloc_.alloc(bytes) : alloc_.allocInfallible(bytes);
          return static_cast<T*>(p);
      }
      template <typename T>
      T* pod_calloc(size_t numElems) {
          T* p = pod_malloc<T>(numElems);
          if (MOZ_UNLIKELY(!p))
              return nullptr;
          memset(p, 0, numElems * sizeof(T));
          return p;
      }
      template <typename T>
      T* pod_realloc(T* p, size_t oldSize, size_t newSize) {
          T* n = pod_malloc<T>(newSize);
          if (MOZ_UNLIKELY(!n))
              return nullptr;
          MOZ_ASSERT(!(oldSize & mozilla::tl::MulOverflowMask<sizeof(T)>::value));
          memcpy(n, p, Min(oldSize * sizeof(T), newSize * sizeof(T)));
          return n;
      }
      void free_(void* p) {
      }
      void reportAllocOverflow() const {
      }
  };
  
  } // namespace js
  
  #endif /* ds_LifoAlloc_h */
  