Skip to contentSkip to conversation

riscv: lib: add optimized memcmp() and extend KUnit tests

PATCH Superseded Milan Tripkovic 3 participants 5 messages May 14 – May 15

Subsystems (2)

v2 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

v2 cover riscv: lib: add optimized memcmp() and extend KUnit tests

Add an assembly implementation of memcmp() for RISC-V. This version incorporates feedback from v1 regarding alignment safety, loop efficiency, and ZBB usage.

The second patch extends the KUnit string tests to include functional verification and benchmarking for memcmp().

---
v2 changes:
- Added alignment checks for buffers to avoid expensive misaligned loads.
- Optimized the loop using end-pointers to reduce per-iteration overhead.
- Implemented word-aligned tail handling using ZBB shifts.
- Removed redundant pointer equality (a0 == a1) check.
- Retained BE support via #ifndef; ZBB rev8 is used for the LE fast-path.
- Fixed KUnit build failures for Clang and non-benchmark configs.

Milan Tripkovic (2):
riscv: lib: add memcmp() implementation lib/string_kunit: extend benchmarks and unit test to memcmp()

 arch/riscv/include/asm/string.h |   2 +
 arch/riscv/lib/Makefile         |   1 +
 arch/riscv/lib/memcmp.S         | 124 ++++++++++++++++++++++++++++++++
 arch/riscv/purgatory/Makefile   |   5 +-
 lib/tests/string_kunit.c        | 106 +++++++++++++++++++++++++++
 5 files changed, 237 insertions(+), 1 deletion(-)
 create mode 100644 arch/riscv/lib/memcmp.S
Signature · 1 line
2.43.0
#1 lore raw

PATCH v2 1/2 riscv: lib: add memcmp() implementation

From: Milan Tripkovic <[email protected]>

Add an assembly implementation of memcmp() for RISC-V. The implementation uses the ZBB extension for word-at-a-time comparison and an assembly fallback for non-ZBB systems.

Benchmark results (QEMU TCG, rv64, Aligned):

  Len   | Default | NoZBB  | ZBB    | %NoZBB | %ZBB
  ------|---------|--------|--------|--------|-------
  1 B   | 20.3    | 25.0   | 20.9   | +23.2% | +3.0%
  7 B   | 88.9    | 107.5  | 155.7  | +20.9% | +75.1%
  8 B   | 89.6    | 110.9  | 176.2  | +23.8% | +96.7%
  16 B  | 134.4   | 172.4  | 334.8  | +28.3% | +149.1%
  31 B  | 163.5   | 220.5  | 606.2  | +34.9% | +270.8%
  64 B  | 203.8   | 235.9  | 968.6  | +15.8% | +375.3%
  127 B | 224.6   | 268.7  | 1362.8 | +19.6% | +506.8%
  512 B | 235.7   | 271.1  | 1913.7 | +15.0% | +711.9%
  1024 B| 256.8   | 290.6  | 2123.6 | +13.2% | +726.9%
  4096 B| 263.8   | 302.9  | 2290.4 | +14.8% | +768.2%

Benchmark results (QEMU TCG, rv64, Unaligned - Offset 3):

  Len   | Default | NoZBB  | ZBB    | %NoZBB | %ZBB
  ------|---------|--------|--------|--------|-------
  1 B   | 20.7    | 21.7   | 21.5   | +4.8%  | +3.9%
  7 B   | 96.2    | 99.1   | 96.9   | +3.0%  | +0.7%
  8 B   | 97.5    | 118.5  | 110.5  | +21.5% | +13.3%
  16 B  | 136.7   | 166.6  | 172.8  | +21.9% | +26.4%
  31 B  | 167.6   | 206.5  | 211.9  | +23.2% | +26.4%
  64 B  | 204.4   | 229.9  | 240.3  | +12.5% | +17.6%
  127 B | 229.6   | 261.7  | 269.0  | +14.0% | +17.2%
  512 B | 245.5   | 260.8  | 269.9  | +6.2%  | +9.9%
  1024 B| 246.9   | 261.2  | 283.5  | +5.8%  | +14.8%
  4096 B| 250.7   | 295.8  | 299.7  | +18.0% | +19.5%
---
 arch/riscv/include/asm/string.h |   2 +
 arch/riscv/lib/Makefile         |   1 +
 arch/riscv/lib/memcmp.S         | 124 ++++++++++++++++++++++++++++++++
 arch/riscv/purgatory/Makefile   |   5 +-
 4 files changed, 131 insertions(+), 1 deletion(-)
 create mode 100644 arch/riscv/lib/memcmp.S
