1 /* Mapper for connections between MRouteD multicast routers.
2 * Written by Pavel Curtis <Pavel@PARC.Xerox.Com>
4 * mapper.c,v 3.8.4.3 1998/01/06 01:57:47 fenner Exp
6 * $FreeBSD: src/usr.sbin/mrouted/mapper.c,v 1.15.2.1 2002/09/12 16:27:49 nectar Exp $
7 * $DragonFly: src/usr.sbin/mrouted/mapper.c,v 1.3 2003/11/03 19:31:38 eirikn Exp $
11 * Copyright (c) Xerox Corporation 1992. All rights reserved.
13 * License is granted to copy, to use, and to make and to use derivative
14 * works for research and evaluation purposes, provided that Xerox is
15 * acknowledged in all documentation pertaining to any such copy or derivative
16 * work. Xerox grants no other licenses expressed or implied. The Xerox trade
17 * name should not be used in any advertising without its written permission.
19 * XEROX CORPORATION MAKES NO REPRESENTATIONS CONCERNING EITHER THE
20 * MERCHANTABILITY OF THIS SOFTWARE OR THE SUITABILITY OF THIS SOFTWARE
21 * FOR ANY PARTICULAR PURPOSE. The software is provided "as is" without
22 * express or implied warranty of any kind.
24 * These notices must be retained in any copies of any part of this software.
32 #include <arpa/inet.h>
39 #define DEFAULT_TIMEOUT 2 /* How long to wait before retrying requests */
40 #define DEFAULT_RETRIES 1 /* How many times to ask each router */
43 /* All IP addresses are stored in the data structure in NET order. */
45 typedef struct neighbor {
46 struct neighbor *next;
47 u_int32 addr; /* IP address in NET order */
48 u_char metric; /* TTL cost of forwarding */
49 u_char threshold; /* TTL threshold to forward */
50 u_short flags; /* flags on connection */
51 #define NF_PRESENT 0x8000 /* True if flags are meaningful */
54 typedef struct interface {
55 struct interface *next;
56 u_int32 addr; /* IP address of the interface in NET order */
57 Neighbor *neighbors; /* List of neighbors' IP addresses */
61 u_int32 addr; /* IP address of this entry in NET order */
62 u_int32 version; /* which mrouted version is running */
63 int tries; /* How many requests sent? -1 for aliases */
65 struct node *alias; /* If alias, to what? */
66 struct interface *interfaces; /* Else, neighbor data */
68 struct node *left, *right;
73 u_int32 our_addr, target_addr = 0; /* in NET order */
75 int retries = DEFAULT_RETRIES;
76 int timeout = DEFAULT_TIMEOUT;
77 int show_names = TRUE;
78 vifi_t numvifs; /* to keep loader happy */
79 /* (see COPY_TABLES macro called in kern.c) */
81 Node * find_node(u_int32 addr, Node **ptr);
82 Interface * find_interface(u_int32 addr, Node *node);
83 Neighbor * find_neighbor(u_int32 addr, Node *node);
84 int main(int argc, char *argv[]);
85 void ask(u_int32 dst);
86 void ask2(u_int32 dst);
87 int retry_requests(Node *node);
88 char * inet_name(u_int32 addr);
89 void print_map(Node *node);
90 char * graph_name(u_int32 addr, char *buf, int len);
91 void graph_edges(Node *node);
92 void elide_aliases(Node *node);
94 int get_number(int *var, int deflt, char ***pargv,
96 u_int32 host_addr(char *name);
97 static void usage(void);
100 Node *find_node(addr, ptr)
107 *ptr = n = (Node *) malloc(sizeof(Node));
112 n->left = n->right = 0;
114 } else if (addr == n->addr)
116 else if (addr < n->addr)
117 return find_node(addr, &(n->left));
119 return find_node(addr, &(n->right));
123 Interface *find_interface(addr, node)
129 for (ifc = node->u.interfaces; ifc; ifc = ifc->next)
130 if (ifc->addr == addr)
133 ifc = (Interface *) malloc(sizeof(Interface));
135 ifc->next = node->u.interfaces;
136 node->u.interfaces = ifc;
143 Neighbor *find_neighbor(addr, node)
149 for (ifc = node->u.interfaces; ifc; ifc = ifc->next) {
152 for (nb = ifc->neighbors; nb; nb = nb->next)
153 if (nb->addr == addr)
162 * Log errors and other messages to stderr, according to the severity of the
163 * message and the current debug level. For errors of severity LOG_ERR or
164 * worse, terminate the program.
168 log(int severity, int syserr, char *format, ...)
173 va_start(ap, format);
177 log(severity, syserr, format, va_alist)
178 int severity, syserr;
189 case 0: if (severity > LOG_WARNING) return;
190 case 1: if (severity > LOG_NOTICE ) return;
191 case 2: if (severity > LOG_INFO ) return;
194 if (severity == LOG_WARNING)
195 strcpy(fmt, "warning - ");
196 strncat(fmt, format, sizeof(fmt)-strlen(fmt));
197 fmt[sizeof(fmt)-1]='\0';
198 vfprintf(stderr, fmt, ap);
200 fprintf(stderr, "\n");
201 else if (syserr < sys_nerr)
202 fprintf(stderr, ": %s\n", sys_errlist[syserr]);
204 fprintf(stderr, ": errno %d\n", syserr);
207 if (severity <= LOG_ERR)
213 * Send a neighbors-list request.
218 send_igmp(our_addr, dst, IGMP_DVMRP, DVMRP_ASK_NEIGHBORS,
219 htonl(MROUTED_LEVEL), 0);
225 send_igmp(our_addr, dst, IGMP_DVMRP, DVMRP_ASK_NEIGHBORS2,
226 htonl(MROUTED_LEVEL), 0);
231 * Process an incoming group membership report.
233 void accept_group_report(src, dst, group, r_type)
234 u_int32 src, dst, group;
237 log(LOG_INFO, 0, "ignoring IGMP group membership report from %s to %s",
238 inet_fmt(src, s1), inet_fmt(dst, s2));
243 * Process an incoming neighbor probe message.
245 void accept_probe(src, dst, p, datalen, level)
246 u_int32 src, dst, level;
250 log(LOG_INFO, 0, "ignoring DVMRP probe from %s to %s",
251 inet_fmt(src, s1), inet_fmt(dst, s2));
256 * Process an incoming route report message.
258 void accept_report(src, dst, p, datalen, level)
259 u_int32 src, dst, level;
263 log(LOG_INFO, 0, "ignoring DVMRP routing report from %s to %s",
264 inet_fmt(src, s1), inet_fmt(dst, s2));
269 * Process an incoming neighbor-list request message.
271 void accept_neighbor_request(src, dst)
276 "ignoring spurious DVMRP neighbor request from %s to %s",
277 inet_fmt(src, s1), inet_fmt(dst, s2));
280 void accept_neighbor_request2(src, dst)
285 "ignoring spurious DVMRP neighbor request2 from %s to %s",
286 inet_fmt(src, s1), inet_fmt(dst, s2));
291 * Process an incoming neighbor-list message.
293 void accept_neighbors(src, dst, p, datalen, level)
294 u_int32 src, dst, level;
298 Node *node = find_node(src, &routers);
300 if (node->tries == 0) /* Never heard of 'em; must have hit them at */
301 node->tries = 1; /* least once, though...*/
302 else if (node->tries == -1) /* follow alias link */
303 node = node->u.alias;
305 #define GET_ADDR(a) (a = ((u_int32)*p++ << 24), a += ((u_int32)*p++ << 16),\
306 a += ((u_int32)*p++ << 8), a += *p++)
308 /* if node is running a recent mrouted, ask for additional info */
310 node->version = level;
319 fprintf(stderr, " datalen = %d\n", datalen);
320 for (i = 0; i < datalen; i++) {
322 fprintf(stderr, " ");
323 fprintf(stderr, " %02x", p[i]);
324 if ((i & 0xF) == 0xF)
325 fprintf(stderr, "\n");
327 if ((datalen & 0xF) != 0xF)
328 fprintf(stderr, "\n");
331 while (datalen > 0) { /* loop through interfaces */
333 u_char metric, threshold, ncount;
336 Neighbor *old_neighbors;
338 if (datalen < 4 + 3) {
339 log(LOG_WARNING, 0, "received truncated interface record from %s",
345 ifc_addr = htonl(ifc_addr);
351 /* Fix up any alias information */
352 ifc_node = find_node(ifc_addr, &routers);
353 if (ifc_node->tries == 0) { /* new node */
354 ifc_node->tries = -1;
355 ifc_node->u.alias = node;
356 } else if (ifc_node != node
357 && (ifc_node->tries > 0 || ifc_node->u.alias != node)) {
358 /* must merge two hosts' nodes */
359 Interface *ifc_i, *next_ifc_i;
361 if (ifc_node->tries == -1) {
362 Node *tmp = ifc_node->u.alias;
364 ifc_node->u.alias = node;
368 /* Merge ifc_node (foo_i) into node (foo_n) */
370 if (ifc_node->tries > node->tries)
371 node->tries = ifc_node->tries;
373 for (ifc_i = ifc_node->u.interfaces; ifc_i; ifc_i = next_ifc_i) {
374 Neighbor *nb_i, *next_nb_i, *nb_n;
375 Interface *ifc_n = find_interface(ifc_i->addr, node);
377 old_neighbors = ifc_n->neighbors;
378 for (nb_i = ifc_i->neighbors; nb_i; nb_i = next_nb_i) {
379 next_nb_i = nb_i->next;
380 for (nb_n = old_neighbors; nb_n; nb_n = nb_n->next)
381 if (nb_i->addr == nb_n->addr) {
382 if (nb_i->metric != nb_n->metric
383 || nb_i->threshold != nb_n->threshold)
385 "inconsistent %s for neighbor %s of %s",
387 inet_fmt(nb_i->addr, s1),
388 inet_fmt(node->addr, s2));
392 if (!nb_n) { /* no match for this neighbor yet */
393 nb_i->next = ifc_n->neighbors;
394 ifc_n->neighbors = nb_i;
398 next_ifc_i = ifc_i->next;
402 ifc_node->tries = -1;
403 ifc_node->u.alias = node;
406 ifc = find_interface(ifc_addr, node);
407 old_neighbors = ifc->neighbors;
409 /* Add the neighbors for this interface */
416 log(LOG_WARNING, 0, "received truncated neighbor list from %s",
422 neighbor = htonl(neighbor);
425 for (nb = old_neighbors; nb; nb = nb->next)
426 if (nb->addr == neighbor) {
427 if (metric != nb->metric || threshold != nb->threshold)
429 "inconsistent %s for neighbor %s of %s",
431 inet_fmt(nb->addr, s1), inet_fmt(node->addr, s2));
435 nb = (Neighbor *) malloc(sizeof(Neighbor));
436 nb->next = ifc->neighbors;
440 nb->threshold = threshold;
443 n_node = find_node(neighbor, &routers);
444 if (n_node->tries == 0 && !target_addr) { /* it's a new router */
454 void accept_neighbors2(src, dst, p, datalen, level)
455 u_int32 src, dst, level;
459 Node *node = find_node(src, &routers);
460 u_int broken_cisco = ((level & 0xffff) == 0x020a); /* 10.2 */
461 /* well, only possibly_broken_cisco, but that's too long to type. */
463 if (node->tries == 0) /* Never heard of 'em; must have hit them at */
464 node->tries = 1; /* least once, though...*/
465 else if (node->tries == -1) /* follow alias link */
466 node = node->u.alias;
468 while (datalen > 0) { /* loop through interfaces */
470 u_char metric, threshold, ncount, flags;
473 Neighbor *old_neighbors;
475 if (datalen < 4 + 4) {
476 log(LOG_WARNING, 0, "received truncated interface record from %s",
481 ifc_addr = *(u_int32*)p;
489 if (broken_cisco && ncount == 0) /* dumb Ciscos */
491 if (broken_cisco && ncount > 15) /* dumb Ciscos */
492 ncount = ncount & 0xf;
494 /* Fix up any alias information */
495 ifc_node = find_node(ifc_addr, &routers);
496 if (ifc_node->tries == 0) { /* new node */
497 ifc_node->tries = -1;
498 ifc_node->u.alias = node;
499 } else if (ifc_node != node
500 && (ifc_node->tries > 0 || ifc_node->u.alias != node)) {
501 /* must merge two hosts' nodes */
502 Interface *ifc_i, *next_ifc_i;
504 if (ifc_node->tries == -1) {
505 Node *tmp = ifc_node->u.alias;
507 ifc_node->u.alias = node;
511 /* Merge ifc_node (foo_i) into node (foo_n) */
513 if (ifc_node->tries > node->tries)
514 node->tries = ifc_node->tries;
516 for (ifc_i = ifc_node->u.interfaces; ifc_i; ifc_i = next_ifc_i) {
517 Neighbor *nb_i, *next_nb_i, *nb_n;
518 Interface *ifc_n = find_interface(ifc_i->addr, node);
520 old_neighbors = ifc_n->neighbors;
521 for (nb_i = ifc_i->neighbors; nb_i; nb_i = next_nb_i) {
522 next_nb_i = nb_i->next;
523 for (nb_n = old_neighbors; nb_n; nb_n = nb_n->next)
524 if (nb_i->addr == nb_n->addr) {
525 if (nb_i->metric != nb_n->metric
526 || nb_i->threshold != nb_i->threshold)
528 "inconsistent %s for neighbor %s of %s",
530 inet_fmt(nb_i->addr, s1),
531 inet_fmt(node->addr, s2));
535 if (!nb_n) { /* no match for this neighbor yet */
536 nb_i->next = ifc_n->neighbors;
537 ifc_n->neighbors = nb_i;
541 next_ifc_i = ifc_i->next;
545 ifc_node->tries = -1;
546 ifc_node->u.alias = node;
549 ifc = find_interface(ifc_addr, node);
550 old_neighbors = ifc->neighbors;
552 /* Add the neighbors for this interface */
553 while (ncount-- && datalen > 0) {
559 log(LOG_WARNING, 0, "received truncated neighbor list from %s",
564 neighbor = *(u_int32*)p;
568 /* make leaf nets point to themselves */
571 for (nb = old_neighbors; nb; nb = nb->next)
572 if (nb->addr == neighbor) {
573 if (metric != nb->metric || threshold != nb->threshold)
575 "inconsistent %s for neighbor %s of %s",
577 inet_fmt(nb->addr, s1), inet_fmt(node->addr, s2));
581 nb = (Neighbor *) malloc(sizeof(Neighbor));
582 nb->next = ifc->neighbors;
586 nb->threshold = threshold;
587 nb->flags = flags | NF_PRESENT;
589 n_node = find_node(neighbor, &routers);
590 if (n_node->tries == 0 && !target_addr) { /* it's a new router */
601 void check_vif_state()
603 log(LOG_NOTICE, 0, "network marked down...");
607 int retry_requests(node)
613 result = retry_requests(node->left);
614 if (node->tries > 0 && node->tries < retries) {
622 return retry_requests(node->right) || result;
628 char *inet_name(addr)
633 e = gethostbyaddr((char *)&addr, sizeof(addr), AF_INET);
635 return e ? e->h_name : 0;
645 print_map(node->left);
647 addr = inet_fmt(node->addr, s1);
649 || (node->tries >= 0 && node->u.interfaces)
650 || (node->tries == -1
651 && node->u.alias->tries >= 0
652 && node->u.alias->u.interfaces)) {
653 if (show_names && (name = inet_name(node->addr)))
654 printf("%s (%s):", addr, name);
658 printf(" alias for %s\n\n", inet_fmt(node->u.alias->addr, s1));
659 else if (!node->u.interfaces)
660 printf(" no response to query\n\n");
665 printf(" <v%d.%d>", node->version & 0xff,
666 (node->version >> 8) & 0xff);
668 for (ifc = node->u.interfaces; ifc; ifc = ifc->next) {
670 char *ifc_name = inet_fmt(ifc->addr, s1);
671 int ifc_len = strlen(ifc_name);
674 printf(" %s:", ifc_name);
675 for (nb = ifc->neighbors; nb; nb = nb->next) {
677 printf("%*s", ifc_len + 5, "");
678 printf(" %s", inet_fmt(nb->addr, s1));
679 if (show_names && (name = inet_name(nb->addr)))
680 printf(" (%s)", name);
681 printf(" [%d/%d", nb->metric, nb->threshold);
683 u_short flags = nb->flags;
684 if (flags & DVMRP_NF_TUNNEL)
686 if (flags & DVMRP_NF_SRCRT)
688 if (flags & DVMRP_NF_QUERIER)
690 if (flags & DVMRP_NF_DISABLED)
692 if (flags & DVMRP_NF_DOWN)
702 print_map(node->right);
707 char *graph_name(addr, buf, len)
714 if (len < sizeof("255.255.255.255")) {
716 "Buffer too small in graph_name, provided %d bytes, but needed %d.\n",
717 len, sizeof("255.255.255.255"));
720 if (show_names && (name = inet_name(addr))) {
721 strncpy(buf, name, len - 1);
730 void graph_edges(node)
738 graph_edges(node->left);
739 if (node->tries >= 0) {
740 printf(" %d {$ NP %d0 %d0 $} \"%s%s\" \n",
742 node->addr & 0xFF, (node->addr >> 8) & 0xFF,
743 graph_name(node->addr, name, sizeof(name)),
744 node->u.interfaces ? "" : "*");
745 for (ifc = node->u.interfaces; ifc; ifc = ifc->next)
746 for (nb = ifc->neighbors; nb; nb = nb->next) {
747 Node *nb_node = find_node(nb->addr, &routers);
750 if (nb_node->tries < 0)
751 nb_node = nb_node->u.alias;
753 if (node != nb_node &&
754 (!(nb2 = find_neighbor(node->addr, nb_node))
755 || node->addr < nb_node->addr)) {
756 printf(" %d \"%d/%d",
757 nb_node->addr, nb->metric, nb->threshold);
758 if (nb2 && (nb2->metric != nb->metric
759 || nb2->threshold != nb->threshold))
760 printf(",%d/%d", nb2->metric, nb2->threshold);
761 if (nb->flags & NF_PRESENT)
763 nb->flags & DVMRP_NF_SRCRT ? "" :
764 nb->flags & DVMRP_NF_TUNNEL ? "E" : "P",
765 nb->flags & DVMRP_NF_DOWN ? "D" : "");
771 graph_edges(node->right);
775 void elide_aliases(node)
779 elide_aliases(node->left);
780 if (node->tries >= 0) {
783 for (ifc = node->u.interfaces; ifc; ifc = ifc->next) {
786 for (nb = ifc->neighbors; nb; nb = nb->next) {
787 Node *nb_node = find_node(nb->addr, &routers);
789 if (nb_node->tries < 0)
790 nb->addr = nb_node->u.alias->addr;
794 elide_aliases(node->right);
800 time_t now = time(0);
801 char *nowstr = ctime(&now);
803 nowstr[24] = '\0'; /* Kill the newline at the end */
804 elide_aliases(routers);
805 printf("GRAPH \"Multicast Router Connectivity: %s\" = UNDIRECTED\n",
807 graph_edges(routers);
812 int get_number(var, deflt, pargv, pargc)
813 int *var, *pargc, deflt;
816 if ((*pargv)[0][2] == '\0') { /* Get the value from the next argument */
817 if (*pargc > 1 && isdigit((*pargv)[1][0])) {
818 (*pargv)++, (*pargc)--;
819 *var = atoi((*pargv)[0]);
821 } else if (deflt >= 0) {
826 } else { /* Get value from the rest of this argument */
827 if (isdigit((*pargv)[0][2])) {
828 *var = atoi((*pargv)[0] + 2);
837 u_int32 host_addr(name)
840 struct hostent *e = gethostbyname(name);
843 if (e && e->h_length == sizeof(addr))
844 memcpy(&addr, e->h_addr_list[0], e->h_length);
846 addr = inet_addr(name);
859 int flood = FALSE, graph = FALSE;
862 errx(1, "must be root");
870 while (argc > 0 && argv[0][0] == '-') {
871 switch (argv[0][1]) {
873 if (!get_number(&debug, DEFAULT_DEBUG, &argv, &argc))
886 if (!get_number(&retries, -1, &argv, &argc))
890 if (!get_number(&timeout, -1, &argv, &argc))
901 } else if (argc == 1 && !(target_addr = host_addr(argv[0])))
902 errx(2, "unknown host: %s", argv[0]);
905 fprintf(stderr, "Debug level %u\n", debug);
907 { /* Find a good local address for us. */
909 struct sockaddr_in addr;
910 int addrlen = sizeof(addr);
912 addr.sin_family = AF_INET;
914 addr.sin_len = sizeof addr;
916 addr.sin_addr.s_addr = dvmrp_group;
917 addr.sin_port = htons(2000); /* any port over 1024 will do... */
918 if ((udp = socket(AF_INET, SOCK_DGRAM, 0)) < 0
919 || connect(udp, (struct sockaddr *) &addr, sizeof(addr)) < 0
920 || getsockname(udp, (struct sockaddr *) &addr, &addrlen) < 0)
921 err(-1, "determining local address");
923 our_addr = addr.sin_addr.s_addr;
926 /* Send initial seed message to all local routers */
927 ask(target_addr ? target_addr : allhosts_group);
930 Node *n = find_node(target_addr, &routers);
938 /* Main receive loop */
942 int count, recvlen, dummy = 0;
944 if (igmp_socket >= FD_SETSIZE)
945 log(LOG_ERR, 0, "descriptor too big");
947 FD_SET(igmp_socket, &fds);
952 count = select(igmp_socket + 1, &fds, 0, 0, &tv);
958 } else if (count == 0) {
959 log(LOG_DEBUG, 0, "Timed out receiving neighbor lists");
960 if (retry_requests(routers))
966 recvlen = recvfrom(igmp_socket, recv_buf, RECV_BUF_SIZE,
969 accept_igmp(recvlen);
970 else if (errno != EINTR)
980 printf("Multicast Router Connectivity:\n\n");
990 fprintf(stderr, "%s\n%s\n",
991 "usage: map-mbone [-f] [-g] [-n] [-t timeout] [-r retries]",
992 " [-d [debug-level]] [router]");
997 void accept_prune(src, dst, p, datalen)
1003 void accept_graft(src, dst, p, datalen)
1009 void accept_g_ack(src, dst, p, datalen)
1015 void add_table_entry(origin, mcastgrp)
1016 u_int32 origin, mcastgrp;
1019 void accept_leave_message(src, dst, group)
1020 u_int32 src, dst, group;
1023 void accept_mtrace(src, dst, group, data, no, datalen)
1024 u_int32 src, dst, group;
1030 void accept_membership_query(src, dst, group, tmo)
1031 u_int32 src, dst, group;
1035 void accept_info_request(src, dst, p, datalen)
1041 void accept_info_reply(src, dst, p, datalen)