Skip to contentSkip to conversation

- futex_requeue_pi implementation (requeue from futex1 to PI-futex2)

RFC PATCH In review Pierre Peiffer 2 participants 2 messages Dec 13, 2006 Futex

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 - futex_requeue_pi implementation (requeue from futex1 to PI-futex2)

Hi,

With the introduction of the PI-futex (used for the PI-pthread_mutex in the glibc), the current futex_requeue optimization (*) can not be used any more if the pthread_mutex used with the pthread-condvar is a PI-mutex.

(*) this optimization is used in pthread_cond_broadcast.

To use this optimization with PI-mutex, we need a function that re-queues some threads from a normal futex to a PI-futex (see why in this discussion:
http://marc.theaimsgroup.com/?l=linux-kernel&m=115020355126851&w=2 )

Here is a proposal of an implementation of futex_requeue_pi. (Only the 32-bits version has been implemented for now)

To use or test this patch with pthreads, you will need to patch the glibc. The glibc patch is available here:
http://www.bullopensource.org/posix/pi-futex/glibc_requeue_pi.diff
(Only available for ix86 architecture)
or use the generic pthread_cond_broadcast.c file
(patch here:
http://www.bullopensource.org/posix/pi-futex/glibc_pth_broadcast_c_file.diff
)

I'll send some explanations in a separate mail.

The code has been tested and seems to work fine but is probably, heu, "perfectible" ...
So, comments, suggestions, feedbacks are welcome.

---

 include/linux/futex.h   |    8
 kernel/futex.c          |  583 ++++++++++++++++++++++++++++++++++++++++++------
 kernel/futex_compat.c   |    3
 kernel/rtmutex.c        |   43 ---
 kernel/rtmutex_common.h |   36 ++
 5 files changed, 575 insertions(+), 98 deletions(-)

---

---

include/linux/futex.h +7 -1
Index: linux-2.6/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		0x1fffffff
 
 /*
  * This limit protects against a deliberately circular list.
kernel/futex.c +520 -63

779 lines not on this page · raw message

kernel/rtmutex.c +10 -33

73 lines not on this page · raw message

kernel/rtmutex_common.h +36 -0
Index: linux-2.6/kernel/rtmutex_common.h
===================================================================
@@ -113,6 +113,30 @@ 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;
+		cpu_relax();
+	} 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 +144,16 @@ 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,
+			  unsigned long flags);
 #endif
kernel/futex_compat.c +2 -1
Index: linux-2.6/kernel/futex_compat.c
===================================================================
@@ -150,7 +150,8 @@ asmlinkage long compat_sys_futex(u32 __u
 		if (!timespec_valid(&t))
 			return -EINVAL;
 	}
-	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, &t, uaddr2, val2, val3);

Thanks,

Signature · 1 line
Pierre Peiffer
#1 lore raw
Quoted 7 lines · Pierre Peiffer

With the introduction of the PI-futex (used for the PI-pthread_mutex in the glibc), the current futex_requeue optimization (*) can not be used any more if the pthread_mutex used with the pthread-condvar is a PI-mutex.

(*) this optimization is used in pthread_cond_broadcast.

Quoted 7 lines

To use this optimization with PI-mutex, we need a function that re-queues some threads from a normal futex to a PI-futex (see why in this discussion:
http://marc.theaimsgroup.com/?l=linux-kernel&m=115020355126851&w=2 )

Here is a proposal of an implementation of futex_requeue_pi. (Only the 32-bits version has been implemented for now)

the kernel patch looks straightforward and desirable to me. (modulo some minor style-nitpicking observations below.) I'd suggest to implement the 64-bit and compat versions too, unless Jakub can see a hole in the concept or in the implementation.

include/linux/futex.h struct robust_list_head { · line 94

Quoted 2 lines
include/linux/futex.h +1 -1
-#define FUTEX_TID_MASK		0x3fffffff
+#define FUTEX_TID_MASK		0x1fffffff

ABI change but tthis should be fine i think ... right now we dont let PIDs go above 0xffff anyway. It might make sense to lower it to 0x0fffffff, to have one more bit in that word ... just in case.

kernel/futex.c struct futex_q { · line 139

Quoted 2 lines
kernel/futex.c +2 -0
+	/* This waiter is used in case of requeue from a
+	   normal futex to a PI-futex */

please use proper comment style.

kernel/futex.c static int get_futex_key(void *uaddr, un · line 274

Quoted 7 lines
kernel/futex.c +7 -0
+	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);

such multi-line branches need curly braces.

Quoted 5 lines
kernel/futex.c +4 -0
+static inline int lookup_pi_state_for_requeue(u32 __user *uaddr,
+					      struct futex_hash_bucket *hb,
+					      union futex_key *key,
+					      struct futex_pi_state 

**pi_state)

patch line wrap problem? Also, if the function name is so long, you can do:

static inline int
lookup_pi_state_for_requeue(u32 __user *uaddr, struct futex_hash_bucket *hb,

Ingo