lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Tue, 7 Oct 2014 16:19:42 0700 From: Greg KroahHartman <gregkh@...uxfoundation.org> To: linuxkernel@...r.kernel.org Cc: Greg KroahHartman <gregkh@...uxfoundation.org>, stable@...r.kernel.org, Thomas Gleixner <tglx@...utronix.de>, Ingo Molnar <mingo@...hat.com>, Paul Turner <pjt@...gle.com>, Richard Cochran <richardcochran@...il.com>, Prarit Bhargava <prarit@...hat.com>, Aaron Jacobs <jacobsa@...gle.com>, Andrew Hunter <ahh@...gle.com>, John Stultz <john.stultz@...aro.org>, Ben Hutchings <ben@...adent.org.uk> Subject: [PATCH 3.16 26/26] jiffies: Fix timeval conversion to jiffies 3.16stable review patch. If anyone has any objections, please let me know.  From: Andrew Hunter <ahh@...gle.com> commit d78c9300c51d6ceed9f6d078d4e9366f259de28c upstream. timeval_to_jiffies tried to round a timeval up to an integral number of jiffies, but the logic for doing so was incorrect: intervals corresponding to exactly N jiffies would become N+1. This manifested itself particularly repeatedly stopping/starting an itimer: setitimer(ITIMER_PROF, &val, NULL); setitimer(ITIMER_PROF, NULL, &val); would add a full tick to val, _even if it was exactly representable in terms of jiffies_ (say, the result of a previous rounding.) Doing this repeatedly would cause unbounded growth in val. So fix the math. Here's what was wrong with the conversion: we essentially computed (eliding seconds) jiffies = usec * (NSEC_PER_USEC/TICK_NSEC) by using scaling arithmetic, which took the best approximation of NSEC_PER_USEC/TICK_NSEC with denominator of 2^USEC_JIFFIE_SC = x/(2^USEC_JIFFIE_SC), and computed: jiffies = (usec * x) >> USEC_JIFFIE_SC and rounded this calculation up in the intermediate form (since we can't necessarily exactly represent TICK_NSEC in usec.) But the scaling arithmetic is a (very slight) *over*approximation of the true value; that is, instead of dividing by (1 usec/ 1 jiffie), we effectively divided by (1 usec/1 jiffie)epsilon (rounding down). This would normally be fine, but we want to round timeouts up, and we did so by adding 2^USEC_JIFFIE_SC  1 before the shift; this would be fine if our division was exact, but dividing this by the slightly smaller factor was equivalent to adding just _over_ 1 to the final result (instead of just _under_ 1, as desired.) In particular, with HZ=1000, we consistently computed that 10000 usec was 11 jiffies; the same was true for any exact multiple of TICK_NSEC. We could possibly still round in the intermediate form, adding something less than 2^USEC_JIFFIE_SC  1, but easier still is to convert usec>nsec, round in nanoseconds, and then convert using time*spec*_to_jiffies. This adds one constant multiplication, and is not observably slower in microbenchmarks on recent x86 hardware. Tested: the following program: int main() { struct itimerval zero = {{0, 0}, {0, 0}}; /* Initially set to 10 ms. */ struct itimerval initial = zero; initial.it_interval.tv_usec = 10000; setitimer(ITIMER_PROF, &initial, NULL); /* Save and restore several times. */ for (size_t i = 0; i < 10; ++i) { struct itimerval prev; setitimer(ITIMER_PROF, &zero, &prev); /* on old kernels, this goes up by TICK_USEC every iteration */ printf("previous value: %ld %ld %ld %ld\n", prev.it_interval.tv_sec, prev.it_interval.tv_usec, prev.it_value.tv_sec, prev.it_value.tv_usec); setitimer(ITIMER_PROF, &prev, NULL); } return 0; } Cc: Thomas Gleixner <tglx@...utronix.de> Cc: Ingo Molnar <mingo@...hat.com> Cc: Paul Turner <pjt@...gle.com> Cc: Richard Cochran <richardcochran@...il.com> Cc: Prarit Bhargava <prarit@...hat.com> Reviewedby: Paul Turner <pjt@...gle.com> Reportedby: Aaron Jacobs <jacobsa@...gle.com> Signedoffby: Andrew Hunter <ahh@...gle.com> [jstultz: Tweaked to apply to 3.17rc] Signedoffby: John Stultz <john.stultz@...aro.org> [bwh: Backported to 3.16: adjust filename] Signedoffby: Ben Hutchings <ben@...adent.org.uk> Signedoffby: Greg KroahHartman <gregkh@...uxfoundation.org>  include/linux/jiffies.h  12  kernel/time.c  54 ++++++++++++++++++++++++++ 2 files changed, 30 insertions(+), 36 deletions()  a/include/linux/jiffies.h +++ b/include/linux/jiffies.h @@ 258,23 +258,11 @@ extern unsigned long preset_lpj; #define SEC_JIFFIE_SC (32  SHIFT_HZ) #endif #define NSEC_JIFFIE_SC (SEC_JIFFIE_SC + 29) #define USEC_JIFFIE_SC (SEC_JIFFIE_SC + 19) #define SEC_CONVERSION ((unsigned long)((((u64)NSEC_PER_SEC << SEC_JIFFIE_SC) +\ TICK_NSEC 1) / (u64)TICK_NSEC)) #define NSEC_CONVERSION ((unsigned long)((((u64)1 << NSEC_JIFFIE_SC) +\ TICK_NSEC 1) / (u64)TICK_NSEC)) #define USEC_CONVERSION \  ((unsigned long)((((u64)NSEC_PER_USEC << USEC_JIFFIE_SC) +\  TICK_NSEC 1) / (u64)TICK_NSEC)) /*  * USEC_ROUND is used in the timeval to jiffie conversion. See there  * for more details. It is the scaled resolution rounding value. Note  * that it is a 64bit value. Since, when it is applied, we are already  * in jiffies (albit scaled), it is nothing but the bits we will shift  * off.  */ #define USEC_ROUND (u64)(((u64)1 << USEC_JIFFIE_SC)  1) /* * The maximum jiffie value is (MAX_INT >> 1). Here we translate that * into seconds. The 64bit case will overflow if we are not careful,  a/kernel/time.c +++ b/kernel/time.c @@ 496,17 +496,20 @@ EXPORT_SYMBOL(usecs_to_jiffies); * that a remainder subtract here would not do the right thing as the * resolution values don't fall on second boundries. I.e. the line: * nsec = nsec % TICK_NSEC; is NOT a correct resolution rounding. + * Note that due to the small error in the multiplier here, this + * rounding is incorrect for sufficiently large values of tv_nsec, but + * well formed timespecs should have tv_nsec < NSEC_PER_SEC, so we're + * OK. * * Rather, we just shift the bits off the right. * * The >> (NSEC_JIFFIE_SC  SEC_JIFFIE_SC) converts the scaled nsec * value to a scaled second value. */ unsigned long timespec_to_jiffies(const struct timespec *value) +static unsigned long +__timespec_to_jiffies(unsigned long sec, long nsec) {  unsigned long sec = value>tv_sec;  long nsec = value>tv_nsec + TICK_NSEC  1; + nsec = nsec + TICK_NSEC  1; if (sec >= MAX_SEC_IN_JIFFIES){ sec = MAX_SEC_IN_JIFFIES; @@ 517,6 +520,13 @@ timespec_to_jiffies(const struct timespe (NSEC_JIFFIE_SC  SEC_JIFFIE_SC))) >> SEC_JIFFIE_SC; } + +unsigned long +timespec_to_jiffies(const struct timespec *value) +{ + return __timespec_to_jiffies(value>tv_sec, value>tv_nsec); +} + EXPORT_SYMBOL(timespec_to_jiffies); void @@ 533,31 +543,27 @@ jiffies_to_timespec(const unsigned long } EXPORT_SYMBOL(jiffies_to_timespec); /* Same for "timeval" +/* + * We could use a similar algorithm to timespec_to_jiffies (with a + * different multiplier for usec instead of nsec). But this has a + * problem with rounding: we can't exactly add TICK_NSEC  1 to the + * usec value, since it's not necessarily integral. + * + * We could instead round in the intermediate scaled representation + * (i.e. in units of 1/2^(large scale) jiffies) but that's also + * perilous: the scaling introduces a small positive error, which + * combined with a divisionroundingupward (i.e. adding 2^(scale)  1 + * units to the intermediate before shifting) leads to accidental + * overflow and overestimates. *  * Well, almost. The problem here is that the real system resolution is  * in nanoseconds and the value being converted is in micro seconds.  * Also for some machines (those that use HZ = 1024, inparticular),  * there is a LARGE error in the tick size in microseconds.   * The solution we use is to do the rounding AFTER we convert the  * microsecond part. Thus the USEC_ROUND, the bits to be shifted off.  * Instruction wise, this should cost only an additional add with carry  * instruction above the way it was done above. + * At the cost of one additional multiplication by a constant, just + * use the timespec implementation. */ unsigned long timeval_to_jiffies(const struct timeval *value) {  unsigned long sec = value>tv_sec;  long usec = value>tv_usec;   if (sec >= MAX_SEC_IN_JIFFIES){  sec = MAX_SEC_IN_JIFFIES;  usec = 0;  }  return (((u64)sec * SEC_CONVERSION) +  (((u64)usec * USEC_CONVERSION + USEC_ROUND) >>  (USEC_JIFFIE_SC  SEC_JIFFIE_SC))) >> SEC_JIFFIE_SC; + return __timespec_to_jiffies(value>tv_sec, + value>tv_usec * NSEC_PER_USEC); } EXPORT_SYMBOL(timeval_to_jiffies);  To unsubscribe from this list: send the line "unsubscribe linuxkernel" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomoinfo.html Please read the FAQ at http://www.tux.org/lkml/
Powered by blists  more mailing lists