Traversing the gc heap (and introducing PSSCOR.DLL)

Article
04/05/2004

We have an improved SOS.DLL with many bug fixes and enhancements. Tom Christian in Product Support maintains it, and gave me permission to post it here under the name PSSCOR.DLL.

[update June 2005 - For some time now, PSSCOR.DLL has been included with the Windows Debugger package, although it is renamed to SOS.DLL. I've removed this old link because you get it just by installing the debugger].

It works on V1.0 and V1.1 of the CLR. Load it in the same way you'd load sos.dll in the Windows Debugger, with “ .load psscor.dll“. The good thing about PSSCOR.DLL is that we can fix bugs and enhance functions without going through a lengthy QFE process. If you've found bugs in SOS, it's likely that many were fixed already in PSSCOR.DLL.

The code examples below use psscor.dll to explore the gc heap. You'll want to use it in lieu of SOS, because some commands like !DumpMT and !EEHeap have additional useful output.

It's useful to know how objects are laid out in the gc heap. During garbage collection, valid objects are marked by recursively visiting objects starting from roots on stacks and in handles. But it's also important that the location of the objects sit in an organized way from the beginning to end of each heap segment. The psscor !DumpHeap command counts on this logical organization to walk the heap properly, and if it reports an error you can bet something is wrong with your heap (and will bite you later with a perplexing application violation). So to understand what !dumpheap is talking about, here is your guide to walking these objects by hand, hopping from one stone to another across a vast lake.

First you need a program. I have taken this program from Joel Pobar's Reflection Emit example, and inserted a PInvoke to DebugBreak so you can easily stop in the Windows Debugger. (You could use Visual Studio for these illustrations too, but the Windows Debugger "dd" command is quicker for viewing memory).

using System;
using System.Reflection;
using System.Reflection.Emit;
using System.Threading;
using System.Runtime.InteropServices;

public class EmitHelloWorld
{

[DllImport("kernel32")]
public static extern void DebugBreak();

      static void Main(string[] args)
      {
            // create a dynamic assembly and module
            AssemblyName assemblyName = new AssemblyName();
            assemblyName.Name = "HelloWorld";
            AssemblyBuilder assemblyBuilder = Thread.GetDomain().DefineDynamicAssembly(assemblyName, AssemblyBuilderAccess.RunAndSave);
            ModuleBuilder module;
            module = assemblyBuilder.DefineDynamicModule("HelloWorld.exe");

       // create a new type to hold our Main method
            TypeBuilder typeBuilder = module.DefineType("HelloWorldType", TypeAttributes.Public | TypeAttributes.Class);

            // create the Main(string[] args) method
            MethodBuilder methodbuilder = typeBuilder.DefineMethod("Main", MethodAttributes.HideBySig | MethodAttributes.Static | MethodAttributes.Public, typeof(void), new Type[] { typeof(string[]) });

            // generate the IL for the Main method
            ILGenerator ilGenerator = methodbuilder.GetILGenerator();
            ilGenerator.EmitWriteLine("hello, world");
            ilGenerator.Emit(OpCodes.Ret);

// bake it
Type helloWorldType = typeBuilder.CreateType();

// run it
helloWorldType.GetMethod("Main").Invoke(null, new string[] {null});

DebugBreak();

            // set the entry point for the application and save it
            assemblyBuilder.SetEntryPoint(methodbuilder, PEFileKinds.ConsoleApplication);
            assemblyBuilder.Save("HelloWorld.exe");
      }
}

Save the program as example.cs, compile and run "cdb -g example.exe"

When you reach the breakpoint, load psscor and run "!eeheap -gc". It lists the heap segments that objects are stored in:

0:000> !eeheap -gc
Number of GC Heaps: 1
generation 0 starts at 0x00aa1b78
generation 1 starts at 0x00a5100c
generation 2 starts at 0x00a51000
ephemeral segment allocation context: none
segment begin allocated size
00a50000 00a51000 00ae4000 0x00093000(602112)
Large object heap starts at 0x01a51000
segment begin allocated size
01a50000 01a51000 01a54060 0x00003060(12384)
Total Size 0x96060(614496)
------------------------------
GC Heap Size 0x96060(614496)

This is a small gc heap, with only one normal object segment, and one large object segment (for objects over 80K). It's fine for our purposes. Normal-sized objects start at address 00a51000, and end at 00ae4000. In general we have this simple pattern:

|---------| segment.begin = 00a51000
|object 1 |
|_________|
|object 2 |
|_________|
| ... |
|_________|
|object N |
|_________| segment.allocated = 00ae4000

How large is each object? You can run !dumpobj to find out. The interesting thing is that each object has a 4 byte header, and the size of the header for object 2 is included in the size of object 1. Another point is that a special kind of object called a "Free" object lives in the heap. This is used to plug holes between valid objects. These Free objects are temporary, in that if a compacting gc occurs they'll disappear. Yun wrote a great article about how the heap could be unable to compact in the face of heavy pinning , and be filled with Free objects (https://blogs.msdn.com/yunjin/archive/2004/01/27/63642.aspx).

Let's start walking. (My heap may look different because it's a Whidbey debug build)

