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 $
10 * Copyright (c) Xerox Corporation 1992. All rights reserved.
12 * License is granted to copy, to use, and to make and to use derivative
13 * works for research and evaluation purposes, provided that Xerox is
14 * acknowledged in all documentation pertaining to any such copy or derivative
15 * work. Xerox grants no other licenses expressed or implied. The Xerox trade
16 * name should not be used in any advertising without its written permission.
18 * XEROX CORPORATION MAKES NO REPRESENTATIONS CONCERNING EITHER THE
19 * MERCHANTABILITY OF THIS SOFTWARE OR THE SUITABILITY OF THIS SOFTWARE
20 * FOR ANY PARTICULAR PURPOSE. The software is provided "as is" without
21 * express or implied warranty of any kind.
23 * These notices must be retained in any copies of any part of this software.
31 #include <arpa/inet.h>
34 #define DEFAULT_TIMEOUT 2 /* How long to wait before retrying requests */
35 #define DEFAULT_RETRIES 1 /* How many times to ask each router */
38 /* All IP addresses are stored in the data structure in NET order. */
40 typedef struct neighbor {
41 struct neighbor *next;
42 u_int32 addr; /* IP address in NET order */
43 u_char metric; /* TTL cost of forwarding */
44 u_char threshold; /* TTL threshold to forward */
45 u_short flags; /* flags on connection */
46 #define NF_PRESENT 0x8000 /* True if flags are meaningful */
49 typedef struct interface {
50 struct interface *next;
51 u_int32 addr; /* IP address of the interface in NET order */
52 Neighbor *neighbors; /* List of neighbors' IP addresses */
56 u_int32 addr; /* IP address of this entry in NET order */
57 u_int32 version; /* which mrouted version is running */
58 int tries; /* How many requests sent? -1 for aliases */
60 struct node *alias; /* If alias, to what? */
61 struct interface *interfaces; /* Else, neighbor data */
63 struct node *left, *right;
68 u_int32 our_addr, target_addr = 0; /* in NET order */
70 int retries = DEFAULT_RETRIES;
71 int timeout = DEFAULT_TIMEOUT;
72 int show_names = TRUE;
73 vifi_t numvifs; /* to keep loader happy */
74 /* (see COPY_TABLES macro called in kern.c) */
76 Node * find_node(u_int32 addr, Node **ptr);
77 Interface * find_interface(u_int32 addr, Node *node);
78 Neighbor * find_neighbor(u_int32 addr, Node *node);
79 void ask(u_int32 dst);
80 void ask2(u_int32 dst);
81 int retry_requests(Node *node);
82 char * inet_name(u_int32 addr);
83 void print_map(Node *node);
84 char * graph_name(u_int32 addr, char *buf, int len);
85 void graph_edges(Node *node);
86 void elide_aliases(Node *node);
88 int get_number(int *var, int deflt, char ***pargv,
90 u_int32 host_addr(char *name);
91 static void usage(void);
94 find_node(u_int32 addr, Node **ptr)
99 *ptr = n = (Node *) malloc(sizeof(Node));
103 n->u.interfaces = NULL;
104 n->left = n->right = NULL;
106 } else if (addr == n->addr)
108 else if (addr < n->addr)
109 return find_node(addr, &(n->left));
111 return find_node(addr, &(n->right));
115 find_interface(u_int32 addr, Node *node)
119 for (ifc = node->u.interfaces; ifc; ifc = ifc->next)
120 if (ifc->addr == addr)
123 ifc = (Interface *) malloc(sizeof(Interface));
125 ifc->next = node->u.interfaces;
126 node->u.interfaces = ifc;
127 ifc->neighbors = NULL;
133 find_neighbor(u_int32 addr, Node *node)
137 for (ifc = node->u.interfaces; ifc; ifc = ifc->next) {
140 for (nb = ifc->neighbors; nb; nb = nb->next)
141 if (nb->addr == addr)
150 * Log errors and other messages to stderr, according to the severity of the
151 * message and the current debug level. For errors of severity LOG_ERR or
152 * worse, terminate the program.
155 dolog(int severity, int syserr, char *format, ...)
160 va_start(ap, format);
163 case 0: if (severity > LOG_WARNING) return;
164 case 1: if (severity > LOG_NOTICE ) return;
165 case 2: if (severity > LOG_INFO ) return;
168 if (severity == LOG_WARNING)
169 strcpy(fmt, "warning - ");
170 strncat(fmt, format, sizeof(fmt)-strlen(fmt));
171 fmt[sizeof(fmt)-1]='\0';
172 vfprintf(stderr, fmt, ap);
174 fprintf(stderr, "\n");
175 else if (syserr < sys_nerr)
176 fprintf(stderr, ": %s\n", sys_errlist[syserr]);
178 fprintf(stderr, ": errno %d\n", syserr);
181 if (severity <= LOG_ERR)
187 * Send a neighbors-list request.
193 send_igmp(our_addr, dst, IGMP_DVMRP, DVMRP_ASK_NEIGHBORS,
194 htonl(MROUTED_LEVEL), 0);
201 send_igmp(our_addr, dst, IGMP_DVMRP, DVMRP_ASK_NEIGHBORS2,
202 htonl(MROUTED_LEVEL), 0);
207 * Process an incoming group membership report.
210 accept_group_report(u_int32 src, u_int32 dst, u_int32 group, int r_type)
213 dolog(LOG_INFO, 0, "ignoring IGMP group membership report from %s to %s",
214 inet_fmt(src, s1), inet_fmt(dst, s2));
219 * Process an incoming neighbor probe message.
222 accept_probe(u_int32 src, u_int32 dst, char *p, int datalen, u_int32 level)
224 dolog(LOG_INFO, 0, "ignoring DVMRP probe from %s to %s",
225 inet_fmt(src, s1), inet_fmt(dst, s2));
230 * Process an incoming route report message.
233 accept_report(u_int32 src, u_int32 dst, char *p, int datalen, u_int32 level)
235 dolog(LOG_INFO, 0, "ignoring DVMRP routing report from %s to %s",
236 inet_fmt(src, s1), inet_fmt(dst, s2));
241 * Process an incoming neighbor-list request message.
244 accept_neighbor_request(u_int32 src, u_int32 dst)
246 if (src != our_addr) {
248 "ignoring spurious DVMRP neighbor request from %s to %s",
249 inet_fmt(src, s1), inet_fmt(dst, s2));
254 accept_neighbor_request2(u_int32 src, u_int32 dst)
256 if (src != our_addr) {
258 "ignoring spurious DVMRP neighbor request2 from %s to %s",
259 inet_fmt(src, s1), inet_fmt(dst, s2));
264 * Process an incoming neighbor-list message.
267 accept_neighbors(u_int32 src, u_int32 dst, u_char *p, int datalen,
270 Node *node = find_node(src, &routers);
272 if (node->tries == 0) /* Never heard of 'em; must have hit them at */
273 node->tries = 1; /* least once, though...*/
274 else if (node->tries == -1) /* follow alias link */
275 node = node->u.alias;
277 #define GET_ADDR(a) (a = ((u_int32)*p++ << 24), a += ((u_int32)*p++ << 16),\
278 a += ((u_int32)*p++ << 8), a += *p++)
280 /* if node is running a recent mrouted, ask for additional info */
282 node->version = level;
291 fprintf(stderr, " datalen = %d\n", datalen);
292 for (i = 0; i < datalen; i++) {
294 fprintf(stderr, " ");
295 fprintf(stderr, " %02x", p[i]);
296 if ((i & 0xF) == 0xF)
297 fprintf(stderr, "\n");
299 if ((datalen & 0xF) != 0xF)
300 fprintf(stderr, "\n");
303 while (datalen > 0) { /* loop through interfaces */
305 u_char metric, threshold, ncount;
308 Neighbor *old_neighbors;
310 if (datalen < 4 + 3) {
311 dolog(LOG_WARNING, 0, "received truncated interface record from %s",
317 ifc_addr = htonl(ifc_addr);
323 /* Fix up any alias information */
324 ifc_node = find_node(ifc_addr, &routers);
325 if (ifc_node->tries == 0) { /* new node */
326 ifc_node->tries = -1;
327 ifc_node->u.alias = node;
328 } else if (ifc_node != node
329 && (ifc_node->tries > 0 || ifc_node->u.alias != node)) {
330 /* must merge two hosts' nodes */
331 Interface *ifc_i, *next_ifc_i;
333 if (ifc_node->tries == -1) {
334 Node *tmp = ifc_node->u.alias;
336 ifc_node->u.alias = node;
340 /* Merge ifc_node (foo_i) into node (foo_n) */
342 if (ifc_node->tries > node->tries)
343 node->tries = ifc_node->tries;
345 for (ifc_i = ifc_node->u.interfaces; ifc_i; ifc_i = next_ifc_i) {
346 Neighbor *nb_i, *next_nb_i, *nb_n;
347 Interface *ifc_n = find_interface(ifc_i->addr, node);
349 old_neighbors = ifc_n->neighbors;
350 for (nb_i = ifc_i->neighbors; nb_i; nb_i = next_nb_i) {
351 next_nb_i = nb_i->next;
352 for (nb_n = old_neighbors; nb_n; nb_n = nb_n->next)
353 if (nb_i->addr == nb_n->addr) {
354 if (nb_i->metric != nb_n->metric
355 || nb_i->threshold != nb_n->threshold)
356 dolog(LOG_WARNING, 0,
357 "inconsistent %s for neighbor %s of %s",
359 inet_fmt(nb_i->addr, s1),
360 inet_fmt(node->addr, s2));
364 if (!nb_n) { /* no match for this neighbor yet */
365 nb_i->next = ifc_n->neighbors;
366 ifc_n->neighbors = nb_i;
370 next_ifc_i = ifc_i->next;
374 ifc_node->tries = -1;
375 ifc_node->u.alias = node;
378 ifc = find_interface(ifc_addr, node);
379 old_neighbors = ifc->neighbors;
381 /* Add the neighbors for this interface */
388 dolog(LOG_WARNING, 0, "received truncated neighbor list from %s",
394 neighbor = htonl(neighbor);
397 for (nb = old_neighbors; nb; nb = nb->next)
398 if (nb->addr == neighbor) {
399 if (metric != nb->metric || threshold != nb->threshold)
400 dolog(LOG_WARNING, 0,
401 "inconsistent %s for neighbor %s of %s",
403 inet_fmt(nb->addr, s1), inet_fmt(node->addr, s2));
407 nb = (Neighbor *) malloc(sizeof(Neighbor));
408 nb->next = ifc->neighbors;
412 nb->threshold = threshold;
415 n_node = find_node(neighbor, &routers);
416 if (n_node->tries == 0 && !target_addr) { /* it's a new router */
427 accept_neighbors2(u_int32 src, u_int32 dst, u_char *p, int datalen,
430 Node *node = find_node(src, &routers);
431 u_int broken_cisco = ((level & 0xffff) == 0x020a); /* 10.2 */
432 /* well, only possibly_broken_cisco, but that's too long to type. */
434 if (node->tries == 0) /* Never heard of 'em; must have hit them at */
435 node->tries = 1; /* least once, though...*/
436 else if (node->tries == -1) /* follow alias link */
437 node = node->u.alias;
439 while (datalen > 0) { /* loop through interfaces */
441 u_char metric, threshold, ncount, flags;
444 Neighbor *old_neighbors;
446 if (datalen < 4 + 4) {
447 dolog(LOG_WARNING, 0, "received truncated interface record from %s",
452 ifc_addr = *(u_int32*)p;
460 if (broken_cisco && ncount == 0) /* dumb Ciscos */
462 if (broken_cisco && ncount > 15) /* dumb Ciscos */
463 ncount = ncount & 0xf;
465 /* Fix up any alias information */
466 ifc_node = find_node(ifc_addr, &routers);
467 if (ifc_node->tries == 0) { /* new node */
468 ifc_node->tries = -1;
469 ifc_node->u.alias = node;
470 } else if (ifc_node != node
471 && (ifc_node->tries > 0 || ifc_node->u.alias != node)) {
472 /* must merge two hosts' nodes */
473 Interface *ifc_i, *next_ifc_i;
475 if (ifc_node->tries == -1) {
476 Node *tmp = ifc_node->u.alias;
478 ifc_node->u.alias = node;
482 /* Merge ifc_node (foo_i) into node (foo_n) */
484 if (ifc_node->tries > node->tries)
485 node->tries = ifc_node->tries;
487 for (ifc_i = ifc_node->u.interfaces; ifc_i; ifc_i = next_ifc_i) {
488 Neighbor *nb_i, *next_nb_i, *nb_n;
489 Interface *ifc_n = find_interface(ifc_i->addr, node);
491 old_neighbors = ifc_n->neighbors;
492 for (nb_i = ifc_i->neighbors; nb_i; nb_i = next_nb_i) {
493 next_nb_i = nb_i->next;
494 for (nb_n = old_neighbors; nb_n; nb_n = nb_n->next)
495 if (nb_i->addr == nb_n->addr) {
496 if (nb_i->metric != nb_n->metric
497 || nb_i->threshold != nb_n->threshold)
498 dolog(LOG_WARNING, 0,
499 "inconsistent %s for neighbor %s of %s",
501 inet_fmt(nb_i->addr, s1),
502 inet_fmt(node->addr, s2));
506 if (!nb_n) { /* no match for this neighbor yet */
507 nb_i->next = ifc_n->neighbors;
508 ifc_n->neighbors = nb_i;
512 next_ifc_i = ifc_i->next;
516 ifc_node->tries = -1;
517 ifc_node->u.alias = node;
520 ifc = find_interface(ifc_addr, node);
521 old_neighbors = ifc->neighbors;
523 /* Add the neighbors for this interface */
524 while (ncount-- && datalen > 0) {
530 dolog(LOG_WARNING, 0, "received truncated neighbor list from %s",
535 neighbor = *(u_int32*)p;
539 /* make leaf nets point to themselves */
542 for (nb = old_neighbors; nb; nb = nb->next)
543 if (nb->addr == neighbor) {
544 if (metric != nb->metric || threshold != nb->threshold)
545 dolog(LOG_WARNING, 0,
546 "inconsistent %s for neighbor %s of %s",
548 inet_fmt(nb->addr, s1), inet_fmt(node->addr, s2));
552 nb = (Neighbor *) malloc(sizeof(Neighbor));
553 nb->next = ifc->neighbors;
557 nb->threshold = threshold;
558 nb->flags = flags | NF_PRESENT;
560 n_node = find_node(neighbor, &routers);
561 if (n_node->tries == 0 && !target_addr) { /* it's a new router */
572 check_vif_state(void)
574 dolog(LOG_NOTICE, 0, "network marked down...");
578 retry_requests(Node *node)
583 result = retry_requests(node->left);
584 if (node->tries > 0 && node->tries < retries) {
592 return retry_requests(node->right) || result;
598 inet_name(u_int32 addr)
602 e = gethostbyaddr(&addr, sizeof(addr), AF_INET);
604 return e ? e->h_name : 0;
608 print_map(Node *node)
613 print_map(node->left);
615 addr = inet_fmt(node->addr, s1);
617 || (node->tries >= 0 && node->u.interfaces)
618 || (node->tries == -1
619 && node->u.alias->tries >= 0
620 && node->u.alias->u.interfaces)) {
621 if (show_names && (name = inet_name(node->addr)))
622 printf("%s (%s):", addr, name);
626 printf(" alias for %s\n\n", inet_fmt(node->u.alias->addr, s1));
627 else if (!node->u.interfaces)
628 printf(" no response to query\n\n");
633 printf(" <v%d.%d>", node->version & 0xff,
634 (node->version >> 8) & 0xff);
636 for (ifc = node->u.interfaces; ifc; ifc = ifc->next) {
638 char *ifc_name = inet_fmt(ifc->addr, s1);
639 int ifc_len = strlen(ifc_name);
642 printf(" %s:", ifc_name);
643 for (nb = ifc->neighbors; nb; nb = nb->next) {
645 printf("%*s", ifc_len + 5, "");
646 printf(" %s", inet_fmt(nb->addr, s1));
647 if (show_names && (name = inet_name(nb->addr)))
648 printf(" (%s)", name);
649 printf(" [%d/%d", nb->metric, nb->threshold);
651 u_short flags = nb->flags;
652 if (flags & DVMRP_NF_TUNNEL)
654 if (flags & DVMRP_NF_SRCRT)
656 if (flags & DVMRP_NF_QUERIER)
658 if (flags & DVMRP_NF_DISABLED)
660 if (flags & DVMRP_NF_DOWN)
670 print_map(node->right);
675 graph_name(u_int32 addr, char *buf, int len)
679 if (len < sizeof("255.255.255.255")) {
681 "Buffer too small in graph_name, provided %d bytes, but needed %d.\n",
682 len, sizeof("255.255.255.255"));
685 if (show_names && (name = inet_name(addr))) {
686 strncpy(buf, name, len - 1);
695 graph_edges(Node *node)
702 graph_edges(node->left);
703 if (node->tries >= 0) {
704 printf(" %d {$ NP %d0 %d0 $} \"%s%s\" \n",
706 node->addr & 0xFF, (node->addr >> 8) & 0xFF,
707 graph_name(node->addr, name, sizeof(name)),
708 node->u.interfaces ? "" : "*");
709 for (ifc = node->u.interfaces; ifc; ifc = ifc->next)
710 for (nb = ifc->neighbors; nb; nb = nb->next) {
711 Node *nb_node = find_node(nb->addr, &routers);
714 if (nb_node->tries < 0)
715 nb_node = nb_node->u.alias;
717 if (node != nb_node &&
718 (!(nb2 = find_neighbor(node->addr, nb_node))
719 || node->addr < nb_node->addr)) {
720 printf(" %d \"%d/%d",
721 nb_node->addr, nb->metric, nb->threshold);
722 if (nb2 && (nb2->metric != nb->metric
723 || nb2->threshold != nb->threshold))
724 printf(",%d/%d", nb2->metric, nb2->threshold);
725 if (nb->flags & NF_PRESENT)
727 nb->flags & DVMRP_NF_SRCRT ? "" :
728 nb->flags & DVMRP_NF_TUNNEL ? "E" : "P",
729 nb->flags & DVMRP_NF_DOWN ? "D" : "");
735 graph_edges(node->right);
740 elide_aliases(Node *node)
743 elide_aliases(node->left);
744 if (node->tries >= 0) {
747 for (ifc = node->u.interfaces; ifc; ifc = ifc->next) {
750 for (nb = ifc->neighbors; nb; nb = nb->next) {
751 Node *nb_node = find_node(nb->addr, &routers);
753 if (nb_node->tries < 0)
754 nb->addr = nb_node->u.alias->addr;
758 elide_aliases(node->right);
769 nowstr = ctime(&now);
770 nowstr[24] = '\0'; /* Kill the newline at the end */
771 elide_aliases(routers);
772 printf("GRAPH \"Multicast Router Connectivity: %s\" = UNDIRECTED\n",
774 graph_edges(routers);
779 get_number(int *var, int deflt, char ***pargv, int *pargc)
781 if ((*pargv)[0][2] == '\0') { /* Get the value from the next argument */
782 if (*pargc > 1 && isdigit((*pargv)[1][0])) {
783 (*pargv)++, (*pargc)--;
784 *var = atoi((*pargv)[0]);
786 } else if (deflt >= 0) {
791 } else { /* Get value from the rest of this argument */
792 if (isdigit((*pargv)[0][2])) {
793 *var = atoi((*pargv)[0] + 2);
802 host_addr(char *name)
804 struct hostent *e = gethostbyname(name);
807 if (e && e->h_length == sizeof(addr))
808 memcpy(&addr, e->h_addr_list[0], e->h_length);
810 addr = inet_addr(name);
819 main(int argc, char **argv)
821 int flood = FALSE, graph = FALSE;
824 errx(1, "must be root");
832 while (argc > 0 && argv[0][0] == '-') {
833 switch (argv[0][1]) {
835 if (!get_number(&debug, DEFAULT_DEBUG, &argv, &argc))
848 if (!get_number(&retries, -1, &argv, &argc))
852 if (!get_number(&timeout, -1, &argv, &argc))
863 } else if (argc == 1 && !(target_addr = host_addr(argv[0])))
864 errx(2, "unknown host: %s", argv[0]);
867 fprintf(stderr, "Debug level %u\n", debug);
869 { /* Find a good local address for us. */
871 struct sockaddr_in addr;
872 int addrlen = sizeof(addr);
874 addr.sin_family = AF_INET;
876 addr.sin_len = sizeof addr;
878 addr.sin_addr.s_addr = dvmrp_group;
879 addr.sin_port = htons(2000); /* any port over 1024 will do... */
880 if ((udp = socket(AF_INET, SOCK_DGRAM, 0)) < 0
881 || connect(udp, (struct sockaddr *) &addr, sizeof(addr)) < 0
882 || getsockname(udp, (struct sockaddr *) &addr, &addrlen) < 0)
883 err(-1, "determining local address");
885 our_addr = addr.sin_addr.s_addr;
888 /* Send initial seed message to all local routers */
889 ask(target_addr ? target_addr : allhosts_group);
892 Node *n = find_node(target_addr, &routers);
900 /* Main receive loop */
904 int count, recvlen, dummy = 0;
906 if (igmp_socket >= FD_SETSIZE)
907 dolog(LOG_ERR, 0, "descriptor too big");
909 FD_SET(igmp_socket, &fds);
914 count = select(igmp_socket + 1, &fds, 0, 0, &tv);
920 } else if (count == 0) {
921 dolog(LOG_DEBUG, 0, "Timed out receiving neighbor lists");
922 if (retry_requests(routers))
928 recvlen = recvfrom(igmp_socket, recv_buf, RECV_BUF_SIZE,
931 accept_igmp(recvlen);
932 else if (errno != EINTR)
942 printf("Multicast Router Connectivity:\n\n");
952 fprintf(stderr, "%s\n%s\n",
953 "usage: map-mbone [-f] [-g] [-n] [-t timeout] [-r retries]",
954 " [-d [debug-level]] [router]");
960 accept_prune(u_int32 src, u_int32 dst, char *p, int datalen)
965 accept_graft(u_int32 src, u_int32 dst, char *p, int datalen)
970 accept_g_ack(u_int32 src, u_int32 dst, char *p, int datalen)
975 add_table_entry(u_int32 origin, u_int32 mcastgrp)
980 accept_leave_message(u_int32 src, u_int32 dst, u_int32 group)
985 accept_mtrace(u_int32 src, u_int32 dst, u_int32 group,
986 char *data, u_int no, int datalen)
991 accept_membership_query(u_int32 src, u_int32 dst, u_int32 group, int tmo)
996 accept_info_request(u_int32 src, u_int32 dst, u_char *p, int datalen)
1001 accept_info_reply(u_int32 src, u_int32 dst, u_char *p, int datalen)