Merge commit '1518970c' into HEAD

Fixing several race-conditions in event code.

After a suggestion by Santiago, I added the direct list pointer into
events and the events are now using this value to check whether the
route is active or not. Also the whole trick with sentinel node unioned
with event list is now gone.

For debugging, there is also an internal circular buffer to store what
has been recently happening in event code before e.g. a crash happened.
By default, this debug is off and must be manually enabled in
lib/event.c as it eats quite some time and space.

Longer unit test default timeout to prevent spurious build failures on slow virtuals

Table: Re-scheduling prune event when another prune loop is pending

Export event doesn't have to be postponed before requeuing as an export-stop event

Converted simple table events to loop flags

Loop flags: a simple idempotent event announcement mechanism

Cancelling all timers when loop stops

Routing tables have their own service loops.

Memory pages allocator is now a global simple lockless structure

Revert "Routing tables now have their own loops."

This reverts commit 878eeec12bf020c9e7460040d225a929bbbd2bd2.

These changes have been done in a different way in the other branch of
the future merge.

Table export announcer needs both an event and a timer to do export bundling the right way

Created a dedicated settle timer structure

Merge remote-tracking branch 'origin/master' into thread-next

Merge commit 'd2c1036a42881d413ec97203ede92a69f8cd218f' into thread-next

Merge branch 'mq-fix-eattr-setting' into thread-next

Table access is now locked.

Table feed refactoring to allow for locking and unlocking

Table long-locking debug code

Next hop updater has its own event

Next hop refactoring to allow for table locking

Better profylaction recursive route loops

In some specific configurations, it was possible to send BIRD into an
infinite loop of recursive next hop resolution. This was caused by route
priority inversion.

To prevent priority inversions affecting other next hops, we simply
refuse to resolve any next hop if the best route for the matching prefix
is recursive or any other route with the same preference is recursive.

Next hop resolution doesn't change route priority, therefore it is
perfectly OK to resolve BGP next hops e.g. by an OSPF route, yet if the
same (or covering) prefix is also announced by iBGP, by retraction of
the OSPF route we would get a possible priority inversion.

Next hop update triggered at the very end of hostcache update

Exporter routine refactoring to allow for nicer table locking

Added an indirection to the export announcement routine

There are performance reasons for this, mostly that we don't want to
ping the table service routine with every import.

ROA subscriptions are also converted to export requests.

By this, the requesting channels do the timers in their own loops,
avoiding unnecessary synchronization when the central timer went off.

This is of course less effective for now, yet it allows to easily
implement selective reloads in future.

Flowspec revalidate notification converted to an export hook

Instead of synchronous notifications, we use the asynchronous export
framework to notify flowspec src route updates. This allows us to
invoke flowspec revalidation without locking collisions.

Hostcache update notification converted to an export hook

Instead of synchronous notifications, we use the asynchronous export
framework to notify also hostcache updates. This allows us to do the
hostcache update and the subsequent next hop update notification without
locking collisions.

Miscellaneous refactoring

Table debug is now a per-table setting and has categories.

Default tables are not created unless actually used.

This allows for setting default table values at the beginning of config
file before "master4" and "master6" tables are initialized.

Tables: Requesting prune only after export cleanup

We can't free the network structures before the export has been cleaned
up, therefore it makes more sense to request prune only after export
cleanup. This change also reduces prune calls on table shutdown.

Merge branch 'mq-fix-eattr-setting' into backport

Simplified the protocol hookup code in Makefiles

Fixed initialization of Linux kernel route attributes

Merge branch 'backport' into thread-next

Merge commit '082905a8' into thread-next

Merge commit '534d0a4b' into thread-next

Merge commit '2e484f8d' into thread-next

Merge commit '971721c9' into thread-next

Merge commit '4d48ede5' into thread-next

Merge commit 'c7d0c5b2' into thread-next

Merge commit '18f66055' into thread-next

Merge commit '038fcf1c' into thread-next

It was necessary to update the code to match removal of rta, as well as
existence of cached nested attribute lists.

Merge commit '082905a8' into HEAD

rip_rte_better() uses the IGP_METRIC_UNKNOWN instead of protocol-specific infinity

Merge commit '97476e00' into thread-next

Had to fix route source locking inside BGP export table as we need to
keep the route sources properly allocated until even last BGP pending
update is sent out, therefore the export table printout is accurate.

BGP: The bucket/prefix hashes are now a resource to allow for proper cleanup

Merge commit 'f0507f05ce57398e135651896dace4cb68eeed54' into thread-next

Merge branch 'ballygarvan' into HEAD

Replacing the old 3.0-alpha0 cork mechanism with another one inside the
routing table. This version should be simpler and also quite clear what
it does, why and when.

Revert "Split route table event into separate events"

This reverts commit 445eeaf3df126af2c7b61e71c4f08a583eb4fa60.

Revert "Table cork: Stop creating updates when there are too many pending."

