Skip to contentSkip to conversation

futex: checkpatch cleanup

PATCH In review Daniel Walker 3 participants 14 messages Jun 24, 2008 – Jun 25, 2008

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/6 futex: checkpatch cleanup

---
 kernel/futex.c |   52 +++++++++++++++++++++++++++-------------------------
 1 file changed, 27 insertions(+), 25 deletions(-)
kernel/futex.c +27 -25
Index: linux-2.6.25/kernel/futex.c
===================================================================
@@ -145,7 +145,7 @@ static inline void futex_unlock_mm(struc
  */
 static struct futex_hash_bucket *hash_futex(union futex_key *key)
 {
-	u32 hash = jhash2((u32*)&key->both.word,
+	u32 hash = jhash2((u32 *)&key->both.word,
 			  (sizeof(key->both.word)+sizeof(key->both.ptr))/4,
 			  key->both.offset);
 	return &futex_queues[hash & ((1 << FUTEX_HASHBITS)-1)];
@@ -234,7 +234,8 @@ static int get_futex_key(u32 __user *uad
 	 * mappings of _writable_ handles.
 	 */
 	if (likely(!(vma->vm_flags & VM_MAYSHARE))) {
-		key->both.offset |= FUT_OFF_MMSHARED; /* reference taken on mm */
+		/* reference taken on mm */
+		key->both.offset |= FUT_OFF_MMSHARED;
 		key->private.mm = mm;
 		key->private.address = address;
 		return 0;
@@ -277,12 +278,12 @@ static void get_futex_key_refs(union fut
 	if (key->both.ptr == NULL)
 		return;
 	switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
-		case FUT_OFF_INODE:
-			atomic_inc(&key->shared.inode->i_count);
-			break;
-		case FUT_OFF_MMSHARED:
-			atomic_inc(&key->private.mm->mm_count);
-			break;
+	case FUT_OFF_INODE:
+		atomic_inc(&key->shared.inode->i_count);
+		break;
+	case FUT_OFF_MMSHARED:
+		atomic_inc(&key->private.mm->mm_count);
+		break;
 	}
 }
 
@@ -295,12 +296,12 @@ static void drop_futex_key_refs(union fu
 	if (!key->both.ptr)
 		return;
 	switch (key->both.offset & (FUT_OFF_INODE|FUT_OFF_MMSHARED)) {
-		case FUT_OFF_INODE:
-			iput(key->shared.inode);
-			break;
-		case FUT_OFF_MMSHARED:
-			mmdrop(key->private.mm);
-			break;
+	case FUT_OFF_INODE:
+		iput(key->shared.inode);
+		break;
+	case FUT_OFF_MMSHARED:
+		mmdrop(key->private.mm);
+		break;
 	}
 }
 
@@ -333,7 +334,7 @@ static int get_futex_value_locked(u32 *d
 static int futex_handle_fault(unsigned long address,
 			      struct rw_semaphore *fshared, int attempt)
 {
-	struct vm_area_struct * vma;
+	struct vm_area_struct *vma;
 	struct mm_struct *mm = current->mm;
 	int ret = -EFAULT;
 
@@ -391,7 +392,7 @@ static int refill_pi_state_cache(void)
 	return 0;
 }
 
-static struct futex_pi_state * alloc_pi_state(void)
+static struct futex_pi_state *alloc_pi_state(void)
 {
 	struct futex_pi_state *pi_state = current->pi_state_cache;
 
@@ -436,7 +437,7 @@ static void free_pi_state(struct futex_p
  * Look up the task based on what TID userspace gave us.
  * We dont trust it.
  */
-static struct task_struct * futex_find_get_task(pid_t pid)
+static struct task_struct *futex_find_get_task(pid_t pid)
 {
 	struct task_struct *p;
 
@@ -742,7 +743,7 @@ static int futex_wake(u32 __user *uaddr,
 	head = &hb->chain;
 
 	plist_for_each_entry_safe(this, next, head, list) {
-		if (match_futex (&this->key, &key)) {
+		if (match_futex(&this->key, &key)) {
 			if (this->pi_state) {
 				ret = -EINVAL;
 				break;
@@ -848,7 +849,7 @@ retry:
 	head = &hb1->chain;
 
 	plist_for_each_entry_safe(this, next, head, list) {
-		if (match_futex (&this->key, &key1)) {
+		if (match_futex(&this->key, &key1)) {
 			wake_futex(this);
 			if (++ret >= nr_wake)
 				break;
@@ -860,7 +861,7 @@ retry:
 
 		op_ret = 0;
 		plist_for_each_entry_safe(this, next, head, list) {
-			if (match_futex (&this->key, &key2)) {
+			if (match_futex(&this->key, &key2)) {
 				wake_futex(this);
 				if (++op_ret >= nr_wake2)
 					break;
@@ -938,7 +939,7 @@ static int futex_requeue(u32 __user *uad
 
 	head1 = &hb1->chain;
 	plist_for_each_entry_safe(this, next, head1, list) {
-		if (!match_futex (&this->key, &key1))
+		if (!match_futex(&this->key, &key1))
 			continue;
 		if (++ret <= nr_wake) {
 			wake_futex(this);
@@ -1648,7 +1649,8 @@ retry_unlocked:
 	 * anyone else up:
 	 */
 	if (!(uval & FUTEX_OWNER_DIED))
-		uval = cmpxchg_futex_value_locked(uaddr, task_pid_vnr(current), 0);
+		uval = cmpxchg_futex_value_locked(uaddr,
+						  task_pid_vnr(current), 0);
 
 
 	if (unlikely(uval == -EFAULT))
@@ -1667,7 +1669,7 @@ retry_unlocked:
 	head = &hb->chain;
 
 	plist_for_each_entry_safe(this, next, head, list) {
-		if (!match_futex (&this->key, &key))
+		if (!match_futex(&this->key, &key))
 			continue;
 		ret = wake_futex_pi(uaddr, uval, this);
 		/*
@@ -1913,8 +1915,8 @@ void exit_robust_list(struct task_struct
 		 * don't process it twice:
 		 */
 		if (entry != pending)
-			if (handle_futex_death((void __user *)entry + futex_offset,
-						curr, pi))
+			if (handle_futex_death((void __user *)entry +
+						futex_offset, curr, pi))
 				return;
 		if (rc)
 			return;
#1 lore raw

PATCH 2/6 futex: update prio on requeue

Since the priority may have changed, the requeue is a good place to update the priority since we're already deleting and adding to a new list.

---
 kernel/futex.c |    4 ++++
 1 file changed, 4 insertions(+)
kernel/futex.c +4 -0
Index: linux-2.6.25/kernel/futex.c
===================================================================
@@ -949,7 +949,11 @@ static int futex_requeue(u32 __user *uad
 			 * requeue.
 			 */
 			if (likely(head1 != &hb2->chain)) {
+				struct task_struct *task = this->task;
+				int prio = min(task->normal_prio, MAX_RT_PRIO);
+
 				plist_del(&this->list, &hb1->chain);
+				plist_node_init(&this->list, prio);
 				plist_add(&this->list, &hb2->chain);
 				this->lock_ptr = &hb2->lock;
 #ifdef CONFIG_DEBUG_PI_LIST
#2 lore raw

PATCH 3/6 mutex debug: add generic blocked_on usage

In reply to Daniel Walker

There are a couple of blocked on type structures. One for mutexes, and one for rtmutexes, and we also need one for futexes.

Instead of just adding another one to the task struct I combined them all into a union. Since a waiter can only be blocked on one of the types at any given time this should be safe.

I also usurped the pi_lock as the lock which protects all the blocked_on types.

---
 include/linux/sched.h |   39 +++++++++++++++++++++++++++++++++++----
 kernel/mutex-debug.c  |   25 ++++++++++++++++++-------
 kernel/mutex-debug.h  |    4 +++-
 kernel/mutex.c        |    6 +++++-
 4 files changed, 61 insertions(+), 13 deletions(-)
include/linux/sched.h +35 -4
Index: linux-2.6.25/include/linux/sched.h
===================================================================
@@ -1023,6 +1023,17 @@ struct sched_rt_entity {
 #endif
 };
 
+enum lock_waiter_type {
+	MUTEX_WAITER = 1,
+};
+
+struct lock_waiter_state {
+	enum lock_waiter_type lock_type;
+	union {
+		struct mutex_waiter *mutex_blocked_on;
+	};
+};
+
 struct task_struct {
 	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
 	void *stack;
@@ -1200,7 +1211,7 @@ struct task_struct {
 /* Protection of (de-)allocation: mm, files, fs, tty, keyrings */
 	spinlock_t alloc_lock;
 
-	/* Protection of the PI data structures: */
+	/* Protects blocked_on field and PI waiters list. */
 	spinlock_t pi_lock;
 
 #ifdef CONFIG_RT_MUTEXES
@@ -1210,10 +1221,14 @@ struct task_struct {
 	struct rt_mutex_waiter *pi_blocked_on;
 #endif
 
-#ifdef CONFIG_DEBUG_MUTEXES
-	/* mutex deadlock detection */
-	struct mutex_waiter *blocked_on;
+#if defined(CONFIG_DEBUG_MUTEXES)
+	/*
+	 * Deadlock detection and priority inheritance handling,
+	 * and any other out of line mutex operations
+	 */
+	struct lock_waiter_state *blocked_on;
 #endif
+
 #ifdef CONFIG_TRACE_IRQFLAGS
 	unsigned int irq_events;
 	int hardirqs_enabled;
@@ -1305,6 +1320,22 @@ struct task_struct {
 #endif
 };
 
+#if defined(CONFIG_DEBUG_MUTEXES)
+/*
+ * set_blocked_on - Set the blocked on field in the task struct.
+ */
+static inline void
+set_blocked_on(struct task_struct *p, struct lock_waiter_state *blocked_on)
+{
+	spin_lock(&p->pi_lock);
+	p->blocked_on = blocked_on;
+	spin_unlock(&p->pi_lock);
+}
+#else
+static inline void
+set_blocked_on(struct task_struct *p, struct lock_waiter_state *blocked_on) { }
+#endif
+
 /*
  * Priority of a process goes from 0..MAX_PRIO-1, valid RT
  * priority is 0..MAX_RT_PRIO-1, and SCHED_NORMAL/SCHED_BATCH
kernel/mutex-debug.c +18 -7
Index: linux-2.6.25/kernel/mutex-debug.c
===================================================================
@@ -52,23 +52,34 @@ void debug_mutex_free_waiter(struct mute
 	memset(waiter, MUTEX_DEBUG_FREE, sizeof(*waiter));
 }
 
-void debug_mutex_add_waiter(struct mutex *lock, struct mutex_waiter *waiter,
-			    struct thread_info *ti)
+void
+debug_mutex_add_waiter(struct mutex *lock,
+		       struct lock_waiter_state *lock_waiter,
+		       struct thread_info *ti)
 {
+	struct task_struct *task = ti->task;
+
 	SMP_DEBUG_LOCKS_WARN_ON(!spin_is_locked(&lock->wait_lock));
 
 	/* Mark the current thread as blocked on the lock: */
-	ti->task->blocked_on = waiter;
-	waiter->lock = lock;
+	lock_waiter->mutex_blocked_on->lock = lock;
+	set_blocked_on(task, lock_waiter);
 }
 
 void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter *waiter,
 			 struct thread_info *ti)
 {
+	struct task_struct *task = ti->task;
+
+	spin_lock(&task->pi_lock);
+
 	DEBUG_LOCKS_WARN_ON(list_empty(&waiter->list));
-	DEBUG_LOCKS_WARN_ON(waiter->task != ti->task);
-	DEBUG_LOCKS_WARN_ON(ti->task->blocked_on != waiter);
-	ti->task->blocked_on = NULL;
+	DEBUG_LOCKS_WARN_ON(waiter->task != task);
+	DEBUG_LOCKS_WARN_ON(task->blocked_on == NULL);
+	DEBUG_LOCKS_WARN_ON(task->blocked_on->mutex_blocked_on != waiter);
+
+	task->blocked_on = NULL;
+	spin_unlock(&task->pi_lock);
 
 	list_del_init(&waiter->list);
 	waiter->task = NULL;
kernel/mutex-debug.h +3 -1
Index: linux-2.6.25/kernel/mutex-debug.h
===================================================================
@@ -25,10 +25,12 @@ extern void debug_mutex_lock_common(stru
 				    struct mutex_waiter *waiter);
 extern void debug_mutex_wake_waiter(struct mutex *lock,
 				    struct mutex_waiter *waiter);
+
 extern void debug_mutex_free_waiter(struct mutex_waiter *waiter);
 extern void debug_mutex_add_waiter(struct mutex *lock,
-				   struct mutex_waiter *waiter,
+				   struct lock_waiter_state *lock_waiter,
 				   struct thread_info *ti);
+
 extern void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter *waiter,
 				struct thread_info *ti);
 extern void debug_mutex_unlock(struct mutex *lock);
kernel/mutex.c +5 -1
Index: linux-2.6.25/kernel/mutex.c
===================================================================
@@ -130,12 +130,16 @@ __mutex_lock_common(struct mutex *lock, 
 	struct mutex_waiter waiter;
 	unsigned int old_val;
 	unsigned long flags;
+#ifdef CONFIG_DEBUG_MUTEXES
+	struct lock_waiter_state lock_waiter = {
+		.lock_type = MUTEX_WAITER, { .mutex_blocked_on = &waiter} };
+#endif
 
 	spin_lock_mutex(&lock->wait_lock, flags);
 
 	debug_mutex_lock_common(lock, &waiter);
 	mutex_acquire(&lock->dep_map, subclass, 0, ip);
-	debug_mutex_add_waiter(lock, &waiter, task_thread_info(task));
+	debug_mutex_add_waiter(lock, &lock_waiter, task_thread_info(task));
 
 	/* add waiting tasks to the end of the waitqueue (FIFO): */
 	list_add_tail(&waiter.list, &lock->wait_list);
#3 lore raw

PATCH 4/6 rtmutex: add generic blocked_on usage

In reply to Daniel Walker

Modify the rtmutex to use the generic blocked_on field.

---
 include/linux/sched.h   |    8 ++++----
 kernel/fork.c           |    3 +--
 kernel/rtmutex-debug.c  |    2 +-
 kernel/rtmutex-tester.c |    2 +-
 kernel/rtmutex.c        |   35 ++++++++++++++++++++++++-----------
 5 files changed, 31 insertions(+), 19 deletions(-)
include/linux/sched.h +4 -4
Index: linux-2.6.25/include/linux/sched.h
===================================================================
@@ -1025,12 +1025,14 @@ struct sched_rt_entity {
 
 enum lock_waiter_type {
 	MUTEX_WAITER = 1,
+	RT_MUTEX_WAITER,
 };
 
 struct lock_waiter_state {
 	enum lock_waiter_type lock_type;
 	union {
 		struct mutex_waiter *mutex_blocked_on;
+		struct rt_mutex_waiter *rt_blocked_on;
 	};
 };
 
@@ -1217,11 +1219,9 @@ struct task_struct {
 #ifdef CONFIG_RT_MUTEXES
 	/* PI waiters blocked on a rt_mutex held by this task */
 	struct plist_head pi_waiters;
-	/* Deadlock detection and priority inheritance handling */
-	struct rt_mutex_waiter *pi_blocked_on;
 #endif
 
-#if defined(CONFIG_DEBUG_MUTEXES)
+#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_RT_MUTEXES)
 	/*
 	 * Deadlock detection and priority inheritance handling,
 	 * and any other out of line mutex operations
@@ -1320,7 +1320,7 @@ struct task_struct {
 #endif
 };
 
-#if defined(CONFIG_DEBUG_MUTEXES)
+#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_RT_MUTEXES)
 /*
  * set_blocked_on - Set the blocked on field in the task struct.
  */
kernel/fork.c +1 -2
Index: linux-2.6.25/kernel/fork.c
===================================================================
@@ -850,7 +850,6 @@ static void rt_mutex_init_task(struct ta
 	spin_lock_init(&p->pi_lock);
 #ifdef CONFIG_RT_MUTEXES
 	plist_head_init(&p->pi_waiters, &p->pi_lock);
-	p->pi_blocked_on = NULL;
 #endif
 }
 
@@ -1028,7 +1027,7 @@ static struct task_struct *copy_process(
 	p->lockdep_recursion = 0;
 #endif
 
-#ifdef CONFIG_DEBUG_MUTEXES
+#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_RT_MUTEXES)
 	p->blocked_on = NULL; /* not blocked yet */
 #endif
 
kernel/rtmutex-debug.c +1 -1
Index: linux-2.6.25/kernel/rtmutex-debug.c
===================================================================
@@ -112,7 +112,7 @@ static void printk_lock(struct rt_mutex 
 void rt_mutex_debug_task_free(struct task_struct *task)
 {
 	WARN_ON(!plist_head_empty(&task->pi_waiters));
-	WARN_ON(task->pi_blocked_on);
+	WARN_ON(task->blocked_on);
 }
 
 /*
kernel/rtmutex-tester.c +1 -1
Index: linux-2.6.25/kernel/rtmutex-tester.c
===================================================================
@@ -377,7 +377,7 @@ static ssize_t sysfs_test_status(struct 
 		td->opcode, td->event, tsk->state,
 			(MAX_RT_PRIO - 1) - tsk->prio,
 			(MAX_RT_PRIO - 1) - tsk->normal_prio,
-		tsk->pi_blocked_on, td->bkl);
+		tsk->blocked_on, td->bkl);
 
 	for (i = MAX_RT_TEST_MUTEXES - 1; i >=0 ; i--)
 		curr += sprintf(curr, "%d", td->mutexes[i]);
kernel/rtmutex.c +24 -11
Index: linux-2.6.25/kernel/rtmutex.c
===================================================================
@@ -74,6 +74,14 @@ static void fixup_rt_mutex_waiters(struc
 		clear_rt_mutex_waiters(lock);
 }
 
+static
+struct rt_mutex_waiter *rt_mutex_get_waiter(struct task_struct *task)
+{
+	if (task->blocked_on && task->blocked_on->lock_type == RT_MUTEX_WAITER)
+		return task->blocked_on->rt_blocked_on;
+	return NULL;
+}
+
 /*
  * We can speed up the acquire/release, if the architecture
  * supports cmpxchg and if there's no debugging state to be set up
@@ -197,7 +205,7 @@ static int rt_mutex_adjust_prio_chain(st
 	 */
 	spin_lock_irqsave(&task->pi_lock, flags);
 
-	waiter = task->pi_blocked_on;
+	waiter = rt_mutex_get_waiter(task);
 	/*
 	 * Check whether the end of the boosting chain has been
 	 * reached or the state of the chain has changed while we
@@ -411,6 +419,7 @@ static int try_to_take_rt_mutex(struct r
  */
 static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 				   struct rt_mutex_waiter *waiter,
+				   struct lock_waiter_state *lock_waiter,
 				   int detect_deadlock)
 {
 	struct task_struct *owner = rt_mutex_owner(lock);
@@ -430,7 +439,7 @@ static int task_blocks_on_rt_mutex(struc
 		top_waiter = rt_mutex_top_waiter(lock);
 	plist_add(&waiter->list_entry, &lock->wait_list);
 
-	current->pi_blocked_on = waiter;
+	current->blocked_on = lock_waiter;
 
 	spin_unlock_irqrestore(&current->pi_lock, flags);
 
@@ -440,7 +449,7 @@ static int task_blocks_on_rt_mutex(struc
 		plist_add(&waiter->pi_list_entry, &owner->pi_waiters);
 
 		__rt_mutex_adjust_prio(owner);
-		if (owner->pi_blocked_on)
+		if (rt_mutex_get_waiter(owner))
 			chain_walk = 1;
 		spin_unlock_irqrestore(&owner->pi_lock, flags);
 	}
@@ -501,7 +510,7 @@ static void wakeup_next_waiter(struct rt
 	spin_unlock_irqrestore(&current->pi_lock, flags);
 
 	/*
-	 * Clear the pi_blocked_on variable and enqueue a possible
+	 * Clear the blocked_on variable and enqueue a possible
 	 * waiter into the pi_waiters list of the pending owner. This
 	 * prevents that in case the pending owner gets unboosted a
 	 * waiter with higher priority than pending-owner->normal_prio
@@ -509,11 +518,12 @@ static void wakeup_next_waiter(struct rt
 	 */
 	spin_lock_irqsave(&pendowner->pi_lock, flags);
 
-	WARN_ON(!pendowner->pi_blocked_on);
-	WARN_ON(pendowner->pi_blocked_on != waiter);
-	WARN_ON(pendowner->pi_blocked_on->lock != lock);
+	WARN_ON(!pendowner->blocked_on);
+	WARN_ON(pendowner->blocked_on->lock_type != RT_MUTEX_WAITER);
+	WARN_ON(pendowner->blocked_on->rt_blocked_on != waiter);
+	WARN_ON(pendowner->blocked_on->rt_blocked_on->lock != lock);
 
-	pendowner->pi_blocked_on = NULL;
+	pendowner->blocked_on = NULL;
 
 	if (rt_mutex_has_waiters(lock)) {
 		struct rt_mutex_waiter *next;
@@ -542,7 +552,7 @@ static void remove_waiter(struct rt_mute
 	spin_lock_irqsave(&current->pi_lock, flags);
 	plist_del(&waiter->list_entry, &lock->wait_list);
 	waiter->task = NULL;
-	current->pi_blocked_on = NULL;
+	current->blocked_on = NULL;
 	spin_unlock_irqrestore(&current->pi_lock, flags);
 
 	if (first && owner != current) {
@@ -559,7 +569,7 @@ static void remove_waiter(struct rt_mute
 		}
 		__rt_mutex_adjust_prio(owner);
 
-		if (owner->pi_blocked_on)
+		if (rt_mutex_get_waiter(owner))
 			chain_walk = 1;
 
 		spin_unlock_irqrestore(&owner->pi_lock, flags);
@@ -592,7 +602,7 @@ void rt_mutex_adjust_pi(struct task_stru
 
 	spin_lock_irqsave(&task->pi_lock, flags);
 
-	waiter = task->pi_blocked_on;
+	waiter = rt_mutex_get_waiter(task);
 	if (!waiter || waiter->list_entry.prio == task->prio) {
 		spin_unlock_irqrestore(&task->pi_lock, flags);
 		return;
@@ -614,6 +624,8 @@ rt_mutex_slowlock(struct rt_mutex *lock,
 		  int detect_deadlock)
 {
 	struct rt_mutex_waiter waiter;
+	struct lock_waiter_state lock_waiter = {
+		.lock_type = RT_MUTEX_WAITER, { .rt_blocked_on = &waiter} };
 	int ret = 0;
 
 	debug_rt_mutex_init_waiter(&waiter);
@@ -663,6 +675,7 @@ rt_mutex_slowlock(struct rt_mutex *lock,
 		 */
 		if (!waiter.task) {
 			ret = task_blocks_on_rt_mutex(lock, &waiter,
+						      &lock_waiter,
 						      detect_deadlock);
 			/*
 			 * If we got woken up by the owner then start loop
#4 lore raw

PATCH 5/6 -rt: nested rtmutex blocked_on

In reply to Daniel Walker

Fix the rare rare case that you might be inside another blocked_on user section and locking an rt-mutex. This can't happen in mainline, but can happen in -rt .

Allows nesting of the blocked on structures only for the rtmutex.

---
 include/linux/sched.h |    1 
 kernel/mutex.c        |    4 +--
 kernel/rtmutex.c      |   66 +++++++++++++++++++++++++++++++++++++++++---------
 3 files changed, 58 insertions(+), 13 deletions(-)
include/linux/sched.h +1 -0
Index: linux-2.6.25/include/linux/sched.h
===================================================================
@@ -1034,6 +1034,7 @@ struct lock_waiter_state {
 		struct mutex_waiter *mutex_blocked_on;
 		struct rt_mutex_waiter *rt_blocked_on;
 	};
+	struct lock_waiter_state *next;
 };
 
 struct task_struct {
kernel/mutex.c +2 -2
Index: linux-2.6.25/kernel/mutex.c
===================================================================
@@ -131,8 +131,8 @@ __mutex_lock_common(struct mutex *lock, 
 	unsigned int old_val;
 	unsigned long flags;
 #ifdef CONFIG_DEBUG_MUTEXES
-	struct lock_waiter_state lock_waiter = {
-		.lock_type = MUTEX_WAITER, { .mutex_blocked_on = &waiter} };
+	struct lock_waiter_state lock_waiter = { .lock_type = MUTEX_WAITER,
+		{ .mutex_blocked_on = &waiter}, .next = NULL };
 #endif
 
 	spin_lock_mutex(&lock->wait_lock, flags);
kernel/rtmutex.c +55 -11

99 lines not on this page · raw message

#5 lore raw

PATCH 6/6 futex: fix miss ordered wakeups

In reply to Daniel Walker

Adds an additional function call to the sched_setscheduler to update the waiter position of a task if it happens to be waiting on a futex. This ensures that the kernel level waiter ordering is correctly maintained based on the changed priority of the task.

I fixed the locking issue noticed by Thomas Gleixner.

This doesn't address userspace at all, only the kernel level wakeups and kernel level ordering.

The additional locking added to the futex_wait function has no visible speed impact, and only effects waiters which actual enter the kernel.

---
 include/linux/sched.h |   10 ++++++++--
 kernel/fork.c         |    3 ++-
 kernel/futex.c        |   45 +++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched.c        |    1 +
 4 files changed, 56 insertions(+), 3 deletions(-)
include/linux/sched.h +8 -2
Index: linux-2.6.25/include/linux/sched.h
===================================================================
@@ -1026,6 +1026,7 @@ struct sched_rt_entity {
 enum lock_waiter_type {
 	MUTEX_WAITER = 1,
 	RT_MUTEX_WAITER,
+	FUTEX_WAITER
 };
 
 struct lock_waiter_state {
@@ -1033,6 +1034,7 @@ struct lock_waiter_state {
 	union {
 		struct mutex_waiter *mutex_blocked_on;
 		struct rt_mutex_waiter *rt_blocked_on;
+		union futex_key	*futex_blocked_on;
 	};
 	struct lock_waiter_state *next;
 };
@@ -1222,7 +1224,8 @@ struct task_struct {
 	struct plist_head pi_waiters;
 #endif
 
-#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_RT_MUTEXES)
+#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_RT_MUTEXES) \
+	|| defined(CONFIG_FUTEX)
 	/*
 	 * Deadlock detection and priority inheritance handling,
 	 * and any other out of line mutex operations
@@ -1321,7 +1324,8 @@ struct task_struct {
 #endif
 };
 
-#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_RT_MUTEXES)
+#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_RT_MUTEXES) \
+	|| defined(CONFIG_FUTEX)
 /*
  * set_blocked_on - Set the blocked on field in the task struct.
  */
@@ -1680,6 +1684,8 @@ static inline int rt_mutex_getprio(struc
 # define rt_mutex_adjust_pi(p)		do { } while (0)
 #endif
 
+extern void futex_adjust_waiters(struct task_struct *p);
+
 extern void set_user_nice(struct task_struct *p, long nice);
 extern int task_prio(const struct task_struct *p);
 extern int task_nice(const struct task_struct *p);
kernel/fork.c +2 -1
Index: linux-2.6.25/kernel/fork.c
===================================================================
@@ -1027,7 +1027,8 @@ static struct task_struct *copy_process(
 	p->lockdep_recursion = 0;
 #endif
 
-#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_RT_MUTEXES)
+#if defined(CONFIG_DEBUG_MUTEXES) || defined(CONFIG_RT_MUTEXES) \
+	|| defined(CONFIG_FUTEX)
 	p->blocked_on = NULL; /* not blocked yet */
 #endif
 
kernel/futex.c +45 -0

81 lines not on this page · raw message

kernel/sched.c +1 -0
Index: linux-2.6.25/kernel/sched.c
===================================================================
@@ -4869,6 +4869,7 @@ recheck:
 	spin_unlock_irqrestore(&p->pi_lock, flags);
 
 	rt_mutex_adjust_pi(p);
+	futex_adjust_waiters(p);
 
 	return 0;
 }
maintainer
#6 lore raw

Re: [PATCH 6/6] futex: fix miss ordered wakeups

Quoted 6 lines · Daniel Walker

plain text document attachment (blocked_on-futex.patch)
Adds an additional function call to the sched_setscheduler to update the waiter position of a task if it happens to be waiting on a futex. This ensures that the kernel level waiter ordering is correctly maintained based on the changed priority of the task.

Quoted 7 lines

I fixed the locking issue noticed by Thomas Gleixner.

This doesn't address userspace at all, only the kernel level wakeups and kernel level ordering.

The additional locking added to the futex_wait function has no visible speed impact, and only effects waiters which actual enter the kernel.

Daniel, I'm not sure what to think,.. you were told how broken this approach was, you were told to give proper justification for this change. You did neither and just reposted the same old broken shite again.

Wake up.

(Just in case you missed it, that's a NAK)

#7 lore raw

Re: [PATCH 6/6] futex: fix miss ordered wakeups

Quoted 4 lines · Peter Zijlstra

Daniel, I'm not sure what to think,.. you were told how broken this approach was, you were told to give proper justification for this change. You did neither and just reposted the same old broken shite again.

Broken approach ? Never heard that before, in fact the problem is whether or not the changes are needed (not weather their broken).. I gave justification in the last thread, and I'm not sure why it's unclear to you..

Daniel

maintainer
#8 lore raw

Re: [PATCH 6/6] futex: fix miss ordered wakeups

Quoted 8 lines · Daniel Walker
Quoted 4 lines · Peter Zijlstra

Daniel, I'm not sure what to think,.. you were told how broken this approach was, you were told to give proper justification for this change. You did neither and just reposted the same old broken shite again.

Broken approach ? Never heard that before,

I suggest you re-read some of Thomas' emails from last time...

http://lkml.org/lkml/2008/6/12/275

Quoted 4 lines

in fact the problem is
whether or not the changes are needed (not weather their broken).. I gave justification in the last thread, and I'm not sure why it's unclear to you..

You failed to convince, also justification goes in the changelog, not in random lkml threads.

#9 lore raw

Re: [PATCH 6/6] futex: fix miss ordered wakeups

Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Daniel Walker
Quoted 4 lines · Peter Zijlstra

Daniel, I'm not sure what to think,.. you were told how broken this approach was, you were told to give proper justification for this change. You did neither and just reposted the same old broken shite again.

Quoted 5 lines
Quoted 1 line

Broken approach ? Never heard that before,

I suggest you re-read some of Thomas' emails from last time...

http://lkml.org/lkml/2008/6/12/275

Most of what he's saying there is that it breaks real time, and I provided a real time fix in this set of patches. I don't have a problem with the state mixing, since 99.9% of the time we're dealing operations that don't interact (and it's perfectly ok when they do interact).

Quoted 7 lines
Quoted 4 lines

in fact the problem is
whether or not the changes are needed (not weather their broken).. I gave justification in the last thread, and I'm not sure why it's unclear to you..

You failed to convince, also justification goes in the changelog, not in random lkml threads.

It boils down to POSIX compliance which was discussed in the last thread. POSIX requires the waiters to be sorts for 5-10 different API's which ultimately use the futex (most of which aren't at all related to PI).

And yes I can add it to the headers, before it goes up stream.

Daniel

maintainer
#10 lore raw

Re: [PATCH 6/6] futex: fix miss ordered wakeups

Quoted 11 lines · Daniel Walker
Quoted 10 lines · Peter Zijlstra
Quoted 8 lines · Daniel Walker
Quoted 4 lines · Peter Zijlstra

Daniel, I'm not sure what to think,.. you were told how broken this approach was, you were told to give proper justification for this change. You did neither and just reposted the same old broken shite again.

Broken approach ? Never heard that before,

Quoted 8 lines
Quoted 3 lines

I suggest you re-read some of Thomas' emails from last time...

http://lkml.org/lkml/2008/6/12/275

Most of what he's saying there is that it breaks real time, and I provided a real time fix in this set of patches. I don't have a problem with the state mixing, since 99.9% of the time we're dealing operations that don't interact (and it's perfectly ok when they do interact).

You're not the maintainer, and you fail to respect their opinion - so what makes you think your patches are going anywhere but /dev/null?

Also, the main point was about mixing user and kernel space state, you still do so by including the futex waiter in the same union. That's a fundamental fugly - no matter if you can make it work.

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

in fact the problem is
whether or not the changes are needed (not weather their broken).. I gave justification in the last thread, and I'm not sure why it's unclear to you..

Quoted 7 lines
Quoted 2 lines

You failed to convince, also justification goes in the changelog, not in random lkml threads.

It boils down to POSIX compliance which was discussed in the last thread. POSIX requires the waiters to be sorts for 5-10 different API's which ultimately use the futex (most of which aren't at all related to PI).

I'm unconvinced, my reading of the spec doesn't say that at all. It says its up to how things get scheduled.

Also, you have failed to say what real world use cases care about this behaviour. This was asked multiple times - you never answered any of those queries.

Quoted 1 line

And yes I can add it to the headers, before it goes up stream.

Don't bother, at this rate that will be never.

#11 lore raw

Re: [PATCH 6/6] futex: fix miss ordered wakeups

Quoted 2 lines · Peter Zijlstra

You're not the maintainer, and you fail to respect their opinion - so what makes you think your patches are going anywhere but /dev/null?

It may not be going anyplace. I'm not submitting it to anyone but LKML, at this point anyway.

Quoted 3 lines

Also, the main point was about mixing user and kernel space state, you still do so by including the futex waiter in the same union. That's a fundamental fugly - no matter if you can make it work.

I don't think it's ugly at all, but I'm open to suggestion for alternate methods of implementing it .. I don't need to unify the blocked_on structures, but it does allow for some nice things like reducing the size of the task struct, and potentially later doing PI across different API's.

Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
Quoted 4 lines

in fact the problem is
whether or not the changes are needed (not weather their broken).. I gave justification in the last thread, and I'm not sure why it's unclear to you..

You failed to convince, also justification goes in the changelog, not in random lkml threads.

Quoted 7 lines
Quoted 4 lines

It boils down to POSIX compliance which was discussed in the last thread. POSIX requires the waiters to be sorts for 5-10 different API's which ultimately use the futex (most of which aren't at all related to PI).

I'm unconvinced, my reading of the spec doesn't say that at all. It says its up to how things get scheduled.

Any way you read it there is an ordering that isn't random or FIFO or un-ordered, which is what we end up with now depending on the order the syscalls are used.

We already go to the trouble of sorting the waiters, which I think speaks for itself ..

Quoted 3 lines

Also, you have failed to say what real world use cases care about this behaviour. This was asked multiple times - you never answered any of those queries.

At this point it all seems academic .. We all know how the code works now, and the issue I'm addressing .. There's no crash associated with this ..

I don't have access to code where this causes a devastating problem, all I have is people asking me about the lack of determinism in this interface.

Daniel

#12 lore raw

Re: [PATCH 6/6] futex: fix miss ordered wakeups

Quoted 10 lines · Daniel Walker
Quoted 3 lines · Peter Zijlstra

Also, the main point was about mixing user and kernel space state, you still do so by including the futex waiter in the same union. That's a fundamental fugly - no matter if you can make it work.

I don't think it's ugly at all, but I'm open to suggestion for alternate methods of implementing it .. I don't need to unify the blocked_on structures, but it does allow for some nice things like reducing the size of the task struct, and potentially later doing PI across different API's.

Just get it. Mixing concurrency controls and futex waiters is fundamentally wrong. A task can be blocked on exactly one concurrency control, but it can be on a futex waiter _AND_ then block on a concurrency control.

Unifying the mutex and the rtmutex blocked_on is semantically correct and is a worthwhile thing to do, but adding the futex waiter to it is simply a semantical brain fart which can not be excused by reducing the size of task struct.

No thanks,

tglx

#13 lore raw

Re: [PATCH 6/6] futex: fix miss ordered wakeups

Quoted 4 lines · Thomas Gleixner

Unifying the mutex and the rtmutex blocked_on is semantically correct and is a worthwhile thing to do, but adding the futex waiter to it is simply a semantical brain fart which can not be excused by reducing the size of task struct.

I can unify just the rtmutex and the mutex, then add the futex waiter as another entity.

Daniel