[solved] weird segfault [--> stack overflow]

[big_M]

Hey. I need some help here. I have a pair of procedures which recursively process a map. This runs fine until it suddenly throws a segmentation fault.

The procedures look like this:

Code: Pascal  [Select][+][-]

1. procedure FillFloodMaps_Crawler(x,y,dist:integer; fillHeight:single); forward;
2.  
3. procedure FillFloodMaps(x,y,dist:integer; fillHeight:single);
4. var DEM_Height, DEM_NoDataValue:single;
5. begin
6.   if FlowMap[x,y] >= dist then
7.     if FloodHeightMap[x,y] < fillHeight then
8.     begin
9.       //DEM_Height:=0;
10.       //writeLn(floattostr(DEM_Height));        {--> segfaults when uncommented}
11.       DEM.GetPixel(x,y,single(DEM_Height));  {--> segfaults}
12.       //writeLn(floattostr(DEM_Height));
13.       DEM.GetNoDataValue(single(DEM_NoDataValue));
14.       if (DEM_Height<>DEM_NoDataValue) AND (DEM_Height<fillHeight) then
15.       begin
16.         FloodHeightMap[x,y]:=fillHeight;
17.         FloodDepthMap[x,y]:=fillHeight-DEM_Height;
18.         FillFloodMaps_Crawler(x,y,dist,fillHeight);
19.       end;
20.     end;
21. end;
22.  
23. procedure FillFloodMaps_Crawler(x,y,dist:integer; fillHeight:single);
24. begin
25.   if (x+1<=Flood.Width-1)                           then FillFloodMaps(x+1,y,  dist,fillHeight);
26.   if (x+1<=Flood.Width-1) AND (y+1<=Flood.Height-1) then FillFloodMaps(x+1,y+1,dist,fillHeight);
27.   if                          (y+1<=Flood.Height-1) then FillFloodMaps(x,y+1,  dist,fillHeight);
28.   if (x-1>=0)             AND (y+1<=Flood.Height-1) then FillFloodMaps(x-1,y+1,dist,fillHeight);
29.   if (x-1>=0)                                       then FillFloodMaps(x-1,y,  dist,fillHeight);
30.   if (x-1>=0)             AND (y-1>=0)              then FillFloodMaps(x-1,y-1,dist,fillHeight);
31.   if                          (y-1>=0)              then FillFloodMaps(x,y-1,  dist,fillHeight);
32.   if (x+1<=Flood.Width-1) AND (y-1>=0)              then FillFloodMaps(x+1,y-1,dist,fillHeight);
33. end;        

Part of UEnvi.pas which contains the .GetPixel procedure:

Code: Pascal  [Select][+][-]

1. procedure TEnviMap.GetPixel(x,y:integer; var value:Single);
2. begin
3.   try
4.     value:=FMap_Single[x,y]
5.   except
6.     WriteLn('Access violation #4');
7.     value:=0;
8.     abort:=true;
9.   end;
10. end;    

FillFloodMaps gets called with x and y as coordinates, and this runs FillFloodMaps_Crawler to go recursively over a portion of the map. At some point though, the variable DEM_Height in FillFloodMaps can for whatever reason not be read anymore. If I run the code like written here, I get this from the gdb:

#0  0x000000000044d74c in GETPIXEL (this=0x0, X=0, Y=0, VALUE=<error reading variable: Cannot access memory at address 0x0>) at uenvi.pas:143
#1  0x0000000000450439 in FILLFLOODMAPS (X=9692, Y=5171, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:60
#2  0x000000000045063c in FILLFLOODMAPS_CRAWLER (X=9693, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:79
#3  0x00000000004504ba in FILLFLOODMAPS (X=9693, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:67
#4  0x000000000045050d in FILLFLOODMAPS_CRAWLER (X=9692, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:74
#5  0x00000000004504ba in FILLFLOODMAPS (X=9692, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:67
#6  0x000000000045050d in FILLFLOODMAPS_CRAWLER (X=9691, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:74
#7  0x00000000004504ba in FILLFLOODMAPS (X=9691, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:67
#8  0x000000000045050d in FILLFLOODMAPS_CRAWLER (X=9690, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:74
#9  0x00000000004504ba in FILLFLOODMAPS (X=9690, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:67
#10 0x000000000045050d in FILLFLOODMAPS_CRAWLER (X=9689, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:74
#11 0x00000000004504ba in FILLFLOODMAPS (X=9689, Y=5172, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:67
#12 0x000000000045063c in FILLFLOODMAPS_CRAWLER (X=9690, Y=5173, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:79
#13 0x00000000004504ba in FILLFLOODMAPS (X=9690, Y=5173, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:67
#14 0x000000000045050d in FILLFLOODMAPS_CRAWLER (X=9689, Y=5173, DIST=2007, FILLHEIGHT=262.304565) at ufunctions.pas:74
...

