futex: Introducing throughput-optimized (TP) futexes

index 9246d9f..0ea1b57 100644
@@ -477,6 +477,35 @@ static void drop_futex_key_refs(union futex_key *key)
 }
 
 /**
+ * futex_setup_timer - set up the sleeping hrtimer.
+ * @time:	ptr to the given timeout value
+ * @timeout:	the hrtimer_sleeper structure to be set up
+ * @flags:	futex flags
+ * @range_ns:	optional range in ns
+ *
+ * Return: Initialized hrtimer_sleeper structure or NULL if no timeout
+ *	   value given
+ */
+static inline struct hrtimer_sleeper *
+futex_setup_timer(ktime_t *time, struct hrtimer_sleeper *timeout,
+		  int flags, u64 range_ns)
+{
+	if (!time)
+		return NULL;
+
+	hrtimer_init_on_stack(&timeout->timer, (flags & FLAGS_CLOCKRT) ?
+			      CLOCK_REALTIME : CLOCK_MONOTONIC,
+			      HRTIMER_MODE_ABS);
+	hrtimer_init_sleeper(timeout, current);
+	if (range_ns)
+		hrtimer_set_expires_range_ns(&timeout->timer, *time, range_ns);
+	else
+		hrtimer_set_expires(&timeout->timer, *time);
+
+	return timeout;
+}
+
+/**
  * get_futex_key() - Get parameters which are the keys for a futex
  * @uaddr:	virtual address of the futex
  * @fshared:	0 for a PROCESS_PRIVATE futex, 1 for PROCESS_SHARED

@@ -2402,7 +2431,7 @@ static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
 static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
 		      ktime_t *abs_time, u32 bitset)
 {
-	struct hrtimer_sleeper timeout, *to = NULL;
+	struct hrtimer_sleeper timeout, *to;
 	struct restart_block *restart;
 	struct futex_hash_bucket *hb;
 	struct futex_q q = futex_q_init;

@@ -2412,17 +2441,8 @@ static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
 		return -EINVAL;
 	q.bitset = bitset;
 
-	if (abs_time) {
-		to = &timeout;
-
-		hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
-				      CLOCK_REALTIME : CLOCK_MONOTONIC,
-				      HRTIMER_MODE_ABS);
-		hrtimer_init_sleeper(to, current);
-		hrtimer_set_expires_range_ns(&to->timer, *abs_time,
-					     current->timer_slack_ns);
-	}
-
+	to = futex_setup_timer(abs_time, &timeout, flags,
+			       current->timer_slack_ns);
 retry:
 	/*
 	 * Prepare to wait on uaddr. On success, holds hb lock and increments

@@ -2502,7 +2522,7 @@ static long futex_wait_restart(struct restart_block *restart)
 static int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
 			 ktime_t *time, int trylock)
 {
-	struct hrtimer_sleeper timeout, *to = NULL;
+	struct hrtimer_sleeper timeout, *to;
 	struct futex_hash_bucket *hb;
 	struct futex_q q = futex_q_init;
 	int res, ret;

@@ -2510,13 +2530,7 @@ static int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
 	if (refill_pi_state_cache())
 		return -ENOMEM;
 
-	if (time) {
-		to = &timeout;
-		hrtimer_init_on_stack(&to->timer, CLOCK_REALTIME,
-				      HRTIMER_MODE_ABS);
-		hrtimer_init_sleeper(to, current);
-		hrtimer_set_expires(&to->timer, *time);
-	}
+	to = futex_setup_timer(time, &timeout, FLAGS_CLOCKRT, 0);
 
 retry:
 	ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q.key, VERIFY_WRITE);

@@ -2811,7 +2825,7 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
 				 u32 val, ktime_t *abs_time, u32 bitset,
 				 u32 __user *uaddr2)
 {
-	struct hrtimer_sleeper timeout, *to = NULL;
+	struct hrtimer_sleeper timeout, *to;
 	struct rt_mutex_waiter rt_waiter;
 	struct rt_mutex *pi_mutex = NULL;
 	struct futex_hash_bucket *hb;

@@ -2825,15 +2839,8 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
 	if (!bitset)
 		return -EINVAL;
 
-	if (abs_time) {
-		to = &timeout;
-		hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
-				      CLOCK_REALTIME : CLOCK_MONOTONIC,
-				      HRTIMER_MODE_ABS);
-		hrtimer_init_sleeper(to, current);
-		hrtimer_set_expires_range_ns(&to->timer, *abs_time,
-					     current->timer_slack_ns);
-	}
+	to = futex_setup_timer(abs_time, &timeout, flags,
+			       current->timer_slack_ns);
 
 	/*
 	 * The waiter is allocated on our stack, manipulated by the requeue

index 4d19052..453143c 100644
@@ -126,7 +126,7 @@ struct sched_attr {
 	u64 sched_period;
 };
 
-struct futex_pi_state;
+struct futex_state;
 struct robust_list_head;
 struct bio_list;
 struct fs_struct;

@@ -1830,7 +1830,7 @@ struct task_struct {
 	struct compat_robust_list_head __user *compat_robust_list;
 #endif
 	struct list_head pi_state_list;
-	struct futex_pi_state *pi_state_cache;
+	struct futex_state *pi_state_cache;
 #endif
 #ifdef CONFIG_PERF_EVENTS
 	struct perf_event_context *perf_event_ctxp[perf_nr_task_contexts];

271 lines not on this page · raw message

index 6f7cb40..7590c7d 100644
@@ -803,6 +803,21 @@ static int get_futex_value_locked(u32 *dest, u32 __user *from)
 	return ret ? -EFAULT : 0;
 }
 
+/*
+ * The equivalents of the above cmpxchg_futex_value_locked() and
+ * get_futex_value_locked which are called without the hash bucket lock
+ * and so can have page fault enabled.
+ */
+static inline int cmpxchg_futex_value(u32 *curval, u32 __user *uaddr,
+				      u32 uval, u32 newval)
+{
+	return futex_atomic_cmpxchg_inatomic(curval, uaddr, uval, newval);
+}
+
+static inline int get_futex_value(u32 *dest, u32 __user *from)
+{
+	return __get_user(*dest, from);
+}
 
 /*
  * PI code:

index 7590c7d..ccec962 100644
@@ -822,6 +822,39 @@ static inline int get_futex_value(u32 *dest, u32 __user *from)
 /*
  * PI code:
  */
+
+/**
+ * task_pi_list_add - add futex state object to a task's pi_state_list
+ * @task : task structure
+ * @state: futex state object
+ */
+static inline void task_pi_list_add(struct task_struct *task,
+				    struct futex_state *state)
+{
+	raw_spin_lock_irq(&task->pi_lock);
+	WARN_ON(!list_empty(&state->list));
+	list_add(&state->list, &task->pi_state_list);
+	state->owner = task;
+	raw_spin_unlock_irq(&task->pi_lock);
+}
+
+/**
+ * task_pi_list_del - delete futex state object from a task's pi_state_list
+ * @state: futex state object
+ * @warn : warn if list is empty when set
+ */
+static inline void task_pi_list_del(struct futex_state *state, const bool warn)
+{
+	struct task_struct *task = state->owner;
+
+	raw_spin_lock_irq(&task->pi_lock);
+	if (warn)
+		WARN_ON(list_empty(&state->list));
+	list_del_init(&state->list);
+	state->owner = NULL;
+	raw_spin_unlock_irq(&task->pi_lock);
+}
+
 static int refill_futex_state_cache(void)
 {
 	struct futex_state *state;

@@ -874,9 +907,7 @@ static void put_futex_state(struct futex_state *state)
 	 * and has cleaned up the futex state already
 	 */
 	if (state->owner) {
-		raw_spin_lock_irq(&state->owner->pi_lock);
-		list_del_init(&state->list);
-		raw_spin_unlock_irq(&state->owner->pi_lock);
+		task_pi_list_del(state, false);
 
 		rt_mutex_proxy_unlock(&state->pi_mutex, state->owner);
 	}

@@ -1397,16 +1428,8 @@ static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this,
 		return ret;
 	}
 