0:000> !dumpobj 00a51000
Free Object
Size 12(0xc) bytes
0:000> !dumpobj 00a51000+c
Free Object
Size 12(0xc) bytes
0:000> !dumpobj 00a51000+c+c
Free Object
Size 12(0xc) bytes
0:000> !dumpobj 00a51000+c+c+c
Name: System.OutOfMemoryException
MethodTable: 03077e9c
EEClass: 03064050
Size: 68(0x44) bytes
(C:\WINDOWS\Microsoft.NET\Framework\v2.0.x86dbg\mscorlib.dll)
Fields:
MT Field Offset Type Attr Value Name
03076b7c 40000a5 4 CLASS instance 00000000 _className
03076b7c 40000a6 8 CLASS instance 00000000 _exceptionMe
thod
03076b7c 40000a7 c CLASS instance 00000000 _exceptionMe
thodString
03076b7c 40000a8 10 CLASS instance 00000000 _message
03076b7c 40000a9 14 CLASS instance 00000000 _data
03076b7c 40000aa 18 CLASS instance 00000000 _innerExcept
ion
03076b7c 40000ab 1c CLASS instance 00000000 _helpURL
03076b7c 40000ac 20 CLASS instance 00000000 _stackTrace
03076b7c 40000ad 24 CLASS instance 00000000 _stackTraceS
tring
03076b7c 40000ae 28 CLASS instance 00000000 _remoteStack
TraceString
03076b7c 40000af 30 System.Int32 instance 0 _remoteStack
Index
03076b7c 40000b0 34 System.Int32 instance -2147024882 _HResult
03076b7c 40000b1 2c CLASS instance 00000000 _source
03076b7c 40000b2 38 System.IntPtr instance 0 _xptrs
03076b7c 40000b3 3c System.Int32 instance -532459699 _xcode

Wow, it took some time to get to something interesting. You could continue like this until you get a buffer overflow due to all the "+c+44+68+12+..." You can also let !DumpHeap do this for you. It gives a rather sparse printout of the object pointers. Let's limit the output to the segment we care about (and note that Size is in decimal):

0:000> !dumpheap 00a51000 00ae4000
Address MT Size
00a51000 0015c260 12 Free
00a5100c 0015c260 12 Free
00a51018 0015c260 12 Free
00a51024 03077e9c 68
00a51068 030782cc 68
00a510ac 030786fc 68
00a510f0 03078b5c 68
00a51134 030f7b54 20
00a51148 0308b06c 108
00a511b4 030fa5bc 32
00a511d4 0305bbf8 28
00a511f0 030592e0 80
00a51240 0015c260 72 Free
...

How do we know the size of each object? Just look at the MethodTable, the first DWORD of the object. You can run !dumpmt on it:

0:000> !dumpmt 03077e9c
EEClass: 03064050
Module: 0016b118
Name: System.OutOfMemoryException
mdToken: 02000038 (C:\WINDOWS\Microsoft.NET\Framework\v2.0.x86dbg\mscorlib.dll)
BaseSize: 44
Number of IFaces in IFaceMap: 2
Slots in VTable: 21

BaseSize is in hex here. (We have a hard time deciding how we like to see these things!) How about arrays, how do we know their size? Let's list all the arrays in the segment to figure it out:

0:000> !dumpheap -type [] 00a51000 00ae4000
Address MT Size
00a511f0 030592e0 80
00a5129c 03115b68 56
00a51348 03135ca0 76
00a513a8 030592e0 16
00a51434 0313b1c0 144
00a51634 0313c234 100
00a51698 0313c620 56
00a51cc4 030592e0 16
00a51e8c 0313b1c0 144
00a52008 0313b1c0 144
00a52244 0313b1c0 144
00a52308 0313b1c0 144
00a523cc 0313b1c0 144
00a52620 0313b1c0 144
00a526e4 0313b1c0 144
00a52a14 031e23f8 36
00a52b7c 0313b1c0 144
00a52c0c 0315778c 1084
00a53048 0315778c 1628
00a536a4 0315778c 824
...

Picking one at random:

0:000> !dumpobj 00a52c0c
Name: System.Int32[]
MethodTable: 0315778c
EEClass: 03157708
Size: 1084(0x43c) bytes
Array: Rank 1, Type Int32
Element Type: System.Int32
Fields:
None

