Alloca-Implementierung

Lesezeit: 9 Minuten

Benutzer-Avatar
dsimcha

Wie implementiert man alloca() mit Inline-x86-Assembler in Sprachen wie D, C und C++? Ich möchte eine leicht modifizierte Version davon erstellen, aber zuerst muss ich wissen, wie die Standardversion implementiert ist. Das Lesen der Disassemblierung von Compilern hilft nicht, weil sie so viele Optimierungen durchführen, und ich möchte nur die kanonische Form.

Bearbeiten: Ich denke, der schwierige Teil ist, dass ich möchte, dass dies eine normale Funktionsaufrufsyntax hat, dh mit einer nackten Funktion oder so etwas wie das normale alloca() aussieht.

Bearbeiten # 2: Ah, was soll’s, Sie können davon ausgehen, dass wir den Frame-Zeiger nicht weglassen.

Benutzer-Avatar
Evan Teran

umsetzen alloca eigentlich erfordert Compiler-Unterstützung. Ein paar Leute hier sagen, es ist so einfach wie:

sub esp, <size>

das ist leider nur die Hälfte des Bildes. Ja, das würde “Speicherplatz auf dem Stapel zuweisen”, aber es gibt ein paar Fallstricke.

  1. wenn der Compiler Code ausgegeben hätte, der andere Variablen relativ zu referenziert esp Anstatt von ebp
    (typisch, wenn Sie ohne Rahmenzeiger kompilieren). Dann müssen diese Referenzen angepasst werden. Sogar bei Frame-Zeigern tun Compiler dies manchmal.

  2. was noch wichtiger ist, per Definition zugewiesener Speicherplatz alloca muss “freigegeben” werden, wenn die Funktion beendet wird.

Der große Punkt ist Punkt 2. Wegen dir brauchen der Compiler zum Ausgeben von Code zum symmetrischen Hinzufügen <size> zu esp an jedem Austrittspunkt der Funktion.

Der wahrscheinlichste Fall ist, dass der Compiler einige Intrinsics anbietet, die es Bibliotheksautoren ermöglichen, den Compiler um die benötigte Hilfe zu bitten.

BEARBEITEN:

Tatsächlich in glibc (GNUs Implementierung von libc). Die Implementierung von alloca ist einfach das:

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

BEARBEITEN:

Nachdem ich darüber nachgedacht habe, wäre das Minimum, das meiner Meinung nach erforderlich wäre, der Compiler stets Verwenden Sie einen Rahmenzeiger in allen Funktionen, die verwendet werden alloca, unabhängig von den Optimierungseinstellungen. Dies würde ermöglichen, dass alle Einheimischen durchreferenziert werden ebp sicher und die Frame-Bereinigung würde durch Wiederherstellen des Frame-Zeigers gehandhabt esp.

BEARBEITEN:

Also habe ich ein paar Experimente mit solchen Dingen gemacht:

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

was leider funktioniert nicht korrekt. Nach der Analyse der Assembly-Ausgabe von gcc. Es scheint, dass Optimierungen im Weg stehen. Das Problem scheint zu sein, dass der Optimierer des Compilers, da er meine Inline-Assembly überhaupt nicht kennt, die Angewohnheit hat, die Dinge in einer unerwarteten Reihenfolge zu tun und still Verweisen auf Dinge über esp.

Hier ist das resultierende ASM:

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 <[email protected]>
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 <[email protected]>
8048496: mov    eax,DWORD PTR [ebp-0x4]
8048499: mov    DWORD PTR [esp],eax           ; <- whoops! compiler still referencing via esp
804849c: call   8048368 <[email protected]>
80484a1: leave
80484a2: ret

Wie Sie sehen können, ist es nicht so einfach. Leider bleibe ich bei meiner ursprünglichen Behauptung, dass Sie Compiler-Unterstützung benötigen.

  • Ich denke, da bist du in Ordnung; Die ESP-Zugriffe schreiben Argumente vor Funktionsaufrufen, und ESP-relativ ist korrekt. Du könntest es versuchen -fno-accumulate-outgoing-args oder was auch immer es und verwandte Argumente sind, um gcc dazu zu bringen, nur PUSH zu verwenden, anstatt MOV zu verwenden, um den unteren Teil des Stapels zu ändern.

    – Peter Cordes

    19. November 2016 um 14:59 Uhr


  • Aber wirklich, der Versuch, alloca hinter dem Rücken des Compilers zu implementieren, ist a abscheulich Idee, wie Sie im frühen Teil dieser hervorragenden Antwort darauf hinweisen. So viele Möglichkeiten, dass es schief geht, und es gibt keinen Grund, dies zu tun. Wenn Leute asm schreiben und ihre eigene Stapelzuweisung vornehmen wollen, schreiben Sie einfach in reinem asm, anstatt inline-asm in C++ zu missbrauchen.

    – Peter Cordes

    19. November 2016 um 15:01 Uhr

  • @PeterCordes stimmt, dass die meisten ESP-Referenzen Funktionsargumente sind, aber weil versucht wurde, den Speicherplatz vorab zuzuweisen Vor die “alloca”, diese Bewegungen trampeln auf dem “zugewiesenen Raum” des Benutzers herum. Was kaputt ist, wenn ich beabsichtige, diesen Raum zu verwenden. Das Ändern dieser zu richtigen Pushs würde das meiste beheben. Auch die letzte esp-Referenz speichert ein Ergebnis in einer lokalen Variablen und trampelt erneut auf dem “Array”. Es geht ziemlich schnell schlecht.

    – Evan Teran

    19. November 2016 um 15:18 Uhr


  • Oh, guter Punkt, ja, ich habe vergessen, wem welcher Raum gehört. Aber DWORD PTR [esp],eax schreibt ein Argument für puts; Ich sehe keinen ESP-relativen Zugriff auf einen lokalen. Wie auch immer, ich denke, wir sind uns einig, dass die Schlussfolgerung hier lautet: “Vielleicht möglich unter kontrollierten Bedingungen mit einer Reihe von gcc-Optionen, die normalerweise die Leistung beeinträchtigen; absolut nicht wert und eine schlechte Idee”. Vor allem, da es in x86-64-Code keine Möglichkeit gibt, dem Compiler mitzuteilen, dass Sie die rote Zone überschreiben möchten, sodass dies überhaupt nicht auf x86-64 portierbar ist.

    – Peter Cordes

    19. November 2016 um 15:34 Uhr

  • @PeterCordes, einverstanden und guter Anruf für den letzten DWORD PTR [esp],eax Ich habe das falsch gelesen, es wird tatsächlich nur ein Argument für die eingerichtet puts.

    – Evan Teran

    20. November 2016 um 5:23 Uhr

