RFC: patch to allow lock-free traversal of lists with insertion
Quoted 12 lines · In article <[email protected]>…
Quoted 4 lines · Paul Mackerras
The difficulty is in making sure that no reader is still inspecting the list element you just removed before you free it, or modify any field that the reader would be looking at (particularly the `next' field :).
..which implies _some_ sort of locking, even if it may be deferred.
The locking can be per-CPU, whatever - have a per-CPU count for "this many traversals in progress", and have every lookup increment it before starting, and decrement it after stopping.
Quoted 5 lines
Then the deleter can actually free the thing once he has seen every CPU go down to zero, with the proper memory barriers.
Yes, I see that it can work. But it sounds like a _lot_ of complexity for not very much gain.
It can get really ugly since the deleter has to keep checking periodically for zero-traversal-count. During that peiod more deletions can happen and the resulting in the need to maintain deleters as well.
An alternative approach is to divide the timeline
of the kernel into cycles - periods where every CPU does atleast one context switch thereby losing reference to any pointer to kernel data. You can now batch all the deletions prior to the start of a period and finish them after the end of that period. Any new deletions that happens during such a period get batched to the next such period. Any new traversal will see not see the older copy of the data since the global pointer(s) was updated.
Quoted 4 lines
Right now, you already have to have eight CPU's to see locking as a large problem in normal life. People have normal patches to bring that easily up to 16. Then how much hard-to-debug-with-subtle-memory-ordering-issues code do you want to handle the few machines that aren't in that range?
Yes, various degrees of weakness of memory ordering will make writing code harder, but it can be dealt with be defining primitives that behaves uniformly across different architectures. As for large machines are concerned, I hope the answer is "yes as long as it doesn't adversely affect the lower end" :-)
Thanks
Dipankar
Signature · 2 lines
Dipankar Sarma <[email protected]> Project: http://lse.sourceforge.net Linux Technology Center, IBM Software Lab, Bangalore, India.