Date: Mon, 17 Apr 2017 19:03:31 +0000 (UTC) From: Alexander Motin <mav@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r317064 - head/lib/libc/gen Message-ID: <201704171903.v3HJ3VNA060623@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: mav Date: Mon Apr 17 19:03:31 2017 New Revision: 317064 URL: https://svnweb.freebsd.org/changeset/base/317064 Log: 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. PR: 218622 Reviewed by: jhb, jilles MFC after: 2 weeks Sponsored by: iXsystems, Inc. Differential Revision: https://reviews.freebsd.org/D10408 Modified: head/lib/libc/gen/telldir.c Modified: head/lib/libc/gen/telldir.c ============================================================================== --- head/lib/libc/gen/telldir.c Mon Apr 17 18:57:26 2017 (r317063) +++ head/lib/libc/gen/telldir.c Mon Apr 17 19:03:31 2017 (r317064) @@ -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)
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201704171903.v3HJ3VNA060623>