summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authormav <mav@FreeBSD.org>2017-05-01 06:03:44 +0000
committermav <mav@FreeBSD.org>2017-05-01 06:03:44 +0000
commit34cc6eaf5677cd69d2f10eb83a5dfc4a35242298 (patch)
tree5bf7ebb880fefad85be0e531724c37a3dd957b02 /lib
parentca050d45e568414f39e74f571da232e4fdd820a1 (diff)
downloadFreeBSD-src-34cc6eaf5677cd69d2f10eb83a5dfc4a35242298.zip
FreeBSD-src-34cc6eaf5677cd69d2f10eb83a5dfc4a35242298.tar.gz
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.
Diffstat (limited to 'lib')
-rw-r--r--lib/libc/gen/telldir.c18
1 files changed, 14 insertions, 4 deletions
diff --git a/lib/libc/gen/telldir.c b/lib/libc/gen/telldir.c
index 19cd6ee..d322990 100644
--- a/lib/libc/gen/telldir.c
+++ b/lib/libc/gen/telldir.c
@@ -53,15 +53,22 @@ long
telldir(dirp)
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));
@@ -73,7 +80,10 @@ telldir(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)
OpenPOWER on IntegriCloud