Allows rejected routes to be kept and examined.

When 'import keep rejected' protocol option is activated, routes
rejected by the import filter are kept in the routing table, but they
are hidden and not propagated to other protocols. It is possible to
examine them using 'show route rejected'.

9 files changed, 135 insertions, 52 deletions

diff --git a/doc/bird.sgml b/doc/bird.sgml
index 24bc3026..e5550590 100644
--- a/doc/bird.sgml
+++ b/doc/bird.sgml
@@ -459,6 +459,14 @@ to zero to disable it. An empty <cf><m/switch/</cf> is equivalent to <cf/on/
 	works in the direction from the routing table to the protocol.
 	Default: <cf/none/.
 
+	<tag>import keep rejected <m/bool/</tag>
+	Usually, if an import filter rejects a route, the route is
+	forgotten. When this option is active, rejected routes are
+	kept in the routing table, but they are hidden and not
+	propagated to other protocols. But it is possible to show them
+	using <cf/show route rejected/. Note that this option does not
+	work for the pipe protocol. Default: off.
+
 	<tag>import limit <m/number/ [action warn | block | restart | disable]</tag>
 	Specify an import route limit (a maximum number of routes
 	imported from the protocol) and optionally the action to be
@@ -467,8 +475,11 @@ to zero to disable it. An empty <cf><m/switch/</cf> is equivalent to <cf/on/
 	protocol. Restart and disable actions shut the protocol down
 	like appropriate commands. Disable is the default action if an
 	action is not explicitly specified. Note that limits are reset
-	during protocol reconfigure, reload or restart.
-	Default: <cf/none/.
+	during protocol reconfigure, reload or restart. Also note that
+	if <cf/import keep rejected/ is active, rejected routes are
+	counted towards the limit and blocked routes are forgotten, as
+	the main purpose of the import limit is to protect routing
+	tables from overflow. Default: <cf/none/.
 
 	<tag>export limit <m/number/ [action warn | block | restart | disable]</tag>
 	Specify an export route limit, works similarly to
@@ -661,6 +672,9 @@ This argument can be omitted if there exists only a single instance.
 	<p>You can also select just routes added by a specific protocol.
 	<cf>protocol <m/p/</cf>.
 
+	<p>If BIRD is configured to keep rejected routes (see </cf/import keep rejected/
+	option), you can show them instead of routes by using </cf/rejected/ switch.
+
 	<p>The <cf/stats/ switch requests showing of route statistics (the
 	number of networks, number of routes before and after filtering). If
 	you use <cf/count/ instead, only the statistics will be printed.
@@ -2460,13 +2474,13 @@ interface definitions, prefix definitions and DNS definitions:
 	router. 0 means do not use as a default router. Default: 3 *
 	<cf/max ra interval/.
 
-	<tag>rdnss local <m/bool/</tag>
+	<tag>rdnss local <m/switch/</tag>
 	Use only local (interface-specific) RDNSS definitions for this
 	interface. Otherwise, both global and local definitions are
 	used. Could also be used to disable RDNSS for given interface
 	if no local definitons are specified. Default: no.
 
-	<tag>dnssl local <m/bool/</tag>
+	<tag>dnssl local <m/switch/</tag>
 	Use only local DNSSL definitions for this interface. See
 	<cf/rdnss local/ option above. Default: no.
 </descrip>
diff --git a/nest/config.Y b/nest/config.Y
index a75dd0c3..93402d90 100644
--- a/nest/config.Y
+++ b/nest/config.Y
@@ -44,7 +44,7 @@ CF_DECLS
 
 CF_KEYWORDS(ROUTER, ID, PROTOCOL, TEMPLATE, PREFERENCE, DISABLED, DEBUG, ALL, OFF, DIRECT)
 CF_KEYWORDS(INTERFACE, IMPORT, EXPORT, FILTER, NONE, TABLE, STATES, ROUTES, FILTERS)
