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>