diff options
| -rw-r--r-- | nest/route.h | 2 | ||||
| -rw-r--r-- | nest/rt-show.c | 2 | ||||
| -rw-r--r-- | nest/rt-table.c | 271 | ||||
| -rw-r--r-- | sysdep/unix/krt.c | 2 |
4 files changed, 174 insertions, 103 deletions
diff --git a/nest/route.h b/nest/route.h index 9baaeda0..e4507d4a 100644 --- a/nest/route.h +++ b/nest/route.h @@ -335,7 +335,7 @@ static inline net *net_get(rtable *tab, const net_addr *addr) { return (net *) f void *net_route(rtable *tab, const net_addr *n); int net_roa_check(rtable *tab, const net_addr *n, u32 asn); int rt_examine(rtable *t, net_addr *a, struct channel *c, const struct filter *filter); -rte *rt_export_merged(struct channel *c, net *net, linpool *pool, int silent); +rte *rt_export_merged_show(struct channel *c, net *n, linpool *pool); void rt_refresh_begin(rtable *t, struct channel *c); void rt_refresh_end(rtable *t, struct channel *c); void rt_modify_stale(rtable *t, struct channel *c); diff --git a/nest/rt-show.c b/nest/rt-show.c index ae5000f5..ffbc0a90 100644 --- a/nest/rt-show.c +++ b/nest/rt-show.c @@ -143,7 +143,7 @@ rt_show_net(struct cli *c, net *n, struct rt_show_data *d) { /* Special case for merged export */ pass = 1; - rte *em = rt_export_merged(ec, n, c->show_pool, 1); + rte *em = rt_export_merged_show(ec, n, c->show_pool); if (em) e = *em; else diff --git a/nest/rt-table.c b/nest/rt-table.c index 280551aa..146734f4 100644 --- a/nest/rt-table.c +++ b/nest/rt-table.c @@ -51,6 +51,13 @@ static linpool *rte_update_pool; list routing_tables; +struct rt_pending_export { + struct rte_storage *new; /* New route */ + struct rte_storage *new_best; /* New best route */ + struct rte_storage *old; /* Old route */ + struct rte_storage *old_best; /* Old best route */ +}; + static void rt_free_hostcache(rtable *tab); static void rt_notify_hostcache(rtable *tab, net *net); static void rt_update_hostcache(rtable *tab); @@ -370,6 +377,29 @@ rte_trace_out(uint flag, struct channel *c, rte *e, const char *msg) rte_trace(c, e, '<', msg); } +static uint +rte_feed_count(net *n) +{ + uint count = 0; + for (struct rte_storage *e = n->routes; e; e = e->next) + if (rte_is_valid(RTE_OR_NULL(e))) + count++; + return count; +} + +static void +rte_feed_obtain(net *n, struct rte **feed, uint count) +{ + uint i = 0; + for (struct rte_storage *e = n->routes; e; e = e->next) + if (rte_is_valid(RTE_OR_NULL(e))) + { + ASSERT_DIE(i < count); + feed[i++] = &e->rte; + } + ASSERT_DIE(i == count); +} + static rte * export_filter_(struct channel *c, rte *rt, linpool *pool, int silent) { @@ -523,81 +553,71 @@ rt_notify_basic(struct channel *c, const net_addr *net, rte *new, rte *old, int } static void -rt_notify_accepted(struct channel *c, net *net, rte *new_changed, rte *old_changed, int refeed) +rt_notify_accepted(struct channel *c, const net_addr *n, struct rt_pending_export *rpe, + struct rte **feed, uint count, int refeed) { - // struct proto *p = c->proto; - rte nb0; - rte *new_best = NULL; - rte *old_best = NULL; - int new_first = 0; - - /* - * We assume that there are no changes in net route order except (added) - * new_changed and (removed) old_changed. Therefore, the function is not - * compatible with deterministic_med (where nontrivial reordering can happen - * as a result of a route change) and with recomputation of recursive routes - * due to next hop update (where many routes can be changed in one step). - * - * Note that we need this assumption just for optimizations, we could just - * run full new_best recomputation otherwise. - * - * There are three cases: - * feed or old_best is old_changed -> we need to recompute new_best - * old_best is before new_changed -> new_best is old_best, ignore - * old_best is after new_changed -> try new_changed, otherwise old_best - */ - - if (net->routes) - c->export_stats.updates_received++; - else - c->export_stats.withdraws_received++; + rte nb0, *new_best = NULL, *old_best = NULL; - /* Find old_best - either old_changed, or route for net->routes */ - if (old_changed && bmap_test(&c->export_map, old_changed->id)) - old_best = old_changed; - else + for (uint i = 0; i < count; i++) { - for (struct rte_storage *r = net->routes; r && rte_is_valid(&r->rte); r = r->next) + if (!rte_is_valid(feed[i])) + continue; + + /* Has been already rejected, won't bother with it */ + if (!refeed && bmap_test(&c->export_reject_map, feed[i]->id)) + continue; + + /* Previously exported */ + if (!old_best && bmap_test(&c->export_map, feed[i]->id)) { - if (bmap_test(&c->export_map, r->rte.id)) + /* is still best */ + if (!new_best) { - old_best = &r->rte; - break; + DBG("rt_notify_accepted: idempotent\n"); + return; } - /* Note if new_changed found before old_best */ - if (&r->rte == new_changed) - new_first = 1; + /* is superseded */ + old_best = feed[i]; + break; + } + + /* Have no new best route yet */ + if (!new_best) + { + /* Try this route not seen before */ + nb0 = *feed[i]; + new_best = export_filter(c, &nb0, 0); + DBG("rt_notify_accepted: checking route id %u: %s\n", feed[i]->id, new_best ? "ok" : "no"); } } - /* Find new_best */ - if ((new_changed == old_changed) || (old_best == old_changed)) - { - /* Feed or old_best changed -> find first accepted by filters */ - for (struct rte_storage *r = net->routes; r && rte_is_valid(&r->rte); r = r->next) + /* Check obsolete routes for previously exported */ + if (!old_best) + if (rpe && rpe->old && bmap_test(&c->export_map, rpe->old->rte.id)) + old_best = &rpe->old->rte; + +/* for (; rpe; rpe = atomic_load_explicit(&rpe->next, memory_order_relaxed)) { - /* Already rejected before */ - if (!refeed && bmap_test(&c->export_reject_map, r->rte.id)) - continue; + if (rpe->old && bmap_test(&hook->accept_map, rpe->old->id)) + { + old_best = &rpe->old.rte; + break; + } - if (new_best = export_filter(c, ((nb0 = r->rte), &nb0), 0)) + if (rpe == rpe_last) break; } - } - else - { - /* Other cases -> either new_changed, or old_best (and nothing changed) */ - if (new_first && (new_changed = export_filter(c, new_changed, 0))) - new_best = new_changed; - else - return; - } + */ + /* Nothing to export */ if (!new_best && !old_best) + { + DBG("rt_notify_accepted: nothing to export\n"); return; + } - do_rt_notify(c, net->n.addr, new_best, old_best, refeed); + do_rt_notify(c, n, new_best, old_best, refeed); } @@ -607,36 +627,45 @@ nexthop_merge_rta(struct nexthop *nhs, rta *a, linpool *pool, int max) return nexthop_merge(nhs, &(a->nh), 1, 0, max, pool); } -rte * -rt_export_merged(struct channel *c, net *net, linpool *pool, int silent) +static rte * +rt_export_merged(struct channel *c, struct rte **feed, uint count, linpool *pool, int silent, int refeed) { + _Thread_local static rte rloc; + // struct proto *p = c->proto; struct nexthop *nhs = NULL; - _Thread_local static rte rme; - struct rte_storage *best0 = net->routes; - rte *best; + rte *best0 = feed[0], *best = NULL; - if (!best0 || !rte_is_valid(&best0->rte)) + if (!rte_is_valid(best0)) return NULL; - best = export_filter_(c, ((rme = best0->rte), &rme), pool, silent); + /* Already rejected, no need to re-run the filter */ + if (!refeed && bmap_test(&c->export_reject_map, best0->id)) + return NULL; + + rloc = *best0; + best = export_filter_(c, &rloc, pool, silent); + + if (!best) + /* Best route doesn't pass the filter */ + return NULL; - if (!best || !rte_is_reachable(best)) + if (!rte_is_reachable(best)) + /* Unreachable routes can't be merged */ return best; - for (struct rte_storage *rt0 = best0->next; rt0; rt0 = rt0->next) + for (uint i = 1; i < count; i++) { - if (!rte_mergable(best, &rt0->rte)) + if (!rte_mergable(best0, feed[i])) continue; - rte rnh = rt0->rte; - rte *rt = export_filter_(c, &rnh, pool, 1); + rte tmp0 = *feed[i]; + rte *tmp = export_filter_(c, &tmp0, pool, 1); - if (!rt) + if (!tmp || !rte_is_reachable(tmp)) continue; - if (rte_is_reachable(rt)) - nhs = nexthop_merge_rta(nhs, rt->attrs, pool, c->merge_limit); + nhs = nexthop_merge_rta(nhs, tmp->attrs, pool, c->merge_limit); } if (nhs) @@ -653,41 +682,77 @@ rt_export_merged(struct channel *c, net *net, linpool *pool, int silent) return best; } +rte * +rt_export_merged_show(struct channel *c, net *n, linpool *pool) +{ + uint count = rte_feed_count(n); + rte **feed = alloca(count * sizeof(rte *)); + rte_feed_obtain(n, feed, count); + return rt_export_merged(c, feed, count, pool, 1, 0); +} static void -rt_notify_merged(struct channel *c, net *net, rte *new_changed, rte *old_changed, - rte *new_best, rte *old_best, int refeed) +rt_notify_merged(struct channel *c, const net_addr *n, struct rt_pending_export *rpe, + struct rte **feed, uint count, int refeed) { - /* We assume that all rte arguments are either NULL or rte_is_valid() */ - - /* This check should be done by the caller */ - if (!new_best && !old_best) - return; + // struct proto *p = c->proto; +#if 0 /* TODO: Find whether this check is possible when processing multiple changes at once. */ /* Check whether the change is relevant to the merged route */ if ((new_best == old_best) && (new_changed != old_changed) && !rte_mergable(new_best, new_changed) && !rte_mergable(old_best, old_changed)) return; +#endif - if (new_best) - c->export_stats.updates_received++; - else - c->export_stats.withdraws_received++; + rte *old_best = NULL; + /* Find old best route */ + for (uint i = 0; i < count; i++) + if (bmap_test(&c->export_map, feed[i]->id)) + { + old_best = feed[i]; + break; + } - /* Prepare new merged route */ - if (new_best) - new_best = rt_export_merged(c, net, rte_update_pool, 0); + /* Check obsolete routes for previously exported */ + if (!old_best) + if (rpe && rpe->old && bmap_test(&c->export_map, rpe->old->rte.id)) + old_best = &rpe->old->rte; - /* Check old merged route */ - if (old_best && !bmap_test(&c->export_map, old_best->id)) - old_best = NULL; +/* for (; rpe; rpe = atomic_load_explicit(&rpe->next, memory_order_relaxed)) + { + if (rpe->old && bmap_test(&hook->accept_map, rpe->old->id)) + { + old_best = &rpe->old.rte; + break; + } - if (!new_best && !old_best) + if (rpe == rpe_last) + break; + } + */ + + /* Prepare new merged route */ + rte *new_merged = count ? rt_export_merged(c, feed, count, rte_update_pool, 0, refeed) : NULL; + + if (!new_merged && !old_best) return; - do_rt_notify(c, net->n.addr, new_best, old_best, refeed); + do_rt_notify(c, n, new_merged, old_best, refeed); +} + +static void +rt_notify_bulk(struct channel *c, const net_addr *n, struct rt_pending_export *rpe, + struct rte **feed, uint count, int refeed) +{ + switch (c->ra_mode) + { + case RA_ACCEPTED: + return rt_notify_accepted(c, n, rpe, feed, count, refeed); + case RA_MERGED: + return rt_notify_merged(c, n, rpe, feed, count, refeed); + } } @@ -774,12 +839,15 @@ rte_announce(rtable *tab, net *net, struct rte_storage *new, struct rte_storage break; case RA_ACCEPTED: - rt_notify_accepted(c, net, RTE_OR_NULL(new), RTE_OR_NULL(old), 0); - break; - case RA_MERGED: - rt_notify_merged(c, net, RTE_OR_NULL(new), RTE_OR_NULL(old), RTE_OR_NULL(new_best), RTE_OR_NULL(old_best), 0); - break; + { + struct rt_pending_export rpe = { .new = new, .old = old, .new_best = new_best, .old_best = old_best }; + uint count = rte_feed_count(net); + rte **feed = alloca(count * sizeof(rte *)); + rte_feed_obtain(net, feed, count); + rt_notify_bulk(c, net->n.addr, &rpe, feed, count, 0); + break; + } } /* Drop the old stored rejection if applicable. @@ -2127,10 +2195,13 @@ static inline void do_feed_channel(struct channel *c, net *n, rte *e) { rte_update_lock(); - if (c->ra_mode == RA_ACCEPTED) - rt_notify_accepted(c, n, NULL, NULL, c->refeeding); - else if (c->ra_mode == RA_MERGED) - rt_notify_merged(c, n, NULL, NULL, e, e, c->refeeding); + if ((c->ra_mode == RA_ACCEPTED) || (c->ra_mode == RA_MERGED)) + { + uint count = rte_feed_count(n); + rte **feed = alloca(count * sizeof(rte *)); + rte_feed_obtain(n, feed, count); + rt_notify_bulk(c, n->n.addr, NULL, feed, count, c->refeeding); + } else /* RA_BASIC */ { rte e0 = *e; diff --git a/sysdep/unix/krt.c b/sysdep/unix/krt.c index 0a746631..b98e7ec0 100644 --- a/sysdep/unix/krt.c +++ b/sysdep/unix/krt.c @@ -566,7 +566,7 @@ krt_export_net(struct krt_proto *p, net *net) const struct filter *filter = c->out_filter; if (c->ra_mode == RA_MERGED) - return rt_export_merged(c, net, krt_filter_lp, 1); + return rt_export_merged_show(c, net, krt_filter_lp); static _Thread_local rte rt; rt = net->routes->rte; |