The NetBSD Project

CVS log for src/sys/net/rtbl.c

[BACK] Up to [cvs.NetBSD.org] / src / sys / net

Request diff between arbitrary revisions


Keyword substitution: kv
Default branch: MAIN


Revision 1.1.18.1: download - view: text, markup, annotated - select for diffs
Sun Dec 3 11:39:02 2017 UTC (8 years, 11 months ago) by jdolecek
Branches: tls-maxphys
Diff to: previous 1.1: preferred, colored; next MAIN 1.2: preferred, colored
Changes since revision 1.1: +29 -7 lines
update from HEAD

Revision 1.1.36.5: download - view: text, markup, annotated - select for diffs
Mon Aug 28 17:53:11 2017 UTC (9 years, 2 months ago) by skrll
Branches: nick-nhusb
Diff to: previous 1.1.36.4: preferred, colored; branchpoint 1.1: preferred, colored; next MAIN 1.2: preferred, colored
Changes since revision 1.1.36.4: +3 -4 lines
Sync with HEAD

Revision 1.7: download - view: text, markup, annotated - select for diffs
Thu Jun 1 02:45:14 2017 UTC (9 years, 5 months ago) by chs
Branches: MAIN
CVS tags: tls-maxphys-base-20171202, thorpej-ifq-base, thorpej-ifq, thorpej-i2c-spi-conf2-base, thorpej-i2c-spi-conf2, thorpej-i2c-spi-conf-base, thorpej-i2c-spi-conf, thorpej-futex2-base, thorpej-futex2, thorpej-futex-base, thorpej-futex, thorpej-cfargs2-base, thorpej-cfargs2, thorpej-cfargs-base, thorpej-cfargs, thorpej-altq-separation-base, thorpej-altq-separation, phil-wifi-base, phil-wifi-20200421, phil-wifi-20200411, phil-wifi-20200406, phil-wifi-20191119, phil-wifi-20190609, phil-wifi, pgoyette-compat-merge-20190127, pgoyette-compat-base, pgoyette-compat-20190127, pgoyette-compat-20190118, pgoyette-compat-1226, pgoyette-compat-1126, pgoyette-compat-1020, pgoyette-compat-0930, pgoyette-compat-0906, pgoyette-compat-0728, pgoyette-compat-0625, pgoyette-compat-0521, pgoyette-compat-0502, pgoyette-compat-0422, pgoyette-compat-0415, pgoyette-compat-0407, pgoyette-compat-0330, pgoyette-compat-0322, pgoyette-compat-0315, pgoyette-compat, perseant-stdc-iso10646-base, perseant-stdc-iso10646, perseant-exfatfs-base-20261102, perseant-exfatfs-base-20250801, perseant-exfatfs-base-20240630, perseant-exfatfs-base, perseant-exfatfs, nick-nhusb-base-20170825, netbsd-9-base, netbsd-9-5-RELEASE, netbsd-9-4-RELEASE, netbsd-9-3-RELEASE, netbsd-9-2-RELEASE, netbsd-9-1-RELEASE, netbsd-9-0-RELEASE, netbsd-9-0-RC2, netbsd-9-0-RC1, netbsd-9, netbsd-8-base, netbsd-8-3-RELEASE, netbsd-8-2-RELEASE, netbsd-8-1-RELEASE, netbsd-8-1-RC1, netbsd-8-0-RELEASE, netbsd-8-0-RC2, netbsd-8-0-RC1, netbsd-8, netbsd-11-base, netbsd-11-1-RELEASE, netbsd-11-0-RELEASE, netbsd-11-0-RC7, netbsd-11-0-RC6, netbsd-11-0-RC5, netbsd-11-0-RC4, netbsd-11-0-RC3, netbsd-11-0-RC2, netbsd-11-0-RC1, netbsd-11, netbsd-10-base, netbsd-10-2-RELEASE, netbsd-10-1-RELEASE, netbsd-10-0-RELEASE, netbsd-10-0-RC6, netbsd-10-0-RC5, netbsd-10-0-RC4, netbsd-10-0-RC3, netbsd-10-0-RC2, netbsd-10-0-RC1, netbsd-10, matt-nb8-mediatek-base, matt-nb8-mediatek, isaki-audio2-base, isaki-audio2, is-mlppp-base, is-mlppp, cjep_sun2x-base1, cjep_sun2x-base, cjep_sun2x, cjep_staticlib_x-base1, cjep_staticlib_x-base, cjep_staticlib_x, bouyer-xenpvh-base2, bouyer-xenpvh-base1, bouyer-xenpvh-base, bouyer-xenpvh, bouyer-sunxi-drm-base, bouyer-sunxi-drm, ad-namecache-base3, ad-namecache-base2, ad-namecache-base1, ad-namecache-base, ad-namecache, HEAD
Diff to: previous 1.6: preferred, colored
Changes since revision 1.6: +3 -4 lines
remove checks for failure after memory allocation calls that cannot fail:

  kmem_alloc() with KM_SLEEP
  kmem_zalloc() with KM_SLEEP
  percpu_alloc()
  pserialize_create()
  psref_class_create()

