Filter refactoring: dropped the recursion from the interpreter

This is a major change of how the filters are interpreted. If everything
works how it should, it should not affect you unless you are hacking the
filters themselves.

Anyway, this change should make a huge improvement in the filter performance
as previous benchmarks showed that our major problem lies in the
recursion itself.

There are also some changes in nest and protocols, related mostly to
spreading const declarations throughout the whole BIRD and also to
refactored dynamic attribute definitions. The need of these came up
during the whole work and it is too difficult to split out these
not-so-related changes.

10 files changed, 179 insertions, 152 deletions

diff --git a/nest/a-path.c b/nest/a-path.c
index 6f1c40bf..d3a1d636 100644
--- a/nest/a-path.c
+++ b/nest/a-path.c
@@ -77,10 +77,10 @@ bad:
 }
 
 int
-as_path_16to32(byte *dst, byte *src, uint len)
+as_path_16to32(byte *dst, const byte *src, uint len)
 {
   byte *dst0 = dst;
-  byte *end = src + len;
+  const byte *end = src + len;
   uint i, n;
 
   while (src < end)
@@ -101,10 +101,10 @@ as_path_16to32(byte *dst, byte *src, uint len)
 }
 
 int
-as_path_32to16(byte *dst, byte *src, uint len)
+as_path_32to16(byte *dst, const byte *src, uint len)
 {
   byte *dst0 = dst;
-  byte *end = src + len;
+  const byte *end = src + len;
   uint i, n;
 
   while (src < end)
@@ -273,11 +273,11 @@ as_path_to_old(struct linpool *pool, const struct adata *path)
  * AS_CONFED_* segments have zero length and must be added if they are on edge.
  * In contrast to other as_path_* functions, @path is modified in place.
  */
-void
-as_path_cut(struct adata *path, uint num)
+struct adata *
+as_path_cut(struct linpool *pool, const struct adata *path, uint num)
 {
-  byte *pos = path->data;
-  byte *end = pos + path->length;
+  const byte *pos = path->data;
+  const byte *end = pos + path->length;
 
   while (pos < end)
   {
@@ -297,28 +297,39 @@ as_path_cut(struct adata *path, uint num)
     /* Cannot add whole segment, so try partial one and finish */
     if (num < n)
     {
+      const byte *nend = pos;
+      if (num)
+	nend += 2 + BS * num;
+
+      struct adata *res = lp_alloc_adata(pool, path->length);
+      res->length = nend - (const byte *) path->data;
+      memcpy(res->data, path->data, res->length);
+
       if (num)
       {
-	pos[1] = num;
-	pos += 2 + BS * num;
+	byte *dpos = ((byte *) res->data) + (pos - (const byte *) path->data);
+	dpos[1] = num;
       }
 
-      break;
+      return res;
     }
 
     num -= n;
     pos += 2 + BS * l;
   }
 
-  path->length = pos - path->data;
+  struct adata *res = lp_alloc_adata(pool, path->length);
+  res->length = path->length;
+  memcpy(res->data, path->data, res->length);
+  return res;
 }
 
 /*
  * Merge (concatenate) paths @p1 and @p2 and return the result.
  * In contrast to other as_path_* functions, @p1 and @p2 may be reused.
  */
-struct adata *
-as_path_merge(struct linpool *pool, struct adata *p1, struct adata *p2)
+const struct adata *
+as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2)
 {
   if (p1->length == 0)
     return p2;
@@ -561,7 +572,7 @@ as_path_contains(const struct adata *path, u32 as, int min)
 }
 
 int
-as_path_match_set(const struct adata *path, struct f_tree *set)
+as_path_match_set(const struct adata *path, const struct f_tree *set)
 {
   const u8 *p = path->data;
   const u8 *q = p+path->length;
@@ -574,7 +585,7 @@ as_path_match_set(const struct adata *path, struct f_tree *set)
       for (i=0; i<n; i++)
 	{
 	  struct f_val v = {T_INT, .val.i = get_as(p)};
-	  if (find_tree(set, v))
+	  if (find_tree(set, &v))
 	    return 1;
 	  p += BS;
 	}
@@ -583,8 +594,8 @@ as_path_match_set(const struct adata *path, struct f_tree *set)
   return 0;
 }
 
