¿Cómo funciona la pila en lenguaje ensamblador?

Actualmente estoy tratando de entender cómo funciona la pila, así que decidí enseñarme algo de lenguaje ensamblador , estoy usando este libro:

http://savannah.nongnu.org/projects/pgubook/

Estoy usando Gas y estoy desarrollando en Linux Mint .

Estoy un poco confundido por algo:

Hasta donde yo sabía, una pila es simplemente una estructura de datos. Entonces asumí que si estaba codificando en ensamblador tendría que implementar la pila yo mismo. Sin embargo, este no parece ser el caso, ya que hay comandos como

pushl
popl

Entonces, al codificar en ensamblado para la arquitectura x86 y usar la sintaxis de Gas: ¿es la pila solo una estructura de datos que ya está implementada? ¿O está realmente implementado a nivel de hardware? ¿O es otra cosa? Además, ¿la mayoría de los lenguajes ensambladores para otros conjuntos de chips ya tienen la pila implementada?

Sé que esta es una pregunta un poco tonta, pero en realidad estoy bastante confundido por esto.

Creo que principalmente te estás confundiendo entre a program's stacky any old stack.

Un montón

Es una estructura de datos abstracta que consta de información en un sistema de último en entrar, primero en salir. Pones objetos arbitrarios en la pila y luego los quitas de nuevo, al igual que una bandeja de entrada / salida, el elemento superior es siempre el que se quita y siempre lo colocas en la parte superior.

Una pila de programas

Es una pila, es una sección de memoria que se usa durante la ejecución, generalmente tiene un tamaño estático por programa y se usa con frecuencia para almacenar parámetros de función. Usted empuja los parámetros a la pila cuando llama a una función y la función se dirige a la pila directamente o saca las variables de la pila.

Una pila de programas no es generalmente hardware (aunque se mantiene en la memoria, por lo que se puede argumentar como tal), pero el puntero de la pila que apunta a un área actual de la pila es generalmente un registro de la CPU. Esto lo hace un poco más flexible que una pila LIFO, ya que puede cambiar el punto en el que se dirige la pila.

Debe leer y asegurarse de comprender el artículo de wikipedia, ya que ofrece una buena descripción de la pila de hardware, que es con lo que está tratando.

También existe este tutorial que explica la pila en términos de los registros antiguos de 16 bits, pero podría ser útil y otro específicamente sobre la pila.

Desde Nils Pipenbrinck:

Vale la pena señalar que algunos procesadores no implementan todas las instrucciones para acceder y manipular la pila (push, pop, stack pointer, etc.) pero el x86 lo hace debido a su frecuencia de uso. En estas situaciones, si quisiera una pila, tendría que implementarla usted mismo (algunos MIPS y algunos procesadores ARM se crean sin pilas).

Por ejemplo, en MIP se implementaría una instrucción push como:

addi $sp, $sp, -4  # Decrement stack pointer by 4  
sw   $t0, ($sp)   # Save $t0 to stack  

y una instrucción Pop se vería así:

lw   $t0, ($sp)   # Copy from stack to $t0  
addi $sp, $sp, 4   # Increment stack pointer by 4  

(He hecho una idea general de todo el código en esta respuesta en caso de que quieras jugar con él)

Solo hice las cosas más básicas en ASM durante mi curso CS101 en 2003. Y nunca había "entendido" realmente cómo funcionan ASM y Stack hasta que me di cuenta de que todo es básicamente como programar en C o C ++ ... pero sin variables, parámetros y funciones locales. Probablemente no suene fácil todavía :) Déjame mostrarte (para asm x86 con sintaxis Intel ).

1. ¿Qué es la pila?

La pila suele ser una porción contigua de memoria asignada para cada subproceso antes de que comiencen. Puedes guardar allí lo que quieras. En términos de C ++ ( fragmento de código n. ° 1 ):

const int STACK_CAPACITY = 1000;
thread_local int stack[STACK_CAPACITY];

2. Parte superior e inferior de la pila

