timer: Migrate running timers

Cc Steven Miao <[email protected]>

+#define TIMER_FLAG_MASK 0x7LU

kernel/time/timer.c +17 -1

@@ -1189,12 +1195,41 @@ static inline void __run_timers(struct tvec_base *base)
 			cascade(base, &base->tv5, INDEX(3));
 		++base->timer_jiffies;
 		list_replace_init(base->tv1.vec + index, head);
+
+again:
 		while (!list_empty(head)) {
 			void (*fn)(unsigned long);
 			unsigned long data;
 			bool irqsafe;
 
-			timer = list_first_entry(head, struct timer_list,entry);
+			timer = list_first_entry(head, struct timer_list, entry);
+
+			if (unlikely(timer_running(timer))) {
+				/*
+				 * The only way to get here is if the handler,
+				 * running on another base, re-queued itself on
+				 * this base, and the handler hasn't finished
+				 * yet.
+				 */
+
+				if (list_is_last(&timer->entry, head)) {
+					/*
+					 * Drop lock, so that TIMER_RUNNING can
+					 * be cleared on another base.
+					 */

kernel/time/timer.c +12 -0

+			}
+
 			fn = timer->function;
 			data = timer->data;
 			irqsafe = tbase_get_irqsafe(timer->base);

@@ -1202,6 +1237,7 @@ static inline void __run_timers(struct tvec_base *base)
 			timer_stats_account_timer(timer);
 
 			base->running_timer = timer;
+			timer_set_running(timer);
 			detach_expired_timer(timer, base);
 
 			if (irqsafe) {

@@ -1213,6 +1249,25 @@ static inline void __run_timers(struct tvec_base *base)
 				call_timer_fn(timer, fn, data);
 				spin_lock_irq(&base->lock);
 			}
+
+			/*
+			 * Handler running on this base, re-queued itself on
+			 * another base ?
+			 */
+			if (unlikely(timer->base != base)) {
+				unsigned long flags;
+				struct tvec_base *tbase;
+

No new flags in the timer base, no concurrent expiry, no extra conditionals in the expiry path. Just a single extra check at the end of the softirq handler for this rare condition instead of imposing all that nonsense to the hotpath.

Does this look any better ?

1.) Should the above list_empty(migration_list) block be added out of the

	while (time_after_eq(jiffies, base->timer_jiffies))

    block ? So that we check it only once per timer interrupt.

Also ->running_timer is set to the last serviced timer and a del_timer_sync() might be waiting to remove it. But we continue with the migration list first, without clearing it first. Not sure if this is important at all..

2.) By the time we finish serving all pending timers, local CPU might not be
idle anymore OR the target CPU may become idle.

2.) It might be better to update preferred_target every time we choose a difference base. This may help us avoid calling get_nohz_timer_target() in the second if block above.

Are you realizing that __mod_timer() is a massive hotpath for network heavy workloads?

Quoted 3 lines · Thomas Gleixner

Are you realizing that __mod_timer() is a massive hotpath for network heavy workloads?

BTW I was considering using mod_timer_pinned() from these networking timers (ie sk_reset_timer())

get_nohz_timer_target() sounds cool for laptop users, but is one cause for bad responses to DDOS, when the selected cpu gets stressed.

This is the reason I used mod_timer_pinned() in commit 789f558cfb3680ae ("tcp/dccp: get rid of central timewait timer")

Hmm, that sounds unfortunate, this would wreck life for the power aware laptop/tablet etc.. people.

There is already a sysctl to manage this, is that not enough to mitigate this problem on the server side of things?

Check commit 4a8e320c929991c9480 ("net: sched: use pinned timers") for a specific example of the problems that can be raised.

but /proc/sys/kernel/timer_migration adds a fair overhead in many workloads.

get_nohz_timer_target() has to touch 3 cache lines per cpu...

Quoted 2 lines · Eric Dumazet

Check commit 4a8e320c929991c9480 ("net: sched: use pinned timers") for a specific example of the problems that can be raised.

If you have a problem with the core timer code then it should be fixed there and not worked around in some place which will ruin stuff for power saving interested users. I'm so tired of this 'I fix it in my sandbox' attitude, really. If the core code has a shortcoming we fix it there right away because you are probably not the only one who runs into that shortcoming. So if we don't fix it in the core we end up with a metric ton of slightly different (or broken) workarounds which affect the workload/system characteristics of other people.

Just for the record. Even the changelog of this commit is blatantly wrong:

