Large Object Heap Fragmentation

Question

The C#/.NET application I am working on is suffering from a slow memory leak. I have used CDB with SOS to try to determine what is happening but the data does not seem to make any sense so I was hoping one of you may have experienced this before.

The application is running on the 64 bit framework. It is continuously calculating and serialising data to a remote host and is hitting the Large Object Heap (LOH) a fair bit. However, most of the LOH objects I expect to be transient: once the calculation is complete and has been sent to the remote host, the memory should be freed. What I am seeing, however, is a large number of (live) object arrays interleaved with free blocks of memory, e.g., taking a random segment from the LOH:

0:000> !DumpHeap 000000005b5b1000  000000006351da10
         Address               MT     Size
...
000000005d4f92e0 0000064280c7c970 16147872
000000005e45f880 00000000001661d0  1901752 Free
000000005e62fd38 00000642788d8ba8     1056       <--
000000005e630158 00000000001661d0  5988848 Free
000000005ebe6348 00000642788d8ba8     1056
000000005ebe6768 00000000001661d0  6481336 Free
000000005f214d20 00000642788d8ba8     1056
000000005f215140 00000000001661d0  7346016 Free
000000005f9168a0 00000642788d8ba8     1056
000000005f916cc0 00000000001661d0  7611648 Free
00000000600591c0 00000642788d8ba8     1056
00000000600595e0 00000000001661d0   264808 Free
...

Obviously I would expect this to be the case if my application were creating long-lived, large objects during each calculation. (It does do this and I accept there will be a degree of LOH fragmentation but that is not the problem here.) The problem is the very small (1056 byte) object arrays you can see in the above dump which I cannot see in code being created and which are remaining rooted somehow.

Also note that CDB is not reporting the type when the heap segment is dumped: I am not sure if this is related or not. If I dump the marked (<--) object, CDB/SOS reports it fine:

0:015> !DumpObj 000000005e62fd38
Name: System.Object[]
MethodTable: 00000642788d8ba8
EEClass: 00000642789d7660
Size: 1056(0x420) bytes
Array: Rank 1, Number of elements 128, Type CLASS
Element Type: System.Object
Fields:
None

The elements of the object array are all strings and the strings are recognisable as from our application code.

Also, I am unable to find their GC roots as the !GCRoot command hangs and never comes back (I have even tried leaving it overnight).

So, I would very much appreciate it if anyone could shed any light as to why these small (<85k) object arrays are ending up on the LOH: what situations will .NET put a small object array in there? Also, does anyone happen to know of an alternative way of ascertaining the roots of these objects?

Thanks in advance.

---

Update 1

Another theory I came up with late yesterday is that these object arrays started out large but have been shrunk leaving the blocks of free memory that are evident in the memory dumps. What makes me suspicious is that the object arrays always appear to be 1056 bytes long (128 elements), 128 * 8 for the references and 32 bytes of overhead.

The idea is that perhaps some unsafe code in a library or in the CLR is corrupting the number of elements field in the array header. Bit of a long shot I know...

---

Update 2

Thanks to Brian Rasmussen (see accepted answer) the problem has been identified as fragmentation of the LOH caused by the string intern table! I wrote a quick test application to confirm this:

static void Main()
{
    const int ITERATIONS = 100000;

    for (int index = 0; index < ITERATIONS; ++index)
    {
        string str = "NonInterned" + index;
        Console.Out.WriteLine(str);
    }

    Console.Out.WriteLine("Continue.");
    Console.In.ReadLine();

    for (int index = 0; index < ITERATIONS; ++index)
    {
        string str = string.Intern("Interned" + index);
        Console.Out.WriteLine(str);
    }

    Console.Out.WriteLine("Continue?");
    Console.In.ReadLine();
}

The application first creates and dereferences unique strings in a loop. This is just to prove that the memory does not leak in this scenario. Obviously it should not and it does not.

In the second loop, unique strings are created and interned. This action roots them in the intern table. What I did not realise is how the intern table is represented. It appears it consists of a set of pages -- object arrays of 128 string elements -- that are created in the LOH. This is more evident in CDB/SOS:

0:000> .loadby sos mscorwks
0:000> !EEHeap -gc
Number of GC Heaps: 1
generation 0 starts at 0x00f7a9b0
generation 1 starts at 0x00e79c3c
generation 2 starts at 0x00b21000
ephemeral segment allocation context: none
 segment    begin allocated     size
00b20000 00b21000  010029bc 0x004e19bc(5118396)
Large object heap starts at 0x01b21000
 segment    begin allocated     size
01b20000 01b21000  01b8ade0 0x00069de0(433632)
Total Size  0x54b79c(5552028)
------------------------------
GC Heap Size  0x54b79c(5552028)

Taking a dump of the LOH segment reveals the pattern I saw in the leaking application:

0:000> !DumpHeap 01b21000 01b8ade0
...
01b8a120 793040bc      528
01b8a330 00175e88       16 Free
01b8a340 793040bc      528
01b8a550 00175e88       16 Free
01b8a560 793040bc      528
01b8a770 00175e88       16 Free
01b8a780 793040bc      528
01b8a990 00175e88       16 Free
01b8a9a0 793040bc      528
01b8abb0 00175e88       16 Free
01b8abc0 793040bc      528
01b8add0 00175e88       16 Free    total 1568 objects
Statistics:
      MT    Count    TotalSize Class Name
00175e88      784        12544      Free
793040bc      784       421088 System.Object[]
Total 1568 objects

