summaryrefslogtreecommitdiff
path: root/filter
diff options
context:
space:
mode:
Diffstat (limited to 'filter')
-rw-r--r--filter/Makefile11
-rw-r--r--filter/config.Y187
-rw-r--r--filter/f-util.c11
-rw-r--r--filter/filter.c320
-rw-r--r--filter/filter.h87
-rw-r--r--filter/filter_test.c87
-rw-r--r--filter/test.conf1481
-rw-r--r--filter/test.conf.inc6
-rw-r--r--filter/test.conf293
-rw-r--r--filter/test6.conf182
-rw-r--r--filter/tree_test.c304
-rw-r--r--filter/trie.c71
-rw-r--r--filter/trie_test.c185
13 files changed, 2224 insertions, 801 deletions
diff --git a/filter/Makefile b/filter/Makefile
index 2de598da..6bada8ca 100644
--- a/filter/Makefile
+++ b/filter/Makefile
@@ -1,5 +1,8 @@
-source=f-util.c filter.c tree.c trie.c
-root-rel=../
-dir-name=filter
+src := filter.c f-util.c tree.c trie.c
+obj := $(src-o-files)
+$(all-daemon)
+$(cf-local)
-include ../Rules
+tests_src := tree_test.c filter_test.c trie_test.c
+tests_targets := $(tests_targets) $(tests-target-files)
+tests_objs := $(tests_objs) $(src-o-files)
diff --git a/filter/config.Y b/filter/config.Y
index 1ef5a3a8..6b7bedaf 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -227,7 +227,6 @@ f_generate_ec(u16 kind, struct f_inst *tk, struct f_inst *tv)
cf_error("Can't operate with key of non-integer/IPv4 type in EC constructor");
}
-#ifndef IPV6
/* IP->Quad implicit conversion */
else if (tk->fi_code == FI_CONSTANT_INDIRECT) {
c1 = 1;
@@ -239,13 +238,12 @@ f_generate_ec(u16 kind, struct f_inst *tk, struct f_inst *tv)
else if (val->type == T_QUAD) {
ipv4_used = 1; key = val->val.i;
}
- else if (val->type == T_IP) {
- ipv4_used = 1; key = ipa_to_u32(val->val.px.ip);
+ else if ((val->type == T_IP) && ipa_is_ip4(val->val.ip)) {
+ ipv4_used = 1; key = ipa_to_u32(val->val.ip);
}
else
cf_error("Can't operate with key of non-integer/IPv4 type in EC constructor");
}
-#endif
if (tv->fi_code == FI_CONSTANT) {
if (tv->aux != T_INT)
@@ -317,25 +315,90 @@ f_generate_lc(struct f_inst *t1, struct f_inst *t2, struct f_inst *t3)
return rv;
}
+/*
+ * Remove all new lines and doubled whitespaces
+ * and convert all tabulators to spaces
+ * and return a copy of string
+ */
+char *
+assert_copy_expr(const char *start, size_t len)
+{
+ /* XXX: Allocates maybe a little more memory than we really finally need */
+ char *str = cfg_alloc(len + 1);
+
+ char *dst = str;
+ const char *src = start - 1;
+ const char *end = start + len;
+ while (++src < end)
+ {
+ if (*src == '\n')
+ continue;
+
+ /* Skip doubled whitespaces */
+ if (src != start)
+ {
+ const char *prev = src - 1;
+ if ((*src == ' ' || *src == '\t') && (*prev == ' ' || *prev == '\t'))
+ continue;
+ }
+
+ if (*src == '\t')
+ *dst = ' ';
+ else
+ *dst = *src;
+
+ dst++;
+ }
+ *dst = '\0';
+ return str;
+}
+
+/*
+ * assert_done - create f_instruction of bt_assert
+ * @expr: expression in bt_assert()
+ * @start: pointer to first char of test expression
+ * @end: pointer to the last char of test expression
+ */
+static struct f_inst *
+assert_done(struct f_inst *expr, const char *start, const char *end)
+{
+ struct f_inst *i;
+ i = f_new_inst(FI_ASSERT);
+ i->a1.p = expr;
+
+ if (end >= start)
+ {
+ i->a2.p = assert_copy_expr(start, end - start + 1);
+ }
+ else
+ {
+ /* this is a break of lexer buffer */
+ i->a2.p = "???";
+ }
+
+ return i;
+}
CF_DECLS
CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
ACCEPT, REJECT, ERROR, QUITBIRD,
- INT, BOOL, IP, PREFIX, PAIR, QUAD, EC, LC,
+ INT, BOOL, IP, TYPE, PREFIX, RD, PAIR, QUAD, EC, LC,
SET, STRING, BGPMASK, BGPPATH, CLIST, ECLIST, LCLIST,
IF, THEN, ELSE, CASE,
TRUE, FALSE, RT, RO, UNKNOWN, GENERIC,
- FROM, GW, NET, MASK, PROTO, SOURCE, SCOPE, CAST, DEST, IFNAME, IFINDEX,
+ FROM, GW, NET, MASK, PROTO, SOURCE, SCOPE, DEST, IFNAME, IFINDEX,
PREFERENCE,
- LEN,
+ ROA_CHECK, ASN,
+ IS_V4, IS_V6,
+ LEN, MAXLEN,
DEFINED,
ADD, DELETE, CONTAINS, RESET,
PREPEND, FIRST, LAST, LAST_NONAGGREGATED, MATCH,
- ROA_CHECK,
EMPTY,
- FILTER, WHERE, EVAL)
+ FILTER, WHERE, EVAL,
+ BT_ASSERT, BT_TEST_SUITE, FORMAT)
%nonassoc THEN
%nonassoc ELSE
@@ -348,9 +411,11 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
%type <i32> cnum
%type <e> pair_item ec_item lc_item set_item switch_item set_items switch_items switch_body
%type <trie> fprefix_set
-%type <v> set_atom switch_atom fprefix fprefix_s fipa
+%type <v> set_atom switch_atom fipa
+%type <px> fprefix
%type <s> decls declsn one_decl function_params
-%type <h> bgp_path bgp_path_tail1 bgp_path_tail2
+%type <h> bgp_path bgp_path_tail
+%type <t> get_cf_position
CF_GRAMMAR
@@ -370,11 +435,27 @@ filter_eval:
EVAL term { f_eval_int($2); }
;
+CF_ADDTO(conf, bt_test_suite)
+bt_test_suite:
+ BT_TEST_SUITE '(' SYM ',' text ')' {
+ if (!($3->class & SYM_FUNCTION))
+ cf_error("Function expected");
+
+ struct f_bt_test_suite *t = cfg_alloc(sizeof(struct f_bt_test_suite));
+ t->fn = $3->def;
+ t->fn_name = $3->name;
+ t->dsc = $5;
+
+ add_tail(&new_config->tests, &t->n);
+ }
+ ;
+
type:
INT { $$ = T_INT; }
| BOOL { $$ = T_BOOL; }
| IP { $$ = T_IP; }
- | PREFIX { $$ = T_PREFIX; }
+ | RD { $$ = T_RD; }
+ | PREFIX { $$ = T_NET; }
| PAIR { $$ = T_PAIR; }
| QUAD { $$ = T_QUAD; }
| EC { $$ = T_EC; }
@@ -396,7 +477,7 @@ type:
$$ = T_SET;
break;
- case T_PREFIX:
+ case T_NET:
$$ = T_PREFIX_SET;
break;
@@ -527,7 +608,8 @@ block:
* Complex types, their bison value is struct f_val
*/
fipa:
- IPA %prec PREFIX_DUMMY { $$.type = T_IP; $$.val.px.ip = $1; }
+ IP4 %prec PREFIX_DUMMY { $$.type = T_IP; $$.val.ip = ipa_from_ip4($1); }
+ | IP6 %prec PREFIX_DUMMY { $$.type = T_IP; $$.val.ip = ipa_from_ip6($1); }
;
@@ -541,7 +623,6 @@ fipa:
set_atom:
NUM { $$.type = T_INT; $$.val.i = $1; }
- | RTRID { $$.type = T_QUAD; $$.val.i = $1; }
| fipa { $$ = $1; }
| ENUM { $$.type = pair_a($1); $$.val.i = pair_b($1); }
| '(' term ')' {
@@ -558,7 +639,6 @@ set_atom:
switch_atom:
NUM { $$.type = T_INT; $$.val.i = $1; }
| '(' term ')' { $$.type = T_INT; $$.val.i = f_eval_int($2); }
- | RTRID { $$.type = T_QUAD; $$.val.i = $1; }
| fipa { $$ = $1; }
| ENUM { $$.type = pair_a($1); $$.val.i = pair_b($1); }
;
@@ -631,26 +711,20 @@ switch_items:
| switch_items ',' switch_item { $$ = f_merge_items($1, $3); }
;
-fprefix_s:
- IPA '/' NUM %prec '/' {
- if (($3 < 0) || ($3 > MAX_PREFIX_LENGTH) || !ip_is_prefix($1, $3)) cf_error("Invalid network prefix: %I/%d.", $1, $3);
- $$.type = T_PREFIX; $$.val.px.ip = $1; $$.val.px.len = $3;
- }
- ;
-
fprefix:
- fprefix_s { $$ = $1; }
- | fprefix_s '+' { $$ = $1; $$.val.px.len |= LEN_PLUS; }
- | fprefix_s '-' { $$ = $1; $$.val.px.len |= LEN_MINUS; }
- | fprefix_s '{' NUM ',' NUM '}' {
- if (! ((0 <= $3) && ($3 <= $5) && ($5 <= MAX_PREFIX_LENGTH))) cf_error("Invalid prefix pattern range: {%d, %d}.", $3, $5);
- $$ = $1; $$.val.px.len |= LEN_RANGE | ($3 << 16) | ($5 << 8);
+ net_ip_ { $$.net = $1; $$.lo = $1.pxlen; $$.hi = $1.pxlen; }
+ | net_ip_ '+' { $$.net = $1; $$.lo = $1.pxlen; $$.hi = net_max_prefix_length[$1.type]; }
+ | net_ip_ '-' { $$.net = $1; $$.lo = 0; $$.hi = $1.pxlen; }
+ | net_ip_ '{' NUM ',' NUM '}' {
+ $$.net = $1; $$.lo = $3; $$.hi = $5;
+ if (($3 > $5) || ($5 > net_max_prefix_length[$1.type]))
+ cf_error("Invalid prefix pattern range: {%u, %u}", $3, $5);
}
;
fprefix_set:
- fprefix { $$ = f_new_trie(cfg_mem, sizeof(struct f_trie_node)); trie_add_fprefix($$, &($1.val.px)); }
- | fprefix_set ',' fprefix { $$ = $1; trie_add_fprefix($$, &($3.val.px)); }
+ fprefix { $$ = f_new_trie(cfg_mem, sizeof(struct f_trie_node)); trie_add_prefix($$, &($1.net), $1.lo, $1.hi); }
+ | fprefix_set ',' fprefix { $$ = $1; trie_add_prefix($$, &($3.net), $3.lo, $3.hi); }
;
switch_body: /* EMPTY */ { $$ = NULL; }
@@ -678,33 +752,26 @@ bgp_path_expr:
;
bgp_path:
- PO bgp_path_tail1 PC { $$ = $2; }
- | '/' bgp_path_tail2 '/' { $$ = $2; }
+ PO bgp_path_tail PC { $$ = $2; }
;
-bgp_path_tail1:
- NUM bgp_path_tail1 { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_ASN; $$->val = $1; }
- | NUM DDOT NUM bgp_path_tail1 { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $4; $$->kind = PM_ASN_RANGE; $$->val = $1; $$->val2 = $3; }
- | '*' bgp_path_tail1 { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_ASTERISK; }
- | '?' bgp_path_tail1 { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_QUESTION; }
- | bgp_path_expr bgp_path_tail1 { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_ASN_EXPR; $$->val = (uintptr_t) $1; }
+bgp_path_tail:
+ NUM bgp_path_tail { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_ASN; $$->val = $1; }
+ | NUM DDOT NUM bgp_path_tail { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $4; $$->kind = PM_ASN_RANGE; $$->val = $1; $$->val2 = $3; }
+ | '*' bgp_path_tail { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_ASTERISK; }
+ | '?' bgp_path_tail { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_QUESTION; }
+ | bgp_path_expr bgp_path_tail { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_ASN_EXPR; $$->val = (uintptr_t) $1; }
| { $$ = NULL; }
;
-bgp_path_tail2:
- NUM bgp_path_tail2 { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_ASN; $$->val = $1; }
- | '?' bgp_path_tail2 { $$ = cfg_allocz(sizeof(struct f_path_mask)); $$->next = $2; $$->kind = PM_ASTERISK; }
- | { $$ = NULL; }
- ;
-
constant:
NUM { $$ = f_new_inst(FI_CONSTANT); $$->aux = T_INT; $$->a2.i = $1; }
| TRUE { $$ = f_new_inst(FI_CONSTANT); $$->aux = T_BOOL; $$->a2.i = 1; }
| FALSE { $$ = f_new_inst(FI_CONSTANT); $$->aux = T_BOOL; $$->a2.i = 0; }
| TEXT { $$ = f_new_inst(FI_CONSTANT); $$->aux = T_STRING; $$->a2.p = $1; }
- | fipa { NEW_F_VAL; $$ = f_new_inst(FI_CONSTANT_INDIRECT); $$->a1.p = val; *val = $1; }
- | fprefix_s {NEW_F_VAL; $$ = f_new_inst(FI_CONSTANT_INDIRECT); $$->a1.p = val; *val = $1; }
- | RTRID { $$ = f_new_inst(FI_CONSTANT); $$->aux = T_QUAD; $$->a2.i = $1; }
+ | fipa { NEW_F_VAL; $$ = f_new_inst(FI_CONSTANT_INDIRECT); $$->a1.p = val; *val = $1; }
+ | VPN_RD { NEW_F_VAL; $$ = f_new_inst(FI_CONSTANT_INDIRECT); val->type = T_RD; val->val.ec = $1; $$->a1.p = val; }
+ | net_ { NEW_F_VAL; $$ = f_new_inst(FI_CONSTANT_INDIRECT); val->type = T_NET; val->val.net = $1; $$->a1.p = val; }
| '[' set_items ']' { DBG( "We've got a set here..." ); $$ = f_new_inst(FI_CONSTANT); $$->aux = T_SET; $$->a2.p = build_tree($2); DBG( "ook\n" ); }
| '[' fprefix_set ']' { $$ = f_new_inst(FI_CONSTANT); $$->aux = T_PREFIX_SET; $$->a2.p = $2; }
| ENUM { $$ = f_new_inst(FI_CONSTANT); $$->aux = $1 >> 16; $$->a2.i = $1 & 0xffff; }
@@ -765,11 +832,10 @@ symbol:
static_attr:
FROM { $$ = f_new_static_attr(T_IP, SA_FROM, 1); }
| GW { $$ = f_new_static_attr(T_IP, SA_GW, 1); }
- | NET { $$ = f_new_static_attr(T_PREFIX, SA_NET, 0); }
+ | NET { $$ = f_new_static_attr(T_NET, SA_NET, 0); }
| PROTO { $$ = f_new_static_attr(T_STRING, SA_PROTO, 0); }
| SOURCE { $$ = f_new_static_attr(T_ENUM_RTS, SA_SOURCE, 0); }
| SCOPE { $$ = f_new_static_attr(T_ENUM_SCOPE, SA_SCOPE, 1); }
- | CAST { $$ = f_new_static_attr(T_ENUM_RTC, SA_CAST, 0); }
| DEST { $$ = f_new_static_attr(T_ENUM_RTD, SA_DEST, 1); }
| IFNAME { $$ = f_new_static_attr(T_STRING, SA_IFNAME, 0); }
| IFINDEX { $$ = f_new_static_attr(T_INT, SA_IFINDEX, 0); }
@@ -804,8 +870,13 @@ term:
| rtadot dynamic_attr { $$ = f_new_inst_da(FI_EA_GET, $2); }
+ | term '.' IS_V4 { $$ = f_new_inst(FI_IS_V4); $$->a1.p = $1; }
+ | term '.' TYPE { $$ = f_new_inst(FI_TYPE); $$->a1.p = $1; }
| term '.' IP { $$ = f_new_inst(FI_IP); $$->a1.p = $1; $$->aux = T_IP; }
+ | term '.' RD { $$ = f_new_inst(FI_ROUTE_DISTINGUISHER); $$->a1.p = $1; $$->aux = T_RD; }
| term '.' LEN { $$ = f_new_inst(FI_LENGTH); $$->a1.p = $1; }
+ | term '.' MAXLEN { $$ = f_new_inst(FI_ROA_MAXLEN); $$->a1.p = $1; }
+ | term '.' ASN { $$ = f_new_inst(FI_ROA_ASN); $$->a1.p = $1; }
| term '.' MASK '(' term ')' { $$ = f_new_inst(FI_IP_MASK); $$->a1.p = $1; $$->a2.p = $5; }
| term '.' FIRST { $$ = f_new_inst(FI_AS_PATH_FIRST); $$->a1.p = $1; }
| term '.' LAST { $$ = f_new_inst(FI_AS_PATH_LAST); $$->a1.p = $1; }
@@ -828,8 +899,12 @@ term:
| DELETE '(' term ',' term ')' { $$ = f_new_inst(FI_CLIST_ADD_DEL); $$->a1.p = $3; $$->a2.p = $5; $$->aux = 'd'; }
| FILTER '(' term ',' term ')' { $$ = f_new_inst(FI_CLIST_ADD_DEL); $$->a1.p = $3; $$->a2.p = $5; $$->aux = 'f'; }
- | ROA_CHECK '(' SYM ')' { $$ = f_generate_roa_check($3, NULL, NULL); }
- | ROA_CHECK '(' SYM ',' term ',' term ')' { $$ = f_generate_roa_check($3, $5, $7); }
+ | ROA_CHECK '(' rtable ')' { $$ = f_generate_roa_check($3, NULL, NULL); }
+ | ROA_CHECK '(' rtable ',' term ',' term ')' { $$ = f_generate_roa_check($3, $5, $7); }
+
+ | FORMAT '(' term ')' { $$ = f_new_inst(FI_FORMAT); $$->a1.p = $3; }
+
+/* | term '.' LEN { $$->code = P('P','l'); } */
/* function_call is inlined here */
| SYM '(' var_list ')' {
@@ -948,12 +1023,18 @@ cmd:
$$->a2.p = build_tree( $4 );
}
-
| rtadot dynamic_attr '.' EMPTY ';' { $$ = f_generate_empty($2); }
| rtadot dynamic_attr '.' PREPEND '(' term ')' ';' { $$ = f_generate_complex( FI_PATH_PREPEND, 'x', $2, $6 ); }
| rtadot dynamic_attr '.' ADD '(' term ')' ';' { $$ = f_generate_complex( FI_CLIST_ADD_DEL, 'a', $2, $6 ); }
| rtadot dynamic_attr '.' DELETE '(' term ')' ';' { $$ = f_generate_complex( FI_CLIST_ADD_DEL, 'd', $2, $6 ); }
| rtadot dynamic_attr '.' FILTER '(' term ')' ';' { $$ = f_generate_complex( FI_CLIST_ADD_DEL, 'f', $2, $6 ); }
+ | BT_ASSERT '(' get_cf_position term get_cf_position ')' ';' { $$ = assert_done($4, $3 + 1, $5 - 1); }
;
+get_cf_position:
+{
+ $$ = cf_text;
+};
+
+
CF_END
diff --git a/filter/f-util.c b/filter/f-util.c
index 42b08868..68aecd73 100644
--- a/filter/f-util.c
+++ b/filter/f-util.c
@@ -27,7 +27,7 @@ struct f_inst *
f_new_inst_da(enum f_instruction_code fi_code, struct f_dynamic_attr da)
{
struct f_inst *ret = f_new_inst(fi_code);
- ret->aux = da.type;
+ ret->aux = (da.f_type << 8) | da.type;
ret->a2.i = da.ea_code;
return ret;
}
@@ -60,9 +60,8 @@ f_generate_complex(int operation, int operation_aux, struct f_dynamic_attr da, s
return set_dyn;
}
-
struct f_inst *
-f_generate_roa_check(struct symbol *sym, struct f_inst *prefix, struct f_inst *asn)
+f_generate_roa_check(struct rtable_config *table, struct f_inst *prefix, struct f_inst *asn)
{
struct f_inst_roa_check *ret = cfg_allocz(sizeof(struct f_inst_roa_check));
ret->i.fi_code = FI_ROA_CHECK;
@@ -71,9 +70,9 @@ f_generate_roa_check(struct symbol *sym, struct f_inst *prefix, struct f_inst *a
ret->i.arg2 = asn;
/* prefix == NULL <-> asn == NULL */
- if ((sym->class != SYM_ROA) || ! sym->def)
- cf_error("%s is not a ROA table", sym->name);
- ret->rtc = sym->def;
+ if (table->addr_type != NET_ROA4 && table->addr_type != NET_ROA6)
+ cf_error("%s is not a ROA table", table->name);
+ ret->rtc = table;
return &ret->i;
}
diff --git a/filter/filter.c b/filter/filter.c
index 023f7e2f..28603f27 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -39,6 +39,8 @@
#include "lib/socket.h"
#include "lib/string.h"
#include "lib/unaligned.h"
+#include "lib/net.h"
+#include "lib/ip.h"
#include "nest/route.h"
#include "nest/protocol.h"
#include "nest/iface.h"
@@ -48,6 +50,19 @@
#define CMP_ERROR 999
+void (*bt_assert_hook)(int result, struct f_inst *assert);
+
+static struct adata undef_adata; /* adata of length 0 used for undefined */
+
+/* Special undef value for paths and clists */
+static inline int
+undef_value(struct f_val v)
+{
+ return ((v.type == T_PATH) || (v.type == T_CLIST) ||
+ (v.type == T_ECLIST) || (v.type == T_LCLIST)) &&
+ (v.val.ad == &undef_adata);
+}
+
static struct adata *
adata_empty(struct linpool *pool, int l)
{
@@ -92,17 +107,8 @@ pm_format(struct f_path_mask *p, buffer *buf)
buffer_puts(buf, "=]");
}
-static inline int
-uint_cmp(uint i1, uint i2)
-{
- return (int)(i1 > i2) - (int)(i1 < i2);
-}
-
-static inline int
-u64_cmp(u64 i1, u64 i2)
-{
- return (int)(i1 > i2) - (int)(i1 < i2);
-}
+static inline int val_is_ip4(const struct f_val v)
+{ return (v.type == T_IP) && ipa_is_ip4(v.val.ip); }
static inline int
lcomm_cmp(lcomm v1, lcomm v2)
@@ -128,21 +134,17 @@ lcomm_cmp(lcomm v1, lcomm v2)
int
val_compare(struct f_val v1, struct f_val v2)
{
- int rc;
-
if (v1.type != v2.type) {
if (v1.type == T_VOID) /* Hack for else */
return -1;
if (v2.type == T_VOID)
return 1;
-#ifndef IPV6
/* IP->Quad implicit conversion */
- if ((v1.type == T_QUAD) && (v2.type == T_IP))
- return uint_cmp(v1.val.i, ipa_to_u32(v2.val.px.ip));
- if ((v1.type == T_IP) && (v2.type == T_QUAD))
- return uint_cmp(ipa_to_u32(v1.val.px.ip), v2.val.i);
-#endif
+ if ((v1.type == T_QUAD) && val_is_ip4(v2))
+ return uint_cmp(v1.val.i, ipa_to_u32(v2.val.ip));
+ if (val_is_ip4(v1) && (v2.type == T_QUAD))
+ return uint_cmp(ipa_to_u32(v1.val.ip), v2.val.i);
debug( "Types do not match in val_compare\n" );
return CMP_ERROR;
@@ -158,15 +160,14 @@ val_compare(struct f_val v1, struct f_val v2)
case T_QUAD:
return uint_cmp(v1.val.i, v2.val.i);
case T_EC:
+ case T_RD:
return u64_cmp(v1.val.ec, v2.val.ec);
case T_LC:
return lcomm_cmp(v1.val.lc, v2.val.lc);
case T_IP:
- return ipa_compare(v1.val.px.ip, v2.val.px.ip);
- case T_PREFIX:
- if (rc = ipa_compare(v1.val.px.ip, v2.val.px.ip))
- return rc;
- return uint_cmp(v1.val.px.len, v2.val.px.len);
+ return ipa_compare(v1.val.ip, v2.val.ip);
+ case T_NET:
+ return net_compare(v1.val.net, v2.val.net);
case T_STRING:
return strcmp(v1.val.s, v2.val.s);
default:
@@ -237,38 +238,26 @@ val_same(struct f_val v1, struct f_val v2)
}
}
-void
-fprefix_get_bounds(struct f_prefix *px, int *l, int *h)
-{
- *l = *h = px->len & LEN_MASK;
-
- if (px->len & LEN_MINUS)
- *l = 0;
-
- else if (px->len & LEN_PLUS)
- *h = MAX_PREFIX_LENGTH;
-
- else if (px->len & LEN_RANGE)
- {
- *l = 0xff & (px->len >> 16);
- *h = 0xff & (px->len >> 8);
- }
-}
-
static int
clist_set_type(struct f_tree *set, struct f_val *v)
{
- switch (set->from.type) {
+ switch (set->from.type)
+ {
case T_PAIR:
v->type = T_PAIR;
return 1;
+
case T_QUAD:
-#ifndef IPV6
- case T_IP:
-#endif
v->type = T_QUAD;
return 1;
- break;
+
+ case T_IP:
+ if (val_is_ip4(set->from) && val_is_ip4(set->to))
+ {
+ v->type = T_QUAD;
+ return 1;
+ }
+ /* Fall through */
default:
v->type = T_VOID;
return 0;
@@ -471,11 +460,9 @@ val_in_range(struct f_val v1, struct f_val v2)
if (((v1.type == T_PAIR) || (v1.type == T_QUAD)) && (v2.type == T_CLIST))
return int_set_contains(v2.val.ad, v1.val.i);
-#ifndef IPV6
/* IP->Quad implicit conversion */
- if ((v1.type == T_IP) && (v2.type == T_CLIST))
- return int_set_contains(v2.val.ad, ipa_to_u32(v1.val.px.ip));
-#endif
+ if (val_is_ip4(v1) && (v2.type == T_CLIST))
+ return int_set_contains(v2.val.ad, ipa_to_u32(v1.val.ip));
if ((v1.type == T_EC) && (v2.type == T_ECLIST))
return ec_set_contains(v2.val.ad, v1.val.ec);
@@ -486,21 +473,21 @@ val_in_range(struct f_val v1, struct f_val v2)
if ((v1.type == T_STRING) && (v2.type == T_STRING))
return patmatch(v2.val.s, v1.val.s);
- if ((v1.type == T_IP) && (v2.type == T_PREFIX))
- return ipa_in_net(v1.val.px.ip, v2.val.px.ip, v2.val.px.len);
+ if ((v1.type == T_IP) && (v2.type == T_NET))
+ return ipa_in_netX(v1.val.ip, v2.val.net);
- if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX))
- return net_in_net(v1.val.px.ip, v1.val.px.len, v2.val.px.ip, v2.val.px.len);
+ if ((v1.type == T_NET) && (v2.type == T_NET))
+ return net_in_netX(v1.val.net, v2.val.net);
- if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX_SET))
- return trie_match_fprefix(v2.val.ti, &v1.val.px);
+ if ((v1.type == T_NET) && (v2.type == T_PREFIX_SET))
+ return trie_match_net(v2.val.ti, v1.val.net);
if (v2.type != T_SET)
return CMP_ERROR;
/* With integrated Quad<->IP implicit conversion */
if ((v1.type == v2.val.t->from.type) ||
- ((IP_VERSION == 4) && (v1.type == T_QUAD) && (v2.val.t->from.type == T_IP)))
+ ((v1.type == T_QUAD) && val_is_ip4(v2.val.t->from) && val_is_ip4(v2.val.t->to)))
return !!find_tree(v2.val.t, v1);
if (v1.type == T_CLIST)
@@ -531,12 +518,13 @@ val_format(struct f_val v, buffer *buf)
case T_BOOL: buffer_puts(buf, v.val.i ? "TRUE" : "FALSE"); return;
case T_INT: buffer_print(buf, "%u", v.val.i); return;
case T_STRING: buffer_print(buf, "%s", v.val.s); return;
- case T_IP: buffer_print(buf, "%I", v.val.px.ip); return;
- case T_PREFIX: buffer_print(buf, "%I/%d", v.val.px.ip, v.val.px.len); return;
+ case T_IP: buffer_print(buf, "%I", v.val.ip); return;
+ case T_NET: buffer_print(buf, "%N", v.val.net); return;
case T_PAIR: buffer_print(buf, "(%u,%u)", v.val.i >> 16, v.val.i & 0xffff); return;
case T_QUAD: buffer_print(buf, "%R", v.val.i); return;
case T_EC: ec_format(buf2, v.val.ec); buffer_print(buf, "%s", buf2); return;
case T_LC: lc_format(buf2, v.val.lc); buffer_print(buf, "%s", buf2); return;
+ case T_RD: rd_format(v.val.ec, buf2, 1024); buffer_print(buf, "%s", buf2); return;
case T_PREFIX_SET: trie_format(v.val.ti, buf); return;
case T_SET: tree_format(v.val.t, buf); return;
case T_ENUM: buffer_print(buf, "(enum %x)%u", v.type, v.val.i); return;
@@ -585,11 +573,19 @@ f_rta_cow(void)
(*f_rte)->attrs = rta_do_cow((*f_rte)->attrs, f_pool);
}
+static char *
+val_format_str(struct f_val v) {
+ buffer b;
+ LOG_BUFFER_INIT(b);
+ val_format(v, &b);
+ return lp_strdup(f_pool, b.start);
+}
+
static struct tbf rl_runtime_err = TBF_DEFAULT_LOG_LIMITS;
-#define runtime(x) do { \
+#define runtime(fmt, ...) do { \
if (!(f_flags & FF_SILENT)) \
- log_rl(&rl_runtime_err, L_ERR "filters, line %d: %s", what->lineno, x); \
+ log_rl(&rl_runtime_err, L_ERR "filters, line %d: " fmt, what->lineno, ##__VA_ARGS__); \
res.type = T_RETURN; \
res.val.i = F_ERROR; \
return res; \
@@ -719,12 +715,10 @@ interpret(struct f_inst *what)
else if (v1.type == T_QUAD) {
ipv4_used = 1; key = v1.val.i;
}
-#ifndef IPV6
/* IP->Quad implicit conversion */
- else if (v1.type == T_IP) {
- ipv4_used = 1; key = ipa_to_u32(v1.val.px.ip);
+ else if (val_is_ip4(v1)) {
+ ipv4_used = 1; key = ipa_to_u32(v1.val.ip);
}
-#endif
else
runtime("Can't operate with key of non-integer/IPv4 type in EC constructor");
@@ -824,7 +818,26 @@ interpret(struct f_inst *what)
case FI_DEFINED:
ONEARG;
res.type = T_BOOL;
- res.val.i = (v1.type != T_VOID);
+ res.val.i = (v1.type != T_VOID) && !undef_value(v1);
+ break;
+ case FI_TYPE:
+ ONEARG;
+ switch (v1.type)
+ {
+ case T_NET:
+ res.type = T_ENUM_NETTYPE;
+ res.val.i = v1.val.net->type;
+ break;
+ default:
+ runtime( "Can't determine type of this item" );
+ }
+ break;
+ case FI_IS_V4:
+ ONEARG;
+ if (v1.type != T_IP)
+ runtime( "IP version check needs an IP address" );
+ res.type = T_BOOL;
+ res.val.i = ipa_is_ip4(v1.val.ip);
break;
/* Set to indirect value, a1 = variable, a2 = value */
@@ -832,15 +845,15 @@ interpret(struct f_inst *what)
ARG(v2, a2.p);
sym = what->a1.p;
vp = sym->def;
- if ((sym->class != (SYM_VARIABLE | v2.type)) && (v2.type != T_VOID)) {
-#ifndef IPV6
+ if ((sym->class != (SYM_VARIABLE | v2.type)) && (v2.type != T_VOID))
+ {
/* IP->Quad implicit conversion */
- if ((sym->class == (SYM_VARIABLE | T_QUAD)) && (v2.type == T_IP)) {
+ if ((sym->class == (SYM_VARIABLE | T_QUAD)) && val_is_ip4(v2))
+ {
vp->type = T_QUAD;
- vp->val.i = ipa_to_u32(v2.val.px.ip);
+ vp->val.i = ipa_to_u32(v2.val.ip);
break;
}
-#endif
runtime( "Assigning to variable of incompatible type" );
}
*vp = v2;
@@ -911,17 +924,15 @@ interpret(struct f_inst *what)
switch (what->a2.i)
{
- case SA_FROM: res.val.px.ip = rta->from; break;
- case SA_GW: res.val.px.ip = rta->gw; break;
- case SA_NET: res.val.px.ip = (*f_rte)->net->n.prefix;
- res.val.px.len = (*f_rte)->net->n.pxlen; break;
+ case SA_FROM: res.val.ip = rta->from; break;
+ case SA_GW: res.val.ip = rta->nh.gw; break;
+ case SA_NET: res.val.net = (*f_rte)->net->n.addr; break;
case SA_PROTO: res.val.s = rta->src->proto->name; break;
case SA_SOURCE: res.val.i = rta->source; break;
case SA_SCOPE: res.val.i = rta->scope; break;
- case SA_CAST: res.val.i = rta->cast; break;
case SA_DEST: res.val.i = rta->dest; break;
- case SA_IFNAME: res.val.s = rta->iface ? rta->iface->name : ""; break;
- case SA_IFINDEX: res.val.i = rta->iface ? rta->iface->index : 0; break;
+ case SA_IFNAME: res.val.s = rta->nh.iface ? rta->nh.iface->name : ""; break;
+ case SA_IFINDEX: res.val.i = rta->nh.iface ? rta->nh.iface->index : 0; break;
default:
bug("Invalid static attribute access (%x)", res.type);
@@ -941,20 +952,20 @@ interpret(struct f_inst *what)
switch (what->a2.i)
{
case SA_FROM:
- rta->from = v1.val.px.ip;
+ rta->from = v1.val.ip;
break;
case SA_GW:
{
- ip_addr ip = v1.val.px.ip;
+ ip_addr ip = v1.val.ip;
neighbor *n = neigh_find(rta->src->proto, &ip, 0);
if (!n || (n->scope == SCOPE_HOST))
runtime( "Invalid gw address" );
- rta->dest = RTD_ROUTER;
- rta->gw = ip;
- rta->iface = n->iface;
- rta->nexthops = NULL;
+ rta->dest = RTD_UNICAST;
+ rta->nh.gw = ip;
+ rta->nh.iface = n->iface;
+ rta->nh.next = NULL;
rta->hostentry = NULL;
}
break;
@@ -969,9 +980,9 @@ interpret(struct f_inst *what)
runtime( "Destination can be changed only to blackhole, unreachable or prohibit" );
rta->dest = i;
- rta->gw = IPA_NONE;
- rta->iface = NULL;
- rta->nexthops = NULL;
+ rta->nh.gw = IPA_NONE;
+ rta->nh.iface = NULL;
+ rta->nh.next = NULL;
rta->hostentry = NULL;
break;
@@ -985,6 +996,7 @@ interpret(struct f_inst *what)
{
eattr *e = NULL;
u16 code = what->a2.i;
+ int f_type = what->aux >> 8;
if (!(f_flags & FF_FORCE_TMPATTR))
e = ea_find((*f_rte)->attrs->eattrs, code);
@@ -994,24 +1006,31 @@ interpret(struct f_inst *what)
e = ea_find((*f_rte)->attrs->eattrs, code);
if (!e) {
- /* A special case: undefined int_set looks like empty int_set */
+ /* A special case: undefined as_path looks like empty as_path */
+ if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_AS_PATH) {
+ res.type = T_PATH;
+ res.val.ad = &undef_adata;
+ break;
+ }
+
+ /* The same special case for int_set */
if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_INT_SET) {
res.type = T_CLIST;
- res.val.ad = adata_empty(f_pool, 0);
+ res.val.ad = &undef_adata;
break;
}
/* The same special case for ec_set */
if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_EC_SET) {
res.type = T_ECLIST;
- res.val.ad = adata_empty(f_pool, 0);
+ res.val.ad = &undef_adata;
break;
}
/* The same special case for lc_set */
if ((what->aux & EAF_TYPE_MASK) == EAF_TYPE_LC_SET) {
res.type = T_LCLIST;
- res.val.ad = adata_empty(f_pool, 0);
+ res.val.ad = &undef_adata;
break;
}
@@ -1022,7 +1041,7 @@ interpret(struct f_inst *what)
switch (what->aux & EAF_TYPE_MASK) {
case EAF_TYPE_INT:
- res.type = T_INT;
+ res.type = f_type;
res.val.i = e->u.data;
break;
case EAF_TYPE_ROUTER_ID:
@@ -1036,7 +1055,7 @@ interpret(struct f_inst *what)
case EAF_TYPE_IP_ADDRESS:
res.type = T_IP;
struct adata * ad = e->u.ptr;
- res.val.px.ip = * (ip_addr *) ad->data;
+ res.val.ip = * (ip_addr *) ad->data;
break;
case EAF_TYPE_AS_PATH:
res.type = T_PATH;
@@ -1072,30 +1091,28 @@ interpret(struct f_inst *what)
{
struct ea_list *l = lp_alloc(f_pool, sizeof(struct ea_list) + sizeof(eattr));
u16 code = what->a2.i;
+ int f_type = what->aux >> 8;
l->next = NULL;
l->flags = EALF_SORTED;
l->count = 1;
l->attrs[0].id = code;
l->attrs[0].flags = 0;
- l->attrs[0].type = what->aux | EAF_ORIGINATED;
+ l->attrs[0].type = (what->aux & 0xff) | EAF_ORIGINATED | EAF_FRESH;
switch (what->aux & EAF_TYPE_MASK) {
case EAF_TYPE_INT:
- // Enums are also ints, so allow them in.
- if (v1.type != T_INT && (v1.type < T_ENUM_LO || v1.type > T_ENUM_HI))
+ if (v1.type != f_type)
runtime( "Setting int attribute to non-int value" );
l->attrs[0].u.data = v1.val.i;
break;
case EAF_TYPE_ROUTER_ID:
-#ifndef IPV6
/* IP->Quad implicit conversion */
- if (v1.type == T_IP) {
- l->attrs[0].u.data = ipa_to_u32(v1.val.px.ip);
+ if (val_is_ip4(v1)) {
+ l->attrs[0].u.data = ipa_to_u32(v1.val.ip);
break;
}
-#endif
/* T_INT for backward compatibility */
if ((v1.type != T_QUAD) && (v1.type != T_INT))
runtime( "Setting quad attribute to non-quad value" );
@@ -1111,7 +1128,7 @@ interpret(struct f_inst *what)
int len = sizeof(ip_addr);
struct adata *ad = lp_alloc(f_pool, sizeof(struct adata) + len);
ad->length = len;
- (* (ip_addr *) ad->data) = v1.val.px.ip;
+ (* (ip_addr *) ad->data) = v1.val.ip;
l->attrs[0].u.ptr = ad;
break;
case EAF_TYPE_AS_PATH:
@@ -1191,7 +1208,7 @@ interpret(struct f_inst *what)
ONEARG;
res.type = T_INT;
switch(v1.type) {
- case T_PREFIX: res.val.i = v1.val.px.len; break;
+ case T_NET: res.val.i = net_pxlen(v1.val.net); break;
case T_PATH: res.val.i = as_path_getlen(v1.val.ad); break;
case T_CLIST: res.val.i = int_set_get_size(v1.val.ad); break;
case T_ECLIST: res.val.i = ec_set_get_size(v1.val.ad); break;
@@ -1199,16 +1216,41 @@ interpret(struct f_inst *what)
default: runtime( "Prefix, path, clist or eclist expected" );
}
break;
+ case FI_ROA_MAXLEN: /* Get ROA max prefix length */
+ ONEARG;
+ if (v1.type != T_NET || !net_is_roa(v1.val.net))
+ runtime( "ROA expected" );
+
+ res.type = T_INT;
+ res.val.i = (v1.val.net->type == NET_ROA4) ?
+ ((net_addr_roa4 *) v1.val.net)->max_pxlen :
+ ((net_addr_roa6 *) v1.val.net)->max_pxlen;
+ break;
+ case FI_ROA_ASN: /* Get ROA ASN */
+ ONEARG;
+ if (v1.type != T_NET || !net_is_roa(v1.val.net))
+ runtime( "ROA expected" );
+
+ res.type = T_INT;
+ res.val.i = (v1.val.net->type == NET_ROA4) ?
+ ((net_addr_roa4 *) v1.val.net)->asn :
+ ((net_addr_roa6 *) v1.val.net)->asn;
+ break;
case FI_IP: /* Convert prefix to ... */
ONEARG;
- if (v1.type != T_PREFIX)
+ if (v1.type != T_NET)
runtime( "Prefix expected" );
- res.type = what->aux;
- switch(res.type) {
- /* case T_INT: res.val.i = v1.val.px.len; break; Not needed any more */
- case T_IP: res.val.px.ip = v1.val.px.ip; break;
- default: bug( "Unknown prefix to conversion" );
- }
+ res.type = T_IP;
+ res.val.ip = net_prefix(v1.val.net);
+ break;
+ case FI_ROUTE_DISTINGUISHER:
+ ONEARG;
+ if (v1.type != T_NET)
+ runtime( "Prefix expected" );
+ if (!net_is_vpn(v1.val.net))
+ runtime( "VPN address expected" );
+ res.type = T_RD;
+ res.val.ec = net_rd(v1.val.net);
break;
case FI_AS_PATH_FIRST: /* Get first ASN from AS PATH */
ONEARG;
@@ -1279,11 +1321,11 @@ interpret(struct f_inst *what)
runtime( "Integer expected");
if (v1.type != T_IP)
runtime( "You can mask only IP addresses" );
- {
- ip_addr mask = ipa_mkmask(v2.val.i);
- res.type = T_IP;
- res.val.px.ip = ipa_and(mask, v1.val.px.ip);
- }
+
+ res.type = T_IP;
+ res.val.ip = ipa_is_ip4(v1.val.ip) ?
+ ipa_from_ip4(ip4_and(ipa_to_ip4(v1.val.ip), ip4_mkmask(v2.val.i))) :
+ ipa_from_ip6(ip6_and(ipa_to_ip6(v1.val.ip), ip6_mkmask(v2.val.i)));
break;
case FI_EMPTY: /* Create empty attribute */
@@ -1339,11 +1381,9 @@ interpret(struct f_inst *what)
if ((v2.type == T_PAIR) || (v2.type == T_QUAD))
n = v2.val.i;
-#ifndef IPV6
/* IP->Quad implicit conversion */
- else if (v2.type == T_IP)
- n = ipa_to_u32(v2.val.px.ip);
-#endif
+ else if (val_is_ip4(v2))
+ n = ipa_to_u32(v2.val.ip);
else if ((v2.type == T_SET) && clist_set_type(v2.val.t, &dummy))
arg_set = 1;
else if (v2.type == T_CLIST)
@@ -1473,7 +1513,7 @@ interpret(struct f_inst *what)
if (what->arg1)
{
TWOARGS;
- if ((v1.type != T_PREFIX) || (v2.type != T_INT))
+ if ((v1.type != T_NET) || (v2.type != T_INT))
runtime("Invalid argument to roa_check()");
as = v2.val.i;
@@ -1481,8 +1521,7 @@ interpret(struct f_inst *what)
else
{
ACCESS_RTE;
- v1.val.px.ip = (*f_rte)->net->n.prefix;
- v1.val.px.len = (*f_rte)->net->n.pxlen;
+ v1.val.net = (*f_rte)->net->n.addr;
/* We ignore temporary attributes, probably not a problem here */
/* 0x02 is a value of BA_AS_PATH, we don't want to include BGP headers */
@@ -1494,12 +1533,39 @@ interpret(struct f_inst *what)
as_path_get_last(e->u.ptr, &as);
}
- struct roa_table_config *rtc = ((struct f_inst_roa_check *) what)->rtc;
- if (!rtc->table)
+ struct rtable *table = ((struct f_inst_roa_check *) what)->rtc->table;
+ if (!table)
runtime("Missing ROA table");
+ if (table->addr_type != NET_ROA4 && table->addr_type != NET_ROA6)
+ runtime("Table type must be either ROA4 or ROA6");
+
res.type = T_ENUM_ROA;
- res.val.i = roa_check(rtc->table, v1.val.px.ip, v1.val.px.len, as);
+
+ if (table->addr_type != (v1.val.net->type == NET_IP4 ? NET_ROA4 : NET_ROA6))
+ res.val.i = ROA_UNKNOWN; /* Prefix and table type mismatch */
+ else
+ res.val.i = net_roa_check(table, v1.val.net, as);
+
+ break;
+
+ case FI_FORMAT: /* Format */
+ ONEARG;
+
+ res.type = T_STRING;
+ res.val.s = val_format_str(v1);
+ break;
+
+ case FI_ASSERT: /* Birdtest Assert */
+ ONEARG;
+
+ if (v1.type != T_BOOL)
+ runtime("Should be boolean value");
+
+ res.type = v1.type;
+ res.val = v1.val;
+
+ CALL(bt_assert_hook, res.val.i, what);
break;
default:
@@ -1554,6 +1620,7 @@ i_same(struct f_inst *f1, struct f_inst *f2)
case FI_NOT_MATCH:
case FI_MATCH: TWOARGS; break;
case FI_DEFINED: ONEARG; break;
+ case FI_TYPE: ONEARG; break;
case FI_LC_CONSTRUCT:
TWOARGS;
@@ -1619,6 +1686,7 @@ i_same(struct f_inst *f1, struct f_inst *f2)
case FI_RETURN: ONEARG; break;
case FI_IP: ONEARG; break;
+ case FI_ROUTE_DISTINGUISHER: ONEARG; break;
case FI_CALL: /* Call rewriting trickery to avoid exponential behaviour */
ONEARG;
if (!i_same(f1->a2.p, f2->a2.p))
@@ -1635,7 +1703,7 @@ i_same(struct f_inst *f1, struct f_inst *f2)
case FI_AS_PATH_LAST_NAG: ONEARG; break;
case FI_ROA_CHECK:
TWOARGS;
- /* Does not really make sense - ROA check resuls may change anyway */
+ /* Does not really make sense - ROA check results may change anyway */
if (strcmp(((struct f_inst_roa_check *) f1)->rtc->name,
((struct f_inst_roa_check *) f2)->rtc->name))
return 0;
diff --git a/filter/filter.h b/filter/filter.h
index 1d0f389e..47014785 100644
--- a/filter/filter.h
+++ b/filter/filter.h
@@ -35,6 +35,8 @@
F(FI_MATCH, 0, '~') \
F(FI_NOT_MATCH, '!', '~') \
F(FI_DEFINED, 'd', 'e') \
+ F(FI_TYPE, 0, 'T') \
+ F(FI_IS_V4, 'I', 'i') \
F(FI_SET, 0, 's') \
F(FI_CONSTANT, 0, 'c') \
F(FI_VARIABLE, 0, 'V') \
@@ -50,7 +52,10 @@
F(FI_PREF_GET, 0, 'P') \
F(FI_PREF_SET, 'P', 'S') \
F(FI_LENGTH, 0, 'L') \
+ F(FI_ROA_MAXLEN, 'R', 'M') \
+ F(FI_ROA_ASN, 'R', 'A') \
F(FI_IP, 'c', 'p') \
+ F(FI_ROUTE_DISTINGUISHER, 'R', 'D') \
F(FI_AS_PATH_FIRST, 'a', 'f') \
F(FI_AS_PATH_LAST, 'a', 'l') \
F(FI_AS_PATH_LAST_NAG, 'a', 'L') \
@@ -62,7 +67,9 @@
F(FI_EMPTY, 0, 'E') \
F(FI_PATH_PREPEND, 'A', 'p') \
F(FI_CLIST_ADD_DEL, 'C', 'a') \
- F(FI_ROA_CHECK, 'R', 'C')
+ F(FI_ROA_CHECK, 'R', 'C') \
+ F(FI_FORMAT, 0, 'F') \
+ F(FI_ASSERT, 'a', 's')
enum f_instruction_code {
#define F(c,a,b) \
@@ -74,15 +81,15 @@ FI__LIST
struct f_inst { /* Instruction */
struct f_inst *next; /* Structure is 16 bytes, anyway */
enum f_instruction_code fi_code;
- u16 aux;
+ u16 aux; /* Extension to instruction code, T_*, EA_*, EAF_* */
union {
- int i;
+ uint i;
void *p;
- } a1;
+ } a1; /* The first argument */
union {
- int i;
+ uint i;
void *p;
- } a2;
+ } a2; /* The second argument */
int lineno;
};
@@ -92,7 +99,7 @@ struct f_inst { /* Instruction */
/* Not enough fields in f_inst for three args used by roa_check() */
struct f_inst_roa_check {
struct f_inst i;
- struct roa_table_config *rtc;
+ struct rtable_config *rtc;
};
struct f_inst3 {
@@ -107,23 +114,18 @@ struct f_inst3 {
struct f_prefix {
- ip_addr ip;
- int len;
-#define LEN_MASK 0xff
-#define LEN_PLUS 0x1000000
-#define LEN_MINUS 0x2000000
-#define LEN_RANGE 0x4000000
- /* If range then prefix must be in range (len >> 16 & 0xff, len >> 8 & 0xff) */
+ net_addr net;
+ u8 lo, hi;
};
struct f_val {
- int type;
+ int type; /* T_* */
union {
uint i;
u64 ec;
lcomm lc;
- /* ip_addr ip; Folded into prefix */
- struct f_prefix px;
+ ip_addr ip;
+ const net_addr *net;
char *s;
struct f_tree *t;
struct f_trie *ti;
@@ -158,7 +160,7 @@ static inline struct f_static_attr f_new_static_attr(int f_type, int code, int r
{ return (struct f_static_attr) { .f_type = f_type, .sa_code = code, .readonly = readonly }; }
struct f_tree *f_new_tree(void);
struct f_inst *f_generate_complex(int operation, int operation_aux, struct f_dynamic_attr da, struct f_inst *argument);
-struct f_inst *f_generate_roa_check(struct symbol *sym, struct f_inst *prefix, struct f_inst *asn);
+struct f_inst *f_generate_roa_check(struct rtable_config *table, struct f_inst *prefix, struct f_inst *asn);
struct f_tree *build_tree(struct f_tree *);
@@ -167,28 +169,11 @@ int same_tree(struct f_tree *t1, struct f_tree *t2);
void tree_format(struct f_tree *t, buffer *buf);
struct f_trie *f_new_trie(linpool *lp, uint node_size);
-void *trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h);
-int trie_match_prefix(struct f_trie *t, ip_addr px, int plen);
+void *trie_add_prefix(struct f_trie *t, const net_addr *n, uint l, uint h);
+int trie_match_net(struct f_trie *t, const net_addr *n);
int trie_same(struct f_trie *t1, struct f_trie *t2);
void trie_format(struct f_trie *t, buffer *buf);
-void fprefix_get_bounds(struct f_prefix *px, int *l, int *h);
-
-static inline void
-trie_add_fprefix(struct f_trie *t, struct f_prefix *px)
-{
- int l, h;
- fprefix_get_bounds(px, &l, &h);
- trie_add_prefix(t, px->ip, px->len & LEN_MASK, l, h);
-}
-
-static inline int
-trie_match_fprefix(struct f_trie *t, struct f_prefix *px)
-{
- return trie_match_prefix(t, px->ip, px->len & LEN_MASK);
-}
-
-
struct ea_list;
struct rte;
@@ -218,6 +203,7 @@ void val_format(struct f_val v, buffer *buf);
#define FILTER_ACCEPT NULL
#define FILTER_REJECT ((void *) 1)
+#define FILTER_UNDEF ((void *) 2) /* Used in BGP */
/* Type numbers must be in 0..0xff range */
#define T_MASK 0xff
@@ -242,7 +228,9 @@ void val_format(struct f_val v, buffer *buf);
#define T_ENUM_RTC 0x33
#define T_ENUM_RTD 0x34
#define T_ENUM_ROA 0x35
-#define T_ENUM_RA_PREFERENCE 0x36
+#define T_ENUM_NETTYPE 0x36
+#define T_ENUM_RA_PREFERENCE 0x37
+
/* new enums go here */
#define T_ENUM_EMPTY 0x3f /* Special hack for atomic_aggr */
@@ -250,7 +238,7 @@ void val_format(struct f_val v, buffer *buf);
/* Bigger ones */
#define T_IP 0x20
-#define T_PREFIX 0x21
+#define T_NET 0x21
#define T_STRING 0x22
#define T_PATH_MASK 0x23 /* mask for BGP path */
#define T_PATH 0x24 /* BGP path */
@@ -259,6 +247,7 @@ void val_format(struct f_val v, buffer *buf);
#define T_ECLIST 0x27 /* Extended community list */
#define T_LC 0x28 /* Large community value, lcomm */
#define T_LCLIST 0x29 /* Large community list */
+#define T_RD 0x2a /* Route distinguisher for VPN addresses */
#define T_RETURN 0x40
#define T_SET 0x80
@@ -271,10 +260,9 @@ void val_format(struct f_val v, buffer *buf);
#define SA_PROTO 4
#define SA_SOURCE 5
#define SA_SCOPE 6
-#define SA_CAST 7
-#define SA_DEST 8
-#define SA_IFNAME 9
-#define SA_IFINDEX 10
+#define SA_DEST 7
+#define SA_IFNAME 8
+#define SA_IFINDEX 9
struct f_tree {
@@ -286,7 +274,7 @@ struct f_tree {
struct f_trie_node
{
ip_addr addr, mask, accept;
- int plen;
+ uint plen;
struct f_trie_node *c[2];
};
@@ -303,4 +291,15 @@ struct f_trie
#define FF_FORCE_TMPATTR 1 /* Force all attributes to be temporary */
#define FF_SILENT 2 /* Silent filter execution */
+/* Bird Tests */
+struct f_bt_test_suite {
+ node n; /* Node in config->tests */
+ struct f_inst *fn; /* Root of function */
+ const char *fn_name; /* Name of test */
+ const char *dsc; /* Description */
+};
+
+/* Hook for call bt_assert() function in configuration */
+extern void (*bt_assert_hook)(int result, struct f_inst *assert);
+
#endif
diff --git a/filter/filter_test.c b/filter/filter_test.c
new file mode 100644
index 00000000..be7fd521
--- /dev/null
+++ b/filter/filter_test.c
@@ -0,0 +1,87 @@
+/*
+ * Filters: Tests
+ *
+ * (c) 2015 CZ.NIC z.s.p.o.
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+
+#include <string.h>
+#include <stdlib.h>
+
+#include "test/birdtest.h"
+#include "test/bt-utils.h"
+
+#include "filter/filter.h"
+#include "conf/conf.h"
+
+#define BT_CONFIG_FILE "filter/test.conf"
+
+
+static struct config *
+parse_config_file(const void *filename_void)
+{
+ bt_bird_init();
+
+ size_t fn_size = strlen((const char *) filename_void) + 1;
+ char *filename = alloca(fn_size);
+ strncpy(filename, filename_void, fn_size);
+
+ struct config *c = bt_config_file_parse(filename);
+ bt_bird_cleanup();
+
+ return c;
+}
+
+static int
+run_function(const void *parsed_fn_def)
+{
+ /* XXX: const -> non-const */
+ struct f_inst *f = (struct f_inst *) parsed_fn_def;
+
+ linpool *tmp = lp_new_default(&root_pool);
+ struct f_val res = f_eval(f, tmp);
+ rfree(tmp);
+
+ if (res.type == T_RETURN && res.val.i >= F_REJECT)
+ return 0;
+
+ return 1;
+}
+
+static void
+bt_assert_filter(int result, struct f_inst *assert)
+{
+ int bt_suit_case_result = 1;
+ if (!result)
+ {
+ bt_result = 0;
+ bt_suite_result = 0;
+ bt_suit_case_result = 0;
+ }
+
+ bt_log_suite_case_result(bt_suit_case_result, "Assertion at line %d (%s)", assert->lineno, (char *) assert->a2.p);
+}
+
+int
+main(int argc, char *argv[])
+{
+ bt_init(argc, argv);
+
+ struct config *c = parse_config_file(BT_CONFIG_FILE);
+
+ if (c)
+ {
+ bt_assert_hook = bt_assert_filter;
+
+ struct f_bt_test_suite *t;
+ WALK_LIST(t, c->tests)
+ bt_test_suite_base(run_function, t->fn_name, t->fn, BT_FORKING, BT_TIMEOUT, "%s", t->dsc);
+ }
+
+ return bt_exit_value();
+}
diff --git a/filter/test.conf b/filter/test.conf
index 4dc67c49..989dab14 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -1,127 +1,630 @@
-
/*
- * This is an example configuration file.
+ * This is unit testing configuration file for testing filters
+ *
* FIXME: add all examples from docs here.
*/
-# Yet another comment
-
router id 62.168.0.1;
-define xyzzy = (120+10);
-define '1a-a1' = (20+10);
+/* We have to setup any protocol */
+protocol static { ipv4; }
+
+
+
+
+/*
+ * Common definitions and functions
+ * --------------------------------
+ */
+
define one = 1;
define ten = 10;
-define p23 = (2, 3);
-define ip1222 = 1.2.2.2;
-
function onef(int a)
{
return 1;
}
+
+
+/*
+ * Testing boolean expressions
+ * ---------------------------
+ */
+
+function t_bool()
+bool b;
+{
+ b = true;
+ bt_assert(b);
+ bt_assert(!!b);
+
+ bt_assert(format(true) = "TRUE");
+ bt_assert(format(false) = "FALSE");
+
+ if ( b = true ) then
+ bt_assert(b);
+ else
+ bt_assert(false);
+
+ bt_assert(true && true);
+ bt_assert(true || false);
+ bt_assert(! false && ! false && true);
+ bt_assert(1 < 2 && 1 != 3);
+ bt_assert(true && true && ! false);
+ bt_assert(true || 1+"a");
+ bt_assert(!(false && 1+"a"));
+ bt_assert(!(true && false));
+}
+
+bt_test_suite(t_bool, "Testing boolean expressions");
+
+
+
+
+/*
+ * Testing integers
+ * ----------------
+ */
+
+define four = 4;
+define xyzzy = (120+10);
+define '1a-a1' = (xyzzy-100);
+
+function t_int()
+int i;
+{
+ bt_assert(xyzzy = 130);
+ bt_assert('1a-a1' = 30);
+
+ i = four;
+ i = 12*100 + 60/2 + i;
+ i = (i + 0);
+ bt_assert(i = 1234);
+
+ bt_assert(format(i) = "1234");
+
+ i = 4200000000;
+ bt_assert(i = 4200000000);
+ bt_assert(i > 4100000000);
+ bt_assert(!(i > 4250000000));
+
+ bt_assert(1 = 1);
+ bt_assert(!(1 != 1));
+
+ bt_assert(1 != 2);
+ bt_assert(1 <= 2);
+
+ bt_assert(1 != "a");
+ bt_assert(1 != (0,1));
+
+ bt_assert(!(i = 4));
+ bt_assert(1 <= 1);
+ bt_assert(!(1234 < 1234));
+}
+
+bt_test_suite(t_int, "Testing integers");
+
+
+
+
+/*
+ * Testing sets of integers
+ * ------------------------
+ */
+
+define is1 = [ one, (2+1), (6-one), 8, 11, 15, 17, 19];
+define is2 = [(17+2), 17, 15, 11, 8, 5, 3, 2];
+define is3 = [5, 17, 2, 11, 8, 15, 3, 19];
+
+function t_int_set()
+int set is;
+{
+ bt_assert(1 ~ [1,2,3]);
+ bt_assert(5 ~ [1..20]);
+ bt_assert(2 ~ [ 1, 2, 3 ]);
+ bt_assert(5 ~ [ 4 .. 7 ]);
+ bt_assert(1 !~ [ 2, 3, 4 ]);
+
+ is = [ 2, 3, 4, 7..11 ];
+ bt_assert(10 ~ is);
+ bt_assert(5 !~ is);
+
+ bt_assert(1 ~ is1);
+ bt_assert(3 ~ is1);
+ bt_assert(5 ~ is1);
+ bt_assert((one+2) ~ is1);
+ bt_assert(2 ~ is2);
+ bt_assert(2 ~ is3);
+ bt_assert(4 !~ is1);
+ bt_assert(4 !~ is2);
+ bt_assert(4 !~ is3);
+ bt_assert(10 !~ is1);
+ bt_assert(10 !~ is2);
+ bt_assert(10 !~ is3);
+ bt_assert(15 ~ is1);
+ bt_assert(15 ~ is2);
+ bt_assert(15 ~ is3);
+ bt_assert(18 !~ is1);
+ bt_assert(18 !~ is2);
+ bt_assert(18 !~ is3);
+ bt_assert(19 ~ is1);
+ bt_assert(19 ~ is2);
+ bt_assert(19 ~ is3);
+ bt_assert(20 !~ is1);
+ bt_assert(20 !~ is2);
+ bt_assert(20 !~ is3);
+
+ bt_assert([1,2] != [1,3]);
+ bt_assert([1,4..10,20] = [1,4..10,20]);
+
+ bt_assert(format([ 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 5 ]) = "[1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5]");
+}
+
+bt_test_suite(t_int_set, "Testing sets of integers");
+
+
+
+
+/*
+ * Testing string matching
+ * -----------------------
+ */
+
+function t_string()
+string st;
+{
+ st = "Hello";
+ bt_assert(format(st) = "Hello");
+ bt_assert(st ~ "Hell*");
+ bt_assert(st ~ "?ello");
+ bt_assert(st ~ "Hello");
+ bt_assert(st ~ "Hell?");
+ bt_assert(st !~ "ell*");
+}
+
+bt_test_suite(t_string, "Testing string matching");
+
+
+
+
+/*
+ * Testing pairs
+ * -------------
+ */
+
function 'mkpair-a'(int a)
{
return (1, a);
}
-function mktrip(int a)
+function t_pair()
+pair pp;
{
- return (a, 2*a, 3*a);
+ pp = (1, 2);
+ bt_assert(format(pp) = "(1,2)");
+ bt_assert((1,2) = pp);
+ bt_assert((1,1+1) = pp);
+ bt_assert('mkpair-a'(2) = pp);
+ bt_assert((1,2) = (1,1+1));
+ bt_assert(((1,2) < (2,2)));
+ bt_assert(!((1,1) > (1,1)));
}
-function mkpath(int a; int b)
+bt_test_suite(t_pair, "Testing pairs");
+
+
+
+
+/*
+ * Testing sets of pairs
+ * ---------------------
+ */
+
+function t_pair_set()
+pair pp;
+pair set ps;
{
- return [= a b 3 2 1 =];
+ pp = (1, 2);
+ ps = [(1,(one+one)), (3,4)..(4,8), (5,*), (6,3..6)];
+ bt_assert(format(ps) = "[(1,2), (3,4)..(4,8), (5,0)..(5,65535), (6,3)..(6,6)]");
+ bt_assert(pp ~ ps);
+ bt_assert((3,5) ~ ps);
+ bt_assert((4,1) ~ ps);
+ bt_assert((5,4) ~ ps);
+ bt_assert((5,65535) ~ ps);
+ bt_assert((6,4) ~ ps);
+ bt_assert((3, 10000) ~ ps);
+ bt_assert((3,3) !~ ps);
+ bt_assert((4,9) !~ ps);
+ bt_assert((4,65535) !~ ps);
+ bt_assert((6,2) !~ ps);
+ bt_assert((6,6+one) !~ ps);
+ bt_assert(((one+6),2) !~ ps);
+ bt_assert((1,1) !~ ps);
+
+ ps = [(20..150, 200..300), (50100..50200, 1000..50000), (*, 5+5)];
+ bt_assert((100,200) ~ ps);
+ bt_assert((150,300) ~ ps);
+ bt_assert((50180,1200) ~ ps);
+ bt_assert((50110,49000) ~ ps);
+ bt_assert((0,10) ~ ps);
+ bt_assert((64000,10) ~ ps);
+ bt_assert((20,199) !~ ps);
+ bt_assert((151,250) !~ ps);
+ bt_assert((50050,2000) !~ ps);
+ bt_assert((50150,50050) !~ ps);
+ bt_assert((10,9) !~ ps);
+ bt_assert((65535,11) !~ ps);
}
-function callme(int arg1; int arg2)
-int local1;
-int local2;
-int i;
+bt_test_suite(t_pair_set, "Testing sets of pairs");
+
+
+
+
+/*
+ * Testing quads
+ * -------------
+ */
+
+function t_quad()
+quad qq;
{
- printn "Function callme called arguments ", arg1, " and ", arg2, ": " ;
- i = arg2;
+ qq = 1.2.3.4;
+ bt_assert(format(qq) = "1.2.3.4");
+ bt_assert(qq = 1.2.3.4);
+ bt_assert(qq != 4.3.2.1);
+}
- case arg1 {
- 11, 1, 111: printn "jedna, "; printn "jedna";
- (one+onef(2)): printn "dva, "; printn "jeste jednou dva";
- (2+one) .. 5: if arg2 < 3 then printn "tri az pet";
- else: printn "neco jineho";
- }
- print;
+bt_test_suite(t_quad, "Testing quads");
+
+
+
+
+/*
+ * Testing sets of quads
+ * ---------------------
+ */
+
+function t_quad_set()
+quad qq;
+{
+ qq = 1.2.3.4;
+ bt_assert(qq ~ [1.2.3.4, 5.6.7.8]);
+ bt_assert(qq !~ [1.2.1.1, 1.2.3.5]);
}
-function fifteen()
+bt_test_suite(t_quad_set, "Testing sets of quads");
+
+
+
+
+/*
+ * Testing ip address
+ * ------------------
+ */
+
+define onetwo = 1.2.3.4;
+
+function t_ip()
+ip p;
{
- print "fifteen called";
- return 15;
+ p = 127.1.2.3;
+ bt_assert(p.is_v4);
+ bt_assert(p.mask(8) = 127.0.0.0);
+ bt_assert(1.2.3.4 = 1.2.3.4);
+ bt_assert(1.2.3.4 = onetwo);
+ bt_assert(format(p) = "127.1.2.3");
+
+ p = ::fffe:6:c0c:936d:88c7:35d3;
+ bt_assert(!p.is_v4);
+ bt_assert(format(p) = "::fffe:6:c0c:936d:88c7:35d3");
+
+ p = 1234:5678::;
+ bt_assert(!p.is_v4);
+ bt_assert(p.mask(24) = 1234:5600::);
}
-roa table rl
+bt_test_suite(t_ip, "Testing ip address");
+
+
+
+
+/*
+ * Testing sets of ip address
+ * --------------------------
+ */
+
+define ip1222 = 1.2.2.2;
+
+function t_ip_set()
+ip set ips;
{
- roa 10.110.0.0/16 max 16 as 1000;
- roa 10.120.0.0/16 max 24 as 1000;
- roa 10.130.0.0/16 max 24 as 2000;
- roa 10.130.128.0/18 max 24 as 3000;
+ ips = [ 1.1.1.0 .. 1.1.1.255, ip1222];
+ bt_assert(format(ips) = "[1.1.1.0..1.1.1.255, 1.2.2.2]");
+ bt_assert(1.1.1.0 ~ ips);
+ bt_assert(1.1.1.100 ~ ips);
+ bt_assert(1.2.2.2 ~ ips);
+ bt_assert(1.1.0.255 !~ ips);
+ bt_assert(1.1.2.0 !~ ips);
+ bt_assert(1.2.2.3 !~ ips);
+ bt_assert(192.168.1.1 !~ ips);
+
+ bt_assert(1.2.3.4 !~ [ 1.2.3.3, 1.2.3.5 ]);
+ bt_assert(1.2.3.4 ~ [ 1.2.3.3..1.2.3.5 ]);
}
-function test_roa()
+bt_test_suite(t_ip_set, "Testing sets of ip address");
+
+
+
+
+/*
+ * Testing enums
+ * -------------
+ */
+
+function t_enum()
{
- # cannot be tested in __startup(), sorry
- print "Testing ROA";
- print "Should be true: ", roa_check(rl, 10.10.0.0/16, 1000) = ROA_UNKNOWN,
- " ", roa_check(rl, 10.0.0.0/8, 1000) = ROA_UNKNOWN,
- " ", roa_check(rl, 10.110.0.0/16, 1000) = ROA_VALID,
- " ", roa_check(rl, 10.110.0.0/16, 2000) = ROA_INVALID,
- " ", roa_check(rl, 10.110.32.0/20, 1000) = ROA_INVALID,
- " ", roa_check(rl, 10.120.32.0/20, 1000) = ROA_VALID;
- print "Should be true: ", roa_check(rl, 10.120.32.0/20, 2000) = ROA_INVALID,
- " ", roa_check(rl, 10.120.32.32/28, 1000) = ROA_INVALID,
- " ", roa_check(rl, 10.130.130.0/24, 1000) = ROA_INVALID,
- " ", roa_check(rl, 10.130.130.0/24, 2000) = ROA_VALID,
- " ", roa_check(rl, 10.130.30.0/24, 3000) = ROA_INVALID,
- " ", roa_check(rl, 10.130.130.0/24, 3000) = ROA_VALID;
-}
-
-function path_test()
+ bt_assert(format(RTS_DUMMY) = "(enum 30)0");
+ bt_assert(format(RTS_STATIC) = "(enum 30)1");
+ bt_assert(RTS_STATIC ~ [RTS_STATIC, RTS_DEVICE]);
+ bt_assert(RTS_BGP !~ [RTS_STATIC, RTS_DEVICE]);
+}
+
+bt_test_suite(t_enum, "Testing enums");
+
+
+
+
+/*
+ * Testing prefixes
+ * ----------------
+ */
+
+define netdoc = 2001:db8::/32;
+
+function t_prefix()
+prefix px;
+{
+ px = 1.2.0.0/18;
+ bt_assert(format(px) = "1.2.0.0/18");
+ bt_assert(192.168.0.0/16 ~ 192.168.0.0/16);
+ bt_assert(192.168.0.0/17 ~ 192.168.0.0/16);
+ bt_assert(192.168.254.0/24 ~ 192.168.0.0/16);
+ bt_assert(netdoc ~ 2001::/16);
+ bt_assert(192.168.0.0/15 !~ 192.168.0.0/16);
+ bt_assert(192.160.0.0/17 !~ 192.168.0.0/16);
+ bt_assert(px !~ netdoc);
+
+ bt_assert(1.2.3.4 ~ 1.0.0.0/8);
+ bt_assert(1.0.0.0/8 ~ 1.0.0.0/8);
+}
+
+bt_test_suite(t_prefix, "Testing prefixes");
+
+
+
+
+/*
+ * Testing prefix sets
+ * -------------------
+ */
+
+define net10 = 10.0.0.0/8;
+define pxs2 = [ 10.0.0.0/16{8,12}, 20.0.0.0/16{24,28} ];
+
+function test_pxset(prefix set pxs)
+{
+ bt_assert(net10 ~ pxs);
+ bt_assert(10.0.0.0/10 ~ pxs);
+ bt_assert(10.0.0.0/12 ~ pxs);
+ bt_assert(20.0.0.0/24 ~ pxs);
+ bt_assert(20.0.40.0/24 ~ pxs);
+ bt_assert(20.0.0.0/26 ~ pxs);
+ bt_assert(20.0.100.0/26 ~ pxs);
+ bt_assert(20.0.0.0/28 ~ pxs);
+ bt_assert(20.0.255.0/28 ~ pxs);
+
+ bt_assert(10.0.0.0/7 !~ pxs);
+ bt_assert(10.0.0.0/13 !~ pxs);
+ bt_assert(10.0.0.0/16 !~ pxs);
+ bt_assert(20.0.0.0/16 !~ pxs);
+ bt_assert(20.0.0.0/23 !~ pxs);
+ bt_assert(20.0.0.0/29 !~ pxs);
+ bt_assert(11.0.0.0/10 !~ pxs);
+ bt_assert(20.1.0.0/26 !~ pxs);
+
+ bt_assert(1.0.0.0/8 ~ [ 1.0.0.0/8+ ]);
+ bt_assert(1.0.0.0/9 !~ [ 1.0.0.0/8- ]);
+ bt_assert(1.2.0.0/17 !~ [ 1.0.0.0/8{ 15 , 16 } ]);
+
+ bt_assert([ 10.0.0.0/8{ 15 , 17 } ] = [ 10.0.0.0/8{ 15 , 17 } ]);
+}
+
+function t_prefix_set()
+prefix set pxs;
+{
+ pxs = [ 1.2.0.0/16, 1.4.0.0/16+, 44.66.88.64/30{24,28}, 12.34.56.0/24{8,16} ];
+ bt_assert(format(pxs) = "[1.2.0.0/112{::0.1.0.0}, 1.4.0.0/112{::0.1.255.255}, 12.34.0.0/112{::1.255.0.0}, 44.66.88.64/124{::1f0}]");
+ bt_assert(1.2.0.0/16 ~ pxs);
+ bt_assert(1.4.0.0/16 ~ pxs);
+ bt_assert(1.4.0.0/18 ~ pxs);
+ bt_assert(1.4.0.0/32 ~ pxs);
+ bt_assert(1.1.0.0/16 !~ pxs);
+ bt_assert(1.3.0.0/16 !~ pxs);
+ bt_assert(1.2.0.0/15 !~ pxs);
+ bt_assert(1.2.0.0/17 !~ pxs);
+ bt_assert(1.2.0.0/32 !~ pxs);
+ bt_assert(1.4.0.0/15 !~ pxs);
+
+ test_pxset(pxs2);
+ test_pxset([ 10.0.0.0/16{8,12}, 20.0.0.0/16{24,28} ]);
+
+ bt_assert(1.2.0.0/16 ~ [ 1.0.0.0/8{ 15 , 17 } ]);
+ bt_assert([ 10.0.0.0/8{ 15 , 17 } ] != [ 11.0.0.0/8{ 15 , 17 } ]);
+}
+
+bt_test_suite(t_prefix_set, "Testing prefix sets");
+
+
+
+
+/*
+ * Testing Prefix IPv6
+ * -------------------
+ */
+
+function t_prefix6()
+prefix px;
+{
+ px = 1020::/18;
+ bt_assert(format(px) = "1020::/18");
+ bt_assert(1020:3040:5060:: ~ 1020:3040:5000::/40);
+ bt_assert(1020:3040::/32 ~ 1020:3040::/32);
+ bt_assert(1020:3040::/33 ~ 1020:3040::/32);
+ bt_assert(1020:3040:5060::/48 ~ 1020:3040::/32);
+ bt_assert(1020:3040::/31 !~ 1020:3040::/32);
+ bt_assert(1020:3041::/33 !~ 1020:3040::/32);
+}
+
+bt_test_suite(t_prefix6, "Testing prefix IPv6");
+
+
+
+
+/*
+ * Testing prefix IPv6 sets
+ * ------------------------
+ */
+
+function t_prefix6_set()
+prefix set pxs;
+{
+ bt_assert(1180::/16 ~ [ 1100::/8{15, 17} ]);
+ bt_assert(12::34 = 12::34);
+ bt_assert(12::34 ~ [ 12::33..12::35 ]);
+ bt_assert(1020::34 ~ 1000::/8);
+ bt_assert(1000::/8 ~ 1000::/8);
+ bt_assert(1000::/8 ~ [ 1000::/8+ ]);
+ bt_assert(12::34 !~ [ 12::33, 12::35 ]);
+ bt_assert(1000::/9 !~ [ 1000::/8- ]);
+ bt_assert(1000::/17 !~ [ 1000::/8{15, 16} ]);
+
+ pxs = [ 1102::/16, 1104::/16+];
+ bt_assert(1102::/16 ~ pxs);
+ bt_assert(1104::/16 ~ pxs);
+ bt_assert(1104::/18 ~ pxs);
+ bt_assert(1104::/32 ~ pxs);
+ bt_assert(1101::/16 !~ pxs);
+ bt_assert(1103::/16 !~ pxs);
+ bt_assert(1102::/15 !~ pxs);
+ bt_assert(1102::/17 !~ pxs);
+ bt_assert(1102::/32 !~ pxs);
+ bt_assert(1104::/15 !~ pxs);
+
+ pxs = ([ 1000::/16{8,12}, 2000::/16{24,28} ]);
+ bt_assert(format(pxs) = "[1000::/12{1f0::}, 2000::/16{0:1f0::}]");
+ bt_assert(1000::/8 ~ pxs);
+ bt_assert(1000::/10 ~ pxs);
+ bt_assert(1000::/12 ~ pxs);
+ bt_assert(2000::/24 ~ pxs);
+ bt_assert(2000:4000::/24 ~ pxs);
+ bt_assert(2000::/26 ~ pxs);
+ bt_assert(2000:8000::/26 ~ pxs);
+ bt_assert(2000::/28 ~ pxs);
+ bt_assert(2000:FFF0::/28 ~ pxs);
+ bt_assert(1000::/7 !~ pxs);
+ bt_assert(1000::/13 !~ pxs);
+ bt_assert(1000::/16 !~ pxs);
+ bt_assert(2000::/16 !~ pxs);
+ bt_assert(2000::/23 !~ pxs);
+ bt_assert(2000::/29 !~ pxs);
+ bt_assert(1100::/10 !~ pxs);
+ bt_assert(2010::/26 !~ pxs);
+}
+
+bt_test_suite(t_prefix6_set, "Testing prefix IPv6 sets");
+
+
+
+
+function t_flowspec()
+prefix p;
+{
+ p = flow4 { dst 10.0.0.0/8; };
+ bt_assert(p !~ [ 10.0.0.0/8 ] );
+
+ bt_assert(format(flow4 { dst 10.0.0.0/8; proto = 23; }) = "flow4 { dst 10.0.0.0/8; proto 23; }");
+ bt_assert(format(flow6 { dst ::1/128; src ::2/127; }) = "flow6 { dst ::1/128; src ::2/127; }");
+ bt_assert(format(flow6 { next header false 42; }) = "flow6 { next header false 42; }");
+ bt_assert(format(flow6 { port 80; }) = "flow6 { port 80; }");
+ bt_assert(format(flow6 { dport > 24 && < 30 || 40..50,60..70,80 && >= 90; }) = "flow6 { dport > 24 && < 30 || 40..50,60..70,80 && >= 90; }");
+ bt_assert(format(flow6 { sport 0..0x400; }) = "flow6 { sport 0..1024; }");
+ bt_assert(format(flow6 { icmp type 80; }) = "flow6 { icmp type 80; }");
+ bt_assert(format(flow6 { icmp code 90; }) = "flow6 { icmp code 90; }");
+ bt_assert(format(flow6 { tcp flags 0x03/0x0f; }) = "flow6 { tcp flags 0x3/0x3,0x0/0xc; }");
+ bt_assert(format(flow6 { length 0..65535; }) = "flow6 { length 0..65535; }");
+ bt_assert(format(flow6 { dscp = 63; }) = "flow6 { dscp 63; }");
+ bt_assert(format(flow6 { fragment is_fragment || !first_fragment; }) = "flow6 { fragment is_fragment || !first_fragment; }");
+ bt_assert(format(flow6 { }) = "flow6 { }");
+}
+
+bt_test_suite(t_flowspec, "Testing flowspec routes");
+
+
+
+
+/*
+ * Testing Paths
+ * -------------
+ */
+
+function mkpath(int a; int b)
+{
+ return [= a b 3 2 1 =];
+}
+
+function t_path()
bgpmask pm1;
-bgpmask pm2;
bgppath p2;
-clist l;
-clist l2;
-eclist el;
-eclist el2;
-lclist ll;
-lclist ll2;
{
- print "Entering path test...";
- pm1 = / 4 3 2 1 /;
- pm2 = [= 3..6 3 2 1..2 =];
- print "Testing path masks: ", pm1, " ", pm2;
+ pm1 = [= 4 3 2 1 =];
+
+ bt_assert(format(pm1) = "[= 4 3 2 1 =]");
+
+ bt_assert(+empty+ = +empty+);
+ bt_assert(10 !~ +empty+);
+
p2 = prepend( + empty +, 1 );
p2 = prepend( p2, 2 );
p2 = prepend( p2, 3 );
p2 = prepend( p2, 4 );
- print "Testing path: (4 3 2 1) = ", p2;
- print "Should be true: ", p2 ~ pm1, " ", p2 ~ pm2, " ", 3 ~ p2, " ", p2 ~ [2, 10..20], " ", p2 ~ [4, 10..20];
- print "4 = ", p2.len;
- p2 = prepend( p2, 5 );
- print "Testing path: (5 4 3 2 1) = ", p2;
- print "Should be false: ", p2 ~ pm1, " ", p2 ~ pm2, " ", 10 ~ p2, " ", p2 ~ [8, ten..(2*ten)], " ", p2 ~ [= 1..4 4 3 2 1 =], " ", p2 ~ [= 5 4 4..100 2 1 =];
- print "Should be true: ", p2 ~ / ? 4 3 2 1 /, " ", p2, " ", / ? 4 3 2 1 /;
- print "Should be true: ", p2 ~ [= * 4 3 * 1 =], " ", p2, " ", [= * 4 3 * 1 =];
- print "Should be true: ", p2 ~ [= 5..6 4..10 1..3 1..3 1..65536 =];
- print "Should be true: ", p2 ~ [= (3+2) (2*2) 3 2 1 =], " ", p2 ~ mkpath(5, 4);
- print "Should be true: ", p2.len = 5, " ", p2.first = 5, " ", p2.last = 1;
- print "Should be true: ", pm1 = [= 4 3 2 1 =], " ", pm1 != [= 4 3 1 2 =], " ",
- pm2 = [= 3..6 3 2 1..2 =], " ", pm2 != [= 3..6 3 2 1..3 =], " ",
- [= 1 2 (1+2) =] = [= 1 2 (1+2) =], " ", [= 1 2 (1+2) =] != [= 1 2 (2+1) =];
- print "5 = ", p2.len;
- print "Delete 3: ", delete(p2, 3);
- print "Filter 1-3: ", filter(p2, [1..3]);
+
+ bt_assert(format(p2) = "(path 4 3 2 1)");
+ bt_assert(p2.len = 4);
+ bt_assert(p2 ~ pm1);
+ bt_assert(3 ~ p2);
+ bt_assert(p2 ~ [2, 10..20]);
+ bt_assert(p2 ~ [4, 10..20]);
+
+ p2 = prepend(p2, 5);
+ bt_assert(p2 !~ pm1);
+ bt_assert(10 !~ p2);
+ bt_assert(p2 !~ [8, ten..(2*ten)]);
+ bt_assert(p2 ~ [= * 4 3 * 1 =]);
+ bt_assert(p2 ~ [= (3+2) (2*2) 3 2 1 =]);
+ bt_assert(p2 ~ mkpath(5, 4));
+
+ bt_assert(p2.len = 5);
+ bt_assert(p2.first = 5);
+ bt_assert(p2.last = 1);
+
+ bt_assert(p2.len = 5);
+ 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 );
@@ -130,63 +633,176 @@ lclist ll2;
p2 = prepend( p2, 3 );
p2 = prepend( p2, 2 );
p2 = prepend( p2, 1 );
- print "Should be true: ", p2 ~ pm1, " ", p2, " ", pm1;
- print "Delete 3: ", delete(p2, 3);
- print "Delete 4-5: ", delete(p2, [4..5]);
+ bt_assert(p2 ~ pm1);
+ 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_test_suite(t_path, "Testing paths");
+
+
+
+
+/*
+ * Testing Community List
+ * ----------------------
+ */
+
+define p23 = (2, 3);
+
+function t_clist()
+clist l;
+clist l2;
+clist r;
+{
l = - empty -;
- print "Should be false in this special case: ", l ~ [(*,*)];
+ bt_assert(l !~ [(*,*)]);
+ bt_assert((l ~ [(*,*)]) != (l !~ [(*,*)]));
+
+ bt_assert(-empty- = -empty-);
+
l = add( l, (one,2) );
- print "Should be always true: ", l ~ [(*,*)];
+ bt_assert(l ~ [(*,*)]);
l = add( l, (2,one+2) );
- print "Community list (1,2) (2,3) ", l;
- print "Should be true: ", (2,3) ~ l, " ", l ~ [(1,*)], " ", l ~ [p23]," ", l ~ [(2,2..3)], " ", l ~ [(1,1..2)], " ", l ~ [(1,1)..(1,2)];
- l = add( l, (2,5) );
- l = add( l, (5,one) );
- l = add( l, (6,one) );
- l = add( l, (one,one) );
- l = delete( l, [(5,1),(6,one),(one,1)] );
- l = delete( l, [(5,one),(6,one)] );
- l = filter( l, [(1,*)] );
- print "Community list (1,2) ", l;
- print "Should be false: ", (2,3) ~ l, " ", l ~ [(2,*)], " ", l ~ [(one,3..6)];
- print "Should be always true: ", l ~ [(*,*)];
- l = add( l, (3,one) );
- l = add( l, (one+one+one,one+one) );
- l = add( l, (3,3) );
- l = add( l, (3,4) );
- l = add( l, (3,5) );
- l2 = filter( l, [(3,*)] );
- l = delete( l, [(3,2..4)] );
- print "Community list (1,2) (3,1) (3,5) ", l, " len: ", l.len;
- l = add( l, (3,2) );
- l = add( l, (4,5) );
- print "Community list (1,2) (3,1) (3,5) (3,2) (4,5) ", l, " len: ", l.len;
- print "Should be true: ", l ~ [(*,2)], " ", l ~ [(*,5)], " ", l ~ [(*, one)];
- print "Should be false: ", l ~ [(*,3)], " ", l ~ [(*,(one+6))], " ", l ~ [(*, (one+one+one))];
- l = delete( l, [(*,(one+onef(3)))] );
- l = delete( l, [(*,(4+one))] );
- print "Community list (3,1) ", l;
- l = delete( l, [(*,(onef(5)))] );
- print "Community list empty ", l;
- l2 = add( l2, (3,6) );
- l = filter( l2, [(3,1..4)] );
- l2 = filter( l2, [(3,3..6)] );
- print "clist A (1..4): ", l;
- print "clist B (3..6): ", l2;
- print "clist A union B: ", add( l2, l );
- print "clist A isect B: ", filter( l, l2 );
- print "clist A \ B: ", delete( l, l2 );
+ bt_assert(format(l) = "(clist (1,2) (2,3))");
+
+ bt_assert((2,3) ~ l);
+ bt_assert(l ~ [(1,*)]);
+ bt_assert(l ~ [p23]);
+ bt_assert(l ~ [(2,2..3)]);
+ bt_assert(l ~ [(1,1..2)]);
+ bt_assert(l ~ [(1,1)..(1,2)]);
+
+ l = add(l, (2,5));
+ l = add(l, (5,one));
+ l = add(l, (6,one));
+ l = add(l, (one,one));
+ l = delete(l, [(5,1),(6,one),(one,1)]);
+ l = delete(l, [(5,one),(6,one)]);
+ l = filter(l, [(1,*)]);
+ bt_assert(l = add(-empty-, (1,2)));
+
+ bt_assert((2,3) !~ l);
+ bt_assert(l !~ [(2,*)]);
+ bt_assert(l !~ [(one,3..6)]);
+ bt_assert(l ~ [(*,*)]);
+
+ l = add(l, (3,one));
+ l = add(l, (one+one+one,one+one));
+ l = add(l, (3,3));
+ l = add(l, (3,4));
+ l = add(l, (3,5));
+ l2 = filter(l, [(3,*)]);
+ l = delete(l, [(3,2..4)]);
+ bt_assert(l = add(add(add(-empty-, (1,2)), (3,1)), (3,5)));
+ bt_assert(l.len = 3);
+
+ l = add(l, (3,2));
+ l = add(l, (4,5));
+ bt_assert(l = add(add(add(add(add(-empty-, (1,2)), (3,1)), (3,5)), (3,2)), (4,5)));
+
+ bt_assert(l.len = 5);
+ bt_assert(l ~ [(*,2)]);
+ bt_assert(l ~ [(*,5)]);
+ bt_assert(l ~ [(*, one)]);
+ bt_assert(l !~ [(*,3)]);
+ bt_assert(l !~ [(*,(one+6))]);
+ bt_assert(l !~ [(*, (one+one+one))]);
+
+ l = delete(l, [(*,(one+onef(3)))]);
+ l = delete(l, [(*,(4+one))]);
+ bt_assert(l = add(-empty-, (3,1)));
+ l = delete(l, [(*,(onef(5)))]);
+ bt_assert(l = -empty-);
+
+ l2 = add(l2, (3,6));
+ l = filter(l2, [(3,1..4)]);
+ l2 = filter(l2, [(3,3..6)]);
+
+ # clist A (10,20,30)
+ bt_assert(l = add(add(add(add(-empty-, (3,1)), (3,2)), (3,3)), (3,4)));
+ bt_assert(format(l) = "(clist (3,1) (3,2) (3,3) (3,4))");
+
+ # clist B (30,40,50)
+ bt_assert(l2 = add(add(add(add(-empty-, (3,3)), (3,4)), (3,5)), (3,6)));
+ bt_assert(format(l2) = "(clist (3,3) (3,4) (3,5) (3,6))");
+
+ # clist A union B
+ r = add(l, l2);
+ bt_assert(r = add(add(add(add(add(add(-empty-, (3,1)), (3,2)), (3,3)), (3,4)), (3,5)), (3,6)));
+ bt_assert(format(r) = "(clist (3,1) (3,2) (3,3) (3,4) (3,5) (3,6))");
+
+ # clist A isect B
+ r = filter(l, l2);
+ bt_assert(r = add(add(-empty-, (3,3)), (3,4)));
+ bt_assert(format(r) = "(clist (3,3) (3,4))");
+
+ # clist A \ B
+ r = delete(l, l2);
+ bt_assert(r = add(add(-empty-, (3,1)), (3,2)));
+ bt_assert(format(r) = "(clist (3,1) (3,2))");
+
+ # clist in c set
+ r = filter(l, [(3,1), (*,2)]);
+ bt_assert(r = add(add(-empty-, (3,1)), (3,2)));
+ bt_assert(format(r) = "(clist (3,1) (3,2))");
+}
+
+bt_test_suite(t_clist, "Testing lists of communities");
+
+
+
+
+/*
+ * Testing Extended Communities
+ * ----------------------------
+ */
+
+function t_ec()
+ec cc;
+{
+ cc = (rt, 12345, 200000);
+ bt_assert(format(cc) = "(rt, 12345, 200000)");
+
+ bt_assert(cc = (rt, 12345, 200000));
+ bt_assert(cc < (rt, 12345, 200010));
+ bt_assert(cc != (rt, 12346, 200000));
+ bt_assert(cc != (ro, 12345, 200000));
+ bt_assert(!(cc > (rt, 12345, 200010)));
+
+ bt_assert(format((ro, 100000, 20000)) = "(ro, 100000, 20000)");
+}
+
+bt_test_suite(t_ec, "Testing extended communities");
+
+
+
+
+/*
+ * Testing Extended Community List
+ * -------------------------------
+ */
+
+function t_eclist()
+eclist el;
+eclist el2;
+eclist r;
+{
el = -- empty --;
el = add(el, (rt, 10, 20));
el = add(el, (ro, 10.20.30.40, 100));
el = add(el, (ro, 11.21.31.41.mask(16), 200));
- print "EC list (rt, 10, 20) (ro, 10.20.30.40, 100) (ro, 11.21.0.0, 200):";
- print el;
- print "EC len: ", el.len;
+
+ bt_assert(--empty-- = --empty--);
+ bt_assert(((rt, 10, 20)) !~ --empty--);
+
+ bt_assert(format(el) = "(eclist (rt, 10, 20) (ro, 10.20.30.40, 100) (ro, 11.21.0.0, 200))");
+ bt_assert(el.len = 3);
el = delete(el, (rt, 10, 20));
el = delete(el, (rt, 10, 30));
+ bt_assert(el = add(add(--empty--, (ro, 10.20.30.40, 100)), (ro, 11.21.0.0, 200)));
el = add(el, (unknown 2, ten, 1));
el = add(el, (unknown 5, ten, 1));
el = add(el, (rt, ten, one+one));
@@ -195,31 +811,117 @@ lclist ll2;
el = add(el, (rt, 10, 5));
el = add(el, (generic, 0x2000a, 3*ten));
el = delete(el, [(rt, 10, 2..ten)]);
- print "EC list (ro, 10.20.30.40, 100) (ro, 11.21.0.0, 200) (rt, 10, 1) (unknown 0x5, 10, 1) (rt, 10, 30):";
- print el;
+ bt_assert(el = add(add(add(add(add(--empty--, (ro, 10.20.30.40, 100)), (ro, 11.21.0.0, 200)), (rt, 10, 1)), (unknown 5, 10, 1)), (rt, 10, 30)));
+
el = filter(el, [(rt, 10, *)]);
- print "EC list (rt, 10, 1) (rt, 10, 30): ", el;
- print "Testing EC list, true: ", (rt, 10, 1) ~ el, " ", el ~ [(rt, 10, ten..40)];
- print "Testing EC list, false: ", (rt, 10, 20) ~ el, " ", (ro, 10.20.30.40, 100) ~ el, " ", el ~ [(rt, 10, 35..40)], " ", el ~ [(ro, 10, *)];
+ bt_assert(el = add(add(--empty--, (rt, 10, 1)), (rt, 10, 30)));
+ bt_assert((rt, 10, 1) ~ el);
+ bt_assert(el ~ [(rt, 10, ten..40)]);
+ bt_assert((rt, 10, 20) !~ el);
+ bt_assert((ro, 10.20.30.40, 100) !~ el);
+ bt_assert(el !~ [(rt, 10, 35..40)]);
+ bt_assert(el !~ [(ro, 10, *)]);
+
el = add(el, (rt, 10, 40));
el2 = filter(el, [(rt, 10, 20..40)] );
el2 = add(el2, (rt, 10, 50));
- print "eclist A (1,30,40): ", el;
- print "eclist B (30,40,50): ", el2;
- print "eclist A union B: ", add( el2, el );
- print "eclist A isect B: ", filter( el, el2 );
- print "eclist A \ B: ", delete( el, el2 );
+
+ # eclist A (1,30,40)
+ bt_assert(el = add(add(add(--empty--, (rt, 10, 1)), (rt, 10, 30)), (rt, 10, 40)));
+ bt_assert(format(el) = "(eclist (rt, 10, 1) (rt, 10, 30) (rt, 10, 40))");
+
+ # eclist B (30,40,50)
+ bt_assert(el2 = add(add(add(--empty--, (rt, 10, 30)), (rt, 10, 40)), (rt, 10, 50)));
+ bt_assert(format(el2) = "(eclist (rt, 10, 30) (rt, 10, 40) (rt, 10, 50))");
+
+ # eclist A union B
+ r = add(el2, el);
+ bt_assert(r = add(add(add(add(--empty--, (rt, 10, 30)), (rt, 10, 40)), (rt, 10, 50)), (rt, 10, 1)));
+ bt_assert(format(r) = "(eclist (rt, 10, 30) (rt, 10, 40) (rt, 10, 50) (rt, 10, 1))");
+
+ # eclist A isect B
+ r = filter(el, el2);
+ bt_assert(r = add(add(--empty--, (rt, 10, 30)), (rt, 10, 40)));
+ bt_assert(format(r) = "(eclist (rt, 10, 30) (rt, 10, 40))");
+
+ # eclist A \ B
+ r = delete(el, el2);
+ bt_assert(r = add(--empty--, (rt, 10, 1)));
+ bt_assert(format(r) = "(eclist (rt, 10, 1))");
+
+ # eclist in ec set
+ r = filter(el, [(rt, 10, 1), (rt, 10, 25..30), (ro, 10, 40)]);
+ bt_assert(r = add(add(--empty--, (rt, 10, 1)), (rt, 10, 30)));
+ bt_assert(format(r) = "(eclist (rt, 10, 1) (rt, 10, 30))");
+}
+
+bt_test_suite(t_eclist, "Testing lists of extended communities");
+
+
+
+
+/*
+ * Testing sets of Extended Communities
+ * ------------------------------------
+ */
+
+define ecs2 = [(rt, ten, (one+onef(0))*10), (ro, 100000, 100..200), (rt, 12345, *)];
+
+function t_ec_set()
+ec set ecs;
+{
+ ecs = [(rt, ten, (one+onef(0))*10), (ro, 100000, 100..200), (rt, 12345, *)];
+ bt_assert(format(ecs) = "[(rt, 10, 20), (rt, 12345, 0)..(rt, 12345, 4294967295), (ro, 100000, 100)..(ro, 100000, 200)]");
+ bt_assert(format(ecs2) = "[(rt, 10, 20), (rt, 12345, 0)..(rt, 12345, 4294967295), (ro, 100000, 100)..(ro, 100000, 200)]");
+
+ bt_assert((rt, 10, 20) ~ ecs);
+ bt_assert((ro, 100000, 100) ~ ecs);
+ bt_assert((ro, 100000, 128) ~ ecs);
+ bt_assert((ro, 100000, 200) ~ ecs);
+ bt_assert((rt, 12345, 0) ~ ecs);
+ bt_assert((rt, 12345, 200000) ~ ecs);
+ bt_assert((rt, 12345, 4000000) ~ ecs);
+ bt_assert((ro, 10, 20) !~ ecs);
+ bt_assert((rt, 10, 21) !~ ecs);
+ bt_assert((ro, 100000, 99) !~ ecs);
+ bt_assert((ro, 12345, 10) !~ ecs);
+ bt_assert((rt, 12346, 0) !~ ecs);
+ bt_assert((ro, 0.1.134.160, 150) !~ ecs);
+}
+
+bt_test_suite(t_ec_set, "Testing sets of extended communities");
+
+
+
+
+/*
+ * Testing Large Communities
+ * -------------------------
+ */
+
+function mktrip(int a)
+{
+ return (a, 2*a, 3*a);
+}
+
+function t_lclist()
+lclist ll;
+lclist ll2;
+lclist r;
+{
+ bt_assert(---empty--- = ---empty---);
+ bt_assert((10, 20, 30) !~ ---empty---);
ll = --- empty ---;
ll = add(ll, (ten, 20, 30));
ll = add(ll, (1000, 2000, 3000));
ll = add(ll, mktrip(100000));
- print "LC list (10, 20, 30) (1000, 2000, 3000) (100000, 200000, 300000):";
- print ll;
- print "LC len: ", el.len;
- print "Should be true: ", mktrip(1000) ~ ll, " ", ll ~ [(5,10,15), (10,20,30)], " ", ll ~ [(10,15..25,*)], " ", ll ~ [(ten, *, *)];
- print "Should be false: ", mktrip(100) ~ ll, " ", ll ~ [(5,10,15), (10,21,30)], " ", ll ~ [(10,21..25,*)], " ", ll ~ [(11, *, *)];
- print "LC filtered: ", filter(ll, [(5..15, *, *), (100000, 500..500000, *)]);
+ bt_assert(format(ll) = "(lclist (10, 20, 30) (1000, 2000, 3000) (100000, 200000, 300000))");
+ bt_assert(ll.len = 3);
+ bt_assert(ll = add(add(add(---empty---, (10, 20, 30)), (1000, 2000, 3000)), (100000, 200000, 300000)));
+
+ bt_assert(mktrip(1000) ~ ll);
+ bt_assert(mktrip(100) !~ ll);
ll = --- empty ---;
ll = add(ll, (10, 10, 10));
@@ -231,240 +933,375 @@ lclist ll2;
ll2 = add(ll2, (30, 30, 30));
ll2 = add(ll2, (40, 40, 40));
- print "lclist A (10,20,30): ", ll;
- print "lclist B (20,30,40): ", ll2;
- print "lclist A union B: ", add(ll, ll2);
- print "lclist A isect B: ", filter(ll, ll2);
- print "lclist A \ B: ", delete(ll, ll2);
+ # lclist A (10, 20, 30)
+ bt_assert(format(ll) = "(lclist (10, 10, 10) (20, 20, 20) (30, 30, 30))");
-# test_roa();
-}
+ # lclist B (20, 30, 40)
+ bt_assert(format(ll2) = "(lclist (20, 20, 20) (30, 30, 30) (40, 40, 40))");
-function bla()
-{
- print "fifteen called";
- return 15;
-}
+ # lclist A union B
+ r = add(ll, ll2);
+ bt_assert(r = add(add(add(add(---empty---, (10,10,10)), (20,20,20)), (30,30,30)), (40,40,40)));
+ bt_assert(format(r) = "(lclist (10, 10, 10) (20, 20, 20) (30, 30, 30) (40, 40, 40))");
-define four=4;
-define onetwo=1.2.3.4;
+ # lclist A isect B
+ r = filter(ll, ll2);
+ bt_assert(r = add(add(---empty---, (20, 20, 20)), (30, 30, 30)));
+ bt_assert(format(r) = "(lclist (20, 20, 20) (30, 30, 30))");
-function __test1()
-{
- if source ~ [ RTS_BGP, RTS_STATIC ] then {
-# ospf_metric1 = 65535;
-# ospf_metric2 = 1000;
- ospf_tag = 0x12345678;
- accept;
- } reject;
-}
+ # lclist A \ B
+ r = delete(ll, ll2);
+ bt_assert(r = add(---empty---, (10, 10, 10)));
+ bt_assert(format(r) = "(lclist (10, 10, 10))");
-function __test2()
-{
- if source ~ [ RTS_BGP, RTS_STATIC ] then {
-# ospf_metric1 = 65535;
-# ospf_metric2 = 1000;
- ospf_tag = 0x12345678;
- accept;
- } reject;
+ # lclist in lc set
+ r = filter(ll, [(5..15, *, *), (20, 15..25, *)]);
+ bt_assert(r = add(add(---empty---, (10, 10, 10)), (20, 20, 20)));
+ bt_assert(format(r) = "(lclist (10, 10, 10) (20, 20, 20))");
}
-function test_pxset(prefix set pxs)
+bt_test_suite(t_lclist, "Testing lists of large communities");
+
+
+
+
+/*
+ * Testing sets of Large Communities
+ * ---------------------------------
+ */
+
+function t_lclist_set()
+lclist ll;
+lc set lls;
{
- print pxs;
- print " must be true: ", 10.0.0.0/8 ~ pxs, ",", 10.0.0.0/10 ~ pxs, ",", 10.0.0.0/12 ~ pxs, ",",
- 20.0.0.0/24 ~ pxs, ",", 20.0.40.0/24 ~ pxs, ",", 20.0.0.0/26 ~ pxs, ",",
- 20.0.100.0/26 ~ pxs, ",", 20.0.0.0/28 ~ pxs, ",", 20.0.255.0/28 ~ pxs;
- print " must be false: ", 10.0.0.0/7 ~ pxs, ",", 10.0.0.0/13 ~ pxs, ",", 10.0.0.0/16 ~ pxs, ",",
- 20.0.0.0/16 ~ pxs, ",", 20.0.0.0/23 ~ pxs, ",", 20.0.0.0/29 ~ pxs, ",",
- 11.0.0.0/10 ~ pxs, ",", 20.1.0.0/26 ~ pxs;
+ ll = --- empty ---;
+ ll = add(ll, (10, 20, 30));
+ ll = add(ll, (1000, 2000, 3000));
+ ll = add(ll, mktrip(100000));
+
+ bt_assert(ll ~ [(5,10,15), (10,20,30)]);
+ bt_assert(ll ~ [(10,15..25,*)]);
+ bt_assert(ll ~ [(ten, *, *)]);
+
+ bt_assert(ll !~ [(5,10,15), (10,21,30)]);
+ bt_assert(ll !~ [(10,21..25,*)]);
+ bt_assert(ll !~ [(11, *, *)]);
+
+ lls = [(10, 10, 10), (20, 20, 15..25), (30, 30, *), (40, 35..45, *), (50, *, *), (55..65, *, *)];
+ bt_assert(format(lls) = "[(10, 10, 10), (20, 20, 15)..(20, 20, 25), (30, 30, 0)..(30, 30, 4294967295), (40, 35, 0)..(40, 45, 4294967295), (50, 0, 0)..(50, 4294967295, 4294967295), (55, 0, 0)..(65, 4294967295, 4294967295)]");
+ bt_assert((10, 10, 10) ~ lls);
+ bt_assert((20, 20, 25) ~ lls);
+ bt_assert((20, 20, 26) !~ lls);
+ bt_assert((30, 30, 0) ~ lls);
+ bt_assert((40, 35, 40) ~ lls);
+ bt_assert((40, 34, 40) !~ lls);
+ bt_assert((50, 0, 0) ~ lls);
+ bt_assert((60, 60, 60) ~ lls);
+ bt_assert((70, 60, 60) !~ lls);
}
+bt_test_suite(t_lclist_set, "Testing sets of large communities");
+
+
+
+
+/*
+ * Testing defined() function
+ * --------------------------
+ */
+
function test_undef(int a)
int b;
{
- if a = 3
- then b = 4;
- print "Defined: ", a, " ", b, " ", defined(b);
+ if a = 3 then {
+ b = 4;
+ bt_assert(defined(b));
+ }
+ else {
+ bt_assert(!defined(b));
+ }
}
-define is1 = [ one, (2+1), (6-one), 8, 11, 15, 17, 19];
-define is2 = [(17+2), 17, 15, 11, 8, 5, 3, 2];
-define is3 = [5, 17, 2, 11, 8, 15, 3, 19];
+function t_define()
+int i;
+{
+ test_undef(2);
+ test_undef(3);
+ test_undef(2);
-define pxs2 = [ 10.0.0.0/16{8,12}, 20.0.0.0/16{24,28} ];
+ bt_assert(defined(1));
+ bt_assert(defined(1.2.3.4));
+}
-define ecs2 = [(rt, ten, (one+onef(0))*10), (ro, 100000, 100..200), (rt, 12345, *)];
+bt_test_suite(t_define, "Testing defined() function");
-function __startup()
+
+
+/*
+ * Testing calling functions
+ * -------------------------
+ */
+
+function callme(int arg1; int arg2)
int i;
-bool b;
-prefix px;
-ip p;
-pair pp;
-quad qq;
-ec cc;
-int set is;
-pair set ps;
-ec set ecs;
-ip set ips;
-prefix set pxs;
-string st;
{
- print "1a-a1 = 30: ", '1a-a1';
- print "Testing filter language:";
- i = four;
- i = 12*100 + 60/2 + i;
- i = ( i + 0 );
- print " arithmetics: 1234 = ", i;
- printn " if statements ";
- print "what happens here?";
- printn ".";
- if (i = 4) then { print "*** FAIL: if 0"; quitbird; } else printn ".";
-# if !(i = 3) then { print "*** FAIL: if 0"; quitbird; } else printn ".";
- if 1234 = i then printn "."; else { print "*** FAIL: if 1 else"; }
-# if 1 <= 1 then printn "."; else { print "*** FAIL: test 3"; }
- if 1234 < 1234 then { print "*** FAIL: test 4"; quitbird; } else print "ok";
- is = [ 2, 3, 4, 7..11 ];
+ case arg1 {
+ 1, 42: return 42;
+ else: return arg1 * arg2;
+ }
- print "must be true: ", 1 = 1, " ", 1 != (0,1), " ", 1 != "a", " ", +empty+ = +empty+, " ", -empty- = -empty-, " ", --empty-- = --empty-- ,
- " ", [1,4..10,20] = [1,4..10,20] , " ", [ 10.0.0.0/8{ 15 , 17 } ] = [ 10.0.0.0/8{ 15 , 17 } ];
- print "must be false: ", 1 != 1, " ", 1 = (0,1), " ", 1 = "a", " ", +empty+ = -empty-, " ", -empty- = --empty--, " ", --empty-- = +empty+ ,
- " ", [1,2] = [1,3], " ", [ 10.0.0.0/8{ 15 , 17 } ] = [ 11.0.0.0/8{ 15 , 17 } ];
+ return 0;
+}
- print " must be true: ", 1.2.0.0/16 ~ [ 1.0.0.0/8{ 15 , 17 } ];
- print " data types; must be true: ", 1.2.3.4 = 1.2.3.4, ",", 1 ~ [1,2,3], ",", 5 ~ [1..20], ",", 10 ~ is, ",", 2 ~ [ 1, 2, 3 ], ",", 5 ~ [ 4 .. 7 ], ",", 1.2.3.4 ~ [ 1.2.3.3..1.2.3.5 ], ",", 1.2.3.4 ~ 1.0.0.0/8, ",", 1.0.0.0/8 ~ 1.0.0.0/8, ",", 1.0.0.0/8 ~ [ 1.0.0.0/8+ ];
- print " must be true: ", true && true, ",", true || false, ",", ! false && ! false && true, ",", 1 < 2 && 1 != 3, ",", true && true && ! false, ",", true || 1+"a", ",", !(false && 1+"a");
+function fifteen()
+{
+ return 15;
+}
- print " must be true: ", defined(1), ",", defined(1.2.3.4), ",", 1 != 2, ",", 1 <= 2;
- print " data types: must be false: ", 1 ~ [ 2, 3, 4 ], ",", 5 ~ is, ",", 1.2.3.4 ~ [ 1.2.3.3, 1.2.3.5 ], ",", (1,2) > (2,2), ",", (1,1) > (1,1), ",", 1.0.0.0/9 ~ [ 1.0.0.0/8- ], ",", 1.2.0.0/17 ~ [ 1.0.0.0/8{ 15 , 16 } ], ",", true && false;
+function t_call_function()
+{
+ bt_assert(fifteen() = 15);
+ bt_assert(callme(1, 2) = 42);
+ bt_assert(callme(42, 2) = 42);
- print " must be true: ", 1 ~ is1, " ", 3 ~ is1, " ", 5 ~ is1;
- print " must be true: ", (one+2) ~ is1, " ", 2 ~ is2, " ", 2 ~ is3;
- print " must be false: ", 4 ~ is1, " ", 4 ~ is2, " ", 4 ~ is3;
- print " must be false: ", 10 ~ is1, " ", 10 ~ is2, " ", 10 ~ is3;
- print " must be true: ", 15 ~ is1, " ", 15 ~ is2, " ", 15 ~ is3;
- print " must be false: ", 18 ~ is1, " ", 18 ~ is2, " ", 18 ~ is3;
- print " must be true: ", 19 ~ is1, " ", 19 ~ is2, " ", 19 ~ is3;
- print " must be false: ", 20 ~ is1, " ", 20 ~ is2, " ", 20 ~ is3;
+ bt_assert(callme(2, 2) = 4);
+ bt_assert(callme(3, 2) = 6);
+ bt_assert(callme(4, 4) = 16);
+ bt_assert(callme(7, 2) = 14);
+}
- px = 1.2.0.0/18;
- print "Testing prefixes: 1.2.0.0/18 = ", px;
- print " must be true: ", 192.168.0.0/16 ~ 192.168.0.0/16, " ", 192.168.0.0/17 ~ 192.168.0.0/16, " ", 192.168.254.0/24 ~ 192.168.0.0/16;
- print " must be false: ", 192.168.0.0/15 ~ 192.168.0.0/16, " ", 192.160.0.0/17 ~ 192.168.0.0/16;
+bt_test_suite(t_call_function, "Testing calling functions");
- p = 127.1.2.3;
- print "Testing mask : 127.0.0.0 = ", p.mask(8);
-
- pp = (1, 2);
- print "Testing pairs: (1,2) = ", (1,2), " = ", pp, " = ", (1,1+1), " = ", 'mkpair-a'(2);
- print " must be true: ", (1,2) = (1,1+1);
- print "Testing enums: ", RTS_DUMMY, " ", RTS_STATIC, " ",
- ", true: ", RTS_STATIC ~ [RTS_STATIC, RTS_DEVICE],
- ", false: ", RTS_BGP ~ [RTS_STATIC, RTS_DEVICE];
- ps = [(1,(one+one)), (3,4)..(4,8), (5,*), (6,3..6)];
- print "Pair set: ", ps;
- print "Testing pair set, true: ", pp ~ ps, " ", (3,5) ~ ps, " ", (4,1) ~ ps, " ", (5,4) ~ ps, " ", (5,65535) ~ ps, " ", (6,4) ~ ps, " ", (3, 10000) ~ ps;
- print "Testing pair set, false: ", (3,3) ~ ps, " ", (4,9) ~ ps, " ", (4,65535) ~ ps, " ", (6,2) ~ ps, " ", (6,6+one) ~ ps, " ", ((one+6),2) ~ ps, " ", (1,1) ~ ps;
- ps = [(20..150, 200..300), (50100..50200, 1000..50000), (*, 5+5)];
- print "Pair set: .. too long ..";
- print "Testing pair set, true: ", (100,200) ~ ps, " ", (150,300) ~ ps, " ", (50180,1200) ~ ps, " ", (50110,49000) ~ ps, " ", (0,10) ~ ps, " ", (64000,10) ~ ps;
- print "Testing pair set, false: ", (20,199) ~ ps, " ", (151,250) ~ ps, " ", (50050,2000) ~ ps, " ", (50150,50050) ~ ps, " ", (10,9) ~ ps, " ", (65535,11) ~ ps ;
- qq = 1.2.3.4;
- print "Testinq quad: 1.2.3.4 = ", qq,
- ", true: ", qq = 1.2.3.4, " ", qq ~ [1.2.3.4, 5.6.7.8],
- ", false: ", qq = 4.3.2.1, " ", qq ~ [1.2.1.1, 1.2.3.5];
+/*
+ * Test including another config file
+ * ----------------------------------
+ */
- cc = (rt, 12345, 200000);
- print "Testing EC: (rt, 12345, 200000) = ", cc;
- print "Testing EC: (ro, 100000, 20000) = ", (ro, 100000, 20000);
- print "Testing EC: (rt, 10.20.30.40, 20000) = ", (rt, 10.20.30.40, 20000);
- print " true: ", cc = (rt, 12345, 200000), " ", cc < (rt, 12345, 200010),
- ", false: ", cc = (rt, 12346, 200000), " ", cc = (ro, 12345, 200000), " ", cc > (rt, 12345, 200010);
+function t_include()
+int i;
+{
+ i = 1;
+ include "test.conf.inc";
+ bt_assert(i = 42);
+}
- ecs = [(rt, ten, (one+onef(0))*10), (ro, 100000, 100..200), (rt, 12345, *)];
- print "EC set: ", ecs;
- print "EC set: ", ecs2;
- print "Testing EC set, true: ", (rt, 10, 20) ~ ecs, " ", (ro, 100000, 100) ~ ecs, " ", (ro, 100000, 200) ~ ecs,
- " ", (rt, 12345, 0) ~ ecs, " ", cc ~ ecs, " ", (rt, 12345, 4000000) ~ ecs;
- print "Testing EC set, false: ", (ro, 10, 20) ~ ecs, " ", (rt, 10, 21) ~ ecs, " ", (ro, 100000, 99) ~ ecs,
- " ", (ro, 12345, 10) ~ ecs, " ", (rt, 12346, 0) ~ ecs, " ", (ro, 0.1.134.160, 150) ~ ecs;
+bt_test_suite(t_include, "Testing including another config file");
- st = "Hello";
- print "Testing string: ", st, " true: ", st ~ "Hell*", " false: ", st ~ "ell*";
-
- b = true;
- print "Testing bool: ", b, ", ", !b;
- if ( b = true ) then print "Testing bool comparison b = true: ", b;
- else { print "*** FAIL: TRUE test failed" ; quitbird; }
-
- ips = [ 1.1.1.0 .. 1.1.1.255, ip1222];
- print "Testing IP sets: ";
- print ips;
- print " must be true: ", 1.1.1.0 ~ ips, ",", 1.1.1.100 ~ ips, ",", 1.2.2.2 ~ ips;
- print " must be false: ", 1.1.0.255 ~ ips, ",", 1.1.2.0 ~ ips, ",", 1.2.2.3 ~ ips, ",", 192.168.1.1 ~ ips;
-
- pxs = [ 1.2.0.0/16, 1.4.0.0/16+];
- print "Testing prefix sets: ";
- print pxs;
- print " must be true: ", 1.2.0.0/16 ~ pxs, ",", 1.4.0.0/16 ~ pxs, ",", 1.4.0.0/18 ~ pxs, ",", 1.4.0.0/32 ~ pxs;
- print " must be false: ", 1.1.0.0/16 ~ pxs, ",", 1.3.0.0/16 ~ pxs, ",", 1.2.0.0/15 ~ pxs, ",", 1.2.0.0/17 ~ pxs, ",",
- 1.2.0.0/32 ~ pxs, ",", 1.4.0.0/15 ~ pxs;
- test_pxset(pxs2);
- test_pxset([ 10.0.0.0/16{8,12}, 20.0.0.0/16{24,28} ]);
- print "What will this do? ", [ 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 5 ];
- print "Testing functions...";
- callme ( 1, 2 );
- callme ( 2, 2 );
- callme ( 2, 2 );
- callme ( 3, 2 );
- callme ( 4, 4 );
- callme ( 7, 2 );
+/*
+ * Test if-else statement
+ * ----------------------
+ */
+
+function t_if_else()
+int i;
+{
+ if true then
+ bt_assert(true);
- i = fifteen();
- print "Testing function calls: 15 = ", i;
+ if false then
+ bt_assert(false);
+ else if true then
+ bt_assert(true);
+ else
+ bt_assert(false);
+}
- path_test();
+bt_test_suite(t_if_else, "Testing if-else statement");
- print "1.2.3.4 = ", onetwo;
- i = 4200000000;
- print "4200000000 = ", i, " true: ", i = 4200000000, " ", i > 4100000000, " false: ", i > 4250000000;
- test_undef(2);
- test_undef(3);
- test_undef(2);
- print "Testing include";
- include "test.conf.inc";
+/*
+ * Unused functions -- testing only parsing
+ * ----------------------------------------
+ */
+
+function __test1()
+{
+ if source ~ [ RTS_BGP, RTS_STATIC ] then {
+# ospf_metric1 = 65535;
+# ospf_metric2 = 1000;
+ ospf_tag = 0x12345678;
+ accept;
+ }
+ reject;
+}
- print "done";
- quitbird;
-# print "*** FAIL: this is unreachable";
+function __test2()
+{
+ if source ~ [ RTS_BGP, RTS_STATIC ] then {
+# ospf_metric1 = 65535;
+# ospf_metric2 = 1000;
+ ospf_tag = 0x12345678;
+ accept;
+ }
+ reject;
}
-filter testf
-int j;
-{
+filter testf
+int j;
+{
print "Heya, filtering route to ", net.ip, " prefixlen ", net.len, " source ", source;
print "This route was from ", from;
j = 7;
j = 17;
if rip_metric > 15 then {
- reject "RIP Metric is more than infinity";
+ reject "RIP Metric is more than infinity";
}
rip_metric = 14;
unset(rip_metric);
-
+
accept "ok I take that";
}
-eval __startup();
+filter roa_filter
+{
+ if net ~ [ 10.0.0.0/8{16,24}, 2000::/3{16,96} ] then {
+ accept;
+ }
+ reject;
+}
+
+roa4 table r4;
+roa6 table r6;
+
+protocol static
+{
+ roa4 { table r4; import filter roa_filter; };
+ route 10.110.0.0/16 max 16 as 1000;
+ route 10.120.0.0/16 max 24 as 1000;
+ route 10.130.0.0/16 max 24 as 2000;
+ route 10.130.128.0/18 max 24 as 3000;
+}
+
+protocol static
+{
+ roa6 { table r6; import filter roa_filter; };
+ route 2001:0db8:85a3:8a2e::/64 max 96 as 1000;
+}
+
+function test_roa_check()
+prefix pfx;
+{
+ # cannot be tested in __startup(), sorry
+ bt_assert(roa_check(r4, 10.10.0.0/16, 1000) = ROA_UNKNOWN);
+ bt_assert(roa_check(r4, 10.0.0.0/8, 1000) = ROA_UNKNOWN);
+ bt_assert(roa_check(r4, 10.110.0.0/16, 1000) = ROA_VALID);
+ bt_assert(roa_check(r4, 10.110.0.0/16, 2000) = ROA_INVALID);
+ bt_assert(roa_check(r4, 10.110.32.0/20, 1000) = ROA_INVALID);
+ bt_assert(roa_check(r4, 10.120.32.0/20, 1000) = ROA_VALID);
+ bt_assert(roa_check(r4, 10.120.32.0/20, 2000) = ROA_INVALID);
+ bt_assert(roa_check(r4, 10.120.32.32/28, 1000) = ROA_INVALID);
+ bt_assert(roa_check(r4, 10.130.130.0/24, 1000) = ROA_INVALID);
+ bt_assert(roa_check(r4, 10.130.130.0/24, 2000) = ROA_VALID);
+ bt_assert(roa_check(r4, 10.130.30.0/24, 3000) = ROA_INVALID);
+ bt_assert(roa_check(r4, 10.130.130.0/24, 3000) = ROA_VALID);
+
+ bt_assert(roa_check(r6, 2001:0db8:85a3:8a2e:1234::/80, 1000) = ROA_VALID);
+ bt_assert(roa_check(r6, 2001:0db8:85a3:8a2e:1234::/97, 1000) = ROA_INVALID);
+ bt_assert(roa_check(r6, 2001:0db8:85a3:8a2e::/64, 1000) = ROA_VALID);
+ bt_assert(roa_check(r6, 2001:0db8:85a3::/48, 1000) = ROA_UNKNOWN);
+
+ bt_assert(roa_check(r4, 10.10.0.0/16, 1000) = ROA_UNKNOWN);
+ bt_assert(roa_check(r4, 10.0.0.0/8, 1000) = ROA_UNKNOWN);
+ bt_assert(roa_check(r4, 10.110.0.0/16, 1000) = ROA_VALID);
+ bt_assert(roa_check(r4, 10.110.0.0/16, 2000) = ROA_INVALID);
+ bt_assert(roa_check(r4, 10.110.32.0/20, 1000) = ROA_INVALID);
+ bt_assert(roa_check(r4, 10.120.32.0/20, 1000) = ROA_VALID);
+
+ bt_assert(roa_check(r6, 2001:0db8:85a3:8a2e:1234::/80, 1000) = ROA_VALID);
+ bt_assert(roa_check(r6, 2001:0db8:85a3:8a2e:1234::/97, 1000) = ROA_INVALID);
+ bt_assert(roa_check(r6, 2001:0db8:85a3:8a2e::/64, 1000) = ROA_VALID);
+ bt_assert(roa_check(r6, 2001:0db8:85a3::/48, 1000) = ROA_UNKNOWN);
+
+ bt_assert(roa_check(r4, 2001:0db8:85a3:8a2e:1234::/97, 1000) = ROA_UNKNOWN);
+ bt_assert(roa_check(r6, 2001:0db8:85a3:8a2e:1234::/97, 1000) = ROA_INVALID);
+
+ bt_assert(roa_check(r4, 2001:0db8:85a3:8a2e:1234::/80, 1000) = ROA_UNKNOWN);
+ bt_assert(roa_check(r6, 2001:0db8:85a3:8a2e:1234::/80, 1000) = ROA_VALID);
+ bt_assert(roa_check(r4, 2001:0db8:85a3::/48, 1000) = ROA_UNKNOWN);
+ bt_assert(roa_check(r6, 2001:0db8:85a3::/48, 1000) = ROA_UNKNOWN);
+
+ bt_assert(10.130.130.0/24 ~ 0.0.0.0/0);
+ bt_assert(2001:0db8:85a3:8a2e::/64 ~ ::/0);
+ bt_assert(10.130.130.0/24 !~ ::/0);
+ bt_assert(2001:0db8:85a3:8a2e::/64 !~ 0.0.0.0/0);
+
+ pfx = 12.13.0.0/16 max 24 as 1234;
+ bt_assert(pfx.len = 16);
+ bt_assert(pfx.maxlen = 24);
+ bt_assert(pfx.asn = 1234);
+
+ pfx = 1000::/8 max 32 as 1234;
+ bt_assert(pfx.len = 8);
+ bt_assert(pfx.maxlen = 32);
+ bt_assert(pfx.asn = 1234);
+}
+
+bt_test_suite(test_roa_check, "Testing ROA");
+
+/*
+ * Testing Mixed Net Types
+ * -----------------------
+ */
+
+function t_mixed_prefix()
+prefix set pxs;
+prefix set pxt;
+{
+ pxs = [ 98.45.0.0/16, 128.128.0.0/12+, 2200::/42-, ::ffff:d000:0/100{98,102}];
+ bt_assert(format(pxs) = "[::/0, ::/2{c000::}, 98.45.0.0/112{::0.1.0.0}, 128.128.0.0/108{::0.31.255.255}, 208.0.0.0/100{::124.0.0.0}, 2200::/42{ffff:ffff:ffc0::}]");
+ bt_assert(::fe00:0:0/88 !~ pxs);
+ bt_assert(::fffe:0:0/95 !~ pxs);
+ bt_assert(::ffff:d800:0/101 ~ pxs);
+ bt_assert(216.0.0.0/5 ~ pxs);
+ bt_assert(212.0.0.0/6 ~ pxs);
+ bt_assert(212.0.0.0/7 !~ pxs);
+ bt_assert(::ffff:8080:8080/121 ~ pxs);
+ bt_assert(::/0 ~ pxs);
+ bt_assert(0.0.0.0/0 !~ pxs);
+ bt_assert(128.135.64.17/32 ~ pxs);
+
+# pxt = [ 0:1:2 10.1.10.0/24, 0:5:10000 10.1.10.0/24 ];
+# print pxt;
+
+ bt_assert(format(NET_IP4) = "(enum 36)1"); ## if (net.type = NET_IP4) ...
+ bt_assert(format(NET_VPN6) = "(enum 36)4");
+ bt_assert(format(0:1:2) = "1:2");
+}
+
+bt_test_suite(t_mixed_prefix, "Testing mixed net types");
+
+
+filter vpn_filter
+{
+ bt_assert(format(net) = "0:1:2 10.1.10.0/24");
+ bt_assert(net.type = NET_VPN4);
+ bt_assert(net.type != NET_IP4);
+ bt_assert(net.type != NET_IP6);
+ bt_assert(net.rd = 0:1:2);
+
+ case (net.type) {
+ NET_IP4: print "IPV4";
+ NET_IP6: print "IPV6";
+ }
+
+ accept;
+}
+
+vpn4 table v4;
+vpn4 table v6;
+
+protocol static
+{
+ vpn4 { table v4; import filter vpn_filter; };
+ route 0:1:2 10.1.10.0/24 unreachable;
+}
diff --git a/filter/test.conf.inc b/filter/test.conf.inc
index 109a49c5..8ede2d18 100644
--- a/filter/test.conf.inc
+++ b/filter/test.conf.inc
@@ -1,5 +1,3 @@
-print "Entering include";
-print "Should be 2: ", 1+1;
-print "Leaving include";
-
+bt_assert(1+1 = 2);
+i = 42;
diff --git a/filter/test.conf2 b/filter/test.conf2
index 60bdd965..48515020 100644
--- a/filter/test.conf2
+++ b/filter/test.conf2
@@ -18,6 +18,7 @@ protocol direct {
protocol kernel {
disabled;
+ ipv4; # Must be specified at least one channel
# learn; # Learn all routes from the kernel
# scan time 10; # Scan kernel tables every 10 seconds
}
@@ -25,51 +26,57 @@ protocol kernel {
protocol static {
# disabled;
- import filter { print "ahoj";
- print source;
- if source = RTS_STATIC then {
- print "It is from static";
- }
- print from;
- from = 1.2.3.4;
- print from;
- print scope;
- scope = SCOPE_HOST;
- print scope;
- if !(scope ~ [ SCOPE_HOST, SCOPE_SITE ]) then {
- print "Failed in test";
- quitbird;
- }
-
- preference = 15;
- print preference;
- preference = 29;
- print preference;
- rip_metric = 1;
- print rip_metric;
- rip_metric = rip_metric + 5;
- print rip_metric;
- bgp_community = - empty - ;
- print "nazdar";
- bgp_community = add(bgp_community, (1,2));
- print "cau";
- bgp_community = add(bgp_community, (2,3));
- bgp_community.add((4,5));
- print "community = ", bgp_community;
- bgp_community.delete((2,3));
- print "community = ", bgp_community;
- bgp_community.empty;
- print "community = ", bgp_community;
- print "done";
- };
+ ipv4 {
+ export all;
+
+ import filter {
+ print "ahoj";
+ print source;
+ if source = RTS_STATIC then {
+ print "It is from static";
+ }
+ print from;
+ from = 1.2.3.4;
+ print from;
+ print scope;
+ scope = SCOPE_HOST;
+ print scope;
+ if !(scope ~ [ SCOPE_HOST, SCOPE_SITE ]) then {
+ print "Failed in test";
+ quitbird;
+ }
+
+ preference = 15;
+ print preference;
+ preference = 29;
+ print preference;
+ rip_metric = 1;
+ print rip_metric;
+ rip_metric = rip_metric + 5;
+ print rip_metric;
+ bgp_community = -empty-;
+ print "hi";
+ bgp_community = add(bgp_community, (1,2));
+ print "hello";
+ bgp_community = add(bgp_community, (2,3));
+ bgp_community.add((4,5));
+ print "community = ", bgp_community;
+ bgp_community.delete((2,3));
+ print "community = ", bgp_community;
+ bgp_community.empty;
+ print "community = ", bgp_community;
+ print "done";
+
+ accept;
+ };
+ };
route 0.0.0.0/0 via 195.113.31.113;
route 62.168.0.0/25 reject;
route 1.2.3.4/32 via 195.113.31.124;
-# route 10.0.0.0/8 reject;
-# route 10.1.1.0:255.255.255.0 via 62.168.0.3;
-# route 10.1.2.0:255.255.255.0 via 62.168.0.3;
-# route 10.1.3.0:255.255.255.0 via 62.168.0.4;
-# route 10.2.0.0/24 via "arc0";
- export all;
+ route 10.0.0.0/8 reject;
+ route 10.1.1.0/24 via 62.168.0.3;
+ route 10.1.2.0/24 via 62.168.0.3;
+ route 10.1.3.0/24 via 62.168.0.4;
+ route 10.2.0.0/24 via "arc0";
}
diff --git a/filter/test6.conf b/filter/test6.conf
deleted file mode 100644
index f25ffc47..00000000
--- a/filter/test6.conf
+++ /dev/null
@@ -1,182 +0,0 @@
-/*
- * This is an example configuration file.
- * FIXME: add all examples from docs here.
- */
-
-# Yet another comment
-
-router id 62.168.0.1;
-
-define xyzzy = (120+10);
-
-function callme(int arg1; int arg2)
-int local1;
-int local2;
-int i;
-{
- printn "Function callme called arguments ", arg1, " and ", arg2, ":" ;
- i = arg2;
-
- case arg1 {
- 2: print "dva"; print "jeste jednou dva";
- 3 .. 5: print "tri az pet";
- else: print "neco jineho";
- }
-}
-
-function fifteen()
-{
- print "fifteen called";
- return 15;
-}
-
-function paths()
-bgpmask pm1;
-bgpmask pm2;
-bgppath p2;
-clist l;
-{
- pm1 = / 4 3 2 1 /;
- pm2 = [= 4 3 2 1 =];
- print "Testing path masks: ", pm1, " ", pm2;
- p2 = prepend( + empty +, 1 );
- p2 = prepend( p2, 2 );
- p2 = prepend( p2, 3 );
- p2 = prepend( p2, 4 );
- print "Testing paths: ", p2;
- print "Should be true: ", p2 ~ pm1, " ", p2 ~ pm2;
- print "4 = ", p2.len;
- p2 = prepend( p2, 5 );
- print "Should be false: ", p2 ~ pm1, " ", p2 ~ pm2;
- print "Should be true: ", p2 ~ / ? 4 3 2 1 /, " ", p2, " ", / ? 4 3 2 1 /;
- print "Should be true: ", p2 ~ [= * 4 3 * 1 =], " ", p2, " ", [= * 4 3 * 1 =];
- print "5 = ", p2.len;
-
- pm1 = [= 1 2 * 3 4 5 =];
- p2 = prepend( + empty +, 5 );
- p2 = prepend( p2, 4 );
- p2 = prepend( p2, 3 );
- p2 = prepend( p2, 3 );
- p2 = prepend( p2, 2 );
- p2 = prepend( p2, 1 );
- print "Should be true: ", p2 ~ pm1, " ", p2, " ", pm1;
-
- l = - empty -;
- l = add( l, (1,2) );
- l = add( l, (2,3) );
- print "Community list (1,2) (2,3) ", l;
- print "Should be true: ", (2,3) ~ l;
- l = delete( l, (2,3) );
- print "Community list (1,2) ", l;
- print "Should be false: ", (2,3) ~ l;
-}
-
-function bla()
-{
- print "fifteen called";
- return 15;
-}
-
-define four=4;
-
-function test_pxset(prefix set pxs)
-{
- print " must be true: ", 1000::/8 ~ pxs, ",", 1000::/10 ~ pxs, ",", 1000::/12 ~ pxs, ",",
- 2000::/24 ~ pxs, ",", 2000:4000::/24 ~ pxs, ",", 2000::/26 ~ pxs, ",",
- 2000:8000::/26 ~ pxs, ",", 2000::/28 ~ pxs, ",", 2000:FFF0::/28 ~ pxs;
- print " must be false: ", 1000::/7 ~ pxs, ",", 1000::/13 ~ pxs, ",", 1000::/16 ~ pxs, ",",
- 2000::/16 ~ pxs, ",", 2000::/23 ~ pxs, ",", 2000::/29 ~ pxs, ",",
- 1100::/10 ~ pxs, ",", 2010::/26 ~ pxs;
-}
-
-function __startup()
-int i;
-bool b;
-prefix px;
-ip p;
-pair pp;
-int set is;
-prefix set pxs;
-string s;
-{
- print "Testing filter language:";
- i = four;
- i = 12*100 + 60/2 + i;
- i = ( i + 0 );
- print " arithmetics: 1234 = ", i;
- printn " if statements ";
- print "what happens here?";
- printn ".";
- if (i = 4) then { print "*** FAIL: if 0"; quitbird; } else printn ".";
-# if !(i = 3) then { print "*** FAIL: if 0"; quitbird; } else printn ".";
- if 1234 = i then printn "."; else { print "*** FAIL: if 1 else"; }
-# if 1 <= 1 then printn "."; else { print "*** FAIL: test 3"; }
- if 1234 < 1234 then { print "*** FAIL: test 4"; quitbird; } else print "ok";
- is = [ 2, 3, 4, 7..11 ];
- print " must be true: ", 1180::/16 ~ [ 1100::/8{ 15 , 17 } ];
- print " data types; must be true: ", 12::34 = 12::34, ",", 1 ~ [1,2,3], ",", 5 ~ [1..20], ",", 10 ~ is, ",", 2 ~ [ 1, 2, 3 ], ",", 5 ~ [ 4 .. 7 ], ",", 12::34 ~ [ 12::33..12::35 ], ",", 1020::34 ~ 1000::/8, ",", 1000::/8 ~ 1000::/8, ",", 1000::/8 ~ [ 1000::/8+ ];
- print " must be true: ", true && true, ",", true || false;
-
-# print " must be true: ", defined(1), ",", defined(1.2.3.4), ",", 1 != 2, ",", 1 <= 2;
- print " data types: must be false: ", 1 ~ [ 2, 3, 4 ], ",", 5 ~ is, ",", 12::34 ~ [ 12::33, 12::35 ], ",", (1,2) > (2,2), ",", (1,1) > (1,1), ",", 1000::/9 ~ [ 1000::/8- ], ",", 1000::/17 ~ [ 1000::/8{ 15 , 16 } ], ",", true && false;
-
- px = 1020::/18;
- print "Testing prefixes: 1020::/18 = ", px;
- p = 1234:5678::;
- print "Testing mask : 1200:: = ", p.mask(8);
-
- pp = (1, 2);
- print "Testing pairs: (1,2) = ", (1,2), " = ", pp;
- print "Testing enums: ", RTS_DUMMY, " ", RTS_STATIC;
-
- s = "Hello";
- print "Testing string: ", s, " true: ", s ~ "Hell*", " false: ", s ~ "ell*";
-
- b = true;
- print "Testing bool: ", b, ", ", !b;
-
- pxs = [ 1102::/16, 1104::/16+];
- print "Testing prefix sets: ";
- print pxs;
- print " must be true: ", 1102::/16 ~ pxs, ",", 1104::/16 ~ pxs, ",", 1104::/18 ~ pxs, ",", 1104::/32 ~ pxs;
- print " must be false: ", 1101::/16 ~ pxs, ",", 1103::/16 ~ pxs, ",", 1102::/15 ~ pxs, ",", 1102::/17 ~ pxs, ",",
- 1102::/32 ~ pxs, ",", 1104::/15 ~ pxs;
-
- test_pxset([ 1000::/16{8,12}, 2000::/16{24,28} ]);
- print "What will this do? ", [ 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 5 ];
-
- print "Testing functions...";
-# callme ( 1, 2 );
- callme ( 2, 2 );
- callme ( 2, 2 );
- callme ( 3, 2 );
- callme ( 4, 2 );
- callme ( 7, 2 );
-
- i = fifteen();
- print "Testing function calls: 15 = ", i;
-
- paths();
-
- print "done";
- quitbird;
-# print "*** FAIL: this is unreachable";
-}
-
-filter testf
-int j;
-{
- print "Heya, filtering route to ", net.ip, " prefixlen ", net.len, " source ", source;
- print "This route was from ", from;
- j = 7;
- j = 17;
- if rip_metric > 15 then {
- reject "RIP Metric is more than infinity";
- }
- rip_metric = 14;
- unset(rip_metric);
-
- accept "ok I take that";
-}
-
-eval __startup(); \ No newline at end of file
diff --git a/filter/tree_test.c b/filter/tree_test.c
new file mode 100644
index 00000000..5b22a9fe
--- /dev/null
+++ b/filter/tree_test.c
@@ -0,0 +1,304 @@
+/*
+ * Filters: Utility Functions Tests
+ *
+ * (c) 2015 CZ.NIC z.s.p.o.
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "test/birdtest.h"
+#include "test/bt-utils.h"
+
+#include "filter/filter.h"
+#include "conf/conf.h"
+
+#define MAX_TREE_HEIGHT 13
+
+static void
+start_conf_env(void)
+{
+ bt_bird_init();
+
+ pool *p = rp_new(&root_pool, "helper_pool");
+ linpool *l = lp_new_default(p);
+ cfg_mem = l;
+}
+
+static struct f_tree *
+new_tree(uint id)
+{
+ struct f_tree *tree = f_new_tree();
+ tree->from.type = tree->to.type = T_INT;
+ tree->from.val.i = tree->to.val.i = id;
+
+ return tree;
+}
+
+/*
+ * Show subtree in infix notation
+ */
+static void
+show_subtree(struct f_tree *node)
+{
+ if (!node)
+ return;
+
+ show_subtree(node->left);
+
+ if (node->from.val.i == node->to.val.i)
+ bt_debug("%u ", node->from.val.i);
+ else
+ bt_debug("%u..%u ", node->from.val.i, node->to.val.i);
+
+ show_subtree(node->right);
+}
+
+static void
+show_tree2(struct f_tree *root_node, const char *tree_name)
+{
+ bt_debug("%s: \n", tree_name);
+ bt_debug("[ ");
+ show_subtree(root_node);
+ bt_debug("]\n\n");
+}
+
+#define show_tree(tree) show_tree2(tree, #tree);
+
+static uint
+get_nodes_count_full_bin_tree(uint height)
+{
+ return (bt_naive_pow(2, height+1) - 1);
+}
+
+static struct f_tree *
+get_balanced_full_subtree(uint height, uint idx)
+{
+ struct f_tree *node = new_tree(idx);
+ if (height > 0)
+ {
+ uint nodes_in_subtree = get_nodes_count_full_bin_tree(--height);
+ node->left = get_balanced_full_subtree(height, idx - nodes_in_subtree/2 - 1);
+ node->right = get_balanced_full_subtree(height, idx + nodes_in_subtree/2 + 1);
+ }
+ return node;
+}
+
+static struct f_tree *
+get_balanced_full_tree(uint height)
+{
+ return get_balanced_full_subtree(height, get_nodes_count_full_bin_tree(height)/2);
+}
+
+static struct f_tree *
+get_degenerated_left_tree(uint nodes_count)
+{
+ struct f_tree *old = NULL;
+ struct f_tree *new = NULL;
+ uint i;
+
+ for (i = 0; i < nodes_count; i++)
+ {
+ old = new;
+ new = new_tree(nodes_count-1-i);
+ new->left = old;
+ }
+
+ return new;
+}
+
+static struct f_tree *
+get_random_degenerated_left_tree(uint nodes_count)
+{
+ struct f_tree *tree = get_degenerated_left_tree(nodes_count);
+
+ size_t avaible_indexes_size = nodes_count * sizeof(byte);
+ byte *avaible_indexes = malloc(avaible_indexes_size);
+ memset(avaible_indexes, 0, avaible_indexes_size);
+
+ struct f_tree *n;
+ for (n = tree; n; n = n->left)
+ {
+ uint selected_idx;
+ do
+ {
+ selected_idx = bt_random() % nodes_count;
+ } while(avaible_indexes[selected_idx] != 0);
+
+ avaible_indexes[selected_idx] = 1;
+ n->from.type = n->to.type = T_INT;
+ n->from.val.i = n->to.val.i = selected_idx;
+ }
+
+ free(avaible_indexes);
+ return tree;
+}
+
+static struct f_tree *
+get_balanced_tree_with_ranged_values(uint nodes_count)
+{
+ struct f_tree *tree = get_degenerated_left_tree(nodes_count);
+
+ uint idx = 0;
+ struct f_tree *n;
+ for (n = tree; n; n = n->left)
+ {
+ n->from.type = n->to.type = T_INT;
+ n->from.val.i = idx;
+ idx += (uint)bt_random() / nodes_count; /* (... / nodes_count) preventing overflow an uint idx */
+ n->to.val.i = idx++;
+ }
+
+ return build_tree(tree);
+}
+
+
+static int
+t_balancing(void)
+{
+ start_conf_env();
+
+ uint height;
+ for (height = 1; height < MAX_TREE_HEIGHT; height++)
+ {
+ uint nodes_count = get_nodes_count_full_bin_tree(height);
+
+ struct f_tree *simple_degenerated_tree = get_degenerated_left_tree(nodes_count);
+ show_tree(simple_degenerated_tree);
+
+ struct f_tree *expected_balanced_tree = get_balanced_full_tree(height);
+ show_tree(expected_balanced_tree);
+
+ struct f_tree *balanced_tree_from_simple = build_tree(simple_degenerated_tree);
+ show_tree(balanced_tree_from_simple);
+
+ bt_assert(same_tree(balanced_tree_from_simple, expected_balanced_tree));
+ }
+
+ return 1;
+}
+
+
+static int
+t_balancing_random(void)
+{
+ start_conf_env();
+
+ uint height;
+ for (height = 1; height < MAX_TREE_HEIGHT; height++)
+ {
+ uint nodes_count = get_nodes_count_full_bin_tree(height);
+
+ struct f_tree *expected_balanced_tree = get_balanced_full_tree(height);
+
+ uint i;
+ for(i = 0; i < 10; i++)
+ {
+ struct f_tree *random_degenerated_tree = get_random_degenerated_left_tree(nodes_count);
+ show_tree(random_degenerated_tree);
+
+ struct f_tree *balanced_tree_from_random = build_tree(random_degenerated_tree);
+
+ show_tree(expected_balanced_tree);
+ show_tree(balanced_tree_from_random);
+
+ bt_assert(same_tree(balanced_tree_from_random, expected_balanced_tree));
+ }
+ }
+
+ return 1;
+}
+
+static int
+t_find(void)
+{
+ start_conf_env();
+
+ uint height;
+ for (height = 1; height < MAX_TREE_HEIGHT; height++)
+ {
+ uint nodes_count = get_nodes_count_full_bin_tree(height);
+
+ struct f_tree *tree = get_balanced_full_tree(height);
+ show_tree(tree);
+
+ struct f_val looking_up_value = {
+ .type = T_INT
+ };
+ for(looking_up_value.val.i = 0; looking_up_value.val.i < nodes_count; looking_up_value.val.i++)
+ {
+ struct f_tree *found_tree = find_tree(tree, looking_up_value);
+ bt_assert((val_compare(looking_up_value, found_tree->from) == 0) && (val_compare(looking_up_value, found_tree->to) == 0));
+ }
+ }
+
+ return 1;
+}
+
+static uint
+get_max_value_in_unbalanced_tree(struct f_tree *node, uint max)
+{
+ if (!node)
+ return max;
+
+ if (node->to.val.i > max)
+ max = node->to.val.i;
+
+ uint max_left = get_max_value_in_unbalanced_tree(node->left, max);
+ if (max_left > max)
+ max = max_left;
+
+ uint max_right = get_max_value_in_unbalanced_tree(node->right, max);
+ if (max_right > max)
+ max = max_right;
+
+ return max;
+}
+
+static int
+t_find_ranges(void)
+{
+ start_conf_env();
+
+ uint height;
+ for (height = 1; height < MAX_TREE_HEIGHT; height++)
+ {
+ uint nodes_count = get_nodes_count_full_bin_tree(height);
+
+ struct f_tree *tree = get_balanced_tree_with_ranged_values(nodes_count);
+ uint max_value = get_max_value_in_unbalanced_tree(tree, 0);
+
+ show_tree(tree);
+
+ bt_debug("max_value: %u \n", max_value);
+
+ struct f_val needle = {
+ .type = T_INT
+ };
+ uint *i = &needle.val.i;
+
+ for(*i = 0; *i <= max_value; *i += (uint)bt_random()/nodes_count)
+ {
+ struct f_tree *found_tree = find_tree(tree, needle);
+ bt_debug("searching: %u \n", *i);
+ bt_assert(
+ (val_compare(needle, found_tree->from) == 0) || (val_compare(needle, found_tree->to) == 0) ||
+ ((val_compare(needle, found_tree->from) == 1) && (val_compare(needle, found_tree->to) == -1))
+ );
+ }
+ }
+
+ return 1;
+}
+
+int
+main(int argc, char *argv[])
+{
+ bt_init(argc, argv);
+
+ bt_test_suite(t_balancing, "Balancing strong unbalanced trees");
+ bt_test_suite(t_balancing_random, "Balancing random unbalanced trees");
+ bt_test_suite(t_find, "Finding values in trees");
+ bt_test_suite(t_find_ranges, "Finding values in trees with random ranged values");
+
+ return bt_exit_value();
+}
diff --git a/filter/trie.c b/filter/trie.c
index 565ae82f..adcfcdf3 100644
--- a/filter/trie.c
+++ b/filter/trie.c
@@ -74,6 +74,19 @@
#include "conf/conf.h"
#include "filter/filter.h"
+
+/*
+ * In the trie code, the prefix length is internally treated as for the whole
+ * ip_addr, regardless whether it contains an IPv4 or IPv6 address. Therefore,
+ * remaining definitions make sense.
+ */
+
+#define ipa_mkmask(x) ip6_mkmask(x)
+#define ipa_masklen(x) ip6_masklen(&x)
+#define ipa_pxlen(x,y) ip6_pxlen(x,y)
+#define ipa_getbit(x,n) ip6_getbit(x,n)
+
+
/**
* f_new_trie - allocates and returns a new empty trie
* @lp: linear pool to allocate items from
@@ -109,12 +122,11 @@ attach_node(struct f_trie_node *parent, struct f_trie_node *child)
/**
* trie_add_prefix
* @t: trie to add to
- * @px: prefix address
- * @plen: prefix length
+ * @net: IP network prefix
* @l: prefix lower bound
* @h: prefix upper bound
*
- * Adds prefix (prefix pattern) @px/@plen to trie @t. @l and @h are lower
+ * Adds prefix (prefix pattern) @n to trie @t. @l and @h are lower
* and upper bounds on accepted prefix lengths, both inclusive.
* 0 <= l, h <= 32 (128 for IPv6).
*
@@ -124,8 +136,19 @@ attach_node(struct f_trie_node *parent, struct f_trie_node *child)
*/
void *
-trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
+trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
{
+ ip_addr px = net_prefix(net);
+ uint plen = net_pxlen(net);
+
+ if (net->type == NET_IP4)
+ {
+ const uint delta = IP6_MAX_PREFIX_LENGTH - IP4_MAX_PREFIX_LENGTH;
+ plen += delta;
+ l += delta;
+ h += delta;
+ }
+
if (l == 0)
t->zero = 1;
else
@@ -140,7 +163,7 @@ trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
struct f_trie_node *o = NULL;
struct f_trie_node *n = t->root;
- while(n)
+ while (n)
{
ip_addr cmask = ipa_and(n->mask, pmask);
@@ -196,18 +219,8 @@ trie_add_prefix(struct f_trie *t, ip_addr px, int plen, int l, int h)
return a;
}
-/**
- * trie_match_prefix
- * @t: trie
- * @px: prefix address
- * @plen: prefix length
- *
- * Tries to find a matching prefix pattern in the trie such that
- * prefix @px/@plen matches that prefix pattern. Returns 1 if there
- * is such prefix pattern in the trie.
- */
-int
-trie_match_prefix(struct f_trie *t, ip_addr px, int plen)
+static int
+trie_match_prefix(struct f_trie *t, ip_addr px, uint plen)
{
ip_addr pmask = ipa_mkmask(plen);
ip_addr paddr = ipa_and(px, pmask);
@@ -241,6 +254,30 @@ trie_match_prefix(struct f_trie *t, ip_addr px, int plen)
return 0;
}
+/**
+ * trie_match_net
+ * @t: trie
+ * @n: net address
+ *
+ * Tries to find a matching net in the trie such that
+ * prefix @n matches that prefix pattern. Returns 1 if there
+ * is such prefix pattern in the trie.
+ */
+int
+trie_match_net(struct f_trie *t, const net_addr *n)
+{
+ uint add = 0;
+
+ switch (n->type) {
+ case NET_IP4:
+ case NET_VPN4:
+ case NET_ROA4:
+ add = IP6_MAX_PREFIX_LENGTH - IP4_MAX_PREFIX_LENGTH;
+ }
+
+ return trie_match_prefix(t, net_prefix(n), net_pxlen(n) + add);
+}
+
static int
trie_node_same(struct f_trie_node *t1, struct f_trie_node *t2)
{
diff --git a/filter/trie_test.c b/filter/trie_test.c
new file mode 100644
index 00000000..7529a5c5
--- /dev/null
+++ b/filter/trie_test.c
@@ -0,0 +1,185 @@
+/*
+ * Filters: Utility Functions Tests
+ *
+ * (c) 2015 CZ.NIC z.s.p.o.
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "test/birdtest.h"
+#include "test/bt-utils.h"
+
+#include "filter/filter.h"
+#include "conf/conf.h"
+
+#define TESTS_NUM 10
+#define PREFIXES_NUM 10
+#define PREFIX_TESTS_NUM 10000
+
+#define BIG_BUFFER_SIZE 10000
+
+/* Wrapping structure for storing f_prefixes structures in list */
+struct f_prefix_node {
+ node n;
+ struct f_prefix prefix;
+};
+
+static u32
+xrandom(u32 max)
+{
+ return (bt_random() % max);
+}
+
+static int
+is_prefix_included(list *prefixes, struct f_prefix *needle)
+{
+ struct f_prefix_node *n;
+ WALK_LIST(n, *prefixes)
+ {
+ ip6_addr cmask = ip6_mkmask(MIN(n->prefix.net.pxlen, needle->net.pxlen));
+
+ ip6_addr ip = net6_prefix(&n->prefix.net);
+ ip6_addr needle_ip = net6_prefix(&needle->net);
+
+ if ((ipa_compare(ipa_and(ip, cmask), ipa_and(needle_ip, cmask)) == 0) &&
+ (n->prefix.lo <= needle->net.pxlen) && (needle->net.pxlen <= n->prefix.hi))
+ {
+ bt_debug("FOUND\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&n->prefix.net)), n->prefix.net.pxlen, n->prefix.lo, n->prefix.hi);
+ return 1; /* OK */
+ }
+ }
+ return 0; /* FAIL */
+}
+
+static struct f_prefix
+get_random_ip6_prefix(void)
+{
+ struct f_prefix p;
+ u8 pxlen = xrandom(120)+8;
+ ip6_addr ip6 = ip6_build(bt_random(),bt_random(),bt_random(),bt_random());
+ net_addr_ip6 net6 = NET_ADDR_IP6(ip6, pxlen);
+
+ p.net = *((net_addr*) &net6);
+
+ if (bt_random() % 2)
+ {
+ p.lo = 0;
+ p.hi = p.net.pxlen;
+ }
+ else
+ {
+ p.lo = p.net.pxlen;
+ p.hi = net_max_prefix_length[p.net.type];
+ }
+
+ return p;
+}
+
+static void
+generate_random_ipv6_prefixes(list *prefixes)
+{
+ int i;
+ for (i = 0; i < PREFIXES_NUM; i++)
+ {
+ struct f_prefix f = get_random_ip6_prefix();
+
+ struct f_prefix_node *px = calloc(1, sizeof(struct f_prefix_node));
+ px->prefix = f;
+
+ bt_debug("ADD\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&px->prefix.net)), px->prefix.net.pxlen, px->prefix.lo, px->prefix.hi);
+ add_tail(prefixes, &px->n);
+ }
+}
+
+static int
+t_match_net(void)
+{
+ bt_bird_init();
+ bt_config_parse(BT_CONFIG_SIMPLE);
+
+ uint round;
+ for (round = 0; round < TESTS_NUM; round++)
+ {
+ list prefixes; /* of structs f_extended_prefix */
+ init_list(&prefixes);
+ struct f_trie *trie = f_new_trie(config->mem, sizeof(struct f_trie_node));
+
+ generate_random_ipv6_prefixes(&prefixes);
+ struct f_prefix_node *n;
+ WALK_LIST(n, prefixes)
+ {
+ trie_add_prefix(trie, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+ }
+
+ int i;
+ for (i = 0; i < PREFIX_TESTS_NUM; i++)
+ {
+ struct f_prefix f = get_random_ip6_prefix();
+ bt_debug("TEST\t" PRIip6 "/%d\n", ARGip6(net6_prefix(&f.net)), f.net.pxlen);
+
+ int should_be = is_prefix_included(&prefixes, &f);
+ int is_there = trie_match_net(trie, &f.net);
+ bt_assert_msg(should_be == is_there, "Prefix " PRIip6 "/%d %s", ARGip6(net6_prefix(&f.net)), f.net.pxlen, (should_be ? "should be found in trie" : "should not be found in trie"));
+ }
+
+ struct f_prefix_node *nxt;
+ WALK_LIST_DELSAFE(n, nxt, prefixes)
+ {
+ free(n);
+ }
+ }
+
+ bt_bird_cleanup();
+ return 1;
+}
+
+static int
+t_trie_same(void)
+{
+ bt_bird_init();
+ bt_config_parse(BT_CONFIG_SIMPLE);
+
+ int round;
+ for (round = 0; round < TESTS_NUM*4; round++)
+ {
+ struct f_trie * trie1 = f_new_trie(config->mem, sizeof(struct f_trie_node));
+ struct f_trie * trie2 = f_new_trie(config->mem, sizeof(struct f_trie_node));
+
+ list prefixes; /* a list of f_extended_prefix structures */
+ init_list(&prefixes);
+ int i;
+ for (i = 0; i < 100; i++)
+ generate_random_ipv6_prefixes(&prefixes);
+
+ struct f_prefix_node *n;
+ WALK_LIST(n, prefixes)
+ {
+ trie_add_prefix(trie1, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+ }
+ WALK_LIST_BACKWARDS(n, prefixes)
+ {
+ trie_add_prefix(trie2, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+ }
+
+ bt_assert(trie_same(trie1, trie2));
+
+ struct f_prefix_node *nxt;
+ WALK_LIST_DELSAFE(n, nxt, prefixes)
+ {
+ free(n);
+ }
+ }
+
+ return 1;
+}
+
+int
+main(int argc, char *argv[])
+{
+ bt_init(argc, argv);
+
+ bt_test_suite(t_match_net, "Testing random prefix matching");
+ bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward.");
+
+ return bt_exit_value();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-03-31 17:27:33 +0000