[PATCH bpf-next] bpf: Specialize inlined lookups for more htab types

[PATCH bpf-next] bpf: Specialize inlined lookups for more htab types

[Mykyta Yatsenko]

From: Mykyta Yatsenko <yatsenko@meta.com>

Commit 63b13537e6b2 ("bpf: Speed up htab lookups for u32/u64 keys")
specializes the inlined lookup only for BPF_MAP_TYPE_HASH. LRU_HASH,
PERCPU_HASH and HASH_OF_MAPS still call the generic lookup.

Select the lookup function in all htab map_gen_lookup() callbacks by
key size and by has_hash. has_hash does not change after map creation,
so each variant uses a constant elem_has_hash. This also removes the
load and the branch on htab->has_hash for other key sizes.
LRU_PERCPU_HASH has no inlined lookup and does not change.

Calculate has_hash from map_type and key_size, not from struct
bpf_htab. For map-in-map, map_gen_lookup() gets the inner map
template, which is only a struct bpf_map. bpf_map_meta_equal() makes
these fields the same for all inner maps.

Measure with ten runs of:

  ./bench -q -a -w3 -d10 bpf-hashmap-lookup --key_size KEY_SIZE \
      --max_entries MAX_ENTRIES --nr_entries NR_ENTRIES \
      --nr_loops NR_LOOPS --map_flags 0x40

in a vng guest with two vCPUs, 4 GiB of RAM and KASAN off. For LRU and
PERCPU, the benchmark was changed locally to create an LRU_HASH or
PERCPU_HASH map. The workloads are:

               max_entries   nr_entries    nr_loops
  small                512          256   8,388,608
  medium            10,000        5,000   8,000,000
  large            100,000       50,000   8,000,000

Change of median lookup throughput:

                            key size (bytes)
                         1        4        8       10
  HASH     small     +2.4%    +1.7%    -0.3%    +2.7%
           medium    -0.2%    +1.8%    +0.1%    +5.1%
           large     +0.3%    +1.5%    +2.1%    +8.4%
  LRU      small     -0.8%  +116.6%   +42.8%    +3.3%
           medium    +1.2%   +62.1%   +37.6%    +5.1%
           large     +2.6%   +48.7%   +31.4%    +5.9%
  PERCPU   small     +0.1%  +195.3%   +82.0%    +4.0%
           medium    +1.6%  +133.1%   +73.6%    +4.3%
           large     +0.7%   +71.0%   +73.3%    +8.8%

HASH with u32 and u64 keys runs the same code as before, so these
changes are noise. HASH_OF_MAPS uses the same lookup functions as HASH.

Signed-off-by: Mykyta Yatsenko <yatsenko@meta.com>
---
The LRU_HASH and PERCPU_HASH numbers come from a local change to the
hashmap lookup benchmark. That change is not part of this patch.
---
 kernel/bpf/hashtab.c | 107 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 66 insertions(+), 41 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 6e2115477cb9..a2d0bfd4c3ec 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -196,10 +196,15 @@ static inline void htab_unlock_bucket(struct bucket *b, unsigned long flags)
 
 static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node);
 
+static bool htab_map_is_lru(const struct bpf_map *map)
+{
+	return map->map_type == BPF_MAP_TYPE_LRU_HASH ||
+		map->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;
+}
+
 static bool htab_is_lru(const struct bpf_htab *htab)
 {
-	return htab->map.map_type == BPF_MAP_TYPE_LRU_HASH ||
-		htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;
+	return htab_map_is_lru(&htab->map);
 }
 
 static bool htab_is_percpu(const struct bpf_htab *htab)
@@ -224,6 +229,12 @@ static __always_inline bool htab_key_size_needs_hash(u32 key_size)
 	return key_size > sizeof(unsigned long);
 }
 
