From nobody Sun Apr 28 09:02:37 2024 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass header.i=@intel.com; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=intel.com ARC-Seal: i=1; a=rsa-sha256; t=1658415214; cv=none; d=zohomail.com; s=zohoarc; b=XvAxb41tdlbvbZ0UQ8M4qrJRAjHJIeeueYQaUH+7EOtQ0uyItRVJAPaAVwzUTp8H4sROVEZIB89R+x64X61RxfIXRZXrMPAKGuonLap44PD64l3jnNzrMKNd5mCdzTWIxM81AAHI3FS9yfaij9yux2ajkwHWojZ60rCzYTAa8Mo= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1658415214; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:References:Sender:Subject:To; bh=/isU2lU5WalOaaecF6LptZskO6su5e0VXJLdhUSFbF4=; b=MXjp+qivTbzZGhri8Ido8ycrCWewney1mko/aBhckByg9xTsyA8mkN4ugFMJunVuU9YuKo4CZKJlnfxDltRif7F/vGtWragt0sLTKJdZSEMfv4LM4AbLwG3NDfUFpilWXIL/5azStlWPnE80tTltYxXSINmbBNjcUDdg/lQyFik= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass header.i=@intel.com; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1658415214400567.2515263662635; Thu, 21 Jul 2022 07:53:34 -0700 (PDT) Received: from localhost ([::1]:54996 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oEXYS-0006Ry-4l for importer@patchew.org; Thu, 21 Jul 2022 10:53:32 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:41236) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oETTO-0005N7-Ba for qemu-devel@nongnu.org; Thu, 21 Jul 2022 06:32:02 -0400 Received: from mga17.intel.com ([192.55.52.151]:1766) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oETTK-0000x9-No for qemu-devel@nongnu.org; Thu, 21 Jul 2022 06:32:01 -0400 Received: from orsmga002.jf.intel.com ([10.7.209.21]) by fmsmga107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 21 Jul 2022 03:31:57 -0700 Received: from xuling-b360m-d3h.sh.intel.com ([10.239.82.110]) by orsmga002.jf.intel.com with ESMTP; 21 Jul 2022 03:31:55 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1658399518; x=1689935518; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=6Yx+QD6dGs3wP6H+5PYyzmKCBqlBXkJP6ASzkZMAkts=; b=P4nrAlRJab4awiPcAYyzm3wGJtWGg7wksug6utjQM/1qlnydTPGkGTFF wZi1elKMOxg8/Mh5XvAEVD3bR5pb0a5f8TNu/abRMzy9rOf4atdRlAl7i NBDFs6rMXF68ex1FGdUY8XsDOx4iTRKGWQ83m5H0zh4SMXXw3ZZO/ALYM wx8wcXvQeU/6zhpqpxvKqGGp1HSXL63SXLZWTH8+QW+x8qaq7PjRXX0mL VpHSgprORoTKxYp2q4QNMprjDTJV48t4h4gKtsCU+JPjunIcfkheyGhlO 4JDCxLj5sbBOeVuCRJYzdqZwcdo2BdupiO2QuzA0MPGTijs1HJ+YjMvJ7 w==; X-IronPort-AV: E=McAfee;i="6400,9594,10414"; a="267407928" X-IronPort-AV: E=Sophos;i="5.92,289,1650956400"; d="scan'208";a="267407928" X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.92,289,1650956400"; d="scan'208";a="598415364" From: ling xu To: qemu-devel@nongnu.org Cc: quintela@redhat.com, dgilbert@redhat.com, ling xu , Zhou Zhao , Jun Jin Subject: [PATCH 1/1] Add AVX512 support for xbzrle_encode_buffer function Date: Thu, 21 Jul 2022 18:31:47 +0800 Message-Id: <20220721103147.96608-2-ling1.xu@intel.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220721103147.96608-1-ling1.xu@intel.com> References: <20220721103147.96608-1-ling1.xu@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=192.55.52.151; envelope-from=ling1.xu@intel.com; helo=mga17.intel.com X-Spam_score_int: -44 X-Spam_score: -4.5 X-Spam_bar: ---- X-Spam_report: (-4.5 / 5.0 requ) BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.082, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-Mailman-Approved-At: Thu, 21 Jul 2022 10:50:32 -0400 X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" X-ZohoMail-DKIM: pass (identity @intel.com) X-ZM-MESSAGEID: 1658415216865100001 Content-Type: text/plain; charset="utf-8" This commit adds AVX512 implementation of xbzrle_encode_buffer function to accelerate xbzrle encoding speed. Compared with C version of xbzrle_encode_= buffer function, AVX512 version can achieve almost 60%-70% performance improvement on unit t= est provided by qemu. In addition, we provide one more unit test called "test_encode_decode_rando= m", in which dirty data are randomly located in 4K page, and this case can achieve almos= t 140% performance gain. Signed-off-by: ling xu Co-authored-by: Zhou Zhao Co-authored-by: Jun Jin --- configure | 434 ++++++++++++++++++++++++++++++++++++++- migration/ram.c | 6 + migration/xbzrle.c | 177 ++++++++++++++++ migration/xbzrle.h | 4 + tests/unit/test-xbzrle.c | 307 +++++++++++++++++++++++++-- 5 files changed, 908 insertions(+), 20 deletions(-) diff --git a/configure b/configure index 4f12481765..7685479297 100755 --- a/configure +++ b/configure @@ -587,6 +587,431 @@ else cpu=3D$(uname -m) fi =20 +# cpu flag for x86 +x86_cpu_flags=3D"" + +get_x86_cpu_flags(){ + # check sse flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m128 a,b; + int res=3D _mm_ucomieq_ss(a,b); + return 0; +} +EOF + local_cpu_flag=3D"-msse" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -msse" + fi + + # check sse2 flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m128d a,b; + int res=3D _mm_ucomineq_sd (a, b); + return 0; +} +EOF + local_cpu_flag=3D"-msse2" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -msse2" + fi + + # check sse3 flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m128 a; + __m128 res=3D _mm_moveldup_ps (a); + return 0; +} +EOF + local_cpu_flag=3D"-msse3" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -msse3" + fi + + # check ssse3 flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m128i a; + __m12i8 res=3D _mm_abs_epi32 (a); + return 0; +} +EOF + local_cpu_flag=3D"-mssse3" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mssse3" + fi + + # check sse4.1 flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m128 a; + __m128 res=3D_mm_ceil_ps (a); + return 0; +} +EOF + local_cpu_flag=3D"-msse4.1" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -msse4.1" + fi + + # check sse4.2 flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m128i a,b; + __m128i res=3D_mm_cmpgt_epi64 (a,b); + return 0; +} +EOF + local_cpu_flag=3D"-msse4.2" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -msse4.2" + fi + + # check avx flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m256 a; + __m256 res=3D _mm256_ceil_ps(a); + return 0; +} +EOF + local_cpu_flag=3D"-mavx" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx" + fi + + # check avx2 flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m256i a; + __m256i res=3D _mm256_abs_epi32(a); + return 0; +} +EOF + local_cpu_flag=3D"-mavx2" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx2" + fi + + # check AVX_VNNI flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m128i a,b,c; + __m128i res=3D _mm_dpbusd_epi32(a,b,c); + return 0; +} +EOF + local_cpu_flag=3D"-mavxvnni" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavxvnni" + fi + + # check AVX512f flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m128d a; + __m512d res=3D _mm512_broadcastsd_pd(a); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512f" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512f" + fi + + # check AVX512bw flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512i a; + __m512i res=3D _mm512_abs_epi8(a); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512bw" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512bw" + fi + + # check AVX512CD flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512i a; + __mmask16 k; + __m512i res=3D _mm512_maskz_lzcnt_epi32 (k, a); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512cd" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512cd" + fi + + # check AVX512DQ flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __mmask8 a,b; + __mmask8 res=3D_kxor_mask8(a,b); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512dq" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512dq" + fi + + # check AVX512ER flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512d a; + __m512d res=3D_mm512_rsqrt28_pd(a); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512er" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512er" + fi + + # check AVX512IFMA52 flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512i a,b,c; + __m512i res=3D _mm512_madd52lo_epu64 (a, b, c); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512ifma" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512ifma" + fi + + # check AVX512PF flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + char* base_addr; + __mmask8 k; + __m512i vindex; + _mm512_mask_prefetch_i64scatter_pd (base_addr, k, vindex, 1, 2); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512pf" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512pf" + fi + + # check AVX512VPOPCNTDQ flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512i a; + __mmask8 k; + __m512i res=3D _mm512_maskz_popcnt_epi64(k,a); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512vpopcntdq" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512vpopcntdq" + fi + + # check AVX512_4VNNIW flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512i a,b,c,d,e; + __m128 g; + __m512i res=3D _mm512_4dpwssd_epi32 (a, b, c, d, e, &g); + return 0; +} +EOF + local_cpu_flag=3D"-mavx5124vnniw" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx5124vnniw" + fi + + # check AVX512_BITALG flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512i a; + __m512i res=3D _mm512_popcnt_epi16 (a); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512bitalg" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512bitalg" + fi + + # check AVX512_VBMI flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512i a,b,c; + __m512i res=3D _mm512_permutex2var_epi8 (a, b, c); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512vbmi" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512vbmi" + fi + + # check AVX512_VBMI2 flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512i a,b,c; + __m512i res=3D _mm512_shrdv_epi64 (a, b, c); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512vbmi2" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512vbmi2" + fi + + # check AVX512_VNNI flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m512i a,b,c; + __mmask16 k; + __m512i res=3D _mm512_maskz_dpwssds_epi32 (k,a, b, c); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512vnni" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512vnni" + fi + + # check AVX512_FP16 flag + cat > $TMPC << EOF +#include +int main(int argc, char *argv[]) +{ + __m128h a; + __m128 res=3D _mm_castph_ps (a); + return 0; +} +EOF + local_cpu_flag=3D"-mavx512fp16" + rm -f $TMPE + do_cc $local_cpu_flag -o $TMPE $TMPC + if [ -e $TMPE ] + then + x86_cpu_flags=3D"$x86_cpu_flags -mavx512fp16" + fi +} + # Normalise host CPU name, set multilib cflags # Note that this case should only have supported host CPUs, not guests. case "$cpu" in @@ -595,16 +1020,19 @@ case "$cpu" in =20 i386|i486|i586|i686|i86pc|BePC) cpu=3D"i386" - CPU_CFLAGS=3D"-m32" ;; + get_x86_cpu_flags + CPU_CFLAGS=3D"-m32 $x86_cpu_flags" ;; x32) cpu=3D"x86_64" - CPU_CFLAGS=3D"-mx32" ;; + get_x86_cpu_flags + CPU_CFLAGS=3D"-mx32 $x86_cpu_flags" ;; x86_64|amd64) cpu=3D"x86_64" + get_x86_cpu_flags # ??? Only extremely old AMD cpus do not have cmpxchg16b. # If we truly care, we should simply detect this case at # runtime and generate the fallback to serial emulation. - CPU_CFLAGS=3D"-m64 -mcx16" ;; + CPU_CFLAGS=3D"-m64 -mcx16 $x86_cpu_flags" ;; =20 mips*) cpu=3D"mips" ;; diff --git a/migration/ram.c b/migration/ram.c index 01f9cc1d72..3b931c325f 100644 --- a/migration/ram.c +++ b/migration/ram.c @@ -747,9 +747,15 @@ static int save_xbzrle_page(RAMState *rs, uint8_t **cu= rrent_data, memcpy(XBZRLE.current_buf, *current_data, TARGET_PAGE_SIZE); =20 /* XBZRLE encoding (if there is no overflow) */ + #if defined(__x86_64__) && defined(__AVX512BW__) + encoded_len =3D xbzrle_encode_buffer_512(prev_cached_page, XBZRLE.curr= ent_buf, + TARGET_PAGE_SIZE, XBZRLE.encoded_bu= f, + TARGET_PAGE_SIZE); + #else encoded_len =3D xbzrle_encode_buffer(prev_cached_page, XBZRLE.current_= buf, TARGET_PAGE_SIZE, XBZRLE.encoded_bu= f, TARGET_PAGE_SIZE); + #endif =20 /* * Update the cache contents, so that it corresponds to the data diff --git a/migration/xbzrle.c b/migration/xbzrle.c index 1ba482ded9..9eea1c0a5f 100644 --- a/migration/xbzrle.c +++ b/migration/xbzrle.c @@ -174,3 +174,180 @@ int xbzrle_decode_buffer(uint8_t *src, int slen, uint= 8_t *dst, int dlen) =20 return d; } + +#if defined(__x86_64__) && defined(__AVX512BW__) +#include +#include +#define SET_ZERO512(r) r =3D _mm512_set1_epi32(0) +int xbzrle_encode_buffer_512(uint8_t *old_buf, uint8_t *new_buf, int slen, + uint8_t *dst, int dlen) +{ + uint32_t zrun_len =3D 0, nzrun_len =3D 0; + int d =3D 0, i =3D 0, num =3D 0; + uint8_t *nzrun_start =3D NULL; + int count512s =3D (slen >> 6); + int res =3D slen % 64; + bool never_same =3D true; + while (count512s--) { + if (d + 2 > dlen) { + return -1; + } + __m512i old_data =3D _mm512_mask_loadu_epi8(old_data, + 0xffffffffffffffff, old_buf + i); + __m512i new_data =3D _mm512_mask_loadu_epi8(new_data, + 0xffffffffffffffff, new_b= uf + i); + /* in mask bit 1 for same, 0 for diff */ + __mmask64 comp =3D _mm512_cmpeq_epi8_mask(old_data, new_data); + + int bytesToCheck =3D 64; + bool is_same =3D (comp & 0x1); + while (bytesToCheck) { + if (is_same) { + if (nzrun_len) { + d +=3D uleb128_encode_small(dst + d, nzrun_len); + if (d + nzrun_len > dlen) { + return -1; + } + nzrun_start =3D new_buf + i - nzrun_len; + memcpy(dst + d, nzrun_start, nzrun_len); + d +=3D nzrun_len; + nzrun_len =3D 0; + } + if (comp =3D=3D 0xffffffffffffffff) { + i +=3D 64; + zrun_len +=3D 64; + break; + } + never_same =3D false; + num =3D __builtin_ctzl(~comp); + num =3D (num < bytesToCheck) ? num : bytesToCheck; + zrun_len +=3D num; + bytesToCheck -=3D num; + comp >>=3D num; + i +=3D num; + if (bytesToCheck) { + /* still has different data after same data */ + d +=3D uleb128_encode_small(dst + d, zrun_len); + zrun_len =3D 0; + } else { + break; + } + } + if (never_same || zrun_len) { + /* + * never_same only acts if + * data begins with diff in first count512s + */ + d +=3D uleb128_encode_small(dst + d, zrun_len); + zrun_len =3D 0; + never_same =3D false; + } + /* has diff */ + if ((bytesToCheck =3D=3D 64) && (comp =3D=3D 0x0)) { + i +=3D 64; + nzrun_len +=3D 64; + break; + } + num =3D __builtin_ctzl(comp); + num =3D (num < bytesToCheck) ? num : bytesToCheck; + nzrun_len +=3D num; + bytesToCheck -=3D num; + comp >>=3D num; + i +=3D num; + if (bytesToCheck) { + /* mask like 111000 */ + d +=3D uleb128_encode_small(dst + d, nzrun_len); + /* overflow */ + if (d + nzrun_len > dlen) { + return -1; + } + nzrun_start =3D new_buf + i - nzrun_len; + memcpy(dst + d, nzrun_start, nzrun_len); + d +=3D nzrun_len; + nzrun_len =3D 0; + is_same =3D true; + } + } + } + if (res) { + /* the number of data is less than 64 */ + unsigned long long mask =3D pow(2, res); + mask -=3D 1; + __m512i r =3D SET_ZERO512(r); + __m512i old_data =3D _mm512_mask_loadu_epi8(r, mask, old_buf + i); + __m512i new_data =3D _mm512_mask_loadu_epi8(r, mask, new_buf + i); + __mmask64 comp =3D _mm512_cmpeq_epi8_mask(old_data, new_data); + + int bytesToCheck =3D res; + bool is_same =3D (comp & 0x1); + while (bytesToCheck) { + if (is_same) { + if (nzrun_len) { + d +=3D uleb128_encode_small(dst + d, nzrun_len); + if (d + nzrun_len > dlen) { + return -1; + } + nzrun_start =3D new_buf + i - nzrun_len; + memcpy(dst + d, nzrun_start, nzrun_len); + d +=3D nzrun_len; + nzrun_len =3D 0; + } + never_same =3D false; + num =3D __builtin_ctzl(~comp); + num =3D (num < bytesToCheck) ? num : bytesToCheck; + zrun_len +=3D num; + bytesToCheck -=3D num; + comp >>=3D num; + i +=3D num; + if (bytesToCheck) { + /* diff after same */ + d +=3D uleb128_encode_small(dst + d, zrun_len); + zrun_len =3D 0; + } else { + break; + } + } + + if (never_same || zrun_len) { + d +=3D uleb128_encode_small(dst + d, zrun_len); + zrun_len =3D 0; + never_same =3D false; + } + /* has diff */ + num =3D __builtin_ctzl(comp); + num =3D (num < bytesToCheck) ? num : bytesToCheck; + nzrun_len +=3D num; + bytesToCheck -=3D num; + comp >>=3D num; + i +=3D num; + if (bytesToCheck) { + d +=3D uleb128_encode_small(dst + d, nzrun_len); + /* overflow */ + if (d + nzrun_len > dlen) { + return -1; + } + nzrun_start =3D new_buf + i - nzrun_len; + memcpy(dst + d, nzrun_start, nzrun_len); + d +=3D nzrun_len; + nzrun_len =3D 0; + is_same =3D true; + } + } + } + + if (zrun_len) { + return (zrun_len =3D=3D slen) ? 0 : d; + } + if (nzrun_len !=3D 0) { + d +=3D uleb128_encode_small(dst + d, nzrun_len); + /* overflow */ + if (d + nzrun_len > dlen) { + return -1; + } + nzrun_start =3D new_buf + i - nzrun_len; + memcpy(dst + d, nzrun_start, nzrun_len); + d +=3D nzrun_len; + } + return d; +} +#endif diff --git a/migration/xbzrle.h b/migration/xbzrle.h index a0db507b9c..e03ee51d3a 100644 --- a/migration/xbzrle.h +++ b/migration/xbzrle.h @@ -18,4 +18,8 @@ int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_b= uf, int slen, uint8_t *dst, int dlen); =20 int xbzrle_decode_buffer(uint8_t *src, int slen, uint8_t *dst, int dlen); +#if defined(__x86_64__) && defined(__AVX512BW__) +int xbzrle_encode_buffer_512(uint8_t *old_buf, uint8_t *new_buf, int slen, + uint8_t *dst, int dlen); +#endif #endif diff --git a/tests/unit/test-xbzrle.c b/tests/unit/test-xbzrle.c index ef951b6e54..653016826f 100644 --- a/tests/unit/test-xbzrle.c +++ b/tests/unit/test-xbzrle.c @@ -38,111 +38,280 @@ static void test_uleb(void) g_assert(val =3D=3D 0); } =20 -static void test_encode_decode_zero(void) +static float *test_encode_decode_zero(void) { uint8_t *buffer =3D g_malloc0(XBZRLE_PAGE_SIZE); uint8_t *compressed =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *buffer512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *compressed512 =3D g_malloc0(XBZRLE_PAGE_SIZE); int i =3D 0; - int dlen =3D 0; + int dlen =3D 0, dlen512 =3D 0; int diff_len =3D g_test_rand_int_range(0, XBZRLE_PAGE_SIZE - 1006); =20 for (i =3D diff_len; i > 0; i--) { buffer[1000 + i] =3D i; + buffer512[1000 + i] =3D i; } =20 buffer[1000 + diff_len + 3] =3D 103; buffer[1000 + diff_len + 5] =3D 105; =20 + buffer512[1000 + diff_len + 3] =3D 103; + buffer512[1000 + diff_len + 5] =3D 105; + /* encode zero page */ + time_t t_start, t_end, t_start512, t_end512; + t_start =3D clock(); dlen =3D xbzrle_encode_buffer(buffer, buffer, XBZRLE_PAGE_SIZE, compre= ssed, XBZRLE_PAGE_SIZE); + t_end =3D clock(); + float time_val =3D difftime(t_end, t_start); g_assert(dlen =3D=3D 0); =20 + t_start512 =3D clock(); + dlen512 =3D xbzrle_encode_buffer_512(buffer512, buffer512, XBZRLE_PAGE= _SIZE, + compressed512, XBZRLE_PAGE_SIZE); + t_end512 =3D clock(); + float time_val512 =3D difftime(t_end512, t_start512); + g_assert(dlen512 =3D=3D 0); + + static float result_zero[2]; + result_zero[0] =3D time_val; + result_zero[1] =3D time_val512; + g_free(buffer); g_free(compressed); + g_free(buffer512); + g_free(compressed512); + + return result_zero; +} + +static void test_encode_decode_zero_range(void) +{ + int i; + float time_raw =3D 0.0, time_512 =3D 0.0; + float *res; + for (i =3D 0; i < 10000; i++) { + res =3D test_encode_decode_zero(); + time_raw +=3D res[0]; + time_512 +=3D res[1]; + } + printf("Zero test:\n"); + printf("Raw xbzrle_encode time is %f ms\n", time_raw); + printf("512 xbzrle_encode time is %f ms\n", time_512); } =20 -static void test_encode_decode_unchanged(void) +static float *test_encode_decode_unchanged(void) { uint8_t *compressed =3D g_malloc0(XBZRLE_PAGE_SIZE); uint8_t *test =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *compressed512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *test512 =3D g_malloc0(XBZRLE_PAGE_SIZE); int i =3D 0; - int dlen =3D 0; + int dlen =3D 0, dlen512 =3D 0; int diff_len =3D g_test_rand_int_range(0, XBZRLE_PAGE_SIZE - 1006); =20 for (i =3D diff_len; i > 0; i--) { test[1000 + i] =3D i + 4; + test512[1000 + i] =3D i + 4; } =20 test[1000 + diff_len + 3] =3D 107; test[1000 + diff_len + 5] =3D 109; =20 + test512[1000 + diff_len + 3] =3D 107; + test512[1000 + diff_len + 5] =3D 109; + /* test unchanged buffer */ + time_t t_start, t_end, t_start512, t_end512; + t_start =3D clock(); dlen =3D xbzrle_encode_buffer(test, test, XBZRLE_PAGE_SIZE, compressed, XBZRLE_PAGE_SIZE); + t_end =3D clock(); + float time_val =3D difftime(t_end, t_start); g_assert(dlen =3D=3D 0); =20 + t_start512 =3D clock(); + dlen512 =3D xbzrle_encode_buffer_512(test512, test512, XBZRLE_PAGE_SIZ= E, + compressed512, XBZRLE_PAGE_SIZE); + t_end512 =3D clock(); + float time_val512 =3D difftime(t_end512, t_start512); + g_assert(dlen512 =3D=3D 0); + + static float result_unchanged[2]; + result_unchanged[0] =3D time_val; + result_unchanged[1] =3D time_val512; + g_free(test); g_free(compressed); + g_free(test512); + g_free(compressed512); + + return result_unchanged; } =20 -static void test_encode_decode_1_byte(void) +static void test_encode_decode_unchanged_range(void) +{ + int i; + float time_raw =3D 0.0, time_512 =3D 0.0; + float *res; + for (i =3D 0; i < 10000; i++) { + res =3D test_encode_decode_unchanged(); + time_raw +=3D res[0]; + time_512 +=3D res[1]; + } + printf("Unchanged test:\n"); + printf("Raw xbzrle_encode time is %f ms\n", time_raw); + printf("512 xbzrle_encode time is %f ms\n", time_512); +} + +static float *test_encode_decode_1_byte(void) { uint8_t *buffer =3D g_malloc0(XBZRLE_PAGE_SIZE); uint8_t *test =3D g_malloc0(XBZRLE_PAGE_SIZE); uint8_t *compressed =3D g_malloc(XBZRLE_PAGE_SIZE); - int dlen =3D 0, rc =3D 0; + uint8_t *buffer512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *test512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *compressed512 =3D g_malloc(XBZRLE_PAGE_SIZE); + int dlen =3D 0, rc =3D 0, dlen512 =3D 0, rc512 =3D 0; uint8_t buf[2]; + uint8_t buf512[2]; =20 test[XBZRLE_PAGE_SIZE - 1] =3D 1; + test512[XBZRLE_PAGE_SIZE - 1] =3D 1; =20 + time_t t_start, t_end, t_start512, t_end512; + t_start =3D clock(); dlen =3D xbzrle_encode_buffer(buffer, test, XBZRLE_PAGE_SIZE, compress= ed, XBZRLE_PAGE_SIZE); + t_end =3D clock(); + float time_val =3D difftime(t_end, t_start); g_assert(dlen =3D=3D (uleb128_encode_small(&buf[0], 4095) + 2)); =20 rc =3D xbzrle_decode_buffer(compressed, dlen, buffer, XBZRLE_PAGE_SIZE= ); g_assert(rc =3D=3D XBZRLE_PAGE_SIZE); g_assert(memcmp(test, buffer, XBZRLE_PAGE_SIZE) =3D=3D 0); =20 + t_start512 =3D clock(); + dlen512 =3D xbzrle_encode_buffer_512(buffer512, test512, XBZRLE_PAGE_S= IZE, + compressed512, XBZRLE_PAGE_SIZE); + t_end512 =3D clock(); + float time_val512 =3D difftime(t_end512, t_start512); + g_assert(dlen512 =3D=3D (uleb128_encode_small(&buf512[0], 4095) + 2)); + + rc512 =3D xbzrle_decode_buffer(compressed512, dlen512, buffer512, + XBZRLE_PAGE_SIZE); + g_assert(rc512 =3D=3D XBZRLE_PAGE_SIZE); + g_assert(memcmp(test512, buffer512, XBZRLE_PAGE_SIZE) =3D=3D 0); + + static float result_1_byte[2]; + result_1_byte[0] =3D time_val; + result_1_byte[1] =3D time_val512; + g_free(buffer); g_free(compressed); g_free(test); + g_free(buffer512); + g_free(compressed512); + g_free(test512); + + return result_1_byte; } =20 -static void test_encode_decode_overflow(void) +static void test_encode_decode_1_byte_range(void) +{ + int i; + float time_raw =3D 0.0, time_512 =3D 0.0; + float *res; + for (i =3D 0; i < 10000; i++) { + res =3D test_encode_decode_1_byte(); + time_raw +=3D res[0]; + time_512 +=3D res[1]; + } + printf("1 byte test:\n"); + printf("Raw xbzrle_encode time is %f ms\n", time_raw); + printf("512 xbzrle_encode time is %f ms\n", time_512); +} + +static float *test_encode_decode_overflow(void) { uint8_t *compressed =3D g_malloc0(XBZRLE_PAGE_SIZE); uint8_t *test =3D g_malloc0(XBZRLE_PAGE_SIZE); uint8_t *buffer =3D g_malloc0(XBZRLE_PAGE_SIZE); - int i =3D 0, rc =3D 0; + uint8_t *compressed512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *test512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *buffer512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + int i =3D 0, rc =3D 0, rc512 =3D 0; =20 for (i =3D 0; i < XBZRLE_PAGE_SIZE / 2 - 1; i++) { test[i * 2] =3D 1; + test512[i * 2] =3D 1; } =20 /* encode overflow */ + time_t t_start, t_end, t_start512, t_end512; + t_start =3D clock(); rc =3D xbzrle_encode_buffer(buffer, test, XBZRLE_PAGE_SIZE, compressed, XBZRLE_PAGE_SIZE); + t_end =3D clock(); + float time_val =3D difftime(t_end, t_start); g_assert(rc =3D=3D -1); =20 + t_start512 =3D clock(); + rc512 =3D xbzrle_encode_buffer_512(buffer512, test512, XBZRLE_PAGE_SIZ= E, + compressed512, XBZRLE_PAGE_SIZE); + t_end512 =3D clock(); + float time_val512 =3D difftime(t_end512, t_start512); + g_assert(rc512 =3D=3D -1); + + static float result_overflow[2]; + result_overflow[0] =3D time_val; + result_overflow[1] =3D time_val512; + g_free(buffer); g_free(compressed); g_free(test); + g_free(buffer512); + g_free(compressed512); + g_free(test512); + + return result_overflow; +} + +static void test_encode_decode_overflow_range(void) +{ + int i; + float time_raw =3D 0.0, time_512 =3D 0.0; + float *res; + for (i =3D 0; i < 10000; i++) { + res =3D test_encode_decode_overflow(); + time_raw +=3D res[0]; + time_512 +=3D res[1]; + } + printf("Overflow test:\n"); + printf("Raw xbzrle_encode time is %f ms\n", time_raw); + printf("512 xbzrle_encode time is %f ms\n", time_512); } =20 -static void encode_decode_range(void) +static float *encode_decode_range(void) { uint8_t *buffer =3D g_malloc0(XBZRLE_PAGE_SIZE); uint8_t *compressed =3D g_malloc(XBZRLE_PAGE_SIZE); uint8_t *test =3D g_malloc0(XBZRLE_PAGE_SIZE); - int i =3D 0, rc =3D 0; - int dlen =3D 0; + uint8_t *buffer512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *compressed512 =3D g_malloc(XBZRLE_PAGE_SIZE); + uint8_t *test512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + int i =3D 0, rc =3D 0, rc512 =3D 0; + int dlen =3D 0, dlen512 =3D 0; =20 int diff_len =3D g_test_rand_int_range(0, XBZRLE_PAGE_SIZE - 1006); =20 for (i =3D diff_len; i > 0; i--) { buffer[1000 + i] =3D i; test[1000 + i] =3D i + 4; + buffer512[1000 + i] =3D i; + test512[1000 + i] =3D i + 4; } =20 buffer[1000 + diff_len + 3] =3D 103; @@ -151,26 +320,129 @@ static void encode_decode_range(void) buffer[1000 + diff_len + 5] =3D 105; test[1000 + diff_len + 5] =3D 109; =20 + buffer512[1000 + diff_len + 3] =3D 103; + test512[1000 + diff_len + 3] =3D 107; + + buffer512[1000 + diff_len + 5] =3D 105; + test512[1000 + diff_len + 5] =3D 109; + /* test encode/decode */ + time_t t_start, t_end, t_start512, t_end512; + t_start =3D clock(); dlen =3D xbzrle_encode_buffer(test, buffer, XBZRLE_PAGE_SIZE, compress= ed, XBZRLE_PAGE_SIZE); - + t_end =3D clock(); + float time_val =3D difftime(t_end, t_start); rc =3D xbzrle_decode_buffer(compressed, dlen, test, XBZRLE_PAGE_SIZE); g_assert(rc < XBZRLE_PAGE_SIZE); g_assert(memcmp(test, buffer, XBZRLE_PAGE_SIZE) =3D=3D 0); =20 + t_start512 =3D clock(); + dlen512 =3D xbzrle_encode_buffer_512(test512, buffer512, XBZRLE_PAGE_S= IZE, + compressed512, XBZRLE_PAGE_SIZE); + t_end512 =3D clock(); + float time_val512 =3D difftime(t_end512, t_start512); + rc512 =3D xbzrle_decode_buffer(compressed512, dlen512, test512, XBZRLE= _PAGE_SIZE); + g_assert(rc512 < XBZRLE_PAGE_SIZE); + g_assert(memcmp(test512, buffer512, XBZRLE_PAGE_SIZE) =3D=3D 0); + + static float result_range[2]; + result_range[0] =3D time_val; + result_range[1] =3D time_val512; + g_free(buffer); g_free(compressed); g_free(test); + g_free(buffer512); + g_free(compressed512); + g_free(test512); + + return result_range; } =20 static void test_encode_decode(void) { int i; + float time_raw =3D 0.0, time_512 =3D 0.0; + float *res; + for (i =3D 0; i < 10000; i++) { + res =3D encode_decode_range(); + time_raw +=3D res[0]; + time_512 +=3D res[1]; + } + printf("Encode decode test:\n"); + printf("Raw xbzrle_encode time is %f ms\n", time_raw); + printf("512 xbzrle_encode time is %f ms\n", time_512); +} =20 +static float *encode_decode_random(void) +{ + uint8_t *buffer =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *compressed =3D g_malloc(XBZRLE_PAGE_SIZE); + uint8_t *test =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *buffer512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + uint8_t *compressed512 =3D g_malloc(XBZRLE_PAGE_SIZE); + uint8_t *test512 =3D g_malloc0(XBZRLE_PAGE_SIZE); + int i =3D 0, rc =3D 0, rc512 =3D 0; + int dlen =3D 0, dlen512 =3D 0; + + int diff_len =3D g_test_rand_int_range(0, XBZRLE_PAGE_SIZE - 1); + /* store the index of diff */ + int dirty_index[diff_len]; + for (int j =3D 0; j < diff_len; j++) { + dirty_index[j] =3D g_test_rand_int_range(0, XBZRLE_PAGE_SIZE - 1); + } + for (i =3D diff_len - 1; i >=3D 0; i--) { + buffer[dirty_index[i]] =3D i; + test[dirty_index[i]] =3D i + 4; + buffer512[dirty_index[i]] =3D i; + test512[dirty_index[i]] =3D i + 4; + } + + time_t t_start, t_end, t_start512, t_end512; + t_start =3D clock(); + dlen =3D xbzrle_encode_buffer(test, buffer, XBZRLE_PAGE_SIZE, compress= ed, + XBZRLE_PAGE_SIZE); + t_end =3D clock(); + float time_val =3D difftime(t_end, t_start); + rc =3D xbzrle_decode_buffer(compressed, dlen, test, XBZRLE_PAGE_SIZE); + g_assert(rc < XBZRLE_PAGE_SIZE); + + t_start512 =3D clock(); + dlen512 =3D xbzrle_encode_buffer_512(test512, buffer512, XBZRLE_PAGE_S= IZE, + compressed512, XBZRLE_PAGE_SIZE); + t_end512 =3D clock(); + float time_val512 =3D difftime(t_end512, t_start512); + rc512 =3D xbzrle_decode_buffer(compressed512, dlen512, test512, XBZRLE= _PAGE_SIZE); + g_assert(rc512 < XBZRLE_PAGE_SIZE); + + static float result_random[2]; + result_random[0] =3D time_val; + result_random[1] =3D time_val512; + + g_free(buffer); + g_free(compressed); + g_free(test); + g_free(buffer512); + g_free(compressed512); + g_free(test512); + + return result_random; +} + +static void test_encode_decode_random(void) +{ + int i; + float time_raw =3D 0.0, time_512 =3D 0.0; + float *res; for (i =3D 0; i < 10000; i++) { - encode_decode_range(); + res =3D encode_decode_random(); + time_raw +=3D res[0]; + time_512 +=3D res[1]; } + printf("Random test:\n"); + printf("Raw xbzrle_encode time is %f ms\n", time_raw); + printf("512 xbzrle_encode time is %f ms\n", time_512); } =20 int main(int argc, char **argv) @@ -178,13 +450,14 @@ int main(int argc, char **argv) g_test_init(&argc, &argv, NULL); g_test_rand_int(); g_test_add_func("/xbzrle/uleb", test_uleb); - g_test_add_func("/xbzrle/encode_decode_zero", test_encode_decode_zero); + g_test_add_func("/xbzrle/encode_decode_zero", test_encode_decode_zero_= range); g_test_add_func("/xbzrle/encode_decode_unchanged", - test_encode_decode_unchanged); - g_test_add_func("/xbzrle/encode_decode_1_byte", test_encode_decode_1_b= yte); + test_encode_decode_unchanged_range); + g_test_add_func("/xbzrle/encode_decode_1_byte", test_encode_decode_1_b= yte_range); g_test_add_func("/xbzrle/encode_decode_overflow", - test_encode_decode_overflow); + test_encode_decode_overflow_range); g_test_add_func("/xbzrle/encode_decode", test_encode_decode); + g_test_add_func("/xbzrle/encode_decode_random", test_encode_decode_ran= dom); =20 return g_test_run(); } --=20 2.25.1