aboutsummaryrefslogtreecommitdiff
path: root/test/unit/bit_util.c
diff options
context:
space:
mode:
authorWarner Losh <imp@FreeBSD.org>2025-02-05 23:20:13 +0000
committerWarner Losh <imp@FreeBSD.org>2025-02-05 23:20:13 +0000
commit48ec896efb0b78141df004eaa21288b84590c9da (patch)
tree33799792fd95c266d472ab1ae51d50ab4f942eb3 /test/unit/bit_util.c
parentd28d7fbede216494aa3942af042cc084fcd6098a (diff)
jemalloc: Import 5.3.0 54eaed1d8b56b1aa528be3bdd1877e59c56fa90cvendor/jemalloc/5.3.0vendor/jemalloc
Import jemalloc 5.3.0. This import changes how manage the jemalloc vendor branch (which was just started anyway). Starting with 5.3.0, we import a clean tree from the upstream github, removing all the old files that are no longer upstream, or that we've kept around for some reason. We do this because we merge from this raw version of jemalloc into the FreeBSD contrib/jemalloc, then we run autogen stuff, generate all the generated .h files with gmake, then finally remove much of the generated files in contrib/jemalloc using an update script. Sponsored by: Netflix
Diffstat (limited to 'test/unit/bit_util.c')
-rw-r--r--test/unit/bit_util.c254
1 files changed, 225 insertions, 29 deletions
diff --git a/test/unit/bit_util.c b/test/unit/bit_util.c
index b747deb433c9..7d31b2109233 100644
--- a/test/unit/bit_util.c
+++ b/test/unit/bit_util.c
@@ -6,27 +6,27 @@
unsigned i, pow2; \
t x; \
\
- assert_##suf##_eq(pow2_ceil_##suf(0), 0, "Unexpected result"); \
+ expect_##suf##_eq(pow2_ceil_##suf(0), 0, "Unexpected result"); \
\
for (i = 0; i < sizeof(t) * 8; i++) { \
- assert_##suf##_eq(pow2_ceil_##suf(((t)1) << i), ((t)1) \
+ expect_##suf##_eq(pow2_ceil_##suf(((t)1) << i), ((t)1) \
<< i, "Unexpected result"); \
} \
\
for (i = 2; i < sizeof(t) * 8; i++) { \
- assert_##suf##_eq(pow2_ceil_##suf((((t)1) << i) - 1), \
+ expect_##suf##_eq(pow2_ceil_##suf((((t)1) << i) - 1), \
((t)1) << i, "Unexpected result"); \
} \
\
for (i = 0; i < sizeof(t) * 8 - 1; i++) { \
- assert_##suf##_eq(pow2_ceil_##suf((((t)1) << i) + 1), \
+ expect_##suf##_eq(pow2_ceil_##suf((((t)1) << i) + 1), \
((t)1) << (i+1), "Unexpected result"); \
} \
\
for (pow2 = 1; pow2 < 25; pow2++) { \
for (x = (((t)1) << (pow2-1)) + 1; x <= ((t)1) << pow2; \
x++) { \
- assert_##suf##_eq(pow2_ceil_##suf(x), \
+ expect_##suf##_eq(pow2_ceil_##suf(x), \
((t)1) << pow2, \
"Unexpected result, x=%"pri, x); \
} \
@@ -49,35 +49,35 @@ TEST_BEGIN(test_pow2_ceil_zu) {
TEST_END
void
-assert_lg_ceil_range(size_t input, unsigned answer) {
+expect_lg_ceil_range(size_t input, unsigned answer) {
if (input == 1) {
- assert_u_eq(0, answer, "Got %u as lg_ceil of 1", answer);
+ expect_u_eq(0, answer, "Got %u as lg_ceil of 1", answer);
return;
}
- assert_zu_le(input, (ZU(1) << answer),
+ expect_zu_le(input, (ZU(1) << answer),
"Got %u as lg_ceil of %zu", answer, input);
- assert_zu_gt(input, (ZU(1) << (answer - 1)),
+ expect_zu_gt(input, (ZU(1) << (answer - 1)),
"Got %u as lg_ceil of %zu", answer, input);
}
void
-assert_lg_floor_range(size_t input, unsigned answer) {
+expect_lg_floor_range(size_t input, unsigned answer) {
if (input == 1) {
- assert_u_eq(0, answer, "Got %u as lg_floor of 1", answer);
+ expect_u_eq(0, answer, "Got %u as lg_floor of 1", answer);
return;
}
- assert_zu_ge(input, (ZU(1) << answer),
+ expect_zu_ge(input, (ZU(1) << answer),
"Got %u as lg_floor of %zu", answer, input);
- assert_zu_lt(input, (ZU(1) << (answer + 1)),
+ expect_zu_lt(input, (ZU(1) << (answer + 1)),
"Got %u as lg_floor of %zu", answer, input);
}
TEST_BEGIN(test_lg_ceil_floor) {
for (size_t i = 1; i < 10 * 1000 * 1000; i++) {
- assert_lg_ceil_range(i, lg_ceil(i));
- assert_lg_ceil_range(i, LG_CEIL(i));
- assert_lg_floor_range(i, lg_floor(i));
- assert_lg_floor_range(i, LG_FLOOR(i));
+ expect_lg_ceil_range(i, lg_ceil(i));
+ expect_lg_ceil_range(i, LG_CEIL(i));
+ expect_lg_floor_range(i, lg_floor(i));
+ expect_lg_floor_range(i, LG_FLOOR(i));
}
for (int i = 10; i < 8 * (1 << LG_SIZEOF_PTR) - 5; i++) {
for (size_t j = 0; j < (1 << 4); j++) {
@@ -85,27 +85,223 @@ TEST_BEGIN(test_lg_ceil_floor) {
- j * ((size_t)1 << (i - 4));
size_t num2 = ((size_t)1 << i)
+ j * ((size_t)1 << (i - 4));
- assert_zu_ne(num1, 0, "Invalid lg argument");
- assert_zu_ne(num2, 0, "Invalid lg argument");
- assert_lg_ceil_range(num1, lg_ceil(num1));
- assert_lg_ceil_range(num1, LG_CEIL(num1));
- assert_lg_ceil_range(num2, lg_ceil(num2));
- assert_lg_ceil_range(num2, LG_CEIL(num2));
+ expect_zu_ne(num1, 0, "Invalid lg argument");
+ expect_zu_ne(num2, 0, "Invalid lg argument");
+ expect_lg_ceil_range(num1, lg_ceil(num1));
+ expect_lg_ceil_range(num1, LG_CEIL(num1));
+ expect_lg_ceil_range(num2, lg_ceil(num2));
+ expect_lg_ceil_range(num2, LG_CEIL(num2));
- assert_lg_floor_range(num1, lg_floor(num1));
- assert_lg_floor_range(num1, LG_FLOOR(num1));
- assert_lg_floor_range(num2, lg_floor(num2));
- assert_lg_floor_range(num2, LG_FLOOR(num2));
+ expect_lg_floor_range(num1, lg_floor(num1));
+ expect_lg_floor_range(num1, LG_FLOOR(num1));
+ expect_lg_floor_range(num2, lg_floor(num2));
+ expect_lg_floor_range(num2, LG_FLOOR(num2));
}
}
}
TEST_END
+#define TEST_FFS(t, suf, test_suf, pri) do { \
+ for (unsigned i = 0; i < sizeof(t) * 8; i++) { \
+ for (unsigned j = 0; j <= i; j++) { \
+ for (unsigned k = 0; k <= j; k++) { \
+ t x = (t)1 << i; \
+ x |= (t)1 << j; \
+ x |= (t)1 << k; \
+ expect_##test_suf##_eq(ffs_##suf(x), k, \
+ "Unexpected result, x=%"pri, x); \
+ } \
+ } \
+ } \
+} while(0)
+
+TEST_BEGIN(test_ffs_u) {
+ TEST_FFS(unsigned, u, u,"u");
+}
+TEST_END
+
+TEST_BEGIN(test_ffs_lu) {
+ TEST_FFS(unsigned long, lu, lu, "lu");
+}
+TEST_END
+
+TEST_BEGIN(test_ffs_llu) {
+ TEST_FFS(unsigned long long, llu, qd, "llu");
+}
+TEST_END
+
+TEST_BEGIN(test_ffs_u32) {
+ TEST_FFS(uint32_t, u32, u32, FMTu32);
+}
+TEST_END
+
+TEST_BEGIN(test_ffs_u64) {
+ TEST_FFS(uint64_t, u64, u64, FMTu64);
+}
+TEST_END
+
+TEST_BEGIN(test_ffs_zu) {
+ TEST_FFS(size_t, zu, zu, "zu");
+}
+TEST_END
+
+#define TEST_FLS(t, suf, test_suf, pri) do { \
+ for (unsigned i = 0; i < sizeof(t) * 8; i++) { \
+ for (unsigned j = 0; j <= i; j++) { \
+ for (unsigned k = 0; k <= j; k++) { \
+ t x = (t)1 << i; \
+ x |= (t)1 << j; \
+ x |= (t)1 << k; \
+ expect_##test_suf##_eq(fls_##suf(x), i, \
+ "Unexpected result, x=%"pri, x); \
+ } \
+ } \
+ } \
+} while(0)
+
+TEST_BEGIN(test_fls_u) {
+ TEST_FLS(unsigned, u, u,"u");
+}
+TEST_END
+
+TEST_BEGIN(test_fls_lu) {
+ TEST_FLS(unsigned long, lu, lu, "lu");
+}
+TEST_END
+
+TEST_BEGIN(test_fls_llu) {
+ TEST_FLS(unsigned long long, llu, qd, "llu");
+}
+TEST_END
+
+TEST_BEGIN(test_fls_u32) {
+ TEST_FLS(uint32_t, u32, u32, FMTu32);
+}
+TEST_END
+
+TEST_BEGIN(test_fls_u64) {
+ TEST_FLS(uint64_t, u64, u64, FMTu64);
+}
+TEST_END
+
+TEST_BEGIN(test_fls_zu) {
+ TEST_FLS(size_t, zu, zu, "zu");
+}
+TEST_END
+
+TEST_BEGIN(test_fls_u_slow) {
+ TEST_FLS(unsigned, u_slow, u,"u");
+}
+TEST_END
+
+TEST_BEGIN(test_fls_lu_slow) {
+ TEST_FLS(unsigned long, lu_slow, lu, "lu");
+}
+TEST_END
+
+TEST_BEGIN(test_fls_llu_slow) {
+ TEST_FLS(unsigned long long, llu_slow, qd, "llu");
+}
+TEST_END
+
+static unsigned
+popcount_byte(unsigned byte) {
+ int count = 0;
+ for (int i = 0; i < 8; i++) {
+ if ((byte & (1 << i)) != 0) {
+ count++;
+ }
+ }
+ return count;
+}
+
+static uint64_t
+expand_byte_to_mask(unsigned byte) {
+ uint64_t result = 0;
+ for (int i = 0; i < 8; i++) {
+ if ((byte & (1 << i)) != 0) {
+ result |= ((uint64_t)0xFF << (i * 8));
+ }
+ }
+ return result;
+}
+
+#define TEST_POPCOUNT(t, suf, pri_hex) do { \
+ t bmul = (t)0x0101010101010101ULL; \
+ for (unsigned i = 0; i < (1 << sizeof(t)); i++) { \
+ for (unsigned j = 0; j < 256; j++) { \
+ /* \
+ * Replicate the byte j into various \
+ * bytes of the integer (as indicated by the \
+ * mask in i), and ensure that the popcount of \
+ * the result is popcount(i) * popcount(j) \
+ */ \
+ t mask = (t)expand_byte_to_mask(i); \
+ t x = (bmul * j) & mask; \
+ expect_u_eq( \
+ popcount_byte(i) * popcount_byte(j), \
+ popcount_##suf(x), \
+ "Unexpected result, x=0x%"pri_hex, x); \
+ } \
+ } \
+} while (0)
+
+TEST_BEGIN(test_popcount_u) {
+ TEST_POPCOUNT(unsigned, u, "x");
+}
+TEST_END
+
+TEST_BEGIN(test_popcount_u_slow) {
+ TEST_POPCOUNT(unsigned, u_slow, "x");
+}
+TEST_END
+
+TEST_BEGIN(test_popcount_lu) {
+ TEST_POPCOUNT(unsigned long, lu, "lx");
+}
+TEST_END
+
+TEST_BEGIN(test_popcount_lu_slow) {
+ TEST_POPCOUNT(unsigned long, lu_slow, "lx");
+}
+TEST_END
+
+TEST_BEGIN(test_popcount_llu) {
+ TEST_POPCOUNT(unsigned long long, llu, "llx");
+}
+TEST_END
+
+TEST_BEGIN(test_popcount_llu_slow) {
+ TEST_POPCOUNT(unsigned long long, llu_slow, "llx");
+}
+TEST_END
+
int
main(void) {
- return test(
+ return test_no_reentrancy(
test_pow2_ceil_u64,
test_pow2_ceil_u32,
test_pow2_ceil_zu,
- test_lg_ceil_floor);
+ test_lg_ceil_floor,
+ test_ffs_u,
+ test_ffs_lu,
+ test_ffs_llu,
+ test_ffs_u32,
+ test_ffs_u64,
+ test_ffs_zu,
+ test_fls_u,
+ test_fls_lu,
+ test_fls_llu,
+ test_fls_u32,
+ test_fls_u64,
+ test_fls_zu,
+ test_fls_u_slow,
+ test_fls_lu_slow,
+ test_fls_llu_slow,
+ test_popcount_u,
+ test_popcount_u_slow,
+ test_popcount_lu,
+ test_popcount_lu_slow,
+ test_popcount_llu,
+ test_popcount_llu_slow);
}
generated by cgit v1.3 (git 2.53.0) at 2026-09-12 02:23:01 +0000