En principio, podría almacenar valores en celdas aleatorias de la stackmatriz ( fragmento # 2.1 ):

stack[333] = 123;
stack[517] = 456;
stack[555] = stack[333] + stack[517];

Pero imagínese lo difícil que sería recordar qué células de stackya están en uso y cuáles son "gratuitas". Es por eso que almacenamos nuevos valores en la pila uno al lado del otro.

Una cosa extraña acerca de la pila de asm (x86) es que agrega cosas allí comenzando con el último índice y se mueve a índices inferiores: pila [999], luego pila [998] y así sucesivamente ( fragmento # 2.2 ):

stack[999] = 123;
stack[998] = 456;
stack[997] = stack[999] + stack[998];

Y aún así (precaución, ahora estarás confundido) el nombre "oficial" de stack[999]está al final de la pila .
La última celda utilizada ( stack[997]en el ejemplo anterior) se denomina parte superior de la pila (consulte Dónde está la parte superior de la pila en x86 ).

3. Puntero de pila (SP)

Para el propósito de esta discusión, supongamos que los registros de CPU se representan como variables globales (consulte Registros de propósito general ).

int AX, BX, SP, BP, ...;
int main(){...}

Hay un registro de CPU (SP) especial que rastrea la parte superior de la pila. SP es un puntero (contiene una dirección de memoria como 0xAAAABBCC). Pero para los propósitos de esta publicación, lo usaré como un índice de matriz (0, 1, 2, ...).

Cuando se inicia un hilo, SP == STACK_CAPACITYel programa y el sistema operativo lo modifican según sea necesario. La regla es que no puede escribir en las celdas de la pila más allá de la parte superior de la pila y cualquier índice menor que SP no es válido y no es seguro (debido a las interrupciones del sistema ), por lo que primero disminuye SP y luego escribe un valor en la celda recién asignada.

Cuando desee insertar varios valores en la pila en una fila, puede reservar espacio para todos ellos por adelantado ( fragmento # 3 ):

SP -= 3;
stack[999] = 12;
stack[998] = 34;
stack[997] = stack[999] + stack[998];

Nota. Ahora puede ver por qué la asignación en la pila es tan rápida: es solo una disminución de un solo registro.

4. Variables locales

Echemos un vistazo a esta función simplista ( fragmento # 4.1 ):

int triple(int a) {
    int result = a * 3;
    return result;
}

y reescribirlo sin usar la variable local ( fragmento # 4.2 ):

int triple_noLocals(int a) {
    SP -= 1; // move pointer to unused cell, where we can store what we need
    stack[SP] = a * 3;
    return stack[SP];
}

y vea cómo se llama ( fragmento # 4.3 ):

// SP == 1000
someVar = triple_noLocals(11);
// now SP == 999, but we don't need the value at stack[999] anymore
// and we will move the stack index back, so we can reuse this cell later
SP += 1; // SP == 1000 again

5. Push / pop

La adición de un nuevo elemento en la parte superior de la pila es una operación tan frecuente que las CPU tienen una instrucción especial para eso push. Lo implementaremos así ( fragmento 5.1 ):

void push(int value) {
    --SP;
    stack[SP] = value;
}

Del mismo modo, tomando el elemento superior de la pila ( fragmento 5.2 ):

void pop(int& result) {
    result = stack[SP];
    ++SP; // note that `pop` decreases stack's size
}

El patrón de uso común para push / pop está ahorrando algo de valor temporalmente. Digamos, tenemos algo útil en variable myVary por alguna razón necesitamos hacer cálculos que lo sobrescriban ( fragmento 5.3 ):

int myVar = ...;
push(myVar); // SP == 999
myVar += 10;
... // do something with new value in myVar
pop(myVar); // restore original value, SP == 1000

6. Parámetros de función

Ahora pasemos los parámetros usando la pila ( fragmento # 6 ):

int triple_noL_noParams() { // `a` is at index 999, SP == 999
    SP -= 1; // SP == 998, stack[SP + 1] == a
    stack[SP] = stack[SP + 1] * 3;
    return stack[SP];
}

int main(){
    push(11); // SP == 999
    assert(triple(11) == triple_noL_noParams());
    SP += 2; // cleanup 1 local and 1 parameter
}

7. returndeclaración

Devolvemos el valor en el registro AX ( fragmento # 7 ):

void triple_noL_noP_noReturn() { // `a` at 998, SP == 998
    SP -= 1; // SP == 997

    stack[SP] = stack[SP + 1] * 3;
    AX = stack[SP];

    SP += 1; // finally we can cleanup locals right in the function body, SP == 998
}

void main(){
    ... // some code
    push(AX); // save AX in case there is something useful there, SP == 999
    push(11); // SP == 998
    triple_noL_noP_noReturn();
    assert(triple(11) == AX);
    SP += 1; // cleanup param
             // locals were cleaned up in the function body, so we don't need to do it here
    pop(AX); // restore AX
    ...
}

8. Apilar el puntero de base (BP) (también conocido como puntero de marco ) y marco de pila

Tomemos una función más "avanzada" y la reescribamos en nuestro C ++ tipo asm ( fragmento # 8.1 ):

int myAlgo(int a, int b) {
    int t1 = a * 3;
    int t2 = b * 3;
    return t1 - t2;
}

void myAlgo_noLPR() { // `a` at 997, `b` at 998, old AX at 999, SP == 997
    SP -= 2; // SP == 995

    stack[SP + 1] = stack[SP + 2] * 3; 
    stack[SP]     = stack[SP + 3] * 3;
    AX = stack[SP + 1] - stack[SP];

    SP += 2; // cleanup locals, SP == 997
}

int main(){
    push(AX); // SP == 999
    push(22); // SP == 998
    push(11); // SP == 997
    myAlgo_noLPR();
    assert(myAlgo(11, 22) == AX);
    SP += 2;
    pop(AX);
}

Ahora imagine que decidimos introducir una nueva variable local para almacenar el resultado allí antes de regresar, como lo hacemos en tripple(fragmento # 4.1). El cuerpo de la función será ( fragmento # 8.2 ):

SP -= 3; // SP == 994
stack[SP + 2] = stack[SP + 3] * 3; 
stack[SP + 1] = stack[SP + 4] * 3;
stack[SP]     = stack[SP + 2] - stack[SP + 1];
AX = stack[SP];
SP += 3;

Verá, tuvimos que actualizar cada una de las referencias a los parámetros de función y las variables locales. Para evitar eso, necesitamos un índice de anclaje, que no cambia cuando la pila crece.

Crearemos el ancla justo después de la entrada de la función (antes de asignar espacio para los locales) guardando el tope actual (valor de SP) en el registro BP. Fragmento n.º 8.3 :

void myAlgo_noLPR_withAnchor() { // `a` at 997, `b` at 998, SP == 997
    push(BP);   // save old BP, SP == 996
    BP = SP;    // create anchor, stack[BP] == old value of BP, now BP == 996
    SP -= 2;    // SP == 994

    stack[BP - 1] = stack[BP + 1] * 3;
    stack[BP - 2] = stack[BP + 2] * 3;
    AX = stack[BP - 1] - stack[BP - 2];

    SP = BP;    // cleanup locals, SP == 996
    pop(BP);    // SP == 997
}

El segmento de la pila, que pertenece y tiene el control total de la función se llama marco de pila de la función . myAlgo_noLPR_withAnchorEl marco de pila de Eg es stack[996 .. 994](ambos idexes inclusive).
El marco comienza en el BP de la función (después de que lo hayamos actualizado dentro de la función) y dura hasta el siguiente marco de pila. Por tanto, los parámetros de la pila son parte del marco de pila de la persona que llama (consulte la nota 8a).

Notas:
8a. Wikipedia dice lo contrario sobre los parámetros, pero aquí me adhiero al manual del desarrollador de software de Intel , ver vol. 1, sección 6.2.4.1 Puntero de base de marco apilado y Figura 6-2 en la sección 6.3.2 Operación de LLAMADA y RET lejanos . Los parámetros de la función y el marco de pila son parte del registro de activación de la función (consulte El gen en los perílogos de la función ).
8b. las compensaciones positivas de BP apuntan a parámetros de función y las compensaciones negativas apuntan a variables locales. Eso es bastante útil para depurar
8c. stack[BP]almacena la dirección del marco de pila anterior,stack[stack[BP]]almacena el marco de pila anterior y así sucesivamente. Siguiendo esta cadena, puede descubrir marcos de todas las funciones en el programa, que aún no regresaron. Así es como los depuradores muestran que llama a la pila
8d. las primeras 3 instrucciones de myAlgo_noLPR_withAnchor, donde configuramos el marco (guardar BP antiguo, actualizar BP, reservar espacio para locales) se llaman función prólogo

9. Convenciones de llamadas

En el fragmento 8.1, hemos enviado los parámetros myAlgode derecha a izquierda y devolvimos el resultado en AX. También podríamos pasar los params de izquierda a derecha y regresar BX. O pase los parámetros en BX y CX y regrese en AX. Obviamente, caller ( main()) y la función llamada deben estar de acuerdo en dónde y en qué orden se almacenan todas estas cosas.

La convención de llamada es un conjunto de reglas sobre cómo se pasan los parámetros y se devuelve el resultado.

En el código anterior, usamos la convención de llamada cdecl :

• Los parámetros se pasan a la pila, con el primer argumento en la dirección más baja de la pila en el momento de la llamada (pulsado el último <...>). La persona que llama es responsable de quitar los parámetros de la pila después de la llamada.
• el valor de retorno se coloca en AX
• EBP y ESP deben ser preservados por la persona que llama ( myAlgo_noLPR_withAnchorfunción en nuestro caso), de modo que la persona que llama ( mainfunción) puede confiar en que esos registros no han sido cambiados por una llamada.
• Todos los demás registros (EAX, <...>) pueden ser modificados libremente por el destinatario; si una persona que llama desea conservar un valor antes y después de la llamada a la función, debe guardar el valor en otro lugar (hacemos esto con AX)

^{(Fuente: ejemplo "cdecl de 32 bits" de la documentación de Stack Overflow; copyright 2016 de icktoofay y Peter Cordes ; con licencia CC BY-SA 3.0. Se puede encontrar un archivo del contenido completo de la documentación de Stack Overflow en archive.org, en el que este ejemplo está indexado por ID de tema 3261 y ID de ejemplo 11196.)}

10. Llamadas a funciones

Ahora la parte más interesante. Al igual que los datos, el código ejecutable también se almacena en la memoria (sin ninguna relación con la memoria para la pila) y cada instrucción tiene una dirección.
Cuando no se le ordena lo contrario, la CPU ejecuta las instrucciones una tras otra, en el orden en que se almacenan en la memoria. Pero podemos ordenarle a la CPU que "salte" a otra ubicación en la memoria y ejecute instrucciones desde allí. En asm puede ser cualquier dirección, y en lenguajes de más alto nivel como C ++ solo puede saltar a direcciones marcadas con etiquetas ( hay soluciones pero no son bonitas, por decir lo menos).

Tomemos esta función ( fragmento # 10.1 ):

int myAlgo_withCalls(int a, int b) {
    int t1 = triple(a);
    int t2 = triple(b);
    return t1 - t2;
}

Y en lugar de llamar a trippleC ++, haga lo siguiente:

1. copia trippleel código al principio del myAlgocuerpo
2. en la myAlgoentrada saltar sobre trippleel código congoto
3. cuando necesitemos ejecutar trippleel código, guarde en la dirección de pila de la línea de código justo después de la tripplellamada, para que podamos volver aquí más tarde y continuar la ejecución ( PUSH_ADDRESSmacro a continuación)
4. saltar a la dirección de la primera línea ( tripplefunción) y ejecutarla hasta el final (3. y 4. juntos son CALLmacro)
5. al final de tripple(después de haber limpiado los locales), toma la dirección de retorno de la parte superior de la pila y salta allí ( RETmacro)

Debido a que no existe una manera fácil de saltar a una dirección de código particular en C ++, usaremos etiquetas para marcar los lugares de los saltos. No entraré en detalles sobre cómo funcionan las macros a continuación, solo créanme que hacen lo que digo que hacen ( fragmento # 10.2 ):

// pushes the address of the code at label's location on the stack
// NOTE1: this gonna work only with 32-bit compiler (so that pointer is 32-bit and fits in int)
// NOTE2: __asm block is specific for Visual C++. In GCC use https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
#define PUSH_ADDRESS(labelName) {               \
    void* tmpPointer;                           \
    __asm{ mov [tmpPointer], offset labelName } \
    push(reinterpret_cast<int>(tmpPointer));    \
}

// why we need indirection, read https://stackoverflow.com/a/13301627/264047
#define TOKENPASTE(x, y) x ## y
#define TOKENPASTE2(x, y) TOKENPASTE(x, y)

// generates token (not a string) we will use as label name. 
// Example: LABEL_NAME(155) will generate token `lbl_155`
#define LABEL_NAME(num) TOKENPASTE2(lbl_, num)

#define CALL_IMPL(funcLabelName, callId)    \
    PUSH_ADDRESS(LABEL_NAME(callId));       \
    goto funcLabelName;                     \
    LABEL_NAME(callId) :

// saves return address on the stack and jumps to label `funcLabelName`
#define CALL(funcLabelName) CALL_IMPL(funcLabelName, __LINE__)

// takes address at the top of stack and jump there
#define RET() {                                         \
    int tmpInt;                                         \
    pop(tmpInt);                                        \
    void* tmpPointer = reinterpret_cast<void*>(tmpInt); \
    __asm{ jmp tmpPointer }                             \
}

void myAlgo_asm() {
    goto my_algo_start;

triple_label:
    push(BP);
    BP = SP;
    SP -= 1;

    // stack[BP] == old BP, stack[BP + 1] == return address
    stack[BP - 1] = stack[BP + 2] * 3;
    AX = stack[BP - 1];

    SP = BP;     
    pop(BP);
    RET();

my_algo_start:
    push(BP);   // SP == 995
    BP = SP;    // BP == 995; stack[BP] == old BP, 
                // stack[BP + 1] == dummy return address, 
                // `a` at [BP + 2], `b` at [BP + 3]
    SP -= 2;    // SP == 993

    push(AX);
    push(stack[BP + 2]);
    CALL(triple_label);
    stack[BP - 1] = AX;
    SP -= 1;
    pop(AX);

    push(AX);
    push(stack[BP + 3]);
    CALL(triple_label);
    stack[BP - 2] = AX;
    SP -= 1;
    pop(AX);

    AX = stack[BP - 1] - stack[BP - 2];

    SP = BP; // cleanup locals, SP == 997
    pop(BP);
}

int main() {
    push(AX);
    push(22);
    push(11);
    push(7777); // dummy value, so that offsets inside function are like we've pushed return address
    myAlgo_asm();
    assert(myAlgo_withCalls(11, 22) == AX);
    SP += 1; // pop dummy "return address"
    SP += 2;
    pop(AX);
}

Notas:
10a. debido a que la dirección de retorno se almacena en la pila, en principio podemos cambiarla. Así es como funciona el ataque de aplastamiento de pilas
10b. las últimas 3 instrucciones al "final" de triple_label(limpiar locales, restaurar BP antiguo, regresar) se denominan epílogo de la función

11. Montaje

Ahora veamos el asm real myAlgo_withCalls. Para hacer eso en Visual Studio:

• establecer la plataforma de compilación en x86 ( no x86_64)
• tipo de compilación: depuración
• establecer un punto de interrupción en algún lugar dentro de myAlgo_withCalls
• ejecutar, y cuando la ejecución se detenga en el punto de interrupción, presione Ctrl + Alt + D

Una diferencia con nuestro C ++ tipo asm es que la pila de asm opera en bytes en lugar de ints. Entonces, para reservar espacio para uno int, SP se reducirá en 4 bytes.
Aquí vamos ( fragmento # 11.1 , los números de línea en los comentarios son de la esencia ):

;   114: int myAlgo_withCalls(int a, int b) {
 push        ebp        ; create stack frame 
 mov         ebp,esp  
; return address at (ebp + 4), `a` at (ebp + 8), `b` at (ebp + 12)
 
 sub         esp,0D8h   ; reserve space for locals. Compiler can reserve more bytes then needed. 0D8h is hexadecimal == 216 decimal 
 
 push        ebx        ; cdecl requires to save all these registers
 push        esi  
 push        edi  
 
 ; fill all the space for local variables (from (ebp-0D8h) to (ebp)) with value 0CCCCCCCCh repeated 36h times (36h * 4 == 0D8h)
 ; see https://stackoverflow.com/q/3818856/264047
 ; I guess that's for ease of debugging, so that stack is filled with recognizable values
 ; 0CCCCCCCCh in binary is 110011001100...
 lea         edi,[ebp-0D8h]     
 mov         ecx,36h    
 mov         eax,0CCCCCCCCh  
 rep stos    dword ptr es:[edi]  
 
;   115:    int t1 = triple(a);
 mov         eax,dword ptr [ebp+8]   ; push parameter `a` on the stack
 push        eax  
 
 call        triple (01A13E8h)  
 add         esp,4                   ; clean up param 
 mov         dword ptr [ebp-8],eax   ; copy result from eax to `t1`
 
;   116:    int t2 = triple(b);
 mov         eax,dword ptr [ebp+0Ch] ; push `b` (0Ch == 12)
 push        eax  
 
 call        triple (01A13E8h)  
 add         esp,4  
 mov         dword ptr [ebp-14h],eax ; t2 = eax
 
 mov         eax,dword ptr [ebp-8]   ; calculate and store result in eax
 sub         eax,dword ptr [ebp-14h]  

 pop         edi  ; restore registers
 pop         esi  
 pop         ebx  
 
 add         esp,0D8h  ; check we didn't mess up esp or ebp. this is only for debug builds
 cmp         ebp,esp  
 call        __RTC_CheckEsp (01A116Dh)  
 
 mov         esp,ebp  ; destroy frame
 pop         ebp  
 ret  

Y asm para tripple( fragmento # 11.2 ):

 push        ebp  
 mov         ebp,esp  
 sub         esp,0CCh  
 push        ebx  
 push        esi  
 push        edi  
 lea         edi,[ebp-0CCh]  
 mov         ecx,33h  
 mov         eax,0CCCCCCCCh  
 rep stos    dword ptr es:[edi]  
 imul        eax,dword ptr [ebp+8],3  
 mov         dword ptr [ebp-8],eax  
 mov         eax,dword ptr [ebp-8]  
 pop         edi  
 pop         esi  
 pop         ebx  
 mov         esp,ebp  
 pop         ebp  
 ret  

Espero que, después de leer esta publicación, el ensamblaje no se vea tan críptico como antes :)

Aquí hay enlaces del cuerpo de la publicación y algunas lecturas adicionales:

• Eli Bendersky , donde la parte superior de la pila está en x86 : superior / inferior, push / pop, SP, marco de pila, convenciones de llamada
• Eli Bendersky , diseño de marco de pila en x86-64 - args pasando en x64, marco de pila, zona roja
• University of Mariland, Understanding the Stack : una introducción muy bien escrita a los conceptos de stack. (Es para MIPS (no x86) y en sintaxis GAS, pero esto es insignificante para el tema). Consulte otras notas sobre la programación MIPS ISA si está interesado.
• x86 Asm wikibook, registros de propósito general
• wikibook de desmontaje x86, The Stack
• wikilibro de desmontaje x86, funciones y marcos de pila
• Manuales para desarrolladores de software de Intel : esperaba que fuera realmente duro, pero sorprendentemente es bastante fácil de leer (aunque la cantidad de información es abrumadora)
• Jonathan de Boyne Pollard, The gen on function perilogues - prólogo / epílogo, marco de pila / registro de activación, zona roja

Con respecto a si la pila está implementada en el hardware, este artículo de Wikipedia podría ayudar.

Algunas familias de procesadores, como x86, tienen instrucciones especiales para manipular la pila del subproceso que se está ejecutando actualmente. Otras familias de procesadores, incluidos PowerPC y MIPS, no tienen soporte de pila explícito, sino que dependen de la convención y delegan la gestión de pila a la Interfaz binaria de aplicación (ABI) del sistema operativo.

Ese artículo y los demás a los que se vincula pueden ser útiles para tener una idea del uso de la pila en los procesadores.

El concepto

Primero, piensa en todo el asunto como si fueras la persona que lo inventó. Me gusta esto:

Primero, piense en una matriz y cómo se implementa en el nivel bajo -> básicamente es solo un conjunto de ubicaciones de memoria contiguas (ubicaciones de memoria que están una al lado de la otra). Ahora que tiene esa imagen mental en su cabeza, piense en el hecho de que puede acceder a CUALQUIERA de esas ubicaciones de memoria y eliminarla cuando lo desee a medida que elimina o agrega datos en su matriz. Ahora piense en esa misma matriz, pero en lugar de la posibilidad de eliminar cualquier ubicación, decide que eliminará solo la ÚLTIMA ubicación a medida que elimina o agrega datos en su matriz. Ahora, su nueva idea para manipular los datos en esa matriz de esa manera se llama LIFO, que significa Último en entrar, primero en salir. Su idea es muy buena porque facilita el seguimiento del contenido de esa matriz sin tener que usar un algoritmo de clasificación cada vez que elimina algo de ella. También, para saber en todo momento cuál es la dirección del último objeto de la matriz, dedica un Registro en la Cpu para realizar un seguimiento de la misma. Ahora, la forma en que el registro lo rastrea es que cada vez que elimina o agrega algo a su matriz, también disminuye o aumenta el valor de la dirección en su registro por la cantidad de objetos que eliminó o agregó de la matriz (por la cantidad de espacio de direcciones que ocuparon). También desea asegurarse de que la cantidad en la que disminuye o aumenta ese registro se fija en una cantidad (como 4 ubicaciones de memoria, es decir, 4 bytes) por objeto, nuevamente, para facilitar el seguimiento y también para hacerlo posible para usar ese registro con algunas construcciones de bucle porque los bucles usan incrementos fijos por iteración (p. ej. para recorrer su matriz con un ciclo, construye el ciclo para incrementar su registro en 4 en cada iteración, lo que no sería posible si su matriz tiene objetos de diferentes tamaños). Por último, elige llamar a esta nueva estructura de datos "Pila", porque le recuerda a una pila de platos en un restaurante donde siempre quitan o agregan un plato en la parte superior de esa pila.

La implementación

Como puede ver, una pila no es más que una matriz de ubicaciones de memoria contiguas donde decidió cómo manipularla. Por eso, puede ver que ni siquiera necesita usar las instrucciones especiales y los registros para controlar la pila. Puede implementarlo usted mismo con las instrucciones básicas mov, add y sub y usando registros de propósito general en lugar de ESP y EBP como este:

mov edx, 0FFFFFFFFh

; -> esta será la dirección de inicio de su pila, más alejada de su código y datos, también servirá como ese registro que realiza un seguimiento del último objeto en la pila que expliqué anteriormente. Lo llama el "puntero de pila", por lo que elige el registro EDX para que sea para lo que se usa normalmente ESP.

sub edx, 4

mov [edx], dword ptr [someVar]

; -> estas dos instrucciones reducirán su puntero de pila en 4 ubicaciones de memoria y copiarán los 4 bytes comenzando en [someVar] ubicación de memoria a la ubicación de memoria a la que ahora apunta EDX, al igual que una instrucción PUSH disminuye el ESP, solo que aquí lo hizo manualmente y utilizó EDX. Entonces, la instrucción PUSH es básicamente un código de operación más corto que realmente hace esto con ESP.

mov eax, dword ptr [edx]

agregar edx, 4

; -> y aquí hacemos lo contrario, primero copiamos los 4 bytes comenzando en la ubicación de memoria a la que ahora apunta EDX en el registro EAX (elegido arbitrariamente aquí, podríamos haberlo copiado en cualquier lugar que quisiéramos). Y luego incrementamos nuestro puntero de pila EDX en 4 ubicaciones de memoria. Esto es lo que hace la instrucción POP.

Ahora puede ver que Intel acaba de agregar las instrucciones PUSH y POP y los registros ESP y EBP para facilitar la escritura y la lectura del concepto anterior de la estructura de datos de "pila". Todavía hay algunas Cpu-s RISC (conjunto de instrucciones reducidas) que no tienen las instrucciones PUSH y POP y registros dedicados para la manipulación de la pila, y mientras escribe programas de ensamblaje para esas Cpu-s, debe implementar la pila usted mismo como te mostré.

Confundes una pila abstracta y la pila implementada por hardware. Este último ya está implementado.

Creo que la respuesta principal que está buscando ya ha sido insinuada.

Cuando se inicia una computadora x86, la pila no está configurada. El programador debe configurarlo explícitamente en el momento del arranque. Sin embargo, si ya está en un sistema operativo, esto se ha solucionado. A continuación se muestra un ejemplo de código de un programa de arranque simple.

Primero se establecen los registros de segmento de datos y pila, y luego el puntero de pila se establece 0x4000 más allá de eso.

    movw    $BOOT_SEGMENT, %ax
    movw    %ax, %ds
    movw    %ax, %ss
    movw    $0x4000, %ax
    movw    %ax, %sp

Después de este código, se puede usar la pila. Ahora estoy seguro de que se puede hacer de diferentes formas, pero creo que esto debería ilustrar la idea.

La pila es solo una forma en que los programas y funciones usan la memoria.

La pila siempre me confundió, así que hice una ilustración:

( versión svg aquí )

La pila ya existe, por lo que puede asumir eso al escribir su código. La pila contiene las direcciones de retorno de las funciones, las variables locales y las variables que se pasan entre funciones. También hay registros de pila como BP, SP (Stack Pointer) incorporados que puede utilizar, de ahí los comandos incorporados que ha mencionado. Si la pila no estaba ya implementada, las funciones no se podían ejecutar y el flujo de código no podía funcionar.

La pila se "implementa" por medio del puntero de pila, que (asumiendo aquí la arquitectura x86) apunta al segmento de pila . Cada vez que se inserta algo en la pila (mediante pushl, llamada o un código de operación de pila similar), se escribe en la dirección a la que apunta el puntero de la pila y el puntero de la pila se reduce (la pila crece hacia abajo , es decir, direcciones más pequeñas) . Cuando saca algo de la pila (popl, ret), el puntero de la pila se incrementa y el valor se lee en la pila.

En una aplicación de espacio de usuario, la pila ya está configurada cuando se inicia la aplicación. En un entorno de espacio de kernel, primero debe configurar el segmento de pila y el puntero de pila ...

No he visto el ensamblador de Gas específicamente, pero en general la pila se "implementa" manteniendo una referencia a la ubicación en la memoria donde reside la parte superior de la pila. La ubicación de la memoria se almacena en un registro, que tiene diferentes nombres para diferentes arquitecturas, pero se puede considerar como el registro de puntero de pila.

Los comandos pop y push se implementan en la mayoría de arquitecturas basándose en microinstrucciones. Sin embargo, algunas "arquitecturas educativas" requieren que las implemente usted mismo. Funcionalmente, push se implementaría de esta manera:

   load the address in the stack pointer register to a gen. purpose register x
   store data y at the location x
   increment stack pointer register by size of y

Además, algunas arquitecturas almacenan la última dirección de memoria utilizada como Stack Pointer. Algunos almacenan la siguiente dirección disponible.

¿Qué es Stack? Una pila es un tipo de estructura de datos, un medio para almacenar información en una computadora. Cuando se ingresa un nuevo objeto en una pila, se coloca encima de todos los objetos ingresados ​​previamente. En otras palabras, la estructura de datos de la pila es como una pila de tarjetas, papeles, correos de tarjetas de crédito o cualquier otro objeto del mundo real que pueda imaginar. Cuando se quita un objeto de una pila, primero se quita el que está en la parte superior. Este método se conoce como LIFO (último en entrar, primero en salir).

El término "pila" también puede ser la abreviatura de pila de protocolos de red. En las redes, las conexiones entre computadoras se realizan a través de una serie de conexiones más pequeñas. Estas conexiones, o capas, actúan como la estructura de datos de la pila, ya que se crean y eliminan de la misma manera.

Tiene razón en que una pila es una estructura de datos. A menudo, las estructuras de datos (incluidas las pilas) con las que trabaja son abstractas y existen como una representación en la memoria.

La pila con la que está trabajando en este caso tiene una existencia más material: se asigna directamente a registros físicos reales en el procesador. Como estructura de datos, las pilas son estructuras FILO (primero en entrar, último en salir) que garantizan que los datos se eliminen en el orden inverso al que se ingresaron. ¡Vea el logotipo de StackOverflow para una imagen! ;)

Está trabajando con la pila de instrucciones . Esta es la pila de instrucciones reales que está alimentando al procesador.

La pila de llamadas se implementa mediante el conjunto de instrucciones x86 y el sistema operativo.

Instrucciones como push y pop ajustan el puntero de la pila mientras el sistema operativo se encarga de asignar memoria a medida que la pila crece para cada subproceso.

El hecho de que la pila x86 "crezca" de direcciones superiores a direcciones inferiores hace que esta arquitectura sea más susceptible al ataque de desbordamiento del búfer.

Tiene razón en que una pila es "solo" una estructura de datos. Aquí, sin embargo, se refiere a una pila implementada en hardware que se utiliza para un propósito especial: "La pila".

Mucha gente ha comentado acerca de la estructura de datos de pila implementada por hardware versus la pila (de software). Me gustaría agregar que hay tres tipos principales de estructuras de pila:

1. Una pila de llamadas: ¡cuál es la que está preguntando! Almacena los parámetros de función y la dirección de retorno, etc. Lea el Capítulo 4 (Todo sobre la 4ª página, es decir, la página 53) funciones de ese libro. Hay una buena explicación.
2. Una pila genérica que puede usar en su programa para hacer algo especial ...
3. Una pila de hardware genérica
   No estoy seguro de esto, pero recuerdo haber leído en alguna parte que hay una pila de hardware de propósito general implementada disponible en algunas arquitecturas. Si alguien sabe si esto es correcto, por favor comente.

Lo primero que debe saber es la arquitectura para la que está programando, lo que explica el libro (solo lo busqué, enlace). Para entender realmente las cosas, le sugiero que aprenda sobre la memoria, el direccionamiento, los registros y la arquitectura de x86 (supongo que eso es lo que está aprendiendo, del libro).

Las funciones de llamada, que requieren guardar y restaurar el estado local de forma LIFO (en lugar de decir, un enfoque de co-rutina generalizado), resulta ser una necesidad tan increíblemente común que los lenguajes ensambladores y las arquitecturas de CPU básicamente construyen esta funcionalidad. probablemente podría decirse de las nociones de subprocesos, protección de memoria, niveles de seguridad, etc. En teoría, podría implementar su propia pila, convenciones de llamadas, etc., pero supongo que algunos códigos de operación y la mayoría de los tiempos de ejecución existentes se basan en este concepto nativo de "pila". .

stackes parte de la memoria. se utiliza para inputy outputde functions. también se usa para recordar el retorno de la función.

esp registrar es recordar la dirección de la pila.

stacky espse implementan mediante hardware. también puede implementarlo usted mismo. hará que su programa sea muy lento.

ejemplo:

nop // esp= 0012ffc4

pulsar 0 // esp= 0012ffc0, Dword [0012ffc0] = 00000000

llamar proc01 // esp= 0012ffbc, Dword [0012ffbc] = eip, eip= adrr [proc01]

pop eax// eax= Dword [ esp], esp= esp+ 4

Estaba buscando cómo funciona la pila en términos de función y encontré que este blog es increíble y explica el concepto de pila desde cero y cómo la pila almacena el valor en la pila.

Ahora en tu respuesta. Lo explicaré con Python, pero obtendrá una buena idea de cómo funciona la pila en cualquier idioma.

Es un programa:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

Fuente: Cryptroix

algunos de sus temas que cubre en el blog:

How Function work ?
Calling a Function
 Functions In a Stack
 What is Return Address
 Stack
Stack Frame
Call Stack
Frame Pointer (FP) or Base Pointer (BP)
Stack Pointer (SP)
Allocation stack and deallocation of stack
StackoverFlow
What is Heap?

Pero se explica con el lenguaje Python, así que si quieres puedes echarle un vistazo.