Manual Release

Some languages so thoroughly abstract away the hardware of the computer that we may forget it's there. C and C++ do not. By design, these languages operate under the assumption that programmers want direct control of the machine. With that control comes a lot of responsibility. In particular, programmers must manually shepherd heap memory allocations.

Catch and Release

In C, we allocate heap memory by calling malloc with the requested number of bytes. Our request is handled by the allocator, which is part of the C runtime library linked to our executable. The allocator tracks a list of free memory blocks. It searches through this list until it finds a block with enough bytes to satisfy our request. It then carves out the block from its free list and returns a pointer to it.

When we no longer need the allocated memory in our program, we must manually release it by calling free on the pointer. The responsibility of freeing memory lies entirely with us, the programmers. If we do not free the memory, the data will continue to wastefully occupy RAM until the program finishes or crashes after running out of memory. When the host operating system is low on memory, programs run very slowly as inactive memory segments are temporarily written to disk to open up more space.

If a program runs for only a short time and consumes little memory, we will likely see no adverse effects from not freeing our allocations. The operating system will get the memory back when the program finishes. But small programs sometimes imperceptibly become big ones that serve as the foundation of critical infrastructure. To prevent disaster, we should free our dynamically-allocated memory.

Allocator Implementation

Managing stack memory is relatively easy. New stack frames are allocated at the top when a function is called. When the function returns, the topmost frame is released. The stack only changes at one end, and the changes only happen on calls and returns.

Heap memory is not so simple. The lifetime of each allocation is independent and unpredictable. One statement may allocate a block that persists for the duration of the program, while the next statement allocates a block that is released almost immediately. An allocator may end up running out of memory if it doesn't anticipate this haphazard schedule.

Suppose the heap is only 10 kilobytes in size. A first malloc call requests 4 kilobytes, and the allocator gives it a block at the start of the heap. A second malloc call requests 3 kilobytes, and the allocator gives it a block just after the first allocation. Then the first block is released with free. The remaining allocated block is preceded by a 4-kilobyte block and succeeded by a 3-kilobyte block. Even though a total of 7 kilobytes are free, a request for data just slightly over 4 kilobytes will fail. There's no single block that can meet the request.

When contiguous memory is broken up by allocations, the remaining free memory is split or fragmented into smaller chunks that may not be large enough to satisfy a request. The C language specification does not mandate how malloc and free are implemented, but there are several strategies in use that prevent and recover from fragmentation:

• Some allocators maintain several free lists. One list is for small blocks, one for medium, and one for large. When a request comes in, a block is drawn from the appropriate list. In this way, small blocks are less likely to fragment the memory where big blocks reside.
• When an allocation is freed, the allocator might observe that it is adjacent to other freed blocks and consolidate them into a single larger block that is more likely to be able to serve future requests.
• An allocator might defragment the fragmented memory by copying the scattered allocations into a more compact region. Moving memory would break the pointers returned earlier to the program and would require some kind of pointer abstraction or runtime tracking to update them.

Programming languages generally insulate programmers from the inner workings of the allocator. Usually we don't need to concern ourselves with fragmentation, but C and C++ give us the option to plug in our own allocator if we need to speed up our program.

Memory Safety

An allocator needs to maintain information about its allocated and free blocks in order to do its job. It could reserve some space on the heap to store this information, but predicting how much space will be needed for this metadata is hard. Instead, allocators distribute this bookkeeping information in the allocated and freed blocks themselves.

One piece of information that is commonly stored in a block is its size. When we call malloc, the allocator iterates through its free list and checks each block's size to see if it can satisfy our request. When we call free, the allocator examines the size to see if free blocks are adjacent and merges them if possible.

Each allocated block must be big enough to store both our data and this metadata. If we ask for \(n\) bytes, the allocator searches its free list for a block that has at least \(n + \text{sizeof(metadata)}\) bytes. The metadata is commonly stored at the beginning of the allocated block, and the pointer that we receive from malloc points at the memory just after the metadata. When we call free, the allocator looks at the bytes preceding the pointer we pass it to find the metadata.

If we write into the memory cells preceding the pointer that malloc returns, we will violate the integrity of the allocator's distributed data structure. This will in turn wreak havoc when we free the block later on. The corrupted size may break the merging algorithm. If the recorded size is increased by our wild writes, the freed block will overlap with other blocks, and some bytes may end up being allocated twice.

Even if we don't violate the allocator's metadata, there are other ways for memory to be abused:

• Nothing in the C runtime stops us from reading from and writing to arbitrary addresses. As long as we pick a valid address in static, stack, or heap memory, we won't get a segfault.
• If we forget to reserve space for the null terminator of a string, it may get overwritten by another allocation and cause our string to be treated as a much longer string by functions expecting a null terminator.
• After we call free, we still have a pointer to the old block, much like we might still have a key to an old car or house that we no longer own. We can use that dangling pointer to write into memory that is no longer ours. All freed pointers and their aliases should be set to NULL to eliminate this danger. Any invalid accesses will then result in a segfault, which is better than the silent corruption of memory.
• If we call free twice on the same pointer, we may cause a naive allocator to add the block to its free list twice. Setting a freed pointer to NULL eliminates the danger of double frees, because free does nothing when passed NULL.

So, the manual memory management of C and C++ presents two kinds of dangers:

• Putting the burden of freeing memory on forgetful or overwhelmed programmers means that memory will be leaked.
• Giving programmers direct and unchecked access to memory through pointers means that memory will be violated.

Both manual memory management and pointers are integral features of C and C++. The designers of these languages provide these features in the name of performance. But the designers of other languages have presented safer alternatives.