Bugfix

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

Refactor second_pass()

More comments

Minor changes

Bugfix

Set node status to NON_FIB when allocating additional nodes

Refactor aggregator_start()

Rename

Replace uint with u32

Rename

Formatting

Cleanup

Remove assertions

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

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

Refactor aggregator_init_trie()

Replace trie linpool with slab

Fix trie_remove_prefix() to work with pruned trie

Prune the trie after every aggregation

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

Refactor print_prefixes()

Rename

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.

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

Node can have selected bucket when entering third pass

Bugfix

Node can have selected bucket in the second pass

Bugfix

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

Bugfix

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

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

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.

Check consistency of the whole trie after every recalculation

Rename

Bugfix

Assign px_origin of target node in the third pass

Check trie consistency after every aggregation run

Add more comments

Fix comments

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

Fix comments

Add prefix to function names, 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

Rename

Switch order of expressions in condition testing

Replace assert with ASSERT_DIE

Merge branch 'ip-aggregator-new' of https://gitlab.nic.cz/labs/bird into ip-aggregator-new

Aggregator: Support prefix aggregation

(ready for code review)

IP: Getting and setting bits from ip_addr

Satanize the build to find sus behavior

Autoconf: Merge check and add compiler option to one macro

Bugfix

Rework documentation, add comments

Remove first pass, second pass now fills its function

Rename

Add another implementation of node_add_potential_bucket()

Fix formatting

memset removed nodes, add const and inline

Set ancestor without another if

Replace superfluous else-if with else

Remove logs

Rename

Add comments

Fix printing prefixes

Cleanup

Remove unnecessary else branches

Add parentheses to ternary operator expressions
Improve bug messages

Refactor deaggregate()

Add const

Rename aggregator_process_withdraw()

Rename choose_lowest_id_bucket()

Rename node_insert_potential_bucket()

Fix typo

Refactor

Small changes

Cleanup

Rename

Add assertions

Cleanup

Rename

trie_insert_prefix() now takes pointer to aggregator_proto

Rename

Use builtin popcount

Relocate code

Fix errors

Rewrite print_prefixes() using ip_addr instead of net_addr

Rewrite dump_trie() using ip_addr instead of net_addr

Rewrite construct_trie() using ip_addr instead of net_addr

Rewrite trie_process() using ip_addr instead of net_addr

Rewrite third_pass() using ip_addr instead of net_addr

Rewrite find_subtree_prefix() using ip_addr instead of net_addr

Rewrite trie_remove_prefix() using ip_addr instead of net_addr

Rewrite prepare_rte_withdrawal() using ip_addr instead of net_addr

Rewrite trie_insert_prefix() using ip_addr instead of net_addr

Add shift values for ipa bit operations

Rewrite create_route() using ip_addr instead of net_addr

Remove collect_prefixes()

Add macros for ipa bit operations

Small changes

Create default route in the thid pass

Initialize root node with NON_FIB status

Bugfix

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

Use net_addr at rte_withdrawal struct, plus small changes

Small changes