Quelle  BufferAllocator.h   Sprache: C

/* -*- 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/. */

// GC-internal header file for the buffer allocator.

#ifndef gc_BufferAllocator_h
#define gc_BufferAllocator_h

#include "mozilla/Array.h"
#include "mozilla/Atomics.h"
#include "mozilla/BitSet.h"
#include "mozilla/Maybe.h"
#include "mozilla/TimeStamp.h"

#include <cstdint>
#include <stddef.h>
#include <utility>

#include "jstypes.h"  // JS_PUBLIC_API

#include "ds/SlimLinkedList.h"
#include "js/HeapAPI.h"
#include "threading/LockGuard.h"
#include "threading/Mutex.h"
#include "threading/ProtectedData.h"

class JS_PUBLIC_API JSTracer;

namespace JS {
class JS_PUBLIC_API Zone;
}  // namespace JS

namespace js {

class GCMarker;
class Nursery;

namespace gc {

enum class AllocKind : uint8_t;

struct BufferChunk;
struct Cell;
class GCRuntime;
struct MediumBuffer;
struct LargeBuffer;

// BufferAllocator allocates dynamically sized blocks of memory which can be
// reclaimed by the garbage collector and are associated with GC things.
//
// Although these blocks can be reclaimed by GC, explicit free and resize is
// also supported. This is important for buffers that can grow or shrink.
//
// The allocator uses a different strategy depending on the size of the
// allocation requested. There are three size ranges, divided as follows:
//
//   Size:            Kind:   Allocator implementation:
//    16 B  - 128 B   Small   Uses the cell (arena) allocator
//   256 B  - 512 KB  Medium  Uses a free list allocator
//     1 MB -         Large   Uses the OS page allocator (e.g. mmap)
//
// The smallest supported allocation size is 16 bytes. This will be used for a
// dynamic slots allocation with zero slots to set a unique ID on a native
// object. This will be the size of two Values, i.e. 16 bytes.
//
// Supported operations
// --------------------
//
//  - Allocate a buffer. Buffers are always owned by a GC cell, and the
//    allocator tracks whether the owner is in the nursery or the tenured heap.
//
//  - Trace an edge to buffer. When the owning cell is traced it must trace the
//    edge to the buffer. This will mark the buffer in a GC and prevent it from
//    being swept.
//
//  - Free a buffer. This allows uniquely owned buffers to be freed and reused
//    without waiting for the next GC. It is a hint only and is not supported
//    for all buffer kinds.
//
//  - Reallocate a buffer. This allows uniquely owned buffers to be resized,
//    possibly in-place. This is important for performance on some benchmarks.
//
// Integration with the rest of the GC
// -----------------------------------
//
// The GC calls the allocator at several points during minor and major GC (at
// the start, when sweeping starts and at the end). Allocations are swept on a
// background thread and the memory used by unmarked allocations is reclaimed.
//
// The allocator tries hard to avoid locking, and where it is necessary tries to
// minimize the time spent holding locks. A lock is required to allocate a chunk
// but after that no locks are required to allocate on the main thread, even
// when off-thread sweeping is taking place. This is achieved by moving data to
// be swept to separate containers from those used for allocation on the main
// thread. Synchronization is required to merge data about swept allocations at
// the end of sweeping.
//
// Small allocations
// -----------------
//
// These are implemented by the cell allocator and are allocated in arenas (slab
// allocation).
//
// Note: currently we do not allocate these in the nursery because nursery-owned
// buffers are allocated directly in the nursery without going through this
// allocation API.
//
// Medium allocations
// ------------------
//
// These are allocated in their own zone-specific chunks using a segregated free
// list strategy. This is the main part of the allocator.
//
// The requested allocation size is used to pick a size class, which is used to
// index into an array giving a list of free regions of suitable size. The first
// region in the list is used and its start address updated; it may also be
// moved to a different list if it is now empty or too small to satisfy further
// allocations for this size class. A bitmap in the chunk header is used to
// track the start offsets of allocations.
//
// Sweeping works by processing a list of chunks, scanning each one for
// allocated but unmarked buffers and rebuilding the free region data for that
// chunk. Sweeping happens separately for minor and major GC and only
// nursery-owned or tenured-owned buffers are swept at one time. This means that
// chunks containing nursery-owned allocations are swept twice during a major
// GC, once to sweep nursery-owned allocations and once for tenured-owned
// allocations. This is required because the sweeping happens at different
// times.
//
// Chunks containing nursery-owned buffers are stored in a separate list to
// chunks that only contain tenured-owned buffers to reduce the number of chunks
// that need to be swept for minor GC. They are stored in |mediumMixedChunks|
// and are moved to |mediumMixedChunksToSweep| at the start of minor GC. They
// are then swept on a background thread and are placed in
// |sweptMediumMixedChunks| if they are not freed. From there they can merged
// back into one of the main thread lists (since they may no longer contain
// nursery-owned buffers).
//
// Chunks containing tenured-owned buffers are stored in |mediumTenuredChunks|
// and are moved to |mediumTenuredChunksToSweep| at the start of major GC. They
// are unavailable for allocation after this point and will be swept on a
// background thread and placed in |sweptMediumTenuredChunks| if they are not
// freed. From there they will be merged back into |mediumTenuredChunks|. This
// means that allocation during an incremental GC will allocate a new
// chunk.
//
// Merging swept data requires taking a lock and so only happens when
// necessary. This happens when a new chunk is needed or at various points
// during GC. During sweeping no additional synchronization is required for
// allocation.
//
// Since major GC requires doing a minor GC at the start and we don't want to
// have to wait for minor GC sweeping to finish there is an optimization where
// chunks containing nursery-owned buffers swept as part of minor GC at the
// start of a major GC are moved directly from |sweptMediumMixedChunks| to
// |mediumTenuredChunksToSweep| at the end of minor GC sweeping. This is
// controlled by the |majorStartedWhileMinorSweeping| flag.
//
// Similarly, if a major GC finishes while minor GC is sweeping then rather than
// waiting for it to finish we set the |majorFinishedWhileMinorSweeping| flag so
// that we clear the |allocatedDuringCollection| for these chunks the end of the
// minor sweeping.
//
// Free works by extending neighboring free regions to cover the freed
// allocation or adding a new one if necessary. Free regions are found by
// checking the allocated bitmap. Free is not supported if the containing chunk
// is currently being swept off-thread.
//
// Reallocation works by resizing in place if possible. It is always possible to
// shrink a medium allocation in place if the target size is still
// medium. In-place growth is possible if there is enough free space following
// the allocation. This is not supported if the containing chunk is currently
// being swept off-thread.  If not possible, a new allocation is made and the
// contents of the buffer copied.
//
// Large allocations
// -----------------
//
// These are implemented using the OS page allocator. Allocations of this size
// are relatively rare and not much attempt is made to optimize them. They are
// stored with a chunk header at the front to allow them to be distinguished
// from the other allocation kinds easily.
//

class BufferAllocator : public SlimLinkedListElement<BufferAllocator> {
 public:
  static constexpr size_t MinMediumAllocShift = 8;   // 256 B
  static constexpr size_t MaxMediumAllocShift = 19;  // 512 KB

