[src/trunk]: src/sys/net Import lltable/llentry from FreeBSD

[ozaki-r <ozaki-r%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/a112bd0167a3
branches:  trunk
changeset: 810456:a112bd0167a3
user:      ozaki-r <ozaki-r%NetBSD.org@localhost>
date:      Mon Aug 31 07:56:58 2015 +0000

description:
Import lltable/llentry from FreeBSD

lltable/llentry is new L2 nexthop cache data structures that
store caches in each interface (struct ifnet). It is imported
to replace the current ARP cache implementation that uses the
global list with the big kernel lock, and provide fine-grain
locking for cache operations. It is also planned to replace
NDP caches.

The code is based on FreeBSD's lltable/llentry as of r286629
and tweaked for NetBSD.

diffstat:

 sys/net/if_llatbl.c |  750 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 sys/net/if_llatbl.h |  261 ++++++++++++++++++
 2 files changed, 1011 insertions(+), 0 deletions(-)

diffs (truncated from 1019 to 300 lines):

diff -r 2e9217bfa47d -r a112bd0167a3 sys/net/if_llatbl.c
--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
+++ b/sys/net/if_llatbl.c       Mon Aug 31 07:56:58 2015 +0000
@@ -0,0 +1,750 @@
+/*     $NetBSD: if_llatbl.c,v 1.1 2015/08/31 07:56:58 ozaki-r Exp $    */
+/*
+ * Copyright (c) 2004 Luigi Rizzo, Alessandro Cerri. All rights reserved.
+ * Copyright (c) 2004-2008 Qing Li. All rights reserved.
+ * Copyright (c) 2008 Kip Macy. All rights reserved.
+ * Copyright (c) 2015 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * 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 AUTHOR AND CONTRIBUTORS ``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 AUTHOR OR CONTRIBUTORS 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>
+
+#ifdef _KERNEL_OPT
+#include "opt_ddb.h"
+#include "opt_inet.h"
+#include "opt_inet6.h"
+#endif
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/malloc.h>
+#include <sys/mbuf.h>
+#include <sys/syslog.h>
+#include <sys/sysctl.h>
+#include <sys/socket.h>
+#include <sys/kernel.h>
+#include <sys/lock.h>
+#include <sys/mutex.h>
+#include <sys/rwlock.h>
+
+#ifdef DDB
+#include <ddb/ddb.h>
+#endif
+
+#include <netinet/in.h>
+#include <net/if_llatbl.h>
+#include <net/if.h>
+#include <net/if_dl.h>
+#include <net/route.h>
+#include <netinet/if_inarp.h>
+#include <netinet6/in6_var.h>
+#include <netinet6/nd6.h>
+
+static SLIST_HEAD(, lltable) lltables;
+krwlock_t lltable_rwlock;
+
+static void lltable_unlink(struct lltable *llt);
+static void llentries_unlink(struct lltable *llt, struct llentries *head);
+
+static void htable_unlink_entry(struct llentry *lle);
+static void htable_link_entry(struct lltable *llt, struct llentry *lle);
+static int htable_foreach_lle(struct lltable *llt, llt_foreach_cb_t *f,
+    void *farg);
+
+/*
+ * Dump lle state for a specific address family.
+ */
+static int
+lltable_dump_af(struct lltable *llt, struct sysctl_req *wr)
+{
+       int error;
+
+       LLTABLE_LOCK_ASSERT();
+
+       if (llt->llt_ifp->if_flags & IFF_LOOPBACK)
+               return (0);
+       error = 0;
+
+       IF_AFDATA_RLOCK(llt->llt_ifp);
+       error = lltable_foreach_lle(llt,
+           (llt_foreach_cb_t *)llt->llt_dump_entry, wr);
+       IF_AFDATA_RUNLOCK(llt->llt_ifp);
+
+       return (error);
+}
+
+/*
+ * Dump arp state for a specific address family.
+ */
+int
+lltable_sysctl_dumparp(int af, struct sysctl_req *wr)
+{
+       struct lltable *llt;
+       int error = 0;
+
+       LLTABLE_RLOCK();
+       SLIST_FOREACH(llt, &lltables, llt_link) {
+               if (llt->llt_af == af) {
+                       error = lltable_dump_af(llt, wr);
+                       if (error != 0)
+                               goto done;
+               }
+       }
+done:
+       LLTABLE_RUNLOCK();
+       return (error);
+}
+
+/*
+ * Common function helpers for chained hash table.
+ */
+
+/*
+ * Runs specified callback for each entry in @llt.
+ * Caller does the locking.
+ *
+ */
+static int
+htable_foreach_lle(struct lltable *llt, llt_foreach_cb_t *f, void *farg)
+{
+       struct llentry *lle, *next;
+       int i, error;
+
+       error = 0;
+
+       for (i = 0; i < llt->llt_hsize; i++) {
+               LIST_FOREACH_SAFE(lle, &llt->lle_head[i], lle_next, next) {
+                       error = f(llt, lle, farg);
+                       if (error != 0)
+                               break;
+               }
+       }
+
+       return (error);
+}
+
+static void
+htable_link_entry(struct lltable *llt, struct llentry *lle)
+{
+       struct llentries *lleh;
+       uint32_t hashidx;
+
+       if ((lle->la_flags & LLE_LINKED) != 0)
+               return;
+
+       IF_AFDATA_WLOCK_ASSERT(llt->llt_ifp);
+
+       hashidx = llt->llt_hash(lle, llt->llt_hsize);
+       lleh = &llt->lle_head[hashidx];
+
+       lle->lle_tbl  = llt;
+       lle->lle_head = lleh;
+       lle->la_flags |= LLE_LINKED;
+       LIST_INSERT_HEAD(lleh, lle, lle_next);
+}
+
+static void
+htable_unlink_entry(struct llentry *lle)
+{
+
+       if ((lle->la_flags & LLE_LINKED) != 0) {
+               IF_AFDATA_WLOCK_ASSERT(lle->lle_tbl->llt_ifp);
+               LIST_REMOVE(lle, lle_next);
+               lle->la_flags &= ~(LLE_VALID | LLE_LINKED);
+#if 0
+               lle->lle_tbl = NULL;
+               lle->lle_head = NULL;
+#endif
+       }
+}
+
+struct prefix_match_data {
+       const struct sockaddr *prefix;
+       const struct sockaddr *mask;
+       struct llentries dchain;
+       u_int flags;
+};
+
+static int
+htable_prefix_free_cb(struct lltable *llt, struct llentry *lle, void *farg)
+{
+       struct prefix_match_data *pmd;
+
+       pmd = (struct prefix_match_data *)farg;
+
+       if (llt->llt_match_prefix(pmd->prefix, pmd->mask, pmd->flags, lle)) {
+               LLE_WLOCK(lle);
+               LIST_INSERT_HEAD(&pmd->dchain, lle, lle_chain);
+       }
+
+       return (0);
+}
+
+static void
+htable_prefix_free(struct lltable *llt, const struct sockaddr *prefix,
+    const struct sockaddr *mask, u_int flags)
+{
+       struct llentry *lle, *next;
+       struct prefix_match_data pmd;
+
+       memset(&pmd, 0, sizeof(pmd));
+       pmd.prefix = prefix;
+       pmd.mask = mask;
+       pmd.flags = flags;
+       LIST_INIT(&pmd.dchain);
+
+       IF_AFDATA_WLOCK(llt->llt_ifp);
+       /* Push matching lles to chain */
+       lltable_foreach_lle(llt, htable_prefix_free_cb, &pmd);
+
+       llentries_unlink(llt, &pmd.dchain);
+       IF_AFDATA_WUNLOCK(llt->llt_ifp);
+
+       LIST_FOREACH_SAFE(lle, &pmd.dchain, lle_chain, next)
+               llt->llt_free_entry(llt, lle);
+}
+
+static void
+htable_free_tbl(struct lltable *llt)
+{
+
+       free(llt->lle_head, M_LLTABLE);
+       free(llt, M_LLTABLE);
+}
+
+static void
+llentries_unlink(struct lltable *llt, struct llentries *head)
+{
+       struct llentry *lle, *next;
+
+       LIST_FOREACH_SAFE(lle, head, lle_chain, next)
+               llt->llt_unlink_entry(lle);
+}
+
+/*
+ * Helper function used to drop all mbufs in hold queue.
+ *
+ * Returns the number of held packets, if any, that were dropped.
+ */
+size_t
+lltable_drop_entry_queue(struct llentry *lle)
+{
+       size_t pkts_dropped;
+       struct mbuf *next;
+
+       LLE_WLOCK_ASSERT(lle);
+
+       pkts_dropped = 0;
+       while ((lle->la_numheld > 0) && (lle->la_hold != NULL)) {
+               next = lle->la_hold->m_nextpkt;
+               m_freem(lle->la_hold);
+               lle->la_hold = next;
+               lle->la_numheld--;
+               pkts_dropped++;
+       }
+
+       KASSERTMSG(lle->la_numheld == 0,
+               "la_numheld %d > 0, pkts_droped %zd",
+                lle->la_numheld, pkts_dropped);
+
+       return (pkts_dropped);
+}
+
+/*
+ * Deletes an address from the address table.
+ * This function is called by the timer functions
+ * such as arptimer() and nd6_llinfo_timer(), and
+ * the caller does the locking.
+ *
+ * Returns the number of held packets, if any, that were dropped.
+ */
+size_t
+llentry_free(struct llentry *lle)
+{
+       struct lltable *llt;
+       size_t pkts_dropped;
+
+       LLE_WLOCK_ASSERT(lle);
+
+       if ((lle->la_flags & LLE_LINKED) != 0) {
+               llt = lle->lle_tbl;
+
+               IF_AFDATA_WLOCK_ASSERT(llt->llt_ifp);
+               llt->llt_unlink_entry(lle);
+       }
+
+       pkts_dropped = lltable_drop_entry_queue(lle);