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