linux-kernel - RE: [PATCH] riscv: lib: Optimize 'strlen' function

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <bd9159806a2e4fd188a78515b58ec51e@AcuMS.aculab.com>
Date: Mon, 18 Dec 2023 09:20:47 +0000
From: David Laight <David.Laight@...LAB.COM>
To: 'Ivan Orlov' <ivan.orlov0322@...il.com>, "paul.walmsley@...ive.com"
	<paul.walmsley@...ive.com>, "palmer@...belt.com" <palmer@...belt.com>,
	"aou@...s.berkeley.edu" <aou@...s.berkeley.edu>
CC: "conor.dooley@...rochip.com" <conor.dooley@...rochip.com>,
	"ajones@...tanamicro.com" <ajones@...tanamicro.com>, "samuel@...lland.org"
	<samuel@...lland.org>, "alexghiti@...osinc.com" <alexghiti@...osinc.com>,
	"linux-riscv@...ts.infradead.org" <linux-riscv@...ts.infradead.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"skhan@...uxfoundation.org" <skhan@...uxfoundation.org>
Subject: RE: [PATCH] riscv: lib: Optimize 'strlen' function

From: Ivan Orlov
> Sent: 18 December 2023 01:42
> 
> On 12/17/23 17:00, David Laight wrote:
> > I'd also guess that pretty much all the calls in-kernel are short.
> > You might try counting as: histogram[ilog2(strlen_result)]++
> > and seeing what it shows for some workload.
> > I bet you (a beer if I see you!) that you won't see many over 1k.
> 
> Hi David,
> 
> Here is the statistics for strlen result:
> 
> [  223.169575] Calls count for 2^0: 6150
> [  223.173293] Calls count for 2^1: 184852
> [  223.177142] Calls count for 2^2: 313896
> [  223.180990] Calls count for 2^3: 185844
> [  223.184881] Calls count for 2^4: 87868
> [  223.188660] Calls count for 2^5: 9916
> [  223.192368] Calls count for 2^6: 1865
> [  223.196062] Calls count for 2^7: 0
> [  223.199483] Calls count for 2^8: 0
> [  223.202952] Calls count for 2^9: 0
> ...
> 
> Looks like I've just lost a beer :)
> 
> Considering this statistics, I'd say implementing the word-oriented
> strlen is an overcomplication - we wouldn't get any performance gain and
> it just doesn't worth it.

And the 32bit version is about half the speed of the 64bit one.

Of course, the fast way to do strlen is add a custom instruction!

> I simplified your code a little bit, it looks like the alignment there
> is unnecessary: QEMU test shows the same performance independently from
> alignment. Tests on the board gave the same result (perhaps because the
> CPU on the board has 2 DDR channels?)

The alignment is there because it can overread the string end
by one byte - and that mustn't cross a page boundary.
So you either have to mark the second load as 'may fault return
zero' or just not do it.

If the data isn't in cache the cache load will dominate.
The DDR channels only affect cache load times.
Get a TLB miss and add a few thousand more clocks!

> 
> 	mv t0, a0
> 1:
> 	lbu t1, 0(a0)
> 	lbu t2, 1(a0)
> 	addi a0, a0, 2
> 	beqz t1, 2f
> 	bnez t2, 1b
> 	addi a0, a0, 1
> 2:
> 	addi a0, a0, -2
> 	sub a0, a0, t0
> 	ret
> 
> If it looks good to you, would you mind if I send the patch with it?
> Could I add you to suggested-by tag?

Yep..

	David

> 
> --
> Kind regards,
> Ivan Orlov

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)