sched, timer: Improve scalability of itimers

ACCESS_ONCE doesn't work reliably on non-scalar types. This patch removes the rest of the existing usages of ACCESS_ONCE in the scheduler, and use the new READ_ONCE and WRITE_ONCE APIs.

Signed-off-by Jason Low <[email protected]>

ACCESS_ONCE doesn't work reliably on non-scalar types. This patch removes the rest of the existing usages of ACCESS_ONCE in the scheduler, and use the new READ_ONCE and WRITE_ONCE APIs.

Signed-off-by Jason Low<[email protected]>

---
  include/linux/sched.h          |    4 ++--
  kernel/fork.c                  |    2 +-
  kernel/sched/auto_group.c      |    2 +-
  kernel/sched/auto_group.h      |    2 +-
  kernel/sched/core.c            |    4 ++--
  kernel/sched/cputime.c         |    2 +-
  kernel/sched/deadline.c        |    2 +-
  kernel/sched/fair.c            |   14 +++++++-------
  kernel/sched/proc.c            |    4 ++--
  kernel/sched/rt.c              |    2 +-
  kernel/sched/sched.h           |    2 +-
  kernel/sched/wait.c            |    4 ++--
  kernel/time/posix-cpu-timers.c |    8 ++++----
  13 files changed, 26 insertions(+), 26 deletions(-)

...
goto no_join;

kernel/sched/fair.c void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags) · line 2113

Quoted 11 lines

goto no_join;

kernel/sched/fair.c +1 -1

@@ -2107,7 +2107,7 @@ void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
 
  static void reset_ptenuma_scan(struct task_struct *p)
  {
-	ACCESS_ONCE(p->mm->numa_scan_seq)++;
+	WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
  	p->mm->numa_scan_offset = 0;
  }
 

Generally, I am for replacing ACCESS_ONCE() with the more descriptive READ_ONCE() and WRITE_ONCE() except the above case where it makes the code harder to read without any real advantage.

Other than that,

Acked-by Waiman Long <[email protected]>

Quoted 16 lines · On Wed, 29 Apr 2015 13:05:55 -0400 Waiman Long <[email protected]> wrote:

kernel/sched/fair.c void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags) · line 2113

Quoted 11 lines

goto no_join;

kernel/sched/fair.c +1 -1

@@ -2107,7 +2107,7 @@ void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
 
  static void reset_ptenuma_scan(struct task_struct *p)
  {
-	ACCESS_ONCE(p->mm->numa_scan_seq)++;
+	WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
  	p->mm->numa_scan_offset = 0;
  }
 

Generally, I am for replacing ACCESS_ONCE() with the more descriptive READ_ONCE() and WRITE_ONCE() except the above case where it makes the code harder to read without any real advantage.

Quoted 4 lines

Other than that,

Acked-by Waiman Long <[email protected]>

I agree, but I believe this code needs to be updated anyway. Making it uglier may encourage that to happen.

The p->mm->numa_scan_seq is accessed using READ_ONCE/WRITE_ONCE and modified without exclusive access. It is not clear why it is accessed this way. This patch provides some documentation on that.

Signed-off-by Jason Low <[email protected]>

The p->mm->numa_scan_seq is accessed using READ_ONCE/WRITE_ONCE and modified without exclusive access. It is not clear why it is accessed this way. This patch provides some documentation on that.

Signed-off-by Jason Low<[email protected]>

---
  kernel/sched/fair.c |   12 ++++++++++++
  1 files changed, 12 insertions(+), 0 deletions(-)

kernel/sched/fair.c +5 -0

index 5a44371..794f7d7 100644
@@ -1794,6 +1794,11 @@ static void task_numa_placement(struct task_struct *p)
  	u64 runtime, period;
  	spinlock_t *group_lock = NULL;
 
+	/*
+	 * The p->mm->numa_scan_seq gets updated without
+	 * exclusive access. Use READ_ONCE() here to ensure
+	 * that the field is read in a single access.
+	 */
  	seq = READ_ONCE(p->mm->numa_scan_seq);
  	if (p->numa_scan_seq == seq)
  		return;

