Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
From:   Cassio Neri <cassio.neri@gmail.com>
To:     john.stultz@linaro.org, tglx@linutronix.de
Cc:     sboyd@kernel.org, linux-kernel@vger.kernel.org,
        Cassio Neri <cassio.neri@gmail.com>
Subject: [PATCH] kernel/time: Improve performance of time64_to_tm. Add tests.
Date:   Mon, 31 May 2021 17:20:54 +0100
Message-Id: <20210531162054.45694-1-cassio.neri@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

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.

[1] Neri, Schneider, "Euclidean Affine Functions and Applications to
Calendar Algorithms". https://arxiv.org/abs/2102.06959

Signed-off-by: Cassio Neri <cassio.neri@gmail.com>

---

* Disclaimer: I'm an author of [1] and, surely, I have an interest in
seeing my algorithm made into the kernel. If not by this patch, I'm
willing to work closely with maintainers, if they wish, in order to write
an appropriate implementation.

* Benchmarks: It measures the time taken by each implementation to process
65,536 numbers. These numbers are pseudo-random under the uniform
distribution on the interval corresponding to dates spanning 800 years
centered at 1970-01-01:

    https://quick-bench.com/q/i4IssrPmwid7CHOT4OLao82sBzY

(Apologies that the benchmark is in C++ but results in C should be close.)

Disasembly: Shows, in particular, reduction in code size:

    https://godbolt.org/z/nra84xr8e

* FWIW: drivers/rtc/lib.c implements rtc_time64_to_tm very similarly to
time64_to_tm. I've submitted a patch to RTC maintainers to make similar
changes:

    https://tinyurl.com/dxsz2nv7

---
 kernel/time/Kconfig     |   9 ++++
 kernel/time/Makefile    |   1 +
 kernel/time/time_test.c |  98 ++++++++++++++++++++++++++++++++++++
 kernel/time/timeconv.c  | 108 ++++++++++++++++++++--------------------
 4 files changed, 163 insertions(+), 53 deletions(-)
 create mode 100644 kernel/time/time_test.c

diff --git a/kernel/time/Kconfig b/kernel/time/Kconfig
index 83e158d016ba..3610b1bef142 100644
--- a/kernel/time/Kconfig
+++ b/kernel/time/Kconfig
@@ -64,6 +64,15 @@ config LEGACY_TIMER_TICK
 	  lack support for the generic clockevent framework.
 	  New platforms should use generic clockevents instead.
 
+config TIME_KUNIT_TEST
+	tristate "KUnit test for kernel/time functions" if !KUNIT_ALL_TESTS
+	depends on KUNIT
+	default KUNIT_ALL_TESTS
+	help
+	  Enable this option to test RTC library functions.
+
+	  If unsure, say N.
+
 if GENERIC_CLOCKEVENTS
 menu "Timers subsystem"
 
diff --git a/kernel/time/Makefile b/kernel/time/Makefile
index 1fb1c1ef6a19..b733d09a6e4d 100644
--- a/kernel/time/Makefile
+++ b/kernel/time/Makefile
@@ -21,3 +21,4 @@ obj-$(CONFIG_HAVE_GENERIC_VDSO)			+= vsyscall.o
 obj-$(CONFIG_DEBUG_FS)				+= timekeeping_debug.o
 obj-$(CONFIG_TEST_UDELAY)			+= test_udelay.o
 obj-$(CONFIG_TIME_NS)				+= namespace.o
