SlamAllocator.h

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#ifndef SLAM_ALLOCATOR_H
#define SLAM_ALLOCATOR_H
#include <config.h>
 
#include "pedigree/kernel/Spinlock.h"
#include "pedigree/kernel/TargetInfo.h"
#include "pedigree/kernel/compiler.h"
#include "pedigree/kernel/core/SlamBitmap.h"
#include "pedigree/kernel/processor/types.h"
#include "pedigree/kernel/utilities/utility.h"
 
#if PEDIGREE_BENCHMARK
namespace SlamSupport {
uintptr_t getHeapBase();
uintptr_t getHeapEnd();
void getPageAt(void* addr);
void unmapPage(void* page);
void unmapAll();
}  // namespace SlamSupport
#endif
 
class SlamAllocator;
#if PEDIGREE_CONCURRENCY_SMOKE_TESTS
class EXPORTED_PUBLIC SlamCache;
#else
class SlamCache;
#endif
 
#define SLAB_SIZE 1
 
#define SLAB_MINIMUM_SIZE (TargetInfo::getPageSize() * SLAB_SIZE)
 
#define USING_MAGIC 1
 
#define MAGIC_TYPE uintptr_t
 
#define MAGIC_VALUE 0xb00b1e55ULL
 
#define ABSOLUTE_MINIMUM_SIZE 64
#define ALL_HEADERS_SIZE                                          \
  (sizeof(SlamCache::Node) + sizeof(SlamAllocator::AllocHeader) + \
   sizeof(SlamAllocator::AllocFooter))
#define OBJECT_MINIMUM_SIZE \
  (ALL_HEADERS_SIZE < ABSOLUTE_MINIMUM_SIZE ? ABSOLUTE_MINIMUM_SIZE : ALL_HEADERS_SIZE)
 
#define DEBUGGING_SLAB_ALLOCATOR 0
 
#define TEMP_MAGIC 0x67845753
 
#if USE_DEBUG_ALLOCATOR
#define OVERRUN_CHECK 0
#else
#define OVERRUN_CHECK 1
#endif
 
#define VIGILANT_OVERRUN_CHECK 0
 
#define VIGILANT_MAGIC 0x1337cafe
 
#define CRIPPLINGLY_VIGILANT 0
 
#define BOCHS_MAGIC_WATCHPOINTS 0
 
#define SCRIBBLE_FREED_BLOCKS 0
 
#define WARN_PAGE_SIZE_OR_LARGER 0
 
#define SLABS_FOR_HUGE_ALLOCS 0
 
#define VERBOSE_ISPOINTERVALID 0
 
#define EVERY_ALLOCATION_IS_A_SLAB 0
 
#ifndef SLAM_USE_DEBUG_ALLOCATOR
#define SLAM_USE_DEBUG_ALLOCATOR 0
#endif
 
#define SLAM_LOCKED SLAM_USE_DEBUG_ALLOCATOR ? 1 : 0  // need the lock for the debug allocator only
 
#ifndef SLAM_BT_FRAMES
#define SLAM_BT_FRAMES 3
#endif
 
#if PEDIGREE_CONCURRENCY_SMOKE_TESTS
class EXPORTED_PUBLIC SlamCache {
#else
class SlamCache {
#endif
  // struct Node must be public so that sizeof(SlamCache::Node) is available.
 public:
  struct Node {
    Node* next;
#if USING_MAGIC
    MAGIC_TYPE magic;
#endif
  } __attribute__((aligned(16)));
 
  SlamCache();
  virtual ~SlamCache();
 
  void initialise(SlamAllocator* parent, size_t objectSize);
 
  uintptr_t allocate();
 
  void free(uintptr_t object);
 
  size_t recovery(size_t maxSlabs);
 
  bool isPointerValid(uintptr_t object) const;
 
#if defined(PEDIGREE_BUILDUTILS)
  void setListForTest(size_t list);
#endif
 
  inline size_t objectSize() const {
    return m_ObjectSize;
  }
 
  inline size_t slabSize() const {
    return m_SlabSize;
  }
 
  inline size_t slabObjectCount() const {
    return m_SlabObjectCount;
  }
 
  void trackSlab(uintptr_t slab);
  void check();
 
 private:
  SlamCache(const SlamCache&);
  const SlamCache& operator=(const SlamCache&);
 
  struct Slab {
    Node* freeHead;
    Slab* next;
    Slab* previous;
    SlamCache* cache;
    size_t freeObjects;
    size_t objectCount;
    size_t list;
    bool onList;
  };
 
  static constexpr const int NUM_LISTS =
#if defined(PEDIGREE_BUILDUTILS)
      4;
#else
      MULTIPROCESSOR ? 256 : 1;
#endif
 
  Slab* m_PartialLists[NUM_LISTS];
  Slab* m_FastSlabs[NUM_LISTS];
  Node* m_LargeFreeList;
 
  void addSlab(Slab* slab, size_t list);
  void removeSlab(Slab* slab);
  bool beginFastPath();
  void endFastPath();
  Node* popFreeObject(Slab* slab);
  void pushFreeObject(Slab* slab, Node* node);
  Node* objectAt(uintptr_t slab, size_t index) const;
  Slab* slabForObject(uintptr_t object) const;
 
