On Apr 6, 2021, at 9:48 AM, Cong Wang [off-list ref] wrote:

On Mon, Apr 5, 2021 at 11:18 PM Song Liu [off-list ref] wrote:

quoted

quoted

On Apr 5, 2021, at 6:24 PM, Cong Wang [off-list ref] wrote:

On Mon, Apr 5, 2021 at 6:08 PM Song Liu [off-list ref] wrote:

quoted

quoted

On Apr 5, 2021, at 4:49 PM, Cong Wang [off-list ref] wrote:

On Fri, Apr 2, 2021 at 4:31 PM Song Liu [off-list ref] wrote:

quoted

quoted

On Apr 2, 2021, at 1:57 PM, Cong Wang [off-list ref] wrote:

Ideally I even prefer to create timers in kernel-space too, but as I already
explained, this seems impossible to me.

Would hrtimer (include/linux/hrtimer.h) work?

By impossible, I meant it is impossible (to me) to take a refcnt to the callback
prog if we create the timer in kernel-space. So, hrtimer is the same in this
perspective.

Thanks.

I guess I am not following 100%. Here is what I would propose:

We only introduce a new program type BPF_PROG_TYPE_TIMER. No new map type.
The new program will trigger based on a timer, and the program can somehow
control the period of the timer (for example, via return value).

Like we already discussed, with this approach the "timer" itself is not
visible to kernel, that is, only manageable in user-space. Or do you disagree?

Do you mean we need mechanisms to control the timer, like stop the timer,
trigger the timer immediately, etc.? And we need these mechanisms in kernel?
And by "in kernel-space" I assume you mean from BPF programs.

Yes, of course. In the context of our discussion, kernel-space only means
eBPF code running in kernel-space. And like I showed in pseudo code,
we want to manage the timer in eBPF code too, that is, updating timer
expiration time and even deleting a timer. The point is we want to give
users as much flexibility as possible, so that they can use it in whatever
scenarios they want. We do not decide how they use them, they do.

quoted

If these are correct, how about something like:

1. A new program BPF_PROG_TYPE_TIMER, which by default will trigger on a timer.
  Note that, the timer here is embedded in the program. So all the operations
  are on the program.
2. Allow adding such BPF_PROG_TYPE_TIMER programs to a map of type
  BPF_MAP_TYPE_PROG_ARRAY.
3. Some new helpers that access the program via the BPF_MAP_TYPE_PROG_ARRAY map.
  Actually, maybe we can reuse existing bpf_tail_call().

Reusing bpf_tail_call() just for timer sounds even crazier than
my current approach. So... what's the advantage of your approach
compared to mine?

Since I don't know much about conntrack, I don't know which is better. 
The follow is just my thoughts based on the example you showed. It is 
likely that I misunderstand something. 

IIUC, the problem with user space timer is that we need a dedicated task 
for each wait-trigger loop. So I am proposing a BPF program that would
trigger up on timer expiration. 

The advantage (I think) is to not introduce a separate timer entity. 
The timer is bundled with the program.  

quoted

The BPF program and map will look like:

==================== 8< ==========================
struct data_elem {
       __u64 expiration;
       /* other data */
};

So, expiration is separated from "timer" itself. Naturally, expiration
belongs to the timer itself.

In this example, expiration is not related to the timer. It is just part
of the data element. It is possible that we won't need the expiration for 
some use cases. 

quoted

struct {
       __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
       __uint(max_entries, 256);
       __type(key, __u32);
       __type(value, struct data_elem);
} data_map SEC(".maps");

struct {
       __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
       __uint(max_entries, 256);
       __type(key, __u32);
       __type(value, __u64);
} timer_prog_map SEC(".maps");

So, users have to use two maps just for a timer. Looks unnecessarily
complex to me.

The data_map is not for the timer program, it is for the actual data. 
timer_prog_map is also optional here. We only need it when we want to 
trigger the program sooner than the scheduled time. If we can wait a
little longer, timer_prog_map can also be removed.

quoted

static __u64
check_expired_elem(struct bpf_map *map, __u32 *key, __u64 *val,
                int *data)
{
       u64 expires = *val;

       if (expires < bpf_jiffies64()) {

Value is a 64-bit 'expiration', so it is not atomic to read/write it on 32bit
CPU. And user-space could update it in parallel to this timer callback.
So basically we have to use a bpf spinlock here.

quoted

               bpf_map_delete_elem(map, key);
               *data++;
       }
return 0;
}

SEC("timer")
int clean_up_timer(void)
{
       int count;

       bpf_for_each_map_elem(&data_map, check_expired_elem, &count, 0);
       if (count)
               return 0; // not re-arm this timer
       else
               return 10; // reschedule this timer after 10 jiffies
}

SEC("tp_btf/XXX")
int another_trigger(void)
{
       if (some_condition)
               bpf_tail_call(NULL, &timer_prog_map, idx);

Are you sure you can use bpf_tail_call() to call a prog asynchronously?

I am not sure that we gonna use bpf_tail_call() here. If necessary, we 
can introduce a new helper. 


I am not sure whether this makes sense. I feel there is still some 
misunderstanding. It will be helpful if you can share more information 
about the overall design. 

BTW: this could be a good topic for the BPF office hour. See more details
here:

https://docs.google.com/spreadsheets/d/1LfrDXZ9-fdhvPEp_LHkxAMYyxxpwBXjywWa0AejEveU/edit#gid=0

Thanks,
Song