Annotation of embedaddon/quagga/babeld/route.c, revision 1.1
1.1 ! misho 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: *
! 18: Copyright (c) 2007, 2008 by Juliusz Chroboczek
! 19: Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
! 20:
! 21: Permission is hereby granted, free of charge, to any person obtaining a copy
! 22: of this software and associated documentation files (the "Software"), to deal
! 23: in the Software without restriction, including without limitation the rights
! 24: to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
! 25: copies of the Software, and to permit persons to whom the Software is
! 26: furnished to do so, subject to the following conditions:
! 27:
! 28: The above copyright notice and this permission notice shall be included in
! 29: all copies or substantial portions of the Software.
! 30:
! 31: THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
! 32: IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
! 33: FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
! 34: AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
! 35: LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
! 36: OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
! 37: THE 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:
! 54: static void consider_route(struct babel_route *route);
! 55:
! 56: struct babel_route **routes = NULL;
! 57: static int route_slots = 0, max_route_slots = 0;
! 58: int kernel_metric = 0;
! 59: int allow_duplicates = -1;
! 60: int diversity_kind = DIVERSITY_NONE;
! 61: int diversity_factor = 256; /* in units of 1/256 */
! 62: int 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:
! 68: static int
! 69: route_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:
! 87: static int
! 88: find_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:
! 118: struct babel_route *
! 119: find_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:
! 139: struct babel_route *
! 140: find_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. */
! 151: int
! 152: installed_routes_estimate(void)
! 153: {
! 154: return route_slots;
! 155: }
! 156:
! 157: static int
! 158: resize_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. */
! 179: static struct babel_route *
! 180: insert_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:
! 211: void
! 212: flush_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:
! 262: void
! 263: flush_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:
! 282: void
! 283: flush_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:
! 304: void
! 305: flush_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. */
! 328: void
! 329: for_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:
! 342: void
! 343: for_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:
! 353: static int
! 354: metric_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. */
! 361: static void
! 362: move_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:
! 377: void
! 378: install_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:
! 413: void
! 414: uninstall_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:
! 435: static void
! 436: switch_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:
! 468: static void
! 469: change_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:
! 496: static void
! 497: retract_route(struct babel_route *route)
! 498: {
! 499: change_route_metric(route, INFINITY, INFINITY, 0);
! 500: }
! 501:
! 502: int
! 503: route_feasible(struct babel_route *route)
! 504: {
! 505: return update_feasible(route->src, route->seqno, route->refmetric);
! 506: }
! 507:
! 508: int
! 509: route_old(struct babel_route *route)
! 510: {
! 511: return route->time < babel_now.tv_sec - route->hold_time * 7 / 8;
! 512: }
! 513:
! 514: int
! 515: route_expired(struct babel_route *route)
! 516: {
! 517: return route->time < babel_now.tv_sec - route->hold_time;
! 518: }
! 519:
! 520: static int
! 521: channels_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:
! 532: int
! 533: route_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:
! 565: int
! 566: update_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. */
! 585: struct babel_route *
! 586: find_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:
! 609: void
! 610: update_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. */
! 636: void
! 637: update_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:
! 654: void
! 655: update_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. */
! 670: struct babel_route *
! 671: update_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. */
! 799: void
! 800: send_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. */
! 821: static void
! 822: consider_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:
! 862: void
! 863: retract_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:
! 884: void
! 885: send_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. */
! 943: void
! 944: route_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. */
! 968: void
! 969: route_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. */
! 987: void
! 988: expire_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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to route.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / babeld