Date: Wed, 19 Jan 2005 21:19:07 -0800 From: Alfred Perlstein <alfred@freebsd.org> To: "Charles M. Hannum" <abuse@spamalicious.com> Cc: tech-kern@netbsd.org Subject: Re: namei caching of newly created files? Message-ID: <20050120051907.GC6174@elvis.mu.org> In-Reply-To: <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> <20050120051418.GB6174@elvis.mu.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050120051907.GC6174>