Extend the mutex pool implementation to permit the creation and use of

multiple mutex pools with different options and sizes.  Mutex pools can
be created with either the default sleep mutexes or with spin mutexes.
A dynamically created mutex pool can now be destroyed if it is no longer
needed.

Create two pools by default, one that matches the existing pool that
uses the MTX_NOWITNESS option that should be used for building higher
level locks, and a new pool with witness checking enabled.

Modify the users of the existing mutex pool to use the appropriate pool
in the new implementation.

Reviewed by:	jhb

1 files changed, 133 insertions, 54 deletions

diff --git a/sys/kern/kern_mtxpool.c b/sys/kern/kern_mtxpool.c
index b93fcfa..93ce655 100644
--- a/sys/kern/kern_mtxpool.c
+++ b/sys/kern/kern_mtxpool.c
@@ -35,85 +35,164 @@ __FBSDID("$FreeBSD$");
 #include <sys/mutex.h>
 #include <sys/systm.h>
 
-#ifndef MTX_POOL_SIZE
-#define MTX_POOL_SIZE	128
-#endif
-#define MTX_POOL_MASK	(MTX_POOL_SIZE - 1)
 
-static struct mtx mtx_pool_ary[MTX_POOL_SIZE];
+MALLOC_DEFINE(M_MTXPOOL, "mtx_pool", "mutex pool");
+
+/* Pool sizes must be a power of two */
+#ifndef MTX_POOL_LOCKBUILDER_SIZE
+#define MTX_POOL_LOCKBUILDER_SIZE	128
+#endif
+#ifndef MTX_POOL_SLEEP_SIZE
+#define MTX_POOL_SLEEP_SIZE		128
+#endif
 
-int mtx_pool_valid = 0;
+struct mtxpool_header {
+	int		mtxpool_size;
+	int		mtxpool_mask;
+	int		mtxpool_shift;
+	int		mtxpool_next;
+};
+
+struct mtx_pool {
+	struct mtxpool_header mtx_pool_header;
+	struct mtx	mtx_pool_ary[1];
+};
+
+static struct mtx_pool_lockbuilder {
+	struct mtxpool_header mtx_pool_header;
+	struct mtx	mtx_pool_ary[MTX_POOL_LOCKBUILDER_SIZE];
+} lockbuilder_pool;
+
+#define mtx_pool_size	mtx_pool_header.mtxpool_size
+#define mtx_pool_mask	mtx_pool_header.mtxpool_mask
+#define mtx_pool_shift	mtx_pool_header.mtxpool_shift
+#define mtx_pool_next	mtx_pool_header.mtxpool_next
+
+struct mtx_pool *mtxpool_sleep;
+struct mtx_pool *mtxpool_lockbuilder;
+
+#if UINTPTR_MAX == UINT64_MAX	/* 64 bits */
+# define POINTER_BITS		64
+# define HASH_MULTIPLIER	11400714819323198485u /* (2^64)*(sqrt(5)-1)/2 */
+#else				/* assume 32 bits */
+# define POINTER_BITS		32
+# define HASH_MULTIPLIER	2654435769u	      /* (2^32)*(sqrt(5)-1)/2 */
+#endif
 
 /*
- * Inline version of mtx_pool_find(), used to streamline our main API
- * function calls.
+ * Return the (shared) pool mutex associated with the specified address.
+ * The returned mutex is a leaf level mutex, meaning that if you obtain it
+ * you cannot obtain any other mutexes until you release it.  You can
+ * legally msleep() on the mutex.
  */
-static __inline struct mtx *
-_mtx_pool_find(void *ptr)
+struct mtx *
+mtx_pool_find(struct mtx_pool *pool, void *ptr)
 {
-    int p;
-
-    p = (int)(uintptr_t)ptr;
-    return (&mtx_pool_ary[(p ^ (p >> 6)) & MTX_POOL_MASK]);
+	int p;
+
+	KASSERT(pool != NULL, ("_mtx_pool_find(): null pool"));
+	/*
+	 * Fibonacci hash, see Knuth's
+	 * _Art of Computer Programming, Volume 3 / Sorting and Searching_
+	 */
+	p = ((HASH_MULTIPLIER * (uintptr_t)ptr) >> pool->mtx_pool_shift) &
+	    pool->mtx_pool_mask;
+	return (&pool->mtx_pool_ary[p]);
 }
 
 static void
-mtx_pool_setup(void *dummy __unused)
+mtx_pool_initialize(struct mtx_pool *pool, const char *mtx_name, int pool_size,
+    int opts)
 {
-    int i;
-
-    for (i = 0; i < MTX_POOL_SIZE; ++i)
-	mtx_init(&mtx_pool_ary[i], "pool mutex", NULL,
-	    MTX_DEF | MTX_NOWITNESS | MTX_QUIET);
-    mtx_pool_valid = 1;
+	int i, maskbits;
+
+	pool->mtx_pool_size = pool_size;
+	pool->mtx_pool_mask = pool_size - 1;
+	for (i = 1, maskbits = 0; (i & pool_size) == 0; i = i << 1)
+		maskbits++;
+	pool->mtx_pool_shift = POINTER_BITS - maskbits;
+	pool->mtx_pool_next = 0;
+	for (i = 0; i < pool_size; ++i)
+		mtx_init(&pool->mtx_pool_ary[i], mtx_name, NULL, opts);
 }
 
