rt-table.c: Solution for missing igp_metric described in issue #154.
The igp_metric was set as an eattr, but not as a hostentry attribut.
However, the eattr was ignored and possibly even rewritten to
the hostentry (default) value.
The hostentry is initialized in ea_set_hostentry. There is an ea_list,
but it is not used for setting the igp_metric and it seems like it
does not contain the igp_metric at all. That is why I set it in rt_next_hop_resolve_rte.

rt-table: fixed rt_notify_basic - old route is now cleared in case it was previously rejected. The problem manifested in RA_OPTIMAL channel mode. In this mode, we need only one route of a net to be in accepted table or to be in rejected table, but not in both. When there was a route in accepted map and we were addind another route of the same net, we added the new route, removed the old route and everything was ok. But when the first route was in rejected map, we just added the new route. That caused inconsistency - there were two routes of the same net in the maps (in accepted and rejected or both in rejected). This was causing a crashes in assert in channel_notify_basic.

Fixing a refeed inconsistency

On refeed, the table should not resend any obsolete routes
which have already been seen by the recipient, nor the appropriate
journal items.

fixup! BGP: Export uses common attribute cache

BGP: Export uses common attribute cache

There is no real need for storing bucket attributes locally and we may
save some memory by caching the attributes in one central place.

This was a contention problem though, so this commit got reverted,
but now the attribute cache is actually lockless (yay!) and we can
try it again.

If this becomes a contention problem, we should ... no, please not.
Not again! Please!

(Dug out from the history and updated by Katerina Kubecova.)

Unlocking the global attribute cache

Now, when we have the unlocked slab, we can also go for a completely
lockless global attribute cache, which has been the major contention
point in BIRD 3.

This is a complicated data structure, basically a lockless hash table
with use-counted items inside, allowing concurrent insertions and
deletions.

Hash tables have to dynamically resize its base array, and the rehash
routine runs from an event if needed.

Also, due to some funny meta-race conditions, it is now possible to
end up with multiple ea_list_storage instances with the same contents,
yet it looks like it happens very rarely. (Prove us wrong, we dare you!)

Slab: Allowing concurrent allocations without locking

Every active thread now gets its own page from which it allocates
blocks. This enables concurrent allocations without much contention,
alleviating the need for mutex locking over Slab allocations,
effectively making Slab lock-free.

This adds some overhead in case every thread just allocates one item and
finishes, yet these situations should not happen too often and/or have
too large impact, so we don't need to care much. If something like this
happens, though, please cry. We'll cry with you, for sure.

Also there is a cleanup routine now which has to run often enough to
ensure that pages with some freed blocks get available for allocations.

This rework also changes the API of slabs, requiring an event list to
send cleanup events to, to be passed to sl_new().

Slab: Remove fake slab

From the beginning, there is a years-old implementation of a slab
not actually being a slab, just transparently passing all requests
to malloc and free. We don't need that anymore, we have different
methods now to determine whether the problem is the allocator or
something else, and as we are going to change the slab API anyway,
together with some behavioral updates, having a fake slab is just
an anachronism.

Threads: assigning IDs from hmap

For certain upcoming data structures, we actually need to use thread IDs
as a functional information to index things, not just a logging token.
Thus, we need them to be dense, not just flying around as they were until now.

To achieve this, we assign the IDs from a global hmap when the threads
are started, and properly return them when the threads are finished.
This way, the IDs of stopping threads are expected to be recycled,
whereas until now it wasn't expected to happen.

You may need to take care about this in your log reading apparatus.

Also there is now a maximum thread count hard limit because unlimited
thread count is too crazy to handle. But the limit is still ridiculously
high and nobody is ever expected to hit it anyway.

Threads: add a callback for thread shutdown

RCU: Add split-sync calls

Now, instead of synchronize_rcu(), one can call rcu_begin_sync(),
store the value, and (probably via defer_call()) use it later
to check by rcu_end_sync() that it indeed has ended.

Documentation: show memory decription

Revert migration of route attributes and BGP TX cache to Stonehenge

It collides with the new implementation of lockless Slab and global
attribute cache, and becomes effectively useless.

This reverts commit 4f7899e3cb17ee67875e53512db25ba5aa1dc236.
This reverts commit 240dd41f06ef805f0f45ab8d2f58376fb9e538a6.
This reverts commit 29df992f7f6ad03110240b2e65b498fe97371725.

