4.14.4 Memory Manager

We want to test our code to make sure that it always releases allocated memory and that it behaves robustly when memory allocations fail. We can do the former by building our own memory manager that keeps tracks of blocks as they are allocated and freed. The memory manager can also disallow allocations according to a policy set by the user, taking care of the latter.

The available policies are:

126. <Test declarations 122> +=
/* Memory tracking policy. */
enum mt_policy 
  {
    MT_TRACK,			/* Track allocation for leak detection. */
    MT_NO_TRACK,		/* No leak detection. */
    MT_FAIL_COUNT,      	/* Fail allocations after a while. */
    MT_FAIL_PERCENT,		/* Fail allocations randomly. */
    MT_SUBALLOC                 /* Suballocate from larger blocks. */
  };

MT_TRACK and MT_NO_TRACK should be self-explanatory. MT_FAIL_COUNT takes an argument specifying after how many allocations further allocations should always fail. MT_FAIL_PERCENT takes an argument specifying an integer percentage of allocations to randomly fail.

MT_SUBALLOC causes small blocks to be carved out of larger ones allocated with malloc(). This is a good idea for two reasons: malloc() can be slow and malloc() can waste a lot of space dealing with the small blocks that libavl uses for its node. Suballocation cannot be implemented in an entirely portable way because of alignment issues, but the test program here requires the user to specify the alignment needed, and its use is optional anyhow.

The memory manager keeps track of allocated blocks using struct block:

127. <Memory tracker 127> =
/* Memory tracking allocator. */

/* A memory block. */
struct block 
  {
    struct block *next;                 /* Next in linked list. */

    int idx;                            /* Allocation order index number. */
    size_t size;                        /* Size in bytes. */
    size_t used;                        /* MT_SUBALLOC: amount used so far. */
    void *content;                      /* Allocated region. */
  };

See also 128, 129, 130, 131, 132, and133.

The next member of struct block is used to keep a linked list of all the currently allocated blocks. Searching this list is inefficient, but there are at least two reasons to do it this way, instead of using a more efficient data structure, such as a binary tree. First, this code is for testing binary tree routines—using a binary tree data structure to do it is a strange idea! Second, the ISO C standard says that, with few exceptions, using the relational operators (<, <=, >, >=) to compare pointers that do not point inside the same array produces undefined behavior, but allows use of the equality operators (==, !=) for a larger class of pointers.

We also need a data structure to keep track of settings and a list of blocks. This memory manager uses the technique discussed in Exercise 2.5-3 to provide this structure to the allocator.

128. <Memory tracker 127> +=
/* Indexes into arg[] within struct mt_allocator. */
enum mt_arg_index 
  {
    MT_COUNT = 0,      /* MT_FAIL_COUNT: Remaining successful allocations. */
    MT_PERCENT = 0,    /* MT_FAIL_PERCENT: Failure percentage. */
    MT_BLOCK_SIZE = 0, /* MT_SUBALLOC: Size of block to suballocate. */
    MT_ALIGN = 1       /* MT_SUBALLOC: Alignment of suballocated blocks. */
  };

/* Memory tracking allocator. */
struct mt_allocator 
  {
    struct libavl_allocator allocator;  /* Allocator.  Must be first member. */

    /* Settings. */
    enum mt_policy policy;              /* Allocation policy. */
    int arg[2];                         /* Policy arguments. */
    int verbosity;                      /* Message verbosity level. */

    /* Current state. */
    struct block *head, *tail;          /* Head and tail of block list. */
    int alloc_idx;                      /* Number of allocations so far. */
    int block_cnt;                      /* Number of still-allocated blocks. */
  };

Function mt_create() creates a new instance of the memory tracker. It takes an allocation policy and policy argument, as well as a number specifying how verbose it should be in reporting information. It uses utility function xmalloc(), a simple wrapper for malloc() that aborts the program on failure. Here it is:

129. <Memory tracker 127> +=
static void *mt_allocate (struct libavl_allocator *, size_t);
static void mt_free (struct libavl_allocator *, void *);

/* Initializes the memory manager for use 
   with allocation policy policy and policy arguments arg[],
   at verbosity level verbosity, where 0 is a “normal” value. */
struct mt_allocator *
mt_create (enum mt_policy policy, int arg[2], int verbosity) 
{
  struct mt_allocator *mt = xmalloc (sizeof *mt);

  mt->allocator.libavl_malloc = mt_allocate;
  mt->allocator.libavl_free = mt_free;

  mt->policy = policy;
  mt->arg[0] = arg[0];
  mt->arg[1] = arg[1];
  mt->verbosity = verbosity;

  mt->head = mt->tail = NULL;
  mt->alloc_idx = 0;
  mt->block_cnt = 0;

  return mt;
}

After allocations and deallocations are done, the memory manager must be freed with mt_destroy(), which also reports any memory leaks. Blocks are removed from the block list as they are freed, so any remaining blocks must be leaked memory:

130. <Memory tracker 127> +=
/* Frees and destroys memory tracker mt, 
   reporting any memory leaks. */
void 
mt_destroy (struct mt_allocator *mt) 
{
  assert (mt != NULL);

  if (mt->block_cnt == 0) 
    {
      if (mt->policy != MT_NO_TRACK && mt->verbosity >= 1)
        printf ("  No memory leaks.\n");
    } 
  else 
    {
      struct block *iter, *next;

      if (mt->policy != MT_SUBALLOC) 
        printf ("  Memory leaks detected:\n");
      for (iter = mt->head; iter != NULL; iter = next) 
        {
          if (mt->policy != MT_SUBALLOC) 
            printf ("    block #%d: %lu bytes\n",
                    iter->idx, (unsigned long) iter->size);

          next = iter->next;
          free (iter->content);
          free (iter);
        }
    }

  free (mt);
}

