summaryrefslogtreecommitdiffstats
path: root/sys/net/radix.c (follow)
Commit message (Collapse)AuthorAgeFilesLines
* spellingjsg2021-03-101-2/+2
| | | | ok gnezdo@ semarie@ mpi@
* free(9) sizes for M_RTABLE.mpi2019-07-081-3/+3
| | | | ok kn@
* Remove KERNEL_LOCK() asserts.mpi2017-06-201-6/+1
| | | | | | | pf table code iterates on a radix tree and currently relies on the NET_LOCK() to do the serialization. Found the hardway by jasper@
* Make rn_match() and rn_lookup() safe to be used in parrallel, whenmpi2017-06-191-32/+47
| | | | | | | | | | | | | different trees are manipulated: - Stop writting to global variables - Use a buffer on the stack - Anotate read/only arrays as such While here introduce a SALEN() macro and assert that the KERNEL_LOCK() is held when a tree is modified. ok bluhm@
* A space here, a space there. Soon we're talking real whitespacekrw2017-01-241-5/+5
| | | | rectification.
* Remove radix_mpath dragons.mpi2016-11-141-78/+1
| | | | | | This code insn't used since ART is the default. ok vgross@
* all pools have their ipl set via pool_setipl, so fold it into pool_init.dlg2016-09-151-4/+3
| | | | | | | | | | | | | | | | | | | | | | the ioff argument to pool_init() is unused and has been for many years, so this replaces it with an ipl argument. because the ipl will be set on init we no longer need pool_setipl. most of these changes have been done with coccinelle using the spatch below. cocci sucks at formatting code though, so i fixed that by hand. the manpage and subr_pool.c bits i did myself. ok tedu@ jmatthew@ @ipl@ expression pp; expression ipl; expression s, a, o, f, m, p; @@ -pool_init(pp, s, a, o, f, m, p); -pool_setipl(pp, ipl); +pool_init(pp, s, a, ipl, f, m, p);
* pool_setipldlg2016-08-301-1/+2
| | | | ok claudio@ mpi@
* Do not compile net/radix_mpath.c in ART-enabled kernels.mpi2015-11-061-1/+5
| | | | | | | In such kernels multipath routing support is independant from the data structure used to perform the binary lookup. Is is implemented as a singly-listed list of route entries. This is possible because a "struct rtentry" is no longer mapped 1:1 to a node in the tree.
* Some tweaks to build the rtable API and backends in userland.mpi2015-11-041-1/+6
| | | | Needed by the regression tests.
* Use the radix API directly and get rid of the function pointers. Therempi2015-10-081-6/+1
| | | | | | is no point in keeping an unused level of abstraction. ok mikeb@, claudio@
* Initialize the routing table before domains.mpi2015-10-071-2/+3
| | | | | | | | | | | | | | | | | | | | | | | 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 every subsystem using a radix tree call rn_init() and pass thempi2015-09-041-21/+43
| | | | | | | | | | | | | | | 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@
* Use a global table for domains instead of building a list at run time.mpi2015-08-301-6/+8
| | | | | | | As a side effect there's no need to run if_attachdomain() after the list of domains has been built. ok claudio@, reyk@
* Fix rn_match and there for the expoerted lookup functions in radix.cclaudio2015-07-161-11/+22
| | | | | | to never return the internal RNF_ROOT nodes. This removes the checks in the callee to verify that not an RNF_ROOT node was returned. OK mpi@
* Do not return internal nodes to the upper layer in rn_lookup().mpi2015-07-071-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | The limit between the radix layer and the route layer is somewhat vague, if it exists at all. This changes prevent rtrequest1(9) to find and delete the root node (RNF_ROOT) when trying to delete a non-existing default route: # route delete 0.0.0.0 delete host 0.0.0.0 # route delete 0.0.0.0 route: writing to routing socket: No such process delete host 0.0.0.0: not in table Historically rn_delete() was a no-op when called with an internal node as argument. But there's no reason to manipulate such node. In a better world rn_match() would contain such check, but let's change the perfect-match function for the moment as this fixes a bug and many dragons are lurking in there. Fix a regression introduced by the big refactoring of r1.40 and reported by tobias@. ok tobias@, claudio@, pelikan@
* Make sure that rn_mpath_adj_mpflag() is called with the correct pointerclaudio2015-03-041-1/+6
| | | | | | | to the multipath chain when removing routes. This fixes the sbin/route testcases 17-19 and fixes an annoying opsfd bug because of routes wrongly marked as multipath ones. OK deraadt, mpi, sthen, benno, phessler
* replace some malloc multiplies with mallocarry. ok deraadt henningtedu2014-12-021-2/+2
|
* add a size argument to free. will be used soon, but for now default to 0.tedu2014-07-121-2/+2
| | | | after discussions with beck deraadt kettenis.
* KASSERT() the correct node if a hint is passed to rn_delete().mpi2014-07-011-4/+4
| | | | | | | Fix a panic when trying to remove a route with the magical 0.0.0.0 destination. looks ok to claudio@
* Big refactoring of the radix code (mainly rn_addroute but also partclaudio2014-05-271-279/+456
| | | | | | | | of rn_delete was changed). The mpath code gets a much better rn_mpath_next() function that allows looping through the dupedkey list based on prio, any or only active routes. This solves the issues seen with failed deletes of down routes. Commit this now so that it gets tested. Both sthen@ and blambert@ agree.
* Kill the RN_DEBUG code it is broken since rev 1.1 and not worth fixing.claudio2014-01-221-50/+1
| | | | OK mpi@ and krw@
* Cleanup the abuse of x as the rn_addmask radix node. Since in mostclaudio2014-01-211-54/+55
| | | | | | | | | cases x is just used as a temp variable. Main offender is rn_addmask() which sets x once at the top uses it then late in the function and then starts reuing it for various other stuff. While there fix some for loops to while ones and fix one strange do { } while() loop. And since rn_search() can not return NULL remove one extra check. OK mpi@
* Try to be more consistent in how various variables are setup and named.claudio2014-01-201-65/+72
| | | | | | | | Also remove a memset that is already happeing because we use PR_ZERO on the allocation. Move two memmove to memcpy because the addrs can not overlap. Make some simple helper functions static __inline and remove one of the explicit rn_search inlines. OK mpi@
* More cleanup in radix.c. Kill the rt_mkfreelist and replace it with aclaudio2014-01-191-20/+10
| | | | radix_mask pool. With input and OK mikeb@ and henning@
* Start to reduce the madness in radix.c. This only used by the kernelclaudio2014-01-191-10/+1
| | | | since ages so remove the bits used for userland compiles. OK mikeb@
* replace the rest of the obsolete radix macrostedu2014-01-101-27/+39
| | | | | sprinkle 0 -> NULL where obvious ok millert mpi
* replace Bcopy macro with memmove and memcpy. ok mpitedu2014-01-091-4/+4
|
* Fix invalid size to memcmp() in rn_lexobetter() introduced when themillert2013-12-121-4/+3
| | | | | hand-rolled loop was converted to memcmp(). From Kieran Devlin. OK markus@
* Rename rn_mpath_count() to rn_mpath_active_count() since it will onlyclaudio2013-10-201-2/+2
| | | | return the number of active aka RTF_UP multipath routes. OK grep & gcc
* Place declarations for internal radix functions inside radix.c, stopblambert2012-07-101-1/+7
| | | | | | exporting them to the outside world via radix.h. ok claudio@ sthen@ henning@
* fix typos, martin pelikanhenning2011-07-221-2/+2
|
* Fix a 16 year old bug in the sorting routine for non-contiguous netmasks.mpf2010-08-221-7/+16
| | | | | | | | | | | | | For masks of identical length rn_lexobetter() did not stop on the first non-equal byte. This leads rn_addroute() to not detecting duplicate entries and thus we might create a very long list of masks to check for each node. This can have a huge impact on IPsec performance, where non-contiguous masks are used for the flow lookup. In a setup with 1300 flows we saw 400 duplicate masks and only a third of the expected throughput. Lots of help in narrowing this down from markus@. Improved comments from claudio@. OK markus@, claudio@
* Add the rtable id as an argument to rn_walktree(). Functions likeclaudio2010-06-281-4/+5
| | | | | | | rt_if_remove_rtdelete() need to know the table id to be able to correctly remove nodes. Problem found by Andrea Parazzini and analyzed by Martin Pelikán. OK henning@
* Change the way way rn_mklists work (especially the RNF_NORMAL ones).claudio2009-01-061-6/+60
| | | | | | | | | | | | Until now RNF_NORMAL masks did not use the refcount because only one route in a particular subtree could have this mask. With multipath routing this is no longer correct. The result was wrong backtracking information beeing stored in the radix tree and so cretain lookups ended up on the wrong multipath nodes. Use rm_refs for RNF_NORMAL masks so that all multipath routes are able to point to the same radix_mask entry. Additional logic ensures that rm_leaf always points back to the head of the multipath rn_dupedkey chain. Tested by dlg@, gollo@, david@, sthen@ and a few more This can have my OK dlg@
* At least try to make this code a bit easier to read. Don't fiddle with xclaudio2008-12-291-7/+6
| | | | | | when xx can do the trick or in dlg's words: "xx was a copy of x so they could use x for some temp working and restore it from xx later? yeesh" ok dlg@
* Change rn_mpath_next() to be able to walk over the full multipath listclaudio2008-11-211-2/+2
| | | | | | | not only over routes of the same prio. This makes it possible to modify rt_mpath_matchgate() so that if only gateway is specified without a specific priority it will scan the full list and not only the first routes. This is also needed for upcoming link state tracking.
* Fix a logic botch around prioinv that resulted in wrong ordering of moreclaudio2008-05-091-3/+4
| | | | specific routes. OK henning@
* Implement routing priorities. Every route inserted has a priority assignedclaudio2008-05-071-43/+47
| | | | | | | | | and the one route with the lowest number wins. This will be used by the routing daemons to resolve the synchronisations issue in case of conflicts. The nasty bits of this are in the multipath code. If no priority is specified the kernel will choose an appropriate priority. Looked at by a few people at n2k8 code is much older
* Add support for equal-cost multipath IP.pascoe2006-06-181-5/+9
| | | | | | | | | | | | | | To minimise path disruptions, this implements recommendations made in RFC2992 - the hash-threshold mechanism to select paths based on source/destination IP address pairs, and inserts multipath routes in the middle of the route table. To enable multipath distribution, use: sysctl net.inet.ip.multipath=1 and/or: sysctl net.inet6.ip6.multipath=1 testing norby@ ok claudio@ henning@ hshoexer@
* typos from alexey dobriyan;jmc2006-02-061-2/+2
|
* ANSI, mostly from Toni Mueller <openbsd-tech@oeko.net>henning2005-05-151-54/+21
|
* permit multiple default route. from kameitojun2004-04-251-4/+3
|
* radix tree with multipath support. from kame. deraadt okitojun2004-04-251-2/+50
| | | | | | | | | | | | | user visible changes: - you can add multiple routes with same key (route add A B then route add A C) - you have to specify gateway address if there are multiple entries on the table (route delete A B, instead of route delete A) kernel change: - radix_node_head has an extra entry - rnh_deladdr takes extra argument TODO: - actually take advantage of multipath (rtalloc -> rtalloc_mpath)
* sync with NetBSD, mostly a Lite2 merge.brad2004-04-251-24/+51
| | | | ok itojun@
* undo "oops" commit on 1.14 (radix_mpath).itojun2004-04-251-62/+4
|
* indentation fixitojun2004-04-251-5/+63
|
* rn_satsifies_leaf -> rn_satisfies_leafbrad2003-12-191-5/+5
| | | | | | from itojun@netbsd rev 1.15 ok deraadt@
* de-register. deraadt okitojun2003-12-101-34/+34
|
* RNF_IGNORE can corrupt the radix tree when an interface is down, ithenric2003-08-271-6/+4
| | | | | | | makes routing lookups slightly more expensive, and serves no useful purpose. ok itojun@ tedu@
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.