¿La pila crece hacia arriba o hacia abajo?

89

Tengo este fragmento de código en 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);

La salida es:

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

Entonces, veo que de aa a[2], las direcciones de memoria aumentan en 4 bytes cada una. Pero de qa s, las direcciones de memoria disminuyen en 4 bytes.

Me pregunto 2 cosas:

  1. ¿La pila crece hacia arriba o hacia abajo? (Me parece que ambos en este caso)
  2. ¿Qué sucede entre las direcciones de memoria a[2]y q? ¿Por qué hay una gran diferencia de memoria? (20 bytes).

Nota: Esta no es una pregunta de tarea. Tengo curiosidad por saber cómo funciona la pila. Gracias por cualquier ayuda.

Spikatrix
fuente
El orden es arbitrario. La brecha es probablemente para almacenar un resultado intermedio como & q o & s - mire el desmontaje y compruébelo usted mismo.
Tom Leys
Estoy de acuerdo, lea el código de ensamblaje. Si está haciendo este tipo de preguntas, es hora de aprender a leerlo.
Per Johansson
Una versión de ensamblaje más sencilla de responder: stackoverflow.com/questions/664744/…
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Respuestas:

74

El comportamiento de la pila (creciendo o disminuyendo) depende de la interfaz binaria de la aplicación (ABI) y de cómo se organiza la pila de llamadas (también conocido como registro de activación).

A lo largo de su vida, un programa está obligado a comunicarse con otros programas como OS. ABI determina cómo un programa puede comunicarse con otro programa.

La pila para diferentes arquitecturas puede crecer de cualquier manera, pero para una arquitectura será consistente. Consulte este enlace wiki. Pero, el crecimiento de la pila lo decide la ABI de esa arquitectura.

Por ejemplo, si toma MIPS ABI, la pila de llamadas se define a continuación.

Consideremos que la función 'fn1' llama a 'fn2'. Ahora el marco de pila visto por 'fn2' es el siguiente:

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

Ahora puede ver que la pila crece hacia abajo. Entonces, si las variables se asignan al marco local de la función, las direcciones de la variable en realidad crecen hacia abajo. El compilador puede decidir el orden de las variables para la asignación de memoria. (En su caso, puede ser 'q' o 's' el primero en asignar memoria de pila. Pero, generalmente, el compilador hace la asignación de memoria de pila según el orden de la declaración de las variables).

Pero en el caso de las matrices, la asignación tiene un solo puntero y la memoria que se debe asignar será en realidad apuntada por un solo puntero. La memoria debe ser contigua para una matriz. Entonces, aunque la pila crece hacia abajo, para las matrices la pila crece.

Ganesh Gopalasubramanian
fuente
5
Además, si desea comprobar si la pila crece hacia arriba o hacia abajo. Declare una variable local en la función principal. Imprime la dirección de la variable. Llame a otra función desde main. Declare una variable local en la función. Imprime su dirección. Según las direcciones impresas, podemos decir que la pila crece hacia arriba o hacia abajo.
Ganesh Gopalasubramanian
gracias Ganesh, tengo una pequeña pregunta: en la figura que dibujó, en el tercer bloque, ¿quiso decir "registro guardado de calleR que se está usando en CALLER" porque cuando f1 llama a f2, tenemos que almacenar la dirección f1 (que es la dirección de retorno para los registros f2) y f1 (calleR), no los registros f2 (callee). ¿Derecho?
CSawy
44

En realidad, se trata de dos preguntas. Uno trata sobre la forma en que crece la pila cuando una función llama a otra (cuando se asigna un nuevo marco), y el otro trata sobre cómo se distribuyen las variables en el marco de una función en particular.

Ninguno de los dos está especificado por el estándar C, pero las respuestas son un poco diferentes:

  • ¿De qué manera crece la pila cuando se asigna un nuevo marco? Si la función f () llama a la función g (), ¿ fel puntero del marco será mayor o menor que gel puntero del marco? Esto puede ser de cualquier manera: depende del compilador y la arquitectura en particular (busque "convención de llamada"), pero siempre es consistente dentro de una plataforma dada (con algunas excepciones extrañas, vea los comentarios). Hacia abajo es más común; es el caso de x86, PowerPC, MIPS, SPARC, EE y las SPU de celda.
  • ¿Cómo se distribuyen las variables locales de una función dentro de su marco de pila? Esto no está especificado y es completamente impredecible; el compilador es libre de ordenar sus variables locales sin embargo le gusta obtener el resultado más eficiente.
