linux-kernel - Re: [PATCH] fscrypt: optimize fscrypt_base64url

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: <20250831142352.16372-1-409411716@gms.tku.edu.tw>
Date: Sun, 31 Aug 2025 22:23:52 +0800
From: Guan-Chun Wu <409411716@....tku.edu.tw>
To: ebiggers@...nel.org
Cc: 409411716@....tku.edu.tw,
	jaegeuk@...nel.org,
	linux-fscrypt@...r.kernel.org,
	linux-kernel@...r.kernel.org,
	tytso@....edu
Subject: Re: [PATCH] fscrypt: optimize fscrypt_base64url_encode() with block processing

Hi Eric,

>On Sat, Aug 30, 2025 at 09:28:32PM +0800, Guan-Chun Wu wrote:
>> Previously, fscrypt_base64url_encode() processed input one byte at a
>> time, using a bitstream, accumulating bits and emitting characters when
>> 6 bits were available. This was correct but added extra computation.
>> 
>> This patch processes input in 3-byte blocks, mapping directly to 4 output
>> characters. Any remaining 1 or 2 bytes are handled according to Base64 URL
>> rules. This reduces computation and improves performance.
>> 
>> Performance test (5 runs) for fscrypt_base64url_encode():
>> 
>> 64B input:
>> -------------------------------------------------------
>> | Old method | 131 | 108 | 114 | 122 | 123 | avg ~120 ns |
>> -------------------------------------------------------
>> | New method |  84 |  81 |  84 |  82 |  84 | avg ~83 ns  |
>> -------------------------------------------------------
>> 
>> 1KB input:
>> --------------------------------------------------------
>> | Old method | 1152 | 1121 | 1142 | 1147 | 1148 | avg ~1142 ns |
>> --------------------------------------------------------
>> | New method |  767 |  752 |  765 |  771 |  776 | avg ~766 ns  |
>> --------------------------------------------------------
>> 
>> Signed-off-by: Guan-Chun Wu <409411716@....tku.edu.tw>
>
>Thanks!
>
>> Tested on Linux 6.8.0-64-generic x86_64
>> with Intel Core i7-10700 @ 2.90GHz
>> 
>> Test is executed in the form of kernel module.
>> 
>> Test script:
>
>Is there any chance you'd be interested in creating an fscrypt KUnit
>test (in a separate patch) which tests fscrypt_base64url_encode() and
>fscrypt_base64url_decode()?

I’m interested in adding a KUnit test as a separate patch
to cover both fscrypt_base64url_encode() and fscrypt_base64url_decode().

Per Thomas’s suggestion, I’d also like to explore a generic Base64 helper in lib/
(with encoding table and optional padding), with tests in lib/test/
covering both the standard and URL-safe variants.

>
>> diff --git a/fs/crypto/fname.c b/fs/crypto/fname.c
>> index 010f9c0a4c2f..adaa16905498 100644
>> --- a/fs/crypto/fname.c
>> +++ b/fs/crypto/fname.c
>> @@ -204,20 +204,31 @@ static const char base64url_table[65] =
>>  static int fscrypt_base64url_encode(const u8 *src, int srclen, char *dst)
>>  {
>>  	u32 ac = 0;
>> -	int bits = 0;
>> -	int i;
>> +	int i = 0;
>>  	char *cp = dst;
>>  
>> -	for (i = 0; i < srclen; i++) {
>> -		ac = (ac << 8) | src[i];
>> -		bits += 8;
>> -		do {
>> -			bits -= 6;
>> -			*cp++ = base64url_table[(ac >> bits) & 0x3f];
>> -		} while (bits >= 6);
>> +	while (i + 2 < srclen) {
>> +		ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8) | (u32)src[i + 2];
>> +		*cp++ = base64url_table[(ac >> 18) & 0x3f];
>> +		*cp++ = base64url_table[(ac >> 12) & 0x3f];
>> +		*cp++ = base64url_table[(ac >> 6) & 0x3f];
>> +		*cp++ = base64url_table[ac & 0x3f];
>> +		i += 3;
>> +	}
>
>To make it a bit easier to understand, how about updating src and srclen
>as we go along?
>
>	while (srclen >= 3) {
>		ac = ((u32)src[0] << 16) | ((u32)src[1] << 8) | (u32)src[2];
>		*cp++ = base64url_table[ac >> 18];
>		*cp++ = base64url_table[(ac >> 12) & 0x3f];
>		*cp++ = base64url_table[(ac >> 6) & 0x3f];
>		*cp++ = base64url_table[ac & 0x3f];
>		src += 3;
>		srclen -= 3;
>	}
>
>	switch (srclen) {
>	case 2:
>		ac = ((u32)src[0] << 16) | ((u32)src[1] << 8);
>		*cp++ = base64url_table[ac >> 18];
>		*cp++ = base64url_table[(ac >> 12) & 0x3f];
>		*cp++ = base64url_table[(ac >> 6) & 0x3f];
>		break;
>	case 1:
>		ac = ((u32)src[0] << 16);
>		*cp++ = base64url_table[ac >> 18];
>		*cp++ = base64url_table[(ac >> 12) & 0x3f];
>		break;
>	}
>
>'srclen >= 3' is much more readable than 'i + 2 < srclen', IMO.
>
>Also, instead of '(ac >> 18) & 0x3f', we can just use 'ac >> 18', since
>'ac' is a 24-bit value.
>
>- Eric

Thanks, Eric. I'll update the loop condition to use 'srclen >= 3' for
better readability, and drop the redundant '& 0x3f' when shifting the
24-bit accumulator.