-CF_KEYWORDS(LIMIT, ACTION, WARN, BLOCK, RESTART, DISABLE)
+CF_KEYWORDS(LIMIT, ACTION, WARN, BLOCK, RESTART, DISABLE, KEEP, REJECTED)
 CF_KEYWORDS(PASSWORD, FROM, PASSIVE, TO, ID, EVENTS, PACKETS, PROTOCOLS, INTERFACES)
 CF_KEYWORDS(PRIMARY, STATS, COUNT, FOR, COMMANDS, PREEXPORT, GENERATE, ROA, MAX, FLUSH)
 CF_KEYWORDS(LISTEN, BGP, V6ONLY, DUAL, ADDRESS, PORT, PASSWORDS, DESCRIPTION, SORTED)
@@ -187,6 +187,7 @@ proto_item:
  | EXPORT imexport { this_proto->out_filter = $2; }
  | IMPORT LIMIT limit_spec { this_proto->in_limit = $3; }
  | EXPORT LIMIT limit_spec { this_proto->out_limit = $3; }
+ | IMPORT KEEP REJECTED bool { this_proto->in_keep_rejected = $4; }
  | TABLE rtable { this_proto->table = $2; }
  | ROUTER ID idval { this_proto->router_id = $3; }
  | DESCRIPTION TEXT { this_proto->dsc = $2; }
@@ -405,7 +406,7 @@ CF_CLI(SHOW INTERFACES SUMMARY,,, [[Show summary of network interfaces]])
 { if_show_summary(); } ;
 
 CF_CLI_HELP(SHOW ROUTE, ..., [[Show routing table]])
-CF_CLI(SHOW ROUTE, r_args, [[[<prefix>|for <prefix>|for <ip>] [table <t>] [filter <f>|where <cond>] [all] [primary] [(export|preexport) <p>] [protocol <p>] [stats|count]]], [[Show routing table]])
+CF_CLI(SHOW ROUTE, r_args, [[[<prefix>|for <prefix>|for <ip>] [table <t>] [filter <f>|where <cond>] [all] [primary] [rejected] [(export|preexport) <p>] [protocol <p>] [stats|count]]], [[Show routing table]])
 { rt_show($3); } ;
 
 r_args:
@@ -451,6 +452,10 @@ r_args:
      $$ = $1;
      $$->primary_only = 1;
    }
