Annotation of src/sys/ufs/ufs/dirhash.h, Revision 1.7
1.7 ! dholland 1: /* $NetBSD: dirhash.h,v 1.6 2008/06/04 11:33:19 ad Exp $ */
1.1 rumble 2:
3: /*
4: * Copyright (c) 2001 Ian Dowse. All rights reserved.
5: *
6: * Redistribution and use in source and binary forms, with or without
7: * modification, are permitted provided that the following conditions
8: * are met:
9: * 1. Redistributions of source code must retain the above copyright
10: * notice, this list of conditions and the following disclaimer.
11: * 2. Redistributions in binary form must reproduce the above copyright
12: * notice, this list of conditions and the following disclaimer in the
13: * documentation and/or other materials provided with the distribution.
14: *
15: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18: * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25: * SUCH DAMAGE.
26: *
27: * $FreeBSD: src/sys/ufs/ufs/dirhash.h,v 1.2.2.2 2004/12/08 11:54:13 dwmalone Exp $
28: */
29:
30: #ifndef _UFS_UFS_DIRHASH_H_
31: #define _UFS_UFS_DIRHASH_H_
32:
33: /*
34: * For fast operations on large directories, we maintain a hash
35: * that maps the file name to the offset of the directory entry within
36: * the directory file.
37: *
38: * The hashing uses a dumb spillover to the next free slot on
39: * collisions, so we must keep the utilisation low to avoid
40: * long linear searches. Deleted entries that are not the last
41: * in a chain must be marked DIRHASH_DEL.
42: *
43: * We also maintain information about free space in each block
44: * to speed up creations.
45: */
46: #define DIRHASH_EMPTY (-1) /* entry unused */
47: #define DIRHASH_DEL (-2) /* deleted entry; may be part of chain */
48:
49: #define DIRALIGN 4
1.7 ! dholland 50: #define DH_NFSTATS (UFS_DIRECTSIZ(FFS_MAXNAMLEN + 1) / DIRALIGN)
1.1 rumble 51: /* max DIRALIGN words in a directory entry */
52:
53: /*
54: * Dirhash uses a score mechanism to achieve a hybrid between a
55: * least-recently-used and a least-often-used algorithm for entry
56: * recycling. The score is incremented when a directory is used, and
57: * decremented when the directory is a candidate for recycling. When
58: * the score reaches zero, the hash is recycled. Hashes are linked
59: * together on a TAILQ list, and hashes with higher scores filter
60: * towards the tail (most recently used) end of the list.
61: *
62: * New hash entries are given an inital score of DH_SCOREINIT and are
63: * placed at the most-recently-used end of the list. This helps a lot
64: * in the worst-case case scenario where every directory access is
65: * to a directory that is not hashed (i.e. the working set of hash
66: * candidates is much larger than the configured memry limit). In this
67: * case it limits the number of hash builds to 1/DH_SCOREINIT of the
68: * number of accesses.
1.2 perry 69: */
1.1 rumble 70: #define DH_SCOREINIT 8 /* initial dh_score when dirhash built */
71: #define DH_SCOREMAX 64 /* max dh_score value */
72:
73: /*
74: * The main hash table has 2 levels. It is an array of pointers to
75: * blocks of DH_NBLKOFF offsets.
76: */
77: #define DH_BLKOFFSHIFT 8
78: #define DH_NBLKOFF (1 << DH_BLKOFFSHIFT)
79: #define DH_BLKOFFMASK (DH_NBLKOFF - 1)
80:
81: #define DH_ENTRY(dh, slot) \
82: ((dh)->dh_hash[(slot) >> DH_BLKOFFSHIFT][(slot) & DH_BLKOFFMASK])
83:
84: struct dirhash {
1.5 ad 85: kmutex_t dh_lock; /* protects all fields except dh_list */
86:
1.1 rumble 87: doff_t **dh_hash; /* the hash array (2-level) */
1.6 ad 88: size_t dh_hashsz;
1.1 rumble 89: int dh_narrays; /* number of entries in dh_hash */
90: int dh_hlen; /* total slots in the 2-level hash array */
91: int dh_hused; /* entries in use */
92:
93: u_int8_t *dh_blkfree; /* free DIRALIGN words in each dir block */
1.6 ad 94: size_t dh_blkfreesz;
1.1 rumble 95: int dh_nblk; /* size of dh_blkfree array */
96: int dh_dirblks; /* number of DIRBLKSIZ blocks in dir */
97: int dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */
98:
99: int dh_seqopt; /* sequential access optimisation enabled */
100: doff_t dh_seqoff; /* sequential access optimisation offset */
101:
102: int dh_score; /* access count for this dirhash */
103:
104: int dh_onlist; /* true if on the ufsdirhash_list chain */
105:
1.5 ad 106: /* Protected by ufsdirhash_lock. */
1.1 rumble 107: TAILQ_ENTRY(dirhash) dh_list; /* chain of all dirhashes */
108: };
109:
110:
111: /*
112: * Dirhash functions.
113: */
114: int ufsdirhash_build(struct inode *);
115: doff_t ufsdirhash_findfree(struct inode *, int, int *);
116: doff_t ufsdirhash_enduseful(struct inode *);
117: int ufsdirhash_lookup(struct inode *, const char *, int, doff_t *,
118: struct buf **, doff_t *);
119: void ufsdirhash_newblk(struct inode *, doff_t);
120: void ufsdirhash_add(struct inode *, struct direct *, doff_t);
121: void ufsdirhash_remove(struct inode *, struct direct *, doff_t);
122: void ufsdirhash_move(struct inode *, struct direct *, doff_t, doff_t);
123: void ufsdirhash_dirtrunc(struct inode *, doff_t);
124: void ufsdirhash_free(struct inode *);
125: void ufsdirhash_checkblock(struct inode *, char *, doff_t);
126: void ufsdirhash_init(void);
127: void ufsdirhash_done(void);
128:
129: #endif /* !_UFS_UFS_DIRHASH_H_ */
CVSweb <webmaster@jp.NetBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to dirhash.h CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [cvs.NetBSD.org] / src / sys / ufs / ufs