@@ -2107,6 +2112,13 @@ void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
 
  static void reset_ptenuma_scan(struct task_struct *p)
  {

Quoted 27 lines · Jason Low

The p->mm->numa_scan_seq is accessed using READ_ONCE/WRITE_ONCE and modified without exclusive access. It is not clear why it is accessed this way. This patch provides some documentation on that.

Signed-off-by Jason Low<[email protected]>

---
  kernel/sched/fair.c |   12 ++++++++++++
  1 files changed, 12 insertions(+), 0 deletions(-)

kernel/sched/fair.c +5 -0

index 5a44371..794f7d7 100644
@@ -1794,6 +1794,11 @@ static void task_numa_placement(struct task_struct *p)
  	u64 runtime, period;
  	spinlock_t *group_lock = NULL;
 
+	/*
+	 * The p->mm->numa_scan_seq gets updated without
+	 * exclusive access. Use READ_ONCE() here to ensure
+	 * that the field is read in a single access.
+	 */
  	seq = READ_ONCE(p->mm->numa_scan_seq);
  	if (p->numa_scan_seq == seq)
  		return;

@@ -2107,6 +2112,13 @@ void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
 

kernel/sched/fair.c void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags) · line 2124

Quoted 12 lines

kernel/sched/fair.c +7 -0

  static void reset_ptenuma_scan(struct task_struct *p)
  {
+	/*
+	 * We only did a read acquisition of the mmap sem, so
+	 * p->mm->numa_scan_seq is written to without exclusive access.
+	 * That's not much of an issue though, since this is just used
+	 * for statistical sampling. Use WRITE_ONCE and READ_ONCE, which
+	 * are not expensive, to avoid load/store tearing.
+	 */
  	WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
  	p->mm->numa_scan_offset = 0;
  }

READ_ONCE followed by a WRITE_ONCE won't stop load/store tearing from happening unless you use an atomic instruction to do the increment. So I think your comment may be a bit misleading.

Quoted 28 lines · Waiman Long

Quoted 27 lines · Jason Low

The p->mm->numa_scan_seq is accessed using READ_ONCE/WRITE_ONCE and modified without exclusive access. It is not clear why it is accessed this way. This patch provides some documentation on that.

Signed-off-by Jason Low<[email protected]>

---
   kernel/sched/fair.c |   12 ++++++++++++
   1 files changed, 12 insertions(+), 0 deletions(-)

kernel/sched/fair.c +5 -0

index 5a44371..794f7d7 100644
@@ -1794,6 +1794,11 @@ static void task_numa_placement(struct task_struct *p)
   	u64 runtime, period;
   	spinlock_t *group_lock = NULL;
 
+	/*
+	 * The p->mm->numa_scan_seq gets updated without
+	 * exclusive access. Use READ_ONCE() here to ensure
+	 * that the field is read in a single access.
+	 */
   	seq = READ_ONCE(p->mm->numa_scan_seq);
   	if (p->numa_scan_seq == seq)
   		return;

@@ -2107,6 +2112,13 @@ void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
 

Quoted 15 lines

kernel/sched/fair.c void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags) · line 2124

Quoted 12 lines

kernel/sched/fair.c +7 -0

   static void reset_ptenuma_scan(struct task_struct *p)
   {
+	/*
+	 * We only did a read acquisition of the mmap sem, so
+	 * p->mm->numa_scan_seq is written to without exclusive access.
+	 * That's not much of an issue though, since this is just used
+	 * for statistical sampling. Use WRITE_ONCE and READ_ONCE, which
+	 * are not expensive, to avoid load/store tearing.
+	 */
   	WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
   	p->mm->numa_scan_offset = 0;
   }

READ_ONCE followed by a WRITE_ONCE won't stop load/store tearing from happening unless you use an atomic instruction to do the increment. So I think your comment may be a bit misleading.

