diff options
81 files changed, 3423 insertions, 1194 deletions
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index 7809fecd..0a758cff 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -134,21 +134,11 @@ docker_fedora-34-amd64: IMG_NAME: "fedora-34-amd64" <<: *docker_build -docker_centos-7-amd64: - variables: - IMG_NAME: "centos-7-amd64" - <<: *docker_build - docker_centos-8-amd64: variables: IMG_NAME: "centos-8-amd64" <<: *docker_build -docker_ubuntu-14_04-amd64: - variables: - IMG_NAME: "ubuntu-14.04-amd64" - <<: *docker_build - docker_ubuntu-16_04-amd64: variables: IMG_NAME: "ubuntu-16.04-amd64" @@ -312,18 +302,10 @@ build-fedora-34-amd64: <<: *build-linux image: registry.nic.cz/labs/bird:fedora-33-amd64 -build-centos-7-amd64: - <<: *build-linux - image: registry.nic.cz/labs/bird:centos-7-amd64 - build-centos-8-amd64: <<: *build-linux image: registry.nic.cz/labs/bird:centos-8-amd64 -build-ubuntu-14_04-amd64: - <<: *build-linux - image: registry.nic.cz/labs/bird:ubuntu-14.04-amd64 - build-ubuntu-16_04-amd64: <<: *build-linux image: registry.nic.cz/labs/bird:ubuntu-16.04-amd64 @@ -466,14 +448,7 @@ pkg-fedora-33-amd64: pkg-fedora-34-amd64: <<: *pkg-rpm needs: [build-fedora-34-amd64] - image: registry.nic.cz/labs/bird:fedora-34-amd64 - -pkg-centos-7-amd64: - <<: *pkg-rpm-wa - variables: - LC_ALL: en_US.UTF-8 - needs: [build-centos-7-amd64] - image: registry.nic.cz/labs/bird:centos-7-amd64 + image: registry.labs.nic.cz/labs/bird:fedora-34-amd64 pkg-centos-8-amd64: <<: *pkg-rpm-wa @@ -27,9 +27,9 @@ Requirements For compiling BIRD you need these programs and libraries: - - GNU C Compiler (or LLVM Clang) + - GNU C Compiler (or LLVM Clang) capable of compiling C11 code - GNU Make - - GNU Bison + - GNU Bison (at least 3.0) - GNU M4 - Flex @@ -1,3 +1,11 @@ +Version 2.0.10 (2022-06-16) + o BGP performance improvements + o BFD: New 'strict bind' option + o RPKI: VRF support + o Allow use of 240.0.0.0/4 as a private range + o BIRD client uses exit status to report errors + o Important bugfixes + Version 2.0.9 (2022-02-09) o BGP: Flowspec validation procedure o Babel: MAC authentication support @@ -1,5 +1,6 @@ dnl ** Additional Autoconf tests for BIRD configure script dnl ** (c) 1999 Martin Mares <mj@ucw.cz> +dnl ** (c) 2021 Maria Matejka <mq@jmq.cz> AC_DEFUN([BIRD_CHECK_POINTER_ALIGNMENT], [ @@ -35,14 +36,23 @@ AC_DEFUN([BIRD_CHECK_THREAD_LOCAL], AC_COMPILE_IFELSE([ AC_LANG_PROGRAM( [ - _Thread_local static int x = 42; + static _Thread_local int x = 42; ], [] ) ], [bird_cv_thread_local=yes], + [AC_COMPILE_IFELSE([ + AC_LANG_PROGRAM( + [ + static __thread int x = 42; + ], + [] + ) + ], + [bird_cv_thread_local=__thread], [bird_cv_thread_local=no] - ) + )]) ) ]) diff --git a/bird-gdb.py b/bird-gdb.py index 62c0ec87..077703f9 100644 --- a/bird-gdb.py +++ b/bird-gdb.py @@ -122,7 +122,7 @@ class BIRDFLinePrinter(BIRDPrinter): "n": n, "code": str(self.val['items'][n]['fi_code']), } if n % 8 == 0 else str(self.val['items'][n]['fi_code']) for n in range(cnt)])) - + class BIRDFExecStackPrinter(BIRDPrinter): "Print BIRD's struct f_exec_stack" @@ -140,6 +140,118 @@ class BIRDFExecStackPrinter(BIRDPrinter): "n": n } for n in range(cnt-1, -1, -1) ]) + +class BIRD: + def skip_back(t, i, v): + if isinstance(t, str): + t = gdb.lookup_type(t) + elif isinstance(t, gdb.Value): + t = gdb.lookup_type(t.string()) + elif not isinstance(t, gdb.Type): + raise Exception(f"First argument of skip_back(t, i, v) must be a type, got {type(t)}") + + t = t.strip_typedefs() + nullptr = gdb.Value(0).cast(t.pointer()) + + if isinstance(i, gdb.Value): + i = i.string() + elif not isinstance(i, str): + raise Exception(f"Second argument of skip_back(t, i, v) must be a item name, got {type(i)}") + + if not isinstance(v, gdb.Value): + raise Exception(f"Third argument of skip_back(t, i, v) must be a value, got {type(v)}") + if v.type.code != gdb.TYPE_CODE_PTR and v.type.code != gdb.TYPE_CODE_REF: + raise Exception(f"Third argument of skip_back(t, i, v) must be a pointer, is {v.type} ({v.type.code})") + if v.type.target().strip_typedefs() != nullptr[i].type: + raise Exception(f"Third argument of skip_back(t, i, v) points to type {v.type.target().strip_typedefs()}, should be {nullptr[i].type}") + + uintptr_t = gdb.lookup_type("uintptr_t") + taddr = v.dereference().address.cast(uintptr_t) - nullptr[i].address.cast(uintptr_t) + return gdb.Value(taddr).cast(t.pointer()) + + class skip_back_gdb(gdb.Function): + "Given address of a structure item, returns address of the structure, as the SKIP_BACK macro does" + def __init__(self): + gdb.Function.__init__(self, "SKIP_BACK") + + def invoke(self, t, i, v): + return BIRD.skip_back(t, i, v) + + +BIRD.skip_back_gdb() + + +class BIRDList: + def __init__(self, val): + ltype = val.type.strip_typedefs() + if ltype.code != gdb.TYPE_CODE_UNION or ltype.tag != "list": + raise Exception(f"Not a list, is type {ltype}") + + self.head = val["head"] + self.tail_node = val["tail_node"] + + if str(self.head.address) == '0x0': + raise Exception("List head is NULL") + + if str(self.tail_node["prev"].address) == '0x0': + raise Exception("List tail is NULL") + + def walk(self, do): + cur = self.head + while cur.dereference() != self.tail_node: + do(cur) + cur = cur.dereference()["next"] + + +class BIRDListLength(gdb.Function): + """Returns length of the list, as in + print $list_length(routing_tables)""" + def __init__(self): + super(BIRDListLength, self).__init__("list_length") + + def count(self, _): + self.cnt += 1 + + def invoke(self, l): + self.cnt = 0 + BIRDList(l).walk(self.count) + return self.cnt + +BIRDListLength() + +class BIRDListItem(gdb.Function): + """Returns n-th item of the list.""" + def __init__(self): + super(BIRDListItem, self).__init__("list_item") + + class BLException(Exception): + def __init__(self, node, msg): + Exception.__init__(self, msg) + self.node = node + + def count(self, node): + if self.cnt == self.pos: + raise self.BLException(node, "Node found") + + self.cnt += 1 + + def invoke(self, l, n, t=None, item="n"): + self.cnt = 0 + self.pos = n + bl = BIRDList(l) + try: + bl.walk(self.count) + except self.BLException as e: + if t is None: + return e.node + else: + return BIRD.skip_back(t, item, e.node) + + raise Exception("List too short") + +BIRDListItem() + + def register_printers(objfile): objfile.pretty_printers.append(BIRDFInstPrinter.lookup) objfile.pretty_printers.append(BIRDFValPrinter.lookup) diff --git a/conf/cf-lex.l b/conf/cf-lex.l index 11bcdb18..04e0b3a5 100644 --- a/conf/cf-lex.l +++ b/conf/cf-lex.l @@ -577,6 +577,8 @@ check_eof(void) return 0; } +static inline void cf_swap_soft_scope(void); + static struct symbol * cf_new_symbol(const byte *c) { @@ -586,6 +588,8 @@ cf_new_symbol(const byte *c) if (l > SYM_MAX_LEN) cf_error("Symbol too long"); + cf_swap_soft_scope(); + s = cfg_allocz(sizeof(struct symbol) + l + 1); *s = (struct symbol) { .scope = conf_this_scope, .class = SYM_VOID, }; strcpy(s->name, c); @@ -676,8 +680,8 @@ cf_localize_symbol(struct symbol *sym) return sym; /* If the scope is the current, it is already defined in this scope. */ - if (sym->scope == conf_this_scope) - cf_error("Symbol already defined"); + if (cf_symbol_is_local(sym)) + cf_error("Symbol '%s' already defined", sym->name); /* Not allocated here yet, doing it now. */ return cf_new_symbol(sym->name); @@ -839,6 +843,8 @@ cf_push_scope(struct symbol *sym) void cf_pop_scope(void) { + ASSERT(!conf_this_scope->soft_scopes); + conf_this_scope->active = 0; conf_this_scope = conf_this_scope->next; @@ -846,6 +852,52 @@ cf_pop_scope(void) } /** + * cf_push_soft_scope - enter new soft scope + * + * If we want to enter a new anonymous scope that most likely will not contain + * any symbols, we can use cf_push_soft_scope() insteas of cf_push_scope(). + * Such scope will be converted to a regular scope on first use. + */ +void +cf_push_soft_scope(void) +{ + if (conf_this_scope->soft_scopes < 0xfe) + conf_this_scope->soft_scopes++; + else + cf_push_scope(NULL); +} + +/** + * cf_pop_soft_scope - leave a soft scope + * + * Leave a soft scope entered by cf_push_soft_scope(). + */ +void +cf_pop_soft_scope(void) +{ + if (conf_this_scope->soft_scopes) + conf_this_scope->soft_scopes--; + else + cf_pop_scope(); +} + +/** + * cf_swap_soft_scope - convert soft scope to regular scope + * + * Soft scopes cannot hold symbols, so they must be converted to regular scopes + * on first use. It is done automatically by cf_new_symbol(). + */ +static inline void +cf_swap_soft_scope(void) +{ + if (conf_this_scope->soft_scopes) + { + conf_this_scope->soft_scopes--; + cf_push_scope(NULL); + } +} + +/** * cf_symbol_class_name - get name of a symbol class * @sym: symbol * diff --git a/conf/conf.c b/conf/conf.c index 580a6472..17424402 100644 --- a/conf/conf.c +++ b/conf/conf.c @@ -140,6 +140,7 @@ config_parse(struct config *c) protos_preconfig(c); rt_preconfig(c); cf_parse(); + rt_postconfig(c); if (EMPTY_LIST(c->protos)) cf_error("No protocol is specified in the config file"); diff --git a/conf/conf.h b/conf/conf.h index 4ccaa54e..50e01bf5 100644 --- a/conf/conf.h +++ b/conf/conf.h @@ -44,7 +44,7 @@ struct config { int cli_debug; /* Tracing of CLI connections and commands */ int latency_debug; /* I/O loop tracks duration of each event */ - int pipe_debug; /* Track route propagation through pipes */ + int table_debug; /* Track route propagation through tables */ u32 latency_limit; /* Events with longer duration are logged (us) */ u32 watchdog_warning; /* I/O loop watchdog limit for warning (us) */ u32 watchdog_timeout; /* Watchdog timeout (in seconds, 0 = disabled) */ @@ -136,7 +136,8 @@ struct sym_scope { HASH(struct symbol) hash; /* Local symbol hash */ uint slots; /* Variable slots */ - int active; /* Currently entered */ + byte active; /* Currently entered */ + byte soft_scopes; /* Number of soft scopes above */ }; extern struct sym_scope *global_root_scope; @@ -202,6 +203,9 @@ struct symbol *cf_get_symbol(const byte *c); struct symbol *cf_default_name(char *template, int *counter); struct symbol *cf_localize_symbol(struct symbol *sym); +static inline int cf_symbol_is_local(struct symbol *sym) +{ return (sym->scope == conf_this_scope) && !conf_this_scope->soft_scopes; } + /** * cf_define_symbol - define meaning of a symbol * @sym: symbol to be defined @@ -225,6 +229,9 @@ struct symbol *cf_localize_symbol(struct symbol *sym); void cf_push_scope(struct symbol *); void cf_pop_scope(void); +void cf_push_soft_scope(void); +void cf_pop_soft_scope(void); + char *cf_symbol_class_name(struct symbol *sym); /* Parser */ diff --git a/conf/confbase.Y b/conf/confbase.Y index 58890cd6..241c332d 100644 --- a/conf/confbase.Y +++ b/conf/confbase.Y @@ -76,6 +76,7 @@ CF_DECLS struct f_attr_bit fab; struct f_lval flv; struct f_line *fl; + struct f_arg *fa; const struct filter *f; struct f_tree *e; struct f_trie *trie; @@ -111,7 +112,7 @@ CF_DECLS %type <i> expr bool pxlen4 %type <time> expr_us time %type <a> ipa -%type <net> net_ip4_ net_ip6_ net_ip6 net_ip_ net_ip net_or_ipa +%type <net> net_ip4_ net_ip4 net_ip6_ net_ip6 net_ip_ net_ip net_or_ipa %type <net_ptr> net_ net_any net_vpn4_ net_vpn6_ net_vpn_ net_roa4_ net_roa6_ net_roa_ net_ip6_sadr_ net_mpls_ %type <ad> label_stack_start label_stack @@ -154,14 +155,14 @@ conf: definition ; definition: DEFINE symbol '=' term ';' { struct f_val val; - if (f_eval(f_linearize($4), &val) > F_RETURN) cf_error("Runtime error"); + if (f_eval(f_linearize($4, 1), &val) > F_RETURN) cf_error("Runtime error"); cf_define_symbol($2, SYM_CONSTANT | val.type, val, lp_val_copy(cfg_mem, &val)); } ; expr: NUM - | '(' term ')' { $$ = f_eval_int(f_linearize($2)); } + | '(' term ')' { $$ = f_eval_int(f_linearize($2, 1)); } | symbol_known { if ($1->class != (SYM_CONSTANT | T_INT)) cf_error("Number constant expected"); $$ = SYM_VAL($1).i; } @@ -307,6 +308,15 @@ net_: /* Networks - regular */ +net_ip4: + net_ip4_ + | CF_SYM_KNOWN { + if (($1->class != (SYM_CONSTANT | T_NET)) || (SYM_VAL($1).net->type != NET_IP4)) + cf_error("IPv4 network constant expected"); + $$ = * SYM_VAL($1).net; + } + ; + net_ip6: net_ip6_ | CF_SYM_KNOWN { diff --git a/conf/flowspec.Y b/conf/flowspec.Y index 56a7c5dc..dbdbdda5 100644 --- a/conf/flowspec.Y +++ b/conf/flowspec.Y @@ -142,7 +142,7 @@ flow_frag_opts: ; flow4_item: - flow_srcdst net_ip { + flow_srcdst net_ip4 { flow_builder_set_type(this_flow, $1); flow_builder4_add_pfx(this_flow, (net_addr_ip4 *) &($2)); } diff --git a/configure.ac b/configure.ac index 321bed95..330add87 100644 --- a/configure.ac +++ b/configure.ac @@ -36,12 +36,6 @@ AC_ARG_ENABLE([memcheck], [enable_memcheck=yes] ) -AC_ARG_ENABLE([pthreads], - [AS_HELP_STRING([--enable-pthreads], [enable POSIX threads support @<:@try@:>@])], - [], - [enable_pthreads=try] -) - AC_ARG_ENABLE([libssh], [AS_HELP_STRING([--enable-libssh], [enable LibSSH support in RPKI @<:@try@:>@])], [], @@ -125,25 +119,19 @@ if test -z "$GCC" ; then fi BIRD_CHECK_THREAD_LOCAL -if test "$bird_cv_thread_local" = yes ; then - AC_DEFINE([HAVE_THREAD_LOCAL], [1], [Define to 1 if _Thread_local is available]) +if test "$bird_cv_thread_local" = no ; then + AC_MSG_ERROR([This program requires thread local storage.]) +elif test "$bird_cv_thread_local" != yes ; then + AC_DEFINE_UNQUOTED([_Thread_local], [$bird_cv_thread_local], [Legacy _Thread_local]) fi -if test "$enable_pthreads" != no ; then - BIRD_CHECK_PTHREADS +BIRD_CHECK_PTHREADS - if test "$bird_cv_lib_pthreads" = yes ; then - AC_DEFINE([USE_PTHREADS], [1], [Define to 1 if pthreads are enabled]) - CFLAGS="$CFLAGS -pthread" - LDFLAGS="$LDFLAGS -pthread" - proto_bfd=bfd - elif test "$enable_pthreads" = yes ; then - AC_MSG_ERROR([POSIX threads not available.]) - fi - - if test "$enable_pthreads" = try ; then - enable_pthreads="$bird_cv_lib_pthreads" - fi +if test "$bird_cv_lib_pthreads" = yes ; then + CFLAGS="$CFLAGS -pthread" + LDFLAGS="$LDFLAGS -pthread" +else + AC_MSG_ERROR([POSIX threads not available.]) fi # This is assumed to be necessary for proper BIRD build @@ -304,8 +292,7 @@ if test "$enable_mpls_kernel" != no ; then fi fi -all_protocols="$proto_bfd babel bgp mrt ospf perf pipe radv rip rpki static" - +all_protocols="bfd babel bgp mrt ospf perf pipe radv rip rpki static" all_protocols=`echo $all_protocols | sed 's/ /,/g'` if test "$with_protocols" = all ; then @@ -350,10 +337,16 @@ case $sysdesc in ;; esac -AC_CHECK_HEADERS_ONCE([alloca.h syslog.h]) -AC_CHECK_HEADER([sys/mman.h], [AC_DEFINE([HAVE_MMAP], [1], [Define to 1 if mmap() is available.])]) +AC_CHECK_HEADERS_ONCE([alloca.h syslog.h stdatomic.h]) +AC_CHECK_HEADER([sys/mman.h], [AC_DEFINE([HAVE_MMAP], [1], [Define to 1 if mmap() is available.])], have_mman=no) +AC_CHECK_FUNC([aligned_alloc], [AC_DEFINE([HAVE_ALIGNED_ALLOC], [1], [Define to 1 if aligned_alloc() is available.])], have_aligned_alloc=no) AC_CHECK_MEMBERS([struct sockaddr.sa_len], [], [], [#include <sys/socket.h>]) +if test "$have_aligned_alloc" = "no" && test "$have_mman" = "no" ; then + AC_MSG_ERROR([No means of aligned alloc found. Need mmap() or aligned_alloc().]) +fi + + AC_C_BIGENDIAN( [AC_DEFINE([CPU_BIG_ENDIAN], [1], [Define to 1 if cpu is big endian])], [AC_DEFINE([CPU_LITTLE_ENDIAN], [1], [Define to 1 if cpu is little endian])], @@ -409,7 +402,7 @@ if test "$enable_debug" = yes ; then fi fi - if test "enable_debug_expensive" = yes ; then + if test "$enable_debug_expensive" = yes ; then AC_DEFINE([ENABLE_EXPENSIVE_CHECKS], [1], [Define to 1 if you want to run expensive consistency checks.]) fi fi @@ -474,7 +467,6 @@ AC_MSG_RESULT([ Object directory: $objdir]) AC_MSG_RESULT([ Iproute2 directory: $iproutedir]) AC_MSG_RESULT([ System configuration: $sysdesc]) AC_MSG_RESULT([ Debugging: $enable_debug]) -AC_MSG_RESULT([ POSIX threads: $enable_pthreads]) AC_MSG_RESULT([ Routing protocols: $protocols]) AC_MSG_RESULT([ LibSSH support in RPKI: $enable_libssh]) AC_MSG_RESULT([ Kernel MPLS support: $enable_mpls_kernel]) diff --git a/doc/bird.sgml b/doc/bird.sgml index c9ce670b..a4d7cb0c 100644 --- a/doc/bird.sgml +++ b/doc/bird.sgml @@ -684,6 +684,30 @@ to set options. limit to the settle time from the initial ROA table change even if there are consecutive updates gradually renewing the settle time. Default: 20 s. + + <tag><label id="rtable-gc-threshold">gc threshold <m/number/</tag> + Specify a minimum amount of removed networks that triggers a garbage + collection (GC) cycle. Default: 1000. + + <tag><label id="rtable-gc-period">gc period <m/time/</tag> + Specify a period of time between consecutive GC cycles. When there is a + significant amount of route withdraws, GC cycles are executed repeatedly + with given period time (with some random factor). When there is just + small amount of changes, GC cycles are not executed. In extensive route + server setups, running GC on hundreds of full BGP routing tables can + take significant amount of time, therefore they should use higher GC + periods. Default: adaptive, based on number of routing tables in the + configuration. From 10 s (with <= 25 routing tables) up to 600 s (with + >= 1500 routing tables). + + <tag><label id="rtable-cork-threshold">cork threshold <m/number/ <m/number/</tag> + Too many pending exports may lead to memory bloating. In such cases, + BIRD tries to relieve the memory pressure by pausing some routines until + the queue sizes get low enough. This option allows the user to set the + thresholds; first value is the low threshold (when to resume), the + second one is the high threshold (when to pause). The higher is the + threshold, the more memory can get used. In most cases, the defaults + should work for you. Default: 128, 512. </descrip> @@ -1247,8 +1271,8 @@ this: <code> filter not_too_far -int var; { + int var; if defined( rip_metric ) then var = rip_metric; else { @@ -1277,9 +1301,9 @@ local variables. Recursion is not allowed. Function definitions look like this: <code> function name () -int local_variable; { - local_variable = 5; + int local_variable; + int another_variable = 5; } function with_parameters (int parameter) @@ -1288,16 +1312,19 @@ function with_parameters (int parameter) } </code> -<p>Unlike in C, variables are declared after the <cf/function/ line, but before -the first <cf/{/. You can't declare variables in nested blocks. Functions are -called like in C: <cf>name(); with_parameters(5);</cf>. Function may return -values using the <cf>return <m/[expr]/</cf> command. Returning a value exits -from current function (this is similar to C). +<p>Like in C programming language, variables are declared inside function body, +either at the beginning, or mixed with other statements. Declarations may +contain initialization. You can also declare variables in nested blocks, such +variables have scope restricted to such block. There is a deprecated syntax to +declare variables after the <cf/function/ line, but before the first <cf/{/. +Functions are called like in C: <cf>name(); with_parameters(5);</cf>. Function +may return values using the <cf>return <m/[expr]/</cf> command. Returning a +value exits from current function (this is similar to C). -<p>Filters are defined in a way similar to functions except they can't have +<p>Filters are defined in a way similar to functions except they cannot have explicit parameters. They get a route table entry as an implicit parameter, it is also passed automatically to any functions called. The filter must terminate -with either <cf/accept/ or <cf/reject/ statement. If there's a runtime error in +with either <cf/accept/ or <cf/reject/ statement. If there is a runtime error in filter, the route is rejected. <p>A nice trick to debug filters is to use <cf>show route filter <m/name/</cf> @@ -1667,7 +1694,8 @@ prefix and an ASN as arguments. <sect>Control structures <label id="control-structures"> -<p>Filters support two control structures: conditions and case switches. +<p>Filters support several control structures: conditions, for loops and case +switches. <p>Syntax of a condition is: <cf>if <M>boolean expression</M> then <m/commandT/; else <m/commandF/;</cf> and you can use <cf>{ <m/command1/; <m/command2/; @@ -1675,6 +1703,14 @@ else <m/commandF/;</cf> and you can use <cf>{ <m/command1/; <m/command2/; omitted. If the <cf><m>boolean expression</m></cf> is true, <m/commandT/ is executed, otherwise <m/commandF/ is executed. +<p>For loops allow to iterate over elements in compound data like BGP paths or +community lists. The syntax is: <cf>for [ <m/type/ ] <m/variable/ in <m/expr/ +do <m/command/;</cf> and you can also use compound command like in conditions. +The expression is evaluated to a compound data, then for each element from such +data the command is executed with the item assigned to the variable. A variable +may be an existing one (when just name is used) or a locally defined (when type +and name is used). In both cases, it must have the same type as elements. + <p>The <cf>case</cf> is similar to case from Pascal. Syntax is <cf>case <m/expr/ { else: | <m/num_or_prefix [ .. num_or_prefix]/: <m/statement/ ; [ ... ] }</cf>. The expression after <cf>case</cf> can be of any type which can be @@ -1687,16 +1723,21 @@ neither of the <cf/:/ clauses, the statements after <cf/else:/ are executed. <p>Here is example that uses <cf/if/ and <cf/case/ structures: <code> +if 1234 = i then printn "."; else { + print "not 1234"; + print "You need {} around multiple commands"; +} + +for int asn in bgp_path do { + printn "ASN: ", asn; + if asn < 65536 then print " (2B)"; else print " (4B)"; +} + case arg1 { 2: print "two"; print "I can do more commands without {}"; 3 .. 5: print "three to five"; else: print "something else"; } - -if 1234 = i then printn "."; else { - print "not 1234"; - print "You need {} around multiple commands"; -} </code> diff --git a/filter/config.Y b/filter/config.Y index 8cecf936..5ba4f7e6 100644 --- a/filter/config.Y +++ b/filter/config.Y @@ -32,6 +32,36 @@ static inline u32 pair_b(u32 p) { return p & 0xFFFF; } f_new_inst(FI_EA_SET, f_new_inst(fi_code, f_new_inst(FI_DEFAULT, f_new_inst(FI_EA_GET, da), f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_INT, .val.i = def })), arg), da) +static int +f_new_var(struct sym_scope *s) +{ + /* + * - A variable is an offset on vstack from vbase. + * - Vbase is set on filter start / function call. + * - Scopes contain anonymous scopes (blocks) inside filter/function scope + * - Each scope knows number of vars in that scope + * - Offset is therefore a sum of 'slots' up to named scope + * - New variables are added on top of vstk, so intermediate values cannot + * be there during FI_VAR_INIT. I.e. no 'var' inside 'term'. + * - Also, each f_line must always have its scope, otherwise a variable may + * be defined but not initialized if relevant f_line is not executed. + */ + + int offset = s->slots++; + + while (!s->name) + { + s = s->next; + ASSERT(s); + offset += s->slots; + } + + if (offset >= 0xff) + cf_error("Too many variables, at most 255 allowed"); + + return offset; +} + /* * Sets and their items are during parsing handled as lists, linked * through left ptr. The first item in a list also contains a pointer @@ -276,7 +306,7 @@ assert_assign(struct f_lval *lval, struct f_inst *expr, const char *start, const checker = f_new_inst(FI_EQ, expr, getter); setter->next = checker; - + return assert_done(setter, start, end); } @@ -287,6 +317,7 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN, INT, BOOL, IP, TYPE, PREFIX, RD, PAIR, QUAD, EC, LC, SET, STRING, BGPMASK, BGPPATH, CLIST, ECLIST, LCLIST, IF, THEN, ELSE, CASE, + FOR, IN, DO, TRUE, FALSE, RT, RO, UNKNOWN, GENERIC, FROM, GW, NET, MASK, PROTO, SCOPE, DEST, IFNAME, IFINDEX, WEIGHT, GW_MPLS, ROA_CHECK, ASN, SRC, DST, @@ -305,21 +336,23 @@ CF_KEYWORDS(FUNCTION, PRINT, PRINTN, UNSET, RETURN, %nonassoc ELSE %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 <x> term cmd cmd_var cmds cmds_scoped constant constructor print_list var var_init var_list function_call symbol_value bgp_path_expr bgp_path bgp_path_tail %type <fsa> static_attr %type <fab> attr_bit %type <f> filter where_filter %type <fl> filter_body function_body %type <flv> lvalue -%type <i> type function_args function_vars +%type <i> type function_vars +%type <fa> function_argsn function_args %type <ecs> ec_kind -%type <fret> break_command +%type <fret> break_command %type <i32> cnum %type <e> pair_item ec_item lc_item set_item switch_item set_items switch_items switch_body %type <trie> fprefix_set %type <v> set_atom switch_atom fipa %type <px> fprefix %type <t> get_cf_position +%type <s> for_var CF_GRAMMAR @@ -343,7 +376,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 ; @@ -425,25 +458,28 @@ type: ; function_argsn: - /* EMPTY */ + /* EMPTY */ { $$ = NULL; } | function_argsn type symbol ';' { if ($3->scope->slots >= 0xfe) cf_error("Too many declarations, at most 255 allowed"); - cf_define_symbol($3, SYM_VARIABLE | $2, offset, $3->scope->slots++); + $$ = cfg_alloc(sizeof(struct f_arg)); + $$->arg = cf_define_symbol($3, SYM_VARIABLE | $2, offset, sym_->scope->slots++); + $$->next = $1; } ; function_args: - '(' ')' { $$ = 0; } + '(' ')' { $$ = NULL; } | '(' function_argsn type symbol ')' { - cf_define_symbol($4, SYM_VARIABLE | $3, offset, $4->scope->slots++); - $$ = $4->scope->slots; + $$ = cfg_alloc(sizeof(struct f_arg)); + $$->arg = cf_define_symbol($4, SYM_VARIABLE | $3, offset, sym_->scope->slots++); + $$->next = $2; } ; function_vars: /* EMPTY */ { $$ = 0; } | function_vars type symbol ';' { - cf_define_symbol($3, SYM_VARIABLE | $2, offset, $3->scope->slots++); + cf_define_symbol($3, SYM_VARIABLE | $2, offset, f_new_var(sym_->scope)); $$ = $1 + 1; } ; @@ -471,20 +507,35 @@ where_filter: function_body: function_vars '{' cmds '}' { - $$ = f_linearize($3); + $$ = f_linearize($3, 0); $$->vars = $1; } ; 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 { - DBG("Definition of function %s with %u args and %u local vars.\n", $2->name, $4, $5->vars); - $5->args = $4; - $2->function = $5; + } 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 = dummy->arg_list; + dummy->arg_list = tmp; + dummy->args++; + } + } function_body { + $6->args = $2->function->args; + $6->arg_list = $2->function->arg_list; + $2->function = $6; cf_pop_scope(); } ; @@ -495,7 +546,11 @@ cmds: /* EMPTY */ { $$ = NULL; } | cmds_int { $$ = $1.begin; } ; -cmd_prep: cmd { +cmds_scoped: { cf_push_soft_scope(); } cmds { cf_pop_soft_scope(); $$ = $2; } ; + +cmd_var: var | cmd ; + +cmd_prep: cmd_var { $$.begin = $$.end = $1; if ($1) while ($$.end->next) @@ -517,15 +572,6 @@ cmds_int: cmd_prep } ; -block: - cmd { - $$=$1; - } - | '{' cmds '}' { - $$=$2; - } - ; - /* * Complex types, their bison value is struct f_val */ @@ -549,7 +595,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), &($$)) > F_RETURN) cf_error("Runtime error"); + if (f_eval(f_linearize($2, 1), &($$)) > F_RETURN) cf_error("Runtime error"); if (!f_valid_set_type($$.type)) cf_error("Set-incompatible type"); } | symbol_known { @@ -561,13 +607,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); } @@ -651,19 +697,19 @@ fprefix_set: ; switch_body: /* EMPTY */ { $$ = NULL; } - | switch_body switch_items ':' cmds { + | switch_body switch_items ':' cmds_scoped { /* 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); } - | switch_body ELSECOL cmds { + | switch_body ELSECOL cmds_scoped { 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); } ; @@ -680,6 +726,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; @@ -699,6 +746,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), }); @@ -722,27 +770,22 @@ var_list: /* EMPTY */ { $$ = NULL; } | var_list ',' term { $$ = $3; $$->next = $1; } function_call: - symbol_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."); - struct f_inst *fc = f_new_inst(FI_CALL, $1); - uint args = 0; + /* Revert the var_list */ + struct f_inst *args = NULL; while ($3) { - args++; - struct f_inst *tmp = $3->next; - $3->next = fc; + struct f_inst *tmp = $3; + $3 = $3->next; - fc = $3; - $3 = tmp; + tmp->next = args; + args = tmp; } - if (args != $1->function->args) - cf_error("Function call '%s' got %u arguments, need %u arguments.", - $1->name, args, $1->function->args); - - $$ = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_VOID }); - $$->next = fc; + $$ = f_new_inst(FI_CALL, args, $1); } ; @@ -866,13 +909,44 @@ print_list: /* EMPTY */ { $$ = NULL; } } ; +var_init: + /* empty */ { $$ = f_new_inst(FI_CONSTANT, (struct f_val) { }); } + | '=' term { $$ = $2; } + ; + +var: + type symbol var_init ';' { + struct symbol *sym = cf_define_symbol($2, SYM_VARIABLE | $1, offset, f_new_var(sym_->scope)); + $$ = f_new_inst(FI_VAR_INIT, $3, sym); + } + +for_var: + type symbol { $$ = cf_define_symbol($2, SYM_VARIABLE | $1, offset, f_new_var(sym_->scope)); } + | CF_SYM_KNOWN { $$ = $1; cf_assert_symbol($1, SYM_VARIABLE); } + ; + cmd: - IF term THEN block { + '{' cmds_scoped '}' { + $$ = $2; + } + | IF term THEN cmd { $$ = f_new_inst(FI_CONDITION, $2, $4, NULL); } - | IF term THEN block ELSE block { + | IF term THEN cmd ELSE cmd { $$ = f_new_inst(FI_CONDITION, $2, $4, $6); } + | FOR { + /* Reserve space for walk data on stack */ + cf_push_scope(NULL); + conf_this_scope->slots += 2; + } for_var IN + /* Parse term in the parent scope */ + { conf_this_scope->active = 0; } term { conf_this_scope->active = 1; } + DO cmd { + cf_pop_scope(); + $$ = f_new_inst(FI_FOR_INIT, $6, $3); + $$->next = f_new_inst(FI_FOR_NEXT, $3, $9); + } | symbol_known '=' term ';' { switch ($1->class) { case SYM_VARIABLE_RANGE: @@ -929,7 +1003,7 @@ cmd: | PRINTN print_list ';' { $$ = f_new_inst(FI_PRINT, $2); } - | function_call ';' { $$ = f_new_inst(FI_DROP_RESULT, $1); } + | function_call ';' { $$ = f_new_inst(FI_DROP_RESULT, $1); } | CASE term '{' switch_body '}' { $$ = f_new_inst(FI_SWITCH, $2, build_tree($4)); } diff --git a/filter/data.c b/filter/data.c index 9dab1915..d26b07f5 100644 --- a/filter/data.c +++ b/filter/data.c @@ -71,6 +71,7 @@ btype f_type_element_type(btype t) { switch(t) { + case T_PATH: return T_INT; case T_CLIST: return T_PAIR; case T_ECLIST: return T_EC; case T_LCLIST: return T_LC; @@ -78,6 +79,8 @@ f_type_element_type(btype 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, @@ -90,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 void @@ -178,7 +184,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; } @@ -292,6 +298,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: @@ -528,6 +540,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 23db4a85..c1e7c736 100644 --- a/filter/data.h +++ b/filter/data.h @@ -209,9 +209,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 || 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); @@ -227,7 +229,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; static inline const struct f_val *f_get_empty(btype t) { switch (t) { diff --git a/filter/decl.m4 b/filter/decl.m4 index c59cd7f3..e2472127 100644 --- a/filter/decl.m4 +++ b/filter/decl.m4 @@ -191,6 +191,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()') @@ -216,7 +222,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 @@ -244,9 +250,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; @@ -300,6 +310,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 @@ -375,6 +386,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; } @@ -402,6 +414,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. @@ -505,6 +518,11 @@ f_const_promotion(struct f_inst *arg, btype 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; } @@ -560,7 +578,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; i<count; i++) @@ -572,6 +590,8 @@ f_linearize_concat(const struct f_inst * const inst[], uint count) for (uint i=0; i<count; i++) out->len = linearize(out, inst[i], out->len); + out->results = results; + #ifdef LOCAL_DEBUG f_dump_line(out, 0); #endif @@ -640,6 +660,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 */ btype 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 e7b642ab..fff93517 100644 --- a/filter/f-inst.c +++ b/filter/f-inst.c @@ -62,8 +62,9 @@ * m4_dnl INST(FI_NOP, in, out) { enum value, input args, output args * m4_dnl ARG(num, type); argument, its id (in data fields) and type accessible by v1, v2, v3 * 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 @@ -80,10 +81,17 @@ * m4_dnl ) * * m4_dnl RESULT(type, union-field, value); putting this on value stack + * m4_dnl RESULT_(type, union-field, value); like RESULT(), but do not declare the type * m4_dnl RESULT_VAL(value-struct); pass the struct f_val directly + * m4_dnl RESULT_TYPE(type); just declare the type of result value * m4_dnl RESULT_VOID; return undef * m4_dnl } * + * Note that runtime arguments m4_dnl (ARG*, VARARG) must be defined before + * parse-time arguments m4_dnl (LINE, SYMBOL, ...). During linearization, + * first ones move position in f_line by linearizing arguments first, while + * second ones store data to the current position. + * * Also note that the { ... } blocks are not respected by M4 at all. * If you get weird unmatched-brace-pair errors, check what it generated and why. * What is really considered as one instruction is not the { ... } block @@ -91,6 +99,24 @@ * * Other code is just copied into the interpreter part. * + * The filter language uses a simple type system, where values have types + * (constants T_*) and also terms (instructions) are statically typed. Our + * static typing is partial (some terms do not declare types of arguments + * or results), therefore it can detect most but not all type errors and + * therefore we still have runtime type checks. + * + * m4_dnl Types of arguments are declared by macros ARG() and ARG_TYPE(), + * m4_dnl types of results are declared by RESULT() and RESULT_TYPE(). + * m4_dnl Macros ARG_ANY(), RESULT_() and RESULT_VAL() do not declare types + * m4_dnl themselves, but can be combined with ARG_TYPE() / RESULT_TYPE(). + * + * m4_dnl Note that types should be declared only once. If there are + * m4_dnl multiple RESULT() macros in an instruction definition, they must + * m4_dnl use the exact same expression for type, or they should be replaced + * m4_dnl by multiple RESULT_() macros and a common RESULT_TYPE() macro. + * m4_dnl See e.g. FI_EA_GET or FI_MIN instructions. + * + * * If you are satisfied with this, you don't need to read the following * detailed description of what is really done with the instruction definitions. * @@ -215,6 +241,37 @@ * * m4_dnl If you are stymied, see FI_CALL or FI_CONSTANT or just search for * m4_dnl the mentioned macros in this file to see what is happening there in wild. + * + * + * A note about soundness of the type system: + * + * A type system is sound when types of expressions are consistent with + * types of values resulting from evaluation of such expressions. Untyped + * expressions are ok, but badly typed expressions are not sound. So is + * the type system of BIRD filtering code sound? There are some points: + * + * All cases of (one) m4_dnl RESULT() macro are obviously ok, as the macro + * both declares a type and returns a value. One have to check instructions + * that use m4_dnl RESULT_TYPE() macro. There are two issues: + * + * FI_AND, FI_OR - second argument is statically checked to be T_BOOL and + * passed as result without dynamic typecheck, declared to be T_BOOL. If + * an untyped non-bool expression is used as a second argument, then + * the mismatched type is returned. + * + * FI_VAR_GET - soundness depends on consistency of declared symbol types + * and stored values. This is maintained when values are stored by + * FI_VAR_SET, but when they are stored by FI_CALL, only static checking is + * used, so when an untyped expression returning mismatched value is used + * as a function argument, then inconsistent value is stored and subsequent + * FI_VAR_GET would be unsound. + * + * Both of these issues are inconsequential, as mismatched values from + * unsound expressions will be caught by dynamic typechecks like mismatched + * values from untyped expressions. + * + * Also note that FI_CALL is the only expression without properly declared + * result type. */ /* Binary operators */ @@ -255,7 +312,7 @@ RESULT_TYPE(T_BOOL); if (v1.val.i) - LINE(2,0); + LINE(2,1); else RESULT_VAL(v1); } @@ -265,7 +322,7 @@ RESULT_TYPE(T_BOOL); if (!v1.val.i) - LINE(2,0); + LINE(2,1); else RESULT_VAL(v1); } @@ -358,7 +415,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) { @@ -380,12 +437,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)); } @@ -456,6 +515,18 @@ RESULT(T_BOOL, i, ipa_is_ip4(v1.val.ip)); } + INST(FI_VAR_INIT, 1, 0) { + NEVER_CONSTANT; + ARG_ANY(1); + SYMBOL; + ARG_TYPE(1, sym->class & 0xff); + + /* New variable is always the last on stack */ + uint pos = curline.vbase + sym->offset; + fstk->vstk[pos] = v1; + fstk->vcnt = pos + 1; + } + /* Set to indirect value prepared in v1 */ INST(FI_VAR_SET, 1, 0) { NEVER_CONSTANT; @@ -486,12 +557,100 @@ RESULT_VAL(val); } + INST(FI_FOR_INIT, 1, 0) { + NEVER_CONSTANT; + ARG_ANY(1); + SYMBOL; + + FID_NEW_BODY() + ASSERT((sym->class & ~0xff) == SYM_VARIABLE); + + /* Static type check */ + if (f1->type) + { + enum btype t_var = (sym->class & 0xff); + enum btype t_arg = f_type_element_type(f1->type); + if (!t_arg) + cf_error("Value of expression in FOR must be iterable, got %s", + f_type_name(f1->type)); + if (t_var != t_arg) + cf_error("Loop variable '%s' in FOR must be %s, is %s", + sym->name, f_type_name(t_arg), f_type_name(t_var)); + } + + FID_INTERPRET_BODY() + + /* Dynamic type check */ + if ((sym->class & 0xff) != f_type_element_type(v1.type)) + runtime("Mismatched argument and variable type"); + + /* Setup the index */ + v2 = (struct f_val) { .type = T_INT, .val.i = 0 }; + + /* Keep v1 and v2 on the stack */ + fstk->vcnt += 2; + } + + INST(FI_FOR_NEXT, 2, 0) { + NEVER_CONSTANT; + SYMBOL; + + /* Type checks are done in FI_FOR_INIT */ + + /* Loop variable */ + struct f_val *var = &fstk->vstk[curline.vbase + sym->offset]; + int step = 0; + + switch(v1.type) + { + case T_PATH: + var->type = T_INT; + step = as_path_walk(v1.val.ad, &v2.val.i, &var->val.i); + break; + + case T_CLIST: + var->type = T_PAIR; + step = int_set_walk(v1.val.ad, &v2.val.i, &var->val.i); + break; + + case T_ECLIST: + var->type = T_EC; + step = ec_set_walk(v1.val.ad, &v2.val.i, &var->val.ec); + break; + + case T_LCLIST: + var->type = T_LC; + step = lc_set_walk(v1.val.ad, &v2.val.i, &var->val.lc); + break; + + default: + runtime( "Clist or lclist expected" ); + } + + if (step) + { + /* Keep v1 and v2 on the stack */ + fstk->vcnt += 2; + + /* Repeat this instruction */ + curline.pos--; + + /* Execute the loop body */ + LINE(1, 0); + + /* Space for loop variable, may be unused */ + fstk->vcnt += 1; + } + else + var->type = T_VOID; + } + INST(FI_CONDITION, 1, 0) { ARG(1, T_BOOL); if (v1.val.i) LINE(2,0); else - LINE(3,1); + LINE(3,0); } INST(FI_PRINT, 0, 0) { @@ -771,6 +930,7 @@ INST(FI_DEFAULT, 2, 1) { ARG_ANY(1); ARG_ANY(2); + RESULT_TYPE(f_type_element_type(v2.type)); log(L_INFO "Type of arg 1 is: %d", v1.type); @@ -945,7 +1105,7 @@ RESULT(T_INT, i, v1.val.lc.ldp2); } - INST(FI_MIN, 1, 1) { /* Get minimum element from set */ + INST(FI_MIN, 1, 1) { /* Get minimum element from list */ ARG_ANY(1); RESULT_TYPE(f_type_element_type(v1.type)); switch(v1.type) @@ -979,7 +1139,7 @@ } } - INST(FI_MAX, 1, 1) { /* Get maximum element from set */ + INST(FI_MAX, 1, 1) { /* Get maximum element from list */ ARG_ANY(1); RESULT_TYPE(f_type_element_type(v1.type)); switch(v1.type) @@ -1013,7 +1173,7 @@ } } - INST(FI_RETURN, 1, 1) { + INST(FI_RETURN, 1, 0) { NEVER_CONSTANT; /* Acquire the return value */ ARG_ANY(1); @@ -1041,28 +1201,59 @@ INST(FI_CALL, 0, 1) { NEVER_CONSTANT; + VARARG; SYMBOL; + /* Fake result type declaration */ + RESULT_TYPE(T_VOID); + + FID_NEW_BODY() + ASSERT(sym->class == SYM_FUNCTION); + + if (whati->varcount != sym->function->args) + cf_error("Function '%s' expects %u arguments, got %u arguments", + sym->name, sym->function->args, whati->varcount); + + /* Typecheck individual arguments */ + struct f_inst *a = fvar; + struct f_arg *b = sym->function->arg_list; + for (uint i = 1; a && b; a = a->next, b = b->next, i++) + { + enum btype b_type = b->arg->class & 0xff; + + if (a->type && (a->type != b_type) && !f_const_promotion(a, b_type)) + cf_error("Argument %u of '%s' must be %s, got %s", + i, sym->name, f_type_name(b_type), f_type_name(a->type)); + } + ASSERT(!a && !b); + + /* Add implicit void slot for the return value */ + struct f_inst *tmp = f_new_inst(FI_CONSTANT, (struct f_val) { .type = T_VOID }); + tmp->next = whati->fvar; + 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() /* Push the body on stack */ LINEX(sym->function); + curline.vbase = curline.ventry; curline.emask |= FE_RETURN; - /* Before this instruction was called, there was the T_VOID - * automatic return value pushed on value stack and also - * sym->function->args function arguments. Setting the - * vbase to point to first argument. */ - ASSERT(curline.ventry >= sym->function->args); - curline.ventry -= sym->function->args; - curline.vbase = curline.ventry; + /* Arguments on stack */ + fstk->vcnt += sym->function->args; /* Storage for local variables */ f_vcnt_check_overflow(sym->function->vars); @@ -1176,17 +1367,10 @@ if (v1.type == T_PATH) { - const struct f_tree *set = NULL; - u32 key = 0; - - if (v2.type == T_INT) - key = v2.val.i; - else if ((v2.type == T_SET) && (v2.val.t->from.type == T_INT)) - set = v2.val.t; + if ((v2.type == T_SET) && path_set_type(v2.val.t) || (v2.type == T_INT)) + RESULT_(T_PATH, ad, [[ as_path_filter(fpool, v1.val.ad, &v2, 0) ]]); else runtime("Can't delete non-integer (set)"); - - RESULT_(T_PATH, ad, [[ as_path_filter(fpool, v1.val.ad, set, key, 0) ]]); } else if (v1.type == T_CLIST) @@ -1238,10 +1422,8 @@ if (v1.type == T_PATH) { - u32 key = 0; - - if ((v2.type == T_SET) && (v2.val.t->from.type == T_INT)) - RESULT_(T_PATH, ad, [[ as_path_filter(fpool, v1.val.ad, v2.val.t, key, 1) ]]); + if ((v2.type == T_SET) && path_set_type(v2.val.t)) + RESULT_(T_PATH, ad, [[ as_path_filter(fpool, v1.val.ad, &v2, 1) ]]); else runtime("Can't filter integer"); } @@ -1301,7 +1483,7 @@ } - INST(FI_FORMAT, 1, 0) { /* Format */ + INST(FI_FORMAT, 1, 1) { /* Format */ ARG_ANY(1); RESULT(T_STRING, s, val_format_str(fpool, &v1)); } diff --git a/filter/f-inst.h b/filter/f-inst.h index 047a66c9..fbc59de7 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 */ @@ -35,19 +35,26 @@ const char *f_instruction_name_(enum f_instruction_code fi); static inline const char *f_instruction_name(enum f_instruction_code fi) { return f_instruction_name_(fi) + 3; } +struct f_arg { + struct symbol *arg; + struct f_arg *next; +}; + /* Filter structures for execution */ /* Line of instructions to be unconditionally executed one after another */ 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 fb93ee80..82a06bdd 100644 --- a/filter/f-util.c +++ b/filter/f-util.c @@ -37,6 +37,6 @@ 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 ad2fafe2..9a94545c 100644 --- a/filter/filter.c +++ b/filter/filter.c @@ -179,8 +179,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/filter/filter_test.c b/filter/filter_test.c index 63764964..5b24a765 100644 --- a/filter/filter_test.c +++ b/filter/filter_test.c @@ -70,6 +70,7 @@ int main(int argc, char *argv[]) { bt_init(argc, argv); + bt_bird_init(); bt_assert_hook = bt_assert_filter; diff --git a/filter/test.conf b/filter/test.conf index cd2fa8db..22f5dea3 100644 --- a/filter/test.conf +++ b/filter/test.conf @@ -146,9 +146,8 @@ bt_test_same(onef, twof, 0); */ function t_bool() -bool b; { - b = true; + bool b = true; bt_assert(b); bt_assert(!!b); @@ -184,12 +183,11 @@ define xyzzy = (120+10); define '1a-a1' = (xyzzy-100); function t_int() -int i; { bt_assert(xyzzy = 130); bt_assert('1a-a1' = 30); - i = four; + int i = four; i = 12*100 + 60/2 + i; i = (i + 0); bt_assert(i = 1234); @@ -238,14 +236,19 @@ define is2 = [(17+2), 17, 15, 11, 8, 5, 3, 2]; define is3 = [5, 17, 2, 11, 8, 15, 3, 19]; function t_int_set() -int set is; { + int set 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); @@ -280,6 +283,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"); @@ -293,9 +297,8 @@ bt_test_suite(t_int_set, "Testing sets of integers"); */ function t_string() -string st; { - st = "Hello"; + string st = "Hello"; bt_assert(format(st) = "Hello"); bt_assert(st ~ "Hell*"); bt_assert(st ~ "?ello"); @@ -320,9 +323,8 @@ function 'mkpair-a'(int a) } function t_pair() -pair pp; { - pp = (1, 2); + pair pp = (1, 2); bt_assert(format(pp) = "(1,2)"); bt_assert((1,2) = pp); bt_assert((1,1+1) = pp); @@ -343,10 +345,11 @@ bt_test_suite(t_pair, "Testing pairs"); */ function t_pair_set() -pair pp; -pair set ps; { - pp = (1, 2); + pair pp = (1, 2); + pair set 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); @@ -363,6 +366,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); @@ -414,6 +418,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"); @@ -494,6 +499,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"); @@ -582,13 +588,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}]"); @@ -673,6 +700,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 ]); @@ -790,6 +823,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); @@ -800,6 +834,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); @@ -808,6 +844,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 ); @@ -827,6 +867,15 @@ int set set12; bt_assert(delete(p2, [4..5]) = prepend(prepend(prepend(prepend(+empty+, 3), 3), 2), 1)); bt_assert(format([= 1 2+ 3 =]) = "[= 1 2 + 3 =]"); + + # iteration over path + int x = 0; + int y = 0; + for int i in p2 do { + x = x + i; + y = y + x; + } + bt_assert(x = 18 && y = 50); } bt_test_suite(t_path, "Testing paths"); @@ -868,6 +917,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)); @@ -905,6 +955,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))); @@ -949,6 +1002,12 @@ clist r; 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)); + + # iteration over clist + int x = 0; + for pair c in r do + x = x + c.asn * c.asn * c.data; + bt_assert(x = 36); } bt_test_suite(t_clist, "Testing lists of communities"); @@ -1022,11 +1081,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))"); @@ -1060,6 +1123,13 @@ eclist r; 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)); + + # iteration over eclist + int x = 0; + for ec c in r do + if c > (rt, 2, 0) && c < (rt, 3, 0) then + x = x + 1; + bt_assert(x = 3); } bt_test_suite(t_eclist, "Testing lists of extended communities"); @@ -1144,6 +1214,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))"); @@ -1175,6 +1248,19 @@ lclist r; 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)); + + # iteration over lclist + int x = 0; + int y = 0; + lc mx = (0, 0, 0); + for lc c in r do { + int asn2 = c.asn * c.asn; + x = x + asn2 * c.data1; + y = y + asn2 * c.data2; + if c > mx then mx = c; + } + bt_assert(x = 39 && y = 49); + bt_assert(mx = r.max); } bt_test_suite(t_lclist, "Testing lists of large communities"); @@ -1203,6 +1289,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)]"); @@ -1259,6 +1346,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]"); @@ -1269,6 +1360,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"); @@ -1335,7 +1427,85 @@ function fifteen() return 15; } +function local_vars(int j) +{ + int k = 10; + bt_assert(j = 5 && k = 10); + { + int j = 15; + k = 20; + bt_assert(j = 15 && k = 20); + } + bt_assert(j = 5 && k = 20); + + if j < 10 then + { + int j = 25; + string k = "hello"; + bt_assert(j = 25 && k = "hello"); + } + bt_assert(j = 5 && k = 20); + + int m = 100; + { + j = 35; + int k = 40; + bt_assert(j = 35 && k = 40 && m = 100); + } + bt_assert(j = 35 && k = 20 && m = 100); +} + +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) +{ + # x -> return src or dst + # y -> print state + + if n = 0 then { if x then return h_src; else return h_dst; } + + bgppath tmp1 = hanoi_solve(n - 1, h_src, h_aux, h_dst, true, y); + bgppath tmp2 = hanoi_solve(n - 1, h_src, h_aux, h_dst, false, false); + h_src = tmp1; + h_aux = tmp2; + + int 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); @@ -1347,6 +1517,17 @@ function t_call_function() bt_assert(callme(4, 4) = 16); bt_assert(callme(7, 2) = 14); bt_assert(callmeagain(1, 2, 3) = 6); + local_vars(5); + + 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"); @@ -1592,13 +1773,16 @@ filter vpn_filter bt_assert(net.type != NET_IP6); bt_assert(net.rd = 0:1:2); + bool b = false; case (net.type) { NET_IP4: print "IPV4"; NET_IP6: print "IPV6"; + else: b = true; } + bt_assert(b); bt_check_assign(from, 10.20.30.40); - bt_check_assign(gw, 55.55.55.44); + # bt_check_assign(gw, 55.55.55.44); bgp_community.add((3,5)); bgp_ext_community.add((ro, 135, 999)); diff --git a/lib/Makefile b/lib/Makefile index 15f757d9..f4ade9a6 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -1,4 +1,4 @@ -src := a-path.c a-set.c bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c resource.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c +src := a-path.c a-set.c bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c rcu.c resource.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c obj := $(src-o-files) $(all-daemon) diff --git a/lib/a-path.c b/lib/a-path.c index 0eca8475..a7a22e40 100644 --- a/lib/a-path.c +++ b/lib/a-path.c @@ -602,8 +602,10 @@ as_path_match_set(const struct adata *path, const struct f_tree *set) } const struct adata * -as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos) +as_path_filter(struct linpool *pool, const struct adata *path, const struct f_val *set, int pos) { + ASSERT((set->type == T_SET) || (set->type == T_INT)); + if (!path) return NULL; @@ -629,13 +631,13 @@ as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tr u32 as = get_as(p); int match; - if (set) + if (set->type == T_SET) { struct f_val v = { .type = T_INT, .val.i = as}; - match = !!find_tree(set, &v); + match = !!find_tree(set->val.t, &v); } - else - match = (as == key); + else /* T_INT */ + match = (as == set->val.i); if (match == pos) { @@ -667,6 +669,35 @@ as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tr return res; } +int +as_path_walk(const struct adata *path, uint *pos, uint *val) +{ + if (!path) + return 0; + + const u8 *p = path->data; + const u8 *q = p + path->length; + uint n, x = *pos; + + while (p < q) + { + n = p[1]; + p += 2; + + if (x < n) + { + *val = get_as(p + x * BS); + *pos += 1; + return 1; + } + + p += n * BS; + x -= n; + } + + return 0; +} + struct pm_pos { diff --git a/lib/a-path_test.c b/lib/a-path_test.c index 38f77642..c6f8ce8b 100644 --- a/lib/a-path_test.c +++ b/lib/a-path_test.c @@ -12,6 +12,7 @@ #include "nest/rt.h" #include "lib/attrs.h" #include "lib/resource.h" +#include "filter/data.h" #define TESTS_NUM 30 #define AS_PATH_LENGTH 1000 @@ -127,8 +128,9 @@ t_path_include(void) int counts_of_contains = count_asn_in_array(as_nums, as_nums[i]); bt_assert_msg(as_path_contains(as_path, as_nums[i], counts_of_contains), "AS Path should contains %d-times number %d", counts_of_contains, as_nums[i]); - bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 0) != NULL); - bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 1) != NULL); + struct f_val v = { .type = T_INT, .val.i = as_nums[i] }; + bt_assert(as_path_filter(tmp_linpool, as_path, &v, 0) != NULL); + bt_assert(as_path_filter(tmp_linpool, as_path, &v, 1) != NULL); } for (i = 0; i < 10000; i++) diff --git a/lib/a-set.c b/lib/a-set.c index 8ede9b83..dcb86058 100644 --- a/lib/a-set.c +++ b/lib/a-set.c @@ -693,3 +693,51 @@ lc_set_max(const struct adata *list, lcomm *val) *val = (lcomm) { res[0], res[1], res[2] }; return 1; } + +int +int_set_walk(const struct adata *list, uint *pos, uint *val) +{ + if (!list) + return 0; + + if (*pos >= (uint) int_set_get_size(list)) + return 0; + + u32 *res = int_set_get_data(list) + *pos; + *val = *res; + *pos += 1; + + return 1; +} + +int +ec_set_walk(const struct adata *list, uint *pos, u64 *val) +{ + if (!list) + return 0; + + if (*pos >= (uint) int_set_get_size(list)) + return 0; + + u32 *res = int_set_get_data(list) + *pos; + *val = ec_generic(res[0], res[1]); + *pos += 2; + + return 1; +} + +int +lc_set_walk(const struct adata *list, uint *pos, lcomm *val) +{ + if (!list) + return 0; + + if (*pos >= (uint) int_set_get_size(list)) + return 0; + + u32 *res = int_set_get_data(list) + *pos; + *val = (lcomm) { res[0], res[1], res[2] }; + *pos += 3; + + return 1; +} diff --git a/lib/a-set_test.c b/lib/a-set_test.c index 3280031f..693b8f08 100644 --- a/lib/a-set_test.c +++ b/lib/a-set_test.c @@ -221,6 +221,7 @@ t_set_ec_delete(void) return 1; } + int main(int argc, char *argv[]) { diff --git a/lib/attrs.h b/lib/attrs.h index a75abcd3..af2f1036 100644 --- a/lib/attrs.h +++ b/lib/attrs.h @@ -60,6 +60,7 @@ static inline int adata_same(const struct adata *a, const struct adata *b) * to 16bit slot (like in 16bit AS_PATH). See RFC 4893 for details */ +struct f_val; struct f_tree; int as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen); @@ -81,7 +82,8 @@ int as_path_get_last(const struct adata *path, u32 *last_as); u32 as_path_get_last_nonaggregated(const struct adata *path); int as_path_contains(const struct adata *path, u32 as, int min); int as_path_match_set(const struct adata *path, const struct f_tree *set); -const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos); +const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_val *set, int pos); +int as_path_walk(const struct adata *path, uint *pos, uint *val); static inline struct adata *as_path_prepend(struct linpool *pool, const struct adata *path, u32 as) { return as_path_prepend2(pool, path, AS_PATH_SEQUENCE, as); } @@ -256,6 +258,9 @@ int lc_set_min(const struct adata *list, lcomm *val); int int_set_max(const struct adata *list, u32 *val); int ec_set_max(const struct adata *list, u64 *val); int lc_set_max(const struct adata *list, lcomm *val); +int int_set_walk(const struct adata *list, uint *pos, u32 *val); +int ec_set_walk(const struct adata *list, uint *pos, u64 *val); +int lc_set_walk(const struct adata *list, uint *pos, lcomm *val); void ec_set_sort_x(struct adata *set); /* Sort in place */ diff --git a/lib/birdlib.h b/lib/birdlib.h index 9b6e4a16..d55b1a44 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -15,7 +15,7 @@ /* Ugly structure offset handling macros */ #define OFFSETOF(s, i) ((size_t) &((s *)0)->i) -#define SKIP_BACK(s, i, p) ((s *)((char *)p - OFFSETOF(s, i))) +#define SKIP_BACK(s, i, p) ({ s *_ptr = ((s *)((char *)p - OFFSETOF(s, i))); ASSERT_DIE(&_ptr->i == p); _ptr; }) #define BIRD_ALIGN(s, a) (((s)+a-1)&~(a-1)) #define CPU_STRUCT_ALIGN (MAX_(_Alignof(void*), _Alignof(u64))) #define BIRD_CPU_ALIGN(s) BIRD_ALIGN((s), CPU_STRUCT_ALIGN) @@ -86,6 +86,7 @@ static inline int u64_cmp(u64 i1, u64 i2) /* Macros for gcc attributes */ #define NORET __attribute__((noreturn)) +#define USE_RESULT __atribute__((warn_unused_result)) #define UNUSED __attribute__((unused)) #define PACKED __attribute__((packed)) #define NONNULL(...) __attribute__((nonnull((__VA_ARGS__)))) @@ -93,10 +94,6 @@ static inline int u64_cmp(u64 i1, u64 i2) #define STATIC_ASSERT(EXP) _Static_assert(EXP, #EXP) #define STATIC_ASSERT_MSG(EXP,MSG) _Static_assert(EXP, MSG) -#ifndef HAVE_THREAD_LOCAL -#define _Thread_local -#endif - /* Microsecond time */ typedef s64 btime; @@ -178,8 +175,13 @@ void debug(const char *msg, ...); /* Printf to debug output */ #if defined(LOCAL_DEBUG) || defined(GLOBAL_DEBUG) #define DBG(x, y...) debug(x, ##y) +#define DBGL(x, y...) debug(x "\n", ##y) +#elif defined(DEBUG_TO_LOG) +#define DBG(...) do { } while (0) +#define DBGL(...) log(L_DEBUG __VA_ARGS__) #else -#define DBG(x, y...) do { } while(0) +#define DBG(...) do { } while(0) +#define DBGL(...) do { } while (0) #endif #define ASSERT_DIE(x) do { if (!(x)) bug("Assertion '%s' failed at %s:%d", #x, __FILE__, __LINE__); } while(0) diff --git a/lib/event.c b/lib/event.c index 33dc00b0..07d7dc53 100644 --- a/lib/event.c +++ b/lib/event.c @@ -19,20 +19,95 @@ * events in them and explicitly ask to run them. */ +#undef LOCAL_DEBUG + #include "nest/bird.h" #include "lib/event.h" +#include "lib/io-loop.h" event_list global_event_list; event_list global_work_list; -inline void -ev_postpone(event *e) +STATIC_ASSERT(OFFSETOF(event_list, _sentinel.next) >= OFFSETOF(event_list, _end[0])); + +void +ev_init_list(event_list *el, struct birdloop *loop, const char *name) +{ + el->name = name; + el->loop = loop; + + atomic_store_explicit(&el->receiver, &el->_sentinel, memory_order_relaxed); + atomic_store_explicit(&el->_executor, &el->_sentinel, memory_order_relaxed); + atomic_store_explicit(&el->_sentinel.next, NULL, memory_order_relaxed); +} + +/* + * The event list should work as a message passing point. Sending a message + * must be a fairly fast process with no locks and low waiting times. OTOH, + * processing messages always involves running the assigned code and the + * receiver is always a single one thread with no concurrency at all. There is + * also a postponing requirement to synchronously remove an event from a queue, + * yet we allow this only when the caller has its receiver event loop locked. + * It still means that the event may get postponed from other event in the same + * list, therefore we have to be careful. + */ + +static inline int +ev_remove_from(event *e, event * _Atomic * head) { - if (ev_active(e)) + /* The head pointer stores where cur is pointed to from */ + event * _Atomic *prev = head; + + /* The current event in queue to check */ + event *cur = atomic_load_explicit(prev, memory_order_acquire); + + /* Pre-loaded next pointer; if NULL, this is sentinel */ + event *next = atomic_load_explicit(&cur->next, memory_order_acquire); + + while (next) + { + if (e == cur) { - rem_node(&e->n); - e->n.next = NULL; + /* Check whether we have collided with somebody else + * adding an item to the queue. */ + if (!atomic_compare_exchange_strong_explicit( + prev, &cur, next, + memory_order_acq_rel, memory_order_acquire)) + { + /* This may happen only on list head */ + ASSERT_DIE(prev == head); + + /* Restart. The collision should never happen again. */ + return ev_remove_from(e, head); + } + + /* Successfully removed from the list; inactivate this event. */ + atomic_store_explicit(&cur->next, NULL, memory_order_release); + return 1; } + + /* Go to the next event. */ + prev = &cur->next; + cur = next; + next = atomic_load_explicit(&cur->next, memory_order_acquire); + } + + return 0; +} + +inline void +ev_postpone(event *e) +{ + /* Find the list to remove the event from */ + event_list *sl = ev_get_list(e); + if (!sl) + return; + + /* Postponing allowed only from the target loop */ + ASSERT_DIE(birdloop_inside(sl->loop)); + + /* Remove from one of these lists. */ + ASSERT(ev_remove_from(e, &sl->_executor) || ev_remove_from(e, &sl->receiver)); } static void @@ -43,7 +118,7 @@ ev_dump(resource *r) debug("(code %p, data %p, %s)\n", e->hook, e->data, - e->n.next ? "scheduled" : "inactive"); + atomic_load_explicit(&e->next, memory_order_relaxed) ? "scheduled" : "inactive"); } static struct resclass ev_class = { @@ -95,40 +170,21 @@ ev_run(event *e) * list @l which can be run by calling ev_run_list(). */ inline void -ev_enqueue(event_list *l, event *e) -{ - ev_postpone(e); - add_tail(l, &e->n); -} - -/** - * ev_schedule - schedule an event - * @e: an event - * - * This function schedules an event by enqueueing it to a system-wide - * event list which is run by the platform dependent code whenever - * appropriate. - */ -void -ev_schedule(event *e) -{ - ev_enqueue(&global_event_list, e); -} - -/** - * ev_schedule_work - schedule a work-event. - * @e: an event - * - * This function schedules an event by enqueueing it to a system-wide work-event - * list which is run by the platform dependent code whenever appropriate. This - * is designated for work-events instead of regular events. They are executed - * less often in order to not clog I/O loop. - */ -void -ev_schedule_work(event *e) +ev_send(event_list *l, event *e) { - if (!ev_active(e)) - add_tail(&global_work_list, &e->n); + event_list *sl = ev_get_list(e); + if (sl == l) + return; + if (sl) + bug("Queuing an already queued event to another queue is not supported."); + + event *next = atomic_load_explicit(&l->receiver, memory_order_acquire); + do atomic_store_explicit(&e->next, next, memory_order_relaxed); + while (!atomic_compare_exchange_strong_explicit( + &l->receiver, &next, e, + memory_order_acq_rel, memory_order_acquire)); + + birdloop_ping(l->loop); } void io_log_event(void *hook, void *data); @@ -140,62 +196,56 @@ void io_log_event(void *hook, void *data); * This function calls ev_run() for all events enqueued in the list @l. */ int -ev_run_list(event_list *l) +ev_run_list_limited(event_list *l, uint limit) { - node *n; - list tmp_list; + event * _Atomic *ep = &l->_executor; - init_list(&tmp_list); - add_tail_list(&tmp_list, l); - init_list(l); - WALK_LIST_FIRST(n, tmp_list) - { - event *e = SKIP_BACK(event, n, n); - - /* This is ugly hack, we want to log just events executed from the main I/O loop */ - if ((l == &global_event_list) || (l == &global_work_list)) - io_log_event(e->hook, e->data); + /* No pending events, refill the queue. */ + if (atomic_load_explicit(ep, memory_order_relaxed) == &l->_sentinel) + { + /* Move the current event list aside and create a new one. */ + event *received = atomic_exchange_explicit( + &l->receiver, &l->_sentinel, memory_order_acq_rel); - ev_run(e); - tmp_flush(); - } + /* No event to run. */ + if (received == &l->_sentinel) + return 0; - return !EMPTY_LIST(*l); -} + /* Setup the executor queue */ + event *head = &l->_sentinel; -int -ev_run_list_limited(event_list *l, uint limit) -{ - node *n; - list tmp_list; + /* Flip the order of the events by relinking them one by one (push-pop) */ + while (received != &l->_sentinel) + { + event *cur = received; + received = atomic_exchange_explicit(&cur->next, head, memory_order_relaxed); + head = cur; + } - init_list(&tmp_list); - add_tail_list(&tmp_list, l); - init_list(l); + /* Store the executor queue to its designated place */ + atomic_store_explicit(ep, head, memory_order_relaxed); + } - WALK_LIST_FIRST(n, tmp_list) + /* Run the events in order. */ + event *e; + while ((e = atomic_load_explicit(ep, memory_order_relaxed)) != &l->_sentinel) { - event *e = SKIP_BACK(event, n, n); - - if (!limit) - break; + /* Check limit */ + if (!--limit) + return 1; /* This is ugly hack, we want to log just events executed from the main I/O loop */ if ((l == &global_event_list) || (l == &global_work_list)) io_log_event(e->hook, e->data); - ev_run(e); + /* Inactivate the event */ + atomic_store_explicit(ep, atomic_load_explicit(&e->next, memory_order_relaxed), memory_order_relaxed); + atomic_store_explicit(&e->next, NULL, memory_order_relaxed); + + /* Run the event */ + e->hook(e->data); tmp_flush(); - limit--; } - if (!EMPTY_LIST(tmp_list)) - { - /* Attach new items after the unprocessed old items */ - add_tail_list(&tmp_list, l); - init_list(l); - add_tail_list(l, &tmp_list); - } - - return !EMPTY_LIST(*l); + return atomic_load_explicit(&l->receiver, memory_order_relaxed) != &l->_sentinel; } diff --git a/lib/event.h b/lib/event.h index 5f3b78d8..9773c3a9 100644 --- a/lib/event.h +++ b/lib/event.h @@ -10,33 +10,69 @@ #define _BIRD_EVENT_H_ #include "lib/resource.h" +#include "lib/locking.h" + +#include <stdatomic.h> + +struct birdloop; typedef struct event { resource r; void (*hook)(void *); void *data; - node n; /* Internal link */ + struct event * _Atomic next; } event; -typedef list event_list; +typedef union event_list { + struct { + event * _Atomic receiver; /* Event receive list */ + event * _Atomic _executor; /* Event execute list */ + const char *name; + struct birdloop *loop; /* The executor loop */ + char _end[0]; + }; + event _sentinel; /* Sentinel node to actively detect list end */ +} event_list; extern event_list global_event_list; extern event_list global_work_list; event *ev_new(pool *); void ev_run(event *); -#define ev_init_list(el) init_list(el) +void ev_init_list(event_list *, struct birdloop *loop, const char *name); void ev_enqueue(event_list *, event *); -void ev_schedule(event *); -void ev_schedule_work(event *); +#define ev_send ev_enqueue +#define ev_send_loop(l, e) ev_send(birdloop_event_list((l)), (e)) + +#define ev_schedule(e) ({ ASSERT_THE_BIRD_LOCKED; if (!ev_active((e))) ev_send(&global_event_list, (e)); }) +#define ev_schedule_work(e) ({ ASSERT_THE_BIRD_LOCKED; if (!ev_active((e))) ev_send(&global_work_list, (e)); }) + void ev_postpone(event *); -int ev_run_list(event_list *); int ev_run_list_limited(event_list *, uint); +#define ev_run_list(l) ev_run_list_limited((l), ~0) + +#define LEGACY_EVENT_LIST(l) (((l) == &global_event_list) || ((l) == &global_work_list)) static inline int ev_active(event *e) { - return e->n.next != NULL; + return atomic_load_explicit(&e->next, memory_order_relaxed) != NULL; +} + +static inline event_list * +ev_get_list(event *e) +{ + /* We are looking for the sentinel node at the list end. + * After this, we have s->next == NULL */ + event *s = e; + for (event *sn; sn = atomic_load_explicit(&s->next, memory_order_acquire); s = sn) + ; + + /* No sentinel, no list. */ + if (s == e) + return NULL; + else + return SKIP_BACK(event_list, _sentinel, s); } static inline event* diff --git a/lib/event_test.c b/lib/event_test.c index 3070327d..612deb25 100644 --- a/lib/event_test.c +++ b/lib/event_test.c @@ -54,7 +54,6 @@ t_ev_run_list(void) int i; olock_init(); - timer_init(); rt_init(); io_init(); if_init(); diff --git a/lib/io-loop.h b/lib/io-loop.h new file mode 100644 index 00000000..2450a609 --- /dev/null +++ b/lib/io-loop.h @@ -0,0 +1,58 @@ +/* + * BIRD -- I/O and event loop + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_IO_LOOP_H_ +#define _BIRD_IO_LOOP_H_ + +#include "nest/bird.h" +#include "lib/lists.h" +#include "lib/locking.h" +#include "lib/resource.h" +#include "lib/event.h" +#include "lib/socket.h" + +extern struct birdloop main_birdloop; + +void sk_start(sock *s); +void sk_stop(sock *s); +void sk_reloop(sock *s, struct birdloop *loop); + +/* Start a new birdloop owned by given pool and domain */ +struct birdloop *birdloop_new(pool *p, uint order, const char *name); + +/* Stop the loop. At the end, the @stopped callback is called unlocked in tail + * position to finish cleanup. Run birdloop_free() from that callback to free + * the loop itself. */ +void birdloop_stop(struct birdloop *loop, void (*stopped)(void *data), void *data); +void birdloop_stop_self(struct birdloop *loop, void (*stopped)(void *data), void *data); +void birdloop_free(struct birdloop *loop); + +/* Get birdloop's event list */ +event_list *birdloop_event_list(struct birdloop *loop); + +/* Get birdloop's time heap */ +struct timeloop *birdloop_time_loop(struct birdloop *loop); + +/* Enter and exit the birdloop */ +void birdloop_enter(struct birdloop *loop); +void birdloop_leave(struct birdloop *loop); + +_Bool birdloop_inside(struct birdloop *loop); + +void birdloop_mask_wakeups(struct birdloop *loop); +void birdloop_unmask_wakeups(struct birdloop *loop); + +void birdloop_link(struct birdloop *loop); +void birdloop_unlink(struct birdloop *loop); + +void birdloop_ping(struct birdloop *loop); + +void birdloop_init(void); + +/* Yield for a little while. Use only in special cases. */ +void birdloop_yield(void); + +#endif /* _BIRD_IO_LOOP_H_ */ diff --git a/lib/lists.c b/lib/lists.c index 200576cf..8f95c7c2 100644 --- a/lib/lists.c +++ b/lib/lists.c @@ -26,7 +26,7 @@ #define _BIRD_LISTS_C_ -#include "nest/bird.h" +#include "lib/birdlib.h" #include "lib/lists.h" LIST_INLINE int @@ -35,11 +35,12 @@ check_list(list *l, node *n) if (!l) { ASSERT_DIE(n); - ASSERT_DIE(n->prev); - do { n = n->prev; } while (n->prev); + node *nn = n; + while (nn->prev) + nn = nn->prev; - l = SKIP_BACK(list, head_node, n); + l = SKIP_BACK(list, head_node, nn); } int seen = 0; @@ -60,7 +61,7 @@ check_list(list *l, node *n) } ASSERT_DIE(cur == &(l->tail_node)); - ASSERT_DIE(!n || (seen == 1)); + ASSERT_DIE(!n || (seen == 1) || (n == &l->head_node) || (n == &l->tail_node)); return 1; } @@ -120,7 +121,7 @@ add_head(list *l, node *n) LIST_INLINE void insert_node(node *n, node *after) { - EXPENSIVE_CHECK(check_list(l, after)); + EXPENSIVE_CHECK(check_list(NULL, after)); ASSUME(n->prev == NULL); ASSUME(n->next == NULL); @@ -141,7 +142,7 @@ insert_node(node *n, node *after) LIST_INLINE void rem_node(node *n) { - EXPENSIVE_CHECK(check_list(NULL, n)); + EXPENSIVE_CHECK((n == n->prev) && (n == n->next) || check_list(NULL, n)); node *z = n->prev; node *x = n->next; diff --git a/lib/lists.h b/lib/lists.h index 7e6d5467..86ff59c9 100644 --- a/lib/lists.h +++ b/lib/lists.h @@ -69,6 +69,18 @@ typedef union list { /* In fact two overlayed nodes */ #define EMPTY_LIST(list) (!(list).head->next) +static inline _Bool +enlisted(node *n) +{ + switch ((!!n->next) + (!!n->prev)) + { + case 0: return 0; + case 2: return 1; + case 1: bug("Garbled event list node"); + } + + bug("Maths is broken. And you should see a new heaven and a new earth: for the first heaven and the first earth had been passed away."); +} #ifndef _BIRD_LISTS_C_ #define LIST_INLINE static inline diff --git a/lib/locking.h b/lib/locking.h new file mode 100644 index 00000000..a9a8aa9b --- /dev/null +++ b/lib/locking.h @@ -0,0 +1,63 @@ +/* + * BIRD Library -- Locking + * + * (c) 2020--2021 Maria Matejka <mq@jmq.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_LOCKING_H_ +#define _BIRD_LOCKING_H_ + +struct domain_generic; + +/* Here define the global lock order; first to last. */ +struct lock_order { + struct domain_generic *the_bird; + struct domain_generic *proto; + struct domain_generic *rtable; + struct domain_generic *resource; +}; + +extern _Thread_local struct lock_order locking_stack; +extern _Thread_local struct domain_generic **last_locked; + +#define DOMAIN(type) struct domain__##type +#define DEFINE_DOMAIN(type) DOMAIN(type) { struct domain_generic *type; } +#define DOMAIN_ORDER(type) OFFSETOF(struct lock_order, type) + +#define DOMAIN_NEW(type, name) (DOMAIN(type)) { .type = domain_new(name, DOMAIN_ORDER(type)) } +struct domain_generic *domain_new(const char *name, uint order); + +#define DOMAIN_FREE(type, d) domain_free((d).type) +void domain_free(struct domain_generic *); + +#define DOMAIN_NULL(type) (DOMAIN(type)) {} + +#define LOCK_DOMAIN(type, d) do_lock(((d).type), &(locking_stack.type)) +#define UNLOCK_DOMAIN(type, d) do_unlock(((d).type), &(locking_stack.type)) + +#define DOMAIN_IS_LOCKED(type, d) (((d).type) == (locking_stack.type)) +#define DG_IS_LOCKED(d) ((d) == *(DG_LSP(d))) + +/* Internal for locking */ +void do_lock(struct domain_generic *dg, struct domain_generic **lsp); +void do_unlock(struct domain_generic *dg, struct domain_generic **lsp); + +uint dg_order(struct domain_generic *dg); + +#define DG_LSP(d) ((struct domain_generic **) (((void *) &locking_stack) + dg_order(d))) +#define DG_LOCK(d) do_lock(d, DG_LSP(d)) +#define DG_UNLOCK(d) do_unlock(d, DG_LSP(d)) + +/* Use with care. To be removed in near future. */ +DEFINE_DOMAIN(the_bird); +extern DOMAIN(the_bird) the_bird_domain; + +#define the_bird_lock() LOCK_DOMAIN(the_bird, the_bird_domain) +#define the_bird_unlock() UNLOCK_DOMAIN(the_bird, the_bird_domain) +#define the_bird_locked() DOMAIN_IS_LOCKED(the_bird, the_bird_domain) + +#define ASSERT_THE_BIRD_LOCKED ({ if (!the_bird_locked()) bug("The BIRD lock must be locked here: %s:%d", __FILE__, __LINE__); }) + +#endif diff --git a/lib/rcu.c b/lib/rcu.c new file mode 100644 index 00000000..83fdd022 --- /dev/null +++ b/lib/rcu.c @@ -0,0 +1,79 @@ +/* + * BIRD Library -- Read-Copy-Update Basic Operations + * + * (c) 2021 Maria Matejka <mq@jmq.cz> + * (c) 2021 CZ.NIC z.s.p.o. + * + * Can be freely distributed and used under the terms of the GNU GPL. + * Note: all the relevant patents shall be expired. + * + * Using the Supplementary Material for User-Level Implementations of Read-Copy-Update + * by Matthieu Desnoyers, Paul E. McKenney, Alan S. Stern, Michel R. Dagenais and Jonathan Walpole + * obtained from https://www.efficios.com/pub/rcu/urcu-supp-accepted.pdf + */ + +#include "lib/rcu.h" +#include "lib/io-loop.h" +#include "lib/locking.h" + +_Atomic uint rcu_gp_ctl = RCU_NEST_CNT; +_Thread_local struct rcu_birdloop *this_rcu_birdloop = NULL; + +static list rcu_birdloop_list; + +static struct rcu_birdloop main_rcu_birdloop; + +DEFINE_DOMAIN(resource); +static DOMAIN(resource) rcu_domain; + +static int +rcu_gp_ongoing(_Atomic uint *ctl) +{ + uint val = atomic_load(ctl); + return (val & RCU_NEST_CNT) && ((val ^ rcu_gp_ctl) & RCU_GP_PHASE); +} + +static void +update_counter_and_wait(void) +{ + atomic_fetch_xor(&rcu_gp_ctl, RCU_GP_PHASE); + struct rcu_birdloop *rc; + WALK_LIST(rc, rcu_birdloop_list) + while (rcu_gp_ongoing(&rc->ctl)) + birdloop_yield(); +} + +void +synchronize_rcu(void) +{ + LOCK_DOMAIN(resource, rcu_domain); + update_counter_and_wait(); + update_counter_and_wait(); + UNLOCK_DOMAIN(resource, rcu_domain); +} + +void +rcu_birdloop_start(struct rcu_birdloop *rc) +{ + LOCK_DOMAIN(resource, rcu_domain); + add_tail(&rcu_birdloop_list, &rc->n); + this_rcu_birdloop = rc; + UNLOCK_DOMAIN(resource, rcu_domain); +} + +void +rcu_birdloop_stop(struct rcu_birdloop *rc) +{ + LOCK_DOMAIN(resource, rcu_domain); + this_rcu_birdloop = NULL; + rem_node(&rc->n); + UNLOCK_DOMAIN(resource, rcu_domain); +} + +void +rcu_init(void) +{ + rcu_domain = DOMAIN_NEW(resource, "Read-Copy-Update"); + init_list(&rcu_birdloop_list); + rcu_birdloop_start(&main_rcu_birdloop); +} diff --git a/lib/rcu.h b/lib/rcu.h new file mode 100644 index 00000000..c537a1ef --- /dev/null +++ b/lib/rcu.h @@ -0,0 +1,55 @@ +/* + * BIRD Library -- Read-Copy-Update Basic Operations + * + * (c) 2021 Maria Matejka <mq@jmq.cz> + * (c) 2021 CZ.NIC z.s.p.o. + * + * Can be freely distributed and used under the terms of the GNU GPL. + * Note: all the relevant patents shall be expired. + */ + +#ifndef _BIRD_RCU_H_ +#define _BIRD_RCU_H_ + +#include "lib/birdlib.h" +#include "lib/lists.h" +#include <stdatomic.h> + +#define RCU_GP_PHASE 0x100000 +#define RCU_NEST_MASK 0x0fffff +#define RCU_NEST_CNT 0x000001 + +extern _Atomic uint rcu_gp_ctl; + +struct rcu_birdloop { + node n; + _Atomic uint ctl; +}; + +extern _Thread_local struct rcu_birdloop *this_rcu_birdloop; + +static inline void rcu_read_lock(void) +{ + uint cmp = atomic_load_explicit(&this_rcu_birdloop->ctl, memory_order_acquire); + + if (cmp & RCU_NEST_MASK) + atomic_store_explicit(&this_rcu_birdloop->ctl, cmp + RCU_NEST_CNT, memory_order_relaxed); + else + atomic_store(&this_rcu_birdloop->ctl, atomic_load_explicit(&rcu_gp_ctl, memory_order_acquire)); +} + +static inline void rcu_read_unlock(void) +{ + atomic_fetch_sub(&this_rcu_birdloop->ctl, RCU_NEST_CNT); +} + +void synchronize_rcu(void); + +/* Registering and unregistering a birdloop. To be called from birdloop implementation */ +void rcu_birdloop_start(struct rcu_birdloop *); +void rcu_birdloop_stop(struct rcu_birdloop *); + +/* Run this from resource init */ +void rcu_init(void); + +#endif diff --git a/lib/resource.c b/lib/resource.c index c31d9889..898fb533 100644 --- a/lib/resource.c +++ b/lib/resource.c @@ -14,6 +14,7 @@ #include "nest/bird.h" #include "lib/resource.h" #include "lib/string.h" +#include "lib/rcu.h" /** * DOC: Resource pools @@ -29,12 +30,6 @@ * is freed upon shutdown of the module. */ -struct pool { - resource r; - list inside; - const char *name; -}; - static void pool_dump(resource *); static void pool_free(resource *); static resource *pool_lookup(resource *, unsigned long); @@ -285,6 +280,7 @@ void resource_init(void) { resource_sys_init(); + rcu_init(); root_pool.r.class = &pool_class; root_pool.name = "Root"; diff --git a/lib/resource.h b/lib/resource.h index 4cedbf00..5ad011ec 100644 --- a/lib/resource.h +++ b/lib/resource.h @@ -40,7 +40,12 @@ struct resclass { /* Generic resource manipulation */ -typedef struct pool pool; +typedef struct pool { + resource r; + list inside; + const char *name; +} pool; + void resource_init(void); pool *rp_new(pool *, const char *); /* Create new pool */ @@ -115,6 +120,7 @@ void sl_free(void *); void buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size); /* Allocator of whole pages; for use in slabs and other high-level allocators. */ +#define PAGE_HEAD(x) ((void *) (((uintptr_t) (x)) & ~(page_size-1))) extern long page_size; void *alloc_page(void); void free_page(void *); diff --git a/lib/route.h b/lib/route.h index 68596316..2d691215 100644 --- a/lib/route.h +++ b/lib/route.h @@ -29,12 +29,10 @@ typedef struct rte { u8 generation; /* If this route import is based on other previously exported route, this value should be 1 + MAX(generation of the parent routes). Otherwise the route is independent and this value is zero. */ + u8 stale_cycle; /* Auxiliary value for route refresh */ } rte; #define REF_FILTERED 2 /* Route is rejected by import filter */ -#define REF_STALE 4 /* Route is stale in a refresh cycle */ -#define REF_DISCARD 8 /* Route is scheduled for discard */ -#define REF_MODIFY 16 /* Route is scheduled for modify */ #define REF_PENDING 32 /* Route has not propagated completely yet */ /* Route is valid for propagation (may depend on other flags in the future), accepts NULL */ @@ -425,7 +423,7 @@ static inline int ea_is_cached(const ea_list *r) { return r->flags & EALF_CACHED static inline struct ea_storage *ea_get_storage(ea_list *r) { ASSERT_DIE(ea_is_cached(r)); - return SKIP_BACK(struct ea_storage, l, r); + return SKIP_BACK(struct ea_storage, l[0], r); } static inline ea_list *ea_clone(ea_list *r) { ea_get_storage(r)->uc++; return r; } @@ -197,7 +197,7 @@ static struct resclass sl_class = { slab_memsize }; -#define SL_GET_HEAD(x) ((struct sl_head *) (((uintptr_t) (x)) & ~(page_size-1))) +#define SL_GET_HEAD(x) PAGE_HEAD(x) #define SL_HEAD_CHANGE_STATE(_s, _h, _from, _to) ({ \ ASSERT_DIE(_h->state == slh_##_from); \ diff --git a/lib/socket.h b/lib/socket.h index 0b6ac589..5c69482e 100644 --- a/lib/socket.h +++ b/lib/socket.h @@ -12,6 +12,7 @@ #include <errno.h> #include "lib/resource.h" +#include "lib/event.h" #ifdef HAVE_LIBSSH #define LIBSSH_LEGACY_0_4 #include <libssh/libssh.h> @@ -79,6 +80,7 @@ typedef struct birdsock { const char *password; /* Password for MD5 authentication */ const char *err; /* Error message */ struct ssh_sock *ssh; /* Used in SK_SSH */ + struct event reloop; /* Reloop event */ } sock; sock *sock_new(pool *); /* Allocate new socket */ @@ -129,6 +131,7 @@ extern int sk_priority_control; /* Suggested priority for control traffic, shou #define SKF_TRUNCATED 0x200 /* Received packet was truncated, set by IO layer */ #define SKF_HDRINCL 0x400 /* Used internally */ #define SKF_PKTINFO 0x800 /* Used internally */ +#define SKF_PASSIVE_THREAD 0x1000 /* Child sockets used in thread, do not add to main loop */ /* * Socket types SA SP DA DP IF TTL SendTo (?=may, -=must not, *=must) diff --git a/lib/timer.c b/lib/timer.c index c47e0bbc..ff6975a4 100644 --- a/lib/timer.c +++ b/lib/timer.c @@ -36,57 +36,13 @@ #include "lib/resource.h" #include "lib/timer.h" - -struct timeloop main_timeloop; - - -#ifdef USE_PTHREADS - #include <pthread.h> -/* Data accessed and modified from proto/bfd/io.c */ -pthread_key_t current_time_key; - -static inline struct timeloop * -timeloop_current(void) -{ - return pthread_getspecific(current_time_key); -} - -static inline void -timeloop_init_current(void) -{ - pthread_key_create(¤t_time_key, NULL); - pthread_setspecific(current_time_key, &main_timeloop); -} +_Atomic btime last_time; +_Atomic btime real_time; void wakeup_kick_current(void); -#else - -/* Just use main timelooop */ -static inline struct timeloop * timeloop_current(void) { return &main_timeloop; } -static inline void timeloop_init_current(void) { } - -#endif - -btime -current_time(void) -{ - return timeloop_current()->last_time; -} - -btime -current_real_time(void) -{ - struct timeloop *loop = timeloop_current(); - - if (!loop->real_time) - times_update_real_time(loop); - - return loop->real_time; -} - #define TIMER_LESS(a,b) ((a)->expires < (b)->expires) #define TIMER_SWAP(heap,a,b,t) (t = heap[a], heap[a] = heap[b], heap[b] = t, \ @@ -112,7 +68,7 @@ tm_dump(resource *r) if (t->recurrent) debug("recur %d, ", t->recurrent); if (t->expires) - debug("expires in %d ms)\n", (t->expires - current_time()) TO_MS); + debug("in loop %p expires in %d ms)\n", t->loop, (t->expires - current_time()) TO_MS); else debug("inactive)\n"); } @@ -135,41 +91,40 @@ tm_new(pool *p) return t; } -void -tm_set(timer *t, btime when) +static void +tm_set_in_tl(timer *t, btime when, struct timeloop *local_timeloop) { - struct timeloop *loop = timeloop_current(); - uint tc = timers_count(loop); + uint tc = timers_count(local_timeloop); if (!t->expires) { t->index = ++tc; t->expires = when; - BUFFER_PUSH(loop->timers) = t; - HEAP_INSERT(loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP); + BUFFER_PUSH(local_timeloop->timers) = t; + HEAP_INSERT(local_timeloop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP); } else if (t->expires < when) { t->expires = when; - HEAP_INCREASE(loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); + HEAP_INCREASE(local_timeloop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); } else if (t->expires > when) { t->expires = when; - HEAP_DECREASE(loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); + HEAP_DECREASE(local_timeloop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); } -#ifdef CONFIG_BFD - /* Hack to notify BFD loops */ - if ((loop != &main_timeloop) && (t->index == 1)) - wakeup_kick_current(); -#endif + t->loop = local_timeloop; + + if (t->index == 1) + birdloop_ping(local_timeloop->loop); } void -tm_start(timer *t, btime after) +tm_set_in(timer *t, btime when, struct birdloop *loop) { - tm_set(t, current_time() + MAX(after, 0)); + ASSERT_DIE(birdloop_inside(loop)); + tm_set_in_tl(t, when, birdloop_time_loop(loop)); } void @@ -178,20 +133,22 @@ tm_stop(timer *t) if (!t->expires) return; - struct timeloop *loop = timeloop_current(); - uint tc = timers_count(loop); + TLOCK_TIMER_ASSERT(t->loop); - HEAP_DELETE(loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); - BUFFER_POP(loop->timers); + uint tc = timers_count(t->loop); + + HEAP_DELETE(t->loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); + BUFFER_POP(t->loop->timers); t->index = -1; t->expires = 0; + t->loop = NULL; } void timers_init(struct timeloop *loop, pool *p) { - times_init(loop); + TLOCK_TIMER_ASSERT(loop); BUFFER_INIT(loop->timers, p, 4); BUFFER_PUSH(loop->timers) = NULL; @@ -200,13 +157,15 @@ timers_init(struct timeloop *loop, pool *p) void io_log_event(void *hook, void *data); void -timers_fire(struct timeloop *loop) +timers_fire(struct timeloop *loop, int io_log) { + TLOCK_TIMER_ASSERT(loop); + btime base_time; timer *t; - times_update(loop); - base_time = loop->last_time; + times_update(); + base_time = current_time(); while (t = timers_first(loop)) { @@ -217,19 +176,19 @@ timers_fire(struct timeloop *loop) { btime when = t->expires + t->recurrent; - if (when <= loop->last_time) - when = loop->last_time + t->recurrent; + if (when <= base_time) + when = base_time + t->recurrent; if (t->randomize) when += random() % (t->randomize + 1); - tm_set(t, when); + tm_set_in_tl(t, when, loop); } else tm_stop(t); /* This is ugly hack, we want to log just timers executed from the main I/O loop */ - if (loop == &main_timeloop) + if (io_log) io_log_event(t->hook, t->data); t->hook(t); @@ -237,13 +196,6 @@ timers_fire(struct timeloop *loop) } } -void -timer_init(void) -{ - timers_init(&main_timeloop, &root_pool); - timeloop_init_current(); -} - /** * tm_parse_time - parse a date and time diff --git a/lib/timer.h b/lib/timer.h index c5ea430c..555fc96f 100644 --- a/lib/timer.h +++ b/lib/timer.h @@ -12,8 +12,14 @@ #include "nest/bird.h" #include "lib/buffer.h" +#include "lib/io-loop.h" +#include "lib/locking.h" #include "lib/resource.h" +#include <stdatomic.h> + +extern _Atomic btime last_time; +extern _Atomic btime real_time; typedef struct timer { @@ -25,36 +31,42 @@ typedef struct timer uint randomize; /* Amount of randomization */ uint recurrent; /* Timer recurrence */ + struct timeloop *loop; /* Loop where the timer is active */ + int index; } timer; struct timeloop { BUFFER_(timer *) timers; - btime last_time; - btime real_time; + struct domain_generic *domain; + struct birdloop *loop; }; +#define TLOCK_TIMER_ASSERT(loop) ASSERT_DIE((loop)->domain && DG_IS_LOCKED((loop)->domain)) +#define TLOCK_LOCAL_ASSERT(loop) ASSERT_DIE(!(loop)->domain || DG_IS_LOCKED((loop)->domain)) + static inline uint timers_count(struct timeloop *loop) -{ return loop->timers.used - 1; } +{ TLOCK_TIMER_ASSERT(loop); return loop->timers.used - 1; } static inline timer *timers_first(struct timeloop *loop) -{ return (loop->timers.used > 1) ? loop->timers.data[1] : NULL; } +{ TLOCK_TIMER_ASSERT(loop); return (loop->timers.used > 1) ? loop->timers.data[1] : NULL; } -extern struct timeloop main_timeloop; - -btime current_time(void); -btime current_real_time(void); +#define current_time() atomic_load_explicit(&last_time, memory_order_acquire) +#define current_real_time() atomic_load_explicit(&real_time, memory_order_acquire) //#define now (current_time() TO_S) //#define now_real (current_real_time() TO_S) extern btime boot_time; timer *tm_new(pool *p); -void tm_set(timer *t, btime when); -void tm_start(timer *t, btime after); +#define tm_set(t, when) tm_set_in((t), (when), &main_birdloop) +#define tm_start(t, after) tm_start_in((t), (after), &main_birdloop) void tm_stop(timer *t); +void tm_set_in(timer *t, btime when, struct birdloop *loop); +#define tm_start_in(t, after, loop) tm_set_in((t), (current_time() + MAX_((after), 0)), loop) + static inline int tm_active(timer *t) { @@ -94,15 +106,11 @@ tm_start_max(timer *t, btime after) } /* In sysdep code */ -void times_init(struct timeloop *loop); -void times_update(struct timeloop *loop); -void times_update_real_time(struct timeloop *loop); +void times_update(void); /* For I/O loop */ void timers_init(struct timeloop *loop, pool *p); -void timers_fire(struct timeloop *loop); - -void timer_init(void); +void timers_fire(struct timeloop *loop, int io_log); struct timeformat { diff --git a/misc/bird.spec b/misc/bird.spec index 425a6340..c3fdd7d6 100644 --- a/misc/bird.spec +++ b/misc/bird.spec @@ -1,6 +1,6 @@ Summary: BIRD Internet Routing Daemon Name: bird -Version: 2.0.9 +Version: 2.0.10 Release: 1 Copyright: GPL Group: Networking/Daemons diff --git a/nest/Makefile b/nest/Makefile index 0350c3b6..39617350 100644 --- a/nest/Makefile +++ b/nest/Makefile @@ -6,7 +6,11 @@ $(call proto-build,dev_build) $(proto-build-c): $(lastword $(MAKEFILE_LIST)) $(E)echo GEN $@ - $(Q)echo "#include \"lib/birdlib.h\"\n$(patsubst %,void %(void);\n,$(PROTO_BUILD)) void protos_build_gen(void) { $(patsubst %, %();\n,$(PROTO_BUILD))}" > $@ + $(Q)echo "#include \"lib/birdlib.h\"" > $@ + $(Q)$(patsubst %,echo 'void %(void);' >> $@;,$(PROTO_BUILD)) + $(Q)echo "void protos_build_gen(void) {" >> $@ + $(Q)$(patsubst %,echo ' %();'>>$@;,$(PROTO_BUILD)) + $(Q)echo "}" >> $@ tests_src := tests_targets := $(tests_targets) $(tests-target-files) diff --git a/nest/config.Y b/nest/config.Y index edddfc2b..91147a29 100644 --- a/nest/config.Y +++ b/nest/config.Y @@ -125,7 +125,7 @@ CF_KEYWORDS(TIMEFORMAT, ISO, SHORT, LONG, ROUTE, PROTOCOL, BASE, LOG, S, MS, US) CF_KEYWORDS(GRACEFUL, RESTART, WAIT, MAX, AS) CF_KEYWORDS(MIN, IDLE, RX, TX, INTERVAL, MULTIPLIER, PASSIVE) CF_KEYWORDS(CHECK, LINK) -CF_KEYWORDS(SORTED, TRIE, MIN, MAX, SETTLE, TIME) +CF_KEYWORDS(CORK, SORTED, TRIE, MIN, MAX, SETTLE, TIME, GC, THRESHOLD, PERIOD) /* For r_args_channel */ CF_KEYWORDS(IPV4, IPV4_MC, IPV4_MPLS, IPV6, IPV6_MC, IPV6_MPLS, IPV6_SADR, VPN4, VPN4_MC, VPN4_MPLS, VPN6, VPN6_MC, VPN6_MPLS, ROA4, ROA6, FLOW4, FLOW6, MPLS, PRI, SEC) @@ -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)) @@ -229,6 +229,12 @@ table_opt: } | MIN SETTLE TIME expr_us { this_table->min_settle_time = $4; } | MAX SETTLE TIME expr_us { this_table->max_settle_time = $4; } + | GC THRESHOLD expr { this_table->gc_threshold = $3; } + | GC PERIOD expr_us { this_table->gc_period = (uint) $3; if ($3 > 3600 S_) cf_error("GC period must be at most 3600 s"); } + | CORK THRESHOLD expr expr { + if ($3 > $4) cf_error("Cork low threshold must be lower than the high threshold."); + this_table->cork_threshold.low = $3; + this_table->cork_threshold.high = $4; } ; table_opts: @@ -384,7 +390,7 @@ debug_default: DEBUG PROTOCOLS debug_mask { new_config->proto_default_debug = $3; } | DEBUG CHANNELS debug_mask { new_config->channel_default_debug = $3; } | DEBUG COMMANDS expr { new_config->cli_debug = $3; } - | DEBUG PIPE bool { new_config->pipe_debug = $3; } + | DEBUG TABLES bool { new_config->table_debug = $3; } ; /* MRTDUMP PROTOCOLS is in systep/unix/config.Y */ @@ -470,6 +476,7 @@ proto: dev_proto '}' ; dev_proto_start: proto_start DIRECT { this_proto = proto_config_new(&proto_device, $1); init_list(&DIRECT_CFG->iface_list); + this_proto->late_if_feed = 1; } ; @@ -875,7 +882,7 @@ CF_CLI(DUMP FILTER ALL,,, [[Dump all filters in linearized form]]) { filters_dump_all(); cli_msg(0, ""); } ; CF_CLI(EVAL, term, <expr>, [[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 [, ...] }) [<buffer-size>], [[Control echoing of log messages]]) { diff --git a/nest/proto.c b/nest/proto.c index 061205c1..1d480ba2 100644 --- a/nest/proto.c +++ b/nest/proto.c @@ -57,7 +57,28 @@ static void channel_feed_end(struct channel *c); static void channel_export_stopped(struct rt_export_request *req); static inline int proto_is_done(struct proto *p) -{ return (p->proto_state == PS_DOWN) && (p->active_channels == 0); } +{ return (p->proto_state == PS_DOWN) && proto_is_inactive(p); } + +static inline event_list *proto_event_list(struct proto *p) +{ return p->loop == &main_birdloop ? &global_event_list : birdloop_event_list(p->loop); } + +static inline event_list *proto_work_list(struct proto *p) +{ return p->loop == &main_birdloop ? &global_work_list : birdloop_event_list(p->loop); } + +static inline void proto_send_event(struct proto *p) +{ ev_send(proto_event_list(p), p->event); } + +#define PROTO_ENTER_FROM_MAIN(p) ({ \ + ASSERT_DIE(birdloop_inside(&main_birdloop)); \ + struct birdloop *_loop = (p)->loop; \ + if (_loop != &main_birdloop) birdloop_enter(_loop); \ + _loop; \ + }) + +#define PROTO_LEAVE_FROM_MAIN(loop) ({ if (loop != &main_birdloop) birdloop_leave(loop); }) + +#define PROTO_LOCKED_FROM_MAIN(p) for (struct birdloop *_proto_loop = PROTO_ENTER_FROM_MAIN(p); _proto_loop; PROTO_LEAVE_FROM_MAIN(_proto_loop), (_proto_loop = NULL)) + static inline int channel_is_active(struct channel *c) { return (c->channel_state != CS_DOWN); } @@ -438,7 +459,6 @@ channel_start_import(struct channel *c) .dump_req = channel_dump_import_req, .log_state_change = channel_import_log_state_change, .preimport = channel_preimport, - .rte_modify = c->proto->rte_modify, }; ASSERT(c->channel_state == CS_UP); @@ -468,6 +488,7 @@ channel_start_export(struct channel *c) c->out_req = (struct rt_export_request) { .name = rn, + .list = proto_work_list(c->proto), .addr = c->out_subprefix, .addr_mode = c->out_subprefix ? TE_ADDR_IN : TE_ADDR_NONE, .trace_routes = c->debug | c->proto->debug, @@ -514,7 +535,7 @@ channel_check_stopped(struct channel *c) return; channel_set_state(c, CS_DOWN); - ev_schedule(c->proto->event); + proto_send_event(c->proto); break; case CS_PAUSE: @@ -634,6 +655,7 @@ channel_setup_in_table(struct channel *c) { c->reload_req = (struct rt_export_request) { .name = mb_sprintf(c->proto->pool, "%s.%s.import", c->proto->name, c->name), + .list = proto_work_list(c->proto), .trace_routes = c->debug | c->proto->debug, .export_bulk = channel_reload_export_bulk, .dump_req = channel_reload_dump_req, @@ -698,8 +720,6 @@ channel_do_stop(struct channel *c) CALL(c->channel->shutdown, c); - /* This have to be done in here, as channel pool is freed before channel_do_down() */ - c->out_table = NULL; } static void @@ -721,7 +741,7 @@ channel_do_down(struct channel *c) /* Schedule protocol shutddown */ if (proto_is_done(c->proto)) - ev_schedule(c->proto->event); + proto_send_event(c->proto); } void @@ -1032,17 +1052,34 @@ proto_configure_channel(struct proto *p, struct channel **pc, struct channel_con return 1; } +static void +proto_cleanup(struct proto *p) +{ + rfree(p->pool); + p->pool = NULL; + + p->active = 0; + proto_log_state_change(p); + proto_rethink_goal(p); +} static void -proto_event(void *ptr) +proto_loop_stopped(void *ptr) { struct proto *p = ptr; - if (p->do_start) - { - if_feed_baby(p); - p->do_start = 0; - } + birdloop_enter(&main_birdloop); + + p->loop = &main_birdloop; + proto_cleanup(p); + + birdloop_leave(&main_birdloop); +} + +static void +proto_event(void *ptr) +{ + struct proto *p = ptr; if (p->do_stop) { @@ -1052,14 +1089,10 @@ proto_event(void *ptr) } if (proto_is_done(p)) - { - rfree(p->pool); - p->pool = NULL; - - p->active = 0; - proto_log_state_change(p); - proto_rethink_goal(p); - } + if (p->loop != &main_birdloop) + birdloop_stop_self(p->loop, proto_loop_stopped, p); + else + proto_cleanup(p); } @@ -1100,6 +1133,7 @@ proto_init(struct proto_config *c, node *n) struct protocol *pr = c->protocol; struct proto *p = pr->init(c); + p->loop = &main_birdloop; p->proto_state = PS_DOWN; p->last_state_change = current_time(); p->vrf = c->vrf; @@ -1116,11 +1150,19 @@ proto_init(struct proto_config *c, node *n) static void proto_start(struct proto *p) { - /* Here we cannot use p->cf->name since it won't survive reconfiguration */ - p->pool = rp_new(proto_pool, p->proto->name); + DBG("Kicking %s up\n", p->name); + PD(p, "Starting"); + + p->pool = rp_newf(proto_pool, "Protocol %s", p->cf->name); if (graceful_restart_state == GRS_INIT) p->gr_recovery = 1; + + if (p->cf->loop_order != DOMAIN_ORDER(the_bird)) + p->loop = birdloop_new(p->pool, p->cf->loop_order, p->pool->name); + + PROTO_LOCKED_FROM_MAIN(p) + proto_notify_state(p, (p->proto->start ? p->proto->start(p) : PS_UP)); } @@ -1156,6 +1198,7 @@ proto_config_new(struct protocol *pr, int class) cf->class = class; cf->debug = new_config->proto_default_debug; cf->mrtdump = new_config->proto_default_mrtdump; + cf->loop_order = DOMAIN_ORDER(the_bird); init_list(&cf->channels); @@ -1445,11 +1488,20 @@ protos_commit(struct config *new, struct config *old, int force_reconfig, int ty } static void -proto_rethink_goal(struct proto *p) +proto_shutdown(struct proto *p) { - struct protocol *q; - byte goal; + if (p->proto_state == PS_START || p->proto_state == PS_UP) + { + /* Going down */ + DBG("Kicking %s down\n", p->name); + PD(p, "Shutting down"); + proto_notify_state(p, (p->proto->shutdown ? p->proto->shutdown(p) : PS_DOWN)); + } +} +static void +proto_rethink_goal(struct proto *p) +{ if (p->reconfiguring && !p->active) { struct proto_config *nc = p->cf_new; @@ -1469,32 +1521,12 @@ proto_rethink_goal(struct proto *p) /* Determine what state we want to reach */ if (p->disabled || p->reconfiguring) - goal = PS_DOWN; - else - goal = PS_UP; - - q = p->proto; - if (goal == PS_UP) - { - if (!p->active) - { - /* Going up */ - DBG("Kicking %s up\n", p->name); - PD(p, "Starting"); - proto_start(p); - proto_notify_state(p, (q->start ? q->start(p) : PS_UP)); - } - } - else { - if (p->proto_state == PS_START || p->proto_state == PS_UP) - { - /* Going down */ - DBG("Kicking %s down\n", p->name); - PD(p, "Shutting down"); - proto_notify_state(p, (q->shutdown ? q->shutdown(p) : PS_DOWN)); - } + PROTO_LOCKED_FROM_MAIN(p) + proto_shutdown(p); } + else if (!p->active) + proto_start(p); } struct proto * @@ -1699,7 +1731,7 @@ protos_dump_all(void) #define DPF(x) (p->x ? " " #x : "") debug(" protocol %s (%p) state %s with %d active channels flags: %s%s%s%s%s\n", p->name, p, p_states[p->proto_state], p->active_channels, - DPF(disabled), DPF(active), DPF(do_start), DPF(do_stop), DPF(reconfiguring)); + DPF(disabled), DPF(active), DPF(do_stop), DPF(reconfiguring)); #undef DPF struct channel *c; @@ -1935,8 +1967,8 @@ static inline void proto_do_start(struct proto *p) { p->active = 1; - p->do_start = 1; - ev_schedule(p->event); + if (!p->cf->late_if_feed) + if_feed_baby(p); } static void @@ -1949,6 +1981,9 @@ proto_do_up(struct proto *p) } proto_start_channels(p); + + if (p->cf->late_if_feed) + if_feed_baby(p); } static inline void @@ -1963,9 +1998,6 @@ proto_do_stop(struct proto *p) p->down_sched = 0; p->gr_recovery = 0; - p->do_stop = 1; - ev_schedule(p->event); - if (p->main_source) { rt_unlock_source(p->main_source); @@ -1973,6 +2005,9 @@ proto_do_stop(struct proto *p) } proto_stop_channels(p); + + p->do_stop = 1; + proto_send_event(p); } static void @@ -1983,7 +2018,7 @@ proto_do_down(struct proto *p) /* Shutdown is finished in the protocol event */ if (proto_is_done(p)) - ev_schedule(p->event); + proto_send_event(p); } @@ -2222,7 +2257,7 @@ proto_cmd_disable(struct proto *p, uintptr_t arg, int cnt UNUSED) p->disabled = 1; p->down_code = PDC_CMD_DISABLE; proto_set_message(p, (char *) arg, -1); - proto_rethink_goal(p); + proto_shutdown(p); cli_msg(-9, "%s: disabled", p->name); } @@ -2255,9 +2290,9 @@ proto_cmd_restart(struct proto *p, uintptr_t arg, int cnt UNUSED) p->disabled = 1; p->down_code = PDC_CMD_RESTART; proto_set_message(p, (char *) arg, -1); - proto_rethink_goal(p); + proto_shutdown(p); p->disabled = 0; - proto_rethink_goal(p); + /* After the protocol shuts down, proto_rethink_goal() is run from proto_event. */ cli_msg(-12, "%s: restarted", p->name); } @@ -2332,7 +2367,9 @@ proto_apply_cmd_symbol(const struct symbol *s, void (* cmd)(struct proto *, uint if (s->proto->proto) { - cmd(s->proto->proto, arg, 0); + struct proto *p = s->proto->proto; + PROTO_LOCKED_FROM_MAIN(p) + cmd(p, arg, 0); cli_msg(0, ""); } else @@ -2347,7 +2384,8 @@ proto_apply_cmd_patt(const char *patt, void (* cmd)(struct proto *, uintptr_t, i WALK_LIST(p, proto_list) if (!patt || patmatch(patt, p->name)) - cmd(p, arg, cnt++); + PROTO_LOCKED_FROM_MAIN(p) + cmd(p, arg, cnt++); if (!cnt) cli_msg(8003, "No protocols match"); diff --git a/nest/protocol.h b/nest/protocol.h index 3ccd364a..3c823ae1 100644 --- a/nest/protocol.h +++ b/nest/protocol.h @@ -102,8 +102,10 @@ struct proto_config { u8 net_type; /* Protocol network type (NET_*), 0 for undefined */ u8 disabled; /* Protocol enabled/disabled by default */ u8 vrf_set; /* Related VRF instance (below) is defined */ + u8 late_if_feed; /* Delay interface feed after channels are up */ u32 debug, mrtdump; /* Debugging bitfields, both use D_* constants */ u32 router_id; /* Protocol specific router ID */ + uint loop_order; /* Launch a birdloop on this locking level; use DOMAIN_ORDER(the_bird) for mainloop */ list channels; /* List of channel configs (struct channel_config) */ struct iface *vrf; /* Related VRF instance, NULL if global */ @@ -121,6 +123,7 @@ struct proto { struct proto_config *cf_new; /* Configuration we want to switch to after shutdown (NULL=delete) */ pool *pool; /* Pool containing local objects */ event *event; /* Protocol event */ + struct birdloop *loop; /* BIRDloop running this protocol */ list channels; /* List of channels to rtables (struct channel) */ struct channel *main_channel; /* Primary channel */ @@ -131,12 +134,12 @@ struct proto { u32 debug; /* Debugging flags */ u32 mrtdump; /* MRTDump flags */ uint active_channels; /* Number of active channels */ + uint active_loops; /* Number of active IO loops */ byte net_type; /* Protocol network type (NET_*), 0 for undefined */ byte disabled; /* Manually disabled */ byte vrf_set; /* Related VRF instance (above) is defined */ byte proto_state; /* Protocol state machine (PS_*, see below) */ byte active; /* From PS_START to cleanup after PS_STOP */ - byte do_start; /* Start actions are scheduled */ byte do_stop; /* Stop actions are scheduled */ byte reconfiguring; /* We're shutting down due to reconfiguration */ byte gr_recovery; /* Protocol should participate in graceful restart recovery */ @@ -189,7 +192,6 @@ struct proto { int (*rte_recalculate)(struct rtable *, struct network *, struct rte *, struct rte *, struct rte *); int (*rte_better)(struct rte *, struct rte *); int (*rte_mergable)(struct rte *, struct rte *); - struct rte *(*rte_modify)(struct rte *, struct linpool *); void (*rte_insert)(struct network *, struct rte *); void (*rte_remove)(struct network *, struct rte *); u32 (*rte_igp_metric)(const struct rte *); @@ -339,6 +341,8 @@ void proto_notify_state(struct proto *p, unsigned state); * as a result of received ROUTE-REFRESH request). */ +static inline int proto_is_inactive(struct proto *p) +{ return (p->active_channels == 0) && (p->active_loops == 0); } /* diff --git a/nest/rt-show.c b/nest/rt-show.c index c3294518..b784bf83 100644 --- a/nest/rt-show.c +++ b/nest/rt-show.c @@ -77,7 +77,11 @@ rt_show_rte(struct cli *c, byte *ia, rte *e, struct rt_show_data *d, int primary e->src->proto->name, tm, from, primary ? (sync_error ? " !" : " *") : "", info); if (d->verbose) + { ea_show_list(c, a); + cli_printf(c, -1008, "\tInternal route handling values: %uL %uG %uS id %u", + e->src->private_id, e->src->global_id, e->stale_cycle, e->id); + } else if (dest == RTD_UNICAST) ea_show_nexthop_list(c, nhad); else if (had) @@ -256,6 +260,18 @@ rt_show_dump_req(struct rt_export_request *req) } static void +rt_show_done(struct rt_show_data *d) +{ + /* No more action */ + d->cli->cleanup = NULL; + d->cli->cont = NULL; + d->cli->rover = NULL; + + /* Write pending messages */ + cli_write_trigger(d->cli); +} + +static void rt_show_cont(struct rt_show_data *d) { struct cli *c = d->cli; @@ -263,18 +279,13 @@ rt_show_cont(struct rt_show_data *d) if (d->running_on_config && (d->running_on_config != config)) { cli_printf(c, 8004, "Stopped due to reconfiguration"); - - /* No more action */ - c->cleanup = NULL; - c->cont = NULL; - c->rover = NULL; - cli_write_trigger(c); - return; + return rt_show_done(d); } d->req = (struct rt_export_request) { .addr = d->addr, .name = "CLI Show Route", + .list = &global_work_list, .export_bulk = rt_show_net_export_bulk, .dump_req = rt_show_dump_req, .log_state_change = rt_show_log_state_change, @@ -316,7 +327,6 @@ rt_show_export_stopped(struct rt_export_request *req) if (NODE_VALID(d->tab)) return rt_show_cont(d); - /* Printout total stats */ if (d->stats && (d->table_counter > 1)) { @@ -329,7 +339,8 @@ rt_show_export_stopped(struct rt_export_request *req) else cli_printf(d->cli, 0, ""); - cli_write_trigger(d->cli); + /* No more route showing */ + rt_show_done(d); } struct rt_show_data_rtable * diff --git a/nest/rt-table.c b/nest/rt-table.c index 29690414..15dbc371 100644 --- a/nest/rt-table.c +++ b/nest/rt-table.c @@ -110,6 +110,8 @@ #include "proto/bgp/bgp.h" #endif +#include <stdatomic.h> + pool *rt_table_pool; static linpool *rte_update_pool; @@ -117,6 +119,18 @@ static linpool *rte_update_pool; list routing_tables; list deleted_routing_tables; +struct rt_cork rt_cork; + +/* Data structures for export journal */ +#define RT_PENDING_EXPORT_ITEMS (page_size - sizeof(struct rt_export_block)) / sizeof(struct rt_pending_export) + +struct rt_export_block { + node n; + _Atomic u32 end; + _Atomic _Bool not_last; + struct rt_pending_export export[]; +}; + static void rt_free_hostcache(rtable *tab); static void rt_notify_hostcache(rtable *tab, net *net); static void rt_update_hostcache(rtable *tab); @@ -126,11 +140,23 @@ static inline void rt_flowspec_resolve_rte(rte *r, struct channel *c); static inline void rt_prune_table(rtable *tab); static inline void rt_schedule_notify(rtable *tab); static void rt_flowspec_notify(rtable *tab, net *net); +static void rt_kick_prune_timer(rtable *tab); static void rt_feed_by_fib(void *); static void rt_feed_by_trie(void *); static void rt_feed_equal(void *); static void rt_feed_for(void *); static uint rt_feed_net(struct rt_export_hook *c, net *n); +static void rt_check_cork_low(rtable *tab); +static void rt_check_cork_high(rtable *tab); +static void rt_cork_release_hook(void *); + +static inline void rt_export_used(struct rt_exporter *); +static void rt_export_cleanup(rtable *tab); + +static inline void rte_update_lock(void); +static inline void rte_update_unlock(void); + +static int rte_same(rte *x, rte *y); const char *rt_import_state_name_array[TIS_MAX] = { [TIS_DOWN] = "DOWN", @@ -684,8 +710,9 @@ rte_mergable(rte *pri, rte *sec) static void rte_trace(const char *name, const rte *e, int dir, const char *msg) { - log(L_TRACE "%s %c %s %N %uL %uG %s", - name, dir, msg, e->net, e->src->private_id, e->src->global_id, + log(L_TRACE "%s %c %s %N src %uL %uG %uS id %u %s", + name, dir, msg, e->net, + e->src->private_id, e->src->global_id, e->stale_cycle, e->id, rta_dest_name(rte_dest(e))); } @@ -725,8 +752,8 @@ rte_feed_count(net *n) { uint count = 0; for (struct rte_storage *e = n->routes; e; e = e->next) - if (rte_is_valid(RTE_OR_NULL(e))) - count++; + count++; + return count; } @@ -735,11 +762,11 @@ rte_feed_obtain(net *n, struct rte **feed, uint count) { uint i = 0; for (struct rte_storage *e = n->routes; e; e = e->next) - if (rte_is_valid(RTE_OR_NULL(e))) { ASSERT_DIE(i < count); feed[i++] = &e->rte; } + ASSERT_DIE(i == count); } @@ -847,6 +874,16 @@ do_rt_notify(struct channel *c, const net_addr *net, rte *new, const rte *old) static void rt_notify_basic(struct channel *c, const net_addr *net, rte *new, rte *old) { + if (new && old && rte_same(new, old)) + { + if ((new->id != old->id) && bmap_test(&c->export_map, old->id)) + { + bmap_set(&c->export_map, new->id); + bmap_clear(&c->export_map, old->id); + } + return; + } + if (new) new = export_filter(c, new, 0); @@ -859,6 +896,16 @@ rt_notify_basic(struct channel *c, const net_addr *net, rte *new, rte *old) do_rt_notify(c, net, new, old); } +static void +channel_rpe_mark_seen(struct rt_export_request *req, struct rt_pending_export *rpe) +{ + struct channel *c = SKIP_BACK(struct channel, out_req, req); + + rpe_mark_seen(req->hook, rpe); + if (rpe->old) + bmap_clear(&c->export_reject_map, rpe->old->rte.id); +} + void rt_notify_accepted(struct rt_export_request *req, const net_addr *n, struct rt_pending_export *rpe, struct rte **feed, uint count) @@ -902,38 +949,30 @@ rt_notify_accepted(struct rt_export_request *req, const net_addr *n, struct rt_p } } +done: /* Check obsolete routes for previously exported */ - if (!old_best) - if (rpe && rpe->old && bmap_test(&c->export_map, rpe->old->rte.id)) - old_best = &rpe->old->rte; - -/* for (; rpe; rpe = atomic_load_explicit(&rpe->next, memory_order_relaxed)) + while (rpe) + { + channel_rpe_mark_seen(req, rpe); + if (rpe->old) { - if (rpe->old && bmap_test(&hook->accept_map, rpe->old->id)) + if (bmap_test(&c->export_map, rpe->old->rte.id)) { - old_best = &rpe->old.rte; - break; + ASSERT_DIE(old_best == NULL); + old_best = &rpe->old->rte; } - - if (rpe == rpe_last) - break; } - */ + rpe = rpe_next(rpe, NULL); + } /* Nothing to export */ if (!new_best && !old_best) { DBG("rt_notify_accepted: nothing to export\n"); - goto done; + return; } do_rt_notify(c, n, new_best, old_best); - -done: - /* Drop the old stored rejection if applicable. - * new->id == old->id happens when updating hostentries. */ - if (rpe && rpe->old && (!rpe->new || (rpe->new->rte.id != rpe->old->rte.id))) - bmap_clear(&c->export_reject_map, rpe->old->rte.id); } rte * @@ -1025,63 +1064,74 @@ rt_notify_merged(struct rt_export_request *req, const net_addr *n, struct rt_pen } /* Check obsolete routes for previously exported */ - if (!old_best) - if (rpe && rpe->old && bmap_test(&c->export_map, rpe->old->rte.id)) - old_best = &rpe->old->rte; - -/* for (; rpe; rpe = atomic_load_explicit(&rpe->next, memory_order_relaxed)) + while (rpe) + { + channel_rpe_mark_seen(req, rpe); + if (rpe->old) { - if (rpe->old && bmap_test(&hook->accept_map, rpe->old->id)) + if (bmap_test(&c->export_map, rpe->old->rte.id)) { - old_best = &rpe->old.rte; - break; + ASSERT_DIE(old_best == NULL); + old_best = &rpe->old->rte; } - - if (rpe == rpe_last) - break; } - */ + rpe = rpe_next(rpe, NULL); + } /* Prepare new merged route */ rte *new_merged = count ? rt_export_merged(c, feed, count, rte_update_pool, 0) : NULL; if (new_merged || old_best) do_rt_notify(c, n, new_merged, old_best); - - /* Drop the old stored rejection if applicable. - * new->id == old->id happens when updating hostentries. */ - if (rpe && rpe->old && (!rpe->new || (rpe->new->rte.id != rpe->old->rte.id))) - bmap_clear(&c->export_reject_map, rpe->old->rte.id); } void rt_notify_optimal(struct rt_export_request *req, const net_addr *net, struct rt_pending_export *rpe) { struct channel *c = SKIP_BACK(struct channel, out_req, req); - rte n0; - if (rpe->new_best != rpe->old_best) - rt_notify_basic(c, net, RTE_COPY(rpe->new_best, &n0), RTE_OR_NULL(rpe->old_best)); + rte *o = RTE_VALID_OR_NULL(rpe->old_best); + struct rte_storage *new_best = rpe->new_best; - /* Drop the old stored rejection if applicable. - * new->id == old->id happens when updating hostentries. */ - if (rpe->old && (!rpe->new || (rpe->new->rte.id != rpe->old->rte.id))) - bmap_clear(&c->export_reject_map, rpe->old->rte.id); + while (rpe) + { + channel_rpe_mark_seen(req, rpe); + new_best = rpe->new_best; + rpe = rpe_next(rpe, NULL); + } + + rte n0 = RTE_COPY_VALID(new_best); + if (n0.src || o) + rt_notify_basic(c, net, n0.src ? &n0 : NULL, o); } void rt_notify_any(struct rt_export_request *req, const net_addr *net, struct rt_pending_export *rpe) { struct channel *c = SKIP_BACK(struct channel, out_req, req); - rte n0; - if (rpe->new != rpe->old) - rt_notify_basic(c, net, RTE_COPY(rpe->new, &n0), RTE_OR_NULL(rpe->old)); + rte *n = RTE_VALID_OR_NULL(rpe->new); + rte *o = RTE_VALID_OR_NULL(rpe->old); - /* Drop the old stored rejection if applicable. - * new->id == old->id happens when updating hostentries. */ - if (rpe->old && (!rpe->new || (rpe->new->rte.id != rpe->old->rte.id))) - bmap_clear(&c->export_reject_map, rpe->old->rte.id); + if (!n && !o) + { + channel_rpe_mark_seen(req, rpe); + return; + } + + struct rte_src *src = n ? n->src : o->src; + struct rte_storage *new_latest = rpe->new; + + while (rpe) + { + channel_rpe_mark_seen(req, rpe); + new_latest = rpe->new; + rpe = rpe_next(rpe, src); + } + + rte n0 = RTE_COPY_VALID(new_latest); + if (n0.src || o) + rt_notify_basic(c, net, n0.src ? &n0 : NULL, o); } void @@ -1090,10 +1140,103 @@ rt_feed_any(struct rt_export_request *req, const net_addr *net, struct rt_pendin struct channel *c = SKIP_BACK(struct channel, out_req, req); for (uint i=0; i<count; i++) + if (rte_is_valid(feed[i])) + { + rte n0 = *feed[i]; + rt_notify_basic(c, net, &n0, NULL); + } +} + +void +rpe_mark_seen(struct rt_export_hook *hook, struct rt_pending_export *rpe) +{ + bmap_set(&hook->seq_map, rpe->seq); +} + +struct rt_pending_export * +rpe_next(struct rt_pending_export *rpe, struct rte_src *src) +{ + struct rt_pending_export *next = atomic_load_explicit(&rpe->next, memory_order_acquire); + + if (!next) + return NULL; + + if (!src) + return next; + + while (rpe = next) + if (src == (rpe->new ? rpe->new->rte.src : rpe->old->rte.src)) + return rpe; + else + next = atomic_load_explicit(&rpe->next, memory_order_acquire); + + return NULL; +} + +static struct rt_pending_export * rt_next_export_fast(struct rt_pending_export *last); +static void +rte_export(struct rt_export_hook *hook, struct rt_pending_export *rpe) +{ + if (bmap_test(&hook->seq_map, rpe->seq)) + goto ignore; /* Seen already */ + + const net_addr *n = rpe->new_best ? rpe->new_best->rte.net : rpe->old_best->rte.net; + + switch (hook->req->addr_mode) + { + case TE_ADDR_NONE: + break; + + case TE_ADDR_IN: + if (!net_in_netX(n, hook->req->addr)) + goto ignore; + break; + + case TE_ADDR_EQUAL: + if (!net_equal(n, hook->req->addr)) + goto ignore; + break; + + case TE_ADDR_FOR: + bug("Continuos export of best prefix match not implemented yet."); + + default: + bug("Strange table export address mode: %d", hook->req->addr_mode); + } + + if (rpe->new) + hook->stats.updates_received++; + else + hook->stats.withdraws_received++; + + if (hook->req->export_one) + hook->req->export_one(hook->req, n, rpe); + else if (hook->req->export_bulk) { - rte n0 = *feed[i]; - rt_notify_basic(c, net, &n0, NULL); + net *net = SKIP_BACK(struct network, n.addr, (net_addr (*)[0]) n); + uint count = rte_feed_count(net); + rte **feed = NULL; + if (count) + { + feed = alloca(count * sizeof(rte *)); + rte_feed_obtain(net, feed, count); + } + hook->req->export_bulk(hook->req, n, rpe, feed, count); } + else + bug("Export request must always provide an export method"); + +ignore: + /* Get the next export if exists */ + hook->rpe_next = rt_next_export_fast(rpe); + + /* The last block may be available to free */ + if (PAGE_HEAD(hook->rpe_next) != PAGE_HEAD(rpe)) + CALL(hook->table->used, hook->table); + + /* Releasing this export for cleanup routine */ + DBG("store hook=%p last_export=%p seq=%lu\n", hook, rpe, rpe->seq); + atomic_store_explicit(&hook->last_export, rpe, memory_order_release); } /** @@ -1131,26 +1274,17 @@ static void rte_announce(rtable *tab, net *net, struct rte_storage *new, struct rte_storage *old, struct rte_storage *new_best, struct rte_storage *old_best) { - if (!rte_is_valid(RTE_OR_NULL(new))) - new = NULL; - - if (!rte_is_valid(RTE_OR_NULL(old))) - old = NULL; + int new_best_valid = rte_is_valid(RTE_OR_NULL(new_best)); + int old_best_valid = rte_is_valid(RTE_OR_NULL(old_best)); - if (!rte_is_valid(RTE_OR_NULL(new_best))) - new_best = NULL; - - if (!rte_is_valid(RTE_OR_NULL(old_best))) - old_best = NULL; - - if (!new && !old && !new_best && !old_best) + if ((new == old) && (new_best == old_best)) return; - if (new_best != old_best) + if (new_best_valid || old_best_valid) { - if (new_best) + if (new_best_valid) new_best->rte.sender->stats.pref++; - if (old_best) + if (old_best_valid) old_best->rte.sender->stats.pref--; if (tab->hostcache) @@ -1162,57 +1296,206 @@ rte_announce(rtable *tab, net *net, struct rte_storage *new, struct rte_storage rt_schedule_notify(tab); - struct rt_pending_export rpe = { .new = new, .old = old, .new_best = new_best, .old_best = old_best }; - uint count = rte_feed_count(net); - rte **feed = NULL; - if (count) + if (EMPTY_LIST(tab->exporter.hooks) && EMPTY_LIST(tab->exporter.pending)) { - feed = alloca(count * sizeof(rte *)); - rte_feed_obtain(net, feed, count); + /* No export hook and no pending exports to cleanup. We may free the route immediately. */ + if (!old) + return; + + hmap_clear(&tab->id_map, old->rte.id); + rte_free(old); + return; } - struct rt_export_hook *eh; - WALK_LIST(eh, tab->exporter.hooks) + /* Get the pending export structure */ + struct rt_export_block *rpeb = NULL, *rpebsnl = NULL; + u32 end = 0; + + if (!EMPTY_LIST(tab->exporter.pending)) + { + rpeb = TAIL(tab->exporter.pending); + end = atomic_load_explicit(&rpeb->end, memory_order_relaxed); + if (end >= RT_PENDING_EXPORT_ITEMS) + { + ASSERT_DIE(end == RT_PENDING_EXPORT_ITEMS); + rpebsnl = rpeb; + + rpeb = NULL; + end = 0; + } + } + + if (!rpeb) + { + rpeb = alloc_page(); + *rpeb = (struct rt_export_block) {}; + add_tail(&tab->exporter.pending, &rpeb->n); + } + + /* Fill the pending export */ + struct rt_pending_export *rpe = &rpeb->export[rpeb->end]; + *rpe = (struct rt_pending_export) { + .new = new, + .new_best = new_best, + .old = old, + .old_best = old_best, + .seq = tab->exporter.next_seq++, + }; + + DBGL("rte_announce: table=%s net=%N new=%p id %u from %s old=%p id %u from %s new_best=%p id %u old_best=%p id %u seq=%lu", + tab->name, net->n.addr, + new, new ? new->rte.id : 0, new ? new->rte.sender->req->name : NULL, + old, old ? old->rte.id : 0, old ? old->rte.sender->req->name : NULL, + new_best, old_best, rpe->seq); + + ASSERT_DIE(atomic_fetch_add_explicit(&rpeb->end, 1, memory_order_release) == end); + + if (rpebsnl) + { + _Bool f = 0; + ASSERT_DIE(atomic_compare_exchange_strong_explicit(&rpebsnl->not_last, &f, 1, + memory_order_release, memory_order_relaxed)); + } + + /* Append to the same-network squasher list */ + if (net->last) + { + struct rt_pending_export *rpenull = NULL; + ASSERT_DIE(atomic_compare_exchange_strong_explicit( + &net->last->next, &rpenull, rpe, + memory_order_relaxed, + memory_order_relaxed)); + + } + + net->last = rpe; + + if (!net->first) + net->first = rpe; + + if (tab->exporter.first == NULL) + tab->exporter.first = rpe; + + rt_check_cork_high(tab); + + if (!tm_active(tab->exporter.export_timer)) + tm_start(tab->exporter.export_timer, tab->config->export_settle_time); +} + +static struct rt_pending_export * +rt_next_export_fast(struct rt_pending_export *last) +{ + /* Get the whole export block and find our position in there. */ + struct rt_export_block *rpeb = PAGE_HEAD(last); + u32 pos = (last - &rpeb->export[0]); + u32 end = atomic_load_explicit(&rpeb->end, memory_order_acquire); + ASSERT_DIE(pos < end); + + /* Next is in the same block. */ + if (++pos < end) + return &rpeb->export[pos]; + + /* There is another block. */ + if (atomic_load_explicit(&rpeb->not_last, memory_order_acquire)) { - if (eh->export_state == TES_STOP) + /* This is OK to do non-atomically because of the not_last flag. */ + rpeb = NODE_NEXT(rpeb); + return &rpeb->export[0]; + } + + /* There is nothing more. */ + return NULL; +} + +static struct rt_pending_export * +rt_next_export(struct rt_export_hook *hook, struct rt_exporter *tab) +{ + /* As the table is locked, it is safe to reload the last export pointer */ + struct rt_pending_export *last = atomic_load_explicit(&hook->last_export, memory_order_acquire); + + /* It is still valid, let's reuse it */ + if (last) + return rt_next_export_fast(last); + + /* No, therefore we must process the table's first pending export */ + else + return tab->first; +} + +static inline void +rt_send_export_event(struct rt_export_hook *hook) +{ + ev_send(hook->req->list, hook->event); +} + +static void +rt_announce_exports(timer *tm) +{ + rtable *tab = tm->data; + + struct rt_export_hook *c; node *n; + WALK_LIST2(c, n, tab->exporter.hooks, n) + { + if (atomic_load_explicit(&c->export_state, memory_order_acquire) != TES_READY) continue; - switch (eh->req->addr_mode) - { - case TE_ADDR_NONE: - break; + rt_send_export_event(c); + } +} - case TE_ADDR_IN: - if (!net_in_netX(net->n.addr, eh->req->addr)) - continue; - break; +static struct rt_pending_export * +rt_last_export(struct rt_exporter *tab) +{ + struct rt_pending_export *rpe = NULL; - case TE_ADDR_EQUAL: - if (!net_equal(net->n.addr, eh->req->addr)) - continue; - break; + if (!EMPTY_LIST(tab->pending)) + { + /* We'll continue processing exports from this export on */ + struct rt_export_block *reb = TAIL(tab->pending); + ASSERT_DIE(reb->end); + rpe = &reb->export[reb->end - 1]; + } - case TE_ADDR_FOR: - bug("Continuos export of best prefix match not implemented yet."); + return rpe; +} - default: - bug("Strange table export address mode: %d", eh->req->addr_mode); +#define RT_EXPORT_BULK 1024 + +static void +rt_export_hook(void *_data) +{ + struct rt_export_hook *c = _data; + + ASSERT_DIE(atomic_load_explicit(&c->export_state, memory_order_relaxed) == TES_READY); + + if (!c->rpe_next) + { + c->rpe_next = rt_next_export(c, c->table); + + if (!c->rpe_next) + { + CALL(c->table->used, c->table); + return; } + } - if (new) - eh->stats.updates_received++; - else - eh->stats.withdraws_received++; + /* Process the export */ + for (uint i=0; i<RT_EXPORT_BULK; i++) + { + rte_update_lock(); - if (eh->req->export_one) - eh->req->export_one(eh->req, net->n.addr, &rpe); - else if (eh->req->export_bulk) - eh->req->export_bulk(eh->req, net->n.addr, &rpe, feed, count); - else - bug("Export request must always provide an export method"); + rte_export(c, c->rpe_next); + + if (!c->rpe_next) + break; + + rte_update_unlock(); } + + rt_send_export_event(c); } + static inline int rte_validate(struct channel *ch, rte *e) { @@ -1322,8 +1605,7 @@ rte_recalculate(struct rt_import_hook *c, net *net, rte *new, struct rte_src *sr if (new && rte_same(old, &new_stored->rte)) { /* No changes, ignore the new route and refresh the old one */ - - old->flags &= ~(REF_STALE | REF_DISCARD | REF_MODIFY); + old->stale_cycle = new->stale_cycle; if (!rte_is_filtered(new)) { @@ -1458,14 +1740,8 @@ rte_recalculate(struct rt_import_hook *c, net *net, rte *new, struct rte_src *sr if (new_stored) { new_stored->rte.lastmod = current_time(); - - if (!old) - { - new_stored->rte.id = hmap_first_zero(&table->id_map); - hmap_set(&table->id_map, new_stored->rte.id); - } - else - new_stored->rte.id = old->id; + new_stored->rte.id = hmap_first_zero(&table->id_map); + hmap_set(&table->id_map, new_stored->rte.id); } /* Log the route change */ @@ -1486,9 +1762,8 @@ rte_recalculate(struct rt_import_hook *c, net *net, rte *new, struct rte_src *sr net->routes, old_best_stored); if (!net->routes && - (table->gc_counter++ >= table->config->gc_max_ops) && - (table->gc_time + table->config->gc_min_time <= current_time())) - rt_schedule_prune(table); + (table->gc_counter++ >= table->config->gc_threshold)) + rt_kick_prune_timer(table); #if 0 /* Enable and reimplement these callbacks if anybody wants to use them */ @@ -1498,13 +1773,6 @@ rte_recalculate(struct rt_import_hook *c, net *net, rte *new, struct rte_src *sr p->rte_insert(net, &new_stored->rte); #endif - if (old) - { - if (!new_stored) - hmap_clear(&table->id_map, old->id); - - rte_free(old_stored); - } } static int rte_update_nest_cnt; /* Nesting counter to allow recursive updates */ @@ -1639,6 +1907,9 @@ rte_import(struct rt_import_request *req, const net_addr *n, rte *new, struct rt nn = net_get(hook->table, n); new->net = nn->n.addr; new->sender = hook; + + /* Set the stale cycle */ + new->stale_cycle = hook->stale_set; } else if (!(nn = net_find(hook->table, n))) { @@ -1669,24 +1940,6 @@ rte_discard(net *net, rte *old) /* Non-filtered route deletion, used during garb rte_update_unlock(); } -/* Modify existing route by protocol hook, used for long-lived graceful restart */ -static inline void -rte_modify(net *net, rte *old) -{ - rte_update_lock(); - - rte *new = old->sender->req->rte_modify(old, rte_update_pool); - if (new != old) - { - if (new) - new->flags = old->flags & ~REF_MODIFY; - - rte_recalculate(old->sender, net, new, old->src); - } - - rte_update_unlock(); -} - /* Check rtable for best route to given net whether it would be exported do p */ int rt_examine(rtable *t, net_addr *a, struct channel *c, const struct filter *filter) @@ -1726,16 +1979,19 @@ rt_export_stopped(void *data) struct rt_export_hook *hook = data; struct rt_exporter *tab = hook->table; + /* Drop pending exports */ + CALL(tab->used, tab); + /* Unlist */ rem_node(&hook->n); - /* Reporting the channel as stopped. */ + /* Report the channel as stopped. */ hook->stopped(hook->req); /* Reporting the hook as finished. */ CALL(tab->done, hook); - /* Freeing the hook together with its coroutine. */ + /* Free the hook. */ rfree(hook->pool); } @@ -1753,7 +2009,7 @@ void rt_set_export_state(struct rt_export_hook *hook, u8 state) { hook->last_state_change = current_time(); - hook->export_state = state; + atomic_store_explicit(&hook->export_state, state, memory_order_release); if (hook->req->log_state_change) hook->req->log_state_change(hook->req, state); @@ -1799,7 +2055,6 @@ rt_table_export_start(struct rt_exporter *re, struct rt_export_request *req) pool *p = rp_new(tab->rp, "Export hook"); struct rt_export_hook *hook = mb_allocz(p, sizeof(struct rt_export_hook)); hook->pool = p; - hook->lp = lp_new_default(p); /* stats zeroed by mb_allocz */ switch (req->addr_mode) @@ -1844,12 +2099,18 @@ rt_request_export(struct rt_exporter *re, struct rt_export_request *req) hook->req = req; hook->table = re; + bmap_init(&hook->seq_map, hook->pool, 1024); + + struct rt_pending_export *rpe = rt_last_export(hook->table); + DBG("store hook=%p last_export=%p seq=%lu\n", hook, rpe, rpe ? rpe->seq : 0); + atomic_store_explicit(&hook->last_export, rpe, memory_order_relaxed); + hook->n = (node) {}; add_tail(&re->hooks, &hook->n); /* Regular export */ rt_set_export_state(hook, TES_FEEDING); - ev_schedule_work(hook->event); + rt_send_export_event(hook); } static void @@ -1857,7 +2118,7 @@ rt_table_export_stop(struct rt_export_hook *hook) { rtable *tab = SKIP_BACK(rtable, exporter, hook->table); - if (hook->export_state != TES_FEEDING) + if (atomic_load_explicit(&hook->export_state, memory_order_relaxed) != TES_FEEDING) return; switch (hook->req->addr_mode) @@ -1898,7 +2159,7 @@ rt_stop_export(struct rt_export_request *req, void (*stopped)(struct rt_export_r rt_set_export_state(hook, TES_STOP); /* Run the stopped event */ - ev_schedule(hook->event); + rt_send_export_event(hook); } /** @@ -1916,15 +2177,38 @@ rt_stop_export(struct rt_export_request *req, void (*stopped)(struct rt_export_r * flag in rt_refresh_end() and then removing such routes in the prune loop. */ void -rt_refresh_begin(rtable *t, struct rt_import_request *req) +rt_refresh_begin(struct rt_import_request *req) { - FIB_WALK(&t->fib, net, n) - { - for (struct rte_storage *e = n->routes; e; e = e->next) - if (e->rte.sender == req->hook) - e->rte.flags |= REF_STALE; - } - FIB_WALK_END; + struct rt_import_hook *hook = req->hook; + ASSERT_DIE(hook); + ASSERT_DIE(hook->stale_set == hook->stale_valid); + + /* If the pruning routine is too slow */ + if ((hook->stale_pruned < hook->stale_valid) && (hook->stale_pruned + 128 < hook->stale_valid) + || (hook->stale_pruned > hook->stale_valid) && (hook->stale_pruned > hook->stale_valid + 128)) + { + log(L_WARN "Route refresh flood in table %s", hook->table->name); + FIB_WALK(&hook->table->fib, net, n) + { + for (struct rte_storage *e = n->routes; e; e = e->next) + if (e->rte.sender == req->hook) + e->rte.stale_cycle = 0; + } + FIB_WALK_END; + hook->stale_set = 1; + hook->stale_valid = 0; + hook->stale_pruned = 0; + } + /* Setting a new value of the stale modifier */ + else if (!++hook->stale_set) + { + /* Let's reserve the stale_cycle zero value for always-invalid routes */ + hook->stale_set = 1; + hook->stale_valid = 0; + } + + if (req->trace_routes & D_STATES) + log(L_TRACE "%s: route refresh begin [%u]", req->name, hook->stale_set); } /** @@ -1936,43 +2220,18 @@ rt_refresh_begin(rtable *t, struct rt_import_request *req) * hook. See rt_refresh_begin() for description of refresh cycles. */ void -rt_refresh_end(rtable *t, struct rt_import_request *req) +rt_refresh_end(struct rt_import_request *req) { - int prune = 0; - - FIB_WALK(&t->fib, net, n) - { - for (struct rte_storage *e = n->routes; e; e = e->next) - if ((e->rte.sender == req->hook) && (e->rte.flags & REF_STALE)) - { - e->rte.flags |= REF_DISCARD; - prune = 1; - } - } - FIB_WALK_END; - - if (prune) - rt_schedule_prune(t); -} + struct rt_import_hook *hook = req->hook; + ASSERT_DIE(hook); -void -rt_modify_stale(rtable *t, struct rt_import_request *req) -{ - int prune = 0; + hook->stale_valid++; + ASSERT_DIE(hook->stale_set == hook->stale_valid); - FIB_WALK(&t->fib, net, n) - { - for (struct rte_storage *e = n->routes; e; e = e->next) - if ((e->rte.sender == req->hook) && (e->rte.flags & REF_STALE) && !(e->rte.flags & REF_FILTERED)) - { - e->rte.flags |= REF_MODIFY; - prune = 1; - } - } - FIB_WALK_END; + rt_schedule_prune(hook->table); - if (prune) - rt_schedule_prune(t); + if (req->trace_routes & D_STATES) + log(L_TRACE "%s: route refresh end [%u]", req->name, hook->stale_valid); } /** @@ -2054,8 +2313,8 @@ rt_dump_hooks(rtable *tab) { eh->req->dump_req(eh->req); debug(" Export hook %p requested by %p:" - " refeed_pending=%u last_state_change=%t export_state=%u stopped=%p\n", - eh, eh->req, eh->refeed_pending, eh->last_state_change, eh->export_state, eh->stopped); + " refeed_pending=%u last_state_change=%t export_state=%u\n", + eh, eh->req, eh->refeed_pending, eh->last_state_change, atomic_load_explicit(&eh->export_state, memory_order_relaxed)); } debug("\n"); } @@ -2108,6 +2367,20 @@ rt_schedule_prune(rtable *tab) tab->prune_state |= 1; } +static void +rt_export_used(struct rt_exporter *e) +{ + rtable *tab = SKIP_BACK(rtable, exporter, e); + + if (config->table_debug) + log(L_TRACE "%s: Export cleanup requested", tab->name); + + if (tab->export_used) + return; + + tab->export_used = 1; + ev_schedule(tab->rt_event); +} static void rt_event(void *ptr) @@ -2116,6 +2389,25 @@ rt_event(void *ptr) rt_lock_table(tab); + if (tab->export_used) + rt_export_cleanup(tab); + + if ( + tab->hcu_corked || + tab->nhu_corked || + (tab->hcu_scheduled || tab->nhu_state) && rt_cork_check(tab->uncork_event) + ) + { + if (!tab->hcu_corked && !tab->nhu_corked && config->table_debug) + log(L_TRACE "%s: Auxiliary routines corked", tab->name); + + tab->hcu_corked |= tab->hcu_scheduled; + tab->hcu_scheduled = 0; + + tab->nhu_corked |= tab->nhu_state; + tab->nhu_state = 0; + } + if (tab->hcu_scheduled) rt_update_hostcache(tab); @@ -2128,6 +2420,45 @@ rt_event(void *ptr) rt_unlock_table(tab); } +static void +rt_uncork_event(void *ptr) +{ + rtable *tab = ptr; + + tab->hcu_scheduled |= tab->hcu_corked; + tab->hcu_corked = 0; + + tab->nhu_state |= tab->nhu_corked; + tab->nhu_corked = 0; + + if (config->table_debug) + log(L_TRACE "%s: Auxiliary routines uncorked", tab->name); + + ev_schedule(tab->rt_event); +} + +static void +rt_prune_timer(timer *t) +{ + rtable *tab = t->data; + + if (tab->gc_counter >= tab->config->gc_threshold) + rt_schedule_prune(tab); +} + +static void +rt_kick_prune_timer(rtable *tab) +{ + /* Return if prune is already scheduled */ + if (tm_active(tab->prune_timer) || (tab->prune_state & 1)) + return; + + /* Randomize GC period to +/- 50% */ + btime gc_period = tab->config->gc_period; + gc_period = (gc_period / 2) + (random_u32() % (uint) gc_period); + tm_start(tab->prune_timer, gc_period); +} + static inline btime rt_settled_time(rtable *tab) @@ -2293,9 +2624,6 @@ rt_free(resource *_r) DBG("Deleting routing table %s\n", r->name); ASSERT_DIE(r->use_count == 0); - if (r->internal) - return; - r->config->table = NULL; rem_node(&r->n); @@ -2359,28 +2687,34 @@ rt_setup(pool *pp, struct rtable_config *cf) .start = rt_table_export_start, .stop = rt_table_export_stop, .done = rt_table_export_done, + .used = rt_export_used, }; + init_list(&t->exporter.hooks); + init_list(&t->exporter.pending); - if (!(t->internal = cf->internal)) - { - init_list(&t->imports); + init_list(&t->imports); - hmap_init(&t->id_map, p, 1024); - hmap_set(&t->id_map, 0); + hmap_init(&t->id_map, p, 1024); + hmap_set(&t->id_map, 0); - init_list(&t->subscribers); + init_list(&t->subscribers); - t->rt_event = ev_new_init(p, rt_event, t); - t->last_rt_change = t->gc_time = current_time(); + t->rt_event = ev_new_init(p, rt_event, t); + t->uncork_event = ev_new_init(p, rt_uncork_event, t); + t->prune_timer = tm_new_init(p, rt_prune_timer, t, 0, 0); + t->exporter.export_timer = tm_new_init(p, rt_announce_exports, t, 0, 0); + t->last_rt_change = t->gc_time = current_time(); + t->exporter.next_seq = 1; - t->rl_pipe = (struct tbf) TBF_DEFAULT_LOG_LIMITS; + t->cork_threshold = cf->cork_threshold; - if (rt_is_flow(t)) - { - t->flowspec_trie = f_new_trie(lp_new_default(p), 0); - t->flowspec_trie->ipv4 = (t->addr_type == NET_FLOW4); - } + t->rl_pipe = (struct tbf) TBF_DEFAULT_LOG_LIMITS; + + if (rt_is_flow(t)) + { + t->flowspec_trie = f_new_trie(lp_new_default(p), 0); + t->flowspec_trie->ipv4 = (t->addr_type == NET_FLOW4); } return t; @@ -2400,6 +2734,8 @@ rt_init(void) rte_update_pool = lp_new_default(rt_table_pool); init_list(&routing_tables); init_list(&deleted_routing_tables); + ev_init_list(&rt_cork.queue, &main_birdloop, "Route cork release"); + rt_cork.run = (event) { .hook = rt_cork_release_hook }; } @@ -2440,10 +2776,20 @@ rt_prune_table(rtable *tab) WALK_LIST2(ih, n, tab->imports, n) if (ih->import_state == TIS_STOP) rt_set_import_state(ih, TIS_FLUSHING); + else if ((ih->stale_valid != ih->stale_pruning) && (ih->stale_pruning == ih->stale_pruned)) + { + ih->stale_pruning = ih->stale_valid; + + if (ih->req->trace_routes & D_STATES) + log(L_TRACE "%s: table prune after refresh begin [%u]", ih->req->name, ih->stale_pruning); + } FIB_ITERATE_INIT(fit, &tab->fib); tab->prune_state = 2; + tab->gc_counter = 0; + tab->gc_time = current_time(); + if (tab->prune_trie) { /* Init prefix trie pruning */ @@ -2465,24 +2811,19 @@ again: for (struct rte_storage *e=n->routes; e; e=e->next) { - if ((e->rte.sender->import_state == TIS_FLUSHING) || (e->rte.flags & REF_DISCARD)) + struct rt_import_hook *s = e->rte.sender; + if ((s->import_state == TIS_FLUSHING) || + (e->rte.stale_cycle < s->stale_valid) || + (e->rte.stale_cycle > s->stale_set)) { rte_discard(n, &e->rte); limit--; goto rescan; } - - if (e->rte.flags & REF_MODIFY) - { - rte_modify(n, &e->rte); - limit--; - - goto rescan; - } } - if (!n->routes) /* Orphaned FIB entry */ + if (!n->routes && !n->first) /* Orphaned FIB entry */ { FIB_ITERATE_PUT(fit); fib_delete(&tab->fib, n); @@ -2501,9 +2842,6 @@ again: fib_check(&tab->fib); #endif - tab->gc_counter = 0; - tab->gc_time = current_time(); - /* state change 2->0, 3->1 */ tab->prune_state &= 1; @@ -2540,16 +2878,212 @@ again: rt_prune_sources(); + uint flushed_channels = 0; + /* Close flushed channels */ WALK_LIST2_DELSAFE(ih, n, x, tab->imports, n) if (ih->import_state == TIS_FLUSHING) { - rt_set_import_state(ih, TIS_CLEARED); - ih->stopped(ih->req); - rem_node(&ih->n); - mb_free(ih); - rt_unlock_table(tab); + ih->flush_seq = tab->exporter.next_seq; + rt_set_import_state(ih, TIS_WAITING); + flushed_channels++; + } + else if (ih->stale_pruning != ih->stale_pruned) + { + ih->stale_pruned = ih->stale_pruning; + if (ih->req->trace_routes & D_STATES) + log(L_TRACE "%s: table prune after refresh end [%u]", ih->req->name, ih->stale_pruned); + } + + /* In some cases, we may want to directly proceed to export cleanup */ + if (EMPTY_LIST(tab->exporter.hooks) && flushed_channels) + rt_export_cleanup(tab); +} + +static void +rt_export_cleanup(rtable *tab) +{ + tab->export_used = 0; + + u64 min_seq = ~((u64) 0); + struct rt_pending_export *last_export_to_free = NULL; + struct rt_pending_export *first = tab->exporter.first; + + struct rt_export_hook *eh; + node *n; + WALK_LIST2(eh, n, tab->exporter.hooks, n) + { + switch (atomic_load_explicit(&eh->export_state, memory_order_acquire)) + { + case TES_DOWN: + continue; + + case TES_READY: + { + struct rt_pending_export *last = atomic_load_explicit(&eh->last_export, memory_order_acquire); + if (!last) + /* No last export means that the channel has exported nothing since last cleanup */ + goto done; + + else if (min_seq > last->seq) + { + min_seq = last->seq; + last_export_to_free = last; + } + continue; + } + + default: + /* It's only safe to cleanup when the export state is idle or regular. No feeding or stopping allowed. */ + goto done; + } + } + + tab->exporter.first = last_export_to_free ? rt_next_export_fast(last_export_to_free) : NULL; + + if (config->table_debug) + log(L_TRACE "%s: Export cleanup, old exporter.first seq %lu, new %lu, min_seq %ld", + tab->name, + first ? first->seq : 0, + tab->exporter.first ? tab->exporter.first->seq : 0, + min_seq); + + WALK_LIST2(eh, n, tab->exporter.hooks, n) + { + if (atomic_load_explicit(&eh->export_state, memory_order_acquire) != TES_READY) + continue; + + struct rt_pending_export *last = atomic_load_explicit(&eh->last_export, memory_order_acquire); + if (last == last_export_to_free) + { + /* This may fail when the channel managed to export more inbetween. This is OK. */ + atomic_compare_exchange_strong_explicit( + &eh->last_export, &last, NULL, + memory_order_release, + memory_order_relaxed); + + DBG("store hook=%p last_export=NULL\n", eh); + } + } + + while (first && (first->seq <= min_seq)) + { + ASSERT_DIE(first->new || first->old); + + const net_addr *n = first->new ? + first->new->rte.net : + first->old->rte.net; + net *net = SKIP_BACK(struct network, n.addr, (net_addr (*)[0]) n); + + ASSERT_DIE(net->first == first); + + if (first == net->last) + /* The only export here */ + net->last = net->first = NULL; + else + /* First is now the next one */ + net->first = atomic_load_explicit(&first->next, memory_order_relaxed); + + /* For now, the old route may be finally freed */ + if (first->old) + { + rt_rte_trace_in(D_ROUTES, first->old->rte.sender->req, &first->old->rte, "freed"); + hmap_clear(&tab->id_map, first->old->rte.id); + rte_free(first->old); } + +#ifdef LOCAL_DEBUG + memset(first, 0xbd, sizeof(struct rt_pending_export)); +#endif + + struct rt_export_block *reb = HEAD(tab->exporter.pending); + ASSERT_DIE(reb == PAGE_HEAD(first)); + + u32 pos = (first - &reb->export[0]); + u32 end = atomic_load_explicit(&reb->end, memory_order_relaxed); + ASSERT_DIE(pos < end); + + struct rt_pending_export *next = NULL; + + if (++pos < end) + next = &reb->export[pos]; + else + { + rem_node(&reb->n); + +#ifdef LOCAL_DEBUG + memset(reb, 0xbe, page_size); +#endif + + free_page(reb); + + if (EMPTY_LIST(tab->exporter.pending)) + { + if (config->table_debug) + log(L_TRACE "%s: Resetting export seq", tab->name); + + node *n; + WALK_LIST2(eh, n, tab->exporter.hooks, n) + { + if (atomic_load_explicit(&eh->export_state, memory_order_acquire) != TES_READY) + continue; + + ASSERT_DIE(atomic_load_explicit(&eh->last_export, memory_order_acquire) == NULL); + bmap_reset(&eh->seq_map, 1024); + } + + tab->exporter.next_seq = 1; + } + else + { + reb = HEAD(tab->exporter.pending); + next = &reb->export[0]; + } + } + + first = next; + } + + rt_check_cork_low(tab); + +done:; + struct rt_import_hook *ih; node *x; + _Bool imports_stopped = 0; + WALK_LIST2_DELSAFE(ih, n, x, tab->imports, n) + if (ih->import_state == TIS_WAITING) + if (!first || (first->seq >= ih->flush_seq)) + { + ih->import_state = TIS_CLEARED; + ih->stopped(ih->req); + rem_node(&ih->n); + mb_free(ih); + rt_unlock_table(tab); + imports_stopped = 1; + } + + if (tab->export_used) + ev_schedule(tab->rt_event); + + if (imports_stopped) + { + if (config->table_debug) + log(L_TRACE "%s: Sources pruning routine requested", tab->name); + + rt_prune_sources(); + } + + if (EMPTY_LIST(tab->exporter.pending) && tm_active(tab->exporter.export_timer)) + tm_stop(tab->exporter.export_timer); +} + +static void +rt_cork_release_hook(void *data UNUSED) +{ + do synchronize_rcu(); + while ( + !atomic_load_explicit(&rt_cork.active, memory_order_acquire) && + ev_run_list(&rt_cork.queue) + ); } /** @@ -2627,6 +3161,20 @@ rt_preconfig(struct config *c) rt_new_table(cf_get_symbol("master6"), NET_IP6); } +void +rt_postconfig(struct config *c) +{ + uint num_tables = list_length(&c->tables); + btime def_gc_period = 400 MS * num_tables; + def_gc_period = MAX(def_gc_period, 10 S); + def_gc_period = MIN(def_gc_period, 600 S); + + struct rtable_config *rc; + WALK_LIST(rc, c->tables) + if (rc->gc_period == (uint) -1) + rc->gc_period = (uint) def_gc_period; +} + /* * Some functions for handing internal next hop updates @@ -3017,6 +3565,11 @@ rt_next_hop_update_net(rtable *tab, net *n) /* Replace the route in the list */ new->next = e->next; *k = e = new; + + /* Get a new ID for the route */ + new->rte.lastmod = current_time(); + new->rte.id = hmap_first_zero(&tab->id_map); + hmap_set(&tab->id_map, new->rte.id); } ASSERT_DIE(pos <= count); @@ -3043,14 +3596,14 @@ rt_next_hop_update_net(rtable *tab, net *n) for (int i=0; i<count; i++) { _Bool nb = (new == updates[i].new), ob = (old_best == updates[i].old); - const char *best_indicator[2][2] = { { "updated", "updated [-best]" }, { "updated [+best]", "updated [best]" } }; + const char *best_indicator[2][2] = { + { "autoupdated", "autoupdated [-best]" }, + { "autoupdated [+best]", "autoupdated [best]" } + }; rt_rte_trace_in(D_ROUTES, updates[i].new->rte.sender->req, &updates[i].new->rte, best_indicator[nb][ob]); rte_announce_i(tab, n, updates[i].new, updates[i].old, new, old_best); } - for (int i=0; i<count; i++) - rte_free(updates[i].old); - return count; } @@ -3109,10 +3662,12 @@ rt_new_table(struct symbol *s, uint addr_type) cf_define_symbol(s, SYM_TABLE, table, c); c->name = s->name; c->addr_type = addr_type; - c->gc_max_ops = 1000; - c->gc_min_time = 5; + c->gc_threshold = 1000; + c->gc_period = (uint) -1; /* set in rt_postconfig() */ c->min_settle_time = 1 S; c->max_settle_time = 20 S; + c->cork_threshold.low = 128; + c->cork_threshold.high = 512; add_tail(&new_config->tables, &c->n); @@ -3158,6 +3713,36 @@ rt_unlock_table(rtable *r) } } +static void +rt_check_cork_low(rtable *tab) +{ + if (!tab->cork_active) + return; + + if (!tab->exporter.first || (tab->exporter.first->seq + tab->cork_threshold.low > tab->exporter.next_seq)) + { + tab->cork_active = 0; + rt_cork_release(); + + if (config->table_debug) + log(L_TRACE "%s: Uncorked", tab->name); + } +} + +static void +rt_check_cork_high(rtable *tab) +{ + if (!tab->cork_active && tab->exporter.first && (tab->exporter.first->seq + tab->cork_threshold.high <= tab->exporter.next_seq)) + { + tab->cork_active = 1; + rt_cork_acquire(); + + if (config->table_debug) + log(L_TRACE "%s: Corked", tab->name); + } +} + + static int rt_reconfigure(rtable *tab, struct rtable_config *new, struct rtable_config *old) { @@ -3171,6 +3756,14 @@ rt_reconfigure(rtable *tab, struct rtable_config *new, struct rtable_config *old tab->name = new->name; tab->config = new; + tab->cork_threshold = new->cork_threshold; + + if (new->cork_threshold.high != old->cork_threshold.high) + rt_check_cork_high(tab); + + if (new->cork_threshold.low != old->cork_threshold.low) + rt_check_cork_low(tab); + return 1; } @@ -3229,6 +3822,16 @@ rt_commit(struct config *new, struct config *old) DBG("\tdone\n"); } +static void +rt_feed_done(struct rt_export_hook *c) +{ + c->event->hook = rt_export_hook; + + rt_set_export_state(c, TES_READY); + + rt_send_export_event(c); +} + /** * rt_feed_by_fib - advertise all routes to a channel by walking a fib * @c: channel to be fed @@ -3246,7 +3849,7 @@ rt_feed_by_fib(void *data) struct fib_iterator *fit = &c->feed_fit; int max_feed = 256; - ASSERT(c->export_state == TES_FEEDING); + ASSERT(atomic_load_explicit(&c->export_state, memory_order_relaxed) == TES_FEEDING); rtable *tab = SKIP_BACK(rtable, exporter, c->table); @@ -3255,18 +3858,19 @@ rt_feed_by_fib(void *data) if (max_feed <= 0) { FIB_ITERATE_PUT(fit); - ev_schedule_work(c->event); + rt_send_export_event(c); return; } - ASSERT(c->export_state == TES_FEEDING); + if (atomic_load_explicit(&c->export_state, memory_order_acquire) != TES_FEEDING) + return; if ((c->req->addr_mode == TE_ADDR_NONE) || net_in_netX(n->n.addr, c->req->addr)) max_feed -= rt_feed_net(c, n); } FIB_ITERATE_END; - rt_set_export_state(c, TES_READY); + rt_feed_done(c); } static void @@ -3280,7 +3884,7 @@ rt_feed_by_trie(void *data) int max_feed = 256; - ASSERT_DIE(c->export_state == TES_FEEDING); + ASSERT(atomic_load_explicit(&c->export_state, memory_order_relaxed) == TES_FEEDING); net_addr addr; while (trie_walk_next(ws, &addr)) @@ -3292,7 +3896,8 @@ rt_feed_by_trie(void *data) if ((max_feed -= rt_feed_net(c, n)) <= 0) return; - ASSERT_DIE(c->export_state == TES_FEEDING); + if (atomic_load_explicit(&c->export_state, memory_order_acquire) != TES_FEEDING) + return; } rt_unlock_trie(tab, c->walk_lock); @@ -3301,7 +3906,7 @@ rt_feed_by_trie(void *data) mb_free(c->walk_state); c->walk_state = NULL; - rt_set_export_state(c, TES_READY); + rt_feed_done(c); } static void @@ -3310,14 +3915,14 @@ rt_feed_equal(void *data) struct rt_export_hook *c = data; rtable *tab = SKIP_BACK(rtable, exporter, c->table); - ASSERT_DIE(c->export_state == TES_FEEDING); + ASSERT_DIE(atomic_load_explicit(&c->export_state, memory_order_relaxed) == TES_FEEDING); ASSERT_DIE(c->req->addr_mode == TE_ADDR_EQUAL); net *n = net_find(tab, c->req->addr); if (n) rt_feed_net(c, n); - rt_set_export_state(c, TES_READY); + rt_feed_done(c); } static void @@ -3326,52 +3931,53 @@ rt_feed_for(void *data) struct rt_export_hook *c = data; rtable *tab = SKIP_BACK(rtable, exporter, c->table); - ASSERT_DIE(c->export_state == TES_FEEDING); + ASSERT_DIE(atomic_load_explicit(&c->export_state, memory_order_relaxed) == TES_FEEDING); ASSERT_DIE(c->req->addr_mode == TE_ADDR_FOR); net *n = net_route(tab, c->req->addr); if (n) rt_feed_net(c, n); - rt_set_export_state(c, TES_READY); + rt_feed_done(c); } static uint rt_feed_net(struct rt_export_hook *c, net *n) { - if (c->req->export_bulk) - { - uint count = rte_feed_count(n); - if (count) - { - rte_update_lock(); - rte **feed = alloca(count * sizeof(rte *)); - rte_feed_obtain(n, feed, count); - struct rt_pending_export rpe = { .new_best = n->routes }; - c->req->export_bulk(c->req, n->n.addr, &rpe, feed, count); - rte_update_unlock(); - } - return count; - } + uint count = 0; - if (n->routes && rte_is_valid(&n->routes->rte)) - { - rte_update_lock(); - struct rt_pending_export rpe = { .new = n->routes, .new_best = n->routes }; - c->req->export_one(c->req, n->n.addr, &rpe); - rte_update_unlock(); - return 1; - } + if (c->req->export_bulk) + { + count = rte_feed_count(n); + if (count) + { + rte_update_lock(); + rte **feed = alloca(count * sizeof(rte *)); + rte_feed_obtain(n, feed, count); + c->req->export_bulk(c->req, n->n.addr, NULL, feed, count); + rte_update_unlock(); + } + } - return 0; -} + else if (n->routes) + { + rte_update_lock(); + struct rt_pending_export rpe = { .new = n->routes, .new_best = n->routes }; + c->req->export_one(c->req, n->n.addr, &rpe); + rte_update_unlock(); + count = 1; + } + for (struct rt_pending_export *rpe = n->first; rpe; rpe = rpe_next(rpe, NULL)) + rpe_mark_seen(c, rpe); + + return count; +} /* * Import table */ - void channel_reload_export_bulk(struct rt_export_request *req, const net_addr *net, struct rt_pending_export *rpe UNUSED, rte **feed, uint count) { struct channel *c = SKIP_BACK(struct channel, reload_req, req); @@ -3589,9 +4195,12 @@ rt_update_hostentry(rtable *tab, struct hostentry *he) { struct rte_storage *e = n->routes; ea_list *a = e->rte.attrs; - pxlen = n->n.addr->pxlen; + u32 pref = rt_get_preference(&e->rte); - if (ea_find(a, &ea_gen_hostentry)) + for (struct rte_storage *ee = n->routes; ee; ee = ee->next) + if (rte_is_valid(&ee->rte) && + (rt_get_preference(&ee->rte) >= pref) && + ea_find(ee->rte.attrs, &ea_gen_hostentry)) { /* Recursive route should not depend on another recursive route */ log(L_WARN "Next hop address %I resolvable through recursive route for %N", @@ -3599,6 +4208,8 @@ rt_update_hostentry(rtable *tab, struct hostentry *he) goto done; } + pxlen = n->n.addr->pxlen; + eattr *nhea = ea_find(a, &ea_gen_nexthop); ASSERT_DIE(nhea); struct nexthop_adata *nhad = (void *) nhea->u.ptr; @@ -17,6 +17,10 @@ #include "lib/type.h" #include "lib/fib.h" #include "lib/route.h" +#include "lib/event.h" +#include "lib/rcu.h" + +#include <stdatomic.h> struct ea_list; struct protocol; @@ -30,6 +34,10 @@ struct f_trie; struct f_trie_walk_state; struct cli; +struct rt_cork_threshold { + u64 low, high; +}; + /* * Master Routing Tables. Generally speaking, each of them contains a FIB * with each entry pointing to a list of route entries representing routes @@ -47,13 +55,14 @@ struct rtable_config { struct rtable *table; struct proto_config *krt_attached; /* Kernel syncer attached to this table */ uint addr_type; /* Type of address data stored in table (NET_*) */ - int gc_max_ops; /* Maximum number of operations before GC is run */ - int gc_min_time; /* Minimum time between two consecutive GC runs */ + uint gc_threshold; /* Maximum number of operations before GC is run */ + uint gc_period; /* Approximate time between two consecutive GC runs */ byte sorted; /* Routes of network are sorted according to rte_better() */ - byte internal; /* Internal table of a protocol */ byte trie_used; /* Rtable has attached trie */ btime min_settle_time; /* Minimum settle time for notifications */ btime max_settle_time; /* Maximum settle time for notifications */ + btime export_settle_time; /* Delay before exports are announced */ + struct rt_cork_threshold cork_threshold; /* Cork threshold values */ }; struct rt_export_hook; @@ -62,9 +71,17 @@ struct rt_export_request; struct rt_exporter { list hooks; /* Registered route export hooks */ uint addr_type; /* Type of address data exported (NET_*) */ + struct rt_export_hook *(*start)(struct rt_exporter *, struct rt_export_request *); void (*stop)(struct rt_export_hook *); void (*done)(struct rt_export_hook *); + void (*used)(struct rt_exporter *); + + list pending; /* List of packed struct rt_pending_export */ + struct timer *export_timer; + + struct rt_pending_export *first; /* First export to announce */ + u64 next_seq; /* The next export will have this ID */ }; typedef struct rtable { @@ -90,15 +107,21 @@ typedef struct rtable { * obstacle from this routing table. */ struct event *rt_event; /* Routing table event */ + struct event *uncork_event; /* Called when uncork happens */ + struct timer *prune_timer; /* Timer for periodic pruning / GC */ btime last_rt_change; /* Last time when route changed */ btime base_settle_time; /* Start time of rtable settling interval */ btime gc_time; /* Time of last GC */ - int gc_counter; /* Number of operations since last GC */ + uint gc_counter; /* Number of operations since last GC */ byte prune_state; /* Table prune state, 1 -> scheduled, 2-> running */ byte prune_trie; /* Prune prefix trie during next table prune */ byte hcu_scheduled; /* Hostcache update is scheduled */ + byte hcu_corked; /* Hostcache update is corked with this state */ byte nhu_state; /* Next Hop Update state */ - byte internal; /* This table is internal for some other object */ + byte nhu_corked; /* Next Hop Update is corked with this state */ + byte export_used; /* Pending Export pruning is scheduled */ + byte cork_active; /* Cork has been activated */ + struct rt_cork_threshold cork_threshold; /* Threshold for table cork */ struct fib_iterator prune_fit; /* Rtable prune FIB iterator */ struct fib_iterator nhu_fit; /* Next Hop Update FIB iterator */ struct f_trie *trie_new; /* New prefix trie defined during pruning */ @@ -127,13 +150,48 @@ struct rt_flowspec_link { u32 uc; }; +extern struct rt_cork { + _Atomic uint active; + event_list queue; + event run; +} rt_cork; + +static inline void rt_cork_acquire(void) +{ + atomic_fetch_add_explicit(&rt_cork.active, 1, memory_order_acq_rel); +} + +static inline void rt_cork_release(void) +{ + if (atomic_fetch_sub_explicit(&rt_cork.active, 1, memory_order_acq_rel) == 1) + { + synchronize_rcu(); + ev_schedule_work(&rt_cork.run); + } +} + +static inline int rt_cork_check(event *e) +{ + rcu_read_lock(); + + int corked = (atomic_load_explicit(&rt_cork.active, memory_order_acquire) > 0); + if (corked) + ev_send(&rt_cork.queue, e); + + rcu_read_unlock(); + + return corked; +} + + #define NHU_CLEAN 0 #define NHU_SCHEDULED 1 #define NHU_RUNNING 2 #define NHU_DIRTY 3 typedef struct network { - struct rte_storage *routes; /* Available routes for this network */ + struct rte_storage *routes; /* Available routes for this network */ + struct rt_pending_export *first, *last; struct fib_node n; /* FIB flags reserved for kernel syncer */ } net; @@ -168,8 +226,10 @@ struct rte_storage { struct rte rte; /* Route data */ }; -#define RTE_COPY(r, l) ((r) ? (((*(l)) = (r)->rte), (l)) : NULL) -#define RTE_OR_NULL(r) ((r) ? &((r)->rte) : NULL) +#define RTE_COPY(r) ((r) ? (r)->rte : (rte) {}) +#define RTE_COPY_VALID(r) (((r) && (rte_is_valid(&(r)->rte))) ? (r)->rte : (rte) {}) +#define RTE_OR_NULL(r) ((r) ? &((r)->rte) : NULL) +#define RTE_VALID_OR_NULL(r) (((r) && (rte_is_valid(&(r)->rte))) ? &((r)->rte) : NULL) /* Table-channel connections */ @@ -183,7 +243,6 @@ struct rt_import_request { /* Preimport is called when the @new route is just-to-be inserted, replacing @old. * Return a route (may be different or modified in-place) to continue or NULL to withdraw. */ int (*preimport)(struct rt_import_request *req, struct rte *new, struct rte *old); - struct rte *(*rte_modify)(struct rte *, struct linpool *); }; struct rt_import_hook { @@ -200,15 +259,22 @@ struct rt_import_hook { u32 withdraws_accepted; /* Number of route withdraws accepted and processed */ } stats; + u64 flush_seq; /* Table export seq when the channel announced flushing */ btime last_state_change; /* Time of last state transition */ u8 import_state; /* IS_* */ + u8 stale_set; /* Set this stale_cycle to imported routes */ + u8 stale_valid; /* Routes with this stale_cycle and bigger are considered valid */ + u8 stale_pruned; /* Last prune finished when this value was set at stale_valid */ + u8 stale_pruning; /* Last prune started when this value was set at stale_valid */ void (*stopped)(struct rt_import_request *); /* Stored callback when import is stopped */ }; struct rt_pending_export { + struct rt_pending_export * _Atomic next; /* Next export for the same destination */ struct rte_storage *new, *new_best, *old, *old_best; + u64 seq; /* Sequential ID (table-local) of the pending export */ }; struct rt_export_request { @@ -218,6 +284,8 @@ struct rt_export_request { u8 trace_routes; u8 addr_mode; /* Network prefilter mode (TE_ADDR_*) */ + event_list *list; /* Where to schedule export events */ + /* There are two methods of export. You can either request feeding every single change * or feeding the whole route feed. In case of regular export, &export_one is preferred. * Anyway, when feeding, &export_bulk is preferred, falling back to &export_one. @@ -237,7 +305,6 @@ struct rt_export_hook { struct rt_exporter *table; /* The connected table */ pool *pool; - linpool *lp; struct rt_export_request *req; /* The requestor */ @@ -256,10 +323,15 @@ struct rt_export_hook { u32 hash_iter; /* Iterator over hash */ }; + struct bmap seq_map; /* Keep track which exports were already procesed */ + + struct rt_pending_export * _Atomic last_export;/* Last export processed */ + struct rt_pending_export *rpe_next; /* Next pending export to process */ + btime last_state_change; /* Time of last state transition */ u8 refeed_pending; /* Refeeding and another refeed is scheduled */ - u8 export_state; /* Route export state (TES_*, see below) */ + _Atomic u8 export_state; /* Route export state (TES_*, see below) */ u8 feed_type; /* Which feeding method is used (TFT_*, see below) */ struct event *event; /* Event running all the export operations */ @@ -310,6 +382,15 @@ void rt_set_export_state(struct rt_export_hook *hook, u8 state); void rte_import(struct rt_import_request *req, const net_addr *net, rte *new, struct rte_src *src); +/* Get next rpe. If src is given, it must match. */ +struct rt_pending_export *rpe_next(struct rt_pending_export *rpe, struct rte_src *src); + +/* Mark the pending export processed */ +void rpe_mark_seen(struct rt_export_hook *hook, struct rt_pending_export *rpe); + +/* Get pending export seen status */ +int rpe_get_seen(struct rt_export_hook *hook, struct rt_pending_export *rpe); + /* Types of route announcement, also used as flags */ #define RA_UNDEF 0 /* Undefined RA type */ #define RA_OPTIMAL 1 /* Announcement of optimal route change */ @@ -363,6 +444,7 @@ struct config; void rt_init(void); void rt_preconfig(struct config *); +void rt_postconfig(struct config *); void rt_commit(struct config *new, struct config *old); void rt_lock_table(rtable *); void rt_unlock_table(rtable *); @@ -383,8 +465,8 @@ net *net_get(rtable *tab, const net_addr *addr); net *net_route(rtable *tab, const net_addr *n); int rt_examine(rtable *t, net_addr *a, struct channel *c, const struct filter *filter); rte *rt_export_merged(struct channel *c, rte ** feed, uint count, linpool *pool, int silent); -void rt_refresh_begin(rtable *t, struct rt_import_request *); -void rt_refresh_end(rtable *t, struct rt_import_request *); +void rt_refresh_begin(struct rt_import_request *); +void rt_refresh_end(struct rt_import_request *); void rt_modify_stale(rtable *t, struct rt_import_request *); void rt_schedule_prune(rtable *t); void rte_dump(struct rte_storage *); diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 4939619f..00b9aa79 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -315,7 +315,9 @@ babel_add_seqno_request(struct babel_proto *p, struct babel_entry *e, /* Found older */ rem_node(NODE sr); - rem_node(&sr->nbr_node); + + if (sr->nbr) + rem_node(&sr->nbr_node); goto found; } @@ -455,10 +457,7 @@ babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) struct babel_seqno_request *sr; WALK_LIST_FIRST2(sr, nbr_node, nbr->requests) - { - sr->nbr = NULL; - rem_node(&sr->nbr_node); - } + babel_remove_seqno_request(p, sr); nbr->ifa = NULL; rem_node(NODE nbr); @@ -2258,9 +2257,9 @@ babel_kick_timer(struct babel_proto *p) static int -babel_preexport(struct channel *c, struct rte *new) +babel_preexport(struct channel *C, struct rte *new) { - if (new->src->proto != c->proto) + if (new->src->proto != C->proto) return 0; /* Reject our own unreachable routes */ diff --git a/proto/bfd/Makefile b/proto/bfd/Makefile index dbdc0a09..11d639d7 100644 --- a/proto/bfd/Makefile +++ b/proto/bfd/Makefile @@ -1,4 +1,4 @@ -src := bfd.c io.c packets.c +src := bfd.c packets.c obj := $(src-o-files) $(all-daemon) $(cf-local) diff --git a/proto/bfd/bfd.c b/proto/bfd/bfd.c index 871ecf69..e7d27f74 100644 --- a/proto/bfd/bfd.c +++ b/proto/bfd/bfd.c @@ -113,8 +113,16 @@ #define HASH_IP_EQ(a1,n1,a2,n2) ipa_equal(a1, a2) && n1 == n2 #define HASH_IP_FN(a,n) ipa_hash(a) ^ u32_hash(n) -static list STATIC_LIST_INIT(bfd_proto_list); -static list STATIC_LIST_INIT(bfd_wait_list); +DEFINE_DOMAIN(rtable); +#define BFD_LOCK LOCK_DOMAIN(rtable, bfd_global.lock) +#define BFD_UNLOCK UNLOCK_DOMAIN(rtable, bfd_global.lock) + +static struct { + DOMAIN(rtable) lock; + list wait_list; + list pickup_list; + list proto_list; +} bfd_global; const char *bfd_state_names[] = { "AdminDown", "Down", "Init", "Up" }; @@ -188,7 +196,7 @@ bfd_session_update_tx_interval(struct bfd_session *s) return; /* Set timer relative to last tx_timer event */ - tm_set(s->tx_timer, s->last_tx + tx_int_l); + tm_set_in(s->tx_timer, s->last_tx + tx_int_l, s->ifa->bfd->p.loop); } static void @@ -202,7 +210,7 @@ bfd_session_update_detection_time(struct bfd_session *s, int kick) if (!s->last_rx) return; - tm_set(s->hold_timer, s->last_rx + timeout); + tm_set_in(s->hold_timer, s->last_rx + timeout, s->ifa->bfd->p.loop); } static void @@ -226,7 +234,7 @@ bfd_session_control_tx_timer(struct bfd_session *s, int reset) if (reset || !tm_active(s->tx_timer)) { s->last_tx = 0; - tm_start(s->tx_timer, 0); + tm_start_in(s->tx_timer, 0, s->ifa->bfd->p.loop); } return; @@ -419,7 +427,7 @@ bfd_get_free_id(struct bfd_proto *p) static struct bfd_session * bfd_add_session(struct bfd_proto *p, ip_addr addr, ip_addr local, struct iface *iface, struct bfd_options *opts) { - birdloop_enter(p->loop); + ASSERT_DIE(birdloop_inside(p->p.loop)); struct bfd_iface *ifa = bfd_get_iface(p, local, iface); @@ -454,8 +462,6 @@ bfd_add_session(struct bfd_proto *p, ip_addr addr, ip_addr local, struct iface * TRACE(D_EVENTS, "Session to %I added", s->addr); - birdloop_leave(p->loop); - return s; } @@ -463,38 +469,34 @@ bfd_add_session(struct bfd_proto *p, ip_addr addr, ip_addr local, struct iface * static void bfd_open_session(struct bfd_proto *p, struct bfd_session *s, ip_addr local, struct iface *ifa) { - birdloop_enter(p->loop); + birdloop_enter(p->p.loop); s->opened = 1; bfd_session_control_tx_timer(s); - birdloop_leave(p->loop); + birdloop_leave(p->p.loop); } static void bfd_close_session(struct bfd_proto *p, struct bfd_session *s) { - birdloop_enter(p->loop); + birdloop_enter(p->p.loop); s->opened = 0; bfd_session_update_state(s, BFD_STATE_DOWN, BFD_DIAG_PATH_DOWN); bfd_session_control_tx_timer(s); - birdloop_leave(p->loop); + birdloop_leave(p->p.loop); } */ static void -bfd_remove_session(struct bfd_proto *p, struct bfd_session *s) +bfd_remove_session_locked(struct bfd_proto *p, struct bfd_session *s) { - ip_addr ip = s->addr; - /* Caller should ensure that request list is empty */ - birdloop_enter(p->loop); - /* Remove session from notify list if scheduled for notification */ /* No need for bfd_lock_sessions(), we are already protected by birdloop_enter() */ if (NODE_VALID(&s->n)) @@ -508,11 +510,17 @@ bfd_remove_session(struct bfd_proto *p, struct bfd_session *s) HASH_REMOVE(p->session_hash_id, HASH_ID, s); HASH_REMOVE(p->session_hash_ip, HASH_IP, s); - sl_free(s); + TRACE(D_EVENTS, "Session to %I removed", s->addr); - TRACE(D_EVENTS, "Session to %I removed", ip); + sl_free(s); +} - birdloop_leave(p->loop); +static void +bfd_remove_session(struct bfd_proto *p, struct bfd_session *s) +{ + birdloop_enter(p->p.loop); + bfd_remove_session_locked(p, s); + birdloop_leave(p->p.loop); } static void @@ -521,7 +529,7 @@ bfd_reconfigure_session(struct bfd_proto *p, struct bfd_session *s) if (EMPTY_LIST(s->request_list)) return; - birdloop_enter(p->loop); + birdloop_enter(p->p.loop); struct bfd_request *req = SKIP_BACK(struct bfd_request, n, HEAD(s->request_list)); s->cf = bfd_merge_options(s->ifa->cf, &req->opts); @@ -534,7 +542,7 @@ bfd_reconfigure_session(struct bfd_proto *p, struct bfd_session *s) bfd_session_control_tx_timer(s, 0); - birdloop_leave(p->loop); + birdloop_leave(p->p.loop); TRACE(D_EVENTS, "Session to %I reconfigured", s->addr); } @@ -627,9 +635,9 @@ bfd_reconfigure_iface(struct bfd_proto *p, struct bfd_iface *ifa, struct bfd_con (new->passive != old->passive); /* This should be probably changed to not access ifa->cf from the BFD thread */ - birdloop_enter(p->loop); + birdloop_enter(p->p.loop); ifa->cf = new; - birdloop_leave(p->loop); + birdloop_leave(p->p.loop); } @@ -690,41 +698,68 @@ bfd_add_request(struct bfd_proto *p, struct bfd_request *req) } static void -bfd_submit_request(struct bfd_request *req) +bfd_pickup_requests(void *_data UNUSED) { node *n; + WALK_LIST(n, bfd_global.proto_list) + { + struct bfd_proto *p = SKIP_BACK(struct bfd_proto, bfd_node, n); + birdloop_enter(p->p.loop); + BFD_LOCK; - WALK_LIST(n, bfd_proto_list) - if (bfd_add_request(SKIP_BACK(struct bfd_proto, bfd_node, n), req)) - return; + node *rn, *rnxt; + WALK_LIST_DELSAFE(rn, rnxt, bfd_global.pickup_list) + bfd_add_request(p, SKIP_BACK(struct bfd_request, n, rn)); - rem_node(&req->n); - add_tail(&bfd_wait_list, &req->n); - req->session = NULL; - bfd_request_notify(req, BFD_STATE_ADMIN_DOWN, 0); + BFD_UNLOCK; + birdloop_leave(p->p.loop); + } + + BFD_LOCK; + node *rn, *rnxt; + WALK_LIST_DELSAFE(rn, rnxt, bfd_global.pickup_list) + { + rem_node(rn); + add_tail(&bfd_global.wait_list, rn); + bfd_request_notify(SKIP_BACK(struct bfd_request, n, rn), BFD_STATE_ADMIN_DOWN, 0); + } + BFD_UNLOCK; } +static event bfd_pickup_event = { .hook = bfd_pickup_requests }; + static void bfd_take_requests(struct bfd_proto *p) { node *n, *nn; - - WALK_LIST_DELSAFE(n, nn, bfd_wait_list) + BFD_LOCK; + WALK_LIST_DELSAFE(n, nn, bfd_global.wait_list) bfd_add_request(p, SKIP_BACK(struct bfd_request, n, n)); + BFD_UNLOCK; } static void bfd_drop_requests(struct bfd_proto *p) { node *n; - - HASH_WALK(p->session_hash_id, next_id, s) + BFD_LOCK; + HASH_WALK_DELSAFE(p->session_hash_id, next_id, s) { - /* We assume that p is not in bfd_proto_list */ WALK_LIST_FIRST(n, s->request_list) - bfd_submit_request(SKIP_BACK(struct bfd_request, n, n)); + { + struct bfd_request *req = SKIP_BACK(struct bfd_request, n, n); + rem_node(&req->n); + add_tail(&bfd_global.pickup_list, &req->n); + req->session = NULL; + bfd_request_notify(req, BFD_STATE_ADMIN_DOWN, 0); + } + + ev_send(&global_event_list, &bfd_pickup_event); + + bfd_remove_session_locked(p, s); } HASH_WALK_END; + BFD_UNLOCK; } static struct resclass bfd_request_class; @@ -737,9 +772,6 @@ bfd_request_session(pool *p, ip_addr addr, ip_addr local, { struct bfd_request *req = ralloc(p, &bfd_request_class); - /* Hack: self-link req->n, we will call rem_node() on it */ - req->n.prev = req->n.next = &req->n; - req->addr = addr; req->local = local; req->iface = iface; @@ -748,11 +780,16 @@ bfd_request_session(pool *p, ip_addr addr, ip_addr local, if (opts) req->opts = *opts; - bfd_submit_request(req); - req->hook = hook; req->data = data; + req->session = NULL; + + BFD_LOCK; + add_tail(&bfd_global.pickup_list, &req->n); + ev_send(&global_event_list, &bfd_pickup_event); + BFD_UNLOCK; + return req; } @@ -1023,10 +1060,10 @@ bfd_start(struct proto *P) struct bfd_proto *p = (struct bfd_proto *) P; struct bfd_config *cf = (struct bfd_config *) (P->cf); - p->loop = birdloop_new(); - p->tpool = rp_new(NULL, "BFD thread root"); pthread_spin_init(&p->lock, PTHREAD_PROCESS_PRIVATE); + p->tpool = rp_new(P->pool, "BFD loop pool"); + p->session_slab = sl_new(P->pool, sizeof(struct bfd_session)); HASH_INIT(p->session_hash_id, P->pool, 8); HASH_INIT(p->session_hash_ip, P->pool, 8); @@ -1036,9 +1073,7 @@ bfd_start(struct proto *P) init_list(&p->notify_list); bfd_notify_init(p); - add_tail(&bfd_proto_list, &p->bfd_node); - - birdloop_enter(p->loop); + add_tail(&bfd_global.proto_list, &p->bfd_node); if (!cf->strict_bind) { @@ -1055,42 +1090,33 @@ bfd_start(struct proto *P) p->rx6_m = bfd_open_rx_sk(p, 1, SK_IPV6); } - birdloop_leave(p->loop); - bfd_take_requests(p); struct bfd_neighbor *n; WALK_LIST(n, cf->neigh_list) bfd_start_neighbor(p, n); - birdloop_start(p->loop); - return PS_UP; } - static int bfd_shutdown(struct proto *P) { struct bfd_proto *p = (struct bfd_proto *) P; - struct bfd_config *cf = (struct bfd_config *) (P->cf); + struct bfd_config *cf = (struct bfd_config *) (p->p.cf); rem_node(&p->bfd_node); - birdloop_stop(p->loop); - - struct bfd_neighbor *n; - WALK_LIST(n, cf->neigh_list) - bfd_stop_neighbor(p, n); + struct bfd_neighbor *bn; + WALK_LIST(bn, cf->neigh_list) + bfd_stop_neighbor(p, bn); bfd_drop_requests(p); - /* FIXME: This is hack */ - birdloop_enter(p->loop); - rfree(p->tpool); - birdloop_leave(p->loop); - - birdloop_free(p->loop); + if (p->rx4_1) sk_stop(p->rx4_1); + if (p->rx4_m) sk_stop(p->rx4_m); + if (p->rx6_1) sk_stop(p->rx6_1); + if (p->rx6_m) sk_stop(p->rx6_m); return PS_DOWN; } @@ -1111,7 +1137,7 @@ bfd_reconfigure(struct proto *P, struct proto_config *c) (new->strict_bind != old->strict_bind)) return 0; - birdloop_mask_wakeups(p->loop); + birdloop_mask_wakeups(p->p.loop); WALK_LIST(ifa, p->iface_list) bfd_reconfigure_iface(p, ifa, new); @@ -1125,7 +1151,7 @@ bfd_reconfigure(struct proto *P, struct proto_config *c) bfd_reconfigure_neighbors(p, new); - birdloop_unmask_wakeups(p->loop); + birdloop_unmask_wakeups(p->p.loop); return 1; } @@ -1196,4 +1222,9 @@ void bfd_build(void) { proto_build(&proto_bfd); + + bfd_global.lock = DOMAIN_NEW(rtable, "BFD Global"); + init_list(&bfd_global.wait_list); + init_list(&bfd_global.pickup_list); + init_list(&bfd_global.proto_list); } diff --git a/proto/bfd/bfd.h b/proto/bfd/bfd.h index 60b7916c..b9afaf92 100644 --- a/proto/bfd/bfd.h +++ b/proto/bfd/bfd.h @@ -17,12 +17,12 @@ #include "nest/password.h" #include "conf/conf.h" #include "lib/hash.h" +#include "lib/io-loop.h" #include "lib/resource.h" #include "lib/socket.h" #include "lib/string.h" #include "nest/bfd.h" -#include "io.h" #define BFD_CONTROL_PORT 3784 @@ -88,9 +88,11 @@ struct bfd_neighbor struct bfd_proto { struct proto p; - struct birdloop *loop; - pool *tpool; + pthread_spinlock_t lock; + + pool *tpool; + node bfd_node; slab *session_slab; diff --git a/proto/bfd/config.Y b/proto/bfd/config.Y index 70461872..0d6e33fa 100644 --- a/proto/bfd/config.Y +++ b/proto/bfd/config.Y @@ -37,6 +37,7 @@ proto: bfd_proto ; bfd_proto_start: proto_start BFD { this_proto = proto_config_new(&proto_bfd, $1); + this_proto->loop_order = DOMAIN_ORDER(proto); init_list(&BFD_CFG->patt_list); init_list(&BFD_CFG->neigh_list); BFD_CFG->accept_ipv4 = BFD_CFG->accept_ipv6 = 1; diff --git a/proto/bfd/io.h b/proto/bfd/io.h deleted file mode 100644 index ec706e9a..00000000 --- a/proto/bfd/io.h +++ /dev/null @@ -1,34 +0,0 @@ -/* - * BIRD -- I/O and event loop - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#ifndef _BIRD_BFD_IO_H_ -#define _BIRD_BFD_IO_H_ - -#include "nest/bird.h" -#include "lib/lists.h" -#include "lib/resource.h" -#include "lib/event.h" -#include "lib/timer.h" -#include "lib/socket.h" - - -void ev2_schedule(event *e); - -void sk_start(sock *s); -void sk_stop(sock *s); - -struct birdloop *birdloop_new(void); -void birdloop_start(struct birdloop *loop); -void birdloop_stop(struct birdloop *loop); -void birdloop_free(struct birdloop *loop); - -void birdloop_enter(struct birdloop *loop); -void birdloop_leave(struct birdloop *loop); -void birdloop_mask_wakeups(struct birdloop *loop); -void birdloop_unmask_wakeups(struct birdloop *loop); - - -#endif /* _BIRD_BFD_IO_H_ */ diff --git a/proto/bfd/packets.c b/proto/bfd/packets.c index 5f10734c..6f0b4eaf 100644 --- a/proto/bfd/packets.c +++ b/proto/bfd/packets.c @@ -412,7 +412,7 @@ bfd_err_hook(sock *sk, int err) sock * bfd_open_rx_sk(struct bfd_proto *p, int multihop, int af) { - sock *sk = sk_new(p->tpool); + sock *sk = sk_new(p->p.pool); sk->type = SK_UDP; sk->subtype = af; sk->sport = !multihop ? BFD_CONTROL_PORT : BFD_MULTI_CTL_PORT; @@ -475,7 +475,7 @@ bfd_open_rx_sk_bound(struct bfd_proto *p, ip_addr local, struct iface *ifa) sock * bfd_open_tx_sk(struct bfd_proto *p, ip_addr local, struct iface *ifa) { - sock *sk = sk_new(p->tpool); + sock *sk = sk_new(p->p.pool); sk->type = SK_UDP; sk->saddr = local; sk->dport = ifa ? BFD_CONTROL_PORT : BFD_MULTI_CTL_PORT; diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c index 084c9b63..a7b1a7ed 100644 --- a/proto/bgp/attrs.c +++ b/proto/bgp/attrs.c @@ -1901,7 +1901,6 @@ bgp_out_table_export_start(struct rt_exporter *re, struct rt_export_request *req pool *p = rp_new(c->c.proto->pool, "Export hook"); struct rt_export_hook *hook = mb_allocz(p, sizeof(struct rt_export_hook)); hook->pool = p; - hook->lp = lp_new_default(p); hook->event = ev_new_init(p, bgp_out_table_feed, hook); hook->feed_type = TFT_HASH; @@ -1919,6 +1918,7 @@ bgp_setup_out_table(struct bgp_channel *c) }; init_list(&c->prefix_exporter.hooks); + init_list(&c->prefix_exporter.pending); c->c.out_table = &c->prefix_exporter; } @@ -1929,10 +1929,10 @@ bgp_setup_out_table(struct bgp_channel *c) */ int -bgp_preexport(struct channel *c, rte *e) +bgp_preexport(struct channel *C, rte *e) { struct proto *SRC = e->src->proto; - struct bgp_proto *p = (struct bgp_proto *) (c->proto); + struct bgp_proto *p = (struct bgp_proto *) C->proto; struct bgp_proto *src = (SRC->proto == &proto_bgp) ? (struct bgp_proto *) SRC : NULL; /* Reject our routes */ @@ -2546,27 +2546,57 @@ bgp_rte_recalculate(rtable *table, net *net, rte *new, rte *old, rte *old_best) return !old_suppressed; } -rte * -bgp_rte_modify_stale(struct rte *r, struct linpool *pool) +void +bgp_rte_modify_stale(struct rt_export_request *req, const net_addr *n, struct rt_pending_export *rpe UNUSED, rte **feed, uint count) { - eattr *ea = ea_find(r->attrs, BGP_EA_ID(BA_COMMUNITY)); - const struct adata *ad = ea ? ea->u.ptr : NULL; - uint flags = ea ? ea->flags : BAF_PARTIAL; + struct bgp_channel *c = SKIP_BACK(struct bgp_channel, stale_feed, req); + struct rt_import_hook *irh = c->c.in_req.hook; - if (ad && int_set_contains(ad, BGP_COMM_NO_LLGR)) - return NULL; + /* Find our routes among others */ + for (uint i=0; i<count; i++) + { + rte *r = feed[i]; + + if ( + !rte_is_valid(r) || /* Not a valid route */ + (r->sender != irh) || /* Not our route */ + (r->stale_cycle == irh->stale_set)) /* A new route, do not mark as stale */ + continue; + + eattr *ea = ea_find(r->attrs, BGP_EA_ID(BA_COMMUNITY)); + const struct adata *ad = ea ? ea->u.ptr : NULL; + uint flags = ea ? ea->flags : BAF_PARTIAL; - if (ad && int_set_contains(ad, BGP_COMM_LLGR_STALE)) - return r; + /* LLGR not allowed, withdraw the route */ + if (ad && int_set_contains(ad, BGP_COMM_NO_LLGR)) + { + rte_import(&c->c.in_req, n, NULL, r->src); + continue; + } + + /* Route already marked as LLGR, do nothing */ + if (ad && int_set_contains(ad, BGP_COMM_LLGR_STALE)) + continue; - _Thread_local static rte e0; - e0 = *r; + /* Store the tmp_linpool state to aggresively save memory */ + struct lp_state tmpp; + lp_save(tmp_linpool, &tmpp); - bgp_set_attr_ptr(&e0.attrs, BA_COMMUNITY, flags, - int_set_add(pool, ad, BGP_COMM_LLGR_STALE)); - e0.pflags |= BGP_REF_STALE; + /* Mark the route as LLGR */ + rte e0 = *r; + bgp_set_attr_ptr(&e0.attrs, BA_COMMUNITY, flags, int_set_add(tmp_linpool, ad, BGP_COMM_LLGR_STALE)); + e0.pflags &= ~BGP_REF_NOT_STALE; + e0.pflags |= BGP_REF_STALE; - return &e0; + /* We need to update the route but keep it stale. */ + ASSERT_DIE(irh->stale_set == irh->stale_valid + 1); + irh->stale_set--; + rte_import(&c->c.in_req, n, &e0, r->src); + irh->stale_set++; + + /* Restore the memory state */ + lp_restore(tmp_linpool, &tmpp); + } } diff --git a/proto/bgp/bgp.c b/proto/bgp/bgp.c index 6ffe8824..33849b0b 100644 --- a/proto/bgp/bgp.c +++ b/proto/bgp/bgp.c @@ -139,6 +139,9 @@ static void bgp_update_bfd(struct bgp_proto *p, const struct bfd_options *bfd); static int bgp_incoming_connection(sock *sk, uint dummy UNUSED); static void bgp_listen_sock_err(sock *sk UNUSED, int err); +static void bgp_graceful_restart_feed(struct bgp_channel *c); + + /** * bgp_open - open a BGP instance * @p: BGP instance @@ -373,6 +376,7 @@ bgp_close_conn(struct bgp_conn *conn) conn->keepalive_timer = NULL; rfree(conn->hold_timer); conn->hold_timer = NULL; + rfree(conn->tx_ev); conn->tx_ev = NULL; rfree(conn->sk); @@ -511,6 +515,7 @@ void bgp_stop(struct bgp_proto *p, int subcode, byte *data, uint len) { proto_notify_state(&p->p, PS_STOP); + p->uncork_ev->data = NULL; bgp_graceful_close_conn(&p->outgoing_conn, subcode, data, len); bgp_graceful_close_conn(&p->incoming_conn, subcode, data, len); ev_schedule(p->event); @@ -760,25 +765,25 @@ bgp_handle_graceful_restart(struct bgp_proto *p) { case BGP_GRS_NONE: c->gr_active = BGP_GRS_ACTIVE; - rt_refresh_begin(c->c.table, &c->c.in_req); + rt_refresh_begin(&c->c.in_req); break; case BGP_GRS_ACTIVE: - rt_refresh_end(c->c.table, &c->c.in_req); - rt_refresh_begin(c->c.table, &c->c.in_req); + rt_refresh_end(&c->c.in_req); + rt_refresh_begin(&c->c.in_req); break; case BGP_GRS_LLGR: - rt_refresh_begin(c->c.table, &c->c.in_req); - rt_modify_stale(c->c.table, &c->c.in_req); + rt_refresh_begin(&c->c.in_req); + bgp_graceful_restart_feed(c); break; } } else { /* Just flush the routes */ - rt_refresh_begin(c->c.table, &c->c.in_req); - rt_refresh_end(c->c.table, &c->c.in_req); + rt_refresh_begin(&c->c.in_req); + rt_refresh_end(&c->c.in_req); } /* Reset bucket and prefix tables */ @@ -796,6 +801,53 @@ bgp_handle_graceful_restart(struct bgp_proto *p) tm_start(p->gr_timer, p->conn->remote_caps->gr_time S); } +static void +bgp_graceful_restart_feed_done(struct rt_export_request *req) +{ + req->hook = NULL; +} + +static void +bgp_graceful_restart_feed_dump_req(struct rt_export_request *req) +{ + struct bgp_channel *c = SKIP_BACK(struct bgp_channel, stale_feed, req); + debug(" BGP-GR %s.%s export request %p\n", c->c.proto->name, c->c.name, req); +} + +static void +bgp_graceful_restart_feed_log_state_change(struct rt_export_request *req, u8 state) +{ + struct bgp_channel *c = SKIP_BACK(struct bgp_channel, stale_feed, req); + struct bgp_proto *p = (void *) c->c.proto; + BGP_TRACE(D_EVENTS, "Long-lived graceful restart export state changed to %s", rt_export_state_name(state)); + + if (state == TES_READY) + rt_stop_export(req, bgp_graceful_restart_feed_done); +} + +static void +bgp_graceful_restart_drop_export(struct rt_export_request *req UNUSED, const net_addr *n UNUSED, struct rt_pending_export *rpe UNUSED) +{ /* Nothing to do */ } + +static void +bgp_graceful_restart_feed(struct bgp_channel *c) +{ + c->stale_feed = (struct rt_export_request) { + .name = "BGP-GR", + .list = &global_work_list, + .trace_routes = c->c.debug | c->c.proto->debug, + .dump_req = bgp_graceful_restart_feed_dump_req, + .log_state_change = bgp_graceful_restart_feed_log_state_change, + .export_bulk = bgp_rte_modify_stale, + .export_one = bgp_graceful_restart_drop_export, + }; + + rt_request_export(&c->c.table->exporter, &c->stale_feed); +} + + + + /** * bgp_graceful_restart_done - finish active BGP graceful restart * @c: BGP channel @@ -819,7 +871,7 @@ bgp_graceful_restart_done(struct bgp_channel *c) BGP_TRACE(D_EVENTS, "Neighbor graceful restart done"); tm_stop(c->stale_timer); - rt_refresh_end(c->c.table, &c->c.in_req); + rt_refresh_end(&c->c.in_req); } /** @@ -861,7 +913,7 @@ bgp_graceful_restart_timeout(timer *t) /* Channel is in GR, and supports LLGR -> start LLGR */ c->gr_active = BGP_GRS_LLGR; tm_start(c->stale_timer, c->stale_time S); - rt_modify_stale(c->c.table, &c->c.in_req); + bgp_graceful_restart_feed(c); } } else @@ -899,7 +951,7 @@ bgp_refresh_begin(struct bgp_channel *c) { log(L_WARN "%s: BEGIN-OF-RR received before END-OF-RIB, ignoring", p->p.name); return; } c->load_state = BFS_REFRESHING; - rt_refresh_begin(c->c.table, &c->c.in_req); + rt_refresh_begin(&c->c.in_req); } /** @@ -920,7 +972,7 @@ bgp_refresh_end(struct bgp_channel *c) { log(L_WARN "%s: END-OF-RR received without prior BEGIN-OF-RR, ignoring", p->p.name); return; } c->load_state = BFS_NONE; - rt_refresh_end(c->c.table, &c->c.in_req); + rt_refresh_end(&c->c.in_req); } @@ -1526,6 +1578,8 @@ bgp_start(struct proto *P) p->last_rx_update = 0; p->event = ev_new_init(p->p.pool, bgp_decision, p); + p->uncork_ev = ev_new_init(p->p.pool, bgp_uncork, p); + p->startup_timer = tm_new_init(p->p.pool, bgp_startup_timeout, p, 0, 0); p->gr_timer = tm_new_init(p->p.pool, bgp_graceful_restart_timeout, p, 0, 0); @@ -1672,7 +1726,6 @@ bgp_init(struct proto_config *CF) P->rte_better = bgp_rte_better; P->rte_mergable = bgp_rte_mergable; P->rte_recalculate = cf->deterministic_med ? bgp_rte_recalculate : NULL; - P->rte_modify = bgp_rte_modify_stale; P->rte_igp_metric = bgp_rte_igp_metric; p->cf = cf; diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h index 003893e0..469f0cb9 100644 --- a/proto/bgp/bgp.h +++ b/proto/bgp/bgp.h @@ -319,6 +319,7 @@ struct bgp_proto { struct bgp_socket *sock; /* Shared listening socket */ struct bfd_request *bfd_req; /* BFD request, if BFD is used */ struct birdsock *postponed_sk; /* Postponed incoming socket for dynamic BGP */ + event *uncork_ev; /* Uncork event in case of congestion */ struct bgp_stats stats; /* BGP statistics */ btime last_established; /* Last time of enter/leave of established state */ btime last_rx_update; /* Last time of RX update */ @@ -371,6 +372,7 @@ struct bgp_channel { timer *stale_timer; /* Long-lived stale timer for LLGR */ u32 stale_time; /* Stored LLGR stale time from last session */ + struct rt_export_request stale_feed; /* Feeder request for stale route modification */ u8 add_path_rx; /* Session expects receive of ADD-PATH extended NLRI */ u8 add_path_tx; /* Session expects transmit of ADD-PATH extended NLRI */ @@ -576,7 +578,7 @@ void bgp_done_prefix(struct bgp_channel *c, struct bgp_prefix *px, struct bgp_bu int bgp_rte_better(struct rte *, struct rte *); int bgp_rte_mergable(rte *pri, rte *sec); int bgp_rte_recalculate(rtable *table, net *net, rte *new, rte *old, rte *old_best); -struct rte *bgp_rte_modify_stale(struct rte *r, struct linpool *pool); +void bgp_rte_modify_stale(struct rt_export_request *req, const net_addr *n, struct rt_pending_export *rpe UNUSED, rte **feed, uint count); u32 bgp_rte_igp_metric(const rte *); void bgp_rt_notify(struct proto *P, struct channel *C, const net_addr *n, rte *new, const rte *old); int bgp_preexport(struct channel *, struct rte *); @@ -609,6 +611,7 @@ void bgp_schedule_packet(struct bgp_conn *conn, struct bgp_channel *c, int type) void bgp_kick_tx(void *vconn); void bgp_tx(struct birdsock *sk); int bgp_rx(struct birdsock *sk, uint size); +void bgp_uncork(void *vp); const char * bgp_error_dsc(unsigned code, unsigned subcode); void bgp_log_error(struct bgp_proto *p, u8 class, char *msg, unsigned code, unsigned subcode, byte *data, unsigned len); diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c index 4d4ae3eb..de976588 100644 --- a/proto/bgp/packets.c +++ b/proto/bgp/packets.c @@ -3175,6 +3175,21 @@ bgp_rx_packet(struct bgp_conn *conn, byte *pkt, uint len) } } +void +bgp_uncork(void *vp) +{ + struct bgp_proto *p = vp; + + if (p && p->conn && (p->conn->state == BS_ESTABLISHED) && !p->conn->sk->rx_hook) + { + struct birdsock *sk = p->conn->sk; + ASSERT_DIE(sk->rpos > sk->rbuf); + sk->rx_hook = bgp_rx; + bgp_rx(sk, sk->rpos - sk->rbuf); + BGP_TRACE(D_PACKETS, "Uncorked"); + } +} + /** * bgp_rx - handle received data * @sk: socket @@ -3189,6 +3204,7 @@ int bgp_rx(sock *sk, uint size) { struct bgp_conn *conn = sk->data; + struct bgp_proto *p = conn->bgp; byte *pkt_start = sk->rbuf; byte *end = pkt_start + size; uint i, len; @@ -3198,6 +3214,12 @@ bgp_rx(sock *sk, uint size) { if ((conn->state == BS_CLOSE) || (conn->sk != sk)) return 0; + if ((conn->state == BS_ESTABLISHED) && rt_cork_check(conn->bgp->uncork_ev)) + { + sk->rx_hook = NULL; + BGP_TRACE(D_PACKETS, "Corked"); + return 0; + } for(i=0; i<16; i++) if (pkt_start[i] != 0xff) { diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c index 6a4ee8ab..9c25f0f0 100644 --- a/proto/ospf/ospf.c +++ b/proto/ospf/ospf.c @@ -486,13 +486,13 @@ ospf_disp(timer * timer) * import to the filters. */ static int -ospf_preexport(struct channel *c, rte *e) +ospf_preexport(struct channel *C, rte *e) { - struct ospf_proto *p = (struct ospf_proto *) c->proto; + struct ospf_proto *p = (struct ospf_proto *) C->proto; struct ospf_area *oa = ospf_main_area(p); /* Reject our own routes */ - if (e->src->proto == c->proto) + if (e->src->proto == &p->p) return -1; /* Do not export routes to stub areas */ diff --git a/proto/pipe/pipe.c b/proto/pipe/pipe.c index 351db36b..8af6de81 100644 --- a/proto/pipe/pipe.c +++ b/proto/pipe/pipe.c @@ -73,12 +73,12 @@ pipe_rt_notify(struct proto *P, struct channel *src_ch, const net_addr *n, rte * } static int -pipe_preexport(struct channel *c, rte *e) +pipe_preexport(struct channel *C, rte *e) { - struct pipe_proto *p = (void *) c->proto; + struct pipe_proto *p = (void *) C->proto; /* Avoid direct loopbacks */ - if (e->sender == c->in_req.hook) + if (e->sender == C->in_req.hook) return -1; /* Indirection check */ @@ -86,8 +86,8 @@ pipe_preexport(struct channel *c, rte *e) if (e->generation >= max_generation) { log_rl(&p->rl_gen, L_ERR "Route overpiped (%u hops of %u configured in %s) in table %s: %N %s/%u:%u", - e->generation, max_generation, c->proto->name, - c->table->name, e->net, e->src->proto->name, e->src->private_id, e->src->global_id); + e->generation, max_generation, C->proto->name, + C->table->name, e->net, e->src->proto->name, e->src->private_id, e->src->global_id); return -1; } diff --git a/proto/radv/radv.c b/proto/radv/radv.c index 3a159462..10d5e3ed 100644 --- a/proto/radv/radv.c +++ b/proto/radv/radv.c @@ -394,10 +394,10 @@ radv_net_match_trigger(struct radv_config *cf, const net_addr *n) } int -radv_preexport(struct channel *c, rte *new) +radv_preexport(struct channel *C, rte *new) { // struct radv_proto *p = (struct radv_proto *) P; - struct radv_config *cf = (struct radv_config *) (c->proto->cf); + struct radv_config *cf = (struct radv_config *) (C->proto->cf); if (radv_net_match_trigger(cf, new->net)) return RIC_PROCESS; diff --git a/proto/rpki/packets.c b/proto/rpki/packets.c index 4a52b54b..108da61b 100644 --- a/proto/rpki/packets.c +++ b/proto/rpki/packets.c @@ -661,9 +661,9 @@ rpki_handle_cache_response_pdu(struct rpki_cache *cache, const struct pdu_cache_ * a refresh cycle. */ if (cache->p->roa4_channel) - rt_refresh_begin(cache->p->roa4_channel->table, &cache->p->roa4_channel->in_req); + rt_refresh_begin(&cache->p->roa4_channel->in_req); if (cache->p->roa6_channel) - rt_refresh_begin(cache->p->roa6_channel->table, &cache->p->roa6_channel->in_req); + rt_refresh_begin(&cache->p->roa6_channel->in_req); cache->p->refresh_channels = 1; } @@ -846,9 +846,9 @@ rpki_handle_end_of_data_pdu(struct rpki_cache *cache, const struct pdu_end_of_da { cache->p->refresh_channels = 0; if (cache->p->roa4_channel) - rt_refresh_end(cache->p->roa4_channel->table, &cache->p->roa4_channel->in_req); + rt_refresh_end(&cache->p->roa4_channel->in_req); if (cache->p->roa6_channel) - rt_refresh_end(cache->p->roa6_channel->table, &cache->p->roa6_channel->in_req); + rt_refresh_end(&cache->p->roa6_channel->in_req); } cache->last_update = current_time(); 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 diff --git a/sysdep/config.h b/sysdep/config.h index b0531844..5cdadbb0 100644 --- a/sysdep/config.h +++ b/sysdep/config.h @@ -13,7 +13,7 @@ #ifdef GIT_LABEL #define BIRD_VERSION XSTR1(GIT_LABEL) #else -#define BIRD_VERSION "2.0.9" +#define BIRD_VERSION "2.0.10" #endif /* Include parameters determined by configure script */ diff --git a/sysdep/unix/Makefile b/sysdep/unix/Makefile index 51ab98a9..3f1a8b3a 100644 --- a/sysdep/unix/Makefile +++ b/sysdep/unix/Makefile @@ -1,4 +1,4 @@ -src := alloc.c io.c krt.c log.c main.c random.c +src := alloc.c io.c io-loop.c krt.c log.c main.c random.c domain.c obj := $(src-o-files) $(all-daemon) $(cf-local) diff --git a/sysdep/unix/alloc.c b/sysdep/unix/alloc.c index edad6209..a2384ca8 100644 --- a/sysdep/unix/alloc.c +++ b/sysdep/unix/alloc.c @@ -97,7 +97,7 @@ alloc_page(void) struct free_page *fp = SKIP_BACK(struct free_page, n, HEAD(fps->pages)); rem_node(&fp->n); if ((--fps->cnt < fps->min) && !shutting_down) - ev_schedule(&fps->cleanup); + ev_send(&global_work_list, &fps->cleanup); bzero(fp, page_size); return fp; @@ -124,7 +124,7 @@ free_page(void *ptr) add_tail(&fps->pages, &fp->n); if ((++fps->cnt > fps->max) && !shutting_down) - ev_schedule(&fps->cleanup); + ev_send(&global_work_list, &fps->cleanup); #endif } diff --git a/sysdep/unix/domain.c b/sysdep/unix/domain.c new file mode 100644 index 00000000..0a5858a6 --- /dev/null +++ b/sysdep/unix/domain.c @@ -0,0 +1,116 @@ +/* + * BIRD Locking + * + * (c) 2020 Maria Matejka <mq@jmq.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _GNU_SOURCE +#define _GNU_SOURCE +#endif + +#undef LOCAL_DEBUG + +#undef DEBUG_LOCKING + +#include "lib/birdlib.h" +#include "lib/locking.h" +#include "lib/resource.h" +#include "lib/timer.h" + +#include "conf/conf.h" + +#include <errno.h> +#include <fcntl.h> +#include <poll.h> +#include <pthread.h> +#include <semaphore.h> +#include <stdatomic.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +/* + * Locking subsystem + */ + +_Thread_local struct lock_order locking_stack = {}; +_Thread_local struct domain_generic **last_locked = NULL; + +#define ASSERT_NO_LOCK ASSERT_DIE(last_locked == NULL) + +struct domain_generic { + pthread_mutex_t mutex; + uint order; + struct domain_generic **prev; + struct lock_order *locked_by; + const char *name; +}; + +#define DOMAIN_INIT(_name, _order) { .mutex = PTHREAD_MUTEX_INITIALIZER, .name = _name, .order = _order } + +static struct domain_generic the_bird_domain_gen = DOMAIN_INIT("The BIRD", OFFSETOF(struct lock_order, the_bird)); + +DOMAIN(the_bird) the_bird_domain = { .the_bird = &the_bird_domain_gen }; + +struct domain_generic * +domain_new(const char *name, uint order) +{ + ASSERT_DIE(order < sizeof(struct lock_order)); + struct domain_generic *dg = xmalloc(sizeof(struct domain_generic)); + *dg = (struct domain_generic) DOMAIN_INIT(name, order); + return dg; +} + +void +domain_free(struct domain_generic *dg) +{ + pthread_mutex_destroy(&dg->mutex); + xfree(dg); +} + +uint dg_order(struct domain_generic *dg) +{ + return dg->order; +} + +void do_lock(struct domain_generic *dg, struct domain_generic **lsp) +{ + if ((char *) lsp - (char *) &locking_stack != dg->order) + bug("Trying to lock on bad position: order=%u, lsp=%p, base=%p", dg->order, lsp, &locking_stack); + + if (lsp <= last_locked) + bug("Trying to lock in a bad order"); + if (*lsp) + bug("Inconsistent locking stack state on lock"); + + btime lock_begin = current_time(); + pthread_mutex_lock(&dg->mutex); + btime duration = current_time() - lock_begin; + if (config && (duration > config->watchdog_warning)) + log(L_WARN "Locking of %s took %d ms", dg->name, (int) (duration TO_MS)); + + if (dg->prev || dg->locked_by) + bug("Previous unlock not finished correctly"); + dg->prev = last_locked; + *lsp = dg; + last_locked = lsp; + dg->locked_by = &locking_stack; +} + +void do_unlock(struct domain_generic *dg, struct domain_generic **lsp) +{ + if ((char *) lsp - (char *) &locking_stack != dg->order) + bug("Trying to unlock on bad position: order=%u, lsp=%p, base=%p", dg->order, lsp, &locking_stack); + + if (dg->locked_by != &locking_stack) + bug("Inconsistent domain state on unlock"); + if ((last_locked != lsp) || (*lsp != dg)) + bug("Inconsistent locking stack state on unlock"); + dg->locked_by = NULL; + last_locked = dg->prev; + *lsp = NULL; + dg->prev = NULL; + pthread_mutex_unlock(&dg->mutex); +} diff --git a/proto/bfd/io.c b/sysdep/unix/io-loop.c index e696cc89..3e3fc31a 100644 --- a/proto/bfd/io.c +++ b/sysdep/unix/io-loop.c @@ -15,7 +15,6 @@ #include <sys/time.h> #include "nest/bird.h" -#include "proto/bfd/io.h" #include "lib/buffer.h" #include "lib/lists.h" @@ -24,56 +23,41 @@ #include "lib/timer.h" #include "lib/socket.h" +#include "lib/io-loop.h" +#include "sysdep/unix/io-loop.h" +#include "conf/conf.h" -struct birdloop -{ - pool *pool; - pthread_t thread; - pthread_mutex_t mutex; - - u8 stop_called; - u8 poll_active; - u8 wakeup_masked; - int wakeup_fds[2]; - - struct timeloop time; - list event_list; - list sock_list; - uint sock_num; - - BUFFER(sock *) poll_sk; - BUFFER(struct pollfd) poll_fd; - u8 poll_changed; - u8 close_scheduled; -}; - +#define THREAD_STACK_SIZE 65536 /* To be lowered in near future */ /* * Current thread context */ -static pthread_key_t current_loop_key; -extern pthread_key_t current_time_key; +_Thread_local struct birdloop *birdloop_current; +static _Thread_local struct birdloop *birdloop_wakeup_masked; +static _Thread_local uint birdloop_wakeup_masked_count; -static inline struct birdloop * -birdloop_current(void) +event_list * +birdloop_event_list(struct birdloop *loop) { - return pthread_getspecific(current_loop_key); + return &loop->event_list; } -static inline void -birdloop_set_current(struct birdloop *loop) +struct timeloop * +birdloop_time_loop(struct birdloop *loop) { - pthread_setspecific(current_loop_key, loop); - pthread_setspecific(current_time_key, loop ? &loop->time : &main_timeloop); + return &loop->time; } -static inline void -birdloop_init_current(void) +_Bool +birdloop_inside(struct birdloop *loop) { - pthread_key_create(¤t_loop_key, NULL); -} + for (struct birdloop *c = birdloop_current; c; c = c->prev_loop) + if (loop == c) + return 1; + return 0; +} /* * Wakeup code for birdloop @@ -150,60 +134,24 @@ wakeup_do_kick(struct birdloop *loop) } static inline void -wakeup_kick(struct birdloop *loop) -{ - if (!loop->wakeup_masked) - wakeup_do_kick(loop); - else - loop->wakeup_masked = 2; -} - -/* For notifications from outside */ -void -wakeup_kick_current(void) +birdloop_do_ping(struct birdloop *loop) { - struct birdloop *loop = birdloop_current(); + if (atomic_fetch_add_explicit(&loop->ping_sent, 1, memory_order_acq_rel)) + return; - if (loop && loop->poll_active) - wakeup_kick(loop); -} - - -/* - * Events - */ - -static inline uint -events_waiting(struct birdloop *loop) -{ - return !EMPTY_LIST(loop->event_list); -} - -static inline void -events_init(struct birdloop *loop) -{ - init_list(&loop->event_list); -} - -static void -events_fire(struct birdloop *loop) -{ - times_update(&loop->time); - ev_run_list(&loop->event_list); + if (loop == birdloop_wakeup_masked) + birdloop_wakeup_masked_count++; + else + wakeup_do_kick(loop); } void -ev2_schedule(event *e) +birdloop_ping(struct birdloop *loop) { - struct birdloop *loop = birdloop_current(); - - if (loop->poll_active && EMPTY_LIST(loop->event_list)) - wakeup_kick(loop); - - if (e->n.next) - rem_node(&e->n); - - add_tail(&loop->event_list, &e->n); + if (birdloop_inside(loop) && !loop->ping_pending) + loop->ping_pending++; + else + birdloop_do_ping(loop); } @@ -231,16 +179,14 @@ sockets_add(struct birdloop *loop, sock *s) s->index = -1; loop->poll_changed = 1; - if (loop->poll_active) - wakeup_kick(loop); + birdloop_ping(loop); } void sk_start(sock *s) { - struct birdloop *loop = birdloop_current(); - - sockets_add(loop, s); + ASSERT_DIE(birdloop_current != &main_birdloop); + sockets_add(birdloop_current, s); } static void @@ -250,30 +196,21 @@ sockets_remove(struct birdloop *loop, sock *s) loop->sock_num--; if (s->index >= 0) - loop->poll_sk.data[s->index] = NULL; - - s->index = -1; - loop->poll_changed = 1; - - /* Wakeup moved to sk_stop() */ -} - -void -sk_stop(sock *s) -{ - struct birdloop *loop = birdloop_current(); - - sockets_remove(loop, s); - - if (loop->poll_active) { + loop->poll_sk.data[s->index] = NULL; + s->index = -1; + loop->poll_changed = 1; loop->close_scheduled = 1; - wakeup_kick(loop); + birdloop_ping(loop); } else close(s->fd); +} - s->fd = -1; +void +sk_stop(sock *s) +{ + sockets_remove(birdloop_current, s); } static inline uint sk_want_events(sock *s) @@ -354,7 +291,7 @@ sockets_fire(struct birdloop *loop) sock **psk = loop->poll_sk.data; int poll_num = loop->poll_fd.used - 1; - times_update(&loop->time); + times_update(); /* Last fd is internal wakeup fd */ if (pfd[poll_num].revents & POLLIN) @@ -373,12 +310,15 @@ sockets_fire(struct birdloop *loop) if (pfd->revents & POLLIN) while (e && *psk && (*psk)->rx_hook) - e = sk_read(*psk, 0); + e = sk_read(*psk, pfd->revents); e = 1; if (pfd->revents & POLLOUT) + { + loop->poll_changed = 1; while (e && *psk) e = sk_write(*psk); + } } } @@ -387,90 +327,176 @@ sockets_fire(struct birdloop *loop) * Birdloop */ -static void * birdloop_main(void *arg); +struct birdloop main_birdloop; + +static void birdloop_enter_locked(struct birdloop *loop); + +void +birdloop_init(void) +{ + wakeup_init(&main_birdloop); + + main_birdloop.time.domain = the_bird_domain.the_bird; + main_birdloop.time.loop = &main_birdloop; + + times_update(); + timers_init(&main_birdloop.time, &root_pool); + + birdloop_enter_locked(&main_birdloop); +} + +static void *birdloop_main(void *arg); struct birdloop * -birdloop_new(void) +birdloop_new(pool *pp, uint order, const char *name) { - /* FIXME: this init should be elsewhere and thread-safe */ - static int init = 0; - if (!init) - { birdloop_init_current(); init = 1; } + struct domain_generic *dg = domain_new(name, order); - pool *p = rp_new(NULL, "Birdloop root"); + pool *p = rp_new(pp, name); struct birdloop *loop = mb_allocz(p, sizeof(struct birdloop)); loop->pool = p; - pthread_mutex_init(&loop->mutex, NULL); - wakeup_init(loop); + loop->time.domain = dg; + loop->time.loop = loop; + + birdloop_enter(loop); - events_init(loop); + wakeup_init(loop); + ev_init_list(&loop->event_list, loop, name); timers_init(&loop->time, p); sockets_init(loop); + int e = 0; + + if (e = pthread_attr_init(&loop->thread_attr)) + die("pthread_attr_init() failed: %M", e); + + if (e = pthread_attr_setstacksize(&loop->thread_attr, THREAD_STACK_SIZE)) + die("pthread_attr_setstacksize(%u) failed: %M", THREAD_STACK_SIZE, e); + + if (e = pthread_attr_setdetachstate(&loop->thread_attr, PTHREAD_CREATE_DETACHED)) + die("pthread_attr_setdetachstate(PTHREAD_CREATE_DETACHED) failed: %M", e); + + if (e = pthread_create(&loop->thread_id, &loop->thread_attr, birdloop_main, loop)) + die("pthread_create() failed: %M", e); + + birdloop_leave(loop); + return loop; } +static void +birdloop_do_stop(struct birdloop *loop, void (*stopped)(void *data), void *data) +{ + loop->stopped = stopped; + loop->stop_data = data; + wakeup_do_kick(loop); +} + void -birdloop_start(struct birdloop *loop) +birdloop_stop(struct birdloop *loop, void (*stopped)(void *data), void *data) { - int rv = pthread_create(&loop->thread, NULL, birdloop_main, loop); - if (rv) - die("pthread_create(): %M", rv); + DG_LOCK(loop->time.domain); + birdloop_do_stop(loop, stopped, data); + DG_UNLOCK(loop->time.domain); } void -birdloop_stop(struct birdloop *loop) +birdloop_stop_self(struct birdloop *loop, void (*stopped)(void *data), void *data) { - pthread_mutex_lock(&loop->mutex); - loop->stop_called = 1; - wakeup_do_kick(loop); - pthread_mutex_unlock(&loop->mutex); + ASSERT_DIE(loop == birdloop_current); + ASSERT_DIE(DG_IS_LOCKED(loop->time.domain)); - int rv = pthread_join(loop->thread, NULL); - if (rv) - die("pthread_join(): %M", rv); + birdloop_do_stop(loop, stopped, data); } void birdloop_free(struct birdloop *loop) { + ASSERT_DIE(loop->links == 0); + ASSERT_DIE(pthread_equal(pthread_self(), loop->thread_id)); + + rcu_birdloop_stop(&loop->rcu); + pthread_attr_destroy(&loop->thread_attr); + + domain_free(loop->time.domain); rfree(loop->pool); } +static void +birdloop_enter_locked(struct birdloop *loop) +{ + ASSERT_DIE(DG_IS_LOCKED(loop->time.domain)); + ASSERT_DIE(!birdloop_inside(loop)); + + /* Store the old context */ + loop->prev_loop = birdloop_current; + + /* Put the new context */ + birdloop_current = loop; +} void birdloop_enter(struct birdloop *loop) { - /* TODO: these functions could save and restore old context */ - pthread_mutex_lock(&loop->mutex); - birdloop_set_current(loop); + DG_LOCK(loop->time.domain); + return birdloop_enter_locked(loop); +} + +static void +birdloop_leave_locked(struct birdloop *loop) +{ + /* Check the current context */ + ASSERT_DIE(birdloop_current == loop); + + /* Send pending pings */ + if (loop->ping_pending) + { + loop->ping_pending = 0; + birdloop_do_ping(loop); + } + + /* Restore the old context */ + birdloop_current = loop->prev_loop; } void birdloop_leave(struct birdloop *loop) { - /* TODO: these functions could save and restore old context */ - birdloop_set_current(NULL); - pthread_mutex_unlock(&loop->mutex); + birdloop_leave_locked(loop); + DG_UNLOCK(loop->time.domain); } void birdloop_mask_wakeups(struct birdloop *loop) { - pthread_mutex_lock(&loop->mutex); - loop->wakeup_masked = 1; - pthread_mutex_unlock(&loop->mutex); + ASSERT_DIE(birdloop_wakeup_masked == NULL); + birdloop_wakeup_masked = loop; } void birdloop_unmask_wakeups(struct birdloop *loop) { - pthread_mutex_lock(&loop->mutex); - if (loop->wakeup_masked == 2) + ASSERT_DIE(birdloop_wakeup_masked == loop); + birdloop_wakeup_masked = NULL; + if (birdloop_wakeup_masked_count) wakeup_do_kick(loop); - loop->wakeup_masked = 0; - pthread_mutex_unlock(&loop->mutex); + + birdloop_wakeup_masked_count = 0; +} + +void +birdloop_link(struct birdloop *loop) +{ + ASSERT_DIE(birdloop_inside(loop)); + loop->links++; +} + +void +birdloop_unlink(struct birdloop *loop) +{ + ASSERT_DIE(birdloop_inside(loop)); + loop->links--; } static void * @@ -480,18 +506,17 @@ birdloop_main(void *arg) timer *t; int rv, timeout; - birdloop_set_current(loop); + rcu_birdloop_start(&loop->rcu); + + btime loop_begin = current_time(); tmp_init(loop->pool); - pthread_mutex_lock(&loop->mutex); + birdloop_enter(loop); while (1) { - events_fire(loop); - timers_fire(&loop->time); - - times_update(&loop->time); - if (events_waiting(loop)) + timers_fire(&loop->time, 0); + if (ev_run_list(&loop->event_list)) timeout = 0; else if (t = timers_first(&loop->time)) timeout = (tm_remains(t) TO_MS) + 1; @@ -501,8 +526,11 @@ birdloop_main(void *arg) if (loop->poll_changed) sockets_prepare(loop); - loop->poll_active = 1; - pthread_mutex_unlock(&loop->mutex); + btime duration = current_time() - loop_begin; + if (duration > config->watchdog_warning) + log(L_WARN "I/O loop cycle took %d ms", (int) (duration TO_MS)); + + birdloop_leave(loop); try: rv = poll(loop->poll_fd.data, loop->poll_fd.used, timeout); @@ -513,25 +541,38 @@ birdloop_main(void *arg) die("poll: %m"); } - pthread_mutex_lock(&loop->mutex); - loop->poll_active = 0; + birdloop_enter(loop); if (loop->close_scheduled) sockets_close_fds(loop); - if (loop->stop_called) + if (loop->stopped) break; + loop_begin = current_time(); + if (rv) sockets_fire(loop); - timers_fire(&loop->time); + atomic_exchange_explicit(&loop->ping_sent, 0, memory_order_acq_rel); } - loop->stop_called = 0; - pthread_mutex_unlock(&loop->mutex); + /* Flush remaining events */ + ASSERT_DIE(!ev_run_list(&loop->event_list)); + + /* No timers allowed */ + ASSERT_DIE(timers_count(&loop->time) == 0); + ASSERT_DIE(EMPTY_LIST(loop->sock_list)); + ASSERT_DIE(loop->sock_num == 0); + + birdloop_leave(loop); + loop->stopped(loop->stop_data); return NULL; } - +void +birdloop_yield(void) +{ + usleep(100); +} diff --git a/sysdep/unix/io-loop.h b/sysdep/unix/io-loop.h new file mode 100644 index 00000000..31c40459 --- /dev/null +++ b/sysdep/unix/io-loop.h @@ -0,0 +1,43 @@ +/* + * BIRD -- I/O and event loop + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_SYSDEP_UNIX_IO_LOOP_H_ +#define _BIRD_SYSDEP_UNIX_IO_LOOP_H_ + +#include "lib/rcu.h" + +struct birdloop +{ + pool *pool; + + struct timeloop time; + event_list event_list; + list sock_list; + uint sock_num; + + BUFFER(sock *) poll_sk; + BUFFER(struct pollfd) poll_fd; + u8 poll_changed; + u8 close_scheduled; + + uint ping_pending; + _Atomic u32 ping_sent; + int wakeup_fds[2]; + + pthread_t thread_id; + pthread_attr_t thread_attr; + + struct rcu_birdloop rcu; + + uint links; + + void (*stopped)(void *data); + void *stop_data; + + struct birdloop *prev_loop; +}; + +#endif diff --git a/sysdep/unix/io.c b/sysdep/unix/io.c index 8a116789..23baffb2 100644 --- a/sysdep/unix/io.c +++ b/sysdep/unix/io.c @@ -36,12 +36,14 @@ #include "lib/resource.h" #include "lib/socket.h" #include "lib/event.h" +#include "lib/locking.h" #include "lib/timer.h" #include "lib/string.h" #include "nest/iface.h" #include "conf/conf.h" #include "sysdep/unix/unix.h" +#include "sysdep/unix/io-loop.h" #include CONFIG_INCLUDE_SYSIO_H /* Maximum number of calls of tx handler for one socket in one @@ -122,55 +124,50 @@ rf_fileno(struct rfile *f) btime boot_time; + void -times_init(struct timeloop *loop) +times_update(void) { struct timespec ts; int rv; + btime old_time = current_time(); + btime old_real_time = current_real_time(); + rv = clock_gettime(CLOCK_MONOTONIC, &ts); if (rv < 0) die("Monotonic clock is missing"); if ((ts.tv_sec < 0) || (((u64) ts.tv_sec) > ((u64) 1 << 40))) log(L_WARN "Monotonic clock is crazy"); - - loop->last_time = ts.tv_sec S + ts.tv_nsec NS; - loop->real_time = 0; -} - -void -times_update(struct timeloop *loop) -{ - struct timespec ts; - int rv; - - rv = clock_gettime(CLOCK_MONOTONIC, &ts); - if (rv < 0) - die("clock_gettime: %m"); - + btime new_time = ts.tv_sec S + ts.tv_nsec NS; - if (new_time < loop->last_time) + if (new_time < old_time) log(L_ERR "Monotonic clock is broken"); - loop->last_time = new_time; - loop->real_time = 0; -} - -void -times_update_real_time(struct timeloop *loop) -{ - struct timespec ts; - int rv; - rv = clock_gettime(CLOCK_REALTIME, &ts); if (rv < 0) die("clock_gettime: %m"); - loop->real_time = ts.tv_sec S + ts.tv_nsec NS; -} + btime new_real_time = ts.tv_sec S + ts.tv_nsec NS; + if (!atomic_compare_exchange_strong_explicit( + &last_time, + &old_time, + new_time, + memory_order_acq_rel, + memory_order_relaxed)) + DBG("Time update collision: last_time"); + + if (!atomic_compare_exchange_strong_explicit( + &real_time, + &old_real_time, + new_real_time, + memory_order_acq_rel, + memory_order_relaxed)) + DBG("Time update collision: real_time"); +} /** * DOC: Sockets @@ -804,18 +801,16 @@ sk_free(resource *r) sk_ssh_free(s); #endif - if (s->fd < 0) + if ((s->fd < 0) || (s->flags & SKF_THREAD)) return; - /* FIXME: we should call sk_stop() for SKF_THREAD sockets */ - if (!(s->flags & SKF_THREAD)) - { - if (s == current_sock) - current_sock = sk_next(s); - if (s == stored_sock) - stored_sock = sk_next(s); + if (s == current_sock) + current_sock = sk_next(s); + if (s == stored_sock) + stored_sock = sk_next(s); + + if (enlisted(&s->n)) rem_node(&s->n); - } if (s->type != SK_SSH && s->type != SK_SSH_ACTIVE) close(s->fd); @@ -1108,7 +1103,11 @@ sk_passive_connected(sock *s, int type) return 1; } - sk_insert(t); + if (s->flags & SKF_PASSIVE_THREAD) + t->flags |= SKF_THREAD; + else + sk_insert(t); + sk_alloc_bufs(t); s->rx_hook(t, 0); return 1; @@ -1516,6 +1515,36 @@ sk_open_unix(sock *s, char *name) return 0; } +static void +sk_reloop_hook(void *_vs) +{ + sock *s = _vs; + if (birdloop_inside(&main_birdloop)) + { + s->flags &= ~SKF_THREAD; + sk_insert(s); + } + else + { + s->flags |= SKF_THREAD; + sk_start(s); + } +} + +void +sk_reloop(sock *s, struct birdloop *loop) +{ + if (enlisted(&s->n)) + rem_node(&s->n); + + s->reloop = (event) { + .hook = sk_reloop_hook, + .data = s, + }; + + ev_send_loop(loop, &s->reloop); +} + #define CMSG_RX_SPACE MAX(CMSG4_SPACE_PKTINFO+CMSG4_SPACE_TTL, \ CMSG6_SPACE_PKTINFO+CMSG6_SPACE_TTL) @@ -2037,34 +2066,21 @@ struct event_log_entry static struct event_log_entry event_log[EVENT_LOG_LENGTH]; static struct event_log_entry *event_open; static int event_log_pos, event_log_num, watchdog_active; -static btime last_time; +static btime last_io_time; static btime loop_time; static void io_update_time(void) { - struct timespec ts; - int rv; - - /* - * This is third time-tracking procedure (after update_times() above and - * times_update() in BFD), dedicated to internal event log and latency - * tracking. Hopefully, we consolidate these sometimes. - */ - - rv = clock_gettime(CLOCK_MONOTONIC, &ts); - if (rv < 0) - die("clock_gettime: %m"); - - last_time = ts.tv_sec S + ts.tv_nsec NS; + last_io_time = current_time(); if (event_open) { - event_open->duration = last_time - event_open->timestamp; + event_open->duration = last_io_time - event_open->timestamp; if (event_open->duration > config->latency_limit) - log(L_WARN "Event 0x%p 0x%p took %d ms", - event_open->hook, event_open->data, (int) (event_open->duration TO_MS)); + log(L_WARN "Event 0x%p 0x%p took %u.%03u ms", + event_open->hook, event_open->data, (uint) (event_open->duration TO_MS), (uint) (event_open->duration % 1000)); event_open = NULL; } @@ -2089,7 +2105,7 @@ io_log_event(void *hook, void *data) en->hook = hook; en->data = data; - en->timestamp = last_time; + en->timestamp = last_io_time; en->duration = 0; event_log_num++; @@ -2117,14 +2133,14 @@ io_log_dump(void) struct event_log_entry *en = event_log + (event_log_pos + i) % EVENT_LOG_LENGTH; if (en->hook) log(L_DEBUG " Event 0x%p 0x%p at %8d for %d ms", en->hook, en->data, - (int) ((last_time - en->timestamp) TO_MS), (int) (en->duration TO_MS)); + (int) ((last_io_time - en->timestamp) TO_MS), (int) (en->duration TO_MS)); } } void watchdog_sigalrm(int sig UNUSED) { - /* Update last_time and duration, but skip latency check */ + /* Update last_io_time and duration, but skip latency check */ config->latency_limit = 0xffffffff; io_update_time(); @@ -2137,7 +2153,7 @@ watchdog_start1(void) { io_update_time(); - loop_time = last_time; + loop_time = last_io_time; } static inline void @@ -2145,7 +2161,7 @@ watchdog_start(void) { io_update_time(); - loop_time = last_time; + loop_time = last_io_time; event_log_num = 0; if (config->watchdog_timeout) @@ -2166,10 +2182,10 @@ watchdog_stop(void) watchdog_active = 0; } - btime duration = last_time - loop_time; + btime duration = last_io_time - loop_time; if (duration > config->watchdog_warning) - log(L_WARN "I/O loop cycle took %d ms for %d events", - (int) (duration TO_MS), event_log_num); + log(L_WARN "I/O loop cycle took %u.%03u ms for %d events", + (uint) (duration TO_MS), (uint) (duration % 1000), event_log_num); } @@ -2181,8 +2197,9 @@ void io_init(void) { init_list(&sock_list); - init_list(&global_event_list); - init_list(&global_work_list); + ev_init_list(&global_event_list, &main_birdloop, "Global event list"); + ev_init_list(&global_work_list, &main_birdloop, "Global work list"); + ev_init_list(&main_birdloop.event_list, &main_birdloop, "Global fast event list"); krt_io_init(); // XXX init_times(); // XXX update_times(); @@ -2196,6 +2213,8 @@ static int short_loops = 0; #define SHORT_LOOP_MAX 10 #define WORK_EVENTS_MAX 10 +void pipe_drain(int fd); + void io_loop(void) { @@ -2210,22 +2229,28 @@ io_loop(void) watchdog_start1(); for(;;) { - times_update(&main_timeloop); + times_update(); events = ev_run_list(&global_event_list); events = ev_run_list_limited(&global_work_list, WORK_EVENTS_MAX) || events; - timers_fire(&main_timeloop); + events = ev_run_list(&main_birdloop.event_list) || events; + timers_fire(&main_birdloop.time, 1); io_close_event(); // FIXME poll_tout = (events ? 0 : 3000); /* Time in milliseconds */ - if (t = timers_first(&main_timeloop)) + if (t = timers_first(&main_birdloop.time)) { - times_update(&main_timeloop); + times_update(); timeout = (tm_remains(t) TO_MS) + 1; poll_tout = MIN(poll_tout, timeout); } - nfds = 0; + /* A hack to reload main io_loop() when something has changed asynchronously. */ + pfd[0].fd = main_birdloop.wakeup_fds[0]; + pfd[0].events = POLLIN; + + nfds = 1; + WALK_LIST(n, sock_list) { pfd[nfds] = (struct pollfd) { .fd = -1 }; /* everything other set to 0 by this */ @@ -2284,7 +2309,9 @@ io_loop(void) /* And finally enter poll() to find active sockets */ watchdog_stop(); + birdloop_leave(&main_birdloop); pout = poll(pfd, nfds, poll_tout); + birdloop_enter(&main_birdloop); watchdog_start(); if (pout < 0) @@ -2295,7 +2322,15 @@ io_loop(void) } if (pout) { - times_update(&main_timeloop); + if (pfd[0].revents & POLLIN) + { + /* IO loop reload requested */ + pipe_drain(main_birdloop.wakeup_fds[0]); + atomic_exchange_explicit(&main_birdloop.ping_sent, 0, memory_order_acq_rel); + continue; + } + + times_update(); /* guaranteed to be non-empty */ current_sock = SKIP_BACK(sock, n, HEAD(sock_list)); diff --git a/sysdep/unix/krt.c b/sysdep/unix/krt.c index 93d19614..dd2c63c4 100644 --- a/sysdep/unix/krt.c +++ b/sysdep/unix/krt.c @@ -681,9 +681,9 @@ krt_scan_timer_kick(struct krt_proto *p) */ static int -krt_preexport(struct channel *c, rte *e) +krt_preexport(struct channel *C, rte *e) { - if (e->src->proto == c->proto) + if (e->src->proto == C->proto) return -1; if (!krt_capable(e)) diff --git a/sysdep/unix/log.c b/sysdep/unix/log.c index 4e9df069..185231e8 100644 --- a/sysdep/unix/log.c +++ b/sysdep/unix/log.c @@ -15,6 +15,7 @@ * user's manual. */ +#include <stdatomic.h> #include <stdio.h> #include <stdlib.h> #include <stdarg.h> @@ -35,8 +36,10 @@ static FILE *dbgf; static list *current_log_list; static char *current_syslog_name; /* NULL -> syslog closed */ +static _Atomic uint max_thread_id = ATOMIC_VAR_INIT(1); +static _Thread_local uint this_thread_id; -#ifdef USE_PTHREADS +#define THIS_THREAD_ID (this_thread_id ?: (this_thread_id = atomic_fetch_add_explicit(&max_thread_id, 1, memory_order_acq_rel))) #include <pthread.h> @@ -48,15 +51,6 @@ static pthread_t main_thread; void main_thread_init(void) { main_thread = pthread_self(); } static int main_thread_self(void) { return pthread_equal(pthread_self(), main_thread); } -#else - -static inline void log_lock(void) { } -static inline void log_unlock(void) { } -void main_thread_init(void) { } -static int main_thread_self(void) { return 1; } - -#endif - #ifdef HAVE_SYSLOG_H #include <sys/syslog.h> @@ -189,7 +183,7 @@ log_commit(int class, buffer *buf) l->pos += msg_len; } - fprintf(l->fh, "%s <%s> ", tbuf, class_names[class]); + fprintf(l->fh, "%s [%04x] <%s> ", tbuf, THIS_THREAD_ID, class_names[class]); } fputs(buf->start, l->fh); fputc('\n', l->fh); @@ -299,6 +293,8 @@ die(const char *msg, ...) exit(1); } +static struct timespec dbg_time_start; + /** * debug - write to debug output * @msg: a printf-like message @@ -311,12 +307,33 @@ debug(const char *msg, ...) { #define MAX_DEBUG_BUFSIZE 16384 va_list args; - char buf[MAX_DEBUG_BUFSIZE]; + char buf[MAX_DEBUG_BUFSIZE], *pos = buf; + int max = MAX_DEBUG_BUFSIZE; va_start(args, msg); if (dbgf) { - if (bvsnprintf(buf, MAX_DEBUG_BUFSIZE, msg, args) < 0) + struct timespec dbg_time; + clock_gettime(CLOCK_MONOTONIC, &dbg_time); + uint nsec; + uint sec; + + if (dbg_time.tv_nsec > dbg_time_start.tv_nsec) + { + nsec = dbg_time.tv_nsec - dbg_time_start.tv_nsec; + sec = dbg_time.tv_sec - dbg_time_start.tv_sec; + } + else + { + nsec = 1000000000 + dbg_time.tv_nsec - dbg_time_start.tv_nsec; + sec = dbg_time.tv_sec - dbg_time_start.tv_sec - 1; + } + + int n = bsnprintf(pos, max, "%u.%09u: [%04x] ", sec, nsec, THIS_THREAD_ID); + pos += n; + max -= n; + + if (bvsnprintf(pos, max, msg, args) < 0) bug("Extremely long debug output, split it."); fputs(buf, dbgf); @@ -422,6 +439,8 @@ done: void log_init_debug(char *f) { + clock_gettime(CLOCK_MONOTONIC, &dbg_time_start); + if (dbgf && dbgf != stderr) fclose(dbgf); if (!f) diff --git a/sysdep/unix/main.c b/sysdep/unix/main.c index fd4934d9..bf9f2be0 100644 --- a/sysdep/unix/main.c +++ b/sysdep/unix/main.c @@ -28,6 +28,7 @@ #include "lib/resource.h" #include "lib/socket.h" #include "lib/event.h" +#include "lib/locking.h" #include "lib/timer.h" #include "lib/string.h" #include "nest/rt.h" @@ -116,7 +117,7 @@ add_num_const(char *name, int val, const char *file, const uint line) struct f_val *v = cfg_alloc(sizeof(struct f_val)); *v = (struct f_val) { .type = T_INT, .val.i = val }; struct symbol *sym = cf_get_symbol(name); - if (sym->class && (sym->scope == conf_this_scope)) + if (sym->class && cf_symbol_is_local(sym)) cf_error("Error reading value for %s from %s:%d: already defined", name, file, line); cf_define_symbol(sym, SYM_CONSTANT | T_INT, val, v); @@ -873,13 +874,16 @@ main(int argc, char **argv) dmalloc_debug(0x2f03d00); #endif + times_update(); parse_args(argc, argv); log_switch(1, NULL, NULL); + the_bird_lock(); + random_init(); net_init(); resource_init(); - timer_init(); + birdloop_init(); olock_init(); rt_init(); io_init(); @@ -927,6 +931,7 @@ main(int argc, char **argv) dup2(0, 2); } + main_thread_init(); write_pid_file(); diff --git a/test/birdtest.c b/test/birdtest.c index ae05d1a5..5e3de1c5 100644 --- a/test/birdtest.c +++ b/test/birdtest.c @@ -21,6 +21,7 @@ #include "test/birdtest.h" #include "lib/string.h" #include "lib/event.h" +#include "lib/io-loop.h" #ifdef HAVE_EXECINFO_H #include <execinfo.h> @@ -64,6 +65,9 @@ bt_init(int argc, char *argv[]) { int c; + /* We have no interest in stdin */ + close(0); + initstate(BT_RANDOM_SEED, (char *) bt_random_state, sizeof(bt_random_state)); bt_verbose = 0; @@ -120,9 +124,11 @@ bt_init(int argc, char *argv[]) clock_gettime(CLOCK_MONOTONIC, &bt_begin); bt_suite_case_begin = bt_suite_begin = bt_begin; + the_bird_lock(); resource_init(); - ev_init_list(&global_event_list); - + ev_init_list(&global_event_list, &main_birdloop, "Global event list in unit tests"); + ev_init_list(&global_work_list, &main_birdloop, "Global work list in unit tests"); + birdloop_init(); return; usage: diff --git a/test/bt-utils.c b/test/bt-utils.c index 509b5ed4..36e44da4 100644 --- a/test/bt-utils.c +++ b/test/bt-utils.c @@ -53,6 +53,8 @@ cf_file_read(byte *dest, uint max_len, int fd) return l; } +void resource_sys_init(void); + void bt_bird_init(void) { @@ -61,7 +63,6 @@ bt_bird_init(void) log_switch(bt_verbose != 0, NULL, NULL); olock_init(); - timer_init(); rt_init(); io_init(); if_init(); @@ -73,6 +74,7 @@ bt_bird_init(void) void bt_bird_cleanup(void) { config = new_config = NULL; + the_bird_unlock(); } static char * |