Exploring snmalloc internals

// backend/globalconfig.h
  /**
   * Create allocator type for this configuration.
   */
  using Alloc = snmalloc::LocalAllocator<snmalloc::StandardConfig>;

// mem/localalloc.h
  template<SNMALLOC_CONCEPT(IsConfig) Config_>
  class LocalAllocator
  {
    // [...]
  private:
    // [...]

    // Free list per small size class.  These are used for
    // allocation on the fast path. This part of the code is inspired by
    // mimalloc.
    // Also contains remote deallocation cache.
    LocalCache local_cache{&Config::unused_remote};

    // Underlying allocator for most non-fast path operations.
    CoreAlloc* core_alloc{nullptr};
    
    // [...]
  }

// ds_core/ptrwrap.h
    namespace bounds
    {
      /**
       * Internal access to an entire Arena.  These exist only in the backend.
       */
      using Arena = bound<
        dimension::Spatial::Arena,
        dimension::AddressSpaceControl::Full,
        dimension::Wildness::Tame>;

      /**
       * Internal access to a Chunk of memory.  These flow across the boundary
       * between back- and front-ends, for example.
       */
      using Chunk = bound<
        dimension::Spatial::Chunk,
        dimension::AddressSpaceControl::Full,
        dimension::Wildness::Tame>;

      /**
       * User access to an entire Chunk.  Used as an ephemeral state when
       * returning a large allocation.  See capptr_chunk_is_alloc.
       */
      using ChunkUser =
        Chunk::with_address_space_control<dimension::AddressSpaceControl::User>;

      /**
       * Internal access to just one allocation (usually, within a slab).
       */
      using AllocFull = Chunk::with_spatial<dimension::Spatial::Alloc>;

      /**
       * User access to just one allocation (usually, within a slab).
       */
      using Alloc = AllocFull::with_address_space_control<
        dimension::AddressSpaceControl::User>;

      /**
       * A wild (i.e., putative) CBAllocExport pointer handed back by the
       * client. See capptr_from_client() and capptr_domesticate().
       */
      using AllocWild = Alloc::with_wildness<dimension::Wildness::Wild>;
    } // namespace bounds

    /**
     * The number of deallocation required until we hit a slow path. This
     * counts down in two different ways that are handled the same on the
     * fast path.  The first is
     *   - deallocations until the slab has sufficient entries to be considered
     *   useful to allocate from.  This could be as low as 1, or when we have
     *   a requirement for entropy then it could be much higher.
     *   - deallocations until the slab is completely unused.  This is needed
     *   to be detected, so that the statistics can be kept up to date, and
     *   potentially return memory to the a global pool of slabs/chunks.
     */
    uint16_t needed_ = 0;

// class CoreAllocator
// ...
    /**
     * Define local names for specialised versions of various types that are
     * specialised for the back-end that we are using.
     * @{
     */
    using BackendSlabMetadata = typename Config::Backend::SlabMetadata;
    using PagemapEntry = typename Config::PagemapEntry;
    /// }@

    /**
     * Per size class list of active slabs for this allocator.
     */
    struct SlabMetadataCache
    {
      SeqSet<BackendSlabMetadata> available{};

      uint16_t unused = 0;
      uint16_t length = 0;
    } alloc_classes[NUM_SMALL_SIZECLASSES]{};

    /**
     * The set of all slabs and large allocations
     * from this allocator that are full or almost full.
     */
    SeqSet<BackendSlabMetadata> laden{};
// ...

// mem/remoteallocator.h
  struct alignas(REMOTE_MIN_ALIGN) RemoteAllocator
  {
    /**
     * Global key for all remote lists.
     *
     * Note that we use a single key for all remote free lists and queues.
     * This is so that we do not have to recode next pointers when sending
     * segments, and look up specific keys based on destination.  This is
     * potentially more performant, but could make it easier to guess the key.
     */
    inline static FreeListKey key_global{0xdeadbeef, 0xbeefdead, 0xdeadbeef};

    using alloc_id_t = address_t;

    // Store the message queue on a separate cacheline. It is mutable data that
    // is read by other threads.
    alignas(CACHELINE_SIZE) freelist::AtomicQueuePtr back{nullptr};
    // Store the two ends on different cache lines as access by different
    // threads.
    alignas(CACHELINE_SIZE) freelist::AtomicQueuePtr front{nullptr};
    // Fake first entry
    freelist::Object::T<capptr::bounds::AllocWild> stub{};
    // [...]
  }

