Revert "Replace uint with u32"

This reverts commit e0f228bd98fde24458779e48658c999df92813f2.

Refactor find_subtree_prefix()

More comments

Many small improvements

Refactor creating new buckets, add bucket counter

Implement arbitrary sized bitmap

Refactor dump_trie()

Comments

Refactor add_bucket()

Refactor node_add_potential_bucket()

Remove get_new_bucket_id()

Use bool instead of int, cleanup

bucket_update() now takes net_addr instead of net

Add dump request to aggregator

Add dump_request_target

Refactor dump_trie()

Make immediate fixes so the code compiles

Some updates from Maria

Implement basics of prefix aggregation functionality

Fix previous version, aggregator is now stable but untested

Move trie initialization to aggregator_start()

Add new implementation of third_pass() and remove old implementation

Remove unused code

Fix aggregator_bucket_intersect(), add comments and fix naming

Refactor and fix aggregator_bucket_unionize()

Delete trie during aggregator shutdown

Fix const warning, add few comments

Fix aggregator_bucket_unionize()

The last two while loops were incorrectly placed inside the first while loop

Extend remove_node() with deleting root node

Add a few comments, print prefixes after aggregation

Fix argument order in several functions

Assign route bucket only to the last inserted node

Fix incorrect implementation of the third pass

Assign bucket of ancestor node to leaf node

Simplify delete_trie() function

Change order of parameters in a few functions

Add comments

Remove unused code

Use net_addr_ip4 instead of ip4_addr for printing prefixes

Fix how bucket for new leaf nodes is chosen

Rename constant

Remove unused code

Add assertions and general code improvements

Run ORTC algorithm

Create event to run ORTC algorithm exactly once

Do not assign bucket of any prefix to the root node

Do not discard bucket from internal nodes

Make pointer to aggregator bucket const

Add more assertions

Create default empty route for aggregation

Add script to prepare test case run

Remove unused code

Add small changes to test script

Bugfix

Due to wrong cast of void pointer, pointers to potential buckets
were compared and eventually sorted in wrong order, thus assigning
wrong buckets to trie nodes.
This caused some trie nodes to stay in trie even though they should
have been removed. Consequently, trie contained superfluos prefixes
after the algorithm finished.

Since pointers were never dereferenced, only compared by their numeric
values in the comparator function, program did not crash (even though
pointers could be NULL because of the incorrect cast to double pointer
and single dereference).

Remove configuration rule enforcing aggregation on NET

Refactor printing prefixes in trie

Remove const from aggregator_bucket pointers in trie nodes

Collect prefixes in trie after aggregation and export new routes

Run correct aggregation (by nets or by attributes) according to configuration

Refactor functions for comparing buckets and computing union and intersection of buckets

Change a few logs

Create and assign net to default route

Rename variables of type protocol in order to be consistent with the rest of the codebase

Add debugging logs

Clear bit after setting it when collecting prefixes from trie

Bugfix

Program crashed when disabling aggregation protocol or shutting the daemon down.
Shutdown procedure attempted to remove the first route (which is the last that
was inserted) by different key than one by which it was inserted into the table.
They key is computed from net and src of each route. It turned out that src of
the last route was inadvertently changed.

Use idiomatic functions for manipulating net_addr, remove unnecessary use of alloca

Use %N for printing net addresses

Create separate functions for inserting IP4 and IPv6 prefixes into trie

Create default net based on adress type

Collect and print prefixes according to address type

Check correct address types during aggregation configuration

Remove code duplication

Add small check to the first pass of ORTC algorithm

Add variable to track node depth in the trie

Remove debugging logs

Add modified implementation of the first pass

Add more assertions

Remove debugging logs

Use refactored first pass function

Don't schedule aggregation as event but run it at the protocol feed end

Construct trie only after protocol feed ends

Rename

Rename

Make small changes to increase readability

Add logs and declarations, remove unused code

Reorder parameters to stay consistent with the codebase

Replace for loops with memcpy

Replace for loops with memcpy

Replace goto with else

Remove unused code

Use memcpy with size argument based on destination size

Add assertions

Backport settle timer from v3

Move aggregation algorithm to separate function

Replace goto with else

Add settle timer

Backport SKIP_BACK with type control from v3

Fix incorrect use of SKIP_BACK

