snmalloc

Allocation Constraints

• No Overlap: snmalloc ensures no two live allocations have overlapping bounds. Pointers are bounded to no more than the slab entry used to back the allocation.
• Vmem Stripping: Returned pointers are stripped of vmem authority (if supported) so clients cannot manipulate the underlying page mappings.
• Realloc Policy: If realloc() changes the size class, it triggers an allocate-copy-deallocate sequence. Even if the object stays in place, the returned pointer is re-bounded as if it were a new allocation.

Deallocation Behavior

• Interior Pointers: Currently, snmalloc permits deallocating an object using a pointer to any part of that object. The allocator will find the object's start and end via metadata.
• Lower Bound Lookup: During deallocation, snmalloc uses the lower bound address of the provided pointer to look up metadata, ensuring compatibility with architectures where bounds are monotonically non-increasing.

snmalloc is organized into a layered hierarchy. Each layer provides abstractions that the layers above it depend on. Understanding this hierarchy helps in knowing where to find specific functionality or where to inject custom logic:

• ds_core/: Core data structures (language extension abstractions).
• aal/: Architecture Abstraction Layer (CPU intrinsics, virtual address-space size).
• ds_aal/: Data structures depending on the AAL.
• mitigations/: Security mitigation configuration (e.g., mitigations() function controlled by SNMALLOC_CHECK_CLIENT).
• pal/: Platform Abstraction Layer (OS/environment abstractions).
• ds/: Data structures depending on platform services or CPU features.
• mem/: Core allocator abstractions (templated over a back-end).
• backend_helpers/: Helpers for defining back ends (e.g., pagemap implementations, buddy allocators).
• backend/: Example implementations of global memory allocators. Users can replace this with a custom back end.
• global/: Front-end components assuming a global configuration.
• override/: Implementations for specific language APIs (C malloc, C++ operator new, Rust std::alloc, etc.).

snmalloc implements a 'guarded' version of memcpy to prevent out-of-bounds (OOB) heap corruption. When memcpy(dst, src, len) is called, snmalloc can verify that the operation does not cross the boundary of the allocated memory blocks.

By default, for release builds, snmalloc performs a check to ensure the destination (dst) is large enough to hold len bytes. It can also be configured to check the source (src) to ensure it does not read beyond the end of the object.

Safety Logic

To ensure safety, the following checks are conceptually performed:

  if (src is managed by snmalloc)
    check(remaining_bytes(src) >= len);
  if (dst is managed by snmalloc)
    check(remaining_bytes(dst) >= len);

Key Characteristics

• Compatibility: If memory is not managed by snmalloc, the system assumes the operation is correct. This is achieved by mapping the 0 value in the chunk map to a virtual slab covering the entire address space.
• Initialization Safety: The implementation includes a check to handle cases where memcpy is called before snmalloc has been initialized.
• Performance: The overhead is most significant for very small copies (e.g., a single byte) but rapidly diminishes as the copy size increases. For copies of 128 bytes or more, the overhead is typically negligible.

snmalloc uses a novel technique to protect "in-band" meta-data (data stored within the unused memory of allocations) from corruption via use-after-free or out-of-bounds writes.

Instead of using a single linked list, snmalloc uses a doubly linked queue where both forward and backward pointers are encoded using cryptographic-like functions. This allows the allocator to verify the integrity of the list by checking the invariant: x.next.prev == x.

Encoding Mechanism

• Forward direction: Uses an involution f(a) = a XOR k0, where k0 is a randomly chosen value.
• Backward direction: Uses a two-argument function g(a, b) = (a XOR k1) * (b XOR k2), where k1 and k2 are randomly chosen 64-bit values.

Because the order of construction and consumption must match to maintain these invariants, snmalloc uses queues rather than stacks for its free lists.

Benefits

• Corruption Detection: Detects out-of-bounds writes or use-after-free attacks on the next or prev pointers during reallocation.
• Double Free Protection: If an object is freed twice, it corrupts the prev pointer. The error is detected when the object is later reused.
• Low Overhead: The protection is integrated into the fast path of allocation with minimal performance impact (one multiplication, one branch, and a few additional loads/stores).

The Combining Lock is an optimization of the MCS queue lock designed to reduce contention. Instead of each thread only performing its own work, the thread that currently holds the lock (the 'head') can traverse the queue and execute the operations (lambdas) of other waiting threads.

Core Abstractions

• LockStatus: A state machine for each node in the queue:
  • WAITING: The thread is waiting for the lock to become available.
  • HEAD: The thread is responsible for completing more work from the queue.
  • DONE: Another thread has already completed the operation for this thread.
• CombiningLockNode: A node in the queue containing a pointer to the next node, the current LockStatus, and a function pointer (f_raw) representing the work to be done.
• CombiningLockNodeTempl<F>: A template wrapper that allows passing a lambda/function F and uses manual dispatch (via reinterpret_cast) instead of virtual tables to avoid vtable overhead.

enum class LockStatus
{
  WAITING,
  DONE,
  HEAD
};

struct CombiningLockNode
{
  std::atomic<CombiningLockNode*> next{nullptr};
  std::atomic<LockStatus> status{WAITING};
  void (*f_raw)(CombiningLockNode*);

  void run()
  {
    f_raw(this);
  }
};

template<typename F>
struct CombiningLockNodeTempl : CombiningLockNode
{
  F f;

  CombiningLockNodeTempl(F&& f_)
  : CombiningLockNode([](CombiningLockNode* self) {
      auto self_templ = reinterpret_cast<CombiningLockNodeTempl*>(self);
      self_templ->f();
    }), 
    f(f_) {}
};