Stack Overflow Error: Infinite Recursion With Cyclicly Connected Intersections.

[DrSuperGood]

Roundabouts are when one way road signs are used to direct traffic in a circular motion around a circular section of road with various branches going off from it. Since each lane branches off the idea is that it allows traffic to continuously move and prevents the need to directly cross a lane of traffic at a right angle. If this allows higher throughput over a standard intersection I do not know however it does look pretty cool.

What should happen...
Best result would be if the convoys continuously move in a circular motion. If all sides are taken at once by convoys destined towards a non-immediate turnoff then they all rotate together (driving across their appropriate intersections simultaneously) in a circular motion.

A worse alternative would be that they are reported as stuck. Since parking on an intersection is not allowed and the intersection destination is blocked by a convoy in a similar circumstance ending in a loop back at the first convoy there are cyclic dependencies. As it will not resolve naturally the convoys can happily report back as stuck.

What does happen...
The game throws a Stack Overflow exception. This is fatal so the game has to be closed.

Version...
Affects both current release and nighly build. Probably has been a problem for a very long time.

Extra details...
This stack trace from the latest nightly gives a good idea why a stack overflow is occurring.

Code Select Expand


Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++
Simutrans Debug.exe!vehicle_t::can_enter_tile(int & restart_speed, bool second_check) Line 1062 C++
Simutrans Debug.exe!road_vehicle_t::can_enter_tile(const grund_t * gr, int & restart_speed, bool second_check) Line 2208 C++

Infinite call recursion between the convoys with cyclic dependencies fills the thread stack until it overflows and the OS raises a fatal error and aborts the process.

The blocks of code involved are...

Code Select Expand


