From owner-svn-src-all@freebsd.org Mon Apr 17 19:03:32 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 76770D41425; Mon, 17 Apr 2017 19:03:32 +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 2FD2C1C41; Mon, 17 Apr 2017 19:03:32 +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 v3HJ3VaR060624; Mon, 17 Apr 2017 19:03:31 GMT (envelope-from mav@FreeBSD.org) Received: (from mav@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id v3HJ3VNA060623; Mon, 17 Apr 2017 19:03:31 GMT (envelope-from mav@FreeBSD.org) Message-Id: <201704171903.v3HJ3VNA060623@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: mav set sender to mav@FreeBSD.org using -f From: Alexander Motin Date: Mon, 17 Apr 2017 19:03:31 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r317064 - head/lib/libc/gen X-SVN-Group: head 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, 17 Apr 2017 19:03:32 -0000 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)