delayed wakeup list

pièce jointe document texte brut (sched-wakeup-list.patch) Provide means to queue wakeup targets for later mass wakeup.

This is useful for locking primitives that can effect multiple wakeups per operation and want to avoid lock internal lock contention by delaying the wakeups until we've released the lock internal locks.

Alternatively it can be used to avoid issuing multiple wakeups, and thus save a few cycles, in packet processing. Queue all target tasks and wakeup once you've processed all packets. That way you avoid waking the target task multiple times if there were multiple packets for the same task.

Cc Thomas Gleixner <[email protected]>

Cc Darren Hart <[email protected]>

Cc Manfred Spraul <[email protected]>

Cc David Miller <[email protected]>

Cc Eric Dumazet <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

---
 include/linux/sched.h |   44 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched.c        |   21 +++++++++++++++++++++
 2 files changed, 65 insertions(+)

Index: linux-2.6/include/linux/sched.h
===================================================================

include/linux/sched.h +32 -0

@@ -1065,6 +1065,19 @@ struct uts_namespace;
 struct rq;
 struct sched_domain;
 
+struct wake_list_head {
+	struct wake_list_node *first;
+};
+
+struct wake_list_node {
+	struct wake_list_node *next;
+};
+
+#define WAKE_LIST_TAIL ((struct wake_list_node *)0x01)
+
+#define WAKE_LIST(name) \
+	struct wake_list_head name = { WAKE_LIST_TAIL }
+
 /*
  * wake flags
  */

