This allows for filtering routes from specific interfaces and neighbours. With the current internal route selection proto babel exports only up to one route and an admin cannot do fine-grained filtering. To fix this we rip out the internal route selection entirely and put them all into the bird's nest instead. This appears to not actually be a breaking change as route announcement was already based on which routes bird would send back to babel_rt_notify filters shouldn't be able to tell the difference between a single and multiple routes AFAIK. --- Changes in v3: - Subsume FIB_RESTART v2 patch: instead of restarting FIB iteration we keep lists of actions to perform after FIB iteration is finished. proto/babel/babel.c | 269 +++++++++++++++++++------------------------- proto/babel/babel.h | 8 +- 2 files changed, 120 insertions(+), 157 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index ff8b6b52..087fd95b 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -29,10 +29,11 @@ * possible routes for the prefix are tracked as &babel_route entries and the * feasibility distance is maintained through &babel_source structures. * - * 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. The function selects from feasible and reachable routes the - * one with the lowest metric to be announced to the core. + * The main route selection is done by the bird nest (heh). For each prefix we + * export all feasible routes to the core with a distinct source (rte_src) per + * neihbour. Bird will then notify us of the optimal one by calling + * babel_rt_notify and we remember which neighbour it selected in + * babel_entry.selected_nbr. */ #include <stdlib.h> @@ -50,7 +51,7 @@ 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, struct babel_route *mod); +static void babel_announce_rte(struct babel_proto *p, struct babel_entry *e, struct babel_route *r); 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, struct babel_neighbor *n); @@ -164,13 +165,19 @@ babel_get_route(struct babel_proto *p, struct babel_entry *e, struct babel_neigh return r; } +static struct babel_route * +babel_get_selected_route(struct babel_proto *p, struct babel_entry *e) +{ + if (e->selected_nbr) + return babel_get_route(p, e, e->selected_nbr); + return NULL; +} + 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); + babel_announce_rte(p, r->e, r); } static void @@ -182,9 +189,6 @@ babel_flush_route(struct babel_proto *p UNUSED, struct babel_route *r) rem_node(NODE r); rem_node(&r->neigh_route); - if (r->e->selected == r) - r->e->selected = NULL; - sl_free(r); } @@ -200,6 +204,7 @@ babel_expire_route(struct babel_proto *p, struct babel_route *r) { r->metric = r->advert_metric = BABEL_INFINITY; r->expires = current_time() + cf->hold_time; + babel_announce_rte(p, r->e, r); } else { @@ -210,7 +215,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 (r == r->e->selected) + if (r == babel_get_selected_route(p, r->e)) babel_send_route_request(p, r->e, r->neigh); r->refresh_time = 0; @@ -221,16 +226,15 @@ babel_expire_routes_(struct babel_proto *p, struct fib *rtable) { struct babel_config *cf = (void *) p->p.cf; struct babel_route *r, *rx; + struct babel_entry *retract_head = NULL, *delete_head = NULL; + struct babel_route *expire_head = NULL; struct fib_iterator fit; btime now_ = current_time(); - FIB_ITERATE_INIT(&fit, rtable); -loop: + FIB_ITERATE_INIT(&fit, rtable); FIB_ITERATE_START(rtable, &fit, struct babel_entry, e) { - int changed = 0; - WALK_LIST_DELSAFE(r, rx, e->routes) { if (r->refresh_time && r->refresh_time <= now_) @@ -238,23 +242,11 @@ loop: if (r->expires && r->expires <= now_) { - changed = changed || (r == e->selected); - babel_expire_route(p, r); + r->expire_next = expire_head; + expire_head = r; } } - if (changed) - { - /* - * We have to restart the iteration because there may be a cascade of - * 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; @@ -262,9 +254,8 @@ loop: /* Clean up unreachable route */ if (e->unreachable && (!e->valid || (e->router_id == p->router_id))) { - FIB_ITERATE_PUT(&fit); - babel_announce_retraction(p, e); - goto loop; + e->retract_next = retract_head; + retract_head = e; } babel_expire_sources(p, e); @@ -273,12 +264,25 @@ loop: /* Remove empty entries */ if (!e->valid && EMPTY_LIST(e->routes) && EMPTY_LIST(e->sources) && EMPTY_LIST(e->requests)) { - FIB_ITERATE_PUT(&fit); - fib_delete(rtable, e); - goto loop; + e->delete_next = delete_head; + delete_head = e; } } FIB_ITERATE_END; + + for (struct babel_route *r_next, *r = expire_head; r ; r = r_next) { + r_next = r->expire_next; + babel_expire_route(p, r); + } + + for (struct babel_entry *e = retract_head; e ; e = e->retract_next) { + babel_announce_retraction(p, e); + } + + for (struct babel_entry *e_next, *e = delete_head; e ; e = e_next) { + e_next = e->delete_next; + fib_delete(rtable, e); + } } static void @@ -447,6 +451,7 @@ babel_get_neighbor(struct babel_iface *ifa, ip_addr addr) nbr = mb_allocz(ifa->pool, sizeof(struct babel_neighbor)); nbr->ifa = ifa; + nbr->src = rt_get_source(&p->p, idm_alloc(&p->src_ids)); nbr->addr = addr; nbr->rxcost = BABEL_INFINITY; nbr->txcost = BABEL_INFINITY; @@ -474,6 +479,8 @@ babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) } nbr->ifa = NULL; + + idm_free(&p->src_ids, nbr->src->private_id); rem_node(NODE nbr); mb_free(nbr); } @@ -634,11 +641,40 @@ done: WALK_LIST2(r, n, nbr->routes, neigh_route) { r->metric = babel_compute_metric(nbr, r->advert_metric); - babel_select_route(p, r->e, r); + babel_announce_rte(p, r->e, r); } } } +static void +babel_announce_rte_unreachable(struct babel_proto *p, struct babel_entry *e, u8 unreachable) +{ + struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; + rte *rte = NULL; + + if (unreachable) { + /* Unreachable */ + rta a0 = { + .source = RTS_BABEL, + .scope = SCOPE_UNIVERSE, + .dest = RTD_UNREACHABLE, + .pref = 1, + }; + + rta *a = rta_lookup(&a0); + rte = rte_get_temp(a, p->p.main_source); + } + + e->unreachable = unreachable; + + /* Unlike the many neighbour routes we only want one unreachable route, for + * one it's ugly to have lots of unreachable routes (if we just did this right + * in babel_announce_rte) but we also loose access to the neibour rte_src id + * when the neighbour is deallocated. This happens on a different schedule + * than unreachable route removal. */ + rte_update2(c, e->n.addr, rte, p->p.main_source); +} + /** * babel_announce_rte - announce selected route to the core * @p: Babel protocol instance @@ -649,12 +685,11 @@ done: * 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) +babel_announce_rte(struct babel_proto *p, struct babel_entry *e, struct babel_route *r) { - struct babel_route *r = e->selected; struct channel *c = (e->n.addr->type == NET_IP4) ? p->ip4_channel : p->ip6_channel; - if (r) + if (r->metric != BABEL_INFINITY && r->feasible) { rta a0 = { .source = RTS_BABEL, @@ -698,124 +733,27 @@ babel_announce_rte(struct babel_proto *p, struct babel_entry *e) a0.nh.flags = RNF_ONLINK; rta *a = rta_lookup(&a0); - rte *rte = rte_get_temp(a, p->p.main_source); + rte *rte = rte_get_temp(a, r->neigh->src); - 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 = { - .source = RTS_BABEL, - .scope = SCOPE_UNIVERSE, - .dest = RTD_UNREACHABLE, - .pref = 1, - }; - - rta *a = rta_lookup(&a0); - rte *rte = rte_get_temp(a, p->p.main_source); - - e->unreachable = 1; - rte_update2(c, e->n.addr, rte, p->p.main_source); + rte_update2(c, e->n.addr, rte, r->neigh->src); + babel_announce_rte_unreachable(p, e, 0); } else - { - /* Retraction */ - e->unreachable = 0; - rte_update2(c, e->n.addr, NULL, p->p.main_source); - } + rte_update2(c, e->n.addr, NULL, r->neigh->src); } /* Special case of babel_announce_rte() just for retraction */ static inline void babel_announce_retraction(struct babel_proto *p, struct babel_entry *e) { + TRACE(D_EVENTS, "Retract unreachable route for %N", + e->n.addr); + 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 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. 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. - * - * 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, struct babel_route *mod) -{ - struct babel_route *r, *best = e->selected; - - /* Shortcut if only non-best was modified */ - if (mod && (mod != best)) - { - /* Either select modified route, or keep old best route */ - if ((mod->metric < (best ? best->metric : BABEL_INFINITY)) && mod->feasible) - best = mod; - else - return; - } - else - { - /* Selected route may be modified and no longer admissible */ - if (!best || (best->metric == BABEL_INFINITY) || !best->feasible) - best = NULL; - - /* 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; - } - - 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(). - */ - - 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); -} - /* * Functions to send replies */ @@ -1300,7 +1238,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) 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; + best = babel_get_selected_route(p, e); /* * RFC section 3.8.2.2 - Dealing with unfeasible updates. Generate a one-off @@ -1338,7 +1276,7 @@ babel_handle_update(union babel_msg *m, struct babel_iface *ifa) e->updated = current_time(); } - babel_select_route(p, e, r); + babel_announce_rte(p, e, r); } void @@ -2003,10 +1941,10 @@ babel_dump_route(struct babel_route *r) } static void -babel_dump_entry(struct babel_entry *e) +babel_dump_entry(struct babel_proto *p, struct babel_entry *e) { struct babel_source *s; - struct babel_route *r; + struct babel_route *r, *best = babel_get_selected_route(p, e); debug("Babel: Entry %N:\n", e->n.addr); @@ -2016,7 +1954,7 @@ babel_dump_entry(struct babel_entry *e) WALK_LIST(r,e->routes) { debug(" "); - if (r == e->selected) debug("*"); + if (r == best) debug("*"); babel_dump_route(r); } } @@ -2057,12 +1995,12 @@ babel_dump(struct proto *P) FIB_WALK(&p->ip4_rtable, struct babel_entry, e) { - babel_dump_entry(e); + babel_dump_entry(p, e); } FIB_WALK_END; FIB_WALK(&p->ip6_rtable, struct babel_entry, e) { - babel_dump_entry(e); + babel_dump_entry(p, e); } FIB_WALK_END; } @@ -2186,7 +2124,7 @@ babel_show_entries_(struct babel_proto *p, struct fib *rtable) FIB_WALK(rtable, struct babel_entry, e) { - struct babel_route *r = NULL; + struct babel_route *r = NULL, *best = babel_get_selected_route(p, e); uint rts = 0, srcs = 0; node *n; @@ -2199,7 +2137,7 @@ babel_show_entries_(struct babel_proto *p, struct fib *rtable) if (e->valid) cli_msg(-1025, "%-*N %-23lR %6u %5u %7u %7u", width, e->n.addr, e->router_id, e->metric, e->seqno, rts, srcs); - else if (r = e->selected) + else if (r = best) cli_msg(-1025, "%-*N %-23lR %6u %5u %7u %7u", width, e->n.addr, r->router_id, r->metric, r->seqno, rts, srcs); else @@ -2236,10 +2174,10 @@ babel_show_routes_(struct babel_proto *p, struct fib *rtable) FIB_WALK(rtable, struct babel_entry, e) { - struct babel_route *r; + struct babel_route *r, *best = babel_get_selected_route(p, e); WALK_LIST(r, e->routes) { - char c = (r == e->selected) ? '*' : (r->feasible ? '+' : ' '); + char c = (r == best) ? '*' : (r->feasible ? '+' : ' '); btime time = r->expires ? r->expires - current_time() : 0; cli_msg(-1025, "%-*N %-25I %-10s %5u %c %5u %7t", width, e->n.addr, r->next_hop, r->neigh->ifa->ifname, @@ -2320,15 +2258,18 @@ 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_iface *ifa; + struct babel_neighbor *n; if (new) { /* Update */ + uint internal = new->src->proto == P; uint rt_seqno; uint rt_metric = ea_get_int(new->attrs->eattrs, EA_BABEL_METRIC, 0); u64 rt_router_id = 0; - if (new->src->proto == P) + if (internal) { rt_seqno = ea_find(new->attrs->eattrs, EA_BABEL_SEQNO)->u.data; eattr *e = ea_find(new->attrs->eattrs, EA_BABEL_ROUTER_ID); @@ -2350,6 +2291,18 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, e = babel_get_entry(p, net->n.addr); + while (internal) { + ifa = babel_find_iface(p, new->attrs->nh.iface); + if (!ifa) break; + n = babel_find_neighbor(ifa, new->attrs->from); + if (!n) break; + e->selected_nbr = n; + break; + } + if (!internal) { + e->selected_nbr = NULL; + } + /* Activate triggered updates */ if ((e->valid != BABEL_ENTRY_VALID) || (e->router_id != rt_router_id)) @@ -2373,6 +2326,9 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, e->valid = BABEL_ENTRY_STALE; e->metric = BABEL_INFINITY; + e->selected_nbr = NULL; + + babel_announce_rte_unreachable(p, e, 1); babel_trigger_update(p); e->updated = current_time(); @@ -2464,6 +2420,7 @@ babel_start(struct proto *P) p->source_slab = sl_new(P->pool, sizeof(struct babel_source)); p->msg_slab = sl_new(P->pool, sizeof(struct babel_msg_node)); p->seqno_slab = sl_new(P->pool, sizeof(struct babel_seqno_request)); + idm_init(&p->src_ids, P->pool, 8); p->log_pkt_tbf = (struct tbf){ .rate = 1, .burst = 5 }; diff --git a/proto/babel/babel.h b/proto/babel/babel.h index da8386b3..1d7e19f0 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -25,6 +25,7 @@ #include "lib/socket.h" #include "lib/string.h" #include "lib/timer.h" +#include "lib/idm.h" #define EA_BABEL_METRIC EA_CODE(PROTOCOL_BABEL, 0) #define EA_BABEL_ROUTER_ID EA_CODE(PROTOCOL_BABEL, 1) @@ -174,6 +175,7 @@ struct babel_proto { slab *source_slab; slab *msg_slab; slab *seqno_slab; + struct idm src_ids; struct tbf log_pkt_tbf; /* TBF for packet messages */ }; @@ -216,6 +218,7 @@ struct babel_iface { struct babel_neighbor { node n; struct babel_iface *ifa; + struct rte_src *src; ip_addr addr; u16 rxcost; /* Sent in last IHU */ @@ -256,6 +259,7 @@ struct babel_source { struct babel_route { node n; node neigh_route; + struct babel_route *expire_next; struct babel_entry *e; struct babel_neighbor *neigh; @@ -281,7 +285,9 @@ struct babel_seqno_request { }; struct babel_entry { - struct babel_route *selected; + struct babel_neighbor *selected_nbr; + + struct babel_entry *retract_next, *delete_next; list routes; /* Routes for this prefix (struct babel_route) */ list sources; /* Source entries for this prefix (struct babel_source). */ -- 2.30.2