Don't run aggregation on feed end

Compare pointers to NULL using implicit conversion to bool

Use sl_allocz() for node allocation

Ignore updates if protocol is not UP

Change logs

Run aggregation only once (temporary solution)

Add more assertions

Change slabs for linpools

Remove delete_trie()

Move trie initialization to separate function

Run aggregation on feed end from src channel and request feeding after receiving update

Rename

Set aggregation mode in the configuration file

Request feed when settle timer triggers and initialize trie just before aggregation

Kick settle timer when receiving updates in rt_notify()

Modify aggregator_start() and shutdown()

Add get_status() function

Bugfix

Small changes

Remove old first_pass()

Small changes, add assert

Rename

Change order of parameters in create_route()

Add comments

Remove unused includes

Small changes

Add protocol cleanup

Add counters of nodes with assigned bucket

Add unique ID to buckets and compare them by this ID

Change order of parameters, make aesthetic changes

Add logging option to log prefix aggregation progress

Update time before and after aggregation

Write documentation

Add ancestor pointer to enable faster lookup of ancestor with non-null bucket

Split third pass function into two functions
(in order to get rid of redundant condition testing)

Avoid unnecessary allocation of nodes in the first pass

Add logs about number of nodes

Bugfix

During implementation of the new mechanism of storing potential buckets it was
found that aggregator allocates more than 4000 buckets despite routes in the
configuration file being grouped to approximately 200 buckets.

Upon closer inspection it became clear that tmp_bucket in aggregator_rt_notify()
was allocated in the linpool when it should have been allocated on stack.
Moreover, tmp_bucket was allocated without additional space for aggr_data.
These data were never copied from tmp_bucket to new_bucket.

This was the source of false negative results of HASH_FIND. Buckets are compared
not only by their hashes, but also lists of aggr_data. Because same_val_list()
was reading beyond allocated memory, buckets were never equal. HASH_FIND
therefore returned NULL, which prompted aggregator to create many more buckets
despite already existing buckets with the same hash.

Delete unnecessary code

Implement bitmaps for storing potential buckets

Log time to measure duration of individual aggregation phases

Use hmap for assigning bucket IDs

Rename

Refactor

Remove settle timer

node_insert_potential_bucket() accepts bucket pointer, not an ID

Second pass doesn't need protocol

Add selected bucket and FIB status to node

Modify merge_potential_buckets() to return whether the target set has changed

Do not delete trie after finishing aggregation

Fix wording in comments

trie_insert_prefix() now allows updating a bucket of existing prefix

Create function to choose bucket with the lowest ID from the set of potential buckets

Add more assertions

Silence unused variable warning

Don't assign selected bucket to imaginary node in the third pass

Cleanup

Small changes

Check ancestors after aggregation

choose_lowest_id_bucket() now returns the bucket, it does not assign it

Rename bucket to original_bucket

Do not delete potential buckets in the third pass

Root has a depth 0 instead of 1

Rewrite function for allocating bucket IDs

Implement function to process incremental update

Process incremental updates in rt_notify()

Add dumping trie

Small additions

Trie dump now contains all node information

Add prefix origin

Implement processing of incremental updates

Incorporate updates into trie

Small changes

Leaves don't have to be IN_FIB since we are not removing NON_FIB leaves anymore

Delete parent pointer when removing node from trie

Set px_origin where it makes sense

Recycle bucket ID when bucket is empty

Bugfix

Add comments

Increase readability of old code

Extend logging functions

Implement removing prefix from the trie

Move code around

Original prefix always keeps its status

Remove unused code

Rename

Add more checks

Overwrite removed nodes with garbage values

Implement deaggregation

Incorporate updates to the trie

Deaggregation runs on the whole subtree

Incorporate withdrawals to the trie

Move static variable to the top

Rename

 Add find_subtree_prefix()

Keep track of current prefix during third pass

Add comments

Add assertions

Cleanup

Rename

Small changes

Implement route withdrawal

trie_remove_prefix() now removes route from the table

Process route withdrawals caused by incorporating updates to the trie

Do not set IN_FIB status for newly added prefixes

FIB status now truly reflects whether prefix is in export table or not.
Based on the change of FIB status, third pass can now decide whether
the export or route removal is needed.

Cleanup

Small changes

Use net_addr at rte_withdrawal struct, plus small changes

