1 /* $NetBSD: route.c,v 1.5 1995/12/10 10:07:12 mycroft Exp $ */ 2 3 /* 4 * The mrouted program is covered by the license in the accompanying file 5 * named "LICENSE". Use of the mrouted program represents acceptance of 6 * the terms and conditions listed in that file. 7 * 8 * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of 9 * Leland Stanford Junior University. 10 */ 11 12 13 #include "defs.h" 14 15 16 /* 17 * This define statement saves a lot of space later 18 */ 19 #define RT_ADDR (struct rtentry *)&routing_table 20 21 /* 22 * Exported variables. 23 */ 24 int routes_changed; /* 1=>some routes have changed */ 25 int delay_change_reports; /* 1=>postpone change reports */ 26 27 28 /* 29 * The routing table is shared with prune.c , so must not be static. 30 */ 31 struct rtentry *routing_table; /* pointer to list of route entries */ 32 33 /* 34 * Private variables. 35 */ 36 static struct rtentry *rtp; /* pointer to a route entry */ 37 static struct rtentry *rt_end; /* pointer to last route entry */ 38 unsigned int nroutes; /* current number of route entries */ 39 40 /* 41 * Private functions. 42 */ 43 static int init_children_and_leaves(struct rtentry *r, vifi_t parent); 44 static int find_route(u_int32_t origin, u_int32_t mask); 45 static void create_route(u_int32_t origin, u_int32_t mask); 46 static void discard_route(struct rtentry *prev_r); 47 static int compare_rts(const void *rt1, const void *rt2); 48 static int report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst); 49 50 /* 51 * Initialize the routing table and associated variables. 52 */ 53 void 54 init_routes() 55 { 56 routing_table = NULL; 57 rt_end = RT_ADDR; 58 nroutes = 0; 59 routes_changed = FALSE; 60 delay_change_reports = FALSE; 61 } 62 63 64 /* 65 * Initialize the children and leaf bits for route 'r', along with the 66 * associated dominant, subordinate, and leaf timing data structures. 67 * Return TRUE if this changes the value of either the children or 68 * leaf bitmaps for 'r'. 69 */ 70 static int 71 init_children_and_leaves(struct rtentry *r, vifi_t parent) 72 { 73 vifi_t vifi; 74 struct uvif *v; 75 vifbitmap_t old_children, old_leaves; 76 77 VIFM_COPY(r->rt_children, old_children); 78 VIFM_COPY(r->rt_leaves, old_leaves ); 79 80 VIFM_CLRALL(r->rt_children); 81 VIFM_CLRALL(r->rt_leaves); 82 r->rt_flags &= ~RTF_LEAF_TIMING; 83 84 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) { 85 r->rt_dominants [vifi] = 0; 86 r->rt_subordinates[vifi] = 0; 87 88 if (vifi != parent && !(v->uv_flags & (VIFF_DOWN|VIFF_DISABLED))) { 89 VIFM_SET(vifi, r->rt_children); 90 if (v->uv_neighbors == NULL) { 91 VIFM_SET(vifi, r->rt_leaves); 92 r->rt_leaf_timers[vifi] = 0; 93 } 94 else { 95 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME; 96 r->rt_flags |= RTF_LEAF_TIMING; 97 } 98 } 99 else { 100 r->rt_leaf_timers[vifi] = 0; 101 } 102 } 103 104 return (!VIFM_SAME(r->rt_children, old_children) || 105 !VIFM_SAME(r->rt_leaves, old_leaves)); 106 } 107 108 109 /* 110 * A new vif has come up -- update the children and leaf bitmaps in all route 111 * entries to take that into account. 112 */ 113 void 114 add_vif_to_routes(vifi_t vifi) 115 { 116 struct rtentry *r; 117 struct uvif *v; 118 119 v = &uvifs[vifi]; 120 for (r = routing_table; r != NULL; r = r->rt_next) { 121 if (r->rt_metric != UNREACHABLE && 122 !VIFM_ISSET(vifi, r->rt_children)) { 123 VIFM_SET(vifi, r->rt_children); 124 r->rt_dominants [vifi] = 0; 125 r->rt_subordinates[vifi] = 0; 126 if (v->uv_neighbors == NULL) { 127 VIFM_SET(vifi, r->rt_leaves); 128 r->rt_leaf_timers[vifi] = 0; 129 } 130 else { 131 VIFM_CLR(vifi, r->rt_leaves); 132 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME; 133 r->rt_flags |= RTF_LEAF_TIMING; 134 } 135 update_table_entry(r); 136 } 137 } 138 } 139 140 141 /* 142 * A vif has gone down -- expire all routes that have that vif as parent, 143 * and update the children bitmaps in all other route entries to take into 144 * account the failed vif. 145 */ 146 void 147 delete_vif_from_routes(vifi_t vifi) 148 { 149 struct rtentry *r; 150 151 for (r = routing_table; r != NULL; r = r->rt_next) { 152 if (r->rt_metric != UNREACHABLE) { 153 if (vifi == r->rt_parent) { 154 del_table_entry(r, 0, DEL_ALL_ROUTES); 155 r->rt_timer = ROUTE_EXPIRE_TIME; 156 r->rt_metric = UNREACHABLE; 157 r->rt_flags |= RTF_CHANGED; 158 routes_changed = TRUE; 159 } 160 else if (VIFM_ISSET(vifi, r->rt_children)) { 161 VIFM_CLR(vifi, r->rt_children); 162 VIFM_CLR(vifi, r->rt_leaves); 163 r->rt_subordinates[vifi] = 0; 164 r->rt_leaf_timers [vifi] = 0; 165 update_table_entry(r); 166 } 167 else { 168 r->rt_dominants[vifi] = 0; 169 } 170 } 171 } 172 } 173 174 175 /* 176 * A neighbor has failed or become unreachable. If that neighbor was 177 * considered a dominant or subordinate router in any route entries, 178 * take appropriate action. 179 */ 180 void 181 delete_neighbor_from_routes(u_int32_t addr, vifi_t vifi) 182 { 183 struct rtentry *r; 184 struct uvif *v; 185 186 v = &uvifs[vifi]; 187 for (r = routing_table; r != NULL; r = r->rt_next) { 188 if (r->rt_metric != UNREACHABLE) { 189 if (r->rt_dominants[vifi] == addr) { 190 VIFM_SET(vifi, r->rt_children); 191 r->rt_dominants [vifi] = 0; 192 r->rt_subordinates[vifi] = 0; 193 if (v->uv_neighbors == NULL) { 194 VIFM_SET(vifi, r->rt_leaves); 195 r->rt_leaf_timers[vifi] = 0; 196 } 197 else { 198 VIFM_CLR(vifi, r->rt_leaves); 199 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME; 200 r->rt_flags |= RTF_LEAF_TIMING; 201 } 202 update_table_entry(r); 203 } 204 else if (r->rt_subordinates[vifi] == addr) { 205 r->rt_subordinates[vifi] = 0; 206 if (v->uv_neighbors == NULL) { 207 VIFM_SET(vifi, r->rt_leaves); 208 update_table_entry(r); 209 } 210 else { 211 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME; 212 r->rt_flags |= RTF_LEAF_TIMING; 213 } 214 } 215 else if (v->uv_neighbors == NULL && 216 r->rt_leaf_timers[vifi] != 0) { 217 VIFM_SET(vifi, r->rt_leaves); 218 r->rt_leaf_timers[vifi] = 0; 219 update_table_entry(r); 220 } 221 } 222 } 223 } 224 225 226 /* 227 * Prepare for a sequence of ordered route updates by initializing a pointer 228 * to the start of the routing table. The pointer is used to remember our 229 * position in the routing table in order to avoid searching from the 230 * beginning for each update; this relies on having the route reports in 231 * a single message be in the same order as the route entries in the routing 232 * table. 233 */ 234 void 235 start_route_updates(void) 236 { 237 rtp = RT_ADDR; 238 } 239 240 241 /* 242 * Starting at the route entry following the one to which 'rtp' points, 243 * look for a route entry matching the specified origin and mask. If a 244 * match is found, return TRUE and leave 'rtp' pointing at the found entry. 245 * If no match is found, return FALSE and leave 'rtp' pointing to the route 246 * entry preceding the point at which the new origin should be inserted. 247 * This code is optimized for the normal case in which the first entry to 248 * be examined is the matching entry. 249 */ 250 static int 251 find_route(u_int32_t origin, u_int32_t mask) 252 { 253 struct rtentry *r; 254 255 r = rtp->rt_next; 256 while (r != NULL) { 257 if (origin == r->rt_origin && mask == r->rt_originmask) { 258 rtp = r; 259 return (TRUE); 260 } 261 if (ntohl(mask) < ntohl(r->rt_originmask) || 262 (mask == r->rt_originmask && 263 ntohl(origin) < ntohl(r->rt_origin))) { 264 rtp = r; 265 r = r->rt_next; 266 } 267 else break; 268 } 269 return (FALSE); 270 } 271 272 /* 273 * Create a new routing table entry for the specified origin and link it into 274 * the routing table. The shared variable 'rtp' is assumed to point to the 275 * routing entry after which the new one should be inserted. It is left 276 * pointing to the new entry. 277 * 278 * Only the origin, originmask, originwidth and flags fields are initialized 279 * in the new route entry; the caller is responsible for filling in the rest. 280 */ 281 static void 282 create_route(u_int32_t origin, u_int32_t mask) 283 { 284 struct rtentry *r; 285 286 if ((r = malloc(sizeof(struct rtentry) + 287 (2 * numvifs * sizeof(u_int32_t)) + 288 (numvifs * sizeof(u_int)))) == NULL) { 289 logit(LOG_ERR, 0, "ran out of memory"); /* fatal */ 290 } 291 r->rt_origin = origin; 292 r->rt_originmask = mask; 293 if (((char *)&mask)[3] != 0) r->rt_originwidth = 4; 294 else if (((char *)&mask)[2] != 0) r->rt_originwidth = 3; 295 else if (((char *)&mask)[1] != 0) r->rt_originwidth = 2; 296 else r->rt_originwidth = 1; 297 r->rt_flags = 0; 298 r->rt_dominants = (u_int32_t *)(r + 1); 299 r->rt_subordinates = (u_int32_t *)(r->rt_dominants + numvifs); 300 r->rt_leaf_timers = (u_int *)(r->rt_subordinates + numvifs); 301 r->rt_groups = NULL; 302 303 r->rt_next = rtp->rt_next; 304 rtp->rt_next = r; 305 r->rt_prev = rtp; 306 if (r->rt_next != NULL) 307 (r->rt_next)->rt_prev = r; 308 else 309 rt_end = r; 310 rtp = r; 311 ++nroutes; 312 } 313 314 315 /* 316 * Discard the routing table entry following the one to which 'prev_r' points. 317 */ 318 static void 319 discard_route(struct rtentry *prev_r) 320 { 321 struct rtentry *r; 322 323 r = prev_r->rt_next; 324 prev_r->rt_next = r->rt_next; 325 if (prev_r->rt_next != NULL) 326 (prev_r->rt_next)->rt_prev = prev_r; 327 else 328 rt_end = prev_r; 329 free((char *)r); 330 --nroutes; 331 } 332 333 334 /* 335 * Process a route report for a single origin, creating or updating the 336 * corresponding routing table entry if necessary. 'src' is either the 337 * address of a neighboring router from which the report arrived, or zero 338 * to indicate a change of status of one of our own interfaces. 339 */ 340 void 341 update_route(u_int32_t origin, u_int32_t mask, u_int metric, u_int32_t src, 342 vifi_t vifi) 343 { 344 struct rtentry *r; 345 u_int adj_metric; 346 347 /* 348 * Compute an adjusted metric, taking into account the cost of the 349 * subnet or tunnel over which the report arrived, and normalizing 350 * all unreachable/poisoned metrics into a single value. 351 */ 352 if (src != 0 && (metric < 1 || metric >= 2*UNREACHABLE)) { 353 logit(LOG_WARNING, 0, 354 "%s reports out-of-range metric %u for origin %s", 355 inet_fmt(src, s1), metric, inet_fmts(origin, mask, s2)); 356 return; 357 } 358 adj_metric = metric + uvifs[vifi].uv_metric; 359 if (adj_metric > UNREACHABLE) adj_metric = UNREACHABLE; 360 361 /* 362 * Look up the reported origin in the routing table. 363 */ 364 if (!find_route(origin, mask)) { 365 /* 366 * Not found. 367 * Don't create a new entry if the report says it's unreachable, 368 * or if the reported origin and mask are invalid. 369 */ 370 if (adj_metric == UNREACHABLE) { 371 return; 372 } 373 if (src != 0 && !inet_valid_subnet(origin, mask)) { 374 logit(LOG_WARNING, 0, 375 "%s reports an invalid origin (%s) and/or mask (%08x)", 376 inet_fmt(src, s1), inet_fmt(origin, s2), ntohl(mask)); 377 return; 378 } 379 380 /* 381 * OK, create the new routing entry. 'rtp' will be left pointing 382 * to the new entry. 383 */ 384 create_route(origin, mask); 385 386 /* 387 * Now "steal away" any sources that belong under this route 388 * by deleting any cache entries they might have created 389 * and allowing the kernel to re-request them. 390 */ 391 steal_sources(rtp); 392 393 rtp->rt_metric = UNREACHABLE; /* temporary; updated below */ 394 } 395 396 /* 397 * We now have a routing entry for the reported origin. Update it? 398 */ 399 r = rtp; 400 if (r->rt_metric == UNREACHABLE) { 401 /* 402 * The routing entry is for a formerly-unreachable or new origin. 403 * If the report claims reachability, update the entry to use 404 * the reported route. 405 */ 406 if (adj_metric == UNREACHABLE) 407 return; 408 409 r->rt_parent = vifi; 410 init_children_and_leaves(r, vifi); 411 412 r->rt_gateway = src; 413 r->rt_timer = 0; 414 r->rt_metric = adj_metric; 415 r->rt_flags |= RTF_CHANGED; 416 routes_changed = TRUE; 417 update_table_entry(r); 418 } 419 else if (src == r->rt_gateway) { 420 /* 421 * The report has come either from the interface directly-connected 422 * to the origin subnet (src and r->rt_gateway both equal zero) or 423 * from the gateway we have chosen as the best first-hop gateway back 424 * towards the origin (src and r->rt_gateway not equal zero). Reset 425 * the route timer and, if the reported metric has changed, update 426 * our entry accordingly. 427 */ 428 r->rt_timer = 0; 429 if (adj_metric == r->rt_metric) 430 return; 431 432 if (adj_metric == UNREACHABLE) { 433 del_table_entry(r, 0, DEL_ALL_ROUTES); 434 r->rt_timer = ROUTE_EXPIRE_TIME; 435 } 436 else if (adj_metric < r->rt_metric) { 437 if (init_children_and_leaves(r, vifi)) { 438 update_table_entry(r); 439 } 440 } 441 r->rt_metric = adj_metric; 442 r->rt_flags |= RTF_CHANGED; 443 routes_changed = TRUE; 444 } 445 else if (src == 0 || 446 (r->rt_gateway != 0 && 447 (adj_metric < r->rt_metric || 448 (adj_metric == r->rt_metric && 449 (ntohl(src) < ntohl(r->rt_gateway) || 450 r->rt_timer >= ROUTE_SWITCH_TIME))))) { 451 /* 452 * The report is for an origin we consider reachable; the report 453 * comes either from one of our own interfaces or from a gateway 454 * other than the one we have chosen as the best first-hop gateway 455 * back towards the origin. If the source of the update is one of 456 * our own interfaces, or if the origin is not a directly-connected 457 * subnet and the reported metric for that origin is better than 458 * what our routing entry says, update the entry to use the new 459 * gateway and metric. We also switch gateways if the reported 460 * metric is the same as the one in the route entry and the gateway 461 * associated with the route entry has not been heard from recently, 462 * or if the metric is the same but the reporting gateway has a lower 463 * IP address than the gateway associated with the route entry. 464 * Did you get all that? 465 */ 466 if (r->rt_parent != vifi || adj_metric < r->rt_metric) { 467 /* 468 * XXX Why do we do this if we are just changing the metric? 469 */ 470 r->rt_parent = vifi; 471 if (init_children_and_leaves(r, vifi)) { 472 update_table_entry(r); 473 } 474 } 475 r->rt_gateway = src; 476 r->rt_timer = 0; 477 r->rt_metric = adj_metric; 478 r->rt_flags |= RTF_CHANGED; 479 routes_changed = TRUE; 480 } 481 else if (vifi != r->rt_parent) { 482 /* 483 * The report came from a vif other than the route's parent vif. 484 * Update the children and leaf info, if necessary. 485 */ 486 if (VIFM_ISSET(vifi, r->rt_children)) { 487 /* 488 * Vif is a child vif for this route. 489 */ 490 if (metric < r->rt_metric || 491 (metric == r->rt_metric && 492 ntohl(src) < ntohl(uvifs[vifi].uv_lcl_addr))) { 493 /* 494 * Neighbor has lower metric to origin (or has same metric 495 * and lower IP address) -- it becomes the dominant router, 496 * and vif is no longer a child for me. 497 */ 498 VIFM_CLR(vifi, r->rt_children); 499 VIFM_CLR(vifi, r->rt_leaves); 500 r->rt_dominants [vifi] = src; 501 r->rt_subordinates[vifi] = 0; 502 r->rt_leaf_timers [vifi] = 0; 503 update_table_entry(r); 504 } 505 else if (metric > UNREACHABLE) { /* "poisoned reverse" */ 506 /* 507 * Neighbor considers this vif to be on path to route's 508 * origin; if no subordinate recorded, record this neighbor 509 * as subordinate and clear the leaf flag. 510 */ 511 if (r->rt_subordinates[vifi] == 0) { 512 VIFM_CLR(vifi, r->rt_leaves); 513 r->rt_subordinates[vifi] = src; 514 r->rt_leaf_timers [vifi] = 0; 515 update_table_entry(r); 516 } 517 } 518 else if (src == r->rt_subordinates[vifi]) { 519 /* 520 * Current subordinate no longer considers this vif to be on 521 * path to route's origin; it is no longer a subordinate 522 * router, and we set the leaf confirmation timer to give 523 * us time to hear from other subordinates. 524 */ 525 r->rt_subordinates[vifi] = 0; 526 if (uvifs[vifi].uv_neighbors == NULL || 527 uvifs[vifi].uv_neighbors->al_next == NULL) { 528 VIFM_SET(vifi, r->rt_leaves); 529 update_table_entry(r); 530 } 531 else { 532 r->rt_leaf_timers [vifi] = LEAF_CONFIRMATION_TIME; 533 r->rt_flags |= RTF_LEAF_TIMING; 534 } 535 } 536 537 } 538 else if (src == r->rt_dominants[vifi] && 539 (metric > r->rt_metric || 540 (metric == r->rt_metric && 541 ntohl(src) > ntohl(uvifs[vifi].uv_lcl_addr)))) { 542 /* 543 * Current dominant no longer has a lower metric to origin 544 * (or same metric and lower IP address); we adopt the vif 545 * as our own child. 546 */ 547 VIFM_SET(vifi, r->rt_children); 548 r->rt_dominants [vifi] = 0; 549 if (metric > UNREACHABLE) { 550 r->rt_subordinates[vifi] = src; 551 } 552 else if (uvifs[vifi].uv_neighbors == NULL || 553 uvifs[vifi].uv_neighbors->al_next == NULL) { 554 VIFM_SET(vifi, r->rt_leaves); 555 } 556 else { 557 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME; 558 r->rt_flags |= RTF_LEAF_TIMING; 559 } 560 update_table_entry(r); 561 } 562 } 563 } 564 565 566 /* 567 * On every timer interrupt, advance the timer in each routing entry. 568 */ 569 void 570 age_routes(void) 571 { 572 struct rtentry *r; 573 struct rtentry *prev_r; 574 vifi_t vifi; 575 576 for (prev_r = RT_ADDR, r = routing_table; 577 r != NULL; 578 prev_r = r, r = r->rt_next) { 579 580 if ((r->rt_timer += TIMER_INTERVAL) < ROUTE_EXPIRE_TIME) { 581 /* 582 * Route is still good; see if any leaf timers need to be 583 * advanced. 584 */ 585 if (r->rt_flags & RTF_LEAF_TIMING) { 586 r->rt_flags &= ~RTF_LEAF_TIMING; 587 for (vifi = 0; vifi < numvifs; ++vifi) { 588 if (r->rt_leaf_timers[vifi] != 0) { 589 /* 590 * Unlike other timers, leaf timers decrement. 591 */ 592 if ((r->rt_leaf_timers[vifi] -= TIMER_INTERVAL) == 0){ 593 #ifdef NOTYET 594 /* If the vif is a physical leaf but has neighbors, 595 * it is not a tree leaf. If I am a leaf, then no 596 * interface with neighbors is a tree leaf. */ 597 if (!(((uvifs[vifi].uv_flags & VIFF_LEAF) || 598 (vifs_with_neighbors == 1)) && 599 (uvifs[vifi].uv_neighbors != NULL))) { 600 #endif 601 VIFM_SET(vifi, r->rt_leaves); 602 update_table_entry(r); 603 #ifdef NOTYET 604 } 605 #endif 606 } 607 else { 608 r->rt_flags |= RTF_LEAF_TIMING; 609 } 610 } 611 } 612 } 613 } 614 else if (r->rt_timer >= ROUTE_DISCARD_TIME) { 615 /* 616 * Time to garbage-collect the route entry. 617 */ 618 del_table_entry(r, 0, DEL_ALL_ROUTES); 619 discard_route(prev_r); 620 r = prev_r; 621 } 622 else if (r->rt_metric != UNREACHABLE) { 623 /* 624 * Time to expire the route entry. If the gateway is zero, 625 * i.e., it is a route to a directly-connected subnet, just 626 * set the timer back to zero; such routes expire only when 627 * the interface to the subnet goes down. 628 */ 629 if (r->rt_gateway == 0) { 630 r->rt_timer = 0; 631 } 632 else { 633 del_table_entry(r, 0, DEL_ALL_ROUTES); 634 r->rt_metric = UNREACHABLE; 635 r->rt_flags |= RTF_CHANGED; 636 routes_changed = TRUE; 637 } 638 } 639 } 640 } 641 642 643 /* 644 * Mark all routes as unreachable. This function is called only from 645 * hup() in preparation for informing all neighbors that we are going 646 * off the air. For consistency, we ought also to delete all reachable 647 * route entries from the kernel, but since we are about to exit we rely 648 * on the kernel to do its own cleanup -- no point in making all those 649 * expensive kernel calls now. 650 */ 651 void 652 expire_all_routes(void) 653 { 654 struct rtentry *r; 655 656 for (r = routing_table; r != NULL; r = r->rt_next) { 657 r->rt_metric = UNREACHABLE; 658 r->rt_flags |= RTF_CHANGED; 659 routes_changed = TRUE; 660 } 661 } 662 663 664 /* 665 * Delete all the routes in the routing table. 666 */ 667 void 668 free_all_routes(void) 669 { 670 struct rtentry *r; 671 672 r = RT_ADDR; 673 674 while (r->rt_next) 675 discard_route(r); 676 } 677 678 679 /* 680 * Process an incoming neighbor probe message. 681 */ 682 void 683 accept_probe(u_int32_t src, u_int32_t dst, char *p, int datalen, 684 u_int32_t level) 685 { 686 vifi_t vifi; 687 688 if ((vifi = find_vif(src, dst)) == NO_VIF) { 689 logit(LOG_INFO, 0, 690 "ignoring probe from non-neighbor %s", inet_fmt(src, s1)); 691 return; 692 } 693 694 update_neighbor(vifi, src, DVMRP_PROBE, p, datalen, level); 695 } 696 697 struct newrt { 698 u_int32_t mask; 699 u_int32_t origin; 700 int metric; 701 int pad; 702 }; 703 704 static int 705 compare_rts(const void *rt1, const void *rt2) 706 { 707 struct newrt *r1 = (struct newrt *)rt1; 708 struct newrt *r2 = (struct newrt *)rt2; 709 u_int32_t m1 = ntohl(r1->mask); 710 u_int32_t m2 = ntohl(r2->mask); 711 u_int32_t o1, o2; 712 713 if (m1 > m2) 714 return (-1); 715 if (m1 < m2) 716 return (1); 717 718 /* masks are equal */ 719 o1 = ntohl(r1->origin); 720 o2 = ntohl(r2->origin); 721 if (o1 > o2) 722 return (-1); 723 if (o1 < o2) 724 return (1); 725 return (0); 726 } 727 728 /* 729 * Process an incoming route report message. 730 */ 731 void 732 accept_report(u_int32_t src, u_int32_t dst, char *p, int datalen, 733 u_int32_t level) 734 { 735 vifi_t vifi; 736 int width, i, nrt = 0; 737 int metric; 738 u_int32_t mask; 739 u_int32_t origin; 740 struct newrt rt[4096]; 741 742 if ((vifi = find_vif(src, dst)) == NO_VIF) { 743 logit(LOG_INFO, 0, 744 "ignoring route report from non-neighbor %s", inet_fmt(src, s1)); 745 return; 746 } 747 748 if (!update_neighbor(vifi, src, DVMRP_REPORT, NULL, 0, level)) 749 return; 750 751 if (datalen > 2*4096) { 752 logit(LOG_INFO, 0, 753 "ignoring oversize (%d bytes) route report from %s", 754 datalen, inet_fmt(src, s1)); 755 return; 756 } 757 758 while (datalen > 0) { /* Loop through per-mask lists. */ 759 760 if (datalen < 3) { 761 logit(LOG_WARNING, 0, 762 "received truncated route report from %s", 763 inet_fmt(src, s1)); 764 return; 765 } 766 ((u_char *)&mask)[0] = 0xff; width = 1; 767 if ((((u_char *)&mask)[1] = *p++) != 0) width = 2; 768 if ((((u_char *)&mask)[2] = *p++) != 0) width = 3; 769 if ((((u_char *)&mask)[3] = *p++) != 0) width = 4; 770 if (!inet_valid_mask(ntohl(mask))) { 771 logit(LOG_WARNING, 0, 772 "%s reports bogus netmask 0x%08x (%s)", 773 inet_fmt(src, s1), ntohl(mask), inet_fmt(mask, s2)); 774 return; 775 } 776 datalen -= 3; 777 778 do { /* Loop through (origin, metric) pairs */ 779 if (datalen < width + 1) { 780 logit(LOG_WARNING, 0, 781 "received truncated route report from %s", 782 inet_fmt(src, s1)); 783 return; 784 } 785 origin = 0; 786 for (i = 0; i < width; ++i) 787 ((char *)&origin)[i] = *p++; 788 metric = *p++; 789 datalen -= width + 1; 790 rt[nrt].mask = mask; 791 rt[nrt].origin = origin; 792 rt[nrt].metric = (metric & 0x7f); 793 ++nrt; 794 } while (!(metric & 0x80)); 795 } 796 797 qsort((char*)rt, nrt, sizeof(rt[0]), compare_rts); 798 start_route_updates(); 799 /* 800 * If the last entry is default, change mask from 0xff000000 to 0 801 */ 802 if (rt[nrt-1].origin == 0) 803 rt[nrt-1].mask = 0; 804 805 logit(LOG_DEBUG, 0, "Updating %d routes from %s to %s", nrt, 806 inet_fmt(src, s1), inet_fmt(dst, s2)); 807 for (i = 0; i < nrt; ++i) { 808 if (i != 0 && rt[i].origin == rt[i-1].origin && 809 rt[i].mask == rt[i-1].mask) { 810 logit(LOG_WARNING, 0, "%s reports duplicate route for %s", 811 inet_fmt(src, s1), inet_fmts(rt[i].origin, rt[i].mask, s2)); 812 continue; 813 } 814 update_route(rt[i].origin, rt[i].mask, rt[i].metric, 815 src, vifi); 816 } 817 818 if (routes_changed && !delay_change_reports) 819 report_to_all_neighbors(CHANGED_ROUTES); 820 } 821 822 823 /* 824 * Send a route report message to destination 'dst', via virtual interface 825 * 'vifi'. 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES. 826 */ 827 void 828 report(int which_routes, vifi_t vifi, u_int32_t dst) 829 { 830 struct rtentry *r; 831 char *p; 832 int i; 833 int datalen = 0; 834 int width = 0; 835 u_int32_t mask = 0; 836 u_int32_t src; 837 u_int32_t nflags; 838 839 src = uvifs[vifi].uv_lcl_addr; 840 841 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN; 842 843 #ifdef NOTYET 844 /* If I'm not a leaf, but the neighbor is a leaf, only advertise default */ 845 if ((vifs_with_neighbors != 1) && (uvifs[vifi].uv_flags & VIFF_LEAF)) { 846 *p++ = 0; /* 0xff000000 mask */ 847 *p++ = 0; 848 *p++ = 0; 849 *p++ = 0; /* class A net 0.0.0.0 == default */ 850 *p++ = 0x81; /*XXX metric 1, is this safe? */ 851 datalen += 5; 852 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 853 htonl(MROUTED_LEVEL), datalen); 854 return; 855 } 856 #endif 857 858 nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS; 859 860 for (r = rt_end; r != RT_ADDR; r = r->rt_prev) { 861 862 if (which_routes == CHANGED_ROUTES && !(r->rt_flags & RTF_CHANGED)) 863 continue; 864 865 /* 866 * If there is no room for this route in the current message, 867 * send the message and start a new one. 868 */ 869 if (datalen + ((r->rt_originmask == mask) ? 870 (width + 1) : 871 (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) { 872 *(p-1) |= 0x80; 873 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 874 htonl(MROUTED_LEVEL | nflags), datalen); 875 876 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN; 877 datalen = 0; 878 mask = 0; 879 } 880 881 if (r->rt_originmask != mask || datalen == 0) { 882 mask = r->rt_originmask; 883 width = r->rt_originwidth; 884 if (datalen != 0) *(p-1) |= 0x80; 885 *p++ = ((char *)&mask)[1]; 886 *p++ = ((char *)&mask)[2]; 887 *p++ = ((char *)&mask)[3]; 888 datalen += 3; 889 } 890 891 for (i = 0; i < width; ++i) 892 *p++ = ((char *)&(r->rt_origin))[i]; 893 894 *p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ? 895 (char)(r->rt_metric + UNREACHABLE) : /* "poisoned reverse" */ 896 (char)(r->rt_metric); 897 898 datalen += width + 1; 899 } 900 901 if (datalen != 0) { 902 *(p-1) |= 0x80; 903 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 904 htonl(MROUTED_LEVEL | nflags), datalen); 905 } 906 } 907 908 909 /* 910 * Send a route report message to all neighboring routers. 911 * 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES. 912 */ 913 void 914 report_to_all_neighbors(int which_routes) 915 { 916 vifi_t vifi; 917 struct uvif *v; 918 struct rtentry *r; 919 int routes_changed_before; 920 921 /* 922 * Remember the state of the global routes_changed flag before 923 * generating the reports, and clear the flag. 924 */ 925 routes_changed_before = routes_changed; 926 routes_changed = FALSE; 927 928 929 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) { 930 if (v->uv_neighbors != NULL) { 931 report(which_routes, vifi, 932 (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr 933 : dvmrp_group); 934 } 935 } 936 937 /* 938 * If there were changed routes before we sent the reports AND 939 * if no new changes occurred while sending the reports, clear 940 * the change flags in the individual route entries. If changes 941 * did occur while sending the reports, new reports will be 942 * generated at the next timer interrupt. 943 */ 944 if (routes_changed_before && !routes_changed) { 945 for (r = routing_table; r != NULL; r = r->rt_next) { 946 r->rt_flags &= ~RTF_CHANGED; 947 } 948 } 949 950 /* 951 * Set a flag to inhibit further reports of changed routes until the 952 * next timer interrupt. This is to alleviate update storms. 953 */ 954 delay_change_reports = TRUE; 955 } 956 957 /* 958 * Send a route report message to destination 'dst', via virtual interface 959 * 'vifi'. 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES. 960 */ 961 static int 962 report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst) 963 { 964 struct rtentry *r; 965 char *p; 966 int i; 967 int nrt = 0; 968 int datalen = 0; 969 int width = 0; 970 u_int32_t mask = 0; 971 u_int32_t src; 972 u_int32_t nflags; 973 974 src = uvifs[vifi].uv_lcl_addr; 975 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN; 976 977 nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS; 978 979 for (r = start_rt; r != RT_ADDR; r = r->rt_prev) { 980 981 #ifdef NOTYET 982 /* Don't send poisoned routes back to parents if I am a leaf */ 983 if ((vifs_with_neighbors == 1) && (r->rt_parent == vifi) 984 && (r->rt_metric > 1)) { 985 ++nrt; 986 continue; 987 } 988 #endif 989 990 /* 991 * If there is no room for this route in the current message, 992 * send it & return how many routes we sent. 993 */ 994 if (datalen + ((r->rt_originmask == mask) ? 995 (width + 1) : 996 (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) { 997 *(p-1) |= 0x80; 998 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 999 htonl(MROUTED_LEVEL | nflags), datalen); 1000 return (nrt); 1001 } 1002 if (r->rt_originmask != mask || datalen == 0) { 1003 mask = r->rt_originmask; 1004 width = r->rt_originwidth; 1005 if (datalen != 0) *(p-1) |= 0x80; 1006 *p++ = ((char *)&mask)[1]; 1007 *p++ = ((char *)&mask)[2]; 1008 *p++ = ((char *)&mask)[3]; 1009 datalen += 3; 1010 } 1011 for (i = 0; i < width; ++i) 1012 *p++ = ((char *)&(r->rt_origin))[i]; 1013 1014 *p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ? 1015 (char)(r->rt_metric + UNREACHABLE) : /* "poisoned reverse" */ 1016 (char)(r->rt_metric); 1017 ++nrt; 1018 datalen += width + 1; 1019 } 1020 if (datalen != 0) { 1021 *(p-1) |= 0x80; 1022 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 1023 htonl(MROUTED_LEVEL | nflags), datalen); 1024 } 1025 return (nrt); 1026 } 1027 1028 /* 1029 * send the next chunk of our routing table to all neighbors. 1030 * return the length of the smallest chunk we sent out. 1031 */ 1032 int 1033 report_next_chunk(void) 1034 { 1035 vifi_t vifi; 1036 struct uvif *v; 1037 struct rtentry *sr; 1038 int i, n = 0, min = 20000; 1039 static int start_rt; 1040 1041 if (nroutes <= 0) 1042 return (0); 1043 1044 /* 1045 * find this round's starting route. 1046 */ 1047 for (sr = rt_end, i = start_rt; --i >= 0; ) { 1048 sr = sr->rt_prev; 1049 if (sr == RT_ADDR) 1050 sr = rt_end; 1051 } 1052 1053 /* 1054 * send one chunk of routes starting at this round's start to 1055 * all our neighbors. 1056 */ 1057 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) { 1058 if ((v->uv_neighbors != NULL) 1059 #ifdef NOTYET 1060 && !(v->uv_flags & VIFF_LEAF) 1061 #endif 1062 ) { 1063 n = report_chunk(sr, vifi, 1064 (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr 1065 : dvmrp_group); 1066 if (n < min) 1067 min = n; 1068 } 1069 } 1070 if (min == 20000) 1071 min = 0; /* Neighborless router didn't send any routes */ 1072 1073 n = min; 1074 logit(LOG_INFO, 0, "update %d starting at %d of %d", 1075 n, (nroutes - start_rt), nroutes); 1076 1077 start_rt = (start_rt + n) % nroutes; 1078 return (n); 1079 } 1080 1081 1082 /* 1083 * Print the contents of the routing table on file 'fp'. 1084 */ 1085 void 1086 dump_routes(FILE *fp) 1087 { 1088 struct rtentry *r; 1089 vifi_t i; 1090 1091 1092 fprintf(fp, 1093 "Multicast Routing Table (%u %s)\n%s\n", 1094 nroutes, (nroutes == 1) ? "entry" : "entries", 1095 " Origin-Subnet From-Gateway Metric Tmr In-Vif Out-Vifs"); 1096 1097 for (r = routing_table; r != NULL; r = r->rt_next) { 1098 1099 fprintf(fp, " %-18s %-15s ", 1100 inet_fmts(r->rt_origin, r->rt_originmask, s1), 1101 (r->rt_gateway == 0) ? "" : inet_fmt(r->rt_gateway, s2)); 1102 1103 fprintf(fp, (r->rt_metric == UNREACHABLE) ? " NR " : "%4u ", 1104 r->rt_metric); 1105 1106 fprintf(fp, " %3u %3u ", r->rt_timer, r->rt_parent); 1107 1108 for (i = 0; i < numvifs; ++i) { 1109 if (VIFM_ISSET(i, r->rt_children)) { 1110 fprintf(fp, " %u%c", 1111 i, VIFM_ISSET(i, r->rt_leaves) ? '*' : ' '); 1112 } 1113 } 1114 fprintf(fp, "\n"); 1115 } 1116 fprintf(fp, "\n"); 1117 } 1118 1119 struct rtentry * 1120 determine_route(u_int32_t src) 1121 { 1122 struct rtentry *rt; 1123 1124 for (rt = routing_table; rt != NULL; rt = rt->rt_next) { 1125 if (rt->rt_origin == (src & rt->rt_originmask)) 1126 break; 1127 } 1128 return rt; 1129 } 1130