bool road_vehicle_t::can_enter_tile(const grund_t *gr, int &restart_speed, bool second_check)
{
// check for traffic lights (only relevant for the first car in a convoi)
if(  leading  ) {
// no further check, when already entered a crossing (to allow leaving it)
if (!second_check) {
const grund_t *gr_current = welt->lookup(get_pos());
if(  gr_current  &&  gr_current->ist_uebergang()  ) {
return true;
}
}

assert(gr);

const strasse_t *str = (strasse_t *)gr->get_weg(road_wt);
if(  !str  ||  gr->get_top() > 250  ) {
// too many cars here or no street
return false;
}

// first: check roadsigns
const roadsign_t *rs = NULL;
if(  str->has_sign()  ) {
rs = gr->find<roadsign_t>();
route_t const& r = *cnv->get_route();

if(  rs  &&  (route_index + 1u < r.get_count())  ) {
// since at the corner, our direction may be diagonal, we make it straight
uint8 richtung = ribi_typ(get_pos(), pos_next);

if(  rs->get_besch()->is_traffic_light()  &&  (rs->get_dir()&richtung) == 0  ) {
// wait here
restart_speed = 16;
return false;
}
// check, if we reached a choose point
else {
// route position after road sign
const koord pos_next_next = r.position_bei(route_index + 1u).get_2d();
// since at the corner, our direction may be diagonal, we make it straight
richtung = ribi_typ( pos_next, pos_next_next );

if(  rs->is_free_route(richtung)  &&  !target_halt.is_bound()  ) {
if(  second_check  ) {
return false;
}
if(  !choose_route( restart_speed, richtung, route_index )  ) {
return false;
}
}
}
}
}

vehicle_base_t *obj = NULL;
uint32 test_index = route_index + 1u;

// way should be clear for overtaking: we checked previously
if(  !cnv->is_overtaking()  ) {
// calculate new direction
route_t const& r = *cnv->get_route();
koord3d next = route_index < r.get_count() - 1u ? r.position_bei(route_index + 1u) : pos_next;
ribi_t::ribi curr_direction   = get_direction();
ribi_t::ribi curr_90direction = calc_direction(get_pos(), pos_next);
ribi_t::ribi next_direction   = calc_direction(get_pos(), next);
ribi_t::ribi next_90direction = calc_direction(pos_next, next);
obj = no_cars_blocking( gr, cnv, curr_direction, next_direction, next_90direction );

// do not block intersections
bool int_block = ribi_t::is_threeway(str->get_ribi_unmasked())  &&  (((drives_on_left ? ribi_t::rotate90l(curr_90direction) : ribi_t::rotate90(curr_90direction)) & str->get_ribi_unmasked())  ||  curr_90direction != next_90direction  ||  (rs  &&  rs->get_besch()->is_traffic_light()));

// check exit from crossings and intersections, allow to proceed after 4 consecutive
while(  !obj   &&  (str->is_crossing()  ||  int_block)  &&  test_index < r.get_count()  &&  test_index < route_index + 4u  ) {
if(  str->is_crossing()  ) {
crossing_t* cr = gr->find<crossing_t>(2);
if(  !cr->request_crossing(this)  ) {
restart_speed = 0;
return false;
}
}

// test next position
gr = welt->lookup(r.position_bei(test_index));
if(  !gr  ) {
// way (weg) not existent (likely destroyed)
if(  !second_check  ) {
cnv->suche_neue_route();
}
return false;
}

str = (strasse_t *)gr->get_weg(road_wt);
if(  !str  ||  gr->get_top() > 250  ) {
// too many cars here or no street
return false;
}

// check cars
curr_direction   = next_direction;
curr_90direction = next_90direction;
if(  test_index + 1u < r.get_count()  ) {
next                 = r.position_bei(test_index + 1u);
next_direction   = calc_direction(r.position_bei(test_index - 1u), next);
next_90direction = calc_direction(r.position_bei(test_index),      next);
obj = no_cars_blocking( gr, cnv, curr_direction, next_direction, next_90direction );
}
else {
next                 = r.position_bei(test_index);
next_90direction = calc_direction(r.position_bei(test_index - 1u), next);
if(  curr_direction == next_90direction  ||  !gr->is_halt()  ) {
// check cars but allow to enter intersection if we are turning even when a car is blocking the halt on the last tile of our route
// preserves old bus terminal behaviour
obj = no_cars_blocking( gr, cnv, curr_direction, next_90direction, ribi_t::keine );
}
}

// check roadsigns
if(  str->has_sign()  ) {
rs = gr->find<roadsign_t>();
if(  rs  ) {
// since at the corner, our direction may be diagonal, we make it straight
if(  rs->get_besch()->is_traffic_light()  &&  (rs->get_dir() & curr_90direction)==0  ) {
// wait here
restart_speed = 16;
return false;
}
// check, if we reached a choose point

else if(  rs->is_free_route(curr_90direction)  &&  !target_halt.is_bound()  ) {
if(  second_check  ) {
return false;
}
if(  !choose_route( restart_speed, curr_90direction, test_index )  ) {
return false;
}
}
}
}
else {
rs = NULL;
}

// check for blocking intersection
int_block = ribi_t::is_threeway(str->get_ribi_unmasked())  &&  (((drives_on_left ? ribi_t::rotate90l(curr_90direction) : ribi_t::rotate90(curr_90direction)) & str->get_ribi_unmasked())  ||  curr_90direction != next_90direction  ||  (rs  &&  rs->get_besch()->is_traffic_light()));

test_index++;
}

if(  obj  &&  test_index > route_index + 1u  &&  !str->is_crossing()  &&  !int_block  ) {
// found a car blocking us after checking at least 1 intersection or crossing
// and the car is in a place we could stop. So if it can move, assume it will, so we will too.
if(  road_vehicle_t const* const car = obj_cast<road_vehicle_t>(obj)  ) {
const convoi_t* const ocnv = car->get_convoi();
int dummy;
[b] if(  ocnv->front()->get_route_index() < ocnv->get_route()->get_count()  &&  ocnv->front()->can_enter_tile(dummy, true)  ) {[/b]
return true;
}
}
}
}

// stuck message ...
if(  obj  &&  !second_check  ) {
if(  obj->is_stuck()  ) {
// end of traffic jam, but no stuck message, because previous vehicle is stuck too
restart_speed = 0;
cnv->set_tiles_overtaking(0);
cnv->reset_waiting();
}
else {
if(  test_index == route_index + 1u  ) {
// no intersections or crossings, we might be able to overtake this one ...
overtaker_t *over = obj->get_overtaker();
if(  over  &&  !over->is_overtaken()  ) {
if(  over->is_overtaking()  ) {
// otherwise we would stop every time being overtaken
return true;
}
// not overtaking/being overtake: we need to make a more thought test!
if(  road_vehicle_t const* const car = obj_cast<road_vehicle_t>(obj)  ) {
convoi_t* const ocnv = car->get_convoi();
if(  cnv->can_overtake( ocnv, (ocnv->get_state()==convoi_t::LOADING ? 0 : over->get_max_power_speed()), ocnv->get_length_in_steps()+ocnv->get_vehikel(0)->get_steps())  ) {
return true;
}
}
else if(  private_car_t* const caut = obj_cast<private_car_t>(obj)  ) {
if(  cnv->can_overtake(caut, caut->get_besch()->get_geschw(), VEHICLE_STEPS_PER_TILE)  ) {
return true;
}
}
}
}
// we have to wait ...
restart_speed = (cnv->get_akt_speed()*3)/4;
cnv->set_tiles_overtaking(0);
}
}

return obj==NULL;
}

return true;
}