  static constexpr size_t MediumAllocClasses =
      MaxMediumAllocShift - MinMediumAllocShift + 1;

  // An RAII guard to lock and unlock the buffer allocator lock.
  class AutoLock : public LockGuard<Mutex> {
   public:
    explicit AutoLock(GCRuntime* gc);
    explicit AutoLock(BufferAllocator* allocator);
  };

  // A lock guard that is locked only when needed.
  using MaybeLock = mozilla::Maybe<AutoLock>;

 private:
  using BufferChunkList = SlimLinkedList<BufferChunk>;

  struct FreeRegion;
  using FreeList = SlimLinkedList<FreeRegion>;

  // Segregated free list: an array of free lists, one per size class.
  class FreeLists {
    using FreeListArray = mozilla::Array<FreeList, MediumAllocClasses>;
    FreeListArray lists;
    mozilla::BitSet<MediumAllocClasses, uint32_t> available;

   public:
    FreeLists() = default;

    FreeLists(FreeLists&& other);
    FreeLists& operator=(FreeLists&& other);

    using const_iterator = FreeListArray::const_iterator;
    auto begin() const { return lists.begin(); }
    auto end() const { return lists.end(); }

    // Returns SIZE_MAX if none available.
    size_t getFirstAvailableSizeClass(size_t minSizeClass) const;

