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