Building free() from Scratch in x86 Assembly

[00:00:00]Take a look at this memory profile right here. These are blocks of memory. They could be anything that you use in a higher level language or low-level language. It could be objects or just maloc calls from C. This is our heap.

[00:00:10]And right now we have, let's say, three blocks. A 16 byt block, a 32- block, and another 16 byt block. Without the free function, we're never able to reuse any of these blocks. We'd have to continue to allocate sort of forever the way that our bump allocator works right now. So today what we're going to do is write the free function which allows us to free one of these blocks. So we can see here that our 32 byt block was able to be freed by the current state of the program. This is what we're going to make today. And then I'm able to reuse that 32 byt block instead of having more blocks after. And we're also going to be building this little heap profile viewer so that we can see exactly what's happening in our heap. So let's get started. This is what we had last. If we go down to maloc here where we allocate pair, we get the request in and we're going to take the current heat pointer return that in rex and then we're going to add right to the heat pointer the size that they ended up getting so that we can move that heat pointer forward and that space is their reserved memory that we give back to them. But before we do this, we need to record the size somewhere. We're not really writing it down, right? Malo has no idea the blocks that it's given out and how large they are. So if somebody does come back to us to say, "Hey, I'm free. I'm done with this memory block." We don't really know anything about the memory block except for the memory address. So before we return anything here and increment, we need to keep track of these block sizes.

[00:01:34]And the question is where do we put it, right? Do we create an array or some sort of table or we hash it? There's all sorts of ideas that we can come up with of how we can try to keep track of these memory blocks. But as it turns out, the simplest way of doing this is just to write down the size and the status of whether it's free or not right in the memory itself. So if they're asking for 32 bytes, what we're going to do now is we're going to get that heat pointer.

[00:01:59]We're going to write in the data that we want about that block and then we're going to give them that position after we've written that data in as their payload. So So let's think about what we need. We need the size, right? And what we can do is keep it as four bytes because right now we're not going to have like gigabytes worth of allocations. We're going to keep it four bytes which goes to like uh four gigs or whatever it is. And then we also need a flag to know if the block is free or not, right? Cuz right now we're trying to build a free function. So we need to know the status, right? We need a flag.

[00:02:30]So I'm going to put is free and that will also be four bytes just to make it simple. So in total it looks like our header is going to be eight bytes long.

[00:02:39]So let's put header size equals 8. So now that we know that our header size is 8, we need to do a couple things right here where we are aligning the requested value from the user. If they ask for seven bytes, right, we align it to uh in this case eight. We also need to add our header size. So we're going to add that I guess right before we save it to memory. So right here what we can do is we can add to RDI offset header size. So let's run this and test test test it out.

[00:03:13]We requested one bite and you can see now we're missing 16 bytes. It should have been rounded to 8 before but now it's 16 because it is aligned to eight but then we add eight more for the header. Let's see this one. 17 should be rounded to 24 but you see now it's 32.

[00:03:27]So our block size has now increased because we have that metadata, right?

[00:03:30]That header built in, at least a space for it. We've allocated the space or reserved the space for it. And if we take a look at that again, uh, of course, this is now incorrect, right?

[00:03:39]Because we're actually aligned to 8 and the header is the one that is making it 32. So we need to adjust these strings a bit to keep it uh truthful, right? Right now we've muddied uh the alignment and adding that header size. So let's fix that so that our output is still clean and then we can go from there. So right now the allocation string talks about alignment and that's probably wrong. We should just say that it's allocated. So I'm just going to put allocated block.

[00:04:06]But before we had two variables in our format specifier. Now we only have one.

[00:04:10]So let's go up. If we do a search for S allocation. There it is. So RSI is the first argument and RDX is a second. So we really want this one to go to RSI now. And this one should not be used.

[00:04:27]So here we have allocated block. This looks good. So back to our string here.

[00:04:30]And now we can make a new string. Let's say s aligned. And we can put aligned to percent d. And also we're going to want to know our total block size. So let's do s total block size.

[00:04:48]So now that we have these two new strings. So let's go up to where we added the header size right here. And the way this is right now is RAX got the aligned size and then we shift stuff to RDI luckily for us. So RAX actually contains the aligned size and RDI contains a total block size. So this is kind of a perfect spot for us. So after we save the local variable right with the total block size, we can just print the value of rex for the aligned size.