Code Select Expand


bool vehicle_t::can_enter_tile(int &restart_speed, bool second_check)
{
grund_t *gr = welt->lookup(pos_next);
if (gr) {
[b] return can_enter_tile(gr, restart_speed, second_check);[/b]
}
else {
if(  !second_check  ) {
cnv->suche_neue_route();
}
return false;
}
}


The attached map can recreate this error.

Solution...
I currently have none. This issue is on-going.

[Dwachs]

Here is a fix. It basically saves all checked cars in a vector, then checks whether some car already was checked. No crash anymore, the roundabout still jams.

[DrSuperGood]

the roundabout still jams.

They would need special handling not to jam and I realise that now. Becoming stuck is better than crashing so it can be considered a solution.

Maybe in the future special mechanics could be considered for them.

[Ters]

There is a question how much a vehicle should take into consideration. I had a big "roundabout" lock-up yesterday, with a circumference of about twenty tiles.

[DrSuperGood]

There is a question how much a vehicle should take into consideration. I had a big "roundabout" lock-up yesterday, with a circumference of about twenty tiles.

In theory deadlock could occur with anything that has cyclically connected intersections. If there is no space left in the circle and all convoys waiting at all the comprising intersections want to move around the circle then there is a deadlock. One-way circles are most prone to this as it forces all traffic around in a single direction.

What actually is needed is a special turning circle type of way which has special intersections which convoys in the circle can park across and that if one-way convoys not going to immediate exits can overtake with the other lane across the intersection (so all convoys approaching intersections from the circle will leave the circle). However that is probably not worth the programming effort to implement.

[prissi]

Since the cars are checked in well-defined order, should it not be enough to have a flag which goes between 1 or zero (for even or odd step nr). If then a previous car is encoutnered that has stepped, then no further checks are needed. That could even save time in those roundabouts or similar situations, since not that many cars need to be checked.

[DrSuperGood]

People should not use roundabouts as this has shown. They can still lockup even if it does not crash.

[prissi]

True, but it may happen by accident.

By the way, should be drive_on_left not a static variable? Otherwise one could mix both directions on a road ...

[TurfIt]

Interesting this should only be found now... While developing these algorithms, the 'op' map was my prime testing one, and it's chock full of congested roundabouts. Make me wonder if some subsequent change to ist_weg_frei caused it, but I don't see any that look promising. Would be nice to find the culprit commit...

Here is a fix. It basically saves all checked cars in a vector, then checks whether some car already was checked. No crash anymore, the roundabout still jams.

I think simpler would be to just replace the second_check bool with a recursion counter. And return false after ending up too deep ( 8? ). The only purpose of this second_check is to allow a line of cars to all get moving together after they've been stopped. Make a huge difference in throughput past certain road structures sometimes maybe - . It's certainly not critical to the correct movement of the vehicles, so short circuiting after 8 or so would be fine.

In theory deadlock could occur with anything that has cyclically connected intersections. If there is no space left in the circle and all convoys waiting at all the comprising intersections want to move around the circle then there is a deadlock. One-way circles are most prone to this as it forces all traffic around in a single direction.

The 'op' game is very prone to this having some 3000 buses jammed onto the map. I spend quite some time unjamming things, but it can run at best 6 months before 60+ buses all form a circle around Mong Kok and deadlock.

People should not use roundabouts as this has shown.

Other than perhaps looking pretty, they have no real use in simutrans. Plain no traffic light intersections provide the best throughput (In very limited special circumstances traffic lights can help).

Since the cars are checked in well-defined order, should it not be enough to have a flag which goes between 1 or zero (for even or odd step nr). If then a previous car is encoutnered that has stepped, then no further checks are needed. That could even save time in those roundabouts or similar situations, since not that many cars need to be checked.

I'm not sure how this would help. It's possible all the cars in the circle have not been processed yet, hence the infinite recursion would still occur. Further, I had such a sync_step heartbeat in several objects while experimenting with sync_step, it's a very significant performance killer. I think the simple recursion counter with limit should suffice.

By the way, should be drive_on_left not a static variable? Otherwise one could mix both directions on a road ...

IMO vehicle_base_t::drives_on_left could be removed completely. It's only used in vehicle_base_t::get_screen_offset, and it's only set true for road_vehicle_t and private_car_t objects. And it's only ever set from welt->get_settings().is_drive_left() which works as the static. Both road_vehicle_t::get_screen_offset and private_car_t::get_screen_offset already exist - the drive left function could be moved there.

[Dwachs]

Looks much better than my fix.

[prissi]

The seems indeed much more elegant. The superflous drvie left I submitted. YOu are free to submit also the other.