Introduction
One of the fundamental things you need to know as a software engineer is how the stack and heap work. Today we will address one of the most common questions which is what happens when the stack and the heap collide.
Having a lot of experience in the field and knowing the challenges that it presents I can assure you that understanding where those collide and being able to navigate that can help you greatly into optimizing your code but also having a better conceptual view of your applications memory profile.
Stack and heap are two parts of a program’s memory space. The stack is used for static memory allocation to store local variables and function calls, whereas heap is used for dynamic memory allocation, i.e. allocation and deallocation during run-time.
When the stack and heap collide, it means that both memory regions start overlapping with each other. This can lead to several issues, such as the ones listed below.
Buffer Overflow
If a program writes data beyond the allocated boundary of a buffer in the heap or stack, it can corrupt the adjacent memory locations used by another variable. This can result in unpredictable behavior, such as crashes or incorrect results. This is not to be confused from security coding errors which do not allow a higher memory buffer to be allocated for a write but the effect both is the same. Essentially this could very likely be from a programming error but also from an exploited vulnerability.
As you can see above when the program starts overwriting data in the stack basically important information about the function is being destroyed which could result into a crash. More particularly since the return address is also stored in the stack if that gets overwritten with a random value the program will try to return execution in the wrong address and that will cause an abrupt termination of your application.
Similarly you could be overwriting important things such as the saved frame and stack pointer which are restored at the function closure routine so a wrong overwrite of this will completely destroy any references to saved variables and even a stack frame parameters of your function.
Memory Leak
If a program fails to release dynamically allocated heap memory, the memory may stay allocated indefinitely, leading to a memory leak. Eventually, the program will run out of available memory, and either crash or slow down significantly.
The above case of stack overflows has a very similar effect here but the difference is that you are basically killing your application by a thousand cuts. Let me explain what I mean by that. Essentially your application is slowly leaking memory and as time passes by it builds up to the point that you will run out of memory space and potentially crash.
Additionally the performance of your system will be highly impacted to the point that you cannot longer run other applications as your existing one will be exhausting the entire memory space of your system.
If you check above the address space of your application basically the sequential free mapping results into a page fault as a result of the virtual memory address mapping. This is a very good example of how things can go south and get unpredictable leaks in your app since the pointer gets destroyed and you have no reference of clearing it out.
Pointer Errors
If a pointer variable is misused, it can point to a location beyond the allocated boundaries of the heap or stack, leading to bugs and crashes.
Essentially when you end up having a pointer that’s pointing to the wrong address it is known as a dangling pointer. This essentially means you can now have side effects in your application because your pointer is wrong. A good example of that is trying to free the wrong address it will result basically in a segmentation fault and have an abrupt termination of your application.
Additionally you can have a mismatch when you are doing comparison of data such as strings. Since the dangling pointer will be pointing to garbage it will fail and result into execution issues as altering the path of your logic since the byte comparison will have failed.
Below are some examples that could cause stack-heap collision in a program:
Example 1
void func() {
int *ptr = (int*) malloc(sizeof(int));
int val = *ptr;
free(ptr);
}
In this example, the function func() allocates memory on the heap using malloc(). However, it also tries to access memory on the stack without initializing it first. This can lead to unpredictable behavior if the stack and heap overlap.
Example 2
void func(int size) {
int arr[size];
int *ptr = &arr[0];
*(ptr + size + 10) = 20;
}
In this example, func() declares an array on the stack and allocates a pointer variable to point to its first element. It then writes data beyond the allocated boundary of the array using pointer arithmetic. This can lead to a buffer overflow if the stack and heap overlap.
Example 3
void func(int *p) {
int arr[10];
p = &arr[0];
}
int main() {
int *ptr = NULL;
func(ptr);
*ptr = 10;
}
In this example, the function func() tries to modify a passed pointer variable in the caller function. It allocates an array on the stack and assigns the pointer variable to its first element, effectively overwriting its original value. When main() tries to use the pointer variable after calling func(), it can result in unexpected behavior if the stack and heap overlap.
Example 4
void func() {
char *str1 = "Hello";
char str2[] = "World!";
strcat(str1, str2);
}
In this example, the function func() concatenates two strings: a string literal on the stack and an array on the heap. However, the string literal does not have enough space to hold the contents of both strings, so the string operation can overflow beyond the allocated boundary of the string literal.
Example 5
void func() {
int *ptr1 = (int*) malloc(sizeof(int));
int *ptr2 = ptr1 + 10;
free(ptr1);
*ptr2 = 20;
}
In this example, the function func() allocates memory on the heap using malloc(). It then uses pointer arithmetic to create a new pointer variable that points to memory beyond the allocated boundary of the first pointer. After freeing the first pointer, it writes data to the second pointer. This can result in memory corruption if the stack and heap overlap.
Example 6
void func(int *p) {
int *ptr = p;
free(ptr);
}
int main() {
int *ptr = (int*) malloc(sizeof(int));
func(ptr);
*ptr = 10;
}
In this example, the caller function main() allocates memory on the heap using malloc(). It then calls func() and passes the pointer variable as an argument. func() re-assigns the passed pointer variable to another pointer on the stack and frees the heap memory. After returning to main(), main() tries to use the freed pointer, which can result in undefined behavior if the stack and heap overlap.
Example 7
void func() {
char *str1 = "Hello";
char *str2 = (char*) malloc(sizeof(char) * 20);
strcpy(str2, "World!");
strcat(str1, str2);
free(str2);
}
In this example, the function func() concatenates two strings: a string literal on the stack and a dynamically allocated string on the heap. It then frees the heap memory used by the second string after the concatenation is done. However, the string literal does not have enough space to hold the contents of both strings, so the string operation can overflow beyond the allocated boundary of the string literal.
Example 8
int* func() {
int arr[10];
return &arr[0];
}
int main() {
int *ptr = func();
*ptr = 10;
}
In this example, the function func() declares an array on the stack and returns its first element as a pointer variable. main() assigns the returned pointer variable to a new pointer and writes data to it. However, the array is allocated on the stack and has a lifetime that extends only for the duration of the function call. After func() returns, the memory occupied by arr[] becomes invalid, which can result in undefined behavior if the stack and heap overlap.
Conclusion
If you want to master the control flow of your application and better understand how memory allocation and separation between the heap and stack works it’s worth to spend a bit of time going through the examples mentioned above. As soon as you get a good grasp of these concepts I promise to you that your application will become much more efficient and easier to handle when debugging and understanding the root cause of the potential points of failure.
Related
- Does Hyperthreading Cause Latency
- Why Stack Is Faster Than Heap
- What Is The Hardest Thing in C Programming Language