1 /*- 2 * SPDX-License-Identifier: BSD-3-Clause 3 * 4 * Copyright (c) 2026 Gleb Smirnoff <glebius@FreeBSD.org> 5 * Copyright (c) 1982, 1986, 1991, 1993 6 * The Regents of the University of California. All rights reserved. 7 * (c) UNIX System Laboratories, Inc. 8 * All or some portions of this file are derived from material licensed 9 * to the University of California by American Telephone and Telegraph 10 * Co. or Unix System Laboratories, Inc. and are reproduced herein with 11 * the permission of UNIX System Laboratories, Inc. 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 3. Neither the name of the University nor the names of its contributors 22 * may be used to endorse or promote products derived from this software 23 * without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 */ 37 38 #include <sys/param.h> 39 #include <sys/systm.h> 40 #include <sys/malloc.h> 41 #include <sys/ck.h> 42 #include <sys/queue.h> 43 #include <sys/mutex.h> 44 #include <sys/rmlock.h> 45 #include <sys/rwlock.h> 46 #include <sys/sx.h> 47 #include <sys/hash.h> 48 49 #define ASSERT_NOPAD(head, lock) _Static_assert( \ 50 sizeof(head ## _HEAD(, foo)) + sizeof(struct lock) == \ 51 sizeof(struct { head ## _HEAD(, foo) h; struct lock l; }), \ 52 "Structure of " #head "_HEAD and " #lock " has padding") 53 ASSERT_NOPAD(LIST, mtx); 54 ASSERT_NOPAD(CK_LIST, mtx); 55 ASSERT_NOPAD(SLIST, mtx); 56 ASSERT_NOPAD(CK_SLIST, mtx); 57 ASSERT_NOPAD(STAILQ, mtx); 58 ASSERT_NOPAD(CK_STAILQ, mtx); 59 ASSERT_NOPAD(TAILQ, mtx); 60 ASSERT_NOPAD(LIST, rwlock); 61 ASSERT_NOPAD(CK_LIST, rwlock); 62 ASSERT_NOPAD(SLIST, rwlock); 63 ASSERT_NOPAD(CK_SLIST, rwlock); 64 ASSERT_NOPAD(STAILQ, rwlock); 65 ASSERT_NOPAD(CK_STAILQ, rwlock); 66 ASSERT_NOPAD(TAILQ, rwlock); 67 ASSERT_NOPAD(LIST, sx); 68 ASSERT_NOPAD(CK_LIST, sx); 69 ASSERT_NOPAD(SLIST, sx); 70 ASSERT_NOPAD(CK_SLIST, sx); 71 ASSERT_NOPAD(STAILQ, sx); 72 ASSERT_NOPAD(CK_STAILQ, sx); 73 ASSERT_NOPAD(TAILQ, sx); 74 ASSERT_NOPAD(LIST, rmlock); 75 ASSERT_NOPAD(CK_LIST, rmlock); 76 ASSERT_NOPAD(SLIST, rmlock); 77 ASSERT_NOPAD(CK_SLIST, rmlock); 78 ASSERT_NOPAD(STAILQ, rmlock); 79 ASSERT_NOPAD(CK_STAILQ, rmlock); 80 ASSERT_NOPAD(TAILQ, rmlock); 81 ASSERT_NOPAD(LIST, rmslock); 82 ASSERT_NOPAD(CK_LIST, rmslock); 83 ASSERT_NOPAD(SLIST, rmslock); 84 ASSERT_NOPAD(CK_SLIST, rmslock); 85 ASSERT_NOPAD(STAILQ, rmslock); 86 ASSERT_NOPAD(CK_STAILQ, rmslock); 87 ASSERT_NOPAD(TAILQ, rmslock); 88 #undef ASSERT_NOPAD 89 90 static inline void 91 hashalloc_sizes(struct hashalloc_args *args, size_t *hdrsize, size_t *loffset) 92 { 93 switch (args->head) { 94 case HASH_HEAD_LIST: 95 *loffset = sizeof(LIST_HEAD(, foo)); 96 break; 97 case HASH_HEAD_CK_LIST: 98 *loffset = sizeof(CK_LIST_HEAD(, foo)); 99 break; 100 case HASH_HEAD_SLIST: 101 *loffset = sizeof(SLIST_HEAD(, foo)); 102 break; 103 case HASH_HEAD_CK_SLIST: 104 *loffset = sizeof(CK_SLIST_HEAD(, foo)); 105 break; 106 case HASH_HEAD_STAILQ: 107 *loffset = sizeof(STAILQ_HEAD(, foo)); 108 break; 109 case HASH_HEAD_CK_STAILQ: 110 *loffset = sizeof(CK_STAILQ_HEAD(, foo)); 111 break; 112 case HASH_HEAD_TAILQ: 113 *loffset = sizeof(TAILQ_HEAD(, foo)); 114 break; 115 } 116 117 switch (args->lock) { 118 case HASH_LOCK_NONE: 119 *hdrsize = *loffset; 120 break; 121 case HASH_LOCK_MTX: 122 *hdrsize = *loffset + sizeof(struct mtx); 123 break; 124 case HASH_LOCK_RWLOCK: 125 *hdrsize = *loffset + sizeof(struct rwlock); 126 break; 127 case HASH_LOCK_SX: 128 *hdrsize = *loffset + sizeof(struct sx); 129 break; 130 case HASH_LOCK_RMLOCK: 131 *hdrsize = *loffset + sizeof(struct rmlock); 132 break; 133 case HASH_LOCK_RMSLOCK: 134 *hdrsize = *loffset + sizeof(struct rmslock); 135 break; 136 } 137 138 if (args->hdrsize > 0) { 139 MPASS(args->hdrsize >= *hdrsize); 140 *hdrsize = args->hdrsize; 141 } else 142 args->hdrsize = *hdrsize; 143 } 144 145 void * 146 hashalloc(struct hashalloc_args *args) 147 { 148 static const int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 149 1531, 2039, 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653, 150 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; 151 void *mem; 152 size_t size, hdrsize, loffset; 153 u_int i; 154 155 MPASS(args->version == 0); 156 MPASS(args->size > 0); 157 158 switch (args->type) { 159 case HASH_TYPE_POWER2: 160 for (size = 1; size <= args->size; size <<= 1) 161 continue; 162 size >>= 1; 163 break; 164 case HASH_TYPE_PRIME: 165 for (i = nitems(primes) - 1; args->size < primes[i]; i--) 166 ; 167 size = primes[i]; 168 break; 169 } 170 171 hashalloc_sizes(args, &hdrsize, &loffset); 172 173 mem = malloc(size * hdrsize, args->mtype, args->mflags); 174 if (mem == NULL) { 175 args->error = ENOMEM; 176 return (NULL); 177 } 178 179 switch (args->lock) { 180 case HASH_LOCK_NONE: 181 break; 182 case HASH_LOCK_MTX: 183 MPASS(args->lname != NULL); 184 if ((args->mflags & M_ZERO) == 0) 185 args->lopts |= MTX_NEW; 186 break; 187 case HASH_LOCK_RWLOCK: 188 MPASS(args->lname != NULL); 189 if ((args->mflags & M_ZERO) == 0) 190 args->lopts |= RW_NEW; 191 break; 192 case HASH_LOCK_SX: 193 MPASS(args->lname != NULL); 194 if ((args->mflags & M_ZERO) == 0) 195 args->lopts |= SX_NEW; 196 break; 197 case HASH_LOCK_RMLOCK: 198 MPASS(args->lname != NULL); 199 if ((args->mflags & M_ZERO) == 0) 200 args->lopts |= RM_NEW; 201 break; 202 case HASH_LOCK_RMSLOCK: 203 MPASS(args->lname != NULL); 204 break; 205 } 206 207 for (i = 0; i < size; i++) { 208 void *slot; 209 210 slot = (char *)mem + i * hdrsize; 211 switch (args->head) { 212 case HASH_HEAD_LIST: 213 LIST_INIT((LIST_HEAD(, foo) *)slot); 214 break; 215 case HASH_HEAD_CK_LIST: 216 CK_LIST_INIT((CK_LIST_HEAD(, foo) *)slot); 217 break; 218 case HASH_HEAD_SLIST: 219 SLIST_INIT((SLIST_HEAD(, foo) *)slot); 220 break; 221 case HASH_HEAD_CK_SLIST: 222 CK_SLIST_INIT((CK_SLIST_HEAD(, foo) *)slot); 223 break; 224 case HASH_HEAD_STAILQ: 225 STAILQ_INIT((STAILQ_HEAD(, foo) *)slot); 226 break; 227 case HASH_HEAD_CK_STAILQ: 228 CK_STAILQ_INIT((CK_STAILQ_HEAD(, foo) *)slot); 229 break; 230 case HASH_HEAD_TAILQ: 231 TAILQ_INIT((TAILQ_HEAD(, foo) *)slot); 232 break; 233 } 234 235 slot = (char *)slot + loffset; 236 switch (args->lock) { 237 case HASH_LOCK_NONE: 238 break; 239 case HASH_LOCK_MTX: 240 mtx_init((struct mtx *)slot, args->lname, NULL, 241 args->lopts); 242 break; 243 case HASH_LOCK_RWLOCK: 244 rw_init_flags((struct rwlock *)slot, args->lname, 245 args->lopts); 246 break; 247 case HASH_LOCK_SX: 248 sx_init_flags((struct sx *)slot, args->lname, 249 args->lopts); 250 break; 251 case HASH_LOCK_RMLOCK: 252 rm_init_flags((struct rmlock *)slot, args->lname, 253 args->lopts); 254 break; 255 case HASH_LOCK_RMSLOCK: 256 rms_init((struct rmslock *)slot, args->lname); 257 break; 258 } 259 260 if (args->ctor != NULL) { 261 slot = (char *)mem + i * hdrsize; 262 if ((args->error = args->ctor(slot)) != 0) { 263 slot = (char *)slot + loffset; 264 switch (args->lock) { 265 case HASH_LOCK_NONE: 266 break; 267 case HASH_LOCK_MTX: 268 mtx_destroy((struct mtx *)slot); 269 break; 270 case HASH_LOCK_RWLOCK: 271 rw_destroy((struct rwlock *)slot); 272 break; 273 case HASH_LOCK_SX: 274 sx_destroy((struct sx *)slot); 275 break; 276 case HASH_LOCK_RMLOCK: 277 rm_destroy((struct rmlock *)slot); 278 break; 279 case HASH_LOCK_RMSLOCK: 280 rms_destroy((struct rmslock *)slot); 281 break; 282 } 283 args->size = i; 284 hashfree(mem, args); 285 return (NULL); 286 } 287 } 288 } 289 290 args->size = size; 291 return (mem); 292 } 293 294 void 295 hashfree(void *mem, struct hashalloc_args *args) 296 { 297 size_t hdrsize, loffset; 298 299 if (__predict_false(mem == NULL)) 300 return; 301 302 hashalloc_sizes(args, &hdrsize, &loffset); 303 304 for (u_int i = 0; i < args->size; i++) { 305 #ifdef INVARIANTS 306 static const char msg[] = 307 "%s: hashtbl %p not empty (malloc type %s)"; 308 #endif 309 #define HPASS(exp) KASSERT(exp, (msg, __func__, mem, args->mtype->ks_shortdesc)) 310 void *slot; 311 312 slot = (char *)mem + i * hdrsize; 313 if (args->dtor != NULL) 314 args->dtor(slot); 315 switch (args->head) { 316 case HASH_HEAD_LIST: 317 HPASS(LIST_EMPTY((LIST_HEAD(, foo) *)slot)); 318 break; 319 case HASH_HEAD_CK_LIST: 320 HPASS(CK_LIST_EMPTY((CK_LIST_HEAD(, foo) *)slot)); 321 break; 322 case HASH_HEAD_SLIST: 323 HPASS(SLIST_EMPTY((SLIST_HEAD(, foo) *)slot)); 324 break; 325 case HASH_HEAD_CK_SLIST: 326 HPASS(CK_SLIST_EMPTY((CK_SLIST_HEAD(, foo) *)slot)); 327 break; 328 case HASH_HEAD_STAILQ: 329 HPASS(STAILQ_EMPTY((STAILQ_HEAD(, foo) *)slot)); 330 break; 331 case HASH_HEAD_CK_STAILQ: 332 HPASS(CK_STAILQ_EMPTY((CK_STAILQ_HEAD(, foo) *)slot)); 333 break; 334 case HASH_HEAD_TAILQ: 335 HPASS(TAILQ_EMPTY((TAILQ_HEAD(, foo) *)slot)); 336 break; 337 } 338 #undef HPASS 339 340 slot = (char *)slot + loffset; 341 switch (args->lock) { 342 case HASH_LOCK_NONE: 343 break; 344 case HASH_LOCK_MTX: 345 mtx_destroy((struct mtx *)slot); 346 break; 347 case HASH_LOCK_RWLOCK: 348 rw_destroy((struct rwlock *)slot); 349 break; 350 case HASH_LOCK_SX: 351 sx_destroy((struct sx *)slot); 352 break; 353 case HASH_LOCK_RMLOCK: 354 rm_destroy((struct rmlock *)slot); 355 break; 356 case HASH_LOCK_RMSLOCK: 357 rms_destroy((struct rmslock *)slot); 358 break; 359 } 360 } 361 362 free(mem, args->mtype); 363 } 364 365 static __inline int 366 hash_mflags(int flags) 367 { 368 369 return ((flags & HASH_NOWAIT) ? M_NOWAIT : M_WAITOK); 370 } 371 372 /* 373 * General routine to allocate a hash table with control of memory flags. 374 */ 375 void * 376 hashinit_flags(int elements, struct malloc_type *type, u_long *hashmask, 377 int flags) 378 { 379 struct hashalloc_args args = { 380 .size = elements, 381 .mtype = type, 382 .mflags = hash_mflags(flags), 383 }; 384 void *rv; 385 386 rv = hashalloc(&args); 387 if (rv != NULL) 388 *hashmask = args.size - 1; 389 return (rv); 390 } 391 392 /* 393 * Allocate and initialize a hash table with default flag: may sleep. 394 */ 395 void * 396 hashinit(int elements, struct malloc_type *type, u_long *hashmask) 397 { 398 399 return (hashinit_flags(elements, type, hashmask, HASH_WAITOK)); 400 } 401 402 void 403 hashdestroy(void *vhashtbl, struct malloc_type *type, u_long hashmask) 404 { 405 struct hashalloc_args args = { 406 .size = hashmask + 1, 407 .mtype = type, 408 }; 409 410 hashfree(vhashtbl, &args); 411 } 412 413 /* 414 * General routine to allocate a prime number sized hash table with control of 415 * memory flags. 416 */ 417 void * 418 phashinit_flags(int elements, struct malloc_type *type, u_long *nentries, int flags) 419 { 420 struct hashalloc_args args = { 421 .size = elements, 422 .mtype = type, 423 .type = HASH_TYPE_PRIME, 424 .mflags = hash_mflags(flags), 425 }; 426 void *rv; 427 428 rv = hashalloc(&args); 429 if (rv != NULL) 430 *nentries = args.size; 431 return (rv); 432 } 433 434 /* 435 * Allocate and initialize a prime number sized hash table with default flag: 436 * may sleep. 437 */ 438 void * 439 phashinit(int elements, struct malloc_type *type, u_long *nentries) 440 { 441 442 return (phashinit_flags(elements, type, nentries, HASH_WAITOK)); 443 } 444