mirrors/bird
mirrors/bird
0
0
Fork 0
mirror of https://gitlab.nic.cz/labs/bird.git synced 2024-11-08 12:18:42 +00:00
Code Releases Activity
oz-parametric-hashes
bird/lib
History
Ondrej Zajicek 0e39ed0004 Nest: Parametric network hashes 
Currently, all fib hash tables use the same hashing function. This leads
to a situation where feeding routes through a pipe from one table to
another causes significant number of collisions, as routes are fed in the
order of increasing hash values, but dst tables are sized based on the
number of stored routes.

The patch makes fib hashing function parametric and chooses random
parameter for each table. Also generally improves quality of hashing
functions.

Unfortunately, while this patch fixes the issue with initial collisions,
having different hashing functions leads to 2x slowdown of pipe feeding,
presumably due to worse cache behavior in dst tables. Also, the original
issue significantly affects just the initial part of feed, when the dst
table is small, so even ideal fix would not improve that much.

Therefore, no merge for this patch.
2022-06-14 18:15:30 +02:00
..
alloca.h Several minor fixes 2017-02-20 02:26:45 +01:00
birdlib.h Nest: Parametric network hashes 2022-06-14 18:15:30 +02:00
bitmap_test.c Lib: Basic and hierarchical bitmaps 2019-11-26 18:39:02 +01:00
bitmap.c Nest: Use bitmaps to keep track of exported routes 2019-11-26 18:39:25 +01:00
bitmap.h Nest: Use bitmaps to keep track of exported routes 2019-11-26 18:39:25 +01:00
bitops_test.c Birdtest: Replace BT_SUCCESS and BT_FAILURE with 1 and 0 2016-11-11 17:43:09 +01:00
bitops.c Initial commit on integrated BIRD 2015-11-05 12:48:52 +01:00
bitops.h Nest: Parametric network hashes 2022-06-14 18:15:30 +02:00
blake2-impl.h Lib: Add Blake2s and Blake2b hash functions 2021-06-06 16:26:58 +02:00
blake2-kat.h Lib: Add tests for blake2s and blake2b 2021-06-06 16:28:09 +02:00
blake2.h Lib: Add Blake2s and Blake2b hash functions 2021-06-06 16:26:58 +02:00
blake2b.c Lib: Add Blake2s and Blake2b hash functions 2021-06-06 16:26:58 +02:00
blake2s.c Lib: Add Blake2s and Blake2b hash functions 2021-06-06 16:26:58 +02:00
buffer_test.c Static: Minor overhaul 2017-03-09 13:47:00 +01:00
buffer.h Filter: Recursive filter iteration code 2021-02-07 19:21:42 +01:00
checksum_test.c Birdtest: Replace BT_SUCCESS and BT_FAILURE with 1 and 0 2016-11-11 17:43:09 +01:00
checksum.c unsigned [int] -> uint 2015-06-08 02:24:08 +02:00
checksum.h unsigned [int] -> uint 2015-06-08 02:24:08 +02:00
Doc Doc: Rename code documentation files back to Doc 2018-12-14 02:03:42 +01:00
event_test.c Timers: Fix tests after timer change 2017-12-07 13:49:27 +01:00
event.c Rate-limit scheduling of work-events 2021-03-12 15:35:56 +01:00
event.h Rate-limit scheduling of work-events 2021-03-12 15:35:56 +01:00
fletcher16_test.c Fletcher16 test fixed to work at bigendian architectures. 2020-04-05 01:15:26 +02:00
fletcher16.h OSPF: Redesign LSA checksumming 2015-05-01 14:40:56 +02:00
flowspec_test.c Flowspec: Label field should use numeric operator and not bitmask operator 2021-05-18 20:23:08 +02:00
flowspec.c Flowspec: Documentation update 2021-05-18 20:41:01 +02:00
flowspec.h Flowspec: Fix values for true/false operators 2021-05-14 18:44:52 +02:00
hash_test.c Birdtest: Replace BT_SUCCESS and BT_FAILURE with 1 and 0 2016-11-11 17:43:09 +01:00
hash.h Hash: mem_hash doesn't modify the memory, declared constant 2018-12-04 14:00:53 +01:00
heap_test.c Birdtest: Replace BT_SUCCESS and BT_FAILURE with 1 and 0 2016-11-11 17:43:09 +01:00
heap.h BFD work in progress. 2013-09-16 23:57:40 +02:00
idm.c Merge branch 'master' into int-new 2016-11-08 19:27:58 +01:00
idm.h Move ID allocator to a separate file and use it also in OSPF 2015-12-29 15:42:12 +01:00
ip_test.c Trie: Simplify network matching code 2021-11-13 21:11:18 +01:00
ip.c Lib: Allow use of 240.0.0.0/4 as a private range 2022-03-16 20:01:18 +01:00
ip.h Nest: Parametric network hashes 2022-06-14 18:15:30 +02:00
lists_test.c Lists: Replaced replace_node() by update_node() which is the only use of that function. 2020-05-01 15:19:12 +02:00
lists.c Lists: Replaced replace_node() by update_node() which is the only use of that function. 2020-05-01 15:19:12 +02:00
lists.h Babel: Seqno requests are properly decoupled from neighbors when the underlying interface disappears 2021-05-30 13:29:21 +02:00
mac_test.c Lib: Add tests for blake2s and blake2b 2021-06-06 16:28:09 +02:00
mac.c Nest: Allow MAC algorithms to specify min/max key length 2021-06-06 16:28:18 +02:00
mac.h Nest: Allow MAC algorithms to specify min/max key length 2021-06-06 16:28:18 +02:00
macro.h Macro: Added a bunch of dirty C preprocessor tricks 2018-05-29 11:53:51 +02:00
Makefile Lib: Add Blake2s and Blake2b hash functions 2021-06-06 16:26:58 +02:00
md5.c Add generic message authentication interface 2016-11-02 16:23:53 +01:00
md5.h Add generic message authentication interface 2016-11-02 16:23:53 +01:00
mempool.c Memory statistics split into Effective and Overhead 2021-11-27 22:54:15 +01:00
net.c Nest: Parametric network hashes 2022-06-14 18:15:30 +02:00
net.h Nest: Parametric network hashes 2022-06-14 18:15:30 +02:00
patmatch_test.c Birdtest: Replace BT_SUCCESS and BT_FAILURE with 1 and 0 2016-11-11 17:43:09 +01:00
patmatch.c Some consts for function arguments 2015-11-24 13:52:26 +01:00
printf_test.c Lib: Support for 64-bit numbers in bvsnprintf() 2019-10-09 17:53:23 +02:00
printf.c Lib: Support for 64-bit numbers in bvsnprintf() 2019-10-09 17:53:23 +02:00
resource.c Memory statistics split into Effective and Overhead 2021-11-27 22:54:15 +01:00
resource.h Memory statistics split into Effective and Overhead 2021-11-27 22:54:15 +01:00
resource.sgml Fixes for the programmer's manual. 2000-06-08 12:37:21 +00:00
sha1.c Add generic message authentication interface 2016-11-02 16:23:53 +01:00
sha1.h Add generic message authentication interface 2016-11-02 16:23:53 +01:00
sha256.c Add generic message authentication interface 2016-11-02 16:23:53 +01:00
sha256.h Add generic message authentication interface 2016-11-02 16:23:53 +01:00
sha512.c Add generic message authentication interface 2016-11-02 16:23:53 +01:00
sha512.h Add generic message authentication interface 2016-11-02 16:23:53 +01:00
slab.c Lib: Update alignment of slabs 2022-02-07 04:39:49 +01:00
slist_test.c Birdtest: Replace BT_SUCCESS and BT_FAILURE with 1 and 0 2016-11-11 17:43:09 +01:00
slists.c Unit Testing for BIRD 2016-11-09 16:36:34 +01:00
slists.h Temporary integrated OSPF commit. 2014-06-26 11:58:57 +02:00
socket.h IO: Support nonlocal bind in socket interface 2022-01-08 19:02:31 +01:00
string.h Nest: Allow specifying security keys as hex bytes as well as strings 2021-06-06 16:28:18 +02:00
strtoul.c Nest: Allow specifying security keys as hex bytes as well as strings 2021-06-06 16:28:18 +02:00
tbf.c Timers: Fix TBF and some last remains 2017-12-07 13:53:42 +01:00
timer.c Lib: Fix handling of buffers in timestamp formatting 2021-04-12 17:01:31 +02:00
timer.h Configuration strings are constant. 2020-04-09 15:37:14 +02:00
unaligned.h The MRT protocol 2018-11-20 17:45:35 +01:00
xmalloc.c unsigned [int] -> uint 2015-06-08 02:24:08 +02:00