The recent Arqua analysis of the Linux kernel has generated a few questions to me on how to untangle tangled dependencies. Here are a few ways to invert dependencies in C using function pointers.

Let’s have a look at a simple example of a system with two files:

Client.c

void clientNotify(int notification)
{
    printf("Notification %i\n", notification);
}

static void clientDoAction()
{
    serverDoAction(4);
}

int main()
{
    clientDoAction();

    return 0;
}

Server.c

void serverDoAction(int notifications)
{
    int i;

    for (i = 0; i < notifications; i++) {
        clientNotify(i);
    }
}

The server here notifies the client of an action as many times specified in the parameter to serverDoAction. When running Arqua on this system we get the following result:

As we can see in the image the two files Server and Client has a tangled dependency. It is because the notification back to the client is a static direct call to the client function notifyClient. This type of dependency is not healthy because of several reasons:

• The server can only server one static client and is not reusable.
• The server is not testable without that specific client. Isolating the code for mocking becomes impossible. Strictly speaking this is an important special case of reusability.
• Both files needs to be understood in order to do changes to only one. If not, the risk to introduce recursive calls, memory leaks etc. increases. The control abstraction made when creating the two files has thus failed. It could still be a relevant data abstraction, protecting internal types.

This tangle can easily be resolved using dependency inversion. In C dependency inversion can be done using function pointers. In our example we need to make sure that the server somehow gets a function pointer to call at notification time. The trick is to find a good way to pass this function pointer on to the server. There are a few ways to do this:

• Statically initialize the server with the function pointer
• Passing the function pointer to the server function as a parameter
• Creating a server instance and pass the function pointer as a parameter to the constructor of the server.

Static initialization

The simplest way to invert the dependency while keeping the existing API is to initialize the server at startup with all its needed dependencies. In our case we need to initialize it with a function pointer type. This is done in the new function serverInit. This function stores the globally initialized function pointer in the variable gNotifier:

static void(*gNotifier)(int) = 0;

void serverInit(void(*notifier)(int))
{
    if (notifier) {
        gNotifier = notifier;
    }
}

The globally set function pointer now needs to be used by serverDoAction. We need to change the direct call to clientNotify to a call to the variable gNotifier instead, giving us this new serverDoAction function:

void serverDoAction(int notifications)
{
    int i;

    for (i = 0; i < notifications; i++) {
        gNotifier(i);
    }
}

The usage of the server is still the same, however we need to make sure that initServer is called before we start to use serverDoAction. In a real system this type of static initialization is more commonly setup outside of the client in a separate subsystem responsible for system wiring. In our limited example we can instead add this to the main function in the client file:

int main()
{
    serverInit(clientNotify);
    clientDoAction();

    return 0;
}

These changes now gives us a different result when running Arqua on the system:

As we can see the dependency from the server to the client has now been removed and the structural quality is up to 100%.

It is possible to create a more robust server component by making sure that gNotifier is always initialized to a real function doing nothing, similar to the Null Object Pattern:

static void serverNullNotifier(int a)
{
    //Default behavior
}

static void(*gNotifier)(int) = serverNullNotifier;

Now calling the server will always work, even if we have not changed the default behavior in serverNullNotifier.

The static initialization method makes the server independent of the client and enable us to test the server isolated. It is however the most primitive of the three methods. In a big system it is easy to make the mistake of having multiple clients who tries to initialize and use the server. Some systems uses a system wiring subsystem to be the only one to initialize but for a less error prone and reusable server we need to take it a step further.

Function Pointer Parameter

If we really would like to be able to call the server from multiple clients the static initialization method is not enough. To enable this we need to change the way we interact with the server. The first option is to change the function serverDoAction only, adding the function pointer as a new parameter:

void serverDoAction(void(*notifier)(int), int notifications)
{
    int i;

    for (i = 0; i < notifications; i++) {
        notifier(i);
    }
}

The function serverDoAction now calls the parameter notifier instead of doing the static call to clientNotify. The client also needs to be changed since the signature of the server function has changed. Now we send clientNotify as a parameter instead:

static void clientDoAction()
{
    serverDoAction(clientNotify, 4);
}

Running Arqua again gives us another result:

