Filter: Improve handling of stack frames in filter bytecode

When f_line is done, we have to pop the stack frame. The old code just
removed nominal number of args/vars. Change it to use stored ventry value
modified by number of returned values. This allows to allocate variables
on a stack frame during execution of f_lines instead of just at start.

But we need to know the number of returned values for a f_line. It is 1
for term, 0 for cmd. Store that to f_line during linearization.

Filter: Simplify handling of command sequences

Command sequences in curly braces used a separate nonterminal in grammar.
Handle them as a regular command.

Filter: Fix bug in variable shadowing

When a new variable used the same name as an existing symbol in an outer
scope, then offset number was defined based on a scope of the existing
symbol ($3) instead of a scope of the new symbol (sym_). That can lead
to two variables sharing the same memory slot.

Filter: Implement soft scopes

Soft scopes are anonymous scopes that most likely do not contain any
symbol, so allocating regular scope is postponed when it is really
needed.

Filter: Implement direct recursion

Direct recursion almost worked, just crashed on function signature check.
Split function parsing such that function signature is saved before
function body is processed. Recursive calls are marked so they can be
avoided during f_same() and similar code walking.

Also, include tower of hanoi solver as a test case.

Filter: Apply constant promotion for FI_EQ / FI_NEQ

Equality comparison is defined on all values, even of different
types, but we still want to do constant promotion if possible.

Filter: Add literal for empty set

Add literal for empty set [], which works both for tree-based sets
and prefix sets by using existing constant promotion mechanism.

Minor changes by committer.

Nest: Cleanups in as_path_filter()

Use struct f_val as a common argument for as_path_filter(), as suggested
by Alexander Zubkov. That allows to use NULL sets as valid arguments.

Filter: Ensure that all expressions declared return type

All instructions with a return value (i.e. expressions, ones with
non-zero outval, third argument in INST()) should declare their return
type. Check that automatically by M4 macros.

Set outval of FI_RETURN to 0. The instruction adds one value to stack,
but syntactically it is a statement, not an expression.

Add fake return type declaration to FI_CALL, otherwise the automatic
check would fail builds.

Filter: Improve description of type system

Filter: Implement type checks for function calls

Keep list of function parameters in f_line and use it to verify
types of arguments for function calls. Only static type checks
are implemented.

Filter: Clean up function call instruction

Pass instructions of function call arguments as vararg arguments to
FI_CALL instruction constructor and move necessary magic from parser
code to interpreter / instruction code.

Preexport callback now takes the channel instead of protocol as argument

Passing protocol to preexport was in fact a historical relic from the
old times when channels weren't a thing. Refactoring that to match
current extensibility needs.

NEWS and version update

IPv4 flowspec literals should reject IPv6 prefices in a well-behaved way

When writing flow4 { dst 2001:db8::dead:beef/128; }, BIRD crashed on an
not-well-debuggable segfault as it tried to copy the whole 128-bit
prefix into an IPv4-sized memory.

Babel: Do not try to remove multicast seqno request objects from neighbour list

The Babel seqno request code keeps track of which seqno requests are
outstanding for a neighbour by putting them onto a per-neighbour list. When
reusing a seqno request, it will try to remove this node, but if the seqno
request in question was a multicast request with no neighbour attached this
will result in a crash because it tries to remove a list node that wasn't
added to any list.

Fix this by making the list remove conditional. Also fix neighbor removal
which were changing seqno requests to multicast ones instead of removing
them.

