c preprocessor - How can I implement a dynamic dispatch table in C

Question

First of all, I understand how to implement a dispatch table using function pointers and a string or other lookup, that's not the challenge.

What I'm looking for is some way to dynamically add entries to this table at compile time.

The type of code structure I'd hope for is something like:

Strategy.h - contains function definition for the dispatcher and dispatch table definition Strategy.c - contains code for dispatcher

MyFirstStrategy.c - includes Strategy.h and provides one implementation of the strategy MyOtherStrategy.c - includes Strategy.h and provides a second implementation of the stratgy

The idea is that the code to insert function pointers and strategy names into the dispatch table should not live in Strategy.c but should be in the individual strategy implementation files and the lookup table should be somehow dynamically constructed at compile time.

For a fixed size dispatch table, this could be managed as below but I want a dynamically sized table, I don't want the Strategy.c implementation to have to include all of the header files for the implementations and I'd like the dispatch table to be constructed at compile time, not run time.

Fixed Size Example

Strategy.h

typedef void strategy_fn_t(int);
typedef struct {
    char           *strategyName;
    strategy_fn_t  *implementation;
} dispatchTableEntry_t;

MyFirstStrategy.h

#include "Strategy.h"

void firstStrategy( int param );

MyOtherStrategy.h

#include "Strategy.h"

void otherStrategy( int param );

Strategy.c

#include "Strategy.h"
#include "MyFirstStrategy.h"
#include "MyOtherStrategy.h"

dispatchTableEntry_t dispatchTable[] = {
    { "First Strategy", firstStrategy },
    { "Other Strategy", otherStrategy }
};
int numStrategies = sizeof( dispatchTable ) / sizeof(dispatchTable[0] );

What I really want is some preprocessor magic which I can insert into the strategy implementation files to handle this automatically e.g.

MyFirstStrategy.c

#include "Strategy.h"

void firstStrategy( int param );

ADD_TO_DISPATCH_TABLE( "First Strategy", firstStrategy );

Any thoughts ?

Answer 1

On systems with gnu linker and compiler or something compatible, it's possible to put certain objects in different sections. The linker will then generate symbols for the start and end of the section. Using that you can put all your structs into that section in different objects, the linker will consolidate those sections when linking and you can access them as an array. This requires a lot more fiddling if you're doing this in shared libraries and is definitely not portable outside of ELF Linux/*BSD.

I've done a similar thing (although this example will not work) on MacOS and a.out BSD, but I've lost that code. Here's an example of how to do it that works on Linux:

$ cat link_set.c
#include <stdio.h>

struct dispatch_table {
    const char *name;
    void (*fun)(int);
};

#define ADD_TO_DISPATCH_TABLE(name, fun) 
    static const struct dispatch_table entry_##fun 
        __attribute__((__section__("link_set_dispatch_table"))) = 
        { name, fun }

int
main(int argc, char **argv)
{
    extern struct dispatch_table __start_link_set_dispatch_table;
    extern struct dispatch_table __stop_link_set_dispatch_table;
    struct dispatch_table *dt;

    for (dt = &__start_link_set_dispatch_table; dt != &__stop_link_set_dispatch_table; dt++) {
        printf("name: %s
", dt->name);
        (*dt->fun)(0);
    }
    return 0;
}

void
fun1(int x)
{
    printf("fun1 called
");
}
ADD_TO_DISPATCH_TABLE("fun 1", fun1);

void
fun2(int x)
{
    printf("fun2 called
");
}
ADD_TO_DISPATCH_TABLE("fun 2", fun2);
$ cc -o link_set link_set.c
$ ./link_set
name: fun 1
fun1 called
name: fun 2
fun2 called
$

To explain what the macro does. It creates a struct dispatch_table with a name that we hope is unique since you might want to use it multiple times in one object (if you use the same function multiple times, figure out some other way to name the struct) and defines it with the gnu extension to specify which section the object should end up with. If we put the objects into "some_section_name" then the linker will automatically add symbols __start_some_section_name and __end_some_section_name. We can then walk between those symbols and get all the structs we put into that section.

Updated with a working example for MacOS:

#include <stdio.h>
#include <mach-o/ldsyms.h>
#include <mach-o/getsect.h>
#include <mach-o/loader.h>

struct dispatch_table {
        const char *name;
        void (*fun)(int);
};

#define ADD_TO_DISPATCH_TABLE(name, fun) 
    static const struct dispatch_table entry_##fun 
    __attribute__((__section__("__DATA,set_dt"))) = 
    { name, fun }

int
main(int argc, char **argv)
{
        struct dispatch_table *start;
        unsigned long sz;
        intptr_t s;
        int i;

        s = (intptr_t)getsectdata("__DATA", "set_dt", &sz);
        if (s == 0)
                return 1;
        s += _dyld_get_image_vmaddr_slide(0);
        start = (struct dispatch_table *)s;
        sz /= sizeof(*start);

        for (i = 0; i < sz; i++) {
                struct dispatch_table *dt = &start[i];
                printf("name: %s
", dt->name);
                (*dt->fun)(0);
        }
        return 0;
}

void
fun1(int x)
{
        printf("fun1 called
");
}
ADD_TO_DISPATCH_TABLE("fun 1", fun1);

void
fun2(int x)
{
        printf("fun2 called
");
}
ADD_TO_DISPATCH_TABLE("fun 2", fun2);

The section has to be called "set_dt" here because section names are limited in length in this executable format.

Of course, if you've come as far as needing this you surely understand that this is all very dangerous, unportable, not guaranteed to work ever (the code I had from three years ago didn't work on a current version of macos), has no type or other safety and if something else decides to put things into a section with the same name things will end up in very pretty fireworks. But it's a very neat trick. I use this method in two large projects and it really saves a lot of work central dispatch tables don't have to be edited in a shared repository which used to give everyone conflicts.