diff options
| -rw-r--r-- | conf/confbase.Y | 1 | ||||
| -rw-r--r-- | doc/bird.sgml | 33 | ||||
| -rw-r--r-- | filter/Doc | 1 | ||||
| -rw-r--r-- | filter/Makefile | 2 | ||||
| -rw-r--r-- | filter/config.Y | 69 | ||||
| -rw-r--r-- | filter/filter.c | 76 | ||||
| -rw-r--r-- | filter/filter.h | 21 | ||||
| -rw-r--r-- | filter/test.conf | 38 | ||||
| -rw-r--r-- | filter/test6.conf | 182 | ||||
| -rw-r--r-- | filter/trie.c | 325 | ||||
| -rw-r--r-- | lib/bitops.c | 21 | ||||
| -rw-r--r-- | lib/bitops.h | 2 | ||||
| -rw-r--r-- | lib/ipv4.h | 10 | ||||
| -rw-r--r-- | lib/ipv6.h | 20 |
14 files changed, 743 insertions, 58 deletions
diff --git a/conf/confbase.Y b/conf/confbase.Y index e6401f47..43854623 100644 --- a/conf/confbase.Y +++ b/conf/confbase.Y @@ -34,6 +34,7 @@ CF_DECLS struct f_inst *x; struct filter *f; struct f_tree *e; + struct f_trie *trie; struct f_val v; struct f_path_mask *h; struct password_item *p; diff --git a/doc/bird.sgml b/doc/bird.sgml index a7cda823..21141512 100644 --- a/doc/bird.sgml +++ b/doc/bird.sgml @@ -508,12 +508,33 @@ incompatible with each other (that is to prevent you from shooting in the foot). Filters recognize four types of sets. Sets are similar to strings: you can pass them around but you can't modify them. Literals of type <cf>set int</cf> look like <cf> [ 1, 2, 5..7 ]</cf>. As you can see, both simple values and ranges are permitted in - sets. Sets of prefixes are special: you can specify which prefix lengths should match them by - using <cf>[ 1.0.0.0/8+, 2.0.0.0/8-, 3.0.0.0/8{5,6} ]</cf>. <cf>3.0.0.0/8{5,6}</cf> matches - prefixes <cf/3.X.X.X/ whose prefix length is 5 to 6. <cf><m>address</m>/<m>num</m>+</cf> is a shorthand for <cf><m>address</m>/{0,<m/num/}</cf>, - <cf><m>address</m>/<m/num/-</cf> is a shorthand for <cf><m>address</m>/{0,<m/num-1/}</cf>. For example, - <cf>1.2.0.0/16 ˜ [ 1.0.0.0/8{ 15 , 17 } ]</cf> is true, but - <cf>1.0.0.0/8 ˜ [ 1.0.0.0/8- ]</cf> is false. + sets. + + Sets of prefixes are special: their literals does not allow ranges, but allows + prefix patterns that are written as <cf><M>ipaddress</M>/<M>pxlen</M>{<M>low</M>,<M>high</M>}</cf>. + Prefix <cf><m>ip1</m>/<m>len1</m></cf> matches prefix pattern <cf><m>ip2</m>/<m>len2</m>{<m>l</m>, <m>h</m>}</cf> iff + the first <cf>min(len1, len2)</cf> bits of <cf/ip1/> and <cf/ip2/ are identical and <cf>len1 ≤ ip1 ≤ len2</cf>. + A valid prefix pattern has to satisfy <cf/low ≤ high/, but <cf/pxlen> is not constrained by <cf/low/ + or <cf/high/. Obviously, a prefix matches a prefix set literal iff it matches any prefix pattern in the + prefix set literal. + + There are also two shorthands for prefix patterns: <cf><m>address</m>/<m/len/+</cf> is a shorthand for + <cf><m>address</m>/<m/len/{<m/len/,<m/maxlen/}</cf> (where <cf><m>maxlen</m></c> is 32 for IPv4 and 128 for IPv6), + that means prefix <cf><m>address</m>/<m/len/</cf> and all its subprefixes. <cf><m>address</m>/<m/len/-</cf> + is a shorthand for <cf><m>address</m>/<m/len/{0,<m/len/}</cf>, that means prefix <cf><m>address</m>/<m/len/</cf> + and all its superprefixes (prefixes that contain it). + + For example, <cf>[ 1.0.0.0/8, 2.0.0.0/8+, 3.0.0.0/8-, 4.0.0.0/8{16,24} ]</cf> matches + prefix <cf>1.0.0.0/8</cf>, all subprefixes of <cf>2.0.0.0/8</cf>, all superprefixes of <cf>3.0.0.0/8</cf> and prefixes + <cf/4.X.X.X/ whose prefix length is 16 to 24. <cf>[ 0.0.0.0/0{20,24} ]</cf> matches all prefixes (regardless of + IP address) whose prefix length is 20 to 24, <cf>[ 1.2.3.4/32- ]</cf> matches any prefix that contains IP address + <cf>1.2.3.4</cf>. <cf>1.2.0.0/16 ˜ [ 1.0.0.0/8{ 15 , 17 } ]</cf> is true, + but <cf>1.0.0.0/16 ˜ [ 1.0.0.0/8- ]</cf> is false. + + Cisco-style patterns like <cf>10.0.0.0/8 ge 16 le 24</cf> can be expressed + in Bird as <cf>10.0.0.0/8{16,24}</cf>, <cf>192.168.0.0/16 le 24</cf> as + <cf>192.168.0.0/16{16,24}</cf> and <cf>192.168.0.0/16 ge 24</cf> as + <cf>192.168.0.0/16{24,32}</cf>. <tag/enum/ Enumeration types are fixed sets of possibilities. You can't define your own @@ -1,3 +1,4 @@ H Filters S filter.c S tree.c +S trie.c
\ No newline at end of file diff --git a/filter/Makefile b/filter/Makefile index f41d7a3d..2de598da 100644 --- a/filter/Makefile +++ b/filter/Makefile @@ -1,4 +1,4 @@ -source=f-util.c filter.c tree.c +source=f-util.c filter.c tree.c trie.c root-rel=../ dir-name=filter diff --git a/filter/config.Y b/filter/config.Y index 688464d9..b6a0f470 100644 --- a/filter/config.Y +++ b/filter/config.Y @@ -36,6 +36,7 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN, %type <f> filter filter_body where_filter %type <i> type break_command pair %type <e> set_item set_items switch_body +%type <trie> fprefix_set %type <v> set_atom fprefix fprefix_s fipa %type <s> decls declsn one_decl function_params %type <h> bgp_path bgp_path_tail1 bgp_path_tail2 @@ -69,12 +70,20 @@ type: | CLIST { $$ = T_CLIST; } | type SET { switch ($1) { + case T_INT: + case T_IP: + case T_PAIR: + $$ = T_SET; + break; + + case T_PREFIX: + $$ = T_PREFIX_SET; + break; + default: cf_error( "You can't create sets of this type." ); - case T_INT: case T_IP: case T_PREFIX: case T_PAIR: ; - } - $$ = $1 | T_SET; } + } ; one_decl: @@ -201,20 +210,6 @@ pair: /* * Complex types, their bison value is struct f_val */ -fprefix_s: - IPA '/' NUM %prec '/' { - if (!ip_is_prefix($1, $3)) cf_error("Invalid network prefix: %I/%d.", $1, $3); - $$.type = T_PREFIX; $$.val.px.ip = $1; $$.val.px.len = $3; - } - ; - -fprefix: - fprefix_s { $$ = $1; } - | fprefix_s '+' { $$ = $1; $$.val.px.len |= LEN_PLUS; } - | fprefix_s '-' { $$ = $1; $$.val.px.len |= LEN_MINUS; } - | fprefix_s '{' NUM ',' NUM '}' { $$ = $1; $$.val.px.len |= LEN_RANGE | ($3 << 16) | ($5 << 8); } - ; - fipa: IPA %prec PREFIX_DUMMY { $$.type = T_IP; $$.val.px.ip = $1; } ; @@ -223,7 +218,6 @@ set_atom: NUM { $$.type = T_INT; $$.val.i = $1; } | pair { $$.type = T_PAIR; $$.val.i = $1; } | fipa { $$ = $1; } - | fprefix { $$ = $1; } | ENUM { $$.type = $1 >> 16; $$.val.i = $1 & 0xffff; } ; @@ -231,18 +225,12 @@ set_item: set_atom { $$ = f_new_tree(); $$->from = $1; - if ($1.type != T_PREFIX) - $$->to = $1; - else { - $$->to = $1; - $$->to.val.px.ip = ipa_or( $$->to.val.px.ip, ipa_not( ipa_mkmask( $$->to.val.px.len ) )); - } + $$->to = $1; } | set_atom '.' '.' set_atom { $$ = f_new_tree(); $$->from = $1; $$->to = $4; - if (($1.type == T_PREFIX) || ($4.type == T_PREFIX)) cf_error( "You can't use prefixes for range." ); } ; @@ -251,6 +239,28 @@ set_items: | set_items ',' set_item { $$ = $3; $$->left = $1; } ; +fprefix_s: + IPA '/' NUM %prec '/' { + if (($3 < 0) || ($3 > MAX_PREFIX_LENGTH) || !ip_is_prefix($1, $3)) cf_error("Invalid network prefix: %I/%d.", $1, $3); + $$.type = T_PREFIX; $$.val.px.ip = $1; $$.val.px.len = $3; + } + ; + +fprefix: + fprefix_s { $$ = $1; } + | fprefix_s '+' { $$ = $1; $$.val.px.len |= LEN_PLUS; } + | fprefix_s '-' { $$ = $1; $$.val.px.len |= LEN_MINUS; } + | fprefix_s '{' NUM ',' NUM '}' { + if (! ((0 <= $3) && ($3 <= $5) && ($5 <= MAX_PREFIX_LENGTH))) cf_error("Invalid prefix pattern range: {%d, %d}.", $3, $5); + $$ = $1; $$.val.px.len |= LEN_RANGE | ($3 << 16) | ($5 << 8); + } + ; + +fprefix_set: + fprefix { $$ = f_new_trie(); trie_add_prefix($$, &($1.val.px)); } + | fprefix_set ',' fprefix { $$ = $1; trie_add_prefix($$, &($3.val.px)); } + ; + switch_body: /* EMPTY */ { $$ = NULL; } | set_item ':' cmds switch_body { $$ = $1; @@ -294,6 +304,7 @@ constant: | fipa { NEW_F_VAL; $$ = f_new_inst(); $$->code = 'C'; $$->a1.p = val; *val = $1; } | fprefix_s {NEW_F_VAL; $$ = f_new_inst(); $$->code = 'C'; $$->a1.p = val; *val = $1; } | '[' set_items ']' { DBG( "We've got a set here..." ); $$ = f_new_inst(); $$->code = 'c'; $$->aux = T_SET; $$->a2.p = build_tree($2); DBG( "ook\n" ); } + | '[' fprefix_set ']' { $$ = f_new_inst(); $$->code = 'c'; $$->aux = T_PREFIX_SET; $$->a2.p = $2; } | ENUM { $$ = f_new_inst(); $$->code = 'c'; $$->aux = $1 >> 16; $$->a2.i = $1 & 0xffff; } | bgp_path { NEW_F_VAL; $$ = f_new_inst(); $$->code = 'C'; val->type = T_PATH_MASK; val->val.path_mask = $1; $$->a1.p = val; } ; @@ -374,12 +385,16 @@ term: case SYM_IPA: { NEW_F_VAL; $$ = f_new_inst(); $$->code = 'C'; $$->a1.p = val; val->type = T_IP; val->val.px.ip = * (ip_addr *) ($1->def); } break; + case SYM_VARIABLE | T_BOOL: case SYM_VARIABLE | T_INT: case SYM_VARIABLE | T_PAIR: - case SYM_VARIABLE | T_PREFIX: + case SYM_VARIABLE | T_STRING: case SYM_VARIABLE | T_IP: - case SYM_VARIABLE | T_PATH_MASK: + case SYM_VARIABLE | T_PREFIX: + case SYM_VARIABLE | T_PREFIX_SET: + case SYM_VARIABLE | T_SET: case SYM_VARIABLE | T_PATH: + case SYM_VARIABLE | T_PATH_MASK: case SYM_VARIABLE | T_CLIST: $$->code = 'C'; $$->a1.p = $1->def; diff --git a/filter/filter.c b/filter/filter.c index 623ab291..2e13c752 100644 --- a/filter/filter.c +++ b/filter/filter.c @@ -145,6 +145,25 @@ val_compare(struct f_val v1, struct f_val v2) } } + +void +f_prefix_get_bounds(struct f_prefix *px, int *l, int *h) +{ + *l = *h = px->len & LEN_MASK; + + if (px->len & LEN_MINUS) + *l = 0; + + else if (px->len & LEN_PLUS) + *h = MAX_PREFIX_LENGTH; + + else if (px->len & LEN_RANGE) + { + *l = 0xff & (px->len >> 16); + *h = 0xff & (px->len >> 8); + } +} + /* * val_simple_in_range - check if @v1 ~ @v2 for everything except sets */ @@ -162,21 +181,21 @@ val_simple_in_range(struct f_val v1, struct f_val v2) return !(ipa_compare(ipa_and(v2.val.px.ip, ipa_mkmask(v2.val.px.len)), ipa_and(v1.val.px.ip, ipa_mkmask(v2.val.px.len)))); if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX)) { - ip_addr mask; + if (v1.val.px.len & (LEN_PLUS | LEN_MINUS | LEN_RANGE)) return CMP_ERROR; - mask = ipa_mkmask( v2.val.px.len & LEN_MASK ); + + int p1 = v1.val.px.len & LEN_MASK; + int p2 = v2.val.px.len & LEN_MASK; + ip_addr mask = ipa_mkmask(MIN(p1, p2)); + if (ipa_compare(ipa_and(v2.val.px.ip, mask), ipa_and(v1.val.px.ip, mask))) return 0; - if ((v2.val.px.len & LEN_MINUS) && (v1.val.px.len <= (v2.val.px.len & LEN_MASK))) - return 0; - if ((v2.val.px.len & LEN_PLUS) && (v1.val.px.len < (v2.val.px.len & LEN_MASK))) - return 0; - if ((v2.val.px.len & LEN_RANGE) && ((v1.val.px.len < (0xff & (v2.val.px.len >> 16))) - || (v1.val.px.len > (0xff & (v2.val.px.len >> 8))))) - return 0; - return 1; + int l, h; + f_prefix_get_bounds(&v2.val.px, &l, &h); + + return ((l <= v1.val.px.len) && (v1.val.px.len <= h)); } return CMP_ERROR; } @@ -199,6 +218,9 @@ val_in_range(struct f_val v1, struct f_val v2) if (res != CMP_ERROR) return res; + if ((v1.type == T_PREFIX) && (v2.type == T_PREFIX_SET)) + return trie_match_prefix(v2.val.ti, &v1.val.px); + if (v2.type == T_SET) switch (v1.type) { case T_ENUM: @@ -248,6 +270,7 @@ val_print(struct f_val v) case T_IP: PRINTF( "%I", v.val.px.ip ); break; case T_PREFIX: PRINTF( "%I/%d", v.val.px.ip, v.val.px.len ); break; case T_PAIR: PRINTF( "(%d,%d)", v.val.i >> 16, v.val.i & 0xffff ); break; + case T_PREFIX_SET: trie_print(v.val.ti, buf, 2040); break; case T_SET: tree_print( v.val.t ); PRINTF( "\n" ); break; case T_ENUM: PRINTF( "(enum %x)%d", v.type, v.val.i ); break; case T_PATH: as_path_format(v.val.ad, buf2, 1020); PRINTF( "(path %s)", buf2 ); break; @@ -430,13 +453,17 @@ interpret(struct f_inst *what) switch (res.type = v2.type) { case T_VOID: runtime( "Can't assign void values" ); case T_ENUM: - case T_INT: - case T_IP: - case T_PREFIX: - case T_PAIR: + case T_BOOL: + case T_INT: + case T_PAIR: + case T_STRING: + case T_IP: + case T_PREFIX: + case T_PREFIX_SET: + case T_SET: case T_PATH: - case T_CLIST: case T_PATH_MASK: + case T_CLIST: if (sym->class != (SYM_VARIABLE | v2.type)) runtime( "Assigning to variable of incompatible type" ); * (struct f_val *) sym->def = v2; @@ -447,10 +474,12 @@ interpret(struct f_inst *what) break; /* some constants have value in a2, some in *a1.p, strange. */ - case 'c': /* integer (or simple type) constant, or string, or set */ + case 'c': /* integer (or simple type) constant, string, set, or prefix_set */ res.type = what->aux; - if (res.type == T_SET) + if (res.type == T_PREFIX_SET) + res.val.ti = what->a2.p; + else if (res.type == T_SET) res.val.t = what->a2.p; else if (res.type == T_STRING) res.val.s = what->a2.p; @@ -818,16 +847,21 @@ i_same(struct f_inst *f1, struct f_inst *f2) break; case 'c': - if (f1->aux & T_SET) { + switch (f1->aux) { + + case T_PREFIX_SET: + if (!trie_same(f1->a2.p, f2->a2.p)) + return 0; + + case T_SET: if (!same_tree(f1->a2.p, f2->a2.p)) return 0; - break; - } - switch (f1->aux) { + case T_STRING: if (strcmp(f1->a2.p, f2->a2.p)) return 0; break; + default: A2_SAME; } diff --git a/filter/filter.h b/filter/filter.h index f71e54d3..2277f519 100644 --- a/filter/filter.h +++ b/filter/filter.h @@ -50,6 +50,7 @@ struct f_val { struct f_prefix px; char *s; struct f_tree *t; + struct f_trie *ti; struct adata *ad; struct f_path_mask *path_mask; } val; @@ -69,6 +70,12 @@ struct f_tree *build_tree(struct f_tree *); struct f_tree *find_tree(struct f_tree *t, struct f_val val); int same_tree(struct f_tree *t1, struct f_tree *t2); +struct f_trie *f_new_trie(void); +void trie_add_prefix(struct f_trie *t, struct f_prefix *px); +int trie_match_prefix(struct f_trie *t, struct f_prefix *px); +int trie_same(struct f_trie *t1, struct f_trie *t2); +int trie_print(struct f_trie *t, char *buf, int blen); + struct ea_list; struct rte; @@ -128,6 +135,7 @@ void val_print(struct f_val v); #define T_RETURN 0x40 #define T_SET 0x80 +#define T_PREFIX_SET 0x81 struct f_tree { struct f_tree *left, *right; @@ -135,6 +143,19 @@ struct f_tree { void *data; }; +struct f_trie_node +{ + ip_addr addr, mask, accept; + int plen; + struct f_trie_node *c[2]; +}; + +struct f_trie +{ + int zero; + struct f_trie_node root; +}; + #define NEW_F_VAL struct f_val * val; val = cfg_alloc(sizeof(struct f_val)); #define FF_FORCE_TMPATTR 1 /* Force all attributes to be temporary */ diff --git a/filter/test.conf b/filter/test.conf index 96859e53..af889073 100644 --- a/filter/test.conf +++ b/filter/test.conf @@ -100,10 +100,25 @@ function __test2() } reject; } +function test_pxset(prefix set pxs) +{ + print " must be true: ", 10.0.0.0/8 ~ pxs, ",", 10.0.0.0/10 ~ pxs, ",", 10.0.0.0/12 ~ pxs, ",", + 20.0.0.0/24 ~ pxs, ",", 20.0.40.0/24 ~ pxs, ",", 20.0.0.0/26 ~ pxs, ",", + 20.0.100.0/26 ~ pxs, ",", 20.0.0.0/28 ~ pxs, ",", 20.0.255.0/28 ~ pxs; + print " must be false: ", 10.0.0.0/7 ~ pxs, ",", 10.0.0.0/13 ~ pxs, ",", 10.0.0.0/16 ~ pxs, ",", + 20.0.0.0/16 ~ pxs, ",", 20.0.0.0/23 ~ pxs, ",", 20.0.0.0/29 ~ pxs, ",", + 11.0.0.0/10 ~ pxs, ",", 20.1.0.0/26 ~ pxs; +} + function __startup() int i; +bool b; prefix px; ip p; +pair pp; +int set is; +prefix set pxs; +string s; { print "Testing filter language:"; i = four; @@ -118,20 +133,37 @@ ip p; if 1234 = i then printn "."; else { print "*** FAIL: if 1 else"; } # if 1 <= 1 then printn "."; else { print "*** FAIL: test 3"; } if 1234 < 1234 then { print "*** FAIL: test 4"; quitbird; } else print "ok"; + is = [ 2, 3, 4, 7..11 ]; print " must be true: ", 1.2.0.0/16 ~ [ 1.0.0.0/8{ 15 , 17 } ]; - print " data types; must be true: ", 1.2.3.4 = 1.2.3.4, ",", 1 ~ [1,2,3], ",", 5 ~ [1..20], ",", 2 ~ [ 1, 2, 3 ], ",", 5 ~ [ 4 .. 7 ], ",", 1.2.3.4 ~ [ 1.2.3.3..1.2.3.5 ], ",", 1.2.3.4 ~ 1.0.0.0/8, ",", 1.0.0.0/8 ~ 1.0.0.0/8, ",", 1.0.0.0/8 ~ [ 1.0.0.0/8+ ]; + print " data types; must be true: ", 1.2.3.4 = 1.2.3.4, ",", 1 ~ [1,2,3], ",", 5 ~ [1..20], ",", 10 ~ is, ",", 2 ~ [ 1, 2, 3 ], ",", 5 ~ [ 4 .. 7 ], ",", 1.2.3.4 ~ [ 1.2.3.3..1.2.3.5 ], ",", 1.2.3.4 ~ 1.0.0.0/8, ",", 1.0.0.0/8 ~ 1.0.0.0/8, ",", 1.0.0.0/8 ~ [ 1.0.0.0/8+ ]; print " must be true: ", true && true, ",", true || false; # print " must be true: ", defined(1), ",", defined(1.2.3.4), ",", 1 != 2, ",", 1 <= 2; - print " data types: must be false: ", 1 ~ [ 2, 3, 4 ], ",", 5 ~ [ 2, 3, 4, 7..11 ], ",", 1.2.3.4 ~ [ 1.2.3.3, 1.2.3.5 ], ",", (1,2) > (2,2), ",", (1,1) > (1,1), ",", 1.0.0.0/8 ~ [ 1.0.0.0/8- ], ",", 1.2.0.0/17 ~ [ 1.0.0.0/8{ 15 , 16 } ], ",", true && false; + print " data types: must be false: ", 1 ~ [ 2, 3, 4 ], ",", 5 ~ is, ",", 1.2.3.4 ~ [ 1.2.3.3, 1.2.3.5 ], ",", (1,2) > (2,2), ",", (1,1) > (1,1), ",", 1.0.0.0/9 ~ [ 1.0.0.0/8- ], ",", 1.2.0.0/17 ~ [ 1.0.0.0/8{ 15 , 16 } ], ",", true && false; px = 1.2.0.0/18; print "Testing prefixes: 1.2.0.0/18 = ", px; p = 127.1.2.3; print "Testing mask : 127.0.0.0 = ", p.mask(8); - print "Testing pairs: (1,2) = ", (1,2); + + pp = (1, 2); + print "Testing pairs: (1,2) = ", (1,2), " = ", pp; print "Testing enums: ", RTS_DUMMY, " ", RTS_STATIC; + s = "Hello"; + print "Testing string: ", s, " true: ", s ~ "Hell*", " false: ", s ~ "ell*"; + + b = true; + print "Testing bool: ", b, ", ", !b; + + pxs = [ 1.2.0.0/16, 1.4.0.0/16+]; + print "Testing prefix sets: "; + print pxs; + print " must be true: ", 1.2.0.0/16 ~ pxs, ",", 1.4.0.0/16 ~ pxs, ",", 1.4.0.0/18 ~ pxs, ",", 1.4.0.0/32 ~ pxs; + print " must be false: ", 1.1.0.0/16 ~ pxs, ",", 1.3.0.0/16 ~ pxs, ",", 1.2.0.0/15 ~ pxs, ",", 1.2.0.0/17 ~ pxs, ",", + 1.2.0.0/32 ~ pxs, ",", 1.4.0.0/15 ~ pxs; + + test_pxset([ 10.0.0.0/16{8,12}, 20.0.0.0/16{24,28} ]); print "What will this do? ", [ 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 5 ]; print "Testing functions..."; diff --git a/filter/test6.conf b/filter/test6.conf new file mode 100644 index 00000000..f25ffc47 --- /dev/null +++ b/filter/test6.conf @@ -0,0 +1,182 @@ +/* + * This is an example configuration file. + * FIXME: add all examples from docs here. + */ + +# Yet another comment + +router id 62.168.0.1; + +define xyzzy = (120+10); + +function callme(int arg1; int arg2) +int local1; +int local2; +int i; +{ + printn "Function callme called arguments ", arg1, " and ", arg2, ":" ; + i = arg2; + + case arg1 { + 2: print "dva"; print "jeste jednou dva"; + 3 .. 5: print "tri az pet"; + else: print "neco jineho"; + } +} + +function fifteen() +{ + print "fifteen called"; + return 15; +} + +function paths() +bgpmask pm1; +bgpmask pm2; +bgppath p2; +clist l; +{ + pm1 = / 4 3 2 1 /; + pm2 = [= 4 3 2 1 =]; + print "Testing path masks: ", pm1, " ", pm2; + p2 = prepend( + empty +, 1 ); + p2 = prepend( p2, 2 ); + p2 = prepend( p2, 3 ); + p2 = prepend( p2, 4 ); + print "Testing paths: ", p2; + print "Should be true: ", p2 ~ pm1, " ", p2 ~ pm2; + print "4 = ", p2.len; + p2 = prepend( p2, 5 ); + print "Should be false: ", p2 ~ pm1, " ", p2 ~ pm2; + print "Should be true: ", p2 ~ / ? 4 3 2 1 /, " ", p2, " ", / ? 4 3 2 1 /; + print "Should be true: ", p2 ~ [= * 4 3 * 1 =], " ", p2, " ", [= * 4 3 * 1 =]; + print "5 = ", p2.len; + + pm1 = [= 1 2 * 3 4 5 =]; + p2 = prepend( + empty +, 5 ); + p2 = prepend( p2, 4 ); + p2 = prepend( p2, 3 ); + p2 = prepend( p2, 3 ); + p2 = prepend( p2, 2 ); + p2 = prepend( p2, 1 ); + print "Should be true: ", p2 ~ pm1, " ", p2, " ", pm1; + + l = - empty -; + l = add( l, (1,2) ); + l = add( l, (2,3) ); + print "Community list (1,2) (2,3) ", l; + print "Should be true: ", (2,3) ~ l; + l = delete( l, (2,3) ); + print "Community list (1,2) ", l; + print "Should be false: ", (2,3) ~ l; +} + +function bla() +{ + print "fifteen called"; + return 15; +} + +define four=4; + +function test_pxset(prefix set pxs) +{ + print " must be true: ", 1000::/8 ~ pxs, ",", 1000::/10 ~ pxs, ",", 1000::/12 ~ pxs, ",", + 2000::/24 ~ pxs, ",", 2000:4000::/24 ~ pxs, ",", 2000::/26 ~ pxs, ",", + 2000:8000::/26 ~ pxs, ",", 2000::/28 ~ pxs, ",", 2000:FFF0::/28 ~ pxs; + print " must be false: ", 1000::/7 ~ pxs, ",", 1000::/13 ~ pxs, ",", 1000::/16 ~ pxs, ",", + 2000::/16 ~ pxs, ",", 2000::/23 ~ pxs, ",", 2000::/29 ~ pxs, ",", + 1100::/10 ~ pxs, ",", 2010::/26 ~ pxs; +} + +function __startup() +int i; +bool b; +prefix px; +ip p; +pair pp; +int set is; +prefix set pxs; +string s; +{ + print "Testing filter language:"; + i = four; + i = 12*100 + 60/2 + i; + i = ( i + 0 ); + print " arithmetics: 1234 = ", i; + printn " if statements "; + print "what happens here?"; + printn "."; + if (i = 4) then { print "*** FAIL: if 0"; quitbird; } else printn "."; +# if !(i = 3) then { print "*** FAIL: if 0"; quitbird; } else printn "."; + if 1234 = i then printn "."; else { print "*** FAIL: if 1 else"; } +# if 1 <= 1 then printn "."; else { print "*** FAIL: test 3"; } + if 1234 < 1234 then { print "*** FAIL: test 4"; quitbird; } else print "ok"; + is = [ 2, 3, 4, 7..11 ]; + print " must be true: ", 1180::/16 ~ [ 1100::/8{ 15 , 17 } ]; + print " data types; must be true: ", 12::34 = 12::34, ",", 1 ~ [1,2,3], ",", 5 ~ [1..20], ",", 10 ~ is, ",", 2 ~ [ 1, 2, 3 ], ",", 5 ~ [ 4 .. 7 ], ",", 12::34 ~ [ 12::33..12::35 ], ",", 1020::34 ~ 1000::/8, ",", 1000::/8 ~ 1000::/8, ",", 1000::/8 ~ [ 1000::/8+ ]; + print " must be true: ", true && true, ",", true || false; + +# print " must be true: ", defined(1), ",", defined(1.2.3.4), ",", 1 != 2, ",", 1 <= 2; + print " data types: must be false: ", 1 ~ [ 2, 3, 4 ], ",", 5 ~ is, ",", 12::34 ~ [ 12::33, 12::35 ], ",", (1,2) > (2,2), ",", (1,1) > (1,1), ",", 1000::/9 ~ [ 1000::/8- ], ",", 1000::/17 ~ [ 1000::/8{ 15 , 16 } ], ",", true && false; + + px = 1020::/18; + print "Testing prefixes: 1020::/18 = ", px; + p = 1234:5678::; + print "Testing mask : 1200:: = ", p.mask(8); + + pp = (1, 2); + print "Testing pairs: (1,2) = ", (1,2), " = ", pp; + print "Testing enums: ", RTS_DUMMY, " ", RTS_STATIC; + + s = "Hello"; + print "Testing string: ", s, " true: ", s ~ "Hell*", " false: ", s ~ "ell*"; + + b = true; + print "Testing bool: ", b, ", ", !b; + + pxs = [ 1102::/16, 1104::/16+]; + print "Testing prefix sets: "; + print pxs; + print " must be true: ", 1102::/16 ~ pxs, ",", 1104::/16 ~ pxs, ",", 1104::/18 ~ pxs, ",", 1104::/32 ~ pxs; + print " must be false: ", 1101::/16 ~ pxs, ",", 1103::/16 ~ pxs, ",", 1102::/15 ~ pxs, ",", 1102::/17 ~ pxs, ",", + 1102::/32 ~ pxs, ",", 1104::/15 ~ pxs; + + test_pxset([ 1000::/16{8,12}, 2000::/16{24,28} ]); + print "What will this do? ", [ 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 5 ]; + + print "Testing functions..."; +# callme ( 1, 2 ); + callme ( 2, 2 ); + callme ( 2, 2 ); + callme ( 3, 2 ); + callme ( 4, 2 ); + callme ( 7, 2 ); + + i = fifteen(); + print "Testing function calls: 15 = ", i; + + paths(); + + print "done"; + quitbird; +# print "*** FAIL: this is unreachable"; +} + +filter testf +int j; +{ + print "Heya, filtering route to ", net.ip, " prefixlen ", net.len, " source ", source; + print "This route was from ", from; + j = 7; + j = 17; + if rip_metric > 15 then { + reject "RIP Metric is more than infinity"; + } + rip_metric = 14; + unset(rip_metric); + + accept "ok I take that"; +} + +eval __startup();
\ No newline at end of file diff --git a/filter/trie.c b/filter/trie.c new file mode 100644 index 00000000..7f9f5f88 --- /dev/null +++ b/filter/trie.c @@ -0,0 +1,325 @@ +/* + * Filters: Trie for prefix sets + * + * Copyright 2009 Ondrej Zajicek <santiago@crfreenet.org> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +/** + * 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 pattern. 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 + * 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. + + * There also might be + * a problem that interval of acceptance (on path from root to the + * final node) might be completely missing (for example if we have + * prefix patterns 192.168.128.0/24{8,10} and 192.168.1.0/24 + * + * 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. + * + * There are four cases when we walk through a trie: + * + * - we are in NULL + * - we are out of path (prefixes are inconsistent) + * - we are in the wanted (final) node (node length == &plen) + * - 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 add_node_to_trie() and trie_match_prefix() + * is structured according to these cases. + */ + +#include "nest/bird.h" +#include "conf/conf.h" +#include "filter/filter.h" + +/** + * f_new_trie + * + * Allocates and returns a new empty trie. + */ +struct f_trie * +f_new_trie(void) +{ + struct f_trie * ret; + ret = cfg_allocz(sizeof(struct f_trie)); + return ret; +} + +static inline struct f_trie_node * +new_node(int plen, ip_addr paddr, ip_addr pmask, ip_addr amask) +{ + struct f_trie_node *n = cfg_allocz(sizeof(struct f_trie_node)); + n->plen = plen; + n->addr = paddr; + n->mask = pmask; + n->accept = amask; + return n; +} + +static inline void +attach_node(struct f_trie_node *parent, struct f_trie_node *child) +{ + parent->c[ipa_getbit(child->addr, parent->plen) ? 1 : 0] = child; +} + +static void +add_node_to_trie(struct f_trie *t, int plen, ip_addr ip, ip_addr amask) +{ + ip_addr pmask = ipa_mkmask(plen); + ip_addr paddr = ipa_and(ip, pmask); + struct f_trie_node *o = NULL; + struct f_trie_node *n = &t->root; + + while(n) + { + ip_addr cmask = ipa_and(n->mask, pmask); + + if (ipa_compare(ipa_and(paddr, cmask), ipa_and(n->addr, 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, n->addr); + ip_addr bmask = ipa_mkmask(blen); + ip_addr baddr = ipa_and(ip, bmask); + + /* Merge accept masks from children to get accept mask for node 'b' */ + ip_addr baccm = ipa_and(ipa_or(amask, n->accept), bmask); + + struct f_trie_node *a = new_node(plen, paddr, pmask, amask); + struct f_trie_node *b = new_node(blen, baddr, bmask, baccm); + attach_node(o, b); + attach_node(b, n); + attach_node(b, a); + return; + } + + if (plen < n->plen) + { + /* We add new node 'a' between node 'o' and node 'n' */ + amask = ipa_or(amask, ipa_and(n->accept, pmask)); + struct f_trie_node *a = new_node(plen, paddr, pmask, amask); + attach_node(o, a); + attach_node(a, n); + return; + } + + if (plen == n->plen) + { + /* We already found added node in trie. Just update accept mask */ + n->accept = ipa_or(n->accept, amask); + return; + } + + /* Update accept mask part M2 and go deeper */ + n->accept = ipa_or(n->accept, ipa_and(amask, n->mask)); + + /* n->plen < plen and plen <= 32 */ + o = n; + n = n->c[ipa_getbit(paddr, n->plen) ? 1 : 0]; + } + + /* We add new tail node 'a' after node 'o' */ + struct f_trie_node *a = new_node(plen, paddr, pmask, amask); + attach_node(o, a); +} + +/** + * trie_add_prefix + * @t: trie to add to + * @px: prefix to add + * + * Adds prefix (prefix pattern) @px to trie @t. + */ +void +trie_add_prefix(struct f_trie *t, struct f_prefix *px) +{ + int l, h; + int plen = px->len & LEN_MASK; + ip_addr pmask = ipa_mkmask(plen); + + /* 'l' and 'h' are lower and upper bounds on accepted + prefix lengths, both inclusive. 0 <= l, h <= 32 */ + f_prefix_get_bounds(px, &l, &h); + + if (l == 0) + t->zero = 1; + else + l--; + + ip_addr amask = ipa_xor(ipa_mkmask(l), ipa_mkmask(h)); + /* MIN(plen, h) instead of just plen is a little trick. */ + add_node_to_trie(t, MIN(plen, h), px->ip, amask); +} + +/** + * trie_match_prefix + * @t: trie + * @px: prefix + * + * Tries to find a matching prefix pattern in the trie such that + * prefix @px matches that prefix pattern. Returns 1 if there + * is such prefix pattern in the trie. + */ +int +trie_match_prefix(struct f_trie *t, struct f_prefix *px) +{ + int plen = px->len & LEN_MASK; + ip_addr pmask = ipa_mkmask(plen); + ip_addr paddr = ipa_and(px->ip, pmask); + + if (plen == 0) + return t->zero; + + int plentest = plen - 1; + struct f_trie_node *n = &t->root; + + while(n) + { + ip_addr cmask = ipa_and(n->mask, pmask); + + /* We are out of path */ + if (ipa_compare(ipa_and(paddr, cmask), ipa_and(n->addr, cmask))) + return 0; + + /* Check accept mask */ + if (ipa_getbit(n->accept, plentest)) + return 1; + + /* We finished trie walk and still no match */ + if (plen <= n->plen) + return 0; + + /* Choose children */ + n = n->c[(ipa_getbit(paddr, n->plen)) ? 1 : 0]; + } + + return 0; +} + +static int +trie_node_same(struct f_trie_node *t1, struct f_trie_node *t2) +{ + if ((t1 == NULL) && (t2 == NULL)) + return 1; + + if ((t1 == NULL) || (t2 == NULL)) + return 0; + + if ((t1->plen != t2->plen) || + (! ipa_equal(t1->addr, t2->addr)) || + (! ipa_equal(t1->accept, t2->accept))) + return 0; + + return trie_node_same(t1->c[0], t2->c[0]) && trie_node_same(t1->c[1], t2->c[1]); +} + +/** + * trie_same + * @t1: first trie to be compared + * @t2: second one + * + * Compares two tries and returns 1 if they are same + */ +int +trie_same(struct f_trie *t1, struct f_trie *t2) +{ + return (t1->zero == t2->zero) && trie_node_same(&t1->root, &t2->root); +} + +static int +trie_node_print(struct f_trie_node *t, char *buf, int blen) +{ + if (t == NULL) + return; + + int old_blen = blen; + int wb = 0; // bsnprintf(buf, blen, "%I/%d accept %I\n", t->addr, t->plen, t->accept); +debug("%I/%d accept %I\n", t->addr, t->plen, t->accept); + + if ((wb < 0) || ((blen - wb) < 10)) + { + bsnprintf(buf, blen, "...\n"); + return -1; + } + + buf += wb; + blen -= wb; + + wb = trie_node_print(t->c[0], buf, blen); + if (wb < 0) + return -1; + + buf += wb; + blen -= wb; + + wb = trie_node_print(t->c[1], buf, blen); + if (wb < 0) + return -1; + + blen -= wb; + + return (old_blen - blen); +} + +/** + * trie_print + * @t: trie to be printed + * @buf: buffer + * @blen: buffer length + * + * Prints the trie to the buffer, using at most blen bytes. + * Returns the number of used bytes, or -1 if there is not + * enough space in the buffer. + */ +int +trie_print(struct f_trie *t, char *buf, int blen) +{ + return trie_node_print(&t->root, buf, blen); +} diff --git a/lib/bitops.c b/lib/bitops.c index 6ca05050..88cef78a 100644 --- a/lib/bitops.c +++ b/lib/bitops.c @@ -45,3 +45,24 @@ u32_masklen(u32 x) if (x & 0xaaaaaaaa) l++; return l; } + +/** + * u32_log2 - compute a binary logarithm. + * @v: number + * + * This function computes a integral part of binary logarithm of given + * integer @v and returns it. The computed value is also an index of the + * first non-zero bit position. + */ + +u32 +u32_log2(u32 v) +{ + u32 r, shift; + r = (v > 0xFFFF) << 4; v >>= r; + shift = (v > 0xFF ) << 3; v >>= shift; r |= shift; + shift = (v > 0xF ) << 2; v >>= shift; r |= shift; + shift = (v > 0x3 ) << 1; v >>= shift; r |= shift; + r |= (v >> 1); + return r; +} diff --git a/lib/bitops.h b/lib/bitops.h index 1b6dc68e..bebd830d 100644 --- a/lib/bitops.h +++ b/lib/bitops.h @@ -17,3 +17,5 @@ u32 u32_mkmask(unsigned n); int u32_masklen(u32 x); + +u32 u32_log2(u32 v); @@ -35,6 +35,7 @@ typedef u32 ip_addr; #endif +#define MAX_PREFIX_LENGTH 32 #define BITS_PER_IP_ADDRESS 32 #define STD_ADDRESS_P_LENGTH 15 #define SIZE_OF_IP_HEADER 24 @@ -58,6 +59,9 @@ typedef u32 ip_addr; #define ipa_from_u32(x) _MI(x) #define ipa_to_u32(x) _I(x) #define ipa_compare(x,y) ipv4_compare(_I(x),_I(y)) +/* ipa_pxlen() requires that x != y */ +#define ipa_pxlen(x, y) ipv4_pxlen(_I(x), _I(y)) +#define ipa_getbit(x, y) (_I(x) & (0x80000000 >> (y))) #define ip_skip_header(x, y) ipv4_skip_header(x, y) @@ -78,6 +82,12 @@ static inline int ipv4_compare(u32 x, u32 y) return (x > y) - (x < y); } +static inline u32 ipv4_pxlen(u32 a, u32 b) +{ + return 31 - u32_log2(a ^ b); +} + + #define IP_PREC_INTERNET_CONTROL 0xc0 #endif @@ -12,6 +12,7 @@ #include <sys/types.h> #include <netinet/in.h> #include "lib/string.h" +#include "lib/bitops.h" typedef struct ipv6_addr { u32 addr[4]; @@ -23,6 +24,7 @@ typedef struct ipv6_addr { #define _I2(a) ((a).addr[2]) #define _I3(a) ((a).addr[3]) +#define MAX_PREFIX_LENGTH 128 #define BITS_PER_IP_ADDRESS 128 #define STD_ADDRESS_P_LENGTH 39 #define SIZE_OF_IP_HEADER 40 @@ -57,6 +59,9 @@ typedef struct ipv6_addr { /* ipa_from_u32 and ipa_to_u32 replaced by ipa_build */ #define ipa_build(a,b,c,d) _MI(a,b,c,d) #define ipa_compare(x,y) ipv6_compare(x,y) +/* ipa_pxlen() requires that x != y */ +#define ipa_pxlen(x, y) ipv6_pxlen(x, y) +#define ipa_getbit(x, y) ipv6_getbit(x, y) #define ipa_absolutize(x,y) ipv6_absolutize(x,y) ip_addr ipv6_mkmask(unsigned); @@ -81,6 +86,21 @@ static inline unsigned ipv6_hash(ip_addr *a) return (x ^ (x >> 16) ^ (x >> 8)) & 0xffff; } +static inline u32 ipv6_getbit(ip_addr a, u32 y) +{ + return a.addr[y / 32] & (0x80000000 >> (y % 32)); +} + +static inline u32 ipv6_pxlen(ip_addr a, ip_addr b) +{ + int i = 0; + i+= (a.addr[i] == b.addr[i]); + i+= (a.addr[i] == b.addr[i]); + i+= (a.addr[i] == b.addr[i]); + i+= (a.addr[i] == b.addr[i]); + return 32 * i + 31 - u32_log2(a.addr[i] ^ b.addr[i]); +} + /* * RFC 1883 defines packet precendece, but RFC 2460 replaces it * by generic Traffic Class ID with no defined semantics. Better |