From 33b0b87c7f75846a43b41baa24ae0d170d110724 Mon Sep 17 00:00:00 2001 From: Matthew Dillon Date: Wed, 15 Jul 2009 11:29:43 -0700 Subject: [PATCH] MPSAFE - Add a set of general blocking/spinnable mutex functions. These locks are intended to eventually replace lockmgr locks for most use cases. * Optimized based on in-line atomic_cmpset_int() calls with fallback call. * Recursive shared and exclusive locks. Downgrading, and non-blocking upgrading. * Interlocked wakeup flags. * Serial wakeup for exclusive waiters (i.e. optimal in the face of a large number of waiting threads). Mass-wakeup for shared waiters. * Additional entry points for spinning. * Ref-count support, separate from lock count. --- sys/conf/files | 1 + sys/kern/kern_mutex.c | 356 ++++++++++++++++++++++++++++++++++++++++++ sys/sys/mutex.h | 97 ++++++++++++ sys/sys/mutex2.h | 227 +++++++++++++++++++++++++++ 4 files changed, 681 insertions(+) create mode 100644 sys/kern/kern_mutex.c create mode 100644 sys/sys/mutex.h create mode 100644 sys/sys/mutex2.h diff --git a/sys/conf/files b/sys/conf/files index 459cd516d0..345c452fc6 100644 --- a/sys/conf/files +++ b/sys/conf/files @@ -677,6 +677,7 @@ kern/kern_usched.c standard kern/usched_bsd4.c standard kern/usched_dummy.c standard kern/kern_umtx.c standard +kern/kern_mutex.c standard kern/lwkt_thread.c standard kern/lwkt_ipiq.c standard kern/lwkt_token.c standard diff --git a/sys/kern/kern_mutex.c b/sys/kern/kern_mutex.c new file mode 100644 index 0000000000..96a4f04a9c --- /dev/null +++ b/sys/kern/kern_mutex.c @@ -0,0 +1,356 @@ +/* + * Copyright (c) 2009 The DragonFly Project. All rights reserved. + * + * This code is derived from software contributed to The DragonFly Project + * by Matthew Dillon + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name of The DragonFly Project nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific, prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ +/* + * Implement fast persistent locks based on atomic_cmpset_int() with + * semantics similar to lockmgr locks but faster and taking up much less + * space. Taken from HAMMER's lock implementation. + * + * These are meant to complement our LWKT tokens. Tokens are only held + * while the thread is running. Mutexes can be held across blocking + * conditions. + * + * Most of the support is in sys/mutex[2].h. We mostly provide backoff + * functions here. + */ + +#include +#include +#include +#include +#include +#include + +#include + +#include +#include + +static __int64_t mtx_contention_count; +static __int64_t mtx_collision_count; +static __int64_t mtx_wakeup_count; + +SYSCTL_QUAD(_kern, OID_AUTO, mtx_contention_count, CTLFLAG_RW, + &mtx_contention_count, 0, ""); +SYSCTL_QUAD(_kern, OID_AUTO, mtx_collision_count, CTLFLAG_RW, + &mtx_collision_count, 0, ""); +SYSCTL_QUAD(_kern, OID_AUTO, mtx_wakeup_count, CTLFLAG_RW, + &mtx_wakeup_count, 0, ""); + +/* + * Exclusive-lock a mutex, block until acquired. Recursion is allowed. + */ +void +_mtx_lock_ex(mtx_t mtx, const char *ident, int flags) +{ + u_int lock; + u_int nlock; + + for (;;) { + lock = mtx->mtx_lock; + if (lock == 0) { + nlock = MTX_EXCLUSIVE | 1; + if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) { + /* mtx_owner set by caller */ + return; + } + } else if ((lock & MTX_EXCLUSIVE) && + mtx->mtx_owner == curthread) { + KKASSERT((lock & MTX_MASK) != MTX_MASK); + nlock = (lock + 1); + if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) + return; + } else { + nlock = lock | MTX_EXWANTED; + tsleep_interlock(mtx, 0); + if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) { + ++mtx_contention_count; + tsleep(mtx, flags, ident, 0); + } + } + ++mtx_collision_count; + } +} + +/* + * Share-lock a mutex, block until acquired. Recursion is allowed. + */ +void +_mtx_lock_sh(mtx_t mtx, const char *ident, int flags) +{ + u_int lock; + u_int nlock; + + for (;;) { + lock = mtx->mtx_lock; + if ((lock & MTX_EXCLUSIVE) == 0) { + KKASSERT((lock & MTX_MASK) != MTX_MASK); + nlock = lock + 1; + if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) + return; + } else { + nlock = lock | MTX_SHWANTED; + tsleep_interlock(mtx, 0); + if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) { + ++mtx_contention_count; + tsleep(mtx, flags, ident, 0); + } + } + ++mtx_collision_count; + } +} + +void +_mtx_spinlock_ex(mtx_t mtx) +{ + u_int lock; + u_int nlock; + int bb = 1; + int bo; + + for (;;) { + lock = mtx->mtx_lock; + if (lock == 0) { + nlock = MTX_EXCLUSIVE | 1; + if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) { + /* mtx_owner set by caller */ + return; + } + } else if ((lock & MTX_EXCLUSIVE) && + mtx->mtx_owner == curthread) { + KKASSERT((lock & MTX_MASK) != MTX_MASK); + nlock = (lock + 1); + if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) + return; + } else { + /* MWAIT here */ + if (bb < 1000) + ++bb; + cpu_pause(); + for (bo = 0; bo < bb; ++bo) + ; + ++mtx_contention_count; + } + ++mtx_collision_count; + } +} + +void +_mtx_spinlock_sh(mtx_t mtx) +{ + u_int lock; + u_int nlock; + int bb = 1; + int bo; + + for (;;) { + lock = mtx->mtx_lock; + if ((lock & MTX_EXCLUSIVE) == 0) { + KKASSERT((lock & MTX_MASK) != MTX_MASK); + nlock = lock + 1; + if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) + return; + } else { + /* MWAIT here */ + if (bb < 1000) + ++bb; + cpu_pause(); + for (bo = 0; bo < bb; ++bo) + ; + ++mtx_contention_count; + } + ++mtx_collision_count; + } +} + +int +_mtx_lock_ex_try(mtx_t mtx) +{ + u_int lock; + u_int nlock; + int error = 0; + + for (;;) { + lock = mtx->mtx_lock; + if (lock == 0) { + nlock = MTX_EXCLUSIVE | 1; + if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) { + /* mtx_owner set by caller */ + break; + } + } else if ((lock & MTX_EXCLUSIVE) && + mtx->mtx_owner == curthread) { + KKASSERT((lock & MTX_MASK) != MTX_MASK); + nlock = (lock + 1); + if (atomic_cmpset_int(&mtx->mtx_lock, 0, nlock)) + break; + } else { + error = EAGAIN; + break; + } + ++mtx_collision_count; + } + return (error); +} + +int +_mtx_lock_sh_try(mtx_t mtx) +{ + u_int lock; + u_int nlock; + int error = 0; + + for (;;) { + lock = mtx->mtx_lock; + if ((lock & MTX_EXCLUSIVE) == 0) { + KKASSERT((lock & MTX_MASK) != MTX_MASK); + nlock = lock + 1; + if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) + break; + } else { + error = EAGAIN; + break; + } + ++mtx_collision_count; + } + return (error); +} + +/* + * If the lock is held exclusively it must be owned by the caller. If the + * lock is already a shared lock this operation is a NOP. A panic will + * occur if the lock is not held either shared or exclusive. + * + * The exclusive count is converted to a shared count. + */ +void +_mtx_downgrade(mtx_t mtx) +{ + u_int lock; + u_int nlock; + + for (;;) { + lock = mtx->mtx_lock; + if ((lock & MTX_EXCLUSIVE) == 0) { + KKASSERT((lock & MTX_MASK) > 0); + break; + } + KKASSERT(mtx->mtx_owner == curthread); + nlock = lock & ~(MTX_EXCLUSIVE | MTX_SHWANTED); + if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) { + if (lock & MTX_SHWANTED) { + ++mtx_wakeup_count; + wakeup(mtx); + } + break; + } + ++mtx_collision_count; + } +} + +/* + * Upgrade a shared lock to an exclusive lock. The upgrade will fail if + * the shared lock has a count other then 1. Optimize the most likely case + * but note that a single cmpset can fail due to WANTED races. + * + * If the lock is held exclusively it must be owned by the caller and + * this function will simply return without doing anything. A panic will + * occur if the lock is held exclusively by someone other then the caller. + * + * Returns 0 on success, EDEADLK on failure. + */ +int +_mtx_upgrade_try(mtx_t mtx) +{ + u_int lock; + u_int nlock; + int error = 0; + + for (;;) { + lock = mtx->mtx_lock; + + if ((lock & ~MTX_EXWANTED) == 1) { + nlock = lock | MTX_EXCLUSIVE; + if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) { + mtx->mtx_owner = curthread; + break; + } + } else if (lock & MTX_EXCLUSIVE) { + KKASSERT(mtx->mtx_owner == curthread); + break; + } else { + error = EDEADLK; + break; + } + ++mtx_collision_count; + } + return (error); +} + +/* + * Unlock a lock. The caller must hold the lock either shared or exclusive. + */ +void +_mtx_unlock(mtx_t mtx) +{ + u_int lock; + u_int nlock; + + for (;;) { + lock = mtx->mtx_lock; + nlock = (lock & (MTX_EXCLUSIVE | MTX_MASK)) - 1; + if (nlock == 0) { + if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0)) { + if (lock & (MTX_SHWANTED | MTX_EXWANTED)) { + ++mtx_wakeup_count; + wakeup(mtx); + } + } + } else if (nlock == MTX_EXCLUSIVE) { + mtx->mtx_owner = NULL; + if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0)) { + if (lock & (MTX_SHWANTED | MTX_EXWANTED)) { + ++mtx_wakeup_count; + wakeup(mtx); + } + break; + } + } else { + nlock = lock - 1; + KKASSERT((nlock & MTX_MASK) != MTX_MASK); + if (atomic_cmpset_int(&mtx->mtx_lock, lock, nlock)) + break; + } + ++mtx_collision_count; + } +} diff --git a/sys/sys/mutex.h b/sys/sys/mutex.h new file mode 100644 index 0000000000..82a43c914b --- /dev/null +++ b/sys/sys/mutex.h @@ -0,0 +1,97 @@ +/* + * Copyright (c) 2009 The DragonFly Project. All rights reserved. + * + * This code is derived from software contributed to The DragonFly Project + * by Matthew Dillon + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name of The DragonFly Project nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific, prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef _SYS_MUTEX_H_ +#define _SYS_MUTEX_H_ + +#if defined(_KERNEL) || defined(_KERNEL_STRUCTURES) + +#ifndef _SYS_TYPES_H_ +#include +#endif +#ifndef _MACHINE_ATOMIC_H_ +#include +#endif +#ifndef _MACHINE_CPUFUNC_H_ +#include +#endif + +/* + * The general mutex structure provides recursive shared and exclusive + * locks, downgrade, a non-blocking upgrade, and various other functions. + * + * The structure is 16-byte aligned and either 16 or 32 bytes, designed + * for 32 or 64 bit cpus. + */ +struct thread; + +typedef struct mtx { + volatile u_int mtx_lock; + int mtx_refs; + struct thread *mtx_owner; +#if LONG_BIT == 32 + int mtx_unused; +#endif +} *mtx_t; + +#define MTX_EXCLUSIVE 0x80000000 +#define MTX_SHWANTED 0x40000000 +#define MTX_EXWANTED 0x20000000 +#define MTX_MASK 0x0FFFFFFF + +#define MTX_PCATCH 0x00000001 + +#define MTX_OWNER_NONE NULL +#define MTX_OWNER_ANON (struct thread *)-2) + +#endif + +/* + * See also sys/mutex2.h + */ +#ifdef _KERNEL + +void _mtx_lock_ex(mtx_t mtx, const char *ident, int flags); +void _mtx_lock_sh(mtx_t mtx, const char *ident, int flags); +void _mtx_spinlock_ex(mtx_t mtx); +void _mtx_spinlock_sh(mtx_t mtx); +int _mtx_lock_ex_try(mtx_t mtx); +int _mtx_lock_sh_try(mtx_t mtx); +void _mtx_downgrade(mtx_t mtx); +int _mtx_upgrade_try(mtx_t mtx); +void _mtx_unlock(mtx_t mtx); + +#endif + +#endif diff --git a/sys/sys/mutex2.h b/sys/sys/mutex2.h new file mode 100644 index 0000000000..24ee26f383 --- /dev/null +++ b/sys/sys/mutex2.h @@ -0,0 +1,227 @@ +/* + * Copyright (c) 2009 The DragonFly Project. All rights reserved. + * + * This code is derived from software contributed to The DragonFly Project + * by Matthew Dillon + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name of The DragonFly Project nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific, prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT + * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef _SYS_MUTEX2_H_ +#define _SYS_MUTEX2_H_ + +#ifndef _SYS_MUTEX_H_ +#include +#endif +#ifndef _MACHINE_ATOMIC_H_ +#include +#endif + +/* + * Initialize a new mutex, placing it in an unlocked state with no refs. + */ +static __inline void +mtx_init(mtx_t mtx) +{ + mtx->mtx_lock = 0; + mtx->mtx_refs = 0; + mtx->mtx_owner = NULL; +} + +/* + * Deinitialize a mutex + */ +static __inline void +mtx_uninit(mtx_t mtx) +{ + /* empty */ +} + +/* + * Exclusive-lock a mutex, block until acquired. Recursion is allowed. + */ +static __inline void +mtx_lock_ex(mtx_t mtx, const char *ident, int flags) +{ + if (atomic_cmpset_int(&mtx->mtx_lock, 0, MTX_EXCLUSIVE | 1) == 0) + _mtx_lock_ex(mtx, ident, flags); + mtx->mtx_owner = curthread; +} + +/* + * Share-lock a mutex, block until acquired. Recursion is allowed. + */ +static __inline void +mtx_lock_sh(mtx_t mtx, const char *ident, int flags) +{ + if (atomic_cmpset_int(&mtx->mtx_lock, 0, 1) == 0) + _mtx_lock_sh(mtx, ident, flags); +} + +/* + * Exclusive-lock a mutex, spin until acquired. Recursion is allowed. + */ +static __inline void +mtx_spinlock_ex(mtx_t mtx) +{ + if (atomic_cmpset_int(&mtx->mtx_lock, 0, MTX_EXCLUSIVE | 1) == 0) + _mtx_spinlock_ex(mtx); +} + +/* + * Share-lock a mutex, spin until acquired. Recursion is allowed. + */ +static __inline void +mtx_spinlock_sh(mtx_t mtx) +{ + if (atomic_cmpset_int(&mtx->mtx_lock, 0, 1) == 0) + _mtx_spinlock_sh(mtx); +} + +/* + * Attempt to exclusive-lock a mutex, return 0 on success and + * EAGAIN on failure. + */ +static __inline int +mtx_lock_ex_try(mtx_t mtx) +{ + if (atomic_cmpset_int(&mtx->mtx_lock, 0, MTX_EXCLUSIVE | 1) == 0) + return (_mtx_lock_ex_try(mtx)); + mtx->mtx_owner = curthread; + return (0); +} + +/* + * Attempt to share-lock a mutex, return 0 on success and + * EAGAIN on failure. + */ +static __inline int +mtx_lock_sh_try(mtx_t mtx) +{ + if (atomic_cmpset_int(&mtx->mtx_lock, 0, 1) == 0) + return (_mtx_lock_sh_try(mtx)); + return (0); +} + +/* + * If the lock is held exclusively it must be owned by the caller. If the + * lock is already a shared lock this operation is a NOP. A panic will + * occur if the lock is not held either shared or exclusive. + * + * The exclusive count is converted to a shared count. + */ +static __inline void +mtx_downgrade(mtx_t mtx) +{ + mtx->mtx_owner = NULL; + if (atomic_cmpset_int(&mtx->mtx_lock, MTX_EXCLUSIVE | 1, 0) == 0) + _mtx_downgrade(mtx); +} + +/* + * Upgrade a shared lock to an exclusive lock. The upgrade will fail if + * the shared lock has a count other then 1. Optimize the most likely case + * but note that a single cmpset can fail due to WANTED races. + * + * If the lock is held exclusively it must be owned by the caller and + * this function will simply return without doing anything. A panic will + * occur if the lock is held exclusively by someone other then the caller. + * + * Returns 0 on success, EDEADLK on failure. + */ +static __inline int +mtx_upgrade_try(mtx_t mtx) +{ + if (atomic_cmpset_int(&mtx->mtx_lock, 1, MTX_EXCLUSIVE | 1)) + return(0); + return (_mtx_upgrade_try(mtx)); +} + +/* + * Optimized unlock cases. + */ +static __inline void +mtx_unlock(mtx_t mtx) +{ + u_int lock = mtx->mtx_lock; + + if (lock == (MTX_EXCLUSIVE | 1)) { + mtx->mtx_owner = NULL; + if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0) == 0) + _mtx_unlock(mtx); + } else if (lock == 1) { + if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0) == 0) + _mtx_unlock(mtx); + } else { + _mtx_unlock(mtx); + } +} + +static __inline void +mtx_unlock_ex(mtx_t mtx) +{ + u_int lock = mtx->mtx_lock; + + if (lock == (MTX_EXCLUSIVE | 1)) { + mtx->mtx_owner = NULL; + if (atomic_cmpset_int(&mtx->mtx_lock, lock, 0) == 0) + _mtx_unlock(mtx); + } else { + _mtx_unlock(mtx); + } +} + +static __inline void +mtx_unlock_sh(mtx_t mtx) +{ + if (atomic_cmpset_int(&mtx->mtx_lock, 1, 0) == 0) + _mtx_unlock(mtx); +} + +/* + * Bump the lock's ref count. This field is independent of the lock. + */ +static __inline void +mtx_hold(mtx_t mtx) +{ + atomic_add_acq_int(&mtx->mtx_refs, 1); +} + +/* + * Drop the lock's ref count. This field is independent of the lock. + * + * Returns the previous ref count, interlocked so testing against + * 1 means you won the 1->0 transition + */ +static __inline int +mtx_drop(mtx_t mtx) +{ + return (atomic_fetchadd_int(&mtx->mtx_refs, -1)); +} + +#endif -- 2.41.0