-	raw_spin_lock(&pi_state->owner->pi_lock);
-	WARN_ON(list_empty(&pi_state->list));
-	list_del_init(&pi_state->list);
-	raw_spin_unlock(&pi_state->owner->pi_lock);
-
-	raw_spin_lock(&new_owner->pi_lock);
-	WARN_ON(!list_empty(&pi_state->list));
-	list_add(&pi_state->list, &new_owner->pi_state_list);
-	pi_state->owner = new_owner;
-	raw_spin_unlock(&new_owner->pi_lock);
+	task_pi_list_del(pi_state, true);
+	task_pi_list_add(new_owner, pi_state);
 
 	raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
 

@@ -2211,19 +2234,10 @@ static int fixup_pi_state_owner(u32 __user *uaddr, struct futex_q *q,
 	 * We fixed up user space. Now we need to fix the pi_state
 	 * itself.
 	 */
-	if (pi_state->owner != NULL) {
-		raw_spin_lock_irq(&pi_state->owner->pi_lock);
-		WARN_ON(list_empty(&pi_state->list));
-		list_del_init(&pi_state->list);
-		raw_spin_unlock_irq(&pi_state->owner->pi_lock);
-	}
+	if (pi_state->owner != NULL)
+		task_pi_list_del(pi_state, true);
 
-	pi_state->owner = newowner;
-
-	raw_spin_lock_irq(&newowner->pi_lock);
-	WARN_ON(!list_empty(&pi_state->list));
-	list_add(&pi_state->list, &newowner->pi_state_list);
-	raw_spin_unlock_irq(&newowner->pi_lock);
+	task_pi_list_add(newowner, pi_state);
 	return 0;
 
 	/*

index ccec962..c8ff773 100644
@@ -191,6 +191,10 @@
 #define FLAGS_CLOCKRT		0x02
 #define FLAGS_HAS_TIMEOUT	0x04
 
+enum futex_type {
+	TYPE_PI = 0,
+};
+
 /*
  * Futex state object:
  *  - Priority Inheritance state

@@ -210,6 +214,7 @@ struct futex_state {
 	struct task_struct *owner;
 	atomic_t refcount;
 
+	enum futex_type type;
 	union futex_key key;
 };
 

@@ -903,13 +908,14 @@ static void put_futex_state(struct futex_state *state)
 		return;
 
 	/*
-	 * If state->owner is NULL, the owner is most probably dying
-	 * and has cleaned up the futex state already
+	 * If state->owner is NULL and the type is TYPE_PI, the owner is
+	 * most probably dying and has cleaned up the futex state already.
 	 */
 	if (state->owner) {
 		task_pi_list_del(state, false);
 
-		rt_mutex_proxy_unlock(&state->pi_mutex, state->owner);
+		if (state->type == TYPE_PI)
+			rt_mutex_proxy_unlock(&state->pi_mutex, state->owner);
 	}
 
 	if (current->pi_state_cache)

@@ -1062,7 +1068,7 @@ static int attach_to_pi_state(u32 uval, struct futex_state *pi_state,
 	/*
 	 * Userspace might have messed up non-PI and PI futexes [3]
 	 */
-	if (unlikely(!pi_state))
+	if (unlikely(!pi_state || (pi_state->type != TYPE_PI)))
 		return -EINVAL;
 
 	WARN_ON(!atomic_read(&pi_state->refcount));

@@ -1180,6 +1186,7 @@ static int attach_to_pi_owner(u32 uval, union futex_key *key,
 
 	/* Store the key for possible exit cleanups: */
 	pi_state->key = *key;
+	pi_state->type = TYPE_PI;
 
 	WARN_ON(!list_empty(&pi_state->list));
 	list_add(&pi_state->list, &p->pi_state_list);

index c8ff773..8b9e982 100644
@@ -207,6 +207,11 @@ struct futex_state {
 	struct list_head list;
 
 	/*
+	 * Can link to fs_head in the owning hash bucket.
+	 */
+	struct list_head fs_list;
+
+	/*
 	 * The PI object:
 	 */
 	struct rt_mutex pi_mutex;

@@ -262,11 +267,24 @@ struct futex_q {
  * Hash buckets are shared by all the futex_keys that hash to the same
  * location.  Each key may have multiple futex_q structures, one for each task
  * waiting on a futex.
+ *
+ * Alternatively (in SMP), a key can be associated with a unique futex_state
+ * object where multiple waiters waiting for that futex can queue up in that
+ * futex_state object without using the futex_q structure. A separate
+ * futex_state lock (fs_lock) is used for processing those futex_state objects.
  */
 struct futex_hash_bucket {
 	atomic_t waiters;
 	spinlock_t lock;
 	struct plist_head chain;
+
+#ifdef CONFIG_SMP
+	/*
+	 * Fields for managing futex_state object list
+	 */
+	spinlock_t fs_lock;
+	struct list_head fs_head;
+#endif
 } ____cacheline_aligned_in_smp;
 
 /*

@@ -873,6 +891,8 @@ static int refill_futex_state_cache(void)
 		return -ENOMEM;
 
 	INIT_LIST_HEAD(&state->list);
+	INIT_LIST_HEAD(&state->fs_list);
+
 	/* pi_mutex gets initialized later */
 	state->owner = NULL;
 	atomic_set(&state->refcount, 1);

@@ -3363,6 +3383,10 @@ static int __init futex_init(void)
 		atomic_set(&futex_queues[i].waiters, 0);
 		plist_head_init(&futex_queues[i].chain);
 		spin_lock_init(&futex_queues[i].lock);
+#ifdef CONFIG_SMP
+		INIT_LIST_HEAD(&futex_queues[i].fs_head);
+		spin_lock_init(&futex_queues[i].fs_lock);
+#endif
 	}
 
 	return 0;

index 0b1f716..7f676ac 100644
@@ -20,6 +20,8 @@
 #define FUTEX_WAKE_BITSET	10
 #define FUTEX_WAIT_REQUEUE_PI	11
 #define FUTEX_CMP_REQUEUE_PI	12
+#define FUTEX_LOCK		13
+#define FUTEX_UNLOCK		14
 
 #define FUTEX_PRIVATE_FLAG	128
 #define FUTEX_CLOCK_REALTIME	256

@@ -39,6 +41,8 @@
 					 FUTEX_PRIVATE_FLAG)
 #define FUTEX_CMP_REQUEUE_PI_PRIVATE	(FUTEX_CMP_REQUEUE_PI | \
 					 FUTEX_PRIVATE_FLAG)
+#define FUTEX_LOCK_PRIVATE	(FUTEX_LOCK | FUTEX_PRIVATE_FLAG)
+#define FUTEX_UNLOCK_PRIVATE	(FUTEX_UNLOCK | FUTEX_PRIVATE_FLAG)
 
 /*
  * Support for robust futexes: the kernel cleans up held futexes at

626 lines not on this page · raw message

index 2374cce..2d3ec8d 100644
@@ -1004,7 +1004,7 @@ static struct task_struct * futex_find_get_task(pid_t pid)
 }
 
 /*
- * This task is holding PI mutexes at exit time => bad.
+ * This task is holding PI or TP mutexes at exit time => bad.
  * Kernel cleans up PI-state, but userspace is likely hosed.
  * (Robust-futex cleanup is separate and might save the day for userspace.)
  */

@@ -1021,12 +1021,31 @@ void exit_pi_state_list(struct task_struct *curr)
 	 * We are a ZOMBIE and nobody can enqueue itself on
 	 * pi_state_list anymore, but we have to be careful
 	 * versus waiters unqueueing themselves:
+	 *
+	 * For TP futexes, the only purpose of showing up in the
+	 * pi_state_list is for this function to wake up the serialization
+	 * mutex owner (state->mutex_owner). We don't actually need to take
+	 * the HB lock. The futex state and task struct won't go away as long
+	 * as we hold the pi_lock.
 	 */
 	raw_spin_lock_irq(&curr->pi_lock);
 	while (!list_empty(head)) {
 
 		next = head->next;
 		pi_state = list_entry(next, struct futex_state, list);
+
+		if (pi_state->type == TYPE_TP) {
+			struct task_struct *owner;
+
+			owner = READ_ONCE(pi_state->mutex_owner);
+			WARN_ON(list_empty(&pi_state->list));
+			list_del_init(&pi_state->list);
+			pi_state->owner = NULL;
+			if (owner)
+				wake_up_process(owner);
+			continue;
+		}
+
 		key = pi_state->key;
 		hb = hash_futex(&key);
 		raw_spin_unlock_irq(&curr->pi_lock);

@@ -3183,8 +3202,8 @@ int handle_futex_death(u32 __user *uaddr, struct task_struct *curr, int pi)
 			goto retry;
 
 		/*
-		 * Wake robust non-PI futexes here. The wakeup of
-		 * PI futexes happens in exit_pi_state():
+		 * Wake robust wait-wake futexes here. The wakeup of
+		 * PI and TP futexes happens in exit_pi_state():
 		 */
 		if (!pi && (uval & FUTEX_WAITERS))
 			futex_wake(uaddr, 1, 1, FUTEX_BITSET_MATCH_ANY);

@@ -3325,6 +3344,12 @@ void exit_robust_list(struct task_struct *curr)
  * Unlike the other futexes, the futex_q structures aren't used. Instead,
  * they will queue up in the serialization mutex of the futex state container
  * queued in the hash bucket.
+ *
+ * To handle the exceptional case that the futex owner died, the robust
+ * futexes list mechanism is used to for waking up sleeping top waiter.
+ * Checks are also made in the futex_spin_on_owner() loop for dead task
+ * structure or invalid pid. In both cases, the top waiter will take over
+ * the ownership of the futex.
  */
 
 /**

@@ -3513,6 +3538,10 @@ static inline int futex_set_waiters_bit(u32 __user *uaddr, u32 *puval)
 static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			       struct futex_state *state)
 {
+#define OWNER_DEAD_MESSAGE					\
+	"futex: owner pid %d of TP futex 0x%lx was %s.\n"	\
+	"\tLock is now acquired by pid %d!\n"
+
 	int ret;
 	u32 uval;
 	u32 owner_pid = 0;

@@ -3527,13 +3556,47 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			break;
 
 		if ((uval & FUTEX_TID_MASK) != owner_pid) {
-			if (owner_task)
+			if (owner_task) {
+				/*
+				 * task_pi_list_del() should always be
+				 * done before put_task_struct(). The futex
+				 * state may have been dequeued if the task
+				 * is dead.
+				 */
+				if (state->owner) {
+					WARN_ON(state->owner != owner_task);
+					task_pi_list_del(state, true);
+				}
 				put_task_struct(owner_task);
+			}
 
 			owner_pid  = uval & FUTEX_TID_MASK;
 			owner_task = futex_find_get_task(owner_pid);
 		}
 
+		if (unlikely(!owner_task ||
+			    (owner_task->flags & PF_EXITING) ||
+			    (uval & FUTEX_OWNER_DIED))) {
+			/*
+			 * PID invalid or exiting/dead task, we can directly
+			 * grab the lock now.
+			 */
+			u32 curval;
+			char *owner_state;
+
+			ret = cmpxchg_futex_value_locked(&curval, uaddr, uval,
+							 vpid);
+			if (unlikely(ret))
+				break;
+			if (curval != uval)
+				continue;
+			owner_state = (owner_task || (uval & FUTEX_OWNER_DIED))
+				    ? "dead" : "invalid";
+			pr_info(OWNER_DEAD_MESSAGE, owner_pid,
+				(long)uaddr, owner_state, vpid);
+			break;
+		}
+
 		if (need_resched()) {
 			__set_current_state(TASK_RUNNING);
 			schedule_preempt_disabled();

@@ -3552,12 +3615,17 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 
 		/*
 		 * If the owner isn't active, we need to go to sleep after
-		 * making sure that the FUTEX_WAITERS bit is set.
+		 * making sure that the FUTEX_WAITERS bit is set. We also
+		 * need to put the futex state into the futex owner's
+		 * pi_state_list to prevent deadlock when the owner dies.
 		 */
 		ret = futex_set_waiters_bit(uaddr, &uval);
 		if (ret)
 			break;
 
+		if (owner_task && !state->owner)
+			task_pi_list_add(owner_task, state);
+
 		/*
 		 * Do a trylock after setting the task state to make
 		 * sure we won't miss a wakeup.

@@ -3593,8 +3661,13 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			goto retry;
 	}
 
-	if (owner_task)
+	if (owner_task) {
+		if (state->owner)
+			task_pi_list_del(state, false);
 		put_task_struct(owner_task);
+	} else {
+		WARN_ON(state->owner);
+	}
 
 	/*
 	 * Cleanup futex state.

index 2d3ec8d..711a2b4 100644
@@ -63,6 +63,7 @@
 #include <linux/pid.h>
 #include <linux/nsproxy.h>
 #include <linux/ptrace.h>
+#include <linux/sched.h>
 #include <linux/sched/rt.h>
 #include <linux/hugetlb.h>
 #include <linux/freezer.h>

@@ -235,6 +236,8 @@ struct futex_state {
 	struct task_struct *mutex_owner;	/* For TP futexes only */
 	atomic_t refcount;
 
+	u32 handoff_pid;			/* For TP futexes only */
+
 	enum futex_type type;
 	union futex_key key;
 };

@@ -912,6 +915,7 @@ static int refill_futex_state_cache(void)
 	/* pi_mutex gets initialized later */
 	state->owner = NULL;
 	state->mutex_owner = NULL;
+	state->handoff_pid = 0;
 	atomic_set(&state->refcount, 1);
 	state->key = FUTEX_KEY_INIT;
 

@@ -3335,8 +3339,9 @@ void exit_robust_list(struct task_struct *curr)
  * and unlocking.
  *
  * The purpose of this FUTEX_WAITERS bit is to make the unlocker wake up the
- * serialization mutex owner. Not having the FUTEX_WAITERS bit set doesn't
- * mean there is no waiter in the kernel.
+ * serialization mutex owner or to hand off the lock directly to the top
+ * waiter. Not having the FUTEX_WAITERS bit set doesn't mean there is no
+ * waiter in the kernel.
  *
  * Like PI futexes, TP futexes are orthogonal to robust futexes can be
  * used together.

@@ -3352,6 +3357,16 @@ void exit_robust_list(struct task_struct *curr)
  * the ownership of the futex.
  */
 
+/*
+ * Timeout value for enabling lock handoff and prevent lock starvation.
+ *
+ * Currently, lock handoff will be enabled if the top waiter can't get the
+ * futex after about 5ms. To reduce time checking overhead, it is only done
+ * after every 128 spins or right after wakeup. As a result, the actual
+ * elapsed time will be a bit longer than the specified value.
+ */
+#define TP_HANDOFF_TIMEOUT	5000000	/* 5ms	*/
+
 /**
  * lookup_futex_state - Looking up the futex state structure.
  * @hb:		 hash bucket

@@ -3431,6 +3446,7 @@ static inline int put_futex_state_unlocked(struct futex_state *state)
  * If waiter is true
  * then
  *   don't preserve the flag bits;
+ *   check for handoff (futex word == own pid)
  * else
  *   preserve the flag bits
  * endif

@@ -3449,6 +3465,9 @@ static inline int futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
 
 	uval = *puval;
 
+	if (waiter && (uval & FUTEX_TID_MASK) == vpid)
+		return 1;
+
 	if (uval & FUTEX_TID_MASK)
 		return 0;	/* Trylock fails */
 

@@ -3542,10 +3561,12 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	"futex: owner pid %d of TP futex 0x%lx was %s.\n"	\
 	"\tLock is now acquired by pid %d!\n"
 
-	int ret;
+	int ret, loopcnt = 1;
+	bool handoff_set = false;
 	u32 uval;
 	u32 owner_pid = 0;
 	struct task_struct *owner_task = NULL;
+	u64 handoff_time = sched_clock() + TP_HANDOFF_TIMEOUT;
 
 	preempt_disable();
 	WRITE_ONCE(state->mutex_owner, current);

@@ -3600,6 +3621,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 		if (need_resched()) {
 			__set_current_state(TASK_RUNNING);
 			schedule_preempt_disabled();
+			loopcnt = 0;
 			continue;
 		}
 

@@ -3608,6 +3630,23 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			break;
 		}
 