[00:05:15]this load to RDI as aligned and then let's move to RSI RX and then we should be able to call print f and then directly after that let's print the total block size. So let's move or I guess we can load to RDI S total block size and we can move to RSI what is in RB minus 16 and we can call print F and then at this point RDI is being added here. So we need to reload to RDI the total block size uh after print f cuz it's going to be clobbered and go through all sorts of other functions. So let's move to RDI rq - 16. And that's because we've entered these new these two new string functions here and we bothered you know RDI. So we're just going to restore it. So if we run this then we do get some nasty sort of output here but it does look good right the user requested 17 bytes and we aligned it to 24 and now our total block size is 32 right because those eight bytes are there for the header and we have our addresses here which is great. And now looking at this again, the requester is still getting the start of the memory block as the address, right? As that payload, which is wrong because now we want to reserve those first eight bytes for our own sort of bookkeeping. So right before we return that value, let's go back into the program. So if we go down to maloc allocate, here's our return. So right before we return, we want to shift their pointer from the start of the metadata right to skip our header to keep it intact and then return the start of that memory that we will allow them to read and write from. So right here, right before we sort of finish our function, we really want to add to x what's in heap, no header size.

[00:07:01]Now, if we run this, we're not going to see any change because the print happens before, right? Allocation happens before we increase this. We still want to print this because that's the actual start of the memory block and maloc is going to care about the memory block, not necessarily the payload, right? The user will care about the payload, but we really want to care about the entire block. So, we're going to keep this printing out. And at the bottom, let's also make another string, maybe s payload with one hex variable here. And maybe let's shorten this a bit just to keep it a little bit cleaner. So going back up right before we return right here, let's uh temporarily push RAX, let's load that new string to RDI.

[00:07:42]Let's move what's in RAX to RSI. Let's call print F and then we can restore RAX, which is the pointer, right? And let's see how this looks. Uh so here it looks pretty bad. And I I'll shorten these so they look a little better. But we see here that the block address ends in 610, but the payload is 618. So 8 bytes later, that's perfect. So we have our header starting here and the payload starting just 8 bytes after. So this looks great, but let's shorten those strings a bit because they are way too long with a larger font. This is how I have it right now. And here's how it looks. So we've got the request, we've aligned it, we've added our header size to it. So that means that now we can actually write to that header the information that we need to be able to make the free function cuz right now we still need to get that metadata written down. We want the first four bytes of the eight to be the size that the block is including the header. We want only to talk about block size. We don't really care about request size anymore or align size. All we care about when it comes to managing our heap itself is the block size. So the first four bytes are going to be the block size and the second four bytes are going to be the flag or the status of is this block available or not? Is it in use? Right? Is it free? So the right time to do this is probably again right before we return that block to the user. So right here remember rax originally pointed to the start of the block itself. Right? So right before we actually add the header size to it, before we shift it to give it to the user, we can use relax as a pointer to write it in. So let's move to relax, which is that address of the header, right? We want to put the size here, but we don't have the size yet. So let's use maybe rcx and load it from our variable. And we can just put rcx right here. And we're going to put it at the start of the header. I'm going to do plus zero here to make it obvious that we're talking to the header and we want those offsets. So offset zero is going to be the size and offset four is going to be the flag. So in this case the user has requested this memory and it's going to be in use because we're giving it to them. Right?

[00:09:53]So we just need to write to x+4 the value of let's say zero. Right? We need to figure out is a zero when it's free or is a zero when it's used. I'm going to go with zero being that it's not available. So in other words, the header is going to be size and is free. So it's a question. Is it free? One is yes, zero is no. So I'm going to say in this case, we're giving out a block of memory to be used. So it's going to be a zero, right?

[00:10:21]It's not a one cuz it's not free. Right?

[00:10:23]Now it's going to be taken. Then we can just let the program proceed. it continues to add the header size and then we end up returning that to the user and we print out you know the payload. So I think this should be fine.

[00:10:34]I do need to add here though actually um a keyword pointer because the assembler is not going to know how big this zero is. So let's specify a quad word. It should be a dword sorry because we want 32 bits and I have another problem here actually.

[00:10:52]This should be ECX uh because I was about to write eight bytes. And now it probably would have been fine because we were going to overwrite it that last four bytes, but really we're talking to 32 bits. We only want four bytes. And you might say, well, we can we can make this ECX2. And that's totally fine. We could do that. Uh but we've been reading and writing these as 8 byt values, but we know that we're going to cut it off at a 4 by maximum. So ECX is going to be our four bytes that's added to our header. And you could very easily make the header 16 bytes and 8 bytes 8 bytes.

[00:11:22]That's totally fine. So let's see if I have an error here. And we seem to be fine. So at this point each one of these allocations should have the header written where the block is right. So where the block starts in these eight byt difference, right? And the 8 byt gap from between 10 and 18 and 68 and 70 and 78 and 80. The eight bytes in between should have that data that we just wrote. So let's let's check that and verify it. So let's go to GDB and our program is maloc. So GDB maloc and if your GDB doesn't look like this then first do set this assembly assembly flavor intel and uh layout ASM and layout regge uh should get it looking the way I have it. Now what I want to do is disassemble start so we can see the code here. And if we press a down arrow, then I'm going to go down to where exit is called, which is this instruction right here.

