7. The Global Allocator Object

Copyright 2020 Andy Curtis & Daniel Curtis

A quick note about C allocation methods:

In C, there are five basic functions for allocating memory (technically there are more, but they are rarely used).

void *malloc(size_t len);
void *calloc(size_t num, size_t len);
void *realloc(void *p, size_t len);
char *strdup(char *p);
void free(void *p);

The middle three functions essentially work as follows (although the internal implementation is more complex for performance reasons).

void *calloc(size_t num, size_t len) {
  void *res = malloc(num*len);
  memset(res, 0, num*len);
  return res;
}

void *realloc(void *p, size_t len) {
  size_t old_len = extract_length(p); // details of this function depend upon how malloc is implemented
  void *res = malloc(len);
  if(len < old_len)
    memcpy(res, p, len);
  else
    memcpy(res, p, old_len);
  free(p);
  return res;
}

char *strdup(char *p) {
  size_t len = strlen(p)+1;
  char *res = (char *)malloc(len);
  memcpy(res, p, len);
  return res;
}

It's important to realize that malloc (memory alloc) is the core behind all of these functions or at a minimum, they are derivates of malloc.

One of the reasons that people tend to steer clear of C is because you must maintain pointers to memory that you allocate so that it can later be freed. In the last chapter, I introduced doubly-linked lists. We can implement a way of tracking allocations using a doubly-linked list. The functions that we will implement are the ones defined above - so the interface will be pretty straight forward. To prevent naming conflicts, we will use the ac prefix.

#ifndef _ac_allocator_H
#define _ac_allocator_H

#include "ac_common.h"

void *ac_malloc(size_t len);
void *ac_calloc(size_t len);
void *ac_realloc(void *p, size_t len);
char *ac_strdup(char *p);
void ac_free(void *p);

#endif

You may notice that I don't use two parameters for ac_calloc. This is intentional as I don't see a benefit in changing the signature from malloc.

We could redefine our interface as

#ifndef _ac_allocator_H
#define _ac_allocator_H

#include <stdlib.h> /* for size_t */

void *ac_malloc(const char *filename, int line, size_t len);
void *ac_calloc(const char *filename, int line, size_t len);
void *ac_realloc(const char *filename, int line, void *p, size_t len);
char *ac_strdup(const char *filename, int line, char *p);
void ac_free(const char *filename, void *p);

#endif

and then call our functions like this.

sample.c (this won't work - because I'm not building the object this way in the end)

#include "ac_allocator.h"

int main( int argc, char *argv[] ) {
  char *s = (char *)ac_malloc(__FILE__, __LINE__, 100);
  ac_free(__FILE__, __LINE__, s);
  return 0;
}

There is a pattern above in that every time we call ac_malloc (and others), we would call it with FILE, LINE, as the first two parameters.

In creating the global allocator, maybe we only want line numbers and malloc to be passed in when the software is defined as being in debug mode. To define ac_malloc, we might want to do the following. Considering that we have just identified how to merge the FILE and LINE, we will use that.

#ifdef _AC_DEBUG_MEMORY_
#define ac_malloc(len) _ac_malloc_d(__AC_FILE_LINE__, len)
#else
#define ac_malloc(len) malloc(len)
#endif

void *_ac_malloc_d( const char *caller, size_t len );

When defining functions this way, it is good to come up with a convention. My convention is to use an underscore before the function and to suffix the debug function with _d. In defining the final interface, I came up with a few additional features. The first is based upon the idea that the allocator will use an internal object to represent its structure. That object will be global, and all of the allocation functions will have to pass a pointer to the object.

void *_ac_malloc_d( const char *caller, size_t len );

becomes

void *_ac_malloc_d( ac_allocator_t *a, const char *caller, size_t len );

The macro changes to.

#define ac_malloc(len) _ac_malloc_d(NULL, __AC_FILE_LINE__, len)

A NULL allocator simply means to use the global allocator.

The second feature is to allow for a mechanism to allow for custom content in place of the caller. For example, if we allocate a buffer and keep changing its size, we might want to know the following: where the buffer was initialized, the maximum size of the buffer, its initial size, etc. Passing a boolean at the end denotes this custom feature, which defaults to false.

void *_ac_malloc_d( ac_allocator_t *a, const char *caller, size_t len );

becomes

void *_ac_malloc_d( ac_allocator_t *a, const char *caller, size_t len, bool custom );

The macro changes to.

#define ac_malloc(len) _ac_malloc_d(NULL, __AC_FILE_LINE__, len, false)

