lkml.org 
[lkml]   [2017]   [Aug]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH v2] timers: Don't wake ktimersoftd on every tick
From
Date
Thomas,

Apologies on the late response. I've been busy last few weeks.

On 07/18/2017 04:33 PM, Thomas Gleixner wrote:
> On Mon, 17 Jul 2017, Haris Okanovic wrote:
>> We recently upgraded from 4.1 to 4.6 and noticed a minor latency
>> regression caused by an additional thread wakeup (ktimersoftd) in
>> interrupt context on every tick. The wakeups are from
>> run_local_timers() raising TIMER_SOFTIRQ. Both TIMER and SCHED softirq
>> coalesced into one ksoftirqd wakeup prior to Sebastian's change to split
>> timers into their own thread.
>>
>> There's already logic in run_local_timers() to avoid some unnecessary
>> wakeups of ksoftirqd, but it doesn't seems to catch them all. In
>> particular, I've seen many unnecessary wakeups when jiffies increments
>> prior to run_local_timers().
>>
>> Change the way timers are collected per Julia and Thomas'
>> recommendation: Expired timers are now collected in interrupt context
>> and fired in ktimersoftd to avoid double-walk of `pending_map`.
>>
>> Collect expired timers in interrupt context to avoid overhead of waking
>> ktimersoftd on every tick. ktimersoftd now wakes only when one or more
>> timers are ready, which yields a minor reduction in small latency spikes.
>>
>> This is implemented by storing lists of expired timers in timer_base,
>> updated on each tick. Any addition to the lists wakes ktimersoftd
>> (softirq) to process those timers.
>
> One thing which would be really good to have in the changelog is the
> overhead of that collection operation in hard irq context.
>

Added testing note: Execution time of run_local_timers() increases by
0.2us to 2.5us as measured by TSC on a 2core Intel Atom E3825 system.

I'm guessing the variance is spin lock contention caused by timers being
added/removed by different threads.

I also verified the average case latency decrease in cyclictest and
reran Anna-Maria's test on a qemu 4core Nehalem VM; latency decreases
and no stalls.

>> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
>> index 5730d42bfd67..e5b537f2308c 100644
>> --- a/kernel/time/timer.c
>> +++ b/kernel/time/timer.c
>> @@ -209,9 +209,12 @@ struct timer_base {
>> bool is_idle;
>> DECLARE_BITMAP(pending_map, WHEEL_SIZE);
>> struct hlist_head vectors[WHEEL_SIZE];
>> + struct hlist_head expired_lists[LVL_DEPTH];
>> + int expired_count;
>
> You need to look at the cache layout of that whole thing. My gut feeling
> tells me that that count is at the wrong place.
>

You're right, there's a 4-byte hole after `lock` we can use. I'll move
`expired_count` there.

>> } ____cacheline_aligned;
>>
>> static DEFINE_PER_CPU(struct timer_base, timer_bases[NR_BASES]);
>> +static DEFINE_PER_CPU(int, block_softirqs);
>
> Why are you putting that into a seperate per cpu variable instead of adding
> a bool to the base struct as I suggested in my example:
>
> base->softirq_activated = false;
>
> Having that separate makes no sense conceptually and cache wise it can
> force to touch yet another cacheline depending on the placement by
> compiler/linker. Looking at your implementation it does in 100% of the
> cases.
>
> You can use the first base for that, as that is going to be touched anyway
> and is cache hot in any case.
>

I was trying to avoid using twice as much memory in the NOHZ case and
didn't consider cache implications. There's actually another 1-byte hole
after `timer_base.is_idle` which can fit this bool.

