blog · git · desktop · images · contact

grep.asm – Schritt 1: Ein naives cat

2018-08-11

Es gab kürzlich bei Computerphile einen kurzen Talk von Brian Kernighan über den Ursprung des Namens „grep“. Dort hat er auch erwähnt, dass ed und dann grep in PDP 11 Assembler geschrieben waren. Da dachte ich mir: Das wäre doch eine nette Übung, mal ein grep in x86-64 Assembler zu schreiben. :-)

Es wird ein paar Einschränkungen geben:

Darüberhinaus bin ich mal ganz sicher nicht Ken Thompson. Das wird also eine Weile dauern. :-) Im Laufe der nächsten Monate werden voraussichtlich mehrere Blogposts dazu entstehen.

Wer Fehler findet oder Verbesserungen hat, immer her damit.

Ein naives, zeilenorientiertes cat

Der erste Schritt wird sein, ein zeilenbasiertes cat zu schreiben. Lies eine Zeile ein, dann gib sie wieder aus. Der folgende Code wird genau das tun. Der nächste Schritt ist dann, mal wieder mehr über x86-64 Assembler zu lernen und einige ineffiziente oder schlichtweg „blöde“ Code-Stellen zu beseitigen. Danach kann ich dann schauen, wie man überhaupt eine Regex-Engine programmiert und dann nur die matchenden Zeilen ausgeben lassen.

(Das hier ist natürlich noch nicht einmal cat, weil es nichts konkatenieren kann. Ist trotzdem klar, was ich meine.)

Das Programm wird keine Bibliotheken benutzen. Das schließt auch eine libc ein. Heißt also, dass wir Syscalls zur Kommunikation mit dem Kernel verwenden werden und sonst alles andere selbst schreiben. Wenn man also objdump auf die fertige Binary loslässt, soll nur unser eigener Code erscheinen.

Okay, hier ist das Hauptprogramm:

.text
.global _start

/* (0) */
_start:
    /* (1) */
    pushq %rbp
    movq %rsp, %rbp

    /* (2) */
    /*  -8(%rbp), 8 = pointer to current line (char *)
     * -16(%rbp), 8 = size of line buffer (size_t) */
    subq $16, %rsp

    /* Initialize our pointer with "NULL" and size with 0. */
    movq $0, -8(%rbp)
    movq $0, -16(%rbp)

    .Lreadwriteloop:
        /* (3) */
        /* Read a line. Memory management is done entirely by
         * readline(). */
        leaq -8(%rbp), %rdi
        leaq -16(%rbp), %rsi
        call readline

        /* Test if readline() returned 0. If it did, exit our loop. */
        cmpq $0, %rax
        je .Lreadwriteloop_end

        /* Print the line we've just read. */
        movq -8(%rbp), %rdi
        movq %rax, %rsi
        call print

        jmp .Lreadwriteloop

    .Lreadwriteloop_end:
        movq $0, %rdi
        call exit

Im Folgenden ein paar Erklärungen, falls du noch nie etwas mit Assembler zu tun hattest.

Bei (0) kann man das Label _start sehen. Hier beginnt das Programm. In C hat man es in aller Regel mit main() zu tun, das kommt aber aus der libc und das wollen wir hier nicht benutzen. Jedes Programm beginnt eigentlich bei _start und main() ist dann ein ziemlich dicker Wrapper drumherum. Zu dem Thema gibt es auch dieses ältere Posting.

Die zwei Instruktionen bei (1) bauen einen „Frame Pointer“ oder „Stack Frame“ auf. Auch dazu hatte ich schonmal etwas geschrieben – das war damals noch 32-Bit-Code, funktioniert aber bei 64 Bit im Wesentlichen genauso. Hier drüben gibt es nochmal eine Erklärung in Englisch dazu.

Die grundlegende Idee eines Frame Pointers ist, ein Register zu haben, das die Basisadresse des aktuellen Stack Frames enthält. Dieser Wert ist für die Laufzeit der aktuellen „Funktion“ fest. Dafür wird in aller Regel %rbp verwendet. Adressen relativ dazu können dann auf „Variablen“ auf dem Stack zeigen.

Beispiel:

movq $0, -8(%rbp)