Fixes: ebd5751cdeb4 ("Babel: Seqno requests are properly decoupled from
neighbors when the underlying interface disappears").

Based on the patch from Toke Høiland-Jørgensen <toke@toke.dk>,
bug reported by Stefan Haller <stefan.haller@stha.de>, thanks.

IO: Improve resolution of latency debugging messages

Nest: Improve GC strategy for rtables

Use timer (configurable as 'gc period') to schedule routing table
GC/pruning to ensure that prune is done on time but not too often.

Randomize GC timers to avoid concentration of GC events from different
tables in one loop cycle.

Fix a bug that caused minimum inter-GC interval be 5 us instead of 5 s.

Make default 'gc period' adaptive based on number of routing tables,
from 10 s for small setups to 600 s for large ones.

In marge multi-table RS setup, the patch improved time of flushing
a downed peer from 20-30 min to <2 min and removed 40s latencies.

CI: Remove broken FreeBSD builds

We currently do not have FreeBSD CI workers.

BGP: Display neighbor port on show protocol

RPKI: Display cache server port on show protocol

Thanks to Luiz Amaral for the idea.

RPKI: Implement VRF support

BGP: Improve tx performance during feed/flush

The prefix hash table in BGP used the same hash function as the rtable.
When a batch of routes are exported during feed/flush to the BGP, they
all have similar hash values, so they are all crowded in a few slots in
the BGP prefix table (which is much smaller - around the size of the
batch - and uses higher bits from hash values), making it much slower due
to excessive collisions. Use a different hash function to avoid this.

Also, increase the batch size to fill 4k BGP packets and increase minimum
BGP bucket and prefix hash sizes to avoid back and forth resizing during
flushes.

This leads to order of magnitude faster flushes (on my test data).

Doc: fix mating -> matching in flowspec section

Babel: Fix compilation when LOCAL_DEBUG is set in packets.c

The debug output was not updated with the rest of the code, so packets.c
fails to compile if LOCAL_DEBUG is set.

Babel: Send out low-interval hello on shutdown

When shutting down a Babel instance we send a wildcard retraction to make
sure all peers can quickly switch to other route origins. Add another small
optimisation borrowed from babeld: sending a Hello message (along with the
retraction) with a very low interval.

This will cause neighbours to modify their expiry timers for the node's
state to quickly time it out, thus conserving resources in the network.

Fixed a munmap abort bug

When BIRD was munmapping too many pages, it sometimes aborted, saying
that munmap failed with "Not enough memory" as the address space was
getting more and more fragmented.

There is a workaround in place, simply keeping that page for future use,
yet it has never been compiled in because I somehow forgot to include
errno.h. And because I also thought that somebody may have ENOMEM not
defined (why?!), there was a check which quietly omitted that
workaround.

Anyway, ENOMEM is POSIX. It's an utter nonsense to check for its
existence. If it doesn't exist, something is broken.

BFD: Add 'strict bind' option

Add BFD protocol option 'strict bind' to use separate listening socket
for each BFD interface bound to its address instead of using shared
listening sockets.

Netlink: Remove superfluous sysdep/linux/netlink.c.orig

Thanks to Vincent Bernat for notice.

Lib: Allow use of 240.0.0.0/4 as a private range

There were several requests to allow use of 240.0.0.0/4 as a private
range, and Linux kernel already allows such routes, so perhaps we can
allow that too.

Thanks to Vincent Bernat and others for suggestion and patches.

Pkg: Improve RPM package unit file

Update the RPM package unit file to check configuration before start and
to use "birdc configure" instead of "kill -HUP".

Client: Use exit status to report errors

When birdc is called with a command as an argument, it should set exit
status to non-zero when BIRD replied with an error reply code.

Thanks to Vincent Bernat and others for suggestion.

Small improvement in directory test

Babel: Fix bug in iface reconfiguration

A recent change in Babel causes ifaces to disappear after
reconfiguration. The patch fixes that.

Thanks to Johannes Kimmel for an insightful bugreport.

Small change to fix doc building on Debian

Small changes related to the new release

NEWS: Fix formatting and add some notes

NEWS and version update

Alloc: Use posix_memalign() instead of aligned_alloc()

For compatibility with older systems use posix_memalign(). We can
switch to aligned_alloc() when we commit to C11 for multithreading.

Netlink: Minor cleanup

Lib: Update alignment of slabs

Alignment of slabs should be at least sizeof(ptr) to avoid unaligned
pointers in slab structures. Fixme: Use proper way to choose alignment
for internal allocators.

Merge branch 'oz-trie-table'

Trie: Fix trie format

After switching to 16-way tries, trie format ignored unaligned / internal
prefixes and only reported the primary prefix of a trie node.

Fix trie format by showing internal prefixes based on the 'local' bitmask
of a node. Also do basic (intra-node) reconstruction of prefix patterns
by finding common subtrees in 'local' bitmask.

In future, we could improve that by doing inter-node reconstruction, so
prefixes entered as one pattern for a subtree (e.g. 192.168.0.0/18+)
would be reported as such, like with aligned prefixes.

Nest: Implement locking of prefix tries during walks

The prune loop may may rebuild the prefix trie and therefore invalidate
walk state for asynchronous walks (used in 'show route in' cmd). Fix it
by adding locking that keeps the old trie in memory until current walks
are done.

In future this could be improved by rebuilding trie walk states (by
lookup for last found prefix) after the prefix trie rebuild.

Nest: Implement prefix trie pruning

When rtable is pruned and network fib nodes are removed, we also need to
prune prefix trie. Unfortunately, rebuilding prefix trie takes long time
(got about 400 ms for 1M networks), so must not be atomic, we have to
rebuild a new trie while current one is still active. That may require
some considerable amount of temporary memory, so we do that only if
we expect significant trie size reduction.

Trie: Add prefix counter

Add counter of prefixes stored in trie. Works only for 'restricted' tries
composed of explicit prefixes (pxlen == l == h), like ones used in rtables.

Doc: Describe routing table options

BGP: Implement flowspec validation procedure

Implement flowspec validation procedure as described in RFC 8955 sec. 6
and RFC 9117. The Validation procedure enforces that only routers in the
forwarding path for a network can originate flowspec rules for that
network.

The patch adds new mechanism for tracking inter-table dependencies, which
is necessary as the flowspec validation depends on IP routes, and flowspec
rules must be revalidated when best IP routes change.

The validation procedure is disabled by default and requires that
relevant IP table uses trie, as it uses interval queries for subnets.

Nest: Add routing table configuration blocks

Allow to specify sorted flag, trie fla, and min/max settle time.

Also do not enable trie by default, it must be explicitly enabled.

Nest: Add convenience functions to check rtable net type

Nest: Avoid unnecessary net_format() in 'show route' command

When output of 'show route' command was generated, the net_format() was
called for each network prematurely, even if the result was not needed.

Fix the code to call net_format() only when needed. This makes queries
that process many networks but show only few (e.g. 'show route where ..',
or 'show route count') much faster (like 5x - 10x faster).

Nest: Add trie iteration code to 'show route'

Add trie iteration code to rt_show_cont() CLI hook and use it to
accelerate 'show route in <addr>' commands using interval queries.

Nest: Implement 'show route in <addr>' command

Implement 'show route in <addr>' command, which shows all routes in
networks that are subnets of given network. Currently limited to IP
network types.

Nest: Attach prefix trie to rtable for faster LPM and interval queries

Attach a prefix trie to IP/VPN/ROA tables. Use it for net_route() and
net_roa_check(). This leads to 3-5x speedups for IPv4 and 5-10x
speedup for IPv6 of these calls.

TODO:
 - Rebuild the trie during rt_prune_table()
 - Better way to avoid trie_add_prefix() in net_get() for existing tables
 - Make it configurable (?)

BGP: Make routing loops silent

One of previous commits added error logging of invalid routes. This
also inadvertently caused error logging of route loops, which should
be ignored silently. Fix that.

BGP: Use proper class in attribute error messages

Most error messages in attribute processing are in rx/decode step and
these use L_REMOTE log class. But there are few that are in tx/export
step and these should use L_ERR log class.

Use tx-specific macro (REJECT()) in tx/export code and rename field
err_withdraw to err_reject in struct bgp_export_state to ensure that
appropriate error reporting macros are called in proper contexts.

BGP: Improve 'invalid next hop' error reporting

Distinguish multiple causes of 'invalid next hop' message and report
the relevant next hop address.

Thanks to Simon Ruderich for the original patch.

BGP: Log route updates that were changed to withdraws

Typical BGP error handling is treat-as-withdraw, where an invalid route
is replaced with a withdraw. Log route network when it happens.

.gitlab-ci.yml: minor changes inside the .yml file.

+ ubuntu:21.10 added into the pipeline,
- ubuntu:20.10 removed from the pipeline,

+ misc/docker/ubuntu-21.10-amd64/Dockerfile added,
- misc/docker/ubuntu-20.10-amd64/Dockerfile removed.

Netlink: Add option to specify netlink socket receive buffer size

Add option 'netlink rx buffer' to specify netlink socket receive buffer
size. Uses SO_RCVBUFFORCE, so it can override rmem_max limit.

Thanks to Trisha Biswas and Michal for the original patches.

Netlink: Add another workaround for older kernel headers

Unfortunately, SOL_NETLINK is both recently added and arch-dependent,
so we cannot just define it.

Netlink: Add workaround for older kernel headers

Netlink: Enable strict checking for KRT dumps

Add strict checking for netlink KRT dumps to avoid PMTU cache records
from FNHE table dump along with KRT.

Linux Kernel added FNHE table dump to the netlink API in patch:

https://patchwork.ozlabs.org/project/netdev/patch/8d3b68cd37fb5fddc470904cdd6793fcf480c6c1.1561131177.git.sbrivio@redhat.com/

Therefore, since Linux 5.3 these route cache entries are dumped together
with regular routes during periodic KRT scans, which in some cases may be
huge amount of useless data. This can be avoided by using strict checking
for netlink dumps:

https://lore.kernel.org/netdev/20181008031644.15989-1-dsahern@kernel.org/

The patch mitigates the risk of receiving unknown and potentially large
number of FNHE records that would block BIRD I/O in each sync. There is a
known issue caused by the GRE tunnels on Linux that seems to be creating
one FNHE record for each destination IP address that is routed through
the tunnel, even when the PMTU equals to GRE interface MTU.

Thanks to Tomas Hlavacek for the original patch.

Netlink: Explicitly skip received cloned routes

Kernel uses cloned routes to keep route cache entries, but reports them
together with regular routes. They were skipped implicitly as they
do not have rtm_protocol filled. Add explicit check for cloned flag
and skip such routes explicitly.

Also, improve debug logs of skipped routes.

BGP: Add option 'free bind'

The BGP 'free bind' option applies the IP_FREEBIND/IPV6_FREEBIND
socket option for the BGP listening socket.

Thanks to Alexander Zubkov for the idea.

IO: Support nonlocal bind in socket interface

Add option to socket interface for nonlocal binding, i.e. binding to an
IP address that is not present on interfaces. This behaviour is enabled
when SKF_FREEBIND socket flag is set. For Linux systems, it is
implemented by IP_FREEBIND socket flag.

Minor changes done by commiter.

Test: Activate some remaining build tests

Netlink: Do not ignore dead routes from BIRD

Currently, BIRD ignores dead routes to consider them absent. But it also
ignores its own routes and thus it can not correctly manage such routes
in some cases. This patch makes an exception for routes with proto bird
when ignoring dead routes, so they can be properly updated or removed.

Thanks to Alexander Zubkov for the original patch.

Netlink: Improve multipath parsing errors

Function nl_parse_multipath() should handle errors internally.

Conf: Fix parsing full-length IPv6 addresses

Lexer expression for bytestring was too loose, accepting also
full-length IPv6 addresses. It should be restricted such that
colon is used between every byte or never.

Fix the regex and also add some test cases for it.

Thanks to Alexander Zubkov for the bugreport

gitlab-ci.yml: failing gitlab runner fixed.

'registry.labs.nic.cz' -> 'registry.nic.cz' changed

Doc: Document min/max operators for lists

Filter: Add operators to find minimum and maximum element of sets

Add operators .min and .max to find minumum or maximum element in sets
of types: clist, eclist, lclist. Example usage:

bgp_community.min
bgp_ext_community.max
filter(bgp_large_community, [(as1, as2, *)]).min

Signed-off-by: Alexander Zubkov <green@qrator.net>

Doc: Document community components access operators

Filter: Add operators to pick community components

Add operators that can be used to pick components from
pair (standard community) or lc (large community) types.
For example:

(10, 20).asn --> 10
(10, 20).data --> 20

(10, 20, 30).asn --> 10
(10, 20, 30).data1 --> 20
(10, 20, 30).data2 --> 30

Signed-off-by: Alexander Zubkov <green@qrator.net>

BSD: Assume onlink flag on ifaces with only host addresses

The BSD kernel does not support the onlink flag and BIRD does not use
direct routes for next hop validation, instead depends on interface
address ranges. We would like to handle PtMP cases with only host
addresses configured, like:

  ifconfig wg0 192.168.0.10/32
  route add 192.168.0.4 -iface wg0
  route add 192.168.0.8 -iface wg0

To accept BIRD routes with onlink next-hop, like:

  route 192.168.42.0/24 via 192.168.0.4%wg0 onlink

BIRD would dismiss the route when receiving from the kernel, as the
next-hop 192.168.0.4 is not part of any interface subnet and onlink
flag is not kept by the BSD kernel.

The commit fixes this by assuming that for routes received from the
kernel, any next-hop is onlink on ifaces with only host addresses.

Thanks to Stefan Haller for the original patch.

RPKI: Add contextual out-of-bound checks in RTR Prefix PDU handler

RFC 6810 and RFC 8210 specify that the "Max Length" value MUST NOT be
less than the Prefix Length element (underflow). On the other side,
overflow of the Max Length element also is possible, it being an 8-bit
unsigned integer allows for values larger than 32 or 128. This also
implicitly ensures there is no overflow of "Length" value.

When a PDU is received where the Max Length field is corrputed, the RTR
client (BIRD) should immediately terminate the session, flush all data
learned from that cache, and log an error for the operator.

Minor changes done by commiter.

Doc: bgp: remove "advertise ipv4"

The option was removed in d15b0b0a ("BGP redesign", 2016-12-07)
but the documentation wasn't updated.

Nest: Do not ignore secondary flag changes in ifa updates

Compare all IA_* flags that are set by sysdep iface code.

The old code ignores IA_SECONDARY flag when comparing whether iface
address updates from kernel changed anything. This is usually not an
issue as kernel removes all secondary addresses due to removal of the
primary one, but it breaks when sysctl 'promote_secondaries' is enabled
and kernel promotes secondary addresses to primary ones.

Thanks to 'Alexander' for the bugreport.

Trie: Clarify handling of less-common net types

For convenience, Trie functions generally accept as input values not only
NET_IPx types of nets, but also NET_VPNx and NET_ROAx types. But returned
values are always NET_IPx types.

Memory statistics split into Effective and Overhead

This feature is intended mostly for checking that BIRD's allocation
strategies don't consume much memory space. There are some cases where
withdrawing routes in a specific order lead to memory fragmentation and
this output should give the user at least a notion of how much memory is
actually used for data storage and how much memory is "just allocated"
or used for overhead.

Also raising the "system allocator overhead estimation" from 8 to 16
bytes; it is probably even more. I've found 16 as a local minimum in
best scenarios among reachable machines. I couldn't find any reasonable
method to estimate this value when BIRD starts up.

This commit also fixes the inaccurate computation of memory overhead for
slabs where the "system allocater overhead estimation" was improperly
added to the size of mmap-ed memory.

Trie: Implement longest-prefix-match queries and walks

The prefix trie now supports longest-prefix-match query by function
trie_match_longest_ipX() and it can be extended to iteration over all
covering prefixes for a given prefix (from longest to shortest) using
TRIE_WALK_TO_ROOT_IPx() macro.

Directly mapped pages are kept for future use if temporarily not needed

Trie: Implement trie walking code

Trie walking allows enumeration of prefixes in a trie in the usual
lexicographic order. Optionally, trie enumeration can be restricted
to a chosen subnet (and its descendants).

Trie: Simplify network matching code

Introduce ipX_prefix_equal() and use it to simplify network matching code.

Conf: Fix crash during shutdown

BIRD implements shutdown by reconfiguring to fake empty configuration.
Such fake config structure is created from the last running config and
shares some data, including symbol table. This allows access to (removed)
routing tables and causes crash when 'show route' command is used during
shutdown.

Clean up symbol table, table list and links to default tables, so removed
routing tables cannot be accessed during shutdown.

Filter: Add prefix trie benchmarks

Add trie tests intended as benchmarks that use external datasets
instead of generated prefixes. As datasets are not included, they
are commented out by default.

Filter: Improve prefix trie tests

Add tests explicitly matching insides and outsides of trie and update
tests to do testing of both IPv4 and IPv6 tries.

Filter: Update trie documentation

Filter: Fix trie test

Generated prefixes must be valid.

Filter: Faster prefix sets

Use 16-way (4bit) branching in prefix trie instead of basic binary
branching. The change makes IPv4 prefix sets almost 3x faster, but
with more memory consumption and much more complicated algorithm.

Together with a previous filter change, it makes IPv4 prefix sets
about ~4.3x faster and slightly smaller (on my test data).

Nest: Clean up main channel handling

Remove assumption that main channel is the only channel.

Nest: Fix export of tmpattrs through pipes

Pipes copy the original rte with old values, so they require rte to be
exported with stored tmpattrs. Other protocols access stored attributes
using eattr list, so they require rte to be exported with expanded
tmpattrs. This is temporary hack, we plan to remove whoe tmpattr mechanism.

Thanks to Paul Donohue for the bugreport.

Revert "Nest: Fix export of tmpattrs through pipes"

This reverts commit f8e273b5e7a3c721f4a30cf27a0b4fe54602e83f.

Nest: Fix export of tmpattrs through pipes

In most cases of export there is no need to store back temporary
attributes to rte, as receivers (protocols) access eattr list anyway.
But pipe copies the original rte with old values, so we should store
tmpattrs also during export.

Thanks to Paul Donohue for the bugreport.

CI: Allow Babel tests

Nest: Allow both 'password' and 'key' keywords for authentication keys

Babel: Simplify auth expiration

Just use hello_expiry for that, keep init_expiry for initial
unauthentized neighbors.

Nest: Fix password list parsing code

One of previous patches broke password list parsing code, fix that.

Lib: Fix static assert macro