[00:12:19]And I want the program to stop right before it exit so that we can see all the memory that has been allocated.

[00:12:24]Everything has been written and we can sort of inspect the memory. So we see that it's on this line here 406.

[00:12:31]So I'm going to do break and then star for uh dreference. And we'll put the address uh 4106 C. And if we run this now, we should see our output here. Now, the little GUI in GDB gets really messed up. We can see there's a bunch of sort of clipped together text here that is very hard to read. So, I'm going to disable the GUI, I guess. TUI disabled. I'm going to do I'm going to run it again.

[00:13:00]So, we have our blocks here. And we're currently stopped, right? It says breakpoint one has been reached, right?

[00:13:06]406. That's where we added that breakpoint to halt the program. So what we want to do is inspect these blocks here to see what's written. Okay, we have our total size. So we know what should show up if it was written correctly to memory. So if we look at this first one here, we want to examine one hexadimal word at 0x 403 0 1 0.

[00:13:30]And we see here that the value is 20.

[00:13:33]Now 20 in hex is 32. So this one seems to add up, right? Cuz 2 * 16 is 32. We can also do it as a decimal. So instead of X we can put D for decimal. So we have 32 the value the four byt value that's written because we have a word here and a word in this case it's four bytes on GDB. So we have four bytes that are 32 here. Now let's check our flag.

[00:13:53]Four bytes after this address should be our flag of is it free and we were expecting a zero because none of these should be free. So let's examine again 1 xw at 403 014 and we have zeros. So our flag is set and our size and we can check out some more. So let's look at 403030 and see if we get 56 which is kind of an odd size.

[00:14:20]And there it is 56 at 4030.

[00:14:24]So this works well. This verifies that we've written to the start of our header the size and the status of whether it's free or not. So let's exit GDB.

[00:14:37]And now that we know that we're writing properly to our memory, we can write a function that actually traverses or walks through our allocations because we really want to be able to look through those different allocations to find out which blocks are free, which ones are not, and their size. So we've looked at it through GDB. We verified that there is something for us to find. So now let's try to print it out with our assembly itself. So let's go back to our program here and let's create a new function. Um maybe we can call it print heap or something like that. So I'm going to go down to let's see I guess right here and I'll do print heap. So in the very beginning we need to start at the start of our heap, right? So let's move to reax he keep start.

[00:15:21]And then we're going to loop, right? We only want to set that up the first time.

[00:15:24]So let's add print heap loop here. And then what we want to do is print only the allocations that we have. So we know that the heat pointer still marks the end of the current allocations, right?

[00:15:36]Or the start of the the block that hasn't been allocated yet, the the first new slot, the first empty slot we could say. So what that means is there's a valid block anytime has not reached heat pointer. So let's compare x to heat pointer. And if rax is greater than or equal to key pointer then we can just exit. So print heat exit. Just add that down here. Print heap exit. And we'll just return. Right.

[00:16:06]So if we've reached the heat pointer, we quit. But if we haven't reached the heat pointer, then we should be at a block that's worth printing. So let us load four bytes. So we're going to use ecx.

[00:16:18]Let's say from rax plus0, write the address. And then we can move to maybe edex plus 4. So we get from offset zero the size put into ecx and we get the flag or the status into edx. And now we can print those values. So let's go down to the bottom and add another string. Uh maybe a block size string maybe in a little bracket.

[00:16:48]And then let's get two just single words here. Used, I guess. And we can close those brackets. And we can add a space.

[00:16:56]We're going to probably have these in a line, right? And we can do S free. And we can do free. And also with a little space. If we go back up now to print heap, then we can load that. So let's first load the block size. So let's load to RDI S block size. And ECX is the one that has that data. So we can move to our side rcx and we can call print f.

[00:17:21]And if we run this now I guess we can make a call and test it. So after we allocate the first time let's call print heap. And it doesn't loop yet. So it shouldn't get stuck in an infinite loop or anything like that.

[00:17:35]And I have a mispelling or something.

[00:17:38]Print heap exit. Is it not that print heap? Let's check. Print heap exit. Oh, I didn't have my colon here. All right, let's try that again.

[00:17:47]And print probably the same thing. Oh, I have a dot here. Let me remove the dots.

[00:17:54]And it's a bit hard for me to find where that actually printed out. I guess it's right here. I'm going to move it to the bottom to make it a bit easier to find.

[00:18:03]So after we do everything, right before exit, I'll do call print.

[00:18:10]Okay, so it is right here at the bottom.

[00:18:11]So it's found the size of that first block. Uh, we know it's 16 bytes and it found it. We can modify that. Let's make this like 96 and it should show us that there's 104 bytes, right? 96 plus the header size is 104. So, it is correctly finding and outputting that first block's header. So, it's able to read the information about itself that we've saved within the block. So, let's go back to our program and let's go back down to print heap. At this point, we have the size in ECX which we printed.

