NAME
docs/dev/dod.pod - Dead object detection (DOD)
Overview
The DOD code performs dead object detection and reclamation, thereby implementing a mark and copy garbage collector. The official garbage collection PDD is PDD 9 and is located in the docs/pdds directory of the parrot distribution. This Pod file is only meant to describe the current state of the code and is not meant to replace a thorough understanding of PDD 9.
Data Structures and Algorithms
Marking (pass 1)
Each PMC has a flags member which, among other things, is used to facilitate garbage collection. The mark phase of the collection cycle goes though each PMC and sets the PMC_live_FLAG bit in the flags member. It also appends the PMC to the end of a list used for further (pass 2) marking. However, if the PMC has already been marked as used, the current end of list is returned (instead of appending the already processed PMC) to prevent endless looping.
PMCs are detected in the following order
Marking PMCs(pass 2)
After all of the PMCs have been marked, then they are traversed a second time. This second phase looks for aggregate PMCs. In other words, some PMCs contain other PMCs, buffers, or buffers of PMCs. The second phase looks for those aggregate PMCs and marks the contained PMCs or buffers thereby ensuring they will not be collected. Furthermore, if the PMC has a custom mark function in its vtable, it is called at this point. It is important to note that those PMCs marked by this second phase will be added to the end of the traversal list in case they, themselves, have any aggregate PMCs that need to be marked.
Marking Buffers
After all PMCs have been marked, the non PMC buffers are examined. They are examined in the following order
Once a buffer is found to be live, the flags member of the buffer structure has the BUFFER_live_FLAG bit set on.
Collection
After all of the buffers and PMCs in use have been marked live, the collection stage is started. First, PMCs are collected, followed by buffers.
- Collecting PMCs
-
To collect PMCs, each PMC arena is examined, from the most recently created backwards. Each PMC is examined to see if it is live, already on the free list, or constant. If it is not, then it is added to the free list and marked as being already on the free list.
- Collecting buffers
-
To collect buffers, each Buffer arena is examined from the most recently created backwards. If the buffer is not live, not already on the free list and it is not a constant or copy on write, then it is added to the free pool for reuse.
In both cases (PMC and buffer), the live flag is reset after examination for reclamation.
History
Initial Version by Mike Lambert on 2002.05.27
Notes
The buffer_lives function can be found in dod.h The add_to_free_pool function can be found in headers.h
References
There are a number of references available for Garbage Collection. For example:
- Garbage Collection Algorithms for Automatic Dynamic Memory Management by Jones and Lins
- http://www.cs.utexas.edu/users/oops/papers.html
Also, the http://dev.perl.org web site has an archive of the perl6-internals mailing list which contains numerous discussions on the Parrot garbage collector.