subr_hash.c

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 /*      $NetBSD: subr_hash.c,v 1.12 2021/06/13 14:58:49 simonb Exp $    */
    2 
    3 /*
    4  * Copyright (c) 1982, 1986, 1991, 1993
    5  *      The Regents of the University of California.  All rights reserved.
    6  * (c) UNIX System Laboratories, Inc.
    7  * All or some portions of this file are derived from material licensed
    8  * to the University of California by American Telephone and Telegraph
    9  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
   10  * the permission of UNIX System Laboratories, Inc.
   11  *
   12  * Redistribution and use in source and binary forms, with or without
   13  * modification, are permitted provided that the following conditions
   14  * are met:
   15  * 1. Redistributions of source code must retain the above copyright
   16  *    notice, this list of conditions and the following disclaimer.
   17  * 2. Redistributions in binary form must reproduce the above copyright
   18  *    notice, this list of conditions and the following disclaimer in the
   19  *    documentation and/or other materials provided with the distribution.
   20  * 3. Neither the name of the University nor the names of its contributors
   21  *    may be used to endorse or promote products derived from this software
   22  *    without specific prior written permission.
   23  *
   24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   34  * SUCH DAMAGE.
   35  *
   36  *      @(#)kern_subr.c 8.4 (Berkeley) 2/14/95
   37  */
   38 
   39 #include <sys/cdefs.h>
   40 __KERNEL_RCSID(0, "$NetBSD: subr_hash.c,v 1.12 2021/06/13 14:58:49 simonb Exp $");
   41 
   42 #include <sys/param.h>
   43 #include <sys/bitops.h>
   44 #include <sys/kmem.h>
   45 #include <sys/systm.h>
   46 #include <sys/pslist.h>
   47 #include <sys/rwlock.h>
   48 #include <sys/sysctl.h>
   49 
   50 static int hashstat_sysctl(SYSCTLFN_PROTO);
   51 
   52 static size_t
   53 hash_list_size(enum hashtype htype)
   54 {
   55         LIST_HEAD(, generic) *hashtbl_list;
   56         SLIST_HEAD(, generic) *hashtbl_slist;
   57         TAILQ_HEAD(, generic) *hashtbl_tailq;
   58         struct pslist_head *hashtbl_pslist;
   59         size_t esize;
   60 
   61         switch (htype) {
   62         case HASH_LIST:
   63                 esize = sizeof(*hashtbl_list);
   64                 break;
   65         case HASH_PSLIST:
   66                 esize = sizeof(*hashtbl_pslist);
   67                 break;
   68         case HASH_SLIST:
   69                 esize = sizeof(*hashtbl_slist);
   70                 break;
   71         case HASH_TAILQ:
   72                 esize = sizeof(*hashtbl_tailq);
   73                 break;
   74         default:
   75                 panic("hashdone: invalid table type");
   76         }
   77         return esize;
   78 }
   79 
   80 /*
   81  * General routine to allocate a hash table.
   82  * Allocate enough memory to hold at least `elements' list-head pointers.
   83  * Return a pointer to the allocated space and set *hashmask to a pattern
   84  * suitable for masking a value to use as an index into the returned array.
   85  */
   86 void *
   87 hashinit(u_int elements, enum hashtype htype, bool waitok, u_long *hashmask)
   88 {
   89         LIST_HEAD(, generic) *hashtbl_list;
   90         SLIST_HEAD(, generic) *hashtbl_slist;
   91         TAILQ_HEAD(, generic) *hashtbl_tailq;
   92         struct pslist_head *hashtbl_pslist;
   93         u_long hashsize, i;
   94         size_t esize;
   95         void *p;
   96 
   97         KASSERT(elements > 0);
   98 
   99 #define MAXELEMENTS (1U << ((sizeof(elements) * NBBY) - 1))
  100         if (elements > MAXELEMENTS)
  101                 elements = MAXELEMENTS;
  102 
  103         hashsize = 1UL << (ilog2(elements - 1) + 1);
  104         esize = hash_list_size(htype);
  105 
  106         p = kmem_alloc(hashsize * esize, waitok ? KM_SLEEP : KM_NOSLEEP);
  107         if (p == NULL)
  108                 return NULL;
  109 
  110         switch (htype) {
  111         case HASH_LIST:
  112                 hashtbl_list = p;
  113                 for (i = 0; i < hashsize; i++)
  114                         LIST_INIT(&hashtbl_list[i]);
  115                 break;
  116         case HASH_PSLIST:
  117                 hashtbl_pslist = p;
  118                 for (i = 0; i < hashsize; i++)
  119                         PSLIST_INIT(&hashtbl_pslist[i]);
  120                 break;
  121         case HASH_SLIST:
  122                 hashtbl_slist = p;
  123                 for (i = 0; i < hashsize; i++)
  124                         SLIST_INIT(&hashtbl_slist[i]);
  125                 break;
  126         case HASH_TAILQ:
  127                 hashtbl_tailq = p;
  128                 for (i = 0; i < hashsize; i++)
  129                         TAILQ_INIT(&hashtbl_tailq[i]);
  130                 break;
  131         }
  132         *hashmask = hashsize - 1;
  133         return p;
  134 }
  135 
  136 /*
  137  * Free memory from hash table previosly allocated via hashinit().
  138  */
  139 void
  140 hashdone(void *hashtbl, enum hashtype htype, u_long hashmask)
  141 {
  142         const size_t esize = hash_list_size(htype);
  143         kmem_free(hashtbl, esize * (hashmask + 1));
  144 }
  145 
  146 /*
  147  * Support for hash statistics (vmstat -H / vmstat -h hashname).
  148  */
  149 
  150 struct hashstat {
  151         const char *hs_name;
  152         hashstat_func_t hs_func;
  153         TAILQ_ENTRY(hashstat) hs_next;
  154 };
  155 TAILQ_HEAD(, hashstat) hashstat_list =
  156     TAILQ_HEAD_INITIALIZER(hashstat_list);
  157 static krwlock_t hashstat_lock;
  158 
  159 void
  160 hashstat_register(const char *name, hashstat_func_t func)
  161 {
  162         struct hashstat *hs;
  163 
  164         hs = kmem_alloc(sizeof(*hs), KM_SLEEP);
  165 
  166         hs->hs_name = name;
  167         hs->hs_func = func;
  168 
  169         rw_enter(&hashstat_lock, RW_WRITER);
  170         TAILQ_INSERT_TAIL(&hashstat_list, hs, hs_next);
  171         rw_exit(&hashstat_lock);
  172 }
  173 
  174 /*
  175  * sysctl support for returning kernel hash statistics.
  176  *
  177  * We (ab)use CTL_DESCRIBE and CTL_QUERY:
  178  * When passed an OID of CTL_DESCRIBE, return a list and description
  179  * of the available hashes.
  180  * When passed an OID of CTL_QUERY, use the hash name passed in the
  181  * "new" hash input as the name of a single hash to return stats on.
  182  */
  183 static int
  184 hashstat_sysctl(SYSCTLFN_ARGS)
  185 {
  186         struct hashstat_sysctl hs;
  187         struct hashstat *hash;
  188         char queryname[SYSCTL_NAMELEN];
  189         size_t written;
  190         bool fill, query;
  191         int error;
  192 
  193         if (oldp == NULL) {
  194                 *oldlenp = 0;
  195                 TAILQ_FOREACH(hash, &hashstat_list, hs_next)
  196                         *oldlenp += sizeof(hs);
  197                 return 0;
  198         }
  199 
  200         error = 0;
  201         written = 0;
  202 
  203         if (namelen > 0 && name[0] == CTL_DESCRIBE)
  204                 fill = false;
  205         else
  206                 fill = true;
  207 
  208         if (namelen > 0 && name[0] == CTL_QUERY) {
  209                 const struct hashstat_sysctl *h = newp;
  210                 size_t s;
  211 
  212                 if (h == NULL) {
  213                         /* Can't QUERY one hash without supplying the hash name. */
  214                         return EINVAL;
  215                 }
  216                 query = true;
  217                 error = sysctl_copyinstr(l, h->hash_name, queryname, 
  218                     sizeof(queryname), &s);
  219                 if (error)
  220                         return error;
  221         } else {
  222                 query = false;
  223         }
  224 
  225         sysctl_unlock();
  226         rw_enter(&hashstat_lock, RW_READER);
  227         TAILQ_FOREACH(hash, &hashstat_list, hs_next) {
  228                 if (query && (strcmp(hash->hs_name, queryname) != 0)) {
  229                         continue;
  230                 }
  231 
  232                 memset(&hs, 0, sizeof(hs));
  233                 error = hash->hs_func(&hs, fill);
  234                 if (error)
  235                         break;
  236 
  237                 error = sysctl_copyout(l, &hs, oldp, sizeof(hs));
  238                 if (error)
  239                         break;
  240                 written += sizeof(hs);
  241                 oldp = (char *)oldp + sizeof(hs);
  242         }
  243         rw_exit(&hashstat_lock);
  244         sysctl_relock();
  245 
  246         if (query && written == 0)      /* query not found? */
  247                 error = ENOENT;
  248 
  249         *oldlenp = written;
  250         return error;
  251 }
  252 
  253 
  254 SYSCTL_SETUP(sysctl_hash_setup, "sysctl hash stats setup")
  255 {
  256 
  257         rw_init(&hashstat_lock);        /* as good a place as any for this */
  258 
  259         sysctl_createv(NULL, 0, NULL, NULL,
  260                        CTLFLAG_PERMANENT|CTLFLAG_READWRITE,
  261                        CTLTYPE_STRUCT,
  262                        "hashstat", SYSCTL_DESCR("kernel hash statistics"),
  263                        hashstat_sysctl, 0, NULL, 0,
  264                        CTL_KERN, CTL_CREATE, CTL_EOL);
  265 }

Cache object: dcb63636dc9d28851565b9ffa0f0d594

[ 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.

FreeBSD/Linux Kernel Cross Reference sys/kern/subr_hash.c

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_hash.c