summaryrefslogtreecommitdiff
path: root/filter
diff options
context:
space:
mode:
Diffstat (limited to 'filter')
-rw-r--r--filter/config.Y160
-rw-r--r--filter/data.c116
-rw-r--r--filter/data.h192
-rw-r--r--filter/decl.m48
-rw-r--r--filter/f-inst.c479
-rw-r--r--filter/f-inst.h16
-rw-r--r--filter/f-util.c145
-rw-r--r--filter/filter.c67
-rw-r--r--filter/filter.h19
-rw-r--r--filter/filter_test.c4
-rw-r--r--filter/test.conf249
-rw-r--r--filter/test.conf26
-rw-r--r--filter/tree_test.c5
-rw-r--r--filter/trie.c951
-rw-r--r--filter/trie_test.c851
15 files changed, 2449 insertions, 819 deletions
diff --git a/filter/config.Y b/filter/config.Y
index 8034b790..ca792593 100644
--- a/filter/config.Y
+++ b/filter/config.Y
@@ -22,6 +22,13 @@ static inline u32 pair_b(u32 p) { return p & 0xFFFF; }
#define f_generate_complex(fi_code, da, arg) \
f_new_inst(FI_EA_SET, f_new_inst(fi_code, f_new_inst(FI_EA_GET, da), arg), da)
+#define f_generate_complex_sym(fi_code, sym, arg) ({ \
+ if (sym->class != SYM_ATTRIBUTE) \
+ cf_error("Can't empty %s: not an attribute", sym->name); \
+ f_generate_complex(fi_code, sym->attribute, arg); \
+})
+
+
/*
* Sets and their items are during parsing handled as lists, linked
* through left ptr. The first item in a list also contains a pointer
@@ -161,28 +168,32 @@ f_new_lc_item(u32 f1, u32 t1, u32 f2, u32 t2, u32 f3, u32 t3)
}
static inline struct f_inst *
-f_generate_empty(struct f_dynamic_attr dyn)
+f_generate_empty(const struct symbol *sym)
{
- struct f_val empty;
+ if (sym->class != SYM_ATTRIBUTE)
+ cf_error("Can't empty %s: not an attribute", sym->name);
- switch (dyn.type & EAF_TYPE_MASK) {
- case EAF_TYPE_AS_PATH:
- empty = f_const_empty_path;
- break;
- case EAF_TYPE_INT_SET:
- empty = f_const_empty_clist;
- break;
- case EAF_TYPE_EC_SET:
- empty = f_const_empty_eclist;
- break;
- case EAF_TYPE_LC_SET:
- empty = f_const_empty_lclist;
- break;
- default:
- cf_error("Can't empty that attribute");
- }
+ const struct ea_class *def = sym->attribute;
+ const struct f_val *empty = f_get_empty(def->type);
+ if (!empty)
+ cf_error("Can't empty attribute %s", def->name);
- return f_new_inst(FI_EA_SET, f_new_inst(FI_CONSTANT, empty), dyn);
+ return f_new_inst(FI_EA_SET, f_new_inst(FI_CONSTANT, *empty), def);
+}
+
+static inline struct f_inst *
+f_implicit_roa_check(struct rtable_config *tab)
+{
+ const struct ea_class *def = ea_class_find("bgp_path");
+ if (!def)
+ cf_error("Fatal: Couldn't find BGP path attribute definition.");
+
+ struct f_static_attr fsa = f_new_static_attr(T_NET, SA_NET, 1);
+
+ return f_new_inst(FI_ROA_CHECK,
+ f_new_inst(FI_RTA_GET, fsa),
+ f_new_inst(FI_AS_PATH_LAST, f_new_inst(FI_EA_GET, def)),
+ tab);
}
/*
@@ -274,14 +285,15 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
SET, STRING, BGPMASK, BGPPATH, CLIST, ECLIST, LCLIST,
IF, THEN, ELSE, CASE,
TRUE, FALSE, RT, RO, UNKNOWN, GENERIC,
- FROM, GW, NET, MASK, PROTO, SOURCE, SCOPE, DEST, IFNAME, IFINDEX, WEIGHT, GW_MPLS,
- PREFERENCE,
+ FROM, GW, NET, MASK, PROTO, SCOPE, DEST, IFNAME, IFINDEX, WEIGHT, GW_MPLS,
ROA_CHECK, ASN, SRC, DST,
IS_V4, IS_V6,
LEN, MAXLEN,
+ DATA, DATA1, DATA2,
DEFINED,
- ADD, DELETE, CONTAINS, RESET,
- PREPEND, FIRST, LAST, LAST_NONAGGREGATED, MATCH,
+ ADD, DELETE, RESET,
+ PREPEND, FIRST, LAST, LAST_NONAGGREGATED,
+ MIN, MAX,
EMPTY,
FILTER, WHERE, EVAL, ATTRIBUTE,
BT_ASSERT, BT_TEST_SUITE, BT_CHECK_ASSIGN, BT_TEST_SAME, FORMAT, STACKS)
@@ -291,8 +303,8 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN,
%type <xp> cmds_int cmd_prep
%type <x> term block cmd cmds constant constructor print_list var_list function_call symbol_value bgp_path_expr bgp_path bgp_path_tail
-%type <fda> dynamic_attr
%type <fsa> static_attr
+%type <fab> attr_bit
%type <f> filter where_filter
%type <fl> filter_body function_body
%type <flv> lvalue
@@ -333,12 +345,19 @@ filter_eval:
conf: custom_attr ;
custom_attr: ATTRIBUTE type symbol ';' {
- cf_define_symbol($3, SYM_ATTRIBUTE, attribute, ca_lookup(new_config->pool, $3->name, $2)->fda);
+ if (($3->class == SYM_ATTRIBUTE) && ($3->scope == new_config->root_scope))
+ cf_error("Duplicate attribute %s definition", $3->name);
+
+ cf_define_symbol($3, SYM_ATTRIBUTE, attribute,
+ ea_register_alloc(new_config->pool, (struct ea_class) {
+ .name = $3->name,
+ .type = $2,
+ })->class);
};
conf: bt_test_suite ;
bt_test_suite:
- BT_TEST_SUITE '(' CF_SYM_KNOWN ',' text ')' {
+ BT_TEST_SUITE '(' symbol_known ',' text ')' {
cf_assert_symbol($3, SYM_FUNCTION);
struct f_bt_test_suite *t = cfg_allocz(sizeof(struct f_bt_test_suite));
t->fn = $3->function;
@@ -351,7 +370,7 @@ bt_test_suite:
conf: bt_test_same ;
bt_test_same:
- BT_TEST_SAME '(' CF_SYM_KNOWN ',' CF_SYM_KNOWN ',' NUM ')' {
+ BT_TEST_SAME '(' symbol_known ',' symbol_known ',' NUM ')' {
cf_assert_symbol($3, SYM_FUNCTION);
cf_assert_symbol($5, SYM_FUNCTION);
struct f_bt_test_suite *t = cfg_allocz(sizeof(struct f_bt_test_suite));
@@ -429,7 +448,7 @@ function_vars:
filter_body: function_body ;
filter:
- CF_SYM_KNOWN {
+ symbol_known {
cf_assert_symbol($1, SYM_FILTER);
$$ = $1->filter;
}
@@ -527,10 +546,10 @@ set_atom:
| VPN_RD { $$.type = T_RD; $$.val.ec = $1; }
| ENUM { $$.type = pair_a($1); $$.val.i = pair_b($1); }
| '(' term ')' {
- if (f_eval(f_linearize($2), cfg_mem, &($$)) > F_RETURN) cf_error("Runtime error");
+ if (f_eval(f_linearize($2), &($$)) > F_RETURN) cf_error("Runtime error");
if (!f_valid_set_type($$.type)) cf_error("Set-incompatible type");
}
- | CF_SYM_KNOWN {
+ | symbol_known {
cf_assert_symbol($1, SYM_CONSTANT);
if (!f_valid_set_type(SYM_TYPE($1))) cf_error("%s: set-incompatible type", $1->name);
$$ = *$1->val;
@@ -700,7 +719,7 @@ var_list: /* EMPTY */ { $$ = NULL; }
| var_list ',' term { $$ = $3; $$->next = $1; }
function_call:
- CF_SYM_KNOWN '(' var_list ')' {
+ symbol_known '(' var_list ')' {
if ($1->class != SYM_FUNCTION)
cf_error("You can't call something which is not a function. Really.");
@@ -724,7 +743,7 @@ function_call:
}
;
-symbol_value: CF_SYM_KNOWN
+symbol_value: symbol_known
{
switch ($1->class) {
case SYM_CONSTANT_RANGE:
@@ -734,7 +753,7 @@ symbol_value: CF_SYM_KNOWN
$$ = f_new_inst(FI_VAR_GET, $1);
break;
case SYM_ATTRIBUTE:
- $$ = f_new_inst(FI_EA_GET, *$1->attribute);
+ $$ = f_new_inst(FI_EA_GET, $1->attribute);
break;
default:
cf_error("Can't get value of symbol %s", $1->name);
@@ -743,17 +762,13 @@ symbol_value: CF_SYM_KNOWN
;
static_attr:
- FROM { $$ = f_new_static_attr(T_IP, SA_FROM, 0); }
- | GW { $$ = f_new_static_attr(T_IP, SA_GW, 0); }
+ GW { $$ = f_new_static_attr(T_IP, SA_GW, 0); }
| NET { $$ = f_new_static_attr(T_NET, SA_NET, 1); }
| PROTO { $$ = f_new_static_attr(T_STRING, SA_PROTO, 1); }
- | SOURCE { $$ = f_new_static_attr(T_ENUM_RTS, SA_SOURCE, 1); }
- | SCOPE { $$ = f_new_static_attr(T_ENUM_SCOPE, SA_SCOPE, 0); }
| DEST { $$ = f_new_static_attr(T_ENUM_RTD, SA_DEST, 0); }
| IFNAME { $$ = f_new_static_attr(T_STRING, SA_IFNAME, 0); }
| IFINDEX { $$ = f_new_static_attr(T_INT, SA_IFINDEX, 1); }
| WEIGHT { $$ = f_new_static_attr(T_INT, SA_WEIGHT, 0); }
- | PREFERENCE { $$ = f_new_static_attr(T_INT, SA_PREF, 0); }
| GW_MPLS { $$ = f_new_static_attr(T_INT, SA_GW_MPLS, 0); }
;
@@ -763,6 +778,8 @@ term:
| term '-' term { $$ = f_new_inst(FI_SUBTRACT, $1, $3); }
| term '*' term { $$ = f_new_inst(FI_MULTIPLY, $1, $3); }
| term '/' term { $$ = f_new_inst(FI_DIVIDE, $1, $3); }
+ | term '&' term { $$ = f_new_inst(FI_BITAND, $1, $3); }
+ | term '|' term { $$ = f_new_inst(FI_BITOR, $1, $3); }
| term AND term { $$ = f_new_inst(FI_AND, $1, $3); }
| term OR term { $$ = f_new_inst(FI_OR, $1, $3); }
| term '=' term { $$ = f_new_inst(FI_EQ, $1, $3); }
@@ -781,8 +798,10 @@ term:
| constructor { $$ = $1; }
| static_attr { $$ = f_new_inst(FI_RTA_GET, $1); }
-
- | dynamic_attr { $$ = f_new_inst(FI_EA_GET, $1); }
+ | attr_bit {
+ struct f_inst *c = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_INT, .val.i = (1U << $1.bit)});
+ $$ = f_new_inst(FI_EQ, c, f_new_inst(FI_BITAND, f_new_inst(FI_EA_GET, $1.class), c));
+ }
| term '.' IS_V4 { $$ = f_new_inst(FI_IS_V4, $1); }
| term '.' TYPE { $$ = f_new_inst(FI_TYPE, $1); }
@@ -790,13 +809,18 @@ term:
| term '.' RD { $$ = f_new_inst(FI_ROUTE_DISTINGUISHER, $1); }
| term '.' LEN { $$ = f_new_inst(FI_LENGTH, $1); }
| term '.' MAXLEN { $$ = f_new_inst(FI_ROA_MAXLEN, $1); }
- | term '.' ASN { $$ = f_new_inst(FI_ROA_ASN, $1); }
+ | term '.' ASN { $$ = f_new_inst(FI_ASN, $1); }
| term '.' SRC { $$ = f_new_inst(FI_NET_SRC, $1); }
| term '.' DST { $$ = f_new_inst(FI_NET_DST, $1); }
| term '.' MASK '(' term ')' { $$ = f_new_inst(FI_IP_MASK, $1, $5); }
| term '.' FIRST { $$ = f_new_inst(FI_AS_PATH_FIRST, $1); }
| term '.' LAST { $$ = f_new_inst(FI_AS_PATH_LAST, $1); }
| term '.' LAST_NONAGGREGATED { $$ = f_new_inst(FI_AS_PATH_LAST_NAG, $1); }
+ | term '.' DATA { $$ = f_new_inst(FI_PAIR_DATA, $1); }
+ | term '.' DATA1 { $$ = f_new_inst(FI_LC_DATA1, $1); }
+ | term '.' DATA2 { $$ = f_new_inst(FI_LC_DATA2, $1); }
+ | term '.' MIN { $$ = f_new_inst(FI_MIN, $1); }
+ | term '.' MAX { $$ = f_new_inst(FI_MAX, $1); }
/* Communities */
/* This causes one shift/reduce conflict
@@ -815,13 +839,11 @@ term:
| DELETE '(' term ',' term ')' { $$ = f_new_inst(FI_CLIST_DEL, $3, $5); }
| FILTER '(' term ',' term ')' { $$ = f_new_inst(FI_CLIST_FILTER, $3, $5); }
- | ROA_CHECK '(' rtable ')' { $$ = f_new_inst(FI_ROA_CHECK_IMPLICIT, $3); }
- | ROA_CHECK '(' rtable ',' term ',' term ')' { $$ = f_new_inst(FI_ROA_CHECK_EXPLICIT, $5, $7, $3); }
+ | ROA_CHECK '(' rtable ')' { $$ = f_implicit_roa_check($3); }
+ | ROA_CHECK '(' rtable ',' term ',' term ')' { $$ = f_new_inst(FI_ROA_CHECK, $5, $7, $3); }
| FORMAT '(' term ')' { $$ = f_new_inst(FI_FORMAT, $3); }
-/* | term '.' LEN { $$->code = P('P','l'); } */
-
| function_call
;
@@ -848,13 +870,15 @@ cmd:
| IF term THEN block ELSE block {
$$ = f_new_inst(FI_CONDITION, $2, $4, $6);
}
- | CF_SYM_KNOWN '=' term ';' {
+ | symbol_known '=' term ';' {
switch ($1->class) {
case SYM_VARIABLE_RANGE:
$$ = f_new_inst(FI_VAR_SET, $3, $1);
break;
case SYM_ATTRIBUTE:
- $$ = f_new_inst(FI_EA_SET, $3, *$1->attribute);
+ if ($1->attribute->readonly)
+ cf_error("Attribute %s is read-only", $1->attribute->name);
+ $$ = f_new_inst(FI_EA_SET, $3, $1->attribute);
break;
default:
cf_error("Can't assign to symbol %s", $1->name);
@@ -864,16 +888,25 @@ cmd:
DBG( "Ook, we'll return the value\n" );
$$ = f_new_inst(FI_RETURN, $2);
}
- | dynamic_attr '=' term ';' {
- $$ = f_new_inst(FI_EA_SET, $3, $1);
- }
| static_attr '=' term ';' {
if ($1.readonly)
cf_error( "This static attribute is read-only.");
$$ = f_new_inst(FI_RTA_SET, $3, $1);
}
- | UNSET '(' dynamic_attr ')' ';' {
- $$ = f_new_inst(FI_EA_UNSET, $3);
+ | UNSET '(' symbol_known ')' ';' {
+ if ($3->class != SYM_ATTRIBUTE)
+ cf_error("Can't unset %s", $3->name);
+ if ($3->attribute->readonly)
+ cf_error("Attribute %s is read-only", $3->attribute->name);
+ $$ = f_new_inst(FI_EA_UNSET, $3->attribute);
+ }
+ | attr_bit '=' term ';' {
+ $$ = f_new_inst(FI_CONDITION, $3,
+ f_generate_complex(FI_BITOR, $1.class,
+ f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_INT, .val.i = (1U << $1.bit)})),
+ f_generate_complex(FI_BITAND, $1.class,
+ f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_INT, .val.i = ~(1U << $1.bit)}))
+ );
}
| break_command print_list ';' {
struct f_inst *breaker = f_new_inst(FI_DIE, $1);
@@ -898,11 +931,11 @@ cmd:
$$ = f_new_inst(FI_SWITCH, $2, build_tree($4));
}
- | dynamic_attr '.' EMPTY ';' { $$ = f_generate_empty($1); }
- | dynamic_attr '.' PREPEND '(' term ')' ';' { $$ = f_generate_complex( FI_PATH_PREPEND, $1, $5 ); }
- | dynamic_attr '.' ADD '(' term ')' ';' { $$ = f_generate_complex( FI_CLIST_ADD, $1, $5 ); }
- | dynamic_attr '.' DELETE '(' term ')' ';' { $$ = f_generate_complex( FI_CLIST_DEL, $1, $5 ); }
- | dynamic_attr '.' FILTER '(' term ')' ';' { $$ = f_generate_complex( FI_CLIST_FILTER, $1, $5 ); }
+ | symbol_known '.' EMPTY ';' { $$ = f_generate_empty($1); }
+ | symbol_known '.' PREPEND '(' term ')' ';' { $$ = f_generate_complex_sym( FI_PATH_PREPEND, $1, $5 ); }
+ | symbol_known '.' ADD '(' term ')' ';' { $$ = f_generate_complex_sym( FI_CLIST_ADD, $1, $5 ); }
+ | symbol_known '.' DELETE '(' term ')' ';' { $$ = f_generate_complex_sym( FI_CLIST_DEL, $1, $5 ); }
+ | symbol_known '.' FILTER '(' term ')' ';' { $$ = f_generate_complex_sym( FI_CLIST_FILTER, $1, $5 ); }
| BT_ASSERT '(' get_cf_position term get_cf_position ')' ';' { $$ = assert_done($4, $3 + 1, $5 - 1); }
| BT_CHECK_ASSIGN '(' get_cf_position lvalue get_cf_position ',' term ')' ';' { $$ = assert_assign(&$4, $7, $3 + 1, $5 - 1); }
;
@@ -913,8 +946,17 @@ get_cf_position:
};
lvalue:
- CF_SYM_KNOWN { cf_assert_symbol($1, SYM_VARIABLE); $$ = (struct f_lval) { .type = F_LVAL_VARIABLE, .sym = $1 }; }
+ symbol_known {
+ switch ($1->class) {
+ case SYM_VARIABLE_RANGE:
+ $$ = (struct f_lval) { .type = F_LVAL_VARIABLE, .sym = $1 };
+ break;
+ case SYM_ATTRIBUTE:
+ $$ = (struct f_lval) { .type = F_LVAL_EA, .da = $1->attribute };
+ break;
+ }
+ }
| static_attr { $$ = (struct f_lval) { .type = F_LVAL_SA, .sa = $1 }; }
- | dynamic_attr { $$ = (struct f_lval) { .type = F_LVAL_EA, .da = $1 }; };
+ ;
CF_END
diff --git a/filter/data.c b/filter/data.c
index 7c33d2cb..9dab1915 100644
--- a/filter/data.c
+++ b/filter/data.c
@@ -16,10 +16,10 @@
#include "lib/unaligned.h"
#include "lib/net.h"
#include "lib/ip.h"
-#include "nest/route.h"
+#include "nest/rt.h"
#include "nest/protocol.h"
#include "nest/iface.h"
-#include "nest/attrs.h"
+#include "lib/attrs.h"
#include "conf/conf.h"
#include "filter/filter.h"
#include "filter/f-inst.h"
@@ -27,6 +27,8 @@
static const char * const f_type_str[] = {
[T_VOID] = "void",
+ [T_OPAQUE] = "opaque byte string",
+ [T_IFACE] = "interface",
[T_INT] = "int",
[T_BOOL] = "bool",
@@ -36,7 +38,6 @@ static const char * const f_type_str[] = {
[T_ENUM_RTS] = "enum rts",
[T_ENUM_BGP_ORIGIN] = "enum bgp_origin",
[T_ENUM_SCOPE] = "enum scope",
- [T_ENUM_RTC] = "enum rtc",
[T_ENUM_RTD] = "enum rtd",
[T_ENUM_ROA] = "enum roa",
[T_ENUM_NETTYPE] = "enum nettype",
@@ -47,6 +48,7 @@ static const char * const f_type_str[] = {
[T_NET] = "prefix",
[T_STRING] = "string",
[T_PATH_MASK] = "bgpmask",
+ [T_PATH_MASK_ITEM] = "bgpmask item",
[T_PATH] = "bgppath",
[T_CLIST] = "clist",
[T_EC] = "ec",
@@ -54,18 +56,26 @@ static const char * const f_type_str[] = {
[T_LC] = "lc",
[T_LCLIST] = "lclist",
[T_RD] = "rd",
+
+ [T_SET] = "set",
+ [T_PREFIX_SET] = "prefix set",
};
const char *
-f_type_name(enum f_type t)
+f_type_name(btype t)
{
- if (t < ARRAY_SIZE(f_type_str))
- return f_type_str[t] ?: "?";
-
- if ((t == T_SET) || (t == T_PREFIX_SET))
- return "set";
+ return (t < ARRAY_SIZE(f_type_str)) ? (f_type_str[t] ?: "?") : "?";
+}
- return "?";
+btype
+f_type_element_type(btype t)
+{
+ switch(t) {
+ case T_CLIST: return T_PAIR;
+ case T_ECLIST: return T_EC;
+ case T_LCLIST: return T_LC;
+ default: return T_VOID;
+ };
}
const struct f_val f_const_empty_path = {
@@ -82,14 +92,6 @@ const struct f_val f_const_empty_path = {
.val.ad = &null_adata,
};
-static struct adata *
-adata_empty(struct linpool *pool, int l)
-{
- struct adata *res = lp_alloc(pool, sizeof(struct adata) + l);
- res->length = l;
- return res;
-}
-
static void
pm_format(const struct f_path_mask *p, buffer *buf)
{
@@ -412,7 +414,7 @@ clist_filter(struct linpool *pool, const struct adata *list, const struct f_val
if (nl == list->length)
return list;
- struct adata *res = adata_empty(pool, nl);
+ struct adata *res = lp_alloc_adata(pool, nl);
memcpy(res->data, tmp, nl);
return res;
}
@@ -446,7 +448,7 @@ eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val
if (nl == list->length)
return list;
- struct adata *res = adata_empty(pool, nl);
+ struct adata *res = lp_alloc_adata(pool, nl);
memcpy(res->data, tmp, nl);
return res;
}
@@ -478,7 +480,7 @@ lclist_filter(struct linpool *pool, const struct adata *list, const struct f_val
if (nl == list->length)
return list;
- struct adata *res = adata_empty(pool, nl);
+ struct adata *res = lp_alloc_adata(pool, nl);
memcpy(res->data, tmp, nl);
return res;
}
@@ -599,3 +601,75 @@ val_dump(const struct f_val *v) {
return val_dump_buffer;
}
+
+struct f_val *
+lp_val_copy(struct linpool *lp, const struct f_val *v)
+{
+ switch (v->type)
+ {
+ case T_VOID:
+ case T_BOOL:
+ case T_INT:
+ case T_IP:
+ case T_PAIR:
+ case T_QUAD:
+ case T_EC:
+ case T_LC:
+ case T_RD:
+ case T_ENUM:
+ case T_PATH_MASK_ITEM:
+ /* These aren't embedded but there is no need to copy them */
+ case T_SET:
+ case T_PREFIX_SET:
+ case T_PATH_MASK:
+ case T_IFACE:
+ {
+ struct f_val *out = lp_alloc(lp, sizeof(*out));
+ *out = *v;
+ return out;
+ }
+
+ case T_NET:
+ {
+ struct {
+ struct f_val val;
+ net_addr net[0];
+ } *out = lp_alloc(lp, sizeof(*out) + v->val.net->length);
+ out->val = *v;
+ out->val.val.net = out->net;
+ net_copy(out->net, v->val.net);
+ return &out->val;
+ }
+
+ case T_STRING:
+ {
+ uint len = strlen(v->val.s);
+ struct {
+ struct f_val val;
+ char buf[0];
+ } *out = lp_alloc(lp, sizeof(*out) + len + 1);
+ out->val = *v;
+ out->val.val.s = out->buf;
+ memcpy(out->buf, v->val.s, len+1);
+ return &out->val;
+ }
+
+ case T_PATH:
+ case T_CLIST:
+ case T_ECLIST:
+ case T_LCLIST:
+ {
+ struct {
+ struct f_val val;
+ struct adata ad;
+ } *out = lp_alloc(lp, sizeof(*out) + v->val.ad->length);
+ out->val = *v;
+ out->val.val.ad = &out->ad;
+ memcpy(&out->ad, v->val.ad, v->val.ad->length);
+ return &out->val;
+ }
+
+ default:
+ bug("Unknown type in value copy: %d", v->type);
+ }
+}
diff --git a/filter/data.h b/filter/data.h
index 45246f9f..23db4a85 100644
--- a/filter/data.h
+++ b/filter/data.h
@@ -11,110 +11,37 @@
#define _BIRD_FILTER_DATA_H_
#include "nest/bird.h"
-
-/* Type numbers must be in 0..0xff range */
-#define T_MASK 0xff
-
-/* Internal types */
-enum f_type {
-/* Nothing. Simply nothing. */
- T_VOID = 0,
-
-/* User visible types, which fit in int */
- T_INT = 0x10,
- T_BOOL = 0x11,
- T_PAIR = 0x12, /* Notice that pair is stored as integer: first << 16 | second */
- T_QUAD = 0x13,
-
-/* Put enumerational types in 0x30..0x3f range */
- T_ENUM_LO = 0x30,
- T_ENUM_HI = 0x3f,
-
- T_ENUM_RTS = 0x30,
- T_ENUM_BGP_ORIGIN = 0x31,
- T_ENUM_SCOPE = 0x32,
- T_ENUM_RTC = 0x33,
- T_ENUM_RTD = 0x34,
- T_ENUM_ROA = 0x35,
- T_ENUM_NETTYPE = 0x36,
- T_ENUM_RA_PREFERENCE = 0x37,
- T_ENUM_AF = 0x38,
-
-/* new enums go here */
- T_ENUM_EMPTY = 0x3f, /* Special hack for atomic_aggr */
-
-#define T_ENUM T_ENUM_LO ... T_ENUM_HI
-
-/* Bigger ones */
- T_IP = 0x20,
- T_NET = 0x21,
- T_STRING = 0x22,
- T_PATH_MASK = 0x23, /* mask for BGP path */
- T_PATH = 0x24, /* BGP path */
- T_CLIST = 0x25, /* Community list */
- T_EC = 0x26, /* Extended community value, u64 */
- T_ECLIST = 0x27, /* Extended community list */
- T_LC = 0x28, /* Large community value, lcomm */
- T_LCLIST = 0x29, /* Large community list */
- T_RD = 0x2a, /* Route distinguisher for VPN addresses */
- T_PATH_MASK_ITEM = 0x2b, /* Path mask item for path mask constructors */
-
- T_SET = 0x80,
- T_PREFIX_SET = 0x81,
-} PACKED;
+#include "lib/type.h"
/* Filter value; size of this affects filter memory consumption */
struct f_val {
- enum f_type type; /* T_* */
- union {
- uint i;
- u64 ec;
- lcomm lc;
- ip_addr ip;
- const net_addr *net;
- const char *s;
- const struct f_tree *t;
- const struct f_trie *ti;
- const struct adata *ad;
- const struct f_path_mask *path_mask;
- struct f_path_mask_item pmi;
- } val;
+ btype type; /* T_* */
+ union bval_long val;
};
-/* Dynamic attribute definition (eattrs) */
-struct f_dynamic_attr {
- u8 type; /* EA type (EAF_*) */
- u8 bit; /* For bitfield accessors */
- enum f_type f_type; /* Filter type */
- uint ea_code; /* EA code */
-};
+#define fputip(a) ({ ip_addr *ax = falloc(sizeof(*ax)); *ax = (a); ax; })
enum f_sa_code {
- SA_FROM = 1,
- SA_GW,
+ SA_GW = 1,
SA_NET,
SA_PROTO,
- SA_SOURCE,
- SA_SCOPE,
SA_DEST,
SA_IFNAME,
SA_IFINDEX,
SA_WEIGHT,
- SA_PREF,
SA_GW_MPLS,
} PACKED;
/* Static attribute definition (members of struct rta) */
struct f_static_attr {
- enum f_type f_type; /* Filter type */
+ btype type; /* Data type */
enum f_sa_code sa_code; /* Static attribute id */
- int readonly:1; /* Don't allow writing */
+ int readonly:1; /* Don't allow writing */
};
/* Filter l-value type */
enum f_lval_type {
F_LVAL_VARIABLE,
- F_LVAL_PREFERENCE,
F_LVAL_SA,
F_LVAL_EA,
};
@@ -124,7 +51,7 @@ struct f_lval {
enum f_lval_type type;
union {
struct symbol *sym;
- struct f_dynamic_attr da;
+ const struct ea_class *da;
struct f_static_attr sa;
};
};
@@ -141,18 +68,23 @@ struct f_tree {
void *data;
};
+#define TRIE_STEP 4
+#define TRIE_STACK_LENGTH 33
+
struct f_trie_node4
{
ip4_addr addr, mask, accept;
- uint plen;
- struct f_trie_node4 *c[2];
+ u16 plen;
+ u16 local;
+ struct f_trie_node4 *c[1 << TRIE_STEP];
};
struct f_trie_node6
{
ip6_addr addr, mask, accept;
- uint plen;
- struct f_trie_node6 *c[2];
+ u16 plen;
+ u16 local;
+ struct f_trie_node6 *c[1 << TRIE_STEP];
};
struct f_trie_node
@@ -169,9 +101,20 @@ struct f_trie
u8 zero;
s8 ipv4; /* -1 for undefined / empty */
u16 data_size; /* Additional data for each trie node */
+ u32 prefix_count; /* Works only for restricted tries (pxlen == l == h) */
struct f_trie_node root; /* Root trie node */
};
+struct f_trie_walk_state
+{
+ u8 ipv4;
+ u8 accept_length; /* Current inter-node prefix position */
+ u8 start_pos; /* Initial prefix position in stack[0] */
+ u8 local_pos; /* Current intra-node prefix position */
+ u8 stack_pos; /* Current node in stack below */
+ const struct f_trie_node *stack[TRIE_STACK_LENGTH];
+};
+
struct f_tree *f_new_tree(void);
struct f_tree *build_tree(struct f_tree *);
const struct f_tree *find_tree(const struct f_tree *t, const struct f_val *val);
@@ -182,12 +125,75 @@ void tree_walk(const struct f_tree *t, void (*hook)(const struct f_tree *, void
struct f_trie *f_new_trie(linpool *lp, uint data_size);
void *trie_add_prefix(struct f_trie *t, const net_addr *n, uint l, uint h);
int trie_match_net(const struct f_trie *t, const net_addr *n);
+int trie_match_longest_ip4(const struct f_trie *t, const net_addr_ip4 *net, net_addr_ip4 *dst, ip4_addr *found0);
+int trie_match_longest_ip6(const struct f_trie *t, const net_addr_ip6 *net, net_addr_ip6 *dst, ip6_addr *found0);
+void trie_walk_init(struct f_trie_walk_state *s, const struct f_trie *t, const net_addr *from);
+int trie_walk_next(struct f_trie_walk_state *s, net_addr *net);
int trie_same(const struct f_trie *t1, const struct f_trie *t2);
void trie_format(const struct f_trie *t, buffer *buf);
+static inline int
+trie_match_next_longest_ip4(net_addr_ip4 *n, ip4_addr *found)
+{
+ while (n->pxlen)
+ {
+ n->pxlen--;
+ ip4_clrbit(&n->prefix, n->pxlen);
+
+ if (ip4_getbit(*found, n->pxlen))
+ return 1;
+ }
+
+ return 0;
+}
+
+static inline int
+trie_match_next_longest_ip6(net_addr_ip6 *n, ip6_addr *found)
+{
+ while (n->pxlen)
+ {
+ n->pxlen--;
+ ip6_clrbit(&n->prefix, n->pxlen);
+
+ if (ip6_getbit(*found, n->pxlen))
+ return 1;
+ }
+
+ return 0;
+}
+
+
+#define TRIE_WALK_TO_ROOT_IP4(trie, net, dst) ({ \
+ net_addr_ip4 dst; \
+ ip4_addr _found; \
+ for (int _n = trie_match_longest_ip4(trie, net, &dst, &_found); \
+ _n; \
+ _n = trie_match_next_longest_ip4(&dst, &_found))
+
+#define TRIE_WALK_TO_ROOT_IP6(trie, net, dst) ({ \
+ net_addr_ip6 dst; \
+ ip6_addr _found; \
+ for (int _n = trie_match_longest_ip6(trie, net, &dst, &_found); \
+ _n; \
+ _n = trie_match_next_longest_ip6(&dst, &_found))
+
+#define TRIE_WALK_TO_ROOT_END })
+
+
+#define TRIE_WALK(trie, net, from) ({ \
+ net_addr net; \
+ struct f_trie_walk_state tws_; \
+ trie_walk_init(&tws_, trie, from); \
+ while (trie_walk_next(&tws_, &net))
+
+#define TRIE_WALK_END })
+
+
#define F_CMP_ERROR 999
-const char *f_type_name(enum f_type t);
+const char *f_type_name(btype t);
+
+enum btype f_type_element_type(btype t);
int val_same(const struct f_val *v1, const struct f_val *v2);
int val_compare(const struct f_val *v1, const struct f_val *v2);
@@ -195,6 +201,8 @@ void val_format(const struct f_val *v, buffer *buf);
char *val_format_str(struct linpool *lp, const struct f_val *v);
const char *val_dump(const struct f_val *v);
+struct f_val *lp_val_copy(struct linpool *lp, const struct f_val *v);
+
static inline int val_is_ip4(const struct f_val *v)
{ return (v->type == T_IP) && ipa_is_ip4(v->val.ip); }
int val_in_range(const struct f_val *v1, const struct f_val *v2);
@@ -220,7 +228,17 @@ undef_value(struct f_val v)
}
extern const struct f_val f_const_empty_path, f_const_empty_clist, f_const_empty_eclist, f_const_empty_lclist;
+static inline const struct f_val *f_get_empty(btype t)
+{
+ switch (t) {
+ case T_PATH: return &f_const_empty_path;
+ case T_CLIST: return &f_const_empty_clist;
+ case T_ECLIST: return &f_const_empty_eclist;
+ case T_LCLIST: return &f_const_empty_lclist;
+ default: return NULL;
+ }
+}
-enum filter_return f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres);
+enum filter_return f_eval(const struct f_line *expr, struct f_val *pres);
#endif
diff --git a/filter/decl.m4 b/filter/decl.m4
index 44537aaa..c59cd7f3 100644
--- a/filter/decl.m4
+++ b/filter/decl.m4
@@ -94,7 +94,7 @@ FID_DUMP_BODY()m4_dnl
debug("%s" $4 "\n", INDENT, $5);
]])
FID_INTERPRET_EXEC()m4_dnl
-const $1 $2 = whati->$2
+$1 $2 = whati->$2
FID_INTERPRET_BODY')
# Instruction arguments are needed only until linearization is done.
@@ -256,7 +256,7 @@ FID_INTERPRET_BODY()')
m4_define(SYMBOL, `FID_MEMBER(struct symbol *, sym, [[strcmp(f1->sym->name, f2->sym->name) || (f1->sym->class != f2->sym->class)]], "symbol %s", item->sym->name)')
m4_define(RTC, `FID_MEMBER(struct rtable_config *, rtc, [[strcmp(f1->rtc->name, f2->rtc->name)]], "route table %s", item->rtc->name)')
m4_define(STATIC_ATTR, `FID_MEMBER(struct f_static_attr, sa, f1->sa.sa_code != f2->sa.sa_code,,)')
-m4_define(DYNAMIC_ATTR, `FID_MEMBER(struct f_dynamic_attr, da, f1->da.ea_code != f2->da.ea_code,,)')
+m4_define(DYNAMIC_ATTR, `FID_MEMBER(const struct ea_class *, da, f1->da != f2->da,,)')
m4_define(ACCESS_RTE, `FID_HIC(,[[do { if (!fs->rte) runtime("No route to access"); } while (0)]],NEVER_CONSTANT())')
# 2) Code wrapping
@@ -490,7 +490,7 @@ fi_constant(struct f_inst *what, struct f_val val)
}
static int
-f_const_promotion(struct f_inst *arg, enum f_type want)
+f_const_promotion(struct f_inst *arg, btype want)
{
if (arg->fi_code != FI_CONSTANT)
return 0;
@@ -640,7 +640,7 @@ FID_WR_PUT(4)m4_dnl
struct f_inst {
struct f_inst *next; /* Next instruction */
enum f_instruction_code fi_code; /* Instruction code */
- enum f_type type; /* Type of returned value, if known */
+ btype type; /* Type of returned value, if known */
int size; /* How many instructions are underneath */
int lineno; /* Line number */
union {
diff --git a/filter/f-inst.c b/filter/f-inst.c
index 00e22383..1690c9f6 100644
--- a/filter/f-inst.c
+++ b/filter/f-inst.c
@@ -240,6 +240,16 @@
if (v2.val.i == 0) runtime( "Mother told me not to divide by 0" );
RESULT(T_INT, i, v1.val.i / v2.val.i);
}
+ INST(FI_BITOR, 2, 1) {
+ ARG(1,T_INT);
+ ARG(2,T_INT);
+ RESULT(T_INT, i, v1.val.i | v2.val.i);
+ }
+ INST(FI_BITAND, 2, 1) {
+ ARG(1,T_INT);
+ ARG(2,T_INT);
+ RESULT(T_INT, i, v1.val.i & v2.val.i);
+ }
INST(FI_AND, 1, 1) {
ARG(1,T_BOOL);
ARG_TYPE_STATIC(2,T_BOOL);
@@ -519,78 +529,100 @@
{
STATIC_ATTR;
ACCESS_RTE;
- struct rta *rta = fs->rte->attrs;
+ ACCESS_EATTRS;
switch (sa.sa_code)
{
- case SA_FROM: RESULT(sa.f_type, ip, rta->from); break;
- case SA_GW: RESULT(sa.f_type, ip, rta->nh.gw); break;
- case SA_NET: RESULT(sa.f_type, net, fs->rte->net); break;
- case SA_PROTO: RESULT(sa.f_type, s, fs->rte->src->proto->name); break;
- case SA_SOURCE: RESULT(sa.f_type, i, rta->source); break;
- case SA_SCOPE: RESULT(sa.f_type, i, rta->scope); break;
- case SA_DEST: RESULT(sa.f_type, i, rta->dest); break;
- case SA_IFNAME: RESULT(sa.f_type, s, rta->nh.iface ? rta->nh.iface->name : ""); break;
- case SA_IFINDEX: RESULT(sa.f_type, i, rta->nh.iface ? rta->nh.iface->index : 0); break;
- case SA_WEIGHT: RESULT(sa.f_type, i, rta->nh.weight + 1); break;
- case SA_PREF: RESULT(sa.f_type, i, rta->pref); break;
- case SA_GW_MPLS: RESULT(sa.f_type, i, rta->nh.labels ? rta->nh.label[0] : MPLS_NULL); break;
-
+ case SA_NET: RESULT(sa.type, net, fs->rte->net); break;
+ case SA_PROTO: RESULT(sa.type, s, fs->rte->src->proto->name); break;
default:
- bug("Invalid static attribute access (%u/%u)", sa.f_type, sa.sa_code);
+ {
+ struct eattr *nhea = ea_find(*fs->eattrs, &ea_gen_nexthop);
+ struct nexthop_adata *nhad = nhea ? (struct nexthop_adata *) nhea->u.ptr : NULL;
+ struct nexthop *nh = nhad ? &nhad->nh : NULL;
+
+ switch (sa.sa_code)
+ {
+ case SA_DEST:
+ RESULT(sa.type, i, nhad ?
+ (NEXTHOP_IS_REACHABLE(nhad) ? RTD_UNICAST : nhad->dest)
+ : RTD_NONE);
+ break;
+ case SA_GW:
+ RESULT(sa.type, ip, nh ? nh->gw : IPA_NONE);
+ break;
+ case SA_IFNAME:
+ RESULT(sa.type, s, (nh && nh->iface) ? nh->iface->name : "");
+ break;
+ case SA_IFINDEX:
+ RESULT(sa.type, i, (nh && nh->iface) ? nh->iface->index : 0);
+ break;
+ case SA_WEIGHT:
+ RESULT(sa.type, i, (nh ? nh->weight : 0) + 1);
+ break;
+ case SA_GW_MPLS:
+ RESULT(sa.type, i, (nh && nh->labels) ? nh->label[0] : MPLS_NULL);
+ break;
+ default:
+ bug("Invalid static attribute access (%u/%u)", sa.type, sa.sa_code);
+ }
+ }
}
}
}
INST(FI_RTA_SET, 1, 0) {
ACCESS_RTE;
+ ACCESS_EATTRS;
ARG_ANY(1);
STATIC_ATTR;
- ARG_TYPE(1, sa.f_type);
+ ARG_TYPE(1, sa.type);
f_rta_cow(fs);
{
- struct rta *rta = fs->rte->attrs;
+ union {
+ struct nexthop_adata nha;
+ struct {
+ struct adata ad;
+ struct nexthop nh;
+ u32 label;
+ };
+ } nha;
+
+ nha.ad = (struct adata) {
+ .length = sizeof (struct nexthop_adata) - sizeof (struct adata),
+ };
+
+ eattr *a = NULL;
switch (sa.sa_code)
{
- case SA_FROM:
- rta->from = v1.val.ip;
- break;
+ case SA_DEST:
+ {
+ int i = v1.val.i;
+ if ((i != RTD_BLACKHOLE) && (i != RTD_UNREACHABLE) && (i != RTD_PROHIBIT))
+ runtime( "Destination can be changed only to blackhole, unreachable or prohibit" );
+ nha.nha.dest = i;
+ nha.ad.length = NEXTHOP_DEST_SIZE;
+ break;
+ }
case SA_GW:
{
+ struct eattr *nh_ea = ea_find(*fs->eattrs, &ea_gen_nexthop);
+
ip_addr ip = v1.val.ip;
- struct iface *ifa = ipa_is_link_local(ip) ? rta->nh.iface : NULL;
+ struct iface *ifa = (ipa_is_link_local(ip) && nh_ea) ?
+ ((struct nexthop_adata *) nh_ea->u.ptr)->nh.iface : NULL;
+
neighbor *n = neigh_find(fs->rte->src->proto, ip, ifa, 0);
if (!n || (n->scope == SCOPE_HOST))
runtime( "Invalid gw address" );
- rta->dest = RTD_UNICAST;
- rta->nh.gw = ip;
- rta->nh.iface = n->iface;
- rta->nh.next = NULL;
- rta->hostentry = NULL;
- rta->nh.labels = 0;
- }
- break;
-
- case SA_SCOPE:
- rta->scope = v1.val.i;
- break;
-
- case SA_DEST:
- {
- int i = v1.val.i;
- if ((i != RTD_BLACKHOLE) && (i != RTD_UNREACHABLE) && (i != RTD_PROHIBIT))
- runtime( "Destination can be changed only to blackhole, unreachable or prohibit" );
-
- rta->dest = i;
- rta->nh.gw = IPA_NONE;
- rta->nh.iface = NULL;
- rta->nh.next = NULL;
- rta->hostentry = NULL;
- rta->nh.labels = 0;
+ nha.nh = (struct nexthop) {
+ .gw = ip,
+ .iface = n->iface,
+ };
}
break;
@@ -600,12 +632,9 @@
if (!ifa)
runtime( "Invalid iface name" );
- rta->dest = RTD_UNICAST;
- rta->nh.gw = IPA_NONE;
- rta->nh.iface = ifa;
- rta->nh.next = NULL;
- rta->hostentry = NULL;
- rta->nh.labels = 0;
+ nha.nh = (struct nexthop) {
+ .iface = ifa,
+ };
}
break;
@@ -614,13 +643,20 @@
if (v1.val.i >= 0x100000)
runtime( "Invalid MPLS label" );
+ struct eattr *nh_ea = ea_find(*fs->eattrs, &ea_gen_nexthop);
+ if (!nh_ea)
+ runtime( "No nexthop to add a MPLS label to" );
+
+ nha.nh = ((struct nexthop_adata *) nh_ea->u.ptr)->nh;
+
if (v1.val.i != MPLS_NULL)
{
- rta->nh.label[0] = v1.val.i;
- rta->nh.labels = 1;
+ nha.nh.label[0] = v1.val.i;
+ nha.nh.labels = 1;
+ nha.ad.length = sizeof nha - sizeof (struct adata);
}
else
- rta->nh.labels = 0;
+ nha.nh.labels = 0;
}
break;
@@ -629,22 +665,36 @@
int i = v1.val.i;
if (i < 1 || i > 256)
runtime( "Setting weight value out of bounds" );
- if (rta->dest != RTD_UNICAST)
+
+ struct eattr *nh_ea = ea_find(*fs->eattrs, &ea_gen_nexthop);
+ if (!nh_ea)
+ runtime( "No nexthop to set weight on" );
+
+ struct nexthop_adata *nhad = (struct nexthop_adata *) nh_ea->u.ptr;
+ if (!NEXTHOP_IS_REACHABLE(nhad))
runtime( "Setting weight needs regular nexthop " );
+ struct nexthop_adata *nhax = (struct nexthop_adata *) tmp_copy_adata(&nhad->ad);
+
/* Set weight on all next hops */
- for (struct nexthop *nh = &rta->nh; nh; nh = nh->next)
+ NEXTHOP_WALK(nh, nhax)
nh->weight = i - 1;
- }
- break;
- case SA_PREF:
- rta->pref = v1.val.i;
+ a = ea_set_attr(fs->eattrs,
+ EA_LITERAL_DIRECT_ADATA(&ea_gen_nexthop, 0, &nhax->ad));
+ }
break;
default:
- bug("Invalid static attribute access (%u/%u)", sa.f_type, sa.sa_code);
+ bug("Invalid static attribute access (%u/%u)", sa.type, sa.sa_code);
}
+
+ if (!a)
+ a = ea_set_attr(fs->eattrs,
+ EA_LITERAL_DIRECT_ADATA(&ea_gen_nexthop, 0, tmp_copy_adata(&nha.ad)));
+
+ a->originated = 1;
+ a->fresh = 1;
}
}
@@ -652,74 +702,30 @@
DYNAMIC_ATTR;
ACCESS_RTE;
ACCESS_EATTRS;
- RESULT_TYPE(da.f_type);
+ RESULT_TYPE(da->type);
{
- eattr *e = ea_find(*fs->eattrs, da.ea_code);
-
- if (!e) {
- /* A special case: undefined as_path looks like empty as_path */
- if (da.type == EAF_TYPE_AS_PATH) {
- RESULT_(T_PATH, ad, &null_adata);
- break;
- }
-
- /* The same special case for int_set */
- if (da.type == EAF_TYPE_INT_SET) {
- RESULT_(T_CLIST, ad, &null_adata);
- break;
- }
+ const struct f_val *empty;
+ const eattr *e = ea_find(*fs->eattrs, da->id);
- /* The same special case for ec_set */
- if (da.type == EAF_TYPE_EC_SET) {
- RESULT_(T_ECLIST, ad, &null_adata);
- break;
- }
+ if (e)
+ {
+ ASSERT_DIE(e->type == da->type);
- /* The same special case for lc_set */
- if (da.type == EAF_TYPE_LC_SET) {
- RESULT_(T_LCLIST, ad, &null_adata);
- break;
+ switch (e->type) {
+ case T_IP:
+ RESULT_(T_IP, ip, *((const ip_addr *) e->u.ptr->data));
+ break;
+ default:
+ RESULT_VAL([[(struct f_val) {
+ .type = e->type,
+ .val.bval = e->u,
+ }]]);
}
-
- /* Undefined value */
- RESULT_VOID;
- break;
}
-
- switch (e->type & EAF_TYPE_MASK) {
- case EAF_TYPE_INT:
- RESULT_(da.f_type, i, e->u.data);
- break;
- case EAF_TYPE_ROUTER_ID:
- RESULT_(T_QUAD, i, e->u.data);
- break;
- case EAF_TYPE_OPAQUE:
- RESULT_(T_ENUM_EMPTY, i, 0);
- break;
- case EAF_TYPE_IP_ADDRESS:
- RESULT_(T_IP, ip, *((ip_addr *) e->u.ptr->data));
- break;
- case EAF_TYPE_AS_PATH:
- RESULT_(T_PATH, ad, e->u.ptr);
- break;
- case EAF_TYPE_BITFIELD:
- RESULT_(T_BOOL, i, !!(e->u.data & (1u << da.bit)));
- break;
- case EAF_TYPE_INT_SET:
- RESULT_(T_CLIST, ad, e->u.ptr);
- break;
- case EAF_TYPE_EC_SET:
- RESULT_(T_ECLIST, ad, e->u.ptr);
- break;
- case EAF_TYPE_LC_SET:
- RESULT_(T_LCLIST, ad, e->u.ptr);
- break;
- case EAF_TYPE_UNDEF:
+ else if (empty = f_get_empty(da->type))
+ RESULT_VAL(*empty);
+ else
RESULT_VOID;
- break;
- default:
- bug("Unknown dynamic attribute type");
- }
}
}
@@ -728,62 +734,34 @@
ACCESS_EATTRS;
ARG_ANY(1);
DYNAMIC_ATTR;
- ARG_TYPE(1, da.f_type);
+ ARG_TYPE(1, da->type);
{
- struct ea_list *l = lp_alloc(fs->pool, sizeof(struct ea_list) + sizeof(eattr));
-
- l->next = NULL;
- l->flags = EALF_SORTED;
- l->count = 1;
- l->attrs[0].id = da.ea_code;
- l->attrs[0].flags = 0;
- l->attrs[0].type = da.type | EAF_ORIGINATED | EAF_FRESH;
-
- switch (da.type) {
- case EAF_TYPE_INT:
- case EAF_TYPE_ROUTER_ID:
- l->attrs[0].u.data = v1.val.i;
- break;
+ struct eattr *a;
- case EAF_TYPE_OPAQUE:
- runtime( "Setting opaque attribute is not allowed" );
- break;
+ if (da->type >= EAF_TYPE__MAX)
+ bug("Unsupported attribute type");
- case EAF_TYPE_IP_ADDRESS:;
- int len = sizeof(ip_addr);
- struct adata *ad = lp_alloc(fs->pool, sizeof(struct adata) + len);
- ad->length = len;
- (* (ip_addr *) ad->data) = v1.val.ip;
- l->attrs[0].u.ptr = ad;
- break;
+ f_rta_cow(fs);
- case EAF_TYPE_AS_PATH:
- case EAF_TYPE_INT_SET:
- case EAF_TYPE_EC_SET:
- case EAF_TYPE_LC_SET:
- l->attrs[0].u.ptr = v1.val.ad;
+ switch (da->type) {
+ case T_OPAQUE:
+ case T_IFACE:
+ runtime( "Setting opaque attribute is not allowed" );
break;
- case EAF_TYPE_BITFIELD:
- {
- /* First, we have to find the old value */
- eattr *e = ea_find(*fs->eattrs, da.ea_code);
- u32 data = e ? e->u.data : 0;
-
- if (v1.val.i)
- l->attrs[0].u.data = data | (1u << da.bit);
- else
- l->attrs[0].u.data = data & ~(1u << da.bit);
- }
+ case T_IP:
+ a = ea_set_attr(fs->eattrs,
+ EA_LITERAL_STORE_ADATA(da, 0, &v1.val.ip, sizeof(ip_addr)));
break;
default:
- bug("Unknown dynamic attribute type");
+ a = ea_set_attr(fs->eattrs,
+ EA_LITERAL_GENERIC(da->id, da->type, 0, .u = v1.val.bval));
+ break;
}
- f_rta_cow(fs);
- l->next = *fs->eattrs;
- *fs->eattrs = l;
+ a->originated = 1;
+ a->fresh = 1;
}
}
@@ -792,21 +770,8 @@
ACCESS_RTE;
ACCESS_EATTRS;
- {
- struct ea_list *l = lp_alloc(fs->pool, sizeof(struct ea_list) + sizeof(eattr));
-
- l->next = NULL;
- l->flags = EALF_SORTED;
- l->count = 1;
- l->attrs[0].id = da.ea_code;
- l->attrs[0].flags = 0;
- l->attrs[0].type = EAF_TYPE_UNDEF | EAF_ORIGINATED | EAF_FRESH;
- l->attrs[0].u.data = 0;
-
- f_rta_cow(fs);
- l->next = *fs->eattrs;
- *fs->eattrs = l;
- }
+ f_rta_cow(fs);
+ ea_unset_attr(fs->eattrs, 1, da);
}
INST(FI_LENGTH, 1, 1) { /* Get length of */
@@ -901,14 +866,31 @@
((net_addr_roa6 *) v1.val.net)->max_pxlen);
}
- INST(FI_ROA_ASN, 1, 1) { /* Get ROA ASN */
- ARG(1, T_NET);
- if (!net_is_roa(v1.val.net))
- runtime( "ROA expected" );
+ INST(FI_ASN, 1, 1) { /* Get ROA ASN or community ASN part */
+ ARG_ANY(1);
+ RESULT_TYPE(T_INT);
+ switch(v1.type)
+ {
+ case T_NET:
+ if (!net_is_roa(v1.val.net))
+ runtime( "ROA expected" );
- RESULT(T_INT, i, (v1.val.net->type == NET_ROA4) ?
- ((net_addr_roa4 *) v1.val.net)->asn :
- ((net_addr_roa6 *) v1.val.net)->asn);
+ RESULT_(T_INT, i, (v1.val.net->type == NET_ROA4) ?
+ ((net_addr_roa4 *) v1.val.net)->asn :
+ ((net_addr_roa6 *) v1.val.net)->asn);
+ break;
+
+ case T_PAIR:
+ RESULT_(T_INT, i, v1.val.i >> 16);
+ break;
+
+ case T_LC:
+ RESULT_(T_INT, i, v1.val.lc.asn);
+ break;
+
+ default:
+ runtime( "Net, pair or lc expected" );
+ }
}
INST(FI_IP, 1, 1) { /* Convert prefix to ... */
@@ -942,6 +924,89 @@
RESULT(T_INT, i, as_path_get_last_nonaggregated(v1.val.ad));
}
+ INST(FI_PAIR_DATA, 1, 1) { /* Get data part from the standard community */
+ ARG(1, T_PAIR);
+ RESULT(T_INT, i, v1.val.i & 0xFFFF);
+ }
+
+ INST(FI_LC_DATA1, 1, 1) { /* Get data1 part from the large community */
+ ARG(1, T_LC);
+ RESULT(T_INT, i, v1.val.lc.ldp1);
+ }
+
+ INST(FI_LC_DATA2, 1, 1) { /* Get data2 part from the large community */
+ ARG(1, T_LC);
+ RESULT(T_INT, i, v1.val.lc.ldp2);
+ }
+
+ INST(FI_MIN, 1, 1) { /* Get minimum element from set */
+ ARG_ANY(1);
+ RESULT_TYPE(f_type_element_type(v1.type));
+ switch(v1.type)
+ {
+ case T_CLIST:
+ {
+ u32 val = 0;
+ int_set_min(v1.val.ad, &val);
+ RESULT_(T_PAIR, i, val);
+ }
+ break;
+
+ case T_ECLIST:
+ {
+ u64 val = 0;
+ ec_set_min(v1.val.ad, &val);
+ RESULT_(T_EC, ec, val);
+ }
+ break;
+
+ case T_LCLIST:
+ {
+ lcomm val = { 0, 0, 0 };
+ lc_set_min(v1.val.ad, &val);
+ RESULT_(T_LC, lc, val);
+ }
+ break;
+
+ default:
+ runtime( "Clist or lclist expected" );
+ }
+ }
+
+ INST(FI_MAX, 1, 1) { /* Get maximum element from set */
+ ARG_ANY(1);
+ RESULT_TYPE(f_type_element_type(v1.type));
+ switch(v1.type)
+ {
+ case T_CLIST:
+ {
+ u32 val = 0;
+ int_set_max(v1.val.ad, &val);
+ RESULT_(T_PAIR, i, val);
+ }
+ break;
+
+ case T_ECLIST:
+ {
+ u64 val = 0;
+ ec_set_max(v1.val.ad, &val);
+ RESULT_(T_EC, ec, val);
+ }
+ break;
+
+ case T_LCLIST:
+ {
+ lcomm val = { 0, 0, 0 };
+ lc_set_max(v1.val.ad, &val);
+ RESULT_(T_LC, lc, val);
+ }
+ break;
+
+ default:
+ runtime( "Clist or lclist expected" );
+ }
+ }
+
INST(FI_RETURN, 1, 1) {
NEVER_CONSTANT;
/* Acquire the return value */
@@ -1208,37 +1273,7 @@
runtime("Can't filter non-[e|l]clist");
}
- INST(FI_ROA_CHECK_IMPLICIT, 0, 1) { /* ROA Check */
- NEVER_CONSTANT;
- RTC(1);
- struct rtable *table = rtc->table;
- ACCESS_RTE;
- ACCESS_EATTRS;
- const net_addr *net = fs->rte->net;
-
- /* 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 */
- eattr *e = ea_find(*fs->eattrs, EA_CODE(PROTOCOL_BGP, 0x02));
-
- if (!e || ((e->type & EAF_TYPE_MASK) != EAF_TYPE_AS_PATH))
- runtime("Missing AS_PATH attribute");
-
- u32 as = 0;
- as_path_get_last(e->u.ptr, &as);
-
- 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");
-
- if (table->addr_type != (net->type == NET_IP4 ? NET_ROA4 : NET_ROA6))
- RESULT(T_ENUM_ROA, i, ROA_UNKNOWN); /* Prefix and table type mismatch */
- else
- RESULT(T_ENUM_ROA, i, [[ net_roa_check(table, net, as) ]]);
- }
-
- INST(FI_ROA_CHECK_EXPLICIT, 2, 1) { /* ROA Check */
+ INST(FI_ROA_CHECK, 2, 1) { /* ROA Check */
NEVER_CONSTANT;
ARG(1, T_NET);
ARG(2, T_INT);
diff --git a/filter/f-inst.h b/filter/f-inst.h
index df45f88e..047a66c9 100644
--- a/filter/f-inst.h
+++ b/filter/f-inst.h
@@ -87,15 +87,17 @@ void f_add_lines(const struct f_line_item *what, struct filter_iterator *fit);
struct filter *f_new_where(struct f_inst *);
-static inline struct f_dynamic_attr f_new_dynamic_attr(u8 type, enum f_type f_type, uint code) /* Type as core knows it, type as filters know it, and code of dynamic attribute */
-{ return (struct f_dynamic_attr) { .type = type, .f_type = f_type, .ea_code = code }; } /* f_type currently unused; will be handy for static type checking */
-static inline struct f_dynamic_attr f_new_dynamic_attr_bit(u8 bit, enum f_type f_type, uint code) /* Type as core knows it, type as filters know it, and code of dynamic attribute */
-{ return (struct f_dynamic_attr) { .type = EAF_TYPE_BITFIELD, .bit = bit, .f_type = f_type, .ea_code = code }; } /* f_type currently unused; will be handy for static type checking */
-static inline struct f_static_attr f_new_static_attr(int f_type, int code, int readonly)
-{ return (struct f_static_attr) { .f_type = f_type, .sa_code = code, .readonly = readonly }; }
-struct f_inst *f_generate_complex(enum f_instruction_code fi_code, struct f_dynamic_attr da, struct f_inst *argument);
+static inline struct f_static_attr f_new_static_attr(btype type, int code, int readonly)
+{ return (struct f_static_attr) { .type = type, .sa_code = code, .readonly = readonly }; }
struct f_inst *f_generate_roa_check(struct rtable_config *table, struct f_inst *prefix, struct f_inst *asn);
+struct f_attr_bit {
+ const struct ea_class *class;
+ uint bit;
+};
+
+#define f_new_dynamic_attr_bit(_bit, _name) ((struct f_attr_bit) { .bit = _bit, .class = ea_class_find(_name) })
+
/* Hook for call bt_assert() function in configuration */
extern void (*bt_assert_hook)(int result, const struct f_line_item *assert);
diff --git a/filter/f-util.c b/filter/f-util.c
index 410999a6..fb93ee80 100644
--- a/filter/f-util.c
+++ b/filter/f-util.c
@@ -2,7 +2,7 @@
* Filters: utility functions
*
* Copyright 1998 Pavel Machek <pavel@ucw.cz>
- * 2017 Jan Maria Matejka <mq@ucw.cz>
+ * 2017 Maria Matejka <mq@ucw.cz>
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
@@ -13,7 +13,7 @@
#include "filter/f-inst.h"
#include "lib/idm.h"
#include "nest/protocol.h"
-#include "nest/route.h"
+#include "nest/rt.h"
#define P(a,b) ((a<<8) | b)
@@ -40,144 +40,3 @@ struct filter *f_new_where(struct f_inst *where)
f->root = f_linearize(cond);
return f;
}
-
-#define CA_KEY(n) n->name, n->fda.type
-#define CA_NEXT(n) n->next
-#define CA_EQ(na,ta,nb,tb) (!strcmp(na,nb) && (ta == tb))
-#define CA_FN(n,t) (mem_hash(n, strlen(n)) ^ (t*0xaae99453U))
-#define CA_ORDER 8 /* Fixed */
-
-struct ca_storage {
- struct ca_storage *next;
- struct f_dynamic_attr fda;
- u32 uc;
- char name[0];
-};
-
-HASH(struct ca_storage) ca_hash;
-
-static struct idm ca_idm;
-static struct ca_storage **ca_storage;
-static uint ca_storage_max;
-
-static void
-ca_free(resource *r)
-{
- struct custom_attribute *ca = (void *) r;
- struct ca_storage *cas = HASH_FIND(ca_hash, CA, ca->name, ca->fda->type);
- ASSERT(cas);
-
- ca->name = NULL;
- ca->fda = NULL;
- if (!--cas->uc) {
- uint id = EA_CUSTOM_ID(cas->fda.ea_code);
- idm_free(&ca_idm, id);
- HASH_REMOVE(ca_hash, CA, cas);
- ca_storage[id] = NULL;
- mb_free(cas);
- }
-}
-
-static void
-ca_dump(resource *r)
-{
- struct custom_attribute *ca = (void *) r;
- debug("name \"%s\" id 0x%04x ea_type 0x%02x f_type 0x%02x\n",
- ca->name, ca->fda->ea_code, ca->fda->type, ca->fda->f_type);
-}
-
-static struct resclass ca_class = {
- .name = "Custom attribute",
- .size = sizeof(struct custom_attribute),
- .free = ca_free,
- .dump = ca_dump,
- .lookup = NULL,
- .memsize = NULL,
-};
-
-struct custom_attribute *
-ca_lookup(pool *p, const char *name, int f_type)
-{
- int ea_type;
-
- switch (f_type) {
- case T_INT:
- ea_type = EAF_TYPE_INT;
- break;
- case T_IP:
- ea_type = EAF_TYPE_IP_ADDRESS;
- break;
- case T_QUAD:
- ea_type = EAF_TYPE_ROUTER_ID;
- break;
- case T_PATH:
- ea_type = EAF_TYPE_AS_PATH;
- break;
- case T_CLIST:
- ea_type = EAF_TYPE_INT_SET;
- break;
- case T_ECLIST:
- ea_type = EAF_TYPE_EC_SET;
- break;
- case T_LCLIST:
- ea_type = EAF_TYPE_LC_SET;
- break;
- default:
- cf_error("Custom route attribute of unsupported type");
- }
-
- static int inited = 0;
- if (!inited) {
- idm_init(&ca_idm, &root_pool, 8);
- HASH_INIT(ca_hash, &root_pool, CA_ORDER);
-
- ca_storage_max = 256;
- ca_storage = mb_allocz(&root_pool, sizeof(struct ca_storage *) * ca_storage_max);
-
- inited++;
- }
-
- struct ca_storage *cas = HASH_FIND(ca_hash, CA, name, ea_type);
- if (cas) {
- cas->uc++;
- } else {
-
- uint id = idm_alloc(&ca_idm);
-
- if (id >= EA_CUSTOM_BIT)
- cf_error("Too many custom attributes.");
-
- if (id >= ca_storage_max) {
- ca_storage_max *= 2;
- ca_storage = mb_realloc(ca_storage, sizeof(struct ca_storage *) * ca_storage_max * 2);
- }
-
- cas = mb_allocz(&root_pool, sizeof(struct ca_storage) + strlen(name) + 1);
- cas->fda = f_new_dynamic_attr(ea_type, f_type, EA_CUSTOM(id));
- cas->uc = 1;
-
- strcpy(cas->name, name);
- ca_storage[id] = cas;
-
- HASH_INSERT(ca_hash, CA, cas);
- }
-
- struct custom_attribute *ca = ralloc(p, &ca_class);
- ca->fda = &(cas->fda);
- ca->name = cas->name;
- return ca;
-}
-
-const char *
-ea_custom_name(uint ea)
-{
- uint id = EA_CUSTOM_ID(ea);
- if (id >= ca_storage_max)
- return NULL;
-
- if (!ca_storage[id])
- return NULL;
-
- return ca_storage[id]->name;
-}
-
diff --git a/filter/filter.c b/filter/filter.c
index 6f1e6ea0..124c9932 100644
--- a/filter/filter.c
+++ b/filter/filter.c
@@ -35,10 +35,10 @@
#include "lib/ip.h"
#include "lib/net.h"
#include "lib/flowspec.h"
-#include "nest/route.h"
+#include "nest/rt.h"
#include "nest/protocol.h"
#include "nest/iface.h"
-#include "nest/attrs.h"
+#include "lib/attrs.h"
#include "conf/conf.h"
#include "filter/filter.h"
#include "filter/f-inst.h"
@@ -79,9 +79,6 @@ struct filter_state {
/* Cached pointer to ea_list */
struct ea_list **eattrs;
- /* Linpool for adata allocation */
- struct linpool *pool;
-
/* Buffer for log output */
struct buffer buf;
@@ -117,7 +114,7 @@ f_rta_cow(struct filter_state *fs)
* at the end of f_run()), also the lock of hostentry is inherited (we
* suppose hostentry is not changed by filters).
*/
- fs->rte->attrs = rta_do_cow(fs->rte->attrs, fs->pool);
+ fs->rte->attrs = rta_do_cow(fs->rte->attrs, tmp_linpool);
/* Re-cache the ea_list */
f_cache_eattrs(fs);
@@ -185,8 +182,8 @@ interpret(struct filter_state *fs, const struct f_line *line, struct f_val *val)
return F_ERROR; \
} while(0)
-#define falloc(size) lp_alloc(fs->pool, size)
-#define fpool fs->pool
+#define falloc(size) tmp_alloc(size)
+#define fpool tmp_linpool
#define ACCESS_EATTRS do { if (!fs->eattrs) f_cache_eattrs(fs); } while (0)
@@ -237,7 +234,7 @@ interpret(struct filter_state *fs, const struct f_line *line, struct f_val *val)
* tmp_pool, otherwise the filters may modify it.
*/
enum filter_return
-f_run(const struct filter *filter, struct rte *rte, struct linpool *tmp_pool, int flags)
+f_run(const struct filter *filter, struct rte *rte, int flags)
{
if (filter == FILTER_ACCEPT)
return F_ACCEPT;
@@ -250,7 +247,6 @@ f_run(const struct filter *filter, struct rte *rte, struct linpool *tmp_pool, in
/* Initialize the filter state */
filter_state = (struct filter_state) {
.rte = rte,
- .pool = tmp_pool,
.flags = flags,
};
@@ -285,11 +281,10 @@ f_run(const struct filter *filter, struct rte *rte, struct linpool *tmp_pool, in
*/
enum filter_return
-f_eval_rte(const struct f_line *expr, struct rte *rte, struct linpool *tmp_pool)
+f_eval_rte(const struct f_line *expr, struct rte *rte)
{
filter_state = (struct filter_state) {
.rte = rte,
- .pool = tmp_pool,
};
f_stack_init(filter_state);
@@ -308,11 +303,9 @@ f_eval_rte(const struct f_line *expr, struct rte *rte, struct linpool *tmp_pool)
* @pres: here the output will be stored
*/
enum filter_return
-f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres)
+f_eval(const struct f_line *expr, struct f_val *pres)
{
- filter_state = (struct filter_state) {
- .pool = tmp_pool,
- };
+ filter_state = (struct filter_state) {};
f_stack_init(filter_state);
@@ -331,9 +324,7 @@ uint
f_eval_int(const struct f_line *expr)
{
/* Called independently in parse-time to eval expressions */
- filter_state = (struct filter_state) {
- .pool = cfg_mem,
- };
+ filter_state = (struct filter_state) {};
f_stack_init(filter_state);
@@ -354,10 +345,10 @@ f_eval_int(const struct f_line *expr)
* f_eval_buf - get a value of a term and print it to the supplied buffer
*/
enum filter_return
-f_eval_buf(const struct f_line *expr, struct linpool *tmp_pool, buffer *buf)
+f_eval_buf(const struct f_line *expr, buffer *buf)
{
struct f_val val;
- enum filter_return fret = f_eval(expr, tmp_pool, &val);
+ enum filter_return fret = f_eval(expr, &val);
if (fret <= F_RETURN)
val_format(&val, buf);
return fret;
@@ -425,6 +416,23 @@ filter_commit(struct config *new, struct config *old)
}
}
+void channel_filter_dump(const struct filter *f)
+{
+ if (f == FILTER_ACCEPT)
+ debug(" ALL");
+ else if (f == FILTER_REJECT)
+ debug(" NONE");
+ else if (f == FILTER_UNDEF)
+ debug(" UNDEF");
+ else if (f->sym) {
+ ASSERT(f->sym->filter == f);
+ debug(" named filter %s", f->sym->name);
+ } else {
+ debug("\n");
+ f_dump_line(f->root, 2);
+ }
+}
+
void filters_dump_all(void)
{
struct symbol *sym;
@@ -444,19 +452,10 @@ void filters_dump_all(void)
struct channel *c;
WALK_LIST(c, sym->proto->proto->channels) {
debug(" Channel %s (%s) IMPORT", c->name, net_label[c->net_type]);
- if (c->in_filter == FILTER_ACCEPT)
- debug(" ALL\n");
- else if (c->in_filter == FILTER_REJECT)
- debug(" NONE\n");
- else if (c->in_filter == FILTER_UNDEF)
- debug(" UNDEF\n");
- else if (c->in_filter->sym) {
- ASSERT(c->in_filter->sym->filter == c->in_filter);
- debug(" named filter %s\n", c->in_filter->sym->name);
- } else {
- debug("\n");
- f_dump_line(c->in_filter->root, 2);
- }
+ channel_filter_dump(c->in_filter);
+ debug(" EXPORT", c->name, net_label[c->net_type]);
+ channel_filter_dump(c->out_filter);
+ debug("\n");
}
}
}
diff --git a/filter/filter.h b/filter/filter.h
index 9964831c..3f2e62eb 100644
--- a/filter/filter.h
+++ b/filter/filter.h
@@ -13,8 +13,8 @@
#include "lib/resource.h"
#include "lib/ip.h"
#include "lib/macro.h"
-#include "nest/route.h"
-#include "nest/attrs.h"
+#include "nest/rt.h"
+#include "lib/attrs.h"
/* Possible return values of filter execution */
enum filter_return {
@@ -51,10 +51,10 @@ struct filter {
struct rte;
-enum filter_return f_run(const struct filter *filter, struct rte *rte, struct linpool *tmp_pool, int flags);
-enum filter_return f_eval_rte(const struct f_line *expr, struct rte *rte, struct linpool *tmp_pool);
+enum filter_return f_run(const struct filter *filter, struct rte *rte, int flags);
+enum filter_return f_eval_rte(const struct f_line *expr, struct rte *rte);
uint f_eval_int(const struct f_line *expr);
-enum filter_return f_eval_buf(const struct f_line *expr, struct linpool *tmp_pool, buffer *buf);
+enum filter_return f_eval_buf(const struct f_line *expr, buffer *buf);
const char *filter_name(const struct filter *filter);
int filter_same(const struct filter *new, const struct filter *old);
@@ -70,13 +70,4 @@ void filters_dump_all(void);
#define FF_SILENT 2 /* Silent filter execution */
-/* Custom route attributes */
-struct custom_attribute {
- resource r;
- struct f_dynamic_attr *fda;
- const char *name;
-};
-
-struct custom_attribute *ca_lookup(pool *p, const char *name, int ea_type);
-
#endif
diff --git a/filter/filter_test.c b/filter/filter_test.c
index 7e4af092..63764964 100644
--- a/filter/filter_test.c
+++ b/filter/filter_test.c
@@ -46,9 +46,7 @@ run_function(const void *arg)
if (t->cmp)
return t->result == f_same(t->fn, t->cmp);
- linpool *tmp = lp_new_default(&root_pool);
- enum filter_return fret = f_eval(t->fn, tmp, NULL);
- rfree(tmp);
+ enum filter_return fret = f_eval(t->fn, NULL);
return (fret < F_REJECT);
}
diff --git a/filter/test.conf b/filter/test.conf
index 93e7a770..21e7330f 100644
--- a/filter/test.conf
+++ b/filter/test.conf
@@ -9,7 +9,109 @@ router id 62.168.0.1;
/* We have to setup any protocol */
protocol device { }
-
+/* Setting some custom attributes, enough to force BIRD to reallocate the attribute idmap */
+attribute int test_ca_int1;
+attribute int test_ca_int2;
+attribute int test_ca_int3;
+attribute int test_ca_int4;
+attribute int test_ca_int5;
+attribute int test_ca_int6;
+attribute int test_ca_int7;
+attribute int test_ca_int8;
+attribute int test_ca_int9;
+attribute int test_ca_int10;
+
+attribute ip test_ca_ip1;
+attribute ip test_ca_ip2;
+attribute ip test_ca_ip3;
+attribute ip test_ca_ip4;
+attribute ip test_ca_ip5;
+attribute ip test_ca_ip6;
+attribute ip test_ca_ip7;
+attribute ip test_ca_ip8;
+attribute ip test_ca_ip9;
+attribute ip test_ca_ip10;
+
+attribute quad test_ca_quad1;
+attribute quad test_ca_quad2;
+attribute quad test_ca_quad3;
+attribute quad test_ca_quad4;
+attribute quad test_ca_quad5;
+attribute quad test_ca_quad6;
+attribute quad test_ca_quad7;
+attribute quad test_ca_quad8;
+attribute quad test_ca_quad9;
+attribute quad test_ca_quad10;
+
+attribute bgppath test_ca_bgppath1;
+attribute bgppath test_ca_bgppath2;
+attribute bgppath test_ca_bgppath3;
+attribute bgppath test_ca_bgppath4;
+attribute bgppath test_ca_bgppath5;
+attribute bgppath test_ca_bgppath6;
+attribute bgppath test_ca_bgppath7;
+attribute bgppath test_ca_bgppath8;
+attribute bgppath test_ca_bgppath9;
+attribute bgppath test_ca_bgppath10;
+
+attribute clist test_ca_clist1;
+attribute clist test_ca_clist2;
+attribute clist test_ca_clist3;
+attribute clist test_ca_clist4;
+attribute clist test_ca_clist5;
+attribute clist test_ca_clist6;
+attribute clist test_ca_clist7;
+attribute clist test_ca_clist8;
+attribute clist test_ca_clist9;
+attribute clist test_ca_clist10;
+
+attribute eclist test_ca_eclist1;
+attribute eclist test_ca_eclist2;
+attribute eclist test_ca_eclist3;
+attribute eclist test_ca_eclist4;
+attribute eclist test_ca_eclist5;
+attribute eclist test_ca_eclist6;
+attribute eclist test_ca_eclist7;
+attribute eclist test_ca_eclist8;
+attribute eclist test_ca_eclist9;
+attribute eclist test_ca_eclist10;
+
+attribute lclist test_ca_lclist1;
+attribute lclist test_ca_lclist2;
+attribute lclist test_ca_lclist3;
+attribute lclist test_ca_lclist4;
+attribute lclist test_ca_lclist5;
+attribute lclist test_ca_lclist6;
+attribute lclist test_ca_lclist7;
+attribute lclist test_ca_lclist8;
+attribute lclist test_ca_lclist9;
+attribute lclist test_ca_lclist10;
+
+attribute lclist test_ca_lclist_max1;
+attribute lclist test_ca_lclist_max2;
+attribute lclist test_ca_lclist_max3;
+attribute lclist test_ca_lclist_max4;
+attribute lclist test_ca_lclist_max5;
+attribute lclist test_ca_lclist_max6;
+attribute lclist test_ca_lclist_max7;
+attribute lclist test_ca_lclist_max8;
+attribute lclist test_ca_lclist_max9;
+attribute lclist test_ca_lclist_max10;
+attribute lclist test_ca_lclist_max11;
+attribute lclist test_ca_lclist_max12;
+attribute lclist test_ca_lclist_max13;
+attribute lclist test_ca_lclist_max14;
+attribute lclist test_ca_lclist_max15;
+attribute lclist test_ca_lclist_max16;
+attribute lclist test_ca_lclist_max17;
+attribute lclist test_ca_lclist_max18;
+attribute lclist test_ca_lclist_max19;
+attribute lclist test_ca_lclist_max20;
+attribute lclist test_ca_lclist_max21;
+
+
+/* Uncomment this to get an error */
+#attribute int bgp_path;
/*
* Common definitions and functions
@@ -111,6 +213,14 @@ int i;
bt_assert(!(i = 4));
bt_assert(1 <= 1);
bt_assert(!(1234 < 1234));
+
+ bt_assert(10 - 5 = 5);
+ bt_assert(4294967295 + 1 = 0);
+ bt_assert(6*9=54);
+ bt_assert(984/41 = 24);
+ bt_assert(123/45 = 2);
+ bt_assert(0xfee1a | 0xbeef = 0xffeff);
+ bt_assert(0xfee1a & 0xbeef = 0xae0a);
}
bt_test_suite(t_int, "Testing integers");
@@ -335,6 +445,26 @@ ip p;
p = 1234:5678::;
bt_assert(!p.is_v4);
bt_assert(p.mask(24) = 1234:5600::);
+
+ p = 1:2:3:4:5:6:7:8;
+ bt_assert(!p.is_v4);
+ bt_assert(format(p) = "1:2:3:4:5:6:7:8");
+ bt_assert(p.mask(64) = 1:2:3:4::);
+
+ p = 10:20:30:40:50:60:70:80;
+ bt_assert(!p.is_v4);
+ bt_assert(format(p) = "10:20:30:40:50:60:70:80");
+ bt_assert(p.mask(64) = 10:20:30:40::);
+
+ p = 1090:20a0:30b0:40c0:50d0:60e0:70f0:8000;
+ bt_assert(!p.is_v4);
+ bt_assert(format(p) = "1090:20a0:30b0:40c0:50d0:60e0:70f0:8000");
+ bt_assert(p.mask(64) = 1090:20a0:30b0:40c0::);
+
+ p = ::fffe:6:c0c:936d:88c7:35d3;
+ bt_assert(!p.is_v4);
+ bt_assert(format(p) = "::fffe:6:c0c:936d:88c7:35d3");
+ bt_assert(p.mask(64) = 0:0:fffe:6::);
}
bt_test_suite(t_ip, "Testing ip address");
@@ -378,9 +508,9 @@ bt_test_suite(t_ip_set, "Testing sets of ip address");
function t_enum()
{
- bt_assert(format(RTS_STATIC) = "(enum 30)1");
- bt_assert(format(NET_IP4) = "(enum 36)1");
- bt_assert(format(NET_VPN6) = "(enum 36)4");
+ bt_assert(format(RTS_STATIC) = "(enum 31)1");
+ bt_assert(format(NET_IP4) = "(enum 3b)1");
+ bt_assert(format(NET_VPN6) = "(enum 3b)4");
bt_assert(RTS_STATIC ~ [RTS_STATIC, RTS_DEVICE]);
bt_assert(RTS_BGP !~ [RTS_STATIC, RTS_DEVICE]);
@@ -478,6 +608,33 @@ prefix set pxs;
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 } ]);
+
+ /* Formatting of prefix sets, some cases are a bit strange */
+ bt_assert(format([ 0.0.0.0/0 ]) = "[0.0.0.0/0]");
+ bt_assert(format([ 10.10.0.0/32 ]) = "[10.10.0.0/32{0.0.0.1}]");
+ bt_assert(format([ 10.10.0.0/17 ]) = "[10.10.0.0/17{0.0.128.0}]");
+ bt_assert(format([ 10.10.0.0/17{17,19} ]) = "[10.10.0.0/17{0.0.224.0}]"); # 224 = 128+64+32
+ bt_assert(format([ 10.10.128.0/17{18,19} ]) = "[10.10.128.0/18{0.0.96.0}, 10.10.192.0/18{0.0.96.0}]"); # 96 = 64+32
+ bt_assert(format([ 10.10.64.0/18- ]) = "[0.0.0.0/0, 0.0.0.0/1{128.0.0.0}, 0.0.0.0/2{64.0.0.0}, 0.0.0.0/3{32.0.0.0}, 10.10.0.0/16{255.255.0.0}, 10.10.0.0/17{0.0.128.0}, 10.10.64.0/18{0.0.64.0}]");
+ bt_assert(format([ 10.10.64.0/18+ ]) = "[10.10.64.0/18{0.0.96.0}, 10.10.64.0/20{0.0.31.255}, 10.10.80.0/20{0.0.31.255}, 10.10.96.0/20{0.0.31.255}, 10.10.112.0/20{0.0.31.255}]");
+
+ bt_assert(format([ 10.10.160.0/19 ]) = "[10.10.160.0/19{0.0.32.0}]");
+ bt_assert(format([ 10.10.160.0/19{19,22} ]) = "[10.10.160.0/19{0.0.32.0}, 10.10.160.0/20{0.0.28.0}, 10.10.176.0/20{0.0.28.0}]"); # 28 = 16+8+4
+ bt_assert(format([ 10.10.160.0/19+ ]) = "[10.10.160.0/19{0.0.32.0}, 10.10.160.0/20{0.0.31.255}, 10.10.176.0/20{0.0.31.255}]");
+
+ bt_assert(format([ ::/0 ]) = "[::/0]");
+ bt_assert(format([ 11:22:33:44:55:66:77:88/128 ]) = "[11:22:33:44:55:66:77:88/128{::1}]");
+ bt_assert(format([ 11:22:33:44::/64 ]) = "[11:22:33:44::/64{0:0:0:1::}]");
+ bt_assert(format([ 11:22:33:44::/64+ ]) = "[11:22:33:44::/64{::1:ffff:ffff:ffff:ffff}]");
+
+ bt_assert(format([ 11:22:33:44::/65 ]) = "[11:22:33:44::/65{::8000:0:0:0}]");
+ bt_assert(format([ 11:22:33:44::/65{65,67} ]) = "[11:22:33:44::/65{::e000:0:0:0}]"); # e = 8+4+2
+ bt_assert(format([ 11:22:33:44:8000::/65{66,67} ]) = "[11:22:33:44:8000::/66{::6000:0:0:0}, 11:22:33:44:c000::/66{::6000:0:0:0}]"); # 6 = 4+2
+ bt_assert(format([ 11:22:33:44:4000::/66- ]) = "[::/0, ::/1{8000::}, ::/2{4000::}, ::/3{2000::}, 11:22:33:44::/64{ffff:ffff:ffff:ffff::}, 11:22:33:44::/65{::8000:0:0:0}, 11:22:33:44:4000::/66{::4000:0:0:0}]");
+ bt_assert(format([ 11:22:33:44:4000::/66+ ]) = "[11:22:33:44:4000::/66{::6000:0:0:0}, 11:22:33:44:4000::/68{::1fff:ffff:ffff:ffff}, 11:22:33:44:5000::/68{::1fff:ffff:ffff:ffff}, 11:22:33:44:6000::/68{::1fff:ffff:ffff:ffff}, 11:22:33:44:7000::/68{::1fff:ffff:ffff:ffff}]");
+ bt_assert(format([ 11:22:33:44:c000::/67 ]) = "[11:22:33:44:c000::/67{::2000:0:0:0}]");
+ bt_assert(format([ 11:22:33:44:c000::/67{67,71} ]) = "[11:22:33:44:c000::/67{::2000:0:0:0}, 11:22:33:44:c000::/68{::1e00:0:0:0}, 11:22:33:44:d000::/68{::1e00:0:0:0}]");
+ bt_assert(format([ 11:22:33:44:c000::/67+ ]) = "[11:22:33:44:c000::/67{::2000:0:0:0}, 11:22:33:44:c000::/68{::1fff:ffff:ffff:ffff}, 11:22:33:44:d000::/68{::1fff:ffff:ffff:ffff}]");
}
bt_test_suite(t_prefix_set, "Testing prefix sets");
@@ -557,6 +714,12 @@ prefix set pxs;
bt_assert(2000::/29 !~ pxs);
bt_assert(1100::/10 !~ pxs);
bt_assert(2010::/26 !~ pxs);
+
+ pxs = [ 52E0::/13{13,128} ];
+ bt_assert(52E7:BE81:379B:E6FD:541F:B0D0::/93 ~ pxs);
+
+ pxs = [ 41D8:8718::/30{0,30}, 413A:99A8:6C00::/38{38,128} ];
+ bt_assert(4180::/9 ~ pxs);
}
bt_test_suite(t_prefix6_set, "Testing prefix IPv6 sets");
@@ -683,6 +846,11 @@ clist l;
clist l2;
clist r;
{
+ bt_assert((10, 20).asn = 10);
+ bt_assert((10, 20).data = 20);
+ bt_assert(p23.asn = 2);
+ bt_assert(p23.data = 3);
+
l = - empty -;
bt_assert(l !~ [(*,*)]);
bt_assert((l ~ [(*,*)]) != (l !~ [(*,*)]));
@@ -775,6 +943,12 @@ clist r;
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))");
+
+ # minimim & maximum element
+ r = add(add(add(add(add(-empty-, (2,1)), (1,3)), (2,2)), (3,1)), (2,3));
+ bt_assert(format(r) = "(clist (2,1) (1,3) (2,2) (3,1) (2,3))");
+ bt_assert(r.min = (1,3));
+ bt_assert(r.max = (3,1));
}
bt_test_suite(t_clist, "Testing lists of communities");
@@ -880,6 +1054,12 @@ eclist r;
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))");
+
+ # minimim & maximum element
+ r = add(add(add(add(add(--empty--, (rt, 2, 1)), (rt, 1, 3)), (rt, 2, 2)), (rt, 3, 1)), (rt, 2, 3));
+ bt_assert(format(r) = "(eclist (rt, 2, 1) (rt, 1, 3) (rt, 2, 2) (rt, 3, 1) (rt, 2, 3))");
+ bt_assert(r.min = (rt, 1, 3));
+ bt_assert(r.max = (rt, 3, 1));
}
bt_test_suite(t_eclist, "Testing lists of extended communities");
@@ -939,6 +1119,10 @@ lclist r;
bt_assert(---empty--- = ---empty---);
bt_assert((10, 20, 30) !~ ---empty---);
+ bt_assert((10, 20, 30).asn = 10);
+ bt_assert((10, 20, 30).data1 = 20);
+ bt_assert((10, 20, 30).data2 = 30);
+
ll = --- empty ---;
ll = add(ll, (ten, 20, 30));
ll = add(ll, (1000, 2000, 3000));
@@ -985,6 +1169,12 @@ lclist r;
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))");
+
+ # minimim & maximum element
+ r = add(add(add(add(add(---empty---, (2, 3, 3)), (1, 2, 3)), (2, 3, 1)), (3, 1, 2)), (2, 1, 3));
+ bt_assert(format(r) = "(lclist (2, 3, 3) (1, 2, 3) (2, 3, 1) (3, 1, 2) (2, 1, 3))");
+ bt_assert(r.min = (1, 2, 3));
+ bt_assert(r.max = (3, 1, 2));
}
bt_test_suite(t_lclist, "Testing lists of large communities");
@@ -1243,6 +1433,7 @@ function __test2()
filter testf
int j;
+bool t;
{
print "Heya, filtering route to ", net.ip, " prefixlen ", net.len, " source ", source;
print "This route was from ", from;
@@ -1254,6 +1445,56 @@ int j;
rip_metric = 14;
unset(rip_metric);
+ test_ca_int1 = 42;
+ test_ca_ip2 = 1.3.5.7;
+ test_ca_quad3 = 2.4.6.8;
+ test_ca_bgppath4 = +empty+;
+ test_ca_clist5 = -empty-;
+ test_ca_eclist6 = --empty--;
+ test_ca_lclist7 = ---empty---;
+
+ igp_metric = 53;
+ babel_metric = 64;
+ t = defined(babel_router_id);
+ j = babel_seqno;
+
+ bgp_origin = ORIGIN_IGP;
+ bgp_path = +empty+;
+ bgp_next_hop = 3456:789a:bcde:f012::3456:789a;
+ bgp_med = 71;
+ bgp_local_pref = 942;
+ t = defined(bgp_atomic_aggr);
+ t = defined(bgp_aggregator);
+ bgp_community = -empty-;
+ bgp_originator_id = 9.7.5.3;
+ bgp_cluster_list = -empty-;
+ t = defined(bgp_mp_reach_nlri);
+ t = defined(bgp_mp_unreach_nlri);
+ bgp_ext_community = --empty--;
+ bgp_as4_path = +empty+;
+ t = defined(bgp_as4_aggregator);
+ t = defined(bgp_aigp);
+ bgp_large_community = ---empty---;
+ t = defined(bgp_mpls_label_stack);
+
+ ospf_metric1 = 64;
+ ospf_metric2 = 111;
+ ospf_tag = 654432;
+
+ radv_preference = RA_PREF_LOW;
+ radv_lifetime = 28;
+
+ rip_metric = 2;
+ rip_tag = 4;
+ t = defined(rip_from);
+
+ krt_source = 17;
+ krt_metric = 19;
+
+# krt_lock_mtu = false;
+# krt_lock_window = true;
+# krt_lock_rtt = krt_lock_rttvar && krt_lock_sstresh || krt_lock_cwnd;
+
accept "ok I take that";
}
diff --git a/filter/test.conf2 b/filter/test.conf2
index e95f9563..9fc8330f 100644
--- a/filter/test.conf2
+++ b/filter/test.conf2
@@ -38,12 +38,6 @@ protocol 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";
- }
preference = 15;
print preference;
diff --git a/filter/tree_test.c b/filter/tree_test.c
index 6472d17e..05702f81 100644
--- a/filter/tree_test.c
+++ b/filter/tree_test.c
@@ -19,10 +19,7 @@ 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;
+ cfg_mem = tmp_linpool;
}
static struct f_tree *
diff --git a/filter/trie.c b/filter/trie.c
index 1a4e1ac3..12ba0b82 100644
--- a/filter/trie.c
+++ b/filter/trie.c
@@ -1,7 +1,8 @@
/*
* Filters: Trie for prefix sets
*
- * Copyright 2009 Ondrej Zajicek <santiago@crfreenet.org>
+ * (c) 2009--2021 Ondrej Zajicek <santiago@crfreenet.org>
+ * (c) 2009--2021 CZ.NIC z.s.p.o.
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
@@ -9,53 +10,68 @@
/**
* DOC: Trie for prefix sets
*
- * We use a (compressed) trie to represent prefix sets. Every node
- * in the trie represents one prefix (&addr/&plen) and &plen also
- * indicates the index of the bit in the address that is used to
- * branch at the node. If we need to represent just a set of
- * prefixes, it would be simple, but we have to represent a
- * set of prefix patterns. Each prefix pattern consists of
- * &ppaddr/&pplen and two integers: &low and &high, and a prefix
- * &paddr/&plen matches that pattern if the first MIN(&plen, &pplen)
- * bits of &paddr and &ppaddr are the same and &low <= &plen <= &high.
- *
- * We use a bitmask (&accept) to represent accepted prefix lengths
- * at a node. As there are 33 prefix lengths (0..32 for IPv4), but
- * there is just one prefix of zero length in the whole trie so we
- * have &zero flag in &f_trie (indicating whether the trie accepts
- * prefix 0.0.0.0/0) as a special case, and &accept bitmask
+ * We use a (compressed) trie to represent prefix sets. Every node in the trie
+ * represents one prefix (&addr/&plen) and &plen also indicates the index of
+ * bits in the address that are used to branch at the node. Note that such
+ * prefix is not necessary a member of the prefix set, it is just a canonical
+ * prefix associated with a node. Prefix lengths of nodes are aligned to
+ * multiples of &TRIE_STEP (4) and there is 16-way branching in each
+ * node. Therefore, we say that a node is associated with a range of prefix
+ * lengths (&plen .. &plen + TRIE_STEP - 1).
+ *
+ * The prefix set is not just a set of prefixes, it is defined by a set of
+ * prefix patterns. Each prefix pattern consists of &ppaddr/&pplen and two
+ * integers: &low and &high. The tested prefix &paddr/&plen matches that pattern
+ * if the first MIN(&plen, &pplen) bits of &paddr and &ppaddr are the same and
+ * &low <= &plen <= &high.
+ *
+ * There are two ways to represent accepted prefixes for a node. First, there is
+ * a bitmask &local, which represents independently all 15 prefixes that extend
+ * the canonical prefix of the node and are within a range of prefix lengths
+ * associated with the node. E.g., for node 10.0.0.0/8 they are 10.0.0.0/8,
+ * 10.0.0.0/9, 10.128.0.0/9, .. 10.224.0.0/11. This order (first by length, then
+ * lexicographically) is used for indexing the bitmask &local, starting at
+ * position 1. I.e., index is 2^(plen - base) + offset within the same length,
+ * see function trie_local_mask6() for details.
+ *
+ * Second, we use a bitmask &accept to represent accepted prefix lengths at a
+ * node. The bit is set means that all prefixes of given length that are either
+ * subprefixes or superprefixes of the canonical prefix are accepted. As there
+ * are 33 prefix lengths (0..32 for IPv4), but there is just one prefix of zero
+ * length in the whole trie so we have &zero flag in &f_trie (indicating whether
+ * the trie accepts prefix 0.0.0.0/0) as a special case, and &accept bitmask
* represents accepted prefix lengths from 1 to 32.
*
- * There are two cases in prefix matching - a match when the length
- * of the prefix is smaller that the length of the prefix pattern,
- * (&plen < &pplen) and otherwise. The second case is simple - we
- * just walk through the trie and look at every visited node
- * whether that prefix accepts our prefix length (&plen). The
- * first case is tricky - we don't want to examine every descendant
- * of a final node, so (when we create the trie) we have to propagate
- * that information from nodes to their ascendants.
- *
- * Suppose that we have two masks (M1 and M2) for a node. Mask M1
- * represents accepted prefix lengths by just the node and mask M2
- * represents accepted prefix lengths by the node or any of its
- * descendants. Therefore M2 is a bitwise or of M1 and children's
- * M2 and this is a maintained invariant during trie building.
- * Basically, when we want to match a prefix, we walk through the trie,
- * check mask M1 for our prefix length and when we came to
- * final node, we check mask M2.
- *
- * There are two differences in the real implementation. First,
- * we use a compressed trie so there is a case that we skip our
- * final node (if it is not in the trie) and we came to node that
- * is either extension of our prefix, or completely out of path
- * In the first case, we also have to check M2.
- *
- * Second, we really need not to maintain two separate bitmasks.
- * Checks for mask M1 are always larger than &applen and we need
- * just the first &pplen bits of mask M2 (if trie compression
- * hadn't been used it would suffice to know just $applen-th bit),
- * so we have to store them together in &accept mask - the first
- * &pplen bits of mask M2 and then mask M1.
+ * One complication is handling of prefix patterns with unaligned prefix length.
+ * When such pattern is to be added, we add a primary node above (with rounded
+ * down prefix length &nlen) and a set of secondary nodes below (with rounded up
+ * prefix lengths &slen). Accepted prefix lengths of the original prefix pattern
+ * are then represented in different places based on their lengths. For prefixes
+ * shorter than &nlen, it is &accept bitmask of the primary node, for prefixes
+ * between &nlen and &slen - 1 it is &local bitmask of the primary node, and for
+ * prefixes longer of equal &slen it is &accept bitmasks of secondary nodes.
+ *
+ * There are two cases in prefix matching - a match when the length of the
+ * prefix is smaller that the length of the prefix pattern, (&plen < &pplen) and
+ * otherwise. The second case is simple - we just walk through the trie and look
+ * at every visited node whether that prefix accepts our prefix length (&plen).
+ * The first case is tricky - we do not want to examine every descendant of a
+ * final node, so (when we create the trie) we have to propagate that
+ * information from nodes to their ascendants.
+ *
+ * There are two kinds of propagations - propagation from child's &accept
+ * bitmask to parent's &accept bitmask, and propagation from child's &accept
+ * bitmask to parent's &local bitmask. The first kind is simple - as all
+ * superprefixes of a parent are also all superprefixes of appropriate length of
+ * a child, then we can just add (by bitwise or) a child &accept mask masked by
+ * parent prefix length mask to the parent &accept mask. This handles prefixes
+ * shorter than node &plen.
+ *
+ * The second kind of propagation is necessary to handle superprefixes of a
+ * child that are represented by parent &local mask - that are in the range of
+ * prefix lengths associated with the parent. For each accepted (by child
+ * &accept mask) prefix length from that range, we need to set appropriate bit
+ * in &local mask. See function trie_amask_to_local() for details.
*
* There are four cases when we walk through a trie:
*
@@ -65,8 +81,32 @@
* - we are beyond the end of path (node length > &plen)
* - we are still on path and keep walking (node length < &plen)
*
- * The walking code in trie_match_prefix() is structured according to
- * these cases.
+ * The walking code in trie_match_net() is structured according to these cases.
+ *
+ * Iteration over prefixes in a trie can be done using TRIE_WALK() macro, or
+ * directly using trie_walk_init() and trie_walk_next() functions. The second
+ * approach allows suspending the iteration and continuing in it later.
+ * Prefixes are enumerated in the usual lexicographic order and may be
+ * restricted to a subset of the trie (all subnets of a specified prefix).
+ *
+ * Note that the trie walk does not reliably enumerate `implicit' prefixes
+ * defined by &low and &high fields in prefix patterns, it is supposed to be
+ * used on tries constructed from `explicit' prefixes (&low == &plen == &high
+ * in call to trie_add_prefix()).
+ *
+ * The trie walk has three basic state variables stored in the struct
+ * &f_trie_walk_state -- the current node in &stack[stack_pos], &accept_length
+ * for iteration over inter-node prefixes (non-branching prefixes on compressed
+ * path between the current node and its parent node, stored in the bitmap
+ * &accept of the current node) and &local_pos for iteration over intra-node
+ * prefixes (stored in the bitmap &local).
+ *
+ * The trie also supports longest-prefix-match query by trie_match_longest_ip4()
+ * and it can be extended to iteration over all covering prefixes for a given
+ * prefix (from longest to shortest) using TRIE_WALK_TO_ROOT_IP4() macro. There
+ * are also IPv6 versions (for practical reasons, these functions and macros are
+ * separate for IPv4 and IPv6). There is the same limitation to enumeration of
+ * `implicit' prefixes like with the previous TRIE_WALK() macro.
*/
#include "nest/bird.h"
@@ -86,7 +126,10 @@
#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)
+#define ipa_getbit(a,p) ip6_getbit(a,p)
+#define ipa_getbits(a,p,n) ip6_getbits(a,p,n)
+#define ipa_setbits(a,p,n) ip6_setbits(a,p,n)
+#define trie_local_mask(a,b,c) trie_local_mask6(a,b,c)
#define ipt_from_ip4(x) _MI6(_I(x), 0, 0, 0)
#define ipt_to_ip4(x) _MI4(_I0(x))
@@ -109,10 +152,11 @@ f_new_trie(linpool *lp, uint data_size)
}
static inline struct f_trie_node4 *
-new_node4(struct f_trie *t, int plen, ip4_addr paddr, ip4_addr pmask, ip4_addr amask)
+new_node4(struct f_trie *t, uint plen, uint local, ip4_addr paddr, ip4_addr pmask, ip4_addr amask)
{
struct f_trie_node4 *n = lp_allocz(t->lp, sizeof(struct f_trie_node4) + t->data_size);
n->plen = plen;
+ n->local = local;
n->addr = paddr;
n->mask = pmask;
n->accept = amask;
@@ -120,10 +164,11 @@ new_node4(struct f_trie *t, int plen, ip4_addr paddr, ip4_addr pmask, ip4_addr a
}
static inline struct f_trie_node6 *
-new_node6(struct f_trie *t, int plen, ip6_addr paddr, ip6_addr pmask, ip6_addr amask)
+new_node6(struct f_trie *t, uint plen, uint local, ip6_addr paddr, ip6_addr pmask, ip6_addr amask)
{
struct f_trie_node6 *n = lp_allocz(t->lp, sizeof(struct f_trie_node6) + t->data_size);
n->plen = plen;
+ n->local = local;
n->addr = paddr;
n->mask = pmask;
n->accept = amask;
@@ -131,24 +176,24 @@ new_node6(struct f_trie *t, int plen, ip6_addr paddr, ip6_addr pmask, ip6_addr a
}
static inline struct f_trie_node *
-new_node(struct f_trie *t, int plen, ip_addr paddr, ip_addr pmask, ip_addr amask)
+new_node(struct f_trie *t, uint plen, uint local, ip_addr paddr, ip_addr pmask, ip_addr amask)
{
if (t->ipv4)
- return (struct f_trie_node *) new_node4(t, plen, ipt_to_ip4(paddr), ipt_to_ip4(pmask), ipt_to_ip4(amask));
+ return (struct f_trie_node *) new_node4(t, plen, local, ipt_to_ip4(paddr), ipt_to_ip4(pmask), ipt_to_ip4(amask));
else
- return (struct f_trie_node *) new_node6(t, plen, ipa_to_ip6(paddr), ipa_to_ip6(pmask), ipa_to_ip6(amask));
+ return (struct f_trie_node *) new_node6(t, plen, local, ipa_to_ip6(paddr), ipa_to_ip6(pmask), ipa_to_ip6(amask));
}
static inline void
attach_node4(struct f_trie_node4 *parent, struct f_trie_node4 *child)
{
- parent->c[ip4_getbit(child->addr, parent->plen) ? 1 : 0] = child;
+ parent->c[ip4_getbits(child->addr, parent->plen, TRIE_STEP)] = child;
}
static inline void
attach_node6(struct f_trie_node6 *parent, struct f_trie_node6 *child)
{
- parent->c[ip6_getbit(child->addr, parent->plen) ? 1 : 0] = child;
+ parent->c[ip6_getbits(child->addr, parent->plen, TRIE_STEP)] = child;
}
static inline void
@@ -160,63 +205,96 @@ attach_node(struct f_trie_node *parent, struct f_trie_node *child, int v4)
attach_node6(&parent->v6, &child->v6);
}
-#define GET_ADDR(N,F,X) ((X) ? ipt_from_ip4((N)->v4.F) : ipa_from_ip6((N)->v6.F))
-#define SET_ADDR(N,F,X,V) ({ if (X) (N)->v4.F =ipt_to_ip4(V); else (N)->v6.F =ipa_to_ip6(V); })
-#define GET_CHILD(N,F,X,I) ((X) ? (struct f_trie_node *) (N)->v4.c[I] : (struct f_trie_node *) (N)->v6.c[I])
-/**
- * trie_add_prefix
- * @t: trie to add to
- * @net: IP network prefix
- * @l: prefix lower bound
- * @h: prefix upper bound
+/*
+ * Internal prefixes of a node a represented by the local bitmask, each bit for
+ * one prefix. Bit 0 is unused, Bit 1 is for the main prefix of the node,
+ * remaining bits correspond to subprefixes by this pattern:
*
- * 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).
+ * 1
+ * 2 3
+ * 4 5 6 7
+ * 8 9 A B C D E F
*
- * Returns a pointer to the allocated node. The function can return a pointer to
- * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
- * a pointer to the root node is returned. Returns NULL when called with
- * mismatched IPv4/IPv6 net type.
+ * E.g. for 10.0.0.0/8 node, the 10.64.0.0/10 would be position 5.
*/
-void *
-trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
+/*
+ * Compute appropriate mask representing prefix px/plen in local bitmask of node
+ * with prefix length nlen. Assuming that nlen <= plen < (nlen + TRIE_STEP).
+ */
+static inline uint
+trie_local_mask4(ip4_addr px, uint plen, uint nlen)
{
- uint plen = net_pxlen(net);
- ip_addr px;
- int v4;
+ uint step = plen - nlen;
+ uint pos = (1u << step) + ip4_getbits(px, nlen, step);
+ return 1u << pos;
+}
- switch (net->type)
- {
- case NET_IP4: px = ipt_from_ip4(net4_prefix(net)); v4 = 1; break;
- case NET_IP6: px = ipa_from_ip6(net6_prefix(net)); v4 = 0; break;
- default: bug("invalid type");
- }
+static inline uint
+trie_local_mask6(ip6_addr px, uint plen, uint nlen)
+{
+ uint step = plen - nlen;
+ uint pos = (1u << step) + ip6_getbits(px, nlen, step);
+ return 1u << pos;
+}
- if (t->ipv4 != v4)
- {
- if (t->ipv4 < 0)
- t->ipv4 = v4;
- else
- return NULL;
- }
+/*
+ * Compute an appropriate local mask (for a node with prefix length nlen)
+ * representing prefixes of px that are accepted by amask and fall within the
+ * range associated with that node. Used for propagation of child accept mask
+ * to parent local mask.
+ */
+static inline uint
+trie_amask_to_local(ip_addr px, ip_addr amask, uint nlen)
+{
+ uint local = 0;
- if (l == 0)
- t->zero = 1;
- else
- l--;
+ for (uint plen = MAX(nlen, 1); plen < (nlen + TRIE_STEP); plen++)
+ if (ipa_getbit(amask, plen - 1))
+ local |= trie_local_mask(px, plen, nlen);
- if (h < plen)
- plen = h;
+ return local;
+}
+
+/*
+ * Compute a bitmask representing a level of subprefixes (of the same length),
+ * using specified position as a root. E.g., level 2 from root position 3 would
+ * be bit positions C-F, returned as bitmask 0xf000.
+ */
+static inline uint
+trie_level_mask(uint pos, uint level)
+{
+ return ((1u << (1u << level)) - 1) << (pos << level);
+}
- ip_addr amask = ipa_xor(ipa_mkmask(l), ipa_mkmask(h));
+
+#define GET_ADDR(N,F,X) ((X) ? ipt_from_ip4((N)->v4.F) : ipa_from_ip6((N)->v6.F))
+#define SET_ADDR(N,F,X,V) ({ if (X) (N)->v4.F =ipt_to_ip4(V); else (N)->v6.F =ipa_to_ip6(V); })
+
+#define GET_LOCAL(N,X) ((X) ? (N)->v4.local : (N)->v6.local)
+#define ADD_LOCAL(N,X,V) ({ uint v_ = (V); if (X) (N)->v4.local |= v_; else (N)->v6.local |= v_; })
+
+#define GET_CHILD(N,X,I) ((X) ? (struct f_trie_node *) (N)->v4.c[I] : (struct f_trie_node *) (N)->v6.c[I])
+
+
+static void *
+trie_add_node(struct f_trie *t, uint plen, ip_addr px, uint local, uint l, uint h)
+{
+ uint l_ = l ? (l - 1) : 0;
+ ip_addr amask = (l_ < h) ? ipa_xor(ipa_mkmask(l_), ipa_mkmask(h)) : IPA_NONE;
ip_addr pmask = ipa_mkmask(plen);
ip_addr paddr = ipa_and(px, pmask);
struct f_trie_node *o = NULL;
struct f_trie_node *n = &t->root;
+ int v4 = t->ipv4;
+ /* Add all bits for each active level (0x0002 0x000c 0x00f0 0xff00) */
+ for (uint i = 0; i < TRIE_STEP; i++)
+ if ((l <= (plen + i)) && ((plen + i) <= h))
+ local |= trie_level_mask(1, i);
+
+ DBG("Insert node %I/%u (%I %x)\n", paddr, plen, amask, local);
while (n)
{
ip_addr naddr = GET_ADDR(n, addr, v4);
@@ -225,23 +303,31 @@ trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
ip_addr cmask = ipa_and(nmask, pmask);
uint nlen = v4 ? n->v4.plen : n->v6.plen;
+ DBG("Found node %I/%u (%I %x)\n",
+ naddr, nlen, accept, v4 ? n->v4.local : n->v6.local);
+
if (ipa_compare(ipa_and(paddr, cmask), ipa_and(naddr, cmask)))
{
/* We are out of path - we have to add branching node 'b'
between node 'o' and node 'n', and attach new node 'a'
as the other child of 'b'. */
- int blen = ipa_pxlen(paddr, naddr);
+ int blen = ROUND_DOWN_POW2(ipa_pxlen(paddr, naddr), TRIE_STEP);
ip_addr bmask = ipa_mkmask(blen);
ip_addr baddr = ipa_and(px, bmask);
/* Merge accept masks from children to get accept mask for node 'b' */
ip_addr baccm = ipa_and(ipa_or(amask, accept), bmask);
+ uint bloc = trie_amask_to_local(naddr, accept, blen) |
+ trie_amask_to_local(paddr, amask, blen);
- struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
- struct f_trie_node *b = new_node(t, blen, baddr, bmask, baccm);
+ struct f_trie_node *a = new_node(t, plen, local, paddr, pmask, amask);
+ struct f_trie_node *b = new_node(t, blen, bloc, baddr, bmask, baccm);
attach_node(o, b, v4);
attach_node(b, n, v4);
attach_node(b, a, v4);
+ t->prefix_count++;
+
+ DBG("Case 1\n");
return a;
}
@@ -249,66 +335,195 @@ trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
{
/* We add new node 'a' between node 'o' and node 'n' */
amask = ipa_or(amask, ipa_and(accept, pmask));
- struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
+ local |= trie_amask_to_local(naddr, accept, plen);
+ struct f_trie_node *a = new_node(t, plen, local, paddr, pmask, amask);
attach_node(o, a, v4);
attach_node(a, n, v4);
+ t->prefix_count++;
+
+ DBG("Case 2\n");
return a;
}
if (plen == nlen)
{
- /* We already found added node in trie. Just update accept mask */
+ /* We already found added node in trie. Just update accept and local mask */
accept = ipa_or(accept, amask);
SET_ADDR(n, accept, v4, accept);
+
+ if ((GET_LOCAL(n, v4) & local) != local)
+ t->prefix_count++;
+
+ ADD_LOCAL(n, v4, local);
+
+ DBG("Case 3\n");
return n;
}
/* Update accept mask part M2 and go deeper */
accept = ipa_or(accept, ipa_and(amask, nmask));
SET_ADDR(n, accept, v4, accept);
+ ADD_LOCAL(n, v4, trie_amask_to_local(paddr, amask, nlen));
+
+ DBG("Step %u\n", ipa_getbits(paddr, nlen));
/* n->plen < plen and plen <= 32 (128) */
o = n;
- n = GET_CHILD(n, c, v4, ipa_getbit(paddr, nlen) ? 1 : 0);
+ n = GET_CHILD(n, v4, ipa_getbits(paddr, nlen, TRIE_STEP));
}
/* We add new tail node 'a' after node 'o' */
- struct f_trie_node *a = new_node(t, plen, paddr, pmask, amask);
+ struct f_trie_node *a = new_node(t, plen, local, paddr, pmask, amask);
attach_node(o, a, v4);
+ t->prefix_count++;
+ DBG("Case 4\n");
return a;
}
+/**
+ * trie_add_prefix
+ * @t: trie to add to
+ * @net: IP network prefix
+ * @l: prefix lower bound
+ * @h: prefix upper bound
+ *
+ * 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).
+ *
+ * Returns a pointer to the allocated node. The function can return a pointer to
+ * an existing node if @px and @plen are the same. If px/plen == 0/0 (or ::/0),
+ * a pointer to the root node is returned. Returns NULL when called with
+ * mismatched IPv4/IPv6 net type.
+ */
+void *
+trie_add_prefix(struct f_trie *t, const net_addr *net, uint l, uint h)
+{
+ uint plen = net_pxlen(net);
+ ip_addr px;
+ int v4;
+
+ switch (net->type)
+ {
+ case NET_IP4:
+ case NET_VPN4:
+ case NET_ROA4:
+ px = ipt_from_ip4(net4_prefix(net));
+ v4 = 1;
+ break;
+
+ case NET_IP6:
+ case NET_VPN6:
+ case NET_ROA6:
+ case NET_IP6_SADR:
+ px = ipa_from_ip6(net6_prefix(net));
+ v4 = 0;
+ break;
+
+ default:
+ bug("invalid type");
+ }
+
+ if (t->ipv4 != v4)
+ {
+ if (t->ipv4 < 0)
+ t->ipv4 = v4;
+ else
+ return NULL;
+ }
+
+ DBG("\nInsert net %N (%u-%u)\n", net, l, h);
+
+ if (l == 0)
+ t->zero = 1;
+
+ if (h < plen)
+ plen = h;
+
+ /* Primary node length, plen rounded down */
+ uint nlen = ROUND_DOWN_POW2(plen, TRIE_STEP);
+
+ if (plen == nlen)
+ return trie_add_node(t, nlen, px, 0, l, h);
+
+ /* Secondary node length, plen rouned up */
+ uint slen = nlen + TRIE_STEP;
+ void *node = NULL;
+
+ /*
+ * For unaligned prefix lengths it is more complicated. We need to encode
+ * matching prefixes of lengths from l to h. There are three cases of lengths:
+ *
+ * 1) 0..nlen are encoded by the accept mask of the primary node
+ * 2) nlen..(slen-1) are encoded by the local mask of the primary node
+ * 3) slen..max are encoded in secondary nodes
+ */
+
+ if (l < slen)
+ {
+ uint local = 0;
+
+ /* Compute local bits for accepted nlen..(slen-1) prefixes */
+ for (uint i = 0; i < TRIE_STEP; i++)
+ if ((l <= (nlen + i)) && ((nlen + i) <= h))
+ {
+ uint pos = (1u << i) + ipa_getbits(px, nlen, i);
+ uint len = ((nlen + i) <= plen) ? 1 : (1u << (nlen + i - plen));
+
+ /* We need to fill 'len' bits starting at 'pos' position */
+ local |= ((1u << len) - 1) << pos;
+ }
+
+ /* Add the primary node */
+ node = trie_add_node(t, nlen, px, local, l, nlen);
+ }
+
+ if (slen <= h)
+ {
+ uint l2 = MAX(l, slen);
+ uint max = (1u << (slen - plen));
+
+ /* Add secondary nodes */
+ for (uint i = 0; i < max; i++)
+ node = trie_add_node(t, slen, ipa_setbits(px, slen - 1, i), 0, l2, h);
+ }
+
+ return node;
+}
+
+
static int
trie_match_net4(const struct f_trie *t, ip4_addr px, uint plen)
{
- ip4_addr pmask = ip4_mkmask(plen);
- ip4_addr paddr = ip4_and(px, pmask);
-
if (plen == 0)
return t->zero;
int plentest = plen - 1;
+ uint nlen = ROUND_DOWN_POW2(plen, TRIE_STEP);
+ uint local = trie_local_mask4(px, plen, nlen);
const struct f_trie_node4 *n = &t->root.v4;
while (n)
{
- ip4_addr cmask = ip4_and(n->mask, pmask);
-
/* We are out of path */
- if (ip4_compare(ip4_and(paddr, cmask), ip4_and(n->addr, cmask)))
+ if (!ip4_prefix_equal(px, n->addr, MIN(plen, n->plen)))
return 0;
+ /* Check local mask */
+ if ((n->plen == nlen) && (n->local & local))
+ return 1;
+
/* Check accept mask */
if (ip4_getbit(n->accept, plentest))
return 1;
/* We finished trie walk and still no match */
- if (plen <= n->plen)
+ if (nlen <= n->plen)
return 0;
/* Choose children */
- n = n->c[(ip4_getbit(paddr, n->plen)) ? 1 : 0];
+ n = n->c[ip4_getbits(px, n->plen, TRIE_STEP)];
}
return 0;
@@ -317,33 +532,34 @@ trie_match_net4(const struct f_trie *t, ip4_addr px, uint plen)
static int
trie_match_net6(const struct f_trie *t, ip6_addr px, uint plen)
{
- ip6_addr pmask = ip6_mkmask(plen);
- ip6_addr paddr = ip6_and(px, pmask);
-
if (plen == 0)
return t->zero;
int plentest = plen - 1;
+ uint nlen = ROUND_DOWN_POW2(plen, TRIE_STEP);
+ uint local = trie_local_mask6(px, plen, nlen);
const struct f_trie_node6 *n = &t->root.v6;
while (n)
{
- ip6_addr cmask = ip6_and(n->mask, pmask);
-
/* We are out of path */
- if (ip6_compare(ip6_and(paddr, cmask), ip6_and(n->addr, cmask)))
+ if (!ip6_prefix_equal(px, n->addr, MIN(plen, n->plen)))
return 0;
+ /* Check local mask */
+ if ((n->plen == nlen) && (n->local & local))
+ return 1;
+
/* Check accept mask */
if (ip6_getbit(n->accept, plentest))
return 1;
/* We finished trie walk and still no match */
- if (plen <= n->plen)
+ if (nlen <= n->plen)
return 0;
/* Choose children */
- n = n->c[(ip6_getbit(paddr, n->plen)) ? 1 : 0];
+ n = n->c[ip6_getbits(px, n->plen, TRIE_STEP)];
}
return 0;
@@ -378,6 +594,412 @@ trie_match_net(const struct f_trie *t, const net_addr *n)
}
}
+
+/**
+ * trie_match_longest_ip4
+ * @t: trie
+ * @net: net address
+ * @dst: return value
+ * @found0: optional returned bitmask of found nodes
+ *
+ * Perform longest prefix match for the address @net and return the resulting
+ * prefix in the buffer @dst. The bitmask @found0 is used to report lengths of
+ * prefixes on the path from the root to the resulting prefix. E.g., if there is
+ * also a /20 shorter matching prefix, then 20-th bit is set in @found0. This
+ * can be used to enumerate all matching prefixes for the network @net using
+ * function trie_match_next_longest_ip4() or macro TRIE_WALK_TO_ROOT_IP4().
+ *
+ * This function assumes IPv4 trie, there is also an IPv6 variant. The @net
+ * argument is typed as net_addr_ip4, but would accept any IPv4-based net_addr,
+ * like net4_prefix(). Anyway, returned @dst is always net_addr_ip4.
+ *
+ * Result: 1 if a matching prefix was found, 0 if not.
+ */
+int
+trie_match_longest_ip4(const struct f_trie *t, const net_addr_ip4 *net, net_addr_ip4 *dst, ip4_addr *found0)
+{
+ ASSERT(t->ipv4);
+
+ const ip4_addr prefix = net->prefix;
+ const int pxlen = net->pxlen;
+
+ const struct f_trie_node4 *n = &t->root.v4;
+ int len = 0;
+
+ ip4_addr found = IP4_NONE;
+ int last = -1;
+
+ while (n)
+ {
+ /* We are out of path */
+ if (!ip4_prefix_equal(prefix, n->addr, MIN(pxlen, n->plen)))
+ goto done;
+
+ /* Check accept mask */
+ for (; len < n->plen; len++)
+ {
+ if (len > pxlen)
+ goto done;
+
+ if (ip4_getbit(n->accept, len - 1))
+ {
+ /* len is always < 32 due to len < n->plen */
+ ip4_setbit(&found, len);
+ last = len;
+ }
+ }
+
+ /* Special case for max length, there is only one valid local position */
+ if (len == IP4_MAX_PREFIX_LENGTH)
+ {
+ if (n->local & (1u << 1))
+ last = len;
+
+ goto done;
+ }
+
+ /* Check local mask */
+ for (int pos = 1; pos < (1 << TRIE_STEP); pos = 2 * pos + ip4_getbit(prefix, len), len++)
+ {
+ if (len > pxlen)
+ goto done;
+
+ if (n->local & (1u << pos))
+ {
+ /* len is always < 32 due to special case above */
+ ip4_setbit(&found, len);
+ last = len;
+ }
+ }
+
+ /* Choose child */
+ n = n->c[ip4_getbits(prefix, n->plen, TRIE_STEP)];
+ }
+
+done:
+ if (last < 0)
+ return 0;
+
+ *dst = NET_ADDR_IP4(ip4_and(prefix, ip4_mkmask(last)), last);
+
+ if (found0)
+ *found0 = found;
+
+ return 1;
+}
+
+
+/**
+ * trie_match_longest_ip6
+ * @t: trie
+ * @net: net address
+ * @dst: return value
+ * @found0: optional returned bitmask of found nodes
+ *
+ * Perform longest prefix match for the address @net and return the resulting
+ * prefix in the buffer @dst. The bitmask @found0 is used to report lengths of
+ * prefixes on the path from the root to the resulting prefix. E.g., if there is
+ * also a /20 shorter matching prefix, then 20-th bit is set in @found0. This
+ * can be used to enumerate all matching prefixes for the network @net using
+ * function trie_match_next_longest_ip6() or macro TRIE_WALK_TO_ROOT_IP6().
+ *
+ * This function assumes IPv6 trie, there is also an IPv4 variant. The @net
+ * argument is typed as net_addr_ip6, but would accept any IPv6-based net_addr,
+ * like net6_prefix(). Anyway, returned @dst is always net_addr_ip6.
+ *
+ * Result: 1 if a matching prefix was found, 0 if not.
+ */
+int
+trie_match_longest_ip6(const struct f_trie *t, const net_addr_ip6 *net, net_addr_ip6 *dst, ip6_addr *found0)
+{
+ ASSERT(!t->ipv4);
+
+ const ip6_addr prefix = net->prefix;
+ const int pxlen = net->pxlen;
+
+ const struct f_trie_node6 *n = &t->root.v6;
+ int len = 0;
+
+ ip6_addr found = IP6_NONE;
+ int last = -1;
+
+ while (n)
+ {
+ /* We are out of path */
+ if (!ip6_prefix_equal(prefix, n->addr, MIN(pxlen, n->plen)))
+ goto done;
+
+ /* Check accept mask */
+ for (; len < n->plen; len++)
+ {
+ if (len > pxlen)
+ goto done;
+
+ if (ip6_getbit(n->accept, len - 1))
+ {
+ /* len is always < 128 due to len < n->plen */
+ ip6_setbit(&found, len);
+ last = len;
+ }
+ }
+
+ /* Special case for max length, there is only one valid local position */
+ if (len == IP6_MAX_PREFIX_LENGTH)
+ {
+ if (n->local & (1u << 1))
+ last = len;
+
+ goto done;
+ }
+
+ /* Check local mask */
+ for (int pos = 1; pos < (1 << TRIE_STEP); pos = 2 * pos + ip6_getbit(prefix, len), len++)
+ {
+ if (len > pxlen)
+ goto done;
+
+ if (n->local & (1u << pos))
+ {
+ /* len is always < 128 due to special case above */
+ ip6_setbit(&found, len);
+ last = len;
+ }
+ }
+
+ /* Choose child */
+ n = n->c[ip6_getbits(prefix, n->plen, TRIE_STEP)];
+ }
+
+done:
+ if (last < 0)
+ return 0;
+
+ *dst = NET_ADDR_IP6(ip6_and(prefix, ip6_mkmask(last)), last);
+
+ if (found0)
+ *found0 = found;
+
+ return 1;
+}
+
+#define SAME_PREFIX(A,B,X,L) ((X) ? ip4_prefix_equal((A)->v4.addr, net4_prefix(B), (L)) : ip6_prefix_equal((A)->v6.addr, net6_prefix(B), (L)))
+#define GET_NET_BITS(N,X,A,B) ((X) ? ip4_getbits(net4_prefix(N), (A), (B)) : ip6_getbits(net6_prefix(N), (A), (B)))
+
+/**
+ * trie_walk_init
+ * @s: walk state
+ * @t: trie
+ * @net: optional subnet for walk
+ *
+ * Initialize walk state for subsequent walk through nodes of the trie @t by
+ * trie_walk_next(). The argument @net allows to restrict walk to given subnet,
+ * otherwise full walk over all nodes is used. This is done by finding node at
+ * or below @net and starting position in it.
+ */
+void
+trie_walk_init(struct f_trie_walk_state *s, const struct f_trie *t, const net_addr *net)
+{
+ *s = (struct f_trie_walk_state) {
+ .ipv4 = t->ipv4,
+ .accept_length = 0,
+ .start_pos = 1,
+ .local_pos = 1,
+ .stack_pos = 0,
+ .stack[0] = &t->root
+ };
+
+ if (!net)
+ return;
+
+ /* We want to find node of level at least plen */
+ int plen = ROUND_DOWN_POW2(net->pxlen, TRIE_STEP);
+ const struct f_trie_node *n = &t->root;
+ const int v4 = t->ipv4;
+
+ while (n)
+ {
+ int nlen = v4 ? n->v4.plen : n->v6.plen;
+
+ /* We are out of path */
+ if (!SAME_PREFIX(n, net, v4, MIN(net->pxlen, nlen)))
+ break;
+
+ /* We found final node */
+ if (nlen >= plen)
+ {
+ if (nlen == plen)
+ {
+ /* Find proper local_pos, while accept_length is not used */
+ int step = net->pxlen - plen;
+ s->start_pos = s->local_pos = (1u << step) + GET_NET_BITS(net, v4, plen, step);
+ s->accept_length = plen;
+ }
+ else
+ {
+ /* Start from pos 1 in local node, but first try accept mask */
+ s->accept_length = net->pxlen;
+ }
+
+ s->stack[0] = n;
+ return;
+ }
+
+ /* Choose child */
+ n = GET_CHILD(n, v4, GET_NET_BITS(net, v4, nlen, TRIE_STEP));
+ }
+
+ s->stack[0] = NULL;
+ return;
+}
+
+#define GET_ACCEPT_BIT(N,X,B) ((X) ? ip4_getbit((N)->v4.accept, (B)) : ip6_getbit((N)->v6.accept, (B)))
+#define GET_LOCAL_BIT(N,X,B) (((X) ? (N)->v4.local : (N)->v6.local) & (1u << (B)))
+
+/**
+ * trie_walk_next
+ * @s: walk state
+ * @net: return value
+ *
+ * Find the next prefix in the trie walk and return it in the buffer @net.
+ * Prefixes are walked in the usual lexicographic order and may be restricted
+ * to a subset of the trie during walk setup by trie_walk_init(). Note that the
+ * trie walk does not iterate reliably over 'implicit' prefixes defined by &low
+ * and &high fields in prefix patterns, it is supposed to be used on tries
+ * constructed from 'explicit' prefixes (&low == &plen == &high in call to
+ * trie_add_prefix()).
+ *
+ * Result: 1 if the next prefix was found, 0 for the end of walk.
+ */
+int
+trie_walk_next(struct f_trie_walk_state *s, net_addr *net)
+{
+ const struct f_trie_node *n = s->stack[s->stack_pos];
+ int len = s->accept_length;
+ int pos = s->local_pos;
+ int v4 = s->ipv4;
+
+ /*
+ * The walk has three basic state variables -- n, len and pos. In each node n,
+ * we first walk superprefixes (by len in &accept bitmask), and then we walk
+ * internal positions (by pos in &local bitmask). These positions are:
+ *
+ * 1
+ * 2 3
+ * 4 5 6 7
+ * 8 9 A B C D E F
+ *
+ * We walk them depth-first, including virtual positions 10-1F that are
+ * equivalent of position 1 in child nodes 0-F.
+ */
+
+ if (!n)
+ {
+ memset(net, 0, v4 ? sizeof(net_addr_ip4) : sizeof(net_addr_ip6));
+ return 0;
+ }
+
+next_node:;
+ /* Current node prefix length */
+ int nlen = v4 ? n->v4.plen : n->v6.plen;
+
+ /* First, check for accept prefix */
+ for (; len < nlen; len++)
+ if (GET_ACCEPT_BIT(n, v4, len - 1))
+ {
+ if (v4)
+ net_fill_ip4(net, ip4_and(n->v4.addr, ip4_mkmask(len)), len);
+ else
+ net_fill_ip6(net, ip6_and(n->v6.addr, ip6_mkmask(len)), len);
+
+ s->local_pos = pos;
+ s->accept_length = len + 1;
+ return 1;
+ }
+
+next_pos:
+ /* Bottom of this node */
+ if (pos >= (1 << TRIE_STEP))
+ {
+ const struct f_trie_node *child = GET_CHILD(n, v4, pos - (1 << TRIE_STEP));
+ int dir = 0;
+
+ /* No child node */
+ if (!child)
+ {
+ /* Step up until return from left child (pos is even) */
+ do
+ {
+ /* Step up from start node */
+ if ((s->stack_pos == 0) && (pos == s->start_pos))
+ {
+ s->stack[0] = NULL;
+ memset(net, 0, v4 ? sizeof(net_addr_ip4) : sizeof(net_addr_ip6));
+ return 0;
+ }
+
+ /* Top of this node */
+ if (pos == 1)
+ {
+ ASSERT(s->stack_pos);
+ const struct f_trie_node *old = n;
+
+ /* Move to parent node */
+ s->stack_pos--;
+ n = s->stack[s->stack_pos];
+ nlen = v4 ? n->v4.plen : n->v6.plen;
+
+ pos = v4 ?
+ ip4_getbits(old->v4.addr, nlen, TRIE_STEP) :
+ ip6_getbits(old->v6.addr, nlen, TRIE_STEP);
+ pos += (1 << TRIE_STEP);
+ len = nlen;
+
+ ASSERT(GET_CHILD(n, v4, pos - (1 << TRIE_STEP)) == old);
+ }
+
+ /* Step up */
+ dir = pos % 2;
+ pos = pos / 2;
+ }
+ while (dir);
+
+ /* Continue with step down to the right child */
+ pos = 2 * pos + 1;
+ goto next_pos;
+ }
+
+ /* Move to child node */
+ pos = 1;
+ len = nlen + TRIE_STEP;
+
+ s->stack_pos++;
+ n = s->stack[s->stack_pos] = child;
+ goto next_node;
+ }
+
+ /* Check for local prefix */
+ if (GET_LOCAL_BIT(n, v4, pos))
+ {
+ /* Convert pos to address of local network */
+ int x = (pos >= 2) + (pos >= 4) + (pos >= 8);
+ int y = pos & ((1u << x) - 1);
+
+ if (v4)
+ net_fill_ip4(net, !x ? n->v4.addr : ip4_setbits(n->v4.addr, nlen + x - 1, y), nlen + x);
+ else
+ net_fill_ip6(net, !x ? n->v6.addr : ip6_setbits(n->v6.addr, nlen + x - 1, y), nlen + x);
+
+ s->local_pos = 2 * pos;
+ s->accept_length = len;
+ return 1;
+ }
+
+ /* Step down */
+ pos = 2 * pos;
+ goto next_pos;
+}
+
+
static int
trie_node_same4(const struct f_trie_node4 *t1, const struct f_trie_node4 *t2)
{
@@ -392,7 +1014,11 @@ trie_node_same4(const struct f_trie_node4 *t1, const struct f_trie_node4 *t2)
(! ip4_equal(t1->accept, t2->accept)))
return 0;
- return trie_node_same4(t1->c[0], t2->c[0]) && trie_node_same4(t1->c[1], t2->c[1]);
+ for (uint i = 0; i < (1 << TRIE_STEP); i++)
+ if (! trie_node_same4(t1->c[i], t2->c[i]))
+ return 0;
+
+ return 1;
}
static int
@@ -409,7 +1035,11 @@ trie_node_same6(const struct f_trie_node6 *t1, const struct f_trie_node6 *t2)
(! ip6_equal(t1->accept, t2->accept)))
return 0;
- return trie_node_same6(t1->c[0], t2->c[0]) && trie_node_same6(t1->c[1], t2->c[1]);
+ for (uint i = 0; i < (1 << TRIE_STEP); i++)
+ if (! trie_node_same6(t1->c[i], t2->c[i]))
+ return 0;
+
+ return 1;
}
/**
@@ -431,30 +1061,70 @@ trie_same(const struct f_trie *t1, const struct f_trie *t2)
return trie_node_same6(&t1->root.v6, &t2->root.v6);
}
+
+static const u8 log2[16] = {0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3};
+
static void
-trie_node_format4(const struct f_trie_node4 *t, buffer *buf)
+trie_node_format(const struct f_trie_node *n, buffer *buf, int v4)
{
- if (t == NULL)
+ if (n == NULL)
return;
- if (ip4_nonzero(t->accept))
- buffer_print(buf, "%I4/%d{%I4}, ", t->addr, t->plen, t->accept);
+ if (v4)
+ {
+ if (ip4_nonzero(n->v4.accept))
+ buffer_print(buf, "%I4/%d{%I4}, ", n->v4.addr, n->v4.plen, n->v4.accept);
+ }
+ else
+ {
+ if (ip6_nonzero(n->v6.accept))
+ buffer_print(buf, "%I6/%d{%I6}, ", n->v6.addr, n->v6.plen, n->v6.accept);
+ }
- trie_node_format4(t->c[0], buf);
- trie_node_format4(t->c[1], buf);
-}
+ int nlen = v4 ? n->v4.plen : n->v6.plen;
+ uint local = v4 ? n->v4.local : n->v6.local;
-static void
-trie_node_format6(const struct f_trie_node6 *t, buffer *buf)
-{
- if (t == NULL)
- return;
+ for (int i = (nlen ? 0 : 1); i < TRIE_STEP; i++)
+ if (GET_ACCEPT_BIT(n, v4, nlen + i - 1))
+ local &= ~trie_level_mask(1, i);
- if (ip6_nonzero(t->accept))
- buffer_print(buf, "%I6/%d{%I6}, ", t->addr, t->plen, t->accept);
+ for (int pos = 2; local && (pos < (1 << TRIE_STEP)); pos++)
+ if (local & (1u << pos))
+ {
+ int lvl = log2[pos];
+ int plen = nlen + lvl;
+
+ int i;
+ for (i = 0; lvl + i < TRIE_STEP; i++)
+ {
+ uint lmask = trie_level_mask(pos, i);
+
+ if ((local & lmask) != lmask)
+ break;
+
+ local &= ~lmask;
+ }
+
+ uint addr_bits = pos & ((1u << lvl) - 1);
+ uint accept_bits = (1u << i) - 1;
+ int h = plen + i - 1;
+
+ if (v4)
+ {
+ ip4_addr addr = ip4_setbits(n->v4.addr, plen - 1, addr_bits);
+ ip4_addr mask = ip4_setbits(IP4_NONE, h - 1, accept_bits);
+ buffer_print(buf, "%I4/%d{%I4}, ", addr, plen, mask);
+ }
+ else
+ {
+ ip6_addr addr = ip6_setbits(n->v6.addr, plen - 1, addr_bits);
+ ip6_addr mask = ip6_setbits(IP6_NONE, h - 1, accept_bits);
+ buffer_print(buf, "%I6/%d{%I6}, ", addr, plen, mask);
+ }
+ }
- trie_node_format6(t->c[0], buf);
- trie_node_format6(t->c[1], buf);
+ for (int i = 0; i < (1 << TRIE_STEP); i++)
+ trie_node_format(GET_CHILD(n, v4, i), buf, v4);
}
/**
@@ -472,10 +1142,7 @@ trie_format(const struct f_trie *t, buffer *buf)
if (t->zero)
buffer_print(buf, "%I/%d, ", t->ipv4 ? IPA_NONE4 : IPA_NONE6, 0);
- if (t->ipv4)
- trie_node_format4(&t->root.v4, buf);
- else
- trie_node_format6(&t->root.v6, buf);
+ trie_node_format(&t->root, buf, t->ipv4);
if (buf->pos == buf->end)
return;
diff --git a/filter/trie_test.c b/filter/trie_test.c
index b2b36716..dc791280 100644
--- a/filter/trie_test.c
+++ b/filter/trie_test.c
@@ -14,9 +14,12 @@
#include "conf/conf.h"
#define TESTS_NUM 10
-#define PREFIXES_NUM 10
+#define PREFIXES_NUM 32
#define PREFIX_TESTS_NUM 10000
+#define PREFIX_BENCH_NUM 100000000
+#define TRIE_BUFFER_SIZE 1024
+#define TEST_BUFFER_SIZE (1024*1024)
#define BIG_BUFFER_SIZE 10000
/* Wrapping structure for storing f_prefixes structures in list */
@@ -31,146 +34,849 @@ xrandom(u32 max)
return (bt_random() % max);
}
+static inline uint
+get_exp_random(void)
+{
+ uint r, n = 0;
+
+ for (r = bt_random(); r & 1; r = r >> 1)
+ n++;
+
+ return n;
+}
+
static int
-is_prefix_included(list *prefixes, struct f_prefix *needle)
+compare_prefixes(const void *a, const void *b)
{
- struct f_prefix_node *n;
- WALK_LIST(n, *prefixes)
- {
- ip6_addr cmask = ip6_mkmask(MIN(n->prefix.net.pxlen, needle->net.pxlen));
+ return net_compare(&((const struct f_prefix *) a)->net,
+ &((const struct f_prefix *) b)->net);
+}
+
+static inline int
+matching_ip4_nets(const net_addr_ip4 *a, const net_addr_ip4 *b)
+{
+ ip4_addr cmask = ip4_mkmask(MIN(a->pxlen, b->pxlen));
+ return ip4_compare(ip4_and(a->prefix, cmask), ip4_and(b->prefix, cmask)) == 0;
+}
+
+static inline int
+matching_ip6_nets(const net_addr_ip6 *a, const net_addr_ip6 *b)
+{
+ ip6_addr cmask = ip6_mkmask(MIN(a->pxlen, b->pxlen));
+ return ip6_compare(ip6_and(a->prefix, cmask), ip6_and(b->prefix, cmask)) == 0;
+}
- ip6_addr ip = net6_prefix(&n->prefix.net);
- ip6_addr needle_ip = net6_prefix(&needle->net);
+static inline int
+matching_nets(const net_addr *a, const net_addr *b)
+{
+ if (a->type != b->type)
+ return 0;
+
+ return (a->type == NET_IP4) ?
+ matching_ip4_nets((const net_addr_ip4 *) a, (const net_addr_ip4 *) b) :
+ matching_ip6_nets((const net_addr_ip6 *) a, (const net_addr_ip6 *) b);
+}
- 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))
+static int
+is_prefix_included(list *prefixes, const net_addr *needle)
+{
+ struct f_prefix_node *n;
+ WALK_LIST(n, *prefixes)
+ if (matching_nets(&n->prefix.net, needle) &&
+ (n->prefix.lo <= needle->pxlen) && (needle->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);
+ char buf[64];
+ bt_format_net(buf, 64, &n->prefix.net);
+ bt_debug("FOUND %s %d-%d\n", buf, n->prefix.lo, n->prefix.hi);
+
return 1; /* OK */
}
- }
+
return 0; /* FAIL */
}
-static struct f_prefix
-get_random_ip6_prefix(void)
+static void
+get_random_net(net_addr *net, int v6)
{
- 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);
+ if (!v6)
+ {
+ uint pxlen = xrandom(24)+8;
+ ip4_addr ip4 = ip4_from_u32((u32) bt_random());
+ net_fill_ip4(net, ip4_and(ip4, ip4_mkmask(pxlen)), pxlen);
+ }
+ else
+ {
+ uint pxlen = xrandom(120)+8;
+ ip6_addr ip6 = ip6_build(bt_random(), bt_random(), bt_random(), bt_random());
+ net_fill_ip6(net, ip6_and(ip6, ip6_mkmask(pxlen)), pxlen);
+ }
+}
- p.net = *((net_addr*) &net6);
+static void
+get_random_prefix(struct f_prefix *px, int v6, int tight)
+{
+ get_random_net(&px->net, v6);
+
+ if (tight)
+ {
+ px->lo = px->hi = px->net.pxlen;
+ }
+ else if (bt_random() % 2)
+ {
+ px->lo = 0;
+ px->hi = px->net.pxlen;
+ }
+ else
+ {
+ px->lo = px->net.pxlen;
+ px->hi = net_max_prefix_length[px->net.type];
+ }
+}
+
+static void
+get_random_ip4_subnet(net_addr_ip4 *net, const net_addr_ip4 *src, int pxlen)
+{
+ *net = NET_ADDR_IP4(ip4_and(src->prefix, ip4_mkmask(pxlen)), pxlen);
+
+ if (pxlen > src->pxlen)
+ {
+ ip4_addr rnd = ip4_from_u32((u32) bt_random());
+ ip4_addr mask = ip4_xor(ip4_mkmask(src->pxlen), ip4_mkmask(pxlen));
+ net->prefix = ip4_or(net->prefix, ip4_and(rnd, mask));
+ }
+}
+
+static void
+get_random_ip6_subnet(net_addr_ip6 *net, const net_addr_ip6 *src, int pxlen)
+{
+ *net = NET_ADDR_IP6(ip6_and(src->prefix, ip6_mkmask(pxlen)), pxlen);
+
+ if (pxlen > src->pxlen)
+ {
+ ip6_addr rnd = ip6_build(bt_random(), bt_random(), bt_random(), bt_random());
+ ip6_addr mask = ip6_xor(ip6_mkmask(src->pxlen), ip6_mkmask(pxlen));
+ net->prefix = ip6_or(net->prefix, ip6_and(rnd, mask));
+ }
+}
+
+static void
+get_random_subnet(net_addr *net, const net_addr *src, int pxlen)
+{
+ if (src->type == NET_IP4)
+ get_random_ip4_subnet((net_addr_ip4 *) net, (const net_addr_ip4 *) src, pxlen);
+ else
+ get_random_ip6_subnet((net_addr_ip6 *) net, (const net_addr_ip6 *) src, pxlen);
+}
+
+static void
+get_inner_net(net_addr *net, const struct f_prefix *src)
+{
+ int pxlen, step;
if (bt_random() % 2)
{
- p.lo = 0;
- p.hi = p.net.pxlen;
+ step = get_exp_random();
+ step = MIN(step, src->hi - src->lo);
+ pxlen = (bt_random() % 2) ? (src->lo + step) : (src->hi - step);
}
else
+ pxlen = src->lo + bt_random() % (src->hi - src->lo + 1);
+
+ get_random_subnet(net, &src->net, pxlen);
+}
+
+static void
+swap_random_bits_ip4(net_addr_ip4 *net, int num)
+{
+ for (int i = 0; i < num; i++)
{
- p.lo = p.net.pxlen;
- p.hi = net_max_prefix_length[p.net.type];
+ ip4_addr swap = IP4_NONE;
+ ip4_setbit(&swap, bt_random() % net->pxlen);
+ net->prefix = ip4_xor(net->prefix, swap);
}
+}
- return p;
+static void
+swap_random_bits_ip6(net_addr_ip6 *net, int num)
+{
+ for (int i = 0; i < num; i++)
+ {
+ ip6_addr swap = IP6_NONE;
+ ip6_setbit(&swap, bt_random() % net->pxlen);
+ net->prefix = ip6_xor(net->prefix, swap);
+ }
}
static void
-generate_random_ipv6_prefixes(list *prefixes)
+swap_random_bits(net_addr *net, int num)
{
- int i;
- for (i = 0; i < PREFIXES_NUM; i++)
+ if (net->type == NET_IP4)
+ swap_random_bits_ip4((net_addr_ip4 *) net, num);
+ else
+ swap_random_bits_ip6((net_addr_ip6 *) net, num);
+}
+
+static void
+get_outer_net(net_addr *net, const struct f_prefix *src)
+{
+ int pxlen, step;
+ int inside = 0;
+ int max = net_max_prefix_length[src->net.type];
+
+ if ((src->lo > 0) && (bt_random() % 3))
+ {
+ step = 1 + get_exp_random();
+ step = MIN(step, src->lo);
+ pxlen = src->lo - step;
+ }
+ else if ((src->hi < max) && (bt_random() % 2))
{
- struct f_prefix f = get_random_ip6_prefix();
+ step = 1 + get_exp_random();
+ step = MIN(step, max - src->hi);
+ pxlen = src->hi + step;
+ }
+ else
+ {
+ pxlen = src->lo + bt_random() % (src->hi - src->lo + 1);
+ inside = 1;
+ }
- struct f_prefix_node *px = calloc(1, sizeof(struct f_prefix_node));
- px->prefix = f;
+ get_random_subnet(net, &src->net, pxlen);
- 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);
+ /* Perhaps swap some bits in prefix */
+ if ((net->pxlen > 0) && (inside || (bt_random() % 4)))
+ swap_random_bits(net, 1 + get_exp_random());
+}
+
+static list *
+make_random_prefix_list(int num, int v6, int tight)
+{
+ list *prefixes = lp_allocz(tmp_linpool, sizeof(struct f_prefix_node));
+ init_list(prefixes);
+
+ for (int i = 0; i < num; i++)
+ {
+ struct f_prefix_node *px = lp_allocz(tmp_linpool, sizeof(struct f_prefix_node));
+ get_random_prefix(&px->prefix, v6, tight);
add_tail(prefixes, &px->n);
+
+ char buf[64];
+ bt_format_net(buf, 64, &px->prefix.net);
+ bt_debug("ADD %s{%d,%d}\n", buf, px->prefix.lo, px->prefix.hi);
+ }
+
+ return prefixes;
+}
+
+static struct f_trie *
+make_trie_from_prefix_list(list *prefixes)
+{
+ struct f_trie *trie = f_new_trie(tmp_linpool, 0);
+
+ struct f_prefix_node *n;
+ WALK_LIST(n, *prefixes)
+ trie_add_prefix(trie, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+
+ return trie;
+}
+
+/*
+ * Read sequence of prefixes from file handle and return prefix list.
+ * Each prefix is on one line, sequence terminated by empty line or eof.
+ * Arg @plus means prefix should include all longer ones.
+ */
+static list *
+read_prefix_list(FILE *f, int v6, int plus)
+{
+ ASSERT(!v6);
+
+ uint a0, a1, a2, a3, pl;
+ char s[32];
+ int n;
+
+ list *pxlist = lp_allocz(tmp_linpool, sizeof(struct f_prefix_node));
+ init_list(pxlist);
+
+ errno = 0;
+ while (fgets(s, 32, f))
+ {
+ if (s[0] == '\n')
+ return pxlist;
+
+ n = sscanf(s, "%u.%u.%u.%u/%u", &a0, &a1, &a2, &a3, &pl);
+
+ if (n != 5)
+ bt_abort_msg("Invalid content of trie_data");
+
+ struct f_prefix_node *px = lp_allocz(tmp_linpool, sizeof(struct f_prefix_node));
+ net_fill_ip4(&px->prefix.net, ip4_build(a0, a1, a2, a3), pl);
+ px->prefix.lo = pl;
+ px->prefix.hi = plus ? IP4_MAX_PREFIX_LENGTH : pl;
+ add_tail(pxlist, &px->n);
+
+ char buf[64];
+ bt_format_net(buf, 64, &px->prefix.net);
+ bt_debug("ADD %s{%d,%d}\n", buf, px->prefix.lo, px->prefix.hi);
}
+
+ bt_syscall(errno, "fgets()");
+ return EMPTY_LIST(*pxlist) ? NULL : pxlist;
}
+/*
+ * Open file, read multiple sequences of prefixes from it. Fill @data with
+ * prefix lists and @trie with generated tries. Return number of sequences /
+ * tries. Use separate linpool @lp0 for prefix lists and @lp1 for tries.
+ * Arg @plus means prefix should include all longer ones.
+ */
static int
-t_match_net(void)
+read_prefix_file(const char *filename, int plus,
+ list *data[], struct f_trie *trie[])
+{
+ FILE *f = fopen(filename, "r");
+ bt_syscall(!f, "fopen(%s)", filename);
+
+ int n = 0;
+ list *pxlist;
+ while (pxlist = read_prefix_list(f, 0, plus))
+ {
+ data[n] = pxlist;
+ trie[n] = make_trie_from_prefix_list(pxlist);
+ bt_debug("NEXT\n");
+ n++;
+ }
+
+ fclose(f);
+ bt_debug("DONE reading %d tries\n", n);
+
+ return n;
+}
+
+/*
+ * Select random subset of @dn prefixes from prefix list @src of length @sn,
+ * and store them to buffer @dst (of size @dn). Prefixes may be chosen multiple
+ * times. Randomize order of prefixes in @dst buffer.
+ */
+static void
+select_random_prefix_subset(list *src[], net_addr dst[], int sn, int dn)
+{
+ int pn = 0;
+
+ if (!dn)
+ return;
+
+ /* Compute total prefix number */
+ for (int i = 0; i < sn; i++)
+ pn += list_length(src[i]);
+
+ /* Change of selecting a prefix */
+ int rnd = (pn / dn) + 10;
+ int n = 0;
+
+ /* Iterate indefinitely over src array */
+ for (int i = 0; 1; i++, i = (i < sn) ? i : 0)
+ {
+ struct f_prefix_node *px;
+ WALK_LIST(px, *src[i])
+ {
+ if (xrandom(rnd) != 0)
+ continue;
+
+ net_copy(&dst[n], &px->prefix.net);
+ n++;
+
+ /* We have enough */
+ if (n == dn)
+ goto done;
+ }
+ }
+
+done:
+ /* Shuffle networks */
+ for (int i = 0; i < dn; i++)
+ {
+ int j = xrandom(dn);
+
+ if (i == j)
+ continue;
+
+ net_addr tmp;
+ net_copy(&tmp, &dst[i]);
+ net_copy(&dst[i], &dst[j]);
+ net_copy(&dst[j], &tmp);
+ }
+}
+
+/* Fill @dst buffer with @dn randomly generated /32 prefixes */
+static void
+make_random_addresses(net_addr dst[], int dn)
+{
+ for (int i = 0; i < dn; i++)
+ net_fill_ip4(&dst[i], ip4_from_u32((u32) bt_random()), IP4_MAX_PREFIX_LENGTH);
+}
+
+static void
+test_match_net(list *prefixes, struct f_trie *trie, const net_addr *net)
+{
+ char buf[64];
+ bt_format_net(buf, 64, net);
+ bt_debug("TEST %s\n", buf);
+
+ int should_be = is_prefix_included(prefixes, net);
+ int is_there = trie_match_net(trie, net);
+
+ bt_assert_msg(should_be == is_there, "Prefix %s %s match", buf,
+ (should_be ? "should" : "should not"));
+}
+
+static int
+t_match_random_net(void)
{
bt_bird_init();
bt_config_parse(BT_CONFIG_SIMPLE);
- uint round;
- for (round = 0; round < TESTS_NUM; round++)
+ int v6 = 0;
+ for (int 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, 0);
+ list *prefixes = make_random_prefix_list(PREFIXES_NUM, v6, 0);
+ struct f_trie *trie = make_trie_from_prefix_list(prefixes);
- generate_random_ipv6_prefixes(&prefixes);
- struct f_prefix_node *n;
- WALK_LIST(n, prefixes)
+ for (int i = 0; i < PREFIX_TESTS_NUM; i++)
{
- trie_add_prefix(trie, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+ net_addr net;
+ get_random_net(&net, v6);
+ test_match_net(prefixes, trie, &net);
}
- int i;
- for (i = 0; i < PREFIX_TESTS_NUM; i++)
+ v6 = !v6;
+ tmp_flush();
+ }
+
+ bt_bird_cleanup();
+ return 1;
+}
+
+static int
+t_match_inner_net(void)
+{
+ bt_bird_init();
+ bt_config_parse(BT_CONFIG_SIMPLE);
+
+ int v6 = 0;
+ for (int round = 0; round < TESTS_NUM; round++)
+ {
+ list *prefixes = make_random_prefix_list(PREFIXES_NUM, v6, 0);
+ struct f_trie *trie = make_trie_from_prefix_list(prefixes);
+
+ struct f_prefix_node *n = HEAD(*prefixes);
+ for (int 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);
+ net_addr net;
+ get_inner_net(&net, &n->prefix);
+ test_match_net(prefixes, trie, &net);
- 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"));
+ n = NODE_VALID(NODE_NEXT(n)) ? NODE_NEXT(n) : HEAD(*prefixes);
}
- struct f_prefix_node *nxt;
- WALK_LIST_DELSAFE(n, nxt, prefixes)
+ v6 = !v6;
+ tmp_flush();
+ }
+
+ bt_bird_cleanup();
+ return 1;
+}
+
+static int
+t_match_outer_net(void)
+{
+ bt_bird_init();
+ bt_config_parse(BT_CONFIG_SIMPLE);
+
+ int v6 = 0;
+ for (int round = 0; round < TESTS_NUM; round++)
+ {
+ list *prefixes = make_random_prefix_list(PREFIXES_NUM, v6, 0);
+ struct f_trie *trie = make_trie_from_prefix_list(prefixes);
+
+ struct f_prefix_node *n = HEAD(*prefixes);
+ for (int i = 0; i < PREFIX_TESTS_NUM; i++)
{
- free(n);
+ net_addr net;
+ get_outer_net(&net, &n->prefix);
+ test_match_net(prefixes, trie, &net);
+
+ n = NODE_VALID(NODE_NEXT(n)) ? NODE_NEXT(n) : HEAD(*prefixes);
}
+
+ v6 = !v6;
+ tmp_flush();
}
+ v6 = !v6;
+ bt_bird_cleanup();
+ return 1;
+}
+
+/*
+ * Read prefixes from @filename, build set of tries, prepare test data and do
+ * PREFIX_BENCH_NUM trie lookups. With @plus = 0, use random subset of known
+ * prefixes as test data, with @plus = 1, use randomly generated /32 prefixes
+ * as test data.
+ */
+static int
+benchmark_trie_dataset(const char *filename, int plus)
+{
+ int n = 0;
+ list *data[TRIE_BUFFER_SIZE];
+ struct f_trie *trie[TRIE_BUFFER_SIZE];
+ net_addr *nets;
+
+ bt_reset_suite_case_timer();
+ bt_log_suite_case_result(1, "Reading %s", filename, n);
+ n = read_prefix_file(filename, plus, data, trie);
+ bt_log_suite_case_result(1, "Read prefix data, %d lists, ", n);
+
+ size_t trie_size = rmemsize(tmp_linpool).effective * 1000 / (1024*1024);
+ bt_log_suite_case_result(1, "Trie size %u.%03u MB",
+ (uint) (trie_size / 1000), (uint) (trie_size % 1000));
+
+ int t = PREFIX_BENCH_NUM / n;
+ int tb = MIN(t, TEST_BUFFER_SIZE);
+ nets = tmp_alloc(tb * sizeof(net_addr));
+
+ if (!plus)
+ select_random_prefix_subset(data, nets, n, tb);
+ else
+ make_random_addresses(nets, tb);
+
+ bt_log_suite_case_result(1, "Make test data, %d (%d) tests", t, tb);
+ bt_reset_suite_case_timer();
+
+ /*
+ int match = 0;
+ for (int i = 0; i < t; i++)
+ for (int j = 0; j < n; j++)
+ test_match_net(data[j], trie[j], &nets[i]);
+ */
+
+ int match = 0;
+ for (int i = 0; i < t; i++)
+ for (int j = 0; j < n; j++)
+ if (trie_match_net(trie[j], &nets[i % TEST_BUFFER_SIZE]))
+ match++;
+
+ bt_log_suite_case_result(1, "Matching done, %d / %d matches", match, t * n);
+
+ tmp_flush();
+ return 1;
+}
+
+static int UNUSED
+t_bench_trie_datasets_subset(void)
+{
+ bt_bird_init();
+ bt_config_parse(BT_CONFIG_SIMPLE);
+
+ /* Specific datasets, not included */
+ benchmark_trie_dataset("trie-data-bgp-1", 0);
+ benchmark_trie_dataset("trie-data-bgp-10", 0);
+ benchmark_trie_dataset("trie-data-bgp-100", 0);
+ benchmark_trie_dataset("trie-data-bgp-1000", 0);
+
bt_bird_cleanup();
+
return 1;
}
+static int UNUSED
+t_bench_trie_datasets_random(void)
+{
+ bt_bird_init();
+ bt_config_parse(BT_CONFIG_SIMPLE);
+
+ /* Specific datasets, not included */
+ benchmark_trie_dataset("trie-data-bgp-1", 1);
+ benchmark_trie_dataset("trie-data-bgp-10", 1);
+ benchmark_trie_dataset("trie-data-bgp-100", 1);
+ benchmark_trie_dataset("trie-data-bgp-1000", 1);
+
+ 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++)
+ int v6 = 0;
+ for (int round = 0; round < TESTS_NUM*4; round++)
{
- struct f_trie * trie1 = f_new_trie(config->mem, 0);
- struct f_trie * trie2 = f_new_trie(config->mem, 0);
+ list *prefixes = make_random_prefix_list(100 * PREFIXES_NUM, v6, 0);
+ struct f_trie *trie1 = f_new_trie(tmp_linpool, 0);
+ struct f_trie *trie2 = f_new_trie(tmp_linpool, 0);
- 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));
+
+ v6 = !v6;
+ tmp_flush();
+ }
+
+ bt_bird_cleanup();
+ return 1;
+}
+
+static inline void
+log_networks(const net_addr *a, const net_addr *b)
+{
+ if (bt_verbose >= BT_VERBOSE_ABSOLUTELY_ALL)
+ {
+ char buf0[64];
+ char buf1[64];
+ bt_format_net(buf0, 64, a);
+ bt_format_net(buf1, 64, b);
+ bt_debug("Found %s expected %s\n", buf0, buf1);
+ }
+}
+
+static int
+t_trie_walk(void)
+{
+ bt_bird_init();
+ bt_config_parse(BT_CONFIG_SIMPLE);
+
+ for (int round = 0; round < TESTS_NUM*8; round++)
+ {
+ int level = round / TESTS_NUM;
+ int v6 = level % 2;
+ int num = PREFIXES_NUM * (int[]){1, 10, 100, 1000}[level / 2];
+ int pos = 0, end = 0;
+ list *prefixes = make_random_prefix_list(num, v6, 1);
+ struct f_trie *trie = make_trie_from_prefix_list(prefixes);
+ struct f_prefix *pxset = malloc((num + 1) * sizeof(struct f_prefix));
struct f_prefix_node *n;
- WALK_LIST(n, prefixes)
+ WALK_LIST(n, *prefixes)
+ pxset[pos++] = n->prefix;
+ memset(&pxset[pos], 0, sizeof (struct f_prefix));
+
+ qsort(pxset, num, sizeof(struct f_prefix), compare_prefixes);
+
+
+ /* Full walk */
+ bt_debug("Full walk (round %d, %d nets)\n", round, num);
+
+ pos = 0;
+ uint pxc = 0;
+ TRIE_WALK(trie, net, NULL)
{
- trie_add_prefix(trie1, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+ log_networks(&net, &pxset[pos].net);
+ bt_assert(net_equal(&net, &pxset[pos].net));
+
+ /* Skip possible duplicates */
+ while (net_equal(&pxset[pos].net, &pxset[pos + 1].net))
+ pos++;
+
+ pos++;
+ pxc++;
}
- WALK_LIST_BACKWARDS(n, prefixes)
+ TRIE_WALK_END;
+
+ bt_assert(pos == num);
+ bt_assert(pxc == trie->prefix_count);
+ bt_debug("Full walk done\n");
+
+
+ /* Prepare net for subnet walk - start with random prefix */
+ pos = bt_random() % num;
+ end = pos + (int[]){2, 2, 3, 4}[level / 2];
+ end = MIN(end, num);
+
+ struct f_prefix from = pxset[pos];
+
+ /* Find a common superprefix to several subsequent prefixes */
+ for (; pos < end; pos++)
{
- trie_add_prefix(trie2, &n->prefix.net, n->prefix.lo, n->prefix.hi);
+ if (net_equal(&from.net, &pxset[pos].net))
+ continue;
+
+ int common = !v6 ?
+ ip4_pxlen(net4_prefix(&from.net), net4_prefix(&pxset[pos].net)) :
+ ip6_pxlen(net6_prefix(&from.net), net6_prefix(&pxset[pos].net));
+ from.net.pxlen = MIN(from.net.pxlen, common);
+
+ if (!v6)
+ ((net_addr_ip4 *) &from.net)->prefix =
+ ip4_and(net4_prefix(&from.net), net4_prefix(&pxset[pos].net));
+ else
+ ((net_addr_ip6 *) &from.net)->prefix =
+ ip6_and(net6_prefix(&from.net), net6_prefix(&pxset[pos].net));
}
- bt_assert(trie_same(trie1, trie2));
+ /* Fix irrelevant bits */
+ if (!v6)
+ ((net_addr_ip4 *) &from.net)->prefix =
+ ip4_and(net4_prefix(&from.net), ip4_mkmask(net4_pxlen(&from.net)));
+ else
+ ((net_addr_ip6 *) &from.net)->prefix =
+ ip6_and(net6_prefix(&from.net), ip6_mkmask(net6_pxlen(&from.net)));
+
+
+ /* Find initial position for final prefix */
+ for (pos = 0; pos < num; pos++)
+ if (compare_prefixes(&pxset[pos], &from) >= 0)
+ break;
+
+ int p0 = pos;
+ char buf0[64];
+ bt_format_net(buf0, 64, &from.net);
+ bt_debug("Subnet walk for %s (round %d, %d nets)\n", buf0, round, num);
+
+ /* Subnet walk */
+ TRIE_WALK(trie, net, &from.net)
+ {
+ log_networks(&net, &pxset[pos].net);
+ bt_assert(net_equal(&net, &pxset[pos].net));
+ bt_assert(net_in_netX(&net, &from.net));
+
+ /* Skip possible duplicates */
+ while (net_equal(&pxset[pos].net, &pxset[pos + 1].net))
+ pos++;
- struct f_prefix_node *nxt;
- WALK_LIST_DELSAFE(n, nxt, prefixes)
+ pos++;
+ }
+ TRIE_WALK_END;
+
+ bt_assert((pos == num) || !net_in_netX(&pxset[pos].net, &from.net));
+ bt_debug("Subnet walk done for %s (found %d nets)\n", buf0, pos - p0);
+
+ tmp_flush();
+ }
+
+ bt_bird_cleanup();
+ return 1;
+}
+
+static int
+find_covering_nets(struct f_prefix *prefixes, int num, const net_addr *net, net_addr *found)
+{
+ struct f_prefix key;
+ net_addr *n = &key.net;
+ int found_num = 0;
+
+ net_copy(n, net);
+
+ while (1)
+ {
+ struct f_prefix *px =
+ bsearch(&key, prefixes, num, sizeof(struct f_prefix), compare_prefixes);
+
+ if (px)
+ {
+ net_copy(&found[found_num], n);
+ found_num++;
+ }
+
+ if (n->pxlen == 0)
+ return found_num;
+
+ n->pxlen--;
+
+ if (n->type == NET_IP4)
+ ip4_clrbit(&((net_addr_ip4 *) n)->prefix, n->pxlen);
+ else
+ ip6_clrbit(&((net_addr_ip6 *) n)->prefix, n->pxlen);
+ }
+}
+
+static int
+t_trie_walk_to_root(void)
+{
+ bt_bird_init();
+ bt_config_parse(BT_CONFIG_SIMPLE);
+
+ for (int round = 0; round < TESTS_NUM * 4; round++)
+ {
+ int level = round / TESTS_NUM;
+ int v6 = level % 2;
+ int num = PREFIXES_NUM * (int[]){32, 512}[level / 2];
+ int pos = 0;
+ int st = 0, sn = 0, sm = 0;
+
+ list *prefixes = make_random_prefix_list(num, v6, 1);
+ struct f_trie *trie = make_trie_from_prefix_list(prefixes);
+ struct f_prefix *pxset = malloc((num + 1) * sizeof(struct f_prefix));
+
+ struct f_prefix_node *pxn;
+ WALK_LIST(pxn, *prefixes)
+ pxset[pos++] = pxn->prefix;
+ memset(&pxset[pos], 0, sizeof (struct f_prefix));
+
+ qsort(pxset, num, sizeof(struct f_prefix), compare_prefixes);
+
+ int i;
+ for (i = 0; i < (PREFIX_TESTS_NUM / 10); i++)
{
- free(n);
+ net_addr from;
+ get_random_net(&from, v6);
+
+ net_addr found[129];
+ int found_num = find_covering_nets(pxset, num, &from, found);
+ int n = 0;
+
+ if (bt_verbose >= BT_VERBOSE_ABSOLUTELY_ALL)
+ {
+ char buf[64];
+ bt_format_net(buf, 64, &from);
+ bt_debug("Lookup for %s (expect %d)\n", buf, found_num);
+ }
+
+ /* Walk to root, separate for IPv4 and IPv6 */
+ if (!v6)
+ {
+ TRIE_WALK_TO_ROOT_IP4(trie, (net_addr_ip4 *) &from, net)
+ {
+ log_networks((net_addr *) &net, &found[n]);
+ bt_assert((n < found_num) && net_equal((net_addr *) &net, &found[n]));
+ n++;
+ }
+ TRIE_WALK_TO_ROOT_END;
+ }
+ else
+ {
+ TRIE_WALK_TO_ROOT_IP6(trie, (net_addr_ip6 *) &from, net)
+ {
+ log_networks((net_addr *) &net, &found[n]);
+ bt_assert((n < found_num) && net_equal((net_addr *) &net, &found[n]));
+ n++;
+ }
+ TRIE_WALK_TO_ROOT_END;
+ }
+
+ bt_assert(n == found_num);
+
+ /* Stats */
+ st += n;
+ sn += !!n;
+ sm = MAX(sm, n);
}
+
+ bt_debug("Success in %d / %d, sum %d, max %d\n", sn, i, st, sm);
+
+ tmp_flush();
}
+ bt_bird_cleanup();
return 1;
}
@@ -179,8 +885,15 @@ main(int argc, char *argv[])
{
bt_init(argc, argv);
- bt_test_suite(t_match_net, "Testing random prefix matching");
+ bt_test_suite(t_match_random_net, "Testing random prefix matching");
+ bt_test_suite(t_match_inner_net, "Testing random inner prefix matching");
+ bt_test_suite(t_match_outer_net, "Testing random outer prefix matching");
bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward.");
+ bt_test_suite(t_trie_walk, "Testing TRIE_WALK() on random tries");
+ bt_test_suite(t_trie_walk_to_root, "Testing TRIE_WALK_TO_ROOT() on random tries");
+
+ // bt_test_suite(t_bench_trie_datasets_subset, "Benchmark tries from datasets by random subset of nets");
+ // bt_test_suite(t_bench_trie_datasets_random, "Benchmark tries from datasets by generated addresses");
return bt_exit_value();
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-24 13:24:45 +0000