NEWS and version update

Merge remote-tracking branch 'origin/stable-v2.16' into HEAD

NEWS and version update

Merge commit 'abecb5bb408f253cd24345ba94940ea0f7b59f4f' into HEAD

Merge commit '85aa283071ed75059fd8c889bc4ee33be1f901af' into HEAD

Merge commit 'd221f39731be40ed3821f8db09d590edb849cb0c' into HEAD

Merge commit 'e063365590b9b857a5bd0acfa519783eba639bbf' into stable-v3.0

lib: Unify alignment of allocators

Different internal allocators (memory blocks, linpools, and slabs) used
different way to compute alignment. Unify it to use alignment based on
standard max_align_t type.

On x86_64, this does not change alignment of memory blocks and linpools
(both old and new is 16), but it increases alignment of slabs from 8 to
16.

Minor changes by commiter.

Table: Fixed table debug settings reconfiguration

Table: more best route refeed fixes

Best route refeed is tricky. The journal may include repeatedly the same
route in the old and/or in the new position in case of flaps. We don't
like checking that fully in the RCU critical section which is already
way too long, thus we filter out the repeated occurence of the current
best route while keeping possibly more old routes.

We also don't want to send spurious withdraws, and we need to check that
only one notification per net is sent for RA_OPTIMAL.

There was also missing a rejected map update in case of idempotent
squashed update, and last but not least, the best route journal should
not include invalid routes (import keep filtered).

Table: old best route refeed fix

When refeeding with RA_OPTIMAL, the old best routes weren't announced,
leading to weird behavior of protocols, mostly kernel. Fixed.

BGP: fixed deterministic med crashes

There were several places of forgotten NULL checks.

Thanks to Alarig Le Lay <alarig@swordarmor.fr> for reporting:
https://trubka.network.cz/pipermail/bird-users/2024-December/017990.html

BGP: fix display name of bgp_otc attribute

Allocate the normalization buckets on stack

Even though allocating from tmp_linpool is quite cheap,
it isn't cheap when the block is larger than a page, which is the case here.
Instead, we now allocate just the result which typically fits in a page,
avoiding a necessity of a malloc().

BGP: TX bucket storage moved to Stonehenge

Route attribute storage moved to Stonehenge

Stonehenge: multi-slab allocator

To mid-term allocate and free lots of small blocks in a fast pace,
mb_alloc is too slow and causes heap bloating. We can already allocate
blocks from slabs, and if we allow for a little bit of inefficiency,
we can just use multiple slabs with stepped sizes.

This technique is already used in ea_list allocation which is gonna be
converted to Stonehenge.

Graceful recovery: converted to obstacles

Yet another refcounting mechanism had a locking collision.

Kernel: feed only once during startup

There was an inefficiency in the initial scan state machine,
causing routes to be fed several times instead of just once.
Now the export startup is postponed until first krt_scan()
finishes and we actually can do the pruning with full information.

CLI: Flushing tmp_linpool after every shown net.

There is no reason to keep the allocated objects through multiple nets.

CLI: allocate TX buffers as pages, not by malloc

Every malloc risks heap bloating and these blocks are already
the same size as pages.

Static: fixed ASPA reconfiguration

Due to an oversight, the provider lists weren't compared on reconfiguration.

Reported-By: Ralph Covelli <rcovelli@he.net>

Nest: Fix handling of 64-bit rte_src.private_id

The commit 21213be523baa7f2cbf0feaa617f265c55e9b17a expanded private_id
in route source to u64, but forgot to modify function arguments, so it
was still cropped at 32-bit, which may cause some collisions for L3VPN.
This patch fixes that.

Lib: Ensure that all net_addr structures have the same alignment

Also weaken the explicit alignment of net_addr to be u32, as VPN
is already u32-aligned.

Doc: Fix protocol outline in RPKI

Protocol outlines should not contain specific values.

Also fix some space intendation in code sections.

Lib: Data type for VPN route distinguishers

Use a distinct data structure for VPN route distinguishers instead
of just u64.

Netlink: Handle onlink flag on BSD-Netlink

On BSD, the onlink flag is not tracked or reported by kernel. We are
using an heuristic that assigns the onlink flag to routes scanned from
the kernel. We should use the same heuristic even in BSD-Netlink
case, as the onlink flag is not reported here too.

Thanks to Björn König for the original patch.

Babel: fix seqno wrapping on seqno request

The Babel seqno wraps around when reaching its maximum value (UINT16_MAX).
When comparing seqnos, this has to be taken into account. Therefore,
plain number comparisons do not work.

BFD: Fix session reconfiguration locking order

The sessions have to be updated asynchronously to avoid
cross-locking between protocols.

Testsuite: cf-ibgp-bfd-switch, cf-ibgp-multi-bfd-auth
Fixes: #139
Thanks to Daniel Suchy <danny@danysek.cz> for reporting:
https://trubka.network.cz/pipermail/bird-users/2024-December/017984.html

BGP: fix locking order error on dynamic protocol spawn

We missed that the protocol spawner violates the prescribed
locking order. When the rtable level is locked, no new protocol can be
started, thus we need to:

* create the protocol from a clean mainloop context
* in protocol start hook, take the socket

Testsuite: cf-bgp-autopeer
Fixes: #136
Thanks to Job Snijders <job@fastly.com> for reporting:
https://trubka.network.cz/pipermail/bird-users/2024-December/017980.html

Kernel: when channel traces, we have to trace the final result

Otherwise it looks like we are sending too much traffic to netlink
every other while, which is not true. Now we can disambiguate between
in-kernel updates and ignored routes.

Table: not feeding twice, once is enough

If there is no feed pending, the requested one should be
activated immediately, otherwise it is activated only after
the full run, effectively running first a full feed and
then the requested one.

Kernel: Fix crash for merge paths on if no route is in BIRD

There was a missing check for a NULL return value.
Also fixed an indenting error.

Thanks to Radu Anghel for reporting it:
https://bird.network.cz/pipermail/bird-users/2024-December/017977.html

NEWS and version update

Debian: Depend on libssh's default flavor

This mirrors Debian bird2 change, gcrypt flavor is deprecated.

https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=1074257

BGP: Print warnings when the allocated memory is larger than given acceptable maximum.

Table exporter journal dumping and memsize

The show-memory command wasn't showing the consumed memory
properly because it ignored the journal size. Now it does.

Fix mallopt configure checks

Some systems do have malloc.h but don't have mallopt.

Table cork compromise

The original values were way too low but what was set
later was too high and caused memory buildup upon startup.

Table prune inhibited during reconfiguration

When many changes are done during reconfiguration, the table may
start pruning old routes before everything is settled down, slowing
down not only the reconfiguration, but also the shutdown process.

Disable multiple malloc arenas

In our usecase, these are impossibly greedy because we often
free memory in a different thread than where we allocate, forcing
the default allocator to scatter the used memory all over the place.

More accurate allocator internal log

Drop forgotten debug logs

ROA: Extended and more thorough test

There was a suspicion that maybe the BIRD 3 version of ROA gets the
digesting wrong. This test covers the nastiest cornercases we could
think about, so now we can expect it to be right.

Merge commit '1dbee120' into thread-next

Merge tag 'v2.16' into thread-next

v2.16

Allow allocating cold pages inside RCU critical section

We have quite large critical sections and we need to allocate inside
them. This is something to revise properly later on, yet for now,
instead of slowly but surely growing the virtual memory address space,
it's better to optimize the cold page cache pickup and count situations
where this happened inside the critical section.

Fixed a subtle memory leak in protocol restart routine

Merge commit '707cad61' into thread-next

Merge commit 'ef456118' into thread-next

Merge commit 'd85fa48e' into thread-next

The resource dumping routines needed to be updated in v3 to use the new
API introduced in v2.

Conflicts:
filter/f-util.c
filter/filter.c
lib/birdlib.h
lib/event.c
lib/mempool.c
lib/resource.c
lib/resource.h
lib/slab.c
lib/timer.c
nest/config.Y
nest/iface.c
nest/iface.h
nest/locks.c
nest/neighbor.c
nest/proto.c
nest/route.h
nest/rt-attr.c
nest/rt-table.c
proto/bfd/bfd.c
proto/bmp/bmp.c
sysdep/unix/io.c
sysdep/unix/krt.c
sysdep/unix/main.c
sysdep/unix/unix.h

Merge remote-tracking branch 'origin/apkg-v3' into thread-next

EAttr normalization rewritten to use bucket sort

The EAttr ID space is dense so we can just walk once, sweep the whole
input and go home.

There is a little bit of memory inefficiency in allocating always the
largest possible block, yet it isn't too bad.

