1 /* $NetBSD: ulfs_dirhash.h,v 1.8 2015/09/21 01:24:23 dholland Exp $ */ 2 /* from NetBSD: dirhash.h,v 1.6 2008/06/04 11:33:19 ad Exp */ 3 4 /* 5 * Copyright (c) 2001 Ian Dowse. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 * 28 * $FreeBSD: src/sys/ufs/ufs/dirhash.h,v 1.2.2.2 2004/12/08 11:54:13 dwmalone Exp $ 29 */ 30 31 #ifndef _UFS_LFS_ULFS_DIRHASH_H_ 32 #define _UFS_LFS_ULFS_DIRHASH_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 (LFS_MAXDIRENTRYSIZE / 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 kmutex_t dh_lock; /* protects all fields except dh_list */ 87 88 doff_t **dh_hash; /* the hash array (2-level) */ 89 size_t dh_hashsz; 90 int dh_narrays; /* number of entries in dh_hash */ 91 int dh_hlen; /* total slots in the 2-level hash array */ 92 int dh_hused; /* entries in use */ 93 94 u_int8_t *dh_blkfree; /* free DIRALIGN words in each dir block */ 95 size_t dh_blkfreesz; 96 int dh_nblk; /* size of dh_blkfree array */ 97 int dh_dirblks; /* number of DIRBLKSIZ blocks in dir */ 98 int dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */ 99 100 int dh_seqopt; /* sequential access optimisation enabled */ 101 doff_t dh_seqoff; /* sequential access optimisation offset */ 102 103 int dh_score; /* access count for this dirhash */ 104 105 int dh_onlist; /* true if on the ulfsdirhash_list chain */ 106 107 /* Protected by ulfsdirhash_lock. */ 108 TAILQ_ENTRY(dirhash) dh_list; /* chain of all dirhashes */ 109 }; 110 111 112 /* 113 * Dirhash functions. 114 */ 115 int ulfsdirhash_build(struct inode *); 116 doff_t ulfsdirhash_findfree(struct inode *, int, int *); 117 doff_t ulfsdirhash_enduseful(struct inode *); 118 int ulfsdirhash_lookup(struct inode *, const char *, int, doff_t *, 119 struct buf **, doff_t *); 120 void ulfsdirhash_newblk(struct inode *, doff_t); 121 void ulfsdirhash_add(struct inode *, LFS_DIRHEADER *, doff_t); 122 void ulfsdirhash_remove(struct inode *, LFS_DIRHEADER *, doff_t); 123 void ulfsdirhash_move(struct inode *, LFS_DIRHEADER *, doff_t, doff_t); 124 void ulfsdirhash_dirtrunc(struct inode *, doff_t); 125 void ulfsdirhash_free(struct inode *); 126 void ulfsdirhash_checkblock(struct inode *, char *, doff_t); 127 void ulfsdirhash_init(void); 128 void ulfsdirhash_done(void); 129 130 #endif /* !_UFS_LFS_ULFS_DIRHASH_H_ */ 131