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.

Extended route trace: logging Path Identifiers

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.

Dropping the unused rte_same hook

Dropping rte-local dumper entries

Kernel: Convert the rte-local attributes to extended attributes and flags to pflags

Route: moved rte_src pointer from rta to rte

It is an auxiliary key in the routing table, not a route attribute.

Preexport: No route modification, no linpool needed

RIP fixup + dropping the tmp_attrs mechanism as obsolete

Dropping the RTS_DUMMY temporary route storage.

Kernel route sync is done by other ways now and this code is not used
currently.

Preference moved to RTA and set explicitly in protocols

Export table: Delay freeing of old stored route.

This is needed to provide the protocols the full old route after filters
when export table is enabled.

BGP: Moved the suppressed and stale flags to pflags

Babel: Convert the rte-local attributes to extended attributes

There may be a symbol with NULL protocol when reconfiguring

OSPF: Convert the rte-local attributes to extended attributes

Show route may be accidentally called on shutdown also when not all default tables are present

RIP: convert the rte-local attributes to extended attributes

Extended route attributes may include also pointers

IGP metric getter refactoring to protocol callback

Direct protocol hooks for IGP metric inside nest/rt-table.c make the
protocol API unnecessarily complex. Instead, we use a proper callback.

fixup! Multipage allocation

Multipage allocation

We can also quite simply allocate bigger blocks. Anyway, we need these
blocks to be aligned to their size which needs one mmap() two times
bigger and then two munmap()s returning the unaligned parts.

The user can specify -B <N> on startup when <N> is the exponent of 2,
setting the block size to 2^N. On most systems, N is 12, anyway if you
know that your configuration is going to eat gigabytes of RAM, you are
almost forced to raise your block size as you may easily get into memory
fragmentation issues or you have to raise your maximum mapping count,
e.g. "sysctl vm.max_map_count=(number)".

CLI socket accept() may also fail and should produce some message, not a coredump.

OSPF: explicitly stop the periodic tick on shutdown to avoid recalculation races

Linpools may use pages instead of xmalloc

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

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).

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

Reducing filter stack size to allow for lesser thread stack size

OSPF: Setting a list node NULL before use

Fixed memory poisoning in slab

Debug output uses local buffer to avoid clashes between threads.

Filter: Additional consistency checks

Nest: Clean up main channel handling

Remove assumption that main channel is the only channel.

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

Babel: Add MAC authentication support - update

Some cleanups and bugfixes to the previous patch, including:

 - Fix rate limiting in index mismatch check

 - Fix missing BABEL_AUTH_INDEX_LEN in auth_tx_overhead computation

 - Fix missing auth_tx_overhead recalculation during reconfiguration

 - Fix pseudoheader construction in babel_auth_sign() (sport vs fport)

 - Fix typecasts for ptrdiffs in log messages

 - Make auth log messages similar to corresponding RIP/OSPF ones

 - Change auth log messages for events that happen during regular
   operation to debug messages

 - Switch meaning of babel_auth_check*() functions for consistency
   with corresponding RIP/OSPF ones

 - Remove requirement for min/max key length, only those required by
   given MAC code are enforced

Babel: Add MAC authentication support

This implements support for MAC authentication in the Babel protocol, as
specified by RFC 8967. The implementation seeks to follow the RFC as close
as possible, with the only deliberate deviation being the addition of
support for all the HMAC algorithms already supported by Bird, as well as
the Blake2b variant of the Blake algorithm.

For description of applicability, assumptions and security properties,
see RFC 8967 sections 1.1 and 1.2.

Babel: Refactor TLV parsing code for easier reuse

In preparation for adding authentication checks, refactor the TLV
walking code so it can be reused for a separate pass of the packet
for authentication checks.

Nest: Allow MAC algorithms to specify min/max key length

Add min/max key length fields to the MAC algorithm description and
validate configured keys before they are used.

Nest: Allow specifying security keys as hex bytes as well as strings

Add support for specifying a password in hexadecimal format, The result
is the same whether a password is specified as a quoted string or a
hex-encoded byte string, this just makes it more convenient to input
high-entropy byte strings as MAC keys.

Lib: Add tests for blake2s and blake2b

Import the blake2-kat.h header with test vector output from the blake
reference implementation, and add tests to mac_test.c to compare the
output of the Bird MAC algorithm implementations with that reference
output.

Since the reference implementation only has test vectors for the full
output size, there are no tests for the smaller-sized output variants.