arch/riscv/include/asm/string.h +2 -0
index 764ffe8f6479..5c5299678c66 100644
@@ -18,6 +18,8 @@ extern asmlinkage void *__memcpy(void *, const void *, size_t);
 #define __HAVE_ARCH_MEMMOVE
 extern asmlinkage void *memmove(void *, const void *, size_t);
 extern asmlinkage void *__memmove(void *, const void *, size_t);
+#define __HAVE_ARCH_MEMCMP
+extern asmlinkage int memcmp(const void *, const void *, size_t);
 
 #if !(defined(CONFIG_KASAN_GENERIC) || defined(CONFIG_KASAN_SW_TAGS))
 #define __HAVE_ARCH_STRCMP
arch/riscv/lib/Makefile +1 -0
index 6f767b2a349d..b529e1be18b2 100644
@@ -3,6 +3,7 @@ lib-y			+= delay.o
 lib-y			+= memcpy.o
 lib-y			+= memset.o
 lib-y			+= memmove.o
+lib-y			+= memcmp.o
 ifeq ($(CONFIG_KASAN_GENERIC)$(CONFIG_KASAN_SW_TAGS),)
 lib-y			+= strcmp.o
 lib-y			+= strlen.o
arch/riscv/lib/memcmp.S new file +124 -0

124 lines not on this page · raw message

arch/riscv/purgatory/Makefile +4 -1
index b0358a78f11a..456929971da7 100644
@@ -1,6 +1,6 @@
 # SPDX-License-Identifier: GPL-2.0
 
-purgatory-y := purgatory.o sha256.o entry.o string.o ctype.o memcpy.o memset.o
+purgatory-y := purgatory.o sha256.o entry.o string.o ctype.o memcpy.o memset.o memcmp.o
 ifeq ($(CONFIG_KASAN_GENERIC)$(CONFIG_KASAN_SW_TAGS),)
 purgatory-y += strcmp.o strlen.o strncmp.o strnlen.o strchr.o strrchr.o
 endif
@@ -41,6 +41,9 @@ $(obj)/strchr.o: $(srctree)/arch/riscv/lib/strchr.S FORCE
 $(obj)/strrchr.o: $(srctree)/arch/riscv/lib/strrchr.S FORCE
 	$(call if_changed_rule,as_o_S)
 
+$(obj)/memcmp.o: $(srctree)/arch/riscv/lib/memcmp.S FORCE
+	$(call if_changed_rule,as_o_S)
+
 CFLAGS_sha256.o := -D__DISABLE_EXPORTS -D__NO_FORTIFY
 CFLAGS_string.o := -D__DISABLE_EXPORTS
 CFLAGS_ctype.o := -D__DISABLE_EXPORTS
Signature · 1 line
2.43.0
#2 lore raw

PATCH v2 2/2 lib/string_kunit: extend benchmarks and unit test to memcmp()

In reply to Milan Tripkovic

From: Milan Tripkovic <[email protected]>

Extend the string benchmarking suite to include memcmp(). Extend the string unit test to include memcmp().

---
 lib/tests/string_kunit.c | 106 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 106 insertions(+)
lib/tests/string_kunit.c +106 -0
index 0819ace5b027..d0bad40a719a 100644
@@ -881,6 +881,110 @@ static void string_bench_strrchr(struct kunit *test)
 	STRING_BENCH_BUF(test, buf, len, strrchr, buf, '\0');
 }
 
