Nest: Implement BGP path mask loop operator

Implement regex-like '+' operator in BGP path masks to match previous
path mask item multiple times. This is useful as ASNs may appear
multiple times in paths due to path prepending for traffic engineering
purposes.

diff --git a/doc/bird.sgml b/doc/bird.sgml
index 1808d04cbdb087538a349d3dcbc7bf3c91cca087..786f124b7f105e8e074ce85a4449c2c96691cb88 100644 (file)
--- a/doc/bird.sgml
+++ b/doc/bird.sgml
@@ -1471,11 +1471,16 @@ in the foot).
        <cf/*/ matches any (even empty) sequence of arbitrary AS numbers and
        <cf/?/ matches one arbitrary AS number. For example, if <cf>bgp_path</cf>
        is 4 3 2 1, then: <tt>bgp_path &tilde; [= * 4 3 * =]</tt> is true,
-       but <tt>bgp_path &tilde; [= * 4 5 * =]</tt> is false. BGP mask
-       expressions can also contain integer expressions enclosed in parenthesis
-       and integer variables, for example <tt>[= * 4 (1+2) a =]</tt>. You can
-       also use ranges (e.g. <tt>[= * 3..5 2 100..200 * =]</tt>) and sets
-       (e.g. <tt>[= 1 2 [3, 5, 7] * =]</tt>).
+       but <tt>bgp_path &tilde; [= * 4 5 * =]</tt> is false. There is also
+       <cf/+/ operator which matches one or multiple instances of previous
+       expression, e.g. <tt>[= 1 2+ 3 =]</tt> matches both path 1 2 3 and path
+       1 2 2 2 3, but not 1 3 nor 1 2 4 3. Note that while <cf/*/ and <cf/?/
+       are wildcard-style operators, <cf/+/ is regex-style operator.
+
+       BGP mask expressions can also contain integer expressions enclosed in
+       parenthesis and integer variables, for example <tt>[= * 4 (1+2) a =]</tt>.
+       You can also use ranges (e.g. <tt>[= * 3..5 2 100..200 * =]</tt>)
+       and sets (e.g. <tt>[= 1 2 [3, 5, 7] * =]</tt>).
 
        <tag><label id="type-clist">clist</tag>
        Clist is similar to a set, except that unlike other sets, it can be

diff --git a/filter/config.Y b/filter/config.Y
index 77424a8b21c67586003f69cc481b9cdc9470861a..557a951f07517b8151d1bb2ef382bef02c03a481 100644 (file)
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -662,6 +662,7 @@ bgp_path_tail:
  }
  | '*' bgp_path_tail           { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .kind = PM_ASTERISK }, }); $$->next = $2; }
  | '?' bgp_path_tail           { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .kind = PM_QUESTION }, }); $$->next = $2; }
+ | '+' bgp_path_tail           { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .kind = PM_LOOP }, }); $$->next = $2; }
  | bgp_path_expr bgp_path_tail { $$ = $1; $$->next = $2; }
  |                             { $$ = NULL; }
  ;

diff --git a/filter/data.c b/filter/data.c
index 62edd9e0e24216fe7ebbe5153b21a872739f8f1b..402202554c2f73ed4b345ce67e65b270026eb298 100644 (file)
--- a/filter/data.c
+++ b/filter/data.c
@@ -93,6 +93,8 @@ adata_empty(struct linpool *pool, int l)
 static void
 pm_format(const struct f_path_mask *p, buffer *buf)
 {
+  int loop = 0;
+
   buffer_puts(buf, "[= ");
 
   for (uint i=0; i<p->len; i++)
@@ -111,6 +113,10 @@ pm_format(const struct f_path_mask *p, buffer *buf)
       buffer_puts(buf, "* ");
       break;
 
+    case PM_LOOP:
+      loop = 1;
+      break;
+
     case PM_ASN_RANGE:
       buffer_print(buf, "%u..%u ", p->item[i].from, p->item[i].to);
       break;
@@ -119,6 +125,11 @@ pm_format(const struct f_path_mask *p, buffer *buf)
       ASSERT(0);
     }
 
