Basic route aggregation

Add a new protocol offering route aggregation.

User can specify list of route attributes in the configuration file and
run route aggregation on the export side of the pipe protocol. Routes are
sorted and for every group of equivalent routes new route is created and
exported to the routing table. It is also possible to specify filter
which will run for every route before aggregation.

Furthermore, it will be possible to set attributes of new routes
according to attributes of the aggregated routes.

This is a work in progress.

Original work by Igor Putovny, subsequent cleanups and finalization by
Maria Matejka.

6 files changed, 139 insertions, 30 deletions

diff --git a/filter/config.Y b/filter/config.Y
index dfabddf7..a15683f5 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -45,7 +45,7 @@ static inline void f_method_call_start(struct f_inst *object)
     .object = object,
     .main = new_config->current_scope,
     .scope = {
-      .next = NULL,
+      .next = global_root_scope,
       .hash = scope->hash,
       .active = 1,
       .block = 1,
@@ -244,6 +244,25 @@ f_new_lc_item(u32 f1, u32 t1, u32 f2, u32 t2, u32 f3, u32 t3)
   return t;
 }
 
+static inline struct f_inst *
+f_const_empty(enum f_type t)
+{
+  switch (t) {
+    case T_PATH:
+    case T_CLIST:
+    case T_ECLIST:
+    case T_LCLIST:
+      return f_new_inst(FI_CONSTANT, (struct f_val) {
+	.type = t,
+	.val.ad = &null_adata,
+      });
+    case T_ROUTE:
+      return f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_ROUTE });
+    default:
+      return f_new_inst(FI_CONSTANT, (struct f_val) {});
+  }
+}
+
 /*
  * Remove all new lines and doubled whitespaces
  * and convert all tabulators to spaces
@@ -303,8 +322,8 @@ f_lval_getter(struct f_lval *lval)
 {
   switch (lval->type) {
     case F_LVAL_VARIABLE:	return f_new_inst(FI_VAR_GET, lval->sym);
-    case F_LVAL_SA:		return f_new_inst(FI_RTA_GET, lval->sa);
-    case F_LVAL_EA:		return f_new_inst(FI_EA_GET, lval->da);
+    case F_LVAL_SA:		return f_new_inst(FI_RTA_GET, lval->rte, lval->sa);
+    case F_LVAL_EA:		return f_new_inst(FI_EA_GET, lval->rte, lval->da);
     default:			bug("Unknown lval type");
   }
 }
@@ -447,6 +466,7 @@ type:
  | CLIST { $$ = T_CLIST; }
  | ECLIST { $$ = T_ECLIST; }
  | LCLIST { $$ = T_LCLIST; }
+ | ROUTE { $$ = T_ROUTE; }
  | type SET {
 	switch ($1) {
 	  case T_INT:
@@ -832,7 +852,7 @@ symbol_value: symbol_known
 	$$ = f_new_inst(FI_VAR_GET, $1);
 	break;
       case SYM_ATTRIBUTE:
-	$$ = f_new_inst(FI_EA_GET, *$1->attribute);
+	$$ = f_new_inst(FI_EA_GET, f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_ROUTE, .val.rte = NULL }), *$1->attribute);
 	break;
       default:
 	cf_error("Can't get value of symbol %s", $1->name);
@@ -866,6 +886,16 @@ method_name_cont:
    } '(' var_list ')' {
      $$ = f_dispatch_method($1, FM.object, $4, 1);
    }
+ | static_attr {
+     if (FM.object->type != T_ROUTE)
+       cf_error("Getting a route attribute from %s, need a route", f_type_name(FM.object->type));
+     $$ = f_new_inst(FI_RTA_GET, FM.object, $1);
+   }
+ | dynamic_attr {
+     if (FM.object->type != T_ROUTE)
+       cf_error("Getting a route attribute from %s, need a route", f_type_name(FM.object->type));
+     $$ = f_new_inst(FI_EA_GET, FM.object, $1);
+   }
  ;
 
 term:
@@ -891,9 +921,9 @@ term:
  | constant { $$ = $1; }
  | constructor { $$ = $1; }
 
- | static_attr { $$ = f_new_inst(FI_RTA_GET, $1); }
+ | static_attr { $$ = f_new_inst(FI_RTA_GET, f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_ROUTE, .val.rte = NULL }), $1); }
 
- | dynamic_attr { $$ = f_new_inst(FI_EA_GET, $1); }
+ | dynamic_attr { $$ = f_new_inst(FI_EA_GET, f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_ROUTE, .val.rte = NULL }), $1); }
 
  | term_dot_method
 
@@ -1044,16 +1074,17 @@ lvalue:
      switch ($1->class)
      {
        case SYM_VARIABLE_RANGE:
-	 $$ = (struct f_lval) { .type = F_LVAL_VARIABLE, .sym = $1 };
+	 $$ = (struct f_lval) { .type = F_LVAL_VARIABLE, .sym = $1, .rte = f_const_empty(T_ROUTE) };
          break;
        case SYM_ATTRIBUTE:
-         $$ = (struct f_lval) { .type = F_LVAL_EA, .da = *($1->attribute) };
+         $$ = (struct f_lval) { .type = F_LVAL_EA, .da = *($1->attribute), .rte = f_const_empty(T_ROUTE) };
 	 break;
        default:
 	 cf_error("Variable name or custom attribute name required");
      }
    }
- | static_attr { $$ = (struct f_lval) { .type = F_LVAL_SA, .sa = $1 }; }
- | dynamic_attr { $$ = (struct f_lval) { .type = F_LVAL_EA, .da = $1 }; };
+ | static_attr { $$ = (struct f_lval) { .type = F_LVAL_SA, .sa = $1, .rte = f_const_empty(T_ROUTE) }; }
+ | dynamic_attr { $$ = (struct f_lval) { .type = F_LVAL_EA, .da = $1, .rte = f_const_empty(T_ROUTE) }; }
+ ;
 
 CF_END
diff --git a/filter/data.c b/filter/data.c
index 89b75e56..e268a8ec 100644
--- a/filter/data.c
+++ b/filter/data.c
@@ -56,6 +56,9 @@ static const char * const f_type_str[] = {
   [T_LC]	= "lc",
   [T_LCLIST]	= "lclist",
   [T_RD]	= "rd",
+
+  [T_ROUTE] = "route",
+  [T_ROUTES_BLOCK] = "block of routes",
 };
 
 const char *
@@ -78,6 +81,7 @@ f_type_element_type(enum f_type t)
     case T_CLIST:  return T_PAIR;
     case T_ECLIST: return T_EC;
     case T_LCLIST: return T_LC;
+    case T_ROUTES_BLOCK: return T_ROUTE;
     default: return T_VOID;
   };
 }
@@ -206,6 +210,11 @@ val_compare(const struct f_val *v1, const struct f_val *v2)
     return net_compare(v1->val.net, v2->val.net);
   case T_STRING:
     return strcmp(v1->val.s, v2->val.s);
+  case T_PATH:
+    return as_path_compare(v1->val.ad, v2->val.ad);
+  case T_ROUTE:
+  /* Fall through */
+  case T_ROUTES_BLOCK:
   default:
     return F_CMP_ERROR;
   }
