Implement a fast presix-set lookup. This magic trie is able to match a
authorclaudio <claudio@openbsd.org>
Fri, 7 Sep 2018 10:49:22 +0000 (10:49 +0000)
committerclaudio <claudio@openbsd.org>
Fri, 7 Sep 2018 10:49:22 +0000 (10:49 +0000)
commita02daadde29b2a2d13f5b1b0aec5558b755c1098
treec08a5e998513df5a2f551321b593cb14dafb88f8
parent7fdc021ee4c6df681ba7261bc939823142518930
Implement a fast presix-set lookup. This magic trie is able to match a
prefix addr/plen to a prefix-set spec addr/plen prefixlen min - max (a
prefix including prefixlen range). Every addr/plen pair is a node in the
trie and the prefixlen is added as a bitmask to those nodes.
For the lookup the any match is OK, there is no need to do longest or
best prefix matching.
Inspiration for this solution comes from the way bird implements this
which was done by Ondrej Zajicek santiago (at) crfreenet.org
OK benno@
usr.sbin/bgpd/Makefile
usr.sbin/bgpd/bgpd.c
usr.sbin/bgpd/bgpd.h
usr.sbin/bgpd/rde.c
usr.sbin/bgpd/rde.h
usr.sbin/bgpd/rde_filter.c
usr.sbin/bgpd/rde_trie.c [new file with mode: 0644]