Rekursion =>Stackoverflow??

[Null]

Hallo Forum,

warum verursacht der folgende Code einen Speicherzugriffsfehler auf meinem System?

Code: Select all

/***********************************************************************/
                                 Mergesort                                        
/***********************************************************************/
#include <stdio.h>
#include <time.h>
#define BIL system&#40;"clear"&#41;;
#define MAX_BUFFER &#40;sizeof&#40;sort_array&#41; / sizeof&#40;char&#41;&#41;

void ausgabe &#40;char *, int          &#41;;
void mische  &#40;char *, int, int, int&#41;;
void sortiere&#40;char *, int, int     &#41;;
/***********************************************************************/
int main&#40;&#41;
&#123;

   char sort_array&#91;&#93; = "segfjpsekfepsskaa987654";

  BIL;
  printf&#40;"\n\n\tUnsortierter String!\n"&#41;;
  ausgabe&#40;sort_array, MAX_BUFFER&#41;;

  sortiere&#40;sort_array, 1, MAX_BUFFER&#41;;

  printf&#40;"\n\n\tNach Größe sortiert!\n"&#41;;
  ausgabe&#40;sort_array, MAX_BUFFER&#41;;
  printf&#40;"\n\n"&#41;;
&#125;
/***********************************************************************/
void sortiere&#40;char sort_array&#91;&#93;, int anfang, int ende&#41;
&#123;
    int mitte;

  if &#40;anfang < ende&#41; 
  &#123;
    mitte = &#40;int&#41;&#40;&#40;anfang + ende&#41; / 2&#41;; 

    sortiere&#40;sort_array, anfang, mitte&#41;;
    sortiere&#40;sort_array, mitte+1, ende&#41;;

    mische&#40;sort_array, anfang, mitte, ende&#41;;
  &#125;
&#125;
/***********************************************************************/
void mische&#40;char sort_array&#91;&#93;, int anfang, int mitte, int ende&#41;
&#123;
  char hilfs_array&#91;MAX_BUFFER+1&#93;; 
  int i, i1=anfang, i2 = mitte+1;

  for &#40;i = anfang; i <= ende; i++&#41;
  &#123; 
    if &#40;&#40;&#40;i1 <= mitte&#41; &&
         &#40;sort_array&#91;i1-1&#93; < sort_array&#91;i2-1&#93;&#41; ||  &#40;i2 > ende&#41;&#41; != 0&#41; &#123;

            hilfs_array&#91;i&#93; = sort_array&#91;i1-1&#93;; 
             i1++; &#125;
    
    else &#123;
     	    hilfs_array&#91;i&#93; = sort_array&#91;i2-1&#93;; 
             i2++; &#125;
  &#125;                       

  for &#40;i = anfang; i <= ende; i++&#41; 
             sort_array&#91;i-1&#93; = hilfs_array&#91;i&#93;;
&#125;
/***********************************************************************/
void ausgabe&#40;char sort_array&#91;&#93;, int anzahl&#41; 
&#123;
  int i;

  printf&#40;"\n\n\t"&#41;;
  for &#40;i = 0; i <= anzahl; i++&#41;
	 printf&#40;"%c  ", sort_array&#91;i-1&#93;&#41;;
&#125;
/***********************************************************************/

Kürze ich jedoch den Vektor mit dem String um nur ein Element funktioniert das Programm
wie geplant. Wo liegt der Fehler???

MfG!

[c-progger]

du hättest ja mal debuggen können und die zeile angeben können wo der fehler passiert.
aber ich denke ich weiß wo der fehler liegt:

Code: Select all

for &#40;i = 0; i <= anzahl; i++&#41;

schaus dir nochmal an! ersetzte 'i <= anzahl' durch 'i < anzahl' sonst zählt er einen über den array hinaus; daher dann der speicherzugriffsfehler.

[Null]

Danke für die schnelle Antwort, aber beachte den Schleifenkörper....

Code: Select all

 
      for&#40;i = 0; i <= anzahl; i++&#41;
             printf&#40;"%c ", sort_array&#91;i-1&#93;;
   

Der Array-Index wird vor der Ausgabe um eins vermindert!
Ich weiß, schlecht lesbarer Code.., sorry!
Das Problem muß in der Rekursion selber liegen...vielleicht zu viele Funktionsaufrufe?

[Tom2]

hier einige Ausgaben bezüglich der aktuellen Aufrufparameter:

Unsortierter String!