There are also unit tests for this.

CLI: show threads all crash fixed

When socket dropped before finished, it failed to cleanup.

Fix alignment requirements to include atomic u64.

Not having this led to bus errors on unaligned atomic u64 access
on architectures with 4B pointers.

Proto show: show creation and last autorestart time

Merge commit '4dd5b3d9' into thread-next

Merge commit '145830bd' into thread-next

Merge commit '946386f2' into thread-next

Merge commit '7ee27418' into thread-next

BMP: Fixing corner cases

Protocol state propagation collision, shutdown collision.

BMP: Never touching the BGP directly

Dropped hopefully last remnants of BMP directly accessing BGP structures.

Nest: proto/channel state table naming convention cleanup

Lockfree journal: Cleanup hook runs only when needed.

The function lfjour_cleanup_hook() was scheduled each time any of the
journal recipients reached end of a block of journal items or read all
of journal items. Because lfjour_cleanup_hook() can clean only journal
items every recipient has processed, it was often called uselessly.

This commit restricts most of the unuseful scheduling. Only some
recipients are given a token alowing them to try to schedule the
cleanup hook. When a recipient wants to schedule the cleanup hook, it
checks whether it has a token. If yes, it decrements number of tokens
the journal has given (issued_tokens) and discards its own token. If
issued_tokens reaches zero, the recipient is allowed to schedule the
cleanup hook.

There is a maximum number of tokens a journal can give to its recipients
(max_tokens). A new recipient is given a token in its init, unless the
maximum number of tokens is reached. The rest of tokens is given to
customers in lfjour_cleanup_hook().

In the cleanup hook, the issued_tokens number is increased in order to
avoid calling the hook before it finishes. Then, tokens are given to the
slowest recipients (but never to more than max_token recipients). Before
leaving lfjour_cleanup_hook(), the issued_tokens number is decreased back.
If no other tokens are given, we have to make sure the
lfjour_cleanup_hook will be called again. If every item in journal was
read by every recipient, tokens are given to random recipients. If all
recipients with tokens managed to finish until now, we give the token to
the first unfinished customer we find, or we just call the hook again.

Nest: fixed a race-condition between import and export

There was a leaking stack pointer to the global memory.
Fixed by making that temporary structure thread local static.

Fix typos found by lintian

I: bird3: spelling-error-in-binary "an other" "another" [usr/sbin/bird]
I: bird3: spelling-error-in-binary Reseting Resetting [usr/sbin/bird]
I: bird3: spelling-error-in-binary authenication authentication [usr/sbin/bird]

I was unable to fix the following:

I: bird3: spelling-error-in-binary upto up to [usr/sbin/bird]

Debian: Remove unneeded Pre-Depends: init-system-helpers

Lintian proclaims this is an essential package.

Debian: Add upstream lintian-overrides

Debian: Add BuildDepends: ca-certificates

This should reportedly fix test issues on ARM.

Debian: Add Rules-Requires-Root: no to d/control

Debian: Rename package to bird3

Also reformat using

    wrap-and-sort -bast

BMP: Dropped remnants of unused channels

BMP: refactored lists and table locks to tlists

BMP: protocol state ingestion refactoring

BMP: Tamed a TX buffer warning

Merge commit 'a47704a53db4f088e52e43f8b24785e5777ce147' into thread-next

Merge commit '73e7d3f5cede2e72eb9e77d61424a8c443672c09' into thread-next

Merge commit '5205ff97448cc34cf7334e90172c28eb48f227f2' into thread-next

Merge commit 'e6a100b31a7637ee739338e4b933367707ec931f' into thread-next

CI: Fix filter tests for ASPA

(broken by previous change)

Static: Fix ASPA static route argument

It seems that it should be 'providers' instead of 'provider'.

It matches keyword declaration and documentation. Mismatch beween keyword
declaration also breaks static-only builds.

Merge commit '460321cfe979459e3b78ba87694f29865d321612' into thread-next

NEWS and version update

Documentation: Updating roadmap as of end of 2024

CLI: Dumping forces new file creation instead of truncating.

CLI: show memory also displays cold pages

Minor changes by committer.

RPKI: Fix several errors in handling of Error PDU

Fix several errors including:
 - Unaligned memory access to 'Length of Error Text' field
 - No validation of 'Length of Encapsulated PDU' field
 - No validation of 'Error Code' field
 - No validation of characters in diagnostic message