Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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);
}
@ZmnSCPxj

This comment has been minimized.

Copy link

ZmnSCPxj commented Aug 8, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.