"We can see that timers get migrated into a single cpu, presumably
idle at the time timers are set up."

The timer migration moves timers to non idle cpus to leave the idle ones alone for power saving sake.

I can see and understand the reason why you want to avoid that, but I have to ask the question whether this pinning is the correct behaviour under all workloads and system characteristics. If yes, then the patch is the right answer, if no, then it is simply the wrong approach.

Quoted 3 lines

but /proc/sys/kernel/timer_migration adds a fair overhead in many workloads.

Quoted 1 line

get_nohz_timer_target() has to touch 3 cache lines per cpu...

And this is something we can fix and completely avoid if we think about it. Looking at the code I have to admit that the out of line call and the sysctl variable lookup is silly. But its not rocket science to fix this.

Quoted 13 lines · Thomas Gleixner

Quoted 2 lines · Eric Dumazet

Check commit 4a8e320c929991c9480 ("net: sched: use pinned timers") for a specific example of the problems that can be raised.

If you have a problem with the core timer code then it should be fixed there and not worked around in some place which will ruin stuff for power saving interested users. I'm so tired of this 'I fix it in my sandbox' attitude, really. If the core code has a shortcoming we fix it there right away because you are probably not the only one who runs into that shortcoming. So if we don't fix it in the core we end up with a metric ton of slightly different (or broken) workarounds which affect the workload/system characteristics of other people.

Quoted 5 lines

Just for the record. Even the changelog of this commit is blatantly wrong:

"We can see that timers get migrated into a single cpu, presumably
idle at the time timers are set up."

Spare me the obvious typo. A 'not' is missing.

Quoted 8 lines

The timer migration moves timers to non idle cpus to leave the idle ones alone for power saving sake.

I can see and understand the reason why you want to avoid that, but I have to ask the question whether this pinning is the correct behaviour under all workloads and system characteristics. If yes, then the patch is the right answer, if no, then it is simply the wrong approach.

Quoted 9 lines

Quoted 4 lines

but /proc/sys/kernel/timer_migration adds a fair overhead in many workloads.

get_nohz_timer_target() has to touch 3 cache lines per cpu...

And this is something we can fix and completely avoid if we think about it. Looking at the code I have to admit that the out of line call and the sysctl variable lookup is silly. But its not rocket science to fix this.

Awesome.

kernel/sched/core.c void resched_cpu(int cpu) · line 602

Quoted 11 lines · Thomas Gleixner

kernel/sched/core.c +3 -4

