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" ), soft_timer_pinned SEC(".maps" ), abs_timer_pinned SEC(".maps" ), |
55 | race_array SEC(".maps" ); |
56 | |
57 | __u64 bss_data; |
58 | __u64 abs_data; |
59 | __u64 err; |
60 | __u64 ok; |
61 | __u64 callback_check = 52; |
62 | __u64 callback2_check = 52; |
63 | __u64 pinned_callback_check; |
64 | __s32 pinned_cpu; |
65 | |
66 | #define ARRAY 1 |
67 | #define HTAB 2 |
68 | #define HTAB_MALLOC 3 |
69 | #define LRU 4 |
70 | |
71 | /* callback for array and lru timers */ |
72 | static int timer_cb1(void *map, int *key, struct bpf_timer *timer) |
73 | { |
74 | /* increment bss variable twice. |
75 | * Once via array timer callback and once via lru timer callback |
76 | */ |
77 | bss_data += 5; |
78 | |
79 | /* *key == 0 - the callback was called for array timer. |
80 | * *key == 4 - the callback was called from lru timer. |
81 | */ |
82 | if (*key == ARRAY) { |
83 | struct bpf_timer *lru_timer; |
84 | int lru_key = LRU; |
85 | |
86 | /* rearm array timer to be called again in ~35 seconds */ |
87 | if (bpf_timer_start(timer, 1ull << 35, 0) != 0) |
88 | err |= 1; |
89 | |
90 | lru_timer = bpf_map_lookup_elem(&lru, &lru_key); |
91 | if (!lru_timer) |
92 | return 0; |
93 | bpf_timer_set_callback(lru_timer, timer_cb1); |
94 | if (bpf_timer_start(lru_timer, 0, 0) != 0) |
95 | err |= 2; |
96 | } else if (*key == LRU) { |
97 | int lru_key, i; |
98 | |
99 | for (i = LRU + 1; |
100 | i <= 100 /* for current LRU eviction algorithm this number |
101 | * should be larger than ~ lru->max_entries * 2 |
102 | */; |
103 | i++) { |
104 | struct elem init = {}; |
105 | |
106 | /* lru_key cannot be used as loop induction variable |
107 | * otherwise the loop will be unbounded. |
108 | */ |
109 | lru_key = i; |
110 | |
111 | /* add more elements into lru map to push out current |
112 | * element and force deletion of this timer |
113 | */ |
114 | bpf_map_update_elem(map, &lru_key, &init, 0); |
115 | /* look it up to bump it into active list */ |
116 | bpf_map_lookup_elem(map, &lru_key); |
117 | |
118 | /* keep adding until *key changes underneath, |
119 | * which means that key/timer memory was reused |
120 | */ |
121 | if (*key != LRU) |
122 | break; |
123 | } |
124 | |
125 | /* check that the timer was removed */ |
126 | if (bpf_timer_cancel(timer) != -EINVAL) |
127 | err |= 4; |
128 | ok |= 1; |
129 | } |
130 | return 0; |
131 | } |
132 | |
133 | SEC("fentry/bpf_fentry_test1" ) |
134 | int BPF_PROG2(test1, int, a) |
135 | { |
136 | struct bpf_timer *arr_timer, *lru_timer; |
137 | struct elem init = {}; |
138 | int lru_key = LRU; |
139 | int array_key = ARRAY; |
140 | |
141 | arr_timer = bpf_map_lookup_elem(&array, &array_key); |
142 | if (!arr_timer) |
143 | return 0; |
144 | bpf_timer_init(arr_timer, &array, CLOCK_MONOTONIC); |
145 | |
146 | bpf_map_update_elem(&lru, &lru_key, &init, 0); |
147 | lru_timer = bpf_map_lookup_elem(&lru, &lru_key); |
148 | if (!lru_timer) |
149 | return 0; |
150 | bpf_timer_init(lru_timer, &lru, CLOCK_MONOTONIC); |
151 | |
152 | bpf_timer_set_callback(arr_timer, timer_cb1); |
153 | bpf_timer_start(arr_timer, 0 /* call timer_cb1 asap */, 0); |
154 | |
155 | /* init more timers to check that array destruction |
156 | * doesn't leak timer memory. |
157 | */ |
158 | array_key = 0; |
159 | arr_timer = bpf_map_lookup_elem(&array, &array_key); |
160 | if (!arr_timer) |
161 | return 0; |
162 | bpf_timer_init(arr_timer, &array, CLOCK_MONOTONIC); |
163 | return 0; |
164 | } |
165 | |
166 | /* callback for prealloc and non-prealloca hashtab timers */ |
167 | static int timer_cb2(void *map, int *key, struct hmap_elem *val) |
168 | { |
169 | if (*key == HTAB) |
170 | callback_check--; |
171 | else |
172 | callback2_check--; |
173 | if (val->counter > 0 && --val->counter) { |
174 | /* re-arm the timer again to execute after 1 usec */ |
175 | bpf_timer_start(&val->timer, 1000, 0); |
176 | } else if (*key == HTAB) { |
177 | struct bpf_timer *arr_timer; |
178 | int array_key = ARRAY; |
179 | |
180 | /* cancel arr_timer otherwise bpf_fentry_test1 prog |
181 | * will stay alive forever. |
182 | */ |
183 | arr_timer = bpf_map_lookup_elem(&array, &array_key); |
184 | if (!arr_timer) |
185 | return 0; |
186 | if (bpf_timer_cancel(arr_timer) != 1) |
187 | /* bpf_timer_cancel should return 1 to indicate |
188 | * that arr_timer was active at this time |
189 | */ |
190 | err |= 8; |
191 | |
192 | /* try to cancel ourself. It shouldn't deadlock. */ |
193 | if (bpf_timer_cancel(&val->timer) != -EDEADLK) |
194 | err |= 16; |
195 | |
196 | /* delete this key and this timer anyway. |
197 | * It shouldn't deadlock either. |
198 | */ |
199 | bpf_map_delete_elem(map, key); |
200 | |
201 | /* in preallocated hashmap both 'key' and 'val' could have been |
202 | * reused to store another map element (like in LRU above), |
203 | * but in controlled test environment the below test works. |
204 | * It's not a use-after-free. The memory is owned by the map. |
205 | */ |
206 | if (bpf_timer_start(&val->timer, 1000, 0) != -EINVAL) |
207 | err |= 32; |
208 | ok |= 2; |
209 | } else { |
210 | if (*key != HTAB_MALLOC) |
211 | err |= 64; |
212 | |
213 | /* try to cancel ourself. It shouldn't deadlock. */ |
214 | if (bpf_timer_cancel(&val->timer) != -EDEADLK) |
215 | err |= 128; |
216 | |
217 | /* delete this key and this timer anyway. |
218 | * It shouldn't deadlock either. |
219 | */ |
220 | bpf_map_delete_elem(map, key); |
221 | |
222 | ok |= 4; |
223 | } |
224 | return 0; |
225 | } |
226 | |
227 | int bpf_timer_test(void) |
228 | { |
229 | struct hmap_elem *val; |
230 | int key = HTAB, key_malloc = HTAB_MALLOC; |
231 | |
232 | val = bpf_map_lookup_elem(&hmap, &key); |
233 | if (val) { |
234 | if (bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME) != 0) |
235 | err |= 512; |
236 | bpf_timer_set_callback(&val->timer, timer_cb2); |
237 | bpf_timer_start(&val->timer, 1000, 0); |
238 | } |
239 | val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); |
240 | if (val) { |
241 | if (bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME) != 0) |
242 | err |= 1024; |
243 | bpf_timer_set_callback(&val->timer, timer_cb2); |
244 | bpf_timer_start(&val->timer, 1000, 0); |
245 | } |
246 | return 0; |
247 | } |
248 | |
249 | SEC("fentry/bpf_fentry_test2" ) |
250 | int BPF_PROG2(test2, int, a, int, b) |
251 | { |
252 | struct hmap_elem init = {}, *val; |
253 | int key = HTAB, key_malloc = HTAB_MALLOC; |
254 | |
255 | init.counter = 10; /* number of times to trigger timer_cb2 */ |
256 | bpf_map_update_elem(&hmap, &key, &init, 0); |
257 | val = bpf_map_lookup_elem(&hmap, &key); |
258 | if (val) |
259 | bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME); |
260 | /* update the same key to free the timer */ |
261 | bpf_map_update_elem(&hmap, &key, &init, 0); |
262 | |
263 | bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); |
264 | val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); |
265 | if (val) |
266 | bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME); |
267 | /* update the same key to free the timer */ |
268 | bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); |
269 | |
270 | /* init more timers to check that htab operations |
271 | * don't leak timer memory. |
272 | */ |
273 | key = 0; |
274 | bpf_map_update_elem(&hmap, &key, &init, 0); |
275 | val = bpf_map_lookup_elem(&hmap, &key); |
276 | if (val) |
277 | bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME); |
278 | bpf_map_delete_elem(&hmap, &key); |
279 | bpf_map_update_elem(&hmap, &key, &init, 0); |
280 | val = bpf_map_lookup_elem(&hmap, &key); |
281 | if (val) |
282 | bpf_timer_init(&val->timer, &hmap, CLOCK_BOOTTIME); |
283 | |
284 | /* and with non-prealloc htab */ |
285 | key_malloc = 0; |
286 | bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); |
287 | val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); |
288 | if (val) |
289 | bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME); |
290 | bpf_map_delete_elem(&hmap_malloc, &key_malloc); |
291 | bpf_map_update_elem(&hmap_malloc, &key_malloc, &init, 0); |
292 | val = bpf_map_lookup_elem(&hmap_malloc, &key_malloc); |
293 | if (val) |
294 | bpf_timer_init(&val->timer, &hmap_malloc, CLOCK_BOOTTIME); |
295 | |
296 | return bpf_timer_test(); |
297 | } |
298 | |
299 | /* callback for absolute timer */ |
300 | static int timer_cb3(void *map, int *key, struct bpf_timer *timer) |
301 | { |
302 | abs_data += 6; |
303 | |
304 | if (abs_data < 12) { |
305 | bpf_timer_start(timer, bpf_ktime_get_boot_ns() + 1000, |
306 | BPF_F_TIMER_ABS); |
307 | } else { |
308 | /* Re-arm timer ~35 seconds in future */ |
309 | bpf_timer_start(timer, bpf_ktime_get_boot_ns() + (1ull << 35), |
310 | BPF_F_TIMER_ABS); |
311 | } |
312 | |
313 | return 0; |
314 | } |
315 | |
316 | SEC("fentry/bpf_fentry_test3" ) |
317 | int BPF_PROG2(test3, int, a) |
318 | { |
319 | int key = 0; |
320 | struct bpf_timer *timer; |
321 | |
322 | bpf_printk("test3" ); |
323 | |
324 | timer = bpf_map_lookup_elem(&abs_timer, &key); |
325 | if (timer) { |
326 | if (bpf_timer_init(timer, &abs_timer, CLOCK_BOOTTIME) != 0) |
327 | err |= 2048; |
328 | bpf_timer_set_callback(timer, timer_cb3); |
329 | bpf_timer_start(timer, bpf_ktime_get_boot_ns() + 1000, |
330 | BPF_F_TIMER_ABS); |
331 | } |
332 | |
333 | return 0; |
334 | } |
335 | |
336 | /* callback for pinned timer */ |
337 | static int timer_cb_pinned(void *map, int *key, struct bpf_timer *timer) |
338 | { |
339 | __s32 cpu = bpf_get_smp_processor_id(); |
340 | |
341 | if (cpu != pinned_cpu) |
342 | err |= 16384; |
343 | |
344 | pinned_callback_check++; |
345 | return 0; |
346 | } |
347 | |
348 | static void test_pinned_timer(bool soft) |
349 | { |
350 | int key = 0; |
351 | void *map; |
352 | struct bpf_timer *timer; |
353 | __u64 flags = BPF_F_TIMER_CPU_PIN; |
354 | __u64 start_time; |
355 | |
356 | if (soft) { |
357 | map = &soft_timer_pinned; |
358 | start_time = 0; |
359 | } else { |
360 | map = &abs_timer_pinned; |
361 | start_time = bpf_ktime_get_boot_ns(); |
362 | flags |= BPF_F_TIMER_ABS; |
363 | } |
364 | |
365 | timer = bpf_map_lookup_elem(map, &key); |
366 | if (timer) { |
367 | if (bpf_timer_init(timer, map, CLOCK_BOOTTIME) != 0) |
368 | err |= 4096; |
369 | bpf_timer_set_callback(timer, timer_cb_pinned); |
370 | pinned_cpu = bpf_get_smp_processor_id(); |
371 | bpf_timer_start(timer, start_time + 1000, flags); |
372 | } else { |
373 | err |= 8192; |
374 | } |
375 | } |
376 | |
377 | SEC("fentry/bpf_fentry_test4" ) |
378 | int BPF_PROG2(test4, int, a) |
379 | { |
380 | bpf_printk("test4" ); |
381 | test_pinned_timer(soft: true); |
382 | |
383 | return 0; |
384 | } |
385 | |
386 | SEC("fentry/bpf_fentry_test5" ) |
387 | int BPF_PROG2(test5, int, a) |
388 | { |
389 | bpf_printk("test5" ); |
390 | test_pinned_timer(soft: false); |
391 | |
392 | return 0; |
393 | } |
394 | |
395 | static int race_timer_callback(void *race_array, int *race_key, struct bpf_timer *timer) |
396 | { |
397 | bpf_timer_start(timer, 1000000, 0); |
398 | return 0; |
399 | } |
400 | |
401 | SEC("syscall" ) |
402 | int race(void *ctx) |
403 | { |
404 | struct bpf_timer *timer; |
405 | int err, race_key = 0; |
406 | struct elem init; |
407 | |
408 | __builtin_memset(&init, 0, sizeof(struct elem)); |
409 | bpf_map_update_elem(&race_array, &race_key, &init, BPF_ANY); |
410 | |
411 | timer = bpf_map_lookup_elem(&race_array, &race_key); |
412 | if (!timer) |
413 | return 1; |
414 | |
415 | err = bpf_timer_init(timer, &race_array, CLOCK_MONOTONIC); |
416 | if (err && err != -EBUSY) |
417 | return 1; |
418 | |
419 | bpf_timer_set_callback(timer, race_timer_callback); |
420 | bpf_timer_start(timer, 0, 0); |
421 | bpf_timer_cancel(timer); |
422 | |
423 | return 0; |
424 | } |
425 | |