class: center, middle ### COMP26020 Programming Languages and Paradigms Part 1: C Programming *** # Dynamic Memory Allocation ??? - Hello everyone - In this video we will talk about dynamic memory allocation, allocating memory space at runtime --- # Motivation - Many scenarios where an array size is **determined only at runtime** (vs. compile time) .leftcol[ ```c int main(int argc, char **argv) { if(argc != 2) { printf("Usage: %s <array size>\n", argv[0]); return -1; } int size = atoi(argv[1]); int array[size]; // variable size array for(int i=0; i<size; i++) { array[i] = i; printf("array[%d] = %d\n", i, array[i]); } return 0; } ``` .codelink[<a href="src/variable-size-array.c" download>`11-dynamic-memory-allocation/variable-size-array.c`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/9xPVXnuEKrv2o" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] ] .rightcol[ - Variable size arrays are rarely used due to support and space restrictions - We need another solution ] ??? - So until now we have only worked with data that is allocated statically - This means that the amount of memory space reserved for all the variables we used is determined at compile time - But there are some scenarios in which the amount of space needed is only known at runtime - Here is an example with a program taking an integer as command line argument and allocating an array which size is based on that number - Size is only known at runtime and thus this is a variable size arrays - They are rarely used in C because they have many downsides - They are not supported in some versions of C - Most importantly, they are stored on a location in memory called the stack, that has very limited space - For example if you try that program with a large number you will get a memory error because you will overflow the stack - So we need another solution --- name: layout # Program Memory Layout ```c *int large_array[10000000]; int process_array(int *array, int size) { /* do some stuff with array */ } int main(int argc, char **argv) { int size; /* check argc ... */ size = atoi(argv[1]); if(size < 500) { /* Make sure small_array does not overflow the stack */ * int small_array[size]; process_array(small_array, size); } process_array(large_array, 10000000); return 0; } ``` .codelink[<a href="src/memory-layout.c" download>`11-dynamic-memory-allocation/memory-layout.c`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/8SqmVKszQ6Nqw" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] ??? - Before explaining dynamic memory allocation, let's talk a bit about how the program memory is organised - We take this example program manipulating 2 arrays - We have a static one, with a relatively large size, declared as a global variable - And we have a variable size array for which we make sure that the size is not too big --- template:layout <div style="text-align:center"><img src="include/layout.svg" width=800 /></div> ??? - In memory things look like this - We have an area named the static memory that contains many things and in particular the global variables - Its size can be very large - And the size of what is contained in there is determined at compile time - For example the size of large array is 10 millions of ints and it won't change - Now there is another area called the stack and it is small -- 2MB on Linux - Most allocation sizes there are also fixed at compile time, although we can have variable size arrays too --- template:layout <div style="text-align:center"><img src="include/layout2.svg" width=800 /></div> ??? - And then we have a third area called the heap - It has a large size and all allocations there are realised dynamically at runtime --- # Allocating on the Heap: `malloc` ```c #include <stdio.h> #include <stdlib.h> // needed for malloc int process_array(int *array, int size) { /* do something with array */ } int main(int argc, char **argv) { int *heap_array; /* ... */ int size = atoi(argv[1]); * heap_array = malloc(size * sizeof(int)); * if(heap_array == NULL) return -1; process_array(heap_array, size); * free(heap_array); return 0; } ``` .codelink[<a href="src/malloc.c" download>`11-dynamic-memory-allocation/malloc.c`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/4CcauFYXepIvE" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] <div style="text-align:center"><img src="include/layout3.svg" width=800 /></div> ??? - There is a function used to perform dynamic memory allocation on the heap - It is called malloc - We have an example of usage here on the slide - We declare an int pointer that will point to the array - Then we call malloc - Malloc takes one parameter, the size in bytes of the space we want to reserve - Here it's size -- the size of the array we wish to allocated in elements, multiplied by the size of one element, that is size of int - Malloc will allocate a contiguous memory space and returns a pointer to it - A very important thing to do is to check the return value of malloc - It can be NULL if the system runs out of memory - If you don't check and continue execution you will get nasty bugs - One last thing to know about dynamic memory allocation is that the programmer is responsible for releasing the allocated memory - This is done with the free function, as parameter a pointer that points to a space previously allocated with malloc - It is important to free up memory as soon as you are done with it - Otherwise you are holding memory for nothing, it is called a memory leak --- # Allocating on the Heap: `malloc` - **`malloc` allocates a chunk of memory on the heap and returns a pointer to it** - Memory is contiguous and can be used as an array - Returns `NULL` (0) if the allocation fails - **Always check the return value** ```c void *malloc(size_t size); void free(void *ptr); ``` - `void *`: generic pointer type - `size_t`: long unsigned int ??? - So you have a small summary on this slide - Remember to always check the return value - You'll notice the type of the pointer returned by malloc, void * - It's a generic type so malloc can be used to allocate data that will be pointed by pointers of all types - A last thing to remember is to free memory once you are done with it --- # Allocating on the Heap: `malloc` ```c double *ptr1; int main(int argc, char **argv) { int *ptr2; ptr1 = malloc(10 * sizeof(double)); ptr2 = malloc(30 * sizeof(int)); if(ptr1 == NULL || ptr2 == NULL) { /* ... */ } /* ... */ free(ptr1); free(ptr2); return 0; } ``` .codelink[<a href="src/malloc2.c" download>`11-dynamic-memory-allocation/malloc2.c`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/05xo40y1xVheW" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] <div style="text-align:center"><img src="include/pointers.svg" width=800 /></div> ??? - Heap memory can only be accessed with pointers - Let's look at this example - We have a global variable pointer ptr1 - and a local variable pointer, ptr2 - So ptr1 itself resides in static data - and ptr2 on the stack - We make two calls to malloc to reserve two buffers on the heap - Of course we check that the allocations succeed - And now we have ptr1 pointing to the heap at 0x40, and ptr2 also pointing to the heap at 0x230 - Don't forget to free memory when done --- name:2d # Multidimensional Arrays and `malloc` - 3 x 2 `int` array ??? - To allocate multidimensional arrays you need to proceed as follows - Let's say we want to allocate a 2D int array of size 3 by 2 elements --- template: 2d <div style="text-align:center"><img src="include/2d-1.svg" width=700 /></div> ??? - We declare an int star star variable, that is a pointer of pointer of int - let's say it's a local variable on the stack --- template: 2d <div style="text-align:center"><img src="include/2d-2.svg" width=700 /></div> ??? - With malloc we create a first buffer and have array point to it - Its size is equals to the first dimension of the array we wish to create, 3 - Array is a pointer of pointers of int so in that buffer We will store pointers of int - Remember that we can index the content pointed with the square brackets so we can refer to these pointers as array of 0, array of 1, and so on --- template: 2d <div style="text-align:center"><img src="include/2d-3.svg" width=700 /></div> ??? - Next we allocate three buffers with malloc and have them pointed by the 3 pointers - These were pointers of int so the 3 buffers contain the actual type we wish to store in our array, int - There size is equal to the second dimension of the array, 2 - We can use the original pointer named array and the square brackets to index the array in the exact same way we would do with a static array --- # Multidimensional Arrays and `malloc` ```c int a = 3; int b = 2; int **array; array = malloc(a * sizeof(int *)); if(array == NULL) return -1; for(int i=0; i<a; i++) { array[i] = malloc(b * sizeof(int)); if(array[i] == NULL) return -1; } array[2][0] = 12; /* ... */ for(int i=0; i<a; i++) free(array[i]); free(array); ``` .codelink[<a href="src/malloc-2d-array.c" download>`11-dynamic-memory-allocation/malloc-2d-array.c`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/82EgAjpyefgjn" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] ??? - Let's look at the code, it's very simple - We declare the original pointers as int star star - Allocate the buffer that will contains 3 pointers of int - Then in a loop, we allocated with malloc 3 buffers that will hold the array content - Let's not forget to check all of malloc return values - And to free each buffer when done --- # Memory Leaks - Don't forget to free memory! ```c void print_ten_integers() { int *array = malloc(10 * sizeof(int)); if(!array) { printf("cannot allocate memory ...\n"); return; } for(int i=0; i<10; i++) { array[i] = rand()%100; printf("%d ", array[i]); } printf("\n"); /* array is neve freed, leaking 10*sizeof(int) of memory each iteration */ } int main(int argc, char **argv) { int iterations = atoi(argv[1]); for(int i=0; i<iterations; i++) print_ten_integers(); return 0; } ``` .codelink[<a href="src/leak.c" download>`11-dynamic-memory-allocation/leak.c`</a> <a href="https://github.com/olivierpierre/comp26020-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/7c2pyT9yQgJ1d" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] ??? - When you forget to free memory it is called a memory leak - Such wasted memory is inefficient and can lead to crashes when the system runs out of memory, for example with long running programs such as servers - In this example we allocated memory with malloc but never free it, creating a leak --- # Memory Leaks - Valgrind is a useful tool to detect memory leaks - Let's try it on the program from the previous slide: ```bash gcc -g src/leak.c -o leak valgrind --leak-check=full ./leak 10 # ... ==11613== ==11613== HEAP SUMMARY: ==11613== in use at exit: 400 bytes in 10 blocks ==11613== total heap usage: 11 allocs, 1 frees, 1,424 bytes allocated ==11613== ==11613== 400 bytes in 10 blocks are definitely lost in loss record 1 of 1 ==11613== at 0x483577F: malloc (vg_replace_malloc.c:299) ==11613== by 0x109196: print_ten_integers (leak.c:5) ==11613== by 0x109294: main (leak.c:32) ==11613== ==11613== LEAK SUMMARY: ==11613== definitely lost: 400 bytes in 10 blocks ==11613== indirectly lost: 0 bytes in 0 blocks ==11613== possibly lost: 0 bytes in 0 blocks ==11613== still reachable: 0 bytes in 0 blocks ==11613== suppressed: 0 bytes in 0 blocks ``` ??? - Valgrind is a very useful tool to detect leaks, amongst other features - We can run it on our faulty program here - For Valgrind to work correctly, your program needs to be compiled with additional debug metadata so use the -g flag when calling gcc - Valgrind reports the amount of bytes leaked, as well as the line in the sources of the corresponding calls to malloc --- ## Summary - Malloc and free for dynamic memory allocation - Don't forget to: - check malloc's return - free everything you malloc ---- .center[Feedback form: https://bit.ly/3AsW3cZ] <div style="text-align:center"><img src="include/qr-code.png" height=150 /></div> ??? - Let's recap - We saw the malloc and free functions for memory allocations which size is unknown at compile time - Do not forget to check malloc's return value to avoid bugs - And to free everything that you malloc to avoid leaks - In the next video we will talk about the C standard library