Asserting during map-matching when core factor used

[danpat]

Every now and again, we see an assertion being thrown during map-matching:

`bt full` leading up to assertion

(gdb) bt full
#0  0x00007f8c9fdc1c37 in raise () from /lib/x86_64-linux-gnu/libc.so.6
No symbol table info available.
#1  0x00007f8c9fdc5028 in abort () from /lib/x86_64-linux-gnu/libc.so.6
No symbol table info available.
#2  0x00007f8ca08f5bbd in __gnu_cxx::__verbose_terminate_handler() () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
No symbol table info available.
#3  0x00007f8ca08f3b96 in ?? () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
No symbol table info available.
#4  0x00007f8ca08f3be1 in std::terminate() () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
No symbol table info available.
#5  0x00007f8c9da4f2ac in (anonymous namespace)::assertion_failed_msg_helper (
    expr=0x7f8c9dabf1ba "forward_core_heap.GetData(middle).parent == middle && reverse_core_heap.GetData(middle).parent == middle", msg=0x7f8c9dac0855 "",
    function=0x7f8c9dabf04f "void osrm::engine::routing_algorithms::BasicRoutingInterface::SearchWithCore(const std::shared_ptr<const datafacade::BaseDataFacade>, SearchEngineData::QueryHeap &, SearchEngineData::QueryHeap &, Sear"...,
    file=0x7f8c9dabee53 "/home/travis/build/Project-OSRM/node-osrm/deps/osrm-backend-Debug/src/engine/routing_algorithms/routing_base.cpp", line=431)
    at /home/travis/build/Project-OSRM/node-osrm/deps/osrm-backend-Debug/src/util/assert.cpp:18
        tid = {_M_thread = 140241671280384}
#6  0x00007f8c9da4f1c7 in boost::assertion_failed (
    expr=0x7f8c9dabf1ba "forward_core_heap.GetData(middle).parent == middle && reverse_core_heap.GetData(middle).parent == middle",
    function=0x7f8c9dabf04f "void osrm::engine::routing_algorithms::BasicRoutingInterface::SearchWithCore(const std::shared_ptr<const datafacade::BaseDataFacade>, SearchEngineData::QueryHeap &, SearchEngineData::QueryHeap &, Sear"...,
    file=0x7f8c9dabee53 "/home/travis/build/Project-OSRM/node-osrm/deps/osrm-backend-Debug/src/engine/routing_algorithms/routing_base.cpp", line=431)
    at /home/travis/build/Project-OSRM/node-osrm/deps/osrm-backend-Debug/src/util/assert.cpp:27
