bpf: compute hashes in bloom filter similar to hashmap
PATCH 1/1 bpf: compute hashes in bloom filter similar to hashmap
If the value size in a bloom filter is a multiple of 4, then the jhash2() function is used to compute hashes. The length parameter of this function equals to the number of 32-bit words in input. Compute it in the hot path instead of pre-computing it, as this is translated to one extra shift to divide the length by four vs. one extra memory load of a pre-computed length.
--- kernel/bpf/bloom_filter.c | 17 ++--------------- 1 file changed, 2 insertions(+), 15 deletions(-)
kernel/bpf/bloom_filter.c +2 -15
@@ -16,13 +16,6 @@ struct bpf_bloom_filter {struct bpf_map map;u32 bitset_mask;u32 hash_seed; -/* If the size of the values in the bloom filter is u32 aligned, -* then it is more performant to use jhash2 as the underlying hash -* function, else we use jhash. This tracks the number of u32s -* in an u32-aligned value size. If the value size is not u32 aligned, -* this will be 0. -*/ -u32 aligned_u32_count;u32 nr_hash_funcs;unsigned long bitset[]; };
@@ -32,9 +25,8 @@ static u32 hash(struct bpf_bloom_filter *bloom, void *value, {u32 h; -if (bloom->aligned_u32_count) - h =jhash2 (value, bloom->aligned_u32_count, - bloom->hash_seed + index); +if (likely (value_size %4 ==0 )) + h =jhash2 (value, value_size /4 , bloom->hash_seed + index);else h =jhash (value, value_size, bloom->hash_seed + index);
@@ -152,11 +144,6 @@ static struct bpf_map *bloom_map_alloc(union bpf_attr *attr) bloom->nr_hash_funcs = nr_hash_funcs; bloom->bitset_mask = bitset_mask; -/* Check whether the value size is u32-aligned */ -if ((attr->value_size & (sizeof (u32) -1 )) ==0 ) - bloom->aligned_u32_count = - attr->value_size /sizeof (u32); -if (!(attr->map_flags &BPF_F_ZERO_SEED )) bloom->hash_seed =get_random_u32 ();
Signature · 1 line
2.34.1
This patch was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This patch was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 9 lines · On Sun, 2 Apr 2023 11:43:40 +0000 you wrote:
If the value size in a bloom filter is a multiple of 4, then the
jhash2()function is used to compute hashes. The length parameter of this function equals to the number of 32-bit words in input. Compute it in the hot path instead of pre-computing it, as this is translated to one extra shift to divide the length by four vs. one extra memory load of a pre-computed length.Signed-off-by Anton Protopopov <[email protected]>[...]
Here is the summary with links:
- [bpf-next] bpf: compute hashes in bloom filter similar to hashmap
https://git.kernel.org/bpf/bpf-next/c/92b2e810f0d3
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html