dijkstra-hard-limit.patch

diff --git a/gossipd/gossip_wire.csv b/gossipd/gossip_wire.csv
index 63392d87b..7b36f9831 100644
--- a/gossipd/gossip_wire.csv
+++ b/gossipd/gossip_wire.csv
@@ -37,6 +37,7 @@ msgdata,gossip_getroute_request,fuzz,double,
 msgdata,gossip_getroute_request,num_excluded,u16,
 msgdata,gossip_getroute_request,excluded,short_channel_id_dir,num_excluded
 msgdata,gossip_getroute_request,max_hops,u32,
+msgdata,gossip_getroute_request,hard_limit,bool,
 
 msgtype,gossip_getroute_reply,3106
 msgdata,gossip_getroute_reply,num_hops,u16,
diff --git a/gossipd/gossipd.c b/gossipd/gossipd.c
index 89e675b15..7cd42694e 100644
--- a/gossipd/gossipd.c
+++ b/gossipd/gossipd.c
@@ -2149,6 +2149,7 @@ static struct io_plan *getroute_req(struct io_conn *conn, struct daemon *daemon,
 	struct route_hop *hops;
 	double fuzz;
 	struct short_channel_id_dir *excluded;
+	bool hard_limit;
 
 	/* To choose between variations, we need to know how much we're
 	 * sending (eliminates too-small channels, and also effects the fees
@@ -2166,7 +2167,8 @@ static struct io_plan *getroute_req(struct io_conn *conn, struct daemon *daemon,
 					      &msat, &riskfactor_by_million,
 					      &final_cltv, &fuzz,
 					      &excluded,
-					      &max_hops))
+					      &max_hops,
+					      &hard_limit))
 		master_badmsg(WIRE_GOSSIP_GETROUTE_REQUEST, msg);
 
 	status_trace("Trying to find a route from %s to %s for %s",
@@ -2178,7 +2180,8 @@ static struct io_plan *getroute_req(struct io_conn *conn, struct daemon *daemon,
 	/* routing.c does all the hard work; can return NULL. */
 	hops = get_route(tmpctx, daemon->rstate, source, &destination,
 			 msat, riskfactor_by_million / 1000000.0, final_cltv,
-			 fuzz, pseudorand_u64(), excluded, max_hops);
+			 fuzz, pseudorand_u64(), excluded, max_hops,
+			 hard_limit);
 
 	out = towire_gossip_getroute_reply(NULL, hops);
 	daemon_conn_send(daemon->master, take(out));
diff --git a/gossipd/routing.c b/gossipd/routing.c
index 80dc82779..09f97ae0e 100644
--- a/gossipd/routing.c
+++ b/gossipd/routing.c
@@ -691,7 +691,8 @@ static void adjust_unvisited(struct node *node,
 			     struct amount_msat cost_before,
 			     struct amount_msat total,
 			     struct amount_msat risk,
-			     struct amount_msat cost_after)
+			     struct amount_msat cost_after,
+			     u32 num_hops)
 {
 	struct node **arr;
 
@@ -702,6 +703,7 @@ static void adjust_unvisited(struct node *node,
 	/* Update node */
 	node->dijkstra.total = total;
 	node->dijkstra.risk = risk;
+	node->dijkstra.num_hops = num_hops;
 
 	SUPERVERBOSE("%s now cost %s",
 		     type_to_string(tmpctx, struct node_id, &node->id),
@@ -754,11 +756,15 @@ static void update_unvisited_neighbors(struct routing_state *rstate,
 				       double fuzz,
 				       const struct siphash_seed *base_seed,
 				       struct unvisited *unvisited,
-				       costfn_t *costfn)
+				       costfn_t *costfn,
+				       u32 hard_max_hops)
 {
 	struct chan_map_iter i;
 	struct chan *chan;
 
+	if (cur->dijkstra.num_hops == hard_max_hops)
+		return;
+
 	/* Consider all neighbors */
 	for (chan = first_chan(cur, &i); chan; chan = next_chan(cur, &i)) {
 		struct amount_msat total, risk, cost_before, cost_after;
@@ -811,7 +817,8 @@ static void update_unvisited_neighbors(struct routing_state *rstate,
 				     type_to_string(tmpctx, struct amount_msat,
 						    &risk));
 			adjust_unvisited(peer, unvisited,
-					 cost_before, total, risk, cost_after);
+					 cost_before, total, risk, cost_after,
+					 cur->dijkstra.num_hops + 1);
 		}
 	}
 }
