summaryrefslogtreecommitdiffstats
path: root/sys/net/art.h (follow)
Commit message (Collapse)AuthorAgeFilesLines
* include of netinet/in.h here is incorrect, because net/route.h will pullderaadt2021-03-021-2/+1
| | | | | excessive types into scope. ok claudio
* Document art locking.mpi2020-11-121-9/+15
| | | | ok denis@, jmatthew@
* Add feature to force the selection of source IP addressdenis2020-10-291-1/+3
| | | | | | | Based/previous work on an idea from deraadt@ Input from claudio@, djm@, deraadt@, sthen@ OK deraadt@
* Make ART data structure definitions visible to userland, in order to fixmpi2019-03-311-1/+33
| | | | | | netstat(1) inspection of routing tables. From Naoki Fukaumi, ok yasuoka@
* Prevent a MP race in rtable_lookup().mpi2017-02-281-6/+5
| | | | | | | | | | | | | | If an ART node is linked to multiple route entries, in the MPATH case, it is not safe to dereference ``an_dst''. This non-refcounted pointer can be changed at any time by another CPU. So get rid of the pointer and use the first destination of a route entry when comparing sockaddrs. This allows us so remove a pointer from 'struct art_node' and save 5Mb of memory in an IPv4 fullfeed. ok jmatthew@, claudio@, dlg@
* Make the art interface a bit more generic by not depending on sockaddrclaudio2017-01-231-7/+7
| | | | | in the functions. This way it can be used for other trees as well. OK mpi@ phessler@
* use a per-table rwlock to serialize ART updates and walks, rather thanjmatthew2016-08-301-1/+4
| | | | | | taking the kernel lock. ok mpi@ dlg@
* Convert the links between art data structures used during lookups into srps.jmatthew2016-06-141-4/+5
| | | | | | | | | | | | | art_lookup and art_match now return an active srp_ref, which the caller must leave when it's done with the returned route (if any). This allows lookups to be done without holding any locks. The art_table and art_node garbage collectors are still responsible for freeing items removed from the routing table, so they now use srp_finalize to wait out any active references, and updates are done using srp_swap operations. ok dlg@ mpi@
* defer the freeing of art tables and nodes to a task.dlg2016-06-031-2/+7
| | | | | | | | | | | | | | | | | this will allow us to sleep in srp_finalize before freeing the memory. the defer is done by putting the tables and nodes on a list which is serviced by a task. the task removes all the entries from the list and pool_puts them. the art_tables gc code uses at_parent as its list entry, and the art_node gc code uses a union with the an_dst pointer. both at_parent and an_dst are only used when theyre active as part of an art data structure, and are not used in lookups. once the art is done with them we can reuse these pointers safely. ok mpi@
* Keep all pools in the same place.mpi2016-04-131-1/+4
| | | | ok jmatthew@
* Remove unneeded art_free().mpi2016-04-121-2/+1
| | | | Reported by and ok jmatthew@
* Pass the address length to art_alloc() and remove the hack abusing thempi2016-01-181-4/+4
| | | | offset of the address in the sockaddr to initialize the stride lengths.
* Reduce the stride length of the tables by two and use a single pagempi2015-12-041-2/+2
| | | | | | | | | | | | | allocator for the 4K heap. In this configuration a fullfeed BGP server for v4 and v6 consumes 10M more than with the radix tree. This double the depth of the tree and makes the lookup slower. But the ratio speed/memory can be adjusted in the future, for now we are interested in a lock-free route lookup. Tested by and ok benno@
* Use SRPL_HEAD() and SRPL_ENTRY() to be consistent with and allow tompi2015-12-031-3/+2
| | | | | | fallback to a SLIST. ok dlg@, jasper@
* Convert the simple list of multipath route entries used by ART kernelsmpi2015-11-291-2/+2
| | | | | | | | | | | | to a SRP list. This turns the rtable_* layer mpsafe. We now only need to protect the ART implementation itself. Note that route(8) regress tests will now fail due to a supplementary reference taken by the SRPL_INIT(9) API. ok dlg@
* Provide art_free(), a method to release unused routing table heads.mpi2015-11-241-1/+2
| | | | While here initialize pools in art_init().
* Use a SLIST instead of a LIST for MPATH route entries with ART.mpi2015-11-061-2/+2
|
* Rewrite the logic around the dymanic array of routing tables to helpmpi2015-10-141-2/+2
| | | | | | | | | | | | | | | turning rtable_get(9) MP-safe. Use only one per-AF array, as suggested by claudio@, pointing to an array of pointers to the routing table heads. Routing tables are now allocated/initialized per-AF. This will let us allocate routing table on-demand instead of always having an AF_INET, AF_MPLS and AF_INET table as soon as a new rtableID is used. This also get rid of the "void ***" madness. ok dlg@, jmatthew@
* Initialize the routing table before domains.mpi2015-10-071-2/+2
| | | | | | | | | | | | | | | | | | | | | | | 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@
* Make ART internals free of 'struct sockaddr'.mpi2015-08-201-5/+7
| | | | | | | | | | Keep route entry/BSD compatibility goos in the rtable layer. The way addresses and masks (prefix-lengths) are encoded is really tied to the radix-tree implementation. Since we decided to no longer support non-contiguous masks, we could get rid of some extra "sockaddr" allocations and reduce the memory grows related to the use of a multibit-trie.
* Import an alternative routing table backend based on Yoichi Hariguchi'smpi2015-08-201-0/+61
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@
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.