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

[Keith Owens <kaos@ocs.com.au>]

On Wed, 10 Oct 2001 09:54:36 -0600, 
Victor Yodaiken <yodaiken@fsmlabs.com> wrote:
>Although I kind of like the idea of
>	normal operation create mess by avoiding synchronization
>	when system seems idle, get BKL, and clean up. 

That does not work.  A process can read an entry from a list then
perform an operation that puts the process to sleep.  When it wakes up
again, how can it tell if the list has been changed?  How can the
cleanup code tell if any process has slept while it was traversing a
list?  An idle system does not prevent processes from sleeping at the
wrong point.

Don't even think of requiring "processes must not sleep while
traversing a lock free list".  Programmers cannot get "processes must
not sleep while holding a lock" correct and that error is much easier
to detect.

The inability for update code to know when a lock free list is being
traversed is the reason that most lock free work requires type stable
storage.  You can mark a list entry as free and put it on a free chain
but you can never unmap the storage nor use the free entry for data of
a different type.  That is the only way to guarantee that a process can
safely determine if the list has changed under it during traversal
while still allowing the process to be interrupted or to sleep.