The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/ufs/ufs/dirhash.h

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * Copyright (c) 2001 Ian Dowse.  All rights reserved.
    3  *
    4  * Redistribution and use in source and binary forms, with or without
    5  * modification, are permitted provided that the following conditions
    6  * are met:
    7  * 1. Redistributions of source code must retain the above copyright
    8  *    notice, this list of conditions and the following disclaimer.
    9  * 2. Redistributions in binary form must reproduce the above copyright
   10  *    notice, this list of conditions and the following disclaimer in the
   11  *    documentation and/or other materials provided with the distribution.
   12  *
   13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   16  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   17  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   18  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   19  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   20  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   22  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   23  * SUCH DAMAGE.
   24  *
   25  * $FreeBSD$
   26  */
   27 
   28 #ifndef _UFS_UFS_DIRHASH_H_
   29 #define _UFS_UFS_DIRHASH_H_
   30 
   31 #include <sys/_lock.h>
   32 #include <sys/_sx.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         struct sx dh_lock;      /* protects all fields except list & score */
   87         int     dh_refcount;
   88 
   89         doff_t  **dh_hash;      /* the hash array (2-level) */
   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         int     dh_memreq;      /* Memory used. */
   94 
   95         /* Free space statistics. XXX assumes DIRBLKSIZ is 512. */
   96         u_int8_t *dh_blkfree;   /* free DIRALIGN words in each dir block */
   97         int     dh_nblk;        /* size of dh_blkfree array */
   98         int     dh_dirblks;     /* number of DIRBLKSIZ blocks in dir */
   99         int     dh_firstfree[DH_NFSTATS + 1]; /* first blk with N words free */
  100 
  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 ufsdirhash_list chain */
  106 
  107         time_t  dh_lastused;    /* time the dirhash was last read or written*/
  108 
  109         /* Protected by ufsdirhash_mtx. */
  110         TAILQ_ENTRY(dirhash) dh_list;   /* chain of all dirhashes */
  111 };
  112 
  113 
  114 /*
  115  * Dirhash functions.
  116  */
  117 void    ufsdirhash_init(void);
  118 void    ufsdirhash_uninit(void);
  119 int     ufsdirhash_build(struct inode *);
  120 doff_t  ufsdirhash_findfree(struct inode *, int, int *);
  121 doff_t  ufsdirhash_enduseful(struct inode *);
  122 int     ufsdirhash_lookup(struct inode *, char *, int, doff_t *, struct buf **,
  123             doff_t *);
  124 void    ufsdirhash_newblk(struct inode *, doff_t);
  125 void    ufsdirhash_add(struct inode *, struct direct *, doff_t);
  126 void    ufsdirhash_remove(struct inode *, struct direct *, doff_t);
  127 void    ufsdirhash_move(struct inode *, struct direct *, doff_t, doff_t);
  128 void    ufsdirhash_dirtrunc(struct inode *, doff_t);
  129 void    ufsdirhash_free(struct inode *);
  130 
  131 void    ufsdirhash_checkblock(struct inode *, char *, doff_t);
  132 
  133 #endif /* !_UFS_UFS_DIRHASH_H_ */

Cache object: e63c77374f54bc46ebd3531b95aecc68


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.