Crashworks
fuente
7
"siempre es coherente dentro de una plataforma determinada", no garantizado. He visto una plataforma sin memoria virtual, donde la pila se extendió dinámicamente. Los nuevos bloques de pila estaban mal ubicados, lo que significa que irías "hacia abajo" un bloque de pila por un tiempo, y luego de repente "de lado" a un bloque diferente. "De lado" podría significar una dirección mayor o menor, totalmente por suerte del sorteo.
Steve Jessop
2
Para obtener detalles adicionales sobre el elemento 2, un compilador puede decidir que una variable nunca necesita estar en la memoria (manteniéndola en un registro durante la vida de la variable), y / o si la vida útil de dos o más variables no lo hace. Si se superponen, el compilador puede decidir utilizar la misma memoria para más de una variable.
Michael Burr
2
Creo que S / 390 (IBM zSeries) tiene una ABI donde los marcos de llamada están vinculados en lugar de crecer en una pila.
efímero
2
Correcto en S / 390. Una llamada es "BALR", registro de rama y enlace. El valor de retorno se coloca en un registro en lugar de empujarlo a una pila. La función de retorno es una rama del contenido de ese registro. A medida que la pila se hace más profunda, se asigna espacio en el montón y se encadenan. Aquí es donde el equivalente MVS de "/ bin / true" recibe su nombre: "IEFBR14". La primera versión tenía una sola instrucción: "BR 14", que se ramificaba al contenido del registro 14 que contenía la dirección de retorno.
enero
1
Y algunos compiladores de procesadores PIC realizan análisis de todo el programa y asignan ubicaciones fijas para las variables automáticas de cada función; la pila real es pequeña y no es accesible desde el software; es solo para direcciones de retorno.
enero
13

La dirección en la que crecen las pilas depende de la arquitectura. Dicho esto, tengo entendido que solo unas pocas arquitecturas de hardware tienen pilas que crecen.

La dirección en la que crece una pila es independiente del diseño de un objeto individual. Por tanto, aunque la pila puede reducirse, las matrices no lo harán (es decir, & array [n] siempre será <& array [n + 1]);

R Samuel Klatchko
fuente
4

No hay nada en el estándar que exija cómo se organizan las cosas en la pila. De hecho, se podría construir un compilador que no se ajusten almacenar elementos de la matriz de elementos contiguos en la pila en absoluto, siempre y cuando tuvo la inteligencia para hacer aún gama de elementos aritméticos correctamente (por lo que sabía, por ejemplo, que un 1 fue 1K de distancia de un [0] y podría ajustarlo).

La razón por la que puede obtener resultados diferentes es porque, si bien la pila puede crecer hacia abajo para agregarle "objetos", la matriz es un solo "objeto" y puede tener elementos de matriz ascendentes en el orden opuesto. Pero no es seguro confiar en ese comportamiento, ya que la dirección puede cambiar y las variables pueden intercambiarse por una variedad de razones que incluyen, entre otras:

  • mejoramiento.
  • alineación.
  • los caprichos de la persona que gestiona la pila forma parte del compilador.

Vea aquí mi excelente tratado sobre la dirección de la pila :-)

En respuesta a sus preguntas específicas:

  1. ¿La pila crece hacia arriba o hacia abajo?
    No importa en absoluto (en términos del estándar) pero, como lo preguntaste, puede crecer hacia arriba o hacia abajo en la memoria, dependiendo de la implementación.
  2. ¿Qué sucede entre las direcciones de memoria a [2] yq? ¿Por qué hay una gran diferencia de memoria? (20 bytes)?
    No importa en absoluto (en términos del estándar). Consulte más arriba para conocer las posibles razones.
paxdiablo
fuente
Te vi vincular que la mayoría de las arquitecturas de CPU adoptan la forma de "crecer hacia abajo", ¿sabes si hay alguna ventaja en hacerlo?
Baiyan Huang
Realmente no tengo idea. Es posible que alguien haya pensado que el código va hacia arriba desde 0, por lo que la pila debería ir hacia abajo desde highmem, para minimizar la posibilidad de intersección. Pero algunas CPU comienzan a ejecutar código específicamente en ubicaciones distintas de cero, por lo que puede que no sea el caso. Como con la mayoría de las cosas, tal vez se hizo de esa manera simplemente porque fue la primera forma en que alguien pensó en hacerlo :-)
paxdiablo
@lzprgmr: Hay algunas ventajas leves de tener ciertos tipos de asignación de montón realizados en orden ascendente, e históricamente ha sido común que la pila y el montón se encuentren en extremos opuestos de un espacio de direccionamiento común. Siempre que el uso combinado de estática + pila + pila no excediera la memoria disponible, uno no tenía que preocuparse por la cantidad exacta de memoria de pila que usaba un programa.
supercat
3