+static void string_test_memcmp(struct kunit *test)
+{
+	const int max_offset = 16;
+	const int max_len = 32;
+	const int buf_size = max_offset + max_len + 32;
+	u8 *buf1, *buf2;
+	int i, j, len, k;
+
+	buf1 = kunit_kzalloc(test, buf_size, GFP_KERNEL);
+	buf2 = kunit_kzalloc(test, buf_size, GFP_KERNEL);
+	KUNIT_ASSERT_NOT_ERR_OR_NULL(test, buf1);
+	KUNIT_ASSERT_NOT_ERR_OR_NULL(test, buf2);
+
+	for (i = 0; i < max_offset; i++) {
+		for (j = 0; j < max_offset; j++) {
+			for (len = 0; len <= max_len; len++) {
+				memset(buf1, 'A', buf_size);
+				memset(buf2, 'A', buf_size);
+				KUNIT_EXPECT_EQ_MSG(test, memcmp(buf1 + i, buf2 + j, len), 0,
+						    "Should be equal: i:%d j:%d len:%d", i, j, len);
+				for (k = 0; k < len; k++) {
+					memset(buf1, 'A', buf_size);
+					memset(buf2, 'A', buf_size);
+					buf2[j + k] = 'B';
+					int res = memcmp(buf1 + i, buf2 + j, len);
+
+					KUNIT_EXPECT_NE_MSG(test, res, 0,
+							    "Should detect difference at k:%d (i:%d j:%d len:%d)",
+						k, i, j, len);
+
+					if (buf1[i + k] < buf2[j + k])
+						KUNIT_EXPECT_LT(test, res, 0);
+					else
+						KUNIT_EXPECT_GT(test, res, 0);
+				}
+			}
+		}
+	}
+}
+
+#if IS_ENABLED(CONFIG_STRING_KUNIT_BENCH)
+static void string_bench_memcmp(struct kunit *test)
+{
+	char *buf1, *buf2;
+	size_t lengths[] = { 1, 7, 8, 16, 32, 64, 128, 512, 1024, 4096};
+	int offsets[] = {0, 1, 3, 7};
+	const size_t max_len = 4096 + 64;
+
+	buf1 = vmalloc(max_len);
+	buf2 = vmalloc(max_len);
+
+	if (!buf1 || !buf2) {
+		vfree(buf1);
+		vfree(buf2);
+		kunit_err(test, "vmalloc failed\n");
+		return;
+	}
+
+	memset(buf1, 'A', max_len);
+	memset(buf2, 'A', max_len);
+
+	for (int i = 0; i < 100000; i++)
+		(void)memcmp(buf1, buf2, 4096);
+
+	for (int o = 0; o < ARRAY_SIZE(offsets); o++) {
+		int off = offsets[o];
+
+		for (int i = 0; i < ARRAY_SIZE(lengths); i++) {
+			size_t len = lengths[i];
+			char *p1 = buf1;
+			char *p2 = buf2 + off;
+
+			u32 iterations = (len < 512) ? 100000 : 10000;
+
+			for (u32 j = 0; j < iterations; j++) {
+				(void)memcmp(p1, p2, len);
+				barrier();
+			}
+
+			u64 elapsed = STRING_BENCH(iterations, memcmp, p1, p2, len);
+			u64 ns_per_call = div_u64(elapsed, iterations);
+			u64 mbps = len ? div_u64((u64)len * iterations * 1000,
+									 elapsed) : 0;
+
+			if (off == 0) {
+				kunit_info(test, "bench_memcmp_aligned: len=%-4zu: %llu MB/s (%llu ns/call)\n",
+					   len, mbps, ns_per_call);
+			} else {
+				kunit_info(test, "bench_memcmp_unaligned(off=%d): len=%-4zu: %llu MB/s (%llu ns/call)\n",
+					   off, len, mbps, ns_per_call);
+			}
+		}
+	}
+
+	vfree(buf1);
+	vfree(buf2);
+}
+#else
+static void string_bench_memcmp(struct kunit *test)
+{
+	kunit_skip(test, "not enabled");
+}
+#endif
+
 static struct kunit_case string_test_cases[] = {
 	KUNIT_CASE(string_test_memset16),
 	KUNIT_CASE(string_test_memset32),
@@ -910,6 +1014,8 @@ static struct kunit_case string_test_cases[] = {
 	KUNIT_CASE(string_bench_strnlen),
 	KUNIT_CASE(string_bench_strchr),
 	KUNIT_CASE(string_bench_strrchr),
+	KUNIT_CASE(string_test_memcmp),
+	KUNIT_CASE_SLOW(string_bench_memcmp),
 	{}
 };
 
Signature · 1 line
2.43.0
maintainer
#3 lore raw

Re: [PATCH v2 2/2] lib/string_kunit: extend benchmarks and unit test to memcmp()

Quoted 49 lines · Milan Tripkovic

From: Milan Tripkovic <[email protected]>

Extend the string benchmarking suite to include memcmp(). Extend the string unit test to include memcmp().

---
 lib/tests/string_kunit.c | 106 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 106 insertions(+)
lib/tests/string_kunit.c +29 -0
index 0819ace5b027..d0bad40a719a 100644
@@ -881,6 +881,110 @@ static void string_bench_strrchr(struct kunit *test)
 	STRING_BENCH_BUF(test, buf, len, strrchr, buf, '\0');
 }
 