If the custom feature is enabled, the objects need a way to dump their state to a file (or to the terminal). In C, you can define a function pointer and then associate the pointer to functions programmatically. An example is below. The gist of it is that you specify the new function pointer type by surrounding the name in parenthesis and an extra asterisk.

For example,

typedef void (*my_function)();

would declare a function pointer type named my_function, which took no arguments and didn't return anything (it has a void return type). I recommend using a suffix for function pointers (I'm going to use _f). The allocator needs to define a function pointer to allow other objects to dump their details.

typedef void (*ac_dump_details_f)(FILE *out, void *p, size_t length);

In C, the order of the members of a structure is also the byte order of the structure. This is often exploited to allow a structure to be able to be cast as a structure of a different type.

typedef struct {
  ac_dump_details_f dump;
  const char *caller;
} ac_allocator_dump_t;

Another useful feature is to have the state of the memory usage dumped every so often. All this means is that if ACDEBUGMEMORY is defined as a filename, any program which uses the allocator will record all of the memory allocations every N seconds and rotate the previous snapshot. To maintain a smaller number of output files, the rotations will rotate files with an ever-expanding gap between them.

The full allocator interface is below.

$ac/src/ac_allocator.h

#ifndef _ac_allocator_H
#define _ac_allocator_H

#include "ac_common.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef _AC_DEBUG_MEMORY_
#define ac_malloc(len) _ac_malloc_d(NULL, __AC_FILE_LINE__, len, false)
#define ac_calloc(len) _ac_calloc_d(NULL, __AC_FILE_LINE__, len, false)
#define ac_realloc(p, len) _ac_realloc_d(NULL, __AC_FILE_LINE__, p, len, false)
#define ac_strdup(p) _ac_strdup_d(NULL, __AC_FILE_LINE__, p)
#define ac_free(p) _ac_free_d(NULL, __AC_FILE_LINE__, p)
#else
#define ac_malloc(len) malloc(len)
#define ac_calloc(len) calloc(1, len)
#define ac_realloc(p, len) realloc(p, len)
#define ac_strdup(p) strdup(p)
#define ac_free(p) free(p)
#endif

typedef void (*ac_dump_details_f)(FILE *out, void *p, size_t length);

typedef struct {
  ac_dump_details_f dump;
  const char *caller;
} ac_allocator_dump_t;

struct ac_allocator_s;
typedef struct ac_allocator_s ac_allocator_t;

ac_allocator_t *ac_allocator_init();
void ac_allocator_destroy(ac_allocator_t *a);

void ac_dump_global_allocations(ac_allocator_t *a, FILE *out);

void *_ac_malloc_d(ac_allocator_t *a, const char *caller, size_t len, bool custom );

void *_ac_calloc_d(ac_allocator_t *a, const char *caller, size_t len, bool custom );

void *_ac_realloc_d(ac_allocator_t *a, const char *caller, void *p, size_t len, bool custom);

char *_ac_strdup_d(ac_allocator_t *a, const char *caller, const char *p );

void _ac_free_d(ac_allocator_t *a, const char *caller, void *p);

#endif

Before understanding the implementation, let's see how other objects and code use this. The ac_timer.h/c will change in the following way:

Include ac_common.h

ac_timer.h

#include "ac_common.h"

Replace

ac_timer_t *ac_timer_init(int repeat);

with

#ifdef _AC_DEBUG_MEMORY_
#define ac_timer_init(repeat) _ac_timer_init(repeat, AC_FILE_LINE_MACRO("ac_timer"))
ac_timer_t *_ac_timer_init(int repeat, const char *caller);
#else
#define ac_timer_init(repeat) _ac_timer_init(repeat)
ac_timer_t *_ac_timer_init(int repeat);
#endif

