Re:Nah Lock: A Lock-Free Memory Allocator
by haberman on Sunday November 16, 2014 @11:40AM
(#8614609)
> After writing an email to Kayvon professing "correctness", I realized that I had a very bad and obvious race condition: [some thread reads an old pointer, leading to segfault]. Is there a more clever (lockfree) way than having a locked instruction on the common path in order to satisfy a rare edge case?
While I don't fully understand the details of the allocator design described here, this sounds very much like the "safe memory reclamation" problem that plagues lock-free algorithms. I run into this almost every time I want to do something interesting that is lock-free. It's a huge bummer.
The basic problem is this: anytime you want to be able to free memory in a lock-free data structure, there is almost always the risk that some other thread has read a pointer to that very memory, has the pointer sitting in memory or some register, and then goes to sleep (ie. is preempted) before it can actually dereference it. These threads are "ticking time bombs", so to speak. If you free the memory, the thread will crash when it wakes up and dereferences the memory.
Every simple solution to this problem you're tempted to invent doesn't work. The main solution to the problem in the literature is Hazard Pointers (http://en.wikipedia.org/wiki/Hazard_pointer), which also solves a related problem in lock-free algorithms, the ABA problem. Another approach is to just never free memory, or not free it until the structure itself is freed (when you can guarantee that no thread is using the structure anymore).
I believe that this problem is one of the biggest reasons lock-free algorithms aren't more practical. I wrote more about this (and some of the weaknesses of hazard pointers) here: https://news.ycombinator.com/item?id=8265803
Re:Nah Lock: A Lock-Free Memory Allocator
by scott_s on Sunday November 16, 2014 @03:48PM
(#8615382)
I don't recall this specific circumstance being a problem with lock-free memory allocation. The semantics of malloc itself help you; when someone frees memory, they're asserting that they're allowed to do it. If they use that memory again, then that's their fault, not yours (when we're the one implementing the memory allocator).
We can also avoid this problem because scalable memory allocators try to minimize different threads touching the same parts of the internal data structure. This is counter to, say, trying to implement a lock-free red black tree. There, the whole point is that multiple threads will all touch the same state.
The allocator I worked on maintained lock-free queues for remote frees. We would sometimes deallocate these queues entirely - but we knew this was safe because we would only do it when all of the chunks of memory attached to these queues were free. If there was a dangling pointer somewhere, that was an application error.
Data structures inside memory allocators serve a different purpose than data structures inside typical applications. When you have, say, a tree in your application, you very much care about the actual data stored in it. Your payload - the entire point of having the data structure - is the particular data stored somewhere in the tree. If you want, say, the element with the key "ABCD", then no other element will do. The payload for the data structures in a memory allocator is just chunks of memory. If you're doing an allocation, then any chunk will do. If you're doing a free, you need to free that particular chunk, but you can also assume that no one else will free it.
Re:Nah Lock: A Lock-Free Memory Allocator
by haberman on Sunday November 16, 2014 @05:16PM
(#8615687)
> The allocator I worked on maintained lock-free queues for remote frees. We would sometimes deallocate these queues entirely - but we knew this was safe because we would only do it when all of the chunks of memory attached to these queues were free.
In a memory allocator, don't you generally want to maintain freelists of memory that is available for reuse? If so, isn't there a race between threads trying to unmap the freed blocks and threads trying to reuse them?
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).
Re:Nah Lock: A Lock-Free Memory Allocator
by haberman on Sunday November 16, 2014 @05:29PM
(#8615740)
I don't know that much about RCU, but the description on Wikipedia says that step 3-4 for all writers is:
> 3. Wait for a grace period to elapse, so that all previous readers (which might still have pointers to the data structure removed in the prior step) will have completed their RCU read-side critical sections.
>
> 4. At this point, there cannot be any readers still holding references to the data structure, so it now may safely be reclaimed (e.g., freed).
So this appears to not be wait-free for writers, and it also requires a way of being assured that readers have exited the critical section. The mechanism for ensuring you have waited long enough (as a writer) is non-trivial.
The user-space variety of RCU appears to require per-thread registration/deregistration, whether explicit or implicit. This is similar to the requirement that hazard pointers have.
Re:Nah Lock: A Lock-Free Memory Allocator
by davidtgoldblatt on Sunday November 16, 2014 @12:28PM
(#8614768)
BTW, the problems with thread registration you mention can be solved using cpu-local storage instead of thread-local. This can also save space usage and collection time since, assuming short lifetimes for guard objects, the total maximum number of guard objects that ever come into existence simultaneously is smaller.
In lots of practical scenarios though, hazard pointers aren't great for performance, since they require a Store|Load fence during every load operation (e.g. traversing linked list requires O(n) mfences). Alternatives like Fraser's epoch-based reclamation or quiescent state based reclamation often perform better in "real life". (Not to imply you're not familiar with this, haberman, but it's useful to document for other readers).
Re:Nah Lock: A Lock-Free Memory Allocator
by jamesaguilar on Sunday November 16, 2014 @03:41PM
(#8615358)
Kinda agree with this flippant response, but then again, if you need speed such that you care about lock free algorithms, you are likely using one of the very fast languages, and few of these offer a garbage collector.
Re:Nah Lock: A Lock-Free Memory Allocator
by jcr on Sunday November 16, 2014 @10:17AM
(#8614355)
Unfortunately, it seems the git repository mentioned is not publicly
available. I searched for 'apodolsk' and found one on github, but the
nalloc code is not there. Luckily, it seems the author is on HN (user:
"gosu"):
I toyed with scalable allocators for a course a few years back.
It's a little embarassing, but if you want to see what the costs
actually are:
http://www.andrew.cmu.edu/user/apodolsk/418/finalreport.html
Re:Nah Lock: A Lock-Free Memory Allocator
by scott_s on Sunday November 16, 2014 @03:21PM
(#8615291)
The true lockfree allocators, NBMalloc, Streamflow, and the implementation of Maged Michael's alloc, all failed to compile on ALADDIN (2 failed to compile on my machine) and I don't think I should attempt to resolve that now.
I'm one of the Streamflow authors and implementors. What's ALADDIN? I may be able to help get it compile.
While I don't fully understand the details of the allocator design described here, this sounds very much like the "safe memory reclamation" problem that plagues lock-free algorithms. I run into this almost every time I want to do something interesting that is lock-free. It's a huge bummer.
The basic problem is this: anytime you want to be able to free memory in a lock-free data structure, there is almost always the risk that some other thread has read a pointer to that very memory, has the pointer sitting in memory or some register, and then goes to sleep (ie. is preempted) before it can actually dereference it. These threads are "ticking time bombs", so to speak. If you free the memory, the thread will crash when it wakes up and dereferences the memory.
Every simple solution to this problem you're tempted to invent doesn't work. The main solution to the problem in the literature is Hazard Pointers (http://en.wikipedia.org/wiki/Hazard_pointer), which also solves a related problem in lock-free algorithms, the ABA problem. Another approach is to just never free memory, or not free it until the structure itself is freed (when you can guarantee that no thread is using the structure anymore).
I believe that this problem is one of the biggest reasons lock-free algorithms aren't more practical. I wrote more about this (and some of the weaknesses of hazard pointers) here: https://news.ycombinator.com/item?id=8265803
We can also avoid this problem because scalable memory allocators try to minimize different threads touching the same parts of the internal data structure. This is counter to, say, trying to implement a lock-free red black tree. There, the whole point is that multiple threads will all touch the same state.
The allocator I worked on maintained lock-free queues for remote frees. We would sometimes deallocate these queues entirely - but we knew this was safe because we would only do it when all of the chunks of memory attached to these queues were free. If there was a dangling pointer somewhere, that was an application error.
Data structures inside memory allocators serve a different purpose than data structures inside typical applications. When you have, say, a tree in your application, you very much care about the actual data stored in it. Your payload - the entire point of having the data structure - is the particular data stored somewhere in the tree. If you want, say, the element with the key "ABCD", then no other element will do. The payload for the data structures in a memory allocator is just chunks of memory. If you're doing an allocation, then any chunk will do. If you're doing a free, you need to free that particular chunk, but you can also assume that no one else will free it.
In a memory allocator, don't you generally want to maintain freelists of memory that is available for reuse? If so, isn't there a race between threads trying to unmap the freed blocks and threads trying to reuse them?
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).
> 3. Wait for a grace period to elapse, so that all previous readers (which might still have pointers to the data structure removed in the prior step) will have completed their RCU read-side critical sections. > > 4. At this point, there cannot be any readers still holding references to the data structure, so it now may safely be reclaimed (e.g., freed).
So this appears to not be wait-free for writers, and it also requires a way of being assured that readers have exited the critical section. The mechanism for ensuring you have waited long enough (as a writer) is non-trivial.
The user-space variety of RCU appears to require per-thread registration/deregistration, whether explicit or implicit. This is similar to the requirement that hazard pointers have.
In lots of practical scenarios though, hazard pointers aren't great for performance, since they require a Store|Load fence during every load operation (e.g. traversing linked list requires O(n) mfences). Alternatives like Fraser's epoch-based reclamation or quiescent state based reclamation often perform better in "real life". (Not to imply you're not familiar with this, haberman, but it's useful to document for other readers).
[0]: http://concurrencykit.org/
https://news.ycombinator.com/item?id=8613038
https://news.ycombinator.com/item?id=8613156With luck he'll notice that his nalloc work is on the front page of HN, and possibly tell us if the nalloc code is available somewhere.
It looks like the public AFS/web gateways around don't seem to support .git directories (huh!). But, I have cloned it and mirrored a git bundle:
http://emarhavil.com/~joshua/nalloc.bdl
wget it, then 'git clone nalloc.bdl nalloc'.
I'm one of the Streamflow authors and implementors. What's ALADDIN? I may be able to help get it compile.