slab: function to assert slab id empty

fixup: slab.c: Prevent running sl_free after slab_free

fixup! fixup! rt-attr.c: make ea class usecount atomic

fixup! rt-attr.c: make ea class usecount atomic

rt-attr.c: make ea class usecount atomic

fixup! fixup: rt-attr.c: (hopefully) solved deadlock in rehash.  The solution for rehash broke ea_storage_free logic, but now both look repaired.

fixup: rt-attr.c: (hopefully) solved deadlock in rehash.
 The solution for rehash broke ea_storage_free logic, but now both look repaired.

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.

Taming static checker: flow[64]_validate_cf() checks NULL data

This does not apply for the current code but if somebody chose to use
the flowspec validation functions for something totally broken, it may
unnecessarily crash.

Taming static checker: MPLS static label policy requires static handles

Taming static checker: Do not request bits on negative positions in prefixes

The code is actually called. It's harmless, yet confusing.

Taming static checker: Fixed hypothetical adata comparator crash

BFD session handling rework

The original implementation for BIRD 3 was rooted in the first
methods how I tried to go for multithreading and it had several flaws,
mostly incomprehensive notification and request pickup routines.
Also converting to a double-loop architecture where one of the
loops (low-latency) solely runs BFD socket communication, whereas
the other one does all the other shenanigans.

Proper thread group setup

Now the thread groups can be explicitly configured with their
latency and timing values.

IO loop: converted the thread group to a regular locked structure

IO loop: refactored thread and loop lists to tlists

Tlist enlisted allows const pointer argument

Make implicit function declaration an actual error

Fixed SAME_TYPE to work with obviously nonzero pointers without warnings

Taming static checker: rt_notify never sets net_addr to zero

Taming static checker: don't memcpy zero length

Merge commit '99c295e59' into thread-next

Merge commit '2679de7a3' into thread-next

Merge commit 'a8fa3f6b8' into thread-next

Merge commit 'deec84ca3' into thread-next

Merge commit '96ec6b42d' into thread-next

Merge commit '8d062e931' into thread-next

Merge commit '161aef353' into thread-next

Merge commit '38a422d48' into thread-next

Merge commit '6a55359b1' into thread-next

Table export: Relaxing too strict inconsistency assert

In case of refeeds, we may get old routes which we have not seen,
the table does not know that and the channel ingress is the right place
to detect it.

Bug introduced in commit 25557fceb08c8db6daead02a2f4b7a99d8a1f922
by Maria Matejka <mq@ucw.cz>, Mon Mar 3 19:48:58 2025 +0100

    Table export: Another inconsistency in refeeds

Doc: Replace <m/num/ with <m/number/

Both variants were used inconsistently, the second one is more frequent
and more expressive.

Doc: Add BGP reconfiguration section

Some changes by committer.

Doc: Minor fixes in BGP options

Doc: Add BGP protocol outline

Fixed refeed seqmap inconsistency

For some weird reason (probably oversight, as always), regular exports
were not marked in seq_map, leading to sus reexports and confusing
refeeds.

BGP: Fix reconfiguration of hostname option

The old code did not properly compare and update hostname strings,
causing BGP restarts during reconfigurations.

Nest: Fix locking of tables by channels

Channels that are down keep ptr on routing tables but do not keep them
locked. It is safe because the existence of tables depend on being
configured. But when a table is removed during reconfiguration, the
channel kept a dangling pointer since it fell down until it was removed.
This could be triggered by 'show protocols all' and other similar.

Change locking so that a channel kept a table locked for its whole
existence. The same change is already in BIRD 3.

Note that this is somewhat conceptually problematic as downed channels
do not keep resources. Also, other objects in specialized channels
(igp_table, base_table in bgp_channel, mpls_domain / mpls_range in
mpls_channel) are still locked only when channel is active, but for
them it is easier to keep track that they are not accessed when
they are deconfigured.

Table best export: asserting seqmap consistency

In case of some exports have been seen and others not, it makes no sense
for the second one to be seen if the first one was not seen.

RCU Unwinder stores where it came from last time

This information is vital for stuck situations where the
RCU Unwinder keeps longjumping away.

Table export: Another inconsistency in refeeds