+obj-$(CONFIG_TIME_KUNIT_TEST)			+= time_test.o
diff --git a/kernel/time/time_test.c b/kernel/time/time_test.c
new file mode 100644
index 000000000000..7893539cb458
--- /dev/null
+++ b/kernel/time/time_test.c
@@ -0,0 +1,98 @@
+// SPDX-License-Identifier: LGPL-2.1+
+
+#include <kunit/test.h>
+#include <linux/time.h>
+
+/*
+ * Tradicional implementation of is_leap.
+ */
+static bool is_leap(long year)
+{
+	return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
+}
+
+/*
+ * Gets the last day of a month.
+ */
+static int last_day_of_month(long year, int month)
+{
+	if (month == 2)
+		return 28 + is_leap(year);
+	if (month == 4 || month == 6 || month == 9 || month == 11)
+		return 30;
+	return 31;
+}
+
+/*
+ * Advances a date by one day.
+ */
+static void advance_date(long *year, int *month, int *mday, int *yday)
+{
+	if (*mday != last_day_of_month(*year, *month)) {
+		++*mday;
+		++*yday;
+		return;
+	}
+
+	*mday = 1;
+	if (*month != 12) {
+		++*month;
+		++*yday;
+		return;
+	}
+
+	*month = 1;
+	*yday  = 0;
+	++*year;
+}
+
+/*
+ * Checks every day in a 160000 years interval centered at 1970-01-01
+ * against the expected result.
+ */
+static void time64_to_tm_test_date_range(struct kunit *test)
+{
+	/*
+	 *  80000 years = (80000 / 400) * 400 years
+	 *              = (80000 / 400) * 146097 days
+	 *              = (80000 / 400) * 146097 * 86400 seconds
+	 */
+	time64_t total_secs = ((time64_t) 80000) / 400 * 146097 * 86400;
+	long     year       = 1970 - 80000;
+	int      month      = 1;
+	int      mdday      = 1;
+	int      yday       = 0;
+
+	struct tm result;
+	time64_t  secs;
+	s64       days;
+
+	for (secs = -total_secs; secs <= total_secs; secs += 86400) {
+
+		time64_to_tm(secs, 0, &result);
+
+		days = div_s64(secs, 86400);
+
+		#define FAIL_MSG "%05ld/%02d/%02d (%2d) : %ld", \
+			year, month, mdday, yday, days
+
+		KUNIT_ASSERT_EQ_MSG(test, year - 1900, result.tm_year, FAIL_MSG);
+		KUNIT_ASSERT_EQ_MSG(test, month - 1, result.tm_mon, FAIL_MSG);
+		KUNIT_ASSERT_EQ_MSG(test, mdday, result.tm_mday, FAIL_MSG);
+		KUNIT_ASSERT_EQ_MSG(test, yday, result.tm_yday, FAIL_MSG);
+
+		advance_date(&year, &month, &mdday, &yday);
+	}
+}
+
+static struct kunit_case time_test_cases[] = {
+	KUNIT_CASE(time64_to_tm_test_date_range),
+	{}
+};
+
+static struct kunit_suite time_test_suite = {
+	.name = "time_test_cases",
+	.test_cases = time_test_cases,
+};
+
+kunit_test_suite(time_test_suite);
diff --git a/kernel/time/timeconv.c b/kernel/time/timeconv.c
index 62e3b46717a6..21ede23cd719 100644
--- a/kernel/time/timeconv.c
+++ b/kernel/time/timeconv.c
@@ -22,64 +22,53 @@
 
 /*
  * Converts the calendar time to broken-down time representation
- * Based on code from glibc-2.6
  *
  * 2009-7-14:
  *   Moved from glibc-2.6 to kernel by Zhaolei<zhaolei@cn.fujitsu.com>
+ * 2021-5-22:
+ *   Partially reimplemented by Cassio Neri <cassio.neri@gmail.com>
  */
 
 #include <linux/time.h>
 #include <linux/module.h>
 
 /*
- * Nonzero if YEAR is a leap year (every 4 years,
- * except every 100th isn't, and every 400th is).
+ * True if y is a leap year (every 4 years, except every 100th isn't, and
+ * every 400th is).
  */
-static int __isleap(long year)
+static bool is_leap(long year)
 {
-	return (year) % 4 == 0 && ((year) % 100 != 0 || (year) % 400 == 0);
+	/* This implementation is more branch-predictor friendly than the
+	 * traditional:
+	 *   return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
+	 */
+	return year % 100 != 0 ? year % 4 == 0 : year % 400 == 0;
 }
 
-/* do a mathdiv for long type */
-static long math_div(long a, long b)
-{
-	return a / b - (a % b < 0);
-}
-
-/* How many leap years between y1 and y2, y1 must less or equal to y2 */
-static long leaps_between(long y1, long y2)
-{
-	long leaps1 = math_div(y1 - 1, 4) - math_div(y1 - 1, 100)
-		+ math_div(y1 - 1, 400);
-	long leaps2 = math_div(y2 - 1, 4) - math_div(y2 - 1, 100)
-		+ math_div(y2 - 1, 400);
-	return leaps2 - leaps1;
-}
-
-/* How many days come before each month (0-12). */
-static const unsigned short __mon_yday[2][13] = {
-	/* Normal years. */
-	{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365},
-	/* Leap years. */
-	{0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366}
-};
-
 #define SECS_PER_HOUR	(60 * 60)
 #define SECS_PER_DAY	(SECS_PER_HOUR * 24)
 
-/**
- * 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.
  */
 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;
 
 	days = div_s64_rem(totalsecs, SECS_PER_DAY, &remainder);
 	rem = remainder;
@@ -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;
 
-		/* 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;
+	q2 = u2 >> 32;
+	r2 = ((u32) u2) / 2939745 / 4;
 
-	result->tm_yday = days;
+	n3 = 2141 * r2 + 197913;
+	q3 = n3 >> 16;
+	r3 = ((u16) n3) / 2141;
 
-	ip = __mon_yday[__isleap(y)];
-	for (y = 11; days < ip[y]; y--)
-		continue;
-	days -= ip[y];
+	j = r2 >= 306;
+	y = 100 * q1 + q2 + j - 6313183731940000;
+	m = j ? q3 - 12 : q3;
+	d = r3 + 1;
 
-	result->tm_mon = y;
-	result->tm_mday = days + 1;
+	result->tm_year = y - 1900;
+	result->tm_mon  = m - 1;
+	result->tm_mday = d;
+
+	/* 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);
 }
 EXPORT_SYMBOL(time64_to_tm);

base-commit: 245a057fee18be08d6ac12357463579d06bea077
-- 
2.31.0