1 /* $NetBSD: route.c,v 1.11 2003/05/16 22:59:50 dsl 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(void) 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 = (struct rtentry *) 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), metric, 356 inet_fmts(origin, mask)); 357 return; 358 } 359 adj_metric = metric + uvifs[vifi].uv_metric; 360 if (adj_metric > UNREACHABLE) adj_metric = UNREACHABLE; 361 362 /* 363 * Look up the reported origin in the routing table. 364 */ 365 if (!find_route(origin, mask)) { 366 /* 367 * Not found. 368 * Don't create a new entry if the report says it's unreachable, 369 * or if the reported origin and mask are invalid. 370 */ 371 if (adj_metric == UNREACHABLE) { 372 return; 373 } 374 if (src != 0 && !inet_valid_subnet(origin, mask)) { 375 logit(LOG_WARNING, 0, 376 "%s reports an invalid origin (%s) and/or mask (%08x)", 377 inet_fmt(src), 378 inet_fmt(origin), ntohl(mask)); 379 return; 380 } 381 382 /* 383 * OK, create the new routing entry. 'rtp' will be left pointing 384 * to the new entry. 385 */ 386 create_route(origin, mask); 387 388 /* 389 * Now "steal away" any sources that belong under this route 390 * by deleting any cache entries they might have created 391 * and allowing the kernel to re-request them. 392 */ 393 steal_sources(rtp); 394 395 rtp->rt_metric = UNREACHABLE; /* temporary; updated below */ 396 } 397 398 /* 399 * We now have a routing entry for the reported origin. Update it? 400 */ 401 r = rtp; 402 if (r->rt_metric == UNREACHABLE) { 403 /* 404 * The routing entry is for a formerly-unreachable or new origin. 405 * If the report claims reachability, update the entry to use 406 * the reported route. 407 */ 408 if (adj_metric == UNREACHABLE) 409 return; 410 411 r->rt_parent = vifi; 412 init_children_and_leaves(r, vifi); 413 414 r->rt_gateway = src; 415 r->rt_timer = 0; 416 r->rt_metric = adj_metric; 417 r->rt_flags |= RTF_CHANGED; 418 routes_changed = TRUE; 419 update_table_entry(r); 420 } 421 else if (src == r->rt_gateway) { 422 /* 423 * The report has come either from the interface directly-connected 424 * to the origin subnet (src and r->rt_gateway both equal zero) or 425 * from the gateway we have chosen as the best first-hop gateway back 426 * towards the origin (src and r->rt_gateway not equal zero). Reset 427 * the route timer and, if the reported metric has changed, update 428 * our entry accordingly. 429 */ 430 r->rt_timer = 0; 431 if (adj_metric == r->rt_metric) 432 return; 433 434 if (adj_metric == UNREACHABLE) { 435 del_table_entry(r, 0, DEL_ALL_ROUTES); 436 r->rt_timer = ROUTE_EXPIRE_TIME; 437 } 438 else if (adj_metric < r->rt_metric) { 439 if (init_children_and_leaves(r, vifi)) { 440 update_table_entry(r); 441 } 442 } 443 r->rt_metric = adj_metric; 444 r->rt_flags |= RTF_CHANGED; 445 routes_changed = TRUE; 446 } 447 else if (src == 0 || 448 (r->rt_gateway != 0 && 449 (adj_metric < r->rt_metric || 450 (adj_metric == r->rt_metric && 451 (ntohl(src) < ntohl(r->rt_gateway) || 452 r->rt_timer >= ROUTE_SWITCH_TIME))))) { 453 /* 454 * The report is for an origin we consider reachable; the report 455 * comes either from one of our own interfaces or from a gateway 456 * other than the one we have chosen as the best first-hop gateway 457 * back towards the origin. If the source of the update is one of 458 * our own interfaces, or if the origin is not a directly-connected 459 * subnet and the reported metric for that origin is better than 460 * what our routing entry says, update the entry to use the new 461 * gateway and metric. We also switch gateways if the reported 462 * metric is the same as the one in the route entry and the gateway 463 * associated with the route entry has not been heard from recently, 464 * or if the metric is the same but the reporting gateway has a lower 465 * IP address than the gateway associated with the route entry. 466 * Did you get all that? 467 */ 468 if (r->rt_parent != vifi || adj_metric < r->rt_metric) { 469 /* 470 * XXX Why do we do this if we are just changing the metric? 471 */ 472 r->rt_parent = vifi; 473 if (init_children_and_leaves(r, vifi)) { 474 update_table_entry(r); 475 } 476 } 477 r->rt_gateway = src; 478 r->rt_timer = 0; 479 r->rt_metric = adj_metric; 480 r->rt_flags |= RTF_CHANGED; 481 routes_changed = TRUE; 482 } 483 else if (vifi != r->rt_parent) { 484 /* 485 * The report came from a vif other than the route's parent vif. 486 * Update the children and leaf info, if necessary. 487 */ 488 if (VIFM_ISSET(vifi, r->rt_children)) { 489 /* 490 * Vif is a child vif for this route. 491 */ 492 if (metric < r->rt_metric || 493 (metric == r->rt_metric && 494 ntohl(src) < ntohl(uvifs[vifi].uv_lcl_addr))) { 495 /* 496 * Neighbor has lower metric to origin (or has same metric 497 * and lower IP address) -- it becomes the dominant router, 498 * and vif is no longer a child for me. 499 */ 500 VIFM_CLR(vifi, r->rt_children); 501 VIFM_CLR(vifi, r->rt_leaves); 502 r->rt_dominants [vifi] = src; 503 r->rt_subordinates[vifi] = 0; 504 r->rt_leaf_timers [vifi] = 0; 505 update_table_entry(r); 506 } 507 else if (metric > UNREACHABLE) { /* "poisoned reverse" */ 508 /* 509 * Neighbor considers this vif to be on path to route's 510 * origin; if no subordinate recorded, record this neighbor 511 * as subordinate and clear the leaf flag. 512 */ 513 if (r->rt_subordinates[vifi] == 0) { 514 VIFM_CLR(vifi, r->rt_leaves); 515 r->rt_subordinates[vifi] = src; 516 r->rt_leaf_timers [vifi] = 0; 517 update_table_entry(r); 518 } 519 } 520 else if (src == r->rt_subordinates[vifi]) { 521 /* 522 * Current subordinate no longer considers this vif to be on 523 * path to route's origin; it is no longer a subordinate 524 * router, and we set the leaf confirmation timer to give 525 * us time to hear from other subordinates. 526 */ 527 r->rt_subordinates[vifi] = 0; 528 if (uvifs[vifi].uv_neighbors == NULL || 529 uvifs[vifi].uv_neighbors->al_next == NULL) { 530 VIFM_SET(vifi, r->rt_leaves); 531 update_table_entry(r); 532 } 533 else { 534 r->rt_leaf_timers [vifi] = LEAF_CONFIRMATION_TIME; 535 r->rt_flags |= RTF_LEAF_TIMING; 536 } 537 } 538 539 } 540 else if (src == r->rt_dominants[vifi] && 541 (metric > r->rt_metric || 542 (metric == r->rt_metric && 543 ntohl(src) > ntohl(uvifs[vifi].uv_lcl_addr)))) { 544 /* 545 * Current dominant no longer has a lower metric to origin 546 * (or same metric and lower IP address); we adopt the vif 547 * as our own child. 548 */ 549 VIFM_SET(vifi, r->rt_children); 550 r->rt_dominants [vifi] = 0; 551 if (metric > UNREACHABLE) { 552 r->rt_subordinates[vifi] = src; 553 } 554 else if (uvifs[vifi].uv_neighbors == NULL || 555 uvifs[vifi].uv_neighbors->al_next == NULL) { 556 VIFM_SET(vifi, r->rt_leaves); 557 } 558 else { 559 r->rt_leaf_timers[vifi] = LEAF_CONFIRMATION_TIME; 560 r->rt_flags |= RTF_LEAF_TIMING; 561 } 562 update_table_entry(r); 563 } 564 } 565 } 566 567 568 /* 569 * On every timer interrupt, advance the timer in each routing entry. 570 */ 571 void 572 age_routes(void) 573 { 574 struct rtentry *r; 575 struct rtentry *prev_r; 576 vifi_t vifi; 577 578 for (prev_r = RT_ADDR, r = routing_table; 579 r != NULL; 580 prev_r = r, r = r->rt_next) { 581 582 if ((r->rt_timer += TIMER_INTERVAL) < ROUTE_EXPIRE_TIME) { 583 /* 584 * Route is still good; see if any leaf timers need to be 585 * advanced. 586 */ 587 if (r->rt_flags & RTF_LEAF_TIMING) { 588 r->rt_flags &= ~RTF_LEAF_TIMING; 589 for (vifi = 0; vifi < numvifs; ++vifi) { 590 if (r->rt_leaf_timers[vifi] != 0) { 591 /* 592 * Unlike other timers, leaf timers decrement. 593 */ 594 if ((r->rt_leaf_timers[vifi] -= TIMER_INTERVAL) == 0){ 595 #ifdef NOTYET 596 /* If the vif is a physical leaf but has neighbors, 597 * it is not a tree leaf. If I am a leaf, then no 598 * interface with neighbors is a tree leaf. */ 599 if (!(((uvifs[vifi].uv_flags & VIFF_LEAF) || 600 (vifs_with_neighbors == 1)) && 601 (uvifs[vifi].uv_neighbors != NULL))) { 602 #endif 603 VIFM_SET(vifi, r->rt_leaves); 604 update_table_entry(r); 605 #ifdef NOTYET 606 } 607 #endif 608 } 609 else { 610 r->rt_flags |= RTF_LEAF_TIMING; 611 } 612 } 613 } 614 } 615 } 616 else if (r->rt_timer >= ROUTE_DISCARD_TIME) { 617 /* 618 * Time to garbage-collect the route entry. 619 */ 620 del_table_entry(r, 0, DEL_ALL_ROUTES); 621 discard_route(prev_r); 622 r = prev_r; 623 } 624 else if (r->rt_metric != UNREACHABLE) { 625 /* 626 * Time to expire the route entry. If the gateway is zero, 627 * i.e., it is a route to a directly-connected subnet, just 628 * set the timer back to zero; such routes expire only when 629 * the interface to the subnet goes down. 630 */ 631 if (r->rt_gateway == 0) { 632 r->rt_timer = 0; 633 } 634 else { 635 del_table_entry(r, 0, DEL_ALL_ROUTES); 636 r->rt_metric = UNREACHABLE; 637 r->rt_flags |= RTF_CHANGED; 638 routes_changed = TRUE; 639 } 640 } 641 } 642 } 643 644 645 /* 646 * Mark all routes as unreachable. This function is called only from 647 * hup() in preparation for informing all neighbors that we are going 648 * off the air. For consistency, we ought also to delete all reachable 649 * route entries from the kernel, but since we are about to exit we rely 650 * on the kernel to do its own cleanup -- no point in making all those 651 * expensive kernel calls now. 652 */ 653 void 654 expire_all_routes(void) 655 { 656 struct rtentry *r; 657 658 for (r = routing_table; r != NULL; r = r->rt_next) { 659 r->rt_metric = UNREACHABLE; 660 r->rt_flags |= RTF_CHANGED; 661 routes_changed = TRUE; 662 } 663 } 664 665 666 /* 667 * Delete all the routes in the routing table. 668 */ 669 void 670 free_all_routes(void) 671 { 672 struct rtentry *r; 673 674 r = RT_ADDR; 675 676 while (r->rt_next) 677 discard_route(r); 678 } 679 680 681 /* 682 * Process an incoming neighbor probe message. 683 */ 684 void 685 accept_probe(u_int32_t src, u_int32_t dst, char *p, int datalen, 686 u_int32_t level) 687 { 688 vifi_t vifi; 689 690 if ((vifi = find_vif(src, dst)) == NO_VIF) { 691 logit(LOG_INFO, 0, 692 "ignoring probe from non-neighbor %s", inet_fmt(src)); 693 return; 694 } 695 696 update_neighbor(vifi, src, DVMRP_PROBE, p, datalen, level); 697 } 698 699 struct newrt { 700 u_int32_t mask; 701 u_int32_t origin; 702 int metric; 703 int pad; 704 }; 705 706 static int 707 compare_rts(const void *rt1, const void *rt2) 708 { 709 struct newrt *r1 = (struct newrt *)rt1; 710 struct newrt *r2 = (struct newrt *)rt2; 711 u_int32_t m1 = ntohl(r1->mask); 712 u_int32_t m2 = ntohl(r2->mask); 713 u_int32_t o1, o2; 714 715 if (m1 > m2) 716 return (-1); 717 if (m1 < m2) 718 return (1); 719 720 /* masks are equal */ 721 o1 = ntohl(r1->origin); 722 o2 = ntohl(r2->origin); 723 if (o1 > o2) 724 return (-1); 725 if (o1 < o2) 726 return (1); 727 return (0); 728 } 729 730 /* 731 * Process an incoming route report message. 732 */ 733 void 734 accept_report(u_int32_t src, u_int32_t dst, char *p, int datalen, 735 u_int32_t level) 736 { 737 vifi_t vifi; 738 int width, i, nrt = 0; 739 int metric; 740 u_int32_t mask; 741 u_int32_t origin; 742 struct newrt rt[4096]; 743 744 if ((vifi = find_vif(src, dst)) == NO_VIF) { 745 logit(LOG_INFO, 0, 746 "ignoring route report from non-neighbor %s", inet_fmt(src)); 747 return; 748 } 749 750 if (!update_neighbor(vifi, src, DVMRP_REPORT, NULL, 0, level)) 751 return; 752 753 if (datalen > 2*4096) { 754 logit(LOG_INFO, 0, 755 "ignoring oversize (%d bytes) route report from %s", 756 datalen, inet_fmt(src)); 757 return; 758 } 759 760 while (datalen > 0) { /* Loop through per-mask lists. */ 761 762 if (datalen < 3) { 763 logit(LOG_WARNING, 0, 764 "received truncated route report from %s", 765 inet_fmt(src)); 766 return; 767 } 768 ((u_char *)&mask)[0] = 0xff; width = 1; 769 if ((((u_char *)&mask)[1] = *p++) != 0) width = 2; 770 if ((((u_char *)&mask)[2] = *p++) != 0) width = 3; 771 if ((((u_char *)&mask)[3] = *p++) != 0) width = 4; 772 if (!inet_valid_mask(ntohl(mask))) { 773 logit(LOG_WARNING, 0, 774 "%s reports bogus netmask 0x%08x (%s)", 775 inet_fmt(src), ntohl(mask), 776 inet_fmt(mask)); 777 return; 778 } 779 datalen -= 3; 780 781 do { /* Loop through (origin, metric) pairs */ 782 if (datalen < width + 1) { 783 logit(LOG_WARNING, 0, 784 "received truncated route report from %s", 785 inet_fmt(src)); 786 return; 787 } 788 origin = 0; 789 for (i = 0; i < width; ++i) 790 ((char *)&origin)[i] = *p++; 791 metric = *p++; 792 datalen -= width + 1; 793 rt[nrt].mask = mask; 794 rt[nrt].origin = origin; 795 rt[nrt].metric = (metric & 0x7f); 796 ++nrt; 797 } while (!(metric & 0x80)); 798 } 799 800 qsort((char*)rt, nrt, sizeof(rt[0]), compare_rts); 801 start_route_updates(); 802 /* 803 * If the last entry is default, change mask from 0xff000000 to 0 804 */ 805 if (rt[nrt-1].origin == 0) 806 rt[nrt-1].mask = 0; 807 808 logit(LOG_DEBUG, 0, "Updating %d routes from %s to %s", nrt, 809 inet_fmt(src), inet_fmt(dst)); 810 for (i = 0; i < nrt; ++i) { 811 if (i != 0 && rt[i].origin == rt[i-1].origin && 812 rt[i].mask == rt[i-1].mask) { 813 logit(LOG_WARNING, 0, "%s reports duplicate route for %s", 814 inet_fmt(src), 815 inet_fmts(rt[i].origin, rt[i].mask)); 816 continue; 817 } 818 update_route(rt[i].origin, rt[i].mask, rt[i].metric, 819 src, vifi); 820 } 821 822 if (routes_changed && !delay_change_reports) 823 report_to_all_neighbors(CHANGED_ROUTES); 824 } 825 826 827 /* 828 * Send a route report message to destination 'dst', via virtual interface 829 * 'vifi'. 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES. 830 */ 831 void 832 report(int which_routes, vifi_t vifi, u_int32_t dst) 833 { 834 struct rtentry *r; 835 char *p; 836 int i; 837 int datalen = 0; 838 int width = 0; 839 u_int32_t mask = 0; 840 u_int32_t src; 841 u_int32_t nflags; 842 843 src = uvifs[vifi].uv_lcl_addr; 844 845 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN; 846 847 #ifdef NOTYET 848 /* If I'm not a leaf, but the neighbor is a leaf, only advertise default */ 849 if ((vifs_with_neighbors != 1) && (uvifs[vifi].uv_flags & VIFF_LEAF)) { 850 *p++ = 0; /* 0xff000000 mask */ 851 *p++ = 0; 852 *p++ = 0; 853 *p++ = 0; /* class A net 0.0.0.0 == default */ 854 *p++ = 0x81; /*XXX metric 1, is this safe? */ 855 datalen += 5; 856 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 857 htonl(MROUTED_LEVEL), datalen); 858 return; 859 } 860 #endif 861 862 nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS; 863 864 for (r = rt_end; r != RT_ADDR; r = r->rt_prev) { 865 866 if (which_routes == CHANGED_ROUTES && !(r->rt_flags & RTF_CHANGED)) 867 continue; 868 869 /* 870 * If there is no room for this route in the current message, 871 * send the message and start a new one. 872 */ 873 if (datalen + ((r->rt_originmask == mask) ? 874 (width + 1) : 875 (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) { 876 *(p-1) |= 0x80; 877 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 878 htonl(MROUTED_LEVEL | nflags), datalen); 879 880 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN; 881 datalen = 0; 882 mask = 0; 883 } 884 885 if (r->rt_originmask != mask || datalen == 0) { 886 mask = r->rt_originmask; 887 width = r->rt_originwidth; 888 if (datalen != 0) *(p-1) |= 0x80; 889 *p++ = ((char *)&mask)[1]; 890 *p++ = ((char *)&mask)[2]; 891 *p++ = ((char *)&mask)[3]; 892 datalen += 3; 893 } 894 895 for (i = 0; i < width; ++i) 896 *p++ = ((char *)&(r->rt_origin))[i]; 897 898 *p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ? 899 (char)(r->rt_metric + UNREACHABLE) : /* "poisoned reverse" */ 900 (char)(r->rt_metric); 901 902 datalen += width + 1; 903 } 904 905 if (datalen != 0) { 906 *(p-1) |= 0x80; 907 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 908 htonl(MROUTED_LEVEL | nflags), datalen); 909 } 910 } 911 912 913 /* 914 * Send a route report message to all neighboring routers. 915 * 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES. 916 */ 917 void 918 report_to_all_neighbors(int which_routes) 919 { 920 vifi_t vifi; 921 struct uvif *v; 922 struct rtentry *r; 923 int routes_changed_before; 924 925 /* 926 * Remember the state of the global routes_changed flag before 927 * generating the reports, and clear the flag. 928 */ 929 routes_changed_before = routes_changed; 930 routes_changed = FALSE; 931 932 933 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) { 934 if (v->uv_neighbors != NULL) { 935 report(which_routes, vifi, 936 (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr 937 : dvmrp_group); 938 } 939 } 940 941 /* 942 * If there were changed routes before we sent the reports AND 943 * if no new changes occurred while sending the reports, clear 944 * the change flags in the individual route entries. If changes 945 * did occur while sending the reports, new reports will be 946 * generated at the next timer interrupt. 947 */ 948 if (routes_changed_before && !routes_changed) { 949 for (r = routing_table; r != NULL; r = r->rt_next) { 950 r->rt_flags &= ~RTF_CHANGED; 951 } 952 } 953 954 /* 955 * Set a flag to inhibit further reports of changed routes until the 956 * next timer interrupt. This is to alleviate update storms. 957 */ 958 delay_change_reports = TRUE; 959 } 960 961 /* 962 * Send a route report message to destination 'dst', via virtual interface 963 * 'vifi'. 'which_routes' specifies ALL_ROUTES or CHANGED_ROUTES. 964 */ 965 static int 966 report_chunk(struct rtentry *start_rt, vifi_t vifi, u_int32_t dst) 967 { 968 struct rtentry *r; 969 char *p; 970 int i; 971 int nrt = 0; 972 int datalen = 0; 973 int width = 0; 974 u_int32_t mask = 0; 975 u_int32_t src; 976 u_int32_t nflags; 977 978 src = uvifs[vifi].uv_lcl_addr; 979 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN; 980 981 nflags = (uvifs[vifi].uv_flags & VIFF_LEAF) ? 0 : LEAF_FLAGS; 982 983 for (r = start_rt; r != RT_ADDR; r = r->rt_prev) { 984 985 #ifdef NOTYET 986 /* Don't send poisoned routes back to parents if I am a leaf */ 987 if ((vifs_with_neighbors == 1) && (r->rt_parent == vifi) 988 && (r->rt_metric > 1)) { 989 ++nrt; 990 continue; 991 } 992 #endif 993 994 /* 995 * If there is no room for this route in the current message, 996 * send it & return how many routes we sent. 997 */ 998 if (datalen + ((r->rt_originmask == mask) ? 999 (width + 1) : 1000 (r->rt_originwidth + 4)) > MAX_DVMRP_DATA_LEN) { 1001 *(p-1) |= 0x80; 1002 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 1003 htonl(MROUTED_LEVEL | nflags), datalen); 1004 return (nrt); 1005 } 1006 if (r->rt_originmask != mask || datalen == 0) { 1007 mask = r->rt_originmask; 1008 width = r->rt_originwidth; 1009 if (datalen != 0) *(p-1) |= 0x80; 1010 *p++ = ((char *)&mask)[1]; 1011 *p++ = ((char *)&mask)[2]; 1012 *p++ = ((char *)&mask)[3]; 1013 datalen += 3; 1014 } 1015 for (i = 0; i < width; ++i) 1016 *p++ = ((char *)&(r->rt_origin))[i]; 1017 1018 *p++ = (r->rt_parent == vifi && r->rt_metric != UNREACHABLE) ? 1019 (char)(r->rt_metric + UNREACHABLE) : /* "poisoned reverse" */ 1020 (char)(r->rt_metric); 1021 ++nrt; 1022 datalen += width + 1; 1023 } 1024 if (datalen != 0) { 1025 *(p-1) |= 0x80; 1026 send_igmp(src, dst, IGMP_DVMRP, DVMRP_REPORT, 1027 htonl(MROUTED_LEVEL | nflags), datalen); 1028 } 1029 return (nrt); 1030 } 1031 1032 /* 1033 * send the next chunk of our routing table to all neighbors. 1034 * return the length of the smallest chunk we sent out. 1035 */ 1036 int 1037 report_next_chunk(void) 1038 { 1039 vifi_t vifi; 1040 struct uvif *v; 1041 struct rtentry *sr; 1042 int i, n = 0, min = 20000; 1043 static int start_rt; 1044 1045 if (nroutes <= 0) 1046 return (0); 1047 1048 /* 1049 * find this round's starting route. 1050 */ 1051 for (sr = rt_end, i = start_rt; --i >= 0; ) { 1052 sr = sr->rt_prev; 1053 if (sr == RT_ADDR) 1054 sr = rt_end; 1055 } 1056 1057 /* 1058 * send one chunk of routes starting at this round's start to 1059 * all our neighbors. 1060 */ 1061 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) { 1062 if ((v->uv_neighbors != NULL) 1063 #ifdef NOTYET 1064 && !(v->uv_flags & VIFF_LEAF) 1065 #endif 1066 ) { 1067 n = report_chunk(sr, vifi, 1068 (v->uv_flags & VIFF_TUNNEL) ? v->uv_rmt_addr 1069 : dvmrp_group); 1070 if (n < min) 1071 min = n; 1072 } 1073 } 1074 if (min == 20000) 1075 min = 0; /* Neighborless router didn't send any routes */ 1076 1077 n = min; 1078 logit(LOG_INFO, 0, "update %d starting at %d of %d", 1079 n, (nroutes - start_rt), nroutes); 1080 1081 start_rt = (start_rt + n) % nroutes; 1082 return (n); 1083 } 1084 1085 1086 /* 1087 * Print the contents of the routing table on file 'fp'. 1088 */ 1089 void 1090 dump_routes(FILE *fp) 1091 { 1092 struct rtentry *r; 1093 vifi_t i; 1094 1095 1096 fprintf(fp, 1097 "Multicast Routing Table (%u %s)\n%s\n", 1098 nroutes, (nroutes == 1) ? "entry" : "entries", 1099 " Origin-Subnet From-Gateway Metric Tmr In-Vif Out-Vifs"); 1100 1101 for (r = routing_table; r != NULL; r = r->rt_next) { 1102 1103 fprintf(fp, " %-18s %-15s ", 1104 inet_fmts(r->rt_origin, r->rt_originmask), 1105 (r->rt_gateway == 0) ? "" : inet_fmt(r->rt_gateway)); 1106 1107 fprintf(fp, (r->rt_metric == UNREACHABLE) ? " NR " : "%4u ", 1108 r->rt_metric); 1109 1110 fprintf(fp, " %3u %3u ", r->rt_timer, r->rt_parent); 1111 1112 for (i = 0; i < numvifs; ++i) { 1113 if (VIFM_ISSET(i, r->rt_children)) { 1114 fprintf(fp, " %u%c", 1115 i, VIFM_ISSET(i, r->rt_leaves) ? '*' : ' '); 1116 } 1117 } 1118 fprintf(fp, "\n"); 1119 } 1120 fprintf(fp, "\n"); 1121 } 1122 1123 struct rtentry * 1124 determine_route(u_int32_t src) 1125 { 1126 struct rtentry *rt; 1127 1128 for (rt = routing_table; rt != NULL; rt = rt->rt_next) { 1129 if (rt->rt_origin == (src & rt->rt_originmask)) 1130 break; 1131 } 1132 return rt; 1133 } 1134