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
StackBlockmozilla::StackBlock25 StackBlock() : mNext(nullptr) {}
~StackBlockmozilla::StackBlock26 ~StackBlock() {}
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
StackArena()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
~StackArena()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
SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const65 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
Push()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 NS_NOTREACHED("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
Allocate(size_t aSize)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
Pop()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 NS_NOTREACHED("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
173