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