1 00:00:02,096 --> 00:00:08,023 In this video, we're going to talk about the first of three garbage collection 2 00:00:08,023 --> 00:00:14,024 techniques that we're going to look at in detail. First one is mark-and-sweep. 3 00:00:14,024 --> 00:00:17,744 Mark-and-sweep works in two phases. And it's called, not surprisingly, mark and 4 00:00:17,744 --> 00:00:21,674 sweep. So, the mark phase is going to trace all the reachable objects. So, when 5 00:00:21,674 --> 00:00:25,616 memory runs out and we stop to do the garbage collection, the first thing we're 6 00:00:25,616 --> 00:00:30,107 going to do is go and trace out all the reachable objects. And then the Sweep 7 00:00:30,107 --> 00:00:34,417 phase is going to collect all the garbage objects. And to support this, every object 8 00:00:34,417 --> 00:00:38,337 is going to have an extra bit somewhere in it called the mark bit. And, this is 9 00:00:38,337 --> 00:00:42,428 reserved from memory management and it's not going to be used by anything except 10 00:00:42,428 --> 00:00:46,534 the garbage collector. And initially, before we start a garbage collection, the 11 00:00:46,534 --> 00:00:50,600 mark bit of every object will always be zero. And that's going to be set to one, 12 00:00:50,600 --> 00:00:54,535 for the reachable objects in the mark phase. So, when we mark an object, we mark 13 00:00:54,535 --> 00:00:59,436 it with a And that indicates that the object is reachable. So, here is the mark 14 00:00:59,436 --> 00:01:04,391 phase. It's going to be a work list based algorithm and so initially our work list 15 00:01:04,391 --> 00:01:10,175 consists of all the roots so all the initial pointers held in registers and 16 00:01:10,175 --> 00:01:14,737 then while the work list, the to-do list is not empty, we're going to do the 17 00:01:14,737 --> 00:01:20,266 following. We pick some element v out of the to-do list we'll remove it from the 18 00:01:20,266 --> 00:01:25,472 to-do list, okay. And then, this is the crux of the algorithm. If the object v is 19 00:01:25,472 --> 00:01:30,256 not already marked then we mark it, okay. So, we say, mark bit to one and then we 20 00:01:30,256 --> 00:01:34,250 find all the pointers inside of it, alright. And we add those to our work 21 00:01:34,250 --> 00:01:38,765 list. So, everything, every point gets added to work list. Now, if v is already 22 00:01:38,765 --> 00:01:42,899 marked, well then we have already processed it and we've already add all the 23 00:01:42,899 --> 00:01:47,161 things it points to, to the work list. And so we just need to do nothing there is no 24 00:01:47,161 --> 00:01:52,510 else branch and we just drop it from the to-do list. So, once we've completed the 25 00:01:52,510 --> 00:01:57,834 mark phase and every reachable object has been marked, then the sweep phase is going 26 00:01:57,834 --> 00:02:01,666 to scan th rough the heap looking for objects that have mark bit zero. And the 27 00:02:01,666 --> 00:02:05,993 sweep phase is just going to march through all of memory. It's going to start at the 28 00:02:05,993 --> 00:02:10,102 bottom of the heap and walk over every object in the heap and check its mark bit. 29 00:02:10,102 --> 00:02:13,971 And so, any of the objects that it finds that have mark bit zero, they were not 30 00:02:13,971 --> 00:02:18,134 visited in mark phase and they're clearly not reachable. S, all those objects will 31 00:02:18,134 --> 00:02:22,869 be added to a free list. And as we go through the memory is one other detail 32 00:02:22,869 --> 00:02:28,195 that's important. Any object that has its mark bit set is gonna have its mark bit 33 00:02:28,195 --> 00:02:34,047 reset to zero. So, that way it's ready for the next garbage collection. So, here is 34 00:02:34,047 --> 00:02:40,203 the pseudo-code for the sweep phase and this will function, size of p is going to 35 00:02:40,203 --> 00:02:45,241 size of block, the size of the object that starts at pointer p, alright. And as 36 00:02:45,241 --> 00:02:49,784 you'll see this is actually, the reason that we have the size of objects encoded 37 00:02:49,784 --> 00:02:53,986 in the object in COOL. So, remember in the header for COOL objects there is a size 38 00:02:53,986 --> 00:02:58,352 field that is, so that the garbage collector as it's walking through memory 39 00:02:58,352 --> 00:03:02,633 can figure out how big the objects are. Anyway, we start at the bottom of the 40 00:03:02,633 --> 00:03:07,040 heap. And while we haven't reached the top of the heap, we do the following. We look 41 00:03:07,040 --> 00:03:11,485 at where we're pointing and then we'll always be pointing to the beginning of an 42 00:03:11,485 --> 00:03:15,362 object. So, we check to see if the mark bit of that object is one. And if it is, 43 00:03:15,362 --> 00:03:19,132 well then it was a reachable object. So, we just reset its mark bit to zero. 44 00:03:19,134 --> 00:03:23,144 Otherwise, if its mark bit was zero, then we're going to add that block of memory, 45 00:03:23,144 --> 00:03:27,520 okay, which is the size of the object to the free list. And finally, in either 46 00:03:27,520 --> 00:03:32,190 case, okay, we're going to increment p by the size of the object that it points to 47 00:03:32,190 --> 00:03:36,867 so we point to the next object. Then we'll just repeat that loop over and over again 48 00:03:37,034 --> 00:03:41,066 resetting the mark bits of things that were reached and adding things that were 49 00:03:41,066 --> 00:03:46,095 not reached for the free list until we've touched every object in the heap. Here's a 50 00:03:46,095 --> 00:03:51,049 little example. So, we're starting out here with a, a heap and we're gonna assume 51 00:03:51,049 --> 00:03:56,026 there's just one root for simplicity. And here are all the objects and initially 52 00:03:56,026 --> 00:04:00,086 their marked bits are zero and we do have a free list, an initial free list over 53 00:04:00,086 --> 00:04:05,227 here. Notice that, you know, there's a little bit of memory that is on the free 54 00:04:05,227 --> 00:04:08,527 list. Okay. So, after the mark phase, what has happened? Well, we've gone through, 55 00:04:08,527 --> 00:04:12,976 and touched all the reachable objects. So, we started with A and, of course, we set 56 00:04:12,976 --> 00:04:17,682 its mark bit to one. And then we followed pointers reachable from A, set the mark 57 00:04:17,682 --> 00:04:21,940 bit there. Follow the pointer reachable from C, set the mark bit there. And so we 58 00:04:21,940 --> 00:04:26,463 wind up A, C, and E being marked, nothing else is marked, okay. And now the sweep 59 00:04:26,463 --> 00:04:31,702 phase will go through memory, it's going to reset all the marked bits to zero. And 60 00:04:31,702 --> 00:04:36,719 as it finds unreachable objects, in this case B and D, it's going to add them to 61 00:04:36,719 --> 00:04:41,239 the free list and so what we'll wind up the free list will wind up being a linked 62 00:04:41,239 --> 00:04:46,487 list of, of, of blocks of memory that are available for future allocations. Now, 63 00:04:46,487 --> 00:04:50,957 this algorithm is very simple. And conceptually, I think it's, it's very 64 00:04:50,957 --> 00:04:55,383 clear how it works. But there are a number of tricky details and this is very typical 65 00:04:55,383 --> 00:05:00,049 of automatic memory management algorithms. And there's actually a serious problem 66 00:05:00,049 --> 00:05:04,403 with the mark phase. And, and this is also typical of, of garbage collection 67 00:05:04,403 --> 00:05:08,476 algorithms. Now, notice that we only run this algorithm when we are out of space, 68 00:05:08,476 --> 00:05:12,635 okay. So, the whole point is that we're garbage collecting because there's no more 69 00:05:12,635 --> 00:05:17,945 system memory available for allocating new objects. And yet we have this to-do list, 70 00:05:17,945 --> 00:05:22,410 okay. And notice that the work list was not bounded in size. There was no 71 00:05:22,410 --> 00:05:26,120 guarantee about how many elements were going to be on the to-do list. And I 72 00:05:26,120 --> 00:05:30,213 think, it's easy to see that, that data structure could actually be fairly large, 73 00:05:30,213 --> 00:05:34,478 alright. And so, we can't just allocate a fixed amount of space for the to-do list 74 00:05:34,478 --> 00:05:38,605 or reserve some constant amount of space. But we need to deal with the fact that we 75 00:05:38,605 --> 00:05:42,883 actually don't have any space at all when we get around to doing a garbage collect 76 00:05:42,883 --> 00:05:47,729 ion. Now, there is a trick that can be used to maintain the to-do list during the 77 00:05:47,729 --> 00:05:52,093 mark phase without having to use any extra storage. And that is to do what is called 78 00:05:52,093 --> 00:05:57,050 pointer reversal. So, when a pointer is followed, it's going to be reversed to 79 00:05:57,050 --> 00:06:02,009 point back to its parent. And this is going to allows us actually to track what 80 00:06:02,009 --> 00:06:06,052 elements or what objects in the heap still need to be processed without having to use 81 00:06:06,052 --> 00:06:10,059 any extra space. And let's just if you don't understand that I'm going to do an 82 00:06:10,059 --> 00:06:14,405 example in just a second. I wanna mention a second problem as well and that is, you 83 00:06:14,405 --> 00:06:18,374 know, where is the free list stored? And this is a little easier to see how that 84 00:06:18,374 --> 00:06:23,308 works. So, the free list consists of blocks of memory. And, and we just use the 85 00:06:23,308 --> 00:06:28,074 space in these blocks to maintain the free list so perhaps the first word or 86 00:06:28,074 --> 00:06:34,007 something of the block of memory will contain the size of the block and then the 87 00:06:34,007 --> 00:06:39,282 second word will point to the next block in the list, you know, something like that 88 00:06:39,282 --> 00:06:43,759 but we can use the space in the blocks themselves to maintain the free list. And 89 00:06:43,759 --> 00:06:49,806 so, now let's come back to this pointer reversal idea. Let's say that we have some 90 00:06:49,806 --> 00:06:54,557 objects, okay, and we want to track reachability, okay, and we can't maintain 91 00:06:54,557 --> 00:06:59,658 the to-do list, all right in a separate data structure. And so how are we going to 92 00:06:59,658 --> 00:07:04,794 do that? Well, well, here's the idea when we change colors. So, we're doing to come 93 00:07:04,794 --> 00:07:09,272 in here and we're going to mark this first object. Let's say this is reachable from 94 00:07:09,272 --> 00:07:13,617 the root and now that this is the root the first object. And now we're going to 95 00:07:13,617 --> 00:07:18,393 follow the pointers in this object and let's say this is one here, this one here 96 00:07:18,393 --> 00:07:23,600 is the first pointer in the object. So, we're going to follow it and then we're 97 00:07:23,600 --> 00:07:28,096 going to reverse it. We're going to have it point back to the parent. So, now we 98 00:07:28,096 --> 00:07:32,609 will mark this object and then we'll follow the pointers in, in this object, 99 00:07:32,609 --> 00:07:36,720 okay. And as we go down, we'll have this pointer point back and then we'll mark 100 00:07:36,720 --> 00:07:41,368 this object. And now, we got no point ers in this object and so we need to go back 101 00:07:41,368 --> 00:07:46,235 and process any pointers that weren't covered in the object set that we that we 102 00:07:46,235 --> 00:07:50,077 have already seen, okay. And how do we find our way back? Well, that's what the 103 00:07:50,077 --> 00:07:54,022 pointer reversal was for. So, we could follow the blue arrow back here, as we 104 00:07:54,022 --> 00:07:57,080 come back, we'll restore the original pointer. So, we'll get rid of the reversed 105 00:07:57,080 --> 00:08:01,038 pointer. There are no more pointers in this object either so we'll go back one 106 00:08:01,038 --> 00:08:04,097 more object and now, of course, this pointer will go away and we'll restore the 107 00:08:04,097 --> 00:08:08,050 original pointer, alright. And now, we're in this object and we see there was a 108 00:08:08,050 --> 00:08:12,021 second pointer that we haven't followed yet, okay. And, and then we'll follow it 109 00:08:12,021 --> 00:08:16,025 and we'll reverse it and we'll follow the other pointer from that, reversing it, 110 00:08:16,025 --> 00:08:20,003 and, and then we'll mark these two objects, when we get down to this object 111 00:08:20,003 --> 00:08:24,018 and we discover there are no additional pointers, we'll be able to use this, these 112 00:08:24,018 --> 00:08:28,037 blue arrows here to work our way back and we'll restore the red arrows as we walk 113 00:08:28,037 --> 00:08:31,853 back up through the objects. So, essentially the point of reversal does is 114 00:08:31,853 --> 00:08:36,014 it helps us maintain the stack for a depth for search of the graph. So, if you're 115 00:08:36,014 --> 00:08:40,236 doing adept for search of the graph and you want to be sure that you cover all the 116 00:08:40,236 --> 00:08:44,550 notes that are reachable then you have to be able to do the back tracking. And the, 117 00:08:44,550 --> 00:08:49,733 the reversed pointers allow us to do that [cough]. There's one more tiny issue here 118 00:08:49,733 --> 00:08:54,503 with the reversed pointers. So, notice that there's a little bit of a problem. 119 00:08:54,503 --> 00:08:59,029 So, I want to talk about reversing pointers and let me draw two new objects 120 00:08:59,029 --> 00:09:04,033 here just to illustrate the point. Let's say, I have a, a pointer from this object 121 00:09:04,033 --> 00:09:09,320 to that object. So, when I cross over, to the object that is pointed to, what does 122 00:09:09,320 --> 00:09:14,230 it mean to reverse this pointer? Well the, you know, the space where the pointer is 123 00:09:14,230 --> 00:09:19,437 actually in this object, there's no space necessarily for the pointer at all in, in 124 00:09:19,437 --> 00:09:24,883 the object that I'm going to. And so, in fact, what's going to happen let's say 125 00:09:24,883 --> 00:09:30,894 this was part of a chain of objects, okay. And, and this problem is easily solved, 126 00:09:30,894 --> 00:09:35,831 the issue is just off by one problem. So, I have, I have space in this object for a 127 00:09:35,831 --> 00:09:40,842 pointer and I can change that pointer. I don't know if I even have any pointers in 128 00:09:40,842 --> 00:09:45,853 this object yet, alright. So, let's say this is part of a chain of objects, okay, 129 00:09:45,853 --> 00:09:50,860 and that I've walked down this chain to, to this particular object. So, as I pass 130 00:09:50,860 --> 00:09:55,760 over to this third object with I, the pointer that I will reverse is this one 131 00:09:55,760 --> 00:10:01,315 and I will make it point back to the previous object, okay. And then I'm just 132 00:10:01,315 --> 00:10:06,083 going to remember this particular object, you know, I'll keep the pointer to this 133 00:10:06,083 --> 00:10:12,007 particular object in a register. So, I'll keep the last pointer at reversed in a 134 00:10:12,007 --> 00:10:17,032 register. An, and a pointer to the last object that I came from in a register and 135 00:10:17,032 --> 00:10:22,033 then when I go on to another object, I will use the pointer that I'm traversing 136 00:10:22,033 --> 00:10:27,047 in the current object to point back to the parent of the previous object, okay. So, 137 00:10:27,047 --> 00:10:32,073 it's just a off by one problem, I need one register here to hold on to the previous 138 00:10:32,073 --> 00:10:37,074 object that I visited and then I can reverse pointers back up to their parents 139 00:10:37,074 --> 00:10:42,039 and grandparents. Alright, to summarize the discussion of mark-and-sweep. Space 140 00:10:42,039 --> 00:10:47,051 for a new object is going to be allocated from the free list, little typo there. And 141 00:10:47,051 --> 00:10:52,045 we're always going to pick a block, we always have to pick a block from the free 142 00:10:52,045 --> 00:10:56,750 list that is large enough to hold the object that we're allocating. And in an 143 00:10:56,750 --> 00:11:01,048 area of the size that we need is going to be allocated from that block and then the 144 00:11:01,048 --> 00:11:05,066 leftovers is to be put back on the free list. So, let's say the free list has a 145 00:11:05,066 --> 00:11:10,018 block, let's say it has 100 bytes and then we need an object that has 50 bytes in it. 146 00:11:10,018 --> 00:11:14,328 So, what will happen is that this block will get split up. We'll use this first 147 00:11:14,328 --> 00:11:18,829 half, the first 50 for the object and then this other part the leftover will get put 148 00:11:18,829 --> 00:11:23,121 back on to the free list. And the result of that kind of strategy where we, we have 149 00:11:23,121 --> 00:11:27,874 to find blocks that are big enough but then we might not use the entire block is 150 00:11:27,874 --> 00:11:31,749 that mark-and-sweep can fragment the memory. We might wind up with lots of 151 00:11:31,749 --> 00:11:36,213 little bits of leftover memory maybe nothing big enough to actually hold an 152 00:11:36,213 --> 00:11:41,026 object. And these blocks, these little tiny blocks might be scattered all over 153 00:11:41,026 --> 00:11:46,206 the place. So, it's important actually, for mark-and-sweep to also merge blocks 154 00:11:46,206 --> 00:11:52,032 whenever possible. So, it's merge free blocks, when possible. So, basically when 155 00:11:52,032 --> 00:11:57,486 the sweep phase is working on the free list. It needs to recognize when it has 156 00:11:57,486 --> 00:12:02,222 two adjacent blocks of memory that will be immediately adjacent to each other in 157 00:12:02,222 --> 00:12:07,054 memory. So, if I have two blocks that are contiguous, what I really want to do is to 158 00:12:07,054 --> 00:12:11,451 merge them into one big block and just have one entry in the free list. That's a 159 00:12:11,451 --> 00:12:16,025 counteract fragmentation of memory. Now, one big advantage and perhaps the biggest 160 00:12:16,025 --> 00:12:20,029 advantage of mark-and-sweep is that objects are not moved during garbage 161 00:12:20,029 --> 00:12:24,094 collection. And that means I don't have to update the pointer objects. Object stay 162 00:12:24,094 --> 00:12:29,058 put, they don't move as part of garbage collection. And what this means is it's 163 00:12:29,058 --> 00:12:34,059 actually possible to adapt mark and sweet, for languages like CNC++. So, in CNC++, 164 00:12:34,059 --> 00:12:39,747 pointers are exposed to the programmer so programmers can, can manipulate pointers 165 00:12:39,747 --> 00:12:45,001 and test pointers and so you can't move objects in CNC++ because the pointer is 166 00:12:45,001 --> 00:12:49,095 part of their semantics. The pointer address, I should say, is part of their 167 00:12:49,095 --> 00:12:54,822 semantics. But it is actually possible and people actually have done it to build 168 00:12:55,030 --> 00:13:00,316 conservative or, you know, variations of a mark-and-sweep garbage collection for C++ 169 00:13:00,316 --> 00:13:05,079 precisely because the objects don't move.