Module Name: src
Committed By: roy
Date: Fri Sep 11 14:59:22 UTC 2020
Modified Files:
src/sys/net: Makefile files.net
Added Files:
src/sys/net: nd.c nd.h
Log Message:
Implement address agnostic Neighbor Detection.
This is heavily based on IPv6 Neighbor Detection and allows per protocol
timers which also facilitate Neighor Unreachability Detection.
To generate a diff of this commit:
cvs rdiff -u -r1.43 -r1.44 src/sys/net/Makefile
cvs rdiff -u -r1.26 -r1.27 src/sys/net/files.net
cvs rdiff -u -r0 -r1.1 src/sys/net/nd.c src/sys/net/nd.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/net/Makefile
diff -u src/sys/net/Makefile:1.43 src/sys/net/Makefile:1.44
--- src/sys/net/Makefile:1.43 Thu Aug 20 21:21:32 2020
+++ src/sys/net/Makefile Fri Sep 11 14:59:22 2020
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.43 2020/08/20 21:21:32 riastradh Exp $
+# $NetBSD: Makefile,v 1.44 2020/09/11 14:59:22 roy Exp $
INCSDIR= /usr/include/net
@@ -6,8 +6,9 @@ INCS= bpf.h bpfjit.h bpfdesc.h dlt.h eth
if_bridgevar.h if_dl.h if_ether.h if_gif.h \
if_gre.h if_ieee1394.h if_ipsec.h if_llc.h if_media.h if_mpls.h \
if_pflog.h if_ppp.h if_pppoe.h if_l2tp.h if_sppp.h if_srt.h if_stats.h \
- if_stf.h if_tap.h if_tun.h if_types.h if_vlanvar.h if_wg.h net_stats.h \
- netisr.h pfil.h pfkeyv2.h pfvar.h ppp-comp.h ppp_defs.h radix.h \
+ if_stf.h if_tap.h if_tun.h if_types.h if_vlanvar.h if_wg.h \
+ nd.h net_stats.h netisr.h \
+ pfil.h pfkeyv2.h pfvar.h ppp-comp.h ppp_defs.h radix.h \
raw_cb.h route.h slcompress.h slip.h zlib.h
SUBDIR= agr npf
Index: src/sys/net/files.net
diff -u src/sys/net/files.net:1.26 src/sys/net/files.net:1.27
--- src/sys/net/files.net:1.26 Thu Aug 20 21:21:32 2020
+++ src/sys/net/files.net Fri Sep 11 14:59:22 2020
@@ -1,4 +1,4 @@
-# $NetBSD: files.net,v 1.26 2020/08/20 21:21:32 riastradh Exp $
+# $NetBSD: files.net,v 1.27 2020/09/11 14:59:22 roy Exp $
# XXX CLEANUP
define net
@@ -34,6 +34,7 @@ file net/if_tun.c tun
file net/if_vlan.c vlan needs-flag
file net/if_pppoe.c pppoe needs-flag
file net/if_wg.c wg needs-flag
+file net/nd.c inet | inet6
file net/pfil.c net
file net/ppp-deflate.c ppp & ppp_deflate
file net/ppp_tty.c ppp
Added files:
Index: src/sys/net/nd.c
diff -u /dev/null src/sys/net/nd.c:1.1
--- /dev/null Fri Sep 11 14:59:22 2020
+++ src/sys/net/nd.c Fri Sep 11 14:59:22 2020
@@ -0,0 +1,420 @@
+/* $NetBSD: */
+
+/*
+ * Copyright (c) 2020 The NetBSD Foundation, Inc.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Roy Marples.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD: nd.c,v 1.1 2020/09/11 14:59:22 roy Exp $");
+
+#include <sys/callout.h>
+#include <sys/mbuf.h>
+#include <sys/socketvar.h> /* for softnet_lock */
+
+#include <net/if_llatbl.h>
+#include <net/nd.h>
+#include <net/route.h>
+
+#include <netinet/in.h>
+#include <netinet/ip6.h>
+
+static struct nd_domain *nd_domains[AF_MAX];
+
+static int nd_gctimer = (60 * 60 * 24); /* 1 day: garbage collection timer */
+
+static void nd_set_timertick(struct llentry *, time_t);
+static struct nd_domain *nd_find_domain(int);
+
+static void
+nd_timer(void *arg)
+{
+ struct llentry *ln = arg;
+ struct nd_domain *nd;
+ struct ifnet *ifp = NULL;
+ struct psref psref;
+ struct mbuf *m = NULL;
+ bool send_ns = false, missed = false;
+ union nd_addr taddr, *daddrp = NULL;
+
+ SOFTNET_KERNEL_LOCK_UNLESS_NET_MPSAFE();
+ LLE_WLOCK(ln);
+
+ if (!(ln->la_flags & LLE_LINKED))
+ goto out;
+ if (ln->ln_ntick > 0) {
+ nd_set_timer(ln, ND_TIMER_TICK);
+ goto out;
+ }
+
+ nd = nd_find_domain(ln->lle_tbl->llt_af);
+ ifp = ln->lle_tbl->llt_ifp;
+ KASSERT(ifp != NULL);
+ if_acquire(ifp, &psref);
+
+ memcpy(&taddr, &ln->r_l3addr, sizeof(taddr));
+
+ switch (ln->ln_state) {
+ case ND_LLINFO_WAITDELETE:
+ LLE_REMREF(ln);
+ nd->nd_free(ln, 0);
+ ln = NULL;
+ break;
+
+ case ND_LLINFO_INCOMPLETE:
+ if (ln->ln_asked++ < nd->nd_mmaxtries) {
+ send_ns = true;
+ break;
+ }
+
+ if (ln->ln_hold) {
+ struct mbuf *m0, *mnxt;
+
+ /*
+ * Assuming every packet in ln_hold
+ * has the same IP header.
+ */
+ m = ln->ln_hold;
+ for (m0 = m->m_nextpkt; m0 != NULL; m0 = mnxt) {
+ mnxt = m0->m_nextpkt;
+ m0->m_nextpkt = NULL;
+ m_freem(m0);
+ }
+
+ m->m_nextpkt = NULL;
+ ln->ln_hold = NULL;
+ }
+
+ missed = true;
+ ln->ln_state = ND_LLINFO_WAITDELETE;
+ if (ln->ln_asked == nd->nd_mmaxtries)
+ nd_set_timer(ln, ND_TIMER_RETRANS);
+ else
+ send_ns = true;
+ break;
+
+ case ND_LLINFO_REACHABLE:
+ if (!ND_IS_LLINFO_PERMANENT(ln)) {
+ ln->ln_state = ND_LLINFO_STALE;
+ nd_set_timer(ln, ND_TIMER_GC);
+ }
+ break;
+
+ case ND_LLINFO_PURGE: /* FALLTHROUGH */
+ case ND_LLINFO_STALE:
+ if (!ND_IS_LLINFO_PERMANENT(ln)) {
+ LLE_REMREF(ln);
+ nd->nd_free(ln, 1);
+ ln = NULL;
+ }
+ break;
+
+ case ND_LLINFO_DELAY:
+ if (nd->nd_nud_enabled(ifp)) {
+ ln->ln_asked = 1;
+ ln->ln_state = ND_LLINFO_PROBE;
+ send_ns = true;
+ daddrp = &taddr;
+ } else {
+ ln->ln_state = ND_LLINFO_STALE;
+ nd_set_timer(ln, ND_TIMER_GC);
+ }
+ break;
+
+ case ND_LLINFO_PROBE:
+ if (ln->ln_asked < nd->nd_umaxtries) {
+ ln->ln_asked++;
+ send_ns = true;
+ daddrp = &taddr;
+ } else {
+ LLE_REMREF(ln);
+ nd->nd_free(ln, 0);
+ ln = NULL;
+ }
+ break;
+ }
+
+ if (send_ns) {
+ uint8_t lladdr[255], *lladdrp;
+ union nd_addr src, *psrc;
+
+ nd_set_timer(ln, ND_TIMER_RETRANS);
+ if (ln->ln_state > ND_LLINFO_INCOMPLETE &&
+ ln->la_flags & LLE_VALID)
+ {
+ KASSERT(sizeof(lladdr) >= ifp->if_addrlen);
+ memcpy(lladdr, &ln->ll_addr, ifp->if_addrlen);
+ lladdrp = lladdr;
+ } else
+ lladdrp = NULL;
+ psrc = nd->nd_holdsrc(ln, &src);
+ LLE_FREE_LOCKED(ln);
+ ln = NULL;
+ nd->nd_output(ifp, daddrp, &taddr, lladdrp, psrc);
+ }
+
+out:
+ if (ln != NULL)
+ LLE_FREE_LOCKED(ln);
+ SOFTNET_KERNEL_UNLOCK_UNLESS_NET_MPSAFE();
+
+ if (missed)
+ nd->nd_missed(ifp, &taddr, m);
+ if (ifp != NULL)
+ if_release(ifp, &psref);
+}
+
+static void
+nd_set_timertick(struct llentry *ln, time_t xtick)
+{
+
+ CTASSERT(sizeof(time_t) > sizeof(int));
+ KASSERT(xtick >= 0);
+
+ /*
+ * We have to take care of a reference leak which occurs if
+ * callout_reset overwrites a pending callout schedule. Unfortunately
+ * we don't have a mean to know the overwrite, so we need to know it
+ * using callout_stop. We need to call callout_pending first to exclude
+ * the case that the callout has never been scheduled.
+ */
+ if (callout_pending(&ln->la_timer)) {
+ bool expired;
+
+ expired = callout_stop(&ln->la_timer);
+ if (!expired)
+ LLE_REMREF(ln);
+ }
+
+ ln->ln_expire = time_uptime + xtick / hz;
+ LLE_ADDREF(ln);
+ if (xtick > INT_MAX) {
+ ln->ln_ntick = xtick - INT_MAX;
+ xtick = INT_MAX;
+ } else {
+ ln->ln_ntick = 0;
+ }
+ callout_reset(&ln->ln_timer_ch, xtick, nd_timer, ln);
+}
+
+void
+nd_set_timer(struct llentry *ln, int type)
+{
+ time_t xtick;
+ struct ifnet *ifp;
+ struct nd_domain *nd;
+
+ LLE_WLOCK_ASSERT(ln);
+
+ ifp = ln->lle_tbl->llt_ifp;
+ nd = nd_find_domain(ln->lle_tbl->llt_af);
+
+ switch (type) {
+ case ND_TIMER_IMMEDIATE:
+ xtick = 0;
+ break;
+ case ND_TIMER_TICK:
+ xtick = ln->ln_ntick;
+ break;
+ case ND_TIMER_RETRANS:
+ xtick = nd->nd_retrans(ifp) * hz / 1000;
+ break;
+ case ND_TIMER_REACHABLE:
+ xtick = nd->nd_reachable(ifp) * hz / 1000;
+ break;
+ case ND_TIMER_EXPIRE:
+ if (ln->ln_expire > time_uptime)
+ xtick = (ln->ln_expire - time_uptime) * hz;
+ else
+ xtick = nd_gctimer * hz;
+ break;
+ case ND_TIMER_DELAY:
+ xtick = nd->nd_delay * hz;
+ break;
+ case ND_TIMER_GC:
+ xtick = nd_gctimer * hz;
+ break;
+ default:
+ panic("%s: invalid timer type\n", __func__);
+ }
+
+ nd_set_timertick(ln, xtick);
+}
+
+int
+nd_resolve(struct llentry *ln, const struct rtentry *rt, struct mbuf *m,
+ uint8_t *lldst, size_t dstsize)
+{
+ struct ifnet *ifp;
+ struct nd_domain *nd;
+ int error;
+
+ LLE_WLOCK_ASSERT(ln);
+
+ ifp = ln->lle_tbl->llt_ifp;
+ nd = nd_find_domain(ln->lle_tbl->llt_af);
+
+ /* We don't have to do link-layer address resolution on a p2p link. */
+ if (ifp->if_flags & IFF_POINTOPOINT &&
+ ln->ln_state < ND_LLINFO_REACHABLE)
+ {
+ ln->ln_state = ND_LLINFO_STALE;
+ nd_set_timer(ln, ND_TIMER_GC);
+ }
+
+ /*
+ * The first time we send a packet to a neighbor whose entry is
+ * STALE, we have to change the state to DELAY and a sets a timer to
+ * expire in DELAY_FIRST_PROBE_TIME seconds to ensure do
+ * neighbor unreachability detection on expiration.
+ * (RFC 2461 7.3.3)
+ */
+ if (ln->ln_state == ND_LLINFO_STALE) {
+ ln->ln_asked = 0;
+ ln->ln_state = ND_LLINFO_DELAY;
+ nd_set_timer(ln, ND_TIMER_DELAY);
+ }
+
+ /*
+ * If the neighbor cache entry has a state other than INCOMPLETE
+ * (i.e. its link-layer address is already resolved), just
+ * send the packet.
+ */
+ if (ln->ln_state > ND_LLINFO_INCOMPLETE) {
+ KASSERT((ln->la_flags & LLE_VALID) != 0);
+ memcpy(lldst, &ln->ll_addr, MIN(dstsize, ifp->if_addrlen));
+ LLE_WUNLOCK(ln);
+ return 0;
+ }
+
+ /*
+ * There is a neighbor cache entry, but no ethernet address
+ * response yet. Append this latest packet to the end of the
+ * packet queue in the mbuf, unless the number of the packet
+ * does not exceed maxqueuelen. When it exceeds maxqueuelen,
+ * the oldest packet in the queue will be removed.
+ */
+ if (ln->ln_state == ND_LLINFO_NOSTATE ||
+ ln->ln_state == ND_LLINFO_WAITDELETE)
+ ln->ln_state = ND_LLINFO_INCOMPLETE;
+
+ if (ln->ln_hold != NULL) {
+ struct mbuf *m_hold;
+ int i;
+
+ i = 0;
+ for (m_hold = ln->ln_hold; m_hold; m_hold = m_hold->m_nextpkt) {
+ i++;
+ if (m_hold->m_nextpkt == NULL) {
+ m_hold->m_nextpkt = m;
+ break;
+ }
+ }
+ while (i >= nd->nd_maxqueuelen) {
+ m_hold = ln->ln_hold;
+ ln->ln_hold = ln->ln_hold->m_nextpkt;
+ m_freem(m_hold);
+ i--;
+ }
+ } else
+ ln->ln_hold = m;
+
+ if (ln->ln_asked >= nd->nd_mmaxtries)
+ error = (rt != NULL && rt->rt_flags & RTF_GATEWAY) ?
+ EHOSTUNREACH : EHOSTDOWN;
+ else
+ error = EWOULDBLOCK;
+
+ /*
+ * If there has been no NS for the neighbor after entering the
+ * INCOMPLETE state, send the first solicitation.
+ */
+ if (!ND_IS_LLINFO_PERMANENT(ln) && ln->ln_asked == 0) {
+ struct psref psref;
+ union nd_addr dst, src, *psrc;
+
+ ln->ln_asked++;
+ nd_set_timer(ln, ND_TIMER_RETRANS);
+ memcpy(&dst, &ln->r_l3addr, sizeof(dst));
+ psrc = nd->nd_holdsrc(ln, &src);
+ if_acquire(ifp, &psref);
+ LLE_WUNLOCK(ln);
+
+ nd->nd_output(ifp, NULL, &dst, NULL, psrc);
+ if_release(ifp, &psref);
+ } else
+ LLE_WUNLOCK(ln);
+
+ return error;
+}
+
+void
+nd_nud_hint(struct llentry *ln)
+{
+ struct nd_domain *nd;
+
+ if (ln == NULL)
+ return;
+
+ LLE_WLOCK_ASSERT(ln);
+
+ if (ln->ln_state < ND_LLINFO_REACHABLE)
+ goto done;
+
+ nd = nd_find_domain(ln->lle_tbl->llt_af);
+
+ /*
+ * if we get upper-layer reachability confirmation many times,
+ * it is possible we have false information.
+ */
+ ln->ln_byhint++;
+ if (ln->ln_byhint > nd->nd_maxnudhint)
+ goto done;
+
+ ln->ln_state = ND_LLINFO_REACHABLE;
+ if (!ND_IS_LLINFO_PERMANENT(ln))
+ nd_set_timer(ln, ND_TIMER_REACHABLE);
+
+done:
+ LLE_WUNLOCK(ln);
+
+ return;
+}
+
+static struct nd_domain *
+nd_find_domain(int af)
+{
+
+ KASSERT(af < __arraycount(nd_domains) && nd_domains[af] != NULL);
+ return nd_domains[af];
+}
+
+void
+nd_attach_domain(struct nd_domain *nd)
+{
+
+ KASSERT(nd->nd_family < __arraycount(nd_domains));
+ nd_domains[nd->nd_family] = nd;
+}
Index: src/sys/net/nd.h
diff -u /dev/null src/sys/net/nd.h:1.1
--- /dev/null Fri Sep 11 14:59:22 2020
+++ src/sys/net/nd.h Fri Sep 11 14:59:22 2020
@@ -0,0 +1,98 @@
+/* $NetBSD: nd.h,v 1.1 2020/09/11 14:59:22 roy Exp $ */
+
+/*
+ * Copyright (c) 2020 The NetBSD Foundation, Inc.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Roy Marples.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _NET_ND_H_
+#define _NET_ND_H_
+
+/* ND LLINFO states */
+#define ND_LLINFO_PURGE -3
+#define ND_LLINFO_NOSTATE -2
+#define ND_LLINFO_WAITDELETE -1
+#define ND_LLINFO_INCOMPLETE 0
+#define ND_LLINFO_REACHABLE 1
+#define ND_LLINFO_STALE 2
+#define ND_LLINFO_DELAY 3
+#define ND_LLINFO_PROBE 4
+
+#ifdef _KERNEL
+#define ND_IS_LLINFO_PROBREACH(ln) \
+ ((ln)->ln_state > ND_LLINFO_INCOMPLETE)
+#define ND_IS_LLINFO_PERMANENT(ln) \
+ (((ln)->ln_expire == 0) && ((ln)->ln_state > ND_LLINFO_INCOMPLETE))
+
+/* ND timer types */
+#define ND_TIMER_IMMEDIATE 0
+#define ND_TIMER_TICK 1
+#define ND_TIMER_REACHABLE 2
+#define ND_TIMER_RETRANS 3
+#define ND_TIMER_EXPIRE 4
+#define ND_TIMER_DELAY 5
+#define ND_TIMER_GC 6
+
+/* node constants */
+#define MAX_REACHABLE_TIME 3600000 /* msec */
+#define REACHABLE_TIME 30000 /* msec */
+#define RETRANS_TIMER 1000 /* msec */
+#define MIN_RANDOM_FACTOR 512 /* 1024 * 0.5 */
+#define MAX_RANDOM_FACTOR 1536 /* 1024 * 1.5 */
+#define ND_COMPUTE_RTIME(x) \
+ ((MIN_RANDOM_FACTOR * (x >> 10)) + (cprng_fast32() & \
+ ((MAX_RANDOM_FACTOR - MIN_RANDOM_FACTOR) * (x >> 10))))
+
+#include <netinet/in.h>
+union nd_addr {
+ struct in_addr nd_addr4;
+ struct in6_addr nd_addr6;
+};
+
+struct nd_domain {
+ int nd_family;
+ int nd_delay; /* delay first probe time in seconds */
+ int nd_mmaxtries; /* maximum multicast query */
+ int nd_umaxtries; /* maximum unicast query */
+ int nd_maxnudhint; /* max # of subsequent upper layer hints */
+ int nd_maxqueuelen; /* max # of packets in unresolved ND entries */
+ bool (*nd_nud_enabled)(struct ifnet *);
+ unsigned int (*nd_reachable)(struct ifnet *); /* msec */
+ unsigned int (*nd_retrans)(struct ifnet *); /* msec */
+ union nd_addr *(*nd_holdsrc)(struct llentry *, union nd_addr *);
+ void (*nd_output)(struct ifnet *, const union nd_addr *,
+ const union nd_addr *, const uint8_t *, const union nd_addr *);
+ void (*nd_missed)(struct ifnet *, const union nd_addr *, struct mbuf *);
+ void (*nd_free)(struct llentry *, int);
+};
+
+int nd_resolve(struct llentry *, const struct rtentry *, struct mbuf *,
+ uint8_t *, size_t);
+void nd_set_timer(struct llentry *, int);
+void nd_nud_hint(struct llentry *);
+
+void nd_attach_domain(struct nd_domain *);
+#endif /* !_KERNEL */
+#endif /* !_NET_ND_H_ */
