netdev - Re: [RFC Patch bpf-next] bpf: introduce bpf timer

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <45B3E744-000D-4958-89C0-A5E83959CD4A@fb.com>
Date:   Tue, 6 Apr 2021 06:17:55 +0000
From:   Song Liu <songliubraving@...com>
To:     Cong Wang <xiyou.wangcong@...il.com>
CC:     "open list:BPF (Safe dynamic programs and tools)" 
        <netdev@...r.kernel.org>,
        "open list:BPF (Safe dynamic programs and tools)" 
        <bpf@...r.kernel.org>,
        "duanxiongchun@...edance.com" <duanxiongchun@...edance.com>,
        "wangdongdong.6@...edance.com" <wangdongdong.6@...edance.com>,
        Muchun Song <songmuchun@...edance.com>,
        "Cong Wang" <cong.wang@...edance.com>,
        Alexei Starovoitov <ast@...nel.org>,
        "Daniel Borkmann" <daniel@...earbox.net>,
        Andrii Nakryiko <andrii@...nel.org>,
        "Martin Lau" <kafai@...com>, Yonghong Song <yhs@...com>
Subject: Re: [RFC Patch bpf-next] bpf: introduce bpf timer



> On Apr 5, 2021, at 6:24 PM, Cong Wang <xiyou.wangcong@...il.com> wrote:
> 
> On Mon, Apr 5, 2021 at 6:08 PM Song Liu <songliubraving@...com> wrote:
>> 
>> 
>> 
>>> On Apr 5, 2021, at 4:49 PM, Cong Wang <xiyou.wangcong@...il.com> wrote:
>>> 
>>> On Fri, Apr 2, 2021 at 4:31 PM Song Liu <songliubraving@...com> wrote:
>>>> 
>>>> 
>>>> 
>>>>> On Apr 2, 2021, at 1:57 PM, Cong Wang <xiyou.wangcong@...il.com> 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. 

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(). 

The BPF program and map will look like:

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

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");

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

	if (expires < bpf_jiffies64()) {
		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);
	return 0;
}

==================== 8< ==========================

Would something like this work for contract?

Thanks,
Song

> 
>> 
>> With this approach, the user simply can create multiple timer programs and
>> hold the fd for them. And these programs trigger up to timer expiration.
> 
> Sure, this is precisely why I moved timer creation to user-space to solve
> the refcnt issue. ;)
> 
>> 
>> Does this make sense?
> 
> Yes, except kernel-space code can't see it. If you look at the timeout map
> I had, you will see something like this:
> 
> val = lookup(map, key);
> if (val && val->expires < now)
>   rearm_timer(&timer); // the timer periodically scans the hashmap
> 
> For conntrack, this is obviously in kernel-space. The point of the code is to
> flush all expired items as soon as possible without doing explicit deletions
> which are obviously expensive for the fast path.
> 
> Thanks.