[BACK]Return to dirhash.h CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / sys / ufs / ufs

File: [cvs.NetBSD.org] / src / sys / ufs / ufs / dirhash.h (download)

Revision 1.6, Wed Jun 4 11:33:19 2008 UTC (6 years, 4 months ago) by ad
Branch: MAIN
CVS Tags: yamt-pf42-base4, yamt-pagecache-tag8, yamt-pagecache-base8, yamt-pagecache-base7, yamt-pagecache-base6, yamt-pagecache-base5, yamt-pagecache-base4, yamt-pagecache-base3, yamt-pagecache-base2, yamt-pagecache-base, yamt-nfs-mp-base9, yamt-nfs-mp-base8, yamt-nfs-mp-base7, yamt-nfs-mp-base6, yamt-nfs-mp-base5, yamt-nfs-mp-base4, yamt-nfs-mp-base3, yamt-nfs-mp-base11, yamt-nfs-mp-base10, wrstuden-revivesa-base-4, wrstuden-revivesa-base-3, wrstuden-revivesa-base-2, wrstuden-revivesa-base-1, wrstuden-revivesa-base, uebayasi-xip-base4, uebayasi-xip-base3, uebayasi-xip-base2, uebayasi-xip-base1, uebayasi-xip-base, uebayasi-xip, simonb-wapbl-nbase, simonb-wapbl-base, simonb-wapbl, rmind-uvmplock-nbase, rmind-uvmplock-base, rmind-uvmplock, nick-hppapmap-base4, nick-hppapmap-base3, nick-hppapmap-base2, nick-hppapmap-base, nick-hppapmap, netbsd-6-base, netbsd-6-1-RELEASE, netbsd-6-1-RC4, netbsd-6-1-RC3, netbsd-6-1-RC2, netbsd-6-1-RC1, netbsd-6-1-5-RELEASE, netbsd-6-1-4-RELEASE, netbsd-6-1-3-RELEASE, netbsd-6-1-2-RELEASE, netbsd-6-1-1-RELEASE, netbsd-6-1, netbsd-6-0-RELEASE, netbsd-6-0-RC2, netbsd-6-0-RC1, netbsd-6-0-6-RELEASE, netbsd-6-0-5-RELEASE, netbsd-6-0-4-RELEASE, netbsd-6-0-3-RELEASE, netbsd-6-0-2-RELEASE, netbsd-6-0-1-RELEASE, netbsd-6-0, netbsd-6, netbsd-5-base, netbsd-5-2-RELEASE, netbsd-5-2-RC1, netbsd-5-2-2-RELEASE, netbsd-5-2-1-RELEASE, netbsd-5-2, netbsd-5-1-RELEASE, netbsd-5-1-RC4, netbsd-5-1-RC3, netbsd-5-1-RC2, netbsd-5-1-RC1, netbsd-5-1-4-RELEASE, netbsd-5-1-3-RELEASE, netbsd-5-1-2-RELEASE, netbsd-5-1-1-RELEASE, netbsd-5-1, netbsd-5-0-RELEASE, netbsd-5-0-RC4, netbsd-5-0-RC3, netbsd-5-0-RC2, netbsd-5-0-RC1, netbsd-5-0-2-RELEASE, netbsd-5-0-1-RELEASE, netbsd-5-0, netbsd-5, mjf-devfs2-base, matt-premerge-20091211, matt-nb6-plus-nbase, matt-nb6-plus-base, matt-nb6-plus, matt-nb5-pq3-base, matt-nb5-pq3, matt-nb5-mips64-u2-k2-k4-k7-k8-k9, matt-nb5-mips64-u1-k1-k5, matt-nb5-mips64-premerge-20101231, matt-nb5-mips64-premerge-20091211, matt-nb5-mips64-k15, matt-nb5-mips64, matt-nb4-mips64-k7-u2a-k9b, matt-mips64-premerge-20101231, matt-mips64-base2, khorben-n900, jymxensuspend-base, jym-xensuspend-nbase, jym-xensuspend-base, jym-xensuspend, jruoho-x86intr-base, jruoho-x86intr, jmcneill-usbmp-pre-base2, jmcneill-usbmp-base9, jmcneill-usbmp-base8, jmcneill-usbmp-base7, jmcneill-usbmp-base6, jmcneill-usbmp-base5, jmcneill-usbmp-base4, jmcneill-usbmp-base3, jmcneill-usbmp-base2, jmcneill-usbmp-base10, jmcneill-usbmp-base, jmcneill-usbmp, jmcneill-audiomp3-base, jmcneill-audiomp3, haad-nbase2, haad-dm-base2, haad-dm-base1, haad-dm-base, haad-dm, cherry-xenmp-base, cherry-xenmp, bouyer-quota2-nbase, bouyer-quota2-base, bouyer-quota2, agc-symver-base, agc-symver, ad-audiomp2-base, ad-audiomp2
Branch point for: yamt-pagecache, tls-maxphys
Changes since 1.5: +3 -1 lines

