From owner-freebsd-hackers Fri Oct 31 10:34:38 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id KAA25996 for hackers-outgoing; Fri, 31 Oct 1997 10:34:38 -0800 (PST) (envelope-from owner-freebsd-hackers) Received: from sinbin.demos.su (sinbin.demos.su [194.87.5.31]) by hub.freebsd.org (8.8.7/8.8.7) with SMTP id KAA25991 for ; Fri, 31 Oct 1997 10:34:34 -0800 (PST) (envelope-from bag@sinbin.demos.su) Received: by sinbin.demos.su id VAA15139; (8.6.12/D) Fri, 31 Oct 1997 21:33:16 +0300 From: bag@sinbin.demos.su (Alex G. Bulushev) Message-Id: <199710311833.VAA15139@sinbin.demos.su> Subject: Re: Password file builds In-Reply-To: <19971031042509.23697@golden.net> from "Dave Chapeskie" at "Oct 31, 97 04:25:09 am" X-ELM-OSV: (Our standard violations) no-mime=1; no-hdr-encoding=1 To: dchapes@golden.net (Dave Chapeskie) Date: Fri, 31 Oct 1997 21:33:16 +0300 (MSK) Cc: freebsd-hackers@FreeBSD.ORG, bryn@nwlink.com X-Mailer: ELM [version 2.4ME+ PL32 (25)] Content-Type: text Sender: owner-freebsd-hackers@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk > On Thu, Oct 30, 1997 at 02:00:31PM -0800, Bryn Wm. Moslow wrote: > > I'm running 2.2.2-RELEASE on a mail server that has several thousand > > users. > [...] > > Password file rebuilds just absolutely HAMMER the system. Whenever > > pwd_mkdb is running the whole box literally comes to a standstill > > > I believe that the way FreeBSD handles the password files needs to be > changed in order to handle a large number of users efficiently. I write patch for pwd_mkdb perfomance (ache know) but it is incompatible with BSDI etc ... two or three years ago ... Alex. > > Currently, unless called with the '-u' argument, pwd_mkdb rebuilds the > ENTIRE password database from the text file. You can prevent this by > avoiding things like vipw(8) in favor of things like chpass(1) which > will call pwd_mkdb with the '-u' argument so that only a single record > is rebuilt. This is still inefficient in that chpass keeps the text > version of the password file in sync by rewriting the entire file. > > > Ideally if only the db files were updated you'd have: > add/delete O(log(n)) > rebuild O(n*log(n)) > > Since chpass rebuilds the text file you get: > add/delete O(n) > and most of its time is spent writing out the text file. > > Since vipw rebuilds the whole database you get O(n*log(n)) for ANY > change. > > > So if you add users the way adduser(8) does, by stupidly appending to > /etc/master.password and calling pwd_mkdb you have each addition taking > O(n*log(n)) time whereas by simply using "chpass -a" instead, each > addition takes only O(n) time. (ie adduser needs to be fixed!) > > For batch adding large numbers of users to systems that already have a > lot of users (as many ISPs and the like will periodicly do) this changes > to O(n^2*log(n)) for adduser(8), O(n^2) for "chpass -a", and O(n*log(n)) > for a single vipw. If you make a small modification to chpass to NOT > update the text file after each user is added (or to just append to it) > then this drops multiple "chpass -a"'s to O(n)! > > > Clearly the way the system handles the text version of the password file > is inefficient for a large number of users. Also the usefulness of a > text version decreases when you get tons of users (ie any shell scripts > that grep the password file should be rewritten in C or perl to use the > password database routines). > > > For a friend of mine that wants to run a FreeBSD system with tens or > hundreds of thousands of users I suggested he do the following: > > - Modify chpass and friends to not print a warning for uids > 65535. (I > don't know why the warning is there, I've used UIDs>100000 with NFS > before, perhaps something to do with NIS?). > > - Modify chpass and friends to NEVER update the text password file but > to set a dirty flag within the database. > > - Add a flag to chpass for deleting a userid from the database. > > - Add a new command, say pwd_dump, that rebuilds the text password file > from the password database if the dirty bit is set and then clears the > dirty bit. BTW, the database already stores "line numbers" so you can > maintain arbitrary ordering of the text password file. > > - Change vipw to print a warning that it may take a long while and call > pwd_dump before calling the editor and then finally calling pwd_mkdb. > > - Run pwd_dump from cron periodically. > > Shell scripts or users that rely on grepping /etc/password instead of > using the password routines won't always get what they expect since the > text version may be out of date. Scripts can be rewritten in C or perl > to use the password database routines to avoid this and to run _much_ > faster. > > Since my friend's system only allows pop/imap/ftp access to most users > the fact that the text version of the password file isn't always up > to date doesn't matter. For him I even suggested adding arguments to > pwd_dump to only extract a subset of the users (based on uid system accounts or shell users) to save space and time. > > > I think that if done properly the above changes should be incorporated > into FreeBSD and the text password files made optional. Ie, on a small > system like my home system leave things as they are but allow for ISPs > and the like to do away with the text versions. > > If others think something like this would be useful (as an option, > not the default of course) I'd consider doing the above changes and > submitting it. > > -- > Dave Chapeskie, DDM Consulting > E-Mail: dchapes@golden.net >