This reverts commit 3b20722a1fc777c27ab2e0451d0ea3fee7fa81a2.

Also next hop update routines are corking themselves when congestion is detected

BGP: respecting table cork

Route table cork: Indicate whether the export queues are congested.

These routines detect the export congestion (as defined by configurable
thresholds) and propagate the state to readers. There are no readers for
now, they will be added in following commits.

Introducing basic RCU primitives for lock-less shared data structures

Fixed main birdloop init in unit tests

Some unit tests weren't initializing the birdloop, trying to write the
birdloop ping into stdin. Fixed this and also forced stdin close on
startup of every test just to be sure that CI and local build behave the
same in this. (CI was failing on this while local build not.)

Sending an event must also ping the target IO loop

Moved the thread starting code to IO loop code

Merge commit '03bf6b90' into thread-next

Revert "Adding a generic cork mechanism for events"

This reverts commit 6e841b3153565632b6753f6b1fe74850c37f2808.

Merge branch 'master' into backport

Netlink: Restrict route replace for IPv6

Seems like the previous patch was too optimistic, as route replace is
still broken even in Linux 4.19 LTS (but fixed in Linux 5.10 LTS) for:

  ip route add 2001:db8::/32 via fe80::1 dev eth0
  ip route replace 2001:db8::/32 dev eth0

It ends with two routes instead of just the second.

The issue is limited to direct and special type (e.g. unreachable)
routes, the patch restricts route replace for cases when the new route
is a regular route (with a next hop address).

Netlink: Simplify handling of IPv6 ECMP routes

When IPv6 ECMP support first appeared in Linux kernel, it used different
API than IPv4 ECMP. Individual next hops were updated and announced
separately, instead of using RTA_MULTIPATH as in IPv4. This has several
drawbacks and requires complex code to merge received notifications to
one multipath route.

When Linux came with IPv6 RTA_MULTIPATH support, the initial versions
were somewhat buggy, so we kept using the old API for updates (splitting
multipath routes to sequences of route updates), while accepting both
old-style routes and RTA_MULTIPATH routes in scans / notifications.

As IPv6 RTA_MULTIPATH support is here for a long time, this patch fully
switches Netlink to the IPv6 RTA_MULTIPATH API and removes old complex
code for handling individual next hop announces.

The required Linux version is at least 4.11 for reliable operation.

Thanks to Daniel Gröber for the original patch.

Merge branch 'master' into backport

KRT: Scan routing tables separetely on linux to avoid congestion

Remove compile-time sysdep option CONFIG_ALL_TABLES_AT_ONCE, replace it
with runtime ability to run either separate table scans or shared scan.

On Linux, use separate table scans by default when the netlink socket
option NETLINK_GET_STRICT_CHK is available, but retreat to shared scan
when it fails.

Running separate table scans has advantages where some routing tables are
managed independently, e.g. when multiple routing daemons are running on
the same machine, as kernel routing table modification performance is
significantly reduced when the table is modified while it is being
scanned.

Thanks Daniel Gröber for the original patch and Toke Høiland-Jørgensen
for suggestions.

Fixed a rarely used part of Babel: comparing two routes in table by their metric

Revert "Export table: Delay freeing of old stored route."

This reverts commit cee0cd148c9b71bf47d007c850193b5fbf9486c1.
This change is not needed in version 2 and the surrounding code has
disappeared mostly in version 3.

Event lists rewritten to a single linked list

In multithreaded environment, we need to pass messages between workers.
This is done by queuing events to their respective queues. The
double-linked list is not really useful for that as it needs locking
everywhere.

This commit rewrites the event subsystem to use a single-linked list
where events are enqueued by a single atomic instruction and the queue
is processed after atomically moving the whole queue aside.

Merge commit '94eb0858' into thread-next

Merge commit 'a4451535' into thread-next

Fixed an annoying warning in ea_get_storage()

Fixing build issues caused by a nonportable Makefile rule

Merge commit 'a845651b' into thread-next

Merge commit 'c70b3198' into thread-next [lots of conflicts]

There were more conflicts that I'd like to see, most notably in route
export. If a bisect identifies this commit with something related, it
may be simply true that this commit introduces that bug. Let's hope it
doesn't happen.

Fixed invalid routes handling

The invalid routes were filtered out before they could ever get
exported, yet some of the routines need them available, e.g. for
display or import reload.

Now the invalid routes are properly exported and dropped in channel
export routines instead.

Merge branch 'backport' into thread-next

Merge commit '2e5bfeb73ac25e236a24b6c1a88d0f2221ca303f' into thread-next

Merge commit 'd429bc5c841a8e9d4c81786973edfa56d20a407e' into thread-next

Merge commit '7e9cede1fd1878fb4c00e793bccd0ca6c18ad452' into thread-next

Fixed bug in repeated show route command

Introduced by 13ef5e53dd4a98c80261139b4c9ce4b1074cac40, the CLI was not
properly cleaned up when the command finished, causing BIRD to not parse
any other command after "show route".

