The last type of memory allocation is known as a dynamic memory
allocation, which corresponds to memory allocated via
operator new. The sizes, addresses and contents of such memory vary
at run-time and so can cause a lot of problems when trying to diagnose a fault
in a program. These memory allocations are called dynamic memory allocations
because their location and size can vary throughout the lifetime of a program.
Such memory allocations are placed in a system memory area called the heap, which is allocated per process on some systems, but on others may be allocated directly from the system in scattered blocks. Unlike memory allocated on the stack, memory allocated on the heap is not freed when a function or scope is exited and so must be explicitly freed by the programmer. The pattern of allocations and deallocations is not guaranteed to be (and is not really expected to be) linear and so the functions that allocate memory from the heap must be able to efficiently reuse freed memory and resize existing allocated memory on request. In some programming languages there is support for a garbage collector, which attempts to automatically free memory that has had all references to it removed, but this has traditionally not been very popular for programming languages such as C and C++, and has been more widely used in functional languages like ML1.
Because dynamic memory allocations are performed at run-time rather than compile-time, they are outwith the domain of the compiler and must be implemented in a run-time package, usually as a set of functions within a linker library. Such a package manages the heap in such a way as to abstract its underlying structure from the programmer, providing a common interface to heap management on different systems. However, this malloc library must decide whether to implement a fast memory allocator, a space-conserving memory allocator, or a bit of both. It must also try to keep its own internal tables to a minimum so as to conserve memory, but this means that it has very little capability to diagnose errors if any occur.
In some compiler implementations there is a builtin function called
alloca(). This is a dynamic memory allocation function that allocates
memory from the stack rather than the heap, and so the memory is automatically
freed when the function that called it returns. This is a non-standard feature
that is not guaranteed to be present in a compiler, and indeed may not be
possible to implement on some systems2. However,
the mpatrol library provides a debugging version of this function (and a few
other related functions) on all systems, so that they make use of the heap
instead of the stack.
As can be seen from the above paragraphs, dynamic memory allocations are the types of memory allocations that can cause the most problems in a program since almost nothing about them can be used by the compiler to give the programmer useful warnings about using uninitialised variables, using freed memory, running off the end of a dynamically-allocated array, etc. It is these types of memory allocation problems that the mpatrol library loves to get its teeth into!