- futex_requeue_pi implementation (requeue from futex1 to PI-futex2)
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
@@ -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
@@ -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
@@ -150,7 +150,8 @@ asmlinkage long compat_sys_futex(u32 __uif (!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
Quoted 7 lines · Pierre Peiffer
With the introduction of the PI-futex (used for the PI-pthread_mutex in the glibc), the current
futex_requeueoptimization (*) can not be used any more if thepthread_mutexused 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