1 # Copyright (C) 2001-2009, Parrot Foundation.
4 =head1 PDD 9: Garbage Collection Subsystem
8 This PDD specifies Parrot's garbage collection subsystems.
16 =head3 Garbage collection (GC)
18 Garbage collection is a process of freeing up memory that is no longer used by
19 the interpreter, by determining which objects will not be referenced again and
24 All reachable objects are marked as alive, first marking a root set, and then
25 recursively marking objects reachable from other reachable objects. Objects
26 not reached are considered dead. After collection, all objects are reset to
27 unmarked, and the process starts again.
31 Instead of a simple separation of marked (as live) and unmarked (dead), the
32 object set is divided into three parts: white, gray, and black. The white
33 objects are presumed dead. The gray objects have been marked as live by some
34 other object, but haven't yet marked the objects they refer to. The black
35 objects are live, and have marked all objects they directly refer to.
37 In the initial run, all objects start as white and the root set is marked
38 gray. The marking process changes white objects to gray (marking them from
39 another gray object), and gray objects to black (when all objects they refer
40 to are marked). When the gray set is empty, all live objects have been marked
41 and the white set can be collected. After a collection run, all black objects
42 are reset to white, the root set to gray, and the process begins again.
44 The advantage of a tri-color mark over a simple mark is that it can be broken
49 In this GC scheme, after all reachable objects are marked as live, a sweep
50 through the object arenas collects all unmarked objects.
52 =head3 Copying collection
54 In this scheme, live objects are copied into a new memory region. The entire
55 old memory region can then be reclaimed.
57 =head3 Compacting collection
59 In this scheme, live objects are moved closer together, eliminating fragments
60 of free space between live objects. This compaction makes later allocation of
61 new objects faster, since the allocator doesn't have to scan for fragments of
64 =head3 Reference counting
66 In this scheme, all objects have a count of how often they are referred to by
67 other objects. If that count reaches zero, the object's memory can be
68 reclaimed. This scheme doesn't cope well with reference loops--loops of dead
69 objects, all referencing one another but not reachable from elsewhere, never
74 A common disadvantage of a simple mark implementation is that the entire
75 system (including all threads that use the same memory pools) must be
76 suspended while the whole memory set is examined during marking and
77 collection. Normal operation continues only after the whole GC cycle is
78 performed. This can lead to arbitrarily long pauses during program execution.
82 Rather than suspending the system for marking and collection, GC is done in
83 small increments intermittent with normal program operation. Some
84 implementations perform the marking as part of ordinary object access.
88 The pauses caused by GC don't exceed a certain limit.
92 The object space is divided between a young generation (short-lived
93 temporaries) and one or more old generations. Only young generations are reset
94 to white (presumed dead). Avoiding scanning the old generations repeatedly can
95 considerably speed up GC.
97 Generational collection does not guarantee that all unreachable objects will
98 be reclaimed, so in large systems it is sometimes combined with a
99 mark-and-sweep or copying collection scheme, one for light collection runs
100 performed frequently, and the other for more complete runs performed rarely.
104 GC marking and collection runs as a separate thread, sometimes with multiple
105 threads participating in GC. On a multi-processor machine, concurrent GC may
116 =item - Parrot provides swappable garbage collection schemes. The GC scheme
117 can be selected at configure/compile time. The GC scheme cannot be changed
118 on-the-fly at runtime, but in the future may be selected with a command-line
119 option at execution time.
121 =item - All live PMCs must be reachable from the root set of objects in the
124 =item - Garbage collection must be safe for objects shared across multiple
125 interpreters/threads.
127 =item - The phrase "dead object detection" and abbreviation "DOD" are
132 =head2 Implementation
134 Parrot supports pluggable garbage collection cores, so ultimately any garbage
135 collection model devised can run on it. However, different GC models are more
136 or less appropriate for different application areas. The current default
137 stop-the-world mark-and-sweep model is not well suited for concurrent/parallel
138 execution. We will keep the simple mark-and-sweep implementation, but it will
139 no longer be primary.
141 Parrot really has two independent GC models, one used for objects (PMCs) and
142 the other used for buffers (including strings). The core difference is that
143 buffers cannot contain other buffers, so incremental marking is unnecessary.
144 Currently, PMCs are not allowed to move after creation, so the GC model used
145 there is not copying nor compacting.
147 The primary GC model for PMCs, at least for the 1.0 release, will use a
148 tri-color incremental marking scheme, combined with a concurrent sweep scheme.
152 A GC run is composed of two distinct operations: Finding objects which are
153 dead (the "trace" or "mark" phase) and freeing dead objects for later reuse
154 (the "sweep" phase). The sweep phase is also known as the collection phase.
155 The trace phase is less frequently known as the "dead object detection" phase.
156 The use of the term "dead object detection" and its acronym DOD has been
159 =head3 Initial Marking
161 Each PMC has a C<flags> member which, among other things, facilitates garbage
162 collection. At the beginning of the mark phase, the C<PObj_is_live_FLAG> and
163 C<PObj_is_fully_marked_FLAG> are both unset, which flags the PMC as presumed
164 dead (white). The initial mark phase of the collection cycle goes through each
165 PMC in the root set and sets the C<PObj_is_live_FLAG> bit in the C<flags>
166 member (the PMC is gray). It does not set the C<PObj_is_fully_marked_FLAG>
167 bit (changing the PMC to black), because in the initial mark, the PMCs or
168 buffers contained by a PMC are not marked. It also appends the PMC to the end
169 of a list used for further marking. However, if the PMC has already been
170 marked as black, the current end of list is returned (instead of appending the
171 already processed PMC) to prevent endless looping.
173 The fourth combination of the two flags, where C<PObj_is_live_FLAG> is unset
174 and C<PObj_is_fully_marked_FLAG> is set, is reserved for PMCs of an older
175 generation not actively participating in the GC run.
177 The root set for the initial marking phase includes the following core storage
184 =item System stack and processor registers
186 =item Current PMC register set
190 =item PMC register stack
194 =head3 Incremental Marking
196 After the root set of PMCs have been marked, a series of incremental mark runs
197 are performed. These may be performed frequently, between other operations.
198 The incremental mark runs work to move gray PMCs to black. They take a PMC
199 from the list for further marking, mark any PMCs or buffers it contains as
200 gray (the C<PObj_is_live_FLAG> is set and the C<PObj_is_fully_marked_FLAG> is
201 left unset), and add the contained PMCs or buffers to the list for further
202 marking. If the PMC has a custom mark function in its vtable, it is called at
205 After all contained PMCs or buffers have been marked, the PMC itself is marked
206 as black (the C<PObj_is_live_FLAG> and C<PObj_is_fully_marked_FLAG> are both
207 set). A limit may be placed on the number of PMCs handled in each incremental
210 =head3 Buffer Marking
212 The initial marking phase also marks the root set of buffers. Because buffers
213 cannot contain other buffers, they are immediately marked as black and not
214 added to the list for further marking. Because PMCs may contain buffers, the
215 buffer collection phase can't run until the incremental marking of PMCs is
218 The root set for buffers includes the following locations:
222 =item Current String register set
224 =item String register set stack
230 Once a buffer is found to be live, the C<flags> member of the buffer structure
231 has the C<PObj_live_FLAG> and C<PObj_is_fully_marked_FLAG> bits set.
235 When the list for further marking is empty (all gray PMCs have changed to
236 black), the collection stage is started. First, PMCs are collected, followed
237 by buffers. In both cases (PMC and buffer), the "live" and "fully_marked"
238 flags are reset after examination for reclamation.
240 =head4 Collecting PMCs
242 To collect PMCs, each PMC arena is examined from the most recently created
243 backwards. Each PMC is examined to see if it is live, already on the free
244 list, or constant. If it is not, then it is added to the free list and marked
245 as being on the free list with the C<PObj_on_free_list_FLAG>.
248 Are the PMCs in the arena examined back-to-front as well? How about Buffers?
249 Order of destruction can be important.
251 =head4 Collecting buffers
253 To collect buffers, each Buffer arena is examined from the most recently
254 created backwards. If the buffer is not live, not already on the free list
255 and it is not a constant or copy on write, then it is added to the free pool
256 for reuse and marked with the C<PObj_on_free_list_FLAG>.
258 =head4 Concurrent collection
260 For the most part, the variable sets between concurrent tasks don't interact.
261 They have independent root sets and don't require information on memory usage
262 from other tasks before performing a collection phase. In Parrot, tasks tend
263 to be short-lived, and their variables can be considered young generations
264 from a generational GC perspective. Because of this, a full heavyweight task
265 will maintain its own small memory pools, quickly born and quickly dying.
267 Shared variables, on the other hand, do require information from multiple
268 concurrent tasks before they can be collected. Because of this, they live in
269 the parent interpreter's global pools, and can only be collected after all
270 concurrent tasks have completed a full mark phase without marking the shared
271 variable as live. Because GC in the concurrent tasks happens incrementally
272 between operations, a full collection of the shared variables can happen
273 lazily, and does not require a stop-the-world sweep through all concurrent
274 tasks simultaneously.
276 =head3 Internal Structures
278 The different GC cores are independent, but they share some code and
279 resources. The arena structures and arena creation routines are common across
280 most GC cores, and some GC cores also share mark routines.
282 The main interpreter structure has an mem_pools member, which is a pointer to
283 an Memory_Pools struct.
285 =head4 The Memory_Pools structure
287 The C<Memory_Pools> structure contains pointers to a variety of memory pools,
288 each used for a specific purpose. Two are Var_Size_Pool pointers (memory_pool,
289 constant_string_pool), and six are Fixed_Size_Pool structures (pmc_pool,
290 constant_pmc_pool, constant_string_header_pool).
292 The C<Memory_Pools> structure holds function pointers for the core defined
293 interface of the currently active GC subsystem: C<init_pool>, C<do_gc_mark>,
294 C<finalize_gc_system>. It holds various accounting information for the GC
295 subsystem, including how many GC runs have been completed, amount of memory
296 allocated since the last run, and total memory allocated. This accounting
297 information is updated by the GC system. The current block level for GC mark
298 and sweep phases is stored in the C<Memory_Pools> structure.
299 (See L<Blocking GC>.)
301 The pointer C<void *gc_private> is reserved for use by the currently active GC
302 subsystem (with freedom for variation between GC implementations).
304 =head4 The Var_Size_Pool structure
306 The C<Var_Size_Pool> structure is a simple memory pool. It contains a pointer
307 to the top block of the allocated pool, the total allocated size of the pool,
308 the block size, and some details on the reclamation characteristics of the
311 =head4 The Fixed_Size_Pool structure
313 The C<Fixed_Size_Pool> structure is a richer memory pool for object
314 allocation. It tracks details like the number of allocated and free objects
315 in the pool, a list of free objects, and for the generational GC
316 implementation maintains linked lists of white, black, and gray PMCs. It
317 contains a pointer to a simple C<Var_Size_Pool> (the base storage of the
318 pool). It holds function pointers for adding and retrieving free objects in
319 the pool, and for allocating objects.
323 Currently only one GC system is active at a time, selected at configure or
324 compile time. Future versions will support switching GC systems at
325 execution-time to accommodate different work loads.
328 Does "execution-time" mean "before starting a runcore" or "at some point after
331 Each GC core provides a standard interface for interaction with the core.
333 =head4 Initialization
335 Each GC core declares an initialization routine as a function pointer,
336 which is installed in F<src/memory.c:mem_setup_allocator()> after
337 creating C<mem_pools> in the interpreter struct.
341 =item C<void Parrot_gc_XXX_init(Interp *)>
343 A routine to initialize the GC system named C<XXX>.
345 The initialization code is responsible for the creation of the header pools
346 and fills the function pointer slots in the interpreter's C<mem_pools>
351 =head4 Memory_Pools structure function pointers
353 Each GC system declares 3 function pointers, stored in the Memory_Pools
358 =item C<void (*init_gc_system) (Interp *)>
360 Initialize the GC system. Install the additional function pointers into
361 the Memory_Pools structure, and prepare any private storage to be used by
362 the GC in the Memory_Pools->gc_private field.
364 =item C<void (*do_gc_mark) (Interp *, int flags)>
366 Trigger or perform a GC run. With an incremental GC core, this may only
367 start/continue a partial mark phase or sweep phase, rather than performing an
368 entire run from start to finish. It may take several calls to C<do_gc_mark> in
369 order to complete an entire run of an incremental collector.
371 For a concurrent collector, calls to this function may activate a concurrent
372 collection thread or, if such a thread is already running, do nothing at all.
374 The C<do_gc_mark> function is called from the C<Parrot_gc_mark_and_sweep>
375 function, and should not usually be called directly.
383 Run the GC normally, including the trace and the sweep phases, if applicable.
384 Incremental GCs will likely only run one portion of the complete GC run, and
385 repeated calls would be required for a complete run. A complete trace of all
386 system areas is not required.
388 =item GC_trace_normal | GC_trace_stack_FLAG
390 Run a normal GC trace cycle, at least. This is typically called when there
391 is a resource shortage in the buffer memory pools before the sweep phase is
392 run. The processor registers and any other system areas have to be traced too.
394 Behavior is determined by the GC implementation, and might or might not
395 actually run a full GC cycle. If the system is an incremental GC, it might
396 do nothing depending on the current state of the GC. In an incremental GC, if
397 the GC is already past the trace phase it may opt to do nothing and return
398 immediately. A copying collector may choose to run a mark phase if it hasn't
399 yet, to prevent the unnecessary copying of dead objects later on.
403 Do a timely destruction run. The goal is either to detect all objects that
404 need timely destruction or to do a full collection. This is called from the
405 Parrot run-loop, typically when a lexical scope is exited and the local
406 variables in that scope need to be cleaned up. Many types of PMC objects, such
407 as line-buffered IO PMCs rely on this behavior for proper operation.
409 No system areas have to be traced.
413 Finalize and destroy all living PMCs. This is called during interpreter
414 destruction. The GC subsystem must clear the live state of all objects
415 and perform a sweep in the PMC header pool, so that destructors and finalizers
416 get called. PMCs which have custom destructors rely on this behavior for
421 =item C<void (*finalize_gc_system) (Interp *)>
423 Called during interpreter destruction. Free used resources and memory pools.
424 All PMCs must be swept, and PMCs with custom destroy VTABLE methods must have
427 =item C<void (*init_pool) (Interp *, Fixed_Size_Pool *)>
429 Initialize the given pool. Populates the C<Fixed_Size_Pool> structure with
430 initial values, and sets a series of function pointers for working with the
431 pool. The function pointers used with the pool are discussed next.
435 =head4 Fixed_Size_Pool function pointers
437 Each GC core defines 4 function pointers stored in the C<Fixed_Size_Pool>
438 structures. These function pointers are used throughout Parrot to implement
439 basic behaviors for the pool.
443 =item C<PObj * (*get_free_object) (Interp *, Fixed_Size_Pool*)>
445 Get a free object from the pool. This function returns one free object from
446 the given pool and removes that object from the pool's free list. PObject
447 flags are returned clear, except flags that are used by the garbage collector
448 itself, if any. If the pool is a buffer header pool all other object memory
451 =item C<void (*add_free_object) (Interp *, Fixed_Size_Pool *, PObj *);>
453 Add a freed object to the pool's free list. This function is most often called
454 internally to the GC itself to add items to the free list after a sweep, or
455 when a new arena is created to add the new items to the free list. It does
456 not need to be used in this way, however.
458 =item C<void (*alloc_objects) (Interp *, Fixed_Size_Pool *);>
460 Allocate a new arena of objects for the pool. Initialize the new arena and add
461 all new objects to the pool's free list. Some collectors implement a growth
462 factor which increases the size of each new allocated arena.
464 =item C<void (*more_objects) (Interp *, Fixed_Size_Pool *);>
466 Reallocation for additional objects. It has the same signature as
467 C<alloc_objects>, and in some GC cores the same function pointer is used for
468 both. In some GC cores, C<more_objects> may do a GC run in an attempt to free
469 existing objects without having to allocate new ones. This function may also
470 call C<pool->alloc_objects> internally, to allocate objects if a GC run fails
471 to free any old objects.
477 Each GC core has to provide the following macros. All of these might be
478 defined empty, for GC cores which do not use them.
482 =item C<GC_WRITE_BARRIER(Interp *, PMC *agg, PMC *old, PMC *new)>
484 This macro is invoked when in aggregate C<agg> the element C<old> is getting
485 overwritten by C<new>. Either C<old>, C<new>, or both may be NULL.
487 =item C<GC_WRITE_BARRIER_KEY(Interp *, PMC *agg, PMC *old, PObj
488 *old_key, PMC *new, PObj *new_key)>
490 Similar to C<GC_WRITE_BARRIER>. Invoked when a hash key C<new_key> is
491 inserted into hash C<agg> with value C<new>, possibly replacing a key/value
492 pair C<old_key> and C<old>, respectively. Any of C<old>, C<old_key>, C<new>
493 or C<new_key> might be C<NULL>.
499 Being able to block GC is important, so newly allocated Buffers or PMCs won't
500 be collected before they're attached to the live tree. Parrot provides locking
501 mechanisms to prevent the GC from taking certain actions, such as marking
502 or sweeping. GC block functions are nesting, and multiple calls to a lock
503 function requires the same number of calls to the corresponding unlock
504 function in order to operate the GC normally again. The following functions
505 are used to block the GC from performing certain actions:
509 =item Parrot_block_GC_mark(Interp *interpreter)
511 Block the GC mark phase for the passed interpreter, but do not block the sweep
512 phase. In a stop-the-world collector, this will prevent the entire collection
513 run, but in an incremental collector this will only block if the GC is in the
516 =item Parrot_block_GC_sweep(Interp *interpreter)
518 Block the GC sweep phase for the passed interpreter, but do not block the
521 =item Parrot_unblock_GC_mark(Interp *interpreter)
523 Unblock the GC mark phase for the passed interpreter, but do not unblock a
524 blocked sweep phase, if it is blocked using C<Parrot_block_GC_sweep>.
526 =item Parrot_unblock_GC_sweep(Interp *interpreter)
528 Unblock the GC sweep phase for the passed interpreter, but do not unblock the
529 mark phase if it has been blocked by C<Parrot_block_GC_mark>.
531 =item Parrot_is_blocked_GC_mark(Interp *interpreter)
533 Test whether the mark phase has been blocked. Notice that the sweep phase can
534 be locked independently and cannot be determined using this function.
536 =item Parrot_is_blocked_GC_sweep(Interp *interpreter)
538 Test whether the sweep phase has been blocked. Notice that the mark phase can
539 be locked independently and cannot be determined using this function.
543 =head3 PMC/Buffer API
547 For PMCs and Buffers to be collected properly, you must set the appropriate
548 flags on them. Directly manipulating these flags is not recommended because
549 the exact values can be changed over time. A series of macros have been
550 created in F<include/parrot/pobject.h> that set and check for these flags.
551 Always use these provided macros when you need to test or set these flags.
555 =item PObj_custom_destroy_FLAG
557 The PMC has some sort of active destructor, and will have that destructor
558 called when the PMC is destroyed. The destructor is typically called from
559 within C<src/gc/api.c:Parrot_gc_free_pmc>.
561 =item PObj_custom_mark_FLAG
563 The C<mark> vtable slot will be called during the GC mark phase. The mark
564 function must call C<Parrot_gc_mark_PObj_alive> for all non-NULL objects
565 (Buffers and PMCs) that PMC refers to. This flag is typically tested and the
566 custom mark VTABLE method called from C<src/gc/api.c:mark_special>.
568 =item PObj_external_FLAG
570 Set if the buffer points to memory that came from outside Parrot's memory
573 =item PObj_sysmem_FLAG
575 Set if the memory came from the system malloc. When the buffer is considered
576 dead, the memory will be freed back to the system.
580 The buffer's memory is copy on write. Any changes to the buffer must first
581 have the buffer's memory copied. The COW flag should then be removed.
585 The following flags can be used by the GC subsystem:
591 The system considers the object to be alive for collection purposes. Objects
592 with this flag set should never be collected, freed, destroyed, or put on the
595 =item PObj_on_free_list_FLAG
597 The object is unused, and on the free list for later allocation.
599 =item PObj_custom_GC_FLAG
601 Mark the buffer as needing GC.
615 "Uniprocessor Garbage Collection Techniques"
616 http://www.cs.rice.edu/~javaplt/311/Readings/wilson92uniprocessor.pdf
618 "A unified theory of garbage collection":
619 http://portal.acm.org/citation.cfm?id=1028982
621 "Scalable Locality-Conscious Multithreaded Memory Allocation":
622 http://people.cs.vt.edu/~scschnei/papers/ismm06.pdf
624 "Parallel and concurrent garbage collectors":
625 http://chaoticjava.com/posts/parallel-and-concurrent-garbage-collectors/
627 "Region-Based Memory Management":
628 http://www.irisa.fr/prive/talpin/papers/ic97.pdf
630 Dan's first musings on the GC subsystem:
631 http://www.mail-archive.com/perl6-all@perl.org/msg14072.html
633 Semi-timely and ordered destruction:
634 http://www.sidhe.org/~dan/blog/archives/000199.html
642 vim: expandtab shiftwidth=4: