Loading...
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright (c) 2016 Facebook
4 */
5#define _GNU_SOURCE
6#include <stdio.h>
7#include <unistd.h>
8#include <errno.h>
9#include <string.h>
10#include <assert.h>
11#include <sched.h>
12#include <stdlib.h>
13#include <time.h>
14
15#include <sys/wait.h>
16
17#include <bpf/bpf.h>
18#include <bpf/libbpf.h>
19
20#include "bpf_util.h"
21#include "../../../include/linux/filter.h"
22
23#define LOCAL_FREE_TARGET (128)
24#define PERCPU_FREE_TARGET (4)
25
26static int nr_cpus;
27
28static int create_map(int map_type, int map_flags, unsigned int size)
29{
30 LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = map_flags);
31 int map_fd;
32
33 map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long),
34 sizeof(unsigned long long), size, &opts);
35
36 if (map_fd == -1)
37 perror("bpf_map_create");
38
39 return map_fd;
40}
41
42static int bpf_map_lookup_elem_with_ref_bit(int fd, unsigned long long key,
43 void *value)
44{
45 struct bpf_insn insns[] = {
46 BPF_LD_MAP_VALUE(BPF_REG_9, 0, 0),
47 BPF_LD_MAP_FD(BPF_REG_1, fd),
48 BPF_LD_IMM64(BPF_REG_3, key),
49 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
50 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
51 BPF_STX_MEM(BPF_DW, BPF_REG_2, BPF_REG_3, 0),
52 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
53 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4),
54 BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
55 BPF_STX_MEM(BPF_DW, BPF_REG_9, BPF_REG_1, 0),
56 BPF_MOV64_IMM(BPF_REG_0, 42),
57 BPF_JMP_IMM(BPF_JA, 0, 0, 1),
58 BPF_MOV64_IMM(BPF_REG_0, 1),
59 BPF_EXIT_INSN(),
60 };
61 __u8 data[64] = {};
62 int mfd, pfd, ret, zero = 0;
63 LIBBPF_OPTS(bpf_test_run_opts, topts,
64 .data_in = data,
65 .data_size_in = sizeof(data),
66 .repeat = 1,
67 );
68
69 mfd = bpf_map_create(BPF_MAP_TYPE_ARRAY, NULL, sizeof(int), sizeof(__u64), 1, NULL);
70 if (mfd < 0)
71 return -1;
72
73 insns[0].imm = mfd;
74
75 pfd = bpf_prog_load(BPF_PROG_TYPE_SCHED_CLS, NULL, "GPL", insns, ARRAY_SIZE(insns), NULL);
76 if (pfd < 0) {
77 close(mfd);
78 return -1;
79 }
80
81 ret = bpf_prog_test_run_opts(pfd, &topts);
82 if (ret < 0 || topts.retval != 42) {
83 ret = -1;
84 } else {
85 assert(!bpf_map_lookup_elem(mfd, &zero, value));
86 ret = 0;
87 }
88 close(pfd);
89 close(mfd);
90 return ret;
91}
92
93static int map_subset(int map0, int map1)
94{
95 unsigned long long next_key = 0;
96 unsigned long long value0[nr_cpus], value1[nr_cpus];
97 int ret;
98
99 while (!bpf_map_get_next_key(map1, &next_key, &next_key)) {
100 assert(!bpf_map_lookup_elem(map1, &next_key, value1));
101 ret = bpf_map_lookup_elem(map0, &next_key, value0);
102 if (ret) {
103 printf("key:%llu not found from map. %s(%d)\n",
104 next_key, strerror(errno), errno);
105 return 0;
106 }
107 if (value0[0] != value1[0]) {
108 printf("key:%llu value0:%llu != value1:%llu\n",
109 next_key, value0[0], value1[0]);
110 return 0;
111 }
112 }
113 return 1;
114}
115
116static int map_equal(int lru_map, int expected)
117{
118 return map_subset(lru_map, expected) && map_subset(expected, lru_map);
119}
120
121static int sched_next_online(int pid, int *next_to_try)
122{
123 cpu_set_t cpuset;
124 int next = *next_to_try;
125 int ret = -1;
126
127 while (next < nr_cpus) {
128 CPU_ZERO(&cpuset);
129 CPU_SET(next, &cpuset);
130 next++;
131 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) {
132 ret = 0;
133 break;
134 }
135 }
136
137 *next_to_try = next;
138 return ret;
139}
140
141/* Size of the LRU map is 2
142 * Add key=1 (+1 key)
143 * Add key=2 (+1 key)
144 * Lookup Key=1
145 * Add Key=3
146 * => Key=2 will be removed by LRU
147 * Iterate map. Only found key=1 and key=3
148 */
149static void test_lru_sanity0(int map_type, int map_flags)
150{
151 unsigned long long key, value[nr_cpus];
152 int lru_map_fd, expected_map_fd;
153 int next_cpu = 0;
154
155 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
156 map_flags);
157
158 assert(sched_next_online(0, &next_cpu) != -1);
159
160 if (map_flags & BPF_F_NO_COMMON_LRU)
161 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
162 else
163 lru_map_fd = create_map(map_type, map_flags, 2);
164 assert(lru_map_fd != -1);
165
166 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
167 assert(expected_map_fd != -1);
168
169 value[0] = 1234;
170
171 /* insert key=1 element */
172
173 key = 1;
174 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
175 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
176 BPF_NOEXIST));
177
178 /* BPF_NOEXIST means: add new element if it doesn't exist */
179 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST);
180 /* key=1 already exists */
181
182 assert(bpf_map_update_elem(lru_map_fd, &key, value, -1) == -EINVAL);
183
184 /* insert key=2 element */
185
186 /* check that key=2 is not found */
187 key = 2;
188 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
189
190 /* BPF_EXIST means: update existing element */
191 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT);
192 /* key=2 is not there */
193
194 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
195
196 /* insert key=3 element */
197
198 /* check that key=3 is not found */
199 key = 3;
200 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
201
202 /* check that key=1 can be found and mark the ref bit to
203 * stop LRU from removing key=1
204 */
205 key = 1;
206 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
207 assert(value[0] == 1234);
208
209 key = 3;
210 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
211 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
212 BPF_NOEXIST));
213
214 /* key=2 has been removed from the LRU */
215 key = 2;
216 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
217
218 /* lookup elem key=1 and delete it, then check it doesn't exist */
219 key = 1;
220 assert(!bpf_map_lookup_and_delete_elem(lru_map_fd, &key, &value));
221 assert(value[0] == 1234);
222
223 /* remove the same element from the expected map */
224 assert(!bpf_map_delete_elem(expected_map_fd, &key));
225
226 assert(map_equal(lru_map_fd, expected_map_fd));
227
228 close(expected_map_fd);
229 close(lru_map_fd);
230
231 printf("Pass\n");
232}
233
234/* Size of the LRU map is 1.5*tgt_free
235 * Insert 1 to tgt_free (+tgt_free keys)
236 * Lookup 1 to tgt_free/2
237 * Insert 1+tgt_free to 2*tgt_free (+tgt_free keys)
238 * => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU
239 */
240static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free)
241{
242 unsigned long long key, end_key, value[nr_cpus];
243 int lru_map_fd, expected_map_fd;
244 unsigned int batch_size;
245 unsigned int map_size;
246 int next_cpu = 0;
247
248 if (map_flags & BPF_F_NO_COMMON_LRU)
249 /* This test is only applicable to common LRU list */
250 return;
251
252 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
253 map_flags);
254
255 assert(sched_next_online(0, &next_cpu) != -1);
256
257 batch_size = tgt_free / 2;
258 assert(batch_size * 2 == tgt_free);
259
260 map_size = tgt_free + batch_size;
261 lru_map_fd = create_map(map_type, map_flags, map_size);
262 assert(lru_map_fd != -1);
263
264 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
265 assert(expected_map_fd != -1);
266
267 value[0] = 1234;
268
269 /* Insert 1 to tgt_free (+tgt_free keys) */
270 end_key = 1 + tgt_free;
271 for (key = 1; key < end_key; key++)
272 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
273 BPF_NOEXIST));
274
275 /* Lookup 1 to tgt_free/2 */
276 end_key = 1 + batch_size;
277 for (key = 1; key < end_key; key++) {
278 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
279 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
280 BPF_NOEXIST));
281 }
282
283 /* Insert 1+tgt_free to 2*tgt_free
284 * => 1+tgt_free/2 to LOCALFREE_TARGET will be
285 * removed by LRU
286 */
287 key = 1 + tgt_free;
288 end_key = key + tgt_free;
289 for (; key < end_key; key++) {
290 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
291 BPF_NOEXIST));
292 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
293 BPF_NOEXIST));
294 }
295
296 assert(map_equal(lru_map_fd, expected_map_fd));
297
298 close(expected_map_fd);
299 close(lru_map_fd);
300
301 printf("Pass\n");
302}
303
304/* Size of the LRU map 1.5 * tgt_free
305 * Insert 1 to tgt_free (+tgt_free keys)
306 * Update 1 to tgt_free/2
307 * => The original 1 to tgt_free/2 will be removed due to
308 * the LRU shrink process
309 * Re-insert 1 to tgt_free/2 again and do a lookup immeidately
310 * Insert 1+tgt_free to tgt_free*3/2
311 * Insert 1+tgt_free*3/2 to tgt_free*5/2
312 * => Key 1+tgt_free to tgt_free*3/2
313 * will be removed from LRU because it has never
314 * been lookup and ref bit is not set
315 */
316static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free)
317{
318 unsigned long long key, value[nr_cpus];
319 unsigned long long end_key;
320 int lru_map_fd, expected_map_fd;
321 unsigned int batch_size;
322 unsigned int map_size;
323 int next_cpu = 0;
324
325 if (map_flags & BPF_F_NO_COMMON_LRU)
326 /* This test is only applicable to common LRU list */
327 return;
328
329 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
330 map_flags);
331
332 assert(sched_next_online(0, &next_cpu) != -1);
333
334 batch_size = tgt_free / 2;
335 assert(batch_size * 2 == tgt_free);
336
337 map_size = tgt_free + batch_size;
338 lru_map_fd = create_map(map_type, map_flags, map_size);
339 assert(lru_map_fd != -1);
340
341 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
342 assert(expected_map_fd != -1);
343
344 value[0] = 1234;
345
346 /* Insert 1 to tgt_free (+tgt_free keys) */
347 end_key = 1 + tgt_free;
348 for (key = 1; key < end_key; key++)
349 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
350 BPF_NOEXIST));
351
352 /* Any bpf_map_update_elem will require to acquire a new node
353 * from LRU first.
354 *
355 * The local list is running out of free nodes.
356 * It gets from the global LRU list which tries to
357 * shrink the inactive list to get tgt_free
358 * number of free nodes.
359 *
360 * Hence, the oldest key 1 to tgt_free/2
361 * are removed from the LRU list.
362 */
363 key = 1;
364 if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
365 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
366 BPF_NOEXIST));
367 assert(!bpf_map_delete_elem(lru_map_fd, &key));
368 } else {
369 assert(bpf_map_update_elem(lru_map_fd, &key, value,
370 BPF_EXIST));
371 }
372
373 /* Re-insert 1 to tgt_free/2 again and do a lookup
374 * immeidately.
375 */
376 end_key = 1 + batch_size;
377 value[0] = 4321;
378 for (key = 1; key < end_key; key++) {
379 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
380 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
381 BPF_NOEXIST));
382 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
383 assert(value[0] == 4321);
384 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
385 BPF_NOEXIST));
386 }
387
388 value[0] = 1234;
389
390 /* Insert 1+tgt_free to tgt_free*3/2 */
391 end_key = 1 + tgt_free + batch_size;
392 for (key = 1 + tgt_free; key < end_key; key++)
393 /* These newly added but not referenced keys will be
394 * gone during the next LRU shrink.
395 */
396 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
397 BPF_NOEXIST));
398
399 /* Insert 1+tgt_free*3/2 to tgt_free*5/2 */
400 end_key = key + tgt_free;
401 for (; key < end_key; key++) {
402 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
403 BPF_NOEXIST));
404 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
405 BPF_NOEXIST));
406 }
407
408 assert(map_equal(lru_map_fd, expected_map_fd));
409
410 close(expected_map_fd);
411 close(lru_map_fd);
412
413 printf("Pass\n");
414}
415
416/* Size of the LRU map is 2*tgt_free
417 * It is to test the active/inactive list rotation
418 * Insert 1 to 2*tgt_free (+2*tgt_free keys)
419 * Lookup key 1 to tgt_free*3/2
420 * Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys)
421 * => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU
422 */
423static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free)
424{
425 unsigned long long key, end_key, value[nr_cpus];
426 int lru_map_fd, expected_map_fd;
427 unsigned int batch_size;
428 unsigned int map_size;
429 int next_cpu = 0;
430
431 if (map_flags & BPF_F_NO_COMMON_LRU)
432 /* This test is only applicable to common LRU list */
433 return;
434
435 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
436 map_flags);
437
438 assert(sched_next_online(0, &next_cpu) != -1);
439
440 batch_size = tgt_free / 2;
441 assert(batch_size * 2 == tgt_free);
442
443 map_size = tgt_free * 2;
444 lru_map_fd = create_map(map_type, map_flags, map_size);
445 assert(lru_map_fd != -1);
446
447 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
448 assert(expected_map_fd != -1);
449
450 value[0] = 1234;
451
452 /* Insert 1 to 2*tgt_free (+2*tgt_free keys) */
453 end_key = 1 + (2 * tgt_free);
454 for (key = 1; key < end_key; key++)
455 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
456 BPF_NOEXIST));
457
458 /* Lookup key 1 to tgt_free*3/2 */
459 end_key = tgt_free + batch_size;
460 for (key = 1; key < end_key; key++) {
461 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
462 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
463 BPF_NOEXIST));
464 }
465
466 /* Add 1+2*tgt_free to tgt_free*5/2
467 * (+tgt_free/2 keys)
468 */
469 key = 2 * tgt_free + 1;
470 end_key = key + batch_size;
471 for (; key < end_key; key++) {
472 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
473 BPF_NOEXIST));
474 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
475 BPF_NOEXIST));
476 }
477
478 assert(map_equal(lru_map_fd, expected_map_fd));
479
480 close(expected_map_fd);
481 close(lru_map_fd);
482
483 printf("Pass\n");
484}
485
486/* Test deletion */
487static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free)
488{
489 int lru_map_fd, expected_map_fd;
490 unsigned long long key, value[nr_cpus];
491 unsigned long long end_key;
492 int next_cpu = 0;
493
494 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
495 map_flags);
496
497 assert(sched_next_online(0, &next_cpu) != -1);
498
499 if (map_flags & BPF_F_NO_COMMON_LRU)
500 lru_map_fd = create_map(map_type, map_flags,
501 3 * tgt_free * nr_cpus);
502 else
503 lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free);
504 assert(lru_map_fd != -1);
505
506 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0,
507 3 * tgt_free);
508 assert(expected_map_fd != -1);
509
510 value[0] = 1234;
511
512 for (key = 1; key <= 2 * tgt_free; key++)
513 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
514 BPF_NOEXIST));
515
516 key = 1;
517 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
518
519 for (key = 1; key <= tgt_free; key++) {
520 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
521 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
522 BPF_NOEXIST));
523 }
524
525 for (; key <= 2 * tgt_free; key++) {
526 assert(!bpf_map_delete_elem(lru_map_fd, &key));
527 assert(bpf_map_delete_elem(lru_map_fd, &key));
528 }
529
530 end_key = key + 2 * tgt_free;
531 for (; key < end_key; key++) {
532 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
533 BPF_NOEXIST));
534 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
535 BPF_NOEXIST));
536 }
537
538 assert(map_equal(lru_map_fd, expected_map_fd));
539
540 close(expected_map_fd);
541 close(lru_map_fd);
542
543 printf("Pass\n");
544}
545
546static void do_test_lru_sanity5(unsigned long long last_key, int map_fd)
547{
548 unsigned long long key, value[nr_cpus];
549
550 /* Ensure the last key inserted by previous CPU can be found */
551 assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, last_key, value));
552 value[0] = 1234;
553
554 key = last_key + 1;
555 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
556 assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, key, value));
557
558 /* Cannot find the last key because it was removed by LRU */
559 assert(bpf_map_lookup_elem(map_fd, &last_key, value) == -ENOENT);
560}
561
562/* Test map with only one element */
563static void test_lru_sanity5(int map_type, int map_flags)
564{
565 unsigned long long key, value[nr_cpus];
566 int next_cpu = 0;
567 int map_fd;
568
569 if (map_flags & BPF_F_NO_COMMON_LRU)
570 return;
571
572 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
573 map_flags);
574
575 map_fd = create_map(map_type, map_flags, 1);
576 assert(map_fd != -1);
577
578 value[0] = 1234;
579 key = 0;
580 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
581
582 while (sched_next_online(0, &next_cpu) != -1) {
583 pid_t pid;
584
585 pid = fork();
586 if (pid == 0) {
587 do_test_lru_sanity5(key, map_fd);
588 exit(0);
589 } else if (pid == -1) {
590 printf("couldn't spawn process to test key:%llu\n",
591 key);
592 exit(1);
593 } else {
594 int status;
595
596 assert(waitpid(pid, &status, 0) == pid);
597 assert(status == 0);
598 key++;
599 }
600 }
601
602 close(map_fd);
603 /* At least one key should be tested */
604 assert(key > 0);
605
606 printf("Pass\n");
607}
608
609/* Test list rotation for BPF_F_NO_COMMON_LRU map */
610static void test_lru_sanity6(int map_type, int map_flags, int tgt_free)
611{
612 int lru_map_fd, expected_map_fd;
613 unsigned long long key, value[nr_cpus];
614 unsigned int map_size = tgt_free * 2;
615 int next_cpu = 0;
616
617 if (!(map_flags & BPF_F_NO_COMMON_LRU))
618 return;
619
620 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
621 map_flags);
622
623 assert(sched_next_online(0, &next_cpu) != -1);
624
625 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
626 assert(expected_map_fd != -1);
627
628 lru_map_fd = create_map(map_type, map_flags, map_size * nr_cpus);
629 assert(lru_map_fd != -1);
630
631 value[0] = 1234;
632
633 for (key = 1; key <= tgt_free; key++) {
634 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
635 BPF_NOEXIST));
636 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
637 BPF_NOEXIST));
638 }
639
640 for (; key <= tgt_free * 2; key++) {
641 unsigned long long stable_key;
642
643 /* Make ref bit sticky for key: [1, tgt_free] */
644 for (stable_key = 1; stable_key <= tgt_free; stable_key++) {
645 /* Mark the ref bit */
646 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd,
647 stable_key, value));
648 }
649 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
650 BPF_NOEXIST));
651 }
652
653 for (; key <= tgt_free * 3; key++) {
654 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
655 BPF_NOEXIST));
656 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
657 BPF_NOEXIST));
658 }
659
660 assert(map_equal(lru_map_fd, expected_map_fd));
661
662 close(expected_map_fd);
663 close(lru_map_fd);
664
665 printf("Pass\n");
666}
667
668/* Size of the LRU map is 2
669 * Add key=1 (+1 key)
670 * Add key=2 (+1 key)
671 * Lookup Key=1 (datapath)
672 * Lookup Key=2 (syscall)
673 * Add Key=3
674 * => Key=2 will be removed by LRU
675 * Iterate map. Only found key=1 and key=3
676 */
677static void test_lru_sanity7(int map_type, int map_flags)
678{
679 unsigned long long key, value[nr_cpus];
680 int lru_map_fd, expected_map_fd;
681 int next_cpu = 0;
682
683 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
684 map_flags);
685
686 assert(sched_next_online(0, &next_cpu) != -1);
687
688 if (map_flags & BPF_F_NO_COMMON_LRU)
689 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
690 else
691 lru_map_fd = create_map(map_type, map_flags, 2);
692 assert(lru_map_fd != -1);
693
694 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
695 assert(expected_map_fd != -1);
696
697 value[0] = 1234;
698
699 /* insert key=1 element */
700
701 key = 1;
702 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
703 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
704 BPF_NOEXIST));
705
706 /* BPF_NOEXIST means: add new element if it doesn't exist */
707 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST);
708 /* key=1 already exists */
709
710 /* insert key=2 element */
711
712 /* check that key=2 is not found */
713 key = 2;
714 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
715
716 /* BPF_EXIST means: update existing element */
717 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT);
718 /* key=2 is not there */
719
720 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
721
722 /* insert key=3 element */
723
724 /* check that key=3 is not found */
725 key = 3;
726 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
727
728 /* check that key=1 can be found and mark the ref bit to
729 * stop LRU from removing key=1
730 */
731 key = 1;
732 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
733 assert(value[0] == 1234);
734
735 /* check that key=2 can be found and do _not_ mark ref bit.
736 * this will be evicted on next update.
737 */
738 key = 2;
739 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
740 assert(value[0] == 1234);
741
742 key = 3;
743 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
744 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
745 BPF_NOEXIST));
746
747 /* key=2 has been removed from the LRU */
748 key = 2;
749 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
750
751 assert(map_equal(lru_map_fd, expected_map_fd));
752
753 close(expected_map_fd);
754 close(lru_map_fd);
755
756 printf("Pass\n");
757}
758
759/* Size of the LRU map is 2
760 * Add key=1 (+1 key)
761 * Add key=2 (+1 key)
762 * Lookup Key=1 (syscall)
763 * Lookup Key=2 (datapath)
764 * Add Key=3
765 * => Key=1 will be removed by LRU
766 * Iterate map. Only found key=2 and key=3
767 */
768static void test_lru_sanity8(int map_type, int map_flags)
769{
770 unsigned long long key, value[nr_cpus];
771 int lru_map_fd, expected_map_fd;
772 int next_cpu = 0;
773
774 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
775 map_flags);
776
777 assert(sched_next_online(0, &next_cpu) != -1);
778
779 if (map_flags & BPF_F_NO_COMMON_LRU)
780 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
781 else
782 lru_map_fd = create_map(map_type, map_flags, 2);
783 assert(lru_map_fd != -1);
784
785 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
786 assert(expected_map_fd != -1);
787
788 value[0] = 1234;
789
790 /* insert key=1 element */
791
792 key = 1;
793 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
794
795 /* BPF_NOEXIST means: add new element if it doesn't exist */
796 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST);
797 /* key=1 already exists */
798
799 /* insert key=2 element */
800
801 /* check that key=2 is not found */
802 key = 2;
803 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
804
805 /* BPF_EXIST means: update existing element */
806 assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT);
807 /* key=2 is not there */
808
809 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
810 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
811 BPF_NOEXIST));
812
813 /* insert key=3 element */
814
815 /* check that key=3 is not found */
816 key = 3;
817 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
818
819 /* check that key=1 can be found and do _not_ mark ref bit.
820 * this will be evicted on next update.
821 */
822 key = 1;
823 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
824 assert(value[0] == 1234);
825
826 /* check that key=2 can be found and mark the ref bit to
827 * stop LRU from removing key=2
828 */
829 key = 2;
830 assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
831 assert(value[0] == 1234);
832
833 key = 3;
834 assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
835 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
836 BPF_NOEXIST));
837
838 /* key=1 has been removed from the LRU */
839 key = 1;
840 assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
841
842 assert(map_equal(lru_map_fd, expected_map_fd));
843
844 close(expected_map_fd);
845 close(lru_map_fd);
846
847 printf("Pass\n");
848}
849
850int main(int argc, char **argv)
851{
852 int map_types[] = {BPF_MAP_TYPE_LRU_HASH,
853 BPF_MAP_TYPE_LRU_PERCPU_HASH};
854 int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
855 int t, f;
856
857 setbuf(stdout, NULL);
858
859 nr_cpus = bpf_num_possible_cpus();
860 assert(nr_cpus != -1);
861 printf("nr_cpus:%d\n\n", nr_cpus);
862
863 /* Use libbpf 1.0 API mode */
864 libbpf_set_strict_mode(LIBBPF_STRICT_ALL);
865
866 for (f = 0; f < ARRAY_SIZE(map_flags); f++) {
867 unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ?
868 PERCPU_FREE_TARGET : LOCAL_FREE_TARGET;
869
870 for (t = 0; t < ARRAY_SIZE(map_types); t++) {
871 test_lru_sanity0(map_types[t], map_flags[f]);
872 test_lru_sanity1(map_types[t], map_flags[f], tgt_free);
873 test_lru_sanity2(map_types[t], map_flags[f], tgt_free);
874 test_lru_sanity3(map_types[t], map_flags[f], tgt_free);
875 test_lru_sanity4(map_types[t], map_flags[f], tgt_free);
876 test_lru_sanity5(map_types[t], map_flags[f]);
877 test_lru_sanity6(map_types[t], map_flags[f], tgt_free);
878 test_lru_sanity7(map_types[t], map_flags[f]);
879 test_lru_sanity8(map_types[t], map_flags[f]);
880
881 printf("\n");
882 }
883 }
884
885 return 0;
886}
1/*
2 * Copyright (c) 2016 Facebook
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of version 2 of the GNU General Public
6 * License as published by the Free Software Foundation.
7 */
8#define _GNU_SOURCE
9#include <stdio.h>
10#include <unistd.h>
11#include <errno.h>
12#include <string.h>
13#include <assert.h>
14#include <sched.h>
15#include <stdlib.h>
16#include <time.h>
17
18#include <sys/wait.h>
19#include <sys/resource.h>
20
21#include "bpf_sys.h"
22#include "bpf_util.h"
23
24#define LOCAL_FREE_TARGET (128)
25#define PERCPU_FREE_TARGET (16)
26
27static int nr_cpus;
28
29static int create_map(int map_type, int map_flags, unsigned int size)
30{
31 int map_fd;
32
33 map_fd = bpf_map_create(map_type, sizeof(unsigned long long),
34 sizeof(unsigned long long), size, map_flags);
35
36 if (map_fd == -1)
37 perror("bpf_map_create");
38
39 return map_fd;
40}
41
42static int map_subset(int map0, int map1)
43{
44 unsigned long long next_key = 0;
45 unsigned long long value0[nr_cpus], value1[nr_cpus];
46 int ret;
47
48 while (!bpf_map_next_key(map1, &next_key, &next_key)) {
49 assert(!bpf_map_lookup(map1, &next_key, value1));
50 ret = bpf_map_lookup(map0, &next_key, value0);
51 if (ret) {
52 printf("key:%llu not found from map. %s(%d)\n",
53 next_key, strerror(errno), errno);
54 return 0;
55 }
56 if (value0[0] != value1[0]) {
57 printf("key:%llu value0:%llu != value1:%llu\n",
58 next_key, value0[0], value1[0]);
59 return 0;
60 }
61 }
62 return 1;
63}
64
65static int map_equal(int lru_map, int expected)
66{
67 return map_subset(lru_map, expected) && map_subset(expected, lru_map);
68}
69
70static int sched_next_online(int pid, int *next_to_try)
71{
72 cpu_set_t cpuset;
73 int next = *next_to_try;
74 int ret = -1;
75
76 while (next < nr_cpus) {
77 CPU_ZERO(&cpuset);
78 CPU_SET(next++, &cpuset);
79 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) {
80 ret = 0;
81 break;
82 }
83 }
84
85 *next_to_try = next;
86 return ret;
87}
88
89/* Size of the LRU amp is 2
90 * Add key=1 (+1 key)
91 * Add key=2 (+1 key)
92 * Lookup Key=1
93 * Add Key=3
94 * => Key=2 will be removed by LRU
95 * Iterate map. Only found key=1 and key=3
96 */
97static void test_lru_sanity0(int map_type, int map_flags)
98{
99 unsigned long long key, value[nr_cpus];
100 int lru_map_fd, expected_map_fd;
101 int next_cpu = 0;
102
103 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
104 map_flags);
105
106 assert(sched_next_online(0, &next_cpu) != -1);
107
108 if (map_flags & BPF_F_NO_COMMON_LRU)
109 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
110 else
111 lru_map_fd = create_map(map_type, map_flags, 2);
112 assert(lru_map_fd != -1);
113
114 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
115 assert(expected_map_fd != -1);
116
117 value[0] = 1234;
118
119 /* insert key=1 element */
120
121 key = 1;
122 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
123 assert(!bpf_map_update(expected_map_fd, &key, value, BPF_NOEXIST));
124
125 /* BPF_NOEXIST means: add new element if it doesn't exist */
126 assert(bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST) == -1 &&
127 /* key=1 already exists */
128 errno == EEXIST);
129
130 assert(bpf_map_update(lru_map_fd, &key, value, -1) == -1 &&
131 errno == EINVAL);
132
133 /* insert key=2 element */
134
135 /* check that key=2 is not found */
136 key = 2;
137 assert(bpf_map_lookup(lru_map_fd, &key, value) == -1 &&
138 errno == ENOENT);
139
140 /* BPF_EXIST means: update existing element */
141 assert(bpf_map_update(lru_map_fd, &key, value, BPF_EXIST) == -1 &&
142 /* key=2 is not there */
143 errno == ENOENT);
144
145 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
146
147 /* insert key=3 element */
148
149 /* check that key=3 is not found */
150 key = 3;
151 assert(bpf_map_lookup(lru_map_fd, &key, value) == -1 &&
152 errno == ENOENT);
153
154 /* check that key=1 can be found and mark the ref bit to
155 * stop LRU from removing key=1
156 */
157 key = 1;
158 assert(!bpf_map_lookup(lru_map_fd, &key, value));
159 assert(value[0] == 1234);
160
161 key = 3;
162 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
163 assert(!bpf_map_update(expected_map_fd, &key, value, BPF_NOEXIST));
164
165 /* key=2 has been removed from the LRU */
166 key = 2;
167 assert(bpf_map_lookup(lru_map_fd, &key, value) == -1);
168
169 assert(map_equal(lru_map_fd, expected_map_fd));
170
171 close(expected_map_fd);
172 close(lru_map_fd);
173
174 printf("Pass\n");
175}
176
177/* Size of the LRU map is 1.5*tgt_free
178 * Insert 1 to tgt_free (+tgt_free keys)
179 * Lookup 1 to tgt_free/2
180 * Insert 1+tgt_free to 2*tgt_free (+tgt_free keys)
181 * => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU
182 */
183static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free)
184{
185 unsigned long long key, end_key, value[nr_cpus];
186 int lru_map_fd, expected_map_fd;
187 unsigned int batch_size;
188 unsigned int map_size;
189 int next_cpu = 0;
190
191 if (map_flags & BPF_F_NO_COMMON_LRU)
192 /* Ther percpu lru list (i.e each cpu has its own LRU
193 * list) does not have a local free list. Hence,
194 * it will only free old nodes till there is no free
195 * from the LRU list. Hence, this test does not apply
196 * to BPF_F_NO_COMMON_LRU
197 */
198 return;
199
200 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
201 map_flags);
202
203 assert(sched_next_online(0, &next_cpu) != -1);
204
205 batch_size = tgt_free / 2;
206 assert(batch_size * 2 == tgt_free);
207
208 map_size = tgt_free + batch_size;
209 lru_map_fd = create_map(map_type, map_flags, map_size);
210 assert(lru_map_fd != -1);
211
212 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
213 assert(expected_map_fd != -1);
214
215 value[0] = 1234;
216
217 /* Insert 1 to tgt_free (+tgt_free keys) */
218 end_key = 1 + tgt_free;
219 for (key = 1; key < end_key; key++)
220 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
221
222 /* Lookup 1 to tgt_free/2 */
223 end_key = 1 + batch_size;
224 for (key = 1; key < end_key; key++) {
225 assert(!bpf_map_lookup(lru_map_fd, &key, value));
226 assert(!bpf_map_update(expected_map_fd, &key, value,
227 BPF_NOEXIST));
228 }
229
230 /* Insert 1+tgt_free to 2*tgt_free
231 * => 1+tgt_free/2 to LOCALFREE_TARGET will be
232 * removed by LRU
233 */
234 key = 1 + tgt_free;
235 end_key = key + tgt_free;
236 for (; key < end_key; key++) {
237 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
238 assert(!bpf_map_update(expected_map_fd, &key, value,
239 BPF_NOEXIST));
240 }
241
242 assert(map_equal(lru_map_fd, expected_map_fd));
243
244 close(expected_map_fd);
245 close(lru_map_fd);
246
247 printf("Pass\n");
248}
249
250/* Size of the LRU map 1.5 * tgt_free
251 * Insert 1 to tgt_free (+tgt_free keys)
252 * Update 1 to tgt_free/2
253 * => The original 1 to tgt_free/2 will be removed due to
254 * the LRU shrink process
255 * Re-insert 1 to tgt_free/2 again and do a lookup immeidately
256 * Insert 1+tgt_free to tgt_free*3/2
257 * Insert 1+tgt_free*3/2 to tgt_free*5/2
258 * => Key 1+tgt_free to tgt_free*3/2
259 * will be removed from LRU because it has never
260 * been lookup and ref bit is not set
261 */
262static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free)
263{
264 unsigned long long key, value[nr_cpus];
265 unsigned long long end_key;
266 int lru_map_fd, expected_map_fd;
267 unsigned int batch_size;
268 unsigned int map_size;
269 int next_cpu = 0;
270
271 if (map_flags & BPF_F_NO_COMMON_LRU)
272 /* Ther percpu lru list (i.e each cpu has its own LRU
273 * list) does not have a local free list. Hence,
274 * it will only free old nodes till there is no free
275 * from the LRU list. Hence, this test does not apply
276 * to BPF_F_NO_COMMON_LRU
277 */
278 return;
279
280 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
281 map_flags);
282
283 assert(sched_next_online(0, &next_cpu) != -1);
284
285 batch_size = tgt_free / 2;
286 assert(batch_size * 2 == tgt_free);
287
288 map_size = tgt_free + batch_size;
289 if (map_flags & BPF_F_NO_COMMON_LRU)
290 lru_map_fd = create_map(map_type, map_flags,
291 map_size * nr_cpus);
292 else
293 lru_map_fd = create_map(map_type, map_flags, map_size);
294 assert(lru_map_fd != -1);
295
296 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
297 assert(expected_map_fd != -1);
298
299 value[0] = 1234;
300
301 /* Insert 1 to tgt_free (+tgt_free keys) */
302 end_key = 1 + tgt_free;
303 for (key = 1; key < end_key; key++)
304 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
305
306 /* Any bpf_map_update will require to acquire a new node
307 * from LRU first.
308 *
309 * The local list is running out of free nodes.
310 * It gets from the global LRU list which tries to
311 * shrink the inactive list to get tgt_free
312 * number of free nodes.
313 *
314 * Hence, the oldest key 1 to tgt_free/2
315 * are removed from the LRU list.
316 */
317 key = 1;
318 if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
319 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
320 assert(!bpf_map_delete(lru_map_fd, &key));
321 } else {
322 assert(bpf_map_update(lru_map_fd, &key, value, BPF_EXIST));
323 }
324
325 /* Re-insert 1 to tgt_free/2 again and do a lookup
326 * immeidately.
327 */
328 end_key = 1 + batch_size;
329 value[0] = 4321;
330 for (key = 1; key < end_key; key++) {
331 assert(bpf_map_lookup(lru_map_fd, &key, value));
332 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
333 assert(!bpf_map_lookup(lru_map_fd, &key, value));
334 assert(value[0] == 4321);
335 assert(!bpf_map_update(expected_map_fd, &key, value,
336 BPF_NOEXIST));
337 }
338
339 value[0] = 1234;
340
341 /* Insert 1+tgt_free to tgt_free*3/2 */
342 end_key = 1 + tgt_free + batch_size;
343 for (key = 1 + tgt_free; key < end_key; key++)
344 /* These newly added but not referenced keys will be
345 * gone during the next LRU shrink.
346 */
347 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
348
349 /* Insert 1+tgt_free*3/2 to tgt_free*5/2 */
350 end_key = key + tgt_free;
351 for (; key < end_key; key++) {
352 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
353 assert(!bpf_map_update(expected_map_fd, &key, value,
354 BPF_NOEXIST));
355 }
356
357 assert(map_equal(lru_map_fd, expected_map_fd));
358
359 close(expected_map_fd);
360 close(lru_map_fd);
361
362 printf("Pass\n");
363}
364
365/* Size of the LRU map is 2*tgt_free
366 * It is to test the active/inactive list rotation
367 * Insert 1 to 2*tgt_free (+2*tgt_free keys)
368 * Lookup key 1 to tgt_free*3/2
369 * Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys)
370 * => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU
371 */
372static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free)
373{
374 unsigned long long key, end_key, value[nr_cpus];
375 int lru_map_fd, expected_map_fd;
376 unsigned int batch_size;
377 unsigned int map_size;
378 int next_cpu = 0;
379
380 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
381 map_flags);
382
383 assert(sched_next_online(0, &next_cpu) != -1);
384
385 batch_size = tgt_free / 2;
386 assert(batch_size * 2 == tgt_free);
387
388 map_size = tgt_free * 2;
389 if (map_flags & BPF_F_NO_COMMON_LRU)
390 lru_map_fd = create_map(map_type, map_flags,
391 map_size * nr_cpus);
392 else
393 lru_map_fd = create_map(map_type, map_flags, map_size);
394 assert(lru_map_fd != -1);
395
396 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
397 assert(expected_map_fd != -1);
398
399 value[0] = 1234;
400
401 /* Insert 1 to 2*tgt_free (+2*tgt_free keys) */
402 end_key = 1 + (2 * tgt_free);
403 for (key = 1; key < end_key; key++)
404 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
405
406 /* Lookup key 1 to tgt_free*3/2 */
407 end_key = tgt_free + batch_size;
408 for (key = 1; key < end_key; key++) {
409 assert(!bpf_map_lookup(lru_map_fd, &key, value));
410 assert(!bpf_map_update(expected_map_fd, &key, value,
411 BPF_NOEXIST));
412 }
413
414 /* Add 1+2*tgt_free to tgt_free*5/2
415 * (+tgt_free/2 keys)
416 */
417 key = 2 * tgt_free + 1;
418 end_key = key + batch_size;
419 for (; key < end_key; key++) {
420 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
421 assert(!bpf_map_update(expected_map_fd, &key, value,
422 BPF_NOEXIST));
423 }
424
425 assert(map_equal(lru_map_fd, expected_map_fd));
426
427 close(expected_map_fd);
428 close(lru_map_fd);
429
430 printf("Pass\n");
431}
432
433/* Test deletion */
434static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free)
435{
436 int lru_map_fd, expected_map_fd;
437 unsigned long long key, value[nr_cpus];
438 unsigned long long end_key;
439 int next_cpu = 0;
440
441 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
442 map_flags);
443
444 assert(sched_next_online(0, &next_cpu) != -1);
445
446 if (map_flags & BPF_F_NO_COMMON_LRU)
447 lru_map_fd = create_map(map_type, map_flags,
448 3 * tgt_free * nr_cpus);
449 else
450 lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free);
451 assert(lru_map_fd != -1);
452
453 expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0,
454 3 * tgt_free);
455 assert(expected_map_fd != -1);
456
457 value[0] = 1234;
458
459 for (key = 1; key <= 2 * tgt_free; key++)
460 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
461
462 key = 1;
463 assert(bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
464
465 for (key = 1; key <= tgt_free; key++) {
466 assert(!bpf_map_lookup(lru_map_fd, &key, value));
467 assert(!bpf_map_update(expected_map_fd, &key, value,
468 BPF_NOEXIST));
469 }
470
471 for (; key <= 2 * tgt_free; key++) {
472 assert(!bpf_map_delete(lru_map_fd, &key));
473 assert(bpf_map_delete(lru_map_fd, &key));
474 }
475
476 end_key = key + 2 * tgt_free;
477 for (; key < end_key; key++) {
478 assert(!bpf_map_update(lru_map_fd, &key, value, BPF_NOEXIST));
479 assert(!bpf_map_update(expected_map_fd, &key, value,
480 BPF_NOEXIST));
481 }
482
483 assert(map_equal(lru_map_fd, expected_map_fd));
484
485 close(expected_map_fd);
486 close(lru_map_fd);
487
488 printf("Pass\n");
489}
490
491static void do_test_lru_sanity5(unsigned long long last_key, int map_fd)
492{
493 unsigned long long key, value[nr_cpus];
494
495 /* Ensure the last key inserted by previous CPU can be found */
496 assert(!bpf_map_lookup(map_fd, &last_key, value));
497
498 value[0] = 1234;
499
500 key = last_key + 1;
501 assert(!bpf_map_update(map_fd, &key, value, BPF_NOEXIST));
502 assert(!bpf_map_lookup(map_fd, &key, value));
503
504 /* Cannot find the last key because it was removed by LRU */
505 assert(bpf_map_lookup(map_fd, &last_key, value));
506}
507
508/* Test map with only one element */
509static void test_lru_sanity5(int map_type, int map_flags)
510{
511 unsigned long long key, value[nr_cpus];
512 int next_cpu = 0;
513 int map_fd;
514
515 if (map_flags & BPF_F_NO_COMMON_LRU)
516 return;
517
518 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
519 map_flags);
520
521 map_fd = create_map(map_type, map_flags, 1);
522 assert(map_fd != -1);
523
524 value[0] = 1234;
525 key = 0;
526 assert(!bpf_map_update(map_fd, &key, value, BPF_NOEXIST));
527
528 while (sched_next_online(0, &next_cpu) != -1) {
529 pid_t pid;
530
531 pid = fork();
532 if (pid == 0) {
533 do_test_lru_sanity5(key, map_fd);
534 exit(0);
535 } else if (pid == -1) {
536 printf("couldn't spawn process to test key:%llu\n",
537 key);
538 exit(1);
539 } else {
540 int status;
541
542 assert(waitpid(pid, &status, 0) == pid);
543 assert(status == 0);
544 key++;
545 }
546 }
547
548 close(map_fd);
549 /* At least one key should be tested */
550 assert(key > 0);
551
552 printf("Pass\n");
553}
554
555int main(int argc, char **argv)
556{
557 struct rlimit r = {RLIM_INFINITY, RLIM_INFINITY};
558 int map_types[] = {BPF_MAP_TYPE_LRU_HASH,
559 BPF_MAP_TYPE_LRU_PERCPU_HASH};
560 int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
561 int t, f;
562
563 setbuf(stdout, NULL);
564
565 assert(!setrlimit(RLIMIT_MEMLOCK, &r));
566
567 nr_cpus = bpf_num_possible_cpus();
568 assert(nr_cpus != -1);
569 printf("nr_cpus:%d\n\n", nr_cpus);
570
571 for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) {
572 unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ?
573 PERCPU_FREE_TARGET : LOCAL_FREE_TARGET;
574
575 for (t = 0; t < sizeof(map_types) / sizeof(*map_types); t++) {
576 test_lru_sanity0(map_types[t], map_flags[f]);
577 test_lru_sanity1(map_types[t], map_flags[f], tgt_free);
578 test_lru_sanity2(map_types[t], map_flags[f], tgt_free);
579 test_lru_sanity3(map_types[t], map_flags[f], tgt_free);
580 test_lru_sanity4(map_types[t], map_flags[f], tgt_free);
581 test_lru_sanity5(map_types[t], map_flags[f]);
582
583 printf("\n");
584 }
585 }
586
587 return 0;
588}