shuffling-allocator

A shuffling allocator.

This crate provides the ShufflingAllocator type, which wraps an existing allocator and shuffles the order of heap allocations it yields, effectively randomizing the placement of heap allocations.

Randomizing the locations of heap allocations is useful for testing, benchmarking, and performance evaluation. It helps you separate the performance effects of a given code change from accidental heap object locality and the effects this may have on performance due to memory caches in the CPU. This is the use case that this crate focuses on.

While randomizing the locations of heap allocations can also be used for defense-in-depth security, similar to ASLR, this crate is not written to support that use case. As a result, this crate may not be the right choice if your use case is the defense-in-depth security use case. Some trade offs and design decisions made in this crate's implementation might not be the choices you want for your use case.

This crate is inspired by the allocator described in Stabilizer: Statistically Sound Performance Evaluation by Curtsinger and Berger.

How Does It Work?

An array of available objects for each size class is always maintained. Allocating a new object involves making the allocation, choosing a random index in the array, swapping the new allocation for array[i] and returning the swapped out value. Freeing an object is similar: choose a random index in the array, swap the pointer being freed with array[i], and then use the underlying allocator to actually free the swapped out pointer. The larger the array in the shuffling layer, the closer to truly randomized heap allocations we get, but also the greater the overhead. Curtsinger and Berger found that arrays of size 256 gave good randomization for acceptable overhead, and that is also the array size that this crate uses.

Example

Wrap the system allocator in a ShufflingAllocator, randomizing the location of the system allocator's heap objects:

use shuffling_allocator::ShufflingAllocator;
use std::alloc::System;

static SHUFFLED_SYSTEM_ALLOC: ShufflingAllocator<System> =
    shuffling_allocator::wrap!(&System);