From owner-freebsd-bugs@FreeBSD.ORG  Sat May  7 09:40:08 2011
Return-Path: <owner-freebsd-bugs@FreeBSD.ORG>
Delivered-To: freebsd-bugs@hub.freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 4D98C106564A
	for <freebsd-bugs@hub.freebsd.org>;
	Sat,  7 May 2011 09:40:08 +0000 (UTC)
	(envelope-from gnats@FreeBSD.org)
Received: from freefall.freebsd.org (freefall.freebsd.org
	[IPv6:2001:4f8:fff6::28])
	by mx1.freebsd.org (Postfix) with ESMTP id 38F6B8FC13
	for <freebsd-bugs@hub.freebsd.org>;
	Sat,  7 May 2011 09:40:08 +0000 (UTC)
Received: from freefall.freebsd.org (localhost [127.0.0.1])
	by freefall.freebsd.org (8.14.4/8.14.4) with ESMTP id p479e85S015746
	for <freebsd-bugs@freefall.freebsd.org>; Sat, 7 May 2011 09:40:08 GMT
	(envelope-from gnats@freefall.freebsd.org)
Received: (from gnats@localhost)
	by freefall.freebsd.org (8.14.4/8.14.4/Submit) id p479e8Wv015745;
	Sat, 7 May 2011 09:40:08 GMT (envelope-from gnats)
Date: Sat, 7 May 2011 09:40:08 GMT
Message-Id: <201105070940.p479e8Wv015745@freefall.freebsd.org>
To: freebsd-bugs@FreeBSD.org
From: Gordon Tetlow <gordon@tetlows.org>
Cc: 
Subject: Re: kern/75855: [libc] getpwent(3) functions on 5.3 with large
 password file extremely slow
X-BeenThere: freebsd-bugs@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
Reply-To: Gordon Tetlow <gordon@tetlows.org>
List-Id: Bug reports <freebsd-bugs.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-bugs>,
	<mailto:freebsd-bugs-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-bugs>
List-Post: <mailto:freebsd-bugs@freebsd.org>
List-Help: <mailto:freebsd-bugs-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-bugs>,
	<mailto:freebsd-bugs-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sat, 07 May 2011 09:40:08 -0000

The following reply was made to PR kern/75855; it has been noted by GNATS.

From: Gordon Tetlow <gordon@tetlows.org>
To: bug-followup@FreeBSD.org, bruce@engmail.uwaterloo.ca
Cc:  
Subject: Re: kern/75855: [libc] getpwent(3) functions on 5.3 with large
 password file extremely slow
Date: Sat, 7 May 2011 01:59:52 -0700

 The reason for this is how the compat code scans the password table
 looking for compat entries. The algorithm is O(m * n) where m is the
 number of entries to lookup (in the case of the ls -l /home) and n is
 the number of lines in the password database. This is clearly
 pessimized and should be able to be better optimized.
 
 The current logic is something like:
 
 scan each entry in the passwd db:
   if it starts with '+/-' do compat checking
   if the key matches, return
 
 The logic for files is something like:
 Lookup exact entry in db, return if found.
 
 The process could probably do some amount of intelligence to avoid
 rescanning the password database on every lookup, but I can't think of
 anything off the top of my head (it's late). I'll think about it some
 more.