No locals.
#7  0x00007f8c9da45db5 in osrm::engine::routing_algorithms::BasicRoutingInterface::SearchWithCore (this=0x1bccbf8, facade=warning: RTTI symbol not found for class 'std::_Sp_counted_ptr_inplace<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade, std::allocator<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade>, (__gnu_cxx::_Lock_policy)2>'
warning: RTTI symbol not found for class 'std::_Sp_counted_ptr_inplace<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade, std::allocator<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade>, (__gnu_cxx::_Lock_policy)2>'
std::shared_ptr (count 9, weak 0) 0x7f8680001380,
    forward_heap=..., reverse_heap=..., forward_core_heap=..., reverse_core_heap=..., weight=@0x7f8c8effbf48: 41, packed_leg=std::vector of length 0, capacity 0,
    force_loop_forward=false, force_loop_reverse=false, weight_upper_bound=6241)
    at /home/travis/build/Project-OSRM/node-osrm/deps/osrm-backend-Debug/src/engine/routing_algorithms/routing_base.cpp:430
        middle = 66241075
        forward_entry_points = std::vector of length 14, capacity 16 = {std::tuple containing = {[1] = 52003922, [2] = -2019, [3] = 52003923}, std::tuple containing = {
            [1] = 38395, [2] = -1652, [3] = 20403636}, std::tuple containing = {[1] = 38393, [2] = -1631, [3] = 20403636}, std::tuple containing = {[1] = 20486256,
            [2] = -1402, [3] = 20403635}, std::tuple containing = {[1] = 47744389, [2] = -1238, [3] = 20403636}, std::tuple containing = {[1] = 64617055, [2] = -1172,
            [3] = 20225327}, std::tuple containing = {[1] = 64617056, [2] = -1127, [3] = 20225327}, std::tuple containing = {[1] = 64617061, [2] = -756, [3] = 20542431},
          std::tuple containing = {[1] = 64617059, [2] = -558, [3] = 64617062}, std::tuple containing = {[1] = 52003970, [2] = -412, [3] = 20403635},
          std::tuple containing = {[1] = 66241087, [2] = 340, [3] = 52003928}, std::tuple containing = {[1] = 52003936, [2] = 440, [3] = 52003978}, std::tuple containing = {
            [1] = 66241065, [2] = 773, [3] = 20366556}, std::tuple containing = {[1] = 66257727, [2] = 2286, [3] = 52003942}}
        reverse_entry_points = std::vector of length 19, capacity 32 = {std::tuple containing = {[1] = 58849798, [2] = 420, [3] = 57717628}, std::tuple containing = {
            [1] = 38364, [2] = 436, [3] = 57717628}, std::tuple containing = {[1] = 20403643, [2] = 505, [3] = 5445087}, std::tuple containing = {[1] = 52003922, [2] = 1300,
            [3] = 52004000}, std::tuple containing = {[1] = 20502902, [2] = 1335, [3] = 52004000}, std::tuple containing = {[1] = 64617059, [2] = 1384, [3] = 52004000},
          std::tuple containing = {[1] = 38361, [2] = 1391, [3] = 20229182}, std::tuple containing = {[1] = 47697650, [2] = 1454, [3] = 38362}, std::tuple containing = {
            [1] = 20502901, [2] = 1469, [3] = 20229182}, std::tuple containing = {[1] = 64617056, [2] = 1509, [3] = 52004004}, std::tuple containing = {[1] = 66241087,
            [2] = 1520, [3] = 52004000}, std::tuple containing = {[1] = 58849805, [2] = 1676, [3] = 52004004}, std::tuple containing = {[1] = 66241075, [2] = 1770,
---Type <return> to continue, or q <return> to quit---
            [3] = 57832346}, std::tuple containing = {[1] = 38389, [2] = 1877, [3] = 52004000}, std::tuple containing = {[1] = 66241060, [2] = 2004, [3] = 57832346},
          std::tuple containing = {[1] = 47697665, [2] = 2037, [3] = 38362}, std::tuple containing = {[1] = 20486256, [2] = 2119, [3] = 52004000}, std::tuple containing = {
            [1] = 20502895, [2] = 2401, [3] = 52004000}, std::tuple containing = {[1] = 38393, [2] = 2485, [3] = 57832346}}
        min_edge_offset = -4308
        STALLING_ENABLED = true
        insertInCoreHeap = {<No data fields>}
        min_core_edge_offset = -2019
        STALLING_DISABLED = false
#8  0x00007f8c9da46e3c in osrm::engine::routing_algorithms::BasicRoutingInterface::GetNetworkDistanceWithCore (this=0x1bccbf8, facade=warning: RTTI symbol not found for class 'std::_Sp_counted_ptr_inplace<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade, std::allocator<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade>, (__gnu_cxx::_Lock_policy)2>'
warning: RTTI symbol not found for class 'std::_Sp_counted_ptr_inplace<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade, std::allocator<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade>, (__gnu_cxx::_Lock_policy)2>'

Which is this: https://github.com/Project-OSRM/osrm-backend/blob/5.6/src/engine/routing_algorithms/routing_base.cpp#L430-L431

This trace is from OSRM 5.6.4.

This looks like it's a different issue to #3647, but as it also touches self-loops, I wonder if it's not a related problem.

[daniel-j-h]

@danpat this sounds related, no? #3429

[danpat]

@daniel-j-h possibly, except that is during path unpacking (after routing is complete), this one is happening during routing.

They're both related to self loops though, so fixing one might fix them both.

[oxidase]

Here is the analysis for another abort. The problem is that data is ephemeral and it is not possible to find out exact graph weights now, so i made an assumption about the edge that could potentially lead to the abort.

The input phantom nodes at are

