[ltt-dev] [PATCH 3/3] lock-free queue with RCU-based garbage collection

[Paolo Bonzini]

On 03/11/2010 11:09 PM, Mathieu Desnoyers wrote:
> It could be nice to try separating memory allocation from this lockless
> queue implementation. I think they belong to different problem space,
> and that we should just let the users provide whatever allocator they
> use. Possibly, if you need internal copies within your data structure,
> that the caller should pass pointers to its malloc/free implementation.

True.  Before that, the implementation would need to be genericized, as 
right now it's just a test file.

> Then providing a lock-free malloc/free could come as a separate lib.

Or an RCU-based malloc/free. :-)

Regarding the articles, I'll add a note.  It's basically only "Fast and 
Practical Non-Blocking and Blocking Concurrent Queue Algorithms", by 
Maged Michael and Michael Scott (1996), except that I don't use 
double-word compare-and-swap, and that this RCU-friendly allocation 
strategy is "invented" by me.

@inproceeding{Michael96podc,
  author = {Maged M. Michael and Michael L. Scott},
  title = {Fast and Practical Non-Blocking and Blocking Concurrent
          Queue Algorithms},
  booktitle = {Proc. 15th ACM Symp. on Principles of Distributed
          Computing},
  year = {1996},
  pages = {267--275},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.8494}
}

Paolo