Implementación de aloca

Question

¿Cómo se implementa alloca() usando el ensamblador x86 en línea en idiomas como D, C y C++? Quiero crear una versión ligeramente modificada, pero primero necesito saber cómo se implementa la versión estándar. Leer el desmontaje de los compiladores no ayuda porque realizan tantas optimizaciones, y solo quiero la forma canónica.

Editar: Supongo que la parte más difícil es que quiero que esto tenga una sintaxis de llamada a función normal, es decir, usar una función desnuda o algo así, hacer que se vea como la asignación normal().

Edición # 2: Ah, qué demonios, puede suponer que no estamos omitiendo el puntero del marco.

Answer 1

implementando alloca en realidad requiere la ayuda del compilador. Unas pocas personas aquí están diciendo que es tan fácil como:

sub esp, <size> 

que es, lamentablemente, sólo la mitad de la imagen. Sí, eso "asignaría espacio en la pila", pero hay un par de trampas.

1. si el compilador había emitido código que hace referencia a otras variables relativa a esp en lugar de ebp (típico si se compila con ningún puntero marco). Entonces esas referencias deben ajustarse. Incluso con punteros de marco, los compiladores hacen esto a veces.

2. más importante, por definición, el espacio asignado con alloca debe ser "liberado" cuando la función sale.

El grande es el punto # 2. Porque necesita el compilador para emitir código para agregar simétricamente <size> a esp en cada punto de salida de la función.

El caso más probable es que el compilador ofrece algunas características intrínsecas que permiten a los autores de la biblioteca solicitar al compilador la ayuda necesaria.

EDIT:

De hecho, en glibc (implementación de libc de GNU). La implementación de alloca es simplemente esto:

#ifdef __GNUC__ 
# define __alloca(size) __builtin_alloca (size) 
#endif /* GCC. */ 

EDIT:

después de pensarlo, el mínimo Creo que se necesitaría sería que el compilador para siempre usar el puntero en cualquier funciones que usa alloca, independientemente de la configuración de optimización. Esto permitiría hacer referencia a todos los locales a través del ebp de forma segura y la limpieza del marco se manejaría restaurando el puntero del marco al esp.

EDIT:

Así que he hecho un poco de experimentar con cosas como esta:

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

#define __alloca(p, N) \ 
    do { \ 
     __asm__ __volatile__(\ 
     "sub %1, %%esp \n" \ 
     "mov %%esp, %0 \n" \ 
     : "=m"(p) \ 
     : "i"(N) \ 
     : "esp"); \ 
    } while(0) 

int func() { 
    char *p; 
    __alloca(p, 100); 
    memset(p, 0, 100); 
    strcpy(p, "hello world\n"); 
    printf("%s\n", p); 
} 

int main() { 
    func(); 
} 

que por desgracia no funciona correctamente. Después de analizar la salida de ensamblaje por gcc. Parece que las optimizaciones se interponen. El problema parece ser que, dado que el optimizador del compilador desconoce por completo mi ensamblado en línea, tiene la costumbre de hacer las cosas en un orden inesperado y todavía haciendo referencia a cosas a través de esp.

Aquí está la ASM resultante:

8048454: push ebp 
8048455: mov ebp,esp 
8048457: sub esp,0x28 
804845a: sub esp,0x64      ; <- this and the line below are our "alloc" 
804845d: mov DWORD PTR [ebp-0x4],esp 
8048460: mov eax,DWORD PTR [ebp-0x4] 
8048463: mov DWORD PTR [esp+0x8],0x64  ; <- whoops! compiler still referencing via esp 
804846b: mov DWORD PTR [esp+0x4],0x0  ; <- whoops! compiler still referencing via esp 
8048473: mov DWORD PTR [esp],eax   ; <- whoops! compiler still referencing via esp   
8048476: call 8048338 <memset@plt> 
804847b: mov eax,DWORD PTR [ebp-0x4] 
804847e: mov DWORD PTR [esp+0x8],0xd  ; <- whoops! compiler still referencing via esp 
8048486: mov DWORD PTR [esp+0x4],0x80485a8 ; <- whoops! compiler still referencing via esp 
804848e: mov DWORD PTR [esp],eax   ; <- whoops! compiler still referencing via esp 
8048491: call 8048358 <memcpy@plt> 
8048496: mov eax,DWORD PTR [ebp-0x4] 
8048499: mov DWORD PTR [esp],eax   ; <- whoops! compiler still referencing via esp 
804849c: call 8048368 <puts@plt> 
80484a1: leave 
80484a2: ret 

Como se puede ver, no es tan simple. Desafortunadamente, estoy de acuerdo con mi afirmación original de que necesita ayuda del compilador.

Answer 2

Alloca es fácil, solo mueve el puntero de la pila; a continuación, generar todas las lecturas/escrituras para apuntar a este nuevo bloque

sub esp, 4 

Answer 3

Recomiendo la instrucción "enter". Disponible en 286 y los procesadores más nuevos (pueden han estado disponibles en el 186 también, no puedo recordar de improviso, pero esos no estaban ampliamente disponibles de todos modos).

Answer 4

