Newer
Older
// SPDX-License-Identifier: GPL-2.0-only
/*
* Copyright (c) 2016 Facebook
*/
#define _GNU_SOURCE
#include <stdio.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <assert.h>
#include <sched.h>
#include <stdlib.h>
#include <time.h>
#include <sys/wait.h>
#include <bpf/libbpf.h>
#include "bpf_util.h"
#include "../../../include/linux/filter.h"
#define LOCAL_FREE_TARGET (128)
#define PERCPU_FREE_TARGET (4)
static int nr_cpus;
static int create_map(int map_type, int map_flags, unsigned int size)
{
int map_fd;
map_fd = bpf_create_map(map_type, sizeof(unsigned long long),
sizeof(unsigned long long), size, map_flags);
if (map_fd == -1)
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
static int bpf_map_lookup_elem_with_ref_bit(int fd, unsigned long long key,
void *value)
{
struct bpf_load_program_attr prog;
struct bpf_create_map_attr map;
struct bpf_insn insns[] = {
BPF_LD_MAP_VALUE(BPF_REG_9, 0, 0),
BPF_LD_MAP_FD(BPF_REG_1, fd),
BPF_LD_IMM64(BPF_REG_3, key),
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
BPF_STX_MEM(BPF_DW, BPF_REG_2, BPF_REG_3, 0),
BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4),
BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
BPF_STX_MEM(BPF_DW, BPF_REG_9, BPF_REG_1, 0),
BPF_MOV64_IMM(BPF_REG_0, 42),
BPF_JMP_IMM(BPF_JA, 0, 0, 1),
BPF_MOV64_IMM(BPF_REG_0, 1),
BPF_EXIT_INSN(),
};
__u8 data[64] = {};
int mfd, pfd, ret, zero = 0;
__u32 retval = 0;
memset(&map, 0, sizeof(map));
map.map_type = BPF_MAP_TYPE_ARRAY;
map.key_size = sizeof(int);
map.value_size = sizeof(unsigned long long);
map.max_entries = 1;
mfd = bpf_create_map_xattr(&map);
if (mfd < 0)
return -1;
insns[0].imm = mfd;
memset(&prog, 0, sizeof(prog));
prog.prog_type = BPF_PROG_TYPE_SCHED_CLS;
prog.insns = insns;
prog.insns_cnt = ARRAY_SIZE(insns);
prog.license = "GPL";
pfd = bpf_load_program_xattr(&prog, NULL, 0);
if (pfd < 0) {
close(mfd);
return -1;
}
ret = bpf_prog_test_run(pfd, 1, data, sizeof(data),
NULL, NULL, &retval, NULL);
if (ret < 0 || retval != 42) {
ret = -1;
} else {
assert(!bpf_map_lookup_elem(mfd, &zero, value));
ret = 0;
}
close(pfd);
close(mfd);
return ret;
}
static int map_subset(int map0, int map1)
{
unsigned long long next_key = 0;
unsigned long long value0[nr_cpus], value1[nr_cpus];
int ret;
while (!bpf_map_get_next_key(map1, &next_key, &next_key)) {
assert(!bpf_map_lookup_elem(map1, &next_key, value1));
ret = bpf_map_lookup_elem(map0, &next_key, value0);
if (ret) {
printf("key:%llu not found from map. %s(%d)\n",
next_key, strerror(errno), errno);
return 0;
}
if (value0[0] != value1[0]) {
printf("key:%llu value0:%llu != value1:%llu\n",
next_key, value0[0], value1[0]);
return 0;
}
}
return 1;
}
static int map_equal(int lru_map, int expected)
{
return map_subset(lru_map, expected) && map_subset(expected, lru_map);
}
static int sched_next_online(int pid, int *next_to_try)
int next = *next_to_try;
int ret = -1;
while (next < nr_cpus) {
CPU_SET(next++, &cpuset);
if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) {
ret = 0;
*next_to_try = next;
return ret;
/* Size of the LRU map is 2
* Add key=1 (+1 key)
* Add key=2 (+1 key)
* Lookup Key=1
* Add Key=3
* => Key=2 will be removed by LRU
* Iterate map. Only found key=1 and key=3
*/
static void test_lru_sanity0(int map_type, int map_flags)
{
unsigned long long key, value[nr_cpus];
int lru_map_fd, expected_map_fd;
printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
map_flags);
assert(sched_next_online(0, &next_cpu) != -1);
if (map_flags & BPF_F_NO_COMMON_LRU)
lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
else
lru_map_fd = create_map(map_type, map_flags, 2);
assert(lru_map_fd != -1);
expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
assert(expected_map_fd != -1);
value[0] = 1234;
/* insert key=1 element */
key = 1;
assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
/* BPF_NOEXIST means: add new element if it doesn't exist */
assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -1
assert(bpf_map_update_elem(lru_map_fd, &key, value, -1) == -1 &&
errno == EINVAL);
/* insert key=2 element */
/* check that key=2 is not found */
key = 2;
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
/* BPF_EXIST means: update existing element */
assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -1 &&
/* key=2 is not there */
errno == ENOENT);
assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
/* insert key=3 element */
/* check that key=3 is not found */
key = 3;
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
/* check that key=1 can be found and mark the ref bit to
* stop LRU from removing key=1
*/
key = 1;
assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
assert(value[0] == 1234);
key = 3;
assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
/* key=2 has been removed from the LRU */
key = 2;
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
assert(map_equal(lru_map_fd, expected_map_fd));
close(expected_map_fd);
close(lru_map_fd);
printf("Pass\n");
}
/* Size of the LRU map is 1.5*tgt_free
* Insert 1 to tgt_free (+tgt_free keys)
* Lookup 1 to tgt_free/2
* Insert 1+tgt_free to 2*tgt_free (+tgt_free keys)
* => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU
*/
static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free)
{
unsigned long long key, end_key, value[nr_cpus];
int lru_map_fd, expected_map_fd;
unsigned int batch_size;
unsigned int map_size;
if (map_flags & BPF_F_NO_COMMON_LRU)
/* This test is only applicable to common LRU list */
return;
printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
map_flags);
assert(sched_next_online(0, &next_cpu) != -1);
batch_size = tgt_free / 2;
assert(batch_size * 2 == tgt_free);
map_size = tgt_free + batch_size;
lru_map_fd = create_map(map_type, map_flags, map_size);
assert(lru_map_fd != -1);
expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
assert(expected_map_fd != -1);
value[0] = 1234;
/* Insert 1 to tgt_free (+tgt_free keys) */
end_key = 1 + tgt_free;
for (key = 1; key < end_key; key++)
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
/* Lookup 1 to tgt_free/2 */
end_key = 1 + batch_size;
for (key = 1; key < end_key; key++) {
assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
}
/* Insert 1+tgt_free to 2*tgt_free
* => 1+tgt_free/2 to LOCALFREE_TARGET will be
* removed by LRU
*/
key = 1 + tgt_free;
end_key = key + tgt_free;
for (; key < end_key; key++) {
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
}
assert(map_equal(lru_map_fd, expected_map_fd));
close(expected_map_fd);
close(lru_map_fd);
printf("Pass\n");
}
/* Size of the LRU map 1.5 * tgt_free
* Insert 1 to tgt_free (+tgt_free keys)
* Update 1 to tgt_free/2
* => The original 1 to tgt_free/2 will be removed due to
* the LRU shrink process
* Re-insert 1 to tgt_free/2 again and do a lookup immeidately
* Insert 1+tgt_free to tgt_free*3/2
* Insert 1+tgt_free*3/2 to tgt_free*5/2
* => Key 1+tgt_free to tgt_free*3/2
* will be removed from LRU because it has never
* been lookup and ref bit is not set
*/
static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free)
{
unsigned long long key, value[nr_cpus];
unsigned long long end_key;
int lru_map_fd, expected_map_fd;
unsigned int batch_size;
unsigned int map_size;
if (map_flags & BPF_F_NO_COMMON_LRU)
/* This test is only applicable to common LRU list */
return;
printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
map_flags);
assert(sched_next_online(0, &next_cpu) != -1);
batch_size = tgt_free / 2;
assert(batch_size * 2 == tgt_free);
map_size = tgt_free + batch_size;
lru_map_fd = create_map(map_type, map_flags, map_size);
assert(lru_map_fd != -1);
expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
assert(expected_map_fd != -1);
value[0] = 1234;
/* Insert 1 to tgt_free (+tgt_free keys) */
end_key = 1 + tgt_free;
for (key = 1; key < end_key; key++)
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
/* Any bpf_map_update_elem will require to acquire a new node
* from LRU first.
*
* The local list is running out of free nodes.
* It gets from the global LRU list which tries to
* shrink the inactive list to get tgt_free
* number of free nodes.
*
* Hence, the oldest key 1 to tgt_free/2
* are removed from the LRU list.
*/
key = 1;
if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
assert(!bpf_map_delete_elem(lru_map_fd, &key));
assert(bpf_map_update_elem(lru_map_fd, &key, value,
BPF_EXIST));
}
/* Re-insert 1 to tgt_free/2 again and do a lookup
* immeidately.
*/
end_key = 1 + batch_size;
value[0] = 4321;
for (key = 1; key < end_key; key++) {
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
}
value[0] = 1234;
/* Insert 1+tgt_free to tgt_free*3/2 */
end_key = 1 + tgt_free + batch_size;
for (key = 1 + tgt_free; key < end_key; key++)
/* These newly added but not referenced keys will be
* gone during the next LRU shrink.
*/
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
/* Insert 1+tgt_free*3/2 to tgt_free*5/2 */
end_key = key + tgt_free;
for (; key < end_key; key++) {
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
}
assert(map_equal(lru_map_fd, expected_map_fd));
close(expected_map_fd);
close(lru_map_fd);
printf("Pass\n");
}
/* Size of the LRU map is 2*tgt_free
* It is to test the active/inactive list rotation
* Insert 1 to 2*tgt_free (+2*tgt_free keys)
* Lookup key 1 to tgt_free*3/2
* Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys)
* => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU
*/
static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free)
{
unsigned long long key, end_key, value[nr_cpus];
int lru_map_fd, expected_map_fd;
unsigned int batch_size;
unsigned int map_size;
if (map_flags & BPF_F_NO_COMMON_LRU)
/* This test is only applicable to common LRU list */
return;
printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
map_flags);
assert(sched_next_online(0, &next_cpu) != -1);
batch_size = tgt_free / 2;
assert(batch_size * 2 == tgt_free);
map_size = tgt_free * 2;
lru_map_fd = create_map(map_type, map_flags, map_size);
assert(lru_map_fd != -1);
expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
assert(expected_map_fd != -1);
value[0] = 1234;
/* Insert 1 to 2*tgt_free (+2*tgt_free keys) */
end_key = 1 + (2 * tgt_free);
for (key = 1; key < end_key; key++)
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
/* Lookup key 1 to tgt_free*3/2 */
end_key = tgt_free + batch_size;
for (key = 1; key < end_key; key++) {
assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
}
/* Add 1+2*tgt_free to tgt_free*5/2
* (+tgt_free/2 keys)
*/
key = 2 * tgt_free + 1;
end_key = key + batch_size;
for (; key < end_key; key++) {
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
}
assert(map_equal(lru_map_fd, expected_map_fd));
close(expected_map_fd);
close(lru_map_fd);
printf("Pass\n");
}
/* Test deletion */
static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free)
{
int lru_map_fd, expected_map_fd;
unsigned long long key, value[nr_cpus];
unsigned long long end_key;
printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
map_flags);
assert(sched_next_online(0, &next_cpu) != -1);
if (map_flags & BPF_F_NO_COMMON_LRU)
lru_map_fd = create_map(map_type, map_flags,
3 * tgt_free * nr_cpus);
else
lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free);
assert(lru_map_fd != -1);
expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0,
3 * tgt_free);
assert(expected_map_fd != -1);
value[0] = 1234;
for (key = 1; key <= 2 * tgt_free; key++)
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
for (key = 1; key <= tgt_free; key++) {
assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
}
for (; key <= 2 * tgt_free; key++) {
assert(!bpf_map_delete_elem(lru_map_fd, &key));
assert(bpf_map_delete_elem(lru_map_fd, &key));
}
end_key = key + 2 * tgt_free;
for (; key < end_key; key++) {
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
}
assert(map_equal(lru_map_fd, expected_map_fd));
close(expected_map_fd);
close(lru_map_fd);
printf("Pass\n");
}
static void do_test_lru_sanity5(unsigned long long last_key, int map_fd)
{
unsigned long long key, value[nr_cpus];
/* Ensure the last key inserted by previous CPU can be found */
assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, last_key, value));
value[0] = 1234;
key = last_key + 1;
assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, key, value));
/* Cannot find the last key because it was removed by LRU */
assert(bpf_map_lookup_elem(map_fd, &last_key, value) == -1 &&
errno == ENOENT);
}
/* Test map with only one element */
static void test_lru_sanity5(int map_type, int map_flags)
{
unsigned long long key, value[nr_cpus];
int map_fd;
if (map_flags & BPF_F_NO_COMMON_LRU)
return;
printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
map_flags);
map_fd = create_map(map_type, map_flags, 1);
assert(map_fd != -1);
value[0] = 1234;
key = 0;
assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
while (sched_next_online(0, &next_cpu) != -1) {
pid_t pid;
pid = fork();
if (pid == 0) {
do_test_lru_sanity5(key, map_fd);
exit(0);
} else if (pid == -1) {
printf("couldn't spawn process to test key:%llu\n",
key);
exit(1);
} else {
int status;
assert(waitpid(pid, &status, 0) == pid);
assert(status == 0);
key++;
}
}
close(map_fd);
/* At least one key should be tested */
assert(key > 0);
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
/* Test list rotation for BPF_F_NO_COMMON_LRU map */
static void test_lru_sanity6(int map_type, int map_flags, int tgt_free)
{
int lru_map_fd, expected_map_fd;
unsigned long long key, value[nr_cpus];
unsigned int map_size = tgt_free * 2;
int next_cpu = 0;
if (!(map_flags & BPF_F_NO_COMMON_LRU))
return;
printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
map_flags);
assert(sched_next_online(0, &next_cpu) != -1);
expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
assert(expected_map_fd != -1);
lru_map_fd = create_map(map_type, map_flags, map_size * nr_cpus);
assert(lru_map_fd != -1);
value[0] = 1234;
for (key = 1; key <= tgt_free; key++) {
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
}
for (; key <= tgt_free * 2; key++) {
unsigned long long stable_key;
/* Make ref bit sticky for key: [1, tgt_free] */
for (stable_key = 1; stable_key <= tgt_free; stable_key++) {
/* Mark the ref bit */
assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd,
stable_key, value));
}
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
}
for (; key <= tgt_free * 3; key++) {
assert(!bpf_map_update_elem(lru_map_fd, &key, value,
BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
}
assert(map_equal(lru_map_fd, expected_map_fd));
close(expected_map_fd);
close(lru_map_fd);
printf("Pass\n");
}
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
/* Size of the LRU map is 2
* Add key=1 (+1 key)
* Add key=2 (+1 key)
* Lookup Key=1 (datapath)
* Lookup Key=2 (syscall)
* Add Key=3
* => Key=2 will be removed by LRU
* Iterate map. Only found key=1 and key=3
*/
static void test_lru_sanity7(int map_type, int map_flags)
{
unsigned long long key, value[nr_cpus];
int lru_map_fd, expected_map_fd;
int next_cpu = 0;
printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
map_flags);
assert(sched_next_online(0, &next_cpu) != -1);
if (map_flags & BPF_F_NO_COMMON_LRU)
lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
else
lru_map_fd = create_map(map_type, map_flags, 2);
assert(lru_map_fd != -1);
expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
assert(expected_map_fd != -1);
value[0] = 1234;
/* insert key=1 element */
key = 1;
assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
/* BPF_NOEXIST means: add new element if it doesn't exist */
assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -1
/* key=1 already exists */
&& errno == EEXIST);
/* insert key=2 element */
/* check that key=2 is not found */
key = 2;
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
/* BPF_EXIST means: update existing element */
assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -1 &&
/* key=2 is not there */
errno == ENOENT);
assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
/* insert key=3 element */
/* check that key=3 is not found */
key = 3;
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
/* check that key=1 can be found and mark the ref bit to
* stop LRU from removing key=1
*/
key = 1;
assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
assert(value[0] == 1234);
/* check that key=2 can be found and do _not_ mark ref bit.
* this will be evicted on next update.
*/
key = 2;
assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
assert(value[0] == 1234);
key = 3;
assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
/* key=2 has been removed from the LRU */
key = 2;
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
assert(map_equal(lru_map_fd, expected_map_fd));
close(expected_map_fd);
close(lru_map_fd);
printf("Pass\n");
}
/* Size of the LRU map is 2
* Add key=1 (+1 key)
* Add key=2 (+1 key)
* Lookup Key=1 (syscall)
* Lookup Key=2 (datapath)
* Add Key=3
* => Key=1 will be removed by LRU
* Iterate map. Only found key=2 and key=3
*/
static void test_lru_sanity8(int map_type, int map_flags)
{
unsigned long long key, value[nr_cpus];
int lru_map_fd, expected_map_fd;
int next_cpu = 0;
printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
map_flags);
assert(sched_next_online(0, &next_cpu) != -1);
if (map_flags & BPF_F_NO_COMMON_LRU)
lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
else
lru_map_fd = create_map(map_type, map_flags, 2);
assert(lru_map_fd != -1);
expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
assert(expected_map_fd != -1);
value[0] = 1234;
/* insert key=1 element */
key = 1;
assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
/* BPF_NOEXIST means: add new element if it doesn't exist */
assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -1
/* key=1 already exists */
&& errno == EEXIST);
/* insert key=2 element */
/* check that key=2 is not found */
key = 2;
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
/* BPF_EXIST means: update existing element */
assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -1 &&
/* key=2 is not there */
errno == ENOENT);
assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
/* insert key=3 element */
/* check that key=3 is not found */
key = 3;
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
/* check that key=1 can be found and do _not_ mark ref bit.
* this will be evicted on next update.
*/
key = 1;
assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
assert(value[0] == 1234);
/* check that key=2 can be found and mark the ref bit to
* stop LRU from removing key=2
*/
key = 2;
assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
assert(value[0] == 1234);
key = 3;
assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
assert(!bpf_map_update_elem(expected_map_fd, &key, value,
BPF_NOEXIST));
/* key=1 has been removed from the LRU */
key = 1;
assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
errno == ENOENT);
assert(map_equal(lru_map_fd, expected_map_fd));
close(expected_map_fd);
close(lru_map_fd);
printf("Pass\n");
}
int main(int argc, char **argv)
{
int map_types[] = {BPF_MAP_TYPE_LRU_HASH,
BPF_MAP_TYPE_LRU_PERCPU_HASH};
int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
int t, f;
setbuf(stdout, NULL);
nr_cpus = bpf_num_possible_cpus();
assert(nr_cpus != -1);
printf("nr_cpus:%d\n\n", nr_cpus);
for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) {
unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ?
PERCPU_FREE_TARGET : LOCAL_FREE_TARGET;
for (t = 0; t < sizeof(map_types) / sizeof(*map_types); t++) {
test_lru_sanity0(map_types[t], map_flags[f]);
test_lru_sanity1(map_types[t], map_flags[f], tgt_free);
test_lru_sanity2(map_types[t], map_flags[f], tgt_free);
test_lru_sanity3(map_types[t], map_flags[f], tgt_free);
test_lru_sanity4(map_types[t], map_flags[f], tgt_free);
test_lru_sanity5(map_types[t], map_flags[f]);
test_lru_sanity6(map_types[t], map_flags[f], tgt_free);
test_lru_sanity7(map_types[t], map_flags[f]);
test_lru_sanity8(map_types[t], map_flags[f]);
printf("\n");
}
}
return 0;
}