The formula for determining array size is:

MethodTable.BaseSize + (MethodTable.ComponentSize * Object.Components)

!dumpmt will tell you the first two:

0:000> !dumpmt 315778c
EEClass: 03157708
Module: 0016b118
Name: System.Int32[]
mdToken: 02000000 (C:\WINDOWS\Microsoft.NET\Framework\v2.0.x86dbg\mscorlib.dll)
BaseSize: 0xc
ComponentSize: 0x4
Number of IFaces in IFaceMap: 4
Slots in VTable: 25

and you can find the number of items in the array with:

0:000> dd 00a52c0c+4 l1
00a52c10 0000010C
0:000>

[I'm sure Josh Williams will come along and chide me for forgetting that on 64-bit pointers are 8 bytes, so I'd have to add 8 instead of 4 above. :p]. 0xc + (0x10C*0x4) = 0x43c, so our size is correct.

So we understand object sizes, and how they are arranged. There is one thing missing though, and this is the presence of zero-filled regions throughout the heap called Allocation Contexts. For efficiency, each managed thread can be given such a region to direct new allocations to. This allows multithreaded apps to allocate without expensive locking operations. There is also an Allocation Context for the heap segment that contains generations 0 and 1 (also called the Ephemeral Segment). The !dumpheap command is aware of these regions, and steps lightly over them. You can get the thread Allocation Context addresses with the !threads command:

0:000> !threads
ThreadCount: 2
UnstartedThread: 0
BackgroundThread: 1
PendingThread: 0
DeadThread: 0
PreEmptive GC Alloc Lock
ID OSID ThreadOBJ State GC Context Domain Count APT Exception
0 1 16ac 00155da8 a020 Enabled 00ae2e1c:00ae3ff4 0014a890 0 MTA
2 2 169c 001648f8 b220 Enabled 00000000:00000000 0014a890 0 MTA (Finalizer)

Thread 0 (the main thread) has an allocation context, from 00ae2e1c to 00ae3ff4. If we look at that memory, we'll see all zeros:

0:000> dd 00ae2e1c
00ae2e1c 00000000 00000000 00000000 00000000
00ae2e2c 00000000 00000000 00000000 00000000
00ae2e3c 00000000 00000000 00000000 00000000
00ae2e4c ...

As for the Ephemeral Segment Allocation Context, we don't have one. Recalling !eeheap -gc output:

You might end up with a buffer overflow someday, and obliterate the MethodTable of an object right after your array of StrongBad fan club members. The next time a GC occurs, your program will crash. Let's simulate that dreadful occurrance and see how !dumpheap responds:

0:000> ed adf7f8 00650033 (I'm overwriting the MethodTable of the array we've been enjoying)
0:000> !dumpheap 00a51000 00ae4000
...
00adf7ac 03135ca0 76
object 00adf7f8: does not have valid MT
curr_object : 00adf7f8
Last good object: 00adf7ac

This allows you to become suspicious of the last good object, 00adf7ac. Of course we know he's alright, he's not responsible for what happened. But in the real world, an aggressive response is required! [imagine WWII air-raid siren here]

What is that last good object anyway?

0:000> !dumpobj adf7ac
Name: System.Byte[]
MethodTable: 03135ca0
EEClass: 03135c1c
Size: 76(0x4c) bytes
Array: Rank 1, Type Byte
Element Type: System.Byte
Fields:
None

Who cares about him? If I can find a root to this object on a stack, I may be close to code that would overwrite the next object:

0:000> !gcroot adf7ac
Note: Roots found on stacks may be false positives. Run "!help gcroot" for
more info.
Scan Thread 0 OSTHread 16ac
ESP:12ea9c:Root:00ad4914(System.Reflection.Emit.MethodBuilder)->00ad4448(System.
Reflection.Emit.TypeBuilder)->00adf52c(System.Reflection.Emit.MethodBuilder)->00
adf74c(System.Reflection.Emit.ILGenerator)->00adf7ac(System.Byte[])
Scan Thread 2 OSTHread 169c

Thread 0, eh? He's employed by an ILGenerator, eh? What kind of nefarious operations are going on in their shop! Okay I'll stop. But it's true, often the last good object is somehow responsible, and a PInvoke overrun is the reason why.

I've ignore the Large Object Heap Segment, but it is crawled in the same way. It has no pesky Allocation Contexts to muddy the water. Large Object segments are never compacted, it would take to long to move such objects around, as they are over 80K in size.

Have fun with PSSCOR.DLL.

Traversing the gc heap (and introducing PSSCOR.DLL)

Additional resources