    FreeRegion* getFirstRegion(size_t sizeClass);

    void pushFront(size_t sizeClass, FreeRegion* region);
    void pushBack(size_t sizeClass, FreeRegion* region);

    void append(FreeLists&& other);
    void prepend(FreeLists&& other);

    void remove(size_t sizeClass, FreeRegion* region);

    void clear();

    template <typename Pred>
    void eraseIf(Pred&& pred);

    void assertEmpty() const;
    void assertContains(size_t sizeClass, FreeRegion* region) const;
    void checkAvailable() const;
  };

  using LargeAllocList = SlimLinkedList<LargeBuffer>;

  enum class State : uint8_t { NotCollecting, Marking, Sweeping };

  enum class OwnerKind : uint8_t { Tenured = 0, Nursery, None };

  // The zone this allocator is associated with.
  MainThreadOrGCTaskData<JS::Zone*> zone;

  // Chunks that contain medium buffers. May contain both nursery-owned and
  // tenured-owned buffers.
  MainThreadData<BufferChunkList> mediumMixedChunks;

  // Chunks that contain only tenured-owned medium sized buffers.
  MainThreadData<BufferChunkList> mediumTenuredChunks;

  // Free lists for medium sized buffers. Used for allocation.
  MainThreadData<FreeLists> mediumFreeLists;

  // Chunks that may contain nursery-owned buffers waiting to be swept during a
  // minor GC. Populated from |mediumMixedChunks|.
  MainThreadOrGCTaskData<BufferChunkList> mediumMixedChunksToSweep;

  // Chunks that contain only tenured-owned buffers waiting to be swept during a
  // major GC. Populated from |mediumTenuredChunks|.
  MainThreadOrGCTaskData<BufferChunkList> mediumTenuredChunksToSweep;

  // Chunks that have been swept and their associated free lists.
  MutexData<BufferChunkList> sweptMediumMixedChunks;
  MutexData<BufferChunkList> sweptMediumTenuredChunks;
  MutexData<FreeLists> sweptMediumNurseryFreeLists;
  MutexData<FreeLists> sweptMediumTenuredFreeLists;

  // List of large nursery-owned buffers.
  MainThreadData<LargeAllocList> largeNurseryAllocs;

  // List of large tenured-owned buffers.
  MainThreadData<LargeAllocList> largeTenuredAllocs;

  // Large buffers waiting to be swept.
  MainThreadOrGCTaskData<LargeAllocList> largeTenuredAllocsToSweep;

  // Large buffers that have been swept.
  MainThreadData<LargeAllocList> sweptLargeNurseryAllocs;
  MutexData<LargeAllocList> sweptLargeTenuredAllocs;

  // Flag to indicate that swept chunks are available to be merged in the
  // sweptMediumMixedChunks or sweptMediumTenuredChunks lists.
  mozilla::Atomic<bool, mozilla::Relaxed> sweptChunksAvailable;

  // GC state for minor and major GC.
  MainThreadData<State> minorState;
  MainThreadData<State> majorState;

  // A major GC was started while a minor GC was still sweeping. Chunks by the
  // minor GC will be moved directly to the list of chunks to sweep for the
  // major GC. This happens for the minor GC at the start of every major GC.
  MainThreadData<bool> majorStartedWhileMinorSweeping;

  // A major GC finished while a minor GC was still sweeping. Some post major GC
  // cleanup will be deferred to the end of the minor sweeping.
  MainThreadData<bool> majorFinishedWhileMinorSweeping;

  // Flag to tell the main thread that minor sweeping has finished and
  // minorState should be updated.
  MutexData<bool> minorSweepingFinished;

 public:
  explicit BufferAllocator(JS::Zone* zone);
  ~BufferAllocator();

