Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
MIME-Version: 1.0
References: <20230312190600.324573-1-joe@isovalent.com> <c6172fe2-7d88-f9f8-e19a-47c232f9cb75@linux.dev>
 <CADa=RyxDHp5x0iCcfgiCDuM68we=dTAmVBvx1hgrRLBbN27rdw@mail.gmail.com> <f015a098-1e17-b503-a098-b3d1adbe4ce8@linux.dev>
In-Reply-To: <f015a098-1e17-b503-a098-b3d1adbe4ce8@linux.dev>
From:   Joe Stringer <joe@isovalent.com>
Date:   Sat, 1 Apr 2023 11:57:27 -0700
Message-ID: <CADa=RywTEdbTdHHi=Qh6MRrHRUDUKZfPGU---Ea+-RF7+t+o+A@mail.gmail.com>
Subject: Re: [PATCH bpf-next v3] docs/bpf: Add LRU internals description and graph
To:     Martin KaFai Lau <martin.lau@linux.dev>
Cc:     linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org,
        ast@kernel.org, corbet@lwn.net, bagasdotme@gmail.com,
        maxtram95@gmail.com, bpf@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Thu, Mar 16, 2023 at 11:05=E2=80=AFPM Martin KaFai Lau <martin.lau@linux=
.dev> wrote:
>
> On 3/15/23 6:54 PM, Joe Stringer wrote:
> > On Tue, Mar 14, 2023 at 12:31=E2=80=AFPM Martin KaFai Lau <martin.lau@l=
inux.dev> wrote:
> >>
> >> 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...
>
> shrink should try to shrink a couple of stale elems which are likely hash=
ed to
> different buckets. If shrink hits htab_lock_bucket() EBUSY on all stale e=
lems,
> shrink could fail but unlikely.

The failure case I had in mind for this is to assume that shrinking
succeeds and we find an LRU node during the htab_map_update_elem()
call through prealloc_lru_pop(), but then immediately afterwards it
makes a direct htab_lock_bucket() call which has just one chance to
succeed based on whether this CPU races against some other user of the
bucket lock. Still seems somewhat rare, but feasible to hit.

> > Could there be a case something like "userspace process is touching tha=
t bucket,
> > gets interrupted, then the same CPU runs an eBPF program that attempts =
to
> > update/delete elements in the same bucket"?
>
> raw_spin_lock_irqsave() is done after the percpu counter, so there is a g=
ap but
> not sure if it matters though unless the production use case can really h=
it it.

Yeah unfortunately I'm going off an incident from last year and I
don't have this level of visibility into the failure scenario in a
prod-like environment today.