layout/base/StackArena.cpp

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
   3  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 #include "StackArena.h"
   6 #include "nsAlgorithm.h"
   7 #include "nsDebug.h"
   8
   9 namespace mozilla {
  10
  11 // A block of memory that the stack will chop up and hand out.
  12 struct StackBlock {
  13   // Subtract sizeof(StackBlock*) to give space for the |mNext| field.
  14   static const size_t MAX_USABLE_SIZE = 4096 - sizeof(StackBlock*);
  15
  16   // A block of memory.
  17   char mBlock[MAX_USABLE_SIZE];
  18
  19   // Another block of memory that would only be created if our stack
  20   // overflowed.
  21   StackBlock* mNext;
  22
  23   StackBlock() : mNext(nullptr) { }
  24   ~StackBlock() { }
  25 };
  26
  27 static_assert(sizeof(StackBlock) == 4096, "StackBlock must be 4096 bytes");
  28
  29 // We hold an array of marks. A push pushes a mark on the stack.
  30 // A pop pops it off.
  31 struct StackMark {
  32   // The block of memory from which we are currently handing out chunks.
  33   StackBlock* mBlock;
  34
  35   // Our current position in the block.
  36   size_t mPos;
  37 };
  38
  39 StackArena* AutoStackArena::gStackArena;
  40
  41 StackArena::StackArena()
  42 {
  43   mMarkLength = 0;
  44   mMarks = nullptr;
  45
  46   // Allocate our stack memory.
  47   mBlocks = new StackBlock();
  48   mCurBlock = mBlocks;
  49
  50   mStackTop = 0;
  51   mPos = 0;
  52 }
  53
  54 StackArena::~StackArena()
  55 {
  56   // Free up our data.
  57   delete [] mMarks;
  58   while (mBlocks) {
  59     StackBlock* toDelete = mBlocks;
  60     mBlocks = mBlocks->mNext;
  61     delete toDelete;
  62   }
  63 }
  64
  65 size_t
  66 StackArena::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
  67 {
  68   size_t n = 0;
  69   StackBlock *block = mBlocks;
  70   while (block) {
  71     n += aMallocSizeOf(block);
  72     block = block->mNext;
  73   }
  74   n += aMallocSizeOf(mMarks);
  75   return n;
  76 }
  77
  78 static const int STACK_ARENA_MARK_INCREMENT = 50;
  79
  80 void
  81 StackArena::Push()
  82 {
  83   // Resize the mark array if we overrun it.  Failure to allocate the
  84   // mark array is not fatal; we just won't free to that mark.  This
  85   // allows callers not to worry about error checking.
  86   if (mStackTop >= mMarkLength) {
  87     uint32_t newLength = mStackTop + STACK_ARENA_MARK_INCREMENT;
  88     StackMark* newMarks = new StackMark[newLength];
  89     if (newMarks) {
  90       if (mMarkLength) {
  91         memcpy(newMarks, mMarks, sizeof(StackMark)*mMarkLength);
  92       }
  93       // Fill in any marks that we couldn't allocate during a prior call
  94       // to Push().
  95       for (; mMarkLength < mStackTop; ++mMarkLength) {
  96         NS_NOTREACHED("should only hit this on out-of-memory");
  97         newMarks[mMarkLength].mBlock = mCurBlock;
  98         newMarks[mMarkLength].mPos = mPos;
  99       }
 100       delete [] mMarks;
 101       mMarks = newMarks;
 102       mMarkLength = newLength;
 103     }
 104   }
 105
 106   // Set a mark at the top (if we can).
 107   NS_ASSERTION(mStackTop < mMarkLength, "out of memory");
 108   if (mStackTop < mMarkLength) {
 109     mMarks[mStackTop].mBlock = mCurBlock;
 110     mMarks[mStackTop].mPos = mPos;
 111   }
 112
 113   mStackTop++;
 114 }
 115
 116 void*
 117 StackArena::Allocate(size_t aSize)
 118 {
 119   NS_ASSERTION(mStackTop > 0, "Allocate called without Push");
 120
 121   // Align to a multiple of 8.
 122   aSize = NS_ROUNDUP<size_t>(aSize, 8);
 123
 124   // On stack overflow, grab another block.
 125   if (mPos + aSize >= StackBlock::MAX_USABLE_SIZE) {
 126     NS_ASSERTION(aSize <= StackBlock::MAX_USABLE_SIZE,
 127                  "Requested memory is greater that our block size!!");
 128     if (mCurBlock->mNext == nullptr) {
 129       mCurBlock->mNext = new StackBlock();
 130     }
 131
 132     mCurBlock = mCurBlock->mNext;
 133     mPos = 0;
 134   }
 135
 136   // Return the chunk they need.
 137   void *result = mCurBlock->mBlock + mPos;
 138   mPos += aSize;
 139
 140   return result;
 141 }
 142
 143 void
 144 StackArena::Pop()
 145 {
 146   // Pop off the mark.
 147   NS_ASSERTION(mStackTop > 0, "unmatched pop");
 148   mStackTop--;
 149
 150   if (mStackTop >= mMarkLength) {
 151     // We couldn't allocate the marks array at the time of the push, so
 152     // we don't know where we're freeing to.
 153     NS_NOTREACHED("out of memory");
 154     if (mStackTop == 0) {
 155       // But we do know if we've completely pushed the stack.
 156       mCurBlock = mBlocks;
 157       mPos = 0;
 158     }
 159     return;
 160   }
 161
 162 #ifdef DEBUG
 163   // Mark the "freed" memory with 0xdd to help with debugging of memory
 164   // allocation problems.
 165   {
 166     StackBlock *block = mMarks[mStackTop].mBlock, *block_end = mCurBlock;
 167     size_t pos = mMarks[mStackTop].mPos;
 168     for (; block != block_end; block = block->mNext, pos = 0) {
 169       memset(block->mBlock + pos, 0xdd, sizeof(block->mBlock) - pos);
 170     }
 171     memset(block->mBlock + pos, 0xdd, mPos - pos);
 172   }
 173 #endif
 174
 175   mCurBlock = mMarks[mStackTop].mBlock;
 176   mPos      = mMarks[mStackTop].mPos;
 177 }
 178
 179 } // namespace mozilla