Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * Copyright (c) 2016 Facebook
0004  */
0005 #define _GNU_SOURCE
0006 #include <stdio.h>
0007 #include <unistd.h>
0008 #include <errno.h>
0009 #include <string.h>
0010 #include <assert.h>
0011 #include <sched.h>
0012 #include <stdlib.h>
0013 #include <time.h>
0014 
0015 #include <sys/wait.h>
0016 
0017 #include <bpf/bpf.h>
0018 #include <bpf/libbpf.h>
0019 
0020 #include "bpf_util.h"
0021 #include "../../../include/linux/filter.h"
0022 
0023 #define LOCAL_FREE_TARGET   (128)
0024 #define PERCPU_FREE_TARGET  (4)
0025 
0026 static int nr_cpus;
0027 
0028 static int create_map(int map_type, int map_flags, unsigned int size)
0029 {
0030     LIBBPF_OPTS(bpf_map_create_opts, opts, .map_flags = map_flags);
0031     int map_fd;
0032 
0033     map_fd = bpf_map_create(map_type, NULL,  sizeof(unsigned long long),
0034                 sizeof(unsigned long long), size, &opts);
0035 
0036     if (map_fd == -1)
0037         perror("bpf_map_create");
0038 
0039     return map_fd;
0040 }
0041 
0042 static int bpf_map_lookup_elem_with_ref_bit(int fd, unsigned long long key,
0043                         void *value)
0044 {
0045     struct bpf_insn insns[] = {
0046         BPF_LD_MAP_VALUE(BPF_REG_9, 0, 0),
0047         BPF_LD_MAP_FD(BPF_REG_1, fd),
0048         BPF_LD_IMM64(BPF_REG_3, key),
0049         BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
0050         BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
0051         BPF_STX_MEM(BPF_DW, BPF_REG_2, BPF_REG_3, 0),
0052         BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
0053         BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4),
0054         BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
0055         BPF_STX_MEM(BPF_DW, BPF_REG_9, BPF_REG_1, 0),
0056         BPF_MOV64_IMM(BPF_REG_0, 42),
0057         BPF_JMP_IMM(BPF_JA, 0, 0, 1),
0058         BPF_MOV64_IMM(BPF_REG_0, 1),
0059         BPF_EXIT_INSN(),
0060     };
0061     __u8 data[64] = {};
0062     int mfd, pfd, ret, zero = 0;
0063     LIBBPF_OPTS(bpf_test_run_opts, topts,
0064         .data_in = data,
0065         .data_size_in = sizeof(data),
0066         .repeat = 1,
0067     );
0068 
0069     mfd = bpf_map_create(BPF_MAP_TYPE_ARRAY, NULL, sizeof(int), sizeof(__u64), 1, NULL);
0070     if (mfd < 0)
0071         return -1;
0072 
0073     insns[0].imm = mfd;
0074 
0075     pfd = bpf_prog_load(BPF_PROG_TYPE_SCHED_CLS, NULL, "GPL", insns, ARRAY_SIZE(insns), NULL);
0076     if (pfd < 0) {
0077         close(mfd);
0078         return -1;
0079     }
0080 
0081     ret = bpf_prog_test_run_opts(pfd, &topts);
0082     if (ret < 0 || topts.retval != 42) {
0083         ret = -1;
0084     } else {
0085         assert(!bpf_map_lookup_elem(mfd, &zero, value));
0086         ret = 0;
0087     }
0088     close(pfd);
0089     close(mfd);
0090     return ret;
0091 }
0092 
0093 static int map_subset(int map0, int map1)
0094 {
0095     unsigned long long next_key = 0;
0096     unsigned long long value0[nr_cpus], value1[nr_cpus];
0097     int ret;
0098 
0099     while (!bpf_map_get_next_key(map1, &next_key, &next_key)) {
0100         assert(!bpf_map_lookup_elem(map1, &next_key, value1));
0101         ret = bpf_map_lookup_elem(map0, &next_key, value0);
0102         if (ret) {
0103             printf("key:%llu not found from map. %s(%d)\n",
0104                    next_key, strerror(errno), errno);
0105             return 0;
0106         }
0107         if (value0[0] != value1[0]) {
0108             printf("key:%llu value0:%llu != value1:%llu\n",
0109                    next_key, value0[0], value1[0]);
0110             return 0;
0111         }
0112     }
0113     return 1;
0114 }
0115 
0116 static int map_equal(int lru_map, int expected)
0117 {
0118     return map_subset(lru_map, expected) && map_subset(expected, lru_map);
0119 }
0120 
0121 static int sched_next_online(int pid, int *next_to_try)
0122 {
0123     cpu_set_t cpuset;
0124     int next = *next_to_try;
0125     int ret = -1;
0126 
0127     while (next < nr_cpus) {
0128         CPU_ZERO(&cpuset);
0129         CPU_SET(next++, &cpuset);
0130         if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) {
0131             ret = 0;
0132             break;
0133         }
0134     }
0135 
0136     *next_to_try = next;
0137     return ret;
0138 }
0139 
0140 /* Size of the LRU map is 2
0141  * Add key=1 (+1 key)
0142  * Add key=2 (+1 key)
0143  * Lookup Key=1
0144  * Add Key=3
0145  *   => Key=2 will be removed by LRU
0146  * Iterate map.  Only found key=1 and key=3
0147  */
0148 static void test_lru_sanity0(int map_type, int map_flags)
0149 {
0150     unsigned long long key, value[nr_cpus];
0151     int lru_map_fd, expected_map_fd;
0152     int next_cpu = 0;
0153 
0154     printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
0155            map_flags);
0156 
0157     assert(sched_next_online(0, &next_cpu) != -1);
0158 
0159     if (map_flags & BPF_F_NO_COMMON_LRU)
0160         lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
0161     else
0162         lru_map_fd = create_map(map_type, map_flags, 2);
0163     assert(lru_map_fd != -1);
0164 
0165     expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
0166     assert(expected_map_fd != -1);
0167 
0168     value[0] = 1234;
0169 
0170     /* insert key=1 element */
0171 
0172     key = 1;
0173     assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0174     assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0175                     BPF_NOEXIST));
0176 
0177     /* BPF_NOEXIST means: add new element if it doesn't exist */
0178     assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST);
0179     /* key=1 already exists */
0180 
0181     assert(bpf_map_update_elem(lru_map_fd, &key, value, -1) == -EINVAL);
0182 
0183     /* insert key=2 element */
0184 
0185     /* check that key=2 is not found */
0186     key = 2;
0187     assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0188 
0189     /* BPF_EXIST means: update existing element */
0190     assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT);
0191     /* key=2 is not there */
0192 
0193     assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0194 
0195     /* insert key=3 element */
0196 
0197     /* check that key=3 is not found */
0198     key = 3;
0199     assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0200 
0201     /* check that key=1 can be found and mark the ref bit to
0202      * stop LRU from removing key=1
0203      */
0204     key = 1;
0205     assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
0206     assert(value[0] == 1234);
0207 
0208     key = 3;
0209     assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0210     assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0211                     BPF_NOEXIST));
0212 
0213     /* key=2 has been removed from the LRU */
0214     key = 2;
0215     assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0216 
0217     /* lookup elem key=1 and delete it, then check it doesn't exist */
0218     key = 1;
0219     assert(!bpf_map_lookup_and_delete_elem(lru_map_fd, &key, &value));
0220     assert(value[0] == 1234);
0221 
0222     /* remove the same element from the expected map */
0223     assert(!bpf_map_delete_elem(expected_map_fd, &key));
0224 
0225     assert(map_equal(lru_map_fd, expected_map_fd));
0226 
0227     close(expected_map_fd);
0228     close(lru_map_fd);
0229 
0230     printf("Pass\n");
0231 }
0232 
0233 /* Size of the LRU map is 1.5*tgt_free
0234  * Insert 1 to tgt_free (+tgt_free keys)
0235  * Lookup 1 to tgt_free/2
0236  * Insert 1+tgt_free to 2*tgt_free (+tgt_free keys)
0237  * => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU
0238  */
0239 static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free)
0240 {
0241     unsigned long long key, end_key, value[nr_cpus];
0242     int lru_map_fd, expected_map_fd;
0243     unsigned int batch_size;
0244     unsigned int map_size;
0245     int next_cpu = 0;
0246 
0247     if (map_flags & BPF_F_NO_COMMON_LRU)
0248         /* This test is only applicable to common LRU list */
0249         return;
0250 
0251     printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
0252            map_flags);
0253 
0254     assert(sched_next_online(0, &next_cpu) != -1);
0255 
0256     batch_size = tgt_free / 2;
0257     assert(batch_size * 2 == tgt_free);
0258 
0259     map_size = tgt_free + batch_size;
0260     lru_map_fd = create_map(map_type, map_flags, map_size);
0261     assert(lru_map_fd != -1);
0262 
0263     expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
0264     assert(expected_map_fd != -1);
0265 
0266     value[0] = 1234;
0267 
0268     /* Insert 1 to tgt_free (+tgt_free keys) */
0269     end_key = 1 + tgt_free;
0270     for (key = 1; key < end_key; key++)
0271         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0272                         BPF_NOEXIST));
0273 
0274     /* Lookup 1 to tgt_free/2 */
0275     end_key = 1 + batch_size;
0276     for (key = 1; key < end_key; key++) {
0277         assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
0278         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0279                         BPF_NOEXIST));
0280     }
0281 
0282     /* Insert 1+tgt_free to 2*tgt_free
0283      * => 1+tgt_free/2 to LOCALFREE_TARGET will be
0284      * removed by LRU
0285      */
0286     key = 1 + tgt_free;
0287     end_key = key + tgt_free;
0288     for (; key < end_key; key++) {
0289         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0290                         BPF_NOEXIST));
0291         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0292                         BPF_NOEXIST));
0293     }
0294 
0295     assert(map_equal(lru_map_fd, expected_map_fd));
0296 
0297     close(expected_map_fd);
0298     close(lru_map_fd);
0299 
0300     printf("Pass\n");
0301 }
0302 
0303 /* Size of the LRU map 1.5 * tgt_free
0304  * Insert 1 to tgt_free (+tgt_free keys)
0305  * Update 1 to tgt_free/2
0306  *   => The original 1 to tgt_free/2 will be removed due to
0307  *      the LRU shrink process
0308  * Re-insert 1 to tgt_free/2 again and do a lookup immeidately
0309  * Insert 1+tgt_free to tgt_free*3/2
0310  * Insert 1+tgt_free*3/2 to tgt_free*5/2
0311  *   => Key 1+tgt_free to tgt_free*3/2
0312  *      will be removed from LRU because it has never
0313  *      been lookup and ref bit is not set
0314  */
0315 static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free)
0316 {
0317     unsigned long long key, value[nr_cpus];
0318     unsigned long long end_key;
0319     int lru_map_fd, expected_map_fd;
0320     unsigned int batch_size;
0321     unsigned int map_size;
0322     int next_cpu = 0;
0323 
0324     if (map_flags & BPF_F_NO_COMMON_LRU)
0325         /* This test is only applicable to common LRU list */
0326         return;
0327 
0328     printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
0329            map_flags);
0330 
0331     assert(sched_next_online(0, &next_cpu) != -1);
0332 
0333     batch_size = tgt_free / 2;
0334     assert(batch_size * 2 == tgt_free);
0335 
0336     map_size = tgt_free + batch_size;
0337     lru_map_fd = create_map(map_type, map_flags, map_size);
0338     assert(lru_map_fd != -1);
0339 
0340     expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
0341     assert(expected_map_fd != -1);
0342 
0343     value[0] = 1234;
0344 
0345     /* Insert 1 to tgt_free (+tgt_free keys) */
0346     end_key = 1 + tgt_free;
0347     for (key = 1; key < end_key; key++)
0348         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0349                         BPF_NOEXIST));
0350 
0351     /* Any bpf_map_update_elem will require to acquire a new node
0352      * from LRU first.
0353      *
0354      * The local list is running out of free nodes.
0355      * It gets from the global LRU list which tries to
0356      * shrink the inactive list to get tgt_free
0357      * number of free nodes.
0358      *
0359      * Hence, the oldest key 1 to tgt_free/2
0360      * are removed from the LRU list.
0361      */
0362     key = 1;
0363     if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
0364         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0365                         BPF_NOEXIST));
0366         assert(!bpf_map_delete_elem(lru_map_fd, &key));
0367     } else {
0368         assert(bpf_map_update_elem(lru_map_fd, &key, value,
0369                        BPF_EXIST));
0370     }
0371 
0372     /* Re-insert 1 to tgt_free/2 again and do a lookup
0373      * immeidately.
0374      */
0375     end_key = 1 + batch_size;
0376     value[0] = 4321;
0377     for (key = 1; key < end_key; key++) {
0378         assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0379         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0380                         BPF_NOEXIST));
0381         assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
0382         assert(value[0] == 4321);
0383         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0384                         BPF_NOEXIST));
0385     }
0386 
0387     value[0] = 1234;
0388 
0389     /* Insert 1+tgt_free to tgt_free*3/2 */
0390     end_key = 1 + tgt_free + batch_size;
0391     for (key = 1 + tgt_free; key < end_key; key++)
0392         /* These newly added but not referenced keys will be
0393          * gone during the next LRU shrink.
0394          */
0395         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0396                         BPF_NOEXIST));
0397 
0398     /* Insert 1+tgt_free*3/2 to  tgt_free*5/2 */
0399     end_key = key + tgt_free;
0400     for (; key < end_key; key++) {
0401         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0402                         BPF_NOEXIST));
0403         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0404                         BPF_NOEXIST));
0405     }
0406 
0407     assert(map_equal(lru_map_fd, expected_map_fd));
0408 
0409     close(expected_map_fd);
0410     close(lru_map_fd);
0411 
0412     printf("Pass\n");
0413 }
0414 
0415 /* Size of the LRU map is 2*tgt_free
0416  * It is to test the active/inactive list rotation
0417  * Insert 1 to 2*tgt_free (+2*tgt_free keys)
0418  * Lookup key 1 to tgt_free*3/2
0419  * Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys)
0420  *  => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU
0421  */
0422 static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free)
0423 {
0424     unsigned long long key, end_key, value[nr_cpus];
0425     int lru_map_fd, expected_map_fd;
0426     unsigned int batch_size;
0427     unsigned int map_size;
0428     int next_cpu = 0;
0429 
0430     if (map_flags & BPF_F_NO_COMMON_LRU)
0431         /* This test is only applicable to common LRU list */
0432         return;
0433 
0434     printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
0435            map_flags);
0436 
0437     assert(sched_next_online(0, &next_cpu) != -1);
0438 
0439     batch_size = tgt_free / 2;
0440     assert(batch_size * 2 == tgt_free);
0441 
0442     map_size = tgt_free * 2;
0443     lru_map_fd = create_map(map_type, map_flags, map_size);
0444     assert(lru_map_fd != -1);
0445 
0446     expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
0447     assert(expected_map_fd != -1);
0448 
0449     value[0] = 1234;
0450 
0451     /* Insert 1 to 2*tgt_free (+2*tgt_free keys) */
0452     end_key = 1 + (2 * tgt_free);
0453     for (key = 1; key < end_key; key++)
0454         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0455                         BPF_NOEXIST));
0456 
0457     /* Lookup key 1 to tgt_free*3/2 */
0458     end_key = tgt_free + batch_size;
0459     for (key = 1; key < end_key; key++) {
0460         assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
0461         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0462                         BPF_NOEXIST));
0463     }
0464 
0465     /* Add 1+2*tgt_free to tgt_free*5/2
0466      * (+tgt_free/2 keys)
0467      */
0468     key = 2 * tgt_free + 1;
0469     end_key = key + batch_size;
0470     for (; key < end_key; key++) {
0471         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0472                         BPF_NOEXIST));
0473         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0474                         BPF_NOEXIST));
0475     }
0476 
0477     assert(map_equal(lru_map_fd, expected_map_fd));
0478 
0479     close(expected_map_fd);
0480     close(lru_map_fd);
0481 
0482     printf("Pass\n");
0483 }
0484 
0485 /* Test deletion */
0486 static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free)
0487 {
0488     int lru_map_fd, expected_map_fd;
0489     unsigned long long key, value[nr_cpus];
0490     unsigned long long end_key;
0491     int next_cpu = 0;
0492 
0493     printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
0494            map_flags);
0495 
0496     assert(sched_next_online(0, &next_cpu) != -1);
0497 
0498     if (map_flags & BPF_F_NO_COMMON_LRU)
0499         lru_map_fd = create_map(map_type, map_flags,
0500                     3 * tgt_free * nr_cpus);
0501     else
0502         lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free);
0503     assert(lru_map_fd != -1);
0504 
0505     expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0,
0506                      3 * tgt_free);
0507     assert(expected_map_fd != -1);
0508 
0509     value[0] = 1234;
0510 
0511     for (key = 1; key <= 2 * tgt_free; key++)
0512         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0513                         BPF_NOEXIST));
0514 
0515     key = 1;
0516     assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0517 
0518     for (key = 1; key <= tgt_free; key++) {
0519         assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
0520         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0521                         BPF_NOEXIST));
0522     }
0523 
0524     for (; key <= 2 * tgt_free; key++) {
0525         assert(!bpf_map_delete_elem(lru_map_fd, &key));
0526         assert(bpf_map_delete_elem(lru_map_fd, &key));
0527     }
0528 
0529     end_key = key + 2 * tgt_free;
0530     for (; key < end_key; key++) {
0531         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0532                         BPF_NOEXIST));
0533         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0534                         BPF_NOEXIST));
0535     }
0536 
0537     assert(map_equal(lru_map_fd, expected_map_fd));
0538 
0539     close(expected_map_fd);
0540     close(lru_map_fd);
0541 
0542     printf("Pass\n");
0543 }
0544 
0545 static void do_test_lru_sanity5(unsigned long long last_key, int map_fd)
0546 {
0547     unsigned long long key, value[nr_cpus];
0548 
0549     /* Ensure the last key inserted by previous CPU can be found */
0550     assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, last_key, value));
0551     value[0] = 1234;
0552 
0553     key = last_key + 1;
0554     assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
0555     assert(!bpf_map_lookup_elem_with_ref_bit(map_fd, key, value));
0556 
0557     /* Cannot find the last key because it was removed by LRU */
0558     assert(bpf_map_lookup_elem(map_fd, &last_key, value) == -ENOENT);
0559 }
0560 
0561 /* Test map with only one element */
0562 static void test_lru_sanity5(int map_type, int map_flags)
0563 {
0564     unsigned long long key, value[nr_cpus];
0565     int next_cpu = 0;
0566     int map_fd;
0567 
0568     if (map_flags & BPF_F_NO_COMMON_LRU)
0569         return;
0570 
0571     printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
0572            map_flags);
0573 
0574     map_fd = create_map(map_type, map_flags, 1);
0575     assert(map_fd != -1);
0576 
0577     value[0] = 1234;
0578     key = 0;
0579     assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
0580 
0581     while (sched_next_online(0, &next_cpu) != -1) {
0582         pid_t pid;
0583 
0584         pid = fork();
0585         if (pid == 0) {
0586             do_test_lru_sanity5(key, map_fd);
0587             exit(0);
0588         } else if (pid == -1) {
0589             printf("couldn't spawn process to test key:%llu\n",
0590                    key);
0591             exit(1);
0592         } else {
0593             int status;
0594 
0595             assert(waitpid(pid, &status, 0) == pid);
0596             assert(status == 0);
0597             key++;
0598         }
0599     }
0600 
0601     close(map_fd);
0602     /* At least one key should be tested */
0603     assert(key > 0);
0604 
0605     printf("Pass\n");
0606 }
0607 
0608 /* Test list rotation for BPF_F_NO_COMMON_LRU map */
0609 static void test_lru_sanity6(int map_type, int map_flags, int tgt_free)
0610 {
0611     int lru_map_fd, expected_map_fd;
0612     unsigned long long key, value[nr_cpus];
0613     unsigned int map_size = tgt_free * 2;
0614     int next_cpu = 0;
0615 
0616     if (!(map_flags & BPF_F_NO_COMMON_LRU))
0617         return;
0618 
0619     printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
0620            map_flags);
0621 
0622     assert(sched_next_online(0, &next_cpu) != -1);
0623 
0624     expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
0625     assert(expected_map_fd != -1);
0626 
0627     lru_map_fd = create_map(map_type, map_flags, map_size * nr_cpus);
0628     assert(lru_map_fd != -1);
0629 
0630     value[0] = 1234;
0631 
0632     for (key = 1; key <= tgt_free; key++) {
0633         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0634                         BPF_NOEXIST));
0635         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0636                         BPF_NOEXIST));
0637     }
0638 
0639     for (; key <= tgt_free * 2; key++) {
0640         unsigned long long stable_key;
0641 
0642         /* Make ref bit sticky for key: [1, tgt_free] */
0643         for (stable_key = 1; stable_key <= tgt_free; stable_key++) {
0644             /* Mark the ref bit */
0645             assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd,
0646                                  stable_key, value));
0647         }
0648         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0649                         BPF_NOEXIST));
0650     }
0651 
0652     for (; key <= tgt_free * 3; key++) {
0653         assert(!bpf_map_update_elem(lru_map_fd, &key, value,
0654                         BPF_NOEXIST));
0655         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0656                         BPF_NOEXIST));
0657     }
0658 
0659     assert(map_equal(lru_map_fd, expected_map_fd));
0660 
0661     close(expected_map_fd);
0662     close(lru_map_fd);
0663 
0664     printf("Pass\n");
0665 }
0666 
0667 /* Size of the LRU map is 2
0668  * Add key=1 (+1 key)
0669  * Add key=2 (+1 key)
0670  * Lookup Key=1 (datapath)
0671  * Lookup Key=2 (syscall)
0672  * Add Key=3
0673  *   => Key=2 will be removed by LRU
0674  * Iterate map.  Only found key=1 and key=3
0675  */
0676 static void test_lru_sanity7(int map_type, int map_flags)
0677 {
0678     unsigned long long key, value[nr_cpus];
0679     int lru_map_fd, expected_map_fd;
0680     int next_cpu = 0;
0681 
0682     printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
0683            map_flags);
0684 
0685     assert(sched_next_online(0, &next_cpu) != -1);
0686 
0687     if (map_flags & BPF_F_NO_COMMON_LRU)
0688         lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
0689     else
0690         lru_map_fd = create_map(map_type, map_flags, 2);
0691     assert(lru_map_fd != -1);
0692 
0693     expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
0694     assert(expected_map_fd != -1);
0695 
0696     value[0] = 1234;
0697 
0698     /* insert key=1 element */
0699 
0700     key = 1;
0701     assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0702     assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0703                     BPF_NOEXIST));
0704 
0705     /* BPF_NOEXIST means: add new element if it doesn't exist */
0706     assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST);
0707     /* key=1 already exists */
0708 
0709     /* insert key=2 element */
0710 
0711     /* check that key=2 is not found */
0712     key = 2;
0713     assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0714 
0715     /* BPF_EXIST means: update existing element */
0716     assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT);
0717     /* key=2 is not there */
0718 
0719     assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0720 
0721     /* insert key=3 element */
0722 
0723     /* check that key=3 is not found */
0724     key = 3;
0725     assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0726 
0727     /* check that key=1 can be found and mark the ref bit to
0728      * stop LRU from removing key=1
0729      */
0730     key = 1;
0731     assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
0732     assert(value[0] == 1234);
0733 
0734     /* check that key=2 can be found and do _not_ mark ref bit.
0735      * this will be evicted on next update.
0736      */
0737     key = 2;
0738     assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
0739     assert(value[0] == 1234);
0740 
0741     key = 3;
0742     assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0743     assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0744                     BPF_NOEXIST));
0745 
0746     /* key=2 has been removed from the LRU */
0747     key = 2;
0748     assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0749 
0750     assert(map_equal(lru_map_fd, expected_map_fd));
0751 
0752     close(expected_map_fd);
0753     close(lru_map_fd);
0754 
0755     printf("Pass\n");
0756 }
0757 
0758 /* Size of the LRU map is 2
0759  * Add key=1 (+1 key)
0760  * Add key=2 (+1 key)
0761  * Lookup Key=1 (syscall)
0762  * Lookup Key=2 (datapath)
0763  * Add Key=3
0764  *   => Key=1 will be removed by LRU
0765  * Iterate map.  Only found key=2 and key=3
0766  */
0767 static void test_lru_sanity8(int map_type, int map_flags)
0768 {
0769     unsigned long long key, value[nr_cpus];
0770     int lru_map_fd, expected_map_fd;
0771     int next_cpu = 0;
0772 
0773     printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
0774            map_flags);
0775 
0776     assert(sched_next_online(0, &next_cpu) != -1);
0777 
0778     if (map_flags & BPF_F_NO_COMMON_LRU)
0779         lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
0780     else
0781         lru_map_fd = create_map(map_type, map_flags, 2);
0782     assert(lru_map_fd != -1);
0783 
0784     expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
0785     assert(expected_map_fd != -1);
0786 
0787     value[0] = 1234;
0788 
0789     /* insert key=1 element */
0790 
0791     key = 1;
0792     assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0793 
0794     /* BPF_NOEXIST means: add new element if it doesn't exist */
0795     assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -EEXIST);
0796     /* key=1 already exists */
0797 
0798     /* insert key=2 element */
0799 
0800     /* check that key=2 is not found */
0801     key = 2;
0802     assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0803 
0804     /* BPF_EXIST means: update existing element */
0805     assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -ENOENT);
0806     /* key=2 is not there */
0807 
0808     assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0809     assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0810                     BPF_NOEXIST));
0811 
0812     /* insert key=3 element */
0813 
0814     /* check that key=3 is not found */
0815     key = 3;
0816     assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0817 
0818     /* check that key=1 can be found and do _not_ mark ref bit.
0819      * this will be evicted on next update.
0820      */
0821     key = 1;
0822     assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
0823     assert(value[0] == 1234);
0824 
0825     /* check that key=2 can be found and mark the ref bit to
0826      * stop LRU from removing key=2
0827      */
0828     key = 2;
0829     assert(!bpf_map_lookup_elem_with_ref_bit(lru_map_fd, key, value));
0830     assert(value[0] == 1234);
0831 
0832     key = 3;
0833     assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
0834     assert(!bpf_map_update_elem(expected_map_fd, &key, value,
0835                     BPF_NOEXIST));
0836 
0837     /* key=1 has been removed from the LRU */
0838     key = 1;
0839     assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -ENOENT);
0840 
0841     assert(map_equal(lru_map_fd, expected_map_fd));
0842 
0843     close(expected_map_fd);
0844     close(lru_map_fd);
0845 
0846     printf("Pass\n");
0847 }
0848 
0849 int main(int argc, char **argv)
0850 {
0851     int map_types[] = {BPF_MAP_TYPE_LRU_HASH,
0852                  BPF_MAP_TYPE_LRU_PERCPU_HASH};
0853     int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
0854     int t, f;
0855 
0856     setbuf(stdout, NULL);
0857 
0858     nr_cpus = bpf_num_possible_cpus();
0859     assert(nr_cpus != -1);
0860     printf("nr_cpus:%d\n\n", nr_cpus);
0861 
0862     /* Use libbpf 1.0 API mode */
0863     libbpf_set_strict_mode(LIBBPF_STRICT_ALL);
0864 
0865     for (f = 0; f < ARRAY_SIZE(map_flags); f++) {
0866         unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ?
0867             PERCPU_FREE_TARGET : LOCAL_FREE_TARGET;
0868 
0869         for (t = 0; t < ARRAY_SIZE(map_types); t++) {
0870             test_lru_sanity0(map_types[t], map_flags[f]);
0871             test_lru_sanity1(map_types[t], map_flags[f], tgt_free);
0872             test_lru_sanity2(map_types[t], map_flags[f], tgt_free);
0873             test_lru_sanity3(map_types[t], map_flags[f], tgt_free);
0874             test_lru_sanity4(map_types[t], map_flags[f], tgt_free);
0875             test_lru_sanity5(map_types[t], map_flags[f]);
0876             test_lru_sanity6(map_types[t], map_flags[f], tgt_free);
0877             test_lru_sanity7(map_types[t], map_flags[f]);
0878             test_lru_sanity8(map_types[t], map_flags[f]);
0879 
0880             printf("\n");
0881         }
0882     }
0883 
0884     return 0;
0885 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!