-struct adata *
-as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos)
+const struct adata *
+as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos)
 {
   if (!path)
     return NULL;
@@ -612,7 +623,10 @@ as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32
 	  int match;
 
 	  if (set)
-	    match = !!find_tree(set, (struct f_val){T_INT, .val.i = as});
+	    {
+	      struct f_val v = {T_INT, .val.i = as};
+	      match = !!find_tree(set, &v);
+	    }
 	  else
 	    match = (as == key);
 
@@ -771,7 +785,7 @@ pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
  * is marked.
  */
 int
-as_path_match(const struct adata *path, struct f_path_mask *mask)
+as_path_match(const struct adata *path, const struct f_path_mask *mask)
 {
   struct pm_pos pos[2048 + 1];
   int plen = parse_path(path, pos);
@@ -788,12 +802,12 @@ as_path_match(const struct adata *path, struct f_path_mask *mask)
   l = h = 0;
   pos[0].mark = 1;
 
-  while (mask)
+  for (uint m=0; m < mask->len; m++)
     {
       /* We remove this mark to not step after pos[plen] */
       pos[plen].mark = 0;
 
-      switch (mask->kind)
+      switch (mask->item[m].kind)
 	{
 	case PM_ASTERISK:
 	  for (i = l; i <= plen; i++)
@@ -802,13 +816,13 @@ as_path_match(const struct adata *path, struct f_path_mask *mask)
 	  break;
 
 	case PM_ASN:	/* Define single ASN as ASN..ASN - very narrow interval */
-	  val2 = val = mask->val;
+	  val2 = val = mask->item[m].asn;
 	  goto step;
 	case PM_ASN_EXPR:
 	  bug("Expressions should be evaluated on AS path mask construction.");
 	case PM_ASN_RANGE:
-	  val = mask->val;
-	  val2 = mask->val2;
+	  val = mask->item[m].from;
+	  val2 = mask->item[m].to;
 	  goto step;
 	case PM_QUESTION:
 	step:
@@ -817,7 +831,7 @@ as_path_match(const struct adata *path, struct f_path_mask *mask)
 	    if (pos[i].mark)
 	      {
 		pos[i].mark = 0;
-		if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val, val2))
+		if ((mask->item[m].kind == PM_QUESTION) || pm_match(pos + i, val, val2))
 		  pm_mark(pos, i, plen, &nl, &nh);
 	      }
 
@@ -828,8 +842,6 @@ as_path_match(const struct adata *path, struct f_path_mask *mask)
 	  l = nl;
 	  break;
 	}
-
-      mask = mask->next;
     }
 
   return pos[plen].mark;
diff --git a/nest/a-path_test.c b/nest/a-path_test.c
index a71b48ba..9ed0a786 100644
--- a/nest/a-path_test.c
+++ b/nest/a-path_test.c
@@ -34,26 +34,24 @@ t_as_path_match(void)
     first_prepended = last_prepended = 0;
     struct linpool *lp = lp_new_default(&root_pool);
 
-    struct f_path_mask mask[AS_PATH_LENGTH] = {};
-    int i;
-    for (i = 0; i < AS_PATH_LENGTH; i++)
+    struct f_path_mask *mask = alloca(sizeof(struct f_path_mask) + AS_PATH_LENGTH * sizeof(struct f_path_mask_item));
+    mask->len = AS_PATH_LENGTH;
+    for (int i = AS_PATH_LENGTH - 1; i >= 0; i--)
     {
       u32 val = bt_random();
       as_path = as_path_prepend(lp, as_path, val);
       bt_debug("Prepending ASN: %10u \n", val);
 
       if (i == 0)
-	first_prepended = val;
-      if (i == AS_PATH_LENGTH-1)
 	last_prepended = val;
+      if (i == AS_PATH_LENGTH-1)
+	first_prepended = val;
 
-      mask[i].kind = PM_ASN;
-      mask[i].val  = val;
-      if (i)
-	mask[i].next = &mask[i-1];
+      mask->item[i].kind = PM_ASN;
+      mask->item[i].asn  = val;
     }
 
-    bt_assert_msg(as_path_match(as_path, &mask[AS_PATH_LENGTH-1]), "Mask should match with AS path");
+    bt_assert_msg(as_path_match(as_path, mask), "Mask should match with AS path");
 
     u32 asn;
 
diff --git a/nest/a-set.c b/nest/a-set.c
index 048e522d..10ddd139 100644
--- a/nest/a-set.c
+++ b/nest/a-set.c
@@ -34,7 +34,7 @@
  * the buffer to indicate truncation.
  */
 int
-int_set_format(struct adata *set, int way, int from, byte *buf, uint size)
+int_set_format(const struct adata *set, int way, int from, byte *buf, uint size)
 {
   u32 *z = (u32 *) set->data;
   byte *end = buf + size - 24;
@@ -115,7 +115,7 @@ ec_format(byte *buf, u64 ec)
 }
 
 int
-ec_set_format(struct adata *set, int from, byte *buf, uint size)
+ec_set_format(const struct adata *set, int from, byte *buf, uint size)
 {
   u32 *z = int_set_get_data(set);
   byte *end = buf + size - 64;
@@ -150,7 +150,7 @@ lc_format(byte *buf, lcomm lc)
 }
 
 int
-lc_set_format(struct adata *set, int from, byte *buf, uint bufsize)
+lc_set_format(const struct adata *set, int from, byte *buf, uint bufsize)
 {
   u32 *d = (u32 *) set->data;
   byte *end = buf + bufsize - 64;
@@ -181,7 +181,7 @@ lc_set_format(struct adata *set, int from, byte *buf, uint bufsize)
 }
 
 int
