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 int main(int argc, char **argv);
80 void ask(u_int32 dst);
81 void ask2(u_int32 dst);
82 int retry_requests(Node *node);
83 char * inet_name(u_int32 addr);
84 void print_map(Node *node);
85 char * graph_name(u_int32 addr, char *buf, int len);
86 void graph_edges(Node *node);
87 void elide_aliases(Node *node);
89 int get_number(int *var, int deflt, char ***pargv,
91 u_int32 host_addr(char *name);
92 static void usage(void);
95 find_node(u_int32 addr, Node **ptr)
100 *ptr = n = (Node *) malloc(sizeof(Node));
104 n->u.interfaces = NULL;
105 n->left = n->right = NULL;
107 } else if (addr == n->addr)
109 else if (addr < n->addr)
110 return find_node(addr, &(n->left));
112 return find_node(addr, &(n->right));
116 find_interface(u_int32 addr, Node *node)
120 for (ifc = node->u.interfaces; ifc; ifc = ifc->next)
121 if (ifc->addr == addr)
124 ifc = (Interface *) malloc(sizeof(Interface));
126 ifc->next = node->u.interfaces;
127 node->u.interfaces = ifc;
128 ifc->neighbors = NULL;
134 find_neighbor(u_int32 addr, Node *node)
138 for (ifc = node->u.interfaces; ifc; ifc = ifc->next) {
141 for (nb = ifc->neighbors; nb; nb = nb->next)
142 if (nb->addr == addr)
151 * Log errors and other messages to stderr, according to the severity of the
152 * message and the current debug level. For errors of severity LOG_ERR or
153 * worse, terminate the program.
156 dolog(int severity, int syserr, char *format, ...)
161 va_start(ap, format);
164 case 0: if (severity > LOG_WARNING) return;
165 case 1: if (severity > LOG_NOTICE ) return;
166 case 2: if (severity > LOG_INFO ) return;
169 if (severity == LOG_WARNING)
170 strcpy(fmt, "warning - ");
171 strncat(fmt, format, sizeof(fmt)-strlen(fmt));
172 fmt[sizeof(fmt)-1]='\0';
173 vfprintf(stderr, fmt, ap);
175 fprintf(stderr, "\n");
176 else if (syserr < sys_nerr)
177 fprintf(stderr, ": %s\n", sys_errlist[syserr]);
179 fprintf(stderr, ": errno %d\n", syserr);
182 if (severity <= LOG_ERR)
188 * Send a neighbors-list request.
194 send_igmp(our_addr, dst, IGMP_DVMRP, DVMRP_ASK_NEIGHBORS,
195 htonl(MROUTED_LEVEL), 0);
202 send_igmp(our_addr, dst, IGMP_DVMRP, DVMRP_ASK_NEIGHBORS2,
203 htonl(MROUTED_LEVEL), 0);
208 * Process an incoming group membership report.
211 accept_group_report(u_int32 src, u_int32 dst, u_int32 group, int r_type)
214 dolog(LOG_INFO, 0, "ignoring IGMP group membership report from %s to %s",
215 inet_fmt(src, s1), inet_fmt(dst, s2));
220 * Process an incoming neighbor probe message.
223 accept_probe(u_int32 src, u_int32 dst, char *p, int datalen, u_int32 level)
225 dolog(LOG_INFO, 0, "ignoring DVMRP probe from %s to %s",
226 inet_fmt(src, s1), inet_fmt(dst, s2));
231 * Process an incoming route report message.
234 accept_report(u_int32 src, u_int32 dst, char *p, int datalen, u_int32 level)
236 dolog(LOG_INFO, 0, "ignoring DVMRP routing report from %s to %s",
237 inet_fmt(src, s1), inet_fmt(dst, s2));
242 * Process an incoming neighbor-list request message.
245 accept_neighbor_request(u_int32 src, u_int32 dst)
247 if (src != our_addr) {
249 "ignoring spurious DVMRP neighbor request from %s to %s",
250 inet_fmt(src, s1), inet_fmt(dst, s2));
255 accept_neighbor_request2(u_int32 src, u_int32 dst)
257 if (src != our_addr) {
259 "ignoring spurious DVMRP neighbor request2 from %s to %s",
260 inet_fmt(src, s1), inet_fmt(dst, s2));
265 * Process an incoming neighbor-list message.
268 accept_neighbors(u_int32 src, u_int32 dst, u_char *p, int datalen,
271 Node *node = find_node(src, &routers);
273 if (node->tries == 0) /* Never heard of 'em; must have hit them at */
274 node->tries = 1; /* least once, though...*/
275 else if (node->tries == -1) /* follow alias link */
276 node = node->u.alias;
278 #define GET_ADDR(a) (a = ((u_int32)*p++ << 24), a += ((u_int32)*p++ << 16),\
279 a += ((u_int32)*p++ << 8), a += *p++)
281 /* if node is running a recent mrouted, ask for additional info */
283 node->version = level;
292 fprintf(stderr, " datalen = %d\n", datalen);
293 for (i = 0; i < datalen; i++) {
295 fprintf(stderr, " ");
296 fprintf(stderr, " %02x", p[i]);
297 if ((i & 0xF) == 0xF)
298 fprintf(stderr, "\n");
300 if ((datalen & 0xF) != 0xF)
301 fprintf(stderr, "\n");
304 while (datalen > 0) { /* loop through interfaces */
306 u_char metric, threshold, ncount;
309 Neighbor *old_neighbors;
311 if (datalen < 4 + 3) {
312 dolog(LOG_WARNING, 0, "received truncated interface record from %s",
318 ifc_addr = htonl(ifc_addr);
324 /* Fix up any alias information */
325 ifc_node = find_node(ifc_addr, &routers);
326 if (ifc_node->tries == 0) { /* new node */
327 ifc_node->tries = -1;
328 ifc_node->u.alias = node;
329 } else if (ifc_node != node
330 && (ifc_node->tries > 0 || ifc_node->u.alias != node)) {
331 /* must merge two hosts' nodes */
332 Interface *ifc_i, *next_ifc_i;
334 if (ifc_node->tries == -1) {
335 Node *tmp = ifc_node->u.alias;
337 ifc_node->u.alias = node;
341 /* Merge ifc_node (foo_i) into node (foo_n) */
343 if (ifc_node->tries > node->tries)
344 node->tries = ifc_node->tries;
346 for (ifc_i = ifc_node->u.interfaces; ifc_i; ifc_i = next_ifc_i) {
347 Neighbor *nb_i, *next_nb_i, *nb_n;
348 Interface *ifc_n = find_interface(ifc_i->addr, node);
350 old_neighbors = ifc_n->neighbors;
351 for (nb_i = ifc_i->neighbors; nb_i; nb_i = next_nb_i) {
352 next_nb_i = nb_i->next;
353 for (nb_n = old_neighbors; nb_n; nb_n = nb_n->next)
354 if (nb_i->addr == nb_n->addr) {
355 if (nb_i->metric != nb_n->metric
356 || nb_i->threshold != nb_n->threshold)
357 dolog(LOG_WARNING, 0,
358 "inconsistent %s for neighbor %s of %s",
360 inet_fmt(nb_i->addr, s1),
361 inet_fmt(node->addr, s2));
365 if (!nb_n) { /* no match for this neighbor yet */
366 nb_i->next = ifc_n->neighbors;
367 ifc_n->neighbors = nb_i;
371 next_ifc_i = ifc_i->next;
375 ifc_node->tries = -1;
376 ifc_node->u.alias = node;
379 ifc = find_interface(ifc_addr, node);
380 old_neighbors = ifc->neighbors;
382 /* Add the neighbors for this interface */
389 dolog(LOG_WARNING, 0, "received truncated neighbor list from %s",
395 neighbor = htonl(neighbor);
398 for (nb = old_neighbors; nb; nb = nb->next)
399 if (nb->addr == neighbor) {
400 if (metric != nb->metric || threshold != nb->threshold)
401 dolog(LOG_WARNING, 0,
402 "inconsistent %s for neighbor %s of %s",
404 inet_fmt(nb->addr, s1), inet_fmt(node->addr, s2));
408 nb = (Neighbor *) malloc(sizeof(Neighbor));
409 nb->next = ifc->neighbors;
413 nb->threshold = threshold;
416 n_node = find_node(neighbor, &routers);
417 if (n_node->tries == 0 && !target_addr) { /* it's a new router */
428 accept_neighbors2(u_int32 src, u_int32 dst, u_char *p, int datalen,
431 Node *node = find_node(src, &routers);
432 u_int broken_cisco = ((level & 0xffff) == 0x020a); /* 10.2 */
433 /* well, only possibly_broken_cisco, but that's too long to type. */
435 if (node->tries == 0) /* Never heard of 'em; must have hit them at */
436 node->tries = 1; /* least once, though...*/
437 else if (node->tries == -1) /* follow alias link */
438 node = node->u.alias;
440 while (datalen > 0) { /* loop through interfaces */
442 u_char metric, threshold, ncount, flags;
445 Neighbor *old_neighbors;
447 if (datalen < 4 + 4) {
448 dolog(LOG_WARNING, 0, "received truncated interface record from %s",
453 ifc_addr = *(u_int32*)p;
461 if (broken_cisco && ncount == 0) /* dumb Ciscos */
463 if (broken_cisco && ncount > 15) /* dumb Ciscos */
464 ncount = ncount & 0xf;
466 /* Fix up any alias information */
467 ifc_node = find_node(ifc_addr, &routers);
468 if (ifc_node->tries == 0) { /* new node */
469 ifc_node->tries = -1;
470 ifc_node->u.alias = node;
471 } else if (ifc_node != node
472 && (ifc_node->tries > 0 || ifc_node->u.alias != node)) {
473 /* must merge two hosts' nodes */
474 Interface *ifc_i, *next_ifc_i;
476 if (ifc_node->tries == -1) {
477 Node *tmp = ifc_node->u.alias;
479 ifc_node->u.alias = node;
483 /* Merge ifc_node (foo_i) into node (foo_n) */
485 if (ifc_node->tries > node->tries)
486 node->tries = ifc_node->tries;
488 for (ifc_i = ifc_node->u.interfaces; ifc_i; ifc_i = next_ifc_i) {
489 Neighbor *nb_i, *next_nb_i, *nb_n;
490 Interface *ifc_n = find_interface(ifc_i->addr, node);
492 old_neighbors = ifc_n->neighbors;
493 for (nb_i = ifc_i->neighbors; nb_i; nb_i = next_nb_i) {
494 next_nb_i = nb_i->next;
495 for (nb_n = old_neighbors; nb_n; nb_n = nb_n->next)
496 if (nb_i->addr == nb_n->addr) {
497 if (nb_i->metric != nb_n->metric
498 || nb_i->threshold != nb_i->threshold)
499 dolog(LOG_WARNING, 0,
500 "inconsistent %s for neighbor %s of %s",
502 inet_fmt(nb_i->addr, s1),
503 inet_fmt(node->addr, s2));
507 if (!nb_n) { /* no match for this neighbor yet */
508 nb_i->next = ifc_n->neighbors;
509 ifc_n->neighbors = nb_i;
513 next_ifc_i = ifc_i->next;
517 ifc_node->tries = -1;
518 ifc_node->u.alias = node;
521 ifc = find_interface(ifc_addr, node);
522 old_neighbors = ifc->neighbors;
524 /* Add the neighbors for this interface */
525 while (ncount-- && datalen > 0) {
531 dolog(LOG_WARNING, 0, "received truncated neighbor list from %s",
536 neighbor = *(u_int32*)p;
540 /* make leaf nets point to themselves */
543 for (nb = old_neighbors; nb; nb = nb->next)
544 if (nb->addr == neighbor) {
545 if (metric != nb->metric || threshold != nb->threshold)
546 dolog(LOG_WARNING, 0,
547 "inconsistent %s for neighbor %s of %s",
549 inet_fmt(nb->addr, s1), inet_fmt(node->addr, s2));
553 nb = (Neighbor *) malloc(sizeof(Neighbor));
554 nb->next = ifc->neighbors;
558 nb->threshold = threshold;
559 nb->flags = flags | NF_PRESENT;
561 n_node = find_node(neighbor, &routers);
562 if (n_node->tries == 0 && !target_addr) { /* it's a new router */
573 check_vif_state(void)
575 dolog(LOG_NOTICE, 0, "network marked down...");
579 retry_requests(Node *node)
584 result = retry_requests(node->left);
585 if (node->tries > 0 && node->tries < retries) {
593 return retry_requests(node->right) || result;
599 inet_name(u_int32 addr)
603 e = gethostbyaddr(&addr, sizeof(addr), AF_INET);
605 return e ? e->h_name : 0;
609 print_map(Node *node)
614 print_map(node->left);
616 addr = inet_fmt(node->addr, s1);
618 || (node->tries >= 0 && node->u.interfaces)
619 || (node->tries == -1
620 && node->u.alias->tries >= 0
621 && node->u.alias->u.interfaces)) {
622 if (show_names && (name = inet_name(node->addr)))
623 printf("%s (%s):", addr, name);
627 printf(" alias for %s\n\n", inet_fmt(node->u.alias->addr, s1));
628 else if (!node->u.interfaces)
629 printf(" no response to query\n\n");
634 printf(" <v%d.%d>", node->version & 0xff,
635 (node->version >> 8) & 0xff);
637 for (ifc = node->u.interfaces; ifc; ifc = ifc->next) {
639 char *ifc_name = inet_fmt(ifc->addr, s1);
640 int ifc_len = strlen(ifc_name);
643 printf(" %s:", ifc_name);
644 for (nb = ifc->neighbors; nb; nb = nb->next) {
646 printf("%*s", ifc_len + 5, "");
647 printf(" %s", inet_fmt(nb->addr, s1));
648 if (show_names && (name = inet_name(nb->addr)))
649 printf(" (%s)", name);
650 printf(" [%d/%d", nb->metric, nb->threshold);
652 u_short flags = nb->flags;
653 if (flags & DVMRP_NF_TUNNEL)
655 if (flags & DVMRP_NF_SRCRT)
657 if (flags & DVMRP_NF_QUERIER)
659 if (flags & DVMRP_NF_DISABLED)
661 if (flags & DVMRP_NF_DOWN)
671 print_map(node->right);
676 graph_name(u_int32 addr, char *buf, int len)
680 if (len < sizeof("255.255.255.255")) {
682 "Buffer too small in graph_name, provided %d bytes, but needed %d.\n",
683 len, sizeof("255.255.255.255"));
686 if (show_names && (name = inet_name(addr))) {
687 strncpy(buf, name, len - 1);
696 graph_edges(Node *node)
703 graph_edges(node->left);
704 if (node->tries >= 0) {
705 printf(" %d {$ NP %d0 %d0 $} \"%s%s\" \n",
707 node->addr & 0xFF, (node->addr >> 8) & 0xFF,
708 graph_name(node->addr, name, sizeof(name)),
709 node->u.interfaces ? "" : "*");
710 for (ifc = node->u.interfaces; ifc; ifc = ifc->next)
711 for (nb = ifc->neighbors; nb; nb = nb->next) {
712 Node *nb_node = find_node(nb->addr, &routers);
715 if (nb_node->tries < 0)
716 nb_node = nb_node->u.alias;
718 if (node != nb_node &&
719 (!(nb2 = find_neighbor(node->addr, nb_node))
720 || node->addr < nb_node->addr)) {
721 printf(" %d \"%d/%d",
722 nb_node->addr, nb->metric, nb->threshold);
723 if (nb2 && (nb2->metric != nb->metric
724 || nb2->threshold != nb->threshold))
725 printf(",%d/%d", nb2->metric, nb2->threshold);
726 if (nb->flags & NF_PRESENT)
728 nb->flags & DVMRP_NF_SRCRT ? "" :
729 nb->flags & DVMRP_NF_TUNNEL ? "E" : "P",
730 nb->flags & DVMRP_NF_DOWN ? "D" : "");
736 graph_edges(node->right);
741 elide_aliases(Node *node)
744 elide_aliases(node->left);
745 if (node->tries >= 0) {
748 for (ifc = node->u.interfaces; ifc; ifc = ifc->next) {
751 for (nb = ifc->neighbors; nb; nb = nb->next) {
752 Node *nb_node = find_node(nb->addr, &routers);
754 if (nb_node->tries < 0)
755 nb->addr = nb_node->u.alias->addr;
759 elide_aliases(node->right);
770 nowstr = ctime(&now);
771 nowstr[24] = '\0'; /* Kill the newline at the end */
772 elide_aliases(routers);
773 printf("GRAPH \"Multicast Router Connectivity: %s\" = UNDIRECTED\n",
775 graph_edges(routers);
780 get_number(int *var, int deflt, char ***pargv, int *pargc)
782 if ((*pargv)[0][2] == '\0') { /* Get the value from the next argument */
783 if (*pargc > 1 && isdigit((*pargv)[1][0])) {
784 (*pargv)++, (*pargc)--;
785 *var = atoi((*pargv)[0]);
787 } else if (deflt >= 0) {
792 } else { /* Get value from the rest of this argument */
793 if (isdigit((*pargv)[0][2])) {
794 *var = atoi((*pargv)[0] + 2);
803 host_addr(char *name)
805 struct hostent *e = gethostbyname(name);
808 if (e && e->h_length == sizeof(addr))
809 memcpy(&addr, e->h_addr_list[0], e->h_length);
811 addr = inet_addr(name);
820 main(int argc, char **argv)
822 int flood = FALSE, graph = FALSE;
825 errx(1, "must be root");
833 while (argc > 0 && argv[0][0] == '-') {
834 switch (argv[0][1]) {
836 if (!get_number(&debug, DEFAULT_DEBUG, &argv, &argc))
849 if (!get_number(&retries, -1, &argv, &argc))
853 if (!get_number(&timeout, -1, &argv, &argc))
864 } else if (argc == 1 && !(target_addr = host_addr(argv[0])))
865 errx(2, "unknown host: %s", argv[0]);
868 fprintf(stderr, "Debug level %u\n", debug);
870 { /* Find a good local address for us. */
872 struct sockaddr_in addr;
873 int addrlen = sizeof(addr);
875 addr.sin_family = AF_INET;
877 addr.sin_len = sizeof addr;
879 addr.sin_addr.s_addr = dvmrp_group;
880 addr.sin_port = htons(2000); /* any port over 1024 will do... */
881 if ((udp = socket(AF_INET, SOCK_DGRAM, 0)) < 0
882 || connect(udp, (struct sockaddr *) &addr, sizeof(addr)) < 0
883 || getsockname(udp, (struct sockaddr *) &addr, &addrlen) < 0)
884 err(-1, "determining local address");
886 our_addr = addr.sin_addr.s_addr;
889 /* Send initial seed message to all local routers */
890 ask(target_addr ? target_addr : allhosts_group);
893 Node *n = find_node(target_addr, &routers);
901 /* Main receive loop */
905 int count, recvlen, dummy = 0;
907 if (igmp_socket >= FD_SETSIZE)
908 dolog(LOG_ERR, 0, "descriptor too big");
910 FD_SET(igmp_socket, &fds);
915 count = select(igmp_socket + 1, &fds, 0, 0, &tv);
921 } else if (count == 0) {
922 dolog(LOG_DEBUG, 0, "Timed out receiving neighbor lists");
923 if (retry_requests(routers))
929 recvlen = recvfrom(igmp_socket, recv_buf, RECV_BUF_SIZE,
932 accept_igmp(recvlen);
933 else if (errno != EINTR)
943 printf("Multicast Router Connectivity:\n\n");
953 fprintf(stderr, "%s\n%s\n",
954 "usage: map-mbone [-f] [-g] [-n] [-t timeout] [-r retries]",
955 " [-d [debug-level]] [router]");
961 accept_prune(u_int32 src, u_int32 dst, char *p, int datalen)
966 accept_graft(u_int32 src, u_int32 dst, char *p, int datalen)
971 accept_g_ack(u_int32 src, u_int32 dst, char *p, int datalen)
976 add_table_entry(u_int32 origin, u_int32 mcastgrp)
981 accept_leave_message(u_int32 src, u_int32 dst, u_int32 group)
986 accept_mtrace(u_int32 src, u_int32 dst, u_int32 group,
987 char *data, u_int no, int datalen)
992 accept_membership_query(u_int32 src, u_int32 dst, u_int32 group, int tmo)
997 accept_info_request(u_int32 src, u_int32 dst, u_char *p, int datalen)
1002 accept_info_reply(u_int32 src, u_int32 dst, u_char *p, int datalen)