source_phantom = @0x7f8c080b82d0: {forward_segment_id = {id = 12090888, enabled = 1}, reverse_segment_id = {id = 12090890, enabled = 0}, name_id = 942284, forward_weight = 585, reverse_weight = 109,
  forward_weight_offset = 0, reverse_weight_offset = 0, forward_duration = 585, reverse_duration = 109, forward_duration_offset = 0, reverse_duration_offset = 0, packed_geometry_id = 6897232, component = {
    id = 11385, is_tiny = 0}, location = {lon = {__value = -119215129}, lat = {__value = 34282801}}, input_location = {lon = {__value = -119215127}, lat = {__value = 34282801}}, fwd_segment_position = 0,
  forward_travel_mode = 1 '\001', backward_travel_mode = 1 '\001'}
target_phantom = @0x7f8c081d6910: {forward_segment_id = {id = 12090888, enabled = 1}, reverse_segment_id = {id = 12090890, enabled = 1}, name_id = 942284, forward_weight = 694, reverse_weight = 0,
  forward_weight_offset = 0, reverse_weight_offset = 0, forward_duration = 694, reverse_duration = 0, forward_duration_offset = 0, reverse_duration_offset = 0, packed_geometry_id = 6897232, component = {
    id = 11385, is_tiny = 0}, location = {lon = {__value = -119215142}, lat = {__value = 34282854}}, input_location = {lon = {__value = -119215172}, lat = {__value = 34282852}}, fwd_segment_position = 0,
  forward_travel_mode = 1 '\001', backward_travel_mode = 1 '\001'}

The abort happened at with the following state of the stack

this = 0x36c2158
facade = warning: RTTI symbol not found for class 'std::_Sp_counted_ptr_inplace<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade, std::allocator<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade>, (__gnu_cxx::_Lock_policy)2>'
warning: RTTI symbol not found for class 'std::_Sp_counted_ptr_inplace<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade, std::allocator<osrm::engine::datafacade::ContiguousInternalMemoryDataFacade>, (__gnu_cxx::_Lock_policy)2>'
std::shared_ptr (count 5, weak 0) 0x7f8628001340
forward_heap = @0x7f8c080033d0: {inserted_nodes = std::vector of length 22, capacity 128 = {{node = 12090888, key = 0, weight = -585, data = {parent = 12090888}}, {node = 12090887, key = 0, weight = 115, 
      data = {parent = 12090888}}, {node = 12090889, key = 0, weight = 167, data = {parent = 12090888}}, {node = 12090883, key = 0, weight = 296, data = {parent = 12090887}}, {node = 12090885, key = 0, 
      weight = 351, data = {parent = 12090887}}, {node = 12090886, key = 0, weight = 318, data = {parent = 12090887}}, {node = 12095820, key = 0, weight = 610, data = {parent = 12090889}}, {node = 12090872, 
      key = 0, weight = 1178, data = {parent = 12090883}}, {node = 12090873, key = 0, weight = 1146, data = {parent = 12090883}}, {node = 12090881, key = 0, weight = 1647, data = {parent = 12090883}}, {
      node = 12123274, key = 0, weight = 851, data = {parent = 12090883}}, {node = 12123276, key = 0, weight = 903, data = {parent = 12090883}}, {node = 12116540, key = 0, weight = 802, data = {
        parent = 12095820}}, {node = 12116541, key = 0, weight = 750, data = {parent = 12095820}}, {node = 12106087, key = 0, weight = 1599, data = {parent = 12090885}}, {node = 12116525, key = 0, 
      weight = 771, data = {parent = 12090885}}, {node = 12116537, key = 0, weight = 547, data = {parent = 12090885}}, {node = 12124565, key = 0, weight = 866, data = {parent = 12090885}}, {node = 12124566, 
      key = 0, weight = 850, data = {parent = 12090885}}, {node = 78842882, key = 0, weight = 1013, data = {parent = 12116537}}, {node = 78842883, key = 0, weight = 993, data = {parent = 12116537}}, {
      node = 12116539, key = 0, weight = 771, data = {parent = 12095820}}}, heap = std::vector of length 1, capacity 64 = {{index = 0, weight = -2147483648}}, node_index = {
    nodes = std::unordered_map with 22 elements = {[12116539] = 21, [78842883] = 20, [78842882] = 19, [12124566] = 18, [12124565] = 17, [12116537] = 16, [12116525] = 15, [12106087] = 14, [12116541] = 13, 
      [12116540] = 12, [12123276] = 11, [12123274] = 10, [12090881] = 9, [12090873] = 8, [12090872] = 7, [12095820] = 6, [12090886] = 5, [12090885] = 4, [12090883] = 3, [12090889] = 2, [12090887] = 1, 
      [12090888] = 0}}}