+		/*
+		 * Enable lock handoff if the elapsed time exceed the timeout
+		 * value. We also need to set the FUTEX_WAITERS bit to make
+		 * sure that futex lock holder will initiate the handoff at
+		 * unlock time.
+		 */
+		if (!handoff_set && !(loopcnt++ & 0x7f)) {
+			if (sched_clock() > handoff_time) {
+				WARN_ON(READ_ONCE(state->handoff_pid));
+				ret = futex_set_waiters_bit(uaddr, &uval);
+				if (ret)
+					break;
+				WRITE_ONCE(state->handoff_pid, vpid);
+				handoff_set = true;
+			}
+		}
+
 		if (owner_task->on_cpu) {
 			cpu_relax();
 			continue;

@@ -3650,8 +3689,10 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 		 * lock stealing happen in between setting the FUTEX_WAITERS
 		 * and setting state to TASK_INTERRUPTIBLE.
 		 */
-		if (!(uval & FUTEX_OWNER_DIED) && (uval & FUTEX_WAITERS))
+		if (!(uval & FUTEX_OWNER_DIED) && (uval & FUTEX_WAITERS)) {
 			schedule_preempt_disabled();
+			loopcnt = 0;
+		}
 		__set_current_state(TASK_RUNNING);
 	}
 

