Skip to contentSkip to conversation

Futexes functionalities and improvements

PATCH In review [email protected] 4 participants 13 messages Mar 13, 2007 – Mar 20, 2007

Subsystems (2)
ABI/API Futex
lore
Share & tools
lore

[email protected]

author
#0 lore raw

cover Futexes functionalities and improvements

Hi Andrew,

This is a re-send of a series of patches concerning futexes (here after is a short description)

Could you consider them for inclusion in -mm tree ?

All of them have already been discussed in January and have already been included in -rt for a while. I think that we agreed to potentially include them in the -mm tree.

Ulrich is specially interested by sys_futex64.

There are:
* futex uses prio list : allows RT-threads to be woken in priority order
instead of FIFO order.
* futex_wait uses hrtimer : allows the use of finer timer resolution.
* futex_requeue_pi functionality : allows use of requeue optimization for
PI-mutexes/PI-futexes.
* futex64 syscall : allows use of 64-bit futexes instead of 32-bit.

Note: it does not inlcude the fix "PI state locking fix" sent yesterday by Ingo.

Thanks,

Signature · 1 line
Pierre
author
#1 lore raw

PATCH 1/4 futex priority based wakeup

Today, all threads waiting for a given futex are woken in FIFO order (first waiter woken first) instead of priority order.

This patch makes use of plist (pirotity ordered lists) instead of simple list in futex_hash_bucket.

All non-RT threads are stored with priority MAX_RT_PRIO, causing them to be woken last, in FIFO order (RT-threads are woken first, in priority order).

Signed-off-by Sébastien Dugué <[email protected]>
Signed-off-by Pierre Peiffer <[email protected]>
---
 kernel/futex.c |   78 +++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 49 insertions(+), 29 deletions(-)
