bpf/progs/timer.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /* Copyright (c) 2021 Facebook */
0003 #include <linux/bpf.h>
0004 #include <time.h>
0005 #include <errno.h>
0006 #include <bpf/bpf_helpers.h>
0007 #include "bpf_tcp_helpers.h"
0008
0009 char _license[] SEC("license") = "GPL";
0010 struct hmap_elem {
0011     int counter;
0012     struct bpf_timer timer;
0013     struct bpf_spin_lock lock; /* unused */
0014 };
0015
0016 struct {
0017     __uint(type, BPF_MAP_TYPE_HASH);
0018     __uint(max_entries, 1000);
0019     __type(key, int);
0020     __type(value, struct hmap_elem);
0021 } hmap SEC(".maps");
0022
0023 struct {
0024     __uint(type, BPF_MAP_TYPE_HASH);
0025     __uint(map_flags, BPF_F_NO_PREALLOC);
0026     __uint(max_entries, 1000);
0027     __type(key, int);
0028     __type(value, struct hmap_elem);
0029 } hmap_malloc SEC(".maps");
0030
0031 struct elem {
0032     struct bpf_timer t;
0033 };
0034
0035 struct {
0036     __uint(type, BPF_MAP_TYPE_ARRAY);
0037     __uint(max_entries, 2);
0038     __type(key, int);
0039     __type(value, struct elem);
0040 } array SEC(".maps");
0041
0042 struct {
0043     __uint(type, BPF_MAP_TYPE_LRU_HASH);
0044     __uint(max_entries, 4);
0045     __type(key, int);
0046     __type(value, struct elem);
0047 } lru SEC(".maps");
0048
0049 __u64 bss_data;
0050 __u64 err;
0051 __u64 ok;
0052 __u64 callback_check = 52;
0053 __u64 callback2_check = 52;
0054
0055 #define ARRAY 1
0056 #define HTAB 2
0057 #define HTAB_MALLOC 3
0058 #define LRU 4
0059
0060 /* callback for array and lru timers */
0061 static int timer_cb1(void *map, int *key, struct bpf_timer *timer)
0062 {
0063     /* increment bss variable twice.
0064      * Once via array timer callback and once via lru timer callback
0065      */
0066     bss_data += 5;
0067
0068     /* *key == 0 - the callback was called for array timer.
0069      * *key == 4 - the callback was called from lru timer.
0070      */
0071     if (*key == ARRAY) {
0072         struct bpf_timer *lru_timer;
0073         int lru_key = LRU;
0074
0075         /* rearm array timer to be called again in ~35 seconds */
0076         if (bpf_timer_start(timer, 1ull << 35, 0) != 0)
0077             err |= 1;
0078
0079         lru_timer = bpf_map_lookup_elem(&lru, &lru_key);
0080         if (!lru_timer)
0081             return 0;
0082         bpf_timer_set_callback(lru_timer, timer_cb1);
0083         if (bpf_timer_start(lru_timer, 0, 0) != 0)
0084             err |= 2;
0085     } else if (*key == LRU) {
0086         int lru_key, i;
0087
0088         for (i = LRU + 1;
0089              i <= 100  /* for current LRU eviction algorithm this number
0090                 * should be larger than ~ lru->max_entries * 2
0091                 */;
0092              i++) {
0093             struct elem init = {};
0094
0095             /* lru_key cannot be used as loop induction variable
0096              * otherwise the loop will be unbounded.
0097              */
0098             lru_key = i;
0099
0100             /* add more elements into lru map to push out current
0101              * element and force deletion of this timer
0102              */
0103             bpf_map_update_elem(map, &lru_key, &init, 0);
0104             /* look it up to bump it into active list */
0105             bpf_map_lookup_elem(map, &lru_key);
0106
0107             /* keep adding until *key changes underneath,
0108              * which means that key/timer memory was reused
0109              */
0110             if (*key != LRU)
0111                 break;
0112         }
0113
0114         /* check that the timer was removed */
0115         if (bpf_timer_cancel(timer) != -EINVAL)
0116             err |= 4;
0117         ok |= 1;
0118     }
0119     return 0;
0120 }
0121
0122 SEC("fentry/bpf_fentry_test1")
0123 int BPF_PROG(test1, int a)
0124 {
0125     struct bpf_timer *arr_timer, *lru_timer;
0126     struct elem init = {};
0127     int lru_key = LRU;
0128     int array_key = ARRAY;
0129
0130     arr_timer = bpf_map_lookup_elem(&array, &array_key);
0131     if (!arr_timer)
0132         return 0;
0133     bpf_timer_init(arr_timer, &array, CLOCK_MONOTONIC);
0134
0135     bpf_map_update_elem(&lru, &lru_key, &init, 0);
0136     lru_timer = bpf_map_lookup_elem(&lru, &lru_key);
0137     if (!lru_timer)
0138         return 0;
0139     bpf_timer_init(lru_timer, &lru, CLOCK_MONOTONIC);
0140
0141     bpf_timer_set_callback(arr_timer, timer_cb1);
0142     bpf_timer_start(arr_timer, 0 /* call timer_cb1 asap */, 0);
0143
0144     /* init more timers to check that array destruction
0145      * doesn't leak timer memory.
0146      */
0147     array_key = 0;
0148     arr_timer = bpf_map_lookup_elem(&array, &array_key);
0149     if (!arr_timer)
0150         return 0;
0151     bpf_timer_init(arr_timer, &array, CLOCK_MONOTONIC);
0152     return 0;
0153 }
0154
0155 /* callback for prealloc and non-prealloca hashtab timers */
0156 static int timer_cb2(void *map, int *key, struct hmap_elem *val)
0157 {
0158     if (*key == HTAB)
0159         callback_check--;
0160     else
0161         callback2_check--;
0162     if (val->counter > 0 && --val->counter) {
0163         /* re-arm the timer again to execute after 1 usec */
0164         bpf_timer_start(&val->timer, 1000, 0);
0165     } else if (*key == HTAB) {
0166         struct bpf_timer *arr_timer;
0167         int array_key = ARRAY;
0168
0169         /* cancel arr_timer otherwise bpf_fentry_test1 prog
0170          * will stay alive forever.
0171          */
0172         arr_timer = bpf_map_lookup_elem(&array, &array_key);
0173         if (!arr_timer)
0174             return 0;
0175         if (bpf_timer_cancel(arr_timer) != 1)
0176             /* bpf_timer_cancel should return 1 to indicate
0177              * that arr_timer was active at this time
0178              */
0179             err |= 8;
0180
0181         /* try to cancel ourself. It shouldn't deadlock. */
0182         if (bpf_timer_cancel(&val->timer) != -EDEADLK)
0183             err |= 16;
0184
0185         /* delete this key and this timer anyway.
0186          * It shouldn't deadlock either.
0187          */
0188         bpf_map_delete_elem(map, key);
0189
0190         /* in preallocated hashmap both 'key' and 'val' could have been
0191          * reused to store another map element (like in LRU above),
0192          * but in controlled test environment the below test works.
0193          * It's not a use-after-free. The memory is owned by the map.
0194          */
0195         if (bpf_timer_start(&val->timer, 1000, 0) != -EINVAL)
0196             err |= 32;
0197         ok |= 2;
0198     } else {
0199         if (*key != HTAB_MALLOC)
0200             err |= 64;
0201
0202         /* try to cancel ourself. It shouldn't deadlock. */
0203         if (bpf_timer_cancel(&val->timer) != -EDEADLK)
0204             err |= 128;
0205
0206         /* delete this key and this timer anyway.
0207          * It shouldn't deadlock either.
0208          */
0209         bpf_map_delete_elem(map, key);
0210
0211         /* in non-preallocated hashmap both 'key' and 'val' are RCU
0212          * protected and still valid though this element was deleted
0213          * from the map. Arm this timer for ~35 seconds. When callback
0214          * finishes the call_rcu will invoke:
0215          * htab_elem_free_rcu
0216          *   check_and_free_timer
0217          *     bpf_timer_cancel_and_free
0218          * to cancel this 35 second sleep and delete the timer for real.
0219          */
0220         if (bpf_timer_start(&val->timer, 1ull << 35, 0) != 0)
0221             err |= 256;
0222         ok |= 4;
0223     }
0224     return 0;
0225 }
0226
0227 int bpf_timer_test(void)
0228 {
0229     struct hmap_elem *val;
0230     int key = HTAB, key_malloc = HTAB_MALLOC;
0231
0232     val = bpf_map_lookup_elem(&hmap, &key);
0233     if (val) {
0234         if (bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME) != 0)
0235             err |= 512;
0236         bpf_timer_set_callback(&val->timer, timer_cb2);
0237         bpf_timer_start(&val->timer, 1000, 0);
0238     }
0239     val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc);
0240     if (val) {
0241         if (bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME) != 0)
0242             err |= 1024;
0243         bpf_timer_set_callback(&val->timer, timer_cb2);
0244         bpf_timer_start(&val->timer, 1000, 0);
0245     }
0246     return 0;
0247 }
0248
0249 SEC("fentry/bpf_fentry_test2")
0250 int BPF_PROG(test2, int a, int b)
0251 {
0252     struct hmap_elem init = {}, *val;
0253     int key = HTAB, key_malloc = HTAB_MALLOC;
0254
0255     init.counter = 10; /* number of times to trigger timer_cb2 */
0256     bpf_map_update_elem(&hmap, &key, &init, 0);
0257     val = bpf_map_lookup_elem(&hmap, &key);
0258     if (val)
0259         bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME);
0260     /* update the same key to free the timer */
0261     bpf_map_update_elem(&hmap, &key, &init, 0);
0262
0263     bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0);
0264     val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc);
0265     if (val)
0266         bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME);
0267     /* update the same key to free the timer */
0268     bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0);
0269
0270     /* init more timers to check that htab operations
0271      * don't leak timer memory.
0272      */
0273     key = 0;
0274     bpf_map_update_elem(&hmap, &key, &init, 0);
0275     val = bpf_map_lookup_elem(&hmap, &key);
0276     if (val)
0277         bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME);
0278     bpf_map_delete_elem(&hmap, &key);
0279     bpf_map_update_elem(&hmap, &key, &init, 0);
0280     val = bpf_map_lookup_elem(&hmap, &key);
0281     if (val)
0282         bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME);
0283
0284     /* and with non-prealloc htab */
0285     key_malloc = 0;
0286     bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0);
0287     val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc);
0288     if (val)
0289         bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME);
0290     bpf_map_delete_elem(&hmap_malloc, &key_malloc);
0291     bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0);
0292     val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc);
0293     if (val)
0294         bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME);
0295
0296     return bpf_timer_test();
0297 }