kern_mtxpool.c revision 117494
1238106Sdes/*- 2238106Sdes * Copyright (c) 2001 Matthew Dillon. All Rights Reserved. Copyright 3238106Sdes * terms are as specified in the COPYRIGHT file at the base of the source 4238106Sdes * tree. 5238106Sdes * 6238106Sdes * Mutex pool routines. These routines are designed to be used as short 7238106Sdes * term leaf mutexes (e.g. the last mutex you might aquire other then 8238106Sdes * calling msleep()). They operate using a shared pool. A mutex is chosen 9238106Sdes * from the pool based on the supplied pointer (which may or may not be 10238106Sdes * valid). 11238106Sdes * 12238106Sdes * Advantages: 13238106Sdes * - no structural overhead. Mutexes can be associated with structures 14238106Sdes * without adding bloat to the structures. 15238106Sdes * - mutexes can be obtained for invalid pointers, useful when uses 16238106Sdes * mutexes to interlock destructor ops. 17238106Sdes * - no initialization/destructor overhead. 18238106Sdes * - can be used with msleep. 19238106Sdes * 20238106Sdes * Disadvantages: 21238106Sdes * - should generally only be used as leaf mutexes. 22238106Sdes * - pool/pool dependancy ordering cannot be depended on. 23238106Sdes * - possible L1 cache mastersip contention between cpus. 24269257Sdes */ 25269257Sdes 26269257Sdes#include <sys/cdefs.h> 27269257Sdes__FBSDID("$FreeBSD: head/sys/kern/kern_mtxpool.c 117494 2003-07-13 01:22:21Z truckman $"); 28269257Sdes 29269257Sdes#include <sys/param.h> 30269257Sdes#include <sys/proc.h> 31269257Sdes#include <sys/kernel.h> 32269257Sdes#include <sys/ktr.h> 33269257Sdes#include <sys/lock.h> 34238106Sdes#include <sys/malloc.h> 35238106Sdes#include <sys/mutex.h> 36238106Sdes#include <sys/systm.h> 37238106Sdes 38238106Sdes 39238106SdesMALLOC_DEFINE(M_MTXPOOL, "mtx_pool", "mutex pool"); 40238106Sdes 41238106Sdes/* Pool sizes must be a power of two */ 42238106Sdes#ifndef MTX_POOL_LOCKBUILDER_SIZE 43238106Sdes#define MTX_POOL_LOCKBUILDER_SIZE 128 44238106Sdes#endif 45238106Sdes#ifndef MTX_POOL_SLEEP_SIZE 46238106Sdes#define MTX_POOL_SLEEP_SIZE 128 47238106Sdes#endif 48238106Sdes 49238106Sdesstruct mtxpool_header { 50238106Sdes int mtxpool_size; 51238106Sdes int mtxpool_mask; 52238106Sdes int mtxpool_shift; 53238106Sdes int mtxpool_next; 54238106Sdes}; 55238106Sdes 56238106Sdesstruct mtx_pool { 57238106Sdes struct mtxpool_header mtx_pool_header; 58269257Sdes struct mtx mtx_pool_ary[1]; 59238106Sdes}; 60238106Sdes 61238106Sdesstatic struct mtx_pool_lockbuilder { 62238106Sdes struct mtxpool_header mtx_pool_header; 63238106Sdes struct mtx mtx_pool_ary[MTX_POOL_LOCKBUILDER_SIZE]; 64238106Sdes} lockbuilder_pool; 65238106Sdes 66238106Sdes#define mtx_pool_size mtx_pool_header.mtxpool_size 67238106Sdes#define mtx_pool_mask mtx_pool_header.mtxpool_mask 68238106Sdes#define mtx_pool_shift mtx_pool_header.mtxpool_shift 69238106Sdes#define mtx_pool_next mtx_pool_header.mtxpool_next 70238106Sdes 71238106Sdesstruct mtx_pool *mtxpool_sleep; 72238106Sdesstruct mtx_pool *mtxpool_lockbuilder; 73238106Sdes 74238106Sdes#if UINTPTR_MAX == UINT64_MAX /* 64 bits */ 75238106Sdes# define POINTER_BITS 64 76238106Sdes# define HASH_MULTIPLIER 11400714819323198485u /* (2^64)*(sqrt(5)-1)/2 */ 77238106Sdes#else /* assume 32 bits */ 78238106Sdes# define POINTER_BITS 32 79238106Sdes# define HASH_MULTIPLIER 2654435769u /* (2^32)*(sqrt(5)-1)/2 */ 80238106Sdes#endif 81238106Sdes 82238106Sdes/* 83238106Sdes * Return the (shared) pool mutex associated with the specified address. 84238106Sdes * The returned mutex is a leaf level mutex, meaning that if you obtain it 85238106Sdes * you cannot obtain any other mutexes until you release it. You can 86238106Sdes * legally msleep() on the mutex. 87238106Sdes */ 88238106Sdesstruct mtx * 89238106Sdesmtx_pool_find(struct mtx_pool *pool, void *ptr) 90238106Sdes{ 91238106Sdes int p; 92238106Sdes 93238106Sdes KASSERT(pool != NULL, ("_mtx_pool_find(): null pool")); 94238106Sdes /* 95238106Sdes * Fibonacci hash, see Knuth's 96238106Sdes * _Art of Computer Programming, Volume 3 / Sorting and Searching_ 97238106Sdes */ 98238106Sdes p = ((HASH_MULTIPLIER * (uintptr_t)ptr) >> pool->mtx_pool_shift) & 99238106Sdes pool->mtx_pool_mask; 100238106Sdes return (&pool->mtx_pool_ary[p]); 101238106Sdes} 102238106Sdes 103238106Sdesstatic void 104238106Sdesmtx_pool_initialize(struct mtx_pool *pool, const char *mtx_name, int pool_size, 105238106Sdes int opts) 106238106Sdes{ 107238106Sdes int i, maskbits; 108238106Sdes 109238106Sdes pool->mtx_pool_size = pool_size; 110238106Sdes pool->mtx_pool_mask = pool_size - 1; 111238106Sdes for (i = 1, maskbits = 0; (i & pool_size) == 0; i = i << 1) 112238106Sdes maskbits++; 113238106Sdes pool->mtx_pool_shift = POINTER_BITS - maskbits; 114238106Sdes pool->mtx_pool_next = 0; 115238106Sdes for (i = 0; i < pool_size; ++i) 116238106Sdes mtx_init(&pool->mtx_pool_ary[i], mtx_name, NULL, opts); 117238106Sdes} 118238106Sdes 119238106Sdesstruct mtx_pool * 120238106Sdesmtx_pool_create(const char *mtx_name, int pool_size, int opts) 121238106Sdes{ 122238106Sdes struct mtx_pool *pool; 123238106Sdes 124238106Sdes if (pool_size <= 0 || !powerof2(pool_size)) { 125238106Sdes printf("WARNING: %s pool size is not a power of 2.\n", 126238106Sdes mtx_name); 127238106Sdes pool_size = 128; 128238106Sdes } 129238106Sdes MALLOC(pool, struct mtx_pool *, 130238106Sdes sizeof (struct mtx_pool) + ((pool_size - 1) * sizeof (struct mtx)), 131238106Sdes M_MTXPOOL, M_WAITOK | M_ZERO); 132238106Sdes mtx_pool_initialize(pool, mtx_name, pool_size, opts); 133238106Sdes return pool; 134238106Sdes} 135238106Sdes 136238106Sdesvoid 137238106Sdesmtx_pool_destroy(struct mtx_pool **poolp) 138238106Sdes{ 139238106Sdes int i; 140238106Sdes struct mtx_pool *pool = *poolp; 141238106Sdes 142238106Sdes for (i = pool->mtx_pool_size - 1; i >= 0; --i) 143238106Sdes mtx_destroy(&pool->mtx_pool_ary[i]); 144238106Sdes FREE(pool, M_MTXPOOL); 145238106Sdes *poolp = NULL; 146238106Sdes} 147238106Sdes 148238106Sdesstatic void 149238106Sdesmtx_pool_setup_static(void *dummy __unused) 150238106Sdes{ 151238106Sdes mtx_pool_initialize((struct mtx_pool *)&lockbuilder_pool, 152238106Sdes "lockbuilder mtxpool", MTX_POOL_LOCKBUILDER_SIZE, 153238106Sdes MTX_DEF | MTX_NOWITNESS | MTX_QUIET); 154238106Sdes mtxpool_lockbuilder = (struct mtx_pool *)&lockbuilder_pool; 155238106Sdes} 156238106Sdes 157238106Sdesstatic void 158238106Sdesmtx_pool_setup_dynamic(void *dummy __unused) 159238106Sdes{ 160238106Sdes mtxpool_sleep = mtx_pool_create("sleep mtxpool", 161238106Sdes MTX_POOL_SLEEP_SIZE, MTX_DEF); 162238106Sdes} 163238106Sdes 164238106Sdes/* 165269257Sdes * Obtain a (shared) mutex from the pool. The returned mutex is a leaf 166238106Sdes * level mutex, meaning that if you obtain it you cannot obtain any other 167238106Sdes * mutexes until you release it. You can legally msleep() on the mutex. 168238106Sdes */ 169238106Sdesstruct mtx * 170238106Sdesmtx_pool_alloc(struct mtx_pool *pool) 171238106Sdes{ 172238106Sdes int i; 173238106Sdes 174238106Sdes KASSERT(pool != NULL, ("mtx_pool_alloc(): null pool")); 175238106Sdes /* 176238106Sdes * mtx_pool_next is unprotected against multiple accesses, 177238106Sdes * but simultaneous access by two CPUs should not be very 178238106Sdes * harmful. 179238106Sdes */ 180238106Sdes i = pool->mtx_pool_next; 181238106Sdes pool->mtx_pool_next = (i + 1) & pool->mtx_pool_mask; 182238106Sdes return (&pool->mtx_pool_ary[i]); 183238106Sdes} 184238106Sdes 185238106Sdes/* 186238106Sdes * The lockbuilder pool must be initialized early because the lockmgr 187238106Sdes * and sx locks depend on it. The sx locks are used in the kernel 188238106Sdes * memory allocator. The lockmgr subsystem is initialized by 189238106Sdes * SYSINIT(..., SI_SUB_LOCK, ...). 190238106Sdes * 191238106Sdes * We can't call MALLOC() to dynamically allocate the sleep pool 192238106Sdes * until after kmeminit() has been called, which is done by 193238106Sdes * SYSINIT(..., SI_SUB_KMEM, ...). 194238106Sdes */ 195238106SdesSYSINIT(mtxpooli1, SI_SUB_MTX_POOL_STATIC, SI_ORDER_FIRST, 196238106Sdes mtx_pool_setup_static, NULL); 197238106SdesSYSINIT(mtxpooli2, SI_SUB_MTX_POOL_DYNAMIC, SI_ORDER_FIRST, 198238106Sdes mtx_pool_setup_dynamic, NULL); 199238106Sdes