Por fin luego de tanto luchar ya hallamos el arreglo de este contratiempo que muchos usuarios de esta web presentan. Si deseas aportar algún dato no dejes de compartir tu comentario.
Solución:
Creo que principalmente te estás confundiendo entre un program's stack y 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 de arriba 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 brinda 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 un resumen 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, puede almacenar valores en celdas aleatorias de stack matrizfragmento # 2.1):
stack[333] = 123;
stack[517] = 456;
stack[555] = stack[333] + stack[517];
Pero imagina lo difícil que sería recordar qué células de stack ya están en uso y cuáles son “gratuitos”. Es por eso que almacenamos nuevos valores en la pila uno al lado del otro.
Una cosa extraña sobre la pila de asm (x86) es que agrega cosas allí comenzando con el último índice y se mueve a índices inferiores: pila[999], luego apila[998] etcétera (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] es parte inferior de la pila.
La última celda utilizada (stack[997] en el ejemplo anterior) se llama 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 la 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 comienza un hilo, SP == STACK_CAPACITY y luego el 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 inferior a SP no es válido e inseguro (debido a las interrupciones del sistema), por lo que
primero disminuir 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 mira como se llamafragmento # 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. Empuje / haga estallar
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 myVar y 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 stack (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. return declaració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 la 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 referencia a parámetros de función y 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
La porción de pila, que pertenece y tiene el control total de la función se llama marco de pila de la función. P.ej myAlgo_noLPR_withAnchorEl marco de la pila 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 de pila y la Figura 6-2 en sección 6.3.2 Operación Far CALL y RET. Los parámetros de la función y el marco de pila son parte de registro de activación de la función (ver La generación de perílogos de funciones).
8b. las compensaciones positivas de BP apuntan a los parámetros de función y las compensaciones negativas apuntan a las 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 su pila de llamadas
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 convocatorias
En el fragmento 8.1, hemos enviado parámetros para myAlgo de derecha a izquierda y devuelto el resultado en AX. También podríamos pasar los parámetros de izquierda a derecha y regresar BX. O pase los parámetros en BX y CX y regrese en AX. Obviamente, la persona que llama (main()) y la función llamada deben acordar dónde y en qué orden se almacenan todas estas cosas.
Convención de llamadas es un conjunto de reglas sobre cómo se pasan los parámetros y se devuelve el resultado.
En el código anterior hemos usado 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
- El destinatario de la llamada debe conservar EBP y ESP (
myAlgo_noLPR_withAnchorfunción en nuestro caso), de modo que la persona que llama (mainfunción) puede confiar en que esos registros no hayan sido modificados por una llamada. - Todos los demás registros (EAX, <...>) puede ser modificado 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 “32-bit cdecl” 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 tripple De forma C ++, haga lo siguiente:
- Copiar
trippleel código al principio demyAlgocuerpo - a
myAlgosalto de entradatrippleel código congoto - cuando necesitamos ejecutar
tripple, guárdelo en la dirección de pila de la línea de código justo despuéstripplellamar, para que podamos volver aquí más tarde y continuar la ejecución (PUSH_ADDRESSmacro a continuación) - saltar a la dirección de la 1ra línea (
tripplefunción) y ejecutarlo hasta el final (3. y 4. juntos sonCALLmacro) - al final de
tripple(después de haber limpiado los locales), tome la dirección de retorno de la parte superior de la pila y salte 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(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(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:
10 a. 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 llaman epílogo de la función
11. Montaje
Ahora veamos el asm real para 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. Así que 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 que pasan en x64, marco de pila, zona roja
- University of Mariland, Understanding the Stack: una introducción realmente 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 de MIPS ISA si está interesado.
- x86 Asm wikibook, registros de propósito general
- wikilibro 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 explícito de pila, sino que se basan en 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 familiarizarse con el uso de la pila en los procesadores.
Sección de Reseñas y Valoraciones
No se te olvide compartir este ensayo si te ayudó.