The Mem interface exports exceptions, routines, and macros:

<mem.h>≡
  #ifndef MEM_INCLUDED
  #define MEM_INCLUDED
  #include "except.h"

  <exported exceptions 70>
  <exported functions 70>
  <exported macros 70>

  #endif

Mem’s allocation functions are similar to those in the standard C library, but they don’t accept zero sizes and never return null pointers:

<exported exceptions 70>≡
   extern const Except_T Mem_Failed;

<exported functions 70>≡
   extern void *Mem_alloc (long nbytes,
       const char *file, int line);
   extern void *Mem_calloc(long count, long nbytes,
       const char *file, int line);

Mem_alloc allocates a block of at least nbytes and returns a pointer to the first byte. The block is aligned on an addressing boundary that is suitable for the data with the strictest alignment requirement. The contents of the block are uninitialized. It is a checked runtime error for nbytes to be nonpositive.

Mem_calloc allocates a block large enough to hold an array of count elements each of size nbytes, and returns a pointer to the first element. The block is aligned as for Mem_alloc, and is initialized to zeros. The null pointer and 0.0 are not necessarily represented by zeros, so Mem_calloc may not initialize them correctly. It is a checked runtime error for count or nbytes to be nonpositive.

The last two arguments to Mem_alloc and Mem_calloc are the file name and line number of the location of the call. These are supplied by the following macros, which are the usual way to invoke these functions.

<exported macros 70>≡
   #define ALLOC(nbytes) 
       Mem_alloc((nbytes), __FILE__, __LINE__)
   #define CALLOC(count, nbytes) 
       Mem_calloc((count),  (nbytes), __FILE__, __LINE__)

If Mem_alloc or Mem_calloc cannot allocate the memory requested, they raise Mem_Failed and pass file and line to Except_raise so that the exception reports the location of the call. If file is the null pointer, Mem_alloc and Mem_calloc supply the locations within their implementations that raise Mem_Failed.

Many allocations have the form

   struct T *p;
   p = Mem_alloc(sizeof (struct T));

which allocates a block for an instance of the structure T and returns a pointer to that block. A better version of this idiom is

   p = Mem_alloc(sizeof *p);

Using sizeof *p instead of sizeof (struct T) works for any pointer type, except void pointers, and sizeof *p is independent of the pointer’s referent type. If the type of p is changed, this allocation remains correct, but the one with sizeof (struct T) must be changed to reflect the change in p’s type. That is,

   p = Mem_alloc(sizeof (struct T));

is correct only if p is really a pointer to a struct T. If p is changed to a pointer to another structure and the call isn’t updated, the call may allocate too much memory, which wastes space, or too little memory, which is disastrous, because the client may scribble on unallocated storage.

This allocation idiom is so common that Mem provides macros that encapsulate both the allocation and the assignment:

<exported macros 70>+≡
   #define  NEW(p) ((p) = ALLOC((long)sizeof *(p)))
   #define NEW0(p) ((p) = CALLOC(1, (long)sizeof *(p)))

NEW(p) allocates an uninitialized block to hold *p and sets p to the address of that block. NEW0(p) does the same, but also clears the block. NEW is provided on the assumption that most clients initialize a block immediately after allocating it. The argument to the compile-time operator sizeof is used only for its type; it is not evaluated at runtime. So NEW and NEW0 evaluate p exactly once, and it’s safe to use an expression that has side effects as an actual argument to either macro, such as NEW(a[i++]), for example.

malloc and calloc take arguments of type size_t; sizeof yields a constant of type size_t. The type size_t is an unsigned integral type capable of representing the size of the largest object that can be declared, and it’s used in the standard library wherever object sizes are specified. In practice, size_t is either unsigned int or unsigned long. Mem_alloc and Mem_calloc take integer arguments to avoid errors when negative numbers are passed to unsigned arguments. For example,

   int n = -1;
   ...
   p = malloc(n);

is clearly an error, but many implementations of malloc won’t catch the error because when −1 is converted to a size_t, it usually winds up as a very large unsigned value.

Memory is deallocated by Mem_free:

<exported functions 70>+≡
   extern void Mem_free(void *ptr,
       const char *file, int line);

<exported macros 70>+≡
   #define FREE(ptr) ((void)(Mem_free((ptr), 
       __FILE__, __LINE__), (ptr) = 0))

