59

Possible Duplicate:
What and where are the stack and heap?

With regard to the basic concepts of memory layout in a c program, I understand the that:

  • The language uses two primary data structures stack and heap.
  • Stack is created to store the local variables and book keeping data of subroutines
  • Heap is created to store the dynamically allocated variables of the program
  • Heap is of variable length in nature.(Not very sure on stack)
  • Normally it is the responsibility of the compiler/Language to request the OS to create these data structures before the execution.

Questions

  • What is the initial size with which a stack/heap is created? and who decides it?
  • Wherein physical memory are they are created? I see a general description as "Stack is created in the top-level-address and the heap at the low-level-address" Please elobarate this
trincot
  • 317,000
  • 35
  • 244
  • 286
Vivek Maran
  • 2,623
  • 5
  • 38
  • 52

4 Answers4

69

"Stack is created in the top-level-address and the heap at the low-level-address" Please elobarate this

This is a myth. It may have a basis in historical truth. It might sometimes resonate with things you see in real life. But it is not literally true.

It's easy enough to explore, though:

#include <stdlib.h>
#include <stdio.h>

void check(int depth) {
    char c;
    char *ptr = malloc(1);
    printf("stack at %p, heap at %p\n", &c, ptr);
    if (depth <= 0) return;
    check(depth-1);
}

int main() {
    check(10);
    return 0;
}

On my machine I see:

stack at 0x22ac3b, heap at 0x20010240
stack at 0x22ac0b, heap at 0x200485b0
stack at 0x22abdb, heap at 0x200485c0
stack at 0x22abab, heap at 0x200485d0
stack at 0x22ab7b, heap at 0x200485e0
stack at 0x22ab4b, heap at 0x200485f0
stack at 0x22ab1b, heap at 0x20048600
stack at 0x22aaeb, heap at 0x20048610
stack at 0x22aabb, heap at 0x20048620
stack at 0x22aa8b, heap at 0x20048630
stack at 0x22aa5b, heap at 0x20048640

So, the stack is going downwards and the heap is going upwards (as you might expect based on the myth), but the stack has the smaller address, and they are not growing toward each other (myth busted).

Btw, my check function is tail-recursive, and on some implementations with some compiler options you might see the stack not moving at all. Which tells you something about why the standard doesn't mandate how all this works -- if it did it might inadvertently forbid useful optimizations.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • 1
    Tail recursion eliminates the current stack frame before the recursive call is made, as it is not needed after the recursive call ends. Stack is still going downwards, it just happens in this case, there is no need to grow the stack. – user1706991 Feb 15 '16 at 18:53
  • 6
    It's not a myth. Your program output on modern non-[ASLR](https://en.wikipedia.org/wiki/Address_space_layout_randomization) Linux: `stack at 0x7fff356d5fd7, heap at 0x1d39010`. Doing `sudo bash -c 'for x in /proc/*/maps; do echo $x; egrep stack\|heap $x; done'` shows similar for all processes. A stack/heap collision was used as exploit in 2014: ["The effect of all these command line arguments is to bloat both the stack (which grows down) and the heap (which grows up) until they crash into each other."](http://googleprojectzero.blogspot.co.uk/2014/08/the-poisoned-nul-byte-2014-edition.html) – bain Jul 04 '16 at 16:26
  • 9
    The fact that there exists a system on which the statement is true doesn't prevent it from being a myth when presented as a "general description" as in the question. It's one way to do it, but the general claim that it's "the way it's done" is just wrong. – Steve Jessop Jul 14 '16 at 23:11
22

As mentioned already, sizes are OS specific. For e.g. on windows using Visual Studio, default stack size is 1MB

msdn

On Linux the following command can show show your current one.

ulimit -s or -a

On my Linux mint 64 bit it shows 8192 KB.

Every program when loaded in memory has several segments. In assembly one can indicate each of those using .data, .code etc prefix (intelx86).

It is data segment which has several sub sections. Both stack and heap are part of it in addition to several others.

Stack can also grow implicitly i.e. when you make another function call, an activation record is pushed on to stack, there by utilizing more memory of stack. That is why infinite recursion results in a crash when a program runs out of allocated stack.

When a function call returns, that activation record is popped and stack shrinks.

In contrast heap grows from the opposite direction and contains all dynamically allocated memory.

The reason these two segments grow in opposite direction is to maximize the utilization of their combined memory. Note that as mentioned in comments this is not a c standard, but most common OS's have this implemented.

------ stack starts ----------- stack grows downward

-------- Unless they cross each other a program is okay to run.

------- heap starts ------------heap grows upwards

If your program uses no heap, your stack can utilize maximum memory including that of heap too. If program makes few recursive calls and uses minimum local variables (i.e. uses less memory for stack), it can utilize heap to the most.

Other parts of data segment are BSS etc. which might contain fields such as uninitialized static variables

fkl
  • 5,412
  • 4
  • 28
  • 68
  • 1
    The direction of stack/heap expansion isn't specified by the C standard. They can both grow up or down and it would be allowed by the standard. – Alexey Frunze Oct 02 '12 at 09:12
  • 1
    Agreed. That is a common implementation for e.g. in Linux. But like mentioned, not a c standard – fkl Oct 02 '12 at 09:15
  • 2
    Thanks for the answer!! Additionally I would like to quote the following "ulimit" does show the upper limit on the stack size (not the one used by the compiler). I presume after this limit the program terminates with a stack overflow error – Vivek Maran Oct 02 '12 at 11:28
11

What is the initial size with which a stack/heap is created? and who decides it?

This is compiler- and OS-specific.

Wherein physical memory are they are created? I see a general description as "Heap is created in the top-level-address and stack at the low-level-address".

This is compiler- and OS-specific.

Really. The language standard does not mandate the minimum stack size nor specifies the location of either the stack or the heap in memory. And the reason for that is to make C programs less dependent on these details and therefore more portable to different platforms (read: different OSes, different CPUs, different compilers).

Alexey Frunze
  • 61,140
  • 12
  • 83
  • 180
6

First of all, the C standard doesn't impose any requirements on how the stack/heap is implemented by the platform.

What is the initial size with which a stack/heap is created? and who decides it?

Typically a fixed size of stack is allocated for every process by the OS which is platform-specific. There's no limit on heap size, program usually have all of the available virtual address space.

Wherein physical memory are they are created?

This is platform specific. Typically stack grows downwards and heap grows upwards.

P.P
  • 117,907
  • 20
  • 175
  • 238