1 /*- 2 * Copyright (c) 2001 Ian Dowse. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 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. 12 * 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 23 * SUCH DAMAGE. 24 * 25 * $FreeBSD$ 26 */ 27 28 #ifndef _UFS_UFS_DIRHASH_H_ 29 #define _UFS_UFS_DIRHASH_H_ 30 31 /* 32 * For fast operations on large directories, we maintain a hash 33 * that maps the file name to the offset of the directory entry within 34 * the directory file. 35 * 36 * The hashing uses a dumb spillover to the next free slot on 37 * collisions, so we must keep the utilisation low to avoid 38 * long linear searches. Deleted entries that are not the last 39 * in a chain must be marked DIRHASH_DEL. 40 * 41 * We also maintain information about free space in each block 42 * to speed up creations. 43 */ 44 #define DIRHASH_EMPTY (-1) /* entry unused */ 45 #define DIRHASH_DEL (-2) /* deleted entry; may be part of chain */ 46 47 #define DIRALIGN 4 48 #define DH_NFSTATS (DIRECTSIZ(MAXNAMLEN + 1) / DIRALIGN) 49 /* max DIRALIGN words in a directory entry */ 50 51 /* 52 * Dirhash uses a score mechanism to achieve a hybrid between a 53 * least-recently-used and a least-often-used algorithm for entry 54 * recycling. The score is incremented when a directory is used, and 55 * decremented when the directory is a candidate for recycling. When 56 * the score reaches zero, the hash is recycled. Hashes are linked 57 * together on a TAILQ list, and hashes with higher scores filter 58 * towards the tail (most recently used) end of the list. 59 * 60 * New hash entries are given an inital score of DH_SCOREINIT and are 61 * placed at the most-recently-used end of the list. This helps a lot 62 * in the worst-case case scenario where every directory access is 63 * to a directory that is not hashed (i.e. the working set of hash 64 * candidates is much larger than the configured memry limit). In this 65 * case it limits the number of hash builds to 1/DH_SCOREINIT of the 66 * number of accesses. 67 */ 68 #define DH_SCOREINIT 8 /* initial dh_score when dirhash built */ 69 #define DH_SCOREMAX 64 /* max dh_score value */ 70 71 /* 72 * The main hash table has 2 levels. It is an array of pointers to 73 * blocks of DH_NBLKOFF offsets. 74 */ 75 #define DH_BLKOFFSHIFT 8 76 #define DH_NBLKOFF (1 << DH_BLKOFFSHIFT) 77 #define DH_BLKOFFMASK (DH_NBLKOFF - 1) 78 79 #define DH_ENTRY(dh, slot) \ 80 ((dh)->dh_hash[(slot) >> DH_BLKOFFSHIFT][(slot) & DH_BLKOFFMASK]) 81 82 struct dirhash { 83 struct mtx dh_mtx; /* protects all fields except dh_list */ 84 85 doff_t **dh_hash; /* the hash array (2-level) */ 86 int dh_narrays; /* number of entries in dh_hash */ 87 int dh_hlen; /* total slots in the 2-level hash array */ 88 int dh_hused; /* entries in use */ 89 90 /* Free space statistics. XXX assumes DIRBLKSIZ is 512. */ 91 u_int8_t *dh_blkfree; /* free DIRALIGN words in each dir block */ 92 int dh_nblk; /* size of dh_blkfree array */ 93 int dh_dirblks; /* number of DIRBLKSIZ blocks in dir */ 94 int dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */ 95 96 int dh_seqopt; /* sequential access optimisation enabled */ 97 doff_t dh_seqoff; /* sequential access optimisation offset */ 98 99 int dh_score; /* access count for this dirhash */ 100 101 int dh_onlist; /* true if on the ufsdirhash_list chain */ 102 103 /* Protected by ufsdirhash_mtx. */ 104 TAILQ_ENTRY(dirhash) dh_list; /* chain of all dirhashes */ 105 }; 106 107 108 /* 109 * Dirhash functions. 110 */ 111 void ufsdirhash_init(void); 112 void ufsdirhash_uninit(void); 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 **, 117 doff_t *); 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 *); 124 125 void ufsdirhash_checkblock(struct inode *, char *, doff_t); 126 127 #endif /* !_UFS_UFS_DIRHASH_H_ */ 128