Re: [PATCH bpf-next v3] docs/bpf: Add LRU internals description and graph

[Joe Stringer]

On Tue, Mar 14, 2023 at 12:31 PM Martin KaFai Lau <martin.lau@xxxxxxxxx> wrote:
>
> On 3/12/23 12:05 PM, Joe Stringer wrote:
> > Extend the bpf hashmap docs to include a brief description of the
> > internals of the LRU map type (setting appropriate API expectations),
> > including the original commit message from Martin and a variant on the
> > graph that I had presented during my Linux Plumbers Conference 2022 talk
> > on "Pressure feedback for LRU map types"[0].
> >
> > The node names in the dot file correspond roughly to the functions where
> > the logic for those decisions or steps is defined, to help curious
> > developers to cross-reference and update this logic if the details of
> > the LRU implementation ever differ from this description.
> >
> > [0]: https://lpc.events/event/16/contributions/1368/
> >
> > Signed-off-by: Joe Stringer <joe@xxxxxxxxxxxxx>
> > ---
> > v3: Use standard table syntax
> >      Replace inline commit message with reference to commit
> >      Fix incorrect Y/N label for common LRU check
> >      Rename some dotfile variables to reduce confusion between cases
> >      Minor wording touchups
> > v2: Fix issue that caused initial email submission to fail
> > ---
> >   Documentation/bpf/map_hash.rst            |  62 ++++++++
> >   Documentation/bpf/map_lru_hash_update.dot | 166 ++++++++++++++++++++++
> >   2 files changed, 228 insertions(+)
> >   create mode 100644 Documentation/bpf/map_lru_hash_update.dot
> >
> > diff --git a/Documentation/bpf/map_hash.rst b/Documentation/bpf/map_hash.rst
> > index 8669426264c6..61602ce26561 100644
> > --- a/Documentation/bpf/map_hash.rst
> > +++ b/Documentation/bpf/map_hash.rst
> > @@ -1,5 +1,6 @@
> >   .. SPDX-License-Identifier: GPL-2.0-only
> >   .. Copyright (C) 2022 Red Hat, Inc.
> > +.. Copyright (C) 2022-2023 Isovalent, Inc.
> >
> >   ===============================================
> >   BPF_MAP_TYPE_HASH, with PERCPU and LRU Variants
> > @@ -206,3 +207,64 @@ Userspace walking the map elements from the map declared above:
> >                       cur_key = &next_key;
> >               }
> >       }
> > +
> > +Internals
> > +=========
> > +
> > +This section of the document is targeted at Linux developers and describes
> > +aspects of the map implementations that are not considered stable ABI. The
> > +following details are subject to change in future versions of the kernel.
> > +
> > +``BPF_MAP_TYPE_LRU_HASH`` and variants
> > +--------------------------------------
> > +
> > +An LRU hashmap type consists of two properties: Firstly, it is a hash map and
> > +hence is indexable by key for constant time lookups. Secondly, when at map
> > +capacity, map updates will trigger eviction of old entries based on the age of
> > +the elements in a set of lists. Each of these properties may be either global
> > +or per-CPU, depending on the map type and flags used to create the map:
> > +
> > ++------------------------+---------------------------+----------------------------------+
> > +|                        | ``BPF_MAP_TYPE_LRU_HASH`` | ``BPF_MAP_TYPE_LRU_PERCPU_HASH`` |
> > ++========================+===========================+==================================+
> > +| ``BPF_NO_COMMON_LRU``  | Per-CPU LRU, global map   | Per-CPU LRU, per-cpu map         |
> > ++------------------------+---------------------------+----------------------------------+
> > +| ``!BPF_NO_COMMON_LRU`` | Global LRU, global map    | Global LRU, per-cpu map          |
> > ++------------------------+---------------------------+----------------------------------+
> > +
> > +Notably, there are various steps that the update algorithm attempts in order to
> > +enforce the LRU property which have increasing impacts on other CPUs involved
> > +in the following operation attempts:
> > +
> > +- Attempt to use CPU-local state to batch operations
> > +- Attempt to fetch free nodes from global lists
> > +- Attempt to pull any node from a global list and remove it from the hashmap
> > +- Attempt to pull any node from any CPU's list and remove it from the hashmap
> > +
> > +Even if an LRU node may be acquired, maps of type ``BPF_MAP_TYPE_LRU_HASH``
> > +may fail to insert the entry into the map if other CPUs are heavily contending
> > +on the global hashmap lock.
>
> The global hashmap lock described here is the action taken in htab_lock_bucket()?
>
> It is a percpu counter added in commit 20b6cc34ea74 ("bpf: Avoid hashtab
> deadlock with map_locked") to avoid deadlock/recursion.

Hmm, yes that's the lock I had in mind. Thanks for the pointer, I
didn't really understand the motivation for that case previously. That
said, I now find it even harder to think of reasonable wording to
describe in the ABI about how an eBPF program developer should reason
about the -EBUSY failure case.

> I would suggest to simplify the diagram by removing the "Can lock this hashtab
> bucket?" details.

I could swap that to instead have "Update hashmap with new element",
then have two possible outcomes depending on whether that succeeds or
not. I guess this is also similar to John's feedback above that in the
end, EBUSY return code ends up being ABI for the helper. Does that
make sense? One of my goals for the diagram was to at least capture
the various return codes to assist readers in reasoning about the
different failure modes.

> Maybe a note somewhere to mention why it will still fail to
> shrink the list because the htab_lock_bucket() have detected potential
> deadlock/recursion which is a very unlikely case.

I missed the "shrink the list" link here since it seems like this
could happen for any combination of update or delete elems for the
same bucket. But yeah given that also needs to happen on the same CPU,
it does seem very unlikely... Could there be a case something like
"userspace process is touching that bucket, gets interrupted, then the
same CPU runs an eBPF program that attempts to update/delete elements
in the same bucket"?

Previously I had read this to think that EBUSY was the common case and
ENOMEM is the uncommon case, but based on your pointers above I'm less
convinced now, and more surprised that either failure would occur.
Perhaps the failure I had hit was even later in the regular hashtab
update logic. At the time of the incidents I was investigating, we
unfortunately did not record which of the failure cases occurred so I
don't have specific data to back up what we were experiencing. We have
since added such reporting but I haven't received further information
from the failure mode.