kobj multiple inheritance

[Doug Rabson]

On Mon, 2003-09-22 at 21:45, Justin T. Gibbs wrote:
> > On Mon, 2003-09-22 at 20:50, Justin T. Gibbs wrote:
> >> > I believe that I have the kobj multiple inheritance changes about ready
> >> > for committing now. I have locked up the class handling in kobj and I've
> >> > re-done the method dispatch so that it is MP-safe without needing locks
> >> > (I would appreciate a close look at that part by another pair of eyes).
> >> 
> >> I've only just glanced at these patches, but I don't see how the
> >> method cache is now MP safe.  Aren't you still vulnerable to a cache
> >> collision from two different threads performing an operation on the
> >> same class?
> > 
> > Thats the cunning part :-). The key is that the cache entries now point
> > directly at the method structures instead of being copies of the
> > structure. The main race condition theoretically present in the old code
> > was that one thread could read a cache entry part way through that entry
> > being updated by another thread. Since the cache entries are now simple
> > pointers, that can't happen.
> 
> The code assumes that pointer accesses are atomic, which I didn't
> think was guaranteed on all machines we support.  That's why I didn't
> think it was safe.

I think that we are guaranteed that a pointer read from a memory
location will be a whole copy of some value written to that location
(i.e. not a combination of part of one write with part of another) That
might not be true for bde's exotic i386/64bit long platform.

With this scheme, a cache entry will always be either NULL or will point
at some instance of struct kobj_method. A thread performing a lookup
will read the cache entry once and then simply work with the pointer it
has read. That value will either be NULL or will point at a read-only
structure (i.e. one which some other thread is guaranteed not to
change). If the value read from the cache is the right one (has the
right desc pointer), we have a hit. At this point, it doesn't matter if
another thread writes to the cache entry, we are using a copy of the
pointer which it contained so we are safe from anything another thread
might do to the cache.

On the other hand, if the value read was NULL or had the wrong desc
pointer, we do the slow lookup. This slow lookup does all of its work
with read-only structures and is also safe from other threads. The last
thing it does is write the value it found to the cache (note that this
is simply to help subsequent lookups - we don't read back from the cache
so it doesn't matter if something else is written to our cache entry.
The value from the slow lookup is returned in a register and the
function is called.

If two threads look up the same method simultaneously, they will both
write the same value to the cache entry and will both call the same
function. If two threads collide for different methods, they will both
write different entries but will still call the right function. It would
be theoretically possible for a pathological case to end up doing the
slow lookup in that case more often than normal but I would be surprised
if that ever happened in the wild.

I could possibly shave an instruction off the inline lookup code by
initialising each cache entry to point at a bogus method structure
instead of initialising it to NULL.

> 
> >> I still believe that the concept of inherited interfaces is better
> >> way to achieve multiple inheritance.  The methods I may want to
> >> inherit need not be associated with what we currently call a device
> >> class.  The nice thing about your approach is that it doesn't require
> >> a massive rototilling of the drivers, but I fear it doesn't go far
> >> enough toward providing flexible inheritence.
> > 
> > It was the mass rototilling which I wanted to avoid. It still seems like
> > a pretty good thing to maintain some kind of API compatibility between
> > FreeBSD 4, 5 and 6 and this method can support that. Your original
> > scheme was 'single inheritance of multiple interfaces'. This patch can
> > support that since you can derive from as many base classes as you like
> > - each base class will be looked at if the previous class doesn't find a
> > match.
> 
> There were quite a few differences:
> 
> 1) Inheritence was not limited to only inheriting from a base interface.
>    The method lookup traversed all the way to the root.

This proposed scheme also traverses through base classes of base classes
up to the roots.

> 
> 2) Default methods were removed and classes were forced to explicitly
>    list supported interfaces.  I found this to be much less confusing.

This is a pretty good idea. It might be a good idea to take this in a
few steps - i.e. get the basic MI into the system and stable. Then add
some handy base classes containing the various default methods. After
all the drivers are updated to use those base classes, remove the
support for default methods.

> 
> 3) Short-hand for inheriting all of the interfaces of a "parent class"
>    were provided.  This just meant having the ability to list classes
>    to inherit from so that the kobj class compiling code could iterate
>    through all the interfaces of specified classes.
> 
> 4) The method cache was removed in favor of a direct indexing into
>    the interface's static method table.  Interface lookup was explicit,
>    the hope being that one interface lookup could be amortized over
>    multiple method calls.  This would allow using kobj interfaces
>    for more heavy weight tasks such as exporting the correct XPT
>    interface in CAM to low-level drivers (FC, SPI, SATA, SAS, etc).

Interface lookup using current kobj can be done expliticly. There is
nothing to say that you must call the generated inline function - you
can just as well call KOBJOPLOOKUP yourself e.g. if you need to call the
method a few hundred thousand times. Given that the amortised cost of
calling a kobj method is only about 20% slower than a direct function
call, this kind of thing should only be needed in extreme cases.

> 
> 5) I also planned to add a way to do "super" invocations.  This would
>    cut down on lots of the bloat in things like cardbus.

I've been thinking a bit about that. In C++, the normal way is to
explicitly call the base method:

	void foo() {
		do important stuff;
		BaseClass::foo();
		OtherBaseClass::foo();
	}

This version is easy and is what cardbus does now. You simply export the
function and call it directly. This is what happens for instance in
cardbus_read_ivar - it handles its own variables and then calls
pci_read_ivar for everything else.

It would be possible to do something with dynamic lookups using the ops
cache of the base class but I haven't thought of a way of presenting the
API which isn't messy.

> 
> The goal was to be able to do things like, using cardbus as an example,
> inheret all of the interfaces of PCI adding in the CIS parsing interface
> shared with pccard.  CIS parsing is just a list of methods that doesn't
> make sense to be a "driver class" on its own.

I think that you can do exactly this with what I've proposed.

> 
> I guess I have bigger dreams than most for how to use newbus...

Big dreams are good :-)

> 
> Do you also have a proposal for handling ivar in the multiple-inheritance
> scheme?  This is required to make multiple inheritance really useful.

Off the top of my head, assign ranges to drivers at compile time in such
a way that the ivar indices of one driver are guaranteed to be different
from the indices of another driver. Requires a centralised registry but
we have one - the CVS repository would serve.