+static void string_test_memcmp(struct kunit *test)
+{
+	const int max_offset = 16;
+	const int max_len = 32;
+	const int buf_size = max_offset + max_len + 32;
+	u8 *buf1, *buf2;
+	int i, j, len, k;
+
+	buf1 = kunit_kzalloc(test, buf_size, GFP_KERNEL);
+	buf2 = kunit_kzalloc(test, buf_size, GFP_KERNEL);
+	KUNIT_ASSERT_NOT_ERR_OR_NULL(test, buf1);
+	KUNIT_ASSERT_NOT_ERR_OR_NULL(test, buf2);
+
+	for (i = 0; i < max_offset; i++) {
+		for (j = 0; j < max_offset; j++) {
+			for (len = 0; len <= max_len; len++) {
+				memset(buf1, 'A', buf_size);
+				memset(buf2, 'A', buf_size);
+				KUNIT_EXPECT_EQ_MSG(test, memcmp(buf1 + i, buf2 + j, len), 0,
+						    "Should be equal: i:%d j:%d len:%d", i, j, len);
+				for (k = 0; k < len; k++) {
+					memset(buf1, 'A', buf_size);
+					memset(buf2, 'A', buf_size);
+					buf2[j + k] = 'B';
+					int res = memcmp(buf1 + i, buf2 + j, len);
+
+					KUNIT_EXPECT_NE_MSG(test, res, 0,
+							    "Should detect difference at k:%d (i:%d j:%d len:%d)",
+						k, i, j, len);

lib/tests/string_kunit.c static void string_bench_strrchr(struct kunit *test) · line 922

Quoted 10 lines
lib/tests/string_kunit.c +10 -0
+
+					if (buf1[i + k] < buf2[j + k])
+						KUNIT_EXPECT_LT(test, res, 0);
+					else
+						KUNIT_EXPECT_GT(test, res, 0);
+				}
+			}
+		}
+	}
+}

This looks good, thanks!

lib/tests/string_kunit.c static void string_bench_strrchr(struct kunit *test) · line 930

Quoted 7 lines
lib/tests/string_kunit.c +7 -0
+#if IS_ENABLED(CONFIG_STRING_KUNIT_BENCH)
+static void string_bench_memcmp(struct kunit *test)
+{
+	char *buf1, *buf2;
+	size_t lengths[] = { 1, 7, 8, 16, 32, 64, 128, 512, 1024, 4096};
+	int offsets[] = {0, 1, 3, 7};
+	const size_t max_len = 4096 + 64;

I think I'd prefer, instead of a ifdef stub, to do:

if (!IS_ENABLED(CONFIG_STRING_KUNIT_BENCH))
kunit_skip(test, "CONFIG_STRING_KUNIT_BENCH not enabled")

here.

Quoted 72 lines
lib/tests/string_kunit.c +59 -0
+
+	buf1 = vmalloc(max_len);
+	buf2 = vmalloc(max_len);
+
+	if (!buf1 || !buf2) {
+		vfree(buf1);
+		vfree(buf2);
+		kunit_err(test, "vmalloc failed\n");
+		return;
+	}
+
+	memset(buf1, 'A', max_len);
+	memset(buf2, 'A', max_len);
+
+	for (int i = 0; i < 100000; i++)
+		(void)memcmp(buf1, buf2, 4096);
+
+	for (int o = 0; o < ARRAY_SIZE(offsets); o++) {
+		int off = offsets[o];
+
+		for (int i = 0; i < ARRAY_SIZE(lengths); i++) {
+			size_t len = lengths[i];
+			char *p1 = buf1;
+			char *p2 = buf2 + off;
+
+			u32 iterations = (len < 512) ? 100000 : 10000;
+
+			for (u32 j = 0; j < iterations; j++) {
+				(void)memcmp(p1, p2, len);
+				barrier();
+			}
+
+			u64 elapsed = STRING_BENCH(iterations, memcmp, p1, p2, len);
+			u64 ns_per_call = div_u64(elapsed, iterations);
+			u64 mbps = len ? div_u64((u64)len * iterations * 1000,
+									 elapsed) : 0;
+
+			if (off == 0) {
+				kunit_info(test, "bench_memcmp_aligned: len=%-4zu: %llu MB/s (%llu ns/call)\n",
+					   len, mbps, ns_per_call);
+			} else {
+				kunit_info(test, "bench_memcmp_unaligned(off=%d): len=%-4zu: %llu MB/s (%llu ns/call)\n",
+					   off, len, mbps, ns_per_call);
+			}
+		}
+	}
+
+	vfree(buf1);
+	vfree(buf2);
+}
+#else
+static void string_bench_memcmp(struct kunit *test)
+{
+	kunit_skip(test, "not enabled");
+}
+#endif
+
 static struct kunit_case string_test_cases[] = {
 	KUNIT_CASE(string_test_memset16),
 	KUNIT_CASE(string_test_memset32),
@@ -910,6 +1014,8 @@ static struct kunit_case string_test_cases[] = {
 	KUNIT_CASE(string_bench_strnlen),
 	KUNIT_CASE(string_bench_strchr),
 	KUNIT_CASE(string_bench_strrchr),
+	KUNIT_CASE(string_test_memcmp),
+	KUNIT_CASE_SLOW(string_bench_memcmp),
 	{}
 };
 
Signature · 1 line
2.43.0
Signature · 1 line
Kees Cook
#4 lore raw

Re: [PATCH v2 2/2] lib/string_kunit: extend benchmarks and unit test to memcmp()

Quoted 8 lines · Kees Cook
Quoted 7 lines · Milan Tripkovic

From: Milan Tripkovic <[email protected]>

Extend the string benchmarking suite to include memcmp(). Extend the string unit test to include memcmp().

What does this mean? The absence of the test cases won't ever be reported by LKP.

...

Quoted 9 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+#if IS_ENABLED(CONFIG_STRING_KUNIT_BENCH)
+static void string_bench_memcmp(struct kunit *test)

I think I'd prefer, instead of a ifdef stub, to do:

if (!IS_ENABLED(CONFIG_STRING_KUNIT_BENCH))
kunit_skip(test, "CONFIG_STRING_KUNIT_BENCH not enabled")

here.

What about having two functions?

static void do_test_string_bench_memcmp() // choose better name {
...
}

