Implementazione di Alloca

Question

Come si implementa alloca() utilizzando l'assembler in linea x86 in lingue come D, C e C++? Voglio creare una versione leggermente modificata di esso, ma prima devo sapere come viene implementata la versione standard. Leggere il disassemblaggio dai compilatori non aiuta perché eseguono così tante ottimizzazioni e voglio solo la forma canonica.

Edit: Credo che la parte difficile è che voglio che questo abbia normale sintassi di chiamata di funzione, cioè utilizzando una funzione nuda o qualcosa del genere, rendilo simile al normale alloca().

Edit # 2: Ah, che diamine, si può presumere che non stiamo omettendo il puntatore del frame.

Answer 1

in esecuzione alloca in realtà richiede l'assistenza del compilatore. Alcune persone dicono che è facile come:

sub esp, <size> 

che purtroppo è solo metà dell'immagine. Sì, "allocerebbe spazio nello stack", ma ci sono un paio di trucchi.

1. se il compilatore aveva emesso il codice che fa riferimento altre variabili rispetto al esp invece di ebp (tipica se si compila senza puntatore telaio). Quindi è necessario modificare i riferimenti . Anche con i puntatori di frame, i compilatori lo fanno a volte.

2. ancora più importante, per definizione, lo spazio allocato con alloca deve essere "liberato" quando la funzione termina.

Il più grande è il punto 2. Poiché è necessario il compilare il codice per aggiungere simmetricamente <size> a esp in ogni punto di uscita della funzione.

Il caso più probabile è che il compilatore offra alcuni elementi intrinseci che consentono agli scrittori di librerie di chiedere al compilatore l'aiuto necessario.

EDIT:

Infatti, in glibc (implementazione GNU di libc). L'implementazione di alloca è semplicemente questo:

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

EDIT:

dopo averci pensato, il minimo credo sarebbe necessario sarebbe per il compilatore a sempre utilizzare una forma di cornice in qualsiasi funzioni che utilizzano alloca, indipendentemente dalle impostazioni di ottimizzazione. Ciò consentirebbe a tutti i locali di essere referenziati attraverso ebp in modo sicuro e la pulizia del frame verrebbe gestita ripristinando il puntatore del frame su esp.

EDIT:

così ho fatto alcuni esperimenti con cose come questa:

#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(); 
} 

che purtroppo non funziona correttamente. Dopo aver analizzato l'output dell'assembly da gcc. Sembra che le ottimizzazioni si intromettano. Il problema sembra essere che, poiché l'ottimizzatore del compilatore è completamente inconsapevole del mio assembly inline, ha l'abitudine di fare le cose in un ordine inaspettato e ancora riferimento a cose via esp.

Ecco l'ASM risultante:

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 

Come si può vedere, non è così semplice. Sfortunatamente, sostengo la mia affermazione iniziale secondo cui hai bisogno di assistenza per il compilatore.

Answer 2

Alloca è facile, basta spostare il puntatore dello stack verso l'alto; quindi generare tutte le letture/scritture per puntare a questo nuovo blocco

sub esp, 4 

Answer 3

Raccomando l'istruzione "invio". Disponibile su processori 286 e più recenti (è possibile che sia disponibile anche sul 186, non riesco a ricordare a priori, ma non erano comunque largamente disponibili).

Answer 4

alloca viene implementato direttamente nel codice assembly. Questo perché non puoi controllare il layout dello stack direttamente dai linguaggi di alto livello.

Si noti inoltre che la maggior parte delle implementazioni eseguirà alcune ottimizzazioni aggiuntive come l'allineamento dello stack per motivi di prestazioni. Il metodo standard di allocare spazio dello stack su X86 si presenta così:

sub esp, XXX 

Mentre XXX è il numero di byte da allcoate

Edit:
Se si vuole guardare alla implementazione (e stai usando MSVC) vedi alloca16.asm e chkstk.asm.
Il codice nel primo file allinea sostanzialmente la dimensione di allocazione desiderata a un limite di 16 byte. Il codice nel 2 ° file cammina effettivamente tutte le pagine che appartengono alla nuova area dello stack e le tocca. Ciò probabilmente innesca le eccezioni PAGE_GAURD che vengono utilizzate dal sistema operativo per far crescere lo stack.

Answer 5

Sarebbe complicato farlo - in effetti, a meno che non si abbia abbastanza controllo sulla generazione del codice del compilatore, non può essere fatto interamente in sicurezza. La tua routine avrebbe dovuto manipolare lo stack, in modo tale che quando veniva restituito tutto veniva pulito, ma il puntatore dello stack rimaneva in tale posizione che il blocco di memoria rimaneva in quel posto.

Il problema è che, a meno che non si possa informare il compilatore che il puntatore dello stack è stato modificato attraverso la chiamata di funzione, si può decidere che possa continuare a fare riferimento ad altri locals (o altro) attraverso il puntatore dello stack - ma gli offset saranno errati.

Answer 6

Per il linguaggio di programmazione D, il codice sorgente per alloca() viene fornito con download. Come funziona è abbastanza ben commentato. Per dmd1, è in /dmd/src/phobos/internal/alloca.d. Per dmd2, è in /dmd/src/druntime/src/compiler/dmd/alloca.d.

Answer 7

È possibile esaminare le fonti di un compilatore C open-source, come Open Watcom, e scoprire da soli

Answer 8

Gli standard C e C++ non specificare che alloca() deve l'uso della pila, in quanto non è alloca() negli standard C o C++ (o POSIX per quello) ¹.

Un compilatore può anche implementare alloca() utilizzando l'heap. Ad esempio, il compilatore ARM RealView (RVCT) alloca() utilizza malloc() per allocare il buffer (referenced on their website here) e fa sì che il compilatore emetta il codice che libera il buffer quando la funzione restituisce. Questo non richiede di giocare con il puntatore dello stack, ma richiede comunque il supporto del compilatore.

Microsoft Visual C++ ha una funzione _malloca() che utilizza l'heap se non c'è abbastanza spazio sullo stack, ma richiede al chiamante di utilizzare _freea(), a differenza _alloca(), che non ha bisogno/voglia liberazione esplicito.

(Con i distruttori C++ a disposizione, è possibile eseguire la pulizia senza il supporto del compilatore, ma non è possibile dichiarare variabili locali all'interno di un'espressione arbitraria, quindi non penso che si possa scrivere una macro alloca() che utilizza RAII. poi di nuovo, a quanto pare non è possibile utilizzare alloca() in alcune espressioni (come function parameters) comunque.)

¹ Sì, è legale di scrivere un alloca() che chiama semplicemente system("/usr/games/nethack").

Answer 9

Continuazione Passando Stile Assegnazione

a lunghezza variabile array in puro ISO C++. Implementazione Proof-of-Concept.

Uso

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

Nucleo Idea

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

Se non è possibile utilizzare array di lunghezza variabile di C99, è possibile utilizzare un cast letterale composto da un puntatore vuoto.

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

Questo funziona anche per -ansi (come estensione gcc) e anche quando è un argomento di funzione;

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

Il rovescio della medaglia è che quando compilato come C++, g ++> 4.6 vi darà un error: taking address of temporary array ... clang e ICC non si lamentano se