From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1759513AbcHaIb5 (ORCPT ); Wed, 31 Aug 2016 04:31:57 -0400 Received: from mail-wm0-f45.google.com ([74.125.82.45]:37853 "EHLO mail-wm0-f45.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1758387AbcHaIbQ (ORCPT ); Wed, 31 Aug 2016 04:31:16 -0400 From: Nicolai Stange To: Thomas Gleixner Cc: Nicolai Stange , John Stultz , linux-kernel@vger.kernel.org Subject: Re: [RFC v4 13/22] clockevents: check a programmed delta's bounds in terms of cycles References: <20160822233320.4548-1-nicstange@gmail.com> <20160822233320.4548-14-nicstange@gmail.com> <874m66z1aa.fsf@gmail.com> Date: Wed, 31 Aug 2016 10:31:13 +0200 In-Reply-To: <874m66z1aa.fsf@gmail.com> (Nicolai Stange's message of "Sat, 27 Aug 2016 17:20:29 +0200") Message-ID: <87a8ftqqzy.fsf@gmail.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Nicolai Stange writes: > Nicolai Stange 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