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