Right, the READ and WRITE operations will still be done separately and won't be atomic. Here, we're saying that this prevents load/store tearing on each of those individual write/read operations. Please let me know if you prefer this to be worded differently.

Quoted 44 lines · Jason Low

Quoted 28 lines · Waiman Long

Quoted 27 lines · Jason Low

The p->mm->numa_scan_seq is accessed using READ_ONCE/WRITE_ONCE and modified without exclusive access. It is not clear why it is accessed this way. This patch provides some documentation on that.

Signed-off-by Jason Low<[email protected]>

---
   kernel/sched/fair.c |   12 ++++++++++++
   1 files changed, 12 insertions(+), 0 deletions(-)

kernel/sched/fair.c +5 -0

index 5a44371..794f7d7 100644
@@ -1794,6 +1794,11 @@ static void task_numa_placement(struct task_struct *p)
   	u64 runtime, period;
   	spinlock_t *group_lock = NULL;
 
+	/*
+	 * The p->mm->numa_scan_seq gets updated without
+	 * exclusive access. Use READ_ONCE() here to ensure
+	 * that the field is read in a single access.
+	 */
   	seq = READ_ONCE(p->mm->numa_scan_seq);
   	if (p->numa_scan_seq == seq)
   		return;

@@ -2107,6 +2112,13 @@ void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
 

Quoted 15 lines

kernel/sched/fair.c void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags) · line 2124

Quoted 12 lines

kernel/sched/fair.c +7 -0

   static void reset_ptenuma_scan(struct task_struct *p)
   {
+	/*
+	 * We only did a read acquisition of the mmap sem, so
+	 * p->mm->numa_scan_seq is written to without exclusive access.
+	 * That's not much of an issue though, since this is just used
+	 * for statistical sampling. Use WRITE_ONCE and READ_ONCE, which
+	 * are not expensive, to avoid load/store tearing.
+	 */
   	WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
   	p->mm->numa_scan_offset = 0;
   }

READ_ONCE followed by a WRITE_ONCE won't stop load/store tearing from happening unless you use an atomic instruction to do the increment. So I think your comment may be a bit misleading.

Quoted 4 lines

Right, the READ and WRITE operations will still be done separately and won't be atomic. Here, we're saying that this prevents load/store tearing on each of those individual write/read operations. Please let me know if you prefer this to be worded differently.

I do have a question of what kind of tearing you are talking about. Do you mean the tearing due to mm being changed in the middle of the access? The reason why I don't like this kind of construct is that I am not sure if
the address translation p->mm->numa_scan_seq is being done once or twice. I looked at the compiled code and the translation is done only once.

Anyway, the purpose of READ_ONCE and WRITE_ONCE is not for eliminating data tearing. They are to make sure that the compiler won't compile away data access and they are done in the order they appear in the program. I don't think it is a good idea to associate tearing elimination with those macros. So I would suggest removing the last sentence in your comment.

Quoted 56 lines · Waiman Long

Quoted 44 lines · Jason Low

Quoted 28 lines · Waiman Long

Quoted 27 lines · Jason Low

The p->mm->numa_scan_seq is accessed using READ_ONCE/WRITE_ONCE and modified without exclusive access. It is not clear why it is accessed this way. This patch provides some documentation on that.

Signed-off-by Jason Low<[email protected]>

---
    kernel/sched/fair.c |   12 ++++++++++++
    1 files changed, 12 insertions(+), 0 deletions(-)

kernel/sched/fair.c +5 -0

index 5a44371..794f7d7 100644
@@ -1794,6 +1794,11 @@ static void task_numa_placement(struct task_struct *p)
    	u64 runtime, period;
    	spinlock_t *group_lock = NULL;
 
+	/*
+	 * The p->mm->numa_scan_seq gets updated without
+	 * exclusive access. Use READ_ONCE() here to ensure
+	 * that the field is read in a single access.
+	 */
    	seq = READ_ONCE(p->mm->numa_scan_seq);
    	if (p->numa_scan_seq == seq)
    		return;

