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_PROG(test1,int a)123 int BPF_PROG(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 		/* in non-preallocated hashmap both 'key' and 'val' are RCU
212 		 * protected and still valid though this element was deleted
213 		 * from the map. Arm this timer for ~35 seconds. When callback
214 		 * finishes the call_rcu will invoke:
215 		 * htab_elem_free_rcu
216 		 *   check_and_free_timer
217 		 *     bpf_timer_cancel_and_free
218 		 * to cancel this 35 second sleep and delete the timer for real.
219 		 */
220 		if (bpf_timer_start(&val->timer, 1ull << 35, 0) != 0)
221 			err |= 256;
222 		ok |= 4;
223 	}
224 	return 0;
225 }
226 
bpf_timer_test(void)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")
BPF_PROG(test2,int a,int b)250 int BPF_PROG(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