Skip site navigation (1)Skip section navigation (2)
Date:      Fri, 31 May 2019 01:28:48 +0000 (UTC)
From:      Rick Macklem <rmacklem@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r348452 - head/usr.sbin/mountd
Message-ID:  <201905310128.x4V1Sme9047556@repo.freebsd.org>

next in thread | raw e-mail | index | archive | help
Author: rmacklem
Date: Fri May 31 01:28:48 2019
New Revision: 348452
URL: https://svnweb.freebsd.org/changeset/base/348452

Log:
  Replace a single linked list with a hash table of lists.
  
  mountd.c uses a single linked list of "struct exportlist" structures,
  where there is one of these for each exported file system on the NFS server.
  This list gets long if there are a large number of file systems exported and
  the list must be searched for each line in the exports file(s) when
  SIGHUP causes the exports file(s) to be reloaded.
  A simple benchmark that traverses SLIST() elements and compares two 32bit
  fields in the structure for equal (which is what the search is)
  appears to take a couple of nsec. So, for a server with 72000 exported file
  systems, this can take about 5sec during reload of the exports file(s).
  By replacing the single linked list with a hash table with a target of
  10 elements per list, the time should be reduced to less than 1msec.
  Peter Errikson (who has a server with 72000+ exported file systems) ran
  a test program using 5 hashes to see how they worked.
  fnv_32_buf(fsid,..., 0)
  fnv_32_buf(fsid,..., FNV1_32_INIT)
  hash32_buf(fsid,..., 0)
  hash32_buf(fsid,..., HASHINIT)
  - plus simply using the low order bits of fsid.val[0].
  The first three behaved about equally well, with the first one being
  slightly better than the others.
  It has an average variation of about 4.5% about the target list length
  and that is what this patch uses.
  Peter Errikson also tested this hash table version and found that the
  performance wasn't measurably improved by a larger hash table, so a
  load factor of 10 appears adequate.
  
  Tested by:	pen@lysator.liu.se (with other patches)
  PR:		237860
  MFC after:	1 month

Modified:
  head/usr.sbin/mountd/mountd.c

Modified: head/usr.sbin/mountd/mountd.c
==============================================================================
--- head/usr.sbin/mountd/mountd.c	Fri May 31 00:56:31 2019	(r348451)
+++ head/usr.sbin/mountd/mountd.c	Fri May 31 01:28:48 2019	(r348452)
@@ -49,6 +49,7 @@ __FBSDID("$FreeBSD$");
 
 #include <sys/param.h>
 #include <sys/fcntl.h>
+#include <sys/fnv_hash.h>
 #include <sys/linker.h>
 #include <sys/module.h>
 #include <sys/mount.h>
@@ -234,7 +235,9 @@ static int	xdr_fhs(XDR *, caddr_t);
 static int	xdr_mlist(XDR *, caddr_t);
 static void	terminate(int);
 
-static struct exportlisthead exphead = SLIST_HEAD_INITIALIZER(&exphead);
+#define	EXPHASH(f)	(fnv_32_buf((f), sizeof(fsid_t), 0) % exphashsize)
+static struct exportlisthead *exphead = NULL;
+static int exphashsize = 0;
 static SLIST_HEAD(, mountlist) mlhead = SLIST_HEAD_INITIALIZER(&mlhead);
 static char *exnames_default[2] = { _PATH_EXPORTS, NULL };
 static char **exnames;
@@ -1092,7 +1095,7 @@ mntsrv(struct svc_req *rqstp, SVCXPRT *transp)
 		if (bad)
 			ep = NULL;
 		else
