2 * BIRD -- The Babel protocol
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.
8 * Can be freely distributed and used under the terms of the GNU GPL.
10 * This file contains the main routines for handling and sending TLVs, as
11 * well as timers and interaction with the nest.
15 * DOC: The Babel protocol
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
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.
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.
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.
41 #define LOG_PKT_AUTH(msg, args...) \
42 log_rl(&p->log_pkt_tbf, L_AUTH "%s: " msg, p->p.name, args)
45 * Is one number greater or equal than another mod 2^16? This is based on the
46 * definition of serial number space in RFC 1982. Note that arguments are of
47 * uint type to avoid integer promotion to signed integer.
49 static inline int ge_mod64k(uint a
, uint b
)
50 { return (u16
)(a
- b
) < 0x8000; }
52 static void babel_expire_requests(struct babel_proto
*p
, struct babel_entry
*e
);
53 static void babel_select_route(struct babel_proto
*p
, struct babel_entry
*e
, struct babel_route
*mod
);
54 static inline void babel_announce_retraction(struct babel_proto
*p
, struct babel_entry
*e
);
55 static void babel_send_route_request(struct babel_proto
*p
, struct babel_entry
*e
, struct babel_neighbor
*n
);
56 static void babel_send_seqno_request(struct babel_proto
*p
, struct babel_entry
*e
, struct babel_seqno_request
*sr
);
57 static void babel_update_cost(struct babel_neighbor
*n
);
58 static inline void babel_kick_timer(struct babel_proto
*p
);
59 static inline void babel_iface_kick_timer(struct babel_iface
*ifa
);
62 * Functions to maintain data structures
66 babel_init_entry(struct fib
*f UNUSED
, void *E
)
68 struct babel_entry
*e
= E
;
70 e
->updated
= current_time();
71 init_list(&e
->requests
);
72 init_list(&e
->sources
);
73 init_list(&e
->routes
);
76 static inline struct babel_entry
*
77 babel_find_entry(struct babel_proto
*p
, const net_addr
*n
)
79 struct fib
*rtable
= (n
->type
== NET_IP4
) ? &p
->ip4_rtable
: &p
->ip6_rtable
;
80 return fib_find(rtable
, n
);
83 static struct babel_entry
*
84 babel_get_entry(struct babel_proto
*p
, const net_addr
*n
)
86 struct fib
*rtable
= (n
->type
== NET_IP4
) ? &p
->ip4_rtable
: &p
->ip6_rtable
;
87 struct babel_entry
*e
= fib_get(rtable
, n
);
91 static struct babel_source
*
92 babel_find_source(struct babel_entry
*e
, u64 router_id
)
94 struct babel_source
*s
;
96 WALK_LIST(s
, e
->sources
)
97 if (s
->router_id
== router_id
)
103 static struct babel_source
*
104 babel_get_source(struct babel_proto
*p
, struct babel_entry
*e
, u64 router_id
)
106 struct babel_source
*s
= babel_find_source(e
, router_id
);
111 s
= sl_allocz(p
->source_slab
);
112 s
->router_id
= router_id
;
113 s
->expires
= current_time() + BABEL_GARBAGE_INTERVAL
;
115 s
->metric
= BABEL_INFINITY
;
116 add_tail(&e
->sources
, NODE s
);
122 babel_expire_sources(struct babel_proto
*p UNUSED
, struct babel_entry
*e
)
124 struct babel_source
*n
, *nx
;
125 btime now_
= current_time();
127 WALK_LIST_DELSAFE(n
, nx
, e
->sources
)
129 if (n
->expires
&& n
->expires
<= now_
)
137 static struct babel_route
*
138 babel_find_route(struct babel_entry
*e
, struct babel_neighbor
*n
)
140 struct babel_route
*r
;
142 WALK_LIST(r
, e
->routes
)
149 static struct babel_route
*
150 babel_get_route(struct babel_proto
*p
, struct babel_entry
*e
, struct babel_neighbor
*nbr
)
152 struct babel_route
*r
= babel_find_route(e
, nbr
);
157 r
= sl_allocz(p
->route_slab
);
161 add_tail(&e
->routes
, NODE r
);
162 add_tail(&nbr
->routes
, NODE
&r
->neigh_route
);
168 babel_retract_route(struct babel_proto
*p
, struct babel_route
*r
)
170 r
->metric
= r
->advert_metric
= BABEL_INFINITY
;
172 if (r
== r
->e
->selected
)
173 babel_select_route(p
, r
->e
, r
);
177 babel_flush_route(struct babel_proto
*p UNUSED
, struct babel_route
*r
)
179 DBG("Babel: Flush route %N router_id %lR neigh %I\n",
180 r
->e
->n
.addr
, r
->router_id
, r
->neigh
->addr
);
183 rem_node(&r
->neigh_route
);
185 if (r
->e
->selected
== r
)
186 r
->e
->selected
= NULL
;
192 babel_expire_route(struct babel_proto
*p
, struct babel_route
*r
)
194 struct babel_config
*cf
= (void *) p
->p
.cf
;
196 TRACE(D_EVENTS
, "Route expiry timer for %N router-id %lR fired",
197 r
->e
->n
.addr
, r
->router_id
);
199 if (r
->metric
< BABEL_INFINITY
)
201 r
->metric
= r
->advert_metric
= BABEL_INFINITY
;
202 r
->expires
= current_time() + cf
->hold_time
;
206 babel_flush_route(p
, r
);
211 babel_refresh_route(struct babel_proto
*p
, struct babel_route
*r
)
213 if (r
== r
->e
->selected
)
214 babel_send_route_request(p
, r
->e
, r
->neigh
);
220 babel_expire_routes_(struct babel_proto
*p
, struct fib
*rtable
)
222 struct babel_config
*cf
= (void *) p
->p
.cf
;
223 struct babel_route
*r
, *rx
;
224 struct fib_iterator fit
;
225 btime now_
= current_time();
227 FIB_ITERATE_INIT(&fit
, rtable
);
230 FIB_ITERATE_START(rtable
, &fit
, struct babel_entry
, e
)
234 WALK_LIST_DELSAFE(r
, rx
, e
->routes
)
236 if (r
->refresh_time
&& r
->refresh_time
<= now_
)
237 babel_refresh_route(p
, r
);
239 if (r
->expires
&& r
->expires
<= now_
)
241 changed
= changed
|| (r
== e
->selected
);
242 babel_expire_route(p
, r
);
249 * We have to restart the iteration because there may be a cascade of
250 * synchronous events babel_select_route() -> nest table change ->
251 * babel_rt_notify() -> rtable change, invalidating hidden variables.
253 FIB_ITERATE_PUT(&fit
);
254 babel_select_route(p
, e
, NULL
);
258 /* Clean up stale entries */
259 if ((e
->valid
== BABEL_ENTRY_STALE
) && ((e
->updated
+ cf
->hold_time
) <= now_
))
260 e
->valid
= BABEL_ENTRY_DUMMY
;
262 /* Clean up unreachable route */
263 if (e
->unreachable
&& (!e
->valid
|| (e
->router_id
== p
->router_id
)))
265 FIB_ITERATE_PUT(&fit
);
266 babel_announce_retraction(p
, e
);
270 babel_expire_sources(p
, e
);
271 babel_expire_requests(p
, e
);
273 /* Remove empty entries */
274 if (!e
->valid
&& EMPTY_LIST(e
->routes
) && EMPTY_LIST(e
->sources
) && EMPTY_LIST(e
->requests
))
276 FIB_ITERATE_PUT(&fit
);
277 fib_delete(rtable
, e
);
285 babel_expire_routes(struct babel_proto
*p
)
287 babel_expire_routes_(p
, &p
->ip4_rtable
);
288 babel_expire_routes_(p
, &p
->ip6_rtable
);
291 static inline int seqno_request_valid(struct babel_seqno_request
*sr
)
292 { return !sr
->nbr
|| sr
->nbr
->ifa
; }
295 * Add seqno request to the table of pending requests (RFC 6216 3.2.6) and send
296 * it to network. Do nothing if it is already in the table.
300 babel_add_seqno_request(struct babel_proto
*p
, struct babel_entry
*e
,
301 u64 router_id
, u16 seqno
, u8 hop_count
,
302 struct babel_neighbor
*nbr
)
304 struct babel_seqno_request
*sr
;
306 WALK_LIST(sr
, e
->requests
)
307 if (sr
->router_id
== router_id
)
309 /* Found matching or newer */
310 if (ge_mod64k(sr
->seqno
, seqno
) && seqno_request_valid(sr
))
315 rem_node(&sr
->nbr_node
);
320 /* No entries found */
321 sr
= sl_allocz(p
->seqno_slab
);
324 sr
->router_id
= router_id
;
326 sr
->hop_count
= hop_count
;
328 sr
->expires
= current_time() + BABEL_SEQNO_REQUEST_EXPIRY
;
331 add_tail(&nbr
->requests
, &sr
->nbr_node
);
333 add_tail(&e
->requests
, NODE sr
);
335 babel_send_seqno_request(p
, e
, sr
);
339 babel_remove_seqno_request(struct babel_proto
*p UNUSED
, struct babel_seqno_request
*sr
)
342 rem_node(&sr
->nbr_node
);
349 babel_satisfy_seqno_request(struct babel_proto
*p
, struct babel_entry
*e
,
350 u64 router_id
, u16 seqno
)
352 struct babel_seqno_request
*sr
;
354 WALK_LIST(sr
, e
->requests
)
355 if ((sr
->router_id
== router_id
) && ge_mod64k(seqno
, sr
->seqno
))
357 /* Found the request, remove it */
358 babel_remove_seqno_request(p
, sr
);
366 babel_expire_requests(struct babel_proto
*p
, struct babel_entry
*e
)
368 struct babel_seqno_request
*sr
, *srx
;
369 btime now_
= current_time();
371 WALK_LIST_DELSAFE(sr
, srx
, e
->requests
)
373 /* Remove seqno requests sent to dead neighbors */
374 if (!seqno_request_valid(sr
))
376 babel_remove_seqno_request(p
, sr
);
380 /* Handle expired requests - resend or remove */
381 if (sr
->expires
&& sr
->expires
<= now_
)
383 if (sr
->count
< BABEL_SEQNO_REQUEST_RETRY
)
386 sr
->expires
+= (BABEL_SEQNO_REQUEST_EXPIRY
<< sr
->count
);
387 babel_send_seqno_request(p
, e
, sr
);
391 TRACE(D_EVENTS
, "Seqno request for %N router-id %lR expired",
392 e
->n
.addr
, sr
->router_id
);
394 babel_remove_seqno_request(p
, sr
);
401 static struct babel_neighbor
*
402 babel_find_neighbor(struct babel_iface
*ifa
, ip_addr addr
)
404 struct babel_neighbor
*nbr
;
406 WALK_LIST(nbr
, ifa
->neigh_list
)
407 if (ipa_equal(nbr
->addr
, addr
))
413 static struct babel_neighbor
*
414 babel_get_neighbor(struct babel_iface
*ifa
, ip_addr addr
)
416 struct babel_proto
*p
= ifa
->proto
;
417 struct babel_neighbor
*nbr
= babel_find_neighbor(ifa
, addr
);
422 TRACE(D_EVENTS
, "New neighbor %I on %s", addr
, ifa
->iface
->name
);
424 nbr
= mb_allocz(ifa
->pool
, sizeof(struct babel_neighbor
));
427 nbr
->rxcost
= BABEL_INFINITY
;
428 nbr
->txcost
= BABEL_INFINITY
;
429 nbr
->cost
= BABEL_INFINITY
;
430 nbr
->init_expiry
= current_time() + BABEL_INITIAL_NEIGHBOR_TIMEOUT
;
431 init_list(&nbr
->routes
);
432 init_list(&nbr
->requests
);
433 add_tail(&ifa
->neigh_list
, NODE nbr
);
439 babel_flush_neighbor(struct babel_proto
*p
, struct babel_neighbor
*nbr
)
441 struct babel_route
*r
;
444 TRACE(D_EVENTS
, "Removing neighbor %I on %s", nbr
->addr
, nbr
->ifa
->iface
->name
);
446 WALK_LIST_FIRST(n
, nbr
->routes
)
448 r
= SKIP_BACK(struct babel_route
, neigh_route
, n
);
449 babel_retract_route(p
, r
);
450 babel_flush_route(p
, r
);
453 struct babel_seqno_request
*sr
;
454 WALK_LIST_FIRST2(sr
, nbr_node
, nbr
->requests
)
457 rem_node(&sr
->nbr_node
);
466 babel_expire_ihu(struct babel_proto
*p
, struct babel_neighbor
*nbr
)
468 TRACE(D_EVENTS
, "IHU from nbr %I on %s expired", nbr
->addr
, nbr
->ifa
->iface
->name
);
470 nbr
->txcost
= BABEL_INFINITY
;
472 babel_update_cost(nbr
);
476 babel_expire_hello(struct babel_proto
*p
, struct babel_neighbor
*nbr
, btime now_
)
479 nbr
->hello_map
<<= 1;
481 if (nbr
->hello_cnt
< 16)
484 nbr
->hello_expiry
+= nbr
->last_hello_int
;
486 /* We may expire multiple hellos if last_hello_int is too short */
487 if (nbr
->hello_map
&& nbr
->hello_expiry
<= now_
)
490 TRACE(D_EVENTS
, "Hello from nbr %I on %s expired, %d left",
491 nbr
->addr
, nbr
->ifa
->iface
->name
, u32_popcount(nbr
->hello_map
));
494 babel_update_cost(nbr
);
496 babel_flush_neighbor(p
, nbr
);
500 babel_expire_neighbors(struct babel_proto
*p
)
502 struct babel_iface
*ifa
;
503 struct babel_neighbor
*nbr
, *nbx
;
504 btime now_
= current_time();
506 WALK_LIST(ifa
, p
->interfaces
)
508 WALK_LIST_DELSAFE(nbr
, nbx
, ifa
->neigh_list
)
510 if (nbr
->ihu_expiry
&& nbr
->ihu_expiry
<= now_
)
511 babel_expire_ihu(p
, nbr
);
513 if (nbr
->init_expiry
&& nbr
->init_expiry
<= now_
)
514 { babel_flush_neighbor(p
, nbr
); continue; }
516 if (nbr
->hello_expiry
&& nbr
->hello_expiry
<= now_
)
517 { babel_expire_hello(p
, nbr
, now_
); continue; }
523 * Best route selection
527 * From the RFC (section 3.5.1):
529 * a route advertisement carrying the quintuple (prefix, plen, router-id, seqno,
530 * metric) is feasible if one of the following conditions holds:
532 * - metric is infinite; or
534 * - no entry exists in the source table indexed by (id, prefix, plen); or
536 * - an entry (prefix, plen, router-id, seqno', metric') exists in the source
538 * - seqno' < seqno or
539 * - seqno = seqno' and metric < metric'.
542 babel_is_feasible(struct babel_source
*s
, u16 seqno
, u16 metric
)
545 (metric
== BABEL_INFINITY
) ||
546 (seqno
> s
->seqno
) ||
547 ((seqno
== s
->seqno
) && (metric
< s
->metric
));
550 /* Simple additive metric - Appendix 3.1 in the RFC */
552 babel_compute_metric(struct babel_neighbor
*n
, uint metric
)
554 return MIN(metric
+ n
->cost
, BABEL_INFINITY
);
558 babel_update_cost(struct babel_neighbor
*nbr
)
560 struct babel_proto
*p
= nbr
->ifa
->proto
;
561 struct babel_iface_config
*cf
= nbr
->ifa
->cf
;
562 uint rcv
= u32_popcount(nbr
->hello_map
); // number of bits set
563 uint max
= nbr
->hello_cnt
;
564 uint rxcost
= BABEL_INFINITY
; /* Cost to announce in IHU */
565 uint txcost
= BABEL_INFINITY
; /* Effective cost for route selection */
567 if (!rcv
|| !nbr
->ifa
->up
)
572 case BABEL_IFACE_TYPE_WIRED
:
573 /* k-out-of-j selection - Appendix 2.1 in the RFC. */
575 /* Link is bad if less than cf->limit/16 of expected hellos were received */
576 if (rcv
* 16 < cf
->limit
* max
)
580 txcost
= nbr
->txcost
;
583 case BABEL_IFACE_TYPE_WIRELESS
:
585 * ETX - Appendix 2.2 in the RFC.
587 * alpha = prob. of successful transmission estimated by the neighbor
588 * beta = prob. of successful transmission estimated by the router
589 * rxcost = nominal rxcost of the router / beta
590 * txcost = nominal rxcost of the neighbor / (alpha * beta)
591 * = received txcost / beta
593 * Note that received txcost is just neighbor's rxcost. Beta is rcv/max,
594 * we use inverse values of beta (i.e. max/rcv) to stay in integers.
596 rxcost
= MIN( cf
->rxcost
* max
/ rcv
, BABEL_INFINITY
);
597 txcost
= MIN(nbr
->txcost
* max
/ rcv
, BABEL_INFINITY
);
602 /* If RX cost changed, send IHU with next Hello */
603 if (rxcost
!= nbr
->rxcost
)
605 nbr
->rxcost
= rxcost
;
609 /* If link cost changed, run route selection */
610 if (txcost
!= nbr
->cost
)
612 TRACE(D_EVENTS
, "Cost of nbr %I on %s changed from %u to %u",
613 nbr
->addr
, nbr
->ifa
->iface
->name
, nbr
->cost
, txcost
);
617 struct babel_route
*r
; node
*n
;
618 WALK_LIST2(r
, n
, nbr
->routes
, neigh_route
)
620 r
->metric
= babel_compute_metric(nbr
, r
->advert_metric
);
621 babel_select_route(p
, r
->e
, r
);
627 * babel_announce_rte - announce selected route to the core
628 * @p: Babel protocol instance
629 * @e: Babel route entry to announce
631 * This function announces a Babel entry to the core if it has a selected
632 * incoming path, and retracts it otherwise. If there is no selected route but
633 * the entry is valid and ours, the unreachable route is announced instead.
636 babel_announce_rte(struct babel_proto
*p
, struct babel_entry
*e
)
638 struct babel_route
*r
= e
->selected
;
639 struct channel
*c
= (e
->n
.addr
->type
== NET_IP4
) ? p
->ip4_channel
: p
->ip6_channel
;
645 .scope
= SCOPE_UNIVERSE
,
647 .pref
= c
->preference
,
648 .from
= r
->neigh
->addr
,
649 .nh
.gw
= r
->next_hop
,
650 .nh
.iface
= r
->neigh
->ifa
->iface
,
651 .eattrs
= alloca(sizeof(ea_list
) + 3*sizeof(eattr
)),
654 *a0
.eattrs
= (ea_list
) { .count
= 3 };
655 a0
.eattrs
->attrs
[0] = (eattr
) {
656 .id
= EA_BABEL_METRIC
,
657 .type
= EAF_TYPE_INT
,
661 struct adata
*ad
= alloca(sizeof(struct adata
) + sizeof(u64
));
662 ad
->length
= sizeof(u64
);
663 memcpy(ad
->data
, &(r
->router_id
), sizeof(u64
));
664 a0
.eattrs
->attrs
[1] = (eattr
) {
665 .id
= EA_BABEL_ROUTER_ID
,
666 .type
= EAF_TYPE_OPAQUE
,
670 a0
.eattrs
->attrs
[2] = (eattr
) {
671 .id
= EA_BABEL_SEQNO
,
672 .type
= EAF_TYPE_INT
,
677 * If we cannot find a reachable neighbour, set the entry to be onlink. This
678 * makes it possible to, e.g., assign /32 addresses on a mesh interface and
681 if (!neigh_find(&p
->p
, r
->next_hop
, r
->neigh
->ifa
->iface
, 0))
682 a0
.nh
.flags
= RNF_ONLINK
;
684 rta
*a
= rta_lookup(&a0
);
685 rte
*rte
= rte_get_temp(a
, p
->p
.main_source
);
688 rte_update2(c
, e
->n
.addr
, rte
, p
->p
.main_source
);
690 else if (e
->valid
&& (e
->router_id
!= p
->router_id
))
695 .scope
= SCOPE_UNIVERSE
,
696 .dest
= RTD_UNREACHABLE
,
700 rta
*a
= rta_lookup(&a0
);
701 rte
*rte
= rte_get_temp(a
, p
->p
.main_source
);
705 rte_update2(c
, e
->n
.addr
, rte
, p
->p
.main_source
);
711 rte_update2(c
, e
->n
.addr
, NULL
, p
->p
.main_source
);
715 /* Special case of babel_announce_rte() just for retraction */
717 babel_announce_retraction(struct babel_proto
*p
, struct babel_entry
*e
)
719 struct channel
*c
= (e
->n
.addr
->type
== NET_IP4
) ? p
->ip4_channel
: p
->ip6_channel
;
721 rte_update2(c
, e
->n
.addr
, NULL
, p
->p
.main_source
);
726 * babel_select_route - select best route for given route entry
727 * @p: Babel protocol instance
728 * @e: Babel entry to select the best route for
729 * @mod: Babel route that was modified or NULL if unspecified
731 * Select the best reachable and feasible route for a given prefix among the
732 * routes received from peers, and propagate it to the nest. This just selects
733 * the reachable and feasible route with the lowest metric, but keeps selected
734 * the old one in case of tie.
736 * If no feasible route is available for a prefix that previously had a route
737 * selected, a seqno request is sent to try to get a valid route. If the entry
738 * is valid and not owned by us, the unreachable route is announced to the nest
739 * (to blackhole packets going to it, as per section 2.8). It is later removed
740 * by babel_expire_routes(). Otherwise, the route is just removed from the nest.
742 * Argument @mod is used to optimize best route calculation. When specified, the
743 * function can assume that only the @mod route was modified to avoid full best
744 * route selection and announcement when non-best route was modified in minor
745 * way. The caller is advised to not call babel_select_route() when no change is
746 * done (e.g. periodic route updates) to avoid unnecessary announcements of the
747 * same best route. The caller is not required to call the function in case of a
748 * retraction of a non-best route.
750 * Note that the function does not active triggered updates. That is done by
751 * babel_rt_notify() when the change is propagated back to Babel.
754 babel_select_route(struct babel_proto
*p
, struct babel_entry
*e
, struct babel_route
*mod
)
756 struct babel_route
*r
, *best
= e
->selected
;
758 /* Shortcut if only non-best was modified */
759 if (mod
&& (mod
!= best
))
761 /* Either select modified route, or keep old best route */
762 if ((mod
->metric
< (best
? best
->metric
: BABEL_INFINITY
)) && mod
->feasible
)
769 /* Selected route may be modified and no longer admissible */
770 if (!best
|| (best
->metric
== BABEL_INFINITY
) || !best
->feasible
)
773 /* Find the best feasible route from all routes */
774 WALK_LIST(r
, e
->routes
)
775 if ((r
->metric
< (best
? best
->metric
: BABEL_INFINITY
)) && r
->feasible
)
781 if (best
!= e
->selected
)
782 TRACE(D_EVENTS
, "Picked new route for prefix %N: router-id %lR metric %d",
783 e
->n
.addr
, best
->router_id
, best
->metric
);
785 else if (e
->selected
)
788 * We have lost all feasible routes. We have to broadcast seqno request
789 * (Section 3.8.2.1) and keep unreachable route for a while (section 2.8).
790 * The later is done automatically by babel_announce_rte().
793 TRACE(D_EVENTS
, "Lost feasible route for prefix %N", e
->n
.addr
);
794 if (e
->valid
&& (e
->selected
->router_id
== e
->router_id
))
795 babel_add_seqno_request(p
, e
, e
->selected
->router_id
, e
->selected
->seqno
+ 1, 0, NULL
);
801 babel_announce_rte(p
, e
);
805 * Functions to send replies
809 babel_send_ack(struct babel_iface
*ifa
, ip_addr dest
, u16 nonce
)
811 struct babel_proto
*p
= ifa
->proto
;
812 union babel_msg msg
= {};
814 TRACE(D_PACKETS
, "Sending ACK to %I with nonce %d", dest
, nonce
);
816 msg
.type
= BABEL_TLV_ACK
;
817 msg
.ack
.nonce
= nonce
;
819 babel_send_unicast(&msg
, ifa
, dest
);
823 babel_build_ihu(union babel_msg
*msg
, struct babel_iface
*ifa
, struct babel_neighbor
*n
)
825 struct babel_proto
*p
= ifa
->proto
;
827 msg
->type
= BABEL_TLV_IHU
;
828 msg
->ihu
.addr
= n
->addr
;
829 msg
->ihu
.rxcost
= n
->rxcost
;
830 msg
->ihu
.interval
= ifa
->cf
->ihu_interval
;
832 TRACE(D_PACKETS
, "Sending IHU for %I with rxcost %d interval %t",
833 msg
->ihu
.addr
, msg
->ihu
.rxcost
, (btime
) msg
->ihu
.interval
);
837 babel_send_ihu(struct babel_iface
*ifa
, struct babel_neighbor
*n
)
839 union babel_msg msg
= {};
840 babel_build_ihu(&msg
, ifa
, n
);
841 babel_send_unicast(&msg
, ifa
, n
->addr
);
842 n
->ihu_cnt
= BABEL_IHU_INTERVAL_FACTOR
;
846 babel_send_ihus(struct babel_iface
*ifa
)
848 struct babel_neighbor
*n
;
849 WALK_LIST(n
, ifa
->neigh_list
)
851 if (n
->hello_cnt
&& (--n
->ihu_cnt
<= 0))
853 union babel_msg msg
= {};
854 babel_build_ihu(&msg
, ifa
, n
);
855 babel_enqueue(&msg
, ifa
);
856 n
->ihu_cnt
= BABEL_IHU_INTERVAL_FACTOR
;
862 babel_send_hello(struct babel_iface
*ifa
)
864 struct babel_proto
*p
= ifa
->proto
;
865 union babel_msg msg
= {};
867 msg
.type
= BABEL_TLV_HELLO
;
868 msg
.hello
.seqno
= ifa
->hello_seqno
++;
869 msg
.hello
.interval
= ifa
->cf
->hello_interval
;
871 TRACE(D_PACKETS
, "Sending hello on %s with seqno %d interval %t",
872 ifa
->ifname
, msg
.hello
.seqno
, (btime
) msg
.hello
.interval
);
874 babel_enqueue(&msg
, ifa
);
876 babel_send_ihus(ifa
);
880 babel_send_route_request(struct babel_proto
*p
, struct babel_entry
*e
, struct babel_neighbor
*n
)
882 union babel_msg msg
= {};
884 TRACE(D_PACKETS
, "Sending route request for %N to %I", e
->n
.addr
, n
->addr
);
886 msg
.type
= BABEL_TLV_ROUTE_REQUEST
;
887 net_copy(&msg
.route_request
.net
, e
->n
.addr
);
889 babel_send_unicast(&msg
, n
->ifa
, n
->addr
);
893 babel_send_wildcard_request(struct babel_iface
*ifa
)
895 struct babel_proto
*p
= ifa
->proto
;
896 union babel_msg msg
= {};
898 TRACE(D_PACKETS
, "Sending wildcard route request on %s", ifa
->ifname
);
900 msg
.type
= BABEL_TLV_ROUTE_REQUEST
;
901 msg
.route_request
.full
= 1;
903 babel_enqueue(&msg
, ifa
);
907 babel_send_seqno_request(struct babel_proto
*p
, struct babel_entry
*e
, struct babel_seqno_request
*sr
)
909 union babel_msg msg
= {};
911 msg
.type
= BABEL_TLV_SEQNO_REQUEST
;
912 msg
.seqno_request
.hop_count
= sr
->hop_count
?: BABEL_INITIAL_HOP_COUNT
;
913 msg
.seqno_request
.seqno
= sr
->seqno
;
914 msg
.seqno_request
.router_id
= sr
->router_id
;
915 net_copy(&msg
.seqno_request
.net
, e
->n
.addr
);
919 TRACE(D_PACKETS
, "Sending seqno request for %N router-id %lR seqno %d to %I on %s",
920 e
->n
.addr
, sr
->router_id
, sr
->seqno
, sr
->nbr
->addr
, sr
->nbr
->ifa
->ifname
);
922 babel_send_unicast(&msg
, sr
->nbr
->ifa
, sr
->nbr
->addr
);
926 TRACE(D_PACKETS
, "Sending broadcast seqno request for %N router-id %lR seqno %d",
927 e
->n
.addr
, sr
->router_id
, sr
->seqno
);
929 struct babel_iface
*ifa
;
930 WALK_LIST(ifa
, p
->interfaces
)
931 babel_enqueue(&msg
, ifa
);
936 * babel_send_update - send route table updates
937 * @ifa: Interface to transmit on
938 * @changed: Only send entries changed since this time
940 * This function produces update TLVs for all entries changed since the time
941 * indicated by the &changed parameter and queues them for transmission on the
942 * selected interface. During the process, the feasibility distance for each
943 * transmitted entry is updated.
946 babel_send_update_(struct babel_iface
*ifa
, btime changed
, struct fib
*rtable
)
948 struct babel_proto
*p
= ifa
->proto
;
950 /* Update increase was requested */
951 if (p
->update_seqno_inc
)
954 p
->update_seqno_inc
= 0;
957 FIB_WALK(rtable
, struct babel_entry
, e
)
962 /* Our own seqno might have changed, in which case we update the routes we
964 if ((e
->router_id
== p
->router_id
) && (e
->seqno
< p
->update_seqno
))
966 e
->seqno
= p
->update_seqno
;
967 e
->updated
= current_time();
970 /* Skip routes that weren't updated since 'changed' time */
971 if (e
->updated
< changed
)
974 TRACE(D_PACKETS
, "Sending update for %N router-id %lR seqno %d metric %d",
975 e
->n
.addr
, e
->router_id
, e
->seqno
, e
->metric
);
977 union babel_msg msg
= {};
978 msg
.type
= BABEL_TLV_UPDATE
;
979 msg
.update
.interval
= ifa
->cf
->update_interval
;
980 msg
.update
.seqno
= e
->seqno
;
981 msg
.update
.metric
= e
->metric
;
982 msg
.update
.router_id
= e
->router_id
;
983 net_copy(&msg
.update
.net
, e
->n
.addr
);
985 msg
.update
.next_hop
= ((e
->n
.addr
->type
== NET_IP4
) ?
986 ifa
->next_hop_ip4
: ifa
->next_hop_ip6
);
988 /* Do not send route if next hop is unknown, e.g. no configured IPv4 address */
989 if (ipa_zero(msg
.update
.next_hop
))
992 babel_enqueue(&msg
, ifa
);
994 /* Update feasibility distance for redistributed routes */
995 if (e
->router_id
!= p
->router_id
)
997 struct babel_source
*s
= babel_get_source(p
, e
, e
->router_id
);
998 s
->expires
= current_time() + BABEL_GARBAGE_INTERVAL
;
1000 if ((msg
.update
.seqno
> s
->seqno
) ||
1001 ((msg
.update
.seqno
== s
->seqno
) && (msg
.update
.metric
< s
->metric
)))
1003 s
->seqno
= msg
.update
.seqno
;
1004 s
->metric
= msg
.update
.metric
;
1012 babel_send_update(struct babel_iface
*ifa
, btime changed
)
1014 struct babel_proto
*p
= ifa
->proto
;
1016 babel_send_update_(ifa
, changed
, &p
->ip4_rtable
);
1017 babel_send_update_(ifa
, changed
, &p
->ip6_rtable
);
1021 babel_trigger_iface_update(struct babel_iface
*ifa
)
1023 struct babel_proto
*p
= ifa
->proto
;
1025 /* Interface not active or already scheduled */
1026 if (!ifa
->up
|| ifa
->want_triggered
)
1029 TRACE(D_EVENTS
, "Scheduling triggered updates for %s seqno %d",
1030 ifa
->iface
->name
, p
->update_seqno
);
1032 ifa
->want_triggered
= current_time();
1033 babel_iface_kick_timer(ifa
);
1036 /* Sends and update on all interfaces. */
1038 babel_trigger_update(struct babel_proto
*p
)
1043 struct babel_iface
*ifa
;
1044 WALK_LIST(ifa
, p
->interfaces
)
1045 babel_trigger_iface_update(ifa
);
1050 /* A retraction is an update with an infinite metric */
1052 babel_send_retraction(struct babel_iface
*ifa
, net_addr
*n
)
1054 struct babel_proto
*p
= ifa
->proto
;
1055 union babel_msg msg
= {};
1057 TRACE(D_PACKETS
, "Sending retraction for %N seqno %d", n
, p
->update_seqno
);
1059 msg
.type
= BABEL_TLV_UPDATE
;
1060 msg
.update
.interval
= ifa
->cf
->update_interval
;
1061 msg
.update
.seqno
= p
->update_seqno
;
1062 msg
.update
.metric
= BABEL_INFINITY
;
1063 msg
.update
.net
= *n
;
1065 babel_enqueue(&msg
, ifa
);
1069 babel_send_wildcard_retraction(struct babel_iface
*ifa
)
1071 struct babel_proto
*p
= ifa
->proto
;
1072 union babel_msg msg
= {};
1074 TRACE(D_PACKETS
, "Sending wildcard retraction on %s", ifa
->ifname
);
1076 msg
.type
= BABEL_TLV_UPDATE
;
1077 msg
.update
.wildcard
= 1;
1078 msg
.update
.interval
= ifa
->cf
->update_interval
;
1079 msg
.update
.seqno
= p
->update_seqno
;
1080 msg
.update
.metric
= BABEL_INFINITY
;
1082 babel_enqueue(&msg
, ifa
);
1087 * TLV handler helpers
1090 /* Update hello history according to Appendix A1 of the RFC */
1092 babel_update_hello_history(struct babel_neighbor
*n
, u16 seqno
, uint interval
)
1095 * Compute the difference between expected and received seqno (modulo 2^16).
1096 * If the expected and received seqnos are within 16 of each other, the modular
1097 * difference is going to be less than 16 for one of the directions. Otherwise,
1098 * the values differ too much, so just reset the state.
1101 u16 delta
= ((uint
) seqno
- (uint
) n
->next_hello_seqno
);
1103 if ((delta
== 0) || (n
->hello_cnt
== 0))
1107 else if (delta
<= 16)
1109 /* Sending node decreased interval; fast-forward */
1110 n
->hello_map
<<= delta
;
1111 n
->hello_cnt
= MIN(n
->hello_cnt
+ delta
, 16);
1113 else if (delta
>= 0xfff0)
1115 u8 diff
= (0xffff - delta
);
1116 /* Sending node increased interval; undo history */
1117 n
->hello_map
>>= diff
;
1118 n
->hello_cnt
= (diff
< n
->hello_cnt
) ? n
->hello_cnt
- diff
: 0;
1122 /* Note state reset - flush entries */
1123 n
->hello_map
= n
->hello_cnt
= 0;
1127 n
->hello_map
= (n
->hello_map
<< 1) | 1;
1128 n
->next_hello_seqno
= seqno
+1;
1129 if (n
->hello_cnt
< 16) n
->hello_cnt
++;
1131 /* Update expiration */
1132 n
->hello_expiry
= current_time() + BABEL_HELLO_EXPIRY_FACTOR(interval
);
1133 n
->last_hello_int
= interval
;
1135 /* Disable initial timeout */
1145 babel_handle_ack_req(union babel_msg
*m
, struct babel_iface
*ifa
)
1147 struct babel_proto
*p
= ifa
->proto
;
1148 struct babel_msg_ack_req
*msg
= &m
->ack_req
;
1150 TRACE(D_PACKETS
, "Handling ACK request nonce %d interval %t",
1151 msg
->nonce
, (btime
) msg
->interval
);
1153 babel_send_ack(ifa
, msg
->sender
, msg
->nonce
);
1157 babel_handle_hello(union babel_msg
*m
, struct babel_iface
*ifa
)
1159 struct babel_proto
*p
= ifa
->proto
;
1160 struct babel_msg_hello
*msg
= &m
->hello
;
1162 TRACE(D_PACKETS
, "Handling hello seqno %d interval %t",
1163 msg
->seqno
, (btime
) msg
->interval
);
1165 struct babel_neighbor
*n
= babel_get_neighbor(ifa
, msg
->sender
);
1166 int first_hello
= !n
->hello_cnt
;
1168 babel_update_hello_history(n
, msg
->seqno
, msg
->interval
);
1169 babel_update_cost(n
);
1171 /* Speed up session establishment by sending IHU immediately */
1173 babel_send_ihu(ifa
, n
);
1177 babel_handle_ihu(union babel_msg
*m
, struct babel_iface
*ifa
)
1179 struct babel_proto
*p
= ifa
->proto
;
1180 struct babel_msg_ihu
*msg
= &m
->ihu
;
1182 /* Ignore IHUs that are not about us */
1183 if ((msg
->ae
!= BABEL_AE_WILDCARD
) && !ipa_equal(msg
->addr
, ifa
->addr
))
1186 TRACE(D_PACKETS
, "Handling IHU rxcost %d interval %t",
1187 msg
->rxcost
, (btime
) msg
->interval
);
1189 struct babel_neighbor
*n
= babel_get_neighbor(ifa
, msg
->sender
);
1190 n
->txcost
= msg
->rxcost
;
1191 n
->ihu_expiry
= current_time() + BABEL_IHU_EXPIRY_FACTOR(msg
->interval
);
1192 babel_update_cost(n
);
1196 * babel_handle_update - handle incoming route updates
1197 * @m: Incoming update TLV
1198 * @ifa: Interface the update was received on
1200 * This function is called as a handler for update TLVs and handles the updating
1201 * and maintenance of route entries in Babel's internal routing cache. The
1202 * handling follows the actions described in the Babel RFC, and at the end of
1203 * each update handling, babel_select_route() is called on the affected entry to
1204 * optionally update the selected routes and propagate them to the core.
1207 babel_handle_update(union babel_msg
*m
, struct babel_iface
*ifa
)
1209 struct babel_proto
*p
= ifa
->proto
;
1210 struct babel_msg_update
*msg
= &m
->update
;
1212 struct babel_neighbor
*nbr
;
1213 struct babel_entry
*e
;
1214 struct babel_source
*s
;
1215 struct babel_route
*r
, *best
;
1217 int feasible
, metric
;
1220 TRACE(D_PACKETS
, "Handling wildcard retraction", msg
->seqno
);
1222 TRACE(D_PACKETS
, "Handling update for %N with seqno %d metric %d",
1223 &msg
->net
, msg
->seqno
, msg
->metric
);
1225 nbr
= babel_find_neighbor(ifa
, msg
->sender
);
1228 DBG("Babel: Haven't heard from neighbor %I; ignoring update.\n", msg
->sender
);
1232 if (msg
->router_id
== p
->router_id
)
1234 DBG("Babel: Ignoring update for our own router ID.\n");
1238 struct channel
*c
= (msg
->net
.type
== NET_IP4
) ? p
->ip4_channel
: p
->ip6_channel
;
1239 if (!c
|| (c
->channel_state
!= CS_UP
))
1241 DBG("Babel: Ignoring update for inactive address family.\n");
1246 if (msg
->metric
== BABEL_INFINITY
)
1251 * Special case: This is a retraction of all prefixes announced by this
1252 * neighbour (see second-to-last paragraph of section 4.4.9 in the RFC).
1254 WALK_LIST(n
, nbr
->routes
)
1256 r
= SKIP_BACK(struct babel_route
, neigh_route
, n
);
1257 babel_retract_route(p
, r
);
1262 e
= babel_find_entry(p
, &msg
->net
);
1267 /* The route entry indexed by neighbour */
1268 r
= babel_find_route(e
, nbr
);
1273 /* Router-id, next-hop and seqno are ignored for retractions */
1274 babel_retract_route(p
, r
);
1277 /* Done with retractions */
1281 /* Regular update */
1282 e
= babel_get_entry(p
, &msg
->net
);
1283 r
= babel_get_route(p
, e
, nbr
); /* the route entry indexed by neighbour */
1284 s
= babel_find_source(e
, msg
->router_id
); /* for feasibility */
1285 feasible
= babel_is_feasible(s
, msg
->seqno
, msg
->metric
);
1286 metric
= babel_compute_metric(nbr
, msg
->metric
);
1289 /* RFC section 3.8.2.2 - Dealing with unfeasible updates */
1290 if (!feasible
&& (metric
!= BABEL_INFINITY
) &&
1291 (!best
|| (r
== best
) || (metric
< best
->metric
)))
1292 babel_add_seqno_request(p
, e
, s
->router_id
, s
->seqno
+ 1, 0, nbr
);
1294 /* Special case - ignore unfeasible update to best route */
1295 if (r
== best
&& !feasible
&& (msg
->router_id
== r
->router_id
))
1298 r
->expires
= current_time() + BABEL_ROUTE_EXPIRY_FACTOR(msg
->interval
);
1299 r
->refresh_time
= current_time() + BABEL_ROUTE_REFRESH_FACTOR(msg
->interval
);
1301 /* No further processing if there is no change */
1302 if ((r
->feasible
== feasible
) && (r
->seqno
== msg
->seqno
) &&
1303 (r
->metric
== metric
) && (r
->advert_metric
== msg
->metric
) &&
1304 (r
->router_id
== msg
->router_id
) && ipa_equal(r
->next_hop
, msg
->next_hop
))
1307 /* Last paragraph above - update the entry */
1308 r
->feasible
= feasible
;
1309 r
->seqno
= msg
->seqno
;
1311 r
->advert_metric
= msg
->metric
;
1312 r
->router_id
= msg
->router_id
;
1313 r
->next_hop
= msg
->next_hop
;
1315 /* If received update satisfies seqno request, we send triggered updates */
1316 if (babel_satisfy_seqno_request(p
, e
, msg
->router_id
, msg
->seqno
))
1318 babel_trigger_update(p
);
1319 e
->updated
= current_time();
1322 babel_select_route(p
, e
, r
);
1326 babel_handle_route_request(union babel_msg
*m
, struct babel_iface
*ifa
)
1328 struct babel_proto
*p
= ifa
->proto
;
1329 struct babel_msg_route_request
*msg
= &m
->route_request
;
1331 /* RFC 6126 3.8.1.1 */
1333 /* Wildcard request - full update on the interface */
1336 TRACE(D_PACKETS
, "Handling wildcard route request");
1337 ifa
->want_triggered
= 1;
1341 TRACE(D_PACKETS
, "Handling route request for %N", &msg
->net
);
1343 /* Non-wildcard request - see if we have an entry for the route.
1344 If not, send a retraction, otherwise send an update. */
1345 struct babel_entry
*e
= babel_find_entry(p
, &msg
->net
);
1348 babel_send_retraction(ifa
, &msg
->net
);
1352 babel_trigger_iface_update(ifa
);
1353 e
->updated
= current_time();
1358 babel_handle_seqno_request(union babel_msg
*m
, struct babel_iface
*ifa
)
1360 struct babel_proto
*p
= ifa
->proto
;
1361 struct babel_msg_seqno_request
*msg
= &m
->seqno_request
;
1363 /* RFC 6126 3.8.1.2 */
1365 TRACE(D_PACKETS
, "Handling seqno request for %N router-id %lR seqno %d hop count %d",
1366 &msg
->net
, msg
->router_id
, msg
->seqno
, msg
->hop_count
);
1368 /* Ignore if we have no such entry or entry has infinite metric */
1369 struct babel_entry
*e
= babel_find_entry(p
, &msg
->net
);
1370 if (!e
|| !e
->valid
|| (e
->metric
== BABEL_INFINITY
))
1373 /* Trigger update on incoming interface if we have a selected route with
1374 different router id or seqno no smaller than requested */
1375 if ((e
->router_id
!= msg
->router_id
) || ge_mod64k(e
->seqno
, msg
->seqno
))
1377 babel_trigger_iface_update(ifa
);
1378 e
->updated
= current_time();
1382 /* Seqno is larger; check if we own the router id */
1383 if (msg
->router_id
== p
->router_id
)
1385 /* Ours; seqno increase and trigger global update */
1386 p
->update_seqno_inc
= 1;
1387 babel_trigger_update(p
);
1389 else if (msg
->hop_count
> 1)
1391 /* Not ours; forward if TTL allows it */
1393 /* Find best admissible route */
1394 struct babel_route
*r
, *best1
= NULL
, *best2
= NULL
;
1395 WALK_LIST(r
, e
->routes
)
1396 if ((r
->router_id
== msg
->router_id
) && !ipa_equal(r
->neigh
->addr
, msg
->sender
))
1398 /* Find best feasible route */
1399 if ((!best1
|| r
->metric
< best1
->metric
) && r
->feasible
)
1402 /* Find best not necessary feasible route */
1403 if (!best2
|| r
->metric
< best2
->metric
)
1407 /* If no route is found, do nothing */
1412 babel_add_seqno_request(p
, e
, msg
->router_id
, msg
->seqno
, msg
->hop_count
-1, r
->neigh
);
1417 * Authentication functions
1421 * babel_auth_reset_index - Reset authentication index on interface
1422 * @ifa: Interface to reset
1424 * This function resets the authentication index and packet counter for an
1425 * interface, and should be called on interface configuration, or when the
1426 * packet counter overflows.
1429 babel_auth_reset_index(struct babel_iface
*ifa
)
1431 random_bytes(ifa
->auth_index
, BABEL_AUTH_INDEX_LEN
);
1436 babel_auth_send_challenge_request(struct babel_iface
*ifa
, struct babel_neighbor
*n
)
1438 struct babel_proto
*p
= ifa
->proto
;
1439 union babel_msg msg
= {};
1441 TRACE(D_PACKETS
, "Sending challenge request to %I on %s",
1442 n
->addr
, ifa
->ifname
);
1444 random_bytes(n
->auth_nonce
, BABEL_AUTH_NONCE_LEN
);
1445 n
->auth_nonce_expiry
= current_time() + BABEL_AUTH_CHALLENGE_TIMEOUT
;
1446 n
->auth_next_challenge
= current_time() + BABEL_AUTH_CHALLENGE_INTERVAL
;
1448 msg
.type
= BABEL_TLV_CHALLENGE_REQUEST
;
1449 msg
.challenge
.nonce_len
= BABEL_AUTH_NONCE_LEN
;
1450 msg
.challenge
.nonce
= n
->auth_nonce
;
1452 babel_send_unicast(&msg
, ifa
, n
->addr
);
1456 babel_auth_send_challenge_reply(struct babel_iface
*ifa
, struct babel_neighbor
*n
, struct babel_msg_auth
*rcv
)
1458 struct babel_proto
*p
= ifa
->proto
;
1459 union babel_msg msg
= {};
1461 TRACE(D_PACKETS
, "Sending challenge reply to %I on %s",
1462 n
->addr
, ifa
->ifname
);
1464 n
->auth_next_challenge_reply
= current_time() + BABEL_AUTH_CHALLENGE_INTERVAL
;
1466 msg
.type
= BABEL_TLV_CHALLENGE_REPLY
;
1467 msg
.challenge
.nonce_len
= rcv
->challenge_len
;
1468 msg
.challenge
.nonce
= rcv
->challenge
;
1470 babel_send_unicast(&msg
, ifa
, n
->addr
);
1474 babel_auth_check_pc(struct babel_iface
*ifa
, struct babel_msg_auth
*msg
)
1476 struct babel_proto
*p
= ifa
->proto
;
1477 struct babel_neighbor
*n
;
1480 * We create the neighbour entry at this point because it makes it easier to
1481 * rate limit challenge replies; this is explicitly allowed by the spec (see
1484 n
= babel_get_neighbor(ifa
, msg
->sender
);
1486 /* (3b) Handle challenge request */
1487 if (msg
->challenge_seen
&& (n
->auth_next_challenge_reply
<= current_time()))
1488 babel_auth_send_challenge_reply(ifa
, n
, msg
);
1490 /* (4a) If PC TLV is missing, drop the packet */
1493 LOG_PKT_AUTH("Authentication failed for %I on %s - missing or invalid PC",
1494 msg
->sender
, ifa
->ifname
);
1498 /* (4b) On successful challenge, update PC and index to current values */
1499 if (msg
->challenge_reply_seen
&&
1500 (n
->auth_nonce_expiry
> current_time()) &&
1501 !memcmp(msg
->challenge_reply
, n
->auth_nonce
, BABEL_AUTH_NONCE_LEN
))
1503 n
->auth_index_len
= msg
->index_len
;
1504 memcpy(n
->auth_index
, msg
->index
, msg
->index_len
);
1506 n
->auth_pc
= msg
->pc
;
1512 /* (5) If index differs, send challenge and drop the packet */
1513 if ((n
->auth_index_len
!= msg
->index_len
) ||
1514 memcmp(n
->auth_index
, msg
->index
, msg
->index_len
))
1516 TRACE(D_PACKETS
, "Index mismatch for packet from %I via %s",
1517 msg
->sender
, ifa
->ifname
);
1519 if (n
->auth_next_challenge
<= current_time())
1520 babel_auth_send_challenge_request(ifa
, n
);
1525 /* (6) Index matches; only accept if PC is greater than last */
1526 if (n
->auth_pc
>= msg
->pc
)
1528 LOG_PKT_AUTH("Authentication failed for %I on %s - "
1529 "lower packet counter (rcv %u, old %u)",
1530 msg
->sender
, ifa
->ifname
, msg
->pc
, n
->auth_pc
);
1534 n
->auth_pc
= msg
->pc
;
1546 * babel_iface_timer - Babel interface timer handler
1549 * This function is called by the per-interface timer and triggers sending of
1550 * periodic Hello's and both triggered and periodic updates. Periodic Hello's
1551 * and updates are simply handled by setting the next_{hello,regular} variables
1552 * on the interface, and triggering an update (and resetting the variable)
1553 * whenever 'now' exceeds that value.
1555 * For triggered updates, babel_trigger_iface_update() will set the
1556 * want_triggered field on the interface to a timestamp value. If this is set
1557 * (and the next_triggered time has passed; this is a rate limiting mechanism),
1558 * babel_send_update() will be called with this timestamp as the second
1559 * parameter. This causes updates to be send consisting of only the routes that
1560 * have changed since the time saved in want_triggered.
1562 * Mostly when an update is triggered, the route being modified will be set to
1563 * the value of 'now' at the time of the trigger; the >= comparison for
1564 * selecting which routes to send in the update will make sure this is included.
1567 babel_iface_timer(timer
*t
)
1569 struct babel_iface
*ifa
= t
->data
;
1570 struct babel_proto
*p
= ifa
->proto
;
1571 btime hello_period
= ifa
->cf
->hello_interval
;
1572 btime update_period
= ifa
->cf
->update_interval
;
1573 btime now_
= current_time();
1575 if (now_
>= ifa
->next_hello
)
1577 babel_send_hello(ifa
);
1578 ifa
->next_hello
+= hello_period
* (1 + (now_
- ifa
->next_hello
) / hello_period
);
1581 if (now_
>= ifa
->next_regular
)
1583 TRACE(D_EVENTS
, "Sending regular updates on %s", ifa
->ifname
);
1584 babel_send_update(ifa
, 0);
1585 ifa
->next_regular
+= update_period
* (1 + (now_
- ifa
->next_regular
) / update_period
);
1586 ifa
->want_triggered
= 0;
1589 else if (ifa
->want_triggered
&& (now_
>= ifa
->next_triggered
))
1591 TRACE(D_EVENTS
, "Sending triggered updates on %s", ifa
->ifname
);
1592 babel_send_update(ifa
, ifa
->want_triggered
);
1593 ifa
->next_triggered
= now_
+ MIN(1 S
, update_period
/ 2);
1594 ifa
->want_triggered
= 0;
1598 btime next_event
= MIN(ifa
->next_hello
, ifa
->next_regular
);
1599 if (ifa
->want_triggered
) next_event
= MIN(next_event
, ifa
->next_triggered
);
1600 tm_set(ifa
->timer
, next_event
);
1604 babel_iface_kick_timer(struct babel_iface
*ifa
)
1606 if (ifa
->timer
->expires
> (current_time() + 100 MS
))
1607 tm_start(ifa
->timer
, 100 MS
);
1611 babel_iface_start(struct babel_iface
*ifa
)
1613 struct babel_proto
*p
= ifa
->proto
;
1615 TRACE(D_EVENTS
, "Starting interface %s", ifa
->ifname
);
1617 ifa
->next_hello
= current_time() + (random() % ifa
->cf
->hello_interval
);
1618 ifa
->next_regular
= current_time() + (random() % ifa
->cf
->update_interval
);
1619 ifa
->next_triggered
= current_time() + MIN(1 S
, ifa
->cf
->update_interval
/ 2);
1620 ifa
->want_triggered
= 0; /* We send an immediate update (below) */
1621 tm_start(ifa
->timer
, 100 MS
);
1624 babel_send_hello(ifa
);
1625 babel_send_wildcard_retraction(ifa
);
1626 babel_send_wildcard_request(ifa
);
1627 babel_send_update(ifa
, 0); /* Full update */
1631 babel_iface_stop(struct babel_iface
*ifa
)
1633 struct babel_proto
*p
= ifa
->proto
;
1634 struct babel_neighbor
*nbr
;
1635 struct babel_route
*r
;
1638 TRACE(D_EVENTS
, "Stopping interface %s", ifa
->ifname
);
1641 * Rather than just flushing the neighbours, we set the metric of their routes
1642 * to infinity. This allows us to keep the neighbour hello state for when the
1643 * interface comes back up. The routes will also be kept until they expire.
1645 WALK_LIST(nbr
, ifa
->neigh_list
)
1647 WALK_LIST(n
, nbr
->routes
)
1649 r
= SKIP_BACK(struct babel_route
, neigh_route
, n
);
1650 babel_retract_route(p
, r
);
1654 tm_stop(ifa
->timer
);
1659 babel_iface_link_up(struct babel_iface
*ifa
)
1661 return !ifa
->cf
->check_link
|| (ifa
->iface
->flags
& IF_LINK_UP
);
1665 babel_iface_update_state(struct babel_iface
*ifa
)
1667 int up
= ifa
->sk
&& babel_iface_link_up(ifa
);
1673 babel_iface_start(ifa
);
1675 babel_iface_stop(ifa
);
1679 babel_iface_update_addr4(struct babel_iface
*ifa
)
1681 struct babel_proto
*p
= ifa
->proto
;
1683 ip_addr addr4
= ifa
->iface
->addr4
? ifa
->iface
->addr4
->ip
: IPA_NONE
;
1684 ifa
->next_hop_ip4
= ipa_nonzero(ifa
->cf
->next_hop_ip4
) ? ifa
->cf
->next_hop_ip4
: addr4
;
1686 if (ipa_zero(ifa
->next_hop_ip4
) && p
->ip4_channel
)
1687 log(L_WARN
"%s: Missing IPv4 next hop address for %s", p
->p
.name
, ifa
->ifname
);
1690 babel_iface_kick_timer(ifa
);
1694 babel_iface_update_buffers(struct babel_iface
*ifa
)
1699 uint mtu
= MAX(BABEL_MIN_MTU
, ifa
->iface
->mtu
);
1700 uint rbsize
= ifa
->cf
->rx_buffer
?: mtu
;
1701 uint tbsize
= ifa
->cf
->tx_length
?: mtu
;
1702 rbsize
= MAX(rbsize
, tbsize
);
1704 sk_set_rbsize(ifa
->sk
, rbsize
);
1705 sk_set_tbsize(ifa
->sk
, tbsize
);
1707 ifa
->tx_length
= tbsize
- BABEL_OVERHEAD
;
1709 babel_auth_set_tx_overhead(ifa
);
1712 static struct babel_iface
*
1713 babel_find_iface(struct babel_proto
*p
, struct iface
*what
)
1715 struct babel_iface
*ifa
;
1717 WALK_LIST (ifa
, p
->interfaces
)
1718 if (ifa
->iface
== what
)
1725 babel_iface_locked(struct object_lock
*lock
)
1727 struct babel_iface
*ifa
= lock
->data
;
1728 struct babel_proto
*p
= ifa
->proto
;
1730 if (!babel_open_socket(ifa
))
1732 log(L_ERR
"%s: Cannot open socket for %s", p
->p
.name
, ifa
->iface
->name
);
1736 babel_iface_update_buffers(ifa
);
1737 babel_iface_update_state(ifa
);
1741 babel_add_iface(struct babel_proto
*p
, struct iface
*new, struct babel_iface_config
*ic
)
1743 struct babel_iface
*ifa
;
1745 TRACE(D_EVENTS
, "Adding interface %s", new->name
);
1747 pool
*pool
= rp_new(p
->p
.pool
, new->name
);
1749 ifa
= mb_allocz(pool
, sizeof(struct babel_iface
));
1754 ifa
->ifname
= new->name
;
1755 ifa
->addr
= new->llv6
->ip
;
1757 add_tail(&p
->interfaces
, NODE ifa
);
1759 ip_addr addr4
= new->addr4
? new->addr4
->ip
: IPA_NONE
;
1760 ifa
->next_hop_ip4
= ipa_nonzero(ic
->next_hop_ip4
) ? ic
->next_hop_ip4
: addr4
;
1761 ifa
->next_hop_ip6
= ipa_nonzero(ic
->next_hop_ip6
) ? ic
->next_hop_ip6
: ifa
->addr
;
1763 if (ipa_zero(ifa
->next_hop_ip4
) && p
->ip4_channel
)
1764 log(L_WARN
"%s: Missing IPv4 next hop address for %s", p
->p
.name
, new->name
);
1766 init_list(&ifa
->neigh_list
);
1767 ifa
->hello_seqno
= 1;
1769 if (ic
->auth_type
!= BABEL_AUTH_NONE
)
1770 babel_auth_reset_index(ifa
);
1772 ifa
->timer
= tm_new_init(ifa
->pool
, babel_iface_timer
, ifa
, 0, 0);
1774 init_list(&ifa
->msg_queue
);
1775 ifa
->send_event
= ev_new_init(ifa
->pool
, babel_send_queue
, ifa
);
1777 struct object_lock
*lock
= olock_new(ifa
->pool
);
1778 lock
->type
= OBJLOCK_UDP
;
1779 lock
->addr
= IP6_BABEL_ROUTERS
;
1780 lock
->port
= ifa
->cf
->port
;
1781 lock
->iface
= ifa
->iface
;
1782 lock
->hook
= babel_iface_locked
;
1785 olock_acquire(lock
);
1789 babel_remove_iface(struct babel_proto
*p
, struct babel_iface
*ifa
)
1791 TRACE(D_EVENTS
, "Removing interface %s", ifa
->iface
->name
);
1793 struct babel_neighbor
*n
;
1794 WALK_LIST_FIRST(n
, ifa
->neigh_list
)
1795 babel_flush_neighbor(p
, n
);
1799 rfree(ifa
->pool
); /* contains ifa itself, locks, socket, etc */
1803 iface_is_valid(struct babel_proto
*p
, struct iface
*iface
)
1805 if (!(iface
->flags
& IF_MULTICAST
))
1807 log(L_ERR
"%s: Interface %s does not support multicast",
1808 p
->p
.name
, iface
->name
);
1817 babel_if_notify(struct proto
*P
, unsigned flags
, struct iface
*iface
)
1819 struct babel_proto
*p
= (void *) P
;
1820 struct babel_config
*cf
= (void *) P
->cf
;
1821 struct babel_iface
*ifa
= babel_find_iface(p
, iface
);
1823 if (iface
->flags
& IF_IGNORE
)
1826 /* Add, remove or restart interface */
1827 if (flags
& (IF_CHANGE_UPDOWN
| IF_CHANGE_LLV6
))
1830 babel_remove_iface(p
, ifa
);
1832 if (!(iface
->flags
& IF_UP
))
1835 /* Ignore ifaces without link-local address */
1839 struct babel_iface_config
*ic
= (void *) iface_patt_find(&cf
->iface_list
, iface
, NULL
);
1841 if (ic
&& iface_is_valid(p
, iface
))
1842 babel_add_iface(p
, iface
, ic
);
1850 if (flags
& IF_CHANGE_ADDR4
)
1851 babel_iface_update_addr4(ifa
);
1853 if (flags
& IF_CHANGE_MTU
)
1854 babel_iface_update_buffers(ifa
);
1856 if (flags
& IF_CHANGE_LINK
)
1857 babel_iface_update_state(ifa
);
1861 babel_reconfigure_iface(struct babel_proto
*p
, struct babel_iface
*ifa
, struct babel_iface_config
*new)
1863 struct babel_iface_config
*old
= ifa
->cf
;
1865 /* Change of these options would require to reset the iface socket */
1866 if ((new->port
!= old
->port
) ||
1867 (new->tx_tos
!= old
->tx_tos
) ||
1868 (new->tx_priority
!= old
->tx_priority
))
1871 TRACE(D_EVENTS
, "Reconfiguring interface %s", ifa
->iface
->name
);
1875 ip_addr addr4
= ifa
->iface
->addr4
? ifa
->iface
->addr4
->ip
: IPA_NONE
;
1876 ifa
->next_hop_ip4
= ipa_nonzero(new->next_hop_ip4
) ? new->next_hop_ip4
: addr4
;
1877 ifa
->next_hop_ip6
= ipa_nonzero(new->next_hop_ip6
) ? new->next_hop_ip6
: ifa
->addr
;
1879 babel_iface_update_buffers(ifa
);
1881 if ((new->auth_type
!= BABEL_AUTH_NONE
) && (new->auth_type
!= old
->auth_type
))
1882 babel_auth_reset_index(ifa
);
1884 if (ipa_zero(ifa
->next_hop_ip4
) && p
->ip4_channel
)
1885 log(L_WARN
"%s: Missing IPv4 next hop address for %s", p
->p
.name
, ifa
->ifname
);
1887 if (ifa
->next_hello
> (current_time() + new->hello_interval
))
1888 ifa
->next_hello
= current_time() + (random() % new->hello_interval
);
1890 if (ifa
->next_regular
> (current_time() + new->update_interval
))
1891 ifa
->next_regular
= current_time() + (random() % new->update_interval
);
1893 if (new->check_link
!= old
->check_link
)
1894 babel_iface_update_state(ifa
);
1897 babel_iface_kick_timer(ifa
);
1903 babel_reconfigure_ifaces(struct babel_proto
*p
, struct babel_config
*cf
)
1905 struct iface
*iface
;
1907 WALK_LIST(iface
, iface_list
)
1909 if (!(iface
->flags
& IF_UP
))
1912 /* Ignore ifaces without link-local address */
1916 struct babel_iface
*ifa
= babel_find_iface(p
, iface
);
1917 struct babel_iface_config
*ic
= (void *) iface_patt_find(&cf
->iface_list
, iface
, NULL
);
1919 if (ic
&& !iface_is_valid(p
, iface
))
1924 if (babel_reconfigure_iface(p
, ifa
, ic
))
1928 log(L_INFO
"%s: Restarting interface %s", p
->p
.name
, ifa
->iface
->name
);
1929 babel_remove_iface(p
, ifa
);
1930 babel_add_iface(p
, iface
, ic
);
1934 babel_remove_iface(p
, ifa
);
1937 babel_add_iface(p
, iface
, ic
);
1943 * Debugging and info output functions
1947 babel_dump_source(struct babel_source
*s
)
1949 debug("Source router_id %lR seqno %d metric %d expires %t\n",
1950 s
->router_id
, s
->seqno
, s
->metric
,
1951 s
->expires
? s
->expires
- current_time() : 0);
1955 babel_dump_route(struct babel_route
*r
)
1957 debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %t\n",
1958 r
->neigh
->addr
, r
->neigh
->ifa
->ifname
, r
->seqno
, r
->advert_metric
, r
->metric
,
1959 r
->router_id
, r
->expires
? r
->expires
- current_time() : 0);
1963 babel_dump_entry(struct babel_entry
*e
)
1965 struct babel_source
*s
;
1966 struct babel_route
*r
;
1968 debug("Babel: Entry %N:\n", e
->n
.addr
);
1970 WALK_LIST(s
,e
->sources
)
1971 { debug(" "); babel_dump_source(s
); }
1973 WALK_LIST(r
,e
->routes
)
1976 if (r
== e
->selected
) debug("*");
1977 babel_dump_route(r
);
1982 babel_dump_neighbor(struct babel_neighbor
*n
)
1984 debug("Neighbor %I txcost %d hello_map %x next seqno %d expires %t/%t\n",
1985 n
->addr
, n
->txcost
, n
->hello_map
, n
->next_hello_seqno
,
1986 n
->hello_expiry
? n
->hello_expiry
- current_time() : 0,
1987 n
->ihu_expiry
? n
->ihu_expiry
- current_time() : 0);
1991 babel_dump_iface(struct babel_iface
*ifa
)
1993 struct babel_neighbor
*n
;
1995 debug("Babel: Interface %s addr %I rxcost %d type %d hello seqno %d intervals %t %t",
1996 ifa
->ifname
, ifa
->addr
, ifa
->cf
->rxcost
, ifa
->cf
->type
, ifa
->hello_seqno
,
1997 ifa
->cf
->hello_interval
, ifa
->cf
->update_interval
);
1998 debug(" next hop v4 %I next hop v6 %I\n", ifa
->next_hop_ip4
, ifa
->next_hop_ip6
);
2000 WALK_LIST(n
, ifa
->neigh_list
)
2001 { debug(" "); babel_dump_neighbor(n
); }
2005 babel_dump(struct proto
*P
)
2007 struct babel_proto
*p
= (struct babel_proto
*) P
;
2008 struct babel_iface
*ifa
;
2010 debug("Babel: router id %lR update seqno %d\n", p
->router_id
, p
->update_seqno
);
2012 WALK_LIST(ifa
, p
->interfaces
)
2013 babel_dump_iface(ifa
);
2015 FIB_WALK(&p
->ip4_rtable
, struct babel_entry
, e
)
2017 babel_dump_entry(e
);
2020 FIB_WALK(&p
->ip6_rtable
, struct babel_entry
, e
)
2022 babel_dump_entry(e
);
2028 babel_get_route_info(rte
*rte
, byte
*buf
)
2031 eattr
*e
= ea_find(rte
->attrs
->eattrs
, EA_BABEL_ROUTER_ID
);
2033 memcpy(&rid
, e
->u
.ptr
->data
, sizeof(u64
));
2035 buf
+= bsprintf(buf
, " (%d/%d) [%lR]", rte
->attrs
->pref
,
2036 ea_get_int(rte
->attrs
->eattrs
, EA_BABEL_METRIC
, BABEL_INFINITY
), rid
);
2040 babel_get_attr(const eattr
*a
, byte
*buf
, int buflen UNUSED
)
2044 case EA_BABEL_SEQNO
:
2047 case EA_BABEL_METRIC
:
2048 bsprintf(buf
, "metric: %d", a
->u
.data
);
2051 case EA_BABEL_ROUTER_ID
:
2054 memcpy(&rid
, a
->u
.ptr
->data
, sizeof(u64
));
2055 bsprintf(buf
, "router_id: %lR", rid
);
2065 babel_show_interfaces(struct proto
*P
, const char *iff
)
2067 struct babel_proto
*p
= (void *) P
;
2068 struct babel_iface
*ifa
= NULL
;
2069 struct babel_neighbor
*nbr
= NULL
;
2071 if (p
->p
.proto_state
!= PS_UP
)
2073 cli_msg(-1023, "%s: is not up", p
->p
.name
);
2077 cli_msg(-1023, "%s:", p
->p
.name
);
2078 cli_msg(-1023, "%-10s %-6s %-5s %7s %6s %7s %-15s %s",
2079 "Interface", "State", "Auth", "RX cost", "Nbrs", "Timer",
2080 "Next hop (v4)", "Next hop (v6)");
2082 WALK_LIST(ifa
, p
->interfaces
)
2084 if (iff
&& !patmatch(iff
, ifa
->iface
->name
))
2088 WALK_LIST(nbr
, ifa
->neigh_list
)
2091 btime timer
= MIN(ifa
->next_regular
, ifa
->next_hello
) - current_time();
2092 cli_msg(-1023, "%-10s %-6s %-5s %7u %6u %7t %-15I %I",
2093 ifa
->iface
->name
, (ifa
->up
? "Up" : "Down"),
2094 (ifa
->cf
->auth_type
== BABEL_AUTH_MAC
?
2095 (ifa
->cf
->auth_permissive
? "Perm" : "Yes") : "No"),
2096 ifa
->cf
->rxcost
, nbrs
, MAX(timer
, 0),
2097 ifa
->next_hop_ip4
, ifa
->next_hop_ip6
);
2102 babel_show_neighbors(struct proto
*P
, const char *iff
)
2104 struct babel_proto
*p
= (void *) P
;
2105 struct babel_iface
*ifa
= NULL
;
2106 struct babel_neighbor
*n
= NULL
;
2107 struct babel_route
*r
= NULL
;
2109 if (p
->p
.proto_state
!= PS_UP
)
2111 cli_msg(-1024, "%s: is not up", p
->p
.name
);
2115 cli_msg(-1024, "%s:", p
->p
.name
);
2116 cli_msg(-1024, "%-25s %-10s %6s %6s %6s %7s %4s",
2117 "IP address", "Interface", "Metric", "Routes", "Hellos", "Expires", "Auth");
2119 WALK_LIST(ifa
, p
->interfaces
)
2121 if (iff
&& !patmatch(iff
, ifa
->iface
->name
))
2124 WALK_LIST(n
, ifa
->neigh_list
)
2127 WALK_LIST(r
, n
->routes
)
2130 uint hellos
= u32_popcount(n
->hello_map
);
2131 btime timer
= (n
->hello_expiry
?: n
->init_expiry
) - current_time();
2132 cli_msg(-1024, "%-25I %-10s %6u %6u %6u %7t %-4s",
2133 n
->addr
, ifa
->iface
->name
, n
->cost
, rts
, hellos
, MAX(timer
, 0),
2134 n
->auth_passed
? "Yes" : "No");
2140 babel_show_entries_(struct babel_proto
*p
, struct fib
*rtable
)
2142 int width
= babel_sadr_enabled(p
) ? -54 : -24;
2144 FIB_WALK(rtable
, struct babel_entry
, e
)
2146 struct babel_route
*r
= NULL
;
2147 uint rts
= 0, srcs
= 0;
2150 WALK_LIST(n
, e
->routes
)
2153 WALK_LIST(n
, e
->sources
)
2157 cli_msg(-1025, "%-*N %-23lR %6u %5u %7u %7u", width
,
2158 e
->n
.addr
, e
->router_id
, e
->metric
, e
->seqno
, rts
, srcs
);
2159 else if (r
= e
->selected
)
2160 cli_msg(-1025, "%-*N %-23lR %6u %5u %7u %7u", width
,
2161 e
->n
.addr
, r
->router_id
, r
->metric
, r
->seqno
, rts
, srcs
);
2163 cli_msg(-1025, "%-*N %-23s %6s %5s %7u %7u", width
,
2164 e
->n
.addr
, "<none>", "-", "-", rts
, srcs
);
2170 babel_show_entries(struct proto
*P
)
2172 struct babel_proto
*p
= (void *) P
;
2173 int width
= babel_sadr_enabled(p
) ? -54 : -24;
2175 if (p
->p
.proto_state
!= PS_UP
)
2177 cli_msg(-1025, "%s: is not up", p
->p
.name
);
2181 cli_msg(-1025, "%s:", p
->p
.name
);
2182 cli_msg(-1025, "%-*s %-23s %6s %5s %7s %7s", width
,
2183 "Prefix", "Router ID", "Metric", "Seqno", "Routes", "Sources");
2185 babel_show_entries_(p
, &p
->ip4_rtable
);
2186 babel_show_entries_(p
, &p
->ip6_rtable
);
2190 babel_show_routes_(struct babel_proto
*p
, struct fib
*rtable
)
2192 int width
= babel_sadr_enabled(p
) ? -54 : -24;
2194 FIB_WALK(rtable
, struct babel_entry
, e
)
2196 struct babel_route
*r
;
2197 WALK_LIST(r
, e
->routes
)
2199 char c
= (r
== e
->selected
) ? '*' : (r
->feasible
? '+' : ' ');
2200 btime time
= r
->expires
? r
->expires
- current_time() : 0;
2201 cli_msg(-1025, "%-*N %-25I %-10s %5u %c %5u %7t", width
,
2202 e
->n
.addr
, r
->next_hop
, r
->neigh
->ifa
->ifname
,
2203 r
->metric
, c
, r
->seqno
, MAX(time
, 0));
2210 babel_show_routes(struct proto
*P
)
2212 struct babel_proto
*p
= (void *) P
;
2213 int width
= babel_sadr_enabled(p
) ? -54 : -24;
2215 if (p
->p
.proto_state
!= PS_UP
)
2217 cli_msg(-1025, "%s: is not up", p
->p
.name
);
2221 cli_msg(-1025, "%s:", p
->p
.name
);
2222 cli_msg(-1025, "%-*s %-25s %-9s %6s F %5s %7s", width
,
2223 "Prefix", "Nexthop", "Interface", "Metric", "Seqno", "Expires");
2225 babel_show_routes_(p
, &p
->ip4_rtable
);
2226 babel_show_routes_(p
, &p
->ip6_rtable
);
2231 * Babel protocol glue
2235 * babel_timer - global timer hook
2238 * This function is called by the global protocol instance timer and handles
2239 * expiration of routes and neighbours as well as pruning of the seqno request
2243 babel_timer(timer
*t
)
2245 struct babel_proto
*p
= t
->data
;
2247 babel_expire_routes(p
);
2248 babel_expire_neighbors(p
);
2252 babel_kick_timer(struct babel_proto
*p
)
2254 if (p
->timer
->expires
> (current_time() + 100 MS
))
2255 tm_start(p
->timer
, 100 MS
);
2260 babel_preexport(struct proto
*P
, struct rte
*new)
2262 struct rta
*a
= new->attrs
;
2263 /* Reject our own unreachable routes */
2264 if ((a
->dest
== RTD_UNREACHABLE
) && (new->src
->proto
== P
))
2271 * babel_rt_notify - core tells us about new route (possibly our own),
2272 * so store it into our data structures.
2275 babel_rt_notify(struct proto
*P
, struct channel
*c UNUSED
, struct network
*net
,
2276 struct rte
*new, struct rte
*old UNUSED
)
2278 struct babel_proto
*p
= (void *) P
;
2279 struct babel_entry
*e
;
2285 uint rt_metric
= ea_get_int(new->attrs
->eattrs
, EA_BABEL_METRIC
, 0);
2286 u64 rt_router_id
= 0;
2288 if (new->src
->proto
== P
)
2290 rt_seqno
= ea_find(new->attrs
->eattrs
, EA_BABEL_SEQNO
)->u
.data
;
2291 eattr
*e
= ea_find(new->attrs
->eattrs
, EA_BABEL_ROUTER_ID
);
2293 memcpy(&rt_router_id
, e
->u
.ptr
->data
, sizeof(u64
));
2297 rt_seqno
= p
->update_seqno
;
2298 rt_router_id
= p
->router_id
;
2301 if (rt_metric
> BABEL_INFINITY
)
2303 log(L_WARN
"%s: Invalid babel_metric value %u for route %N",
2304 p
->p
.name
, rt_metric
, net
->n
.addr
);
2305 rt_metric
= BABEL_INFINITY
;
2308 e
= babel_get_entry(p
, net
->n
.addr
);
2310 /* Activate triggered updates */
2311 if ((e
->valid
!= BABEL_ENTRY_VALID
) ||
2312 (e
->router_id
!= rt_router_id
))
2314 babel_trigger_update(p
);
2315 e
->updated
= current_time();
2318 e
->valid
= BABEL_ENTRY_VALID
;
2319 e
->seqno
= rt_seqno
;
2320 e
->metric
= rt_metric
;
2321 e
->router_id
= rt_router_id
;
2326 e
= babel_find_entry(p
, net
->n
.addr
);
2328 if (!e
|| e
->valid
!= BABEL_ENTRY_VALID
)
2331 e
->valid
= BABEL_ENTRY_STALE
;
2332 e
->metric
= BABEL_INFINITY
;
2334 babel_trigger_update(p
);
2335 e
->updated
= current_time();
2340 babel_rte_better(struct rte
*new, struct rte
*old
)
2342 uint new_metric
= ea_find(new->attrs
->eattrs
, EA_BABEL_SEQNO
)->u
.data
;
2343 uint old_metric
= ea_find(old
->attrs
->eattrs
, EA_BABEL_SEQNO
)->u
.data
;
2345 return new_metric
< old_metric
;
2349 babel_rte_igp_metric(struct rte
*rt
)
2351 return ea_get_int(rt
->attrs
->eattrs
, EA_BABEL_METRIC
, BABEL_INFINITY
);
2356 babel_postconfig(struct proto_config
*CF
)
2358 struct babel_config
*cf
= (void *) CF
;
2359 struct channel_config
*ip4
, *ip6
, *ip6_sadr
;
2361 ip4
= proto_cf_find_channel(CF
, NET_IP4
);
2362 ip6
= proto_cf_find_channel(CF
, NET_IP6
);
2363 ip6_sadr
= proto_cf_find_channel(CF
, NET_IP6_SADR
);
2365 if (ip6
&& ip6_sadr
)
2366 cf_error("Both ipv6 and ipv6-sadr channels");
2368 cf
->ip4_channel
= ip4
;
2369 cf
->ip6_channel
= ip6
?: ip6_sadr
;
2372 static struct proto
*
2373 babel_init(struct proto_config
*CF
)
2375 struct proto
*P
= proto_new(CF
);
2376 struct babel_proto
*p
= (void *) P
;
2377 struct babel_config
*cf
= (void *) CF
;
2379 proto_configure_channel(P
, &p
->ip4_channel
, cf
->ip4_channel
);
2380 proto_configure_channel(P
, &p
->ip6_channel
, cf
->ip6_channel
);
2382 P
->if_notify
= babel_if_notify
;
2383 P
->rt_notify
= babel_rt_notify
;
2384 P
->preexport
= babel_preexport
;
2385 P
->rte_better
= babel_rte_better
;
2386 P
->rte_igp_metric
= babel_rte_igp_metric
;
2392 babel_randomize_router_id(struct babel_proto
*p
)
2394 p
->router_id
&= (u64
) 0xffffffff;
2395 p
->router_id
|= ((u64
) random()) << 32;
2396 TRACE(D_EVENTS
, "Randomized router ID to %lR", p
->router_id
);
2400 babel_start(struct proto
*P
)
2402 struct babel_proto
*p
= (void *) P
;
2403 struct babel_config
*cf
= (void *) P
->cf
;
2404 u8 ip6_type
= cf
->ip6_channel
? cf
->ip6_channel
->net_type
: NET_IP6
;
2406 fib_init(&p
->ip4_rtable
, P
->pool
, NET_IP4
, sizeof(struct babel_entry
),
2407 OFFSETOF(struct babel_entry
, n
), 0, babel_init_entry
);
2408 fib_init(&p
->ip6_rtable
, P
->pool
, ip6_type
, sizeof(struct babel_entry
),
2409 OFFSETOF(struct babel_entry
, n
), 0, babel_init_entry
);
2411 init_list(&p
->interfaces
);
2412 p
->timer
= tm_new_init(P
->pool
, babel_timer
, p
, 1 S
, 0);
2413 tm_start(p
->timer
, 1 S
);
2414 p
->update_seqno
= 1;
2415 p
->router_id
= proto_get_router_id(&cf
->c
);
2417 if (cf
->randomize_router_id
)
2418 babel_randomize_router_id(p
);
2420 p
->route_slab
= sl_new(P
->pool
, sizeof(struct babel_route
));
2421 p
->source_slab
= sl_new(P
->pool
, sizeof(struct babel_source
));
2422 p
->msg_slab
= sl_new(P
->pool
, sizeof(struct babel_msg_node
));
2423 p
->seqno_slab
= sl_new(P
->pool
, sizeof(struct babel_seqno_request
));
2425 p
->log_pkt_tbf
= (struct tbf
){ .rate
= 1, .burst
= 5 };
2431 babel_iface_shutdown(struct babel_iface
*ifa
)
2435 babel_send_wildcard_retraction(ifa
);
2436 babel_send_queue(ifa
);
2441 babel_shutdown(struct proto
*P
)
2443 struct babel_proto
*p
= (void *) P
;
2444 struct babel_iface
*ifa
;
2446 TRACE(D_EVENTS
, "Shutdown requested");
2448 WALK_LIST(ifa
, p
->interfaces
)
2449 babel_iface_shutdown(ifa
);
2455 babel_reconfigure(struct proto
*P
, struct proto_config
*CF
)
2457 struct babel_proto
*p
= (void *) P
;
2458 struct babel_config
*new = (void *) CF
;
2459 u8 ip6_type
= new->ip6_channel
? new->ip6_channel
->net_type
: NET_IP6
;
2461 TRACE(D_EVENTS
, "Reconfiguring");
2463 if (p
->ip6_rtable
.addr_type
!= ip6_type
)
2466 if (!proto_configure_channel(P
, &p
->ip4_channel
, new->ip4_channel
) ||
2467 !proto_configure_channel(P
, &p
->ip6_channel
, new->ip6_channel
))
2471 babel_reconfigure_ifaces(p
, new);
2473 babel_trigger_update(p
);
2474 babel_kick_timer(p
);
2480 struct protocol proto_babel
= {
2482 .template = "babel%d",
2483 .class = PROTOCOL_BABEL
,
2484 .preference
= DEF_PREF_BABEL
,
2485 .channel_mask
= NB_IP
| NB_IP6_SADR
,
2486 .proto_size
= sizeof(struct babel_proto
),
2487 .config_size
= sizeof(struct babel_config
),
2488 .postconfig
= babel_postconfig
,
2491 .start
= babel_start
,
2492 .shutdown
= babel_shutdown
,
2493 .reconfigure
= babel_reconfigure
,
2494 .get_route_info
= babel_get_route_info
,
2495 .get_attr
= babel_get_attr
2501 proto_build(&proto_babel
);