Re:Nah Lock: A Lock-Free Memory Allocator
by scott_s on Sunday November 16, 2014 @08:25PM
(#8616355)
Yes, but no.
The design goal of the allocator I worked on (http://www.scott-a-s.com/projects/#streamflow) specifically, and scalable allocators in general, is for threads to avoid interfering with each other. You're probably thinking of one giant, global free list that all threads interact with. That's not what happens. Instead, each thread has its own set of free lists. When thread A calls malloc, you grant those requests from thread A's data structures. Threads B and C cannot allocate memory form these spaces.
Cribbing from my own description of the approach:
"Streamflow avoids synchronization across threads as much as possible, and only uses lock-free synchronization when it is unavoidable. The common allocation path avoids synchronization by using per-thread private heaps, and a lock-free remote free list. If a thread needs to allocate memory, and it has sufficient free memory to satisfy the request, it only needs to touch data structures that it owns. If a thread frees memory that it allocated, it also only needs to touch data structures that it owns. The tricky case is when a thread needs to free memory that a different thread allocated. That memory gets added to the allocating thread’s remote free list in a lock-free manner—but the allocating thread will only touch that list when it does not have sufficient free memory."
So, if a thread does not have enough free chunks to grant a request, it first checks its remote-free lists. (That is, memory freed by other threads, even though it was allocated by this thread.) This means that a thread checking its remote-free list will be relatively rare, meaning that remote frees are unlikely to encounter contention. If it still can't grant the request, then it makes a request for an entirely new free list from a global page manager. That global page manager, in my implementation, was protected by a lock. Some recent follow up work eliminated this global lock (I think, see http://aces.snu.ac.kr/SFMalloc.html).
The design goal of the allocator I worked on (http://www.scott-a-s.com/projects/#streamflow) specifically, and scalable allocators in general, is for threads to avoid interfering with each other. You're probably thinking of one giant, global free list that all threads interact with. That's not what happens. Instead, each thread has its own set of free lists. When thread A calls malloc, you grant those requests from thread A's data structures. Threads B and C cannot allocate memory form these spaces.
Cribbing from my own description of the approach:
"Streamflow avoids synchronization across threads as much as possible, and only uses lock-free synchronization when it is unavoidable. The common allocation path avoids synchronization by using per-thread private heaps, and a lock-free remote free list. If a thread needs to allocate memory, and it has sufficient free memory to satisfy the request, it only needs to touch data structures that it owns. If a thread frees memory that it allocated, it also only needs to touch data structures that it owns. The tricky case is when a thread needs to free memory that a different thread allocated. That memory gets added to the allocating thread’s remote free list in a lock-free manner—but the allocating thread will only touch that list when it does not have sufficient free memory."
So, if a thread does not have enough free chunks to grant a request, it first checks its remote-free lists. (That is, memory freed by other threads, even though it was allocated by this thread.) This means that a thread checking its remote-free list will be relatively rare, meaning that remote frees are unlikely to encounter contention. If it still can't grant the request, then it makes a request for an entirely new free list from a global page manager. That global page manager, in my implementation, was protected by a lock. Some recent follow up work eliminated this global lock (I think, see http://aces.snu.ac.kr/SFMalloc.html).