@@ -3673,6 +3714,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	 * Cleanup futex state.
 	 */
 	WRITE_ONCE(state->mutex_owner, NULL);
+	WRITE_ONCE(state->handoff_pid, 0);
 
 	preempt_enable();
 	return ret;

@@ -3787,6 +3829,7 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
 static int futex_unlock(u32 __user *uaddr, unsigned int flags)
 {
 	u32 uval, vpid = task_pid_vnr(current);
+	u32 newpid = 0;
 	union futex_key key = FUTEX_KEY_INIT;
 	struct futex_hash_bucket *hb;
 	struct futex_state *state = NULL;

@@ -3820,6 +3863,10 @@ static int futex_unlock(u32 __user *uaddr, unsigned int flags)
 		goto out_put_key;
 	}
 
+	newpid = READ_ONCE(state->handoff_pid);
+	if (newpid)
+		WRITE_ONCE(state->handoff_pid, 0);
+
 	owner = READ_ONCE(state->mutex_owner);
 	if (owner)
 		wake_q_add(&wake_q, owner);

@@ -3827,13 +3874,13 @@ static int futex_unlock(u32 __user *uaddr, unsigned int flags)
 	spin_unlock(&hb->fs_lock);
 
 	/*
-	 * Unlock the futex.
+	 * Unlock the futex or handoff to the next owner.
 	 * The flag bits are not preserved to encourage more lock stealing.
 	 */
 	for (;;) {
 		u32 old = uval;
 
-		if (cmpxchg_futex_value(&uval, uaddr, old, 0)) {
+		if (cmpxchg_futex_value(&uval, uaddr, old, newpid)) {
 			ret = -EFAULT;
 			break;
 		}

index 711a2b4..3308cc3 100644
@@ -3367,7 +3367,23 @@ void exit_robust_list(struct task_struct *curr)
  */
 #define TP_HANDOFF_TIMEOUT	5000000	/* 5ms	*/
 
-/**
+/*
+ * The futex_lock() function returns the internal status of the TP futex.
+ * The status code consists of the following 3 fields:
+ * 1) bits 00-07: code on how the lock is acquired
+ *		   0 - steals the lock
+ *		   1 - top waiter (mutex owner) acquires the lock
+ *		   2 - handed off the lock
+ * 2) bits 08-15: reserved
+ * 3) bits 15-30: how many times the task has slept or yield to scheduler
+ *		  in futex_spin_on_owner().
+ */
+#define TP_LOCK_STOLEN		0
+#define TP_LOCK_ACQUIRED	1
+#define TP_LOCK_HANDOFF		2
+#define TP_STATUS_SLEEP(val, sleep)	((val)|((sleep) << 16))
+
+ /**
  * lookup_futex_state - Looking up the futex state structure.
  * @hb:		 hash bucket
  * @key:	 futex key

@@ -3451,9 +3467,11 @@ static inline int put_futex_state_unlocked(struct futex_state *state)
  *   preserve the flag bits
  * endif
  *
- * Return: 1 if lock acquired;
+ * Return: TP_LOCK_ACQUIRED if lock acquired;
+ *	   TP_LOCK_HANDOFF if lock was handed off;
  *	   0 if lock acquisition failed;
  *	   -EFAULT if an error happened.
+ *	   *puval will contain the latest futex value when trylock fails.
  */
 static inline int futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
 				const bool waiter)

@@ -3466,7 +3484,7 @@ static inline int futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
 	uval = *puval;
 
 	if (waiter && (uval & FUTEX_TID_MASK) == vpid)
-		return 1;
+		return TP_LOCK_HANDOFF;
 
 	if (uval & FUTEX_TID_MASK)
 		return 0;	/* Trylock fails */

@@ -3477,7 +3495,7 @@ static inline int futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
 	if (unlikely(cmpxchg_futex_value(puval, uaddr, uval, vpid|flags)))
 		return -EFAULT;
 
-	return *puval == uval;
+	return (*puval == uval) ? TP_LOCK_ACQUIRED : 0;
 }
 
 /**

@@ -3491,7 +3509,8 @@ static inline int futex_trylock(u32 __user *uaddr, const u32 vpid, u32 *puval,
  * of faulting in the futex word. This function should only be called from
  * within futex_spin_on_owner().
  *
- * Return: 1 if lock acquired;
+ * Return: TP_LOCK_ACQUIRED if lock acquired;
+ *	   TP_LOCK_HANDOFF if lock was handed off;
  *	   0 if lock acquisition failed;
  *	   -EFAULT if an error happened.
  */

