[freeciv-ai] (PR#10613) create_danger_segment called more than once per node

["Gregory Berkolaiko" <Gregory.Berkolaiko@xxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=10613 >

> [jdorje - Thu Oct 21 17:14:15 2004]:
> 
> In fact this bug is inside PF.  When iterating over a danger map
> sometimes the danger segment for a node will be allocated multiple times.
> 
> I really have no idea what's going on here (though I haven't looked
> closely).  Is there supposed to be one danger segment for each direction
> (currently there is just one per node)?  Or are we erronously
> initializing the danger data for the node more than once?
> 
> This patch "fixes" the problem by freeing the data before allocating it
> a second time.  Replace this check with an assert and you can see the
> bug in action.  The patch fixes the leak without breaking anything...but
> there's a pretty good chance the current behavior is buggy.

Your patch was right.  The fears were unfounded -- it is ok for the
danger_segment to be written multiple times.  It is the danger-PF
analogue of dir_to_here which gets overwritten every now and then when
we find a better route.

Attached patch moves things around a bit, adds an error message (can do
an assert too but it's not a critical mistake) and adds some comments.

Gr.

Index: common/aicore/path_finding.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/path_finding.c,v
retrieving revision 1.26
diff -u -r1.26 path_finding.c
--- common/aicore/path_finding.c        22 Nov 2004 19:14:41 -0000      1.26
+++ common/aicore/path_finding.c        23 Nov 2004 06:04:44 -0000
@@ -771,11 +771,7 @@
 
   /* Allocating memory */
   if (d_node1->danger_segment) {
-    /* FIXME: it is probably a major bug that create_danger_segment gets
-     * called more than once per node.  Here we prevent a memory leak when
-     * it happens, but who knows what other problems it could cause?  See
-     * PR#10613. */
-    free(d_node1->danger_segment);
+    freelog(LOG_ERROR, "Possible memory leak in create_danger_segment");
   }
   d_node1->danger_segment = fc_malloc(length * sizeof(struct pf_danger_pos));
 
@@ -831,14 +827,16 @@
   return cost;
 }
 
-/*****************************************************************
+/*****************************************************************************
   Primary method for iterative path-finding in presence of danger
   Notes: 
   1. Whenever the path-finding stumbles upon a dangerous 
   location, it goes into a sub-Dijkstra which processes _only_ 
   dangerous locations, by means of a separate queue.  When this
   sub-Dijkstra reaches a safe location, it records the segment of
-  the path going across the dangerous terrain.
+  the path going across the dangerous terrain.  Hence danger_segment is an
+  extended (and reversed) version of the dir_to_here field.  It can be 
+  re-recorded multiple times as we find shorter and shorter routes.
   2. Waiting is realised by inserting the (safe) tile back into 
   the queue with a lower priority P.  This tile might pop back 
   sooner than P, because there might be several copies of it in 
@@ -856,7 +854,7 @@
   is one.  To gurantee the best (in terms of total_CC) safe segments 
   across danger, supply get_EC which returns small extra on 
   dangerous tiles.
-******************************************************************/
+*****************************************************************************/
 static bool danger_iterate_map(struct pf_map *pf_map)
 {
   mapindex_t index;
@@ -941,16 +939,16 @@
          node1->cost = cost;
          node1->dir_to_here = dir;
           d_node1->step = loc_step + 1;
+          /* Clear the previously recorded path back */
+          if (d_node1->danger_segment) {
+            free(d_node1->danger_segment);
+            d_node1->danger_segment = NULL;
+          }
          if (d_node->is_dangerous) {
            /* Transition from red to blue, need to record the path back */
            create_danger_segment(pf_map, dir, d_node1, 
                                   d_node->segment_length);
          } else {
-           /* Clear the path back */
-           if (d_node1->danger_segment) {
-             free(d_node1->danger_segment);
-             d_node1->danger_segment = NULL;
-           }
             /* We don't consider waiting to get to a safe tile as 
              * "real" waiting */
            d_node1->waited = FALSE;