alloca se implementa directamente en el código de ensamblaje. Eso se debe a que no se puede controlar el diseño de la pila directamente desde los lenguajes de alto nivel.

También tenga en cuenta que la mayoría de la implementación realizará algunas optimizaciones adicionales como la alineación de la pila por motivos de rendimiento. La forma estándar de asignación de espacio de pila en el X86 es el siguiente:

sub esp, XXX 

Mientras que XXX es el número de bytes a allcoate

Editar:
Si desea examinar la aplicación (y está usando MSVC) vea alloca16.asm y chkstk.asm.
El código en el primer archivo básicamente alinea el tamaño de asignación deseado a un límite de 16 bytes. El código en el segundo archivo realmente recorre todas las páginas que pertenecerían a la nueva área de pila y las toca. Esto posiblemente activará las excepciones PAGE_GAURD que el SO usa para hacer crecer la pila.

Answer 5

Sería complicado hacer esto; de hecho, a menos que tenga suficiente control sobre la generación del código del compilador, no se puede hacer de manera totalmente segura. Tu rutina debería manipular la pila, de modo que cuando volviera todo se limpiara, pero el puntero de la pila permanecía en una posición tal que el bloque de memoria permanecía en ese lugar. El problema es que a menos que pueda informar al compilador que el puntero de la pila se ha modificado en su llamada de función, bien puede decidir que puede seguir refiriéndose a otros locales (o lo que sea) a través del puntero de la pila, pero los desplazamientos serán incorrectos.

Answer 6

Para el lenguaje de programación D, el código fuente para alloca() viene con el download. Cómo funciona está bastante bien comentado. Para dmd1, está en /dmd/src/phobos/internal/alloca.d. Para dmd2, está en /dmd/src/druntime/src/compiler/dmd/alloca.d.

Answer 7

puede examinar las fuentes de un compilador de C de código abierto, como Open Watcom, y encontrar por sí mismo

Answer 8

Los estándares de C y C++ no especificar que alloca() tiene que el uso de la pila, porque no es alloca() en los estándares C o C++ (o POSIX para el caso) ¹.

Un compilador también puede implementar alloca() usando el montón. Por ejemplo, el compilador ARM RealView (RVCT) alloca() usa malloc() para asignar el búfer (referenced on their website here) y también hace que el compilador emita código que libera el búfer cuando la función retorna. Esto no requiere jugar con el puntero de la pila, pero aún requiere soporte del compilador.

Microsoft Visual C++ tiene una función _malloca() que utiliza la pila si no hay suficiente espacio en la pila, pero requiere de la persona que llama a utilizar _freea(), a diferencia de _alloca(), que no necesita/quiere liberación explícita.

(Con destructores C++ a su disposición, obviamente puede hacer la limpieza sin soporte del compilador, pero no puede declarar variables locales dentro de una expresión arbitraria así que no creo que pueda escribir una macro alloca() que use RAII. por otra parte, al parecer, no se puede utilizar alloca() en algunas expresiones (como function parameters) de todos modos.)

¹ Sí, es legal para escribir un alloca() que simplemente llama system("/usr/games/nethack").

Answer 9

Continuación Pasando Estilo alloca

matriz de longitud variable en puro ISO C++. Implementación de prueba de concepto.

Uso

void foo(unsigned n) 
{ 
    cps_alloca<Payload>(n,[](Payload *first,Payload *last) 
    { 
     fill(first,last,something); 
    }); 
} 

idea central

template<typename T,unsigned N,typename F> 
auto cps_alloca_static(F &&f) -> decltype(f(nullptr,nullptr)) 
{ 
    T data[N]; 
    return f(&data[0],&data[0]+N); 
} 

template<typename T,typename F> 
auto cps_alloca_dynamic(unsigned n,F &&f) -> decltype(f(nullptr,nullptr)) 
{ 
    vector<T> data(n); 
    return f(&data[0],&data[0]+n); 
} 

template<typename T,typename F> 
auto cps_alloca(unsigned n,F &&f) -> decltype(f(nullptr,nullptr)) 
{ 
    switch(n) 
    { 
     case 1: return cps_alloca_static<T,1>(f); 
     case 2: return cps_alloca_static<T,2>(f); 
     case 3: return cps_alloca_static<T,3>(f); 
     case 4: return cps_alloca_static<T,4>(f); 
     case 0: return f(nullptr,nullptr); 
     default: return cps_alloca_dynamic<T>(n,f); 
    }; // mpl::for_each/array/index pack/recursive bsearch/etc variacion 
} 

LIVE DEMO

cps_alloca on github

Answer 10

Si no puede utilizar matrices de longitud variable de C99, se puede utilizar un molde literal compuesto de un puntero de vacío

#define ALLOCA(sz) ((void*)((char[sz]){0})) 

Esto también funciona para -ansi (como una extensión gcc) e incluso cuando se trata de un argumento de la función;

some_func(&useful_return, ALLOCA(sizeof(struct useless_return))); 

La desventaja es que cuando se compila como C++, g ++> 4.6 le dará una error: taking address of temporary array ... sonido metálico y el ICC no se quejan de que