For the sake of good encapsulation, mt_allocator() returns the struct libavl_allocator associated with a given memory tracker:

131. <Memory tracker 127> +=
/* Returns the struct libavl_allocator associated with mt. */
void *
mt_allocator (struct mt_allocator *mt) 
{
  return &mt->allocator;
}

The allocator function mt_allocate() is in charge of implementing the selected allocation policy. It delegates most of the work to a pair of helper functions new_block() and reject_request() and makes use of utility function xmalloc(), a simple wrapper for malloc() that aborts the program on failure. The implementation is straightforward:

132. <Memory tracker 127> +=
/* Creates a new struct block containing size bytes of content
   and returns a pointer to content. */
static void *
new_block (struct mt_allocator *mt, size_t size) 
{
  struct block *new;

  /* Allocate and initialize new struct block. */
  new = xmalloc (sizeof *new);
  new->next = NULL;
  new->idx = mt->alloc_idx++;
  new->size = size;
  new->used = 0;
  new->content = xmalloc (size);

  /* Add block to linked list. */
  if (mt->head == NULL)
    mt->head = new;
  else 
    mt->tail->next = new;
  mt->tail = new;

  /* Alert user. */
  if (mt->verbosity >= 3) 
    printf ("    block #%d: allocated %lu bytes\n",
            new->idx, (unsigned long) size);

  /* Finish up and return. */
  mt->block_cnt++;
  return new->content;
}

/* Prints a message about a rejected allocation if appropriate. */
static void 
reject_request (struct mt_allocator *mt, size_t size) 
{
  if (mt->verbosity >= 2)
    printf ("    block #%d: rejected request for %lu bytes\n",
            mt->alloc_idx++, (unsigned long) size);
}

/* Allocates and returns a block of size bytes. */
static void *
mt_allocate (struct libavl_allocator *allocator, size_t size) 
{
  struct mt_allocator *mt = (struct mt_allocator *) allocator;

  /* Special case. */  
  if (size == 0)
    return NULL;

  switch (mt->policy) 
    {
    case MT_TRACK: 
      return new_block (mt, size);

    case MT_NO_TRACK: 
      return xmalloc (size);

    case MT_FAIL_COUNT:
      if (mt->arg[MT_COUNT] == 0) 
        {
          reject_request (mt, size);
          return NULL;
        }
      mt->arg[MT_COUNT]--;
      return new_block (mt, size);

    case MT_FAIL_PERCENT:
      if (rand () / (RAND_MAX / 100 + 1) < mt->arg[MT_PERCENT]) 
        {
          reject_request (mt, size);
          return NULL;
        }
      else 
        return new_block (mt, size);

    case MT_SUBALLOC:
      if (mt->tail == NULL
          || mt->tail->used + size > (size_t) mt->arg[MT_BLOCK_SIZE])
        new_block (mt, mt->arg[MT_BLOCK_SIZE]);
      if (mt->tail->used + size <= (size_t) mt->arg[MT_BLOCK_SIZE]) 
        {
          void *p = (char *) mt->tail->content + mt->tail->used;
          size = ((size + mt->arg[MT_ALIGN] - 1)
                  / mt->arg[MT_ALIGN] * mt->arg[MT_ALIGN]);
          mt->tail->used += size;
          if (mt->verbosity >= 3)
            printf ("    block #%d: suballocated %lu bytes\n",
                    mt->tail->idx, (unsigned long) size);
          return p;
        }
      else 
        fail ("blocksize %lu too small for %lubyte allocation",
              (unsigned long) mt->tail->size, (unsigned long) size);

    default: 
      assert (0);
    }
}

The corresponding function mt_free() searches the block list for the specified block, removes it, and frees the associated memory. It reports an error if the block is not in the list:

133. <Memory tracker 127> +=
/* Releases block previously returned by mt_allocate(). */
static void 
mt_free (struct libavl_allocator *allocator, void *block) 
{
  struct mt_allocator *mt = (struct mt_allocator *) allocator;
  struct block *iter, *prev;

  /* Special cases. */
  if (block == NULL || mt->policy == MT_NO_TRACK) 
    {
      free (block);
      return;
    }
  if (mt->policy == MT_SUBALLOC)
    return;

  /* Search for block within the list of allocated blocks. */
  for (prev = NULL, iter = mt->head; iter; prev = iter, iter = iter->next) 
    {
      if (iter->content == block) 
        {
          /* Block found.  Remove it from the list. */
          struct block *next = iter->next;

          if (prev == NULL)
            mt->head = next;
          else 
            prev->next = next;
          if (next == NULL) 
            mt->tail = prev;

          /* Alert user. */
          if (mt->verbosity >= 4)
            printf ("    block #%d: freed %lu bytes\n",
                    iter->idx, (unsigned long) iter->size);

          /* Free block. */
          free (iter->content);
          free (iter);

          /* Finish up and return. */	  
          mt->block_cnt--;
          return;
        }
    }

  /* Block not in list. */
  printf ("    attempt to free unknown block %p (already freed?)\n", block);
}

See also:  [ISO 1990], sections 6.3.8 and 6.3.9.

Exercises:

1. As its first action, mt_allocate() checks for and special-cases a size of 0. Why? [answer]