[MUSIC].

All right.
now that we know a lot about memory
allocation and we know some of its
basics, we know some details,
implementations and so on.
let's talk about something called garbage
collection.
We're trying to make a lot of this
automatic.
Right.
So far, we have assumed that applications
are going to malloc and then free
whenever they don't need it anymore.
But it turns out that's, that can be a
pain and a big source of, of memory
problems like leaks and so on, okay?
So that's why a garbage collection was
invented, so it's it provides automatic
reclamation, reclamation of heap
allocated storage.
So, for example, suppose that here's a
function foo that has a pointer p.
It allocates this malloc, allocates, and
then when this function returns, this
pointer's going to be gone.
So there's nothing that points to the
allocated block anymore.
That means that the, the block piece is
now garbage, because nobody can reference
it, 'kay?
So and so you can just go and
automatically free it and garbage
collection does that.
This is automatic freeing of blocks that
are no longer useful, that we know are no
longer useful, okay?
So this is very common in functional
languages, scripting languages, and
modern objective-orientated languages.
So like, things like lists, ML, Java,
just common Java, Perl, Mathematica,
Python and so on, 'kay?
So there are also variants of garbage
collectors called conservative garbage
collectors for C and C++.
They had to be conservative because C and
C++ are very flexible in how they support
pointers and then makes implementing
garbage collection hard.
So they have to be conservative, okay?
It works but it can, it can't you might
not be able to collect all garbage.
So let's answer some of the core
questions of garbage collection.
The first one is knowing when memory can
be freed.
So in general, it's very hard to know
what's going to be used in the future,
since it depends on conditions and so on.
So we have to have a way of knowing that
it's never going to be used again.
But so we can know when certain blocks
are no longer reachable.
There's nothing that point to them.
So if, if you have blocks in your heap,
but we know there are no pointers to
those blocks, then we know for sure that
those blocks can be collected.
Okay, can, it can be freed.
But for that, the allocator needs to know
what is a pointer, what's not a pointer.
How can he do this?
Well, it needs language support.
You need to, or you need, you need to be
disciplined on how you use pointers.
Okay?
So there will be some support, either the
program is going to declare what's
pointer, what's that pointer, what the
language supports it and so on, okay?
So, we're going to make some assumptions
about pointers in the rest of this of
this video.
First memory allocator can distinguish
pointers from non-pointers, okay?
So all pointers point to the start of a
block, in the heap, and the application
cannot hide pointers.
For example, it cannot cast them to int
and then back again to hide pointers,
'kay?
So that's what I mentioned before,
disciplined use of pointers, 'kay?
There are many garbage collection
algorithms.
Now, one of the classic point, classic
ones is market sweep, which is going to,
we're going to see in this video now.
it doesn't move blocks around it just
collect them, 'kay?
unless if, if, if you compact, then the
effect is moving it but we're not
going to be looking at that.
So anyways, there is a bunch of of, of
algorithms and note that it started long
time ago, 1960, so it's been, it's been a
problem for a while.
If interesting and learn, we're going to
give you a basic overview in this video.
But if you do want to learn more, there's
this really nice book Garbage Collection:
Algorithms for Automatic Dynamic Memory
by Jones and Lin.
It's a really cool book, if you're
interested in that, I definitely
encourage you to read it.
So let's get started with the basics.
First of all, we're going to look at
memory as a graph, as a directed graph,
'kay?
So, each allocated heap block is a node
in the graph and each pointer is a notch
in the graph.
Okay?
So, and locations that are not in the
heap that contain pointers into the heap
are called root nodes.
They're these things that are outside the
heap.
So these are the heap nodes.
So you do the, the root nodes.
Okay?
So, green nodes here are reachable,
meaning that there is a pointer from the
roots to them, and the other ones are not
the ones we rather not reachable.
'Kay?
So, and we define reachable as follows.
A node is reachable if there's a path
from any root node to to that node, 'kay?
So for example, so this one is green
because there's a path, this one is green
because there's a path, through here.
But now, this one, these ones are not
reachable, because there's no way to get
from any of the root nodes to them, 'kay?
So these ones are, are the ones that
we're going to consider garbage, are the
ones that we're going to collect.
'Kay?
So, let's see it how mark-and-sweep
works.
It's one of the classic, simplest,
algorithms that, that do that.
And that could be built on top of malloc
and free package.
So we, we allocate using malloc, until we
run out of space and then you do garbage
collection.
'Kay?
And when, when you're out of space,
here's what we're going to do.
We're going to use an extra mark bit in
the head of each block.
Okay?
And then we have this mark phase that
starts a lot of the roots and sets the
mark page on each reachable block, 'kay?
And once we do that, over the entire
heap, we can sweep, scan over all blocks
in the heap and free the ones that are
not marked, because we know that those
are not reachable, okay?
So here's an example.
Visual example.
here's what we have before mark.
We have a root another points here, okay?
So from there, we're going to traverse.
Now we, we're going to, we're going to
traverse this and mark the free block.
So from here, we can reach here, so we
mark this one, okay?
So from this one, we can reach this one,
so can mark this one.
And, from so since it points here, from
this one, we can reach here so we marked
this one, 'kay?
Once that's done, we're going to have the
sweep phase, which we know that these
here were not, this was not marked and
this was not marked, so we can go ahead
and free both of them.
Pretty simple, right?
So, let's think of this as a simple
implementation.
But we need assumptions for that.
First, this new, this function new here
with n returns a pointer to a new block
with all locations cleared.
[INAUDIBLE] and read b,i reads location i
of block b into a register, 'kay?
And writes b,i and v, write v into
location i of block b.
So, it does is, it just add, no, location
i to block b.
This is v, okay?
And each block is going to have a header
word that's pointed by b minus 1, 'kay?
So having these restriction here, you
know?
So if, if we're going to use this
function, if applications use this
function, now we can actually keep track
of what is pointers, and where allocation
was being used, and so on, okay?
So the functions used by the garbage
collection is going to be as follows.
We're going to check whether certain p is
a pointer to a block, okay?
So whether something, whether p, so if
you pass p as a parameter, this returns
through if p happens to be a pointer to a
block.
Length of p just tells us the size of the
block not including the header, and get
roots, returns all of the roots in the
system.
Root again, roots are all of the pointers
that are outside the heap, 'kay?
Alright, so let's see how this works.
So, this is the mark phase we started
with we started with the pointer p, 'kay?
So if it's, if p is not a pointer, it
just return, okay?
So also, if its already marked, we return
as well.
Okay?
But now, we go if, if we are here, it,
because it is a pointer hasn't been
marked so we mark it.
And not only that, we're going to go over
the entire block pointed by p and we're
going to go call mark it.
So parts of it are going to be pointers,
parts of this block is not going to be
pointers.
Okay?
So we, we recur, so this is going to mark
the entire graph, so we're going to
traverse entire heap and mark it a, and,
and mark whatever is a pointer and and so
on.
Okay?
Now sweep is going to use length to find
the next block.
Okay?
So we're going to start with p, and we
know, we know where, where it ends.
Okay?
So while p has not reach the end, if the
mark bit is set, we clear the mark bit.
Now, if the allocated bit is set, so but
it, it, if it's not marked, and the
allocate bit is set, we're going to go
and free it.
Because we know it's allocated, but it's
not marked.
It means it's not reachable.
Okay?
Great.
So now we're going to go to, to, to the
next pointer, we're just adding length.
'Kay?
That's pretty cool, pretty simple.
Now, how would we make that work in C?
Well, the challenge of doing this in C is
that, remember that we need this
function, say the, whether certain
location's a pointer.
So in C, anything can be positive.
That, that's a little bit complicated.
So we have to keep track of when you put
pointers.
You have to, to somehow tell a run-time
system that a system location is a
pointer.
Okay?
So but also in C, a pointer can point to,
to the middle of an allocated block.
So that makes it tricky to find allocated
allocated blocks in the mark phase.
Okay.
So the way to solve this as I said by
calling the run-time system, call the
information and so on.
but the, the upshot is that we can make
it work somehow, but it's going to be
conservative.
It might miss, blocks if everything that
it marks, everything that it decides that
can be collected, indeed can be
collected.
However, you might miss some unreachable
blocks and not free those.
So, it's not it might miss something.
But it's it should work reasonably well.
'Kay?
See you soon.