// ds/pagemap.h
  /**
   * Simple pagemap that for each GRANULARITY_BITS of the address range
   * stores a T.
   */
  template<size_t GRANULARITY_BITS, typename T, typename PAL, bool has_bounds>
  class FlatPagemap
  {
  public:
    static constexpr size_t SHIFT = GRANULARITY_BITS;
    static constexpr size_t GRANULARITY = bits::one_at_bit(GRANULARITY_BITS);

  private:
    /**
     * Before init is called will contain a single entry
     * that is the default value.  This is needed so that
     * various calls do not have to check for nullptr.
     *   free(nullptr)
     * and
     *   malloc_usable_size(nullptr)
     * do not require an allocation to have ocurred before
     * they are called.
     */
    inline static const T default_value{};

    /**
     * The representation of the page map.
     *
     * Initially a single element to ensure nullptr operations
     * work.
     */
    T* body{const_cast<T*>(&default_value)};

    /**
     * The representation of the pagemap, but nullptr if it has not been
     * initialised.  Used to combine init checking and lookup.
     */
    T* body_opt{nullptr};

    /**
     * If `has_bounds` is set, then these should contain the
     * bounds of the heap that is being managed by this pagemap.
     */
    address_t base{0};
    size_t size{0};
// [...]
  }

  class MetaEntryBase
  {
  protected:
  // [...]
    /**
     * In common cases, the pointer to the slab metadata.  See
     * docs/AddressSpace.md for additional details.
     *
     * The bottom bit is used to indicate if this is the first chunk in a PAL
     * allocation, that cannot be combined with the preceeding chunk.
     */
    uintptr_t meta{0};

    /**
     * In common cases, a bit-packed pointer to the owning allocator (if any),
     * and the sizeclass of this chunk.  See `encode` for
     * details of this case and docs/AddressSpace.md for further details.
     */
    uintptr_t remote_and_sizeclass{0};
  // [...]
  };

// [...]
    /**
     *  Data-structure for building the free list for this slab.
     */
    SNMALLOC_NO_UNIQUE_ADDRESS freelist::Builder<mitigations(random_preserve)>
      free_queue;

    /**
     * The number of deallocation required until we hit a slow path. This
     * counts down in two different ways that are handled the same on the
     * fast path.  The first is
     *   - deallocations until the slab has sufficient entries to be considered
     *   useful to allocate from.  This could be as low as 1, or when we have
     *   a requirement for entropy then it could be much higher.
     *   - deallocations until the slab is completely unused.  This is needed
     *   to be detected, so that the statistics can be kept up to date, and
     *   potentially return memory to the a global pool of slabs/chunks.
     */
    uint16_t needed_ = 0;

    /**
     * Flag that is used to indicate that the slab is currently not active.
     * I.e. it is not in a CoreAllocator cache for the appropriate sizeclass.
     */
    bool sleeping_ = false;

    /**
     * Flag to indicate this is actually a large allocation rather than a slab
     * of small allocations.
     */
    bool large_ = false;
// [...]

  /**
   * This class implements the standard backend for handling allocations.
   * It is parameterised by its Pagemap management and
   * address space management (LocalState).
   */
  template<
    SNMALLOC_CONCEPT(IsPAL) PAL,
    typename PagemapEntry,
    typename Pagemap,
    typename Authmap,
    typename LocalState>
  class BackendAllocator

    using LocalState = std::conditional_t<
      mitigations(metadata_protection),
      MetaProtectedRangeLocalState<Pal, Pagemap, Base>,
      StandardLocalState<Pal, Pagemap, Base>>;

// ...
  private:
    using ObjectRange = Pipe<LargeObjectRange, SmallBuddyRange>;

    ObjectRange object_range;

  public:
    // Expose a global range for the initial allocation of meta-data.
    using GlobalMetaRange = Pipe<ObjectRange, GlobalRange>;

    /**
     * Where we turn for allocations of user chunks.
     *
     * Reach over the SmallBuddyRange that's at the near end of the ObjectRange
     * pipe, rather than having that range adapter dynamically branch to its
     * parent.
     */
    LargeObjectRange* get_object_range()
    {
      return object_range.template ancestor<LargeObjectRange>();
    }

    /**
     * The backend has its own need for small objects without using the
     * frontend allocators; this range manages those.
     */
    ObjectRange& get_meta_range()
    {
      // Use the object range to service meta-data requests.
      return object_range;
    }