@@ -1255,6 +1268,8 @@ struct task_struct {
 	unsigned int btrace_seq;
 #endif
 
+	struct wake_list_node wake_list;
+
 	unsigned int policy;
 	cpumask_t cpus_allowed;
 

@@ -2143,6 +2158,35 @@ extern void wake_up_new_task(struct task
 extern void sched_fork(struct task_struct *p);
 extern void sched_dead(struct task_struct *p);
 
+static inline void
+wake_list_add(struct wake_list_head *head, struct task_struct *p)
+{
+	struct wake_list_node *n = &p->wake_list;
+
+	get_task_struct(p);
+	/*
+	 * Atomically grab the task, if ->wake_list is !0 already it means
+	 * its already queued (either by us or someone else) and will get the
+	 * wakeup due to that.
+	 *
+	 * This cmpxchg() implies a full barrier, which pairs with the write
+	 * barrier implied by the wakeup in wake_up_list().
+	 */
+	if (cmpxchg(&n->next, 0, n) != 0) {
+		/* It was already queued, drop the extra ref and we're done. */
+		put_task_struct(p);

I dont understand why you make a get_task_struct() before the cmpxchg() and rollback. We certainly must hold a lock/mutex before calling wake_list_add()

It could be :

{
        if (cmpxchg(&n->next, NULL, head->first))
                return;
         
        get_task_struct(p);
        head->first = n;
} 

Provide means to queue wakeup targets for later mass wakeup.

This is useful for locking primitives that can effect multiple wakeups per operation and want to avoid lock internal lock contention by delaying the wakeups until we've released the lock internal locks.

Alternatively it can be used to avoid issuing multiple wakeups, and thus save a few cycles, in packet processing. Queue all target tasks and wakeup once you've processed all packets. That way you avoid waking the target task multiple times if there were multiple packets for the same task.

Cc Thomas Gleixner <[email protected]>

Cc Darren Hart <[email protected]>

Cc Manfred Spraul <[email protected]>

Cc David Miller <[email protected]>

Cc Eric Dumazet <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

---
 include/linux/sched.h |   44 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched.c        |   21 +++++++++++++++++++++
 2 files changed, 65 insertions(+)

Index: linux-2.6/include/linux/sched.h
===================================================================

include/linux/sched.h +44 -0

@@ -1065,6 +1065,19 @@ struct uts_namespace;
 struct rq;
 struct sched_domain;
 
+struct wake_list_head {
+	struct wake_list_node *first;
+};
+
+struct wake_list_node {
+	struct wake_list_node *next;
+};
+
+#define WAKE_LIST_TAIL ((struct wake_list_node *)0x01)
+
+#define WAKE_LIST(name) \
+	struct wake_list_head name = { WAKE_LIST_TAIL }
+
 /*
  * wake flags
  */

@@ -1255,6 +1268,8 @@ struct task_struct {
 	unsigned int btrace_seq;
 #endif
 
+	struct wake_list_node wake_list;
+
 	unsigned int policy;
 	cpumask_t cpus_allowed;
 

@@ -2143,6 +2158,35 @@ extern void wake_up_new_task(struct task
 extern void sched_fork(struct task_struct *p);
 extern void sched_dead(struct task_struct *p);
 
+static inline void
+wake_list_add(struct wake_list_head *head, struct task_struct *p)
+{
+	struct wake_list_node *n = &p->wake_list;
+
+	get_task_struct(p);
+	/*
+	 * Atomically grab the task, if ->wake_list is !0 already it means
+	 * its already queued (either by us or someone else) and will get the
+	 * wakeup due to that.
+	 *
+	 * This cmpxchg() implies a full barrier, which pairs with the write
+	 * barrier implied by the wakeup in wake_up_list().
+	 */
+	if (cmpxchg(&n->next, 0, n) != 0) {
+		/* It was already queued, drop the extra ref and we're done. */
+		put_task_struct(p);
+		return;
+	}
+
+	/*
+	 * The head is context local, there can be no concurrency.
+	 */
+	n->next = head->first;
+	head->first = n;
+}
+
+extern void wake_up_list(struct wake_list_head *head, unsigned int state);
+
 extern void proc_caches_init(void);
 extern void flush_signals(struct task_struct *);
 extern void __flush_signals(struct task_struct *);

Index: linux-2.6/kernel/sched.c
===================================================================

kernel/sched.c +21 -0

+void wake_up_list(struct wake_list_head *head, unsigned int state)
+{
+	struct wake_list_node *n = head->first;
+	struct task_struct *p;
+
+	while (n != WAKE_LIST_TAIL) {
+		p = container_of(n, struct task_struct, wake_list);
+		n = n->next;
+
+		p->wake_list.next = NULL;
+		/*
+		 * wake_up_state() implies a wmb() to pair with the queueing
+		 * in wake_list_add() so as not to miss wakeups.
+		 */
+		wake_up_state(p, state);
+		put_task_struct(p);
+	}
+}
+
 /*
  * Perform scheduler related setup for a newly forked process p.
  * p is forked by current.

@@ -2943,6 +2962,8 @@ static void __sched_fork(struct task_str
 #ifdef CONFIG_PREEMPT_NOTIFIERS
 	INIT_HLIST_HEAD(&p->preempt_notifiers);
 #endif
+
+	p->wake_list.next = NULL;
 }
 
 /*

Missing here is what the value of state should be when calling wake_up_list.

Quoted 2 lines · Darren Hart

Missing here is what the value of state should be when calling wake_up_list.

Depends on what all you want to wake up :-) Would a reference to the comment of try_to_wake_up() be good enough?

It's probably worth folding the idle_cpu fix for checking whether there's an enqueued task into this.

include/linux/sched.h +10 -0

@@ -2143,6 +2158,35 @@ extern void wake_up_new_task(struct task
  extern void sched_fork(struct task_struct *p);
  extern void sched_dead(struct task_struct *p);
 
+static inline void
+wake_list_add(struct wake_list_head *head, struct task_struct *p)
+{
+	struct wake_list_node *n =&p->wake_list;
+
+	get_task_struct(p);
+	/*
+	 * Atomically grab the task, if ->wake_list is !0 already it means
+	 * its already queued (either by us or someone else) and will get the
+	 * wakeup due to that.

include/linux/sched.h +9 -0

+	/*
+	 * The head is context local, there can be no concurrency.
+	 */
+	n->next = head->first;
+	head->first = n;
+}
+
+extern void wake_up_list(struct wake_list_head *head, unsigned int state);
+
  extern void proc_caches_init(void);
  extern void flush_signals(struct task_struct *);
  extern void __flush_signals(struct task_struct *);

Index: linux-2.6/kernel/sched.c
===================================================================

kernel/sched.c +8 -0

@@ -2916,6 +2916,25 @@ int wake_up_state(struct task_struct *p,
  	return try_to_wake_up(p, state, 0);
  }
 
+void wake_up_list(struct wake_list_head *head, unsigned int state)
+{
+	struct wake_list_node *n = head->first;
+	struct task_struct *p;
+
+	while (n != WAKE_LIST_TAIL) {
+		p = container_of(n, struct task_struct, wake_list);
+		n = n->next;

Do you still work on the wake_up_list() patch?

Use the brand spanking new wake_list to delay the futex wakeups until after we've released the hash bucket locks. This avoids the newly woken tasks from immediately getting stuck on the hb lock.

This is esp. painful on -rt, where the hb lock is preemptible.

Cc Thomas Gleixner <[email protected]>

Cc Darren Hart <[email protected]>

Signed-off-by Peter Zijlstra <[email protected]>

---
 kernel/futex.c |   23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

Index: linux-2.6/kernel/futex.c
===================================================================

kernel/futex.c +2 -4

 {
 	struct task_struct *p = q->task;
 

@@ -834,7 +834,7 @@ static void wake_futex(struct futex_q *q
 	 * struct. Prevent this by holding a reference on p across the
 	 * wake up.
 	 */
-	get_task_struct(p);
+	wake_list_add(wake_list, p);
 
 	__unqueue_futex(q);
 	/*

@@ -845,9 +845,6 @@ static void wake_futex(struct futex_q *q
 	 */
 	smp_wmb();
 	q->lock_ptr = NULL;
-
-	wake_up_state(p, TASK_NORMAL);
-	put_task_struct(p);
 }
 
 static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this)

@@ -964,6 +961,7 @@ futex_wake(u32 __user *uaddr, unsigned i
 	struct futex_q *this, *next;
 	struct plist_head *head;
 	union futex_key key = FUTEX_KEY_INIT;
+	WAKE_LIST(wake_list);
 	int ret;
 
 	if (!bitset)

kernel/futex.c +9 -3

 			if (++ret >= nr_wake)
 				break;
 		}

@@ -996,6 +994,8 @@ futex_wake(u32 __user *uaddr, unsigned i
 
 	spin_unlock(&hb->lock);
 	put_futex_key(&key);
+
+	wake_up_list(&wake_list, TASK_NORMAL);
 out:
 	return ret;
 }

@@ -1012,6 +1012,7 @@ futex_wake_op(u32 __user *uaddr1, unsign
 	struct futex_hash_bucket *hb1, *hb2;
 	struct plist_head *head;
 	struct futex_q *this, *next;
+	WAKE_LIST(wake_list);
 	int ret, op_ret;
 
 retry:

@@ -1062,7 +1063,7 @@ futex_wake_op(u32 __user *uaddr1, unsign
 
 	plist_for_each_entry_safe(this, next, head, list) {
 		if (match_futex (&this->key, &key1)) {
-			wake_futex(this);
+			wake_futex(&wake_list, this);
 			if (++ret >= nr_wake)
 				break;
 		}

@@ -1074,7 +1075,7 @@ futex_wake_op(u32 __user *uaddr1, unsign
 		op_ret = 0;
 		plist_for_each_entry_safe(this, next, head, list) {
 			if (match_futex (&this->key, &key2)) {
-				wake_futex(this);
+				wake_futex(&wake_list, this);
 				if (++op_ret >= nr_wake2)
 					break;
 			}

@@ -1087,6 +1088,8 @@ futex_wake_op(u32 __user *uaddr1, unsign
 	put_futex_key(&key2);
 out_put_key1:
 	put_futex_key(&key1);
+
+	wake_up_list(&wake_list, TASK_NORMAL);
 out:
 	return ret;
 }

@@ -1239,6 +1242,7 @@ static int futex_requeue(u32 __user *uad
 	struct futex_hash_bucket *hb1, *hb2;
 	struct plist_head *head1;
 	struct futex_q *this, *next;
+	WAKE_LIST(wake_list);
 	u32 curval2;
 
 	if (requeue_pi) {

@@ -1384,7 +1388,7 @@ static int futex_requeue(u32 __user *uad
 		 * woken by futex_unlock_pi().
 		 */
 		if (++task_count <= nr_wake && !requeue_pi) {
-			wake_futex(this);
+			wake_futex(&wake_list, this);
 			continue;
 		}
 

Quoted 4 lines · Peter Zijlstra

Use the brand spanking new wake_list to delay the futex wakeups until after we've released the hash bucket locks. This avoids the newly woken tasks from immediately getting stuck on the hb lock.

Quoted 1 line

This is esp. painful on -rt, where the hb lock is preemptible.

Nice!

Have you run this through the functional and performance tests from futextest? Looks like I should also add a multiwake test to really showcase this.

If you don't have it local I can setup a github repository for futextest until korg is back.... or do the testing myself... right.

kernel/futex.c futex_wake(u32 __user *uaddr, unsigned i · line 989

Quoted 6 lines

kernel/futex.c +1 -1

@@ -988,7 +986,7 @@ futex_wake(u32 __user *uaddr, unsigned i
 			if (!(this->bitset & bitset))
 				continue;
 
-			wake_futex(this);
+			wake_futex(&wake_list, this);

I guess this is OK. wake_futex_pi will always be one task I believe, so the list syntax might confuse newcomers... Would it make sense to have a wake_futex_list() call? Thinking outloud...

Quoted 6 lines

kernel/futex.c +1 -0

@@ -1437,6 +1441,7 @@ static int futex_requeue(u32 __user *uad
 	put_futex_key(&key2);
 out_put_key1:
 	put_futex_key(&key1);
+	wake_up_list(&wake_list, TASK_NORMAL);
 out:

kernel/futex.c static int futex_requeue(u32 __user *uad · line 1447

Quoted 4 lines

kernel/futex.c +0 -0

 	if (pi_state != NULL)
 		free_pi_state(pi_state);

I _think_ requeue_pi is in the clear here as it uses requeue_pi_wake_futex, which calls wake_up_state directly. Still, some testing with futextest functional/futex_requeue_pi is in order.

Quoted 6 lines · Darren Hart

Quoted 4 lines · Peter Zijlstra

Use the brand spanking new wake_list to delay the futex wakeups until after we've released the hash bucket locks. This avoids the newly woken tasks from immediately getting stuck on the hb lock.

Quoted 7 lines

Quoted 1 line

This is esp. painful on -rt, where the hb lock is preemptible.

Nice!

Have you run this through the functional and performance tests from futextest? Looks like I should also add a multiwake test to really showcase this.

Not more functional than booting, but a very similar patch used to live in 33-rt.. I lost the use-case we had that led to that patch, for -rt it made a huge difference because we endlessly scheduled back and forth between the waker and the wakee bouncing on the hb lock.

Quoted 2 lines

If you don't have it local I can setup a github repository for futextest until korg is back.... or do the testing myself... right.

Right, I don't think I have futextest, or I might, I'd have to dig around a bit.

Quoted 5 lines

Quoted 5 lines

kernel/futex.c +0 -0

@@ -988,7 +986,7 @@ futex_wake(u32 __user *uaddr, unsigned i
 			if (!(this->bitset & bitset))
 				continue;
 

Quoted 7 lines

Review futex_wake(u32 __user *uaddr, unsigned i · line 989

Quoted 2 lines

(quoted diff) +1 -1

-			wake_futex(this);
+			wake_futex(&wake_list, this);

I guess this is OK. wake_futex_pi will always be one task I believe, so the list syntax might confuse newcomers... Would it make sense to have a wake_futex_list() call? Thinking outloud...

To what purpose? Even delaying a single wakeup until after we release the hb lock is useful. On it matters even on !-rt since the woken task can wake on another cpu and then spin on hb-lock.

Quoted 15 lines

kernel/futex.c static int futex_requeue(u32 __user *uad · line 1447

Quoted 11 lines

kernel/futex.c +1 -0

@@ -1437,6 +1441,7 @@ static int futex_requeue(u32 __user *uad
 	put_futex_key(&key2);
 out_put_key1:
 	put_futex_key(&key1);
+	wake_up_list(&wake_list, TASK_NORMAL);
 out:
 	if (pi_state != NULL)
 		free_pi_state(pi_state);

I _think_ requeue_pi is in the clear here as it uses requeue_pi_wake_futex, which calls wake_up_state directly. Still, some testing with futextest functional/futex_requeue_pi is in order.

Ah, right, that might want frobbing too..

Quoted 10 lines · Darren Hart

Quoted 5 lines · Peter Zijlstra

Use the brand spanking new wake_list to delay the futex wakeups until after we've released the hash bucket locks. This avoids the newly woken tasks from immediately getting stuck on the hb lock.

This is esp. painful on -rt, where the hb lock is preemptible.

Nice!

Quoted 3 lines

Have you run this through the functional and performance tests from futextest? Looks like I should also add a multiwake test to really showcase this.

Not more functional than booting, but a very similar patch used to live in 33-rt.. I lost the use-case we had that led to that patch, for -rt it made a huge difference because we endlessly scheduled back and forth between the waker and the wakee bouncing on the hb lock.

kernel/futex.c +2 -1

@@ -964,6 +961,7 @@ futex_wake(u32 __user *uaddr, unsigned i
        struct futex_q *this, *next;
        struct plist_head *head;
        union futex_key key = FUTEX_KEY_INIT;
+       WAKE_LIST(wake_list);
        int ret;
 
        if (!bitset)

@@ -988,7 +986,7 @@ futex_wake(u32 __user *uaddr, unsigned i
                        if (!(this->bitset & bitset))
                                continue;
 
-                       wake_futex(this);
+                       wake_futex(&wake_list, this);
                        if (++ret >= nr_wake)
                                break;
                }

So while initially I thought the sem patch was busted, it turns out this one is.

Thomas managed to spot the race:

   Task-0			Task-1

futex_wait()
queue_me()

				futex_wake()
				  wake_list_add();
				  __unqueue_futex();
				    plist_del();

if (!plist_node_empty())
__set_current_state(TASK_RUNNNIG);

				  wake_up_list();
				    /* waking an already running task-0 */

I guess the biggest question is, do we care? Ideally everything should be able to deal with spurious wakeups, although we generally try to avoid them.

How do we verify that everything is able to deal with spurious wakeups?

Quoted 3 lines · Manfred Spraul

How do we verify that everything is able to deal with spurious wakeups?

Well, I could go audit all 1400+ *schedule*() callsites in the kernel. Or we can rely on the fact that current code can already cause spurious wakeups due to signals.

This removes the home-brew busy-wait and the requirement to keep preemption disabled.

Patch 3 converts sysv sems, and is broken

/**
* newary - Create a new semaphore set

ipc/sem.c +4 -11

@@ -406,51 +388,39 @@ static int try_atomic_semop (struct sem_
  	return result;
  }
 
-/** wake_up_sem_queue_prepare(q, error): Prepare wake-up
+/** wake_up_sem_queue_prepare(wake_list, q, error): Prepare wake-up
+ * @wake_list: list to queue the to be woken task on
   * @q: queue entry that must be signaled
   * @error: Error value for the signal
   *
   * Prepare the wake-up of the queue entry q.
   */
-static void wake_up_sem_queue_prepare(struct list_head *pt,
+static void wake_up_sem_queue_prepare(struct wake_list_head *wake_list,
  				struct sem_queue *q, int error)
  {
-	if (list_empty(pt)) {
-		/*
-		 * Hold preempt off so that we don't get preempted and have the
-		 * wakee busy-wait until we're scheduled back on.
-		 */
-		preempt_disable();
-	}
-	q->status = IN_WAKEUP;
-	q->pid = error;
+	struct task_struct *p = ACCESS_ONCE(q->sleeper);

ipc/sem.c +3 -8

  /**
- * wake_up_sem_queue_do(pt) - do the actual wake-up
- * @pt: list of tasks to be woken up
+ * wake_up_sem_queue_do(wake_list) - do the actual wake-up
+ * @wake_list: list of tasks to be woken up
   *
   * Do the actual wake-up.
   * The function is called without any locks held, thus the semaphore array
   * could be destroyed already and the tasks can disappear as soon as the
   * status is set to the actual return code.
   */
-static void wake_up_sem_queue_do(struct list_head *pt)
+static void wake_up_sem_queue_do(struct wake_list_head *wake_list)
  {
-	struct sem_queue *q, *t;
-	int did_something;
-
-	did_something = !list_empty(pt);
-	list_for_each_entry_safe(q, t, pt, simple_list) {

Hi Peter,

What is broken?

Quoted 5 lines

ipc/sem.c +2 -0

+static void wake_up_sem_queue_prepare(struct wake_list_head *wake_list,
  				struct sem_queue *q, int error)
  {
+	struct task_struct *p = ACCESS_ONCE(q->sleeper);

ipc/sem.c static int try_atomic_semop (struct sem_ · line 410

Quoted 8 lines

ipc/sem.c +7 -0

+	get_task_struct(p);
+	q->status = error;
+	/*
+	 * implies a full barrier
+	 */
+	wake_list_add(wake_list, p);
+	put_task_struct(p);
  }

I think the get_task_struct()/put_task_struct is not necessary:
Just do the wake_list_add() before writing q->status:
wake_list_add() is identical to list_add_tail(&q->simple_list, pt). [except that it contains additional locking, which doesn't matter here]

ipc/sem.c static int try_atomic_semop (struct sem_ · line 424

Quoted 5 lines

ipc/sem.c +2 -0

+static void wake_up_sem_queue_do(struct wake_list_head *wake_list)
  {
+	wake_up_list(wake_list, TASK_ALL);
  }

wake_up_list() calls wake_up_state() that calls try_to_wake_up(). try_to_wake_up() seems to return immediately when the state is TASK_DEAD.

That leaves: Is it safe to call wake_up_list() in parallel with do_exit()? The current implementation avoids that.

Quoted 13 lines

Quoted 13 lines

ipc/sem.c +9 -0

+static void wake_up_sem_queue_prepare(struct wake_list_head *wake_list,
                            struct sem_queue *q, int error)
  {
+   struct task_struct *p = ACCESS_ONCE(q->sleeper);
 
+   get_task_struct(p);
+   q->status = error;
+   /*
+    * implies a full barrier
+    */
+   wake_list_add(wake_list, p);
+   put_task_struct(p);
  }

Quoted 4 lines

I think the get_task_struct()/put_task_struct is not necessary:
Just do the wake_list_add() before writing q->status:
wake_list_add() is identical to list_add_tail(&q->simple_list, pt). [except that it contains additional locking, which doesn't matter here]

Quoted 14 lines · Peter Zijlstra

Quoted 13 lines

Quoted 13 lines

ipc/sem.c +9 -0

+static void wake_up_sem_queue_prepare(struct wake_list_head *wake_list,
                            struct sem_queue *q, int error)
  {
+   struct task_struct *p = ACCESS_ONCE(q->sleeper);
 
+   get_task_struct(p);
+   q->status = error;
+   /*
+    * implies a full barrier
+    */
+   wake_list_add(wake_list, p);
+   put_task_struct(p);
  }

Quoted 4 lines

Quoted 4 lines

I think the get_task_struct()/put_task_struct is not necessary:
Just do the wake_list_add() before writing q->status:
wake_list_add() is identical to list_add_tail(&q->simple_list, pt). [except that it contains additional locking, which doesn't matter here]

OK, I can't read properly.. so the problem with doing the wake_list_add() before the write is that the wakeup can actually happen before the write in case p already had a wakeup queued.

Quoted 18 lines · Peter Zijlstra

Quoted 17 lines · Peter Zijlstra

Quoted 17 lines

ipc/sem.c static int try_atomic_semop (struct sem_ · line 410

Quoted 13 lines

ipc/sem.c +9 -0

+static void wake_up_sem_queue_prepare(struct wake_list_head *wake_list,
                             struct sem_queue *q, int error)
   {
+   struct task_struct *p = ACCESS_ONCE(q->sleeper);
 
+   get_task_struct(p);
+   q->status = error;
+   /*
+    * implies a full barrier
+    */
+   wake_list_add(wake_list, p);
+   put_task_struct(p);
   }

I think the get_task_struct()/put_task_struct is not necessary:
Just do the wake_list_add() before writing q->status:
wake_list_add() is identical to list_add_tail(&q->simple_list, pt). [except that it contains additional locking, which doesn't matter here]

Quoted 3 lines

OK, I can't read properly.. so the problem with doing the wake_list_add() before the write is that the wakeup can actually happen before the write in case p already had a wakeup queued.

Ah, but if the wakeup happens early, we return from schedule with -EINTR and re-acquire the sem_lock and re-test. Since we do this update from under sem_lock it should serialize and come out all-right,.. right?

What is broken?

Quoted 1 line · Manfred Spraul

What is broken?

So basically sembench was broken and the futex patch is causing spurious wakeups.

I've got the below patch to fix up the sem code.

One more question, do the sem wakeups need to be issued in FIFO order? There's a comment in there:

* User space visible behavior:
* - FIFO ordering for semop() operations (just FIFO, not starvation
* protection)

that seems to suggest the sem ops processing is in FIFO order, but does the user visible effect propagate to the wakeup order?

Currently the wake-list is a FILO, although making it FIFO isn't really hard (in fact, I've got the patch).

This patch-set provides the infrastructure to delay/batch task wakeups.

This is useful for locking primitives that can effect multiple wakeups per operation and want to avoid lock internal lock contention by delaying the wakeups until we've released the lock internal locks.

Patch 2 converts futexes
Patch 3 converts sysv sems, and is broken

[ I've been staring at patch 3 way too long, so I thought I'd post it just
to get a few more eyes on it.. ]

Alternatively it can be used to avoid issuing multiple wakeups, and thus save a few cycles, in packet processing. Queue all target tasks and wakeup once you've processed all packets. That way you avoid waking the target task multiple times if there were multiple packets for the same task.

No actual such usage yet, but ISTR talking to some net folks a long while back about this, is there still interest, Dave, Eric?

Quoted 11 lines · Peter Zijlstra

This patch-set provides the infrastructure to delay/batch task wakeups.

Alternatively it can be used to avoid issuing multiple wakeups, and thus save a few cycles, in packet processing. Queue all target tasks and wakeup once you've processed all packets. That way you avoid waking the target task multiple times if there were multiple packets for the same task.

No actual such usage yet, but ISTR talking to some net folks a long while back about this, is there still interest, Dave, Eric?

Yes, I remember playing with such idea some years ago, to speedup multicast processing.

Say you have 10 receivers on a multicast group, each incoming message actually wakeups 10 threads.

If we receive a burst of 10 messages, we spend a lot of time in scheduler.

So adding one queue to batch all scheduler works (and factorize some work if the same thread is queued), and perform the scheduler calls at the end of software IRQ for example was a win.