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 50static int hashstat_sysctl(SYSCTLFN_PROTO); 51 52static size_t 53hash_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 */ 86void * 87hashinit(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 */ 139void 140hashdone(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 150struct hashstat { 151 const char *hs_name; 152 hashstat_func_t hs_func; 153 TAILQ_ENTRY(hashstat) hs_next; 154}; 155TAILQ_HEAD(, hashstat) hashstat_list = 156 TAILQ_HEAD_INITIALIZER(hashstat_list); 157static krwlock_t hashstat_lock; 158 159void 160hashstat_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 */ 183static int 184hashstat_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 254SYSCTL_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} 266