[Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero

[Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero

[Richard Henderson]

Changes from v2 to v3:

  * Unit testing.  This includes having x86 attempt all versions of
    the accelerator that will run on the hardware.  Thus an avx2 host
    will run the basic test 5 times (1.5sec on my laptop).

  * Drop the ppc and aarch64 specializations.  I have improved the
    basic integer version to the point that those vectorized versions
    are not a win.

    In the case of my aarch64 mustang, the integer version is 4 times
    faster than the neon version that I delete.  With effort I was
    able to rewrite the neon version to come to within a factor of 1.1,
    but it remained slower than the integer.  To be fair, gcc6 makes
    very good use of ldp, so the integer path is *also* loading 16 bytes
    per insn.

    I can forward my standalone aarch64 benchmark if anyone is interested.

    Note however that at least the avx2 acceleration is still very much
    a win, being about 3 times faster on my laptop.  Of course, it's
    handling 4 times as much data per loop as the integer version, so
    one can still see the overhead caused by using vector insns.

    For grins I wrote an avx512 version, if someone has a skylake upon
    which to test and benchmark.  That requires additional configure
    checks, so I didn't bother to include it here.


r~


Richard Henderson (9):
  cutils: Move buffer_is_zero and subroutines to a new file
  cutils: Remove SPLAT macro
  cutils: Export only buffer_is_zero
  cutils: Rearrange buffer_is_zero acceleration
  cutils: Add test for buffer_is_zero
  cutils: Add generic prefetch
  cutils: Rewrite x86 buffer zero checking
  cutils: Remove aarch64 buffer zero checking
  cutils: Remove ppc buffer zero checking

 configure                 |  21 +--
 include/qemu/cutils.h     |   3 +-
 migration/ram.c           |   2 +-
 migration/rdma.c          |   5 +-
 tests/Makefile.include    |   3 +
 tests/test-bufferiszero.c |  78 +++++++++++
 util/Makefile.objs        |   1 +
 util/bufferiszero.c       | 332 ++++++++++++++++++++++++++++++++++++++++++++++
 util/cutils.c             | 244 ----------------------------------
 9 files changed, 423 insertions(+), 266 deletions(-)
 create mode 100644 tests/test-bufferiszero.c
 create mode 100644 util/bufferiszero.c

-- 
2.7.4

[Qemu-devel] [PATCH v3 1/9] cutils: Move buffer_is_zero and subroutines to a new file

[Richard Henderson]

Signed-off-by: Richard Henderson <rth@twiddle.net>
---
 util/Makefile.objs  |   1 +
 util/bufferiszero.c | 272 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 util/cutils.c       | 244 ----------------------------------------------
 3 files changed, 273 insertions(+), 244 deletions(-)
 create mode 100644 util/bufferiszero.c

diff --git a/util/Makefile.objs b/util/Makefile.objs
index 96cb1e0..ffca8f3 100644
--- a/util/Makefile.objs
+++ b/util/Makefile.objs
@@ -1,4 +1,5 @@
 util-obj-y = osdep.o cutils.o unicode.o qemu-timer-common.o
+util-obj-y += bufferiszero.o
 util-obj-$(CONFIG_POSIX) += compatfd.o
 util-obj-$(CONFIG_POSIX) += event_notifier-posix.o
 util-obj-$(CONFIG_POSIX) += mmap-alloc.o
diff --git a/util/bufferiszero.c b/util/bufferiszero.c
new file mode 100644
index 0000000..9bb1ae5
--- /dev/null
+++ b/util/bufferiszero.c
@@ -0,0 +1,272 @@
+/*
+ * Simple C functions to supplement the C library
+ *
+ * Copyright (c) 2006 Fabrice Bellard
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+#include "qemu/osdep.h"
+#include "qemu-common.h"
+#include "qemu/cutils.h"
+
+
+/* vector definitions */
+#ifdef __ALTIVEC__
+#include <altivec.h>
+/* The altivec.h header says we're allowed to undef these for
+ * C++ compatibility.  Here we don't care about C++, but we
+ * undef them anyway to avoid namespace pollution.
+ */
+#undef vector
+#undef pixel
+#undef bool
+#define VECTYPE        __vector unsigned char
+#define SPLAT(p)       vec_splat(vec_ld(0, p), 0)
+#define ALL_EQ(v1, v2) vec_all_eq(v1, v2)
+#define VEC_OR(v1, v2) ((v1) | (v2))
+/* altivec.h may redefine the bool macro as vector type.
+ * Reset it to POSIX semantics. */
+#define bool _Bool
+#elif defined __SSE2__
+#include <emmintrin.h>
+#define VECTYPE        __m128i
+#define SPLAT(p)       _mm_set1_epi8(*(p))
+#define ALL_EQ(v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF)
+#define VEC_OR(v1, v2) (_mm_or_si128(v1, v2))
+#elif defined(__aarch64__)
+#include "arm_neon.h"
+#define VECTYPE        uint64x2_t
+#define ALL_EQ(v1, v2) \
+        ((vgetq_lane_u64(v1, 0) == vgetq_lane_u64(v2, 0)) && \
+         (vgetq_lane_u64(v1, 1) == vgetq_lane_u64(v2, 1)))
+#define VEC_OR(v1, v2) ((v1) | (v2))
+#else
+#define VECTYPE        unsigned long
+#define SPLAT(p)       (*(p) * (~0UL / 255))
+#define ALL_EQ(v1, v2) ((v1) == (v2))
+#define VEC_OR(v1, v2) ((v1) | (v2))
+#endif
+
+#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8
+
+static bool
+can_use_buffer_find_nonzero_offset_inner(const void *buf, size_t len)
+{
+    return (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
+                   * sizeof(VECTYPE)) == 0
+            && ((uintptr_t) buf) % sizeof(VECTYPE) == 0);
+}
+
+/*
+ * Searches for an area with non-zero content in a buffer
+ *
+ * Attention! The len must be a multiple of
+ * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE)
+ * and addr must be a multiple of sizeof(VECTYPE) due to
+ * restriction of optimizations in this function.
+ *
+ * can_use_buffer_find_nonzero_offset_inner() can be used to
+ * check these requirements.
+ *
+ * The return value is the offset of the non-zero area rounded
+ * down to a multiple of sizeof(VECTYPE) for the first
+ * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR chunks and down to
+ * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE)
+ * afterwards.
+ *
+ * If the buffer is all zero the return value is equal to len.
+ */
+
+static size_t buffer_find_nonzero_offset_inner(const void *buf, size_t len)
+{
+    const VECTYPE *p = buf;
+    const VECTYPE zero = (VECTYPE){0};
+    size_t i;
+
+    assert(can_use_buffer_find_nonzero_offset_inner(buf, len));
+
+    if (!len) {
+        return 0;
+    }
+
+    for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) {
+        if (!ALL_EQ(p[i], zero)) {
+            return i * sizeof(VECTYPE);
+        }
+    }
+
+    for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
+         i < len / sizeof(VECTYPE);
+         i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
+        VECTYPE tmp0 = VEC_OR(p[i + 0], p[i + 1]);
+        VECTYPE tmp1 = VEC_OR(p[i + 2], p[i + 3]);
+        VECTYPE tmp2 = VEC_OR(p[i + 4], p[i + 5]);
+        VECTYPE tmp3 = VEC_OR(p[i + 6], p[i + 7]);
+        VECTYPE tmp01 = VEC_OR(tmp0, tmp1);
+        VECTYPE tmp23 = VEC_OR(tmp2, tmp3);
+        if (!ALL_EQ(VEC_OR(tmp01, tmp23), zero)) {
+            break;
+        }
+    }
+
+    return i * sizeof(VECTYPE);
+}
+
+#if defined CONFIG_AVX2_OPT
+#pragma GCC push_options
+#pragma GCC target("avx2")
+#include <cpuid.h>
+#include <immintrin.h>
+
+#define AVX2_VECTYPE        __m256i
+#define AVX2_SPLAT(p)       _mm256_set1_epi8(*(p))
+#define AVX2_ALL_EQ(v1, v2) \
+    (_mm256_movemask_epi8(_mm256_cmpeq_epi8(v1, v2)) == 0xFFFFFFFF)
+#define AVX2_VEC_OR(v1, v2) (_mm256_or_si256(v1, v2))
+
+static bool
+can_use_buffer_find_nonzero_offset_avx2(const void *buf, size_t len)
+{
+    return (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
+                   * sizeof(AVX2_VECTYPE)) == 0
+            && ((uintptr_t) buf) % sizeof(AVX2_VECTYPE) == 0);
+}
+
+static size_t buffer_find_nonzero_offset_avx2(const void *buf, size_t len)
+{
+    const AVX2_VECTYPE *p = buf;
+    const AVX2_VECTYPE zero = (AVX2_VECTYPE){0};
+    size_t i;
+
+    assert(can_use_buffer_find_nonzero_offset_avx2(buf, len));
+
+    if (!len) {
+        return 0;
+    }
+
+    for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) {
+        if (!AVX2_ALL_EQ(p[i], zero)) {
+            return i * sizeof(AVX2_VECTYPE);
+        }
+    }
+
+    for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
+         i < len / sizeof(AVX2_VECTYPE);
+         i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
+        AVX2_VECTYPE tmp0 = AVX2_VEC_OR(p[i + 0], p[i + 1]);
+        AVX2_VECTYPE tmp1 = AVX2_VEC_OR(p[i + 2], p[i + 3]);
+        AVX2_VECTYPE tmp2 = AVX2_VEC_OR(p[i + 4], p[i + 5]);
+        AVX2_VECTYPE tmp3 = AVX2_VEC_OR(p[i + 6], p[i + 7]);
+        AVX2_VECTYPE tmp01 = AVX2_VEC_OR(tmp0, tmp1);
+        AVX2_VECTYPE tmp23 = AVX2_VEC_OR(tmp2, tmp3);
+        if (!AVX2_ALL_EQ(AVX2_VEC_OR(tmp01, tmp23), zero)) {
+            break;
+        }
+    }
+
+    return i * sizeof(AVX2_VECTYPE);
+}
+
+static bool avx2_support(void)
+{
+    int a, b, c, d;
+
+    if (__get_cpuid_max(0, NULL) < 7) {
+        return false;
+    }
+
+    __cpuid_count(7, 0, a, b, c, d);
+
+    return b & bit_AVX2;
+}
+
+bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len) \
+         __attribute__ ((ifunc("can_use_buffer_find_nonzero_offset_ifunc")));
+size_t buffer_find_nonzero_offset(const void *buf, size_t len) \
+         __attribute__ ((ifunc("buffer_find_nonzero_offset_ifunc")));
+
+static void *buffer_find_nonzero_offset_ifunc(void)
+{
+    typeof(buffer_find_nonzero_offset) *func = (avx2_support()) ?
+        buffer_find_nonzero_offset_avx2 : buffer_find_nonzero_offset_inner;
+
+    return func;
+}
+
+static void *can_use_buffer_find_nonzero_offset_ifunc(void)
+{
+    typeof(can_use_buffer_find_nonzero_offset) *func = (avx2_support()) ?
+        can_use_buffer_find_nonzero_offset_avx2 :
+        can_use_buffer_find_nonzero_offset_inner;
+
+    return func;
+}
+#pragma GCC pop_options
+#else
+bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len)
+{
+    return can_use_buffer_find_nonzero_offset_inner(buf, len);
+}
+
+size_t buffer_find_nonzero_offset(const void *buf, size_t len)
+{
+    return buffer_find_nonzero_offset_inner(buf, len);
+}
+#endif
+
+/*
+ * Checks if a buffer is all zeroes
+ *
+ * Attention! The len must be a multiple of 4 * sizeof(long) due to
+ * restriction of optimizations in this function.
+ */
+bool buffer_is_zero(const void *buf, size_t len)
+{
+    /*
+     * Use long as the biggest available internal data type that fits into the
+     * CPU register and unroll the loop to smooth out the effect of memory
+     * latency.
+     */
+
+    size_t i;
+    long d0, d1, d2, d3;
+    const long * const data = buf;
+
+    /* use vector optimized zero check if possible */
+    if (can_use_buffer_find_nonzero_offset(buf, len)) {
+        return buffer_find_nonzero_offset(buf, len) == len;
+    }
+
+    assert(len % (4 * sizeof(long)) == 0);
+    len /= sizeof(long);
+
+    for (i = 0; i < len; i += 4) {
+        d0 = data[i + 0];
+        d1 = data[i + 1];
+        d2 = data[i + 2];
+        d3 = data[i + 3];
+
+        if (d0 || d1 || d2 || d3) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
diff --git a/util/cutils.c b/util/cutils.c
index 7505fda..4fefcf3 100644
--- a/util/cutils.c
+++ b/util/cutils.c
@@ -161,250 +161,6 @@ int qemu_fdatasync(int fd)
 #endif
 }
 
-/* vector definitions */
-#ifdef __ALTIVEC__
-#include <altivec.h>
-/* The altivec.h header says we're allowed to undef these for
- * C++ compatibility.  Here we don't care about C++, but we
- * undef them anyway to avoid namespace pollution.
- */
-#undef vector
-#undef pixel
-#undef bool
-#define VECTYPE        __vector unsigned char
-#define SPLAT(p)       vec_splat(vec_ld(0, p), 0)
-#define ALL_EQ(v1, v2) vec_all_eq(v1, v2)
-#define VEC_OR(v1, v2) ((v1) | (v2))
-/* altivec.h may redefine the bool macro as vector type.
- * Reset it to POSIX semantics. */
-#define bool _Bool
-#elif defined __SSE2__
-#include <emmintrin.h>
-#define VECTYPE        __m128i
-#define SPLAT(p)       _mm_set1_epi8(*(p))
-#define ALL_EQ(v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF)
-#define VEC_OR(v1, v2) (_mm_or_si128(v1, v2))
-#elif defined(__aarch64__)
-#include "arm_neon.h"
-#define VECTYPE        uint64x2_t
-#define ALL_EQ(v1, v2) \
-        ((vgetq_lane_u64(v1, 0) == vgetq_lane_u64(v2, 0)) && \
-         (vgetq_lane_u64(v1, 1) == vgetq_lane_u64(v2, 1)))
-#define VEC_OR(v1, v2) ((v1) | (v2))
-#else
-#define VECTYPE        unsigned long
-#define SPLAT(p)       (*(p) * (~0UL / 255))
-#define ALL_EQ(v1, v2) ((v1) == (v2))
-#define VEC_OR(v1, v2) ((v1) | (v2))
-#endif
-
-#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8
-
-static bool
-can_use_buffer_find_nonzero_offset_inner(const void *buf, size_t len)
-{
-    return (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
-                   * sizeof(VECTYPE)) == 0
-            && ((uintptr_t) buf) % sizeof(VECTYPE) == 0);
-}
-
-/*
- * Searches for an area with non-zero content in a buffer
- *
- * Attention! The len must be a multiple of
- * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE)
- * and addr must be a multiple of sizeof(VECTYPE) due to
- * restriction of optimizations in this function.
- *
- * can_use_buffer_find_nonzero_offset_inner() can be used to
- * check these requirements.
- *
- * The return value is the offset of the non-zero area rounded
- * down to a multiple of sizeof(VECTYPE) for the first
- * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR chunks and down to
- * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE)
- * afterwards.
- *
- * If the buffer is all zero the return value is equal to len.
- */
-
-static size_t buffer_find_nonzero_offset_inner(const void *buf, size_t len)
-{
-    const VECTYPE *p = buf;
-    const VECTYPE zero = (VECTYPE){0};
-    size_t i;
-
-    assert(can_use_buffer_find_nonzero_offset_inner(buf, len));
-
-    if (!len) {
-        return 0;
-    }
-
-    for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) {
-        if (!ALL_EQ(p[i], zero)) {
-            return i * sizeof(VECTYPE);
-        }
-    }
-
-    for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
-         i < len / sizeof(VECTYPE);
-         i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
-        VECTYPE tmp0 = VEC_OR(p[i + 0], p[i + 1]);
-        VECTYPE tmp1 = VEC_OR(p[i + 2], p[i + 3]);
-        VECTYPE tmp2 = VEC_OR(p[i + 4], p[i + 5]);
-        VECTYPE tmp3 = VEC_OR(p[i + 6], p[i + 7]);
-        VECTYPE tmp01 = VEC_OR(tmp0, tmp1);
-        VECTYPE tmp23 = VEC_OR(tmp2, tmp3);
-        if (!ALL_EQ(VEC_OR(tmp01, tmp23), zero)) {
-            break;
-        }
-    }
-
-    return i * sizeof(VECTYPE);
-}
-
-#if defined CONFIG_AVX2_OPT
-#pragma GCC push_options
-#pragma GCC target("avx2")
-#include <cpuid.h>
-#include <immintrin.h>
-
-#define AVX2_VECTYPE        __m256i
-#define AVX2_SPLAT(p)       _mm256_set1_epi8(*(p))
-#define AVX2_ALL_EQ(v1, v2) \
-    (_mm256_movemask_epi8(_mm256_cmpeq_epi8(v1, v2)) == 0xFFFFFFFF)
-#define AVX2_VEC_OR(v1, v2) (_mm256_or_si256(v1, v2))
-
-static bool
-can_use_buffer_find_nonzero_offset_avx2(const void *buf, size_t len)
-{
-    return (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
-                   * sizeof(AVX2_VECTYPE)) == 0
-            && ((uintptr_t) buf) % sizeof(AVX2_VECTYPE) == 0);
-}
-
-static size_t buffer_find_nonzero_offset_avx2(const void *buf, size_t len)
-{
-    const AVX2_VECTYPE *p = buf;
-    const AVX2_VECTYPE zero = (AVX2_VECTYPE){0};
-    size_t i;
-
-    assert(can_use_buffer_find_nonzero_offset_avx2(buf, len));
-
-    if (!len) {
-        return 0;
-    }
-
-    for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) {
-        if (!AVX2_ALL_EQ(p[i], zero)) {
-            return i * sizeof(AVX2_VECTYPE);
-        }
-    }
-
-    for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
-         i < len / sizeof(AVX2_VECTYPE);
-         i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
-        AVX2_VECTYPE tmp0 = AVX2_VEC_OR(p[i + 0], p[i + 1]);
-        AVX2_VECTYPE tmp1 = AVX2_VEC_OR(p[i + 2], p[i + 3]);
-        AVX2_VECTYPE tmp2 = AVX2_VEC_OR(p[i + 4], p[i + 5]);
-        AVX2_VECTYPE tmp3 = AVX2_VEC_OR(p[i + 6], p[i + 7]);
-        AVX2_VECTYPE tmp01 = AVX2_VEC_OR(tmp0, tmp1);
-        AVX2_VECTYPE tmp23 = AVX2_VEC_OR(tmp2, tmp3);
-        if (!AVX2_ALL_EQ(AVX2_VEC_OR(tmp01, tmp23), zero)) {
-            break;
-        }
-    }
-
-    return i * sizeof(AVX2_VECTYPE);
-}
-
-static bool avx2_support(void)
-{
-    int a, b, c, d;
-
-    if (__get_cpuid_max(0, NULL) < 7) {
-        return false;
-    }
-
-    __cpuid_count(7, 0, a, b, c, d);
-
-    return b & bit_AVX2;
-}
-
-bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len) \
-         __attribute__ ((ifunc("can_use_buffer_find_nonzero_offset_ifunc")));
-size_t buffer_find_nonzero_offset(const void *buf, size_t len) \
-         __attribute__ ((ifunc("buffer_find_nonzero_offset_ifunc")));
-
-static void *buffer_find_nonzero_offset_ifunc(void)
-{
-    typeof(buffer_find_nonzero_offset) *func = (avx2_support()) ?
-        buffer_find_nonzero_offset_avx2 : buffer_find_nonzero_offset_inner;
-
-    return func;
-}
-
-static void *can_use_buffer_find_nonzero_offset_ifunc(void)
-{
-    typeof(can_use_buffer_find_nonzero_offset) *func = (avx2_support()) ?
-        can_use_buffer_find_nonzero_offset_avx2 :
-        can_use_buffer_find_nonzero_offset_inner;
-
-    return func;
-}
-#pragma GCC pop_options
-#else
-bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len)
-{
-    return can_use_buffer_find_nonzero_offset_inner(buf, len);
-}
-
-size_t buffer_find_nonzero_offset(const void *buf, size_t len)
-{
-    return buffer_find_nonzero_offset_inner(buf, len);
-}
-#endif
-
-/*
- * Checks if a buffer is all zeroes
- *
- * Attention! The len must be a multiple of 4 * sizeof(long) due to
- * restriction of optimizations in this function.
- */
-bool buffer_is_zero(const void *buf, size_t len)
-{
-    /*
-     * Use long as the biggest available internal data type that fits into the
-     * CPU register and unroll the loop to smooth out the effect of memory
-     * latency.
-     */
-
-    size_t i;
-    long d0, d1, d2, d3;
-    const long * const data = buf;
-
-    /* use vector optimized zero check if possible */
-    if (can_use_buffer_find_nonzero_offset(buf, len)) {
-        return buffer_find_nonzero_offset(buf, len) == len;
-    }
-
-    assert(len % (4 * sizeof(long)) == 0);
-    len /= sizeof(long);
-
-    for (i = 0; i < len; i += 4) {
-        d0 = data[i + 0];
-        d1 = data[i + 1];
-        d2 = data[i + 2];
-        d3 = data[i + 3];
-
-        if (d0 || d1 || d2 || d3) {
-            return false;
-        }
-    }
-
-    return true;
-}
-
 #ifndef _WIN32
 /* Sets a specific flag */
 int fcntl_setfl(int fd, int flag)
