638
edits
Tamarin::MMgc: Difference between revisions
→Mark consistency
| Line 505: | Line 505: | ||
=== Mark consistency === | === Mark consistency === | ||
A correct collector never deletes a live object (duh). In order to be correct we must account for a new or unmarked object being stored into an object we've already marked. In implementation terms this means a new or unmarked object is stored in an object that has already been processed by the marking algorithm and is no longer in the queue. Unless we do something we will delete this object and leave a dangling pointer to it in its | A correct collector never deletes a live object (duh). In order to be correct we must account for a new or unmarked object being stored into an object we've already marked. In implementation terms this means a new or unmarked object is stored in an object that has already been processed by the marking algorithm and is no longer in the queue. Unless we do something we will delete this object and leave a dangling pointer to it in its referent. | ||
There are a couple | There are a couple different techniques for this, but the most popular one based on some research uses a tri-color algorithm with write barriers. Every object has 3 states: black, gray and white. | ||
{| | {| | ||
| Line 515: | Line 515: | ||
|- | |- | ||
| [[Image:Tamarin-MMGC-Gcgray.png]] | | [[Image:Tamarin-MMGC-Gcgray.png]] | ||
| ''' | | '''Gray''' means the object is in the work queue but not yet marked | ||
|- | |- | ||
| [[Image:Tamarin-MMGC-Gcwhite.png]] | | [[Image:Tamarin-MMGC-Gcwhite.png]] | ||
| Line 521: | Line 521: | ||
|} | |} | ||
The first increment will push all the roots on to the queue, thus after this step all the roots are | The first increment will push all the roots on to the queue, thus after this step all the roots are gray and everything else is white. As the queue is processed all live objects go through two steps, from gray to black and white to gray. Whenever a pointer to a white object is written to a black object we have to intercept that write and remember to go back and put the white object in the work queue, that's what a write barrier does. The other scenarios we don't care about: | ||
# | # Gray written to Black/Gray/White - since the object is gray its on the queue and will be marked before we sweep | ||
# White written to | # White written to Gray - the white object will be marked as reachable when the gray object is marked | ||
# White written to White - the referant will either eventually become | # White written to White - the referant will either eventually become gray if its reachable or not in which case both objects will get marked | ||
# Black written to Black/ | # Black written to Black/Gray/White - its black, its already been marked | ||
So a write barrier needs to be inserted anywhere we could possibly store a pointer to a white object into a black object. In practice this means: | So a write barrier needs to be inserted anywhere we could possibly store a pointer to a white object into a black object. In practice this means: | ||