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 file,
michael@0:  * You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "StackArena.h"
michael@0: #include "nsAlgorithm.h"
michael@0: #include "nsDebug.h"
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: // A block of memory that the stack will chop up and hand out.
michael@0: struct StackBlock {
michael@0:   // Subtract sizeof(StackBlock*) to give space for the |mNext| field.
michael@0:   static const size_t MAX_USABLE_SIZE = 4096 - sizeof(StackBlock*);
michael@0: 
michael@0:   // A block of memory.
michael@0:   char mBlock[MAX_USABLE_SIZE];
michael@0: 
michael@0:   // Another block of memory that would only be created if our stack
michael@0:   // overflowed.
michael@0:   StackBlock* mNext;
michael@0: 
michael@0:   StackBlock() : mNext(nullptr) { }
michael@0:   ~StackBlock() { }
michael@0: };
michael@0: 
michael@0: static_assert(sizeof(StackBlock) == 4096, "StackBlock must be 4096 bytes");
michael@0: 
michael@0: // We hold an array of marks. A push pushes a mark on the stack.
michael@0: // A pop pops it off.
michael@0: struct StackMark {
michael@0:   // The block of memory from which we are currently handing out chunks.
michael@0:   StackBlock* mBlock;
michael@0: 
michael@0:   // Our current position in the block.
michael@0:   size_t mPos;
michael@0: };
michael@0: 
michael@0: StackArena* AutoStackArena::gStackArena;
michael@0: 
michael@0: StackArena::StackArena()
michael@0: {
michael@0:   mMarkLength = 0;
michael@0:   mMarks = nullptr;
michael@0: 
michael@0:   // Allocate our stack memory.
michael@0:   mBlocks = new StackBlock();
michael@0:   mCurBlock = mBlocks;
michael@0: 
michael@0:   mStackTop = 0;
michael@0:   mPos = 0;
michael@0: }
michael@0: 
michael@0: StackArena::~StackArena()
michael@0: {
michael@0:   // Free up our data.
michael@0:   delete [] mMarks;
michael@0:   while (mBlocks) {
michael@0:     StackBlock* toDelete = mBlocks;
michael@0:     mBlocks = mBlocks->mNext;
michael@0:     delete toDelete;
michael@0:   }
michael@0: }
michael@0: 
michael@0: size_t
michael@0: StackArena::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
michael@0: {
michael@0:   size_t n = 0;
michael@0:   StackBlock *block = mBlocks;
michael@0:   while (block) {
michael@0:     n += aMallocSizeOf(block);
michael@0:     block = block->mNext;
michael@0:   }
michael@0:   n += aMallocSizeOf(mMarks);
michael@0:   return n;
michael@0: }
michael@0: 
michael@0: static const int STACK_ARENA_MARK_INCREMENT = 50;
michael@0: 
michael@0: void
michael@0: StackArena::Push()
michael@0: {
michael@0:   // Resize the mark array if we overrun it.  Failure to allocate the
michael@0:   // mark array is not fatal; we just won't free to that mark.  This
michael@0:   // allows callers not to worry about error checking.
michael@0:   if (mStackTop >= mMarkLength) {
michael@0:     uint32_t newLength = mStackTop + STACK_ARENA_MARK_INCREMENT;
michael@0:     StackMark* newMarks = new StackMark[newLength];
michael@0:     if (newMarks) {
michael@0:       if (mMarkLength) {
michael@0:         memcpy(newMarks, mMarks, sizeof(StackMark)*mMarkLength);
michael@0:       }
michael@0:       // Fill in any marks that we couldn't allocate during a prior call
michael@0:       // to Push().
michael@0:       for (; mMarkLength < mStackTop; ++mMarkLength) {
michael@0:         NS_NOTREACHED("should only hit this on out-of-memory");
michael@0:         newMarks[mMarkLength].mBlock = mCurBlock;
michael@0:         newMarks[mMarkLength].mPos = mPos;
michael@0:       }
michael@0:       delete [] mMarks;
michael@0:       mMarks = newMarks;
michael@0:       mMarkLength = newLength;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Set a mark at the top (if we can).
michael@0:   NS_ASSERTION(mStackTop < mMarkLength, "out of memory");
michael@0:   if (mStackTop < mMarkLength) {
michael@0:     mMarks[mStackTop].mBlock = mCurBlock;
michael@0:     mMarks[mStackTop].mPos = mPos;
michael@0:   }
michael@0: 
michael@0:   mStackTop++;
michael@0: }
michael@0: 
michael@0: void*
michael@0: StackArena::Allocate(size_t aSize)
michael@0: {
michael@0:   NS_ASSERTION(mStackTop > 0, "Allocate called without Push");
michael@0: 
michael@0:   // Align to a multiple of 8.
michael@0:   aSize = NS_ROUNDUP<size_t>(aSize, 8);
michael@0: 
michael@0:   // On stack overflow, grab another block.
michael@0:   if (mPos + aSize >= StackBlock::MAX_USABLE_SIZE) {
michael@0:     NS_ASSERTION(aSize <= StackBlock::MAX_USABLE_SIZE,
michael@0:                  "Requested memory is greater that our block size!!");
michael@0:     if (mCurBlock->mNext == nullptr) {
michael@0:       mCurBlock->mNext = new StackBlock();
michael@0:     }
michael@0: 
michael@0:     mCurBlock = mCurBlock->mNext;
michael@0:     mPos = 0;
michael@0:   }
michael@0: 
michael@0:   // Return the chunk they need.
michael@0:   void *result = mCurBlock->mBlock + mPos;
michael@0:   mPos += aSize;
michael@0: 
michael@0:   return result;
michael@0: }
michael@0: 
michael@0: void
michael@0: StackArena::Pop()
michael@0: {
michael@0:   // Pop off the mark.
michael@0:   NS_ASSERTION(mStackTop > 0, "unmatched pop");
michael@0:   mStackTop--;
michael@0: 
michael@0:   if (mStackTop >= mMarkLength) {
michael@0:     // We couldn't allocate the marks array at the time of the push, so
michael@0:     // we don't know where we're freeing to.
michael@0:     NS_NOTREACHED("out of memory");
michael@0:     if (mStackTop == 0) {
michael@0:       // But we do know if we've completely pushed the stack.
michael@0:       mCurBlock = mBlocks;
michael@0:       mPos = 0;
michael@0:     }
michael@0:     return;
michael@0:   }
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   // Mark the "freed" memory with 0xdd to help with debugging of memory
michael@0:   // allocation problems.
michael@0:   {
michael@0:     StackBlock *block = mMarks[mStackTop].mBlock, *block_end = mCurBlock;
michael@0:     size_t pos = mMarks[mStackTop].mPos;
michael@0:     for (; block != block_end; block = block->mNext, pos = 0) {
michael@0:       memset(block->mBlock + pos, 0xdd, sizeof(block->mBlock) - pos);
michael@0:     }
michael@0:     memset(block->mBlock + pos, 0xdd, mPos - pos);
michael@0:   }
michael@0: #endif
michael@0: 
michael@0:   mCurBlock = mMarks[mStackTop].mBlock;
michael@0:   mPos      = mMarks[mStackTop].mPos;
michael@0: }
michael@0: 
michael@0: } // namespace mozilla