Es wäre schwierig, dies zu tun – in der Tat, wenn Sie nicht genügend Kontrolle über die Codegenerierung des Compilers haben, kann dies nicht ganz sicher durchgeführt werden. Ihre Routine müsste den Stapel so manipulieren, dass bei der Rückgabe alles bereinigt wurde, der Stapelzeiger jedoch an einer solchen Position blieb, dass der Speicherblock an dieser Stelle blieb.

Das Problem ist, dass, wenn Sie den Compiler nicht darüber informieren können, dass der Stapelzeiger über Ihren Funktionsaufruf geändert wurde, er möglicherweise entscheidet, dass er weiterhin über den Stapelzeiger auf andere lokale (oder was auch immer) verweisen kann – aber die Offsets werden sein falsch.

Benutzer-Avatar
bk1e

Die C- und C++-Standards spezifizieren das nicht alloca() muss den Stack verwenden, weil alloca() ist nicht in den C- oder C++-Standards (oder POSIX für diese Angelegenheit)¹.

Ein Compiler kann auch implementieren alloca() mit dem Haufen. Zum Beispiel der Compiler ARM RealView (RVCT). alloca() Verwendet malloc() um den Puffer zuzuweisen (hier auf ihrer Website verwiesen) und bewirkt außerdem, dass der Compiler Code ausgibt, der den Puffer freigibt, wenn die Funktion zurückkehrt. Dies erfordert kein Herumspielen mit dem Stapelzeiger, erfordert aber dennoch Compiler-Unterstützung.

Microsoft Visual C++ hat eine _malloca() Funktion, die den Heap verwendet, wenn nicht genügend Platz auf dem Stack vorhanden ist, der Aufrufer sie jedoch verwenden muss _freea()nicht wie _alloca()die keine explizite Freigabe benötigt/wünscht.

(Mit C++-Destruktoren, die Ihnen zur Verfügung stehen, können Sie die Bereinigung natürlich ohne Compiler-Unterstützung durchführen, aber Sie können keine lokalen Variablen innerhalb eines beliebigen Ausdrucks deklarieren, daher glaube ich nicht, dass Sie eine schreiben könnten alloca() Makro, das RAII verwendet. Andererseits können Sie anscheinend nicht verwenden alloca() in manchen Ausdrücken (wie Funktionsparameter) ohnehin.)

¹ Ja, es ist legal, eine zu schreiben alloca() das ruft einfach system("/usr/games/nethack").

Für die Programmiersprache D wird der Quellcode für alloca() mit dem geliefert Download. Wie es funktioniert, ist ziemlich gut kommentiert. Für dmd1 ist es in /dmd/src/phobos/internal/alloca.d. Für dmd2 befindet es sich in /dmd/src/druntime/src/compiler/dmd/alloca.d.

Fortsetzung Passing Style Alloca

Array variabler Länge in reines ISO-C++. Proof-of-Concept-Implementierung.

Verwendungszweck

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

Kernidee

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 auf github

Benutzer-Avatar
Brad Gilbert

alloca ist direkt im Assembler-Code implementiert. Das liegt daran, dass Sie das Stack-Layout nicht direkt von Hochsprachen aus steuern können.

Beachten Sie auch, dass die meisten Implementierungen einige zusätzliche Optimierungen durchführen, z. B. das Ausrichten des Stapels aus Leistungsgründen. Die Standardmethode zum Zuweisen von Stack-Speicherplatz auf X86 sieht folgendermaßen aus:

sub esp, XXX

Wobei XXX die Anzahl der Bytes für allcoate ist

Bearbeiten:

Wenn Sie sich die Implementierung ansehen möchten (und MSVC verwenden), sehen Sie sich alloca16.asm und chkstk.asm an.
Der Code in der ersten Datei richtet die gewünschte Zuweisungsgröße grundsätzlich an einer 16-Byte-Grenze aus. Der Code in der 2. Datei durchläuft tatsächlich alle Seiten, die zum neuen Stapelbereich gehören würden, und berührt sie. Dies wird möglicherweise PAGE_GAURD-Ausnahmen auslösen, die vom Betriebssystem verwendet werden, um den Stapel zu vergrößern.

Benutzer-Avatar
dmitjugow

Sie können Quellen eines Open-Source-C-Compilers untersuchen, z Öffnen Sie Watcomund finden Sie es selbst

1386070cookie-checkAlloca-Implementierung

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy