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

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

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

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

Merge commit 'd39ef961d1dde230c55fcc931b53f44cb34a1e63' into haugesund

Merge commit '4a23ede2b056a41456790cc20a0c3d92a7137693' into haugesund

Merge commit 'ebd807c0b8eb0b7a3dc3371cd4c87ae886c00885' into haugesund

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

Merge commit '9eec503b251c3388579032b300d32640403d8612' into haugesund-to-2.0

Merge commit '692055e3df6cc9f0d428d3b0dd8cdd8e825eb6f4' into haugesund-to-2.0

Merge commit '3a6eda995ecfcebff3130d86ee3baeab12a41335' into haugesund

Squashing the route attribute structure into one level.

For now, all route attributes are stored as eattrs in ea_list. This
should make route manipulation easier and it also allows for a layered
approach of route attributes where updates from filters will be stored
as an overlay over the previous version.

Route destination field merged with nexthop attribute; splitting flowspec validation result out.

As there is either a nexthop or another destination specification
(or othing in case of ROAs and Flowspec), it may be merged together.
This code is somehow quirky and should be replaced in future by better
implementation of nexthop.

Also flowspec validation result has its own attribute now as it doesn't
have anything to do with route nexthop.

CI: Remove broken FreeBSD builds

We currently do not have FreeBSD CI workers.

Moved hostentry to eattr

Moved nexthop from struct rta to extended attribute.

This doesn't do anything more than to put the whole structure inside
adata. The overall performance is certainly going downhill; we'll
optimize this later.

Anyway, this is one of the latest items inside rta and in several
commits we may drop rta completely and move to eattrs-only routes.

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

All outstanding MPLS label stacks are stored as adata

Moved route source attribute (RTS_*) to eattrs

Removing the route scope attribute. Use custom attributes instead.

The route scope attribute was used for simple user route marking. As
there is a better tool for this (custom attributes), the old and limited
way can be dropped.

Moved route preference to eattrs

Joined the RTA igp_metric and EA igp_metric attributes

Removed forgotten remnants of unused enum rtc

Conf: Allowing keyword redefinition

Some tokens are both keywords and symbols. For now, we allow only
specific keywords to be redefined; in future, more of the keywords may
be added to this category.

The redefinable keywords must be specified in any .Y file as follows:

  toksym: THE_KEYWORD ;

See proto/bgp/config.Y for an example.

Also dropped a lot of unused terminals.

Moved advertising router info (FROM attribute) to eattrs

Explicit definition structures of route attributes

Changes in internal API:

* Every route attribute must be defined as struct ea_class somewhere.
* Registration of route attributes known at startup must be done by
  ea_register_init() from protocol build functions.
* Every attribute has now its symbol registered in a global symbol table
  defined as SYM_ATTRIBUTE
* All attribute ID's are dynamically allocated.
* Attribute value custom formatting hook is defined in the ea_class.
* Attribute names are the same for display and filters, always prefixed
  by protocol name.

Also added some unit testing code for filters with route attributes.

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.

Local route attributes are always allocated from tmp_linpool

Filters always allocate from tmp_linpool

Attribute list normalization cleanup

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

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

Implicit ROA check converted to explicit filter instruction sequence

Protocols use EA_LITERAL_* to set attributes

Moved filter value union to lib

Filters: removing adata_empty() duplicating lp_alloc_adata()

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

Fixed spurious undef of route attributes

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.

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.

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.

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.

Protocols have their own explicit init routines