Re: [PATCH v7 bpf-next 0/3] Add lookup_and_delete_elem support to BPF hash map types

[Denis Salopek <denis.salopek@sartura.hr>]

On Tue, Jul 27, 2021 at 11:10:12AM -0700, Andrii Nakryiko wrote:
> On Mon, May 24, 2021 at 3:02 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Tue, May 11, 2021 at 2:01 PM Denis Salopek <denis.salopek@sartura.hr> wrote:
> > >
> > > This patch series extends the existing bpf_map_lookup_and_delete_elem()
> > > functionality with 4 more map types:
> > >  - BPF_MAP_TYPE_HASH,
> > >  - BPF_MAP_TYPE_PERCPU_HASH,
> > >  - BPF_MAP_TYPE_LRU_HASH and
> > >  - BPF_MAP_TYPE_LRU_PERCPU_HASH.
> > >
> > > Patch 1 adds most of its functionality and logic as well as
> > > documentation.
> > >
> > > As it was previously limited to only stacks and queues which do not
> > > support the BPF_F_LOCK flag, patch 2 enables its usage by adding a new
> > > libbpf API bpf_map_lookup_and_delete_elem_flags() based on the existing
> > > bpf_map_lookup_elem_flags().
> > >
> > > Patch 3 adds selftests for lookup_and_delete_elem().
> > >
> > > Changes in patch 1:
> > > v7: Minor formating nits, add Acked-by.
> > > v6: Remove unneeded flag check, minor code/format fixes.
> > > v5: Split patch to 3 patches. Extend BPF_MAP_LOOKUP_AND_DELETE_ELEM
> > > documentation with this changes.
> > > v4: Fix the return value for unsupported map types.
> > > v3: Add bpf_map_lookup_and_delete_elem_flags() and enable BPF_F_LOCK
> > > flag, change CHECKs to ASSERT_OKs, initialize variables to 0.
> > > v2: Add functionality for LRU/per-CPU, add test_progs tests.
> > >
> > > Changes in patch 2:
> > > v7: No change.
> > > v6: Add Acked-by.
> > > v5: Move to the newest libbpf version (0.4.0).
> > >
> > > Changes in patch 3:
> > > v7: Remove ASSERT_GE macro which is already added in some other commit,
> > > change ASSERT_OK to ASSERT_OK_PTR, add Acked-by.
> > > v6: Remove PERCPU macros, add ASSERT_GE macro to test_progs.h, remove
> > > leftover code.
> > > v5: Use more appropriate macros. Better check for changed value.
> > >
> > > Denis Salopek (3):
> > >   bpf: add lookup_and_delete_elem support to hashtab
> > >   bpf: extend libbpf with bpf_map_lookup_and_delete_elem_flags
> > >   selftests/bpf: add bpf_lookup_and_delete_elem tests
> > >
> 
> Hey Denis,
> 
> I've noticed a new failure for the tests you added:
> 
> setup_prog:PASS:test_lookup_and_delete__open 0 nsec
> setup_prog:PASS:bpf_map__set_type 0 nsec
> setup_prog:PASS:bpf_map__set_max_entries 0 nsec
> setup_prog:PASS:test_lookup_and_delete__load 0 nsec
> setup_prog:PASS:bpf_map__fd 0 nsec
> test_lookup_and_delete_lru_hash:PASS:setup_prog 0 nsec
> fill_values:PASS:bpf_map_update_elem 0 nsec
> fill_values:PASS:bpf_map_update_elem 0 nsec
> test_lookup_and_delete_lru_hash:PASS:fill_values 0 nsec
> trigger_tp:PASS:test_lookup_and_delete__attach 0 nsec
> test_lookup_and_delete_lru_hash:PASS:trigger_tp 0 nsec
> test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
> test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_and_delete_elem 0 nsec
> test_lookup_and_delete_lru_hash:PASS:bpf_map_lookup_elem 0 nsec
> test_lookup_and_delete_lru_hash:FAIL:bpf_map_lookup_elem unexpected success: 0
> #67/3 lookup_and_delete_lru:FAIL
> 
> I haven't seen this before, probably some timing assumptions or
> something. Can you please check and see if there is anything we can do
> to make the test more reliable?
> 
> See https://app.travis-ci.com/github/kernel-patches/bpf/builds/233733889
> for the complete test run log. Thanks!

Hello Andrii,

I figured the LRU tests would go like this:
1. We create LRU hash map with 2 elements.
2. We fill both of those elements with a default value (1234) at keys 1
and 2.
3. We trigger the outside BPF program that sets the element at key 3 to
a new value (4321). My initial presumption was that since the map is
full, the new element will cause the 'oldest' one (key = 1) to be
deleted and add the new one, leaving only keys 2 and 3 in the map.
4. We lookup_and_delete the newly added element at key = 3 (so only key
= 2 remains in the map).
5. We check whether key = 3 exists in the map -> it shouldn't and it
doesn't.
6. We check whether key = 1 exists in the map -> it shouldn't, but it
does.

So, the LRU test fails at the last check.

The lookup_and_deleted element at key = 3 is really deleted, as the test
gives us PASS (one line before FAIL), and as that is the point of this
test, I guess we can just skip the last check for the deleted LRU
element?

The LRU_PERCPU test (which passes, by the way) does the same thing as
the LRU test, so we can make the same changes on both of them, if you
agree with the above.

Kind regards,
Denis

> 
> 
> > >  include/linux/bpf.h                           |   2 +
> > >  include/uapi/linux/bpf.h                      |  13 +
> > >  kernel/bpf/hashtab.c                          |  98 ++++++
> > >  kernel/bpf/syscall.c                          |  34 ++-
> > >  tools/include/uapi/linux/bpf.h                |  13 +
> > >  tools/lib/bpf/bpf.c                           |  13 +
> > >  tools/lib/bpf/bpf.h                           |   2 +
> > >  tools/lib/bpf/libbpf.map                      |   1 +
> > >  .../bpf/prog_tests/lookup_and_delete.c        | 288 ++++++++++++++++++
> > >  .../bpf/progs/test_lookup_and_delete.c        |  26 ++
> > >  tools/testing/selftests/bpf/test_lru_map.c    |   8 +
> > >  tools/testing/selftests/bpf/test_maps.c       |  17 ++
> > >  12 files changed, 511 insertions(+), 4 deletions(-)
> > >  create mode 100644 tools/testing/selftests/bpf/prog_tests/lookup_and_delete.c
> > >  create mode 100644 tools/testing/selftests/bpf/progs/test_lookup_and_delete.c
> > >
> > > --
> > > 2.26.2
> > >
> >
> > Patchbot is having a bad day...
> >
> > Applied to bpf-next, thanks. Fixed up a small merge conflict in libbpf.map.