Annotation of embedaddon/bird/proto/babel/babel.c, revision 1.1
1.1 ! misho 1: /*
! 2: * BIRD -- The Babel protocol
! 3: *
! 4: * Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
! 5: *
! 6: * Can be freely distributed and used under the terms of the GNU GPL.
! 7: *
! 8: * This file contains the main routines for handling and sending TLVs, as
! 9: * well as timers and interaction with the nest.
! 10: */
! 11:
! 12: /**
! 13: * DOC: The Babel protocol
! 14: *
! 15: * Babel (RFC6126) is a loop-avoiding distance-vector routing protocol that is
! 16: * robust and efficient both in ordinary wired networks and in wireless mesh
! 17: * networks.
! 18: *
! 19: * The Babel protocol keeps state for each neighbour in a &babel_neighbor
! 20: * struct, tracking received Hello and I Heard You (IHU) messages. A
! 21: * &babel_interface struct keeps hello and update times for each interface, and
! 22: * a separate hello seqno is maintained for each interface.
! 23: *
! 24: * For each prefix, Babel keeps track of both the possible routes (with next hop
! 25: * and router IDs), as well as the feasibility distance for each prefix and
! 26: * router id. The prefix itself is tracked in a &babel_entry struct, while the
! 27: * possible routes for the prefix are tracked as &babel_route entries and the
! 28: * feasibility distance is maintained through &babel_source structures.
! 29: *
! 30: * The main route selection is done in babel_select_route(). This is called when
! 31: * an entry is updated by receiving updates from the network or when modified by
! 32: * internal timers. It performs feasibility checks on the available routes for
! 33: * the prefix and selects the one with the lowest metric to be announced to the
! 34: * core.
! 35: */
! 36:
! 37: #include <stdlib.h>
! 38: #include "babel.h"
! 39:
! 40:
! 41: #define OUR_ROUTE(r) (r->neigh == NULL)
! 42:
! 43: /*
! 44: * Is one number greater or equal than another mod 2^16? This is based on the
! 45: * definition of serial number space in RFC 1982. Note that arguments are of
! 46: * uint type to avoid integer promotion to signed integer.
! 47: */
! 48: static inline int ge_mod64k(uint a, uint b)
! 49: { return (u16)(a - b) < 0x8000; }
! 50:
! 51: static void babel_dump_entry(struct babel_entry *e);
! 52: static void babel_dump_route(struct babel_route *r);
! 53: static void babel_select_route(struct babel_entry *e);
! 54: static void babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n);
! 55: static void babel_send_wildcard_request(struct babel_iface *ifa);
! 56: static int babel_cache_seqno_request(struct babel_proto *p, ip_addr prefix, u8 plen,
! 57: u64 router_id, u16 seqno);
! 58: static void babel_trigger_iface_update(struct babel_iface *ifa);
! 59: static void babel_trigger_update(struct babel_proto *p);
! 60: static void babel_send_seqno_request(struct babel_entry *e);
! 61: static inline void babel_kick_timer(struct babel_proto *p);
! 62: static inline void babel_iface_kick_timer(struct babel_iface *ifa);
! 63:
! 64:
! 65: /*
! 66: * Functions to maintain data structures
! 67: */
! 68:
! 69: static void
! 70: babel_init_entry(struct fib_node *n)
! 71: {
! 72: struct babel_entry *e = (void *) n;
! 73: e->proto = NULL;
! 74: e->selected_in = NULL;
! 75: e->selected_out = NULL;
! 76: e->updated = now;
! 77: init_list(&e->sources);
! 78: init_list(&e->routes);
! 79: }
! 80:
! 81: static inline struct babel_entry *
! 82: babel_find_entry(struct babel_proto *p, ip_addr prefix, u8 plen)
! 83: {
! 84: return fib_find(&p->rtable, &prefix, plen);
! 85: }
! 86:
! 87: static struct babel_entry *
! 88: babel_get_entry(struct babel_proto *p, ip_addr prefix, u8 plen)
! 89: {
! 90: struct babel_entry *e = fib_get(&p->rtable, &prefix, plen);
! 91: e->proto = p;
! 92: return e;
! 93: }
! 94:
! 95: static struct babel_source *
! 96: babel_find_source(struct babel_entry *e, u64 router_id)
! 97: {
! 98: struct babel_source *s;
! 99:
! 100: WALK_LIST(s, e->sources)
! 101: if (s->router_id == router_id)
! 102: return s;
! 103:
! 104: return NULL;
! 105: }
! 106:
! 107: static struct babel_source *
! 108: babel_get_source(struct babel_entry *e, u64 router_id)
! 109: {
! 110: struct babel_proto *p = e->proto;
! 111: struct babel_source *s = babel_find_source(e, router_id);
! 112:
! 113: if (s)
! 114: return s;
! 115:
! 116: s = sl_alloc(p->source_slab);
! 117: s->router_id = router_id;
! 118: s->expires = now + BABEL_GARBAGE_INTERVAL;
! 119: s->seqno = 0;
! 120: s->metric = BABEL_INFINITY;
! 121: add_tail(&e->sources, NODE s);
! 122:
! 123: return s;
! 124: }
! 125:
! 126: static void
! 127: babel_expire_sources(struct babel_entry *e)
! 128: {
! 129: struct babel_proto *p = e->proto;
! 130: struct babel_source *n, *nx;
! 131:
! 132: WALK_LIST_DELSAFE(n, nx, e->sources)
! 133: {
! 134: if (n->expires && n->expires <= now)
! 135: {
! 136: rem_node(NODE n);
! 137: sl_free(p->source_slab, n);
! 138: }
! 139: }
! 140: }
! 141:
! 142: static struct babel_route *
! 143: babel_find_route(struct babel_entry *e, struct babel_neighbor *n)
! 144: {
! 145: struct babel_route *r;
! 146:
! 147: WALK_LIST(r, e->routes)
! 148: if (r->neigh == n)
! 149: return r;
! 150:
! 151: return NULL;
! 152: }
! 153:
! 154: static struct babel_route *
! 155: babel_get_route(struct babel_entry *e, struct babel_neighbor *nbr)
! 156: {
! 157: struct babel_proto *p = e->proto;
! 158: struct babel_route *r = babel_find_route(e, nbr);
! 159:
! 160: if (r)
! 161: return r;
! 162:
! 163: r = sl_alloc(p->route_slab);
! 164: memset(r, 0, sizeof(*r));
! 165: r->e = e;
! 166: add_tail(&e->routes, NODE r);
! 167:
! 168: if (nbr)
! 169: {
! 170: r->neigh = nbr;
! 171: r->expires = now + BABEL_GARBAGE_INTERVAL;
! 172: add_tail(&nbr->routes, NODE &r->neigh_route);
! 173: }
! 174:
! 175: return r;
! 176: }
! 177:
! 178: static void
! 179: babel_flush_route(struct babel_route *r)
! 180: {
! 181: struct babel_proto *p = r->e->proto;
! 182:
! 183: DBG("Babel: Flush route %I/%d router_id %lR neigh %I\n",
! 184: r->e->n.prefix, r->e->n.pxlen, r->router_id, r->neigh ? r->neigh->addr : IPA_NONE);
! 185:
! 186: rem_node(NODE r);
! 187:
! 188: if (r->neigh)
! 189: rem_node(&r->neigh_route);
! 190:
! 191: if (r->e->selected_in == r)
! 192: r->e->selected_in = NULL;
! 193:
! 194: if (r->e->selected_out == r)
! 195: r->e->selected_out = NULL;
! 196:
! 197: sl_free(p->route_slab, r);
! 198: }
! 199:
! 200: static void
! 201: babel_expire_route(struct babel_route *r)
! 202: {
! 203: struct babel_proto *p = r->e->proto;
! 204: struct babel_entry *e = r->e;
! 205:
! 206: TRACE(D_EVENTS, "Route expiry timer for %I/%d router-id %lR fired",
! 207: e->n.prefix, e->n.pxlen, r->router_id);
! 208:
! 209: if (r->metric < BABEL_INFINITY)
! 210: {
! 211: r->metric = BABEL_INFINITY;
! 212: r->expires = now + r->expiry_interval;
! 213: }
! 214: else
! 215: {
! 216: babel_flush_route(r);
! 217: }
! 218: }
! 219:
! 220: static void
! 221: babel_refresh_route(struct babel_route *r)
! 222: {
! 223: if (!OUR_ROUTE(r) && (r == r->e->selected_in))
! 224: babel_send_route_request(r->e, r->neigh);
! 225:
! 226: r->refresh_time = 0;
! 227: }
! 228:
! 229: static void
! 230: babel_expire_routes(struct babel_proto *p)
! 231: {
! 232: struct babel_entry *e;
! 233: struct babel_route *r, *rx;
! 234: struct fib_iterator fit;
! 235:
! 236: FIB_ITERATE_INIT(&fit, &p->rtable);
! 237:
! 238: loop:
! 239: FIB_ITERATE_START(&p->rtable, &fit, n)
! 240: {
! 241: e = (struct babel_entry *) n;
! 242: int changed = 0;
! 243:
! 244: WALK_LIST_DELSAFE(r, rx, e->routes)
! 245: {
! 246: if (r->refresh_time && r->refresh_time <= now)
! 247: babel_refresh_route(r);
! 248:
! 249: if (r->expires && r->expires <= now)
! 250: {
! 251: babel_expire_route(r);
! 252: changed = 1;
! 253: }
! 254: }
! 255:
! 256: if (changed)
! 257: {
! 258: /*
! 259: * We have to restart the iteration because there may be a cascade of
! 260: * synchronous events babel_select_route() -> nest table change ->
! 261: * babel_rt_notify() -> p->rtable change, invalidating hidden variables.
! 262: */
! 263:
! 264: FIB_ITERATE_PUT(&fit, n);
! 265: babel_select_route(e);
! 266: goto loop;
! 267: }
! 268:
! 269: babel_expire_sources(e);
! 270:
! 271: /* Remove empty entries */
! 272: if (EMPTY_LIST(e->sources) && EMPTY_LIST(e->routes))
! 273: {
! 274: FIB_ITERATE_PUT(&fit, n);
! 275: fib_delete(&p->rtable, e);
! 276: goto loop;
! 277: }
! 278: }
! 279: FIB_ITERATE_END(n);
! 280: }
! 281:
! 282: static struct babel_neighbor *
! 283: babel_find_neighbor(struct babel_iface *ifa, ip_addr addr)
! 284: {
! 285: struct babel_neighbor *nbr;
! 286:
! 287: WALK_LIST(nbr, ifa->neigh_list)
! 288: if (ipa_equal(nbr->addr, addr))
! 289: return nbr;
! 290:
! 291: return NULL;
! 292: }
! 293:
! 294: static struct babel_neighbor *
! 295: babel_get_neighbor(struct babel_iface *ifa, ip_addr addr)
! 296: {
! 297: struct babel_neighbor *nbr = babel_find_neighbor(ifa, addr);
! 298:
! 299: if (nbr)
! 300: return nbr;
! 301:
! 302: nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor));
! 303: nbr->ifa = ifa;
! 304: nbr->addr = addr;
! 305: nbr->txcost = BABEL_INFINITY;
! 306: init_list(&nbr->routes);
! 307: add_tail(&ifa->neigh_list, NODE nbr);
! 308:
! 309: return nbr;
! 310: }
! 311:
! 312: static void
! 313: babel_flush_neighbor(struct babel_neighbor *nbr)
! 314: {
! 315: struct babel_proto *p = nbr->ifa->proto;
! 316: node *n;
! 317:
! 318: TRACE(D_EVENTS, "Flushing neighbor %I", nbr->addr);
! 319:
! 320: WALK_LIST_FIRST(n, nbr->routes)
! 321: {
! 322: struct babel_route *r = SKIP_BACK(struct babel_route, neigh_route, n);
! 323: struct babel_entry *e = r->e;
! 324: int selected = (r == e->selected_in);
! 325:
! 326: babel_flush_route(r);
! 327:
! 328: if (selected)
! 329: babel_select_route(e);
! 330: }
! 331:
! 332: rem_node(NODE nbr);
! 333: mb_free(nbr);
! 334: }
! 335:
! 336: static void
! 337: babel_expire_ihu(struct babel_neighbor *nbr)
! 338: {
! 339: nbr->txcost = BABEL_INFINITY;
! 340: }
! 341:
! 342: static void
! 343: babel_expire_hello(struct babel_neighbor *nbr)
! 344: {
! 345: nbr->hello_map <<= 1;
! 346:
! 347: if (nbr->hello_cnt < 16)
! 348: nbr->hello_cnt++;
! 349:
! 350: if (!nbr->hello_map)
! 351: babel_flush_neighbor(nbr);
! 352: }
! 353:
! 354: static void
! 355: babel_expire_neighbors(struct babel_proto *p)
! 356: {
! 357: struct babel_iface *ifa;
! 358: struct babel_neighbor *nbr, *nbx;
! 359:
! 360: WALK_LIST(ifa, p->interfaces)
! 361: {
! 362: WALK_LIST_DELSAFE(nbr, nbx, ifa->neigh_list)
! 363: {
! 364: if (nbr->ihu_expiry && nbr->ihu_expiry <= now)
! 365: babel_expire_ihu(nbr);
! 366:
! 367: if (nbr->hello_expiry && nbr->hello_expiry <= now)
! 368: babel_expire_hello(nbr);
! 369: }
! 370: }
! 371: }
! 372:
! 373:
! 374: /*
! 375: * Best route selection
! 376: */
! 377:
! 378: /*
! 379: * From the RFC (section 3.5.1):
! 380: *
! 381: * a route advertisement carrying the quintuple (prefix, plen, router-id, seqno,
! 382: * metric) is feasible if one of the following conditions holds:
! 383: *
! 384: * - metric is infinite; or
! 385: *
! 386: * - no entry exists in the source table indexed by (id, prefix, plen); or
! 387: *
! 388: * - an entry (prefix, plen, router-id, seqno', metric') exists in the source
! 389: * table, and either
! 390: * - seqno' < seqno or
! 391: * - seqno = seqno' and metric < metric'.
! 392: */
! 393: static inline int
! 394: babel_is_feasible(struct babel_source *s, u16 seqno, u16 metric)
! 395: {
! 396: return !s ||
! 397: (metric == BABEL_INFINITY) ||
! 398: (seqno > s->seqno) ||
! 399: ((seqno == s->seqno) && (metric < s->metric));
! 400: }
! 401:
! 402: static u16
! 403: babel_compute_rxcost(struct babel_neighbor *n)
! 404: {
! 405: struct babel_iface *ifa = n->ifa;
! 406: u8 cnt, missed;
! 407: u16 map=n->hello_map;
! 408:
! 409: if (!map) return BABEL_INFINITY;
! 410: cnt = u32_popcount(map); // number of bits set
! 411: missed = n->hello_cnt-cnt;
! 412:
! 413: if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
! 414: {
! 415: /* ETX - Appendix 2.2 in the RFC.
! 416:
! 417: beta = prob. of successful transmission.
! 418: rxcost = BABEL_RXCOST_WIRELESS/beta
! 419:
! 420: Since: beta = 1-missed/n->hello_cnt = cnt/n->hello_cnt
! 421: Then: rxcost = BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt
! 422: */
! 423: if (!cnt) return BABEL_INFINITY;
! 424: return BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt;
! 425: }
! 426: else
! 427: {
! 428: /* k-out-of-j selection - Appendix 2.1 in the RFC. */
! 429: DBG("Babel: Missed %d hellos from %I\n", missed, n->addr);
! 430: /* Link is bad if more than half the expected hellos were lost */
! 431: return (missed > n->hello_cnt/2) ? BABEL_INFINITY : ifa->cf->rxcost;
! 432: }
! 433: }
! 434:
! 435:
! 436: static u16
! 437: babel_compute_cost(struct babel_neighbor *n)
! 438: {
! 439: struct babel_iface *ifa = n->ifa;
! 440: u16 rxcost = babel_compute_rxcost(n);
! 441: if (rxcost == BABEL_INFINITY) return rxcost;
! 442: else if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
! 443: {
! 444: /* ETX - Appendix 2.2 in the RFC */
! 445: return (MAX(n->txcost, BABEL_RXCOST_WIRELESS) * rxcost)/BABEL_RXCOST_WIRELESS;
! 446: }
! 447: else
! 448: {
! 449: /* k-out-of-j selection - Appendix 2.1 in the RFC. */
! 450: return n->txcost;
! 451: }
! 452: }
! 453:
! 454: /* Simple additive metric - Appendix 3.1 in the RFC */
! 455: static u16
! 456: babel_compute_metric(struct babel_neighbor *n, uint metric)
! 457: {
! 458: metric += babel_compute_cost(n);
! 459: return MIN(metric, BABEL_INFINITY);
! 460: }
! 461:
! 462:
! 463: /**
! 464: * babel_announce_rte - announce selected route to the core
! 465: * @p: Babel protocol instance
! 466: * @e: Babel route entry to announce
! 467: *
! 468: * This function announces a Babel entry to the core if it has a selected
! 469: * incoming path, and retracts it otherwise. If the selected entry has infinite
! 470: * metric, the route is announced as unreachable.
! 471: */
! 472: static void
! 473: babel_announce_rte(struct babel_proto *p, struct babel_entry *e)
! 474: {
! 475: struct babel_route *r = e->selected_in;
! 476:
! 477: if (r)
! 478: {
! 479: net *n = net_get(p->p.table, e->n.prefix, e->n.pxlen);
! 480: rta A = {
! 481: .src = p->p.main_source,
! 482: .source = RTS_BABEL,
! 483: .scope = SCOPE_UNIVERSE,
! 484: .cast = RTC_UNICAST,
! 485: .dest = r->metric == BABEL_INFINITY ? RTD_UNREACHABLE : RTD_ROUTER,
! 486: .flags = 0,
! 487: .from = r->neigh->addr,
! 488: .iface = r->neigh->ifa->iface,
! 489: };
! 490:
! 491: if (r->metric < BABEL_INFINITY)
! 492: A.gw = r->next_hop;
! 493:
! 494: rta *a = rta_lookup(&A);
! 495: rte *rte = rte_get_temp(a);
! 496: rte->u.babel.metric = r->metric;
! 497: rte->u.babel.router_id = r->router_id;
! 498: rte->net = n;
! 499: rte->pflags = 0;
! 500:
! 501: rte_update(&p->p, n, rte);
! 502: }
! 503: else
! 504: {
! 505: /* Retraction */
! 506: net *n = net_find(p->p.table, e->n.prefix, e->n.pxlen);
! 507: rte_update(&p->p, n, NULL);
! 508: }
! 509: }
! 510:
! 511: /**
! 512: * babel_select_route - select best route for given route entry
! 513: * @e: Babel entry to select the best route for
! 514: *
! 515: * Select the best feasible route for a given prefix among the routes received
! 516: * from peers, and propagate it to the nest. This just selects the feasible
! 517: * route with the lowest metric.
! 518: *
! 519: * If no feasible route is available for a prefix that previously had a route
! 520: * selected, a seqno request is sent to try to get a valid route. In the
! 521: * meantime, the route is marked as infeasible in the nest (to blackhole packets
! 522: * going to it, as per the RFC).
! 523: *
! 524: * If no feasible route is available, and no previous route is selected, the
! 525: * route is removed from the nest entirely.
! 526: */
! 527: static void
! 528: babel_select_route(struct babel_entry *e)
! 529: {
! 530: struct babel_proto *p = e->proto;
! 531: struct babel_route *r, *cur = e->selected_in;
! 532:
! 533: /* try to find the best feasible route */
! 534: WALK_LIST(r, e->routes)
! 535: if (!OUR_ROUTE(r) && /* prevent propagating our own routes back to core */
! 536: (!cur || r->metric < cur->metric) &&
! 537: babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric))
! 538: cur = r;
! 539:
! 540: if (cur && !OUR_ROUTE(cur) &&
! 541: ((!e->selected_in && cur->metric < BABEL_INFINITY) ||
! 542: (e->selected_in && cur->metric < e->selected_in->metric)))
! 543: {
! 544: TRACE(D_EVENTS, "Picked new route for prefix %I/%d: router id %lR metric %d",
! 545: e->n.prefix, e->n.pxlen, cur->router_id, cur->metric);
! 546:
! 547: e->selected_in = cur;
! 548: e->updated = now;
! 549: babel_announce_rte(p, e);
! 550: }
! 551: else if (!cur || cur->metric == BABEL_INFINITY)
! 552: {
! 553: /* Couldn't find a feasible route. If we have a selected route, that means
! 554: it just became infeasible; so set it's metric to infinite and install it
! 555: (as unreachable), then send a seqno request.
! 556:
! 557: babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/
! 558: if (e->selected_in)
! 559: {
! 560: TRACE(D_EVENTS, "Lost feasible route for prefix %I/%d",
! 561: e->n.prefix, e->n.pxlen);
! 562:
! 563: e->selected_in->metric = BABEL_INFINITY;
! 564: e->updated = now;
! 565:
! 566: babel_send_seqno_request(e);
! 567: babel_announce_rte(p, e);
! 568:
! 569: /* Section 3.6 of the RFC forbids an infeasible from being selected. This
! 570: is cleared after announcing the route to the core to make sure an
! 571: unreachable route is propagated first. */
! 572: e->selected_in = NULL;
! 573: }
! 574: else
! 575: {
! 576: /* No route currently selected, and no new one selected; this means we
! 577: don't have a route to this destination anymore (and were probably
! 578: called from an expiry timer). Remove the route from the nest. */
! 579: TRACE(D_EVENTS, "Flushing route for prefix %I/%d", e->n.prefix, e->n.pxlen);
! 580:
! 581: e->selected_in = NULL;
! 582: e->updated = now;
! 583: babel_announce_rte(p, e);
! 584: }
! 585: }
! 586: }
! 587:
! 588: /*
! 589: * Functions to send replies
! 590: */
! 591:
! 592: static void
! 593: babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce)
! 594: {
! 595: struct babel_proto *p = ifa->proto;
! 596: union babel_msg msg = {};
! 597:
! 598: TRACE(D_PACKETS, "Sending ACK to %I with nonce %d", dest, nonce);
! 599:
! 600: msg.type = BABEL_TLV_ACK;
! 601: msg.ack.nonce = nonce;
! 602:
! 603: babel_send_unicast(&msg, ifa, dest);
! 604: }
! 605:
! 606: static void
! 607: babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neighbor *n)
! 608: {
! 609: struct babel_proto *p = ifa->proto;
! 610:
! 611: msg->type = BABEL_TLV_IHU;
! 612: msg->ihu.addr = n->addr;
! 613: msg->ihu.rxcost = babel_compute_rxcost(n);
! 614: msg->ihu.interval = ifa->cf->ihu_interval;
! 615:
! 616: TRACE(D_PACKETS, "Sending IHU for %I with rxcost %d interval %d",
! 617: msg->ihu.addr, msg->ihu.rxcost, msg->ihu.interval);
! 618: }
! 619:
! 620: static void
! 621: babel_send_ihu(struct babel_iface *ifa, struct babel_neighbor *n)
! 622: {
! 623: union babel_msg msg = {};
! 624: babel_build_ihu(&msg, ifa, n);
! 625: babel_send_unicast(&msg, ifa, n->addr);
! 626: }
! 627:
! 628: static void
! 629: babel_send_ihus(struct babel_iface *ifa)
! 630: {
! 631: struct babel_neighbor *n;
! 632: WALK_LIST(n, ifa->neigh_list)
! 633: {
! 634: union babel_msg msg = {};
! 635: babel_build_ihu(&msg, ifa, n);
! 636: babel_enqueue(&msg, ifa);
! 637: }
! 638: }
! 639:
! 640: static void
! 641: babel_send_hello(struct babel_iface *ifa, u8 send_ihu)
! 642: {
! 643: struct babel_proto *p = ifa->proto;
! 644: union babel_msg msg = {};
! 645:
! 646: msg.type = BABEL_TLV_HELLO;
! 647: msg.hello.seqno = ifa->hello_seqno++;
! 648: msg.hello.interval = ifa->cf->hello_interval;
! 649:
! 650: TRACE(D_PACKETS, "Sending hello on %s with seqno %d interval %d",
! 651: ifa->ifname, msg.hello.seqno, msg.hello.interval);
! 652:
! 653: babel_enqueue(&msg, ifa);
! 654:
! 655: if (send_ihu)
! 656: babel_send_ihus(ifa);
! 657: }
! 658:
! 659: static void
! 660: babel_send_route_request(struct babel_entry *e, struct babel_neighbor *n)
! 661: {
! 662: struct babel_proto *p = e->proto;
! 663: struct babel_iface *ifa = n->ifa;
! 664: union babel_msg msg = {};
! 665:
! 666: TRACE(D_PACKETS, "Sending route request for %I/%d to %I",
! 667: e->n.prefix, e->n.pxlen, n->addr);
! 668:
! 669: msg.type = BABEL_TLV_ROUTE_REQUEST;
! 670: msg.route_request.prefix = e->n.prefix;
! 671: msg.route_request.plen = e->n.pxlen;
! 672:
! 673: babel_send_unicast(&msg, ifa, n->addr);
! 674: }
! 675:
! 676: static void
! 677: babel_send_wildcard_request(struct babel_iface *ifa)
! 678: {
! 679: struct babel_proto *p = ifa->proto;
! 680: union babel_msg msg = {};
! 681:
! 682: TRACE(D_PACKETS, "Sending wildcard route request on %s",
! 683: ifa->ifname);
! 684:
! 685: msg.type = BABEL_TLV_ROUTE_REQUEST;
! 686: msg.route_request.full = 1;
! 687:
! 688: babel_enqueue(&msg, ifa);
! 689: }
! 690:
! 691: static void
! 692: babel_send_seqno_request(struct babel_entry *e)
! 693: {
! 694: struct babel_proto *p = e->proto;
! 695: struct babel_route *r = e->selected_in;
! 696: struct babel_iface *ifa = NULL;
! 697: struct babel_source *s = NULL;
! 698: union babel_msg msg = {};
! 699:
! 700: s = babel_find_source(e, r->router_id);
! 701: if (!s || !babel_cache_seqno_request(p, e->n.prefix, e->n.pxlen, r->router_id, s->seqno + 1))
! 702: return;
! 703:
! 704: TRACE(D_PACKETS, "Sending seqno request for %I/%d router-id %lR seqno %d",
! 705: e->n.prefix, e->n.pxlen, r->router_id, s->seqno + 1);
! 706:
! 707: msg.type = BABEL_TLV_SEQNO_REQUEST;
! 708: msg.seqno_request.plen = e->n.pxlen;
! 709: msg.seqno_request.seqno = s->seqno + 1;
! 710: msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT;
! 711: msg.seqno_request.router_id = r->router_id;
! 712: msg.seqno_request.prefix = e->n.prefix;
! 713:
! 714: WALK_LIST(ifa, p->interfaces)
! 715: babel_enqueue(&msg, ifa);
! 716: }
! 717:
! 718: static void
! 719: babel_unicast_seqno_request(struct babel_route *r)
! 720: {
! 721: struct babel_entry *e = r->e;
! 722: struct babel_proto *p = e->proto;
! 723: struct babel_iface *ifa = r->neigh->ifa;
! 724: struct babel_source *s = NULL;
! 725: union babel_msg msg = {};
! 726:
! 727: s = babel_find_source(e, r->router_id);
! 728: if (!s || !babel_cache_seqno_request(p, e->n.prefix, e->n.pxlen, r->router_id, s->seqno + 1))
! 729: return;
! 730:
! 731: TRACE(D_PACKETS, "Sending seqno request for %I/%d router-id %lR seqno %d",
! 732: e->n.prefix, e->n.pxlen, r->router_id, s->seqno + 1);
! 733:
! 734: msg.type = BABEL_TLV_SEQNO_REQUEST;
! 735: msg.seqno_request.plen = e->n.pxlen;
! 736: msg.seqno_request.seqno = s->seqno + 1;
! 737: msg.seqno_request.hop_count = BABEL_INITIAL_HOP_COUNT;
! 738: msg.seqno_request.router_id = r->router_id;
! 739: msg.seqno_request.prefix = e->n.prefix;
! 740:
! 741: babel_send_unicast(&msg, ifa, r->neigh->addr);
! 742: }
! 743:
! 744: /**
! 745: * babel_send_update - send route table updates
! 746: * @ifa: Interface to transmit on
! 747: * @changed: Only send entries changed since this time
! 748: *
! 749: * This function produces update TLVs for all entries changed since the time
! 750: * indicated by the &changed parameter and queues them for transmission on the
! 751: * selected interface. During the process, the feasibility distance for each
! 752: * transmitted entry is updated.
! 753: */
! 754: static void
! 755: babel_send_update(struct babel_iface *ifa, bird_clock_t changed)
! 756: {
! 757: struct babel_proto *p = ifa->proto;
! 758:
! 759: FIB_WALK(&p->rtable, n)
! 760: {
! 761: struct babel_entry *e = (void *) n;
! 762: struct babel_route *r = e->selected_out;
! 763:
! 764: if (!r)
! 765: continue;
! 766:
! 767: /* Our own seqno might have changed, in which case we update the routes we
! 768: originate. */
! 769: if ((r->router_id == p->router_id) && (r->seqno < p->update_seqno))
! 770: {
! 771: r->seqno = p->update_seqno;
! 772: e->updated = now;
! 773: }
! 774:
! 775: /* Skip routes that weren't updated since 'changed' time */
! 776: if (e->updated < changed)
! 777: continue;
! 778:
! 779: TRACE(D_PACKETS, "Sending update for %I/%d router-id %lR seqno %d metric %d",
! 780: e->n.prefix, e->n.pxlen, r->router_id, r->seqno, r->metric);
! 781:
! 782: union babel_msg msg = {};
! 783: msg.type = BABEL_TLV_UPDATE;
! 784: msg.update.plen = e->n.pxlen;
! 785: msg.update.interval = ifa->cf->update_interval;
! 786: msg.update.seqno = r->seqno;
! 787: msg.update.metric = r->metric;
! 788: msg.update.prefix = e->n.prefix;
! 789: msg.update.router_id = r->router_id;
! 790:
! 791: babel_enqueue(&msg, ifa);
! 792:
! 793: /* Update feasibility distance for redistributed routes */
! 794: if (!OUR_ROUTE(r))
! 795: {
! 796: struct babel_source *s = babel_get_source(e, r->router_id);
! 797: s->expires = now + BABEL_GARBAGE_INTERVAL;
! 798:
! 799: if ((msg.update.seqno > s->seqno) ||
! 800: ((msg.update.seqno == s->seqno) && (msg.update.metric < s->metric)))
! 801: {
! 802: s->seqno = msg.update.seqno;
! 803: s->metric = msg.update.metric;
! 804: }
! 805: }
! 806: }
! 807: FIB_WALK_END;
! 808: }
! 809:
! 810: static void
! 811: babel_trigger_iface_update(struct babel_iface *ifa)
! 812: {
! 813: struct babel_proto *p = ifa->proto;
! 814:
! 815: /* Interface not active or already scheduled */
! 816: if (!ifa->up || ifa->want_triggered)
! 817: return;
! 818:
! 819: TRACE(D_EVENTS, "Scheduling triggered updates for %s seqno %d",
! 820: ifa->iface->name, p->update_seqno);
! 821:
! 822: ifa->want_triggered = now;
! 823: babel_iface_kick_timer(ifa);
! 824: }
! 825:
! 826: /* Sends and update on all interfaces. */
! 827: static void
! 828: babel_trigger_update(struct babel_proto *p)
! 829: {
! 830: if (p->triggered)
! 831: return;
! 832:
! 833: struct babel_iface *ifa;
! 834: WALK_LIST(ifa, p->interfaces)
! 835: babel_trigger_iface_update(ifa);
! 836:
! 837: p->triggered = 1;
! 838: }
! 839:
! 840: /* A retraction is an update with an infinite metric */
! 841: static void
! 842: babel_send_retraction(struct babel_iface *ifa, ip_addr prefix, int plen)
! 843: {
! 844: struct babel_proto *p = ifa->proto;
! 845: union babel_msg msg = {};
! 846:
! 847: TRACE(D_PACKETS, "Sending retraction for %I/%d seqno %d",
! 848: prefix, plen, p->update_seqno);
! 849:
! 850: msg.type = BABEL_TLV_UPDATE;
! 851: msg.update.plen = plen;
! 852: msg.update.interval = ifa->cf->update_interval;
! 853: msg.update.seqno = p->update_seqno;
! 854: msg.update.metric = BABEL_INFINITY;
! 855: msg.update.prefix = prefix;
! 856:
! 857: babel_enqueue(&msg, ifa);
! 858: }
! 859:
! 860: static void
! 861: babel_send_wildcard_retraction(struct babel_iface *ifa)
! 862: {
! 863: struct babel_proto *p = ifa->proto;
! 864: union babel_msg msg = {};
! 865:
! 866: TRACE(D_PACKETS, "Sending wildcard retraction on %s", ifa->ifname);
! 867:
! 868: msg.type = BABEL_TLV_UPDATE;
! 869: msg.update.wildcard = 1;
! 870: msg.update.interval = ifa->cf->update_interval;
! 871: msg.update.seqno = p->update_seqno;
! 872: msg.update.metric = BABEL_INFINITY;
! 873:
! 874: babel_enqueue(&msg, ifa);
! 875: }
! 876:
! 877:
! 878: /*
! 879: * TLV handler helpers
! 880: */
! 881:
! 882: /* Update hello history according to Appendix A1 of the RFC */
! 883: static void
! 884: babel_update_hello_history(struct babel_neighbor *n, u16 seqno, u16 interval)
! 885: {
! 886: /*
! 887: * Compute the difference between expected and received seqno (modulo 2^16).
! 888: * If the expected and received seqnos are within 16 of each other, the modular
! 889: * difference is going to be less than 16 for one of the directions. Otherwise,
! 890: * the values differ too much, so just reset the state.
! 891: */
! 892:
! 893: u16 delta = ((uint) seqno - (uint) n->next_hello_seqno);
! 894:
! 895: if (delta == 0)
! 896: {
! 897: /* Do nothing */
! 898: }
! 899: else if (delta <= 16)
! 900: {
! 901: /* Sending node decreased interval; fast-forward */
! 902: n->hello_map <<= delta;
! 903: n->hello_cnt = MIN(n->hello_cnt + delta, 16);
! 904: }
! 905: else if (delta >= 0xfff0)
! 906: {
! 907: u8 diff = (0xffff - delta);
! 908: /* Sending node increased interval; undo history */
! 909: n->hello_map >>= diff;
! 910: n->hello_cnt = (diff < n->hello_cnt) ? n->hello_cnt - diff : 0;
! 911: }
! 912: else
! 913: {
! 914: /* Note state reset - flush entries */
! 915: n->hello_map = n->hello_cnt = 0;
! 916: }
! 917:
! 918: /* Current entry */
! 919: n->hello_map = (n->hello_map << 1) | 1;
! 920: n->next_hello_seqno = seqno+1;
! 921: if (n->hello_cnt < 16) n->hello_cnt++;
! 922: n->hello_expiry = now + BABEL_HELLO_EXPIRY_FACTOR(interval);
! 923: }
! 924:
! 925: static void
! 926: babel_expire_seqno_requests(struct babel_proto *p)
! 927: {
! 928: struct babel_seqno_request *n, *nx;
! 929: WALK_LIST_DELSAFE(n, nx, p->seqno_cache)
! 930: {
! 931: if ((n->updated + BABEL_SEQNO_REQUEST_EXPIRY) <= now)
! 932: {
! 933: rem_node(NODE n);
! 934: sl_free(p->seqno_slab, n);
! 935: }
! 936: }
! 937: }
! 938:
! 939: /*
! 940: * Checks the seqno request cache for a matching request and returns failure if
! 941: * found. Otherwise, a new entry is stored in the cache.
! 942: */
! 943: static int
! 944: babel_cache_seqno_request(struct babel_proto *p, ip_addr prefix, u8 plen,
! 945: u64 router_id, u16 seqno)
! 946: {
! 947: struct babel_seqno_request *r;
! 948:
! 949: WALK_LIST(r, p->seqno_cache)
! 950: {
! 951: if (ipa_equal(r->prefix, prefix) && (r->plen == plen) &&
! 952: (r->router_id == router_id) && (r->seqno == seqno))
! 953: return 0;
! 954: }
! 955:
! 956: /* no entries found */
! 957: r = sl_alloc(p->seqno_slab);
! 958: r->prefix = prefix;
! 959: r->plen = plen;
! 960: r->router_id = router_id;
! 961: r->seqno = seqno;
! 962: r->updated = now;
! 963: add_tail(&p->seqno_cache, NODE r);
! 964:
! 965: return 1;
! 966: }
! 967:
! 968: static void
! 969: babel_forward_seqno_request(struct babel_entry *e,
! 970: struct babel_msg_seqno_request *in,
! 971: ip_addr sender)
! 972: {
! 973: struct babel_proto *p = e->proto;
! 974: struct babel_route *r;
! 975:
! 976: TRACE(D_PACKETS, "Forwarding seqno request for %I/%d router-id %lR seqno %d",
! 977: e->n.prefix, e->n.pxlen, in->router_id, in->seqno);
! 978:
! 979: WALK_LIST(r, e->routes)
! 980: {
! 981: if ((r->router_id == in->router_id) &&
! 982: !OUR_ROUTE(r) &&
! 983: !ipa_equal(r->neigh->addr, sender))
! 984: {
! 985: if (!babel_cache_seqno_request(p, e->n.prefix, e->n.pxlen, in->router_id, in->seqno))
! 986: return;
! 987:
! 988: union babel_msg msg = {};
! 989: msg.type = BABEL_TLV_SEQNO_REQUEST;
! 990: msg.seqno_request.plen = in->plen;
! 991: msg.seqno_request.seqno = in->seqno;
! 992: msg.seqno_request.hop_count = in->hop_count-1;
! 993: msg.seqno_request.router_id = in->router_id;
! 994: msg.seqno_request.prefix = e->n.prefix;
! 995:
! 996: babel_send_unicast(&msg, r->neigh->ifa, r->neigh->addr);
! 997: return;
! 998: }
! 999: }
! 1000: }
! 1001:
! 1002:
! 1003: /*
! 1004: * TLV handlers
! 1005: */
! 1006:
! 1007: void
! 1008: babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa)
! 1009: {
! 1010: struct babel_proto *p = ifa->proto;
! 1011: struct babel_msg_ack_req *msg = &m->ack_req;
! 1012:
! 1013: TRACE(D_PACKETS, "Handling ACK request nonce %d interval %d",
! 1014: msg->nonce, msg->interval);
! 1015:
! 1016: babel_send_ack(ifa, msg->sender, msg->nonce);
! 1017: }
! 1018:
! 1019: void
! 1020: babel_handle_hello(union babel_msg *m, struct babel_iface *ifa)
! 1021: {
! 1022: struct babel_proto *p = ifa->proto;
! 1023: struct babel_msg_hello *msg = &m->hello;
! 1024:
! 1025: TRACE(D_PACKETS, "Handling hello seqno %d interval %d",
! 1026: msg->seqno, msg->interval);
! 1027:
! 1028: struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
! 1029: babel_update_hello_history(n, msg->seqno, msg->interval);
! 1030: if (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS)
! 1031: babel_send_ihu(ifa, n);
! 1032: }
! 1033:
! 1034: void
! 1035: babel_handle_ihu(union babel_msg *m, struct babel_iface *ifa)
! 1036: {
! 1037: struct babel_proto *p = ifa->proto;
! 1038: struct babel_msg_ihu *msg = &m->ihu;
! 1039:
! 1040: /* Ignore IHUs that are not about us */
! 1041: if ((msg->ae != BABEL_AE_WILDCARD) && !ipa_equal(msg->addr, ifa->addr))
! 1042: return;
! 1043:
! 1044: TRACE(D_PACKETS, "Handling IHU rxcost %d interval %d",
! 1045: msg->rxcost, msg->interval);
! 1046:
! 1047: struct babel_neighbor *n = babel_get_neighbor(ifa, msg->sender);
! 1048: n->txcost = msg->rxcost;
! 1049: n->ihu_expiry = now + BABEL_IHU_EXPIRY_FACTOR(msg->interval);
! 1050: }
! 1051:
! 1052: /**
! 1053: * babel_handle_update - handle incoming route updates
! 1054: * @m: Incoming update TLV
! 1055: * @ifa: Interface the update was received on
! 1056: *
! 1057: * This function is called as a handler for update TLVs and handles the updating
! 1058: * and maintenance of route entries in Babel's internal routing cache. The
! 1059: * handling follows the actions described in the Babel RFC, and at the end of
! 1060: * each update handling, babel_select_route() is called on the affected entry to
! 1061: * optionally update the selected routes and propagate them to the core.
! 1062: */
! 1063: void
! 1064: babel_handle_update(union babel_msg *m, struct babel_iface *ifa)
! 1065: {
! 1066: struct babel_proto *p = ifa->proto;
! 1067: struct babel_msg_update *msg = &m->update;
! 1068:
! 1069: struct babel_neighbor *nbr;
! 1070: struct babel_entry *e;
! 1071: struct babel_source *s;
! 1072: struct babel_route *r;
! 1073: node *n;
! 1074: int feasible;
! 1075:
! 1076: TRACE(D_PACKETS, "Handling update for %I/%d with seqno %d metric %d",
! 1077: msg->prefix, msg->plen, msg->seqno, msg->metric);
! 1078:
! 1079: nbr = babel_find_neighbor(ifa, msg->sender);
! 1080: if (!nbr)
! 1081: {
! 1082: DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg->sender);
! 1083: return;
! 1084: }
! 1085:
! 1086: if (msg->router_id == p->router_id)
! 1087: {
! 1088: DBG("Babel: Ignoring update for our own router ID.\n");
! 1089: return;
! 1090: }
! 1091:
! 1092: /*
! 1093: * RFC section 3.5.4:
! 1094: *
! 1095: * When a Babel node receives an update (id, prefix, seqno, metric) from a
! 1096: * neighbour neigh with a link cost value equal to cost, it checks whether it
! 1097: * already has a routing table entry indexed by (neigh, id, prefix).
! 1098: *
! 1099: * If no such entry exists:
! 1100: *
! 1101: * o if the update is unfeasible, it is ignored;
! 1102: *
! 1103: * o if the metric is infinite (the update is a retraction), the update is
! 1104: * ignored;
! 1105: *
! 1106: * o otherwise, a new route table entry is created, indexed by (neigh, id,
! 1107: * prefix), with seqno equal to seqno and an advertised metric equal to the
! 1108: * metric carried by the update.
! 1109: *
! 1110: * If such an entry exists:
! 1111: *
! 1112: * o if the entry is currently installed and the update is unfeasible, then
! 1113: * the behaviour depends on whether the router-ids of the two entries match.
! 1114: * If the router-ids are different, the update is treated as though it were
! 1115: * a retraction (i.e., as though the metric were FFFF hexadecimal). If the
! 1116: * router-ids are equal, the update is ignored;
! 1117: *
! 1118: * o otherwise (i.e., if either the update is feasible or the entry is not
! 1119: * currently installed), then the entry's sequence number, advertised
! 1120: * metric, metric, and router-id are updated and, unless the advertised
! 1121: * metric is infinite, the route's expiry timer is reset to a small multiple
! 1122: * of the Interval value included in the update.
! 1123: */
! 1124:
! 1125: /* Retraction */
! 1126: if (msg->metric == BABEL_INFINITY)
! 1127: {
! 1128: if (msg->wildcard)
! 1129: {
! 1130: /*
! 1131: * Special case: This is a retraction of all prefixes announced by this
! 1132: * neighbour (see second-to-last paragraph of section 4.4.9 in the RFC).
! 1133: */
! 1134: WALK_LIST(n, nbr->routes)
! 1135: {
! 1136: r = SKIP_BACK(struct babel_route, neigh_route, n);
! 1137: r->metric = BABEL_INFINITY;
! 1138: babel_select_route(r->e);
! 1139: }
! 1140: }
! 1141: else
! 1142: {
! 1143: e = babel_find_entry(p, msg->prefix, msg->plen);
! 1144:
! 1145: if (!e)
! 1146: return;
! 1147:
! 1148: /* The route entry indexed by neighbour */
! 1149: r = babel_find_route(e, nbr);
! 1150:
! 1151: if (!r)
! 1152: return;
! 1153:
! 1154: r->metric = BABEL_INFINITY;
! 1155: babel_select_route(e);
! 1156: }
! 1157:
! 1158: /* Done with retractions */
! 1159: return;
! 1160: }
! 1161:
! 1162: e = babel_get_entry(p, msg->prefix, msg->plen);
! 1163: r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */
! 1164: s = babel_find_source(e, msg->router_id); /* for feasibility */
! 1165: feasible = babel_is_feasible(s, msg->seqno, msg->metric);
! 1166:
! 1167: if (!r)
! 1168: {
! 1169: if (!feasible)
! 1170: return;
! 1171:
! 1172: r = babel_get_route(e, nbr);
! 1173: r->advert_metric = msg->metric;
! 1174: r->router_id = msg->router_id;
! 1175: r->metric = babel_compute_metric(nbr, msg->metric);
! 1176: r->next_hop = msg->next_hop;
! 1177: r->seqno = msg->seqno;
! 1178: }
! 1179: else if (r == r->e->selected_in && !feasible)
! 1180: {
! 1181: /*
! 1182: * Route is installed and update is infeasible - we may lose the route,
! 1183: * so send a unicast seqno request (section 3.8.2.2 second paragraph).
! 1184: */
! 1185: babel_unicast_seqno_request(r);
! 1186:
! 1187: if (msg->router_id == r->router_id)
! 1188: return;
! 1189:
! 1190: /* Treat as retraction */
! 1191: r->metric = BABEL_INFINITY;
! 1192: }
! 1193: else
! 1194: {
! 1195: /* Last paragraph above - update the entry */
! 1196: r->advert_metric = msg->metric;
! 1197: r->metric = babel_compute_metric(nbr, msg->metric);
! 1198: r->next_hop = msg->next_hop;
! 1199:
! 1200: r->router_id = msg->router_id;
! 1201: r->seqno = msg->seqno;
! 1202:
! 1203: r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval);
! 1204: r->expires = now + r->expiry_interval;
! 1205: if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL)
! 1206: r->refresh_time = now + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL;
! 1207:
! 1208: /* If the route is not feasible at this point, it means it is from another
! 1209: neighbour than the one currently selected; so send a unicast seqno
! 1210: request to try to get a better route (section 3.8.2.2 last paragraph). */
! 1211: if (!feasible)
! 1212: babel_unicast_seqno_request(r);
! 1213: }
! 1214:
! 1215: babel_select_route(e);
! 1216: }
! 1217:
! 1218: void
! 1219: babel_handle_route_request(union babel_msg *m, struct babel_iface *ifa)
! 1220: {
! 1221: struct babel_proto *p = ifa->proto;
! 1222: struct babel_msg_route_request *msg = &m->route_request;
! 1223:
! 1224: /* RFC 6126 3.8.1.1 */
! 1225:
! 1226: /* Wildcard request - full update on the interface */
! 1227: if (msg->full)
! 1228: {
! 1229: TRACE(D_PACKETS, "Handling wildcard route request");
! 1230: ifa->want_triggered = 1;
! 1231: return;
! 1232: }
! 1233:
! 1234: TRACE(D_PACKETS, "Handling route request for %I/%d", msg->prefix, msg->plen);
! 1235:
! 1236: /* Non-wildcard request - see if we have an entry for the route.
! 1237: If not, send a retraction, otherwise send an update. */
! 1238: struct babel_entry *e = babel_find_entry(p, msg->prefix, msg->plen);
! 1239: if (!e)
! 1240: {
! 1241: babel_send_retraction(ifa, msg->prefix, msg->plen);
! 1242: }
! 1243: else
! 1244: {
! 1245: babel_trigger_iface_update(ifa);
! 1246: e->updated = now;
! 1247: }
! 1248: }
! 1249:
! 1250:
! 1251: void
! 1252: babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa)
! 1253: {
! 1254: struct babel_proto *p = ifa->proto;
! 1255: struct babel_msg_seqno_request *msg = &m->seqno_request;
! 1256:
! 1257: /* RFC 6126 3.8.1.2 */
! 1258:
! 1259: TRACE(D_PACKETS, "Handling seqno request for %I/%d router-id %lR seqno %d hop count %d",
! 1260: msg->prefix, msg->plen, msg->router_id, msg->seqno, msg->hop_count);
! 1261:
! 1262: /* Ignore if we have no such entry or entry has infinite metric */
! 1263: struct babel_entry *e = babel_find_entry(p, msg->prefix, msg->plen);
! 1264: if (!e || !e->selected_out || (e->selected_out->metric == BABEL_INFINITY))
! 1265: return;
! 1266:
! 1267: /* Trigger update on incoming interface if we have a selected route with
! 1268: different router id or seqno no smaller than requested */
! 1269: struct babel_route *r = e->selected_out;
! 1270: if ((r->router_id != msg->router_id) || ge_mod64k(r->seqno, msg->seqno))
! 1271: {
! 1272: babel_trigger_iface_update(ifa);
! 1273: e->updated = now;
! 1274: return;
! 1275: }
! 1276:
! 1277: /* Seqno is larger; check if we own the router id */
! 1278: if (msg->router_id == p->router_id)
! 1279: {
! 1280: /* Ours; update seqno and trigger global update */
! 1281: p->update_seqno++;
! 1282: babel_trigger_update(p);
! 1283: }
! 1284: else
! 1285: {
! 1286: /* Not ours; forward if TTL allows it */
! 1287: if (msg->hop_count > 1)
! 1288: babel_forward_seqno_request(e, msg, msg->sender);
! 1289: }
! 1290: }
! 1291:
! 1292:
! 1293: /*
! 1294: * Babel interfaces
! 1295: */
! 1296:
! 1297: /**
! 1298: * babel_iface_timer - Babel interface timer handler
! 1299: * @t: Timer
! 1300: *
! 1301: * This function is called by the per-interface timer and triggers sending of
! 1302: * periodic Hello's and both triggered and periodic updates. Periodic Hello's
! 1303: * and updates are simply handled by setting the next_{hello,regular} variables
! 1304: * on the interface, and triggering an update (and resetting the variable)
! 1305: * whenever 'now' exceeds that value.
! 1306: *
! 1307: * For triggered updates, babel_trigger_iface_update() will set the
! 1308: * want_triggered field on the interface to a timestamp value. If this is set
! 1309: * (and the next_triggered time has passed; this is a rate limiting mechanism),
! 1310: * babel_send_update() will be called with this timestamp as the second
! 1311: * parameter. This causes updates to be send consisting of only the routes that
! 1312: * have changed since the time saved in want_triggered.
! 1313: *
! 1314: * Mostly when an update is triggered, the route being modified will be set to
! 1315: * the value of 'now' at the time of the trigger; the >= comparison for
! 1316: * selecting which routes to send in the update will make sure this is included.
! 1317: */
! 1318: static void
! 1319: babel_iface_timer(timer *t)
! 1320: {
! 1321: struct babel_iface *ifa = t->data;
! 1322: struct babel_proto *p = ifa->proto;
! 1323: bird_clock_t hello_period = ifa->cf->hello_interval;
! 1324: bird_clock_t update_period = ifa->cf->update_interval;
! 1325:
! 1326: if (now >= ifa->next_hello)
! 1327: {
! 1328: babel_send_hello(ifa, (ifa->cf->type == BABEL_IFACE_TYPE_WIRELESS ||
! 1329: ifa->hello_seqno % BABEL_IHU_INTERVAL_FACTOR == 0));
! 1330: ifa->next_hello += hello_period * (1 + (now - ifa->next_hello) / hello_period);
! 1331: }
! 1332:
! 1333: if (now >= ifa->next_regular)
! 1334: {
! 1335: TRACE(D_EVENTS, "Sending regular updates on %s", ifa->ifname);
! 1336: babel_send_update(ifa, 0);
! 1337: ifa->next_regular += update_period * (1 + (now - ifa->next_regular) / update_period);
! 1338: ifa->want_triggered = 0;
! 1339: p->triggered = 0;
! 1340: }
! 1341: else if (ifa->want_triggered && (now >= ifa->next_triggered))
! 1342: {
! 1343: TRACE(D_EVENTS, "Sending triggered updates on %s", ifa->ifname);
! 1344: babel_send_update(ifa, ifa->want_triggered);
! 1345: ifa->next_triggered = now + MIN(5, update_period / 2 + 1);
! 1346: ifa->want_triggered = 0;
! 1347: p->triggered = 0;
! 1348: }
! 1349:
! 1350: bird_clock_t next_event = MIN(ifa->next_hello, ifa->next_regular);
! 1351: tm_start(ifa->timer, ifa->want_triggered ? 1 : (next_event - now));
! 1352: }
! 1353:
! 1354: static inline void
! 1355: babel_iface_kick_timer(struct babel_iface *ifa)
! 1356: {
! 1357: if (ifa->timer->expires > (now + 1))
! 1358: tm_start(ifa->timer, 1);
! 1359: }
! 1360:
! 1361: static void
! 1362: babel_iface_start(struct babel_iface *ifa)
! 1363: {
! 1364: struct babel_proto *p = ifa->proto;
! 1365:
! 1366: TRACE(D_EVENTS, "Starting interface %s", ifa->ifname);
! 1367:
! 1368: ifa->next_hello = now + (random() % ifa->cf->hello_interval) + 1;
! 1369: ifa->next_regular = now + (random() % ifa->cf->update_interval) + 1;
! 1370: ifa->next_triggered = now + MIN(5, ifa->cf->update_interval / 2 + 1);
! 1371: ifa->want_triggered = 0; /* We send an immediate update (below) */
! 1372: tm_start(ifa->timer, 1);
! 1373: ifa->up = 1;
! 1374:
! 1375: babel_send_hello(ifa, 0);
! 1376: babel_send_wildcard_retraction(ifa);
! 1377: babel_send_wildcard_request(ifa);
! 1378: babel_send_update(ifa, 0); /* Full update */
! 1379: }
! 1380:
! 1381: static void
! 1382: babel_iface_stop(struct babel_iface *ifa)
! 1383: {
! 1384: struct babel_proto *p = ifa->proto;
! 1385: struct babel_neighbor *nbr;
! 1386: struct babel_route *r;
! 1387: node *n;
! 1388:
! 1389: TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname);
! 1390:
! 1391: /*
! 1392: * Rather than just flushing the neighbours, we set the metric of their routes
! 1393: * to infinity. This allows us to keep the neighbour hello state for when the
! 1394: * interface comes back up. The routes will also be kept until they expire.
! 1395: */
! 1396: WALK_LIST(nbr, ifa->neigh_list)
! 1397: {
! 1398: WALK_LIST(n, nbr->routes)
! 1399: {
! 1400: r = SKIP_BACK(struct babel_route, neigh_route, n);
! 1401: r->metric = BABEL_INFINITY;
! 1402: r->expires = now + r->expiry_interval;
! 1403: babel_select_route(r->e);
! 1404: }
! 1405: }
! 1406:
! 1407: tm_stop(ifa->timer);
! 1408: ifa->up = 0;
! 1409: }
! 1410:
! 1411: static inline int
! 1412: babel_iface_link_up(struct babel_iface *ifa)
! 1413: {
! 1414: return !ifa->cf->check_link || (ifa->iface->flags & IF_LINK_UP);
! 1415: }
! 1416:
! 1417: static void
! 1418: babel_iface_update_state(struct babel_iface *ifa)
! 1419: {
! 1420: int up = ifa->sk && babel_iface_link_up(ifa);
! 1421:
! 1422: if (up == ifa->up)
! 1423: return;
! 1424:
! 1425: if (up)
! 1426: babel_iface_start(ifa);
! 1427: else
! 1428: babel_iface_stop(ifa);
! 1429: }
! 1430:
! 1431: static void
! 1432: babel_iface_update_buffers(struct babel_iface *ifa)
! 1433: {
! 1434: if (!ifa->sk)
! 1435: return;
! 1436:
! 1437: uint mtu = MAX(BABEL_MIN_MTU, ifa->iface->mtu);
! 1438: uint rbsize = ifa->cf->rx_buffer ?: mtu;
! 1439: uint tbsize = ifa->cf->tx_length ?: mtu;
! 1440: rbsize = MAX(rbsize, tbsize);
! 1441:
! 1442: sk_set_rbsize(ifa->sk, rbsize);
! 1443: sk_set_tbsize(ifa->sk, tbsize);
! 1444:
! 1445: ifa->tx_length = tbsize - BABEL_OVERHEAD;
! 1446: }
! 1447:
! 1448: static struct babel_iface*
! 1449: babel_find_iface(struct babel_proto *p, struct iface *what)
! 1450: {
! 1451: struct babel_iface *ifa;
! 1452:
! 1453: WALK_LIST (ifa, p->interfaces)
! 1454: if (ifa->iface == what)
! 1455: return ifa;
! 1456:
! 1457: return NULL;
! 1458: }
! 1459:
! 1460: static void
! 1461: babel_iface_locked(struct object_lock *lock)
! 1462: {
! 1463: struct babel_iface *ifa = lock->data;
! 1464: struct babel_proto *p = ifa->proto;
! 1465:
! 1466: if (!babel_open_socket(ifa))
! 1467: {
! 1468: log(L_ERR "%s: Cannot open socket for %s", p->p.name, ifa->iface->name);
! 1469: return;
! 1470: }
! 1471:
! 1472: babel_iface_update_buffers(ifa);
! 1473: babel_iface_update_state(ifa);
! 1474: }
! 1475:
! 1476: static void
! 1477: babel_add_iface(struct babel_proto *p, struct iface *new, struct babel_iface_config *ic)
! 1478: {
! 1479: struct babel_iface *ifa;
! 1480:
! 1481: TRACE(D_EVENTS, "Adding interface %s", new->name);
! 1482:
! 1483: pool *pool = rp_new(p->p.pool, new->name);
! 1484:
! 1485: ifa = mb_allocz(pool, sizeof(struct babel_iface));
! 1486: ifa->proto = p;
! 1487: ifa->iface = new;
! 1488: ifa->cf = ic;
! 1489: ifa->pool = pool;
! 1490: ifa->ifname = new->name;
! 1491:
! 1492: add_tail(&p->interfaces, NODE ifa);
! 1493:
! 1494: struct ifa *addr;
! 1495: WALK_LIST(addr, new->addrs)
! 1496: if (ipa_is_link_local(addr->ip))
! 1497: ifa->addr = addr->ip;
! 1498:
! 1499: if (ipa_zero(ifa->addr))
! 1500: log(L_WARN "%s: Cannot find link-local addr on %s", p->p.name, new->name);
! 1501:
! 1502: init_list(&ifa->neigh_list);
! 1503: ifa->hello_seqno = 1;
! 1504:
! 1505: ifa->timer = tm_new_set(ifa->pool, babel_iface_timer, ifa, 0, 0);
! 1506:
! 1507: init_list(&ifa->msg_queue);
! 1508: ifa->send_event = ev_new(ifa->pool);
! 1509: ifa->send_event->hook = babel_send_queue;
! 1510: ifa->send_event->data = ifa;
! 1511:
! 1512: struct object_lock *lock = olock_new(ifa->pool);
! 1513: lock->type = OBJLOCK_UDP;
! 1514: lock->addr = IP6_BABEL_ROUTERS;
! 1515: lock->port = ifa->cf->port;
! 1516: lock->iface = ifa->iface;
! 1517: lock->hook = babel_iface_locked;
! 1518: lock->data = ifa;
! 1519:
! 1520: olock_acquire(lock);
! 1521: }
! 1522:
! 1523: static void
! 1524: babel_remove_iface(struct babel_proto *p, struct babel_iface *ifa)
! 1525: {
! 1526: TRACE(D_EVENTS, "Removing interface %s", ifa->iface->name);
! 1527:
! 1528: struct babel_neighbor *n;
! 1529: WALK_LIST_FIRST(n, ifa->neigh_list)
! 1530: babel_flush_neighbor(n);
! 1531:
! 1532: rem_node(NODE ifa);
! 1533:
! 1534: rfree(ifa->pool); /* contains ifa itself, locks, socket, etc */
! 1535: }
! 1536:
! 1537: static void
! 1538: babel_if_notify(struct proto *P, unsigned flags, struct iface *iface)
! 1539: {
! 1540: struct babel_proto *p = (void *) P;
! 1541: struct babel_config *cf = (void *) P->cf;
! 1542:
! 1543: if (iface->flags & IF_IGNORE)
! 1544: return;
! 1545:
! 1546: if (flags & IF_CHANGE_UP)
! 1547: {
! 1548: struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, iface->addr);
! 1549:
! 1550: /* we only speak multicast */
! 1551: if (!(iface->flags & IF_MULTICAST))
! 1552: return;
! 1553:
! 1554: if (ic)
! 1555: babel_add_iface(p, iface, ic);
! 1556:
! 1557: return;
! 1558: }
! 1559:
! 1560: struct babel_iface *ifa = babel_find_iface(p, iface);
! 1561:
! 1562: if (!ifa)
! 1563: return;
! 1564:
! 1565: if (flags & IF_CHANGE_DOWN)
! 1566: {
! 1567: babel_remove_iface(p, ifa);
! 1568: return;
! 1569: }
! 1570:
! 1571: if (flags & IF_CHANGE_MTU)
! 1572: babel_iface_update_buffers(ifa);
! 1573:
! 1574: if (flags & IF_CHANGE_LINK)
! 1575: babel_iface_update_state(ifa);
! 1576: }
! 1577:
! 1578: static int
! 1579: babel_reconfigure_iface(struct babel_proto *p, struct babel_iface *ifa, struct babel_iface_config *new)
! 1580: {
! 1581: struct babel_iface_config *old = ifa->cf;
! 1582:
! 1583: /* Change of these options would require to reset the iface socket */
! 1584: if ((new->port != old->port) ||
! 1585: (new->tx_tos != old->tx_tos) ||
! 1586: (new->tx_priority != old->tx_priority))
! 1587: return 0;
! 1588:
! 1589: TRACE(D_EVENTS, "Reconfiguring interface %s", ifa->iface->name);
! 1590:
! 1591: ifa->cf = new;
! 1592:
! 1593: if (ifa->next_hello > (now + new->hello_interval))
! 1594: ifa->next_hello = now + (random() % new->hello_interval) + 1;
! 1595:
! 1596: if (ifa->next_regular > (now + new->update_interval))
! 1597: ifa->next_regular = now + (random() % new->update_interval) + 1;
! 1598:
! 1599: if ((new->tx_length != old->tx_length) || (new->rx_buffer != old->rx_buffer))
! 1600: babel_iface_update_buffers(ifa);
! 1601:
! 1602: if (new->check_link != old->check_link)
! 1603: babel_iface_update_state(ifa);
! 1604:
! 1605: if (ifa->up)
! 1606: babel_iface_kick_timer(ifa);
! 1607:
! 1608: return 1;
! 1609: }
! 1610:
! 1611: static void
! 1612: babel_reconfigure_ifaces(struct babel_proto *p, struct babel_config *cf)
! 1613: {
! 1614: struct iface *iface;
! 1615:
! 1616: WALK_LIST(iface, iface_list)
! 1617: {
! 1618: if (! (iface->flags & IF_UP))
! 1619: continue;
! 1620:
! 1621: struct babel_iface *ifa = babel_find_iface(p, iface);
! 1622: struct babel_iface_config *ic = (void *) iface_patt_find(&cf->iface_list, iface, NULL);
! 1623:
! 1624: if (ifa && ic)
! 1625: {
! 1626: if (babel_reconfigure_iface(p, ifa, ic))
! 1627: continue;
! 1628:
! 1629: /* Hard restart */
! 1630: log(L_INFO "%s: Restarting interface %s", p->p.name, ifa->iface->name);
! 1631: babel_remove_iface(p, ifa);
! 1632: babel_add_iface(p, iface, ic);
! 1633: }
! 1634:
! 1635: if (ifa && !ic)
! 1636: babel_remove_iface(p, ifa);
! 1637:
! 1638: if (!ifa && ic)
! 1639: babel_add_iface(p, iface, ic);
! 1640: }
! 1641: }
! 1642:
! 1643:
! 1644: /*
! 1645: * Debugging and info output functions
! 1646: */
! 1647:
! 1648: static void
! 1649: babel_dump_source(struct babel_source *s)
! 1650: {
! 1651: debug("Source router_id %lR seqno %d metric %d expires %d\n",
! 1652: s->router_id, s->seqno, s->metric, s->expires ? s->expires-now : 0);
! 1653: }
! 1654:
! 1655: static void
! 1656: babel_dump_route(struct babel_route *r)
! 1657: {
! 1658: debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %d\n",
! 1659: r->neigh ? r->neigh->addr : IPA_NONE,
! 1660: r->neigh ? r->neigh->ifa->ifname : "(none)",
! 1661: r->seqno, r->advert_metric, r->metric,
! 1662: r->router_id, r->expires ? r->expires-now : 0);
! 1663: }
! 1664:
! 1665: static void
! 1666: babel_dump_entry(struct babel_entry *e)
! 1667: {
! 1668: struct babel_source *s;
! 1669: struct babel_route *r;
! 1670:
! 1671: debug("Babel: Entry %I/%d:\n", e->n.prefix, e->n.pxlen);
! 1672:
! 1673: WALK_LIST(s,e->sources)
! 1674: { debug(" "); babel_dump_source(s); }
! 1675:
! 1676: WALK_LIST(r,e->routes)
! 1677: {
! 1678: debug(" ");
! 1679: if (r == e->selected_out) debug("*");
! 1680: if (r == e->selected_in) debug("+");
! 1681: babel_dump_route(r);
! 1682: }
! 1683: }
! 1684:
! 1685: static void
! 1686: babel_dump_neighbor(struct babel_neighbor *n)
! 1687: {
! 1688: debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %d/%d\n",
! 1689: n->addr, n->txcost, n->hello_map, n->next_hello_seqno,
! 1690: n->hello_expiry ? n->hello_expiry - now : 0,
! 1691: n->ihu_expiry ? n->ihu_expiry - now : 0);
! 1692: }
! 1693:
! 1694: static void
! 1695: babel_dump_iface(struct babel_iface *ifa)
! 1696: {
! 1697: struct babel_neighbor *n;
! 1698:
! 1699: debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %d %d\n",
! 1700: ifa->ifname, ifa->addr, ifa->cf->rxcost, ifa->cf->type, ifa->hello_seqno,
! 1701: ifa->cf->hello_interval, ifa->cf->update_interval);
! 1702:
! 1703: WALK_LIST(n, ifa->neigh_list)
! 1704: { debug(" "); babel_dump_neighbor(n); }
! 1705: }
! 1706:
! 1707: static void
! 1708: babel_dump(struct proto *P)
! 1709: {
! 1710: struct babel_proto *p = (struct babel_proto *) P;
! 1711: struct babel_iface *ifa;
! 1712:
! 1713: debug("Babel: router id %lR update seqno %d\n", p->router_id, p->update_seqno);
! 1714:
! 1715: WALK_LIST(ifa, p->interfaces)
! 1716: babel_dump_iface(ifa);
! 1717:
! 1718: FIB_WALK(&p->rtable, n)
! 1719: {
! 1720: babel_dump_entry((struct babel_entry *) n);
! 1721: }
! 1722: FIB_WALK_END;
! 1723: }
! 1724:
! 1725: static void
! 1726: babel_get_route_info(rte *rte, byte *buf, ea_list *attrs UNUSED)
! 1727: {
! 1728: buf += bsprintf(buf, " (%d/%d) [%lR]", rte->pref, rte->u.babel.metric, rte->u.babel.router_id);
! 1729: }
! 1730:
! 1731: static int
! 1732: babel_get_attr(eattr *a, byte *buf, int buflen UNUSED)
! 1733: {
! 1734: switch (a->id)
! 1735: {
! 1736: case EA_BABEL_METRIC:
! 1737: bsprintf(buf, "metric: %d", a->u.data);
! 1738: return GA_FULL;
! 1739:
! 1740: case EA_BABEL_ROUTER_ID:
! 1741: {
! 1742: u64 rid = 0;
! 1743: memcpy(&rid, a->u.ptr->data, sizeof(u64));
! 1744: bsprintf(buf, "router_id: %lR", rid);
! 1745: return GA_FULL;
! 1746: }
! 1747:
! 1748: default:
! 1749: return GA_UNKNOWN;
! 1750: }
! 1751: }
! 1752:
! 1753: void
! 1754: babel_show_interfaces(struct proto *P, char *iff)
! 1755: {
! 1756: struct babel_proto *p = (void *) P;
! 1757: struct babel_iface *ifa = NULL;
! 1758: struct babel_neighbor *nbr = NULL;
! 1759:
! 1760: if (p->p.proto_state != PS_UP)
! 1761: {
! 1762: cli_msg(-1023, "%s: is not up", p->p.name);
! 1763: cli_msg(0, "");
! 1764: return;
! 1765: }
! 1766:
! 1767: cli_msg(-1023, "%s:", p->p.name);
! 1768: cli_msg(-1023, "%-10s %-6s %7s %6s %6s",
! 1769: "Interface", "State", "RX cost", "Nbrs", "Timer");
! 1770:
! 1771: WALK_LIST(ifa, p->interfaces)
! 1772: {
! 1773: if (iff && !patmatch(iff, ifa->iface->name))
! 1774: continue;
! 1775:
! 1776: int nbrs = 0;
! 1777: WALK_LIST(nbr, ifa->neigh_list)
! 1778: nbrs++;
! 1779:
! 1780: int timer = MIN(ifa->next_regular, ifa->next_hello) - now;
! 1781: cli_msg(-1023, "%-10s %-6s %7u %6u %6u",
! 1782: ifa->iface->name, (ifa->up ? "Up" : "Down"), ifa->cf->rxcost, nbrs, MAX(timer, 0));
! 1783: }
! 1784:
! 1785: cli_msg(0, "");
! 1786: }
! 1787:
! 1788: void
! 1789: babel_show_neighbors(struct proto *P, char *iff)
! 1790: {
! 1791: struct babel_proto *p = (void *) P;
! 1792: struct babel_iface *ifa = NULL;
! 1793: struct babel_neighbor *n = NULL;
! 1794: struct babel_route *r = NULL;
! 1795:
! 1796: if (p->p.proto_state != PS_UP)
! 1797: {
! 1798: cli_msg(-1024, "%s: is not up", p->p.name);
! 1799: cli_msg(0, "");
! 1800: return;
! 1801: }
! 1802:
! 1803: cli_msg(-1024, "%s:", p->p.name);
! 1804: cli_msg(-1024, "%-25s %-10s %6s %6s %10s",
! 1805: "IP address", "Interface", "Metric", "Routes", "Next hello");
! 1806:
! 1807: WALK_LIST(ifa, p->interfaces)
! 1808: {
! 1809: if (iff && !patmatch(iff, ifa->iface->name))
! 1810: continue;
! 1811:
! 1812: WALK_LIST(n, ifa->neigh_list)
! 1813: {
! 1814: int rts = 0;
! 1815: WALK_LIST(r, n->routes)
! 1816: rts++;
! 1817:
! 1818: int timer = n->hello_expiry - now;
! 1819: cli_msg(-1024, "%-25I %-10s %6u %6u %10u",
! 1820: n->addr, ifa->iface->name, n->txcost, rts, MAX(timer, 0));
! 1821: }
! 1822: }
! 1823:
! 1824: cli_msg(0, "");
! 1825: }
! 1826:
! 1827: void
! 1828: babel_show_entries(struct proto *P)
! 1829: {
! 1830: struct babel_proto *p = (void *) P;
! 1831: struct babel_entry *e = NULL;
! 1832: struct babel_source *s = NULL;
! 1833: struct babel_route *r = NULL;
! 1834:
! 1835: char ipbuf[STD_ADDRESS_P_LENGTH+5];
! 1836: char ridbuf[ROUTER_ID_64_LENGTH+1];
! 1837:
! 1838: if (p->p.proto_state != PS_UP)
! 1839: {
! 1840: cli_msg(-1025, "%s: is not up", p->p.name);
! 1841: cli_msg(0, "");
! 1842: return;
! 1843: }
! 1844:
! 1845: cli_msg(-1025, "%s:", p->p.name);
! 1846: cli_msg(-1025, "%-29s %-23s %6s %5s %7s %7s",
! 1847: "Prefix", "Router ID", "Metric", "Seqno", "Expires", "Sources");
! 1848:
! 1849: FIB_WALK(&p->rtable, n)
! 1850: {
! 1851: e = (struct babel_entry *) n;
! 1852: r = e->selected_in ? e->selected_in : e->selected_out;
! 1853:
! 1854: int srcs = 0;
! 1855: WALK_LIST(s, e->sources)
! 1856: srcs++;
! 1857:
! 1858: bsprintf(ipbuf, "%I/%u", e->n.prefix, e->n.pxlen);
! 1859:
! 1860: if (r)
! 1861: {
! 1862: if (r->router_id == p->router_id)
! 1863: bsprintf(ridbuf, "%s", "<self>");
! 1864: else
! 1865: bsprintf(ridbuf, "%lR", r->router_id);
! 1866:
! 1867: int time = r->expires ? r->expires - now : 0;
! 1868: cli_msg(-1025, "%-29s %-23s %6u %5u %7u %7u",
! 1869: ipbuf, ridbuf, r->metric, r->seqno, MAX(time, 0), srcs);
! 1870: }
! 1871: else
! 1872: {
! 1873: cli_msg(-1025, "%-29s %-44s %7u", ipbuf, "<pending>", srcs);
! 1874: }
! 1875: }
! 1876: FIB_WALK_END;
! 1877:
! 1878: cli_msg(0, "");
! 1879: }
! 1880:
! 1881:
! 1882: /*
! 1883: * Babel protocol glue
! 1884: */
! 1885:
! 1886: /**
! 1887: * babel_timer - global timer hook
! 1888: * @t: Timer
! 1889: *
! 1890: * This function is called by the global protocol instance timer and handles
! 1891: * expiration of routes and neighbours as well as pruning of the seqno request
! 1892: * cache.
! 1893: */
! 1894: static void
! 1895: babel_timer(timer *t)
! 1896: {
! 1897: struct babel_proto *p = t->data;
! 1898:
! 1899: babel_expire_routes(p);
! 1900: babel_expire_seqno_requests(p);
! 1901: babel_expire_neighbors(p);
! 1902: }
! 1903:
! 1904: static inline void
! 1905: babel_kick_timer(struct babel_proto *p)
! 1906: {
! 1907: if (p->timer->expires > (now + 1))
! 1908: tm_start(p->timer, 1);
! 1909: }
! 1910:
! 1911:
! 1912: static struct ea_list *
! 1913: babel_prepare_attrs(struct linpool *pool, ea_list *next, uint metric, u64 router_id)
! 1914: {
! 1915: struct ea_list *l = lp_alloc(pool, sizeof(struct ea_list) + 2*sizeof(eattr));
! 1916: struct adata *rid = lp_alloc(pool, sizeof(struct adata) + sizeof(u64));
! 1917: rid->length = sizeof(u64);
! 1918: memcpy(&rid->data, &router_id, sizeof(u64));
! 1919:
! 1920: l->next = next;
! 1921: l->flags = EALF_SORTED;
! 1922: l->count = 2;
! 1923:
! 1924: l->attrs[0].id = EA_BABEL_METRIC;
! 1925: l->attrs[0].flags = 0;
! 1926: l->attrs[0].type = EAF_TYPE_INT | EAF_TEMP;
! 1927: l->attrs[0].u.data = metric;
! 1928:
! 1929: l->attrs[1].id = EA_BABEL_ROUTER_ID;
! 1930: l->attrs[1].flags = 0;
! 1931: l->attrs[1].type = EAF_TYPE_OPAQUE | EAF_TEMP;
! 1932: l->attrs[1].u.ptr = rid;
! 1933:
! 1934: return l;
! 1935: }
! 1936:
! 1937:
! 1938: static int
! 1939: babel_import_control(struct proto *P, struct rte **rt, struct ea_list **attrs, struct linpool *pool)
! 1940: {
! 1941: struct babel_proto *p = (void *) P;
! 1942:
! 1943: /* Prepare attributes with initial values */
! 1944: if ((*rt)->attrs->source != RTS_BABEL)
! 1945: *attrs = babel_prepare_attrs(pool, NULL, 0, p->router_id);
! 1946:
! 1947: return 0;
! 1948: }
! 1949:
! 1950: static struct ea_list *
! 1951: babel_make_tmp_attrs(struct rte *rt, struct linpool *pool)
! 1952: {
! 1953: return babel_prepare_attrs(pool, NULL, rt->u.babel.metric, rt->u.babel.router_id);
! 1954: }
! 1955:
! 1956: static void
! 1957: babel_store_tmp_attrs(struct rte *rt, struct ea_list *attrs)
! 1958: {
! 1959: rt->u.babel.metric = ea_get_int(attrs, EA_BABEL_METRIC, 0);
! 1960: }
! 1961:
! 1962: /*
! 1963: * babel_rt_notify - core tells us about new route (possibly our own),
! 1964: * so store it into our data structures.
! 1965: */
! 1966: static void
! 1967: babel_rt_notify(struct proto *P, struct rtable *table UNUSED, struct network *net,
! 1968: struct rte *new, struct rte *old UNUSED, struct ea_list *attrs UNUSED)
! 1969: {
! 1970: struct babel_proto *p = (void *) P;
! 1971: struct babel_entry *e;
! 1972: struct babel_route *r;
! 1973:
! 1974: if (new)
! 1975: {
! 1976: /* Update */
! 1977: e = babel_get_entry(p, net->n.prefix, net->n.pxlen);
! 1978:
! 1979: if (new->attrs->src->proto != P)
! 1980: {
! 1981: r = babel_get_route(e, NULL);
! 1982: r->seqno = p->update_seqno;
! 1983: r->router_id = p->router_id;
! 1984: r->metric = 0; /* FIXME: should be selectable */
! 1985: }
! 1986: else
! 1987: r = e->selected_in;
! 1988:
! 1989: if (r != e->selected_out)
! 1990: {
! 1991: e->selected_out = r;
! 1992: e->updated = now;
! 1993: babel_trigger_update(p);
! 1994: }
! 1995: }
! 1996: else
! 1997: {
! 1998: /* Withdraw */
! 1999: e = babel_find_entry(p, net->n.prefix, net->n.pxlen);
! 2000: if (!e || !e->selected_out)
! 2001: return;
! 2002:
! 2003: if (OUR_ROUTE(e->selected_out))
! 2004: {
! 2005: /*
! 2006: * We originate this route, so set its metric to infinity and set an
! 2007: * expiry time. This causes a retraction to be sent, and later the route
! 2008: * to be flushed once the hold time has passed.
! 2009: */
! 2010: e->selected_out->metric = BABEL_INFINITY;
! 2011: e->selected_out->expires = now + BABEL_HOLD_TIME;
! 2012: e->updated = now;
! 2013: babel_trigger_update(p);
! 2014: }
! 2015: else
! 2016: {
! 2017: /*
! 2018: * This is a route originating from someone else that was lost; presumably
! 2019: * because an export filter was updated to filter it. This means we can't
! 2020: * set the metric to infinity (it would be overridden on subsequent
! 2021: * updates from the peer originating the route), so just clear the
! 2022: * exported route.
! 2023: *
! 2024: * This causes peers to expire the route after a while (like if we just
! 2025: * shut down), but it's the best we can do in these circumstances; and
! 2026: * since export filters presumably aren't updated that often this is
! 2027: * acceptable.
! 2028: */
! 2029: e->selected_out = NULL;
! 2030: }
! 2031: }
! 2032: }
! 2033:
! 2034: static int
! 2035: babel_rte_better(struct rte *new, struct rte *old)
! 2036: {
! 2037: return new->u.babel.metric < old->u.babel.metric;
! 2038: }
! 2039:
! 2040: static int
! 2041: babel_rte_same(struct rte *new, struct rte *old)
! 2042: {
! 2043: return ((new->u.babel.router_id == old->u.babel.router_id) &&
! 2044: (new->u.babel.metric == old->u.babel.metric));
! 2045: }
! 2046:
! 2047:
! 2048: static struct proto *
! 2049: babel_init(struct proto_config *cfg)
! 2050: {
! 2051: struct proto *P = proto_new(cfg, sizeof(struct babel_proto));
! 2052:
! 2053: P->accept_ra_types = RA_OPTIMAL;
! 2054: P->if_notify = babel_if_notify;
! 2055: P->rt_notify = babel_rt_notify;
! 2056: P->import_control = babel_import_control;
! 2057: P->make_tmp_attrs = babel_make_tmp_attrs;
! 2058: P->store_tmp_attrs = babel_store_tmp_attrs;
! 2059: P->rte_better = babel_rte_better;
! 2060: P->rte_same = babel_rte_same;
! 2061:
! 2062: return P;
! 2063: }
! 2064:
! 2065: static int
! 2066: babel_start(struct proto *P)
! 2067: {
! 2068: struct babel_proto *p = (void *) P;
! 2069: struct babel_config *cf = (void *) P->cf;
! 2070:
! 2071: fib_init(&p->rtable, P->pool, sizeof(struct babel_entry), 0, babel_init_entry);
! 2072: init_list(&p->interfaces);
! 2073: p->timer = tm_new_set(P->pool, babel_timer, p, 0, 1);
! 2074: tm_start(p->timer, 2);
! 2075: p->update_seqno = 1;
! 2076: p->router_id = proto_get_router_id(&cf->c);
! 2077:
! 2078: p->route_slab = sl_new(P->pool, sizeof(struct babel_route));
! 2079: p->source_slab = sl_new(P->pool, sizeof(struct babel_source));
! 2080: p->msg_slab = sl_new(P->pool, sizeof(struct babel_msg_node));
! 2081: p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request));
! 2082: init_list(&p->seqno_cache);
! 2083:
! 2084: p->log_pkt_tbf = (struct tbf){ .rate = 1, .burst = 5 };
! 2085:
! 2086: return PS_UP;
! 2087: }
! 2088:
! 2089: static inline void
! 2090: babel_iface_shutdown(struct babel_iface *ifa)
! 2091: {
! 2092: if (ifa->sk)
! 2093: {
! 2094: babel_send_wildcard_retraction(ifa);
! 2095: babel_send_queue(ifa);
! 2096: }
! 2097: }
! 2098:
! 2099: static int
! 2100: babel_shutdown(struct proto *P)
! 2101: {
! 2102: struct babel_proto *p = (void *) P;
! 2103: struct babel_iface *ifa;
! 2104:
! 2105: TRACE(D_EVENTS, "Shutdown requested");
! 2106:
! 2107: WALK_LIST(ifa, p->interfaces)
! 2108: babel_iface_shutdown(ifa);
! 2109:
! 2110: return PS_DOWN;
! 2111: }
! 2112:
! 2113: static int
! 2114: babel_reconfigure(struct proto *P, struct proto_config *c)
! 2115: {
! 2116: struct babel_proto *p = (void *) P;
! 2117: struct babel_config *new = (void *) c;
! 2118:
! 2119: TRACE(D_EVENTS, "Reconfiguring");
! 2120:
! 2121: p->p.cf = c;
! 2122: babel_reconfigure_ifaces(p, new);
! 2123:
! 2124: babel_trigger_update(p);
! 2125: babel_kick_timer(p);
! 2126:
! 2127: return 1;
! 2128: }
! 2129:
! 2130:
! 2131: struct protocol proto_babel = {
! 2132: .name = "Babel",
! 2133: .template = "babel%d",
! 2134: .attr_class = EAP_BABEL,
! 2135: .preference = DEF_PREF_BABEL,
! 2136: .config_size = sizeof(struct babel_config),
! 2137: .init = babel_init,
! 2138: .dump = babel_dump,
! 2139: .start = babel_start,
! 2140: .shutdown = babel_shutdown,
! 2141: .reconfigure = babel_reconfigure,
! 2142: .get_route_info = babel_get_route_info,
! 2143: .get_attr = babel_get_attr
! 2144: };
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to babel.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / proto / babel