[MUSIC]. All right, so let's see our last topic in the Memory Allocation section now. Which is going to be about memory bugs in C, memory related bugs in C, and how to deal with them. And how complicated and nasty they can be. Okay. there are many, many problems in manipulating memory and pointers in C okay. You could dereference a bad pointer, you could read memory that was uninitialized, you could override memory without noticing. You could reference non-existent variables, you could free a block multiple times. you could reference free blocks, so you get garbage that was in memory, whatever, whatever was there. Or it might fail to free your blocks and exhaust your memory and so on. Okay. So let's talk about dereferencing bad pointer. Okay. So here's what's happening here. We declare a variable val, and we call scanf, which just reads something from intput and stores it in val. Okay, and but what we're supposed to have done here is to have. Past the address of val just kind of as opposed to val. But the problem here is that in the best case, in the but it's going to have us to know, it's going to interpret that as a value and it's going to consider that a pointer. So in the best case, your program is just going to terminate immediately and because of a seg fault, it's going to cause a seg fault. But in the worst case, the contents of val actually corresponds. To some valid read write area of memory that you're going to do it in. And later in the actual program, you're going to have some problems, not good, evil, hard to find, complicated. So be careful that when, when you pass a value as a parameter, make sure it actually, and it happens it's going to be interpreted as a pointer. Make sure it's actually passing as a pointer as opposed to some other random value. Okay. The other problem that happens often is just reading uninitialized memory. 'Kay? So, here. Suppose that I have this vector y here. Like it allocates space for it. Has you know n, n ints. 'Kay, as. Enough space for n ints. But I don't I don't initialize it. And here, when I'm doing y of i, plus equals, and whatever the, the rest of expression. I'm implicitly reading y, because it going to be y equals y plus the rest of the expression. So when I read y, whatever was there before, for the first time I read it, it's just going to be, whatever was there. Some garbage. So it's going to affect the computation and leads, for surely, to bad results. 'Kay. So do not assume that the, the free blocks in the heap when you allocate it they're going to be initialized to zero. Unless you use a function that calls it. Like c alloc for, c alloc for example initializes to zero. 'Kay, but normally people don't do it because it's it's it's expensive. Okay. So the other one, it might be overriding memory because there's many ways of overriding memory. And one of them, we're going to tell you a bunch of those now. But the first one is, you allocate a possibly wrong size object. For example here, i of p, which is supposed to be point of pointer, a vector of pointers, okay? N elements, N pointers. to the size of int, okay? So, but later here, I'm going to assign to p of i, another pointer, but look at what I allocated here? Hmm, It's an int as opposed to an int star. Bad, right? So why this potentially overwrite memory? Well, first of all, whenever I'm doing this, this if this is a 64-bit machine. This is going to so int star is 64 bits. Okay, so this is a 64-bit assignment okay. Not good, it's going to overwrite memory, okay. you can also, another one that's pretty common is off by one error, okay. Again, suppose I had the same example there and now I actually have to write. the right object size n star so that's not a problem. But the problem here is that in this loop I'm going from 0 to n, so I'm assuming that it's going to, so this loop's going to actually traverse n plus one elements. But we only have n. So the last write here, which is going to be p of n, is overriding whatever is after n in, after p in memory. Okay? So it's going to override stuff there. For sure, not good. 'Kay? Now, the other problem is not checking the size of a string before you write it. 'Kay, so here's an example. You have you de-, you declare a, a array of 8 bytes in your stack. 'Kay? And then you pass it as a parameter to get s. And then you go and read the string. That goes on, that one, two, three, four, five, six, seven, eight nine. 'Kay? And we have one extra byte here. With the slice here. This already ten bites, but I have only had eight. It's going to overwrite stuff in your stack. Can, can, it can potentially effect even the return pointer in the stack. And, in fact, this is the basis for classic butter-overflow attack. You pass something that's bigger than what's expected end up overwriting things on the stack. And you're going to have, actually, we're going to play with that in one of your assignments, okay? So you might also overwrite memory by misunderstanding pointer arithmetic. For example, if you have a function called search. Okay? And you pass up the parameter pointer p, pointer to it. N, a value, val. And this, this loop here, just up. So this going to be, then we going to have, an array of int's in memory. And p points to the first element. And then this loop, it's going to traverse this int look at each one to see that it matches val. Okay,but, and the way that we're doing is that every iteration of group we're going to make p bump to the next one, the next one and so on. But what I'm doing here, I'm actually adding size of int's. But since we're already told the comparator p is an int because that how it is declared here, the comparator is already doing implicit multiplication with the size of the object. So there's going to be size of int by size of. It's going to be bumping the pointer by more than it should. Okay? And then when you return it, it's just going to, first of all you're going to reach stuff, grab from memory, and then you going to go and return it. Which could be used in a way, and over written, and that's going to overwrite memory. Again, not good. Here's another one. when you reference a pointer you want to make sure that you actually referencing what you expect. Okay? So if you reference a pointer as opposed to the object it points to that could be a problem. So here's an example. When I call, when, when I execute sta size minus, minus here, I am not decrementing the value of size which is clearly what intended in this code. I'm decrementing the size of the pointer first, okay? So just pointing somewhere and then when it passes the parameter, I am not going to get what I expect. Okay, we're going to be pointing whatever comes before size in, in memory. And that's because the operators minus, minus and star have the same precedence and therefore, we go from right to left. Okay? So, the decrement happens first. That's not what it, what, what was intended. 'Kay? That's all so be careful when you use those operators. Now, the other problem is if you return a pointer to something in your stack, okay. So in this example, I have variable val which is using foo's its going to be allocated in the stack. Okay? And I going to return its pointer. As soon as I return this pointer the location of foo permit ends and the stack frame is freed. That means it might be there but later, when you use it, that could be easily overwritten when you do more function calls. So be careful with that too. Never return a pointer to the stack, unless it's some very, very special circumstances. But even then you, you should find other ways of not doing that. So another problem that could happen with pointers just you free a block multiple times. Okay, dangerous. So for example if I allocate a piece of memory in n, it is example and store into x and manipulate and then later I manipulate I free x after being done with it. Then I allocate something at y, and then it happens to call free x again but what if this was allocated in the same position and I freed. Hmm, that might actually freeing y just because it happens to be in the same place, okay? So in free, it won't return any elements here because it could, could be there's still a valid block in that case. But it's not and you want to free that, so be careful, okay? So be careful when calling free and make sure that you're not calling twice. And in this case it's a problem because you have reallocation that could haven't, happen to be freer. So just call free only ones for each object. Okay? So the other problem is referencing free blocks. This is just evil. Be careful. Okay? So again similar to what we have before, we allocate a bunch of memory, put in the x, manipulate it and then I free it. And the later, I refer x again, data might still be there but it could have been, it might have been overwritten. Because if I do a malloc here, I could use memory just freed by this one. Just like the previous one, okay? And now, when I do x here, it might affect, in fact be y here, you never know. So it could be something and so be, be careful not to reference memory that you have freed, okay? So that can't happen. So the other problem's what we call memory leak. When you allocate something, so you, you allocate and you use it. And then, so in this case, this pointer's going to be dead. Right? Because I, the only pointer. I don't return any pointers here, so. And the pointer, to, what I just allocated is, is on full stack, when full returns. That's, that's gone. But I haven't freed it, so I no longer, I'm no longer going to know the pointer so I can't free it. So that's a problem. So, memory leaks are really a long long term killer and is slow and silent. Okay, be careful because it eventually going to exhaust your heap without noticing it. now another problem that happens and that might leads to failing to free blocks and lead to memory leaks is the only free part of a data structure. Okay, for example, suppose that we have a struct here called list, it has a certain, its linked list, right it has a value as a payload here and a pointer. Okay, and then, when we create this list, you know, create a head here, allocate size of struct, okay? And then I, I set a next here to, to know, to not point into anything, just actually, when I'm allocating here, I'm allocating space for both the val and the pointer. Okay? I going to create and manipulate the rest of the list, but then it just free heads. But for each element, I'm going to do a a malloc. But when I do free head, I'm just going to free the first one. So you have to be care, not the rest, so you have to be careful to, if you have a link list. And you're going to allocate each element of the link list in the separately. When you freed, you free all of them. You traverse and free all of them, otherwise it going to have memory leak. 'Kay? So there are many ways of dealing with well I wish there were many ways. There's just a handful of ways of dealing with memory bugs. It can use the debugger, gdb. 'Kay? So it's good for finding bad pointer references, but it's hard to detect other memory bugs. For example, memory leaks are hard to, to, to detect to find with debuggers. So, there's a special version of malloc. For example the University of Toronto's CSRI malloc. it has special features, okay? It's a wrap around the typical malloc and it detects several memory bugs, okay? So at the boundaries of mallocs and frees, okay? So it detects things like memory overrides that, that corrupts heap structures. it detects some instances of freeing blocks multiple times. It detects memory leaks, you know, if you free it and go, if you malloc and go free it might alert you, and so on. But it cannot detect all memory bugs. Okay? So it cannot detect overwrites into the middle of allocated blocks, because it doesn't monitor all of the reads and writes to memory. Okay. It does it's hard to, to detect freeing block twice. It has been allocate, reallocated in the interim because we saw one of these problems on the earlier in this video. And if you allocate it again something that if you are going to free it again it could be that what is reallocated. Don't really know that, that didn't, you're actually freeing twice so that's actually very hard to find. And also does not detect. Referencing freed blocks because it can only detect things at the boundaries of malloc and free calls. Now, it does instrument all of the memory, all of the memory accesses, okay? So there is, there is another one. There is this tool called val, valgrind that actually does binary instrumentation. Of your program actually moni-, monitors much more of the execution. So it's pretty powerful, okay? It actually rewrites the text of code to, to do special things. And it, and it can check each, so and since it examines your whole program, it can check each individual reference at run time. Things like bad point over writing, and referencing outside of allocated block and so on. And by the way, some malloc implementations contain some check code. Okay, so you can actually set. See, if you use the Linux glib malloc library, you can set an environment variable that's going to check some some of the calls to the memory allocater. Okay, equivalent things are developing for FreeBSD. Well, this concludes our section on memory allocation. And I hope you learned what you should avoid in writing C code with pointers.