How are linked lists maintained in memory?

Dynamic memory allocation

Linked lists are inherently dynamic data structures; they rely on new and delete (or malloc and free) for their operation. Normally, dynamic memory management is provided by the C/C++ standard library, with help from the operating system. However, nothing stops us from writing our own allocator, providing the same services as malloc and free.

Differences between C++ and C

In C++, to dynamically allocate memory, we write newtype or newtype[size] for an array, and we get back a pointer, a type*. Internally, both of these boil down to a request for a contiguous chunk of memory of a certain size (sizeof(type) * size). In C, this is provided directly: malloc(bytes) takes a number of bytes as a parameter and returns a void* (a generic pointer) to a contiguous region of memory. Similarly, when we do delete p we are passing the pointer p to the allocator to inform it that the memory is not needed. In C, this is done via free(p). I’ll use the C versions, as they are more low level.

In C++, most standard library classes which need dynamic memory (string, vector, etc.) take a compile-time allocator parameter, which allows a different allocator to be “plugged in” to the class. In C, the standard allocator can only be replaced globally, by linking with a different allocator library.

Restrictions

When we’re writing an allocator, we must bear in mind that we are responsible for handling dynamic memory requests. This means that the allocator code should itself try to be as efficient in terms of memory as possible, and of course, the allocator cannot use any dynamic memory! Thus, although they would be useful, normal implementations of things like linked lists, trees, etc. are not possible in an allocator. We will see that something like linked lists can be used, with some care as to where the “nodes” are placed.

Fragmentation

Fragmentation refers to the tendency of the heap to go from one large available block at the beginning to many small available blocks. It may be possible that, while the total amount of memory is larger than the amount requested, no single block is big enough to satisfy it. For example, suppose we have a heap of size 20, and the following memory requests:

There are theoretically 10 bytes of memory available, but the largest malloc we can handle is of size 5! This particular example is called external fragmentation, fragmentation where the available memory is broken into many small blocks rather than a few large ones.. There’s relatively little an allocator can do about external fragmentation, partly because we are not allowed to move existing blocks (this would require finding every pointer into that block and updating it to the block’s new location, something that is not possible in either C or C++).

(Internal fragmentation occurs when an allocator reserves more space per-block than is actually requested.)

Basic allocator functionality

The allocator maintains some internal state to keep track of free/in-use memory and responds to two kinds of requests:

• malloc(n) – A request for n bytes of contiguous memory. The allocator should return a pointer to such a block, if it has one available, or a null pointer if it does not. The block of memory should be marked as “in-use” in the allocators internal state. (Secure allocators might zero memory before giving it over, to ensure that existing data is not “leaked”.)

• free(p) – An offer to release the memory pointed to by p. The allocator should mark the memory used by p as not in-use. (Error-checking allocators might fill the memory with a recognizable byte pattern so that use-after-free errors are easy to detect.)

We assume that once a given region has been given to us (as a pointer returned from malloc) the allocator will not later give us a pointer to the same region; that is, blocks of memory returned by malloc are required to not overlap each other. Similarly, when we release a block with free, we expect that only that block will be affected. The allocator has access to a large region of memory (the heap section), which it may be able to expand via operating system request, but which is otherwise reserved entirely for the allocator’s use.

No-free allocation

The simplest possible allocator is one where we simply add each allocated block of memory immediately after the end of the previous allocation. That is, if we have the following three requests:

then we have the following memory layout:

When memory is free-d, we do nothing. Allocated memory is never released, until the program ends. The reason why we make this choice is that keeping track of which blocks of memory are in-use and which are not requires a fair bit of complexity, so we avoid it by not doing it at all.

This allocator’s internal state is simply a pointer fp to the next free address (e.g., in the above, this would point to address 22). The implementation of malloc is thus:

while free is just

The only advantages to this allocator are that both allocation and deallocation run in \(O(1)\) time. Despite its simplicity, this “never-free” allocator can be quite useful for structures which are partially dynamic, but which are created once, at program startup, and then not freed until program end.

Note that while we can’t free individual blocks, we can free the entire heap, all at once, and revert to a state where nothing has been allocated.

Stack-based allocation

Looking at the previous allocator, we can see that there always one block of memory which we could free easily: the last one. If a free is received for the most-recently allocated block, we can deallocate it by simply decrementing fp by the size of the block. Note that we do not above store the size of the blocks anywhere, so we will need to add some extra information. At the end of each block, just after the last byte, we will write a pointer to the beginning of the block, and similarly, before the beginning of the block, we will write a pointer to the end. This allows us to navigate through the blocks as if they were a doubly-linked list.

