Osrm-backend: assertion failed @ QueryHeap::MinKey()

[slavanap]

I've localized the issue and made the proper patch (below). The assetion only fails with alternatives=true in the query.
I'm not aware of the algorithm, thus this patch may be not exhaustive.

diff --git a/src/engine/routing_algorithms/alternative_path_mld.cpp b/src/engine/routing_algorithms/alternative_path_mld.cpp
index 7bc14e5..5fffa63 100644
--- a/src/engine/routing_algorithms/alternative_path_mld.cpp
+++ b/src/engine/routing_algorithms/alternative_path_mld.cpp
@@ -683,6 +683,9 @@ makeCandidateVias(SearchEngineData<Algorithm> &search_engine_data,
     // we're over factor * weight. We have to set the weight for routingStep to INVALID_EDGE_WEIGHT
     // so that stepping will continue even after we reached the shortest path upper bound.

+    if (forward_heap.Empty())
+        return candidate_vias;
+
     EdgeWeight forward_heap_min = forward_heap.MinKey();
     EdgeWeight reverse_heap_min = reverse_heap.MinKey();

backtrace:

[assert][140490038109952] /src/osrm-backend/include/util/query_heap.hpp:280
in: Weight osrm::util::QueryHeap<NodeID, Key, Weight, Data, IndexStorage>::MinKey() const [with NodeID = unsigned int; Key = unsigned int; Weight = int; Data = osrm::engine::MultiLayerDijkstraHeapData; IndexStorage = osrm::util::TwoLevelStorage<unsigned int, int>]: !heap.empty()
terminate called without an active exception

Thread 4 "osrm-routed" received signal SIGABRT, Aborted.
[Switching to Thread 0x7fc662d0e700 (LWP 1548)]
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
50      ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
(gdb) bt
#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1  0x00007fc7df6e1859 in __GI_abort () at abort.c:79
#2  0x00007fc7dfab6951 in ?? () from /lib/x86_64-linux-gnu/libstdc++.so.6
#3  0x00007fc7dfac247c in ?? () from /lib/x86_64-linux-gnu/libstdc++.so.6
#4  0x00007fc7dfac24e7 in std::terminate() () from /lib/x86_64-linux-gnu/libstdc++.so.6
#5  0x0000563eb36b396e in (anonymous namespace)::assertion_failed_msg_helper (expr=expr@entry=0x563eb3849931 "!heap.empty()", msg=msg@entry=0x563eb3846f3c "",
    function=function@entry=0x563eb3874de8 "Weight osrm::util::QueryHeap<NodeID, Key, Weight, Data, IndexStorage>::MinKey() const [with NodeID = unsigned int; Key = unsigned int; Weight = int; Data = osrm::engine::MultiLayerDijkstraHeapData; In"..., file=file@entry=0x563eb3870c58 "/src/osrm-backend/include/util/query_heap.hpp", line=line@entry=280)
    at /src/osrm-backend/src/util/assert.cpp:19
#6  0x0000563eb36b398b in boost::assertion_failed (expr=expr@entry=0x563eb3849931 "!heap.empty()",
    function=function@entry=0x563eb3874de8 "Weight osrm::util::QueryHeap<NodeID, Key, Weight, Data, IndexStorage>::MinKey() const [with NodeID = unsigned int; Key = unsigned int; Weight = int; Data = osrm::engine::MultiLayerDijkstraHeapData; In"..., file=file@entry=0x563eb3870c58 "/src/osrm-backend/include/util/query_heap.hpp", line=line@entry=280)
    at /src/osrm-backend/src/util/assert.cpp:28
#7  0x0000563eb37e5c79 in osrm::util::QueryHeap<unsigned int, unsigned int, int, osrm::engine::MultiLayerDijkstraHeapData, osrm::util::TwoLevelStorage<unsigned int, int, osrm::util::UnorderedMapStorage, osrm::util::ArrayStorage> >::MinKey (this=this@entry=0x7fc6580038f0) at /src/osrm-backend/include/util/query_heap.hpp:278
#8  0x0000563eb37eddf2 in osrm::engine::routing_algorithms::(anonymous namespace)::makeCandidateVias (search_engine_data=..., facade=..., phantom_node_pair=..., parameters=...)
    at /src/osrm-backend/src/engine/routing_algorithms/alternative_path_mld.cpp:686
