trace_attributes segfaults on ~1 MB thread stacks: unbounded recursion in expand_from_node #6294

expand_from_node, a file-local function in src/thor/route_matcher.cc, recurses once per matched edge (route_matcher.cc:249) and once per hierarchy transition (route_matcher.cc:277). Nothing bounds the depth. Recursion depth is proportional to the number of edges in the shape being matched, so a trace_route / trace_attributes request with shape_match=edge_walk needs a thread stack proportional to the length of the input shape. About 1,300 edges overflows a 1 MB stack and the process dies with SIGSEGV.

Why the server never sees it

valhalla_service worker threads start with 8 MB, which covers any shape a normal client sends. In-process embedders get much less: JNI worker threads on Android and Dart isolate workers are around 1 MB, and non-main pthreads on Darwin default to 512 KB. The same request against the same tiles works over HTTP and segfaults when the library is called directly from a worker thread.

This came in downstream as Rallista/valhalla-mobile#89, which has the full backtrace. They shipped a workaround (actor actions now run on a dedicated thread with a 16 MB stack, Rallista/valhalla-mobile#110) and asked us to report the root cause here.

Reproduction

1. Truck route from Milan (45.4642, 9.19) to Verona (45.4384, 10.9916) with costing_options.truck.top_speed=88. The alternative is a non-motorway route of about 1,300 edges over 162 km.
2. Pass the returned shape to trace_attributes with shape_match=edge_walk and the same costing.
3. Make the call through actor_t on a thread with a 1 MB stack. SIGSEGV.

The same call on an 8 MB stack thread succeeds, and a 475-edge shape does not crash at 1 MB. Depth scales with edge count, so the threshold depends on the caller's stack size.

Observed on 3.8.2 (Linux aarch64, gcc 13.3, tiles built from a Northern Italy extract).

Still present on master: route_matcher.cc is byte-for-byte identical between 3.8.2 and current master, and neither #6034 nor #6047, the only changes since 3.6.3, touches the recursion.

Backtrace

One return address repeated down the stack:

#0  valhalla::baldr::GraphReader::GetGraphTile(valhalla::baldr::GraphId const&)
#1  0x...f1a4 in ?? ()
#2  0x...f90c in ?? ()
#3  0x...f90c in ?? ()   <- same frame, repeating
#4..#N 0x...f90c

Proposed fix

Convert expand_from_node to an iteration over an explicit stack. The backtracking semantics have to be preserved exactly: the pop of path_infos and the elapsed unwind on a failed branch, the followed_edges bookkeeping, and the expansion of transitions.

For regression coverage, a gurka map with a long generated chain of edges (~1,500) traced from a thread created with a small stack should be enough. No large fixture needed.