futex: hashbucket as list of futex instead of waiters

RFC In review Gerd Gerats 3 participants 5 messages Sep 10, 2017 – Sep 29, 2017

Share & tools

Gerd Gerats

author

2017-09-10 21:42 UTC #0 lore raw

RFC 1/1 futex: hashbucket as list of futex instead of waiters

When using futex as a condition variable, for example: to manage a threadpool, there may be a lot of threads inside the futex_wait to sleep on this futex. The futex_hash_bucket consists therefore of many struct futex_q for the same futex.

On bad luck another futex, used as mutex, hashed into the same bucket. Every futex_wake on this mutex, has to scan the whole chain of above waiter to find the struct futex_q for this mutex. For non-unusual threadpool sizes of more than 20, this should be a considerable effort.

I therefore suggest to include in the hash-bucketchain only one struct futex_q per futex and to queue additional waiter in an extrachain at the 'top' futex_q entry. Thus different futex are isolated from each other, the cost of a hash collision is reduced.

To show the idea, I added a sample patch. Here, the plist is exchanged for a futex-specific implementation. kernel/pring.h is certainly not not the right place.

Signed-off-by Gerd Gerats <[email protected]>

---
 kernel/futex.c | 159 +++++++++++++++++++++++++++++++++++++++------------------
 kernel/pring.h | 110 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 219 insertions(+), 50 deletions(-)
 create mode 100644 kernel/pring.h

kernel/futex.c +109 ~~-50~~

index 357348a6cf6b..5598c4b1ad96 100644
@@ -72,6 +72,8 @@
 
 #include "locking/rtmutex_common.h"
 
+#include "pring.h"
+
 /*
  * READ this before attempting to hack on futexes!
  *

@@ -229,7 +231,7 @@ struct futex_pi_state {
  * we can wake only the relevant ones (hashed queues may be shared).
  *
  * A futex_q has a woken state, just like tasks have TASK_RUNNING.
- * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
+ * It is considered woken when futexq_lists_empty(&q) || q->lock_ptr == 0.
  * The order of wakeup is always to make the first condition true, then
  * the second.
  *

@@ -237,7 +239,8 @@ struct futex_pi_state {
  * the rt_mutex code. See unqueue_me_pi().
  */
 struct futex_q {
-	struct plist_node list;
+	struct list_head  list;
+	struct pring_node ring;
 
 	struct task_struct *task;
 	spinlock_t *lock_ptr;

@@ -262,7 +265,7 @@ static const struct futex_q futex_q_init = {
 struct futex_hash_bucket {
 	atomic_t waiters;
 	spinlock_t lock;
-	struct plist_head chain;
+	struct list_head chain;
 } ____cacheline_aligned_in_smp;
 
 /*

@@ -745,13 +748,78 @@ static struct futex_q *futex_top_waiter(struct futex_hash_bucket *hb,
 {
 	struct futex_q *this;
 
-	plist_for_each_entry(this, &hb->chain, list) {
+	list_for_each_entry(this, &hb->chain, list) {
 		if (match_futex(&this->key, key))
 			return this;
 	}
 	return NULL;
 }
 
+/**
+ * futexq_init() - initialize futex_q chain fields
+ * @q           The futex_q to initialize
+ * @prio:	priority
+ */
+static void futexq_init(struct futex_q *q, int prio)
+{
+	INIT_LIST_HEAD(&q->list);
+	pring_init(&q->ring, prio);
+}
+
+/**
+ * futexq_add() - Enqueue the futex_q on the futex_hash_bucket
+ * @q:	The futex_q to enqueue
+ * @hb:	The destination hash bucket
+ */
+static void futexq_add(struct futex_q *q, struct futex_hash_bucket *hb)
+{
+	struct futex_q *top;
+
+	top = futex_top_waiter(hb, &q->key);
+	if (top) {
+		if (pring_add(&q->ring, &top->ring) == &q->ring)
+			list_replace_init(&top->list, &q->list);
+	} else {
+		list_add_tail(&q->list, &hb->chain);
+	}
+}
+
+/**
+ * futexq_del() - Remove the futex_q from its futex_hash_bucket
+ * @q:	The futex_q to unqueue
+ * @hb:	hash bucket to remove from
+ */
+static void futexq_del(struct futex_q *q, struct futex_hash_bucket *hb)
+{
+	struct futex_q *next;
+
+	if (pring_is_singular(&q->ring)) {
+		list_del_init(&q->list);
+	} else {
+		next = pring_next_entry(q, ring);
+		if (!list_empty(&q->list))
+			list_replace_init(&q->list, &next->list);
+		pring_del(&q->ring);
+	}
+}
+
+static inline bool futexq_lists_empty(struct futex_q *q)
+{
+	return list_empty(&q->list) && pring_is_singular(&q->ring);
+}
+
+static inline struct futex_q *futexq_next_or_null(struct futex_q *q)
+{
+	struct futex_q *next = pring_next_entry(q, ring);
+
+	return list_empty(&next->list) ? next : 0;
+}
+
+#define futex_for_each_match_safe(pos, n, hb, key) \
+	for (pos = futex_top_waiter(hb, key); \
+		pos && ({ n = futexq_next_or_null(pos); 1; }); \
+		pos = n)
+
 static int cmpxchg_futex_value_locked(u32 *curval, u32 __user *uaddr,
 				      u32 uval, u32 newval)
 {

@@ -1352,11 +1420,11 @@ static void __unqueue_futex(struct futex_q *q)
 	struct futex_hash_bucket *hb;
 
 	if (WARN_ON_SMP(!q->lock_ptr || !spin_is_locked(q->lock_ptr))
-	    || WARN_ON(plist_node_empty(&q->list)))
+	    || WARN_ON(futexq_lists_empty(q)))
 		return;
 
 	hb = container_of(q->lock_ptr, struct futex_hash_bucket, lock);
-	plist_del(&q->list, &hb->chain);
+	futexq_del(q, hb);
 	hb_waiters_dec(hb);
 }

@@ -1384,7 +1452,7 @@ static void mark_wake_futex(struct wake_q_head *wake_q, struct futex_q *q)
 	 * is written, without taking any locks. This is possible in the event
 	 * of a spurious wakeup, for example. A memory barrier is required here
 	 * to prevent the following store to lock_ptr from getting ahead of the
-	 * plist_del in __unqueue_futex().
+	 * futexq_del/pring_del in __unqueue_futex().
 	 */
 	smp_store_release(&q->lock_ptr, NULL);
 }