When a route has been already sent to the channel and the refeed
runs because of a filter change or just because requested, the
old and new routes are the same which was actually not anticipated
by rt_notify_basic().

Filters: don't rewrite gw explicitly set by filters

If the originating protocol sets hostentry, it should be
overridden by filters and not rewrite gw.

This fixes #156. Issue #154 may need a similar fix.

Thanks to Peter Hutchinson for reporting.

Signed-Off-By: Katerina Kubecova <katerina.kubecova@nic.cz>

Fix source-specific routing in Bird 3

Commit 69d1ffde4c72 ("Split route data structure to storage (ro) /
manipulation (rw) structures.") changed rte->net from a pointer to a
'struct network' to a 'struct net_addr', but kept the address-of (&)
operator before casting to 'net_addr_ip6_sadr *' when sending a
source-specific route to the kernel.

Because 'struct network' had an embedded struct member (struct
fib_node), the address-of was needed to get back to a pointer to the
data, but with the change in the commit mentioned above, e->net is now a
straight pointer to the address.

The bug meant that the source prefixes passed to the kernel were
essentially garbage, leading to routes in the kernel like:

default from b74:9e05:0:1:d8cf:c000::/86 via fe80::1 dev eth0 proto bird metric 32 pref medium

Fix this by getting rid of the address-of operator.

Note by commiter: used our TYPE_CAST macro instead of plain typecast
to avoid this kind of problem in future.

Fixes: 69d1ffde4c72 ("Split route data structure to storage (ro) / manipulation (rw) structures.")
Signed-off-by: Toke Høiland-Jørgensen <toke@toke.dk>
Signed-off-by: Maria Matejka <mq@jmq.cz>

CI: Add hostname test to CI

Add option hostname for each protocol

Install comment updated by Maria

Updated router id docs to 4-byte integer.

Table export: fixed inconsistency in export_rejected_map

When updates arrived in such an order that the first one was rejected and
the second one got accepted, the export_rejected_map flag mistakenly
stayed set, leaking the route ID.

In the RA_OPTIMAL channel mode, there are consistency checks that at
most one route for a net has been accepted or rejected. After some time,
the leaked ID and bit in export_rejected_map caused spurious crashes in
asserts later in channel_notify_basic().

Thanks to NIX-CZ and Maiyun Zhang for reporting this.

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.

Added build for Debian 12

Needed right now for a customer. There is a better fix pending.

BGP export table src fix

When exchanging routes in BGP export table, we forgot to update
the src in cases of add path off. This led to falsely claiming another
origin of that route in export table dump and also holding protocols
in the flush state because of their srcs being kept in the export tables.

Flowspec: allowed TES_PARTIAL in validator link state

This probably slipped through some refactoring, TES_PARTIAL
is definitely a valid state for a flowspec link export.

Fix channel restart sequence

If channel goes start -> pause -> start, the original code crashed
but it's a valid sequence for protocol half-restart, going from UP
to START and then back UP.

Old config should not be freed early when reconfiguring in fast succession

Kernel: pause exports also on restart until scan is done

To save some time, exports are disabled to kernel when the initial scan
is running. The same should happen when kernel protocol is restarting.

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.

Update obsolete RFC 5575 to newer RFCs 8955 / 8956

Update the obsoleted RFC 5575 by newer RFCs 8955 (ipv4) and 8956 (ipv6)

Fix the flow6 label description and example

Fix error in example of direct protocol

Fix typo in docs

BGP: fix shutdown crash when dynamic peer is just connected

In some edge cases, the dynamic BGP starts but doesn't yet pick up
the socket from the peer, when it gets shut down, typically on
a complete shutdown. Fixing this to just close the socket, not assert
it being already picked up.

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.

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

Debian: Update Standards-Version to latest 4.7.0

Debian: Reformat with wrap-and-sort -bast

Debian: Add BuildDepends: ca-certificates

This should reportedly fix test issues on ARM.

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

Static: fixed ASPA reconfiguration

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

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

CI: Cleanup tests for single protocol builds

BFD and MRT can be built independently, only BMP requires BGP.

BMP: Cleanup keyword declarations

BFD: Fix missing keyword declarations

Some keywords were missing for BFD-only build.