Bugfix

Export new route when node status is changing from NON_FIB or UNASSIGNED to IN_FIB

Initialize root node with NON_FIB status

Create default route in the thid pass

Small changes

Add macros for ipa bit operations

Remove collect_prefixes()

Rewrite create_route() using ip_addr instead of net_addr

Add shift values for ipa bit operations

Rewrite trie_insert_prefix() using ip_addr instead of net_addr

Rewrite prepare_rte_withdrawal() using ip_addr instead of net_addr

Rewrite trie_remove_prefix() using ip_addr instead of net_addr

Rewrite find_subtree_prefix() using ip_addr instead of net_addr

Rewrite third_pass() using ip_addr instead of net_addr

Rewrite trie_process() using ip_addr instead of net_addr

Rewrite construct_trie() using ip_addr instead of net_addr

Rewrite dump_trie() using ip_addr instead of net_addr

Rewrite print_prefixes() using ip_addr instead of net_addr

Fix errors

Relocate code

Use builtin popcount

Rename

trie_insert_prefix() now takes pointer to aggregator_proto

Rename

Cleanup

Add assertions

Rename

Cleanup

Small changes

Refactor

Fix typo

Rename node_insert_potential_bucket()

Rename choose_lowest_id_bucket()

Rename aggregator_process_withdraw()

Add const

Refactor deaggregate()

Add parentheses to ternary operator expressions
Improve bug messages

Remove unnecessary else branches

Cleanup

Fix printing prefixes

Add comments

Rename

Remove logs

Replace superfluous else-if with else

Set ancestor without another if

memset removed nodes, add const and inline

Fix formatting

Add another implementation of node_add_potential_bucket()

Rename

Remove first pass, second pass now fills its function

Rework documentation, add comments

Bugfix

Replace assert with ASSERT_DIE

Switch order of expressions in condition testing

Rename

Split aggregator.c into two files

aggregator.c now contains main protocol functionality, evaluation of route
attributes and operations with buckets

trie.c now contains prefix aggregation and functions that operate on the trie

Add prefix to function names, rename

Fix comments

Fix

Bugfix

Do not add potential bucket during deaggregation, this is done in the second
pass now that the first pass is omitted.
Change node status to FILLER if it's not ORIGINAL during deaggregation.

Fix comments

Add more comments

Check trie consistency after every aggregation run

Bugfix

Assign px_origin of target node in the third pass

Rename

Check consistency of the whole trie after every recalculation

Bugfix

Fix aggregator_trie_remove_prefix()

Never change FIB status except in the third pass. FIB status is decided only
by the algorithm and no one else. Never withdraw route except in the third pass.
Again, route exports and withdrawals are solely the algorithm's responsibility.
Keep selected bucket because it will be needed for route withdrawal in the
third pass.

Bugfix

When removing prefix from the trie, prefix node can still be IN_FIB and
it will be a filler because it is no longer original.

Bugfix

IN_FIB node can be a filler if it was previously original and was removed
from the trie

Bugfix

Do not delete selected bucket during deaggregation, it will be needed
in the third pass for route withdrawal

Bugfix

Node can have selected bucket in the second pass

Bugfix

Node can have selected bucket when entering third pass

Bugfix

When removing prefix from the trie, we need to find the closest IN_FIB
ancestor of the updated node. However, since the updated node may still
have IN_FIB status, we need to check that the target node and updated node
are not the same.

This bug manifested itself in a following way. After running aggregator with
configuation A and reconfiguring it to configuration B, routes from A, which
should have been removed, were still present in the routing table. This was
caused by old prefixes not being removed from the trie.

Because of the missing condition that the updated node and its ancestor are not
the same, trie recalculation was called on prefix nodes which were, in most
cases, leaves. Therefore, trie was not updated at all. All prefixes were still
present in the trie, and thus in the routing table as well.

Bugfix

This was another bug tricky to find.
It manifested in a following way. After running aggregator with configuration A,
reconfiguring it to B (this works now as it was fixed in the previous commit)
and reconfiguring back to A, no routes from A were exported to the routing
table, despite prefixes being present in the trie.

