diff options
| -rw-r--r-- | bird.conf | 10 | ||||
| -rw-r--r-- | conf/cf-lex.l | 4 | ||||
| -rw-r--r-- | conf/confbase.Y | 4 | ||||
| -rw-r--r-- | filter/Makefile | 2 | ||||
| -rw-r--r-- | filter/config.Y | 24 | ||||
| -rw-r--r-- | filter/filter.c | 107 | ||||
| -rw-r--r-- | filter/filter.h | 13 | ||||
| -rw-r--r-- | filter/tree.c | 125 |
8 files changed, 251 insertions, 38 deletions
@@ -20,6 +20,16 @@ int i; if 1 <= 1 then print "test 3 passed"; else { print "*** FAIL: test 3"; } if 1234 < 1234 then { print "*** FAIL: test 4"; quitbird; } else print "test 4 passed"; + print "Testing IP addresses: 1.2.3.4 = " 1.2.3.4; + print "Testing sets of ints = " [ 1, 2, 3 ]; + print "Testing sets of ints = " [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ]; + print "Testing sets of IPs = " [ 1.2.3.4, 2.3.4.5, 3.4.5.6 ]; + print "Sets: true = " 1 ~ [ 1, 2, 3 ]; + print " false = " 1 ~ [ 2, 3, 4 ]; + print "a..b: true = " 5 ~ [ 4 .. 7 ]; + print " false = " 5 ~ [ 2, 3, 4, 7..11 ]; + print "IPsets: true = " 1.2.3.4 ~ [ 1.2.3.3..1.2.3.5 ]; + print " false = " 1.2.3.4 ~ [ 1.2.3.3, 1.2.3.5 ]; print "done"; quitbird; diff --git a/conf/cf-lex.l b/conf/cf-lex.l index a9e7b542..ca7bfae1 100644 --- a/conf/cf-lex.l +++ b/conf/cf-lex.l @@ -9,6 +9,8 @@ %{ #undef REJECT /* Avoid name clashes */ +#include "filter/filter.h" + #include <errno.h> #include <stdlib.h> #include <string.h> @@ -103,7 +105,7 @@ WHITE [ \t] return SYM; } -[={}:;,()+*/%-<>~] { +[={}:;,()+*/%-<>~\[\]] { return yytext[0]; } diff --git a/conf/confbase.Y b/conf/confbase.Y index 0598d560..f65a9f6b 100644 --- a/conf/confbase.Y +++ b/conf/confbase.Y @@ -27,6 +27,8 @@ CF_DECLS char *t; struct f_inst *x; struct filter *f; + struct f_tree *e; + struct f_val v; } %token END @@ -37,7 +39,7 @@ CF_DECLS %type <i> expr bool pxlen -%nonassoc '=' '<' '>' +%nonassoc '=' '<' '>' '~' ELSE IF %left '+' '-' %left '*' '/' '%' %left '!' diff --git a/filter/Makefile b/filter/Makefile index 81bd355b..f41d7a3d 100644 --- a/filter/Makefile +++ b/filter/Makefile @@ -1,4 +1,4 @@ -source=f-util.c filter.c +source=f-util.c filter.c tree.c root-rel=../ dir-name=filter diff --git a/filter/config.Y b/filter/config.Y index a3eeef7e..4f910c26 100644 --- a/filter/config.Y +++ b/filter/config.Y @@ -18,7 +18,7 @@ CF_HDR CF_DECLS -CF_KEYWORDS(FUNCTION, PRINTDEBUG, PRINT, CONST, PUTS, +CF_KEYWORDS(FUNCTION, PRINT, CONST, ACCEPT, REJECT, ERROR, QUITBIRD, INT, BOOL, IP, PREFIX, PAIR, SET, STRING, IF, THEN, ELSE, @@ -29,6 +29,8 @@ CF_KEYWORDS(FUNCTION, PRINTDEBUG, PRINT, CONST, PUTS, %type <x> term block cmds cmd function_body ifthen constant print_one print_list %type <f> filter filter_body %type <i> type break_command +%type <e> set_item set_items +%type <v> set_atom CF_GRAMMAR @@ -128,12 +130,29 @@ block: } ; +set_atom: + NUM { $$.type = T_INT; $$.val.i = $1; } + | IPA { $$.type = T_IP; $$.val.ip = $1; } + ; + +set_item: + set_atom { $$ = f_new_tree(); $$->from = $$->to = $1 } + | set_atom '.' '.' set_atom { $$ = f_new_tree(); $$->from = $1; $$->to = $4; } + ; + +set_items: + set_item { $$ = $1; } + | set_items ',' set_item { $$ = $3; $$->left = $1; } + ; + constant: CONST '(' expr ')' { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_INT; $$->a2.i = $3; } | NUM { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_INT; $$->a2.i = $1; } | TRUE { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_BOOL; $$->a2.i = 1; } | FALSE { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_BOOL; $$->a2.i = 0; } - | TEXT { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_STRING; $$->a2.p = $1; } + | TEXT { $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_STRING; $$->a2.p = $1; } + | IPA { struct f_val * val; val = cfg_alloc(sizeof(struct f_val)); $$ = f_new_inst(); $$->code = 'C'; $$->a1.p = val; val->type = T_IP; val->val.ip = $1; } + | '[' set_items ']' { printf( "We've got a set here..." ); $$ = f_new_inst(); $$->code = 'c'; $$->a1.i = T_SET; $$->a2.p = build_tree($2); printf( "ook\n" ); } ; term: @@ -145,6 +164,7 @@ term: | term '<' '=' term { $$ = f_new_inst(); $$->code = '<='; $$->a1.p = $1; $$->a2.p = $4; } | term '>' term { $$ = f_new_inst(); $$->code = '<'; $$->a1.p = $3; $$->a2.p = $1; } | term '>' '=' term { $$ = f_new_inst(); $$->code = '<='; $$->a1.p = $4; $$->a2.p = $1; } + | term '~' term { $$ = f_new_inst(); $$->code = '~'; $$->a1.p = $1; $$->a2.p = $3; } | SYM { $$ = f_new_inst(); diff --git a/filter/filter.c b/filter/filter.c index 4d48cfb3..a83067df 100644 --- a/filter/filter.c +++ b/filter/filter.c @@ -16,6 +16,7 @@ #include "lib/lists.h" #include "lib/resource.h" #include "lib/socket.h" +#include "lib/string.h" #include "nest/route.h" #include "nest/protocol.h" #include "nest/iface.h" @@ -43,11 +44,59 @@ struct f_inst *startup_func = NULL; if (v1.type != v2.type) \ runtime( "Can not operate with values of incompatible types" ); +#define CMP_ERROR 999 + +/* Compare two values, returns -1, 0, 1 compared, ERROR 999 */ +int +val_compare(struct f_val v1, struct f_val v2) +{ + switch (v1.type) { + case T_INT: + if (v1.val.i == v2.val.i) return 0; + if (v1.val.i < v2.val.i) return -1; + return 1; + default: return CMP_ERROR; + } +} + +static void +tree_print(struct f_tree *t) +{ + if (!t) { + printf( "() " ); + return; + } + printf( "[ " ); + tree_print( t->left ); + printf( ", " ); val_print( t->from ); printf( ".." ); val_print( t->to ); printf( ", " ); + tree_print( t->right ); + printf( "] " ); +} + +void +val_print(struct f_val v) +{ + char buf[2048]; +#define PRINTF(a...) bsnprintf( buf, 2040, a ) + buf[0] = 0; + switch (v.type) { + case T_VOID: PRINTF( "(void)" ); break; + case T_BOOL: PRINTF( v.val.i ? "TRUE" : "FALSE" ); break; + case T_INT: PRINTF( "%d ", v.val.i ); break; + case T_STRING: PRINTF( "%s", v.val.s ); break; + case T_IP: PRINTF( "%I", v.val.ip ); break; + case T_SET: tree_print( v.val.t ); PRINTF( "\n" ); break; + default: PRINTF( "[unknown type %x]", v.type ); + } + printf( buf ); +} + static struct f_val interpret(struct f_inst *what) { struct symbol *sym; struct f_val v1, v2, res; + int i,j,k; res.type = T_VOID; if (!what) @@ -80,38 +129,32 @@ interpret(struct f_inst *what) break; /* Relational operators */ - case '!=': - case '==': - TWOARGS_C; - res.type = T_BOOL; - switch (v1.type) { - case T_VOID: runtime( "Can not operate with values of type void" ); - case T_INT: res.val.i = (v1.val.i == v2.val.i); break; - default: runtime( "Usage of unknown type" ); - } - if (what->code == '!=') - res.val.i = !(res.val.i); - break; - case '<': - TWOARGS_C; - res.type = T_BOOL; - switch (v1.type) { - case T_VOID: runtime( "Can not operate with values of type void" ); - case T_INT: res.val.i = (v1.val.i < v2.val.i); break; - default: runtime( "Usage of unknown type" ); - } + +#define COMPARE(x) \ + TWOARGS_C; \ + res.type = T_BOOL; \ + i = val_compare(v1, v2); \ + if (i==CMP_ERROR) \ + runtime( "Error in comparation" ); \ + res.val.i = (x); \ break; - case '<=': - TWOARGS_C; + + case '!=': COMPARE(i!=0); + case '==': COMPARE(i==0); + case '<': COMPARE(i==-1); + case '<=': COMPARE(i!=1); + + case '~': + TWOARGS; res.type = T_BOOL; - switch (v1.type) { - case T_VOID: runtime( "Can not operate with values of type void" ); - case T_INT: res.val.i = (v1.val.i <= v2.val.i); break; - default: runtime( "Usage of unknown type" ); + if (((v1.type == T_INT) || (v1.type == T_IP)) && (v2.type == T_SET)) { + res.val.i = !! find_tree(v2.val.t, v1); + break; } + runtime( "~ applied on unknown type pair" ); break; -/* Set */ + /* Set to consant, a1 = type, a2 = value */ case 's': ARG(v2, a2.p); sym = what->a1.p; @@ -129,18 +172,16 @@ interpret(struct f_inst *what) res.type = what->a1.i; res.val.i = (int) what->a2.p; break; + case 'C': + res = * ((struct f_val *) what->a1.p); + break; case 'i': res.type = what->a1.i; res.val.i = * ((int *) what->a2.p); break; case 'p': ONEARG; - switch (v1.type) { - case T_VOID: printf( "(void)" ); break; - case T_INT: printf( "%d ", v1.val.i ); break; - case T_STRING: printf( "%s", v1.val.i ); break; - default: runtime( "Print of variable of unknown type" ); - } + val_print(v1); break; case '?': /* ? has really strange error value, so we can implement if ... else nicely :-) */ ONEARG; diff --git a/filter/filter.h b/filter/filter.h index ffb50b3f..cc3fef12 100644 --- a/filter/filter.h +++ b/filter/filter.h @@ -40,6 +40,7 @@ struct f_val { ip_addr ip; struct prefix px; char *s; + struct f_tree *t; } val; }; @@ -50,10 +51,16 @@ struct filter { void filters_postconfig(void); struct f_inst *f_new_inst(void); +struct f_tree *f_new_tree(void); + +struct f_tree *build_tree(struct f_tree *); +struct f_tree *find_tree(struct f_tree *t, struct f_val val); int f_run(struct filter *filter, struct rte **rte, struct ea_list **tmp_attrs, struct linpool *tmp_pool); char *filter_name(struct filter *filter); +int val_compare(struct f_val v1, struct f_val v2); +void val_print(struct f_val v); #define F_NOP 0 #define F_ACCEPT 1 /* Need to preserve ordering: accepts < rejects! */ @@ -85,4 +92,10 @@ char *filter_name(struct filter *filter); #define T_SET 0x80 +struct f_tree { + struct f_tree *left, *right; + struct f_val from, to; + void *data; +}; + #endif diff --git a/filter/tree.c b/filter/tree.c new file mode 100644 index 00000000..ea1f18f2 --- /dev/null +++ b/filter/tree.c @@ -0,0 +1,125 @@ +/* + * Filters: utility functions + * + * Copyright 1998 Pavel Machek <pavel@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include <stdio.h> +#include <fcntl.h> +#include <unistd.h> +#include <sys/signal.h> +#include <setjmp.h> + +#include "nest/bird.h" +#include "lib/lists.h" +#include "lib/resource.h" +#include "lib/socket.h" +#include "nest/route.h" +#include "nest/protocol.h" +#include "nest/iface.h" +#include "conf/conf.h" +#include "filter/filter.h" + +/* Finds n-th item in list linked by right. Trashes pointers in right. */ +static struct f_tree * +find_nth(struct f_tree *from, int nth) +{ + struct f_tree *pivot; + int lcount = 0, rcount = 0; + struct f_tree *left, *right, *next; + + pivot = from; + + left = right = NULL; + next = from->right; + while (from = next) { + next = from->right; + if (val_compare(pivot->from, from->from)==1) { + from->right = left; + left = from; + lcount++; + } else { + from->right = right; + right = from; + rcount++; + } + } + if (lcount == nth) + return pivot; + if (lcount < nth) + return find_nth(right, nth-lcount-1); + return find_nth(left, nth); +} + +/* Gets list linked by left, finds its median, trashes pointers in right */ +static struct f_tree * +find_median(struct f_tree *from) +{ + struct f_tree *t = from; + int cnt = 0; + + if (!from) + return NULL; + do { + t->right = t->left; + cnt++; + } while (t = t->left); + return find_nth(from, cnt/2); +} + +struct f_tree * +find_tree(struct f_tree *t, struct f_val val) +{ + if (!t) + return 0; + if ((val_compare(t->from, val) != 1) && + (val_compare(t->to, val) != -1)) + return t; + if (val_compare(t->from, val) == -1) + return find_tree(t->right, val); + else + return find_tree(t->left, val); +} + +/* Gets list linked by left */ +struct f_tree * +build_tree(struct f_tree *from) +{ + struct f_tree *median, *t = from, *next, *left = NULL, *right = NULL; + + median = find_median(from); + if (!median) + return NULL; + + do { + next = t->left; + if (t == median) + continue; + + if (val_compare(median->from, t->from)==1) { + t->left = left; + left = t; + } else { + t->left = right; + right = t; + } + } while(t = next); + + median->left = build_tree(left); + median->right = build_tree(right); + return median; +} + +struct f_tree * +f_new_tree(void) +{ + struct f_tree * ret; + ret = cfg_alloc(sizeof(struct f_tree)); + ret->left = ret->right = NULL; + ret->from.type = ret->to.type = T_VOID; + ret->from.val.i = ret->to.val.i = 0; + ret->data = NULL; + return ret; +} |