by Frederic Weisbecker

[permalink] [raw]

Subject: Re: [PATCH 3/8] posix-cpu-timers: fix wrong timer initialization

On Tue, Jun 18, 2013 at 11:12:17AM -0400, KOSAKI Motohiro wrote:
> On Tue, Jun 18, 2013 at 10:20 AM, Frederic Weisbecker
> <[email protected]> wrote:
> > On Sun, May 26, 2013 at 05:35:44PM -0400, [email protected] wrote:
> >> From: KOSAKI Motohiro <[email protected]>
> >>
> >> Currently glibc's rt/tst-cputimer1 testcase sporadically fails because
> >> a timer created by timer_create() may fire earlier than specified.
> >>
> >> posix_cpu_timer_set() uses "val" as current time for three purpose. 1)
> >> initialize sig->cputimer. 2) calculation "old" val. 3) calculations an
> >> expires.
> >>
> >> (1) and (2) should only use committed time (i.e. without delta_exec)
> >> because run_posix_cpu_timers() don't care of delta_exec and we need
> >> consistency, but (3) need exact current time (aka cpu clock time) because
> >> an expires should be "now + timeout" by definition.
> >>
> >> This patch distinguishes between two kinds of "now".
> >>
> >> Cc: Olivier Langlois <[email protected]>
> >> Cc: Thomas Gleixner <[email protected]>
> >> Cc: Frederic Weisbecker <[email protected]>
> >> Cc: Ingo Molnar <[email protected]>
> >> Acked-by: Peter Zijlstra <[email protected]>
> >> Signed-off-by: KOSAKI Motohiro <[email protected]>
> >> ---
> >> include/linux/kernel_stat.h | 5 -----
> >> kernel/posix-cpu-timers.c | 14 ++++++++++++--
> >> kernel/sched/core.c | 13 -------------
> >> 3 files changed, 12 insertions(+), 20 deletions(-)
> >>
> >> diff --git a/include/linux/kernel_stat.h b/include/linux/kernel_stat.h
> >> index ed5f6ed..f5d4fdf 100644
> >> --- a/include/linux/kernel_stat.h
> >> +++ b/include/linux/kernel_stat.h
> >> @@ -117,11 +117,6 @@ static inline unsigned int kstat_cpu_irqs_sum(unsigned int cpu)
> >> return kstat_cpu(cpu).irqs_sum;
> >> }
> >>
> >> -/*
> >> - * Lock/unlock the current runqueue - to extract task statistics:
> >> - */
> >> -extern unsigned long long task_delta_exec(struct task_struct *);
> >> -
> >> extern void account_user_time(struct task_struct *, cputime_t, cputime_t);
> >> extern void account_system_time(struct task_struct *, int, cputime_t, cputime_t);
> >> extern void account_steal_time(cputime_t);
> >> diff --git a/kernel/posix-cpu-timers.c b/kernel/posix-cpu-timers.c
> >> index 25447c5..d068808 100644
> >> --- a/kernel/posix-cpu-timers.c
> >> +++ b/kernel/posix-cpu-timers.c
> >> @@ -652,7 +652,7 @@ static int cpu_timer_sample_group(const clockid_t which_clock,
> >> cpu->cpu = cputime.utime;
> >> break;
> >> case CPUCLOCK_SCHED:
> >> - cpu->sched = cputime.sum_exec_runtime + task_delta_exec(p);
> >> + cpu->sched = cputime.sum_exec_runtime;
> >
> > Are you sure that all callers of cpu_timer_sample_group() are fine with that change?
>
> Now, cpu_timer_sample_group() is used from following four points.
>
> posix_cpu_timer_set(): for timer initialization

Right, so to recall what is in your changelog, here we want to:

1) get initial sample and initialize cputime->running to 1, so here
we don't want to commit pending deltas otherwise they may be
accounted twice

2) to compute old value. I would say that here both kind of samples
work (with or without committed pending deltas)

3) set the new timer. We want committed pending deltas here to
compute now + deltas, otherwise the timer might trigger too early

> posix_cpu_timer_get(): for timer_gettime(2)

Here I would say it doesn't matter whether we include pending delta
or not. But just to stay consistent with clock_gettime(), I'd rather
include the pending deltas.

> posix_cpu_timer_schedule(): timer firing

firing or fired. But rescheduling in any case. I would tend to
think we want to include pending deltas as a base to calculate
the next expiry time on top of interval increments, etc...
Pretty much like posix_cpu_timer_set() in fact.

> set_process_cpu_timer(): for itimer

