Line data Source code
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
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef mozilla_ArenaAllocator_h
8 : #define mozilla_ArenaAllocator_h
9 :
10 : #include <algorithm>
11 : #include <cstdint>
12 :
13 : #include "mozilla/fallible.h"
14 : #include "mozilla/Likely.h"
15 : #include "mozilla/MemoryChecking.h"
16 : #include "mozilla/MemoryReporting.h"
17 : #include "mozilla/OperatorNewExtensions.h"
18 : #include "mozilla/TemplateLib.h"
19 : #include "nsDebug.h"
20 :
21 : namespace mozilla {
22 :
23 : /**
24 : * A very simple arena allocator based on NSPR's PLArena.
25 : *
26 : * The arena allocator only provides for allocation, all memory is retained
27 : * until the allocator is destroyed. It's useful for situations where a large
28 : * amount of small transient allocations are expected.
29 : *
30 : * Example usage:
31 : *
32 : * // Define an allocator that is page sized and returns allocations that are
33 : * // 8-byte aligned.
34 : * ArenaAllocator<4096, 8> a;
35 : * for (int i = 0; i < 1000; i++) {
36 : * DoSomething(a.Allocate(i));
37 : * }
38 : */
39 : template<size_t ArenaSize, size_t Alignment=1>
40 : class ArenaAllocator
41 : {
42 : public:
43 229 : constexpr ArenaAllocator()
44 : : mHead()
45 229 : , mCurrent(nullptr)
46 : {
47 : static_assert(mozilla::tl::FloorLog2<Alignment>::value ==
48 : mozilla::tl::CeilingLog2<Alignment>::value,
49 : "ArenaAllocator alignment must be a power of two");
50 229 : }
51 :
52 : ArenaAllocator(const ArenaAllocator&) = delete;
53 : ArenaAllocator& operator=(const ArenaAllocator&) = delete;
54 :
55 : /**
56 : * Frees all internal arenas but does not call destructors for objects
57 : * allocated out of the arena.
58 : */
59 174 : ~ArenaAllocator()
60 : {
61 174 : Clear();
62 174 : }
63 :
64 : /**
65 : * Fallibly allocates a chunk of memory with the given size from the internal
66 : * arenas. If the allocation size is larger than the chosen arena a size an
67 : * entire arena is allocated and used.
68 : */
69 39590 : MOZ_ALWAYS_INLINE void* Allocate(size_t aSize, const fallible_t&)
70 : {
71 39590 : MOZ_RELEASE_ASSERT(aSize, "Allocation size must be non-zero");
72 39590 : return InternalAllocate(AlignedSize(aSize));
73 : }
74 :
75 12177 : void* Allocate(size_t aSize)
76 : {
77 12177 : void* p = Allocate(aSize, fallible);
78 12177 : if (MOZ_UNLIKELY(!p)) {
79 0 : NS_ABORT_OOM(std::max(aSize, ArenaSize));
80 : }
81 :
82 12177 : return p;
83 : }
84 :
85 : /**
86 : * Frees all entries. The allocator can be reused after this is called.
87 : *
88 : * NB: This will not run destructors of any objects that were allocated from
89 : * the arena.
90 : */
91 174 : void Clear()
92 : {
93 : // Free all chunks.
94 174 : auto a = mHead.next;
95 910 : while (a) {
96 368 : auto tmp = a;
97 368 : a = a->next;
98 368 : free(tmp);
99 : }
100 :
101 : // Reset the list head.
102 174 : mHead.next = nullptr;
103 174 : mCurrent = nullptr;
104 174 : }
105 :
106 : /**
107 : * Adjusts the given size to the required alignment.
108 : */
109 52198 : static constexpr size_t AlignedSize(size_t aSize)
110 : {
111 52198 : return (aSize + (Alignment - 1)) & ~(Alignment - 1);
112 : }
113 :
114 21 : size_t SizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
115 : {
116 21 : size_t s = 0;
117 42 : for (auto arena = mHead.next; arena; arena = arena->next) {
118 21 : s += aMallocSizeOf(arena);
119 : }
120 :
121 21 : return s;
122 : }
123 :
124 : private:
125 : struct ArenaHeader
126 : {
127 : /**
128 : * The location in memory of the data portion of the arena.
129 : */
130 : uintptr_t offset;
131 : /**
132 : * The location in memory of the end of the data portion of the arena.
133 : */
134 : uintptr_t tail;
135 : };
136 :
137 : struct ArenaChunk
138 : {
139 229 : constexpr ArenaChunk() : header{0, 0}, next(nullptr) {}
140 :
141 649 : explicit ArenaChunk(size_t aSize)
142 1298 : : header{AlignedSize(uintptr_t(this + 1)), uintptr_t(this) + aSize}
143 1298 : , next(nullptr)
144 : {
145 649 : }
146 :
147 : ArenaHeader header;
148 : ArenaChunk* next;
149 :
150 : /**
151 : * Allocates a chunk of memory out of the arena and advances the offset.
152 : */
153 39590 : void* Allocate(size_t aSize)
154 : {
155 39590 : MOZ_ASSERT(aSize <= Available());
156 39590 : char* p = reinterpret_cast<char*>(header.offset);
157 39590 : header.offset += aSize;
158 : MOZ_MAKE_MEM_UNDEFINED(p, aSize);
159 39590 : return p;
160 : }
161 :
162 : /**
163 : * Calculates the amount of space available for allocation in this chunk.
164 : */
165 78948 : size_t Available() const {
166 78948 : return header.tail - header.offset;
167 : }
168 : };
169 :
170 : /**
171 : * Allocates an arena chunk of the given size and initializes its header.
172 : */
173 649 : ArenaChunk* AllocateChunk(size_t aSize)
174 : {
175 : static const size_t kOffset = AlignedSize(sizeof(ArenaChunk));
176 649 : MOZ_ASSERT(kOffset < aSize);
177 :
178 649 : const size_t chunkSize = aSize + kOffset;
179 649 : void* p = malloc(chunkSize);
180 649 : if (!p) {
181 0 : return nullptr;
182 : }
183 :
184 649 : ArenaChunk* arena = new (KnownNotNull, p) ArenaChunk(chunkSize);
185 : MOZ_MAKE_MEM_NOACCESS((void*)arena->header.offset,
186 : arena->header.tail - arena->header.offset);
187 :
188 : // Insert into the head of the list.
189 649 : arena->next = mHead.next;
190 649 : mHead.next = arena;
191 :
192 : // Only update |mCurrent| if this is a standard allocation, large
193 : // allocations will always end up full so there's no point in updating
194 : // |mCurrent| in that case.
195 649 : if (aSize == ArenaSize - kOffset) {
196 649 : mCurrent = arena;
197 : }
198 :
199 649 : return arena;
200 : }
201 :
202 39590 : MOZ_ALWAYS_INLINE void* InternalAllocate(size_t aSize)
203 : {
204 : static_assert(ArenaSize > AlignedSize(sizeof(ArenaChunk)),
205 : "Arena size must be greater than the header size");
206 :
207 : static const size_t kMaxArenaCapacity =
208 : ArenaSize - AlignedSize(sizeof(ArenaChunk));
209 :
210 39590 : if (mCurrent && aSize <= mCurrent->Available()) {
211 38941 : return mCurrent->Allocate(aSize);
212 : }
213 :
214 649 : ArenaChunk* arena = AllocateChunk(std::max(kMaxArenaCapacity, aSize));
215 649 : return arena ? arena->Allocate(aSize) : nullptr;
216 : }
217 :
218 : ArenaChunk mHead;
219 : ArenaChunk* mCurrent;
220 : };
221 :
222 : } // namespace mozilla
223 :
224 : #endif // mozilla_ArenaAllocator_h
|