[00:18:45]So, we don't need that anymore. But edx has a flag. So, if we compare edx to the value of one, then we know it's free. If it's equal to one, then we can jump to block is free. And if it's not equal to one, then we know it's not free. Uh, but let's pretend let's fall through right here and write this code. So, if it is free, we're just going to load the string and say that it's free. So we'll load to RDI free and call print f. And then we're going to jump somewhere. I guess print heap next, right? Because next up we'll have the block is free. I have a mistake here.

[00:19:30]We're jumping if equal to is free. So this is really going to be used. And then down here we're going to load RDIS free and call print f.

[00:19:42]And then I guess we'll just fall through. Let me add some tags to uh print he next.

[00:19:50]So now we need to traverse to the next block. Right? So we have the starting block and we're going to use the size that we got from his header himself to shift forward now. Right? In this case it was 104. So, we're going to look at that first block. We're going to see it's 104 the whole size of the block.

[00:20:07]And we're going to shift now by 104 to get to the start of the next block. Uh, so we're just going to add to rax, although rax is not going to survive through all of these calls. So, we're going to need to make some local variables here. For now, I'll leave that empty. Let's make sure that we're printing out whether it's free or not.

[00:20:28]Uh, so let's run this. And here we have 104 bytes used. So, it correctly identified that this block is 104 bytes and that it's used. So, um that's great.

[00:20:41]Now, let's add in that traversal that we were talking about. So, squiggly period to go back to the last edition. And before we do that, let's actually add a little banner so that it's easier to find cuz it's kind of hard to to see it.

[00:20:55]So, at the bottom here, let's add a little banner like s uh heap dump maybe.

[00:21:00]And we can just put some marks here and keep dump. And then up here now let us print that. So let's load to RDI s heap dump and call print.

[00:21:13]And actually this should be before we set react.

[00:21:17]All right. So we have heap dump here.

[00:21:19]And now we can create some space on our stack to create a local variable because since we're going to go through all these prints, we really want to be able to keep our reax value steady so that we know where we are on the heap. It's going to get clobbered. So we need to make sure that we keep it right before we get in. We're going to push RBP.

[00:21:35]We're going to move the stack pointer to RBP. That's a standard function prologue. And then we're going to need to keep actually three values. Uh we're let's just say 8 bytes per value. says 24, but let's round it up to 16 by alignment, which is 32 bytes. So, let's subtract from RSB 32. And right after we set to the heap start, let's actually write that into our variable. So, let's set RB command 32X.

[00:22:05]So, we have it safe and sound on our stack. And then after we load these values, let's just move them to the stack as well. So, we're going to move now, let's say, to RBUS 24, right? Not 32. We want to give them all their own 8 byt sort of blocks to write to rcx and down here let's move to rb minus 16 rdx.

[00:22:27]So now that we're comparing edx to one, right? Because after that print rdx has probably been messed up. So let's restore it. So let's move to edx. What's that? RB minus uh 16 is what we had up here where we first set it. So we're going to restore edx. And now we can compare it and now it will be intelligent. Before it was probably just taking any you know whatever number was in there. So print heap next now let's move to orex what we have saved to restore it. And then we can just add tox what's I was going to say what's rdi. No not rdi. I was going to say what's rdx but we've just called printf here potentially. So I'm just going to load it itself. So I'm going to do RBP minus 24, right? Because that's where we are saving the size, right? Zero offset is the size of our header, right? Offset 4 is the flag. So offset zero, four bytes goes into ECX and we're putting that at rbus 24. So right here, we're just going to add that to rex, right?

[00:23:32]Cuz at the start of the current block, we're going to add the entire size of our current block itself to get to the next block. And after we do that, uh, let's update our saved variable with a new value after we'd made the addition. And we should be able to just jump to, uh, the print keep loop up there at the top right here. So, let's see what happens.

[00:23:59]So, we have a segmentation fault, but we did walk the heap pretty well. We had 104.

[00:24:06]We had 32. 56.

[00:24:10]16. 24.

[00:24:13]16. 16 16.

[00:24:20]And then we failed when we got to a portion that was not allocated.

[00:24:26]So, let's go back down and try to figure out where the mistake is. Find. Oh, I always make this this mistake. Uh down here on line 238, I am not uh basically tearing down our stack frame. I'm not unwinding our stack. So, let us move to RSP. Well, it's an RBP and let's pop RBP to restore our stack. And that seems to work a lot better. So, we do have our heap being printed out. All of our allocations being printed out very nicely. Now, we are still not printing the end of our of our heap, sort of the tail of our heap. So, let's add that next because we really want to show how much heap we have left over that's been unused, right? Even though there's no header there, we can still figure it out because we know where that heap pointer is and we know where the end is. So, if we make some sort of subtraction and figure out what's in there, we can at least print that out and say, "Hey, there's 2,000 bytes that are unallocated." Right before we exit, we can we can do that. So at this point we can move reax uh also what's in rbp no heap pointer is fine and we can move to like rcx actually we don't need to do that we could just subtract from rex oh I have this backwards heap pointer is what we want here we want heap end right so we get heap end into rex and we subtract the pointer and in between is the size uh we do need a string though so at the bottom let's do s maybe unallocated and I'll put unallocated space remain that might be too long uh this many bytes ra has a value that we want so we can move to rsi what's in rax and we can load that string s unallocated I think and then call print f all right all right so here we have 3800 bytes unallocated remaining. And I guess that makes sense.

