[RFC 0/5] memset_l and memfill

[RFC 0/5] memset_l and memfill

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

zram was recently enhanced to support compressing pages with a repeating
pattern up to the size of an unsigned long.  As part of the discussion,
we noted it would be nice if architectures had optimised routines to
fill regions of memory with patterns larger than those contained in a
single byte.

The memfill() function exists as part of Lars Wirzenius' publib, but
it's not necessarily the most convenient interface to use.  So I offer
four interfaces as part of this patchset -- memset_l (long), memset32
(32-bit), memset64 (64-bit) and memfill (arbitrary length).

We have one user in this patchset for each of memset32() and memset_l().
Patches to convert more users would be welcome.  In particular, there
aren't any users for the generic memfill() yet.  Requests for memset_p
(pointer), memset16 and memset_s (short) would be interesting.  memset_ll
(long long), or other suggestions that would lead to compiling memset64()
on 32-bit would also be interesting.

I'd also like to see assembly language mavens produce optimised
memset32/memset64 implementations for their pet architecture.  I've
included my awful test-suite for your benefit; it did find a few bugs
in memfill() while I was getting the edge cases nailed down.

Matthew Wilcox (5):
  Add memset_l(), memset32() and memset64()
  zram: Convert to using memset_l()
  sym53c8xx_2: Convert to use memset32()
  Add memfill()
  Hacky testsuite for memfill() and memset_l()

 drivers/block/zram/zram_drv.c                 | 15 +----
 drivers/scsi/sym53c8xx_2/sym_hipd.c           | 11 +---
 include/linux/string.h                        | 16 +++++
 lib/string.c                                  | 85 +++++++++++++++++++++++++++
 tools/include/linux/compiler.h                |  5 ++
 tools/include/linux/string.h                  | 11 ++++
 tools/testing/radix-tree/asm/page.h           |  0
 tools/testing/radix-tree/asm/word-at-a-time.h |  1 +
 tools/testing/radix-tree/linux/ctype.h        |  0
 tools/testing/radix-tree/linux/kernel.h       |  2 +
 tools/testing/radix-tree/string.c             | 53 +++++++++++++++++
 11 files changed, 179 insertions(+), 20 deletions(-)
 create mode 100644 tools/testing/radix-tree/asm/page.h
 create mode 100644 tools/testing/radix-tree/asm/word-at-a-time.h
 create mode 100644 tools/testing/radix-tree/linux/ctype.h
 create mode 100644 tools/testing/radix-tree/string.c

-- 
2.11.0

[PATCH 1/5] Add memset_l(), memset32() and memset64()

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

memset_l() is like memset() but allows the user to fill the destination
with a pattern which fits in an unsigned long.  memset32() and memset64()
are 32-bit and 64-bit variants of this; memset_l() will call the
appropriate one.  memset32() is also useful by itself, while I am not
currently aware of any user who would benefit from memset64() on 32-bit.

Architecture maintainers should be able to write optimised versions of
these quite easily as it would share a lot with the core of an optimised
memset().

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/string.h | 13 +++++++++++++
 lib/string.c           | 44 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+)

diff --git a/include/linux/string.h b/include/linux/string.h
index 26b6f6a66f83..642a82290a25 100644
--- a/include/linux/string.h
+++ b/include/linux/string.h
@@ -99,6 +99,19 @@ extern __kernel_size_t strcspn(const char *,const char *);
 #ifndef __HAVE_ARCH_MEMSET
 extern void * memset(void *,int,__kernel_size_t);
 #endif
+#ifndef __HAVE_ARCH_MEMSET_PLUS
+extern void *memset32(uint32_t *, uint32_t, __kernel_size_t);
+extern void *memset64(uint64_t *, uint64_t, __kernel_size_t);
+static inline void *memset_l(unsigned long *p, unsigned long v,
+		__kernel_size_t n)
+{
+#if BITS_PER_LONG == 32
+	return memset32((uint32_t *)p, v, n);
+#else
+	return memset64((uint64_t *)p, v, n);
+#endif
+}
+#endif
 #ifndef __HAVE_ARCH_MEMCPY
 extern void * memcpy(void *,const void *,__kernel_size_t);
 #endif
