![[BACK]](/icons/back.gif){kind=icon}
Up to [local] / src / sys / net
Request diff between arbitrary revisions
Default branch: MAIN
Revision 1.31 / (download) - annotate - [select for diffs], Sat Nov 11 12:17:50 2023 UTC (7 months ago) by bluhm
Branch: MAIN
CVS Tags: OPENBSD_7_5_BASE,
OPENBSD_7_5,
HEAD
Changes since 1.30: +2 -2 lines
Diff to previous 1.30 (colored)
Remove unused parameter dst from art_get(). OK mvs@
Revision 1.30 / (download) - annotate - [select for diffs], Fri Nov 10 20:05:22 2023 UTC (7 months ago) by bluhm
Branch: MAIN
Changes since 1.29: +8 -8 lines
Diff to previous 1.29 (colored)
rtable_match() takes constant destination. For implementing MP safe route lookup, it helps to know which function parameters are constant. Add some const declarations, so that the compiler guarantees that sockaddr dst parameter of rtable_match() does not change. OK dlg@
Revision 1.29 / (download) - annotate - [select for diffs], Thu Nov 12 15:25:28 2020 UTC (3 years, 6 months ago) by mpi
Branch: MAIN
CVS Tags: OPENBSD_7_4_BASE,
OPENBSD_7_4,
OPENBSD_7_3_BASE,
OPENBSD_7_3,
OPENBSD_7_2_BASE,
OPENBSD_7_2,
OPENBSD_7_1_BASE,
OPENBSD_7_1,
OPENBSD_7_0_BASE,
OPENBSD_7_0,
OPENBSD_6_9_BASE,
OPENBSD_6_9
Changes since 1.28: +1 -2 lines
Diff to previous 1.28 (colored)
Document art locking. ok denis@, jmatthew@
Revision 1.28 / (download) - annotate - [select for diffs], Sun Mar 31 19:29:27 2019 UTC (5 years, 2 months ago) by tb
Branch: MAIN
CVS Tags: OPENBSD_6_8_BASE,
OPENBSD_6_8,
OPENBSD_6_7_BASE,
OPENBSD_6_7,
OPENBSD_6_6_BASE,
OPENBSD_6_6,
OPENBSD_6_5_BASE,
OPENBSD_6_5
Changes since 1.27: +1 -32 lines
Diff to previous 1.27 (colored)
Unbreak tree by removing the bits that were copied to art.h in r1.18 from here. reported by anton and otto
Revision 1.27 / (download) - annotate - [select for diffs], Tue Feb 28 09:50:13 2017 UTC (7 years, 3 months ago) by mpi
Branch: MAIN
CVS Tags: OPENBSD_6_4_BASE,
OPENBSD_6_4,
OPENBSD_6_3_BASE,
OPENBSD_6_3,
OPENBSD_6_2_BASE,
OPENBSD_6_2,
OPENBSD_6_1_BASE,
OPENBSD_6_1
Changes since 1.26: +1 -3 lines
Diff to previous 1.26 (colored)
Prevent a MP race in rtable_lookup(). 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@
Revision 1.26 / (download) - annotate - [select for diffs], Tue Jan 24 10:08:30 2017 UTC (7 years, 4 months ago) by krw
Branch: MAIN
Changes since 1.25: +2 -2 lines
Diff to previous 1.25 (colored)
A space here, a space there. Soon we're talking real whitespace rectification.
Revision 1.25 / (download) - annotate - [select for diffs], Mon Jan 23 01:02:11 2017 UTC (7 years, 4 months ago) by claudio
Branch: MAIN
Changes since 1.24: +6 -6 lines
Diff to previous 1.24 (colored)
Make the art interface a bit more generic by not depending on sockaddr in the functions. This way it can be used for other trees as well. OK mpi@ phessler@
Revision 1.24 / (download) - annotate - [select for diffs], Thu Sep 15 02:00:18 2016 UTC (7 years, 8 months ago) by dlg
Branch: MAIN
Changes since 1.23: +9 -14 lines
Diff to previous 1.23 (colored)
all pools have their ipl set via pool_setipl, so fold it into pool_init. 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);
Revision 1.23 / (download) - annotate - [select for diffs], Tue Aug 30 07:42:57 2016 UTC (7 years, 9 months ago) by jmatthew
Branch: MAIN
Changes since 1.22: +8 -7 lines
Diff to previous 1.22 (colored)
use a per-table rwlock to serialize ART updates and walks, rather than taking the kernel lock. ok mpi@ dlg@
Revision 1.22 / (download) - annotate - [select for diffs], Tue Jul 19 10:51:44 2016 UTC (7 years, 10 months ago) by mpi
Branch: MAIN
CVS Tags: OPENBSD_6_0_BASE,
OPENBSD_6_0
Changes since 1.21: +3 -3 lines
Diff to previous 1.21 (colored)
Revert use of the _SAFE version of SRPL_FOREACH() now that the offending 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.
Revision 1.21 / (download) - annotate - [select for diffs], Mon Jul 4 08:11:48 2016 UTC (7 years, 11 months ago) by mpi
Branch: MAIN
Changes since 1.20: +3 -3 lines
Diff to previous 1.20 (colored)
Use the _SAFE_ version of SRPL_FOREACH() in rtable_walk_helper() to 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@
Revision 1.20 / (download) - annotate - [select for diffs], Wed Jun 22 06:32:32 2016 UTC (7 years, 11 months ago) by dlg
Branch: MAIN
Changes since 1.19: +72 -46 lines
Diff to previous 1.19 (colored)
rework art_walk so it will behave in an mpsafe world. 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@
Revision 1.19 / (download) - annotate - [select for diffs], Tue Jun 14 04:42:02 2016 UTC (7 years, 11 months ago) by jmatthew
Branch: MAIN
Changes since 1.18: +171 -104 lines
Diff to previous 1.18 (colored)
Convert the links between art data structures used during lookups into srps. 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@
Revision 1.18 / (download) - annotate - [select for diffs], Fri Jun 3 03:59:43 2016 UTC (8 years ago) by dlg
Branch: MAIN
Changes since 1.17: +75 -13 lines
Diff to previous 1.17 (colored)
defer the freeing of art tables and nodes to a task. 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@
Revision 1.17 / (download) - annotate - [select for diffs], Thu Jun 2 00:39:22 2016 UTC (8 years ago) by dlg
Branch: MAIN
Changes since 1.16: +8 -1 lines
Diff to previous 1.16 (colored)
pool_setipl at IPL_SOFTNET for all the art structures.
Revision 1.16 / (download) - annotate - [select for diffs], Thu Jun 2 00:34:13 2016 UTC (8 years ago) by dlg
Branch: MAIN
Changes since 1.15: +4 -5 lines
Diff to previous 1.15 (colored)
always clean up the heap in art_table_delete, even for the last at_refcnt in the future a table may also be referenced by a cpu reading it with srp as well as the art rtable, so try and make sure it is always usable. ok mpi@
Revision 1.15 / (download) - annotate - [select for diffs], Wed Jun 1 06:19:06 2016 UTC (8 years ago) by dlg
Branch: MAIN
Changes since 1.14: +2 -1 lines
Diff to previous 1.14 (colored)
move all the art_node initialisation to art_get in art.c ok mpi@
Revision 1.14 / (download) - annotate - [select for diffs], Wed Apr 13 08:04:14 2016 UTC (8 years, 2 months ago) by mpi
Branch: MAIN
Changes since 1.13: +24 -2 lines
Diff to previous 1.13 (colored)
Keep all pools in the same place. ok jmatthew@
Revision 1.13 / (download) - annotate - [select for diffs], Tue Apr 12 06:40:44 2016 UTC (8 years, 2 months ago) by mpi
Branch: MAIN
Changes since 1.12: +2 -9 lines
Diff to previous 1.12 (colored)
Remove unneeded art_free(). Reported by and ok jmatthew@
Revision 1.12 / (download) - annotate - [select for diffs], Mon Jan 18 18:27:11 2016 UTC (8 years, 4 months ago) by mpi
Branch: MAIN
CVS Tags: OPENBSD_5_9_BASE,
OPENBSD_5_9
Changes since 1.11: +6 -9 lines
Diff to previous 1.11 (colored)
Pass the address length to art_alloc() and remove the hack abusing the offset of the address in the sockaddr to initialize the stride lengths.
Revision 1.11 / (download) - annotate - [select for diffs], Fri Dec 4 14:15:27 2015 UTC (8 years, 6 months ago) by mpi
Branch: MAIN
Changes since 1.10: +19 -19 lines
Diff to previous 1.10 (colored)
Reduce the stride length of the tables by two and use a single page 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@
Revision 1.10 / (download) - annotate - [select for diffs], Tue Nov 24 12:48:20 2015 UTC (8 years, 6 months ago) by dlg
Branch: MAIN
Changes since 1.9: +4 -1 lines
Diff to previous 1.9 (colored)
in art_insert, if at_default on the first table is set then return the existing route rather than overwrite it. ok mpi@
Revision 1.9 / (download) - annotate - [select for diffs], Tue Nov 24 12:06:30 2015 UTC (8 years, 6 months ago) by mpi
Branch: MAIN
Changes since 1.8: +20 -16 lines
Diff to previous 1.8 (colored)
Provide art_free(), a method to release unused routing table heads. While here initialize pools in art_init().
Revision 1.8 / (download) - annotate - [select for diffs], Thu Nov 12 14:29:04 2015 UTC (8 years, 7 months ago) by mpi
Branch: MAIN
Changes since 1.7: +59 -35 lines
Diff to previous 1.7 (colored)
Allocate root tables on demand an free them like any other table. With this change we no longer waste some precious Kb for unused routing tables like the AF_MPLS one or those with rtableid != 0. This will also simplify the SRP dance during lookups.
Revision 1.7 / (download) - annotate - [select for diffs], Tue Nov 10 10:23:27 2015 UTC (8 years, 7 months ago) by mpi
Branch: MAIN
Changes since 1.6: +51 -8 lines
Diff to previous 1.6 (colored)
Allocate ART table's heap independently from the structure and use 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@
Revision 1.6 / (download) - annotate - [select for diffs], Wed Nov 4 09:50:21 2015 UTC (8 years, 7 months ago) by mpi
Branch: MAIN
Changes since 1.5: +5 -1 lines
Diff to previous 1.5 (colored)
Some tweaks to build the rtable API and backends in userland. Needed by the regression tests.
Revision 1.5 / (download) - annotate - [select for diffs], Wed Oct 14 10:09:30 2015 UTC (8 years, 7 months ago) by mpi
Branch: MAIN
Changes since 1.4: +2 -2 lines
Diff to previous 1.4 (colored)
Rewrite the logic around the dymanic array of routing tables to help 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@
Revision 1.4 / (download) - annotate - [select for diffs], Wed Oct 7 10:50:35 2015 UTC (8 years, 8 months ago) by mpi
Branch: MAIN
Changes since 1.3: +11 -13 lines
Diff to previous 1.3 (colored)
Initialize the routing table before domains. 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@
Revision 1.3 / (download) - annotate - [select for diffs], Thu Aug 20 12:51:10 2015 UTC (8 years, 9 months ago) by mpi
Branch: MAIN
Changes since 1.2: +9 -39 lines
Diff to previous 1.2 (colored)
Make ART internals free of 'struct sockaddr'. 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.
Revision 1.2 / (download) - annotate - [select for diffs], Thu Aug 20 12:41:54 2015 UTC (8 years, 9 months ago) by mpi
Branch: MAIN
Changes since 1.1: +2 -35 lines
Diff to previous 1.1 (colored)
In an email dated 11 Feb 2015, Yoichi Hariguchi accepted to re-license his reference ART implementation from a BSD 4-clause to ISC. Thanks a lot to him!
Revision 1.1 / (download) - annotate - [select for diffs], Thu Aug 20 12:39:43 2015 UTC (8 years, 9 months ago) by mpi
Branch: MAIN
Import an alternative routing table backend based on Yoichi Hariguchi's 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@