linux-kernel - [PATCH] ceph: optimize ceph_base64

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>] [day] [month] [year] [list]
Message-Id: <20250830132822.7827-1-409411716@gms.tku.edu.tw>
Date: Sat, 30 Aug 2025 21:28:22 +0800
From: Guan-Chun Wu <409411716@....tku.edu.tw>
To: xiubli@...hat.com,
	idryomov@...il.com
Cc: ceph-devel@...r.kernel.org,
	linux-kernel@...r.kernel.org,
	Guan-Chun Wu <409411716@....tku.edu.tw>
Subject: [PATCH] ceph: optimize ceph_base64_encode() with block processing

Previously, ceph_base64_encode() used a bitstream approach, handling one
input byte at a time and performing extra bit operations. While correct,
this method was suboptimal.

This patch processes input in 3-byte blocks, mapping directly to 4 output
characters. Remaining 1 or 2 bytes are handled according to standard Base64
rules. This reduces computation and improves performance.

Performance test (5 runs) for ceph_base64_encode():

64B input:
-------------------------------------------------------
| Old method | 123 | 115 | 137 | 119 | 109 | avg ~121 ns |
-------------------------------------------------------
| New method |  84 |  83 |  86 |  85 |  84 | avg ~84 ns  |
-------------------------------------------------------

1KB input:
--------------------------------------------------------
| Old method | 1217 | 1150 | 1146 | 1149 | 1149 | avg ~1162 ns |
--------------------------------------------------------
| New method |  776 |  772 |  772 |  774 |  770 | avg ~773 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++ = base64_table[(ac >> bits) & 0x3f];
		} while (bits >= 6);
	}
	if (bits)
		*cp++ = base64_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++ = base64_table[(ac >> 18) & 0x3f];
		*cp++ = base64_table[(ac >> 12) & 0x3f];
		*cp++ = base64_table[(ac >> 6) & 0x3f];
		*cp++ = base64_table[ac & 0x3f];
		i += 3;
	}

	switch (srclen - i) {
	case 2:
		ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8);
		*cp++ = base64_table[(ac >> 18) & 0x3f];
		*cp++ = base64_table[(ac >> 12) & 0x3f];
		*cp++ = base64_table[(ac >> 6) & 0x3f];
		break;
	case 1:
		ac = ((u32)src[i] << 16);
		*cp++ = base64_table[(ac >> 18) & 0x3f];
		*cp++ = base64_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);
}
---
 fs/ceph/crypto.c | 33 ++++++++++++++++++++++-----------
 1 file changed, 22 insertions(+), 11 deletions(-)

diff --git a/fs/ceph/crypto.c b/fs/ceph/crypto.c
index 3b3c4d8d401e..a35570fd8ff5 100644
--- a/fs/ceph/crypto.c
+++ b/fs/ceph/crypto.c
@@ -27,20 +27,31 @@ static const char base64_table[65] =
 int ceph_base64_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++ = base64_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++ = base64_table[(ac >> 18) & 0x3f];
+		*cp++ = base64_table[(ac >> 12) & 0x3f];
+		*cp++ = base64_table[(ac >> 6) & 0x3f];
+		*cp++ = base64_table[ac & 0x3f];
+		i += 3;
+	}
+
+	switch (srclen - i) {
+	case 2:
+		ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8);
+		*cp++ = base64_table[(ac >> 18) & 0x3f];
+		*cp++ = base64_table[(ac >> 12) & 0x3f];
+		*cp++ = base64_table[(ac >> 6) & 0x3f];
+		break;
+	case 1:
+		ac = ((u32)src[i] << 16);
+		*cp++ = base64_table[(ac >> 18) & 0x3f];
+		*cp++ = base64_table[(ac >> 12) & 0x3f];
+		break;
 	}
-	if (bits)
-		*cp++ = base64_table[(ac << (6 - bits)) & 0x3f];
 	return cp - dst;
 }
 
-- 
2.34.1