diff --git a/lib/string.c b/lib/string.c
index ed83562a53ae..85628c8d3abd 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -697,6 +697,50 @@ void memzero_explicit(void *s, size_t count)
 }
 EXPORT_SYMBOL(memzero_explicit);
 
+#ifndef __HAVE_ARCH_MEMSET_PLUS
+/**
+ * memset32() - Fill a memory area with a uint32_t
+ * @s: Pointer to the start of the area.
+ * @v: The value to fill the area with
+ * @count: The number of values to store
+ *
+ * Differs from memset() in that it fills with a uint32_t instead
+ * of a byte.  Remember that @count is the number of uint32_ts to
+ * store, not the number of bytes.
+ */
+void *memset32(uint32_t *s, uint32_t v, size_t count)
+{
+	uint32_t *xs = s;
+
+	while (count--)
+		*xs++ = v;
+	return s;
+}
+EXPORT_SYMBOL(memset32);
+
+#if BITS_PER_LONG > 32
+/**
+ * memset64() - Fill a memory area with a uint64_t
+ * @s: Pointer to the start of the area.
+ * @v: The value to fill the area with
+ * @count: The number of values to store
+ *
+ * Differs from memset() in that it fills with a uint64_t instead
+ * of a byte.  Remember that @count is the number of uint64_ts to
+ * store, not the number of bytes.
+ */
+void *memset64(uint64_t *s, uint64_t v, size_t count)
+{
+	uint64_t *xs = s;
+
+	while (count--)
+		*xs++ = v;
+	return s;
+}
+EXPORT_SYMBOL(memset64);
+#endif
+#endif
+
 #ifndef __HAVE_ARCH_MEMCPY
 /**
  * memcpy - Copy one area of memory to another
-- 
2.11.0

[PATCH 2/5] zram: Convert to using memset_l()

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

zram was the motivation for creating memset_l().

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 drivers/block/zram/zram_drv.c | 15 +++------------
 1 file changed, 3 insertions(+), 12 deletions(-)

diff --git a/drivers/block/zram/zram_drv.c b/drivers/block/zram/zram_drv.c
index e27d89a36c34..25dcad309695 100644
--- a/drivers/block/zram/zram_drv.c
+++ b/drivers/block/zram/zram_drv.c
@@ -157,20 +157,11 @@ static inline void update_used_max(struct zram *zram,
 	} while (old_max != cur_max);
 }
 
-static inline void zram_fill_page(char *ptr, unsigned long len,
+static inline void zram_fill_page(void *ptr, unsigned long len,
 					unsigned long value)
 {
-	int i;
-	unsigned long *page = (unsigned long *)ptr;
-
 	WARN_ON_ONCE(!IS_ALIGNED(len, sizeof(unsigned long)));
-
-	if (likely(value == 0)) {
-		memset(ptr, 0, len);
-	} else {
-		for (i = 0; i < len / sizeof(*page); i++)
-			page[i] = value;
-	}
+	memset_l(ptr, value, len / sizeof(unsigned long));
 }
 
 static bool page_same_filled(void *ptr, unsigned long *element)
@@ -193,7 +184,7 @@ static bool page_same_filled(void *ptr, unsigned long *element)
 static void handle_same_page(struct bio_vec *bvec, unsigned long element)
 {
 	struct page *page = bvec->bv_page;
-	void *user_mem;
+	char *user_mem;
 
 	user_mem = kmap_atomic(page);
 	zram_fill_page(user_mem + bvec->bv_offset, bvec->bv_len, element);
-- 
2.11.0

[PATCH 3/5] sym53c8xx_2: Convert to use memset32()

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

memset32() can be used to initialise these three arrays.  Minor code
footprint reduction.

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 drivers/scsi/sym53c8xx_2/sym_hipd.c | 11 +++--------
 1 file changed, 3 insertions(+), 8 deletions(-)

diff --git a/drivers/scsi/sym53c8xx_2/sym_hipd.c b/drivers/scsi/sym53c8xx_2/sym_hipd.c
index 6b349e301869..b886b10e3499 100644
--- a/drivers/scsi/sym53c8xx_2/sym_hipd.c
+++ b/drivers/scsi/sym53c8xx_2/sym_hipd.c
@@ -4985,13 +4985,10 @@ struct sym_lcb *sym_alloc_lcb (struct sym_hcb *np, u_char tn, u_char ln)
 	 *  Compute the bus address of this table.
 	 */
 	if (ln && !tp->luntbl) {
-		int i;
-
 		tp->luntbl = sym_calloc_dma(256, "LUNTBL");
 		if (!tp->luntbl)
 			goto fail;
-		for (i = 0 ; i < 64 ; i++)
-			tp->luntbl[i] = cpu_to_scr(vtobus(&np->badlun_sa));
+		memset32(tp->luntbl, cpu_to_scr(vtobus(&np->badlun_sa)), 64);
 		tp->head.luntbl_sa = cpu_to_scr(vtobus(tp->luntbl));
 	}
 