reverse_heap = @0x7f8c08000dd0: {inserted_nodes = std::vector of length 7, capacity 256 = {{node = 12090888, key = 0, weight = 487, data = {parent = 12090890}}, {node = 12090890, key = 0, weight = 0, data = {
        parent = 12090890}}, {node = 12090884, key = 0, weight = 668, data = {parent = 12090888}}, {node = 12095818, key = 0, weight = 858, data = {parent = 12090888}}, {node = 12090881, key = 0, weight = 797, 
      data = {parent = 12090884}}, {node = 12116535, key = 0, weight = 857, data = {parent = 12090884}}, {node = 12116539, key = 0, weight = 1424, data = {parent = 12090884}}}, 
  heap = std::vector of length 1, capacity 64 = {{index = 0, weight = -2147483648}}, node_index = {nodes = std::unordered_map with 7 elements = {[12116539] = 6, [12116535] = 5, [12090881] = 4, [12095818] = 3, 
      [12090884] = 2, [12090890] = 1, [12090888] = 0}}}
forward_core_heap = @0x7f8c08007680: {inserted_nodes = std::vector of length 0, capacity 32768, heap = std::vector of length 1, capacity 4096 = {{index = 0, weight = -2147483648}}, node_index = {
    nodes = std::unordered_map with 0 elements}}
reverse_core_heap = @0x7f8c080097a0: {inserted_nodes = std::vector of length 0, capacity 32768, heap = std::vector of length 1, capacity 2048 = {{index = 0, weight = -2147483648}}, node_index = {
    nodes = std::unordered_map with 0 elements}}
weight = @0x7f8c1bffdf48: 109
packed_leg = std::vector of length 0, capacity 0
force_loop_forward = false
force_loop_reverse = false
weight_upper_bound = 1017
middle = 12090888
forward_entry_points = std::vector of length 0, capacity 0
reverse_entry_points = std::vector of length 0, capacity 0
min_edge_offset = -585
STALLING_ENABLED = true
insertInCoreHeap = {<No data fields>}
min_core_edge_offset = 0
STALLING_DISABLED = false

From the heap data forward_heap.GetKey(middle) + reverse_heap.GetKey(middle)=-585+487=-98 and weight=109 but reverse_heap.GetData(middle).parent = 12090890 and not equal to the expected 12090888 that causes the abort.

This can happen with the following steps:

1. Heaps initialized as
   forward_heap={ {12090888, -585, 12090888} },
   reverse_heap={ {12090890, 0, 12090890}, {12090888, 694, 12090888}}
2. At middle=2147483647 and weight=1017
3. In the first RoutingStep call for forward_heap
   a) reverse_heap.WasInserted(node)=true
   b) new_weight=-585+694=109
   c) force_loop_forward=false, force_loop_reverse=false, new_weight=109
   d) middle_node_id=12090888, upper_bound=109
4. In the first RoutingStep call for reverse_heap
   a) Node 12090890 has a backward edge to 12090888 with weight = 487, so
   to_weight=0+487
   b) forward_heap.WasInserted(to)=true
   c) Heap contains inconsistent data starting from reverse_heap={ {12090890, 0, 12090890}, {12090888, 487, 12090890}}

EDIT: it is not really possible to reproduce the issue without data, but there are two possibilities:

• the edge assumption is correct, so assertion must be adjusted
• the edge assumption is incorrect than probably there is an issue in the edge weight update

[miccolis]

Is this still a concern as we're considering deprecating CoreCH?

[danpat]

Agreed, I think we can let this go and assume it will disappear once CoreCH is gone. Closing as WONTFIX.