# [OT] caccia all'Heisenbug: stack size limitato [RISOLTO]

## CRV§ADER//KY

Sto uscendo cretino. Ho scritto un programma per il politecnico (che devo consegnare entro lunedì e da cui dipende la valutazione di un esame da 10 crediti). In linea di massima funziona ma.... è affetto da un maledetto Heisenbug, ossia un bug che, ogni volta che lo lancio, date le stesse idendiche condizioni iniziali, lo manda in segfault in un punto diverso.

Questo l'output di ddd (notare position, che cambia ogni santissima volta e indica la posizione in un array)

```
Program received signal SIGSEGV, Segmentation fault.

0x08049102 in flag_set (f=0x821f008, position=262237, value=1) at flags.c:73

(gdb) run

Program received signal SIGSEGV, Segmentation fault.

0x08049102 in flag_set (f=0x821f008, position=262234, value=1) at flags.c:73

(gdb) run

Program received signal SIGSEGV, Segmentation fault.

0x08049102 in flag_set (f=0x821f008, position=261958, value=1) at flags.c:73

(gdb) run

Program received signal SIGSEGV, Segmentation fault.

0x08049102 in flag_set (f=0x821f008, position=262307, value=1) at flags.c:73
```

La cosa divertente è che crasha in un punto completamente casuale (subito dopo o subito prima l'entrata di una funzione) e dopo un numero di ricursioni completamente casuale. Ogni tanto invece funziona. Ogni tanto.

Quel che è peggio è che, se lo faccio girare sotto valgrind, FUNZIONA. -_-

Che diavolo può essere? So che è quasi sicuramente colpa di RAM che ho "sporcato" inavvertitamente, ma non ho la più pallida idea di DOVE l'ho sporcata. Esistono dei tools che facciano al caso mio?

Allego il programma, nel caso in cui qualcuno avesse la serata libera  :Very Happy: 

si compila con "make all" e si lancia con

echo "0 0" | ./bitmap

output desiderato:

```
Colore del pixel (0, 0): 1

Numero totale di pixel di colore 1: 480000

Calcolo numero di pixel connessi...

Trovo il percorso più lungo...

Lunghezza del tratto continuo più lungo: 480000
```

Ovviamente è altamente probabile che, cambiando versione di glibc/gcc, il bug svanisca o si presenti sotto aspetti ancora più inquietanti...  :Twisted Evil: 

http://www.crusaderky.altervista.org/_altervista_ht/bitmap.tar.gz

(copia il link nella barra dell'URL per aggirare le protezioni referer di altervista)

----------

## CRV§ADER//KY

Così funziona:

```
echo "0 0" | valgrind --tool=none ./bitmap
```

Così no:

```
echo "0 0" | ./bitmap
```

Inutile dire che valgrind --tool=memcheck non rileva niente. E' qualcosa che sporca lo stack... ma io NON HO array o puntatori in stack!!!

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAARGH

----------

## comio

oltre al conforto... non so cosa posso darti...

Probabilmente scrivi su memoria non allocata... e quando esci fuori dalla paginetta hai il seg fault.

ciao

----------

## CRV§ADER//KY

 *comio wrote:*   

> Probabilmente scrivi su memoria non allocata... e quando esci fuori dalla paginetta hai il seg fault.

 

Sì ma il problema è che il programma non va in segfault quando faccio l'accesso non autorizzato, ma DOPO!

Mi stupirei se non esistesse nessuna utility che faccia crashare il programma al momento giusto....

----------

## oRDeX

scusa se intervengo in modo brusco perchè ddd non lo conosco bene.

ma 

```
at flags.c:73
```

 non indica dove il programma va in errore?

----------

## comio

 *CRV§ADER//KY wrote:*   

>  *comio wrote:*   Probabilmente scrivi su memoria non allocata... e quando esci fuori dalla paginetta hai il seg fault. 
> 
> Sì ma il problema è che il programma non va in segfault quando faccio l'accesso non autorizzato, ma DOPO!
> 
> Mi stupirei se non esistesse nessuna utility che faccia crashare il programma al momento giusto....

 

esempio di scenario che porta a crash...

alloco della memoria... quindi la dealloco... ma la pagina rimane sempre allocata al programma. Non alloco ma uso un puntatore... che per pura fortuna punta a memoria non allocata, ma comunque in una pagina allocata dal SO.

ciao

----------

## CRV§ADER//KY

 *oRDeX wrote:*   

> scusa se intervengo in modo brusco perchè ddd non lo conosco bene.
> 
> ma 
> 
> ```
> ...

 

sì. è la prima istruzione della funzione (che non lavora sull'heap né altra roba strana). Altre volte crasha sull'istruzione che _chiama_ quella funzione.

----------

## Danilo

State studiando le bitmap o la ricorsione ?   :Wink: 

ho provato a modificare la funzione cosi'

```

//calcola il numero di pixel connessi (raggiungibili) e salva il risultato in connected

void rconnect(int r0, int c0)

{

//---- Aggiunte Danilo

   static long myStack =0;

   static long myEntrate =0;

   myStack ++;

   myEntrate++;

   printf(" myEntrate[%d] - myStack [%d] \n" , myEntrate, myStack);

//---- Fine aggiunte Danilo

   

   flag_set(fconnected, r0*XRES+c0, TRUE);

   connected++;

   int r,c;

   for (r = r0-1; r < r0+2; r++)

   {

      for (c = c0-1; c < c0+2; c++)

      {

         if (

            c>=0 && r>=0                           //entro i limiti inferiori

            && c<XRES && r<YRES                      //entro i limiti superiori

            && !(r==r0 && c==c0)                     //non è lo stesso pixel

            && bitmap[r][c].color == bitmap[r0][c0].color   //compatibile (stesso colore)

            && !flag_get(fconnected, r*XRES+c)            //non è già compresa nel percorso attuale

         )

         {

            rconnect(r,c);

         }

      }

   }

//---- Aggiunte Danilo

   myStack --;

//---- Fine aggiunte Danilo

}

```

e poi l'ho lanciato e testato l'output

```

danilo@mymachine ~/tmp/lll/esame $ echo "0 0" |./bitmap >1.tmp

Calcolo numero di pixel connessi...

Segmentation fault

danilo@mymachine ~/tmp/lll/esame $ cat 1.tmp |wc -l

261645

danilo@mymachine ~/tmp/lll/esame $ tail -f 1.tmp

 myEntrate[261635] - myStack [261635]

 myEntrate[261636] - myStack [261636]

 myEntrate[261637] - myStack [261637]

 myEntrate[261638] - myStack [261638]

 myEntrate[261639] - myStack [261639]

 myEntrate[261640] - myStack [261640]

 myEntrate[261641] - myStack [261641]

 myEntrate[261642] - myStack [261642]

 myEntrate[261643] - myStack [261643]

 myEntrate[2616

```

Uso raramente la ricorsione ma uno stack cosi' lungo non l'avevo mai creato.

Io per prima cosa proverei a trasformarla in iterativa...

----------

## btbbass

 *CRV§ADER//KY wrote:*   

> Così funziona:
> 
> ```
> echo "0 0" | valgrind --tool=none ./bitmap
> ```
> ...

 

Ma dai!!!

Allora abbiamo fatto l'esame insieme!! io mi ci devo ancora mettere...vabbe...

Senti, se hai la possibilità, prova a compilarlo anche in winzoz... 

So che può essere un'idiozia, ma mi succedeva la stessa cosa con un programma fatto sempre per APA (l'esercitazione 4 di laboratorio...) ; ci ho perso dei giorni interi perchè nn mi scriveva correttamente alcuni nomi delle città... ho provato in win e funziona! dipende cmq (almeno per me) da alcune aree di ram che nn pulisce, anche se allocate con calloc!!!

Boh, fai un tentativo, poi fammi sapere!

----------

## emix

 *Danilo wrote:*   

> Uso raramente la ricorsione ma uno stack cosi' lungo non l'avevo mai creato.
> 
> Io per prima cosa proverei a trasformarla in iterativa...

 

Pensavo più o meno la stessa cosa...

----------

## Danilo

Ho provato anche a 

```

danilo@mymachine ~/tmp/lll/esame $ cat   main.cpp

#include <stdio.h>

void ricor()

{

        static long stack=0;

        stack++;

        printf("%d\n", stack);

        ricor();

}

int main()

{

        ricor();

        return 0;

}

```

compilatore g++

```
danilo@mymachine ~/tmp/lll/esame $ g++  main.cpp

danilo@mymachine ~/tmp/lll/esame $ ./a.out >1.tmp

Segmentation fault

danilo@mymachine ~/tmp/lll/esame $ tail 1.tmp

523768

523769

523770

523771

523772

523773

523774

523775

523776

```

L'errore non cambia.

Stavolta usa il doppio delle chiamate ma in compenso NON ha variabili da conservarsi...

----------

## CRV§ADER//KY

 *Danilo wrote:*   

> State studiando le bitmap o la ricorsione ?  

 

la ricorsione  :Wink: 

 *Quote:*   

> Uso raramente la ricorsione ma uno stack cosi' lungo non l'avevo mai creato.
> 
> Io per prima cosa proverei a trasformarla in iterativa...

 

 *Quote:*   

> Ho provato anche a [CUT]

 

dovrei avere DUE GIGA di stack.....  :Shocked:  com'è possibile che crashi dopo appena mezzo milione di ricorsioni? 

e soprattutto, com'è possibile che la RAM rimanga assolutamente intatta? (ho ~250Mb di RAM libera più 1.5Gb di swap. lo swap non viene neanche toccato).

btbbass: è piccolo il mondo  :Very Happy: 

con che prof l'hai dato?

Sì, ci ho già pensato e ho provato sotto windows (MinGW/GCC), ma non cambia niente.

----------

## CRV§ADER//KY

Ho provato il tuo programma: con -O1 crasha, mentre con -O2 va avanti all'infinito!!!!! (io l'ho killato che era a 56 milioni e rotti...)

Ora resta solo da capire quale delle seguenti ottimizzazioni risolve il problema.....

-fforce-mem -foptimize-sibling-calls -fstrength-reduce -fcse-follow-jumps  -fcse-skip-blocks -frerun-cse-after-loop  -frerun-loop-opt -fgcse -fgcse-lm -fgcse-sm -fdelete-null-pointer-checks -fexpensive-optimizations -fregmove -fschedule-insns  -fschedule-insns2 -fsched-interblock -fsched-spec -fcaller-saves -fpeephole2 -freorder-blocks -freorder-functions -fstrict-aliasing -falign-functions  -falign-jumps -falign-loops -falign-labels

[EDIT]è -foptimize-sibling-calls. da man gcc: *Quote:*   

>  -foptimize-sibling-calls
> 
>            Optimize sibling and tail recursive calls.
> 
>            Enabled at levels -O2, -O3, -Os.

 

Ora c'è un "piccolo" problema..... il mio programma originario crasha lo stesso!!!

----------

## Danilo

 *CRV§ADER//KY wrote:*   

> 
> 
> Ora c'è un "piccolo" problema..... il mio programma originario crasha lo stesso!!!

 

Io proverei lo stesso a far divenire la funzione interativa e a vedere dove scoppia.

Potrebbe essere un bug del compilatore.

IMHO non credo che ci siano  molti programmi con stack di quelle dimensioni

----------

## CRV§ADER//KY

 *Danilo wrote:*   

> Io proverei lo stesso a far divenire la funzione interativa e a vedere dove scoppia.

 

Impossibilie AFAIK. rconnect() determina tutti i pixel adiacenti dello stesso colore, quindi potrei convertirla in una visita in ampiezza (ora è in profondità) e farla diventare iterativa.

rsolve() invece è una visita in profondità di un grafo e deve rimanere tale... non vedo come potrei farla divenire iterativa.

 *Quote:*   

> Potrebbe essere un bug del compilatore.

 

Lo trovo altamente probabile. Mi è stato riferito che accade anche con gcc 3.4/glibc 2.3.5.

Qualcuno con gcc 4.0 può provare?

 *Quote:*   

> IMHO non credo che ci siano  molti programmi con stack di quelle dimensioni

 

Alcuni programmi scientifici superano tranquillamente i 2Gb.

----------

## Danilo

 *CRV§ADER//KY wrote:*   

> rconnect() determina tutti i pixel adiacenti dello stesso colore, quindi potrei convertirla in una visita in ampiezza (ora è in profondità) e farla diventare iterativa.
> 
> 

 

Sono da salvare 6-7 variabili (anche in una lista di puntatori va bene) per chiamata a funzione. 

Come avresti fatto se il c non avesse permesso la ricorsione?

Chi diceva che qualunque ricorsione si puo' trasformare in iterazione?

A me va in dump sempre in rconnect, all'entrata o prima della chiamata stessa.

Prova ad eliminare qualcosa che tu non controlli direttamente (lo stacche) e vedi dove cora...

----------

## CRV§ADER//KY

 *Danilo wrote:*   

> Come avresti fatto se il c non avesse permesso la ricorsione?

 

Probabilmente avrei cambiato linguaggio  :Very Happy: 

Scherzi a parte, FORSE è fattibile con una lista dinamica di proporzioni colossali, che rallenta il programma a 1/10 delle sue prestazioni originarie... dubito di aver voglia di implementarla anche perché significherebbe stravolgere l'algoritmo originario, cosa non positiva per il voto.

----------

## Danilo

 *CRV§ADER//KY wrote:*   

>  *Danilo wrote:*   Come avresti fatto se il c non avesse permesso la ricorsione? 
> 
> Probabilmente avrei cambiato linguaggio 
> 
> Scherzi a parte, FORSE è fattibile con una lista dinamica di proporzioni colossali, che rallenta il programma a 1/10 delle sue prestazioni originarie... dubito di aver voglia di implementarla anche perché significherebbe stravolgere l'algoritmo originario, cosa non positiva per il voto.

 

Lista di puntatori (forse ne serve una doppiamente linkata), niente di che': solo che tu controlli l'allocazione/deallocazione.

Una lista LIFO per capirci.

E poi in che senso rallenta il programma? solo per delle new e delle copie di interi?

E cosa credi che debba fare una chiamata ricorsiva?

Ora hai tempo per trovare il baco domenica pomeriggio no.  :Wink: 

Ciao

----------

## btbbass

 *CRV§ADER//KY wrote:*   

> 
> 
> btbbass: è piccolo il mondo 
> 
> con che prof l'hai dato?

 

L'ho dato con camurati/squillero (aula 12...)

----------

## comio

 *btbbass wrote:*   

>  *CRV§ADER//KY wrote:*   
> 
> btbbass: è piccolo il mondo 
> 
> con che prof l'hai dato? 
> ...

 

una volta ero il borsista di quel corso (quando era vecchio ordinamento)  :Smile:  magari esistono ancora le dispense fatte da me... ma con il nuovo ordinamento erano un po' OT come dispense...

ciao

----------

## federico

Ho un amico al poli di torino che è il miglior programmatore C che io conosca ^_^ (alessandro, sideralis) provo a mandargli una mail girando il problema (si sa mai)

----------

## CRV§ADER//KY

Sempre più criptico... ho scritto una variante del programma di Danilo:

stackcrack2.c

```
#include <stdio.h>

void recurse(int stack)

{

   stack++;

   printf("%8x %d\n", (unsigned int)&stack, stack);

   recurse(stack);

}

int main()

{

   recurse(0);

   return 0;

}
```

```
$ ./stackcrack2 > log.txt

Segmentation fault

crusader@eva ~/data/documents/poli/apa/esame/stackcrack $ tail log.txt

bf5050a0 260888

bf505080 260889

bf505060 260890

bf505040 260891

bf505020 260892

bf505000 260893

bf504fe0 260894

bf504fc0 260895

bf504fa0 260896
```

Appare evidente che:

1)ogni livello di stack richiede 32 bytes di RAM

2)il programma crasha dopo (260.869 * 32 / 2^20) = 8Mb scarsi di stack, mentre l'OS ne dovrebbe supportare 2Gb

Occorre inoltre notare che -foptimize-sibling-calls non sortisce più alcun effetto.

Con valgrind le cose migliorano leggermente, ma non vengono risolte:

```
$ valgrind --tool=none ./stackcrack2 > log.txt

==26517== Nulgrind, a binary JIT-compiler for x86-linux.

==26517== Copyright (C) 2002-2004, and GNU GPL'd, by Nicholas Nethercote.

==26517== Using valgrind-2.4.0, a program supervision framework for x86-linux.

==26517== Copyright (C) 2000-2005, and GNU GPL'd, by Julian Seward et al.

==26517== For more details, rerun with: -v

==26517==

Segmentation fault

crusader@eva ~/data/documents/poli/apa/esame/stackcrack $ tail log.txt

ad269270 1460882

ad269250 1460883

ad269230 1460884

ad269210 1460885

ad2691f0 1460886

ad2691d0 1460887

ad2691b0 1460888

ad269190 1460889

ad269170 1460890

```

1.460.890 * 32 / (2^20) = 44.5 Mb

Qualcuno che abbia linux-2.4, mm-sources, etc. può provare a vedere cosa succede? Si prega di postare:

1)OS, con versione ed eventuali patch del kernel (-gentoo, -mm, etc.)

2)versione di libc

3)versione di gcc

Sarebbe anche interessante vedere cosa succede con compilatori Intel, Borland e Microsoft sotto windows. Purtroppo non li ho sottomano.

----------

## yardbird

Io ho provato il programma nel post appena sopra con gcc 4.1.0-beta. Trovo una corrispondenza diretta fra lo stack size e la "quota" a cui appare il segfault. Esempio:

```
plan3 yardbird # ulimit -s 2000

plan3 yardbird # ./recur |tail

bfe0c9a0 63810

bfe0c980 63811

bfe0c960 63812

bfe0c940 63813

bfe0c920 63814

bfe0c900 63815

bfe0c8e0 63816

bfe0c8c0 63817

bfe0c8a0 63818

plan3 yardbird # ulimit -s 4000

plan3 yardbird # ./recur |tail

bfc18ee0 127768

bfc18ec0 127769

bfc18ea0 127770

bfc18e80 127771

bfc18e60 127772

bfc18e40 127773

bfc18e20 127774

bfc18e00 127775

bfc18de0 127776

plan3 yardbird # ulimit -s 8000

plan3 yardbird # ./recur |tail

bf830ee0 255768

bf830ec0 255769

bf830ea0 255770

bf830e80 255771

bf830e60 255772

bf830e40 255773

bf830e20 255774

bf830e00 255775

bf830de0 255776

plan3 yardbird # ulimit -s 16000

plan3 yardbird # ./recur |tail

bf060ee0 511768

bf060ec0 511769

bf060ea0 511770

bf060e80 511771

bf060e60 511772

bf060e40 511773

bf060e20 511774

bf060e00 511775

bf060de0 511776

plan3 yardbird #     

```

Mi sembra abbastanza coerente come cosa, no?

----------

## CRV§ADER//KY

 :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked:   :Shocked: 

Non conoscevo assolutamente ulimit...........

FUNZIONAAAAAAAAAAAAAAAAA!

Come avevo detto in IRC l'altro giorno....

 *Quote:*   

> crusaderky: venererò come un DIO chiunque riesca a venire a capo di questo problema

 

yardbird, che giorno è la tua festa? Come devono essere celebrati i tuoi riti?

Vuoi dei sacrifici? vitelli, polli, giovani vergini?

*si prostra ai piedi di yardbird, accende delle candele e comincia a intonare delle nenie*

----------

## yardbird

 *CRV§ADER//KY wrote:*   

>                
> 
> Non conoscevo assolutamente ulimit...........
> 
> 

 

Eh, neanche io tempo fa... avevo avuto un problema simile scrivendo un software multi-thread, e avevo chiesto anch'io aiuto sui forum. Una buon'anima è venuta in mio soccorso svelandomi l'arcano  :Wink:  Lieto di essere stato d'aiuto.

 *CRV§ADER//KY wrote:*   

> Come avevo detto in IRC l'altro giorno....
> 
>  *Quote:*   crusaderky: venererò come un DIO chiunque riesca a venire a capo di questo problema 
> 
> yardbird, che giorno è la tua festa? Come devono essere celebrati i tuoi riti?
> ...

 

 :Laughing: 

Guarda, lascia stare i polli e i vitelli, mi accontento delle giovani vergini  :Twisted Evil: 

----------

