P.J. Plauger is senior editor of The C Users Journal. He is secretary of the ANSI C standards committee, X3J11, and convenor of the ISO C standards committee, WG14. His latest book is The Standard C Library, published by Prentice-Hall. You can reach him care of The C Users Journal or via Internet at pjp@plauger.uunet.uu. net.
Introduction
Few functions are as much fun to tinker with as the storage allocation functions that come with the Standard C library. I can't begin to count all the variations of malloc and friends that have crossed my desk as editor. I see several reasons for this phenomenon:
Unfortunately, these functions are also easy to get wrong:
- They form a compact subset that can be replaced as a unit.
- They can almost always profit from the addition of debugging hooks.
- They can often be made more efficient for any given pattern of usage.
If you're ever tempted to tinker in this arena, you may as well start from a firm foundation. This column describes the storage management functions in detail. It also presents an implementation that works on a broad class of architectures. The code also seems to be fairly free of bugs.
- They involve several tricky algorithms that are notoriously error prone.
- They interact with computer architectures in various nonobvious ways.
- They need to be as efficient as possible.
Kinds of Storage
The data objects in a Standard C program occupy three kinds of storage:
The functions that manipulate allocated storage are the storage allocation functions declared in <stdlib.h>.
- The program allocates static storage and stores initial values in it prior to program startup. If you specify no initial value for (part or all of) a data object, the program initializes each of its scalar components to zero. Such a data object continues in existence until program termination.
- The program allocates dynamic storage upon each entry to a block. If you specify no initial value for a data object, its initial content is indeterminate. Such a data object continues in existence until execution of the block terminates.
- The program allocates allocated storage only when you call one of the functions calloc, malloc, or realloc. It initializes such a data object to an array of zero characters only if you call calloc. Otherwise, its initial content is indeterminate. Such a data object continues in existence until you call free with its address as the argument or else until program termination.
Static storage remains stable during program execution. Dynamic storage follows a last-in/first-out discipline. It can be implemented on a stack. Often, dynamic storage shares the call stack with function-call and return information. Allocated storage follows no such tidy discipline. The program can intermix the allocation and freeing of such data objects in arbitrary order. Hence, the Standard C library must maintain a separate pool of storage called a heap to satisfy requests for controlled storage.
In some implementations, the call stack and the heap contend for a limited amount of storage. Allocate enough storage with malloc and you may limit the depth to which you can call functions later in the program. Or you may simply run out of space on the heap. In any event, it is simply good hygiene to allocate only what storage you need and to free it as soon as you're done with it.
Be aware that allocated storage involves certain overheads. Accompanying each allocated data object is enough information for free to determine the size of the region being freed. Allocate 1,000 one-character data objects and you can easily consume four to eight times as much storage on the heap. The heap is also subject to fragmentation. Allocating and freeing data objects on the heap in arbitrary order inevitably leaves unusable holes between some of the allocated data objects. That too lowers the usable size of the heap.
Don't overreact to this knowledge. Gather related data into a structure and allocate it all at once. That minimizes heap overhead, to be sure, but it is also good programming style. Do not gather unrelated data just to save heap overhead. Similarly, allocate data objects with similar lifetimes all at once, then free them at about the same time. That minimizes heap fragmentation, but it too is good style. Do not advance or defer unrelated heap operations just to minimize fragmentation. The storage-allocation functions are an important aid to programming flexibility. Use them as they are intended to be used.
What the C Standard Says
7.10.3 Memory management functions
The order and contiguity of storage allocated by successive calls to the calloc, molloc, and realloc functions is unspecified. The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object and then used to access such an object or an array of such objects in the space allocated (until the space is explicitly freed or reallocated). Each such allocation shall yield a pointer to an object disjoint from any other object. The pointer returned points to the start (lowest byte address) of the allocated space. If the space cannot be allocated, a null pointer is returned. If the size of the space requested is zero, the behavior is implementation-defined; the value returned shall be either a null pointer or a unique pointer. The value of a pointer that refers to freed space is indeterminate.
7.10.3.1 The calloc function
Synopsis
#include <stdlib.h> void *calloc(size_t nmemb, size_t size);Description
The calloc function allocates space for an array of nmemb objects, each of whose size is size. The space is initialized to all bits zero.127
Returns
The calloc function returns either a null pointer or a pointer to the allocated space.
7.10.3.2 The free function
Synopsis
#include <stdlib.h> void free(void *ptr);Description
The free function causes the space pointed to by ptr to be deallocated, that is, made available for further allocation. If ptr is a null pointer, no action occurs. Otherwise, if the argument does not match a pointer earlier returned by the calloc, malloc, or realloc function, or if the space has been deallocated by a call to free or realloc, the behavior is undefined.
Returns
The free function returns no value.
7.10.3.3 The malloc function
Synopsis
#include <stdlib.h> void *malloc(size_t size);Description
The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate.
Returns
The malloc function returns either a null pointer or a pointer to the allocated space.
7.10.3.4 The realloc function
Synopsis
#include <stdlib.h> void *realloc(void *ptr, size_t size);Description
The realloc function changes the size of the object pointed to by ptr to the size specified by size. The contents of the object shall be unchanged up to the lesser of the new and old sizes. If the new size is larger, the value of the newly allocated portion of the object is indeterminate. If ptr is a null pointer, the realloc function behaves like the malloc function for the specified size. Otherwise, if ptr does not match a pointer earlier returned by the calloc, malloc, or realloc function, or if the space has been deallocated by a call to the free or realloc function, the behavior is undefined. If the space cannot be allocated, the object pointed to by ptr is unchanged. If size is zero and ptr is not a null pointer, the object it points to is freed.
Returns
The realloc function returns either a null pointer or a pointer to the possibly moved allocated space.Footnote
127. Note that this need not be the same as the representation of floating-point zero or a null pointer constant.
Using the Functions
calloc — Use this function to allocate an array data object and store zeros in all of the characters that constitute the data object. You can assume that the size of any character type is 1, but otherwise you should use the operator sizeof to determine the second argument. Do not specify a second argument whose value is zero.For maximum portability, don't assume that any floating-point values thus become zero or that any pointers become null pointers. Probably they are, but you can't count on it. Nor should you assume that the product of the two arguments is all that matters. An implementation can select a storage alignment for the allocated data object based on the size specified by the second argument. Thus, you should allocate:
free — Use this function to deallocate storage you allocated earlier in the execution of the program by calling calloc, malloc, or realloc. You can safely call free with a null pointer. (The function does nothing in this case.) Otherwise, the argument to free must be the value p returned by one of the three functions listed above. Don't call free((char *)p + N) to free all but the first N allocated characters — call realloc(p, N) instead. Once you call free (p) don't access the value currently stored in p in any expression — some computer architectures may treat such an access as a fatal error.
- an array of N int as calloc(N, sizeof (int))
- a data object of type struct x as calloc(1, sizeof (struct x))
You are not obliged to free storage that you allocate. A good discipline, however, is to free all allocated storage as soon as possible. Freed storage can be reallocated, making better use of a limited resource. Moreover, some implementations can report storage allocated at program termination. That helps you locate places where you unintentionally fail to free storage.
malloc — See the discussion of calloc, above. Use malloc to allocate a data object that you intend to initialize yourself. If the data object contains only integers and you want them all set to zero, call calloc instead. The same considerations apply for the argument to malloc as for the second argument to calloc.
realloc — The common use for this function is to make a previously allocated data object larger or smaller. If you make it larger, the values stored in the added portion are undefined. If you make it smaller, the values stored in the retained portion remain unchanged. In either case, however, the function may alter where the data object is stored. As with free, described above, you shouldn't access the argument value in any expression once realloc returns. Replace the call realloc(NULL, size) with malloc(size). The same considerations apply for the second argument to realloc as for the second argument to calloc, described above.
Implementing the Functions
Several functions cooperate to allocate and free storage during program execution. You can implement these functions many ways. I chose to maintain a pool of available storage (the "heap") as a singly-linked list. The list elements remain in sort by their addresses in storage. A static pointer points to the start of the list — the element with the lowest address.Listing 1 shows the file xalloc.h. It is an internal header that is included by all of the storage allocation functions. It defines several macros and types. A list element, for example, has type _Cell. At least it begins with such a data object. The member _Size gives the useful size in bytes of the entire element, which is typically much larger than a _Cell data object. The member _Next points to the next element of the available storage list.
An allocated element still begins with the member _Size. That information may be needed later if the program elects to free the allocated element. The program does not see this size information, however. The allocation functions return a pointer to the usable area beyond the member _Size. The macro CELL_OFF gives the offset in bytes of the usable area from the start of the allocated element.
Many computer architectures care about storage boundaries. Some require that certain types of data objects begin at a storage address that is some multiple of bytes. Typical multiples are two, four, or eight bytes. Other computer architectures do not require such alignment, but execute faster when manipulating data objects that are properly aligned. The macros defined in <stdarg.h> typically must correct for holes left by the alignment of argument data objects.
The storage allocation functions also fret about storage boundaries. They assume that a worst-case storage boundary exists. Any data object aligned on such a boundary is thus suitably aligned. The internal header <yvals.h> defines the macro _MEMBND to specify this worst-case storage boundary. For a boundary of 2N, the macro has the value 2N-1. On an Intel 80X86 computer, for example, the macro can be zero (no constraints). You should probably make it at least 1 (two-byte boundaries). For such a computer with 32-bit memory, you might want to make it 3 (four-byte boundaries).
Much of the ugly logic in the storage allocation functions results from this attempt to parametrize the worst-case storage boundary. The macro CELL_OFF assumes that a list element begins on a worst-case storage boundary. It determines the start of the usable area as the next such boundary beyond the space set aside for the member _Size. Similarly, the macro SIZE_CELL yields the smallest permissible value of _Size for a list element. The list element must be large enough to hold a _Cell data object. It must also end on a worst-case storage boundary.
The remainder of xalloc.h is best explained along with the function malloc. Listing 2 shows the file malloc.c. The function malloc endeavors to allocate a data object of size bytes. To do so, it looks for an element on the list of available storage that has a usable area at least this large. If it finds one, it splits off any excess large enough to make an additional list element. It returns a pointer to the usable area.
The internal function findmem, defined in malloc.c scans the list of available storage. It retains two static pointers in the data object _Aldata of type _Altab, defined in xstdio.h:
Whenever possible, findmem begins its scan where it left off on a previous call. That strategy reduces fragmentation at the start of a list by distributing usage over the entire list.malloc itself and the function free cooperate in maintaining these two pointers.
- _Head points to the start of the list. If the list is empty, it contains a null pointer.
- _Plast is the address of the pointer to the next list element to consider. It can point to _Aladata._Head or to the _Next of an available list element. Or it can be a null pointer.
If findmem cannot find a suitable element on the available list, it endeavors to obtain more storage. (Initially the heap is empty, so the first request takes this path.) It calls the function _Getmem, declared in xalloc.h to do so. That primitive function must return a pointer to a storage area of at least the requested size, aligned on the worst-case storage boundary. If it cannot, it returns a null pointer.
The macro SIZE_BLOCK, defined in xalloc.h, specifies the smallest preferred list-element size. I have set it to 512, but you may want to change it. findmem first requests the larger of the required size and SIZE_BLOCK. If that fails, it halves the requested size repeatedly until the request is granted or a request of exactly the required size cannot be honored. This strategy favors larger element sizes but takes what it can get. If the request is granted, findmem makes the new storage look like a previously allocated element. It calls free to add the storage to the available list. The next iteration of the scan loop should discover this storage and use it.
The function _Getmem depends strongly on the execution environment. You must tailor this primitive extensively for each operating system. For completeness, I show here a version of _Getmem that runs under UNIX.
Listing 3 shows the file xgetmem.c. As with the earlier UNIX primitives I've presented, it assumes the existence of a C-callable system service with its name altered to a reserved form. _Sbrk performs the UNIX sbrk system service, which allocates a block of storage. Note that _Sbrk expects an int argument. Hence _Getmem must ensure that a very large request is not misinterpreted.
Listing 4 shows the file calloc.c. It calls malloc to allocate storage, then sets its individual characters to zero. A more cautious version would check that the product of the two arguments is of a reasonable size.
Listing 5 shows the file free.c. It frees storage earlier allocated by malloc or realloc. Two common programming errors cause trouble for free:
Probably no amount of checking is enough to keep ill-formed programs from sabotaging free. This version makes just one or two cursory checks. If the _Size member is not a multiple of the worst-case storage boundary, it has been altered or was never allocated. If the element to be freed overlaps an existing element on the available list, it has been freed twice. Both errors cause free to return without freeing the designated storage. A more helpful version might report a signal or generate a diagnostic. At the very least, is might store a nonzero value in errno, defined in <errno. h>.
- Invalid stores alter the value of the _Size member.
- A program calls free with an invalid pointer. Either the data object was never allocated or it has already been freed.
Most of the work of free involves finding the appropriate place to insert the freed element in the list of available storage. If the freed element is adjacent to one or two existing list elements, the adjacent elements are combined. That minimizes fragmentation of the list.
Note that free alters the scan pointer _Aldato._Plast. That is necessary because the stored pointer may be to a list element now merged with another. I chose to have the scan resume just after the freed element. That's an easy address to determine here. This approach also spreads the use of storage more uniformly across the list. And it postpones as long as possible recycling freed storage (a questionable kindness to buggy programs). On the other hand, it lowers performance whenever the heap grows by calling _Getmem. Here is an area that can occupy a designer for a long time.
Listing 6 shows the file realloc.c. The function realloc tries to allocate a larger storage area if that is necessary. It also tries to trim the existing storage area if that proves to be worthwhile.
This version doesn't try quite as hard as it could. If a larger storage area is required, the function insists on allocating a new area before freeing the existing area. That eliminates any worries about preserving data stored in the usable area during the shuffle. But it precludes one possibility — the larger area may be available only after the existing area is freed. Here is yet another place where an ambitious implementor can make improvements.
This article is excerpted from P.J. Plauger, The Standard C Library, (Englewood Cliffs, N.J.: Prentice-Hall, 1992).