Skip to contentSkip to conversation

mutex subsystem, core

PATCH In review Ingo Molnar 4 participants 7 messages Jan 3, 2006 Locking primitives

lore
Share & tools
lore
#0 lore raw

PATCH 8/19 mutex subsystem, core

mutex implementation, core files: just the basic subsystem, no users of it.

----

 include/linux/mutex.h |  111 ++++++++++++
 kernel/Makefile       |    2 
 kernel/mutex.c        |  438 ++++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/mutex.h        |   35 +++
 4 files changed, 585 insertions(+), 1 deletion(-)
include/linux/mutex.h new file +111 -0
Index: linux/include/linux/mutex.h
===================================================================
@@ -0,0 +1,111 @@
+/*
+ * 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.
+ */
+#ifndef __LINUX_MUTEX_H
+#define __LINUX_MUTEX_H
+
+#include <linux/list.h>
+#include <linux/spinlock_types.h>
+
+#include <asm/atomic.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(mutex)			__mutex_init(mutex, NULL)
+# define mutex_destroy(mutex)				do { } while (0)
+# 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));
+
+/***
+ * mutex_is_locked - is the mutex locked
+ * @lock: the mutex to be queried
+ *
+ * Returns 1 if the mutex is locked, 0 if unlocked.
+ */
+static inline int fastcall mutex_is_locked(struct mutex *lock)
+{
+	return atomic_read(&lock->count) != 1;
+}
+
+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));
+
+#endif
kernel/Makefile +1 -1
Index: linux/kernel/Makefile
===================================================================
@@ -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 +438 -0

438 lines not on this page · raw message

kernel/mutex.h new file +35 -0
Index: linux/kernel/mutex.h
===================================================================
@@ -0,0 +1,35 @@
+/*
+ * Mutexes: blocking mutual exclusion locks
+ *
+ * started by Ingo Molnar:
+ *
+ *  Copyright (C) 2004, 2005 Red Hat, Inc., Ingo Molnar <[email protected]>
+ *
+ * This file contains mutex debugging related internal prototypes, for the
+ * !CONFIG_DEBUG_MUTEXES case. Most of them are NOPs:
+ */
+
+#define spin_lock_mutex(lock)			spin_lock(lock)
+#define spin_unlock_mutex(lock)			spin_unlock(lock)
+#define mutex_remove_waiter(lock, waiter, ti) \
+		__list_del((waiter)->list.prev, (waiter)->list.next)
+
+#define DEBUG_WARN_ON(c)				do { } while (0)
+#define debug_mutex_set_owner(lock, new_owner)		do { } while (0)
+#define debug_mutex_clear_owner(lock)			do { } while (0)
+#define debug_mutex_init_waiter(waiter)			do { } while (0)
+#define debug_mutex_wake_waiter(lock, waiter)		do { } while (0)
+#define debug_mutex_free_waiter(waiter)			do { } while (0)
+#define debug_mutex_add_waiter(lock, waiter, ti, ip)	do { } while (0)
+#define debug_mutex_unlock(lock)			do { } while (0)
+#define debug_mutex_init(lock, name)			do { } while (0)
+
+/*
+ * Return-address parameters/declarations. They are very useful for
+ * debugging, but add overhead in the !DEBUG case - so we go the
+ * trouble of using this not too elegant but zero-cost solution:
+ */
+#define __IP_DECL__
+#define __IP__
+#define __RET_IP__
+
#1 lore raw
Quoted 44 lines · Ingo Molnar
kernel/mutex.c new file +44 -0
+
+/*
+ * Spinlock based trylock, we take the spinlock and check whether we
+ * can get the lock:
+ */
+static inline int __mutex_trylock_nonatomic(atomic_t *lock_count)
+{
+	struct mutex *lock = container_of(lock_count, struct mutex, count);
+	int prev;
+
+	spin_lock_mutex(&lock->wait_lock);
+
+	prev = atomic_xchg(&lock->count, -1);
+	if (likely(prev == 1))
+		debug_mutex_set_owner(lock, current_thread_info() __RET_IP__);
+	/* Set it back to 0 if there are no waiters: */
+	if (likely(list_empty(&lock->wait_list)))
+		atomic_set(&lock->count, 0);
+
+	spin_unlock_mutex(&lock->wait_lock);
+
+	return prev == 1;
+}
+
+/***
+ * mutex_trylock - try acquire the mutex, without waiting
+ * @lock: the mutex to be acquired
+ *
+ * Try to acquire the mutex atomically. Returns 1 if the mutex
+ * has been acquired successfully, and 0 on contention.
+ *
+ * NOTE: this function follows the spin_trylock() convention, so
+ * it is negated to the down_trylock() return values! Be careful
+ * about this when converting semaphore users to mutexes.
+ *
+ * This function must not be used in interrupt context. The
+ * mutex must be released by the same task that acquired it.
+ */
+int fastcall mutex_trylock(struct mutex *lock)
+{
+	return __mutex_fastpath_trylock(&lock->count,
+					__mutex_trylock_nonatomic);
+}
+

