WORD PTR

Pointed Development

Tegen Memory Logging

| Comments

tegen Memory Routines

tegen includes a memory diagnostic module, wp_memory. Much of this information is available in the literate form at github.com/jgshort/tegen. I’ve made an abridged blog-friendly version here. It lacks many of the details available in the source.

A majority of the routines within wp_memory were written explicitly for diagnostic purposes during debugging. They are absolutely not recommended for production execution! tegen defines several of its own memory allocation and deallocation routines for use throughout the project or in peripheral libraries. During a production compilation (in which _DEBUG would not be enabled) the wp_malloc, wp_free, and wp_malloc_array methods are replaced with their malloc and free C equivalents, as defined under Production Aliases. Otherwise, if _DEBUG is enabled, the diagnostic routines take advantage of a runtime memory transaction log wp_memory_txn that monitors allocation and deallocation statistics, and assists with dynamic memory allocation and free leak identification within the code base.

Memory pools and other higher-level constructs will eventually utilize the functions defined here.

Production Aliases

If _DEBUG is not specified during compilation, the following allocation and deallocation routines are used in place of the diagnostic utilities. No surprises here, wp_memory_print_stats is a no-op, while wp_malloc allocates Sz bytes. tegen includes its own array allocation mechanism in order to explicitly declare N number of size Sz blocks are allocated by malloc.

1
2
3
4
#define wp_memory_print_stats() ((void)0)
#define wp_malloc(Sz) (malloc((Sz)))
#define wp_malloc_array(Sz, N) (malloc((N) * (Sz)))
#define wp_free(P) free(P)

Diagnostic Aliases.

If _DEBUG has been defined, all instances of the aforementioned methods are replaced with their diagnostic counterparts. Conceptually, any call to an allocation method creates an entry in a runtime transaction log. During deallocation, the objects within the log entries are dereferenced and released, but the log is not released. At program exit, the transaction log is walked and diagnostic messages are printed for all non-deallocated objects. The transaction log is freed after all other diagnostic functions have executed.

Generally, it is somewhat more algorithmically expensive to free an object with the tegen utilities than to allocate an object. Generally.

These routines are not intedended to replace manual memory management with some sort of degenerate garbage collector. They’re much too naive and much too primitive. However, for simple diagnostic logging of allocations to deallocations, they’re acceptable.

We may add a garbage collector one of these days.

Allocation with wp_malloc

wp_malloc wraps the wp_malloc_wrapper function, which assists with debugging during development. If _DEBUG is not enabled, wp_malloc wraps malloc. The call void *m = wp_malloc(sizeof *m) is identical to calling void *m = malloc(sizeof *m).

1
#define wp_malloc(Sz) (wp_malloc_wrapper((Sz),__FILE__,__LINE__))

Array allocation with wp_malloc_array

wp_malloc_array wraps wp_malloc_wrapper, allocating enough space for N elements of size Sz. The call v = wp_malloc_array(sizeof *v, 10) is identical to calling v = malloc(10 * sizeof*v).

1
#define wp_malloc_array(Sz, N) (wp_malloc_wrapper((N) * (Sz),__FILE__,__LINE__))

Deallocation with wp_free

Just like its C counterpart, wp_free frees memory previously allocated by one of the allocation methods listed above. P may be NULL. The call wp_free(v) is identical to calling free(v). If _DEBUG is enabled, wp_free walks its list of allocated objects and sets its transaction Log ref property to 0.

1
#define wp_free(P) wp_free_wrapper(P)

The Memory Transaction Log.

The runtime memory transaction log is a lightweight, circular doubly-linked list that tracks allocation and deallocation usage within the tegen framework. It contains the following properties:

  • A prev pointer to the previous item within the list
  • A next pointer to the next item within the list
  • A pointer, p, to the block of memory allocated by malloc
  • The file in which the call to the allocation method occurred
  • The size, sz, in bytes of the structure allocated
  • A flag ref, which is 1 if the structure was successfully allocated, otherwise 0
  • The line the allocation occurred within the file

A global static sentinel tracks the list head.

1
2
3
4
5
6
7
8
9
typedef struct wp_memory_txn {
    struct wp_memory_txn * restrict prev; /* Pointer to previous */
    struct wp_memory_txn * restrict next; /* Pointer to next */
    const char           * restrict file; /* Source file */
    void                 * p;    /* Allocated Pointer */
    size_t                 sz;   /* Size allocated */
    int                    ref;  /* Reference flag */
    int                    line; /* Source line */
} wp_memory_txn;

