Skip to contentSkip to conversation

selftests/bpf: Add benchmark for local_storage get

PATCH Superseded Dave Marchevsky 3 participants 6 messages May 18, 2022 – May 23, 2022

Subsystems (3)

v2 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

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
index 4030dd6cbc34..6095f6af2ad1 100644
@@ -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
index fb3e213df3dc..0a137eedc959 100644
@@ -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
new file mode 100755
index 000000000000..479096c47c93
@@ -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
index 6c5e6023a69f..d9f40af82006 100644
@@ -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
new file mode 100644
index 000000000000..498f0c81014b
@@ -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
new file mode 100644
index 000000000000..71514576a05d
@@ -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
new file mode 100644
index 000000000000..15e4fe13d0b5
@@ -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
#1 lore raw
Quoted 5 lines · Dave Marchevsky

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.

...

Quoted 21 lines

+++ b/tools/testing/selftests/bpf/progs/local_storage_bench.h

tools/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 ?

#2 lore raw
Quoted 42 lines · Alexei Starovoitov
Quoted 5 lines · Dave Marchevsky

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.

...

Quoted 21 lines

+++ b/tools/testing/selftests/bpf/progs/local_storage_bench.h

tools/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).

Quoted 1 line

Where do you see it's reaching MAX_USED_MAPS limit ?

You're right, that's a holdover from v1.

Will fix and send v3 w/ new benchmark results.

#3 lore raw
In reply to Dave Marchevsky
Quoted 40 lines · Dave Marchevsky

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
=============

[...]

Quoted 26 lines

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
=============

[...]

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: ~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

[...]

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
new file mode 100644
index 000000000000..b5e358dee245

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

#4 lore raw
Quoted 119 lines · Andrii Nakryiko
Quoted 40 lines · Dave Marchevsky

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
=============

[...]

Quoted 26 lines

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
=============

[...]

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: ~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

[...]

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 -0
new file mode 100644
index 000000000000..b5e358dee245

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

Quoted 9 lines

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.

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_hashmap and do_lookup_task_storage and 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_lookup flavors 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 benchmark
cache_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

#5 lore raw
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_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
=============

[...]

Quoted 26 lines

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
=============

[...]

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: ~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

[...]

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.

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 -0
new file mode 100644
index 000000000000..b5e358dee245

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

Quoted 9 lines

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.

Quoted 3 lines

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.

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_hashmap and do_lookup_task_storage and 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_lookup flavors 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.

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_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 benchmark
cache_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.

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_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.

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_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.

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