From owner-freebsd-fs@FreeBSD.ORG  Thu Jan 20 05:19:07 2005
Return-Path: <owner-freebsd-fs@FreeBSD.ORG>
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 3D85D16A4CE
	for <fs@freebsd.org>; Thu, 20 Jan 2005 05:19:07 +0000 (GMT)
Received: from elvis.mu.org (elvis.mu.org [192.203.228.196])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 2155743D53
	for <fs@freebsd.org>; Thu, 20 Jan 2005 05:19:07 +0000 (GMT)
	(envelope-from bright@elvis.mu.org)
Received: by elvis.mu.org (Postfix, from userid 1192)
	id 160CD5C9F1; Wed, 19 Jan 2005 21:19:07 -0800 (PST)
Date: Wed, 19 Jan 2005 21:19:07 -0800
From: Alfred Perlstein <alfred@freebsd.org>
To: "Charles M. Hannum" <abuse@spamalicious.com>
Message-ID: <20050120051907.GC6174@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>
	<20050120051418.GB6174@elvis.mu.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20050120051418.GB6174@elvis.mu.org>
User-Agent: Mutt/1.4.2.1i
cc: Daniel Carosone <dan@geek.com.au>
cc: Havard Eidnes <he@uninett.no>
cc: Bill Studenmund <wrstuden@netbsd.org>
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 <freebsd-fs.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-fs>,
	<mailto:freebsd-fs-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-fs>
List-Post: <mailto:freebsd-fs@freebsd.org>
List-Help: <mailto:freebsd-fs-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-fs>,
	<mailto:freebsd-fs-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Thu, 20 Jan 2005 05:19:07 -0000

One other trick is just a negative cache:

Each in memory directory has a bucket list in it
for power of two up until MAXFILELEN.

If you have to do a scan, just populate the negative
entries.

Then only "fix" the negative entries if you delete something.

Then you'll avoid repeated scans when there's no space.


* Alfred Perlstein <bright@mu.org> [050119 21:14] wrote:
> 
> 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

-- 
- Alfred Perlstein
- Research Engineering Development Inc.
- email: bright@mu.org cell: 408-480-4684