[snip]

kernel/mutex.h line 13

Quoted 3 lines
kernel/mutex.h new file +3 -0
+
+#define spin_lock_mutex(lock)			spin_lock(lock)
+#define spin_unlock_mutex(lock)			spin_unlock(lock)

Is this an interrupt deadlock, or do you not allow interrupt contexts to even trylock a mutex?

If the former, I would simply use atomic_cmpxchg unconditionally for the trylock and not use a spinlock fallback function at all.

Alternately, you may 'trylock' the spinlock, but it just seems like extra code for not much reason (when you can use atomic_cmpxchg).

Signature · 3 lines
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 
#2 lore raw
Quoted 5 lines · Nick Piggin

kernel/mutex.h line 13

Quoted 2 lines
kernel/mutex.h new file +2 -0
+#define spin_lock_mutex(lock)			spin_lock(lock)
+#define spin_unlock_mutex(lock)			spin_unlock(lock)

Is this an interrupt deadlock, or do you not allow interrupt contexts to even trylock a mutex?

correct, no irq contexts are allowed. This is also checked for if CONFIG_DEBUG_MUTEXES is enabled.

Ingo

#3 lore raw
Quoted 6 lines · Ingo Molnar
Quoted 3 lines

Is this an interrupt deadlock, or do you not allow interrupt contexts to even trylock a mutex?

correct, no irq contexts are allowed. This is also checked for if CONFIG_DEBUG_MUTEXES is enabled.

Note that semaphores are definitely used from interrupt context, and as such you can't replace them with mutexes if you do this.

The prime example is the console semaphore. See kernel/printk.c, look for "down_trylock()", and realize that they are all about interrupts.

Linus

#4 lore raw
Quoted 5 lines · Linus Torvalds
Quoted 4 lines · Ingo Molnar
Quoted 3 lines

Is this an interrupt deadlock, or do you not allow interrupt contexts to even trylock a mutex?

Quoted 8 lines
Quoted 2 lines

correct, no irq contexts are allowed. This is also checked for if CONFIG_DEBUG_MUTEXES is enabled.

Note that semaphores are definitely used from interrupt context, and as such you can't replace them with mutexes if you do this.

The prime example is the console semaphore. See kernel/printk.c, look for "down_trylock()", and realize that they are all about interrupts.

yeah, i know - and i'm not trying to replace _all_ semaphore uses. down_trylock() is used only 54 times in drivers/*, while down() is used 2986 times. And even of those 54 cases, only a small minority does it from an IRQ context.

Ingo

#5 lore raw
In reply to Ingo Molnar
Quoted 3 lines · Ingo Molnar

mutex implementation, core files: just the basic subsystem, no users of it.

(on top of this patch)

'add_to_head' always declared and used along with 'struct waiter'. I think it is better to hide 'add_to_head' in that struct.

