OpenASP

Debugging: GCD

In dieser Einheit werden wir ein fehlerhaftes Programm analysieren und debuggen.

In dieser und den kommenden Wochen werden wir Ihnen für einige der Programmieraufgaben Materialvorlagen bereitstellen, die Ihnen das bearbeiten der Aufgaben erleichtern. Diese enthalten üblicherweise ein Rahmenprogramm, welches grundlegende I/O-Funktionalitäten bereitstellt, und ein Makefile, welches Anweisungen zum Kompilieren des Programms enthält.

1. Laden Sie die Vorlage herunter: wget https://openasp.aengelke.net/m/gcd.tar.gz

2. Extrahieren Sie die Dateien aus dem Tar-Archiv: tar xf gcd.tar.gz

3. Wechseln Sie in den neu angelegten Ordner gcd (cd gcd) und vergewissern Sie sich (ls), dass sich dort die Dateien gcd.c und Makefile befinden.

4. Öffnen Sie nun die Datei gcd.c mit einem Texteditor Ihrer Wahl. Welche Bedeutung haben folgende Zeilen?

   • #include <stdio.h>

     Lösung

     Diese Präprozessoranweisung fügt lediglich den Inhalt der Datei stdio.h an der aktuellen Stelle ein. Diese sog. Header-Datei enthält Deklarationen von Funktionen wie printf, welche in der C-Standardbibliothek definiert sind.

   • void test(int, int);

     Lösung

     Diese Deklaration der Funktion gibt an, dass die genannte Funktion später oder in einer anderen Datei definiert wird. Zudem wird der Prototyp der Funktion (d.h. Rückgabetyp und Parametertypen) definiert.

   • int main(int argc, char** argv)

     Lösung

     Ein C-Programm beginnt üblicherweise bei der Funktion main. Die beiden Parameter geben die Anzahl und die Werte der Programmargumente an.

   • printf(...) (siehe auch: man 3 printf)

     Lösung

     printf nimmt einen Format-String (erstes Argument), fügt die nachfolgenden Werte in der genannten Reihenfolge in die Platzhalter ein. Der erste Platzhalter ist %s, d.h. printf erwartet als erstes Argument nach dem Format-String einen String (char*) und fügt diesen an der Stelle ein.

5. Kompilieren Sie das Programm mittels make und führen Sie es aus. Verhält sich das Programm wie erwartet?

   Hinweis: Sie können das Programm mit Ctrl-C abbrechen.

   Lösung

   Das Programm geht in eine Endlosschleife.

6. Bevor wir das Programm debuggen werden, lassen Sie sich die Disassembly des Programms anzeigen (objdump -d gcd | less). Können Sie die rekursiven Funktionsaufrufe identifizieren?

   Lösung

   Nein. Die Rekursion ist vom Compiler optimiert worden. Diese sog. Tail Call Optimization ist möglich, da der Rückgabewert der Rekursion nicht mehr verändert wird. Damit ist es möglich Tail-Recursion durch eine Schleife zu ersetzen. Dies passiert natürlich nur bei aktivierter Compiler-Optimierung.

7. Öffnen Sie die Datei Makefile und ändern Sie das Compiler -O2 zu -O0, um Optimierungen abzuschalten. Speichern Sie die Datei, löschen Sie die alte Binary mit make clean und kompilieren Sie das Programme erneut mit make. Wie verhält sich das Programm nun?

   Lösung

   Das Programm stürzt mit einem Segmentation Fault ab.

8. Ändern Sie das Compiler-Flags im Makefile erneut und fügen Sie zusätzlich das Flag -g hinzu. Nutzen Sie man gcc um die Bedeutung des Flags herauszufinden. (Es empfiehlt sich, die Suchfunktion durch Eingabe von /-g\b zu nutzen.) Kompilieren Sie das Programm erneut (make clean gcd).

   Lösung

   Das Flag -g weist den Compiler an, Debuginfos zu generieren und in die Binary zu schreiben.

9. Starten Sie den Debugger GDB (gdb ./gcd) und starten Sie das Programm (r als Abkürzung für run). Lassen Sie sich den Backtrace anzeigen (bt für backtrace). Erkennen Sie das Problem?

   Hinweis: Sie können auch ein ausgeführtes GDB-Kommando jederzeit mit Ctrl-C abbrechen.

   Lösung

   Es handelt sich um einen Stack Overflow.

10. Überlegen Sie, wie Sie das Problem lösen könnten.

    Lösung

    Man könnte eine andere Formulierung des Algorithmus nehmen, die kein Problem mit negativen Zahlen hat.

    int gcd(int a, int b) {
      return b ? gcd(b, a % b) : a;
    }