-int_set_contains(struct adata *list, u32 val)
+int_set_contains(const struct adata *list, u32 val)
 {
   if (!list)
     return 0;
@@ -198,7 +198,7 @@ int_set_contains(struct adata *list, u32 val)
 }
 
 int
-ec_set_contains(struct adata *list, u64 val)
+ec_set_contains(const struct adata *list, u64 val)
 {
   if (!list)
     return 0;
@@ -217,7 +217,7 @@ ec_set_contains(struct adata *list, u64 val)
 }
 
 int
-lc_set_contains(struct adata *list, lcomm val)
+lc_set_contains(const struct adata *list, lcomm val)
 {
   if (!list)
     return 0;
@@ -233,8 +233,8 @@ lc_set_contains(struct adata *list, lcomm val)
   return 0;
 }
 
-struct adata *
-int_set_prepend(struct linpool *pool, struct adata *list, u32 val)
+const struct adata *
+int_set_prepend(struct linpool *pool, const struct adata *list, u32 val)
 {
   struct adata *res;
   int len;
@@ -254,8 +254,8 @@ int_set_prepend(struct linpool *pool, struct adata *list, u32 val)
   return res;
 }
 
-struct adata *
-int_set_add(struct linpool *pool, struct adata *list, u32 val)
+const struct adata *
+int_set_add(struct linpool *pool, const struct adata *list, u32 val)
 {
   struct adata *res;
   int len;
@@ -275,8 +275,8 @@ int_set_add(struct linpool *pool, struct adata *list, u32 val)
   return res;
 }
 
-struct adata *
-ec_set_add(struct linpool *pool, struct adata *list, u64 val)
+const struct adata *
+ec_set_add(struct linpool *pool, const struct adata *list, u64 val)
 {
   if (ec_set_contains(list, val))
     return list;
@@ -295,8 +295,8 @@ ec_set_add(struct linpool *pool, struct adata *list, u64 val)
   return res;
 }
 
-struct adata *
-lc_set_add(struct linpool *pool, struct adata *list, lcomm val)
+const struct adata *
+lc_set_add(struct linpool *pool, const struct adata *list, lcomm val)
 {
   if (lc_set_contains(list, val))
     return list;
@@ -313,8 +313,8 @@ lc_set_add(struct linpool *pool, struct adata *list, lcomm val)
   return res;
 }
 
-struct adata *
-int_set_del(struct linpool *pool, struct adata *list, u32 val)
+const struct adata *
+int_set_del(struct linpool *pool, const struct adata *list, u32 val)
 {
   if (!int_set_contains(list, val))
     return list;
@@ -335,8 +335,8 @@ int_set_del(struct linpool *pool, struct adata *list, u32 val)
   return res;
 }
 
-struct adata *
-ec_set_del(struct linpool *pool, struct adata *list, u64 val)
+const struct adata *
+ec_set_del(struct linpool *pool, const struct adata *list, u64 val)
 {
   if (!ec_set_contains(list, val))
     return list;
@@ -362,8 +362,8 @@ ec_set_del(struct linpool *pool, struct adata *list, u64 val)
   return res;
 }
 
-struct adata *
-lc_set_del(struct linpool *pool, struct adata *list, lcomm val)
+const struct adata *
+lc_set_del(struct linpool *pool, const struct adata *list, lcomm val)
 {
   if (!lc_set_contains(list, val))
     return list;
@@ -384,8 +384,8 @@ lc_set_del(struct linpool *pool, struct adata *list, lcomm val)
   return res;
 }
 
-struct adata *
-int_set_union(struct linpool *pool, struct adata *l1, struct adata *l2)
+const struct adata *
+int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2)
 {
   if (!l1)
     return l2;
@@ -414,8 +414,8 @@ int_set_union(struct linpool *pool, struct adata *l1, struct adata *l2)
   return res;
 }
 
-struct adata *
-ec_set_union(struct linpool *pool, struct adata *l1, struct adata *l2)
+const struct adata *
+ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2)
 {
   if (!l1)
     return l2;
@@ -447,8 +447,8 @@ ec_set_union(struct linpool *pool, struct adata *l1, struct adata *l2)
   return res;
 }
 
