layout/base/StackArena.cpp

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