Debugging Memory Errors with Custom Allocators
Cristian Vlasceanu
Allocators may be weird, but it's a Good Weird. With a little help from your operating system, they can even find memory access errors.
“Allocators are weird.” — Scott Meyers [1]
Introduction
Illegal memory accesses are a common source of program bugs. An illegal memory access that stops the application immediately is not very difficult to debug; it’s merely a matter of examining the stack trace in the debugger. However, in everyday programming practice, some piece of code may overwrite memory that it does not own and cause a crash in a different module, in a completely unrelated execution path. When the cause and effect are separated by both time and space, memory corruption bugs are hard to find and fix.
The technique described in this article helps reduce this separation by bringing the cause and effect of the illegal memory accesses [2] closer together. When the program crashes as soon as there is an incorrect memory access, debugging the problem becomes trivial. This idea is inspired by techniques used by a debugging tool called Electric Fence, <ftp://ftp.perens.com/pub/ElectricFence/>.
With a little support from the operating system, one can write a memory allocator that can be used with STL containers and that provides methods for setting access rights for the memory it manages. Such an allocator allows the memory owner to make the memory read-only (or not accessible) to the outside world.
The Scenario
Imagine the following scenario. You have a class that has been debugged, tested, and working fine in production for the last couple of months. Then, a new feature is added to the project, and your class starts breaking in a very inconsistent and hard-to-reproduce way. You know that it’s not your bug, but it’s your problem. The stack traces from the crash all go back to your code, your class has corrupt data, and the testing department has assigned the bug to you.
The Strategy
What can the victim class do to protect itself? Imagine a class that could declare all of its memory as read-only to the rest of the world — anyone trying to write to it would be caught instantly.
One strategy for bringing the bug into the spotlight is to make the block of memory that the bug corrupts read-only. This will cause the program to receive a notification [3] as soon as an illegal access to the memory is attempted. This event can be caught in the debugger, and the source of the problem can be found by examining the stack. Listing 1 shows the skeleton of a class to which has been added an extra method for controlling the access rights to the memory it owns.
Victim’s constructor can “lock” the memory as soon as the initialization is completed:
Victim::Victim() // : initializer list { // some more initializations... // ... setMemoryAccessMode(readOnly); }
Then, all member functions that modify the internal data (all non-const methods) have to be slightly rewritten:
void Victim::setSomeData(/* ... */) { setMemoryAccessMode(readWrite); // modify the internal data // ... setMemoryAccessMode(readOnly); }
This way, the class’ implementer makes sure that no other code writes to the memory owned by the class instances. Any attempt to tamper with the memory will result in an immediate crash, and finding the culprit becomes just a matter of examining the call stack in your favorite debugger.
In the example above, the “useful” code is sandwiched between setMemoryAccessMode calls. There is a slightly better way to ensure that no early return from the function leaves the memory in a read-write mode. You can use a helper class to implement the “resource acquisition is initialization” idiom [4]:
template<class T> class ReadWriteMemoryScope { public: explicit ReadWriteMemoryScope(T& ref) : ref_(ref) { ref_.setMemoryAccess(readWrite); } // automatically restore read-only mode when destructed ~ReadWriteMemoryScope() { ref_.setMemoryAccess(readOnly); } private: T& ref_; };
The template class works with any class implementing setMemoryAccessMode, and now the example setter method can be rewritten as follows:
void Victim::setSomeData(/* ... */) { ReadWriteMemoryScope<Victim>(*this); // modify the internal data don’t worry about restoring // the read-only mode, it’s all automatic }
Contiguous vs. Non-Contiguous Memory
The strategy that I have presented is not difficult to implement when the data members are placed in memory in a contiguous fashion. Assume that this class has a C-style array and an STL vector as its internal data members. Also assume that the operating system provides a C-style function named protect_memory with the following prototype:
int protect_memory(const void* address, size_t size, int mode_flags);
where address is a pointer to the beginning of the memory area for which the access mode is to be applied, size is the size of the memory area in bytes, and mode_flags is a bit-mask of flags that specifies the new access modes. Bear in mind, though, that this is just an imaginary function to help describe the mechanism in a platform-independent way [5].
The Victim class now looks like the code shown in Listing 2. For the class in Listing 2, the definition of the setMemoryAccessMode method may look something like Listing 3. Both the C-style array and the vector in Listing 3 place their elements in memory contiguously.
But what happens when your memory layout is not contiguous? What if your code uses, say, an STL map? A map is an associative container. It is usually implemented as a red-black binary tree [6] (a non-contiguous data structure). The nodes of the tree are not placed in memory in a contiguous manner (although some implementations may strive for grouping them as close as possible [7]).
If you run the code in Listing 4 and look at the stack trace when it crashes, you will see that appears to be the problem is in the printElem call. In this simple example, it is obvious that printElem is not the culprit (hopefully not just because I named the other function offender).
In real life situations, it is much harder to prove the innocence of a function such as printElem and bring the real offender to justice. You can try using the strategy that I proposed earlier: make all the memory owned by the map in Listing 4 read-only after initializing it. You’ll soon find that it is hard, if not impossible, to do. You don’t know (and shouldn’t care about) how the STL vendor has implemented the map. You don’t know where the memory blocks are allocated. Do they store just your data, or some other internal information?
In the earlier example shown in Listings 2 and 3, vector was much easier to deal with, since you can safely assume the elements are contiguous.
This brings me to the following point. For STL containers other than vector, you need a custom allocator to keep track of (and make read-only) the memory.
Fortunately, STL containers can be parameterized by how they obtain the raw memory they need. STL containers accept an allocator class in their list of template arguments. An allocator is an abstraction that basically encapsulates the methods for dynamically obtaining and releasing memory. You can write a custom allocator that keeps track of the memory blocks its “client” STL container uses and that provides the means for making all these blocks read-only with just one call.
Implementation
In order to make a block of dynamically allocated memory read-only, you will use the VirtualProtect function on Windows and mprotect on Unix. Both have signatures that resemble the protect_memory pseudo-system call that I used earlier. Please consult MSDN or your manual pages for more details.
The memory allocation mechanisms are implemented by the stand-alone functions allocate and deallocate. While the first has a signature that reminds us of the standard malloc, the latter differs from free by taking the size of the memory to be deallocated in addition to the memory address.
If you wonder why you have to write your own functions, the answer is simple. This implementation makes sure that the dynamically allocated memory satisfies the requirements imposed by the system-specific incarnation of protect_memory.
On Windows, the VirtualAlloc and VirtualFree API calls are used for allocation, since, according to the documentation, VirtualProtect requires that all pages in the region to be locked must be within the same region allocated by calling VirtualAlloc or VirtualAllocEx, using MEM_RESERVE.
On Linux, mprotect, which you will use to modify the memory access mode, requires the memory to be page-aligned. In this case, allocate calls pvalloc, which allocates memory aligned to a page boundary.
Another Unix-specific way to allocate memory (not shown here but available for download in the companion code at <www.cuj.com/code>) is via mmap system calls. In the companion code, this implementation can be turned on by defining the USE_MMAP preprocessor macro. The stripped-down implementation looks essentially like Listing 5.
The allocator also needs a memory manager class that keeps track of the allocated blocks so that you can change their access mode in the application code. The implementation of the memory manager class does not need to be exposed to the clients. You should be able to change it without affecting the clients of our debug allocator. You should also be able to switch between different implementations depending on the application’s threading model.
For these reasons, the public interface of the memory manager is presented in allocator.h as an abstract class, but the actual implementation is buried in allocator.cpp. (Both files available at <www.cuj.com/code>.)
The memory manager class sports functionality for registering and unregistering memory blocks (insert and erase). The allocator registers the allocated chunks with the memory manager after calling allocate and deregisters them after calling deallocate. This way, the memory manager knows the addresses and lengths of the currently allocated memory blocks. Its setAccessMethod can be invoked for modifying the access rights for all the blocks that have been registered (see Listing 6).
The allocator class uses allocate and deallocate to implement the homonym methods, as shown in Listing 7. References [1] and [6] are good places to start if you want to understand all the scaffolding code needed to implement a custom allocator.
Usage Example
You can now rewrite the code in Listing 4 with just a few lines and find the culprit for the memory corruption. You change the type definition from:
typedef map<int, string> MapType;
to:
typedef map<int, string, less<int>, Allocator<pair<const int, string> > > MapType;
In the main function, you will embed the code that uses the map in a read-only scope (see allocator.h available at <www.cuj.com/code> for the read-only scope class definition):
// ... // initialize map elements // ... { BaseAllocator::MemReadOnlyScope readOnlyScope; offender(m.find(1)->second.getAddr()); printElem(m, 1); }
Now if you recompile, run, and inspect the stack when the code crashes, you can clearly see the problem.
This is the output from running the program under the GNU debugger:
(gdb) run Starting program: /home/cristiv/Projects/DebugAllocator/g++-Linux/test_allocator allocated 24 bytes at 0x8051000 allocated 24 bytes at 0x8055000 allocated 24 bytes at 0x8053000 Program received signal SIGSEGV, Segmentation fault. 0x40116b95 in memcpy () from /lib/i686/libc.so.6 (gdb) backtrace #0 0x40116b95 in memcpy () from /lib/i686/libc.so.6 #1 0x0804aec1 in offender (ptr=0x8055014) at ../Source/main.cpp:28 #2 0x0804b0b6 in main () at ../Source/main.cpp:69 #3 0x400ab177 in __libc_start_main (main=0x804af7c <main>, argc=1, ubp_av=0xbffff9fc, init=0x8049f74 <_init>, fini=0x804e40c <_fini>, rtld_fini=0x4000e184 <_dl_fini>, stack_end=0xbffff9ec) at ../sysdeps/generic/libc-start.c:129 (gdb)
Caveats
First, the allocator presented in allocator.cpp (see the companion code) locks/unlocks the memory globally and not on a per-class basis. This design decision was based on the fact that I wanted to keep the implementation simple. The companion code (available at <www.cuj.com/code>) includes support for multithreaded applications (for Linux pthreads and Windows).
Second, you must be aware that the custom allocator may change the behavior of the bug that you are trying to unveil. On Unix platforms, for example, the mprotect call works only if the memory is page-aligned. To allocate memory aligned to a page boundary, you can use (as shown in the companion code) either the mmap or pvalloc system calls. A side effect may be that the memory-corrupting bug magically disappears or manifests itself in a different way.
Conclusion
Custom allocators can be used for debugging memory corruption problems by controlling memory access rights.
The companion code for this article contains a proposed implementation that has been developed on Windows 2000 and Linux, using Visual C++ 6.0, CodeWarrior 6.0, and g++ versions 2.95.2 and 3.0.1.
Acknowledgements
Thanks to Andrei Alexandrescu, Bob Archer, Ionut Burete, Chris Dyer, and Mark Riggins for taking the time to review this article, and for all of their suggestions and constructive criticism.
Notes and References
[1] Scott Meyers. Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library (Addison-Wesley, 2001), Item 10, page 48.
[2] When a program writes past the end of a buffer, it is called a memory overrun. When it tries to write before the beginning of a buffer (for example through an index that incorrectly assumes negative values), it is called a memory under run.
[3] On POSIX-compliant systems, the notification comes as a “segmentation fault” signal. Under Windows, it will take the shape of an “Access Violation.”
[4] “Bjarne Stroustrup’s C++ Glossary,” <www.research.att.com/~bs/glossary.html>.
[5] In order to be able to implement the setMemoryAccessMode method, there is some support needed from the operation system. The good news is such support exists (see the section, “Implementation”). Win32 has VirtualProtect and VirtualProtectEx. Unix has mprotect. I will explain later how these system APIs are used to implement memory allocation.
[6] Nicolai M. Josuttis. The C++ Standard Library: A Tutorial and Reference, (Addison-Wesley, 1999).
[7] Scott Meyers. Effective STL 50: Specific Ways to Improve Your Use of the Standard Template Library (Addison-Wesley, 2001) Item 23, page 103.
[8] For Unix systems, please consult your manual pages for the mprotect system call.
Cristian Vlasceanu graduated from the “Politehnica” University of Bucharest in 1994. He is a software engineer with Amazon.com in Seattle, where he uses C++ for modeling and coding business logic. Previously, he worked for RealNetworks, where he developed code for interfacing portable players such as the Nomad Jukebox with RealNetworks software. His interests include network programming, generic algorithms, and classical guitar. He can be reached at [email protected].