It was found that aggregator_bucket_update() is correctly called, however, it
returned on the first "if", meaning that bucket was empty. It was found that
there were two different buckets with the same ID. The culprit turned out to
be freeing bucket ID when the bucket becomes empty in rt_notify() due to
reconfiguration. When that happens, freed ID will be used again for new bucket
created during reconfiguration.
However, the bucket pointer in the bucket list was never updated and pointer to
old bucket was still kept there at position [ID]. When the aggregator decided
for creating new route after reconfiguring back to A, it found bucket pointer
by its ID. However, this pointer was actually pointer to an empty bucket.
This triggered early return from aggregator_bucket_update(), which means that
control flow never reached the point where new route could be exported.
Either way, the empty bucket means that rte_update2() would be called with
wrong arguments and route export would still be unsuccessful.

Rename

Refactor print_prefixes()

Refactor: merge update_prefix() and withdraw_prefix() into one function

Prune the trie after every aggregation

Fix trie_remove_prefix() to work with pruned trie

Replace trie linpool with slab

Refactor aggregator_init_trie()

Don't deaggregate trie as a separate step, do it during second pass

Remove assertions

If prefix node was pruned from the trie, these assertions may not hold
for returned node

Cleanup

Formatting

Rename

Replace uint with u32

Rename

Refactor aggregator_start()

Bugfix

Set node status to NON_FIB when allocating additional nodes

Minor changes

More comments

Refactor second_pass()

Bugfix

When pruning the trie, do not remove nodes of original prefixes

maria's notes

Fixes

some todos

Cleanup, rename

Do not allocate any nodes in aggregator.c, initialize root node in trie.c

Run whole aggregation after initial feed, recompute for updates received after that

Refactor

Refactor second pass

Refactor dump_trie()

Small refactor, add comments

Refactor propagate_and_merge()

Refactor group_prefixes()

Extend documentation

BSD: Silence some warnings

BSD: Fix build on NetBSD

Newer NetBSD versions removed RTF_LLINFO and added RTF_LLDATA.
In FreeBSD, RTF_LLINFO is obsolete, but still defined.

CI: Add builds on new NetBSD workers

BGP: Fix crash when incoming connection for disabled protocol arrives

The function bgp_find_proto() may return a protocol in DOWN state, but
ao.keys (as most protocol data) are only valid in non-DOWN state.

Silence some warnings

CI: Add builds on new OpenBSD workers

CI: Add FreeBSD 14 and netlink builds for FreeBSD 13 and 14.

CI: Do not rebuild Docker images for test builds for new branches

New branch considers all files changed. We don't want to rebuild all
docker images for new branches; that's just a waste of time and energy.

There is a better way for future -- a much better fine-grained control
may be obtained by running secondary pipelines.

fixes #212

cli/commands: Help for multiple word command did not show properly.

Possible commands are stored as keywords, each keyword has its own structure.
The last acceptable keyword structure contains string with hint. But when the hint was printed only direct child
of the base keyword was considered. If it was multi keyword command, the first child did not carry any hint to print,
so it was ignored.

Now, if we don't find a hint in a child, we recursively search in grandchildren.

CI: enable Fedora 42: image, build, package.

Docker: added lost docker file for Fedora 42.

Docker: lost files for OpenSuse 15.4, 15.5

Doc: Minor corrections in README and INSTALL

- Licence to License - also in code comments.
- copyright date until now.
- updated license text from gnu.org
- added command to build bird documentation.

CI: Fix missing srcdir in path to tools/version

CI: fix test collisions between branches (again)

The build-netlab job was side-effecting the test-* jobs,
and if for some reason Gitlab scheduled build-netlab before
other pipeline's test-* jobs finished, these jobs got a wrong
binary, possibly failing. Solved by using explicit artifacts, which is
not the fastest way to do this (we could keep the binaries named there)
but it's the gitlab-right way to do this.

(Re-committed, was accidentally removed by one of previous commits)

NEWS and version update

Release tools: fix several bugs in version number detection

Forgetting to do proper checks, I merged a buggy release tools update
not detecting the right version (mostly if tagged).

Doc singlepage: add bold handler

Docker build machinery: a little bit of documentation

CI: Massive update of build and test runners

Fixed and added current distros, deleted certain EOL distros,
sorted things in the CI file.

With some heavy lifting and comments by Maria.

Signed-Off-By: Maria Matejka <mq@jmq.cz>

Fix dependecy issue with bs4 on legacy distros