@@ -296,6 +305,10 @@ val_same(const struct f_val *v1, const struct f_val *v2)
     return same_tree(v1->val.t, v2->val.t);
   case T_PREFIX_SET:
     return trie_same(v1->val.ti, v2->val.ti);
+  case T_ROUTE:
+    return v1->val.rte == v2->val.rte;
+  case T_ROUTES_BLOCK:
+    return v1->val.ad == v2->val.ad;
   default:
     bug("Invalid type in val_same(): %x", v1->type);
   }
@@ -570,6 +583,36 @@ val_in_range(const struct f_val *v1, const struct f_val *v2)
 }
 
 /*
+ * rte_format - format route information
+ */
+static void
+rte_format(const struct rte *rte, buffer *buf)
+{
+  if (rte)
+    buffer_print(buf, "Route [%d] to %N from %s.%s via %s",
+                 rte->src->global_id, rte->net->n.addr,
+                 rte->sender->proto->name, rte->sender->name,
+                 rte->src->proto->name);
+  else
+    buffer_puts(buf, "[No route]");
+}
+
+static void
+rte_block_format(const struct rte *rte, buffer *buf)
+{
+  buffer_print(buf, "Block of routes:");
+
+  int i = 0;
+  while (rte)
+  {
+    buffer_print(buf, "%s%d: ", i ? "; " : " ", i);
+    rte_format(rte, buf);
+    rte = rte->next;
+    i++;
+  }
+}
+
+/*
  * val_format - format filter value
  */
 void
@@ -598,6 +641,8 @@ val_format(const struct f_val *v, buffer *buf)
   case T_ECLIST: ec_set_format(v->val.ad, -1, buf2, 1000); buffer_print(buf, "(eclist %s)", buf2); return;
   case T_LCLIST: lc_set_format(v->val.ad, -1, buf2, 1000); buffer_print(buf, "(lclist %s)", buf2); return;
   case T_PATH_MASK: pm_format(v->val.path_mask, buf); return;
