Re: [Patch bpf-next v5 1/3] bpf: introduce timeout hash map

[Daniel Borkmann <daniel@iogearbox.net>]

On 1/27/21 7:00 PM, Alexei Starovoitov wrote:
> On Tue, Jan 26, 2021 at 11:00 PM Cong Wang <xiyou.wangcong@gmail.com> wrote:
>>>>                ret = PTR_ERR(l_new);
>>>> +             if (ret == -EAGAIN) {
>>>> +                     htab_unlock_bucket(htab, b, hash, flags);
>>>> +                     htab_gc_elem(htab, l_old);
>>>> +                     mod_delayed_work(system_unbound_wq, &htab->gc_work, 0);
>>>> +                     goto again;
>>>
>>> Also this one looks rather worrying, so the BPF prog is stalled here, loop-waiting
>>> in (e.g. XDP) hot path for system_unbound_wq to kick in to make forward progress?
>>
>> In this case, the old one is scheduled for removal in GC, we just wait for GC
>> to finally remove it. It won't stall unless GC itself or the worker scheduler is
>> wrong, both of which should be kernel bugs.
>>
>> If we don't do this, users would get a -E2BIG when it is not too big. I don't
>> know a better way to handle this sad situation, maybe returning -EBUSY
>> to users and let them call again?
> 
> I think using wq for timers is a non-starter.
> Tying a hash/lru map with a timer is not a good idea either.

Thinking some more, given we have jiffies64 helper and atomic ops for BPF by now,
we would technically only need the ability to delete entries via bpf iter progs
(d6c4503cc296 ("bpf: Implement bpf iterator for hash maps")) which could then be
kicked off from user space at e.g. dynamic intervals which would be the equivalent
for the wq in here. That patch could then be implemented this way. I presume
the ability to delete map entries from bpf iter progs would be generic and useful
enough anyway.

> I think timers have to be done as independent objects similar to
> how the kernel uses them.
> Then there will be no question whether lru or hash map needs it.
> The bpf prog author will be able to use timers with either.
> The prog will be able to use timers without hash maps too.
> 
> I'm proposing a timer map where each object will go through
> bpf_timer_setup(timer, callback, flags);
> where "callback" is a bpf subprogram.
> Corresponding bpf_del_timer and bpf_mod_timer would work the same way
> they are in the kernel.
> The tricky part is kernel style of using from_timer() to access the
> object with additional info.

Would this mean N timer objs for N map elems? I presume not given this could be
racy and would have huge extra mem overhead. Either way, timer obj could work, but
then at the same time you could probably also solve it with the above; it's not
like you need the timer to kick in at some /exact/ time, but rather at some point
to clean up stale entries before the map gets full and worst case refuses updates
for new entries. (In the ideal case though we wouldn't need the extra effort to
search deeply for elements w/o penalizing the fast-path lookup costs too much when
walking the bucket.)

> I think bpf timer map can model it the same way.
> At map creation time the value_size will specify the amount of extra
> bytes necessary.
> Another alternative is to pass an extra data argument to a callback.