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.

11 files changed, 52 insertions, 52 deletions

diff --git a/proto/babel/config.Y b/proto/babel/config.Y
index 3af79fd6..b93a423b 100644
--- a/proto/babel/config.Y
+++ b/proto/babel/config.Y
@@ -125,7 +125,7 @@ babel_iface_opt_list:
 babel_iface:
   babel_iface_start iface_patt_list_nopx babel_iface_opt_list babel_iface_finish;
 
-dynamic_attr: BABEL_METRIC { $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_BABEL_METRIC); } ;
+dynamic_attr: BABEL_METRIC { $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_BABEL_METRIC); } ;
 
 CF_CLI_HELP(SHOW BABEL, ..., [[Show information about Babel protocol]]);
 
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++)
diff --git a/proto/ospf/config.Y b/proto/ospf/config.Y
index 36fbd5f1..9669b708 100644
--- a/proto/ospf/config.Y
+++ b/proto/ospf/config.Y
@@ -498,10 +498,10 @@ ospf_iface:
   ospf_iface_start ospf_iface_patt_list ospf_iface_opt_list { ospf_iface_finish(); }
  ;
 
-dynamic_attr: OSPF_METRIC1 { $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_OSPF_METRIC1); } ;
-dynamic_attr: OSPF_METRIC2 { $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_OSPF_METRIC2); } ;
-dynamic_attr: OSPF_TAG { $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_OSPF_TAG); } ;
-dynamic_attr: OSPF_ROUTER_ID { $$ = f_new_dynamic_attr(EAF_TYPE_ROUTER_ID, T_QUAD, EA_OSPF_ROUTER_ID); } ;
+dynamic_attr: OSPF_METRIC1 { $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_OSPF_METRIC1); } ;
+dynamic_attr: OSPF_METRIC2 { $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_OSPF_METRIC2); } ;
+dynamic_attr: OSPF_TAG { $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_OSPF_TAG); } ;
+dynamic_attr: OSPF_ROUTER_ID { $$ = f_new_dynamic_attr(EAF_TYPE_ROUTER_ID, 0, T_QUAD, EA_OSPF_ROUTER_ID); } ;
 
 CF_CLI_HELP(SHOW OSPF, ..., [[Show information about OSPF protocol]]);
 CF_CLI(SHOW OSPF, optsym, [<name>], [[Show information about OSPF protocol]])
diff --git a/proto/radv/config.Y b/proto/radv/config.Y
index 53715f77..b8eeb439 100644
--- a/proto/radv/config.Y
+++ b/proto/radv/config.Y
@@ -332,8 +332,8 @@ radv_sensitive:
  | SENSITIVE bool { $$ = $2; }
  ;
 
-dynamic_attr: RA_PREFERENCE { $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_ENUM_RA_PREFERENCE, EA_RA_PREFERENCE); } ;
-dynamic_attr: RA_LIFETIME { $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_RA_LIFETIME); } ;
+dynamic_attr: RA_PREFERENCE { $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_ENUM_RA_PREFERENCE, EA_RA_PREFERENCE); } ;
+dynamic_attr: RA_LIFETIME { $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_RA_LIFETIME); } ;
 
 CF_CODE
 
diff --git a/proto/rip/config.Y b/proto/rip/config.Y
index 172299d0..265912b2 100644
--- a/proto/rip/config.Y
+++ b/proto/rip/config.Y
@@ -186,8 +186,8 @@ rip_iface:
   rip_iface_start iface_patt_list_nopx rip_iface_opt_list rip_iface_finish;
 
 
-dynamic_attr: RIP_METRIC { $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_RIP_METRIC); } ;
-dynamic_attr: RIP_TAG { $$ = f_new_dynamic_attr(EAF_TYPE_INT, T_INT, EA_RIP_TAG); } ;
+dynamic_attr: RIP_METRIC { $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_RIP_METRIC); } ;
+dynamic_attr: RIP_TAG { $$ = f_new_dynamic_attr(EAF_TYPE_INT, 0, T_INT, EA_RIP_TAG); } ;
 
 CF_CLI_HELP(SHOW RIP, ..., [[Show information about RIP protocol]]);
 
diff --git a/proto/static/config.Y b/proto/static/config.Y
index d7a02961..56caef24 100644
--- a/proto/static/config.Y
+++ b/proto/static/config.Y
@@ -14,7 +14,7 @@ CF_DEFINES
 
 #define STATIC_CFG ((struct static_config *) this_proto)
 static struct static_route *this_srt, *this_snh;
-static struct f_inst **this_srt_last_cmd;
+static struct f_inst *this_srt_cmds, **this_srt_last_cmd;
 
 static struct static_route *
 static_nexthop_new(void)
@@ -39,6 +39,8 @@ static_route_finish(void)
 {
   if (net_type_match(this_srt->net, NB_DEST) == !this_srt->dest)
     cf_error("Unexpected or missing nexthop/type");
+
+  this_srt->cmds = f_postfixify(this_srt_cmds);
 }
 
 CF_DECLS
@@ -108,7 +110,8 @@ stat_route0: ROUTE net_any {
      this_srt = cfg_allocz(sizeof(struct static_route));
      add_tail(&STATIC_CFG->routes, &this_srt->n);
      this_srt->net = $2;
-     this_srt_last_cmd = &(this_srt->cmds);
+     this_srt_cmds = NULL;
+     this_srt_last_cmd = &this_srt_cmds;
      this_srt->mp_next = NULL;
      this_snh = NULL;
   }
diff --git a/proto/static/static.c b/proto/static/static.c
index 75a74ad0..2fa687eb 100644
--- a/proto/static/static.c
+++ b/proto/static/static.c
@@ -308,7 +308,7 @@ static inline int
 static_same_rte(struct static_route *or, struct static_route *nr)
 {
   /* Note that i_same() requires arguments in (new, old) order */
-  return static_same_dest(or, nr) && i_same(nr->cmds, or->cmds);
+  return static_same_dest(or, nr) && f_same(nr->cmds, or->cmds);
 }
 
 static void
diff --git a/proto/static/static.h b/proto/static/static.h
index a3c30b87..f736996c 100644
--- a/proto/static/static.h
+++ b/proto/static/static.h
@@ -39,7 +39,7 @@ struct static_route {
   struct static_route *chain;		/* Next for the same neighbor */
   struct static_route *mp_head;		/* First nexthop of this route */
   struct static_route *mp_next;		/* Nexthops for multipath routes */
-  struct f_inst *cmds;			/* List of commands for setting attributes */
+  struct f_line *cmds;			/* List of commands for setting attributes */
   byte dest;				/* Destination type (RTD_*) */
   byte state;				/* State of route announcement (SRS_*) */
   byte active;				/* Next hop is active (nbr/iface/BFD available) */