Wie findet man eigentlich so einen Fehler wenn man dies nicht auf dem ersten Blick sieht?
Zuerst kompiliert das Programm gar nicht und es kommt die Meldung:
Code: Select all
In file included from /usr/include/stdio.h:34,
from merge.c:4:
/lfs/user/bartosch/software/gcc/lib/gcc/i686-pc-linux-gnu/3.4.0/include/stddef.h:213: error: syntax error before "typedef"
merge.c:74:74: warning: no newline at end of file
Da in der Headerdatei stddef.h wohl kaum Fehler zu finden sind, muß es davor sein. Unterstützt durch das Codehighlighting des Editors findet man irgendwann, dass "Mergesort" nicht auskommentiert ist.
Dannach kompiliert das Programm, aber es stürzt mit einer Segmentation Violation ab. Folglich wird irgendwo auf Speicher zugegriffen, der nicht benutzt werden darf. Um solche Fehler zu finden, benutzen wir das Tool valgrind, das dafür prädestiniert ist.
Code: Select all
valgrind --tool=memcheck --num-callers=32 ./a.out
Das Ergebnis ist:
Code: Select all
==285== Memcheck, a memory error detector for x86-linux.
==285== Copyright (C) 2002-2003, and GNU GPL'd, by Julian Seward.
==285== Using valgrind-2.1.0, a program supervision framework for x86-linux.
==285== Copyright (C) 2000-2003, and GNU GPL'd, by Julian Seward.
==285== Estimated CPU clock rate is 2826 MHz
==285== For more details, rerun with: -v
==285==
Unsortierter String!
==285== Conditional jump or move depends on uninitialised value(s)
==285== at 0x402B3341: _IO_file_overflow@@GLIBC_2.1 (in /lib/libc.so.6)
==285== by 0x402B4599: __overflow (in /lib/libc.so.6)
==285== by 0x40292654: _IO_vfprintf (in /lib/libc.so.6)
==285== by 0x40299CC1: _IO_printf (in /lib/libc.so.6)
==285== by 0x804854E: ausgabe (merge.c:70)
==285== by 0x804839E: main (merge.c:18)
==285==
==285== Conditional jump or move depends on uninitialised value(s)
==285== at 0x402B3370: _IO_file_overflow@@GLIBC_2.1 (in /lib/libc.so.6)
==285== by 0x402B4599: __overflow (in /lib/libc.so.6)
==285== by 0x40292654: _IO_vfprintf (in /lib/libc.so.6)
==285== by 0x40299CC1: _IO_printf (in /lib/libc.so.6)
==285== by 0x804854E: ausgabe (merge.c:70)
==285== by 0x804839E: main (merge.c:18)
==285==
==285== Conditional jump or move depends on uninitialised value(s)
==285== at 0x40292601: _IO_vfprintf (in /lib/libc.so.6)
==285== by 0x40299CC1: _IO_printf (in /lib/libc.so.6)
==285== by 0x804854E: ausgabe (merge.c:70)
==285== by 0x804839E: main (merge.c:18)
==285==
==285== Conditional jump or move depends on uninitialised value(s)
==285== at 0x80484A2: mische (merge.c:49)
==285== by 0x804845F: sortiere (merge.c:38)
==285== by 0x804843F: sortiere (merge.c:36)
==285== by 0x804843F: sortiere (merge.c:36)
==285== by 0x804843F: sortiere (merge.c:36)
==285== by 0x80483B9: main (merge.c:20)
==285==
==285== Jump to the invalid address stated on the next line
==285== at 0x40BFFFEF: ???
==285== Address 0x40BFFFEF is not stack'd, malloc'd or free'd
==285==
==285== Invalid read of size 1
==285== at 0x40BFFFF1: ???
==285== Address 0x19 is not stack'd, malloc'd or free'd
==285==
==285== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==285== Address not mapped to object at address 0x19
==285== at 0x40BFFFF1: ???
==285==
==285== ERROR SUMMARY: 7 errors from 6 contexts (suppressed: 0 from 0)
==285== malloc/free: in use at exit: 0 bytes in 0 blocks.
==285== malloc/free: 0 allocs, 0 frees, 0 bytes allocated.
==285== For a detailed leak analysis, rerun with: --leak-check=yes
==285== For counts of detected errors, rerun with: -v
Der erste Fehler zeigt, dass in Zeile 70 Speicher benutzt wird, der nicht initialisert wurde. Mit dieser Information findet man schnell den Fehler in
folgendem Code:
Code: Select all
for (i = 0; i <= anzahl; i++)
printf("%c ", sort_array[i-1]);
Nachdem der Fehler korrigiert wurde erhalten wir von valgrind die folgende Ausgabe:
Code: Select all
==2864== Memcheck, a memory error detector for x86-linux.
==2864== Copyright (C) 2002-2003, and GNU GPL'd, by Julian Seward.
==2864== Using valgrind-2.1.0, a program supervision framework for x86-linux.
==2864== Copyright (C) 2000-2003, and GNU GPL'd, by Julian Seward.
==2864== Estimated CPU clock rate is 2815 MHz
==2864== For more details, rerun with: -v
==2864==
Unsortierter String!
==2864== Conditional jump or move depends on uninitialised value(s)
==2864== at 0x80484A2: mische (merge.c:49)
==2864== by 0x804845F: sortiere (merge.c:38)
==2864== by 0x804843F: sortiere (merge.c:36)
==2864== by 0x804843F: sortiere (merge.c:36)
==2864== by 0x804843F: sortiere (merge.c:36)
==2864== by 0x80483B9: main (merge.c:20)
==2864==
==2864== Jump to the invalid address stated on the next line
==2864== at 0x40BFFFEF: ???
==2864== Address 0x40BFFFEF is not stack'd, malloc'd or free'd
==2864==
==2864== Invalid read of size 1
==2864== at 0x40BFFFF1: ???
==2864== Address 0x19 is not stack'd, malloc'd or free'd
==2864==
==2864== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==2864== Address not mapped to object at address 0x19
==2864== at 0x40BFFFF1: ???
==2864==
==2864== ERROR SUMMARY: 4 errors from 3 contexts (suppressed: 0 from 0)
==2864== malloc/free: in use at exit: 0 bytes in 0 blocks.
==2864== malloc/free: 0 allocs, 0 frees, 0 bytes allocated.
==2864== For a detailed leak analysis, rerun with: --leak-check=yes
==2864== For counts of detected errors, rerun with: -v
Segmentation fault
Die Ausgabe läßt zunächst vermuten, dass in der folgenden Zeile nicht initialisierter Speicher benutzt wird:
Code: Select all
if (((i1 <= mitte) &&
Wenn man sich die Herkunft der beiden Variablen i1 und mitte anschaut, dann bemerkt man, dass diese auf jeden Fall initialisiert wurden. Dies zusammen mit der Tatsache, dass valgrind bei den nächsten Fehlermeldungen keinen Stacktrace mehr ausgeben kann, ist ein sicheres Indiz dafür, dass der Stack korrumpiert wurde.
Da dieses Programm auf einem Array herumfuchtelt, liegt es nahe anzunehmen, dass bei einer Arrayoperation auch der Stack überschrieben wurde. Deshalb müssen wir der Reihe nach die Arrays vom Stack auslagern. Am besten geht dies, indem wir sie auf dem Heap anlegen. Da valgrind alle Heapoperationen durch Pre- und Postfences schützt, kann es da Fehler leichter finden.
Das Programm benutzt zwei Arrays auf dem Stack - sort_array und hilfs_array. Da der Fehler laut valgrind in der Nähe von mische stattfindet, lagern wir zuerst das hilfs_array aus. So wird aus
Code: Select all
char hilfs_array[MAX_BUFFER+1];
ein
Code: Select all
char * hilfs_array = malloc(MAX_BUFFER+1);
Am Ende der Funktion fügen wir noch folgendes ein:
und includen den Header "malloc.h"
Ein erneuter valgrind Lauf ergibt:
Code: Select all
==2928== Memcheck, a memory error detector for x86-linux.
==2928== Copyright (C) 2002-2003, and GNU GPL'd, by Julian Seward.
==2928== Using valgrind-2.1.0, a program supervision framework for x86-linux.
==2928== Copyright (C) 2000-2003, and GNU GPL'd, by Julian Seward.
==2928== Estimated CPU clock rate is 2822 MHz
==2928== For more details, rerun with: -v
==2928==
Unsortierter String!
==2928== Invalid write of size 1
==2928== at 0x804854A: mische (merge.c:57)
==2928== by 0x80484BF: sortiere (merge.c:39)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x804849F: sortiere (merge.c:37)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x8048419: main (merge.c:21)
==2928== Address 0x4149D099 is 0 bytes after a block of size 5 alloc'd
==2928== at 0x40028BCE: malloc (vg_replace_malloc.c:160)
==2928== by 0x80484D3: mische (merge.c:45)
==2928== by 0x80484BF: sortiere (merge.c:39)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x804849F: sortiere (merge.c:37)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x8048419: main (merge.c:21)
==2928==
==2928== Invalid read of size 1
==2928== at 0x8048575: mische (merge.c:62)
==2928== by 0x80484BF: sortiere (merge.c:39)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x804849F: sortiere (merge.c:37)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x8048419: main (merge.c:21)
==2928== Address 0x4149D099 is 0 bytes after a block of size 5 alloc'd
==2928== at 0x40028BCE: malloc (vg_replace_malloc.c:160)
==2928== by 0x80484D3: mische (merge.c:45)
==2928== by 0x80484BF: sortiere (merge.c:39)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x804849F: sortiere (merge.c:37)
==2928== by 0x8048485: sortiere (merge.c:36)
==2928== by 0x8048485: sortiere (merge.c:36)
...
==2928== by 0x80484BF: sortiere (merge.c:39)
==2928== by 0x8048419: main (merge.c:21)
s e g f j p s e k f e p s s k a a 9 8 7 6 5 4
Nach Größe sortiert!
4 5 6 7 8 9 a a e e e f f g j k k p p s s s s
==2928==
==2928== ERROR SUMMARY: 199 errors from 24 contexts (suppressed: 0 from 0)
==2928== malloc/free: in use at exit: 0 bytes in 0 blocks.
==2928== malloc/free: 23 allocs, 23 frees, 115 bytes allocated.
==2928== For a detailed leak analysis, rerun with: --leak-check=yes
==2928== For counts of detected errors, rerun with: -v
In Zeile 57 wird also in verbotenen Speicher hinein geschrieben.
Code: Select all
hilfs_array[i] = sort_array[i2-1];
Der Zähler i läuft jedoch von anfang bis ende und wird in der Schleife nicht verändert. Entweder sind nun anfang, ende falsch oder hilfs_array hat nicht die richtige Größe. Von der Korrektheit von anfang und ende kann man sich durch printf Ausgaben überzeugen. Also muß hilfs_array die falsche Größe haben. Schauen wir uns die Definition an:
Code: Select all
char * hilfs_array = malloc(MAX_BUFFER+1);
und expandieren das Makro zu
Code: Select all
char * hilfs_array = malloc(sizeof(sort_array) / sizeof(char)+1);
Das geübte Auge sieht sofort den Fehler, aber die meisten würden sich nun MAX_BUFFER per printf ausgeben lassen.
Das Ergebnis ist 4, so dass hilfs_array nur fünf Elemente fasst. Den Rest dazu hat schon mcr erklärt.
Das ist ungefähr ein direkter Weg, um diesen Fehler zu finden. Zuletzt noch eine Anmerkung: sizeof(char) ist immer 1.