ALINK="#FF0000">
LINUX GAZETTE
[ Prev ][ Table of Contents ][ Front Page ][ Talkback ][ FAQ ][ Next ]

"Linux Gazette...making Linux just a little more fun!"

Is Your Memory Not What It Used To Be?

By Madhu M Kurup

Intent

The intent of this article is to provide an understanding of memory leak detection and profiling tools currently available. It also aims at providing you with enough information to be able to make a choice between the different tools for your needs.

Leaks and Corruption

We are talking software here, not plumbing. And yes, any fairly large, non trivial program is bound to have a problem with memory and or leaks.

Where do problems occur?

First, leaks and such memory problems do not occur in some languages. These languages believe that memory management is so important that it should never be handled by the users of that language. It is better handled by the language designers. Examples of such languages are Perl, Java  and so on.
    However, in some other languages (notably C and C++) the language designers have felt that memory management is so important that it can only be taken care of by the users of the language. A leak is said to occur when you dynamically allocate memory and then forget to return it. In addition to leaks, other memory problems such as buffer overflows, dangling pointers  also occur when programmers manage memory themselves. These problems are caused where there is a  mismatch between what the program (and by extension the programmer) believes the state of memory is, as opposed to what it really is.

What are the problems?

In order for programs to be able to deal with data whose size is not known at compile time, the program may need to request memory from the runtime environment (operating system). However, having obtained a chunk of memory, it may be possible that the program does not return to back to the environment after use. An even more severe condition results when the address of the block that was obtained is lost, which means that it is no longer possible to identify that allocated memory.  Other problems include trying to access memory after it has been returned (dangling pointers). Another common problem is trying to access more memory that was originally requested and so on (buffer overflow).

Why should these problems bother me?

Leaks may not be a problem for short-lived programs that finish their work quickly. Unfortunately, many programs are designed to function without termination for a long period. A good example would be the Apache webserver that is currently providing you this web page. In such a situation, a malfunctioning leaky program could keep requesting memory from the system and not return it. Eventually this would lead to the system running out of memory and all programs running on that machine to suffer. This is obviously not a  good thing. In addition to a program requiring more memory, leaks can also make a program sluggish. The speed at which the program is context-switched in and out can decrease if the memory load increases. While not as severe as causing the machine to crash, an excessive memory load on a machine could cause it to thrash, swapping data back and forth.
    Dangling pointers can result in subtle corruption and bugs that are extremely unusual, obscure and hard to solve. Buffer overflows are probably the most dangerous of the three forms of memory problems. They lead to most of the security exploits that you read about[SEC].  In addition to the problems described above, it may be possible that the same memory chunk is returned back to the system multiple times. This obviously indicates a programming error. A programmer may wish to see how the memory requests are made by a program over the course of the lifetime of the program in order to find and fix bugs.

Combating these problems

There are some run time mechanisms to combat memory problems. Leaks can be solved by periodically stopping and restarting the offending program [OOM]. Dangling pointers can be made repeatable by zeroing out all memory returned back to the operating systems. Buffer overflows have a variety of solutions, some of which are described in more detail here.
    Typically, the overhead of combating these problems at runtime or late in development cycle is so high that finding them and fixing them at the program level is often the more optimal solution.

Open Source

GCC-based alternatives

The gcc toolset now includes a garbage collector which facilitates the easy detection and elimination of many memory problems. Note that while this can be used to detect leaks, the primary reason for creating this was to implement a good garbage collector[GC]. This work is currently being led by Hans-J. Boehm at HP. 

Technology

The technology used here is Boehm-Demers-Weiser technique for keeping track of allocated memory. Allocation of memory is done using the algorithm's version of the standard memory allocation functions. The program is then compiled with these functions and when executed, the algorithm can analyze the behavior of the program. This algorithm is fairly well known and well understood. It should not cause any problems and/or interfere with programs. It can be made thread safe and can even scale onto a multiprocessor system.

Performance

Good performance with reduction in speed in line with expectations. The code is extremely portable and is also available directly with gcc. The version shipped with gcc is slightly older, but can be upgraded.
    There is no interface - it is difficult to use and requires much effort for it to be useful. Existing systems may not have this compiler configuration and may require some additional work to get it going. In addition, in order for the calls to be trapped, all memory calls (such as malloc() and free() ) have to be replaced with equivalents provided by the garbage collector. One could use a macro, but that is still not very flexible.  Also this approach implicitly requires source code for all pieces that require memory profiling with the ability to shift from the real functions to those provided.

Verdict

If you need a solution across multiple platforms (architectures, operating systems) where you have control over all relevant source, this could be it.

Memprof

Memprof is an attractive easy to use package, created by Owen Talyor of Red Hat. This tool is a nice clean GNOME front-end to the Boehm-Demers-Weiser garbage collector.

Technology

At the heart of the profiling, memprof is no different from the toolset described above. However, how it implements this functionality is to trap all memory requests from the program and redirect it at runtime to the garbage collector. While not as functional as the gcc alternative on threads and multiprocessors, the program can be asked to follow forks as they happen.

