c++ - Implementación de Alloca

memory-management assembly

Question

¿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 desmontaje de los compiladores 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 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 ().

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

Answer 1

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<Payload>(n,[](Payload *first,Payload *last)
    {
        fill(first,last,something);
    });
}

Idea principal

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
}

DEMO EN VIVO

cps_alloca en github

Answer 2

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

sub esp, 4

Answer 3

Lo que queremos hacer es algo así:

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

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

;alloca.asm

_TEXT SEGMENT
    PUBLIC alloca
    alloca PROC
        sub rsp, rcx ;<sp> -= size
        mov rax, rsp ;return <sp>;
        ret
    alloca ENDP
_TEXT ENDS

END

Lamentablemente, nuestro puntero de retorno es el último elemento de la pila, 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

Answer 4

Los estándares C y C ++ no especifican que alloca() tiene que usar la pila, porque alloca() no está 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 alloca() del compilador 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 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 usa el montón si no hay suficiente espacio en la pila, 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 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. , 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") .

Answer 5

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

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

Answer 7

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).

Answer 8

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 de que el puntero de la pila 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 pila, pero los desplazamientos serán incorrecto.

Answer 9

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 compila como c ++, g ++> 4.6 le dará un error: tomar la dirección de la matriz temporal ... clang y icc no se quejan, aunque

Answer 10

alloca se implementa directamente en el código de ensamblaje. Esto se debe a que no 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 las implementaciones realizarán algunas optimizaciones adicionales, como la alineación de la pila por motivos de rendimiento. La forma estándar de asignar espacio de pila 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 pila y las toca. Esto posiblemente activará las excepciones PAGE_GAURD que el SO usa para hacer crecer la pila.

Answer 11

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

sub esp, <size>

que lamentablemente es solo 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 relativas a esp lugar de ebp (típico si compila sin puntero de marco). Entonces esas referencias necesitan ser ajustadas. Incluso con punteros de marco, los compiladores 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 compilador emita 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.

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 compilador 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 <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 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 compilador 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 <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 puede ver, no es tan simple. Desafortunadamente, estoy de acuerdo con mi afirmación original de que necesita ayuda del compilador.