Each block now looks like this:

Given a pointer to a block, we can find its starting record (containing its size) by simply going back 8 bytes (1 qword), and then we can find its ending record by adding the size to the pointer.

Malloc must be implemented to maintain these structures:

free looks at the block being released and checks to see if it is the last block allocated; this will be the case if fp points to the address immediately after the start record of the block.

This allocator can free all the memory allocated, provided that calls to free arrive in the opposite of the order of their corresponding mallocs. If this order is not maintained, then some memory will be lost.

With a simple modification, we can allow out-of-order frees to at least partially free their memory. We will add a one-bit flag to the size record at the beginning of every block set to 0 if the block is unused, or 1 if it is used. (Although pointers are 64-bit on x86-64, the system actually only supports addresses up to 40 bits in length; thus, the high 24 bits of every pointer are available for us to use for other purposes.) When we free a block, we perform the following steps:

• If it is not the last block then we simply mark it as unused (set its in-use flag to 0).

• If it is the last block, then we free it as above, and then we repeatedly check for not-in-use blocks before it, and free those as well.

Thus, a chain of not-in-use blocks at the end of the heap will all be freed at once. Note that we still do not reuse the memory of not-in-use blocks, unless they are “really” freed. A block’s memory is only really freed if every block after it has also been freed.

A general-purpose allocator

Using the idea of blocks arranged into a linked-list-like structure, with a flag on each block for “in-use” or not, we can generalize the above to a general-purpose allocator which correctly frees memory on every free, not just those that are in the right order. This is called a free list.

Initially, we set things up so that the entire heap is treated as a single entry in the free-list, marked as not in use. Because we’re not treating the list in a stack-like manner, there’s no need for the “backwards” pointers, so each block has a small record before the beginning which consists of a pointer to the next free block. Because the list only contains free blocks, there’s no need to record whether an entry is free or in-use.

To malloc a block, we search through the list for a block whose size is at least as big as requested. Of all these blocks, we have a choice as to which one to use, determined by the allocation strategy:

• First Fit: use the first block in the list which fits

• Best Fit: use the block in the list whose size is closest to the requested size.

• Use the most/least recently free-d block (LIFO, FIFO).

If the size of the block chosen is larger than the requested size, then we split the block; part of it becomes used, and the remainder is still free. If the size of the block exactly matches the requested size, then the block is removed from the free list entirely.

When a block is freed, we add it to the list. This can be done in several ways:

• Add to the front of the list. (When used with first-fit, this results in LIFO-like behavior).

• Add to the back of the list. (FIFO)

• Insert it into the list so that the list is always ordered by address. This is most common, as the structure of the list mirrors the structure of the memory layout.

Insert-in-memory order has the advantage that it makes it relatively easy to coalesce free blocks which are physically adjacent to each other. E.g., if the free list contains an entry for a block 10-19, and an entry for a block 20-49, these should be removed and replaced with a single entry 10-49. This is easiest to detect if the blocks in the list are address-ordered.

Eager coalescing refers to coalescing done during free. Deferred coalescing is done later, either during a malloc (if no block of sufficient size is found), or perhaps during a later free.

The main disadvantage to this allocator is speed: requests for memory must traverse the list, making them run in \(O(m)\) time, where r is the number of malloc calls so far. Calls to free run in \(O(1)\), as in the worst case, only three blocks will need to be examined and coalesced.

Fixed-size allocator

If we know that every allocation request will be for a block of the same size (or we know that they will all be ≤ some maximum size, and we don’t mind wasting space), we can build a specialized version of any of the above allocators where the block size is hard-coded. We can avoid storing the block size in the records around each block, so these records become either much smaller or, in some cases, non-existent. (E.g., finding the next/previous block is easy if they all have the same size.) A fixed-size allocator is sometimes called an object pool (or memory pool), because a typical use of it is storing objects all of the same type (and hence, having the same size).

An object pool also has the advantage that an allocation for k objects takes the same amount of time as for 1 object, again, because the size of the objects is fixed.

Some allocators reserve a section of the heap for “small” object allocations, and use a fixed-size allocator only in this region, while using a more general method for the rest of the heap.

It’s also possible to reserve several regions, each dedicated to a particular size; if a free space cannot be found in a smaller-sized region, we proceed to search the next larger region.

Linked List explained