-int get_nohz_timer_target(int pinned)
+int get_nohz_timer_target(void)
 {
-	int cpu = smp_processor_id();
-	int i;
+	int i, cpu = smp_processor_id();
 	struct sched_domain *sd;
 
-	if (pinned || !get_sysctl_timer_migration() || !idle_cpu(cpu))
+	if (!idle_cpu(cpu))
 		return cpu;

Maybe also test in_serving_softirq() ?

if (in_serving_softirq() || !idle_cpu(cpu))

	return cpu;

There is a fundamental problem with networking load : Many cpus appear to be idle from scheduler perspective because no user/kernel task is running.

CPUs servicing NIC queues can be very busy handling thousands of packets per second, yet have no user/kernel task running.

idle_cpu() return code is : this cpu is idle. hmmmm, really ?

cpus are busy, *and* have to access alien data/locks to activate timers that hardly fire anyway.

When idle_cpu() finally gives the right indication, it is too late :
ksoftirqd might be running on the wrong cpu. Innocent cpus, overwhelmed by a sudden timer load and locked into a service loop.

This cannot resist to a DOS, and even with non malicious traffic, the overhead is high.

You definitely have a point from the high throughput networking perspective.

Though in a power optimizing scenario with minimal network traffic this might be the wrong decision. We have to gather data from the power maniacs whether this matters or not. The FULL_NO_HZ camp might be pretty unhappy about the above.

Quoted 7 lines · Thomas Gleixner

You definitely have a point from the high throughput networking perspective.

Though in a power optimizing scenario with minimal network traffic this might be the wrong decision. We have to gather data from the power maniacs whether this matters or not. The FULL_NO_HZ camp might be pretty unhappy about the above.

Sure, I understand.

To make this clear, here the profile on a moderately loaded TCP server, pushing ~20Gbits of data. Most of TCP output is ACK clock driven (thus from softirq context).

(using regular sendmsg() system calls, that why the get_nohz_timer_target() is 'only' second in the profile, but add the find_next_bit() to it and this is very close being at first position)

   PerfTop:    4712 irqs/sec  kernel:96.7%  exact:  0.0% [4000Hz cycles],  (all, 72 CPUs)
-----------------------------------------------------------------------------------------
    10.16%  [kernel]          [k] copy_user_enhanced_fast_string            
     5.66%  [kernel]          [k] get_nohz_timer_target                     
     5.59%  [kernel]          [k] _raw_spin_lock                            
     2.53%  [kernel]          [k] __netif_receive_skb_core                  
     2.27%  [kernel]          [k] find_next_bit                             
     1.90%  [kernel]          [k] tcp_ack                                   

Maybe a reasonable heuristic would be to
change /proc/sys/kernel/timer_migration default to 0 on hosts with more than 32 cpus.

profile with timer_migration = 0

   PerfTop:    3656 irqs/sec  kernel:94.3%  exact:  0.0% [4000Hz cycles],  (all, 72 CPUs)
-----------------------------------------------------------------------------------------
    13.95%  [kernel]          [k] copy_user_enhanced_fast_string            
     4.65%  [kernel]          [k] _raw_spin_lock                            
     2.57%  [kernel]          [k] __netif_receive_skb_core                  
     2.33%  [kernel]          [k] tcp_ack               

Quoted 38 lines · Eric Dumazet

Quoted 7 lines · Thomas Gleixner

You definitely have a point from the high throughput networking perspective.

Though in a power optimizing scenario with minimal network traffic this might be the wrong decision. We have to gather data from the power maniacs whether this matters or not. The FULL_NO_HZ camp might be pretty unhappy about the above.

Sure, I understand.

To make this clear, here the profile on a moderately loaded TCP server, pushing ~20Gbits of data. Most of TCP output is ACK clock driven (thus from softirq context).

(using regular sendmsg() system calls, that why the get_nohz_timer_target() is 'only' second in the profile, but add the find_next_bit() to it and this is very close being at first position)

   PerfTop:    4712 irqs/sec  kernel:96.7%  exact:  0.0% [4000Hz cycles],  (all, 72 CPUs)
-----------------------------------------------------------------------------------------
    10.16%  [kernel]          [k] copy_user_enhanced_fast_string            
     5.66%  [kernel]          [k] get_nohz_timer_target                     
     5.59%  [kernel]          [k] _raw_spin_lock                            
     2.53%  [kernel]          [k] __netif_receive_skb_core                  
     2.27%  [kernel]          [k] find_next_bit                             
     1.90%  [kernel]          [k] tcp_ack                                   

Maybe a reasonable heuristic would be to
change /proc/sys/kernel/timer_migration default to 0 on hosts with more than 32 cpus.

profile with timer_migration = 0

Quoted 6 lines

   PerfTop:    3656 irqs/sec  kernel:94.3%  exact:  0.0% [4000Hz cycles],  (all, 72 CPUs)
-----------------------------------------------------------------------------------------
    13.95%  [kernel]          [k] copy_user_enhanced_fast_string            
     4.65%  [kernel]          [k] _raw_spin_lock                            
     2.57%  [kernel]          [k] __netif_receive_skb_core                  
     2.33%  [kernel]          [k] tcp_ack               

Is that with the static key patch applied?

kernel/time/timer.c +9 -0

@@ -1213,6 +1249,25 @@ static inline void __run_timers(struct tvec_base *base)
 				call_timer_fn(timer, fn, data);
 				spin_lock_irq(&base->lock);
 			}
+
+			/*
+			 * Handler running on this base, re-queued itself on
+			 * another base ?
+			 */
+			if (unlikely(timer->base != base)) {
+				unsigned long flags;
+				struct tvec_base *tbase;
+

While queuing a timer, we try to migrate it to a non-idle core if the local core is idle, but we don't try that if the timer is re-armed from its handler.

There were few unsolved problems due to which it was avoided until now. But there are cases where solving these problems can be useful. When the timer is always re-armed from its handler, it never migrates to other cores. And many a times, it ends up waking an idle core to just service the timer, which could have been handled by a non-idle core.

Peter suggested [1] few changes which can make that work and the first patch does exactly that. The second one is a minor improvement, that replaces 'running_timer' pointer with 'busy'. That variable was required as part of a sanity check during CPU hot-unplug operation. I was not sure if we should drop this extra variable ('running_timer' or 'busy') and the sanity check.