High-Performance Memory Allocators: Implementation and Optimization for Enterprise Systems
Memory allocation is one of the most critical performance bottlenecks in enterprise systems. This comprehensive guide explores advanced memory allocator design, implementation techniques, and optimization strategies for building high-performance custom allocators.
Memory Allocator Architecture and Design Principles
Section 1: Advanced Allocator Design Patterns
Understanding the fundamental trade-offs in memory allocator design is crucial for building high-performance systems that can handle enterprise workloads efficiently.
Multi-Tier Allocator Architecture
// allocator_core.h - Core allocator architecture
#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>
#include <pthread.h>
#include <sys/mman.h>
#include <unistd.h>
// Allocation size classes for efficient memory management
#define SMALL_SIZE_THRESHOLD (4 * 1024) // 4KB
#define MEDIUM_SIZE_THRESHOLD (64 * 1024) // 64KB
#define LARGE_SIZE_THRESHOLD (1024 * 1024) // 1MB
#define PAGE_SIZE (4096)
#define CACHE_LINE_SIZE (64)
#define MAX_SIZE_CLASSES (64)
#define THREAD_CACHE_SIZE (2 * 1024 * 1024) // 2MB per thread
// Allocation tiers
typedef enum {
ALLOC_TIER_SMALL, // < 4KB, high-frequency allocations
ALLOC_TIER_MEDIUM, // 4KB - 64KB, moderate frequency
ALLOC_TIER_LARGE, // 64KB - 1MB, low frequency
ALLOC_TIER_HUGE, // > 1MB, very low frequency
ALLOC_TIER_COUNT
} alloc_tier_t;
// Size class definition
struct size_class {
size_t size; // Object size
size_t objects_per_page; // Objects per page
size_t pages_per_span; // Pages per span
uint32_t index; // Size class index
struct free_list free_objects; // Free object list
};
// Thread-local cache for small allocations
struct thread_cache {
pthread_t thread_id;
struct free_list size_class_caches[MAX_SIZE_CLASSES];
size_t total_cached_bytes;
uint64_t allocation_count;
uint64_t deallocation_count;
uint64_t cache_hits;
uint64_t cache_misses;
struct thread_cache *next;
};
// Central allocator state
struct allocator_state {
// Size class management
struct size_class size_classes[MAX_SIZE_CLASSES];
uint32_t num_size_classes;
// Page management
struct page_heap page_heap;
struct span_allocator span_alloc;
// Thread caches
struct thread_cache *thread_caches;
pthread_mutex_t thread_cache_mutex;
// Large allocation tracking
struct large_alloc_tracker large_tracker;
// Statistics and monitoring
struct allocator_stats stats;
// Configuration
struct allocator_config config;
// Memory mapping
void *heap_base;
size_t heap_size;
size_t heap_committed;
// Synchronization
pthread_mutex_t global_mutex;
pthread_rwlock_t size_class_lock;
};
// Global allocator instance
static struct allocator_state *g_allocator = NULL;
static __thread struct thread_cache *tls_cache = NULL;
// Initialize size classes with optimal distribution
static void init_size_classes(struct allocator_state *alloc)
{
size_t size = 8; // Start with 8-byte alignment
uint32_t index = 0;
// Small size classes (8 bytes to 4KB)
while (size <= SMALL_SIZE_THRESHOLD && index < MAX_SIZE_CLASSES) {
struct size_class *sc = &alloc->size_classes[index];
sc->size = size;
sc->index = index;
sc->objects_per_page = PAGE_SIZE / size;
sc->pages_per_span = 1;
// Ensure minimum objects per span for efficiency
if (sc->objects_per_page < 8) {
sc->pages_per_span = (8 * size + PAGE_SIZE - 1) / PAGE_SIZE;
sc->objects_per_page = (sc->pages_per_span * PAGE_SIZE) / size;
}
init_free_list(&sc->free_objects);
index++;
// Size progression: 8, 16, 24, 32, 48, 64, 96, 128, ...
if (size < 128) {
size += 8;
} else if (size < 1024) {
size += size / 8; // 12.5% increase
} else {
size += size / 4; // 25% increase
}
}
alloc->num_size_classes = index;
}
// Fast size class lookup using bit manipulation
static inline uint32_t size_to_class(size_t size)
{
if (size <= 128) {
return (size + 7) / 8 - 1;
}
// Use CLZ (count leading zeros) for efficient lookup
uint32_t lg = 63 - __builtin_clzll(size - 1);
uint32_t delta = size - (1ULL << lg);
uint32_t delta_bits = lg > 6 ? lg - 6 : 0;
uint32_t mod = delta >> delta_bits;
return 13 + (lg - 7) * 4 + mod;
}
// Thread cache initialization
static struct thread_cache *init_thread_cache(void)
{
struct thread_cache *cache = mmap(NULL, sizeof(*cache),
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (cache == MAP_FAILED)
return NULL;
cache->thread_id = pthread_self();
cache->total_cached_bytes = 0;
cache->allocation_count = 0;
cache->deallocation_count = 0;
cache->cache_hits = 0;
cache->cache_misses = 0;
// Initialize size class caches
for (int i = 0; i < MAX_SIZE_CLASSES; i++) {
init_free_list(&cache->size_class_caches[i]);
}
// Add to global thread cache list
pthread_mutex_lock(&g_allocator->thread_cache_mutex);
cache->next = g_allocator->thread_caches;
g_allocator->thread_caches = cache;
pthread_mutex_unlock(&g_allocator->thread_cache_mutex);
return cache;
}
High-Performance Free List Implementation
// free_list.c - Lock-free free list implementation
#include <stdatomic.h>
// Lock-free free list node
struct free_node {
struct free_node *next;
uint64_t aba_counter; // ABA problem prevention
};
// Free list with atomic operations
struct free_list {
atomic_uintptr_t head; // Packed pointer + ABA counter
atomic_size_t count;
size_t max_count;
};
// Pack pointer and ABA counter
static inline uintptr_t pack_ptr(struct free_node *ptr, uint64_t counter)
{
return (uintptr_t)ptr | (counter << 48);
}
// Unpack pointer from packed value
static inline struct free_node *unpack_ptr(uintptr_t packed)
{
return (struct free_node *)(packed & 0x0000FFFFFFFFFFFFULL);
}
// Unpack ABA counter from packed value
static inline uint64_t unpack_counter(uintptr_t packed)
{
return packed >> 48;
}
// Initialize free list
static void init_free_list(struct free_list *list)
{
atomic_store(&list->head, 0);
atomic_store(&list->count, 0);
list->max_count = SIZE_MAX;
}
// Lock-free push operation
static bool free_list_push(struct free_list *list, void *ptr)
{
struct free_node *node = (struct free_node *)ptr;
uintptr_t old_head, new_head;
do {
old_head = atomic_load(&list->head);
struct free_node *old_ptr = unpack_ptr(old_head);
uint64_t old_counter = unpack_counter(old_head);
node->next = old_ptr;
node->aba_counter = old_counter + 1;
new_head = pack_ptr(node, old_counter + 1);
} while (!atomic_compare_exchange_weak(&list->head, &old_head, new_head));
atomic_fetch_add(&list->count, 1);
return true;
}
// Lock-free pop operation
static void *free_list_pop(struct free_list *list)
{
uintptr_t old_head, new_head;
struct free_node *node;
do {
old_head = atomic_load(&list->head);
node = unpack_ptr(old_head);
if (node == NULL)
return NULL;
uint64_t old_counter = unpack_counter(old_head);
new_head = pack_ptr(node->next, old_counter + 1);
} while (!atomic_compare_exchange_weak(&list->head, &old_head, new_head));
atomic_fetch_sub(&list->count, 1);
return node;
}
// Batch operations for better performance
static size_t free_list_pop_batch(struct free_list *list, void **ptrs,
size_t max_count)
{
size_t count = 0;
uintptr_t old_head, new_head;
struct free_node *node, *batch_head;
// Pop multiple items in a single CAS operation
do {
old_head = atomic_load(&list->head);
batch_head = unpack_ptr(old_head);
if (batch_head == NULL)
break;
// Walk the list to find batch_end
node = batch_head;
for (count = 0; count < max_count && node != NULL; count++) {
ptrs[count] = node;
node = node->next;
}
if (count == 0)
break;
uint64_t old_counter = unpack_counter(old_head);
new_head = pack_ptr(node, old_counter + 1);
} while (!atomic_compare_exchange_weak(&list->head, &old_head, new_head));
atomic_fetch_sub(&list->count, count);
return count;
}
Section 2: Slab Allocator Implementation
Slab allocators are ideal for frequently allocated objects of the same size, providing excellent cache locality and minimal fragmentation.
Production-Grade Slab Allocator
// slab_allocator.c - High-performance slab allocator
#include <sys/mman.h>
#include <linux/mman.h>
#define SLAB_MAGIC 0xDEADBEEF
#define SLAB_ALIGN 16
// Slab states
typedef enum {
SLAB_STATE_EMPTY, // No allocated objects
SLAB_STATE_PARTIAL, // Some allocated objects
SLAB_STATE_FULL, // All objects allocated
SLAB_STATE_DESTROYED // Slab being destroyed
} slab_state_t;
// Slab descriptor
struct slab {
uint32_t magic; // Magic number for validation
slab_state_t state; // Current state
size_t object_size; // Size of objects in this slab
size_t objects_per_slab; // Number of objects per slab
size_t free_count; // Number of free objects
// Free object tracking
struct free_list free_objects;
// Memory layout
void *memory; // Slab memory base
size_t slab_size; // Total slab size
// Linked list management
struct slab *next;
struct slab *prev;
// Cache back-reference
struct slab_cache *cache;
// Statistics
uint64_t alloc_count;
uint64_t free_count_total;
uint64_t creation_time;
// Coloring for cache optimization
size_t color_offset;
};
// Slab cache for objects of specific size
struct slab_cache {
char name[32]; // Cache name
size_t object_size; // Object size
size_t object_align; // Object alignment
size_t slab_size; // Size of each slab
size_t objects_per_slab; // Objects per slab
// Constructor/destructor
void (*ctor)(void *obj);
void (*dtor)(void *obj);
// Slab lists
struct slab *empty_slabs;
struct slab *partial_slabs;
struct slab *full_slabs;
// Synchronization
pthread_mutex_t mutex;
// Statistics
atomic_size_t total_slabs;
atomic_size_t active_objects;
atomic_size_t total_allocations;
atomic_size_t cache_misses;
// Cache coloring
size_t color_range;
size_t color_next;
// Linked list of all caches
struct slab_cache *next;
};
// Global cache registry
static struct slab_cache *cache_list = NULL;
static pthread_mutex_t cache_list_mutex = PTHREAD_MUTEX_INITIALIZER;
// Create a new slab cache
struct slab_cache *slab_cache_create(const char *name, size_t object_size,
size_t align, void (*ctor)(void *),
void (*dtor)(void *))
{
struct slab_cache *cache;
// Validate parameters
if (!name || object_size == 0 || align == 0)
return NULL;
// Align object size
object_size = (object_size + align - 1) & ~(align - 1);
cache = calloc(1, sizeof(*cache));
if (!cache)
return NULL;
// Initialize cache
strncpy(cache->name, name, sizeof(cache->name) - 1);
cache->object_size = object_size;
cache->object_align = align;
cache->ctor = ctor;
cache->dtor = dtor;
// Calculate optimal slab size
cache->slab_size = calculate_slab_size(object_size);
cache->objects_per_slab = cache->slab_size / object_size;
// Cache coloring for better cache utilization
cache->color_range = CACHE_LINE_SIZE;
cache->color_next = 0;
pthread_mutex_init(&cache->mutex, NULL);
// Register cache globally
pthread_mutex_lock(&cache_list_mutex);
cache->next = cache_list;
cache_list = cache;
pthread_mutex_unlock(&cache_list_mutex);
return cache;
}
// Calculate optimal slab size
static size_t calculate_slab_size(size_t object_size)
{
size_t slab_size = PAGE_SIZE;
size_t waste;
// Try different slab sizes to minimize waste
for (size_t size = PAGE_SIZE; size <= 16 * PAGE_SIZE; size += PAGE_SIZE) {
size_t objects = size / object_size;
waste = size - (objects * object_size);
// Accept if waste is less than 12.5%
if (waste < size / 8) {
slab_size = size;
break;
}
}
return slab_size;
}
// Create a new slab
static struct slab *create_slab(struct slab_cache *cache)
{
struct slab *slab;
void *memory;
size_t total_size;
// Calculate total size including slab descriptor
total_size = cache->slab_size + sizeof(struct slab);
// Allocate memory with mmap for better control
memory = mmap(NULL, total_size, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (memory == MAP_FAILED)
return NULL;
// Place slab descriptor at the end
slab = (struct slab *)((char *)memory + cache->slab_size);
// Initialize slab
slab->magic = SLAB_MAGIC;
slab->state = SLAB_STATE_EMPTY;
slab->object_size = cache->object_size;
slab->objects_per_slab = cache->objects_per_slab;
slab->free_count = cache->objects_per_slab;
slab->memory = memory;
slab->slab_size = cache->slab_size;
slab->cache = cache;
slab->creation_time = time(NULL);
// Apply cache coloring
slab->color_offset = cache->color_next;
cache->color_next += cache->object_align;
if (cache->color_next >= cache->color_range)
cache->color_next = 0;
init_free_list(&slab->free_objects);
// Initialize free object list
char *obj_ptr = (char *)memory + slab->color_offset;
for (size_t i = 0; i < cache->objects_per_slab; i++) {
// Call constructor if provided
if (cache->ctor)
cache->ctor(obj_ptr);
free_list_push(&slab->free_objects, obj_ptr);
obj_ptr += cache->object_size;
}
atomic_fetch_add(&cache->total_slabs, 1);
return slab;
}
// Allocate object from slab cache
void *slab_cache_alloc(struct slab_cache *cache)
{
struct slab *slab;
void *obj;
pthread_mutex_lock(&cache->mutex);
// Try to allocate from partial slabs first
slab = cache->partial_slabs;
if (!slab) {
// Try empty slabs
slab = cache->empty_slabs;
if (slab) {
// Move from empty to partial list
cache->empty_slabs = slab->next;
if (cache->empty_slabs)
cache->empty_slabs->prev = NULL;
slab->next = cache->partial_slabs;
if (cache->partial_slabs)
cache->partial_slabs->prev = slab;
cache->partial_slabs = slab;
slab->prev = NULL;
}
}
// Create new slab if needed
if (!slab) {
pthread_mutex_unlock(&cache->mutex);
slab = create_slab(cache);
if (!slab) {
atomic_fetch_add(&cache->cache_misses, 1);
return NULL;
}
pthread_mutex_lock(&cache->mutex);
// Add to partial list
slab->next = cache->partial_slabs;
if (cache->partial_slabs)
cache->partial_slabs->prev = slab;
cache->partial_slabs = slab;
}
// Allocate object from slab
obj = free_list_pop(&slab->free_objects);
if (obj) {
slab->free_count--;
slab->alloc_count++;
slab->state = (slab->free_count == 0) ? SLAB_STATE_FULL : SLAB_STATE_PARTIAL;
// Move to full list if necessary
if (slab->state == SLAB_STATE_FULL) {
// Remove from partial list
if (slab->prev)
slab->prev->next = slab->next;
else
cache->partial_slabs = slab->next;
if (slab->next)
slab->next->prev = slab->prev;
// Add to full list
slab->next = cache->full_slabs;
if (cache->full_slabs)
cache->full_slabs->prev = slab;
cache->full_slabs = slab;
slab->prev = NULL;
}
atomic_fetch_add(&cache->active_objects, 1);
atomic_fetch_add(&cache->total_allocations, 1);
}
pthread_mutex_unlock(&cache->mutex);
return obj;
}
// Free object back to slab cache
void slab_cache_free(struct slab_cache *cache, void *obj)
{
struct slab *slab;
if (!obj)
return;
// Find the slab containing this object
slab = find_slab_for_object(cache, obj);
if (!slab || slab->magic != SLAB_MAGIC) {
// Invalid object or corrupted slab
return;
}
pthread_mutex_lock(&cache->mutex);
// Call destructor if provided
if (cache->dtor)
cache->dtor(obj);
// Return object to free list
free_list_push(&slab->free_objects, obj);
slab->free_count++;
slab->free_count_total++;
slab_state_t old_state = slab->state;
if (slab->free_count == slab->objects_per_slab) {
slab->state = SLAB_STATE_EMPTY;
} else {
slab->state = SLAB_STATE_PARTIAL;
}
// Move slab between lists if state changed
if (old_state == SLAB_STATE_FULL && slab->state == SLAB_STATE_PARTIAL) {
// Move from full to partial list
if (slab->prev)
slab->prev->next = slab->next;
else
cache->full_slabs = slab->next;
if (slab->next)
slab->next->prev = slab->prev;
slab->next = cache->partial_slabs;
if (cache->partial_slabs)
cache->partial_slabs->prev = slab;
cache->partial_slabs = slab;
slab->prev = NULL;
} else if (old_state == SLAB_STATE_PARTIAL && slab->state == SLAB_STATE_EMPTY) {
// Consider moving to empty list or destroying
if (cache->total_slabs > 1) { // Keep at least one slab
// Move to empty list
if (slab->prev)
slab->prev->next = slab->next;
else
cache->partial_slabs = slab->next;
if (slab->next)
slab->next->prev = slab->prev;
slab->next = cache->empty_slabs;
if (cache->empty_slabs)
cache->empty_slabs->prev = slab;
cache->empty_slabs = slab;
slab->prev = NULL;
}
}
atomic_fetch_sub(&cache->active_objects, 1);
pthread_mutex_unlock(&cache->mutex);
}
// Find slab containing a specific object
static struct slab *find_slab_for_object(struct slab_cache *cache, void *obj)
{
uintptr_t obj_addr = (uintptr_t)obj;
struct slab *slab;
// Check all slab lists
for (slab = cache->partial_slabs; slab; slab = slab->next) {
uintptr_t slab_start = (uintptr_t)slab->memory;
uintptr_t slab_end = slab_start + slab->slab_size;
if (obj_addr >= slab_start && obj_addr < slab_end)
return slab;
}
for (slab = cache->full_slabs; slab; slab = slab->next) {
uintptr_t slab_start = (uintptr_t)slab->memory;
uintptr_t slab_end = slab_start + slab->slab_size;
if (obj_addr >= slab_start && obj_addr < slab_end)
return slab;
}
return NULL;
}
Advanced Memory Pool Implementations
Section 3: Lock-Free Memory Pool Design
Memory pools provide excellent performance for applications with predictable allocation patterns, especially when combined with lock-free techniques.
High-Throughput Memory Pool
// memory_pool.c - Lock-free memory pool implementation
#include <stdatomic.h>
#define POOL_MAGIC 0xFEEDFACE
#define POOL_MAX_THREADS 64
// Memory block header
struct pool_block {
struct pool_block *next;
uint32_t magic;
uint32_t block_id;
size_t size;
uint64_t allocation_time;
uint32_t thread_id;
uint32_t pool_id;
};
// Per-thread pool cache
struct thread_pool_cache {
struct free_list free_blocks;
size_t cached_bytes;
size_t max_cached_bytes;
uint64_t cache_hits;
uint64_t cache_misses;
uint32_t thread_id;
};
// Memory pool descriptor
struct memory_pool {
uint32_t pool_id;
size_t block_size;
size_t alignment;
size_t initial_blocks;
size_t max_blocks;
// Global free list
struct free_list global_free_list;
// Thread caches
struct thread_pool_cache thread_caches[POOL_MAX_THREADS];
atomic_uint active_threads;
// Memory management
void **memory_chunks;
size_t chunk_count;
size_t chunk_size;
atomic_size_t total_allocated;
atomic_size_t blocks_in_use;
// Statistics
atomic_uint64_t total_allocations;
atomic_uint64_t total_frees;
atomic_uint64_t peak_usage;
// Configuration
bool use_thread_cache;
bool zero_on_alloc;
bool zero_on_free;
// Synchronization
pthread_mutex_t expand_mutex;
char name[32];
};
static atomic_uint pool_id_counter = ATOMIC_VAR_INIT(1);
static __thread uint32_t thread_cache_id = UINT32_MAX;
// Initialize memory pool
struct memory_pool *memory_pool_create(const char *name, size_t block_size,
size_t alignment, size_t initial_blocks)
{
struct memory_pool *pool;
if (block_size == 0 || alignment == 0)
return NULL;
pool = aligned_alloc(CACHE_LINE_SIZE, sizeof(*pool));
if (!pool)
return NULL;
memset(pool, 0, sizeof(*pool));
// Initialize pool parameters
pool->pool_id = atomic_fetch_add(&pool_id_counter, 1);
pool->block_size = (block_size + alignment - 1) & ~(alignment - 1);
pool->alignment = alignment;
pool->initial_blocks = initial_blocks;
pool->max_blocks = initial_blocks * 16; // Allow growth
pool->chunk_size = pool->block_size * initial_blocks;
pool->use_thread_cache = true;
pool->zero_on_alloc = false;
pool->zero_on_free = false;
strncpy(pool->name, name ? name : "unnamed", sizeof(pool->name) - 1);
// Initialize free list
init_free_list(&pool->global_free_list);
// Initialize thread caches
for (int i = 0; i < POOL_MAX_THREADS; i++) {
init_free_list(&pool->thread_caches[i].free_blocks);
pool->thread_caches[i].max_cached_bytes = pool->block_size * 64;
pool->thread_caches[i].thread_id = UINT32_MAX;
}
pthread_mutex_init(&pool->expand_mutex, NULL);
// Allocate initial memory chunk
if (expand_pool(pool) != 0) {
memory_pool_destroy(pool);
return NULL;
}
return pool;
}
// Expand pool with new memory chunk
static int expand_pool(struct memory_pool *pool)
{
void *chunk;
size_t total_size;
struct pool_block *block;
char *block_ptr;
pthread_mutex_lock(&pool->expand_mutex);
// Check if we've reached the maximum
if (pool->chunk_count >= (pool->max_blocks / pool->initial_blocks)) {
pthread_mutex_unlock(&pool->expand_mutex);
return -1;
}
// Calculate total size including block headers
total_size = pool->chunk_size + (pool->initial_blocks * sizeof(struct pool_block));
// Allocate aligned memory chunk
chunk = aligned_alloc(PAGE_SIZE, total_size);
if (!chunk) {
pthread_mutex_unlock(&pool->expand_mutex);
return -1;
}
// Expand memory chunk array
void **new_chunks = realloc(pool->memory_chunks,
(pool->chunk_count + 1) * sizeof(void *));
if (!new_chunks) {
free(chunk);
pthread_mutex_unlock(&pool->expand_mutex);
return -1;
}
pool->memory_chunks = new_chunks;
pool->memory_chunks[pool->chunk_count] = chunk;
pool->chunk_count++;
// Initialize blocks and add to global free list
block_ptr = (char *)chunk;
for (size_t i = 0; i < pool->initial_blocks; i++) {
block = (struct pool_block *)block_ptr;
block->magic = POOL_MAGIC;
block->block_id = atomic_fetch_add(&pool->total_allocated, 1);
block->size = pool->block_size;
block->pool_id = pool->pool_id;
// The actual data comes after the header
void *data_ptr = block_ptr + sizeof(struct pool_block);
free_list_push(&pool->global_free_list, data_ptr);
block_ptr += sizeof(struct pool_block) + pool->block_size;
}
pthread_mutex_unlock(&pool->expand_mutex);
return 0;
}
// Get thread-local cache
static struct thread_pool_cache *get_thread_cache(struct memory_pool *pool)
{
if (thread_cache_id == UINT32_MAX) {
// Assign thread cache ID
uint32_t id = atomic_fetch_add(&pool->active_threads, 1);
if (id >= POOL_MAX_THREADS)
return NULL; // Too many threads
thread_cache_id = id;
pool->thread_caches[id].thread_id = id;
}
return &pool->thread_caches[thread_cache_id];
}
// Allocate block from memory pool
void *memory_pool_alloc(struct memory_pool *pool)
{
void *ptr = NULL;
struct thread_pool_cache *cache = NULL;
if (!pool)
return NULL;
// Try thread cache first if enabled
if (pool->use_thread_cache) {
cache = get_thread_cache(pool);
if (cache) {
ptr = free_list_pop(&cache->free_blocks);
if (ptr) {
cache->cached_bytes -= pool->block_size;
cache->cache_hits++;
goto found;
}
cache->cache_misses++;
}
}
// Try global free list
ptr = free_list_pop(&pool->global_free_list);
if (!ptr) {
// Expand pool and try again
if (expand_pool(pool) == 0) {
ptr = free_list_pop(&pool->global_free_list);
}
}
if (!ptr)
return NULL;
found:
// Update statistics
atomic_fetch_add(&pool->total_allocations, 1);
atomic_fetch_add(&pool->blocks_in_use, 1);
// Update peak usage
size_t current_usage = atomic_load(&pool->blocks_in_use);
size_t peak = atomic_load(&pool->peak_usage);
while (current_usage > peak) {
if (atomic_compare_exchange_weak(&pool->peak_usage, &peak, current_usage))
break;
}
// Get block header
struct pool_block *block = (struct pool_block *)((char *)ptr - sizeof(struct pool_block));
block->allocation_time = rdtsc(); // Use TSC for high-resolution timing
block->thread_id = thread_cache_id;
// Zero memory if requested
if (pool->zero_on_alloc) {
memset(ptr, 0, pool->block_size);
}
return ptr;
}
// Free block back to memory pool
void memory_pool_free(struct memory_pool *pool, void *ptr)
{
struct thread_pool_cache *cache;
struct pool_block *block;
if (!pool || !ptr)
return;
// Get block header and validate
block = (struct pool_block *)((char *)ptr - sizeof(struct pool_block));
if (block->magic != POOL_MAGIC || block->pool_id != pool->pool_id) {
// Invalid block
return;
}
// Zero memory if requested
if (pool->zero_on_free) {
memset(ptr, 0, pool->block_size);
}
// Try thread cache first if enabled
if (pool->use_thread_cache) {
cache = get_thread_cache(pool);
if (cache && cache->cached_bytes < cache->max_cached_bytes) {
free_list_push(&cache->free_blocks, ptr);
cache->cached_bytes += pool->block_size;
atomic_fetch_add(&pool->total_frees, 1);
atomic_fetch_sub(&pool->blocks_in_use, 1);
return;
}
}
// Return to global free list
free_list_push(&pool->global_free_list, ptr);
atomic_fetch_add(&pool->total_frees, 1);
atomic_fetch_sub(&pool->blocks_in_use, 1);
}
// Get high-resolution timestamp counter
static inline uint64_t rdtsc(void)
{
uint32_t low, high;
__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
return ((uint64_t)high << 32) | low;
}
This comprehensive guide covers advanced memory allocator implementation techniques, from multi-tier architectures to lock-free data structures and high-performance memory pools. These implementations provide the foundation for building enterprise-grade systems that can handle demanding workloads with optimal memory utilization and minimal allocation overhead.
The key principles demonstrated include cache-aware design, lock-free programming, NUMA awareness, and comprehensive performance monitoring. By understanding and implementing these advanced techniques, developers can create memory allocators that significantly outperform general-purpose allocators for specific workload patterns commonly found in enterprise environments.