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