@@ -2107,6 +2112,13 @@ void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
 

Quoted 15 lines

kernel/sched/fair.c void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags) · line 2124

Quoted 12 lines

kernel/sched/fair.c +7 -0

    static void reset_ptenuma_scan(struct task_struct *p)
    {
+	/*
+	 * We only did a read acquisition of the mmap sem, so
+	 * p->mm->numa_scan_seq is written to without exclusive access.
+	 * That's not much of an issue though, since this is just used
+	 * for statistical sampling. Use WRITE_ONCE and READ_ONCE, which
+	 * are not expensive, to avoid load/store tearing.
+	 */
    	WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
    	p->mm->numa_scan_offset = 0;
    }

READ_ONCE followed by a WRITE_ONCE won't stop load/store tearing from happening unless you use an atomic instruction to do the increment. So I think your comment may be a bit misleading.

Quoted 4 lines

Right, the READ and WRITE operations will still be done separately and won't be atomic. Here, we're saying that this prevents load/store tearing on each of those individual write/read operations. Please let me know if you prefer this to be worded differently.

I do have a question of what kind of tearing you are talking about. Do you mean the tearing due to mm being changed in the middle of the access? The reason why I don't like this kind of construct is that I am not sure if
the address translation p->mm->numa_scan_seq is being done once or twice. I looked at the compiled code and the translation is done only once.

Quoted 5 lines

Anyway, the purpose of READ_ONCE and WRITE_ONCE is not for eliminating data tearing. They are to make sure that the compiler won't compile away data access and they are done in the order they appear in the program. I don't think it is a good idea to associate tearing elimination with those macros. So I would suggest removing the last sentence in your comment.

I agree. Related, Linus also had some thoughts about the _very specific_ purposes of these macros:
http://www.spinics.net/lists/linux-next/msg32494.html

I also wonder why this patch is included in a set called "sched, timer: Improve scalability of itimers" ;)

I do have a question of what kind of tearing you are talking about. Do you mean the tearing due to mm being changed in the middle of the access? The reason why I don't like this kind of construct is that I am not sure if
the address translation p->mm->numa_scan_seq is being done once or twice. I looked at the compiled code and the translation is done only once.

Anyway, the purpose of READ_ONCE and WRITE_ONCE is not for eliminating data tearing. They are to make sure that the compiler won't compile away data access and they are done in the order they appear in the program. I don't think it is a good idea to associate tearing elimination with those macros. So I would suggest removing the last sentence in your comment.

Quoted 7 lines · Waiman Long

I do have a question of what kind of tearing you are talking about. Do you mean the tearing due to mm being changed in the middle of the access? The reason why I don't like this kind of construct is that I am not sure if
the address translation p->mm->numa_scan_seq is being done once or twice. I looked at the compiled code and the translation is done only once.

Quoted 5 lines

Anyway, the purpose of READ_ONCE and WRITE_ONCE is not for eliminating data tearing. They are to make sure that the compiler won't compile away data access and they are done in the order they appear in the program. I don't think it is a good idea to associate tearing elimination with those macros. So I would suggest removing the last sentence in your comment.

Yes, I can remove the last sentence in the comment since the main goal was to document that we're access this field without exclusive access.

Quoted 7 lines · Waiman Long

I do have a question of what kind of tearing you are talking about. Do you mean the tearing due to mm being changed in the middle of the access? The reason why I don't like this kind of construct is that I am not sure if
the address translation p->mm->numa_scan_seq is being done once or twice. I looked at the compiled code and the translation is done only once.

Quoted 5 lines

Anyway, the purpose of READ_ONCE and WRITE_ONCE is not for eliminating data tearing. They are to make sure that the compiler won't compile away data access and they are done in the order they appear in the program. I don't think it is a good idea to associate tearing elimination with those macros. So I would suggest removing the last sentence in your comment.

