Generic Mutex Subsystem, mutex-core.patch

+ * These semantics are fully enforced when DEBUG_MUTEXESS 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:

+/*
+ * We can speed up the lock-acquire, if the architecture
+ * supports cmpxchg and if there's no debugging state
+ * to be set up (!DEBUG_MUTEXESS).
+ *
+ * trick: we can use cmpxchg on the release side too, if bit
+ * 0 of lock->owner is set if there is at least a single pending

kernel/mutex.c new file +12 -0

+static inline void
+__mutex_wakeup_waiter(struct mutex *lock __IP_DECL__)
+{
+       struct mutex_waiter *waiter;
+
+       SMP_DEBUG_WARN_ON(!spin_is_locked(&lock->wait_lock));
+       DEBUG_WARN_ON(list_empty(&lock->wait_list));
+
+       /*
+        * Get the first entry from the wait-list:
+        */
+       waiter = list_entry(lock->wait_list.next, struct mutex_waiter,

list);
+

kernel/mutex.c new file +5 -0

+       spin_lock(&lock->wait_lock);
+       __add_waiter(lock, waiter, ti, task __IP__);
+       set_task_state(task, task_state);
+
+       /*

kernel/mutex.c line 187

Quoted 11 lines · Ingo Molnar

kernel/mutex.c new file +4 -0

+static inline int
+__mutex_lock_common(struct mutex *lock, struct mutex_waiter *waiter,
+                   struct thread_info *ti, struct task_struct *task,
+                   unsigned long *flags, unsigned long task_state

__IP_DECL__)

kernel/mutex.c new file +6 -0

+{
+       unsigned int old_val;
+
+       debug_lock_irqsave(&debug_lock, *flags, ti);
+       DEBUG_WARN_ON(lock->magic != lock);
+

How expensive is the xchg? Since __mutex_lock_common is called even when it's going to wake up. Maybe it might be more efficient to add something like:

          if (atomic_cmpxchg(&lock->count, 1, 0) {
              debug_set_owner(lock, ti __IP__);
              debug_unlock_irqrestore(&debug_lock, *flags, ti);
              return 1;
	  }

This way we save the overhead of grabbing another spinlock, adding the task to the wait_list and changing it's state.

Quoted 5 lines

kernel/mutex.c new file +5 -0

+       spin_lock(&lock->wait_lock);
+       __add_waiter(lock, waiter, ti, task __IP__);
+       set_task_state(task, task_state);
+
+       /*

kernel/mutex.c line 202

Quoted 10 lines

kernel/mutex.c new file +10 -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. We need to xchg it to -1, so that when we
+        * release the lock, we properly wake up other waiters!
+        */
+       old_val = atomic_xchg(&lock->count, -1);
+
+       if (old_val == 1) {

-- Steve

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

How expensive is the xchg? Since __mutex_lock_common is called even when it's going to wake up. Maybe it might be more efficient to add something like:

          if (atomic_cmpxchg(&lock->count, 1, 0) {
              debug_set_owner(lock, ti __IP__);
              debug_unlock_irqrestore(&debug_lock, *flags, ti);
              return 1;
	  }

This way we save the overhead of grabbing another spinlock, adding the task to the wait_list and changing it's state.

+static inline void __mutex_unlock_nonatomic(struct mutex *lock __IP_DECL__)

kernel/mutex.c new file +7 -0

+{
+       struct thread_info *ti = current_thread_info();
+       unsigned long flags;
+
+       debug_lock_irqsave(&debug_lock, flags, ti);
+       spin_lock(&lock->wait_lock);
+

kernel/mutex.c new file +5 -0

+       if (unlikely(!list_empty(&lock->wait_list)))
+               __mutex_wakeup_waiter(lock __IP__);
+#ifdef CONFIG_DEBUG_MUTEXESS
+       lock->owner = NULL;
+#endif

The unlikely below is only for the non MUTEX_LOCKLESS_FASTPATH case. Maybe have a define for the unlikely?

#ifdef MUTEX_LOCKLESS_FASTPATH
# define UNLIKELY_SLOW(x) x
#else
# define UNLIKELY_SLOW(x) unlikely(x)
#endif

Quoted 2 lines

(quoted diff) +2 -0

+       if (unlikely(!list_empty(&lock->wait_list)))
+               __mutex_wakeup_waiter(lock __IP__);

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

Signed-off-by Ingo Molnar <[email protected]>

----

 include/linux/mutex.h   |  102 ++++++++
 include/linux/preempt.h |    1 
 include/linux/sched.h   |    5 
 kernel/Makefile         |    2 
 kernel/fork.c           |    4 
 kernel/mutex.c          |  564
++++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 677 insertions(+), 1 deletion(-)

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

kernel/mutex.c line 190

Quoted 3 lines

kernel/mutex.c new file +3 -0

+	spin_lock(&lock->wait_lock);
+	__add_waiter(lock, waiter, ti, task __IP__);
+	set_task_state(task, task_state);

I can't understand why __mutex_lock_common() does xchg() after adding the waiter to the ->wait_list. We are holding ->wait_lock, we can't race with __mutex_unlock_nonatomic() - it calls wake_up() and sets ->count under this spinlock.

Quoted 4 lines · Oleg Nesterov

Quoted 3 lines

kernel/mutex.c new file +3 -0

+   spin_lock(&lock->wait_lock);
+   __add_waiter(lock, waiter, ti, task __IP__);
+   set_task_state(task, task_state);

Quoted 4 lines

I can't understand why __mutex_lock_common() does xchg() after adding the waiter to the ->wait_list. We are holding ->wait_lock, we can't race with __mutex_unlock_nonatomic() - it calls wake_up() and sets ->count under this spinlock.

we must make sure that the drop has not been dropped meanwhile, on the way in, between the fastpath-unlock atomic op, and the xchg() here.

But why we can't add the waiter to ->wait_list _after_ xchg() ? What makes the difference? Fastpath atomic op can happen before or after xchg(), this is ok. Unlock path will look at ->wait_list only after taking spinlock, at this time we already added this waiter to the ->wait_list.

In other words: we are holding ->wait_lock, nobody can even look at ->wait_list. We can add the waiter to ->wait_list before or after atomic_xchg() - it does not matter.

kernel/mutex.c line 275

Quoted 8 lines

kernel/mutex.c new file +7 -0

+__mutex_wakeup_waiter(struct mutex *lock __IP_DECL__)
+{
+	struct mutex_waiter *waiter;
...
+	if (!waiter->woken) {
+		waiter->woken = 1;
+		wake_up_process(waiter->ti->task);
+	}

Is it optimization? If yes - why? From mutex.h:

- only one task can hold the mutex at a time
- only the owner can unlock the mutex

So, how can this help?

kernel/mutex.c line 297

Quoted 10 lines

kernel/mutex.c new file +10 -0

+start_mutex_timer(struct timer_list *timer, unsigned long time,
+		  unsigned long *expire)
+{
+	*expire = time + jiffies;
+	init_timer(timer);
+	timer->expires = *expire;
+	timer->data = (unsigned long)current;
+	timer->function = process_timeout;
+	add_timer(timer);
+}

How about

	setup_timer(&timer, process_timeout, (unsigned long)current);
	__mod_timer(&timer, *expire);

?