[PATCH v2 0/4] timer: Improve itimers scalability

[PATCH v2 0/4] timer: Improve itimers scalability

[Jason Low]

While running a database workload on a 16 socket machine, there were
scalability issues related to itimers. The following link contains a
more detailed summary of the issues at the application level.

https://lkml.org/lkml/2015/8/26/737

Commit 1018016c706f addressed the issue with the thread_group_cputimer
spinlock taking up a significant portion of total run time.
This patch series addresses the secondary issue where a lot of time is
spent trying to acquire the sighand lock. It was found in some cases
that 200+ threads were simultaneously contending for the same sighand
lock, reducing throughput by more than 30%.

With this patch set (along with commit 1018016c706f mentioned above),
the performance hit of itimers almost completely goes away on the
16 socket system.

Jason Low (4):
  timer: Optimize fastpath_timer_check()
  timer: Check thread timers only when there are active thread timers
  timer: Convert cputimer->running to bool
  timer: Reduce unnecessary sighand lock contention

 include/linux/init_task.h      |    3 +-
 include/linux/sched.h          |    9 ++++--
 kernel/fork.c                  |    2 +-
 kernel/time/posix-cpu-timers.c |   63 ++++++++++++++++++++++++++++-----------
 4 files changed, 54 insertions(+), 23 deletions(-)

-- 
1.7.2.5

[PATCH v2 1/4] timer: Optimize fastpath_timer_check()

[Jason Low]

In fastpath_timer_check(), the task_cputime() function is always
called to compute the utime and stime values. However, this is not
necessary if there are no per-thread timers to check for. This patch
modifies the code such that we compute the task_cputime values only
when there are per-thread timers set.

Signed-off-by: Jason Low <jason.low2@hp.com>
Reviewed-by: Oleg Nesterov <oleg@redhat.com>
Reviewed-by: Frederic Weisbecker <fweisbec@gmail.com>
Reviewed-by: Davidlohr Bueso <dave@stgolabs.net>
---
 kernel/time/posix-cpu-timers.c |   11 +++--------
 1 files changed, 3 insertions(+), 8 deletions(-)

diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index 892e3da..aa4b6f4 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -1117,17 +1117,12 @@ static inline int task_cputime_expired(const struct task_cputime *sample,
 static inline int fastpath_timer_check(struct task_struct *tsk)
 {
 	struct signal_struct *sig;
-	cputime_t utime, stime;
-
-	task_cputime(tsk, &utime, &stime);
 
 	if (!task_cputime_zero(&tsk->cputime_expires)) {
-		struct task_cputime task_sample = {
-			.utime = utime,
-			.stime = stime,
-			.sum_exec_runtime = tsk->se.sum_exec_runtime
-		};
+		struct task_cputime task_sample;
 
+		task_cputime(tsk, &task_sample.utime, &task_sample.stime);
+		task_sample.sum_exec_runtime = tsk->se.sum_exec_runtime;
 		if (task_cputime_expired(&task_sample, &tsk->cputime_expires))
 			return 1;
 	}
-- 
1.7.2.5

[PATCH v2 2/4] timer: Check thread timers only when there are active thread timers

[Jason Low]

The fastpath_timer_check() contains logic to check for if any timers
are set by checking if !task_cputime_zero(). Similarly, we can do this
before calling check_thread_timers(). In the case where there
are only process-wide timers, this will skip all of the computations for
per-thread timers when there are no per-thread timers.

As suggested by George, we can put the task_cputime_zero() check in
check_thread_timers(), since that is more of an optization to the
function. Similarly, we move the existing check of cputimer->running
to check_process_timers().

Signed-off-by: Jason Low <jason.low2@hp.com>
Reviewed-by: Oleg Nesterov <oleg@redhat.com>
---
 kernel/time/posix-cpu-timers.c |   22 ++++++++++++++++------
 1 files changed, 16 insertions(+), 6 deletions(-)

diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index aa4b6f4..6f6e252 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -864,6 +864,13 @@ static void check_thread_timers(struct task_struct *tsk,
 	unsigned long long expires;
 	unsigned long soft;
 
+	/*
+	 * If cputime_expires is zero, then there are no active
+	 * per thread CPU timers.
+	 */
+	if (task_cputime_zero(&tsk->cputime_expires))
+		return;
+
 	expires = check_timers_list(timers, firing, prof_ticks(tsk));
 	tsk_expires->prof_exp = expires_to_cputime(expires);
 
@@ -962,6 +969,13 @@ static void check_process_timers(struct task_struct *tsk,
 	unsigned long soft;
 
 	/*
+	 * If cputimer is not running, then there are no active
+	 * process wide timers (POSIX 1.b, itimers, RLIMIT_CPU).
+	 */
+	if (!READ_ONCE(tsk->signal->cputimer.running))
+		return;
+
+	/*
 	 * Collect the current process totals.
 	 */
 	thread_group_cputimer(tsk, &cputime);
@@ -1169,12 +1183,8 @@ void run_posix_cpu_timers(struct task_struct *tsk)
 	 * put them on the firing list.
 	 */
 	check_thread_timers(tsk, &firing);
-	/*
-	 * If there are any active process wide timers (POSIX 1.b, itimers,
-	 * RLIMIT_CPU) cputimer must be running.
-	 */
-	if (READ_ONCE(tsk->signal->cputimer.running))
-		check_process_timers(tsk, &firing);
+
+	check_process_timers(tsk, &firing);
 
 	/*
 	 * We must release these locks before taking any timer's lock.
-- 
1.7.2.5

[PATCH v2 3/4] timer: Convert cputimer->running to bool

[Jason Low]

In the next patch in this series, a new field 'checking_timer' will
be added to 'struct thread_group_cputimer'. Both this and the
existing 'running' integer field are just used as boolean values. To
save space in the structure, we can make both of these fields booleans.

This is a preparatory patch to convert the existing running integer
field to a boolean.

Suggested-by: George Spelvin <linux@horizon.com>
Signed-off-by: Jason Low <jason.low2@hp.com>
---
 include/linux/init_task.h      |    2 +-
 include/linux/sched.h          |    6 +++---
 kernel/fork.c                  |    2 +-
 kernel/time/posix-cpu-timers.c |    4 ++--
 4 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index e38681f..c43b80f 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -59,7 +59,7 @@ extern struct fs_struct init_fs;
 	.rlim		= INIT_RLIMITS,					\
 	.cputimer	= { 						\
 		.cputime_atomic	= INIT_CPUTIME_ATOMIC,			\
-		.running	= 0,					\
+		.running	= false,				\
 	},								\
 	INIT_PREV_CPUTIME(sig)						\
 	.cred_guard_mutex =						\
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 23ca455..35a9c46 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -623,15 +623,15 @@ struct task_cputime_atomic {
 /**
  * struct thread_group_cputimer - thread group interval timer counts
  * @cputime_atomic:	atomic thread group interval timers.
- * @running:		non-zero when there are timers running and
- *			@cputime receives updates.
+ * @running:		true when there are timers running and
+ *			@cputime_atomic receives updates.
  *
  * This structure contains the version of task_cputime, above, that is
  * used for thread group CPU timer calculations.
  */
 struct thread_group_cputimer {
 	struct task_cputime_atomic cputime_atomic;
-	int running;
+	bool running;
 };
 
 #include <linux/rwsem.h>
diff --git a/kernel/fork.c b/kernel/fork.c
index 83dea82..fe3f371 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1101,7 +1101,7 @@ static void posix_cpu_timers_init_group(struct signal_struct *sig)
 	cpu_limit = READ_ONCE(sig->rlim[RLIMIT_CPU].rlim_cur);
 	if (cpu_limit != RLIM_INFINITY) {
 		sig->cputime_expires.prof_exp = secs_to_cputime(cpu_limit);
-		sig->cputimer.running = 1;
+		sig->cputimer.running = true;
 	}
 
 	/* The timer lists. */
diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index 6f6e252..2d58153 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -249,7 +249,7 @@ void thread_group_cputimer(struct task_struct *tsk, struct task_cputime *times)
 		 * but barriers are not required because update_gt_cputime()
 		 * can handle concurrent updates.
 		 */
-		WRITE_ONCE(cputimer->running, 1);
+		WRITE_ONCE(cputimer->running, true);
 	}
 	sample_cputime_atomic(times, &cputimer->cputime_atomic);
 }
@@ -918,7 +918,7 @@ static inline void stop_process_timers(struct signal_struct *sig)
 	struct thread_group_cputimer *cputimer = &sig->cputimer;
 
 	/* Turn off cputimer->running. This is done without locking. */
-	WRITE_ONCE(cputimer->running, 0);
+	WRITE_ONCE(cputimer->running, false);
 }
 
 static u32 onecputick;
-- 
1.7.2.5

[PATCH v2 4/4] timer: Reduce unnecessary sighand lock contention

[Jason Low]

It was found while running a database workload on large systems that
significant time was spent trying to acquire the sighand lock.

The issue was that whenever an itimer expired, many threads ended up
simultaneously trying to send the signal. Most of the time, nothing
happened after acquiring the sighand lock because another thread
had just already sent the signal and updated the "next expire" time.
The fastpath_timer_check() didn't help much since the "next expire"
time was updated after the threads exit fastpath_timer_check().

This patch addresses this by having the thread_group_cputimer structure
maintain a boolean to signify when a thread in the group is already
checking for process wide timers, and adds extra logic in the fastpath
to check the boolean.

Signed-off-by: Jason Low <jason.low2@hp.com>
Reviewed-by: Oleg Nesterov <oleg@redhat.com>
---
 include/linux/init_task.h      |    1 +
 include/linux/sched.h          |    3 +++
 kernel/time/posix-cpu-timers.c |   26 ++++++++++++++++++++++++--
 3 files changed, 28 insertions(+), 2 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index c43b80f..810a34f 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -60,6 +60,7 @@ extern struct fs_struct init_fs;
 	.cputimer	= { 						\
 		.cputime_atomic	= INIT_CPUTIME_ATOMIC,			\
 		.running	= false,				\
+		.checking_timer = false,				\
 	},								\
 	INIT_PREV_CPUTIME(sig)						\
 	.cred_guard_mutex =						\
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 35a9c46..0f1ebec 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -625,6 +625,8 @@ struct task_cputime_atomic {
  * @cputime_atomic:	atomic thread group interval timers.
  * @running:		true when there are timers running and
  *			@cputime_atomic receives updates.
+ * @checking_timer:	true when a thread in the group is in the
+ *			process of checking for thread group timers.
  *
  * This structure contains the version of task_cputime, above, that is
  * used for thread group CPU timer calculations.
@@ -632,6 +634,7 @@ struct task_cputime_atomic {
 struct thread_group_cputimer {
 	struct task_cputime_atomic cputime_atomic;
 	bool running;
+	bool checking_timer;
 };
 
 #include <linux/rwsem.h>
diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index 2d58153..957fbae 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -975,6 +975,12 @@ static void check_process_timers(struct task_struct *tsk,
 	if (!READ_ONCE(tsk->signal->cputimer.running))
 		return;
 
+        /*
+	 * Signify that a thread is checking for process timers.
+	 * Write access to this field is protected by the sighand lock.
+	 */
+	sig->cputimer.checking_timer = true;
+
 	/*
 	 * Collect the current process totals.
 	 */
@@ -1029,6 +1035,8 @@ static void check_process_timers(struct task_struct *tsk,
 	sig->cputime_expires.sched_exp = sched_expires;
 	if (task_cputime_zero(&sig->cputime_expires))
 		stop_process_timers(sig);
+
+	sig->cputimer.checking_timer = false;
 }
 
 /*
@@ -1142,8 +1150,22 @@ static inline int fastpath_timer_check(struct task_struct *tsk)
 	}
 
 	sig = tsk->signal;
-	/* Check if cputimer is running. This is accessed without locking. */
-	if (READ_ONCE(sig->cputimer.running)) {
+	/*
+	 * Check if thread group timers expired when the cputimer is
+	 * running and no other thread in the group is already checking
+	 * for thread group cputimers. These fields are read without the
+	 * sighand lock. However, this is fine because this is meant to
+	 * be a fastpath heuristic to determine whether we should try to
+	 * acquire the sighand lock to check/handle timers.
+	 * 
+	 * In the worst case scenario, if 'running' or 'checking_timer' gets
+	 * set but the current thread doesn't see the change yet, we'll wait
+	 * until the next thread in the group gets a scheduler interrupt to
+	 * handle the timer. This isn't an issue in practice because these
+	 * types of delays with signals actually getting sent are expected.
+	 */
+	if (READ_ONCE(sig->cputimer.running) &&
+	    !READ_ONCE(sig->cputimer.checking_timer)) {
 		struct task_cputime group_sample;
 
 		sample_cputime_atomic(&group_sample, &sig->cputimer.cputime_atomic);
-- 
1.7.2.5

Re: [PATCH v2 0/4] timer: Improve itimers scalability

[George Spelvin]

I'm going to give 4/4 a closer look to see if the races with timer
expiration make more sense to me than last time around.
(E.g. do CPU time signals even work in CONFIG_NO_HZ_FULL?)

But although I haven't yet convinced myself the current code is right,
the changes don't seem to make it any worse.  So consider all four

Reviewed-by: George Spelvin <linux@horizon.com>

Thank you!

Re: [PATCH v2 0/4] timer: Improve itimers scalability

[Ingo Molnar]

* Jason Low <jason.low2@hp.com> wrote:

> While running a database workload on a 16 socket machine, there were
> scalability issues related to itimers. The following link contains a
> more detailed summary of the issues at the application level.
> 
> https://lkml.org/lkml/2015/8/26/737
> 
> Commit 1018016c706f addressed the issue with the thread_group_cputimer
> spinlock taking up a significant portion of total run time.
> This patch series addresses the secondary issue where a lot of time is
> spent trying to acquire the sighand lock. It was found in some cases
> that 200+ threads were simultaneously contending for the same sighand
> lock, reducing throughput by more than 30%.
> 
> With this patch set (along with commit 1018016c706f mentioned above),
> the performance hit of itimers almost completely goes away on the
> 16 socket system.
> 
> Jason Low (4):
>   timer: Optimize fastpath_timer_check()
>   timer: Check thread timers only when there are active thread timers
>   timer: Convert cputimer->running to bool
>   timer: Reduce unnecessary sighand lock contention
> 
>  include/linux/init_task.h      |    3 +-
>  include/linux/sched.h          |    9 ++++--
>  kernel/fork.c                  |    2 +-
>  kernel/time/posix-cpu-timers.c |   63 ++++++++++++++++++++++++++++-----------
>  4 files changed, 54 insertions(+), 23 deletions(-)

Is there some itimers benchmark that can be used to measure the effects of these 
changes?

Thanks,

	Ingo

[tip:timers/core] posix_cpu_timer: Optimize fastpath_timer_check( )

[tip-bot for Jason Low]

Commit-ID:  7c177d994eb9637302b79e80d331f48dfbe26368
Gitweb:     http://git.kernel.org/tip/7c177d994eb9637302b79e80d331f48dfbe26368
Author:     Jason Low <jason.low2@hp.com>
AuthorDate: Wed, 14 Oct 2015 12:07:53 -0700
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Thu, 15 Oct 2015 11:23:41 +0200

posix_cpu_timer: Optimize fastpath_timer_check()

In fastpath_timer_check(), the task_cputime() function is always
called to compute the utime and stime values. However, this is not
necessary if there are no per-thread timers to check for. This patch
modifies the code such that we compute the task_cputime values only
when there are per-thread timers set.

Signed-off-by: Jason Low <jason.low2@hp.com>
Reviewed-by: Oleg Nesterov <oleg@redhat.com>
Reviewed-by: Frederic Weisbecker <fweisbec@gmail.com>
Reviewed-by: Davidlohr Bueso <dave@stgolabs.net>
Reviewed-by: George Spelvin <linux@horizon.com>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: hideaki.kimura@hpe.com
Cc: terry.rudd@hpe.com
Cc: scott.norton@hpe.com
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1444849677-29330-2-git-send-email-jason.low2@hp.com
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 kernel/time/posix-cpu-timers.c | 11 +++--------
 1 file changed, 3 insertions(+), 8 deletions(-)

diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index 892e3da..aa4b6f4 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -1117,17 +1117,12 @@ static inline int task_cputime_expired(const struct task_cputime *sample,
 static inline int fastpath_timer_check(struct task_struct *tsk)
 {
 	struct signal_struct *sig;
-	cputime_t utime, stime;
-
-	task_cputime(tsk, &utime, &stime);
 
 	if (!task_cputime_zero(&tsk->cputime_expires)) {
-		struct task_cputime task_sample = {
-			.utime = utime,
-			.stime = stime,
-			.sum_exec_runtime = tsk->se.sum_exec_runtime
-		};
+		struct task_cputime task_sample;
 
+		task_cputime(tsk, &task_sample.utime, &task_sample.stime);
+		task_sample.sum_exec_runtime = tsk->se.sum_exec_runtime;
 		if (task_cputime_expired(&task_sample, &tsk->cputime_expires))
 			return 1;
 	}

[tip:timers/core] posix_cpu_timer: Check thread timers only when there are active thread timers

[tip-bot for Jason Low]

Commit-ID:  934715a191e4be0c602d39455a7a74316f274d60
Gitweb:     http://git.kernel.org/tip/934715a191e4be0c602d39455a7a74316f274d60
Author:     Jason Low <jason.low2@hp.com>
AuthorDate: Wed, 14 Oct 2015 12:07:54 -0700
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Thu, 15 Oct 2015 11:23:41 +0200

posix_cpu_timer: Check thread timers only when there are active thread timers

The fastpath_timer_check() contains logic to check for if any timers
are set by checking if !task_cputime_zero(). Similarly, we can do this
before calling check_thread_timers(). In the case where there
are only process-wide timers, this will skip all of the computations for
per-thread timers when there are no per-thread timers.

As suggested by George, we can put the task_cputime_zero() check in
check_thread_timers(), since that is more of an optization to the
function. Similarly, we move the existing check of cputimer->running
to check_process_timers().

Signed-off-by: Jason Low <jason.low2@hp.com>
Reviewed-by: Oleg Nesterov <oleg@redhat.com>
Reviewed-by: George Spelvin <linux@horizon.com>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: hideaki.kimura@hpe.com
Cc: terry.rudd@hpe.com
Cc: scott.norton@hpe.com
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1444849677-29330-3-git-send-email-jason.low2@hp.com
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 kernel/time/posix-cpu-timers.c | 22 ++++++++++++++++------
 1 file changed, 16 insertions(+), 6 deletions(-)

diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index aa4b6f4..6f6e252 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -864,6 +864,13 @@ static void check_thread_timers(struct task_struct *tsk,
 	unsigned long long expires;
 	unsigned long soft;
 
+	/*
+	 * If cputime_expires is zero, then there are no active
+	 * per thread CPU timers.
+	 */
+	if (task_cputime_zero(&tsk->cputime_expires))
+		return;
+
 	expires = check_timers_list(timers, firing, prof_ticks(tsk));
 	tsk_expires->prof_exp = expires_to_cputime(expires);
 
@@ -962,6 +969,13 @@ static void check_process_timers(struct task_struct *tsk,
 	unsigned long soft;
 
 	/*
+	 * If cputimer is not running, then there are no active
+	 * process wide timers (POSIX 1.b, itimers, RLIMIT_CPU).
+	 */
+	if (!READ_ONCE(tsk->signal->cputimer.running))
+		return;
+
+	/*
 	 * Collect the current process totals.
 	 */
 	thread_group_cputimer(tsk, &cputime);
@@ -1169,12 +1183,8 @@ void run_posix_cpu_timers(struct task_struct *tsk)
 	 * put them on the firing list.
 	 */
 	check_thread_timers(tsk, &firing);
-	/*
-	 * If there are any active process wide timers (POSIX 1.b, itimers,
-	 * RLIMIT_CPU) cputimer must be running.
-	 */
-	if (READ_ONCE(tsk->signal->cputimer.running))
-		check_process_timers(tsk, &firing);
+
+	check_process_timers(tsk, &firing);
 
 	/*
 	 * We must release these locks before taking any timer's lock.

[tip:timers/core] posix_cpu_timer: Convert cputimer-> running to bool

[tip-bot for Jason Low]

Commit-ID:  d5c373eb5610686162ff50429f63f4c00c554799
Gitweb:     http://git.kernel.org/tip/d5c373eb5610686162ff50429f63f4c00c554799
Author:     Jason Low <jason.low2@hp.com>
AuthorDate: Wed, 14 Oct 2015 12:07:55 -0700
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Thu, 15 Oct 2015 11:23:41 +0200

posix_cpu_timer: Convert cputimer->running to bool

In the next patch in this series, a new field 'checking_timer' will
be added to 'struct thread_group_cputimer'. Both this and the
existing 'running' integer field are just used as boolean values. To
save space in the structure, we can make both of these fields booleans.

This is a preparatory patch to convert the existing running integer
field to a boolean.

Suggested-by: George Spelvin <linux@horizon.com>
Signed-off-by: Jason Low <jason.low2@hp.com>
Reviewed: George Spelvin <linux@horizon.com>
Cc: Oleg Nesterov <oleg@redhat.com>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: hideaki.kimura@hpe.com
Cc: terry.rudd@hpe.com
Cc: scott.norton@hpe.com
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1444849677-29330-4-git-send-email-jason.low2@hp.com
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 include/linux/init_task.h      | 2 +-
 include/linux/sched.h          | 6 +++---
 kernel/fork.c                  | 2 +-
 kernel/time/posix-cpu-timers.c | 4 ++--
 4 files changed, 7 insertions(+), 7 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index e38681f..c43b80f 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -59,7 +59,7 @@ extern struct fs_struct init_fs;
 	.rlim		= INIT_RLIMITS,					\
 	.cputimer	= { 						\
 		.cputime_atomic	= INIT_CPUTIME_ATOMIC,			\
-		.running	= 0,					\
+		.running	= false,				\
 	},								\
 	INIT_PREV_CPUTIME(sig)						\
 	.cred_guard_mutex =						\
diff --git a/include/linux/sched.h b/include/linux/sched.h
index b7b9501..6c8504a 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -617,15 +617,15 @@ struct task_cputime_atomic {
 /**
  * struct thread_group_cputimer - thread group interval timer counts
  * @cputime_atomic:	atomic thread group interval timers.
- * @running:		non-zero when there are timers running and
- * 			@cputime receives updates.
+ * @running:		true when there are timers running and
+ *			@cputime_atomic receives updates.
  *
  * This structure contains the version of task_cputime, above, that is
  * used for thread group CPU timer calculations.
  */
 struct thread_group_cputimer {
 	struct task_cputime_atomic cputime_atomic;
-	int running;
+	bool running;
 };
 
 #include <linux/rwsem.h>
diff --git a/kernel/fork.c b/kernel/fork.c
index 2845623..6ac8942 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1101,7 +1101,7 @@ static void posix_cpu_timers_init_group(struct signal_struct *sig)
 	cpu_limit = READ_ONCE(sig->rlim[RLIMIT_CPU].rlim_cur);
 	if (cpu_limit != RLIM_INFINITY) {
 		sig->cputime_expires.prof_exp = secs_to_cputime(cpu_limit);
-		sig->cputimer.running = 1;
+		sig->cputimer.running = true;
 	}
 
 	/* The timer lists. */
diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index 6f6e252..2d58153 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -249,7 +249,7 @@ void thread_group_cputimer(struct task_struct *tsk, struct task_cputime *times)
 		 * but barriers are not required because update_gt_cputime()
 		 * can handle concurrent updates.
 		 */
-		WRITE_ONCE(cputimer->running, 1);
+		WRITE_ONCE(cputimer->running, true);
 	}
 	sample_cputime_atomic(times, &cputimer->cputime_atomic);
 }
@@ -918,7 +918,7 @@ static inline void stop_process_timers(struct signal_struct *sig)
 	struct thread_group_cputimer *cputimer = &sig->cputimer;
 
 	/* Turn off cputimer->running. This is done without locking. */
-	WRITE_ONCE(cputimer->running, 0);
+	WRITE_ONCE(cputimer->running, false);
 }
 
 static u32 onecputick;

[tip:timers/core] posix_cpu_timer: Reduce unnecessary sighand lock contention

[tip-bot for Jason Low]

Commit-ID:  c8d75aa47dd585c9538a8205e9bb9847e12cfb84
Gitweb:     http://git.kernel.org/tip/c8d75aa47dd585c9538a8205e9bb9847e12cfb84
Author:     Jason Low <jason.low2@hp.com>
AuthorDate: Wed, 14 Oct 2015 12:07:56 -0700
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Thu, 15 Oct 2015 11:23:41 +0200

posix_cpu_timer: Reduce unnecessary sighand lock contention

It was found while running a database workload on large systems that
significant time was spent trying to acquire the sighand lock.

The issue was that whenever an itimer expired, many threads ended up
simultaneously trying to send the signal. Most of the time, nothing
happened after acquiring the sighand lock because another thread
had just already sent the signal and updated the "next expire" time.
The fastpath_timer_check() didn't help much since the "next expire"
time was updated after the threads exit fastpath_timer_check().

This patch addresses this by having the thread_group_cputimer structure
maintain a boolean to signify when a thread in the group is already
checking for process wide timers, and adds extra logic in the fastpath
to check the boolean.

Signed-off-by: Jason Low <jason.low2@hp.com>
Reviewed-by: Oleg Nesterov <oleg@redhat.com>
Reviewed-by: George Spelvin <linux@horizon.com>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Davidlohr Bueso <dave@stgolabs.net>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: hideaki.kimura@hpe.com
Cc: terry.rudd@hpe.com
Cc: scott.norton@hpe.com
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1444849677-29330-5-git-send-email-jason.low2@hp.com
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 include/linux/init_task.h      |  1 +
 include/linux/sched.h          |  3 +++
 kernel/time/posix-cpu-timers.c | 26 ++++++++++++++++++++++++--
 3 files changed, 28 insertions(+), 2 deletions(-)

diff --git a/include/linux/init_task.h b/include/linux/init_task.h
index c43b80f..810a34f 100644
--- a/include/linux/init_task.h
+++ b/include/linux/init_task.h
@@ -60,6 +60,7 @@ extern struct fs_struct init_fs;
 	.cputimer	= { 						\
 		.cputime_atomic	= INIT_CPUTIME_ATOMIC,			\
 		.running	= false,				\
+		.checking_timer = false,				\
 	},								\
 	INIT_PREV_CPUTIME(sig)						\
 	.cred_guard_mutex =						\
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 6c8504a..f87559d 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -619,6 +619,8 @@ struct task_cputime_atomic {
  * @cputime_atomic:	atomic thread group interval timers.
  * @running:		true when there are timers running and
  *			@cputime_atomic receives updates.
+ * @checking_timer:	true when a thread in the group is in the
+ *			process of checking for thread group timers.
  *
  * This structure contains the version of task_cputime, above, that is
  * used for thread group CPU timer calculations.
@@ -626,6 +628,7 @@ struct task_cputime_atomic {
 struct thread_group_cputimer {
 	struct task_cputime_atomic cputime_atomic;
 	bool running;
+	bool checking_timer;
 };
 
 #include <linux/rwsem.h>
diff --git a/kernel/time/posix-cpu-timers.c b/kernel/time/posix-cpu-timers.c
index 2d58153..f5e86d2 100644
--- a/kernel/time/posix-cpu-timers.c
+++ b/kernel/time/posix-cpu-timers.c
@@ -975,6 +975,12 @@ static void check_process_timers(struct task_struct *tsk,
 	if (!READ_ONCE(tsk->signal->cputimer.running))
 		return;
 
+        /*
+	 * Signify that a thread is checking for process timers.
+	 * Write access to this field is protected by the sighand lock.
+	 */
+	sig->cputimer.checking_timer = true;
+
 	/*
 	 * Collect the current process totals.
 	 */
@@ -1029,6 +1035,8 @@ static void check_process_timers(struct task_struct *tsk,
 	sig->cputime_expires.sched_exp = sched_expires;
 	if (task_cputime_zero(&sig->cputime_expires))
 		stop_process_timers(sig);
+
+	sig->cputimer.checking_timer = false;
 }
 
 /*
@@ -1142,8 +1150,22 @@ static inline int fastpath_timer_check(struct task_struct *tsk)
 	}
 
 	sig = tsk->signal;
-	/* Check if cputimer is running. This is accessed without locking. */
-	if (READ_ONCE(sig->cputimer.running)) {
+	/*
+	 * Check if thread group timers expired when the cputimer is
+	 * running and no other thread in the group is already checking
+	 * for thread group cputimers. These fields are read without the
+	 * sighand lock. However, this is fine because this is meant to
+	 * be a fastpath heuristic to determine whether we should try to
+	 * acquire the sighand lock to check/handle timers.
+	 *
+	 * In the worst case scenario, if 'running' or 'checking_timer' gets
+	 * set but the current thread doesn't see the change yet, we'll wait
+	 * until the next thread in the group gets a scheduler interrupt to
+	 * handle the timer. This isn't an issue in practice because these
+	 * types of delays with signals actually getting sent are expected.
+	 */
+	if (READ_ONCE(sig->cputimer.running) &&
+	    !READ_ONCE(sig->cputimer.checking_timer)) {
 		struct task_cputime group_sample;
 
 		sample_cputime_atomic(&group_sample, &sig->cputimer.cputime_atomic);

Re: [PATCH v2 0/4] timer: Improve itimers scalability

[Frederic Weisbecker]

On Wed, Oct 14, 2015 at 05:18:27PM -0400, George Spelvin wrote:
> I'm going to give 4/4 a closer look to see if the races with timer
> expiration make more sense to me than last time around.
> (E.g. do CPU time signals even work in CONFIG_NO_HZ_FULL?)

Those enqueued with timer_settime() do work. But itimers,
and rlimits (RLIMIT_RTTIME, RLIMIT_CPU) aren't supported well. I
need to rework that.

> 
> But although I haven't yet convinced myself the current code is right,
> the changes don't seem to make it any worse.  So consider all four
> 
> Reviewed-by: George Spelvin <linux@horizon.com>
> 
> Thank you!

Re: [PATCH v2 0/4] timer: Improve itimers scalability

[Jason Low]

On Wed, 2015-10-14 at 17:18 -0400, George Spelvin wrote:
> I'm going to give 4/4 a closer look to see if the races with timer
> expiration make more sense to me than last time around.
> (E.g. do CPU time signals even work in CONFIG_NO_HZ_FULL?)
> 
> But although I haven't yet convinced myself the current code is right,
> the changes don't seem to make it any worse.  So consider all four
> 
> Reviewed-by: George Spelvin <linux@horizon.com>

Thanks George!

Re: [PATCH v2 0/4] timer: Improve itimers scalability

[Jason Low]

On Thu, 2015-10-15 at 10:47 +0200, Ingo Molnar wrote:
> * Jason Low <jason.low2@hp.com> wrote:
> 
> > While running a database workload on a 16 socket machine, there were
> > scalability issues related to itimers. The following link contains a
> > more detailed summary of the issues at the application level.
> > 
> > https://lkml.org/lkml/2015/8/26/737
> > 
> > Commit 1018016c706f addressed the issue with the thread_group_cputimer
> > spinlock taking up a significant portion of total run time.
> > This patch series addresses the secondary issue where a lot of time is
> > spent trying to acquire the sighand lock. It was found in some cases
> > that 200+ threads were simultaneously contending for the same sighand
> > lock, reducing throughput by more than 30%.
> > 
> > With this patch set (along with commit 1018016c706f mentioned above),
> > the performance hit of itimers almost completely goes away on the
> > 16 socket system.
> > 
> > Jason Low (4):
> >   timer: Optimize fastpath_timer_check()
> >   timer: Check thread timers only when there are active thread timers
> >   timer: Convert cputimer->running to bool
> >   timer: Reduce unnecessary sighand lock contention
> > 
> >  include/linux/init_task.h      |    3 +-
> >  include/linux/sched.h          |    9 ++++--
> >  kernel/fork.c                  |    2 +-
> >  kernel/time/posix-cpu-timers.c |   63 ++++++++++++++++++++++++++++-----------
> >  4 files changed, 54 insertions(+), 23 deletions(-)
> 
> Is there some itimers benchmark that can be used to measure the effects of these 
> changes?

Yes, we also wrote a micro benchmark which generates cache misses and
measures the average cost of each cache miss (with itimers enabled). We
used this while writing and testing patches, since it takes a bit longer
to set up and run the database.

Jason

Re: [PATCH v2 0/4] timer: Improve itimers scalability

[Ingo Molnar]

* Jason Low <jason.low@hpe.com> wrote:

> > > With this patch set (along with commit 1018016c706f mentioned above),
> > > the performance hit of itimers almost completely goes away on the
> > > 16 socket system.
> > > 
> > > Jason Low (4):
> > >   timer: Optimize fastpath_timer_check()
> > >   timer: Check thread timers only when there are active thread timers
> > >   timer: Convert cputimer->running to bool
> > >   timer: Reduce unnecessary sighand lock contention
> > > 
> > >  include/linux/init_task.h      |    3 +-
> > >  include/linux/sched.h          |    9 ++++--
> > >  kernel/fork.c                  |    2 +-
> > >  kernel/time/posix-cpu-timers.c |   63 ++++++++++++++++++++++++++++-----------
> > >  4 files changed, 54 insertions(+), 23 deletions(-)
> > 
> > Is there some itimers benchmark that can be used to measure the effects of these 
> > changes?
> 
> Yes, we also wrote a micro benchmark which generates cache misses and measures 
> the average cost of each cache miss (with itimers enabled). We used this while 
> writing and testing patches, since it takes a bit longer to set up and run the 
> database.

Mind posting it, so that people can stick it into a new 'perf bench timer' 
subcommand, and/or reproduce your results with it?

Thanks,

	Ingo

Re: [PATCH v2 0/4] timer: Improve itimers scalability

[Jason Low]

On Fri, 2015-10-16 at 09:12 +0200, Ingo Molnar wrote:
> * Jason Low <jason.low@hpe.com> wrote:
> 
> > > > With this patch set (along with commit 1018016c706f mentioned above),
> > > > the performance hit of itimers almost completely goes away on the
> > > > 16 socket system.
> > > > 
> > > > Jason Low (4):
> > > >   timer: Optimize fastpath_timer_check()
> > > >   timer: Check thread timers only when there are active thread timers
> > > >   timer: Convert cputimer->running to bool
> > > >   timer: Reduce unnecessary sighand lock contention
> > > > 
> > > >  include/linux/init_task.h      |    3 +-
> > > >  include/linux/sched.h          |    9 ++++--
> > > >  kernel/fork.c                  |    2 +-
> > > >  kernel/time/posix-cpu-timers.c |   63 ++++++++++++++++++++++++++++-----------
> > > >  4 files changed, 54 insertions(+), 23 deletions(-)
> > > 
> > > Is there some itimers benchmark that can be used to measure the effects of these 
> > > changes?
> > 
> > Yes, we also wrote a micro benchmark which generates cache misses and measures 
> > the average cost of each cache miss (with itimers enabled). We used this while 
> > writing and testing patches, since it takes a bit longer to set up and run the 
> > database.
> 
> Mind posting it, so that people can stick it into a new 'perf bench timer' 
> subcommand, and/or reproduce your results with it?

Yes, sure. At the moment, this micro benchmark is written in C++ and
integrated with the database code. We can look into rewriting it into a
more general program so that it can be included in perf.

Thanks,
Jason

Re: [PATCH v2 0/4] timer: Improve itimers scalability

[Hideaki Kimura]

Removing dependency to the database code is trivial. It's just 100 lines 
that launch lots of threads and do NUMA-aware memory accesses so that 
remote NUMA access cost does not affect the benchmark.

It's just a bit tedious to convert the C++11 code into C/pthread.
C++11 really spoiled me.
Still, not much work. Let me know where to post the code.

On 10/16/2015 10:34 AM, Jason Low wrote:
>> Mind posting it, so that people can stick it into a new 'perf bench timer'
>> subcommand, and/or reproduce your results with it?
>
> Yes, sure. At the moment, this micro benchmark is written in C++ and
> integrated with the database code. We can look into rewriting it into a
> more general program so that it can be included in perf.
>
> Thanks,
> Jason
>

-- 
Hideaki Kimura