linux-kernel - Re: [PATCH] kernel/time: Improve performance of time64_to

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:   Tue, 01 Jun 2021 08:44:01 -0700
From:   Joe Perches <joe@...ches.com>
To:     Cassio Neri <cassio.neri@...il.com>, john.stultz@...aro.org,
        tglx@...utronix.de
Cc:     sboyd@...nel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] kernel/time: Improve performance of time64_to_tm. Add
 tests.

On Mon, 2021-05-31 at 17:20 +0100, Cassio Neri wrote:
> The current implementation of time64_to_tm contains unnecessary loops,
> branches and look-up tables. The new one uses an arithmetic-based algorithm
> appeared in [1] and is ~3.3 times faster.
> 
> The drawback is that the new code isn't intuitive and contains many 'magic
> numbers' (not unusual for this type of algorithm). However, [1] justifies
> all those numbers and, given this function's history, I reckon the code is
> unlikely to need much maintenance, if any at all.
> 
> Added file kernel/time/time_test.c containing a KUnit test case that checks
> every day in a 160,000 years interval centered at 1970-01-01 against the
> expected result. A new config TIME_KUNIT_TEST symbol was introduced to
> give the option to run this test suite.

Apologies for the previous blank reply.

> diff --git a/kernel/time/timeconv.c b/kernel/time/timeconv.c
[]
> -/**
> - * time64_to_tm - converts the calendar time to local broken-down time
> +/*
> + * This function converts time64_t to rtc_time.
>   *
> - * @totalsecs:	the number of seconds elapsed since 00:00:00 on January 1, 1970,
> - *		Coordinated Universal Time (UTC).
> - * @offset:	offset seconds adding to totalsecs.
> - * @result:	pointer to struct tm variable to receive broken-down time
> + * @param[in]  totalsecs   The number of seconds since 01-01-1970 00:00:00.
> + * @param[in]  offset      Seconds added to totalsecs.
> + * @param[out] result      Pointer to struct tm variable to receive
> + *                         broken-down time.
>   */

Please do not change this header.
This is kernel-doc and you remove it.

>  void time64_to_tm(time64_t totalsecs, int offset, struct tm *result)
>  {
> -	long days, rem, y;
> +	long days, rem;
>  	int remainder;
> -	const unsigned short *ip;
> +
> +	u64 r0, n1, q1, u64rem;
> +	u32 r1, n2, q2, r2;
> +	u64 u2;
> +	u32 n3, q3, r3;
> +
> +	u32 j;
> +	u64 y;
> +	u32 m, d;

Perhaps use more descriptive naming.

> @@ -103,27 +92,40 @@ void time64_to_tm(time64_t totalsecs, int offset, struct tm *result)
>  	if (result->tm_wday < 0)
>  		result->tm_wday += 7;
>  
> 
> -	y = 1970;
> +	/*
> +	 * The following algorithm is Proposition 6.3 of Neri and Schneider,
> +	 * "Euclidean Affine Functions and Applications to Calendar Algorithms".
> +	 * https://arxiv.org/abs/2102.06959
> +	 */
>  
> 
> -	while (days < 0 || days >= (__isleap(y) ? 366 : 365)) {
> -		/* Guess a corrected year, assuming 365 days per year. */
> -		long yg = y + math_div(days, 365);
> +	r0 = days + 2305843009213814918;

Please use appropriate ULL markers for values >= 1<<32
and compile test using 32 bit compilers as most will emit
warnings for these values.

Also it might be useful to post test results for 32 bit compilers.
>  
> 
> -		/* Adjust DAYS and Y to match the guessed year. */
> -		days -= (yg - y) * 365 + leaps_between(y, yg);
> -		y = yg;
> -	}
> +	n1 = 4 * r0 + 3;
> +	q1 = div64_u64_rem(n1, 146097, &u64rem);
> +	r1 = u64rem / 4;
>  
> -	result->tm_year = y - 1900;
> +	n2 = 4 * r1 + 3;
> +	u2 = ((u64) 2939745) * n2;

It seems odd to cast numeric constants.

> +	/* r2 contains the number of days since previous Mar 1st and j == true
> +	 * if and only if month is Jan or Feb. The bellow is then a correction
> +	 * to get the numbers of days since previous Jan 1st.
> +	 */
> +	result->tm_yday = j ? r2 - 306 : r2 + 59 + is_leap(y);

Perhaps more readable to let the compiler create 306 and 59 by using
365, 31 and 28