Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1421649 > unrolled thread

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

Back to article view | Back to linux.kernel

Contents

  Re: [patch 13/20] timer: Switch to a non cascading wheel "George Spelvin" <linux@sciencehorizons.net> - 2016-06-14 10:20 +0200
    Re: [patch 13/20] timer: Switch to a non cascading wheel Thomas Gleixner <tglx@linutronix.de> - 2016-06-14 11:00 +0200
      Re: [patch 13/20] timer: Switch to a non cascading wheel "George Spelvin" <linux@sciencehorizons.net> - 2016-06-14 12:20 +0200
    Re: [patch 13/20] timer: Switch to a non cascading wheel Peter Zijlstra <peterz@infradead.org> - 2016-06-14 12:30 +0200
      Re: [patch 13/20] timer: Switch to a non cascading wheel "George Spelvin" <linux@sciencehorizons.net> - 2016-06-14 15:00 +0200
        Re: [patch 13/20] timer: Switch to a non cascading wheel Thomas Gleixner <tglx@linutronix.de> - 2016-06-14 19:00 +0200
          Re: [patch 13/20] timer: Switch to a non cascading wheel "George Spelvin" <linux@sciencehorizons.net> - 2016-06-14 22:00 +0200

#1421649 — Re: [patch 13/20] timer: Switch to a non cascading wheel

Nice cleanup!


I think I see a buglet in your level-5 cascading.

Suppose a timer is requested far in the future for a time
that is an exact multiple of 32768 jiffies.

collect_expired_timers() scans level 5 after all the previous ones,
and will cascade it to level 0, in a level-0 bucket which has already
been scanned, and won't be scanned again for 64 jiffies.

I agree that 64 jiffies is well within your allowed rounding accuracy,
and order of timer firing is not guaranteed when they're for the same
time, but it is a bit odd when a timer fires 32 jiffies *before* another
timer scheduled for 32 jiffies later.  That's the sort of peculiarity
that could lead to a subtle bug.


While I like the cleanup of just limiting long-term resolution, if
it turns out to be necessary, it's not too hard to add exact timers
back in if a need is found in future.  All you need is a second
__internal_add_timer function that rounds down rather than up, and to
teach expire_timers() to cascade in the unlikely situation that a timer
does have an expiry time in the future.

(It also gets rid of the special case for level 5.)


Other, mostly minor, code comments:

> +/* Level offsets in the wheel */
> +#define LVL0_OFFS	(0)
> +#define LVL1_OFFS	(LVL_SIZE)
> +#define LVL2_OFFS	(LVL1_OFFS + LVL_SIZE)
> +#define LVL3_OFFS	(LVL2_OFFS + LVL_SIZE)
> +#define LVL4_OFFS	(LVL3_OFFS + LVL_SIZE)
> +#define LVL5_OFFS	(LVL4_OFFS + LVL_SIZE)
> +
> +/* Clock divisor for the next level */
> +#define LVL_CLK_SHIFT	3
> +#define LVL_CLK_DIV	(1 << LVL_CLK_SHIFT)
> +#define LVL_CLK_MASK	(LVL_CLK_DIV - 1)
> +
> +/* The shift constants for selecting the bucket at the levels */
> +#define LVL1_SHIFT	(1 * LVL_CLK_SHIFT)
> +#define LVL2_SHIFT	(2 * LVL_CLK_SHIFT)
> +#define LVL3_SHIFT	(3 * LVL_CLK_SHIFT)
> +#define LVL4_SHIFT	(4 * LVL_CLK_SHIFT)
> +#define LVL5_SHIFT	(5 * LVL_CLK_SHIFT)
> +
> +/* The granularity of each level */
> +#define LVL0_GRAN	0x00000001
> +#define LVL1_GRAN	(LVL0_GRAN << LVL_CLK_SHIFT)
> +#define LVL2_GRAN	(LVL1_GRAN << LVL_CLK_SHIFT)
> +#define LVL3_GRAN	(LVL2_GRAN << LVL_CLK_SHIFT)
> +#define LVL4_GRAN	(LVL3_GRAN << LVL_CLK_SHIFT)
> +#define LVL5_GRAN	(LVL4_GRAN << LVL_CLK_SHIFT)

