In this video, we're going to talk about
the first of three garbage collection
techniques that we're going to look at in
detail. First one is mark-and-sweep.
Mark-and-sweep works in two phases. And
it's called, not surprisingly, mark and
sweep. So, the mark phase is going to
trace all the reachable objects. So, when
memory runs out and we stop to do the
garbage collection, the first thing we're
going to do is go and trace out all the
reachable objects. And then the Sweep
phase is going to collect all the garbage
objects. And to support this, every object
is going to have an extra bit somewhere in
it called the mark bit. And, this is
reserved from memory management and it's
not going to be used by anything except
the garbage collector. And initially,
before we start a garbage collection, the
mark bit of every object will always be
zero. And that's going to be set to one,
for the reachable objects in the mark
phase. So, when we mark an object, we mark
it with a And that indicates that the
object is reachable. So, here is the mark
phase. It's going to be a work list based
algorithm and so initially our work list
consists of all the roots so all the
initial pointers held in registers and
then while the work list, the to-do list
is not empty, we're going to do the
following. We pick some element v out of
the to-do list we'll remove it from the
to-do list, okay. And then, this is the
crux of the algorithm. If the object v is
not already marked then we mark it, okay.
So, we say, mark bit to one and then we
find all the pointers inside of it,
alright. And we add those to our work
list. So, everything, every point gets
added to work list. Now, if v is already
marked, well then we have already
processed it and we've already add all the
things it points to, to the work list. And
so we just need to do nothing there is no
else branch and we just drop it from the
to-do list. So, once we've completed the
mark phase and every reachable object has
been marked, then the sweep phase is going
to scan th rough the heap looking for
objects that have mark bit zero. And the
sweep phase is just going to march through
all of memory. It's going to start at the
bottom of the heap and walk over every
object in the heap and check its mark bit.
And so, any of the objects that it finds
that have mark bit zero, they were not
visited in mark phase and they're clearly
not reachable. S, all those objects will
be added to a free list. And as we go
through the memory is one other detail
that's important. Any object that has its
mark bit set is gonna have its mark bit
reset to zero. So, that way it's ready for
the next garbage collection. So, here is
the pseudo-code for the sweep phase and
this will function, size of p is going to
size of block, the size of the object that
starts at pointer p, alright. And as
you'll see this is actually, the reason
that we have the size of objects encoded
in the object in COOL. So, remember in the
header for COOL objects there is a size
field that is, so that the garbage
collector as it's walking through memory
can figure out how big the objects are.
Anyway, we start at the bottom of the
heap. And while we haven't reached the top
of the heap, we do the following. We look
at where we're pointing and then we'll
always be pointing to the beginning of an
object. So, we check to see if the mark
bit of that object is one. And if it is,
well then it was a reachable object. So,
we just reset its mark bit to zero.
Otherwise, if its mark bit was zero, then
we're going to add that block of memory,
okay, which is the size of the object to
the free list. And finally, in either
case, okay, we're going to increment p by
the size of the object that it points to
so we point to the next object. Then we'll
just repeat that loop over and over again
resetting the mark bits of things that
were reached and adding things that were
not reached for the free list until we've
touched every object in the heap. Here's a
little example. So, we're starting out
here with a, a heap and we're gonna assume
there's just one root for simplicity. And
here are all the objects and initially
their marked bits are zero and we do have
a free list, an initial free list over
here. Notice that, you know, there's a
little bit of memory that is on the free
list. Okay. So, after the mark phase, what
has happened? Well, we've gone through,
and touched all the reachable objects. So,
we started with A and, of course, we set
its mark bit to one. And then we followed
pointers reachable from A, set the mark
bit there. Follow the pointer reachable
from C, set the mark bit there. And so we
wind up A, C, and E being marked, nothing
else is marked, okay. And now the sweep
phase will go through memory, it's going
to reset all the marked bits to zero. And
as it finds unreachable objects, in this
case B and D, it's going to add them to
the free list and so what we'll wind up
the free list will wind up being a linked
list of, of, of blocks of memory that are
available for future allocations. Now,
this algorithm is very simple. And
conceptually, I think it's, it's very
clear how it works. But there are a number
of tricky details and this is very typical
of automatic memory management algorithms.
And there's actually a serious problem
with the mark phase. And, and this is also
typical of, of garbage collection
algorithms. Now, notice that we only run
this algorithm when we are out of space,
okay. So, the whole point is that we're
garbage collecting because there's no more
system memory available for allocating new
objects. And yet we have this to-do list,
okay. And notice that the work list was
not bounded in size. There was no
guarantee about how many elements were
going to be on the to-do list. And I
think, it's easy to see that, that data
structure could actually be fairly large,
alright. And so, we can't just allocate a
fixed amount of space for the to-do list
or reserve some constant amount of space.
But we need to deal with the fact that we
actually don't have any space at all when
we get around to doing a garbage collect
ion. Now, there is a trick that can be
used to maintain the to-do list during the
mark phase without having to use any extra
storage. And that is to do what is called
pointer reversal. So, when a pointer is
followed, it's going to be reversed to
point back to its parent. And this is
going to allows us actually to track what
elements or what objects in the heap still
need to be processed without having to use
any extra space. And let's just if you
don't understand that I'm going to do an
example in just a second. I wanna mention
a second problem as well and that is, you
know, where is the free list stored? And
this is a little easier to see how that
works. So, the free list consists of
blocks of memory. And, and we just use the
space in these blocks to maintain the free
list so perhaps the first word or
something of the block of memory will
contain the size of the block and then the
second word will point to the next block
in the list, you know, something like that
but we can use the space in the blocks
themselves to maintain the free list. And
so, now let's come back to this pointer
reversal idea. Let's say that we have some
objects, okay, and we want to track
reachability, okay, and we can't maintain
the to-do list, all right in a separate
data structure. And so how are we going to
do that? Well, well, here's the idea when
we change colors. So, we're doing to come
in here and we're going to mark this first
object. Let's say this is reachable from
the root and now that this is the root the
first object. And now we're going to
follow the pointers in this object and
let's say this is one here, this one here
is the first pointer in the object. So,
we're going to follow it and then we're
going to reverse it. We're going to have
it point back to the parent. So, now we
will mark this object and then we'll
follow the pointers in, in this object,
okay. And as we go down, we'll have this
pointer point back and then we'll mark
this object. And now, we got no point ers
in this object and so we need to go back
and process any pointers that weren't
covered in the object set that we that we
have already seen, okay. And how do we
find our way back? Well, that's what the
pointer reversal was for. So, we could
follow the blue arrow back here, as we
come back, we'll restore the original
pointer. So, we'll get rid of the reversed
pointer. There are no more pointers in
this object either so we'll go back one
more object and now, of course, this
pointer will go away and we'll restore the
original pointer, alright. And now, we're
in this object and we see there was a
second pointer that we haven't followed
yet, okay. And, and then we'll follow it
and we'll reverse it and we'll follow the
other pointer from that, reversing it,
and, and then we'll mark these two
objects, when we get down to this object
and we discover there are no additional
pointers, we'll be able to use this, these
blue arrows here to work our way back and
we'll restore the red arrows as we walk
back up through the objects. So,
essentially the point of reversal does is
it helps us maintain the stack for a depth
for search of the graph. So, if you're
doing adept for search of the graph and
you want to be sure that you cover all the
notes that are reachable then you have to
be able to do the back tracking. And the,
the reversed pointers allow us to do that
[cough]. There's one more tiny issue here
with the reversed pointers. So, notice
that there's a little bit of a problem.
So, I want to talk about reversing
pointers and let me draw two new objects
here just to illustrate the point. Let's
say, I have a, a pointer from this object
to that object. So, when I cross over, to
the object that is pointed to, what does
it mean to reverse this pointer? Well the,
you know, the space where the pointer is
actually in this object, there's no space
necessarily for the pointer at all in, in
the object that I'm going to. And so, in
fact, what's going to happen let's say
this was part of a chain of objects, okay.
And, and this problem is easily solved,
the issue is just off by one problem. So,
I have, I have space in this object for a
pointer and I can change that pointer. I
don't know if I even have any pointers in
this object yet, alright. So, let's say
this is part of a chain of objects, okay,
and that I've walked down this chain to,
to this particular object. So, as I pass
over to this third object with I, the
pointer that I will reverse is this one
and I will make it point back to the
previous object, okay. And then I'm just
going to remember this particular object,
you know, I'll keep the pointer to this
particular object in a register. So, I'll
keep the last pointer at reversed in a
register. An, and a pointer to the last
object that I came from in a register and
then when I go on to another object, I
will use the pointer that I'm traversing
in the current object to point back to the
parent of the previous object, okay. So,
it's just a off by one problem, I need one
register here to hold on to the previous
object that I visited and then I can
reverse pointers back up to their parents
and grandparents. Alright, to summarize
the discussion of mark-and-sweep. Space
for a new object is going to be allocated
from the free list, little typo there. And
we're always going to pick a block, we
always have to pick a block from the free
list that is large enough to hold the
object that we're allocating. And in an
area of the size that we need is going to
be allocated from that block and then the
leftovers is to be put back on the free
list. So, let's say the free list has a
block, let's say it has 100 bytes and then
we need an object that has 50 bytes in it.
So, what will happen is that this block
will get split up. We'll use this first
half, the first 50 for the object and then
this other part the leftover will get put
back on to the free list. And the result
of that kind of strategy where we, we have
to find blocks that are big enough but
then we might not use the entire block is
that mark-and-sweep can fragment the
memory. We might wind up with lots of
little bits of leftover memory maybe
nothing big enough to actually hold an
object. And these blocks, these little
tiny blocks might be scattered all over
the place. So, it's important actually,
for mark-and-sweep to also merge blocks
whenever possible. So, it's merge free
blocks, when possible. So, basically when
the sweep phase is working on the free
list. It needs to recognize when it has
two adjacent blocks of memory that will be
immediately adjacent to each other in
memory. So, if I have two blocks that are
contiguous, what I really want to do is to
merge them into one big block and just
have one entry in the free list. That's a
counteract fragmentation of memory. Now,
one big advantage and perhaps the biggest
advantage of mark-and-sweep is that
objects are not moved during garbage
collection. And that means I don't have to
update the pointer objects. Object stay
put, they don't move as part of garbage
collection. And what this means is it's
actually possible to adapt mark and sweet,
for languages like CNC++. So, in CNC++,
pointers are exposed to the programmer so
programmers can, can manipulate pointers
and test pointers and so you can't move
objects in CNC++ because the pointer is
part of their semantics. The pointer
address, I should say, is part of their
semantics. But it is actually possible and
people actually have done it to build
conservative or, you know, variations of a
mark-and-sweep garbage collection for C++
precisely because the objects don't move.