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