Performance

The performance of this tool is pretty good. The GUI was well designed, responsive and informative. This tools works directly with executables, and it works without any changes needed to the source. This tool also graphically displays the memory profile as the program executes which helps in understanding memory requirements of the program during its lifetime.
    This tool is currently available only for the x86 and PPC architecture on Linux. If you need help on other platforms, you will need to look elsewhere. This tool is not a GTK application, it needs the full-blown GNOME environment. This may not be feasible everywhere. Finally, development on this tool appears to be static (version 0.4.1. for a while). While it is possible that it does what it is required to do well, it does not seem that this too will do anything more than just leak detection.

Verdict

If you like GUI tools and don't mind GNOME and Linux, this is a tool for you.

Valgrind

Valgrind is a program that attempts to solve a whole slew of memory problems, leaks being just one of them. This tool is the product of Julian Seward (of bzip2 and cacheprof fame). It terms itself "an open source memory debugger for x86 linux" and it certainly fits that bill. In addition, it can profile the usage of the CPU cache, something that is fairly unusual.

Technology

The technology used in this program is fairly complex and well documented. Each byte of memory allocated by the program is tracked by nine status bits, which are then used for housekeeping purposes to identify what is going on. At the cost of tremendously increasing the memory load of an executing program, this tool enables a much greater set of checks. As all the reads and writes are intercepted, cache profiling of the CPU's various L caches can also be done.

Performance

The tool was the slowest of the three detailed here, for obvious reasons. However, for the reduction in speed, this tool provides a wealth of information is probably the most detailed of the three. In addition to the usual suspects, this tool can identify a variety of other memory and even some POSIX pthread issues. Cache information is probably overkill for most applications, but it is an interesting way to look at the performance of an application. The biggest plus for Valgrind is that it is under rapid development with a pro-active developer and an active community. In fact the web page of Valgrind proclaims the following from the author -  "If you have problems with Valgrind, don't suffer in silence. Mail me.".
    The tool however, is very x86 specific. Portability is fairly limited and to x86 Linux. The interface is purely command-line driven and while usable, sometimes the tool gives you too much information for it to be useful. This tool also directly works with binaries, so while recompiles are not required, it will require diligence to go through the output of this tool to find what you are looking for. You can suppress memory profiling for various system libraries by creating suppression files, but writing these files is not easy. In addition, threading support is not complete, although this tool has been used on Mozilla, OpenOffice and such other large threaded programs. If this tool had a GUI front end, it would win hands down.

Verdict

If you are on x86 and know your code well and do not mind a CLI interface, this program will take you another level.

Other Open Source tools

Before I get sent to the stake for not having mentioned your favorite memory tool, I must confess that few compare in completeness to these three in terms of the data that they provide. A more  comprehensive list of leak detection tools is available here.

Commercial

These tools are mentioned here only for completeness.

Purify

The big daddy of memory tools, does not work on Linux, so you can stop asking that question.

Geodesic

A latecomer to this arena, Geodesic is known most in the Linux community for their Mozilla demo, in which they use their tools to help find memory problems in the Mozilla codebase. How much use this has been to the Mozilla team is yet to be quantified, but their open-source friendliness can't hurt. Works for Solaris/Linux with a fully functional trial. Works on Windows as well.

Insure++

A C++ specific tool, but still fairly well known, Parasoft's Insure++ is a fairly complete memory profiling / leak detection tool. In addition, it can find some C++ specific errors as well, so that can't hurt. This tool works with a variety of compilers and operating systems, a free trial version is available too.

Miscellaneous Notes:

Secure Programming

Secure programming involves many components, but probably the most significant is the careful use of memory. More details are available here.

OOM killer

Some the newer Linux kernels employ an algorithm which is known as the Out Of Memory (OOM) killer. This code is invoked when the kernel completely runs out of memory, at which point active programs / processes are chosen to be executed (as in killed, end_of_the_road, happy hunting grounds, etc). More details are available here.

Garbage Collectors

One of the other reasons why garbage collection is not always a preferred solution is that it is really tough to implement. They have severe problems with self-referential structures (i.e. structures that link to themselves) as aptly described here.

Madhu M Kurup

I'm a CS engineer from Bangalore, India and formerly of the ILUG Bangalore. I've been working and playing with Linux for a while and while programming is my first love, Linux comes a close second. I work at the Data Mining group at Yahoo! Inc and work on algorithms, scalability and APIs there. I moonlight on the Linux messenger client and dabble in various software projects when (if ever) I can find any free time.

And yes, if you want to know, I use C++, vi, mutt, Windowmaker and Mandrake; let the flame wars begin :)

Copyright © 2002, Madhu M Kurup.
Copying license http://www.linuxgazette.net/copying.html
Published in Issue 81 of Linux Gazette, August 2002

[ Prev ][ Table of Contents ][ Front Page ][ Talkback ][ FAQ ][ Next ]