Annotation of sys/ufs/ufs/dirhash.h, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: dirhash.h,v 1.4 2006/04/29 23:09:45 tedu Exp $ */
! 2: /*
! 3: * Copyright (c) 2001 Ian Dowse. All rights reserved.
! 4: *
! 5: * Redistribution and use in source and binary forms, with or without
! 6: * modification, are permitted provided that the following conditions
! 7: * are met:
! 8: * 1. Redistributions of source code must retain the above copyright
! 9: * notice, this list of conditions and the following disclaimer.
! 10: * 2. Redistributions in binary form must reproduce the above copyright
! 11: * notice, this list of conditions and the following disclaimer in the
! 12: * documentation and/or other materials provided with the distribution.
! 13: *
! 14: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
! 15: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 16: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 17: * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
! 18: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
! 19: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
! 20: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
! 21: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
! 22: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
! 23: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
! 24: * SUCH DAMAGE.
! 25: *
! 26: * $FreeBSD: src/sys/ufs/ufs/dirhash.h,v 1.4 2003/01/01 18:48:59 schweikh Exp $
! 27: */
! 28:
! 29: #ifndef _UFS_UFS_DIRHASH_H_
! 30: #define _UFS_UFS_DIRHASH_H_
! 31:
! 32: #include <sys/rwlock.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 (DIRECTSIZ(MAXNAMLEN + 1) / 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: doff_t **dh_hash; /* the hash array (2-level) */
! 87: int dh_narrays; /* number of entries in dh_hash */
! 88: int dh_hlen; /* total slots in the 2-level hash array */
! 89: int dh_hused; /* entries in use */
! 90:
! 91: /* Free space statistics. XXX assumes DIRBLKSIZ is 512. */
! 92: u_int8_t *dh_blkfree; /* free DIRALIGN words in each dir block */
! 93: int dh_nblk; /* size of dh_blkfree array */
! 94: int dh_dirblks; /* number of DIRBLKSIZ blocks in dir */
! 95: int dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */
! 96:
! 97: int dh_seqopt; /* sequential access optimisation enabled */
! 98: doff_t dh_seqoff; /* sequential access optimisation offset */
! 99:
! 100: int dh_score; /* access count for this dirhash */
! 101:
! 102: int dh_onlist; /* true if on the ufsdirhash_list chain */
! 103:
! 104: /* Protected by ufsdirhash_mtx. */
! 105: TAILQ_ENTRY(dirhash) dh_list; /* chain of all dirhashes */
! 106: };
! 107:
! 108: extern int ufs_mindirhashsize;
! 109: extern int ufs_dirhashmaxmem;
! 110: extern int ufs_dirhashmem;
! 111:
! 112: /*
! 113: * Dirhash functions.
! 114: */
! 115: void ufsdirhash_init(void);
! 116: void ufsdirhash_uninit(void);
! 117: int ufsdirhash_build(struct inode *);
! 118: doff_t ufsdirhash_findfree(struct inode *, int, int *);
! 119: doff_t ufsdirhash_enduseful(struct inode *);
! 120: int ufsdirhash_lookup(struct inode *, char *, int, doff_t *, struct buf **,
! 121: doff_t *);
! 122: void ufsdirhash_newblk(struct inode *, doff_t);
! 123: void ufsdirhash_add(struct inode *, struct direct *, doff_t);
! 124: void ufsdirhash_remove(struct inode *, struct direct *, doff_t);
! 125: void ufsdirhash_move(struct inode *, struct direct *, doff_t, doff_t);
! 126: void ufsdirhash_dirtrunc(struct inode *, doff_t);
! 127: void ufsdirhash_free(struct inode *);
! 128:
! 129: void ufsdirhash_checkblock(struct inode *, char *, doff_t);
! 130:
! 131: #endif /* !_UFS_UFS_DIRHASH_H_ */
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to dirhash.h CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / ufs / ufs