Re: [RFC] Lock free fd lookup

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

On Fri, 16 Jul 2004 18:19:36 -0700, 
William Lee Irwin III <wli@holomorphy.com> wrote:
>On Sat, Jul 17, 2004 at 10:55:59AM +1000, Keith Owens wrote:
>> The beauty of these lockfree algorithms on large structures is that
>> nothing ever stalls indefinitely.  If the underlying SMP cache hardware
>> is fair, everything running a lockfree list will make progress.  These
>> algorithms do not suffer from reader vs. writer starvation.
>
>That's a large assumption. NUMA hardware typically violates it.

True, which is why I mentioned it.  However I suspect that you read
something into that paragraph which was not intended.

Just reading the lockfree list and the structures on the list does not
suffer from any NUMA problems, because reading does not perform any
global updates at all.  The SMP starvation problem only kicks in when
multiple concurrent updates are being done.  Even with multiple
writers, one of the writers is guaranteed to succeed every time, so
over time all the write operations will proceed, subject to fair access
to exclusive cache lines.

Lockfree reads with Moir's algorithms require extra memory bandwidth.
In the absence of updates, all the cache lines end up in shared state.
That reduces to local memory bandwidth for the (hopefully) common case
of lots of readers and few writers.  Lockfree code is nicely suited to
the same class of problem that RCU addresses, but without the reader
vs. writer starvation problems.

Writer vs. writer starvation on NUMA is a lot harder.  I don't know of
any algorithm that handles lists with lots of concurrent updates and
also scales well on large cpus, unless the underlying hardware is fair
in its handling of exclusive cache lines.