This article was original published for the Pennsylvania State University Computer Science 461 course on programming language concepts in late 2009; I’m publishing it here as I had to research again into efficient memory allocation schemes for my new programming language coreBasic.

Introduction

Dynamic memory allocation is a fundamental feature of many computer programming languages, either sometimes called explicitly by the developer, or implicitly by the language. Certain languages have their entire fundamental data structures, such as LISP’s list element, based on dynamic allocations. This essay will discuss what is dynamic memory allocation, its usage within several programming language paradigms, as well as some implementations and their varying specialization’s.

Dynamic memory allocation is a common feature of programming languages (or libraries, such as in C/C++[3]) that allow allocation of varying sized pieces of data at run-time. This is different from the stack, as stack allocations are based on a first-in-last-out concept, such that when returning from a function data can be lost unless explicitly posted to a common “return” point. The stack structure is fast and self-managed, based on the notion of “pushing” and “popping” data, but is not designed for retaining significant data when moving between functions. This is due to the fact that “activation-frames” are relatively small and disappear when returning from a function[3][4]. The heap, based on dynamic memory allocation, allows for any number of any sized allocations (bounded by the virtual memory the operating system has) that remain persistent in the process until explicitly released by the program. Though not as fast and not self-managed as the stack is, the power is in the fact that data can stay as long as the programmer wants during the lifetime of the process.

Continue reading for more!

Another justification of the heap is that many algorithms are unable to perform their tasks without the need of a variable sized array or object, and thus require special allocations at run-time. An example of this could be that of a web-server that requires retention of user data at run-time in main memory, which could grow at any point during the process life-time. All multiprocess operating systems also need special dynamic allocation systems that support the internals of process swapping, resource management, and storage space for the kernel’s own data[1]. With the advent of the object-oriented programming paradigm, and more recently “managed code”, dynamic memory allocators have had to change to better fit their programming language environments.

Dynamic memory allocation is a necessary tool needed by all programmers, though some languages either directly support them via the language itself, or include standard libraries that do this work[3]. What is very interesting to note is the depth of this relationship that varies between each language and programming paradigm. From functional, to procedural, to imperative; all approaches need heap storage for certain problems.

Discussion of a Language’s Heap System

All programming languages usually take one of three different approaches to dynamic memory allocation systems. The first is to have the developer given full control of the heap, such as in the C programming language. The second is when the developer has partial control, with self-managing units of memory such as lists in LISP or pseudo-managed objects in Objective-C. The third and final approach is that of having a garbage collection / reference counting system, fully managing on allocations.

LISP, the second oldest programming language, uses dynamic memory allocations as a method of managing one of its core features: “list”. Lists, within LISP, are a basic data type that acts as a generic linked-list system[4]. Each list element is a tuple that contains both a value and pointer, in which the pointer points to the next element. Though such a data structure is small and simple, its system of storage is based on the heap. When calling, running, and ultimately returning from a LISP function, lists would have to be passed to and from function calls. Though the stack could be used as a system of posting and retrieving these lists, the actual implementation is far more “clean”. Most of these list cells are stored on the heap, in which an implicit deallocation system exists to automatically remove those list elements that no longer have references to them. This is powerful, as only a pointer to the start of the list is manipulated by functions, while the list itself stays unmoved in memory. What is also interesting to note about LISP’s allocation system is that is uses a reference counting system, similar to that found in Java and other “manages” languages[4], and can be abused to make variables persistently stay in memory by a self-reference.

C, an imperative language, takes the opposite extreme from LISP: all items created in C are strictly on the stack, unless explicitly allocated onto the heap using a standard C-library function that is not officially apart of the language, but of the standard libraries[3]. Developers have to explicitly manage their own memory as well, as there is no built-in garbage collection or reference counting system. C++, an object-oriented version of C, does come with heap-allocation support directly written the language, yet still does not provide any special properties when working with objects created on the heap. C++’s “new” operator does provide some special optimization code, depending on the compiler used and options set, such that it might preemptively allocate several objects into a uniform block, attempting to prepare memory for similar allocations; this is from the assumption that C++ code is more likely to allocate many smaller objects that C code[3]. Objective-C does have the same abilities as standard C, yet also includes several “smart pointer” systems that enable garbage collection, but yet again are only features of the standard library, and not the language itself.

Java, as well as C#, are “managed” object oriented programming languages. They are considered “managed” as all objects in the language are allocated strictly on the heap (except for certain built-in types such as boolean, float, etc.). Though this storage mechanism takes the other extreme of the C programming language approach, it can be found more useful as the system itself is able to identify objects that are no longer used and remove them through a garbage collection system, combined with a reference counting system. This allows developers to no longer worry about memory leaks (allocations on the heap with lost references), and thus speeds up the development time. Even with this improvement, there is a clear loss of run-time performance as the language’s run-time must interrupt itself to purge any unneeded objects in the heap. It could be said that building hardware that caters to such a run-time might increase performance to be competitive with a native programming language, though it is an unrealistic note as the consumer market is dominated by the x86 architecture. Languages such as Objective-C support both a fully managed and fully unmanaged run-time, based on the developers choice.

