Elimination of klists

Elimination of klists

[Alan Stern]

James:

I noticed that you recently posted some updates to the klist code, 
although I haven't looked to see how you are using the klists.

What do you think about eliminating klists entirely, and instead using 
regular lists protected by either a mutex or an rwsem?  It would remove a 
good deal of overhead, and I think it wouldn't be hard to convert the 
driver core.  Would this be feasible for the things you're doing?

Alan Stern

Re: Elimination of klists

[James Bottomley]

On Sun, 2005-09-11 at 15:35 -0400, Alan Stern wrote:
> I noticed that you recently posted some updates to the klist code, 
> although I haven't looked to see how you are using the klists.

Yes, that was mainly to tie their reference counting model back to the
objects they actually embed.  It was just fixing a thinko in the
implementation rather than changing anything fundamental about them.

> What do you think about eliminating klists entirely, and instead using 
> regular lists protected by either a mutex or an rwsem?  It would remove a 
> good deal of overhead, and I think it wouldn't be hard to convert the 
> driver core.  Would this be feasible for the things you're doing?

Actually, the concept of a klist is quite nice, and the beauty is that
all the locking is internal to them, so users can't actually get it
wrong (I like interfaces like this).

Originally the driver model did precisely use an ordinary list and a
mutex.  The problem was that we entangled the mutex in the actions taken
by things like device_for_each_child() which caused deadlocks ... most
noticeably in the transport classes; klists got us out of this.

James

Re: Elimination of klists

[Andrew Morton]

James Bottomley <James.Bottomley@SteelEye.com> wrote:
>
> Actually, the concept of a klist is quite nice, and the beauty is that
>  all the locking is internal to them, so users can't actually get it
>  wrong (I like interfaces like this).

You're a bit screwed if you want to use them from interrupts..

Re: Elimination of klists

[James Bottomley]

On Sun, 2005-09-11 at 15:25 -0700, Andrew Morton wrote:
> James Bottomley <James.Bottomley@SteelEye.com> wrote:
> >
> > Actually, the concept of a klist is quite nice, and the beauty is that
> >  all the locking is internal to them, so users can't actually get it
> >  wrong (I like interfaces like this).
> 
> You're a bit screwed if you want to use them from interrupts..

Yes, but then they're for refcounted lists.  Quite a few of our
refcounted structures aren't safe for final put from interrupt either.
I take the implied point about wanting to leave the lock selection up to
the list head provider... I just can't see an elegant way of
implementing it given how tightly klist iterators have to bind to the
locking and refcounting.  We could always add another pair of
list_head_lock() list_head_unlock() functions which it's up to the
list_head provider also to supply ... I'm just surprised I didn't get
hammered for using that nasty OO concept of delegates with the get/put
functions ... I'm sure someone will notice if I do it a second time.

James


James

Re: Elimination of klists

[Alan Stern]

On Sun, 11 Sep 2005, James Bottomley wrote:

> On Sun, 2005-09-11 at 15:35 -0400, Alan Stern wrote:
> > I noticed that you recently posted some updates to the klist code, 
> > although I haven't looked to see how you are using the klists.
> 
> Yes, that was mainly to tie their reference counting model back to the
> objects they actually embed.  It was just fixing a thinko in the
> implementation rather than changing anything fundamental about them.

I'm not sure it was really a thinko.  Pat Mochel was well aware of the 
problem and just decided not to do anything about it.

> > What do you think about eliminating klists entirely, and instead using 
> > regular lists protected by either a mutex or an rwsem?  It would remove a 
> > good deal of overhead, and I think it wouldn't be hard to convert the 
> > driver core.  Would this be feasible for the things you're doing?
> 
> Actually, the concept of a klist is quite nice, and the beauty is that
> all the locking is internal to them, so users can't actually get it
> wrong (I like interfaces like this).

It's possible to make the locking internal to normal lists as well, if 
anyone wanted to do it.

> Originally the driver model did precisely use an ordinary list and a
> mutex.  The problem was that we entangled the mutex in the actions taken
> by things like device_for_each_child() which caused deadlocks ... most
> noticeably in the transport classes; klists got us out of this.

There's a big difference.  Originally the driver model used a _single_
rwsem that covered everything in a subsystem: all the devices, all the
drivers, and all the lists.  What I'm suggesting is using lots of rwsems
or mutexes, one for each list.  (The driver core has already added a
semaphore for each device.)  Being much finer-grained, it would not lead
to deadlock.


On Sun, 11 Sep 2005, Andrew Morton wrote:

> You're a bit screwed if you want to use them from interrupts..

Actually, in their original form klists could indeed be used in interrupt
contexts, since they involved only spinlocks.  That's not quite true any 
more.

And certainly replacing them with rwsem-protected lists won't make them 
any more interrupt-friendly.  On the other hand, as far as I know nobody 
wants to use them in interrupt contexts.

Alan Stern