ONLamp.com    
 Published on ONLamp.com (http://www.onlamp.com/)
 See this if you're having trouble printing code examples


Modern Memory Management, Part 2

by Howard Feldman
11/23/2005

My previous article discussed the layout of memory during program execution in modern computers. This article continues the discussion, looking at how programming languages store and access variables in memory. It also delves into swap memory, shared memory, and memory leaks.

Regardless of the programming language you use, you will use variables--a program would be quite inflexible without them. While called differently in different languages, all have some concept of global variables, available and accessible anywhere in the code, and local variables, which have a limited scope. Usually there is some concept of a define or constant as well, with a value that does not change and some sort of compile-time processing.

Constants

Constant symbols include things such as #define in C, Java literals, string constants such as string msg="hello";, and even numbers such as the 2 in x = x + 2. Note that the preprocessor reads #defines in C, which then goes through the code and replaces literally each instance of the defined symbol with its value--the compiler never sees them, and so for all intents and purposes, these are the same as typed constants.

While not variables, this important type of program data still must be stored somewhere. As demonstrated in the previous article, constant variables are stored in the code segment of memory, right along with the program instructions. As such, they should be considered read-only.

Local Variables

A local variable has a limited scope--it is automatically destroyed once that scope ends. Often, this will be the duration of one function. You can also think of arguments passed to a function as local to that function, except when passed by reference, because you're really passing only temporary copies of the variables. Local variables are the most commonly used variables, so it is important to understand their storage in memory. Due to their transient nature, they are stored on the stack. This is convenient, because it allows them to bypass the time-consuming overhead of using malloc and the heap to obtain their storage locations. When their scope ends, all the computer needs to do is to pop them off of the stack; this effectively destroys them. Even if several scopes are nested, local variables will be instantiated in a LIFO manner. The innermost scope will always end before outer ones, making a stack ideal for supplying this temporary storage.

Recall that return addresses for function calls are stored on the stack as well. Because all local variables (including function arguments) will be destroyed by popping them off the stack when the function terminates, the return address will then be at the top of the stack ready to be popped off. There is, however, one undesirable side effect of using the stack for variable storage--the stack is of limited size. As a result, large local variables can overflow the stack, bringing the program to an abrupt halt. Consider the following C program to sum 2,000,000 random numbers and print out the result:

#define BUFSZ 2000000

double GetSum(void)
{
    double num[BUFSZ];
    int i;
    double sum = 0.0;

    for (i = 0; i < BUFSZ; i++) {
            num[i] = random();
    }
    for (i = 0; i < BUFSZ; i++) {
            sum += num[i];
    }
    return sum;
}

int main(void)
{
    printf("%f\n", GetSum());
    return 0;       
}

When executed on a 64-bit Solaris machine with the stack size set with ulimit to 8MB, a segmentation fault occurs. Specifically:

signal SEGV (no mapping at the fault address) in GetSum at line 8:
    8           double sum=0.0;
dbx: read of 4 bytes at address fecbd5a0 failed -- Error 0

If you reduce the array size to 1,000,000, the program works fine. Because a double uses eight bytes, the smaller size does not exceed the 8MB stack size. Similarly, doubling the stack size would avoid the crash. Note how the error message seems to indicate a problem in the allocation of the sum variable, although it is not at all clear from the error what is really happening here. To avoid overflowing the stack like this, always allocate large local variables dynamically, using malloc, forcing their storage to come from the heap.

In the previous example, instead declare num as double *num; and then allocate it with num = (double *) malloc (BUFSZ* sizeof(double));. Then be sure to call free() when you finish with num. Alternatively, you could declare it static (in C) or global, so that it is not stored on the stack, and not destroyed when the function exits (see below).

Secure Programming Cookbook for C and C++

Related Reading

Secure Programming Cookbook for C and C++
Recipes for Cryptography, Authentication, Input Validation & More
By John Viega, Matt Messier

Globals

The last class of variables are global ones, which the program allocates once, when first referenced, and which retain their value and memory allocation until the program terminates. They may be accessible throughout the entire program, or only within some limited scope, such as a static variable in a C function. Either way, their method of storage is identical. Globals are allocated off of the heap, the same area of memory used by malloc for dynamic memory allocation. malloc is smart enough to keep track of the memory areas used by globals, so it will not try to give out that memory when a request comes in. Because global variables eat up memory and keep it throughout the entire program, avoid them except when absolutely necessary. For large objects that you don't need for the entire program, it is much better to allocate them dynamically, so that you can free them once you are done with them, so that you can reuse the memory for other purposes.

Swap

Swap memory, or virtual memory, is an effective method for extending memory capacity beyond the physical limits of the RAM chips installed in a machine. All modern operating systems can use swap memory, which uses a special file or partition on disk to act as an additional block of memory. Like normal RAM, swap memory blocks must be contiguous, so often operating systems reserve a special partition on the hard disk just for this purpose. Windows can use one or more swap files in the standard file system, but again, the storage used by each file must be completely unfragmented.

The user can specify the size of swap, usually about equal to the amount of RAM, but it is up to the operating system to decide when and how to actually make use of the swap memory. Most commonly, blocks will be swapped out to disk when they have not been accessed for a while, or when the OS thinks they may no longer be needed (for example, when a process becomes idle). It can swap them back in when necessary. Because disk memory is thousands of times slower than RAM, it is important that swapping in and out be kept to a minimum--it is no replacement for conventional RAM. To see the fraction of a process that is in virtual memory at any given time, use the top utility and subtract the RSS column from the SIZE column. top will also display the amount of swap in use, free RAM, and more.

Shared Memory

The previous article claimed that once a process allocates some memory, it hangs on to it until the process terminates, even if the memory is freed. As a result, memory usage of a process always goes up, never down, over time. One alternative, however, is to use shared memory. A good example of when you might use shared memory is if you had a large data table you wanted several processes to use, but only want to load up one copy in RAM. Using a shared memory space allows all of the processes to access it without storing multiple copies for each new process. Sometimes this may be the only feasible way to perform a task in RAM. Another possible use is for interprocess communication. One process may write data, such as status information, to the shared memory area, while another may read the data written and respond accordingly.

Shared memory is implemented at the operating system level through a handful of system calls, including shmget, shmop, and shmctl. The exact implementation may vary on different CPUs. For details, see the man pages for these commands on your system. For a simple alternative to these system calls, you can use files in /tmp for (slower) interprocess communication, or a RAMDisk. A RAMDisk is simply a block of memory reserved to act like a filesystem. You can read and write files from and to it like any other disk partition, but because it lies in RAM, it is thousands of times faster than conventional disk. The only drawbacks are that you'll lose all of its contents when the machine reboots, and the RAM used will be unavailable for other purposes of course.

Memory Leaks and Garbage Collection

Memory leaks are the bane of any C/C++ programmer and often result in much frustration. A memory leak occurs when memory is allocated with malloc (or similar) and not subsequently freed. There are three distinct types. A reachable memory leak refers to a block of allocated memory, with a pointer variable pointing to it, which is never freed when it is no longer needed. It could still be freed by simply adding a free command to the code once it is no longer needed and is simply wasting resources. An innocuous leak is a reachable one that is only allocated once and is required throughout the entire program, such as a database connection object. It is simply not explicitly freed before the program exits, though the OS will still free it. A true leak is a block of memory that has no pointer variables still pointing to it. It is permanently lost, and cannot be freed from within the program. This type is always a result of programmer error. Thankfully, all modern operating systems automatically clean up any true leaks from a process when it terminates. If they did not, like some early versions of MS-DOS, then you would eventually run out of memory after running leaky software, even with no processes running, and would need to reboot.

A common misconception is that memory leaks are only a concern when using C/C++. This is simply untrue. A language such as Java has built-in garbage collection, which may give programmers a false sense of security that they need not worry about leaking memory. However, garbage collection only works on true leaks, as defined above. That is, once a variable goes out of scope, any blocks of memory associated with it will be freed if no other variables are referencing that block. As long as some reference to it remains, however, the block is kept intact and is effectively a memory leak. Additionally, the garbage collector is normally only activated when the process is idle, or explicitly called by the programmer, and so if a leak happens to be occurring in a busy section of code, the collector may never run before memory exhaustion occurs.

Usually, the first sign of a memory leak is a steady increase in the memory usage of a program over time. This may only be noticeable when the program is run with a specific set of arguments--it may appear to be fine for some sets of inputs, and not for others. Some leaks are obvious, quickly using up all system memory and resulting in a core dump or out-of-memory error. Others are more subtle, and it can be difficult to tell if there is really a memory leak or if all the memory used is legitimate.

Luckily, several excellent programs exist to help detect and correct memory leaks and other memory problems. The best, easiest-to-use, freely available one is Valgrind. It is available only for x86-Linux, and can literally save hours or even days of debugging. Some of the problems it finds may never be found without it! A similar program available for a wider range of operating systems is Rational Purify. Purify is not free, but runs on most flavors of UNIX, as well as Windows, and can analyze code written in Java, C, C++, Visual Basic, C#, and VB.NET. Many other programs exist, as well, but these two probably work the best.

How do these programs work? They basically wrap all system calls that allocate memory, and internally keep track of every allocation and free operation. Why doesn't the standard system malloc do this? Because it is extremely slow--any program will run extremely slowly under Valgrind or Purify--a small price to pay for discovering all of the memory leaks in your code, however. When the program terminates, they basically match up all the calls to malloc and its neighbors with all of the calls to free, and construct a report listing all of the unfreed blocks of memory. They will distinguish between reachable leaks and true leaks, as well. For each leak, they will indicate the line of code that allocated the memory, sorted by size, so that you can address the largest leaks first. It is still up to the programmer to go and correct the mistakes, of course, and to decide which ones are worth fixing. Other types of detectable problems include:

Resource Leaks

A very little-known or -understood variation on the memory leak exists, too--the resource leak. A resource, or handle, is a pointer to some object used to refer to some operating system object or device. This can include file handles, pipes, network connection handles, database connection handles, window handles, and so on. These use up memory, like any other object, and all have corresponding close/free functions that must be called when done with the handle. Some, such as file handles, also have hard limits (set with ulimit in this case) of how many may be in use at any one time. Any attempt to create a new handle beyond this point will fail. If the code does not check for and deal with running out of file handles, unpredictable behavior will occur.

Because handles use up memory, it is possible to have a resource leak, which may manifest itself in a similar manner to a memory leak. Alternately, instead of running out of memory, new handle requests will simply start failing. Here is a trivial buggy program to check a status file on disk, presumably being written by another process:

#define BUFSZ 128

int main(void)
{
    FILE *f;
    char buf[BUFSZ];

    while (1) {
            if (f = fopen("status", "r")) {
                    if (fgets(buf, BUFSZ, f)) {
                            if (!strcmp(buf, "complete"))
                                    break;
                    }
            }
            else {
                    printf("unable to open status file\n");
                    break;
            }
    }
    return 0;
}

This quickly outputs unable to open status file and terminates. If it did not check the return value of fopen for NULL, the program would crash instead when it tried to fgets from a NULL pointer. Leaving out the fclose(f); statement after the fgets statement results in the program quickly using up all of the file handles in the system.

Resource leaks can be difficult to detect because they may exhibit unusual or unexpected behavior. For instance, in the above example, when fopen begins to fail, you might initially think it is some sort of file-locking issue. However, checking errno quickly reveals ENFILE--too many open files. Most languages provide some mechanism to determine why a certain system call fails, so make use of it when debugging to save time. When nothing else seems to make sense, ask if a resource leak could be to blame.

Summary

Memory is a precious resource and you should not waste it. Nevertheless, there are times when using large blocks of memory can be useful. A program that runs through a database doing calculations may run many times faster if you load the entire database into memory first before processing it, rather then processing it on disk or remotely through a connection, one row at a time. In the end, the programmer must decide how to best make use of the resources available on a given machine. Armed with this knowledge, you should be ready to face the trials and tribulations of memory management on anything from a palm computer to a multi-CPU behemoth. So long, and thanks for the memories!

Howard Feldman is a research scientist at the Chemical Computing Group in Montreal, Quebec.


Return to ONLamp.com.

Copyright © 2009 O'Reilly Media, Inc.