Received-SPF: pass (google.com: domain of linux-kernel+bounces-36480-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) client-ip=2604:1380:45e3:2400::1;
From: "Wang, Xiao W" <xiao.w.wang@intel.com>
To: Andrew Jones <ajones@ventanamicro.com>, David Laight
	<David.Laight@aculab.com>
CC: "paul.walmsley@sifive.com" <paul.walmsley@sifive.com>,
	"palmer@dabbelt.com" <palmer@dabbelt.com>, "aou@eecs.berkeley.edu"
	<aou@eecs.berkeley.edu>, "conor.dooley@microchip.com"
	<conor.dooley@microchip.com>, "heiko@sntech.de" <heiko@sntech.de>, "Li,
 Haicheng" <haicheng.li@intel.com>, "linux-riscv@lists.infradead.org"
	<linux-riscv@lists.infradead.org>, "linux-kernel@vger.kernel.org"
	<linux-kernel@vger.kernel.org>
Subject: RE: [PATCH] riscv: Optimize crc32 with Zbc extension
Thread-Topic: [PATCH] riscv: Optimize crc32 with Zbc extension
Thread-Index: AQHaP65h4Tgp9DgCwEu/ue2vJWxme7DcmyaAgAvSDaA=
Date: Wed, 24 Jan 2024 05:44:52 +0000
Message-ID: <BL3PR11MB5747805F781890D336A417D7B87B2@BL3PR11MB5747.namprd11.prod.outlook.com>
References: <20240105080830.3738117-1-xiao.w.wang@intel.com>
 <20240116-9f09b002afc2337ab5e41e3f@orel>
In-Reply-To: <20240116-9f09b002afc2337ab5e41e3f@orel>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?Windows-1252?Q?dUh/sl15NP7vOdlxpgFg5BsUDjKXrguQTSEK+9YoMZZCR45fFVbL5bkz?=
 =?Windows-1252?Q?zZ52fhxtFlWoswHtr0NWappNiSjf+3iWBTh7nxuSVcYRwFwAvHfffAH+?=
 =?Windows-1252?Q?MsdQhQgR8BzGGwTrg2PZSQkMhhVwwsG+vIn1/ecTI4Gb2F0+YHvnFzQO?=
 =?Windows-1252?Q?Bt8Ji3lPgpUu+FgBeiMvmfu6V4bCNWjfke2pl3psxyTT3c/g9XCJCTGF?=
 =?Windows-1252?Q?qSTKTzTtg2AhqX1AwanEqJzwkCGrCy+rBSyWff97Vy2u/hnOTRyF1AtO?=
 =?Windows-1252?Q?ghVunh5/utgT/NPMXYCpRBcXefe6+0bnPBe/pqtZIr3ftSjDcrnslyFS?=
 =?Windows-1252?Q?vv7dgfirXOM8tq7ISdgo31PUpdEkeWzzxLNzMICRzbvlTf0JU9OnX3Ko?=
 =?Windows-1252?Q?KjF7mU4+Ub/sgO/FK4l1a/GEKvqOJcKlO9QZUNGJuIpqKMTJTCir66tl?=
 =?Windows-1252?Q?J/ZZc2fa9gwrXUAPABgS4t5D1XCmTZ2MOV4VcKU8iupVa+N1Dj+nOYWP?=
 =?Windows-1252?Q?w0XY+gHWLX35Q3eV1M8zFCnDuZ2WE+VkSGb59A10jffiS4H80phvO7qt?=
 =?Windows-1252?Q?/LdUpmytVzdf4w5kie/C4KqRT9cTpdVf37xMwPVb0n0hqhpXkPKv+9GX?=
 =?Windows-1252?Q?7t6u79beBz+dhhOLjekI+t7p20rwqNFis9CpeuuFZQXX2fmkDvoTjX8p?=
 =?Windows-1252?Q?BJ4AuIaIZrI6BB8NzRCnMOyLJUcQdfamzV5xvXmkchZX0yNeaZq+xvmT?=
 =?Windows-1252?Q?tIYPKLSlriev7BQ5ylVmaG96nhW3V9IHL8pB8Sao40z5U5AFiI88sY+Y?=
 =?Windows-1252?Q?ipoI9wXCj6XG4YFQGC0aScRz2iymmqjoWGAURktP+L7d+WHasqb0739T?=
 =?Windows-1252?Q?UlvKn3V5eKoWBWiWFUmu1rxxnr0EnqNr+NAg/35nD+45r98muzHK+vRb?=
 =?Windows-1252?Q?tUBikd/R0MHgm3tnmKgdrKVRyHEl6XINofIJgE+G1bKforxU1bP+y2DF?=
 =?Windows-1252?Q?FiIOeLwzdGxiuw6Yelt5z1/HjZEjCoY559MXBVaQNbrtAIJGVKdabH9P?=
 =?Windows-1252?Q?ZEzdYjafDBbwoyfDDl6x/FfQjCnKV85g+HKMd9zvWc1kmh2ySzd1ZwmA?=
 =?Windows-1252?Q?NFyAJrRsC6sIiYQy3CPQx08S1frBZOcYprld7ZQ6p0LrE1QB7FAShG58?=
 =?Windows-1252?Q?iHZ+ykRCzu6LdL5zIYGlY30ckkJApbCv1wSjNjK1ZfZVdep13kcQiWiA?=
 =?Windows-1252?Q?NcDRVG3uONqANsfFrzFof2BsY7cOfmz96DYwC1eUZhmm1rpZZDRcml7u?=
 =?Windows-1252?Q?LiOi9Pcuxcj0GaWWl7s4nKzwBUt4g7Fwkruoc4KXeAevdkq9QuRuvZLE?=
 =?Windows-1252?Q?aBwa/uNjW+zCnmhm5Bv5Q07J7jwSMVFXSsDXgrc6Y04qtapvZH74FyQ3?=
 =?Windows-1252?Q?EaiY/Ll7DPboypT9YODBfiXpu8er30+GGi3R87niHFKxm9EcITmrKuzc?=
 =?Windows-1252?Q?V8I9gA72kBGDDDW6CL0Pr/0657cZAUXt4DC7kaPp52RPyZNda4VF+Z+Y?=
 =?Windows-1252?Q?L7n8tTo4ESbUVn6uiAd27xSVgqJTEo98bduMQnuVJTpP7f5Ge1CHEj0e?=
 =?Windows-1252?Q?/Qs+WO9QEAc7XOKqtU+ZZyok/gO3wzopueB9wmencGsSNG1PyugziUPj?=
 =?Windows-1252?Q?K3x0gZ7SHX4jtO0ei1LJQENPfKAPDWL/?=
