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.

4 files changed, 36 insertions, 39 deletions

diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c
index cbb22038..7c6f2ee9 100644
--- a/proto/bgp/attrs.c
+++ b/proto/bgp/attrs.c
@@ -181,7 +181,7 @@ bgp_encode_u32s(struct bgp_write_state *s UNUSED, eattr *a, byte *buf, uint size
 }
 
 static int
-bgp_put_attr(byte *buf, uint size, uint code, uint flags, byte *data, uint len)
+bgp_put_attr(byte *buf, uint size, uint code, uint flags, const byte *data, uint len)
 {
   if (size < (4+len))
     return -1;
@@ -234,15 +234,15 @@ bgp_format_origin(eattr *a, byte *buf, uint size UNUSED)
 static int
 bgp_encode_as_path(struct bgp_write_state *s, eattr *a, byte *buf, uint size)
 {
-  byte *data = a->u.ptr->data;
+  const byte *data = a->u.ptr->data;
   uint len = a->u.ptr->length;
 
   if (!s->as4_session)
   {
     /* Prepare 16-bit AS_PATH (from 32-bit one) in a temporary buffer */
-    byte *src = data;
-    data = alloca(len);
-    len = as_path_32to16(data, src, len);
+    byte *dst = alloca(len);
+    len = as_path_32to16(dst, data, len);
+    data = dst;
   }
 
   return bgp_put_attr(buf, size, BA_AS_PATH, a->flags, data, len);
@@ -381,15 +381,14 @@ bgp_decode_atomic_aggr(struct bgp_parse_state *s, uint code UNUSED, uint flags,
 static int
 bgp_encode_aggregator(struct bgp_write_state *s, eattr *a, byte *buf, uint size)
 {
-  byte *data = a->u.ptr->data;
+  const byte *data = a->u.ptr->data;
   uint len = a->u.ptr->length;
 
   if (!s->as4_session)
   {
     /* Prepare 16-bit AGGREGATOR (from 32-bit one) in a temporary buffer */
-    byte *src = data;
-    data = alloca(6);
-    len = aggregator_32to16(data, src);
+    byte *dst = alloca(6);
+    len = aggregator_32to16(dst, data);
   }
 
   return bgp_put_attr(buf, size, BA_AGGREGATOR, a->flags, data, len);
@@ -415,7 +414,7 @@ bgp_decode_aggregator(struct bgp_parse_state *s, uint code UNUSED, uint flags, b
 static void
 bgp_format_aggregator(eattr *a, byte *buf, uint size UNUSED)
 {
-  byte *data = a->u.ptr->data;
+  const byte *data = a->u.ptr->data;
 
   bsprintf(buf, "%I4 AS%u", get_ip4(data+4), get_u32(data+0));
 }
@@ -545,12 +544,13 @@ bgp_decode_mp_unreach_nlri(struct bgp_parse_state *s, uint code UNUSED, uint fla
 static void
 bgp_export_ext_community(struct bgp_export_state *s, eattr *a)
 {
-  a->u.ptr = ec_set_del_nontrans(s->pool, a->u.ptr);
+  struct adata *ad = ec_set_del_nontrans(s->pool, a->u.ptr);
 
-  if (a->u.ptr->length == 0)
+  if (ad->length == 0)
     UNSET(a);
 
-  ec_set_sort_x(a->u.ptr);
+  ec_set_sort_x(ad);
+  a->u.ptr = ad;
 }
 
 static void
@@ -1232,7 +1232,7 @@ bgp_get_bucket(struct bgp_channel *c, ea_list *new)
 
     if (!(a->type & EAF_EMBEDDED))
     {
-      struct adata *oa = a->u.ptr;
+      const struct adata *oa = a->u.ptr;
       struct adata *na = (struct adata *) dest;
       memcpy(na, oa, sizeof(struct adata) + oa->length);
       a->u.ptr = na;
@@ -1404,7 +1404,7 @@ bgp_preexport(struct proto *P, rte **new, struct linpool *pool UNUSED)
   if (p->cf->interpret_communities &&
       (c = ea_find(e->attrs->eattrs, EA_CODE(PROTOCOL_BGP, BA_COMMUNITY))))
   {
-    struct adata *d = c->u.ptr;
+    const struct adata *d = c->u.ptr;
 
     /* Do not export anywhere */
     if (int_set_contains(d, BGP_COMM_NO_ADVERTISE))
@@ -1426,9 +1426,6 @@ bgp_preexport(struct proto *P, rte **new, struct linpool *pool UNUSED)
   return 0;
 }
 
-
-static adata null_adata;	/* adata of length 0 */
-
 static ea_list *
 bgp_update_attrs(struct bgp_proto *p, struct bgp_channel *c, rte *e, ea_list *attrs0, struct linpool *pool)
 {
@@ -1437,7 +1434,7 @@ bgp_update_attrs(struct bgp_proto *p, struct bgp_channel *c, rte *e, ea_list *at
   struct bgp_export_state s = { .proto = p, .channel = c, .pool = pool, .src = src, .route = e, .mpls = c->desc->mpls };
   ea_list *attrs = attrs0;
   eattr *a;
-  adata *ad;
+  const adata *ad;
 
   /* ORIGIN attribute - mandatory, attach if missing */
   if (! bgp_find_attr(attrs0, BA_ORIGIN))
@@ -1962,7 +1959,7 @@ struct rte *
 bgp_rte_modify_stale(struct rte *r, struct linpool *pool)
 {
   eattr *a = ea_find(r->attrs->eattrs, EA_CODE(PROTOCOL_BGP, BA_COMMUNITY));
-  struct adata *ad = a ? a->u.ptr : NULL;
+  const struct adata *ad = a ? a->u.ptr : NULL;
   uint flags = a ? a->flags : BAF_PARTIAL;
 
   if (ad && int_set_contains(ad, BGP_COMM_NO_LLGR))
@@ -2021,8 +2018,8 @@ bgp_process_as4_attrs(ea_list **attrs, struct linpool *pool)
       return;
 
     /* Merge AS_PATH and AS4_PATH */
-    as_path_cut(p2->u.ptr, p2_len - p4_len);
-    p2->u.ptr = as_path_merge(pool, p2->u.ptr, p4->u.ptr);
+    struct adata *apc = as_path_cut(pool, p2->u.ptr, p2_len - p4_len);
+    p2->u.ptr = as_path_merge(pool, apc, p4->u.ptr);
   }
 }
 
diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h
index cfc88d8e..b604c7aa 100644
--- a/proto/bgp/bgp.h
+++ b/proto/bgp/bgp.h
@@ -376,7 +376,7 @@ struct bgp_write_state {
   int mpls;
 
   eattr *mp_next_hop;
-  adata *mpls_labels;
+  const adata *mpls_labels;
 };
 
 struct bgp_parse_state {
@@ -507,7 +507,7 @@ bgp_set_attr_u32(ea_list **to, struct linpool *pool, uint code, uint flags, u32
 { bgp_set_attr(to, pool, code, flags, (uintptr_t) val); }
 
 static inline void
-bgp_set_attr_ptr(ea_list **to, struct linpool *pool, uint code, uint flags, struct adata *val)
+bgp_set_attr_ptr(ea_list **to, struct linpool *pool, uint code, uint flags, const struct adata *val)
 { bgp_set_attr(to, pool, code, flags, (uintptr_t) val); }
 
 static inline void
diff --git a/proto/bgp/config.Y b/proto/bgp/config.Y
index ac8d024a..f9e5efaf 100644
--- a/proto/bgp/config.Y
+++ b/proto/bgp/config.Y
@@ -272,29 +272,29 @@ bgp_proto_channel: bgp_channel_start bgp_channel_opt_list bgp_channel_end;
 
 
 dynamic_attr: BGP_ORIGIN
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_ENUM_BGP_ORIGIN, EA_CODE(PROTOCOL_BGP, BA_ORIGIN)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_ENUM_BGP_ORIGIN, EA_CODE(PROTOCOL_BGP, BA_ORIGIN)); } ;
 dynamic_attr: BGP_PATH
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_AS_PATH, T_PATH, EA_CODE(PROTOCOL_BGP, BA_AS_PATH)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_AS_PATH, 0, T_PATH, EA_CODE(PROTOCOL_BGP, BA_AS_PATH)); } ;
 dynamic_attr: BGP_NEXT_HOP
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_IP_ADDRESS, T_IP, EA_CODE(PROTOCOL_BGP, BA_NEXT_HOP)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_IP_ADDRESS, 0, T_IP, EA_CODE(PROTOCOL_BGP, BA_NEXT_HOP)); } ;
 dynamic_attr: BGP_MED
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_CODE(PROTOCOL_BGP, BA_MULTI_EXIT_DISC)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_CODE(PROTOCOL_BGP, BA_MULTI_EXIT_DISC)); } ;
 dynamic_attr: BGP_LOCAL_PREF
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_CODE(PROTOCOL_BGP, BA_LOCAL_PREF)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_CODE(PROTOCOL_BGP, BA_LOCAL_PREF)); } ;
 dynamic_attr: BGP_ATOMIC_AGGR
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_OPAQUE, T_ENUM_EMPTY, EA_CODE(PROTOCOL_BGP, BA_ATOMIC_AGGR)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_OPAQUE, 0, T_ENUM_EMPTY, EA_CODE(PROTOCOL_BGP, BA_ATOMIC_AGGR)); } ;
 dynamic_attr: BGP_AGGREGATOR
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_CODE(PROTOCOL_BGP, BA_AGGREGATOR)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_CODE(PROTOCOL_BGP, BA_AGGREGATOR)); } ;
 dynamic_attr: BGP_COMMUNITY
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT_SET, T_CLIST, EA_CODE(PROTOCOL_BGP, BA_COMMUNITY)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT_SET, 0, T_CLIST, EA_CODE(PROTOCOL_BGP, BA_COMMUNITY)); } ;
 dynamic_attr: BGP_ORIGINATOR_ID
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_ROUTER_ID, T_QUAD, EA_CODE(PROTOCOL_BGP, BA_ORIGINATOR_ID)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_ROUTER_ID, 0, T_QUAD, EA_CODE(PROTOCOL_BGP, BA_ORIGINATOR_ID)); } ;
 dynamic_attr: BGP_CLUSTER_LIST
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT_SET, T_CLIST, EA_CODE(PROTOCOL_BGP, BA_CLUSTER_LIST)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_INT_SET, 0, T_CLIST, EA_CODE(PROTOCOL_BGP, BA_CLUSTER_LIST)); } ;
 dynamic_attr: BGP_EXT_COMMUNITY
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_EC_SET, T_ECLIST, EA_CODE(PROTOCOL_BGP, BA_EXT_COMMUNITY)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_EC_SET, 0, T_ECLIST, EA_CODE(PROTOCOL_BGP, BA_EXT_COMMUNITY)); } ;
 dynamic_attr: BGP_LARGE_COMMUNITY
