linux-kernel - Re: [patch 13/20] timer: Switch to a non cascading wheel

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: <20160614125800.18461.qmail@ns.sciencehorizons.net>
Date:	14 Jun 2016 08:58:00 -0400
From:	"George Spelvin" <linux@...encehorizons.net>
To:	linux@...encehorizons.net, peterz@...radead.org
Cc:	edumazet@...gle.com, linux-kernel@...r.kernel.org,
	richardcochran@...il.com, tglx@...utronix.de
Subject: Re: [patch 13/20] timer: Switch to a non cascading wheel

Peter Zijlstra wrote:
> That did occur to me as well; however I think it would be best to
> eradicate all forms of cascading entirely -- if at all possible.

Agreed.

>> to be replaced with __builtin_clz or similar:

> Problem is for the archs that don't have that, the 5 layer branch is
> trivial for all arches, while software clz/fls is far more expensive.

And there's no way to tell if an architecture has a good one, so bleah.

I was thinking about the flosting-point number representation and what
the effect of a finer table spacing would be.

The maximum error is determined by the difference between LVL_BITS (=6)
and LVL_CLK_SHIFT(=3).

If you dropped those both by 1, you'd get 2/3 as many bits of timer
in 1/2 the space, which would be a slight space saving.  The current 6
levels (64 * 6 = 384 lists) covering 6 + 3*5 = 21 bits be done 32 * 9 =
288 lists (5 + 2*8 = 21).

Not enough to be interesting, and the extra levels increase processing
time.  If you need to shrink TIMER_ARRAYMASK to fit another flag bit,
the easier way would be to encode only the level rather than the index,
since you can derive the latter from level and expiry time trivially.

A couple of really minor tweaks that could be folded in, if Thomas feels
like it:

* It would make sense to move all the TIMER_ARRAYSHIFT/TIMER_ARRAYMASK
  stuff out of patch 13 and into patch 20.
* It would make sense to change the return type of mod_timer (& Co.)
  detach_if_pending, and del_timer to bool.
  ({try_to_,}del_timer_sync return 3 values.)