/* $NetBSD: ulfs_dirhash.h,v 1.12 2021/08/19 20:56:36 andvar Exp $ */ /* from NetBSD: dirhash.h,v 1.7 2013/06/09 17:57:09 dholland Exp */ /* * Copyright (c) 2001 Ian Dowse. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD: src/sys/ufs/ufs/dirhash.h,v 1.2.2.2 2004/12/08 11:54:13 dwmalone Exp $ */ #ifndef _UFS_LFS_ULFS_DIRHASH_H_ #define _UFS_LFS_ULFS_DIRHASH_H_ /* * For fast operations on large directories, we maintain a hash * that maps the file name to the offset of the directory entry within * the directory file. * * The hashing uses a dumb spillover to the next free slot on * collisions, so we must keep the utilisation low to avoid * long linear searches. Deleted entries that are not the last * in a chain must be marked DIRHASH_DEL. * * We also maintain information about free space in each block * to speed up creations. */ #define DIRHASH_EMPTY (-1) /* entry unused */ #define DIRHASH_DEL (-2) /* deleted entry; may be part of chain */ #define DIRALIGN 4 #define DH_NFSTATS (LFS_MAXDIRENTRYSIZE / DIRALIGN) /* max DIRALIGN words in a directory entry */ /* * Dirhash uses a score mechanism to achieve a hybrid between a * least-recently-used and a least-often-used algorithm for entry * recycling. The score is incremented when a directory is used, and * decremented when the directory is a candidate for recycling. When * the score reaches zero, the hash is recycled. Hashes are linked * together on a TAILQ list, and hashes with higher scores filter * towards the tail (most recently used) end of the list. * * New hash entries are given an initial score of DH_SCOREINIT and are * placed at the most-recently-used end of the list. This helps a lot * in the worst-case case scenario where every directory access is * to a directory that is not hashed (i.e. the working set of hash * candidates is much larger than the configured memory limit). In this * case it limits the number of hash builds to 1/DH_SCOREINIT of the * number of accesses. */ #define DH_SCOREINIT 8 /* initial dh_score when dirhash built */ #define DH_SCOREMAX 64 /* max dh_score value */ /* * The main hash table has 2 levels. It is an array of pointers to * blocks of DH_NBLKOFF offsets. */ #define DH_BLKOFFSHIFT 8 #define DH_NBLKOFF (1 << DH_BLKOFFSHIFT) #define DH_BLKOFFMASK (DH_NBLKOFF - 1) #define DH_ENTRY(dh, slot) \ ((dh)->dh_hash[(slot) >> DH_BLKOFFSHIFT][(slot) & DH_BLKOFFMASK]) struct dirhash { kmutex_t dh_lock; /* protects all fields except dh_list */ doff_t **dh_hash; /* the hash array (2-level) */ size_t dh_hashsz; int dh_narrays; /* number of entries in dh_hash */ int dh_hlen; /* total slots in the 2-level hash array */ int dh_hused; /* entries in use */ uint8_t *dh_blkfree; /* free DIRALIGN words in each dir block */ size_t dh_blkfreesz; int dh_nblk; /* size of dh_blkfree array */ int dh_dirblks; /* number of DIRBLKSIZ blocks in dir */ int dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */ int dh_seqopt; /* sequential access optimisation enabled */ doff_t dh_seqoff; /* sequential access optimisation offset */ int dh_score; /* access count for this dirhash */ int dh_onlist; /* true if on the ulfsdirhash_list chain */ /* Protected by ulfsdirhash_lock. */ TAILQ_ENTRY(dirhash) dh_list; /* chain of all dirhashes */ }; /* * Dirhash functions. */ int ulfsdirhash_build(struct inode *); doff_t ulfsdirhash_findfree(struct inode *, int, int *); doff_t ulfsdirhash_enduseful(struct inode *); int ulfsdirhash_lookup(struct inode *, const char *, int, doff_t *, struct buf **, doff_t *); void ulfsdirhash_newblk(struct inode *, doff_t); void ulfsdirhash_add(struct inode *, LFS_DIRHEADER *, doff_t); void ulfsdirhash_remove(struct inode *, LFS_DIRHEADER *, doff_t); void ulfsdirhash_move(struct inode *, LFS_DIRHEADER *, doff_t, doff_t); void ulfsdirhash_dirtrunc(struct inode *, doff_t); void ulfsdirhash_free(struct inode *); void ulfsdirhash_checkblock(struct inode *, char *, doff_t); void ulfsdirhash_init(void); void ulfsdirhash_done(void); #endif /* !_UFS_LFS_ULFS_DIRHASH_H_ */