CS50x Week 5

Memory in a program

Diagram below represents the memory segments of a running program:

Memory segments of a running program by Ling Gen Sheng Shaun
Memory segments of a running program by Ling Gen Sheng Shaun

Text

This segment has 1s and 0s.

Initialized data

This segment has global variable.

Unintiailized data

This segment has global variable.

Heap

This segment is for dynamically allocated variable allocated by malloc function. When malloc is called, the function grabs some memory, and needs to be able to hang on to it without losing control over it, so put on heap, if on stack, it will be removed as soon as it returns. The variables in heap will stay in heap until free() is called.

Stack

When function is called e.g. main, function call, a stack frame is added (containing the function’s variables). Many stack frames layers on top of each other. If there is a need to change data across layers, you need to use pointers. When a function returns, the stack frame is removed.

Environment variables

Function call, added to stack

when main calls foo(), a stack is formed, and each time foo() calls itself recursively, a stack is formed, the stacks are never going away (because there is no return step), so when the stack frames overstep the bounds of segment of memory (stack gets to the segment of heap), a segmentation fault error will occur.

Recursion is not necessary good, because we have limited room in stack and will hit other segment of memory.

Function call, added to stack by Ling Gen Sheng Shaun
Function call, added to stack by Ling Gen Sheng Shaun

Changing data across stack frames

From previous week’s When is pointer used? E.g., we learnt pointer’s importance in changing a variable and not just its copy. Let’s see what is really happening in memory when we use a pointer.

For the fail swap case, the visualisation is as follows:

Swap fail without pointers by Ling Gen Sheng Shaun
Swap fail without pointers by Ling Gen Sheng Shaun

For the success swap case, the visualisation is as follows:

Swap succeed with pointers by Ling Gen Sheng Shaun
Swap succeed with pointers by Ling Gen Sheng Shaun

In the fail case, the swapping occurs within swap() stack frame, the variables a and b in main() stack frame is not changed, so when swap() gets returned/ swap stack frame gets removed, the main() variable remain unchanged. In the success case, the swapping occurs across stack frames with the use of pointers, the variables a and b in main() stack frame is changed, so when swap() gets returned/ swap stack frames gets removed, the main() variable is already changed.

Freeing Dynamically Allocated Memory

When malloc is called, memory is dynamically allocated. The memory is stored in heap. Since the memory in heap is not returned, the heap will get filled over time, you can see the effect when your computer is on for a long time, it will get slow, because some memory is not returned. A tool called Valgrind (memory checker) can be used to check for memory leak (memory that never get returned).

Used Valgrind, memory leak at char* name = GetString(), to return it, we call free(name). Free (return memory) can be thought of as opposite of malloc (give memory).

main() is called and a stack frame is added. Next, f() is called, malloc allocate 40 byte and is stored in heap. The pointer x at stack is pointing to the first address of the 40 byte of memory at heap. x[100] = 50 is buggy, because there is only 10 ints, so number is assigned to an unknown memory. When Valgrind is used to check, it will say invalid write of size 4 byte. Besides that, Valgrind also let us know that we haven’t free the memory given by malloc.

Stack overflow/ buffer overrun/ buffer overflow attack

For e.g., when a function asks for a user input, and the array initialize to store the input is not large enough, memory below the stack will get overridden. If the memory overridden is a return value, then the bad code will get returned instead, and bad things will happen. They can get access to memory that they are not supposed to.

Refer http://en.wikipedia.org/wiki/Buffer_overflow for more information.

typedef

typedef is a keyword in C. It gives name to a new data type.

For example, typedef char* string; gives the data type char* a new name, string. So, the next time you want to call char* test, you can call string test instead.

Another use of typedef is in structure. A structure has variables of different data types, e.g. int, float char.

Above defines a struct account data type with 4 members. You can declare a variable of data type struct account using struct account myAccount. To simplify things, you can do the following:

This will turn your struct data type with 4 members to account data type, so you only need to type account myAccount to define a variable myAccount with above struct data type.

Other posts in the series: Harvard CS50x 2014

Leave a Reply