+    if (loop && (p->item[i].kind != PM_LOOP))
+    {
+      buffer_puts(buf, "+ ");
+      loop = 0;
+    }
   }
 
   buffer_puts(buf, "=]");

diff --git a/filter/f-inst.c b/filter/f-inst.c
index 63a6bdab22a5bc1264c4378183b36351c9f5c1af..df908e26e8fcdd5ebcbfbf0760ecf5250b296494 100644 (file)
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -311,6 +311,17 @@
     for (uint i=0; i<whati->varcount; i++) {
       switch (vv(i).type) {
        case T_PATH_MASK_ITEM:
+         if (vv(i).val.pmi.kind == PM_LOOP)
+         {
+           if (i == 0)
+             runtime("Path mask iterator '+' cannot be first");
+
+           /* We want PM_LOOP as prefix operator */
+           pm->item[i] = pm->item[i - 1];
+           pm->item[i - 1] = vv(i).val.pmi;
+           break;
+         }
+
          pm->item[i] = vv(i).val.pmi;
          break;
 

diff --git a/filter/test.conf b/filter/test.conf
index 634816fd90471c6afd336612ee021e796de28cb1..63af25bb40d1c7fe74d3a28bf094de44b0d944c0 100644 (file)
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -646,7 +646,6 @@ int set set12;
        bt_assert(delete(p2, 3) = prepend(prepend(prepend(prepend(+empty+, 1), 2), 4), 5));
        bt_assert(filter(p2, [1..3]) = prepend(prepend(prepend(+empty+, 1), 2), 3));
 
-       pm1 = [= 1 2 * 3 4 5 =];
        p2 = prepend( + empty +, 5 );
        p2 = prepend( p2, 4 );
        p2 = prepend( p2, 3 );
@@ -654,9 +653,17 @@ int set set12;
        p2 = prepend( p2, 2 );
        p2 = prepend( p2, 1 );
 
-       bt_assert(p2 ~ pm1);
+       bt_assert(p2 !~ [= 1 2 3 4 5 =]);
+       bt_assert(p2 ~ [= 1 2 * 4 5 =]);
+       bt_assert(p2 ~ [= 1 2 * 3 4 5 =]);
+       bt_assert(p2 ~ [= 1 2 3+ 4 5 =]);
+       bt_assert(p2 ~ [= 1 2 3+ 4+ 5 =]);
+       bt_assert(p2 !~ [= 1 2 3+ 5+ 4 5 =]);
+       bt_assert(p2 !~ [= 1 2 3 3 5+ 4 5 =]);
        bt_assert(delete(p2, 3) = prepend(prepend(prepend(prepend(+empty+, 5), 4), 2), 1));
        bt_assert(delete(p2, [4..5]) = prepend(prepend(prepend(prepend(+empty+, 3), 3), 2), 1));
+
+       bt_assert(format([= 1 2+ 3 =]) = "[= 1 2 + 3 =]");
 }
 
 bt_test_suite(t_path, "Testing paths");

diff --git a/nest/a-path.c b/nest/a-path.c
index cffd46ab202c37f11573cd304b2be1d8cdc1327c..2e34a3d1c2eaf16cf8df4641652b9ec35a34cb1c 100644 (file)
--- a/nest/a-path.c
+++ b/nest/a-path.c
@@ -727,7 +727,7 @@ parse_path(const struct adata *path, struct pm_pos *pp)
 }
 
 static int
-pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
+pm_match_val(const struct pm_pos *pos, u32 asn, u32 asn2)
 {
   u32 gas;
   if (! pos->set)
@@ -749,7 +749,7 @@ pm_match(struct pm_pos *pos, u32 asn, u32 asn2)
 }
 
 static int
-pm_match_set(struct pm_pos *pos, const struct f_tree *set)
+pm_match_set(const struct pm_pos *pos, const struct f_tree *set)
 {
   struct f_val asn = { .type = T_INT };
 
@@ -773,25 +773,34 @@ pm_match_set(struct pm_pos *pos, const struct f_tree *set)
   return 0;
 }
 
