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

Groups > linux.kernel > #1471202 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC v4 13/22] clockevents: check a programmed delta's bounds in terms of cycles Nicolai Stange <nicstange@gmail.com> - 2016-08-27 17:30 +0200
    Re: [RFC v4 13/22] clockevents: check a programmed delta's bounds in terms of cycles Nicolai Stange <nicstange@gmail.com> - 2016-08-31 10:40 +0200

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

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


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

[toc] | [next] | [standalone]

#1473187

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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web