[MUSIC]. Now that we know the basics of dynamic memory allocation let's see how it is implemented. So the main implementation issues and questions are. First, how do we know how much memory to free given just a pointer, right, remember that free just takes a pointer as a parameter. So just based on the pointer we need to know how much memory to, to free. So how do we keep track of which blocks in our heap are free, okay? So how do we pick a block among the free blocks to be allocated. That's when many of them might be suitable. How do we pick the best one? Okay. Is it, it could be because we want to reduce fragmentation, we want to be fast enough and so on. and also if you happen to pick a free block that is bigger than what you need, what do you do with the rest of the block? How to make that useful somehow. And finally, how do we reinsert a block when it's freed, okay? We have to reinsert the block into the heap. Let's solve the first question first. So we need to know how much to free. So the standard method is just to keep the length of a block. In a word preceding the block, so we're going to make, we're going to have a header field. So that's going to require some extra words. It's a little bit of overhead. But it'll be worth it. 'Kay. So, for example, here's our heap, and we have this free block here. When I call malloc, I decide to use this block, 'kay? And now what we're going to do, we're going to use one of the words here. To store the block size. So now I know that, you know, there's a word preceding the pointer where the data is. I know that the immediate word always contains the block size. So I know how much to free. 'Kay? So when I call free, I just know, I'm going to call free, free passing p zero. Which is right here. Right? So, right here. And I know that the previous words contains a block size so I know what to free. Pretty simple. 'kay? Now, the next question, keeping the track of, keeping track of free blocks, a little bit more complicated. There's a bunch of options. The first method is an implicit list which is going to see now. We are just going to chain together, based on the, the, on the length or, or the size of the block. We can always determine order of the blocks, and heap, and so on. 'Kay? So now there's an explicit. That's implicit because it traverses and we look whether it's allocated or not. The other method is explicit. So we going to have a link list of all blocks that are free. 'Kay? And then, and then there's some other more sophisticated ways that we can segregate different free lists based on the size. Or we can sort the blocks based by size just to make it faster and more efficient to allocate blocks. Okay? Alright, so let's look at implicit free lists now. So, for each block, we need to know two things, right? What is it's size and whether it's allocated or not. We could store that into words but it's a little wasteful right. This allocator here, fundamentally you only need one bit. So using an entire word for it is so wasteful. So what we going to do? Well we're going to use a standard trick that does the following. Since the blocks are aligned. We know that the low-order bits of the addresses are always zero, okay. For example, if you have an eight byte alignment, all our addresses are going to look like this, you know the lower three bits are all going to be zero. So why not use this last bit here and say, okay we're going to use that bit to, to tell us whether the block is allocated or not. 'Kay, so now, so here's the form of ten allocated blocks. We have the payload that's the useful part and p is going to point to here. "Kay, the p's a pointer to, to the block. We know that in previous words, here the previous word contains the size, and the low order bit is going to tell us if it's set to one the block is allocated. If it's set to zero the block is free. Okay? And payload might be some padding because we might have some padding here because we wanted to honor alignment requirements, okay? So note that since we're going to use this bit for, the lower bit for allocation, we're not really reading the size. We need to mask out this bit. And you know how to do that because you know everything about fiddling with bits by now. Alright? Okay, so let's see how this looks in a, in an example. It, so suppose that we have a sequence of blocks in our heap we have two that, and by the way, this work is size and allocated. So we have a block of two that is at size two and it's not allocated. Four and one that's allocated and so on, okay. So the blocks that are white are free. The light gray is allocated and used. And then dark gray is allocated, but unused, okay. Right, so, and we're going to use an example, [UNKNOWN] byte alignment, okay, so that means that, we may require the initial word to be unused. It does cause some internal fragmentation but it might be worth it. So, and we have one word here, zero size zero, which doesn't make sense, should be zero right, but allocated it's just going to be a marker at the end of the list. That, that, that's the end of our free, of our free list. Okay? So, let's see how we find a free block. The first way we're going to do this is using something called the first fit. Okay? So, and the idea here is just to search the list from the beginning. We choose, we choose the first, flee, free block. Searching the list that fits. Here's how the code works. Okay? So p starts the beginning of the heap. Okay? So it's we have this loop that why we have not reached the end of the heap and the block is already allocated, it's allocated it's not useful. Alright? In the size of the block is lower than the length. 'Kay? Is lower than the required size. And so we do that, we just go to the next block. 'Kay? So now. This, this can take time linear to the total number of blocks allocated than free and allocated if like all blocks in the implicit free list and in practice this cause splinters at the beginning of list because we going to have large blocks you going to find the first one. So that means that we going to start, we're not going to use that very efficiently, okay. So now the next fit is just like first fit, but you start from where you stopped during the last, when, when you stopped when you did the last malloc. Okay? So it should often be faster than first fit because it avoids rescanning blocks that are unhelpful. And then what some, s-, some research suggests that fragmentation is worse. 'Kay? Now, there's something else called the best fit, which you search an entire list, and you find the best free block, which is the one with the fewest bytes left over. 'Kay? By the way, so, a splinters, in case it wasn't clear when I said, is when you have, you tend to find blocks that are too big for what you need. So there's a little bit more waste. Okay. So best fit, we don't have that problem because we always going to find the one that's the best one among the free blocks that you have. The one that's, the smaller one that's sufficient to honor your request. 'Kay? So this, of course, keeps fragmentation small, and it helps, so, it usually helps fragmentation. Okay? And typically runs slower because you're going to have to look at entire lists as opposed to stopping when you find the first one, okay? So let's look at something called splitting now. So what is splitting? Well when you find a, a block that, that, a free block that's bigger than what you need instead of just leaving this there you know, for example here if I allocate of my block p here and I only need four. Wh-what's going to happen with this here? Well, when we allocate, we need only four we can just split it and leave it there. Okay, so that's, that's really what, what we want to do. Because we don't want to use this whole six block size of six because then it's going to be wasteful. Okay? And the way this works is as follows. First, we get, for example, we, we're calling this function addblock of size four at pointer p. Okay, p points right there, we add a symbol. We, we add the block of size four. What going to happens is now we're going to point to, we're going to create a free block of size two, right? 6 minus 4. And then we're going to okay. So that's it. Now, here's how we're going to implement this function called addblock. And we're going to implement we, we're going to say new size equals len plus one shifted by one left, by one is pretty cool. You know what this is doing? Just rounding up to even. And it's just round, it's rounding up to even just because of our alignment requirements, okay? We're going to have an even number of words because of our alignment requirements. Now we're going to keep the old size here. So we're going to mask out we're just going to mask, mask out a little bit and get the size. And now the, the new size here, p has a new size, and ord with one. So mark that it's allocated, okay? But now, the new size is smaller than the old size. What we're going to do is p plus the newsize, which points to the next block, is going to be oldsize minus newsize. And we do not set the low bit here, because the block is free. Pretty cool, huh? Okay, so well, now how do we free a block? Well, the the simplest way so just to clean, is just to clear the allocated flag. Okay, so we can do this, this allocation clear the bits by masking it out. But this is, this is bad because it can lead to false fragmentation, right? So now for I have, I have a free block of four here, free block of two here. Why not just make it look like a block of six, because if we don't later if I do need the block of size six I am not going to able to honor it because I am going to think I don't have free enough but this is not real fragmentation but it looks like real fragmentation alright, so that's a big oops. What's the problem? Now I want to allocate five, now I can't honor it. Okay. So there is enough free space but the allocator won't be able to fit it, just because it got a little confused. So naturally what we're going to do? Well we're going to coalesce these three blocks into a larger one, okay. So now for example, if we have this, this pointer. Be here, to this block four. When I free it what I want to do is to make this logically gone and free it and make the size of the ni, new free block be six. 'Kay? How we going to do that? Well, we're going to clear out the allocated bit, bit. Find the next block. Anything happens to be free. We're just going to Adjust the size. That's all. Pretty cool, right? So it just adds to, we just add the sizes if, if they are free. And, again, since the allocated bit is free you can just do this addition without masking out the bits. Okay. But now How do we coalesce with the previous block? Suppose that I wanted to free a block, and I free the block but the previous one is also free. How do I point backwards? I could just start from the beginning of the, the heap and scan again but that's slow and remember, we want to have high throughput. So that's why we're going to do, we're going to do bidirectional, bidirectional coalescing. This was invented a long time ago. And the idea is to use to is to replicate the size here, the header at the bottom. Okay, so we, we replicate the header at the bottom so both the size in the allocated bit and I can use that to traverse it backward so we can just join them pretty cool isn't it. Okay, so here's a summary of implicit free lis implicit free lists.. Implementation is very simple, okay. The allocate cost is linear time on the total number of heap blocks including allocated and free, okay. So the free cost is constant time, okay, in the worst case even with coalescing, because I'm going to know how to point both forwards, and backwards, so we never have just canned in heap. And so the memory utilization that we get is going to depend on the placement policy, what is first fit, or best fit or next fit, and so this is not used in practice for malloc and free because of this linear time allocation. That's still not good we can do a lot better. You're going to see that. But it is used in some special purpose applications. Okay. So, but in keeping mind that the concepts of splitting and boundary tags are general to all allocators. Okay. So we, we're going to use this concept of splitting, splitting free blocks. Right. So we don't. You, you don't waste the part that was still free in your block in case you use a block that is larger than what you need. And we're going to use things like boundary tag to make coalescing fast. See you soon.