Yes, I can remove the last sentence in the comment since the main goal was to document that we're access this field without exclusive access.

In terms of data tearing, an example would be the write operation gets split into multiple stores (though this is architecture dependent). The idea was that since we're modifying a seq variable without the write lock, we want to remove any forms of optimizations as mentioned above or unpredictable behavior, since READ_ONCE/WRITE_ONCE adds no overhead.

Quoted 18 lines · Jason Low

Quoted 7 lines · Waiman Long

I do have a question of what kind of tearing you are talking about. Do you mean the tearing due to mm being changed in the middle of the access? The reason why I don't like this kind of construct is that I am not sure if
the address translation p->mm->numa_scan_seq is being done once or twice. I looked at the compiled code and the translation is done only once.

Quoted 5 lines

Anyway, the purpose of READ_ONCE and WRITE_ONCE is not for eliminating data tearing. They are to make sure that the compiler won't compile away data access and they are done in the order they appear in the program. I don't think it is a good idea to associate tearing elimination with those macros. So I would suggest removing the last sentence in your comment.

Yes, I can remove the last sentence in the comment since the main goal was to document that we're access this field without exclusive access.

Quoted 5 lines

In terms of data tearing, an example would be the write operation gets split into multiple stores (though this is architecture dependent). The idea was that since we're modifying a seq variable without the write lock, we want to remove any forms of optimizations as mentioned above or unpredictable behavior, since READ_ONCE/WRITE_ONCE adds no overhead.

Just to be clear... READ_ONCE() and WRITE_ONCE() do not avoid data tearing in cases where the thing read or written is too big for a machine word.

If the thing read/written does fit into a machine word and if the location read/written is properly aligned, I would be quite surprised if either READ_ONCE() or WRITE_ONCE() resulted in any sort of tearing.

While running a database workload, we found a scalability issue with itimers.

Much of the problem was caused by the thread_group_cputimer spinlock. Each time we account for group system/user time, we need to obtain a thread_group_cputimer's spinlock to update the timers. On larger systems (such as a 16 socket machine), this caused more than 30% of total time spent trying to obtain this kernel lock to update these group timer stats.

This patch converts the timers to 64 bit atomic variables and use atomic add to update them without a lock. With this patch, the percent of total time spent updating thread group cputimer timers was reduced from 30% down to less than 1%.

Note: On 32 bit systems using the generic 64 bit atomics, this causes sample_group_cputimer() to take locks 3 times instead of just 1 time. However, we tested this patch on a 32 bit system ARM system using the generic atomics and did not find the overhead to be much of an issue. An explanation for why this isn't an issue is that 32 bit systems usually have small numbers of CPUs, and cacheline contention from extra spinlocks called periodically is not really apparent on smaller systems.

Signed-off-by Jason Low <[email protected]>

Quoted 13 lines · Jason Low

While running a database workload, we found a scalability issue with itimers.

Much of the problem was caused by the thread_group_cputimer spinlock. Each time we account for group system/user time, we need to obtain a thread_group_cputimer's spinlock to update the timers. On larger systems (such as a 16 socket machine), this caused more than 30% of total time spent trying to obtain this kernel lock to update these group timer stats.

This patch converts the timers to 64 bit atomic variables and use atomic add to update them without a lock. With this patch, the percent of total time spent updating thread group cputimer timers was reduced from 30% down to less than 1%.

Quoted 7 lines

Note: On 32 bit systems using the generic 64 bit atomics, this causes sample_group_cputimer() to take locks 3 times instead of just 1 time. However, we tested this patch on a 32 bit system ARM system using the generic atomics and did not find the overhead to be much of an issue. An explanation for why this isn't an issue is that 32 bit systems usually have small numbers of CPUs, and cacheline contention from extra spinlocks called periodically is not really apparent on smaller systems.

I don't see 32 bit systems ever getting so many CPUs that this becomes an issue :)

Quoted 1 line

Signed-off-by Jason Low <[email protected]>

Acked-by Rik van Riel <[email protected]>