+  case T_ROUTE: rte_format(v->val.rte, buf); return;
+  case T_ROUTES_BLOCK: rte_block_format(v->val.rte, buf); return;
   default:	buffer_print(buf, "[unknown type %x]", v->type); return;
   }
 }
diff --git a/filter/data.h b/filter/data.h
index 3430455a..0a521ec5 100644
--- a/filter/data.h
+++ b/filter/data.h
@@ -11,6 +11,7 @@
 #define _BIRD_FILTER_DATA_H_
 
 #include "nest/bird.h"
+#include "nest/route.h"
 
 /* Type numbers must be in 0..0xff range */
 #define T_MASK 0xff
@@ -62,6 +63,8 @@ enum f_type {
   T_PATH_MASK_ITEM = 0x2b,	/* Path mask item for path mask constructors */
   T_BYTESTRING = 0x2c,
 
+  T_ROUTE = 0x78,
+  T_ROUTES_BLOCK = 0x79,
   T_SET = 0x80,
   T_PREFIX_SET = 0x81,
 } PACKED;
@@ -90,6 +93,7 @@ struct f_val {
     const struct adata *ad;
     const struct f_path_mask *path_mask;
     struct f_path_mask_item pmi;
+    struct rte *rte;
   } val;
 };
 
@@ -136,6 +140,7 @@ enum f_lval_type {
 /* Filter l-value */
 struct f_lval {
   enum f_lval_type type;
+  struct f_inst *rte;
   union {
     struct symbol *sym;
     struct f_dynamic_attr da;
diff --git a/filter/f-inst.c b/filter/f-inst.c
index a7bec81e..4356a735 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -617,6 +617,22 @@
     METHOD_CONSTRUCTOR("!for_next");
   }
 
+  INST(FI_ROUTES_BLOCK_FOR_NEXT, 3, 0) {
+    NEVER_CONSTANT;
+    ARG(1, T_ROUTES_BLOCK);
+    if (!v2.type)
+      v2 = v1;
+
+    if (v2.val.rte)
+    {
+      v3.val.rte = v2.val.rte;
+      v2.val.rte = v2.val.rte->next;
+      LINE(2,0);
+    }
+
+    METHOD_CONSTRUCTOR("!for_next");
+  }
+
   INST(FI_CONDITION, 1, 0) {
     ARG(1, T_BOOL);
     if (v1.val.i)
@@ -654,11 +670,13 @@
     }
   }
 
-  INST(FI_RTA_GET, 0, 1) {
+  INST(FI_RTA_GET, 1, 1) {
     {
-      STATIC_ATTR;
       ACCESS_RTE;
-      struct rta *rta = (*fs->rte)->attrs;
+      ARG(1, T_ROUTE);
+      STATIC_ATTR;
+
+      struct rta *rta = v1.val.rte ? v1.val.rte->attrs : (*fs->rte)->attrs;
 
       switch (sa.sa_code)
       {
@@ -797,13 +815,15 @@
     }
   }
 
-  INST(FI_EA_GET, 0, 1) {	/* Access to extended attributes */
-    DYNAMIC_ATTR;
+  INST(FI_EA_GET, 1, 1) {	/* Access to extended attributes */
     ACCESS_RTE;
     ACCESS_EATTRS;
+    ARG(1, T_ROUTE);
+    DYNAMIC_ATTR;
     RESULT_TYPE(da.f_type);
     {
-      eattr *e = ea_find(*fs->eattrs, da.ea_code);
+      struct ea_list *eal = v1.val.rte ? v1.val.rte->attrs->eattrs : *fs->eattrs;
+      eattr *e = ea_find(eal, da.ea_code);
 
       if (!e) {
 	RESULT_VAL(val_empty(da.f_type));
diff --git a/filter/filter.c b/filter/filter.c
index 65fb92a4..560778a8 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -90,6 +90,9 @@ struct filter_state {
   /* Buffer for log output */
   struct buffer buf;
 
+  /* Pointers to routes we are aggregating */
+  const struct f_val *val;
+
   /* Filter execution flags */
   int flags;
 };
@@ -157,18 +160,20 @@ static struct tbf rl_runtime_err = TBF_DEFAULT_LOG_LIMITS;
  * TWOARGS macro to get both of them evaluated.
  */
 static enum filter_return
-interpret(struct filter_state *fs, const struct f_line *line, struct f_val *val)
+interpret(struct filter_state *fs, const struct f_line *line, uint argc, const struct f_val *argv, struct f_val *val)
 {
   /* No arguments allowed */
-  ASSERT(line->args == 0);
+  ASSERT_DIE(line->args == argc);
 
   /* Initialize the filter stack */
   struct filter_stack *fstk = fs->stack;
 
-  fstk->vcnt = line->vars;
-  memset(fstk->vstk, 0, sizeof(struct f_val) * line->vars);
+  /* Set the arguments and top-level variables */
+  fstk->vcnt = line->vars + line->args;
+  memcpy(fstk->vstk, argv, sizeof(struct f_val) * line->args);
+  memset(fstk->vstk + line->args, 0, sizeof(struct f_val) * line->vars);
 
-  /* The same as with the value stack. Not resetting the stack for performance reasons. */
+  /* The same as with the value stack. Not resetting the stack completely for performance reasons. */
   fstk->ecnt = 1;
   fstk->estk[0].line = line;
   fstk->estk[0].pos = 0;
@@ -237,7 +242,6 @@ interpret(struct filter_state *fs, const struct f_line *line, struct f_val *val)
   return F_ERROR;
 }
 
-
 /**
  * f_run - run a filter for a route
  * @filter: filter to run
@@ -271,6 +275,12 @@ f_run(const struct filter *filter, struct rte **rte, struct linpool *tmp_pool, i
   if (filter == FILTER_REJECT)
     return F_REJECT;
 
+  return f_run_args(filter, rte, tmp_pool, 0, NULL, flags);
+}
+
+enum filter_return
+f_run_args(const struct filter *filter, struct rte **rte, struct linpool *tmp_pool, uint argc, const struct f_val *argv, int flags)
+{
   int rte_cow = ((*rte)->flags & REF_COW);
   DBG( "Running filter `%s'...", filter->name );
 
@@ -285,7 +295,7 @@ f_run(const struct filter *filter, struct rte **rte, struct linpool *tmp_pool, i
   LOG_BUFFER_INIT(filter_state.buf);
 
   /* Run the interpreter itself */
-  enum filter_return fret = interpret(&filter_state, filter->root, NULL);
+  enum filter_return fret = interpret(&filter_state, filter->root, argc, argv, NULL);
 
   if (filter_state.old_rta) {
     /*
@@ -337,7 +347,7 @@ f_run(const struct filter *filter, struct rte **rte, struct linpool *tmp_pool, i
  */
 
 enum filter_return
-f_eval_rte(const struct f_line *expr, struct rte **rte, struct linpool *tmp_pool)
+f_eval_rte(const struct f_line *expr, struct rte **rte, struct linpool *tmp_pool, uint argc, const struct f_val *argv, struct f_val *pres)
 {
   filter_state = (struct filter_state) {
     .stack = &filter_stack,
@@ -347,10 +357,7 @@ f_eval_rte(const struct f_line *expr, struct rte **rte, struct linpool *tmp_pool
 
   LOG_BUFFER_INIT(filter_state.buf);
 
-  ASSERT(!((*rte)->flags & REF_COW));
-  ASSERT(!rta_is_cached((*rte)->attrs));
-
-  return interpret(&filter_state, expr, NULL);
+  return interpret(&filter_state, expr, argc, argv, pres);
 }
 
 /*
@@ -369,7 +376,7 @@ f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres)
 
   LOG_BUFFER_INIT(filter_state.buf);
 
-  enum filter_return fret = interpret(&filter_state, expr, pres);
+  enum filter_return fret = interpret(&filter_state, expr, 0, NULL, pres);
   return fret;
 }
 
diff --git a/filter/filter.h b/filter/filter.h
index 91de696c..18ff0874 100644
--- a/filter/filter.h
+++ b/filter/filter.h
@@ -52,7 +52,8 @@ struct filter {
 struct rte;
 
 enum filter_return f_run(const struct filter *filter, struct rte **rte, struct linpool *tmp_pool, int flags);
-enum filter_return f_eval_rte(const struct f_line *expr, struct rte **rte, struct linpool *tmp_pool);
+enum filter_return f_run_args(const struct filter *filter, struct rte **rte, struct linpool *tmp_pool, uint argc, const struct f_val *argv, int flags);
+enum filter_return f_eval_rte(const struct f_line *expr, struct rte **rte, struct linpool *tmp_pool, uint argc, const struct f_val *argv, struct f_val *pres);
 enum filter_return f_eval_buf(const struct f_line *expr, struct linpool *tmp_pool, buffer *buf);
 
 struct f_val cf_eval(const struct f_inst *inst, int type);