Mem_free takes a pointer to the block to be deallocated. If ptr is nonnull, Mem_free deallocates that block; if ptr is null, Mem_free has no effect. The FREE macro also takes a pointer to a block, calls Mem_free to deallocate the block, and sets ptr to the null pointer, which, as mentioned in Section 2.4, helps avoid dangling pointers. Since ptr is null after its referent has been deallocated by FREE, a subsequent dereference will usually cause the program to crash with some kind of addressing error. This definite error is better than the unpredictable behavior that dereferencing a dangling pointer can cause. Note that FREE evaluates ptr more than once.

As detailed in the sections that follow, there are two implementations that export the Mem interface. The checking implementation implements checked runtime errors to help catch access errors like those described in the previous section. In that implementation, it is a checked runtime error to pass Mem_free a nonnull ptr that was not returned by a previous call to Mem_alloc, Mem_calloc, or Mem_resize, or a ptr that has already been passed to Mem_free or Mem_resize. The values of Mem_free’s file and line arguments are used to report these checked runtime errors.

In the production implementation, however, these access errors are unchecked runtime errors.

The function

<exported functions 70>+≡
   extern void *Mem_resize(void *ptr, long nbytes,
       const char *file, int line);

<exported macros 70>+≡
   #define RESIZE(ptr, nbytes) ((ptr) = Mem_resize((ptr), 
       (nbytes), __FILE__, __LINE__))

changes the size of the block allocated by a previous call to Mem_alloc, Mem_calloc, or Mem_resize. Like Mem_free, the first argument to Mem_resize is the pointer that holds the address of the block whose size is to be changed. Mem_resize expands or contracts the block so that it holds at least nbytes of memory, suitably aligned, and returns a pointer to the resized block. Mem_resize may move the block in order to change its size, so Mem_resize is logically equivalent to allocating a new block, copying some or all of the data from ptr to the new block, and deallocating ptr. If Mem_resize cannot allocate the new block, it raises Mem_Failed, with file and line as the exception coordinates. The macro RESIZE changes ptr to point at the new block — a common use of Mem_resize. Note that RESIZE evaluates ptr more than once.

If nbytes exceeds the size of the block pointed to by ptr, the excess bytes are uninitialized. Otherwise, nbytes beginning at ptr are copied to the new block.

It is a checked runtime error to pass Mem_resize a null ptr, and for nbytes to be nonpositive. In the checking implementation, it is a checked runtime error to pass Mem_resize a ptr that was not returned by a previous call to Mem_alloc, Mem_calloc, or Mem_resize, and to pass it one that has already been passed to Mem_free or Mem_resize. In the production implementation, these access errors are unchecked runtime errors.

The functions in the Mem interface can be used in addition to the standard C library functions malloc, calloc, realloc, and free. That is, a program can use both sets of allocation functions. The access errors reported as checked runtime errors by the checking implementation apply only to memory managed by that implementation. Only one implementation of the Mem interface may be used in any given program.

In the production implementation, the routines encapsulate calls to the memory-management functions in the standard library in the safer package specified by the Mem interface:

<mem.c>≡
  #include <stdlib.h>
  #include <stddef.h>
  #include "assert.h"
  #include "except.h"
  #include "mem.h"

  <data 74>
  <functions 74>

For example, Mem_alloc calls malloc and raises Mem_Failed when malloc returns the null pointer:

<functions 74>≡
   void *Mem_alloc(long nbytes, const char *file, int line){
       void *ptr;

       assert(nbytes > 0);
       ptr = malloc(nbytes);
       if (ptr == NULL)
           <raise Mem_Failed 74>
       return ptr;
   }

<raise Mem_Failed 74>≡
   {
        if (file == NULL)
            RAISE(Mem_Failed);
        else
            Except_raise(&Mem_Failed, file, line);
   }

<data 74>≡
  const Except_T Mem_Failed = { "Allocation Failed" };

If a client doesn’t handle Mem_Failed, Except_raise will give the caller’s coordinates, which are passed to Mem_alloc when it reports the unhandled exception. For example:

Uncaught exception Allocation Failed raised @parse.c:431 aborting...

Similarly, Mem_calloc encapsulates a call to calloc:

<functions 74>+≡
   void *Mem_calloc(long count, long nbytes,
       const char *file, int line) {
       void *ptr;

       assert(count > 0);
       assert(nbytes > 0);
       ptr = calloc(count, nbytes);
       if (ptr == NULL)
           <raise Mem_Failed 74>
       return ptr;
   }

When either count or nbytes is zero, calloc’s behavior is implementation defined. The Mem interface specifies what happens in these cases, which is one of its advantages and helps avoid bugs.

Mem_free just calls free:

<functions 74>+≡
   void Mem_free(void *ptr, const char *file, int line) {
       if (ptr)
           free(ptr);
   }

