Memory Management/Printable version

Memory Management

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/Memory_Management

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.

Introduction

Memory management is the task of allocating, using, and freeing memory in a computer system. In this book, we will talk about memory management, including allocators and garbage collectors.

Manual Memory Management

In every application, you must allocate new storage before you can use it, and then you must return all such storage to the operating system when you are finished. While some languages handle all of this for you, lower-level languages like C or C++ sometimes require more effort by the programmer to manage memory. There are several ways to do this: implicit and explicit.

Implicit memory allocation is memory that is allocated, typically on the system stack, by the compiler. This occurs when you create a new variable:

void my_func(void) {
  int x;
  char y;
  int z[25];
  ...
}

Here, space is allocated on the system stack for the variables x, y and z when the function is called, and the space is reclaimed automatically when the function exits.

Explicit memory allocation occurs through pointers, and calls to the memory management functions:

#include <stdlib.h>
void my_func(void) {
  int * z;
  z = (int *)malloc(25);
  ...
}

Here, we still have variable z which is still being used as an array of 25 integers. However, this storage is not automatically reclaimed when the function exits. This has the added benefit that an array created this way can be returned from the function:

RIGHT	WRONG
int *my_func(void) { int * x; x = (int *) malloc(25); return x; }	int *my_func(void) { int x[25]; return x; }

Why is one way right, and the other is wrong? The answer is scope: In the left example, the array is created on the heap, and the memory is not reclaimed after the function exits. This means that the memory can still be used even after the function returns. In the example on the right, however, the memory is allocated on the stack and disappears when the function exits.

There are also many places where memory needs to be created in a size which is not known at compile-time. Consider a web browser that needs to allocate enough storage to store the downloaded HTML text of a webpage. Since webpages can be all different sizes, we can't possibly know the sizes of them all when we compile, we must allocate the storage at runtime with malloc or an equivalent.

Memory that is allocated on the stack and is fixed in size and scope is called static. Memory that uses malloc to be allocated at run time is called dynamic.

Freeing Dynamic Memory

When you allocate memory from the heap using malloc or something similar, you obtain a pointer to allocated memory from the system. When you are done with it, you must free the memory, to return it back to the system. Failure to return all the memory that you allocate is called a memory leak. In C, you can free memory using the free() function.

Problems with Memory Management

When you allocate memory, you must always be careful to release your allocated memory back to the system. Herein is the problem: if your system is complicated and needs to allocate many small chunks of memory, you need to be certain to free all those individual little chunks as well. This can be all the more difficult if you are in a dynamic situation where memory is being allocated and deallocated continuously, and memory chunks must stay available for random lengths of time.

To overcome these complications automatic memory manager systems, such as garbage collectors, can be employed to try to automate the memory allocations and deallocations.

Garbage Collection

We've already seen how complicated memory management can be, especially if you are allocating and freeing memory manually. Thankfully, there is a class of systems known as garbage collectors which can help to automate the process of memory reclamation.

What are Garbage Collectors

Garbage Collectors (GC) are systems or sub-systems that are used to manage dynamic memory automatically. Here is how they work:

1. Instead of calling malloc and free directly, these are replaced with a function from the GC called "gc_malloc". Obviously, this function can be named anything in practice.
2. When we call gc_malloc in our program, the garbage collector calls malloc to allocate memory from the system, and find some way to keep track of the memory. There are many ways to track memory, and we will discuss some of them in future chapters
3. The program runs like normal, allocating memory from the GC when needed, but never freeing the memory explicitly.
4. The GC performs a function called a trace intermittently. This can be a synchronous or asynchronous occurrence. During the trace, the GC starts with a set of objects that are immediately visible to the system, called the root set of memory objects. It follows pointers in these memory objects to child-objects. When it reaches an object, it marks it as being alive.
5. When the GC has finished the trace, and no more pointers can be followed, the reclamation phase begins. All objects which are not marked alive are considered dead, because no pointers from the program point to them, and therefore they cannot be possibly accessed by the program. All dead objects are freed by the GC.

