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 */
timer_cb1(void * map,int * key,struct bpf_timer * timer)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")
BPF_PROG2(test1,int,a)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 */
timer_cb2(void * map,int * key,struct hmap_elem * val)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
bpf_timer_test(void)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")
BPF_PROG2(test2,int,a,int,b)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