-/*
- * Obtain a (shared) mutex from the pool.  The returned mutex is a leaf
- * level mutex, meaning that if you obtain it you cannot obtain any other
- * mutexes until you release it.  You can legally msleep() on the mutex.
- */
-struct mtx *
-mtx_pool_alloc(void)
+struct mtx_pool *
+mtx_pool_create(const char *mtx_name, int pool_size, int opts)
 {
-    static int si;
-
-    return (&mtx_pool_ary[si++ & MTX_POOL_MASK]);
+	struct mtx_pool *pool;
+
+	if (pool_size <= 0 || !powerof2(pool_size)) {
+		printf("WARNING: %s pool size is not a power of 2.\n",
+		    mtx_name);
+		pool_size = 128;
+	}
+	MALLOC(pool, struct mtx_pool *,
+	    sizeof (struct mtx_pool) + ((pool_size - 1) * sizeof (struct mtx)),
+	    M_MTXPOOL, M_WAITOK | M_ZERO);
+	mtx_pool_initialize(pool, mtx_name, pool_size, opts);
+	return pool;
 }
 
-/*
- * Return the (shared) pool mutex associated with the specified address.
- * The returned mutex is a leaf level mutex, meaning that if you obtain it
- * you cannot obtain any other mutexes until you release it.  You can
- * legally msleep() on the mutex.
- */
-struct mtx *
-mtx_pool_find(void *ptr)
+void
+mtx_pool_destroy(struct mtx_pool **poolp)
 {
+	int i;
+	struct mtx_pool *pool = *poolp;
 
-    return (_mtx_pool_find(ptr));
+	for (i = pool->mtx_pool_size - 1; i >= 0; --i)
+		mtx_destroy(&pool->mtx_pool_ary[i]);
+	FREE(pool, M_MTXPOOL);
+	*poolp = NULL;
 }
 
-/*
- * Combined find/lock operation.  Lock the pool mutex associated with
- * the specified address.
- */
-void
-mtx_pool_lock(void *ptr)
+static void
+mtx_pool_setup_static(void *dummy __unused)
 {
+	mtx_pool_initialize((struct mtx_pool *)&lockbuilder_pool,
+	    "lockbuilder mtxpool", MTX_POOL_LOCKBUILDER_SIZE,
+	    MTX_DEF | MTX_NOWITNESS | MTX_QUIET);
+	mtxpool_lockbuilder = (struct mtx_pool *)&lockbuilder_pool;
+}
 
-    mtx_lock(_mtx_pool_find(ptr));
+static void
+mtx_pool_setup_dynamic(void *dummy __unused)
+{
+	mtxpool_sleep = mtx_pool_create("sleep mtxpool",
+	    MTX_POOL_SLEEP_SIZE, MTX_DEF);
 }
 
 /*
- * Combined find/unlock operation.  Unlock the pool mutex associated with
- * the specified address.
+ * Obtain a (shared) mutex from the pool.  The returned mutex is a leaf
+ * level mutex, meaning that if you obtain it you cannot obtain any other
+ * mutexes until you release it.  You can legally msleep() on the mutex.
  */
-void
-mtx_pool_unlock(void *ptr)
+struct mtx *
+mtx_pool_alloc(struct mtx_pool *pool)
 {
-
-    mtx_unlock(_mtx_pool_find(ptr));
+	int i;
+
+	KASSERT(pool != NULL, ("mtx_pool_alloc(): null pool"));
+	/*
+	 * mtx_pool_next is unprotected against multiple accesses,
+	 * but simultaneous access by two CPUs should not be very
+	 * harmful.
+	 */
+	i = pool->mtx_pool_next;
+	pool->mtx_pool_next = (i + 1) & pool->mtx_pool_mask;
+	return (&pool->mtx_pool_ary[i]);
 }
 
-SYSINIT(mtxpooli, SI_SUB_MTX_POOL, SI_ORDER_FIRST, mtx_pool_setup, NULL);
+/*
+ * The lockbuilder pool must be initialized early because the lockmgr
+ * and sx locks depend on it.  The sx locks are used in the kernel
+ * memory allocator.  The lockmgr subsystem is initialized by
+ * SYSINIT(..., SI_SUB_LOCK, ...).
+ *
+ * We can't call MALLOC() to dynamically allocate the sleep pool
+ * until after kmeminit() has been called, which is done by
+ * SYSINIT(..., SI_SUB_KMEM, ...).
+ */
+SYSINIT(mtxpooli1, SI_SUB_MTX_POOL_STATIC, SI_ORDER_FIRST,
+    mtx_pool_setup_static, NULL);
+SYSINIT(mtxpooli2, SI_SUB_MTX_POOL_DYNAMIC, SI_ORDER_FIRST,
+    mtx_pool_setup_dynamic, NULL);