-- 
2.7.4

[Qemu-devel] [PATCH v3 3/9] cutils: Export only buffer_is_zero

[Richard Henderson]

Since the two users don't make use of the returned offset,
beyond ensuring that the entire buffer is zero, consider the
can_use_buffer_find_nonzero_offset and buffer_find_nonzero_offset
functions internal.

Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
Signed-off-by: Richard Henderson <rth@twiddle.net>
---
 include/qemu/cutils.h | 2 --
 migration/ram.c       | 2 +-
 migration/rdma.c      | 5 +----
 util/bufferiszero.c   | 8 ++++----
 4 files changed, 6 insertions(+), 11 deletions(-)

diff --git a/include/qemu/cutils.h b/include/qemu/cutils.h
index 3e4ea23..ca58577 100644
--- a/include/qemu/cutils.h
+++ b/include/qemu/cutils.h
@@ -168,8 +168,6 @@ int64_t qemu_strtosz_suffix_unit(const char *nptr, char **end,
 /* used to print char* safely */
 #define STR_OR_NULL(str) ((str) ? (str) : "null")
 
-bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len);
-size_t buffer_find_nonzero_offset(const void *buf, size_t len);
 bool buffer_is_zero(const void *buf, size_t len);
 
 /*
diff --git a/migration/ram.c b/migration/ram.c
index a3d70c4..a6e1c63 100644
--- a/migration/ram.c
+++ b/migration/ram.c
@@ -73,7 +73,7 @@ static const uint8_t ZERO_TARGET_PAGE[TARGET_PAGE_SIZE];
 
 static inline bool is_zero_range(uint8_t *p, uint64_t size)
 {
-    return buffer_find_nonzero_offset(p, size) == size;
+    return buffer_is_zero(p, size);
 }
 
 /* struct contains XBZRLE cache and a static page
diff --git a/migration/rdma.c b/migration/rdma.c
index 5110ec8..88bdb64 100644
--- a/migration/rdma.c
+++ b/migration/rdma.c
@@ -1934,10 +1934,7 @@ retry:
              * memset() + madvise() the entire chunk without RDMA.
              */
 
