As you all know, in CLR memory management is done by Garbage collector (GC). When GC can't find memory in preallocated memory chunk (GC heap) for new objects and can't book enough memory from the OS to expand GC heap, it throws OutOfMemoryException (OOM).

 

The problem

From time to time, I've heard complaints about OOM - people analyze code and monitor memory usage, find out that sometimes their .NET applications throw OOM when there's enough free memory. In most cases I've seen, the problems are:

  1. The virtual address space of the OS is fragmented. This is usually caused by some unmanaged components in the application. This issue exists in unmanaged world for long time, but it could hit GC hard. GC heap is managed in unit of segments, whose size is 16MB for workstation version and 32MB for server version in V1.0 and V1.1. That means when CLR needs to expand GC heap, it has to find 32MB consecutive free virtual memory for a server application. Usually this is not a problem in a system with 2GB address space for user mode. But if there are some unmanaged DLLs in the application manipulating virtual memory without carefulness, the virtual address space could be divided into small blocks of free and reserved memory. Thus GC would fail to find a big enough piece of free memory although the total free memory is enough. This kind of problems could be found out by looking through the whole virtual address space to see which block is reserved by which component.
  2. The GC heap itself is fragmented, meaning GC can't allocate objects in already reserved segments which actually have enough free space inside. I want to focus on this problem in this blog. 

A glance of GC heap

Usually managed heap shouldn't suffer from fragmentation problem because the heap is compacted during GC. Blow shows an oversimplified model of CLR's GC heap: 

  • All objects are adjacent to each other; the top of heap is free space. 

       |---------|

       |free     |

       |_________|

       |Object B |

       |         |

       |_________|

       |Object A |

       |_________|

       |   ...   | 

 

  • New objects are allocated in free space. Allocation always happens at top, just as a stack.

       |---------|

       |free     |

       |_________|

       |Object C |

       |_________|

       |Object B |

       |         |

       |_________|

       |Object A |

       |_________|

       |   ...   | 

  • When free space is used up, a GC happens. During GC, reachable objects are marked. 

       |---------|

       |Object C | (marked)

       |_________|

       |Object B |

       |         |

       |_________|

       |Object A | (marked)

       |_________|

       |   ...   | 

  • After GC, heap is compacted, live (reachable) objects are relocated, dead (unreachable) objects are swept out. 

       |---------|

       |free     |

       |_________|

       |Object C |

       |_________|

       |Object A |

       |_________|

       |   ...   |

 

Free space in GC heap

In above model, you can see that GC actually does a good job to defragment the heap. Free space is always at top of the heap and available for new allocation. But in real production, free space could reside among allocated objects. That is because:

  1. Sometimes GC could choose not to compact part of the heap when it's not necessary. Since relocating all objects could be expensive, GC might avoid doing so under some conditions. In that case, GC will keep a list of free space in heap for future compaction. This won't cause heap fragmentation because GC has full control over the free space. GC could fill up those blocks anytime later when necessary.
  2. Pinned objects are not movable. So if a pinned object survives a GC, it could create a block of free space, like this:

 

       before GC:                              after GC:

 

       |---------|                             |---------|

       |Object C | (pinned, reachable)         |Object C | (pinned)

       |_________|                             |_________|

       |Object B | (unreachable)               | free    |

       |         |                             |         |

       |_________|                             |_________|

       |Object A | (reachable)                 |Object A |

       |_________|                             |_________|

       |   ...   |                             |   ...   |

 

 

How pinning could fragment GC heap

if an application keeps pinning objects in this pattern: pin a new object, do some allocation, pin another object, do some allocation ... and all pinned objects remain pinned for long time, a lot of free space will be created, showed below: 

  • A new object is pinned

       |---------|

       |free     |

       |_________|

       |Pinned 1 |

       |_________|

       |Object A |

       |_________|

       |   ...   | 

  • After some allocation, another object is pinned

       |---------|

       |free     |

       |_________|

       |Pinned 2 |

       |_________|

       |   ...   |

       |_________|

       |Pinned 1 |

       |_________|

       |Object A |

       |_________|

       |   ...   | 

  • More objects are pinned, with unpinned objects in between 

       |_________|

       |Pinned n |

       |_________|

       |   ...   |

       |_________|

       |Pinned 2 |

       |_________|

       |   ...   |

       |_________|

       |Pinned 1 |

       |_________|

       |Object A |

       |_________|

       |   ...   | 

  • A GC happens, because pinned objects can't be relocated, free space remains in the heap 

       |_________|

       |Pinned n |

       |_________|

       | free    |

       |_________|

       |Pinned 2 |

       |_________|

       | free    |

       |_________|

       |Pinned 1 |

       |_________|

       | free    |

       |_________|

       |   ...   |

 

Such a process could create a GC heap with a lot of free slots. Those free slots are being partially reused for allocation but when they are too small or when their remainder is too small, GC can’t use them as long as the objects are pinned. This would prevent GC from using the heap efficiently and might cause OOM eventually.

 

One thing makes the situation worse is that although a developer may not use pinned objects directly, some .Net libraries use them under the hood, like asynchronized IO. For example, in V1.0 and V1.1 the buffer passed to Socket.BeginReceive is pinned by the library so that unmanaged code could access the buffer. Consider a socket server application which handles thousands of socket requests per second and each request could take several minutes because of slow connection, GC heap could be fragmented a lot because of large amount of pinned objects and long lifetime some objects are pinned; then OOM could happen.

 

How to diagnose the problem

