Memory management in C: The heap and the stackLeo FerresDepartment of Com puter ScienceUniversidad de Concepci´[email protected] 7, 20101 IntroductionWhen a program is loaded into memory, it’s organized into three areas of memory, called segments: thetext segment, the stack segment, and the heap segment. The text segment (sometimes also called the codesegment) is where the compiled code of the program itself resides. This is the machine language representationof the program steps to be carried out, in cl ud in g all functions making up the program, both user and systemdefined1. Thus, in general, an ex ec u table program generated by a compiler (like gcc) will have the followingorganization in memory on a typical architecture (such as on M IPS )2:Figure 1: Memory organization of a typical program in MIPSwhere3• Code segment or text segment: Code segment c ontains the code executable or code binary.• Data segment: Data segment is sub divided into two parts– Initialized data segment: All the global, static and constant data are stored in the data segment.– Uninitialized data segment: All the uninitialized data ar e stored in BSS.1http://ee.hawaii.edu/~tep/EE160/Book/chap14/subsection2.1.1.8.html2http://129.107.52.7/cse5317/notes/node33.html3http://www.boundscheck.com/knowledge-base/c-cpp/memory-layout-in-c/342/1• Heap: When program allocate memory at runtime using calloc and malloc function, then memory getsallocated in heap. when some more memory need to be allocated using calloc and malloc function,heap grows upward as shown in above diagram.• Stack: S tack is used to store your loc al variables and is used for passing arguments to the functionsalong with the return address of the instr uc ti on which is to be executed after the fu n cti on call is over.When a new s tack frame needs to be added (as a result of a newly called function), the stack growsdownward.The stack and heap are traditionally located at opposite ends of the process’s virtual address space.The stack grows automatically when access ed , up to a s iz e set by the kernel (which can be adju s ted withsetrlimit(RLIMIT_STACK, ...)). The heap grows when the memory allocator invokes the brk() or sbrk()system call, mapping more pages of physical memory into the process’s virtual address sp ace.Implementation of both the stack and heap is usually down to the runtime/OS. Ofte n games and otherapplications that are per f ormanc e critical create their own memory solution s that grab a large chunk ofmemory from the heap and then dish it out internally to avoid relying on the OS for memory.2 StackStacks in computing architectures are regions of memory where data i s added or removed in a last-in-first-outmanner4. In most modern computer systems, each thread has a reserved region of memory referred to asits stack. When a function executes, it may add some of its state data to the top of the stack; when thefunction exits it is responsible for removing that data from the stack. At a minimum, a thread’s stack is usedto store the location of function calls in order to allow return statements to ret ur n to the correct location,but programmers may further choose to explicitly use the stack. If a region of memory lies on the thread’sstack, that memory i s said to have been allocated on the stack (see Footnote 4).Because the data is added and removed in a last-in-first-out manner, stack allocation is very simple andtypically faster than heap-based memory allocation (also known as dynamic memory allocation). Anotherfeature is that memory on the stack is automatically, and very efficiently, reclaimed when the function exits,which can be convenient for the programmer if the data is no longer req ui r ed . If however, the data needs tobe kept in some form, then it must be copied from the st ack before the function exits. Ther e for e, stack basedallocation is suitable for temporary data or data which is no longer required after the creating function exits(see Footnote 4).A call stack is composed of stack frames (sometimes called activation records) . These are machinedependent data structu r es containing subroutine state information. Each stack frame corresponds to a callto a subroutine which has not yet terminated with a return. For example, if a subroutine named DrawLine iscurrently running, having just been called by a subroutine DrawSquare, the top part of the call stack mightbe laid out like this (where t he stack is growing towards the top)5:Here are a few additional pieces of information about the stack that s houl d be mentioned6:• The OS allocates the stack for each system-level thread when the thread is created. Typically the OSis called by the language runtime to allocate the heap for the application.• The stack is attached to a thread, so when the thread exits the stack is reclaimed. The heap is typicallyallocated at application startup by the runtime, and is reclaimed when the application (te chnicallyprocess) e xi ts .• The size of the stack is set when a thread is created.4http://en.wikipedia.org/wiki/Stack-based_memory_allocation5http://en.wikipedia.org/wiki/Call_stack6http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap/80113#801132Figure 2: Stack fr ame for some DrawRectangle program• The stack is faster because the access pattern makes it trivial to allocate memory from it, while theheap has much more complex bookkeeping involved in an allocation or free. Als o, each byte in thestack tends to be reused very frequently which means it tends to be mapped to t h e processor’s cache,making it very fast.• Stored in computer RAM like the he ap.• Variables created on the stack will go out of scope and automatically deallocate.• Much faster to alloc ate in comparison to variables on the heap.• Implemented with an actual stack data structure.• Stores local data, return addresses, used for parameter pass ing• Can have a stack overflow when too much of the stack is used. (mostly from inifinite (or too much)recursion, very large allocations)• Data created on the stack can be used without pointers.• You would us e the stack if you know exactly how much data you need to allocate befor e compile t imeand it is not too big.• Usually has a maximum size already dete r min ed when your program starts.Some implementation examples are the following:3• In C you can get the be ne fit of variable length allocation through the use of alloca, which allocates