Created
August 8, 2019 06:12
-
-
Save rustyrussell/3c752686991fb73ce256eefabee2ee2a to your computer and use it in GitHub Desktop.
Revisions
-
rustyrussell created this gist
Aug 8, 2019 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,356 @@ 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); }