kobj multiple inheritance

[Doug Rabson]

On Mon, 2003-09-22 at 23:24, Justin T. Gibbs wrote:
> >> 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.
> 
> Okay.  That was my only concern.  For some reason I thought that 
> some early Sparc64 machines only enforced load/store atomicity on 16bit
> entities and that was only true with some platform specific magic.

I thought that this was only a problem for locked read-modify-write
cycles. The kobj lookup scheme doesn't require any kind of locked memory
access.

> 
> >> 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.
> 
> I see the recursion now.

Recursion is necessary otherwise you can't guarantee that the base class
functions correctly.

> 
> >> 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.
> 
> The problem is not entirely that of speed.  The cache is large even
> for classes that may only export or use a few methods.  This also
> means that an active cache requires more than one cache line even
> if only a few methods are used repeatedly.  Lastly, the lookup
> code is a bit large for an inline.  All of this is fine for interfaces
> largely used for device configuration, but this makes the current
> scheme less interesting in, for example, a device driver's main code
> path.

It is true that the cache is often larger than the number of methods. I
have reduced its size in bytes by a factor of two with this patch though
so it currently stands at 2k bytes on a 32bit platform (4k on a 64bit
platform). This cost is per class though so its amortised over all the
instances of that class. Also, the cache should only exist for active
classes (i.e. classes with instances). Classes which don't have
instances have their caches freed.

On i386, the method dispatch with this patch is nine instructions for
the common case (cache hit) plus six instructions for the uncommon case
(cache miss). I think I can shave the common case down to seven
instructions. This doesn't sound too expensive to me and like I said, if
you are calling a method several hundred thousand times, you could
consider cacheing the result of KOBJOPLOOKUP.

> 
> >> 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.
> 
> Yes.  This is one of the sore points of C++.  You shouldn't have to
> know where a method implementation resides in order to call it.  It
> makes it difficult in add layers to a class or interface hierarchy
> since all consumers of a moved method must be updated.

Unfortunately, when you have multiple base classes, there is no general
way of deciding which hase class to use for your 'super'. I haven't
found the explicit naming of the base class to be much of a problem when
writing in C++ (and I've written a lot of code in C++ over the last few
years).

> 
> > 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.
> 
> A method typically knows the interface that it belongs to.  At interface
> compile time, super methods could be recorded into an alternate method
> table within the interface.  This would allow chained super calls all the
> way to the root without having to explicitly walk interface pointers or do
> cache lookups.  The only time you then need to massively update the code is
> if you move a method that makes use of the super feature to a different
> interface.

This works when you have the 'single inheritance of multiple interfaces'
scheme supported by your original work. I'm not quite sure how it would
work when you have multiple base classes, all of which could potentially
implement the method.

> 
> >> 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.
> 
> This doesn't work well for binary only modules that create their own
> interfaces.  Ivars should work even in this case.  I also hope to avoid
> having large sparce ivar tables if possible.  My current thought is
> to use variables for the ivar indexes within an interface so that any
> offsets needed to deal with parent interfaces can be made during interface
> registration.  This becomes easier to deal with in the interface scheme
> since, with classes able to inherit from multiple interfaces, there is
> no need for interfaces to be polymorphic, so it is easy to determine how
> much space to allocate for the parent interface.  The same scheme could
> be used for method table allocations.

Hmm. Some kind of SYSINIT-driven ivar index allocator, perhaps?