Re: [PATCH-tip v6 18/22] TP-futex: Group readers together in wait queue

[kbuild test robot]

Hi Waiman,

[auto build test ERROR on next-20170323]
[also build test ERROR on v4.11-rc3]
[cannot apply to linus/master linux/master tip/perf/core v4.9-rc8 v4.9-rc7 
v4.9-rc6]
[if your patch is applied to the wrong git tree, please drop us a note to help 
improve the system]

url:
https://github.com/0day-ci/linux/commits/Waiman-Long/perf-bench-New-microbenchmark-for-userspace-mutex-performance/20170324-135043
config: ia64-defconfig (attached as .config)
compiler: ia64-linux-gcc (GCC) 6.2.0
reproduce:
wget 
https://raw.githubusercontent.com/01org/lkp-tests/master/sbin/make.cross -O 
~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=ia64 

All errors (new ones prefixed by >>):

   kernel/built-in.o: In function `futex_lock':
>> futex.c:(.text+0xfa4a2): undefined reference to `osq_lock'
>> futex.c:(.text+0xfae22): undefined reference to `osq_unlock'
   futex.c:(.text+0xfaf02): undefined reference to `osq_unlock'
   futex.c:(.text+0xfb502): undefined reference to `osq_lock'
   futex.c:(.text+0xfb9e2): undefined reference to `osq_unlock'

---
0-DAY kernel test infrastructureOpen Source Technology Center
https://lists.01.org/pipermail/kbuild-all   Intel Corporation


.config.gz
Description: application/gzip

Re: [PATCH-tip v6 18/22] TP-futex: Group readers together in wait queue

[kbuild test robot]

Hi Waiman,

[auto build test ERROR on next-20170323]
[also build test ERROR on v4.11-rc3]
[cannot apply to linus/master linux/master tip/perf/core v4.9-rc8 v4.9-rc7 
v4.9-rc6]
[if your patch is applied to the wrong git tree, please drop us a note to help 
improve the system]

url:
https://github.com/0day-ci/linux/commits/Waiman-Long/perf-bench-New-microbenchmark-for-userspace-mutex-performance/20170324-135043
config: m32r-usrv_defconfig (attached as .config)
compiler: m32r-linux-gcc (GCC) 6.2.0
reproduce:
wget 
https://raw.githubusercontent.com/01org/lkp-tests/master/sbin/make.cross -O 
~/bin/make.cross
chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
make.cross ARCH=m32r 

All errors (new ones prefixed by >>):

   kernel/built-in.o: In function `futex_spin_on_reader':
>> kernel/futex.c:4003: undefined reference to `osq_lock'
   kernel/futex.c:4003:(.text+0x5cc98): relocation truncated to fit: 
R_M32R_26_PCREL_RELA against undefined symbol `osq_lock'
>> kernel/futex.c:4040: undefined reference to `osq_unlock'
   kernel/futex.c:4040:(.text+0x5cd2c): relocation truncated to fit: 
R_M32R_26_PCREL_RELA against undefined symbol `osq_unlock'
   kernel/futex.c:4033: undefined reference to `osq_unlock'
   kernel/futex.c:4033:(.text+0x5d0d4): relocation truncated to fit: 
R_M32R_26_PCREL_RELA against undefined symbol `osq_unlock'

vim +4003 kernel/futex.c

  3997  first_reader = READ_ONCE(state->first_reader);
  3998  if (!first_reader)
  3999  first_reader = cmpxchg(>first_reader, NULL, 
current);
  4000  if (!first_reader)
  4001  goto out;   /* Became the first reader */
  4002  
> 4003  if (!osq_lock(>reader_osq))
  4004  goto reschedule;
  4005  
  4006  rcu_read_lock();
  4007  for (;;) {
  4008  u32 uval;
  4009  
  4010  if (!state->handoff_pid && (prefer_reader ||
  4011 (first_reader == READ_ONCE(state->mutex_owner {
  4012  ret = futex_trylock_preempt_disabled(uaddr,
  4013  FUTEX_SHARED, , 
false);
  4014  /*
  4015   * Return if lock acquired or an error happened
  4016   */
  4017  if (ret)
  4018  break;
  4019  }
  4020  
  4021  /*
  4022   * Reread the first reader value again.
  4023   */
  4024  first_reader = READ_ONCE(state->first_reader);
  4025  if (!first_reader)
  4026  first_reader = cmpxchg(>first_reader, 
NULL,
  4027  current);
  4028  if (!first_reader || !first_reader->on_cpu)
  4029  break;
  4030  
  4031  if (need_resched()) {
  4032  rcu_read_unlock();
  4033  osq_unlock(>reader_osq);
  4034  goto reschedule;
  4035  }
  4036  
  4037  cpu_relax();
  4038  }
  4039  rcu_read_unlock();
> 4040  osq_unlock(>reader_osq);
  4041  out:
  4042  *pfirst = first_reader;
  4043  preempt_enable();

---
0-DAY kernel test infrastructureOpen Source Technology Center
https://lists.01.org/pipermail/kbuild-all   Intel Corporation


.config.gz
Description: application/gzip

[PATCH-tip v6 18/22] TP-futex: Group readers together in wait queue

[Waiman Long]

All the TP futex lock waiters are serialized in the kernel using a
kernel mutex which acts like a wait queue. The order at which the
waiters popped out from the wait queue will affect performance when
exclusive (writer) and shared (reader) lock waiters are mixed in the
queue. The worst case scenarios will be something like RWRWRW... in
term of ordering where no parallelism in term of lock ownership
can happen.

To improve throughput, the readers are now grouped together as a single
entity in the wait queue. The first reader that enters the mutex wait
queue will become the leader of the group. The other readers will
spin on the group leader via an OSQ lock. When the futex is put in
the shared mode, either by the group leader or by an external reader
the spinning readers in the reader group will then acquire the read
lock successively.

The spinning readers in the group will get disbanded when the group
leader goes to sleep. In this case, all those readers will go into the
mutex wait queue alone and wait for their turn to acquire the TP futex.

Signed-off-by: Waiman Long 
---
 kernel/futex.c | 143 +++--
 1 file changed, 140 insertions(+), 3 deletions(-)

diff --git a/kernel/futex.c b/kernel/futex.c
index cacaaf1..984b836 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -71,6 +71,7 @@
 #include 
 #include 
 #include 
+#include 
 
 #include 
 
@@ -242,6 +243,16 @@ struct futex_state {
 
u32 handoff_pid;/* 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;
 };
@@ -3403,14 +3414,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_HANDOFF2
+
+#define TP_READER_ALONE1
+#define TP_READER_GROUP2
+
 #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.
@@ -3452,6 +3470,7 @@ void exit_robust_list(struct task_struct *curr)
state = alloc_futex_state();
state->type = TYPE_TP;
state->key = *key;
+   osq_lock_init(>reader_osq);
list_add(>fs_list, >fs_head);
WARN_ON(atomic_read(>refcount) != 1);
 
@@ -3930,6 +3949,105 @@ 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
+ * @prefer_reader: prefer reader if set
+ *
+ * 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  or . 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 prefer-reader mode, the OSQ lock holder will attempt to grab the shared
+ * lock irrespective of the position of the first reader. Otherwise, it will
+ * only grab the lock when the first reader is the serializaton mutex owner.
+ *
+ * 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