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

[Peter Zijlstra]

On Mon, Jun 13, 2016 at 08:41:00AM -0000, Thomas Gleixner wrote:

> + * HZ 1000
> + * Level Offset  Granularity            Range
> + *  0   0          1 ms                 0 ms -         63 ms
> + *  1  64          8 ms                64 ms -        511 ms
> + *  2 128         64 ms               512 ms -       4095 ms (512ms - ~4s)
> + *  3 192        512 ms              4096 ms -      32767 ms (~4s - ~32s)
> + *  4 256       4096 ms (~4s)       32768 ms -     262143 ms (~32s - ~4m)
> + *  5 320      32768 ms (~32s)     262144 ms -    2097151 ms (~4m - ~34m)


> +static int collect_expired_timers(struct timer_base *base,
> +				  struct hlist_head *heads)
> +{
> +	unsigned long clock = base->clk;
> +	struct hlist_head tmp, *vec;
> +	int i, levels = 0;
> +	unsigned int idx;
> +
> +	/* Expire the regular buckets */
> +	for (i = 0; i < LVL_DEPTH - 1; i++) {
> +		idx = (clock & LVL_MASK) + i * LVL_SIZE;
> +
> +		if (__test_and_clear_bit(idx, base->pending_map)) {
> +			vec = base->vectors + idx;
> +			hlist_move_list(vec, heads++);
> +			levels++;
> +		}
> +		/* Is it time to look at the next level? */
> +		if (clock & LVL_CLK_MASK)
> +			return levels;
> +		/* Shift clock for the next level granularity */
> +		clock >>= LVL_CLK_SHIFT;
> +	}
> +
> +	/* Cascading, sigh... */

So given that userspace has no influence on timer period; can't we
simply fail to support timers longer than 30 minutes?

In anything really arming timers _that_ long?

> +	idx = (clock & LVL_MASK) + i * LVL_SIZE;
> +
> +	if (__test_and_clear_bit(idx, base->pending_map)) {
> +		vec = base->vectors + idx;
> +		hlist_move_list(vec, &tmp);
> +		/* Make sure we queue them in the future */
> +		base->clk++;
> +		while (!hlist_empty(&tmp)) {
> +			struct timer_list *timer;
> +
> +			timer = hlist_entry(tmp.first, struct timer_list, entry);
> +			trace_timer_cascade(timer);
> +			__hlist_del(&timer->entry);
> +			__internal_add_timer(base, timer);
> +		}
> +		base->clk--;
> +	}
> +	return levels;
> +}