| Age | Commit message (Collapse) | Author |
|---|
|
implementation for ART based on the singly-linked list of route
entries.
|
|
ok bluhm@
|
|
ok claudio@
|
|
ok bluhm@, dlg@, claudio@
|
|
net/rtable.c. This will ease the introduction of rtable_put().
Routing tables are mapped to a tuple (idx, af) so the public API
should as much as possible require these two keys.
ok dlg@
|
|
The routing table is not an optional component of the network stack
and initializing it inside the "routing domain" requires some ugly
introspection in the domain interface.
This put the rtable* layer at the same level of the if* level. These
two subsystem are organized around the two global data structure used
in the network stack:
- the global &ifnet list, to be used in process context only, and
- the routing table which can be read in interrupt context.
This change makes the rtable_* layer domain-aware and extends the
"struct domain" such that INET, INET6 and MPLS can specify the length
of the binary key used in lookups. This allows us to keep, or move
towards, AF-free route and rtable layers.
While here stop the madness and pass the size of the maximum key length
in *byte* to rn_inithead0().
ok claudio@, mikeb@
|
|
for ART.
While here sync the two remaining mix() macros.
ok chris@, dlg@
|
|
length of the key as argument.
This way every consumer of the radix tree has a chance to explicitly
initialize the shared data structures and no longer rely on another
subsystem to do the initialization.
As a bonus ``dom_maxrtkey'' is no longer used an die.
ART kernels should now be fully usable because pf(4) and IPSEC properly
initialized the radix tree.
ok chris@, reyk@
|
|
ART implementation.
ART (Allotment Routing Table) is a multibit-trie algorithm invented by
D. Knuth while reviewing Yoichi's SMART [0] (Smart Multi-Array Routing
Table) paper.
This implementation, unlike the one from the KAME project, supports
variable stride lengths which makes it easier to adapt the consumed
memory/speed trade-off. It also let you use a bigger first-level
table, what other algorithms such as POPTRIE [1] need to implement
separately.
Adaptation to the OpenBSD kernel has been done with two different data
structures. ART nodes and route entries are managed separately which
makes the algorithm implementation free of any MULTIPATH logic.
This implementation does not include Path Compression.
[0] http://www.hariguchi.org/art/smart.pdf
[1] http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p57.pdf
ok dlg@, reyk@
|
|
Code abusing the radix internals for the routing table should now
includes <net/rtable.h> and only deal with "struct rtentry".
Code using a radix tree for another purpose can still include
<net/radix.h>.
Inputs from and ok claudio@, mikeb@
|