To determine if GC heap is fragmented, SOS is the best tool. Sos.dll is a debugger extension shipped with .NET framework which could check some underlying data structure in CLR. For example, “DumpHeap” could traverse GC heap and dump every object in the heap like this:

 

     0:000>!dumpheap

 

     Address       MT     Size

     00a71000 0015cde8       12 Free

     00a7100c 0015cde8       12 Free

     00a71018 0015cde8       12 Free

     00a71024 5ba58328       68

     00a71068 5ba58380       68

     00a710ac 5ba58430       68

     00a710f0 5ba5dba4       68

     ...

     00a91000 5ba88bd8     2064

     00a91810 0019fe48     2032 Free

     00a92000 5ba88bd8     4096

     00a93000 0019fe48     8192 Free

     00a95000 5ba88bd8     4096

     ...

     total 1892 objects

   

     Statistics:

           MT    Count TotalSize Class Name

     5ba7607c        1        12 System.Security.Permissions.HostProtectionResource

     5ba75d54        1        12 System.Security.Permissions.SecurityPermissionFlag

     5ba61f18        1        12 System.Collections.CaseInsensitiveComparer

     ...

     0015cde8        6     10260      Free

     5ba57bf8      318     18136 System.String

     ...

 

In this example, “DumpHeap” shows that there are 3 small free slots (They appear as special “Free” objects) at the beginning of the heap, followed by some objects with size 68 bytes. More interestingly, the statistics shows that there are 10,260 bytes Free objects (free space among live objects), and 18,136 bytes of string totally in the heap. If you find the Free objects take a very big percentage of the heap, the heap is fragmented (in whidbey, "DumpHeap" would do more analysis about heap fragmentation). In this case, you want to check the objects nearby the free space to see what they are and who holds their roots, you could do it using “DumpObj” and “GCRoot”:

 

     0:000>!dumpobj 00a92000

 

     Name: System.Byte[]

     MethodTable 0x00992c3c

     EEClass 0x00992bc4

     Size 4096(0x1000) bytes

     Array: Rank 1, Type System.Byte

     Element Type: System.Byte

 

  

     0:000>!gcroot 00a92000

 

     Scan Thread 0 (728)

     Scan Thread 1 (730)

     ESP:88cf548:Root:05066b48(System.IO.MemoryStream)->00a92000 (System.Byte[])

     ESP:88cf568:Root:05066b48(System.IO.MemoryStream)->00a92000 (System.Byte[])

     ...

     Scan HandleTable 9b130

     Scan HandleTable 9ff18

     HANDLE(Pinned):d41250:Root: 00a92000 (System.Byte[])

 

This shows that the object at address 00a92000 is a byte array, it's rooted by local variables in thread 1(to be precise, !GCRoot's output of roots in stack can't be trusted) and a pinned handle.

 

And the command "ObjSize" list all handles including pinned ones:

 

     0:000>!objsize

 

     ...

     HANDLE(Pinned):d41250: sizeof(00a92000) = 4096 ( 0x1000) bytes (System.Byte[])

     HANDLE(Pinned):d41254: sizeof(00a95000) = 4096 ( 0x1000) bytes (System.Byte[])

     HANDLE(Pinned):d41258: sizeof(00ac8b5b0) = 16 ( 0x10) bytes (System.Byte[])

     ...

 

Using those Sos commands, you could get a clear picture if the heap is fragmented and how. I believe Michael will have more blogs about details of Sos.

 

Solution

In Everett a lot of work is done in GC to recognize fragmentation caused by pinning and alleviate the situation, more work is already done in Whidbey. So hopefully, the problem won't show up in Whidbey. But besides change in the platform, user code could do something to avoid the issue too. From above analysis, we could tell:

  1. If the pinned objects are allocated around same time, the free slots between each two objects would be smaller, and the situation is better.
  2. If pinning happens on older objects, it could cause fewer problems. Because older objects live at bottom of heap but most of free space is generated on top of heap.
  3. The shorter the objects are pinned, the easier GC could compact the heap

 

So if pinning becomes an issue which causes OOM for a .NET application, instead of creating new object to pin every time, developers could consider preallocating the to-be-pinned objects and reusing them. That way those objects would live close to each other in older part of GC heap and the heap won’t be fragmented that much. For example, if an application keeps pinning 1K buffers (consider the socket server case), we could use such a buffer pool to get the buffers: 

 

public class BufferPool

{

    private const int INITIAL_POOL_SIZE = 512; // initial size of the pool

    private const int BUFFER_SIZE = 1024; // size of the buffers

 

    // pool of buffers

    private Queue m_FreeBuffers;

     

    // singleton instance

    private static BufferPool m_Instance = new BufferPool ();

           

    // Singleton attribute

    public static BufferPool Instance

    {  

        get {

            return m_Instance;

        }

    }

 

    protected BufferPool()

    {

        m_FreeBuffers = new Queue (INITIAL_POOL_SIZE);

        for (int i = 0; i < INITIAL_POOL_SIZE; i++)

        {

            m_FreeBuffers.Enqueue (new byte[BUFFER_SIZE]);

        }

    }

 

    // check out a buffer

    public byte[] Checkout (uint size)

    {

        if (m_FreeBuffers.Count > 0)

        {

            lock (m_FreeBuffers)

            {

                if (m_FreeBuffers.Count > 0)                           

                    return (byte[])m_FreeBuffers.Dequeue ();

            }

        }

        // instead of creating new buffer,

        // blocking waiting or refusing request may be better

        return new byte [BUFFER_SIZE];

    }

 

    // check in a buffer

    public void Checkin (byte[] buffer)

    {

        lock (m_FreeBuffers)

        {

            m_FreeBuffers.Enqueue (buffer);

        }

    }

}

 

 

This posting is provided "AS IS" with no warranties, and confers no rights. Use of included samples are subject to the terms specified at http://www.microsoft.com/info/cpyright.htm"