The standard permits null pointers to be passed to free, but Mem_free doesn’t pass them, because old implementations of free may not accept null pointers.

Mem_resize has a much simpler specification than does realloc, which is reflected in its simpler implementation:

<functions 74>+≡
   void *Mem_resize(void *ptr, long nbytes,
       const char *file, int line) {

       assert(ptr);
       assert(nbytes > 0);
       ptr = realloc(ptr, nbytes);
       if (ptr == NULL)
           <raise Mem_Failed 74>
       return ptr;
   }

Mem_resize’s only purpose is to change the size of an existing block. realloc does this, too, but it also frees a block when nbytes is zero and allocates a block when ptr is the null pointer. These additional capabilities, which are only loosely related to changing the size of an existing block, invite bugs.

The functions exported by the checking implementation of the Mem interface catch the kinds of access errors described at the beginning of this chapter and report them as checked runtime errors.

<memchk.c>≡
  #include <stdlib.h>
  #include <string.h>
  #include "assert.h"
  #include "except.h"
  #include "mem.h"

  <checking types 80>
  <checking macros 79>
  <data 74>
  <checking data 77>
  <checking functions 79>

Mem_free and Mem_resize can detect access errors if Mem_alloc, Mem_calloc, and Mem_resize never return the same address twice and if they remember all of the addresses they do return and which ones refer to allocated memory. Abstractly, these functions maintain a set S whose elements are the pairs (α, free) or (α, allocated), where α is the address returned by an allocation. The value free indicates that the address α does not refer to allocated memory; that is, it has been deallocated explicitly, and the value allocated indicates that α points to allocated memory.

Mem_alloc and Mem_calloc add the pair (ptr, allocated) to S, where ptr is their return value, and they guarantee that neither (ptr, allocated) nor (ptr, free) was in S before the addition. Mem_free(ptr) is legal if ptr is null or if (ptr, allocated) is in S. If ptr is nonnull and (ptr, allocated) is in S, Mem_free deallocates the block at ptr and changes the entry in S to (ptr, free). Similarly, Mem_resize(ptr, nbytes, ...) is legal only if (ptr, allocated) is in S. If so, Mem_resize calls Mem_alloc to allocate a new block, copies the contents of the old one to the new one, and calls Mem_free to deallocate the old one; these calls make the appropriate changes to S.

The condition that the allocation functions never return the same address twice can be implemented by never deallocating anything. This approach wastes space, and it’s easy to do better: never deallocate the byte at an address previously returned by an allocation function. S can be implemented by keeping a table of the addresses of these bytes.

This scheme can be implemented by writing a memory allocator that sits on top of the standard library functions. This allocator maintains a hash table of block descriptors:

<checking data 77>≡
   static struct descriptor {
       struct descriptor *free;
       struct descriptor *link;
       const void *ptr;
       long size;
       const char *file;
       int line;
   } *htab[2048];

ptr is the address of the block, which is allocated elsewhere as described below, and size is the size of the block. file and line are the block’s allocation coordinates — the source coordinates passed to the function that allocated the block. These values aren’t used, but they’re stored in descriptors so that debuggers can print them during a debugging session.

The link fields form a list of descriptors for blocks that hash to the same index in htab, which is an array of pointers to descriptors. These descriptors also form a list of free blocks; the head of this list is the dummy descriptor

<checking data 77>+≡
   static struct descriptor freelist = { &freelist };

and the list is threaded through the free fields of the descriptors. This list is circular: freelist is the last descriptor on the list and its free field points to the first descriptor. At any given time, htab holds descriptors for all of the blocks, both free and allocated, and the free blocks are on freelist. Thus, the descriptor’s free field is null if the block is allocated and nonnull if it’s free, and htab implements S. Figure 5.1 shows these data structures at one point in time. The space associated with each descriptor structure appears behind it. Shaded spaces are allocated; clear spaces are free, solid lines emanate from link fields, and the dotted lines show the free list.

Figure 5.1. htab and freelist structures

Given an address, find searches for its descriptor. It returns either a pointer to the descriptor or the null pointer:

<checking functions 79>≡
   static struct descriptor *find(const void *ptr) {
       struct descriptor *bp = htab[hash(ptr, htab)];

       while (bp && bp->ptr != ptr)
           bp = bp->link;
       return bp;
   }

<checking macros 79>≡
   #define hash(p, t) (((unsigned long)(p)>>3) & 
       (sizeof (t)/sizeof ((t)[0])-1))

The hash macro treats the address as a bit pattern, shifts it right three bits, and reduces it modulo the size of htab. find is enough to write a version of Mem_free in which access errors are checked runtime errors:

<checking functions 79>+≡
   void Mem_free(void *ptr, const char *file, int line) {
       if (ptr) {
           struct descriptor *bp;
           <set bp if ptr is valid 79>
           bp->free = freelist.free;
           freelist.free = bp;
       }
   }

If ptr is nonnull and is a valid address, the block is deallocated by appending it to the free list for possible reuse by a subsequent call to Mem_alloc. A pointer is valid if it points to an allocated block:

<set bp if ptr is valid 79>≡
   if (((unsigned long)ptr)%(sizeof (union align)) != 0
   || (bp = find(ptr)) == NULL || bp->free)
       Except_raise(&Assert_Failed, file, line);

The test ((unsigned long)ptr)%(sizeof (union align)) != 0 avoids calls to find for those addresses that aren’t multiples of the strictest alignment and thus cannot possibly be valid block pointers.

As shown below, Mem_alloc always returns pointers that are aligned on an address that is a multiple of the size of the following union.

<checking types 80>≡
   union align {
       int i;
       long l;
       long *lp;
       void *p;
       void (*fp)(void);
       float f;
       double d;
       long double ld;
   };

This alignment ensures that any type of data can be stored in the blocks returned by Mem_alloc. If the ptr passed to Mem_free isn’t so aligned, it can’t possibly be in htab and is thus invalid.

Mem_resize catches access errors by making the same check, and then calls Mem_free, Mem_alloc, and the library function memcpy:

<checking functions 79>+≡
   void *Mem_resize(void *ptr, long nbytes,
       const char *file, int line) {
       struct descriptor *bp;
       void *newptr;

       assert(ptr);
       assert(nbytes > 0);
       <set bp if ptr is valid 79>
       newptr = Mem_alloc(nbytes, file, line);
       memcpy(newptr, ptr,
           nbytes < bp->size ? nbytes : bp->size);
       Mem_free(ptr, file, line);
       return newptr;
   }

Likewise, Mem_calloc can be implemented by calling Mem_alloc and the library function memset:

<checking functions 79>+≡
   void *Mem_calloc(long count, long nbytes,
       const char *file, int line) {
       void *ptr;

       assert(count > 0);
       assert(nbytes > 0);
       ptr = Mem_alloc(count*nbytes, file, line);
       memset(ptr, '', count*nbytes);
       return ptr;
   }

All that remains is to allocate the descriptors themselves and the code for Mem_alloc. One way to do both tasks with one allocation is to allocate a block large enough to hold a descriptor and the storage requested by a call to Mem_alloc. This approach has two drawbacks. First, it complicates carving up a block of free storage to satisfy several smaller requests, because each request needs its own descriptor. Second, it makes the descriptors vulnerable to corruption by writes through pointers or indices that stray just outside of allocated blocks.

Allocating descriptors separately decouples their allocations from those done by Mem_alloc and reduces — but does not eliminate — the chances that they will be corrupted. dalloc allocates, initializes, and returns one descriptor, doling it out of the 512-descriptor chunks obtained from malloc:

<checking functions 79>+≡
   static struct descriptor *dalloc(void *ptr, long size,
       const char *file, int line) {
       static struct descriptor *avail;
       static int nleft;

       if (nleft <= 0) {
           <allocate descriptors 82>
           nleft = NDESCRIPTORS;
       }
       avail->ptr = ptr;
       avail->size = size;
       avail->file = file;
       avail->line = line;
       avail->free = avail->link = NULL;
       nleft--;
       return avail++;
   }

<checking macros 79>+≡
   #define NDESCRIPTORS 512

The call to malloc might return the null pointer, which dalloc passes back to its caller.

<allocate descriptors 82>≡
   avail = malloc(NDESCRIPTORS*sizeof (*avail));
   if (avail == NULL)
       return NULL;

As shown below, Mem_alloc raises Mem_Failed when dalloc returns the null pointer.

Mem_alloc allocates a block of memory using the first-fit algorithm, one of many memory-allocation algorithms. It searches freelist for the first free block that is large enough to satisfy the request and divides that block to fill the request. If freelist doesn’t contain a suitable block, Mem_alloc calls malloc to allocate a chunk of memory that’s larger than nbytes, adds this chunk onto the free list, and tries again. Since the new chunk is larger than nbytes, it is used to fill the request the second time around. Here’s the code:

