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