Lib: Add Blake2s and Blake2b hash functions

The Babel MAC authentication RFC recommends implementing Blake2s as one of
the supported algorithms. In order to achieve do this, add the blake2b and
blake2s hash functions for MAC authentication. The hashing function
implementations are the reference implementations from blake2.net.

The Blake2 algorithms allow specifying an arbitrary output size, and the
Babel MAC spec says to implement Blake2s with 128-bit output. To satisfy
this, we add two different variants of each of the algorithms, one using
the default size (256 bits for Blake2s, 512 bits for Blake2b), and one
using half the default output size.

Update to BIRD coding style done by committer.

sysdep: Add wrapper to get random bytes - update

Simplify the code and fix an issue with getentropy() return value.

sysdep: Add wrapper to get random bytes

Add a wrapper function in sysdep to get random bytes, and required checks
in configure.ac to select how to do it. The configure script tries, in
order, getrandom(), getentropy() and reading from /dev/urandom.

BGP: Ensure that freed neighbor entry is not accessed

Routes from downed protocols stay in rtable (until next rtable prune
cycle ends) and may be even exported to another protocol. In BGP case,
source BGP protocol is examined, although dynamic parts (including
neighbor entries) are already freed. That may lead to crash under some
race conditions. Ensure that freed neighbor entry is not accessed to
avoid this issue.

Babel: Seqno requests are properly decoupled from neighbors when the underlying interface disappears

When an interface disappears, all the neighbors are freed as well. Seqno
requests were anyway not decoupled from them, leading to strange
segfaults. This fix adds a proper seqno request list inside neighbors to
make sure that no pointer to neighbor is kept after free.

OSPF: Fix OSPFv3 in IPv4 mode with multiple areas

Some area handling code got confused by IPv4 setup in OSPFv3 mode.

CI: Try different locale for Centos 7

CI: Package build for more platforms

.gitlab-ci.yml:
+ pkg targets for some distros added
+ artifacts added
- some distros were commented out (due to errors).