movq heißt, „kopiere ein Quad Word“ (das sind bei uns 8 Bytes). Welche 8 Bytes? Ich benutze hier ein „immediate value“ und zwar eine 0. Wo soll das hinkopiert werden? In den Speicher, der vom Wert in %rbp adressiert wird – minus 8 Bytes. Der Stack in Linux wächst von hohen Adressen hin zu niedrigen Adressen, daher das „minus“.

Bei (2) wird dann die „Größe“ des Stack Frames verändert und dadurch Platz gemacht für unsere Variablen. Dabei wird nach meinem Verständnis nichts tatsächlich „allokiert“, aber zukünftige push-Instruktionen werden beeinflusst, weil diese relativ zu %rsp arbeiten. Wenn wir also einen Wert von %rsp abziehen, dann können wir so tun, als hätten wir ganz viele Werte auf den Stack gepusht, ohne die tatsächlichen push-Instruktionen auch auszuführen. Wenn irgendwelcher fremder Code dann eben doch ein push ausführt, wird er unseren Speicher nicht überschreiben. Auf der anderen Seite können wir selbst auf diese Weise den Speicher direkt ansprechen und zwar mit sowas wie -48(%rbp).

Heißt also, wir benutzen hier zwar Speicher auf dem Stack, aber ohne die Semantiken eines echten Stacks. Einfach, weil es einfacher ist. Es ist für uns linearer Speicher und wir können quasi jedes Byte individuell ansprechen.

So viel zur Wiederholung über Stack Frames.

Die Schleife um (3) herum wird dann eine Zeile lesen, prüfen, ob das tatsächlich funktioniert hat, und die Zeile dann ausgeben. Die Funktionen exit, print und readline sind noch nicht definiert, zu denen kommen wir gleich.

„Eine Funktion aufzurufen“ heißt, dass man sich an Calling Conventions halten sollte. Das ist ein absolutes Muss, wenn man Bibliotheksfunktionen aufrufen oder von ihnen aufgerufen werden möchte. In unserem Programm müssen wir uns aber nicht ganz so strikt daran halten, weil immer nur unser eigener Code läuft. Zum Beispiel habe ich ignoriert, dass manche Register von aufgerufenen Funktionen nicht überschrieben werden sollten. Ich versuche trotzdem, mich an die übliche cdecl-Konvention zu halten.

exit

Nicht so schwer:

exit:
    /* in: %rdi, exit code */

    /* 60 = _exit(), %rdi already contains the exit code */
    movq $60, %rax
    syscall

Einfach nur ein Syscall. Das ist jetzt der Punkt, an dem man alle Hoffnung aufgeben kann, dass dieses Programm noch woanders als unter Linux laufen könnte – es sei denn, dein Betriebssystem benutzt zufällig auch die Nummer 60, um einen Syscall zu beschreiben, der das Programm beendet.

Betrifft natürlich alle Syscalls. Die Nummerierung muss passen und die Parameter natürlich auch. Selbstverständlich muss man sich auch an die korrekte Calling Convention halten. Die ist bei Linux für Syscalls ein kleines bisschen anders als im Userland (siehe A.2.1 im SysV ABI draft und dieses alte Blogposting).

print

Ebenfalls nicht kompliziert:

print:
    /* Print the given number of bytes.
     *
     * in:
     *   %rdi, pointer to buffer (char *)
     *   %rsi, length of string (size_t) */

    /* Just shuffle arguments, call write(1, &buffer, len) (syscall #1) */
    movq %rsi, %rdx
    movq %rdi, %rsi
    movq $1, %rax
    movq $1, %rdi
    syscall
    ret

Eigentlich ist das auch nur ein Wrapper um den write()-Syscall von Linux mit einem festen Wert 1: File Descriptor Nummer 1 wird als stdout angenommen.

Ich hätte mir vielleicht exit und print sparen können und direkt im Hauptprogramm die Syscalls benutzen können. Habe ich nicht gemacht, weil ich das Programm etwas abstrakter und möglicherweise leichter verständlich halten wollte.

readline

Hier wird es jetzt interessant.

Mit etwa 100 Zeilen Code ist das die bisher längste Funktion. Wäre sie in C geschrieben, hätte sie diese Signatur:

size_t readline(char **buffer, size_t *buffer_size);