Content-Type: text/plain; charset="Windows-1252"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk
X-Mailing-List: linux-kernel@vger.kernel.org
List-Id: <linux-kernel.vger.kernel.org>
List-Subscribe: <mailto:linux-kernel+subscribe@vger.kernel.org>
List-Unsubscribe: <mailto:linux-kernel+unsubscribe@vger.kernel.org>
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: BL3PR11MB5747.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: b2975d85-886e-4234-bde3-08dc1c9f9682
X-MS-Exchange-CrossTenant-originalarrivaltime: 24 Jan 2024 05:44:52.9704
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: /0R+CaLb63Gdv4WkNd9v8XfpeKa0R7iUPltMaP6wke1msY1DMPF5BOamUS7bpPFyn2r7gyiYCZo2OQ+hK62c5A==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL1PR11MB5954
X-OriginatorOrg: intel.com

Hi Andrew,

> -----Original Message-----
> From: Andrew Jones <ajones@ventanamicro.com>
> Sent: Tuesday, January 16, 2024 11:04 PM
> To: Wang, Xiao W <xiao.w.wang@intel.com>
> Cc: paul.walmsley@sifive.com; palmer@dabbelt.com;
> aou@eecs.berkeley.edu; conor.dooley@microchip.com; heiko@sntech.de; Li,
> Haicheng <haicheng.li@intel.com>; linux-riscv@lists.infradead.org; linux-
> kernel@vger.kernel.org
> Subject: Re: [PATCH] riscv: Optimize crc32 with Zbc extension
>=20
> On Fri, Jan 05, 2024 at 04:08:30PM +0800, Xiao Wang wrote:
> > As suggested by the B-ext spec, the Zbc (carry-less multiplication)
> > instructions can be used to accelerate CRC calculations. Currently, the
> > crc32 is the most widely used crc function inside kernel, so this patch
> > focuses on the optimization of just the crc32 APIs.
> >
> > Compared with the current table-lookup based optimization, Zbc based
> > optimization can also achieve large stride during CRC calculation loop,
> > meantime, it avoids the memory access latency of the table-lookup based
> > implementation and it reduces memory footprint.
> >
> > If Zbc feature is not supported in a runtime environment, then the
> > table-lookup based implementation would serve as fallback via alternati=
ve
> > mechanism. To avoid the performance concern of unalignment access, we
> also
> > use the fallback implementation to handle the head and tail bytes if an=
y,
> > the main body is accelerated by Zbc extension.
> >
> > This patch is tested on QEMU VM with the kernel CRC32 selftest.
>=20
> Ideally we'd also have the results of some benchmarks, or at least a
> dynamic instruction count or something, but I don't suspect that the
> table-lookup would "win" over Zbc. The bigger question is whether we
> want three implementations, because I assume we want Zvbc, particularly
> since [1] says
>=20
> """
> Zvbc is listed as a development option for use in other algorithms,
> and will become mandatory. Scalar Zbc is now listed as an expansion
> option, i.e., it will probably not become mandatory.
> """
>=20
> [1] https://github.com/riscv/riscv-profiles/blob/main/rva23-profile.adoc