@@ -5077,8 +5074,7 @@ static void sym_alloc_lcb_tags (struct sym_hcb *np, u_char tn, u_char ln)
 	/*
 	 *  Initialize the task table with invalid entries.
 	 */
-	for (i = 0 ; i < SYM_CONF_MAX_TASK ; i++)
-		lp->itlq_tbl[i] = cpu_to_scr(np->notask_ba);
+	memset32(lp->itlq_tbl, cpu_to_scr(np->notask_ba), SYM_CONF_MAX_TASK);
 
 	/*
 	 *  Fill up the tag buffer with tag numbers.
@@ -5764,8 +5760,7 @@ int sym_hcb_attach(struct Scsi_Host *shost, struct sym_fw *fw, struct sym_nvram
 		goto attach_failed;
 
 	np->badlun_sa = cpu_to_scr(SCRIPTB_BA(np, resel_bad_lun));
-	for (i = 0 ; i < 64 ; i++)	/* 64 luns/target, no less */
-		np->badluntbl[i] = cpu_to_scr(vtobus(&np->badlun_sa));
+	memset32(np->badluntbl, cpu_to_scr(vtobus(&np->badlun_sa)), 64);
 
 	/*
 	 *  Prepare the bus address array that contains the bus 
-- 
2.11.0

[PATCH 4/5] Add memfill()

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

Similar to Lars Wirzenius' memfill(), this version has optimisations for
source sizes of 1, 2, 4 (and 8 on 64 bit architectures).

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/string.h |  3 +++
 lib/string.c           | 41 +++++++++++++++++++++++++++++++++++++++++
 2 files changed, 44 insertions(+)

diff --git a/include/linux/string.h b/include/linux/string.h
index 642a82290a25..f340e6fb309f 100644
--- a/include/linux/string.h
+++ b/include/linux/string.h
@@ -112,6 +112,9 @@ static inline void *memset_l(unsigned long *p, unsigned long v,
 #endif
 }
 #endif
+#ifndef __HAVE_ARCH_MEMFILL
+extern void memfill(void *, __kernel_size_t, void *, __kernel_size_t);
+#endif
 #ifndef __HAVE_ARCH_MEMCPY
 extern void * memcpy(void *,const void *,__kernel_size_t);
 #endif
diff --git a/lib/string.c b/lib/string.c
index 85628c8d3abd..d22711e6490a 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -741,6 +741,47 @@ EXPORT_SYMBOL(memset64);
 #endif
 #endif
 
+#ifndef __HAVE_ARCH_MEMFILL
+/**
+ * memfill() - Fill a region of memory with copies of another region
+ * @dst: Destination address
+ * @dsz: Size of destination area
+ * @src: Source address
+ * @ssz: Size of source area
+ */
+void memfill(void *dst, size_t dsz, void *src, size_t ssz)
+{
+	if (ssz == 1) {
+		memset(dst, *(unsigned char *)src, dsz);
+		return;
+	} else if (ssz == sizeof(short)) {
+		uint32_t v = *(unsigned short *)src;
+		v |= (v << 16);
+
+		memset32(dst, v, dsz / sizeof(uint32_t));
+		dst = (uint32_t *)dst + dsz / sizeof(uint32_t);
+		dsz %= sizeof(uint32_t);
+	} else if (ssz == sizeof(int)) {
+		memset32(dst, *(uint32_t *)src, dsz / sizeof(uint32_t));
+		dst = (uint32_t *)dst + dsz / sizeof(uint32_t);
+		dsz %= sizeof(int);
+	} else if (ssz == sizeof(long)) {
+		memset_l(dst, *(long *)src, dsz / sizeof(long));
+		dst = (long *)dst + dsz / sizeof(long);
+		dsz %= sizeof(long);
+	} else {
+		while (dsz >= ssz) {
+			memcpy(dst, src, ssz);
+			dsz -= ssz;
+			dst += ssz;
+		}
+	}
+	if (dsz)
+		memcpy(dst, src, dsz);
+}
+EXPORT_SYMBOL(memfill);
+#endif
+
 #ifndef __HAVE_ARCH_MEMCPY
 /**
  * memcpy - Copy one area of memory to another
-- 
2.11.0

[PATCH 5/5] Hacky testsuite for memfill() and memset_l()

[Matthew Wilcox]

From: Matthew Wilcox <mawilcox@microsoft.com>

cc -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fno-strict-aliasing \
	string.c -o string

Has to be compiled with -fno-strict-aliasing because I do unclean things
with pointers to different types (in the test suite, not the lib).

Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 tools/include/linux/compiler.h                |  5 +++
 tools/include/linux/string.h                  | 11 ++++++
 tools/testing/radix-tree/asm/page.h           |  0
 tools/testing/radix-tree/asm/word-at-a-time.h |  1 +
 tools/testing/radix-tree/linux/ctype.h        |  0
 tools/testing/radix-tree/linux/kernel.h       |  2 +
 tools/testing/radix-tree/string.c             | 53 +++++++++++++++++++++++++++
 7 files changed, 72 insertions(+)
 create mode 100644 tools/testing/radix-tree/asm/page.h
 create mode 100644 tools/testing/radix-tree/asm/word-at-a-time.h
 create mode 100644 tools/testing/radix-tree/linux/ctype.h
 create mode 100644 tools/testing/radix-tree/string.c

diff --git a/tools/include/linux/compiler.h b/tools/include/linux/compiler.h
index 8de163b17c0d..48dca30b5a7a 100644
--- a/tools/include/linux/compiler.h
+++ b/tools/include/linux/compiler.h
@@ -8,6 +8,7 @@
 /* Optimization barrier */
 /* The "volatile" is due to gcc bugs */
 #define barrier() __asm__ __volatile__("": : :"memory")