Allocation

All diagnostic-enabled calls to any of the two tegen allocation methods all wrap (wp_malloc_wrapper). This is the primary driver of the runtime memory transaction log, and it’s responsible for initially inserting all members (except wp_get_txn_head()) to the transaction log list. If we successfully malloc(sz) bytes, we return the pointer created by malloc, not the transaction, as if the caller had called malloc directly.

Right now, we assert that sz > 0. malloc(0) is implementation defined.

1
2
3
4
5
6
7
8
9
10
11
12
13
void *wp_malloc_wrapper(size_t sz, const char * file, int line) {
  static wp_memory_txn *H = NULL;
  if(H == NULL) {
    H = wp_get_txn_head();
  }
  wp_memory_txn *t;

  assert(sz > 0);

  /* Initialize a new transaction (below) */

  return t->p;
}

The transaction is first created (malloc) and all fields initialized to reasonable values. If we’re unable to allocate a transaction log, we consider it game over and we abort immediately. However, if we’re unable to malloc(sz), the application will continue, and t->p will return NULL to the caller as if malloc failed to allocate a block of memory.

In particular, note the call to WP_LIST_PREPEND(H, t), which inserts t at the tail of circular list H|.

1
2
3
4
5
6
7
8
9
10
11
  /* Initialize a new transaction: */
  t = malloc(sizeof *t);
  if(!t) abort();

  WP_LIST_PREPEND(H, t);

  t->sz = sz;
  t->p = malloc(sz);
  t->ref = t->p ? 1 : 0;
  t->file = file;
  t->line = line;

Free

Like it’s C free counterpart, the wp_free_wrapper frees the memory pointed to by p. The wrapper, however, needs to perform a little extra work in order to handle the transaction log details, correctly setting the transaction ref to 0 and freeing the transaction’s void *p. The current linked list traversal is not optimal, but has been found to be optimal enough.

In a future release, we may store all t->p pointers in an array to be searched. Until the following function proves inefficient, we’ll leave it as is.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void wp_free_wrapper(void * p) {
  static const wp_memory_txn * restrict H = NULL;
  if(H == NULL) {
    H = wp_get_txn_head();
  }
  wp_memory_txn *t = H->next;
  if(p) {
    /* It's okay to pass a |p == NULL|*/
    while(t->p != p && (t = t->next) != H)
      ;
    if(t->p == p) {
      free(t->p), t->p = NULL;
      t->ref = 0;
    }
  }
}

Diagnostics

During runtime (particularly during application shutdown or unit tests) it’s sometimes useful to query diagnostic information from the memory module. The struct wp_memory_diagnostics contains simple allocation and deallocation statistics. This information contains no information about the items allocated or deallocated, and is only useful for generating simple counts of objects in memory.

The pattern contained within this method is illustrative of most other methods within the wp_memory module. A wp_memory_txn * pointer first points to wp_get_txn_head(), which is the sentinel object within the transaction log list. We then iterate over the list do { ... } while((t = t->next) != H);, where “…” indicates some action on the current item within the list. We may eventually move this code to a list module.

1
2
3
4
5
  typedef struct wp_memory_diagnostics {
    int alloc;
    int freed;
    size_t total;
  } wp_memory_diagnostics;

wp_memory_get_diagnostics method may be called, for example, like this:

1
2
wp_memory_diagnostics m;
wp_memory_get_diagnostics(&m);

… where m will now contain the allocation count (that is, the number of malloc invocations) and the deallocation count (that is, the number of free invocations). The counts may or may not be balanced during runtime, but should be balanced prior to application termination.

Note that we’re not checking bounds or overflow. We’ll get to this one of these days.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void wp_memory_get_diagnostics(wp_memory_diagnostics * m) {
  static const wp_memory_txn * H = NULL;
  if(H == NULL) {
    H = wp_get_txn_head();
  }
  const wp_memory_txn * restrict t = H->next;

  m->alloc = m->freed = m->total = 0;
  if(t != H) {
    do {
      t->ref ? m->alloc++ : m->freed++;
      m->total += t->sz;
    } while((t = t->next) != H);
  }
}

Conclusion

These functions are specifically designed to help us find memory leaks in tegen. In combination with these routines and a tool like valgrind, we should be reasonably certain that we’re freeing all allocated memory. Additionally, runtime diagnostic routines give us a small window into the memory use of tegen. From here, we can create more sophisticated memory objects such as pools and garbage collectors, and have confidence that our underlying allocations are subsequently freed.

References

Comments