blog · git · desktop · images · contact
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.
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?
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:
.L
anfangen, sind lokale Symbole in GNU as.
Ich benutze sie als Jump-Labels innerhalb einer Funktion und die
sind dann nicht mehr im Weg, wenn man mit GDB mal debuggen muss.leave
ist das Gegenteil von pushq %rbp; movq %rsp, %rbp
. Es
verwirft also den aktuellen Stack Frame. Vielleicht ist aufgefallen,
dass exit
und print
gar kein Stack Frame haben, also gibt es
hier auch kein leave
. exit
hat noch nicht einmal ein ret
, weil
das Programm niemals aus dem Syscall zurückkehrt.mov
nicht beliebige Quellen und Ziele angeben.
Deswegen muss ich oft einen Wert erst vom Stack in irgendein
Register kopieren und dann dort nochmal dereferenzieren. Ich hoffe,
das ist so eine Sache, die man leicht optimieren kann.Den kompletten Code gibt es hier:
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.