| 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
| ||
|
Message-Id: <20250830132832.7911-1-409411716@gms.tku.edu.tw>
Date: Sat, 30 Aug 2025 21:28:32 +0800
From: Guan-Chun Wu <409411716@....tku.edu.tw>
To: ebiggers@...nel.org,
tytso@....edu,
jaegeuk@...nel.org
Cc: linux-fscrypt@...r.kernel.org,
linux-kernel@...r.kernel.org,
Guan-Chun Wu <409411716@....tku.edu.tw>
Subject: [PATCH] fscrypt: optimize fscrypt_base64url_encode() with block processing
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>
---
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:
static int encode_v1(const u8 *src, int srclen, char *dst)
{
u32 ac = 0;
int bits = 0;
int i;
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);
}
if (bits)
*cp++ = base64url_table[(ac << (6 - bits)) & 0x3f];
return cp - dst;
}
static int encode_v2(const u8 *src, int srclen, char *dst)
{
u32 ac = 0;
int i = 0;
char *cp = dst;
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;
}
switch (srclen - i) {
case 2:
ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8);
*cp++ = base64url_table[(ac >> 18) & 0x3f];
*cp++ = base64url_table[(ac >> 12) & 0x3f];
*cp++ = base64url_table[(ac >> 6) & 0x3f];
break;
case 1:
ac = ((u32)src[i] << 16);
*cp++ = base64url_table[(ac >> 18) & 0x3f];
*cp++ = base64url_table[(ac >> 12) & 0x3f];
break;
}
return cp - dst;
}
static void run_test(const char *label, const u8 *data, int len)
{
char *dst1, *dst2;
int n1, n2;
u64 start, end;
dst1 = kmalloc(len * 2, GFP_KERNEL);
dst2 = kmalloc(len * 2, GFP_KERNEL);
if (!dst1 || !dst2) {
pr_err("%s: Failed to allocate dst buffers\n", label);
goto out;
}
pr_info("[%s] input size = %d bytes\n", label, len);
start = ktime_get_ns();
n1 = encode_v1(data, len, dst1);
end = ktime_get_ns();
pr_info("[%s] encode_v1 time: %lld ns\n", label, end - start);
start = ktime_get_ns();
n2 = encode_v2(data, len, dst2);
end = ktime_get_ns();
pr_info("[%s] encode_v2 time: %lld ns\n", label, end - start);
if (n1 != n2 || memcmp(dst1, dst2, n1) != 0)
pr_err("[%s] Mismatch detected between encode_v1 and encode_v2!\n", label);
else
pr_info("[%s] Outputs are identical.\n", label);
out:
kfree(dst1);
kfree(dst2);
}
static int __init base64_perf_init(void)
{
u8 *data1k;
pr_info("Module init - running multi-size tests\n");
{
static u8 test64[64];
get_random_bytes(test64, sizeof(test64));
run_test("64B", test64, sizeof(test64));
}
data1k = kmalloc(1024, GFP_KERNEL);
if (data1k) {
get_random_bytes(data1k, 1024);
run_test("1KB", data1k, 1024);
kfree(data1k);
} else {
pr_err("Failed to allocate 1KB test buffer\n");
}
return 0;
}
---
fs/crypto/fname.c | 33 ++++++++++++++++++++++-----------
1 file changed, 22 insertions(+), 11 deletions(-)
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;
+ }
+
+ switch (srclen - i) {
+ case 2:
+ ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8);
+ *cp++ = base64url_table[(ac >> 18) & 0x3f];
+ *cp++ = base64url_table[(ac >> 12) & 0x3f];
+ *cp++ = base64url_table[(ac >> 6) & 0x3f];
+ break;
+ case 1:
+ ac = ((u32)src[i] << 16);
+ *cp++ = base64url_table[(ac >> 18) & 0x3f];
+ *cp++ = base64url_table[(ac >> 12) & 0x3f];
+ break;
}
- if (bits)
- *cp++ = base64url_table[(ac << (6 - bits)) & 0x3f];
return cp - dst;
}
--
2.34.1
Powered by blists - more mailing lists