Link-time Memory Allocation in C

Imagine you have a series of callback functions that you want your program to execute at some point. Ideally you would like to iterate over an array of function pointers, calling each one in turn. The problem is that each callback might be in a different file, and the total number of callbacks might be subject to change. You might allocate memory for the array dynamically at runtime, but this incurs significant overhead. A better solution would be to allocate memory at compile time since the total number of callbacks is known and you would avoid the overhead of dynamic allocation. Such a solution is tedious because it requires you to count the number of callbacks and adjust the code every time you compile your program.

One possible solution is link-time allocation.

This involves placing a pointer to each callback in a special section and using linker variables to get the size of the section at link-time. The overhead of dynamic allocation and the tedium of static allocation are both avoided.

As an example, let's consider the case of unit testing. Perhaps you are like me, and you don't want to use a bloated library just to run a few tests on a small project. The number of unit tests is subject to change and you don't want to count them up each time. You want a way to just write a test and have it automatically execute.

Let's make a file unittest.h and add the usual header guards and a segment of code defining our function pointers:

#ifndef UNITTEST_H
#define UNITTEST_H

typedef int (*unit_test_ptr)(void);
typedef struct func_ptr_s {
   unit_test_ptr test_function;
} func_ptr_t;

#endif  

Based on this, each unit test function will take no arguments and return an integer. In keeping with tradition, a return value of zero will indicate success (i.e. a passing test).

We now need a way to declare each unit test, create a pointer to it, and store that pointer in a special section. Add the following to unittest.h:

/* This will ensure each function pointer gets a unique name */
#define CONCAT(a, b) CONCAT_INNER(a, b)
#define CONCAT_INNER(a, b) a ## b
#define UNIQUE_NAME(base) CONCAT(base, __LINE__)

#define UNIT_TEST_START(testname)      \
int testname (void) {                  \
   printf("Testing: " #testname" | "); \
   if (1)

#define UNIT_TEST_END(testname) } ADD_FUNC(testname)

/* Where the magic happens */
#define ADD_FUNC(testfunc)                        \
   static func_ptr_t UNIQUE_NAME(ptr_ ##testfunc) \
   __attribute__((used, section("testfunctions"))) = { .test_function = testfunc }

This indicates that we would write our unit tests in the following way:

UNIT_TEST_START(my_test)
{
   /* Test code here */
} UNIT_TEST_END(my_test);

The first macro will start the function definition for our test. The second macro will create a function pointer to our test, give it a unique name, and put it in a linker section called "testfunctions".

At this point we could create a new source file containing our unit tests, but we don't have a way to actually call them yet. Let's create a new macro to do that for us. Again, in unittest.h:

#define SECTION_DO_CALLBACKS(section_name, type_t, elem)         \
   for (type_t *elem = ({                                        \ 
                            extern type_t __start##section_name; \
                            &__start##section_name;              \
                       });                                       \
        elem !=        ({                                        \
                            extern type_t __stop##section_name;  \
                            &__stop##section_name;               \
                       });                                       \
        ++elem)

All this is saying is to create a for loop which will start at the address of __start##section_name and stop once it reaches __stop##section_name. But what are these variables? These are linker variables - we will declare them shortly. In the meantime, remember that section called 'testfunctions' where we put all our function pointers? Let's create a new file called unittest.c. We'll create a function called add and a test for it. We'll use SECTION_DO_CALLBACKS to iterate over the pointers in the 'testfunctions' section and call them in turn.

unittest.c:

#include "unittest.h"
#include <stdio.h>

int
add(int a, int b)
{
   return a + b;
}

UNIT_TEST_START(test_add)
{
   if (add(3, 5) != 8) { return 1; }

   return 0;
} UNIT_TEST_END(test_add);

int
main(void)
{
   SECTION_DO_CALLBACKS(testfunctions, func_ptr_t, entry) {
      int test_result = entry->test_function();
      if (test_result) {
         printf("FAIL\n");
      } else {
         printf("PASS\n");
      }
   }

   return 0;
}

Observe that all we would need to do to add new unit tests is create a new UNIT_TEST_START and UNIT_TEST_END with our test code in between them. We don't need to count the functions in any way or allocate any dynamic memory.

There remains just one thing to do before we will have working code. Recall that we are still missing two linker variables. With the way SECTION_DO_CALLBACKS is used, these would be __starttestfunctions and __stoptestfunctions. Since these are linker variables, we need to create a linker script. If you already have one for your project, you can use that, otherwise you can spit out the default script from your GCC with:

gcc -Wl,-verbose > linker.ld

Within linker.ld, there will be a line near the beginning consisting only of equals symbols, and another line near the end of the file which is the same. Delete everything that isn't between those two lines.

Then, find the data section, it will look something like this:

.data    :
{
  PROVIDE (__data_start = .);
  /* Some more stuff here */
}

Right after the data section (after the close brace), add the following piece of code. This will create a new section called testfunctions and put the symbols __starttestfunctions and __stoptestfunctions at the beginning and end:

__starttestfunctions = .;
.testfunctions    :
{
  *(.testfunctions)
}
__stoptestfunctions = .;

 Finally, when we invoke the compiler we must pass it the new linker script:

gcc -o test unittest.c -T linker.ld

Sample output:

Testing: test_add | PASS