Today, in the next article from .NET Internals series on my blog, we’re going to investigate how the garbage collector (GC) actually releases the memory (which is its main purpose as could be read here), what is marking phase and how the managed heaps are compacted in order to optimize the process. We’ll also see when may the collection be triggered.

Finding objects to be garbage-collected

As we already know, .NET doesn’t allow developers to directly allocate the objects on the heap. Instead, the only thing the programmer needs to do is to use the new keyword – framework takes care of all the rest (placing the object on the proper heap, initializing it etc.). After that, you can simply forget about your object, because it is released (collected) automatically by the garbage collector as soon as it’s not needed anymore. But how does the GC know which objects it can collect?

In principle, all the garbage collector does is looking for the allocated objects which aren’t referenced by anything, which means that such objects are no longer needed. This makes such objects ready to be collected (their memory can be released – marked as being possible to be used again).

There are several sources of references to objects allocated on the heap:

• stack (as we know from the 2nd post),
• global or static reference variables,
• CPU registers,
• interop references (.NET objects used in COM/API calls),
• objects finalization references.

GC roots tree

All above-listed sources are called GC roots (also referred to as root references). As objects referenced from any of the roots can reference another objects (for example a customer may reference its orders collection), all these nested references are represented as a tree (graph) for every .NET application. Such references tree may look as follows:

As you can see, GC root is present on the stack, pointing to Customer reference object. It contains an ArrayList collection of orders, which is referenced by Customer object. The collection itself also contains references to its elements, so the tree grows up.

Each root contains either a reference (address) to some object or null value.

Unreachable (not used) objects

The GC roots tree described above is used by garbage collector to know which objects are no longer needed. As we see, the graph contains all objects that are still in use (are referenced by something else).

GC uses this information the other way around –  generally the GC classifies all objects that are not reachable from any root (not present in the graph) as garbage. Such objects are then collected (the memory allocated for them is released) by the GC during its collection cycles, which will be described in details in the next posts in the series.

Memory releasing (garbage collection)

As mentioned, garbage collection is a process executed in cycles, which will be covered in the later articles, but the process itself contains two main steps:

1. Marking phase – finding which objects are still in use,
2. Collection – actual collection process of not-anymore-used objects (including SOH compaction).

Let’s see both phases in details.

Marking phase

When garbage collector runs its memory releasing process (referred to as ‘collection’), it needs to know which objects on the heap are still in use by the application – obviously, such objects cannot be collected.

In order to obtain this information, GC goes through the whole root references tree and for each GC root moves along all its reference tree (all objects that are referenced from the particular root) in order to mark each object in this tree as “still in use”. That’s why this integrated part of garbage collection process is called marking phase.

Marking is a recursive operation, because as we said before, roots reference some object, which references another object, which references another object…

so in order to make sure that every object in use is added to the “still in use” list (if it’s not there yet), this recursive marking is done as can be seen below:

Let’s now see how it fits into the actual collection operation.

Collection

The actual collection process, including previously-examined marking phase, can be pictured with the following pseudo-code:

First of all, GC gets a list of all GC roots in the application (the list is maintained by JIT compiler and the runtime). Then it needs to iterate through each root and perform marking operation on it. Knowing that marking is a recursive operation, after this phase is finished, GC can be sure that all objects that have any root reference (either direct one or being pointed to by another objects) are added to the list of objects in use.

Next step is the actual memory releasing process of not used objects, represented as a call to Cleanup() method on the listing above. Memory cleanup itself is a very simple process – it’s just marking a particular memory block(s) as free (not used). There’s no overwriting of memory or anything like that 🙂 (except ‘side overwriting’ which happens during heaps compaction – described below). Just simple boolean-like terminology is used for memory blocks – used (1) or not used (0). It works that simple for LOH , but collection on SOH (still don’t know what are LOH and SOH? Go and read here quickly!) also involves the compaction process. Let’s see what that is.

Heaps compaction

As we know from the first post, memory on the managed heaps can get fragmented, leaving holes of not used memory between live objects. That’s why the garbage collection for SOH process involves compaction, which is a process of removing the memory holes on the heap. It’s often referred to as a Copy Collection process, because it’s based on finding the dead objects or memory holes (it’s actually the same – holes of the memory that are not used by anything, present in-between live objects) and overwriting these holes with the live objects allocated later (next) on the heap – by copying chunks of live objects ‘down in the heap’.

The result of the compaction process is the contiguous SOH, where objects are allocated on top of each other with no or minimal possible number of memory holes.

Finally, addresses to the objects stored in reference variables are updated in order to point to the correct, new places in the memory occupied by particular object.

The best gain we get from the compaction is that the SOH is not fragmented, so the memory can be used efficiently. On the other hand it requires some CPU time, which may have some impact on our application’s performance.

By default, LOH is not compacted because of the size of objects stored on it (>85 kilobytes). Copying chunks of such objects would take too much time. Instead, used space and memory holes on the LOH are tracked and the allocation algorithm is adjusted to try to reserve the memory for new objects in the optimal way (by finding the best possible free slots on the fragmented heap).

What’s worth noticing is that starting from .NET Framework 4.5.1, LOH compaction can be enabled on demand by using GCSettings.LargeObjectHeapCompactionMode property.

When does the GC run?

It can be stated that GC works in a non-deterministic manner. It runs on a separate thread when one of the following conditions becomes true:

•  the OS sends low memory notification,
• the memory used by the objects on the managed heap exceeds some defined threshold (which is adjusted dynamically at runtime, based on current allocations),
• GC.Collect() method is called in the code.

If you see GC.Collect() directly used in code, in almost every case it means that there’s something wrong with the application’s implementation. Several great Microsoft engineers and open-source contributors have worked on automatic garbage collection in order to not trigger it manually 🙂

The exceptions for this rule I’d accept are maybe some gaming implementations, in which you work with huge objects and sometimes you’d like to affect the way when these objects’ memory is cleaned-up or usage in debugging – most of memory profilers (like dotMemory or ANTS Memory Profiler) force the collection before the memory snapshot is done by the user. This is reasonable, because when debugging memory leaks or issues you wanna see which objects remain allocated after GC does its cleanup.

What’s also worth mentioning is that when the garbage collection is run, all threads are stopped by default, except the thread in which the collection was triggered. However, this can be configured by changing the GC’s settings to work in workstation or server mode, as well as making it run concurrently or in the background. There are different use cases in which each settings combination should be used – you can find more details about it here and here.

Summary

Today we’ve covered the main blocks from which the garbage collection process in .NET is built. We went through marking phase, then the actual collection process – also including heaps compaction. We learnt how the GC roots tree is built and how garbage collector knows which objects it can clean-up during its cycle. We also listed cases in which the collection can be triggered.

In the next post we’ll examine a very interesting concept – generational garbage collection.

See ya next week! 😉