Re: [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper

[Yonghong Song <yhs@fb.com>]

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@gmail.com/

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
>