kernel/futex.c +49 -29
Index: b/kernel/futex.c
===================================================================
@@ -81,12 +81,12 @@ 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 list_empty(&q->list) || q->lock_ptr == 0.
+ * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
  * The order of wakup is always to make the first condition true, then
  * wake up q->waiters, then make the second condition true.
  */
 struct futex_q {
-	struct list_head list;
+	struct plist_node list;
 	wait_queue_head_t waiters;
 
 	/* Which hash list lock to use: */

@@ -108,8 +108,8 @@ struct futex_q {
  * Split the global futex_lock into every hash list lock.
  */
 struct futex_hash_bucket {
-       spinlock_t              lock;
-       struct list_head       chain;
+	spinlock_t lock;
+	struct plist_head chain;
 };
 
 static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];

@@ -443,13 +443,13 @@ lookup_pi_state(u32 uval, struct futex_h
 {
 	struct futex_pi_state *pi_state = NULL;
 	struct futex_q *this, *next;
-	struct list_head *head;
+	struct plist_head *head;
 	struct task_struct *p;
 	pid_t pid;
 
 	head = &hb->chain;
 
-	list_for_each_entry_safe(this, next, head, list) {
+	plist_for_each_entry_safe(this, next, head, list) {
 		if (match_futex(&this->key, &me->key)) {
 			/*
 			 * Another waiter already exists - bump up

@@ -513,12 +513,12 @@ lookup_pi_state(u32 uval, struct futex_h
  */
 static void wake_futex(struct futex_q *q)
 {
-	list_del_init(&q->list);
+	plist_del(&q->list, &q->list.plist);
 	if (q->filp)
 		send_sigio(&q->filp->f_owner, q->fd, POLL_IN);
 	/*
 	 * The lock in wake_up_all() is a crucial memory barrier after the
-	 * list_del_init() and also before assigning to q->lock_ptr.
+	 * plist_del() and also before assigning to q->lock_ptr.
 	 */
 	wake_up_all(&q->waiters);
 	/*

@@ -631,7 +631,7 @@ static int futex_wake(u32 __user *uaddr,
 {
 	struct futex_hash_bucket *hb;
 	struct futex_q *this, *next;
-	struct list_head *head;
+	struct plist_head *head;
 	union futex_key key;
 	int ret;
 

@@ -645,7 +645,7 @@ static int futex_wake(u32 __user *uaddr,
 	spin_lock(&hb->lock);
 	head = &hb->chain;
 
-	list_for_each_entry_safe(this, next, head, list) {
+	plist_for_each_entry_safe(this, next, head, list) {
 		if (match_futex (&this->key, &key)) {
 			if (this->pi_state) {
 				ret = -EINVAL;

@@ -673,7 +673,7 @@ futex_wake_op(u32 __user *uaddr1, u32 __
 {
 	union futex_key key1, key2;
 	struct futex_hash_bucket *hb1, *hb2;
-	struct list_head *head;
+	struct plist_head *head;
 	struct futex_q *this, *next;
 	int ret, op_ret, attempt = 0;
 

@@ -746,7 +746,7 @@ retry:
 
 	head = &hb1->chain;
 
-	list_for_each_entry_safe(this, next, head, list) {
+	plist_for_each_entry_safe(this, next, head, list) {
 		if (match_futex (&this->key, &key1)) {
 			wake_futex(this);
 			if (++ret >= nr_wake)

@@ -758,7 +758,7 @@ retry:
 		head = &hb2->chain;
 
 		op_ret = 0;
-		list_for_each_entry_safe(this, next, head, list) {
+		plist_for_each_entry_safe(this, next, head, list) {
 			if (match_futex (&this->key, &key2)) {
 				wake_futex(this);
 				if (++op_ret >= nr_wake2)

@@ -785,7 +785,7 @@ static int futex_requeue(u32 __user *uad
 {
 	union futex_key key1, key2;
 	struct futex_hash_bucket *hb1, *hb2;
-	struct list_head *head1;
+	struct plist_head *head1;
 	struct futex_q *this, *next;
 	int ret, drop_count = 0;
 

@@ -834,7 +834,7 @@ static int futex_requeue(u32 __user *uad
 	}
 
 	head1 = &hb1->chain;
-	list_for_each_entry_safe(this, next, head1, list) {
+	plist_for_each_entry_safe(this, next, head1, list) {
 		if (!match_futex (&this->key, &key1))
 			continue;
 		if (++ret <= nr_wake) {

@@ -845,9 +845,13 @@ static int futex_requeue(u32 __user *uad
 			 * requeue.
 			 */
 			if (likely(head1 != &hb2->chain)) {
-				list_move_tail(&this->list, &hb2->chain);
+				plist_del(&this->list, &hb1->chain);
+				plist_add(&this->list, &hb2->chain);
 				this->lock_ptr = &hb2->lock;
-			}
+#ifdef CONFIG_DEBUG_PI_LIST
+				this->list.plist.lock = &hb2->lock;
+#endif
+ 			}
 			this->key = key2;
 			get_futex_key_refs(&key2);
 			drop_count++;

@@ -892,7 +896,23 @@ queue_lock(struct futex_q *q, int fd, st
 
 static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
 {
-	list_add_tail(&q->list, &hb->chain);
+	int prio;
+
+	/*
+	 * The priority used to register this element is
+	 * - either the real thread-priority for the real-time threads
+	 * (i.e. threads with a priority lower than MAX_RT_PRIO)
+	 * - or MAX_RT_PRIO for non-RT threads.
+	 * Thus, all RT-threads are woken first in priority order, and
+	 * the others are woken last, in FIFO order.
+	 */
+	prio = min(current->normal_prio, MAX_RT_PRIO);
+
+	plist_node_init(&q->list, prio);
+#ifdef CONFIG_DEBUG_PI_LIST
+	q->list.plist.lock = &hb->lock;
+#endif
+	plist_add(&q->list, &hb->chain);
 	q->task = current;
 	spin_unlock(&hb->lock);
 }

@@ -947,8 +967,8 @@ static int unqueue_me(struct futex_q *q)
 			spin_unlock(lock_ptr);
 			goto retry;
 		}
-		WARN_ON(list_empty(&q->list));
-		list_del(&q->list);
+		WARN_ON(plist_node_empty(&q->list));
+		plist_del(&q->list, &q->list.plist);
 
 		BUG_ON(q->pi_state);
 

@@ -966,8 +986,8 @@ static int unqueue_me(struct futex_q *q)
  */
 static void unqueue_me_pi(struct futex_q *q, struct futex_hash_bucket *hb)
 {
-	WARN_ON(list_empty(&q->list));
-	list_del(&q->list);
+	WARN_ON(plist_node_empty(&q->list));
+	plist_del(&q->list, &q->list.plist);
 
 	BUG_ON(!q->pi_state);
 	free_pi_state(q->pi_state);

@@ -1060,10 +1080,10 @@ static int futex_wait(u32 __user *uaddr,
 	__set_current_state(TASK_INTERRUPTIBLE);
 	add_wait_queue(&q.waiters, &wait);
 	/*
-	 * !list_empty() is safe here without any lock.
+	 * !plist_node_empty() is safe here without any lock.
 	 * q.lock_ptr != 0 is not safe, because of ordering against wakeup.
 	 */
-	if (likely(!list_empty(&q.list)))
+	if (likely(!plist_node_empty(&q.list)))
 		time = schedule_timeout(time);
 	__set_current_state(TASK_RUNNING);
 

@@ -1336,7 +1356,7 @@ static int futex_unlock_pi(u32 __user *u
 	struct futex_hash_bucket *hb;
 	struct futex_q *this, *next;
 	u32 uval;
-	struct list_head *head;
+	struct plist_head *head;
 	union futex_key key;
 	int ret, attempt = 0;
 

@@ -1387,7 +1407,7 @@ retry_locked:
 	 */
 	head = &hb->chain;
 
-	list_for_each_entry_safe(this, next, head, list) {
+	plist_for_each_entry_safe(this, next, head, list) {
 		if (!match_futex (&this->key, &key))
 			continue;
 		ret = wake_futex_pi(uaddr, uval, this);

@@ -1461,10 +1481,10 @@ static unsigned int futex_poll(struct fi
 	poll_wait(filp, &q->waiters, wait);
 
 	/*
-	 * list_empty() is safe here without any lock.
+	 * plist_node_empty() is safe here without any lock.
 	 * q->lock_ptr != 0 is not safe, because of ordering against wakeup.
 	 */
-	if (list_empty(&q->list))
+	if (plist_node_empty(&q->list))
 		ret = POLLIN | POLLRDNORM;
 
 	return ret;

@@ -1847,7 +1867,7 @@ static int __init init(void)
 	}
 
 	for (i = 0; i < ARRAY_SIZE(futex_queues); i++) {
-		INIT_LIST_HEAD(&futex_queues[i].chain);
+		plist_head_init(&futex_queues[i].chain, &futex_queues[i].lock);
 		spin_lock_init(&futex_queues[i].lock);
 	}
 	return 0;
Signature · 2 lines
-- 
Pierre Peiffer
author
#2 lore raw

PATCH 2/4 Make futex_wait() use an hrtimer for timeout

In reply to [email protected]

This patch modifies futex_wait() to use an hrtimer + schedule() in place of schedule_timeout().

schedule_timeout() is tick based, therefore the timeout granularity is
the tick (1 ms, 4 ms or 10 ms depending on HZ). By using a high resolution timer for timeout wakeup, we can attain a much finer timeout granularity (in the microsecond range). This parallels what is already done for futex_lock_pi().

The timeout passed to the syscall is no longer converted to jiffies
and is therefore passed to do_futex() and futex_wait() as a timespec therefore keeping nanosecond resolution.

Also this removes the need to pass the nanoseconds timeout part to
futex_lock_pi() in val2.

In futex_wait(), if there is no timeout then a regular schedule() is
performed. Otherwise, an hrtimer is fired before schedule() is called.

Signed-off-by Sébastien Dugué <[email protected]>
Signed-off-by Pierre Peiffer <[email protected]>
---
 include/linux/futex.h |    2 -
 kernel/futex.c        |   59 +++++++++++++++++++++++++++++++++-----------------
 kernel/futex_compat.c |   12 ++--------
 3 files changed, 43 insertions(+), 30 deletions(-)
kernel/futex.c +39 -20
Index: b/kernel/futex.c
===================================================================
@@ -998,7 +998,7 @@ static void unqueue_me_pi(struct futex_q
 	drop_futex_key_refs(&q->key);
 }
 
-static int futex_wait(u32 __user *uaddr, u32 val, unsigned long time)
+static int futex_wait(u32 __user *uaddr, u32 val, struct timespec *time)
 {
 	struct task_struct *curr = current;
 	DECLARE_WAITQUEUE(wait, curr);

@@ -1006,6 +1006,8 @@ static int futex_wait(u32 __user *uaddr,
 	struct futex_q q;
 	u32 uval;
 	int ret;
+	struct hrtimer_sleeper t;
+	int rem = 0;
 
 	q.pi_state = NULL;
  retry:

@@ -1083,8 +1085,31 @@ static int futex_wait(u32 __user *uaddr,
 	 * !plist_node_empty() is safe here without any lock.
 	 * q.lock_ptr != 0 is not safe, because of ordering against wakeup.
 	 */
-	if (likely(!plist_node_empty(&q.list)))
-		time = schedule_timeout(time);
+	if (likely(!plist_node_empty(&q.list))) {
+		if (!time)
+			schedule();
+		else {
+			hrtimer_init(&t.timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
+			hrtimer_init_sleeper(&t, current);
+			t.timer.expires = timespec_to_ktime(*time);
+
+			hrtimer_start(&t.timer, t.timer.expires, HRTIMER_MODE_REL);
+
+			/*
+			 * the timer could have already expired, in which
+			 * case current would be flagged for rescheduling.
+			 * Don't bother calling schedule.
+			 */
+			if (likely(t.task))
+				schedule();
+
+			hrtimer_cancel(&t.timer);
+
+			/* Flag if a timeout occured */
+			rem = (t.task == NULL);
+		}
+	}
+
 	__set_current_state(TASK_RUNNING);
 
 	/*

@@ -1095,7 +1120,7 @@ static int futex_wait(u32 __user *uaddr,
 	/* If we were woken (and unqueued), we succeeded, whatever. */
 	if (!unqueue_me(&q))
 		return 0;
-	if (time == 0)
+	if (rem)
 		return -ETIMEDOUT;
 	/*
 	 * We expect signal_pending(current), but another thread may

@@ -1117,8 +1142,8 @@ static int futex_wait(u32 __user *uaddr,
  * if there are waiters then it will block, it does PI, etc. (Due to
  * races the kernel might see a 0 value of the futex too.)
  */
-static int futex_lock_pi(u32 __user *uaddr, int detect, unsigned long sec,
-			 long nsec, int trylock)
+static int futex_lock_pi(u32 __user *uaddr, int detect, struct timespec *time,
+			 int trylock)
 {
 	struct hrtimer_sleeper timeout, *to = NULL;
 	struct task_struct *curr = current;

@@ -1130,11 +1155,11 @@ static int futex_lock_pi(u32 __user *uad
 	if (refill_pi_state_cache())
 		return -ENOMEM;
 
-	if (sec != MAX_SCHEDULE_TIMEOUT) {
+	if (time) {
 		to = &timeout;
 		hrtimer_init(&to->timer, CLOCK_REALTIME, HRTIMER_MODE_ABS);
 		hrtimer_init_sleeper(to, current);
-		to->timer.expires = ktime_set(sec, nsec);
+		to->timer.expires = timespec_to_ktime(*time);
 	}
 
 	q.pi_state = NULL;

@@ -1770,7 +1795,7 @@ void exit_robust_list(struct task_struct
 	}
 }
 
-long do_futex(u32 __user *uaddr, int op, u32 val, unsigned long timeout,
+long do_futex(u32 __user *uaddr, int op, u32 val, struct timespec *timeout,
 		u32 __user *uaddr2, u32 val2, u32 val3)
 {
 	int ret;

@@ -1796,13 +1821,13 @@ long do_futex(u32 __user *uaddr, int op,
 		ret = futex_wake_op(uaddr, uaddr2, val, val2, val3);
 		break;
 	case FUTEX_LOCK_PI:
-		ret = futex_lock_pi(uaddr, val, timeout, val2, 0);
+		ret = futex_lock_pi(uaddr, val, timeout, 0);
 		break;
 	case FUTEX_UNLOCK_PI:
 		ret = futex_unlock_pi(uaddr);
 		break;
 	case FUTEX_TRYLOCK_PI:
-		ret = futex_lock_pi(uaddr, 0, timeout, val2, 1);
+		ret = futex_lock_pi(uaddr, 0, timeout, 1);
 		break;
 	default:
 		ret = -ENOSYS;

@@ -1815,8 +1840,7 @@ asmlinkage long sys_futex(u32 __user *ua
 			  struct timespec __user *utime, u32 __user *uaddr2,
 			  u32 val3)
 {
-	struct timespec t;
-	unsigned long timeout = MAX_SCHEDULE_TIMEOUT;
+	struct timespec t, *tp = NULL;
 	u32 val2 = 0;
 
 	if (utime && (op == FUTEX_WAIT || op == FUTEX_LOCK_PI)) {

@@ -1824,12 +1848,7 @@ asmlinkage long sys_futex(u32 __user *ua
 			return -EFAULT;
 		if (!timespec_valid(&t))
 			return -EINVAL;
-		if (op == FUTEX_WAIT)
-			timeout = timespec_to_jiffies(&t) + 1;
-		else {
-			timeout = t.tv_sec;
-			val2 = t.tv_nsec;
-		}
+		tp = &t;
 	}
 	/*
 	 * requeue parameter in 'utime' if op == FUTEX_REQUEUE.

@@ -1837,7 +1856,7 @@ asmlinkage long sys_futex(u32 __user *ua
 	if (op == FUTEX_REQUEUE || op == FUTEX_CMP_REQUEUE)
 		val2 = (u32) (unsigned long) utime;
 
-	return do_futex(uaddr, op, val, timeout, uaddr2, val2, val3);
+	return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
 }
 
 static int futexfs_get_sb(struct file_system_type *fs_type,
include/linux/futex.h +1 -1
Index: b/include/linux/futex.h
===================================================================
@@ -94,7 +94,7 @@ struct robust_list_head {
 #define ROBUST_LIST_LIMIT	2048
 
 #ifdef __KERNEL__
-long do_futex(u32 __user *uaddr, int op, u32 val, unsigned long timeout,
+long do_futex(u32 __user *uaddr, int op, u32 val, struct timespec *timeout,
 	      u32 __user *uaddr2, u32 val2, u32 val3);
 
 extern int
kernel/futex_compat.c +3 -9
Index: b/kernel/futex_compat.c
===================================================================
@@ -141,8 +141,7 @@ asmlinkage long compat_sys_futex(u32 __u
 		struct compat_timespec __user *utime, u32 __user *uaddr2,
 		u32 val3)
 {
-	struct timespec t;
-	unsigned long timeout = MAX_SCHEDULE_TIMEOUT;
+	struct timespec t, *tp = NULL;
 	int val2 = 0;
 
 	if (utime && (op == FUTEX_WAIT || op == FUTEX_LOCK_PI)) {

@@ -150,15 +149,10 @@ asmlinkage long compat_sys_futex(u32 __u
 			return -EFAULT;
 		if (!timespec_valid(&t))
 			return -EINVAL;
-		if (op == FUTEX_WAIT)
-			timeout = timespec_to_jiffies(&t) + 1;
-		else {
-			timeout = t.tv_sec;
-			val2 = t.tv_nsec;
-		}
+		tp = &t;
 	}
 	if (op == FUTEX_REQUEUE || op == FUTEX_CMP_REQUEUE)
 		val2 = (int) (unsigned long) utime;
 
-	return do_futex(uaddr, op, val, timeout, uaddr2, val2, val3);
+	return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
 }
Signature · 2 lines
-- 
Pierre Peiffer
author
#3 lore raw

PATCH 3/4 futex_requeue_pi optimization

In reply to [email protected]

This patch provides the futex_requeue_pi functionality.

This provides an optimization, already used for (normal) futexes, to be used for PI-futexes.

This optimization is currently used by the glibc in pthread_broadcast, when using "normal" mutexes. With futex_requeue_pi, it can be used with PRIO_INHERIT mutexes too.

Signed-off-by Pierre Peiffer <[email protected]>
---
 include/linux/futex.h   |    8 
 kernel/futex.c          |  557 +++++++++++++++++++++++++++++++++++++++++++-----
 kernel/futex_compat.c   |    3 
 kernel/rtmutex.c        |   41 ---
 kernel/rtmutex_common.h |   34 ++
 5 files changed, 555 insertions(+), 88 deletions(-)
include/linux/futex.h +7 -1
Index: b/include/linux/futex.h
===================================================================
@@ -15,6 +15,7 @@
 #define FUTEX_LOCK_PI		6
 #define FUTEX_UNLOCK_PI		7
 #define FUTEX_TRYLOCK_PI	8
+#define FUTEX_CMP_REQUEUE_PI	9
 
 /*
  * Support for robust futexes: the kernel cleans up held futexes at

@@ -83,9 +84,14 @@ struct robust_list_head {
 #define FUTEX_OWNER_DIED	0x40000000
 
 /*
+ * Some processes have been requeued on this PI-futex
+ */
+#define FUTEX_WAITER_REQUEUED	0x20000000
+
+/*
  * The rest of the robust-futex field is for the TID:
  */
-#define FUTEX_TID_MASK		0x3fffffff
+#define FUTEX_TID_MASK		0x0fffffff
 
 /*
  * This limit protects against a deliberately circular list.
kernel/futex.c +503 -54

728 lines not on this page · raw message

kernel/rtmutex.c +9 -32

71 lines not on this page · raw message

kernel/rtmutex_common.h +34 -0
Index: b/kernel/rtmutex_common.h
===================================================================
@@ -113,6 +113,29 @@ static inline unsigned long rt_mutex_own
 }
 
 /*
+ * We can speed up the acquire/release, if the architecture
+ * supports cmpxchg and if there's no debugging state to be set up
+ */
+#if defined(__HAVE_ARCH_CMPXCHG) && !defined(CONFIG_DEBUG_RT_MUTEXES)
+# define rt_mutex_cmpxchg(l,c,n)	(cmpxchg(&l->owner, c, n) == c)
+static inline void mark_rt_mutex_waiters(struct rt_mutex *lock)
+{
+	unsigned long owner, *p = (unsigned long *) &lock->owner;
+
+	do {
+		owner = *p;
+	} while (cmpxchg(p, owner, owner | RT_MUTEX_HAS_WAITERS) != owner);
+}
+#else
+# define rt_mutex_cmpxchg(l,c,n)	(0)
+static inline void mark_rt_mutex_waiters(struct rt_mutex *lock)
+{
+	lock->owner = (struct task_struct *)
+			((unsigned long)lock->owner | RT_MUTEX_HAS_WAITERS);
+}
+#endif
+
+/*
  * PI-futex support (proxy locking functions, etc.):
  */
 extern struct task_struct *rt_mutex_next_owner(struct rt_mutex *lock);

@@ -120,4 +143,15 @@ extern void rt_mutex_init_proxy_locked(s
 				       struct task_struct *proxy_owner);
 extern void rt_mutex_proxy_unlock(struct rt_mutex *lock,
 				  struct task_struct *proxy_owner);
+
+extern void rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner,
+			       unsigned long mask);
+extern void __rt_mutex_adjust_prio(struct task_struct *task);
+extern int rt_mutex_adjust_prio_chain(struct task_struct *task,
+				      int deadlock_detect,
+				      struct rt_mutex *orig_lock,
+				      struct rt_mutex_waiter *orig_waiter,
+				      struct task_struct *top_task);
+extern void remove_waiter(struct rt_mutex *lock,
+			  struct rt_mutex_waiter *waiter);
 #endif
kernel/futex_compat.c +2 -1
Index: b/kernel/futex_compat.c
===================================================================
@@ -151,7 +151,8 @@ asmlinkage long compat_sys_futex(u32 __u
 			return -EINVAL;
 		tp = &t;
 	}
-	if (op == FUTEX_REQUEUE || op == FUTEX_CMP_REQUEUE)
+	if (op == FUTEX_REQUEUE || op == FUTEX_CMP_REQUEUE
+	    || op == FUTEX_CMP_REQUEUE_PI)
 		val2 = (int) (unsigned long) utime;
 
 	return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
Signature · 2 lines
-- 
Pierre Peiffer
#4 lore raw

Re: [PATCH 2.6.21-rc3-mm2 3/4] futex_requeue_pi optimization

Quoted 22 lines · On Tue, 2007-03-13 at 10:52 +0100, [email protected] wrote:

plain text document attachment (futex-requeue-pi.diff) This patch provides the futex_requeue_pi functionality.

This provides an optimization, already used for (normal) futexes, to be used for PI-futexes.

This optimization is currently used by the glibc in pthread_broadcast, when using "normal" mutexes. With futex_requeue_pi, it can be used with PRIO_INHERIT mutexes too.

Signed-off-by Pierre Peiffer <[email protected]>

---

/*
+ * Retrieve the original address used to compute this key
+ */

kernel/futex.c +5 -0
+static void *get_futex_address(union futex_key *key)
+{
+	void *uaddr;
+
+	if (key->both.offset & 1) {

kernel/futex.c int get_futex_key(u32 __user *uaddr, uni · line 255

Quoted 10 lines
kernel/futex.c +10 -0
+		/* shared mapping */
+		uaddr = (void*)((key->shared.pgoff << PAGE_SHIFT)
+				+ key->shared.offset - 1);
+	} else {
+		/* private mapping */
+		uaddr = (void*)(key->private.address + key->private.offset);
+	}
+
+	return uaddr;
+}

This will not work for nonlinear vmas, granted, not a lot of ppl stick futexes in nonlinear vmas, but the futex_key stuff handles it, this doesn't.

author
#5 lore raw

Re: [PATCH 2.6.21-rc3-mm2 3/4] futex_requeue_pi optimization

Quoted 11 lines · Peter Zijlstra
Quoted 11 lines
kernel/futex.c +11 -0
+static void *get_futex_address(union futex_key *key)
+{
+	void *uaddr;
+
+	if (key->both.offset & 1) {
+		/* shared mapping */
+		uaddr = (void*)((key->shared.pgoff << PAGE_SHIFT)
+				+ key->shared.offset - 1);
+	} else {
+		/* private mapping */
+		uaddr = (void*)(key->private.address + key->private.offset);
Quoted 8 lines

kernel/futex.c int get_futex_key(u32 __user *uaddr, uni · line 255

Quoted 4 lines
kernel/futex.c +4 -0
+	}
+
+	return uaddr;
+}

This will not work for nonlinear vmas, granted, not a lot of ppl stick futexes in nonlinear vmas, but the futex_key stuff handles it, this doesn't.

Indeed ! Thanks for pointing me to this.

Since I'm not familiar with vmm, does this code look more correct to you ?

static void *get_futex_address(union futex_key *key)

{
	void *uaddr;
	struct vm_area_struct *vma = current->mm->mmap;

	if (key->both.offset & 1) {
		/* shared mapping */
		struct file * vmf;

		do {
			if ((vmf = vma->vm_file)
			    && (key->shared.inode == vmf->f_dentry->d_inode))
				break;
			vma = vma->vm_next;
		} while (vma);

		if (likely(!(vma->vm_flags & VM_NONLINEAR)))
			uaddr = (void*)((key->shared.pgoff << PAGE_SHIFT)
					+ key->shared.offset - 1);
		else
			uaddr = (void*) vma->vm_start
				+ ((key->shared.pgoff - vma->vm_pgoff)
				   << PAGE_SHIFT)
				+ key->shared.offset - 1;
	} else {
		/* private mapping */
		uaddr = (void*)(key->private.address + key->private.offset);
	}

	return uaddr;
}

Or is there a more direct way to retrieve the vma corresponding to the given inode ?

Thanks,

Signature · 1 line
Pierre
#6 lore raw

Re: [PATCH 2.6.21-rc3-mm2 3/4] futex_requeue_pi optimization

Quoted 21 lines · Pierre Peiffer
Quoted 11 lines · Peter Zijlstra
Quoted 11 lines
kernel/futex.c +11 -0
+static void *get_futex_address(union futex_key *key)
+{
+	void *uaddr;
+
+	if (key->both.offset & 1) {
+		/* shared mapping */
+		uaddr = (void*)((key->shared.pgoff << PAGE_SHIFT)
+				+ key->shared.offset - 1);
+	} else {
+		/* private mapping */
+		uaddr = (void*)(key->private.address + key->private.offset);
Quoted 8 lines

kernel/futex.c int get_futex_key(u32 __user *uaddr, uni · line 255

Quoted 4 lines
kernel/futex.c +4 -0
+	}
+
+	return uaddr;
+}

This will not work for nonlinear vmas, granted, not a lot of ppl stick futexes in nonlinear vmas, but the futex_key stuff handles it, this doesn't.

Quoted 3 lines

Indeed ! Thanks for pointing me to this.

Since I'm not familiar with vmm, does this code look more correct to you ?

Unfortunately not, nonlinear vmas don't have a linear relation between address and offset. What you would need to do is do a linear walk of the page tables. But even that might not suffice if nonlinear vmas may form a non-injective, surjective mapping.

/me checks..

Hmm, yes that seems valid, so in general, this reverse mapping does not uniquely exist for non-linear vmas. :-(

What to do... disallow futexes in nonlinear mappings, store the address in the key?

Quoted 32 lines

static void *get_futex_address(union futex_key *key)

{
	void *uaddr;
	struct vm_area_struct *vma = current->mm->mmap;

	if (key->both.offset & 1) {
		/* shared mapping */
		struct file * vmf;

		do {
			if ((vmf = vma->vm_file)
			    && (key->shared.inode == vmf->f_dentry->d_inode))
				break;
			vma = vma->vm_next;
		} while (vma);

		if (likely(!(vma->vm_flags & VM_NONLINEAR)))
			uaddr = (void*)((key->shared.pgoff << PAGE_SHIFT)
					+ key->shared.offset - 1);
		else
			uaddr = (void*) vma->vm_start
				+ ((key->shared.pgoff - vma->vm_pgoff)
				   << PAGE_SHIFT)
				+ key->shared.offset - 1;
	} else {
		/* private mapping */
		uaddr = (void*)(key->private.address + key->private.offset);
	}

	return uaddr;
}
Quoted 1 line

Or is there a more direct way to retrieve the vma corresponding to the given inode ?

the vma_prio_tree would be able to give all vmas associated with a mapping.

author
#7 lore raw

Re: [PATCH 2.6.21-rc3-mm2 3/4] futex_requeue_pi optimization

Quoted 6 lines · Peter Zijlstra

Unfortunately not, nonlinear vmas don't have a linear relation between address and offset. What you would need to do is do a linear walk of the page tables. But even that might not suffice if nonlinear vmas may form a non-injective, surjective mapping.

Quoted 8 lines

/me checks..

Hmm, yes that seems valid, so in general, this reverse mapping does not uniquely exist for non-linear vmas. :-(

What to do... disallow futexes in nonlinear mappings,

store the address in the key? <<

That seems to be the only solution... :-/

Quoted 4 lines

the vma_prio_tree would be able to give all vmas associated with a mapping.

Thanks for your help.

Signature · 1 line
Pierre
author
#8 lore raw

PATCH 4/4 sys_futex64 : allows 64bit futexes

In reply to [email protected]

This last patch is an adaptation of the sys_futex64 syscall provided in -rt patch (originally written by Ingo). It allows the use of 64bit futex.

I have re-worked most of the code to avoid the duplication of the code.

It does not provide the functionality for all architectures (only for x64 for now).

Signed-off-by Pierre Peiffer <[email protected]>
---
 include/asm-x86_64/futex.h  |  113 ++++++++++++++++++++
 include/asm-x86_64/unistd.h |    4 
 include/linux/futex.h       |    7 -
 include/linux/syscalls.h    |    3 
 kernel/futex.c              |  248 +++++++++++++++++++++++++++++++-------------
 kernel/futex_compat.c       |    3 
 kernel/sys_ni.c             |    1 
 7 files changed, 301 insertions(+), 78 deletions(-)
include/asm-x86_64/futex.h +113 -0
Index: b/include/asm-x86_64/futex.h
===================================================================
@@ -41,6 +41,39 @@
 	  "=&r" (tem)						\
 	: "r" (oparg), "i" (-EFAULT), "m" (*uaddr), "1" (0))
 
+#define __futex_atomic_op1_64(insn, ret, oldval, uaddr, oparg) \
+  __asm__ __volatile (						\
+"1:	" insn "\n"						\
+"2:	.section .fixup,\"ax\"\n\
+3:	movq	%3, %1\n\
+	jmp	2b\n\
+	.previous\n\
+	.section __ex_table,\"a\"\n\
+	.align	8\n\
+	.quad	1b,3b\n\
+	.previous"						\
+	: "=r" (oldval), "=r" (ret), "=m" (*uaddr)		\
+	: "i" (-EFAULT), "m" (*uaddr), "0" (oparg), "1" (0))
+
+#define __futex_atomic_op2_64(insn, ret, oldval, uaddr, oparg) \
+  __asm__ __volatile (						\
+"1:	movq	%2, %0\n\
+	movq	%0, %3\n"					\
+	insn "\n"						\
+"2:	" LOCK_PREFIX "cmpxchgq %3, %2\n\
+	jnz	1b\n\
+3:	.section .fixup,\"ax\"\n\
+4:	movq	%5, %1\n\
+	jmp	3b\n\
+	.previous\n\
+	.section __ex_table,\"a\"\n\
+	.align	8\n\
+	.quad	1b,4b,2b,4b\n\
+	.previous"						\
+	: "=&a" (oldval), "=&r" (ret), "=m" (*uaddr),		\
+	  "=&r" (tem)						\
+	: "r" (oparg), "i" (-EFAULT), "m" (*uaddr), "1" (0))
+
 static inline int
 futex_atomic_op_inuser (int encoded_op, int __user *uaddr)
 {

@@ -95,6 +128,60 @@ futex_atomic_op_inuser (int encoded_op, 
 }
 
 static inline int
+futex_atomic_op_inuser64 (int encoded_op, u64 __user *uaddr)
+{
+	int op = (encoded_op >> 28) & 7;
+	int cmp = (encoded_op >> 24) & 15;
+	u64 oparg = (encoded_op << 8) >> 20;
+	u64 cmparg = (encoded_op << 20) >> 20;
+	u64 oldval = 0, ret, tem;
+
+	if (encoded_op & (FUTEX_OP_OPARG_SHIFT << 28))
+		oparg = 1 << oparg;
+
+	if (! access_ok (VERIFY_WRITE, uaddr, sizeof(u64)))
+		return -EFAULT;
+
+	inc_preempt_count();
+
+	switch (op) {
+	case FUTEX_OP_SET:
+		__futex_atomic_op1_64("xchgq %0, %2", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_ADD:
+		__futex_atomic_op1_64(LOCK_PREFIX "xaddq %0, %2", ret, oldval,
+				   uaddr, oparg);
+		break;
+	case FUTEX_OP_OR:
+		__futex_atomic_op2_64("orq %4, %3", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_ANDN:
+		__futex_atomic_op2_64("andq %4, %3", ret, oldval, uaddr, ~oparg);
+		break;
+	case FUTEX_OP_XOR:
+		__futex_atomic_op2_64("xorq %4, %3", ret, oldval, uaddr, oparg);
+		break;
+	default:
+		ret = -ENOSYS;
+	}
+
+	dec_preempt_count();
+
+	if (!ret) {
+		switch (cmp) {
+		case FUTEX_OP_CMP_EQ: ret = (oldval == cmparg); break;
+		case FUTEX_OP_CMP_NE: ret = (oldval != cmparg); break;
+		case FUTEX_OP_CMP_LT: ret = (oldval < cmparg); break;
+		case FUTEX_OP_CMP_GE: ret = (oldval >= cmparg); break;
+		case FUTEX_OP_CMP_LE: ret = (oldval <= cmparg); break;
+		case FUTEX_OP_CMP_GT: ret = (oldval > cmparg); break;
+		default: ret = -ENOSYS;
+		}
+	}
+	return ret;
+}
+
+static inline int
 futex_atomic_cmpxchg_inatomic(int __user *uaddr, int oldval, int newval)
 {
 	if (!access_ok(VERIFY_WRITE, uaddr, sizeof(int)))

@@ -121,5 +208,31 @@ futex_atomic_cmpxchg_inatomic(int __user
 	return oldval;
 }
 
+static inline u64
+futex_atomic_cmpxchg_inatomic64(u64 __user *uaddr, u64 oldval, u64 newval)
+{
+	if (!access_ok(VERIFY_WRITE, uaddr, sizeof(u64)))
+		return -EFAULT;
+
+	__asm__ __volatile__(
+		"1:	" LOCK_PREFIX "cmpxchgq %3, %1		\n"
+
+		"2:	.section .fixup, \"ax\"			\n"
+		"3:	mov     %2, %0				\n"
+		"	jmp     2b				\n"
+		"	.previous				\n"
+
+		"	.section __ex_table, \"a\"		\n"
+		"	.align  8				\n"
+		"	.quad   1b,3b				\n"
+		"	.previous				\n"
+
+		: "=a" (oldval), "=m" (*uaddr)
+		: "i" (-EFAULT), "r" (newval), "0" (oldval)
+		: "memory"
+	);
+
+	return oldval;
+}
 #endif
 #endif
include/asm-x86_64/unistd.h +3 -1
Index: b/include/asm-x86_64/unistd.h
===================================================================
@@ -619,8 +619,10 @@ __SYSCALL(__NR_sync_file_range, sys_sync
 __SYSCALL(__NR_vmsplice, sys_vmsplice)
 #define __NR_move_pages		279
 __SYSCALL(__NR_move_pages, sys_move_pages)
+#define __NR_futex64		280
+__SYSCALL(__NR_futex64, sys_futex64)
 
-#define __NR_syscall_max __NR_move_pages
+#define __NR_syscall_max __NR_futex64
 
 #ifndef __NO_STUBS
 #define __ARCH_WANT_OLD_READDIR
include/linux/syscalls.h +3 -0
Index: b/include/linux/syscalls.h
===================================================================
@@ -178,6 +178,9 @@ asmlinkage long sys_set_tid_address(int 
 asmlinkage long sys_futex(u32 __user *uaddr, int op, u32 val,
 			struct timespec __user *utime, u32 __user *uaddr2,
 			u32 val3);
+asmlinkage long sys_futex64(u64 __user *uaddr, int op, u64 val,
+			struct timespec __user *utime, u64 __user *uaddr2,
+			u64 val3);
 
 asmlinkage long sys_init_module(void __user *umod, unsigned long len,
 				const char __user *uargs);
kernel/futex.c +175 -73

568 lines not on this page · raw message

kernel/sys_ni.c +1 -0
Index: b/kernel/sys_ni.c
===================================================================
@@ -41,6 +41,7 @@ cond_syscall(sys_sendmsg);
 cond_syscall(sys_recvmsg);
 cond_syscall(sys_socketcall);
 cond_syscall(sys_futex);
+cond_syscall(sys_futex64);
 cond_syscall(compat_sys_futex);
 cond_syscall(sys_set_robust_list);
 cond_syscall(compat_sys_set_robust_list);
include/linux/futex.h +4 -3
Index: b/include/linux/futex.h
===================================================================
@@ -100,8 +100,9 @@ struct robust_list_head {
 #define ROBUST_LIST_LIMIT	2048
 
 #ifdef __KERNEL__
-long do_futex(u32 __user *uaddr, int op, u32 val, struct timespec *timeout,
-	      u32 __user *uaddr2, u32 val2, u32 val3);
+long do_futex(unsigned long __user *uaddr, int op, unsigned long val,
+	      struct timespec *timeout, unsigned long __user *uaddr2,
+	      unsigned long val2, unsigned long val3, int futex64);
 
 extern int
 handle_futex_death(u32 __user *uaddr, struct task_struct *curr, int pi);

@@ -131,7 +132,7 @@ union futex_key {
 		int offset;
 	} both;
 };
-int get_futex_key(u32 __user *uaddr, union futex_key *key);
+int get_futex_key(void __user *uaddr, union futex_key *key);
 void get_futex_key_refs(union futex_key *key);
 void drop_futex_key_refs(union futex_key *key);
kernel/futex_compat.c +2 -1
Index: b/kernel/futex_compat.c
===================================================================
@@ -155,5 +155,6 @@ asmlinkage long compat_sys_futex(u32 __u
 	    || op == FUTEX_CMP_REQUEUE_PI)
 		val2 = (int) (unsigned long) utime;
 
-	return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
+	return do_futex((unsigned long __user*)uaddr, op, val, tp,
+			(unsigned long __user*)uaddr2, val2, val3, 0);
 }
Signature · 2 lines
-- 
Pierre Peiffer
#9 lore raw

Re: [PATCH 2.6.21-rc3-mm2 4/4] sys_futex64 : allows 64bit futexes

Quoted 7 lines · On Tue, 13 Mar 2007 10:52:07 +0100 [email protected] wrote:

This last patch is an adaptation of the sys_futex64 syscall provided in -rt patch (originally written by Ingo). It allows the use of 64bit futex.

I have re-worked most of the code to avoid the duplication of the code.

It does not provide the functionality for all architectures (only for x64 for now).

What a lot of code.

Why do we want 64-bit futexes?

#10 lore raw

Re: [PATCH 2.6.21-rc3-mm2 4/4] sys_futex64 : allows 64bit futexes

Quoted 1 line · Andrew Morton

Why do we want 64-bit futexes?

I sent this to you already on 1/12/2007:

http://udrepper.livejournal.com/13123.html

Signature · 1 line
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
#11 lore raw

Re: [PATCH 2.6.21-rc3-mm2 4/4] sys_futex64 : allows 64bit futexes

Quoted 7 lines · On Thu, 15 Mar 2007 12:12:11 -0700 Ulrich Drepper <[email protected]> wrote:
Quoted 1 line · Andrew Morton

Why do we want 64-bit futexes?

I sent this to you already on 1/12/2007:

http://udrepper.livejournal.com/13123.html

Well OK. But that doesn't actually explain why 64-bit mutexes are needed. It just says they are required.

#12 lore raw

Re: [PATCH 2.6.21-rc3-mm2 4/4] sys_futex64 : allows 64bit futexes

Quoted 2 lines · Andrew Morton

Well OK. But that doesn't actually explain why 64-bit mutexes are needed. It just says they are required.

I can show you the code but it's not easy to understand. For complicated syn objects like rwlocks the state information is more than just locked or not. Currently we have to use internal locks, modify the state information, and then release it. This is terribly inefficient when many threads are used. With 64bit futexes the state information can be kept in the futex object and we don't need an internal lock, hence the speed-up.

Signature · 1 line
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