-            if (can_use_buffer_find_nonzero_offset((void *)(uintptr_t)sge.addr,
-                                                   length)
-                   && buffer_find_nonzero_offset((void *)(uintptr_t)sge.addr,
-                                                    length) == length) {
+            if (buffer_is_zero((void *)(uintptr_t)sge.addr, length)) {
                 RDMACompress comp = {
                                         .offset = current_addr,
                                         .value = 0,
diff --git a/util/bufferiszero.c b/util/bufferiszero.c
index 067d08f..0cf8b6e 100644
--- a/util/bufferiszero.c
+++ b/util/bufferiszero.c
@@ -192,9 +192,9 @@ static bool avx2_support(void)
     return b & bit_AVX2;
 }
 
-bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len) \
+static bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len) \
          __attribute__ ((ifunc("can_use_buffer_find_nonzero_offset_ifunc")));
-size_t buffer_find_nonzero_offset(const void *buf, size_t len) \
+static size_t buffer_find_nonzero_offset(const void *buf, size_t len) \
          __attribute__ ((ifunc("buffer_find_nonzero_offset_ifunc")));
 
 static void *buffer_find_nonzero_offset_ifunc(void)
@@ -215,12 +215,12 @@ static void *can_use_buffer_find_nonzero_offset_ifunc(void)
 }
 #pragma GCC pop_options
 #else
-bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len)
+static bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len)
 {
     return can_use_buffer_find_nonzero_offset_inner(buf, len);
 }
 
-size_t buffer_find_nonzero_offset(const void *buf, size_t len)
+static size_t buffer_find_nonzero_offset(const void *buf, size_t len)
 {
     return buffer_find_nonzero_offset_inner(buf, len);
 }
-- 
2.7.4

[Qemu-devel] [PATCH v3 4/9] cutils: Rearrange buffer_is_zero acceleration

[Richard Henderson]

Allow selection of several acceleration functions
based on the size and alignment of the buffer.
Do not require ifunc support for AVX2 acceleration.

Signed-off-by: Richard Henderson <rth@twiddle.net>
---
 configure           |  21 +---
 util/bufferiszero.c | 349 ++++++++++++++++++++++++----------------------------
 2 files changed, 166 insertions(+), 204 deletions(-)

diff --git a/configure b/configure
index 4b808f9..9f3d1fa 100755
--- a/configure
+++ b/configure
@@ -1788,28 +1788,19 @@ fi
 ##########################################
 # avx2 optimization requirement check
 
-
-if test "$static" = "no" ; then
-  cat > $TMPC << EOF
+cat > $TMPC << EOF
 #pragma GCC push_options
 #pragma GCC target("avx2")
 #include <cpuid.h>
 #include <immintrin.h>
-
 static int bar(void *a) {
-    return _mm256_movemask_epi8(_mm256_cmpeq_epi8(*(__m256i *)a, (__m256i){0}));
+    __m256i x = *(__m256i *)a;
+    return _mm256_testz_si256(x, x);
 }
-static void *bar_ifunc(void) {return (void*) bar;}
-int foo(void *a) __attribute__((ifunc("bar_ifunc")));
-int main(int argc, char *argv[]) { return foo(argv[0]);}
+int main(int argc, char *argv[]) { return bar(argv[0]); }
 EOF
-  if compile_object "" ; then
-      if has readelf; then
-          if readelf --syms $TMPO 2>/dev/null |grep -q "IFUNC.*foo"; then
-              avx2_opt="yes"
-          fi
-      fi
-  fi
+if compile_object "" ; then
+  avx2_opt="yes"
 fi
 
 #########################################
diff --git a/util/bufferiszero.c b/util/bufferiszero.c
index 0cf8b6e..89224f4 100644
--- a/util/bufferiszero.c
+++ b/util/bufferiszero.c
@@ -24,245 +24,216 @@
 #include "qemu/osdep.h"
 #include "qemu-common.h"
 #include "qemu/cutils.h"
+#include "qemu/bswap.h"
 
 
 /* vector definitions */
+
+extern void link_error(void);
+
+#define ACCEL_BUFFER_ZERO(NAME, SIZE, VECTYPE, NONZERO)         \
+static bool NAME(const void *buf, size_t len)                   \
+{                                                               \
+    const void *end = buf + len;                                \
+    do {                                                        \
+        const VECTYPE *p = buf;                                 \
+        VECTYPE t;                                              \
+        if (SIZE == sizeof(VECTYPE) * 4) {                      \
+            t = (p[0] | p[1]) | (p[2] | p[3]);                  \
+        } else if (SIZE == sizeof(VECTYPE) * 8) {               \
+            t  = p[0] | p[1];                                   \
+            t |= p[2] | p[3];                                   \
+            t |= p[4] | p[5];                                   \
+            t |= p[6] | p[7];                                   \
+        } else {                                                \
+            link_error();                                       \
+        }                                                       \
+        if (unlikely(NONZERO(t))) {                             \
+            return false;                                       \
+        }                                                       \
+        buf += SIZE;                                            \
+    } while (buf < end);                                        \
+    return true;                                                \
+}
+
+typedef bool (*accel_zero_fn)(const void *, size_t);
+
+static bool
+buffer_zero_int(const void *buf, size_t len)
+{
+    if (unlikely(len < 8)) {
+        /* For a very small buffer, simply accumulate all the bytes.  */
+        const unsigned char *p = buf;
+        const unsigned char *e = buf + len;
+        unsigned char t = 0;
+
+        do {
+            t |= *p++;
+        } while (p < e);
+
+        return t == 0;
+    } else {
+        /* Otherwise, use the unaligned memory access functions to
+           handle the beginning and end of the buffer, with a couple
+           of loops handling the middle aligned section.  */
+        uint64_t t = ldq_he_p(buf);
+        const uint64_t *p = (uint64_t *)(((uintptr_t)buf + 8) & -8);
+        const uint64_t *e = (uint64_t *)(((uintptr_t)buf + len) & -8);
+
+        for (; p + 8 <= e; p += 8) {
+            __builtin_prefetch(p + 8);
+            if (t) {
+                return false;
+            }
+            t = p[0] | p[1] | p[2] | p[3] | p[4] | p[5] | p[6] | p[7];
+        }
+        while (p < e) {
+            t |= *p++;
+        }
+        t |= ldq_he_p(buf + len - 8);
+
+        return t == 0;
+    }
+}
+
 #ifdef __ALTIVEC__
 #include <altivec.h>
 /* The altivec.h header says we're allowed to undef these for
  * C++ compatibility.  Here we don't care about C++, but we
  * undef them anyway to avoid namespace pollution.
+ * altivec.h may redefine the bool macro as vector type.
+ * Reset it to POSIX semantics.
  */
 #undef vector
 #undef pixel
 #undef bool
-#define VECTYPE        __vector unsigned char
-#define ALL_EQ(v1, v2) vec_all_eq(v1, v2)
-#define VEC_OR(v1, v2) ((v1) | (v2))
-/* altivec.h may redefine the bool macro as vector type.
- * Reset it to POSIX semantics. */
 #define bool _Bool
-#elif defined __SSE2__
-#include <emmintrin.h>
-#define VECTYPE        __m128i
-#define ALL_EQ(v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF)
-#define VEC_OR(v1, v2) (_mm_or_si128(v1, v2))
-#elif defined(__aarch64__)
-#include "arm_neon.h"
-#define VECTYPE        uint64x2_t
-#define ALL_EQ(v1, v2) \
-        ((vgetq_lane_u64(v1, 0) == vgetq_lane_u64(v2, 0)) && \
-         (vgetq_lane_u64(v1, 1) == vgetq_lane_u64(v2, 1)))
-#define VEC_OR(v1, v2) ((v1) | (v2))
-#else
-#define VECTYPE        unsigned long
-#define ALL_EQ(v1, v2) ((v1) == (v2))
-#define VEC_OR(v1, v2) ((v1) | (v2))
-#endif
-
-#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8
+#define DO_NONZERO(X)  vec_any_ne(X, (__vector unsigned char){ 0 })
+ACCEL_BUFFER_ZERO(buffer_zero_ppc, 128, __vector unsigned char, DO_NONZERO)
 
-static bool
-can_use_buffer_find_nonzero_offset_inner(const void *buf, size_t len)
+static bool select_accel_fn(const void *buf, size_t len)
 {
-    return (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
-                   * sizeof(VECTYPE)) == 0
-            && ((uintptr_t) buf) % sizeof(VECTYPE) == 0);
-}
-
-/*
- * Searches for an area with non-zero content in a buffer
- *
- * Attention! The len must be a multiple of
- * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE)
- * and addr must be a multiple of sizeof(VECTYPE) due to
- * restriction of optimizations in this function.
- *
- * can_use_buffer_find_nonzero_offset_inner() can be used to
- * check these requirements.
- *
- * The return value is the offset of the non-zero area rounded
- * down to a multiple of sizeof(VECTYPE) for the first
- * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR chunks and down to
- * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE)
- * afterwards.
- *
- * If the buffer is all zero the return value is equal to len.
- */
-
-static size_t buffer_find_nonzero_offset_inner(const void *buf, size_t len)
-{
-    const VECTYPE *p = buf;
-    const VECTYPE zero = (VECTYPE){0};
-    size_t i;
-
-    assert(can_use_buffer_find_nonzero_offset_inner(buf, len));
-
-    if (!len) {
-        return 0;
+    uintptr_t ibuf = (uintptr_t)buf;
+    if (len % 128 == 0 && ibuf % sizeof(__vector unsigned char) == 0) {
+        return buffer_zero_ppc(buf, len);
     }
-
-    for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) {
-        if (!ALL_EQ(p[i], zero)) {
-            return i * sizeof(VECTYPE);
-        }
-    }
-
-    for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
-         i < len / sizeof(VECTYPE);
-         i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
-        VECTYPE tmp0 = VEC_OR(p[i + 0], p[i + 1]);
-        VECTYPE tmp1 = VEC_OR(p[i + 2], p[i + 3]);
-        VECTYPE tmp2 = VEC_OR(p[i + 4], p[i + 5]);
-        VECTYPE tmp3 = VEC_OR(p[i + 6], p[i + 7]);
-        VECTYPE tmp01 = VEC_OR(tmp0, tmp1);
-        VECTYPE tmp23 = VEC_OR(tmp2, tmp3);
-        if (!ALL_EQ(VEC_OR(tmp01, tmp23), zero)) {
-            break;
-        }
-    }
-
-    return i * sizeof(VECTYPE);
+    return buffer_zero_int(buf, len);
 }
 