[00:26:28]We can do the math, but I'm sure it's accurate, right? We're subtracting the heap pointer from the heap. And we could make some changes here. Let's delete some of these. And let's just make it so that we know we're going to have one page, which is 4,96 bytes. So, let's allocate maybe 8 bytes, which is really going to be 16. And then, you know, let's just allocate 96 bytes. But 96 is going to have eight bytes added to it.

[00:26:54]So, let's subtract eight. Let's do 88 bytes. And we should have 4,000 bytes remaining. So, here we have it. We have 96 bytes used, right? We wanted 88, but the header size took it to 96. So, that works well. I wish I didn't delete all that stuff to have to write them all back now. Let's Let's add a couple more here. I'll do all these weird numbers.

[00:27:16]All right.

[00:27:17]Oh, and my print heap now.

[00:27:23]Okay. So here's our dump and uh 2904 bytes unallocated and then here's our block. So block block block block.

[00:27:29]Perfect. So this is very helpful and now we can actually get to the actual free function which is funny how far it's been pushed back. But these are some of the things that we have to do. We can't just pretend that the memory has been written properly. We really need to verify. So this verifies that we're reading and writing to our headers properly. And now we can create that free function. So let's get to that. Go back to our program and let's add free.

[00:27:55]So maybe at the bottom, maybe down here, let's add free. So it's a new function.

[00:27:59]We need to kind of be careful here because when the user tries to free a memory block, it's going to be the payload address. And we already know that we have that secret header that he's not going to know about, right? If we shift it or if we shift eight bytes to the left, we have that information sort of reveal itself. So he's going to be pointing eight bytes further than what we want to look to get the size to know how many bytes are free, right?

[00:28:23]Although we don't really care how many there are. We just want to set the flag.

[00:28:26]The first thing we want to do is of course RDI is going to have the payload address to be free, right? So the first thing we want to do is subtract from RDI the uh header size. Right? We shift back revealing the header. And all we really want to do, we don't really care about the size. All we really want to do is write to the flag that it's free, which is a one. So, we're just going to move to RDI + 4, right? Again, plus 0 offset is the size, plus four offset is the flag. The value of one. And I guess we need to set the word pointer so it knows that we're talking about four bytes. And I think that's it. And then we just return. It's like a baby function. And now we could just call this. But we need to of course set a argument to call it, right? And we're not saving any of these addresses.

[00:29:27]We're just pretending that they don't matter. But really a real program, of course, a real user, a uh a real requesttor of memory would be saving these addresses so he could free it. So let us I guess just free this one, right? The second address that we get, we know it's going to be an RAX, right?

[00:29:44]So payload pointer is in RAX. So let's just move RAX to RDI and call free, right? So we're not even touching the memory. We're just getting it and we're immediately freeing it. But let's see if that works. So let's call print pair.

[00:30:05]Oh, that's going to mess up our reax.

[00:30:08]So, let's push rex.

[00:30:11]Pop rex. And this is our little comment.

[00:30:14]I'll put that here. So, we push rex. We call print. We pop rex. Then we call free. And then let's call print heap again. And we should hopefully see a nice little story happening here. So, we have two blocks that are used. Then we called free. And look at that. The second heap dump has 16 bytes free.

[00:30:35]Isn't that wonderful? So we have this one's still used, but we freed the second one. And we can see right that our system is not quite there yet because at the end our final heap dump we have used. This one is still free after we created it. And then used used.

[00:30:51]So ideally what we would have is for this guy to use this block. Although he is too fat to fit in here. He's 48 bytes and the the slot is only 16 bytes. So this would actually never happen, but that's the idea, right? So let's um let's make it sort of doable that way.

[00:31:08]Let's let's make this a bigger block. Uh let's say 128 bytes so that the next ones would fit in here. So we use 136 bytes, which is I guess the 128 plus the 8 bytes for the header. And then we freed it right here. We called free and then this guy really should go in here.

[00:31:26]Uh so that's the functionality that we have to that we have to add. But this looks great. So free works. Um, and this also just reinforces the idea that when you delete something on your computer, it's all about just flags being set, right? Like unless you go in and scrub something, it's just setting a flag saying, "Hey, this memory is available and and that's it." Uh, we're not actually going to go through and zero stuff out. That would just take way too long for a sort of system utility that we're trying to to make here. So, let's continue.

