Stack vs Heap in C Programming (PDF)

CST8234 – C Programming Stack vs Heap (Brief Intro)  How the Function–Call Stack works? ❑ STACK CONCEPT: ▪ Last-In, First-Out (LIFO): The last item added (pushed) to the stack is the first one to be removed (popped). ▪ Think of it as stacking dishes: you add...

CST8234 – C Programming Stack vs Heap (Brief Intro)  How the Function–Call Stack works? ❑ STACK CONCEPT: ▪ Last-In, First-Out (LIFO): The last item added (pushed) to the stack is the first one to be removed (popped). ▪ Think of it as stacking dishes: you add new dishes on top and take them off from the top. ❑ Purpose in Function Calls: ▪ Supports the mechanism for calling and returning from functions and keeps track of where to return control after a function execution is complete ❑ Stack Frames: ▪ Each time a function is called, a stack frame is created and pushed onto the stack. Stack frame contains Return Address and Local Variables. 2  How the Function–Call Stack works? ❑ Returning Control: ▪ When a function completes, its stack frame is popped off, and control transfers to the return address stored in that frame. ❑ Memory Limitations: ▪ Supports the mechanism for calling and returning from functions and keeps track of where to return control after a function execution is complete ❑ Stack Frames: ▪ The stack has a finite size, which means there’s a limit to how many stack frames can exist simultaneously. ▪ Exceeding this limit results in a stack overflow error, which occurs when there are too many nested function calls. 3  How OS invokes ‘main’ (1/3) 4  How OS invokes ‘main’ (2/3) 5  How OS invokes ‘main’ (3/3) 6  Flaw in previous discussion FORGOT about PRINTF being a function too! main calls printf, then printf calls square printf’s argument values must be known in full before printf can be called FLOW 1. OS Calls main: pushes main’s stack frame onto the stack 2. Main Calls square: pushes square’s stack frame onto the stack 3. square Calculates a Value: square performs its computation and then returns this value to main. This pops square’s stack frame from the stack. 4. main Calls printf: Value form square, main calls printf, pushing printf’s stack frame onto the stack 5. printf Executes and Returns: printf processes its arguments, displays the output, and then returns control to main, popping printf’s stack frame from the stack. 6. main Terminates: main completes its execution, which pops its stack frame from the stack, and control returns to the operating system. 7  Memory Organization Two places where data can be stored in memory Stack Heap You can choose where to store the data, but you have to be specific to the complier. 8  Heap ❑ A big block of memory that is used to store global variables, memory that you explicitly/implicitly allocate and some literals. ❑ The heap allows programs to allocate memory at runtime. ❑ Memory allocated on the heap persists until it is explicitly freed. ❑ You can allocate different sizes of memory blocks as needed, making the heap suitable for data whose size can change during execution. ❑ Accessing memory on the heap can be slower than stack memory because it involves more overhead (like searching for free memory blocks). ❑ Over time, if you frequently allocate and free memory, you might encounter fragmentation, where free memory is scattered in small blocks, potentially making it difficult to allocate larger contiguous blocks. 9  Heap - Allocating ❑ As you implicitly or explicitly allocate memory, you are given the pointer to the best chunk (closest match in size), and the heap table is updated as follows: ▪ If the amount of memory you need matches an existing free chunk ▪ the address of the chunk is returned to you, and the chunk is marked as allocated/in-use ▪ Otherwise, a bit of an existing free chunk is split off as a new chunk, with a new starting address and a size equal to the amount of memory you’re requesting, and the original chunk’s size is decremented to accommodate the amount split off ▪ the address of the new chunk is returned to you, and the new chunk is marked as allocated/in-use 10  Heap – Freeing ❑ When you ‘free’ the allocated memory ▪ The chunk in the heap table that had been created for you is marked as unallocated/free, ▪ Then, either ▪ If the location of your now-free chunk is NOT adjacent to another free chunk, it is left as is (but can be re-allocated the next time you need that amount of memory) ▪ If the location of your now-free chunk IS adjacent to another free chunk, the location and the size of the two chunks are merged to create one large free chunk ❑ There is NO Java-style garbage collection! 11  Heap – Pitfalls YOU are responsible for free’ing all the memory you allocate Memory leaks are a problem, and require discipline (and comments!) about who should be doing the free’ing Fragmentation is a possibility You could potentially riddle the heap with an alternating sequence of free and in-use chunks, so that even though the SUM of the free chunks is enough to satisfy your next malloc request, there may not be enough adjacent free chunks! “Out-of-memory” error Data overruns are a risk C will happily let you write data beyond the end of your allocated chunk Thereby corrupting the data in an adjacent chunk! REALLY tough to debug! 12  Stack ❑ A continually changing block of memory that is used to store ▪ Local variables ▪ Function arguments ▪ Variables defined in the function, or in statement block ▪ The location in memory where execution (in the calling function) should continue after a ‘return’ 13  Stack – Tracking Usage ❑ There is a single CPU register (“stack pointer”) that tracks the current location of the next free location in the stack ❑ Typically, it’s manipulated each time you call a function ❑ Each time data is put on to the stack (at the current address in memory defined by the stack pointer), the stack pointer is decremented by the appropriate amount. ❑ The compiler generates all the code that takes care of pushing stuff onto the stack ❑ You DON’T have to! ❑ The compiler generates all the code that will appropriately re-increment the stack pointer to the state it was in before you called a function ❑ You DON’T have to! 14  Stack – Ephemerality Values in memory in the stack aren’t permanent The same memory will be re-used by the next function call You CANNOT count on any memory persisting beyond the program execution E.g., the following will NOT work!!! char* getName() { char name;  created on the stack scanf( “%s”, name ); return name;  rewinds the SP, so that now ‘name’ is below the SP } int main( int argc, char *argv[] ) { char *myName = getName();  points to vulnerable place on stack printf( “%s”, myName );  overwrites stack, clobbering ‘name’ } 15  Stack – Pitfalls Data overruns are a risk C will happily let you write data beyond the end of any array Can then even overwrite return address of function! when you try to return, the information has been corrupted. “Stack Clobber” error. Stack overflow is a possibility Endless recursion will consume all memory, or Cause the stack pointer to enter an allocated chunk Stack/Heap Collision 16