+static inline int
+pm_match(const struct pm_pos *pos, const struct f_path_mask_item *mask, u32 asn, u32 asn2)
+{
+  return ((mask->kind == PM_QUESTION) ||
+         ((mask->kind != PM_ASN_SET) ?
+          pm_match_val(pos, asn, asn2) :
+          pm_match_set(pos, mask->set)));
+}
+
 static void
-pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
+pm_mark(struct pm_pos *pos, int *i, int plen, int *nl, int *nh)
 {
-  int j;
+  int j = *i;
 
-  if (pos[i].set)
-    pos[i].mark = 1;
+  if (pos[j].set)
+    do { pos[j].mark = 1; j++; }
+    while ((j < plen) && pos[j].set);
+  else
+    j++;
 
-  for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
-    pos[j].mark = 1;
   pos[j].mark = 1;
 
-  /* We are going downwards, therefore every mark is
-     new low and just the first mark is new high */
-
-  *nl = i + (pos[i].set ? 0 : 1);
+  /* Update low, high based on first and last marked pos */
+  int l = pos[*i].set ? *i : j;
 
-  if (*nh < 0)
-    *nh = j;
+  *nl = (*nl < 0) ? l : MIN(*nl, l);
+  *nh = MAX(*nh, j);
+  *i = j;
 }
 
 /* AS path matching is nontrivial. Because AS path can
@@ -821,7 +830,7 @@ 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);
-  int l, h, i, nh, nl;
+  int l, h, i, nh, nl, last, loop;
   u32 val = 0;
   u32 val2 = 0;
 
@@ -831,7 +840,7 @@ as_path_match(const struct adata *path, const struct f_path_mask *mask)
   pos[plen].set = 0;
   pos[plen].mark = 0;
 
-  l = h = 0;
+  l = h = loop = 0;
   pos[0].mark = 1;
 
   for (uint m=0; m < mask->len; m++)
@@ -847,6 +856,10 @@ as_path_match(const struct adata *path, const struct f_path_mask *mask)
          h = plen;
          break;
 
+       case PM_LOOP:
+         loop = 1;
+         break;
+
        case PM_ASN:    /* Define single ASN as ASN..ASN - very narrow interval */
          val2 = val = mask->item[m].asn;
          goto step;
@@ -860,15 +873,22 @@ as_path_match(const struct adata *path, const struct f_path_mask *mask)
        case PM_ASN_SET:
        step:
          nh = nl = -1;
+         last = plen;
          for (i = h; i >= l; i--)
            if (pos[i].mark)
              {
                pos[i].mark = 0;
-               if ((mask->item[m].kind == PM_QUESTION) ||
-                   ((mask->item[m].kind != PM_ASN_SET) ?
-                    pm_match(pos + i, val, val2) :
-                    pm_match_set(pos + i, mask->item[m].set)))
-                 pm_mark(pos, i, plen, &nl, &nh);
+               int j = i;
+
+             match:
+               if (pm_match(pos + j, &mask->item[m], val, val2))
+               {
+                 pm_mark(pos, &j, plen, &nl, &nh);
+                 if (loop && (j < last))
+                   goto match;
+               }
+
+               last = i;
              }
 
          if (nh < 0)
@@ -876,6 +896,7 @@ as_path_match(const struct adata *path, const struct f_path_mask *mask)
 
          h = nh;
          l = nl;
+         loop = 0;
          break;
        }
     }

diff --git a/nest/attrs.h b/nest/attrs.h
index d88a73f340f702dba9ca07777c27bb8583f467cb..50da817be20aca3cffe1571c8bff73569d661879 100644 (file)
--- a/nest/attrs.h
+++ b/nest/attrs.h
@@ -61,6 +61,7 @@ static inline struct adata *as_path_prepend(struct linpool *pool, const struct a
 #define PM_ASN_EXPR    3
 #define PM_ASN_RANGE   4
 #define PM_ASN_SET     5
+#define PM_LOOP                6
 
 struct f_path_mask_item {
   union {