  static inline size_t GetGoodAllocSize(size_t requiredBytes);
  static inline size_t GetGoodElementCount(size_t requiredElements,
                                           size_t elementSize);
  static inline size_t GetGoodPower2AllocSize(size_t requiredBytes);
  static inline size_t GetGoodPower2ElementCount(size_t requiredElements,
                                                 size_t elementSize);
  static bool IsBufferAlloc(void* alloc);
  static size_t GetAllocSize(void* alloc);
  static JS::Zone* GetAllocZone(void* alloc);
  static bool IsNurseryOwned(void* alloc);
  static bool IsMarkedBlack(void* alloc);
  static void TraceEdge(JSTracer* trc, Cell* owner, void** bufferp,
                        const char* name);

  void* alloc(size_t bytes, bool nurseryOwned);
  void* allocInGC(size_t bytes, bool nurseryOwned);
  void* realloc(void* ptr, size_t bytes, bool nurseryOwned);
  void free(void* ptr);

  void startMinorCollection(MaybeLock& lock);
  bool startMinorSweeping(LargeAllocList& largeAllocsToFree);
  void sweepForMinorCollection();

  static void FreeLargeAllocs(LargeAllocList& largeAllocsToFree);

  void startMajorCollection(MaybeLock& lock);
  void startMajorSweeping(MaybeLock& lock);
  void sweepForMajorCollection(bool shouldDecommit);
  void finishMajorCollection(const AutoLock& lock);
  void clearMarkStateAfterBarrierVerification();

  void maybeMergeSweptData();
  void maybeMergeSweptData(MaybeLock& lock);
  void mergeSweptData();
  void mergeSweptData(const AutoLock& lock);

  bool isEmpty() const;

  // For debugging, used to implement GetMarkInfo. Returns false for allocations
  // being swept on another thread.
  bool isPointerWithinMediumOrLargeBuffer(void* ptr);

  Mutex& lock() const;

  size_t getSizeOfNurseryBuffers();

  void addSizeOfExcludingThis(size_t* usedBytesOut, size_t* freeBytesOut,
                              size_t* adminBytesOut);

  static void printStatsHeader(FILE* file);
  static void printStats(GCRuntime* gc, mozilla::TimeStamp creationTime,
                         bool isMajorGC, FILE* file);
  void getStats(size_t& usedBytes, size_t& freeBytes, size_t& adminBytes,
                size_t& mediumNurseryChunkCount,
                size_t& mediumTenuredChunkCount, size_t& freeRegions,
                size_t& largeNurseryAllocCount, size_t& largeTenuredAllocCount);

#ifdef DEBUG
  void checkGCStateNotInUse();
  void checkGCStateNotInUse(MaybeLock& lock);
  void checkGCStateNotInUse(const AutoLock& lock);
#endif

 private:
  // GC-internal APIs:
  static bool MarkTenuredAlloc(void* alloc);
  friend class js::GCMarker;

  void markNurseryOwnedAlloc(void* alloc, bool ownerWasTenured);
  friend class js::Nursery;

  // Small allocation methods:

  static inline bool IsSmallAllocSize(size_t bytes);
  static bool IsSmallAlloc(void* alloc);

  void* allocSmall(size_t bytes, bool nurseryOwned);
  void* allocSmallInGC(size_t bytes, bool nurseryOwned);

  static AllocKind AllocKindForSmallAlloc(size_t bytes);

  // Medium allocation methods:

  static bool IsMediumAlloc(void* alloc);

  void* allocMedium(size_t bytes, bool nurseryOwned, bool inGC);
  void* bumpAllocOrRetry(size_t sizeClass, bool inGC);
  void* bumpAlloc(size_t sizeClass);
  void* allocFromRegion(FreeRegion* region, size_t requestedBytes,
                        size_t sizeClass);
  void updateFreeListsAfterAlloc(FreeLists* freeLists, FreeRegion* region,
                                 size_t sizeClass);
  void recommitRegion(FreeRegion* region);
  bool allocNewChunk(bool inGC);
  bool sweepChunk(BufferChunk* chunk, OwnerKind ownerKindToSweep,
                  bool shouldDecommit, FreeLists& freeLists);
  void addSweptRegion(BufferChunk* chunk, uintptr_t freeStart,
                      uintptr_t freeEnd, bool shouldDecommit,
                      bool expectUnchanged, FreeLists& freeLists);
  void freeMedium(void* alloc);
  bool growMedium(void* alloc, size_t newBytes);
  bool shrinkMedium(void* alloc, size_t newBytes);
  FreeRegion* findFollowingFreeRegion(uintptr_t start);
  FreeRegion* findPrecedingFreeRegion(uintptr_t start);
  enum class ListPosition { Front, Back };
  FreeRegion* addFreeRegion(FreeLists* freeLists, size_t sizeClass,
                            uintptr_t start, uintptr_t end, bool anyDecommitted,
                            ListPosition position,
                            bool expectUnchanged = false);
  void updateFreeRegionStart(FreeLists* freeLists, FreeRegion* region,
                             uintptr_t newStart);
  FreeLists* getChunkFreeLists(BufferChunk* chunk);
  bool isSweepingChunk(BufferChunk* chunk);

