Section 4.3. .NET Garbage Collection

4.3. .NET Garbage Collection

In .NET programming, exiting a scope doesn't destroy an object, and unlike COM, .NET doesn't use reference counting of objects. Instead, .NET has a sophisticated garbage-collection mechanism that detects when an object is no longer being used by clients and then destroys it. To do so, .NET must keep track of accessible paths to objects in the code. In the abstract, when the JIT compiler compiles the IL code, it updates a list of roots top-level primordial application starting points, such as static variables and methods (Main, for example), but also internal .NET entities that should be kept alive as long as the application is running. Each root forms the topmost node in a tree-like graph. .NET keeps track of each new object it allocates off the managed heap and of the relationship between this object and its clients. Whenever an object is allocated, .NET updates its graph of objects and adds a reference in the graph to that object from the object that created it. Similarly, .NET updates the graph every time a client receives a reference to an object and when an object saves a reference to another object as a member variable. The JIT compiler also injects code to update the graphs each time the execution path enters or exits a scope.

The entity responsible for releasing unused memory is called the garbage collector. When garbage collection is triggered (usually when the managed heap is exhausted, but also when garbage collection is explicitly requested by the code), the garbage collector deems every object in the graphs as garbage. The garbage collector then recursively traverses each graph, going down from the roots, looking for reachable objects. Every time the garbage collector visits an object, it tags it as reachable. Because the graphs represent the relationships between clients and objects, when the garbage collector is done traversing the graphs, it knows which objects were reachable and which were not. Reachable objects should be kept alive. Unreachable objects are considered garbage, and therefore destroying them does no harm. This algorithm handles cyclic references between objects as well (i.e., where Object A references Object B, which references Object C, which references back to Object A). When the garbage collector reaches an object already marked as reachable, it doesn't continue to look for other objects reachable from that tagged object.

Next, the garbage collector scans the managed heap and disposes of the unreachable objects by compacting the heap and overwriting the unreachable objects with reachable one (see Figure 4-2). The garbage collector moves reachable objects down the heap, writing over the garbage, and thus frees more space at the end for new object allocations. All unreachable objects are purged from the graphs.

Figure 4-2. Garbage collection results in heap compaction

However, compacting the heap by moving down all the reachable objects means that any client that has a reference to those objects (e.g., Objects 8 and 10 in Figure 4-2) now holds an invalid reference. The garbage collector compensates for that by patching up all the references to the moved objects in the client code.

Another problem faced by the garbage collector is that it must ensure that the application code doesn't change the structure of the object graphs or the state of the heap during the cleanup. The only safe way to cope with that is to suspend all application threads during garbage collection. So how does .NET know when it's safe to suspend a thread? The thread might be in the middle of some allocation or data structure modification, such as adding an element to a linked list. To handle this problem, the JIT compiler inserts safe points into the codethat is, points in the execution path (such as those returning from a method call) that are safe for thread suspension. The garbage collector actually hijacks the thread by inserting a different return address from the safe point: an address that includes a call to suspend that thread. When garbage collection is done, .NET sends the thread back to its original return address to continue normal execution.

Garbage collection is usually triggered in .NET by heap exhaustion, but application shutdown also triggers garbage collection.