-struct adata *
-lc_set_union(struct linpool *pool, struct adata *l1, struct adata *l2)
+const struct adata *
+lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2)
 {
   if (!l1)
     return l2;
@@ -479,7 +479,7 @@ lc_set_union(struct linpool *pool, struct adata *l1, struct adata *l2)
 
 
 struct adata *
-ec_set_del_nontrans(struct linpool *pool, struct adata *set)
+ec_set_del_nontrans(struct linpool *pool, const struct adata *set)
 {
   adata *res = lp_alloc_adata(pool, set->length);
   u32 *src = int_set_get_data(set);
@@ -510,7 +510,7 @@ int_set_cmp(const void *X, const void *Y)
 }
 
 struct adata *
-int_set_sort(struct linpool *pool, struct adata *src)
+int_set_sort(struct linpool *pool, const struct adata *src)
 {
   struct adata *dst = lp_alloc_adata(pool, src->length);
   memcpy(dst->data, src->data, src->length);
@@ -528,7 +528,7 @@ ec_set_cmp(const void *X, const void *Y)
 }
 
 struct adata *
-ec_set_sort(struct linpool *pool, struct adata *src)
+ec_set_sort(struct linpool *pool, const struct adata *src)
 {
   struct adata *dst = lp_alloc_adata(pool, src->length);
   memcpy(dst->data, src->data, src->length);
@@ -558,7 +558,7 @@ lc_set_cmp(const void *X, const void *Y)
 }
 
 struct adata *
-lc_set_sort(struct linpool *pool, struct adata *src)
+lc_set_sort(struct linpool *pool, const struct adata *src)
 {
   struct adata *dst = lp_alloc_adata(pool, src->length);
   memcpy(dst->data, src->data, src->length);
diff --git a/nest/a-set_test.c b/nest/a-set_test.c
index a5081f9f..96b6a727 100644
--- a/nest/a-set_test.c
+++ b/nest/a-set_test.c
@@ -15,10 +15,10 @@
 #include "lib/resource.h"
 
 #define SET_SIZE 10
-static struct adata *set_sequence;		/* <0; SET_SIZE) */
-static struct adata *set_sequence_same;		/* <0; SET_SIZE) */
-static struct adata *set_sequence_higher;	/* <SET_SIZE; 2*SET_SIZE) */
-static struct adata *set_random;
+static const struct adata *set_sequence;		/* <0; SET_SIZE) */
+static const struct adata *set_sequence_same;		/* <0; SET_SIZE) */
+static const struct adata *set_sequence_higher;	/* <SET_SIZE; 2*SET_SIZE) */
+static const struct adata *set_random;
 
 #define BUFFER_SIZE 1000
 static byte buf[BUFFER_SIZE] = {};
@@ -34,14 +34,14 @@ enum set_type
 };
 
 static void
-generate_set_sequence(enum set_type type)
+generate_set_sequence(enum set_type type, int len)
 {
   struct adata empty_as_path = {};
   set_sequence = set_sequence_same = set_sequence_higher = set_random = &empty_as_path;
   lp = lp_new_default(&root_pool);
 
   int i;
-  for (i = 0; i < SET_SIZE; i++)
+  for (i = 0; i < len; i++)
   {
     if (type == SET_TYPE_INT)
     {
@@ -72,7 +72,7 @@ t_set_int_contains(void)
   int i;
 
   resource_init();
-  generate_set_sequence(SET_TYPE_INT);
+  generate_set_sequence(SET_TYPE_INT, SET_SIZE);
 
   bt_assert(int_set_get_size(set_sequence) == SET_SIZE);
 
@@ -93,9 +93,9 @@ static int
 t_set_int_union(void)
 {
   resource_init();
-  generate_set_sequence(SET_TYPE_INT);
+  generate_set_sequence(SET_TYPE_INT, SET_SIZE);
 
-  struct adata *set_union;
+  const struct adata *set_union;
   set_union = int_set_union(lp, set_sequence, set_sequence_same);
   bt_assert(int_set_get_size(set_union) == SET_SIZE);
   bt_assert(int_set_format(set_union, 0, 2, buf, BUFFER_SIZE) == 0);
@@ -112,9 +112,8 @@ static int
 t_set_int_format(void)
 {
   resource_init();
-  generate_set_sequence(SET_TYPE_INT);
+  generate_set_sequence(SET_TYPE_INT, SET_SIZE_FOR_FORMAT_OUTPUT);
 
-  set_sequence->length = 4 * SET_SIZE_FOR_FORMAT_OUTPUT; /* dirty */
   bt_assert(int_set_format(set_sequence, 0, 0, buf, BUFFER_SIZE) == 0);
   bt_assert(strcmp(buf, "0.0.0.0 0.0.0.1 0.0.0.2 0.0.0.3 0.0.0.4 0.0.0.5 0.0.0.6 0.0.0.7 0.0.0.8 0.0.0.9") == 0);
 
@@ -134,9 +133,9 @@ static int
 t_set_int_delete(void)
 {
   resource_init();
-  generate_set_sequence(SET_TYPE_INT);
+  generate_set_sequence(SET_TYPE_INT, SET_SIZE);
 
-  struct adata *deleting_sequence = set_sequence;
+  const struct adata *deleting_sequence = set_sequence;
   u32 i;
   for (i = 0; i < SET_SIZE; i++)
   {
@@ -162,7 +161,7 @@ t_set_ec_contains(void)
   u32 i;
 
   resource_init();
-  generate_set_sequence(SET_TYPE_EC);
+  generate_set_sequence(SET_TYPE_EC, SET_SIZE);
 
   bt_assert(ec_set_get_size(set_sequence) == SET_SIZE);
 
@@ -183,9 +182,9 @@ static int
 t_set_ec_union(void)
 {
   resource_init();
-  generate_set_sequence(SET_TYPE_EC);
+  generate_set_sequence(SET_TYPE_EC, SET_SIZE);
 
-  struct adata *set_union;
+  const struct adata *set_union;
   set_union = ec_set_union(lp, set_sequence, set_sequence_same);
   bt_assert(ec_set_get_size(set_union) == SET_SIZE);
   bt_assert(ec_set_format(set_union, 0, buf, BUFFER_SIZE) == 0);
@@ -203,7 +202,7 @@ t_set_ec_format(void)
 {
   resource_init();
 
-  struct adata empty_as_path = {};
+  const struct adata empty_as_path = {};
   set_sequence = set_sequence_same = set_sequence_higher = set_random = &empty_as_path;
   lp = lp_new_default(&root_pool);
 
@@ -224,9 +223,9 @@ static int
 t_set_ec_delete(void)
 {
   resource_init();
-  generate_set_sequence(SET_TYPE_EC);
+  generate_set_sequence(SET_TYPE_EC, SET_SIZE);
 
-  struct adata *deleting_sequence = set_sequence;
+  const struct adata *deleting_sequence = set_sequence;
   u32 i;
   for (i = 0; i < SET_SIZE; i++)
   {
diff --git a/nest/attrs.h b/nest/attrs.h
index 102f378a..d9d97136 100644
--- a/nest/attrs.h
+++ b/nest/attrs.h
@@ -31,15 +31,15 @@
 struct f_tree;
 
 int as_path_valid(byte *data, uint len, int bs, int confed, char *err, uint elen);
-int as_path_16to32(byte *dst, byte *src, uint len);
-int as_path_32to16(byte *dst, byte *src, uint len);
+int as_path_16to32(byte *dst, const byte *src, uint len);
+int as_path_32to16(byte *dst, const byte *src, uint len);
 int as_path_contains_as4(const struct adata *path);
 int as_path_contains_confed(const struct adata *path);
 struct adata *as_path_strip_confed(struct linpool *pool, const struct adata *op);
 struct adata *as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as);
 struct adata *as_path_to_old(struct linpool *pool, const struct adata *path);
-void as_path_cut(struct adata *path, uint num);
-struct adata *as_path_merge(struct linpool *pool, struct adata *p1, struct adata *p2);
+struct adata *as_path_cut(struct linpool *pool, const struct adata *path, uint num);
+const struct adata *as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2);
 void as_path_format(const struct adata *path, byte *buf, uint size);
 int as_path_getlen(const struct adata *path);
 int as_path_getlen_int(const struct adata *path, int bs);
@@ -48,8 +48,8 @@ int as_path_get_first_regular(const struct adata *path, u32 *last_as);
 int as_path_get_last(const struct adata *path, u32 *last_as);
 u32 as_path_get_last_nonaggregated(const struct adata *path);
 int as_path_contains(const struct adata *path, u32 as, int min);
-int as_path_match_set(const struct adata *path, struct f_tree *set);
-struct adata *as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos);
+int as_path_match_set(const struct adata *path, const struct f_tree *set);
+const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos);
 
 static inline struct adata *as_path_prepend(struct linpool *pool, const struct adata *path, u32 as)
 { return as_path_prepend2(pool, path, AS_PATH_SEQUENCE, as); }
@@ -61,20 +61,30 @@ static inline struct adata *as_path_prepend(struct linpool *pool, const struct a
 #define PM_ASN_EXPR	3
 #define PM_ASN_RANGE	4
 
-struct f_path_mask {
-  struct f_path_mask *next;
+struct f_path_mask_item {
+  union {
+    u32 asn; /* PM_ASN */
+    struct f_line *expr; /* PM_ASN_EXPR */
+    struct { /* PM_ASN_RANGE */
+      u32 from;
+      u32 to;
+    };
+  }; 
   int kind;
-  uintptr_t val;
-  uintptr_t val2;
 };
 
-int as_path_match(const struct adata *path, struct f_path_mask *mask);
+struct f_path_mask {
+  uint len;
+  struct f_path_mask_item item[0];
+};
+
+int as_path_match(const struct adata *path, const struct f_path_mask *mask);
 
 
 /* Counterparts to appropriate as_path_* functions */
 
 static inline int
-aggregator_16to32(byte *dst, byte *src)
+aggregator_16to32(byte *dst, const byte *src)
 {
   put_u32(dst, get_u16(src));
   memcpy(dst+4, src+2, 4);
@@ -82,7 +92,7 @@ aggregator_16to32(byte *dst, byte *src)
 }
 
 static inline int
-aggregator_32to16(byte *dst, byte *src)
+aggregator_32to16(byte *dst, const byte *src)
 {
   put_u16(dst, get_u32(src));
   memcpy(dst+2, src+4, 4);
@@ -90,13 +100,13 @@ aggregator_32to16(byte *dst, byte *src)
 }
 
 static inline int
-aggregator_contains_as4(struct adata *a)
+aggregator_contains_as4(const struct adata *a)
 {
   return get_u32(a->data) > 0xFFFF;
 }
 
 static inline struct adata *
-aggregator_to_old(struct linpool *pool, struct adata *a)
+aggregator_to_old(struct linpool *pool, const struct adata *a)
 {
   struct adata *d = lp_alloc_adata(pool, 8);
   put_u32(d->data, 0xFFFF);
@@ -109,26 +119,27 @@ aggregator_to_old(struct linpool *pool, struct adata *a)
 
 
 /* Extended Community subtypes (kinds) */
-#define EC_RT 0x0002
-#define EC_RO 0x0003
-
-#define EC_GENERIC 0xFFFF
+enum ec_subtype {
+  EC_RT = 0x0002,
+  EC_RO = 0x0003,
+  EC_GENERIC = 0xFFFF,
+} PACKED;
 
 /* Transitive bit (for first u32 half of EC) */
 #define EC_TBIT 0x40000000
 
 #define ECOMM_LENGTH 8
 
-static inline int int_set_get_size(struct adata *list)
+static inline int int_set_get_size(const struct adata *list)
 { return list->length / 4; }
 
-static inline int ec_set_get_size(struct adata *list)
+static inline int ec_set_get_size(const struct adata *list)
 { return list->length / 8; }
 
-static inline int lc_set_get_size(struct adata *list)
+static inline int lc_set_get_size(const struct adata *list)
 { return list->length / 12; }
 
-static inline u32 *int_set_get_data(struct adata *list)
+static inline u32 *int_set_get_data(const struct adata *list)
 { return (u32 *) list->data; }
 
 static inline u32 ec_hi(u64 ec) { return ec >> 32; }
@@ -137,16 +148,16 @@ static inline u64 ec_get(const u32 *l, int i)
 { return (((u64) l[i]) << 32) | l[i+1]; }
 
 /* RFC 4360 3.1.  Two-Octet AS Specific Extended Community */
-static inline u64 ec_as2(u64 kind, u64 key, u64 val)
-{ return ((kind | 0x0000) << 48) | (key << 32) | val; }
+static inline u64 ec_as2(enum ec_subtype kind, u64 key, u64 val)
+{ return (((u64) kind | 0x0000) << 48) | (key << 32) | val; }
 
 /* RFC 5668  4-Octet AS Specific BGP Extended Community */
-static inline u64 ec_as4(u64 kind, u64 key, u64 val)
-{ return ((kind | 0x0200) << 48) | (key << 16) | val; }
+static inline u64 ec_as4(enum ec_subtype kind, u64 key, u64 val)
+{ return (((u64) kind | 0x0200) << 48) | (key << 16) | val; }
 
 /* RFC 4360 3.2.  IPv4 Address Specific Extended Community */
-static inline u64 ec_ip4(u64 kind, u64 key, u64 val)
-{ return ((kind | 0x0100) << 48) | (key << 16) | val; }
+static inline u64 ec_ip4(enum ec_subtype kind, u64 key, u64 val)
+{ return (((u64) kind | 0x0100) << 48) | (key << 16) | val; }
 
 static inline u64 ec_generic(u64 key, u64 val)
 { return (key << 32) | val; }
@@ -173,29 +184,29 @@ static inline u32 *lc_copy(u32 *dst, const u32 *src)
 { memcpy(dst, src, LCOMM_LENGTH); return dst + 3; }
 
 
-int int_set_format(struct adata *set, int way, int from, byte *buf, uint size);
+int int_set_format(const struct adata *set, int way, int from, byte *buf, uint size);
 int ec_format(byte *buf, u64 ec);
-int ec_set_format(struct adata *set, int from, byte *buf, uint size);
+int ec_set_format(const struct adata *set, int from, byte *buf, uint size);
 int lc_format(byte *buf, lcomm lc);
-int lc_set_format(struct adata *set, int from, byte *buf, uint size);
-int int_set_contains(struct adata *list, u32 val);
-int ec_set_contains(struct adata *list, u64 val);
-int lc_set_contains(struct adata *list, lcomm val);
-struct adata *int_set_prepend(struct linpool *pool, struct adata *list, u32 val);
-struct adata *int_set_add(struct linpool *pool, struct adata *list, u32 val);
-struct adata *ec_set_add(struct linpool *pool, struct adata *list, u64 val);
-struct adata *lc_set_add(struct linpool *pool, struct adata *list, lcomm val);
-struct adata *int_set_del(struct linpool *pool, struct adata *list, u32 val);
-struct adata *ec_set_del(struct linpool *pool, struct adata *list, u64 val);
-struct adata *lc_set_del(struct linpool *pool, struct adata *list, lcomm val);
-struct adata *int_set_union(struct linpool *pool, struct adata *l1, struct adata *l2);
-struct adata *ec_set_union(struct linpool *pool, struct adata *l1, struct adata *l2);
-struct adata *lc_set_union(struct linpool *pool, struct adata *l1, struct adata *l2);
-
-struct adata *ec_set_del_nontrans(struct linpool *pool, struct adata *set);
-struct adata *int_set_sort(struct linpool *pool, struct adata *src);
-struct adata *ec_set_sort(struct linpool *pool, struct adata *src);
-struct adata *lc_set_sort(struct linpool *pool, struct adata *src);
+int lc_set_format(const struct adata *set, int from, byte *buf, uint size);
+int int_set_contains(const struct adata *list, u32 val);
+int ec_set_contains(const struct adata *list, u64 val);
+int lc_set_contains(const struct adata *list, lcomm val);
+const struct adata *int_set_prepend(struct linpool *pool, const struct adata *list, u32 val);
+const struct adata *int_set_add(struct linpool *pool, const struct adata *list, u32 val);
+const struct adata *ec_set_add(struct linpool *pool, const struct adata *list, u64 val);
+const struct adata *lc_set_add(struct linpool *pool, const struct adata *list, lcomm val);
+const struct adata *int_set_del(struct linpool *pool, const struct adata *list, u32 val);
+const struct adata *ec_set_del(struct linpool *pool, const struct adata *list, u64 val);
+const struct adata *lc_set_del(struct linpool *pool, const struct adata *list, lcomm val);
+const struct adata *int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2);
+const struct adata *ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2);
+const struct adata *lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2);
+
+struct adata *ec_set_del_nontrans(struct linpool *pool, const struct adata *set);
+struct adata *int_set_sort(struct linpool *pool, const struct adata *src);
+struct adata *ec_set_sort(struct linpool *pool, const struct adata *src);
+struct adata *lc_set_sort(struct linpool *pool, const struct adata *src);
 
 void ec_set_sort_x(struct adata *set); /* Sort in place */
 
diff --git a/nest/cmds.c b/nest/cmds.c
index 0c89d20f..6daafcb3 100644
--- a/nest/cmds.c
+++ b/nest/cmds.c
@@ -95,8 +95,9 @@ cmd_show_memory(void)
 }
 
 void
-cmd_eval(struct f_inst *expr)
+cmd_eval(const struct f_line *expr)
 {
+  /* TODO: Return directly the string from eval */
   struct f_val v;
   if (f_eval(expr, this_cli->parser_pool, &v) > F_RETURN)
     {
@@ -106,6 +107,6 @@ cmd_eval(struct f_inst *expr)
 
   buffer buf;
   LOG_BUFFER_INIT(buf);
-  val_format(v, &buf);
+  val_format(&v, &buf);
   cli_msg(23, "%s", buf.start);
 }
diff --git a/nest/cmds.h b/nest/cmds.h
index 4cf8fb1b..194a9d7f 100644
--- a/nest/cmds.h
+++ b/nest/cmds.h
@@ -16,4 +16,6 @@ struct f_inst;
 void cmd_show_status(void);
 void cmd_show_symbols(struct sym_show_data *sym);
 void cmd_show_memory(void);
-void cmd_eval(struct f_inst *expr);
+
+struct f_line;
+void cmd_eval(const struct f_line *expr);
diff --git a/nest/config.Y b/nest/config.Y
index aef5ed46..51fb0bd7 100644
--- a/nest/config.Y
+++ b/nest/config.Y
@@ -112,7 +112,7 @@ rtrid:
 
 idval:
    NUM { $$ = $1; }
- | '(' term ')' { $$ = f_eval_int($2); }
+ | '(' term ')' { $$ = f_eval_int(f_postfixify($2)); }
  | IP4 { $$ = ip4_to_u32($1); }
  | SYM {
      if ($1->class == (SYM_CONSTANT | T_INT) || $1->class == (SYM_CONSTANT | T_QUAD))
@@ -732,7 +732,7 @@ CF_CLI(DUMP PROTOCOLS,,, [[Dump protocol information]])
 { protos_dump_all(); cli_msg(0, ""); } ;
 
 CF_CLI(EVAL, term, <expr>, [[Evaluate an expression]])
-{ cmd_eval($2); } ;
+{ cmd_eval(f_postfixify($2)); } ;
 
 CF_CLI_HELP(ECHO, ..., [[Control echoing of log messages]])
 CF_CLI(ECHO, echo_mask echo_size, (all | off | { debug|trace|info|remote|warning|error|auth [, ...] }) [<buffer-size>], [[Control echoing of log messages]]) {
@@ -790,7 +790,7 @@ proto_patt2:
  | TEXT { $$.ptr = $1; $$.patt = 1; }
  ;
 
-dynamic_attr: IGP_METRIC { $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_GEN_IGP_METRIC); } ;
+dynamic_attr: IGP_METRIC { $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_GEN_IGP_METRIC); } ;
 
 
 CF_CODE
diff --git a/nest/route.h b/nest/route.h
index 74446f48..c7ed80ff 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -473,7 +473,7 @@ typedef struct eattr {
   byte type;				/* Attribute type and several flags (EAF_...) */
   union {
     u32 data;
-    struct adata *ptr;			/* Attribute data elsewhere */
+    const struct adata *ptr;			/* Attribute data elsewhere */
   } u;
 } eattr;
 
@@ -517,6 +517,8 @@ typedef struct adata {
   byte data[0];
 } adata;
 
+extern const adata null_adata;		/* adata of length 0 */
+
 static inline struct adata *
 lp_alloc_adata(struct linpool *pool, uint len)
 {
@@ -525,7 +527,7 @@ lp_alloc_adata(struct linpool *pool, uint len)
   return ad;
 }
 
-static inline int adata_same(struct adata *a, struct adata *b)
+static inline int adata_same(const struct adata *a, const struct adata *b)
 { return (a->length == b->length && !memcmp(a->data, b->data, a->length)); }
 
 
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index 3e4578b0..01e807fa 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -58,6 +58,8 @@
 
 #include <stddef.h>
 
+const adata null_adata;		/* adata of length 0 */
+
 const char * const rta_src_names[RTS_MAX] = {
   [RTS_DUMMY]		= "",
   [RTS_STATIC]		= "static",
@@ -763,7 +765,7 @@ ea_free(ea_list *o)
 	{
 	  eattr *a = &o->attrs[i];
 	  if (!(a->type & EAF_EMBEDDED))
-	    mb_free(a->u.ptr);
+	    mb_free((void *) a->u.ptr);
 	}
       mb_free(o);
     }
@@ -808,7 +810,7 @@ ea_format_bitfield(struct eattr *a, byte *buf, int bufsize, const char **names,
 }
 
 static inline void
-opaque_format(struct adata *ad, byte *buf, uint size)
+opaque_format(const struct adata *ad, byte *buf, uint size)
 {
   byte *bound = buf + size - 10;
   uint i;
@@ -831,7 +833,7 @@ opaque_format(struct adata *ad, byte *buf, uint size)
 }
 
 static inline void
-ea_show_int_set(struct cli *c, struct adata *ad, int way, byte *pos, byte *buf, byte *end)
+ea_show_int_set(struct cli *c, const struct adata *ad, int way, byte *pos, byte *buf, byte *end)
 {
   int i = int_set_format(ad, way, 0, pos, end - pos);
   cli_printf(c, -1012, "\t%s", buf);
@@ -843,7 +845,7 @@ ea_show_int_set(struct cli *c, struct adata *ad, int way, byte *pos, byte *buf,
 }
 
 static inline void
-ea_show_ec_set(struct cli *c, struct adata *ad, byte *pos, byte *buf, byte *end)
+ea_show_ec_set(struct cli *c, const struct adata *ad, byte *pos, byte *buf, byte *end)
 {
   int i = ec_set_format(ad, 0, pos, end - pos);
   cli_printf(c, -1012, "\t%s", buf);
@@ -855,7 +857,7 @@ ea_show_ec_set(struct cli *c, struct adata *ad, byte *pos, byte *buf, byte *end)
 }
 
 static inline void
-ea_show_lc_set(struct cli *c, struct adata *ad, byte *pos, byte *buf, byte *end)
+ea_show_lc_set(struct cli *c, const struct adata *ad, byte *pos, byte *buf, byte *end)
 {
   int i = lc_set_format(ad, 0, pos, end - pos);
   cli_printf(c, -1012, "\t%s", buf);
@@ -882,7 +884,7 @@ ea_show(struct cli *c, eattr *e)
 {
   struct protocol *p;
   int status = GA_UNKNOWN;
-  struct adata *ad = (e->type & EAF_EMBEDDED) ? NULL : e->u.ptr;
+  const struct adata *ad = (e->type & EAF_EMBEDDED) ? NULL : e->u.ptr;
   byte buf[CLI_MSG_SIZE];
   byte *pos = buf, *end = buf + sizeof(buf);
 
@@ -1023,7 +1025,7 @@ ea_hash(ea_list *e)
 	    h ^= a->u.data;
 	  else
 	    {
-	      struct adata *d = a->u.ptr;
+	      const struct adata *d = a->u.ptr;
 	      h ^= mem_hash(d->data, d->length);
 	    }
 	  h *= mul;