+#define barrier_data(ptr) __asm__ __volatile__("": : "r"(ptr) :"memory")
 
 #ifndef __always_inline
 # define __always_inline	inline __attribute__((always_inline))
@@ -44,6 +45,10 @@
 # define __force
 #endif
 
+#ifndef __visible
+# define __visible		__attribute__((externally_visible))
+#endif
+
 #ifndef __weak
 # define __weak			__attribute__((weak))
 #endif
diff --git a/tools/include/linux/string.h b/tools/include/linux/string.h
index f436d2420a18..ce757cb4737c 100644
--- a/tools/include/linux/string.h
+++ b/tools/include/linux/string.h
@@ -4,6 +4,17 @@
 
 #include <linux/types.h>	/* for size_t */
 
+extern void *memset32(uint32_t *, uint32_t, size_t);
+extern void *memset64(uint64_t *, uint64_t, size_t);
+static inline void *memset_l(unsigned long *p, unsigned long v, size_t n)
+{
+#if BITS_PER_LONG == 32
+	return memset32((uint32_t *)p, v, n);
+#else
+	return memset64((uint64_t *)p, v, n);
+#endif
+}
+
 void *memdup(const void *src, size_t len);
 
 int strtobool(const char *s, bool *res);
diff --git a/tools/testing/radix-tree/asm/page.h b/tools/testing/radix-tree/asm/page.h
new file mode 100644
index 000000000000..e69de29bb2d1
diff --git a/tools/testing/radix-tree/asm/word-at-a-time.h b/tools/testing/radix-tree/asm/word-at-a-time.h
new file mode 100644
index 000000000000..2cdbbc249e59
--- /dev/null
+++ b/tools/testing/radix-tree/asm/word-at-a-time.h
@@ -0,0 +1 @@
+#include "../../../include/asm-generic/word-at-a-time.h"
diff --git a/tools/testing/radix-tree/linux/ctype.h b/tools/testing/radix-tree/linux/ctype.h
new file mode 100644
index 000000000000..e69de29bb2d1
diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index b21a77fddcf7..9f38f8a42fcb 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -16,6 +16,8 @@
 #define pr_debug printk
 #define pr_cont printk
 