I would collect instructions count change and include the info in the commi=
t log.
Regarding to the bigger question, I have some thoughts:

- It looks this question also stands for some other cases like lib/str*, wh=
ich currently
has been accelerated by Zbb-ext, but since the in-kernel RVV support has be=
en enabled,
we may also use RVV to accelerate the lib/str*.
ALTERNATIVE_2 mechanism allows a second code patching on the same location.=
 So
two alternative versions for the same function can be supported.

- At this moment, I can't figure out how Zvbc can be used to better acceler=
ate these
crc32 APIs which take just one data stream as input. I have rough idea for =
a batched
version API which takes multi data stream as input (a parallel implementati=
on of below
Zbc acceleration), but not for these 3 APIs here.
BTW, the vector "clmulr" insn is not listed in the Zvbc spec, but it's usef=
ul in below implementation.
https://github.com/riscv/riscv-crypto/blob/main/doc/vector/riscv-crypto-vec=
tor-zvbc.adoc
Anyway, if we come up with a Zvbc based optimization in future, then ALTERN=
ATIVE_2
would help.

>=20
>=20
> A few nits below.

Thanks for all the above & below comments. Will adopt most of the suggestio=
ns, except two,
please check below.

>=20
> >
> > Signed-off-by: Xiao Wang <xiao.w.wang@intel.com>
> > ---
> >  arch/riscv/Kconfig      |  23 +++++
> >  arch/riscv/lib/Makefile |   1 +
> >  arch/riscv/lib/crc32.c  | 216
> ++++++++++++++++++++++++++++++++++++++++
> >  include/linux/crc32.h   |   3 +
> >  4 files changed, 243 insertions(+)
> >  create mode 100644 arch/riscv/lib/crc32.c
> >
[...]

> > +#if (BITS_PER_LONG =3D=3D 64)
> > +					  size_t len, u32 poly, u64 poly_qt,
> > +#else
> > +					  size_t len, u32 poly, u32 poly_qt,
> > +#endif
>=20
> How about creating a new type for poly_qt, defined as u64 for xlen=3D64
> and u32 for xlen=3D32 to avoid the #ifdef?

Would make it as "unsigned long", as David's comment.