Again we have removed the tangle and in this case we have only one dependency from client to server since we have no static initialization call.

Server Instances

Another way to enable multiple clients is to rewrite the static server into a server object that can be instantiated for each client. This becomes extra handy when:

• Having multiple function pointers that the server needs to call.
• Needing to share server behavior between clients, where some can even be agnostic to what notifier is being used, as a primitive form of polymorphism.

When implementing support for server instances we need a few more server functions; a constructor and a destructor, using a new server object type:

struct _Server {
    void(*notifier)(int);
};

Server *serverCreate(void(*notifier)(int))
{
    Server *server = malloc(sizeof(Server));

    if (server) {
        server->notifier = notifier;
    }
    return server;
}

void serverDestroy(Server *server)
{
    free(server);
}

The doServerAction now needs to operate on this new server object type, calling the member notifier instead of clientNotify:

void serverDoAction(Server *server, int notifications)
{
    int i;

    for (i = 0; i < notifications; i++) {
        server->notifier(i);
    }
}

The client also needs to be changed, now to create, destroy and use the new server object type:

static void clientDoAction(Server *server)
{
    serverDoAction(server, 4);
}

int main()
{
    Server *server = serverCreate(clientNotify);
    clientDoAction(server);
    serverDestroy(server);

    return 0;
}

Note that the client internal function clientDoAction does not have to know anything about what notifier being used. In the case of using function pointers as parameters this was not possible. We can now create independent client subsystem that cares only about when serverDoAction should be called and not what the server instance will do.

Running Arqua a last time on this system gives us another result:

Example From The Linux Kernel

Let’s go back to the Arqua analysis of the Linux kernel and take a look at the kernel/power directory:

The quality of each file looks good, but there is a tangle between the files main.c and suspend.c. Arqua reports the two dependencies from main.c to suspend.c as the bad dependencies. This is just a guess; Arqua assumes that the smaller dependency of the two is the cause of the tangle. When we look in the files we can see that we have the following dependencies from main.c to suspend.c:

• state_store calls pm_suspend
• state_show calls valid_state

The dependencies in the opposite direction looks like this:

• suspend_finish calls pm_notifier_call_chain
• suspend_prepare calls pm_notifier_call_chain twice

Now, it is actually possible to invert any of the dependencies between these files. Especially in the case of only having a few dependencies in each direction it might not be obvious what to do. Often the dependency is caused by a larger structural problem. When looking at the whole power subsystem it becomes clear that a bigger refactoring is really needed to resolve this in a good way, but for the sake of the example, let’s just focus on the tangle itself and not the big picture. Let’s try an use an easy way to resolve these dependencies, using the static initialization method above:

Looking at main.c again we see that pm_init is called when the system is started. We can let this function initialize suspend.c also, and add the injection of pm_notifier_call_chain here:

static int __init pm_init(void)
{
    ...

    suspend_init(pm_notifier_call_chain);

    ...
}

The suspend_init function needs to be declared in suspend.h. The input parameter to suspend_init is a function pointer matching the signature of pm_notifier_call_chain:

extern void suspend_init(int(*notifier)(unsigned long));

The new suspend_init function in suspend.c will look like this:

static int(*notifier)(unsigned long) = NULL;

void __init suspend_init(int(*init_notifier)(unsigned long))
{
    notifier = init_notifier;
}

Last thing to do is to remove the static calls to pm_notifier_call_chain:

error = pm_notifier_call_chain(PM_SUSPEND_PREPARE);

to a call to the injected dependency:

error = notifier(PM_SUSPEND_PREPARE);

Running an Arqua analysis again gives us a report without the previous tangle:

The Q score has increased, from 84% to 92%, and the structure of the directory has now been slightly improved.

Summary

Any tangled dependency can be untangled using dependency injection as in the examples above. It usually creates a much clearer separation of responsibilities and more reusable code. When untangling a structure it is important to look at the bigger picture and really see what the problem at hand is. In the kernel example above the tangle has indeed been resolved, however the configuration of the system is still equally complex, activating other parts of the system such as hibernation exposes even more similar tangles etc. Continuously working with keeping a system untangled eventually gives the experience needed to make the right refactoring decisions.