>> -static void expire_timers(struct timer_base *base, struct hlist_head *head)
>> +static inline void __expire_timers(struct timer_base *base,
>
> What's the purpose of this change? If it makes sense to inline it, then the
> compiler will do so.
>

I inlined it because it only has one call site, but I'm sure the
compiler will figure that out as well. Dropped.

>> + struct hlist_head *head)
>> {
>> while (!hlist_empty(head)) {
>> struct timer_list *timer;
>> @@ -1344,21 +1348,45 @@ static void expire_timers(struct timer_base *base, struct hlist_head *head)
>> }
>> }
>>
>> -static int __collect_expired_timers(struct timer_base *base,
>> - struct hlist_head *heads)
>> +static void expire_timers(struct timer_base *base)
>> {
>> - unsigned long clk = base->clk;
>> + struct hlist_head *head;
>> + int count = READ_ONCE(base->expired_count);
>
> Please keep the reverse fir tree ordering based on length for the variables
> as we have it throughout that code.
>

Moved clk.

>> +
>> + while (count--) {
>
> So this changed vs. the previous implementation and in this case the
> READ_ONCE() is pointless as the compiler CANNOT reevaluate base->foo inside
> that loop.
>

Removed.

>> + head = base->expired_lists + count;
>> + __expire_timers(base, head);
>> + }
>> +
>> + /* Zero base->expired_count after processing all base->expired_lists
>> + * to signal it's ready to get re-populated. Otherwise, we race with
>> + * tick_find_expired() when base->lock is temporarily dropped in
>> + * __expire_timers() */
>
> Please stick to the two sane comment styles:
>
> /* Single line comment */
>
> /*
> * Multi line comment
> * Multi line comment
> * Multi line comment
> */
>
> For further enlightment: http://marc.info/?l=linux-kernel&m=146799838429328&w=2
>

Fixed.

>> + base->expired_count = 0;
>> +}
>> +
>> +static int __collect_expired_timers(struct timer_base *base)
>> +{
>> + unsigned long clk;
>> struct hlist_head *vec;
>> - int i, levels = 0;
>> + int i;
>> unsigned int idx;
>
> See above
>
>> + /*
>> + * expire_timers() must be called at least once before we can
>> + * collect more timers
>> + */
>> + if (base->expired_count)
>> + goto end;
>> +
>> + clk = base->clk;
>> for (i = 0; i < LVL_DEPTH; i++) {
>> idx = (clk & LVL_MASK) + i * LVL_SIZE;
>>
>> if (__test_and_clear_bit(idx, base->pending_map)) {
>> vec = base->vectors + idx;
>> - hlist_move_list(vec, heads++);
>> - levels++;
>> + hlist_move_list(vec,
>> + &base->expired_lists[base->expired_count++]);
>
> Eew. What's wrong with local variables ?
>
> struct hist_head *list = &base->expired_vectors;
>
> at the top of this function and then do
>
> hlist_move_list(vec, list++);
> base->expired_levels++;
>
> or have a local count and use it as index to list[]. The code generation
> should be roughly the same, but I expect it to be better with the seperate
> increments.
>

Done, looks nicer. I was trying to keep changes to existing code minimal.

>> }
>> /* Is it time to look at the next level? */
>> if (clk & LVL_CLK_MASK)
>> @@ -1366,7 +1394,8 @@ static int __collect_expired_timers(struct timer_base *base,
>> /* Shift clock for the next level granularity */
>> clk >>= LVL_CLK_SHIFT;
>> }
>> - return levels;
>> +
>> + end: return base->expired_count;
>
> More Eeew! Can you please look how labels are placed in the
> kernel. Certainly not that way.
>
> Aside of that the goto is silly. You can just return expired_count up at
> that conditional, or move the conditional to the caller.
>

Replaced goto with simple return.

> Actually I do not understand that conditional at the top at all. The call
> site breaks out of the loop when the return value is > 0. So what's that
> for? Paranoia? If that's the case then you want a WARN_ONCE there, because
> that should never happen. Otherwise it's just pointless. If actually
> something relies on that, then it's disgusting.
>
Paranoia. We should never hit this case unless TIMER_SOFTIRQ got raised
without expired timers. Added WARN_ONCE().

>> }
>>
>> #ifdef CONFIG_NO_HZ_COMMON
>> @@ -1559,8 +1588,7 @@ void timer_clear_idle(void)
>> base->is_idle = false;
>> }
>>
>> -static int collect_expired_timers(struct timer_base *base,
>> - struct hlist_head *heads)
>> +static int collect_expired_timers(struct timer_base *base)
>> {
>> /*
>> * NOHZ optimization. After a long idle sleep we need to forward the
>> @@ -1581,16 +1609,41 @@ static int collect_expired_timers(struct timer_base *base,
>> }
>> base->clk = next;
>> }
>> - return __collect_expired_timers(base, heads);
>> + return __collect_expired_timers(base);
>> }
>> #else
>> -static inline int collect_expired_timers(struct timer_base *base,
>> - struct hlist_head *heads)
>> +static inline int collect_expired_timers(struct timer_base *base)
>> {
>> - return __collect_expired_timers(base, heads);
>> + return __collect_expired_timers(base);
>> }
>> #endif
>>
>> +/* Increments timer_base to current jiffies or until first expired
>> + * timer is found. Return number of expired timers. */
>
> Sigh.
>

Fixed comment formatting.

>> +static int find_expired_timers(struct timer_base *base)
>> +{
>> + const unsigned long int end_clk = jiffies;
>
> const ? unsigned long int ?
>

Dropped the const. Didn't realize it violated a coding convention.

>> + int expired_count;
>> +
>> + while ( !(expired_count = collect_expired_timers(base)) &&
>> + time_after_eq(end_clk, base->clk) ) {
>
> These extra white spaces after ( and before ) are pointless and not kernel
> coding style.
>
> What's worse is the order of your conditionals. Just look at the original
> code.
>
>> + base->clk++;
>> + }
>

Fixed.

> Aside of that this loop is fricking hard to read.
>
> int levels = 0;
>
> while (!levels && time_after_eq(jiffies, base->clk)) {
> levels = collect_expired_timers(base, heads);
> base->clk++;
> }
>
> return levels;
>
> Is all what you need here, right? That's what the original loop does as
> well.
>

Correct, but the original loop was in __run_timers() and this one is
called from both __run_timers() and run_local_timers(), which is why I
moved it to a separate function.

>> +
>> + return expired_count;
>> +}
>> +
>> +/* Called from CPU tick routine to collect expired timers up to current
>> + * jiffies. Return number of expired timers. */
>
> Wrong. It returns the number of levels which have expired timers. The
> number of actual timers per level is unknown as we move the complete list.
>

Fixed comment.

>> +static int tick_find_expired(struct timer_base *base)
>> +{
>> + int count;
>
> Missing new line between declaration and code. checkpatch.pl is wrong on a
> lot of things, but it would have told you.
>

Fixed.

>> + raw_spin_lock(&base->lock);
>> + count = find_expired_timers(base);
>> + raw_spin_unlock(&base->lock);
>> + return count;
>
> Please be consistent with the names. We use 'levels' throughout all the other
> functions. Random variable names are just confusing.
>

Renamed "count" to "levels" in timer_base and various functions.

>> +}
>> +
>> /*
>> * Called from the timer interrupt handler to charge one tick to the current
>> * process. user_tick is 1 if the tick is user time, 0 for system.
>> @@ -1618,22 +1671,11 @@ void update_process_times(int user_tick)
>> */
>> static inline void __run_timers(struct timer_base *base)
>> {
>> - struct hlist_head heads[LVL_DEPTH];
>> - int levels;
>> -
>> - if (!time_after_eq(jiffies, base->clk))
>> - return;
>> -
>> raw_spin_lock_irq(&base->lock);
>>
>> - while (time_after_eq(jiffies, base->clk)) {
>> + while (find_expired_timers(base))
>> + expire_timers(base);
>
> Now I understand that extra conditional above. That's crap, really. Two
> ways to solve that:
>
> do {
> expire_timers(base);
> } while (find_expired_timers(base));
>
> which requires a check for base->expired_levels inside of
> expire_timers().
>
> or
>
> if (base->expired_levels)
> expire_timers(base);
>
> while (find_expired_timers(base))
> expire_timers(base);
>

The do-while approach works for me. expire_timers() already noops when
expired_levels is zero. However, I would like to keep the
WARN_ONCE(expired_levels) check in __collect_expired_timers() as a
sanity check.

>> raw_spin_unlock_irq(&base->lock);
>> wakeup_timer_waiters(base);
>
> Errm. Please submit patches against mainline. This is RT only. On mainline
> the overhead of raising the softirq is not that big, but the exercise is
> the same.
>

I have been submitting to both mailing lists simultaneously.

>> @@ -1644,12 +1686,16 @@ static inline void __run_timers(struct timer_base *base)
>> static __latent_entropy void run_timer_softirq(struct softirq_action *h)
>> {
>> struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
>> + int* block_softirq = this_cpu_ptr(&block_softirqs);
>
> Sigh. A pointer is declared with:
>
> int *p;
>
> and not
>
> int* p;
>
>> irq_work_tick_soft();
>>
>> __run_timers(base);
>> if (IS_ENABLED(CONFIG_NO_HZ_COMMON) && base->nohz_active)
>> __run_timers(this_cpu_ptr(&timer_bases[BASE_DEF]));
>> +
>> + /* Allow new TIMER_SOFTIRQs to get scheduled by run_local_timers() */
>> + WRITE_ONCE(*block_softirq, 0);
>
> You are in interrupt enabled code here. So you actually might miss a wakeup
> and delay it to the next tick. If that's your intention then please
> document it proper. If not, you need to disable interrupts around the write
> and recheck stuff.
>

I'm not sure what you mean exaclty. My intention here is to only permit
new TIMER_SOFTIRQs to get raised by run_local_timers(). See updated
commit message for details.

> Also the WRITE_ONCE() is pointless. The compiler cannot reorder the
> write. And it does not protect you from racing with the hard interrupt. So
> for the sloppy variant a simple:
>
> base->softirq_activated = false;
>
> is sufficient.
>
>> }
>>
>> /*
>> @@ -1657,18 +1703,28 @@ static __latent_entropy void run_timer_softirq(struct softirq_action *h)
>> */
>> void run_local_timers(void)
>> {
>> - struct timer_base *base = this_cpu_ptr(&timer_bases[BASE_STD]);
>> + int* block_softirq = this_cpu_ptr(&block_softirqs);
>> + struct timer_base *base;
>>
>> hrtimer_run_queues();
>> +
>> + /* Skip if TIMER_SOFTIRQ is already running for this CPU */
>> + if (READ_ONCE(*block_softirq))
>> + return;
>> +
>> + base = this_cpu_ptr(&timer_bases[BASE_STD]);
>
> And this here becomes:
>
> if (base->softirq_activated)
> return;
>
>> +
>> /* Raise the softirq only if required. */
>> - if (time_before(jiffies, base->clk)) {
>> + if (time_before(jiffies, base->clk) || !tick_find_expired(base)) {
>> if (!IS_ENABLED(CONFIG_NO_HZ_COMMON) || !base->nohz_active)
>> return;
>> /* CPU is awake, so check the deferrable base. */
>> base++;
>> - if (time_before(jiffies, base->clk))
>> + if (time_before(jiffies, base->clk) || !tick_find_expired(base))
>> return;
>
> To make that work, all you need here is:
>
> base--;
>
>> }
>
> and
> base->softirq_activated = true;
>

Done. Dropped WRITE_ONCE().

>> static void __init init_timer_cpu(int cpu)
>> {
>> struct timer_base *base;
>> + int* block_softirq;
>> int i;
>>
>> for (i = 0; i < NR_BASES; i++) {
>> @@ -1852,6 +1910,10 @@ static void __init init_timer_cpu(int cpu)
>> #ifdef CONFIG_PREEMPT_RT_FULL
>> init_swait_queue_head(&base->wait_for_running_timer);
>> #endif
>> + base->expired_count = 0;
>> +
>> + block_softirq = per_cpu_ptr(&block_softirqs, cpu);
>> + *block_softirq = 0;
>
> What kind of voodoo initialization is this? Do you not trust BSS? Or do you
> not make sure that the stuff is brought into proper state when a CPU goes
> offline?
>

Yea, this is pointless. Not sure what I was thinking. Removed.

> Aside of the above, this patch wants to be split into two pieces:
>
> 1) Embedd the hlist heads for expired bucket collection into base
> struct and adjust the code accordingly.
>
> 2) Implement the conditional softirq raise machinery
>

I agree. I split it and will submit a PATCH v3 shortly.

> Thanks,
>
> tglx
>

Thanks,
Haris

\
 
 \ /
  Last update: 2017-08-03 23:05    [W:0.193 / U:0.048 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site