[00:31:58]I'm going to add another string real quick for the end of the heap.

[00:32:05]Uh, heap dump end. Try and make it a little bit better. So, where is our heap dump? Right here. So, let's load to RDI heap s dump end and call print.

[00:32:23]Getting too long. I'm going to try to even these out.

[00:32:28]All right, that's a little bit better here. So, what we need to do is write a function that can take a size argument and it will find us a free block of a suitable size and if it doesn't find one, it can just return null and we can allocate the way that we do now with the bump allocator at the end of the current heap pointer. So we either find a free block that fits the requirement that we need or we just go to the end of the line and join write our own header write our own new block. So let's go down to the bottom with shift G. Let's make a function called find free block. RDI is going to have the minimum block size required. Right? So it's going to be very similar to our print heap. We're going to prime our reax with the heap start and we're also going to have a loop. So we'll do find free block loop. Let me just go down a bit to get some more space. We're going to compare rex to heap pointer. Same thing. We probably could use that function and adapt it a bit, but I'm going to write it fresh here again uh since we have a very specific goal in mind. Then maybe after we can do some cleanup. Greater than or equal to. We're just going to jump to find free block exit.

[00:33:47]And maybe we should be a bit more explicit actually. Block not found is probably a bit more descriptive. So if a free block is not found, let's uh let's add that in. So free block not found is going to return null or zero. So we'll just clear out and return. But if X is on a valid position, a valid block of memory that we've written, then we can check to see if it's free. We're going to compare four bytes at rex + 4, right? Because at the start of the header, zero offset is a size, but we want to know if it's free. So rex + 4 to I guess one. And if it's not equal, right, if it's not free, if it's not a one, then we want to move to the next block. Let's say, so down here, let's add next block. And we're going to move, let's say, to ECX racks plus zero, right? We're going to move the size into ECX so we know how much to append just like we did in print heap.

[00:34:51]Then we can add tox which is a pointer to the start of the block what we just loaded into ecx which we now we can use rcx and then we can jump to the next one. So find free block loop we can just repeat the process right if it's not free then we get the size of where we are of the whole block we we jump forward we add that to get to the next block and then we go up to the top to loop. So rax is very stable here we're not really doing any sort of printing.

[00:35:20]So, RX continues to hold the pointer where we are and we can just add to it right here and then we we loop again.

[00:35:27]But if it is free, then we need to check if the size is suitable for us, right?

[00:35:33]Does it meet our minimum block size, which is an RDI? So, let's compare what's in RDI, but we want only the four bytes, right? Because we've just used it as a four byte value. So, EDI is a lower four bytes of RDI. We're comparing EDI to the size. So the four bytes at rex plus0 and you could just put rex but I'm I'm just going to always keep plus 0 + 4 to make it sort of self-documenting that we're talking about offsets.

[00:35:59]And so if the minimum size required the argument right is greater than the size of the block that we're currently at then it's a fail. We need to go to the next block. So jump if greater than right if our argument is greater than the size of the block then it's it's too small. So we're going to jump to next block as well. And really we should do jump if above. So jump if greater than is signed values which allows negatives. But we're really dealing with pointers and memory addresses. So jump if above is better.

[00:36:32]This is for an unsigned comparison. And there's probably many other places that I need to update this but I just remembered here. So if the block is too small, right? If what we need is greater than what this block is and it's too small, we go to the next block. But if it is suitable then we can return with this pointer. I think we just return because reax is already pointing at the block. So if we check if it's free yes and we check if it suits our size our minimum size. Yes. Then we just return.

[00:36:59]Rex is already pointing to the start of that block. So we do need to set an argument. Let's test it out. Let's go to the top here. And right here we we free that second block. We know that we're always freeing that second block just cuz we have it here in code, right? and we allocate once, twice, and then we free it. So right after we free, let's see if our new function finds it. So that second block is 128 bytes. So let's move to RDI. Let's say 32 bytes, right?

[00:37:26]Let's say we want to find 32 bytes. And we'll call find free block.

[00:37:31]And now should contain a pointer to a valid block, a valid free block or null, which is zero. Um, so we can print it, but we need to go down and make a string to print. So I'll just put it here.

[00:37:45]Print find free block result now in orange. So at the bottom, let's create a new string here.

[00:37:54]Maybe s free block found, I guess.

[00:37:57]Although that kind of indicates that we're always going to find a block.

[00:38:00]Maybe a free block result. A free block found. Although that kind of does what I just tried to avoid, but it's fine. It will either be null. If it's null, we know it's nothing. Let's go back up to the top and right here we can load to RDI S free block result and call for gap.

