1# Oilpan: C++ Garbage Collection
2
3Oilpan is an open-source garbage collection library for C++ that can be used stand-alone or in collaboration with V8's JavaScript garbage collector.
4Oilpan implements mark-and-sweep garbage collection (GC) with limited compaction (for a subset of objects).
5
6**Key properties**
7
8- Trace-based garbage collection;
9- Incremental and concurrent marking;
10- Incremental and concurrent sweeping;
11- Precise on-heap memory layout;
12- Conservative on-stack memory layout;
13- Allows for collection with and without considering stack;
14- Non-incremental and non-concurrent compaction for selected spaces;
15
16See the [Hello World](https://chromium.googlesource.com/v8/v8/+/main/samples/cppgc/hello-world.cc) example on how to get started using Oilpan to manage C++ code.
17
18Oilpan follows V8's project organization, see e.g. on how we accept [contributions](https://v8.dev/docs/contribute) and [provide a stable API](https://v8.dev/docs/api).
19
20## Threading model
21
22Oilpan features thread-local garbage collection and assumes heaps are not shared among threads.
23In other words, objects are accessed and ultimately reclaimed by the garbage collector on the same thread that allocates them.
24This allows Oilpan to run garbage collection in parallel with mutators running in other threads.
25
26References to objects belonging to another thread's heap are modeled using cross-thread roots.
27This is even true for on-heap to on-heap references.
28
29Oilpan heaps may generally not be accessed from different threads unless otherwise noted.
30
31## Heap partitioning
32
33Oilpan's heaps are partitioned into spaces.
34The space for an object is chosen depending on a number of criteria, e.g.:
35
36- Objects over 64KiB are allocated in a large object space
37- Objects can be assigned to a dedicated custom space.
38  Custom spaces can also be marked as compactable.
39- Other objects are allocated in one of the normal page spaces bucketed depending on their size.
40
41## Precise and conservative garbage collection
42
43Oilpan supports two kinds of GCs:
44
451. **Conservative GC.**
46A GC is called conservative when it is executed while the regular native stack is not empty.
47In this case, the native stack might contain references to objects in Oilpan's heap, which should be kept alive.
48The GC scans the native stack and treats the pointers discovered via the native stack as part of the root set.
49This kind of GC is considered imprecise because values on stack other than references may accidentally appear as references to on-heap object, which means these objects will be kept alive despite being in practice unreachable from the application as an actual reference.
50
512. **Precise GC.**
52A precise GC is triggered at the end of an event loop, which is controlled by an embedder via a platform.
53At this point, it is guaranteed that there are no on-stack references pointing to Oilpan's heap.
54This means there is no risk of confusing other value types with references.
55Oilpan has precise knowledge of on-heap object layouts, and so it knows exactly where pointers lie in memory.
56Oilpan can just start marking from the regular root set and collect all garbage precisely.
57
58## Atomic, incremental and concurrent garbage collection
59
60Oilpan has three modes of operation:
61
621. **Atomic GC.**
63The entire GC cycle, including all its phases (e.g. see [Marking](#Marking-phase) and [Sweeping](#Sweeping-phase)), are executed back to back in a single pause.
64This mode of operation is also known as Stop-The-World (STW) garbage collection.
65It results in the most jank (due to a single long pause), but is overall the most efficient (e.g. no need for write barriers).
66
672. **Incremental GC.**
68Garbage collection work is split up into multiple steps which are interleaved with the mutator, i.e. user code chunked into tasks.
69Each step is a small chunk of work that is executed either as dedicated tasks between mutator tasks or, as needed, during mutator tasks.
70Using incremental GC introduces the need for write barriers that record changes to the object graph so that a consistent state is observed and no objects are accidentally considered dead and reclaimed.
71The incremental steps are followed by a smaller atomic pause to finalize garbage collection.
72The smaller pause times, due to smaller chunks of work, helps with reducing jank.
73
743. **Concurrent GC.**
75This is the most common type of GC.
76It builds on top of incremental GC and offloads much of the garbage collection work away from the mutator thread and on to background threads.
77Using concurrent GC allows the mutator thread to spend less time on GC and more on the actual mutator.
78
79## Marking phase
80
81The marking phase consists of the following steps:
82
831. Mark all objects in the root set.
84
852. Mark all objects transitively reachable from the root set by calling `Trace()` methods defined on each object.
86
873. Clear out all weak handles to unreachable objects and run weak callbacks.
88
89The marking phase can be executed atomically in a stop-the-world manner, in which all 3 steps are executed one after the other.
90
91Alternatively, it can also be executed incrementally/concurrently.
92With incremental/concurrent marking, step 1 is executed in a short pause after which the mutator regains control.
93Step 2 is repeatedly executed in an interleaved manner with the mutator.
94When the GC is ready to finalize, i.e. step 2 is (almost) finished, another short pause is triggered in which step 2 is finished and step 3 is performed.
95
96To prevent a user-after-free (UAF) issues it is required for Oilpan to know about all edges in the object graph.
97This means that all pointers except on-stack pointers must be wrapped with Oilpan's handles (i.e., Persistent<>, Member<>, WeakMember<>).
98Raw pointers to on-heap objects create an edge that Oilpan cannot observe and cause UAF issues
99Thus, raw pointers shall not be used to reference on-heap objects (except for raw pointers on native stacks).
100
101## Sweeping phase
102
103The sweeping phase consists of the following steps:
104
1051. Invoke pre-finalizers.
106At this point, no destructors have been invoked and no memory has been reclaimed.
107Pre-finalizers are allowed to access any other on-heap objects, even those that may get destructed.
108
1092. Sweeping invokes destructors of the dead (unreachable) objects and reclaims memory to be reused by future allocations.
110
111Assumptions should not be made about the order and the timing of their execution.
112There is no guarantee on the order in which the destructors are invoked.
113That's why destructors must not access any other on-heap objects (which might have already been destructed).
114If some destructor unavoidably needs to access other on-heap objects, it will have to be converted to a pre-finalizer.
115The pre-finalizer is allowed to access other on-heap objects.
116
117The mutator is resumed before all destructors have ran.
118For example, imagine a case where X is a client of Y, and Y holds a list of clients.
119If the code relies on X's destructor removing X from the list, there is a risk that Y iterates the list and calls some method of X which may touch other on-heap objects.
120This causes a use-after-free.
121Care must be taken to make sure that X is explicitly removed from the list before the mutator resumes its execution in a way that doesn't rely on X's destructor (e.g. a pre-finalizer).
122
123Similar to marking, sweeping can be executed in either an atomic stop-the-world manner or incrementally/concurrently.
124With incremental/concurrent sweeping, step 2 is interleaved with mutator.
125Incremental/concurrent sweeping can be atomically finalized in case it is needed to trigger another GC cycle.
126Even with concurrent sweeping, destructors are guaranteed to run on the thread the object has been allocated on to preserve C++ semantics.
127
128Notes:
129
130* Weak processing runs only when the holder object of the WeakMember outlives the pointed object.
131If the holder object and the pointed object die at the same time, weak processing doesn't run.
132It is wrong to write code assuming that the weak processing always runs.
133
134* Pre-finalizers are heavy because the thread needs to scan all pre-finalizers at each sweeping phase to determine which pre-finalizers should be invoked (the thread needs to invoke pre-finalizers of dead objects).
135Adding pre-finalizers to frequently created objects should be avoided.
136