Robert A. Moeser

Many useful programs have no need for storage management. The memory they need can be calculated at compile time, and when run time comes, either enough memory is available or it isn't. Other programs have a relatively simple pattern of memory usage; they consume memory in the course of execution and never return any until terminated, when the system grabs it all back. Then there are cases of more capricious memory use -- in interactive programs, for example, where a human calls the shots. You can implement programs with dynamic and unpredictable memory usage using the routines in the standard C library, but this can result in complex code that is hard to implement, read, and debug.

This article presents a set of routines for memory management. This memory control package is offered as an extension to your library routines malloc and free. It implements a free-list approach to aid in recycling portions of memory. It consists of a mere seven functions and is quite compact.

Most C libraries come with two basic routines, malloc and free. malloc returns a pointer to a block at least the size requested. It is then up to the program to keep track of the block, using it however it will, until it is no longer needed. A call to free will then return that block to storage and make it available for use in subsequent requests. There are other allocation routines in the standard C library, but they are just convenience routines and can be expressed easily in terms of malloc plus some additional code.

  struct tnoed *talloc()
  {
      char *malloc();
      return ((struct tnode *) malloc (sizeof (struct tnode)));
  }

A little more sophisticated is the program that anticipates a recurring need for structures of a certain type and provides not only a special allocator but also a specialized free routine. The routine that frees instances does not return them to the library storage allocator but instead keeps them on a free-list. A free-list is simply a singly linked list that chains freed blocks together. The routine that doles out new instances of the requested type first checks to see if any instances are waiting around and gets one off the free-list if it can. If it can't it goes to malloc for "real" storage.

The interface to the memory control package is simple. A client using the services provided sees it through a handful of functions. One function informs the memory controller of your intention to use objects of a certain size, referred to here as "registration." There are two routines: One for getting pointers to new instances of a registered object, and one for returning instances no longer needed. A fourth routine is available to flush the free-list for any object type (functionality not provided in the example above). There is also a routine used to "de-register" an object type, which the memory controller takes as its cue not only to flush the entity's free-list but also to free its own internal data for dealing with that object type.

Finally, there are two convenience routines, one to flush the free-lists of all known object types and another that will de-register all known object types. While I haven't used these last two in my own work, they were easy to provide and could come in handy in case of a major context shift or processing phase change. You could even call them on program exit, although, because all the memory used is ultimately obtained by malloc, it should find its way back to the system by itself. The accompanying text box summarizes the seven functions of the programming interface.

To use the memory controller package, include the mem.h header in each source file where its functions will be needed. Declare a variable of type MCon for each different object type. For now, think of it as a magic key. It is initialized when you register an object type with a call to newMCon. Usually these will be allocated statically, but the package makes no such restriction. So the following gets you a magic key for "objectA," which is some structure or union in your code:

MCon objectAMCon; 
objectAMCon = newMCon(sizeof objectA);

After that, you use this MCon to specify that it's an objectA you want when you call newInstanceOf to get a new instance. So the following will get you a pointer to an objectA-sized block:

objectA *anA; 
anA = newInstanceOf(objectAMCon);

and disposeInstance(anA); will put that storage back onto the free-list for objectA. The other routines are just as simple to use.

Please keep in mind that just as it is bad to free something that was not malloc'd, so it is bad to disposeInstance of something foreign to the memory control package. And one certain way to make something foreign is to dispose of its controller with disposeMCon. Sometimes these orphans are what you want, but beware. I also caution against freeing an instance obtained by newInstanceOf. Keep direct uses of malloc and free away from uses of the memory controller.

You might guess that an MCon is nothing more than a pointer to a structure which holds all the information that the memory controller needs in order to accomplish its tasks for a given object. This includes the size of the object and a pointer to a free-list of object-sized blocks.

The memory controller keeps all MCon objects on a doubly linked list to facilitate creating and disposing of them in response to a client's newMCon and disposeMCon requests, and to make purgeAllMCons and disposeAllMCons a matter of traversing the list and performing the requested operation on each MCon. A couple of internal routines do this list management.

Each MCon object also maintains some counters to track the use of its object type. They keep track of how many objects have been requested, how many are still "out there" somewhere under control of the client, and how many are currently on the free-list. Counters are used to validate the integrity of the internal data structures and can be used to glean useful information about usage patterns.

