Welcome back. 1
In the previous lecture we have discussed the Tri-color abstraction, which is used to maintain the work 2
of the Incremental and Concurrent collectors. 3
We also mentioned that the actual correctness in this case is achieved through the GC barriers. 4
Let's again recall two sufficient conditions, which may break heap invariants in case of the Concurrent 5
and Incremental collectors, when a Collector may incorrectly reclaim an alive object. 6
So the first condition is: there is some Black object which directly points to a White object 7
And there is no path from any Gray object to this White object. Since the collector after interruption always 8
continues its analysis from the set of the Gray objects 9
this pointer from A to D is illegal, because the Black objects are not considered after interruption and 10
the D object, being White, will be incorrectly removed. 11
Notice that the pointer from A to C might actually be a legal Black-White pointer, since there is a path 12
from a Gray object here. 13
We have mentioned previously usage of the GC barriers in the Generational collector 14
And 15
today we'll be focusing specifically on the Incremental and Concurrent barriers used today in practice. 16
So these are: the Snapshot-at-Beginning. Incremental update. 17
Baker's Copying method, and Brook's method. 18
Okay, so let's begin. Now, before diving into the actual algorithms, we should first define what a barrier is 19
and to see what kinds of barriers are used today in garbage collectors. 20
Now, a Barrier is an extra fragment of code, which is executed on certain Mutator events. 21
What are those events? 22
Well, these are the basic: "Read pointer" and "Store pointer" operations. That is every time when we access 23
some pointer for reading or writing, our barrier code is called. 24
With this the barriers divided further into the Read barriers, which are executed on the reading 25
a pointer, and the Write barriers executed on the writing a pointer. And usually the Read barriers are 26
used in moving collectors (and recall these are the Mark-Compact, and the Copying collector) and the Write 27
barriers are mostly used in the non-moving collectors 28
for example, Concurrent Mark-Sweep collector (or CMS). Although this depends on the implementation and 29
the Write barrier can be used in the moving collector as well. 30
Okay so let's start from the non-moving collectors first. And the first algorithm we're going to consider 31
is the Snapshot-at-beginning. 32
Okay let's take again our object graph, and as we can see here 33
Collector has fully handled the object A, since is Black, and also knows, that the object B is alive, since 34
it's Gray. Collector doesn't know anything yet about children of the object B. The collector was 35
interrupted by the Mutator. And when the Collector will restore its cycle, it will start exactly from 36
the set of Gray objects (in this case is the only object B). The Black objects, that is the object A 37
in this case will not be considered. Let's reproduce our problem situation again here, when the Mutator 38
added the pointer from A to D, and B has changed its pointer from D to E. The Collector comes 39
into play again, and since the object A, being Black, will not be considered, the White object D will be 40
incorrectly reclaimed as we said. Now, the Snapshot-at-Beginning algorithm handles this situation through 41
the Write barrier, when a pointer to a White object is changed to point to another object, like in this 42
case when the pointer B->D is changed to B->E. 43
Notice that the Snapshot-at-Beginning actually allows Black-White pointers. So when the pointer 44
from object A is added to D -- nothing happens at this moment. This is known as legal Black-White pointer 45
since there is still a connection from a Gray object to this White object. However when this connection 46
from the Gray object is changed, the Write barrier is called, and colors the White object is Gray. 47
Once it's done, Mutator can proceed, and change the actual pointer. Since the object D is gray now, on the next 48
collection time slice it will be considered and it will not be lost. 49
Notice that this method is conservative. If the only pointer to the object D was from the object B, then 50
changing this pointer to the object E, would make the object D a garbage. However, it is still colored 51
Gray regardless, and will be considered on the next time slice. It eventually will be removed on the 52
next collection cycle, however and will stay in memory until then. 53
Now let's see another approach to the situation known as the Incremental update. In the Incremental update 54
method 55
The Black-White pointers are actually completely illegal. When there is a pointer change to a White 56
object, it's colored Gray right away. 57
And then the pointer from B can normally be changed 58
it doesn't really matter at this point, since the object is already Gray, since the Write barrier was 59
called 60
This method is known as Dijkstra's Incremental update. 61
Alternative way 62
known as the Steel's Incremental update, would color not the object D as Gray, but the parent object A instead. 63
It's also more conservative, since the whole sub-graph of A should be reconsidered. 64
Okay. 65
Now this is you see GC barriers used in moving collectors, which are mostly Read better as we said. 66
We start from the Baker's Copying method. 67
Okay as we remember, in case of the Semi-Space Copying collector, the heap is divided into two parts: 68
the From space, used by the Mutator, and the To space, used by the Collector. And the Collector evacuates 69
alive objects from the From space to the To space on the collection cycle. 70
In case of the Incremental and Concurrent collector, it can be interrupted again during the collection 71
cycle, during the copying cycle, and actually before it's finished evacuating all the objects. To maintain 72
the correctness, of which objects have already been handled, and which are still needed to be handled 73
and copied, the Copying collector in this case also uses Tri-color abstraction. 74
It divides the To space further in four areas. The Black objects are again those which have been already 75
copied and their children have already been considered and copied as well. 76
The Grey objects are those which have been just copied, that is they are also alive 77
however, their children have not been copied yet. 78
So when the collector will proceed after interruption, it will proceed exactly from the set of Gray 79
objects again 80
And for this the Collector tracks the Scan pointer for the Gray objects. 81
Then follows the Allocation or Evacuation area. 82
This is where the Collector copies the objects from the From space. And all the objects in the From space 83
are the White objects. That is, they haven't yet been copied, and are potential garbage. And once 84
an alive White objects is copied into this Allocation area 85
It becomes Gray. 86
There is also the "green" area here, and it's also allocation area 87
however, now for the Mutator. Since Mutator can interrupt Collector, it needs to continue 88
allocating objects somewhere. It cannot allocate objects in the From space since the collector cycle 89
is in the middle and hasn't finished yet. So it allocates from the opposite side of the To space. 90
Okay now let's see why we need Read barrier here. 91
Imagine that the Mutator interrupted the Collector, and wants to read, say, this object A. 92
Since the collection cycle is still in progress (even though is interrupted), the object A may already 93
be copied to the To space. As we know, the Copying collector can store the Forwarding address directly 94
in the old copy of A. That is, the old object A can already be corrupted by the Collector at that point. 95
So for these all Read operations of the Mutator have to be trapped by the Read barrier. The Read 96
barrier checks, whether the object has already been copied (that is it has the forwarding address set) 97
and in this case the barrier returns the address of the new copy. If the object has not been copied yet 98
like this B object, for example. 99
In this case the Read barrier will actually evacuate the object B, and again will return correct 100
new address. 101
So since Mutator cannot read any White object from the From space, it cannot store a reference to 102
the White object in a Black object, and the heap invariant is preserved. 103
And again this was the Baker's Copying method. 104
The Read barriers, as we know, are expansive: every Read operation is tracked, which creates an overhead on Mutator 105
Alternative solution to avoid usage of the Read barriers, and replace it with the Write barrier 106
is the Brook's method. 107
Let's take a look. To avoid usage of the expensive Read barrier, Brook's Copying method uses an extra 108
data structure of indirect pointers. 109
A pointer in the Mutator program becomes a virtual pointer. 110
It points to this table, which contains the real current address of this object. 111
If an object has already been copied during the collection cycle, its real pointer points to the new 112
copy 113
If, like with the object B, it hasn't yet been copied, the indirection pointer points to the object itself. 114
Notice that in contrast with the Baker's method, the Brook's method actually allows Mutator to see 115
the White objects. For example, Mutator can normally continue reading the object B, since there is no any 116
barriers at all 117
The problem can arise here, when the Mutator tries to store a pointer to a White object from 118
a Black object. That is, from the object, which has already been copied and scanned. 119
In this case Brook's method calls the Write barrier, which evacuates the object B, that is colors it Gray 120
and updates the indirection address. 121
So again this was the Brook's method. 122
Notice also that even if we don't have the Read barrier here anymore, this double-dereferencing of the 123
pointers through the indirection table, can be considered as a sort of "light Read barrier". 124
OK. 125
Here here's the summary for today's lecture. 126
Let's take a look. 127
As we said, to ensure correctness of the collection cycle and to preserve heap invariants, collectors involve 128
usage of the Read- and Write-barriers. The Read barriers are mainly used in moving collectors 129
while the Write barriers -- in non-moving. There are also exceptions here as we said. 130
As we have just seen, the Brook's moving collector uses the Write barrier instead 131
And the barriers 132
work closely with the Tri-color abstraction, and ensure that the objects are colored correctly. 133
To reiterate, automatic memory management is a pretty advanced engineering task. 134
Many production collectors today still not even incremental or concurrent because of this. 135
Those which want to reuse GC pauses, involve the concurrent techniques, and use different sophisticated 136
algorithms, like Tri-color marking, and GC barriers. Whether a garbage collector is a good 137
module specifically for your programming language or not, again depends on the specific environment. 138
Most of the modern general purpose programming languages assuming a GC module as a requirement. 139
So I hope this class helps you to clarify the topic of the automatic memory management, and now implementing 140
the Garbage Collector in your language will be easier. 141
My name is the Dmitry Soshnikov 142
Thanks, and see you in the next classes!