Received-SPF: pass (google.com: domain of linux-kernel+bounces-102717-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249;
From: "Wang, Xiao W" <xiao.w.wang@intel.com>
To: Charlie Jenkins <charlie@rivosinc.com>
CC: "paul.walmsley@sifive.com" <paul.walmsley@sifive.com>,
	"palmer@dabbelt.com" <palmer@dabbelt.com>, "aou@eecs.berkeley.edu"
	<aou@eecs.berkeley.edu>, "ajones@ventanamicro.com" <ajones@ventanamicro.com>,
	"conor.dooley@microchip.com" <conor.dooley@microchip.com>, "heiko@sntech.de"
	<heiko@sntech.de>, "david.laight@aculab.com" <david.laight@aculab.com>, "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 v3] riscv: Optimize crc32 with Zbc extension
Thread-Topic: [PATCH v3] riscv: Optimize crc32 with Zbc extension
Thread-Index: AQHadPUZgJSwa1OZEUm5ETdeu7ZVobE2Rs0AgAA0pQA=
Date: Thu, 14 Mar 2024 02:32:57 +0000
Message-ID: <DM8PR11MB57514B86A2C1AA40973AF705B8292@DM8PR11MB5751.namprd11.prod.outlook.com>
References: <20240313032139.3763427-1-xiao.w.wang@intel.com>
 <ZfIs5ND0S08N2zLd@ghost>
In-Reply-To: <ZfIs5ND0S08N2zLd@ghost>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: =?Windows-1252?Q?68L1vz0S6IkMZuwoCBS4n7R4SLbjF4mlIJ2aXc8iCzbboSBJI41fAy20?=
 =?Windows-1252?Q?srB6i0/7wWu0jaGRlsWIzacCZ3Pe621Mez6S7xzvT5u0jtK0rqtfWfa0?=
 =?Windows-1252?Q?i8kp9TbYeghhU9UslfJ2BVYLYLNZyjf9vfhx9M6S51iJzAqGaLcqtQPN?=
 =?Windows-1252?Q?95boH4TXF6Gjgv55uFGaxi7CF5C9EHq1L7IzngB+PAEd4JMjiNHBSwn3?=
 =?Windows-1252?Q?AWKUwFpWWtMlqGBAU6rHOOPwT/PrIS495PP1bo8VyrUSiM0u1RILf85f?=
 =?Windows-1252?Q?yHd+468R2OFbiyLFq2lV0WmHkZMhoxF72ZCKyd8akWC6ADJSOZMRHRPp?=
 =?Windows-1252?Q?fMc5zOc9BD/ZhTZcSRAgPobglaAtMQ2PlPiSwEuhgFOg4YcsEAguJyHR?=
 =?Windows-1252?Q?8BXdPX/DnuDSPAFl9kEMXpIVe78nnrJuxE8IR0J6jKTX8r0e4qowk5F3?=
 =?Windows-1252?Q?/LFmvgFiKtOL1BoN1w2rTj6YhBJRzOudgKTJ2REA9Pna6gxLTYplk8CD?=
 =?Windows-1252?Q?gO3NiKv82xLY1jufbsL6aRwKM7V9+f8jWiTTe6FAW3nkS6zh9u8y0j/R?=
 =?Windows-1252?Q?Hm3jY53YnNVNayLwcKdeQ9N5qhVW3ot9DnNbspqQqp8bWpfL6ShIqasi?=
 =?Windows-1252?Q?YxVNzUlTLOiX66KSWy4/ZcOqNNUQwZANiFpWdsccDMG4jR/VEab+hlND?=
 =?Windows-1252?Q?8OZqR4/XsTe2N7wW/sByww3s+tkFc10i0Jz+wWsXjEcZVr6PAjPRxpGu?=
 =?Windows-1252?Q?jh5Kti9/FC2uRAtzJSuUjjYdytuCFKeEerhazmgnxVt1j2DpdncwrenN?=
 =?Windows-1252?Q?neYDspu4RPjV8SugZFdMpRqN7bTpqbboa9O1CaJYfyCjO2/TCvtLBZl9?=
 =?Windows-1252?Q?fHMxYE9ThHgV4DkBuyTWxFp2Kno115141u1aE2gpXz+yoN/O03gymEZO?=
 =?Windows-1252?Q?ljYPSFXux0fBbm7E91wSR9y4lviJJkwXz3iYDmEtw3Iw/lKnHcKLTc2s?=
 =?Windows-1252?Q?wBs1OJ95Qm6CvWrr8ndY21F56cTFEPq44wSYBZLG63iptGCUrEY1Gp7p?=
 =?Windows-1252?Q?coa4YLaN+ZKS1Y1EqqalcWaH0enGXvpJ85qE79Yk1fcBE2eKrcdq6aX5?=
 =?Windows-1252?Q?IJwWW9mtmjsPdY+ex9cqaw6jkuBYI1mo1vvZr15Gl53qs6svkc5Umdzd?=
 =?Windows-1252?Q?3IMD8qCohWHfSTxok+ANLD57xB5RBsguEmZvTzWYXc9yKxywsjRZNwNL?=
 =?Windows-1252?Q?rZiarS0RZSXbOuZ5Et86KLgRLflEKPzArpmijgzHoW90TCKqMs5N4z2h?=
 =?Windows-1252?Q?VCKFyUjeYKZocWkkCHqtjGgJ7XRSASOWzALYXJPUk/gMMz3MYCqivTk5?=
 =?Windows-1252?Q?KeXZxAwLgnIcF08hnM2ED9HVXNVE7pqpfFlYRHjtoQ6QcFWlXpXIBtrs?=
 =?Windows-1252?Q?VVLF5F/ahzG1VbAAoWORDuFBglpdcWKA0G7EuSGgRnyNKJCTiq4LCbib?=
 =?Windows-1252?Q?vQIUpvp97ihFT47qLYvEjIIgWhzsA9S8HsYvAV75OT0X5zw4rlV+MdSC?=
 =?Windows-1252?Q?CV3Fjo68ThusKv6868UWyuFJTee5DCZ7kCTu6LYtn0ezVpmGqgXBVx3Q?=
 =?Windows-1252?Q?6pesFEpGWL0wWmAQrqy0UUiDVHhesOcBgLfKAuSZcUQd+hm4BaOhRcz8?=
 =?Windows-1252?Q?UokgVa5XjamcCgHln8pJdiIO9HX9Scyl?=
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: DM8PR11MB5751.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 84e76c87-5c2f-41e0-0758-08dc43cf0f2b
X-MS-Exchange-CrossTenant-originalarrivaltime: 14 Mar 2024 02:32:57.1261
 (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: i68r9x1N9QR3Qrx6HqmOkUBSdIO+npDkHxrvG6CANe+J3yw6cZCSNC+ZhHaJy9ExDJTfmmAEBfc+y/Ygih3XDA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: LV8PR11MB8461
X-OriginatorOrg: intel.com


> -----Original Message-----
> From: Charlie Jenkins <charlie@rivosinc.com>
> Sent: Thursday, March 14, 2024 6:47 AM
> To: Wang, Xiao W <xiao.w.wang@intel.com>
> Cc: paul.walmsley@sifive.com; palmer@dabbelt.com;
> aou@eecs.berkeley.edu; ajones@ventanamicro.com;
> conor.dooley@microchip.com; heiko@sntech.de; david.laight@aculab.com;
> Li, Haicheng <haicheng.li@intel.com>; linux-riscv@lists.infradead.org; li=
nux-
> kernel@vger.kernel.org
> Subject: Re: [PATCH v3] riscv: Optimize crc32 with Zbc extension
>=20
> On Wed, Mar 13, 2024 at 11:21:39AM +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.
> >
> > By inspecting the vmlinux built by gcc v12.2.0 with default optimizatio=
n
> > level (-O2), we can see below instruction count change for each 8-byte
> > stride in the CRC32 loop:
> >
> > rv64: crc32_be (54->31), crc32_le (54->13), __crc32c_le (54->13)
> > rv32: crc32_be (50->32), crc32_le (50->16), __crc32c_le (50->16)
>=20
> Even though this loop is optimized, there are a lot of other
> instructions being executed else where for these tests. When running the
> test-case in QEMU with ZBC enabled, I get these results:
>=20
> [    0.353444] crc32: CRC_LE_BITS =3D 64, CRC_BE BITS =3D 64
> [    0.353470] crc32: self tests passed, processed 225944 bytes in 204470=
0
> nsec
> [    0.354098] crc32c: CRC_LE_BITS =3D 64
> [    0.354114] crc32c: self tests passed, processed 112972 bytes in 28900=
0
> nsec
> [    0.387204] crc32_combine: 8373 self tests passed
> [    0.419881] crc32c_combine: 8373 self tests passed
>=20
> Then when running with ZBC disabled I get:
>=20
> [    0.351331] crc32: CRC_LE_BITS =3D 64, CRC_BE BITS =3D 64
> [    0.351359] crc32: self tests passed, processed 225944 bytes in 567500
> nsec
> [    0.352071] crc32c: CRC_LE_BITS =3D 64
> [    0.352090] crc32c: self tests passed, processed 112972 bytes in 28990=
0
> nsec
> [    0.385395] crc32_combine: 8373 self tests passed
> [    0.418180] crc32c_combine: 8373 self tests passed
>=20
> This is QEMU so it's not a perfect representation of hardware, but being
> 4 times slower with ZBC seems suspicious. I ran these tests numerous
> times and got similar results. Do you know why these tests would perform
> 4 times better without ZBC?

ZBC instruction' functionality is relatively more complex, so QEMU tcg uses=
 the
helper function mechanism to emulate these ZBC instructions. Helper functio=
n
gets called for each ZBC instruction within tcg JIT code, which is ineffici=
ent. I see
similar issue about the Vector extension, the optimized RVV implementation =
runs
actually much slower than the scalar implementation on QEMU tcg.

>=20
> >
> > The compile target CPU is little endian, extra effort is needed for byt=
e
> > swapping for the crc32_be API, thus, the instruction count change is no=
t
> > as significant as that in the *_le cases.
> >
> > This patch is tested on QEMU VM with the kernel CRC32 selftest for both
> > rv64 and rv32.
> >
> > Signed-off-by: Xiao Wang <xiao.w.wang@intel.com>
> > ---
> > v3:
> > - Use Zbc to handle also the data head and tail bytes, instead of calli=
ng
> >   fallback function.
> > - Misc changes due to the new design.
> >
> > v2:
> > - Fix sparse warnings about type casting. (lkp)
> > - Add info about instruction count change in commit log. (Andrew)
> > - Use the min() helper from linux/minmax.h. (Andrew)
> > - Use "#if __riscv_xlen =3D=3D 64" macro check to differentiate rv64 an=
d rv32.
> (Andrew)
> > - Line up several macro values by tab. (Andrew)
> > - Make poly_qt as "unsigned long" to unify the code for rv64 and rv32.
> (David)
> > - Fix the style of comment wing. (Andrew)
> > - Add function wrappers for the asm code for the *_le cases. (Andrew)
> > ---
> >  arch/riscv/Kconfig      |  23 ++++
> >  arch/riscv/lib/Makefile |   1 +
> >  arch/riscv/lib/crc32.c  | 294

[...]
> > +static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const=
 *p,
> > +					  size_t len, u32 poly,
> > +					  unsigned long poly_qt,
> > +					  fallback crc_fb)
> > +{
> > +	size_t offset, head_len, tail_len;
> > +	unsigned long const *p_ul;
> > +	unsigned long s;
> > +
> > +	asm_volatile_goto(ALTERNATIVE("j %l[legacy]", "nop", 0,
>=20
> This needs to be changed to be asm goto:
>=20
> 4356e9f841f7f ("work around gcc bugs with 'asm goto' with outputs")
>=20

Thanks for the pointer. Will change it.

> > +				      RISCV_ISA_EXT_ZBC, 1)
> > +			  : : : : legacy);
> > +
> > +	/* Handle the unaligned head. */
> > +	offset =3D (unsigned long)p & OFFSET_MASK;
> > +	if (offset && len) {
>=20
> If len is 0 nothing in the function seems like it will modify crc. Is the=
re
> a reason to not break out immediately if len is 0?
>=20

Yeah, if len is 0, then crc won't be modified.
Normally in scenarios like hash value calculation and packets CRC check,
the "len" can hardly be zero. And software usually avoids unaligned buf
addr, which means the "offset" here mostly is false.

So if we add a "len =3D=3D 0" check at the beginning of this function, it w=
ill
introduce a branch overhead for the most cases.

> > +		head_len =3D min(STEP - offset, len);
> > +		crc =3D crc32_le_unaligned(crc, p, head_len, poly, poly_qt);
> > +		p +=3D head_len;
> > +		len -=3D head_len;
> > +	}
> > +
> > +	tail_len =3D len & OFFSET_MASK;
> > +	len =3D len >> STEP_ORDER;
> > +	p_ul =3D (unsigned long const *)p;
> > +
> > +	for (int i =3D 0; i < len; i++) {
> > +		s =3D crc32_le_prep(crc, p_ul);
> > +		crc =3D crc32_le_zbc(s, poly, poly_qt);
> > +		p_ul++;
> > +	}
> > +
> > +	/* Handle the tail bytes. */
> > +	p =3D (unsigned char const *)p_ul;
> > +	if (tail_len)
> > +		crc =3D crc32_le_unaligned(crc, p, tail_len, poly, poly_qt);
> > +
> > +	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);
> > +}
> > +
> > +static inline u32 crc32_be_unaligned(u32 crc, unsigned char const *p,
> > +				     size_t len)
> > +{
> > +	size_t bits =3D len * 8;
> > +	unsigned long s =3D 0;
> > +	u32 crc_low =3D 0;
> > +
> > +	s =3D 0;
> > +	for (int i =3D 0; i < len; i++)
> > +		s =3D *p++ | (s << 8);
> > +
> > +	if (__riscv_xlen =3D=3D 32 || len < sizeof(u32)) {
> > +		s ^=3D crc >> (32 - bits);
> > +		crc_low =3D crc << bits;
> > +	} else {
> > +		s ^=3D (unsigned long)crc << (bits - 32);
> > +	}
> > +
> > +	crc =3D crc32_be_zbc(s);
> > +	crc ^=3D crc_low;
> > +
> > +	return crc;
> > +}
> > +
> > +u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
> > +{
> > +	size_t offset, head_len, tail_len;
> > +	unsigned long const *p_ul;
> > +	unsigned long s;
> > +
> > +	asm_volatile_goto(ALTERNATIVE("j %l[legacy]", "nop", 0,
>=20
> Same here
>=20

Will change it.

Thanks for the comments.
-Xiao