The BPF hashmap uses the jhash() hash function. There is an optimized version
of this hash function which may be used if hash size is a multiple of 4. Apply
this optimization to the hashmap in a similar way as it is done in the bloom
filter map.
On practice the optimization is only noticeable for smaller key sizes, which,
however, is sufficient for many applications. An example is listed in the
following table of measurements (a hashmap of 65536 elements was used):
--------------------------------------------------------------------
| key_size | fullness | lookups /sec | lookups (opt) /sec | gain |
--------------------------------------------------------------------
| 4 | 25% | 42.990M | 46.000M | 7.0% |
| 4 | 50% | 37.910M | 39.094M | 3.1% |
| 4 | 75% | 34.486M | 36.124M | 4.7% |
| 4 | 100% | 31.760M | 32.719M | 3.0% |
--------------------------------------------------------------------
| 8 | 25% | 43.855M | 49.626M | 13.2% |
| 8 | 50% | 38.328M | 42.152M | 10.0% |
| 8 | 75% | 34.483M | 38.088M | 10.5% |
| 8 | 100% | 31.306M | 34.686M | 10.8% |
--------------------------------------------------------------------
| 12 | 25% | 38.398M | 43.770M | 14.0% |
| 12 | 50% | 33.336M | 37.712M | 13.1% |
| 12 | 75% | 29.917M | 34.440M | 15.1% |
| 12 | 100% | 27.322M | 30.480M | 11.6% |
--------------------------------------------------------------------
| 16 | 25% | 41.491M | 41.921M | 1.0% |
| 16 | 50% | 36.206M | 36.474M | 0.7% |
| 16 | 75% | 32.529M | 33.027M | 1.5% |
| 16 | 100% | 29.581M | 30.325M | 2.5% |
--------------------------------------------------------------------
| 20 | 25% | 34.240M | 36.787M | 7.4% |
| 20 | 50% | 30.328M | 32.663M | 7.7% |
| 20 | 75% | 27.536M | 29.354M | 6.6% |
| 20 | 100% | 24.847M | 26.505M | 6.7% |
--------------------------------------------------------------------
| 24 | 25% | 36.329M | 40.608M | 11.8% |
| 24 | 50% | 31.444M | 35.059M | 11.5% |
| 24 | 75% | 28.426M | 31.452M | 10.6% |
| 24 | 100% | 26.278M | 28.741M | 9.4% |
--------------------------------------------------------------------
| 28 | 25% | 31.540M | 31.944M | 1.3% |
| 28 | 50% | 27.739M | 28.063M | 1.2% |
| 28 | 75% | 24.993M | 25.814M | 3.3% |
| 28 | 100% | 23.513M | 23.500M | -0.1% |
--------------------------------------------------------------------
| 32 | 25% | 32.116M | 33.953M | 5.7% |
| 32 | 50% | 28.879M | 29.859M | 3.4% |
| 32 | 75% | 26.227M | 26.948M | 2.7% |
| 32 | 100% | 23.829M | 24.613M | 3.3% |
--------------------------------------------------------------------
| 64 | 25% | 22.535M | 22.554M | 0.1% |
| 64 | 50% | 20.471M | 20.675M | 1.0% |
| 64 | 75% | 19.077M | 19.146M | 0.4% |
| 64 | 100% | 17.710M | 18.131M | 2.4% |
--------------------------------------------------------------------
The following script was used to gather the results (SMT & frequency off):
cd tools/testing/selftests/bpf
for key_size in 4 8 12 16 20 24 28 32 64; do
for nr_entries in `seq 16384 16384 65536`; do
fullness=$(printf '%3s' $((nr_entries*100/65536)))
echo -n "key_size=$key_size: $fullness% full: "
sudo ./bench -d2 -a bpf-hashmap-lookup --key_size=$key_size --nr_entries=$nr_entries --max_entries=65536 --nr_loops=2000000 --map_flags=0x40 | grep cpu
done
echo
done
Signed-off-by: Anton Protopopov <aspsk@xxxxxxxxxxxxx>
---
kernel/bpf/hashtab.c | 29 ++++++++++++++++++-----------
1 file changed, 18 insertions(+), 11 deletions(-)
diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 96b645bba3a4..eb804815f7c3 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -103,6 +103,7 @@ struct bpf_htab {
u32 n_buckets; /* number of hash buckets */
u32 elem_size; /* size of each element in bytes */
u32 hashrnd;
+ u32 key_size_u32;
struct lock_class_key lockdep_key;
int __percpu *map_locked[HASHTAB_MAP_LOCK_COUNT];
};
@@ -510,6 +511,10 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
else
htab->elem_size += round_up(htab->map.value_size, 8);
+ /* optimize hash computations if key_size is divisible by 4 */
+ if ((attr->key_size & (sizeof(u32) - 1)) == 0)
+ htab->key_size_u32 = attr->key_size / sizeof(u32);
+
err = -E2BIG;
/* prevent zero size kmalloc and check for u32 overflow */
if (htab->n_buckets == 0 ||
@@ -605,9 +610,11 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
return ERR_PTR(err);
}
-static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
+static inline u32 htab_map_hash(const struct bpf_htab *htab, const void *key, u32 key_len)
{
- return jhash(key, key_len, hashrnd);
+ if (likely(htab->key_size_u32))
+ return jhash2(key, htab->key_size_u32, htab->hashrnd);
+ return jhash(key, key_len, htab->hashrnd);
}
static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
@@ -673,7 +680,7 @@ static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
key_size = map->key_size;
- hash = htab_map_hash(key, key_size, htab->hashrnd);
+ hash = htab_map_hash(htab, key, key_size);
head = select_bucket(htab, hash);
@@ -832,7 +839,7 @@ static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
if (!key)
goto find_first_elem;
- hash = htab_map_hash(key, key_size, htab->hashrnd);
+ hash = htab_map_hash(htab, key, key_size);
head = select_bucket(htab, hash);
@@ -1093,7 +1100,7 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value,
key_size = map->key_size;
- hash = htab_map_hash(key, key_size, htab->hashrnd);
+ hash = htab_map_hash(htab, key, key_size);
b = __select_bucket(htab, hash);
head = &b->head;
@@ -1195,7 +1202,7 @@ static long htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value
key_size = map->key_size;
- hash = htab_map_hash(key, key_size, htab->hashrnd);
+ hash = htab_map_hash(htab, key, key_size);
b = __select_bucket(htab, hash);
head = &b->head;
@@ -1263,7 +1270,7 @@ static long __htab_percpu_map_update_elem(struct bpf_map *map, void *key,
key_size = map->key_size;
- hash = htab_map_hash(key, key_size, htab->hashrnd);
+ hash = htab_map_hash(htab, key, key_size);
b = __select_bucket(htab, hash);
head = &b->head;
@@ -1318,7 +1325,7 @@ static long __htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key,
key_size = map->key_size;
- hash = htab_map_hash(key, key_size, htab->hashrnd);
+ hash = htab_map_hash(htab, key, key_size);
b = __select_bucket(htab, hash);
head = &b->head;
@@ -1393,7 +1400,7 @@ static long htab_map_delete_elem(struct bpf_map *map, void *key)
key_size = map->key_size;
- hash = htab_map_hash(key, key_size, htab->hashrnd);
+ hash = htab_map_hash(htab, key, key_size);
b = __select_bucket(htab, hash);
head = &b->head;
@@ -1429,7 +1436,7 @@ static long htab_lru_map_delete_elem(struct bpf_map *map, void *key)
key_size = map->key_size;
- hash = htab_map_hash(key, key_size, htab->hashrnd);
+ hash = htab_map_hash(htab, key, key_size);
b = __select_bucket(htab, hash);
head = &b->head;
@@ -1572,7 +1579,7 @@ static int __htab_map_lookup_and_delete_elem(struct bpf_map *map, void *key,
key_size = map->key_size;
- hash = htab_map_hash(key, key_size, htab->hashrnd);
+ hash = htab_map_hash(htab, key, key_size);
b = __select_bucket(htab, hash);
head = &b->head;
--
2.34.1