Der erste Parameter ist ein Pointer auf einen „String“, den wir aber nicht NUL-terminieren, weil wir faul sind. Der zweite Parameter ist ein Zeiger auf irgendwelche 8 Bytes, die die derzeitige Größe des Puffers speichern sollen. Beide Variablen leben auf dem Stack des Hauptprogramms – sie wurden bei Schritt (2) allokiert.

Unsere Implementierung von readline wird auf dem Heap dynamisch Speicher allokieren. Dort wird dann eine ganze Zeile abgelegt. Irgendwann in der Zukunft kann die (noch hypothetische) Regex-Engine dann auf diesem Puffer arbeiten. Für den Moment wird sein Inhalt aber einfach nur mittels print ausgegeben, nachdem wir readline wieder verlassen haben.

Um Speicher auf dem Heap zu allokieren, kann man unter Linux den brk()-Syscall benutzen. Ein brk(0) gibt der derzeitige Adresse des „Program Break“ zurück. Ruft man das zum ersten Mal auf, kriegt man eben irgendeine Adresse. Danach kann man aber brk(first_result + some_size) aufrufen, um damit den Program Break zu verschieben – und dadurch entsteht dann der Heap. Das macht in C die Funktion malloc() (manchmal) hinter den Kulissen. Eigentlich funktioniert das insgesamt recht ähnlich zu unserem Stack, allerdings in die andere Richtung. In Linux wächst der Heap in Richtung höherer Adressen.

Was wird readline also machen?

  1. Einen Puffer verwalten, um die gelesenen Daten zu speichern.
  2. Daten von stdin lesen und in diesem Puffer ablegen.
  3. Prüfen, ob wir gerade ein Newline-Zeichen gelesen haben, was dann das Ende der aktuellen Zeile darstellen würde.
  4. Am Ende die Zahl der gelesenen Bytes zurückgeben.

So sieht die tatsächliche Funktion dann aus:

readline:
    /* Read a line (terminated by \n or EOF) from stdin.
     *
     * in + out:
     *   %rdi, pointer to pointer to buffer (char **)
     *   %rsi, pointer to current size of buffer (size_t *)
     *
     * out:
     *   %rax, length of string read (including \n), 0 if EOF */
    pushq %rbp
    movq %rsp, %rbp

    /*  -8(%rbp), 8 = pointer to pointer to buffer (char **)
     * -16(%rbp), 8 = pointer to size of buffer (size_t *)
     * -24(%rbp), 8 = length of string
     * (other 8 bytes are alignment) */
    subq $32, %rsp

    movq %rdi, -8(%rbp)
    movq %rsi, -16(%rbp)
    movq $0, -24(%rbp)

    .Lreadline_next_byte:
        /* Check if there is still room in the buffer */
        movq -16(%rbp), %rbx
        movq (%rbx), %rax
        cmpq %rax, -24(%rbp)
        je .Lreadline_increase_buffer
        .Lreadline_buffer_large_enough:

        /* read(stdin, &(buffer + len), 1) (syscall #0, stdin = fd 0) */
        movq -8(%rbp), %rbx
        movq (%rbx), %rsi
        movq -24(%rbp), %rax
        addq %rax, %rsi

        movq $0, %rax
        movq $0, %rdi
        movq $1, %rdx
        syscall

        /* EOF? */
        cmpq $0, %rax
        je .Lreadline_exit

        /* We read something, so increase the counter. */
        movq -24(%rbp), %rax
        incq %rax
        movq %rax, -24(%rbp)

        /* \n found? */
        movq -8(%rbp), %rbx
        movq (%rbx), %rsi
        movq -24(%rbp), %rax
        decq %rax
        addq %rax, %rsi
        cmpb $10, (%rsi)
        je .Lreadline_exit

        jmp .Lreadline_next_byte

    .Lreadline_increase_buffer:
        /* Get address to base of heap if pointer is still NULL. */
        movq -8(%rbp), %rbx
        movq (%rbx), %rax
        cmpq $0, %rax
        je .Lreadline_initial_buffer_allocation
        .Lreadline_buffer_initially_allocated:

        /* Increase buffer by 32 bytes and call brk(base + new_size).
         * This includes saving the new buffer size to the memory
         * pointed by -16(%rbp). */
        movq -8(%rbp), %rbx
        movq (%rbx), %rdi
        movq -16(%rbp), %rbx
        movq (%rbx), %rax
        addq $32, %rax
        movq %rax, (%rbx)
        addq %rax, %rdi

        movq $12, %rax
        syscall
        jmp .Lreadline_buffer_large_enough

    .Lreadline_initial_buffer_allocation:
        /* brk(0) (syscall #12) to get base of heap */
        movq $12, %rax
        movq $0, %rdi
        syscall
        movq -8(%rbp), %rbx
        movq %rax, (%rbx)
        jmp .Lreadline_buffer_initially_allocated

    .Lreadline_exit:
        movq -24(%rbp), %rax
        leave
        ret

