tools/bpf: Sync kernel btf.h header
[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
22 #include "bpf_util.h"
23 #include "bpf_rlimit.h"
24
25 #define LOCAL_FREE_TARGET       (128)
26 #define PERCPU_FREE_TARGET      (4)
27
28 static int nr_cpus;
29
30 static int create_map(int map_type, int map_flags, unsigned int size)
31 {
32         int map_fd;
33
34         map_fd = bpf_create_map(map_type, sizeof(unsigned long long),
35                                 sizeof(unsigned long long), size, map_flags);
36
37         if (map_fd == -1)
38                 perror("bpf_create_map");
39
40         return map_fd;
41 }
42
43 static int map_subset(int map0, int map1)
44 {
45         unsigned long long next_key = 0;
46         unsigned long long value0[nr_cpus], value1[nr_cpus];
47         int ret;
48
49         while (!bpf_map_get_next_key(map1, &next_key, &next_key)) {
50                 assert(!bpf_map_lookup_elem(map1, &next_key, value1));
51                 ret = bpf_map_lookup_elem(map0, &next_key, value0);
52                 if (ret) {
53                         printf("key:%llu not found from map. %s(%d)\n",
54                                next_key, strerror(errno), errno);
55                         return 0;
56                 }
57                 if (value0[0] != value1[0]) {
58                         printf("key:%llu value0:%llu != value1:%llu\n",
59                                next_key, value0[0], value1[0]);
60                         return 0;
61                 }
62         }
63         return 1;
64 }
65
66 static int map_equal(int lru_map, int expected)
67 {
68         return map_subset(lru_map, expected) && map_subset(expected, lru_map);
69 }
70
71 static int sched_next_online(int pid, int *next_to_try)
72 {
73         cpu_set_t cpuset;
74         int next = *next_to_try;
75         int ret = -1;
76
77         while (next < nr_cpus) {
78                 CPU_ZERO(&cpuset);
79                 CPU_SET(next++, &cpuset);
80                 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset)) {
81                         ret = 0;
82                         break;
83                 }
84         }
85
86         *next_to_try = next;
87         return ret;
88 }
89
90 /* Size of the LRU amp is 2
91  * Add key=1 (+1 key)
92  * Add key=2 (+1 key)
93  * Lookup Key=1
94  * Add Key=3
95  *   => Key=2 will be removed by LRU
96  * Iterate map.  Only found key=1 and key=3
97  */
98 static void test_lru_sanity0(int map_type, int map_flags)
99 {
100         unsigned long long key, value[nr_cpus];
101         int lru_map_fd, expected_map_fd;
102         int next_cpu = 0;
103
104         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
105                map_flags);
106
107         assert(sched_next_online(0, &next_cpu) != -1);
108
109         if (map_flags & BPF_F_NO_COMMON_LRU)
110                 lru_map_fd = create_map(map_type, map_flags, 2 * nr_cpus);
111         else
112                 lru_map_fd = create_map(map_type, map_flags, 2);
113         assert(lru_map_fd != -1);
114
115         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, 2);
116         assert(expected_map_fd != -1);
117
118         value[0] = 1234;
119
120         /* insert key=1 element */
121
122         key = 1;
123         assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
124         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
125                                     BPF_NOEXIST));
126
127         /* BPF_NOEXIST means: add new element if it doesn't exist */
128         assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST) == -1
129                /* key=1 already exists */
130                && errno == EEXIST);
131
132         assert(bpf_map_update_elem(lru_map_fd, &key, value, -1) == -1 &&
133                errno == EINVAL);
134
135         /* insert key=2 element */
136
137         /* check that key=2 is not found */
138         key = 2;
139         assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
140                errno == ENOENT);
141
142         /* BPF_EXIST means: update existing element */
143         assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_EXIST) == -1 &&
144                /* key=2 is not there */
145                errno == ENOENT);
146
147         assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
148
149         /* insert key=3 element */
150
151         /* check that key=3 is not found */
152         key = 3;
153         assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1 &&
154                errno == ENOENT);
155
156         /* check that key=1 can be found and mark the ref bit to
157          * stop LRU from removing key=1
158          */
159         key = 1;
160         assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
161         assert(value[0] == 1234);
162
163         key = 3;
164         assert(!bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
165         assert(!bpf_map_update_elem(expected_map_fd, &key, value,
166                                     BPF_NOEXIST));
167
168         /* key=2 has been removed from the LRU */
169         key = 2;
170         assert(bpf_map_lookup_elem(lru_map_fd, &key, value) == -1);
171
172         assert(map_equal(lru_map_fd, expected_map_fd));
173
174         close(expected_map_fd);
175         close(lru_map_fd);
176
177         printf("Pass\n");
178 }
179
180 /* Size of the LRU map is 1.5*tgt_free
181  * Insert 1 to tgt_free (+tgt_free keys)
182  * Lookup 1 to tgt_free/2
183  * Insert 1+tgt_free to 2*tgt_free (+tgt_free keys)
184  * => 1+tgt_free/2 to LOCALFREE_TARGET will be removed by LRU
185  */
186 static void test_lru_sanity1(int map_type, int map_flags, unsigned int tgt_free)
187 {
188         unsigned long long key, end_key, value[nr_cpus];
189         int lru_map_fd, expected_map_fd;
190         unsigned int batch_size;
191         unsigned int map_size;
192         int next_cpu = 0;
193
194         if (map_flags & BPF_F_NO_COMMON_LRU)
195                 /* This test is only applicable to common LRU list */
196                 return;
197
198         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
199                map_flags);
200
201         assert(sched_next_online(0, &next_cpu) != -1);
202
203         batch_size = tgt_free / 2;
204         assert(batch_size * 2 == tgt_free);
205
206         map_size = tgt_free + batch_size;
207         lru_map_fd = create_map(map_type, map_flags, map_size);
208         assert(lru_map_fd != -1);
209
210         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
211         assert(expected_map_fd != -1);
212
213         value[0] = 1234;
214
215         /* Insert 1 to tgt_free (+tgt_free keys) */
216         end_key = 1 + tgt_free;
217         for (key = 1; key < end_key; key++)
218                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
219                                             BPF_NOEXIST));
220
221         /* Lookup 1 to tgt_free/2 */
222         end_key = 1 + batch_size;
223         for (key = 1; key < end_key; key++) {
224                 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
225                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
226                                             BPF_NOEXIST));
227         }
228
229         /* Insert 1+tgt_free to 2*tgt_free
230          * => 1+tgt_free/2 to LOCALFREE_TARGET will be
231          * removed by LRU
232          */
233         key = 1 + tgt_free;
234         end_key = key + tgt_free;
235         for (; key < end_key; key++) {
236                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
237                                             BPF_NOEXIST));
238                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
239                                             BPF_NOEXIST));
240         }
241
242         assert(map_equal(lru_map_fd, expected_map_fd));
243
244         close(expected_map_fd);
245         close(lru_map_fd);
246
247         printf("Pass\n");
248 }
249
250 /* Size of the LRU map 1.5 * tgt_free
251  * Insert 1 to tgt_free (+tgt_free keys)
252  * Update 1 to tgt_free/2
253  *   => The original 1 to tgt_free/2 will be removed due to
254  *      the LRU shrink process
255  * Re-insert 1 to tgt_free/2 again and do a lookup immeidately
256  * Insert 1+tgt_free to tgt_free*3/2
257  * Insert 1+tgt_free*3/2 to tgt_free*5/2
258  *   => Key 1+tgt_free to tgt_free*3/2
259  *      will be removed from LRU because it has never
260  *      been lookup and ref bit is not set
261  */
262 static void test_lru_sanity2(int map_type, int map_flags, unsigned int tgt_free)
263 {
264         unsigned long long key, value[nr_cpus];
265         unsigned long long end_key;
266         int lru_map_fd, expected_map_fd;
267         unsigned int batch_size;
268         unsigned int map_size;
269         int next_cpu = 0;
270
271         if (map_flags & BPF_F_NO_COMMON_LRU)
272                 /* This test is only applicable to common LRU list */
273                 return;
274
275         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
276                map_flags);
277
278         assert(sched_next_online(0, &next_cpu) != -1);
279
280         batch_size = tgt_free / 2;
281         assert(batch_size * 2 == tgt_free);
282
283         map_size = tgt_free + batch_size;
284         lru_map_fd = create_map(map_type, map_flags, map_size);
285         assert(lru_map_fd != -1);
286
287         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
288         assert(expected_map_fd != -1);
289
290         value[0] = 1234;
291
292         /* Insert 1 to tgt_free (+tgt_free keys) */
293         end_key = 1 + tgt_free;
294         for (key = 1; key < end_key; key++)
295                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
296                                             BPF_NOEXIST));
297
298         /* Any bpf_map_update_elem will require to acquire a new node
299          * from LRU first.
300          *
301          * The local list is running out of free nodes.
302          * It gets from the global LRU list which tries to
303          * shrink the inactive list to get tgt_free
304          * number of free nodes.
305          *
306          * Hence, the oldest key 1 to tgt_free/2
307          * are removed from the LRU list.
308          */
309         key = 1;
310         if (map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
311                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
312                                             BPF_NOEXIST));
313                 assert(!bpf_map_delete_elem(lru_map_fd, &key));
314         } else {
315                 assert(bpf_map_update_elem(lru_map_fd, &key, value,
316                                            BPF_EXIST));
317         }
318
319         /* Re-insert 1 to tgt_free/2 again and do a lookup
320          * immeidately.
321          */
322         end_key = 1 + batch_size;
323         value[0] = 4321;
324         for (key = 1; key < end_key; key++) {
325                 assert(bpf_map_lookup_elem(lru_map_fd, &key, value));
326                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
327                                             BPF_NOEXIST));
328                 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
329                 assert(value[0] == 4321);
330                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
331                                             BPF_NOEXIST));
332         }
333
334         value[0] = 1234;
335
336         /* Insert 1+tgt_free to tgt_free*3/2 */
337         end_key = 1 + tgt_free + batch_size;
338         for (key = 1 + tgt_free; key < end_key; key++)
339                 /* These newly added but not referenced keys will be
340                  * gone during the next LRU shrink.
341                  */
342                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
343                                             BPF_NOEXIST));
344
345         /* Insert 1+tgt_free*3/2 to  tgt_free*5/2 */
346         end_key = key + tgt_free;
347         for (; key < end_key; key++) {
348                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
349                                             BPF_NOEXIST));
350                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
351                                             BPF_NOEXIST));
352         }
353
354         assert(map_equal(lru_map_fd, expected_map_fd));
355
356         close(expected_map_fd);
357         close(lru_map_fd);
358
359         printf("Pass\n");
360 }
361
362 /* Size of the LRU map is 2*tgt_free
363  * It is to test the active/inactive list rotation
364  * Insert 1 to 2*tgt_free (+2*tgt_free keys)
365  * Lookup key 1 to tgt_free*3/2
366  * Add 1+2*tgt_free to tgt_free*5/2 (+tgt_free/2 keys)
367  *  => key 1+tgt_free*3/2 to 2*tgt_free are removed from LRU
368  */
369 static void test_lru_sanity3(int map_type, int map_flags, unsigned int tgt_free)
370 {
371         unsigned long long key, end_key, value[nr_cpus];
372         int lru_map_fd, expected_map_fd;
373         unsigned int batch_size;
374         unsigned int map_size;
375         int next_cpu = 0;
376
377         if (map_flags & BPF_F_NO_COMMON_LRU)
378                 /* This test is only applicable to common LRU list */
379                 return;
380
381         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
382                map_flags);
383
384         assert(sched_next_online(0, &next_cpu) != -1);
385
386         batch_size = tgt_free / 2;
387         assert(batch_size * 2 == tgt_free);
388
389         map_size = tgt_free * 2;
390         lru_map_fd = create_map(map_type, map_flags, map_size);
391         assert(lru_map_fd != -1);
392
393         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
394         assert(expected_map_fd != -1);
395
396         value[0] = 1234;
397
398         /* Insert 1 to 2*tgt_free (+2*tgt_free keys) */
399         end_key = 1 + (2 * tgt_free);
400         for (key = 1; key < end_key; key++)
401                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
402                                             BPF_NOEXIST));
403
404         /* Lookup key 1 to tgt_free*3/2 */
405         end_key = tgt_free + batch_size;
406         for (key = 1; key < end_key; key++) {
407                 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
408                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
409                                             BPF_NOEXIST));
410         }
411
412         /* Add 1+2*tgt_free to tgt_free*5/2
413          * (+tgt_free/2 keys)
414          */
415         key = 2 * tgt_free + 1;
416         end_key = key + batch_size;
417         for (; key < end_key; key++) {
418                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
419                                             BPF_NOEXIST));
420                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
421                                             BPF_NOEXIST));
422         }
423
424         assert(map_equal(lru_map_fd, expected_map_fd));
425
426         close(expected_map_fd);
427         close(lru_map_fd);
428
429         printf("Pass\n");
430 }
431
432 /* Test deletion */
433 static void test_lru_sanity4(int map_type, int map_flags, unsigned int tgt_free)
434 {
435         int lru_map_fd, expected_map_fd;
436         unsigned long long key, value[nr_cpus];
437         unsigned long long end_key;
438         int next_cpu = 0;
439
440         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
441                map_flags);
442
443         assert(sched_next_online(0, &next_cpu) != -1);
444
445         if (map_flags & BPF_F_NO_COMMON_LRU)
446                 lru_map_fd = create_map(map_type, map_flags,
447                                         3 * tgt_free * nr_cpus);
448         else
449                 lru_map_fd = create_map(map_type, map_flags, 3 * tgt_free);
450         assert(lru_map_fd != -1);
451
452         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0,
453                                      3 * tgt_free);
454         assert(expected_map_fd != -1);
455
456         value[0] = 1234;
457
458         for (key = 1; key <= 2 * tgt_free; key++)
459                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
460                                             BPF_NOEXIST));
461
462         key = 1;
463         assert(bpf_map_update_elem(lru_map_fd, &key, value, BPF_NOEXIST));
464
465         for (key = 1; key <= tgt_free; key++) {
466                 assert(!bpf_map_lookup_elem(lru_map_fd, &key, value));
467                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
468                                             BPF_NOEXIST));
469         }
470
471         for (; key <= 2 * tgt_free; key++) {
472                 assert(!bpf_map_delete_elem(lru_map_fd, &key));
473                 assert(bpf_map_delete_elem(lru_map_fd, &key));
474         }
475
476         end_key = key + 2 * tgt_free;
477         for (; key < end_key; key++) {
478                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
479                                             BPF_NOEXIST));
480                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
481                                             BPF_NOEXIST));
482         }
483
484         assert(map_equal(lru_map_fd, expected_map_fd));
485
486         close(expected_map_fd);
487         close(lru_map_fd);
488
489         printf("Pass\n");
490 }
491
492 static void do_test_lru_sanity5(unsigned long long last_key, int map_fd)
493 {
494         unsigned long long key, value[nr_cpus];
495
496         /* Ensure the last key inserted by previous CPU can be found */
497         assert(!bpf_map_lookup_elem(map_fd, &last_key, value));
498
499         value[0] = 1234;
500
501         key = last_key + 1;
502         assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
503         assert(!bpf_map_lookup_elem(map_fd, &key, value));
504
505         /* Cannot find the last key because it was removed by LRU */
506         assert(bpf_map_lookup_elem(map_fd, &last_key, value));
507 }
508
509 /* Test map with only one element */
510 static void test_lru_sanity5(int map_type, int map_flags)
511 {
512         unsigned long long key, value[nr_cpus];
513         int next_cpu = 0;
514         int map_fd;
515
516         if (map_flags & BPF_F_NO_COMMON_LRU)
517                 return;
518
519         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
520                map_flags);
521
522         map_fd = create_map(map_type, map_flags, 1);
523         assert(map_fd != -1);
524
525         value[0] = 1234;
526         key = 0;
527         assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
528
529         while (sched_next_online(0, &next_cpu) != -1) {
530                 pid_t pid;
531
532                 pid = fork();
533                 if (pid == 0) {
534                         do_test_lru_sanity5(key, map_fd);
535                         exit(0);
536                 } else if (pid == -1) {
537                         printf("couldn't spawn process to test key:%llu\n",
538                                key);
539                         exit(1);
540                 } else {
541                         int status;
542
543                         assert(waitpid(pid, &status, 0) == pid);
544                         assert(status == 0);
545                         key++;
546                 }
547         }
548
549         close(map_fd);
550         /* At least one key should be tested */
551         assert(key > 0);
552
553         printf("Pass\n");
554 }
555
556 /* Test list rotation for BPF_F_NO_COMMON_LRU map */
557 static void test_lru_sanity6(int map_type, int map_flags, int tgt_free)
558 {
559         int lru_map_fd, expected_map_fd;
560         unsigned long long key, value[nr_cpus];
561         unsigned int map_size = tgt_free * 2;
562         int next_cpu = 0;
563
564         if (!(map_flags & BPF_F_NO_COMMON_LRU))
565                 return;
566
567         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
568                map_flags);
569
570         assert(sched_next_online(0, &next_cpu) != -1);
571
572         expected_map_fd = create_map(BPF_MAP_TYPE_HASH, 0, map_size);
573         assert(expected_map_fd != -1);
574
575         lru_map_fd = create_map(map_type, map_flags, map_size * nr_cpus);
576         assert(lru_map_fd != -1);
577
578         value[0] = 1234;
579
580         for (key = 1; key <= tgt_free; key++) {
581                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
582                                             BPF_NOEXIST));
583                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
584                                             BPF_NOEXIST));
585         }
586
587         for (; key <= tgt_free * 2; key++) {
588                 unsigned long long stable_key;
589
590                 /* Make ref bit sticky for key: [1, tgt_free] */
591                 for (stable_key = 1; stable_key <= tgt_free; stable_key++) {
592                         /* Mark the ref bit */
593                         assert(!bpf_map_lookup_elem(lru_map_fd, &stable_key,
594                                                     value));
595                 }
596                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
597                                             BPF_NOEXIST));
598         }
599
600         for (; key <= tgt_free * 3; key++) {
601                 assert(!bpf_map_update_elem(lru_map_fd, &key, value,
602                                             BPF_NOEXIST));
603                 assert(!bpf_map_update_elem(expected_map_fd, &key, value,
604                                             BPF_NOEXIST));
605         }
606
607         assert(map_equal(lru_map_fd, expected_map_fd));
608
609         close(expected_map_fd);
610         close(lru_map_fd);
611
612         printf("Pass\n");
613 }
614
615 int main(int argc, char **argv)
616 {
617         int map_types[] = {BPF_MAP_TYPE_LRU_HASH,
618                              BPF_MAP_TYPE_LRU_PERCPU_HASH};
619         int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
620         int t, f;
621
622         setbuf(stdout, NULL);
623
624         nr_cpus = bpf_num_possible_cpus();
625         assert(nr_cpus != -1);
626         printf("nr_cpus:%d\n\n", nr_cpus);
627
628         for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) {
629                 unsigned int tgt_free = (map_flags[f] & BPF_F_NO_COMMON_LRU) ?
630                         PERCPU_FREE_TARGET : LOCAL_FREE_TARGET;
631
632                 for (t = 0; t < sizeof(map_types) / sizeof(*map_types); t++) {
633                         test_lru_sanity0(map_types[t], map_flags[f]);
634                         test_lru_sanity1(map_types[t], map_flags[f], tgt_free);
635                         test_lru_sanity2(map_types[t], map_flags[f], tgt_free);
636                         test_lru_sanity3(map_types[t], map_flags[f], tgt_free);
637                         test_lru_sanity4(map_types[t], map_flags[f], tgt_free);
638                         test_lru_sanity5(map_types[t], map_flags[f]);
639                         test_lru_sanity6(map_types[t], map_flags[f], tgt_free);
640
641                         printf("\n");
642                 }
643         }
644
645         return 0;
646 }