-			ep = ex_search(&fsb.f_fsid, &exphead);
+			ep = ex_search(&fsb.f_fsid, exphead);
 		hostset = defset = 0;
 		if (ep && (chk_host(ep->ex_defdir, saddr, &defset, &hostset,
 		    &numsecflavors, &secflavorsp) ||
@@ -1307,21 +1310,23 @@ xdr_explist_common(XDR *xdrsp, caddr_t cp __unused, in
 	int false = 0;
 	int putdef;
 	sigset_t sighup_mask;
+	int i;
 
 	sigemptyset(&sighup_mask);
 	sigaddset(&sighup_mask, SIGHUP);
 	sigprocmask(SIG_BLOCK, &sighup_mask, NULL);
 
-	SLIST_FOREACH(ep, &exphead, entries) {
-		putdef = 0;
-		if (put_exlist(ep->ex_dirl, xdrsp, ep->ex_defdir,
-			       &putdef, brief))
-			goto errout;
-		if (ep->ex_defdir && putdef == 0 &&
-			put_exlist(ep->ex_defdir, xdrsp, (struct dirlist *)NULL,
-			&putdef, brief))
-			goto errout;
-	}
+	for (i = 0; i < exphashsize; i++)
+		SLIST_FOREACH(ep, &exphead[i], entries) {
+			putdef = 0;
+			if (put_exlist(ep->ex_dirl, xdrsp, ep->ex_defdir,
+				       &putdef, brief))
+				goto errout;
+			if (ep->ex_defdir && putdef == 0 &&
+				put_exlist(ep->ex_defdir, xdrsp, NULL,
+				&putdef, brief))
+				goto errout;
+		}
 	sigprocmask(SIG_UNBLOCK, &sighup_mask, NULL);
 	if (!xdr_bool(xdrsp, &false))
 		return (0);
@@ -1545,7 +1550,7 @@ get_exportlist_one(void)
 					 * See if this directory is already
 					 * in the list.
 					 */
-					ep = ex_search(&fsb.f_fsid, &exphead);
+					ep = ex_search(&fsb.f_fsid, exphead);
 					if (ep == (struct exportlist *)NULL) {
 					    ep = get_exp();
 					    ep->ex_fs = fsb.f_fsid;
@@ -1700,7 +1705,7 @@ get_exportlist_one(void)
 		}
 		dirhead = (struct dirlist *)NULL;
 		if ((ep->ex_flag & EX_LINKED) == 0) {
-			insert_exports(ep, &exphead);
+			insert_exports(ep, exphead);
 
 			ep->ex_flag |= EX_LINKED;
 		}
@@ -1739,7 +1744,8 @@ get_exportlist(void)
 	/*
 	 * First, get rid of the old list
 	 */
-	free_exports(&exphead);
+	if (exphead != NULL)
+		free_exports(exphead);
 
 	/*
 	 * and the old V4 root dir.
@@ -1762,6 +1768,21 @@ get_exportlist(void)
 	 */
 	num = getmntinfo(&mntbufp, MNT_NOWAIT);
 
+	/* Allocate hash tables, for first call. */
+	if (exphead == NULL) {
+		/* Target an average linked list length of 10. */
+		exphashsize = num / 10;
+		if (exphashsize < 1)
+			exphashsize = 1;
+		else if (exphashsize > 100000)
+			exphashsize = 100000;
+		exphead = malloc(exphashsize * sizeof(*exphead));
+		if (exphead == NULL)
+			errx(1, "Can't malloc hash table");
+
+		for (i = 0; i < exphashsize; i++)
+			SLIST_INIT(&exphead[i]);
+	}
 	if (num > 0) {
 		build_iovec(&iov, &iovlen, "fstype", NULL, 0);
 		build_iovec(&iov, &iovlen, "fspath", NULL, 0);
@@ -1806,8 +1827,10 @@ get_exportlist(void)
 static void
 insert_exports(struct exportlist *ep, struct exportlisthead *exhp)
 {
+	uint32_t i;
 
-	SLIST_INSERT_HEAD(exhp, ep, entries);
+	i = EXPHASH(&ep->ex_fs);
+	SLIST_INSERT_HEAD(&exhp[i], ep, entries);
 }
 
 /*
@@ -1817,12 +1840,15 @@ static void
 free_exports(struct exportlisthead *exhp)
 {
 	struct exportlist *ep, *ep2;
+	int i;
 
-	SLIST_FOREACH_SAFE(ep, exhp, entries, ep2) {
-		SLIST_REMOVE(exhp, ep, exportlist, entries);
-		free_exp(ep);
+	for (i = 0; i < exphashsize; i++) {
+		SLIST_FOREACH_SAFE(ep, &exhp[i], entries, ep2) {
+			SLIST_REMOVE(&exhp[i], ep, exportlist, entries);
+			free_exp(ep);
+		}
+		SLIST_INIT(&exhp[i]);
 	}
-	SLIST_INIT(exhp);
 }
 
 /*
@@ -1962,8 +1988,10 @@ static struct exportlist *
 ex_search(fsid_t *fsid, struct exportlisthead *exhp)
 {
 	struct exportlist *ep;
+	uint32_t i;
 
-	SLIST_FOREACH(ep, exhp, entries) {
+	i = EXPHASH(fsid);
+	SLIST_FOREACH(ep, &exhp[i], entries) {
 		if (ep->ex_fs.val[0] == fsid->val[0] &&
 		    ep->ex_fs.val[1] == fsid->val[1])
 			return (ep);



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201905310128.x4V1Sme9047556>