[lkml]   [2001]   [Oct]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: [Lse-tech] Re: RFC: patch to allow lock-free traversal of lists with insertion

On Wed, 10 Oct 2001, Paul Mackerras wrote:
> 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.

Right, that's not the problem.

> 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.

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.

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?

I'm just trying to inject a bit of realism here.


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:05    [W:0.219 / U:0.508 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site