+/* map can be the inner map template, which is not a struct bpf_htab */
+static bool htab_map_needs_hash(const struct bpf_map *map)
+{
+	return htab_map_is_lru(map) || htab_key_size_needs_hash(map->key_size);
+}
+
 /*
  * When hash is omitted, key reads and writes must be atomic to support lockless
  * RCU readers. Zero-extend keys to the word size to support all sub-word key
@@ -676,8 +687,7 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
 	bpf_map_init_from_attr(&htab->map, attr);
 
 	/* Avoid hash memory use and comparisons where unnecessary. */
-	htab->has_hash = htab_is_lru(htab) ||
-			 htab_key_size_needs_hash(htab->map.key_size);
+	htab->has_hash = htab_map_needs_hash(&htab->map);
 
 	if (percpu_lru) {
 		/* ensure each CPU's lru list has >=1 elements.
@@ -892,13 +902,6 @@ static __always_inline void *__htab_lookup(struct bpf_map *map, void *key,
 	return l;
 }
 
-/*
- * Called from syscall or from eBPF program directly, so
- * arguments have to match bpf_map_lookup_elem() exactly.
- * The return value is adjusted by BPF instructions
- * in htab_map_gen_lookup(). u32/u64 specializations
- * allow utilizing compile-time key_size for optimization.
- */
 static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
 {
 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
@@ -907,19 +910,58 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
 }
 
 /*
- * Specialized lookups for htab_map_gen_lookup(). These are only used for
- * BPF_MAP_TYPE_HASH (never LRU), so elem_has_hash depends only on key size.
+ * Called from eBPF program directly, so arguments have to match
+ * bpf_map_lookup_elem() exactly. The return value is adjusted by BPF
+ * instructions in the htab *_map_gen_lookup() callbacks. Constant key_size
+ * and elem_has_hash let the compiler specialize the hash and the compare.
  */
-static void *__htab_map_lookup_elem_u32(struct bpf_map *map, void *key)
+static void *__htab_map_lookup_elem_nohash(struct bpf_map *map, void *key)
+{
+	return __htab_lookup(map, key, map->key_size, false);
+}
+
+static void *__htab_map_lookup_elem_hash(struct bpf_map *map, void *key)
+{
+	return __htab_lookup(map, key, map->key_size, true);
+}
+
+static void *__htab_map_lookup_elem_u32_nohash(struct bpf_map *map, void *key)
+{
+	return __htab_lookup(map, key, sizeof(u32), false);
+}
+
+static void *__htab_map_lookup_elem_u32_hash(struct bpf_map *map, void *key)
+{
+	return __htab_lookup(map, key, sizeof(u32), true);
+}
+
+static void *__htab_map_lookup_elem_u64_nohash(struct bpf_map *map, void *key)
 {
-	return __htab_lookup(map, key, sizeof(u32),
-			     htab_key_size_needs_hash(sizeof(u32)));
+	return __htab_lookup(map, key, sizeof(u64), false);
 }
 
-static void *__htab_map_lookup_elem_u64(struct bpf_map *map, void *key)
+static void *__htab_map_lookup_elem_u64_hash(struct bpf_map *map, void *key)
 {
-	return __htab_lookup(map, key, sizeof(u64),
-			     htab_key_size_needs_hash(sizeof(u64)));
+	return __htab_lookup(map, key, sizeof(u64), true);
+}
+
+typedef void *(*htab_lookup_fn)(struct bpf_map *map, void *key);
+
+static htab_lookup_fn htab_gen_lookup_fn(struct bpf_map *map)
+{
+	bool hash = htab_map_needs_hash(map);
+
+	switch (map->key_size) {
+	case sizeof(u32):
+		return hash ? __htab_map_lookup_elem_u32_hash :
+			      __htab_map_lookup_elem_u32_nohash;
+	case sizeof(u64):
+		return hash ? __htab_map_lookup_elem_u64_hash :
+			      __htab_map_lookup_elem_u64_nohash;
+	default:
+		return hash ? __htab_map_lookup_elem_hash :
+			      __htab_map_lookup_elem_nohash;
+	}
 }
 
 static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
@@ -941,25 +983,14 @@ static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
  *         __htab_map_lookup_elem
  * do:
  * bpf_prog
- *   __htab_map_lookup_elem
+ *   __htab_map_lookup_elem_*()
  */
 static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
 {
 	struct bpf_insn *insn = insn_buf;
 	const int ret = BPF_REG_0;
 
-	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
-		     (void *(*)(struct bpf_map *map, void *key))NULL));
-	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem_u32,
-				  (void *(*)(struct bpf_map *map, void *key))NULL));
-	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem_u64,
-				  (void *(*)(struct bpf_map *map, void *key))NULL));
-	if (map->key_size == sizeof(u32))
-		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u32);
-	else if (map->key_size == sizeof(u64))
-		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem_u64);
-	else
-		*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
+	*insn++ = BPF_EMIT_CALL(htab_gen_lookup_fn(map));
 	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
 	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
 				offsetof(struct htab_elem, key) +