-#if defined CONFIG_AVX2_OPT
-#pragma GCC push_options
-#pragma GCC target("avx2")
+#elif defined(CONFIG_AVX2_OPT)
 #include <cpuid.h>
-#include <immintrin.h>
+#include <x86intrin.h>
 
-#define AVX2_VECTYPE        __m256i
-#define AVX2_ALL_EQ(v1, v2) \
-    (_mm256_movemask_epi8(_mm256_cmpeq_epi8(v1, v2)) == 0xFFFFFFFF)
-#define AVX2_VEC_OR(v1, v2) (_mm256_or_si256(v1, v2))
+#pragma GCC push_options
+#pragma GCC target("avx2")
+#define AVX2_NONZERO(X)  !_mm256_testz_si256((X), (X))
+ACCEL_BUFFER_ZERO(buffer_zero_avx2, 128, __m256i, AVX2_NONZERO)
+#pragma GCC pop_options
 
-static bool
-can_use_buffer_find_nonzero_offset_avx2(const void *buf, size_t len)
-{
-    return (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
-                   * sizeof(AVX2_VECTYPE)) == 0
-            && ((uintptr_t) buf) % sizeof(AVX2_VECTYPE) == 0);
-}
+#pragma GCC push_options
+#pragma GCC target("sse2")
+#define SSE2_NONZERO(X) \
+    (_mm_movemask_epi8(_mm_cmpeq_epi8((X), _mm_setzero_si128())) != 0xFFFF)
+ACCEL_BUFFER_ZERO(buffer_zero_sse2, 64, __m128i, SSE2_NONZERO)
+#pragma GCC pop_options
 
