Conf: Symbols are properly scoped

Now there is a persistent root symbol scope and all scopes have their
symbol hashes to store local symbols and not leak any symbol out.

Replaced boilerplate eattr allocation by ea_set_attr()

Enforcing certain data structure explicit paddings.

Implicit paddings have undefined values in C. We want the eattr blocks
to be comparable by memcmp and eattrs settable directly by structrure
literals. This check ensures that all paddings in eattr and bval are
explicit and therefore zeroed in all literals.

Protocols use EA_LITERAL_* to set attributes

Local route attributes are always allocated from tmp_linpool

Filters always allocate from tmp_linpool

Attribute list normalization cleanup

Moved filter value union to lib

Complex route attributes are data structures, shall be in lib also

Splitting route data structures out to lib

FIB is a data structure generic enough to be in lib

Filters: removing adata_empty() duplicating lp_alloc_adata()

Unified attribute and filter types

This commit removes the EAF_TYPE_* namespace completely and also for
route attributes, filter-based types T_* are used. This simplifies
fetching and setting route attributes from filters.

Also, there is now union bval which serves as an universal value holder
instead of private unions held separately by eattr and filter code.

Opaque types are named opaque also in filters

Special attribute types for enums

Dropping EAF_VAR_LENGTH as the attribute data is either embedded or adata

Filter: Bitfield eattrs reading / writing moved to filter code

Before this change, fetch-update-write and bitmasking was hardcoded in
attribute access code cased by the attribute type. Several filter
instructions are used to do it instead.

As this is certainly going to be a little bit slower than before, the
switch block in attribute access code should be completely removed in
near future, helping with both performance and code cleanliness.

The user interface should have stayed intact.

Filter operations: bitwise AND and OR

Implicit ROA check converted to explicit filter instruction sequence

Fixed spurious undef of route attributes

RIP: fixed the EA_RIP_FROM attribute

The interface pointer was improperly converted to u32 and back. Fixing
this by explicitly allocating an adata structure for it. It's not so
memory efficient, we'll optimize this later.

BGP uses lp_save / lp_restore instead of linpool flushing

It is too cryptic to flush tmp_linpool in these cases and we don't want
anybody in the future to break this code by adding an allocation
somewhere which should persist over that flush.

Saving and restoring linpool state is safer.

All linpools use pages to allocate regular blocks

BGP: Fixed LLGR depreferencing in bgp_rte_mergable

Protocols have their own explicit init routines

Unsetting route attributes without messing with type system

Eattr flags (originated and fresh) get their own struct fields

Minor fix: f_val literals should always have named struct fields

Converted Slab allocator to typed lists

Slab allocator can free the blocks without knowing the parent structure

Typed lists for easier walking and stronger type checking

Printf variant with a result allocated inside a pool / linpool

Slab memory allocator unit test

Fixed a static assert in page allocator

Merge remote-tracking branch 'origin/master' into haugesund

Merge commit '60880b539b8886f76961125d89a265c6e1112b7a' into haugesund

BGP Flowspec validation: Removed in-route optimization for multithreading compatibility

Merge commit 'e42eedb9' into haugesund

Merge commit '5cff1d5f' into haugesund

Conflicts:
      proto/bgp/attrs.c
      proto/pipe/pipe.c

Merge commit 'd5a32563' into haugesund

Fixed resource initialization in unit tests

Linpools with pages fixed to the final page allocator version

Merge commit '0c59f7ff' into haugesund

Revert "Bound allocated pages to resource pools with page caches to avoid unnecessary syscalls"

This reverts commit 7f0e59820899c30a243c18556ce2e3fb72d6d221.

Revert "fixup! Bound allocated pages to resource pools with page caches to avoid unnecessary syscalls"

This reverts commit bea582cbb53e30dd32a5b6829c7443e0e5558d11.

Revert "Multipage allocation"

This reverts commit 6cd37713781a3092f8166b2178fae35cbfec1e28.

Revert "fixup! Multipage allocation"

This reverts commit a54f75f454b7ed8c8ff2c1787a506528f22cbae7.

Single-threaded version of sark-branch memory page management

Replacing BGP temporary linpools by the common temporary linpool

Replaced custom linpools in tests for the common tmp_linpool

Introducing an universal temporary linpool flushed after every task

Static list initializer

Small improvement in directory test

Merge commit '2c13759136951ef0e70a3e3c2b2d3c9a387f7ed9' into haugesund

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.