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