  uintptr_t getSlab();
  void freeSlab(uintptr_t slab);
 
  Node* initialiseSlab(uintptr_t slab);
  size_t currentList() const;
 
  size_t m_ObjectSize;
  size_t m_SlabSize;
  size_t m_SlabObjectOffset;
  size_t m_SlabObjectCount;
 
  // This version of the allocator doesn't have a free list, instead
  // the reap() function returns memory directly to the VMM. This
  // avoids needing to lock the free list on MP systems.
 
  uintptr_t m_FirstSlab;
  size_t m_FastPathState;
 
  Spinlock m_RecoveryLock;
#if BITS_32
  Spinlock m_FreeLock;
#endif
 
  SlamAllocator* m_pParentAllocator;
 
#if defined(PEDIGREE_BUILDUTILS)
  size_t m_TestList = 0;
#endif
};
 
class SlamAllocator {
 public:
  SlamAllocator();
  virtual ~SlamAllocator();
 
  void initialise();
 
  // quickly clear all allocations from the allocator
  void clearAll();
 
  uintptr_t allocate(size_t nBytes);
  void free(uintptr_t mem);
 
#if HOSTED && PEDIGREE_HOSTED_SMOKE_TESTS
  static EXPORTED_PUBLIC uintptr_t guardedAllocateForTest(size_t nBytes);
  static EXPORTED_PUBLIC void guardedFreeForTest(uintptr_t mem);
#endif
 
  size_t recovery(size_t maxSlabs = 1);
 
  bool isPointerValid(uintptr_t mem)
#if !SLAM_LOCKED
      const
#endif
      ;
  bool isWithinHeap(uintptr_t mem) const;
 
  size_t allocSize(uintptr_t mem);
 
  static EXPORTED_PUBLIC SlamAllocator& instance();
 
  size_t heapPageCount() const {
    return m_HeapPageCount;
  }
 
  uintptr_t getSlab(size_t fullSize);
  void freeSlab(uintptr_t address, size_t length);
 
#if defined(PEDIGREE_BUILDUTILS)
  enum class SlabTransitionForTest { Reserved, Mapped, Unmapped };
  using SlabTransitionHookForTest = void (*)(SlabTransitionForTest transition, uintptr_t address,
                                             void* context);
 
  void setSlabTransitionHookForTest(SlabTransitionHookForTest hook, void* context);
#endif
 
 private:
  void freeSlabUnlocked(uintptr_t address, size_t length);
 
 public:
  size_t headerSize() const {
    return sizeof(AllocHeader);
  }
  size_t footerSize() const {
    return sizeof(AllocFooter);
  }
 
  void setVigilance(bool b) {
    m_bVigilant = b;
  }
  bool getVigilance() const {
    return m_bVigilant;
  }
 
 private:
  friend class SlamCache;
 
  SlamAllocator(const SlamAllocator&);
  const SlamAllocator& operator=(const SlamAllocator&);
 
  static SlamAllocator m_Instance;
 
  void wipe();
 
  bool isAllocatedPage(uintptr_t address) const;
 
  void markSlabReady(uintptr_t address, size_t length);
 
  SlamCache m_Caches[32];
 
 public:
  struct AllocHeader_VigilantOverrunCheck_Empty {};
  struct AllocHeader_VigilantOverrunCheck {
    uintptr_t backtrace[SLAM_BT_FRAMES];
    size_t requested;
  };
 
  struct OverrunCheck_Magic_Empty {};
  struct OverrunCheck_Magic
      : pedigree_std::conditional<VIGILANT_OVERRUN_CHECK, AllocHeader_VigilantOverrunCheck,
                                  AllocHeader_VigilantOverrunCheck_Empty>::type {
    size_t magic;
  };
 
  struct AllocHeader : pedigree_std::conditional<OVERRUN_CHECK, OverrunCheck_Magic,
                                                 OverrunCheck_Magic_Empty>::type {
    // Already-present and embedded Node fields.
    SlamCache::Node node;
    SlamCache* cache;
  } __attribute__((aligned(16)));
 
  struct AllocFooter : pedigree_std::conditional<OVERRUN_CHECK, OverrunCheck_Magic,
                                                 OverrunCheck_Magic_Empty>::type {
  } __attribute__((aligned(16)));
 
 private:
  bool m_bInitialised;
 
  bool m_bVigilant;
 
  mutable Spinlock m_SlabRegionLock;
 
  size_t m_HeapPageCount;
 
  SlamBitmap m_SlabRegionBitmap;
  size_t m_SlabRegionBitmapEntries;
  size_t m_SlabRegionPages;
 
  uintptr_t m_Base;
 
#if defined(PEDIGREE_BUILDUTILS)
  SlabTransitionHookForTest m_SlabTransitionHook = nullptr;
  void* m_SlabTransitionHookContext = nullptr;
#endif
 
  Spinlock m_Lock;
};
 
#endif