all of these paths include an assertion that the allocation has not failed,
so callers should not assert that again.

Revision 1.3.2.2: download - view: text, markup, annotated - select for diffs
Mon Mar 20 06:57:50 2017 UTC (9 years, 7 months ago) by pgoyette
Branches: pgoyette-localcount
Diff to: previous 1.3.2.1: preferred, colored; branchpoint 1.3: preferred, colored; next MAIN 1.4: preferred, colored
Changes since revision 1.3.2.1: +2 -3 lines
Sync with HEAD

Revision 1.1.36.4: download - view: text, markup, annotated - select for diffs
Sun Feb 5 13:40:58 2017 UTC (9 years, 9 months ago) by skrll
Branches: nick-nhusb
Diff to: previous 1.1.36.3: preferred, colored; branchpoint 1.1: preferred, colored
Changes since revision 1.1.36.3: +3 -4 lines
Sync with HEAD

Revision 1.6: download - view: text, markup, annotated - select for diffs
Wed Jan 11 13:08:29 2017 UTC (9 years, 10 months ago) by ozaki-r
Branches: MAIN
CVS tags: prg-localcount2-base3, prg-localcount2-base2, prg-localcount2-base1, prg-localcount2-base, prg-localcount2, pgoyette-localcount-20170426, pgoyette-localcount-20170320, nick-nhusb-base-20170204, jdolecek-ncq-base, jdolecek-ncq, bouyer-socketcan-base1, bouyer-socketcan-base, bouyer-socketcan
Diff to: previous 1.5: preferred, colored
Changes since revision 1.5: +2 -3 lines
Get rid of unnecessary header inclusions

Revision 1.3.2.1: download - view: text, markup, annotated - select for diffs
Sat Jan 7 08:56:50 2017 UTC (9 years, 10 months ago) by pgoyette
Branches: pgoyette-localcount
Diff to: previous 1.3: preferred, colored
Changes since revision 1.3: +20 -3 lines
Sync with HEAD.  (Note that most of these changes are simply $NetBSD$
tag issues.)

Revision 1.5: download - view: text, markup, annotated - select for diffs
Mon Dec 12 03:55:57 2016 UTC (9 years, 11 months ago) by ozaki-r
Branches: MAIN
CVS tags: pgoyette-localcount-20170107
Diff to: previous 1.4: preferred, colored
Changes since revision 1.4: +3 -3 lines
Make the routing table and rtcaches MP-safe

See the following descriptions for details.

Proposed on tech-kern and tech-net


Overview
--------

We protect the routing table with a rwock and protect
rtcaches with another rwlock. Each rtentry is protected
from being freed or updated via reference counting and psref.

Global rwlocks
--------------

There are two rwlocks; one for the routing table (rt_lock) and
the other for rtcaches (rtcache_lock). rtcache_lock covers
all existing rtcaches; there may have room for optimizations
(future work).

The locking order is rtcache_lock first and rt_lock is next.

rtentry references
------------------

References to an rtentry is managed with reference counting
and psref. Either of the two mechanisms is used depending on
where a rtentry is obtained. Reference counting is used when
we obtain a rtentry from the routing table directly via
rtalloc1 and rtrequest{,1} while psref is used when we obtain
a rtentry from a rtcache via rtcache_* APIs. In both cases,
a caller can sleep/block with holding an obtained rtentry.

The reasons why we use two different mechanisms are (i) only
using reference counting hurts the performance due to atomic
instructions (rtcache case) (ii) ease of implementation;
applying psref to APIs such rtaloc1 and rtrequest{,1} requires
additional works (adding a local variable and an argument).

We will finally migrate to use only psref but we can do it
when we have a lockless routing table alternative.

Reference counting for rtentry
------------------------------

