summaryrefslogtreecommitdiff
AgeCommit message (Collapse)Author
2022-02-06Nest: Implement locking of prefix tries during walksOndrej Zajicek (work)
The prune loop may may rebuild the prefix trie and therefore invalidate walk state for asynchronous walks (used in 'show route in' cmd). Fix it by adding locking that keeps the old trie in memory until current walks are done. In future this could be improved by rebuilding trie walk states (by lookup for last found prefix) after the prefix trie rebuild.
2022-02-06Nest: Implement prefix trie pruningOndrej Zajicek (work)
When rtable is pruned and network fib nodes are removed, we also need to prune prefix trie. Unfortunately, rebuilding prefix trie takes long time (got about 400 ms for 1M networks), so must not be atomic, we have to rebuild a new trie while current one is still active. That may require some considerable amount of temporary memory, so we do that only if we expect significant trie size reduction.
2022-02-06Trie: Add prefix counterOndrej Zajicek (work)
Add counter of prefixes stored in trie. Works only for 'restricted' tries composed of explicit prefixes (pxlen == l == h), like ones used in rtables.
2022-02-06Doc: Describe routing table optionsOndrej Zajicek (work)
2022-02-06BGP: Implement flowspec validation procedureOndrej Zajicek (work)
Implement flowspec validation procedure as described in RFC 8955 sec. 6 and RFC 9117. The Validation procedure enforces that only routers in the forwarding path for a network can originate flowspec rules for that network. The patch adds new mechanism for tracking inter-table dependencies, which is necessary as the flowspec validation depends on IP routes, and flowspec rules must be revalidated when best IP routes change. The validation procedure is disabled by default and requires that relevant IP table uses trie, as it uses interval queries for subnets.
2022-02-06Nest: Add routing table configuration blocksOndrej Zajicek (work)
Allow to specify sorted flag, trie fla, and min/max settle time. Also do not enable trie by default, it must be explicitly enabled.
2022-02-06Nest: Add convenience functions to check rtable net typeOndrej Zajicek (work)
2022-02-06Nest: Avoid unnecessary net_format() in 'show route' commandOndrej Zajicek (work)
When output of 'show route' command was generated, the net_format() was called for each network prematurely, even if the result was not needed. Fix the code to call net_format() only when needed. This makes queries that process many networks but show only few (e.g. 'show route where ..', or 'show route count') much faster (like 5x - 10x faster).
2022-02-06Nest: Add trie iteration code to 'show route'Ondrej Zajicek (work)
Add trie iteration code to rt_show_cont() CLI hook and use it to accelerate 'show route in <addr>' commands using interval queries.
2022-02-06Nest: Implement 'show route in <addr>' commandOndrej Zajicek (work)
Implement 'show route in <addr>' command, which shows all routes in networks that are subnets of given network. Currently limited to IP network types.
2022-02-06Nest: Attach prefix trie to rtable for faster LPM and interval queriesOndrej Zajicek (work)
Attach a prefix trie to IP/VPN/ROA tables. Use it for net_route() and net_roa_check(). This leads to 3-5x speedups for IPv4 and 5-10x speedup for IPv6 of these calls. TODO: - Rebuild the trie during rt_prune_table() - Better way to avoid trie_add_prefix() in net_get() for existing tables - Make it configurable (?)
2021-12-02Trie: Clarify handling of less-common net typesOndrej Zajicek (work)
For convenience, Trie functions generally accept as input values not only NET_IPx types of nets, but also NET_VPNx and NET_ROAx types. But returned values are always NET_IPx types.
2021-11-26Trie: Implement longest-prefix-match queries and walksOndrej Zajicek (work)
The prefix trie now supports longest-prefix-match query by function trie_match_longest_ipX() and it can be extended to iteration over all covering prefixes for a given prefix (from longest to shortest) using TRIE_WALK_TO_ROOT_IPx() macro.
2021-11-19Trie: Implement trie walking codeOndrej Zajicek (work)
Trie walking allows enumeration of prefixes in a trie in the usual lexicographic order. Optionally, trie enumeration can be restricted to a chosen subnet (and its descendants).
2021-11-13Trie: Simplify network matching codeOndrej Zajicek (work)
Introduce ipX_prefix_equal() and use it to simplify network matching code.
2021-09-25Filter: Add prefix trie benchmarksOndrej Zajicek (work)
Add trie tests intended as benchmarks that use external datasets instead of generated prefixes. As datasets are not included, they are commented out by default.
2021-09-25Filter: Improve prefix trie testsOndrej Zajicek (work)
Add tests explicitly matching insides and outsides of trie and update tests to do testing of both IPv4 and IPv6 tries.
2021-09-25Filter: Update trie documentationOndrej Zajicek (work)
2021-09-25Filter: Fix trie testOndrej Zajicek (work)
Generated prefixes must be valid.
2021-09-25Filter: Faster prefix setsOndrej Zajicek (work)
Use 16-way (4bit) branching in prefix trie instead of basic binary branching. The change makes IPv4 prefix sets almost 3x faster, but with more memory consumption and much more complicated algorithm. Together with a previous filter change, it makes IPv4 prefix sets about ~4.3x faster and slightly smaller (on my test data).
2021-06-17Nest: Clean up main channel handlingOndrej Zajicek (work)
Remove assumption that main channel is the only channel.
2021-06-14Nest: Fix export of tmpattrs through pipesOndrej Zajicek (work)
Pipes copy the original rte with old values, so they require rte to be exported with stored tmpattrs. Other protocols access stored attributes using eattr list, so they require rte to be exported with expanded tmpattrs. This is temporary hack, we plan to remove whoe tmpattr mechanism. Thanks to Paul Donohue for the bugreport.
2021-06-14Revert "Nest: Fix export of tmpattrs through pipes"Ondrej Zajicek (work)
This reverts commit f8e273b5e7a3c721f4a30cf27a0b4fe54602e83f.
2021-06-14Nest: Fix export of tmpattrs through pipesOndrej Zajicek (work)
In most cases of export there is no need to store back temporary attributes to rte, as receivers (protocols) access eattr list anyway. But pipe copies the original rte with old values, so we should store tmpattrs also during export. Thanks to Paul Donohue for the bugreport.
2021-06-11CI: Allow Babel testsOndrej Zajicek (work)
2021-06-09Nest: Allow both 'password' and 'key' keywords for authentication keysOndrej Zajicek (work)
2021-06-09Babel: Simplify auth expirationOndrej Zajicek (work)
Just use hello_expiry for that, keep init_expiry for initial unauthentized neighbors.
2021-06-06Nest: Fix password list parsing codeOndrej Zajicek (work)
One of previous patches broke password list parsing code, fix that.
2021-06-06Lib: Fix static assert macroOndrej Zajicek (work)
2021-06-06Babel: Add MAC authentication support - updateOndrej Zajicek (work)
Some cleanups and bugfixes to the previous patch, including: - Fix rate limiting in index mismatch check - Fix missing BABEL_AUTH_INDEX_LEN in auth_tx_overhead computation - Fix missing auth_tx_overhead recalculation during reconfiguration - Fix pseudoheader construction in babel_auth_sign() (sport vs fport) - Fix typecasts for ptrdiffs in log messages - Make auth log messages similar to corresponding RIP/OSPF ones - Change auth log messages for events that happen during regular operation to debug messages - Switch meaning of babel_auth_check*() functions for consistency with corresponding RIP/OSPF ones - Remove requirement for min/max key length, only those required by given MAC code are enforced
2021-06-06Babel: Add MAC authentication supportToke Høiland-Jørgensen
This implements support for MAC authentication in the Babel protocol, as specified by RFC 8967. The implementation seeks to follow the RFC as close as possible, with the only deliberate deviation being the addition of support for all the HMAC algorithms already supported by Bird, as well as the Blake2b variant of the Blake algorithm. For description of applicability, assumptions and security properties, see RFC 8967 sections 1.1 and 1.2.
2021-06-06Babel: Refactor TLV parsing code for easier reuseToke Høiland-Jørgensen
In preparation for adding authentication checks, refactor the TLV walking code so it can be reused for a separate pass of the packet for authentication checks.
2021-06-06Nest: Allow MAC algorithms to specify min/max key lengthToke Høiland-Jørgensen
Add min/max key length fields to the MAC algorithm description and validate configured keys before they are used.
2021-06-06Nest: Allow specifying security keys as hex bytes as well as stringsToke Høiland-Jørgensen
Add support for specifying a password in hexadecimal format, The result is the same whether a password is specified as a quoted string or a hex-encoded byte string, this just makes it more convenient to input high-entropy byte strings as MAC keys.
2021-06-06Lib: Add tests for blake2s and blake2bToke Høiland-Jørgensen
Import the blake2-kat.h header with test vector output from the blake reference implementation, and add tests to mac_test.c to compare the output of the Bird MAC algorithm implementations with that reference output. Since the reference implementation only has test vectors for the full output size, there are no tests for the smaller-sized output variants.
2021-06-06Lib: Add Blake2s and Blake2b hash functionsToke Høiland-Jørgensen
The Babel MAC authentication RFC recommends implementing Blake2s as one of the supported algorithms. In order to achieve do this, add the blake2b and blake2s hash functions for MAC authentication. The hashing function implementations are the reference implementations from blake2.net. The Blake2 algorithms allow specifying an arbitrary output size, and the Babel MAC spec says to implement Blake2s with 128-bit output. To satisfy this, we add two different variants of each of the algorithms, one using the default size (256 bits for Blake2s, 512 bits for Blake2b), and one using half the default output size. Update to BIRD coding style done by committer.
2021-06-06sysdep: Add wrapper to get random bytes - updateOndrej Zajicek (work)
Simplify the code and fix an issue with getentropy() return value.
2021-06-06sysdep: Add wrapper to get random bytesToke Høiland-Jørgensen
Add a wrapper function in sysdep to get random bytes, and required checks in configure.ac to select how to do it. The configure script tries, in order, getrandom(), getentropy() and reading from /dev/urandom.
2021-06-01BGP: Ensure that freed neighbor entry is not accessedOndrej Zajicek (work)
Routes from downed protocols stay in rtable (until next rtable prune cycle ends) and may be even exported to another protocol. In BGP case, source BGP protocol is examined, although dynamic parts (including neighbor entries) are already freed. That may lead to crash under some race conditions. Ensure that freed neighbor entry is not accessed to avoid this issue.
2021-05-30Babel: Seqno requests are properly decoupled from neighbors when the ↵Maria Matejka
underlying interface disappears When an interface disappears, all the neighbors are freed as well. Seqno requests were anyway not decoupled from them, leading to strange segfaults. This fix adds a proper seqno request list inside neighbors to make sure that no pointer to neighbor is kept after free.
2021-05-26OSPF: Fix OSPFv3 in IPv4 mode with multiple areasOndrej Zajicek (work)
Some area handling code got confused by IPv4 setup in OSPFv3 mode.
2021-05-20CI: Try different locale for Centos 7Ondrej Zajicek (work)
2021-05-20CI: Package build for more platformsMatous Holinka
.gitlab-ci.yml: + pkg targets for some distros added + artifacts added - some distros were commented out (due to errors). misc/docker/*: + Dockerfiles updated with the necessary packages.
2021-05-19CI: Try utf-8 locale to workaround apkg issueOndrej Zajicek (work)
2021-05-19CI: Build documentation where tools are availableOndrej Zajicek (work)
2021-05-19CI: Update docker images for building of documentationOndrej Zajicek (work)
2021-05-19Pkg: Enable docs subpackage for DebianOndrej Zajicek (work)
2021-05-19CI: Test of apkg buildOndrej Zajicek (work)
Also temporarily disable cf-ospf-auth, as there is some problem with it.
2021-05-19Tools: Improve make-dev-archiveOndrej Zajicek (work)
Use git-archive to avoid unrelated and temporary files and fix some minor issues (e.g. dependency on bash as system shell).
2021-05-19ubuntu: use any init-system-helpersJakub Ružička
init-system-helpers (>= 1.56~) can't be satisfied on: * Ubuntu 18.04 (1.51) * Ubuntu 16.04 (1.29) * Debian 9 (1.48) Remove the specific version requirement in order to enable build on older platforms.