[00:38:20]I have way too many gaps here. So here we have our second allocation and then free block found at D5 402 1d5. It ends in a very odd number. So no, there's a problem here. Oh, did I not set the argument? I don't think I set the argument. Yeah. So move RSI RX.

[00:38:41]Yeah, I forgot to do that. This makes more sense. So we requested, right? We had the first one total size 96 as a first block. And then the second block we requested 128. Total size 136. The address is 2060, right? 228 A260.

[00:38:58]Payload is at 68. And this is 136 bytes.

[00:39:01]So we have that allocation go through 136 bytes used. And then we free it, which we don't really have a message when we free, but we do have free block found picking it up right here at 228a26. So it does pick it up, which is great. And then we can see that the next print does show it as free, but we're still of course not using it. We found it now twice in two functions, but we're not using it yet. So let's let's continue. And actually what before I do that, I'm going to start commenting out all these prints because we know that our maloc works and we have our heap printing now. So we kind of don't need all these different print statements. So I'm just going to do a search for print f. And here I'm going to comment I'm going to press period which will repeat what I just did. I'm not going to modify anything else. I'm just going to comment the actual print. This one also can also be killed. The heap end and this one.

[00:40:00]All right, that seems to be an error. We can keep of course. All right, so let's run this again. So this is a lot cleaner now. What happens if we run print heap without anything? Will it bomb or does it everything should be zero. So it should just unallocated space remaining zero bytes. I mean he's not wrong.

[00:40:19]That's before we have anything. So we have the start. We could say it's kind of silly to print that, but whatever.

[00:40:24]Let me let me remove that. But it's interesting to see it. And I think I'm going to remove some of these extra lines here just to clean this up a bit.

[00:40:32]That's like a little a little bad. Kind of embarrassed.

[00:40:37]Now it looks worse. So now that this function here, find free block, is able to find a free block, what we need to do is incorporate that into Maloc itself.

[00:40:47]Because as we know, our maloc loves to just allocate, allocate, allocate. But he needs to now learn that, hey, sometimes there's free blocks behind you, like stop looking that way, like look behind you and see if there's free blocks and fill them in. So, it should be minimal code really. We get the request in for what the user wants. We align it. We still want to do all that, right? We we really want to get to that actual block size needed. So, we get the request, we align it. We add the header size. We still want to do that. And only when we have the actual block size needed do we check to see if there's a free block somewhere that we can use. So the question is where do we insert this?

[00:41:26]Well, here we save our value back to RD.

[00:41:28]I think right here makes sense because this is where we calculate how far our heap will be to accommodate the next request using the heap pointer and and incrementing it by the size. So this is only done if we don't have a free block.

[00:41:42]So this is kind of that spot where we can determine what method do we want to use to accommodate this request. So at this point all we're going to do is call find free block to figure out do we continue uh going through this right pushing back that heat pointer checking if we're out of space allocating more space if we need to or do we just write into a header that a block has now been used and return that address of the payload. So after we call find free block, we know that rex is going to contain the address or null. So let's compare rax to zero. And if it's not equal to zero, right, we want to we want to make sure we fall through in the most efficient way. So if it's not equal to zero, meaning that it found a valid address that we can use, then we want to jump away to somewhere out of nowhere. But if it if it did not find a free block, right, if it is equal to zero. So we're jumping away if it's not equal. If it is equal, we fall through and the rest of the code should just work. Nothing else changes, right? There's no free block. Do as you do, guy. Like go allocate as much as you want. Be your little bump allocator. I think that logic is pretty sound. So we do need to jump away. So if it is not zero, then it's found a valid free block and we can reuse it. I guess that's probably a decent name. So let's do maloc reuse block. And we have to remember that we've just called a function and returned and rdi and rax. Well, rax is being loaded here. RDI was loaded right here. So oh, and this is with our size, right? I forgot to mention that. And I think that's an accident. Did I write that or that was already there? We're setting that minimum size that we need.

[00:43:33]Uh so what we should do is after we return even though I don't think fine tree free block writes to RDI maybe it does it may be fine let's let's reload that let's move to RDI RBQ 16 just to make sure that this dude I have a P missing um that you know he's reloaded for this stage of code because I don't really quite remember what find free block does if it you know messes the RDI and we may add on in the future. So we need to figure out where we put maloc reuse block. So reuse block needs to skip everything that happens in the bump allocator stuff, but we do want to return an address. So let's go back down to where we return stuff because it's probably going to be around here. Right here, reax has the address of the block and then we're adding the header size to it to get the payload for the user. This is when we're doing the bump allocator.

[00:44:24]But we we also want this done when we have the block found by find free block because it points to the start. So we still need to offset it to the payload.

