diff options
| -rw-r--r-- | nest/route.h | 1 | ||||
| -rw-r--r-- | proto/babel/babel.c | 562 | ||||
| -rw-r--r-- | proto/babel/babel.h | 36 | ||||
| -rw-r--r-- | proto/babel/config.Y | 8 | ||||
| -rw-r--r-- | proto/babel/packets.c | 2 |
5 files changed, 316 insertions, 293 deletions
diff --git a/nest/route.h b/nest/route.h index 2aa2bcd8..a838bd38 100644 --- a/nest/route.h +++ b/nest/route.h @@ -236,6 +236,7 @@ typedef struct rte { #endif #ifdef CONFIG_BABEL struct { + u16 seqno; /* Babel seqno */ u16 metric; /* Babel metric */ u64 router_id; /* Babel router id */ } babel; diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 68b32e8f..768bbda8 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -2,6 +2,8 @@ * BIRD -- The Babel protocol * * Copyright (c) 2015--2016 Toke Hoiland-Jorgensen + * (c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org> + * (c) 2016--2017 CZ.NIC z.s.p.o. * * Can be freely distributed and used under the terms of the GNU GPL. * @@ -29,17 +31,14 @@ * * The main route selection is done in babel_select_route(). This is called when * an entry is updated by receiving updates from the network or when modified by - * internal timers. It performs feasibility checks on the available routes for - * the prefix and selects the one with the lowest metric to be announced to the - * core. + * internal timers. The function selects from feasible and reachable routes the + * one with the lowest metric to be announced to the core. */ #include <stdlib.h> #include "babel.h" -#define OUR_ROUTE(r) (r->neigh == NULL) - /* * Is one number greater or equal than another mod 2^16? This is based on the * definition of serial number space in RFC 1982. Note that arguments are of @@ -49,7 +48,8 @@ static inline int ge_mod64k(uint a, uint b) { return (u16)(a - b) < 0x8000; } static void babel_expire_requests(struct babel_proto *p, struct babel_entry *e); -static void babel_select_route(struct babel_proto *p, struct babel_entry *e); +static void babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod); +static inline void babel_announce_retraction(struct babel_proto *p, struct babel_entry *e); static void babel_send_route_request(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *n); static void babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr); static void babel_update_cost(struct babel_neighbor *n); @@ -161,35 +161,35 @@ babel_get_route(struct babel_proto *p, struct babel_entry *e, struct babel_neigh r = sl_alloc(p->route_slab); memset(r, 0, sizeof(*r)); + r->e = e; + r->neigh = nbr; add_tail(&e->routes, NODE r); - - if (nbr) - { - r->neigh = nbr; - r->expires = current_time() + BABEL_GARBAGE_INTERVAL; - add_tail(&nbr->routes, NODE &r->neigh_route); - } + add_tail(&nbr->routes, NODE &r->neigh_route); return r; } +static inline void +babel_retract_route(struct babel_proto *p, struct babel_route *r) +{ + r->metric = r->advert_metric = BABEL_INFINITY; + + if (r == r->e->selected) + babel_select_route(p, r->e, r); +} + static void babel_flush_route(struct babel_proto *p, struct babel_route *r) { DBG("Babel: Flush route %N router_id %lR neigh %I\n", - r->e->n.addr, r->router_id, r->neigh ? r->neigh->addr : IPA_NONE); + r->e->n.addr, r->router_id, r->neigh->addr); rem_node(NODE r); + rem_node(&r->neigh_route); - if (r->neigh) - rem_node(&r->neigh_route); - - if (r->e->selected_in == r) - r->e->selected_in = NULL; - - if (r->e->selected_out == r) - r->e->selected_out = NULL; + if (r->e->selected == r) + r->e->selected = NULL; sl_free(p->route_slab, r); } @@ -197,15 +197,15 @@ babel_flush_route(struct babel_proto *p, struct babel_route *r) static void babel_expire_route(struct babel_proto *p, struct babel_route *r) { - struct babel_entry *e = r->e; + struct babel_config *cf = (void *) p->p.cf; TRACE(D_EVENTS, "Route expiry timer for %N router-id %lR fired", - e->n.addr, r->router_id); + r->e->n.addr, r->router_id); if (r->metric < BABEL_INFINITY) { r->metric = r->advert_metric = BABEL_INFINITY; - r->expires = current_time() + r->expiry_interval; + r->expires = current_time() + cf->hold_time; } else { @@ -216,7 +216,7 @@ babel_expire_route(struct babel_proto *p, struct babel_route *r) static void babel_refresh_route(struct babel_proto *p, struct babel_route *r) { - if (!OUR_ROUTE(r) && (r == r->e->selected_in)) + if (r == r->e->selected) babel_send_route_request(p, r->e, r->neigh); r->refresh_time = 0; @@ -225,6 +225,7 @@ babel_refresh_route(struct babel_proto *p, struct babel_route *r) static void babel_expire_routes_(struct babel_proto *p, struct fib *rtable) { + struct babel_config *cf = (void *) p->p.cf; struct babel_route *r, *rx; struct fib_iterator fit; btime now_ = current_time(); @@ -243,8 +244,8 @@ loop: if (r->expires && r->expires <= now_) { + changed = changed || (r == e->selected); babel_expire_route(p, r); - changed = 1; } } @@ -255,9 +256,20 @@ loop: * synchronous events babel_select_route() -> nest table change -> * babel_rt_notify() -> rtable change, invalidating hidden variables. */ + FIB_ITERATE_PUT(&fit); + babel_select_route(p, e, NULL); + goto loop; + } + + /* Clean up stale entries */ + if ((e->valid == BABEL_ENTRY_STALE) && ((e->updated + cf->hold_time) <= now_)) + e->valid = BABEL_ENTRY_DUMMY; + /* Clean up unreachable route */ + if (e->unreachable && (!e->valid || (e->router_id == p->router_id))) + { FIB_ITERATE_PUT(&fit); - babel_select_route(p, e); + babel_announce_retraction(p, e); goto loop; } @@ -265,7 +277,7 @@ loop: babel_expire_requests(p, e); /* Remove empty entries */ - if (EMPTY_LIST(e->sources) && EMPTY_LIST(e->routes) && EMPTY_LIST(e->requests)) + if (!e->valid && EMPTY_LIST(e->routes) && EMPTY_LIST(e->sources) && EMPTY_LIST(e->requests)) { FIB_ITERATE_PUT(&fit); fib_delete(rtable, e); @@ -425,20 +437,16 @@ babel_get_neighbor(struct babel_iface *ifa, ip_addr addr) static void babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) { + struct babel_route *r; node *n; TRACE(D_EVENTS, "Removing neighbor %I on %s", nbr->addr, nbr->ifa->iface->name); WALK_LIST_FIRST(n, nbr->routes) { - struct babel_route *r = SKIP_BACK(struct babel_route, neigh_route, n); - struct babel_entry *e = r->e; - int selected = (r == e->selected_in); - + r = SKIP_BACK(struct babel_route, neigh_route, n); + babel_retract_route(p, r); babel_flush_route(p, r); - - if (selected) - babel_select_route(p, e); } nbr->ifa = NULL; @@ -600,7 +608,7 @@ done: WALK_LIST2(r, n, nbr->routes, neigh_route) { r->metric = babel_compute_metric(nbr, r->advert_metric); - babel_select_route(p, r->e); + babel_select_route(p, r->e, r); } } } @@ -611,119 +619,151 @@ done: * @e: Babel route entry to announce * * This function announces a Babel entry to the core if it has a selected - * incoming path, and retracts it otherwise. If the selected entry has infinite - * metric, the route is announced as unreachable. + * incoming path, and retracts it otherwise. If there is no selected route but + * the entry is valid and ours, the unreachable route is announced instead. */ static void babel_announce_rte(struct babel_proto *p, struct babel_entry *e) { - struct babel_route *r = e->selected_in; + struct babel_route *r = e->selected; struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; if (r) { - rta *ap0 = allocz(RTA_MAX_SIZE); - *ap0 = (rta) { + rta a0 = { .src = p->p.main_source, .source = RTS_BABEL, .scope = SCOPE_UNIVERSE, - .dest = r->metric == BABEL_INFINITY ? RTD_UNREACHABLE : RTD_UNICAST, + .dest = RTD_UNICAST, .from = r->neigh->addr, + .nh.gw = r->next_hop, .nh.iface = r->neigh->ifa->iface, }; - if (r->metric < BABEL_INFINITY) - ap0->nh.gw = r->next_hop; - - rta *a = rta_lookup(ap0); + rta *a = rta_lookup(&a0); rte *rte = rte_get_temp(a); + rte->u.babel.seqno = r->seqno; rte->u.babel.metric = r->metric; rte->u.babel.router_id = r->router_id; rte->pflags = 0; - r->old_metric = r->metric; + e->unreachable = 0; + rte_update2(c, e->n.addr, rte, p->p.main_source); + } + else if (e->valid && (e->router_id != p->router_id)) + { + /* Unreachable */ + rta a0 = { + .src = p->p.main_source, + .source = RTS_BABEL, + .scope = SCOPE_UNIVERSE, + .dest = RTD_UNREACHABLE, + }; + + rta *a = rta_lookup(&a0); + rte *rte = rte_get_temp(a); + memset(&rte->u.babel, 0, sizeof(rte->u.babel)); + rte->pflags = 0; + rte->pref = 1; + + e->unreachable = 1; rte_update2(c, e->n.addr, rte, p->p.main_source); } else { /* Retraction */ + e->unreachable = 0; rte_update2(c, e->n.addr, NULL, p->p.main_source); } } +/* Special case of babel_announce_rte() just for retraction */ +static inline void +babel_announce_retraction(struct babel_proto *p, struct babel_entry *e) +{ + struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; + e->unreachable = 0; + rte_update2(c, e->n.addr, NULL, p->p.main_source); +} + + /** * babel_select_route - select best route for given route entry + * @p: Babel protocol instance * @e: Babel entry to select the best route for + * @mod: Babel route that was modified or NULL if unspecified * - * Select the best feasible route for a given prefix among the routes received - * from peers, and propagate it to the nest. This just selects the feasible - * route with the lowest metric. + * Select the best reachable and feasible route for a given prefix among the + * routes received from peers, and propagate it to the nest. This just selects + * the reachable and feasible route with the lowest metric, but keeps selected + * the old one in case of tie. * * If no feasible route is available for a prefix that previously had a route - * selected, a seqno request is sent to try to get a valid route. In the - * meantime, the route is marked as infeasible in the nest (to blackhole packets - * going to it, as per the RFC). + * selected, a seqno request is sent to try to get a valid route. If the entry + * is valid and not owned by us, the unreachable route is announced to the nest + * (to blackhole packets going to it, as per section 2.8). It is later removed + * by babel_expire_routes(). Otherwise, the route is just removed from the nest. + * + * Argument @mod is used to optimize best route calculation. When specified, the + * function can assume that only the @mod route was modified to avoid full best + * route selection and announcement when non-best route was modified in minor + * way. The caller is advised to not call babel_select_route() when no change is + * done (e.g. periodic route updates) to avoid unnecessary announcements of the + * same best route. The caller is not required to call the function in case of a + * retraction of a non-best route. * - * If no feasible route is available, and no previous route is selected, the - * route is removed from the nest entirely. + * Note that the function does not active triggered updates. That is done by + * babel_rt_notify() when the change is propagated back to Babel. */ static void -babel_select_route(struct babel_proto *p, struct babel_entry *e) +babel_select_route(struct babel_proto *p, struct babel_entry *e, struct babel_route *mod) { - struct babel_route *r, *cur = e->selected_in, *best = e->selected_in; + struct babel_route *r, *best = e->selected; - /* try to find the best feasible route */ - WALK_LIST(r, e->routes) - if (!OUR_ROUTE(r) && /* prevent propagating our own routes back to core */ - (!cur || r->metric < cur->metric) && - babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric)) - cur = r; - - if (cur && !OUR_ROUTE(cur) && (cur->metric < BABEL_INFINITY) && - (!best || (cur->metric < best->metric) || ((cur == best) && (cur->metric != cur->old_metric)))) + /* Shortcut if only non-best was modified */ + if (mod && (mod != best)) { - if (cur != best) - TRACE(D_EVENTS, "Picked new route for prefix %N: router id %lR metric %d", - e->n.addr, cur->router_id, cur->metric); - - e->selected_in = cur; - e->updated = current_time(); - babel_announce_rte(p, e); + /* Either select modified route, or keep old best route */ + if ((mod->metric < (best ? best->metric : BABEL_INFINITY)) && mod->feasible) + best = mod; + else + return; } - else if (!cur || cur->metric == BABEL_INFINITY) + else { - /* Couldn't find a feasible route. If we have a selected route, that means - it just became infeasible; so set it's metric to infinite and install it - (as unreachable), then send a seqno request. - - babel_build_rte() will set the unreachable flag if the metric is BABEL_INFINITY.*/ - if (best) - { - TRACE(D_EVENTS, "Lost feasible route for prefix %N", e->n.addr); - - best->metric = best->advert_metric = BABEL_INFINITY; - e->updated = current_time(); + /* Selected route may be modified and no longer admissible */ + if (!best || (best->metric == BABEL_INFINITY) || !best->feasible) + best = NULL; - babel_add_seqno_request(p, e, best->router_id, best->seqno + 1, 0, NULL); - babel_announce_rte(p, e); + /* Find the best feasible route from all routes */ + WALK_LIST(r, e->routes) + if ((r->metric < (best ? best->metric : BABEL_INFINITY)) && r->feasible) + best = r; + } - /* Section 3.6 of the RFC forbids an infeasible from being selected. This - is cleared after announcing the route to the core to make sure an - unreachable route is propagated first. */ - e->selected_in = NULL; - } - else - { - /* No route currently selected, and no new one selected; this means we - don't have a route to this destination anymore (and were probably - called from an expiry timer). Remove the route from the nest. */ - // TRACE(D_EVENTS, "Flushing route for prefix %N", e->n.addr); + if (best) + { + if (best != e->selected) + TRACE(D_EVENTS, "Picked new route for prefix %N: router-id %lR metric %d", + e->n.addr, best->router_id, best->metric); + } + else if (e->selected) + { + /* + * We have lost all feasible routes. We have to broadcast seqno request + * (Section 3.8.2.1) and keep unreachable route for a while (section 2.8). + * The later is done automatically by babel_announce_rte(). + */ - e->selected_in = NULL; - e->updated = current_time(); - babel_announce_rte(p, e); - } + TRACE(D_EVENTS, "Lost feasible route for prefix %N", e->n.addr); + if (e->valid && (e->selected->router_id == e->router_id)) + babel_add_seqno_request(p, e, e->selected->router_id, e->selected->seqno + 1, 0, NULL); } + else + return; + + e->selected = best; + babel_announce_rte(p, e); } /* @@ -883,16 +923,14 @@ babel_send_update_(struct babel_iface *ifa, btime changed, struct fib *rtable) FIB_WALK(rtable, struct babel_entry, e) { - struct babel_route *r = e->selected_out; - - if (!r) + if (!e->valid) continue; /* Our own seqno might have changed, in which case we update the routes we originate. */ - if ((r->router_id == p->router_id) && (r->seqno < p->update_seqno)) + if ((e->router_id == p->router_id) && (e->seqno < p->update_seqno)) { - r->seqno = p->update_seqno; + e->seqno = p->update_seqno; e->updated = current_time(); } @@ -901,14 +939,14 @@ babel_send_update_(struct babel_iface *ifa, btime changed, struct fib *rtable) continue; TRACE(D_PACKETS, "Sending update for %N router-id %lR seqno %d metric %d", - e->n.addr, r->router_id, r->seqno, r->metric); + e->n.addr, e->router_id, e->seqno, e->metric); union babel_msg msg = {}; msg.type = BABEL_TLV_UPDATE; msg.update.interval = ifa->cf->update_interval; - msg.update.seqno = r->seqno; - msg.update.metric = r->metric; - msg.update.router_id = r->router_id; + msg.update.seqno = e->seqno; + msg.update.metric = e->metric; + msg.update.router_id = e->router_id; net_copy(&msg.update.net, e->n.addr); msg.update.next_hop = ((e->n.addr->type == NET_IP4) ? @@ -917,9 +955,9 @@ babel_send_update_(struct babel_iface *ifa, btime changed, struct fib *rtable) babel_enqueue(&msg, ifa); /* Update feasibility distance for redistributed routes */ - if (!OUR_ROUTE(r)) + if (e->router_id != p->router_id) { - struct babel_source *s = babel_get_source(p, e, r->router_id); + struct babel_source *s = babel_get_source(p, e, e->router_id); s->expires = current_time() + BABEL_GARBAGE_INTERVAL; if ((msg.update.seqno > s->seqno) || @@ -1164,39 +1202,6 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) return; } - /* - * RFC section 3.5.4: - * - * When a Babel node receives an update (id, prefix, seqno, metric) from a - * neighbour neigh with a link cost value equal to cost, it checks whether it - * already has a routing table entry indexed by (neigh, id, prefix). - * - * If no such entry exists: - * - * o if the update is unfeasible, it is ignored; - * - * o if the metric is infinite (the update is a retraction), the update is - * ignored; - * - * o otherwise, a new route table entry is created, indexed by (neigh, id, - * prefix), with seqno equal to seqno and an advertised metric equal to the - * metric carried by the update. - * - * If such an entry exists: - * - * o if the entry is currently installed and the update is unfeasible, then - * the behaviour depends on whether the router-ids of the two entries match. - * If the router-ids are different, the update is treated as though it were - * a retraction (i.e., as though the metric were FFFF hexadecimal). If the - * router-ids are equal, the update is ignored; - * - * o otherwise (i.e., if either the update is feasible or the entry is not - * currently installed), then the entry's sequence number, advertised - * metric, metric, and router-id are updated and, unless the advertised - * metric is infinite, the route's expiry timer is reset to a small multiple - * of the Interval value included in the update. - */ - /* Retraction */ if (msg->metric == BABEL_INFINITY) { @@ -1209,8 +1214,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) WALK_LIST(n, nbr->routes) { r = SKIP_BACK(struct babel_route, neigh_route, n); - r->metric = r->advert_metric = BABEL_INFINITY; - babel_select_route(p, r->e); + babel_retract_route(p, r); } } else @@ -1226,71 +1230,56 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) if (!r) return; - r->metric = r->advert_metric = BABEL_INFINITY; - babel_select_route(p, e); + /* Router-id, next-hop and seqno are ignored for retractions */ + babel_retract_route(p, r); } /* Done with retractions */ return; } + /* Regular update */ e = babel_get_entry(p, &msg->net); - r = babel_find_route(e, nbr); /* the route entry indexed by neighbour */ + r = babel_get_route(p, e, nbr); /* the route entry indexed by neighbour */ s = babel_find_source(e, msg->router_id); /* for feasibility */ feasible = babel_is_feasible(s, msg->seqno, msg->metric); metric = babel_compute_metric(nbr, msg->metric); - best = e->selected_in; + best = e->selected; /* RFC section 3.8.2.2 - Dealing with unfeasible updates */ if (!feasible && (metric != BABEL_INFINITY) && (!best || (r == best) || (metric < best->metric))) babel_add_seqno_request(p, e, s->router_id, s->seqno + 1, 0, nbr); - if (!r) - { - if (!feasible) - return; - - r = babel_get_route(p, e, nbr); - r->advert_metric = msg->metric; - r->router_id = msg->router_id; - r->metric = metric; - r->next_hop = msg->next_hop; - r->seqno = msg->seqno; - } - else if (r == best && !feasible) - { - /* Penultimate paragraph above - ignore or retract */ - if (msg->router_id == r->router_id) - return; + /* Special case - ignore unfeasible update to best route */ + if (r == best && !feasible && (msg->router_id == r->router_id)) + return; - /* Treat as retraction */ - r->metric = r->advert_metric = BABEL_INFINITY; - } - else - { - /* Last paragraph above - update the entry */ - r->advert_metric = msg->metric; - r->metric = metric; - r->next_hop = msg->next_hop; + r->expires = current_time() + BABEL_ROUTE_EXPIRY_FACTOR(msg->interval); + r->refresh_time = current_time() + BABEL_ROUTE_REFRESH_FACTOR(msg->interval); - r->router_id = msg->router_id; - r->seqno = msg->seqno; + /* No further processing if there is no change */ + if ((r->feasible == feasible) && (r->seqno == msg->seqno) && + (r->metric == metric) && (r->advert_metric == msg->metric) && + (r->router_id == msg->router_id) && ipa_equal(r->next_hop, msg->next_hop)) + return; - r->expiry_interval = BABEL_ROUTE_EXPIRY_FACTOR(msg->interval); - r->expires = current_time() + r->expiry_interval; - if (r->expiry_interval > BABEL_ROUTE_REFRESH_INTERVAL) - r->refresh_time = current_time() + r->expiry_interval - BABEL_ROUTE_REFRESH_INTERVAL; + /* Last paragraph above - update the entry */ + r->feasible = feasible; + r->seqno = msg->seqno; + r->metric = metric; + r->advert_metric = msg->metric; + r->router_id = msg->router_id; + r->next_hop = msg->next_hop; - /* If received update satisfies seqno request, we send triggered updates */ - if (babel_satisfy_seqno_request(p, e, msg->router_id, msg->seqno)) - { - babel_trigger_update(p); - e->updated = current_time(); - } + /* If received update satisfies seqno request, we send triggered updates */ + if (babel_satisfy_seqno_request(p, e, msg->router_id, msg->seqno)) + { + babel_trigger_update(p); + e->updated = current_time(); } - babel_select_route(p, e); + babel_select_route(p, e, r); } void @@ -1338,13 +1327,12 @@ babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) /* Ignore if we have no such entry or entry has infinite metric */ struct babel_entry *e = babel_find_entry(p, &msg->net); - if (!e || !e->selected_out || (e->selected_out->metric == BABEL_INFINITY)) + if (!e || !e->valid || (e->metric == BABEL_INFINITY)) return; /* Trigger update on incoming interface if we have a selected route with different router id or seqno no smaller than requested */ - struct babel_route *r = e->selected_out; - if ((r->router_id != msg->router_id) || ge_mod64k(r->seqno, msg->seqno)) + if ((e->router_id != msg->router_id) || ge_mod64k(e->seqno, msg->seqno)) { babel_trigger_iface_update(ifa); e->updated = current_time(); @@ -1365,11 +1353,10 @@ babel_handle_seqno_request(union babel_msg *m, struct babel_iface *ifa) /* Find best admissible route */ struct babel_route *r, *best1 = NULL, *best2 = NULL; WALK_LIST(r, e->routes) - if ((r->router_id == msg->router_id) && r->neigh && !ipa_equal(r->neigh->addr, msg->sender)) + if ((r->router_id == msg->router_id) && !ipa_equal(r->neigh->addr, msg->sender)) { /* Find best feasible route */ - if (babel_is_feasible(babel_find_source(e, r->router_id), r->seqno, r->advert_metric) && - (!best1 || r->metric < best1->metric)) + if ((!best1 || r->metric < best1->metric) && r->feasible) best1 = r; /* Find best not necessary feasible route */ @@ -1483,7 +1470,6 @@ babel_iface_stop(struct babel_iface *ifa) struct babel_neighbor *nbr; struct babel_route *r; node *n; - btime now_ = current_time(); TRACE(D_EVENTS, "Stopping interface %s", ifa->ifname); @@ -1497,11 +1483,7 @@ babel_iface_stop(struct babel_iface *ifa) WALK_LIST(n, nbr->routes) { r = SKIP_BACK(struct babel_route, neigh_route, n); - r->metric = r->advert_metric = BABEL_INFINITY; - r->expires = now_ + r->expiry_interval; - - if (r == r->e->selected_in) - babel_select_route(p, r->e); + babel_retract_route(p, r); } } @@ -1777,10 +1759,8 @@ static void babel_dump_route(struct babel_route *r) { debug("Route neigh %I if %s seqno %d metric %d/%d router_id %lR expires %t\n", - r->neigh ? r->neigh->addr : IPA_NONE, - r->neigh ? r->neigh->ifa->ifname : "(none)", - r->seqno, r->advert_metric, r->metric, r->router_id, - r->expires ? r->expires - current_time() : 0); + r->neigh->addr, r->neigh->ifa->ifname, r->seqno, r->advert_metric, r->metric, + r->router_id, r->expires ? r->expires - current_time() : 0); } static void @@ -1797,8 +1777,7 @@ babel_dump_entry(struct babel_entry *e) WALK_LIST(r,e->routes) { debug(" "); - if (r == e->selected_out) debug("*"); - if (r == e->selected_in) debug("+"); + if (r == e->selected) debug("*"); babel_dump_route(r); } } @@ -1956,36 +1935,29 @@ babel_show_neighbors(struct proto *P, char *iff) } static void -babel_show_entries_(struct babel_proto *p, struct fib *rtable) +babel_show_entries_(struct babel_proto *p UNUSED, struct fib *rtable) { - struct babel_source *s = NULL; - struct babel_route *r = NULL; - - char ridbuf[ROUTER_ID_64_LENGTH+1]; - FIB_WALK(rtable, struct babel_entry, e) { - r = e->selected_in ? e->selected_in : e->selected_out; + struct babel_route *r = NULL; + uint rts = 0, srcs = 0; + node *n; - int srcs = 0; - WALK_LIST(s, e->sources) - srcs++; + WALK_LIST(n, e->routes) + rts++; - if (r) - { - if (r->router_id == p->router_id) - bsprintf(ridbuf, "%s", "<self>"); - else - bsprintf(ridbuf, "%lR", r->router_id); + WALK_LIST(n, e->sources) + srcs++; - btime time = r->expires ? r->expires - current_time() : 0; - cli_msg(-1025, "%-29N %-23s %6u %5u %7t %7u", - e->n.addr, ridbuf, r->metric, r->seqno, MAX(time, 0), srcs); - } + if (e->valid) + cli_msg(-1025, "%-24N %-23lR %6u %5u %7u %7u", + e->n.addr, e->router_id, e->metric, e->seqno, rts, srcs); + else if (r = e->selected) + cli_msg(-1025, "%-24N %-23lR %6u %5u %7u %7u", + e->n.addr, r->router_id, r->metric, r->seqno, rts, srcs); else - { - cli_msg(-1025, "%-29N %-44s %7u", e->n.addr, "<pending>", srcs); - } + cli_msg(-1025, "%-24N %-23s %6s %5s %7u %7u", + e->n.addr, "<none>", "-", "-", rts, srcs); } FIB_WALK_END; } @@ -2003,8 +1975,8 @@ babel_show_entries(struct proto *P) } cli_msg(-1025, "%s:", p->p.name); - cli_msg(-1025, "%-29s %-23s %6s %5s %7s %7s", - "Prefix", "Router ID", "Metric", "Seqno", "Expires", "Sources"); + cli_msg(-1025, "%-24s %-23s %6s %5s %7s %7s", + "Prefix", "Router ID", "Metric", "Seqno", "Routes", "Sources"); babel_show_entries_(p, &p->ip4_rtable); babel_show_entries_(p, &p->ip6_rtable); @@ -2012,6 +1984,46 @@ babel_show_entries(struct proto *P) cli_msg(0, ""); } +static void +babel_show_routes_(struct babel_proto *p UNUSED, struct fib *rtable) +{ + FIB_WALK(rtable, struct babel_entry, e) + { + struct babel_route *r; + WALK_LIST(r, e->routes) + { + char c = (r == e->selected) ? '*' : (r->feasible ? '+' : ' '); + btime time = r->expires ? r->expires - current_time() : 0; + cli_msg(-1025, "%-24N %-25I %-10s %5u %c %5u %7t", + e->n.addr, r->next_hop, r->neigh->ifa->ifname, + r->metric, c, r->seqno, MAX(time, 0)); + } + } + FIB_WALK_END; +} + +void +babel_show_routes(struct proto *P) +{ + struct babel_proto *p = (void *) P; + + if (p->p.proto_state != PS_UP) + { + cli_msg(-1025, "%s: is not up", p->p.name); + cli_msg(0, ""); + return; + } + + cli_msg(-1025, "%s:", p->p.name); + cli_msg(-1025, "%-24s %-25s %-9s %6s F %5s %7s", + "Prefix", "Nexthop", "Interface", "Metric", "Seqno", "Expires"); + + babel_show_routes_(p, &p->ip4_rtable); + babel_show_routes_(p, &p->ip6_rtable); + + cli_msg(0, ""); +} + /* * Babel protocol glue @@ -2069,12 +2081,18 @@ babel_prepare_attrs(struct linpool *pool, ea_list *next, uint metric, u64 router static int -babel_import_control(struct proto *P, struct rte **rt, struct ea_list **attrs, struct linpool *pool) +babel_import_control(struct proto *P, struct rte **new, struct ea_list **attrs, struct linpool *pool) { struct babel_proto *p = (void *) P; + rte *rt = *new; + + /* Reject our own unreachable routes */ + if ((rt->attrs->dest == RTD_UNREACHABLE) && (rt->attrs->src->proto == P)) + return -1; + /* Prepare attributes with initial values */ - if ((*rt)->attrs->source != RTS_BABEL) + if (rt->attrs->source != RTS_BABEL) *attrs = babel_prepare_attrs(pool, NULL, 0, p->router_id); return 0; @@ -2102,65 +2120,50 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, { struct babel_proto *p = (void *) P; struct babel_entry *e; - struct babel_route *r; if (new) { /* Update */ - e = babel_get_entry(p, net->n.addr); + uint internal = (new->attrs->src->proto == P); + uint rt_seqno = internal ? new->u.babel.seqno : p->update_seqno; + uint rt_metric = ea_get_int(attrs, EA_BABEL_METRIC, 0); + uint rt_router_id = internal ? new->u.babel.router_id : p->router_id; - if (new->attrs->src->proto != P) + if (rt_metric > BABEL_INFINITY) { - r = babel_get_route(p, e, NULL); - r->seqno = p->update_seqno; - r->router_id = p->router_id; - r->metric = 0; /* FIXME: should be selectable */ + log(L_WARN "%s: Invalid babel_metric value %u for route %N", + p->p.name, rt_metric, net->n.addr); + rt_metric = BABEL_INFINITY; } - else - r = e->selected_in; - if (r != e->selected_out) + e = babel_get_entry(p, net->n.addr); + + /* Activate triggered updates */ + if ((e->valid |= BABEL_ENTRY_VALID) || + (e->router_id != rt_router_id)) { babel_trigger_update(p); e->updated = current_time(); - e->selected_out = r; } + + e->valid = BABEL_ENTRY_VALID; + e->seqno = rt_seqno; + e->metric = rt_metric; + e->router_id = rt_router_id; } else { /* Withdraw */ e = babel_find_entry(p, net->n.addr); - if (!e || !e->selected_out) + + if (!e || e->valid != BABEL_ENTRY_VALID) return; - if (OUR_ROUTE(e->selected_out)) - { - /* - * We originate this route, so set its metric to infinity and set an - * expiry time. This causes a retraction to be sent, and later the route - * to be flushed once the hold time has passed. - */ - babel_trigger_update(p); - e->updated = current_time(); - e->selected_out->metric = BABEL_INFINITY; - e->selected_out->expires = current_time() + BABEL_HOLD_TIME; - } - else - { - /* - * This is a route originating from someone else that was lost; presumably - * because an export filter was updated to filter it. This means we can't - * set the metric to infinity (it would be overridden on subsequent - * updates from the peer originating the route), so just clear the - * exported route. - * - * This causes peers to expire the route after a while (like if we just - * shut down), but it's the best we can do in these circumstances; and - * since export filters presumably aren't updated that often this is - * acceptable. - */ - e->selected_out = NULL; - } + e->valid = BABEL_ENTRY_STALE; + e->metric = BABEL_INFINITY; + + babel_trigger_update(p); + e->updated = current_time(); } } @@ -2173,8 +2176,9 @@ babel_rte_better(struct rte *new, struct rte *old) static int babel_rte_same(struct rte *new, struct rte *old) { - return ((new->u.babel.router_id == old->u.babel.router_id) && - (new->u.babel.metric == old->u.babel.metric)); + return ((new->u.babel.seqno == old->u.babel.seqno) && + (new->u.babel.metric == old->u.babel.metric) && + (new->u.babel.router_id == old->u.babel.router_id)); } diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 3ea21269..da3293ef 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -2,6 +2,8 @@ * BIRD -- The Babel protocol * * Copyright (c) 2015--2016 Toke Hoiland-Jorgensen + * (c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org> + * (c) 2016--2017 CZ.NIC z.s.p.o. * * Can be freely distributed and used under the terms of the GNU GPL. * @@ -37,11 +39,11 @@ #define BABEL_HELLO_LIMIT 12 #define BABEL_UPDATE_INTERVAL_FACTOR 4 #define BABEL_IHU_INTERVAL_FACTOR 3 +#define BABEL_HOLD_TIME_FACTOR 4 /* How long we keep unreachable route relative to update interval */ #define BABEL_IHU_EXPIRY_FACTOR(X) ((btime)(X)*7/2) /* 3.5 */ #define BABEL_HELLO_EXPIRY_FACTOR(X) ((btime)(X)*3/2) /* 1.5 */ #define BABEL_ROUTE_EXPIRY_FACTOR(X) ((btime)(X)*7/2) /* 3.5 */ -#define BABEL_ROUTE_REFRESH_INTERVAL (2 S_) /* Time before route expiry to send route request */ -#define BABEL_HOLD_TIME (10 S_) /* Expiry time for our own routes */ +#define BABEL_ROUTE_REFRESH_FACTOR(X) ((btime)(X)*5/2) /* 2.5 */ #define BABEL_SEQNO_REQUEST_RETRY 4 #define BABEL_SEQNO_REQUEST_EXPIRY (2 S_) #define BABEL_GARBAGE_INTERVAL (300 S_) @@ -105,8 +107,8 @@ enum babel_ae_type { struct babel_config { struct proto_config c; - - list iface_list; /* Patterns configured -- keep it first; see babel_reconfigure why */ + list iface_list; /* List of iface configs (struct babel_iface_config) */ + uint hold_time; /* Time to hold stale entries and unreachable routes */ }; struct babel_iface_config { @@ -220,15 +222,14 @@ struct babel_route { struct babel_entry *e; struct babel_neighbor *neigh; + u8 feasible; u16 seqno; - u16 advert_metric; u16 metric; - u16 old_metric; + u16 advert_metric; u64 router_id; ip_addr next_hop; btime refresh_time; btime expires; - btime expiry_interval; }; struct babel_seqno_request { @@ -242,19 +243,25 @@ struct babel_seqno_request { }; struct babel_entry { - struct babel_route *selected_in; - struct babel_route *selected_out; + struct babel_route *selected; - btime updated; - - list requests; - list sources; /* Source entries for this prefix (struct babel_source). */ list routes; /* Routes for this prefix (struct babel_route) */ + list sources; /* Source entries for this prefix (struct babel_source). */ + list requests; + + u8 valid; /* Entry validity state (BABEL_ENTRY_*) */ + u8 unreachable; /* Unreachable route is announced */ + u16 seqno; /* Outgoing seqno */ + u16 metric; /* Outgoing metric */ + u64 router_id; /* Outgoing router ID */ + btime updated; /* Last change of outgoing rte, for triggered updates */ struct fib_node n; }; -/* Stores forwarded seqno requests for duplicate suppression. */ +#define BABEL_ENTRY_DUMMY 0 /* No outgoing route */ +#define BABEL_ENTRY_VALID 1 /* Valid outgoing route */ +#define BABEL_ENTRY_STALE 2 /* Stale outgoing route, waiting for GC */ /* @@ -346,6 +353,7 @@ void babel_handle_seqno_request(union babel_msg *msg, struct babel_iface *ifa); void babel_show_interfaces(struct proto *P, char *iff); void babel_show_neighbors(struct proto *P, char *iff); void babel_show_entries(struct proto *P); +void babel_show_routes(struct proto *P); /* packets.c */ void babel_enqueue(union babel_msg *msg, struct babel_iface *ifa); diff --git a/proto/babel/config.Y b/proto/babel/config.Y index c72c00a3..25ce5ba0 100644 --- a/proto/babel/config.Y +++ b/proto/babel/config.Y @@ -2,6 +2,8 @@ * BIRD -- Babel Configuration * * Copyright (c) 2015-2016 Toke Hoiland-Jorgensen + * (c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org> + * (c) 2016--2017 CZ.NIC z.s.p.o. * * Can be freely distributed and used under the terms of the GNU GPL. */ @@ -32,6 +34,7 @@ babel_proto_start: proto_start BABEL { this_proto = proto_config_new(&proto_babel, $1); init_list(&BABEL_CFG->iface_list); + BABEL_CFG->hold_time = 1 S_; }; babel_proto_item: @@ -84,6 +87,8 @@ babel_iface_finish: if (!BABEL_IFACE->update_interval) BABEL_IFACE->update_interval = MIN_(BABEL_IFACE->hello_interval*BABEL_UPDATE_INTERVAL_FACTOR, BABEL_MAX_INTERVAL); BABEL_IFACE->ihu_interval = MIN_(BABEL_IFACE->hello_interval*BABEL_IHU_INTERVAL_FACTOR, BABEL_MAX_INTERVAL); + + BABEL_CFG->hold_time = MAX_(BABEL_CFG->hold_time, BABEL_IFACE->update_interval*BABEL_HOLD_TIME_FACTOR); }; @@ -131,6 +136,9 @@ CF_CLI(SHOW BABEL NEIGHBORS, optsym opttext, [<name>] [\"<interface>\"], [[Show CF_CLI(SHOW BABEL ENTRIES, optsym opttext, [<name>], [[Show information about Babel prefix entries]]) { babel_show_entries(proto_get_named($4, &proto_babel)); }; +CF_CLI(SHOW BABEL ROUTES, optsym opttext, [<name>], [[Show information about Babel route entries]]) +{ babel_show_routes(proto_get_named($4, &proto_babel)); }; + CF_CODE CF_END diff --git a/proto/babel/packets.c b/proto/babel/packets.c index 8e972db2..4abcf7e4 100644 --- a/proto/babel/packets.c +++ b/proto/babel/packets.c @@ -2,6 +2,8 @@ * BIRD -- The Babel protocol * * Copyright (c) 2015--2016 Toke Hoiland-Jorgensen + * (c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org> + * (c) 2016--2017 CZ.NIC z.s.p.o. * * Can be freely distributed and used under the terms of the GNU GPL. * |