implementazione alloca
-
23-08-2019 - |
Domanda
Come si fa a implementare alloca () utilizzando inline assembler x86 in linguaggi come D, C e C ++? Voglio creare una versione leggermente modificata di esso, ma prima ho bisogno di sapere come viene implementata la versione standard. Leggendo il disassemblaggio da compilatori non aiuta perché svolgono tante ottimizzazioni, e voglio solo la forma canonica.
Edit: Credo che la parte più difficile è che voglio che questo abbia normale sintassi di chiamata di funzione, vale a dire utilizzando una funzione nudo o qualcosa, far sembrare il normale alloca ()
.Modifica # 2:. Ah, che diamine, si può assumere che non stiamo tralasciando il puntatore riquadro
Soluzione
attuazione alloca
realtà richiede assistenza compilatore . Alcune persone qui stanno dicendo che è facile come:
sub esp, <size>
che purtroppo è solo la metà del quadro. Sì che sarebbe "allocare spazio sullo stack", ma ci sono un paio di grattacapi.
-
codice, se il compilatore aveva emesso che fa riferimento altre variabili rispetto al
esp
anzichéebp
(Tipica se si compila senza frame pointer). poi quelli i riferimenti devono essere adeguate. Anche con i puntatori telaio, compilatori lo fanno a volte. -
ancora più importante, per definizione, lo spazio allocato con
alloca
deve essere "Liberata", quando la funzione termina.
Il grande è il punto # 2. Perché si necessità al compilatore di emettere codice per aggiungere simmetricamente <size>
a esp
in ogni punto di uscita della funzione.
Il caso più probabile è il compilatore offre alcune intrinseche che permettono scrittori libreria per chiedere al compilatore per l'aiuto necessario.
Modifica
In realtà, in glibc (implementazione GNU di libc). L'implementazione di alloca
è semplicemente questo:
#ifdef __GNUC__
# define __alloca(size) __builtin_alloca (size)
#endif /* GCC. */
Modifica
dopo averci pensato, il minimo credo sarebbe necessario sarebbe per il compilatore a sempre utilizzare una forma di cornice in qualsiasi funzione che utilizza alloca
, indipendentemente dalle impostazioni di ottimizzazione. Ciò consentirebbe tutti i locali a fare riferimento tramite ebp
in modo sicuro e la pulizia telaio verrebbe gestita ripristinando il puntatore riquadro a esp
.
Modifica
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 in modo corretto. Dopo analisi della produzione assembly gcc. Sembra che le ottimizzazioni intralcio. Il problema sembra essere che, poiché l'ottimizzatore del compilatore è del tutto ignaro del mio assembly inline, si ha l'abitudine di fare le cose in un ordine imprevisto e ancora fa 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. Purtroppo, io sto con la mia affermazione originale che avete bisogno di assistenza compilatore.
Altri suggerimenti
Sarebbe difficile per fare questo - in realtà, se non avete abbastanza controllo sulla generazione del codice del compilatore non può essere fatto interamente in modo sicuro. Vostra routine dovrebbe manipolare lo stack, in modo tale che quando è tornato tutto era pulita, ma lo stack pointer rimasto in una posizione tale che il blocco di memoria è rimasta in quel luogo.
Il problema è che se non è possibile informare il compilatore che lo stack pointer è stato modificato attraverso il vostro chiamata di funzione, si può anche decidere che si può continuare a fare riferimento ad altri locali (o altro) attraverso lo stack pointer - ma il compensazioni non saranno corretti.
Per il linguaggio di programmazione D, il codice sorgente per alloca () viene fornito con la scaricare . 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.
Il C e C ++ non specificare che alloca()
ha per l'utilizzo dello stack, perché alloca()
non è in C o C ++ standard (POSIX o per quella materia) ¹.
Un compilatore può anche applicare alloca()
utilizzando il mucchio. Ad esempio, il RealView ARM (RVCT) alloca()
di compilatore utilizza malloc()
per allocare il buffer ( fa riferimento sul loro sito web qui ), e causa anche il compilatore ad emettere il codice che libera il buffer quando la funzione restituisce. Questo non richiede giocare con lo stack pointer, ma richiede ancora il supporto del compilatore.
Microsoft Visual C ++ ha un href="http://msdn.microsoft.com/en-us/library/5471dc8s.aspx" rel="nofollow noreferrer"> _malloca()
funzione _freea(), a differenza _alloca()
, che non ha bisogno / voglia liberazione esplicito.
(Con distruttori C ++ a vostra disposizione, è possibile ovviamente fare la pulizia senza il supporto del compilatore, ma non è possibile dichiarare le variabili locali all'interno di un'espressione arbitraria quindi non credo che si potrebbe scrivere una macro che utilizza alloca()
Raii. Poi ancora una volta, a quanto pare non è possibile utilizzare alloca()
in alcune espressioni (come parametri della funzione ) in ogni caso .)
¹ Sì, è legale di scrivere un alloca()
che chiama semplicemente system("/usr/games/nethack")
.
alloca è implementata direttamente nel codice assembly. Questo perché non si può controllare il layout dello stack direttamente da linguaggi di alto livello.
Si noti inoltre che la maggior parte implementazione eseguirà qualche ottimizzazione 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
considerando che XXX è il numero di byte da allcoate
Modifica
Se si vuole guardare alla implementazione (e si sta utilizzando MSVC) vedi alloca16.asm e chkstk.asm.
Il codice nel primo file allinea sostanzialmente la dimensione di allocazione desiderata per un limite di 16 byte. Codice nel 2 ° di file in realtà passeggiate tutte le pagine che appartengono alla nuova area di stack e li tocca. Questo sarà probabilmente innescherà eccezioni PAGE_GAURD che vengono utilizzati dal sistema operativo a crescere lo stack.
Continuazione Passando Stile Assegnazione
a lunghezza variabile array in pura ISO C ++ . Proof-of-Concept implementazione.
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
}
È possibile esaminare le fonti di un compilatore C open-source, come Open Watcom , e trovare da soli
Se non è possibile utilizzare array di lunghezza variabile di C99, è possibile utilizzare un cast composto letterale a un puntatore nullo.
#define ALLOCA(sz) ((void*)((char[sz]){0}))
Questo funziona anche per -ansi (come estensione gcc) ed 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 errore: prendere l'indirizzo di array temporaneo ... clang e ICC non si lamentano se
Quello che vogliamo fare è qualcosa di simile:
void* alloca(size_t size) {
<sp> -= size;
return <sp>;
}
In Assembly (Visual Studio 2017, 64bit) sembra che:
;alloca.asm
_TEXT SEGMENT
PUBLIC alloca
alloca PROC
sub rsp, rcx ;<sp> -= size
mov rax, rsp ;return <sp>;
ret
alloca ENDP
_TEXT ENDS
END
Purtroppo il nostro puntatore di ritorno è l'ultimo elemento nello stack, e non vogliamo sovrascrivere. Inoltre abbiamo bisogno di prendersi cura per l'allineamento, vale a dire. rotondo size fino a multiplo 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
Assegnazione è facile, basta spostare il puntatore stack; quindi generare tutta la lettura / scrittura a punto a questo nuovo blocco
sub esp, 4
Vi consiglio l'istruzione "enter". Disponibile su 286 e più recenti processori ( possono sono stati disponibili sulla 186 così, non riesco a ricordare due piedi, ma quelli non erano ampiamente disponibili in ogni modo).