Implementazione di Alloca

Come si implementa alloca () usando l’assembler inline x86 in linguaggi 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: Suppongo che la parte più difficile sia che voglio che questo abbia una normale syntax di chiamata della funzione, cioè usando 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.

implementare l’ alloca richiede effettivamente l’ assistenza del compilatore . Alcune persone qui dicono che è facile come:

 sub esp,  

che sfortunatamente è solo metà dell’immagine. Sì, “allocerebbe spazio nello stack”, ma ci sono un paio di trucchi.

  1. se il compilatore ha emesso il codice che fa riferimento ad altre variabili relative ad esp anziché a ebp (tipico se si compila senza il puntatore del frame). Quindi quei riferimenti devono essere adeguati. 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. Perché è necessario che il compilatore emetta il codice per aggiungere in modo simmetrico ad 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.

MODIFICARE:

In effetti, in glibc (l’implementazione di GNU di libc). L’implementazione di alloca è semplicemente questa:

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

MODIFICARE:

dopo averci pensato, il minimo che credo sarebbe necessario sarebbe che il compilatore usasse sempre un puntatore del frame in qualsiasi funzione che usi alloca , indipendentemente dalle impostazioni di ottimizzazione. Ciò consentirebbe a tutti i locali di essere referenziati tramite ebp modo sicuro e la pulizia del frame verrebbe gestita ripristinando il puntatore del frame su esp .

MODIFICARE:

Così ho fatto alcuni esperimenti con cose del genere:

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

che sfortunatamente 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 di fare ancora riferimento alle cose tramite 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  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 

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

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 tu non possa informare il compilatore che il puntatore dello stack è stato modificato attraverso la tua chiamata di funzione, potrebbe decidere di continuare a riferirsi ad altri locals (o altro) attraverso il puntatore dello stack – ma gli offset saranno errato.

alloca è implementata 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 dell’implementazione eseguirà alcune ulteriori ottimizzazioni come l’allineamento dello stack per motivi di prestazioni. Il modo standard di allocare lo spazio di stack su X86 è simile al seguente:

 sub esp, XXX 

Mentre XXX è il numero di byte da allcoare

Modificare:
Se vuoi vedere l’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.

Per il linguaggio di programmazione D, il codice sorgente per alloca () viene fornito con il 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.

Gli standard C e C ++ non specificano che alloca() debba utilizzare lo stack, perché alloca() non è negli standard C o C ++ (o POSIX per questo) ¹.

Un compilatore può anche implementare alloca() usando l’heap. Ad esempio, l’alloca () del compilatore ARM RealView (RVCT) usa malloc() per allocare il buffer ( indicato nel loro sito Web qui ), e fa sì che il compilatore emetta il codice che libera il buffer quando la funzione ritorna. 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 usa l’heap se non c’è abbastanza spazio nello stack, ma richiede al chiamante di usare _freea() , a differenza di _alloca() , che non ha bisogno / vuole la liberazione esplicita.

(Con i distruttori C ++ a tua disposizione, puoi ovviamente eseguire la pulizia senza il supporto del compilatore, ma non puoi dichiarare variabili locali all’interno di un’espressione arbitraria, quindi non penso che potresti scrivere una macro alloca() che usa RAII. , a quanto pare non è ansible utilizzare alloca() in alcune espressioni (come i parametri di funzione ) in ogni caso).

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

Continuation Passing Style Alloca

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

uso

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

Idea fondamentale

 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 } 

DIMOSTRAZIONE DAL VIVO

cps_alloca su github

Puoi esaminare le fonti di un compilatore C open-source, come Open Watcom , e trovarlo tu stesso

Se non è ansible utilizzare le matrici a lunghezza variabile di c99, è ansible utilizzare un cast letterale composto per un puntatore void.

 #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 ti darà un errore: prendere l’indirizzo di un array temporaneo … clang e icc non si lamentano comunque

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 

Quello che vogliamo fare è qualcosa del genere:

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

In Assembly (Visual Studio 2017, 64 bit) sembra:

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

Sfortunatamente il nostro puntatore di ritorno è l’ultimo elemento in pila e non vogliamo sovrascriverlo. Inoltre, abbiamo bisogno di fare attenzione per l’allineamento, cioè. tondo fino a multipli di 8. Quindi dobbiamo fare questo:

 ;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 

Raccomando l’istruzione “invio”. Disponibile su processori 286 e più recenti ( potrebbe essere stato disponibile anche sul 186, non riesco a ricordare a priori, ma non erano comunque largamente disponibili).