* [Qemu-devel] [PATCH v3 1/9] cutils: Move buffer_is_zero and subroutines to a new file
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
@ 2016-08-29 18:46 ` Richard Henderson
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 3/9] cutils: Export only buffer_is_zero Richard Henderson
` (8 subsequent siblings)
9 siblings, 0 replies; 15+ messages in thread
From: Richard Henderson @ 2016-08-29 18:46 UTC (permalink / raw)
To: qemu-devel; +Cc: pbonzini, vijay.kilari
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
^ permalink raw reply related [flat|nested] 15+ messages in thread* [Qemu-devel] [PATCH v3 3/9] cutils: Export only buffer_is_zero
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 1/9] cutils: Move buffer_is_zero and subroutines to a new file Richard Henderson
@ 2016-08-29 18:46 ` Richard Henderson
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 4/9] cutils: Rearrange buffer_is_zero acceleration Richard Henderson
` (7 subsequent siblings)
9 siblings, 0 replies; 15+ messages in thread
From: Richard Henderson @ 2016-08-29 18:46 UTC (permalink / raw)
To: qemu-devel; +Cc: pbonzini, vijay.kilari
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
^ permalink raw reply related [flat|nested] 15+ messages in thread* [Qemu-devel] [PATCH v3 4/9] cutils: Rearrange buffer_is_zero acceleration
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 1/9] cutils: Move buffer_is_zero and subroutines to a new file Richard Henderson
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 3/9] cutils: Export only buffer_is_zero Richard Henderson
@ 2016-08-29 18:46 ` Richard Henderson
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 5/9] cutils: Add test for buffer_is_zero Richard Henderson
` (6 subsequent siblings)
9 siblings, 0 replies; 15+ messages in thread
From: Richard Henderson @ 2016-08-29 18:46 UTC (permalink / raw)
To: qemu-devel; +Cc: pbonzini, vijay.kilari
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
^ permalink raw reply related [flat|nested] 15+ messages in thread* [Qemu-devel] [PATCH v3 5/9] cutils: Add test for buffer_is_zero
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
` (2 preceding siblings ...)
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 4/9] cutils: Rearrange buffer_is_zero acceleration Richard Henderson
@ 2016-08-29 18:46 ` Richard Henderson
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 6/9] cutils: Add generic prefetch Richard Henderson
` (5 subsequent siblings)
9 siblings, 0 replies; 15+ messages in thread
From: Richard Henderson @ 2016-08-29 18:46 UTC (permalink / raw)
To: qemu-devel; +Cc: pbonzini, vijay.kilari
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
^ permalink raw reply related [flat|nested] 15+ messages in thread* [Qemu-devel] [PATCH v3 6/9] cutils: Add generic prefetch
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
` (3 preceding siblings ...)
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 5/9] cutils: Add test for buffer_is_zero Richard Henderson
@ 2016-08-29 18:46 ` Richard Henderson
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking Richard Henderson
` (4 subsequent siblings)
9 siblings, 0 replies; 15+ messages in thread
From: Richard Henderson @ 2016-08-29 18:46 UTC (permalink / raw)
To: qemu-devel; +Cc: pbonzini, vijay.kilari
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
^ permalink raw reply related [flat|nested] 15+ messages in thread* [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
` (4 preceding siblings ...)
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 6/9] cutils: Add generic prefetch Richard Henderson
@ 2016-08-29 18:46 ` Richard Henderson
2016-09-13 13:26 ` Paolo Bonzini
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 8/9] cutils: Remove aarch64 " Richard Henderson
` (3 subsequent siblings)
9 siblings, 1 reply; 15+ messages in thread
From: Richard Henderson @ 2016-08-29 18:46 UTC (permalink / raw)
To: qemu-devel; +Cc: pbonzini, vijay.kilari
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
^ permalink raw reply related [flat|nested] 15+ messages in thread* Re: [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking Richard Henderson
@ 2016-09-13 13:26 ` Paolo Bonzini
2016-09-13 14:17 ` Paolo Bonzini
0 siblings, 1 reply; 15+ messages in thread
From: Paolo Bonzini @ 2016-09-13 13:26 UTC (permalink / raw)
To: Richard Henderson, qemu-devel; +Cc: vijay.kilari
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
^ permalink raw reply related [flat|nested] 15+ messages in thread* Re: [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking
2016-09-13 13:26 ` Paolo Bonzini
@ 2016-09-13 14:17 ` Paolo Bonzini
2016-09-13 14:49 ` Paolo Bonzini
0 siblings, 1 reply; 15+ messages in thread
From: Paolo Bonzini @ 2016-09-13 14:17 UTC (permalink / raw)
To: Richard Henderson, qemu-devel; +Cc: vijay.kilari
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
^ permalink raw reply [flat|nested] 15+ messages in thread* Re: [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking
2016-09-13 14:17 ` Paolo Bonzini
@ 2016-09-13 14:49 ` Paolo Bonzini
2016-09-13 15:47 ` Paolo Bonzini
0 siblings, 1 reply; 15+ messages in thread
From: Paolo Bonzini @ 2016-09-13 14:49 UTC (permalink / raw)
To: Richard Henderson, qemu-devel; +Cc: vijay.kilari
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
^ permalink raw reply [flat|nested] 15+ messages in thread* Re: [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking
2016-09-13 14:49 ` Paolo Bonzini
@ 2016-09-13 15:47 ` Paolo Bonzini
0 siblings, 0 replies; 15+ messages in thread
From: Paolo Bonzini @ 2016-09-13 15:47 UTC (permalink / raw)
To: Richard Henderson, qemu-devel; +Cc: vijay.kilari
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
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Qemu-devel] [PATCH v3 8/9] cutils: Remove aarch64 buffer zero checking
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
` (5 preceding siblings ...)
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 7/9] cutils: Rewrite x86 buffer zero checking Richard Henderson
@ 2016-08-29 18:46 ` Richard Henderson
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 9/9] cutils: Remove ppc " Richard Henderson
` (2 subsequent siblings)
9 siblings, 0 replies; 15+ messages in thread
From: Richard Henderson @ 2016-08-29 18:46 UTC (permalink / raw)
To: qemu-devel; +Cc: pbonzini, vijay.kilari
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
^ permalink raw reply related [flat|nested] 15+ messages in thread* [Qemu-devel] [PATCH v3 9/9] cutils: Remove ppc buffer zero checking
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
` (6 preceding siblings ...)
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 8/9] cutils: Remove aarch64 " Richard Henderson
@ 2016-08-29 18:46 ` Richard Henderson
2016-08-30 11:48 ` [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Paolo Bonzini
2016-09-05 15:08 ` Dr. David Alan Gilbert
9 siblings, 0 replies; 15+ messages in thread
From: Richard Henderson @ 2016-08-29 18:46 UTC (permalink / raw)
To: qemu-devel; +Cc: pbonzini, vijay.kilari
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
^ permalink raw reply related [flat|nested] 15+ messages in thread* Re: [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
` (7 preceding siblings ...)
2016-08-29 18:46 ` [Qemu-devel] [PATCH v3 9/9] cutils: Remove ppc " Richard Henderson
@ 2016-08-30 11:48 ` Paolo Bonzini
2016-09-05 15:08 ` Dr. David Alan Gilbert
9 siblings, 0 replies; 15+ messages in thread
From: Paolo Bonzini @ 2016-08-30 11:48 UTC (permalink / raw)
To: Richard Henderson, qemu-devel; +Cc: vijay.kilari
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
^ permalink raw reply [flat|nested] 15+ messages in thread* Re: [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero
2016-08-29 18:46 [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Richard Henderson
` (8 preceding siblings ...)
2016-08-30 11:48 ` [Qemu-devel] [PATCH v3 0/9] Improve buffer_is_zero Paolo Bonzini
@ 2016-09-05 15:08 ` Dr. David Alan Gilbert
9 siblings, 0 replies; 15+ messages in thread
From: Dr. David Alan Gilbert @ 2016-09-05 15:08 UTC (permalink / raw)
To: Richard Henderson; +Cc: qemu-devel, pbonzini, vijay.kilari
* 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
^ permalink raw reply [flat|nested] 15+ messages in thread