#9  0x0000563eb37efd98 in osrm::engine::routing_algorithms::alternativePathSearch (search_engine_data=..., facade=..., phantom_node_pair=...,
    number_of_alternatives=number_of_alternatives@entry=1) at /src/osrm-backend/src/engine/routing_algorithms/alternative_path_mld.cpp:796
#10 0x0000563eb3765d1f in osrm::engine::RoutingAlgorithms<osrm::engine::routing_algorithms::mld::Algorithm>::AlternativePathSearch (this=this@entry=0x7fc662d0caa0, phantom_node_pair=...,
    number_of_alternatives=number_of_alternatives@entry=1) at /src/osrm-backend/include/engine/routing_algorithms.hpp:154
#11 0x0000563eb37cf243 in osrm::engine::plugins::ViaRoutePlugin::HandleRequest (this=this@entry=0x563eb55824f4, algorithms=..., route_parameters=..., result=...)
    at /src/osrm-backend/src/engine/plugins/viaroute.cpp:124
#12 0x0000563eb3764e63 in osrm::engine::Engine<osrm::engine::routing_algorithms::mld::Algorithm>::Route (this=0x563eb55824e0, params=..., result=...)
    at /src/osrm-backend/include/engine/engine.hpp:88
#13 0x0000563eb374f2dd in osrm::OSRM::Route (this=this@entry=0x563eb55824d0, params=..., result=...) at /src/osrm-backend/src/osrm/osrm.cpp:62
#14 0x0000563eb36af348 in osrm::server::service::RouteService::RunQuery (this=0x563eb55835a0, prefix_length=18, query=..., result=...)
    at /src/osrm-backend/src/server/service/route_service.cpp:74
#15 0x0000563eb36b350e in osrm::server::ServiceHandler::RunQuery (this=this@entry=0x563eb5582490, parsed_url=..., result=...) at /src/osrm-backend/src/server/service_handler.cpp:52
#16 0x0000563eb36a2aa5 in osrm::server::RequestHandler::HandleRequest (this=<optimized out>, current_request=..., current_reply=...) at /src/osrm-backend/src/server/request_handler.cpp:69
#17 0x0000563eb3698ae7 in osrm::server::Connection::handle_read (this=0x7fc654000cd0, error=..., bytes_transferred=<optimized out>) at /src/osrm-backend/src/server/connection.cpp:79
#18 0x0000563eb36942e5 in boost::_mfi::mf2<void, osrm::server::Connection, boost::system::error_code const&, unsigned long>::call<std::shared_ptr<osrm::server::Connection>, boost::system::error_code const, unsigned long> (this=this@entry=0x7fc662d0d730, u=..., b1=..., b2=@0x7fc662d0d448: 158, b2@entry=@0x7fc662d0d448: <optimized out>)
    at /usr/include/boost/bind/mem_fn_template.hpp:269
#19 0x0000563eb3694311 in boost::_mfi::mf2<void, osrm::server::Connection, boost::system::error_code const&, unsigned long>::operator()<std::shared_ptr<osrm::server::Connection> > (
    this=this@entry=0x7fc662d0d730, u=..., a1=..., a2=<optimized out>) at /usr/include/boost/bind/mem_fn_template.hpp:283
#20 0x0000563eb369437f in boost::_bi::list3<boost::_bi::value<std::shared_ptr<osrm::server::Connection> >, boost::arg<1> (*)(), boost::arg<2> (*)()>::operator()<boost::_mfi::mf2<void, osrm::server::Connection, boost::system::error_code const&, unsigned long>, boost::_bi::rrlist2<boost::system::error_code const&, unsigned long const&> > (this=this@entry=0x7fc662d0d740,
    f=..., a=...) at /usr/include/boost/bind/bind.hpp:396
#21 0x0000563eb36943d3 in boost::_bi::bind_t<void, boost::_mfi::mf2<void, osrm::server::Connection, boost::system::error_code const&, unsigned long>, boost::_bi::list3<boost::_bi::value<std::shared_ptr<osrm::server::Connection> >, boost::arg<1> (*)(), boost::arg<2> (*)()> >::operator()<boost::system::error_code const&, unsigned long const&> (this=0x7fc662d0d730, a1=...,
    a2=<optimized out>) at /usr/include/boost/bind/bind.hpp:1315
