askrene: getroutes makes 28 solver runs when no route fits maxfee (11 before #9627) #9726

The retry loop around the solver in linear_routes() takes more steps since #9627 (commit "askrene: mcf: introduce cost dials", also in v26.06.10); this is about that loop, not the solver. When no route fits maxfee, getroutes now makes 28 solver runs before it fails; it made at most 11 before. The 17 added runs are at mu above 0.95, where a run is slower and the fee found changes little or rises.

1. The loop starts with mu = 0.01 and doubles it at each "fee greater than max" retry, until mu >= 1 - 1e-6.
2. After renormalize_dials() the odds mu / (1 - mu) double per retry. The limit is reached after 27 retries, so 28 solver runs. The previous ladder (1, 10, 20 ... 100) made at most 11.
3. 11 of the 28 runs are below mu 0.95. The other 17 go from 0.954 to 0.9999993.
4. In those 17 runs the fee found changes little or rises, and a run takes up to three times as long on the test gossip snapshot, about ten times as long on a mainnet node.
5. The call fails with "Could not find route without excessive cost" as before, only later, or it reaches askrene-timeout first and fails with "linear_routes: timed out after deadline".

Effect on a mainnet node that rebalances with a tight fee budget, v26.06.10 against v26.06.9: the median rebalance request takes 26 s against 5 s, and 12.8% of them end in the timeout (askrene-timeout 30); none did before.

Who is affected: callers with a tight fee budget, such as a rebalancer. A call that can meet its budget stops at the first mu that fits and never reaches these runs. With xpay's default budget of 1% that is the normal case.

Suggestion: fewer runs above mu 0.95, by larger steps in that range or a lower cut-off. A cut-off at 0.99 gives 15 runs.

Workaround: none. A lower askrene-timeout limits the time; the call then ends in the timeout error.

Related: #9627, #9723 (touches the same loop).

Measured on master 8a0a56a with tests/data/gossip-store-2026-02-03.compressed in the test_real_data setup: getroutes of 1,000,000 sat to each of the first 20 node ids, maxfee_msat 10000 (10 ppm), one call at a time. 19 calls fail on the fee, each after 28 runs. The median call takes 3.6 s, and 2.8 s of that are the 17 runs above 0.95.

A cut-off at 0.99 on the same calls: the first 15 runs take a median 1.3 s. In 13 of the 19 calls no later run finds a lower fee. In 5 calls a later run finds one 0.3% to 7% lower, in one call 39% lower.

The same with 100,000 sat (maxfee_msat 1000): 19 calls fail after 28 runs each, median 1.6 s. The runs do not get slower (0.06 s each). From run 11 on the median fee stays within 8% of the lowest. A run after the first 15 finds a lower fee in 15 of the 19 calls, by a median 5%, at most 31%.

One call on the mainnet node: the runs up to mu 0.954 took about 0.1 s each, the runs from 0.976 on took 0.7 to 2.1 s each. The fee stayed between 875k and 1,059k msat in those runs, against a limit of 829k msat.