| 1 |
# Conservative GC Algorithmic Overview |
| 2 |
|
| 3 |
This is a description of the algorithms and data structures used in our |
| 4 |
conservative garbage collector. I expect the level of detail to increase with |
| 5 |
time. For a survey of GC algorithms, e.g. see Paul Wilson's |
| 6 |
["Uniprocessor Garbage Collection Techniques"](ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps) |
| 7 |
excellent paper. For an overview of the collector interface, see |
| 8 |
[here](gcinterface.md). |
| 9 |
|
| 10 |
This description is targeted primarily at someone trying to understand the |
| 11 |
source code. It specifically refers to variable and function names. It may |
| 12 |
also be useful for understanding the algorithms at a higher level. |
| 13 |
|
| 14 |
The description here assumes that the collector is used in default mode. |
| 15 |
In particular, we assume that it used as a garbage collector, and not just |
| 16 |
a leak detector. We initially assume that it is used in stop-the-world, |
| 17 |
non-incremental mode, though the presence of the incremental collector will |
| 18 |
be apparent in the design. We assume the default finalization model, but the |
| 19 |
code affected by that is very localized. |
| 20 |
|
| 21 |
Table of Contents |
| 22 |
* [Introduction](#introduction) |
| 23 |
* [Allocation](#allocation) |
| 24 |
* [Mark phase](#mark-phase) |
| 25 |
* [Sweep phase](#sweep-phase) |
| 26 |
* [Finalization](#finalization) |
| 27 |
* [Generational Collection and Dirty Bits](#generational-collection-and-dirty-bits) |
| 28 |
* [Black-listing](#black-listing) |
| 29 |
* [Thread support](#thread-support) |
| 30 |
* [Thread-local allocation](#thread-local-allocation) |
| 31 |
|
| 32 |
## Introduction |
| 33 |
|
| 34 |
The garbage collector uses a modified mark-sweep algorithm. Conceptually |
| 35 |
it operates roughly in four phases, which are performed occasionally as part |
| 36 |
of a memory allocation: |
| 37 |
|
| 38 |
1. _Preparation phase_ |
| 39 |
|
| 40 |
Each object has an associated mark bit. Clear all mark |
| 41 |
bits, indicating that all objects are potentially unreachable. |
| 42 |
|
| 43 |
2. _Mark phase_ |
| 44 |
|
| 45 |
Marks all objects that can be reachable via chains of pointers from |
| 46 |
variables. Often the collector has no real information about the location |
| 47 |
of pointer variables in the heap, so it views all static data areas, |
| 48 |
stacks and registers as potentially containing pointers. Any bit |
| 49 |
patterns that represent addresses inside heap objects managed by the |
| 50 |
collector are viewed as pointers. Unless the client program has made heap |
| 51 |
object layout information available to the collector, any heap objects |
| 52 |
found to be reachable from variables are again scanned similarly. |
| 53 |
|
| 54 |
3. _Sweep phase_ |
| 55 |
|
| 56 |
Scans the heap for inaccessible, and hence unmarked, |
| 57 |
objects, and returns them to an appropriate free list for reuse. This is |
| 58 |
not really a separate phase; even in non-incremental mode this operation |
| 59 |
is usually performed on demand during an allocation that discovers an |
| 60 |
empty free list. Thus the sweep phase is very unlikely to touch a page |
| 61 |
that would not have been touched shortly thereafter anyway. |
| 62 |
|
| 63 |
4. _Finalization phase_ |
| 64 |
|
| 65 |
Unreachable objects which had been registered for |
| 66 |
finalization are enqueued for finalization outside the collector. |
| 67 |
|
| 68 |
The remaining sections describe the memory allocation data structures, and |
| 69 |
then the last 3 collection phases in more detail. We conclude by outlining |
| 70 |
some of the additional features implemented in the collector. |
| 71 |
|
| 72 |
## Allocation |
| 73 |
|
| 74 |
The collector includes its own memory allocator. The allocator obtains memory |
| 75 |
from the system in a platform-dependent way. Under UNIX, it uses either |
| 76 |
`malloc`, `sbrk`, or `mmap`. |
| 77 |
|
| 78 |
Most static data used by the allocator, as well as that needed by the rest |
| 79 |
of the garbage collector is stored inside the `_GC_arrays` structure. This |
| 80 |
allows the garbage collector to easily ignore the collectors own data |
| 81 |
structures when it searches for root pointers. Other allocator and collector |
| 82 |
internal data structures are allocated dynamically with `GC_scratch_alloc`. |
| 83 |
The latter does not allow for deallocation, and is therefore used only for |
| 84 |
permanent data structures. |
| 85 |
|
| 86 |
The allocator returns objects of different _kinds_. Different _kinds_ are |
| 87 |
handled somewhat differently by certain parts of the garbage collector. |
| 88 |
Certain kinds are scanned for pointers, others are not. Some may have |
| 89 |
per-object type descriptors that determine pointer locations. Or a specific |
| 90 |
kind may correspond to one specific object layout. Two built-in kinds are |
| 91 |
uncollectible. In spite of that, it is very likely that most C clients of the |
| 92 |
collector currently use at most two kinds: `NORMAL` and `PTRFREE` objects. The |
| 93 |
[GCJ](https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcj/) runtime also makes heavy |
| 94 |
use of a kind (allocated with `GC_gcj_malloc`) that stores type information |
| 95 |
at a known offset in method tables. |
| 96 |
|
| 97 |
The collector uses a two level allocator. A large block is defined to be one |
| 98 |
larger than half of `HBLKSIZE`, which is a power of 2, typically on the order |
| 99 |
of the page size. |
| 100 |
|
| 101 |
Large block sizes are rounded up to the next multiple of `HBLKSIZE` and then |
| 102 |
allocated by `GC_allochblk`. The collector use an approximate best fit |
| 103 |
algorithm by keeping free lists for several large block sizes. The actual |
| 104 |
implementation of `GC_allochblk` is significantly complicated by black-listing |
| 105 |
issues (see below). |
| 106 |
|
| 107 |
Small blocks are allocated in chunks of size `HBLKSIZE`. Each chunk |
| 108 |
is dedicated to only one object size and kind. |
| 109 |
|
| 110 |
The allocator maintains separate free lists for each size and kind of object. |
| 111 |
Associated with each kind is an array of free list pointers, with entry |
| 112 |
`freelist[i]` pointing to a free list of size 'i' objects. Index `i` is |
| 113 |
expressed in granules, which are the minimum allocatable unit, typically 8 or |
| 114 |
16 bytes. The free lists themselves are linked through the first word in each |
| 115 |
object (see `obj_link` macro). |
| 116 |
|
| 117 |
Once a large block is split for use in smaller objects, it can only be used |
| 118 |
for objects of that size, unless the collector discovers a completely empty |
| 119 |
chunk. Completely empty chunks are restored to the appropriate large block |
| 120 |
free list. |
| 121 |
|
| 122 |
In order to avoid allocating blocks for too many distinct object sizes, the |
| 123 |
collector normally does not directly allocate objects of every possible |
| 124 |
request size. Instead, the request is rounded up to one of a smaller number |
| 125 |
of allocated sizes, for which free lists are maintained. The exact allocated |
| 126 |
sizes are computed on demand, but subject to the constraint that they increase |
| 127 |
roughly in geometric progression. Thus objects requested early in the |
| 128 |
execution are likely to be allocated with exactly the requested size, subject |
| 129 |
to alignment constraints. See `GC_init_size_map` for details. |
| 130 |
|
| 131 |
The actual size rounding operation during small object allocation |
| 132 |
is implemented as a table lookup in `GC_size_map` which maps a requested |
| 133 |
allocation size in bytes to a number of granules. |
| 134 |
|
| 135 |
Both collector initialization and computation of allocated sizes are handled |
| 136 |
carefully so that they do not slow down the small object fast allocation path. |
| 137 |
An attempt to allocate before the collector is initialized, or before the |
| 138 |
appropriate `GC_size_map` entry is computed, will take the same path as an |
| 139 |
allocation attempt with an empty free list. This results in a call to the slow |
| 140 |
path code (`GC_generic_malloc_inner`) which performs the appropriate |
| 141 |
initialization checks. |
| 142 |
|
| 143 |
In non-incremental mode, we make a decision about whether to garbage collect |
| 144 |
whenever an allocation would otherwise have failed with the current heap size. |
| 145 |
If the total amount of allocation since the last collection is less than the |
| 146 |
heap size divided by `GC_free_space_divisor`, we try to expand the heap. |
| 147 |
Otherwise, we initiate a garbage collection. This ensures that the amount |
| 148 |
of garbage collection work per allocated byte remains constant. |
| 149 |
|
| 150 |
The above is in fact an oversimplification of the real heap expansion and GC |
| 151 |
triggering heuristic, which adjusts slightly for root size and certain kinds |
| 152 |
of fragmentation. In particular: |
| 153 |
|
| 154 |
* Programs with a large root set size and little live heap memory will |
| 155 |
expand the heap to amortize the cost of scanning the roots. |
| 156 |
* GC actually collects more frequently in non-incremental mode. The large |
| 157 |
block allocator usually refuses to split large heap blocks once the garbage |
| 158 |
collection threshold is reached. This often has the effect of collecting |
| 159 |
well before the heap fills up, thus reducing fragmentation and working set |
| 160 |
size at the expense of GC time. (If the collector is configured not to unmap |
| 161 |
unused pages, GC chooses an intermediate strategy depending on how much |
| 162 |
large object allocation has taken place in the past.) |
| 163 |
* In calculating the amount of allocation since the last collection we give |
| 164 |
partial credit for objects we expect to be explicitly deallocated. Even |
| 165 |
if all objects are explicitly managed, it is often desirable to collect |
| 166 |
on rare occasion, since that is our only mechanism for coalescing completely |
| 167 |
empty chunks. |
| 168 |
|
| 169 |
It has been suggested that this should be adjusted so that we favor expansion |
| 170 |
if the resulting heap still fits into physical memory. In many cases, that |
| 171 |
would no doubt help. But it is tricky to do this in a way that remains robust |
| 172 |
if multiple application are contending for a single pool of physical memory. |
| 173 |
|
| 174 |
## Mark phase |
| 175 |
|
| 176 |
At each collection, the collector marks all objects that are possibly |
| 177 |
reachable from pointer variables. Since it cannot generally tell where pointer |
| 178 |
variables are located, it scans the following _root segments_ for pointers: |
| 179 |
|
| 180 |
* The registers. Depending on the architecture, this may be done using |
| 181 |
assembly code, or by calling a `setjmp`-like function which saves register |
| 182 |
contents on the stack. |
| 183 |
* The stack(s). In the case of a single-threaded application, on most |
| 184 |
platforms this is done by scanning the memory between (an approximation of) |
| 185 |
the current stack pointer and `GC_stackbottom`. (For Intel Itanium, the |
| 186 |
register stack scanned separately.) The `GC_stackbottom` variable is set in |
| 187 |
a highly platform-specific way depending on the appropriate configuration |
| 188 |
information in `gcconfig.h`. Note that the currently active stack needs |
| 189 |
to be scanned carefully, since callee-save registers of client code may |
| 190 |
appear inside collector stack frames, which may change during the mark |
| 191 |
process. This is addressed by scanning some sections of the stack _eagerly_, |
| 192 |
effectively capturing a snapshot at one point in time. |
| 193 |
* Static data region(s). In the simplest case, this is the region between |
| 194 |
`DATASTART` and `DATAEND`, as defined in `gcconfig.h`. However, in most |
| 195 |
cases, this will also involve static data regions associated with dynamic |
| 196 |
libraries. These are identified by the mostly platform-specific code |
| 197 |
in `dyn_load.c`. The marker maintains an explicit stack of memory regions |
| 198 |
that are known to be accessible, but that have not yet been searched for |
| 199 |
contained pointers. Each stack entry contains the starting address of the |
| 200 |
block to be scanned, as well as a descriptor of the block. If no layout |
| 201 |
information is available for the block, then the descriptor is simply |
| 202 |
a length. (For other possibilities, see `gc_mark.h`.) |
| 203 |
|
| 204 |
At the beginning of the mark phase, all root segments (as described above) are |
| 205 |
pushed on the stack by `GC_push_roots`. (Registers and eagerly scanned stack |
| 206 |
sections are processed by pushing the referenced objects instead of the stack |
| 207 |
section itself.) If `ALL_INTERIOR_POINTERS` is not defined, then stack roots |
| 208 |
require special treatment. In this case, the normal marking code ignores |
| 209 |
interior pointers, but `GC_push_all_stack` explicitly checks for interior |
| 210 |
pointers and pushes descriptors for target objects. |
| 211 |
|
| 212 |
The marker is structured to allow incremental marking. Each call |
| 213 |
to `GC_mark_some` performs a small amount of work towards marking the heap. |
| 214 |
It maintains explicit state in the form of `GC_mark_state`, which identifies |
| 215 |
a particular sub-phase. Some other pieces of state, most notably the mark |
| 216 |
stack, identify how much work remains to be done in each sub-phase. The normal |
| 217 |
progression of mark states for a stop-the-world collection is: |
| 218 |
|
| 219 |
1. `MS_INVALID` indicating that there may be accessible unmarked objects. |
| 220 |
In this case `GC_objects_are_marked` will simultaneously be false, so the |
| 221 |
mark state is advanced to |
| 222 |
2. `MS_PUSH_UNCOLLECTABLE` indicating that it suffices to push uncollectible |
| 223 |
objects, roots, and then mark everything reachable from them. `GC_scan_ptr` |
| 224 |
is advanced through the heap until all uncollectible objects are pushed, and |
| 225 |
objects reachable from them are marked. At that point, the next call |
| 226 |
to `GC_mark_some` calls `GC_push_roots` to push the roots. It, then, |
| 227 |
advances the mark state to |
| 228 |
3. `MS_ROOTS_PUSHED` asserting that once the mark stack is empty, all |
| 229 |
reachable objects are marked. Once in this state, we work only on emptying |
| 230 |
the mark stack. Once this is completed, the state changes to |
| 231 |
4. `MS_NONE` indicating that reachable objects are marked. |
| 232 |
|
| 233 |
The core mark routine `GC_mark_from`, is called repeatedly by several of the |
| 234 |
sub-phases when the mark stack starts to fill up. It is also called repeatedly |
| 235 |
in `MS_ROOTS_PUSHED` state to empty the mark stack. The routine is designed |
| 236 |
to only perform a limited amount of marking at each call, so that it can |
| 237 |
also be used by the incremental collector. It is fairly carefully tuned, |
| 238 |
since it usually consumes a large majority of the garbage collection time. |
| 239 |
|
| 240 |
The fact that it performs only a small amount of work per call also allows |
| 241 |
it to be used as the core routine of the parallel marker. In that case it is |
| 242 |
normally invoked on thread-private mark stacks instead of the global mark |
| 243 |
stack. More details can be found [here](scale.md). |
| 244 |
|
| 245 |
The marker correctly handles mark stack overflows. Whenever the mark stack |
| 246 |
overflows, the mark state is reset to `MS_INVALID`. Since there are already |
| 247 |
marked objects in the heap, this eventually forces a complete scan of the |
| 248 |
heap, searching for pointers, during which any unmarked objects referenced |
| 249 |
by marked objects are again pushed on the mark stack. This process is repeated |
| 250 |
until the mark phase completes without a stack overflow. Each time the stack |
| 251 |
overflows, an attempt is made to grow the mark stack. All pieces of the |
| 252 |
collector that push regions onto the mark stack have to be careful to ensure |
| 253 |
forward progress, even in case of repeated mark stack overflows. Every mark |
| 254 |
attempt results in additional marked objects. |
| 255 |
|
| 256 |
Each mark stack entry is processed by examining all candidate pointers in the |
| 257 |
range described by the entry. If the region has no associated type information |
| 258 |
then this typically requires that each 4-byte aligned quantity (8-byte aligned |
| 259 |
if 64-bit pointers) be considered a candidate pointer. |
| 260 |
|
| 261 |
We determine whether a candidate pointer is actually the address of a heap |
| 262 |
block. This is done in the following steps: |
| 263 |
|
| 264 |
* The candidate pointer is checked against rough heap bounds. These heap |
| 265 |
bounds are maintained such that all actual heap objects fall between them. |
| 266 |
In order to facilitate black-listing (see below) we also include address |
| 267 |
regions that the heap is likely to expand into. Most non-pointers fail this |
| 268 |
initial test. |
| 269 |
* The candidate pointer is divided into two pieces; the most significant |
| 270 |
bits identify a `HBLKSIZE`-sized page in the address space, and the least |
| 271 |
significant bits specify an offset within that page. (A hardware page may |
| 272 |
actually consist of multiple such pages. Normally, HBLKSIZE is usually the |
| 273 |
page size divided by a small power of two. Alternatively, if the collector |
| 274 |
is built with `-DLARGE_CONFIG`, such a page may consist of multiple hardware |
| 275 |
pages.) |
| 276 |
* The page address part of the candidate pointer is looked up in |
| 277 |
a [table](tree.md). Each table entry contains either 0, indicating that |
| 278 |
the page is not part of the garbage collected heap, a small integer _n_, |
| 279 |
indicating that the page is part of large object, starting at least _n_ |
| 280 |
pages back, or a pointer to a descriptor for the page. In the first case, |
| 281 |
the candidate pointer is not a true pointer and can be safely ignored. |
| 282 |
In the last two cases, we can obtain a descriptor for the page containing |
| 283 |
the beginning of the object. |
| 284 |
* The starting address of the referenced object is computed. The page |
| 285 |
descriptor contains the size of the object(s) in that page, the object kind, |
| 286 |
and the necessary mark bits for those objects. The size information can be |
| 287 |
used to map the candidate pointer to the object starting address. |
| 288 |
To accelerate this process, the page header also contains a pointer to |
| 289 |
a precomputed map of page offsets to displacements from the beginning of an |
| 290 |
object. The use of this map avoids a potentially slow integer remainder |
| 291 |
operation in computing the object start address. |
| 292 |
* The mark bit for the target object is checked and set. If the object was |
| 293 |
previously unmarked, the object is pushed on the mark stack. The descriptor |
| 294 |
is read from the page descriptor. (This is computed from information stored |
| 295 |
in `GC_obj_kinds` when the page is first allocated.) |
| 296 |
|
| 297 |
At the end of the mark phase, mark bits for left-over free lists are cleared, |
| 298 |
in case a free list was accidentally marked due to a stray pointer. |
| 299 |
|
| 300 |
## Sweep phase |
| 301 |
|
| 302 |
At the end of the mark phase, all blocks in the heap are examined. Unmarked |
| 303 |
large objects are immediately returned to the large object free list. Each |
| 304 |
small object page is checked to see if all mark bits are clear. If so, the |
| 305 |
entire page is returned to the large object free list. Small object pages |
| 306 |
containing some reachable object are queued for later sweeping, unless |
| 307 |
we determine that the page contains very little free space, in which case |
| 308 |
it is not examined further. |
| 309 |
|
| 310 |
This initial sweep pass touches only block headers, not the blocks themselves. |
| 311 |
Thus it does not require significant paging, even if large sections of the |
| 312 |
heap are not in physical memory. |
| 313 |
|
| 314 |
Nonempty small object pages are swept when an allocation attempt encounters |
| 315 |
an empty free list for that object size and kind. Pages for the correct size |
| 316 |
and kind are repeatedly swept until at least one empty block is found. |
| 317 |
Sweeping such a page involves scanning the mark bit array in the page header, |
| 318 |
and building a free list linked through the first words in the objects |
| 319 |
themselves. This does involve touching the appropriate data page, but in most |
| 320 |
cases it will be touched only just before it is used for allocation. Hence any |
| 321 |
paging is essentially unavoidable. |
| 322 |
|
| 323 |
Except in the case of pointer-free objects, we maintain the invariant that any |
| 324 |
object in a small object free list is cleared (except possibly for the link |
| 325 |
field). Thus it becomes the burden of the small object sweep routine to clear |
| 326 |
objects. This has the advantage that we can easily recover from accidentally |
| 327 |
marking a free list, though that could also be handled by other means. The |
| 328 |
collector currently spends a fair amount of time clearing objects, and this |
| 329 |
approach should probably be revisited. In most configurations, we use |
| 330 |
specialized sweep routines to handle common small object sizes. Since |
| 331 |
we allocate one mark bit per word, it becomes easier to examine the relevant |
| 332 |
mark bits if the object size divides the word length evenly. We also suitably |
| 333 |
unroll the inner sweep loop in each case. (It is conceivable that |
| 334 |
profile-based procedure cloning in the compiler could make this unnecessary |
| 335 |
and counterproductive. I know of no existing compiler to which this applies.) |
| 336 |
|
| 337 |
The sweeping of small object pages could be avoided completely at the expense |
| 338 |
of examining mark bits directly in the allocator. This would probably be more |
| 339 |
expensive, since each allocation call would have to reload a large amount |
| 340 |
of state (e.g. next object address to be swept, position in mark bit table) |
| 341 |
before it could do its work. The current scheme keeps the allocator simple and |
| 342 |
allows useful optimizations in the sweeper. |
| 343 |
|
| 344 |
## Finalization |
| 345 |
|
| 346 |
Both `GC_register_disappearing_link` and `GC_register_finalizer` add the |
| 347 |
request to a corresponding hash table. The hash table is allocated out of |
| 348 |
collected memory, but the reference to the finalizable object is hidden from |
| 349 |
the collector. Currently finalization requests are processed non-incrementally |
| 350 |
at the end of a mark cycle. |
| 351 |
|
| 352 |
The collector makes an initial pass over the table of finalizable objects, |
| 353 |
pushing the contents of unmarked objects onto the mark stack. After pushing |
| 354 |
each object, the marker is invoked to mark all objects reachable from it. The |
| 355 |
object itself is not explicitly marked. This assures that objects on which |
| 356 |
a finalizer depends are neither collected nor finalized. |
| 357 |
|
| 358 |
If in the process of marking from an object the object itself becomes marked, |
| 359 |
we have uncovered a cycle involving the object. This usually results in |
| 360 |
a warning from the collector. Such objects are not finalized, since it may be |
| 361 |
unsafe to do so. See the more detailed discussion of |
| 362 |
[finalization semantics](finalization.md). |
| 363 |
|
| 364 |
Any objects remaining unmarked at the end of this process are added to a queue |
| 365 |
of objects whose finalizers can be run. Depending on collector configuration, |
| 366 |
finalizers are dequeued and run either implicitly during allocation calls, |
| 367 |
or explicitly in response to a user request. (Note that the former |
| 368 |
is unfortunately both the default and not generally safe. If finalizers |
| 369 |
perform synchronization, it may result in deadlocks. Nontrivial finalizers |
| 370 |
generally need to perform synchronization, and thus require a different |
| 371 |
collector configuration.) |
| 372 |
|
| 373 |
The collector provides a mechanism for replacing the procedure that is used |
| 374 |
to mark through objects. This is used both to provide support for Java-style |
| 375 |
unordered finalization, and to ignore certain kinds of cycles, e.g. those |
| 376 |
arising from C++ implementations of virtual inheritance. |
| 377 |
|
| 378 |
## Generational Collection and Dirty Bits |
| 379 |
|
| 380 |
We basically use the concurrent and generational GC algorithm described in |
| 381 |
["Mostly Parallel Garbage Collection"](http://www.hboehm.info/gc/papers/pldi91.ps.Z), |
| 382 |
by Boehm, Demers, and Shenker. |
| 383 |
|
| 384 |
The most significant modification is that the collector always starts running |
| 385 |
in the allocating thread. There is no separate garbage collector thread. (If |
| 386 |
parallel GC is enabled, helper threads may also be woken up.) If an allocation |
| 387 |
attempt either requests a large object, or encounters an empty small object |
| 388 |
free list, and notices that there is a collection in progress, it immediately |
| 389 |
performs a small amount of marking work as described above. |
| 390 |
|
| 391 |
This change was made both because we wanted to easily accommodate |
| 392 |
single-threaded environments, and because a separate GC thread requires very |
| 393 |
careful control over the scheduler to prevent the mutator from out-running the |
| 394 |
collector, and hence provoking unneeded heap growth. |
| 395 |
|
| 396 |
In incremental mode, the heap is always expanded when we encounter |
| 397 |
insufficient space for an allocation. Garbage collection is triggered whenever |
| 398 |
we notice that more than `GC_heap_size / 2 * GC_free_space_divisor` bytes |
| 399 |
of allocation have taken place. After `GC_full_freq` minor collections a major |
| 400 |
collection is started. |
| 401 |
|
| 402 |
All collections initially run uninterrupted until a predetermined amount |
| 403 |
of time (50 ms by default) has expired. If this allows the collection |
| 404 |
to complete entirely, we can avoid correcting for data structure modifications |
| 405 |
during the collection. If it does not complete, we return control to the |
| 406 |
mutator, and perform small amounts of additional GC work during those later |
| 407 |
allocations that cannot be satisfied from small object free lists. When |
| 408 |
marking completes, the set of modified pages is retrieved, and we mark once |
| 409 |
again from marked objects on those pages, this time with the mutator stopped. |
| 410 |
|
| 411 |
We keep track of modified pages using one of several distinct mechanisms: |
| 412 |
|
| 413 |
* (`MPROTECT_VDB`) By write-protecting physical pages and catching write |
| 414 |
faults. This is implemented for many Unix-like systems and for Win32. It is |
| 415 |
not possible in a few environments. |
| 416 |
* (`GWW_VDB`) By using the Win32 `GetWriteWatch` function to read dirty |
| 417 |
bits. |
| 418 |
* (`PROC_VDB`) By retrieving dirty bit information from /proc. (Currently |
| 419 |
only Sun's Solaris supports this. Though this is considerably cleaner, |
| 420 |
performance may actually be better with `mprotect` and signals.) |
| 421 |
* (`SOFT_VDB`) By retrieving Linux soft-dirty bit information from /proc. |
| 422 |
* (`PCR_VDB`) By relying on an external dirty bit implementation, in this |
| 423 |
case the one in Xerox PCR. |
| 424 |
* Through explicit mutator cooperation. This enabled by |
| 425 |
`GC_set_manual_vdb_allowed(1)` call, and requires the client code to call |
| 426 |
`GC_ptr_store_and_dirty` or `GC_end_stubborn_change` (followed by a number |
| 427 |
of `GC_reachable_here` calls), and is rarely used. |
| 428 |
* (`DEFAULT_VDB`) By treating all pages as dirty. This is the default |
| 429 |
if none of the other techniques is known to be usable. (Practical only for |
| 430 |
testing.) |
| 431 |
|
| 432 |
## Black-listing |
| 433 |
|
| 434 |
The collector implements _black-listing_ of pages, as described in |
| 435 |
["Space Efficient Conservative Collection", PLDI'93](http://dl.acm.org/citation.cfm?doid=155090.155109) |
| 436 |
by Boehm, also available |
| 437 |
[here](https://www.cs.rice.edu/~javaplt/311/Readings/pldi93.pdf). |
| 438 |
|
| 439 |
During the mark phase, the collector tracks _near misses_, i.e. attempts |
| 440 |
to follow a _pointer_ to just outside the garbage-collected heap, or to |
| 441 |
a currently unallocated page inside the heap. Pages that have been the targets |
| 442 |
of such near misses are likely to be the targets of misidentified _pointers_ |
| 443 |
in the future. To minimize the future damage caused by such misidentification, |
| 444 |
they will be allocated only to small pointer-free objects. |
| 445 |
|
| 446 |
The collector understands two different kinds of black-listing. A page may be |
| 447 |
black listed for interior pointer references (`GC_add_to_black_list_stack`), |
| 448 |
if it was the target of a near miss from a location that requires interior |
| 449 |
pointer recognition, e.g. the stack, or the heap if `GC_all_interior_pointers` |
| 450 |
is set. In this case, we also avoid allocating large blocks that include this |
| 451 |
page. |
| 452 |
|
| 453 |
If the near miss came from a source that did not require interior pointer |
| 454 |
recognition, it is black-listed with `GC_add_to_black_list_normal`. A page |
| 455 |
black-listed in this way may appear inside a large object, so long as it is |
| 456 |
not the first page of a large object. |
| 457 |
|
| 458 |
The `GC_allochblk` routine respects black-listing when assigning a block to |
| 459 |
a particular object kind and size. It occasionally drops (i.e. allocates and |
| 460 |
forgets) blocks that are completely black-listed in order to avoid excessively |
| 461 |
long large block free lists containing only unusable blocks. This would |
| 462 |
otherwise become an issue if there is low demand for small pointer-free |
| 463 |
objects. |
| 464 |
|
| 465 |
## Thread support |
| 466 |
|
| 467 |
We support several different threading models. Unfortunately Pthreads, the |
| 468 |
only reasonably well standardized thread model, supports too narrow |
| 469 |
an interface for conservative garbage collection. There appears to be no |
| 470 |
completely portable way to allow the collector to coexist with various |
| 471 |
Pthreads implementations. Hence we currently support only the more common |
| 472 |
Pthreads implementations. |
| 473 |
|
| 474 |
In particular, it is very difficult for the collector to stop all other |
| 475 |
threads in the system and examine the register contents. This is currently |
| 476 |
accomplished with very different mechanisms for some Pthreads implementations. |
| 477 |
For Linux/HPUX/OSF1, Solaris and Irix it sends signals to individual Pthreads |
| 478 |
and has them wait in the signal handler. |
| 479 |
|
| 480 |
The Linux and Irix implementations use only documented Pthreads calls, but |
| 481 |
rely on extensions to their semantics. The Linux implementation |
| 482 |
`pthread_stop_world.c` relies on only very mild extensions to the pthreads |
| 483 |
semantics, and already supports a large number of other Unix-like pthreads |
| 484 |
implementations. Our goal is to make this the only pthread support in the |
| 485 |
collector. |
| 486 |
|
| 487 |
All implementations must intercept thread creation and a few other |
| 488 |
thread-specific calls to allow enumeration of threads and location of thread |
| 489 |
stacks. This is current accomplished with `#define`'s in `gc.h` (really |
| 490 |
`gc_pthread_redirects.h`), or optionally by using `ld`'s function call |
| 491 |
wrapping mechanism under Linux. |
| 492 |
|
| 493 |
The collector support several facilities to enhance the processor-scalability |
| 494 |
and thread performance of the collector. These are discussed in more detail |
| 495 |
[here](scale.md). We briefly outline the data approach to thread-local |
| 496 |
allocation in the next section. |
| 497 |
|
| 498 |
## Thread-local allocation |
| 499 |
|
| 500 |
If thread-local allocation is enabled (which is true in the default |
| 501 |
configuration for most supported platforms), the collector keeps separate |
| 502 |
arrays of free lists for each thread. |
| 503 |
|
| 504 |
The free list arrays associated with each thread are only used to satisfy |
| 505 |
requests for objects that are both very small, and belong to one of a small |
| 506 |
number of well-known kinds. These include _normal_, pointer-free, _gcj_ and |
| 507 |
_disclaim_ objects. |
| 508 |
|
| 509 |
Thread-local free list entries contain either a pointer to the first element |
| 510 |
of a free list, or they contain a counter of the number of allocation |
| 511 |
granules, corresponding to objects of this size, allocated so far. Initially |
| 512 |
they contain the value one, i.e. a small counter value. |
| 513 |
|
| 514 |
Thread-local allocation goes directly through the global allocator if the |
| 515 |
object is of a size or kind not covered by the local free lists. |
| 516 |
|
| 517 |
If there is an appropriate local free list, the allocator checks whether |
| 518 |
it contains a sufficiently small counter value. If so, the counter is simply |
| 519 |
incremented by a value, and the global allocator is used. In this way, |
| 520 |
the initial few allocations of a given size bypass the local allocator. |
| 521 |
A thread that only allocates a handful of objects of a given size will not |
| 522 |
build up its own free list for that size. This avoids wasting space for |
| 523 |
unpopular objects sizes or kinds. |
| 524 |
|
| 525 |
Once the counter passes a threshold, `GC_malloc_many` is called to allocate |
| 526 |
roughly `HBLKSIZE` space and put it on the corresponding local free list. |
| 527 |
Further allocations of that size and kind then use this free list, and no |
| 528 |
longer need to acquire the allocation lock. The allocation procedure |
| 529 |
is otherwise similar to the global free lists. The local free lists are also |
| 530 |
linked using the first word in the object. In most cases this means they |
| 531 |
require considerably less time. |
| 532 |
|
| 533 |
Local free lists are treated by most of the rest of the collector as though |
| 534 |
they were in-use reachable data. This requires some care, since pointer-free |
| 535 |
objects are not normally traced, and hence a special tracing procedure |
| 536 |
is required to mark all objects on pointer-free and gcj local free lists. |
| 537 |
|
| 538 |
On thread exit, any remaining thread-local free list entries are transferred |
| 539 |
back to the global free list. |
| 540 |
|
| 541 |
Note that if the collector is configured for thread-local allocation (the |
| 542 |
default for most platforms), `GC_malloc` and friends only use thread-local |
| 543 |
allocation. |
| 544 |
|
| 545 |
For some more details see [here](scale.md), and the technical report entitled |
| 546 |
["Fast Multiprocessor Memory Allocation and Garbage Collection"](http://www.hpl.hp.com/techreports/2000/HPL-2000-165.html). |