Implementación de Alloca

¿Cómo se implementa alloca () utilizando 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 desassembly de los comstackdores no ayuda porque realizan tantas optimizaciones, y solo quiero la forma canónica.

Edición: supongo que la parte más difícil es que quiero que tenga una syntax 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 ().

Editar # 2: Ah, qué diablos, puedes asumir que no estamos omitiendo el puntero del marco.

la implementación de alloca realidad requiere la asistencia del comstackdor . Algunas personas aquí dicen que es tan fácil como:

 sub esp,  

que lamentablemente es solo la mitad de la imagen. Sí, eso “asignaría espacio en la stack”, pero hay un par de trampas.

  1. si el comstackdor había emitido código que hace referencia a otras variables relativas a esp lugar de ebp (típico si comstack sin puntero de marco). Entonces esas referencias necesitan ser ajustadas. Incluso con punteros de marco, los comstackdores hacen esto a veces.

  2. más importante aún, por definición, el espacio asignado con alloca debe ser “liberado” cuando la función finaliza.

El grande es el punto # 2. Porque necesita que el comstackdor emita código para agregar simétricamente a esp en cada punto de salida de la función.

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

EDITAR:

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

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

EDITAR:

después de pensarlo, lo mínimo que creo que se requeriría sería que el comstackdor siempre use un puntero de marco en cualquier función que use alloca , independientemente de las configuraciones de optimización. Esto permitiría hacer referencia a todos los locales a través de ebp forma segura y la limpieza del cuadro se manejaría restaurando el puntero del marco a esp .

EDITAR:

Así que hice algo de experimentación con cosas como esta:

 #include  #include  #include  #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 lamentablemente 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 comstackdor desconoce por completo mi ensamblado en línea, tiene la costumbre de hacer las cosas en un orden inesperado y seguir haciendo referencia a las 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  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  8048496: mov eax,DWORD PTR [ebp-0x4] 8048499: mov DWORD PTR [esp],eax ; <- whoops! compiler still referencing via esp 804849c: call 8048368  80484a1: leave 80484a2: ret 

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

Sería complicado hacer esto; de hecho, a menos que tenga suficiente control sobre la generación del código del comstackdor, no se puede hacer de manera totalmente segura. Tu rutina debería manipular la stack, de modo que cuando volviera todo se limpiara, pero el puntero de la stack 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 comstackdor de que el puntero de la stack se ha modificado a través de 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 stack, pero los desplazamientos serán incorrecto.

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

También tenga en cuenta que la mayoría de las implementaciones realizarán algunas optimizaciones adicionales, como la alineación de la stack por motivos de rendimiento. La forma estándar de asignar espacio de stack en X86 tiene este aspecto:

 sub esp, XXX 

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

Editar:
Si desea ver la implementació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 con 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 stack y las toca. Esto posiblemente activará las excepciones PAGE_GAURD que el SO usa para hacer crecer la stack.

Para el lenguaje de progtwigción D, el código fuente de alloca () viene con la descarga . 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.

Los estándares C y C ++ no especifican que alloca() tiene que usar la stack, porque alloca() no está en los estándares C o C ++ (o POSIX para el caso) ¹.

Un comstackdor también puede implementar alloca() usando el montón. Por ejemplo, el alloca() del comstackdor ARM RealView (RVCT) utiliza malloc() para asignar el búfer (al que se hace referencia en su sitio web aquí ), y también hace que el comstackdor emita código que libera el búfer cuando la función retorna. Esto no requiere jugar con el puntero de la stack, pero aún requiere soporte del comstackdor.

Microsoft Visual C ++ tiene una función _malloca() que usa el montón si no hay suficiente espacio en la stack, pero requiere que la persona que llama use _freea() , a diferencia de _alloca() , que no necesita / quiere un permiso explícito.

(Con destructores C ++ a su disposición, obviamente puede hacer la limpieza sin soporte del comstackdor, 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. , al parecer, no se puede usar alloca() en algunas expresiones (como los parámetros de función ) de todos modos.)

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

Continuación Pasando Estilo Alloca

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

Uso

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

Idea principal

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

DEMO EN VIVO

cps_alloca en github

Puede examinar las fonts de un comstackdor C de código abierto, como Open Watcom , y encontrarlo usted mismo

Si no puede usar las matrices de longitud variable de c99, puede usar un molde literal compuesto en un puntero vacío.

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

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

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

El inconveniente es que cuando se comstack como c ++, g ++> 4.6 le dará un error: tomar la dirección de la matriz temporal … clang y icc no se quejan, aunque

Alloca es fácil, solo mueves el puntero de la stack; luego genere todas las lecturas / escrituras para apuntar a este nuevo bloque

 sub esp, 4 

Lo que queremos hacer es algo así:

 void* alloca(size_t size) {  -= size; return ; } 

En Assembly (Visual Studio 2017, 64 bits) se ve así:

 ;alloca.asm _TEXT SEGMENT PUBLIC alloca alloca PROC sub rsp, rcx ; -= size mov rax, rsp ;return ; ret alloca ENDP _TEXT ENDS END 

Lamentablemente, nuestro puntero de retorno es el último elemento de la stack, y no queremos sobrescribirlo. Además, debemos cuidar la alineación, es decir. tamaño redondo hasta múltiplo de 8. Así que tenemos que hacer esto:

 ;alloca.asm _TEXT SEGMENT PUBLIC alloca alloca PROC ;round up to multiple of 8 mov rax, rcx mov rbx, 8 xor rdx, rdx div rbx sub rbx, rdx mov rax, rbx mov rbx, 8 xor rdx, rdx div rbx add rcx, rdx ;increase stack pointer pop rbx sub rsp, rcx mov rax, rsp push rbx ret alloca ENDP _TEXT ENDS END 

Recomiendo la instrucción “enter”. Disponible en 286 y procesadores más nuevos ( puede haber estado disponible también en el 186, no puedo recordarlo de improviso, pero esos no estaban ampliamente disponibles de todos modos).