linux-kernel - Re: [PATCH v3 1/2] timer: add a function to adjust timeouts to be upper bound

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: <871qyb35q4.ffs@tglx>
Date:   Tue, 05 Apr 2022 17:33:23 +0200
From:   Thomas Gleixner <tglx@...utronix.de>
To:     Artem Savkov <asavkov@...hat.com>,
        Anna-Maria Behnsen <anna-maria@...utronix.de>
Cc:     netdev@...r.kernel.org, Josh Poimboeuf <jpoimboe@...hat.com>,
        davem@...emloft.net, yoshfuji@...ux-ipv6.org, dsahern@...nel.org,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3 1/2] timer: add a function to adjust timeouts to be
 upper bound

On Sat, Apr 02 2022 at 08:55, Artem Savkov wrote:
> On Wed, Mar 30, 2022 at 03:40:55PM +0200, Anna-Maria Behnsen wrote:
>> When calculating the level/index with a relative timeout, there is no
>> guarantee that the result is the same when actual enqueueing the timer with
>> expiry = jiffies + timeout .
>
> Yes, you are correct. This especially is a problem for timeouts placed
> just before LVL_START(x), which is a good chunk of cases. I don't
> think it is possible to get to timer_base clock without meddling with
> the hot-path.

Especially not when the timer might end up being migrated to a different
base, which would in the worst case require to do the calculation twice
if the base clocks differ.

The problem especially with network timers is that in the traffic case
the timers are often rearmed at high frequency. See the optimizations in
mod_timer() which try to avoid dequeue/enqueue sequences.

One of the main reasons for giving up on accuracy for the timer wheel
back then was to avoid two issues for networking:

    - Full rearming of a timer which ended up in the same expiry bucket
      due to software batching (incomplete, but with the same goal and
      the same 12.5% error margin).

    - Cascading bursts.

      We gathered statistics from various workloads which showed that
      99+% of all timers were canceled or rearmed before expiry, but
      under certain load scenarios a large portion of those timers where
      cascaded into a lower wheel level with smaller granularity before
      cancelation or rearming.

      As the wheel level granularity was strictly exponential the event
      of cascading a large amount (hint: thousands) of timers in one go
      was not uncommon. Cascading happened with interrupts disabled and
      it touched a usualy cold cache line per cascaded timer...

> Is it possible to determine the upper limit of error margin here? My
> assumption is it shouldn't be very big, so maybe it would be enough to
> account for this when adjusting timeout at the edge of a level.
> I know this doesn't sound good but I am running out of ideas here.

Let's just take a step back.

So we know, that the maximal error margin in the wheel is 12.5%, right?
That means, if you take your relative timeout and subtract 12.5% then
you are in the right ballpark and the earliest expiry will not be before
that point obviously, but it's also guaranteed not to expire later than
the original timeout. Obviously this will converge towards the early
expiry the longer the timeouts are, but it's bound.

Also due to the properties of the wheel, the lag of base::clk will
obviously only affect those levels where lag >= LVL_GRAN(level).

That's not perfect, but perfect is the enemy of good.

Thanks,

        tglx