Assumptions

Most of this discussion will focus on the great history of allocators found in user-level memory-allocation libraries. We draw on Wilson’s excellent survey“Dynamic Storage Allocation: A Survey and Critical Review” by Paul R. Wilson, Mark S. Johnstone, Michael Neely, David Boles. International Workshop on Memory Management, Scotland, UK, September 1995. An excellent and far-reaching survey of many facets of memory allocation. Far too much detail to go into in this tiny chapter! but encourage interested readers to go to the source document itself for more detailsIt is nearly 80 pages long; thus, you really have to be interested!.

Basic interface is provided by malloc() and free()

We assume a basic interface such as that provided by malloc() and free(). Specifically, void *malloc(size_t size) takes a single parameter, size, which is the number of bytes requested by the application; it hands back a pointer (of no particular type, or a void pointer in C lingo) to a region of that size (or greater). The complementary routine void free(void *ptr) takes a pointer and frees the corresponding chunk. Note the implication of the interface: the user, when freeing the space, does not inform the library of its size; thus, the library must be able to figure out how big a chunk of memory is when handed just a pointer to it. We’ll discuss how to do this a bit later on in the chapter.