A Non-blocking Buddy System for Scalable Memory Allocation on Multi-core Machines

In this short paper we tackle the issue of scalability of core memory allocators, which is an orthogonal optimization with respect to reducing the pressure to core allocators by (a), (b), or (c). In particular, our contribution is the design of a non-blocking (lock-free) allocator implementing the buddy-system specification, where concurrent allocations/dellocations are not coordinated via spin-locks, but by only relying on individual Read-Modify-Write (RMW) instructions executed along the critical path of allocation/deallocation operations. These instructions are exploited to detect whether concurrent requests have conflicted on the same portion of the allocator metadata