The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

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

Global stash
System stack
Current PMC register set
Stashes
PMC register stack
General/User stack

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

Current String register set
String register set stack
General/User stack
Control stack

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 parrot-porters and old perl6-internals mailing list which contains numerous discussions on the Parrot garbage collector.