Fix getting the version tag. Now it should also support older versions of git

Readd CentOS 7 to CI build and package process

Add archived repositories for CentOS 8

Remove links to czech repos in EOL debians and add archived repos for debian 9

use python venv for debian

Update build and package targets

Fedora builds for 32-41, Debian up to 12, Ubuntu up to 24.10.

Includes autorebuilder if a Dockerfile changes.

The CI file is obnoxiously boilerplaty. TODO: generate it from a list?

Releasing: a new tgz generator script

Also version detection is done by a separate script, not a magic line in
the Makefile.

CI: Added the release confirm metajob

Separate documentation autobuild

This is expected to hit a webhook inside our CI to trigger
automatic deployment to testweb.

Doc: autoconvertor of our SGML to Markdown

Some minor changes were done in the original documentation to allow for
easier conversion, and also to make the documentation a little bit more
strictly valid.

CI: fix test collisions between branches

The build-netlab job was side-effecting the test-* jobs,
and if for some reason Gitlab scheduled build-netlab before
other pipeline's test-* jobs finished, these jobs got a wrong
binary, possibly failing. Solved by using explicit artifacts, which is
not the fastest way to do this (we could keep the binaries named there)
but it's the gitlab-right way to do this.

BGP: Forbid TCP-AO on dynamic BGP sessions

Reconfiguration does not work properly for this case, disable it for now.

TCP-AO revised version

Reworked and finalized version of TCP-AO.

TCP-AO implementation based on RFC 5925

Uses Linux TCP-AO. Tested against JUNIPER.

BFD: Fix crash related to reconfiguration and passwords

Any change in BFD iface configuration should trigger session
reconfiguration, as config is copied into the bfd_session structure
and not just accessed through the bfd_iface structure.

As bfd_session now contains a pointer to the password list allocated
from the configuration, forgetting to update the bfd_session causes
use-after-free.

Thanks to Lexi Winter for the bugreport.

CI: Re-add bgp-rs-singletab

(was accidentally removed by the previous commit)

Babel: Add option 'next hop prefer' to control next hops of IPv4 routes

By default, the Babel protocol will advertise IPv4 routes with an IPv6
next hop address only on interfaces which do not have an IPv4 address.

Add option 'next hop prefer' to control whether IPv4 routes should use
IPv4 or IPv6 next hop when both are available.

Based on the patch from Chris Webb, thanks!

Filter: Add tests for 'case' expressions

CI: Add bgp-rs-singletab

(For some reason, it is not enabled in CI)

Docs: new link local format added to BGP outline.

BGP: Add option to specify format of link-local next hop

When a BGP session is established using link-local next hop addresses,
there is no global IPv6 address for next hop. Implementations differ on
how to encode such next hop. This leads to interoperability problems.

Add the option 'link local next hop format' to specify which format to
use when encoding such next hops.

Based on a patch from Andrey V. Elsukov and Georgy Kirichenko, submitted
by Aleksandr Stepanov, thanks!

BGP: Fix missing case for decoding link-local next hops in VPN SAFI

CI: Remove broken package builds

Some package build tests were broken due to apkg changes,
disable them temporarily.

Docs: Changed "&lt;", "&gt;" to "<",">" in <code>.

Docs: Replaced "M>" with "m>" (maintainability).

Docs: Replaced "<M>num</M>" with "<M>number</M>".

Docs: Replaced "&lt;num&gt;" with &lt;number&gt;.

l3vpn.c: set proper flag when setting EA_BGP_EXT_COMMUNITY

ASPA: added official tests

from Sriram Kotikalapudi's presentation for IETF 122.

Log: Fix handling of L_BUG messages

Due to an off-by-one error, L_BUG messages (e.g. from ASSERT()) were
handled as L_DBG messages and therefore ignored by our CI.

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

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.

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.

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

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.

CI: test building single protocols

Several users build BIRD with excluded support for protocols they don't
need. Testing single-protocol builds; the assumption is that if single
protocols and all protocols are buildable, then possibly any reasonable
combination is buildable as well.

Minor change by committer.

Fixed several tests which needed static protocol

Now they need device protocol which is always built.

Disabling filter test unless needed protocols are configured

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.

Doc: Fix protocol outline in RPKI

Protocol outlines should not contain specific values.

Also fix some space intendation in code sections.