From 9b302c133f02f96edc5caa769dfd21dc9ef038b5 Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Thu, 3 Mar 2022 20:34:44 +0100 Subject: Filter: Ensure that all expressions declared return type All instructions with a return value (i.e. expressions, ones with non-zero outval, third argument in INST()) should declare their return type. Check that automatically by M4 macros. Set outval of FI_RETURN to 0. The instruction adds one value to stack, but syntactically it is a statement, not an expression. Add fake return type declaration to FI_CALL, otherwise the automatic check would fail builds. --- filter/decl.m4 | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) (limited to 'filter/decl.m4') diff --git a/filter/decl.m4 b/filter/decl.m4 index 5242c04c..4f7ca3ad 100644 --- a/filter/decl.m4 +++ b/filter/decl.m4 @@ -238,9 +238,13 @@ m4_define(ERROR, # This macro specifies result type and makes there are no conflicting definitions m4_define(RESULT_TYPE, `m4_ifdef([[INST_RESULT_TYPE]], - [[m4_ifelse(INST_RESULT_TYPE,$1,,[[ERROR([[Multiple type definitons]])]])]], + [[m4_ifelse(INST_RESULT_TYPE,$1,,[[ERROR([[Multiple type definitions in]] INST_NAME)]])]], [[m4_define(INST_RESULT_TYPE,$1) RESULT_TYPE_($1)]])') +m4_define(RESULT_TYPE_CHECK, + `m4_ifelse(INST_OUTVAL,0,, + [[m4_ifdef([[INST_RESULT_TYPE]],,[[ERROR([[Missing type definition in]] INST_NAME)]])]])') + m4_define(RESULT_TYPE_, ` FID_NEW_BODY()m4_dnl what->type = $1; @@ -294,6 +298,7 @@ m4_define(FID_ITERATE, `FID_ZONE(10, Iteration)') # This macro does all the code wrapping. See inline comments. m4_define(INST_FLUSH, `m4_ifdef([[INST_NAME]], [[ +RESULT_TYPE_CHECK()m4_dnl Check for defined RESULT_TYPE() FID_ENUM()m4_dnl Contents of enum fi_code { ... } INST_NAME(), FID_ENUM_STR()m4_dnl Contents of const char * indexed by enum fi_code @@ -392,6 +397,7 @@ m4_define(INST, `m4_dnl This macro is called on beginning of each instruction INST_FLUSH()m4_dnl First, old data is flushed m4_define([[INST_NAME]], [[$1]])m4_dnl Then we store instruction name, m4_define([[INST_INVAL]], [[$2]])m4_dnl instruction input value count, +m4_define([[INST_OUTVAL]], [[$3]])m4_dnl instruction output value count, m4_undefine([[INST_NEVER_CONSTANT]])m4_dnl reset NEVER_CONSTANT trigger, m4_undefine([[INST_RESULT_TYPE]])m4_dnl and reset RESULT_TYPE value. FID_INTERPRET_BODY()m4_dnl By default, every code is interpreter code. -- cgit v1.2.3 From b2d6d2948af268812a8f55f260d340194eb3f7ac Mon Sep 17 00:00:00 2001 From: Alexander Zubkov Date: Fri, 4 Mar 2022 14:07:58 +0100 Subject: Filter: Add literal for empty set Add literal for empty set [], which works both for tree-based sets and prefix sets by using existing constant promotion mechanism. Minor changes by committer. --- filter/config.Y | 2 ++ filter/data.c | 14 +++++++++++++ filter/data.h | 8 +++---- filter/decl.m4 | 5 +++++ filter/f-inst.c | 2 +- filter/test.conf | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 90 insertions(+), 5 deletions(-) (limited to 'filter/decl.m4') diff --git a/filter/config.Y b/filter/config.Y index a4b4d3d3..a4e82c7d 100644 --- a/filter/config.Y +++ b/filter/config.Y @@ -674,6 +674,7 @@ bgp_path: bgp_path_tail: NUM bgp_path_tail { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .asn = $1, .kind = PM_ASN, }, }); $$->next = $2; } | NUM DDOT NUM bgp_path_tail { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .from = $1, .to = $3, .kind = PM_ASN_RANGE }, }); $$->next = $4; } + | '[' ']' bgp_path_tail { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .set = NULL, .kind = PM_ASN_SET }, }); $$->next = $3; } | '[' set_items ']' bgp_path_tail { if ($2->from.type != T_INT) cf_error("Only integer sets allowed in path mask"); $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_PATH_MASK_ITEM, .val.pmi = { .set = build_tree($2), .kind = PM_ASN_SET }, }); $$->next = $4; @@ -693,6 +694,7 @@ constant: | fipa { $$ = f_new_inst(FI_CONSTANT, $1); } | VPN_RD { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_RD, .val.ec = $1, }); } | net_ { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_NET, .val.net = $1, }); } + | '[' ']' { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_SET, .val.t = NULL, }); } | '[' set_items ']' { DBG( "We've got a set here..." ); $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_SET, .val.t = build_tree($2), }); diff --git a/filter/data.c b/filter/data.c index 56c1fb17..276738a9 100644 --- a/filter/data.c +++ b/filter/data.c @@ -79,6 +79,8 @@ f_type_element_type(enum f_type t) }; } +const struct f_trie f_const_empty_trie = { .ipv4 = -1, }; + const struct f_val f_const_empty_path = { .type = T_PATH, .val.ad = &null_adata, @@ -91,6 +93,9 @@ const struct f_val f_const_empty_path = { }, f_const_empty_lclist = { .type = T_LCLIST, .val.ad = &null_adata, +}, f_const_empty_prefix_set = { + .type = T_PREFIX_SET, + .val.ti = &f_const_empty_trie, }; static struct adata * @@ -301,6 +306,12 @@ val_same(const struct f_val *v1, const struct f_val *v2) int clist_set_type(const struct f_tree *set, struct f_val *v) { + if (!set) + { + v->type = T_VOID; + return 1; + } + switch (set->from.type) { case T_PAIR: @@ -537,6 +548,9 @@ val_in_range(const struct f_val *v1, const struct f_val *v2) if (v2->type != T_SET) return F_CMP_ERROR; + if (!v2->val.t) + return 0; + /* With integrated Quad<->IP implicit conversion */ if ((v1->type == v2->val.t->from.type) || ((v1->type == T_QUAD) && val_is_ip4(&(v2->val.t->from)) && val_is_ip4(&(v2->val.t->to)))) diff --git a/filter/data.h b/filter/data.h index 8cba8c0e..221e4229 100644 --- a/filter/data.h +++ b/filter/data.h @@ -279,11 +279,11 @@ int val_in_range(const struct f_val *v1, const struct f_val *v2); int clist_set_type(const struct f_tree *set, struct f_val *v); static inline int eclist_set_type(const struct f_tree *set) -{ return set->from.type == T_EC; } +{ return !set || set->from.type == T_EC; } static inline int lclist_set_type(const struct f_tree *set) -{ return set->from.type == T_LC; } +{ return !set || set->from.type == T_LC; } static inline int path_set_type(const struct f_tree *set) -{ return set->from.type == T_INT; } +{ return !set || set->from.type == T_INT; } const struct adata *clist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos); const struct adata *eclist_filter(struct linpool *pool, const struct adata *list, const struct f_val *set, int pos); @@ -299,7 +299,7 @@ undef_value(struct f_val v) (v.val.ad == &null_adata); } -extern const struct f_val f_const_empty_path, f_const_empty_clist, f_const_empty_eclist, f_const_empty_lclist; +extern const struct f_val f_const_empty_path, f_const_empty_clist, f_const_empty_eclist, f_const_empty_lclist, f_const_empty_prefix_set; enum filter_return f_eval(const struct f_line *expr, struct linpool *tmp_pool, struct f_val *pres); diff --git a/filter/decl.m4 b/filter/decl.m4 index 4f7ca3ad..fc26e193 100644 --- a/filter/decl.m4 +++ b/filter/decl.m4 @@ -501,6 +501,11 @@ f_const_promotion(struct f_inst *arg, enum f_type want) return 1; } + else if ((c->type == T_SET) && (!c->val.t) && (want == T_PREFIX_SET)) { + *c = f_const_empty_prefix_set; + return 1; + } + return 0; } diff --git a/filter/f-inst.c b/filter/f-inst.c index 5d42c40a..d321f06d 100644 --- a/filter/f-inst.c +++ b/filter/f-inst.c @@ -401,7 +401,7 @@ break; case T_SET: - if (vv(i).val.t->from.type != T_INT) + if (!path_set_type(vv(i).val.t)) runtime("Only integer sets allowed in path mask"); pm->item[i] = (struct f_path_mask_item) { diff --git a/filter/test.conf b/filter/test.conf index 484628e5..50c58b3a 100644 --- a/filter/test.conf +++ b/filter/test.conf @@ -130,12 +130,18 @@ define is3 = [5, 17, 2, 11, 8, 15, 3, 19]; function t_int_set() int set is; { + is = []; + bt_assert(is = []); + bt_assert(0 !~ is); + bt_assert(1 ~ [1,2,3]); bt_assert(5 ~ [1..20]); bt_assert(2 ~ [ 1, 2, 3 ]); bt_assert(5 ~ [ 4 .. 7 ]); bt_assert(1 !~ [ 2, 3, 4 ]); bt_assert(999 !~ [ 666, 333 ]); + bt_assert(1 !~ []); + bt_assert(1 !~ is); is = [ 2, 3, 4, 7..11 ]; bt_assert(10 ~ is); @@ -170,6 +176,7 @@ int set is; bt_assert([1,4..10,20] = [1,4..10,20]); bt_assert(format([ 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 5 ]) = "[1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5]"); + bt_assert(format([]) = "[]"); } bt_test_suite(t_int_set, "Testing sets of integers"); @@ -237,6 +244,9 @@ pair pp; pair set ps; { pp = (1, 2); + ps = []; + bt_assert(pp !~ ps); + ps = [(1,(one+one)), (3,4)..(4,8), (5,*), (6,3..6)]; bt_assert(format(ps) = "[(1,2), (3,4)..(4,8), (5,0)..(5,65535), (6,3)..(6,6)]"); bt_assert(pp ~ ps); @@ -253,6 +263,7 @@ pair set ps; bt_assert((6,6+one) !~ ps); bt_assert(((one+6),2) !~ ps); bt_assert((1,1) !~ ps); + bt_assert(pp !~ []); ps = [(20..150, 200..300), (50100..50200, 1000..50000), (*, 5+5)]; bt_assert((100,200) ~ ps); @@ -304,6 +315,7 @@ quad qq; qq = 1.2.3.4; bt_assert(qq ~ [1.2.3.4, 5.6.7.8]); bt_assert(qq !~ [1.2.1.1, 1.2.3.5]); + bt_assert(qq !~ []); } bt_test_suite(t_quad_set, "Testing sets of quads"); @@ -384,6 +396,7 @@ ip set ips; bt_assert(1.2.3.4 !~ [ 1.2.3.3, 1.2.3.5 ]); bt_assert(1.2.3.4 ~ [ 1.2.3.3..1.2.3.5 ]); + bt_assert(1.2.3.4 !~ []); } bt_test_suite(t_ip_set, "Testing sets of ip address"); @@ -473,13 +486,34 @@ function test_pxset(prefix set pxs) bt_assert(1.0.0.0/8 ~ [ 1.0.0.0/8+ ]); bt_assert(1.0.0.0/9 !~ [ 1.0.0.0/8- ]); bt_assert(1.2.0.0/17 !~ [ 1.0.0.0/8{ 15 , 16 } ]); + bt_assert(net10 !~ []); bt_assert([ 10.0.0.0/8{ 15 , 17 } ] = [ 10.0.0.0/8{ 15 , 17 } ]); } +function test_empty_pxset(prefix set pxs) +int set s0; +prefix set s1; +{ + s0 = []; + s1 = []; + bt_assert(pxs != s0); + bt_assert(pxs = s1); + #bt_assert(pxs = []); +} + function t_prefix_set() prefix set pxs; { + pxs = []; + bt_assert(format(pxs) = "[]"); + #bt_assert(pxs = []); + bt_assert(1.2.0.0/16 !~ []); + bt_assert(1.2.0.0/16 !~ pxs); + + test_empty_pxset([]); + test_empty_pxset(pxs); + pxs = [ 1.2.0.0/16, 1.4.0.0/16+, 44.66.88.64/30{24,28}, 12.34.56.0/24{8,16} ]; bt_assert(format(pxs) = "[1.2.0.0/16{0.1.0.0}, 1.4.0.0/16{0.1.255.255}, 12.34.0.0/16{1.255.0.0}, 44.66.88.64/28{0.0.1.240}]"); @@ -564,6 +598,12 @@ bt_test_suite(t_prefix6, "Testing prefix IPv6"); function t_prefix6_set() prefix set pxs; { + pxs = []; + bt_assert(format(pxs) = "[]"); + #bt_assert(pxs = []); + bt_assert(12::34/128 !~ []); + bt_assert(12::34/128 !~ pxs); + bt_assert(1180::/16 ~ [ 1100::/8{15, 17} ]); bt_assert(12::34 = 12::34); bt_assert(12::34 ~ [ 12::33..12::35 ]); @@ -681,6 +721,7 @@ int set set12; bt_assert(3 ~ p2); bt_assert(p2 ~ [2, 10..20]); bt_assert(p2 ~ [4, 10..20]); + bt_assert(p2 !~ []); p2 = prepend(p2, 5); bt_assert(p2 !~ pm1); @@ -691,6 +732,8 @@ int set set12; bt_assert(p2 ~ [= 5 [2, 4, 6] 3 [1..2] 1 =]); bt_assert(p2 ~ [= 5 set35 3 set12 set12 =]); bt_assert(p2 ~ mkpath(5, 4)); + bt_assert(p2 ~ [= * [3] * =]); + bt_assert(p2 !~ [= * [] * =]); bt_assert(p2.len = 5); bt_assert(p2.first = 5); @@ -699,6 +742,10 @@ int set set12; bt_assert(p2.len = 5); bt_assert(delete(p2, 3) = prepend(prepend(prepend(prepend(+empty+, 1), 2), 4), 5)); bt_assert(filter(p2, [1..3]) = prepend(prepend(prepend(+empty+, 1), 2), 3)); + bt_assert(delete(p2, []) = p2); + bt_assert(filter(p2, []) = +empty+); + bt_assert(delete(prepend(prepend(+empty+, 0), 1), []) = prepend(prepend(+empty+, 0), 1)); + bt_assert(filter(prepend(prepend(+empty+, 0), 1), []) = +empty+); p2 = prepend( + empty +, 5 ); p2 = prepend( p2, 4 ); @@ -759,6 +806,7 @@ clist r; bt_assert(l ~ [(2,2..3)]); bt_assert(l ~ [(1,1..2)]); bt_assert(l ~ [(1,1)..(1,2)]); + bt_assert(l !~ []); l = add(l, (2,5)); l = add(l, (5,one)); @@ -796,6 +844,9 @@ clist r; bt_assert(l !~ [(*,(one+6))]); bt_assert(l !~ [(*, (one+one+one))]); + bt_assert(delete(l, []) = l); + bt_assert(filter(l, []) = -empty-); + l = delete(l, [(*,(one+onef(3)))]); l = delete(l, [(*,(4+one))]); bt_assert(l = add(-empty-, (3,1))); @@ -913,11 +964,15 @@ eclist r; bt_assert((ro, 10.20.30.40, 100) !~ el); bt_assert(el !~ [(rt, 10, 35..40)]); bt_assert(el !~ [(ro, 10, *)]); + bt_assert(el !~ []); el = add(el, (rt, 10, 40)); el2 = filter(el, [(rt, 10, 20..40)] ); el2 = add(el2, (rt, 10, 50)); + bt_assert(delete(el, []) = el); + bt_assert(filter(el, []) = --empty--); + # eclist A (1,30,40) bt_assert(el = add(add(add(--empty--, (rt, 10, 1)), (rt, 10, 30)), (rt, 10, 40))); bt_assert(format(el) = "(eclist (rt, 10, 1) (rt, 10, 30) (rt, 10, 40))"); @@ -1035,6 +1090,9 @@ lclist r; ll2 = add(ll2, (30, 30, 30)); ll2 = add(ll2, (40, 40, 40)); + bt_assert(delete(ll, []) = ll); + bt_assert(filter(ll, []) = ---empty---); + # lclist A (10, 20, 30) bt_assert(format(ll) = "(lclist (10, 10, 10) (20, 20, 20) (30, 30, 30))"); @@ -1094,6 +1152,7 @@ lc set lls; bt_assert(ll !~ [(5,10,15), (10,21,30)]); bt_assert(ll !~ [(10,21..25,*)]); bt_assert(ll !~ [(11, *, *)]); + bt_assert(ll !~ []); lls = [(10, 10, 10), (20, 20, 15..25), (30, 30, *), (40, 35..45, *), (50, *, *), (55..65, *, *)]; bt_assert(format(lls) = "[(10, 10, 10), (20, 20, 15)..(20, 20, 25), (30, 30, 0)..(30, 30, 4294967295), (40, 35, 0)..(40, 45, 4294967295), (50, 0, 0)..(50, 4294967295, 4294967295), (55, 0, 0)..(65, 4294967295, 4294967295)]"); @@ -1150,6 +1209,10 @@ bt_test_suite(t_rd, "Testing route distinguishers"); function t_rd_set() rd set rds; { + rds = []; + bt_assert(rds = []); + bt_assert(10:20 !~ rds); + rds = [10:20, 100000:100..100000:200]; bt_assert(format(rds) = "[10:20, 100000:100..100000:200]"); @@ -1160,6 +1223,7 @@ rd set rds; bt_assert(100000:128 ~ rds); bt_assert(100000:200 ~ rds); bt_assert(100010:150 !~ rds); + bt_assert(100010:150 !~ []); } bt_test_suite(t_rd_set, "Testing sets of route distinguishers"); -- cgit v1.2.3 From fb1d8f65136aa6190b527b691f24abe16a461471 Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Fri, 4 Mar 2022 17:51:50 +0100 Subject: Filter: Apply constant promotion for FI_EQ / FI_NEQ Equality comparison is defined on all values, even of different types, but we still want to do constant promotion if possible. --- filter/data.c | 2 +- filter/decl.m4 | 6 ++++++ filter/f-inst.c | 2 ++ filter/test.conf | 8 ++++---- 4 files changed, 13 insertions(+), 5 deletions(-) (limited to 'filter/decl.m4') diff --git a/filter/data.c b/filter/data.c index 276738a9..2bb5920c 100644 --- a/filter/data.c +++ b/filter/data.c @@ -192,7 +192,7 @@ val_compare(const struct f_val *v1, const struct f_val *v2) if (val_is_ip4(v1) && (v2->type == T_QUAD)) return uint_cmp(ipa_to_u32(v1->val.ip), v2->val.i); - debug( "Types do not match in val_compare\n" ); + DBG( "Types do not match in val_compare\n" ); return F_CMP_ERROR; } diff --git a/filter/decl.m4 b/filter/decl.m4 index fc26e193..a2a8c88a 100644 --- a/filter/decl.m4 +++ b/filter/decl.m4 @@ -186,6 +186,12 @@ if (f$1->type && f$2->type && (f$1->type != f$2->type) && cf_error("Arguments $1 and $2 of %s must be of the same type", f_instruction_name(what->fi_code)); FID_INTERPRET_BODY()') +m4_define(ARG_PREFER_SAME_TYPE, ` +FID_NEW_BODY()m4_dnl +if (f$1->type && f$2->type && (f$1->type != f$2->type)) + (void) (f_const_promotion(f$2, f$1->type) || f_const_promotion(f$1, f$2->type)); +FID_INTERPRET_BODY()') + # Executing another filter line. This replaces the recursion # that was needed in the former implementation. m4_define(LINEX, `FID_INTERPRET_EXEC()LINEX_($1)FID_INTERPRET_NEW()return $1 FID_INTERPRET_BODY()') diff --git a/filter/f-inst.c b/filter/f-inst.c index d321f06d..500732c6 100644 --- a/filter/f-inst.c +++ b/filter/f-inst.c @@ -423,12 +423,14 @@ INST(FI_NEQ, 2, 1) { ARG_ANY(1); ARG_ANY(2); + ARG_PREFER_SAME_TYPE(1, 2); RESULT(T_BOOL, i, !val_same(&v1, &v2)); } INST(FI_EQ, 2, 1) { ARG_ANY(1); ARG_ANY(2); + ARG_PREFER_SAME_TYPE(1, 2); RESULT(T_BOOL, i, val_same(&v1, &v2)); } diff --git a/filter/test.conf b/filter/test.conf index 50c58b3a..401a999b 100644 --- a/filter/test.conf +++ b/filter/test.conf @@ -498,8 +498,8 @@ prefix set s1; s0 = []; s1 = []; bt_assert(pxs != s0); - bt_assert(pxs = s1); - #bt_assert(pxs = []); + bt_assert(pxs = s1); + bt_assert(pxs = []); } function t_prefix_set() @@ -507,7 +507,7 @@ prefix set pxs; { pxs = []; bt_assert(format(pxs) = "[]"); - #bt_assert(pxs = []); + bt_assert(pxs = []); bt_assert(1.2.0.0/16 !~ []); bt_assert(1.2.0.0/16 !~ pxs); @@ -600,7 +600,7 @@ prefix set pxs; { pxs = []; bt_assert(format(pxs) = "[]"); - #bt_assert(pxs = []); + bt_assert(pxs = []); bt_assert(12::34/128 !~ []); bt_assert(12::34/128 !~ pxs); -- cgit v1.2.3 From 26bc4f9904b014c9949489e8ae28366da473e85d Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Sun, 6 Mar 2022 02:18:01 +0100 Subject: Filter: Implement direct recursion Direct recursion almost worked, just crashed on function signature check. Split function parsing such that function signature is saved before function body is processed. Recursive calls are marked so they can be avoided during f_same() and similar code walking. Also, include tower of hanoi solver as a test case. --- filter/config.Y | 23 ++++++++++++--------- filter/decl.m4 | 2 ++ filter/f-inst.c | 9 ++++++-- filter/f-inst.h | 2 +- filter/test.conf | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 86 insertions(+), 13 deletions(-) (limited to 'filter/decl.m4') diff --git a/filter/config.Y b/filter/config.Y index a4e82c7d..82a072ab 100644 --- a/filter/config.Y +++ b/filter/config.Y @@ -460,25 +460,28 @@ function_body: conf: function_def ; function_def: - FUNCTION symbol { DBG( "Beginning of function %s\n", $2->name ); + FUNCTION symbol { + DBG( "Beginning of function %s\n", $2->name ); $2 = cf_define_symbol($2, SYM_FUNCTION, function, NULL); cf_push_scope($2); - } function_args function_body - { - $5->arg_list = NULL; - $5->args = 0; + } function_args { + /* Make dummy f_line for storing function prototype */ + struct f_line *dummy = cfg_allocz(sizeof(struct f_line)); + $2->function = dummy; /* Revert the args */ while ($4) { struct f_arg *tmp = $4; $4 = $4->next; - tmp->next = $5->arg_list; - $5->arg_list = tmp; - $5->args++; + tmp->next = dummy->arg_list; + dummy->arg_list = tmp; + dummy->args++; } - - $2->function = $5; + } function_body { + $6->args = $2->function->args; + $6->arg_list = $2->function->arg_list; + $2->function = $6; cf_pop_scope(); } ; diff --git a/filter/decl.m4 b/filter/decl.m4 index a2a8c88a..3d118e34 100644 --- a/filter/decl.m4 +++ b/filter/decl.m4 @@ -376,6 +376,7 @@ case INST_NAME(): { #undef whati #undef item dest->items[pos].fi_code = what->fi_code; + dest->items[pos].flags = what->flags; dest->items[pos].lineno = what->lineno; break; } @@ -647,6 +648,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_instruction_flags flags; /* Flags, instruction-specific */ enum f_type type; /* Type of returned value, if known */ int size; /* How many instructions are underneath */ int lineno; /* Line number */ diff --git a/filter/f-inst.c b/filter/f-inst.c index 500732c6..e75b5e01 100644 --- a/filter/f-inst.c +++ b/filter/f-inst.c @@ -1165,11 +1165,16 @@ whati->fvar = tmp; what->size += tmp->size; + /* Mark recursive calls, they have dummy f_line */ + if (!sym->function->len) + what->flags |= FIF_RECURSIVE; + FID_SAME_BODY() - if (!(f1->sym->flags & SYM_FLAG_SAME)) - return 0; + if (!(f1->sym->flags & SYM_FLAG_SAME) && !(f1_->flags & FIF_RECURSIVE)) + return 0; FID_ITERATE_BODY() + if (!(what->flags & FIF_RECURSIVE)) BUFFER_PUSH(fit->lines) = whati->sym->function; FID_INTERPRET_BODY() diff --git a/filter/f-inst.h b/filter/f-inst.h index 12df40f6..58563c79 100644 --- a/filter/f-inst.h +++ b/filter/f-inst.h @@ -22,7 +22,7 @@ /* Flags for instructions */ enum f_instruction_flags { - FIF_PRINTED = 1, /* FI_PRINT_AND_DIE: message put in buffer */ + FIF_RECURSIVE = 1, /* FI_CALL: function is directly recursive */ } PACKED; /* Include generated filter instruction declarations */ diff --git a/filter/test.conf b/filter/test.conf index 401a999b..e8b6a663 100644 --- a/filter/test.conf +++ b/filter/test.conf @@ -1290,7 +1290,60 @@ function fifteen() return 15; } +function factorial(int x) +{ + if x = 0 then return 0; + if x = 1 then return 1; + else return x * factorial(x - 1); +} + +function fibonacci(int x) +{ + if x = 0 then return 0; + if x = 1 then return 1; + else return fibonacci(x - 1) + fibonacci(x - 2); +} + +function hanoi_init(int a; int b) +{ + if b = 0 + then return +empty+; + else return prepend(hanoi_init(a + 1, b - 1), a); +} + +function hanoi_solve(int n; bgppath h_src; bgppath h_dst; bgppath h_aux; bool x; bool y) +bgppath tmp1; +bgppath tmp2; +int v; +{ + # x -> return src or dst + # y -> print state + + if n = 0 then { if x then return h_src; else return h_dst; } + + tmp1 = hanoi_solve(n - 1, h_src, h_aux, h_dst, true, y); + tmp2 = hanoi_solve(n - 1, h_src, h_aux, h_dst, false, false); + h_src = tmp1; + h_aux = tmp2; + + v = h_src.first; + # bt_assert(h_dst = +empty+ || v < h_dst.first); + h_src = delete(h_src, v); + h_dst = prepend(h_dst, v); + + if y then + print "move: ", v, " src: ", h_src, " dst:", h_dst, " aux:", h_aux; + + tmp1 = hanoi_solve(n - 1, h_aux, h_dst, h_src, true, y); + tmp2 = hanoi_solve(n - 1, h_aux, h_dst, h_src, false, false); + h_aux = tmp1; + h_dst = tmp2; + + if x then return h_src; else return h_dst; +} + function t_call_function() +bgppath h_src; { bt_assert(fifteen() = 15); @@ -1302,6 +1355,16 @@ function t_call_function() bt_assert(callme(4, 4) = 16); bt_assert(callme(7, 2) = 14); bt_assert(callmeagain(1, 2, 3) = 6); + + bt_assert(factorial(5) = 120); + bt_assert(factorial(10) = 3628800); + + bt_assert(fibonacci(10) = 55); + bt_assert(fibonacci(20) = 6765); + + h_src = hanoi_init(1, 6); + bt_assert(format(h_src) = "(path 1 2 3 4 5 6)"); + bt_assert(hanoi_solve(6, h_src, +empty+, +empty+, false, false) = h_src); } bt_test_suite(t_call_function, "Testing calling functions"); -- cgit v1.2.3 From a2527ee53d9d8fe7a1c29b56f8450b9ef1f9c7bc Mon Sep 17 00:00:00 2001 From: "Ondrej Zajicek (work)" Date: Wed, 9 Mar 2022 02:32:29 +0100 Subject: Filter: Improve handling of stack frames in filter bytecode When f_line is done, we have to pop the stack frame. The old code just removed nominal number of args/vars. Change it to use stored ventry value modified by number of returned values. This allows to allocate variables on a stack frame during execution of f_lines instead of just at start. But we need to know the number of returned values for a f_line. It is 1 for term, 0 for cmd. Store that to f_line during linearization. --- conf/confbase.Y | 4 ++-- filter/config.Y | 14 +++++++------- filter/decl.m4 | 6 ++++-- filter/f-inst.c | 8 ++++---- filter/f-inst.h | 7 ++++--- filter/f-util.c | 2 +- filter/filter.c | 3 +-- nest/config.Y | 4 ++-- proto/static/config.Y | 2 +- 9 files changed, 26 insertions(+), 24 deletions(-) (limited to 'filter/decl.m4') diff --git a/conf/confbase.Y b/conf/confbase.Y index 18ca8489..1d5738ff 100644 --- a/conf/confbase.Y +++ b/conf/confbase.Y @@ -153,14 +153,14 @@ conf: definition ; definition: DEFINE symbol '=' term ';' { struct f_val *val = cfg_allocz(sizeof(struct f_val)); - if (f_eval(f_linearize($4), cfg_mem, val) > F_RETURN) cf_error("Runtime error"); + if (f_eval(f_linearize($4, 1), cfg_mem, val) > F_RETURN) cf_error("Runtime error"); cf_define_symbol($2, SYM_CONSTANT | val->type, val, val); } ; expr: NUM - | '(' term ')' { $$ = f_eval_int(f_linearize($2)); } + | '(' term ')' { $$ = f_eval_int(f_linearize($2, 1)); } | CF_SYM_KNOWN { if ($1->class != (SYM_CONSTANT | T_INT)) cf_error("Number constant expected"); $$ = SYM_VAL($1).i; } diff --git a/filter/config.Y b/filter/config.Y index a3acf245..b67ca925 100644 --- a/filter/config.Y +++ b/filter/config.Y @@ -329,7 +329,7 @@ filter_def: conf: filter_eval ; filter_eval: - EVAL term { f_eval_int(f_linearize($2)); } + EVAL term { f_eval_int(f_linearize($2, 1)); } ; conf: custom_attr ; @@ -453,7 +453,7 @@ where_filter: function_body: function_vars '{' cmds '}' { - $$ = f_linearize($3); + $$ = f_linearize($3, 0); $$->vars = $1; } ; @@ -537,7 +537,7 @@ 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, 1), cfg_mem, &($$)) > F_RETURN) cf_error("Runtime error"); if (!f_valid_set_type($$.type)) cf_error("Set-incompatible type"); } | CF_SYM_KNOWN { @@ -549,13 +549,13 @@ set_atom: switch_atom: NUM { $$.type = T_INT; $$.val.i = $1; } - | '(' term ')' { $$.type = T_INT; $$.val.i = f_eval_int(f_linearize($2)); } + | '(' term ')' { $$.type = T_INT; $$.val.i = f_eval_int(f_linearize($2, 1)); } | fipa { $$ = $1; } | ENUM { $$.type = pair_a($1); $$.val.i = pair_b($1); } ; cnum: - term { $$ = f_eval_int(f_linearize($1)); } + term { $$ = f_eval_int(f_linearize($1, 1)); } pair_item: '(' cnum ',' cnum ')' { $$ = f_new_pair_item($2, $2, $4, $4); } @@ -642,7 +642,7 @@ switch_body: /* EMPTY */ { $$ = NULL; } | switch_body switch_items ':' cmds { /* Fill data fields */ struct f_tree *t; - struct f_line *line = f_linearize($4); + struct f_line *line = f_linearize($4, 0); for (t = $2; t; t = t->left) t->data = line; $$ = f_merge_items($1, $2); @@ -651,7 +651,7 @@ switch_body: /* EMPTY */ { $$ = NULL; } struct f_tree *t = f_new_tree(); t->from.type = t->to.type = T_VOID; t->right = t; - t->data = f_linearize($3); + t->data = f_linearize($3, 0); $$ = f_merge_items($1, t); } ; diff --git a/filter/decl.m4 b/filter/decl.m4 index 3d118e34..4c56cd9c 100644 --- a/filter/decl.m4 +++ b/filter/decl.m4 @@ -216,7 +216,7 @@ whati->f$1 = f$1; FID_DUMP_BODY()m4_dnl f_dump_line(item->fl$1, indent + 1); FID_LINEARIZE_BODY()m4_dnl -item->fl$1 = f_linearize(whati->f$1); +item->fl$1 = f_linearize(whati->f$1, $2); FID_SAME_BODY()m4_dnl if (!f_same(f1->fl$1, f2->fl$1)) return 0; FID_ITERATE_BODY()m4_dnl @@ -568,7 +568,7 @@ FID_WR_PUT(8) } struct f_line * -f_linearize_concat(const struct f_inst * const inst[], uint count) +f_linearize_concat(const struct f_inst * const inst[], uint count, uint results) { uint len = 0; for (uint i=0; ilen = linearize(out, inst[i], out->len); + out->results = results; + #ifdef LOCAL_DEBUG f_dump_line(out, 0); #endif diff --git a/filter/f-inst.c b/filter/f-inst.c index e75b5e01..5b8310c3 100644 --- a/filter/f-inst.c +++ b/filter/f-inst.c @@ -64,7 +64,7 @@ * m4_dnl ARG_ANY(num); argument with no type check accessible by v1, v2, v3 * m4_dnl ARG_TYPE(num, type); just declare the type of argument * m4_dnl VARARG; variable-length argument list; accessible by vv(i) and whati->varcount - * m4_dnl LINE(num, unused); this argument has to be converted to its own f_line + * m4_dnl LINE(num, out); this argument has to be converted to its own f_line * m4_dnl SYMBOL; symbol handed from config * m4_dnl STATIC_ATTR; static attribute definition * m4_dnl DYNAMIC_ATTR; dynamic attribute definition @@ -298,7 +298,7 @@ RESULT_TYPE(T_BOOL); if (v1.val.i) - LINE(2,0); + LINE(2,1); else RESULT_VAL(v1); } @@ -308,7 +308,7 @@ RESULT_TYPE(T_BOOL); if (!v1.val.i) - LINE(2,0); + LINE(2,1); else RESULT_VAL(v1); } @@ -536,7 +536,7 @@ if (v1.val.i) LINE(2,0); else - LINE(3,1); + LINE(3,0); } INST(FI_PRINT, 0, 0) { diff --git a/filter/f-inst.h b/filter/f-inst.h index 58563c79..e35f71c6 100644 --- a/filter/f-inst.h +++ b/filter/f-inst.h @@ -46,14 +46,15 @@ struct f_line { uint len; /* Line length */ u8 args; /* Function: Args required */ u8 vars; + u8 results; /* Results left on stack: cmd -> 0, term -> 1 */ struct f_arg *arg_list; struct f_line_item items[0]; /* The items themselves */ }; /* Convert the f_inst infix tree to the f_line structures */ -struct f_line *f_linearize_concat(const struct f_inst * const inst[], uint count); -static inline struct f_line *f_linearize(const struct f_inst *root) -{ return f_linearize_concat(&root, 1); } +struct f_line *f_linearize_concat(const struct f_inst * const inst[], uint count, uint results); +static inline struct f_line *f_linearize(const struct f_inst *root, uint results) +{ return f_linearize_concat(&root, 1, results); } void f_dump_line(const struct f_line *, uint indent); diff --git a/filter/f-util.c b/filter/f-util.c index 410999a6..fdb314b5 100644 --- a/filter/f-util.c +++ b/filter/f-util.c @@ -37,7 +37,7 @@ struct filter *f_new_where(struct f_inst *where) f_new_inst(FI_DIE, F_REJECT)); struct filter *f = cfg_allocz(sizeof(struct filter)); - f->root = f_linearize(cond); + f->root = f_linearize(cond, 0); return f; } diff --git a/filter/filter.c b/filter/filter.c index e505d570..20a380dc 100644 --- a/filter/filter.c +++ b/filter/filter.c @@ -215,8 +215,7 @@ interpret(struct filter_state *fs, const struct f_line *line, struct f_val *val) } /* End of current line. Drop local variables before exiting. */ - fstk->vcnt -= curline.line->vars; - fstk->vcnt -= curline.line->args; + fstk->vcnt = curline.ventry + curline.line->results; fstk->ecnt--; } diff --git a/nest/config.Y b/nest/config.Y index 17999422..ac599c09 100644 --- a/nest/config.Y +++ b/nest/config.Y @@ -165,7 +165,7 @@ rtrid: idval: NUM { $$ = $1; } - | '(' term ')' { $$ = f_eval_int(f_linearize($2)); } + | '(' term ')' { $$ = f_eval_int(f_linearize($2, 1)); } | IP4 { $$ = ip4_to_u32($1); } | CF_SYM_KNOWN { if ($1->class == (SYM_CONSTANT | T_INT) || $1->class == (SYM_CONSTANT | T_QUAD)) @@ -860,7 +860,7 @@ CF_CLI(DUMP FILTER ALL,,, [[Dump all filters in linearized form]]) { filters_dump_all(); cli_msg(0, ""); } ; CF_CLI(EVAL, term, , [[Evaluate an expression]]) -{ cmd_eval(f_linearize($2)); } ; +{ cmd_eval(f_linearize($2, 1)); } ; CF_CLI_HELP(ECHO, ..., [[Control echoing of log messages]]) CF_CLI(ECHO, echo_mask echo_size, (all | off | { debug|trace|info|remote|warning|error|auth [, ...] }) [], [[Control echoing of log messages]]) { diff --git a/proto/static/config.Y b/proto/static/config.Y index 41e10dbf..9d26ee82 100644 --- a/proto/static/config.Y +++ b/proto/static/config.Y @@ -40,7 +40,7 @@ static_route_finish(void) if (net_type_match(this_srt->net, NB_DEST) == !this_srt->dest) cf_error("Unexpected or missing nexthop/type"); - this_srt->cmds = f_linearize(this_srt_cmds); + this_srt->cmds = f_linearize(this_srt_cmds, 0); } CF_DECLS -- cgit v1.2.3