+#define REPEAT_BYTE(x)	((~0ul / 0xff) * (x))
+
 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
 
 #endif /* _KERNEL_H */
diff --git a/tools/testing/radix-tree/string.c b/tools/testing/radix-tree/string.c
new file mode 100644
index 000000000000..147796d76d27
--- /dev/null
+++ b/tools/testing/radix-tree/string.c
@@ -0,0 +1,53 @@
+#include <stddef.h>
+#include <ctype.h>
+#include <assert.h>
+
+#include <string.h>
+#undef strncpy
+#undef strncmp
+#undef strchr
+#undef strsep
+#include "../../../lib/string.c"
+
+#define short_to_int(x)	((x) | ((unsigned long)(x) << 16))
+#define short_to_long(x) (short_to_int(x) | (short_to_int(x) << 16 << 16))
+
+int main(void)
+{
+	unsigned long foo[27] = {0,};
+	unsigned char bar[128];
+	unsigned int i;
+	unsigned short s = 0x1234;
+	char c;
+
+	memset_l(foo, (unsigned long)main, 21);
+
+	assert(foo[21] == 0);
+	assert(foo[20] == (unsigned long)main);
+
+	assert(foo[0] == (unsigned long)main);
+	memset_l(foo, 1, 0);
+	assert(foo[0] == (unsigned long)main);
+
+	memfill(foo, 10 * sizeof(long), &s, sizeof(s));
+	printf("%lx %lx\n", foo[0], short_to_long(s));
+	for (i = 0; i < 10; i++)
+		assert(foo[i] == short_to_long(s));
+	assert(foo[i] == (unsigned long)main);
+
+	memset(bar, 1, sizeof(bar));
+	for (i = 0; i < sizeof(bar); i++)
+		assert(bar[i] == 1);
+
+	c = 2;
+	memfill(bar, sizeof(bar), &c, 1);
+	for (i = 0; i < sizeof(bar); i++)
+		assert(bar[i] == 2);
+
+	s = 0x4321;
+	memfill(bar, 11, &s, sizeof(s));
+	assert(bar[11] == 2);
+	assert(bar[10] == *(unsigned char *)&s);
+
+	return 0;
+}
-- 
2.11.0