@@ -3552,7 +3571,7 @@ static inline int futex_set_waiters_bit(u32 __user *uaddr, u32 *puval)
  * unless the pid wraps around and the perceived owner is not the real owner.
  * To guard against this case, we will have to use the robust futex feature.
  *
- * Return: 0 if futex acquired, < 0 if an error happens.
+ * Return: TP status code if lock acquired, < 0 if an error happens.
  */
 static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			       struct futex_state *state)

@@ -3562,6 +3581,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	"\tLock is now acquired by pid %d!\n"
 
 	int ret, loopcnt = 1;
+	int nsleep = 0;
 	bool handoff_set = false;
 	u32 uval;
 	u32 owner_pid = 0;

@@ -3621,6 +3641,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 		if (need_resched()) {
 			__set_current_state(TASK_RUNNING);
 			schedule_preempt_disabled();
+			nsleep++;
 			loopcnt = 0;
 			continue;
 		}

@@ -3691,6 +3712,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 		 */
 		if (!(uval & FUTEX_OWNER_DIED) && (uval & FUTEX_WAITERS)) {
 			schedule_preempt_disabled();
+			nsleep++;
 			loopcnt = 0;
 		}
 		__set_current_state(TASK_RUNNING);

@@ -3717,7 +3739,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	WRITE_ONCE(state->handoff_pid, 0);
 
 	preempt_enable();
-	return ret;
+	return (ret < 0) ? ret : TP_STATUS_SLEEP(ret, nsleep);
 }
 
 /*

@@ -3731,8 +3753,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
  * This function is not inlined so that it can show up separately in perf
  * profile for performance analysis purpose.
  *
- * Return: 0   - lock acquired
- *	   < 0 - an error happens
+ * Return: TP status code if lock acquired, < 0 if an error happens.
  */
 static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
 {

@@ -3747,7 +3768,7 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
 	 */
 	ret = futex_trylock(uaddr, vpid, &uval, false);
 	if (ret)
-		goto out;
+		return (ret < 0) ? ret : TP_LOCK_STOLEN;
 
 	/*
 	 * Detect deadlocks.

@@ -3815,7 +3836,7 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
 	put_futex_key(&key);
 
 out:
-	return (ret < 0) ? ret : 0;
+	return ret;
 }
 
 /*

index 3308cc3..429d85f 100644
@@ -3556,9 +3556,10 @@ static inline int futex_set_waiters_bit(u32 __user *uaddr, u32 *puval)
 
 /**
  * futex_spin_on_owner - Optimistically spin on futex owner
- * @uaddr: futex address
- * @vpid:  PID of current task
- * @state: futex state object
+ * @uaddr:   futex address
+ * @vpid:    PID of current task
+ * @state:   futex state object
+ * @timeout: hrtimer_sleeper structure
  *
  * Spin on the futex word while the futex owner is active. Otherwise, set
  * the FUTEX_WAITERS bit and go to sleep.

@@ -3574,7 +3575,8 @@ static inline int futex_set_waiters_bit(u32 __user *uaddr, u32 *puval)
  * Return: TP status code if lock acquired, < 0 if an error happens.
  */
 static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
-			       struct futex_state *state)
+			       struct futex_state *state,
+			       struct hrtimer_sleeper *timeout)
 {
 #define OWNER_DEAD_MESSAGE					\
 	"futex: owner pid %d of TP futex 0x%lx was %s.\n"	\

@@ -3646,6 +3648,12 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 			continue;
 		}
 
+
+		if (timeout && !timeout->task) {
+			ret = -ETIMEDOUT;
+			break;
+		}
+
 		if (signal_pending(current)) {
 			ret = -EINTR;
 			break;

@@ -3753,10 +3761,18 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
  * This function is not inlined so that it can show up separately in perf
  * profile for performance analysis purpose.
  *
+ * The timeout functionality isn't as precise as other other futex types
+ * as timer expiration will not be detected while waiting in the
+ * serialization mutex. One possible solution is to modify the expiration
+ * function to send out a signal as well so as to break the thread out of
+ * the mutex code if we really want more precise timeout.
+ *
  * Return: TP status code if lock acquired, < 0 if an error happens.
  */
-static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
+static noinline int
+futex_lock(u32 __user *uaddr, unsigned int flags, ktime_t *time)
 {
+	struct hrtimer_sleeper timeout, *to;
 	struct futex_hash_bucket *hb;
 	union futex_key key = FUTEX_KEY_INIT;
 	struct futex_state *state;

@@ -3780,6 +3796,8 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
 	if (refill_futex_state_cache())
 		return -ENOMEM;
 
+	to = futex_setup_timer(time, &timeout, flags, current->timer_slack_ns);
+
 	ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, VERIFY_WRITE);
 	if (unlikely(ret))
 		goto out;

@@ -3805,6 +3823,9 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
 		goto out_put_state_key;
 	}
 
+	if (to)
+		hrtimer_start_expires(&to->timer, HRTIMER_MODE_ABS);
+
 	/*
 	 * Acquiring the serialization mutex.
 	 *

@@ -3816,10 +3837,19 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
 		goto out_put_state_key;
 
 	/*
+	 * Check for timeout.
+	 */
+	if (to && !timeout.task) {
+		ret = -ETIMEDOUT;
+		mutex_unlock(&state->mutex);
+		goto out_put_state_key;
+	}
+
+	/*
 	 * As the mutex owner, we can now spin on the futex word as well as
 	 * the active-ness of the futex owner.
 	 */
-	ret = futex_spin_on_owner(uaddr, vpid, state);
+	ret = futex_spin_on_owner(uaddr, vpid, state, to);
 
 	mutex_unlock(&state->mutex);
 

@@ -3836,6 +3866,10 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags)
 	put_futex_key(&key);
 
 out:
+	if (to) {
+		hrtimer_cancel(&to->timer);
+		destroy_hrtimer_on_stack(&to->timer);
+	}
 	return ret;
 }
 

@@ -3989,7 +4023,7 @@ long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
 		return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 1);
 #ifdef CONFIG_SMP
 	case FUTEX_LOCK:
-		return futex_lock(uaddr, flags);
+		return futex_lock(uaddr, flags, timeout);
 	case FUTEX_UNLOCK:
 		return futex_unlock(uaddr, flags);
 #endif

@@ -4008,7 +4042,7 @@ long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
 	int cmd = op & FUTEX_CMD_MASK;
 
 	if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
-		      cmd == FUTEX_WAIT_BITSET ||
+		      cmd == FUTEX_WAIT_BITSET || cmd == FUTEX_LOCK ||
 		      cmd == FUTEX_WAIT_REQUEUE_PI)) {
 		if (unlikely(should_fail_futex(!(op & FUTEX_PRIVATE_FLAG))))
 			return -EFAULT;

index 579a592..b0632df 100644
@@ -36,6 +36,7 @@
 int bench_futex_requeue(int argc, const char **argv, const char *prefix);
 /* pi futexes */
 int bench_futex_lock_pi(int argc, const char **argv, const char *prefix);
+int bench_futex_mutex(int argc, const char **argv, const char *prefix);
 
 #define BENCH_FORMAT_DEFAULT_STR	"default"
 #define BENCH_FORMAT_DEFAULT		0

844 lines not on this page · raw message

index ba7c735..be1eb7a 100644
@@ -87,6 +87,29 @@
 		 val, opflags);
 }
 
