selftests/bpf: Add benchmark for local_storage get
Subsystems (3)
PATCH v2 1/1 selftests/bpf: Add benchmark for local_storage get
Add a benchmarks to demonstrate the performance cliff for local_storage get as the number of local_storage maps increases beyond current local_storage implementation's cache size.
"sequential get" and "interleaved get" benchmarks are added, both of which do many bpf_task_storage_get calls on sets of task local_storage maps of various counts, while considering a single specific map to be 'important' and counting task_storage_gets to the important map separately in addition to normal 'hits' count of all gets. Goal here is to mimic scenario where a particular program using one map - the important one - is running on a system where many other local_storage maps exist and are accessed often.
While "sequential get" benchmark does bpf_task_storage_get for map 0, 1, ..., {9, 99, 999} in order, "interleaved" benchmark interleaves 4 bpf_task_storage_gets for the important map for every 10 map gets. This is meant to highlight performance differences when important map is accessed far more frequently than non-important maps.
A "hashmap control" benchmark is also included for easy comparison of standard bpf hashmap lookup vs local_storage get. The benchmark is identical to "sequential get", but creates and uses BPF_MAP_TYPE_HASH instead of local storage.
Addition of this benchmark is inspired by conversation with Alexei in a previous patchset's thread [0], which highlighted the need for such a benchmark to motivate and validate improvements to local_storage implementation. My approach in that series focused on improving performance for explicitly-marked 'important' maps and was rejected with feedback to make more generally-applicable improvements while avoiding explicitly marking maps as important. Thus the benchmark reports both general and important-map-focused metrics, so effect of future work on both is clear.
Regarding the benchmark results. On a powerful system (Skylake, 20 cores, 256gb ram):
Local Storage
=============
Hashmap Control w/ 500 maps
hashmap (control) sequential get: hits throughput: 64.689 ± 2.806 M ops/s, hits latency: 15.459 ns/op, important_hits throughput: 0.129 ± 0.006 M ops/s
num_maps: 1
local_storage cache sequential get: hits throughput: 3.793 ± 0.101 M ops/s, hits latency: 263.623 ns/op, important_hits throughput: 3.793 ± 0.101 M ops/s local_storage cache interleaved get: hits throughput: 6.539 ± 0.209 M ops/s, hits latency: 152.938 ns/op, important_hits throughput: 6.539 ± 0.209 M ops/s
num_maps: 10
local_storage cache sequential get: hits throughput: 20.237 ± 0.439 M ops/s, hits latency: 49.415 ns/op, important_hits throughput: 2.024 ± 0.044 M ops/s local_storage cache interleaved get: hits throughput: 22.421 ± 0.874 M ops/s, hits latency: 44.601 ns/op, important_hits throughput: 8.007 ± 0.312 M ops/s
num_maps: 16
local_storage cache sequential get: hits throughput: 25.582 ± 0.346 M ops/s, hits latency: 39.090 ns/op, important_hits throughput: 1.599 ± 0.022 M ops/s local_storage cache interleaved get: hits throughput: 26.615 ± 0.601 M ops/s, hits latency: 37.573 ns/op, important_hits throughput: 8.468 ± 0.191 M ops/s
num_maps: 17
local_storage cache sequential get: hits throughput: 22.932 ± 0.436 M ops/s, hits latency: 43.606 ns/op, important_hits throughput: 1.349 ± 0.026 M ops/s local_storage cache interleaved get: hits throughput: 24.005 ± 0.462 M ops/s, hits latency: 41.658 ns/op, important_hits throughput: 7.306 ± 0.140 M ops/s
num_maps: 24
local_storage cache sequential get: hits throughput: 16.025 ± 0.821 M ops/s, hits latency: 62.402 ns/op, important_hits throughput: 0.668 ± 0.034 M ops/s local_storage cache interleaved get: hits throughput: 17.691 ± 0.744 M ops/s, hits latency: 56.526 ns/op, important_hits throughput: 4.976 ± 0.209 M ops/s
num_maps: 32
local_storage cache sequential get: hits throughput: 11.865 ± 0.180 M ops/s, hits latency: 84.279 ns/op, important_hits throughput: 0.371 ± 0.006 M ops/s local_storage cache interleaved get: hits throughput: 14.383 ± 0.108 M ops/s, hits latency: 69.525 ns/op, important_hits throughput: 4.014 ± 0.030 M ops/s
num_maps: 100
local_storage cache sequential get: hits throughput: 6.105 ± 0.190 M ops/s, hits latency: 163.798 ns/op, important_hits throughput: 0.061 ± 0.002 M ops/s local_storage cache interleaved get: hits throughput: 7.055 ± 0.129 M ops/s, hits latency: 141.746 ns/op, important_hits throughput: 1.843 ± 0.034 M ops/s
num_maps: 1000
local_storage cache sequential get: hits throughput: 0.433 ± 0.010 M ops/s, hits latency: 2309.469 ns/op, important_hits throughput: 0.000 ± 0.000 M ops/s local_storage cache interleaved get: hits throughput: 0.499 ± 0.026 M ops/s, hits latency: 2002.510 ns/op, important_hits throughput: 0.127 ± 0.007 M ops/s
Looking at the "sequential get" results, it's clear that as the number of task local_storage maps grows beyond the current cache size (16), there's a significant reduction in hits throughput. Note that current local_storage implementation assigns a cache_idx to maps as they are created. Since "sequential get" is creating maps 0..n in order and then doing bpf_task_storage_get calls in the same order, the benchmark is effectively ensuring that a map will not be in cache when the program tries to access it.
For "interleaved get" results, important-map hits throughput is greatly increased as the important map is more likely to be in cache by virtue of being accessed far more frequently. Throughput still reduces as # maps increases, though.
Note that the test programs need to split task_storage_get calls across multiple programs to work around the verifier's MAX_USED_MAPS limitations. As evidenced by the unintuitive-looking results for smaller num_maps benchmark runs, overhead which is amortized across larger num_maps in other runs dominates when there are fewer maps. To get a sense of the overhead, I commented out bpf_task_storage_get/bpf_map_lookup_elem in local_storage_bench.h and ran the benchmark on the same host as 'real' run. Results:
Local Storage
=============
Hashmap Control w/ 500 maps
hashmap (control) sequential get: hits throughput: 115.812 ± 2.513 M ops/s, hits latency: 8.635 ns/op, important_hits throughput: 0.232 ± 0.005 M ops/s
num_maps: 1
local_storage cache sequential get: hits throughput: 4.031 ± 0.033 M ops/s, hits latency: 248.094 ns/op, important_hits throughput: 4.031 ± 0.033 M ops/s local_storage cache interleaved get: hits throughput: 7.997 ± 0.088 M ops/s, hits latency: 125.046 ns/op, important_hits throughput: 7.997 ± 0.088 M ops/s
num_maps: 10
local_storage cache sequential get: hits throughput: 34.000 ± 0.077 M ops/s, hits latency: 29.412 ns/op, important_hits throughput: 3.400 ± 0.008 M ops/s local_storage cache interleaved get: hits throughput: 37.895 ± 0.670 M ops/s, hits latency: 26.389 ns/op, important_hits throughput: 13.534 ± 0.239 M ops/s
num_maps: 16
local_storage cache sequential get: hits throughput: 46.947 ± 0.283 M ops/s, hits latency: 21.300 ns/op, important_hits throughput: 2.934 ± 0.018 M ops/s local_storage cache interleaved get: hits throughput: 47.301 ± 1.027 M ops/s, hits latency: 21.141 ns/op, important_hits throughput: 15.050 ± 0.327 M ops/s
num_maps: 17
local_storage cache sequential get: hits throughput: 45.871 ± 0.414 M ops/s, hits latency: 21.800 ns/op, important_hits throughput: 2.698 ± 0.024 M ops/s local_storage cache interleaved get: hits throughput: 46.591 ± 1.969 M ops/s, hits latency: 21.463 ns/op, important_hits throughput: 14.180 ± 0.599 M ops/s
num_maps: 24
local_storage cache sequential get: hits throughput: 58.053 ± 1.043 M ops/s, hits latency: 17.226 ns/op, important_hits throughput: 2.419 ± 0.043 M ops/s local_storage cache interleaved get: hits throughput: 58.115 ± 0.377 M ops/s, hits latency: 17.207 ns/op, important_hits throughput: 16.345 ± 0.106 M ops/s
num_maps: 32
local_storage cache sequential get: hits throughput: 68.548 ± 0.820 M ops/s, hits latency: 14.588 ns/op, important_hits throughput: 2.142 ± 0.026 M ops/s local_storage cache interleaved get: hits throughput: 63.015 ± 0.963 M ops/s, hits latency: 15.869 ns/op, important_hits throughput: 17.586 ± 0.269 M ops/s
num_maps: 100
local_storage cache sequential get: hits throughput: 95.375 ± 1.286 M ops/s, hits latency: 10.485 ns/op, important_hits throughput: 0.954 ± 0.013 M ops/s local_storage cache interleaved get: hits throughput: 76.996 ± 2.614 M ops/s, hits latency: 12.988 ns/op, important_hits throughput: 20.111 ± 0.683 M ops/s
num_maps: 1000
local_storage cache sequential get: hits throughput: 119.965 ± 1.386 M ops/s, hits latency: 8.336 ns/op, important_hits throughput: 0.120 ± 0.001 M ops/s local_storage cache interleaved get: hits throughput: 92.665 ± 0.788 M ops/s, hits latency: 10.792 ns/op, important_hits throughput: 23.581 ± 0.200 M ops/s
Adjusting for overhead, latency numbers for "hashmap control" and "sequential get" are:
hashmap_control: ~6.8ns sequential_get_1: ~15.5ns sequential_get_10: ~20ns sequential_get_16: ~17.8ns sequential_get_17: ~21.8ns sequential_get_24: ~45.2ns sequential_get_32: ~69.7ns sequential_get_100: ~153.3ns sequential_get_1000: ~2300ns
Clearly demonstrating a cliff.
When running the benchmarks it may be necessary to bump 'open files' ulimit for a successful run.
[0]: https://lore.kernel.org/all/[email protected]
---
Changelog:
v1 -> v2:
* Adopt ARRAY_OF_MAPS approach for bpf program, allowing truly configurable # of maps (Andrii)
* Add hashmap benchmark (Alexei)
* Add discussion of overhead
tools/testing/selftests/bpf/Makefile | 6 +- tools/testing/selftests/bpf/bench.c | 57 +++ tools/testing/selftests/bpf/bench.h | 5 + .../bpf/benchs/bench_local_storage.c | 345 ++++++++++++++++++ .../bpf/benchs/run_bench_local_storage.sh | 21 ++ .../selftests/bpf/benchs/run_common.sh | 17 + .../selftests/bpf/progs/local_storage_bench.h | 69 ++++ .../bpf/progs/local_storage_bench__get_int.c | 31 ++ .../bpf/progs/local_storage_bench__get_seq.c | 31 ++ .../bpf/progs/local_storage_bench__hashmap.c | 32 ++ 10 files changed, 613 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_local_storage.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_local_storage.sh create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench.h create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__get_int.c create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__get_seq.c create mode 100644 tools/testing/selftests/bpf/progs/local_storage_bench__hashmap.c
tools/testing/selftests/bpf/Makefile +5 -1
@@ -560,6 +560,9 @@ $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \ $(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_bench.skel.h $(OUTPUT)/bench_bpf_loop.o: $(OUTPUT)/bpf_loop_bench.skel.h $(OUTPUT)/bench_strncmp.o: $(OUTPUT)/strncmp_bench.skel.h +$(OUTPUT)/bench_local_storage.o: $(OUTPUT)/local_storage_bench__get_seq.skel.h \ + $(OUTPUT)/local_storage_bench__get_int.skel.h \ + $(OUTPUT)/local_storage_bench__hashmap.skel.h $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o \
@@ -571,7 +574,8 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_ringbufs.o \ $(OUTPUT)/bench_bloom_filter_map.o \ $(OUTPUT)/bench_bpf_loop.o \ - $(OUTPUT)/bench_strncmp.o + $(OUTPUT)/bench_strncmp.o \ + $(OUTPUT)/bench_local_storage.o $(call msg,BINARY,,$@) $(Q)$(CC) $(CFLAGS) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@
tools/testing/selftests/bpf/bench.c +57 -0
92 lines not on this page · raw message
tools/testing/selftests/bpf/bench.h +5 -0
@@ -34,12 +34,14 @@ struct bench_res {long hits;long drops;long false_hits; +long important_hits; };struct bench {const char *name;void (*validate)(void );void (*setup)(void ); +void (*teardown)(void );void *(*producer_thread)(void *ctx);void *(*consumer_thread)(void *ctx);void (*measure)(struct bench_res * res);
@@ -61,6 +63,9 @@ void false_hits_report_progress(int iter, struct bench_res *res, long delta_ns);void false_hits_report_final (struct bench_res res[],int res_cnt);void ops_report_progress (int iter,struct bench_res *res,long delta_ns);void ops_report_final (struct bench_res res[],int res_cnt); +void local_storage_report_progress (int iter,struct bench_res *res, +long delta_ns); +void local_storage_report_final (struct bench_res res[],int res_cnt);static inline __u64 get_time_ns (void ) {
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +345 -0
345 lines not on this page · raw message
tools/testing/selftests/bpf/benchs/run_bench_local_storage.sh new file +21 -0
@@ -0,0 +1,21 @@ +#!/bin/bash +# SPDX-License-Identifier: GPL-2.0 + +source ./benchs/run_common.sh + +set -eufo pipefail + +header "Local Storage" +subtitle "Hashmap Control w/ 500 maps" + summarize_local_storage "hashmap (control) sequential get: "\ + "$(./bench --nr_maps 500 local-storage-cache-hashmap-control)" + printf "\n" + +for i in 1 10 16 17 24 32 100 1000; do +subtitle "num_maps: $i" + summarize_local_storage "local_storage cache sequential get: "\ + "$(./bench --nr_maps $i local-storage-cache-seq-get)" + summarize_local_storage "local_storage cache interleaved get: "\ + "$(./bench --nr_maps $i local-storage-cache-int-get)" + printf "\n" +done
tools/testing/selftests/bpf/benchs/run_common.sh +17 -0
@@ -41,6 +41,16 @@ function ops() echo "$*" | sed -E "s/.*latency\s+([0-9]+\.[0-9]+\sns\/op).*/\1/" } +function local_storage() +{ + echo -n "hits throughput: " + echo -n "$*" | sed -E "s/.* hits throughput\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+\sM\sops\/s).*/\1/" + echo -n -e ", hits latency: " + echo -n "$*" | sed -E "s/.* hits latency\s+([0-9]+\.[0-9]+\sns\/op).*/\1/" + echo -n ", important_hits throughput: " + echo "$*" | sed -E "s/.*important_hits throughput\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+\sM\sops\/s).*/\1/" +} + function total() { echo "$*" | sed -E "s/.*total operations\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/"
@@ -67,6 +77,13 @@ function summarize_ops() printf "%-20s %s\n" "$bench" "$(ops $summary)" } +function summarize_local_storage() +{ + bench="$1" + summary=$(echo $2 | tail -n1) + printf "%-20s %s\n" "$bench" "$(local_storage $summary)" +} + function summarize_total() { bench="$1"
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +69 -0
69 lines not on this page · raw message
tools/testing/selftests/bpf/progs/local_storage_bench__get_int.c new file +31 -0
@@ -0,0 +1,31 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +#include "local_storage_bench.h" + +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,0 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,50 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,100 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,150 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,200 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,250 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,300 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,350 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,400 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,450 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,500 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,550 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,600 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,650 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,700 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,750 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,800 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,850 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,900 ); +TASK_STORAGE_GET_LOOP_PROG_INT (array_of_maps,950 ); + +char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/progs/local_storage_bench__get_seq.c new file +31 -0
@@ -0,0 +1,31 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +#include "local_storage_bench.h" + +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,0 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,50 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,100 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,150 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,200 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,250 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,300 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,350 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,400 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,450 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,500 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,550 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,600 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,650 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,700 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,750 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,800 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,850 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,900 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,950 ); + +char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/progs/local_storage_bench__hashmap.c new file +32 -0
@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +#define LOOKUP_HASHMAP +#include "local_storage_bench.h" + +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,0 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,50 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,100 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,150 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,200 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,250 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,300 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,350 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,400 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,450 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,500 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,550 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,600 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,650 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,700 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,750 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,800 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,850 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,900 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,950 ); + +char _license[] SEC("license") = "GPL";
Signature · 1 line
2.30.2
Quoted 5 lines · Dave Marchevsky
maps increases, though.
Note that the test programs need to split
task_storage_getcalls across multiple programs to work around the verifier'sMAX_USED_MAPSlimitations.
...
Quoted 21 lines
+++
b/tools/testing/selftests/bpf/progs/local_storage_bench.htools/testing/selftests/bpf/progs/local_storage_bench.h new file +19
-0@@ -0,0 +1,69 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); + __uint(max_entries, 1000); + __type(key, int); + __type(value, int); +} array_of_maps SEC(".maps"); + +long important_hits; +long hits; + +#ifdef LOOKUP_HASHMAP +static int do_lookup (unsigned int elem,struct task_struct *task/* unused */ ) +{ +void *map; +int zero =0 ; +
tools/testing/selftests/bpf/progs/local_storage_bench.h line 29
Quoted 10 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +10
-0+ map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_map_lookup_elem (map, &zero); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +}
This prog accesses only two maps: array_of_maps and global data (hidden array map).
Where do you see it's reaching MAX_USED_MAPS limit ?
Quoted 42 lines · Alexei Starovoitov
Quoted 5 lines · Dave Marchevsky
maps increases, though.
Note that the test programs need to split
task_storage_getcalls across multiple programs to work around the verifier'sMAX_USED_MAPSlimitations....
Quoted 21 lines
+++
b/tools/testing/selftests/bpf/progs/local_storage_bench.htools/testing/selftests/bpf/progs/local_storage_bench.h new file +19
-0@@ -0,0 +1,69 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); + __uint(max_entries, 1000); + __type(key, int); + __type(value, int); +} array_of_maps SEC(".maps"); + +long important_hits; +long hits; + +#ifdef LOOKUP_HASHMAP +static int do_lookup (unsigned int elem,struct task_struct *task/* unused */ ) +{ +void *map; +int zero =0 ; +tools/testing/selftests/bpf/progs/local_storage_bench.h line 29
Quoted 10 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +10
-0+ map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_map_lookup_elem (map, &zero); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +}This prog accesses only two maps:
array_of_mapsand global data (hidden array map).
Quoted 1 line
Where do you see it's reaching
MAX_USED_MAPSlimit ?
You're right, that's a holdover from v1.
Will fix and send v3 w/ new benchmark results.
Quoted 40 lines · Dave Marchevsky
Add a benchmarks to demonstrate the performance cliff for
local_storageget as the number oflocal_storagemaps increases beyond currentlocal_storageimplementation's cache size."sequential get" and "interleaved get" benchmarks are added, both of which do many
bpf_task_storage_getcalls on sets of tasklocal_storagemaps of various counts, while considering a single specific map to be 'important' and countingtask_storage_getsto the important map separately in addition to normal 'hits' count of all gets. Goal here is to mimic scenario where a particular program using one map - the important one - is running on a system where many otherlocal_storagemaps exist and are accessed often.While "sequential get" benchmark does
bpf_task_storage_getfor map 0, 1, ..., {9, 99, 999} in order, "interleaved" benchmark interleaves 4bpf_task_storage_getsfor the important map for every 10 map gets. This is meant to highlight performance differences when important map is accessed far more frequently than non-important maps.A "hashmap control" benchmark is also included for easy comparison of standard bpf hashmap lookup vs
local_storageget. The benchmark is identical to "sequential get", but creates and usesBPF_MAP_TYPE_HASHinstead of local storage.Addition of this benchmark is inspired by conversation with Alexei in a previous patchset's thread [0], which highlighted the need for such a benchmark to motivate and validate improvements to
local_storageimplementation. My approach in that series focused on improving performance for explicitly-marked 'important' maps and was rejected with feedback to make more generally-applicable improvements while avoiding explicitly marking maps as important. Thus the benchmark reports both general and important-map-focused metrics, so effect of future work on both is clear.Regarding the benchmark results. On a powerful system (Skylake, 20 cores, 256gb ram):
Local Storage
=============
[...]
Quoted 26 lines
Looking at the "sequential get" results, it's clear that as the number of task
local_storagemaps grows beyond the current cache size (16), there's a significant reduction in hits throughput. Note that currentlocal_storageimplementation assigns acache_idxto maps as they are created. Since "sequential get" is creating maps 0..n in order and then doingbpf_task_storage_getcalls in the same order, the benchmark is effectively ensuring that a map will not be in cache when the program tries to access it.For "interleaved get" results, important-map hits throughput is greatly increased as the important map is more likely to be in cache by virtue of being accessed far more frequently. Throughput still reduces as # maps increases, though.
Note that the test programs need to split
task_storage_getcalls across multiple programs to work around the verifier'sMAX_USED_MAPSlimitations. As evidenced by the unintuitive-looking results for smallernum_mapsbenchmark runs, overhead which is amortized across largernum_mapsin other runs dominates when there are fewer maps. To get a sense of the overhead, I commented out bpf_task_storage_get/bpf_map_lookup_elem inlocal_storage_bench.hand ran the benchmark on the same host as 'real' run. Results:Local Storage
=============
[...]
Quoted 30 lines
Adjusting for overhead, latency numbers for "hashmap control" and "sequential get" are:
hashmap_control: ~6.8ns sequential_get_1: ~15.5ns sequential_get_10: ~20ns sequential_get_16: ~17.8ns sequential_get_17: ~21.8ns sequential_get_24: ~45.2ns sequential_get_32: ~69.7ns sequential_get_100: ~153.3ns sequential_get_1000: ~2300nsClearly demonstrating a cliff.
When running the benchmarks it may be necessary to bump 'open files' ulimit for a successful run.
[0]: https://lore.kernel.org/all/[email protected]
Signed-off-by Dave Marchevsky <[email protected]>---
Changelog:v1 -> v2:
* AdoptARRAY_OF_MAPSapproach for bpf program, allowing truly configurable # of maps (Andrii)
* Add hashmap benchmark (Alexei)
* Add discussion of overhead
[...]
Quoted 9 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +9
-0+ +/* Keep in sync w/ array of maps in bpf */ +#define MAX_NR_MAPS 1000 +/* Keep in sync w/ number of progs in bpf app */ +#define MAX_NR_PROGS 20 + +static struct { + void (*destroy_skel)(void *obj); + int (*load_skel)(void *obj);
tools/testing/selftests/bpf/benchs/bench_local_storage.c line 89
Quoted 10 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +10
-0+long *important_hits; +long *hits; +void *progs; +void *skel; +struct bpf_map *array_of_maps; +} ctx; + +int created_maps[MAX_NR_MAPS ]; +struct bpf_link *attached_links[MAX_NR_PROGS ]; +
static?
Quoted 10 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +10
-0+static void teardown (void ) +{ +int i; + +for (i =0 ; i <MAX_NR_PROGS ; i++) { +if (!attached_links[i]) +break ; +bpf_link__detach (attached_links[i]); + } +
tools/testing/selftests/bpf/benchs/bench_local_storage.c line 109
Quoted 10 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +10
-0+if (ctx.destroy_skel && ctx.skel) + ctx.destroy_skel (ctx.skel); + +for (i =0 ; i <MAX_NR_MAPS ; i++) { +if (!created_maps[i]) +break ; +close (created_maps[i]); + } +} +
Wouldn't all this be cleaned up on bench exit anyway?.. We've been less strict about proper clean up for bench to keep code simpler.
[...]
Quoted 6 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +0
-0
tools/testing/selftests/bpf/progs/local_storage_bench.h line 9
Quoted 9 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +9
-0@@ -0,0 +1,69 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); + __uint(max_entries, 1000); + __type(key, int); + __type(value, int); +} array_of_maps SEC(".maps");
you don't need setup_inner_map_and_load and load_btf, you can just declaratively have two ARRAY_OF_MAPS, one using inner hashmap and another using inner task_local_storage. Grep for __array in selftests to see how to declaratively define inner map prototype, e.g., see test_ringbuf_multi.c. With the below suggestion one of do_lookup flavors will use array_of_hashes and another will use array_of_storages explicitly. From user-space you can create and setup as many inner maps as needed. If you need btf_id for value_type_id for inner map, see if bpf_map__inner_map() would be useful.
tools/testing/selftests/bpf/progs/local_storage_bench.h line 14
Quoted 5 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +5
-0+ +long important_hits; +long hits; + +#ifdef LOOKUP_HASHMAP
why #ifdef'ing if you can have do_lookup_hashmap and do_lookup_task_storage and choose which one to call using read-only variable:
const volatile bool use_hashmap;
just set it before load and verifier will know that one of do_lookup flavors is dead code
Quoted 32 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +32
-0+static int do_lookup (unsigned int elem,struct task_struct *task/* unused */ ) +{ +void *map; +int zero =0 ; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_map_lookup_elem (map, &zero); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#else +static int do_lookup (unsigned int elem,struct task_struct *task) +{ +void *map; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_task_storage_get (map, task,0 ,BPF_LOCAL_STORAGE_GET_F_CREATE ); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#endif /* LOOKUP_HASHMAP */ +
tools/testing/selftests/bpf/progs/local_storage_bench.h line 56
Quoted 10 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +10
-0+#define __TASK_STORAGE_GET_LOOP_PROG (array, start, interleave) \ +SEC("fentry/" SYS_PREFIX "sys_getpgid") \ +int get_local_ ## start(void *ctx) \ +{ \ + struct task_struct *task; \ + unsigned int i, elem; \ + void *map; \ + \ + task = bpf_get_current_task_btf(); \ + for (i = 0; i < 50; i++) { \
I'm trying to understand why you didn't just do
for (i = 0; i < 1000; i++) { ... }
and avoid all the macro stuff? what didn't work?
tools/testing/selftests/bpf/progs/local_storage_bench.h line 60
Quoted 4 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +4
-0+ elem = start + i; \ +if (do_lookup (elem, task)) \ +return 0 ; \ +if (interleave && i %3 ==0 ) \
nit % 3 will be slow(-ish), why not pick some power of 2?
Quoted 9 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +9
-0+do_lookup (0 , task); \ + } \ +return 0 ; \ +} + +#define TASK_STORAGE_GET_LOOP_PROG_SEQ (array, start) \ + __TASK_STORAGE_GET_LOOP_PROG(array, start, false) +#define TASK_STORAGE_GET_LOOP_PROG_INT (array, start) \ + __TASK_STORAGE_GET_LOOP_PROG(array, start, true)
[...]
Quoted 12 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +12
-0+ +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,0 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,50 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,100 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,150 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,200 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,250 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,300 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,350 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,400 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,450 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,500 );
tools/testing/selftests/bpf/progs/local_storage_bench.h
Quoted 10 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +10
-0+TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,550 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,600 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,650 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,700 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,750 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,800 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,850 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,900 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,950 ); +
all these macro make me sad, I'd like to understand why it has to be done this way
Quoted 4 lines
+char _license[]
SEC("license")= "GPL";
--
2.30.2
Quoted 119 lines · Andrii Nakryiko
Quoted 40 lines · Dave Marchevsky
Add a benchmarks to demonstrate the performance cliff for
local_storageget as the number oflocal_storagemaps increases beyond currentlocal_storageimplementation's cache size."sequential get" and "interleaved get" benchmarks are added, both of which do many
bpf_task_storage_getcalls on sets of tasklocal_storagemaps of various counts, while considering a single specific map to be 'important' and countingtask_storage_getsto the important map separately in addition to normal 'hits' count of all gets. Goal here is to mimic scenario where a particular program using one map - the important one - is running on a system where many otherlocal_storagemaps exist and are accessed often.While "sequential get" benchmark does
bpf_task_storage_getfor map 0, 1, ..., {9, 99, 999} in order, "interleaved" benchmark interleaves 4bpf_task_storage_getsfor the important map for every 10 map gets. This is meant to highlight performance differences when important map is accessed far more frequently than non-important maps.A "hashmap control" benchmark is also included for easy comparison of standard bpf hashmap lookup vs
local_storageget. The benchmark is identical to "sequential get", but creates and usesBPF_MAP_TYPE_HASHinstead of local storage.Addition of this benchmark is inspired by conversation with Alexei in a previous patchset's thread [0], which highlighted the need for such a benchmark to motivate and validate improvements to
local_storageimplementation. My approach in that series focused on improving performance for explicitly-marked 'important' maps and was rejected with feedback to make more generally-applicable improvements while avoiding explicitly marking maps as important. Thus the benchmark reports both general and important-map-focused metrics, so effect of future work on both is clear.Regarding the benchmark results. On a powerful system (Skylake, 20 cores, 256gb ram):
Local Storage
=============[...]
Quoted 26 lines
Looking at the "sequential get" results, it's clear that as the number of task
local_storagemaps grows beyond the current cache size (16), there's a significant reduction in hits throughput. Note that currentlocal_storageimplementation assigns acache_idxto maps as they are created. Since "sequential get" is creating maps 0..n in order and then doingbpf_task_storage_getcalls in the same order, the benchmark is effectively ensuring that a map will not be in cache when the program tries to access it.For "interleaved get" results, important-map hits throughput is greatly increased as the important map is more likely to be in cache by virtue of being accessed far more frequently. Throughput still reduces as # maps increases, though.
Note that the test programs need to split
task_storage_getcalls across multiple programs to work around the verifier'sMAX_USED_MAPSlimitations. As evidenced by the unintuitive-looking results for smallernum_mapsbenchmark runs, overhead which is amortized across largernum_mapsin other runs dominates when there are fewer maps. To get a sense of the overhead, I commented out bpf_task_storage_get/bpf_map_lookup_elem inlocal_storage_bench.hand ran the benchmark on the same host as 'real' run. Results:Local Storage
=============[...]
Quoted 30 lines
Adjusting for overhead, latency numbers for "hashmap control" and "sequential get" are:
hashmap_control: ~6.8ns sequential_get_1: ~15.5ns sequential_get_10: ~20ns sequential_get_16: ~17.8ns sequential_get_17: ~21.8ns sequential_get_24: ~45.2ns sequential_get_32: ~69.7ns sequential_get_100: ~153.3ns sequential_get_1000: ~2300nsClearly demonstrating a cliff.
When running the benchmarks it may be necessary to bump 'open files' ulimit for a successful run.
[0]: https://lore.kernel.org/all/[email protected]
Signed-off-by Dave Marchevsky <[email protected]>---
Changelog:v1 -> v2:
* AdoptARRAY_OF_MAPSapproach for bpf program, allowing truly configurable # of maps (Andrii)
* Add hashmap benchmark (Alexei)
* Add discussion of overhead[...]
Quoted 13 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +13
-0+ +/* Keep in sync w/ array of maps in bpf */ +#define MAX_NR_MAPS 1000 +/* Keep in sync w/ number of progs in bpf app */ +#define MAX_NR_PROGS 20 + +static struct { + void (*destroy_skel)(void *obj); + int (*load_skel)(void *obj); + long *important_hits; + long *hits; + void *progs; + void *skel;
Quoted 8 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c line 89
Quoted 6 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +6
-0+struct bpf_map *array_of_maps; +} ctx; + +int created_maps[MAX_NR_MAPS ]; +struct bpf_link *attached_links[MAX_NR_PROGS ]; +static?
I sent v3 before seeing this email, but luckily most of your comments are addressed already.
attached_links is removed in v3, created_maps is moved to ctx
Quoted 17 lines
Quoted 17 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +15
-0+static void teardown (void ) +{ +int i; + +for (i =0 ; i <MAX_NR_PROGS ; i++) { +if (!attached_links[i]) +break ; +bpf_link__detach (attached_links[i]); + } + +if (ctx.destroy_skel && ctx.skel) + ctx.destroy_skel (ctx.skel); + +for (i =0 ; i <MAX_NR_MAPS ; i++) { +if (!created_maps[i])
Quoted 8 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c line 109
Quoted 5 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +5
-0+break ; +close (created_maps[i]); + } +} +Wouldn't all this be cleaned up on bench exit anyway?.. We've been less strict about proper clean up for bench to keep code simpler.
It's important to explicitly clean up created_maps because local_storage maps are assigned a cache slot when the map is created, and count of "how many maps are assigned to this cache slot" is incr'd. On map free the count is decr'd.
So cache behavior of subsequently alloc'd maps can be affected if these are kept around.
Not a big deal now since just 1 bench is run and process exits, but if that changes in the future I don't want the benchmark to silently give odd results.
Quoted 21 lines
[...]
Quoted 6 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +0
-0tools/testing/selftests/bpf/progs/local_storage_bench.h line 9
Quoted 9 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +9
-0@@ -0,0 +1,69 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); + __uint(max_entries, 1000); + __type(key, int); + __type(value, int); +} array_of_maps SEC(".maps");you don't need
setup_inner_map_and_loadandload_btf, you can just
Quoted 9 lines
declaratively have two
ARRAY_OF_MAPS, one using inner hashmap and another using innertask_local_storage. Grep for__arrayin selftests to see how to declaratively define inner map prototype, e.g., seetest_ringbuf_multi.c. With the below suggestion one ofdo_lookupflavors will usearray_of_hashesand another will usearray_of_storagesexplicitly. From user-space you can create and setup as many inner maps as needed. If you needbtf_idforvalue_type_idfor inner map, see ifbpf_map__inner_map()would be useful.
Declaratively specifying an inner task_local_storage map will result in libbpf creating such a map to pass as the inner_map_fd, no? This will have same effect on cache_idx assignment as my previous comment.
Quoted 10 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h line 14
Quoted 5 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +5
-0+ +long important_hits; +long hits; + +#ifdef LOOKUP_HASHMAP why #ifdef'ing if you can have
do_lookup_hashmapanddo_lookup_task_storageand choose which one to call using read-only variable:
Quoted 4 lines
const volatile bool
use_hashmap;just set it before load and verifier will know that one of
do_lookupflavors is dead code
I want it to be obvious that the hashmap part of the benchmark is not a flavor of local_storage, the distinct separation of do_lookups here makes this easier to notice.
Can do a v4 addressing this if you feel strongly about it.
Quoted 52 lines
Quoted 33 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +32
-0+static int do_lookup (unsigned int elem,struct task_struct *task/* unused */ ) +{ +void *map; +int zero =0 ; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_map_lookup_elem (map, &zero); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#else +static int do_lookup (unsigned int elem,struct task_struct *task) +{ +void *map; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_task_storage_get (map, task,0 ,BPF_LOCAL_STORAGE_GET_F_CREATE ); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#endif /* LOOKUP_HASHMAP */ +tools/testing/selftests/bpf/progs/local_storage_bench.h line 56
Quoted 10 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +10
-0+#define __TASK_STORAGE_GET_LOOP_PROG (array, start, interleave) \ +SEC("fentry/" SYS_PREFIX "sys_getpgid") \ +int get_local_ ## start(void *ctx) \ +{ \ + struct task_struct *task; \ + unsigned int i, elem; \ + void *map; \ + \ + task = bpf_get_current_task_btf(); \ + for (i = 0; i < 50; i++) { \I'm trying to understand why you didn't just do
for (i = 0; i < 1000; i++) { ... }
and avoid all the macro stuff? what didn't work?
Quoted 6 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h line 60
Quoted 4 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +4
-0+ elem = start + i; \ +if (do_lookup (elem, task)) \ +return 0 ; \ +if (interleave && i %3 ==0 ) \nit % 3 will be slow(-ish), why not pick some power of 2?
Few reasons:
1) This results in a ratio of "get important map" to "get any other map" closest to v1 of this patchset, and similar interleaving pattern. Made it easy to compare results after big refactor and be reasonably sure I didn't break the benchmark.
2) The current local_storage cache has 16 entries and the current cache slot assignment algorithm will always give the important map cache_idx 0 since it's created first. Second created map - idx 1 in the ARRAY_OF_MAPS - will get cache_idx 1, etc, so for this benchmarkcache_idx = map_of_maps_idx % 16. (Assuming no other task_local_storage maps have been created on the system).
We want to pick a small number because in 'important map' scenario the important map is accessed significantly more often than other maps. So < 16. Considering current implementation with fixed cache_idx, if we pick a power of 2 that's < 16, there will always be the same 'gap' between important map get and other map gets with same cache_idx. We care about these specifically since they'll be knocking each other out of cache slot.
If an odd number is used the gaps will vary, resulting in a benchmark more closely mimicing "bunch of unrelated progs accessing maps in arbitrary order, with one important prog accessing its map very frequently".
Probably moving to bpf_get_prandom or some userspace nondeterminism to feed list of indices to interleave gets of important map is the best solution, but I'm hoping to keep things simple for now.
Quoted 30 lines
Quoted 10 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +9
-0+do_lookup (0 , task); \ + } \ +return 0 ; \ +} + +#define TASK_STORAGE_GET_LOOP_PROG_SEQ (array, start) \ + __TASK_STORAGE_GET_LOOP_PROG(array, start, false) +#define TASK_STORAGE_GET_LOOP_PROG_INT (array, start) \ + __TASK_STORAGE_GET_LOOP_PROG(array, start, true)[...]
Quoted 17 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +17
-0+ +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,0 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,50 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,100 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,150 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,200 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,250 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,300 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,350 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,400 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,450 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,500 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,550 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,600 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,650 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,700 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,750 );
Quoted 9 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h
Quoted 5 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +5
-0+TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,800 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,850 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,900 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,950 ); +all these macro make me sad, I'd like to understand why it has to be done this way
Macro and "why not i < 1000" are addressed in v3. v1 of this patch - before your ARRAY_OF_MAPS suggestion - was hitting MAX_USED_MAPS limit and failing verification when trying to access all 1k maps in a single program. I assumed that accessing maps from within an ARRAY_OF_MAPS would trigger similar limit, but this is not the case.
Quoted 4 lines
Quoted 4 lines
+char _license[]
SEC("license")= "GPL";
--
2.30.2
Quoted 165 lines · Dave Marchevsky
Quoted 119 lines · Andrii Nakryiko
Quoted 40 lines · Dave Marchevsky
Add a benchmarks to demonstrate the performance cliff for
local_storageget as the number oflocal_storagemaps increases beyond currentlocal_storageimplementation's cache size."sequential get" and "interleaved get" benchmarks are added, both of which do many
bpf_task_storage_getcalls on sets of tasklocal_storagemaps of various counts, while considering a single specific map to be 'important' and countingtask_storage_getsto the important map separately in addition to normal 'hits' count of all gets. Goal here is to mimic scenario where a particular program using one map - the important one - is running on a system where many otherlocal_storagemaps exist and are accessed often.While "sequential get" benchmark does
bpf_task_storage_getfor map 0, 1, ..., {9, 99, 999} in order, "interleaved" benchmark interleaves 4bpf_task_storage_getsfor the important map for every 10 map gets. This is meant to highlight performance differences when important map is accessed far more frequently than non-important maps.A "hashmap control" benchmark is also included for easy comparison of standard bpf hashmap lookup vs
local_storageget. The benchmark is identical to "sequential get", but creates and usesBPF_MAP_TYPE_HASHinstead of local storage.Addition of this benchmark is inspired by conversation with Alexei in a previous patchset's thread [0], which highlighted the need for such a benchmark to motivate and validate improvements to
local_storageimplementation. My approach in that series focused on improving performance for explicitly-marked 'important' maps and was rejected with feedback to make more generally-applicable improvements while avoiding explicitly marking maps as important. Thus the benchmark reports both general and important-map-focused metrics, so effect of future work on both is clear.Regarding the benchmark results. On a powerful system (Skylake, 20 cores, 256gb ram):
Local Storage
=============[...]
Quoted 26 lines
Looking at the "sequential get" results, it's clear that as the number of task
local_storagemaps grows beyond the current cache size (16), there's a significant reduction in hits throughput. Note that currentlocal_storageimplementation assigns acache_idxto maps as they are created. Since "sequential get" is creating maps 0..n in order and then doingbpf_task_storage_getcalls in the same order, the benchmark is effectively ensuring that a map will not be in cache when the program tries to access it.For "interleaved get" results, important-map hits throughput is greatly increased as the important map is more likely to be in cache by virtue of being accessed far more frequently. Throughput still reduces as # maps increases, though.
Note that the test programs need to split
task_storage_getcalls across multiple programs to work around the verifier'sMAX_USED_MAPSlimitations. As evidenced by the unintuitive-looking results for smallernum_mapsbenchmark runs, overhead which is amortized across largernum_mapsin other runs dominates when there are fewer maps. To get a sense of the overhead, I commented out bpf_task_storage_get/bpf_map_lookup_elem inlocal_storage_bench.hand ran the benchmark on the same host as 'real' run. Results:Local Storage
=============[...]
Quoted 30 lines
Adjusting for overhead, latency numbers for "hashmap control" and "sequential get" are:
hashmap_control: ~6.8ns sequential_get_1: ~15.5ns sequential_get_10: ~20ns sequential_get_16: ~17.8ns sequential_get_17: ~21.8ns sequential_get_24: ~45.2ns sequential_get_32: ~69.7ns sequential_get_100: ~153.3ns sequential_get_1000: ~2300nsClearly demonstrating a cliff.
When running the benchmarks it may be necessary to bump 'open files' ulimit for a successful run.
[0]: https://lore.kernel.org/all/[email protected]
Signed-off-by Dave Marchevsky <[email protected]>---
Changelog:v1 -> v2:
* AdoptARRAY_OF_MAPSapproach for bpf program, allowing truly configurable # of maps (Andrii)
* Add hashmap benchmark (Alexei)
* Add discussion of overhead[...]
Quoted 13 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +13
-0+ +/* Keep in sync w/ array of maps in bpf */ +#define MAX_NR_MAPS 1000 +/* Keep in sync w/ number of progs in bpf app */ +#define MAX_NR_PROGS 20 + +static struct { + void (*destroy_skel)(void *obj); + int (*load_skel)(void *obj); + long *important_hits; + long *hits; + void *progs; + void *skel;Quoted 8 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c line 89
Quoted 6 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +6
-0+struct bpf_map *array_of_maps; +} ctx; + +int created_maps[MAX_NR_MAPS ]; +struct bpf_link *attached_links[MAX_NR_PROGS ]; +static?
I sent v3 before seeing this email, but luckily most of your comments are addressed already.
attached_linksis removed in v3,created_mapsis moved to ctxQuoted 17 lines
Quoted 17 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +15
-0+static void teardown (void ) +{ +int i; + +for (i =0 ; i <MAX_NR_PROGS ; i++) { +if (!attached_links[i]) +break ; +bpf_link__detach (attached_links[i]); + } + +if (ctx.destroy_skel && ctx.skel) + ctx.destroy_skel (ctx.skel); + +for (i =0 ; i <MAX_NR_MAPS ; i++) { +if (!created_maps[i])Quoted 8 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c line 109
Quoted 5 lines
tools/testing/selftests/bpf/benchs/bench_local_storage.c new file +5
-0+break ; +close (created_maps[i]); + } +} +Wouldn't all this be cleaned up on bench exit anyway?.. We've been less strict about proper clean up for bench to keep code simpler.
It's important to explicitly clean up
created_mapsbecauselocal_storagemaps are assigned a cache slot when the map is created, and count of "how many maps are assigned to this cache slot" is incr'd. On map free the count is decr'd.
Quoted 6 lines
So cache behavior of subsequently alloc'd maps can be affected if these are kept around.
Not a big deal now since just 1 bench is run and process exits, but if that changes in the future I don't want the benchmark to silently give odd results.
Right, I don't see why we'd need to support running multiple benchmarks within the same bench process. We can always run ./bench twice. So the exact point is that there is no need to clean up after benchmark (unless kernel won't clean up after us automatically). That's the reason why we never had teardown callback in the first place, not because there is nothing to clean up, but because it will happen automatically on process exit (and that's ok for ./bench).
Quoted 31 lines
Quoted 21 lines
[...]
Quoted 6 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +0
-0tools/testing/selftests/bpf/progs/local_storage_bench.h line 9
Quoted 9 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +9
-0@@ -0,0 +1,69 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */ + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); + __uint(max_entries, 1000); + __type(key, int); + __type(value, int); +} array_of_maps SEC(".maps");you don't need
setup_inner_map_and_loadandload_btf, you can justQuoted 9 lines
declaratively have two
ARRAY_OF_MAPS, one using inner hashmap and another using innertask_local_storage. Grep for__arrayin selftests to see how to declaratively define inner map prototype, e.g., seetest_ringbuf_multi.c. With the below suggestion one ofdo_lookupflavors will usearray_of_hashesand another will usearray_of_storagesexplicitly. From user-space you can create and setup as many inner maps as needed. If you needbtf_idforvalue_type_idfor inner map, see ifbpf_map__inner_map()would be useful.
Quoted 3 lines
Declaratively specifying an inner
task_local_storagemap will result in libbpf creating such a map to pass as theinner_map_fd, no? This will have same effect oncache_idxassignment as my previous comment.
It will inner "prototype" map, pass its FD as inner_map_fd to create outer map. But after that it will immediately close FD and destroy it. Does that affect the benchmark negatively? Extra inner map should be gone by the time you start creating actual inner maps.
Quoted 13 lines
Quoted 13 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h line 14
Quoted 6 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +5
-0+ +long important_hits; +long hits; + +#ifdef LOOKUP_HASHMAP why #ifdef'ing if you can have
do_lookup_hashmapanddo_lookup_task_storageand choose which one to call using read-only variable:const volatile bool
use_hashmap;
Quoted 8 lines
Quoted 2 lines
just set it before load and verifier will know that one of
do_lookupflavors is dead codeI want it to be obvious that the hashmap part of the benchmark is not a flavor of
local_storage, the distinct separation ofdo_lookupshere makes this easier to notice.Can do a v4 addressing this if you feel strongly about it.
I generally dislike #if/#endif guards for BPF code, if they can be avoided, as they go completely against the spirit of CO-RE.
Quoted 58 lines
Quoted 58 lines
Quoted 34 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +32
-0+static int do_lookup (unsigned int elem,struct task_struct *task/* unused */ ) +{ +void *map; +int zero =0 ; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_map_lookup_elem (map, &zero); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#else +static int do_lookup (unsigned int elem,struct task_struct *task) +{ +void *map; + + map =bpf_map_lookup_elem (&array_of_maps, &elem); +if (!map) +return -1 ; + +bpf_task_storage_get (map, task,0 ,BPF_LOCAL_STORAGE_GET_F_CREATE ); +__sync_add_and_fetch (&hits,1 ); +if (!elem) +__sync_add_and_fetch (&important_hits,1 ); +return 0 ; +} +#endif /* LOOKUP_HASHMAP */ +tools/testing/selftests/bpf/progs/local_storage_bench.h line 56
Quoted 10 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +10
-0+#define __TASK_STORAGE_GET_LOOP_PROG (array, start, interleave) \ +SEC("fentry/" SYS_PREFIX "sys_getpgid") \ +int get_local_ ## start(void *ctx) \ +{ \ + struct task_struct *task; \ + unsigned int i, elem; \ + void *map; \ + \ + task = bpf_get_current_task_btf(); \ + for (i = 0; i < 50; i++) { \I'm trying to understand why you didn't just do
for (i = 0; i < 1000; i++) { ... }
and avoid all the macro stuff? what didn't work?
Quoted 4 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +4
-0+ elem = start + i; \ +if (do_lookup (elem, task)) \ +return 0 ; \ +if (interleave && i %3 ==0 ) \
Quoted 9 lines
Quoted 1 line
nit % 3 will be slow(-ish), why not pick some power of 2?
Few reasons:
1) This results in a ratio of "get important map" to "get any other map" closest to v1 of this patchset, and similar interleaving pattern. Made it easy to compare results after big refactor and be reasonably sure I didn't break the benchmark.
ok, np, div and mod are noticeably more expensive than even multiplication, so if you have microbenchmark it would be preferable to avoid division, if possible
Quoted 14 lines
2) The current
local_storagecache has 16 entries and the current cache slot assignment algorithm will always give the important mapcache_idx0 since it's created first. Second created map - idx 1 in theARRAY_OF_MAPS- will getcache_idx1, etc, so for this benchmarkcache_idx=map_of_maps_idx% 16. (Assuming no othertask_local_storagemaps have been created on the system).We want to pick a small number because in 'important map' scenario the important map is accessed significantly more often than other maps. So < 16. Considering current implementation with fixed
cache_idx, if we pick a power of 2 that's < 16, there will always be the same 'gap' between important map get and other map gets with samecache_idx. We care about these specifically since they'll be knocking each other out of cache slot.
Quoted 8 lines
If an odd number is used the gaps will vary, resulting in a benchmark more closely mimicing "bunch of unrelated progs accessing maps in arbitrary order, with one important prog accessing its map very frequently".
Probably moving to
bpf_get_prandomor some userspace nondeterminism to feed list of indices to interleave gets of important map is the best solution, but I'm hoping to keep things simple for now.
yeah, IMO it's fine, as long as it's done consciously
Quoted 40 lines
Quoted 30 lines
Quoted 10 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +9
-0+do_lookup (0 , task); \ + } \ +return 0 ; \ +} + +#define TASK_STORAGE_GET_LOOP_PROG_SEQ (array, start) \ + __TASK_STORAGE_GET_LOOP_PROG(array, start, false) +#define TASK_STORAGE_GET_LOOP_PROG_INT (array, start) \ + __TASK_STORAGE_GET_LOOP_PROG(array, start, true)[...]
Quoted 17 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +17
-0+ +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,0 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,50 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,100 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,150 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,200 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,250 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,300 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,350 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,400 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,450 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,500 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,550 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,600 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,650 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,700 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,750 );Quoted 9 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h
Quoted 5 lines
tools/testing/selftests/bpf/progs/local_storage_bench.h new file +5
-0+TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,800 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,850 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,900 ); +TASK_STORAGE_GET_LOOP_PROG_SEQ (array_of_maps,950 ); +all these macro make me sad, I'd like to understand why it has to be done this way
Quoted 5 lines
Macro and "why not i < 1000" are addressed in v3. v1 of this patch - before your
ARRAY_OF_MAPSsuggestion - was hittingMAX_USED_MAPSlimit and failing verification when trying to access all 1k maps in a single program. I assumed that accessing maps from within anARRAY_OF_MAPSwould trigger similar limit, but this is not the case.
ok, haven't checked v3 yet, will take a look, thanks
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
+char _license[]
SEC("license")= "GPL";
--
2.30.2