On 2/17/21 10:18 AM, Yonghong Song wrote:
This patch set introduced bpf_for_each_map_elem() helper.
The helper permits bpf program iterates through all elements
for a particular map.
The work originally inspired by an internal discussion where
firewall rules are kept in a map and bpf prog wants to
check packet 5 tuples against all rules in the map.
A bounded loop can be used but it has a few drawbacks.
As the loop iteration goes up, verification time goes up too.
For really large maps, verification may fail.
A helper which abstracts out the loop itself will not have
verification time issue.
A recent discussion in [1] involves to iterate all hash map
elements in bpf program. Currently iterating all hashmap elements
in bpf program is not easy if key space is really big.
Having a helper to abstract out the loop itself is even more
meaningful.
The proposed helper signature looks like:
long bpf_for_each_map_elem(map, callback_fn, callback_ctx, flags)
where callback_fn is a static function and callback_ctx is
a piece of data allocated on the caller stack which can be
accessed by the callback_fn. The callback_fn signature might be
different for different maps. For example, for hash/array maps,
the signature is
long callback_fn(map, key, val, callback_ctx)
In the rest of series, Patches 1/2/3 did some refactoring. Patch 4
implemented core kernel support for the helper. Patches 5 and 6
added hashmap and arraymap support. Patches 7/8 added libbpf
support. Patch 9 added bpftool support. Patches 10 and 11 added
selftests for hashmap and arraymap.
[1]: https://lore.kernel.org/bpf/20210122205415.113822-1-xiyou.wangcong@xxxxxxxxx/
I missed changelog from v1 to v2 and here it is.
Changelogs:
v1 -> v2:
- setup callee frame in check_helper_call() and then proceed to verify
helper return value as normal (Alexei)
- use meta data to keep track of map/func pointer to avoid hard coding
the register number (Alexei)
- verify callback_fn return value range [0, 1]. (Alexei)
- add migrate_{disable, enable} to ensure percpu value is the one
bpf program expects to see. (Alexei)
- change bpf_for_each_map_elem() return value to the number of iterated
elements. (Andrii)
- Change libbpf pseudo_func relo name to RELO_SUBPROG_ADDR and use
more rigid checking for the relocation. (Andrii)
- Better format to print out subprog address with bpftool. (Andrii)
- Use bpf_prog_test_run to trigger bpf run, instead of bpf_iter.
(Andrii)
- Other misc changes.
Yonghong Song (11):
bpf: factor out visit_func_call_insn() in check_cfg()
bpf: factor out verbose_invalid_scalar()
bpf: refactor check_func_call() to allow callback function
bpf: add bpf_for_each_map_elem() helper
bpf: add hashtab support for bpf_for_each_map_elem() helper
bpf: add arraymap support for bpf_for_each_map_elem() helper
libbpf: move function is_ldimm64() earlier in libbpf.c
libbpf: support local function pointer relocation
bpftool: print local function pointer properly
selftests/bpf: add hashmap test for bpf_for_each_map_elem() helper
selftests/bpf: add arraymap test for bpf_for_each_map_elem() helper
include/linux/bpf.h | 17 +
include/linux/bpf_verifier.h | 3 +
include/uapi/linux/bpf.h | 29 +-
kernel/bpf/arraymap.c | 39 ++
kernel/bpf/bpf_iter.c | 16 +
kernel/bpf/hashtab.c | 63 ++++
kernel/bpf/helpers.c | 2 +
kernel/bpf/verifier.c | 346 +++++++++++++++---
kernel/trace/bpf_trace.c | 2 +
tools/bpf/bpftool/xlated_dumper.c | 3 +
tools/include/uapi/linux/bpf.h | 29 +-
tools/lib/bpf/libbpf.c | 52 ++-
.../selftests/bpf/prog_tests/for_each.c | 132 +++++++
.../bpf/progs/for_each_array_map_elem.c | 61 +++
.../bpf/progs/for_each_hash_map_elem.c | 95 +++++
15 files changed, 829 insertions(+), 60 deletions(-)
create mode 100644 tools/testing/selftests/bpf/prog_tests/for_each.c
create mode 100644 tools/testing/selftests/bpf/progs/for_each_array_map_elem.c
create mode 100644 tools/testing/selftests/bpf/progs/for_each_hash_map_elem.c