So here the case seem to be very similar to posix_cpu_timer_set()
again.
We pass a relative expiring time delta to setitimer() so we want
the timer to expire at NOW + timeout. So NOW must be the clock
sample that includes the pending deltas that haven't yet been
committed, otherwise the timer may expire too early.

Shouldn't we use cpu_clock_sample_group() here?

>
> I think all of them are safe because, the point is, timer firing
> procedure (check_thread_timers and check_process_timers) don't care
> uncommitted delta. Then, other timer functions need to use the same
> timer tick. Otherwise the inconsistency leak to userland sooner or
> later.
>
> The another solution is, check_{thread/process}_timers take plenty rq
> locks and use accurate time. However, of course, it may make lots
> performance hit. So, I don't want
> to take this way.

If only we could commit the pending deltas on the task stats (like calling update_curr())
everytime we check the timer/clock sample. This way we wouldn't worry about all
these pending sum_exec_runtime stuff to be accounted twice and we could just always read it
without further thoughts.

Also, cpu_timer_sample_group() looks to be fundamentally buggy to begin with.
It may add task_delta_exec(p) twice if thread_group_timer() is called with cputimer_running == 0.

>
>
> > Looking at set_process_cpu_timer() it seems we want the committed time as well to
> > be added on newval. For the same reasons we use cpu_clock_sample_group() in (3) here.
>
> Sorry, I haven't caught your point. Could you elaborate more?

See above when I describe my worries on set_process_cpu_timer().

2013-06-20 08:41:52

by KOSAKI Motohiro

[permalink] [raw]

Subject: Re: [PATCH 6/8] sched: task_sched_runtime introduce micro optimization

(6/18/13 10:18 AM), Frederic Weisbecker wrote:
> On Tue, Jun 18, 2013 at 11:17:41AM -0400, KOSAKI Motohiro wrote:
>>>> +#ifdef CONFIG_64BIT
>>>> + /*
>>>> + * 64-bit doesn't need locks to atomically read a 64bit value. So we
>>>> + * have two optimization chances, 1) when caller doesn't need
>>>> + * delta_exec and 2) when the task's delta_exec is 0. The former is
>>>> + * obvious. The latter is complicated. reading ->on_cpu is racy, but
>>>> + * this is ok. If we race with it leaving cpu, we'll take a lock. So
>>>> + * we're correct. If we race with it entering cpu, unaccounted time
>>>> + * is 0. This is indistinguishable from the read occurring a few
>>>> + * cycles earlier.
>>>> + */
>>>> + if (!add_delta || !p->on_cpu)
>>>> + return p->se.sum_exec_runtime;
>>>
>>> I'm not sure this is correct from an smp ordering POV. p->on_cpu may appear
>>> to be 0 whereas the task is actually running for a while and p->se.sum_exec_runtime
>>> can then be past the actual value on the remote CPU.
>>
>> Quate form Paul's last e-mail
>>
>>> Stronger:
>>>
>>> +#ifdef CONFIG_64BIT
>>> + if (!p->on_cpu)
>>> + return p->se.sum_exec_runtime;
>>> +#endif
>>>
>>> [ Or !p->on_cpu || !add_delta ].
>>>
>>> We can take the racy read versus p->on_cpu since:
>>> If we race with it leaving cpu: we take lock, we're correct
>>> If we race with it entering cpu: unaccounted time ---> 0, this is
>>> indistinguishable from the read occurring a few cycles earlier.
>
> Yeah, my worry was more about both p->on_cpu and p->se.sum_exec_runtime being
> stale for too long. How much time can happen in the worst case before CPU X sees
> the updates done by a CPU Y under rq(Y)->lock considering that CPU X doesn't take rq(Y)
> to read that update? I guess it depends on the hardware, locking and ordering
> that happened before.

Right. The worst case depend on memory access cost on remote node.
If memory access cost is m, The worst scenario is:

t
-------------
0: CPU X start to fetch p->on_cpu. (now it's 0)
0: CPU Y changes p->on_cpu to 1.
m: CPU X sees p->on_cpu is 0.

Then CPU X uses p->se.sum_exec_runtime even though p has delta m. And, in worst case,
all cpus make the same scenario. So, inaccuracy should be m x nr_online_cpus.
In this case, we can ignore cpu cache because we don't hit anyway in worst case.

However, I think it's ok. m is us order and our run_posx_cpu_timer() only has 1/HZ accuracy.
Moreover,taking lock needs more time than m because it need lock prefixed op. Then, It's free lunch.

I have no seen any ordering issue in this code because each CPU have independent time and no dependency. Please tell me if I'm missing something.

> Bah it probably doesn't matter in practice.

I'm ok to drop this "!p->on_cpu" optimization if you really dislike it.
It is just a micro optimization and the benefit is not so much.