Skip to contentSkip to conversation

bpf: compute hashes in bloom filter similar to hashmap

PATCH Applied Anton Protopopov 2 participants 2 messages Apr 2, 2023 BPF

lore
Share & tools
lore
#0 lore raw

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
index db19784601a7..540331b610a9 100644
@@ -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
#1 lore raw
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.

[...]

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