The above code has two basic cases: one where ACDEBUGMEMORY is defined, and one where it is not (#else). It may be easier to break this into a couple of steps.

  1. convert the init function to be prefixed with an underscore
ac_timer_t *ac_timer_init(int repeat);

becomes

ac_timer_t *_ac_timer_init(int repeat);
  1. create a macro which defines actimerinit as actimer_init

    #define ac_timer_init(repeat) _ac_timer_init(repeat)
    ac_timer_t *_ac_timer_init(int repeat);
  2. define the macro if logic with the else part filled in.

    #ifdef _AC_DEBUG_MEMORY_
    #else
    #define ac_timer_init(repeat) _ac_timer_init(repeat)
    ac_timer_t *_ac_timer_init(int repeat);
    #endif
  3. Add const char *caller to the debug version of actimer_init

    ac_timer_t *_ac_timer_init(int repeat, const char *caller);
  4. define the macro to call the init function.

    #define ac_timer_init(repeat) _ac_timer_init(repeat, AC_FILE_LINE_MACRO("ac_timer"))
  5. put the two calls in the #ifdef ACDEBUGMEMORY section.

    #ifdef _AC_DEBUG_MEMORY_
    #define ac_timer_init(repeat) _ac_timer_init(repeat, AC_FILE_LINE_MACRO("ac_timer"))
    ac_timer_t *_ac_timer_init(int repeat, const char *caller);
    #else
    #define ac_timer_init(repeat) _ac_timer_init(repeat)
    ac_timer_t *_ac_timer_init(int repeat);
    #endif

Objects will typically use the ACFILELINEMACRO("objectname") when defining the init call, as in step 5 above.

Change ac_timer.c from

ac_timer_t *ac_timer_init(int repeat) {
  ac_timer_t *t = (ac_timer_t *)malloc(sizeof(ac_timer_t));

to

#ifdef _AC_DEBUG_MEMORY_
ac_timer_t *_ac_timer_init(int repeat, const char *caller) {
  ac_timer_t *t =
    (ac_timer_t *)_ac_malloc_d(NULL, caller,
                                   sizeof(ac_timer_t), false);
#else
ac_timer_t *_ac_timer_init(int repeat) {
  ac_timer_t *t = (ac_timer_t *)ac_malloc(sizeof(ac_timer_t));
#endif
  1. Change all malloc, calloc, strdup, realloc, and free calls to have ac_ prefix.
  2. Change the function name from actimerinit to actimer_init.
  3. Wrap the block in a #ifdef ACDEBUGMEMORY/#else/#endif block
  4. Define the ACDEBUGMEMORY portion. The actimerinit function has the extra const char *caller parameter. The allocation uses _acmalloc_d directly, as shown above.

To test these changes out, I've modified code from $ac/illustrations/2timing/13timer

The following code is found in illustrations/6allocator/1timing

cd $ac/illustrations/6_allocator/1_timing
$ make
gcc -O3 -I../../../src -D_AC_DEBUG_MEMORY_=NULL ../../../src/ac_timer.c ../../../src/ac_allocator.c ../../../src/ac_buffer.c ../../../src/ac_pool.c test_timer.c -o test_timer
./test_timer ABCDEFGHIJKLMNOPQRSTUVWXYZ Reverse
ABCDEFGHIJKLMNOPQRSTUVWXYZ => ZYXWVUTSRQPONMLKJIHGFEDCBA
time_spent: 7.7260ns
Reverse => esreveR
time_spent: 1.8180ns
overall time_spent: 9.5440ns
99 byte(s) allocated in 4 allocations (160 byte(s) overhead)
test_timer.c:24: 27
test_timer.c:26 [ac_timer]: 32
test_timer.c:24: 8
test_timer.c:26 [ac_timer]: 32

Include acallocator.h in testtimer.c

#include "ac_allocator.h"

and alter the malloc and free calls to acmalloc and acfree. I've intentionally commented out several destroy calls and the ac_free call.

When make was run above, the following extra lines were output

99 byte(s) allocated in 4 allocations (160 byte(s) overhead)
test_timer.c:24: 27
test_timer.c:26 [ac_timer]: 32
test_timer.c:24: 8
test_timer.c:26 [ac_timer]: 32

This indicates that 4 allocations were not properly freed.

line 24

char *s = (char *)ac_malloc(len+1);

line 26

ac_timer_t *copy_timer = ac_timer_init(ac_timer_get_repeat(overall_timer));

To fix the code, we need to make sure that copy_timer is destroyed and s is freed. Lines 47-48 are what need uncommented to make this work.

// ac_timer_destroy(copy_timer);
// ac_free(s);

The error reported logged the actimerinit line as opposed to the acmalloc inside of actimer_init. This is likely more useful unless you are testing the individual object.

Go ahead and uncomment those lines and run make again

$ make
gcc -O3 -I../../../src -D_AC_DEBUG_MEMORY_=NULL ../../../src/ac_timer.c ../../../src/ac_allocator.c ../../../src/ac_buffer.c ../../../src/ac_pool.c test_timer.c -o test_timer
./test_timer ABCDEFGHIJKLMNOPQRSTUVWXYZ Reverse
ABCDEFGHIJKLMNOPQRSTUVWXYZ => ZYXWVUTSRQPONMLKJIHGFEDCBA
time_spent: 7.7260ns
Reverse => esreveR
time_spent: 1.8180ns
overall time_spent: 9.5440ns

Go ahead and revert your changes. You can revert your changes in the current directory by running the following git command. If you don't specify the ., then it will revert all changes in the whole repo (so this command can be somewhat dangerous!)

git checkout .

The lines indicating memory loss are no longer printed. In this example, ACDEBUGMEMORY was defined as NULL in the Makefile using the following line.

FLAGS += -D_AC_DEBUG_MEMORY_=NULL

If we change this to

FLAGS += -D_AC_DEBUG_MEMORY_=\"memory.log\"

run

make clean

and then

$ make
gcc -O3 -I../../../src -D_AC_DEBUG_MEMORY_=\"memory.log\" ../../../src/ac_timer.c ../../../src/ac_allocator.c ../../../src/ac_buffer.c ../../../src/ac_pool.c test_timer.c -o test_timer
./test_timer ABCDEFGHIJKLMNOPQRSTUVWXYZ Reverse
ABCDEFGHIJKLMNOPQRSTUVWXYZ => ZYXWVUTSRQPONMLKJIHGFEDCBA
time_spent: 5.9220ns
Reverse => esreveR
time_spent: 1.5720ns
overall time_spent: 7.4940ns

There is a new file called memory.log in this directory.

$ ls
Makefile	memory.log	test_timer	test_timer.c

You can view memory.log by running

$ cat memory.log
99 byte(s) allocated in 4 allocations (160 byte(s) overhead)
test_timer.c:24: 27
test_timer.c:26 [ac_timer]: 32
test_timer.c:24: 8
test_timer.c:26 [ac_timer]: 32

If you view the testtimer.c code, you will notice that a significant portion of the main function now has the ac prefix.

test_timer.c (main function)

int main( int argc, char *argv[]) {
  int repeat_test = 1000000;
  ac_timer_t *overall_timer = ac_timer_init(repeat_test);
  for( int i=1; i<argc; i++ ) {
    size_t len = strlen(argv[i]);
    char *s = (char *)ac_malloc(len+1);

    ac_timer_t *copy_timer = ac_timer_init(ac_timer_get_repeat(overall_timer));
    ac_timer_start(copy_timer);
    for( int j=0; j<repeat_test; j++ ) {
      strcpy(s, argv[i]);
    }
    ac_timer_stop(copy_timer);

    ac_timer_t *test_timer = ac_timer_init(ac_timer_get_repeat(overall_timer));
    ac_timer_start(test_timer);
    for( int j=0; j<repeat_test; j++ ) {
      strcpy(s, argv[i]);
      reverse_string(s, len);
    }
    ac_timer_stop(test_timer);
    ac_timer_subtract(test_timer, copy_timer);
    ac_timer_add(overall_timer, test_timer);

    printf("%s => %s\n", argv[i], s);
    printf( "time_spent: %0.4fns\n", ac_timer_ns(test_timer) );

    ac_timer_destroy(test_timer);
    // ac_timer_destroy(copy_timer);
    // ac_free(s);
  }
  printf( "overall time_spent: %0.4fns\n", ac_timer_ns(overall_timer) );
  ac_timer_destroy(overall_timer);
  return 0;
}

Breaking out all of the ac_ statements:

  ac_timer_t *overall_timer = ac_timer_init(repeat_test);
    char *s = (char *)ac_malloc(len+1);

    ac_timer_t *copy_timer = ac_timer_init(ac_timer_get_repeat(overall_timer));
    ac_timer_start(copy_timer);

    ac_timer_stop(copy_timer);

    ac_timer_t *test_timer = ac_timer_init(ac_timer_get_repeat(overall_timer));
    ac_timer_start(test_timer);

    ac_timer_stop(test_timer);
    ac_timer_subtract(test_timer, copy_timer);
    ac_timer_add(overall_timer, test_timer);

    ac_timer_destroy(test_timer);
    // ac_timer_destroy(copy_timer);
    // ac_free(s);
  ac_timer_destroy(overall_timer);

If you mentally note that ac is just a prefix and view the code as

timer_t *overall_timer = timer_init(repeat_test);
  char *s = (char *)malloc(len+1);

  timer_t *copy_timer = timer_init(timer_get_repeat(overall_timer));
  timer_start(copy_timer);

  timer_stop(copy_timer);

  timer_t *test_timer = timer_init(timer_get_repeat(overall_timer));
  timer_start(test_timer);

  timer_stop(test_timer);
  timer_subtract(test_timer, copy_timer);
  timer_add(overall_timer, test_timer);

  timer_destroy(test_timer);
  // timer_destroy(copy_timer);
  // free(s);
timer_destroy(overall_timer);

You can see that there are timer objects, malloc, and free. Given that malloc, calloc, realloc, strdup, and free are so common in code, I opted not to provide any extra qualifiers other than ac. I aim to make code highly optimized and very readable. Another important feature of qualified naming is that it makes it possible to search for all places something exists. For example, to find all cases where ac_timer are used, you can run..

cd $ac/illustrations
grep -rn ac_timer .

and your output might look like...

./2_timing/12_timer/test_timer.c:1:#include "ac_timer.h"
./2_timing/12_timer/test_timer.c:20:  ac_timer_t *overall_timer = ac_timer_init(repeat_test);
./2_timing/12_timer/test_timer.c:25:    ac_timer_t *copy_timer = ac_timer_init(ac_timer_get_repeat(overall_timer));
./2_timing/12_timer/test_timer.c:26:    ac_timer_start(copy_timer);
./2_timing/12_timer/test_timer.c:30:    ac_timer_stop(copy_timer);
./2_timing/12_timer/test_timer.c:32:    ac_timer_t *test_timer = ac_timer_init(ac_timer_get_repeat(overall_timer));
./2_timing/12_timer/test_timer.c:33:    ac_timer_start(test_timer);
./2_timing/12_timer/test_timer.c:38:    ac_timer_stop(test_timer);
./2_timing/12_timer/test_timer.c:39:    ac_timer_subtract(test_timer, copy_timer);
./2_timing/12_timer/test_timer.c:40:    ac_timer_add(overall_timer, test_timer);
./2_timing/12_timer/test_timer.c:43:    printf( "time_spent: %0.4fns\n", ac_timer_ns(test_timer) );
./2_timing/12_timer/test_timer.c:45:    ac_timer_destroy(test_timer);
./2_timing/12_timer/test_timer.c:46:    ac_timer_destroy(copy_timer);
./2_timing/12_timer/test_timer.c:49:  printf( "overall time_spent: %0.4fns\n", ac_timer_ns(overall_timer) );
./2_timing/12_timer/test_timer.c:50:  ac_timer_destroy(overall_timer);
./2_timing/12_timer/Makefile:2:OBJECTS=$(ROOT)/src/ac_timer.c
./2_timing/12_timer/Makefile:3:HEADER_FILES=$(ROOT)/src/ac_timer.h
Binary file ./2_timing/12_timer/test_timer matches
./2_timing/13_timer/test_timer.c:1:#include "ac_timer.h"
./2_timing/13_timer/test_timer.c:20:  ac_timer_t *overall_timer = ac_timer_init(repeat_test);
./2_timing/13_timer/test_timer.c:25:    ac_timer_t *copy_timer = ac_timer_init(ac_timer_get_repeat(overall_timer));
./2_timing/13_timer/test_timer.c:26:    ac_timer_start(copy_timer);
./2_timing/13_timer/test_timer.c:30:    ac_timer_stop(copy_timer);
...

This feature alone is extremely valuable when working with a large codebase. It takes longer to write each line of code, but the reader can easily find every line of code where the object is used. This makes it easier to find example code and to build upon the work of others.

A Quick Recap

  1. The 5 basic allocation methods in C are...

    void *malloc(size_t len);
    void *calloc(size_t num, size_t len);
    void *realloc(void *p, size_t len);
    char *strdup(char *p);
    void free(void *p);
  2. We define those functions with the ac_ prefix such that if we are debugging memory, we can track where the allocations are made. This allows us to recognize memory leaks and potentially a couple of other common errors.
  3. Callback functions should have a suffix of _f
  4. We defined an approach to find when objects are created (and not destroyed). The basic changes to actimer were outlined to make it support using the acallocator.
  5. When we are using the acallocator object outside of objects, the only change to the code is to replace the 5 basic allocation methods with `ac...` If, for some reason, you do not wish to allocate memory using the ac method, then make sure that you don't free it with the ac method.
  6. We can define ACDEBUGMEMORY as NULL and have memory leaks reported to the terminal when the program exits.
FLAGS += -D_AC_DEBUG_MEMORY_=\"memory.log\"
  1. We can define ACDEBUGMEMORY as a string and have memory leaks reported to a file periodically. The period is defined in seconds as ACDEBUGMEMORYSPEED_ and defaults to 60 in ac_common.h
  2. You can grep for any line of code which contains an object using the following approach. The following grep line will search all subdirectories for the string ac_timer and report the filename and line number where the text is found.
grep -rn ac_timer .

ac_timer can be replaced with a function name or another object name (or whatever you want to find).

Table of Contents (only if viewing on Github)