From owner-svn-src-all@freebsd.org Mon May 1 06:03:09 2017 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 6E7F7D58DA8; Mon, 1 May 2017 06:03:09 +0000 (UTC) (envelope-from mav@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 27CF815BD; Mon, 1 May 2017 06:03:09 +0000 (UTC) (envelope-from mav@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id v41638wF089419; Mon, 1 May 2017 06:03:08 GMT (envelope-from mav@FreeBSD.org) Received: (from mav@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id v41638tq089418; Mon, 1 May 2017 06:03:08 GMT (envelope-from mav@FreeBSD.org) Message-Id: <201705010603.v41638tq089418@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: mav set sender to mav@FreeBSD.org using -f From: Alexander Motin Date: Mon, 1 May 2017 06:03:08 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-11@freebsd.org Subject: svn commit: r317633 - stable/11/lib/libc/gen X-SVN-Group: stable-11 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 01 May 2017 06:03:09 -0000 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)