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 __u64 bss_data; 50 __u64 err; 51 __u64 ok; 52 __u64 callback_check = 52; 53 __u64 callback2_check = 52; 54 55 #define ARRAY 1 56 #define HTAB 2 57 #define HTAB_MALLOC 3 58 #define LRU 4 59 60 /* callback for array and lru timers */ 61 static int timer_cb1(void *map, int *key, struct bpf_timer *timer) 62 { 63 /* increment bss variable twice. 64 * Once via array timer callback and once via lru timer callback 65 */ 66 bss_data += 5; 67 68 /* *key == 0 - the callback was called for array timer. 69 * *key == 4 - the callback was called from lru timer. 70 */ 71 if (*key == ARRAY) { 72 struct bpf_timer *lru_timer; 73 int lru_key = LRU; 74 75 /* rearm array timer to be called again in ~35 seconds */ 76 if (bpf_timer_start(timer, 1ull << 35, 0) != 0) 77 err |= 1; 78 79 lru_timer = bpf_map_lookup_elem(&lru, &lru_key); 80 if (!lru_timer) 81 return 0; 82 bpf_timer_set_callback(lru_timer, timer_cb1); 83 if (bpf_timer_start(lru_timer, 0, 0) != 0) 84 err |= 2; 85 } else if (*key == LRU) { 86 int lru_key, i; 87 88 for (i = LRU + 1; 89 i <= 100 /* for current LRU eviction algorithm this number 90 * should be larger than ~ lru->max_entries * 2 91 */; 92 i++) { 93 struct elem init = {}; 94 95 /* lru_key cannot be used as loop induction variable 96 * otherwise the loop will be unbounded. 97 */ 98 lru_key = i; 99 100 /* add more elements into lru map to push out current 101 * element and force deletion of this timer 102 */ 103 bpf_map_update_elem(map, &lru_key, &init, 0); 104 /* look it up to bump it into active list */ 105 bpf_map_lookup_elem(map, &lru_key); 106 107 /* keep adding until *key changes underneath, 108 * which means that key/timer memory was reused 109 */ 110 if (*key != LRU) 111 break; 112 } 113 114 /* check that the timer was removed */ 115 if (bpf_timer_cancel(timer) != -EINVAL) 116 err |= 4; 117 ok |= 1; 118 } 119 return 0; 120 } 121 122 SEC("fentry/bpf_fentry_test1") 123 int BPF_PROG2(test1, int, a) 124 { 125 struct bpf_timer *arr_timer, *lru_timer; 126 struct elem init = {}; 127 int lru_key = LRU; 128 int array_key = ARRAY; 129 130 arr_timer = bpf_map_lookup_elem(&array, &array_key); 131 if (!arr_timer) 132 return 0; 133 bpf_timer_init(arr_timer, &array, CLOCK_MONOTONIC); 134 135 bpf_map_update_elem(&lru, &lru_key, &init, 0); 136 lru_timer = bpf_map_lookup_elem(&lru, &lru_key); 137 if (!lru_timer) 138 return 0; 139 bpf_timer_init(lru_timer, &lru, CLOCK_MONOTONIC); 140 141 bpf_timer_set_callback(arr_timer, timer_cb1); 142 bpf_timer_start(arr_timer, 0 /* call timer_cb1 asap */, 0); 143 144 /* init more timers to check that array destruction 145 * doesn't leak timer memory. 146 */ 147 array_key = 0; 148 arr_timer = bpf_map_lookup_elem(&array, &array_key); 149 if (!arr_timer) 150 return 0; 151 bpf_timer_init(arr_timer, &array, CLOCK_MONOTONIC); 152 return 0; 153 } 154 155 /* callback for prealloc and non-prealloca hashtab timers */ 156 static int timer_cb2(void *map, int *key, struct hmap_elem *val) 157 { 158 if (*key == HTAB) 159 callback_check--; 160 else 161 callback2_check--; 162 if (val->counter > 0 && --val->counter) { 163 /* re-arm the timer again to execute after 1 usec */ 164 bpf_timer_start(&val->timer, 1000, 0); 165 } else if (*key == HTAB) { 166 struct bpf_timer *arr_timer; 167 int array_key = ARRAY; 168 169 /* cancel arr_timer otherwise bpf_fentry_test1 prog 170 * will stay alive forever. 171 */ 172 arr_timer = bpf_map_lookup_elem(&array, &array_key); 173 if (!arr_timer) 174 return 0; 175 if (bpf_timer_cancel(arr_timer) != 1) 176 /* bpf_timer_cancel should return 1 to indicate 177 * that arr_timer was active at this time 178 */ 179 err |= 8; 180 181 /* try to cancel ourself. It shouldn't deadlock. */ 182 if (bpf_timer_cancel(&val->timer) != -EDEADLK) 183 err |= 16; 184 185 /* delete this key and this timer anyway. 186 * It shouldn't deadlock either. 187 */ 188 bpf_map_delete_elem(map, key); 189 190 /* in preallocated hashmap both 'key' and 'val' could have been 191 * reused to store another map element (like in LRU above), 192 * but in controlled test environment the below test works. 193 * It's not a use-after-free. The memory is owned by the map. 194 */ 195 if (bpf_timer_start(&val->timer, 1000, 0) != -EINVAL) 196 err |= 32; 197 ok |= 2; 198 } else { 199 if (*key != HTAB_MALLOC) 200 err |= 64; 201 202 /* try to cancel ourself. It shouldn't deadlock. */ 203 if (bpf_timer_cancel(&val->timer) != -EDEADLK) 204 err |= 128; 205 206 /* delete this key and this timer anyway. 207 * It shouldn't deadlock either. 208 */ 209 bpf_map_delete_elem(map, key); 210 211 ok |= 4; 212 } 213 return 0; 214 } 215 216 int bpf_timer_test(void) 217 { 218 struct hmap_elem *val; 219 int key = HTAB, key_malloc = HTAB_MALLOC; 220 221 val = bpf_map_lookup_elem(&hmap, &key); 222 if (val) { 223 if (bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME) != 0) 224 err |= 512; 225 bpf_timer_set_callback(&val->timer, timer_cb2); 226 bpf_timer_start(&val->timer, 1000, 0); 227 } 228 val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); 229 if (val) { 230 if (bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME) != 0) 231 err |= 1024; 232 bpf_timer_set_callback(&val->timer, timer_cb2); 233 bpf_timer_start(&val->timer, 1000, 0); 234 } 235 return 0; 236 } 237 238 SEC("fentry/bpf_fentry_test2") 239 int BPF_PROG2(test2, int, a, int, b) 240 { 241 struct hmap_elem init = {}, *val; 242 int key = HTAB, key_malloc = HTAB_MALLOC; 243 244 init.counter = 10; /* number of times to trigger timer_cb2 */ 245 bpf_map_update_elem(&hmap, &key, &init, 0); 246 val = bpf_map_lookup_elem(&hmap, &key); 247 if (val) 248 bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME); 249 /* update the same key to free the timer */ 250 bpf_map_update_elem(&hmap, &key, &init, 0); 251 252 bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); 253 val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); 254 if (val) 255 bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME); 256 /* update the same key to free the timer */ 257 bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); 258 259 /* init more timers to check that htab operations 260 * don't leak timer memory. 261 */ 262 key = 0; 263 bpf_map_update_elem(&hmap, &key, &init, 0); 264 val = bpf_map_lookup_elem(&hmap, &key); 265 if (val) 266 bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME); 267 bpf_map_delete_elem(&hmap, &key); 268 bpf_map_update_elem(&hmap, &key, &init, 0); 269 val = bpf_map_lookup_elem(&hmap, &key); 270 if (val) 271 bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME); 272 273 /* and with non-prealloc htab */ 274 key_malloc = 0; 275 bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); 276 val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); 277 if (val) 278 bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME); 279 bpf_map_delete_elem(&hmap_malloc, &key_malloc); 280 bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); 281 val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); 282 if (val) 283 bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME); 284 285 return bpf_timer_test(); 286 } 287