sys/ufs/lfs/ulfs_dirhash.h

   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_ */