While running a database workload, we found a scalability issue with itimers.

Much of the problem was caused by the thread_group_cputimer spinlock. Each time we account for group system/user time, we need to obtain a thread_group_cputimer's spinlock to update the timers. On larger systems (such as a 16 socket machine), this caused more than 30% of total time spent trying to obtain this kernel lock to update these group timer stats.

This patch converts the timers to 64 bit atomic variables and use atomic add to update them without a lock. With this patch, the percent of total time spent updating thread group cputimer timers was reduced from 30% down to less than 1%.

Note: On 32 bit systems using the generic 64 bit atomics, this causes sample_group_cputimer() to take locks 3 times instead of just 1 time. However, we tested this patch on a 32 bit system ARM system using the generic atomics and did not find the overhead to be much of an issue. An explanation for why this isn't an issue is that 32 bit systems usually have small numbers of CPUs, and cacheline contention from extra spinlocks called periodically is not really apparent on smaller systems.

Signed-off-by Jason Low<[email protected]>

---
  include/linux/init_task.h      |    7 ++--
  include/linux/sched.h          |   10 ++----
  kernel/fork.c                  |    3 --
  kernel/sched/stats.h           |   15 +++-----
  kernel/time/posix-cpu-timers.c |   79 +++++++++++++++++++++++++---------------
  5 files changed, 62 insertions(+), 52 deletions(-)

include/linux/init_task.h +4 -3

index 696d223..7b9d8b5 100644
@@ -50,9 +50,10 @@ extern struct fs_struct init_fs;
  	.cpu_timers	= INIT_CPU_TIMERS(sig.cpu_timers),		\
  	.rlim		= INIT_RLIMITS,					\
  	.cputimer	= { 						\
-		.cputime = INIT_CPUTIME,				\
-		.running = 0,						\
-		.lock = __RAW_SPIN_LOCK_UNLOCKED(sig.cputimer.lock),	\
+		.utime 		  = ATOMIC64_INIT(0),			\
+		.stime		  = ATOMIC64_INIT(0),			\
+		.sum_exec_runtime = ATOMIC64_INIT(0),			\
+		.running 	  = 0					\
  	},								\
  	.cred_guard_mutex =						\
  		 __MUTEX_INITIALIZER(sig.cred_guard_mutex),		\

include/linux/sched.h +3 -7

