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.

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

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.

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

Filter: Implement for loops

For loops allow to iterate over elements in compound data like BGP paths
or community lists. The syntax is:

  for [ <type> ] <variable> in <expr> do <command-body>

Filter: Implement mixed declarations of local variables

Allow variable declarations mixed with code, also in nested blocks with
proper scoping, and with variable initializers. E.g:

function fn(int a)
{
  int b;
  int c = 10;

  if a > 20 then
  {
    b = 30;
    int d = c * 2;
    print a, b, c, d;
  }

  string s = "Hello";
}

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.

Moved nexthop + hostentry display to other eattrs

Route attribute display now normalizes ea_lists.

This is needed to display every attribute only once with overlay
attribute lists recently introduced.

Fixed new route comparison

Fixed displaying BGP and RIP attributes after recent reworks

Fixed minor bugs in handling some route attributes

Fixed undefined attribute handling

The show-route CLI command now uses the route export API

In the multithreaded environment, it is not supposed that anybody
traverses the routing table as the CLI show-route was doing. Now the
routing table traversal is gone and CLI won't hold the table locked
while computing filters.

Fixed forgotten preference handling in filters

Allowed optimized exporting of a subprefix tree

Added an option for export filter to allow for prefiltering based on the
prefix. Routes outside the given prefix are completely ignored. Config
is simple:

export in <net> <filter>;

Table export generalized to allow for exporting from non-tables

Import tables are stored as an attribute layer inside the main tables.

The separate import tables were too memory-greedy, there is no need for
them being stored as full-sized tables.

Route attribute storage keeps the previous layers

Showing the nexthop resolution target in import tables

NEWS and version update

Merge commit '938742decc6e1d6d3a0375dd012b75172e747bbc' into haugesund

Merge commit '950775f6fa3d569a9d7cd05e33538d35e895d688' into haugesund

There were quite a lot of conflicts in flowspec validation code which
ultimately led to some code being a bit rewritten, not only adapted from
this or that branch, yet it is still in a limit of a merge.

Fixing FlowSpec validation for v3 internal API

Validation is called internally from route table at the same place where
nexthop resolution is done. Also accounting for rte->sender semantics
change (not a channel but the import hook instead).

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.

Merge commit '4fe9881d625f10e44109a649e369a413bd98de71' into haugesund

Merge commit 'f15f2fcee7eeb5a100bd204a0e67018e25953420' into haugesund

Merge commit 'f2e725a76882ba6b75c3ce4fb3c760bd83462410' into haugesund

Merge commit '1c30b689ddd032ef8000fb7836348a48ba3184ff' into haugesund

Merge commit '702c04fbef222e802ca4dfac645dc75ede522db6' into haugesund

Merge commit '337c04c45e1472d6d9b531a3c55f1f2d30ebf308' into haugesund

Merge commit 'd8661a4397e4576ac404661b192dd99d928e7890' into haugesund

Merge commit '17f91f9e6e70f7e3f29502e854823c0d48571eaa' into haugesund

Merge commit '165156beeb2926472bbceca3c103aacc3f81a8cc' into haugesund

Merge commit 'cf07d8ad79273a3bbf0617c17e438602e4b64ece' into haugesund

Merge commit '1d309c4ce6e95b68c64a8f007f6dd2f1830a5707' into haugesund

Merge commit 'ef4313e1667a8745c8d8813ac78342ec7c035895' into haugesund

Merge commit 'f2f3163f6c3fba7f9ef03640d7b2f6323873d2cc' into haugesund

Merge commit 'de86040b2cf4ec9bfbb64f0e208a19d4d7e51adc' into haugesund

Merge commit '3fb70b26faca6788aa0bdf1d558414f9f777c6cd' into haugesund

Merge commit 'ef6a903e6f44b467f9606018446095521ad01ef1' into haugesund

Merge commit '0e1e632f70b74cf111f08175ab3634db2f962579' into haugesund

Merge commit '0d0f6554a5c233bf2bf830ae319191c4b1808d49' into haugesund

Merge commit '80272d4b64a38ee6f04a1c4e8566cac3a2293176' into haugesund

Merge commit 'cd9550b24487ac7327b0234fd825f4214fdf7b16' into haugesund

Merge commit '652be92a21f5575e5f74f6abe98eb4200b86776c' into haugesund

Merge commit '98fd158e28d89f10ee7a41b4f6a14fbd0021ef35' into haugesund