[PATCH 0/2] sched,time: reduce nohz_full syscall overhead 40%

[PATCH 0/2] sched,time: reduce nohz_full syscall overhead 40%

[riel]

unning with nohz_full introduces a fair amount of overhead.
Specifically, various things that are usually done from the
timer interrupt are now done at syscall, irq, and guest
entry and exit times.

However, some of the code that is called every single time
has only ever worked at jiffy resolution. The code in
__acct_update_integrals was also doing some unnecessary
calculations.

Getting rid of the unnecessary calculations, without
changing any of the functionality in __acct_update_integrals
gets us about an 11% win.

Not calling the time statistics updating code more than
once per jiffy, like is done on housekeeping CPUs and on
all the CPUs of a non-nohz_full system, shaves off a
further 30%.

I tested this series with a microbenchmark calling
an invalid syscall number ten million times in a row,
on a nohz_full cpu.

    Run times for the microbenchmark:
    
4.4				3.8 seconds
4.5-rc1				3.7 seconds
4.5-rc1 + first patch		3.3 seconds
4.5-rc1 + first 3 patches	3.1 seconds
4.5-rc1 + all patches		2.3 seconds

[PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[riel]

From: Rik van Riel <riel@redhat.com>

When running a microbenchmark calling an invalid syscall number
in a loop, on a nohz_full CPU, we spend a full 9% of our CPU
time in __acct_update_integrals.

This function converts cputime_t to jiffies, to a timeval, only to
convert the timeval back to microseconds before discarding it.

This patch leaves __acct_update_integrals functionally equivalent,
but speeds things up by about 12%, with 10 million calls to an
invalid syscall number dropping from 3.7 to 3.25 seconds.

Signed-off-by: Rik van Riel <riel@redhat.com>
---
 kernel/tsacct.c | 19 +++++++++----------
 1 file changed, 9 insertions(+), 10 deletions(-)

diff --git a/kernel/tsacct.c b/kernel/tsacct.c
index 975cb49e32bf..41667b23dbd0 100644
--- a/kernel/tsacct.c
+++ b/kernel/tsacct.c
@@ -93,9 +93,9 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
 {
 	struct mm_struct *mm;
 
-	/* convert pages-usec to Mbyte-usec */
-	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
-	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
+	/* convert pages-nsec/KB to Mbyte-usec, see __acct_update_integrals */
+	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / (1000 * KB);
+	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / (1000 * KB);
 	mm = get_task_mm(p);
 	if (mm) {
 		/* adjust to KB unit */
@@ -125,22 +125,21 @@ static void __acct_update_integrals(struct task_struct *tsk,
 {
 	if (likely(tsk->mm)) {
 		cputime_t time, dtime;
-		struct timeval value;
 		unsigned long flags;
 		u64 delta;
 
 		local_irq_save(flags);
 		time = stime + utime;
 		dtime = time - tsk->acct_timexpd;
-		jiffies_to_timeval(cputime_to_jiffies(dtime), &value);
-		delta = value.tv_sec;
-		delta = delta * USEC_PER_SEC + value.tv_usec;
+		delta = cputime_to_nsecs(dtime);
 
-		if (delta == 0)
+		if (delta < TICK_NSEC)
 			goto out;
+
 		tsk->acct_timexpd = time;
-		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm);
-		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm;
+		/* The final unit will be Mbyte-usecs, see xacct_add_tsk */
+		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) / 1024;
+		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm / 1024;
 	out:
 		local_irq_restore(flags);
 	}
-- 
2.5.0

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 905 bytes --]

Hi Rik,

[auto build test ERROR on tip/sched/core]
[also build test ERROR on v4.5-rc1 next-20160129]
[if your patch is applied to the wrong git tree, please drop us a note to help improving the system]

url:    https://github.com/0day-ci/linux/commits/riel-redhat-com/sched-time-remove-non-power-of-two-divides-from-__acct_update_integrals/20160130-114019
config: i386-defconfig (attached as .config)
reproduce:
        # save the attached .config to linux build tree
        make ARCH=i386 

All errors (new ones prefixed by >>):

   kernel/built-in.o: In function `xacct_add_tsk':
>> (.text+0x906b0): undefined reference to `__udivdi3'
   kernel/built-in.o: In function `xacct_add_tsk':
   (.text+0x906e3): undefined reference to `__udivdi3'

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

[-- Attachment #2: .config.gz --]
[-- Type: application/octet-stream, Size: 23958 bytes --]

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[Frederic Weisbecker]

On Fri, Jan 29, 2016 at 10:36:02PM -0500, riel@redhat.com wrote:
> From: Rik van Riel <riel@redhat.com>
> 
> When running a microbenchmark calling an invalid syscall number
> in a loop, on a nohz_full CPU, we spend a full 9% of our CPU
> time in __acct_update_integrals.
> 
> This function converts cputime_t to jiffies, to a timeval, only to
> convert the timeval back to microseconds before discarding it.
> 
> This patch leaves __acct_update_integrals functionally equivalent,
> but speeds things up by about 12%, with 10 million calls to an
> invalid syscall number dropping from 3.7 to 3.25 seconds.
> 
> Signed-off-by: Rik van Riel <riel@redhat.com>
> ---
>  kernel/tsacct.c | 19 +++++++++----------
>  1 file changed, 9 insertions(+), 10 deletions(-)
> 
> diff --git a/kernel/tsacct.c b/kernel/tsacct.c
> index 975cb49e32bf..41667b23dbd0 100644
> --- a/kernel/tsacct.c
> +++ b/kernel/tsacct.c
> @@ -93,9 +93,9 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
>  {
>  	struct mm_struct *mm;
>  
> -	/* convert pages-usec to Mbyte-usec */
> -	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
> -	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
> +	/* convert pages-nsec/KB to Mbyte-usec, see __acct_update_integrals */
> +	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / (1000 * KB);
> +	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / (1000 * KB);
>  	mm = get_task_mm(p);
>  	if (mm) {
>  		/* adjust to KB unit */
> @@ -125,22 +125,21 @@ static void __acct_update_integrals(struct task_struct *tsk,
>  {
>  	if (likely(tsk->mm)) {
>  		cputime_t time, dtime;
> -		struct timeval value;
>  		unsigned long flags;
>  		u64 delta;
>  
>  		local_irq_save(flags);
>  		time = stime + utime;
>  		dtime = time - tsk->acct_timexpd;
> -		jiffies_to_timeval(cputime_to_jiffies(dtime), &value);
> -		delta = value.tv_sec;
> -		delta = delta * USEC_PER_SEC + value.tv_usec;
> +		delta = cputime_to_nsecs(dtime);

You might want to add a comment specifying why we don't call cputime_to_usecs()
directly (because we optimize if delta < TICK_NSEC).

Although this has a good impact on nohz_full, it might have a tiny bad one on !nohz_full
because now we first convert jiffies to nsecs (which implies a multiplication by 1000)
that we later divide again by 1000. Now this is ok because I plan to convert tsk->utime/stime
to nsecs and thus remove most of the cputime_t use and conversions everywhere.

>  
> -		if (delta == 0)
> +		if (delta < TICK_NSEC)
>  			goto out;


> +
>  		tsk->acct_timexpd = time;
> -		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm);
> -		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm;
> +		/* The final unit will be Mbyte-usecs, see xacct_add_tsk */
> +		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) / 1024;
> +		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm / 1024;

The use of 1024 and the change on MB above are confusing me. Why are we doing that?

Thanks.

>  	out:
>  		local_irq_restore(flags);
>  	}
> -- 
> 2.5.0
> 

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[Rik van Riel]

On 01/30/2016 09:44 AM, Frederic Weisbecker wrote:
> On Fri, Jan 29, 2016 at 10:36:02PM -0500, riel@redhat.com wrote:
>> From: Rik van Riel <riel@redhat.com>
>>
>> When running a microbenchmark calling an invalid syscall number
>> in a loop, on a nohz_full CPU, we spend a full 9% of our CPU
>> time in __acct_update_integrals.
>>
>> This function converts cputime_t to jiffies, to a timeval, only to
>> convert the timeval back to microseconds before discarding it.
>>
>> This patch leaves __acct_update_integrals functionally equivalent,
>> but speeds things up by about 12%, with 10 million calls to an
>> invalid syscall number dropping from 3.7 to 3.25 seconds.
>>
>> Signed-off-by: Rik van Riel <riel@redhat.com>
>> ---
>>  kernel/tsacct.c | 19 +++++++++----------
>>  1 file changed, 9 insertions(+), 10 deletions(-)
>>
>> diff --git a/kernel/tsacct.c b/kernel/tsacct.c
>> index 975cb49e32bf..41667b23dbd0 100644
>> --- a/kernel/tsacct.c
>> +++ b/kernel/tsacct.c
>> @@ -93,9 +93,9 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
>>  {
>>  	struct mm_struct *mm;
>>  
>> -	/* convert pages-usec to Mbyte-usec */
>> -	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
>> -	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
>> +	/* convert pages-nsec/KB to Mbyte-usec, see __acct_update_integrals */
>> +	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / (1000 * KB);
>> +	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / (1000 * KB);
>>  	mm = get_task_mm(p);
>>  	if (mm) {
>>  		/* adjust to KB unit */
>> @@ -125,22 +125,21 @@ static void __acct_update_integrals(struct task_struct *tsk,
>>  {
>>  	if (likely(tsk->mm)) {
>>  		cputime_t time, dtime;
>> -		struct timeval value;
>>  		unsigned long flags;
>>  		u64 delta;
>>  
>>  		local_irq_save(flags);
>>  		time = stime + utime;
>>  		dtime = time - tsk->acct_timexpd;
>> -		jiffies_to_timeval(cputime_to_jiffies(dtime), &value);
>> -		delta = value.tv_sec;
>> -		delta = delta * USEC_PER_SEC + value.tv_usec;
>> +		delta = cputime_to_nsecs(dtime);
> 
> You might want to add a comment specifying why we don't call cputime_to_usecs()
> directly (because we optimize if delta < TICK_NSEC).
> 
> Although this has a good impact on nohz_full, it might have a tiny bad one on !nohz_full
> because now we first convert jiffies to nsecs (which implies a multiplication by 1000)
> that we later divide again by 1000. Now this is ok because I plan to convert tsk->utime/stime
> to nsecs and thus remove most of the cputime_t use and conversions everywhere.

Isn't cputime_t in nanoseconds even on !nohz_full systems nowadays,
due to sched_clock?

Also, a multiplication is essentially instantaneous compared to
a division, which is why Peter suggested going this way around.

>>  
>> -		if (delta == 0)
>> +		if (delta < TICK_NSEC)
>>  			goto out;
> 
> 
>> +
>>  		tsk->acct_timexpd = time;
>> -		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm);
>> -		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm;
>> +		/* The final unit will be Mbyte-usecs, see xacct_add_tsk */
>> +		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) / 1024;
>> +		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm / 1024;
> 
> The use of 1024 and the change on MB above are confusing me. Why are we doing that?
> 
> Thanks.

So the compiler can just do a right shift in the frequently called
code, and have no divide at all left in __acct_update_integrals.
However, reducing the value here does seem useful for the prevention
of overflows.

The divide is saved for when the statistics are read out to
userspace.

-- 
All rights reversed

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[Peter Zijlstra]

On Sat, Jan 30, 2016 at 12:53:09PM -0500, Rik van Riel wrote:
> >> +		delta = cputime_to_nsecs(dtime);
> > 
> > You might want to add a comment specifying why we don't call cputime_to_usecs()
> > directly (because we optimize if delta < TICK_NSEC).
> > 
> > Although this has a good impact on nohz_full, it might have a tiny bad one on !nohz_full
> > because now we first convert jiffies to nsecs (which implies a multiplication by 1000)
> > that we later divide again by 1000. Now this is ok because I plan to convert tsk->utime/stime
> > to nsecs and thus remove most of the cputime_t use and conversions everywhere.
> 
> Isn't cputime_t in nanoseconds even on !nohz_full systems nowadays,
> due to sched_clock?

Don't think so, we still use jiffy accounting for !NOHZ_FULL.

> Also, a multiplication is essentially instantaneous compared to
> a division, which is why Peter suggested going this way around.

Yep.

[PATCH 2/4] acct,time: change indentation in __acct_update_integrals

[riel]

From: Rik van Riel <riel@redhat.com>

Change the indentation in __acct_update_integrals to make the function
a little easier to read.

Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Rik van Riel <riel@redhat.com>
---
 kernel/tsacct.c | 41 +++++++++++++++++++++--------------------
 1 file changed, 21 insertions(+), 20 deletions(-)

diff --git a/kernel/tsacct.c b/kernel/tsacct.c
index 41667b23dbd0..8908f8b1d26e 100644
--- a/kernel/tsacct.c
+++ b/kernel/tsacct.c
@@ -123,26 +123,27 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
 static void __acct_update_integrals(struct task_struct *tsk,
 				    cputime_t utime, cputime_t stime)
 {
-	if (likely(tsk->mm)) {
-		cputime_t time, dtime;
-		unsigned long flags;
-		u64 delta;
-
-		local_irq_save(flags);
-		time = stime + utime;
-		dtime = time - tsk->acct_timexpd;
-		delta = cputime_to_nsecs(dtime);
-
-		if (delta < TICK_NSEC)
-			goto out;
-
-		tsk->acct_timexpd = time;
-		/* The final unit will be Mbyte-usecs, see xacct_add_tsk */
-		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) / 1024;
-		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm / 1024;
-	out:
-		local_irq_restore(flags);
-	}
+	cputime_t time, dtime;
+	unsigned long flags;
+	u64 delta;
+
+	if (unlikely(!tsk->mm))
+		return;
+
+	local_irq_save(flags);
+	time = stime + utime;
+	dtime = time - tsk->acct_timexpd;
+	delta = cputime_to_nsecs(dtime);
+
+	if (delta < TICK_NSEC)
+		goto out;
+
+	tsk->acct_timexpd = time;
+	/* The final unit will be Mbyte-usecs, see xacct_add_tsk */
+	tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) / 1024;
+	tsk->acct_vm_mem1 += delta * tsk->mm->total_vm / 1024;
+out:
+	local_irq_restore(flags);
 }
 
 /**
-- 
2.5.0

Re: [PATCH 2/4] acct,time: change indentation in __acct_update_integrals

[Frederic Weisbecker]

On Fri, Jan 29, 2016 at 10:36:03PM -0500, riel@redhat.com wrote:
> From: Rik van Riel <riel@redhat.com>
> 
> Change the indentation in __acct_update_integrals to make the function
> a little easier to read.
> 
> Suggested-by: Peter Zijlstra <peterz@infradead.org>
> Signed-off-by: Rik van Riel <riel@redhat.com>

ACK.

[PATCH 3/4] time,acct: drop irq save & restore from __acct_update_integrals

[riel]

From: Rik van Riel <riel@redhat.com>

It looks like all the call paths that lead to __acct_update_integrals
already have irqs disabled, and __acct_update_integrals does not need
to disable irqs itself.

This is very convenient since about half the CPU time left in this
function was spent in local_irq_save alone.

Performance of a microbenchmark that calls an invalid syscall
ten million times in a row on a nohz_full CPU improves 21% vs.
4.5-rc1 with both the removal of divisions from __acct_update_integrals
and this patch, with runtime dropping from 3.7 to 2.9 seconds.

With these patches applied, the highest remaining cpu user in
the trace is native_sched_clock, which is addressed in the next
patch.

Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Rik van Riel <riel@redhat.com>
---
 kernel/tsacct.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

diff --git a/kernel/tsacct.c b/kernel/tsacct.c
index 8908f8b1d26e..b2663d699a72 100644
--- a/kernel/tsacct.c
+++ b/kernel/tsacct.c
@@ -124,26 +124,22 @@ static void __acct_update_integrals(struct task_struct *tsk,
 				    cputime_t utime, cputime_t stime)
 {
 	cputime_t time, dtime;
-	unsigned long flags;
 	u64 delta;
 
 	if (unlikely(!tsk->mm))
 		return;
 
-	local_irq_save(flags);
 	time = stime + utime;
 	dtime = time - tsk->acct_timexpd;
 	delta = cputime_to_nsecs(dtime);
 
 	if (delta < TICK_NSEC)
-		goto out;
+		return;
 
 	tsk->acct_timexpd = time;
 	/* The final unit will be Mbyte-usecs, see xacct_add_tsk */
 	tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) / 1024;
 	tsk->acct_vm_mem1 += delta * tsk->mm->total_vm / 1024;
-out:
-	local_irq_restore(flags);
 }
 
 /**
-- 
2.5.0

Re: [PATCH 3/4] time,acct: drop irq save & restore from __acct_update_integrals

[Frederic Weisbecker]

On Fri, Jan 29, 2016 at 10:36:04PM -0500, riel@redhat.com wrote:
> From: Rik van Riel <riel@redhat.com>
> 
> It looks like all the call paths that lead to __acct_update_integrals
> already have irqs disabled, and __acct_update_integrals does not need
> to disable irqs itself.
> 
> This is very convenient since about half the CPU time left in this
> function was spent in local_irq_save alone.
> 
> Performance of a microbenchmark that calls an invalid syscall
> ten million times in a row on a nohz_full CPU improves 21% vs.
> 4.5-rc1 with both the removal of divisions from __acct_update_integrals
> and this patch, with runtime dropping from 3.7 to 2.9 seconds.
> 
> With these patches applied, the highest remaining cpu user in
> the trace is native_sched_clock, which is addressed in the next
> patch.
> 
> Suggested-by: Peter Zijlstra <peterz@infradead.org>
> Signed-off-by: Rik van Riel <riel@redhat.com>
> ---
>  kernel/tsacct.c | 6 +-----
>  1 file changed, 1 insertion(+), 5 deletions(-)
> 
> diff --git a/kernel/tsacct.c b/kernel/tsacct.c
> index 8908f8b1d26e..b2663d699a72 100644
> --- a/kernel/tsacct.c
> +++ b/kernel/tsacct.c
> @@ -124,26 +124,22 @@ static void __acct_update_integrals(struct task_struct *tsk,
>  				    cputime_t utime, cputime_t stime)
>  {
>  	cputime_t time, dtime;
> -	unsigned long flags;
>  	u64 delta;
>  
>  	if (unlikely(!tsk->mm))
>  		return;
>  
> -	local_irq_save(flags);
>  	time = stime + utime;
>  	dtime = time - tsk->acct_timexpd;
>  	delta = cputime_to_nsecs(dtime);
>  
>  	if (delta < TICK_NSEC)
> -		goto out;
> +		return;
>  
>  	tsk->acct_timexpd = time;
>  	/* The final unit will be Mbyte-usecs, see xacct_add_tsk */
>  	tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) / 1024;
>  	tsk->acct_vm_mem1 += delta * tsk->mm->total_vm / 1024;
> -out:
> -	local_irq_restore(flags);
>  }

I think you need this as well, because do_exit() probably doesn't have
irqs disabled at that point:

diff --git a/kernel/tsacct.c b/kernel/tsacct.c
index 975cb49..12c6047 100644
--- a/kernel/tsacct.c
+++ b/kernel/tsacct.c
@@ -153,9 +153,12 @@ static void __acct_update_integrals(struct task_struct *tsk,
 void acct_update_integrals(struct task_struct *tsk)
 {
 	cputime_t utime, stime;
+	unsigned long flags;
 
 	task_cputime(tsk, &utime, &stime);
+	local_irq_save(flags);
 	__acct_update_integrals(tsk, utime, stime);
+	local_irq_restore(flags);
 }
 
 /**

[PATCH 4/4] sched,time: only call account_{user,sys,guest,idle}_time once a jiffy

[riel]

From: Rik van Riel <riel@redhat.com>

After removing __acct_update_integrals from the profile,
native_sched_clock remains as the top CPU user. This can be
reduced by only calling account_{user,sys,guest,idle}_time
once per jiffy for long running tasks on nohz_full CPUs.

This will reduce timing accuracy on nohz_full CPUs to jiffy
based sampling, just like on normal CPUs. It results in
totally removing native_sched_clock from the profile, and
significantly speeding up the syscall entry and exit path,
as well as irq entry and exit, and kvm guest entry & exit.

This code relies on another CPU advancing jiffies when the
system is busy. On a nohz_full system, this is done by a
housekeeping CPU.

A microbenchmark calling an invalid syscall number 10 million
times in a row speeds up an additional 30% over the numbers
with just the previous patches, for a total speedup of about
40% over 4.4 and 4.5-rc1.

Run times for the microbenchmark:

4.4				3.8 seconds
4.5-rc1				3.7 seconds
4.5-rc1 + first patch		3.3 seconds
4.5-rc1 + first 3 patches	3.1 seconds
4.5-rc1 + all patches		2.3 seconds

Signed-off-by: Rik van Riel <riel@redhat.com>
---
 include/linux/sched.h  |  1 +
 kernel/sched/cputime.c | 35 +++++++++++++++++++++++++++++------
 2 files changed, 30 insertions(+), 6 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index a10494a94cc3..019c3af98503 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1532,6 +1532,7 @@ struct task_struct {
 	struct prev_cputime prev_cputime;
 #ifdef CONFIG_VIRT_CPU_ACCOUNTING_GEN
 	seqcount_t vtime_seqcount;
+	unsigned long vtime_jiffies;
 	unsigned long long vtime_snap;
 	enum {
 		/* Task is sleeping or running in a CPU with VTIME inactive */
diff --git a/kernel/sched/cputime.c b/kernel/sched/cputime.c
index b2ab2ffb1adc..923c110319b1 100644
--- a/kernel/sched/cputime.c
+++ b/kernel/sched/cputime.c
@@ -668,6 +668,15 @@ void thread_group_cputime_adjusted(struct task_struct *p, cputime_t *ut, cputime
 #endif /* !CONFIG_VIRT_CPU_ACCOUNTING_NATIVE */
 
 #ifdef CONFIG_VIRT_CPU_ACCOUNTING_GEN
+static bool vtime_jiffies_changed(struct task_struct *tsk, unsigned long now)
+{
+	if (tsk->vtime_jiffies == jiffies)
+		return false;
+
+	tsk->vtime_jiffies = jiffies;
+	return true;
+}
+
 static unsigned long long vtime_delta(struct task_struct *tsk)
 {
 	unsigned long long clock;
@@ -699,6 +708,9 @@ static void __vtime_account_system(struct task_struct *tsk)
 
 void vtime_account_system(struct task_struct *tsk)
 {
+	if (!vtime_jiffies_changed(tsk, jiffies))
+		return;
+
 	write_seqcount_begin(&tsk->vtime_seqcount);
 	__vtime_account_system(tsk);
 	write_seqcount_end(&tsk->vtime_seqcount);
@@ -707,7 +719,8 @@ void vtime_account_system(struct task_struct *tsk)
 void vtime_gen_account_irq_exit(struct task_struct *tsk)
 {
 	write_seqcount_begin(&tsk->vtime_seqcount);
-	__vtime_account_system(tsk);
+	if (vtime_jiffies_changed(tsk, jiffies))
+		__vtime_account_system(tsk);
 	if (context_tracking_in_user())
 		tsk->vtime_snap_whence = VTIME_USER;
 	write_seqcount_end(&tsk->vtime_seqcount);
@@ -718,16 +731,19 @@ void vtime_account_user(struct task_struct *tsk)
 	cputime_t delta_cpu;
 
 	write_seqcount_begin(&tsk->vtime_seqcount);
-	delta_cpu = get_vtime_delta(tsk);
 	tsk->vtime_snap_whence = VTIME_SYS;
-	account_user_time(tsk, delta_cpu, cputime_to_scaled(delta_cpu));
+	if (vtime_jiffies_changed(tsk, jiffies)) {
+		delta_cpu = get_vtime_delta(tsk);
+		account_user_time(tsk, delta_cpu, cputime_to_scaled(delta_cpu));
+	}
 	write_seqcount_end(&tsk->vtime_seqcount);
 }
 
 void vtime_user_enter(struct task_struct *tsk)
 {
 	write_seqcount_begin(&tsk->vtime_seqcount);
-	__vtime_account_system(tsk);
+	if (vtime_jiffies_changed(tsk, jiffies))
+		__vtime_account_system(tsk);
 	tsk->vtime_snap_whence = VTIME_USER;
 	write_seqcount_end(&tsk->vtime_seqcount);
 }
@@ -742,7 +758,8 @@ void vtime_guest_enter(struct task_struct *tsk)
 	 * that can thus safely catch up with a tickless delta.
 	 */
 	write_seqcount_begin(&tsk->vtime_seqcount);
-	__vtime_account_system(tsk);
+	if (vtime_jiffies_changed(tsk, jiffies))
+		__vtime_account_system(tsk);
 	current->flags |= PF_VCPU;
 	write_seqcount_end(&tsk->vtime_seqcount);
 }
@@ -759,8 +776,12 @@ EXPORT_SYMBOL_GPL(vtime_guest_exit);
 
 void vtime_account_idle(struct task_struct *tsk)
 {
-	cputime_t delta_cpu = get_vtime_delta(tsk);
+	cputime_t delta_cpu;
+
+	if (!vtime_jiffies_changed(tsk, jiffies))
+		return;
 
+	delta_cpu = get_vtime_delta(tsk);
 	account_idle_time(delta_cpu);
 }
 
@@ -773,6 +794,7 @@ void arch_vtime_task_switch(struct task_struct *prev)
 	write_seqcount_begin(&current->vtime_seqcount);
 	current->vtime_snap_whence = VTIME_SYS;
 	current->vtime_snap = sched_clock_cpu(smp_processor_id());
+	current->vtime_jiffies = jiffies;
 	write_seqcount_end(&current->vtime_seqcount);
 }
 
@@ -784,6 +806,7 @@ void vtime_init_idle(struct task_struct *t, int cpu)
 	write_seqcount_begin(&t->vtime_seqcount);
 	t->vtime_snap_whence = VTIME_SYS;
 	t->vtime_snap = sched_clock_cpu(cpu);
+	t->vtime_jiffies = jiffies;
 	write_seqcount_end(&t->vtime_seqcount);
 	local_irq_restore(flags);
 }
-- 
2.5.0

[PATCH 0/4 v3] sched,time: reduce nohz_full syscall overhead 40%

[riel]

(v3: address comments raised by Frederic)

Running with nohz_full introduces a fair amount of overhead.
Specifically, various things that are usually done from the
timer interrupt are now done at syscall, irq, and guest
entry and exit times.

However, some of the code that is called every single time
has only ever worked at jiffy resolution. The code in
__acct_update_integrals was also doing some unnecessary
calculations.

Getting rid of the unnecessary calculations, without
changing any of the functionality in __acct_update_integrals
gets us about an 11% win.

Not calling the time statistics updating code more than
once per jiffy, like is done on housekeeping CPUs and on
all the CPUs of a non-nohz_full system, shaves off a
further 30%.

I tested this series with a microbenchmark calling
an invalid syscall number ten million times in a row,
on a nohz_full cpu.

    Run times for the microbenchmark:
    
4.4				3.8 seconds
4.5-rc1				3.7 seconds
4.5-rc1 + first patch		3.3 seconds
4.5-rc1 + first 3 patches	3.1 seconds
4.5-rc1 + all patches		2.3 seconds

[PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[riel]

From: Rik van Riel <riel@redhat.com>

When running a microbenchmark calling an invalid syscall number
in a loop, on a nohz_full CPU, we spend a full 9% of our CPU
time in __acct_update_integrals.

This function converts cputime_t to jiffies, to a timeval, only to
convert the timeval back to microseconds before discarding it.

This patch leaves __acct_update_integrals functionally equivalent,
but speeds things up by about 12%, with 10 million calls to an
invalid syscall number dropping from 3.7 to 3.25 seconds.

Signed-off-by: Rik van Riel <riel@redhat.com>
---
 kernel/tsacct.c | 24 ++++++++++++++----------
 1 file changed, 14 insertions(+), 10 deletions(-)

diff --git a/kernel/tsacct.c b/kernel/tsacct.c
index 975cb49e32bf..1b121a2f1c55 100644
--- a/kernel/tsacct.c
+++ b/kernel/tsacct.c
@@ -93,9 +93,9 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
 {
 	struct mm_struct *mm;
 
-	/* convert pages-usec to Mbyte-usec */
-	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
-	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
+	/* convert pages-nsec/1024 to Mbyte-usec, see __acct_update_integrals */
+	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / (1000 * KB);
+	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / (1000 * KB);
 	mm = get_task_mm(p);
 	if (mm) {
 		/* adjust to KB unit */
@@ -125,22 +125,26 @@ static void __acct_update_integrals(struct task_struct *tsk,
 {
 	if (likely(tsk->mm)) {
 		cputime_t time, dtime;
-		struct timeval value;
 		unsigned long flags;
 		u64 delta;
 
 		local_irq_save(flags);
 		time = stime + utime;
 		dtime = time - tsk->acct_timexpd;
-		jiffies_to_timeval(cputime_to_jiffies(dtime), &value);
-		delta = value.tv_sec;
-		delta = delta * USEC_PER_SEC + value.tv_usec;
+		/* Avoid division: cputime_t is often in nanoseconds already. */
+		delta = cputime_to_nsecs(dtime);
 
-		if (delta == 0)
+		if (delta < TICK_NSEC)
 			goto out;
+
 		tsk->acct_timexpd = time;
-		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm);
-		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm;
+		/*
+		 * Divide by 1024 to avoid overflow, and to avoid division.
+		 * The final unit reported to userspace is Mbyte-usecs,
+		 * the rest of the math is done in xacct_add_tsk.
+		 */
+		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) >> 10;
+		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm >> 10;
 	out:
 		local_irq_restore(flags);
 	}
-- 
2.5.0

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 2952 bytes --]

Hi Rik,

[auto build test ERROR on tip/sched/core]
[also build test ERROR on v4.5-rc2 next-20160129]
[if your patch is applied to the wrong git tree, please drop us a note to help improving the system]

url:    https://github.com/0day-ci/linux/commits/riel-redhat-com/sched-time-reduce-nohz_full-syscall-overhead-40/20160201-101609
config: sh-sh7757lcr_defconfig (attached as .config)
reproduce:
        wget https://git.kernel.org/cgit/linux/kernel/git/wfg/lkp-tests.git/plain/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=sh 

All errors (new ones prefixed by >>):

   kernel/built-in.o: In function `get_mm_hiwater_vm':
>> include/linux/mm.h:1377: undefined reference to `__udivdi3'

vim +1377 include/linux/mm.h

172703b0 Matt Fleming      2011-05-24  1361  	atomic_long_dec(&mm->rss_stat.count[member]);
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1362  }
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1363  
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1364  static inline unsigned long get_mm_rss(struct mm_struct *mm)
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1365  {
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1366  	return get_mm_counter(mm, MM_FILEPAGES) +
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1367  		get_mm_counter(mm, MM_ANONPAGES);
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1368  }
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1369  
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1370  static inline unsigned long get_mm_hiwater_rss(struct mm_struct *mm)
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1371  {
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1372  	return max(mm->hiwater_rss, get_mm_rss(mm));
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1373  }
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1374  
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1375  static inline unsigned long get_mm_hiwater_vm(struct mm_struct *mm)
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1376  {
d559db08 KAMEZAWA Hiroyuki 2010-03-05 @1377  	return max(mm->hiwater_vm, mm->total_vm);
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1378  }
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1379  
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1380  static inline void update_hiwater_rss(struct mm_struct *mm)
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1381  {
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1382  	unsigned long _rss = get_mm_rss(mm);
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1383  
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1384  	if ((mm)->hiwater_rss < _rss)
d559db08 KAMEZAWA Hiroyuki 2010-03-05  1385  		(mm)->hiwater_rss = _rss;

:::::: The code at line 1377 was first introduced by commit
:::::: d559db086ff5be9bcc259e5aa50bf3d881eaf1d1 mm: clean up mm_counter

:::::: TO: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
:::::: CC: Linus Torvalds <torvalds@linux-foundation.org>

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

[-- Attachment #2: .config.gz --]
[-- Type: application/octet-stream, Size: 11875 bytes --]

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[Thomas Gleixner]

On Sun, 31 Jan 2016, riel@redhat.com wrote:
> @@ -93,9 +93,9 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
>  {
>  	struct mm_struct *mm;
>  
> -	/* convert pages-usec to Mbyte-usec */
> -	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
> -	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
> +	/* convert pages-nsec/1024 to Mbyte-usec, see __acct_update_integrals */
> +	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / (1000 * KB);
> +	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / (1000 * KB);

You replace "/ (1024 * 1024)" by "/ (1000 * 1024). So that's introducing a non
power of 2 division instead of removing one and wont compile on systems which
do not have a 64/32 division in hardware.

Thanks,

	tglx

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[Peter Zijlstra]

On Mon, Feb 01, 2016 at 09:37:00AM +0100, Thomas Gleixner wrote:
> On Sun, 31 Jan 2016, riel@redhat.com wrote:
> > @@ -93,9 +93,9 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
> >  {
> >  	struct mm_struct *mm;
> >  
> > -	/* convert pages-usec to Mbyte-usec */
> > -	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
> > -	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
> > +	/* convert pages-nsec/1024 to Mbyte-usec, see __acct_update_integrals */
> > +	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / (1000 * KB);
> > +	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / (1000 * KB);
> 
> You replace "/ (1024 * 1024)" by "/ (1000 * 1024). So that's introducing a non
> power of 2 division instead of removing one and wont compile on systems which
> do not have a 64/32 division in hardware.

Yep, so that needs to be fixed to use do_div(). But the reason for this
is that this is the consumer side of these stats and therefore rarely
executed.

This patch effectively moves a div out of the fast path into the slow
path.

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[Thomas Gleixner]

On Mon, 1 Feb 2016, Peter Zijlstra wrote:

> On Mon, Feb 01, 2016 at 09:37:00AM +0100, Thomas Gleixner wrote:
> > On Sun, 31 Jan 2016, riel@redhat.com wrote:
> > > @@ -93,9 +93,9 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
> > >  {
> > >  	struct mm_struct *mm;
> > >  
> > > -	/* convert pages-usec to Mbyte-usec */
> > > -	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
> > > -	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
> > > +	/* convert pages-nsec/1024 to Mbyte-usec, see __acct_update_integrals */
> > > +	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / (1000 * KB);
> > > +	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / (1000 * KB);
> > 
> > You replace "/ (1024 * 1024)" by "/ (1000 * 1024). So that's introducing a non
> > power of 2 division instead of removing one and wont compile on systems which
> > do not have a 64/32 division in hardware.
> 
> Yep, so that needs to be fixed to use do_div(). But the reason for this
> is that this is the consumer side of these stats and therefore rarely
> executed.
> 
> This patch effectively moves a div out of the fast path into the slow
> path.

Yeah, noticed after hitting Send :)
 

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[Rik van Riel]

On 02/01/2016 04:22 AM, Peter Zijlstra wrote:
> On Mon, Feb 01, 2016 at 09:37:00AM +0100, Thomas Gleixner wrote:
>> On Sun, 31 Jan 2016, riel@redhat.com wrote:
>>> @@ -93,9 +93,9 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
>>>  {
>>>  	struct mm_struct *mm;
>>>  
>>> -	/* convert pages-usec to Mbyte-usec */
>>> -	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
>>> -	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
>>> +	/* convert pages-nsec/1024 to Mbyte-usec, see __acct_update_integrals */
>>> +	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / (1000 * KB);
>>> +	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / (1000 * KB);
>>
>> You replace "/ (1024 * 1024)" by "/ (1000 * 1024). So that's introducing a non
>> power of 2 division instead of removing one and wont compile on systems which
>> do not have a 64/32 division in hardware.
> 
> Yep, so that needs to be fixed to use do_div(). But the reason for this
> is that this is the consumer side of these stats and therefore rarely
> executed.

Before I send in a v4 with do_div in that location, are there
any other changes you would like me to make to the code?

-- 
All rights reversed

Re: [PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[Peter Zijlstra]

On Mon, Feb 01, 2016 at 08:44:44AM -0500, Rik van Riel wrote:
> Before I send in a v4 with do_div in that location, are there
> any other changes you would like me to make to the code?

The WARN_ON(!irqs_disabled()) run and adding irq_save/restore to
acct_update_integrals() would be good :-)

[PATCH 0/4 v4] sched,time: reduce nohz_full syscall overhead 40%

[riel]

(v4: address comments by Peter and Frederic)

Running with nohz_full introduces a fair amount of overhead.
Specifically, various things that are usually done from the
timer interrupt are now done at syscall, irq, and guest
entry and exit times.

However, some of the code that is called every single time
has only ever worked at jiffy resolution. The code in
__acct_update_integrals was also doing some unnecessary
calculations.

Getting rid of the unnecessary calculations, without
changing any of the functionality in __acct_update_integrals
gets us about an 11% win.

Not calling the time statistics updating code more than
once per jiffy, like is done on housekeeping CPUs and on
all the CPUs of a non-nohz_full system, shaves off a
further 30%.

I tested this series with a microbenchmark calling
an invalid syscall number ten million times in a row,
on a nohz_full cpu.

    Run times for the microbenchmark:
    
4.4				3.8 seconds
4.5-rc1				3.7 seconds
4.5-rc1 + first patch		3.3 seconds
4.5-rc1 + first 3 patches	3.1 seconds
4.5-rc1 + all patches		2.3 seconds

[PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[riel]

From: Rik van Riel <riel@redhat.com>

When running a microbenchmark calling an invalid syscall number
in a loop, on a nohz_full CPU, we spend a full 9% of our CPU
time in __acct_update_integrals.

This function converts cputime_t to jiffies, to a timeval, only to
convert the timeval back to microseconds before discarding it.

This patch leaves __acct_update_integrals functionally equivalent,
but speeds things up by about 12%, with 10 million calls to an
invalid syscall number dropping from 3.7 to 3.25 seconds.

Signed-off-by: Rik van Riel <riel@redhat.com>
---
 kernel/tsacct.c | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

diff --git a/kernel/tsacct.c b/kernel/tsacct.c
index 975cb49e32bf..460ee2bbfef3 100644
--- a/kernel/tsacct.c
+++ b/kernel/tsacct.c
@@ -93,9 +93,11 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
 {
 	struct mm_struct *mm;
 
-	/* convert pages-usec to Mbyte-usec */
-	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
-	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
+	/* convert pages-nsec/1024 to Mbyte-usec, see __acct_update_integrals */
+	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE;
+	do_div(stats->coremem, 1000 * KB);
+	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE;
+	do_div(stats->virtmem, 1000 * KB);
 	mm = get_task_mm(p);
 	if (mm) {
 		/* adjust to KB unit */
@@ -125,22 +127,26 @@ static void __acct_update_integrals(struct task_struct *tsk,
 {
 	if (likely(tsk->mm)) {
 		cputime_t time, dtime;
-		struct timeval value;
 		unsigned long flags;
 		u64 delta;
 
 		local_irq_save(flags);
 		time = stime + utime;
 		dtime = time - tsk->acct_timexpd;
-		jiffies_to_timeval(cputime_to_jiffies(dtime), &value);
-		delta = value.tv_sec;
-		delta = delta * USEC_PER_SEC + value.tv_usec;
+		/* Avoid division: cputime_t is often in nanoseconds already. */
+		delta = cputime_to_nsecs(dtime);
 
-		if (delta == 0)
+		if (delta < TICK_NSEC)
 			goto out;
+
 		tsk->acct_timexpd = time;
-		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm);
-		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm;
+		/*
+		 * Divide by 1024 to avoid overflow, and to avoid division.
+		 * The final unit reported to userspace is Mbyte-usecs,
+		 * the rest of the math is done in xacct_add_tsk.
+		 */
+		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) >> 10;
+		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm >> 10;
 	out:
 		local_irq_restore(flags);
 	}
-- 
2.5.0

[PATCH 0/4 v5] sched,time: reduce nohz_full syscall overhead 40%

[riel]

(v5: address comments by Frederic & Peter, fix bug found by Eric)

Running with nohz_full introduces a fair amount of overhead.
Specifically, various things that are usually done from the
timer interrupt are now done at syscall, irq, and guest
entry and exit times.

However, some of the code that is called every single time
has only ever worked at jiffy resolution. The code in
__acct_update_integrals was also doing some unnecessary
calculations.

Getting rid of the unnecessary calculations, without
changing any of the functionality in __acct_update_integrals
gets us about an 11% win.

Not calling the time statistics updating code more than
once per jiffy, like is done on housekeeping CPUs and on
all the CPUs of a non-nohz_full system, shaves off a
further 30%.

I tested this series with a microbenchmark calling
an invalid syscall number ten million times in a row,
on a nohz_full cpu.

    Run times for the microbenchmark:
    
4.4				3.8 seconds
4.5-rc1				3.7 seconds
4.5-rc1 + first patch		3.3 seconds
4.5-rc1 + first 3 patches	3.1 seconds
4.5-rc1 + all patches		2.3 seconds

   Same test on a non-NOHZ_FULL, non-housekeeping CPU:
all kernels			1.86 seconds

[PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[riel]

From: Rik van Riel <riel@redhat.com>

When running a microbenchmark calling an invalid syscall number
in a loop, on a nohz_full CPU, we spend a full 9% of our CPU
time in __acct_update_integrals.

This function converts cputime_t to jiffies, to a timeval, only to
convert the timeval back to microseconds before discarding it.

This patch leaves __acct_update_integrals functionally equivalent,
but speeds things up by about 12%, with 10 million calls to an
invalid syscall number dropping from 3.7 to 3.25 seconds.

Signed-off-by: Rik van Riel <riel@redhat.com>
---
 kernel/tsacct.c | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

diff --git a/kernel/tsacct.c b/kernel/tsacct.c
index 975cb49e32bf..460ee2bbfef3 100644
--- a/kernel/tsacct.c
+++ b/kernel/tsacct.c
@@ -93,9 +93,11 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
 {
 	struct mm_struct *mm;
 
-	/* convert pages-usec to Mbyte-usec */
-	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
-	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
+	/* convert pages-nsec/1024 to Mbyte-usec, see __acct_update_integrals */
+	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE;
+	do_div(stats->coremem, 1000 * KB);
+	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE;
+	do_div(stats->virtmem, 1000 * KB);
 	mm = get_task_mm(p);
 	if (mm) {
 		/* adjust to KB unit */
@@ -125,22 +127,26 @@ static void __acct_update_integrals(struct task_struct *tsk,
 {
 	if (likely(tsk->mm)) {
 		cputime_t time, dtime;
-		struct timeval value;
 		unsigned long flags;
 		u64 delta;
 
 		local_irq_save(flags);
 		time = stime + utime;
 		dtime = time - tsk->acct_timexpd;
-		jiffies_to_timeval(cputime_to_jiffies(dtime), &value);
-		delta = value.tv_sec;
-		delta = delta * USEC_PER_SEC + value.tv_usec;
+		/* Avoid division: cputime_t is often in nanoseconds already. */
+		delta = cputime_to_nsecs(dtime);
 
-		if (delta == 0)
+		if (delta < TICK_NSEC)
 			goto out;
+
 		tsk->acct_timexpd = time;
-		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm);
-		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm;
+		/*
+		 * Divide by 1024 to avoid overflow, and to avoid division.
+		 * The final unit reported to userspace is Mbyte-usecs,
+		 * the rest of the math is done in xacct_add_tsk.
+		 */
+		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) >> 10;
+		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm >> 10;
 	out:
 		local_irq_restore(flags);
 	}
-- 
2.5.0

[PATCH 0/4 v6] sched,time: reduce nohz_full syscall overhead 40%

[riel]

(v6: make VIRT_CPU_ACCOUNTING_GEN jiffy granularity)

Running with nohz_full introduces a fair amount of overhead.
Specifically, various things that are usually done from the
timer interrupt are now done at syscall, irq, and guest
entry and exit times.

However, some of the code that is called every single time
has only ever worked at jiffy resolution. The code in
__acct_update_integrals was also doing some unnecessary
calculations.

Getting rid of the unnecessary calculations, without
changing any of the functionality in __acct_update_integrals
gets us about an 11% win.

Not calling the time statistics updating code more than
once per jiffy, like is done on housekeeping CPUs and on
all the CPUs of a non-nohz_full system, shaves off a
further 30%.

I tested this series with a microbenchmark calling
an invalid syscall number ten million times in a row,
on a nohz_full cpu.

    Run times for the microbenchmark:
    
4.4                             3.8 seconds
4.5-rc1                         3.7 seconds
4.5-rc1 + first patch           3.3 seconds
4.5-rc1 + first 3 patches       3.1 seconds
4.5-rc1 + all patches           2.3 seconds

   Same test on a non-NOHZ_FULL, non-housekeeping CPU:
all kernels                     1.86 seconds

[PATCH 1/4] sched,time: remove non-power-of-two divides from __acct_update_integrals

[riel]

From: Rik van Riel <riel@redhat.com>

When running a microbenchmark calling an invalid syscall number
in a loop, on a nohz_full CPU, we spend a full 9% of our CPU
time in __acct_update_integrals.

This function converts cputime_t to jiffies, to a timeval, only to
convert the timeval back to microseconds before discarding it.

This patch leaves __acct_update_integrals functionally equivalent,
but speeds things up by about 12%, with 10 million calls to an
invalid syscall number dropping from 3.7 to 3.25 seconds.

Signed-off-by: Rik van Riel <riel@redhat.com>
---
 kernel/tsacct.c | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

diff --git a/kernel/tsacct.c b/kernel/tsacct.c
index 975cb49e32bf..460ee2bbfef3 100644
--- a/kernel/tsacct.c
+++ b/kernel/tsacct.c
@@ -93,9 +93,11 @@ void xacct_add_tsk(struct taskstats *stats, struct task_struct *p)
 {
 	struct mm_struct *mm;
 
-	/* convert pages-usec to Mbyte-usec */
-	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE / MB;
-	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE / MB;
+	/* convert pages-nsec/1024 to Mbyte-usec, see __acct_update_integrals */
+	stats->coremem = p->acct_rss_mem1 * PAGE_SIZE;
+	do_div(stats->coremem, 1000 * KB);
+	stats->virtmem = p->acct_vm_mem1 * PAGE_SIZE;
+	do_div(stats->virtmem, 1000 * KB);
 	mm = get_task_mm(p);
 	if (mm) {
 		/* adjust to KB unit */
@@ -125,22 +127,26 @@ static void __acct_update_integrals(struct task_struct *tsk,
 {
 	if (likely(tsk->mm)) {
 		cputime_t time, dtime;
-		struct timeval value;
 		unsigned long flags;
 		u64 delta;
 
 		local_irq_save(flags);
 		time = stime + utime;
 		dtime = time - tsk->acct_timexpd;
-		jiffies_to_timeval(cputime_to_jiffies(dtime), &value);
-		delta = value.tv_sec;
-		delta = delta * USEC_PER_SEC + value.tv_usec;
+		/* Avoid division: cputime_t is often in nanoseconds already. */
+		delta = cputime_to_nsecs(dtime);
 
-		if (delta == 0)
+		if (delta < TICK_NSEC)
 			goto out;
+
 		tsk->acct_timexpd = time;
-		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm);
-		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm;
+		/*
+		 * Divide by 1024 to avoid overflow, and to avoid division.
+		 * The final unit reported to userspace is Mbyte-usecs,
+		 * the rest of the math is done in xacct_add_tsk.
+		 */
+		tsk->acct_rss_mem1 += delta * get_mm_rss(tsk->mm) >> 10;
+		tsk->acct_vm_mem1 += delta * tsk->mm->total_vm >> 10;
 	out:
 		local_irq_restore(flags);
 	}
-- 
2.5.0