In my recent articles, "Heap Magic: Process Heap Internals," part 1 and part 2, I described how you can add some padding and tag values to the beginning of your structures and objects so that they are easy to spot within the procefss heap. That technique is very useful when diagnosing problems where instances are prematurely freed, since you can potentially identify what type of object used to live in the memory block by peeking at its dead carcass. In this article, I'll show you how you can use a byproduct of the C++ compiler as another way to help you identify objects within the heap.
Polymorphism Makes Debugging Easy
First let me say, I'm not about to suggest that you create all your objects with virtual methods just for the sake of debugging. Rather, what I am demonstrating is that objects that happen to have virtual methods just so happen to have qualities that can make debugging easier. What is this special quality, you ask? You may have guessed that it is the vtable. The vtable is simply a list of function pointers in memory, but the compiler assigns a unique type to it, making it easy to identify within the debugger.
Every C++ object instantiated from a class that contains at least one virtual method, even if that method is a virtual destructor, contains at least one vtable pointer in the first pointer-sized slots of its memory footprint. You should only design classes with virtual methods if it makes good engineering sense. For example, a class that represents a character in a sentence is not a good candidate for virtual methods. That's because its memory footprint, which should simply be the size of a char type, will be much larger because every instance must also have a pointer to a vtable. You can imagine the bloat on x64 systems where pointer sizes are eight bytes! But it gets even worse, because if you have two instances next to each other in memory, by default three bytes will be wasted for the padding necessary to ensure that the vtable pointer for the next object in memory is aligned on a natural memory boundary for the processor. Ouch!
Let's look at the program in Figure 1, which we'll use for our debugging example. The first thing the code does is to create an STL list of Derived type and populate it with 100 instances. I also create an extra instance on the heap pointed to by the anInstance pointer. And since list<> uses the heap for its internal storage, we can rest assured that the instances within will live on the heap.
Build the code in Figure 1 and run it within the WinDbg debugger. WinDbg is included in the Debugging Tools for Windows, which you can easily download using the web installer for the Windows SDK 7.1. As I described in "Heap Magic: Process Heap Internals," make sure you are debugging a release build and that you set the environment variable _NO_DEBUG_HEAP=1or launch WinDbg with the -hd command-line option.
Note: When I built the sample code, I disabled RTTI to reduce the symbol noise, and I disabled incremental linking for reasons I'll explain shortly.
Searching Symbols in WinDbg
WinDbg makes it really easy to search symbols within modules by using the x command, which also accepts wildcards. For example, to see any type that has anything to do with Derived, execute the following command in WinDbg (note that I built the code into HeapMagic2.exe):
You will get a surprising amount of output showing all the list<> types generated by the compiler that contain instances of Derived. But you'll also see the following output, which is directly associated with the Derived type:
00000001`3fa42c90 HeapMagic2!Derived::Derived (class Derived *)
00000001`3fa41160 HeapMagic2!Derived::Derived (void)
00000001`3fa41190 HeapMagic2!Derived::DoSomething (void)
00000001`3fa626b0 HeapMagic2!Derived::`vftable' = <no type information>
Notice that you can see the method for DoSomething() and the compiler-generated default and copy constructors.
Note: You'll notice the copy constructor prototype in this output is not correct in the technical sense because there is no use of the reference operator (&). This is because WinDbg does not understand the concept of a C++ reference and displays it as a pointer instead.
But notice the curious type named HeapMagic2!Derived::`vftable'. This is the vtable type for Derived! If you want to look at the methods within the vtable, you can pass the vtable pointer to the dps command, as follows:
0:000> dps 00000001`3fa626b0 L1
00000001`3fa626b0 00000001`3fa41190 HeapMagic2!Derived::DoSomething
The L1 suffix to the command tells the debugger that I want to see only one pointer slot. I fed it this because I knew that the vtable only had one slot in it. It does no harm to omit the L1 argument since the debugger will just show you the default number of slots and attempt to resolve the symbols.
Note: If you build with incremental linking turned on, the previous table will contain a pointer to a cryptic-looking type name containing the acronym ILT, which stands for Incremental Linking Table. The pointer points to a thunk that contains a single jmp instruction to the actual code. This is how the linker implements incremental linking at the cost of an extra jmp instruction for every virtual method call.
You may have already surmised that the Base type's vtable symbol is named HeapMagic2!Base::`vftable'. In fact, you can find all the types that contain vtables by searching symbols for the string vftable, as follows:
I won't show the output here, which is quite long since there are some STL types that have vtables.
Finding Instances of Your Objects
Now that you know how to find the vtable types by searching symbols, you can then go to the next level and search for instances of your objects by searching for pointers to the vtables within the heap. Start by setting a breakpoint on the _getch() call within main() and execute up to that pointer. To demonstrate this, we must first identify the heaps within the process and which ones contain the instances we're interested in. !heap -s will show us all the heaps in the process, as shown in Figure 2.
The next logical question is, which one of these is the heap the C++ runtime uses? You can answer this pretty easily since the C++ runtime has a public symbol named _crtheap, which references the global variable holding a pointer to the heap that the runtime uses. You can dump this global using the dp command:
0:000> dp HeapMagic2!_crtheap L1
We can see that the heap used by the C++ runtime and the new operator is the last one in the summary list in Figure 2.
Let's now inspect the segments of the heap using the !heap -m command, as shown in Figure 3. (I've abbreviated the output to show just the segment data.) By taking the difference between the values for Last Entry and Base, I can see that the first segment is 0x10000 bytes and the second is 0x100000 bytes. I can now use the following two variants of the s command to search these memory ranges for the pointer to the Derived vtable (which is 00000001`3fa626b0 in the output shown earlier):
s -q 003c0000 L?10000/8 00000001`3fa626b0
s -q 000c0000 L?100000/8 00000001`3fa626b0
The syntax of this command is a little confusing at first glance. The -q option tells it that we are searching for quadwords, which is the size of a pointer on x64 platforms. The argument prefixed with L? tells it how big of a block to search through in multiples of the size of the object we are looking for. In this context, an object is a pointer eight bytes long, so I must divide the segment length by eight.
Note: To be more generic, I could have replaced 8 with @$ptrsize, the debugger pseudo register containing the pointer size of the current platform.
After executing the search commands above, you should find quite a few hits. Here is some of the output that I got:
0:000> s -q 003c0000 L?10000/8 00000001`3fa626b0
00000000`003c8200 00000001`3fa626b0 00000000`00000000
00000000`003c9010 00000001`3fa626b0 00000000`3fa4f890
00000000`003c9040 00000001`3fa626b0 00000000`3fa4f890
00000000`003c9070 00000001`3fa626b0 00000000`3fa4f890
Using the dt command with one of the pointers above, I can inspect one of these instances, where you can clearly see the vtable pointer occupying the first pointer slot within the object's memory (notice the seemingly random value in the field value, since I do not initialize it):
0:000> dt HeapMagic2!Derived 00000000`003c9040
+0x000 __VFN_table : 0x00000001`3fa626b0
+0x008 value : 0n1067776144
Multiple inheritance within C++ can actually give type two vtable pointers. For example, consider the modifications to the sample code shown in Figure 4. I've introduced a new type named Interface1, which contains one pure virtual function, and I modified Derived to implement this interface. Now, if you run the code within WinDbg, you can use the dt command to display the type information of Derived, as follows:
0:000> dt Derived
+0x000 __VFN_table : Ptr64
+0x008 __VFN_table : Ptr64
+0x010 value : Int4B
You can clearly see the two vtable pointers in the first two slots of the type's memory. If you step right past the point where the anInstance variable is initialized in main(), you can look at the memory where the Derived object lives, using the dps command, and you can see the types of the two vtables as well:
0:000> dps 0x00000000`00708200 L18/8
00000000`00708200 00000001`3fff26b8 HeapMagic2a!Derived::`vftable'
00000000`00708208 00000001`3fff26b0 HeapMagic2a!Derived::`vftable'
There are some important things to note here. How did I get the pointer to the object above? In an x64 debug build without compiler optimization turned on, you can use the debugger's dv command to show you the locals. If optimizations are turned on, this does not always work because various locals are optimized into registers. To learn more about the x64 calling convention, read my article "Challenges of Debugging Optimized x64 Code".
Also notice the types of the vtables are the same type. Taking the lower of the two vtable addresses and inspecting with dps shows the following:
0:000> dps 00000001`3fff26b0 L2
00000001`3fff26b0 00000001`3ffd11e0 HeapMagic2a!Derived::InterfaceMethod1
00000001`3fff26b8 00000001`3ffd11b0 HeapMagic2a!Derived::DoSomething
The table in memory starts with the method pointers for the Interface1 type, and that is followed by the pointers to the virtual methods from Base. The two vtable pointers in the Derived type simply point into two different points within this same table.
A Little Knowledge Goes a Long Way
Knowing a little bit about how the compiler generates C++ code can go a long way when debugging. Once you understand how vtables work and how the C++ compiler implements dynamic polymorphism, it becomes a lot easier to spelunk around the heap. Searching heap memory readily turns up dynamic C++ objects, including their type, allowing you to easily inspect them and troubleshoot hard-to-diagnose problems. I encourage you to take the sample code I've provided and play around with various modifications, then inspect the results within WinDbg. You may also want to see how various compiler and linker switches affect the results. Happy troubleshooting!
Trey Nash is a senior escalation engineer at Microsoft working on the Windows OSs and various other products and is the author of Accelerated C# 2010 (Apress). When not working feverishly within the bowels of the OS, he is delivering training on .NET platform and kernel-mode debugging or playing ice hockey.