  // Get the size class for an allocation. This rounds up to a class that is
  // large enough to hold the required size.
  static size_t SizeClassForAlloc(size_t bytes);

  // Get the maximum size class of allocations that can use a free region. This
  // rounds down to the largest class that can fit in this region.
  static size_t SizeClassForFreeRegion(size_t bytes);

  static size_t SizeClassBytes(size_t sizeClass);
  friend struct MediumBuffer;

  // Large allocation methods:

  static inline bool IsLargeAllocSize(size_t bytes);
  static bool IsLargeAlloc(void* alloc);
  static bool IsLargeAllocMarked(void* alloc);
  static bool MarkLargeAlloc(void* alloc);

  void* allocLarge(size_t bytes, bool nurseryOwned, bool inGC);
  bool sweepLargeTenured(LargeBuffer* header);
  void freeLarge(void* alloc);
  bool shrinkLarge(void* alloc, size_t newBytes);
  void unmapLarge(LargeBuffer* header, bool isSweeping);

  void updateHeapSize(size_t bytes, bool checkThresholds,
                      bool updateRetainedSize);

#ifdef DEBUG
  void checkChunkListGCStateNotInUse(BufferChunkList& chunks,
                                     bool hasNurseryOwnedAllocs,
                                     bool allowAllocatedDuringCollection);
  void checkChunkGCStateNotInUse(BufferChunk* chunk,
                                 bool allowAllocatedDuringCollection);
  void checkAllocListGCStateNotInUse(LargeAllocList& list, bool isNurseryOwned);
  void verifyChunk(BufferChunk* chunk, bool hasNurseryOwnedAllocs);
  void verifyFreeRegion(BufferChunk* chunk, uintptr_t endOffset,
                        size_t expectedSize);
#endif
};

// Internal data structures defined here so that users can get their size.

#ifdef DEBUG
// Magic check values used debug builds.
static constexpr uint16_t MediumBufferCheckValue = 0xBFA1;
static constexpr uint32_t LargeBufferCheckValue = 0xBFA110C2;
static constexpr uint32_t FreeRegionCheckValue = 0xBFA110C3;
#endif

struct alignas(CellAlignBytes) MediumBuffer {
  uint8_t sizeClass;
  bool isNurseryOwned = false;

#ifdef DEBUG
  uint16_t checkValue = MediumBufferCheckValue;
#endif

  MediumBuffer(uint8_t sizeClass, bool nurseryOwned);
  static MediumBuffer* from(BufferChunk* chunk, uintptr_t offset);
  void check() const;
  size_t bytesIncludingHeader() const;
  void* data();
};

struct alignas(CellAlignBytes) LargeBuffer
    : protected ChunkBase,
      public SlimLinkedListElement<LargeBuffer> {
  JS::Zone* const zone;
  size_t bytesIncludingHeader;
  mozilla::Atomic<bool, mozilla::Relaxed> marked;
  bool isNurseryOwned;
  bool allocatedDuringCollection = false;

#ifdef DEBUG
  uint32_t checkValue = LargeBufferCheckValue;
#endif

  inline LargeBuffer(JS::Zone* zone, size_t bytes, bool nurseryOwned);

  inline void check() const;

  inline bool markAtomic();
  inline void* data();
  bool isPointerWithinAllocation(void* ptr) const;
};

static constexpr size_t LargeBufferHeaderSize = sizeof(LargeBuffer);

}  // namespace gc
}  // namespace js

#endif  // gc_BufferAllocator_h