linux-kernel - Re: [RFC PATCH] timer: Fix bucket

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: <87y2ckdnea.ffs@nanos.tec.linutronix.de>
Date:   Wed, 12 May 2021 16:42:21 +0200
From:   Thomas Gleixner <tglx@...utronix.de>
To:     Xiongfeng Wang <wangxiongfeng2@...wei.com>, john.stultz@...aro.org,
        sboyd@...nel.org
Cc:     linux-kernel@...r.kernel.org, wangxiongfeng2@...wei.com
Subject: Re: [RFC PATCH] timer: Fix bucket_expiry calculation

Xiongfeng,

On Wed, May 12 2021 at 20:15, Xiongfeng Wang wrote:
> When I use schedule_timeout(5) to put a process into sleep on my machine
> with HZ = 100. It always sleep about 60ms. I enable the timer trace and
> find out, when the timer_list expires, 'now' is always equal to
> 'expires + 1'. I print 'base->next_expiry' in '__run_timers' and find out
> 'next_expiry' is always equal to 'expires + 1';
>
> It is because we use the following equation to calculate bucket_expiry.
>
>   bucket_expiry = ((expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl)) << LVL_SHIFT(lvl)
>
> 'bucket_expiry' is equal to 'expires + 1' when lvl = 0. So modify the
> equation as follows to fix the issue.
>
>   bucket_expiry = ((expires + LVL_GRAN(lvl) - 1) >> LVL_SHIFT(lvl)) << LVL_SHIFT(lvl)

That's wrong because you move the expiry of each timer one jiffie ahead,
which violates the guarantee that a timer sleeps at least for one jiffie
for real and not measured in jiffies.

  jiffies = 0
  schedule_timeout(1)

   local_irq_disable()
			  -> timer interrupt is raised in HW
   timer->expires = jiffies + 1 <- 1
   add_timer(timer)
   local_irq_enable()
   timer interrupt
      jiffies++;
      softirq()
	  expire(timer); -> timer is expired immediately       

So the off by one has a reason and is required to prevent too short
timeouts. There is nothing you can do about that because that's a
property of low granularity tick based timer wheels.

That's even documented in the comment above the code you modified:

	/*
	 * The timer wheel has to guarantee that a timer does not fire
	 * early. Early expiry can happen due to:
	 * - Timer is armed at the edge of a tick
	 * - Truncation of the expiry time in the outer wheel levels
	 *
	 * Round up with level granularity to prevent this.
	 */

Thanks,

	  tglx