[KinoSearch] Towards a stable C API... via indirect dispatch

[Marvin Humphrey]

On Oct 30, 2007, at 2:47 PM, Nathan Kurz wrote:

> You are probably familiar with it, but the offsetof() macro
> may useful for generating  these offsets.

Thanks for the reminder.  offsetof() will come in handy, but it can't  
be used for measuring all the offsets for this particular design.   
The revised kino_VirtualTable struct looks like this:

     struct kino_VirtualTable {
         kino_VirtualTable *_;
         KINO_OBJ_MEMBER_VARS;
         kino_VirtualTable *parent;
         const char        *class_name;
         size_t             byte_size;
         kino_method_t      methods[1]; /* flexible array */
     };

The methods will all be poured into the methods[] array at runtime  
during a bootstrap operation -- so offsetof() won't help there.  All  
of the "subclasses" of kino_VirtualTable -- KINO_OBJ_VTABLE,  
KINO_SCORER_VTABLE and the like -- had actual members that you could  
take an offsetof() against; however, I think those are all going to  
go away.  KINO_OBJ, KINO_SCORER and the rest will all become  
kino_VirtualTable* objects.

> The Apache Portable Runtime
> might be worth checking for portabalized macros for this.  It also
> might be worth considering for its mmap support.

I looked into APR as Lucy was starting up.  At OSCON, I saw Garrett  
Rooney give a talk on it; I was especially interested because he was  
the first person I know of to attempt a port of Lucene to C (the now- 
defunct "Lucene4C" project at Apache).

First, APR did way, way, WAY more than we needed.  Second, I wasn't  
enthused about e.g. how it made you pass around apr_pool_t objects  
everywhere.  Third, PTSD from trying to install Subversion and going  
through hell with conflicting versions of apr/apr-util/apr-whatever  
colored my judgment some, though that might have been Subversion's  
fault rather than APR's.  :)  In the end, it seemed too heavyweight  
to clear the high bar I set for adding dependencies.

> The Linux kernel builds on this to add container_of, which may or may
> not help as well. Here's a blog post that talks about its use within
> the VFS, which I referred to earlier:
> http://modal-echoes.blogspot.com/2007/03/implementing-polymorphism- 
> in-c.html

Interestingly, that's pretty close to how OO works in the maint  
branch of KS.  For instance, here's the definition of the Scorer struct:

     typedef struct scorer {
         void       *child;
         Similarity *sim;
         float     (*score)(struct scorer*);
         bool      (*next)(struct scorer*);
         U32       (*doc)(struct scorer*);
         bool      (*skip_to)(struct scorer*, U32);
         SV         *similarity_sv;
     } Scorer;

TermScorer, PhraseScorer, etc, all fill in their own "child" struct.

Shared vtables a la Boilerplater/C++/Java are much more compact,  
allowing you to add many more methods, basically for free.

>> This is the assembler we should see when attempting to load the
>> correct function pointer:
>>
>>      movl    self, %edx          # load self into %edx
>>      movl    method_OFFSET, %eax # load method_OFFSET into %eax
>>      addl    (%edx), %eax        # add the address of self->_ to %eax
>
> Realize that things are going to be a little less efficient once you
> are using a shared library.  I think the method_OFFSET variable is
> going to require another level of indirection to allow for the symbol
> relocation.  But I'm fuzzy on this.

True.  (grrr.)

It'll look something like this when compiled with fpic/fPIC:

     movl    self, %edx                    # Load self into %edx.
     movl    method_OFFSET at GOT(%ebx), %eax # Load Global Offset Table
                                           #   pointer entry for
                                           #   method_OFFSET into %eax.
     movl    (%eax), %eax                  # Dereference method_OFFSET.
     addl    (%edx), %eax                  # Add the address of self->_.

I think that stuff'll get pipelined, though -- so as long as the  
vtables, the OFFSET vars, and the GOT don't cause cache misses, I  
don't think the penalty will be severe.

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/




_______________________________________________
KinoSearch mailing list
KinoSearch at rectangular.com
http://www.rectangular.com/mailman/listinfo/kinosearch