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.

Mercurial (39c1aeb25240)

VCS Links

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
/* -*- 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_recordreplay_ChunkAllocator_h
#define mozilla_recordreplay_ChunkAllocator_h

#include "SpinLock.h"

namespace mozilla {
namespace recordreplay {

// ChunkAllocator is a simple allocator class for creating objects which can be
// fetched by their integer id. Objects are stored as a linked list of arrays;
// like a linked list, existing entries can be accessed without taking or
// holding a lock, and using an array in each element mitigates the runtime
// cost of O(n) lookup.
//
// ChunkAllocator contents are never destroyed.
template <typename T>
class ChunkAllocator {
  struct Chunk;
  typedef Atomic<Chunk*, SequentiallyConsistent, Behavior::DontPreserve>
      ChunkPointer;

  // A page sized block holding a next pointer and an array of as many things
  // as possible.
  struct Chunk {
    uint8_t mStorage[PageSize - sizeof(Chunk*)];
    ChunkPointer mNext;
    Chunk() : mStorage{}, mNext(nullptr) {}

    static size_t MaxThings() { return sizeof(mStorage) / sizeof(T); }

    T* GetThing(size_t i) {
      MOZ_RELEASE_ASSERT(i < MaxThings());
      return reinterpret_cast<T*>(&mStorage[i * sizeof(T)]);
    }
  };

  ChunkPointer mFirstChunk;
  Atomic<size_t, SequentiallyConsistent, Behavior::DontPreserve> mCapacity;
  SpinLock mLock;

  void EnsureChunk(ChunkPointer* aChunk) {
    if (!*aChunk) {
      *aChunk = new Chunk();
      mCapacity += Chunk::MaxThings();
    }
  }

  ChunkAllocator(const ChunkAllocator&) = delete;
  ChunkAllocator& operator=(const ChunkAllocator&) = delete;

 public:
  // ChunkAllocators are allocated in static storage and should not have
  // constructors. Their memory will be initially zero.
  ChunkAllocator() = default;
  ~ChunkAllocator() = default;

  // Get an existing entry from the allocator.
  inline T* Get(size_t aId) {
    Chunk* chunk = mFirstChunk;
    while (aId >= Chunk::MaxThings()) {
      aId -= Chunk::MaxThings();
      chunk = chunk->mNext;
    }
    return chunk->GetThing(aId);
  }

  // Get an existing entry from the allocator, or null. This may return an
  // entry that has not been created yet.
  inline T* MaybeGet(size_t aId) {
    return (aId < mCapacity) ? Get(aId) : nullptr;
  }

  // Create a new entry with the specified ID. This must not be called on IDs
  // that have already been used with this allocator.
  inline T* Create(size_t aId) {
    if (aId < mCapacity) {
      T* res = Get(aId);
      return new (res) T();
    }

    AutoSpinLock lock(mLock);
    ChunkPointer* pchunk = &mFirstChunk;
    while (aId >= Chunk::MaxThings()) {
      aId -= Chunk::MaxThings();
      EnsureChunk(pchunk);
      Chunk* chunk = *pchunk;
      pchunk = &chunk->mNext;
    }
    EnsureChunk(pchunk);
    Chunk* chunk = *pchunk;
    T* res = chunk->GetThing(aId);
    return new (res) T();
  }
};

}  // namespace recordreplay
}  // namespace mozilla

#endif  // mozilla_recordreplay_ChunkAllocator_h