En un x86, la "asignación" de memoria de un marco de pila consiste simplemente en restar el número necesario de bytes del puntero de pila (creo que otras arquitecturas son similares). En este sentido, supongo que la pila crece "hacia abajo", en el sentido de que las direcciones se vuelven progresivamente más pequeñas a medida que llama más profundamente en la pila (pero siempre imagino que la memoria comienza con 0 en la parte superior izquierda y obtiene direcciones más grandes a medida que avanza a la derecha y envolver hacia abajo, por lo que en mi imagen mental la pila crece ...). El orden de las variables que se declaran puede no tener ninguna relación con sus direcciones; creo que el estándar permite que el compilador las reordene, siempre que no cause efectos secundarios (alguien, por favor, corríjame si me equivoco) . Ellos'

El espacio alrededor de la matriz puede ser una especie de relleno, pero me resulta misterioso.

rmeador
fuente
1
De hecho, sé que el compilador puede reordenarlos, porque también es gratis no asignarlos en absoluto. Puede simplemente ponerlos en registros y no usar ningún espacio de pila en absoluto.
rmeador
No puede ponerlos en los registros si hace referencia a sus direcciones.
Florín
buen punto, no lo había considerado. pero todavía es suficiente como prueba de que el compilador puede reordenarlos, ya que sabemos que puede hacerlo al menos algunas veces :)
rmeador
1

En primer lugar, sus 8 bytes de espacio no utilizado en la memoria (no son 12, recuerde que la pila crece hacia abajo, por lo que el espacio que no se asigna es de 604 a 597). ¿y por qué?. Porque cada tipo de datos ocupa espacio en la memoria a partir de la dirección divisible por su tamaño. En nuestro caso, la matriz de 3 enteros ocupa 12 bytes de espacio de memoria y 604 no es divisible por 12. De modo que deja espacios vacíos hasta que encuentra una dirección de memoria que es divisible por 12, es 596.

Entonces, el espacio de memoria asignado a la matriz es de 596 a 584. Pero como la asignación de matriz está en continuación, el primer elemento de la matriz comienza desde la dirección 584 y no desde la 596.

Prateek Khurana
fuente
1

El compilador es libre de asignar variables locales (automáticas) en cualquier lugar del marco de pila local, no puede inferir de manera confiable la dirección de crecimiento de la pila simplemente a partir de eso. Puede inferir la dirección de crecimiento de la pila comparando las direcciones de los marcos de pila anidados, es decir, comparando la dirección de una variable local dentro del marco de pila de una función en comparación con su destinatario:

#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;
}
matja
fuente
5
Estoy bastante seguro de que es un comportamiento indefinido restar punteros a diferentes objetos de pila; los punteros que no son parte del mismo objeto no son comparables. Obviamente, aunque no se bloqueará en ninguna arquitectura "normal".
Steve Jessop
@SteveJessop ¿Hay alguna forma de solucionar este problema para obtener la dirección de la pila mediante programación?
xxks-kkk
@ xxks-kkk: en principio no, porque no se requiere una implementación en C para tener una "dirección de pila". Por ejemplo, no violaría el estándar tener una convención de llamada en la que se asigna un bloque de pila por adelantado, y luego se usa alguna rutina de asignación de memoria interna pseudoaleatoria para saltar dentro de él. En la práctica, funciona como describe matja.
Steve Jessop
0

No creo que sea tan determinista. La matriz a parece "crecer" porque esa memoria debe asignarse de forma contigua. Sin embargo, dado que qys no están relacionados entre sí en absoluto, el compilador simplemente coloca cada uno de ellos en una ubicación de memoria libre arbitraria dentro de la pila, probablemente las que se ajustan mejor a un tamaño entero.

Lo que sucedió entre a [2] yq es que el espacio alrededor de la ubicación de q no era lo suficientemente grande (es decir, no era mayor de 12 bytes) para asignar una matriz de 3 enteros.

