1 /*
2 * scamper_tracelb.c
3 *
4 * $Id: scamper_tracelb.c,v 1.60 2020/04/02 06:45:02 mjl Exp $
5 *
6 * Copyright (C) 2008-2010 The University of Waikato
7 * Copyright (C) 2012 The Regents of the University of California
8 * Copyright (C) 2018-2019 Matthew Luckie
9 * Author: Matthew Luckie
10 *
11 * Load-balancer traceroute technique authored by
12 * Brice Augustin, Timur Friedman, Renata Teixeira; "Measuring Load-balanced
13 * Paths in the Internet", in Proc. Internet Measurement Conference 2007.
14 *
15 * This program is free software; you can redistribute it and/or modify
16 * it under the terms of the GNU General Public License as published by
17 * the Free Software Foundation, version 2.
18 *
19 * This program is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License
25 * along with this program; if not, write to the Free Software
26 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
27 *
28 */
29
30 #ifdef HAVE_CONFIG_H
31 #include "config.h"
32 #endif
33 #include "internal.h"
34
35 #include "scamper_addr.h"
36 #include "scamper_list.h"
37 #include "scamper_icmpext.h"
38 #include "scamper_tracelb.h"
39 #include "utils.h"
40
41 typedef struct tracelb_fwdpathc
42 {
43 int pathc;
44 int pathcc;
45 int loop;
46 } tracelb_fwdpathc_t;
47
48 void
scamper_tracelb_probeset_summary_free(scamper_tracelb_probeset_summary_t * sum)49 scamper_tracelb_probeset_summary_free(scamper_tracelb_probeset_summary_t *sum)
50 {
51 int i;
52 if(sum->addrs != NULL)
53 {
54 for(i=0; i<sum->addrc; i++)
55 if(sum->addrs[i] != NULL)
56 scamper_addr_free(sum->addrs[i]);
57 free(sum->addrs);
58 }
59 free(sum);
60 return;
61 }
62
63 scamper_tracelb_probeset_summary_t *
scamper_tracelb_probeset_summary_alloc(scamper_tracelb_probeset_t * set)64 scamper_tracelb_probeset_summary_alloc(scamper_tracelb_probeset_t *set)
65 {
66 scamper_tracelb_probeset_summary_t *sum = NULL;
67 scamper_tracelb_probe_t *probe;
68 scamper_addr_t *addr;
69 uint16_t flowid, j;
70 int i, x;
71
72 if((sum = malloc_zero(sizeof(scamper_tracelb_probeset_summary_t))) == NULL)
73 goto err;
74
75 if(set->probec == 0)
76 return sum;
77
78 flowid = set->probes[0]->flowid;
79 x = 0;
80 for(i=0; i<=set->probec; i++)
81 {
82 if(i == set->probec)
83 {
84 if(x == 0)
85 sum->nullc++;
86 break;
87 }
88
89 probe = set->probes[i];
90 if(probe->flowid != flowid)
91 {
92 /*
93 * if a unique flowid had no response (even with multiple
94 * attempts) then make a note of that.
95 */
96 if(x == 0)
97 sum->nullc++;
98
99 flowid = probe->flowid;
100 x = 0;
101 }
102
103 if(probe->rxc > 0)
104 {
105 for(j=0; j<probe->rxc; j++)
106 {
107 addr = probe->rxs[j]->reply_from;
108 if(array_find((void **)sum->addrs, sum->addrc, addr,
109 (array_cmp_t)scamper_addr_cmp) != NULL)
110 continue;
111 if(array_insert((void ***)&sum->addrs, &sum->addrc,
112 addr, (array_cmp_t)scamper_addr_cmp) != 0)
113 goto err;
114 scamper_addr_use(addr);
115 }
116 x++;
117 }
118 }
119
120 return sum;
121
122 err:
123 if(sum != NULL) scamper_tracelb_probeset_summary_free(sum);
124 return NULL;
125 }
126
127 /*
128 * scamper_tracelb_node_cmp
129 *
130 * function to compare two nodes, taking into account the possibility that
131 * the quoted ttl field is present and has a value.
132 */
scamper_tracelb_node_cmp(const scamper_tracelb_node_t * a,const scamper_tracelb_node_t * b)133 int scamper_tracelb_node_cmp(const scamper_tracelb_node_t *a,
134 const scamper_tracelb_node_t *b)
135 {
136 int i;
137
138 if(a->addr == NULL || b->addr == NULL)
139 {
140 if(a->addr == NULL && b->addr == NULL)
141 return 0;
142 else if(a->addr == NULL)
143 return -1;
144 return 1;
145 }
146
147 if((i = scamper_addr_human_cmp(a->addr, b->addr)) != 0)
148 return i;
149
150 if(SCAMPER_TRACELB_NODE_QTTL(a) == SCAMPER_TRACELB_NODE_QTTL(b))
151 {
152 if(SCAMPER_TRACELB_NODE_QTTL(a))
153 {
154 if(a->q_ttl < b->q_ttl) return -1;
155 if(a->q_ttl > b->q_ttl) return 1;
156 }
157 return 0;
158 }
159 else if(SCAMPER_TRACELB_NODE_QTTL(a))
160 {
161 return -1;
162 }
163 return 1;
164 }
165
166 /*
167 * scamper_tracelb_link_cmp
168 *
169 * function to compare two links. the comparison is based on the nodes
170 * present in each link.
171 */
scamper_tracelb_link_cmp(const scamper_tracelb_link_t * a,const scamper_tracelb_link_t * b)172 int scamper_tracelb_link_cmp(const scamper_tracelb_link_t *a,
173 const scamper_tracelb_link_t *b)
174 {
175 int i;
176
177 if(a == b)
178 return 0;
179
180 if((i = scamper_tracelb_node_cmp(a->from, b->from)) != 0)
181 return i;
182
183 if(a->to != NULL && b->to != NULL)
184 return scamper_tracelb_node_cmp(a->to, b->to);
185
186 if(a->to == NULL && b->to == NULL)
187 return 0;
188 else if(a->to == NULL)
189 return 1;
190 else
191 return -1;
192 }
193
194 /*
195 * tracelb_node_link_cmp
196 *
197 * compare the `to' node of two links.
198 * the from node is the same; this function is used to compare a set of links
199 * attached to a single node and order them accordingly.
200 */
tracelb_node_link_cmp(const scamper_tracelb_link_t * a,const scamper_tracelb_link_t * b)201 static int tracelb_node_link_cmp(const scamper_tracelb_link_t *a,
202 const scamper_tracelb_link_t *b)
203 {
204 assert(a->from == b->from);
205 return scamper_tracelb_node_cmp(a->to, b->to);
206 }
207
208 /*
209 * scamper_tracelb_nodes_extract
210 *
211 * function to extract a set of nodes between two points in the graph.
212 */
tracelb_nodes_extract(const scamper_tracelb_t * trace,scamper_tracelb_node_t * from,scamper_tracelb_node_t * to,scamper_tracelb_node_t ** nodes,int * nodec)213 static void tracelb_nodes_extract(const scamper_tracelb_t *trace,
214 scamper_tracelb_node_t *from,
215 scamper_tracelb_node_t *to,
216 scamper_tracelb_node_t **nodes, int *nodec)
217 {
218 uint16_t i;
219
220 if(array_find((void **)nodes, *nodec, from,
221 (array_cmp_t)scamper_tracelb_node_cmp) != NULL)
222 return;
223
224 nodes[*nodec] = from;
225 *nodec = *nodec + 1;
226 array_qsort((void **)nodes, *nodec, (array_cmp_t)scamper_tracelb_node_cmp);
227
228 if(to != NULL && from == to)
229 return;
230
231 for(i=0; i<from->linkc; i++)
232 {
233 tracelb_nodes_extract(trace, from->links[i]->to, to, nodes, nodec);
234 }
235
236 return;
237 }
238
239 /*
240 * tracelb_nodes_extract
241 *
242 * recursive function to extract a set of nodes between two points in the
243 * graph.
244 */
scamper_tracelb_nodes_extract(const scamper_tracelb_t * trace,scamper_tracelb_node_t * from,scamper_tracelb_node_t * to,scamper_tracelb_node_t ** nodes)245 int scamper_tracelb_nodes_extract(const scamper_tracelb_t *trace,
246 scamper_tracelb_node_t *from,
247 scamper_tracelb_node_t *to,
248 scamper_tracelb_node_t **nodes)
249 {
250 int nodec = 0;
251 tracelb_nodes_extract(trace, from, to, nodes, &nodec);
252 return nodec;
253 }
254
255 /*
256 * tracelb_node_index
257 *
258 * find the corresponding index for a node in the trace.
259 */
tracelb_node_index(const scamper_tracelb_t * trace,const scamper_tracelb_node_t * node)260 static int tracelb_node_index(const scamper_tracelb_t *trace,
261 const scamper_tracelb_node_t *node)
262 {
263 uint16_t i;
264 for(i=0; i<trace->nodec; i++)
265 {
266 if(trace->nodes[i] == node)
267 return i;
268 }
269 return -1;
270 }
271
scamper_tracelb_node_convergencepoint(const scamper_tracelb_t * trace,const int * fwdpathc,int from,int * to)272 int scamper_tracelb_node_convergencepoint(const scamper_tracelb_t *trace,
273 const int *fwdpathc,
274 int from, int *to)
275 {
276 scamper_tracelb_node_t *node;
277 int n, nn, rc = -1;
278 int *loop;
279
280 /* if there are no forward links, then there is no convergence point */
281 if(trace->nodes[from]->linkc == 0)
282 {
283 *to = -1;
284 return 0;
285 }
286
287 /*
288 * if there is only one forward link, then the convergence point is the
289 * next node
290 */
291 if(trace->nodes[from]->linkc == 1)
292 {
293 if((n=tracelb_node_index(trace, trace->nodes[from]->links[0]->to)) == -1)
294 return -1;
295 *to = n;
296 return 0;
297 }
298
299 /*
300 * allocate an array to keep track of which nodes have been visited so
301 * far on this exploration
302 */
303 if((loop = malloc_zero(sizeof(int) * trace->nodec)) == NULL)
304 return -1;
305 n = nn = from;
306 loop[n] = 1;
307
308 for(;;)
309 {
310 node = trace->nodes[n];
311
312 /* if there is no forward link, then there is no convergence point */
313 if(node->linkc == 0)
314 {
315 *to = -1; rc = 0;
316 break;
317 }
318
319 /* get the index into the node array of the next node to visit */
320 if((n = tracelb_node_index(trace, node->links[0]->to)) == -1)
321 break;
322
323 /* check for loops (i.e. already visited) */
324 if(loop[n] != 0)
325 {
326 *to = -1; rc = 0;
327 break;
328 }
329 loop[n] = 1;
330
331 /*
332 * if the path converges here, then return the index into the node array
333 * where it converges
334 */
335 if(fwdpathc[n] >= fwdpathc[nn])
336 {
337 *to = n; rc = 0;
338 break;
339 }
340 }
341
342 free(loop);
343 return rc;
344 }
345
346 /*
347 * tracelb_fwdpathc
348 *
349 * recursive function used to help determine how many unique forward
350 * paths can be observed at a particular node.
351 *
352 */
tracelb_fwdpathc(const scamper_tracelb_t * trace,int n,tracelb_fwdpathc_t * nodes)353 static int tracelb_fwdpathc(const scamper_tracelb_t *trace, int n,
354 tracelb_fwdpathc_t *nodes)
355 {
356 scamper_tracelb_link_t *link;
357 scamper_tracelb_node_t *node;
358 uint16_t i;
359 int nn, c, t;
360
361 if(nodes[n].pathc != 0)
362 {
363 /*
364 * if we have already visited the nodes below this point
365 * (non-zero pathc for the current node) then we increment the
366 * number of paths observable going forward by the number of
367 * unique paths from that point
368 */
369 nodes[n].pathcc += nodes[n].pathc;
370
371 node = trace->nodes[n];
372 for(i=0; i<node->linkc; i++)
373 {
374 link = node->links[i];
375 nn = tracelb_node_index(trace, link->to);
376 assert(nn >= 0 && nn < trace->nodec);
377 tracelb_fwdpathc(trace, nn, nodes);
378 }
379 }
380 else if(trace->nodes[n]->linkc > 0)
381 {
382 /*
383 * count the number of unique paths forward from this point by visiting
384 * each node forward from this point
385 */
386 nodes[n].loop = 1;
387 c = 0;
388 node = trace->nodes[n];
389 for(i=0; i<node->linkc; i++)
390 {
391 link = node->links[i];
392
393 /* get the index of the next node */
394 nn = tracelb_node_index(trace, link->to);
395 assert(nn >= 0 && nn < trace->nodec);
396
397 /* skip over any nodes that would cause us to get into a loop */
398 if(nodes[nn].loop != 0)
399 continue;
400
401 /* count the number of paths beneath it */
402 t = tracelb_fwdpathc(trace, nn, nodes);
403 assert(t > 0);
404
405 /* more paths! */
406 c += t;
407 }
408
409 /* at the end, we store the number of unique paths with the node */
410 nodes[n].pathcc = nodes[n].pathc = c;
411 nodes[n].loop = 0;
412 }
413 else
414 {
415 /*
416 * can't go any further. the first time this node has been visited.
417 * it is part of one unique path so far.
418 */
419 nodes[n].pathcc = nodes[n].pathc = 1;
420 }
421
422 return nodes[n].pathc;
423 }
424
425 /*
426 * scamper_tracelb_fwdpathc
427 *
428 * count the number of unique paths visible from one point towards a
429 * destination.
430 */
scamper_tracelb_fwdpathc(const scamper_tracelb_t * trace,int * nodes)431 int scamper_tracelb_fwdpathc(const scamper_tracelb_t *trace, int *nodes)
432 {
433 tracelb_fwdpathc_t *fwdpathc;
434 uint16_t i;
435
436 if(trace->nodec == 0)
437 return 0;
438
439 if((fwdpathc = malloc_zero(sizeof(tracelb_fwdpathc_t)*trace->nodec)) == NULL)
440 return -1;
441
442 tracelb_fwdpathc(trace, 0, fwdpathc);
443 for(i=0; i<trace->nodec; i++)
444 {
445 nodes[i] = fwdpathc[i].pathcc;
446 }
447 free(fwdpathc);
448
449 return 0;
450 }
451
scamper_tracelb_node_alloc(scamper_addr_t * addr)452 scamper_tracelb_node_t *scamper_tracelb_node_alloc(scamper_addr_t *addr)
453 {
454 scamper_tracelb_node_t *node;
455 if((node = malloc_zero(sizeof(scamper_tracelb_node_t))) != NULL)
456 {
457 if(addr != NULL)
458 node->addr = scamper_addr_use(addr);
459 }
460 return node;
461 }
462
scamper_tracelb_node_free(scamper_tracelb_node_t * node)463 void scamper_tracelb_node_free(scamper_tracelb_node_t *node)
464 {
465 if(node == NULL)
466 return;
467
468 if(node->links != NULL)
469 free(node->links);
470
471 if(node->addr != NULL)
472 scamper_addr_free(node->addr);
473
474 if(node->name != NULL)
475 free(node->name);
476
477 free(node);
478 return;
479 }
480
scamper_tracelb_node_add(scamper_tracelb_t * trace,scamper_tracelb_node_t * node)481 int scamper_tracelb_node_add(scamper_tracelb_t *trace,
482 scamper_tracelb_node_t *node)
483 {
484 size_t len = (trace->nodec + 1) * sizeof(scamper_tracelb_node_t *);
485 if(realloc_wrap((void **)&trace->nodes, len) == 0)
486 {
487 trace->nodes[trace->nodec++] = node;
488 return 0;
489 }
490
491 return -1;
492 }
493
scamper_tracelb_node_find(scamper_tracelb_t * trace,scamper_tracelb_node_t * node)494 scamper_tracelb_node_t *scamper_tracelb_node_find(scamper_tracelb_t *trace,
495 scamper_tracelb_node_t *node)
496 {
497 uint16_t i;
498
499 for(i=0; i<trace->nodec; i++)
500 {
501 if(trace->nodes[i]->addr == NULL)
502 continue;
503
504 if(scamper_tracelb_node_cmp(trace->nodes[i], node) == 0)
505 return trace->nodes[i];
506 }
507 return NULL;
508 }
509
scamper_tracelb_reply_alloc(scamper_addr_t * addr)510 scamper_tracelb_reply_t *scamper_tracelb_reply_alloc(scamper_addr_t *addr)
511 {
512 scamper_tracelb_reply_t *reply;
513
514 if((reply = malloc_zero(sizeof(scamper_tracelb_reply_t))) == NULL)
515 return NULL;
516
517 if(addr != NULL)
518 reply->reply_from = scamper_addr_use(addr);
519
520 return reply;
521 }
522
scamper_tracelb_reply_free(scamper_tracelb_reply_t * reply)523 void scamper_tracelb_reply_free(scamper_tracelb_reply_t *reply)
524 {
525 if(reply == NULL)
526 return;
527
528 if(reply->reply_from != NULL)
529 scamper_addr_free(reply->reply_from);
530
531 if((reply->reply_flags & SCAMPER_TRACELB_REPLY_FLAG_TCP) == 0)
532 scamper_icmpext_free(reply->reply_icmp_ext);
533
534 free(reply);
535 return;
536 }
537
scamper_tracelb_probe_alloc(void)538 scamper_tracelb_probe_t *scamper_tracelb_probe_alloc(void)
539 {
540 scamper_tracelb_probe_t *probe;
541 probe = malloc_zero(sizeof(scamper_tracelb_probe_t));
542 return probe;
543 }
544
scamper_tracelb_probe_free(scamper_tracelb_probe_t * probe)545 void scamper_tracelb_probe_free(scamper_tracelb_probe_t *probe)
546 {
547 uint16_t i;
548
549 if(probe == NULL)
550 return;
551
552 if(probe->rxs != NULL)
553 {
554 for(i=0; i<probe->rxc; i++)
555 scamper_tracelb_reply_free(probe->rxs[i]);
556
557 free(probe->rxs);
558 }
559 free(probe);
560 return;
561 }
562
scamper_tracelb_probe_reply(scamper_tracelb_probe_t * probe,scamper_tracelb_reply_t * reply)563 int scamper_tracelb_probe_reply(scamper_tracelb_probe_t *probe,
564 scamper_tracelb_reply_t *reply)
565 {
566 size_t len;
567
568 /* extend the replies array and store the reply in it */
569 len = (probe->rxc + 1) * sizeof(scamper_tracelb_reply_t *);
570 if(realloc_wrap((void **)&probe->rxs, len) != 0)
571 return -1;
572 probe->rxs[probe->rxc++] = reply;
573 return 0;
574 }
575
scamper_tracelb_probeset_probes_alloc(scamper_tracelb_probeset_t * set,uint16_t probec)576 int scamper_tracelb_probeset_probes_alloc(scamper_tracelb_probeset_t *set,
577 uint16_t probec)
578 {
579 size_t len = sizeof(scamper_tracelb_probe_t *) * probec;
580 if((set->probes = malloc_zero(len)) == NULL)
581 return -1;
582 return 0;
583 }
584
scamper_tracelb_probeset_add(scamper_tracelb_probeset_t * probeset,scamper_tracelb_probe_t * probe)585 int scamper_tracelb_probeset_add(scamper_tracelb_probeset_t *probeset,
586 scamper_tracelb_probe_t *probe)
587 {
588 size_t len = (probeset->probec + 1) * sizeof(scamper_tracelb_probe_t *);
589 if(realloc_wrap((void **)&probeset->probes, len) != 0)
590 return -1;
591 probeset->probes[probeset->probec++] = probe;
592 return 0;
593 }
594
scamper_tracelb_probeset_alloc(void)595 scamper_tracelb_probeset_t *scamper_tracelb_probeset_alloc(void)
596 {
597 scamper_tracelb_probeset_t *set;
598 set = malloc_zero(sizeof(scamper_tracelb_probeset_t));
599 return set;
600 }
601
scamper_tracelb_probeset_free(scamper_tracelb_probeset_t * set)602 void scamper_tracelb_probeset_free(scamper_tracelb_probeset_t *set)
603 {
604 uint16_t i;
605
606 if(set == NULL)
607 return;
608
609 if(set->probes != NULL)
610 {
611 for(i=0; i<set->probec; i++)
612 scamper_tracelb_probe_free(set->probes[i]);
613 free(set->probes);
614 }
615
616 free(set);
617 return;
618 }
619
scamper_tracelb_link_find(const scamper_tracelb_t * tr,scamper_tracelb_link_t * link)620 scamper_tracelb_link_t *scamper_tracelb_link_find(const scamper_tracelb_t *tr,
621 scamper_tracelb_link_t *link)
622 {
623 return array_find((void **)tr->links, tr->linkc, link,
624 (array_cmp_t)scamper_tracelb_link_cmp);
625 }
626
scamper_tracelb_link_alloc(void)627 scamper_tracelb_link_t *scamper_tracelb_link_alloc(void)
628 {
629 return (scamper_tracelb_link_t *)malloc_zero(sizeof(scamper_tracelb_link_t));
630 }
631
scamper_tracelb_link_free(scamper_tracelb_link_t * link)632 void scamper_tracelb_link_free(scamper_tracelb_link_t *link)
633 {
634 uint8_t i;
635
636 if(link == NULL)
637 return;
638
639 if(link->sets != NULL)
640 {
641 for(i=0; i<link->hopc; i++)
642 scamper_tracelb_probeset_free(link->sets[i]);
643
644 free(link->sets);
645 }
646
647 free(link);
648 return;
649 }
650
scamper_tracelb_link_add(scamper_tracelb_t * trace,scamper_tracelb_link_t * link)651 int scamper_tracelb_link_add(scamper_tracelb_t *trace,
652 scamper_tracelb_link_t *link)
653 {
654 scamper_tracelb_node_t *node = NULL;
655 size_t size;
656 uint16_t i;
657
658 /*
659 * to start with, find the node the link originates from, and add the link
660 * to that node
661 */
662 for(i=0; i<trace->nodec; i++)
663 {
664 if((node = trace->nodes[i]) == link->from)
665 break;
666 }
667 if(i == trace->nodec)
668 return -1;
669 assert(node != NULL);
670
671 /* add the link to the node */
672 size = sizeof(scamper_tracelb_link_t *) * (node->linkc+1);
673 if(realloc_wrap((void **)&node->links, size) == 0)
674 {
675 node->links[node->linkc++] = link;
676 array_qsort((void **)node->links, node->linkc,
677 (array_cmp_t)scamper_tracelb_link_cmp);
678 }
679 else return -1;
680
681 /* add the link to the set of links held in the trace */
682 size = sizeof(scamper_tracelb_link_t *) * (trace->linkc+1);
683 if(realloc_wrap((void **)&trace->links, size) == 0)
684 {
685 trace->links[trace->linkc++] = link;
686 array_qsort((void **)trace->links, trace->linkc,
687 (array_cmp_t)scamper_tracelb_link_cmp);
688 return 0;
689 }
690 return -1;
691 }
692
693 /*
694 * scamper_tracelb_link_zerottlfwd
695 *
696 * determine if a link is a case of zero-ttl forwarding.
697 */
scamper_tracelb_link_zerottlfwd(const scamper_tracelb_link_t * link)698 int scamper_tracelb_link_zerottlfwd(const scamper_tracelb_link_t *link)
699 {
700 if(link->from->addr == NULL)
701 return 0;
702 if(scamper_addr_cmp(link->from->addr, link->to->addr) != 0)
703 return 0;
704 if(SCAMPER_TRACELB_NODE_QTTL(link->from) == 0)
705 return 0;
706 if(SCAMPER_TRACELB_NODE_QTTL(link->to) == 0)
707 return 0;
708 if(link->from->q_ttl != 0 || link->to->q_ttl != 1)
709 return 0;
710
711 return 1;
712 }
713
scamper_tracelb_link_probesets_alloc(scamper_tracelb_link_t * link,uint8_t hopc)714 int scamper_tracelb_link_probesets_alloc(scamper_tracelb_link_t *link,
715 uint8_t hopc)
716 {
717 size_t len = hopc * sizeof(scamper_tracelb_probeset_t *);
718 if((link->sets = malloc_zero(len)) == NULL)
719 return -1;
720 return 0;
721 }
722
scamper_tracelb_link_probeset(scamper_tracelb_link_t * link,scamper_tracelb_probeset_t * set)723 int scamper_tracelb_link_probeset(scamper_tracelb_link_t *link,
724 scamper_tracelb_probeset_t *set)
725 {
726 size_t len = (link->hopc + 1) * sizeof(scamper_tracelb_probeset_t *);
727 if(realloc_wrap((void **)&link->sets, len) == 0)
728 {
729 link->sets[link->hopc++] = set;
730 return 0;
731 }
732
733 return -1;
734 }
735
scamper_tracelb_nodes_alloc(scamper_tracelb_t * trace,uint16_t count)736 int scamper_tracelb_nodes_alloc(scamper_tracelb_t *trace, uint16_t count)
737 {
738 size_t size = sizeof(scamper_tracelb_node_t *) * count;
739 if((trace->nodes = malloc_zero(size)) != NULL)
740 return 0;
741 return -1;
742 }
743
scamper_tracelb_links_alloc(scamper_tracelb_t * trace,uint16_t count)744 int scamper_tracelb_links_alloc(scamper_tracelb_t *trace, uint16_t count)
745 {
746 size_t size = sizeof(scamper_tracelb_link_t *) * count;
747 if((trace->links = malloc_zero(size)) != NULL)
748 return 0;
749 return -1;
750 }
751
scamper_tracelb_node_links_alloc(scamper_tracelb_node_t * node,uint16_t count)752 int scamper_tracelb_node_links_alloc(scamper_tracelb_node_t *node,
753 uint16_t count)
754 {
755 size_t size = sizeof(scamper_tracelb_link_t *) * count;
756 if((node->links = malloc_zero(size)) != NULL)
757 return 0;
758 return -1;
759 }
760
scamper_tracelb_probe_replies_alloc(scamper_tracelb_probe_t * probe,uint16_t count)761 int scamper_tracelb_probe_replies_alloc(scamper_tracelb_probe_t *probe,
762 uint16_t count)
763 {
764 size_t size = sizeof(scamper_tracelb_reply_t *) * count;
765 if((probe->rxs = malloc_zero(size)) != NULL)
766 return 0;
767 return -1;
768 }
769
scamper_tracelb_node_links_sort(scamper_tracelb_node_t * node)770 void scamper_tracelb_node_links_sort(scamper_tracelb_node_t *node)
771 {
772 array_qsort((void **)node->links, node->linkc,
773 (array_cmp_t)tracelb_node_link_cmp);
774 return;
775 }
776
scamper_tracelb_addr(const void * va)777 scamper_addr_t *scamper_tracelb_addr(const void *va)
778 {
779 return ((scamper_tracelb_t *)va)->dst;
780 }
781
scamper_tracelb_type_tostr(const scamper_tracelb_t * trace)782 const char *scamper_tracelb_type_tostr(const scamper_tracelb_t *trace)
783 {
784 if(trace->type == SCAMPER_TRACELB_TYPE_UDP_DPORT)
785 return "udp-dport";
786 if(trace->type == SCAMPER_TRACELB_TYPE_ICMP_ECHO)
787 return "icmp-echo";
788 if(trace->type == SCAMPER_TRACELB_TYPE_UDP_SPORT)
789 return "udp-sport";
790 if(trace->type == SCAMPER_TRACELB_TYPE_TCP_SPORT)
791 return "tcp-sport";
792 if(trace->type == SCAMPER_TRACELB_TYPE_TCP_ACK_SPORT)
793 return "tcp-ack-sport";
794 return NULL;
795 }
796
scamper_tracelb_sort(scamper_tracelb_t * trace)797 int scamper_tracelb_sort(scamper_tracelb_t *trace)
798 {
799 scamper_tracelb_node_t **nodes = NULL;
800 scamper_tracelb_node_t **nq = NULL;
801 int i, k, n, q, qt;
802 size_t size;
803 uint16_t j;
804
805 if(trace->nodec == 0)
806 return 0;
807
808 size = sizeof(scamper_tracelb_node_t *) * trace->nodec;
809 if((nodes = malloc_zero(size)) == NULL || (nq = malloc_zero(size)) == NULL)
810 goto err;
811
812 n = 0;
813 q = 0;
814
815 nq[q++] = trace->nodes[0];
816
817 while(q > 0)
818 {
819 qt = q;
820
821 for(i=0; i<qt; i++)
822 {
823 assert(n < trace->nodec);
824 nodes[n++] = nq[i];
825
826 for(j=0; j<nq[i]->linkc; j++)
827 {
828 for(k=0; k<q; k++)
829 {
830 if(nq[i]->links[j]->to == nq[k])
831 break;
832 }
833
834 if(k != q)
835 continue;
836
837 for(k=0; k<n; k++)
838 {
839 if(nq[i]->links[j]->to == nodes[k])
840 break;
841 }
842
843 if(k != n)
844 continue;
845
846 assert(q < trace->nodec);
847 nq[q++] = nq[i]->links[j]->to;
848 }
849 }
850
851 memmove(nq, nq+qt, (q-qt) * sizeof(scamper_tracelb_node_t *));
852 q -= qt;
853 }
854
855 assert(n == trace->nodec);
856 memcpy(trace->nodes, nodes, trace->nodec*sizeof(scamper_tracelb_node_t *));
857 free(nodes);
858 free(nq);
859 return 0;
860
861 err:
862 if(nodes != NULL) free(nodes);
863 if(nq != NULL) free(nq);
864 return -1;
865 }
866
867 /*
868 * scamper_tracelb_free
869 *
870 */
scamper_tracelb_free(scamper_tracelb_t * trace)871 void scamper_tracelb_free(scamper_tracelb_t *trace)
872 {
873 uint16_t i;
874
875 if(trace == NULL) return;
876
877 if(trace->links != NULL)
878 {
879 for(i=0; i<trace->linkc; i++)
880 scamper_tracelb_link_free(trace->links[i]);
881 free(trace->links);
882 }
883
884 if(trace->nodes != NULL)
885 {
886 for(i=0; i<trace->nodec; i++)
887 scamper_tracelb_node_free(trace->nodes[i]);
888 free(trace->nodes);
889 }
890
891 if(trace->dst != NULL) scamper_addr_free(trace->dst);
892 if(trace->src != NULL) scamper_addr_free(trace->src);
893 if(trace->rtr != NULL) scamper_addr_free(trace->rtr);
894
895 if(trace->cycle != NULL) scamper_cycle_free(trace->cycle);
896 if(trace->list != NULL) scamper_list_free(trace->list);
897
898 free(trace);
899 return;
900 }
901
902 /*
903 * scamper_tracelb_alloc
904 *
905 * allocate the trace and all the possibly necessary data fields
906 */
scamper_tracelb_alloc()907 scamper_tracelb_t *scamper_tracelb_alloc()
908 {
909 return (scamper_tracelb_t *)malloc_zero(sizeof(scamper_tracelb_t));
910 }
911