aboutsummaryrefslogtreecommitdiff
path: root/lib/libc/tests
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libc/tests')
-rw-r--r--lib/libc/tests/stdlib/Makefile1
-rw-r--r--lib/libc/tests/stdlib/qsort_bench.c113
-rw-r--r--lib/libc/tests/stdtime/Makefile4
-rw-r--r--lib/libc/tests/stdtime/detect_tz_changes_test.c92
4 files changed, 190 insertions, 20 deletions
diff --git a/lib/libc/tests/stdlib/Makefile b/lib/libc/tests/stdlib/Makefile
index 50726a5d8af6..9d84becfbd1f 100644
--- a/lib/libc/tests/stdlib/Makefile
+++ b/lib/libc/tests/stdlib/Makefile
@@ -14,6 +14,7 @@ ATF_TESTS_C+= qsort_b_test
ATF_TESTS_C+= qsort_r_compat_test
ATF_TESTS_C+= qsort_r_test
ATF_TESTS_C+= qsort_s_test
+ATF_TESTS_C+= qsort_bench
ATF_TESTS_C+= set_constraint_handler_s_test
ATF_TESTS_C+= strfmon_test
ATF_TESTS_C+= tsearch_test
diff --git a/lib/libc/tests/stdlib/qsort_bench.c b/lib/libc/tests/stdlib/qsort_bench.c
new file mode 100644
index 000000000000..5f2cfae40140
--- /dev/null
+++ b/lib/libc/tests/stdlib/qsort_bench.c
@@ -0,0 +1,113 @@
+/*-
+ * Copyright (c) 2025 Dag-Erling Smørgrav <des@FreeBSD.org>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <atf-c.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include <unistd.h>
+
+/*-
+ * Measures qsort(3) runtime with pathological input and verify that it
+ * stays close to N * log2(N).
+ *
+ * Thanks to Vivian Hussey for the proof of concept.
+ *
+ * The input we construct is similar to a sweep from 0 to N where each
+ * half, except for the first element, has been reversed; for instance,
+ * with N = 8, we get { 0, 3, 2, 1, 4, 8, 7, 6 }. This triggers a bug in
+ * the BSD qsort(3) where it will switch to insertion sort if the pivots
+ * are sorted.
+ *
+ * This article goes into more detail about the bug and its origin:
+ *
+ * https://www.raygard.net/2022/02/26/Re-engineering-a-qsort-part-3
+ *
+ * With this optimization (the `if (swap_cnt == 0)` block), qsort(3) needs
+ * roughly N * N / 4 comparisons to sort our pathological input. Without
+ * it, it needs only a little more than N * log2(N) comparisons.
+ */
+
+/* we stop testing once a single takes longer than this */
+#define MAXRUNSECS 10
+
+static bool debugging;
+
+static uintmax_t ncmp;
+
+static int
+intcmp(const void *a, const void *b)
+{
+ ncmp++;
+ return ((*(int *)a > *(int *)b) - (*(int *)a < *(int *)b));
+}
+
+static void
+qsort_bench(int log2n)
+{
+ uintmax_t n = 1LLU << log2n;
+ int *buf;
+
+ /* fill an array with a pathological pattern */
+ ATF_REQUIRE(buf = malloc(n * sizeof(*buf)));
+ buf[0] = 0;
+ buf[n / 2] = n / 2;
+ for (unsigned int i = 1; i < n / 2; i++) {
+ buf[i] = n / 2 - i;
+ buf[n / 2 + i] = n - i;
+ }
+
+ ncmp = 0;
+ qsort(buf, n, sizeof(*buf), intcmp);
+
+ /* check result and free array */
+ if (debugging) {
+ for (unsigned int i = 1; i < n; i++) {
+ ATF_REQUIRE_MSG(buf[i] > buf[i - 1],
+ "array is not sorted");
+ }
+ }
+ free(buf);
+
+ /* check that runtime does not exceed N² */
+ ATF_CHECK_MSG(ncmp / n < n,
+ "runtime %ju exceeds N² for N = %ju", ncmp, n);
+
+ /* check that runtime does not exceed N log N by much */
+ ATF_CHECK_MSG(ncmp / n <= log2n + 1,
+ "runtime %ju exceeds N log N for N = %ju", ncmp, n);
+}
+
+ATF_TC_WITHOUT_HEAD(qsort_bench);
+ATF_TC_BODY(qsort_bench, tc)
+{
+ struct timespec t0, t1;
+ uintmax_t tus;
+
+ for (int i = 10; i <= 30; i++) {
+ clock_gettime(CLOCK_UPTIME, &t0);
+ qsort_bench(i);
+ clock_gettime(CLOCK_UPTIME, &t1);
+ tus = t1.tv_sec * 1000000 + t1.tv_nsec / 1000;
+ tus -= t0.tv_sec * 1000000 + t0.tv_nsec / 1000;
+ if (debugging) {
+ fprintf(stderr, "N = 2^%d in %ju.%06jus\n",
+ i, tus / 1000000, tus % 1000000);
+ }
+ /* stop once an individual run exceeds our limit */
+ if (tus / 1000000 >= MAXRUNSECS)
+ break;
+ }
+}
+
+ATF_TP_ADD_TCS(tp)
+{
+ debugging = !getenv("__RUNNING_INSIDE_ATF_RUN") &&
+ isatty(STDERR_FILENO);
+ ATF_TP_ADD_TC(tp, qsort_bench);
+ return (atf_no_error());
+}
diff --git a/lib/libc/tests/stdtime/Makefile b/lib/libc/tests/stdtime/Makefile
index adb883cc5b9a..6b9068e1641b 100644
--- a/lib/libc/tests/stdtime/Makefile
+++ b/lib/libc/tests/stdtime/Makefile
@@ -1,8 +1,10 @@
.include <src.opts.mk>
ATF_TESTS_C+= strptime_test
-.if ${MK_DETECT_TZ_CHANGES} != "no"
ATF_TESTS_C+= detect_tz_changes_test
+
+.if ${MK_DETECT_TZ_CHANGES} != "no"
+CFLAGS.detect_tz_changes_test+= -DDETECT_TZ_CHANGES
.endif
TESTSDIR:= ${TESTSBASE}/${RELDIR:C/libc\/tests/libc/}
diff --git a/lib/libc/tests/stdtime/detect_tz_changes_test.c b/lib/libc/tests/stdtime/detect_tz_changes_test.c
index 9722546747fd..e3fdcc0baef7 100644
--- a/lib/libc/tests/stdtime/detect_tz_changes_test.c
+++ b/lib/libc/tests/stdtime/detect_tz_changes_test.c
@@ -4,6 +4,8 @@
* SPDX-License-Identifier: BSD-2-Clause
*/
+#include <sys/param.h>
+#include <sys/conf.h>
#include <sys/stat.h>
#include <sys/wait.h>
@@ -20,7 +22,29 @@
#include <atf-c.h>
+static const struct tzcase {
+ const char *tzfn;
+ const char *expect;
+} tzcases[] = {
+ /*
+ * A handful of time zones and the expected result of
+ * strftime("%z (%Z)", tm) when that time zone is active
+ * and tm represents a date in the summer of 2025.
+ */
+ { "America/Vancouver", "-0700 (PDT)" },
+ { "America/New_York", "-0400 (EDT)" },
+ { "Europe/London", "+0100 (BST)" },
+ { "Europe/Paris", "+0200 (CEST)" },
+ { "Asia/Kolkata", "+0530 (IST)" },
+ { "Asia/Tokyo", "+0900 (JST)" },
+ { "Australia/Canberra", "+1000 (AEST)" },
+ { "UTC", "+0000 (UTC)" },
+ { 0 },
+};
+
static const time_t then = 1751328000; /* 2025-07-01 00:00:00 UTC */
+
+#ifdef DETECT_TZ_CHANGES
static const char *tz_change_interval_sym = "__tz_change_interval";
static int *tz_change_interval_p;
static const int tz_change_interval = 3;
@@ -91,25 +115,6 @@ ATF_TC_HEAD(detect_tz_changes, tc)
}
ATF_TC_BODY(detect_tz_changes, tc)
{
- static const struct tzcase {
- const char *tzfn;
- const char *expect;
- } tzcases[] = {
- /*
- * A handful of time zones and the expected result of
- * strftime("%z (%Z)", tm) when that time zone is active
- * and tm represents a date in the summer of 2025.
- */
- { "America/Vancouver", "-0700 (PDT)" },
- { "America/New_York", "-0400 (EDT)" },
- { "Europe/London", "+0100 (BST)" },
- { "Europe/Paris", "+0200 (CEST)" },
- { "Asia/Kolkata", "+0530 (IST)" },
- { "Asia/Tokyo", "+0900 (JST)" },
- { "Australia/Canberra", "+1000 (AEST)" },
- { "UTC", "+0000 (UTC)" },
- { 0 },
- };
char obuf[1024] = "";
char ebuf[1024] = "";
struct pollfd fds[3];
@@ -271,11 +276,60 @@ ATF_TC_BODY(detect_tz_changes, tc)
ATF_REQUIRE(WIFEXITED(status));
ATF_REQUIRE_EQ(0, WEXITSTATUS(status));
}
+#endif /* DETECT_TZ_CHANGES */
+
+static void
+test_tz_env(const char *tzval, const char *expect)
+{
+ char buf[128];
+ struct tm *tm;
+ size_t len;
+
+ setenv("TZ", tzval, 1);
+ ATF_REQUIRE((tm = localtime(&then)) != NULL);
+ len = strftime(buf, sizeof(buf), "%z (%Z)", tm);
+ ATF_REQUIRE(len > 0);
+ ATF_CHECK_STREQ(expect, buf);
+}
+
+ATF_TC(tz_env);
+ATF_TC_HEAD(tz_env, tc)
+{
+ atf_tc_set_md_var(tc, "descr", "Test TZ environment variable");
+}
+ATF_TC_BODY(tz_env, tc)
+{
+ const struct tzcase *tzcase;
+
+ for (tzcase = tzcases; tzcase->tzfn != NULL; tzcase++)
+ test_tz_env(tzcase->tzfn, tzcase->expect);
+}
+
+ATF_TC(tz_env_setugid);
+ATF_TC_HEAD(tz_env_setugid, tc)
+{
+ atf_tc_set_md_var(tc, "descr", "Test TZ environment variable "
+ "in setugid process");
+ atf_tc_set_md_var(tc, "require.user", "root");
+}
+ATF_TC_BODY(tz_env_setugid, tc)
+{
+ const struct tzcase *tzcase;
+
+ ATF_REQUIRE_EQ(0, seteuid(UID_NOBODY));
+ ATF_REQUIRE(issetugid());
+ for (tzcase = tzcases; tzcase->tzfn != NULL; tzcase++)
+ test_tz_env(tzcase->tzfn, tzcase->expect);
+}
ATF_TP_ADD_TCS(tp)
{
+#ifdef DETECT_TZ_CHANGES
debugging = !getenv("__RUNNING_INSIDE_ATF_RUN") &&
isatty(STDERR_FILENO);
ATF_TP_ADD_TC(tp, detect_tz_changes);
+#endif /* DETECT_TZ_CHANGES */
+ ATF_TP_ADD_TC(tp, tz_env);
+ ATF_TP_ADD_TC(tp, tz_env_setugid);
return (atf_no_error());
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-27 08:00:11 +0000