Types of Collectors

There are two primary types of garbage collectors, although often a hybrid approach is found between these to suit particular needs. The first type, the one which might be the most intuitive, is a reference counting collector. The second one, which is most similar to what we described above, is a tracing collector.

Reference Counting Collector

When a new memory object is allocated by the GC, it is given an integer count field. Every time a pointer is made to that object, a reference, the count is increased. So long as the count is a positive non-zero integer, the object is actively being referenced and is still alive.

When a reference to the object is removed, the count is decremented. When the count reaches zero, the object is dead and can be immediately reclaimed.

There are a number of points to remember about Reference Counting collectors:

1. Circular references will never be reclaimed, even if the entire set of objects is dead.
2. Reference counting is pervasive: The entire program must be made aware of the system, and every pointer reference or dereference must be accompanied by an appropriate increment or decrement. Failing to maintain the count, even once in a large program, will create memory problems for your program.
3. Reference counting can be costly, because counts must be manipulated for every pointer operation, and the count must be tested against zero on ever decrement. These operations can, if used often enough, create a performance penalty for your program.

These types of collectors are often called cooperative collectors because they require cooperation from the rest of the system to maintain the counts.

Tracing Collector

Tracing collectors are entirely dissimilar from reference counting collectors, and have opposite strengths and weaknesses.

When the Tracing GC allocates a new memory chunk, the GC does not create a counter, but it does create a flag to determine when the item has been marked, and a pointer to the object that the GC keeps. The flags are not manipulated by the program itself, but are only manipulated by the GC when it performs a run.

During a GC run, the program execution typically halts. This can cause intermittent pauses in the program, pauses which can be quite long if there are many memory objects to trace.

The GC selects a set of root objects which are available to the current program scope and parent scopes. Starting from these objects, the GC identifies all pointers within the objects, called children. The object itself is marked as being alive, and then the collector moves to each child and marks it in the same way. The memory objects form a sort of tree structure, and the GC traverses this tree using recursive or stack-based methods.

At the end of the GC run, when there are no more children to be marked, all unmarked objects are considered unreachable and therefore dead. All dead objects are collected.

A few points to remember about Tracing GCs:

1. Tracing GCs can be used to find cycles, memory objects whose pointers form circular structures. Reference Counting schemes cannot do this.
2. Tracing GCs cause pauses in the program, and these pauses can become unbearably long in some complex programs that use many small memory objects.
3. Dead objects are not reclaimed immediately. Reclamation only occurs after a GC run. This causes a certain inefficiency in memory usage.
4. Tracing collectors do not require the program to account explicitly for memory counts or memory status updates. All memory tracking logic is stored inside the GC itself. This makes it easier to write extensions for these systems, and also makes it easier to install a Tracing GC in an existing system then to install a Reference Counting one.

Tracing GCs are often called uncooperative collectors because they do not require cooperation from the rest of the system to function properly.

Hybrid Collectors

Sometimes, reference counting schemes will utilize Tracing systems to find cyclical garbage. Tracing systems may employ reference counts on very large objects to ensure they are reclaimed quickly. These are just two examples of hybridized garbage collectors that are more common then either of the two "pure" types described above.

In later chapters, we will discuss garbage collectors and their algorithms in more detail.

Implementations

In no particular order,

• TinyGC, a garbage collector for C
• Memory Pool System
• MeixnerGC - an incremental mark and sweep garbage collector for C++ using smart pointers

Illustrations

• 
  Example before garbage collection.
• 
  Example after garbage collection.

Stacks and Heaps

Memory Allocations

In most native executable programs, there are two types of memory available: stack-based and heap-based memory.

Stacks

A stack using frames