When a client requests registration of a new object type through the newMCon routine, the memory controller creates a new MCon object, fills in its fields, and links it into the master list of MCons. When the memory controller actually calls malloc to get storage for an object (the object's free-list being empty), it allocates some extra memory. This extra memory, hiding in front of the actual block you'll use to store your object data, is used to hold a copy of the MCon pointer that was used to create the block. The idea of hiding information in front of an allocated block is nothing new -- in fact malloc itself typically uses some overhead storage this way in its own simpler efforts to manage memory.

In this way disposeInstance can figure out which MCon's free-list to use. When an object is on a free-list, this extra storage is reused to hold a pointer to the next free instance, making a singly linked list of free blocks of the same size.

Now the final trick that complicates the implementation somewhat: Since the memory control package has an unpredictable need for objects of a certain size (MCon objects), it uses its own routines to manage storage for them! It is said that a man who is his own lawyer has a fool for a client, but this use of the memory controller seems OK. The MCon's MCon is the controlCon. When the package is active, this MCon serves as the controller for instances of MCon objects. The actual object is also the head and tail of the doubly linked list of MCons. This MCon object is just a little different than all the other blocks handed out by the memory controller; it lacks the hidden information in front of the block, so it gets allocated by just calling malloc and is freed (if disposeAllMCons is called, shutting down the controller) by a call to free.

The basic mechanism can be easily modified to keep more information about patterns of usage. Any amount of additional data, such as serial numbers or time stamps, can be hidden with each instance. The various mechanisms can be turned off and on in one place for development, testing, and production phases.

Additional functions would be easy to add -- for example, a copy function to return a copy of an instance. Bringing such extensions into the purview of a single memory controller like this one provides one-stop shopping for all kinds of tricks.

Variable-sized objects such as strings present a problem in this scheme. In my own code, I once used a method I dubbed the "Procrustean Allocator." I had MCons for a few different object sizes and rudely grabbed the nearest one that fit. The sizes were all powers of two, and I used the services of the memory controller to accomplish the allocation task with a little array of MCons. There is, of course, no reason you can't continue to use malloc and free wherever you like, as the memory controller in no way precludes other uses of these basic functions.

This set of routines provides simple access to a particular memory management technique. The code acts as a black box, using pointers to create the desired behavior for any conceivable variety of objects and usage patterns. It is self-starting and self-terminating and provides its services with minimal overhead. By using this package, you can improve the readability, if not the performance, of programs that call it. With a few additions, it could serve as a statistics-gathering device for memory use or as the basis for writing in a traditional language, using an object-oriented philosophy.

This section identifies the seven routines that constitute the memory controller program interface.

newMCon

MCon newMCon(size_t theItemSize);

newMCon is used to register an object type. The input argument is simply the size in bytes of the object to be controlled, and the return value is an MCon, or "magic key." If the package is unable to register the new object, the MCon returned will be zero. This MCon is passed to the other routines in the package that need to know which object type to operate on.

newInstanceOf

void *newInstanceOf(MCon theCon);

newInstanceOf takes an MCon as its argument and returns a pointer to a new (or recycled) instance of the object the MCon stands for. The return type is void *, so it can serve as a pointer to anything. This pointer will be zero if storage is unavailable.

disposeInstance

void disposeInstance(void *theItem);

disposeInstance takes as its argument a pointer to any instance that is no longer needed. The actual storage is not freed at this time, but is kept on a free-list for objects of the same type.

purgeMCon

void purgeMCon(MContheCon);

purgeMCon takes as its argument the MCon whose free-list should be returned to the library storage allocator by free.

disposeMCon

counter disposeMCon(MContheCon)

disposeMCon takes as its argument the MCon for an object type that will no longer be needed, and de-registers it. The entire free-list and the memory control package's internal representation for the object type are returned to the library storage allocator by calls to free. The return value is the number of "orphans" that this action creates -- since a client may have active instances of the object under its control, disposing of an object's MCon can create objects which now cannot be freed. This is not strictly an error, but should be a warning sign.

purgeAllMCons

void purgeAllMCons(void);

purgeAllMCons is a convenience routine, and just purges the free-list of every object type known to the memory controller. A client might call this in a desperate attempt to satisfy a memory request.

disposeAllMCons

counter disposeAllMCons(void);

disposeAllMCons is also a convenience routine, and deregisters all known object types. This action can create orphans in the same sense as disposeCon above, and so returns the number. It really ought to be zero unless the client has created objects meant to endure until program termination. The memory controller also shuts itself down and frees all malloc'd storage. --

R.A.M.

_A MEMORY CONTROLLER_ by Robert A. Moeser

<a name="0109_000f">

/* Header for memory control package
 C 1989 Robert A. Moeser, all rights reserved */

/* some things probably in your standard headers... */
#ifndef __size_t
#define __size_t
typedef unsigned long size_t;
#endif

void *malloc(size_t);
void free(void *);
int printf(char *, ...);
int sprintf(char *, char *, ...);
int scanf(char *, ...);
int rand(void);

/* end of things probably in your standard headers... */
typedef long counter;      /* a bit excessive, perhaps... */
typedef struct _mc {
   struct _mc *next;   /* used for doubly-linked list */
   struct _mc *prev;   /* of all mcs */
   size_t itemSize;   /* the size of the object this MCon controls */
   void *freeList;    /* a free list of objects */
   counter nGiven;    /* number of items handed out */
   counter nOut;      /* number still out there somewhere */
   counter nFree;      /* length of free list */
} *MCon;

MCon newMCon(size_t theItemSize);   /* 0 = could not get storage */
void *newInstanceOf(MCon theCon);   /* 0 = could not get storage */
void disposeInstance(void *theItem);
void purgeMCon(MCon theCon);
counter disposeMCon(MCon theCon);    /* number of orphans created by action */
void purgeAllMCons(void);
counter disposeAllMCons(void);        /* number of orphans created by action */




<a name="0109_0010"><a name="0109_0010">
<a name="0109_0011">

<a name="0109_0011">

/*  A Memory Controller. C 1989 Robert A. Moeser, all rights reserved */

# include "mem.h"

static void linkIn(MCon theCon);
static void linkOut(MCon theCon);
static int initMControl(void);

void debugCon(char *);
void printCon(MCon theCon);

static MCon controlCon = 0;      /* 0 -> not yet initialized */

/* Initialize the memory control "package." Returns 1 for successful
initialization or already initialized; returns 0 if it fails. Called
automatically by newMCon, but you can call it explicity if you like. */

int initMControl(void)
{
   if (controlCon) return (1);      /* already initialized! */
   controlCon = (MCon) malloc(sizeof *controlCon);
   if (!controlCon) return (0);   /* sad but true! */
   controlCon->itemSize = sizeof *controlCon;
   controlCon->nGiven = controlCon->nOut = controlCon->nFree = 0;
   controlCon->freeList = (void *) 0;
   controlCon->next = controlCon->prev = controlCon;
   return (1);                  /* OK! */
}

/*  Register a new type (object) for management by the memory controller
takes size of the object as an argument and returns an MCon object, which
is zero in case of failure. The Mcon object is used later to manage creation
of all instances of the new object, to maintain a free list for the object
and to keep track of demand for the object */

MCon newMCon(size_t theItemSize)
{
   MCon t;
   int k;
   k = initMControl();
   if (!k) return ((void *) 0);
   t = newInstanceOf(controlCon);
   if (!t) return ((void *) 0);
   t->itemSize = theItemSize;
   t->nGiven = t->nOut = t->nFree = 0;
   t->freeList = (void *) 0;
   linkIn(t);
   return (t);
}

/* Create a new object. Takes the object's MCon as an argument (previously
created by newMCon). Returns a pointer to a new instance of the object */
void *newInstanceOf(MCon theCon)
{
   void *t;
   if (theCon->freeList) {    /* any on free list? */
      t = theCon->freeList;
      theCon->freeList = *((MCon *) t);
      theCon->nFree--;
   }
   else                      /* nope, go malloc one */
      t = malloc(theCon->itemSize + (sizeof theCon));
   if (!t) return ((void *) 0);   /* allocator failure... */
   *((MCon *) t) = theCon;    /* remember the controller */
   theCon->nGiven++;
   theCon->nOut++;
   return ((void *) ((MCon *) t + 1));
}

/* Dispose of an object. Takes a pointer to the object to dispose of
the storage is kept by the object's MCon on a free list for reuse. */
void disposeInstance(void *theItem)
{
   MCon t;
   void *x;
   int g;
   t = *((MCon *) theItem - 1);   /* recover controllor */
   t->nOut--;
   t->nFree++;
   *((MCon *) theItem - 1) = t->freeList;
   t->freeList = (MCon *) theItem - 1;
}

/* Purge the free list for an MCon. Takes the MCon whose free list should be
returned to the system storage allocator */
void purgeMCon(MCon theCon)
{
   void *bop, *bop2;
   bop = theCon->freeList;
   while (bop) {
      bop2 = *((void **) bop);
      free(bop);
      bop = bop2;
   }
   theCon->freeList = (void *) 0;
   theCon->nFree = 0;
}

/* Unregister a type. Takes the MCon object that is no longer needed
returns the number of "orphans" created. Since active instances are entirely
the responsibility of clients of the memory control package, disposing of
an MCon can mean that there may be outstanding objects of the
no-longer-existing type. This is not strictly an error, but since there is
now no way to free the storage used by the orphans should be a warning sign. */

counter disposeMCon(MCon theCon)
{
   counter orphans = 0;   /* did this dispose create "orphans" ? */
   orphans = theCon->nOut;
   purgeMCon(theCon);   /* goodbye the free list */
   linkOut(theCon);
   disposeInstance((void *) theCon);
   return (orphans);   /* number of "orphans", should be 0! */
}

/* Purge the free list of every object type known to the memory controller
a client might call this in a desperate attempt to satisfy a memory request */
void purgeAllMCons(void)
{
   MCon bop;
   bop = controlCon;
   do {
      purgeMCon(bop);
      bop = bop->next;
   } while (bop != controlCon);
}

/* Unregister all types. This action can create orphans in the same sense as
disposeMCon above, and so returns the number. It really ought to be zero
unless the client has created objects meant to endure until program
termination. Since all types are deactivated the additional step of
deactivating the memory controller itself is taken. All storage used by the
package is returned to the system storage allocator. */

counter disposeAllMCons(void)
{
   counter orphans = 0;
   MCon bop, bop2;
   bop = controlCon->next;
   while (bop != controlCon) {
      bop2 = bop->next;
      orphans += disposeMCon(bop);
      bop = bop2;
   }
   purgeMCon(controlCon);
   free((void *) controlCon);
   controlCon = (void *) 0;   /* de-initialize mc */
   return (orphans);   /* total number of "orphans", should be 0! */
}

/* Internal Routines */

/* Link a new MCon into the doubly-linked list of all known MCons
the list head and tail is the MCon for MCons, so there is always at least one
item on the list and the first item is always the MCon's MCon */
static void linkIn(MCon theConToAdd)
{
   theConToAdd->next = controlCon->next;
   theConToAdd->prev = controlCon;
   controlCon->next = theConToAdd;
   (theConToAdd->next)->prev = theConToAdd;
}

/* Unlink an MCon (called upon destruction of an Mcon */
static void linkOut(MCon theConToDel)
{
   (theConToDel->prev)->next = theConToDel->next;
   (theConToDel->next)->prev = theConToDel->prev;
}

/* Debugging and Utility Routines */

/* Print a list of known MCons with statistics. Takes a tag to accompany
printout as an argument. */
void debugCon(char *s)
{
   MCon bop;
   printf("%s", s);
   if (!controlCon) {
      printf(" -mc is OFF!\n");
      return;
   }
   bop = controlCon;
   do {
      printCon(bop);
      bop = bop->next;
   } while (bop != controlCon);
}

/* Print one MCon. Make a quick check on the integrity of the internal
data structure. */
void printCon(MCon theCon)
{
   char *freeBop;
   int freeCount;
   int OK;
   freeBop = theCon->freeList;
   freeCount = 0;
   while (freeBop) {
      freeCount++;
      freeBop = *((char **) freeBop);
   }
   OK = freeCount == theCon->nFree;
   printf("%lx = %lu\t%ld\t%ld\t%ld\t%lx\t%s\n",
      theCon,
      theCon->itemSize,
      theCon->nGiven,
      theCon->nOut,
      theCon->nFree,
      theCon->freeList,
      OK ? "<ok>" : "<NOK>");
}




<a name="0109_0012"><a name="0109_0012">
<a name="0109_0013">

<a name="0109_0013">

/* Part 1 of torture-test of the memory controller */

# include <stdio.h>
# include <console.h>

void torture(void);
main()
{
   int i;
   for (i = 0; i < 100; i++)
      torture();
}




<a name="0109_0014"><a name="0109_0014">
<a name="0109_0015">

<a name="0109_0015">

/* Part 2 of torture-test of the memory controller */

# include "mem.h"

# define MAXTYPES      20
# define MAXINSTANCES   500
# define BASESIZE      25
# define MAXEXTRA      25
# define NPASSES      50000

void torture(void);
void error(char *);
void makeNewType(void);
void makeNewObject(void);
void freeSomeObject(void);
int randle(int);
void debugCon(char *);
struct {
   MCon mCon;
   long theID;
} regType[MAXTYPES];
struct {
   void *mObj;
   long typeID;
} mBag[MAXINSTANCES];
int nInstances = 0;
int nTypes = 0;
long serialID = 1000;
void torture()
{
   counter orphans = 0;
   size_t sizeItem;
   int typeIdx, objIdx;
   int nPotential, nActual;
   long tID;
   int i, x;
   long looper;
   char msg[64];
   for (looper = 0; looper < NPASSES; looper++) {
      if (orphans) error("orphans have been created");
      if (!nTypes) {
         if (nInstances) error("instances but no active types");
         makeNewType();
      }
      x = randle(10);
      switch (x) {
      case 0 :            /* make a report */
         sprintf(msg, "loop %ld : %d instances of %d types\n",
           looper,
           nInstances,
           nTypes);

         debugCon(msg);
         break;
      case 1 :          /* register a new type if room */
         makeNewType();
         break;
      case 2 :          /* make a new object if room */
         makeNewObject();
         break;
      case 7 :          /* make many new objects */
         nPotential = ((MAXINSTANCES - nInstances) >> 2) + 7;
         nActual = randle(nPotential);
         while (nPotential--)
            makeNewObject();
         break;
      case 3 :          /* free an object if any exist */
         freeSomeObject();
         break;
      case 8 :          /* free many objects */
         nPotential = ((MAXINSTANCES - nInstances) >> 3) + 3;
         nActual = randle(nPotential);
         while (nPotential--)
            freeSomeObject();
         break;
      case 4 :     /* purge free list of a type if any exist */
         if (nTypes) {
            typeIdx = randle(nTypes);
            purgeMCon(regType[typeIdx].mCon);
         }
         break;
      case 9 :               /* purge a number of free lists */
         if (nTypes) {
            nActual = randle(nTypes);
            for (i = 0; i < nActual; i++) {
               typeIdx = randle(nTypes);
               purgeMCon(regType[typeIdx].mCon);
            }
         }
         break;
      case 5 :     /* free all of a registered type if any exist */
         if (nTypes) {
            typeIdx = randle(nTypes);
            tID = regType[typeIdx].theID;
            for (i = 0; i < nInstances; )
               if (mBag[i].typeID == tID) {
                  disposeInstance(mBag[i].mObj);
                  nInstances--;
                  mBag[i] = mBag[nInstances];
               }
               else i++;
               /* and maybe kill the controllor */
            if (randle(13) > 7) {
             orphans += disposeMCon(regType[typeIdx].mCon);
             nTypes--;
             regType[typeIdx] = regType[nTypes];
            }
         }
         break;
      case 6 :            /* free all instances of all types */
         if (randle(20) < 15) break;
         for (i = 0; i < nInstances; i++)
            disposeInstance(mBag[i].mObj);
         nInstances = 0;
               /* kill some controllors */
         for (i = 0; i < nTypes;)
            if (randle(15) > 13) {
                  orphans += disposeMCon(regType[i].mCon);
                  nTypes--;
                  regType[i] = regType[nTypes];
            }
            else i++;
            /* and maybe kill all the rest and shut down! */
         if (randle(20) > 17) {
            orphans += disposeAllMCons();
            nTypes = 0;
         }
         break;
      }
   }
   printf("\n%ld passes...\n", NPASSES);
}
void makeNewType()
{
   MCon tCon;
   size_t sizeItem;
   if (nTypes < MAXTYPES) {
      sizeItem = BASESIZE + randle(MAXEXTRA);
      tCon = newMCon(sizeItem);
      if (!tCon) {
         error("could not make controllor");
         return;
      }
      regType[nTypes].mCon = tCon;
      regType[nTypes].theID = serialID++;
      nTypes++;
   }
}
void makeNewObject()
{
   int typeIdx;
   void *tObj;
   if ((nInstances < MAXINSTANCES) && nTypes) {
      typeIdx = randle(nTypes);
      tObj = newInstanceOf(regType[typeIdx].mCon);
      if (!tObj) {
         error("could not get object memory");
         return;
      }
      mBag[nInstances].mObj = tObj;
      mBag[nInstances].typeID = regType[typeIdx].theID;
      nInstances++;
   }
}
void freeSomeObject()
{
   int objIdx;
   if (nInstances) {
      objIdx = randle(nInstances);
      disposeInstance(mBag[objIdx].mObj);
      nInstances--;
      mBag[objIdx] = mBag[nInstances];
   }
}
void error(char *s)                    /* print error message and hang */
{
   char hang[12];
   printf("\nERROR : %s\n", s);
   scanf("%s", hang);
}
randle(int n)                        /* random number up to not including n */
{
   if (n <= 0) error("bogus randle call");
   return (rand() % n);
}


[Example 1: The K&R tnode allocator]

    struct tnode *talloc()
    {
        char *malloc();
        return ((struct tnode *) malloc(sizeof(struct tnode)));
    }