>=20
> > +					  fallback crc_fb)
> > +{
> > +	size_t offset, head_len, tail_len;
> > +	const unsigned long *p_ul;
> > +	unsigned long s;
> > +
> > +	asm_volatile_goto(ALTERNATIVE("j %l[legacy]", "nop", 0,
> > +				      RISCV_ISA_EXT_ZBC, 1)
> > +			  : : : : legacy);
> > +
> > +	/* Handle the unalignment head. */
> > +	offset =3D (unsigned long)p & OFFSET_MASK;
> > +	if (offset) {
> > +		head_len =3D MIN(STEP - offset, len);
> > +		crc =3D crc_fb(crc, p, head_len);
> > +		len -=3D head_len;
> > +		p +=3D head_len;
> > +	}
> > +
> > +	tail_len =3D len & OFFSET_MASK;
> > +	len =3D len >> STEP_ORDER;
> > +	p_ul =3D (unsigned long *)p;
> > +
> > +	for (int i =3D 0; i < len; i++) {
> > +#if (BITS_PER_LONG =3D=3D 64)
> > +		s =3D (unsigned long)crc ^ __cpu_to_le64(*p_ul++);
> > +		/* We don't have a "clmulrh" insn, so use clmul + slli instead.
> > +		 */
>=20
> need opening /* comment wing
>=20
> > +		asm volatile (".option push\n"
> > +			      ".option arch,+zbc\n"
> > +			      "clmul	%0, %1, %2\n"
> > +			      "slli	%0, %0, 1\n"
> > +			      "xor	%0, %0, %1\n"
> > +			      "clmulr	%0, %0, %3\n"
> > +			      "srli	%0, %0, 32\n"
> > +			      ".option pop\n"
> > +			      : "=3D&r" (crc)
> > +			      : "r" (s),
> > +				"r" (poly_qt),
> > +				"r" ((u64)poly << 32)
> > +			      :);
> > +#else
> > +		s =3D crc ^ __cpu_to_le32(*p_ul++);
> > +		/* We don't have a "clmulrh" insn, so use clmul + slli instead.
>=20
> also here
>=20
> > +		 */
> > +		asm volatile (".option push\n"
> > +			      ".option arch,+zbc\n"
> > +			      "clmul	%0, %1, %2\n"
> > +			      "slli	%0, %0, 1\n"
> > +			      "xor	%0, %0, %1\n"
> > +			      "clmulr	%0, %0, %3\n"
> > +			      ".option pop\n"
> > +			      : "=3D&r" (crc)
> > +			      : "r" (s),
> > +				"r" (poly_qt),
> > +				"r" (poly)
> > +			      :);
> > +#endif
>=20
> Instead of the #ifdef here, we could provide function wrappers for the as=
m
> which would be defined above in the first #ifdef ladder.
>=20
> > +	}
> > +
> > +	/* Handle the tail bytes. */
> > +	if (tail_len)
> > +		crc =3D crc_fb(crc, (unsigned char const *)p_ul, tail_len);
> > +	return crc;
> > +
> > +legacy:
> > +	return crc_fb(crc, p, len);
> > +}
> > +
> > +u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
> > +{
> > +	return crc32_le_generic(crc, p, len, CRC32_POLY_LE,
> CRC32_POLY_QT_LE,
> > +				crc32_le_base);
> > +}
> > +
> > +u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)
> > +{
> > +	return crc32_le_generic(crc, p, len, CRC32C_POLY_LE,
> > +				CRC32C_POLY_QT_LE, __crc32c_le_base);
> > +}
> > +
> > +u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
> > +{
> > +	size_t offset, head_len, tail_len;
> > +	const unsigned long *p_ul;
> > +	unsigned long s;
> > +
> > +	asm_volatile_goto(ALTERNATIVE("j %l[legacy]", "nop", 0,
> > +				      RISCV_ISA_EXT_ZBC, 1)
> > +			  : : : : legacy);
> > +
> > +	/* Handle the unalignment head. */
> > +	offset =3D (unsigned long)p & OFFSET_MASK;
> > +	if (offset) {
> > +		head_len =3D MIN(STEP - offset, len);
> > +		crc =3D crc32_be_base(crc, p, head_len);
> > +		len -=3D head_len;
> > +		p +=3D head_len;
> > +	}
> > +
> > +	tail_len =3D len & OFFSET_MASK;
> > +	len =3D len >> STEP_ORDER;
> > +	p_ul =3D (unsigned long *)p;
> > +
> > +	for (int i =3D 0; i < len; i++) {
> > +#if (BITS_PER_LONG =3D=3D 64)
> > +		s =3D (unsigned long)crc << 32;
> > +		s ^=3D __cpu_to_be64(*p_ul++);
> > +#else
> > +		s =3D crc ^ __cpu_to_be32(*p_ul++);
> > +#endif
>=20
> Could write the above without #ifdef with
>=20
>  if (IS_ENABLED(CONFIG_64BIT)) {
>     ...
>  } else {
>     ...
>  }

I got a warning for riscv32 build with this change, gcc v12.2.0
./arch/riscv/lib/crc32.c:191:40: warning: left shift count >=3D width of t=
ype [-Wshift-count-overflow]
It looks compiler takes the always-impossible code branch into consideratio=
n.

BRs,
Xiao