[solved] weird segfault [--> stack overflow] lazarus / 62-General ---------------------------------------------------------------------- big_M · 2021-10-07 16:14 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure FillFloodMaps_Crawler(x,y,dist:integer; fillHeight:single); forward; procedure FillFloodMaps(x,y,dist:integer; fillHeight:single);var DEM_Height, DEM_NoDataValue:single;begin  if FlowMap[x,y] >= dist then    if FloodHeightMap[x,y] < fillHeight then    begin      //DEM_Height:=0;      //writeLn(floattostr(DEM_Height));      {--> segfaults when uncommented}      DEM.GetPixel(x,y,single(DEM_Height));  {--> segfaults}      //writeLn(floattostr(DEM_Height));      DEM.GetNoDataValue(single(DEM_NoDataValue));      if (DEM_Height<>DEM_NoDataValue) AND (DEM_Height=0)             AND (y+1<=Flood.Height-1) then FillFloodMaps(x-1,y+1,dist,fillHeight);  if (x-1>=0)                                     then FillFloodMaps(x-1,y,  dist,fillHeight);  if (x-1>=0)             AND (y-1>=0)              then FillFloodMaps(x-1,y-1,dist,fillHeight);  if                          (y-1>=0)              then FillFloodMaps(x,y-1,  dist,fillHeight);  if (x+1<=Flood.Width-1) AND (y-1>=0)              then FillFloodMaps(x+1,y-1,dist,fillHeight);end;       Part of UEnvi.pas which contains the .GetPixel procedure: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure TEnviMap.GetPixel(x,y:integer; var value:Single);begin  try    value:=FMap_Single[x,y]  except    WriteLn('Access violation #4');    value:=0;    abort:=true;  end;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: Quote#0  0x000000000044d74c in GETPIXEL (this=0x0, X=0, Y=0, VALUE=) 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: QuoteProgram received signal SIGSEGV, Segmentation fault. 0x000000000040710c in SYSTEM$_$STR_REAL$SMALLINT$SMALLINT$EXTENDED$TRE AL_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 · 2021-10-07 16:46 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 · 2021-10-07 17:17 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 · 2021-10-07 17:41 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 · 2021-10-07 17:54 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 · 2021-10-07 17:59 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 · 2021-10-07 18:01 Oh, interesting, thanks! ---------------------------------------------------------------------- big_M · 2021-10-07 18:32 Quote from: Warfley on October 07, 2021, 07:54:58 pmTail 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 QuoteSupported Optimizations:   REGVAR   STACKFRAME   PEEPHOLE   LOOPUNROLL   TAILREC   CSE   DFA   USERBP   ORDERFIELDS   FASTMATH   REMOVEEMPTYPROCS   CONSTPROP hmm... seems so ---------------------------------------------------------------------- PascalDragon · 2021-10-08 13:09 Quote from: Warfley on October 07, 2021, 07:54:58 pmTail 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 · 2021-10-08 13:18 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 · 2021-10-08 13:23 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 · 2021-10-08 13:38 Quote from: Warfley on October 08, 2021, 03:18:52 pmThen 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 · 2021-10-08 13:53 Quote from: PascalDragon on October 08, 2021, 03:38:56 pmNo, it won't. The optimization only handles calls to the same routine. Before or after inlining? ---------------------------------------------------------------------- Thaddy · 2021-10-08 14:53 Quote from: PascalDragon on October 08, 2021, 03:38:56 pmQuote from: Warfley on October 08, 2021, 03:18:52 pmThen 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 · 2021-10-11 11:49 Quote from: Warfley on October 08, 2021, 03:53:21 pmQuote from: PascalDragon on October 08, 2021, 03:38:56 pmNo, 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. Quote from: Thaddy on October 08, 2021, 04:53:43 pmQuote from: PascalDragon on October 08, 2021, 03:38:56 pmQuote from: Warfley on October 08, 2021, 03:18:52 pmThen 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: QuoteTAILREC     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). ---------------------------------------------------------------------- big_M · 2021-10-12 10:42 Okey, so I tried to compile it with the TAILREC optimization. For this I quickly merged the two procedures into one. The code looks like this now: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure FillFloodMaps(x,y,dist:integer; fillHeight:single);var DEM_NoDataValue,DEM_Height: single;    run: boolean;begin  run:=false;  if FlowMap[x,y] >= dist then    if FloodHeightMap[x,y] < fillHeight then    begin      DEM.GetPixel(x,y,single(DEM_Height));    DEM.GetNoDataValue(single(DEM_NoDataValue));      if (DEM_Height<>DEM_NoDataValue) AND (DEM_Height=0)             AND (y+1<=Flood.Height-1) then FillFloodMaps(x-1,y+1,dist,fillHeight);    if (x-1>=0)                                     then FillFloodMaps(x-1,y,  dist,fillHeight);    if (x-1>=0)             AND (y-1>=0)              then FillFloodMaps(x-1,y-1,dist,fillHeight);    if                          (y-1>=0)              then FillFloodMaps(x,y-1,  dist,fillHeight);  if (x+1<=Flood.Width-1) AND (y-1>=0)              then FillFloodMaps(x+1,y-1,dist,fillHeight);  end;end;                     Unfortunately the optimization doesn't work. But now I'm wondering if this case really is a tail recursion? I'm not too sure about the definition of a tail recursion, but in my case I have multiple lines which run the procedure, so if it is run the first time (line 21) there is still code behind it (even though they all just run the procedure). ---------------------------------------------------------------------- Warfley · 2021-10-12 14:21 I've been wrong in my previous post, this is not a tail recursion, as these if statements are not mutually exclusive (i.e. else if). You could change this by having a fixed order in which you traverse, e.g. zig zag (i.e. first 0,0 then 1,0 then 0,1 then 2,0 then 1,1 then 0,2 then 3,0 then 2,1 then 1,2 then 0,3 and so on) This covers every pixel and only requires one recursive call in the end making it a tail recursion ---------------------------------------------------------------------- big_M · 2021-10-12 15:33 Okey, thanks Then I know I haven't done this for nothing, because I have rewritten it now without recursion. @winni: Thanks for your example. I must say I didn't really understand it, so I just gave it a try myself. I guess the result is something similar though in the end. So far it seems to run fine. I'll post the code just in case someone would find it usefull: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure FillFloodMaps(x,y,dist:integer; fillHeight:single);type  TCheckedDirections = array [0..7] of boolean;  TCheckCoordinate = record    Directions: TCheckedDirections;    x: integer;    y: integer;  end;  TPixelList = array of TCheckCoordinate; var  PixelList: TPixelList;  DEM_NoDataValue,DEM_Height: single;  i:integer;  removePixel: boolean;   procedure IncPixelList(Ax,Ay,AOrigin:integer);  var Fi:integer;  begin    setLength(PixelList, length(PixelList)+1);    for Fi:=0 to 7 do    begin      if Fi=AOrigin then {Set origin direction to true so we don't go backwards}        PixelList[high(PixelList)].Directions[Fi]:=true      else        PixelList[high(PixelList)].Directions[Fi]:=false;    end;    PixelList[high(PixelList)].x:=Ax;    PixelList[high(PixelList)].y:=Ay;  end;   procedure DecPixelList;  begin    setLength(PixelList, length(PixelList)-1);  end;   function CheckPixel(Ax,Ay,Ai:integer):boolean;  begin    result:=false;     //Set the coordinates to check    case Ai of      0: begin Ax:=Ax+1;          end;      1: begin Ax:=Ax+1; Ay:=Ay+1;  end;      2: begin         Ay:=Ay+1;  end;      3: begin Ax:=Ax-1; Ay:=Ay+1;  end;      4: begin Ax:=Ax-1;            end;      5: begin Ax:=Ax-1; Ay:=Ay-1;  end;      6: begin           Ay:=Ay-1;  end;      7: begin Ax:=Ax+1; Ay:=Ay-1;  end;    end;     //If the coordinates are within bounds and the FloodMaps can be drawn    //add the pixel to the PixelList.    if (Ax>=0) AND (Ax=0) AND (Ay= dist then        if FloodHeightMap[Ax,Ay] < fillHeight then        begin          DEM.GetPixel(Ax,Ay,single(DEM_Height));          if (DEM_Height<>DEM_NoDataValue) AND (DEM_Height0 do  begin    x:=PixelList[high(PixelList)].x;    y:=PixelList[high(PixelList)].y;  removePixel:=true;    for i:=0 to 7 do    begin      if PixelList[high(PixelList)].Directions[i]=false then      begin        PixelList[high(PixelList)].Directions[i]:=true;        removePixel:=false;        if CheckPixel(x,y,i) then break; {If FloodMaps can be drawn break the loop and continue with the next pixel}      end;    end;    if removePixel then DecPixelList; {All directions checked, remove last pixel from PixelList and continue with prvious pixel}  end;end;