linux-kernel - Re: [BUG] Paravirtual time accounting / IRQ time accounting

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140322144752.93371i3e3g500fgk@intranet.cs.hku.hk>
Date:	Sat, 22 Mar 2014 14:47:52 +0800
From:	lwcheng@...hku.hk
To:	Mike Galbraith <umgwanakikbuti@...il.com>
Cc:	Glauber Costa <glommer@...il.com>, Rik van Riel <riel@...hat.com>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	LKML <linux-kernel@...r.kernel.org>
Subject: Re: [BUG] Paravirtual time accounting / IRQ time accounting


Quoting Mike Galbraith <umgwanakikbuti@...il.com>:

> On Thu, 2014-03-20 at 12:01 -0300, Glauber Costa wrote:
>> On Wed, Mar 19, 2014 at 6:42 AM,  <lwcheng@...hku.hk> wrote:
>> > In consolidated environments, when there are multiple virtual  
>> machines (VMs)
>> > running on one CPU core, timekeeping will be a problem to the guest OS.
>> > Here, I report my findings about Linux process scheduler.
>> >
>> >
>> > Description
>> > ------------
>> > Linux CFS relies on rq->clock_task to charge each task, determine  
>> vruntime,
>> > etc.
>> >
>> > When CONFIG_IRQ_TIME_ACCOUNTING is enabled, the time spent on serving IRQ
>> > will be excluded from updating rq->clock_task.
>> > When CONFIG_PARAVIRT_TIME_ACCOUNTING is enabled, the time stolen by the
>> > hypervisor
>> > will also be excluded from updating rq->clock_task.
>> >
>> > With "both" CONFIG_IRQ_TIME_ACCOUNTING and CONFIG_PARAVIRT_TIME_ACCOUNTING
>> > enabled,
>> > I put three KVM guests on one core and run hackbench in each guest. I find
>> > that
>> > in the guests, rq->clock_task stays *unchanged*. The malfunction  
>> embarrasses
>> > CFS.
>> > ------------
>> >
>> >
>> > Analysis
>> > ------------
>> > [src/kernel/sched/core.c]
>> > static void update_rq_clock_task(struct rq *rq, s64 delta)
>> > {
>> >     ... ...
>> > #ifdef CONFIG_IRQ_TIME_ACCOUNTING
>> >     irq_delta = irq_time_read(cpu_of(rq)) - rq->prev_irq_time;
>> >     ... ...
>> >     rq->prev_irq_time += irq_delta;
>> >     delta -= irq_delta;
>> > #endif
>> >
>> > #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
>> >     if (static_key_false((&paravirt_steal_rq_enabled))) {
>> >         steal = paravirt_steal_clock(cpu_of(rq));
>> >         steal -= rq->prev_steal_time_rq;
>> >         ... ...
>> >         rq->prev_steal_time_rq += steal;
>> >         delta -= steal;
>> >     }
>> > #endif
>> >
>> >     rq->clock_task += delta;
>> >     ... ...
>> > }
>> > --
>> > "delta" -> the intended increment to rq->clock_task
>> > "irq_delta" -> the time spent on serving IRQ (hard + soft)
>> > "steal" -> the time stolen by the underlying hypervisor
>> > --
>> > "irq_delta" is calculated based on sched_clock_cpu(), which is vulnerable
>> > to VM scheduling delays.
>>
>> This looks like a real problem indeed. The main problem in searching
>> for a solution, is that of course not all of the irq time is steal
>> time and vice versa. In this case, we could subtract irq_time from
>> steal, and add only the steal part time that is in excess. I don't
>> think this is 100 % guaranteed, but maybe it is a good approximation.
>>
>> Rik, do you have an opinion on this ?
>
> Hrm, on my little Q6600 box, I'm running 3 VMS all pinned to CPU3, all
> running hackbench -l zillion, one of them also running crash, staring at
> it's sole rq->clock_task as I write this, with kernels (3.11.10) on both
> host and guest configured as reported.
>
>   clock_task = 631322187004,
>   clock_task = 631387807452,
>   clock_task = 631474214294,
>   clock_task = 631523864893,
>   clock_task = 631604646268,
>   clock_task = 631643276025,
>
> Maybe 3 VMs isn't enough overload for such a beastly CPU.  Top reports
> some very funky utilization numbers, but other than that, the things
> seem to work fine here.  perf thinks scheduling work too.
>
> -Mike
>

I checked the source code again. I forgot to mention that I commented out
steal_ticks() in my experiments (sorry):
[kernel/sched/core.c]
-------------------------------
#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
     if (static_key_false((&paravirt_steal_rq_enabled))) {
         /*
         u64 st;
         */
         steal = paravirt_steal_clock(cpu_of(rq));
         steal -= rq->prev_steal_time_rq;

         if (unlikely(steal > delta))
             steal = delta;
         /*
         st = steal_ticks(steal);
         steal = st * TICK_NSEC;
         */
         rq->prev_steal_time_rq += steal;

         delta -= steal;
     }
#endif

     rq->clock_task += delta;
-------------------------------

I do it just for "accuracy", because I fully trust "steal" reported
by the hypervisor. I do not quite understand why it is trimmed again
using steal_ticks(). Please enlighten me.

Even when "steal == delta", as long as "steal" is not exactly
(N * TICK_NSEC), after steal_ticks(), it will be always smaller
than "delta".
So, rq->clock_task can still progress, but may not in the precise way.
Each time, the error is within the range (0, TICK_NSEC).

When CONFIG_IRQ_TIME_ACCOUNTING is disabled, deleting steal_ticks()
does not affect the update to rq->clock_task.

I tested both 3.10.0 and 3.13.5. The results are consistent.

-Luwei




--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/