Re: [RFC] Lock free fd lookup

[William Lee Irwin III <wli@holomorphy.com>]

On Fri, 16 Jul 2004 18:19:36 -0700, William Lee Irwin III wrote:
>> That's a large assumption. NUMA hardware typically violates it.

On Sat, Jul 17, 2004 at 12:28:54PM +1000, Keith Owens wrote:
> True, which is why I mentioned it.  However I suspect that you read
> something into that paragraph which was not intended.

The NUMA issue is the only caveat I saw. I guess I just wanted to
mention it by name.


On Sat, Jul 17, 2004 at 12:28:54PM +1000, Keith Owens wrote:
> 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.

The only methods I can think of to repair this (basically queueing) are
not busywait-free.


On Sat, Jul 17, 2004 at 12:28:54PM +1000, Keith Owens wrote:
> 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.

I suppose it's worth refining the starvation claim to delaying freeing
memory as opposed to readers causing writers to busywait indefinitely.


On Sat, Jul 17, 2004 at 12:28:54PM +1000, Keith Owens wrote:
> 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.

Well, neither do I. =)


-- wli