Author: mav
Date: Mon May 1 06:03:07 2017
New Revision: 317633
URL: https://svnweb.freebsd.org/changeset/base/317633
Log:
MFC r317064: Optimize pathologic case of telldir() for Samba.
When application reads large directory, calling telldir() for each entry,
like Samba does, it creates exponential performance drop as number of
entries reach tenths to hundreds of thousands. It is caused by full search
through the internal list, that never finds matches in that scenario, but
creates O(n^2) delays. This patch optimizes that search, limiting it to
entries of the same buffer, turning time closer to O(n) in case of linear
directory scan.
Modified:
stable/11/lib/libc/gen/telldir.c
Directory Properties:
stable/11/ (props changed)
Modified: stable/11/lib/libc/gen/telldir.c
==============================================================================
--- stable/11/lib/libc/gen/telldir.c Mon May 1 05:59:52 2017
(r317632)
+++ stable/11/lib/libc/gen/telldir.c Mon May 1 06:03:07 2017
(r317633)
@@ -52,15 +52,22 @@ __FBSDID("$FreeBSD$");
long
telldir(DIR *dirp)
{
- struct ddloc *lp;
+ struct ddloc *lp, *flp;
long idx;
if (__isthreaded)
_pthread_mutex_lock(&dirp->dd_lock);
+ flp = NULL;
LIST_FOREACH(lp, &dirp->dd_td->td_locq, loc_lqe) {
- if (lp->loc_seek == dirp->dd_seek &&
- lp->loc_loc == dirp->dd_loc)
+ if (lp->loc_seek == dirp->dd_seek) {
+ if (flp == NULL)
+ flp = lp;
+ if (lp->loc_loc == dirp->dd_loc)
+ break;
+ } else if (flp != NULL) {
+ lp = NULL;
break;
+ }
}
if (lp == NULL) {
lp = malloc(sizeof(struct ddloc));
@@ -72,7 +79,10 @@ telldir(DIR *dirp)
lp->loc_index = dirp->dd_td->td_loccnt++;
lp->loc_seek = dirp->dd_seek;
lp->loc_loc = dirp->dd_loc;
- LIST_INSERT_HEAD(&dirp->dd_td->td_locq, lp, loc_lqe);
+ if (flp != NULL)
+ LIST_INSERT_BEFORE(flp, lp, loc_lqe);
+ else
+ LIST_INSERT_HEAD(&dirp->dd_td->td_locq, lp, loc_lqe);
}
idx = lp->loc_index;
if (__isthreaded)
_______________________________________________
svn-src-all@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
