[MUSIC]. Hello everybody. My name's Jeremy, and I'm going to be showing you how to get started on the Malloc Lab. number five for this class. so I have my terminal, and my lab five tar all ready, so I'm going to untar that. [NOISE] And it's going to, you know, produce a bunch of files, and we'll get into the lab five directory that I've made. And, so you see we have a bunch of files. And the only ones that you need to really worry about are mm.c and the README, in case you're looking for information about the lab itself. So if you look at the README, it will show you just some information about the files and how to do stuff. so you always want to look at your README's, of course. so let's look that in mm.c. open that in emacs, because we're going to be, updating it in the course of this lab, and that'll open up. So, we've got our source file, mm.c and open in emacs here. And so this is the starter code, your going to have to go in and fill in some function's, to make it actually do what it's suppose to do. so we're going to be implementing the memory allocator malloc. And the general overview of that is that, you have, as we talked about, you have heap in memory, and malloc is the program that allocates and deallocates space on the heap as the program requested. So there's two methods in malloc that we are going to be implementing. Malloc, right here, and, whoops, mm_free, right here. yeah. So, what malloc is going to do, is allocate a block on the heap of a certain size. Whatever size the user specifies, and then it's going to return the pointer to that memory. And then when the user's done with that, they'll call free on that same pointer, and malloc, and the malloc system will put it back into the pool of free memory, that can be allocated. So, the two functions that you're going to be implementing in this lab are malloc and free. And malloc is kind of the more simple one. we give you some code to start with, and it's going to, basically just take, a block of the size, and return a pointer to it. And that, that's not too hard. for purposes of this lab. The harder part, is for free, to take the, pointer to the memory that the user is done using, and put it back into the pool of allocatable memory onto the heap. And to keep track of all those different flocks of memory, we're going to be using a doubly linked list. As you can see in the source files at the top, there's a kind of a ascii picture of that here, and it summarizes the structure and the structure definition is just below. so we're going to have this doubly link list. So you have, like a link list, you have a element and a point to the next thing. But, with a doubly link list you just have two pointer's. One to the next thing, one to previous thing. So that makes it really easy to traverse the list, back and forth when you're looking for the thing of what, whatever appropriate size. And with that there's going to be mostly in the free method, a lot of management that you're going to have to do, to keep the link list, the doubly link list of the free blocks consistent and helpful. Because you're going to have to smash blocks together, if their right next to each other, or split them if they're too big so that's what free is going to do. And, all this is going to have a lot to do with manipulating pointers. There's a lot of code in the source file that is already provided. So, you have functions for coalescing free blocks, removing free blocks, inserting free blocks into the list. And searching the list for a block of a certain size, and you're going to be using all of those to implement malloc and free. So once you're done writing your malloc implementation, and you want to test it we provide the mdriver program the source files in mdriver.c, that you can use to test your malloc implementation. And you're going to make that, with a make and it's going to produce this mdriver program. To test your malloc implementation you just run mdriver. And, of course, my malloc implementation doesn't exist, because I just untied it just now. So, of course, it fails every test. the mdriver program also has some options that you can use to generate more detailed information, and you can find that by using the H flag. So that's a general overview of how you're going to implement and test your malloc. pointers are kind of hard, so you may get frustrated in this lab, but don't worry about it. It's, it's a challenging lab so good luck and have fun.