If try to read out the variable ( writeLn(floattostr(DEM_Height)) ), it crashes also with this from gdb:

Program received signal SIGSEGV, Segmentation fault.
0x000000000040710c in SYSTEM$_$STR_REAL$SMALLINT$SMALLINT$EXTENDED$TREAL_TYPE$OPENSTRING_$$_RETURN_EXPONENTIAL$crcC3D7D0D1 ()
(gdb) bt
#0  0x000000000040710c in SYSTEM$_$STR_REAL$SMALLINT$SMALLINT$EXTENDED$TREAL_TYPE$OPENSTRING_$$_RETURN_EXPONENTIAL$crcC3D7D0D1 ()
#1  0x00000000004066ba in SYSTEM_$$_STR_REAL$SMALLINT$SMALLINT$EXTENDED$TREAL_TYPE$OPENSTRING ()
#2  0x000000000040b804 in fpc_ansistr_float ()
#3  0x000000000046687d in SYSUTILS_$$_FLOATTOSTRFINTL$crc9799277B ()
#4  0x00000000004681a7 in SYSUTILS_$$_FLOATTOSTR$SINGLE$TFORMATSETTINGS$$ANSISTRING ()
#5  0x00000000006e7ea0 in VMT_$SYSUTILS_$$_TMREWEXCEPTION$indirect ()
#6  0x0000000000001b9a in ?? ()
#7  0x0000000000000000 in ?? ()

And now I'm lost. I don't see what I have done wrong here?

[winni]

Hi!

You do a recursive call for every pixel.
The result is known:

There is not enough space one the stack for all the recursive calls.

Solution: Use a linear algo for the floodfill

Winni

[big_M]

Oh, that's a bummer

Yeah, I was already thinking about something along those lines. So this is really a drawback for recursive methods then?

Alternatively I could get rid of the two variables and rewrite GetPixel and GetNoDataValue to be functions I guess.

Other question, how do I know how full the stack is? That is a topic I have no idea about...

[winni]

Hi!

There is a switch for the size of the stack and the heap:

 {$M StackSize,HeapSize}

I you got enough RAM you can play around with it.

Winni

[Warfley]

Tail recursion should usually be flattable by the optimizer making no stack allocations. But I don't know if the FPC supports this optimization

[winni]

Hi!

In the package BGRAbitmapPack you'll find the unit BGRAdefaultBitmap which contains the procedure ParallelFloodFill

It shows how to do a linear FloodFill without recursion.

Winni

[big_M]

Oh, interesting, thanks!

[big_M]

Tail recursion should usually be flattable by the optimizer making no stack allocations. But I don't know if the FPC supports this optimization

fpc -i

Supported Optimizations:
  REGVAR
  STACKFRAME
  PEEPHOLE
  LOOPUNROLL
  TAILREC
  CSE
  DFA
  USERBP
  ORDERFIELDS
  FASTMATH
  REMOVEEMPTYPROCS
  CONSTPROP

hmm... seems so

[PascalDragon]

Tail recursion should usually be flattable by the optimizer making no stack allocations. But I don't know if the FPC supports this optimization

It does, but it needs to be explicitly enabled using -Ootailrec (or a corresponding $Optimization TailRec directive)

[Warfley]

Then you should try to compile that code with the optimization. Because this is a tail recursion. The question is if the compiler detects this over two functions

[Thaddy]

The optimization tail recurson turns it into a while loop btw - flatten it - . You can also do that yourself. That is often better to understand what is happening.

[PascalDragon]

Then you should try to compile that code with the optimization. Because this is a tail recursion. The question is if the compiler detects this over two functions

No, it won't. The optimization only handles calls to the same routine.

[Warfley]

No, it won't. The optimization only handles calls to the same routine.

Before or after inlining?

[Thaddy]

Then you should try to compile that code with the optimization. Because this is a tail recursion. The question is if the compiler detects this over two functions

No, it won't. The optimization only handles calls to the same routine.

Well it is documented as such, Sarah: https://www.freepascal.org/docs-html/prog/progsu58.html
Or do I misunderstood again? 

[PascalDragon]

No, it won't. The optimization only handles calls to the same routine.

Before or after inlining?

I think it's done after inlining which might lead to situations where the optimization is not applied then.

Then you should try to compile that code with the optimization. Because this is a tail recursion. The question is if the compiler detects this over two functions

No, it won't. The optimization only handles calls to the same routine.

Well it is documented as such, Sarah: https://www.freepascal.org/docs-html/prog/progsu58.html
Or do I misunderstood again? 

It's not documented either way whether it works across routines or not, it just says:

TAILREC
    change tail recursion to regular while

It's also not mentioned whether all optimizations apply only at a single routine or not (yes, they all apply only to single routines, but that's not the point here).