rt_refcnt now doesn't count permanent references such as for
rt_timers and rtcaches, instead it is used only for temporal
references when obtaining a rtentry via rtalloc1 and rtrequest{,1}.
We can do so because destroying a rtentry always involves
removing references of rt_timers and rtcaches to the rtentry
and we don't need to track such references. This also makes
it easy to wait for readers to release references on deleting
or updating a rtentry, i.e., we can simply wait until the
reference counter is 0 or 1. (If there are permanent references
the counter can be arbitrary.)

rt_ref increments a reference counter of a rtentry and rt_unref
decrements it. rt_ref is called inside APIs (rtalloc1 and
rtrequest{,1} so users don't need to care about it while
users must call rt_unref to an obtained rtentry after using it.

rtfree is removed and we use rt_unref and rt_free instead.
rt_unref now just decrements the counter of a given rtentry
and rt_free just tries to destroy a given rtentry.

See the next section for destructions of rtentries by rt_free.

Destructions of rtentries
-------------------------

We destroy a rtentry only when we call rtrequst{,1}(RTM_DELETE);
the original implementation can destroy in any rtfree where it's
the last reference. If we use reference counting or psref, it's
easy to understand if the place that a rtentry is destroyed is
fixed.

rt_free waits for references to a given rtentry to be released
before actually destroying the rtentry. rt_free uses a condition
variable (cv_wait) (and psref_target_destroy for psref) to wait.

Unfortunately rtrequst{,1}(RTM_DELETE) can be called in softint
that we cannot use cv_wait. In that case, we have to defer the
destruction to a workqueue.

rtentry#rt_cv, rtentry#rt_psref and global variables
(see rt_free_global) are added to conduct the procedure.

Updates of rtentries
--------------------

One difficulty to use refcnt/psref instead of rwlock for rtentry
is updates of rtentries. We need an additional mechanism to
prevent readers from seeing inconsistency of a rtentry being
updated.

We introduce RTF_UPDATING flag to rtentries that are updating.
While the flag is set to a rtentry, users cannot acquire the
rtentry. By doing so, we avoid users to see inconsistent
rtentries.

There are two options when a user tries to acquire a rtentry
with the RTF_UPDATING flag; if a user runs in softint context
the user fails to acquire a rtentry (NULL is returned).
Otherwise a user waits until the update completes by waiting
on cv.

The procedure of a updater is simpler to destruction of
a rtentry. Wait on cv (and psref) and after all readers left,
proceed with the update.

Global variables (see rt_update_global) are added to conduct
the procedure.

Currently we apply the mechanism to only RTM_CHANGE in
rtsock.c. We would have to apply other codes. See
"Known issues" section.

psref for rtentry
-----------------

When we obtain a rtentry from a rtcache via rtcache_* APIs,
psref is used to reference to the rtentry.

rtcache_ref acquires a reference to a rtentry with psref
and rtcache_unref releases the reference after using it.
rtcache_ref is called inside rtcache_* APIs and users don't
need to take care of it while users must call rtcache_unref
to release the reference.

struct psref and int bound that is needed for psref is
embedded into struct route. By doing so we don't need to
add local variables and additional argument to APIs.

However this adds another constraint to psref other than
reference counting one's; holding a reference of an rtentry
via a rtcache is allowed by just one caller at the same time.
So we must not acquire a rtentry via a rtcache twice and
avoid a recursive use of a rtcache. And also a rtcache must
be arranged to be used by a LWP/softint at the same time
somehow. For IP forwarding case, we have per-CPU rtcaches
used in softint so the constraint is guaranteed. For a h
rtcache of a PCB case, the constraint is guaranteed by the
solock of each PCB. Any other cases (pf, ipf, stf and ipsec)
are currently guaranteed by only the existence of the global
locks (softnet_lock and/or KERNEL_LOCK). If we've found the
cases that we cannot guarantee the constraint, we would need
to introduce other rtcache APIs that use simple reference
counting.

psref of rtcache is created with IPL_SOFTNET and so rtcache
shouldn't used at an IPL higher than IPL_SOFTNET.

Note that rtcache_free is used to invalidate a given rtcache.
We don't need another care by my change; just keep them as
they are.

Performance impact
------------------

When NET_MPSAFE is disabled the performance drop is 3% while
when it's enabled the drop is increased to 11%. The difference
comes from that currently we don't take any global locks and
don't use psref if NET_MPSAFE is disabled.

We can optimize the performance of the case of NET_MPSAFE
on by reducing lookups of rtcache that uses psref;
currently we do two lookups but we should be able to trim
one of two. This is a future work.

Known issues
------------

There are two known issues to be solved; one is that
a caller of rtrequest(RTM_ADD) may change rtentry (see rtinit).
We need to prevent new references during the update. Or
we may be able to remove the code (perhaps, need more
investigations).

The other is rtredirect that updates a rtentry. We need
to apply our update mechanism, however it's not easy because
rtredirect is called in softint and we cannot apply our
mechanism simply. One solution is to defer rtredirect to
a workqueue but it requires some code restructuring.

Revision 1.1.36.3: download - view: text, markup, annotated - select for diffs
Mon Dec 5 10:55:27 2016 UTC (9 years, 11 months ago) by skrll
Branches: nick-nhusb
Diff to: previous 1.1.36.2: preferred, colored; branchpoint 1.1: preferred, colored
Changes since revision 1.1.36.2: +19 -2 lines
Sync with HEAD

Revision 1.4: download - view: text, markup, annotated - select for diffs
Tue Nov 15 01:50:06 2016 UTC (10 years ago) by ozaki-r
Branches: MAIN
CVS tags: nick-nhusb-base-20161204
Diff to: previous 1.3: preferred, colored
Changes since revision 1.3: +19 -2 lines
Don't use rt_walktree to delete routes

Some functions use rt_walktree to scan the routing table and delete
matched routes. However, we shouldn't use rt_walktree to delete
routes because rt_walktree is recursive to the routing table (radix
tree) and isn't friendly to MP-ification. rt_walktree allows a caller
to pass a callback function to delete an matched entry. The callback
function is called from an API of the radix tree (rn_walktree) but
also calls an API of the radix tree to delete an entry.

This change adds a new API of the radix tree, rn_search_matched,
which returns a matched entry that is selected by a callback
function passed by a caller and the caller itself deletes the
entry. By using the API, we can avoid the recursive form.

Revision 1.1.36.2: download - view: text, markup, annotated - select for diffs
Fri Apr 22 15:44:17 2016 UTC (10 years, 6 months ago) by skrll
Branches: nick-nhusb
Diff to: previous 1.1.36.1: preferred, colored; branchpoint 1.1: preferred, colored
Changes since revision 1.1.36.1: +9 -2 lines
Sync with HEAD

Revision 1.3: download - view: text, markup, annotated - select for diffs
Mon Apr 11 09:21:18 2016 UTC (10 years, 7 months ago) by ozaki-r
Branches: MAIN
CVS tags: pgoyette-localcount-base, pgoyette-localcount-20161104, pgoyette-localcount-20160806, pgoyette-localcount-20160726, nick-nhusb-base-20161004, nick-nhusb-base-20160907, nick-nhusb-base-20160529, nick-nhusb-base-20160422, localcount-20160914
Branch point for: pgoyette-localcount
Diff to: previous 1.2: preferred, colored
Changes since revision 1.2: +9 -2 lines
Don't use radix tree API directly

Revision 1.1.36.1: download - view: text, markup, annotated - select for diffs
Tue Sep 22 12:06:10 2015 UTC (11 years, 1 month ago) by skrll
Branches: nick-nhusb
Diff to: previous 1.1: preferred, colored
Changes since revision 1.1: +4 -4 lines
Sync with HEAD

Revision 1.2: download - view: text, markup, annotated - select for diffs
Mon Aug 24 22:21:26 2015 UTC (11 years, 2 months ago) by pooka
Branches: MAIN
CVS tags: nick-nhusb-base-20160319, nick-nhusb-base-20151226, nick-nhusb-base-20150921
Diff to: previous 1.1: preferred, colored
Changes since revision 1.1: +4 -4 lines
sprinkle _KERNEL_OPT

Revision 1.1.6.2: download - view: text, markup, annotated - select for diffs
Mon Jun 6 09:09:53 2011 UTC (15 years, 5 months ago) by jruoho
Branches: jruoho-x86intr
Diff to: previous 1.1.6.1: preferred, colored; branchpoint 1.1: preferred, colored; next MAIN 1.2: preferred, colored
Changes since revision 1.1.6.1: +230 -0 lines
Sync with HEAD.

Revision 1.1.2.2: download - view: text, markup, annotated - select for diffs
Thu Apr 21 01:42:13 2011 UTC (15 years, 7 months ago) by rmind
Branches: rmind-uvmplock
Diff to: previous 1.1.2.1: preferred, colored; branchpoint 1.1: preferred, colored; next MAIN 1.2: preferred, colored
Changes since revision 1.1.2.1: +230 -0 lines
sync with head

Revision 1.1.6.1
Thu Mar 31 19:40:52 2011 UTC (15 years, 7 months ago) by jruoho
Branches: jruoho-x86intr
FILE REMOVED
Changes since revision 1.1: +0 -230 lines
file rtbl.c was added on branch jruoho-x86intr on 2011-06-06 09:09:53 +0000

Revision 1.1.2.1
Thu Mar 31 19:40:52 2011 UTC (15 years, 7 months ago) by rmind
Branches: rmind-uvmplock
FILE REMOVED
Changes since revision 1.1: +0 -230 lines
file rtbl.c was added on branch rmind-uvmplock on 2011-04-21 01:42:13 +0000

Revision 1.1: download - view: text, markup, annotated - select for diffs
Thu Mar 31 19:40:52 2011 UTC (15 years, 7 months ago) by dyoung
Branches: MAIN
CVS tags: yamt-pagecache-tag8, yamt-pagecache-base9, yamt-pagecache-base8, yamt-pagecache-base7, yamt-pagecache-base6, yamt-pagecache-base5, yamt-pagecache-base4, yamt-pagecache-base3, yamt-pagecache-base2, yamt-pagecache-base, yamt-pagecache, tls-maxphys-base, tls-earlyentropy-base, tls-earlyentropy, rmind-uvmplock-nbase, rmind-uvmplock-base, rmind-smpnet-nbase, rmind-smpnet-base, rmind-smpnet, riastradh-xf86-video-intel-2-7-1-pre-2-21-15, riastradh-drm2-base3, riastradh-drm2-base2, riastradh-drm2-base1, riastradh-drm2-base, riastradh-drm2, nick-nhusb-base-20150606, nick-nhusb-base-20150406, nick-nhusb-base, netbsd-7-nhusb-base-20170116, netbsd-7-nhusb-base, netbsd-7-nhusb, netbsd-7-base, netbsd-7-2-RELEASE, netbsd-7-1-RELEASE, netbsd-7-1-RC2, netbsd-7-1-RC1, netbsd-7-1-2-RELEASE, netbsd-7-1-1-RELEASE, netbsd-7-1, netbsd-7-0-RELEASE, netbsd-7-0-RC3, netbsd-7-0-RC2, netbsd-7-0-RC1, netbsd-7-0-2-RELEASE, netbsd-7-0-1-RELEASE, netbsd-7-0, netbsd-7, netbsd-6-base, netbsd-6-1-RELEASE, netbsd-6-1-RC4, netbsd-6-1-RC3, netbsd-6-1-RC2, netbsd-6-1-RC1, netbsd-6-1-5-RELEASE, netbsd-6-1-4-RELEASE, netbsd-6-1-3-RELEASE, netbsd-6-1-2-RELEASE, netbsd-6-1-1-RELEASE, netbsd-6-1, netbsd-6-0-RELEASE, netbsd-6-0-RC2, netbsd-6-0-RC1, netbsd-6-0-6-RELEASE, netbsd-6-0-5-RELEASE, netbsd-6-0-4-RELEASE, netbsd-6-0-3-RELEASE, netbsd-6-0-2-RELEASE, netbsd-6-0-1-RELEASE, netbsd-6-0, netbsd-6, matt-nb6-plus-nbase, matt-nb6-plus-base, matt-nb6-plus, khorben-n900, jmcneill-usbmp-pre-base2, jmcneill-usbmp-base9, jmcneill-usbmp-base8, jmcneill-usbmp-base7, jmcneill-usbmp-base6, jmcneill-usbmp-base5, jmcneill-usbmp-base4, jmcneill-usbmp-base3, jmcneill-usbmp-base2, jmcneill-usbmp-base10, jmcneill-usbmp-base, jmcneill-usbmp, jmcneill-audiomp3-base, jmcneill-audiomp3, cherry-xenmp-base, cherry-xenmp, agc-symver-base, agc-symver
Branch point for: tls-maxphys, rmind-uvmplock, nick-nhusb, jruoho-x86intr
Hide the radix-trie implementation of the forwarding table so that we
will have an easier time replacing it with something different, even if
it is a second radix-trie implementation.

sys/net/route.c and sys/net/rtsock.c no longer operate directly on
radix_nodes or radix_node_heads.

Hopefully this will reduce the temptation to implement multipath or
source-based routing using grotty hacks to the grotty old radix-trie
code, too. :-)

Diff request

This form allows you to request diffs between any two revisions of a file. You may select a symbolic revision name using the selection box or you may type in a numeric name using the type-in text box.

Log view options

CVSweb <webmaster@jp.NetBSD.org>