[00:44:31]So this actually might be the perfect spot right here. And actually the line right above two because we do need to write oh man. And this raises up an interesting point. So we do need to write to the block that it's no longer free, right? The the second field four bytes in four four byt offset is the answer to the question are you free? So if it's a zero it is not free and it's used. So, we do need to write this line of code or include this line of code for the reuse block. But what we don't want to do is write the size to it because we will get a nasty memory leak. Not really a leak, but like a bug. It's kind of a leak. I don't know where, let's say we had a block that was 32 bytes for the original allocation and we free it and then we reuse it. Let's say some guy has 16 bytes. So, he moves in, he's like, "Oh, this is a nice house. 32 bytes."

[00:45:22]Like, we have extra space. If we write the size of the current user to it, then it would write 16 bytes to that header even though we have 32 bytes and we would just go on forever thinking that that memory block is not big enough for anything that's let's say 32 bytes but it would be so we would mislabel it. So we need to make sure that anytime we we reuse a block we do not touch the size.

[00:45:44]The size should be the size. We don't touch it but we do of course write to the flag. So the only time we write to a size is when we actually allocate the original block when we create that block so to speak out of that unused heap space. So right here I think is good.

[00:46:01]We're only writing to the flag and we're going to offset the payload so we can return that to the user. So let's put maloclock reuse reuse block right here. Our regular allocation will just fall through which is fine. And I'm here thinking that I have to do something else. Is that actually it? Because we call fine free block. He gives us an address. We write into rax + 4 which is fine, right? He gave us an address which is an ex. We write that it's taken. It's used. It's no longer free. We offset by 8 to move to the payload. Then we return. I think this may be it. The layering of these things is working really well in our favor right now. So here's our current story. We have two blocks used. We freed this guy and then we allocated. There used to be a this guy right from before.

[00:46:54]The 48 bytes has disappeared. We used to have four blocks at the end. Now we only have three blocks because they reused this guy. So 48 bytes is using up this block. So that's great. That worked out really well. Let's do another test. I guess this looks very messy right here.

[00:47:12]So let's just delete this all.

[00:47:14]Let's do some more allocations. Say eight.

[00:47:20]So we have a bunch of allocations here.

[00:47:21]How about before we do 16, let's free the first one. Let's just push it the return value of this maloc call. And then here's our allocation that ends up being 16 bytes, right? 8 plus the eight bytes in our header. So let us pop to RDI. Let's call free. Let's call print keep. And then let's see now if that guy disappears. I think it did. It used to go down to the next line. So we had 96 136 1032 16 40 and now there's no more 16, right? Because he went in this guy who was free. So we allocated two times, we freed this guy, we put somebody another allocation was made and then we freed him and we reused him. So this is working very very well right now. Uh now there is of course one issue that we can sort of detect here that even though 16 bytes was needed is now taking up the entire 96 bytes which is kind of a waste. We can imagine if that first allocation was let's say 1,024 it's increased to 1032 for our header.

[00:48:28]Then we free it but then it's being used up by that tiny little 16 bytes. So ideally in the future if you have that sort of mismatch where you only need a small amount but the block is huge you would split it into like two blocks. Uh so maybe we'll add that on in the next video. But this is working really well.

[00:48:50]Now it's worth highlighting that when we had our bump allocator working it was one of the fastest memory allocators that we're likely to have. And funny enough, by turning into this method, even though we've gained functionality, we're actually probably at the slowest allocator that we'll have because our allocator right now is strictly dependent on the number of allocations that we have. Uh, and I by that I mean the speed. Imagine if we had a million allocations.

[00:49:25]Right now, we need to go through every single block until we find one that's free and the right size before we return anything. The bump allocator did not care about anything like that. Bumper allocator said, "I'm putting you at the end." Um, no checks necessary. Whereas in this case, we're trying to be efficient and that requires a bunch of processing. So, if we had a million blocks here, we'd be checking every single block until we found one. And if there were no blocks, then every single allocation would cost us the traversal of a million blocks of memory. And that's not really great, right? So, we're going to continue to add on to this allocator. But it's just kind of funny to me that we started with the absolute fastest and we're probably right now at the absolute slowest. But let's see what else we can add. And I actually don't like this label anymore.

[00:50:10]I thought I would have to add a lot more code right here. And we didn't have to.

[00:50:14]So, I'm just going to call it return block because you really want this label to work for both branches to make sense for both branches. It didn't kind of make sense for the original bump allocator branch. So, let's just do return block, which makes a lot more sense. That's what we're doing here.

[00:50:31]We're setting it as in use, shifting to the payload, and returning over here.

[00:50:36]But, this is kind of what I wanted. We have our free working, and we're able to reuse memory. Uh so the next step is really being able to split those big blocks to make smaller blocks out of them when we have a tiny amount of space needed but we have a very big block available. But that's it for me uh tonight. It's been very fun. I hope you're having fun building out this program. So uh we'll continue in the next one and add on some more features and hopefully make our allocator a bit more usable. So thanks again for joining me. I appreciate your time and I will see you