Merge commit 'f18968f5' into thread-next

BGP: Minor improvements to BGP roles

Add support for bgp_otc in filters and warning for configuration
inside confederations.

Merge commit '1df20989' into thread-next

Revert "Special table hooks rectified."

This reverts commit 44f26c49f966ca842ff9af55468de0b98c44b73e.

Removing the rte_modify API

For BGP LLGR purposes, there was an API allowing a protocol to directly
modify their stale routes in table before flushing them. This API was
called by the table prune routine which violates the future locking
requirements.

Instead of this, BGP now requests a special route export and reimports
these routes into the table, allowing for asynchronous execution without
locking the table on export.

Route refresh in tables uses a stale counter.

Until now, we were marking routes as REF_STALE and REF_DISCARD to
cleanup old routes after route refresh. This needed a synchronous route
table walk at both beginning and the end of route refresh routine,
marking the routes by the flags.

We avoid these walks by using a stale counter. Every route contains:
  u8 stale_cycle;
Every import hook contains:
  u8 stale_set;
  u8 stale_valid;
  u8 stale_pruned;
  u8 stale_pruning;

In base_state, stale_set == stale_valid == stale_pruned == stale_pruning
and all routes' stale_cycle also have the same value.

The route refresh looks like follows:
+ ----------- + --------- + ----------- + ------------- + ------------ +
|             | stale_set | stale_valid | stale_pruning | stale_pruned |
| Base        |     x     |      x      |        x      |       x      |
| Begin       |    x+1    |      x      |        x      |       x      |
  ... now routes are being inserted with stale_cycle == (x+1)
| End         |    x+1    |     x+1     |        x      |       x      |
  ... now table pruning routine is scheduled
| Prune begin |    x+1    |     x+1     |       x+1     |       x      |
  ... now routes with stale_cycle not between stale_set and stale_valid
      are deleted
| Prune end   |    x+1    |     x+1     |       x+1     |      x+1     |
+ ----------- + --------- + ----------- + ------------- + ------------ +

The pruning routine is asynchronous and may have high latency in
high-load environments. Therefore, multiple route refresh requests may
happen before the pruning routine starts, leading to this situation:

| Prune begin |    x+k    |     x+k     |    x -> x+k   |       x      |
  ... or even
| Prune begin |   x+k+1   |     x+k     |    x -> x+k   |       x      |
  ... if the prune event starts while another route refresh is running.

In such a case, the pruning routine still deletes routes not fitting
between stale_set and and stale_valid, effectively pruning the remnants
of all unpruned route refreshes from before:

| Prune end   |    x+k    |     x+k     |       x+k     |      x+k     |

In extremely rare cases, there may happen too many route refreshes
before any route prune routine finishes. If the difference between
stale_valid and stale_pruned becomes more than 128 when requesting for
another route refresh, the routine walks the table synchronously and
resets all the stale values to a base state, while logging a warning.

BGP: Implement BGP roles

Implement BGP roles as described in RFC 9234. It is  a mechanism for
route leak prevention and automatic route filtering based on common BGP
topology relationships. It defines role capability (controlled by 'local
role' option) and OTC route attribute, which is used for automatic route
filtering and leak detection.

Minor changes done by commiter.

There are now no internal tables at all.

Dropped the internal kernel protocol table for learnt routes.

The learnt routes are now pushed all into the connected table, not only
the best one. This shouldn't do any damage in well managed setups, yet
it should be noted that it is a change of behavior.

If anybody misses a feature which they implemented by misusing this
internal learn table, let us know, we'll consider implementing it in a
better way.

Export tables merged with BGP prefix hash

Until now, if export table was enabled, Nest was storing exactly the
route before rt_notify() was called on it. This was quite sloppy and
spooky and it also wasn't reflecting the changes BGP does before
sending. And as BGP is storing the routes to be sent anyway, we are
simply keeping the already-sent routes in there to better rule out
unneeded reexports.

Some of the route attributes (IGP metric, preference) make no sense in
BGP, therefore these will be probably replaced by something sensible.
Also the nexthop shown in the short output is the BGP nexthop.

Hash: iterable now per partes by an iterator

It's now possible to pause iteration through hash. This requires
struct hash_iterator to be allocated somewhere handy.

The iteration itself is surrounded by HASH_WALK_ITER and
HASH_WALK_ITER_END. Call HASH_WALK_ITER_PUT to ask for pausing; it may
still do some more iterations until it comes to a suitable pausing
point. The iterator must be initalized to an empty structure. No cleanup
is needed if iteration is abandoned inbetween.

Do not try to check flowspec validity for piped routes

Fixed bad import table attributes freeing

Attribute lists split to storage headers and data to save BGP memory

Show route uses the export request also for one-net queries

Added forgotten route source locking in flowspec validation

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

Merge commit 'beb5f78a' into backport

Merge version 2.0.10 into backport