summaryrefslogtreecommitdiff
path: root/sys/net/rtable.c
AgeCommit message (Collapse)Author
2019-06-21Prevent recursions by not deleting entries inside rtable_walk(9).Martin Pieuchot
rtable_walk(9) now passes a routing entry back to the caller when a non zero value is returned and if it asked for it. This allows us to call rtdeletemsg()/rtrequest_delete() from the caller without creating a recursion because of rtflushclone(). Multicast code hasn't been adapted and is still possibly creating recursions. However multicast route entries aren't cloned so if a recursion exists it isn't because of rtflushclone(). Fix stack exhaustion triggered by the use of "-msave-args". Issue reported by Dániel Lévai on bugs@ confirmed by and ok bluhm@.
2019-03-05Make sure pointer is within bounds before dereferencing it.anton
ok claudio@ deraadt@ Reported-by: syzbot+8e29400e09a351f17884@syzkaller.appspotmail.com
2018-11-23Change rtable_mpath_reprio() to take the prefixlen as argument instead ofClaudio Jeker
the network mask. This saves converting the prefixlen to a mask and back. OK phessler@, benno@
2018-11-20Make rtable_satoplen() a bit more strict when parsing netmasks. EnsureClaudio Jeker
that the mask is contiguous and not longer then the prefixlen is not bigger then the maximum. Make the function behave a bit more like the similar netmask handling code in the old patricia codebase. Fixes a problem reyk@ reported regarding IPv6 masks and the fact that sin6_scope_id is after sin6_addr. OK mpi@
2018-11-19Retire dom_rtkeylen from struct domain. Nothing is using this anymore.Claudio Jeker
It was used by the original patricia tree. OK mpi@
2018-09-09provide rtable_empty(), returns 1 if the rtable doesn't contain any routesHenning Brauer
ok bluhm
2017-09-05Simplify rtable_mpath_insert().Martin Pieuchot
ok jmatthew@
2017-09-05Restart the iteration when a multipath list is re-ordered to make sureMartin Pieuchot
no entry are missed. While here do not re-ordered or send messages for route entries that are already in the expected state. Make rttest30 pass. ok gerhard@
2017-07-30Enable mpath support in the Allotment Routing Table (ART) on the ramdisk.Florian Obser
OK mpi
2017-07-30Switch installer to Allotment Routing Table (ART).Florian Obser
Prompted by a bugreport by naddy that IPv6 autoconfiguration is broken in the installer. OK mpi, "go for it" deraadt
2017-05-11No need to go through a remove/insert cycle when there's a single routeMartin Pieuchot
entry on the multipath list. Fix a NULL dereference triggered by a CPU doing a lookup when another one is updating the priorities of some routes. By not doing a remove/insert we ensure that ``an_rtlist'' is never empty and do not need a conditional in the fast path. Problem reported by and ok markus@
2017-02-28Prevent a MP race in rtable_lookup().Martin Pieuchot
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@
2017-01-24A space here, a space there. Soon we're talking real whitespaceKenneth R Westerback
rectification.
2016-11-20Make rtable_iterate(9) mpsafe by using the new SRPL_NEXT(9).Martin Pieuchot
ok dlg@, jmatthew@
2016-11-20Rename SRPL_ENTER() to SRPL_FIRST() and SRPL_NEXT() to SRPL_FOLLOW().Martin Pieuchot
This allows us to introduce SRPL_NEXT() that can be used to start iterating on an arbitrary member of an srp list, hence without calling SRPL_ENTER(). ok dlg@, jmatthew@
2016-11-14Automatically create a default lo(4) interface per rdomain.Martin Pieuchot
In order to stop abusing lo0 for all rdomains, a new loopback interface will be created every time a rdomain is created. The unit number will be the same as the rdomain, i.e. lo1 will be attached to rdomain 1. If this loopback interface is already in use it wont be possible to create the corresponding rdomain. In order to know which lo(4) interface is attached to a rdomain, its index is stored in the rtable/rdomain map. This is a long overdue since the introduction of rtable/rdomain. It also fixes a recent regression due to resetting the rdomain of an incoming packet reported by semarie@, Andreas Bartelt and Nils Frohberg. ok claudio@
2016-11-14Remove radix_mpath dragons.Martin Pieuchot
This code insn't used since ART is the default. ok vgross@
2016-09-07Rename rtable_mpath_next() into rtable_iterate() and make it do a properMartin Pieuchot
reference count. rtable_iterate() frees the passed ``rt'' and returns the next one on the multipath list or NULL if there's none. ok dlg@
2016-08-30use a per-table rwlock to serialize ART updates and walks, rather thanJonathan Matthew
taking the kernel lock. ok mpi@ dlg@
2016-07-19Revert use of the _SAFE version of SRPL_FOREACH() now that the offendingMartin Pieuchot
function has been fixed. Functions passed to rtable_walk() must return EAGAIN if they delete an entry from the tree, no matter if it is a leaf or not.
2016-07-04Use the _SAFE_ version of SRPL_FOREACH() in rtable_walk_helper() toMartin Pieuchot
prevent an off-by-one when removing entries from the mpath list. Fix a regression introduced by the refactoring needed to serialize rtable_walk() with create/delete. ok jca@
2016-06-22rework art_walk so it will behave in an mpsafe world.David Gwynne
art_walk now explicitly takes the same lock used to serialise change made via rtable_insert and _delete, so it can safely adjust the refcnts on tables while it recurses into them. they need to still exist when returning out of the recursion. it uses srps to access nodes and drops the lock before calling the callback function. this is because some callbacks sleep (eg, copyout in the sysctl code that dumps an rtable to userland), which you shouldnt hold a lock accross. other callbacks attempt to modify the rtable (eg, marking routes as down when then interface theyre on goes down), which tries to take the lock again, which probably wont work in the future. ok jmatthew@ mpi@
2016-06-14Convert the links between art data structures used during lookups into srps.Jonathan Matthew
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@
2016-06-07per trending style, add continue to empty loops.Ted Unangst
ok mglocker
2016-06-01shuffle the code in rtable_insert so it inserts a populated art_node.David Gwynne
this makes the node usable as soon as it is in the tree, rather than after it inserts the rtentry on the node. ok mpi@
2016-06-01rtref and rtfree around moving the rt in rtable_mpath_reprio so the listDavid Gwynne
operations cant drop the refcount to 0. ok mpi@
2016-06-01move all the art_node initialisation to art_get in art.cDavid Gwynne
ok mpi@
2016-05-18rework the srp api so it takes an srp_ref struct that the caller provides.David Gwynne
the srp_ref struct is used to track the location of the callers hazard pointer so later calls to srp_follow and srp_enter already know what to clear. this in turn means most of the caveats around using srps go away. specifically, you can now: - switch cpus while holding an srp ref - ie, you can sleep while holding an srp ref - you can take and release srp refs in any order the original intent was to simplify use of the api when dealing with complicated data structures. the caller now no longer has to track the location of the srp a value was fetched from, the srp_ref effectively does that for you. srp lists have been refactored to use srp_refs instead of srpl_iter structs. this is in preparation of using srps inside the ART code. ART is a complicated data structure, and lookups require overlapping holds of srp references. ok mpi@ jmatthew@
2016-05-02Simplify life for routing table implementations by requiring that rtable_walkJonathan Matthew
callbacks return EAGAIN if they modify the routing table. While we're here, simplify life for rtable_walk callers by moving the loop that restarts the walk on EAGAIN into rtable_walk itself. Flushing cloned routes on interface state changes becomes a bit more inefficient, but this can be improved later. ok mpi@ dlg@
2016-04-13Keep all pools in the same place.Martin Pieuchot
ok jmatthew@
2016-02-24Fix ECMP routing by passing the correct destination address to theMartin Pieuchot
hash routine. Bug reported and fix analysed by Jean-Daniel Dupas <jddupas AT xooloo DOT net> ok deraadt@
2016-01-18Pass the address length to art_alloc() and remove the hack abusing theMartin Pieuchot
offset of the address in the sockaddr to initialize the stride lengths.
2016-01-18Stop storing a backpointer to the corresponding ART node in each routeMartin Pieuchot
entry. This pointer hasn't been used for some time and without it no external reference count is needed to turn art_lookup() mpsafe.
2015-12-21Pass the destination and mask to rtable_mpath_reprio() in order to notMartin Pieuchot
use ``rt_node'' with ART.
2015-12-16Merge rtable_mpath_select() into rtable_match().Martin Pieuchot
This allow us to get rid of one more "rt_node" usage with ART. ok jmatthew@
2015-12-15Do not panic when trying to delete an non-existing route with ART.Martin Pieuchot
Reported by bluhm@, ok jmatthew@
2015-12-04Move the KERNEL_LOCK from rt_match() to rtable_match().Martin Pieuchot
ok claudio@
2015-12-03Get rid of rt_mask() and stop allocating a "struct sockaddr" for everyMartin Pieuchot
route entry in ART. rt_plen() now represents the prefix length of a route entry and should be used instead. For now use a "struct sockaddr_in6" to represent the mask when needed, this should be then replaced by the prefix length and RTA_NETMASK only used for compatibility with userland. ok claudio@
2015-12-02rtable_delete() does not use its prio parameter, so delete it.Alexander Bluhm
OK mpi@
2015-12-02Respect priorities when inserting routes to the same destination in ART.Martin Pieuchot
2015-12-02Move multipath Hash-Threshold selection mechanism inside rtable_match().Martin Pieuchot
This will helps for unlocking the routing table and will prevent further mistake by keeping the multipath logic inside the rtable_* API. ok dlg@, claudio@
2015-11-29Convert the simple list of multipath route entries used by ART kernelsMartin Pieuchot
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@
2015-11-27Document that routing table heads are never freed as suggested by dlg@Martin Pieuchot
and kill rtable_put() because we're not going to use it. The overhead of keeping a "struct art_root/radix_node_head" around is very small compared to the added complexity needed to reference count such structures.
2015-11-27Protect the growth of the routing table arrays used by rtable_get()Martin Pieuchot
with SRPs. This is a simplified version of the dynamically sizeable array of pointers used by if_get() because routing table heads are never freed. ok dlg@
2015-11-24Provide art_free(), a method to release unused routing table heads.Martin Pieuchot
While here initialize pools in art_init().
2015-11-10Allocate ART table's heap independently from the structure and useMartin Pieuchot
pool(9) to not waste most of the memory allocated. This reduces the memory overhead of our ART routing table from 80M to 70M compared to the existing radix-tree when loading ~550K IPv4 routes. ART can now be used for huge tables without exhausting malloc(9)'s limit. claudio@ agrees with the direction, inputs from and ok dlg@
2015-11-09Do not leave dangling pointers in the ART tree in case of memoryMartin Pieuchot
exhaustion. Reported by benno@ and found thanks to his bgpd(8) test setup.
2015-11-06Rename rt_mpath_next() into rtable_mpath_next() and provide anMartin Pieuchot
implementation for ART based on the singly-linked list of route entries.
2015-11-06Use a SLIST instead of a LIST for MPATH route entries with ART.Martin Pieuchot
2015-11-06In ART separate the MPATH delete case to properly recover if art_delete()Martin Pieuchot
does not find a matching node. This currently never happens because we always do a route lookup before calling rtable_delete(). Yes this is odd & due to the way multipath is implemented in the radix tree.