It is important to note the power of garbage collection in programming languages. There exists several approaches to garbage collection, such as the removal of unreferenced heap allocations. This is done such that the programmer no longer has to worry about explicit releases, allowing the system to preemptively release needed space for future run-time allocations. Some of these systems are strictly based on the standard allocation system, as discussed below, though with an added level of management for the release mechanics[3]. This added level is simply a secondary process, or interrupting call, that will step in on an event (such as a certain amount of memory allocated) or time (such as every 100 milliseconds) that will then use a mark-and-sweep[4] algorithm to note unreferenced blocks.

Discussion of a Dynamic Memory Allocator

The majority of general use dynamic memory allocators, such as that found within the GNU standard C library implementation, must be designed to be both memory and time efficient. The Slab allocator, as an example used within the Linux kernel, is efficient at quickly allocating new objects of uniform size as well as keeps fragmentation as low as possible[1]. Another allocator also used with Linux called Hoard, uses a similar approach but with an n-tree-like internal system[2]. Though each dynamic allocation system is slightly different, most derive from a form of linked-list data structures. The algorithms that go through these data structures and return a selected allocated space are akin to basic search algorithms, with special properties based on certain needs of which ever system it is being developed for.

The heap, or general area in which dynamic memory allocations take place on, is usually located at lower addressing. This is common as the heap is usually placed on the opposite side of where the stack is located, both facing each other. This enables both to grow towards each other with the largest spacing possible, minimizing the chance of collision. The operating system usually manages the upper and lower bounds of this segment, as set by POSIX standard functions such as brk/sbrk[3], though the function “mmap” is much more commonly used in modern UNIX/Unix-like systems. These functions sets the maximum size of the heap and stack, based on certain hardware optimizations. Once the heap itself has been allocated, the dynamic memory allocator must segment the heap into it’s own format for use.

The basic design of most dynamic memory allocation systems is to segment this heap into a linked-list of allocated/free memory segments. Each segment has a small data structure at it’s head that notes its current state of usage (allocated or free), as well as size, and the location of the next segment. Each time a process calls for a new allocation (through new, malloc, etc.), the list is traversed by a search algorithm. Once a suitable segment is found, it may sometimes be partitioned into different pieces to make sure that a small allocation does not waste a large free block, thus increasing memory throughput (the optimality of memory usage)[3]. The target allocation segment’s address is returned, while any new partitions are added to the internal free list. Such a structure can be seen in figure 1.

Figure 1: A sample single-linked list allocation system

Once the heap data structures are initialized, we then wait for a process to call the dynamic memory allocation system with a desired allocation size. Depending on the algorithm’s internals, we might want to round up the given size to a more friendly value. This may also help with paging optimization with the hardware. Once the size is determined, there are several different approaches to seek the best fitting segment for this size within the heap. Most of these algorithms fall into “best fit” and “first fit” categories, though others exist. The first category, as the name implies, is to find the most optimal space to place this allocation in. If there does not exist a segment large enough, the allocation fails, yet if the best fitting segment is still too large for the target size, segmentation occurs: the target segment will be split into two new segments. The first segment will be marked as the allocated segment, while the second is marked as a new un-allocated segment and will be inserted into the appropriate list. The benefit of this algorithm is it has optimal memory usage, as well as keeps fragmentation low, but does come at the cost of relatively slow-speeds. The second search method is “first fit”, in which the first free segment of memory that can fit the desired allocation size is used, and then segmented as needed. Though this is the fastest possible approach, is is not memory optimal as many fragmentations can occur.

There can be many variances from this basic allocation design, such as having a homogeneous free and allocated list, rather than a single list that is mixed of both[3]. This eliminates the overhead cost of walking through segments that are already allocated when attempting a new allocation, but does add other overheads when transferring segments between lists. Other allocation systems, such as the Slab allocator, have a cache system such that several linked-lists exist and are ordered based on size, and have internal “mappings” to help searching for correct sizes more quickly[1].

The paired free/release functions are meant as a reclamation system to retain and coalesce memory on the heap. These functions are key to preventing fragmentation, and have as much to do with optimal memory usage as the allocation function does. When a segment is released, coalescing logic is applied: If the segment to the left of this segment is free, they are merged into one large free segment. The same logic is applied to the right segment.

What is interesting to note, for an end-developer, is that many closed-source dynamic memory allocation systems, such as those found on the Windows platform, can be easily reverse-engineered by attempting to read or write past the segment heads or tails. By doing this, a developer can find what kind of variables are used in the internal implementations, as well as the general system’s design for allocation rules. As noted by Kamp[5], there are possible security vulnerabilities due to this as well, though are easily prevent by adding extra bounds-checking logic to allocation and release functions.

Conclusion

The software industry has clearly adopted object-oriented programming as the de-facto approach to general design. With this, dynamic memory allocation systems must evolve with them. A new emergence of “managed” code, a somewhat new twist to several language paradigm, has introduce new approaches to dynamic memory allocations. From LISP to Java, each language has a unique relationship with such an allocation system, which seems to be a fundamental aspect and necessity of all computer programming languages.
References

1. Daniel P. Bovet and Marco Cesati, “Understaind the Linux Kernel”, Third Edition, O’Reilly Media, 2005.
2. Emery Berger, “The Hoard Memory Allocator”, “www.hoard.org”.
3. Frantisek Franek, “Memory as a Programming Concept in C and C++”, Cambridge Univ. Press, 2004.
4. John C. Mitchell, “Concepts in Programming Languages”, Cambridge Univ. Press, 2002.
5. Poul-Henning Kamp, “Malloc(3) revisited”, Usenix, 1998.