@@ -839,14 +846,16 @@ static void dijkstra(struct routing_state *rstate,
 		     u64 riskbias,
 		     double fuzz, const struct siphash_seed *base_seed,
 		     struct unvisited *unvisited,
-		     costfn_t *costfn)
+		     costfn_t *costfn,
+		     u32 hard_max_hops)
 {
 	struct node *cur;
 
 	while ((cur = first_unvisited(unvisited)) != NULL) {
 		update_unvisited_neighbors(rstate, cur, me,
 					   riskfactor, riskbias,
-					   fuzz, base_seed, unvisited, costfn);
+					   fuzz, base_seed, unvisited, costfn,
+					   hard_max_hops);
 		remove_unvisited(cur, unvisited, costfn);
 		if (cur == dst)
 			return;
@@ -975,6 +984,7 @@ static struct unvisited *dijkstra_prepare(const tal_t *ctx,
 	/* Mark start cost: place in unvisited map. */
 	src->dijkstra.total = msat;
 	src->dijkstra.risk = AMOUNT_MSAT(0);
+	src->dijkstra.num_hops = 0;
 	arr = tal_arr(unvisited, struct node *, 1);
 	arr[0] = src;
 	/* Adding 0 can never fail */
@@ -1037,7 +1047,7 @@ find_shorter_route(const tal_t *ctx, struct routing_state *rstate,
 		     type_to_string(tmpctx, struct node_id, &dst->id),
 		     type_to_string(tmpctx, struct node_id, &src->id));
 	dijkstra(rstate, dst, NULL, riskfactor, 1, fuzz, base_seed,
-		 unvisited, shortest_cost_function);
+		 unvisited, shortest_cost_function, -1U);
 	dijkstra_cleanup(unvisited);
 
 	/* This must succeed, since we found a route before */
@@ -1084,7 +1094,7 @@ find_shorter_route(const tal_t *ctx, struct routing_state *rstate,
 		unvisited = dijkstra_prepare(tmpctx, rstate, src, msat,
 					     normal_cost_function);
 		dijkstra(rstate, dst, me, riskfactor, riskbias, fuzz, base_seed,
-			 unvisited, normal_cost_function);
+			 unvisited, normal_cost_function, -1U);
 		dijkstra_cleanup(unvisited);
 
 		route = build_route(ctx, rstate, dst, src, me,
@@ -1127,7 +1137,7 @@ find_route(const tal_t *ctx, struct routing_state *rstate,
 	   struct amount_msat msat,
 	   double riskfactor,
 	   double fuzz, const struct siphash_seed *base_seed,
-	   size_t max_hops,
+	   size_t max_hops, size_t hard_max_hops,
 	   struct amount_msat *fee)
 {
 	struct node *src, *dst;
@@ -1164,7 +1174,7 @@ find_route(const tal_t *ctx, struct routing_state *rstate,
 	unvisited = dijkstra_prepare(tmpctx, rstate, src, msat,
 				     normal_cost_function);
 	dijkstra(rstate, dst, me, riskfactor, 1, fuzz, base_seed,
-		 unvisited, normal_cost_function);
+		 unvisited, normal_cost_function, hard_max_hops);
 	dijkstra_cleanup(unvisited);
 
 	route = build_route(ctx, rstate, dst, src, me, riskfactor, 1,
@@ -2302,7 +2312,7 @@ struct route_hop *get_route(const tal_t *ctx, struct routing_state *rstate,
 			    u32 final_cltv,
 			    double fuzz, u64 seed,
 			    const struct short_channel_id_dir *excluded,
-			    size_t max_hops)
+			    size_t max_hops, bool hard_limit)
 {
 	struct chan **route;
 	struct amount_msat total_amount;
@@ -2331,7 +2341,9 @@ struct route_hop *get_route(const tal_t *ctx, struct routing_state *rstate,
 
 	route = find_route(ctx, rstate, source, destination, msat,
 			   riskfactor / BLOCKS_PER_YEAR / 100,
-			   fuzz, &base_seed, max_hops, &fee);
+			   fuzz, &base_seed,
+			   max_hops, hard_limit ? max_hops : -1U,
+			   &fee);
 
 	/* Now restore the capacity. */
 	/* Restoring is done in reverse order, in order to properly
diff --git a/gossipd/routing.h b/gossipd/routing.h
index b886290f0..8a4e04d04 100644
--- a/gossipd/routing.h
+++ b/gossipd/routing.h
@@ -121,6 +121,8 @@ struct node {
 		struct amount_msat total;
 		/* Total risk premium of this route. */
 		struct amount_msat risk;
+		/* Distance */
+		u32 num_hops;
 	} dijkstra;
 };
 
@@ -336,7 +338,7 @@ struct route_hop *get_route(const tal_t *ctx, struct routing_state *rstate,
 			    double fuzz,
 			    u64 seed,
 			    const struct short_channel_id_dir *excluded,
-			    size_t max_hops);
+			    size_t max_hops, bool hard_limit);
 /* Disable channel(s) based on the given routing failure. */
 void routing_failure(struct routing_state *rstate,
 		     const struct node_id *erring_node,
diff --git a/gossipd/test/run-bench-find_route.c b/gossipd/test/run-bench-find_route.c
index 132d0d895..b589bb2b6 100644
--- a/gossipd/test/run-bench-find_route.c
+++ b/gossipd/test/run-bench-find_route.c
@@ -242,7 +242,7 @@ int main(int argc, char *argv[])
 				   (struct amount_msat){pseudorand(100000)},
 				   riskfactor,
 				   0.75, &base_seed,
-				   ROUTING_MAX_HOPS,
+				   ROUTING_MAX_HOPS, false,
 				   &fee);
 		num_hops = tal_count(route);
 		assert(num_hops < ARRAY_SIZE(route_lengths));
diff --git a/gossipd/test/run-find_route-specific.c b/gossipd/test/run-find_route-specific.c
index c0491de45..2a7cf499b 100644
--- a/gossipd/test/run-find_route-specific.c
+++ b/gossipd/test/run-find_route-specific.c
@@ -199,7 +199,7 @@ int main(void)
 	nc->bcast.timestamp = 1504064344;
 
 	route = find_route(tmpctx, rstate, &a, &c, AMOUNT_MSAT(100000), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(route);
 	assert(tal_count(route) == 2);
 	assert(channel_is_between(route[0], &a, &b));
@@ -208,19 +208,19 @@ int main(void)
 
 	/* We should not be able to find a route that exceeds our own capacity */
 	route = find_route(tmpctx, rstate, &a, &c, AMOUNT_MSAT(1000001), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(!route);
 
 	/* Now test with a query that exceeds the channel capacity after adding
 	 * some fees */
 	route = find_route(tmpctx, rstate, &a, &c, AMOUNT_MSAT(999999), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(!route);
 
 	/* This should fail to return a route because it is smaller than these
 	 * htlc_minimum_msat on the last channel. */
 	route = find_route(tmpctx, rstate, &a, &c, AMOUNT_MSAT(1), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(!route);
 
 	/* {'active': True, 'short_id': '6990:2:1/0', 'fee_per_kw': 10, 'delay': 5, 'message_flags': 1, 'htlc_maximum_msat': 500000, 'htlc_minimum_msat': 100, 'channel_flags': 0, 'destination': '02cca6c5c966fcf61d121e3a70e03a1cd9eeeea024b26ea666ce974d43b242e636', 'source': '03c173897878996287a8100469f954dd820fcd8941daed91c327f168f3329be0bf', 'last_update': 1504064344}, */
@@ -236,13 +236,13 @@ int main(void)
 
 	/* This should route correctly at the max_msat level */
 	route = find_route(tmpctx, rstate, &a, &d, AMOUNT_MSAT(500000), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(route);
 
 	/* This should fail to return a route because it's larger than the
 	 * htlc_maximum_msat on the last channel. */
 	route = find_route(tmpctx, rstate, &a, &d, AMOUNT_MSAT(500001), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(!route);
 
 	tal_free(tmpctx);
diff --git a/gossipd/test/run-find_route.c b/gossipd/test/run-find_route.c
index 1f8fb5d4f..e526ddd1c 100644
--- a/gossipd/test/run-find_route.c
+++ b/gossipd/test/run-find_route.c
@@ -204,7 +204,7 @@ int main(void)
 	add_connection(rstate, &a, &b, 1, 1, 1);
 
 	route = find_route(tmpctx, rstate, &a, &b, AMOUNT_MSAT(1000), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(route);
 	assert(tal_count(route) == 1);
 	assert(amount_msat_eq(fee, AMOUNT_MSAT(0)));
@@ -220,7 +220,7 @@ int main(void)
 	add_connection(rstate, &b, &c, 1, 1, 1);
 
 	route = find_route(tmpctx, rstate, &a, &c, AMOUNT_MSAT(1000), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(route);
 	assert(tal_count(route) == 2);
 	assert(amount_msat_eq(fee, AMOUNT_MSAT(1)));
@@ -236,7 +236,7 @@ int main(void)
 
 	/* Will go via D for small amounts. */
 	route = find_route(tmpctx, rstate, &a, &c, AMOUNT_MSAT(1000), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(route);
 	assert(tal_count(route) == 2);
 	assert(channel_is_between(route[0], &a, &d));
@@ -245,7 +245,7 @@ int main(void)
 
 	/* Will go via B for large amounts. */
 	route = find_route(tmpctx, rstate, &a, &c, AMOUNT_MSAT(3000000), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(route);
 	assert(tal_count(route) == 2);
 	assert(channel_is_between(route[0], &a, &b));
@@ -255,7 +255,7 @@ int main(void)
 	/* Make B->C inactive, force it back via D */
 	get_connection(rstate, &b, &c)->channel_flags |= ROUTING_FLAGS_DISABLED;
 	route = find_route(tmpctx, rstate, &a, &c, AMOUNT_MSAT(3000000), riskfactor, 0.0, NULL,
-			   ROUTING_MAX_HOPS, &fee);
+			   ROUTING_MAX_HOPS, false, &fee);
 	assert(route);
 	assert(tal_count(route) == 2);
 	assert(channel_is_between(route[0], &a, &d));
diff --git a/gossipd/test/run-overlong.c b/gossipd/test/run-overlong.c
index 984d77bf8..a88dcaeac 100644
--- a/gossipd/test/run-overlong.c
+++ b/gossipd/test/run-overlong.c
@@ -173,7 +173,7 @@ int main(void)
 
 		route = find_route(tmpctx, rstate, &ids[0], &ids[NUM_NODES-1],
 				   AMOUNT_MSAT(1000), 0, 0.0, NULL,
-				   i, &fee);
+				   i, false, &fee);
 		assert(route);
 		assert(tal_count(route) == i);
 		if (i != ROUTING_MAX_HOPS)
diff --git a/lightningd/gossip_control.c b/lightningd/gossip_control.c
index 8da48407e..cdf0421e8 100644
--- a/lightningd/gossip_control.c
+++ b/lightningd/gossip_control.c
@@ -290,6 +290,7 @@ static struct command_result *json_getroute(struct command *cmd,
 	double *riskfactor;
 	struct short_channel_id_dir *excluded;
 	u32 *max_hops;
+	bool *hard_limit;
 
 	/* Higher fuzz means that some high-fee paths can be discounted
 	 * for an even larger value, increasing the scope for route
@@ -308,6 +309,8 @@ static struct command_result *json_getroute(struct command *cmd,
 		   p_opt("exclude", param_array, &excludetok),
 		   p_opt_def("maxhops", param_number, &max_hops,
 			     ROUTING_MAX_HOPS),
+		   p_opt_def("hardhoplimit", param_bool, &hard_limit,
+			     false),
 		   NULL))
 		return command_param_failed();
 
@@ -342,7 +345,8 @@ static struct command_result *json_getroute(struct command *cmd,
 						 *riskfactor * 1000000.0,
 						 *cltv, fuzz,
 						 excluded,
-						 *max_hops);
+						 *max_hops,
+						 *hard_limit);
 	subd_req(ld->gossip, ld->gossip, req, -1, 0, json_getroute_reply, cmd);
 	return command_still_pending(cmd);
 }

Increases struct node size by 4 bytes at least, potentially more if we are uncareful about alignment on 64-bit systems, due to new node->dijkstra.num_hops.