Date:   Wed, 26 May 2021 11:34:04 -0400
From:   Jamal Hadi Salim <jhs@...atatu.com>
To:     Alexei Starovoitov <alexei.starovoitov@...il.com>
Cc:     Cong Wang <xiyou.wangcong@...il.com>,
        David Miller <davem@...emloft.net>,
        Daniel Borkmann <daniel@...earbox.net>,
        Andrii Nakryiko <andrii@...nel.org>,
        John Fastabend <john.fastabend@...il.com>,
        Lorenz Bauer <lmb@...udflare.com>,
        Linux Kernel Network Developers <netdev@...r.kernel.org>,
        bpf <bpf@...r.kernel.org>, kernel-team <kernel-team@...com>,
        Pedro Tammela <pctammela@...il.com>
Subject: Re: [RFC PATCH bpf-next] bpf: Introduce bpf_timer

On 2021-05-25 6:08 p.m., Alexei Starovoitov wrote:
> On Tue, May 25, 2021 at 2:09 PM Jamal Hadi Salim <jhs@...atatu.com> wrote:
>>

>> This is certainly a useful feature (for other reasons as well).
>> Does this include create/update/delete issued from user space?
> 
> Right. Any kind of update/delete and create is a subset of update.
> The lookup is not included (yet or may be ever) since it doesn't
> have deterministic start/end points.
> The prog can do a lookup and update values in place while
> holding on the element until prog execution ends.
> 
> While update/delete have precise points in hash/lru/lpm maps.
> Array is a different story.
> 

Didnt follow why this wouldnt work in the same way for Array?

One interesting concept i see come out of this is emulating
netlink-like event generation towards user space i.e a user
space app listening to changes to a map.

>>
>> The challenge we have in this case is LRU makes the decision
>> which entry to victimize. We do have some entries we want to
>> keep longer - even if they are not seeing a lot of activity.
> 
> Right. That's certainly an argument to make LRU eviction
> logic programmable.
> John/Joe/Daniel proposed it as a concept long ago.
> Design ideas are in demand to make further progress here :)
> 

would like to hear what the proposed ideas are.
I see this as a tricky problem to solve - you can make LRU
programmable to allow the variety of LRU replacement algos out
there but not all encompansing for custom or other types of algos.
The problem remains that LRU is very specific to evicting
entries that are least used. I can imagine that if i wanted to
do a LIFO aging for example then it can be done with some acrobatics
as an overlay on top of LRU with all sorts of tweaking.
It is sort of fitting a square peg into a round hole - you can do
it, but why the torture when you have a flexible architecture.

We need to provide the mechanisms (I dont see a disagreement on
need for timers at least).

>> You could just notify user space to re-add the entry but then
>> you have sync challenges.
>> The timers do provide us a way to implement custom GC.
> 
> My point is that time is always going to be a heuristic that will
> break under certain traffic conditions.
> I recommend to focus development effort on creating
> building blocks that are truly great instead of reimplementing
> old ideas in bpf with all of their shortcomings.
> 

There are some basic mechanisms i dont think that we can avoid.
Agreed on the general sentiment of what you are saying.

>> So a question (which may have already been discussed),
>> assuming the following setup:
>> - 2 programs a) Ingress b) egress
>> - sharing a conntrack map which and said map pinned.
>> - a timer prog (with a map with just timers;
>>      even a single timer would be enough in some cases).
>>
>> ingress and egress do std stuff like create/update
>> timer prog does the deletes. For simplicity sake assume
>> we just have one timer that does a foreach and iterates
>> all entries.
>>
>> What happens when both ingress and egress are ejected?
> 
> What is 'ejected'? Like a CD? ;)

I was going to use other verbs to describe this; but
may have sounded obscene ;->

> I think you mean 'detached' ?

Yes.

> and then, I assume, the user space doesn't hold to prog FD?

Right. The pinning may still exist on the maps (therefore a ref
count). Note, this may be design intent.

> The kernel can choose to do different things with the timer here.
> One option is to cancel the outstanding timers and unload
> .text where the timer callback lives
 >
> Another option is to let the timer stay armed and auto unload
> .text of bpf function when it finishes executing.
 >
> If timer callback decides to re-arm itself it can continue
> executing indefinitely.
> This patch is doing the latter.
> There could be a combination of both options.
> All options have their pros/cons.

A reasonable approach is to let the policy be defined
from user space. I may want the timer to keep polling
a map that is not being updated until the next program
restarts and starts updating it.
I thought Cong's approach with timerids/maps was a good
way to achieve control.

cheers,
jamal

Powered by blists - more mailing lists