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
test_hashmap(int task,void * data)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
test_hashmap_sizes(int task,void * data)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
test_hashmap_percpu(int task,void * data)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
test_arraymap(int task,void * data)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
test_arraymap_percpu(int task,void * data)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 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
test_arraymap_percpu_many_keys(void)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 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
test_map_large(void)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
run_parallel(int tasks,void (* fn)(int task,void * data),void * data)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
test_map_stress(void)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
do_work(int fn,void * data)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
test_map_parallel(void)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
run_all_tests(void)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
main(void)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