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

[Nicolai Stange <nicstange@gmail.com>]

Nicolai Stange <nicstange@gmail.com> writes:
> Nicolai Stange <nicstange@gmail.com> 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...

I thought a little bit more about this: having that cut-off point for
the adjusted mult is probably the right thing to do. Reasoning: In order
to avoid the overflows, the sum

  ilog2(max_delta_ns) + ilog2(mult_adjusted)

should be kept bounded from above by some fixed value (this is how
clockevents_config() calculates the proper ->shift value).

Now, if mult_adjusted crossed the cut-off point,
i.e. ilog2(mult_adjusted) increased by one, then I would have no choice
other than setting ->max_delta_ns >>= 1.

Given that the whole purpose of this series is to avoid too early timer
interrupts for large deltas, this would be a strange thing to do.


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

Since the "cut-off point of mult_adjusted is messy" argument is gone
now, I won't do this. So, if you don't object in the meanwhile, v5 will
have both, ->max_delta_ns *and* ->max_delta_ticks. This trades the
reduced complexity of not having to schedule the update everywhere
against an extra min() in the ced programming path.

Thanks,

Nicolai Stange