riscv: optimized mem* functions

+++ b/arch/riscv/lib/string.c

+#include <linux/module.h>

Sent: 21 June 2021 15:27

arch/riscv/lib/string.c line 56

Quoted 1 line

arch/riscv/lib/string.c new file +1 -0

+		for (next = s.ulong[0]; count >= bytes_long + mask; count -= bytes_long) {

Please avoid the pointlessly overlong line. And (just as a matter of personal preference) I find for loop that don't actually use a single iterator rather confusing. Wjy not simply:

		next = s.ulong[0];
		while (count >= bytes_long + mask) {
			...
			count -= bytes_long;
		}

From: Christoph Hellwig

Quoted 1 line

Sent: 21 June 2021 15:27

...

Quoted 11 lines

Quoted 1 line

+ for (next = s.ulong[0]; count >= bytes_long + mask; count -= bytes_long) {

Please avoid the pointlessly overlong line. And (just as a matter of personal preference) I find for loop that don't actually use a single iterator rather confusing. Wjy not simply:

              next = s.ulong[0];
              while (count >= bytes_long + mask) {
                      ...
                      count -= bytes_long;
              }

My fist attack on long 'for' statements is just to move the initialisation to the previous line.
Then make sure there is nothing in the comparison that needs to be calculated every iteration.
I suspect you can subtract 'mask' from 'count'. Giving:

                count -= mask;
                next = s.ulong[0];
                for (;; count > bytes_long; count -= bytes_long) {

Next is to shorten the variable names!

David

arch/riscv/include/asm/string.h line 19

Quoted 2 lines · Matteo Croce

arch/riscv/include/asm/string.h +2 -0

+extern void *memcpy(void *dest, const void *src, size_t count);
+extern void *__memcpy(void *dest, const void *src, size_t count);

No need for externs.

Quoted 1 line

+++ b/arch/riscv/lib/string.c

Nothing in her looks RISC-V specific. Why doesn't this go into lib/ so that other architectures can use it as well.

Quoted 1 line

+#include <linux/module.h>

I think you only need export.h.

arch/riscv/lib/string.c line 38

Quoted 12 lines

arch/riscv/lib/string.c new file +12 -0

+void *__memcpy(void *dest, const void *src, size_t count)
+{
+     const int bytes_long = BITS_PER_LONG / 8;
+#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+     const int mask = bytes_long - 1;
+     const int distance = (src - dest) & mask;
+#endif
+     union const_types s = { .u8 = src };
+     union types d = { .u8 = dest };
+
+#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+     if (count < MIN_THRESHOLD)

Using IS_ENABLED we can avoid a lot of the mess in this function.

        int distance = 0;

        if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)) {
                if (count < MIN_THRESHOLD)
                        goto copy_remainder;

                /* copy a byte at time until destination is aligned */
                for (; count && d.uptr & mask; count--)
                        *d.u8++ = *s.u8++;
                distance = (src - dest) & mask;
        }

        if (distance) {
                ...

arch/riscv/lib/string.c line 55

Quoted 5 lines

arch/riscv/lib/string.c new file +5 -0

+             /* 32/64 bit wide copy from s to d.
+              * d is aligned now but s is not, so read s alignment wise,
+              * and do proper shift to get the right value.
+              * Works only on Little Endian machines.
+              */

Normal kernel comment style always start with a:

                /*

Quoted 1 line

+ for (next = s.ulong[0]; count >= bytes_long + mask; count -= bytes_long) {

Please avoid the pointlessly overlong line. And (just as a matter of personal preference) I find for loop that don't actually use a single iterator rather confusing. Wjy not simply:

                next = s.ulong[0];
                while (count >= bytes_long + mask) {
                        ...
                        count -= bytes_long;
                }

arch/riscv/lib/string.c new file +7 -0

@@ -0,0 +1,91 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * String functions optimized for hardware which doesn't
+ * handle unaligned memory accesses efficiently.
+ *
+ * Copyright (C) 2021 Matteo Croce
+ */

(quoted diff) +1 -0

+		for (next = s.ulong[0]; count >= bytes_long + mask; count -= 

bytes_long) {

arch/riscv/lib/string.c new file +8 -0

+			last = next;
+			next = s.ulong[1];
+
+			d.ulong[0] = last >> (distance * 8) |
+				     next << ((bytes_long - distance) * 8);
+
+			d.ulong++;
+			s.ulong++;

arch/riscv/lib/string.c new file +16 -0

+		for (; count >= bytes_long; count -= bytes_long)
+			*d.ulong++ = *s.ulong++;
+	}
+
+	/* suppress warning when CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS=y */
+	goto copy_remainder;
+
+copy_remainder:
+	while (count--)
+		*d.u8++ = *s.u8++;
+
+	return dest;
+}
+EXPORT_SYMBOL(__memcpy);
+
+void *memcpy(void *dest, const void *src, size_t count) __weak

__alias(__memcpy);
+EXPORT_SYMBOL(memcpy);

Hello Matteo and thanks for the patch,

Στις 2021-06-17 18:27, Matteo Croce έγραψε:

Quoted 15 lines

arch/riscv/lib/string.c new file +13 -0

@@ -0,0 +1,91 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * String functions optimized for hardware which doesn't
+ * handle unaligned memory accesses efficiently.
+ *
+ * Copyright (C) 2021 Matteo Croce
+ */
+
+#include <linux/types.h>
+#include <linux/module.h>
+
+/* Minimum size for a word copy to be convenient */
+#define MIN_THRESHOLD (BITS_PER_LONG / 8 * 2)

arch/riscv/lib/string.c line 17

Quoted 4 lines

arch/riscv/lib/string.c new file +4 -0

+
+/* convenience union to avoid cast between different pointer types */
+union types {
+     u8 *u8;

You are using a type as a name, I'd go with as_bytes/as_ulong/as_uptr which makes it easier for the reader to understand what you are trying to do.

Quoted 4 lines

arch/riscv/lib/string.c new file +4 -0

+     unsigned long *ulong;
+     uintptr_t uptr;
+};
+

arch/riscv/lib/string.c line 26

Quoted 5 lines

arch/riscv/lib/string.c new file +5 -0

+union const_types {
+     const u8 *u8;
+     unsigned long *ulong;
+};
+

I suggest you define those unions inside the function body, no one else is using them.

arch/riscv/lib/string.c line 32

Quoted 6 lines

arch/riscv/lib/string.c new file +6 -0

+void *__memcpy(void *dest, const void *src, size_t count)
+{
+     const int bytes_long = BITS_PER_LONG / 8;
+#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+     const int mask = bytes_long - 1;
+     const int distance = (src - dest) & mask;

Why not unsigned ints ?

arch/riscv/lib/string.c line 37

Quoted 5 lines

arch/riscv/lib/string.c new file +5 -0

+#endif
+     union const_types s = { .u8 = src };
+     union types d = { .u8 = dest };
+
+#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS

If you want to be compliant with memcpy you should check for overlapping regions here since "The memory areas must not overlap", and do nothing about it because according to POSIX this leads to undefined behavior. That's why recent libc implementations use memmove in any case (memcpy is an alias to memmove), which is the suggested approach.

arch/riscv/lib/string.c line 44

Quoted 7 lines

arch/riscv/lib/string.c new file +7 -0

+     if (count < MIN_THRESHOLD)
+             goto copy_remainder;
+
+     /* copy a byte at time until destination is aligned */
+     for (; count && d.uptr & mask; count--)
+             *d.u8++ = *s.u8++;
+

You should check for !IS_ENABLED(CONFIG_CPU_BIG_ENDIAN) here.

arch/riscv/lib/string.c line 49

Quoted 5 lines

arch/riscv/lib/string.c new file +5 -0

+     if (distance) {
+             unsigned long last, next;
+
+             /* move s backward to the previous alignment boundary */
+             s.u8 -= distance;

It'd help here to explain that since s is distance bytes ahead relative to d, and d reached the alignment boundary above, s is now aligned but the data needs to be shifted to compensate for distance, in order to do word-by-word copy.

arch/riscv/lib/string.c line 55

Quoted 6 lines

arch/riscv/lib/string.c new file +6 -0

+
+             /* 32/64 bit wide copy from s to d.
+              * d is aligned now but s is not, so read s alignment wise,
+              * and do proper shift to get the right value.
+              * Works only on Little Endian machines.
+              */

This commend is misleading because s is aligned or else s.ulong[0]/[1] below would result an unaligned access.

Quoted 14 lines

(quoted diff) +1 -0

+             for (next = s.ulong[0]; count >= bytes_long + mask; count -=

bytes_long) {

arch/riscv/lib/string.c new file +12 -0

+                     last = next;
+                     next = s.ulong[1];
+
+                     d.ulong[0] = last >> (distance * 8) |
+                                  next << ((bytes_long - distance) * 8);
+
+                     d.ulong++;
+                     s.ulong++;
+             }
+
+             /* restore s with the original offset */
+             s.u8 += distance;

arch/riscv/lib/string.c line 74

Quoted 6 lines

arch/riscv/lib/string.c new file +6 -0

+     } else
+#endif
+     {
+             /* if the source and dest lower bits are the same, do a simple
+              * 32/64 bit wide copy.
+              */

A while() loop would make more sense here.

Quoted 10 lines

arch/riscv/lib/string.c new file +10 -0

+             for (; count >= bytes_long; count -= bytes_long)
+                     *d.ulong++ = *s.ulong++;
+     }
+
+     /* suppress warning when CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS=y */
+     goto copy_remainder;
+
+copy_remainder:
+     while (count--)
+             *d.u8++ = *s.u8++;

Quoted 8 lines

arch/riscv/lib/string.c new file +6 -0

+
+     return dest;
+}
+EXPORT_SYMBOL(__memcpy);
+
+void *memcpy(void *dest, const void *src, size_t count) __weak

__alias(__memcpy);
+EXPORT_SYMBOL(memcpy);

Quoted 7 lines

If you want to be compliant with memcpy you should check for overlapping regions here since "The memory areas must not overlap", and do nothing about it because according to POSIX this leads to undefined behavior. That's why recent libc implementations use memmove in any case (memcpy is an alias to memmove), which is the suggested approach.

Mmm which memcpy arch implementation does this check? I guess that noone is currently doing it.

arch/riscv/lib/string.c +11 -0

+
+/*
+ * Simply check if the buffer overlaps an call memcpy() in case,
+ * otherwise do a simple one byte at time backward copy.
+ */
+void *__memmove(void *dest, const void *src, size_t count)
+{
+	if (dest < src || src + count <= dest)
+		return memcpy(dest, src, count);
+
+	if (dest > src) {

+void *memmove(void *dest, const void *src, size_t count) __weak __alias(__memmove);
+EXPORT_SYMBOL(memmove);

Sent: 22 June 2021 02:08

Στις 2021-06-17 18:27, Matteo Croce έγραψε:

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 121

Quoted 7 lines

arch/riscv/lib/string.c +7 -0

+
+void *__memset(void *s, int c, size_t count)
+{
+	union types dest = { .u8 = s };
+
+	if (count >= MIN_THRESHOLD) {
+		const int bytes_long = BITS_PER_LONG / 8;

You could make 'const int bytes_long = BITS_PER_LONG / 8;'

Quoted 6 lines

arch/riscv/lib/string.c +6 -0

+		unsigned long cu = (unsigned long)c;
+
+		/* Compose an ulong with 'c' repeated 4/8 times */
+		cu |= cu << 8;
+		cu |= cu << 16;
+#if BITS_PER_LONG == 64

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 130

Quoted 3 lines

arch/riscv/lib/string.c +3 -0

+		cu |= cu << 32;
+#endif
+

You don't have to create cu here, you'll fill dest buffer with 'c' anyway so after filling up enough 'c's to be able to grab an aligned word full of them from dest, you can just grab that word and keep filling up dest with it.

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 135

Quoted 6 lines

arch/riscv/lib/string.c +5 -0

+#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+		/* Fill the buffer one byte at time until the destination
+		 * is aligned on a 32/64 bit boundary.
+		 */
+		for (; count && dest.uptr % bytes_long; count--)

You could reuse & mask here instead of % bytes_long.

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 137

Quoted 2 lines

arch/riscv/lib/string.c +2 -0

+			*dest.u8++ = c;
+#endif

I noticed you also used CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS on your memcpy patch, is it worth it here ? To begin with riscv doesn't set it and even if it did we are talking about a loop that will run just a few times to reach the alignment boundary (worst case scenario it'll run 7 times), I don't think we gain much here, even for archs that have efficient unaligned access.

From: Nick Kossifidis

Quoted 12 lines

Sent: 22 June 2021 02:08

Στις 2021-06-17 18:27, Matteo Croce έγραψε:

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 121

Quoted 7 lines

arch/riscv/lib/string.c +7 -0

+
+void *__memset(void *s, int c, size_t count)
+{
+   union types dest = { .u8 = s };
+
+   if (count >= MIN_THRESHOLD) {
+           const int bytes_long = BITS_PER_LONG / 8;

You could make 'const int bytes_long = BITS_PER_LONG / 8;'

What is wrong with sizeof (long) ?
...

Quoted 6 lines

Quoted 6 lines

arch/riscv/lib/string.c +6 -0

+           unsigned long cu = (unsigned long)c;
+
+           /* Compose an ulong with 'c' repeated 4/8 times */
+           cu |= cu << 8;
+           cu |= cu << 16;
+#if BITS_PER_LONG == 64

Quoted 8 lines

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 130

Quoted 3 lines

arch/riscv/lib/string.c +3 -0

+           cu |= cu << 32;
+#endif
+

You don't have to create cu here, you'll fill dest buffer with 'c' anyway so after filling up enough 'c's to be able to grab an aligned word full of them from dest, you can just grab that word and keep filling up dest with it.

That will be a lot slower - especially if run on something like x86. A write-read of the same size is optimised by the store-load forwarder. But the byte write, word read will have to go via the cache.

You can just write:

        cu = (unsigned long)c * 0x0101010101010101ull;

and let the compiler sort out the best way to generate the constant.

Quoted 12 lines

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 135

Quoted 6 lines

arch/riscv/lib/string.c +5 -0

+#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+           /* Fill the buffer one byte at time until the destination
+            * is aligned on a 32/64 bit boundary.
+            */
+           for (; count && dest.uptr % bytes_long; count--)

You could reuse & mask here instead of % bytes_long.

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 137

Quoted 2 lines

arch/riscv/lib/string.c +2 -0

+                   *dest.u8++ = c;
+#endif

Quoted 6 lines

I noticed you also used CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS on your memcpy patch, is it worth it here ? To begin with riscv doesn't set it and even if it did we are talking about a loop that will run just a few times to reach the alignment boundary (worst case scenario it'll run 7 times), I don't think we gain much here, even for archs that have efficient unaligned access.

With CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS it probably isn't worth even checking the alignment.
While aligning the copy will be quicker for an unaligned buffer they almost certainly don't happen often enough to worry about. In any case you'd want to do a misaligned word write to the start of the buffer - not separate byte writes.
Provided the buffer is long enough you can also do a misaligned write to the end of the buffer before filling from the start.

I suspect you may need either barrier() or use a ptr to packed to avoid the perverted 'undefined behaviour' fubar.'

Sent: 23 June 2021 02:15

Quoted 2 lines · David Laight

From: Nick Kossifidis

Quoted 4 lines

You can just write:

        cu = (unsigned long)c * 0x0101010101010101ull;

and let the compiler sort out the best way to generate the constant.

Interesting. I see that most compilers do an integer multiplication, is it faster than three shift and three or?

clang on riscv generates even more instructions to create the immediate:

unsigned long repeat_shift(int c)
{
unsigned long cu = (unsigned long)c;

  cu |= cu << 8;
  cu |= cu << 16;
  cu |= cu << 32;

return cu;
}

unsigned long repeat_mul(int c)
{
return (unsigned long)c * 0x0101010101010101ull;
}

repeat_shift:
slli a1, a0, 8
or a0, a0, a1
slli a1, a0, 16
or a0, a0, a1
slli a1, a0, 32
or a0, a0, a1
ret

repeat_mul:
lui a1, 4112
addiw a1, a1, 257
slli a1, a1, 16
addi a1, a1, 257
slli a1, a1, 16
addi a1, a1, 257
mul a0, a0, a1
ret

Στις 2021-06-17 18:27, Matteo Croce έγραψε:

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 121

Quoted 7 lines

arch/riscv/lib/string.c +7 -0

+
+void *__memset(void *s, int c, size_t count)
+{
+     union types dest = { .u8 = s };
+
+     if (count >= MIN_THRESHOLD) {
+             const int bytes_long = BITS_PER_LONG / 8;

You could make 'const int bytes_long = BITS_PER_LONG / 8;' and 'const int mask = bytes_long - 1;' from your memcpy patch visible to memset as well (static const...) and use them here (mask would make more sense to be named as word_mask).

Quoted 6 lines

arch/riscv/lib/string.c +6 -0

+             unsigned long cu = (unsigned long)c;
+
+             /* Compose an ulong with 'c' repeated 4/8 times */
+             cu |= cu << 8;
+             cu |= cu << 16;
+#if BITS_PER_LONG == 64

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 130

Quoted 3 lines

arch/riscv/lib/string.c +3 -0

+             cu |= cu << 32;
+#endif
+

You don't have to create cu here, you'll fill dest buffer with 'c' anyway so after filling up enough 'c's to be able to grab an aligned word full of them from dest, you can just grab that word and keep filling up dest with it.

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 135

Quoted 5 lines

arch/riscv/lib/string.c +5 -0

+#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+             /* Fill the buffer one byte at time until the destination
+              * is aligned on a 32/64 bit boundary.
+              */
+             for (; count && dest.uptr % bytes_long; count--)

You could reuse & mask here instead of % bytes_long.

arch/riscv/lib/string.c EXPORT_SYMBOL(__memmove); · line 137

Quoted 2 lines

arch/riscv/lib/string.c +2 -0

+                     *dest.u8++ = c;
+#endif

I noticed you also used CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS on your memcpy patch, is it worth it here ? To begin with riscv doesn't set it and even if it did we are talking about a loop that will run just a few times to reach the alignment boundary (worst case scenario it'll run 7 times), I don't think we gain much here, even for archs that have efficient unaligned access.

From: Matteo Croce <[email protected]>

Replace the assembly mem{cpy,move,set} with C equivalent.

Try to access RAM with the largest bit width possible, but without doing unaligned accesses.

Tested on a BeagleV Starlight with a SiFive U74 core, where the improvement is noticeable.

Hello Matteo,

Στις 2021-06-17 18:27, Matteo Croce έγραψε:

Quoted 10 lines

From: Matteo Croce <[email protected]>

Replace the assembly mem{cpy,move,set} with C equivalent.

Try to access RAM with the largest bit width possible, but without doing unaligned accesses.

Tested on a BeagleV Starlight with a SiFive U74 core, where the improvement is noticeable.

There are already generic C implementations for memcpy/memmove/memset at
https://elixir.bootlin.com/linux/v5.13-rc7/source/lib/string.c#L871 but are doing one byte at a time, I suggest you update them to do word-by-word copy instead of introducing yet another memcpy/memmove C implementation on arch/riscv/.