1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/layout/base/StackArena.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,179 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this file,
1.6 + * You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +#include "StackArena.h"
1.9 +#include "nsAlgorithm.h"
1.10 +#include "nsDebug.h"
1.11 +
1.12 +namespace mozilla {
1.13 +
1.14 +// A block of memory that the stack will chop up and hand out.
1.15 +struct StackBlock {
1.16 + // Subtract sizeof(StackBlock*) to give space for the |mNext| field.
1.17 + static const size_t MAX_USABLE_SIZE = 4096 - sizeof(StackBlock*);
1.18 +
1.19 + // A block of memory.
1.20 + char mBlock[MAX_USABLE_SIZE];
1.21 +
1.22 + // Another block of memory that would only be created if our stack
1.23 + // overflowed.
1.24 + StackBlock* mNext;
1.25 +
1.26 + StackBlock() : mNext(nullptr) { }
1.27 + ~StackBlock() { }
1.28 +};
1.29 +
1.30 +static_assert(sizeof(StackBlock) == 4096, "StackBlock must be 4096 bytes");
1.31 +
1.32 +// We hold an array of marks. A push pushes a mark on the stack.
1.33 +// A pop pops it off.
1.34 +struct StackMark {
1.35 + // The block of memory from which we are currently handing out chunks.
1.36 + StackBlock* mBlock;
1.37 +
1.38 + // Our current position in the block.
1.39 + size_t mPos;
1.40 +};
1.41 +
1.42 +StackArena* AutoStackArena::gStackArena;
1.43 +
1.44 +StackArena::StackArena()
1.45 +{
1.46 + mMarkLength = 0;
1.47 + mMarks = nullptr;
1.48 +
1.49 + // Allocate our stack memory.
1.50 + mBlocks = new StackBlock();
1.51 + mCurBlock = mBlocks;
1.52 +
1.53 + mStackTop = 0;
1.54 + mPos = 0;
1.55 +}
1.56 +
1.57 +StackArena::~StackArena()
1.58 +{
1.59 + // Free up our data.
1.60 + delete [] mMarks;
1.61 + while (mBlocks) {
1.62 + StackBlock* toDelete = mBlocks;
1.63 + mBlocks = mBlocks->mNext;
1.64 + delete toDelete;
1.65 + }
1.66 +}
1.67 +
1.68 +size_t
1.69 +StackArena::SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
1.70 +{
1.71 + size_t n = 0;
1.72 + StackBlock *block = mBlocks;
1.73 + while (block) {
1.74 + n += aMallocSizeOf(block);
1.75 + block = block->mNext;
1.76 + }
1.77 + n += aMallocSizeOf(mMarks);
1.78 + return n;
1.79 +}
1.80 +
1.81 +static const int STACK_ARENA_MARK_INCREMENT = 50;
1.82 +
1.83 +void
1.84 +StackArena::Push()
1.85 +{
1.86 + // Resize the mark array if we overrun it. Failure to allocate the
1.87 + // mark array is not fatal; we just won't free to that mark. This
1.88 + // allows callers not to worry about error checking.
1.89 + if (mStackTop >= mMarkLength) {
1.90 + uint32_t newLength = mStackTop + STACK_ARENA_MARK_INCREMENT;
1.91 + StackMark* newMarks = new StackMark[newLength];
1.92 + if (newMarks) {
1.93 + if (mMarkLength) {
1.94 + memcpy(newMarks, mMarks, sizeof(StackMark)*mMarkLength);
1.95 + }
1.96 + // Fill in any marks that we couldn't allocate during a prior call
1.97 + // to Push().
1.98 + for (; mMarkLength < mStackTop; ++mMarkLength) {
1.99 + NS_NOTREACHED("should only hit this on out-of-memory");
1.100 + newMarks[mMarkLength].mBlock = mCurBlock;
1.101 + newMarks[mMarkLength].mPos = mPos;
1.102 + }
1.103 + delete [] mMarks;
1.104 + mMarks = newMarks;
1.105 + mMarkLength = newLength;
1.106 + }
1.107 + }
1.108 +
1.109 + // Set a mark at the top (if we can).
1.110 + NS_ASSERTION(mStackTop < mMarkLength, "out of memory");
1.111 + if (mStackTop < mMarkLength) {
1.112 + mMarks[mStackTop].mBlock = mCurBlock;
1.113 + mMarks[mStackTop].mPos = mPos;
1.114 + }
1.115 +
1.116 + mStackTop++;
1.117 +}
1.118 +
1.119 +void*
1.120 +StackArena::Allocate(size_t aSize)
1.121 +{
1.122 + NS_ASSERTION(mStackTop > 0, "Allocate called without Push");
1.123 +
1.124 + // Align to a multiple of 8.
1.125 + aSize = NS_ROUNDUP<size_t>(aSize, 8);
1.126 +
1.127 + // On stack overflow, grab another block.
1.128 + if (mPos + aSize >= StackBlock::MAX_USABLE_SIZE) {
1.129 + NS_ASSERTION(aSize <= StackBlock::MAX_USABLE_SIZE,
1.130 + "Requested memory is greater that our block size!!");
1.131 + if (mCurBlock->mNext == nullptr) {
1.132 + mCurBlock->mNext = new StackBlock();
1.133 + }
1.134 +
1.135 + mCurBlock = mCurBlock->mNext;
1.136 + mPos = 0;
1.137 + }
1.138 +
1.139 + // Return the chunk they need.
1.140 + void *result = mCurBlock->mBlock + mPos;
1.141 + mPos += aSize;
1.142 +
1.143 + return result;
1.144 +}
1.145 +
1.146 +void
1.147 +StackArena::Pop()
1.148 +{
1.149 + // Pop off the mark.
1.150 + NS_ASSERTION(mStackTop > 0, "unmatched pop");
1.151 + mStackTop--;
1.152 +
1.153 + if (mStackTop >= mMarkLength) {
1.154 + // We couldn't allocate the marks array at the time of the push, so
1.155 + // we don't know where we're freeing to.
1.156 + NS_NOTREACHED("out of memory");
1.157 + if (mStackTop == 0) {
1.158 + // But we do know if we've completely pushed the stack.
1.159 + mCurBlock = mBlocks;
1.160 + mPos = 0;
1.161 + }
1.162 + return;
1.163 + }
1.164 +
1.165 +#ifdef DEBUG
1.166 + // Mark the "freed" memory with 0xdd to help with debugging of memory
1.167 + // allocation problems.
1.168 + {
1.169 + StackBlock *block = mMarks[mStackTop].mBlock, *block_end = mCurBlock;
1.170 + size_t pos = mMarks[mStackTop].mPos;
1.171 + for (; block != block_end; block = block->mNext, pos = 0) {
1.172 + memset(block->mBlock + pos, 0xdd, sizeof(block->mBlock) - pos);
1.173 + }
1.174 + memset(block->mBlock + pos, 0xdd, mPos - pos);
1.175 + }
1.176 +#endif
1.177 +
1.178 + mCurBlock = mMarks[mStackTop].mBlock;
1.179 + mPos = mMarks[mStackTop].mPos;
1.180 +}
1.181 +
1.182 +} // namespace mozilla
