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