1 /*
2  * Testsuite for eBPF maps
3  *
4  * Copyright (c) 2014 PLUMgrid, http://plumgrid.com
5  * Copyright (c) 2016 Facebook
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of version 2 of the GNU General Public
9  * License as published by the Free Software Foundation.
10  */
11 
12 #include <stdio.h>
13 #include <unistd.h>
14 #include <errno.h>
15 #include <string.h>
16 #include <assert.h>
17 #include <stdlib.h>
18 
19 #include <sys/wait.h>
20 #include <sys/resource.h>
21 
22 #include <linux/bpf.h>
23 
24 #include <bpf/bpf.h>
25 #include "bpf_util.h"
26 
27 static int map_flags;
28 
29 static void test_hashmap(int task, void *data)
30 {
31 	long long key, next_key, first_key, value;
32 	int fd;
33 
34 	fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
35 			    2, map_flags);
36 	if (fd < 0) {
37 		printf("Failed to create hashmap '%s'!\n", strerror(errno));
38 		exit(1);
39 	}
40 
41 	key = 1;
42 	value = 1234;
43 	/* Insert key=1 element. */
44 	assert(bpf_map_update_elem(fd, &key, &value, BPF_ANY) == 0);
45 
46 	value = 0;
47 	/* BPF_NOEXIST means add new element if it doesn't exist. */
48 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
49 	       /* key=1 already exists. */
50 	       errno == EEXIST);
51 
52 	/* -1 is an invalid flag. */
53 	assert(bpf_map_update_elem(fd, &key, &value, -1) == -1 &&
54 	       errno == EINVAL);
55 
56 	/* Check that key=1 can be found. */
57 	assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 1234);
58 
59 	key = 2;
60 	/* Check that key=2 is not found. */
61 	assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
62 
63 	/* BPF_EXIST means update existing element. */
64 	assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == -1 &&
65 	       /* key=2 is not there. */
66 	       errno == ENOENT);
67 
68 	/* Insert key=2 element. */
69 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == 0);
70 
71 	/* key=1 and key=2 were inserted, check that key=0 cannot be
72 	 * inserted due to max_entries limit.
73 	 */
74 	key = 0;
75 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
76 	       errno == E2BIG);
77 
78 	/* Update existing element, though the map is full. */
79 	key = 1;
80 	assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == 0);
81 	key = 2;
82 	assert(bpf_map_update_elem(fd, &key, &value, BPF_ANY) == 0);
83 	key = 3;
84 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
85 	       errno == E2BIG);
86 
87 	/* Check that key = 0 doesn't exist. */
88 	key = 0;
89 	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
90 
91 	/* Iterate over two elements. */
92 	assert(bpf_map_get_next_key(fd, NULL, &first_key) == 0 &&
93 	       (first_key == 1 || first_key == 2));
94 	assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
95 	       (next_key == first_key));
96 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
97 	       (next_key == 1 || next_key == 2) &&
98 	       (next_key != first_key));
99 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
100 	       errno == ENOENT);
101 
102 	/* Delete both elements. */
103 	key = 1;
104 	assert(bpf_map_delete_elem(fd, &key) == 0);
105 	key = 2;
106 	assert(bpf_map_delete_elem(fd, &key) == 0);
107 	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
108 
109 	key = 0;
110 	/* Check that map is empty. */
111 	assert(bpf_map_get_next_key(fd, NULL, &next_key) == -1 &&
112 	       errno == ENOENT);
113 	assert(bpf_map_get_next_key(fd, &key, &next_key) == -1 &&
114 	       errno == ENOENT);
115 
116 	close(fd);
117 }
118 
119 static void test_hashmap_sizes(int task, void *data)
120 {
121 	int fd, i, j;
122 
123 	for (i = 1; i <= 512; i <<= 1)
124 		for (j = 1; j <= 1 << 18; j <<= 1) {
125 			fd = bpf_create_map(BPF_MAP_TYPE_HASH, i, j,
126 					    2, map_flags);
127 			if (fd < 0) {
128 				printf("Failed to create hashmap key=%d value=%d '%s'\n",
129 				       i, j, strerror(errno));
130 				exit(1);
131 			}
132 			close(fd);
133 			usleep(10); /* give kernel time to destroy */
134 		}
135 }
136 
137 static void test_hashmap_percpu(int task, void *data)
138 {
139 	unsigned int nr_cpus = bpf_num_possible_cpus();
140 	BPF_DECLARE_PERCPU(long, value);
141 	long long key, next_key, first_key;
142 	int expected_key_mask = 0;
143 	int fd, i;
144 
145 	fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_HASH, sizeof(key),
146 			    sizeof(bpf_percpu(value, 0)), 2, map_flags);
147 	if (fd < 0) {
148 		printf("Failed to create hashmap '%s'!\n", strerror(errno));
149 		exit(1);
150 	}
151 
152 	for (i = 0; i < nr_cpus; i++)
153 		bpf_percpu(value, i) = i + 100;
154 
155 	key = 1;
156 	/* Insert key=1 element. */
157 	assert(!(expected_key_mask & key));
158 	assert(bpf_map_update_elem(fd, &key, value, BPF_ANY) == 0);
159 	expected_key_mask |= key;
160 
161 	/* BPF_NOEXIST means add new element if it doesn't exist. */
162 	assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == -1 &&
163 	       /* key=1 already exists. */
164 	       errno == EEXIST);
165 
166 	/* -1 is an invalid flag. */
167 	assert(bpf_map_update_elem(fd, &key, value, -1) == -1 &&
168 	       errno == EINVAL);
169 
170 	/* Check that key=1 can be found. Value could be 0 if the lookup
171 	 * was run from a different CPU.
172 	 */
173 	bpf_percpu(value, 0) = 1;
174 	assert(bpf_map_lookup_elem(fd, &key, value) == 0 &&
175 	       bpf_percpu(value, 0) == 100);
176 
177 	key = 2;
178 	/* Check that key=2 is not found. */
179 	assert(bpf_map_lookup_elem(fd, &key, value) == -1 && errno == ENOENT);
180 
181 	/* BPF_EXIST means update existing element. */
182 	assert(bpf_map_update_elem(fd, &key, value, BPF_EXIST) == -1 &&
183 	       /* key=2 is not there. */
184 	       errno == ENOENT);
185 
186 	/* Insert key=2 element. */
187 	assert(!(expected_key_mask & key));
188 	assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == 0);
189 	expected_key_mask |= key;
190 
191 	/* key=1 and key=2 were inserted, check that key=0 cannot be
192 	 * inserted due to max_entries limit.
193 	 */
194 	key = 0;
195 	assert(bpf_map_update_elem(fd, &key, value, BPF_NOEXIST) == -1 &&
196 	       errno == E2BIG);
197 
198 	/* Check that key = 0 doesn't exist. */
199 	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
200 
201 	/* Iterate over two elements. */
202 	assert(bpf_map_get_next_key(fd, NULL, &first_key) == 0 &&
203 	       ((expected_key_mask & first_key) == first_key));
204 	while (!bpf_map_get_next_key(fd, &key, &next_key)) {
205 		if (first_key) {
206 			assert(next_key == first_key);
207 			first_key = 0;
208 		}
209 		assert((expected_key_mask & next_key) == next_key);
210 		expected_key_mask &= ~next_key;
211 
212 		assert(bpf_map_lookup_elem(fd, &next_key, value) == 0);
213 
214 		for (i = 0; i < nr_cpus; i++)
215 			assert(bpf_percpu(value, i) == i + 100);
216 
217 		key = next_key;
218 	}
219 	assert(errno == ENOENT);
220 
221 	/* Update with BPF_EXIST. */
222 	key = 1;
223 	assert(bpf_map_update_elem(fd, &key, value, BPF_EXIST) == 0);
224 
225 	/* Delete both elements. */
226 	key = 1;
227 	assert(bpf_map_delete_elem(fd, &key) == 0);
228 	key = 2;
229 	assert(bpf_map_delete_elem(fd, &key) == 0);
230 	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == ENOENT);
231 
232 	key = 0;
233 	/* Check that map is empty. */
234 	assert(bpf_map_get_next_key(fd, NULL, &next_key) == -1 &&
235 	       errno == ENOENT);
236 	assert(bpf_map_get_next_key(fd, &key, &next_key) == -1 &&
237 	       errno == ENOENT);
238 
239 	close(fd);
240 }
241 
242 static void test_arraymap(int task, void *data)
243 {
244 	int key, next_key, fd;
245 	long long value;
246 
247 	fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value),
248 			    2, 0);
249 	if (fd < 0) {
250 		printf("Failed to create arraymap '%s'!\n", strerror(errno));
251 		exit(1);
252 	}
253 
254 	key = 1;
255 	value = 1234;
256 	/* Insert key=1 element. */
257 	assert(bpf_map_update_elem(fd, &key, &value, BPF_ANY) == 0);
258 
259 	value = 0;
260 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
261 	       errno == EEXIST);
262 
263 	/* Check that key=1 can be found. */
264 	assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 1234);
265 
266 	key = 0;
267 	/* Check that key=0 is also found and zero initialized. */
268 	assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 0);
269 
270 	/* key=0 and key=1 were inserted, check that key=2 cannot be inserted
271 	 * due to max_entries limit.
272 	 */
273 	key = 2;
274 	assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == -1 &&
275 	       errno == E2BIG);
276 
277 	/* Check that key = 2 doesn't exist. */
278 	assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
279 
280 	/* Iterate over two elements. */
281 	assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
282 	       next_key == 0);
283 	assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
284 	       next_key == 0);
285 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
286 	       next_key == 1);
287 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
288 	       errno == ENOENT);
289 
290 	/* Delete shouldn't succeed. */
291 	key = 1;
292 	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
293 
294 	close(fd);
295 }
296 
297 static void test_arraymap_percpu(int task, void *data)
298 {
299 	unsigned int nr_cpus = bpf_num_possible_cpus();
300 	BPF_DECLARE_PERCPU(long, values);
301 	int key, next_key, fd, i;
302 
303 	fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
304 			    sizeof(bpf_percpu(values, 0)), 2, 0);
305 	if (fd < 0) {
306 		printf("Failed to create arraymap '%s'!\n", strerror(errno));
307 		exit(1);
308 	}
309 
310 	for (i = 0; i < nr_cpus; i++)
311 		bpf_percpu(values, i) = i + 100;
312 
313 	key = 1;
314 	/* Insert key=1 element. */
315 	assert(bpf_map_update_elem(fd, &key, values, BPF_ANY) == 0);
316 
317 	bpf_percpu(values, 0) = 0;
318 	assert(bpf_map_update_elem(fd, &key, values, BPF_NOEXIST) == -1 &&
319 	       errno == EEXIST);
320 
321 	/* Check that key=1 can be found. */
322 	assert(bpf_map_lookup_elem(fd, &key, values) == 0 &&
323 	       bpf_percpu(values, 0) == 100);
324 
325 	key = 0;
326 	/* Check that key=0 is also found and zero initialized. */
327 	assert(bpf_map_lookup_elem(fd, &key, values) == 0 &&
328 	       bpf_percpu(values, 0) == 0 &&
329 	       bpf_percpu(values, nr_cpus - 1) == 0);
330 
331 	/* Check that key=2 cannot be inserted due to max_entries limit. */
332 	key = 2;
333 	assert(bpf_map_update_elem(fd, &key, values, BPF_EXIST) == -1 &&
334 	       errno == E2BIG);
335 
336 	/* Check that key = 2 doesn't exist. */
337 	assert(bpf_map_lookup_elem(fd, &key, values) == -1 && errno == ENOENT);
338 
339 	/* Iterate over two elements. */
340 	assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
341 	       next_key == 0);
342 	assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
343 	       next_key == 0);
344 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
345 	       next_key == 1);
346 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
347 	       errno == ENOENT);
348 
349 	/* Delete shouldn't succeed. */
350 	key = 1;
351 	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
352 
353 	close(fd);
354 }
355 
356 static void test_arraymap_percpu_many_keys(void)
357 {
358 	unsigned int nr_cpus = bpf_num_possible_cpus();
359 	BPF_DECLARE_PERCPU(long, values);
360 	/* nr_keys is not too large otherwise the test stresses percpu
361 	 * allocator more than anything else
362 	 */
363 	unsigned int nr_keys = 2000;
364 	int key, fd, i;
365 
366 	fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
367 			    sizeof(bpf_percpu(values, 0)), nr_keys, 0);
368 	if (fd < 0) {
369 		printf("Failed to create per-cpu arraymap '%s'!\n",
370 		       strerror(errno));
371 		exit(1);
372 	}
373 
374 	for (i = 0; i < nr_cpus; i++)
375 		bpf_percpu(values, i) = i + 10;
376 
377 	for (key = 0; key < nr_keys; key++)
378 		assert(bpf_map_update_elem(fd, &key, values, BPF_ANY) == 0);
379 
380 	for (key = 0; key < nr_keys; key++) {
381 		for (i = 0; i < nr_cpus; i++)
382 			bpf_percpu(values, i) = 0;
383 
384 		assert(bpf_map_lookup_elem(fd, &key, values) == 0);
385 
386 		for (i = 0; i < nr_cpus; i++)
387 			assert(bpf_percpu(values, i) == i + 10);
388 	}
389 
390 	close(fd);
391 }
392 
393 #define MAP_SIZE (32 * 1024)
394 
395 static void test_map_large(void)
396 {
397 	struct bigkey {
398 		int a;
399 		char b[116];
400 		long long c;
401 	} key;
402 	int fd, i, value;
403 
404 	fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
405 			    MAP_SIZE, map_flags);
406 	if (fd < 0) {
407 		printf("Failed to create large map '%s'!\n", strerror(errno));
408 		exit(1);
409 	}
410 
411 	for (i = 0; i < MAP_SIZE; i++) {
412 		key = (struct bigkey) { .c = i };
413 		value = i;
414 
415 		assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == 0);
416 	}
417 
418 	key.c = -1;
419 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
420 	       errno == E2BIG);
421 
422 	/* Iterate through all elements. */
423 	assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
424 	key.c = -1;
425 	for (i = 0; i < MAP_SIZE; i++)
426 		assert(bpf_map_get_next_key(fd, &key, &key) == 0);
427 	assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
428 
429 	key.c = 0;
430 	assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 0);
431 	key.a = 1;
432 	assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
433 
434 	close(fd);
435 }
436 
437 static void run_parallel(int tasks, void (*fn)(int task, void *data),
438 			 void *data)
439 {
440 	pid_t pid[tasks];
441 	int i;
442 
443 	for (i = 0; i < tasks; i++) {
444 		pid[i] = fork();
445 		if (pid[i] == 0) {
446 			fn(i, data);
447 			exit(0);
448 		} else if (pid[i] == -1) {
449 			printf("Couldn't spawn #%d process!\n", i);
450 			exit(1);
451 		}
452 	}
453 
454 	for (i = 0; i < tasks; i++) {
455 		int status;
456 
457 		assert(waitpid(pid[i], &status, 0) == pid[i]);
458 		assert(status == 0);
459 	}
460 }
461 
462 static void test_map_stress(void)
463 {
464 	run_parallel(100, test_hashmap, NULL);
465 	run_parallel(100, test_hashmap_percpu, NULL);
466 	run_parallel(100, test_hashmap_sizes, NULL);
467 
468 	run_parallel(100, test_arraymap, NULL);
469 	run_parallel(100, test_arraymap_percpu, NULL);
470 }
471 
472 #define TASKS 1024
473 
474 #define DO_UPDATE 1
475 #define DO_DELETE 0
476 
477 static void do_work(int fn, void *data)
478 {
479 	int do_update = ((int *)data)[1];
480 	int fd = ((int *)data)[0];
481 	int i, key, value;
482 
483 	for (i = fn; i < MAP_SIZE; i += TASKS) {
484 		key = value = i;
485 
486 		if (do_update) {
487 			assert(bpf_map_update_elem(fd, &key, &value,
488 						   BPF_NOEXIST) == 0);
489 			assert(bpf_map_update_elem(fd, &key, &value,
490 						   BPF_EXIST) == 0);
491 		} else {
492 			assert(bpf_map_delete_elem(fd, &key) == 0);
493 		}
494 	}
495 }
496 
497 static void test_map_parallel(void)
498 {
499 	int i, fd, key = 0, value = 0;
500 	int data[2];
501 
502 	fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
503 			    MAP_SIZE, map_flags);
504 	if (fd < 0) {
505 		printf("Failed to create map for parallel test '%s'!\n",
506 		       strerror(errno));
507 		exit(1);
508 	}
509 
510 	/* Use the same fd in children to add elements to this map:
511 	 * child_0 adds key=0, key=1024, key=2048, ...
512 	 * child_1 adds key=1, key=1025, key=2049, ...
513 	 * child_1023 adds key=1023, ...
514 	 */
515 	data[0] = fd;
516 	data[1] = DO_UPDATE;
517 	run_parallel(TASKS, do_work, data);
518 
519 	/* Check that key=0 is already there. */
520 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
521 	       errno == EEXIST);
522 
523 	/* Check that all elements were inserted. */
524 	assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
525 	key = -1;
526 	for (i = 0; i < MAP_SIZE; i++)
527 		assert(bpf_map_get_next_key(fd, &key, &key) == 0);
528 	assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
529 
530 	/* Another check for all elements */
531 	for (i = 0; i < MAP_SIZE; i++) {
532 		key = MAP_SIZE - i - 1;
533 
534 		assert(bpf_map_lookup_elem(fd, &key, &value) == 0 &&
535 		       value == key);
536 	}
537 
538 	/* Now let's delete all elemenets in parallel. */
539 	data[1] = DO_DELETE;
540 	run_parallel(TASKS, do_work, data);
541 
542 	/* Nothing should be left. */
543 	key = -1;
544 	assert(bpf_map_get_next_key(fd, NULL, &key) == -1 && errno == ENOENT);
545 	assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
546 }
547 
548 static void run_all_tests(void)
549 {
550 	test_hashmap(0, NULL);
551 	test_hashmap_percpu(0, NULL);
552 
553 	test_arraymap(0, NULL);
554 	test_arraymap_percpu(0, NULL);
555 
556 	test_arraymap_percpu_many_keys();
557 
558 	test_map_large();
559 	test_map_parallel();
560 	test_map_stress();
561 }
562 
563 int main(void)
564 {
565 	struct rlimit rinf = { RLIM_INFINITY, RLIM_INFINITY };
566 
567 	setrlimit(RLIMIT_MEMLOCK, &rinf);
568 
569 	map_flags = 0;
570 	run_all_tests();
571 
572 	map_flags = BPF_F_NO_PREALLOC;
573 	run_all_tests();
574 
575 	printf("test_maps: OK\n");
576 	return 0;
577 }
578