-	{ $$ = f_new_dynamic_attr(EAF_TYPE_LC_SET, T_LCLIST, EA_CODE(PROTOCOL_BGP, BA_LARGE_COMMUNITY)); } ;
+	{ $$ = f_new_dynamic_attr(EAF_TYPE_LC_SET, 0, T_LCLIST, EA_CODE(PROTOCOL_BGP, BA_LARGE_COMMUNITY)); } ;
 
 
 
diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c
index 26716573..2b5cc440 100644
--- a/proto/bgp/packets.c
+++ b/proto/bgp/packets.c
@@ -1210,10 +1210,10 @@ bgp_rte_update(struct bgp_parse_state *s, net_addr *n, u32 path_id, rta *a0)
 }
 
 static void
-bgp_encode_mpls_labels(struct bgp_write_state *s UNUSED, adata *mpls, byte **pos, uint *size, byte *pxlen)
+bgp_encode_mpls_labels(struct bgp_write_state *s UNUSED, const adata *mpls, byte **pos, uint *size, byte *pxlen)
 {
-  u32 dummy = 0;
-  u32 *labels = mpls ? (u32 *) mpls->data : &dummy;
+  const u32 dummy = 0;
+  const u32 *labels = mpls ? (const u32 *) mpls->data : &dummy;
   uint lnum = mpls ? (mpls->length / 4) : 1;
 
   for (uint i = 0; i < lnum; i++)