From owner-svn-src-all@freebsd.org Fri May 31 01:28:49 2019 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 87E3E15AFAB7; Fri, 31 May 2019 01:28:49 +0000 (UTC) (envelope-from rmacklem@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) server-signature RSA-PSS (4096 bits) client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 2C24575DB0; Fri, 31 May 2019 01:28:49 +0000 (UTC) (envelope-from rmacklem@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 073C0214AD; Fri, 31 May 2019 01:28:49 +0000 (UTC) (envelope-from rmacklem@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id x4V1SmRA047557; Fri, 31 May 2019 01:28:48 GMT (envelope-from rmacklem@FreeBSD.org) Received: (from rmacklem@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id x4V1Sme9047556; Fri, 31 May 2019 01:28:48 GMT (envelope-from rmacklem@FreeBSD.org) Message-Id: <201905310128.x4V1Sme9047556@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: rmacklem set sender to rmacklem@FreeBSD.org using -f From: Rick Macklem Date: Fri, 31 May 2019 01:28:48 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r348452 - head/usr.sbin/mountd X-SVN-Group: head X-SVN-Commit-Author: rmacklem X-SVN-Commit-Paths: head/usr.sbin/mountd X-SVN-Commit-Revision: 348452 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 2C24575DB0 X-Spamd-Bar: -- Authentication-Results: mx1.freebsd.org X-Spamd-Result: default: False [-2.95 / 15.00]; local_wl_from(0.00)[FreeBSD.org]; NEURAL_HAM_MEDIUM(-1.00)[-0.999,0]; NEURAL_HAM_SHORT(-0.95)[-0.952,0]; ASN(0.00)[asn:11403, ipnet:2610:1c1:1::/48, country:US]; NEURAL_HAM_LONG(-1.00)[-1.000,0] X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 31 May 2019 01:28:49 -0000 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 #include +#include #include #include #include @@ -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);