2 * BIRD -- The Babel protocol
4 * Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
6 * Can be freely distributed and used under the terms of the GNU GPL.
8 * This file contains the main routines for handling and sending TLVs, as
9 * well as timers and interaction with the nest.
13 * DOC: The Babel protocol
15 * Babel (RFC6126) is a loop-avoiding distance-vector routing protocol that is
16 * robust and efficient both in ordinary wired networks and in wireless mesh
19 * The Babel protocol keeps state for each neighbour in a &babel_neighbor
20 * struct, tracking received Hello and I Heard You (IHU) messages. A
21 * &babel_interface struct keeps hello and update times for each interface, and
22 * a separate hello seqno is maintained for each interface.
24 * For each prefix, Babel keeps track of both the possible routes (with next hop
25 * and router IDs), as well as the feasibility distance for each prefix and
26 * router id. The prefix itself is tracked in a &babel_entry struct, while the
27 * possible routes for the prefix are tracked as &babel_route entries and the
28 * feasibility distance is maintained through &babel_source structures.
30 * The main route selection is done in babel_select_route(). This is called when
31 * an entry is updated by receiving updates from the network or when modified by
32 * internal timers. It performs feasibility checks on the available routes for
33 * the prefix and selects the one with the lowest metric to be announced to the
41 #define OUR_ROUTE(r) (r->neigh == NULL)
44 * Is one number greater or equal than another mod 2^16? This is based on the
45 * definition of serial number space in RFC 1982. Note that arguments are of
46 * uint type to avoid integer promotion to signed integer.
48 static inline int ge_mod64k(uint a
, uint b
)
49 { return (u16
)(a
- b
) < 0x8000; }
51 static void babel_dump_entry(struct babel_entry
*e
);
52 static void babel_dump_route(struct babel_route
*r
);
53 static void babel_select_route(struct babel_entry
*e
);
54 static void babel_send_route_request(struct babel_entry
*e
, struct babel_neighbor
*n
);
55 static void babel_send_wildcard_request(struct babel_iface
*ifa
);
56 static int babel_cache_seqno_request(struct babel_proto
*p
, ip_addr prefix
, u8 plen
,
57 u64 router_id
, u16 seqno
);
58 static void babel_trigger_iface_update(struct babel_iface
*ifa
);
59 static void babel_trigger_update(struct babel_proto
*p
);
60 static void babel_send_seqno_request(struct babel_entry
*e
);
61 static inline void babel_kick_timer(struct babel_proto
*p
);
62 static inline void babel_iface_kick_timer(struct babel_iface
*ifa
);
66 * Functions to maintain data structures
70 babel_init_entry(struct fib_node
*n
)
72 struct babel_entry
*e
= (void *) n
;
74 e
->selected_in
= NULL
;
75 e
->selected_out
= NULL
;
77 init_list(&e
->sources
);
78 init_list(&e
->routes
);
81 static inline struct babel_entry
*
82 babel_find_entry(struct babel_proto
*p
, ip_addr prefix
, u8 plen
)
84 return fib_find(&p
->rtable
, &prefix
, plen
);
87 static struct babel_entry
*
88 babel_get_entry(struct babel_proto
*p
, ip_addr prefix
, u8 plen
)
90 struct babel_entry
*e
= fib_get(&p
->rtable
, &prefix
, plen
);
95 static struct babel_source
*
96 babel_find_source(struct babel_entry
*e
, u64 router_id
)
98 struct babel_source
*s
;
100 WALK_LIST(s
, e
->sources
)
101 if (s
->router_id
== router_id
)
107 static struct babel_source
*
108 babel_get_source(struct babel_entry
*e
, u64 router_id
)
110 struct babel_proto
*p
= e
->proto
;
111 struct babel_source
*s
= babel_find_source(e
, router_id
);
116 s
= sl_alloc(p
->source_slab
);
117 s
->router_id
= router_id
;
118 s
->expires
= now
+ BABEL_GARBAGE_INTERVAL
;
120 s
->metric
= BABEL_INFINITY
;
121 add_tail(&e
->sources
, NODE s
);
127 babel_expire_sources(struct babel_entry
*e
)
129 struct babel_proto
*p
= e
->proto
;
130 struct babel_source
*n
, *nx
;
132 WALK_LIST_DELSAFE(n
, nx
, e
->sources
)
134 if (n
->expires
&& n
->expires
<= now
)
137 sl_free(p
->source_slab
, n
);
142 static struct babel_route
*
143 babel_find_route(struct babel_entry
*e
, struct babel_neighbor
*n
)
145 struct babel_route
*r
;
147 WALK_LIST(r
, e
->routes
)
154 static struct babel_route
*
155 babel_get_route(struct babel_entry
*e
, struct babel_neighbor
*nbr
)
157 struct babel_proto
*p
= e
->proto
;
158 struct babel_route
*r
= babel_find_route(e
, nbr
);
163 r
= sl_alloc(p
->route_slab
);
164 memset(r
, 0, sizeof(*r
));
166 add_tail(&e
->routes
, NODE r
);
171 r
->expires
= now
+ BABEL_GARBAGE_INTERVAL
;
172 add_tail(&nbr
->routes
, NODE
&r
->neigh_route
);
179 babel_flush_route(struct babel_route
*r
)
181 struct babel_proto
*p
= r
->e
->proto
;
183 DBG("Babel: Flush route %I/%d router_id %lR neigh %I\n",
184 r
->e
->n
.prefix
, r
->e
->n
.pxlen
, r
->router_id
, r
->neigh
? r
->neigh
->addr
: IPA_NONE
);
189 rem_node(&r
->neigh_route
);
191 if (r
->e
->selected_in
== r
)
192 r
->e
->selected_in
= NULL
;
194 if (r
->e
->selected_out
== r
)
195 r
->e
->selected_out
= NULL
;
197 sl_free(p
->route_slab
, r
);
201 babel_expire_route(struct babel_route
*r
)
203 struct babel_proto
*p
= r
->e
->proto
;
204 struct babel_entry
*e
= r
->e
;
206 TRACE(D_EVENTS
, "Route expiry timer for %I/%d router-id %lR fired",
207 e
->n
.prefix
, e
->n
.pxlen
, r
->router_id
);
209 if (r
->metric
< BABEL_INFINITY
)
211 r
->metric
= BABEL_INFINITY
;
212 r
->expires
= now
+ r
->expiry_interval
;
216 babel_flush_route(r
);
221 babel_refresh_route(struct babel_route
*r
)
223 if (!OUR_ROUTE(r
) && (r
== r
->e
->selected_in
))
224 babel_send_route_request(r
->e
, r
->neigh
);
230 babel_expire_routes(struct babel_proto
*p
)
232 struct babel_entry
*e
;
233 struct babel_route
*r
, *rx
;
234 struct fib_iterator fit
;
236 FIB_ITERATE_INIT(&fit
, &p
->rtable
);
239 FIB_ITERATE_START(&p
->rtable
, &fit
, n
)
241 e
= (struct babel_entry
*) n
;
244 WALK_LIST_DELSAFE(r
, rx
, e
->routes
)
246 if (r
->refresh_time
&& r
->refresh_time
<= now
)
247 babel_refresh_route(r
);
249 if (r
->expires
&& r
->expires
<= now
)
251 babel_expire_route(r
);
259 * We have to restart the iteration because there may be a cascade of
260 * synchronous events babel_select_route() -> nest table change ->
261 * babel_rt_notify() -> p->rtable change, invalidating hidden variables.
264 FIB_ITERATE_PUT(&fit
, n
);
265 babel_select_route(e
);
269 babel_expire_sources(e
);
271 /* Remove empty entries */
272 if (EMPTY_LIST(e
->sources
) && EMPTY_LIST(e
->routes
))
274 FIB_ITERATE_PUT(&fit
, n
);
275 fib_delete(&p
->rtable
, e
);
282 static struct babel_neighbor
*
283 babel_find_neighbor(struct babel_iface
*ifa
, ip_addr addr
)
285 struct babel_neighbor
*nbr
;
287 WALK_LIST(nbr
, ifa
->neigh_list
)
288 if (ipa_equal(nbr
->addr
, addr
))
294 static struct babel_neighbor
*
295 babel_get_neighbor(struct babel_iface
*ifa
, ip_addr addr
)
297 struct babel_neighbor
*nbr
= babel_find_neighbor(ifa
, addr
);
302 nbr
= mb_allocz(ifa
->pool
, sizeof(struct babel_neighbor
));
305 nbr
->txcost
= BABEL_INFINITY
;
306 init_list(&nbr
->routes
);
307 add_tail(&ifa
->neigh_list
, NODE nbr
);
313 babel_flush_neighbor(struct babel_neighbor
*nbr
)
315 struct babel_proto
*p
= nbr
->ifa
->proto
;
318 TRACE(D_EVENTS
, "Flushing neighbor %I", nbr
->addr
);
320 WALK_LIST_FIRST(n
, nbr
->routes
)
322 struct babel_route
*r
= SKIP_BACK(struct babel_route
, neigh_route
, n
);
323 struct babel_entry
*e
= r
->e
;
324 int selected
= (r
== e
->selected_in
);
326 babel_flush_route(r
);
329 babel_select_route(e
);
337 babel_expire_ihu(struct babel_neighbor
*nbr
)
339 nbr
->txcost
= BABEL_INFINITY
;
343 babel_expire_hello(struct babel_neighbor
*nbr
)
345 nbr
->hello_map
<<= 1;
347 if (nbr
->hello_cnt
< 16)
351 babel_flush_neighbor(nbr
);
355 babel_expire_neighbors(struct babel_proto
*p
)
357 struct babel_iface
*ifa
;
358 struct babel_neighbor
*nbr
, *nbx
;
360 WALK_LIST(ifa
, p
->interfaces
)
362 WALK_LIST_DELSAFE(nbr
, nbx
, ifa
->neigh_list
)
364 if (nbr
->ihu_expiry
&& nbr
->ihu_expiry
<= now
)
365 babel_expire_ihu(nbr
);
367 if (nbr
->hello_expiry
&& nbr
->hello_expiry
<= now
)
368 babel_expire_hello(nbr
);
375 * Best route selection
379 * From the RFC (section 3.5.1):
381 * a route advertisement carrying the quintuple (prefix, plen, router-id, seqno,
382 * metric) is feasible if one of the following conditions holds:
384 * - metric is infinite; or
386 * - no entry exists in the source table indexed by (id, prefix, plen); or
388 * - an entry (prefix, plen, router-id, seqno', metric') exists in the source
390 * - seqno' < seqno or
391 * - seqno = seqno' and metric < metric'.
394 babel_is_feasible(struct babel_source
*s
, u16 seqno
, u16 metric
)
397 (metric
== BABEL_INFINITY
) ||
398 (seqno
> s
->seqno
) ||
399 ((seqno
== s
->seqno
) && (metric
< s
->metric
));
403 babel_compute_rxcost(struct babel_neighbor
*n
)
405 struct babel_iface
*ifa
= n
->ifa
;
407 u16 map
=n
->hello_map
;
409 if (!map
) return BABEL_INFINITY
;
410 cnt
= u32_popcount(map
); // number of bits set
411 missed
= n
->hello_cnt
-cnt
;
413 if (ifa
->cf
->type
== BABEL_IFACE_TYPE_WIRELESS
)
415 /* ETX - Appendix 2.2 in the RFC.
417 beta = prob. of successful transmission.
418 rxcost = BABEL_RXCOST_WIRELESS/beta
420 Since: beta = 1-missed/n->hello_cnt = cnt/n->hello_cnt
421 Then: rxcost = BABEL_RXCOST_WIRELESS * n->hello_cnt / cnt
423 if (!cnt
) return BABEL_INFINITY
;
424 return BABEL_RXCOST_WIRELESS
* n
->hello_cnt
/ cnt
;
428 /* k-out-of-j selection - Appendix 2.1 in the RFC. */
429 DBG("Babel: Missed %d hellos from %I\n", missed
, n
->addr
);
430 /* Link is bad if more than half the expected hellos were lost */
431 return (missed
> n
->hello_cnt
/2) ? BABEL_INFINITY
: ifa
->cf
->rxcost
;
437 babel_compute_cost(struct babel_neighbor
*n
)
439 struct babel_iface
*ifa
= n
->ifa
;
440 u16 rxcost
= babel_compute_rxcost(n
);
441 if (rxcost
== BABEL_INFINITY
) return rxcost
;
442 else if (ifa
->cf
->type
== BABEL_IFACE_TYPE_WIRELESS
)
444 /* ETX - Appendix 2.2 in the RFC */
445 return (MAX(n
->txcost
, BABEL_RXCOST_WIRELESS
) * rxcost
)/BABEL_RXCOST_WIRELESS
;
449 /* k-out-of-j selection - Appendix 2.1 in the RFC. */
454 /* Simple additive metric - Appendix 3.1 in the RFC */
456 babel_compute_metric(struct babel_neighbor
*n
, uint metric
)
458 metric
+= babel_compute_cost(n
);
459 return MIN(metric
, BABEL_INFINITY
);
464 * babel_announce_rte - announce selected route to the core
465 * @p: Babel protocol instance
466 * @e: Babel route entry to announce
468 * This function announces a Babel entry to the core if it has a selected
469 * incoming path, and retracts it otherwise. If the selected entry has infinite
470 * metric, the route is announced as unreachable.
473 babel_announce_rte(struct babel_proto
*p
, struct babel_entry
*e
)
475 struct babel_route
*r
= e
->selected_in
;
479 net
*n
= net_get(p
->p
.table
, e
->n
.prefix
, e
->n
.pxlen
);
481 .src
= p
->p
.main_source
,
483 .scope
= SCOPE_UNIVERSE
,
485 .dest
= r
->metric
== BABEL_INFINITY
? RTD_UNREACHABLE
: RTD_ROUTER
,
487 .from
= r
->neigh
->addr
,
488 .iface
= r
->neigh
->ifa
->iface
,
491 if (r
->metric
< BABEL_INFINITY
)
494 rta
*a
= rta_lookup(&A
);
495 rte
*rte
= rte_get_temp(a
);
496 rte
->u
.babel
.metric
= r
->metric
;
497 rte
->u
.babel
.router_id
= r
->router_id
;
501 rte_update(&p
->p
, n
, rte
);
506 net
*n
= net_find(p
->p
.table
, e
->n
.prefix
, e
->n
.pxlen
);
507 rte_update(&p
->p
, n
, NULL
);
512 * babel_select_route - select best route for given route entry
513 * @e: Babel entry to select the best route for
515 * Select the best feasible route for a given prefix among the routes received
516 * from peers, and propagate it to the nest. This just selects the feasible
517 * route with the lowest metric.
519 * If no feasible route is available for a prefix that previously had a route
520 * selected, a seqno request is sent to try to get a valid route. In the
521 * meantime, the route is marked as infeasible in the nest (to blackhole packets
522 * going to it, as per the RFC).
524 * If no feasible route is available, and no previous route is selected, the
525 * route is removed from the nest entirely.
528 babel_select_route(struct babel_entry
*e
)
530 struct babel_proto
*p
= e
->proto
;
531 struct babel_route
*r
, *cur
= e
->selected_in
;
533 /* try to find the best feasible route */
534 WALK_LIST(r
, e
->routes
)
535 if (!OUR_ROUTE(r
) && /* prevent propagating our own routes back to core */
536 (!cur
|| r
->metric
< cur
->metric
) &&
537 babel_is_feasible(babel_find_source(e
, r
->router_id
), r
->seqno
, r
->advert_metric
))
540 if (cur
&& !OUR_ROUTE(cur
) &&
541 ((!e
->selected_in
&& cur
->metric
< BABEL_INFINITY
) ||
542 (e
->selected_in
&& cur
->metric
< e
->selected_in
->metric
)))
544 TRACE(D_EVENTS
, "Picked new route for prefix %I/%d: router id %lR metric %d",
545 e
->n
.prefix
, e
->n
.pxlen
, cur
->router_id
, cur
->metric
);
547 e
->selected_in
= cur
;
549 babel_announce_rte(p
, e
);
551 else if (!cur
|| cur
->metric
== BABEL_INFINITY
)
553 /* Couldn't find a feasible route. If we have a selected route, that means
554 it just became infeasible; so set it's metric to infinite and install it
555 (as unreachable), then send a seqno request.
557 babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/
560 TRACE(D_EVENTS
, "Lost feasible route for prefix %I/%d",
561 e
->n
.prefix
, e
->n
.pxlen
);
563 e
->selected_in
->metric
= BABEL_INFINITY
;
566 babel_send_seqno_request(e
);
567 babel_announce_rte(p
, e
);
571 /* No route currently selected, and no new one selected; this means we
572 don't have a route to this destination anymore (and were probably
573 called from an expiry timer). Remove the route from the nest. */
574 TRACE(D_EVENTS
, "Flushing route for prefix %I/%d", e
->n
.prefix
, e
->n
.pxlen
);
576 e
->selected_in
= NULL
;
578 babel_announce_rte(p
, e
);
584 * Functions to send replies
588 babel_send_ack(struct babel_iface
*ifa
, ip_addr dest
, u16 nonce
)
590 struct babel_proto
*p
= ifa
->proto
;
591 union babel_msg msg
= {};
593 TRACE(D_PACKETS
, "Sending ACK to %I with nonce %d", dest
, nonce
);
595 msg
.type
= BABEL_TLV_ACK
;
596 msg
.ack
.nonce
= nonce
;
598 babel_send_unicast(&msg
, ifa
, dest
);
602 babel_build_ihu(union babel_msg
*msg
, struct babel_iface
*ifa
, struct babel_neighbor
*n
)
604 struct babel_proto
*p
= ifa
->proto
;
606 msg
->type
= BABEL_TLV_IHU
;
607 msg
->ihu
.addr
= n
->addr
;
608 msg
->ihu
.rxcost
= babel_compute_rxcost(n
);
609 msg
->ihu
.interval
= ifa
->cf
->ihu_interval
;
611 TRACE(D_PACKETS
, "Sending IHU for %I with rxcost %d interval %d",
612 msg
->ihu
.addr
, msg
->ihu
.rxcost
, msg
->ihu
.interval
);
616 babel_send_ihu(struct babel_iface
*ifa
, struct babel_neighbor
*n
)
618 union babel_msg msg
= {};
619 babel_build_ihu(&msg
, ifa
, n
);
620 babel_send_unicast(&msg
, ifa
, n
->addr
);
624 babel_send_ihus(struct babel_iface
*ifa
)
626 struct babel_neighbor
*n
;
627 WALK_LIST(n
, ifa
->neigh_list
)
629 union babel_msg msg
= {};
630 babel_build_ihu(&msg
, ifa
, n
);
631 babel_enqueue(&msg
, ifa
);
636 babel_send_hello(struct babel_iface
*ifa
, u8 send_ihu
)
638 struct babel_proto
*p
= ifa
->proto
;
639 union babel_msg msg
= {};
641 msg
.type
= BABEL_TLV_HELLO
;
642 msg
.hello
.seqno
= ifa
->hello_seqno
++;
643 msg
.hello
.interval
= ifa
->cf
->hello_interval
;
645 TRACE(D_PACKETS
, "Sending hello on %s with seqno %d interval %d",
646 ifa
->ifname
, msg
.hello
.seqno
, msg
.hello
.interval
);
648 babel_enqueue(&msg
, ifa
);
651 babel_send_ihus(ifa
);
655 babel_send_route_request(struct babel_entry
*e
, struct babel_neighbor
*n
)
657 struct babel_proto
*p
= e
->proto
;
658 struct babel_iface
*ifa
= n
->ifa
;
659 union babel_msg msg
= {};
661 TRACE(D_PACKETS
, "Sending route request for %I/%d to %I",
662 e
->n
.prefix
, e
->n
.pxlen
, n
->addr
);
664 msg
.type
= BABEL_TLV_ROUTE_REQUEST
;
665 msg
.route_request
.prefix
= e
->n
.prefix
;
666 msg
.route_request
.plen
= e
->n
.pxlen
;
668 babel_send_unicast(&msg
, ifa
, n
->addr
);
672 babel_send_wildcard_request(struct babel_iface
*ifa
)
674 struct babel_proto
*p
= ifa
->proto
;
675 union babel_msg msg
= {};
677 TRACE(D_PACKETS
, "Sending wildcard route request on %s",
680 msg
.type
= BABEL_TLV_ROUTE_REQUEST
;
681 msg
.route_request
.full
= 1;
683 babel_enqueue(&msg
, ifa
);
687 babel_send_seqno_request(struct babel_entry
*e
)
689 struct babel_proto
*p
= e
->proto
;
690 struct babel_route
*r
= e
->selected_in
;
691 struct babel_iface
*ifa
= NULL
;
692 struct babel_source
*s
= NULL
;
693 union babel_msg msg
= {};
695 s
= babel_find_source(e
, r
->router_id
);
696 if (!s
|| !babel_cache_seqno_request(p
, e
->n
.prefix
, e
->n
.pxlen
, r
->router_id
, s
->seqno
+ 1))
699 TRACE(D_PACKETS
, "Sending seqno request for %I/%d router-id %lR seqno %d",
700 e
->n
.prefix
, e
->n
.pxlen
, r
->router_id
, s
->seqno
+ 1);
702 msg
.type
= BABEL_TLV_SEQNO_REQUEST
;
703 msg
.seqno_request
.plen
= e
->n
.pxlen
;
704 msg
.seqno_request
.seqno
= s
->seqno
+ 1;
705 msg
.seqno_request
.hop_count
= BABEL_INITIAL_HOP_COUNT
;
706 msg
.seqno_request
.router_id
= r
->router_id
;
707 msg
.seqno_request
.prefix
= e
->n
.prefix
;
709 WALK_LIST(ifa
, p
->interfaces
)
710 babel_enqueue(&msg
, ifa
);
714 babel_unicast_seqno_request(struct babel_route
*r
)
716 struct babel_entry
*e
= r
->e
;
717 struct babel_proto
*p
= e
->proto
;
718 struct babel_iface
*ifa
= r
->neigh
->ifa
;
719 struct babel_source
*s
= NULL
;
720 union babel_msg msg
= {};
722 s
= babel_find_source(e
, r
->router_id
);
723 if (!s
|| !babel_cache_seqno_request(p
, e
->n
.prefix
, e
->n
.pxlen
, r
->router_id
, s
->seqno
+ 1))
726 TRACE(D_PACKETS
, "Sending seqno request for %I/%d router-id %lR seqno %d",
727 e
->n
.prefix
, e
->n
.pxlen
, r
->router_id
, s
->seqno
+ 1);
729 msg
.type
= BABEL_TLV_SEQNO_REQUEST
;
730 msg
.seqno_request
.plen
= e
->n
.pxlen
;
731 msg
.seqno_request
.seqno
= s
->seqno
+ 1;
732 msg
.seqno_request
.hop_count
= BABEL_INITIAL_HOP_COUNT
;
733 msg
.seqno_request
.router_id
= r
->router_id
;
734 msg
.seqno_request
.prefix
= e
->n
.prefix
;
736 babel_send_unicast(&msg
, ifa
, r
->neigh
->addr
);
740 * babel_send_update - send route table updates
741 * @ifa: Interface to transmit on
742 * @changed: Only send entries changed since this time
744 * This function produces update TLVs for all entries changed since the time
745 * indicated by the &changed parameter and queues them for transmission on the
746 * selected interface. During the process, the feasibility distance for each
747 * transmitted entry is updated.
750 babel_send_update(struct babel_iface
*ifa
, bird_clock_t changed
)
752 struct babel_proto
*p
= ifa
->proto
;
754 FIB_WALK(&p
->rtable
, n
)
756 struct babel_entry
*e
= (void *) n
;
757 struct babel_route
*r
= e
->selected_out
;
762 /* Our own seqno might have changed, in which case we update the routes we
764 if ((r
->router_id
== p
->router_id
) && (r
->seqno
< p
->update_seqno
))
766 r
->seqno
= p
->update_seqno
;
770 /* Skip routes that weren't updated since 'changed' time */
771 if (e
->updated
< changed
)
774 TRACE(D_PACKETS
, "Sending update for %I/%d router-id %lR seqno %d metric %d",
775 e
->n
.prefix
, e
->n
.pxlen
, r
->router_id
, r
->seqno
, r
->metric
);
777 union babel_msg msg
= {};
778 msg
.type
= BABEL_TLV_UPDATE
;
779 msg
.update
.plen
= e
->n
.pxlen
;
780 msg
.update
.interval
= ifa
->cf
->update_interval
;
781 msg
.update
.seqno
= r
->seqno
;
782 msg
.update
.metric
= r
->metric
;
783 msg
.update
.prefix
= e
->n
.prefix
;
784 msg
.update
.router_id
= r
->router_id
;
786 /* Update feasibility distance */
787 struct babel_source
*s
= babel_get_source(e
, r
->router_id
);
788 s
->expires
= now
+ BABEL_GARBAGE_INTERVAL
;
789 if ((msg
.update
.seqno
> s
->seqno
) ||
790 ((msg
.update
.seqno
== s
->seqno
) && (msg
.update
.metric
< s
->metric
)))
792 s
->seqno
= msg
.update
.seqno
;
793 s
->metric
= msg
.update
.metric
;
795 babel_enqueue(&msg
, ifa
);
801 babel_trigger_iface_update(struct babel_iface
*ifa
)
803 struct babel_proto
*p
= ifa
->proto
;
805 /* Interface not active or already scheduled */
806 if (!ifa
->up
|| ifa
->want_triggered
)
809 TRACE(D_EVENTS
, "Scheduling triggered updates for %s seqno %d",
810 ifa
->iface
->name
, p
->update_seqno
);
812 ifa
->want_triggered
= now
;
813 babel_iface_kick_timer(ifa
);
816 /* Sends and update on all interfaces. */
818 babel_trigger_update(struct babel_proto
*p
)
823 struct babel_iface
*ifa
;
824 WALK_LIST(ifa
, p
->interfaces
)
825 babel_trigger_iface_update(ifa
);
830 /* A retraction is an update with an infinite metric */
832 babel_send_retraction(struct babel_iface
*ifa
, ip_addr prefix
, int plen
)
834 struct babel_proto
*p
= ifa
->proto
;
835 union babel_msg msg
= {};
837 TRACE(D_PACKETS
, "Sending retraction for %I/%d router-id %lR seqno %d",
838 prefix
, plen
, p
->router_id
, p
->update_seqno
);
840 msg
.type
= BABEL_TLV_UPDATE
;
841 msg
.update
.plen
= plen
;
842 msg
.update
.interval
= ifa
->cf
->update_interval
;
843 msg
.update
.seqno
= p
->update_seqno
;
844 msg
.update
.metric
= BABEL_INFINITY
;
845 msg
.update
.prefix
= prefix
;
846 msg
.update
.router_id
= p
->router_id
;
848 babel_enqueue(&msg
, ifa
);
853 * TLV handler helpers
856 /* Update hello history according to Appendix A1 of the RFC */
858 babel_update_hello_history(struct babel_neighbor
*n
, u16 seqno
, u16 interval
)
861 * Compute the difference between expected and received seqno (modulo 2^16).
862 * If the expected and received seqnos are within 16 of each other, the modular
863 * difference is going to be less than 16 for one of the directions. Otherwise,
864 * the values differ too much, so just reset the state.
867 u16 delta
= ((uint
) seqno
- (uint
) n
->next_hello_seqno
);
873 else if (delta
<= 16)
875 /* Sending node decreased interval; fast-forward */
876 n
->hello_map
<<= delta
;
877 n
->hello_cnt
= MIN(n
->hello_cnt
+ delta
, 16);
879 else if (delta
>= 0xfff0)
881 u8 diff
= (0xffff - delta
);
882 /* Sending node increased interval; undo history */
883 n
->hello_map
>>= diff
;
884 n
->hello_cnt
= (diff
< n
->hello_cnt
) ? n
->hello_cnt
- diff
: 0;
888 /* Note state reset - flush entries */
889 n
->hello_map
= n
->hello_cnt
= 0;
893 n
->hello_map
= (n
->hello_map
<< 1) | 1;
894 n
->next_hello_seqno
= seqno
+1;
895 if (n
->hello_cnt
< 16) n
->hello_cnt
++;
896 n
->hello_expiry
= now
+ BABEL_HELLO_EXPIRY_FACTOR(interval
);
900 babel_expire_seqno_requests(struct babel_proto
*p
)
902 struct babel_seqno_request
*n
, *nx
;
903 WALK_LIST_DELSAFE(n
, nx
, p
->seqno_cache
)
905 if ((n
->updated
+ BABEL_SEQNO_REQUEST_EXPIRY
) <= now
)
908 sl_free(p
->seqno_slab
, n
);
914 * Checks the seqno request cache for a matching request and returns failure if
915 * found. Otherwise, a new entry is stored in the cache.
918 babel_cache_seqno_request(struct babel_proto
*p
, ip_addr prefix
, u8 plen
,
919 u64 router_id
, u16 seqno
)
921 struct babel_seqno_request
*r
;
923 WALK_LIST(r
, p
->seqno_cache
)
925 if (ipa_equal(r
->prefix
, prefix
) && (r
->plen
== plen
) &&
926 (r
->router_id
== router_id
) && (r
->seqno
== seqno
))
930 /* no entries found */
931 r
= sl_alloc(p
->seqno_slab
);
934 r
->router_id
= router_id
;
937 add_tail(&p
->seqno_cache
, NODE r
);
943 babel_forward_seqno_request(struct babel_entry
*e
,
944 struct babel_msg_seqno_request
*in
,
947 struct babel_proto
*p
= e
->proto
;
948 struct babel_route
*r
;
950 TRACE(D_PACKETS
, "Forwarding seqno request for %I/%d router-id %lR seqno %d",
951 e
->n
.prefix
, e
->n
.pxlen
, in
->router_id
, in
->seqno
);
953 WALK_LIST(r
, e
->routes
)
955 if ((r
->router_id
== in
->router_id
) &&
957 !ipa_equal(r
->neigh
->addr
, sender
))
959 if (!babel_cache_seqno_request(p
, e
->n
.prefix
, e
->n
.pxlen
, in
->router_id
, in
->seqno
))
962 union babel_msg msg
= {};
963 msg
.type
= BABEL_TLV_SEQNO_REQUEST
;
964 msg
.seqno_request
.plen
= in
->plen
;
965 msg
.seqno_request
.seqno
= in
->seqno
;
966 msg
.seqno_request
.hop_count
= in
->hop_count
-1;
967 msg
.seqno_request
.router_id
= in
->router_id
;
968 msg
.seqno_request
.prefix
= e
->n
.prefix
;
970 babel_send_unicast(&msg
, r
->neigh
->ifa
, r
->neigh
->addr
);
982 babel_handle_ack_req(union babel_msg
*m
, struct babel_iface
*ifa
)
984 struct babel_proto
*p
= ifa
->proto
;
985 struct babel_msg_ack_req
*msg
= &m
->ack_req
;
987 TRACE(D_PACKETS
, "Handling ACK request nonce %d interval %d",
988 msg
->nonce
, msg
->interval
);
990 babel_send_ack(ifa
, msg
->sender
, msg
->nonce
);
994 babel_handle_hello(union babel_msg
*m
, struct babel_iface
*ifa
)
996 struct babel_proto
*p
= ifa
->proto
;
997 struct babel_msg_hello
*msg
= &m
->hello
;
999 TRACE(D_PACKETS
, "Handling hello seqno %d interval %d",
1000 msg
->seqno
, msg
->interval
);
1002 struct babel_neighbor
*n
= babel_get_neighbor(ifa
, msg
->sender
);
1003 babel_update_hello_history(n
, msg
->seqno
, msg
->interval
);
1004 if (ifa
->cf
->type
== BABEL_IFACE_TYPE_WIRELESS
)
1005 babel_send_ihu(ifa
, n
);
1009 babel_handle_ihu(union babel_msg
*m
, struct babel_iface
*ifa
)
1011 struct babel_proto
*p
= ifa
->proto
;
1012 struct babel_msg_ihu
*msg
= &m
->ihu
;
1014 /* Ignore IHUs that are not about us */
1015 if ((msg
->ae
!= BABEL_AE_WILDCARD
) && !ipa_equal(msg
->addr
, ifa
->addr
))
1018 TRACE(D_PACKETS
, "Handling IHU rxcost %d interval %d",
1019 msg
->rxcost
, msg
->interval
);
1021 struct babel_neighbor
*n
= babel_get_neighbor(ifa
, msg
->sender
);
1022 n
->txcost
= msg
->rxcost
;
1023 n
->ihu_expiry
= now
+ BABEL_IHU_EXPIRY_FACTOR(msg
->interval
);
1027 * babel_handle_update - handle incoming route updates
1028 * @m: Incoming update TLV
1029 * @ifa: Interface the update was received on
1031 * This function is called as a handler for update TLVs and handles the updating
1032 * and maintenance of route entries in Babel's internal routing cache. The
1033 * handling follows the actions described in the Babel RFC, and at the end of
1034 * each update handling, babel_select_route() is called on the affected entry to
1035 * optionally update the selected routes and propagate them to the core.
1038 babel_handle_update(union babel_msg
*m
, struct babel_iface
*ifa
)
1040 struct babel_proto
*p
= ifa
->proto
;
1041 struct babel_msg_update
*msg
= &m
->update
;
1043 struct babel_neighbor
*n
;
1044 struct babel_entry
*e
;
1045 struct babel_source
*s
;
1046 struct babel_route
*r
;
1049 TRACE(D_PACKETS
, "Handling update for %I/%d with seqno %d metric %d",
1050 msg
->prefix
, msg
->plen
, msg
->seqno
, msg
->metric
);
1052 n
= babel_find_neighbor(ifa
, msg
->sender
);
1055 DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg
->sender
);
1059 if (msg
->router_id
== p
->router_id
)
1061 DBG("Babel: Ignoring update for our own router ID.\n");
1066 * RFC section 3.5.4:
1068 * When a Babel node receives an update (id, prefix, seqno, metric) from a
1069 * neighbour neigh with a link cost value equal to cost, it checks whether it
1070 * already has a routing table entry indexed by (neigh, id, prefix).
1072 * If no such entry exists:
1074 * o if the update is unfeasible, it is ignored;
1076 * o if the metric is infinite (the update is a retraction), the update is
1079 * o otherwise, a new route table entry is created, indexed by (neigh, id,
1080 * prefix), with seqno equal to seqno and an advertised metric equal to the
1081 * metric carried by the update.
1083 * If such an entry exists:
1085 * o if the entry is currently installed and the update is unfeasible, then
1086 * the behaviour depends on whether the router-ids of the two entries match.
1087 * If the router-ids are different, the update is treated as though it were
1088 * a retraction (i.e., as though the metric were FFFF hexadecimal). If the
1089 * router-ids are equal, the update is ignored;
1091 * o otherwise (i.e., if either the update is feasible or the entry is not
1092 * currently installed), then the entry's sequence number, advertised
1093 * metric, metric, and router-id are updated and, unless the advertised
1094 * metric is infinite, the route's expiry timer is reset to a small multiple
1095 * of the Interval value included in the update.
1098 if (msg
->metric
== BABEL_INFINITY
)
1099 e
= babel_find_entry(p
, msg
->prefix
, msg
->plen
);
1101 e
= babel_get_entry(p
, msg
->prefix
, msg
->plen
);
1106 s
= babel_find_source(e
, msg
->router_id
); /* for feasibility */
1107 r
= babel_find_route(e
, n
); /* the route entry indexed by neighbour */
1108 feasible
= babel_is_feasible(s
, msg
->seqno
, msg
->metric
);
1112 if (!feasible
|| (msg
->metric
== BABEL_INFINITY
))
1115 r
= babel_get_route(e
, n
);
1116 r
->advert_metric
= msg
->metric
;
1117 r
->router_id
= msg
->router_id
;
1118 r
->metric
= babel_compute_metric(n
, msg
->metric
);
1119 r
->next_hop
= msg
->next_hop
;
1120 r
->seqno
= msg
->seqno
;
1122 else if (r
== r
->e
->selected_in
&& !feasible
)
1124 /* Route is installed and update is infeasible - we may lose the route, so
1125 send a unicast seqno request (section 3.8.2.2 second paragraph). */
1126 babel_unicast_seqno_request(r
);
1128 if (msg
->router_id
== r
->router_id
) return;
1129 r
->metric
= BABEL_INFINITY
; /* retraction */
1133 /* Last paragraph above - update the entry */
1134 r
->advert_metric
= msg
->metric
;
1135 r
->metric
= babel_compute_metric(n
, msg
->metric
);
1136 r
->router_id
= msg
->router_id
;
1137 r
->next_hop
= msg
->next_hop
;
1138 r
->seqno
= msg
->seqno
;
1140 if (msg
->metric
!= BABEL_INFINITY
)
1142 r
->expiry_interval
= BABEL_ROUTE_EXPIRY_FACTOR(msg
->interval
);
1143 r
->expires
= now
+ r
->expiry_interval
;
1144 if (r
->expiry_interval
> BABEL_ROUTE_REFRESH_INTERVAL
)
1145 r
->refresh_time
= now
+ r
->expiry_interval
- BABEL_ROUTE_REFRESH_INTERVAL
;
1148 /* If the route is not feasible at this point, it means it is from another
1149 neighbour than the one currently selected; so send a unicast seqno
1150 request to try to get a better route (section 3.8.2.2 last paragraph). */
1152 babel_unicast_seqno_request(r
);
1155 babel_select_route(e
);
1159 babel_handle_route_request(union babel_msg
*m
, struct babel_iface
*ifa
)
1161 struct babel_proto
*p
= ifa
->proto
;
1162 struct babel_msg_route_request
*msg
= &m
->route_request
;
1164 /* RFC 6126 3.8.1.1 */
1166 /* Wildcard request - full update on the interface */
1169 TRACE(D_PACKETS
, "Handling wildcard route request");
1170 ifa
->want_triggered
= 1;
1174 TRACE(D_PACKETS
, "Handling route request for %I/%d", msg
->prefix
, msg
->plen
);
1176 /* Non-wildcard request - see if we have an entry for the route.
1177 If not, send a retraction, otherwise send an update. */
1178 struct babel_entry
*e
= babel_find_entry(p
, msg
->prefix
, msg
->plen
);
1181 babel_send_retraction(ifa
, msg
->prefix
, msg
->plen
);
1185 babel_trigger_iface_update(ifa
);
1192 babel_handle_seqno_request(union babel_msg
*m
, struct babel_iface
*ifa
)
1194 struct babel_proto
*p
= ifa
->proto
;
1195 struct babel_msg_seqno_request
*msg
= &m
->seqno_request
;
1197 /* RFC 6126 3.8.1.2 */
1199 TRACE(D_PACKETS
, "Handling seqno request for %I/%d router-id %lR seqno %d hop count %d",
1200 msg
->prefix
, msg
->plen
, msg
->router_id
, msg
->seqno
, msg
->hop_count
);
1202 /* Ignore if we have no such entry or entry has infinite metric */
1203 struct babel_entry
*e
= babel_find_entry(p
, msg
->prefix
, msg
->plen
);
1204 if (!e
|| !e
->selected_out
|| (e
->selected_out
->metric
== BABEL_INFINITY
))
1207 /* Trigger update on incoming interface if we have a selected route with
1208 different router id or seqno no smaller than requested */
1209 struct babel_route
*r
= e
->selected_out
;
1210 if ((r
->router_id
!= msg
->router_id
) || ge_mod64k(r
->seqno
, msg
->seqno
))
1212 babel_trigger_iface_update(ifa
);
1217 /* Seqno is larger; check if we own the router id */
1218 if (msg
->router_id
== p
->router_id
)
1220 /* Ours; update seqno and trigger global update */
1222 babel_trigger_update(p
);
1226 /* Not ours; forward if TTL allows it */
1227 if (msg
->hop_count
> 1)
1228 babel_forward_seqno_request(e
, msg
, msg
->sender
);
1238 * babel_iface_timer - Babel interface timer handler
1241 * This function is called by the per-interface timer and triggers sending of
1242 * periodic Hello's and both triggered and periodic updates. Periodic Hello's
1243 * and updates are simply handled by setting the next_{hello,regular} variables
1244 * on the interface, and triggering an update (and resetting the variable)
1245 * whenever 'now' exceeds that value.
1247 * For triggered updates, babel_trigger_iface_update() will set the
1248 * want_triggered field on the interface to a timestamp value. If this is set
1249 * (and the next_triggered time has passed; this is a rate limiting mechanism),
1250 * babel_send_update() will be called with this timestamp as the second
1251 * parameter. This causes updates to be send consisting of only the routes that
1252 * have changed since the time saved in want_triggered.
1254 * Mostly when an update is triggered, the route being modified will be set to
1255 * the value of 'now' at the time of the trigger; the >= comparison for
1256 * selecting which routes to send in the update will make sure this is included.
1259 babel_iface_timer(timer
*t
)
1261 struct babel_iface
*ifa
= t
->data
;
1262 struct babel_proto
*p
= ifa
->proto
;
1263 bird_clock_t hello_period
= ifa
->cf
->hello_interval
;
1264 bird_clock_t update_period
= ifa
->cf
->update_interval
;
1266 if (now
>= ifa
->next_hello
)
1268 babel_send_hello(ifa
, (ifa
->cf
->type
== BABEL_IFACE_TYPE_WIRELESS
||
1269 ifa
->hello_seqno
% BABEL_IHU_INTERVAL_FACTOR
== 0));
1270 ifa
->next_hello
+= hello_period
* (1 + (now
- ifa
->next_hello
) / hello_period
);
1273 if (now
>= ifa
->next_regular
)
1275 TRACE(D_EVENTS
, "Sending regular updates on %s", ifa
->ifname
);
1276 babel_send_update(ifa
, 0);
1277 ifa
->next_regular
+= update_period
* (1 + (now
- ifa
->next_regular
) / update_period
);
1278 ifa
->want_triggered
= 0;
1281 else if (ifa
->want_triggered
&& (now
>= ifa
->next_triggered
))
1283 TRACE(D_EVENTS
, "Sending triggered updates on %s", ifa
->ifname
);
1284 babel_send_update(ifa
, ifa
->want_triggered
);
1285 ifa
->next_triggered
= now
+ MIN(5, update_period
/ 2 + 1);
1286 ifa
->want_triggered
= 0;
1290 bird_clock_t next_event
= MIN(ifa
->next_hello
, ifa
->next_regular
);
1291 tm_start(ifa
->timer
, ifa
->want_triggered
? 1 : (next_event
- now
));
1295 babel_iface_kick_timer(struct babel_iface
*ifa
)
1297 if (ifa
->timer
->expires
> (now
+ 1))
1298 tm_start(ifa
->timer
, 1);
1302 babel_iface_start(struct babel_iface
*ifa
)
1304 struct babel_proto
*p
= ifa
->proto
;
1306 TRACE(D_EVENTS
, "Starting interface %s", ifa
->ifname
);
1308 ifa
->next_hello
= now
+ (random() % ifa
->cf
->hello_interval
) + 1;
1309 ifa
->next_regular
= now
+ (random() % ifa
->cf
->update_interval
) + 1;
1310 ifa
->next_triggered
= now
+ MIN(5, ifa
->cf
->update_interval
/ 2 + 1);
1311 ifa
->want_triggered
= 0; /* We send an immediate update (below) */
1312 tm_start(ifa
->timer
, 1);
1315 babel_send_hello(ifa
, 0);
1316 babel_send_wildcard_request(ifa
);
1317 babel_send_update(ifa
, 0); /* Full update */
1321 babel_iface_stop(struct babel_iface
*ifa
)
1323 struct babel_proto
*p
= ifa
->proto
;
1324 struct babel_neighbor
*nbr
;
1325 struct babel_route
*r
;
1328 TRACE(D_EVENTS
, "Stopping interface %s", ifa
->ifname
);
1331 * Rather than just flushing the neighbours, we set the metric of their routes
1332 * to infinity. This allows us to keep the neighbour hello state for when the
1333 * interface comes back up. The routes will also be kept until they expire.
1335 WALK_LIST(nbr
, ifa
->neigh_list
)
1337 WALK_LIST(n
, nbr
->routes
)
1339 r
= SKIP_BACK(struct babel_route
, neigh_route
, n
);
1340 r
->metric
= BABEL_INFINITY
;
1341 r
->expires
= now
+ r
->expiry_interval
;
1342 babel_select_route(r
->e
);
1346 tm_stop(ifa
->timer
);
1351 babel_iface_link_up(struct babel_iface
*ifa
)
1353 return !ifa
->cf
->check_link
|| (ifa
->iface
->flags
& IF_LINK_UP
);
1357 babel_iface_update_state(struct babel_iface
*ifa
)
1359 int up
= ifa
->sk
&& babel_iface_link_up(ifa
);
1365 babel_iface_start(ifa
);
1367 babel_iface_stop(ifa
);
1371 babel_iface_update_buffers(struct babel_iface
*ifa
)
1376 uint mtu
= MAX(BABEL_MIN_MTU
, ifa
->iface
->mtu
);
1377 uint rbsize
= ifa
->cf
->rx_buffer
?: mtu
;
1378 uint tbsize
= ifa
->cf
->tx_length
?: mtu
;
1379 rbsize
= MAX(rbsize
, tbsize
);
1381 sk_set_rbsize(ifa
->sk
, rbsize
);
1382 sk_set_tbsize(ifa
->sk
, tbsize
);
1384 ifa
->tx_length
= tbsize
- BABEL_OVERHEAD
;
1387 static struct babel_iface
*
1388 babel_find_iface(struct babel_proto
*p
, struct iface
*what
)
1390 struct babel_iface
*ifa
;
1392 WALK_LIST (ifa
, p
->interfaces
)
1393 if (ifa
->iface
== what
)
1400 babel_iface_locked(struct object_lock
*lock
)
1402 struct babel_iface
*ifa
= lock
->data
;
1403 struct babel_proto
*p
= ifa
->proto
;
1405 if (!babel_open_socket(ifa
))
1407 log(L_ERR
"%s: Cannot open socket for %s", p
->p
.name
, ifa
->iface
->name
);
1411 babel_iface_update_buffers(ifa
);
1412 babel_iface_update_state(ifa
);
1416 babel_add_iface(struct babel_proto
*p
, struct iface
*new, struct babel_iface_config
*ic
)
1418 struct babel_iface
*ifa
;
1420 TRACE(D_EVENTS
, "Adding interface %s", new->name
);
1422 pool
*pool
= rp_new(p
->p
.pool
, new->name
);
1424 ifa
= mb_allocz(pool
, sizeof(struct babel_iface
));
1429 ifa
->ifname
= new->name
;
1431 add_tail(&p
->interfaces
, NODE ifa
);
1434 WALK_LIST(addr
, new->addrs
)
1435 if (ipa_is_link_local(addr
->ip
))
1436 ifa
->addr
= addr
->ip
;
1438 if (ipa_zero(ifa
->addr
))
1439 log(L_WARN
"%s: Cannot find link-local addr on %s", p
->p
.name
, new->name
);
1441 init_list(&ifa
->neigh_list
);
1442 ifa
->hello_seqno
= 1;
1444 ifa
->timer
= tm_new_set(ifa
->pool
, babel_iface_timer
, ifa
, 0, 0);
1446 init_list(&ifa
->msg_queue
);
1447 ifa
->send_event
= ev_new(ifa
->pool
);
1448 ifa
->send_event
->hook
= babel_send_queue
;
1449 ifa
->send_event
->data
= ifa
;
1451 struct object_lock
*lock
= olock_new(ifa
->pool
);
1452 lock
->type
= OBJLOCK_UDP
;
1453 lock
->addr
= IP6_BABEL_ROUTERS
;
1454 lock
->port
= ifa
->cf
->port
;
1455 lock
->iface
= ifa
->iface
;
1456 lock
->hook
= babel_iface_locked
;
1459 olock_acquire(lock
);
1463 babel_remove_iface(struct babel_proto
*p
, struct babel_iface
*ifa
)
1465 TRACE(D_EVENTS
, "Removing interface %s", ifa
->iface
->name
);
1467 struct babel_neighbor
*n
;
1468 WALK_LIST_FIRST(n
, ifa
->neigh_list
)
1469 babel_flush_neighbor(n
);
1473 rfree(ifa
->pool
); /* contains ifa itself, locks, socket, etc */
1477 babel_if_notify(struct proto
*P
, unsigned flags
, struct iface
*iface
)
1479 struct babel_proto
*p
= (void *) P
;
1480 struct babel_config
*cf
= (void *) P
->cf
;
1482 if (iface
->flags
& IF_IGNORE
)
1485 if (flags
& IF_CHANGE_UP
)
1487 struct babel_iface_config
*ic
= (void *) iface_patt_find(&cf
->iface_list
, iface
, iface
->addr
);
1489 /* we only speak multicast */
1490 if (!(iface
->flags
& IF_MULTICAST
))
1494 babel_add_iface(p
, iface
, ic
);
1499 struct babel_iface
*ifa
= babel_find_iface(p
, iface
);
1504 if (flags
& IF_CHANGE_DOWN
)
1506 babel_remove_iface(p
, ifa
);
1510 if (flags
& IF_CHANGE_MTU
)
1511 babel_iface_update_buffers(ifa
);
1513 if (flags
& IF_CHANGE_LINK
)
1514 babel_iface_update_state(ifa
);
1518 babel_reconfigure_iface(struct babel_proto
*p
, struct babel_iface
*ifa
, struct babel_iface_config
*new)
1520 struct babel_iface_config
*old
= ifa
->cf
;
1522 /* Change of these options would require to reset the iface socket */
1523 if ((new->port
!= old
->port
) ||
1524 (new->tx_tos
!= old
->tx_tos
) ||
1525 (new->tx_priority
!= old
->tx_priority
))
1528 TRACE(D_EVENTS
, "Reconfiguring interface %s", ifa
->iface
->name
);
1532 if (ifa
->next_regular
> (now
+ new->update_interval
))
1533 ifa
->next_regular
= now
+ (random() % new->update_interval
) + 1;
1535 if ((new->tx_length
!= old
->tx_length
) || (new->rx_buffer
!= old
->rx_buffer
))
1536 babel_iface_update_buffers(ifa
);
1538 if (new->check_link
!= old
->check_link
)
1539 babel_iface_update_state(ifa
);
1542 babel_iface_kick_timer(ifa
);
1548 babel_reconfigure_ifaces(struct babel_proto
*p
, struct babel_config
*cf
)
1550 struct iface
*iface
;
1552 WALK_LIST(iface
, iface_list
)
1554 if (! (iface
->flags
& IF_UP
))
1557 struct babel_iface
*ifa
= babel_find_iface(p
, iface
);
1558 struct babel_iface_config
*ic
= (void *) iface_patt_find(&cf
->iface_list
, iface
, NULL
);
1562 if (babel_reconfigure_iface(p
, ifa
, ic
))
1566 log(L_INFO
"%s: Restarting interface %s", p
->p
.name
, ifa
->iface
->name
);
1567 babel_remove_iface(p
, ifa
);
1568 babel_add_iface(p
, iface
, ic
);
1572 babel_remove_iface(p
, ifa
);
1575 babel_add_iface(p
, iface
, ic
);
1581 * Debugging and info output functions
1585 babel_dump_source(struct babel_source
*s
)
1587 debug("Source router_id %lR seqno %d metric %d expires %d\n",
1588 s
->router_id
, s
->seqno
, s
->metric
, s
->expires
? s
->expires
-now
: 0);
1592 babel_dump_route(struct babel_route
*r
)
1594 debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %d\n",
1595 r
->neigh
? r
->neigh
->addr
: IPA_NONE
,
1596 r
->neigh
? r
->neigh
->ifa
->ifname
: "(none)",
1597 r
->seqno
, r
->advert_metric
, r
->metric
,
1598 r
->router_id
, r
->expires
? r
->expires
-now
: 0);
1602 babel_dump_entry(struct babel_entry
*e
)
1604 struct babel_source
*s
;
1605 struct babel_route
*r
;
1607 debug("Babel: Entry %I/%d:\n", e
->n
.prefix
, e
->n
.pxlen
);
1609 WALK_LIST(s
,e
->sources
)
1610 { debug(" "); babel_dump_source(s
); }
1612 WALK_LIST(r
,e
->routes
)
1615 if (r
== e
->selected_out
) debug("*");
1616 if (r
== e
->selected_in
) debug("+");
1617 babel_dump_route(r
);
1622 babel_dump_neighbor(struct babel_neighbor
*n
)
1624 debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %d/%d\n",
1625 n
->addr
, n
->txcost
, n
->hello_map
, n
->next_hello_seqno
,
1626 n
->hello_expiry
? n
->hello_expiry
- now
: 0,
1627 n
->ihu_expiry
? n
->ihu_expiry
- now
: 0);
1631 babel_dump_iface(struct babel_iface
*ifa
)
1633 struct babel_neighbor
*n
;
1635 debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %d %d\n",
1636 ifa
->ifname
, ifa
->addr
, ifa
->cf
->rxcost
, ifa
->cf
->type
, ifa
->hello_seqno
,
1637 ifa
->cf
->hello_interval
, ifa
->cf
->update_interval
);
1639 WALK_LIST(n
, ifa
->neigh_list
)
1640 { debug(" "); babel_dump_neighbor(n
); }
1644 babel_dump(struct proto
*P
)
1646 struct babel_proto
*p
= (struct babel_proto
*) P
;
1647 struct babel_iface
*ifa
;
1649 debug("Babel: router id %lR update seqno %d\n", p
->router_id
, p
->update_seqno
);
1651 WALK_LIST(ifa
, p
->interfaces
)
1652 babel_dump_iface(ifa
);
1654 FIB_WALK(&p
->rtable
, n
)
1656 babel_dump_entry((struct babel_entry
*) n
);
1662 babel_get_route_info(rte
*rte
, byte
*buf
, ea_list
*attrs
)
1664 buf
+= bsprintf(buf
, " (%d/%d) [%lR]", rte
->pref
, rte
->u
.babel
.metric
, rte
->u
.babel
.router_id
);
1668 babel_get_attr(eattr
*a
, byte
*buf
, int buflen UNUSED
)
1672 case EA_BABEL_METRIC
:
1673 bsprintf(buf
, "metric: %d", a
->u
.data
);
1676 case EA_BABEL_ROUTER_ID
:
1679 memcpy(&rid
, a
->u
.ptr
->data
, sizeof(u64
));
1680 bsprintf(buf
, "router_id: %lR", rid
);
1690 babel_show_interfaces(struct proto
*P
, char *iff
)
1692 struct babel_proto
*p
= (void *) P
;
1693 struct babel_iface
*ifa
= NULL
;
1694 struct babel_neighbor
*nbr
= NULL
;
1696 if (p
->p
.proto_state
!= PS_UP
)
1698 cli_msg(-1023, "%s: is not up", p
->p
.name
);
1703 cli_msg(-1023, "%s:", p
->p
.name
);
1704 cli_msg(-1023, "%-10s %-6s %7s %6s %6s",
1705 "Interface", "State", "RX cost", "Nbrs", "Timer");
1707 WALK_LIST(ifa
, p
->interfaces
)
1709 if (iff
&& !patmatch(iff
, ifa
->iface
->name
))
1713 WALK_LIST(nbr
, ifa
->neigh_list
)
1716 int timer
= MIN(ifa
->next_regular
, ifa
->next_hello
) - now
;
1717 cli_msg(-1023, "%-10s %-6s %7u %6u %6u",
1718 ifa
->iface
->name
, (ifa
->up
? "Up" : "Down"), ifa
->cf
->rxcost
, nbrs
, MAX(timer
, 0));
1725 babel_show_neighbors(struct proto
*P
, char *iff
)
1727 struct babel_proto
*p
= (void *) P
;
1728 struct babel_iface
*ifa
= NULL
;
1729 struct babel_neighbor
*n
= NULL
;
1730 struct babel_route
*r
= NULL
;
1732 if (p
->p
.proto_state
!= PS_UP
)
1734 cli_msg(-1024, "%s: is not up", p
->p
.name
);
1739 cli_msg(-1024, "%s:", p
->p
.name
);
1740 cli_msg(-1024, "%-25s %-10s %6s %6s %10s",
1741 "IP address", "Interface", "Metric", "Routes", "Next hello");
1743 WALK_LIST(ifa
, p
->interfaces
)
1745 if (iff
&& !patmatch(iff
, ifa
->iface
->name
))
1748 WALK_LIST(n
, ifa
->neigh_list
)
1751 WALK_LIST(r
, n
->routes
)
1754 int timer
= n
->hello_expiry
- now
;
1755 cli_msg(-1024, "%-25I %-10s %6u %6u %10u",
1756 n
->addr
, ifa
->iface
->name
, n
->txcost
, rts
, MAX(timer
, 0));
1764 babel_show_entries(struct proto
*P
)
1766 struct babel_proto
*p
= (void *) P
;
1767 struct babel_entry
*e
= NULL
;
1768 struct babel_source
*s
= NULL
;
1769 struct babel_route
*r
= NULL
;
1771 char ipbuf
[STD_ADDRESS_P_LENGTH
+5];
1772 char ridbuf
[ROUTER_ID_64_LENGTH
+1];
1774 if (p
->p
.proto_state
!= PS_UP
)
1776 cli_msg(-1025, "%s: is not up", p
->p
.name
);
1781 cli_msg(-1025, "%s:", p
->p
.name
);
1782 cli_msg(-1025, "%-29s %-23s %6s %5s %7s %7s",
1783 "Prefix", "Router ID", "Metric", "Seqno", "Expires", "Sources");
1785 FIB_WALK(&p
->rtable
, n
)
1787 e
= (struct babel_entry
*) n
;
1788 r
= e
->selected_in
? e
->selected_in
: e
->selected_out
;
1791 WALK_LIST(s
, e
->sources
)
1794 bsprintf(ipbuf
, "%I/%u", e
->n
.prefix
, e
->n
.pxlen
);
1798 if (r
->router_id
== p
->router_id
)
1799 bsprintf(ridbuf
, "%s", "<self>");
1801 bsprintf(ridbuf
, "%lR", r
->router_id
);
1803 int time
= r
->expires
? r
->expires
- now
: 0;
1804 cli_msg(-1025, "%-29s %-23s %6u %5u %7u %7u",
1805 ipbuf
, ridbuf
, r
->metric
, r
->seqno
, MAX(time
, 0), srcs
);
1809 cli_msg(-1025, "%-29s %-44s %7u", ipbuf
, "<pending>", srcs
);
1819 * Babel protocol glue
1823 * babel_timer - global timer hook
1826 * This function is called by the global protocol instance timer and handles
1827 * expiration of routes and neighbours as well as pruning of the seqno request
1831 babel_timer(timer
*t
)
1833 struct babel_proto
*p
= t
->data
;
1835 babel_expire_routes(p
);
1836 babel_expire_seqno_requests(p
);
1837 babel_expire_neighbors(p
);
1841 babel_kick_timer(struct babel_proto
*p
)
1843 if (p
->timer
->expires
> (now
+ 1))
1844 tm_start(p
->timer
, 1);
1848 static struct ea_list
*
1849 babel_prepare_attrs(struct linpool
*pool
, ea_list
*next
, uint metric
, u64 router_id
)
1851 struct ea_list
*l
= lp_alloc(pool
, sizeof(struct ea_list
) + 2*sizeof(eattr
));
1852 struct adata
*rid
= lp_alloc(pool
, sizeof(struct adata
) + sizeof(u64
));
1853 rid
->length
= sizeof(u64
);
1854 memcpy(&rid
->data
, &router_id
, sizeof(u64
));
1857 l
->flags
= EALF_SORTED
;
1860 l
->attrs
[0].id
= EA_BABEL_METRIC
;
1861 l
->attrs
[0].flags
= 0;
1862 l
->attrs
[0].type
= EAF_TYPE_INT
| EAF_TEMP
;
1863 l
->attrs
[0].u
.data
= metric
;
1865 l
->attrs
[1].id
= EA_BABEL_ROUTER_ID
;
1866 l
->attrs
[1].flags
= 0;
1867 l
->attrs
[1].type
= EAF_TYPE_OPAQUE
| EAF_TEMP
;
1868 l
->attrs
[1].u
.ptr
= rid
;
1875 babel_import_control(struct proto
*P
, struct rte
**rt
, struct ea_list
**attrs
, struct linpool
*pool
)
1877 struct babel_proto
*p
= (void *) P
;
1879 /* Prepare attributes with initial values */
1880 if ((*rt
)->attrs
->source
!= RTS_BABEL
)
1881 *attrs
= babel_prepare_attrs(pool
, NULL
, 0, p
->router_id
);
1886 static struct ea_list
*
1887 babel_make_tmp_attrs(struct rte
*rt
, struct linpool
*pool
)
1889 return babel_prepare_attrs(pool
, NULL
, rt
->u
.babel
.metric
, rt
->u
.babel
.router_id
);
1893 babel_store_tmp_attrs(struct rte
*rt
, struct ea_list
*attrs
)
1895 rt
->u
.babel
.metric
= ea_get_int(attrs
, EA_BABEL_METRIC
, 0);
1899 * babel_rt_notify - core tells us about new route (possibly our own),
1900 * so store it into our data structures.
1903 babel_rt_notify(struct proto
*P
, struct rtable
*table UNUSED
, struct network
*net
,
1904 struct rte
*new, struct rte
*old
, struct ea_list
*attrs
)
1906 struct babel_proto
*p
= (void *) P
;
1907 struct babel_entry
*e
;
1908 struct babel_route
*r
;
1913 e
= babel_get_entry(p
, net
->n
.prefix
, net
->n
.pxlen
);
1915 if (new->attrs
->src
->proto
!= P
)
1917 r
= babel_get_route(e
, NULL
);
1918 r
->seqno
= p
->update_seqno
;
1919 r
->router_id
= p
->router_id
;
1920 r
->metric
= 0; /* FIXME: should be selectable */
1925 if (r
!= e
->selected_out
)
1927 e
->selected_out
= r
;
1929 babel_trigger_update(p
);
1935 e
= babel_find_entry(p
, net
->n
.prefix
, net
->n
.pxlen
);
1936 if (!e
|| !e
->selected_out
)
1939 if (OUR_ROUTE(e
->selected_out
))
1942 * We originate this route, so set its metric to infinity and set an
1943 * expiry time. This causes a retraction to be sent, and later the route
1944 * to be flushed once the hold time has passed.
1946 e
->selected_out
->metric
= BABEL_INFINITY
;
1947 e
->selected_out
->expires
= now
+ BABEL_HOLD_TIME
;
1949 babel_trigger_update(p
);
1954 * This is a route originating from someone else that was lost; presumably
1955 * because an export filter was updated to filter it. This means we can't
1956 * set the metric to infinity (it would be overridden on subsequent
1957 * updates from the peer originating the route), so just clear the
1960 * This causes peers to expire the route after a while (like if we just
1961 * shut down), but it's the best we can do in these circumstances; and
1962 * since export filters presumably aren't updated that often this is
1965 e
->selected_out
= NULL
;
1971 babel_rte_better(struct rte
*new, struct rte
*old
)
1973 return new->u
.babel
.metric
< old
->u
.babel
.metric
;
1977 babel_rte_same(struct rte
*new, struct rte
*old
)
1979 return ((new->u
.babel
.router_id
== old
->u
.babel
.router_id
) &&
1980 (new->u
.babel
.metric
== old
->u
.babel
.metric
));
1984 static struct proto
*
1985 babel_init(struct proto_config
*cfg
)
1987 struct proto
*P
= proto_new(cfg
, sizeof(struct babel_proto
));
1989 P
->accept_ra_types
= RA_OPTIMAL
;
1990 P
->if_notify
= babel_if_notify
;
1991 P
->rt_notify
= babel_rt_notify
;
1992 P
->import_control
= babel_import_control
;
1993 P
->make_tmp_attrs
= babel_make_tmp_attrs
;
1994 P
->store_tmp_attrs
= babel_store_tmp_attrs
;
1995 P
->rte_better
= babel_rte_better
;
1996 P
->rte_same
= babel_rte_same
;
2002 babel_start(struct proto
*P
)
2004 struct babel_proto
*p
= (void *) P
;
2005 struct babel_config
*cf
= (void *) P
->cf
;
2007 fib_init(&p
->rtable
, P
->pool
, sizeof(struct babel_entry
), 0, babel_init_entry
);
2008 init_list(&p
->interfaces
);
2009 p
->timer
= tm_new_set(P
->pool
, babel_timer
, p
, 0, 1);
2010 tm_start(p
->timer
, 2);
2011 p
->update_seqno
= 1;
2012 p
->router_id
= proto_get_router_id(&cf
->c
);
2014 p
->route_slab
= sl_new(P
->pool
, sizeof(struct babel_route
));
2015 p
->source_slab
= sl_new(P
->pool
, sizeof(struct babel_source
));
2016 p
->msg_slab
= sl_new(P
->pool
, sizeof(struct babel_msg_node
));
2017 p
->seqno_slab
= sl_new(P
->pool
, sizeof(struct babel_seqno_request
));
2018 init_list(&p
->seqno_cache
);
2020 p
->log_pkt_tbf
= (struct tbf
){ .rate
= 1, .burst
= 5 };
2026 babel_reconfigure(struct proto
*P
, struct proto_config
*c
)
2028 struct babel_proto
*p
= (void *) P
;
2029 struct babel_config
*new = (void *) c
;
2031 TRACE(D_EVENTS
, "Reconfiguring");
2034 babel_reconfigure_ifaces(p
, new);
2036 babel_trigger_update(p
);
2037 babel_kick_timer(p
);
2043 struct protocol proto_babel
= {
2045 .template = "babel%d",
2046 .attr_class
= EAP_BABEL
,
2047 .preference
= DEF_PREF_BABEL
,
2048 .config_size
= sizeof(struct babel_config
),
2051 .start
= babel_start
,
2052 .reconfigure
= babel_reconfigure
,
2053 .get_route_info
= babel_get_route_info
,
2054 .get_attr
= babel_get_attr