+#ifndef FUTEX_LOCK
+#define FUTEX_LOCK	0xff	/* Disable the use of TP futexes */
+#define FUTEX_UNLOCK	0xff
+#endif /* FUTEX_LOCK */
+
+/**
+ * futex_lock() - lock the TP futex
+ */
+static inline int
+futex_lock(u_int32_t *uaddr, struct timespec *timeout, int opflags)
+{
+	return futex(uaddr, FUTEX_LOCK, 0, timeout, NULL, 0, opflags);
+}
+
+/**
+ * futex_unlock() - unlock the TP futex
+ */
+static inline int
+futex_unlock(u_int32_t *uaddr, int opflags)
+{
+	return futex(uaddr, FUTEX_UNLOCK, 0, NULL, NULL, 0, opflags);
+}
+
 #ifndef HAVE_PTHREAD_ATTR_SETAFFINITY_NP
 #include <pthread.h>
 static inline int pthread_attr_setaffinity_np(pthread_attr_t *attr,

index a1cddc6..bf4418d 100644
@@ -20,6 +20,7 @@
 #include "builtin.h"
 #include "bench/bench.h"
 
+#include <locale.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

@@ -62,6 +63,7 @@ struct bench {
 	{ "requeue",	"Benchmark for futex requeue calls",            bench_futex_requeue	},
 	/* pi-futexes */
 	{ "lock-pi",	"Benchmark for futex lock_pi calls",            bench_futex_lock_pi	},
+	{ "mutex",	"Benchmark for mutex locks using futexes",	bench_futex_mutex	},
 	{ "all",	"Run all futex benchmarks",			NULL			},
 	{ NULL,		NULL,						NULL			}
 };

@@ -215,6 +217,7 @@ int cmd_bench(int argc, const char **argv, const char *prefix __maybe_unused)
 {
 	struct collection *coll;
 	int ret = 0;
+	char *locale;
 
 	if (argc < 2) {
 		/* No collection specified. */

@@ -222,6 +225,13 @@ int cmd_bench(int argc, const char **argv, const char *prefix __maybe_unused)
 		goto end;
 	}
 
+	/*
+	 * Enable better number formatting.
+	 */
+	locale = setlocale(LC_NUMERIC, "");
+	if (!strcmp(locale, "C"))
+		setlocale(LC_NUMERIC, "en_US");
+
 	argc = parse_options(argc, argv, bench_options, bench_usage,
 			     PARSE_OPT_STOP_AT_NON_OPTION);
 

index 7f676ac..1a22ecc 100644
@@ -22,6 +22,8 @@
 #define FUTEX_CMP_REQUEUE_PI	12
 #define FUTEX_LOCK		13
 #define FUTEX_UNLOCK		14
+#define FUTEX_LOCK_SHARED	15
+#define FUTEX_UNLOCK_SHARED	16
 
 #define FUTEX_PRIVATE_FLAG	128
 #define FUTEX_CLOCK_REALTIME	256

@@ -43,6 +45,9 @@
 					 FUTEX_PRIVATE_FLAG)
 #define FUTEX_LOCK_PRIVATE	(FUTEX_LOCK | FUTEX_PRIVATE_FLAG)
 #define FUTEX_UNLOCK_PRIVATE	(FUTEX_UNLOCK | FUTEX_PRIVATE_FLAG)
+#define FUTEX_LOCK_SHARED_PRIVATE	(FUTEX_LOCK_SHARED | FUTEX_PRIVATE_FLAG)
+#define FUTEX_UNLOCK_SHARED_PRIVATE	(FUTEX_UNLOCK_SHARED | \
+					 FUTEX_PRIVATE_FLAG)
 
 /*
  * Support for robust futexes: the kernel cleans up held futexes at

@@ -111,9 +116,28 @@ struct robust_list_head {
 #define FUTEX_OWNER_DIED	0x40000000
 
 /*
- * The rest of the robust-futex field is for the TID:
+ * Shared locking bit (for readers).
+ * Robust futexes cannot be used in combination with shared locking.
+ *
+ * The FUTEX_SHARED_UNLOCK bit can be set by userspace to indicate that
+ * an shared unlock is in progress and so no shared locking is allowed
+ * within the kernel.
+ */
+#define FUTEX_SHARED		0x20000000
+#define FUTEX_SHARED_UNLOCK	0x10000000
+
+/*
+ * The rest of the bits is for the TID or, in the case of readers, the
+ * shared locking bit and the numbers of active readers present. IOW, the
+ * max supported TID is actually 0x1fffffff. Only 24 bits are used for
+ * tracking the number of shared futex owners. Bits 24-27 may be used by
+ * the userspace for internal management purpose. However, a successful
+ * FUTEX_UNLOCK_SHARED futex(2) syscall will clear or alter those bits.
  */
-#define FUTEX_TID_MASK		0x3fffffff
+#define FUTEX_TID_MASK		0x1fffffff
+#define FUTEX_SCNT_MASK		0x00ffffff	/* Shared futex owner count */
+#define FUTEX_SHARED_TID_MASK	0x3fffffff	/* FUTEX_SHARED bit + TID   */
+#define FUTEX_SHARED_SCNT_MASK	0x20ffffff	/* FUTEX_SHARED bit + count */
 
 /*
  * This limit protects against a deliberately circular list.

413 lines not on this page · raw message

index ee35264..b690a79 100644
@@ -237,6 +237,7 @@ struct futex_state {
 	atomic_t refcount;
 
 	u32 handoff_pid;			/* For TP futexes only */
+	int locksteal_disabled;			/* For TP futexes only */
 
 	enum futex_type type;
 	union futex_key key;

@@ -3436,6 +3437,7 @@ void exit_robust_list(struct task_struct *curr)
 	state = alloc_futex_state();
 	state->type = TYPE_TP;
 	state->key = *key;
+	state->locksteal_disabled = false;
 	list_add(&state->fs_list, &hb->fs_head);
 	WARN_ON(atomic_read(&state->refcount) != 1);
 

@@ -3781,9 +3783,10 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 				WRITE_ONCE(state->handoff_pid, vpid);
 
 				/*
-				 * Disable handoff check.
+				 * Disable handoff check and reader lock
+				 * stealing.
 				 */
-				handoff_set = true;
+				state->locksteal_disabled = handoff_set = true;
 			}
 		}
 

@@ -3886,6 +3889,7 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	 */
 	WRITE_ONCE(state->mutex_owner, NULL);
 	WRITE_ONCE(state->handoff_pid, 0);
+	state->locksteal_disabled = false;
 
 	preempt_enable();
 	return (ret < 0) ? ret : TP_STATUS_SLEEP(ret, nsleep);

@@ -3966,6 +3970,21 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags,
 		goto out_put_state_key;
 	}
 
+	/*
+	 * For reader, we will try to steal the lock here as if it is the
+	 * top waiter without taking the serialization mutex if reader
+	 * lock stealing isn't disabled even though the FUTEX_WAITERS bit
+	 * is set.
+	 */
+	if (shared && !state->locksteal_disabled) {
+		ret = futex_trylock(uaddr, vpid, &uval, true);
+		if (ret) {
+			if (ret > 0)
+				ret = TP_LOCK_STOLEN;
+			goto out_put_state_key;
+		}
+	}
+
 	if (to)
 		hrtimer_start_expires(&to->timer, HRTIMER_MODE_ABS);
 

