From owner-freebsd-fs@FreeBSD.ORG Thu Jan 20 05:14:18 2005 Return-Path: Delivered-To: freebsd-fs@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id D494316A4CE for ; Thu, 20 Jan 2005 05:14:18 +0000 (GMT) Received: from elvis.mu.org (elvis.mu.org [192.203.228.196]) by mx1.FreeBSD.org (Postfix) with ESMTP id B4E0143D2F for ; Thu, 20 Jan 2005 05:14:18 +0000 (GMT) (envelope-from bright@elvis.mu.org) Received: by elvis.mu.org (Postfix, from userid 1192) id A41EE5C9ED; Wed, 19 Jan 2005 21:14:18 -0800 (PST) Date: Wed, 19 Jan 2005 21:14:18 -0800 From: Alfred Perlstein To: "Charles M. Hannum" Message-ID: <20050120051418.GB6174@elvis.mu.org> References: <1106180748.64610.21987.camel@palm.tree.com> <20050120014731.GD16440@netbsd.org> <20050120032433.GO13149@bcd.geek.com.au> <200501200503.13300.abuse@spamalicious.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200501200503.13300.abuse@spamalicious.com> User-Agent: Mutt/1.4.2.1i cc: Daniel Carosone cc: Havard Eidnes cc: Bill Studenmund cc: fs@freebsd.org cc: tech-perform@netbsd.org cc: tech-kern@netbsd.org Subject: Re: namei caching of newly created files? X-BeenThere: freebsd-fs@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Filesystems List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 20 Jan 2005 05:14:18 -0000 cc'd to fs@freebsd.org because I wish someone would do this for us too. :) * Charles M. Hannum [050119 21:03] wrote: > On Thursday 20 January 2005 03:24, Daniel Carosone wrote: > > This is hurting, mostly, because it's being done over and over again > > all the way to the end of the dir. As the simplest possible change, > > before looking at more complex solutions, having done the search to > > the end once and found no free slots, we could remember that fact. We > > would reset the flag on deleting an entry and making a space, or > > perhaps after doing so several times. > > It's not that simple. There are often small pieces of directory blocks > available, but not large enough for the file name you're trying to create. There's two ways to solve this, one is easy but wastes space, the other is hard but more space effecient. Easy way: Keep track of the amount of free space in a directory versus its size. If the amount of free space is below a threshold then just append to the directory. (this should make creating large numbers of files very fast as we'll always be full or near full so we'll just append to the directory) Hard way: Keep an in memory bucket list of available sizes. The bucket list can be N offsets into the directory for sizes that are power of two up to MAXFILELEN. Tune the bucket structure to the size of the directory. Make sure to keep a "negative entry" for sizes not seen. Whenever you delete make sure to update your bucket structures to include the deleted space or mark the bucket as overflowed if all the entries for a particular size have been taken. Then finding a free space is easy. Do a best fit. -- - Alfred Perlstein - Research Engineering Development Inc. - email: bright@mu.org cell: 408-480-4684