static void string_bench_memcmp(struct kunit *test)

{
        if (IS_ENABLED(CONFIG_STRING_KUNIT_BENCH))
                do_test_string_bench_memcmp(...);
        else
                kunit_skip(test, "CONFIG_STRING_KUNIT_BENCH not enabled");
}

...

Quoted 4 lines

lib/tests/string_kunit.c static void string_bench_strrchr(struct kunit *test) · line 951

Quoted 4 lines
lib/tests/string_kunit.c +4 -0
+     for (int o = 0; o < ARRAY_SIZE(offsets); o++) {
+             int off = offsets[o];
+
+             for (int i = 0; i < ARRAY_SIZE(lengths); i++) {

unsigned int i

Quoted 5 lines

lib/tests/string_kunit.c static void string_bench_strrchr(struct kunit *test) · line 955

Quoted 5 lines
lib/tests/string_kunit.c +4 -0
+                     size_t len = lengths[i];
+                     char *p1 = buf1;
+                     char *p2 = buf2 + off;
 
+

Redundant blank line

Quoted 10 lines

lib/tests/string_kunit.c static void string_bench_strrchr(struct kunit *test) · line 965

Quoted 10 lines
lib/tests/string_kunit.c +9 -0
+                     u32 iterations = (len < 512) ? 100000 : 10000;
+
+                     for (u32 j = 0; j < iterations; j++) {
+                             (void)memcmp(p1, p2, len);
+                             barrier();
+                     }
 
+                     u64 elapsed = STRING_BENCH(iterations, memcmp, p1, p2, len);
+                     u64 ns_per_call = div_u64(elapsed, iterations);
+                     u64 mbps = len ? div_u64((u64)len * iterations * 1000,

Instead of casting just make iterations to be u64.

                     mbps = len ? div_u64(iterations * 1000 * len,
Quoted 1 line
Quoted 1 line

+ elapsed) : 0;

We don't usually allow the C99 definition initialisers inside the code, even for tests.

(With that the last will be a single line.)

Quoted 9 lines
Quoted 9 lines
lib/tests/string_kunit.c +9 -0
+                     if (off == 0) {
+                             kunit_info(test, "bench_memcmp_aligned: len=%-4zu: %llu MB/s (%llu ns/call)\n",
+                                        len, mbps, ns_per_call);
+                     } else {
+                             kunit_info(test, "bench_memcmp_unaligned(off=%d): len=%-4zu: %llu MB/s (%llu ns/call)\n",
+                                        off, len, mbps, ns_per_call);
+                     }
+             }
+     }
Signature · 2 lines
With Best Regards,
Andy Shevchenko