include/linux/mutex.h renamed from include/linux/mutex.h~1_HEAD +1 -0
@@ -61,6 +61,7 @@ struct mutex {
  * which resides on the blocked task's kernel stack:
  */
 struct mutex_waiter {
+	int			add_to_head;
 	struct list_head	list;
 	struct thread_info	*ti;
 #ifdef CONFIG_DEBUG_MUTEXES
kernel/mutex.c renamed from kernel/mutex.c~1_HEAD +19 -13
@@ -28,13 +28,19 @@
 # include <asm/mutex.h>
 #endif
 
+static inline void mutex_init_waiter(struct mutex_waiter *waiter)
+{
+	/* first time queue the waiter as FIFO: */
+	waiter->add_to_head = 0;
+}
+
 /*
  * Block on a lock - add ourselves to the list of waiters.
  * Called with lock->wait_lock held.
  */
 static inline void
 add_waiter(struct mutex *lock, struct mutex_waiter *waiter,
-	   struct thread_info *ti, int add_to_head __IP_DECL__)
+	   struct thread_info *ti __IP_DECL__)
 {
 	debug_mutex_add_waiter(lock, waiter, ti, ip);
 
@@ -44,10 +50,12 @@ add_waiter(struct mutex *lock, struct mu
 	 * Add waiting tasks to the end of the waitqueue (FIFO),
 	 * but add repeat waiters to the head (LIFO):
 	 */
-	if (add_to_head)
+	if (waiter->add_to_head)
 		list_add(&waiter->list, &lock->wait_list);
 	else
 		list_add_tail(&waiter->list, &lock->wait_list);
+
+	waiter->add_to_head = 1;
 }
 
 /*
@@ -74,8 +82,8 @@ mutex_wakeup_waiter(struct mutex *lock _
  */
 static inline int
 __mutex_lock_common(struct mutex *lock, struct mutex_waiter *waiter,
-		    struct thread_info *ti, unsigned long task_state,
-		    const int add_to_head __IP_DECL__)
+		    struct thread_info *ti, unsigned long task_state
+		    __IP_DECL__)
 {
 	struct task_struct *task = ti->task;
 	unsigned int old_val;
@@ -115,7 +123,7 @@ __mutex_lock_common(struct mutex *lock, 
 		return 1;
 	}
 
-	add_waiter(lock, waiter, ti, add_to_head __IP__);
+	add_waiter(lock, waiter, ti __IP__);
 	__set_task_state(task, task_state);
 
 	/*
@@ -133,19 +141,17 @@ static inline void __mutex_lock_nonatomi
 {
 	struct thread_info *ti = current_thread_info();
 	struct mutex_waiter waiter;
-	/* first time queue the waiter as FIFO: */
-	int add_to_head = 0;
 
 	debug_mutex_init_waiter(&waiter);
 
+	mutex_init_waiter(&waiter);
+
 	spin_lock_mutex(&lock->wait_lock);
 
 	/* releases the internal lock: */
 	while (!__mutex_lock_common(lock, &waiter, ti,
-			TASK_UNINTERRUPTIBLE, add_to_head __IP__)) {
+			TASK_UNINTERRUPTIBLE __IP__)) {
 
-		/* start queueing the waiter as LIFO: */
-		add_to_head = 1;
 		/* wait to be woken up: */
 		schedule();
 
@@ -162,23 +168,23 @@ __mutex_lock_interruptible_nonatomic(str
 {
 	struct thread_info *ti = current_thread_info();
 	struct mutex_waiter waiter;
-	int add_to_head = 0;
 
 	debug_mutex_init_waiter(&waiter);
 
+	mutex_init_waiter(&waiter);
+
 	spin_lock_mutex(&lock->wait_lock);
 
 	for (;;) {
 		/* releases the internal lock: */
 		if (__mutex_lock_common(lock, &waiter, ti,
-				TASK_INTERRUPTIBLE, add_to_head __IP__))
+				TASK_INTERRUPTIBLE __IP__))
 			return 0;
 
 		/* break out on a signal: */
 		if (unlikely(signal_pending(ti->task)))
 			break;
 
-		add_to_head = 1;
 		/* wait to be woken up: */
 		schedule();
#6 lore raw
Quoted 6 lines · Oleg Nesterov
Quoted 1 line

mutex implementation, core files: just the basic subsystem, no users of it.

(on top of this patch)

'add_to_head' always declared and used along with 'struct waiter'. I think it is better to hide 'add_to_head' in that struct.

please check -V13, there i got rid of add_to_head altogether, by changing the queueing logic.

Ingo