1 #include "config.h"
2 #include <assert.h>
3 #include <ccan/err/err.h>
4 #include <ccan/opt/opt.h>
5 #include <ccan/time/time.h>
6 #include <common/dijkstra.h>
7 #include <common/gossmap.h>
8 #include <common/route.h>
9 #include <common/type_to_string.h>
10 #include <devtools/clean_topo.h>
11 #include <inttypes.h>
12 #include <stdio.h>
13
14 /* We ignore capacity constraints */
channel_usable(const struct gossmap * map,const struct gossmap_chan * c,int dir,struct amount_msat amount,void * unused)15 static bool channel_usable(const struct gossmap *map,
16 const struct gossmap_chan *c,
17 int dir,
18 struct amount_msat amount,
19 void *unused)
20 {
21 if (!gossmap_chan_set(c, dir))
22 return false;
23 if (!c->half[dir].enabled)
24 return false;
25 return true;
26 }
27
28 /* Note: dijkstra() sets dir to the neighbor side; i.e. c->half[dir].node_idx is the
29 * neighbor. */
channel_usable_to_excl(const struct gossmap * map,const struct gossmap_chan * c,int dir,struct amount_msat amount,struct gossmap_node * excl)30 static bool channel_usable_to_excl(const struct gossmap *map,
31 const struct gossmap_chan *c,
32 int dir,
33 struct amount_msat amount,
34 struct gossmap_node *excl)
35 {
36 if (!channel_usable(map, c, dir, amount, NULL))
37 return false;
38
39 /* Don't go via excl. */
40 if (c->half[dir].nodeidx == gossmap_node_idx(map, excl))
41 return false;
42 return true;
43 }
44
45 /* What nodes can reach n without going through exclude? */
count_possible_sources(const struct gossmap * map,struct gossmap_node * n,struct gossmap_node * exclude,bool is_last_node)46 static size_t count_possible_sources(const struct gossmap *map,
47 struct gossmap_node *n,
48 struct gossmap_node *exclude,
49 bool is_last_node)
50 {
51 const struct dijkstra *dij;
52 size_t distance_budget, num;
53
54 dij = dijkstra(tmpctx, map, n, AMOUNT_MSAT(0), 0,
55 channel_usable_to_excl, route_score_shorter, exclude);
56
57 if (is_last_node)
58 distance_budget = ROUTING_MAX_HOPS - 1;
59 else
60 distance_budget = ROUTING_MAX_HOPS - 2;
61
62 assert(dijkstra_distance(dij, gossmap_node_idx(map, n)) == 0);
63 assert(dijkstra_distance(dij, gossmap_node_idx(map, exclude)) == UINT_MAX);
64
65 num = 0;
66 for (n = gossmap_first_node(map); n; n = gossmap_next_node(map, n)) {
67 if (dijkstra_distance(dij, gossmap_node_idx(map, n)) <= distance_budget)
68 num++;
69 }
70 return num;
71 }
72
73 /* Note: dijkstra() sets dir to the neighbor side; i.e. c->half[dir].node_idx is the
74 * neighbor. */
channel_usable_from_excl(const struct gossmap * map,const struct gossmap_chan * c,int dir,struct amount_msat amount,struct gossmap_node * excl)75 static bool channel_usable_from_excl(const struct gossmap *map,
76 const struct gossmap_chan *c,
77 int dir,
78 struct amount_msat amount,
79 struct gossmap_node *excl)
80 {
81 if (!channel_usable(map, c, !dir, amount, NULL))
82 return false;
83
84 /* Don't go via excl. */
85 if (c->half[dir].nodeidx == gossmap_node_idx(map, excl))
86 return false;
87 return true;
88 }
89
memcount(const void * mem,size_t len,char c)90 static size_t memcount(const void *mem, size_t len, char c)
91 {
92 size_t count = 0;
93 for (size_t i = 0; i < len; i++) {
94 if (((char *)mem)[i] == c)
95 count++;
96 }
97 return count;
98 }
99
visit(const struct gossmap * map,struct gossmap_node * n,struct gossmap_node * exclude,bool * visited)100 static void visit(const struct gossmap *map,
101 struct gossmap_node *n,
102 struct gossmap_node *exclude,
103 bool *visited)
104 {
105 if (n == exclude)
106 return;
107 if (visited[gossmap_node_idx(map, n)])
108 return;
109 visited[gossmap_node_idx(map, n)] = true;
110
111 for (size_t i = 0; i < n->num_chans; i++) {
112 int dir;
113 struct gossmap_chan *c;
114 c = gossmap_nth_chan(map, n, i, &dir);
115
116 if (!channel_usable(map, c, dir, AMOUNT_MSAT(0), NULL))
117 continue;
118 visit(map, gossmap_nth_node(map, c, !dir), exclude, visited);
119 }
120 }
121
122 /* What nodes can n reach without going through exclude? */
count_possible_destinations(const struct gossmap * map,struct gossmap_node * start,struct gossmap_node * exclude,bool is_first_node)123 static size_t count_possible_destinations(const struct gossmap *map,
124 struct gossmap_node *start,
125 struct gossmap_node *exclude,
126 bool is_first_node)
127 {
128 const struct dijkstra *dij;
129 size_t distance_budget, num;
130
131 dij = dijkstra(tmpctx, map, start, AMOUNT_MSAT(0), 0,
132 channel_usable_from_excl, route_score_shorter, exclude);
133
134 if (is_first_node)
135 distance_budget = ROUTING_MAX_HOPS - 1;
136 else
137 distance_budget = ROUTING_MAX_HOPS - 2;
138
139 assert(dijkstra_distance(dij, gossmap_node_idx(map, start)) == 0);
140 assert(dijkstra_distance(dij, gossmap_node_idx(map, exclude)) == UINT_MAX);
141
142 num = 0;
143 for (struct gossmap_node *n = gossmap_first_node(map);
144 n;
145 n = gossmap_next_node(map, n)) {
146 if (dijkstra_distance(dij, gossmap_node_idx(map, n)) <= distance_budget)
147 num++;
148 #if 0
149 else
150 printf("Can't reach %s (%u) if we exclude %s\n",
151 type_to_string(tmpctx, struct node_id,
152 gossmap_node_get_id(map, n)),
153 dijkstra_distance(dij, gossmap_node_idx(map, n)),
154 type_to_string(tmpctx, struct node_id,
155 gossmap_node_get_id(map, exclude)));
156 #endif
157 }
158
159 /* Now double-check with flood-fill. */
160 bool *visited = tal_arrz(tmpctx, bool, gossmap_max_node_idx(map));
161 visit(map, start, exclude, visited);
162 assert(memcount(visited, tal_bytelen(visited), true) == num);
163 return num;
164 }
165
measure_least_cost(struct gossmap * map,struct gossmap_node * src,struct gossmap_node * dst)166 static bool measure_least_cost(struct gossmap *map,
167 struct gossmap_node *src,
168 struct gossmap_node *dst)
169 {
170 const struct dijkstra *dij;
171 u32 srcidx = gossmap_node_idx(map, src);
172 /* 10ksat, budget is 0.5% */
173 const struct amount_msat sent = AMOUNT_MSAT(10000000);
174 const struct amount_msat budget = amount_msat_div(sent, 200);
175 const u32 riskfactor = 0;
176 /* Max distance is 20 */
177 const u32 distance_budget = ROUTING_MAX_HOPS;
178 struct amount_msat maxcost, fee;
179 struct route_hop *path;
180 struct timemono tstart, tstop;
181 struct node_id srcid;
182
183 gossmap_node_get_id(map, src, &srcid);
184 printf("# src %s (%u channels)\n",
185 type_to_string(tmpctx, struct node_id, &srcid),
186 src->num_chans);
187
188 tstart = time_mono();
189 dij = dijkstra(tmpctx, map, dst,
190 sent, riskfactor, channel_usable,
191 route_score_cheaper, NULL);
192 tstop = time_mono();
193
194 printf("# Time to find path: %"PRIu64" usec\n",
195 time_to_usec(timemono_between(tstop, tstart)));
196
197 if (dijkstra_distance(dij, srcidx) > distance_budget) {
198 printf("failed (%s)\n",
199 dijkstra_distance(dij, srcidx) == UINT_MAX ? "unreachable" : "too far");
200 return false;
201 }
202 if (!amount_msat_add(&maxcost, sent, budget))
203 abort();
204
205 path = route_from_dijkstra(map, map, dij, src, sent, 0);
206
207 if (amount_msat_greater(path[0].amount, maxcost)) {
208 printf("failed (too expensive)\n");
209 return false;
210 }
211 printf("# path length %zu\n", tal_count(path));
212 if (!amount_msat_sub(&fee, path[0].amount, sent))
213 abort();
214 printf("# path fee %s\n",
215 type_to_string(tmpctx, struct amount_msat, &fee));
216
217 /* Count possible sources */
218 for (size_t i = 0; i < tal_count(path); i++) {
219 struct gossmap_node *prev, *cur;
220 struct gossmap_chan *c = gossmap_find_chan(map, &path[i].scid);
221
222 /* N+1th node is at end of Nth hop */
223 prev = gossmap_nth_node(map, c, path[i].direction);
224 cur = gossmap_nth_node(map, c, !path[i].direction);
225
226 printf("source set size node %zu/%zu: %zu\n",
227 i+1, tal_count(path),
228 count_possible_sources(map, prev, cur, cur == dst));
229 }
230
231 /* Count possible destinations. */
232 for (size_t i = 0; i < tal_count(path); i++) {
233 struct gossmap_node *cur, *next;
234 struct gossmap_chan *c = gossmap_find_chan(map, &path[i].scid);
235
236 /* N+1th node is at end of Nth hop */
237 cur = gossmap_nth_node(map, c, path[i].direction);
238 next = gossmap_nth_node(map, c, !path[i].direction);
239
240 printf("destination set size node %zu/%zu: %zu\n",
241 i, tal_count(path),
242 count_possible_destinations(map, next, cur, cur == src));
243 }
244 return true;
245 }
246
main(int argc,char * argv[])247 int main(int argc, char *argv[])
248 {
249 struct timemono tstart, tstop;
250 struct gossmap_node *n, *dst;
251 struct gossmap *map;
252 struct node_id dstid;
253 bool no_singles = false;
254
255 setup_locale();
256 setup_tmpctx();
257
258 opt_register_noarg("--no-single-sources", opt_set_bool, &no_singles,
259 "Eliminate single-channel nodes");
260 opt_register_noarg("-h|--help", opt_usage_and_exit,
261 "<gossipstore> <srcid>|all <dstid>\n"
262 "A topology test program.",
263 "Get usage information");
264 opt_parse(&argc, argv, opt_log_stderr_exit);
265 if (argc != 4)
266 opt_usage_exit_fail("Expect 3 arguments");
267
268 tstart = time_mono();
269 map = gossmap_load(NULL, argv[1], NULL);
270 if (!map)
271 err(1, "Loading gossip store %s", argv[1]);
272 tstop = time_mono();
273
274 printf("# Time to load: %"PRIu64" msec\n",
275 time_to_msec(timemono_between(tstop, tstart)));
276
277 clean_topo(map, no_singles);
278 printf("# Reduced to %zu nodes and %zu channels\n",
279 gossmap_num_nodes(map), gossmap_num_chans(map));
280
281 if (!node_id_from_hexstr(argv[3], strlen(argv[3]), &dstid))
282 errx(1, "Bad dstid");
283 dst = gossmap_find_node(map, &dstid);
284 if (!dst)
285 errx(1, "Unknown destination node '%s'", argv[3]);
286
287 if (streq(argv[2], "all")) {
288 for (n = gossmap_first_node(map);
289 n;
290 n = gossmap_next_node(map, n)) {
291 measure_least_cost(map, n, dst);
292 clean_tmpctx();
293 }
294 } else {
295 struct node_id srcid;
296 if (!node_id_from_hexstr(argv[2], strlen(argv[2]), &srcid))
297 errx(1, "Bad srcid");
298 n = gossmap_find_node(map, &srcid);
299 if (!n)
300 errx(1, "Unknown source node '%s'", argv[2]);
301 if (!measure_least_cost(map, n, dst))
302 exit(1);
303 }
304
305 tal_free(map);
306 }
307