From a94f79fae55276f08e1d17550c5c518aee500604 Mon Sep 17 00:00:00 2001 From: mav Date: Mon, 1 May 2017 06:03:07 +0000 Subject: [PATCH] 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. --- lib/libc/gen/telldir.c | 18 ++++++++++++++---- 1 file changed, 14 insertions(+), 4 deletions(-) diff --git a/lib/libc/gen/telldir.c b/lib/libc/gen/telldir.c index 3e5678cf2eb..26febe27d6c 100644 --- a/lib/libc/gen/telldir.c +++ b/lib/libc/gen/telldir.c @@ -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) -- 2.45.0