Whither klists?

Whither klists?

[Alan Stern]

Patrick and Greg:

To put it baldly: Should klists be replaced with regular lists, each 
protected by an rwsem (or even a mutex)?

The advantage of klists is that threads can remove or add nodes while 
other threads iterate through the list.  With an rwsem, only one thread 
would be able to add or remove a node at a time, and only when no other 
thread was using the list.  Considering that klists are currently used 
to hold:

	the set of all devices on a bus,

	the set of all drivers for a bus, and

	the set of all children of a device,

	(not counting the set of all devices bound to a driver, since
	there's already a patch to replace that with a mutex-protected
	regular list)

this limitation on adding or removing doesn't seem significant.  There
aren't many places where these lists are iterated over or altered.  We
could remove most of the overhead associated with klists and get rid of an
extra API for people to learn.

Note that this would be very different from the old bus subsystem rwsem.  
That protected too much -- everything associated with the bus subsystem -- 
making it a pronounced chokepoint.  My suggestion involves a separate 
rwsem for each of these lists, so that none of them would be subject to 
much contention.

Alan Stern

Re: Whither klists?

[Christoph Hellwig]

On Thu, Sep 01, 2005 at 02:09:19PM -0400, Alan Stern wrote:
> Patrick and Greg:
> 
> To put it baldly: Should klists be replaced with regular lists, each 
> protected by an rwsem (or even a mutex)?
> 
> The advantage of klists is that threads can remove or add nodes while 
> other threads iterate through the list.  With an rwsem, only one thread 
> would be able to add or remove a node at a time, and only when no other 
> thread was using the list.  Considering that klists are currently used 
> to hold:
> 
> 	the set of all devices on a bus,
> 
> 	the set of all drivers for a bus, and
> 
> 	the set of all children of a device,
> 
> 	(not counting the set of all devices bound to a driver, since
> 	there's already a patch to replace that with a mutex-protected
> 	regular list)
> 
> this limitation on adding or removing doesn't seem significant.  There
> aren't many places where these lists are iterated over or altered.  We
> could remove most of the overhead associated with klists and get rid of an
> extra API for people to learn.
> 
> Note that this would be very different from the old bus subsystem rwsem.  
> That protected too much -- everything associated with the bus subsystem -- 
> making it a pronounced chokepoint.  My suggestion involves a separate 
> rwsem for each of these lists, so that none of them would be subject to 
> much contention.

Might also be worth to do a micro-benchmark for it (maybe in userland).
The current klist code is far too complex for it's own good.