#22 0x0000563eb3694403 in boost::asio::detail::binder2<boost::_bi::bind_t<void, boost::_mfi::mf2<void, osrm::server::Connection, boost::system::error_code const&, unsigned long>, boost::_bi::list3<boost::_bi::value<std::shared_ptr<osrm::server::Connection> >, boost::arg<1> (*)(), boost::arg<2> (*)()> >, boost::system::error_code, unsigned long>::operator() (
    this=<optimized out>) at /usr/include/boost/asio/detail/bind_handler.hpp:162
#23 0x0000563eb3694460 in boost::asio::asio_handler_invoke<boost::asio::detail::binder2<boost::_bi::bind_t<void, boost::_mfi::mf2<void, osrm::server::Connection, boost::system::error_code const&, unsigned long>, boost::_bi::list3<boost::_bi::value<std::shared_ptr<osrm::server::Connection> >, boost::arg<1> (*)(), boost::arg<2> (*)()> >, boost::system::error_code, unsigned long> > (function=...) at /usr/include/boost/asio/handler_invoke_hook.hpp:67
#24 0x0000563eb369448a in boost_asio_handler_invoke_helpers::invoke<boost::asio::detail::binder2<boost::_bi::bind_t<void, boost::_mfi::mf2<void, osrm::server::Connection, boost::system::err--Type <RET> for more, q to quit, c to continue without paging--q

[slavanap]

Query without alternatives=true in it returns {"message":"No route found between points","code":"NoRoute"} for the same coordinates.

[mjjbell]

I expect this will be symmetric and the assertion can fail for reverse_heap too.

Do still have the query that causes the failure? Would be good to reduce it down to a test case.

[slavanap]

@mjjbell here's the failing instance
slavanap/navi:osrm-5843-hash-bug-demo
the query is
curl 'http://localhost:5000/route/v1/driving/-73.86648000000001,40.8782;-73.88431,40.88261?alternatives=true'

If you run the docker image, it'll sigfault.

[slavanap]

I've minimized the test case even further. https://github.com/slavanap/osrm-5843

[mjjbell]

Thanks for the details. Here's what I've understood so far.

Similar to #5840, this is due to a potential mismatch between what request coordinates can be snapped to in the network, and what is valid after a traffic update.

This line of traffic.csv that sets the speed and rate of a segment to zero is causing the issue:

42773743,42722112,0,0

It updates the last segment in the way the source coordinates are snapped to

After the traffic update, that segment is therefore marked as invalid. Given this is a one-way road, no route can be found from the source. As you've seen, it looks like the alternative path code always assumes the source/target phantom nodes are valid and the search heaps are populated.

Interestingly, flipping the source/target coordinates doesn't fail the assertion.
I think this is because it won't snap a target to the last segment in a way, so either snaps to the segment before and a path is found, or snaps to the way after and doesn't (but at least populates the reverse heap).

If you make the middle segment zero speed and rate instead, the reverse route will also fail:

42773744,42773743,0,0

This is a long-winded way of saying that yes, both heap assertions can fail for the same reason.
Therefore, adding an empty check for both heaps should fix this, or there might be a nice way to incorporate the check into the loop invariant.

Ultimately, adding this check won't help in finding a route though. I think the longer-term approach suggested in #5840 of snapping to N nearest locations to find a valid route would also be needed here.

[slavanap]

Will setting edge value to something very small resolve the "snapping" issue? like to 0.00000001

[mjjbell]

It should prevent it being marked as invalid. I can't say if it has other side effects though. I think you'll just end up with more expensive routes (including alternatives) from that source.

[slavanap]

I see. Is there any way to completely remove that edge and rebuild the graph (even if it'd take long, I'm running offline analysis anyway)? I'm thinking of altering OSM file. Probably it'd work. Or maybe there's other command with OSRM?

[mjjbell]

If you're ok with reconstructing the graph, you could probably utilise the lua profile scripting and a combination of process_way for removing edges and process_segment to set speed/rate from your CSV file. Then you won't have to edit the OSM file.

[slavanap]

This is solved for me. Thank you!

@mjjbell, will adding checks be enough for forward_heap and reverse_heap for PR?
Otherwise, feel free to close the issue.

[mjjbell]

Let's also add a testcase for this. I'm happy to make the PR.

[danpat]

If you can make a PR soon, I've actually got some time to do a proper release - I've tagged 5.23.0-rc.1 already, but it'd be nice to get this fix in as well.

[mjjbell]

Created #5851