Wouldn't this all be so much simpler as

#define LVL_BITS	6	/* Renamed previous LVL_SHIFT */
#define LVL_SIZE	(1 << LVL_BITS)
#define LVL_MASK	(LVL_BITS - 1)
#define LVL_OFFS(n)	((n) * LVL_SIZE)
#define LVL_SHIFT(n)	((n) * LVL_CLK_SHIFT)
#define LVL_GRAN(n)	(1 << LVL_SHIFT(n))

Then you could do
+static inline unsigned calc_index(unsigned expires, unsigned level),
+{
+	/* Round up to next bin bin */
+	expires = ((expires - 1) >> LVL_SHIFT(level)) + 1;
+	return LVL_OFFS(level) + (expires & LVL_MASK);
+}


> +#define LVL1_TSTART	(LVL_SIZE - 1)

Er... isn't that LVL_SIZE, as documented in the table above?
Then it could be
#define LVL_TSTART(n) (LVL_SIZE << LVL_SHIFT(n))

Ideally, you'd like all of that

+	if (delta < LVL1_TSTART) {
+		idx = (expires + LVL0_GRAN) & LVL_MASK;
+	} else if (delta < LVL2_TSTART) {
+		idx = calc_index(expires, LVL1_GRAN, LVL1_SHIFT, LVL1_OFFS);
+	} else if (delta < LVL3_TSTART) {
+		idx = calc_index(expires, LVL2_GRAN, LVL2_SHIFT, LVL2_OFFS);
+	} else if (delta < LVL4_TSTART) {
+		idx = calc_index(expires, LVL3_GRAN, LVL3_SHIFT, LVL3_OFFS);
+	} else if (delta < LVL5_TSTART) {
+		idx = calc_index(expires, LVL4_GRAN, LVL4_SHIFT, LVL4_OFFS);

to be replaced with __builtin_clz or similar:

	level = __fls(delta | LVL_MASK);
	if (level <  LVL_BITS + LVL_SHIFT(LVL_DEPTH-1)) {	/* or LVL_DEPTH-2, no difference */
		level = (level + LVL_CLK_SHIFT - LVL_BITS) / LVL_CLK_SHIFT;
	} else if ((long)delta < 0) {
		expires = base->clk;
		level = 0;
	} else {
		level = LVL_DEPTH - 1;
	}
	index = calc_index(expires, level);


> +static inline void detach_expired_timer(struct timer_list *timer)
>  {
>  	detach_timer(timer, true);
> -	if (!(timer->flags & TIMER_DEFERRABLE))
> -		base->active_timers--;
> -	base->all_timers--;
>  }

Is there even a reason to have this wrapper any more?  Why not
just replace all calls to it in the source?


> +		timer = hlist_entry(head->first, struct timer_list, entry);
> +		fn = timer->function;
> +		data = timer->data;
> +
> +		timer_stats_account_timer(timer);
> +
> +		base->running_timer = timer;
> +		detach_expired_timer(timer);

Is there some non-obvious reason that you have to fetch fn and data
so early?  It seems like a register pressure pessimization, if the
compiler can't figure out that timer_stats code can't change them.

The cache line containing this timer was already prefetched when you
updated its entry.pprev as part of removing the previous entry from
the list.

I see why you want to fetch them with the lock held in case there's some
freaky race, but I'd do it all after detach_timer().

[toc] | [next] | [standalone]

#1421681

On Tue, 14 Jun 2016, George Spelvin wrote:
> I think I see a buglet in your level-5 cascading.
> 
> Suppose a timer is requested far in the future for a time
> that is an exact multiple of 32768 jiffies.
> 
> collect_expired_timers() scans level 5 after all the previous ones,
> and will cascade it to level 0, in a level-0 bucket which has already
> been scanned, and won't be scanned again for 64 jiffies.
> 
> I agree that 64 jiffies is well within your allowed rounding accuracy,
> and order of timer firing is not guaranteed when they're for the same
> time, but it is a bit odd when a timer fires 32 jiffies *before* another
> timer scheduled for 32 jiffies later.  That's the sort of peculiarity
> that could lead to a subtle bug.

I thought about that and when looking at those long timeout thingies I came to
the conclusion that it's simply not worth the trouble.
 
> Wouldn't this all be so much simpler as
> 
> #define LVL_BITS	6	/* Renamed previous LVL_SHIFT */
> #define LVL_SIZE	(1 << LVL_BITS)
> #define LVL_MASK	(LVL_BITS - 1)
> #define LVL_OFFS(n)	((n) * LVL_SIZE)
> #define LVL_SHIFT(n)	((n) * LVL_CLK_SHIFT)
> #define LVL_GRAN(n)	(1 << LVL_SHIFT(n))

Indeed.
 
> Ideally, you'd like all of that
> 
> +	if (delta < LVL1_TSTART) {
> +		idx = (expires + LVL0_GRAN) & LVL_MASK;
> +	} else if (delta < LVL2_TSTART) {
> +		idx = calc_index(expires, LVL1_GRAN, LVL1_SHIFT, LVL1_OFFS);
> +	} else if (delta < LVL3_TSTART) {
> +		idx = calc_index(expires, LVL2_GRAN, LVL2_SHIFT, LVL2_OFFS);
> +	} else if (delta < LVL4_TSTART) {
> +		idx = calc_index(expires, LVL3_GRAN, LVL3_SHIFT, LVL3_OFFS);
> +	} else if (delta < LVL5_TSTART) {
> +		idx = calc_index(expires, LVL4_GRAN, LVL4_SHIFT, LVL4_OFFS);
> 
> to be replaced with __builtin_clz or similar:

Except that __fls() is noticeably slower than the if chain.

> > +static inline void detach_expired_timer(struct timer_list *timer)
> >  {
> >  	detach_timer(timer, true);
> > -	if (!(timer->flags & TIMER_DEFERRABLE))
> > -		base->active_timers--;
> > -	base->all_timers--;
> >  }
> 
> Is there even a reason to have this wrapper any more?  Why not
> just replace all calls to it in the source?

That just happened to stay there for no particular reason.

> > +		timer = hlist_entry(head->first, struct timer_list, entry);
> > +		fn = timer->function;
> > +		data = timer->data;
> > +
> > +		timer_stats_account_timer(timer);
> > +
> > +		base->running_timer = timer;
> > +		detach_expired_timer(timer);
> 
> Is there some non-obvious reason that you have to fetch fn and data
> so early?  It seems like a register pressure pessimization, if the
> compiler can't figure out that timer_stats code can't change them.
> 
> The cache line containing this timer was already prefetched when you
> updated its entry.pprev as part of removing the previous entry from
> the list.
> 
> I see why you want to fetch them with the lock held in case there's some
> freaky race, but I'd do it all after detach_timer().

That's not new code. We kept the ordering, but yes, we definitely can turn
that around. The only restriction is that we get it before releasing the lock.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1421743

On Tue, 14 Jun 2016, Thomas Gleixner wrote:
> I thought about that and when looking at those long timeout thingies
> I came to the conclusion that it's simply not worth the trouble.

Okay.  A comment might be nice, just to stop someone else wasting
brain power on it.  E.g.

/*
 * If the timer happens to expire exactly now, this will cascade it to
 * vectors[0] which we just cleared and won't check again for 64 jiffies.
 * This is acceptable error on a timeout this long.
 */

>> to be replaced with __builtin_clz or similar:
> 
> Except that __fls() is noticeably slower than the if chain.

Fair enogh.  I wasn't sure about the distribution; if it's biased low,
then the if chain would win.

> That's not new code. We kept the ordering, but yes, we definitely can turn
> that around. The only restriction is that we get it before releasing the lock.

Thanks!

[toc] | [prev] | [next] | [standalone]

#1421752

On Tue, Jun 14, 2016 at 04:16:02AM -0400, George Spelvin wrote:
> While I like the cleanup of just limiting long-term resolution, if
> it turns out to be necessary, it's not too hard to add exact timers
> back in if a need is found in future.  All you need is a second
> __internal_add_timer function that rounds down rather than up, and to
> teach expire_timers() to cascade in the unlikely situation that a timer
> does have an expiry time in the future.

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.

If not; then I agree, that would clean things up.

> Wouldn't this all be so much simpler as
> 
> #define LVL_BITS	6	/* Renamed previous LVL_SHIFT */
> #define LVL_SIZE	(1 << LVL_BITS)
> #define LVL_MASK	(LVL_BITS - 1)
> #define LVL_OFFS(n)	((n) * LVL_SIZE)
> #define LVL_SHIFT(n)	((n) * LVL_CLK_SHIFT)
> #define LVL_GRAN(n)	(1 << LVL_SHIFT(n))
> 
> Then you could do
> +static inline unsigned calc_index(unsigned expires, unsigned level),
> +{
> +	/* Round up to next bin bin */
> +	expires = ((expires - 1) >> LVL_SHIFT(level)) + 1;
> +	return LVL_OFFS(level) + (expires & LVL_MASK);
> +}

I like.

> 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.

> > +		timer = hlist_entry(head->first, struct timer_list, entry);
> > +		fn = timer->function;
> > +		data = timer->data;
> > +
> > +		timer_stats_account_timer(timer);
> > +
> > +		base->running_timer = timer;
> > +		detach_expired_timer(timer);
> 
> Is there some non-obvious reason that you have to fetch fn and data
> so early?  It seems like a register pressure pessimization, if the
> compiler can't figure out that timer_stats code can't change them.
> 
> The cache line containing this timer was already prefetched when you
> updated its entry.pprev as part of removing the previous entry from
> the list.
> 
> I see why you want to fetch them with the lock held in case there's some
> freaky race, but I'd do it all after detach_timer().

Good point, ideally the compiler can move those loads around inside the
lock, but its unlikely to be _that_ clever. We could indeed lower those
loads manually to just before the unlock.

[toc] | [prev] | [next] | [standalone]

#1421883

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.)

[toc] | [prev] | [next] | [standalone]

#1422104

On Tue, 14 Jun 2016, George Spelvin wrote:
> 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.
 
We can accomodate wheel with 512 buckets with the current ARRAYMASK and that
really should be enough.
 
> 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.

The expiry code uses the pending_map already in patch 13 to avoid looking at
the bucket if its empty.

> * 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.)

We can do that as a seperate patch. Makes sense. 

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1422269

Thomas Gleixner wrote:
> On Tue, 14 Jun 2016, George Spelvin wrote:
>> If you need to shrink TIMER_ARRAYMASK to fit another flag bit,
> 
> We can accomodate wheel with 512 buckets with the current ARRAYMASK and that
> really should be enough.

You're absolutely correct, but I was referring to the possible development
in the future of the need for another flag bit for some purpose *other*
than encoding a bucket number.  There's no need now, but if next year
someone finds and urgent need for another flag bit, there's a way
to proceed.

(Although you could just enlarge "flags"; the removal of "slack" has left
a 32-bit alignment hole.)

> The expiry code uses the pending_map already in patch 13 to avoid looking at
> the bucket if its empty.

My bad, I'm sorry!  I was quickly re-reading it and missed that.
Given the quality of the patch series, I should have expected that and
looked harder.

> Thanks,

Thank *you*.  It really is a pleasure to read.  I can't find anything but the most
insignificant issues to complain about.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web