1 /*        $NetBSD: dirhash.h,v 1.9 2021/08/19 20:56:36 andvar Exp $   */
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
50 #define DH_NFSTATS  (UFS_DIRECTSIZ(FFS_MAXNAMLEN + 1) / DIRALIGN)
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 initial 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 memory limit). In this
67  * case it limits the number of hash builds to 1/DH_SCOREINIT of the
68  * number of accesses.
69  */
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 {
85           kmutex_t dh_lock;   /* protects all fields except dh_list */
86 
87           doff_t    **dh_hash;          /* the hash array (2-level) */
88           size_t    dh_hashsz;
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 */
94           size_t    dh_blkfreesz;
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 
106           /* Protected by ufsdirhash_lock. */
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_ */
130