@@ -1001,9 +1032,7 @@ static int htab_lru_map_gen_lookup(struct bpf_map *map,
 			    (int)offsetof(struct bpf_lru_node, ref) -
 			    (int)offsetof(struct htab_elem_lru, elem);
 
-	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
-		     (void *(*)(struct bpf_map *map, void *key))NULL));
-	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
+	*insn++ = BPF_EMIT_CALL(htab_gen_lookup_fn(map));
 	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 4);
 	*insn++ = BPF_LDX_MEM(BPF_B, ref_reg, ret, ref_off);
 	*insn++ = BPF_JMP_IMM(BPF_JNE, ref_reg, 0, 1);
@@ -2642,9 +2671,7 @@ static int htab_percpu_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn
 	if (!bpf_jit_supports_percpu_insn())
 		return -EOPNOTSUPP;
 
-	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
-		     (void *(*)(struct bpf_map *map, void *key))NULL));
-	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
+	*insn++ = BPF_EMIT_CALL(htab_gen_lookup_fn(map));
 	*insn++ = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 3);
 	*insn++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_0,
 				offsetof(struct htab_elem, key) + roundup(map->key_size, 8));
@@ -2931,9 +2958,7 @@ static int htab_of_map_gen_lookup(struct bpf_map *map,
 	struct bpf_insn *insn = insn_buf;
 	const int ret = BPF_REG_0;
 
-	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
-		     (void *(*)(struct bpf_map *map, void *key))NULL));
-	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
+	*insn++ = BPF_EMIT_CALL(htab_gen_lookup_fn(map));
 	*insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 2);
 	*insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
 				offsetof(struct htab_elem, key) +

---
base-commit: 5b3d3e7e676630400bfb8a1470a7019803dbd997
change-id: 20261104-b4-hashtab-fast-hashfn-all-types-377eb716e62e

Best regards,
--  
Mykyta Yatsenko <yatsenko@meta.com>

Re: [PATCH bpf-next] bpf: Specialize inlined lookups for more htab types

[patchwork-bot+netdevbpf]

Hello:

This patch was applied to bpf/bpf-next.git (master)
by Andrii Nakryiko <andrii@kernel.org>:

On Thu, 05 Nov 2026 08:56:04 -0800 you wrote:
> From: Mykyta Yatsenko <yatsenko@meta.com>
> 
> Commit 63b13537e6b2 ("bpf: Speed up htab lookups for u32/u64 keys")
> specializes the inlined lookup only for BPF_MAP_TYPE_HASH. LRU_HASH,
> PERCPU_HASH and HASH_OF_MAPS still call the generic lookup.
> 
> Select the lookup function in all htab map_gen_lookup() callbacks by
> key size and by has_hash. has_hash does not change after map creation,
> so each variant uses a constant elem_has_hash. This also removes the
> load and the branch on htab->has_hash for other key sizes.
> LRU_PERCPU_HASH has no inlined lookup and does not change.
> 
> [...]

Here is the summary with links:
  - [bpf-next] bpf: Specialize inlined lookups for more htab types
    https://git.kernel.org/bpf/bpf-next/c/d03b6e1357dc

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html