Re: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

[Paul Mackerras <paulus@samba.org>]

Linus Torvalds writes:

> And THAT is the hard part. Doing lookup without locks ends up being
> pretty much worthless, because you need the locks for the removal
> anyway, at which point the whole thing looks pretty moot.
> 
> Did I miss something?

I believe this all becomes (much more) useful when you are doing
read-copy-update.

There is an assumption that anyone modifying the list (inserting or
deleting) would take a lock first, so the deletion is just a pointer
assignment.  Any reader traversing the list (without a lock) sees
either the old pointer or the new, which is fine.

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 :).  One way of doing that is to defer the free or modification
to a quiescent point.  If you have a separate `next_free' field, you
could safely put the element on a list of elements to be freed at the
next quiescent point.

Paul.