static list routing_tables;
-static void rt_format_via(rte *e, byte *via);
+static byte *rt_format_via(rte *e);
static void rt_free_hostcache(rtable *tab);
static void rt_notify_hostcache(rtable *tab, net *net);
static void rt_update_hostcache(rtable *tab);
static void rt_next_hop_update(rtable *tab);
-static void rt_prune(rtable *tab);
-
+static inline int rt_prune_table(rtable *tab);
static inline void rt_schedule_gc(rtable *tab);
+static inline void rt_schedule_prune(rtable *tab);
+
/* Like fib_route(), but skips empty net entries */
static net *
{
a0 = ipa_and(a, ipa_mkmask(len));
n = fib_find(&tab->fib, &a0, len);
- if (n && n->routes)
+ if (n && rte_is_valid(n->routes))
return n;
len--;
}
/**
* rte_find - find a route
* @net: network node
- * @p: protocol
+ * @src: route source
*
* The rte_find() function returns a route for destination @net
- * which belongs has been defined by protocol @p.
+ * which is from route source @src.
*/
rte *
-rte_find(net *net, struct proto *p)
+rte_find(net *net, struct rte_src *src)
{
rte *e = net->routes;
- while (e && e->attrs->proto != p)
+ while (e && e->attrs->src != src)
e = e->next;
return e;
}
e->attrs = a;
e->flags = 0;
- e->pref = a->proto->preference;
+ e->pref = a->src->proto->preference;
return e;
}
return e;
}
+/**
+ * rte_cow_rta - get a private writable copy of &rte with writable &rta
+ * @r: a route entry to be copied
+ * @lp: a linpool from which to allocate &rta
+ *
+ * rte_cow_rta() takes a &rte and prepares it and associated &rta for
+ * modification. There are three possibilities: First, both &rte and &rta are
+ * private copies, in that case they are returned unchanged. Second, &rte is
+ * private copy, but &rta is cached, in that case &rta is duplicated using
+ * rta_do_cow(). Third, both &rte is shared and &rta is cached, in that case
+ * both structures are duplicated by rte_do_cow() and rta_do_cow().
+ *
+ * Note that in the second case, cached &rta loses one reference, while private
+ * copy created by rta_do_cow() is a shallow copy sharing indirect data (eattrs,
+ * nexthops, ...) with it. To work properly, original shared &rta should have
+ * another reference during the life of created private copy.
+ *
+ * Result: a pointer to the new writable &rte with writable &rta.
+ */
+rte *
+rte_cow_rta(rte *r, linpool *lp)
+{
+ if (!rta_is_cached(r->attrs))
+ return r;
+
+ rte *e = rte_cow(r);
+ rta *a = rta_do_cow(r->attrs, lp);
+ rta_free(e->attrs);
+ e->attrs = a;
+ return e;
+}
+
static int /* Actually better or at least as good as */
rte_better(rte *new, rte *old)
{
int (*better)(rte *, rte *);
- if (!old)
+ if (!rte_is_valid(old))
return 1;
+ if (!rte_is_valid(new))
+ return 0;
+
if (new->pref > old->pref)
return 1;
if (new->pref < old->pref)
return 0;
- if (new->attrs->proto->proto != old->attrs->proto->proto)
+ if (new->attrs->src->proto->proto != old->attrs->src->proto->proto)
{
/*
* If the user has configured protocol preferences, so that two different protocols
* have the same preference, try to break the tie by comparing addresses. Not too
* useful, but keeps the ordering of routes unambiguous.
*/
- return new->attrs->proto->proto > old->attrs->proto->proto;
+ return new->attrs->src->proto->proto > old->attrs->src->proto->proto;
}
- if (better = new->attrs->proto->rte_better)
+ if (better = new->attrs->src->proto->rte_better)
return better(new, old);
return 0;
}
+static int
+rte_mergable(rte *pri, rte *sec)
+{
+ int (*mergable)(rte *, rte *);
+
+ if (!rte_is_valid(pri) || !rte_is_valid(sec))
+ return 0;
+
+ if (pri->pref != sec->pref)
+ return 0;
+
+ if (pri->attrs->src->proto->proto != sec->attrs->src->proto->proto)
+ return 0;
+
+ if (mergable = pri->attrs->src->proto->rte_mergable)
+ return mergable(pri, sec);
+
+ return 0;
+}
+
static void
rte_trace(struct proto *p, rte *e, int dir, char *msg)
{
- byte via[STD_ADDRESS_P_LENGTH+32];
-
- rt_format_via(e, via);
- log(L_TRACE "%s %c %s %I/%d %s", p->name, dir, msg, e->net->n.prefix, e->net->n.pxlen, via);
+ log(L_TRACE "%s %c %s %I/%d %s", p->name, dir, msg, e->net->n.prefix, e->net->n.pxlen, rt_format_via(e));
}
static inline void
-rte_trace_in(unsigned int flag, struct proto *p, rte *e, char *msg)
+rte_trace_in(uint flag, struct proto *p, rte *e, char *msg)
{
if (p->debug & flag)
rte_trace(p, e, '>', msg);
}
static inline void
-rte_trace_out(unsigned int flag, struct proto *p, rte *e, char *msg)
+rte_trace_out(uint flag, struct proto *p, rte *e, char *msg)
{
if (p->debug & flag)
rte_trace(p, e, '<', msg);
}
-static inline void
-do_rte_announce(struct announce_hook *a, int type UNUSED, net *net, rte *new, rte *old, ea_list *tmpa, int refeed)
+static rte *
+export_filter_(struct announce_hook *ah, rte *rt0, rte **rt_free, ea_list **tmpa, linpool *pool, int silent)
{
- struct proto *p = a->proto;
- struct filter *filter = p->out_filter;
- struct proto_stats *stats = &p->stats;
- rte *new0 = new;
- rte *old0 = old;
- int ok;
+ struct proto *p = ah->proto;
+ struct filter *filter = ah->out_filter;
+ struct proto_stats *stats = ah->stats;
+ ea_list *tmpb = NULL;
+ rte *rt;
+ int v;
-#ifdef CONFIG_PIPE
- /* The secondary direction of the pipe */
- if (proto_is_pipe(p) && (p->table != a->table))
+ rt = rt0;
+ *rt_free = NULL;
+
+ if (!tmpa)
+ tmpa = &tmpb;
+
+ *tmpa = rte_make_tmp_attrs(rt, pool);
+
+ v = p->import_control ? p->import_control(p, &rt, tmpa, pool) : 0;
+ if (v < 0)
{
- filter = p->in_filter;
- stats = pipe_get_peer_stats(p);
+ if (silent)
+ goto reject;
+
+ stats->exp_updates_rejected++;
+ if (v == RIC_REJECT)
+ rte_trace_out(D_FILTERS, p, rt, "rejected by protocol");
+ goto reject;
+ }
+ if (v > 0)
+ {
+ if (!silent)
+ rte_trace_out(D_FILTERS, p, rt, "forced accept by protocol");
+ goto accept;
}
-#endif
- if (new)
+ v = filter && ((filter == FILTER_REJECT) ||
+ (f_run(filter, &rt, tmpa, pool, FF_FORCE_TMPATTR) > F_ACCEPT));
+ if (v)
{
- stats->exp_updates_received++;
+ if (silent)
+ goto reject;
- char *drop_reason = NULL;
- if ((ok = p->import_control ? p->import_control(p, &new, &tmpa, rte_update_pool) : 0) < 0)
- {
- stats->exp_updates_rejected++;
- drop_reason = "rejected by protocol";
- }
- else if (ok)
- rte_trace_out(D_FILTERS, p, new, "forced accept by protocol");
- else if ((filter == FILTER_REJECT) ||
- (filter && f_run(filter, &new, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
- {
- stats->exp_updates_filtered++;
- drop_reason = "filtered out";
- }
- if (drop_reason)
- {
- rte_trace_out(D_FILTERS, p, new, drop_reason);
- if (new != new0)
- rte_free(new);
- new = NULL;
- }
+ stats->exp_updates_filtered++;
+ rte_trace_out(D_FILTERS, p, rt, "filtered out");
+ goto reject;
}
- else
- stats->exp_withdraws_received++;
+
+ accept:
+ if (rt != rt0)
+ *rt_free = rt;
+ return rt;
+
+ reject:
+ /* Discard temporary rte */
+ if (rt != rt0)
+ rte_free(rt);
+ return NULL;
+}
+
+static inline rte *
+export_filter(struct announce_hook *ah, rte *rt0, rte **rt_free, ea_list **tmpa, int silent)
+{
+ return export_filter_(ah, rt0, rt_free, tmpa, rte_update_pool, silent);
+}
+
+static void
+do_rt_notify(struct announce_hook *ah, net *net, rte *new, rte *old, ea_list *tmpa, int refeed)
+{
+ struct proto *p = ah->proto;
+ struct proto_stats *stats = ah->stats;
+
/*
- * This is a tricky part - we don't know whether route 'old' was
- * exported to protocol 'p' or was filtered by the export filter.
- * We try tu run the export filter to know this to have a correct
- * value in 'old' argument of rte_update (and proper filter value)
+ * First, apply export limit.
*
- * FIXME - this is broken because 'configure soft' may change
- * filters but keep routes. Refeed is expected to be called after
- * change of the filters and with old == new, therefore we do not
- * even try to run the filter on an old route, This may lead to
- * 'spurious withdraws' but ensure that there are no 'missing
- * withdraws'.
+ * Export route limits has several problems. Because exp_routes
+ * counter is reset before refeed, we don't really know whether
+ * limit is breached and whether the update is new or not. Therefore
+ * the number of really exported routes may exceed the limit
+ * temporarily (routes exported before and new routes in refeed).
*
- * This is not completely safe as there is a window between
- * reconfiguration and the end of refeed - if a newly filtered
- * route disappears during this period, proper withdraw is not
- * sent (because old would be also filtered) and the route is
- * not refeeded (because it disappeared before that).
+ * Minor advantage is that if the limit is decreased and refeed is
+ * requested, the number of exported routes really decrease.
+ *
+ * Second problem is that with export limits, we don't know whether
+ * old was really exported (it might be blocked by limit). When a
+ * withdraw is exported, we announce it even when the previous
+ * update was blocked. This is not a big issue, but the same problem
+ * is in updating exp_routes counter. Therefore, to be consistent in
+ * increases and decreases of exp_routes, we count exported routes
+ * regardless of blocking by limits.
+ *
+ * Similar problem is in handling updates - when a new route is
+ * received and blocking is active, the route would be blocked, but
+ * when an update for the route will be received later, the update
+ * would be propagated (as old != NULL). Therefore, we have to block
+ * also non-new updates (contrary to import blocking).
*/
- if (old && !refeed)
+ struct proto_limit *l = ah->out_limit;
+ if (l && new)
{
- if (filter == FILTER_REJECT)
- old = NULL;
- else
+ if ((!old || refeed) && (stats->exp_routes >= l->limit))
+ proto_notify_limit(ah, l, PLD_OUT, stats->exp_routes);
+
+ if (l->state == PLS_BLOCKED)
{
- ea_list *tmpb = p->make_tmp_attrs ? p->make_tmp_attrs(old, rte_update_pool) : NULL;
- ok = p->import_control ? p->import_control(p, &old, &tmpb, rte_update_pool) : 0;
- if (ok < 0 || (!ok && filter && f_run(filter, &old, &tmpb, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
- {
- if (old != old0)
- rte_free(old);
- old = NULL;
- }
+ stats->exp_routes++; /* see note above */
+ stats->exp_updates_rejected++;
+ rte_trace_out(D_FILTERS, p, new, "rejected [limit]");
+ new = NULL;
+
+ if (!old)
+ return;
}
}
- /* FIXME - This is broken because of incorrect 'old' value (see above) */
- if (!new && !old)
- return;
if (new)
stats->exp_updates_accepted++;
rte_trace_out(D_ROUTES, p, old, "removed");
}
if (!new)
- p->rt_notify(p, a->table, net, NULL, old, NULL);
+ p->rt_notify(p, ah->table, net, NULL, old, NULL);
else if (tmpa)
{
ea_list *t = tmpa;
while (t->next)
t = t->next;
t->next = new->attrs->eattrs;
- p->rt_notify(p, a->table, net, new, old, tmpa);
+ p->rt_notify(p, ah->table, net, new, old, tmpa);
t->next = NULL;
}
else
- p->rt_notify(p, a->table, net, new, old, new->attrs->eattrs);
- if (new && new != new0) /* Discard temporary rte's */
- rte_free(new);
- if (old && old != old0)
- rte_free(old);
+ p->rt_notify(p, ah->table, net, new, old, new->attrs->eattrs);
+}
+
+static void
+rt_notify_basic(struct announce_hook *ah, net *net, rte *new0, rte *old0, int refeed)
+{
+ struct proto *p = ah->proto;
+ struct proto_stats *stats = ah->stats;
+
+ rte *new = new0;
+ rte *old = old0;
+ rte *new_free = NULL;
+ rte *old_free = NULL;
+ ea_list *tmpa = NULL;
+
+ if (new)
+ stats->exp_updates_received++;
+ else
+ stats->exp_withdraws_received++;
+
+ /*
+ * This is a tricky part - we don't know whether route 'old' was
+ * exported to protocol 'p' or was filtered by the export filter.
+ * We try to run the export filter to know this to have a correct
+ * value in 'old' argument of rte_update (and proper filter value)
+ *
+ * FIXME - this is broken because 'configure soft' may change
+ * filters but keep routes. Refeed is expected to be called after
+ * change of the filters and with old == new, therefore we do not
+ * even try to run the filter on an old route, This may lead to
+ * 'spurious withdraws' but ensure that there are no 'missing
+ * withdraws'.
+ *
+ * This is not completely safe as there is a window between
+ * reconfiguration and the end of refeed - if a newly filtered
+ * route disappears during this period, proper withdraw is not
+ * sent (because old would be also filtered) and the route is
+ * not refeeded (because it disappeared before that).
+ */
+
+ if (new)
+ new = export_filter(ah, new, &new_free, &tmpa, 0);
+
+ if (old && !refeed)
+ old = export_filter(ah, old, &old_free, NULL, 1);
+
+ if (!new && !old)
+ {
+ /*
+ * As mentioned above, 'old' value may be incorrect in some race conditions.
+ * We generally ignore it with the exception of withdraw to pipe protocol.
+ * In that case we rather propagate unfiltered withdraws regardless of
+ * export filters to ensure that when a protocol is flushed, its routes are
+ * removed from all tables. Possible spurious unfiltered withdraws are not
+ * problem here as they are ignored if there is no corresponding route at
+ * the other end of the pipe. We directly call rt_notify() hook instead of
+ * do_rt_notify() to avoid logging and stat counters.
+ */
+
+#ifdef CONFIG_PIPE
+ if ((p->proto == &proto_pipe) && !new0 && (p != old0->sender->proto))
+ p->rt_notify(p, ah->table, net, NULL, old0, NULL);
+#endif
+
+ return;
+ }
+
+ do_rt_notify(ah, net, new, old, tmpa, refeed);
+
+ /* Discard temporary rte's */
+ if (new_free)
+ rte_free(new_free);
+ if (old_free)
+ rte_free(old_free);
}
+static void
+rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *old_changed, rte *before_old, int feed)
+{
+ // struct proto *p = ah->proto;
+ struct proto_stats *stats = ah->stats;
+
+ rte *r;
+ rte *new_best = NULL;
+ rte *old_best = NULL;
+ rte *new_free = NULL;
+ rte *old_free = NULL;
+ ea_list *tmpa = NULL;
+
+ /* Used to track whether we met old_changed position. If before_old is NULL
+ old_changed was the first and we met it implicitly before current best route. */
+ int old_meet = old_changed && !before_old;
+
+ /* Note that before_old is either NULL or valid (not rejected) route.
+ If old_changed is valid, before_old have to be too. If old changed route
+ was not valid, caller must use NULL for both old_changed and before_old. */
+
+ if (new_changed)
+ stats->exp_updates_received++;
+ else
+ stats->exp_withdraws_received++;
+
+ /* First, find the new_best route - first accepted by filters */
+ for (r=net->routes; rte_is_valid(r); r=r->next)
+ {
+ if (new_best = export_filter(ah, r, &new_free, &tmpa, 0))
+ break;
+
+ /* Note if we walked around the position of old_changed route */
+ if (r == before_old)
+ old_meet = 1;
+ }
+
+ /*
+ * Second, handle the feed case. That means we do not care for
+ * old_best. It is NULL for feed, and the new_best for refeed.
+ * For refeed, there is a hack similar to one in rt_notify_basic()
+ * to ensure withdraws in case of changed filters
+ */
+ if (feed)
+ {
+ if (feed == 2) /* refeed */
+ old_best = new_best ? new_best :
+ (rte_is_valid(net->routes) ? net->routes : NULL);
+ else
+ old_best = NULL;
+
+ if (!new_best && !old_best)
+ return;
+
+ goto found;
+ }
+
+ /*
+ * Now, we find the old_best route. Generally, it is the same as the
+ * new_best, unless new_best is the same as new_changed or
+ * old_changed is accepted before new_best.
+ *
+ * There are four cases:
+ *
+ * - We would find and accept old_changed before new_best, therefore
+ * old_changed is old_best. In remaining cases we suppose this
+ * is not true.
+ *
+ * - We found no new_best, therefore there is also no old_best and
+ * we ignore this withdraw.
+ *
+ * - We found new_best different than new_changed, therefore
+ * old_best is the same as new_best and we ignore this update.
+ *
+ * - We found new_best the same as new_changed, therefore it cannot
+ * be old_best and we have to continue search for old_best.
+ */
+
+ /* First case */
+ if (old_meet)
+ if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1))
+ goto found;
+
+ /* Second case */
+ if (!new_best)
+ return;
+
+ /* Third case, we use r instead of new_best, because export_filter() could change it */
+ if (r != new_changed)
+ {
+ if (new_free)
+ rte_free(new_free);
+ return;
+ }
+
+ /* Fourth case */
+ for (r=r->next; rte_is_valid(r); r=r->next)
+ {
+ if (old_best = export_filter(ah, r, &old_free, NULL, 1))
+ goto found;
+
+ if (r == before_old)
+ if (old_best = export_filter(ah, old_changed, &old_free, NULL, 1))
+ goto found;
+ }
+
+ /* Implicitly, old_best is NULL and new_best is non-NULL */
+
+ found:
+ do_rt_notify(ah, net, new_best, old_best, tmpa, (feed == 2));
+
+ /* Discard temporary rte's */
+ if (new_free)
+ rte_free(new_free);
+ if (old_free)
+ rte_free(old_free);
+}
+
+
+static struct mpnh *
+mpnh_merge_rta(struct mpnh *nhs, rta *a, linpool *pool, int max)
+{
+ struct mpnh nh = { .gw = a->gw, .iface = a->iface };
+ struct mpnh *nh2 = (a->dest == RTD_MULTIPATH) ? a->nexthops : &nh;
+ return mpnh_merge(nhs, nh2, 1, 0, max, pool);
+}
+
+rte *
+rt_export_merged(struct announce_hook *ah, net *net, rte **rt_free, ea_list **tmpa, linpool *pool, int silent)
+{
+ // struct proto *p = ah->proto;
+ struct mpnh *nhs = NULL;
+ rte *best0, *best, *rt0, *rt, *tmp;
+
+ best0 = net->routes;
+ *rt_free = NULL;
+
+ if (!rte_is_valid(best0))
+ return NULL;
+
+ best = export_filter_(ah, best0, rt_free, tmpa, pool, silent);
+
+ if (!best || !rte_is_reachable(best))
+ return best;
+
+ for (rt0 = best0->next; rt0; rt0 = rt0->next)
+ {
+ if (!rte_mergable(best0, rt0))
+ continue;
+
+ rt = export_filter_(ah, rt0, &tmp, NULL, pool, 1);
+
+ if (!rt)
+ continue;
+
+ if (rte_is_reachable(rt))
+ nhs = mpnh_merge_rta(nhs, rt->attrs, pool, ah->proto->merge_limit);
+
+ if (tmp)
+ rte_free(tmp);
+ }
+
+ if (nhs)
+ {
+ nhs = mpnh_merge_rta(nhs, best->attrs, pool, ah->proto->merge_limit);
+
+ if (nhs->next)
+ {
+ best = rte_cow_rta(best, pool);
+ best->attrs->dest = RTD_MULTIPATH;
+ best->attrs->nexthops = nhs;
+ }
+ }
+
+ if (best != best0)
+ *rt_free = best;
+
+ return best;
+}
+
+
+static void
+rt_notify_merged(struct announce_hook *ah, net *net, rte *new_changed, rte *old_changed,
+ rte *new_best, rte*old_best, int refeed)
+{
+ // struct proto *p = ah->proto;
+
+ rte *new_best_free = NULL;
+ rte *old_best_free = NULL;
+ rte *new_changed_free = NULL;
+ rte *old_changed_free = NULL;
+ ea_list *tmpa = NULL;
+
+ /* 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;
+
+ /* Check whether the change is relevant to the merged route */
+ if ((new_best == old_best) && !refeed)
+ {
+ new_changed = rte_mergable(new_best, new_changed) ?
+ export_filter(ah, new_changed, &new_changed_free, NULL, 1) : NULL;
+
+ old_changed = rte_mergable(old_best, old_changed) ?
+ export_filter(ah, old_changed, &old_changed_free, NULL, 1) : NULL;
+
+ if (!new_changed && !old_changed)
+ return;
+ }
+
+ if (new_best)
+ ah->stats->exp_updates_received++;
+ else
+ ah->stats->exp_withdraws_received++;
+
+ /* Prepare new merged route */
+ if (new_best)
+ new_best = rt_export_merged(ah, net, &new_best_free, &tmpa, rte_update_pool, 0);
+
+ /* Prepare old merged route (without proper merged next hops) */
+ /* There are some issues with running filter on old route - see rt_notify_basic() */
+ if (old_best && !refeed)
+ old_best = export_filter(ah, old_best, &old_best_free, NULL, 1);
+
+ if (new_best || old_best)
+ do_rt_notify(ah, net, new_best, old_best, tmpa, refeed);
+
+ /* Discard temporary rte's */
+ if (new_best_free)
+ rte_free(new_best_free);
+ if (old_best_free)
+ rte_free(old_best_free);
+ if (new_changed_free)
+ rte_free(new_changed_free);
+ if (old_changed_free)
+ rte_free(old_changed_free);
+}
+
+
/**
* rte_announce - announce a routing table change
* @tab: table the route has been added to
* @net: network in question
* @new: the new route to be announced
* @old: the previous route for the same network
- * @tmpa: a list of temporary attributes belonging to the new route
+ * @new_best: the new best route for the same network
+ * @old_best: the previous best route for the same network
+ * @before_old: The previous route before @old for the same network.
+ * If @before_old is NULL @old was the first.
*
* This function gets a routing table update and announces it
* to all protocols that acccepts given type of route announcement
* and are connected to the same table by their announcement hooks.
*
- * Route announcement of type RA_OPTIMAL si generated when optimal
+ * Route announcement of type %RA_OPTIMAL si generated when optimal
* route (in routing table @tab) changes. In that case @old stores the
* old optimal route.
*
- * Route announcement of type RA_ANY si generated when any route (in
+ * Route announcement of type %RA_ANY si generated when any route (in
* routing table @tab) changes In that case @old stores the old route
* from the same protocol.
*
* the protocol gets called.
*/
static void
-rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old, ea_list *tmpa)
+rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old,
+ rte *new_best, rte *old_best, rte *before_old)
{
- struct announce_hook *a;
+ if (!rte_is_valid(new))
+ new = NULL;
+
+ if (!rte_is_valid(old))
+ old = before_old = NULL;
+
+ if (!rte_is_valid(new_best))
+ new_best = NULL;
+
+ if (!rte_is_valid(old_best))
+ old_best = NULL;
+
+ if (!old && !new)
+ return;
if (type == RA_OPTIMAL)
{
if (new)
- new->attrs->proto->stats.pref_routes++;
+ new->attrs->src->proto->stats.pref_routes++;
if (old)
- old->attrs->proto->stats.pref_routes--;
+ old->attrs->src->proto->stats.pref_routes--;
if (tab->hostcache)
rt_notify_hostcache(tab, net);
}
+ struct announce_hook *a;
WALK_LIST(a, tab->hooks)
{
- ASSERT(a->proto->core_state == FS_HAPPY || a->proto->core_state == FS_FEEDING);
+ ASSERT(a->proto->export_state != ES_DOWN);
if (a->proto->accept_ra_types == type)
- do_rte_announce(a, type, net, new, old, tmpa, 0);
+ if (type == RA_ACCEPTED)
+ rt_notify_accepted(a, net, new, old, before_old, 0);
+ else if (type == RA_MERGED)
+ rt_notify_merged(a, net, new, old, new_best, old_best, 0);
+ else
+ rt_notify_basic(a, net, new, old, 0);
}
}
-
static inline int
rte_validate(rte *e)
{
if ((n->n.pxlen > BITS_PER_IP_ADDRESS) || !ip_is_prefix(n->n.prefix,n->n.pxlen))
{
- log(L_BUG "Ignoring bogus prefix %I/%d received via %s",
- n->n.prefix, n->n.pxlen, e->sender->name);
+ log(L_WARN "Ignoring bogus prefix %I/%d received via %s",
+ n->n.prefix, n->n.pxlen, e->sender->proto->name);
return 0;
}
if ((c < 0) || !(c & IADDR_HOST) || ((c & IADDR_SCOPE_MASK) <= SCOPE_LINK))
{
log(L_WARN "Ignoring bogus route %I/%d received via %s",
- n->n.prefix, n->n.pxlen, e->sender->name);
+ n->n.prefix, n->n.pxlen, e->sender->proto->name);
+ return 0;
+ }
+
+ if ((e->attrs->dest == RTD_MULTIPATH) && !mpnh_is_sorted(e->attrs->nexthops))
+ {
+ log(L_WARN "Ignoring unsorted multipath route %I/%d received via %s",
+ n->n.prefix, n->n.pxlen, e->sender->proto->name);
return 0;
}
void
rte_free(rte *e)
{
- if (e->attrs->aflags & RTAF_CACHED)
+ if (rta_is_cached(e->attrs))
rta_free(e->attrs);
sl_free(rte_slab, e);
}
x->flags == y->flags &&
x->pflags == y->pflags &&
x->pref == y->pref &&
- (!x->attrs->proto->rte_same || x->attrs->proto->rte_same(x, y));
+ (!x->attrs->src->proto->rte_same || x->attrs->src->proto->rte_same(x, y));
}
+static inline int rte_is_ok(rte *e) { return e && !rte_is_filtered(e); }
+
static void
-rte_recalculate(rtable *table, net *net, struct proto *p, struct proto *src, rte *new, ea_list *tmpa)
+rte_recalculate(struct announce_hook *ah, net *net, rte *new, struct rte_src *src)
{
- struct proto_stats *stats = &p->stats;
+ struct proto *p = ah->proto;
+ struct rtable *table = ah->table;
+ struct proto_stats *stats = ah->stats;
+ static struct tbf rl_pipe = TBF_DEFAULT_LOG_LIMITS;
+ rte *before_old = NULL;
rte *old_best = net->routes;
rte *old = NULL;
- rte **k, *r, *s;
-
-#ifdef CONFIG_PIPE
- if (proto_is_pipe(p) && (p->table == table))
- stats = pipe_get_peer_stats(p);
-#endif
+ rte **k;
k = &net->routes; /* Find and remove original route from the same protocol */
while (old = *k)
{
- if (old->attrs->proto == src)
+ if (old->attrs->src == src)
{
/* If there is the same route in the routing table but from
* a different sender, then there are two paths from the
* ignore it completely (there might be 'spurious withdraws',
* see FIXME in do_rte_announce())
*/
- if (old->sender != p)
+ if (old->sender->proto != p)
{
if (new)
{
- log(L_ERR "Pipe collision detected when sending %I/%d to table %s",
+ log_rl(&rl_pipe, L_ERR "Pipe collision detected when sending %I/%d to table %s",
net->n.prefix, net->n.pxlen, table->name);
rte_free_quick(new);
}
if (new && rte_same(old, new))
{
/* No changes, ignore the new route */
- stats->imp_updates_ignored++;
- rte_trace_in(D_ROUTES, p, new, "ignored");
+
+ if (!rte_is_filtered(new))
+ {
+ stats->imp_updates_ignored++;
+ rte_trace_in(D_ROUTES, p, new, "ignored");
+ }
+
rte_free_quick(new);
-#ifdef CONFIG_RIP
- /* lastmod is used internally by RIP as the last time
- when the route was received. */
- if (src->proto == &proto_rip)
- old->lastmod = now;
-#endif
return;
}
*k = old->next;
break;
}
k = &old->next;
+ before_old = old;
}
+ if (!old)
+ before_old = NULL;
+
if (!old && !new)
{
stats->imp_withdraws_ignored++;
return;
}
- if (new)
+ int new_ok = rte_is_ok(new);
+ int old_ok = rte_is_ok(old);
+
+ struct proto_limit *l = ah->rx_limit;
+ if (l && !old && new)
+ {
+ u32 all_routes = stats->imp_routes + stats->filt_routes;
+
+ if (all_routes >= l->limit)
+ proto_notify_limit(ah, l, PLD_RX, all_routes);
+
+ if (l->state == PLS_BLOCKED)
+ {
+ /* In receive limit the situation is simple, old is NULL so
+ we just free new and exit like nothing happened */
+
+ stats->imp_updates_ignored++;
+ rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
+ rte_free_quick(new);
+ return;
+ }
+ }
+
+ l = ah->in_limit;
+ if (l && !old_ok && new_ok)
+ {
+ if (stats->imp_routes >= l->limit)
+ proto_notify_limit(ah, l, PLD_IN, stats->imp_routes);
+
+ if (l->state == PLS_BLOCKED)
+ {
+ /* In import limit the situation is more complicated. We
+ shouldn't just drop the route, we should handle it like
+ it was filtered. We also have to continue the route
+ processing if old or new is non-NULL, but we should exit
+ if both are NULL as this case is probably assumed to be
+ already handled. */
+
+ stats->imp_updates_ignored++;
+ rte_trace_in(D_FILTERS, p, new, "ignored [limit]");
+
+ if (ah->in_keep_filtered)
+ new->flags |= REF_FILTERED;
+ else
+ { rte_free_quick(new); new = NULL; }
+
+ /* Note that old && !new could be possible when
+ ah->in_keep_filtered changed in the recent past. */
+
+ if (!old && !new)
+ return;
+
+ new_ok = 0;
+ goto skip_stats1;
+ }
+ }
+
+ if (new_ok)
stats->imp_updates_accepted++;
- else
+ else if (old_ok)
stats->imp_withdraws_accepted++;
+ else
+ stats->imp_withdraws_ignored++;
+
+ skip_stats1:
if (new)
- stats->imp_routes++;
+ rte_is_filtered(new) ? stats->filt_routes++ : stats->imp_routes++;
if (old)
- stats->imp_routes--;
-
- rte_announce(table, RA_ANY, net, new, old, tmpa);
+ rte_is_filtered(old) ? stats->filt_routes-- : stats->imp_routes--;
- if (new && rte_better(new, old_best))
+ if (table->config->sorted)
{
- /* The first case - the new route is cleary optimal, we link it
- at the first position and announce it */
+ /* If routes are sorted, just insert new route to appropriate position */
+ if (new)
+ {
+ if (before_old && !rte_better(new, before_old))
+ k = &before_old->next;
+ else
+ k = &net->routes;
- rte_trace_in(D_ROUTES, p, new, "added [best]");
- rte_announce(table, RA_OPTIMAL, net, new, old_best, tmpa);
- new->next = net->routes;
- net->routes = new;
+ for (; *k; k=&(*k)->next)
+ if (rte_better(new, *k))
+ break;
+
+ new->next = *k;
+ *k = new;
+ }
}
- else if (old == old_best)
+ else
{
- /* The second case - the old best route disappeared, we add the
- new route (if we have any) to the list (we don't care about
- position) and then we elect the new optimal route and relink
- that route at the first position and announce it. New optimal
- route might be NULL if there is no more routes */
+ /* If routes are not sorted, find the best route and move it on
+ the first position. There are several optimized cases. */
- /* Add the new route to the list */
- if (new)
+ if (src->proto->rte_recalculate && src->proto->rte_recalculate(table, net, new, old, old_best))
+ goto do_recalculate;
+
+ if (new && rte_better(new, old_best))
{
- rte_trace_in(D_ROUTES, p, new, "added");
+ /* The first case - the new route is cleary optimal,
+ we link it at the first position */
+
new->next = net->routes;
net->routes = new;
}
-
- /* Find new optimal route */
- r = NULL;
- for (s=net->routes; s; s=s->next)
- if (rte_better(s, r))
- r = s;
-
- /* Announce optimal route */
- rte_announce(table, RA_OPTIMAL, net, r, old_best, tmpa);
-
- /* And relink it (if there is any) */
- if (r)
+ else if (old == old_best)
{
- k = &net->routes;
- while (s = *k)
+ /* The second case - the old best route disappeared, we add the
+ new route (if we have any) to the list (we don't care about
+ position) and then we elect the new optimal route and relink
+ that route at the first position and announce it. New optimal
+ route might be NULL if there is no more routes */
+
+ do_recalculate:
+ /* Add the new route to the list */
+ if (new)
{
- if (s == r)
- {
- *k = r->next;
- break;
- }
- k = &s->next;
+ new->next = net->routes;
+ net->routes = new;
+ }
+
+ /* Find a new optimal route (if there is any) */
+ if (net->routes)
+ {
+ rte **bp = &net->routes;
+ for (k=&(*bp)->next; *k; k=&(*k)->next)
+ if (rte_better(*k, *bp))
+ bp = k;
+
+ /* And relink it */
+ rte *best = *bp;
+ *bp = best->next;
+ best->next = net->routes;
+ net->routes = best;
}
- r->next = net->routes;
- net->routes = r;
}
- else if (table->gc_counter++ >= table->config->gc_max_ops &&
- table->gc_time + table->config->gc_min_time <= now)
- rt_schedule_gc(table);
- }
- else if (new)
- {
- /* The third case - the new route is not better than the old
- best route (therefore old_best != NULL) and the old best
- route was not removed (therefore old_best == net->routes).
- We just link the new route after the old best route. */
-
- ASSERT(net->routes != NULL);
- new->next = net->routes->next;
- net->routes->next = new;
- rte_trace_in(D_ROUTES, p, new, "added");
+ else if (new)
+ {
+ /* The third case - the new route is not better than the old
+ best route (therefore old_best != NULL) and the old best
+ route was not removed (therefore old_best == net->routes).
+ We just link the new route after the old best route. */
+
+ ASSERT(net->routes != NULL);
+ new->next = net->routes->next;
+ net->routes->next = new;
+ }
+ /* The fourth (empty) case - suboptimal route was removed, nothing to do */
}
- /* Log the route removal */
- if (!new && old && (p->debug & D_ROUTES))
+ if (new)
+ new->lastmod = now;
+
+ /* Log the route change */
+ if (p->debug & D_ROUTES)
{
- if (old != old_best)
- rte_trace_in(D_ROUTES, p, old, "removed");
- else if (net->routes)
- rte_trace_in(D_ROUTES, p, old, "removed [replaced]");
- else
- rte_trace_in(D_ROUTES, p, old, "removed [sole]");
+ if (new_ok)
+ rte_trace(p, new, '>', new == net->routes ? "added [best]" : "added");
+ else if (old_ok)
+ {
+ if (old != old_best)
+ rte_trace(p, old, '>', "removed");
+ else if (rte_is_ok(net->routes))
+ rte_trace(p, old, '>', "removed [replaced]");
+ else
+ rte_trace(p, old, '>', "removed [sole]");
+ }
}
+ /* Propagate the route change */
+ rte_announce(table, RA_ANY, net, new, old, NULL, NULL, NULL);
+ if (net->routes != old_best)
+ rte_announce(table, RA_OPTIMAL, net, net->routes, old_best, NULL, NULL, NULL);
+ if (table->config->sorted)
+ rte_announce(table, RA_ACCEPTED, net, new, old, NULL, NULL, before_old);
+ rte_announce(table, RA_MERGED, net, new, old, net->routes, old_best, NULL);
+
+ if (!net->routes &&
+ (table->gc_counter++ >= table->config->gc_max_ops) &&
+ (table->gc_time + table->config->gc_min_time <= now))
+ rt_schedule_gc(table);
+
+ if (old_ok && p->rte_remove)
+ p->rte_remove(net, old);
+ if (new_ok && p->rte_insert)
+ p->rte_insert(net, new);
+
if (old)
- {
- if (p->rte_remove)
- p->rte_remove(net, old);
- rte_free_quick(old);
- }
- if (new)
- {
- new->lastmod = now;
- if (p->rte_insert)
- p->rte_insert(net, new);
- }
+ rte_free_quick(old);
}
static int rte_update_nest_cnt; /* Nesting counter to allow recursive updates */
lp_flush(rte_update_pool);
}
+static inline void
+rte_hide_dummy_routes(net *net, rte **dummy)
+{
+ if (net->routes && net->routes->attrs->source == RTS_DUMMY)
+ {
+ *dummy = net->routes;
+ net->routes = (*dummy)->next;
+ }
+}
+
+static inline void
+rte_unhide_dummy_routes(net *net, rte **dummy)
+{
+ if (*dummy)
+ {
+ (*dummy)->next = net->routes;
+ net->routes = *dummy;
+ }
+}
+
/**
* rte_update - enter a new update to a routing table
* @table: table to be updated
+ * @ah: pointer to table announce hook
* @net: network node
* @p: protocol submitting the update
* @src: protocol originating the update
*/
void
-rte_update(rtable *table, net *net, struct proto *p, struct proto *src, rte *new)
+rte_update2(struct announce_hook *ah, net *net, rte *new, struct rte_src *src)
{
+ struct proto *p = ah->proto;
+ struct proto_stats *stats = ah->stats;
+ struct filter *filter = ah->in_filter;
ea_list *tmpa = NULL;
- struct proto_stats *stats = &p->stats;
-
-#ifdef CONFIG_PIPE
- if (proto_is_pipe(p) && (p->table == table))
- stats = pipe_get_peer_stats(p);
-#endif
+ rte *dummy = NULL;
rte_update_lock();
if (new)
{
- new->sender = p;
- struct filter *filter = p->in_filter;
-
- /* Do not filter routes going through the pipe,
- they are filtered in the export filter only. */
-#ifdef CONFIG_PIPE
- if (proto_is_pipe(p))
- filter = FILTER_ACCEPT;
-#endif
+ new->sender = ah;
stats->imp_updates_received++;
if (!rte_validate(new))
stats->imp_updates_invalid++;
goto drop;
}
+
if (filter == FILTER_REJECT)
{
stats->imp_updates_filtered++;
rte_trace_in(D_FILTERS, p, new, "filtered out");
- goto drop;
+
+ if (! ah->in_keep_filtered)
+ goto drop;
+
+ /* new is a private copy, i could modify it */
+ new->flags |= REF_FILTERED;
}
- if (src->make_tmp_attrs)
- tmpa = src->make_tmp_attrs(new, rte_update_pool);
- if (filter)
+ else
{
- ea_list *old_tmpa = tmpa;
- int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
- if (fr > F_ACCEPT)
+ tmpa = rte_make_tmp_attrs(new, rte_update_pool);
+ if (filter && (filter != FILTER_REJECT))
{
- stats->imp_updates_filtered++;
- rte_trace_in(D_FILTERS, p, new, "filtered out");
- goto drop;
+ ea_list *old_tmpa = tmpa;
+ int fr = f_run(filter, &new, &tmpa, rte_update_pool, 0);
+ if (fr > F_ACCEPT)
+ {
+ stats->imp_updates_filtered++;
+ rte_trace_in(D_FILTERS, p, new, "filtered out");
+
+ if (! ah->in_keep_filtered)
+ goto drop;
+
+ new->flags |= REF_FILTERED;
+ }
+ if (tmpa != old_tmpa && src->proto->store_tmp_attrs)
+ src->proto->store_tmp_attrs(new, tmpa);
}
- if (tmpa != old_tmpa && src->store_tmp_attrs)
- src->store_tmp_attrs(new, tmpa);
}
- if (!(new->attrs->aflags & RTAF_CACHED)) /* Need to copy attributes */
+ if (!rta_is_cached(new->attrs)) /* Need to copy attributes */
new->attrs = rta_lookup(new->attrs);
new->flags |= REF_COW;
}
else
- stats->imp_withdraws_received++;
+ {
+ stats->imp_withdraws_received++;
+
+ if (!net || !src)
+ {
+ stats->imp_withdraws_ignored++;
+ rte_update_unlock();
+ return;
+ }
+ }
- rte_recalculate(table, net, p, src, new, tmpa);
+ recalc:
+ rte_hide_dummy_routes(net, &dummy);
+ rte_recalculate(ah, net, new, src);
+ rte_unhide_dummy_routes(net, &dummy);
rte_update_unlock();
return;
-drop:
+ drop:
rte_free(new);
- rte_recalculate(table, net, p, src, NULL, NULL);
- rte_update_unlock();
+ new = NULL;
+ goto recalc;
}
/* Independent call to rte_announce(), used from next hop
recalculation, outside of rte_update(). new must be non-NULL */
static inline void
-rte_announce_i(rtable *tab, unsigned type, net *n, rte *new, rte *old)
+rte_announce_i(rtable *tab, unsigned type, net *net, rte *new, rte *old,
+ rte *new_best, rte *old_best)
{
- struct proto *src;
- ea_list *tmpa;
+ rte_update_lock();
+ rte_announce(tab, type, net, new, old, new_best, old_best, NULL);
+ rte_update_unlock();
+}
+static inline void
+rte_discard(rte *old) /* Non-filtered route deletion, used during garbage collection */
+{
rte_update_lock();
- src = new->attrs->proto;
- tmpa = src->make_tmp_attrs ? src->make_tmp_attrs(new, rte_update_pool) : NULL;
- rte_announce(tab, type, n, new, old, tmpa);
+ rte_recalculate(old->sender, old->net, NULL, old->attrs->src);
rte_update_unlock();
}
-void
-rte_discard(rtable *t, rte *old) /* Non-filtered route deletion, used during garbage collection */
+/* Check rtable for best route to given net whether it would be exported do p */
+int
+rt_examine(rtable *t, ip_addr prefix, int pxlen, struct proto *p, struct filter *filter)
{
+ net *n = net_find(t, prefix, pxlen);
+ rte *rt = n ? n->routes : NULL;
+
+ if (!rte_is_valid(rt))
+ return 0;
+
rte_update_lock();
- rte_recalculate(t, old->net, old->sender, old->attrs->proto, NULL, NULL);
+
+ /* Rest is stripped down export_filter() */
+ ea_list *tmpa = rte_make_tmp_attrs(rt, rte_update_pool);
+ int v = p->import_control ? p->import_control(p, &rt, &tmpa, rte_update_pool) : 0;
+ if (v == RIC_PROCESS)
+ v = (f_run(filter, &rt, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
+
+ /* Discard temporary rte */
+ if (rt != n->routes)
+ rte_free(rt);
+
rte_update_unlock();
+
+ return v > 0;
+}
+
+
+/**
+ * rt_refresh_begin - start a refresh cycle
+ * @t: related routing table
+ * @ah: related announce hook
+ *
+ * This function starts a refresh cycle for given routing table and announce
+ * hook. The refresh cycle is a sequence where the protocol sends all its valid
+ * routes to the routing table (by rte_update()). After that, all protocol
+ * routes (more precisely routes with @ah as @sender) not sent during the
+ * refresh cycle but still in the table from the past are pruned. This is
+ * implemented by marking all related routes as stale by REF_STALE flag in
+ * rt_refresh_begin(), then marking all related stale routes with REF_DISCARD
+ * flag in rt_refresh_end() and then removing such routes in the prune loop.
+ */
+void
+rt_refresh_begin(rtable *t, struct announce_hook *ah)
+{
+ net *n;
+ rte *e;
+
+ FIB_WALK(&t->fib, fn)
+ {
+ n = (net *) fn;
+ for (e = n->routes; e; e = e->next)
+ if (e->sender == ah)
+ e->flags |= REF_STALE;
+ }
+ FIB_WALK_END;
+}
+
+/**
+ * rt_refresh_end - end a refresh cycle
+ * @t: related routing table
+ * @ah: related announce hook
+ *
+ * This function starts a refresh cycle for given routing table and announce
+ * hook. See rt_refresh_begin() for description of refresh cycles.
+ */
+void
+rt_refresh_end(rtable *t, struct announce_hook *ah)
+{
+ int prune = 0;
+ net *n;
+ rte *e;
+
+ FIB_WALK(&t->fib, fn)
+ {
+ n = (net *) fn;
+ for (e = n->routes; e; e = e->next)
+ if ((e->sender == ah) && (e->flags & REF_STALE))
+ {
+ e->flags |= REF_DISCARD;
+ prune = 1;
+ }
+ }
+ FIB_WALK_END;
+
+ if (prune)
+ rt_schedule_prune(t);
}
+
/**
* rte_dump - dump a route
* @e: &rte to be dumped
rte_dump(rte *e)
{
net *n = e->net;
- if (n)
- debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
- else
- debug("??? ");
+ debug("%-1I/%2d ", n->n.prefix, n->n.pxlen);
debug("KF=%02x PF=%02x pref=%d lm=%d ", n->n.flags, e->pflags, e->pref, now-e->lastmod);
rta_dump(e->attrs);
- if (e->attrs->proto->proto->dump_attrs)
- e->attrs->proto->proto->dump_attrs(e);
+ if (e->attrs->src->proto->proto->dump_attrs)
+ e->attrs->src->proto->proto->dump_attrs(e);
debug("\n");
}
rt_dump(t);
}
+static inline void
+rt_schedule_prune(rtable *tab)
+{
+ rt_mark_for_prune(tab);
+ ev_schedule(tab->rt_event);
+}
+
static inline void
rt_schedule_gc(rtable *tab)
{
tab->nhu_state |= 1;
}
+
+static void
+rt_prune_nets(rtable *tab)
+{
+ struct fib_iterator fit;
+ int ncnt = 0, ndel = 0;
+
+#ifdef DEBUGGING
+ fib_check(&tab->fib);
+#endif
+
+ FIB_ITERATE_INIT(&fit, &tab->fib);
+again:
+ FIB_ITERATE_START(&tab->fib, &fit, f)
+ {
+ net *n = (net *) f;
+ ncnt++;
+ if (!n->routes) /* Orphaned FIB entry */
+ {
+ FIB_ITERATE_PUT(&fit, f);
+ fib_delete(&tab->fib, f);
+ ndel++;
+ goto again;
+ }
+ }
+ FIB_ITERATE_END(f);
+ DBG("Pruned %d of %d networks\n", ndel, ncnt);
+
+ tab->gc_counter = 0;
+ tab->gc_time = now;
+ tab->gc_scheduled = 0;
+}
+
static void
rt_event(void *ptr)
{
if (tab->nhu_state)
rt_next_hop_update(tab);
+ if (tab->prune_state)
+ if (!rt_prune_table(tab))
+ {
+ /* Table prune unfinished */
+ ev_schedule(tab->rt_event);
+ return;
+ }
+
if (tab->gc_scheduled)
- rt_prune(tab);
+ {
+ rt_prune_nets(tab);
+ rt_prune_sources(); // FIXME this should be moved to independent event
+ }
}
void
init_list(&routing_tables);
}
-/**
- * rt_prune - prune a routing table
- * @tab: routing table to be pruned
- *
- * This function is called whenever a protocol shuts down. It scans
- * the routing table and removes all routes belonging to inactive
- * protocols and also stale network entries.
- */
-static void
-rt_prune(rtable *tab)
+
+static int
+rt_prune_step(rtable *tab, int *limit)
{
- struct fib_iterator fit;
- int rcnt = 0, rdel = 0, ncnt = 0, ndel = 0;
+ struct fib_iterator *fit = &tab->prune_fit;
DBG("Pruning route table %s\n", tab->name);
#ifdef DEBUGGING
fib_check(&tab->fib);
#endif
- FIB_ITERATE_INIT(&fit, &tab->fib);
+
+ if (tab->prune_state == RPS_NONE)
+ return 1;
+
+ if (tab->prune_state == RPS_SCHEDULED)
+ {
+ FIB_ITERATE_INIT(fit, &tab->fib);
+ tab->prune_state = RPS_RUNNING;
+ }
+
again:
- FIB_ITERATE_START(&tab->fib, &fit, f)
+ FIB_ITERATE_START(&tab->fib, fit, fn)
{
- net *n = (net *) f;
+ net *n = (net *) fn;
rte *e;
- ncnt++;
+
rescan:
- for (e=n->routes; e; e=e->next, rcnt++)
- if (e->sender->core_state != FS_HAPPY &&
- e->sender->core_state != FS_FEEDING)
+ for (e=n->routes; e; e=e->next)
+ if (e->sender->proto->flushing || (e->flags & REF_DISCARD))
{
- rte_discard(tab, e);
- rdel++;
+ if (*limit <= 0)
+ {
+ FIB_ITERATE_PUT(fit, fn);
+ return 0;
+ }
+
+ rte_discard(e);
+ (*limit)--;
+
goto rescan;
}
- if (!n->routes) /* Orphaned FIB entry? */
+ if (!n->routes) /* Orphaned FIB entry */
{
- FIB_ITERATE_PUT(&fit, f);
- fib_delete(&tab->fib, f);
- ndel++;
+ FIB_ITERATE_PUT(fit, fn);
+ fib_delete(&tab->fib, fn);
goto again;
}
}
- FIB_ITERATE_END(f);
- DBG("Pruned %d of %d routes and %d of %d networks\n", rdel, rcnt, ndel, ncnt);
+ FIB_ITERATE_END(fn);
+
#ifdef DEBUGGING
fib_check(&tab->fib);
#endif
- tab->gc_counter = 0;
- tab->gc_time = now;
- tab->gc_scheduled = 0;
+
+ tab->prune_state = RPS_NONE;
+ return 1;
+}
+
+/**
+ * rt_prune_table - prune a routing table
+ * @tab: a routing table for pruning
+ *
+ * This function scans the routing table @tab and removes routes belonging to
+ * flushing protocols, discarded routes and also stale network entries, in a
+ * similar fashion like rt_prune_loop(). Returns 1 when all such routes are
+ * pruned. Contrary to rt_prune_loop(), this function is not a part of the
+ * protocol flushing loop, but it is called from rt_event() for just one routing
+ * table.
+ *
+ * Note that rt_prune_table() and rt_prune_loop() share (for each table) the
+ * prune state (@prune_state) and also the pruning iterator (@prune_fit).
+ */
+static inline int
+rt_prune_table(rtable *tab)
+{
+ int limit = 512;
+ return rt_prune_step(tab, &limit);
}
/**
- * rt_prune_all - prune all routing tables
+ * rt_prune_loop - prune routing tables
*
- * This function calls rt_prune() for all known routing tables.
+ * The prune loop scans routing tables and removes routes belonging to flushing
+ * protocols, discarded routes and also stale network entries. Returns 1 when
+ * all such routes are pruned. It is a part of the protocol flushing loop.
*/
-void
-rt_prune_all(void)
+int
+rt_prune_loop(void)
{
+ int limit = 512;
rtable *t;
WALK_LIST(t, routing_tables)
- rt_prune(t);
+ if (! rt_prune_step(t, &limit))
+ return 0;
+
+ return 1;
}
void
rt_preconfig(struct config *c)
{
- struct symbol *s = cf_find_symbol("master");
+ struct symbol *s = cf_get_symbol("master");
init_list(&c->tables);
c->master_rtc = rt_new_table(s);
}
static inline rte *
-rt_next_hop_update_rte(rtable *tab, rte *old)
+rt_next_hop_update_rte(rtable *tab UNUSED, rte *old)
{
rta a;
memcpy(&a, old->attrs, sizeof(rta));
if (!old_best)
return 0;
- new_best = NULL;
-
for (k = &n->routes; e = *k; k = &e->next)
- {
- if (rta_next_hop_outdated(e->attrs))
- {
- new = rt_next_hop_update_rte(tab, e);
- *k = new;
+ if (rta_next_hop_outdated(e->attrs))
+ {
+ new = rt_next_hop_update_rte(tab, e);
+ *k = new;
- rte_announce_i(tab, RA_ANY, n, new, e);
- rte_trace_in(D_ROUTES, new->sender, new, "updated");
+ rte_announce_i(tab, RA_ANY, n, new, e, NULL, NULL);
+ rte_trace_in(D_ROUTES, new->sender->proto, new, "updated");
- if (e != old_best)
- rte_free_quick(e);
- else /* Freeing of the old best rte is postponed */
- free_old_best = 1;
+ /* Call a pre-comparison hook */
+ /* Not really an efficient way to compute this */
+ if (e->attrs->src->proto->rte_recalculate)
+ e->attrs->src->proto->rte_recalculate(tab, n, new, e, NULL);
- e = new;
- count++;
- }
+ if (e != old_best)
+ rte_free_quick(e);
+ else /* Freeing of the old best rte is postponed */
+ free_old_best = 1;
+
+ e = new;
+ count++;
+ }
+
+ if (!count)
+ return 0;
+ /* Find the new best route */
+ new_best = NULL;
+ for (k = &n->routes; e = *k; k = &e->next)
+ {
if (!new_best || rte_better(e, *new_best))
new_best = k;
}
/* Announce the new best route */
if (new != old_best)
{
- rte_announce_i(tab, RA_OPTIMAL, n, new, old_best);
- rte_trace_in(D_ROUTES, new->sender, new, "updated [best]");
+ rte_announce_i(tab, RA_OPTIMAL, n, new, old_best, NULL, NULL);
+ rte_trace_in(D_ROUTES, new->sender->proto, new, "updated [best]");
}
- if (free_old_best)
+ /* FIXME: Better announcement of merged routes */
+ rte_announce_i(tab, RA_MERGED, n, new, old_best, new, old_best);
+
+ if (free_old_best)
rte_free_quick(old_best);
return count;
struct rtable_config *
rt_new_table(struct symbol *s)
{
+ /* Hack that allows to 'redefine' the master table */
+ if ((s->class == SYM_TABLE) && (s->def == new_config->master_rtc))
+ return s->def;
+
struct rtable_config *c = cfg_allocz(sizeof(struct rtable_config));
cf_define_symbol(s, SYM_TABLE, c);
{
struct config *conf = r->deleted;
DBG("Deleting routing table %s\n", r->name);
+ r->config->table = NULL;
if (r->hostcache)
rt_free_hostcache(r);
rem_node(&r->n);
rtable *ot = o->table;
if (!ot->deleted)
{
- struct symbol *sym = cf_find_symbol(o->name);
+ struct symbol *sym = cf_find_symbol(new, o->name);
if (sym && sym->class == SYM_TABLE && !new->shutdown)
{
DBG("\t%s: same\n", o->name);
r->table = ot;
ot->name = r->name;
ot->config = r;
+ if (o->sorted != r->sorted)
+ log(L_WARN "Reconfiguration of rtable sorted flag not implemented");
}
else
{
static inline void
do_feed_baby(struct proto *p, int type, struct announce_hook *h, net *n, rte *e)
{
- struct proto *q = e->attrs->proto;
- ea_list *tmpa;
-
rte_update_lock();
- tmpa = q->make_tmp_attrs ? q->make_tmp_attrs(e, rte_update_pool) : NULL;
- do_rte_announce(h, type, n, e, p->refeeding ? e : NULL, tmpa, p->refeeding);
+ if (type == RA_ACCEPTED)
+ rt_notify_accepted(h, n, e, NULL, NULL, p->refeeding ? 2 : 1);
+ else if (type == RA_MERGED)
+ rt_notify_merged(h, n, NULL, NULL, e, p->refeeding ? e : NULL, p->refeeding);
+ else
+ rt_notify_basic(h, n, e, p->refeeding ? e : NULL, p->refeeding);
rte_update_unlock();
}
return 0;
}
- if (p->accept_ra_types == RA_OPTIMAL)
- if (e)
+ /* XXXX perhaps we should change feed for RA_ACCEPTED to not use 'new' */
+
+ if ((p->accept_ra_types == RA_OPTIMAL) ||
+ (p->accept_ra_types == RA_ACCEPTED) ||
+ (p->accept_ra_types == RA_MERGED))
+ if (rte_is_valid(e))
{
- if (p->core_state != FS_FEEDING)
+ if (p->export_state != ES_FEEDING)
return 1; /* In the meantime, the protocol fell down. */
- do_feed_baby(p, RA_OPTIMAL, h, n, e);
+
+ do_feed_baby(p, p->accept_ra_types, h, n, e);
max_feed--;
}
if (p->accept_ra_types == RA_ANY)
- for(e = n->routes; e != NULL; e = e->next)
+ for(e = n->routes; e; e = e->next)
{
- if (p->core_state != FS_FEEDING)
+ if (p->export_state != ES_FEEDING)
return 1; /* In the meantime, the protocol fell down. */
+
+ if (!rte_is_valid(e))
+ continue;
+
do_feed_baby(p, RA_ANY, h, n, e);
max_feed--;
}
static inline void
hc_insert(struct hostcache *hc, struct hostentry *he)
{
- unsigned int k = he->hash_key >> hc->hash_shift;
+ uint k = he->hash_key >> hc->hash_shift;
he->next = hc->hash_table[k];
hc->hash_table[k] = he;
}
hc_remove(struct hostcache *hc, struct hostentry *he)
{
struct hostentry **hep;
- unsigned int k = he->hash_key >> hc->hash_shift;
+ uint k = he->hash_key >> hc->hash_shift;
for (hep = &hc->hash_table[k]; *hep != he; hep = &(*hep)->next);
*hep = he->next;
static void
hc_alloc_table(struct hostcache *hc, unsigned order)
{
- unsigned hsize = 1 << order;
+ uint hsize = 1 << order;
hc->hash_order = order;
hc->hash_shift = 16 - order;
- hc->hash_max = (order >= HC_HI_ORDER) ? ~0 : (hsize HC_HI_MARK);
- hc->hash_min = (order <= HC_LO_ORDER) ? 0 : (hsize HC_LO_MARK);
+ hc->hash_max = (order >= HC_HI_ORDER) ? ~0U : (hsize HC_HI_MARK);
+ hc->hash_min = (order <= HC_LO_ORDER) ? 0U : (hsize HC_LO_MARK);
hc->hash_table = mb_allocz(rt_table_pool, hsize * sizeof(struct hostentry *));
}
static void
hc_resize(struct hostcache *hc, unsigned new_order)
{
- unsigned old_size = 1 << hc->hash_order;
struct hostentry **old_table = hc->hash_table;
struct hostentry *he, *hen;
- int i;
+ uint old_size = 1 << hc->hash_order;
+ uint i;
hc_alloc_table(hc, new_order);
for (i = 0; i < old_size; i++)
hc->slab = sl_new(rt_table_pool, sizeof(struct hostentry));
hc->lp = lp_new(rt_table_pool, 1008);
- hc->trie = f_new_trie(hc->lp);
+ hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
tab->hostcache = hc;
}
return ea->u.data;
rta *a = rt->attrs;
+
+#ifdef CONFIG_OSPF
if ((a->source == RTS_OSPF) ||
(a->source == RTS_OSPF_IA) ||
(a->source == RTS_OSPF_EXT1))
return rt->u.ospf.metric1;
+#endif
+#ifdef CONFIG_RIP
if (a->source == RTS_RIP)
return rt->u.rip.metric;
+#endif
/* Device routes */
if ((a->dest != RTD_ROUTER) && (a->dest != RTD_MULTIPATH))
net *n = net_route(tab, he->addr, MAX_PREFIX_LENGTH);
if (n)
{
- rta *a = n->routes->attrs;
+ rte *e = n->routes;
+ rta *a = e->attrs;
pxlen = n->n.pxlen;
if (a->hostentry)
}
he->src = rta_clone(a);
- he->igp_metric = rt_get_igp_metric(n->routes);
+ he->igp_metric = rt_get_igp_metric(e);
}
done:
/* Reset the trie */
lp_flush(hc->lp);
- hc->trie = f_new_trie(hc->lp);
+ hc->trie = f_new_trie(hc->lp, sizeof(struct f_trie_node));
WALK_LIST_DELSAFE(n, x, hc->hostentries)
{
}
static struct hostentry *
-rt_find_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep)
+rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep)
{
struct hostentry *he;
if (!tab->hostcache)
rt_init_hostcache(tab);
- unsigned int k = hc_hash(a, dep);
+ uint k = hc_hash(a, dep);
struct hostcache *hc = tab->hostcache;
for (he = hc->hash_table[k >> hc->hash_shift]; he != NULL; he = he->next)
if (ipa_equal(he->addr, a) && (he->tab == dep))
void
rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr *gw, ip_addr *ll)
{
- rta_apply_hostentry(a, rt_find_hostentry(tab, *gw, *ll, dep));
+ rta_apply_hostentry(a, rt_get_hostentry(tab, *gw, *ll, dep));
}
+
/*
* CLI commands
*/
-static void
-rt_format_via(rte *e, byte *via)
+static byte *
+rt_format_via(rte *e)
{
rta *a = e->attrs;
+ /* Max text length w/o IP addr and interface name is 16 */
+ static byte via[STD_ADDRESS_P_LENGTH+sizeof(a->iface->name)+16];
+
switch (a->dest)
{
case RTD_ROUTER: bsprintf(via, "via %I on %s", a->gw, a->iface->name); break;
case RTD_MULTIPATH: bsprintf(via, "multipath"); break;
default: bsprintf(via, "???");
}
+ return via;
}
static void
rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, ea_list *tmpa)
{
- byte via[STD_ADDRESS_P_LENGTH+32], from[STD_ADDRESS_P_LENGTH+8];
+ byte from[STD_ADDRESS_P_LENGTH+8];
byte tm[TM_DATETIME_BUFFER_SIZE], info[256];
rta *a = e->attrs;
int primary = (e->net->routes == e);
+ int sync_error = (e->net->n.flags & KRF_SYNC_ERROR);
+ void (*get_route_info)(struct rte *, byte *buf, struct ea_list *attrs);
struct mpnh *nh;
- rt_format_via(e, via);
tm_format_datetime(tm, &config->tf_route, e->lastmod);
if (ipa_nonzero(a->from) && !ipa_equal(a->from, a->gw))
bsprintf(from, " from %I", a->from);
else
from[0] = 0;
- if (a->proto->proto->get_route_info || d->verbose)
+
+ get_route_info = a->src->proto->proto->get_route_info;
+ if (get_route_info || d->verbose)
{
/* Need to normalize the extended attributes */
ea_list *t = tmpa;
ea_merge(t, tmpa);
ea_sort(tmpa);
}
- if (a->proto->proto->get_route_info)
- a->proto->proto->get_route_info(e, info, tmpa);
+ if (get_route_info)
+ get_route_info(e, info, tmpa);
else
bsprintf(info, " (%d)", e->pref);
- cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, via, a->proto->name,
- tm, from, primary ? " *" : "", info);
+ cli_printf(c, -1007, "%-18s %s [%s %s%s]%s%s", ia, rt_format_via(e), a->src->proto->name,
+ tm, from, primary ? (sync_error ? " !" : " *") : "", info);
for (nh = a->nexthops; nh; nh = nh->next)
cli_printf(c, -1007, "\tvia %I on %s weight %d", nh->gw, nh->iface->name, nh->weight + 1);
if (d->verbose)
{
rte *e, *ee;
byte ia[STD_ADDRESS_P_LENGTH+8];
- int ok;
+ struct ea_list *tmpa;
+ struct announce_hook *a = NULL;
+ int first = 1;
+ int pass = 0;
bsprintf(ia, "%I/%d", n->n.prefix, n->n.pxlen);
- if (n->routes)
- d->net_counter++;
- for(e=n->routes; e; e=e->next)
+
+ if (d->export_mode)
+ {
+ if (! d->export_protocol->rt_notify)
+ return;
+
+ a = proto_find_announce_hook(d->export_protocol, d->table);
+ if (!a)
+ return;
+ }
+
+ for (e = n->routes; e; e = e->next)
{
- struct ea_list *tmpa, *old_tmpa;
- struct proto *p0 = e->attrs->proto;
- struct proto *p1 = d->export_protocol;
- struct proto *p2 = d->show_protocol;
+ if (rte_is_filtered(e) != d->filtered)
+ continue;
+
d->rt_counter++;
+ d->net_counter += first;
+ first = 0;
+
+ if (pass)
+ continue;
+
ee = e;
rte_update_lock(); /* We use the update buffer for filtering */
- old_tmpa = tmpa = p0->make_tmp_attrs ? p0->make_tmp_attrs(e, rte_update_pool) : NULL;
- ok = (d->filter == FILTER_ACCEPT || f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
- if (p2 && p2 != p0) ok = 0;
- if (ok && d->export_mode)
+ tmpa = rte_make_tmp_attrs(e, rte_update_pool);
+
+ /* Special case for merged export */
+ if ((d->export_mode == RSEM_EXPORT) && (d->export_protocol->accept_ra_types == RA_MERGED))
+ {
+ rte *rt_free;
+ e = rt_export_merged(a, n, &rt_free, &tmpa, rte_update_pool, 1);
+ pass = 1;
+
+ if (!e)
+ { e = ee; goto skip; }
+ }
+ else if (d->export_mode)
{
- int ic;
- if ((ic = p1->import_control ? p1->import_control(p1, &e, &tmpa, rte_update_pool) : 0) < 0)
- ok = 0;
- else if (!ic && d->export_mode > 1)
+ struct proto *ep = d->export_protocol;
+ int ic = ep->import_control ? ep->import_control(ep, &e, &tmpa, rte_update_pool) : 0;
+
+ if (ep->accept_ra_types == RA_OPTIMAL || ep->accept_ra_types == RA_MERGED)
+ pass = 1;
+
+ if (ic < 0)
+ goto skip;
+
+ if (d->export_mode > RSEM_PREEXPORT)
{
- /* FIXME - this shows what should be exported according
- to current filters, but not what was really exported.
- 'configure soft' command may change the export filter
- and do not update routes */
-
- if ((p1->out_filter == FILTER_REJECT) ||
- (p1->out_filter && f_run(p1->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT))
- ok = 0;
+ /*
+ * FIXME - This shows what should be exported according to current
+ * filters, but not what was really exported. 'configure soft'
+ * command may change the export filter and do not update routes.
+ */
+ int do_export = (ic > 0) ||
+ (f_run(a->out_filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) <= F_ACCEPT);
+
+ if (do_export != (d->export_mode == RSEM_EXPORT))
+ goto skip;
+
+ if ((d->export_mode == RSEM_EXPORT) && (ep->accept_ra_types == RA_ACCEPTED))
+ pass = 1;
}
}
- if (ok)
- {
- d->show_counter++;
- if (d->stats < 2)
- rt_show_rte(c, ia, e, d, tmpa);
- ia[0] = 0;
- }
+
+ if (d->show_protocol && (d->show_protocol != e->attrs->src->proto))
+ goto skip;
+
+ if (f_run(d->filter, &e, &tmpa, rte_update_pool, FF_FORCE_TMPATTR) > F_ACCEPT)
+ goto skip;
+
+ d->show_counter++;
+ if (d->stats < 2)
+ rt_show_rte(c, ia, e, d, tmpa);
+ ia[0] = 0;
+
+ skip:
if (e != ee)
- rte_free(ee);
+ {
+ rte_free(e);
+ e = ee;
+ }
rte_update_unlock();
+
if (d->primary_only)
break;
}
cli_printf(c, 8004, "Stopped due to reconfiguration");
goto done;
}
- if (d->export_protocol &&
- d->export_protocol->core_state != FS_HAPPY &&
- d->export_protocol->core_state != FS_FEEDING)
+ if (d->export_protocol && (d->export_protocol->export_state == ES_DOWN))
{
cli_printf(c, 8005, "Protocol is down");
goto done;
{
net *n;
+ /* Default is either a master table or a table related to a respective protocol */
+ if (!d->table && d->export_protocol) d->table = d->export_protocol->table;
+ if (!d->table && d->show_protocol) d->table = d->show_protocol->table;
+ if (!d->table) d->table = config->master_rtc->table;
+
+ /* Filtered routes are neither exported nor have sensible ordering */
+ if (d->filtered && (d->export_mode || d->primary_only))
+ cli_msg(0, "");
+
if (d->pxlen == 256)
{
FIB_ITERATE_INIT(&d->fit, &d->table->fib);
n = net_route(d->table, d->prefix, d->pxlen);
else
n = net_find(d->table, d->prefix, d->pxlen);
+
if (n)
- {
- rt_show_net(this_cli, n, d);
- cli_msg(0, "");
- }
+ rt_show_net(this_cli, n, d);
+
+ if (d->rt_counter)
+ cli_msg(0, "");
else
cli_msg(8001, "Network not in table");
}