misc/docker/*:
+ Dockerfiles updated with the necessary packages.

CI: Try utf-8 locale to workaround apkg issue

CI: Build documentation where tools are available

CI: Update docker images for building of documentation

Pkg: Enable docs subpackage for Debian

CI: Test of apkg build

Also temporarily disable cf-ospf-auth, as there is some problem with it.

Tools: Improve make-dev-archive

Use git-archive to avoid unrelated and temporary files and fix some
minor issues (e.g. dependency on bash as system shell).

ubuntu: use any init-system-helpers

init-system-helpers (>= 1.56~) can't be satisfied on:

* Ubuntu 18.04 (1.51)
* Ubuntu 16.04 (1.29)
* Debian 9 (1.48)

Remove the specific version requirement in order to enable build on
older platforms.

suse: fix bird.spec to work on SUSE

SUSE is more strict about .spec.

* use SPDX license id
* add missing %ghost file directive

docs: disable docs subpackage to fix FTBFS

Adressing following FTBFS on all older debian/ubuntu distros:

    Can't locate LinuxDocTools/Data/Latin1ToSgml.pm in @INC (you may need to install the LinuxDocTools::Data::Latin1ToSgml module)

add apkg-powered upstream packaging for deb, rpm

Files in a single new distro/ dir allow apkg to build BIRD packages for
various distros directly from upstream sources as well as from upstream
archives.

Please see distro/README.md for more detail as well as apkg docs:

https://apkg.rtfd.io

I've used these files to build bird-2.0.8 on all currently supported
releases of following distros:

* Debian
* Ubuntu
* Fedora
* CentOS
* openSUSE

Please note that latest apkg with accumulated fixes for bird is needed:
https://gitlab.nic.cz/packaging/apkg/-/merge_requests/35

Flowspec: Documentation update

Flowspec: Label field should use numeric operator and not bitmask operator

Flowspec: Do not use comma for bitmask operators

For numeric operators, comma is used for disjunction in expressions like
"10, 20, 30..40". But for bitmask operators, comma is used for
conjunction in a way that does not really make much sense. Use always
explicit logical operators (&& and ||) to connect bitmask operators.

Thanks to Matt Corallo for the bugreport.

Filter: Add MPLS label route attribute

Add support to set or read outgoing MPLS labels using filters. Currently
this supports the addition of one label per route for the first next hop.

Minor changes by committer.

Flowspec: Fix values for true/false operators

RFC 8955 is pretty clear that 000 is false and 111 is true.

Flowspec: Add code for conversion of flowspec parts to interval lists

Implement function flow_explicate_part() to convert flowspec numeric
expressions to a simple list of (disjoint, sorted) intervals. That could
be used in filters to build f_tree-based int-sets from them.

Babel: Log the reason when refusing to run on an interface

The babel protocol code checks whether iface supports multicast, and
whether it has a link-local address assigned. However, it doesn not give
any feedback if any of those checks fail, it just silently ignores the
interface. Fix this by explicitly logging when multicast check fails.

Based on patch from Toke Høiland-Jørgensen, thanks!

BSD: Propagate OS-level IFF_MULTICAST to internal IF_MULTICAST flag

The BSD code did not propagate the OS-level IFF_MULTICAST flag to the
Bird-internal IF_MULTICAST flag, which causes problems with Wireguard
interfaces on FreeBSD. The Linux sysdep code does propagate the flag
already, so just copy over the same check and flag update.

OSPF: Allow ifaces with host address as unnumbered PtP or PtMP ifaces

Ifaces with host address (/32) were forced to be stubby, but now they
can be used as PtP or PtMP. For these ifaces we need to:

 - Do not force stub mode
 - Accept packets from any IP as local
 - Accept any configured neighbor as local
 - Detect ifaces properly as unnumbered
 - Use ONLINK flag for nexthops

OSPF: Packets on PtP networks should be always sent to AllSPFRouters

As specified in RFC 2328 8.1: "On physical point-to-point networks,
the IP destination is always set to the address AllSPFRouters."

Note that this likely break setups with multiple neighbors on a network
configured as PtP, which worked before. These should be configured as
PtMP.

Thanks to Senthil Kumar Nagappan for the original patch and to Joakim
Tjernlund for suggestions.

OSPF: Minor refactoring of packet sending code

Common behavior for LSupd and delayed LSack moved to ospf_send_to_iface()
and other minor changes.

CI: Fix debian-10-i386 docker file

Doc: Include full LinuxDocTools code

BIRD uses hacked LinuxDocTools for building documentation, keeping some
parts locally and using remaining parts from system-installed one. This
setup breaks when LinuxDocTools makes some internal changes and is hard
to keep consistent.

Just include full LinuxDocTools code (both hacked and unmodified parts)
to avoid consistency issues. Note that we still need some binaries from
LinuxDocTools, so it still needs to be installed to build documentation.

CI/CD: some latest releases added.

/misc/docker/:
+ debian 11 (i386+amd64) added,
+ fedora 32 added,
+ fedora 33 added,
+ fedora 34 added,
+ opensuse 15.2 added,
+ opensuse 15.3 added,
+ ubuntu 20.04 added,
+ ubuntu 20.10 added,
+ ubuntu 21.04 added,
- ubuntu 19.10 removed.

/.gitlab-ci.yml:
+ stages 'image' and 'build' updated.

Internal route tables have a reduced cleanup routine

This fixes an internal table cleanup bug introduced
in ff397df7edcbe7a8abca5b419729b9c64c063847.

BSD: Fix invalid pointer derefence in logging code

For logging purposes a stack allocated net_addr struct was passed by
value as vararg (instead of the expected pointer). This resulted in
a segfault when the specific error condition got logged.

Lib: Fix handling of buffers in timestamp formatting

The code in tm_format_real_time() mixed up two buffers and their
sizes, which may cause crash in MRT dumping code.

Thanks to Piotr Wydrych for the bugreport.

Unix: Expand accepted ranges of iproute2 constants

We support 32bit table and realm/flow ids, we should also accept them as
constants.

Thanks to Patrick Hemmer for the bugreport.

Doc: Fix flowspec example

Thanks to Matt Corallo for the bugreport.

Allocation of ea_list in one contiguous memory block

This saves some bytes of memory for complex ea's.

Routing table is now a resource allocated from its own pool

This also fixes memory leaks from import/export tables being never
cleaned up and freed.

Resources: added mb_move() to complement rmove() for memory blocks

Routing tables list iteration should use explicit node struct position

BGP: Do not keep BAF_EXT_LEN flag internally

The flag makes sense just in external representation. It is reset during
BGP export, but keeping it internally broke MRT dumps for short attributes
that used it anyways.

Thanks to Simon Marsh for the bugreport and the patch.