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