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_hashmap_walk(int task, void *data)
243 {
244 	int fd, i, max_entries = 100000;
245 	long long key, value, next_key;
246 	bool next_key_valid = true;
247 
248 	fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
249 			    max_entries, map_flags);
250 	if (fd < 0) {
251 		printf("Failed to create hashmap '%s'!\n", strerror(errno));
252 		exit(1);
253 	}
254 
255 	for (i = 0; i < max_entries; i++) {
256 		key = i; value = key;
257 		assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == 0);
258 	}
259 
260 	for (i = 0; bpf_map_get_next_key(fd, !i ? NULL : &key,
261 					 &next_key) == 0; i++) {
262 		key = next_key;
263 		assert(bpf_map_lookup_elem(fd, &key, &value) == 0);
264 	}
265 
266 	assert(i == max_entries);
267 
268 	assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
269 	for (i = 0; next_key_valid; i++) {
270 		next_key_valid = bpf_map_get_next_key(fd, &key, &next_key) == 0;
271 		assert(bpf_map_lookup_elem(fd, &key, &value) == 0);
272 		value++;
273 		assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == 0);
274 		key = next_key;
275 	}
276 
277 	assert(i == max_entries);
278 
279 	for (i = 0; bpf_map_get_next_key(fd, !i ? NULL : &key,
280 					 &next_key) == 0; i++) {
281 		key = next_key;
282 		assert(bpf_map_lookup_elem(fd, &key, &value) == 0);
283 		assert(value - 1 == key);
284 	}
285 
286 	assert(i == max_entries);
287 	close(fd);
288 }
289 
290 static void test_arraymap(int task, void *data)
291 {
292 	int key, next_key, fd;
293 	long long value;
294 
295 	fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value),
296 			    2, 0);
297 	if (fd < 0) {
298 		printf("Failed to create arraymap '%s'!\n", strerror(errno));
299 		exit(1);
300 	}
301 
302 	key = 1;
303 	value = 1234;
304 	/* Insert key=1 element. */
305 	assert(bpf_map_update_elem(fd, &key, &value, BPF_ANY) == 0);
306 
307 	value = 0;
308 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
309 	       errno == EEXIST);
310 
311 	/* Check that key=1 can be found. */
312 	assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 1234);
313 
314 	key = 0;
315 	/* Check that key=0 is also found and zero initialized. */
316 	assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 0);
317 
318 	/* key=0 and key=1 were inserted, check that key=2 cannot be inserted
319 	 * due to max_entries limit.
320 	 */
321 	key = 2;
322 	assert(bpf_map_update_elem(fd, &key, &value, BPF_EXIST) == -1 &&
323 	       errno == E2BIG);
324 
325 	/* Check that key = 2 doesn't exist. */
326 	assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
327 
328 	/* Iterate over two elements. */
329 	assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
330 	       next_key == 0);
331 	assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
332 	       next_key == 0);
333 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
334 	       next_key == 1);
335 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
336 	       errno == ENOENT);
337 
338 	/* Delete shouldn't succeed. */
339 	key = 1;
340 	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
341 
342 	close(fd);
343 }
344 
345 static void test_arraymap_percpu(int task, void *data)
346 {
347 	unsigned int nr_cpus = bpf_num_possible_cpus();
348 	BPF_DECLARE_PERCPU(long, values);
349 	int key, next_key, fd, i;
350 
351 	fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
352 			    sizeof(bpf_percpu(values, 0)), 2, 0);
353 	if (fd < 0) {
354 		printf("Failed to create arraymap '%s'!\n", strerror(errno));
355 		exit(1);
356 	}
357 
358 	for (i = 0; i < nr_cpus; i++)
359 		bpf_percpu(values, i) = i + 100;
360 
361 	key = 1;
362 	/* Insert key=1 element. */
363 	assert(bpf_map_update_elem(fd, &key, values, BPF_ANY) == 0);
364 
365 	bpf_percpu(values, 0) = 0;
366 	assert(bpf_map_update_elem(fd, &key, values, BPF_NOEXIST) == -1 &&
367 	       errno == EEXIST);
368 
369 	/* Check that key=1 can be found. */
370 	assert(bpf_map_lookup_elem(fd, &key, values) == 0 &&
371 	       bpf_percpu(values, 0) == 100);
372 
373 	key = 0;
374 	/* Check that key=0 is also found and zero initialized. */
375 	assert(bpf_map_lookup_elem(fd, &key, values) == 0 &&
376 	       bpf_percpu(values, 0) == 0 &&
377 	       bpf_percpu(values, nr_cpus - 1) == 0);
378 
379 	/* Check that key=2 cannot be inserted due to max_entries limit. */
380 	key = 2;
381 	assert(bpf_map_update_elem(fd, &key, values, BPF_EXIST) == -1 &&
382 	       errno == E2BIG);
383 
384 	/* Check that key = 2 doesn't exist. */
385 	assert(bpf_map_lookup_elem(fd, &key, values) == -1 && errno == ENOENT);
386 
387 	/* Iterate over two elements. */
388 	assert(bpf_map_get_next_key(fd, NULL, &next_key) == 0 &&
389 	       next_key == 0);
390 	assert(bpf_map_get_next_key(fd, &key, &next_key) == 0 &&
391 	       next_key == 0);
392 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == 0 &&
393 	       next_key == 1);
394 	assert(bpf_map_get_next_key(fd, &next_key, &next_key) == -1 &&
395 	       errno == ENOENT);
396 
397 	/* Delete shouldn't succeed. */
398 	key = 1;
399 	assert(bpf_map_delete_elem(fd, &key) == -1 && errno == EINVAL);
400 
401 	close(fd);
402 }
403 
404 static void test_arraymap_percpu_many_keys(void)
405 {
406 	unsigned int nr_cpus = bpf_num_possible_cpus();
407 	BPF_DECLARE_PERCPU(long, values);
408 	/* nr_keys is not too large otherwise the test stresses percpu
409 	 * allocator more than anything else
410 	 */
411 	unsigned int nr_keys = 2000;
412 	int key, fd, i;
413 
414 	fd = bpf_create_map(BPF_MAP_TYPE_PERCPU_ARRAY, sizeof(key),
415 			    sizeof(bpf_percpu(values, 0)), nr_keys, 0);
416 	if (fd < 0) {
417 		printf("Failed to create per-cpu arraymap '%s'!\n",
418 		       strerror(errno));
419 		exit(1);
420 	}
421 
422 	for (i = 0; i < nr_cpus; i++)
423 		bpf_percpu(values, i) = i + 10;
424 
425 	for (key = 0; key < nr_keys; key++)
426 		assert(bpf_map_update_elem(fd, &key, values, BPF_ANY) == 0);
427 
428 	for (key = 0; key < nr_keys; key++) {
429 		for (i = 0; i < nr_cpus; i++)
430 			bpf_percpu(values, i) = 0;
431 
432 		assert(bpf_map_lookup_elem(fd, &key, values) == 0);
433 
434 		for (i = 0; i < nr_cpus; i++)
435 			assert(bpf_percpu(values, i) == i + 10);
436 	}
437 
438 	close(fd);
439 }
440 
441 #define MAP_SIZE (32 * 1024)
442 
443 static void test_map_large(void)
444 {
445 	struct bigkey {
446 		int a;
447 		char b[116];
448 		long long c;
449 	} key;
450 	int fd, i, value;
451 
452 	fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
453 			    MAP_SIZE, map_flags);
454 	if (fd < 0) {
455 		printf("Failed to create large map '%s'!\n", strerror(errno));
456 		exit(1);
457 	}
458 
459 	for (i = 0; i < MAP_SIZE; i++) {
460 		key = (struct bigkey) { .c = i };
461 		value = i;
462 
463 		assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == 0);
464 	}
465 
466 	key.c = -1;
467 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
468 	       errno == E2BIG);
469 
470 	/* Iterate through all elements. */
471 	assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
472 	key.c = -1;
473 	for (i = 0; i < MAP_SIZE; i++)
474 		assert(bpf_map_get_next_key(fd, &key, &key) == 0);
475 	assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
476 
477 	key.c = 0;
478 	assert(bpf_map_lookup_elem(fd, &key, &value) == 0 && value == 0);
479 	key.a = 1;
480 	assert(bpf_map_lookup_elem(fd, &key, &value) == -1 && errno == ENOENT);
481 
482 	close(fd);
483 }
484 
485 static void run_parallel(int tasks, void (*fn)(int task, void *data),
486 			 void *data)
487 {
488 	pid_t pid[tasks];
489 	int i;
490 
491 	for (i = 0; i < tasks; i++) {
492 		pid[i] = fork();
493 		if (pid[i] == 0) {
494 			fn(i, data);
495 			exit(0);
496 		} else if (pid[i] == -1) {
497 			printf("Couldn't spawn #%d process!\n", i);
498 			exit(1);
499 		}
500 	}
501 
502 	for (i = 0; i < tasks; i++) {
503 		int status;
504 
505 		assert(waitpid(pid[i], &status, 0) == pid[i]);
506 		assert(status == 0);
507 	}
508 }
509 
510 static void test_map_stress(void)
511 {
512 	run_parallel(100, test_hashmap, NULL);
513 	run_parallel(100, test_hashmap_percpu, NULL);
514 	run_parallel(100, test_hashmap_sizes, NULL);
515 	run_parallel(100, test_hashmap_walk, NULL);
516 
517 	run_parallel(100, test_arraymap, NULL);
518 	run_parallel(100, test_arraymap_percpu, NULL);
519 }
520 
521 #define TASKS 1024
522 
523 #define DO_UPDATE 1
524 #define DO_DELETE 0
525 
526 static void do_work(int fn, void *data)
527 {
528 	int do_update = ((int *)data)[1];
529 	int fd = ((int *)data)[0];
530 	int i, key, value;
531 
532 	for (i = fn; i < MAP_SIZE; i += TASKS) {
533 		key = value = i;
534 
535 		if (do_update) {
536 			assert(bpf_map_update_elem(fd, &key, &value,
537 						   BPF_NOEXIST) == 0);
538 			assert(bpf_map_update_elem(fd, &key, &value,
539 						   BPF_EXIST) == 0);
540 		} else {
541 			assert(bpf_map_delete_elem(fd, &key) == 0);
542 		}
543 	}
544 }
545 
546 static void test_map_parallel(void)
547 {
548 	int i, fd, key = 0, value = 0;
549 	int data[2];
550 
551 	fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
552 			    MAP_SIZE, map_flags);
553 	if (fd < 0) {
554 		printf("Failed to create map for parallel test '%s'!\n",
555 		       strerror(errno));
556 		exit(1);
557 	}
558 
559 	/* Use the same fd in children to add elements to this map:
560 	 * child_0 adds key=0, key=1024, key=2048, ...
561 	 * child_1 adds key=1, key=1025, key=2049, ...
562 	 * child_1023 adds key=1023, ...
563 	 */
564 	data[0] = fd;
565 	data[1] = DO_UPDATE;
566 	run_parallel(TASKS, do_work, data);
567 
568 	/* Check that key=0 is already there. */
569 	assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == -1 &&
570 	       errno == EEXIST);
571 
572 	/* Check that all elements were inserted. */
573 	assert(bpf_map_get_next_key(fd, NULL, &key) == 0);
574 	key = -1;
575 	for (i = 0; i < MAP_SIZE; i++)
576 		assert(bpf_map_get_next_key(fd, &key, &key) == 0);
577 	assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
578 
579 	/* Another check for all elements */
580 	for (i = 0; i < MAP_SIZE; i++) {
581 		key = MAP_SIZE - i - 1;
582 
583 		assert(bpf_map_lookup_elem(fd, &key, &value) == 0 &&
584 		       value == key);
585 	}
586 
587 	/* Now let's delete all elemenets in parallel. */
588 	data[1] = DO_DELETE;
589 	run_parallel(TASKS, do_work, data);
590 
591 	/* Nothing should be left. */
592 	key = -1;
593 	assert(bpf_map_get_next_key(fd, NULL, &key) == -1 && errno == ENOENT);
594 	assert(bpf_map_get_next_key(fd, &key, &key) == -1 && errno == ENOENT);
595 }
596 
597 static void run_all_tests(void)
598 {
599 	test_hashmap(0, NULL);
600 	test_hashmap_percpu(0, NULL);
601 	test_hashmap_walk(0, NULL);
602 
603 	test_arraymap(0, NULL);
604 	test_arraymap_percpu(0, NULL);
605 
606 	test_arraymap_percpu_many_keys();
607 
608 	test_map_large();
609 	test_map_parallel();
610 	test_map_stress();
611 }
612 
613 int main(void)
614 {
615 	struct rlimit rinf = { RLIM_INFINITY, RLIM_INFINITY };
616 
617 	setrlimit(RLIMIT_MEMLOCK, &rinf);
618 
619 	map_flags = 0;
620 	run_all_tests();
621 
622 	map_flags = BPF_F_NO_PREALLOC;
623 	run_all_tests();
624 
625 	printf("test_maps: OK\n");
626 	return 0;
627 }
628