- Tidy up the locking a bit.
- Use atomics/kmem_alloc/pool_cache.

/*	$NetBSD: dirhash.h,v 1.6 2008/06/04 11:33:19 ad Exp $	*/

/*
 * Copyright (c) 2001 Ian Dowse.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * $FreeBSD: src/sys/ufs/ufs/dirhash.h,v 1.2.2.2 2004/12/08 11:54:13 dwmalone Exp $
 */

#ifndef _UFS_UFS_DIRHASH_H_
#define _UFS_UFS_DIRHASH_H_

/*
 * For fast operations on large directories, we maintain a hash
 * that maps the file name to the offset of the directory entry within
 * the directory file.
 *
 * The hashing uses a dumb spillover to the next free slot on
 * collisions, so we must keep the utilisation low to avoid
 * long linear searches. Deleted entries that are not the last
 * in a chain must be marked DIRHASH_DEL.
 *
 * We also maintain information about free space in each block
 * to speed up creations.
 */
#define DIRHASH_EMPTY	(-1)	/* entry unused */
#define DIRHASH_DEL	(-2)	/* deleted entry; may be part of chain */

#define DIRALIGN	4
#define DH_NFSTATS	(DIRECTSIZ(FFS_MAXNAMLEN + 1) / DIRALIGN)
				 /* max DIRALIGN words in a directory entry */

/*
 * Dirhash uses a score mechanism to achieve a hybrid between a
 * least-recently-used and a least-often-used algorithm for entry
 * recycling. The score is incremented when a directory is used, and
 * decremented when the directory is a candidate for recycling. When
 * the score reaches zero, the hash is recycled. Hashes are linked
 * together on a TAILQ list, and hashes with higher scores filter
 * towards the tail (most recently used) end of the list.
 *
 * New hash entries are given an inital score of DH_SCOREINIT and are
 * placed at the most-recently-used end of the list. This helps a lot
 * in the worst-case case scenario where every directory access is
 * to a directory that is not hashed (i.e. the working set of hash
 * candidates is much larger than the configured memry limit). In this
 * case it limits the number of hash builds to 1/DH_SCOREINIT of the
 * number of accesses.
 */
#define DH_SCOREINIT	8	/* initial dh_score when dirhash built */
#define DH_SCOREMAX	64	/* max dh_score value */

/*
 * The main hash table has 2 levels. It is an array of pointers to
 * blocks of DH_NBLKOFF offsets.
 */
#define DH_BLKOFFSHIFT	8
#define DH_NBLKOFF	(1 << DH_BLKOFFSHIFT)
#define DH_BLKOFFMASK	(DH_NBLKOFF - 1)

#define DH_ENTRY(dh, slot) \
    ((dh)->dh_hash[(slot) >> DH_BLKOFFSHIFT][(slot) & DH_BLKOFFMASK])

struct dirhash {
	kmutex_t dh_lock;	/* protects all fields except dh_list */

	doff_t	**dh_hash;	/* the hash array (2-level) */
	size_t	dh_hashsz;
	int	dh_narrays;	/* number of entries in dh_hash */
	int	dh_hlen;	/* total slots in the 2-level hash array */
	int	dh_hused;	/* entries in use */

	u_int8_t *dh_blkfree;	/* free DIRALIGN words in each dir block */
	size_t	dh_blkfreesz;
	int	dh_nblk;	/* size of dh_blkfree array */
	int	dh_dirblks;	/* number of DIRBLKSIZ blocks in dir */
	int	dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */

	int	dh_seqopt;	/* sequential access optimisation enabled */
	doff_t	dh_seqoff;	/* sequential access optimisation offset */

	int	dh_score;	/* access count for this dirhash */

	int	dh_onlist;	/* true if on the ufsdirhash_list chain */

	/* Protected by ufsdirhash_lock. */
	TAILQ_ENTRY(dirhash) dh_list;	/* chain of all dirhashes */
};


/*
 * Dirhash functions.
 */
int	ufsdirhash_build(struct inode *);
doff_t	ufsdirhash_findfree(struct inode *, int, int *);
doff_t	ufsdirhash_enduseful(struct inode *);
int	ufsdirhash_lookup(struct inode *, const char *, int, doff_t *,
	    struct buf **, doff_t *);
void	ufsdirhash_newblk(struct inode *, doff_t);
void	ufsdirhash_add(struct inode *, struct direct *, doff_t);
void	ufsdirhash_remove(struct inode *, struct direct *, doff_t);
void	ufsdirhash_move(struct inode *, struct direct *, doff_t, doff_t);
void	ufsdirhash_dirtrunc(struct inode *, doff_t);
void	ufsdirhash_free(struct inode *);
void	ufsdirhash_checkblock(struct inode *, char *, doff_t);
void	ufsdirhash_init(void);
void	ufsdirhash_done(void);

#endif /* !_UFS_UFS_DIRHASH_H_ */