<checking functions 79>+≡
   void *Mem_alloc(long nbytes, const char *file, int line){
       struct descriptor *bp;
       void *ptr;

       assert(nbytes > 0);
       <round nbytes up to an alignment boundary 83>
       for (bp = freelist.free; bp; bp = bp->free) {
           if (bp->size > nbytes) {
               <use the end of the block at bp->ptr 83>
           }
           if (bp == &freelist) {
               struct descriptor *newptr;
               <newptr ← a block of size NALLOC + nbytes 84>
               newptr->free = freelist.free;
               freelist.free = newptr;
           }
       }
       assert(0);
       return NULL;
   }

Mem_alloc starts by rounding nbytes up so that every pointer it returns is a multiple of the size of the union align:

<round nbytes up to an alignment boundary 83>≡
   nbytes = ((nbytes + sizeof (union align) - 1)/
       (sizeof (union align)))*(sizeof (union align));

freelist.free points to the beginning of the free list, which is where the for loop starts. The first free block whose size exceeds nbytes is used to fill the request. The nbytes at the end of this free block are carved off, and the address of that block is returned after its descriptor is created, initialized, and added to htab:

<use the end of the block at bp->ptr 83>≡
  bp->size -= nbytes;
  ptr = (char *)bp->ptr + bp->size;
  if ((bp = dalloc(ptr, nbytes, file, line)) != NULL) {
      unsigned h = hash(ptr, htab);
      bp->link = htab[h];
      htab[h] = bp;
      return ptr;
  } else
      <raise Mem_Failed 74>

Figure 5.2 shows the effect of this chunk: on the left is a descriptor that points to some free space before it’s carved up. On the right, the allocated space is shaded and a new descriptor points to it. Notice that the new descriptor’s free list link is null.

Figure 5.2. Allocating the tail of a free block

The test bp->size> nbytes guarantees that the value of bp->ptr is never reused. Large free blocks are divided to fill smaller requests until they’re reduced to sizeof (union align) bytes, after which bp->size never exceeds nbytes. The first sizeof (union align) bytes of each chunk are never allocated.

If bp reaches freelist, the list does not hold a block whose size exceeds nbytes. In that case, a new chunk of size

<checking macros 79>+≡
   #define NALLOC ((4096 + sizeof (union align) - 1)/ 
       (sizeof (union align)))*(sizeof (union align))

plus nbytes is added to the beginning of the free list; it will be visited on the next iteration of the for loop and will be used to fill the request. This new chunk has a descriptor just as if it had been previously allocated and freed:

<newptr ← a block of size NALLOC + nbytes 84>≡
   if ((ptr = malloc(nbytes + NALLOC)) == NULL
   ||  (newptr = dalloc(ptr, nbytes + NALLOC,
           __FILE__, __LINE__)) == NULL)
       <raise Mem_Failed 74>

One of the purposes of Mem is to improve the interface to the standard C allocation functions. Maguire (1993) gives a critique of these functions and describes a similar repackaging.

Memory-allocation bugs so pervade C programs that entire companies are devoted to building and selling tools that help diagnose and fix such bugs. One of the best is Purify (Hastings and Joyce 1992), which detects almost all kinds of access errors, including those described in Section 5.3. Purify checks every load and store instruction; since it does so by editing object code, it can be used even when source code is unavailable, such as for proprietary libraries. Instrumenting source code to catch access errors is at the other end of the implementation spectrum; for example, Austin, Breach, and Sohi (1994) describe a system in which “safe” pointers carry enough information to catch a wide range of access errors. LCLint (Evans 1996) has many of the features of tools like PC-Lint and can detect many potential memory-allocation errors at compile time.

Knuth (1973a) surveys all of the important memory-allocation algorithms, and explains why first fit is usually better than, for example, best fit, which looks for the free block whose size is closest to the request. The first-fit algorithm used in Mem_alloc is similar to the one described in Section 8.7 of Kernighan and Ritchie (1988).

There are endless variations on most memory-mangement algorithms, usually designed to improve performance for specific applications or allocation patterns. Quick fit (Weinstock and Wulf 1988) is one of the most widely used. It capitalizes on the observation that many applications allocate blocks of only few different sizes. Quick fit keeps N free lists, one for each of the N most frequently requested sizes. Allocating a block of one of these sizes simply removes the first block from the appropriate list, and freeing a block adds it to the appropriate list. When the lists are empty or the request is for an odd size, an alternate algorithm, such as first fit, is used.

Grunwald and Zorn (1993) describe a system that generates implementations of malloc and free tuned for a specific application. They first run the application with versions of malloc and free that collect statistics about block sizes, frequency of allocation versus deallocation, and so forth. They then feed these data to a program that generates source code for versions of malloc and free customized for the application. These versions often use quick fit with a small, application-specific set of block sizes.