// ...

  /**
   * Randomize the location of the pagemap within a larger address space
   * allocation.  The other pages in that allocation may fault if accessed, on
   * platforms that can efficiently express such configurations.
   *
   * This guards against adversarial attempts to access the pagemap.
   *
   * This is unnecessary on StrictProvenance architectures.
   */
  constexpr mitigation::type random_pagemap{1 << 0};
  /**
   * Ensure that every slab (especially slabs used for larger "small" size
   * classes) has a larger minimum number of objects and that a larger
   * percentage of objects in a slab must be free to awaken the slab.
   *
   * This should frustrate use-after-reallocation attacks by delaying reuse.
   * When combined with random_preserve, below, it additionally ensures that at
   * least some shuffling of free objects is possible, and, hence, that there
   * is at least some unpredictability of reuse.
   *
   * TODO: should this be split? mjp: Would require changing some thresholds.
   * The min waking count needs to be ensure we have enough objects on a slab,
   * hence is related to the min count on a slab.  Currently we without this, we
   * have min count of slab of 16, and a min waking count with this enabled
   * of 32. So we would leak memory.
   */
  constexpr mitigation::type random_larger_thresholds{1 << 1};
  /**
   *
   * Obfuscate forward-edge pointers in intra-slab free lists.
   *
   * This helps prevent a UAF write from re-pointing the free list arbitrarily,
   * as the de-obfuscation of a corrupted pointer will generate a wild address.
   *
   * This is not available on StrictProvenance architectures.
   */
  constexpr mitigation::type freelist_forward_edge{1 << 2};
  /**
   * Store obfuscated backward-edge addresses in intra-slab free lists.
   *
   * Ordinarily, these lists are singly-linked.  Storing backward-edges allows
   * the allocator to verify the well-formedness of the links and, importantly,
   * the acyclicity of the list itself.  These backward-edges are also
   * obfuscated in an attempt to frustrate an attacker armed with UAF
   * attempting to construct a new well-formed list.
   *
   * Because the backward-edges are not traversed, this is available on
   * StrictProvenance architectures, unlike freelist_forward_edge.
   *
   * This is required to detect double frees as it will break the doubly linked
   * nature of the free list.
   */
  constexpr mitigation::type freelist_backward_edge{1 << 3};
  /**
   * When de-purposing a slab (releasing its address space for reuse at a
   * different size class or allocation), walk the free list and validate the
   * domestication of all nodes along it.
   *
   * If freelist_forward_edge is also enabled, this will probe the
   * domestication status of the de-obfuscated pointers before traversal.
   * Each of domestication and traversal may probabilistically catch UAF
   * corruption of the free list.
   *
   * If freelist_backward_edge is also enabled, this will verify the integrity
   * of the free list links.
   *
   * This gives the allocator "one last chance" to catch UAF corruption of a
   * slab's free list before the slab is de-purposed.
   *
   * This is required to comprehensively detect double free.
   */
  constexpr mitigation::type freelist_teardown_validate{1 << 4};
  /**
   * When initializing a slab, shuffle its free list.
   *
   * This guards against attackers relying on object-adjacency or address-reuse
   * properties of the allocation stream.
   */
  constexpr mitigation::type random_initial{1 << 5};
  /**
   * When a slab is operating, randomly assign freed objects to one of two
   * intra-slab free lists.  When selecting a slab's free list for allocations,
   * select the longer of the two.
   *
   * This guards against attackers relying on object-adjacency or address-reuse
   * properties of the allocation stream.
   */
  constexpr mitigation::type random_preserve{1 << 6};
  /**
   * Randomly introduce another slab for a given size-class, rather than use
   * the last available to an allocator.
   *
   * This guards against attackers relying on address-reuse, especially in the
   * pathological case of a size-class having only one slab with free entries.
   */
  constexpr mitigation::type random_extra_slab{1 << 7};
  /**
   * Use a LIFO queue, rather than a stack, of slabs with free elements.
   *
   * This generally increases the time between address reuse.
   */
  constexpr mitigation::type reuse_LIFO{1 << 8};
  /**
   * This performs a variety of inexpensive "sanity" tests throughout the
   * allocator:
   *
   * - Requests to free objects must
   *   - not be interior pointers
   *   - be of allocated address space
   * - Requests to free objects which also specify the size must specify a size
   *   that agrees with the current allocation.
   *
   * This guards gainst various forms of client misbehavior.
   *
   * TODO: Should this be split? mjp: It could, but let's not do this until
   * we have performance numbers to see what this costs.
   */
  constexpr mitigation::type sanity_checks{1 << 9};
  /**
   * On CHERI, perform a series of well-formedness tests on capabilities given
   * when requesting to free an object.
   */
  constexpr mitigation::type cheri_checks{1 << 10};
  /**
   * Erase intra-slab free list metadata before completing an allocation.
   *
   * This mitigates information disclosure.
   */
  constexpr mitigation::type clear_meta{1 << 11};
  /**
   * Protect meta data blocks by allocating separate from chunks for
   * user allocations. This involves leaving gaps in address space.
   * This is less efficient, so should only be applied for the checked
   * build.
   */
  constexpr mitigation::type metadata_protection{1 << 12};
  /**
   * If this mitigation is enabled, then Pal implementations should provide
   * exceptions/segfaults if accesses do not obey the
   *  - using
   *  - using_readonly
   *  - not_using
   * model.
   */
  static constexpr mitigation::type pal_enforce_access{1 << 13};