Skip to contentSkip to conversation

RFC: patch to allow lock-free traversal of lists with insertion

Lse-tech Dipankar Sarma 1 participant 1 message Oct 10, 2001

lore
Share & tools
lore
#0 lore raw
Quoted 7 lines · In article <[email protected]>…

Now, in all fairness I can imagine hacky lock-less removals too. To get them to work, you have to (a) change the "next" pointer to point to the next->next (and have some serialization between removals, but removals only, to make sure you don't have next->next also going away from you) and
(b) leave the old "next" pointer (and thus the data structure) around until you can _prove_ that nobody is looking anything up any more, and that the now-defunct data structure can truly be removed.

This is exactly what Read-Copy Update does. You keep the old data structure around until you are sure that all the CPUs have lost references to it by context switching. There are more than one relatively non-intrusive ways of detecting completion of such a cycle and "deleted" data can be freed afterwards.

The details are in http://lse.sourceforge.net/locking/rcupdate.html.

Thanks
Dipankar

Signature · 2 lines
Dipankar Sarma  <[email protected]> Project: http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.