index 604eb7c..c736a47 100644
@@ -601,9 +601,10 @@ struct task_cputime {
   * used for thread group CPU timer calculations.
   */
  struct thread_group_cputimer {
-	struct task_cputime cputime;
+	atomic64_t utime;
+	atomic64_t stime;
+	atomic64_t sum_exec_runtime;
  	int running;
-	raw_spinlock_t lock;
  };
 
  #include<linux/rwsem.h>

@@ -2970,11 +2971,6 @@ static __always_inline bool need_resched(void)
  void thread_group_cputime(struct task_struct *tsk, struct task_cputime *times);
  void thread_group_cputimer(struct task_struct *tsk, struct task_cputime *times);
 
-static inline void thread_group_cputime_init(struct signal_struct *sig)
-{
-	raw_spin_lock_init(&sig->cputimer.lock);
-}
-
  /*
   * Reevaluate whether the task has signals pending delivery.
   * Wake the task if so.

kernel/fork.c +0 -3

index 47c37a4..2e67086 100644
@@ -1091,9 +1091,6 @@ static void posix_cpu_timers_init_group(struct signal_struct *sig)
  {
  	unsigned long cpu_limit;
 
-	/* Thread group counters. */
-	thread_group_cputime_init(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);

kernel/sched/stats.h +5 -10

index 4ab7043..c6d1c7d 100644
@@ -174,7 +174,8 @@ static inline bool cputimer_running(struct task_struct *tsk)
  {
  	struct thread_group_cputimer *cputimer =&tsk->signal->cputimer;
 
-	if (!cputimer->running)
+	/* Check if cputimer isn't running. This is accessed without locking. */
+	if (!READ_ONCE(cputimer->running))
  		return false;
 
  	/*

@@ -215,9 +216,7 @@ static inline void account_group_user_time(struct task_struct *tsk,
  	if (!cputimer_running(tsk))
  		return;
 
-	raw_spin_lock(&cputimer->lock);
-	cputimer->cputime.utime += cputime;
-	raw_spin_unlock(&cputimer->lock);
+	atomic64_add(cputime,&cputimer->utime);
  }
 
  /**

@@ -238,9 +237,7 @@ static inline void account_group_system_time(struct task_struct *tsk,
  	if (!cputimer_running(tsk))
  		return;
 
-	raw_spin_lock(&cputimer->lock);
-	cputimer->cputime.stime += cputime;
-	raw_spin_unlock(&cputimer->lock);
+	atomic64_add(cputime,&cputimer->stime);
  }
 
  /**

@@ -261,7 +258,5 @@ static inline void account_group_exec_runtime(struct task_struct *tsk,
  	if (!cputimer_running(tsk))
  		return;
 
-	raw_spin_lock(&cputimer->lock);
-	cputimer->cputime.sum_exec_runtime += ns;
-	raw_spin_unlock(&cputimer->lock);
+	atomic64_add(ns,&cputimer->sum_exec_runtime);
  }

kernel/time/posix-cpu-timers.c +32 -18

index e072d98..d857306 100644
@@ -196,39 +196,62 @@ static int cpu_clock_sample(const clockid_t which_clock, struct task_struct *p,
  	return 0;
  }
 
-static void update_gt_cputime(struct task_cputime *a, struct task_cputime *b)
+/*
+ * Set cputime to sum_cputime if sum_cputime>  cputime. Use cmpxchg
+ * to avoid race conditions with concurrent updates to cputime.
+ */
+static inline void __update_gt_cputime(atomic64_t *cputime, u64 sum_cputime)
  {
-	if (b->utime>  a->utime)
-		a->utime = b->utime;
+	u64 curr_cputime;
+retry:
+	curr_cputime = atomic64_read(cputime);
+	if (sum_cputime>  curr_cputime) {
+		if (atomic64_cmpxchg(cputime, curr_cputime, sum_cputime) != curr_cputime)
+			goto retry;
+	}
+}
 
-	if (b->stime>  a->stime)
-		a->stime = b->stime;
+static void update_gt_cputime(struct thread_group_cputimer *cputimer, struct task_cputime *sum)
+{
+	__update_gt_cputime(&cputimer->utime, sum->utime);
+	__update_gt_cputime(&cputimer->stime, sum->stime);
+	__update_gt_cputime(&cputimer->sum_exec_runtime, sum->sum_exec_runtime);
+}
 
-	if (b->sum_exec_runtime>  a->sum_exec_runtime)
-		a->sum_exec_runtime = b->sum_exec_runtime;
+/* Sample thread_group_cputimer values in "cputimer", store results in "times". */
+static inline void sample_group_cputimer(struct task_cputime *times,
+					  struct thread_group_cputimer *cputimer)
+{
+	times->utime = atomic64_read(&cputimer->utime);
+	times->stime = atomic64_read(&cputimer->stime);
+	times->sum_exec_runtime = atomic64_read(&cputimer->sum_exec_runtime);
  }
 
  void thread_group_cputimer(struct task_struct *tsk, struct task_cputime *times)
  {
  	struct thread_group_cputimer *cputimer =&tsk->signal->cputimer;
  	struct task_cputime sum;
-	unsigned long flags;
 
-	if (!cputimer->running) {
+	/* Check if cputimer isn't running. This is accessed without locking. */
+	if (!READ_ONCE(cputimer->running)) {
  		/*
  		 * The POSIX timer interface allows for absolute time expiry
  		 * values through the TIMER_ABSTIME flag, therefore we have
-		 * to synchronize the timer to the clock every time we start
-		 * it.
+		 * to synchronize the timer to the clock every time we start it.
  		 */
  		thread_group_cputime(tsk,&sum);
-		raw_spin_lock_irqsave(&cputimer->lock, flags);
-		cputimer->running = 1;
-		update_gt_cputime(&cputimer->cputime,&sum);
-	} else
-		raw_spin_lock_irqsave(&cputimer->lock, flags);
-	*times = cputimer->cputime;
-	raw_spin_unlock_irqrestore(&cputimer->lock, flags);
+		update_gt_cputime(cputimer,&sum);
+
+		/*

Quoted 27 lines · Jason Low

  void thread_group_cputimer(struct task_struct *tsk, struct task_cputime *times)
  {
  	struct thread_group_cputimer *cputimer =&tsk->signal->cputimer;
  	struct task_cputime sum;

kernel/time/posix-cpu-timers.c +6 -11

-	unsigned long flags;
 
-	if (!cputimer->running) {
+	/* Check if cputimer isn't running. This is accessed without locking. */
+	if (!READ_ONCE(cputimer->running)) {
  		/*
  		 * The POSIX timer interface allows for absolute time expiry
  		 * values through the TIMER_ABSTIME flag, therefore we have
-		 * to synchronize the timer to the clock every time we start
-		 * it.
+		 * to synchronize the timer to the clock every time we start it.
  		 */
  		thread_group_cputime(tsk,&sum);
-		raw_spin_lock_irqsave(&cputimer->lock, flags);
-		cputimer->running = 1;
-		update_gt_cputime(&cputimer->cputime,&sum);
-	} else
-		raw_spin_lock_irqsave(&cputimer->lock, flags);
-	*times = cputimer->cputime;
-	raw_spin_unlock_irqrestore(&cputimer->lock, flags);
+		update_gt_cputime(cputimer,&sum);
+
+		/*

kernel/time/posix-cpu-timers.c static int cpu_clock_sample(const clockid_t which_clock, struct task_struct *p, · line 255

Quoted 10 lines

kernel/time/posix-cpu-timers.c +9 -0

+		 * We're setting cputimer->running without a lock. Ensure
+		 * this only gets written to in one operation. We set
+		 * running after update_gt_cputime() as a small optimization,
+		 * but barriers are not required because update_gt_cputime()
+		 * can handle concurrent updates.
+		 */
+		WRITE_ONCE(cputimer->running, 1);
+	}
+	sample_group_cputimer(times, cputimer);
  }

If there is a possibility that more than one thread will be running this code concurrently, I think it will be safer to use cmpxchg to set the running flag:

     if (!READ_ONCE(cputimer->running) && !cmpxchg(&cputimer->running, 
0, 1)) {
         ...

This will ensure that only one thread will update it.

Commit-ID:  1018016c706f7ff9f56fde3a649789c47085a293
Gitweb:     http://git.kernel.org/tip/1018016c706f7ff9f56fde3a649789c47085a293
Author:     Jason Low <[email protected]>
AuthorDate: Tue, 28 Apr 2015 13:00:22 -0700
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 8 May 2015 12:15:31 +0200

sched, timer: Replace spinlocks with atomics in thread_group_cputimer(), to improve scalability

This patch adds an atomic variant of the task_cputime data structure, which can be used to store and update task_cputime statistics without needing to do locking.

Suggested-by Ingo Molnar <[email protected]>

Signed-off-by Jason Low <[email protected]>

Recent optimizations were made to thread_group_cputimer to improve its scalability by keeping track of cputime stats without a lock. However, the values were open coded to the structure, causing them to be at a different abstraction level from the regular task_cputime structure. Furthermore, any subsequent similar optimizations would not be able to share the new code, since they are specific to thread_group_cputimer.

This patch adds the new task_cputime_atomic data structure (introduced in the previous patch in the series) to thread_group_cputimer for keeping track of the cputime atomically, which also helps generalize the code.

Suggested-by Ingo Molnar <[email protected]>

Signed-off-by Jason Low <[email protected]>