summaryrefslogtreecommitdiffstats
path: root/xpcom/ds/ArenaAllocator.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--xpcom/ds/ArenaAllocator.h214
1 files changed, 214 insertions, 0 deletions
diff --git a/xpcom/ds/ArenaAllocator.h b/xpcom/ds/ArenaAllocator.h
new file mode 100644
index 0000000000..76498986ce
--- /dev/null
+++ b/xpcom/ds/ArenaAllocator.h
@@ -0,0 +1,214 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef mozilla_ArenaAllocator_h
+#define mozilla_ArenaAllocator_h
+
+#include <algorithm>
+#include <cstdint>
+
+#include "mozilla/Assertions.h"
+#include "mozilla/fallible.h"
+#include "mozilla/Likely.h"
+#include "mozilla/MemoryChecking.h"
+#include "mozilla/MemoryReporting.h"
+#include "mozilla/OperatorNewExtensions.h"
+#include "mozilla/Poison.h"
+#include "mozilla/TemplateLib.h"
+#include "nsDebug.h"
+
+namespace mozilla {
+
+/**
+ * A very simple arena allocator based on NSPR's PLArena.
+ *
+ * The arena allocator only provides for allocation, all memory is retained
+ * until the allocator is destroyed. It's useful for situations where a large
+ * amount of small transient allocations are expected.
+ *
+ * Example usage:
+ *
+ * // Define an allocator that is page sized and returns allocations that are
+ * // 8-byte aligned.
+ * ArenaAllocator<4096, 8> a;
+ * for (int i = 0; i < 1000; i++) {
+ * DoSomething(a.Allocate(i));
+ * }
+ */
+template <size_t ArenaSize, size_t Alignment = 1>
+class ArenaAllocator {
+ public:
+ constexpr ArenaAllocator() : mHead(), mCurrent(nullptr) {
+ static_assert(mozilla::tl::FloorLog2<Alignment>::value ==
+ mozilla::tl::CeilingLog2<Alignment>::value,
+ "ArenaAllocator alignment must be a power of two");
+ }
+
+ ArenaAllocator(const ArenaAllocator&) = delete;
+ ArenaAllocator& operator=(const ArenaAllocator&) = delete;
+
+ /**
+ * Frees all internal arenas but does not call destructors for objects
+ * allocated out of the arena.
+ */
+ ~ArenaAllocator() { Clear(); }
+
+ /**
+ * Fallibly allocates a chunk of memory with the given size from the internal
+ * arenas. If the allocation size is larger than the chosen arena a size an
+ * entire arena is allocated and used.
+ */
+ MOZ_ALWAYS_INLINE void* Allocate(size_t aSize, const fallible_t&) {
+ MOZ_RELEASE_ASSERT(aSize, "Allocation size must be non-zero");
+ return InternalAllocate(AlignedSize(aSize));
+ }
+
+ void* Allocate(size_t aSize) {
+ void* p = Allocate(aSize, fallible);
+ if (MOZ_UNLIKELY(!p)) {
+ NS_ABORT_OOM(std::max(aSize, ArenaSize));
+ }
+
+ return p;
+ }
+
+ /**
+ * Frees all entries. The allocator can be reused after this is called.
+ *
+ * NB: This will not run destructors of any objects that were allocated from
+ * the arena.
+ */
+ void Clear() {
+ // Free all chunks.
+ auto a = mHead.next;
+ while (a) {
+ auto tmp = a;
+ a = a->next;
+ free(tmp);
+ }
+
+ // Reset the list head.
+ mHead.next = nullptr;
+ mCurrent = nullptr;
+ }
+
+ /**
+ * Adjusts the given size to the required alignment.
+ */
+ static constexpr size_t AlignedSize(size_t aSize) {
+ return (aSize + (Alignment - 1)) & ~(Alignment - 1);
+ }
+
+ size_t SizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
+ size_t s = 0;
+ for (auto arena = mHead.next; arena; arena = arena->next) {
+ s += aMallocSizeOf(arena);
+ }
+
+ return s;
+ }
+
+ void Check() {
+ if (mCurrent) {
+ mCurrent->canary.Check();
+ }
+ }
+
+ private:
+ struct ArenaHeader {
+ /**
+ * The location in memory of the data portion of the arena.
+ */
+ uintptr_t offset;
+ /**
+ * The location in memory of the end of the data portion of the arena.
+ */
+ uintptr_t tail;
+ };
+
+ struct ArenaChunk {
+ constexpr ArenaChunk() : header{0, 0}, next(nullptr) {}
+
+ explicit ArenaChunk(size_t aSize)
+ : header{AlignedSize(uintptr_t(this + 1)), uintptr_t(this) + aSize},
+ next(nullptr) {}
+
+ CorruptionCanary canary;
+ ArenaHeader header;
+ ArenaChunk* next;
+
+ /**
+ * Allocates a chunk of memory out of the arena and advances the offset.
+ */
+ void* Allocate(size_t aSize) {
+ MOZ_ASSERT(aSize <= Available());
+ char* p = reinterpret_cast<char*>(header.offset);
+ MOZ_RELEASE_ASSERT(p);
+ header.offset += aSize;
+ canary.Check();
+ MOZ_MAKE_MEM_UNDEFINED(p, aSize);
+ return p;
+ }
+
+ /**
+ * Calculates the amount of space available for allocation in this chunk.
+ */
+ size_t Available() const { return header.tail - header.offset; }
+ };
+
+ /**
+ * Allocates an arena chunk of the given size and initializes its header.
+ */
+ ArenaChunk* AllocateChunk(size_t aSize) {
+ static const size_t kOffset = AlignedSize(sizeof(ArenaChunk));
+ MOZ_ASSERT(kOffset < aSize);
+
+ const size_t chunkSize = aSize + kOffset;
+ void* p = malloc(chunkSize);
+ if (!p) {
+ return nullptr;
+ }
+
+ ArenaChunk* arena = new (KnownNotNull, p) ArenaChunk(chunkSize);
+ MOZ_MAKE_MEM_NOACCESS((void*)arena->header.offset,
+ arena->header.tail - arena->header.offset);
+
+ // Insert into the head of the list.
+ arena->next = mHead.next;
+ mHead.next = arena;
+
+ // Only update |mCurrent| if this is a standard allocation, large
+ // allocations will always end up full so there's no point in updating
+ // |mCurrent| in that case.
+ if (aSize == ArenaSize - kOffset) {
+ mCurrent = arena;
+ }
+
+ return arena;
+ }
+
+ MOZ_ALWAYS_INLINE void* InternalAllocate(size_t aSize) {
+ static_assert(ArenaSize > AlignedSize(sizeof(ArenaChunk)),
+ "Arena size must be greater than the header size");
+
+ static const size_t kMaxArenaCapacity =
+ ArenaSize - AlignedSize(sizeof(ArenaChunk));
+
+ if (mCurrent && aSize <= mCurrent->Available()) {
+ return mCurrent->Allocate(aSize);
+ }
+
+ ArenaChunk* arena = AllocateChunk(std::max(kMaxArenaCapacity, aSize));
+ return arena ? arena->Allocate(aSize) : nullptr;
+ }
+
+ ArenaChunk mHead;
+ ArenaChunk* mCurrent;
+};
+
+} // namespace mozilla
+
+#endif // mozilla_ArenaAllocator_h