Does stack grow upward or downward?

问题:

I have this piece of code in c:

int q = 10;
int s = 5;
int a[3];

printf(\"Address of a: %d\\n\",    (int)a);
printf(\"Address of a[1]: %d\\n\", (int)&a[1]);
printf(\"Address of a[2]: %d\\n\", (int)&a[2]);
printf(\"Address of q: %d\\n\",    (int)&q);
printf(\"Address of s: %d\\n\",    (int)&s);

The output is:

Address of a: 2293584
Address of a[1]: 2293588
Address of a[2]: 2293592
Address of q: 2293612
Address of s: 2293608

So, I see that from a to a[2], memory addresses increases by 4 bytes each. But from q to s, memory addresses decrease by 4 byte.

I wonder 2 things:

1. Does stack grow up or down? (It looks like both to me in this case)
2. What happen between a[2] and q memory addresses? Why there are a big memory difference there? (20 bytes).

Note: This is not homework question. I am curious on how stack works. Thanks for any help.

回答1:

The behavior of stack (growing up or growing down) depends on the application binary interface (ABI) and how the call stack (aka activation record) is organized.

Throughout its lifetime a program is bound to communicate with other programs like OS. ABI determines how a program can communicate with another program.

The stack for different architectures can grow the either way, but for an architecture it will be consistent. Please check this wiki link. But, the stack\'s growth is decided by the ABI of that architecture.

For example, if you take the MIPS ABI, the call stack is defined as below.

Let us consider that function \'fn1\' calls \'fn2\'. Now the stack frame as seen by \'fn2\' is as follows:

direction of     |                                 |
  growth of      +---------------------------------+ 
   stack         | Parameters passed by fn1(caller)|
from higher addr.|                                 |
to lower addr.   | Direction of growth is opposite |
      |          |   to direction of stack growth  |
      |          +---------------------------------+ <-- SP on entry to fn2
      |          | Return address from fn2(callee) | 
      V          +---------------------------------+ 
                 | Callee saved registers being    | 
                 |   used in the callee function   | 
                 +---------------------------------+
                 | Local variables of fn2          |
                 |(Direction of growth of frame is |
                 | same as direction of growth of  |
                 |            stack)               |
                 +---------------------------------+ 
                 | Arguments to functions called   |
                 | by fn2                          |
                 +---------------------------------+ <- Current SP after stack 
                                                        frame is allocated

Now you can see the stack grows downward. So, if the variables are allocated to the local frame of the function, the variable\'s addresses actually grows downward. The compiler can decide on the order of variables for memory allocation. (In your case it can be either \'q\' or \'s\' that is first allocated stack memory. But, generally the compiler does stack memory allocation as per the order of the declaration of the variables).

But in case of the arrays, the allocation has only single pointer and the memory needs to be allocated will be actually pointed by a single pointer. The memory needs to be contiguous for an array. So, though stack grows downward, for arrays the stack grows up.

回答2:

This is actually two questions. One is about which way the stack grows when one function calls another (when a new frame is allocated), and the other is about how variables are laid out in a particular function\'s frame.

Neither is specified by the C standard, but the answers are a little different:

• Which way does the stack grow when a new frame is allocated -- if function f() calls function g(), will f\'s frame pointer be greater or less than g\'s frame pointer? This can go either way -- it depends on the particular compiler and architecture (look up \"calling convention\"), but it is always consistent within a given platform (with a few bizarre exceptions, see the comments). Downwards is more common; it\'s the case in x86, PowerPC, MIPS, SPARC, EE, and the Cell SPUs.
• How are a function\'s local variables laid out inside its stack frame? This is unspecified and completely unpredictable; the compiler is free to arrange its local variables however it likes to get the most efficient result.

回答3:

The direction is which stacks grow is architecture specific. That said, my understanding is that only a very few hardware architectures have stacks that grow up.

The direction that a stack grows is independent of the the layout of an individual object. So while the stack may grown down, arrays will not (i.e &array[n] will always be < &array[n+1]);

回答4:

There\'s nothing in the standard that mandates how things are organized on the stack at all. In fact, you could build a conforming compiler that didn\'t store array elements at contiguous elements on the stack at all, provided it had the smarts to still do array element arithmetic properly (so that it knew, for example, that a1 was 1K away from a[0] and could adjust for that).

The reason you may be getting different results is because, while the stack may grow down to add \"objects\" to it, the array is a single \"object\" and it may have ascending array elements in the opposite order. But it\'s not safe to rely on that behaviour since direction can change and variables could be swapped around for a variety of reasons including, but not limited to:

• optimization.
• alignment.
• the whims of the person the stack management part of the compiler.

See here for my excellent treatise on stack direction :-)

In answer to your specific questions:

1. Does stack grow up or down?
   It doesn\'t matter at all (in terms of the standard) but, since you asked, it can grow up or down in memory, depending on the implementation.
2. What happen between a[2] and q memory addresses? Why there are a big memory difference there? (20 bytes)?
   It doesn\'t matter at all (in terms of the standard). See above for possible reasons.

回答5:

On an x86, the memory \"allocation\" of a stack frame consists simply of subtracting the necessary number of bytes from the stack pointer (I believe other architectures are similar). In this sense, I guess the stack growns \"down\", in that the addresses get progressively smaller as you call more deeply into the stack (but I always envision the memory as starting with 0 in the top left and getting larger addresses as you move to the right and wrap down, so in my mental image the stack grows up...). The order of the variables being declared may not have any bearing on their addresses -- I believe the standard allows for the compiler to reorder them, as long as it doesn\'t cause side effects (someone please correct me if I\'m wrong). They\'re just stuck somewhere into that gap in the used addresses created when it subtracts the number of bytes from the stack pointer.

The gap around the array may be some kind of padding, but it\'s mysterious to me.

回答6:

First of all, its 8 bytes of unused space in memory(its not 12, remember stack grows downward, So the space which is not allocated is from 604 to 597). and why?. Because every data type takes space in memory starting from the address divisible by its size. In our case array of 3 integers take 12 bytes of memory space and 604 is not divisible by 12. So it leaves empty spaces until it encounters a memory address which is divisible by 12, it is 596.

So the memory space allocated to the array is from 596 to 584. But as array allocation is in continuation, So first element of array starts from 584 address and not from 596.

回答7:

grows downward and this is because of the little endian byte order standard when it comes to the set of data in memory.

One way you could look at it is that the stack DOES grow upward if you look at memory from 0 from the top and max from the bottom.

The reason for the stack growing downward is to be able to dereference from the perspective of the stack or base pointer.

Remember that dereferencing of any type increases from the lowest to highest address. Since the Stack grows downward (highest to lowest address) this lets you treat the stack like dynamic memory.

This is one reason why so many programming and scripting languages use a stack-based virtual machine rather than a register-based.

回答8:

The compiler is free to allocate local (auto) variables at any place on the local stack frame, you cannot reliably infer the stack growing direction purely from that. You can infer the stack grow direction from comparing the addresses of nested stack frames, ie comparing the address of a local variable inside the stack frame of a function compared to it\'s callee :

#include <stdio.h>
int f(int *x)
{
  int a;
  return x == NULL ? f(&a) : &a - x;
}

int main(void)
{
  printf(\"stack grows %s!\\n\", f(NULL) < 0 ? \"down\" : \"up\");
  return 0;
}

回答9:

My stack appears to extend towards lower numbered addresses.

It may be different on another computer, or even on my own computer if I use a different compiler invocation. ... or the compiler muigt choose not to use a stack at all (inline everything (functions and variables if I didn\'t take the address of them)).

$ cat stack.c
#include <stdio.h>

int stack(int x) {
  printf(\"level %d: x is at %p\\n\", x, (void*)&x);
  if (x == 0) return 0;
  return stack(x - 1);
}

int main(void) {
  stack(4);
  return 0;
}

$ /usr/bin/gcc -Wall -Wextra -std=c89 -pedantic stack.c

$ ./a.out
level 4: x is at 0x7fff7781190c
level 3: x is at 0x7fff778118ec
level 2: x is at 0x7fff778118cc
level 1: x is at 0x7fff778118ac
level 0: x is at 0x7fff7781188c

回答10:

The stack grows down (on x86). However, the stack is allocated in one block when the function loads, and you don\'t have a guarantee what order the items will be on the stack.

In this case, it allocated space for two ints and a three-int array on the stack. It also allocated an additional 12 bytes after the array, so it looks like this:

a [12 bytes]
padding(?) [12 bytes]
s [4 bytes]
q [4 bytes]

For whatever reason, your compiler decided that it needed to allocate 32 bytes for this function, and possibly more. That\'s opaque to you as a C programmer, you don\'t get to know why.

If you want to know why, compile the code to assembly language, I believe that it\'s -S on gcc and /S on MS\'s C compiler. If you look at the opening instructions to that function, you\'ll see the old stack pointer being saved and then 32 (or something else!) being subtracted from it. From there, you can see how the code accesses that 32-byte block of memory and figure out what your compiler is doing. At the end of the function, you can see the stack pointer being restored.

回答11:

It depends on your operating system and your compiler.

回答12:

Stack does grow down. So f(g(h())), the stack allocated for h will start at lower address then g and g\'s will be lower then f\'s. But variables within the stack have to follow the C specification,

http://c0x.coding-guidelines.com/6.5.8.html

1206 If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values.

&a[0] < &a[1], must always be true, regardless of how \'a\' is allocated

回答13:

It depends on the architecture. To check your own system, use this code from GeeksForGeeks:

// C program to check whether stack grows 
// downward or upward. 
#include<stdio.h> 

void fun(int *main_local_addr) 
{ 
    int fun_local; 
    if (main_local_addr < &fun_local) 
        printf(\"Stack grows upward\\n\"); 
    else
        printf(\"Stack grows downward\\n\"); 
} 

int main() 
{ 
    // fun\'s local variable 
    int main_local; 

    fun(&main_local); 
    return 0; 
} 

回答14:

I don\'t think it\'s deterministic like that. The a array seems to \"grow\" because that memory should be allocated contiguously. However, since q and s are not related to one another at all, the compiler just sticks each of them in an arbitrary free memory location within the stack, probably the ones that fit an integer size the best.

What happened between a[2] and q is that the space around q\'s location wasn\'t large enough (ie, wasn\'t bigger than 12 bytes) to allocate a 3 integer array.