sched/fair: Add advisory flag for borrowing a timeslice

sched/fair: Add advisory flag for borrowing a timeslice

This patch adds a way for a task to request to borrow one timeslice
from future if it is about to be preempted, so it could delay
preemption and complete any critical task it is in the middle of.

This feature improves performance for apps that use userspace locking
across large number of threads, for example large databases and Java,
and similar solutions have been used for many years on other OSs.
This feature helps in situation where a task acquires a lock before
performing a critical operation on shared data and happens to have
acquired the lock just before its timeslice is up which means it gets
preempted before it completes its task. This lock being held causes
all other tasks that also acquire the same lock to perform their
critical operation on shared data, to start queueing up and causing
large number of context switches. This queueing problem can be avoided
if the task that acquires lock first could request scheduler to let it
borrow one timeslice once it enters its critical section and hence
allow it to complete its critical section without causing queueing
problem. If critical section completes before the task is due for
preemption, the task can desassert its request which causes scheduler
to proceed with normal preemption. A task sends the scheduler this
request by setting a flag in a memory location it has shared with the
kernel. Kernel uses bytes in the same memory location to let the task
know when its request for amnesty from preemption has been granted.

These rules apply to the use of this feature:

- Request to borrow timeslice is not guranteed to be honored.
- If the task is allowed to borrow, kernel will inform the task
  of this. When this happens, task must yield the processor as soon
  as it completes its critical section.
- If the task fails to yield processor after being allowed to
  borrow, it is penalized by not honoring its next request for
  extra timeslice.
- Task is charged additional time for the borrowed timeslice as
  accumulated run time. This pushes it further down in consideration
  for the next task to run.

This feature was tested with a TPC-C workload. TPC-C workload shows

70 more lines

diff --git a/Documentation/scheduler/sched-preempt-delay.txt b/Documentation/scheduler/sched-preempt-delay.txt
new file mode 100644
index 0000000..4c9e111
--- /dev/null
+++ b/Documentation/scheduler/sched-preempt-delay.txt

@@ -0,0 +1,112 @@
+=================================
+What is preemption delay feature?
+=================================
+
+There are times when a userspace task is executing a critical section
+which gates a number of other tasks that want access to the same
+critical section. If the task holding the lock that guards this critical
+section happens to grab the lock just before its timeslice is up and is
+preempted by the scheduler, scheduler ends up scheduling other
+tasks which immediately try to grab the lock to enter the critical
+section. This only results in lots of context switches as tasks wake up
+and go to sleep immediately. If on the other hand, the original task
+were allowed to run for an extra timeslice, it could have completed
+executing its critical section allowing other tasks to make progress
+when they get scheduled. Preemption delay feature allows a task to
+request scheduler to let it borrow one extra timeslice, if possible.
+
+
+==================================
+Using the preemption delay feature
+==================================
+
+This feature is compiled in the kernel by setting
+CONFIG_SCHED_PREEMPT_DELAY in kernel configuration. By default, the
+kernel boots up with this feature disabled. Enable it using sysctl
+tunable kernel.preempt_delay_available. Once this feature is
+enabled, the userspace process communicates with the kernel using a
+4-byte memory location in its address space. This location must be
+aligned to 4-byte boundary. It first gives the kernel address for this
+memory location by making a prctl() system call with PR_SET_PREEMPT_DELAY
+option. This memory location is interpreted as the following data
+structure (defined in linux/sched.h):
+
+struct sched_delay_req {
+	unsigned char nopreempt;	/* flag to request preemption delay */
+	unsigned char yield;		/* flag from kernel indicating  */
+					/* preemption delay was granted */
+	unsigned char rsvd[2];		/* reserved */
+};
+
+Task requests a preemption delay by writing a non-zero value to the
+first byte - nopreempt. Scheduler checks this value before preempting
+the task. Scheduler can choose to grant one and only an additional
+time slice to the task for each delay request but this delay is not
+guaranteed. If scheduler does grant an additional timeslice, it will
+set the flag in second byte. Upon completion of the section of code
+where the task wants preemption delay, task should check the second byte.
+If the flag in second byte is set, it should clear this flag and call
+sched_yield() so as to not hog the processor. If a thread was granted
+additional timeslice and it fails to call sched_yield(), scheduler
+will penalize it by denying its next request for additional timeslice.
+Following sample code illustrates how to use this feature:
+
+#include <linux/sched.h>
+
+int main()
+{
+	unsigned char buf[256];
+	struct sched_delay_req delay;
+
+	bzero(&delay, sizeof(delay));
+
+	/* Tell kernel where the flag lives */
+	prctl(PR_SET_PREEMPT_DELAY, &delay);
+
+	while (/* some condition is true */) {
+		/* do some work and get ready to enter critical section */
+		delay.nopreempt = 1;
+		/*
+		 * Obtain lock for critical section
+		 */
+		/*
+		 * critical section
+		 */
+		/*
+		 * Release lock for critical section
+		 */
+		delay.nopreempt = 0;
+		/* Give the CPU up if required */
+		if (delay.yield) {
+			delay.yield = 0;
+			sched_yield();
+		}
+		/* do some more work */
+	}
+	/*
+	 * Tell kernel we are done asking for preemption delay
+	 */
+	prctl(PR_SET_PREEMPT_DELAY, NULL);
+}
+
+
+====================
+Scheduler statistics
+====================
+
+Preemption delay features adds a new field to scheduler statictics -
+nr_preempt_delayed. This is a per thread statistic that tracks the
+number of times a thread was granted amnesty from preemption when it
+requested for one. "cat /proc/<pid>/task/<tid>/sched" will list this
+number along with other scheduler statistics.
+
+
+=====
+Notes
+=====
+
+1. If the location of shared flag is not aligned to 4-byte boundary,
+   prctl() will terminate with EFAULT.
+2. Userspace app should zero out the sched_delay_req structure before
+   giving kernel the address of this structure. Stale data in this
+   structure could cause unintended requests for preemption delay.

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 41a503c..6c24167 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig

@@ -852,6 +852,17 @@ config SCHED_MC
 	  making when dealing with multi-core CPU chips at a cost of slightly
 	  increased overhead in some places. If unsure say N here.
 
+config SCHED_PREEMPT_DELAY
+	def_bool n
+	prompt "Scheduler preemption delay support"
+	---help---
+	  Say Y here if you want to be able to delay scheduler preemption
+	  when possible by setting a flag in a memory location after
+	  sharing the address of this location with kernel using
+	  PR_SET_PREEMPT_DELAY prctl() call. See
+	  Documentation/scheduler/sched-preempt-delay.txt for details.
+	  If in doubt, say "N".
+
 source "kernel/Kconfig.preempt"
 
 config X86_UP_APIC

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 5e344bb..0b2f911 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h

@@ -1116,6 +1116,7 @@ struct sched_statistics {
 	u64			nr_wakeups_affine_attempts;
 	u64			nr_wakeups_passive;
 	u64			nr_wakeups_idle;
+	u64			nr_preempt_delayed;
 };
 #endif
 

@@ -1232,6 +1233,14 @@ enum perf_event_task_context {
 	perf_nr_task_contexts,
 };
 
+#ifdef CONFIG_SCHED_PREEMPT_DELAY
+struct preempt_delay {
+	struct sched_delay_req *delay_req;	/* delay request flag pointer */
+	unsigned char delay_granted;		/* currently in delay */
+	unsigned char yield_penalty;		/* failure to yield penalty */
+};
+#endif
+
 struct task_struct {
 	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
 	void *stack;

@@ -1324,6 +1333,9 @@ struct task_struct {
 	/* Revert to default priority/policy when forking */
 	unsigned sched_reset_on_fork:1;
 	unsigned sched_contributes_to_load:1;
+#ifdef CONFIG_SCHED_PREEMPT_DELAY
+	struct preempt_delay sched_preempt_delay;
+#endif
 
 	unsigned long atomic_flags; /* Flags needing atomic access. */
 

@@ -3031,4 +3043,30 @@ static inline unsigned long rlimit_max(unsigned int limit)
 	return task_rlimit_max(current, limit);
 }
 
+#ifdef CONFIG_SCHED_PREEMPT_DELAY
+static inline void task_init_preempt_delay(struct task_struct *p)
+{
+	memset(&p->sched_preempt_delay, 0, sizeof(struct preempt_delay));
+}
+static inline void task_clear_preempt_yield(struct task_struct *p)
+{
+	p->sched_preempt_delay.yield_penalty = 0;
+}
+extern int preempt_delay_write(struct task_struct *task,
+					unsigned long preempt_delay_addr);
+#define SCHED_SET_PREEMPT_DELAY(a)	preempt_delay_write(current, a)
+#define SCHED_GET_PREEMPT_DELAY(a)	\
+		put_user((unsigned long)current->sched_preempt_delay.delay_req,\
+				(unsigned long __user *)a)
+#else
+static inline void task_init_preempt_delay(struct task_struct *p)
+{
+}
+static inline void task_clear_preempt_yield(struct task_struct *p)
+{
+}
+#define SCHED_SET_PREEMPT_DELAY(a)	(-EINVAL)
+#define SCHED_GET_PREEMPT_DELAY(a)	(-EINVAL)
+#endif /* CONFIG_SCHED_PREEMPT_DELAY */
+
 #endif

diff --git a/include/linux/sched/sysctl.h b/include/linux/sched/sysctl.h
index 596a0e0..516f74e 100644
--- a/include/linux/sched/sysctl.h
+++ b/include/linux/sched/sysctl.h

@@ -107,4 +107,8 @@ extern int sysctl_numa_balancing(struct ctl_table *table, int write,
 				 void __user *buffer, size_t *lenp,
 				 loff_t *ppos);
 
+#ifdef CONFIG_SCHED_PREEMPT_DELAY
+extern int sysctl_preempt_delay_available;
+#endif
+
 #endif /* _SCHED_SYSCTL_H */

diff --git a/include/uapi/linux/prctl.h b/include/uapi/linux/prctl.h
index 513df75..ecfd2cd 100644
--- a/include/uapi/linux/prctl.h
+++ b/include/uapi/linux/prctl.h

@@ -179,4 +179,7 @@ struct prctl_mm_map {
 #define PR_SET_THP_DISABLE	41
 #define PR_GET_THP_DISABLE	42
 
+#define PR_SET_PREEMPT_DELAY	43
+#define PR_GET_PREEMPT_DELAY	44
+
 #endif /* _LINUX_PRCTL_H */

diff --git a/include/uapi/linux/sched.h b/include/uapi/linux/sched.h
index b932be9..66a2f67 100644
--- a/include/uapi/linux/sched.h
+++ b/include/uapi/linux/sched.h

@@ -49,4 +49,13 @@
  */
 #define SCHED_FLAG_RESET_ON_FORK	0x01
 
+/*
+ * struct for requesting preemption delay from scheduler
+ */
+struct sched_delay_req {
+	unsigned char nopreempt;
+	unsigned char yield;
+	unsigned char rsvd[2];
+};
+
 #endif /* _UAPI_LINUX_SCHED_H */

diff --git a/kernel/fork.c b/kernel/fork.c
index 9b7d746..aea655b 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c

@@ -1672,6 +1672,8 @@ long do_fork(unsigned long clone_flags,
 			get_task_struct(p);
 		}
 
+		task_init_preempt_delay(p);
+
 		wake_up_new_task(p);
 
 		/* forking complete and child started to run, tell ptracer */

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 24beb9b..a926eea 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c

@@ -4201,6 +4201,7 @@ SYSCALL_DEFINE0(sched_yield)
 {
 	struct rq *rq = this_rq_lock();
 
+	task_clear_preempt_yield(current);
 	schedstat_inc(rq, yld_count);
 	current->sched_class->yield_task(rq);
 

diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index ce33780..618d2ac 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c

@@ -597,6 +597,7 @@ void proc_sched_show_task(struct task_struct *p, struct seq_file *m)
 	P(se.statistics.nr_wakeups_affine_attempts);
 	P(se.statistics.nr_wakeups_passive);
 	P(se.statistics.nr_wakeups_idle);
+	P(se.statistics.nr_preempt_delayed);
 
 	{
 		u64 avg_atom, avg_per_cpu;

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index ef2b104..a880c6f 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c

@@ -428,6 +428,129 @@ find_matching_se(struct sched_entity **se, struct sched_entity **pse)
 
 #endif	/* CONFIG_FAIR_GROUP_SCHED */
 
+#ifdef CONFIG_SCHED_PREEMPT_DELAY
+int sysctl_preempt_delay_available;
+
+int
+preempt_delay_write(struct task_struct *task, unsigned long preempt_delay_addr)
+{
+	/*
+	 * Do not allow write if preemption delay feature is disabled
+	 */
+	if (!sysctl_preempt_delay_available)
+		return -EPERM;
+
+	if ((void *)preempt_delay_addr == NULL) {
+		task->sched_preempt_delay.delay_req = NULL;
+		return 0;
+	}
+
+	/*
+	 * Validate the pointer. It should be naturally aligned
+	 */
+	if (unlikely((preempt_delay_addr % sizeof(u32)) != 0))
+		return -EFAULT;
+	if (unlikely(!access_ok(rw, preempt_delay_addr,
+					sizeof(struct sched_delay_req))))
+		return -EFAULT;
+
+	task->sched_preempt_delay.delay_req =
+				(struct sched_delay_req *) preempt_delay_addr;
+	return 0;
+}
+
+/*
+ * delay_resched_rq(): Check if the task about to be preempted has
+ *	requested an additional time slice. If it has, grant it additional
+ *	timeslice once.
+ */
+static void
+delay_resched_rq(struct rq *rq)
+{
+	struct task_struct *curr = rq->curr;
+	struct sched_entity *se;
+	struct sched_delay_req *delay_req, delay_flag;
+	int ret;
+
+	if (!sysctl_preempt_delay_available)
+		goto resched_now;
+
+	/*
+	 * Check if task is using pre-emption delay feature. If address
+	 * for preemption delay request flag is not set, this task is
+	 * not using preemption delay feature, we can reschedule without
+	 * any delay
+	 */
+	delay_req = curr->sched_preempt_delay.delay_req;
+	if (delay_req == NULL)
+		goto resched_now;
+
+	/*
+	 * Pre-emption delay will  be granted only once. If this task
+	 * has already been granted delay, rechedule now
+	 */
+	if (curr->sched_preempt_delay.delay_granted) {
+		curr->sched_preempt_delay.delay_granted = 0;
+		goto resched_now;
+	}
+
+	/*
+	 * Get the value of preemption delay request flag from userspace.
+	 * Task had already passed us the address where the flag is stored
+	 * in userspace earlier. If there is a page fault accessing this
+	 * flag in userspace, that means userspace has not touched this
+	 * flag recently and we can assume no preemption delay is needed.
+	 *
+	 * If task is not requesting additional timeslice, resched now
+	 */
+	pagefault_disable();
+	ret = __copy_from_user_inatomic(&delay_flag, delay_req,
+			sizeof(u32));
+	pagefault_enable();
+	if (ret || !delay_flag.nopreempt)
+		goto resched_now;
+
+	/*
+	 * Current thread has requested preemption delay and has not
+	 * been granted an extension yet. If this thread failed to yield
+	 * processor after being granted amnesty last time, penalize it
+	 * by not granting this delay request, otherwise give it an extra
+	 * timeslice.
+	 */
+	if (curr->sched_preempt_delay.yield_penalty) {
+		curr->sched_preempt_delay.yield_penalty = 0;
+		goto resched_now;
+	}
+
+	se = &curr->se;
+	curr->sched_preempt_delay.delay_granted = 1;
+
+	/*
+	 * Set the penalty flag for failing to yield the processor after
+	 * being granted immunity. This flag will be cleared in
+	 * sched_yield() if the thread indeed calls sched_yield
+	 */
+	curr->sched_preempt_delay.yield_penalty = 1;
+
+	/*
+	 * Let the thread know it got amnesty and it should call
+	 * sched_yield() when it is done to avoid penalty next time
+	 * it wants amnesty.
+	 */
+	delay_flag.nopreempt = 0;
+	delay_flag.yield = 1;
+	schedstat_inc(curr, se.statistics.nr_preempt_delayed);
+	__copy_to_user_inatomic(delay_req, &delay_flag, sizeof(u32));
+
+	return;
+
+resched_now:
+	resched_curr(rq);
+}
+#else
+#define delay_resched_rq(rq) resched_curr(rq)
+#endif /* CONFIG_SCHED_PREEMPT_DELAY */
+
 static __always_inline
 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec);
 

@@ -2951,7 +3074,7 @@ check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
 	ideal_runtime = sched_slice(cfs_rq, curr);
 	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
 	if (delta_exec > ideal_runtime) {
-		resched_curr(rq_of(cfs_rq));
+		delay_resched_rq(rq_of(cfs_rq));
 		/*
 		 * The current task ran long enough, ensure it doesn't get
 		 * re-elected due to buddy favours.

@@ -2975,7 +3098,7 @@ check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
 		return;
 
 	if (delta > ideal_runtime)
-		resched_curr(rq_of(cfs_rq));
+		delay_resched_rq(rq_of(cfs_rq));
 }
 
 static void

@@ -4792,7 +4915,7 @@ static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_
 	return;
 
 preempt:
-	resched_curr(rq);
+	delay_resched_rq(rq);
 	/*
 	 * Only set the backward buddy when the current task is still
 	 * on the rq. This can happen when a wakeup gets interleaved

diff --git a/kernel/sys.c b/kernel/sys.c
index 1eaa2f0..a8b1eff 100644
--- a/kernel/sys.c
+++ b/kernel/sys.c

@@ -2203,6 +2203,12 @@ SYSCALL_DEFINE5(prctl, int, option, unsigned long, arg2, unsigned long, arg3,
 			me->mm->def_flags &= ~VM_NOHUGEPAGE;
 		up_write(&me->mm->mmap_sem);
 		break;
+	case PR_SET_PREEMPT_DELAY:
+		error = SCHED_SET_PREEMPT_DELAY(arg2);
+		break;
+	case PR_GET_PREEMPT_DELAY:
+		error = SCHED_GET_PREEMPT_DELAY(arg2);
+		break;
 	default:
 		error = -EINVAL;
 		break;

diff --git a/kernel/sysctl.c b/kernel/sysctl.c
index 15f2511..c1cd344 100644
--- a/kernel/sysctl.c
+++ b/kernel/sysctl.c

@@ -1104,6 +1104,15 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= proc_dointvec,
 	},
 #endif
+#ifdef CONFIG_SCHED_PREEMPT_DELAY
+	{
+		.procname	= "preempt_delay_available",
+		.data		= &sysctl_preempt_delay_available,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+#endif
 	{ }
 };
 

-- 
1.9.1

On Thu, Dec 18, 2014 at 11:44:19AM -0700, Khalid Aziz wrote:

sched/fair: Add advisory flag for borrowing a timeslice

yuck hatred and much of that.

Also, you fail to explain why a kernel side spin futex-lock is not an
option.

On 12/18/2014 03:28 PM, Peter Zijlstra wrote:

On Thu, Dec 18, 2014 at 11:44:19AM -0700, Khalid Aziz wrote:

quoted

sched/fair: Add advisory flag for borrowing a timeslice

yuck hatred and much of that.

Also, you fail to explain why a kernel side spin futex-lock is not an
option.

I had explained that when this question came up in the last round of discussions. The queuing problem I am trying to solve stems from userspace locks. Java and databases implement their own userspace locks that do not use futex. Solving this with futex will not help the primary users of this solution.

Hope this helps.

Thanks,
Khalid

On Thu, 18 Dec 2014, Khalid Aziz wrote:

On 12/18/2014 03:28 PM, Peter Zijlstra wrote:

quoted

On Thu, Dec 18, 2014 at 11:44:19AM -0700, Khalid Aziz wrote:

quoted

sched/fair: Add advisory flag for borrowing a timeslice

yuck hatred and much of that.

Also, you fail to explain why a kernel side spin futex-lock is not an
option.

I had explained that when this question came up in the last round of
discussions. The queuing problem I am trying to solve stems from userspace
locks. Java and databases implement their own userspace locks that do not use
futex. Solving this with futex will not help the primary users of this
solution.

If we can solve it with a proper designed and well thought out
functionality in the kernel based on a futex like mechanism, why cant
java and databases not switch over to that and simply use it?

You need to modify user space anyway, so it does not matter whether
you modify it in a sane or in a hacky way.

But its simpler to hack crap into the scheduler than coming up with a
proper solution to the problem, right?

Hope this helps.

Not at all.

Thanks,

	tglx

On 12/18/2014 04:02 PM, Thomas Gleixner wrote:

On Thu, 18 Dec 2014, Khalid Aziz wrote:

quoted

On 12/18/2014 03:28 PM, Peter Zijlstra wrote:

quoted

On Thu, Dec 18, 2014 at 11:44:19AM -0700, Khalid Aziz wrote:

quoted

sched/fair: Add advisory flag for borrowing a timeslice

yuck hatred and much of that.

Also, you fail to explain why a kernel side spin futex-lock is not an
option.

I had explained that when this question came up in the last round of
discussions. The queuing problem I am trying to solve stems from userspace
locks. Java and databases implement their own userspace locks that do not use
futex. Solving this with futex will not help the primary users of this
solution.

If we can solve it with a proper designed and well thought out
functionality in the kernel based on a futex like mechanism, why cant
java and databases not switch over to that and simply use it?

You need to modify user space anyway, so it does not matter whether
you modify it in a sane or in a hacky way.

Actually userspace does not need to be modified. The code to use this functionality is already present in database code since this same functionality exists on other OSs (the API is a little different but those details can be handled with a simple header file in userspace). Userspace code has already been tested and debugged thoroughly on the OSs that support this functionality and that has significant impact on testing effort. So for userspace it is simply a matter of turning that code on on Linux as well and recompiling. This would be a multi-platform solution for database/java as opposed to a Linux specific solution.

--
Khalid

On Thu, 18 Dec 2014, Khalid Aziz wrote:

On 12/18/2014 04:02 PM, Thomas Gleixner wrote:

quoted

If we can solve it with a proper designed and well thought out
functionality in the kernel based on a futex like mechanism, why cant
java and databases not switch over to that and simply use it?

You need to modify user space anyway, so it does not matter whether
you modify it in a sane or in a hacky way.

Actually userspace does not need to be modified. The code to use this
functionality is already present in database code since this same
functionality exists on other OSs (the API is a little different but those
details can be handled with a simple header file in userspace). Userspace code
has already been tested and debugged thoroughly on the OSs that support this
functionality and that has significant impact on testing effort. So for
userspace it is simply a matter of turning that code on on Linux as well and
recompiling. This would be a multi-platform solution for database/java as
opposed to a Linux specific solution.

Bullshit. If you turn that option on, it's a modification from the QA
point of view and you need to run a full validation no matter
what. Anything else is just QA by crystal ball.

Of course you carefully avoided (again) to answer the real question:

But its simpler to hack crap into the scheduler than coming up with a
proper solution to the problem, right?

I can answer it for you: Yes, it is simpler.

But as you might have figured out it's not really popular and therefor
not simpler to be accepted by the people who actually care about sane
designs. I can whip you up special purpose hacks for that which will
give you way more guarantees with way less lines of horrible code, but
that does not mean that such hacks are an acceptable solution. You can
carry those hacks in your private tree and ship it to your customers,
but do not expect that any sane maintainer will care about it.

Now the very same maintainers asked you several times to answer the
question why this can't be done with proper futex like spin
mechanisms, which would solve a bunch of related problems as well.

 You never even tried to answer that question simply because you never
 tried to think about it for real. Your only answer is that you want A
 because A is already used on other OSs and therefor solution B is not
 an option.

 But if solution B would gain 4% performance, then according to your
 previous argumentation it would become suddenly very interesting,
 right?

So unless you even show any sign of thinking about different
approaches and technically arguing why they cannot deliver the same
value you wont get anywhere with this and I can tell you why.

You create a new user space ABI

 That forces the kernel to support it forever, which in consequence
 imposes restrictions on the kernel scheduler forever.

 We have enough restrictions by misdesigned ABIs (e.g. sched_yield())
 already, so we really do not need more of that.

You ignore any request to prove why a proper designed spin futex
interface would not be a sensible solution for the problem.

 Of course you are free to ignore that (as you are free to ignore

22 more lines

On 12/18/2014 05:27 PM, Thomas Gleixner wrote:

On Thu, 18 Dec 2014, Khalid Aziz wrote:

quoted

On 12/18/2014 04:02 PM, Thomas Gleixner wrote:

quoted

If we can solve it with a proper designed and well thought out
functionality in the kernel based on a futex like mechanism, why cant
java and databases not switch over to that and simply use it?

You need to modify user space anyway, so it does not matter whether
you modify it in a sane or in a hacky way.

Actually userspace does not need to be modified. The code to use this
functionality is already present in database code since this same
functionality exists on other OSs (the API is a little different but those
details can be handled with a simple header file in userspace). Userspace code
has already been tested and debugged thoroughly on the OSs that support this
functionality and that has significant impact on testing effort. So for
userspace it is simply a matter of turning that code on on Linux as well and
recompiling. This would be a multi-platform solution for database/java as
opposed to a Linux specific solution.

Bullshit. If you turn that option on, it's a modification from the QA
point of view and you need to run a full validation no matter
what. Anything else is just QA by crystal ball.

Of course you carefully avoided (again) to answer the real question:

quoted

But its simpler to hack crap into the scheduler than coming up with a
proper solution to the problem, right?

I can answer it for you: Yes, it is simpler.

But as you might have figured out it's not really popular and therefor
not simpler to be accepted by the people who actually care about sane
designs. I can whip you up special purpose hacks for that which will
give you way more guarantees with way less lines of horrible code, but
that does not mean that such hacks are an acceptable solution. You can
carry those hacks in your private tree and ship it to your customers,
but do not expect that any sane maintainer will care about it.

Now the very same maintainers asked you several times to answer the
question why this can't be done with proper futex like spin

50 more quoted lines

Fair enough. Implications of a new userspace ABI can be significant and I can accept not introducing a new one in the kernel.

The queuing problem caused by a task taking a contended lock just before its current timeslice is up which userspace app wouldn't know about, is a real problem nevertheless. My patch attempts to avoid the contention in the first place. futex with adaptive spinning is a post-contention solution that tries to minimize the cost of contention but does nothing to avoid the contention. Solving this problem using futex can help only if the userspace lock uses futex.

I have looked at solving this problem in userspace using priority inheritance semaphore but ran into many problems. I will go back and take another look at it.

I appreciate your feedback.

Thanks,
Khalid

On Fri, 19 Dec 2014, Khalid Aziz wrote:

The queuing problem caused by a task taking a contended lock just before its
current timeslice is up which userspace app wouldn't know about, is a real
problem nevertheless.

We know that already.

My patch attempts to avoid the contention in the first
place. futex with adaptive spinning is a post-contention solution that tries
to minimize the cost of contention but does nothing to avoid the contention.

I never said that adaptive spinning can solve that problem. 

If you would have carefuly read what I wrote, you might have noticed,
that I said: 

     a proper futex like spin mechanism

Can you spot the subtle difference between that phrase and 'futex with
adaptive spinning'?

Solving this problem using futex can help only if the userspace lock uses
futex.

A really fundamentally new and earth shattering insight.

If you would spend your time to actually digest what maintainers are
telling you, we might make progress on that matter.

But you prefer to spend your time by repeating yourself and providing
completely useless information.

What you are missing completely here is that neither me nor other
maintainers involved care about how you spend your time. But we very
much care about the time WE waste with your behaviour.

Thanks,

	tglx

On 12/19/2014 04:57 PM, Thomas Gleixner wrote:

On Fri, 19 Dec 2014, Khalid Aziz wrote:

quoted

The queuing problem caused by a task taking a contended lock just before its
current timeslice is up which userspace app wouldn't know about, is a real
problem nevertheless.

We know that already.

quoted

My patch attempts to avoid the contention in the first
place. futex with adaptive spinning is a post-contention solution that tries
to minimize the cost of contention but does nothing to avoid the contention.

I never said that adaptive spinning can solve that problem.

If you would have carefuly read what I wrote, you might have noticed,
that I said:

      a proper futex like spin mechanism

Can you spot the subtle difference between that phrase and 'futex with
adaptive spinning'?

quoted

Solving this problem using futex can help only if the userspace lock uses
futex.

A really fundamentally new and earth shattering insight.

If you would spend your time to actually digest what maintainers are
telling you, we might make progress on that matter.

But you prefer to spend your time by repeating yourself and providing
completely useless information.

What you are missing completely here is that neither me nor other
maintainers involved care about how you spend your time. But we very
much care about the time WE waste with your behaviour.

I am sorry that you feel the need to continue to resort to personal attacks even after I made it clear in my last response that I was not going to pursue this patch. There is no possibility of a productive discussion of a solution at this point. I hope someone else can find a solution you find acceptable.

Thanks,
Khalid

* Khalid Aziz [off-list ref] wrote:

On 12/19/2014 04:57 PM, Thomas Gleixner wrote:

quoted

On Fri, 19 Dec 2014, Khalid Aziz wrote:

quoted

The queuing problem caused by a task taking a contended lock just before its
current timeslice is up which userspace app wouldn't know about, is a real
problem nevertheless.

We know that already.

quoted

My patch attempts to avoid the contention in the first
place. futex with adaptive spinning is a post-contention solution that tries
to minimize the cost of contention but does nothing to avoid the contention.

I never said that adaptive spinning can solve that problem.

If you would have carefuly read what I wrote, you might have noticed,
that I said:

     a proper futex like spin mechanism

Can you spot the subtle difference between that phrase and 'futex with
adaptive spinning'?

quoted

Solving this problem using futex can help only if the userspace lock uses
futex.

A really fundamentally new and earth shattering insight.

If you would spend your time to actually digest what maintainers are
telling you, we might make progress on that matter.

But you prefer to spend your time by repeating yourself and providing
completely useless information.

What you are missing completely here is that neither me nor other
maintainers involved care about how you spend your time. But we very
much care about the time WE waste with your behaviour.

I am sorry that you feel the need to continue to resort to 
personal attacks [...]

Thomas did not attack your person AFAICS - he criticised your 
arguments with increasing volume, because he did not see you 
respond to his arguments in substance.

even after I made it clear in my last response that I was not 
going to pursue this patch. There is no possibility of a 
productive discussion of a solution at this point. [...]

I think there is very much a possibility of a productive 
discussion:

[...] I hope someone else can find a solution you find 
acceptable.

to implement what Thomas suggested in the discussion: a proper 
futex like spin mechanism? That looks like a totally acceptable 
solution to me, without the disadvantages of your proposed 
solution.

Thanks,

	Ingo

On 12/23/2014 03:52 AM, Ingo Molnar wrote:

to implement what Thomas suggested in the discussion: a proper
futex like spin mechanism? That looks like a totally acceptable
solution to me, without the disadvantages of your proposed
solution.

Hi Ingo,

Thank you for taking the time to respond. It is indeed possible to implement a futex like spin mechanism. Futex like mechanism will be clean and elegant. That is where I had started when I was given this problem to solve. Trouble I run into is the primary application I am looking at to help with this solution is Database which implements its own locking mechanism without using POSIX semaphore or futex. Since the locking is entirely in userspace, kernel has no clue when the userspace has acquired one of these locks. So I can see only two ways to solve this - find a solution in userspace entirely, or have userspace tell the kernel when it acquires one of these locks. I will spend more time on finding a way to solve it in userspace and see if I can find a way to leverage futex mechanism without causing significant change to database code. There may be a way to use priority inheritance to avoid contention. Database performance people tell me that their testing has shown the cost of making any system calls in this code easily offsets any gains from optimizing for contention avoidance, so that is one big challenge. Database rewriting their locking code is extremely unlikely scenario. Am I missing a third option here?

Thanks,
Khalid

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/23/2014 10:13 AM, Khalid Aziz wrote:

On 12/23/2014 03:52 AM, Ingo Molnar wrote:

quoted

to implement what Thomas suggested in the discussion: a proper 
futex like spin mechanism? That looks like a totally acceptable 
solution to me, without the disadvantages of your proposed 
solution.

Hi Ingo,

Thank you for taking the time to respond. It is indeed possible to 
implement a futex like spin mechanism. Futex like mechanism will
be clean and elegant. That is where I had started when I was given
this problem to solve. Trouble I run into is the primary
application I am looking at to help with this solution is Database
which implements its own locking mechanism without using POSIX
semaphore or futex. Since the locking is entirely in userspace,
kernel has no clue when the userspace has acquired one of these
locks. So I can see only two ways to solve this - find a solution
in userspace entirely, or have userspace tell the kernel when it
acquires one of these locks. I will spend more time on finding a
way to solve it in userspace and see if I can find a way to 
leverage futex mechanism without causing significant change to
database code. There may be a way to use priority inheritance to
avoid contention. Database performance people tell me that their
testing has shown the cost of making any system calls in this code
easily offsets any gains from optimizing for contention avoidance,
so that is one big challenge. Database rewriting their locking code
is extremely unlikely scenario. Am I missing a third option here?

An uncontended futex is taken without ever going into kernel
space. Adaptive spinning allows short duration futexes to be
taken without going into kernel space.

Only long held locks cause a thread to go into kernel space,
where it goes to sleep, freeing up the cpu, and increasing
the chance that the lock holder will run.

- -- 
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJUmbihAAoJEM553pKExN6DDlQH/1vvy9YYuP2dCAZSU3fz855e
pj4796Qja929I2dStsbLl6Qhcg2ELtwtPkLoAePQ/4j2l7DCYgSNLXlC+RzQ32ay
rbMIfwiriEVGp2hsvYTOCpnur19IHf7v726ivaDXVOM/nrRaHsB8wwspLQQyfSIE
b7M7jxvT4S2pEELOGB6JQfEZZhbf5wBv9HBk+fkCBMaO4WZrnYczyD0/omiADm65
xSm/8pCMK22u8Tzn9EpKpIVdIFrl9AlZ1uiRBV2Br1oqwaBTvJVknW4bvIk0DWZU
ErwR/073UYKpl+xce3nbnixH8FeRP7/mq73Xd8e+iCgn6Dtzr1tANsu27EigMZ0=
=WHb3
-----END PGP SIGNATURE-----

On 12/23/2014 11:46 AM, Rik van Riel wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/23/2014 10:13 AM, Khalid Aziz wrote:

quoted

On 12/23/2014 03:52 AM, Ingo Molnar wrote:

quoted

to implement what Thomas suggested in the discussion: a proper
futex like spin mechanism? That looks like a totally acceptable
solution to me, without the disadvantages of your proposed
solution.

Hi Ingo,

Thank you for taking the time to respond. It is indeed possible to
implement a futex like spin mechanism. Futex like mechanism will
be clean and elegant. That is where I had started when I was given
this problem to solve. Trouble I run into is the primary
application I am looking at to help with this solution is Database
which implements its own locking mechanism without using POSIX
semaphore or futex. Since the locking is entirely in userspace,
kernel has no clue when the userspace has acquired one of these
locks. So I can see only two ways to solve this - find a solution
in userspace entirely, or have userspace tell the kernel when it
acquires one of these locks. I will spend more time on finding a
way to solve it in userspace and see if I can find a way to
leverage futex mechanism without causing significant change to
database code. There may be a way to use priority inheritance to
avoid contention. Database performance people tell me that their
testing has shown the cost of making any system calls in this code
easily offsets any gains from optimizing for contention avoidance,
so that is one big challenge. Database rewriting their locking code
is extremely unlikely scenario. Am I missing a third option here?

An uncontended futex is taken without ever going into kernel
space. Adaptive spinning allows short duration futexes to be
taken without going into kernel space.

You are right. Uncontended futex is very fast since it never goes into kernel. Queuing problem happens when the lock holder has been pre-empted. Adaptive spinning does the smart thing os spin-waiting only if the lock holder is still running on another core. If lock holder is not scheduled on any core, even adaptive spinning has to go into the kernel to be put on wait queue. What would avoid queuing problem and reduce the cost of contention is a combination of adaptive spinning, and a way to keep the lock holder running on one of the cores just a little longer so it can release the lock. Without creating special case and a new API in kernel, one way I can think of accomplishing the second part is to boost the priority of lock holder when contention happens and priority ceiling is meant to do exactly that. Priority ceiling implementation in glibc boosts the priority by calling into scheduler which does incur the cost of a system call. Priority boost is a reliable solution that does not change scheduling semantics. The solution allowing lock holder to use one extra timeslice is not a definitive solution but tpcc workload shows it does work and it works without requiring changes to database locking code.

Theoretically a new locking library that uses both these techniques will help solve the problem but being a new locking library, there is a big unknown of what new problems, performance and otherwise, it will bring and database has to recode to this new library. Nevertheless this is the path I am exploring now. The challenge being how to do this without requiring changes to database code or the kernel. The hooks available to me into current database code are schedctl_init(), schedctl_start() and schedctl_stop() which are no-op on Linux at this time. Database folks can replace these no-ops with real code in their library to solve the queuing problem. schedctl_start() and schedctl_stop() are called only when one of the highly contended locks is acquired or released. schedctl_start() is called after the lock has been acquired which means I can not rely upon it to solve contention issue. schedctl_stop() is called after the lock has been released.

Thanks,
Khalid

Only long held locks cause a thread to go into kernel space,
where it goes to sleep, freeing up the cpu, and increasing
the chance that the lock holder will run.

- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJUmbihAAoJEM553pKExN6DDlQH/1vvy9YYuP2dCAZSU3fz855e
pj4796Qja929I2dStsbLl6Qhcg2ELtwtPkLoAePQ/4j2l7DCYgSNLXlC+RzQ32ay
rbMIfwiriEVGp2hsvYTOCpnur19IHf7v726ivaDXVOM/nrRaHsB8wwspLQQyfSIE
b7M7jxvT4S2pEELOGB6JQfEZZhbf5wBv9HBk+fkCBMaO4WZrnYczyD0/omiADm65
xSm/8pCMK22u8Tzn9EpKpIVdIFrl9AlZ1uiRBV2Br1oqwaBTvJVknW4bvIk0DWZU
ErwR/073UYKpl+xce3nbnixH8FeRP7/mq73Xd8e+iCgn6Dtzr1tANsu27EigMZ0=
=WHb3
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/23/2014 03:47 PM, Khalid Aziz wrote:

quoted

You are right. Uncontended futex is very fast since it never goes
into kernel. Queuing problem happens when the lock holder has
been pre-empted. Adaptive spinning does the smart thing os
spin-waiting only if the lock holder is still running on another
core. If lock holder is not scheduled on any core, even adaptive
spinning has to go into the kernel to be put on wait queue. What
would avoid queuing problem and reduce the cost of contention is
a combination of adaptive spinning, and a way to keep the lock
holder running on one of the cores just a little longer so it can
release the lock. Without creating special case and a new API in
kernel, one way I can think of accomplishing the second part is
to boost the priority of lock holder when contention happens and 
priority ceiling is meant to do exactly that. Priority ceiling 
implementation in glibc boosts the priority by calling into
scheduler which does incur the cost of a system call. Priority
boost is a reliable solution that does not change scheduling
semantics. The solution allowing lock holder to use one extra
timeslice is not a definitive solution but tpcc workload shows it
does work and it works without requiring changes to database
locking code.

quoted

Theoretically a new locking library that uses both these
techniques will help solve the problem but being a new locking
library, there is a big unknown of what new problems, performance
and otherwise, it will bring and database has to recode to this
new library. Nevertheless this is the path I am exploring now.
The challenge being how to do this without requiring changes to
database code or the kernel. The hooks available to me into
current database code are schedctl_init(), schedctl_start() and 
schedctl_stop() which are no-op on Linux at this time.

That sounds like a feature.  Keep the uncontended operations fast
by not doing anything, and only slow down when there is contention.

Presumably the database people will optimize their code to avoid
contention, so any complexity can happen in the slow path, instead
of by adding things to the fast path...

- -- 
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJUme3NAAoJEM553pKExN6DD8gH/3am5Izrobk/AiN8sijg3YXA
a9orVuoWNE+BLt49PwWrYpjsR2AgN4G3BbUrb4GVhaFBL5/v/frUhk0As3w3uM21
QjxMtaFvqZviLWCFgtIna7zSxHom+v/eRiAjLtCoX+GtHs+t25Jyf1GowmZnkoNd
UtDPHPXmyA2CqZC0E9d53Uzb9XaP/T4G3J8U2aPSvwoj4Nw85H2S/QMptNQEJDjY
0Qpx/fv2Ze/gJ7GujU3gloX6cH5DDU+p9/pFZ7iDEB6jbbb384Zuacq6R6CeJMVB
EAxKW1tpFtPvaRC51x8TFNJY5FxSISbXKbehxKjXQ8rlkcM/k1euzo2KCKOp68w=
=cTlU
-----END PGP SIGNATURE-----

On Tue, Dec 23, 2014 at 01:46:58PM -0500, Rik van Riel wrote:

An uncontended futex is taken without ever going into kernel
space. Adaptive spinning allows short duration futexes to be
taken without going into kernel space.

The going into kernel is a red herring afaict, a no-op syscall costs ~180
cycles or something like that. So sure you can do a wee spin (~90 cycles
to try and amortize that), but I really doubt that this is the problem.