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