1 // SPDX-License-Identifier: GPL-2.0 2 /* Copyright (c) 2021 Facebook */ 3 #include <linux/bpf.h> 4 #include <time.h> 5 #include <errno.h> 6 #include <bpf/bpf_helpers.h> 7 #include "bpf_tcp_helpers.h" 8 9 char _license[] SEC("license") = "GPL"; 10 struct hmap_elem { 11 int counter; 12 struct bpf_timer timer; 13 struct bpf_spin_lock lock; /* unused */ 14 }; 15 16 struct { 17 __uint(type, BPF_MAP_TYPE_HASH); 18 __uint(max_entries, 1000); 19 __type(key, int); 20 __type(value, struct hmap_elem); 21 } hmap SEC(".maps"); 22 23 struct { 24 __uint(type, BPF_MAP_TYPE_HASH); 25 __uint(map_flags, BPF_F_NO_PREALLOC); 26 __uint(max_entries, 1000); 27 __type(key, int); 28 __type(value, struct hmap_elem); 29 } hmap_malloc SEC(".maps"); 30 31 struct elem { 32 struct bpf_timer t; 33 }; 34 35 struct { 36 __uint(type, BPF_MAP_TYPE_ARRAY); 37 __uint(max_entries, 2); 38 __type(key, int); 39 __type(value, struct elem); 40 } array SEC(".maps"); 41 42 struct { 43 __uint(type, BPF_MAP_TYPE_LRU_HASH); 44 __uint(max_entries, 4); 45 __type(key, int); 46 __type(value, struct elem); 47 } lru SEC(".maps"); 48 49 struct { 50 __uint(type, BPF_MAP_TYPE_ARRAY); 51 __uint(max_entries, 1); 52 __type(key, int); 53 __type(value, struct elem); 54 } abs_timer SEC(".maps"); 55 56 __u64 bss_data; 57 __u64 abs_data; 58 __u64 err; 59 __u64 ok; 60 __u64 callback_check = 52; 61 __u64 callback2_check = 52; 62 63 #define ARRAY 1 64 #define HTAB 2 65 #define HTAB_MALLOC 3 66 #define LRU 4 67 68 /* callback for array and lru timers */ 69 static int timer_cb1(void *map, int *key, struct bpf_timer *timer) 70 { 71 /* increment bss variable twice. 72 * Once via array timer callback and once via lru timer callback 73 */ 74 bss_data += 5; 75 76 /* *key == 0 - the callback was called for array timer. 77 * *key == 4 - the callback was called from lru timer. 78 */ 79 if (*key == ARRAY) { 80 struct bpf_timer *lru_timer; 81 int lru_key = LRU; 82 83 /* rearm array timer to be called again in ~35 seconds */ 84 if (bpf_timer_start(timer, 1ull << 35, 0) != 0) 85 err |= 1; 86 87 lru_timer = bpf_map_lookup_elem(&lru, &lru_key); 88 if (!lru_timer) 89 return 0; 90 bpf_timer_set_callback(lru_timer, timer_cb1); 91 if (bpf_timer_start(lru_timer, 0, 0) != 0) 92 err |= 2; 93 } else if (*key == LRU) { 94 int lru_key, i; 95 96 for (i = LRU + 1; 97 i <= 100 /* for current LRU eviction algorithm this number 98 * should be larger than ~ lru->max_entries * 2 99 */; 100 i++) { 101 struct elem init = {}; 102 103 /* lru_key cannot be used as loop induction variable 104 * otherwise the loop will be unbounded. 105 */ 106 lru_key = i; 107 108 /* add more elements into lru map to push out current 109 * element and force deletion of this timer 110 */ 111 bpf_map_update_elem(map, &lru_key, &init, 0); 112 /* look it up to bump it into active list */ 113 bpf_map_lookup_elem(map, &lru_key); 114 115 /* keep adding until *key changes underneath, 116 * which means that key/timer memory was reused 117 */ 118 if (*key != LRU) 119 break; 120 } 121 122 /* check that the timer was removed */ 123 if (bpf_timer_cancel(timer) != -EINVAL) 124 err |= 4; 125 ok |= 1; 126 } 127 return 0; 128 } 129 130 SEC("fentry/bpf_fentry_test1") 131 int BPF_PROG2(test1, int, a) 132 { 133 struct bpf_timer *arr_timer, *lru_timer; 134 struct elem init = {}; 135 int lru_key = LRU; 136 int array_key = ARRAY; 137 138 arr_timer = bpf_map_lookup_elem(&array, &array_key); 139 if (!arr_timer) 140 return 0; 141 bpf_timer_init(arr_timer, &array, CLOCK_MONOTONIC); 142 143 bpf_map_update_elem(&lru, &lru_key, &init, 0); 144 lru_timer = bpf_map_lookup_elem(&lru, &lru_key); 145 if (!lru_timer) 146 return 0; 147 bpf_timer_init(lru_timer, &lru, CLOCK_MONOTONIC); 148 149 bpf_timer_set_callback(arr_timer, timer_cb1); 150 bpf_timer_start(arr_timer, 0 /* call timer_cb1 asap */, 0); 151 152 /* init more timers to check that array destruction 153 * doesn't leak timer memory. 154 */ 155 array_key = 0; 156 arr_timer = bpf_map_lookup_elem(&array, &array_key); 157 if (!arr_timer) 158 return 0; 159 bpf_timer_init(arr_timer, &array, CLOCK_MONOTONIC); 160 return 0; 161 } 162 163 /* callback for prealloc and non-prealloca hashtab timers */ 164 static int timer_cb2(void *map, int *key, struct hmap_elem *val) 165 { 166 if (*key == HTAB) 167 callback_check--; 168 else 169 callback2_check--; 170 if (val->counter > 0 && --val->counter) { 171 /* re-arm the timer again to execute after 1 usec */ 172 bpf_timer_start(&val->timer, 1000, 0); 173 } else if (*key == HTAB) { 174 struct bpf_timer *arr_timer; 175 int array_key = ARRAY; 176 177 /* cancel arr_timer otherwise bpf_fentry_test1 prog 178 * will stay alive forever. 179 */ 180 arr_timer = bpf_map_lookup_elem(&array, &array_key); 181 if (!arr_timer) 182 return 0; 183 if (bpf_timer_cancel(arr_timer) != 1) 184 /* bpf_timer_cancel should return 1 to indicate 185 * that arr_timer was active at this time 186 */ 187 err |= 8; 188 189 /* try to cancel ourself. It shouldn't deadlock. */ 190 if (bpf_timer_cancel(&val->timer) != -EDEADLK) 191 err |= 16; 192 193 /* delete this key and this timer anyway. 194 * It shouldn't deadlock either. 195 */ 196 bpf_map_delete_elem(map, key); 197 198 /* in preallocated hashmap both 'key' and 'val' could have been 199 * reused to store another map element (like in LRU above), 200 * but in controlled test environment the below test works. 201 * It's not a use-after-free. The memory is owned by the map. 202 */ 203 if (bpf_timer_start(&val->timer, 1000, 0) != -EINVAL) 204 err |= 32; 205 ok |= 2; 206 } else { 207 if (*key != HTAB_MALLOC) 208 err |= 64; 209 210 /* try to cancel ourself. It shouldn't deadlock. */ 211 if (bpf_timer_cancel(&val->timer) != -EDEADLK) 212 err |= 128; 213 214 /* delete this key and this timer anyway. 215 * It shouldn't deadlock either. 216 */ 217 bpf_map_delete_elem(map, key); 218 219 ok |= 4; 220 } 221 return 0; 222 } 223 224 int bpf_timer_test(void) 225 { 226 struct hmap_elem *val; 227 int key = HTAB, key_malloc = HTAB_MALLOC; 228 229 val = bpf_map_lookup_elem(&hmap, &key); 230 if (val) { 231 if (bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME) != 0) 232 err |= 512; 233 bpf_timer_set_callback(&val->timer, timer_cb2); 234 bpf_timer_start(&val->timer, 1000, 0); 235 } 236 val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); 237 if (val) { 238 if (bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME) != 0) 239 err |= 1024; 240 bpf_timer_set_callback(&val->timer, timer_cb2); 241 bpf_timer_start(&val->timer, 1000, 0); 242 } 243 return 0; 244 } 245 246 SEC("fentry/bpf_fentry_test2") 247 int BPF_PROG2(test2, int, a, int, b) 248 { 249 struct hmap_elem init = {}, *val; 250 int key = HTAB, key_malloc = HTAB_MALLOC; 251 252 init.counter = 10; /* number of times to trigger timer_cb2 */ 253 bpf_map_update_elem(&hmap, &key, &init, 0); 254 val = bpf_map_lookup_elem(&hmap, &key); 255 if (val) 256 bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME); 257 /* update the same key to free the timer */ 258 bpf_map_update_elem(&hmap, &key, &init, 0); 259 260 bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); 261 val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); 262 if (val) 263 bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME); 264 /* update the same key to free the timer */ 265 bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); 266 267 /* init more timers to check that htab operations 268 * don't leak timer memory. 269 */ 270 key = 0; 271 bpf_map_update_elem(&hmap, &key, &init, 0); 272 val = bpf_map_lookup_elem(&hmap, &key); 273 if (val) 274 bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME); 275 bpf_map_delete_elem(&hmap, &key); 276 bpf_map_update_elem(&hmap, &key, &init, 0); 277 val = bpf_map_lookup_elem(&hmap, &key); 278 if (val) 279 bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME); 280 281 /* and with non-prealloc htab */ 282 key_malloc = 0; 283 bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); 284 val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); 285 if (val) 286 bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME); 287 bpf_map_delete_elem(&hmap_malloc, &key_malloc); 288 bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); 289 val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); 290 if (val) 291 bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME); 292 293 return bpf_timer_test(); 294 } 295 296 /* callback for absolute timer */ 297 static int timer_cb3(void *map, int *key, struct bpf_timer *timer) 298 { 299 abs_data += 6; 300 301 if (abs_data < 12) { 302 bpf_timer_start(timer, bpf_ktime_get_boot_ns() + 1000, 303 BPF_F_TIMER_ABS); 304 } else { 305 /* Re-arm timer ~35 seconds in future */ 306 bpf_timer_start(timer, bpf_ktime_get_boot_ns() + (1ull << 35), 307 BPF_F_TIMER_ABS); 308 } 309 310 return 0; 311 } 312 313 SEC("fentry/bpf_fentry_test3") 314 int BPF_PROG2(test3, int, a) 315 { 316 int key = 0; 317 struct bpf_timer *timer; 318 319 bpf_printk("test3"); 320 321 timer = bpf_map_lookup_elem(&abs_timer, &key); 322 if (timer) { 323 if (bpf_timer_init(timer, &abs_timer, CLOCK_BOOTTIME) != 0) 324 err |= 2048; 325 bpf_timer_set_callback(timer, timer_cb3); 326 bpf_timer_start(timer, bpf_ktime_get_boot_ns() + 1000, 327 BPF_F_TIMER_ABS); 328 } 329 330 return 0; 331 } 332