Hinweis: Das Forum wird geschlossen! Neue Registrierungen sind nicht mehr möglich!

 Zurück zu Pro-Linux   Foren-Übersicht   FAQ     Suchen    Mitgliederliste
Rekursion =>Stackoverflow??

 
Neuen Beitrag schreiben   Auf Beitrag antworten    Pro-Linux Foren-Übersicht -> Programmieren - C
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Null
Gast





BeitragVerfasst am: 08. Jul 2004 15:39   Titel: Rekursion =>Stackoverflow??

Hallo Forum,

warum verursacht der folgende Code einen Speicherzugriffsfehler auf meinem System?

Code:

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

void ausgabe (char *, int          );
void mische  (char *, int, int, int);
void sortiere(char *, int, int     );
/***********************************************************************/
int main()
{

   char sort_array[] = "segfjpsekfepsskaa987654";

  BIL;
  printf("\n\n\tUnsortierter String!\n");
  ausgabe(sort_array, MAX_BUFFER);

  sortiere(sort_array, 1, MAX_BUFFER);

  printf("\n\n\tNach Größe sortiert!\n");
  ausgabe(sort_array, MAX_BUFFER);
  printf("\n\n");
}
/***********************************************************************/
void sortiere(char sort_array[], int anfang, int ende)
{
    int mitte;

  if (anfang < ende)
  {
    mitte = (int)((anfang + ende) / 2);

    sortiere(sort_array, anfang, mitte);
    sortiere(sort_array, mitte+1, ende);

    mische(sort_array, anfang, mitte, ende);
  }
}
/***********************************************************************/
void mische(char sort_array[], int anfang, int mitte, int ende)
{
  char hilfs_array[MAX_BUFFER+1];
  int i, i1=anfang, i2 = mitte+1;

  for (i = anfang; i <= ende; i++)
  {
    if (((i1 <= mitte) &&
         (sort_array[i1-1] < sort_array[i2-1]) ||  (i2 > ende)) != 0) {

            hilfs_array[i] = sort_array[i1-1];
             i1++; }
   
    else {
            hilfs_array[i] = sort_array[i2-1];
             i2++; }
  }                       

  for (i = anfang; i <= ende; i++)
             sort_array[i-1] = hilfs_array[i];
}
/***********************************************************************/
void ausgabe(char sort_array[], int anzahl)
{
  int i;

  printf("\n\n\t");
  for (i = 0; i <= anzahl; i++)
    printf("%c  ", sort_array[i-1]);
}
/***********************************************************************/


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
Gast





BeitragVerfasst am: 08. Jul 2004 16:24   Titel:

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:

for (i = 0; i <= anzahl; i++)

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

Null
Gast





BeitragVerfasst am: 08. Jul 2004 16:58   Titel:

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

Code:
 
      for(i = 0; i <= anzahl; i++)
             printf("%c ", sort_array[i-1];
   


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
Gast





BeitragVerfasst am: 09. Jul 2004 8:11   Titel:

hier einige Ausgaben bezüglich der aktuellen Aufrufparameter:

Unsortierter String!


╠ 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
Gast





BeitragVerfasst am: 09. Jul 2004 10:35   Titel:

> 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[i];
 

Null
Gast





BeitragVerfasst am: 09. Jul 2004 17:31   Titel:

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
Gast





BeitragVerfasst am: 09. Jul 2004 19:06   Titel:

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
Gast





BeitragVerfasst am: 14. Jul 2004 15:51   Titel:

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
Gast





BeitragVerfasst am: 14. Jul 2004 16:43   Titel:

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:

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:
valgrind --tool=memcheck --num-callers=32 ./a.out


Das Ergebnis ist:

Code:

==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:

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:

==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:
    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:
char hilfs_array[MAX_BUFFER+1];

ein
Code:
char * hilfs_array = malloc(MAX_BUFFER+1);

Am Ende der Funktion fügen wir noch folgendes ein:
Code:
free(hilfs_array);

und includen den Header "malloc.h"

Ein erneuter valgrind Lauf ergibt:
Code:

==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:
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:
char * hilfs_array = malloc(MAX_BUFFER+1);


und expandieren das Makro zu

Code:
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
Gast





BeitragVerfasst am: 14. Jul 2004 18:53   Titel:

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

PS: posting des monats?
 

heinrich



Anmeldungsdatum: 22.09.1999
Beiträge: 219
Wohnort: N49.137 E8.544

BeitragVerfasst am: 20. Aug 2004 1:09   Titel:

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.
_________________
It just works.
 
Benutzer-Profile anzeigen Private Nachricht senden AIM-Name

Beiträge vom vorherigen Thema anzeigen:   
     Pro-Linux Foren-Übersicht -> Programmieren - C Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehen Sie zu:  

Powered by phpBB © phpBB Group
pro_linux Theme © 2004 by Mandaxy