+ | r_args REJECTED {
+     $$ = $1;
+     $$->rejected = 1;
+   }
  | r_args export_or_preexport SYM {
      struct proto_config *c = (struct proto_config *) $3->def;
      $$ = $1;
diff --git a/nest/proto.c b/nest/proto.c
index 53d3f1a2..2fb0e796 100644
--- a/nest/proto.c
+++ b/nest/proto.c
@@ -414,6 +414,7 @@ proto_reconfigure(struct proto *p, struct proto_config *oc, struct proto_config
       p->main_ahook->out_filter = nc->out_filter;
       p->main_ahook->in_limit = nc->in_limit;
       p->main_ahook->out_limit = nc->out_limit;
+      p->main_ahook->in_keep_rejected = nc->in_keep_rejected;
     }
 
   /* Update routes when filters changed. If the protocol in not UP,
@@ -719,8 +720,9 @@ proto_fell_down(struct proto *p)
 {
   DBG("Protocol %s down\n", p->name);
 
-  if (p->stats.imp_routes != 0)
-    log(L_ERR "Protocol %s is down but still has %d routes", p->name, p->stats.imp_routes);
+  u32 all_routes = p->stats.imp_routes + p->stats.rej_routes;
+  if (all_routes != 0)
+    log(L_ERR "Protocol %s is down but still has %d routes", p->name, all_routes);
 
   bzero(&p->stats, sizeof(struct proto_stats));
   proto_free_ahooks(p);
@@ -796,6 +798,7 @@ proto_schedule_feed(struct proto *p, int initial)
       p->main_ahook->out_filter = p->cf->out_filter;
       p->main_ahook->in_limit = p->cf->in_limit;
       p->main_ahook->out_limit = p->cf->out_limit;
+      p->main_ahook->in_keep_rejected = p->cf->in_keep_rejected;
       proto_reset_limit(p->main_ahook->in_limit);
       proto_reset_limit(p->main_ahook->out_limit);
     }
@@ -1093,10 +1096,15 @@ proto_state_name(struct proto *p)
 }
 
 static void
-proto_show_stats(struct proto_stats *s)
+proto_show_stats(struct proto_stats *s, int in_keep_rejected)
 {
-  cli_msg(-1006, "  Routes:         %u imported, %u exported, %u preferred", 
-	  s->imp_routes, s->exp_routes, s->pref_routes);
+  if (in_keep_rejected)
+    cli_msg(-1006, "  Routes:         %u imported, %u rejected, %u exported, %u preferred", 
+	    s->imp_routes, s->rej_routes, s->exp_routes, s->pref_routes);
+  else
+    cli_msg(-1006, "  Routes:         %u imported, %u exported, %u preferred", 
+	    s->imp_routes, s->exp_routes, s->pref_routes);
+
   cli_msg(-1006, "  Route change stats:     received   rejected   filtered    ignored   accepted");
   cli_msg(-1006, "    Import updates:     %10u %10u %10u %10u %10u",
 	  s->imp_updates_received, s->imp_updates_invalid,
@@ -1134,7 +1142,7 @@ proto_show_basic_info(struct proto *p)
   proto_show_limit(p->cf->out_limit, "Export limit:");
 
   if (p->proto_state != PS_DOWN)
-    proto_show_stats(&p->stats);
+    proto_show_stats(&p->stats, p->cf->in_keep_rejected);
 }
 
 void
diff --git a/nest/protocol.h b/nest/protocol.h
index 11fcb164..b10016d7 100644
--- a/nest/protocol.h
+++ b/nest/protocol.h
@@ -91,6 +91,7 @@ struct proto_config {
   int class;				/* SYM_PROTO or SYM_TEMPLATE */
   u32 debug, mrtdump;			/* Debugging bitfields, both use D_* constants */
   unsigned preference, disabled;	/* Generic parameters */
+  int in_keep_rejected;			/* Routes rejected in import filter are kept */
   u32 router_id;			/* Protocol specific router ID */
   struct rtable_config *table;		/* Table we're attached to */
   struct filter *in_filter, *out_filter; /* Attached filters */
@@ -106,7 +107,8 @@ struct proto_config {
 struct proto_stats {
   /* Import - from protocol to core */
   u32 imp_routes;		/* Number of routes successfully imported to the (adjacent) routing table */
-  u32 pref_routes;		/* Number of routes that are preferred, sum over all routing table */
+  u32 rej_routes;		/* Number of routes rejected in import filter but kept in the routing table */
+  u32 pref_routes;		/* Number of routes that are preferred, sum over all routing tables */
   u32 imp_updates_received;	/* Number of route updates received */
   u32 imp_updates_invalid;	/* Number of route updates rejected as invalid */
   u32 imp_updates_filtered;	/* Number of route updates rejected by filters */
@@ -410,6 +412,7 @@ struct announce_hook {
   struct proto_limit *out_limit;	/* Output limit */
   struct proto_stats *stats;		/* Per-table protocol statistics */
   struct announce_hook *next;		/* Next hook for the same protocol */
+  int in_keep_rejected;			/* Routes rejected in import filter are kept */
 };
 
 struct announce_hook *proto_add_announce_hook(struct proto *p, struct rtable *t, struct proto_stats *stats);
diff --git a/nest/route.h b/nest/route.h
index 524e69b3..3c10fc55 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -221,6 +221,14 @@ typedef struct rte {
 } rte;
 
 #define REF_COW		1		/* Copy this rte on write */
+#define REF_REJECTED	2		/* Route is rejected by import filter */
+
+/* Route is valid for propagation (may depend on other flags in the future), accepts NULL */
+static inline int rte_is_valid(rte *r) { return r && !(r->flags & REF_REJECTED); }
+
+/* Route just has REF_REJECTED flag */
+static inline int rte_is_rejected(rte *r) { return !!(r->flags & REF_REJECTED); }
+
 
 /* Types of route announcement, also used as flags */
 #define RA_OPTIMAL	1		/* Announcement of optimal route change */
@@ -263,7 +271,7 @@ struct rt_show_data {
   struct fib_iterator fit;
   struct proto *show_protocol;
   struct proto *export_protocol;
-  int export_mode, primary_only;
+  int export_mode, primary_only, rejected;
   struct config *running_on_config;
   int net_counter, rt_counter, show_counter;
   int stats, show_for;
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 118f4c25..421a05ea 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -69,7 +69,7 @@ net_route(rtable *tab, ip_addr a, int len)
     {
       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--;
     }
@@ -139,8 +139,11 @@ 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)
@@ -399,9 +402,13 @@ rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *ol
   rte *old_free = NULL;
   rte *r;
 
-  /* Used to track whether we met old_changed position. If it is NULL
-     it was the first and met it implicitly before current best route. */
-  int old_meet = (old_changed && !before_old) ? 1 : 0;
+  /* 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++;
@@ -409,7 +416,7 @@ rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *ol
     stats->exp_withdraws_received++;
 
   /* First, find the new_best route - first accepted by filters */
-  for (r=net->routes; r; r=r->next)
+  for (r=net->routes; rte_is_valid(r); r=r->next)
     {
       if (new_best = export_filter(ah, r, &new_free, &tmpa, 0))
 	break;
@@ -428,7 +435,8 @@ rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *ol
   if (feed)
     {
       if (feed == 2)	/* refeed */
-	old_best = new_best ? new_best : net->routes;
+	old_best = new_best ? new_best :
+	  (rte_is_valid(net->routes) ? net->routes : NULL);
       else
 	old_best = NULL;
 
@@ -477,7 +485,7 @@ rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *ol
     }
 
   /* Fourth case */
-  for (r=r->next; r; r=r->next)
+  for (r=r->next; rte_is_valid(r); r=r->next)
     {
       if (old_best = export_filter(ah, r, &old_free, NULL, 1))
 	goto found;
@@ -531,7 +539,14 @@ rt_notify_accepted(struct announce_hook *ah, net *net, rte *new_changed, rte *ol
 static void
 rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old, rte *before_old, ea_list *tmpa)
 {
-  struct announce_hook *a;
+  if (!rte_is_valid(old))
+    old = before_old = NULL;
+
+  if (!rte_is_valid(new))
+    new = NULL;
+
+  if (!old && !new)
+    return;
 
   if (type == RA_OPTIMAL)
     {
@@ -544,6 +559,7 @@ rte_announce(rtable *tab, unsigned type, net *net, rte *new, rte *old, rte *befo
 	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);
@@ -650,8 +666,13 @@ rte_recalculate(struct announce_hook *ah, net *net, rte *new, ea_list *tmpa, str
 	  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_rejected(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
@@ -680,8 +701,10 @@ rte_recalculate(struct announce_hook *ah, net *net, rte *new, ea_list *tmpa, str
   struct proto_limit *l = ah->in_limit;
   if (l && !old && new)
     {
-      if (stats->imp_routes >= l->limit)
-	proto_notify_limit(ah, l, stats->imp_routes);
+      u32 all_routes = stats->imp_routes + stats->rej_routes;
+
+      if (all_routes >= l->limit)
+	proto_notify_limit(ah, l, all_routes);
 
       if (l->state == PLS_BLOCKED)
 	{
@@ -692,15 +715,15 @@ rte_recalculate(struct announce_hook *ah, net *net, rte *new, ea_list *tmpa, str
 	}
     }
 
-  if (new)
+  if (new && !rte_is_rejected(new))
     stats->imp_updates_accepted++;
   else
     stats->imp_withdraws_accepted++;
 
   if (new)
-    stats->imp_routes++;
+    rte_is_rejected(new) ? stats->rej_routes++ : stats->imp_routes++;
   if (old)
-    stats->imp_routes--;
+    rte_is_rejected(old) ? stats->rej_routes-- : stats->imp_routes--;
 
   if (table->config->sorted)
     {
@@ -900,27 +923,41 @@ rte_update2(struct announce_hook *ah, net *net, rte *new, struct proto *src)
 	  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_rejected)
+	    goto drop;
+
+	  /* new is a private copy, i could modify it */
+	  new->flags |= REF_REJECTED;
 	}
-      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)
+	  if (src->make_tmp_attrs)
+	    tmpa = src->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_rejected)
+		    goto drop;
+
+		  new->flags |= REF_REJECTED;
+		}
+	      if (tmpa != old_tmpa && src->store_tmp_attrs)
+		src->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 */
 	new->attrs = rta_lookup(new->attrs);
       new->flags |= REF_COW;
@@ -1553,9 +1590,11 @@ again:
 	  return 0;
 	}
 
+      /* 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))
-	if (e)
+	if (rte_is_valid(e))
 	  {
 	    if (p->core_state != FS_FEEDING)
 	      return 1;  /* In the meantime, the protocol fell down. */
@@ -1564,7 +1603,7 @@ again:
 	  }
 
       if (p->accept_ra_types == RA_ANY)
-	for(e = n->routes; e != NULL; e = e->next)
+	for(e = n->routes; rte_is_valid(e); e = e->next)
 	  {
 	    if (p->core_state != FS_FEEDING)
 	      return 1;  /* In the meantime, the protocol fell down. */
@@ -1817,7 +1856,8 @@ rt_update_hostentry(rtable *tab, struct hostentry *he)
   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)
@@ -1850,7 +1890,7 @@ rt_update_hostentry(rtable *tab, struct hostentry *he)
 	}
 
       he->src = rta_clone(a);
-      he->igp_metric = rt_get_igp_metric(n->routes);
+      he->igp_metric = rt_get_igp_metric(e);
     }
 
  done:
@@ -1980,14 +2020,19 @@ rt_show_net(struct cli *c, net *n, struct rt_show_data *d)
   int ok;
 
   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 (rte_is_rejected(e) != d->rejected)
+	continue;
+
       struct ea_list *tmpa;
       struct proto *p0 = e->attrs->proto;
       struct proto *p1 = d->export_protocol;
       struct proto *p2 = d->show_protocol;
+
+      if (ia[0])
+	d->net_counter++;
       d->rt_counter++;
       ee = e;
       rte_update_lock();		/* We use the update buffer for filtering */
diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index e5bc84dd..9f71544e 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -1346,7 +1346,7 @@ bgp_rte_recalculate(rtable *table, net *net, rte *new, rte *old, rte *old_best)
 
   /* The default case - find a new best-in-group route */
   r = new; /* new may not be in the list */
-  for (s=net->routes; s; s=s->next)
+  for (s=net->routes; rte_is_valid(s); s=s->next)
     if (use_deterministic_med(s) && same_group(s, lpref, lasn))
       {
 	s->u.bgp.suppressed = 1;
diff --git a/proto/bgp/bgp.c b/proto/bgp/bgp.c
index dbc59eea..2eb8ccb4 100644
--- a/proto/bgp/bgp.c
+++ b/proto/bgp/bgp.c
@@ -1188,7 +1188,7 @@ bgp_show_proto_info(struct proto *P)
       cli_msg(-1006, "    Source address:   %I", p->source_addr);
       if (P->cf->in_limit)
 	cli_msg(-1006, "    Route limit:      %d/%d",
-		p->p.stats.imp_routes, P->cf->in_limit->limit);
+		p->p.stats.imp_routes + p->p.stats.rej_routes, P->cf->in_limit->limit);
       cli_msg(-1006, "    Hold timer:       %d/%d",
 	      tm_remains(c->hold_timer), c->hold_time);
       cli_msg(-1006, "    Keepalive timer:  %d/%d",
diff --git a/sysdep/unix/krt.c b/sysdep/unix/krt.c
index 2128e136..6c0e5e91 100644
--- a/sysdep/unix/krt.c
+++ b/sysdep/unix/krt.c
@@ -581,7 +581,7 @@ krt_flush_routes(struct krt_proto *p)
     {
       net *n = (net *) f;
       rte *e = n->routes;
-      if (e && (n->n.flags & KRF_INSTALLED))
+      if (rte_is_valid(e) && (n->n.flags & KRF_INSTALLED))
 	{
 	  /* FIXME: this does not work if gw is changed in export filter */
 	  krt_replace_rte(p, e->net, NULL, e, NULL);
@@ -656,7 +656,7 @@ krt_got_route(struct krt_proto *p, rte *e)
     }
 
   old = net->routes;
-  if ((net->n.flags & KRF_INSTALLED) && old)
+  if ((net->n.flags & KRF_INSTALLED) && rte_is_valid(old))
     {
       /* There may be changes in route attributes, we ignore that.
          Also, this does not work well if gw is changed in export filter */