Nah Lock: A Lock-Free Memory Allocator

Re:Nah Lock: A Lock-Free Memory Allocator by dezgeg on Sunday November 16, 2014 @01:19PM (#8614923)

The RCU technique (http://en.wikipedia.org/wiki/Read-copy-update) used in the Linux kernel does solve the "safe free()" problem. I've heard there's an userspace implementation (http://lwn.net/Articles/573424/) but dunno how that works.

[ Parent | on HN ]

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.

[ Parent | on HN ]