javanix
fuente
si es así, ¿por qué q, s, a no tienen memoria constante? (Ej .: Dirección de q: 2293612 Dirección de s: 2293608 Dirección de a: 2293604)
Veo un "espacio" entre s y a
Debido a que s y a no se asignaron juntos, los únicos punteros que deben ser contiguos son los de la matriz. La otra memoria se puede asignar donde sea.
javanix
0

Mi pila parece extenderse hacia direcciones con números más bajos.

Puede ser diferente en otra computadora, o incluso en mi propia computadora si uso una invocación de compilador diferente. ... o el compilador muigt elige no usar una pila en absoluto (todo en línea (funciones y variables si no tomé la dirección de ellas)).

$ 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
nivel 4: x está en 0x7fff7781190c
nivel 3: x está en 0x7fff778118ec
nivel 2: x está en 0x7fff778118cc
nivel 1: x está en 0x7fff778118ac
nivel 0: x está en 0x7fff7781188c
pmg
fuente
0

La pila crece hacia abajo (en x86). Sin embargo, la pila se asigna en un bloque cuando se carga la función, y no tiene garantía de qué orden estarán los elementos en la pila.

En este caso, asignó espacio para dos entradas y una matriz de tres entradas en la pila. También asignó 12 bytes adicionales después de la matriz, por lo que se ve así:

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

Por alguna razón, su compilador decidió que necesitaba asignar 32 bytes para esta función, y posiblemente más. Eso es opaco para usted como programador de C, no llega a saber por qué.

Si quiere saber por qué, compile el código en lenguaje ensamblador, creo que es -S en gcc y / S en el compilador C de MS. Si observa las instrucciones de apertura de esa función, verá que se guarda el puntero de pila anterior y luego se restan 32 (¡o algo más!). Desde allí, puede ver cómo el código accede a ese bloque de memoria de 32 bytes y averiguar qué está haciendo su compilador. Al final de la función, puede ver cómo se restaura el puntero de la pila.

Aric TenEyck
fuente
0

Depende de su sistema operativo y su compilador.

David R Tribble
fuente
No sé por qué mi respuesta fue rechazada. Realmente depende de su sistema operativo y compilador. En algunos sistemas, la pila crece hacia abajo, pero en otros crece hacia arriba. Y en algunos sistemas, no hay una pila de marcos pushdown real, sino que se simula con un área reservada de memoria o un conjunto de registros.
David R Tribble
3
Probablemente porque las afirmaciones de una sola oración no son buenas respuestas.
Lightness Races in Orbit
0

La pila crece hacia abajo. Entonces, f (g (h ())), la pila asignada para h comenzará en la dirección más baja, luego g y g serán más bajas que f. Pero las variables dentro de la pila deben seguir la especificación C,

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

1206 Si los objetos apuntados son miembros del mismo objeto agregado, los apuntadores a miembros de estructura declarados más tarde comparan mayores que apuntadores a miembros declarados anteriormente en la estructura, y los apuntadores a elementos de matriz con valores de subíndice más grandes comparan mayores que apuntadores a elementos de la misma matriz con valores de subíndice más bajos.

& a [0] <& a [1], siempre debe ser verdadero, independientemente de cómo se asigne 'a'

usuario1187902
fuente
En la mayoría de las máquinas, la pila crece hacia abajo, excepto en aquellas en las que crece hacia arriba.
Jonathan Leffler
0

crece hacia abajo y esto se debe al estándar de orden de bytes little endian cuando se trata del conjunto de datos en la memoria.

Una forma de verlo es que la pila SÍ crece hacia arriba si mira la memoria desde 0 desde arriba y max desde abajo.

La razón por la que la pila crece hacia abajo es poder desreferenciar desde la perspectiva de la pila o del puntero base.

Recuerde que la desreferenciación de cualquier tipo aumenta de la dirección más baja a la más alta. Dado que la pila crece hacia abajo (dirección de mayor a menor), esto le permite tratar la pila como una memoria dinámica.

Esta es una de las razones por las que tantos lenguajes de programación y scripting utilizan una máquina virtual basada en pilas en lugar de una basada en registros.

Nergal
fuente
The reason for the stack growing downward is to be able to dereference from the perspective of the stack or base pointer.Muy buen razonamiento
user3405291
0

Depende de la arquitectura. Para verificar su propio sistema, use este código de 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; 
} 
kurdtpage
fuente