Das ist die „Schönheit“ von Assembler. Es ist echt lang, aber eigentlich auch echt einfach. Es ist nur ein Haufen von „kopiere Daten“, „addiere oder subtrahiere Zahlen“, „vergleiche Werte“, „springe irgendwo hin“ und „sezte einen Syscall ab“. Und eigentlich solltest du auch in der Lage sein, zu verstehen, was hier vor sich geht. Über Stack Frames haben wir schon gesprochen. Über brk() auch. Mit dem read()-Syscall solltest du eh vertraut sein. Und das war’s auch schon. Mehr Magie steckt da nicht drin.

Vermutlich ist es aber trotzdem schwer zu verstehen. Vor allen Dingen werden viele Adressen hin- und hergeschubst. Anfänger haben manchmal Probleme, einfache Pointer in C zu verstehen, und hier haben wir jetzt doppelte Pointer in Assembler. Trotzdem glaube ich, dass das eine lohnenswerte Übung ist: Wenn man erstmal verstanden hat, dass es sich einfach nur um Speicheradressen handelt und dass das ein fundamentaler und eigentlich simpler Teil des alltäglichen Programmmierens ist, dann werden einem Pointer in C ziemlich trivial vorkommen.

Trotzdem nochmal genauer:

In _start enthält das Register %rbp eine Adresse. Bei dieser Adresse beginnt der Stack. Das ist also schon ein „Pointer“ und mit (%rbp) kann man ihn dann dereferenzieren. -8(%rbp) heißt dann, dass 8 vom Wert in %rbp abgezogen werden soll (ohne %rbp zu verändern) und dann das Ergebnis davon für die eigentliche Operation zu benutzen.

leaq -8(%rbp), %rdi führt dieselbe Berechnung durch – subtrahiere 8 vom Wert in %rbp, ohne den Registerinhalt zu ändern – und speichert das Ergebnis dieser Berechnung in %rdi. lea steht für „load effective address“. Dasselbe Ergebnis könnte man erreichen, indem man den Wert von %rbp in ein anderes Register kopiert und dort die 8 subtrahiert, aber lea ist schneller und einfacher. In jedem Fall steht am Ende in %rdi eine Speicheradresse, unter der man eine weitere Adresse findet – ein „double pointer“.

%rdi wird also im Hauptprogramm (_start) gesetzt und dann als Parameter für readline benutzt. In readline selbst speichern wir dann eine Kopie dieses Wertes auf dem lokalen Stack. Wenn wir dann tatsächlich mit diesem Pointer arbeiten wollen, holen wir den Wert vom Stack (das ist nun das ursprüngliche %rdi) und dereferenzieren einmal. Damit bleibt ein einfacher Pointer übrig, ein „char *“, den wir dann read() übergeben können.

Weitere Anmerkungen:

Fazit

Den kompletten Code gibt es hier:

grep.asm

So, das ist jetzt nun mal gar nicht flott. Wir lesen Byte für Byte, was vermutlich das langsamste ist, was man tun kann. Ich habe noch gar nichts „mikro-optimiert“. Um ehrlich zu sein, es ist hauptsächlich einfach so runtergeschrieben worden. Deswegen heißt das Ding bis jetzt „ein naives cat“. Es ist zwar in Assembler geschrieben, aber das heißt eben noch lange nicht, dass es „toll und schnell“ ist. Das muss ich mir als nächstes anschauen.

Fortsetzung: Diese Serie geht in grep.asm – Schritt 2: Ein besseres cat weiter.

Comments?