1/* 2 * This file is free software: you may copy, redistribute and/or modify it 3 * under the terms of the GNU General Public License as published by the 4 * Free Software Foundation, either version 2 of the License, or (at your 5 * option) any later version. 6 * 7 * This file is distributed in the hope that it will be useful, but 8 * WITHOUT ANY WARRANTY; without even the implied warranty of 9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 10 * General Public License for more details. 11 * 12 * You should have received a copy of the GNU General Public License 13 * along with this program. If not, see <http://www.gnu.org/licenses/>. 14 * 15 * This file incorporates work covered by the following copyright and 16 * permission notice: 17 * 18Copyright (c) 2007, 2008 by Juliusz Chroboczek 19Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek 20 21Permission is hereby granted, free of charge, to any person obtaining a copy 22of this software and associated documentation files (the "Software"), to deal 23in the Software without restriction, including without limitation the rights 24to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 25copies of the Software, and to permit persons to whom the Software is 26furnished to do so, subject to the following conditions: 27 28The above copyright notice and this permission notice shall be included in 29all copies or substantial portions of the Software. 30 31THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 32IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 33FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 34AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 35LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 36OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 37THE SOFTWARE. 38*/ 39 40#include <zebra.h> 41#include "if.h" 42 43#include "babeld.h" 44#include "util.h" 45#include "kernel.h" 46#include "babel_interface.h" 47#include "source.h" 48#include "neighbour.h" 49#include "route.h" 50#include "xroute.h" 51#include "message.h" 52#include "resend.h" 53 54static void consider_route(struct babel_route *route); 55 56struct babel_route **routes = NULL; 57static int route_slots = 0, max_route_slots = 0; 58int kernel_metric = 0; 59int allow_duplicates = -1; 60int diversity_kind = DIVERSITY_NONE; 61int diversity_factor = 256; /* in units of 1/256 */ 62int keep_unfeasible = 0; 63 64/* We maintain a list of "slots", ordered by prefix. Every slot 65 contains a linked list of the routes to this prefix, with the 66 installed route, if any, at the head of the list. */ 67 68static int 69route_compare(const unsigned char *prefix, unsigned char plen, 70 struct babel_route *route) 71{ 72 int i = memcmp(prefix, route->src->prefix, 16); 73 if(i != 0) 74 return i; 75 76 if(plen < route->src->plen) 77 return -1; 78 else if(plen > route->src->plen) 79 return 1; 80 else 81 return 0; 82} 83 84/* Performs binary search, returns -1 in case of failure. In the latter 85 case, new_return is the place where to insert the new element. */ 86 87static int 88find_route_slot(const unsigned char *prefix, unsigned char plen, 89 int *new_return) 90{ 91 int p, m, g, c; 92 93 if(route_slots < 1) { 94 if(new_return) 95 *new_return = 0; 96 return -1; 97 } 98 99 p = 0; g = route_slots - 1; 100 101 do { 102 m = (p + g) / 2; 103 c = route_compare(prefix, plen, routes[m]); 104 if(c == 0) 105 return m; 106 else if(c < 0) 107 g = m - 1; 108 else 109 p = m + 1; 110 } while(p <= g); 111 112 if(new_return) 113 *new_return = p; 114 115 return -1; 116} 117 118struct babel_route * 119find_route(const unsigned char *prefix, unsigned char plen, 120 struct neighbour *neigh, const unsigned char *nexthop) 121{ 122 struct babel_route *route; 123 int i = find_route_slot(prefix, plen, NULL); 124 125 if(i < 0) 126 return NULL; 127 128 route = routes[i]; 129 130 while(route) { 131 if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0) 132 return route; 133 route = route->next; 134 } 135 136 return NULL; 137} 138 139struct babel_route * 140find_installed_route(const unsigned char *prefix, unsigned char plen) 141{ 142 int i = find_route_slot(prefix, plen, NULL); 143 144 if(i >= 0 && routes[i]->installed) 145 return routes[i]; 146 147 return NULL; 148} 149 150/* Returns an overestimate of the number of installed routes. */ 151int 152installed_routes_estimate(void) 153{ 154 return route_slots; 155} 156 157static int 158resize_route_table(int new_slots) 159{ 160 struct babel_route **new_routes; 161 assert(new_slots >= route_slots); 162 163 if(new_slots == 0) { 164 new_routes = NULL; 165 free(routes); 166 } else { 167 new_routes = realloc(routes, new_slots * sizeof(struct babel_route*)); 168 if(new_routes == NULL) 169 return -1; 170 } 171 172 max_route_slots = new_slots; 173 routes = new_routes; 174 return 1; 175} 176 177/* Insert a route into the table. If successful, retains the route. 178 On failure, caller must free the route. */ 179static struct babel_route * 180insert_route(struct babel_route *route) 181{ 182 int i, n; 183 184 assert(!route->installed); 185 186 i = find_route_slot(route->src->prefix, route->src->plen, &n); 187 188 if(i < 0) { 189 if(route_slots >= max_route_slots) 190 resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots); 191 if(route_slots >= max_route_slots) 192 return NULL; 193 route->next = NULL; 194 if(n < route_slots) 195 memmove(routes + n + 1, routes + n, 196 (route_slots - n) * sizeof(struct babel_route*)); 197 route_slots++; 198 routes[n] = route; 199 } else { 200 struct babel_route *r; 201 r = routes[i]; 202 while(r->next) 203 r = r->next; 204 r->next = route; 205 route->next = NULL; 206 } 207 208 return route; 209} 210 211void 212flush_route(struct babel_route *route) 213{ 214 int i; 215 struct source *src; 216 unsigned oldmetric; 217 int lost = 0; 218 219 oldmetric = route_metric(route); 220 src = route->src; 221 222 if(route->installed) { 223 uninstall_route(route); 224 lost = 1; 225 } 226 227 i = find_route_slot(route->src->prefix, route->src->plen, NULL); 228 assert(i >= 0 && i < route_slots); 229 230 if(route == routes[i]) { 231 routes[i] = route->next; 232 route->next = NULL; 233 free(route); 234 235 if(routes[i] == NULL) { 236 if(i < route_slots - 1) 237 memmove(routes + i, routes + i + 1, 238 (route_slots - i - 1) * sizeof(struct babel_route*)); 239 routes[route_slots - 1] = NULL; 240 route_slots--; 241 } 242 243 if(route_slots == 0) 244 resize_route_table(0); 245 else if(max_route_slots > 8 && route_slots < max_route_slots / 4) 246 resize_route_table(max_route_slots / 2); 247 } else { 248 struct babel_route *r = routes[i]; 249 while(r->next != route) 250 r = r->next; 251 r->next = route->next; 252 route->next = NULL; 253 free(route); 254 } 255 256 if(lost) 257 route_lost(src, oldmetric); 258 259 release_source(src); 260} 261 262void 263flush_all_routes() 264{ 265 int i; 266 267 /* Start from the end, to avoid shifting the table. */ 268 i = route_slots - 1; 269 while(i >= 0) { 270 while(i < route_slots) { 271 /* Uninstall first, to avoid calling route_lost. */ 272 if(routes[i]->installed) 273 uninstall_route(routes[0]); 274 flush_route(routes[i]); 275 } 276 i--; 277 } 278 279 check_sources_released(); 280} 281 282void 283flush_neighbour_routes(struct neighbour *neigh) 284{ 285 int i; 286 287 i = 0; 288 while(i < route_slots) { 289 struct babel_route *r; 290 r = routes[i]; 291 while(r) { 292 if(r->neigh == neigh) { 293 flush_route(r); 294 goto again; 295 } 296 r = r->next; 297 } 298 i++; 299 again: 300 ; 301 } 302} 303 304void 305flush_interface_routes(struct interface *ifp, int v4only) 306{ 307 int i; 308 309 i = 0; 310 while(i < route_slots) { 311 struct babel_route *r; 312 r = routes[i]; 313 while(r) { 314 if(r->neigh->ifp == ifp && 315 (!v4only || v4mapped(r->nexthop))) { 316 flush_route(r); 317 goto again; 318 } 319 r = r->next; 320 } 321 i++; 322 again: 323 ; 324 } 325} 326 327/* Iterate a function over all routes. */ 328void 329for_all_routes(void (*f)(struct babel_route*, void*), void *closure) 330{ 331 int i; 332 333 for(i = 0; i < route_slots; i++) { 334 struct babel_route *r = routes[i]; 335 while(r) { 336 (*f)(r, closure); 337 r = r->next; 338 } 339 } 340} 341 342void 343for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure) 344{ 345 int i; 346 347 for(i = 0; i < route_slots; i++) { 348 if(routes[i]->installed) 349 (*f)(routes[i], closure); 350 } 351} 352 353static int 354metric_to_kernel(int metric) 355{ 356 return metric < INFINITY ? kernel_metric : KERNEL_INFINITY; 357} 358 359/* This is used to maintain the invariant that the installed route is at 360 the head of the list. */ 361static void 362move_installed_route(struct babel_route *route, int i) 363{ 364 assert(i >= 0 && i < route_slots); 365 assert(route->installed); 366 367 if(route != routes[i]) { 368 struct babel_route *r = routes[i]; 369 while(r->next != route) 370 r = r->next; 371 r->next = route->next; 372 route->next = routes[i]; 373 routes[i] = route; 374 } 375} 376 377void 378install_route(struct babel_route *route) 379{ 380 int i, rc; 381 382 if(route->installed) 383 return; 384 385 if(!route_feasible(route)) 386 zlog_err("WARNING: installing unfeasible route " 387 "(this shouldn't happen)."); 388 389 i = find_route_slot(route->src->prefix, route->src->plen, NULL); 390 assert(i >= 0 && i < route_slots); 391 392 if(routes[i] != route && routes[i]->installed) { 393 fprintf(stderr, "WARNING: attempting to install duplicate route " 394 "(this shouldn't happen)."); 395 return; 396 } 397 398 rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen, 399 route->nexthop, 400 route->neigh->ifp->ifindex, 401 metric_to_kernel(route_metric(route)), NULL, 0, 0); 402 if(rc < 0) { 403 int save = errno; 404 zlog_err("kernel_route(ADD): %s", safe_strerror(errno)); 405 if(save != EEXIST) 406 return; 407 } 408 route->installed = 1; 409 move_installed_route(route, i); 410 411} 412 413void 414uninstall_route(struct babel_route *route) 415{ 416 int rc; 417 418 if(!route->installed) 419 return; 420 421 rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen, 422 route->nexthop, 423 route->neigh->ifp->ifindex, 424 metric_to_kernel(route_metric(route)), NULL, 0, 0); 425 if(rc < 0) 426 zlog_err("kernel_route(FLUSH): %s", safe_strerror(errno)); 427 428 route->installed = 0; 429} 430 431/* This is equivalent to uninstall_route followed with install_route, 432 but without the race condition. The destination of both routes 433 must be the same. */ 434 435static void 436switch_routes(struct babel_route *old, struct babel_route *new) 437{ 438 int rc; 439 440 if(!old) { 441 install_route(new); 442 return; 443 } 444 445 if(!old->installed) 446 return; 447 448 if(!route_feasible(new)) 449 zlog_err("WARNING: switching to unfeasible route " 450 "(this shouldn't happen)."); 451 452 rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen, 453 old->nexthop, old->neigh->ifp->ifindex, 454 metric_to_kernel(route_metric(old)), 455 new->nexthop, new->neigh->ifp->ifindex, 456 metric_to_kernel(route_metric(new))); 457 if(rc < 0) { 458 zlog_err("kernel_route(MODIFY): %s", safe_strerror(errno)); 459 return; 460 } 461 462 old->installed = 0; 463 new->installed = 1; 464 move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen, 465 NULL)); 466} 467 468static void 469change_route_metric(struct babel_route *route, 470 unsigned refmetric, unsigned cost, unsigned add) 471{ 472 int old, new; 473 int newmetric = MIN(refmetric + cost + add, INFINITY); 474 475 old = metric_to_kernel(route_metric(route)); 476 new = metric_to_kernel(newmetric); 477 478 if(route->installed && old != new) { 479 int rc; 480 rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen, 481 route->nexthop, route->neigh->ifp->ifindex, 482 old, 483 route->nexthop, route->neigh->ifp->ifindex, 484 new); 485 if(rc < 0) { 486 zlog_err("kernel_route(MODIFY metric): %s", safe_strerror(errno)); 487 return; 488 } 489 } 490 491 route->refmetric = refmetric; 492 route->cost = cost; 493 route->add_metric = add; 494} 495 496static void 497retract_route(struct babel_route *route) 498{ 499 change_route_metric(route, INFINITY, INFINITY, 0); 500} 501 502int 503route_feasible(struct babel_route *route) 504{ 505 return update_feasible(route->src, route->seqno, route->refmetric); 506} 507 508int 509route_old(struct babel_route *route) 510{ 511 return route->time < babel_now.tv_sec - route->hold_time * 7 / 8; 512} 513 514int 515route_expired(struct babel_route *route) 516{ 517 return route->time < babel_now.tv_sec - route->hold_time; 518} 519 520static int 521channels_interfere(int ch1, int ch2) 522{ 523 if(ch1 == BABEL_IF_CHANNEL_NONINTERFERING 524 || ch2 == BABEL_IF_CHANNEL_NONINTERFERING) 525 return 0; 526 if(ch1 == BABEL_IF_CHANNEL_INTERFERING 527 || ch2 == BABEL_IF_CHANNEL_INTERFERING) 528 return 1; 529 return ch1 == ch2; 530} 531 532int 533route_interferes(struct babel_route *route, struct interface *ifp) 534{ 535 struct babel_interface *babel_ifp = NULL; 536 switch(diversity_kind) { 537 case DIVERSITY_NONE: 538 return 1; 539 case DIVERSITY_INTERFACE_1: 540 return route->neigh->ifp == ifp; 541 case DIVERSITY_CHANNEL_1: 542 case DIVERSITY_CHANNEL: 543 if(route->neigh->ifp == ifp) 544 return 1; 545 babel_ifp = babel_get_if_nfo(ifp); 546 if(channels_interfere(babel_ifp->channel, 547 babel_get_if_nfo(route->neigh->ifp)->channel)) 548 return 1; 549 if(diversity_kind == DIVERSITY_CHANNEL) { 550 int i; 551 for(i = 0; i < DIVERSITY_HOPS; i++) { 552 if(route->channels[i] == 0) 553 break; 554 if(channels_interfere(babel_ifp->channel, route->channels[i])) 555 return 1; 556 } 557 } 558 return 0; 559 default: 560 fprintf(stderr, "Unknown kind of diversity.\n"); 561 return 1; 562 } 563} 564 565int 566update_feasible(struct source *src, 567 unsigned short seqno, unsigned short refmetric) 568{ 569 if(src == NULL) 570 return 1; 571 572 if(src->time < babel_now.tv_sec - SOURCE_GC_TIME) 573 /* Never mind what is probably stale data */ 574 return 1; 575 576 if(refmetric >= INFINITY) 577 /* Retractions are always feasible */ 578 return 1; 579 580 return (seqno_compare(seqno, src->seqno) > 0 || 581 (src->seqno == seqno && refmetric < src->metric)); 582} 583 584/* This returns the feasible route with the smallest metric. */ 585struct babel_route * 586find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, 587 struct neighbour *exclude) 588{ 589 struct babel_route *route = NULL, *r = NULL; 590 int i = find_route_slot(prefix, plen, NULL); 591 592 if(i < 0) 593 return NULL; 594 595 route = routes[i]; 596 597 r = route->next; 598 while(r) { 599 if(!route_expired(r) && 600 (!feasible || route_feasible(r)) && 601 (!exclude || r->neigh != exclude) && 602 (route_metric(r) < route_metric(route))) 603 route = r; 604 r = r->next; 605 } 606 return route; 607} 608 609void 610update_route_metric(struct babel_route *route) 611{ 612 int oldmetric = route_metric(route); 613 614 if(route_expired(route)) { 615 if(route->refmetric < INFINITY) { 616 route->seqno = seqno_plus(route->src->seqno, 1); 617 retract_route(route); 618 if(oldmetric < INFINITY) 619 route_changed(route, route->src, oldmetric); 620 } 621 } else { 622 struct neighbour *neigh = route->neigh; 623 int add_metric = input_filter(route->src->id, 624 route->src->prefix, route->src->plen, 625 neigh->address, 626 neigh->ifp->ifindex); 627 change_route_metric(route, route->refmetric, 628 neighbour_cost(route->neigh), add_metric); 629 if(route_metric(route) != oldmetric) 630 route_changed(route, route->src, oldmetric); 631 } 632} 633 634/* Called whenever a neighbour's cost changes, to update the metric of 635 all routes through that neighbour. Calls local_notify_neighbour. */ 636void 637update_neighbour_metric(struct neighbour *neigh, int changed) 638{ 639 640 if(changed) { 641 int i; 642 643 for(i = 0; i < route_slots; i++) { 644 struct babel_route *r = routes[i]; 645 while(r) { 646 if(r->neigh == neigh) 647 update_route_metric(r); 648 r = r->next; 649 } 650 } 651 } 652} 653 654void 655update_interface_metric(struct interface *ifp) 656{ 657 int i; 658 659 for(i = 0; i < route_slots; i++) { 660 struct babel_route *r = routes[i]; 661 while(r) { 662 if(r->neigh->ifp == ifp) 663 update_route_metric(r); 664 r = r->next; 665 } 666 } 667} 668 669/* This is called whenever we receive an update. */ 670struct babel_route * 671update_route(const unsigned char *router_id, 672 const unsigned char *prefix, unsigned char plen, 673 unsigned short seqno, unsigned short refmetric, 674 unsigned short interval, 675 struct neighbour *neigh, const unsigned char *nexthop, 676 const unsigned char *channels, int channels_len) 677{ 678 struct babel_route *route; 679 struct source *src; 680 int metric, feasible; 681 int add_metric; 682 int hold_time = MAX((4 * interval) / 100 + interval / 50, 15); 683 684 if(memcmp(router_id, myid, 8) == 0) 685 return NULL; 686 687 if(martian_prefix(prefix, plen)) { 688 zlog_err("Rejecting martian route to %s through %s.", 689 format_prefix(prefix, plen), format_address(router_id)); 690 return NULL; 691 } 692 693 add_metric = input_filter(router_id, prefix, plen, 694 neigh->address, neigh->ifp->ifindex); 695 if(add_metric >= INFINITY) 696 return NULL; 697 698 route = find_route(prefix, plen, neigh, nexthop); 699 700 if(route && memcmp(route->src->id, router_id, 8) == 0) 701 /* Avoid scanning the source table. */ 702 src = route->src; 703 else 704 src = find_source(router_id, prefix, plen, 1, seqno); 705 706 if(src == NULL) 707 return NULL; 708 709 feasible = update_feasible(src, seqno, refmetric); 710 metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY); 711 712 if(route) { 713 struct source *oldsrc; 714 unsigned short oldmetric; 715 int lost = 0; 716 717 oldsrc = route->src; 718 oldmetric = route_metric(route); 719 720 /* If a successor switches sources, we must accept his update even 721 if it makes a route unfeasible in order to break any routing loops 722 in a timely manner. If the source remains the same, we ignore 723 the update. */ 724 if(!feasible && route->installed) { 725 debugf(BABEL_DEBUG_COMMON,"Unfeasible update for installed route to %s " 726 "(%s %d %d -> %s %d %d).", 727 format_prefix(src->prefix, src->plen), 728 format_address(route->src->id), 729 route->seqno, route->refmetric, 730 format_address(src->id), seqno, refmetric); 731 if(src != route->src) { 732 uninstall_route(route); 733 lost = 1; 734 } 735 } 736 737 route->src = retain_source(src); 738 if((feasible || keep_unfeasible) && refmetric < INFINITY) 739 route->time = babel_now.tv_sec; 740 route->seqno = seqno; 741 change_route_metric(route, 742 refmetric, neighbour_cost(neigh), add_metric); 743 route->hold_time = hold_time; 744 745 route_changed(route, oldsrc, oldmetric); 746 if(lost) 747 route_lost(oldsrc, oldmetric); 748 749 if(!feasible) 750 send_unfeasible_request(neigh, route->installed && route_old(route), 751 seqno, metric, src); 752 release_source(oldsrc); 753 } else { 754 struct babel_route *new_route; 755 756 if(refmetric >= INFINITY) 757 /* Somebody's retracting a route we never saw. */ 758 return NULL; 759 if(!feasible) { 760 send_unfeasible_request(neigh, 0, seqno, metric, src); 761 if(!keep_unfeasible) 762 return NULL; 763 } 764 765 route = malloc(sizeof(struct babel_route)); 766 if(route == NULL) { 767 perror("malloc(route)"); 768 return NULL; 769 } 770 771 route->src = retain_source(src); 772 route->refmetric = refmetric; 773 route->cost = neighbour_cost(neigh); 774 route->add_metric = add_metric; 775 route->seqno = seqno; 776 route->neigh = neigh; 777 memcpy(route->nexthop, nexthop, 16); 778 route->time = babel_now.tv_sec; 779 route->hold_time = hold_time; 780 route->installed = 0; 781 memset(&route->channels, 0, sizeof(route->channels)); 782 if(channels_len > 0) 783 memcpy(&route->channels, channels, 784 MIN(channels_len, DIVERSITY_HOPS)); 785 route->next = NULL; 786 new_route = insert_route(route); 787 if(new_route == NULL) { 788 fprintf(stderr, "Couldn't insert route.\n"); 789 free(route); 790 return NULL; 791 } 792 consider_route(route); 793 } 794 return route; 795} 796 797/* We just received an unfeasible update. If it's any good, send 798 a request for a new seqno. */ 799void 800send_unfeasible_request(struct neighbour *neigh, int force, 801 unsigned short seqno, unsigned short metric, 802 struct source *src) 803{ 804 struct babel_route *route = find_installed_route(src->prefix, src->plen); 805 806 if(seqno_minus(src->seqno, seqno) > 100) { 807 /* Probably a source that lost its seqno. Let it time-out. */ 808 return; 809 } 810 811 if(force || !route || route_metric(route) >= metric + 512) { 812 send_unicast_multihop_request(neigh, src->prefix, src->plen, 813 src->metric >= INFINITY ? 814 src->seqno : 815 seqno_plus(src->seqno, 1), 816 src->id, 127); 817 } 818} 819 820/* This takes a feasible route and decides whether to install it. */ 821static void 822consider_route(struct babel_route *route) 823{ 824 struct babel_route *installed; 825 struct xroute *xroute; 826 827 if(route->installed) 828 return; 829 830 if(!route_feasible(route)) 831 return; 832 833 xroute = find_xroute(route->src->prefix, route->src->plen); 834 if(xroute && (allow_duplicates < 0 || xroute->metric >= allow_duplicates)) 835 return; 836 837 installed = find_installed_route(route->src->prefix, route->src->plen); 838 839 if(installed == NULL) 840 goto install; 841 842 if(route_metric(route) >= INFINITY) 843 return; 844 845 if(route_metric(installed) >= INFINITY) 846 goto install; 847 848 if(route_metric(installed) >= route_metric(route) + 64) 849 goto install; 850 851 return; 852 853 install: 854 switch_routes(installed, route); 855 if(installed && route->installed) 856 send_triggered_update(route, installed->src, route_metric(installed)); 857 else 858 send_update(NULL, 1, route->src->prefix, route->src->plen); 859 return; 860} 861 862void 863retract_neighbour_routes(struct neighbour *neigh) 864{ 865 int i; 866 867 for(i = 0; i < route_slots; i++) { 868 struct babel_route *r = routes[i]; 869 while(r) { 870 if(r->neigh == neigh) { 871 if(r->refmetric != INFINITY) { 872 unsigned short oldmetric = route_metric(r); 873 retract_route(r); 874 if(oldmetric != INFINITY) 875 route_changed(r, r->src, oldmetric); 876 } 877 } 878 r = r->next; 879 } 880 i++; 881 } 882} 883 884void 885send_triggered_update(struct babel_route *route, struct source *oldsrc, 886 unsigned oldmetric) 887{ 888 unsigned newmetric, diff; 889 /* 1 means send speedily, 2 means resend */ 890 int urgent; 891 892 if(!route->installed) 893 return; 894 895 newmetric = route_metric(route); 896 diff = 897 newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric; 898 899 if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY)) 900 /* Switching sources can cause transient routing loops. 901 Retractions can cause blackholes. */ 902 urgent = 2; 903 else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512) 904 /* Route getting significantly worse */ 905 urgent = 1; 906 else if(unsatisfied_request(route->src->prefix, route->src->plen, 907 route->seqno, route->src->id)) 908 /* Make sure that requests are satisfied speedily */ 909 urgent = 1; 910 else if(oldmetric >= INFINITY && newmetric < INFINITY) 911 /* New route */ 912 urgent = 0; 913 else if(newmetric < oldmetric && diff < 1024) 914 /* Route getting better. This may be a transient fluctuation, so 915 don't advertise it to avoid making routes unfeasible later on. */ 916 return; 917 else if(diff < 384) 918 /* Don't fret about trivialities */ 919 return; 920 else 921 urgent = 0; 922 923 if(urgent >= 2) 924 send_update_resend(NULL, route->src->prefix, route->src->plen); 925 else 926 send_update(NULL, urgent, route->src->prefix, route->src->plen); 927 928 if(oldmetric < INFINITY) { 929 if(newmetric >= oldmetric + 512) { 930 send_request_resend(NULL, route->src->prefix, route->src->plen, 931 route->src->metric >= INFINITY ? 932 route->src->seqno : 933 seqno_plus(route->src->seqno, 1), 934 route->src->id); 935 } else if(newmetric >= oldmetric + 288) { 936 send_request(NULL, route->src->prefix, route->src->plen); 937 } 938 } 939} 940 941/* A route has just changed. Decide whether to switch to a different route or 942 send an update. */ 943void 944route_changed(struct babel_route *route, 945 struct source *oldsrc, unsigned short oldmetric) 946{ 947 if(route->installed) { 948 if(route_metric(route) > oldmetric) { 949 struct babel_route *better_route; 950 better_route = 951 find_best_route(route->src->prefix, route->src->plen, 1, NULL); 952 if(better_route && 953 route_metric(better_route) <= route_metric(route) - 96) 954 consider_route(better_route); 955 } 956 957 if(route->installed) 958 /* We didn't change routes after all. */ 959 send_triggered_update(route, oldsrc, oldmetric); 960 } else { 961 /* Reconsider routes even when their metric didn't decrease, 962 they may not have been feasible before. */ 963 consider_route(route); 964 } 965} 966 967/* We just lost the installed route to a given destination. */ 968void 969route_lost(struct source *src, unsigned oldmetric) 970{ 971 struct babel_route *new_route; 972 new_route = find_best_route(src->prefix, src->plen, 1, NULL); 973 if(new_route) { 974 consider_route(new_route); 975 } else if(oldmetric < INFINITY) { 976 /* Complain loudly. */ 977 send_update_resend(NULL, src->prefix, src->plen); 978 send_request_resend(NULL, src->prefix, src->plen, 979 src->metric >= INFINITY ? 980 src->seqno : seqno_plus(src->seqno, 1), 981 src->id); 982 } 983} 984 985/* This is called periodically to flush old routes. It will also send 986 requests for routes that are about to expire. */ 987void 988expire_routes(void) 989{ 990 struct babel_route *r; 991 int i; 992 993 debugf(BABEL_DEBUG_COMMON,"Expiring old routes."); 994 995 i = 0; 996 while(i < route_slots) { 997 r = routes[i]; 998 while(r) { 999 /* Protect against clock being stepped. */ 1000 if(r->time > babel_now.tv_sec || route_old(r)) { 1001 flush_route(r); 1002 goto again; 1003 } 1004 1005 update_route_metric(r); 1006 1007 if(r->installed && r->refmetric < INFINITY) { 1008 if(route_old(r)) 1009 /* Route about to expire, send a request. */ 1010 send_unicast_request(r->neigh, 1011 r->src->prefix, r->src->plen); 1012 } 1013 r = r->next; 1014 } 1015 i++; 1016 again: 1017 ; 1018 } 1019} 1020