&#9568; s e g f j p s e k f e p s s k a a 9 8 7 6 5 4
SORTIERE! a: 1 m:12 e:24
SORTIERE! a: 1 m:6 e:12
SORTIERE! a: 1 m:3 e:6
SORTIERE! a: 1 m:2 e:3
SORTIERE! a: 1 m:1 e:2
MISCHE! a: 1 m:1 e:2
MISCHE! a: 1 m:2 e:3
SORTIERE! a: 4 m:5 e:6
SORTIERE! a: 4 m:4 e:5
MISCHE! a: 4 m:4 e:5
MISCHE! a: 4 m:5 e:6
MISCHE! a: 1 m:3 e:6
SORTIERE! a: 7 m:9 e:12
SORTIERE! a: 7 m:8 e:9
SORTIERE! a: 7 m:7 e:8
MISCHE! a: 7 m:7 e:8

-----------------------------------
Das hilfs_array im letzten MISCHE-Aufruf wird mit 5 !!! Elementen angelegt, aber die Laufvariable i, mit der Du darauf zugreifst, geht von anfang=7 bis ende=8. Am einfachsten ist es, Du legst einen genügend grossen hilfs_array an.

Gruss
Tom2

[kanonenfutter]

> for(i = 0; i <= anzahl; i++)
> printf("%c ", sort_array[i-1];
> Der Array-Index wird vor der Ausgabe um eins vermindert!

und was soll das bringen, bzw was erwartest du für den fall i==0? richtig, dann wird auf das element sort_array[-1] zugegriffen!
also entweder for (i=1; ) .... array[i-1] oder besser in C-üblicher schreibweise: for(i = 0; i < anzahl; i++) ....... sort_array;

[Null]

Hab's verstanden, danke Tom2!

@kanonenfutter:

Keine Ahnung was das bringen soll, ist nicht mein Programm!
Aber Prinzipell geb ich Dir vollkommen Recht, dass das den Code unötig "schwerfällig"
zu lesen und vorrallem fehleranfällig macht!
Mir ging es lediglich um die Speicherschutzverletzung!

MfG!

[Tom2]

kanonenfutter hat völlig Recht. Wenn Du mit dem Index -1 auf Dein array zugreifst, bekommst Du nur falsche Werte zurück, weil arrays in C von 0 bis MAX angelegt werden.

Tom2

[mcr]

Hallo zusammen,

das Problem liegt in den "bösen" Macros.
#define MAX_BUFFER (sizeof(sort_array) / sizeof(char))

Betrachten wir mal den Wert MAX_BUFFER in der Funktion mische.
sizeof(sort_array) ist hier gleich 4 (Plattform abhängig), da an dieser Stelle
sort_array nur ein Pointer ist.
Somit erhälst du ziemlich bald einen Segmentation fault.

Richtiger wäre:
#define MAX_BUFFER 100


int main()
{

char sort_array[] = "segfjpsekfepsskaa987654";

printf("\n\n\tUnsortierter String!\n");
ausgabe(sort_array, sizeof(sort_array)-1);

printf("\n\n\tausgegeben...!\n");
sortiere(sort_array, 1, sizeof(sort_array)-1);

printf("\n\n\tNach Größe sortiert!\n");
ausgabe(sort_array, sizeof(sort_array)-1);
printf("\n\n");
}

Information zu Macros wie das obige:
Der Compiler ersetzt beim kompilieren den String MAX_BUFFER
durch den angebenen Wert (sizeof(sort_array) / sizeof(char))
und wertet den später aus.


char sort_array[] = "123";
sizeof(sort_array) ist nun 4 und nicht 3, da der String mit \0 terminiert ist.



Gruss mcr

[Ponto]

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 &#40;i = 0; i <= anzahl; i++&#41;
    printf&#40;"%c  ", sort_array&#91;i-1&#93;&#41;;

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 &#40;&#40;&#40;i1 <= mitte&#41; && 

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:

Code: Select all

free(hilfs_array);

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.

[kanonenfutter]

@Ponto: wow, genialer "walk-through".

PS: posting des monats?

[heinrich]

zu den Postings von mcr und Ponto ist nur noch anzufügen, dass man

a) auf dem Stack lediglich kleinere Objekte ablegen sollte.
Grössere Objekte und Arrays sollte man auf den Heap packen. Spätestens wenn man Programme von x86 auf nicht-x86 portiert wird man ansonsten eventuell auf Probleme treffen, weil dort eventuell auf dem Stack weniger Platz ist.

b) Rekursion ohne bekannte Rekursionstiefe ist ein dickes rotes DON'T
Wenn man nicht im Vorraus bestimmen kann, wie tief eine Rekursion wird kann es sehr leicht passieren dass einem zur Laufzeit der Stack nicht mehr ausreicht.