summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--doc/bird.sgml15
-rw-r--r--filter/config.Y1
-rw-r--r--filter/data.c11
-rw-r--r--filter/f-inst.c11
-rw-r--r--filter/test.conf11
-rw-r--r--nest/a-path.c63
-rw-r--r--nest/attrs.h1
7 files changed, 85 insertions, 28 deletions
diff --git a/doc/bird.sgml b/doc/bird.sgml
index 1808d04c..786f124b 100644
--- 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 77424a8b..557a951f 100644
--- 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 62edd9e0..40220255 100644
--- 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 63a6bdab..df908e26 100644
--- 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 634816fd..63af25bb 100644
--- 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 cffd46ab..2e34a3d1 100644
--- 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 d88a73f3..50da817b 100644
--- 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 {
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-23 20:53:55 +0000