linux-kernel - Re: [PATCH v3] 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, 22 Jun 2021 18:03:37 +0200
From:   Thomas Gleixner <tglx@...utronix.de>
To:     Cassio Neri <cassio.neri@...il.com>, john.stultz@...aro.org
Cc:     sboyd@...nel.org, linux-kernel@...r.kernel.org,
        Cassio Neri <cassio.neri@...il.com>
Subject: Re: [PATCH v3] kernel/time: Improve performance of time64_to_tm. Add tests.

Cassio,

On Wed, Jun 02 2021 at 20:00, Cassio Neri wrote:

A few nitpicks vs. the subject line. The proper prefix is 'time:' and
please write time64_to_tm().

> 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.2 times faster (YMMV).
>
> 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

s/I reckon//

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

Add a KUnit test for it which checks every day in a 160,000 years
interval centered at 1970-01-01 against the expected result.

Changelogs should be written in imperative mood. The details about the
filename and the config symbol are not interesting for the change log.

> * Test evidence: This runs the same test implemented in
> kernel/time/time_test.c (see above). It's possible to run it on 32 and 64
> bits.
>
>     https://godbolt.org/z/1rn1aqfqY

Just that this uses XMM registers which the kernel does not. :)

> +/*
> + * Tradicional implementation of is_leap.

Traditional

Also the comment is odd. ... implementation of "is_leap" above a
function named "is_leap" !?!

You probably want to say:

    Traditional implementation of leap year evaluation.

or something like that.


>  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 u64tmp, udays, century, year;
> +	u32 u32tmp, day_of_century, year_of_century, day_of_year, month,
> +		day;
> +	bool is_Jan_or_Feb, is_leap;

Can you please reorder that so it results in a reverse fir tree:

	u64 u64tmp, udays, century, year;
	u32 u32tmp, day_of_century, year_of_century, day_of_year, month, day;
	bool is_Jan_or_Feb, is_leap;
	long days, rem;
 	int remainder;

> +
> +	udays           = ((u64) days) + 2305843009213814918ULL;

The tabulation uses spaces instead of tabs here and in various places below.

> +
> +	u64tmp          = 4 * udays + 3;
> +	century         = div64_u64_rem(u64tmp, 146097, &u64tmp);
> +	day_of_century  = (u32) (u64tmp / 4);
> +
> +	u32tmp          = 4 * day_of_century + 3;
> +	u64tmp          = 2939745ULL * u32tmp;
> +	year_of_century = upper_32_bits(u64tmp);
> +	day_of_year     = lower_32_bits(u64tmp) / 2939745 / 4;
> +
> +	year            = 100 * century + year_of_century;
> +	is_leap         = year_of_century != 0 ?
> +		year_of_century % 4 == 0 : century % 4 == 0;

This really is hard to read.

	is_leap		= year_of_century != 0 ?
			  year_of_century % 4 == 0 : century % 4 == 0;

or just:

	is_leap         = year_of_century ? !(year_of_century % 4) : !(century % 4);

That's longer than 80 characters, but that's not a really hard rule.

> +	u32tmp          = 2141 * day_of_year + 132377;
> +	month           = u32tmp >> 16;
> +	day             = ((u16) u32tmp) / 2141;
> +
> +	/* Recall that January 01 is the 306-th day of the year in the
> +	 * computational (not Gregorian) calendar.
> +	 */

        /*
         * Please format multiline comments according to regular
         * kernel codingstyle.
         */

> +	is_Jan_or_Feb   = day_of_year >= 306;
> +
> +	/* Converts to the Gregorian calendar and adjusts to Unix time. */
> +	year            = year + is_Jan_or_Feb - 6313183731940000ULL;
> +	month           = is_Jan_or_Feb ? month - 12 : month;
> +	day             = day + 1;
> +	day_of_year     = is_Jan_or_Feb ?
> +		day_of_year - 306 : day_of_year + 31 + 28 + is_leap;

See above.

Other than these nitpicks. Nice work!

Thanks,

        tglx