The system stack, for those systems that have them, are used most often to provide frames. A frame is a way to localize information about subroutines. In general, a subroutine must have in its frame the return address (where to jump back to when the subroutine completes), the function's input parameters. When a subroutine is called, all this information is pushed onto the stack in a specific order. When the function returns, all these values on the stack are popped back off, reclaimed to the system for later use with a different function call. In addition, subroutines can also use the stack as storage for local variables.

This whole process, the process of creating frames on the stack and reclaiming them happens mostly transparently, and is handled by the compiler. The programmer is typically not aware of this process, and doesn't need to specifically account for it.

One pitfall to worry about can occur when a local array is allocated on the stack. If the function writes to a memory location beyond the end of the array, a problem called a buffer overflow occurs. A buffer overflow is a problem because data values are stored tightly on the stack and in an overflow you can accidentally overwrite these values. As was mentioned before, the function's return value is stored on the stack. So if this value is overwritten, the function will not return to the correct location. A diligent hacker can use this fact to populate the stack with very specific values, such as the address of virus code in memory.

Stack storage is fixed. That is, the space allocated on the stack is set at compile time by the compiler and is not altered while the program executes.

Heap Storage

The heap is an area of dynamically-allocated memory that is managed automatically by the operating system or the memory manager library. Memory on the heap is allocated, deallocated, and resized regularly during program execution, and this can lead to a problem called fragmentation. Fragmentation occurs when memory objects are allocated with small spaces in between that are too small to hold additional memory objects. The net result is a percentage of the heap space that is not usable for further memory allocations.

Heaps are also susceptible to overflow situations, although the results are typically not as dire as in a stack overflow. It's not impossible for a hacker to disrupt the system through a heap overflow, but it's particularly difficult.

Pages and Superpages

Pages

The word "page" has many meanings in the world of computing. In terms of memory management, we will define the term like this:

Page

A Page is a region of memory dedicated to holding one type of object with a fixed size. This is also known as a homogenous memory region.

Since all the objects in the page are the same size, it can be treated like a gigantic array in memory and objects can be indexed easily and don't require any extra meta data to find objects.

Valid Pointer Detection

Key to performing a memory trace is finding pointers to managed memory objects. If pointers to the object are not found, an uncooperative garbage collector will mark the object as dead and will reclaim the space for later reallocation. Places such as the processor registers and the system call stack need to be examined to find all potential pointers to managed memory objects.

Pointer or Data

When looking at an arbitrary bit pattern, there is no way to determine whether the value is a pointer to a memory location or an integer value. However, most garbage collectors take the conservative approach and assume that all values that could be valid pointers are treated as valid pointers. If the memory management system is allocating memory in pages, it's a trivial task to determine whether a value could be a pointer to an object inside that page. Looping over all pages in this manner will determine whether a given binary value is a pointer to any managed memory objects.

Memory Compacting

Compacting

As a memory pool is allocated from, over time the pool will become fragmented. Some objects from the pool will be allocated surrounded by objects that are not, in seemingly random order. Memory compaction is the process of moving allocated objects together and leaving empty space together.

Consider a system with 3 pages and about 50% of their objects are allocated. By compacting, all the living objects are moved into the first two pages, leaving the second half of the second page and the third page completely empty. The empty page can then be ignored during future mark/sweep phases since it is known to be empty of living objects, or it can be released and returned to the desired operating system. Memory compacting is very important technique for allocating memory properly

Cooperative GC

Cooperative Collectors

Cooperative collectors are collectors that require the rest of the system to participate in the collector's operation, such as with reference counting. These collectors spread the bookkeeping effort throughout the system and don't require a separate mark or sweep phase. These separate GC phases often require the rest of the program to come to a complete stop temporarily, which can create intolerable pauses in program operation. Cooperative collectors don't have these pauses.

Resources

• David A Rusling. "The Linux Kernel": "Chapter 3: Memory Management".
• "Javascript: Memory Management".
• "Mac Developer Library": "Cocoa": "Advanced Memory Management Programming Guide".
• "Mac Developer Library": "Memory Management Programming Guide for Core Foundation"
• "Windows Desktop Applications: Memory Management".