@@ -1521,21 +1589,19 @@ futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)
 
 	spin_lock(&hb->lock);
 
-	plist_for_each_entry_safe(this, next, &hb->chain, list) {
-		if (match_futex (&this->key, &key)) {
-			if (this->pi_state || this->rt_waiter) {
-				ret = -EINVAL;
-				break;
-			}
+	futex_for_each_match_safe(this, next, hb, &key) {
+		if (this->pi_state || this->rt_waiter) {
+			ret = -EINVAL;
+			break;
+		}
 
-			/* Check if one of the bits is set in both bitsets */
-			if (!(this->bitset & bitset))
-				continue;
+		/* Check if one of the bits is set in both bitsets */
+		if (!(this->bitset & bitset))
+			continue;
 
-			mark_wake_futex(&wake_q, this);
-			if (++ret >= nr_wake)
-				break;
-		}
+		mark_wake_futex(&wake_q, this);
+		if (++ret >= nr_wake)
+			break;
 	}
 
 	spin_unlock(&hb->lock);

@@ -1604,30 +1670,26 @@ futex_wake_op(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2,
 		goto retry;
 	}
 
-	plist_for_each_entry_safe(this, next, &hb1->chain, list) {
-		if (match_futex (&this->key, &key1)) {
-			if (this->pi_state || this->rt_waiter) {
-				ret = -EINVAL;
-				goto out_unlock;
-			}
-			mark_wake_futex(&wake_q, this);
-			if (++ret >= nr_wake)
-				break;
+	futex_for_each_match_safe(this, next, hb1, &key1) {
+		if (this->pi_state || this->rt_waiter) {
+			ret = -EINVAL;
+			goto out_unlock;
 		}
+		mark_wake_futex(&wake_q, this);
+		if (++ret >= nr_wake)
+			break;
 	}
 
 	if (op_ret > 0) {
 		op_ret = 0;
-		plist_for_each_entry_safe(this, next, &hb2->chain, list) {
-			if (match_futex (&this->key, &key2)) {
-				if (this->pi_state || this->rt_waiter) {
-					ret = -EINVAL;
-					goto out_unlock;
-				}
-				mark_wake_futex(&wake_q, this);
-				if (++op_ret >= nr_wake2)
-					break;
+		futex_for_each_match_safe(this, next, hb2, &key2) {
+			if (this->pi_state || this->rt_waiter) {
+				ret = -EINVAL;
+				goto out_unlock;
 			}
+			mark_wake_futex(&wake_q, this);
+			if (++op_ret >= nr_wake2)
+				break;
 		}
 		ret += op_ret;
 	}

@@ -1656,18 +1718,18 @@ void requeue_futex(struct futex_q *q, struct futex_hash_bucket *hb1,
 {
 
 	/*
-	 * If key1 and key2 hash to the same bucket, no need to
+	 * If key1 and key2 hash to the same bucket, we still need to
 	 * requeue.
 	 */
+	futexq_del(q, hb1);
 	if (likely(&hb1->chain != &hb2->chain)) {
-		plist_del(&q->list, &hb1->chain);
 		hb_waiters_dec(hb1);
 		hb_waiters_inc(hb2);
-		plist_add(&q->list, &hb2->chain);
 		q->lock_ptr = &hb2->lock;
 	}
 	get_futex_key_refs(key2);
 	q->key = *key2;
+	futexq_add(q, hb2);
 }
 
 /**

@@ -1949,13 +2011,10 @@ static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
 		}
 	}
 
-	plist_for_each_entry_safe(this, next, &hb1->chain, list) {
+	futex_for_each_match_safe(this, next, hb1, &key1) {
 		if (task_count - nr_wake >= nr_requeue)
 			break;
 
-		if (!match_futex(&this->key, &key1))
-			continue;
-
 		/*
 		 * FUTEX_WAIT_REQEUE_PI and FUTEX_CMP_REQUEUE_PI should always
 		 * be paired with each other and no other futex ops.

@@ -2110,8 +2169,8 @@ static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
 	 */
 	prio = min(current->normal_prio, MAX_RT_PRIO);
 
-	plist_node_init(&q->list, prio);
-	plist_add(&q->list, &hb->chain);
+	futexq_init(q, prio);
+	futexq_add(q, hb);
 	q->task = current;
 }

@@ -2396,7 +2455,7 @@ static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
 	 * If we have been removed from the hash list, then another task
 	 * has tried to wake us, and we can skip the call to schedule().
 	 */
-	if (likely(!plist_node_empty(&q->list))) {
+	if (likely(!futexq_lists_empty(q))) {
 		/*
 		 * If the timer has already expired, current will already be
 		 * flagged for rescheduling. Only call schedule if there

@@ -2918,7 +2977,7 @@ int handle_early_requeue_pi_wakeup(struct futex_hash_bucket *hb,
 		 * We were woken prior to requeue by a timeout or a signal.
 		 * Unqueue the futex_q and determine which it was.
 		 */
-		plist_del(&q->list, &hb->chain);
+		futexq_del(q, hb);
 		hb_waiters_dec(hb);
 
 		/* Handle spurious wakeups gracefully */

@@ -3495,7 +3554,7 @@ static int __init futex_init(void)
 
 	for (i = 0; i < futex_hashsize; i++) {
 		atomic_set(&futex_queues[i].waiters, 0);
-		plist_head_init(&futex_queues[i].chain);
+		INIT_LIST_HEAD(&futex_queues[i].chain);
 		spin_lock_init(&futex_queues[i].lock);
 	}

kernel/pring.h new file +110 -0

110 lines not on this page · raw message

Signature · 1 line

2.14.1

Peter Zijlstra

2017-09-28 10:58 UTC #1 lore raw

Quoted 10 lines · Gerd Gerats

When using futex as a condition variable, for example: to manage a threadpool, there may be a lot of threads inside the futex_wait to sleep on this futex. The futex_hash_bucket consists therefore of many struct futex_q for the same futex.
On bad luck another futex, used as mutex, hashed into the same bucket. Every futex_wake on this mutex, has to scan the whole chain of above waiter to find the struct futex_q for this mutex. For non-unusual threadpool sizes of more than 20, this should be a considerable effort.

Quoted 4 lines

I therefore suggest to include in the hash-bucketchain only one struct futex_q per futex and to queue additional waiter in an extrachain at the 'top' futex_q entry. Thus different futex are isolated from each other, the cost of a hash collision is reduced.

So I don't dislike that idea.. however

Quoted 3 lines

To show the idea, I added a sample patch. Here, the plist is exchanged for a futex-specific implementation. kernel/pring.h is certainly not not the right place.

So I suppose the purpose of that plist in futex is to enable waking up the highest prio waiter, but with the advent of SCHED_DEADLINE that no longer works.

I think Thomas resisted going the RB-tree route earlier..

Thomas Gleixner

2017-09-28 12:14 UTC #2 lore raw

Quoted 22 lines · Peter Zijlstra

Quoted 10 lines · Gerd Gerats
When using futex as a condition variable, for example: to manage a threadpool, there may be a lot of threads inside the futex_wait to sleep on this futex. The futex_hash_bucket consists therefore of many struct futex_q for the same futex.
On bad luck another futex, used as mutex, hashed into the same bucket. Every futex_wake on this mutex, has to scan the whole chain of above waiter to find the struct futex_q for this mutex. For non-unusual threadpool sizes of more than 20, this should be a considerable effort.
Quoted 4 lines
I therefore suggest to include in the hash-bucketchain only one struct futex_q per futex and to queue additional waiter in an extrachain at the 'top' futex_q entry. Thus different futex are isolated from each other, the cost of a hash collision is reduced.
So I don't dislike that idea.. however
Quoted 3 lines
To show the idea, I added a sample patch. Here, the plist is exchanged for a futex-specific implementation. kernel/pring.h is certainly not not the right place.

Quoted 5 lines

So I suppose the purpose of that plist in futex is to enable waking up the highest prio waiter, but with the advent of SCHED_DEADLINE that no longer works.
I think Thomas resisted going the RB-tree route earlier..

The only problem I see with the RB tree is the performance overhead and people are constantly complaining about futex performance anyway. But it might be worth a try.

Thanks,

tglx

Gerd Gerats

author

2017-09-28 22:40 UTC #3 lore raw

In reply to Peter Zijlstra

Quoted 18 lines · Peter Zijlstra

Quoted 10 lines · Gerd Gerats
When using futex as a condition variable, for example: to manage a threadpool, there may be a lot of threads inside the futex_wait to sleep on this futex. The futex_hash_bucket consists therefore of many struct futex_q for the same futex.
On bad luck another futex, used as mutex, hashed into the same bucket. Every futex_wake on this mutex, has to scan the whole chain of above waiter to find the struct futex_q for this mutex. For non-unusual threadpool sizes of more than 20, this should be a considerable effort.
Quoted 4 lines
I therefore suggest to include in the hash-bucketchain only one struct futex_q per futex and to queue additional waiter in an extrachain at the 'top' futex_q entry. Thus different futex are isolated from each other, the cost of a hash collision is reduced.
So I don't dislike that idea.. however

Quoted 7 lines

Quoted 3 lines
To show the idea, I added a sample patch. Here, the plist is exchanged for a futex-specific implementation. kernel/pring.h is certainly not not the right place.
So I suppose the purpose of that plist in futex is to enable waking up the highest prio waiter, but with the advent of SCHED_DEADLINE that no longer works.

I do not understand, plist is the original data structure. I assume, it works together with SCHED_DEADLINE. Or is there something on the way not pressent in 4.13.

pring replaces this data structure, retaining prio sorting rules, by a head-less ring. This ring contains all waiter for one futex_key, ordered the same way as by plist.

Thanx, Gerd

Peter Zijlstra

2017-09-29 08:36 UTC #4 lore raw

Quoted 7 lines · Gerd Gerats

Quoted 4 lines
So I suppose the purpose of that plist in futex is to enable waking up the highest prio waiter, but with the advent of SCHED_DEADLINE that no longer works.
I do not understand, plist is the original data structure. I assume, it works together with SCHED_DEADLINE.

plist does not work well with DEADLINE, all deadline tasks will get lumped together at prio -1; prio as a single integer doesn't really work for DEADLINE.

We've converted the RT-mutes over to RB-trees a fair while ago; see commit:

fb00aca47440 ("rtmutex: Turn the plist into an rb-tree")

Quoted 1 line

Or is there something on the way not pressent in 4.13.

Thomas held off on converting futex to rb-trees because, as he said elsewhere in this thread, he's worried about the performance impact on futexes.