mutex subsystem, core
PATCH 5/9 mutex subsystem, core
mutex implementation, core files: just the basic subsystem, no users of it.
----
include/linux/mutex.h | 100 +++++++++ kernel/Makefile | 2 kernel/mutex.c | 518 ++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 619 insertions(+), 1 deletion(-)
include/linux/mutex.h new file +100 -0
@@ -0,0 +1,100 @@ +#ifndef __LINUX_MUTEX_H +#define __LINUX_MUTEX_H + +/* +* Mutexes: blocking mutual exclusion locks +* +* started by Ingo Molnar: +* +* Copyright (C) 2004, 2005 Red Hat, Inc., Ingo Molnar <[email protected]> +* +* This file contains the main data structure and API definitions. +*/ +#include <linux/config.h> +#include <asm/atomic.h> +#include <linux/list.h> +#include <linux/spinlock_types.h> + +/* +* Simple, straightforward mutexes with strict semantics: +* +* - only one task can hold the mutex at a time +* - only the owner can unlock the mutex +* - multiple unlocks are not permitted +* - recursive locking is not permitted +* - a mutex object must be initialized via the API +* - a mutex object must not be initialized via memset or copying +* - task may not exit with mutex held +* - memory areas where held locks reside must not be freed +* - held mutexes must not be reinitialized +* - mutexes may not be used in irq contexts +* +* These semantics are fully enforced when DEBUG_MUTEXES is +* enabled. Furthermore, besides enforcing the above rules, the mutex +* debugging code also implements a number of additional features +* that make lock debugging easier and faster: +* +* - uses symbolic names of mutexes, whenever they are printed in debug output +* - point-of-acquire tracking, symbolic lookup of function names +* - list of all locks held in the system, printout of them +* - owner tracking +* - detects self-recursing locks and prints out all relevant info +* - detects multi-task circular deadlocks and prints out all affected +* locks and tasks (and only those tasks) +*/ +struct mutex { +// 1: unlocked, 0: locked, negative: locked, possible waiters +atomic_t count; +spinlock_t wait_lock; +struct list_head wait_list; +#ifdef CONFIG_DEBUG_MUTEXES +struct thread_info *owner; +struct list_head held_list; +unsigned long acquire_ip; +const char *name; +void *magic; +#endif +}; + +/* +* This is the control structure for tasks blocked on mutex, +* which resides on the blocked task's kernel stack: +*/ +struct mutex_waiter { +struct list_head list; +struct thread_info *ti; +#ifdef CONFIG_DEBUG_MUTEXES +struct mutex *lock; +void *magic; +#endif +}; + +#ifdef CONFIG_DEBUG_MUTEXES +# include <linux/mutex-debug.h> +#else +# define __DEBUG_MUTEX_INITIALIZER (lockname) +# define mutex_init (sem) __mutex_init(sem, NULL) +# define mutex_debug_show_all_locks () do { } while (0) +# define mutex_debug_show_held_locks (p) do { } while (0) +# define mutex_debug_check_no_locks_held (task) do { } while (0) +# define mutex_debug_check_no_locks_freed (from, to) do { } while (0) +#endif + +#define __MUTEX_INITIALIZER (lockname) \ + { .count = ATOMIC_INIT(1) \ + , .wait_lock = SPIN_LOCK_UNLOCKED \ + , .wait_list = LIST_HEAD_INIT(lockname.wait_list) \ + __DEBUG_MUTEX_INITIALIZER(lockname) } + +#define DEFINE_MUTEX (mutexname) \ + struct mutex mutexname = __MUTEX_INITIALIZER(mutexname) + +extern void FASTCALL (__mutex_init (struct mutex *lock,const char *name)); + +extern void FASTCALL (mutex_lock (struct mutex *lock)); +extern int FASTCALL (mutex_lock_interruptible (struct mutex *lock)); +extern int FASTCALL (mutex_trylock (struct mutex *lock)); +extern void FASTCALL (mutex_unlock (struct mutex *lock)); +extern int FASTCALL (mutex_is_locked (struct mutex *lock)); + +#endif
kernel/Makefile +1 -1
@@ -7,7 +7,7 @@ obj-y = sched.o fork.o exec_domain.o sysctl.o capability.o ptrace.o timer.o user.o \ signal.o sys.o kmod.o workqueue.o pid.o \ rcupdate.o intermodule.o extable.o params.o posix-timers.o \ - kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o + kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o obj-$(CONFIG_FUTEX) += futex.o obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
kernel/mutex.c new file +518 -0
518 lines not on this page · raw message
Quoted 1 line
+#include <
linux/config.h>
we don't need config.h anymore, it's included implicitly now.
Quoted 1 line
+#include <
asm/atomic.h>
Any chance we could include this after the <linux/*.h> headers ?
Quoted 1 line
+#include <
linux/spinlock_types.h>
What do we need this one for?
include/linux/mutex.h line 46
Quoted 2 lines
include/linux/mutex.h new file +2
-0+struct mutex { +// 1: unlocked, 0: locked, negative: locked, possible waiters
please use /* */ comments.
include/linux/mutex.h line 57
Quoted 11 lines
include/linux/mutex.h new file +11
-0+atomic_t count; +spinlock_t wait_lock; +struct list_head wait_list; +#ifdef CONFIG_DEBUG_MUTEXES +struct thread_info *owner; +struct list_head held_list; +unsigned long acquire_ip; +const char *name; +void *magic; +#endif +};
I know we generally don't like typedefs, but mutex is like spinlocks one of those cases where the internals should be completely opaqueue, so a mutex_t sounds like a good idea.
Quoted 1 line
+#include <
linux/syscalls.h>
What do you we need this header for?
kernel/mutex.c line 358
Quoted 9 lines
kernel/mutex.c new file +9
-0+static inline void __mutex_lock_atomic (struct mutex *lock) +{ +#ifdef __ARCH_WANT_XCHG_BASED_ATOMICS +if (unlikely (atomic_xchg (&lock->count,0 ) !=1 )) +__mutex_lock_noinline (&lock->count); +#else +atomic_dec_call_if_negative (&lock->count, __mutex_lock_noinline); +#endif +}
this is the kind of thing I meant in the comment to the announcement.
Just having this in arch code would kill all these ifdefs over mutex.c
Quoted 22 lines · Ingo Molnar
kernel/mutex.c new file +21
-0+__mutex_lock_common(struct mutex *lock, struct mutex_waiter *waiter, + struct thread_info *ti, + unsigned long task_state __IP_DECL__) +{ +struct task_struct *task = ti->task; +unsigned int old_val; + +/* +* Lets try to take the lock again - this is needed even if +* we get here for the first time (shortly after failing to +* acquire the lock), to make sure that we get a wakeup once +* it's unlocked. Later on this is the operation that gives +* us the lock. If there are other waiters we need to xchg it +* to -1, so that when we release the lock, we properly wake +* up the other waiters: +*/ + old_val =atomic_xchg (&lock->count,-1 ); + +if (unlikely (old_val ==1 )) { +/* +* Got the lock - rejoice! But there's one small
kernel/mutex.c line 134
Quoted 10 lines
kernel/mutex.c new file +10
-0+* detail to fix up: above we have set the lock to -1, +* unconditionally. But what if there are no waiters? +* While it would work with -1 too, 0 is a better value +* in that case, because we wont hit the slowpath when +* we release the lock. We can simply use atomic_set() +* for this, because we are the owners of the lock now, +* and are still holding the wait_lock: +*/ +if (likely (list_empty (&lock->wait_list))) +atomic_set (&lock->count,0 );
This is a minor issue, but still I think it makes sense to optimize for uncontended case:
old_val = atomic_xchg(&lock->count, 0); // no sleepers
if (old_val == 1) {
// sleepers ?
if (!list_empty(&lock->wait_list))
// need to wakeup them
atomic_set(&lock->count, -1);
...
}Oleg.
Quoted 3 lines · Christoph Hellwig
Quoted 1 line
+#include <
linux/config.h>we don't need
config.hanymore, it's included implicitly now.
thanks, fixed.
Quoted 3 lines
Quoted 1 line
+#include <
asm/atomic.h>Any chance we could include this after the <linux/*.h> headers ?
done.
Quoted 3 lines
Quoted 1 line
+#include <
linux/spinlock_types.h>What do we need this one for?
for:
spinlock_t wait_lock;
Quoted 4 lines
include/linux/mutex.h line 46
Quoted 2 lines
include/linux/mutex.h new file +2
-0+struct mutex { +// 1: unlocked, 0: locked, negative: locked, possible waiters please use /* */ comments.
done.
Quoted 16 lines
include/linux/mutex.h line 57
Quoted 12 lines
include/linux/mutex.h new file +11
-0+atomic_t count; +spinlock_t wait_lock; +struct list_head wait_list; +#ifdef CONFIG_DEBUG_MUTEXES +struct thread_info *owner; +struct list_head held_list; +unsigned long acquire_ip; +const char *name; +void *magic; +#endif +};I know we generally don't like typedefs, but mutex is like spinlocks one of those cases where the internals should be completely opaqueue, so a
mutex_tsounds like a good idea.
yeah, but we have DEFINE_MUTEX ...
Quoted 3 lines
Quoted 1 line
+#include <
linux/syscalls.h>What do you we need this header for?
correct, fixed.
Quoted 11 lines
kernel/mutex.c line 358
Quoted 9 lines
kernel/mutex.c new file +9
-0+static inline void __mutex_lock_atomic (struct mutex *lock) +{ +#ifdef __ARCH_WANT_XCHG_BASED_ATOMICS +if (unlikely (atomic_xchg (&lock->count,0 ) !=1 )) +__mutex_lock_noinline (&lock->count); +#else +atomic_dec_call_if_negative (&lock->count, __mutex_lock_noinline); +#endif +}this is the kind of thing I meant in the comment to the announcement.
i've solved that via the CONFIG_MUTEX_XCHG_ALGORITHM switch. It's more maintainable than 23 asm-*/mutex.h's.
Quoted 1 line
Just having this in arch code would kill all these ifdefs over
mutex.c
it's exactly 3 #ifdefs.
Ingo
Quoted 28 lines · Oleg Nesterov
Quoted 14 lines
kernel/mutex.c new file +14
-0+/* +* Lets try to take the lock again - this is needed even if +* we get here for the first time (shortly after failing to +* acquire the lock), to make sure that we get a wakeup once +* it's unlocked. Later on this is the operation that gives +* us the lock. If there are other waiters we need to xchg it +* to -1, so that when we release the lock, we properly wake +* up the other waiters: +*/ + old_val =atomic_xchg (&lock->count,-1 ); + +if (unlikely (old_val ==1 )) { +/* +* Got the lock - rejoice! But there's one small kernel/mutex.c line 134
Quoted 10 lines
kernel/mutex.c new file +10
-0+* detail to fix up: above we have set the lock to -1, +* unconditionally. But what if there are no waiters? +* While it would work with -1 too, 0 is a better value +* in that case, because we wont hit the slowpath when +* we release the lock. We can simply use atomic_set() +* for this, because we are the owners of the lock now, +* and are still holding the wait_lock: +*/ +if (likely (list_empty (&lock->wait_list))) +atomic_set (&lock->count,0 );This is a minor issue, but still I think it makes sense to optimize for uncontended case:
Quoted 10 lines
old_val = atomic_xchg(&lock->count, 0); // no sleepers
if (old_val == 1) {
// sleepers ?
if (!list_empty(&lock->wait_list))
// need to wakeup them
atomic_set(&lock->count, -1);
...
}
[*]but then we'd have to set it to -1 again, at [*], because we are now about to become a waiter. So i'm not sure it's worth switching this around.
Also, there are two uses of this codepath: first it's the 'did we race with an unlocker', in which case the lock is almost likely still contended. The second pass comes after we have woken up, in which case it's likely uncontended.
while we could split up the two cases and optimize each for its own situation, i think it makes more sense to have then unified, and thus to have more compact code. It's the slowpath after all.
Ingo
Quoted 15 lines · Ingo Molnar
Quoted 4 lines
This is a minor issue, but still I think it makes sense to optimize for uncontended case:
Quoted 10 lines
old_val = atomic_xchg(&lock->count, 0); // no sleepers if (old_val == 1) { // sleepers ? if (!list_empty(&lock->wait_list)) // need to wakeup them atomic_set(&lock->count, -1); ... } [*]
Quoted 1 line
but then we'd have to set it to -1 again, at [*], because we are now
Oh! You are right, thanks.
Oleg.