[Freeciv-Dev] (PR#19822) bug in path_finding.c

["arno." <arno.@xxxxxxxxxx>]

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=19822 >

Hi,
I saw a bug on debian bug tracker :
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=309046

A segfault while telling an unit to go somewhere near an arctic tile.  
There is a savefile attached. I investigated and found that this bug 
comes from path_finding.c

The segfault occurs in create_danger_segment (l765). In 
create_danger_segment, you pass the length of danger_segment to create, 
you start from the current node and go back along the danger path length 
times, and you're supposed to come to a safe tile.

What happens is : segment_length attached to the first node is sometimes 
bigger than the number of steps required to go to a safe tile. In the 
case where the last element of the segment is related to the depart tile 
(ie: you want to goto a tile just near an arctic tile), you come to 
(l793)  :

/* Step further down the tree */
ptile = mapstep(ptile, DIR_REVERSE(node->dir_to_here));
node = &pf_map->lattice[ptile->index];


but node->dir_to_here is not initialized, so mapstep returns NULL, and  
reading ptile->index causes a crash.


segment_length is defined in danger_iterate_map :

(l984)
if (d_node->is_dangerous) {
    /* Increment the number of steps we are making across danger */
    d_node1->segment_length = d_node->segment_length + 1;
} else {
    /* We just moved into the danger area */
    d_node1->segment_length = 1;
}


but the process for dangerous tile is not a real Dijkstra : nodes can be 
processed multiples times :

see (l886):
/* Dangerous tiles can be updated even after being processed */
if ((pf_map->status[index1] == NS_PROCESSED 
    || pf_map->status[index1] == NS_WAITING) 
    && !d_node1->is_dangerous) {
    continue;
}

see also (l968):
/* The procedure is slightly different for dangerous nodes */
/* We will update costs if:
 * 1: we are here for the first time
 * 2: we can possibly go further across dangerous area or
 * 3: we can have lower extra and will not 
 *    overwrite anything useful */
if (pf_map->status[index1] == NS_UNINIT
    || (get_moves_left(pf_map, cost)
    > get_moves_left(pf_map, node1->cost))
    || (get_total_CC(pf_map, cost, extra)
    < get_total_CC(pf_map, node1->cost, node1->extra_cost)
    && pf_map->status[index1] == NS_PROCESSED)) {


So, the scenario is :
you process for example node number 10. segment_length is for example 
12. Then you process node number 11. It's near node 10, so 
segment_length will be 13. Then you process again node number 10 
(because you find a path with lower cost), and segment_length is now 8.
So, segment_length of node number 11 should be 9, but it will stay 13

I tried to tinker a bit in create_danger_segment to avoid using 
segment_length, something like : 

do {
} while (ptile->is_dangerous) 
and necessary modifications to take into account "waited"

I got sometimes a new segfault in danger_construct_path :
(l1139)
/* 5: Step further back */
ptile = mapstep(ptile, DIR_REVERSE(dir_next));
node = &pf_map->lattice[ptile->index];
d_node = &pf_map->d_lattice[ptile->index];

it seemed to be the same problem as explained before :
(l983)
d_node1->step = loc_step + 1;

step of next nodes is not updated, so 
(l1074)
for (i = d_node->step; i >= 0; i--) {
will process too much nodes.

when doing :

/* 3: Check if we finished */
  if (same_pos(ptile, pf_map->params->start_tile)) {
  return path;
}

instead of 
(l1117)
/* 3: Check if we finished */
if (i == 0) {
  /* We should be back at the start now! */
  assert(same_pos(ptile, pf_map->params->start_tile));
  return path;
}

I went out of path_finding.c but triggered a few asserts in 
update_last_part (in goto.c)


May be segment_length and step (and possibly other stuffs) should be 
updated for following nodes each time an already procesed dangerous node 
is updated, but it could be quite bad for performance. May be a way 
should be found to not process dangerous nodes more than once.

pgpZBnTCCXHLS.pgp
Description: PGP signature