Memory Leaks "the hell of dynamic memory allocation"

The computers that we use now a days fall under two general classes of architectures. The Harvard architecture and the Von Neumann architecture. In the Harvard architecture program instructions are stored in a different memory namely the code memory and data stored in the data memory. That way instructions and data do not mix. Most embedded system designs use the Harvard architecture. One main disadvantage of the Harvard architecture is the increased number of bus lines makes design very complex for increased memory capacity because you have to maintain address and data lines separately. In the Von Neumann architecture, program instructions and data are stored in the same memory. Bus lines are multiplexed for both data and instructions. Software and hardware (registers) are used to make the distinction between program instructions and program data. Because computers are getting more complex by the day the memory model and memory management techniques used by the operating system to keep track of memory should change accordingly. This brings us to virtual memory.

Virtual Memory

Virtual memory is a memory management technique used by the operating system to provide a per process view of memory such that, from the processes perspective it has all the address space in memory at it's disposal. The operating system is able to do this my means of data structures it maintains in kernel memory space. Virtual memory does not correspond to physical memory. Virtual memory is mapped to physical memory by means of data structures called page tables. Virtual memory is divided into blocks corresponding to the system page size. Different blocks in virtual memory can map to the same physical memory. Since virtual memory is the program view of memory, pointers to blocks in virtual memory constitute virtual addresses. The CPU's memory management unit (MMU) performs virtual to physical address translation. With this ultra brief primer on virtual memory, lets talk about a programs layout in virtual memory during execution.

NB: This is a gross over simplification of what virtual memory is. There are a lot of material out there that provide detailed explanation.

Program layout in virtual memory

As explained in one of my video posts, The compiler generates object code of the input files and passes the object codes to the linker, the linker then collects all the code and data from the different object files and combines them into the final executable. Due to security and efficiency reasons, the linker combines data and instructions separately into their own regions on disk. The linker then appends headers to the finally generated executable so that when we attempt to run it the OS loader would know how to parse and load it to memory. Program instructions and program data are stored at different locations on disk called sections. Each section has an associated section header that tells the loader the size of the sections data, it's type, whether it's loadable or not, whether the memory page where its loaded should be readable, writable or executable, disk offset to the section's data etc. The section where program instruction goes is the text or code section. Initialized global variables are stored in the data section. Uninitialized global variables are stored in the bss section. Mind you bss means block started by symbol. Both the bss and data sections are fixed in size. The OS also allocates memory to be used by function calls. Variables created inside functions are allocated on the stack and are called automatic variables.

Stack is a last in first out (LIFO) data structure that has only two well defined operations a push and a pop. A push is when you add data on top of stack and pop is when data is removed from the top of the stack. Variables allocated on the stack are called automatic because the compiler emits assembly instructions that automatically allocate and deallocate memory before and after a function call.

Heap memory is another memory space that the OS reserves for a process. Heap memory is managed by the user. Heap memory allows your program to increase memory at runtime. Its used for dynamic memory allocation. Memory allocations for the data and bss sections are static, in the sense they are allocated for at compile time. Stack memory is allocated sequentially one block after the other and freed in the reverse order. Heap memory can be allocated and deallocated in any order. Heap memory can be increased by making system calls to the OS kernel to allocate more memory to be used by the process. This is where things get interesting, These system calls makes the OS search through virtual memory look for a first fit unallocated block and then allocate it. The OS then updates its page tables to mark the memory pages as allocated. Unless you explicitly tell the OS to free dynamically allocated memory the OS would never free it until your program terminates (Not necessarily for embedded system OS) . So for a long running program that makes a lot of heap allocations, your OS would lose valuable memory (even run out memory) that could have been allocated to other process if they were freed. That is what we call memory leaks. Because you are allocating memory that you cannot free.

Lets take an example to see memory leaks in action. This example is Linux specific, so windows users should use WSL to compile and run it. I used Kali Linux VM with gcc compiler. Copy the code below into any file and name it memory_leaks.c or whatever name of choice.

1 | #include <stdio.h>
2 | #include <stdlib.h>
3 | #include <unistd.h>
4 | #include <time.h>
5 | #include <string.h>
6 | #include <sys/resource.h>
7 |
8 |
9 |
10|  
11|
12|
13|
15|
16|
17| int main(int argc, char* argv[])
18| {
19|? ? struct rusage usage;
20|
21|
22|? ? char* block = NULL;
23|? ? size_t mem_size = 4096*1000; // This is on purpose
24|
25|
26|? ? 
27|? ??
28|? ? for(;;)
29|? ? {
30|? ? ? ? puts(" Getting resource usage");
31|
32|
33|? ? ? ? getrusage(RUSAGE_SELF, &usage);
34|
35|
36|? ? ? ? printf("Current memory usage %lu\n",usage.ru_maxrss);
37|
38|
39|? ? ? ? block = malloc(mem_size);
40|? ? ? ? memset(block,-1,mem_size); //Ensure OS commits to physical memory
41|
42|
43|? ? ? ? //free(block);
44|
45|
46|? ? ? ? sleep(5);
47|? ? }
48|
49|? ??
50| }        

On Linux (Don't know about windows) you can measure and monitor the amount of memory that your process consumes. We can get this by means of the getrusage function in sys/resource.h header file. It accepts an enum of type __rusage_who_t which specifies which process' resource usage information we want to collect. And the last argument is a pointer to a struct of type rusage. It makes system calls to the kernel and collects the necessary information we need and populates the structure with these info. There are several fields in this structure most of which are not used. Our field of interest is the ru_maxrss, which is the maximum resident set size. The memory space of our process is divided into two, resident memory and non-resident memory. Resident memory is the pages in our memory space that exists in physical ram, non-resident memory are pages that have been swapped to disk. But we want all the memory pages that belong to our process which is the maximum resident set size, that way we can accurately gauge how much memory our process is using.

We created a for loop, that never ends, and for each iteration we allocate 4000Kb of memory. To ensure that the OS commits the allocated virtual memory to physical memory we write -1 into every byte of the allocated block. we then check our resource usage and print the the maximum resident set size to screen.

Compiling with gcc via the command below

gcc memory_leaks.c -o memleaks.elf && ./memleaks.elf        

With line 43 commented out we should an output like this

You can clearly see that the memory usage is increasing for every iteration. Now lets uncomment line 43 and lets see.

Here you can see the memory usage increased twice and it stopped increasing. But why ? Because of memory leaks. Lets see what is happening. We declared a char pointer named "block". When the program reaches the for loop, we allocate a block of memory of size 4000Kb. we return the pointer to the memory block to the variable "block". Therefore the variable "block" holds a reference to our memory block. For the next iteration and every other iteration we overwrite the pointer that references our allocated block so that we have no way of freeing it. Since we keep doing this forever, either our OS would terminate the program or the OS would run out memory. But if we uncomment line 43 we realized that the usage went to a halt after sometime. Because we kept free each block for every iteration.

Thanks very much for reading. Like and comment. Corrections and suggestions are welcome.