index b690a79..5e69c44 100644
@@ -239,6 +239,16 @@ struct futex_state {
 	u32 handoff_pid;			/* For TP futexes only */
 	int locksteal_disabled;			/* For TP futexes only */
 
+	/*
+	 * To improve reader throughput in TP futexes, all the readers
+	 * in the mutex queue are grouped together. The first reader in the
+	 * queue will set first_reader, then the rest of the readers will
+	 * spin on the first reader via the OSQ without actually entering
+	 * the mutex queue.
+	 */
+	struct optimistic_spin_queue reader_osq;
+	struct task_struct *first_reader;
+
 	enum futex_type type;
 	union futex_key key;
 };

@@ -3388,14 +3398,21 @@ void exit_robust_list(struct task_struct *curr)
  *		   0 - steals the lock
  *		   1 - top waiter (mutex owner) acquires the lock
  *		   2 - handed off the lock
- * 2) bits 08-15: reserved
- * 3) bits 15-30: how many times the task has slept or yield to scheduler
+ * 2) bit  08:	  1 if reader spins alone		(shared lock only)
+ *    bit  09:	  1 if reader is a spin group leader	(shared lock only)
+ *    bits 10-16: reserved
+ * 3) bits 16-30: how many times the task has slept or yield to scheduler
  *		  in futex_spin_on_owner().
  */
 #define TP_LOCK_STOLEN		0
 #define TP_LOCK_ACQUIRED	1
 #define TP_LOCK_HANDOFF		2
+
+#define TP_READER_ALONE		1
+#define TP_READER_GROUP		2
+
 #define TP_STATUS_SLEEP(val, sleep)	((val)|((sleep) << 16))
+#define TP_STATUS_ALONE(val, alone)	((val)|((alone) << 8))
 
 /**
  * lookup_futex_state - Looking up the futex state structure.

@@ -3438,6 +3455,7 @@ void exit_robust_list(struct task_struct *curr)
 	state->type = TYPE_TP;
 	state->key = *key;
 	state->locksteal_disabled = false;
+	osq_lock_init(&state->reader_osq);
 	list_add(&state->fs_list, &hb->fs_head);
 	WARN_ON(atomic_read(&state->refcount) != 1);
 

@@ -3895,6 +3913,98 @@ static int futex_spin_on_owner(u32 __user *uaddr, const u32 vpid,
 	return (ret < 0) ? ret : TP_STATUS_SLEEP(ret, nsleep);
 }
 
+/**
+ * futex_spin_on_reader - Optimistically spin on first reader
+ * @uaddr:   futex address
+ * @pfirst:  pointer to first reader
+ * @state:   futex state object
+ * @timeout: hrtimer_sleeper structure
+ *
+ * Reader performance will depend on the placement of readers within the
+ * mutex queue. For a queue of 4 readers and 4 writers, for example, the
+ * optimal placement will be either RRRRWWWW or WWWWRRRR. A worse case will
+ * be RWRWRWRW.
+ *
+ * One way to avoid the worst case scenario is to gather all the readers
+ * together as a single unit and place it into the mutex queue. This is done
+ * by having the first reader puts its task structure into state->first_reader
+ * and the rest of the readers optimistically spin on it instead of entering
+ * the mutex queue.
+ *
+ * On exit from this function, the reader would have
+ *  1) acquired a read lock on the futex;
+ *  2) become the first reader and goes into the mutex queue; or
+ *  3) seen the first reader slept and needs to go into the mutex queue alone.
+ *
+ * Any fault on accessing the futex will cause it to return 0 and goes into
+ * the mutex queue.
+ *
+ * Return:  > 0 - acquired the read lock
+ *	   <= 0 - need to goes into the mutex queue
+ */
+static int futex_spin_on_reader(u32 __user *uaddr, struct task_struct **pfirst,
+				struct futex_state *state,
+				struct hrtimer_sleeper *timeout)
+{
+	struct task_struct *first_reader;
+	int ret = 0;
+
+	preempt_disable();
+
+retry:
+	first_reader = READ_ONCE(state->first_reader);
+	if (!first_reader)
+		first_reader = cmpxchg(&state->first_reader, NULL, current);
+	if (!first_reader)
+		goto out;	/* Became the first reader */
+
+	if (!osq_lock(&state->reader_osq))
+		goto reschedule;
+
+	for (;;) {
+		u32 uval;
+
+		if (!state->locksteal_disabled) {
+			ret = futex_trylock_preempt_disabled(uaddr,
+						FUTEX_SHARED, &uval);
+			/*
+			 * Return if lock acquired or an error happened
+			 */
+			if (ret)
+				break;
+		}
+
+		/*
+		 * Reread the first reader value again.
+		 */
+		first_reader = READ_ONCE(state->first_reader);
+		if (!first_reader)
+			first_reader = cmpxchg(&state->first_reader, NULL,
+						current);
+		if (!first_reader || !first_reader->on_cpu)
+			break;
+
+		if (need_resched()) {
+			osq_unlock(&state->reader_osq);
+			goto reschedule;
+		}
+
+		cpu_relax();
+	}
+	osq_unlock(&state->reader_osq);
+out:
+	*pfirst = first_reader;
+	preempt_enable();
+	return ret;
+
+reschedule:
+	/*
+	 * Yield the CPU and retry later.
+	 */
+	schedule_preempt_disabled();
+	goto retry;
+}
+
 /*
  * Userspace tried a 0 -> TID atomic transition of the futex value
  * and failed. The kernel side here does the whole locking operation.

@@ -3921,9 +4031,11 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags,
 {
 	struct hrtimer_sleeper timeout, *to;
 	struct futex_hash_bucket *hb;
+	struct task_struct *first_reader = NULL;
 	union futex_key key = FUTEX_KEY_INIT;
 	struct futex_state *state;
 	u32 uval, vpid = shared ? FUTEX_SHARED : task_pid_vnr(current);
+	int alone = 0;
 	int ret;
 
 	/*

@@ -3989,6 +4101,17 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags,
 		hrtimer_start_expires(&to->timer, HRTIMER_MODE_ABS);
 
 	/*
+	 * Spin on the first reader and return if we acquired the read lock.
+	 */
+	if (shared) {
+		int rspin_ret = futex_spin_on_reader(uaddr, &first_reader,
+						     state, to);
+		if (rspin_ret > 0)
+			goto out_put_state_key;
+		alone = first_reader ? TP_READER_ALONE : TP_READER_GROUP;
+	}
+
+	/*
 	 * Acquiring the serialization mutex.
 	 *
 	 * If we got a signal or has some other error, we need to abort

@@ -4016,6 +4139,12 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags,
 	mutex_unlock(&state->mutex);
 
 out_put_state_key:
+	/*
+	 * We will be the first reader if (first_reader == NULL).
+	 */
+	if (shared && !first_reader)
+		WRITE_ONCE(state->first_reader, NULL);
+
 	if (!put_futex_state_unlocked(state)) {
 		/*
 		 * May need to free the futex state object and so must be

@@ -4032,7 +4161,7 @@ static noinline int futex_lock(u32 __user *uaddr, unsigned int flags,
 		hrtimer_cancel(&to->timer);
 		destroy_hrtimer_on_stack(&to->timer);
 	}
-	return ret;
+	return (ret < 0) ? ret : TP_STATUS_ALONE(ret, alone);
 }
 
 /*

index b0632df..a7e2037 100644
@@ -37,6 +37,7 @@
 /* pi futexes */
 int bench_futex_lock_pi(int argc, const char **argv, const char *prefix);
 int bench_futex_mutex(int argc, const char **argv, const char *prefix);
+int bench_futex_rwlock(int argc, const char **argv, const char *prefix);
 
 #define BENCH_FORMAT_DEFAULT_STR	"default"
 #define BENCH_FORMAT_DEFAULT		0

1,000 lines not on this page · raw message

index be1eb7a..199cc77 100644
@@ -88,8 +88,10 @@
 }
 
 #ifndef FUTEX_LOCK
