Re: [RFC v4 13/22] clockevents: check a programmed delta's bounds in terms of cycles

[Nicolai Stange]

Nicolai Stange <nicstange@xxxxxxxxx> writes:

> @@ -332,10 +337,10 @@ int clockevents_program_event(struct clock_event_device *dev, ktime_t expires,
>  	if (delta <= 0)
>  		return force ? clockevents_program_min_delta(dev) : -ETIME;
>  
> -	delta = min(delta, (int64_t) dev->max_delta_ns);
> -	delta = max(delta, (int64_t) dev->min_delta_ns);
> -
>  	clc = ((unsigned long long) delta * dev->mult) >> dev->shift;
> +	clc = min_t(unsigned long, clc, dev->max_delta_ticks);
> +	clc = max_t(unsigned long, clc, dev->min_delta_ticks_adjusted);
> +
>  	rc = dev->set_next_event((unsigned long) clc, dev);
>  
>  	return (rc && force) ? clockevents_program_min_delta(dev) : rc;

This is broken :(

I failed to recognize that ->max_delta_ns serves not only one, but
three purposes actually:
1. It prevents the ced to get programmed with too large values. Still
   works with this patch.
2. It prevents the multiplication by dev->mult from overflowing 64 bits,
   i.e. it clamps the input delta to a range valid for the given
   ->mult. Ouch.
3. On 32 bit archs, it prevents the cast of clc to unsigned long from
   overflowing. Ouch here as well.


The 3.) can be restored by doing 
  clc = min_t(unsigned long long, clc, dev->max_delta_ticks);
rather than min_t(unsigned long, ...)
because dev->max_delta_ticks is of type unsigned long and thus,
<= ULONG_MAX.


Unfortunately, fixing up 2.) is not so straight forward: I'll certainly
have to resort to ->max_delta_ns again. But then, there will be the
issue with non-atomic updates from timekeeping -- at least if
->max_delta_ns continues to represent ->max_delta_ticks as it did
before.

In order to get rid of the requirement to update ->max_delta_ns whenever
the ->mult changes, would it be Ok to decouple ->max_delta_ns from
->max_delta_ticks by
a. setting
     dev->max_delta_ns = (1 << (64 - ilog2(dev->mult))) - 1
   once and for all at device registration (and from clockevents_update_freq()),
b. and introducing an *additional* comparison
     delta = min(delta, (int64_t) dev->max_delta_ns);
   right before the multiplication in clockevents_program_event()?

In this setting, ->max_delta_ns would be a function of the original
->mult only -- more precisely, of ilog2(dev->mult).

Altogether, we'd have

  delta = min(delta, (int64_t) dev->max_delta_ns);
  clc = ((unsigned long long) delta * dev->mult) >> dev->shift;
  clc = min_t(unsigned long long, clc, dev->max_delta_ticks);
  clc = max_t(unsigned long long, clc, dev->min_delta_ticks_adjusted);
  
  rc = dev->set_next_event((unsigned long) clc, dev);

in clockevents_program_event() then.

So, purposes 1.) and 3.) would get served by the second min() while the
first one would make sure that the multiplication will never overflow.

The downside would be the additional comparison + conditional move in
the ced programming path. The ->max_delta_ns and ->max_delta_ticks can
both be moved to struct clock_event_device's first cacheline
simultaneously without affecting any of its remaining hot members though
(on 64 bit archs with a cacheline size of 64 bytes).


Now, to quote your objections to [22/22] ("timekeeping: inform
clockevents about freq adjustments"):

> What makes sure that the resulting shift/mult pair is still valid after this
> adjustment? The non adjusted mult/shift pair might be right at the border of
> potential overflows and the adjustment might just put it over the edge....
> We need at least sanity checks here.

The updated ->mult_adjusted could get restricted to never grow beyond
  (1 << fls(dev->mult)) - 1
where dev->mult is the never changing, non-adjusted mult value. That is,
the mult adjustment would simply stop at the point where it could
possibly introduce overflows for some deltas smaller than the now fixed
->max_delta_ns.


I have to admit that checking both, ->max_delta_ticks and ->max_delta_ns
from clockevents_program_event() is a little bit messy. As is the
cut-off point for the mult adjustments...


Maybe I should just try to schedule the necessary updates from
timekeeping on each CPU instead? If this worked out, I could probably
recalculate appropriate values of ->*_delta_ns and store these
racelessly along with the adjusted mult while not touching
clockevents_program_event() at all. That is, I would schedule something
similar to clockevents_update_freq() on each CPU.


Thanks,

Nicolai Stange