DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215
/* -*- 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 <sstream>

#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