Subject: Re: namei caching of newly created files?
To: Charles M. Hannum <>
From: Alfred Perlstein <>
List: tech-kern
Date: 01/19/2005 21:14:18
cc'd to 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

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: cell: 408-480-4684