[MUSIC]. We're now starting a new section. We're going to be seeing how to manage memory. How, how to further allocate memory as they run, so they can use it for their data structures. 'Kay? So this section is a little long. It has quite a few parts to it. Okay? We're going to start with a, with a quick intro right now and then we're going to see how dynamic memory allocation works. How and the reason we need dynamic memory allocation, is because the size and number of data structures may be only known at run time, dynamically. 'Kay? And then we're going to see how we implement that, that dynamic memory location in a number of ways. We're going to look at something called garbage collection which automates a lot of the memory management process from the programmer's point of view. And then we're going to see how memory related bugs really can make your life hard and how, what are some of the common memory related bugs you see. that happening so you can avoid them in your code. Kay? So what is Dynamic Memory Allocation? The first thing to realize is that it's often impossible for a program to know how much memory it's going to need, until it's actually running. Let me give you an example. Suppose that you write a piece of code that takes whatever the user's typing on the keyboards and stores it in memory. Well, until the program runs, it doesn't know how much the user's going to type. So it doesn't know how much memory it's going to need. 'Kay? So and therefore, it's not going to locate it on the stack. So we're going to, we're going to allocate this in a pa, in the region of the, the memory layout of the program called the heap. 'Kay? So the heap is where dynamically allocated memory goes. It's a region of the heap that where when programs allocate memory dynamically, that's where it's allocated from. 'Kay? So the programmers use dynamic memory allocators such that it can acquire memory at run time. They can acquire pieces of it's address base at run time to store data. 'Kay? Again, this is for data structures that's only known at run time. For anything that's known statically, it can allocate this in, in a different part of memory. We're talking about the heap is everything that's allocated explicity. 'Kay? And we going to be using something called malloc as a dynamic memory allocated which I'm sure you've seen. So the dynamic memory allocators, they manage this part of the other space, as I said, called the heap, at this region here of your address base. That's where all of your regions of memory are allocated with, with malloc go. So let me tell a little bit more about the allocators. Kay? So as I said, the allocators maintain a, a heap. Right? The heap is a collection of blocks. 'Kay? They can be of different sizes, and these blocks can either be free or allocated. 'Kay? So, and these blocks reside in the heap, and the heap region itself might have to grow. Because if the program uses a lot of memory, the region's set aside, the region of the other space set aside. So the heap might not be large enough so the process has to request to the operating system more chunks of the address, of the virtual address space, to to have the heap there. 'Kay? So C application objects are typically smaller than pages. The allocator manages blocks within pages. 'Kay? So but that's not a restriction, applications could have objects much bigger than pages, but typically they are not. So the allocator, so this is not done by the operating system. This allocator runs in user space and manages the actual smaller blocks then, that's that's, that forms the heap. 'Kay? So there's two basic types of allocators, called the Explicit allocator, where applications both allocates blocks and frees the block. That's, that's what malloc and free does in C. That's explicit because the program explicitly requests, and explicitly free up them. There's also something called Implicit allocator. So in thi, using this allocator the application request memory, allocates memory, but does not free, because that's done automatically. 'Kay? And this is what garbage collection is in say, Java ML and Lisp. So you are going to be looking at the malloc package, this is part of the standard C library, and here's what malloc does. Malloc receives a size of the parameter, that's the size of the block that's going to be allocated. And it returns a pointer that doesn't have a type, because we don't know what, what kind of data is going to be there.? 'Kay? So, if it's successful it, it returns a pointer to the new memory block, that has at least size bytes. 'Kay? And if the size is equal 0, it returns NULL. 'Kay? Because then, why are you allocating if the size is 0? Right? Now, so, and if the, if malloc cannot find enough free memory to, to allocate the requested block, it returns NULL and sets an error number. So you know why that happened. And now, free doesn't return anything, but it takes a parameter of pointer p, that is a pointer to the beginning of a block. 'Kay? So and p must come from a previous call to malloc or realloc, but a realloc just resizes the, the size of a block. 'Kay? And what free does, it returns this block pointed by p, back to the available pool, so it could be used in the future. So let me give you an example. by the way, the, the other functions are also calloc that is a new another version of malloc that sets the allocated block to 0. Realloc just resizes the block. And sbrk is using internally by the allocator to grow or shrink to size of the heap, that's the system call. 'Kay? So now I'm going to give you an example. Suppose I have my function called foo here it has two parameters int n and int m, and what we are doing here, and there is a pointer p here. When we call malloc, what malloc's going to do is going to get in, and multiplied it by the size of int, its going to allocate an array of int. 'Kay? So this is an int, and its going to have in elements. So the size of this array is, n multiplied by the size of int's, and that's what we passed some malloc. It's the number of bytes we want to allocate. And since we're going to be stored int's, storing int's, we cast the pointer returned by malloc, to a pointer to a, a pointer to an integer, to an int star. 'Kay? So if p is NULL, that means there was a problem with malloc, and the process exits. All right? Malloc may, may not have found enough free memory. But if it, if it doesn't, if it's not new, that means that right here we have a valid pointer starting p. So now we can execute a loop that just populates that this, this array here with 0, 1, and so on. 'Kay? So, but now let's say that this wasn't enough. So we could do, we could call realloc. Which retakes p, the original block, the pointer original block as a parameter, and takes a new size, and what it does is it just resizes the block. It returns a new pointer. Okay? Which might not be the same. So, and now we can go and extend it. We can write more elements so, so realloc just extends the array here. And then we can go and start using these again. And now we're going to print a new array, and so on. 'Kay? See you soon.