svn commit: r317064 - head/lib/libc/gen

[Alexander Motin]

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)