netdev - Re: [PATCH bpf-next 03/11] libbpf: unify and speed up BTF string deduplication

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 for Android: free password hash cracker in your pocket

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

Date:   Mon, 2 Nov 2020 20:59:36 -0800
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Andrii Nakryiko <andrii@...nel.org>
Cc:     bpf@...r.kernel.org, netdev@...r.kernel.org, ast@...com,
        daniel@...earbox.net, kernel-team@...com,
        Andrii Nakryiko <andriin@...com>
Subject: Re: [PATCH bpf-next 03/11] libbpf: unify and speed up BTF string
 deduplication

On Wed, Oct 28, 2020 at 05:58:54PM -0700, Andrii Nakryiko wrote:
> From: Andrii Nakryiko <andriin@...com>
> 
> Revamp BTF dedup's string deduplication to match the approach of writable BTF
> string management. This allows to transfer deduplicated strings index back to
> BTF object after deduplication without expensive extra memory copying and hash
> map re-construction. It also simplifies the code and speeds it up, because
> hashmap-based string deduplication is faster than sort + unique approach.
> 
> Signed-off-by: Andrii Nakryiko <andriin@...com>
> ---
>  tools/lib/bpf/btf.c | 265 +++++++++++++++++---------------------------
>  1 file changed, 99 insertions(+), 166 deletions(-)
> 
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 89fecfe5cb2b..db9331fea672 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -90,6 +90,14 @@ struct btf {
>  	struct hashmap *strs_hash;
>  	/* whether strings are already deduplicated */
>  	bool strs_deduped;
> +	/* extra indirection layer to make strings hashmap work with stable
> +	 * string offsets and ability to transparently choose between
> +	 * btf->strs_data or btf_dedup->strs_data as a source of strings.
> +	 * This is used for BTF strings dedup to transfer deduplicated strings
> +	 * data back to struct btf without re-building strings index.
> +	 */
> +	void **strs_data_ptr;

I thought one of the ideas of dedup algo was that strings were deduped first,
so there is no need to rebuild them.
Then split BTF cannot touch base BTF strings and they're immutable.
But the commit log is talking about transfer of strings and
hash map re-construction? Why split BTF would reconstruct anything?
It either finds a string in a base BTF or adds to its own strings section.
Is it all due to switch to hash? The speedup motivation is clear, but then
it sounds like that the speedup is causing all these issues.
The strings could have stayed as-is. Just a bit slower ?