Note that the object array size is 528 (rather than 1056) because my workstation is 32 bit and the application server is 64 bit. The object arrays are still 128 elements long.

So the moral to this story is to be very careful interning. If the string you are interning is not known to be a member of a finite set then your application will leak due to fragmentation of the LOH, at least in version 2 of the CLR.

In our application's case, there is general code in the deserialisation code path that interns entity identifiers during unmarshalling: I now strongly suspect this is the culprit. However, the developer's intentions were obviously good as they wanted to make sure that if the same entity is deserialised multiple times then only one instance of the identifier string will be maintained in memory.

Answer 1

If the format is recognizable as your application, why haven't you identified the code that is generating this string format? If there's several possibilities, try adding unique data to figure out which code path is the culprit.

The fact that the arrays are interleaved with large freed items leads me to guess that they were originally paired or at least related. Try to identify the freed objects to figure out what was generating them and the associated strings.

Once you identify what is generating these strings, try to figure out what would be keeping them from being GCed. Perhaps they're being stuffed in a forgotten or unused list for logging purposes or something similar.

---

EDIT: Ignore the memory region and the specific array size for the moment: just figure out what is being done with these strings to cause a leak. Try the !GCRoot when your program has created or manipulated these strings just once or twice, when there's fewer objects to trace.

Answer 2

The CLR uses the LOH to preallocate a few objects (such as the array used for interned strings). Some of these are less than 85000 bytes and thus would not normally be allocated on the LOH.

It is an implementation detail, but I assume the reason for this is to avoid unnecessary garbage collection of instances that are supposed to survive as long as the process it self.

Also due to a somewhat esoteric optimization, any double[] of 1000 or more elements is also allocated on the LOH.

Answer 3

When reading descriptions of how GC works, and the part about how long-lived objects end up in generation 2, and the collection of LOH objects happens at full collection only - as does collection of generation 2, the idea that springs to mind is... why not just keep generation 2 and large objects in the same heap, as they're going to get collected together?

If that's what actually happens then it would explain how small objects end up in the same place as the LOH - if they're long lived enough to end up in generation 2.

And so your problem would appear to be a pretty good rebuttal to the idea that occurs to me - it would result in the fragmentation of the LOH.

Summary: your problem could be explained by the LOH and generation 2 sharing the same heap region, although that is by no means proof that this is the explanation.

Update: the output of !dumpheap -stat pretty much blows this theory out of the water! The generation 2 and LOH have their own regions.

Answer 4

Why can't Microsoft provide us with a simple API in .NET called:

GC.CompactLargeObjectHeap()

even if this method causes the application to hang for 10 seconds or more -- it beats the heck out of crashing and requiring Application restart to clean up the memory!

There are a great many applications that use 3rdparty libraries which make allocations on the LOH. For example, even Microsoft's own XNA fragments the heck out of the LOH each time you do "new Texture2D()" or "Texture.FromFile()" without any remedy!

So if you are trying to create a "Game Engine" in .NET -- this is a real pain in the neck, to have our LOH leak away memory without any way to stop it. All we can do is "slow it down", unless we decide to "make our own library" and forget about XNA. Surely this is not what Microsoft wants!

Many months of headache would be resolved for us (and others!) if MS would simply provide us with this one method; I'll say it again:

GC.CompactLargeObjectHeap()

And while I'm making this suggestion, I would suggest the MS take it one step further, and allow this command:

GC.DoLargeObjectHeapCompactionWhenOutOfMemory = true;   // would be false by default

So we would just set this to true for "Visual3D Game Engine" (our product), and then automatically, when the fragmentation causes the first OOM exception, .NET would automatically compact the LOH, and then retry the allocation!

Wow, now that would aligned with all the .NET hype about "it just works" and "easy to use"... and would only cause this "performance hit" for extreme cases, where the alternative is OOM crash, forcing a restart of the application!

Please Microsoft -- do this for us!

---

Please do not announce your ignorance by saying the trite naive advice of "just use better memory management" -- yeesh! This is very inappropriate advice! You would have to also say "write ALL your own 3rdparty libraries" (e.g. XNA)!!!!

Why hasn't Microsoft already provided this behavior in .NET???? What would it hurt? It would save us from these very frustrating and time-consuming band-aid solutions, which can at best "slow down the memory leaks" but never fully fix them.

The solution we are requesting would be harmless to those who don't want to use it, and provides a refreshing salvation to those who really do want to use it. Please, Please, Please, provide this in .NET 4.0+.

Answer 5

Great question, I learned by reading the questions.

I think other bit of the deserialisation code path are also using the large object heap, hence the fragmentation. If all the strings were interned at the SAME time, I think you would be ok.

Given how good the .net garbage collector is, just letting the deserialisation code path create normal string object is likely to be good enough. Don't do anything more complex until the need is proven.

I would at most look at keeping a hash table of the last few strings you have seen and reusing these. By limiting the hash table size and passing the size in when you create the table you can stop most fragmentation. You then need a way to remove strings you have not seen recently from the hash table to limit it’s size. But if the strings the deserialisation code path create are short lived anyway you will not gain much if anything.

Answer 6

Here are couple of ways to Identify the exact call-stack of LOH allocation.

And to avoid LOH fragmentation Pre-allocate large array of objects and pin them. Reuse these objects when needed. Here is post on LOH Fragmentation. Something like this could help in avoiding LOH fragmentation.