1 /* $NetBSD: subr_hash.c,v 1.15 2026/01/04 03:18:16 riastradh 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.15 2026/01/04 03:18:16 riastradh Exp $"); 41 42 #include <sys/param.h> 43 #include <sys/types.h> 44 45 #include <sys/bitops.h> 46 #include <sys/kmem.h> 47 #include <sys/pslist.h> 48 #include <sys/rwlock.h> 49 #include <sys/sdt.h> 50 #include <sys/sysctl.h> 51 #include <sys/systm.h> 52 53 static int hashstat_sysctl(SYSCTLFN_PROTO); 54 55 static size_t 56 hash_list_size(enum hashtype htype) 57 { 58 LIST_HEAD(, generic) *hashtbl_list; 59 SLIST_HEAD(, generic) *hashtbl_slist; 60 TAILQ_HEAD(, generic) *hashtbl_tailq; 61 struct pslist_head *hashtbl_pslist; 62 size_t esize; 63 64 switch (htype) { 65 case HASH_LIST: 66 esize = sizeof(*hashtbl_list); 67 break; 68 case HASH_PSLIST: 69 esize = sizeof(*hashtbl_pslist); 70 break; 71 case HASH_SLIST: 72 esize = sizeof(*hashtbl_slist); 73 break; 74 case HASH_TAILQ: 75 esize = sizeof(*hashtbl_tailq); 76 break; 77 default: 78 panic("hashdone: invalid table type"); 79 } 80 return esize; 81 } 82 83 /* 84 * General routine to allocate a hash table. 85 * Allocate enough memory to hold at least `elements' list-head pointers. 86 * Return a pointer to the allocated space and set *hashmask to a pattern 87 * suitable for masking a value to use as an index into the returned array. 88 */ 89 void * 90 hashinit(u_int elements, enum hashtype htype, bool waitok, u_long *hashmask) 91 { 92 LIST_HEAD(, generic) *hashtbl_list; 93 SLIST_HEAD(, generic) *hashtbl_slist; 94 TAILQ_HEAD(, generic) *hashtbl_tailq; 95 struct pslist_head *hashtbl_pslist; 96 u_long hashsize, i; 97 size_t esize; 98 void *p; 99 100 KASSERT(elements > 0); 101 102 #define MAXELEMENTS (1U << ((sizeof(elements) * NBBY) - 1)) 103 if (elements > MAXELEMENTS) 104 elements = MAXELEMENTS; 105 106 hashsize = 1UL << (ilog2(elements - 1) + 1); 107 esize = hash_list_size(htype); 108 109 p = kmem_alloc(hashsize * esize, waitok ? KM_SLEEP : KM_NOSLEEP); 110 if (p == NULL) 111 return NULL; 112 113 switch (htype) { 114 case HASH_LIST: 115 hashtbl_list = p; 116 for (i = 0; i < hashsize; i++) 117 LIST_INIT(&hashtbl_list[i]); 118 break; 119 case HASH_PSLIST: 120 hashtbl_pslist = p; 121 for (i = 0; i < hashsize; i++) 122 PSLIST_INIT(&hashtbl_pslist[i]); 123 break; 124 case HASH_SLIST: 125 hashtbl_slist = p; 126 for (i = 0; i < hashsize; i++) 127 SLIST_INIT(&hashtbl_slist[i]); 128 break; 129 case HASH_TAILQ: 130 hashtbl_tailq = p; 131 for (i = 0; i < hashsize; i++) 132 TAILQ_INIT(&hashtbl_tailq[i]); 133 break; 134 } 135 *hashmask = hashsize - 1; 136 return p; 137 } 138 139 /* 140 * Free memory from hash table previously allocated via hashinit(). 141 */ 142 void 143 hashdone(void *hashtbl, enum hashtype htype, u_long hashmask) 144 { 145 const size_t esize = hash_list_size(htype); 146 kmem_free(hashtbl, esize * (hashmask + 1)); 147 } 148 149 /* 150 * Support for hash statistics (vmstat -H / vmstat -h hashname). 151 */ 152 153 struct hashstat { 154 const char *hs_name; 155 hashstat_func_t hs_func; 156 TAILQ_ENTRY(hashstat) hs_next; 157 }; 158 TAILQ_HEAD(, hashstat) hashstat_list = 159 TAILQ_HEAD_INITIALIZER(hashstat_list); 160 static krwlock_t hashstat_lock; 161 162 void 163 hashstat_register(const char *name, hashstat_func_t func) 164 { 165 struct hashstat *hs; 166 167 hs = kmem_alloc(sizeof(*hs), KM_SLEEP); 168 169 hs->hs_name = name; 170 hs->hs_func = func; 171 172 rw_enter(&hashstat_lock, RW_WRITER); 173 TAILQ_INSERT_TAIL(&hashstat_list, hs, hs_next); 174 rw_exit(&hashstat_lock); 175 } 176 177 /* 178 * sysctl support for returning kernel hash statistics. 179 * 180 * We (ab)use CTL_DESCRIBE and CTL_QUERY: 181 * When passed an OID of CTL_DESCRIBE, return a list and description 182 * of the available hashes. 183 * When passed an OID of CTL_QUERY, use the hash name passed in the 184 * "new" hash input as the name of a single hash to return stats on. 185 */ 186 static int 187 hashstat_sysctl(SYSCTLFN_ARGS) 188 { 189 struct hashstat_sysctl hs; 190 struct hashstat *hash; 191 char queryname[SYSCTL_NAMELEN]; 192 size_t written; 193 bool fill, query; 194 int error; 195 196 if (oldp == NULL) { 197 *oldlenp = 0; 198 TAILQ_FOREACH(hash, &hashstat_list, hs_next) 199 *oldlenp += sizeof(hs); 200 return 0; 201 } 202 203 error = 0; 204 written = 0; 205 206 if (namelen > 0 && name[0] == CTL_DESCRIBE) 207 fill = false; 208 else 209 fill = true; 210 211 if (namelen > 0 && name[0] == CTL_QUERY) { 212 const struct hashstat_sysctl *h = newp; 213 size_t s; 214 215 if (h == NULL) { 216 /* Can't QUERY one hash without supplying the hash name. */ 217 return SET_ERROR(EINVAL); 218 } 219 query = true; 220 error = sysctl_copyinstr(l, h->hash_name, queryname, 221 sizeof(queryname), &s); 222 if (error) 223 return error; 224 } else { 225 query = false; 226 } 227 228 sysctl_unlock(); 229 rw_enter(&hashstat_lock, RW_READER); 230 TAILQ_FOREACH(hash, &hashstat_list, hs_next) { 231 if (query && (strcmp(hash->hs_name, queryname) != 0)) { 232 continue; 233 } 234 235 memset(&hs, 0, sizeof(hs)); 236 error = hash->hs_func(&hs, fill); 237 if (error) 238 break; 239 240 error = sysctl_copyout(l, &hs, oldp, sizeof(hs)); 241 if (error) 242 break; 243 written += sizeof(hs); 244 oldp = (char *)oldp + sizeof(hs); 245 } 246 rw_exit(&hashstat_lock); 247 sysctl_relock(); 248 249 if (query && written == 0) /* query not found? */ 250 error = SET_ERROR(ENOENT); 251 252 *oldlenp = written; 253 return error; 254 } 255 256 257 SYSCTL_SETUP(sysctl_hash_setup, "sysctl hash stats setup") 258 { 259 260 rw_init(&hashstat_lock); /* as good a place as any for this */ 261 262 sysctl_createv(NULL, 0, NULL, NULL, 263 CTLFLAG_PERMANENT|CTLFLAG_READWRITE, 264 CTLTYPE_STRUCT, 265 "hashstat", SYSCTL_DESCR("kernel hash statistics"), 266 hashstat_sysctl, 0, NULL, 0, 267 CTL_KERN, CTL_CREATE, CTL_EOL); 268 } 269
Indexes created Fri Feb 20 16:20:20 UTC 2026