2 * Copyright (c) 2001 Ian Dowse. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
14 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
16 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
17 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
18 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
19 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
20 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
21 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
22 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * $FreeBSD: src/sys/ufs/ufs/dirhash.h,v 1.2.2.1 2001/08/01 19:33:39 iedowse Exp $
26 * $DragonFly: src/sys/vfs/ufs/dirhash.h,v 1.4 2006/04/03 02:02:37 dillon Exp $
29 #ifndef _VFS_UFS_DIRHASH_H_
30 #define _VFS_UFS_DIRHASH_H_
33 * XXX DR: On the current directory hashing method; the performance
34 * on large directories is awful due to the lookup code path.
37 * For fast operations on large directories, we maintain a hash
38 * that maps the file name to the offset of the directory entry within
41 * The hashing uses a dumb spillover to the next free slot on
42 * collisions, so we must keep the utilisation low to avoid
43 * long linear searches. Deleted entries that are not the last
44 * in a chain must be marked DIRHASH_DEL.
46 * We also maintain a information about free space in each block
47 * to speed up creations.
49 #define DIRHASH_EMPTY (-1) /* entry unused */
50 #define DIRHASH_DEL (-2) /* deleted entry; may be part of chain */
53 #define DH_NFSTATS (DIRECTSIZ(MAXNAMLEN + 1) / DIRALIGN)
54 /* max DIRALIGN words in a directory entry */
57 * Dirhash uses a score mechanism to achieve a hybrid between a
58 * least-recently-used and a least-often-used algorithm for entry
59 * recycling. The score is incremented when a directory is used, and
60 * decremented when the directory is a candidate for recycling. When
61 * the score reaches zero, the hash is recycled. Hashes are linked
62 * together on a TAILQ list, and hashes with higher scores filter
63 * towards the tail (most recently used) end of the list.
65 * New hash entries are given an inital score of DH_SCOREINIT and are
66 * placed at the most-recently-used end of the list. This helps a lot
67 * in the worst-case case scenario where every directory access is
68 * to a directory that is not hashed (i.e. the working set of hash
69 * candidates is much larger than the configured memry limit). In this
70 * case it limits the number of hash builds to 1/DH_SCOREINIT of the
73 #define DH_SCOREINIT 8 /* initial dh_score when dirhash built */
74 #define DH_SCOREMAX 64 /* max dh_score value */
77 * The main hash table has 2 levels. It is an array of pointers to
78 * blocks of DH_NBLKOFF offsets.
80 #define DH_BLKOFFSHIFT 8
81 #define DH_NBLKOFF (1 << DH_BLKOFFSHIFT)
82 #define DH_BLKOFFMASK (DH_NBLKOFF - 1)
84 #define DH_ENTRY(dh, slot) \
85 ((dh)->dh_hash[(slot) >> DH_BLKOFFSHIFT][(slot) & DH_BLKOFFMASK])
88 doff_t
**dh_hash
; /* the hash array (2-level) */
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 */
93 /* Free space statistics. XXX assumes DIRBLKSIZ is 512. */
94 u_int8_t
*dh_blkfree
; /* free DIRALIGN words in each dir block */
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 */
99 int dh_seqopt
; /* sequential access optimisation enabled */
100 doff_t dh_seqoff
; /* sequential access optimisation offset */
102 int dh_score
; /* access count for this dirhash */
104 int dh_onlist
; /* true if on the ufsdirhash_list chain */
106 TAILQ_ENTRY(dirhash
) dh_list
; /* chain of all dirhashes */
113 int ufsdirhash_build(struct inode
*);
114 doff_t
ufsdirhash_findfree(struct inode
*, int, int *);
115 doff_t
ufsdirhash_enduseful(struct inode
*);
116 int ufsdirhash_lookup(struct inode
*, char *, int, doff_t
*, struct buf
**,
118 void ufsdirhash_newblk(struct inode
*, doff_t
);
119 void ufsdirhash_add(struct inode
*, struct direct
*, doff_t
);
120 void ufsdirhash_remove(struct inode
*, struct direct
*, doff_t
);
121 void ufsdirhash_move(struct inode
*, struct direct
*, doff_t
, doff_t
);
122 void ufsdirhash_dirtrunc(struct inode
*, doff_t
);
123 void ufsdirhash_free(struct inode
*);
125 void ufsdirhash_checkblock(struct inode
*, char *, doff_t
);
127 #endif /* !_VFS_UFS_DIRHASH_H_ */