LRU Cache + Thread-Safe Memory Pool (C++20)

A from-scratch implementation of two data structures commonly used in high-performance systems: a thread-safe LRU Cache backed by a custom memory pool allocator.

Why this project

Most LRU Cache tutorials either ignore thread-safety entirely or use new/delete directly for node allocation, leaving out the kind of detail that matters in real systems code. This project goes further:

• Real thread-safety, validated with concurrent stress tests across multiple threads
• Custom allocator integration: the LRU Cache uses an internal MemoryPool to allocate/deallocate its linked-list nodes, instead of calling new/delete on every put/eviction
• Placement new / explicit destructor calls in the memory pool, so non-trivial objects (with real constructors/destructors) are handled correctly — not just "recycled raw memory"
• Pointer ownership validation on deallocate, preventing pool corruption from a pointer that doesn't belong to it
• Correct move semantics where it matters, and copy semantics explicitly disabled where shallow-copying raw pointers would cause double-free bugs

Architecture

include/
├── lru_cache.hpp      # Thread-safe LRU Cache (std::shared_mutex)
│                      #   -> uses MemoryPool<Node> internally for node allocation
└── memory_pool.hpp    # Thread-safe generic memory pool (std::mutex)
tests/
└── test_main.cpp      # functional tests + concurrent stress tests

Custom allocator integration

The LRU Cache does not call new Node(...) / delete node directly. Instead, it owns a MemoryPool<Node> sized exactly to its capacity — since the cache can never have more live nodes than its capacity, the pool never needs to grow and never gets exhausted under normal use.

Node* node = nodePool.allocate(key, value);  // placement-new under the hood
...
nodePool.deallocate(lru);                    // calls ~Node() explicitly, recycles the slot

This avoids repeated heap allocation/deallocation for small, frequently churned objects (cache nodes) — a known source of overhead and heap fragmentation in systems that allocate/free small objects at high frequency (this is the same idea behind allocators like tcmalloc/jemalloc, just at a much smaller, illustrative scale).

The two mutexes (cache-level and pool-level) never block each other circularly: the pool's lock is only ever acquired while already holding the cache's lock, never the other way around, so there's no deadlock risk from lock ordering.

Build & Run

Requires C++20 (uses std::shared_mutex).

g++ -std=c++20 -Wall -Wextra -g -Iinclude tests/test_main.cpp -o test_main -lpthread
./test_main

Or with CMake:

mkdir build && cd build
cmake ..
cmake --build .
./test_main

Design decisions

LRU Cache

• get() uses unique_lock, not shared_lock, because it mutates the list (moves the accessed node to the front) as a side effect — it's technically a write operation, even though it "reads" a value, so it can't safely use shared/concurrent read access.
• Copy constructor/assignment are explicitly = deleted. The class manages raw Node* pointers internally; a shallow copy would cause double-free on destruction.
• Move semantics are also disabled (= delete), specifically because of the pool integration: moving an LRUCache would require safely moving its internal MemoryPool, whose raw memory blocks and internal bookkeeping aren't trivially relocatable without extra validation. This is a deliberate simplicity/safety trade-off — if move support is ever needed, wrapping the cache in std::unique_ptr<LRUCache<K,V>> achieves the same effect at the call site without needing to move the object itself.

Memory Pool

• Allocates raw memory once, at construction (::operator new with correct alignment via std::align_val_t).
• allocate(args...) uses placement new to actually construct a T object with the given arguments — not just reserve memory.
• deallocate() explicitly calls the destructor (obj->~T()) before recycling the slot.
• Validates that a pointer passed to deallocate() actually belongs to the pool (via an std::unordered_set of valid blocks), throwing std::invalid_argument otherwise.
• Documented trade-off: the pool's destructor does not automatically destroy objects that are still "alive" (not yet deallocated) — that responsibility is on the caller, the same discipline required with manual new/delete. A fully "owning pool" that tracks occupied slots and destroys them automatically on pool destruction would remove this risk, at the cost of extra bookkeeping complexity.

Testing

tests/test_main.cpp covers:

• basic functional behavior (LRU eviction order, hit/miss)
• concurrent stress test: 8 threads × 5000 operations on the LRU Cache (now exercising the pool-backed allocation path on every put/eviction)
• allocation/deallocation with non-trivial objects (real constructors/destructors)
• pool exhaustion behavior (capacity limits)
• invalid pointer detection on deallocate
• concurrent stress test on the memory pool directly, with a final consistency check (all slots return to available)

Note: ThreadSanitizer is not currently supported on the MinGW/Windows toolchain used for this project (libtsan unavailable on this platform). Concurrency was validated via repeated stress testing instead. On Linux/ macOS with clang or a full GCC build, -fsanitize=thread should work and is recommended for further validation.

Possible future extensions

• TTL (time-to-live) support per cache entry
• Multiple block-size classes in the memory pool, similar to production allocators (tcmalloc/jemalloc)
• Throughput benchmarks: pool-backed allocation vs. raw new/delete, single-threaded and multi-threaded