| 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: <fce1adab2b450097edbcea3ec83420257997ec00.camel@ibm.com>
Date: Tue, 2 Sep 2025 19:37:22 +0000
From: Viacheslav Dubeyko <Slava.Dubeyko@....com>
To: "409411716@....tku.edu.tw" <409411716@....tku.edu.tw>,
Xiubo Li
<xiubli@...hat.com>,
"idryomov@...il.com" <idryomov@...il.com>
CC: "ceph-devel@...r.kernel.org" <ceph-devel@...r.kernel.org>,
"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] ceph: optimize ceph_base64_encode() with block
processing
On Sat, 2025-08-30 at 21:28 +0800, Guan-Chun Wu wrote:
> 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.
>
Sounds interesting!
Is ceph_base64_decode() efficient then?
Do we have something in crypto library of Linux kernel? Maybe we can use
something efficient enough from there?
> 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.
>
So, why namely 3-byte blocks? Could you please explain in more details your
motivation and improved technique in commit message? How exactly your technique
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
>
I assume that it is still the commit message. So, I think this portion should be
before Signed-off-by.
> Test is executed in the form of kernel module.
> Test script:
>
Is it finally script or kernel module? As far as I can see, it is not complete
source code. So, I am not sure that everybody will be capable to build and test
this module.
What's about to introduce this as Kunit test or self-test that can be used by
everybody in CephFS kernel client for testing and checking performance? I am
working on initial set of Kunit tests for CephFS kernel client right now.
> 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) {
Frankly speaking, I am not completely happy about hardcoded constants. As a
result, it makes code hard to understand, modify and support. Could you please
introduce named constants instead of hardcoded numbers?
> + 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;
> }
>
Let me test your patch and check that it doesn't introduce regression(s).
Thanks,
Slava.
Powered by blists - more mailing lists