186333Sdillon/*- 2139803Simp * Copyright (c) 2001 Matthew Dillon. All Rights Reserved. 386333Sdillon * 4139803Simp * Redistribution and use in source and binary forms, with or without 5139803Simp * modification, are permitted provided that the following conditions 6139803Simp * are met: 7139803Simp * 1. Redistributions of source code must retain the above copyright 8139803Simp * notice, this list of conditions and the following disclaimer. 9139803Simp * 2. Redistributions in binary form must reproduce the above copyright 10139803Simp * notice, this list of conditions and the following disclaimer in the 11139803Simp * documentation and/or other materials provided with the distribution. 12139803Simp * 13139803Simp * THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND 14139803Simp * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15139803Simp * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 16139803Simp * ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE 17139803Simp * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 18139803Simp * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 19139803Simp * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 20139803Simp * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 21139803Simp * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 22139803Simp * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 23139803Simp * SUCH DAMAGE. 24139803Simp */ 25139803Simp 26139803Simp/* Mutex pool routines. These routines are designed to be used as short 27170035Srwatson * term leaf mutexes (e.g. the last mutex you might acquire other then 2886333Sdillon * calling msleep()). They operate using a shared pool. A mutex is chosen 2986333Sdillon * from the pool based on the supplied pointer (which may or may not be 3086333Sdillon * valid). 3186333Sdillon * 3286333Sdillon * Advantages: 3386333Sdillon * - no structural overhead. Mutexes can be associated with structures 3486333Sdillon * without adding bloat to the structures. 3586333Sdillon * - mutexes can be obtained for invalid pointers, useful when uses 3686333Sdillon * mutexes to interlock destructor ops. 37116305Smux * - no initialization/destructor overhead. 3886333Sdillon * - can be used with msleep. 3986333Sdillon * 4086333Sdillon * Disadvantages: 41116305Smux * - should generally only be used as leaf mutexes. 4286333Sdillon * - pool/pool dependancy ordering cannot be depended on. 43116305Smux * - possible L1 cache mastersip contention between cpus. 4486333Sdillon */ 4586333Sdillon 46116182Sobrien#include <sys/cdefs.h> 47116182Sobrien__FBSDID("$FreeBSD$"); 48116182Sobrien 4986333Sdillon#include <sys/param.h> 5086333Sdillon#include <sys/proc.h> 5186333Sdillon#include <sys/kernel.h> 5286333Sdillon#include <sys/ktr.h> 5386333Sdillon#include <sys/lock.h> 5486333Sdillon#include <sys/malloc.h> 5586333Sdillon#include <sys/mutex.h> 5686333Sdillon#include <sys/systm.h> 5786333Sdillon 58117494Struckman 59141616Sphkstatic MALLOC_DEFINE(M_MTXPOOL, "mtx_pool", "mutex pool"); 60117494Struckman 61117494Struckman/* Pool sizes must be a power of two */ 62117494Struckman#ifndef MTX_POOL_LOCKBUILDER_SIZE 63117494Struckman#define MTX_POOL_LOCKBUILDER_SIZE 128 6486333Sdillon#endif 65117494Struckman#ifndef MTX_POOL_SLEEP_SIZE 66117494Struckman#define MTX_POOL_SLEEP_SIZE 128 67117494Struckman#endif 6886333Sdillon 69117494Struckmanstruct mtxpool_header { 70117494Struckman int mtxpool_size; 71117494Struckman int mtxpool_mask; 72117494Struckman int mtxpool_shift; 73117494Struckman int mtxpool_next; 74117494Struckman}; 7586333Sdillon 76117494Struckmanstruct mtx_pool { 77117494Struckman struct mtxpool_header mtx_pool_header; 78117494Struckman struct mtx mtx_pool_ary[1]; 79117494Struckman}; 8086333Sdillon 81117494Struckmanstatic struct mtx_pool_lockbuilder { 82117494Struckman struct mtxpool_header mtx_pool_header; 83117494Struckman struct mtx mtx_pool_ary[MTX_POOL_LOCKBUILDER_SIZE]; 84117494Struckman} lockbuilder_pool; 85117494Struckman 86117494Struckman#define mtx_pool_size mtx_pool_header.mtxpool_size 87117494Struckman#define mtx_pool_mask mtx_pool_header.mtxpool_mask 88117494Struckman#define mtx_pool_shift mtx_pool_header.mtxpool_shift 89117494Struckman#define mtx_pool_next mtx_pool_header.mtxpool_next 90117494Struckman 91117494Struckmanstruct mtx_pool *mtxpool_sleep; 92117494Struckmanstruct mtx_pool *mtxpool_lockbuilder; 93117494Struckman 94117494Struckman#if UINTPTR_MAX == UINT64_MAX /* 64 bits */ 95117494Struckman# define POINTER_BITS 64 96117494Struckman# define HASH_MULTIPLIER 11400714819323198485u /* (2^64)*(sqrt(5)-1)/2 */ 97117494Struckman#else /* assume 32 bits */ 98117494Struckman# define POINTER_BITS 32 99117494Struckman# define HASH_MULTIPLIER 2654435769u /* (2^32)*(sqrt(5)-1)/2 */ 100117494Struckman#endif 101117494Struckman 10286333Sdillon/* 103117494Struckman * Return the (shared) pool mutex associated with the specified address. 104117494Struckman * The returned mutex is a leaf level mutex, meaning that if you obtain it 105117494Struckman * you cannot obtain any other mutexes until you release it. You can 106117494Struckman * legally msleep() on the mutex. 10786333Sdillon */ 108117494Struckmanstruct mtx * 109117494Struckmanmtx_pool_find(struct mtx_pool *pool, void *ptr) 11086333Sdillon{ 111117494Struckman int p; 11286476Speter 113117494Struckman KASSERT(pool != NULL, ("_mtx_pool_find(): null pool")); 114117494Struckman /* 115117494Struckman * Fibonacci hash, see Knuth's 116117494Struckman * _Art of Computer Programming, Volume 3 / Sorting and Searching_ 117117494Struckman */ 118117494Struckman p = ((HASH_MULTIPLIER * (uintptr_t)ptr) >> pool->mtx_pool_shift) & 119117494Struckman pool->mtx_pool_mask; 120117494Struckman return (&pool->mtx_pool_ary[p]); 12186333Sdillon} 12286333Sdillon 12386333Sdillonstatic void 124117494Struckmanmtx_pool_initialize(struct mtx_pool *pool, const char *mtx_name, int pool_size, 125117494Struckman int opts) 12686333Sdillon{ 127117494Struckman int i, maskbits; 12886333Sdillon 129117494Struckman pool->mtx_pool_size = pool_size; 130117494Struckman pool->mtx_pool_mask = pool_size - 1; 131117494Struckman for (i = 1, maskbits = 0; (i & pool_size) == 0; i = i << 1) 132117494Struckman maskbits++; 133117494Struckman pool->mtx_pool_shift = POINTER_BITS - maskbits; 134117494Struckman pool->mtx_pool_next = 0; 135117494Struckman for (i = 0; i < pool_size; ++i) 136117494Struckman mtx_init(&pool->mtx_pool_ary[i], mtx_name, NULL, opts); 13786333Sdillon} 13886333Sdillon 139117494Struckmanstruct mtx_pool * 140117494Struckmanmtx_pool_create(const char *mtx_name, int pool_size, int opts) 14186333Sdillon{ 142117494Struckman struct mtx_pool *pool; 143116305Smux 144117494Struckman if (pool_size <= 0 || !powerof2(pool_size)) { 145117494Struckman printf("WARNING: %s pool size is not a power of 2.\n", 146117494Struckman mtx_name); 147117494Struckman pool_size = 128; 148117494Struckman } 149184214Sdes pool = malloc(sizeof (struct mtx_pool) + 150184214Sdes ((pool_size - 1) * sizeof (struct mtx)), 151117494Struckman M_MTXPOOL, M_WAITOK | M_ZERO); 152117494Struckman mtx_pool_initialize(pool, mtx_name, pool_size, opts); 153117494Struckman return pool; 15486333Sdillon} 15586333Sdillon 156117494Struckmanvoid 157117494Struckmanmtx_pool_destroy(struct mtx_pool **poolp) 15886333Sdillon{ 159117494Struckman int i; 160117494Struckman struct mtx_pool *pool = *poolp; 161116305Smux 162117494Struckman for (i = pool->mtx_pool_size - 1; i >= 0; --i) 163117494Struckman mtx_destroy(&pool->mtx_pool_ary[i]); 164184205Sdes free(pool, M_MTXPOOL); 165117494Struckman *poolp = NULL; 16686333Sdillon} 16786333Sdillon 168117494Struckmanstatic void 169117494Struckmanmtx_pool_setup_static(void *dummy __unused) 17086333Sdillon{ 171117494Struckman mtx_pool_initialize((struct mtx_pool *)&lockbuilder_pool, 172117494Struckman "lockbuilder mtxpool", MTX_POOL_LOCKBUILDER_SIZE, 173117494Struckman MTX_DEF | MTX_NOWITNESS | MTX_QUIET); 174117494Struckman mtxpool_lockbuilder = (struct mtx_pool *)&lockbuilder_pool; 175117494Struckman} 176116305Smux 177117494Struckmanstatic void 178117494Struckmanmtx_pool_setup_dynamic(void *dummy __unused) 179117494Struckman{ 180117494Struckman mtxpool_sleep = mtx_pool_create("sleep mtxpool", 181117494Struckman MTX_POOL_SLEEP_SIZE, MTX_DEF); 18286333Sdillon} 18386333Sdillon 18486333Sdillon/* 185117494Struckman * Obtain a (shared) mutex from the pool. The returned mutex is a leaf 186117494Struckman * level mutex, meaning that if you obtain it you cannot obtain any other 187117494Struckman * mutexes until you release it. You can legally msleep() on the mutex. 18886333Sdillon */ 189117494Struckmanstruct mtx * 190117494Struckmanmtx_pool_alloc(struct mtx_pool *pool) 19186333Sdillon{ 192117494Struckman int i; 193116305Smux 194117494Struckman KASSERT(pool != NULL, ("mtx_pool_alloc(): null pool")); 195117494Struckman /* 196117494Struckman * mtx_pool_next is unprotected against multiple accesses, 197117494Struckman * but simultaneous access by two CPUs should not be very 198117494Struckman * harmful. 199117494Struckman */ 200117494Struckman i = pool->mtx_pool_next; 201117494Struckman pool->mtx_pool_next = (i + 1) & pool->mtx_pool_mask; 202117494Struckman return (&pool->mtx_pool_ary[i]); 20386333Sdillon} 20486333Sdillon 205117494Struckman/* 206117494Struckman * The lockbuilder pool must be initialized early because the lockmgr 207117494Struckman * and sx locks depend on it. The sx locks are used in the kernel 208117494Struckman * memory allocator. The lockmgr subsystem is initialized by 209117660Struckman * SYSINIT(..., SI_SUB_LOCKMGR, ...). 210117494Struckman * 211184205Sdes * We can't call malloc() to dynamically allocate the sleep pool 212117494Struckman * until after kmeminit() has been called, which is done by 213117494Struckman * SYSINIT(..., SI_SUB_KMEM, ...). 214117494Struckman */ 215117494StruckmanSYSINIT(mtxpooli1, SI_SUB_MTX_POOL_STATIC, SI_ORDER_FIRST, 216117494Struckman mtx_pool_setup_static, NULL); 217117494StruckmanSYSINIT(mtxpooli2, SI_SUB_MTX_POOL_DYNAMIC, SI_ORDER_FIRST, 218117494Struckman mtx_pool_setup_dynamic, NULL); 219