~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/samples/bpf/test_lru_dist.c

Version: ~ [ linux-5.10-rc1 ] ~ [ linux-5.9.1 ] ~ [ linux-5.8.16 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.72 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.152 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.202 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.240 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.240 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 <linux/types.h>
 10 #include <stdio.h>
 11 #include <unistd.h>
 12 #include <linux/bpf.h>
 13 #include <errno.h>
 14 #include <string.h>
 15 #include <assert.h>
 16 #include <sched.h>
 17 #include <sys/wait.h>
 18 #include <sys/stat.h>
 19 #include <sys/resource.h>
 20 #include <fcntl.h>
 21 #include <stdlib.h>
 22 #include <time.h>
 23 
 24 #include "libbpf.h"
 25 #include "bpf_util.h"
 26 
 27 #define min(a, b) ((a) < (b) ? (a) : (b))
 28 #ifndef offsetof
 29 # define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
 30 #endif
 31 #define container_of(ptr, type, member) ({                      \
 32         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
 33         (type *)( (char *)__mptr - offsetof(type,member) );})
 34 
 35 static int nr_cpus;
 36 static unsigned long long *dist_keys;
 37 static unsigned int dist_key_counts;
 38 
 39 struct list_head {
 40         struct list_head *next, *prev;
 41 };
 42 
 43 static inline void INIT_LIST_HEAD(struct list_head *list)
 44 {
 45         list->next = list;
 46         list->prev = list;
 47 }
 48 
 49 static inline int list_empty(const struct list_head *head)
 50 {
 51         return head->next == head;
 52 }
 53 
 54 static inline void __list_add(struct list_head *new,
 55                               struct list_head *prev,
 56                               struct list_head *next)
 57 {
 58         next->prev = new;
 59         new->next = next;
 60         new->prev = prev;
 61         prev->next = new;
 62 }
 63 
 64 static inline void list_add(struct list_head *new, struct list_head *head)
 65 {
 66         __list_add(new, head, head->next);
 67 }
 68 
 69 static inline void __list_del(struct list_head *prev, struct list_head *next)
 70 {
 71         next->prev = prev;
 72         prev->next = next;
 73 }
 74 
 75 static inline void __list_del_entry(struct list_head *entry)
 76 {
 77         __list_del(entry->prev, entry->next);
 78 }
 79 
 80 static inline void list_move(struct list_head *list, struct list_head *head)
 81 {
 82         __list_del_entry(list);
 83         list_add(list, head);
 84 }
 85 
 86 #define list_entry(ptr, type, member) \
 87         container_of(ptr, type, member)
 88 
 89 #define list_last_entry(ptr, type, member) \
 90         list_entry((ptr)->prev, type, member)
 91 
 92 struct pfect_lru_node {
 93         struct list_head list;
 94         unsigned long long key;
 95 };
 96 
 97 struct pfect_lru {
 98         struct list_head list;
 99         struct pfect_lru_node *free_nodes;
100         unsigned int cur_size;
101         unsigned int lru_size;
102         unsigned int nr_unique;
103         unsigned int nr_misses;
104         unsigned int total;
105         int map_fd;
106 };
107 
108 static void pfect_lru_init(struct pfect_lru *lru, unsigned int lru_size,
109                            unsigned int nr_possible_elems)
110 {
111         lru->map_fd = bpf_create_map(BPF_MAP_TYPE_HASH,
112                                      sizeof(unsigned long long),
113                                      sizeof(struct pfect_lru_node *),
114                                      nr_possible_elems, 0);
115         assert(lru->map_fd != -1);
116 
117         lru->free_nodes = malloc(lru_size * sizeof(struct pfect_lru_node));
118         assert(lru->free_nodes);
119 
120         INIT_LIST_HEAD(&lru->list);
121         lru->cur_size = 0;
122         lru->lru_size = lru_size;
123         lru->nr_unique = lru->nr_misses = lru->total = 0;
124 }
125 
126 static void pfect_lru_destroy(struct pfect_lru *lru)
127 {
128         close(lru->map_fd);
129         free(lru->free_nodes);
130 }
131 
132 static int pfect_lru_lookup_or_insert(struct pfect_lru *lru,
133                                       unsigned long long key)
134 {
135         struct pfect_lru_node *node = NULL;
136         int seen = 0;
137 
138         lru->total++;
139         if (!bpf_map_lookup_elem(lru->map_fd, &key, &node)) {
140                 if (node) {
141                         list_move(&node->list, &lru->list);
142                         return 1;
143                 }
144                 seen = 1;
145         }
146 
147         if (lru->cur_size < lru->lru_size) {
148                 node =  &lru->free_nodes[lru->cur_size++];
149                 INIT_LIST_HEAD(&node->list);
150         } else {
151                 struct pfect_lru_node *null_node = NULL;
152 
153                 node = list_last_entry(&lru->list,
154                                        struct pfect_lru_node,
155                                        list);
156                 bpf_map_update_elem(lru->map_fd, &node->key, &null_node, BPF_EXIST);
157         }
158 
159         node->key = key;
160         list_move(&node->list, &lru->list);
161 
162         lru->nr_misses++;
163         if (seen) {
164                 assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_EXIST));
165         } else {
166                 lru->nr_unique++;
167                 assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_NOEXIST));
168         }
169 
170         return seen;
171 }
172 
173 static unsigned int read_keys(const char *dist_file,
174                               unsigned long long **keys)
175 {
176         struct stat fst;
177         unsigned long long *retkeys;
178         unsigned int counts = 0;
179         int dist_fd;
180         char *b, *l;
181         int i;
182 
183         dist_fd = open(dist_file, 0);
184         assert(dist_fd != -1);
185 
186         assert(fstat(dist_fd, &fst) == 0);
187         b = malloc(fst.st_size);
188         assert(b);
189 
190         assert(read(dist_fd, b, fst.st_size) == fst.st_size);
191         close(dist_fd);
192         for (i = 0; i < fst.st_size; i++) {
193                 if (b[i] == '\n')
194                         counts++;
195         }
196         counts++; /* in case the last line has no \n */
197 
198         retkeys = malloc(counts * sizeof(unsigned long long));
199         assert(retkeys);
200 
201         counts = 0;
202         for (l = strtok(b, "\n"); l; l = strtok(NULL, "\n"))
203                 retkeys[counts++] = strtoull(l, NULL, 10);
204         free(b);
205 
206         *keys = retkeys;
207 
208         return counts;
209 }
210 
211 static int create_map(int map_type, int map_flags, unsigned int size)
212 {
213         int map_fd;
214 
215         map_fd = bpf_create_map(map_type, sizeof(unsigned long long),
216                                 sizeof(unsigned long long), size, map_flags);
217 
218         if (map_fd == -1)
219                 perror("bpf_create_map");
220 
221         return map_fd;
222 }
223 
224 static int sched_next_online(int pid, int next_to_try)
225 {
226         cpu_set_t cpuset;
227 
228         if (next_to_try == nr_cpus)
229                 return -1;
230 
231         while (next_to_try < nr_cpus) {
232                 CPU_ZERO(&cpuset);
233                 CPU_SET(next_to_try++, &cpuset);
234                 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset))
235                         break;
236         }
237 
238         return next_to_try;
239 }
240 
241 static void run_parallel(unsigned int tasks, void (*fn)(int i, void *data),
242                          void *data)
243 {
244         int next_sched_cpu = 0;
245         pid_t pid[tasks];
246         int i;
247 
248         for (i = 0; i < tasks; i++) {
249                 pid[i] = fork();
250                 if (pid[i] == 0) {
251                         next_sched_cpu = sched_next_online(0, next_sched_cpu);
252                         fn(i, data);
253                         exit(0);
254                 } else if (pid[i] == -1) {
255                         printf("couldn't spawn #%d process\n", i);
256                         exit(1);
257                 }
258                 /* It is mostly redundant and just allow the parent
259                  * process to update next_shced_cpu for the next child
260                  * process
261                  */
262                 next_sched_cpu = sched_next_online(pid[i], next_sched_cpu);
263         }
264         for (i = 0; i < tasks; i++) {
265                 int status;
266 
267                 assert(waitpid(pid[i], &status, 0) == pid[i]);
268                 assert(status == 0);
269         }
270 }
271 
272 static void do_test_lru_dist(int task, void *data)
273 {
274         unsigned int nr_misses = 0;
275         struct pfect_lru pfect_lru;
276         unsigned long long key, value = 1234;
277         unsigned int i;
278 
279         unsigned int lru_map_fd = ((unsigned int *)data)[0];
280         unsigned int lru_size = ((unsigned int *)data)[1];
281         unsigned long long key_offset = task * dist_key_counts;
282 
283         pfect_lru_init(&pfect_lru, lru_size, dist_key_counts);
284 
285         for (i = 0; i < dist_key_counts; i++) {
286                 key = dist_keys[i] + key_offset;
287 
288                 pfect_lru_lookup_or_insert(&pfect_lru, key);
289 
290                 if (!bpf_map_lookup_elem(lru_map_fd, &key, &value))
291                         continue;
292 
293                 if (bpf_map_update_elem(lru_map_fd, &key, &value, BPF_NOEXIST)) {
294                         printf("bpf_map_update_elem(lru_map_fd, %llu): errno:%d\n",
295                                key, errno);
296                         assert(0);
297                 }
298 
299                 nr_misses++;
300         }
301 
302         printf("    task:%d BPF LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
303                task, pfect_lru.nr_unique, dist_key_counts, nr_misses,
304                dist_key_counts);
305         printf("    task:%d Perfect LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
306                task, pfect_lru.nr_unique, pfect_lru.total,
307                pfect_lru.nr_misses, pfect_lru.total);
308 
309         pfect_lru_destroy(&pfect_lru);
310         close(lru_map_fd);
311 }
312 
313 static void test_parallel_lru_dist(int map_type, int map_flags,
314                                    int nr_tasks, unsigned int lru_size)
315 {
316         int child_data[2];
317         int lru_map_fd;
318 
319         printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
320                map_flags);
321 
322         if (map_flags & BPF_F_NO_COMMON_LRU)
323                 lru_map_fd = create_map(map_type, map_flags,
324                                         nr_cpus * lru_size);
325         else
326                 lru_map_fd = create_map(map_type, map_flags,
327                                         nr_tasks * lru_size);
328         assert(lru_map_fd != -1);
329 
330         child_data[0] = lru_map_fd;
331         child_data[1] = lru_size;
332 
333         run_parallel(nr_tasks, do_test_lru_dist, child_data);
334 
335         close(lru_map_fd);
336 }
337 
338 static void test_lru_loss0(int map_type, int map_flags)
339 {
340         unsigned long long key, value[nr_cpus];
341         unsigned int old_unused_losses = 0;
342         unsigned int new_unused_losses = 0;
343         unsigned int used_losses = 0;
344         int map_fd;
345 
346         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
347                map_flags);
348 
349         assert(sched_next_online(0, 0) != -1);
350 
351         if (map_flags & BPF_F_NO_COMMON_LRU)
352                 map_fd = create_map(map_type, map_flags, 900 * nr_cpus);
353         else
354                 map_fd = create_map(map_type, map_flags, 900);
355 
356         assert(map_fd != -1);
357 
358         value[0] = 1234;
359 
360         for (key = 1; key <= 1000; key++) {
361                 int start_key, end_key;
362 
363                 assert(bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST) == 0);
364 
365                 start_key = 101;
366                 end_key = min(key, 900);
367 
368                 while (start_key <= end_key) {
369                         bpf_map_lookup_elem(map_fd, &start_key, value);
370                         start_key++;
371                 }
372         }
373 
374         for (key = 1; key <= 1000; key++) {
375                 if (bpf_map_lookup_elem(map_fd, &key, value)) {
376                         if (key <= 100)
377                                 old_unused_losses++;
378                         else if (key <= 900)
379                                 used_losses++;
380                         else
381                                 new_unused_losses++;
382                 }
383         }
384 
385         close(map_fd);
386 
387         printf("older-elem-losses:%d(/100) active-elem-losses:%d(/800) "
388                "newer-elem-losses:%d(/100)\n",
389                old_unused_losses, used_losses, new_unused_losses);
390 }
391 
392 static void test_lru_loss1(int map_type, int map_flags)
393 {
394         unsigned long long key, value[nr_cpus];
395         int map_fd;
396         unsigned int nr_losses = 0;
397 
398         printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
399                map_flags);
400 
401         assert(sched_next_online(0, 0) != -1);
402 
403         if (map_flags & BPF_F_NO_COMMON_LRU)
404                 map_fd = create_map(map_type, map_flags, 1000 * nr_cpus);
405         else
406                 map_fd = create_map(map_type, map_flags, 1000);
407 
408         assert(map_fd != -1);
409 
410         value[0] = 1234;
411 
412         for (key = 1; key <= 1000; key++)
413                 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
414 
415         for (key = 1; key <= 1000; key++) {
416                 if (bpf_map_lookup_elem(map_fd, &key, value))
417                         nr_losses++;
418         }
419 
420         close(map_fd);
421 
422         printf("nr_losses:%d(/1000)\n", nr_losses);
423 }
424 
425 static void do_test_parallel_lru_loss(int task, void *data)
426 {
427         const unsigned int nr_stable_elems = 1000;
428         const unsigned int nr_repeats = 100000;
429 
430         int map_fd = *(int *)data;
431         unsigned long long stable_base;
432         unsigned long long key, value[nr_cpus];
433         unsigned long long next_ins_key;
434         unsigned int nr_losses = 0;
435         unsigned int i;
436 
437         stable_base = task * nr_repeats * 2 + 1;
438         next_ins_key = stable_base;
439         value[0] = 1234;
440         for (i = 0; i < nr_stable_elems; i++) {
441                 assert(bpf_map_update_elem(map_fd, &next_ins_key, value,
442                                        BPF_NOEXIST) == 0);
443                 next_ins_key++;
444         }
445 
446         for (i = 0; i < nr_repeats; i++) {
447                 int rn;
448 
449                 rn = rand();
450 
451                 if (rn % 10) {
452                         key = rn % nr_stable_elems + stable_base;
453                         bpf_map_lookup_elem(map_fd, &key, value);
454                 } else {
455                         bpf_map_update_elem(map_fd, &next_ins_key, value,
456                                         BPF_NOEXIST);
457                         next_ins_key++;
458                 }
459         }
460 
461         key = stable_base;
462         for (i = 0; i < nr_stable_elems; i++) {
463                 if (bpf_map_lookup_elem(map_fd, &key, value))
464                         nr_losses++;
465                 key++;
466         }
467 
468         printf("    task:%d nr_losses:%u\n", task, nr_losses);
469 }
470 
471 static void test_parallel_lru_loss(int map_type, int map_flags, int nr_tasks)
472 {
473         int map_fd;
474 
475         printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
476                map_flags);
477 
478         /* Give 20% more than the active working set */
479         if (map_flags & BPF_F_NO_COMMON_LRU)
480                 map_fd = create_map(map_type, map_flags,
481                                     nr_cpus * (1000 + 200));
482         else
483                 map_fd = create_map(map_type, map_flags,
484                                     nr_tasks * (1000 + 200));
485 
486         assert(map_fd != -1);
487 
488         run_parallel(nr_tasks, do_test_parallel_lru_loss, &map_fd);
489 
490         close(map_fd);
491 }
492 
493 int main(int argc, char **argv)
494 {
495         struct rlimit r = {RLIM_INFINITY, RLIM_INFINITY};
496         int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
497         const char *dist_file;
498         int nr_tasks = 1;
499         int lru_size;
500         int f;
501 
502         if (argc < 4) {
503                 printf("Usage: %s <dist-file> <lru-size> <nr-tasks>\n",
504                        argv[0]);
505                 return -1;
506         }
507 
508         dist_file = argv[1];
509         lru_size = atoi(argv[2]);
510         nr_tasks = atoi(argv[3]);
511 
512         setbuf(stdout, NULL);
513 
514         assert(!setrlimit(RLIMIT_MEMLOCK, &r));
515 
516         srand(time(NULL));
517 
518         nr_cpus = bpf_num_possible_cpus();
519         assert(nr_cpus != -1);
520         printf("nr_cpus:%d\n\n", nr_cpus);
521 
522         nr_tasks = min(nr_tasks, nr_cpus);
523 
524         dist_key_counts = read_keys(dist_file, &dist_keys);
525         if (!dist_key_counts) {
526                 printf("%s has no key\n", dist_file);
527                 return -1;
528         }
529 
530         for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) {
531                 test_lru_loss0(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
532                 test_lru_loss1(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
533                 test_parallel_lru_loss(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
534                                        nr_tasks);
535                 test_parallel_lru_dist(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
536                                        nr_tasks, lru_size);
537                 printf("\n");
538         }
539 
540         free(dist_keys);
541 
542         return 0;
543 }
544 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp