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