-static size_t buffer_find_nonzero_offset_avx2(const void *buf, size_t len)
-{
-    const AVX2_VECTYPE *p = buf;
-    const AVX2_VECTYPE zero = (AVX2_VECTYPE){0};
-    size_t i;
+#define CACHE_AVX2    2
+#define CACHE_AVX1    4
+#define CACHE_SSE4    8
+#define CACHE_SSE2    16
 
-    assert(can_use_buffer_find_nonzero_offset_avx2(buf, len));
+static unsigned cpuid_cache;
 
-    if (!len) {
-        return 0;
-    }
+static void __attribute__((constructor)) init_cpuid_cache(void)
+{
+    int max = __get_cpuid_max(0, NULL);
+    int a, b, c, d;
+    unsigned cache = 0;
 
-    for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) {
-        if (!AVX2_ALL_EQ(p[i], zero)) {
-            return i * sizeof(AVX2_VECTYPE);
+    if (max >= 1) {
+        __cpuid(1, a, b, c, d);
+        if (d & bit_SSE2) {
+            cache |= CACHE_SSE2;
+        }
+        if (c & bit_SSE4_1) {
+            cache |= CACHE_SSE4;
         }
-    }
 
-    for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
-         i < len / sizeof(AVX2_VECTYPE);
-         i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
-        AVX2_VECTYPE tmp0 = AVX2_VEC_OR(p[i + 0], p[i + 1]);
-        AVX2_VECTYPE tmp1 = AVX2_VEC_OR(p[i + 2], p[i + 3]);
-        AVX2_VECTYPE tmp2 = AVX2_VEC_OR(p[i + 4], p[i + 5]);
-        AVX2_VECTYPE tmp3 = AVX2_VEC_OR(p[i + 6], p[i + 7]);
-        AVX2_VECTYPE tmp01 = AVX2_VEC_OR(tmp0, tmp1);
-        AVX2_VECTYPE tmp23 = AVX2_VEC_OR(tmp2, tmp3);
-        if (!AVX2_ALL_EQ(AVX2_VEC_OR(tmp01, tmp23), zero)) {
-            break;
+        /* We must check that AVX is not just available, but usable.  */
+        if ((c & bit_OSXSAVE) && (c & bit_AVX)) {
+            __asm("xgetbv" : "=a"(a), "=d"(d) : "c"(0));
+            if ((a & 6) == 6) {
+                cache |= CACHE_AVX1;
+                if (max >= 7) {
+                    __cpuid_count(7, 0, a, b, c, d);
+                    if (b & bit_AVX2) {
+                        cache |= CACHE_AVX2;
+                    }
+                }
+            }
         }
     }
-
-    return i * sizeof(AVX2_VECTYPE);
+    cpuid_cache = cache;
 }
 
-static bool avx2_support(void)
+static bool select_accel_fn(const void *buf, size_t len)
 {
-    int a, b, c, d;
-
-    if (__get_cpuid_max(0, NULL) < 7) {
-        return false;
+    uintptr_t ibuf = (uintptr_t)buf;
+    if (len % 128 == 0 && ibuf % 32 == 0 && (cpuid_cache & CACHE_AVX2)) {
+        return buffer_zero_avx2(buf, len);
     }
-
-    __cpuid_count(7, 0, a, b, c, d);
-
-    return b & bit_AVX2;
+    if (len % 64 == 0 && ibuf % 16 == 0 && (cpuid_cache & CACHE_SSE2)) {
+        return buffer_zero_sse2(buf, len);
+    }
+    return buffer_zero_int(buf, len);
 }
 
-static bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len) \
-         __attribute__ ((ifunc("can_use_buffer_find_nonzero_offset_ifunc")));
-static size_t buffer_find_nonzero_offset(const void *buf, size_t len) \
-         __attribute__ ((ifunc("buffer_find_nonzero_offset_ifunc")));
+#elif defined __SSE2__
+#include <emmintrin.h>
 
-static void *buffer_find_nonzero_offset_ifunc(void)
-{
-    typeof(buffer_find_nonzero_offset) *func = (avx2_support()) ?
-        buffer_find_nonzero_offset_avx2 : buffer_find_nonzero_offset_inner;
+#define SSE2_NONZERO(X) \
+    (_mm_movemask_epi8(_mm_cmpeq_epi8((X), _mm_setzero_si128())) != 0xFFFF)
+ACCEL_BUFFER_ZERO(buffer_zero_sse2, 64, __m128i, SSE2_NONZERO)
 
-    return func;
+static bool select_accel_fn(const void *buf, size_t len)
+{
+    uintptr_t ibuf = (uintptr_t)buf;
+    if (len % 64 == 0 && ibuf % sizeof(__m128i) == 0) {
+        return buffer_zero_sse2(buf, len);
+    }
+    return select_accel_int(buf, len);
 }
 
-static void *can_use_buffer_find_nonzero_offset_ifunc(void)
-{
-    typeof(can_use_buffer_find_nonzero_offset) *func = (avx2_support()) ?
-        can_use_buffer_find_nonzero_offset_avx2 :
-        can_use_buffer_find_nonzero_offset_inner;
+#elif defined(__aarch64__)
+#include "arm_neon.h"
 
-    return func;
-}
-#pragma GCC pop_options
-#else
-static bool can_use_buffer_find_nonzero_offset(const void *buf, size_t len)
-{
-    return can_use_buffer_find_nonzero_offset_inner(buf, len);
-}
+#define DO_NONZERO(X)  (vgetq_lane_u64((X), 0) | vgetq_lane_u64((X), 1))
+ACCEL_BUFFER_ZERO(buffer_zero_neon, 128, uint64x2_t, DO_NONZERO)
 
-static size_t buffer_find_nonzero_offset(const void *buf, size_t len)
+static bool select_accel_fn(const void *buf, size_t len)
 {
-    return buffer_find_nonzero_offset_inner(buf, len);
+    uintptr_t ibuf = (uintptr_t)buf;
+    if (len % 128 == 0 && ibuf % sizeof(uint64x2_t) == 0) {
+        return buffer_zero_neon(buf, len);
+    }
+    return buffer_zero_int(buf, len);
 }
+
+#else
+#define select_accel_fn  buffer_zero_int
 #endif
 
 /*
  * Checks if a buffer is all zeroes
- *
- * Attention! The len must be a multiple of 4 * sizeof(long) due to
- * restriction of optimizations in this function.
  */
 bool buffer_is_zero(const void *buf, size_t len)
 {
-    /*
-     * Use long as the biggest available internal data type that fits into the
-     * CPU register and unroll the loop to smooth out the effect of memory
-     * latency.
-     */
-
-    size_t i;
-    long d0, d1, d2, d3;
-    const long * const data = buf;
-
-    /* use vector optimized zero check if possible */
-    if (can_use_buffer_find_nonzero_offset(buf, len)) {
-        return buffer_find_nonzero_offset(buf, len) == len;
-    }
-
-    assert(len % (4 * sizeof(long)) == 0);
-    len /= sizeof(long);
-
-    for (i = 0; i < len; i += 4) {
-        d0 = data[i + 0];
-        d1 = data[i + 1];
-        d2 = data[i + 2];
-        d3 = data[i + 3];
-
-        if (d0 || d1 || d2 || d3) {
-            return false;
-        }
+    if (unlikely(len == 0)) {
+        return true;
     }
 
-    return true;
+    /* Use an optimized zero check if possible.  Note that this also
+       includes a check for an unrolled loop over longs, as well as
+       the unsized, unaligned fallback to buffer_zero_base.  */
+    return select_accel_fn(buf, len);
 }
-
-- 
2.7.4

[Qemu-devel] [PATCH v3 5/9] cutils: Add test for buffer_is_zero

[Richard Henderson]

Signed-off-by: Richard Henderson <rth@twiddle.net>
---
 include/qemu/cutils.h     |  1 +
 tests/Makefile.include    |  3 ++
 tests/test-bufferiszero.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++
 util/bufferiszero.c       |  7 +++++
 4 files changed, 89 insertions(+)
 create mode 100644 tests/test-bufferiszero.c

diff --git a/include/qemu/cutils.h b/include/qemu/cutils.h
index ca58577..8033929 100644
--- a/include/qemu/cutils.h
+++ b/include/qemu/cutils.h
@@ -169,6 +169,7 @@ int64_t qemu_strtosz_suffix_unit(const char *nptr, char **end,
 #define STR_OR_NULL(str) ((str) ? (str) : "null")
 
 bool buffer_is_zero(const void *buf, size_t len);
+bool test_buffer_is_zero_next_accel(void);
 
 /*
  * Implementation of ULEB128 (http://en.wikipedia.org/wiki/LEB128)
diff --git a/tests/Makefile.include b/tests/Makefile.include
index 14be491..1f053b1 100644
--- a/tests/Makefile.include
+++ b/tests/Makefile.include
@@ -112,6 +112,8 @@ check-unit-y += tests/test-crypto-xts$(EXESUF)
 check-unit-y += tests/test-crypto-block$(EXESUF)
 gcov-files-test-logging-y = tests/test-logging.c
 check-unit-y += tests/test-logging$(EXESUF)
+check-unit-y += tests/test-bufferiszero$(EXESUF)
+gcov-files-check-bufferiszero-y = util/bufferiszero.c
 
 check-block-$(CONFIG_POSIX) += tests/qemu-iotests-quick.sh
 
@@ -465,6 +467,7 @@ tests/test-qdist$(EXESUF): tests/test-qdist.o $(test-util-obj-y)
 tests/test-qht$(EXESUF): tests/test-qht.o $(test-util-obj-y)
 tests/test-qht-par$(EXESUF): tests/test-qht-par.o tests/qht-bench$(EXESUF) $(test-util-obj-y)
 tests/qht-bench$(EXESUF): tests/qht-bench.o $(test-util-obj-y)
+tests/test-bufferiszero$(EXESUF): tests/test-bufferiszero.o $(test-util-obj-y)
 
 tests/test-qdev-global-props$(EXESUF): tests/test-qdev-global-props.o \
 	hw/core/qdev.o hw/core/qdev-properties.o hw/core/hotplug.o\
diff --git a/tests/test-bufferiszero.c b/tests/test-bufferiszero.c
new file mode 100644
index 0000000..42d194c
--- /dev/null
+++ b/tests/test-bufferiszero.c
@@ -0,0 +1,78 @@
+/*
+ * QEMU buffer_is_zero test
+ *
+ * Copyright (c) 2016 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include "qemu/osdep.h"
+#include "qemu/cutils.h"
+
+static char buffer[8 * 1024 * 1024];
+
+static void test_1(void)
+{
+    size_t s, a, o;
+
+    /* Basic positive test.  */
+    g_assert(buffer_is_zero(buffer, sizeof(buffer)));
+
+    /* Basic negative test.  */
+    buffer[sizeof(buffer) - 1] = 1;
+    g_assert(!buffer_is_zero(buffer, sizeof(buffer)));
+    buffer[sizeof(buffer) - 1] = 0;
+
+    /* Positive tests for size and alignment.  */
+    for (a = 1; a <= 64; a++) {
+        for (s = 1; s < 1024; s++) {
+            buffer[a - 1] = 1;
+            buffer[a + s] = 1;
+            g_assert(buffer_is_zero(buffer + a, s));
+            buffer[a - 1] = 0;
+            buffer[a + s] = 0;
+        }
+    }
+
+    /* Negative tests for size, alignment, and the offset of the marker.  */
+    for (a = 1; a <= 64; a++) {
+        for (s = 1; s < 1024; s++) {
+            for (o = 0; o < s; ++o) {
+                buffer[a + o] = 1;
+                g_assert(!buffer_is_zero(buffer + a, s));
+                buffer[a + o] = 0;
+            }
+        }
+    }
+}
+
+static void test_2(void)
+{
+    if (g_test_perf()) {
+        test_1();
+    } else {
+        do {
+            test_1();
+        } while (test_buffer_is_zero_next_accel());
+    }
+}
+
+int main(int argc, char **argv)
+{
+    g_test_init(&argc, &argv, NULL);
+    g_test_add_func("/cutils/bufferiszero", test_2);
+
+    return g_test_run();
+}
diff --git a/util/bufferiszero.c b/util/bufferiszero.c
index 89224f4..c356415 100644
--- a/util/bufferiszero.c
+++ b/util/bufferiszero.c
@@ -223,6 +223,13 @@ static bool select_accel_fn(const void *buf, size_t len)
 #define select_accel_fn  buffer_zero_int
 #endif
 
+#ifndef HAVE_NEXT_ACCEL
+bool test_buffer_is_zero_next_accel(void)
+{
+    return false;
+}
+#endif
+
 /*
  * Checks if a buffer is all zeroes
  */
-- 
2.7.4

[Qemu-devel] [PATCH v3 6/9] cutils: Add generic prefetch

[Richard Henderson]

There's no real knowledge of the cacheline size,
just prefetching one loop ahead.

Signed-off-by: Richard Henderson <rth@twiddle.net>
---
 util/bufferiszero.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/util/bufferiszero.c b/util/bufferiszero.c
index c356415..2c5801b 100644
--- a/util/bufferiszero.c
+++ b/util/bufferiszero.c
@@ -38,6 +38,8 @@ static bool NAME(const void *buf, size_t len)                   \
     do {                                                        \
         const VECTYPE *p = buf;                                 \
         VECTYPE t;                                              \
+        __builtin_prefetch(buf + SIZE);                         \
+        barrier();                                              \
         if (SIZE == sizeof(VECTYPE) * 4) {                      \
             t = (p[0] | p[1]) | (p[2] | p[3]);                  \
         } else if (SIZE == sizeof(VECTYPE) * 8) {               \
@@ -239,6 +241,9 @@ bool buffer_is_zero(const void *buf, size_t len)
         return true;
     }
 
+    /* Fetch the beginning of the buffer while we select the accelerator.  */
+    __builtin_prefetch(buf);
+
     /* Use an optimized zero check if possible.  Note that this also
        includes a check for an unrolled loop over longs, as well as
        the unsized, unaligned fallback to buffer_zero_base.  */
-- 
2.7.4

[Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking

[Richard Henderson]

Handle alignment of buffers, so that the vector paths can be
used more often.  Add versions for AVX1 and SSE4.1, both of
which have incremental improvements over SSE2.

Signed-off-by: Richard Henderson <rth@twiddle.net>
---
 util/bufferiszero.c | 209 ++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 179 insertions(+), 30 deletions(-)

diff --git a/util/bufferiszero.c b/util/bufferiszero.c
index 2c5801b..7fcc8e1 100644
--- a/util/bufferiszero.c
+++ b/util/bufferiszero.c
@@ -122,29 +122,177 @@ static bool select_accel_fn(const void *buf, size_t len)
     return buffer_zero_int(buf, len);
 }
 
-#elif defined(CONFIG_AVX2_OPT)
+#elif defined(CONFIG_AVX2_OPT) || defined(__SSE2__)
 #include <cpuid.h>
 #include <x86intrin.h>
 
+/* Note that we're going to check for LEN >= 64 for all of these.  */
+
+#ifdef CONFIG_AVX2_OPT
 #pragma GCC push_options
 #pragma GCC target("avx2")
-#define AVX2_NONZERO(X)  !_mm256_testz_si256((X), (X))
-ACCEL_BUFFER_ZERO(buffer_zero_avx2, 128, __m256i, AVX2_NONZERO)
+
+static bool
+buffer_zero_avx2(const void *buf, size_t len)
+{
+    /* Begin with an unaligned head of 32 bytes.  */
+    __m256i t = _mm256_loadu_si256(buf);
+    __m256i *p = (__m256i *)(((uintptr_t)buf + 5 * 32) & -32);
+    __m256i *e = (__m256i *)(((uintptr_t)buf + len) & -32);
+
+    if (likely(p <= e)) {
+        /* Loop over 32-byte aligned blocks of 128.  */
+        do {
+            __builtin_prefetch(p);
+            if (unlikely(!_mm256_testz_si256(t, t))) {
+                return false;
+            }
+            t = p[-4] | p[-3] | p[-2] | p[-1];
+            p += 4;
+        } while (p <= e);
+    } else {
+        t |= _mm256_loadu_si256(buf + 32);
+        if (len <= 128) {
+            goto last2;
+        }
+    }
+
+    /* Finish the last block of 128 unaligned.  */
+    t |= _mm256_loadu_si256(buf + len - 4 * 32);
+    t |= _mm256_loadu_si256(buf + len - 3 * 32);
+ last2:
+    t |= _mm256_loadu_si256(buf + len - 2 * 32);
+    t |= _mm256_loadu_si256(buf + len - 1 * 32);
+
+    return _mm256_testz_si256(t, t);
+}
+
+#pragma GCC pop_options
+#pragma GCC push_options
+#pragma GCC target("avx")
+
+static bool
+buffer_zero_avx(const void *buf, size_t len)
+{
+    __m128i t = _mm_loadu_si128(buf);
+    __m128i *p = (__m128i *)(((uintptr_t)buf + 5 * 16) & -16);
+    __m128i *e = (__m128i *)(((uintptr_t)buf + len) & -16);
+
+    /* Loop over 16-byte aligned blocks of 64.  */
+    while (likely(p <= e)) {
+        __builtin_prefetch(p);
+        if (unlikely(!_mm_testz_si128(t, t))) {
+            return false;
+        }
+        t = p[-4] | p[-3] | p[-2] | p[-1];
+        p += 4;
+    }
+
+    /* Finish the last block of 64 unaligned.  */
+    t |= _mm_loadu_si128(buf + len - 4 * 16);
+    t |= _mm_loadu_si128(buf + len - 3 * 16);
+    t |= _mm_loadu_si128(buf + len - 2 * 16);
+    t |= _mm_loadu_si128(buf + len - 1 * 16);
+
+    return _mm_testz_si128(t, t);
+}
+
 #pragma GCC pop_options
+#pragma GCC push_options
+#pragma GCC target("sse4")
+
+static bool
+buffer_zero_sse4(const void *buf, size_t len)
+{
+    __m128i t = _mm_loadu_si128(buf);
+    __m128i *p = (__m128i *)(((uintptr_t)buf + 5 * 16) & -16);
+    __m128i *e = (__m128i *)(((uintptr_t)buf + len) & -16);
+
+    /* Loop over 16-byte aligned blocks of 64.  */
+    while (likely(p <= e)) {
+        __builtin_prefetch(p);
+        if (unlikely(!_mm_testz_si128(t, t))) {
+            return false;
+        }
+        t = p[-4] | p[-3] | p[-2] | p[-1];
+        p += 4;
+    }
 
+    /* Finish the aligned tail.  */
+    t |= e[-3];
+    t |= e[-2];
+    t |= e[-1];
+
+    /* Finish the unaligned tail.  */
+    t |= _mm_loadu_si128(buf + len - 16);
+
+    return _mm_testz_si128(t, t);
+}
+
+#pragma GCC pop_options
 #pragma GCC push_options
 #pragma GCC target("sse2")
-#define SSE2_NONZERO(X) \
-    (_mm_movemask_epi8(_mm_cmpeq_epi8((X), _mm_setzero_si128())) != 0xFFFF)
-ACCEL_BUFFER_ZERO(buffer_zero_sse2, 64, __m128i, SSE2_NONZERO)
+#endif /* CONFIG_AVX2_OPT */
+
+static bool
+buffer_zero_sse2(const void *buf, size_t len)
+{
+    __m128i t = _mm_loadu_si128(buf);
+    __m128i *p = (__m128i *)(((uintptr_t)buf + 5 * 16) & -16);
+    __m128i *e = (__m128i *)(((uintptr_t)buf + len) & -16);
+    __m128i zero = _mm_setzero_si128();
+
+    /* Loop over 16-byte aligned blocks of 64.  */
+    while (likely(p <= e)) {
+        __builtin_prefetch(p);
+        t = _mm_cmpeq_epi8(t, zero);
+        if (unlikely(_mm_movemask_epi8(t) != 0xFFFF)) {
+            return false;
+        }
+        t = p[-4] | p[-3] | p[-2] | p[-1];
+        p += 4;
+    }
+
+    /* Finish the aligned tail.  */
+    t |= e[-3];
+    t |= e[-2];
+    t |= e[-1];
+
+    /* Finish the unaligned tail.  */
+    t |= _mm_loadu_si128(buf + len - 16);
+
+    return _mm_movemask_epi8(_mm_cmpeq_epi8(t, zero)) == 0xFFFF;
+}
+
+#ifdef CONFIG_AVX2_OPT
 #pragma GCC pop_options
 
-#define CACHE_AVX2    2
-#define CACHE_AVX1    4
-#define CACHE_SSE4    8
-#define CACHE_SSE2    16
+/* These values must be most preferable alternative first.
+   See test_buffer_is_zero_next_accel.  */
+#define CACHE_AVX2    1
+#define CACHE_AVX1    2
+#define CACHE_SSE4    4
+#define CACHE_SSE2    8
 
 static unsigned cpuid_cache;
+static accel_zero_fn buffer_accel;
+
+static void init_accel(unsigned cache)
+{
+    accel_zero_fn fn;
+    if (cache & CACHE_AVX2) {
+        fn = buffer_zero_avx2;
+    } else if (cache & CACHE_AVX1) {
+        fn = buffer_zero_avx;
+    } else if (cache & CACHE_SSE4) {
+        fn = buffer_zero_sse4;
+    } else if (cache & CACHE_SSE2) {
+        fn = buffer_zero_sse2;
+    } else {
+        fn = buffer_zero_int;
+    }
+    buffer_accel = fn;
+}
 
 static void __attribute__((constructor)) init_cpuid_cache(void)
 {
@@ -163,8 +311,9 @@ static void __attribute__((constructor)) init_cpuid_cache(void)
 
         /* We must check that AVX is not just available, but usable.  */
         if ((c & bit_OSXSAVE) && (c & bit_AVX)) {
-            __asm("xgetbv" : "=a"(a), "=d"(d) : "c"(0));
-            if ((a & 6) == 6) {
+            int bv;
+            __asm("xgetbv" : "=a"(bv), "=d"(d) : "c"(0));
+            if ((bv & 6) == 6) {
                 cache |= CACHE_AVX1;
                 if (max >= 7) {
                     __cpuid_count(7, 0, a, b, c, d);
@@ -176,34 +325,34 @@ static void __attribute__((constructor)) init_cpuid_cache(void)
         }
     }
     cpuid_cache = cache;
+    init_accel(cache);
 }
 
-static bool select_accel_fn(const void *buf, size_t len)
+#define HAVE_NEXT_ACCEL
+bool test_buffer_is_zero_next_accel(void)
 {
-    uintptr_t ibuf = (uintptr_t)buf;
-    if (len % 128 == 0 && ibuf % 32 == 0 && (cpuid_cache & CACHE_AVX2)) {
-        return buffer_zero_avx2(buf, len);
-    }
-    if (len % 64 == 0 && ibuf % 16 == 0 && (cpuid_cache & CACHE_SSE2)) {
-        return buffer_zero_sse2(buf, len);
+    /* If no bits set, we just tested buffer_zero_int, and there
+       are no more acceleration options to test.  */
+    if (cpuid_cache == 0) {
+        return false;
     }
-    return buffer_zero_int(buf, len);
+    /* Disable the accelerator we used before and select a new one.  */
+    cpuid_cache &= cpuid_cache - 1;
+    init_accel(cpuid_cache);
+    return true;
 }
-
-#elif defined __SSE2__
-#include <emmintrin.h>
-
-#define SSE2_NONZERO(X) \
-    (_mm_movemask_epi8(_mm_cmpeq_epi8((X), _mm_setzero_si128())) != 0xFFFF)
-ACCEL_BUFFER_ZERO(buffer_zero_sse2, 64, __m128i, SSE2_NONZERO)
+#endif /* CONFIG_AVX2_OPT */
 
 static bool select_accel_fn(const void *buf, size_t len)
 {
-    uintptr_t ibuf = (uintptr_t)buf;
-    if (len % 64 == 0 && ibuf % sizeof(__m128i) == 0) {
+    if (likely(len >= 64)) {
+#ifdef CONFIG_AVX2_OPT
+        return buffer_accel(buf, len);
+#else
         return buffer_zero_sse2(buf, len);
+#endif
     }
-    return select_accel_int(buf, len);
+    return buffer_zero_int(buf, len);
 }
 
 #elif defined(__aarch64__)
-- 
2.7.4

[Qemu-devel] [PATCH v3 8/9] cutils: Remove aarch64 buffer zero checking

[Richard Henderson]

The revised integer version is 4 times faster than the neon version
on an AppliedMicro Mustang.  Even with hand scheduling and additional
unrolling I cannot make any neon version run as fast as the integer.

Signed-off-by: Richard Henderson <rth@twiddle.net>
---
 util/bufferiszero.c | 15 ---------------
 1 file changed, 15 deletions(-)

diff --git a/util/bufferiszero.c b/util/bufferiszero.c
index 7fcc8e1..6d13d7f 100644
--- a/util/bufferiszero.c
+++ b/util/bufferiszero.c
@@ -355,21 +355,6 @@ static bool select_accel_fn(const void *buf, size_t len)
     return buffer_zero_int(buf, len);
 }
 
-#elif defined(__aarch64__)
-#include "arm_neon.h"
-
-#define DO_NONZERO(X)  (vgetq_lane_u64((X), 0) | vgetq_lane_u64((X), 1))
-ACCEL_BUFFER_ZERO(buffer_zero_neon, 128, uint64x2_t, DO_NONZERO)
-
-static bool select_accel_fn(const void *buf, size_t len)
-{
-    uintptr_t ibuf = (uintptr_t)buf;
-    if (len % 128 == 0 && ibuf % sizeof(uint64x2_t) == 0) {
-        return buffer_zero_neon(buf, len);
-    }
-    return buffer_zero_int(buf, len);
-}
-
 #else
 #define select_accel_fn  buffer_zero_int
 #endif
-- 
2.7.4

[Qemu-devel] [PATCH v3 9/9] cutils: Remove ppc buffer zero checking

[Richard Henderson]

For ppc64le, gcc6 does extremely poorly with the Altivec code.
Moreover, on POWER7 and POWER8, a hand-optimized Altivec version
turns out to be no faster than the revised integer version, and
therefore not worth the effort.

Signed-off-by: Richard Henderson <rth@twiddle.net>
---
 util/bufferiszero.c | 55 +----------------------------------------------------
 1 file changed, 1 insertion(+), 54 deletions(-)

diff --git a/util/bufferiszero.c b/util/bufferiszero.c
index 6d13d7f..3b39f82 100644
--- a/util/bufferiszero.c
+++ b/util/bufferiszero.c
@@ -29,35 +29,6 @@
 
 /* vector definitions */
 
-extern void link_error(void);
-
-#define ACCEL_BUFFER_ZERO(NAME, SIZE, VECTYPE, NONZERO)         \
-static bool NAME(const void *buf, size_t len)                   \
-{                                                               \
-    const void *end = buf + len;                                \
-    do {                                                        \
-        const VECTYPE *p = buf;                                 \
-        VECTYPE t;                                              \
-        __builtin_prefetch(buf + SIZE);                         \
-        barrier();                                              \
-        if (SIZE == sizeof(VECTYPE) * 4) {                      \
-            t = (p[0] | p[1]) | (p[2] | p[3]);                  \
-        } else if (SIZE == sizeof(VECTYPE) * 8) {               \
-            t  = p[0] | p[1];                                   \
-            t |= p[2] | p[3];                                   \
-            t |= p[4] | p[5];                                   \
-            t |= p[6] | p[7];                                   \
-        } else {                                                \
-            link_error();                                       \
-        }                                                       \
-        if (unlikely(NONZERO(t))) {                             \
-            return false;                                       \
-        }                                                       \
-        buf += SIZE;                                            \
-    } while (buf < end);                                        \
-    return true;                                                \
-}
-
 typedef bool (*accel_zero_fn)(const void *, size_t);
 
 static bool
@@ -98,31 +69,7 @@ buffer_zero_int(const void *buf, size_t len)
     }
 }
 
-#ifdef __ALTIVEC__
-#include <altivec.h>
-/* The altivec.h header says we're allowed to undef these for
- * C++ compatibility.  Here we don't care about C++, but we
- * undef them anyway to avoid namespace pollution.
- * altivec.h may redefine the bool macro as vector type.
- * Reset it to POSIX semantics.
- */
-#undef vector
-#undef pixel
-#undef bool
-#define bool _Bool
-#define DO_NONZERO(X)  vec_any_ne(X, (__vector unsigned char){ 0 })
-ACCEL_BUFFER_ZERO(buffer_zero_ppc, 128, __vector unsigned char, DO_NONZERO)
-
-static bool select_accel_fn(const void *buf, size_t len)
-{
-    uintptr_t ibuf = (uintptr_t)buf;
-    if (len % 128 == 0 && ibuf % sizeof(__vector unsigned char) == 0) {
-        return buffer_zero_ppc(buf, len);
-    }
-    return buffer_zero_int(buf, len);
-}
-
-#elif defined(CONFIG_AVX2_OPT) || defined(__SSE2__)
+#if defined(CONFIG_AVX2_OPT) || defined(__SSE2__)
 #include <cpuid.h>
 #include <x86intrin.h>
 
-- 
2.7.4

Re: [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero

[Paolo Bonzini]

On 29/08/2016 20:46, Richard Henderson wrote:
> Changes from v2 to v3:
> 
>   * Unit testing.  This includes having x86 attempt all versions of
>     the accelerator that will run on the hardware.  Thus an avx2 host
>     will run the basic test 5 times (1.5sec on my laptop).
> 
>   * Drop the ppc and aarch64 specializations.  I have improved the
>     basic integer version to the point that those vectorized versions
>     are not a win.
> 
>     In the case of my aarch64 mustang, the integer version is 4 times
>     faster than the neon version that I delete.  With effort I was
>     able to rewrite the neon version to come to within a factor of 1.1,
>     but it remained slower than the integer.  To be fair, gcc6 makes
>     very good use of ldp, so the integer path is *also* loading 16 bytes
>     per insn.
> 
>     I can forward my standalone aarch64 benchmark if anyone is interested.
> 
>     Note however that at least the avx2 acceleration is still very much
>     a win, being about 3 times faster on my laptop.  Of course, it's
>     handling 4 times as much data per loop as the integer version, so
>     one can still see the overhead caused by using vector insns.
> 
>     For grins I wrote an avx512 version, if someone has a skylake upon
>     which to test and benchmark.  That requires additional configure
>     checks, so I didn't bother to include it here.

Thanks, queued for 2.8.

Paolo

Re: [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero

[Dr. David Alan Gilbert]

* Richard Henderson (rth@twiddle.net) wrote:

Have you considered contributing something similar to this to glibc?
I filed https://sourceware.org/bugzilla/show_bug.cgi?id=19920  a while back
suggesting it would be useful to have it in libc to be used
by things other than just qemu.

Dave

> Changes from v2 to v3:
> 
>   * Unit testing.  This includes having x86 attempt all versions of
>     the accelerator that will run on the hardware.  Thus an avx2 host
>     will run the basic test 5 times (1.5sec on my laptop).
> 
>   * Drop the ppc and aarch64 specializations.  I have improved the
>     basic integer version to the point that those vectorized versions
>     are not a win.
> 
>     In the case of my aarch64 mustang, the integer version is 4 times
>     faster than the neon version that I delete.  With effort I was
>     able to rewrite the neon version to come to within a factor of 1.1,
>     but it remained slower than the integer.  To be fair, gcc6 makes
>     very good use of ldp, so the integer path is *also* loading 16 bytes
>     per insn.
> 
>     I can forward my standalone aarch64 benchmark if anyone is interested.
> 
>     Note however that at least the avx2 acceleration is still very much
>     a win, being about 3 times faster on my laptop.  Of course, it's
>     handling 4 times as much data per loop as the integer version, so
>     one can still see the overhead caused by using vector insns.
> 
>     For grins I wrote an avx512 version, if someone has a skylake upon
>     which to test and benchmark.  That requires additional configure
>     checks, so I didn't bother to include it here.
> 
> 
> r~
> 
> 
> Richard Henderson (9):
>   cutils: Move buffer_is_zero and subroutines to a new file
>   cutils: Remove SPLAT macro
>   cutils: Export only buffer_is_zero
>   cutils: Rearrange buffer_is_zero acceleration
>   cutils: Add test for buffer_is_zero
>   cutils: Add generic prefetch
>   cutils: Rewrite x86 buffer zero checking
>   cutils: Remove aarch64 buffer zero checking
>   cutils: Remove ppc buffer zero checking
> 
>  configure                 |  21 +--
>  include/qemu/cutils.h     |   3 +-
>  migration/ram.c           |   2 +-
>  migration/rdma.c          |   5 +-
>  tests/Makefile.include    |   3 +
>  tests/test-bufferiszero.c |  78 +++++++++++
>  util/Makefile.objs        |   1 +
>  util/bufferiszero.c       | 332 ++++++++++++++++++++++++++++++++++++++++++++++
>  util/cutils.c             | 244 ----------------------------------
>  9 files changed, 423 insertions(+), 266 deletions(-)
>  create mode 100644 tests/test-bufferiszero.c
>  create mode 100644 util/bufferiszero.c
> 
> -- 
> 2.7.4
> 
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

Re: [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking

[Paolo Bonzini]

On 29/08/2016 20:46, Richard Henderson wrote:
> Handle alignment of buffers, so that the vector paths can be
> used more often.  Add versions for AVX1 and SSE4.1, both of
> which have incremental improvements over SSE2.
> 
> Signed-off-by: Richard Henderson <rth@twiddle.net>
> ---
>  util/bufferiszero.c | 209 ++++++++++++++++++++++++++++++++++++++++++++--------
>  1 file changed, 179 insertions(+), 30 deletions(-)
> 
> diff --git a/util/bufferiszero.c b/util/bufferiszero.c
> index 2c5801b..7fcc8e1 100644
> --- a/util/bufferiszero.c
> +++ b/util/bufferiszero.c
> @@ -122,29 +122,177 @@ static bool select_accel_fn(const void *buf, size_t len)
>      return buffer_zero_int(buf, len);
>  }
>  
> -#elif defined(CONFIG_AVX2_OPT)
> +#elif defined(CONFIG_AVX2_OPT) || defined(__SSE2__)
>  #include <cpuid.h>
>  #include <x86intrin.h>
>  
> +/* Note that we're going to check for LEN >= 64 for all of these.  */
> +
> +#ifdef CONFIG_AVX2_OPT
>  #pragma GCC push_options
>  #pragma GCC target("avx2")
> -#define AVX2_NONZERO(X)  !_mm256_testz_si256((X), (X))
> -ACCEL_BUFFER_ZERO(buffer_zero_avx2, 128, __m256i, AVX2_NONZERO)
> +
> +static bool
> +buffer_zero_avx2(const void *buf, size_t len)
> +{
> +    /* Begin with an unaligned head of 32 bytes.  */
> +    __m256i t = _mm256_loadu_si256(buf);
> +    __m256i *p = (__m256i *)(((uintptr_t)buf + 5 * 32) & -32);
> +    __m256i *e = (__m256i *)(((uintptr_t)buf + len) & -32);
> +
> +    if (likely(p <= e)) {
> +        /* Loop over 32-byte aligned blocks of 128.  */
> +        do {
> +            __builtin_prefetch(p);
> +            if (unlikely(!_mm256_testz_si256(t, t))) {
> +                return false;
> +            }
> +            t = p[-4] | p[-3] | p[-2] | p[-1];
> +            p += 4;
> +        } while (p <= e);
> +    } else {
> +        t |= _mm256_loadu_si256(buf + 32);
> +        if (len <= 128) {
> +            goto last2;
> +        }
> +    }
> +
> +    /* Finish the last block of 128 unaligned.  */
> +    t |= _mm256_loadu_si256(buf + len - 4 * 32);
> +    t |= _mm256_loadu_si256(buf + len - 3 * 32);
> + last2:
> +    t |= _mm256_loadu_si256(buf + len - 2 * 32);
> +    t |= _mm256_loadu_si256(buf + len - 1 * 32);
> +
> +    return _mm256_testz_si256(t, t);
> +}
> +
> +#pragma GCC pop_options
> +#pragma GCC push_options
> +#pragma GCC target("avx")
> +
> +static bool
> +buffer_zero_avx(const void *buf, size_t len)
> +{
> +    __m128i t = _mm_loadu_si128(buf);
> +    __m128i *p = (__m128i *)(((uintptr_t)buf + 5 * 16) & -16);
> +    __m128i *e = (__m128i *)(((uintptr_t)buf + len) & -16);
> +
> +    /* Loop over 16-byte aligned blocks of 64.  */
> +    while (likely(p <= e)) {
> +        __builtin_prefetch(p);
> +        if (unlikely(!_mm_testz_si128(t, t))) {
> +            return false;
> +        }
> +        t = p[-4] | p[-3] | p[-2] | p[-1];
> +        p += 4;
> +    }
> +
> +    /* Finish the last block of 64 unaligned.  */
> +    t |= _mm_loadu_si128(buf + len - 4 * 16);
> +    t |= _mm_loadu_si128(buf + len - 3 * 16);
> +    t |= _mm_loadu_si128(buf + len - 2 * 16);
> +    t |= _mm_loadu_si128(buf + len - 1 * 16);
> +
> +    return _mm_testz_si128(t, t);
> +}
> +
>  #pragma GCC pop_options
> +#pragma GCC push_options
> +#pragma GCC target("sse4")
> +
> +static bool
> +buffer_zero_sse4(const void *buf, size_t len)
> +{
> +    __m128i t = _mm_loadu_si128(buf);
> +    __m128i *p = (__m128i *)(((uintptr_t)buf + 5 * 16) & -16);
> +    __m128i *e = (__m128i *)(((uintptr_t)buf + len) & -16);
> +
> +    /* Loop over 16-byte aligned blocks of 64.  */
> +    while (likely(p <= e)) {
> +        __builtin_prefetch(p);
> +        if (unlikely(!_mm_testz_si128(t, t))) {
> +            return false;
> +        }
> +        t = p[-4] | p[-3] | p[-2] | p[-1];
> +        p += 4;
> +    }
>  
> +    /* Finish the aligned tail.  */
> +    t |= e[-3];
> +    t |= e[-2];
> +    t |= e[-1];
> +
> +    /* Finish the unaligned tail.  */
> +    t |= _mm_loadu_si128(buf + len - 16);
> +
> +    return _mm_testz_si128(t, t);
> +}
> +
> +#pragma GCC pop_options
>  #pragma GCC push_options
>  #pragma GCC target("sse2")
> -#define SSE2_NONZERO(X) \
> -    (_mm_movemask_epi8(_mm_cmpeq_epi8((X), _mm_setzero_si128())) != 0xFFFF)
> -ACCEL_BUFFER_ZERO(buffer_zero_sse2, 64, __m128i, SSE2_NONZERO)
> +#endif /* CONFIG_AVX2_OPT */
> +
> +static bool
> +buffer_zero_sse2(const void *buf, size_t len)
> +{
> +    __m128i t = _mm_loadu_si128(buf);
> +    __m128i *p = (__m128i *)(((uintptr_t)buf + 5 * 16) & -16);
> +    __m128i *e = (__m128i *)(((uintptr_t)buf + len) & -16);
> +    __m128i zero = _mm_setzero_si128();
> +
> +    /* Loop over 16-byte aligned blocks of 64.  */
> +    while (likely(p <= e)) {
> +        __builtin_prefetch(p);
> +        t = _mm_cmpeq_epi8(t, zero);
> +        if (unlikely(_mm_movemask_epi8(t) != 0xFFFF)) {
> +            return false;
> +        }
> +        t = p[-4] | p[-3] | p[-2] | p[-1];
> +        p += 4;
> +    }
> +
> +    /* Finish the aligned tail.  */
> +    t |= e[-3];
> +    t |= e[-2];
> +    t |= e[-1];
> +
> +    /* Finish the unaligned tail.  */
> +    t |= _mm_loadu_si128(buf + len - 16);
> +
> +    return _mm_movemask_epi8(_mm_cmpeq_epi8(t, zero)) == 0xFFFF;
> +}
> +
> +#ifdef CONFIG_AVX2_OPT
>  #pragma GCC pop_options
>  
> -#define CACHE_AVX2    2
> -#define CACHE_AVX1    4
> -#define CACHE_SSE4    8
> -#define CACHE_SSE2    16
> +/* These values must be most preferable alternative first.
> +   See test_buffer_is_zero_next_accel.  */
> +#define CACHE_AVX2    1
> +#define CACHE_AVX1    2
> +#define CACHE_SSE4    4
> +#define CACHE_SSE2    8
>  
>  static unsigned cpuid_cache;
> +static accel_zero_fn buffer_accel;
> +
> +static void init_accel(unsigned cache)
> +{
> +    accel_zero_fn fn;
> +    if (cache & CACHE_AVX2) {
> +        fn = buffer_zero_avx2;
> +    } else if (cache & CACHE_AVX1) {
> +        fn = buffer_zero_avx;
> +    } else if (cache & CACHE_SSE4) {
> +        fn = buffer_zero_sse4;
> +    } else if (cache & CACHE_SSE2) {
> +        fn = buffer_zero_sse2;
> +    } else {
> +        fn = buffer_zero_int;
> +    }
> +    buffer_accel = fn;
> +}
>  
>  static void __attribute__((constructor)) init_cpuid_cache(void)
>  {
> @@ -163,8 +311,9 @@ static void __attribute__((constructor)) init_cpuid_cache(void)
>  
>          /* We must check that AVX is not just available, but usable.  */
>          if ((c & bit_OSXSAVE) && (c & bit_AVX)) {
> -            __asm("xgetbv" : "=a"(a), "=d"(d) : "c"(0));
> -            if ((a & 6) == 6) {
> +            int bv;
> +            __asm("xgetbv" : "=a"(bv), "=d"(d) : "c"(0));
> +            if ((bv & 6) == 6) {
>                  cache |= CACHE_AVX1;
>                  if (max >= 7) {
>                      __cpuid_count(7, 0, a, b, c, d);
> @@ -176,34 +325,34 @@ static void __attribute__((constructor)) init_cpuid_cache(void)
>          }
>      }
>      cpuid_cache = cache;
> +    init_accel(cache);
>  }
>  
> -static bool select_accel_fn(const void *buf, size_t len)
> +#define HAVE_NEXT_ACCEL
> +bool test_buffer_is_zero_next_accel(void)
>  {
> -    uintptr_t ibuf = (uintptr_t)buf;
> -    if (len % 128 == 0 && ibuf % 32 == 0 && (cpuid_cache & CACHE_AVX2)) {
> -        return buffer_zero_avx2(buf, len);
> -    }
> -    if (len % 64 == 0 && ibuf % 16 == 0 && (cpuid_cache & CACHE_SSE2)) {
> -        return buffer_zero_sse2(buf, len);
> +    /* If no bits set, we just tested buffer_zero_int, and there
> +       are no more acceleration options to test.  */
> +    if (cpuid_cache == 0) {
> +        return false;
>      }
> -    return buffer_zero_int(buf, len);
> +    /* Disable the accelerator we used before and select a new one.  */
> +    cpuid_cache &= cpuid_cache - 1;
> +    init_accel(cpuid_cache);
> +    return true;
>  }
> -
> -#elif defined __SSE2__
> -#include <emmintrin.h>
> -
> -#define SSE2_NONZERO(X) \
> -    (_mm_movemask_epi8(_mm_cmpeq_epi8((X), _mm_setzero_si128())) != 0xFFFF)
> -ACCEL_BUFFER_ZERO(buffer_zero_sse2, 64, __m128i, SSE2_NONZERO)
> +#endif /* CONFIG_AVX2_OPT */
>  
>  static bool select_accel_fn(const void *buf, size_t len)
>  {
> -    uintptr_t ibuf = (uintptr_t)buf;
> -    if (len % 64 == 0 && ibuf % sizeof(__m128i) == 0) {
> +    if (likely(len >= 64)) {
> +#ifdef CONFIG_AVX2_OPT
> +        return buffer_accel(buf, len);
> +#else
>          return buffer_zero_sse2(buf, len);
> +#endif
>      }
> -    return select_accel_int(buf, len);
> +    return buffer_zero_int(buf, len);
>  }
>  
>  #elif defined(__aarch64__)
> 

I need this on top to fix compilation with older compilers:

diff --git a/util/bufferiszero.c b/util/bufferiszero.c
index 3b39f82..1ce6b7a 100644
--- a/util/bufferiszero.c
+++ b/util/bufferiszero.c
@@ -71,13 +71,13 @@ buffer_zero_int(const void *buf, size_t len)

 #if defined(CONFIG_AVX2_OPT) || defined(__SSE2__)
 #include <cpuid.h>
-#include <x86intrin.h>

 /* Note that we're going to check for LEN >= 64 for all of these.  */

 #ifdef CONFIG_AVX2_OPT
 #pragma GCC push_options
 #pragma GCC target("avx2")
+#include <immintrin.h>

 static bool
 buffer_zero_avx2(const void *buf, size_t len)
@@ -181,6 +181,8 @@ buffer_zero_sse4(const void *buf, size_t len)
 #pragma GCC target("sse2")
 #endif /* CONFIG_AVX2_OPT */

+#include <emmintrin.h>
+
 static bool
 buffer_zero_sse2(const void *buf, size_t len)
 {

Paolo

Re: [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking

[Paolo Bonzini]

On 13/09/2016 15:26, Paolo Bonzini wrote:
> I need this on top to fix compilation with older compilers:
> 
> diff --git a/util/bufferiszero.c b/util/bufferiszero.c
> index 3b39f82..1ce6b7a 100644
> --- a/util/bufferiszero.c
> +++ b/util/bufferiszero.c
> @@ -71,13 +71,13 @@ buffer_zero_int(const void *buf, size_t len)
> 
>  #if defined(CONFIG_AVX2_OPT) || defined(__SSE2__)
>  #include <cpuid.h>
> -#include <x86intrin.h>
> 
>  /* Note that we're going to check for LEN >= 64 for all of these.  */
> 
>  #ifdef CONFIG_AVX2_OPT
>  #pragma GCC push_options
>  #pragma GCC target("avx2")
> +#include <immintrin.h>
> 
>  static bool
>  buffer_zero_avx2(const void *buf, size_t len)
> @@ -181,6 +181,8 @@ buffer_zero_sse4(const void *buf, size_t len)
>  #pragma GCC target("sse2")
>  #endif /* CONFIG_AVX2_OPT */
> 
> +#include <emmintrin.h>
> +
>  static bool
>  buffer_zero_sse2(const void *buf, size_t len)
>  {
> 

Nope, not enough on GCC 4.8:

$ nm util/bufferiszero.o
0000000000000000 b buffer_accel
0000000000000430 T buffer_is_zero
0000000000000240 t buffer_zero_avx
0000000000000330 t buffer_zero_avx2
0000000000000000 t buffer_zero_int
00000000000000b0 t buffer_zero_sse2
0000000000000190 t buffer_zero_sse4
0000000000000008 b cpuid_cache
                 U _GLOBAL_OFFSET_TABLE_
0000000000000000 t init_cpuid_cache
                 U _mm_cmpeq_epi8
                 U _mm_loadu_si128
                 U _mm_movemask_epi8
                 U _mm_setzero_si128
                 U _mm_testz_si128
00000000000003d0 T test_buffer_is_zero_next_accel

Since I have no idea what's going on, I'm dropping these the last three
patches.

Paolo

Re: [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking

[Paolo Bonzini]

On 13/09/2016 16:17, Paolo Bonzini wrote:
> 
> 
> On 13/09/2016 15:26, Paolo Bonzini wrote:
>> I need this on top to fix compilation with older compilers:
>>
>> diff --git a/util/bufferiszero.c b/util/bufferiszero.c
>> index 3b39f82..1ce6b7a 100644
>> --- a/util/bufferiszero.c
>> +++ b/util/bufferiszero.c
>> @@ -71,13 +71,13 @@ buffer_zero_int(const void *buf, size_t len)
>>
>>  #if defined(CONFIG_AVX2_OPT) || defined(__SSE2__)
>>  #include <cpuid.h>
>> -#include <x86intrin.h>
>>
>>  /* Note that we're going to check for LEN >= 64 for all of these.  */
>>
>>  #ifdef CONFIG_AVX2_OPT
>>  #pragma GCC push_options
>>  #pragma GCC target("avx2")
>> +#include <immintrin.h>
>>
>>  static bool
>>  buffer_zero_avx2(const void *buf, size_t len)
>> @@ -181,6 +181,8 @@ buffer_zero_sse4(const void *buf, size_t len)
>>  #pragma GCC target("sse2")
>>  #endif /* CONFIG_AVX2_OPT */
>>
>> +#include <emmintrin.h>
>> +
>>  static bool
>>  buffer_zero_sse2(const void *buf, size_t len)
>>  {
>>
> 
> Nope, not enough on GCC 4.8:
> 
> $ nm util/bufferiszero.o
> 0000000000000000 b buffer_accel
> 0000000000000430 T buffer_is_zero
> 0000000000000240 t buffer_zero_avx
> 0000000000000330 t buffer_zero_avx2
> 0000000000000000 t buffer_zero_int
> 00000000000000b0 t buffer_zero_sse2
> 0000000000000190 t buffer_zero_sse4
> 0000000000000008 b cpuid_cache
>                  U _GLOBAL_OFFSET_TABLE_
> 0000000000000000 t init_cpuid_cache
>                  U _mm_cmpeq_epi8
>                  U _mm_loadu_si128
>                  U _mm_movemask_epi8
>                  U _mm_setzero_si128
>                  U _mm_testz_si128
> 00000000000003d0 T test_buffer_is_zero_next_accel
> 
> Since I have no idea what's going on, I'm dropping these the last three
> patches.

I still have no idea what's going on, but dropping this patch is enough.

Paolo

Re: [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking

[Paolo Bonzini]

On 13/09/2016 16:49, Paolo Bonzini wrote:
> 
> 
> On 13/09/2016 16:17, Paolo Bonzini wrote:
>>
>>
>> On 13/09/2016 15:26, Paolo Bonzini wrote:
>>> I need this on top to fix compilation with older compilers:
>>>
>>> diff --git a/util/bufferiszero.c b/util/bufferiszero.c
>>> index 3b39f82..1ce6b7a 100644
>>> --- a/util/bufferiszero.c
>>> +++ b/util/bufferiszero.c
>>> @@ -71,13 +71,13 @@ buffer_zero_int(const void *buf, size_t len)
>>>
>>>  #if defined(CONFIG_AVX2_OPT) || defined(__SSE2__)
>>>  #include <cpuid.h>
>>> -#include <x86intrin.h>
>>>
>>>  /* Note that we're going to check for LEN >= 64 for all of these.  */
>>>
>>>  #ifdef CONFIG_AVX2_OPT
>>>  #pragma GCC push_options
>>>  #pragma GCC target("avx2")
>>> +#include <immintrin.h>
>>>
>>>  static bool
>>>  buffer_zero_avx2(const void *buf, size_t len)
>>> @@ -181,6 +181,8 @@ buffer_zero_sse4(const void *buf, size_t len)
>>>  #pragma GCC target("sse2")
>>>  #endif /* CONFIG_AVX2_OPT */
>>>
>>> +#include <emmintrin.h>
>>> +
>>>  static bool
>>>  buffer_zero_sse2(const void *buf, size_t len)
>>>  {
>>>
>>
>> Nope, not enough on GCC 4.8:
>>
>> $ nm util/bufferiszero.o
>> 0000000000000000 b buffer_accel
>> 0000000000000430 T buffer_is_zero
>> 0000000000000240 t buffer_zero_avx
>> 0000000000000330 t buffer_zero_avx2
>> 0000000000000000 t buffer_zero_int
>> 00000000000000b0 t buffer_zero_sse2
>> 0000000000000190 t buffer_zero_sse4
>> 0000000000000008 b cpuid_cache
>>                  U _GLOBAL_OFFSET_TABLE_
>> 0000000000000000 t init_cpuid_cache
>>                  U _mm_cmpeq_epi8
>>                  U _mm_loadu_si128
>>                  U _mm_movemask_epi8
>>                  U _mm_setzero_si128
>>                  U _mm_testz_si128
>> 00000000000003d0 T test_buffer_is_zero_next_accel
>>
>> Since I have no idea what's going on, I'm dropping these the last three
>> patches.
> 
> I still have no idea what's going on, but dropping this patch is enough.

Ok, it's the AVX version, the failure somehow is related to vptest not
being in AVX1.

Paolo