-#define FUTEX_LOCK	0xff	/* Disable the use of TP futexes */
-#define FUTEX_UNLOCK	0xff
+#define FUTEX_LOCK		0xff	/* Disable the use of TP futexes */
+#define FUTEX_UNLOCK		0xff
+#define FUTEX_LOCK_SHARED	0xff
+#define FUTEX_UNLOCK_SHARED	0xff
 #endif /* FUTEX_LOCK */
 
 /**

@@ -110,6 +112,24 @@
 	return futex(uaddr, FUTEX_UNLOCK, 0, NULL, NULL, 0, opflags);
 }
 
+/**
+ * futex_lock_shared() - shared locking of TP futex
+ */
+static inline int
+futex_lock_shared(u_int32_t *uaddr, struct timespec *timeout, int opflags)
+{
+	return futex(uaddr, FUTEX_LOCK_SHARED, 0, timeout, NULL, 0, opflags);
+}
+
+/**
+ * futex_unlock_shared() - shared unlocking of TP futex
+ */
+static inline int
+futex_unlock_shared(u_int32_t *uaddr, int opflags)
+{
+	return futex(uaddr, FUTEX_UNLOCK_SHARED, 0, NULL, NULL, 0, opflags);
+}
+
 #ifndef HAVE_PTHREAD_ATTR_SETAFFINITY_NP
 #include <pthread.h>
 static inline int pthread_attr_setaffinity_np(pthread_attr_t *attr,

index bf4418d..424a014 100644
@@ -64,6 +64,7 @@ struct bench {
 	/* pi-futexes */
 	{ "lock-pi",	"Benchmark for futex lock_pi calls",            bench_futex_lock_pi	},
 	{ "mutex",	"Benchmark for mutex locks using futexes",	bench_futex_mutex	},
+	{ "rwlock",	"Benchmark for rwlocks using futexes",		bench_futex_rwlock	},
 	{ "all",	"Run all futex benchmarks",			NULL			},
 	{ NULL,		NULL,						NULL			}
 };

index 453143c..eeb6d5a 100644
@@ -1038,7 +1038,7 @@ struct wake_q_head {
 
 extern void wake_q_add(struct wake_q_head *head,
 		       struct task_struct *task);
-extern void wake_up_q(struct wake_q_head *head);
+extern int wake_up_q(struct wake_q_head *head);
 
 /*
  * sched-domains (multiprocessor balancing) declarations:

index 5e69c44..4f235e8 100644
@@ -4254,11 +4254,9 @@ static int futex_unlock(u32 __user *uaddr, unsigned int flags,
 out_put_key:
 	put_futex_key(&key);
 	if (owner) {
-		/*
-		 * No error would have happened if owner defined.
-		 */
-		wake_up_q(&wake_q);
-		return ret ? ret : 1;
+		int cnt = wake_up_q(&wake_q);
+
+		return ret ? ret : cnt;
 	}
 
 	return ret;

index 966556e..eed7a15 100644
@@ -449,9 +449,10 @@ void wake_q_add(struct wake_q_head *head, struct task_struct *task)
 	head->lastp = &node->next;
 }
 
-void wake_up_q(struct wake_q_head *head)
+int wake_up_q(struct wake_q_head *head)
 {
 	struct wake_q_node *node = head->first;
+	int wakecnt = 0;
 
 	while (node != WAKE_Q_TAIL) {
 		struct task_struct *task;

@@ -466,9 +467,10 @@ void wake_up_q(struct wake_q_head *head)
 		 * wake_up_process() implies a wmb() to pair with the queueing
 		 * in wake_q_add() so as not to miss wakeups.
 		 */
-		wake_up_process(task);
+		wakecnt += wake_up_process(task);
 		put_task_struct(task);
 	}
+	return wakecnt;
 }
 
 /*

index 4f235e8..9f7bfd3 100644
@@ -4425,3 +4425,85 @@ static int __init futex_init(void)
 	return 0;
 }
 __initcall(futex_init);
+
+#if defined(CONFIG_DEBUG_FS) && defined(CONFIG_SMP)
+/*
+ * Debug code to dump selected content of in-kernel futex hash bucket table.
+ */
+#include <linux/debugfs.h>
+
+static int futex_dump_show(struct seq_file *m, void *arg)
+{
+	struct futex_hash_bucket *hb = arg;
+	struct futex_state *state;
+	int i;
+
+	if (list_empty(&hb->fs_head))
+		return 0;
+
+	seq_printf(m, "\nHash bucket %ld:\n", hb - futex_queues);
+	spin_lock(&hb->fs_lock);
+	i = 0;
+	list_for_each_entry(state, &hb->fs_head, fs_list) {
+		seq_printf(m, "  Futex state %d\n", i++);
+		if (state->owner)
+			seq_printf(m, "    owner PID = %d\n",
+				   task_pid_vnr(state->owner));
+		if (state->mutex_owner)
+			seq_printf(m, "    mutex owner PID = %d\n",
+				   task_pid_vnr(state->mutex_owner));
+		seq_printf(m, "    reference count = %d\n",
+			   atomic_read(&state->refcount));
+		seq_printf(m, "    handoff PID = %d\n", state->handoff_pid);
+	}
+	spin_unlock(&hb->fs_lock);
+	return 0;
+}
+
+static void *futex_dump_start(struct seq_file *m, loff_t *pos)
+{
+	return (*pos < futex_hashsize) ? &futex_queues[*pos] : NULL;
+}
+
+static void *futex_dump_next(struct seq_file *m, void *arg, loff_t *pos)
+{
+	(*pos)++;
+	return (*pos < futex_hashsize) ? &futex_queues[*pos] : NULL;
+}
+
+static void futex_dump_stop(struct seq_file *m, void *arg)
+{
+}
+
+static const struct seq_operations futex_dump_op = {
+	.start = futex_dump_start,
+	.next  = futex_dump_next,
+	.stop  = futex_dump_stop,
+	.show  = futex_dump_show,
+};
+
+static int futex_dump_open(struct inode *inode, struct file *file)
+{
+	return seq_open(file, &futex_dump_op);
+}
+
+static const struct file_operations fops_futex_dump = {
+	.open	 = futex_dump_open,
+	.read	 = seq_read,
+	.llseek	 = seq_lseek,
+	.release = seq_release,
+};
+
+/*
+ * Initialize debugfs for the futex hash bucket table dump.
+ */
+static int __init init_futex_dump(void)
+{
+	if (!debugfs_create_file("futex_hash_table", 0400, NULL, NULL,
+				 &fops_futex_dump))
+		return -ENOMEM;
+	return 0;
+}
+fs_initcall(init_futex_dump);
+
+#endif /* CONFIG_DEBUG_FS && CONFIG_SMP */