1 // SPDX-License-Identifier: GPL-2.0-only
3 * Copyright (c) 2016 Facebook
6 #include <linux/types.h>
16 #include <sys/resource.h>
24 #define min(a, b) ((a) < (b) ? (a) : (b))
26 # define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
28 #define container_of(ptr, type, member) ({ \
29 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
30 (type *)( (char *)__mptr - offsetof(type,member) );})
33 static unsigned long long *dist_keys;
34 static unsigned int dist_key_counts;
37 struct list_head *next, *prev;
40 static inline void INIT_LIST_HEAD(struct list_head *list)
46 static inline int list_empty(const struct list_head *head)
48 return head->next == head;
51 static inline void __list_add(struct list_head *new,
52 struct list_head *prev,
53 struct list_head *next)
61 static inline void list_add(struct list_head *new, struct list_head *head)
63 __list_add(new, head, head->next);
66 static inline void __list_del(struct list_head *prev, struct list_head *next)
72 static inline void __list_del_entry(struct list_head *entry)
74 __list_del(entry->prev, entry->next);
77 static inline void list_move(struct list_head *list, struct list_head *head)
79 __list_del_entry(list);
83 #define list_entry(ptr, type, member) \
84 container_of(ptr, type, member)
86 #define list_last_entry(ptr, type, member) \
87 list_entry((ptr)->prev, type, member)
89 struct pfect_lru_node {
90 struct list_head list;
91 unsigned long long key;
95 struct list_head list;
96 struct pfect_lru_node *free_nodes;
97 unsigned int cur_size;
98 unsigned int lru_size;
99 unsigned int nr_unique;
100 unsigned int nr_misses;
105 static void pfect_lru_init(struct pfect_lru *lru, unsigned int lru_size,
106 unsigned int nr_possible_elems)
108 lru->map_fd = bpf_map_create(BPF_MAP_TYPE_HASH, NULL,
109 sizeof(unsigned long long),
110 sizeof(struct pfect_lru_node *),
111 nr_possible_elems, NULL);
112 assert(lru->map_fd != -1);
114 lru->free_nodes = malloc(lru_size * sizeof(struct pfect_lru_node));
115 assert(lru->free_nodes);
117 INIT_LIST_HEAD(&lru->list);
119 lru->lru_size = lru_size;
120 lru->nr_unique = lru->nr_misses = lru->total = 0;
123 static void pfect_lru_destroy(struct pfect_lru *lru)
126 free(lru->free_nodes);
129 static int pfect_lru_lookup_or_insert(struct pfect_lru *lru,
130 unsigned long long key)
132 struct pfect_lru_node *node = NULL;
136 if (!bpf_map_lookup_elem(lru->map_fd, &key, &node)) {
138 list_move(&node->list, &lru->list);
144 if (lru->cur_size < lru->lru_size) {
145 node = &lru->free_nodes[lru->cur_size++];
146 INIT_LIST_HEAD(&node->list);
148 struct pfect_lru_node *null_node = NULL;
150 node = list_last_entry(&lru->list,
151 struct pfect_lru_node,
153 bpf_map_update_elem(lru->map_fd, &node->key, &null_node, BPF_EXIST);
157 list_move(&node->list, &lru->list);
161 assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_EXIST));
164 assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_NOEXIST));
170 static unsigned int read_keys(const char *dist_file,
171 unsigned long long **keys)
174 unsigned long long *retkeys;
175 unsigned int counts = 0;
180 dist_fd = open(dist_file, 0);
181 assert(dist_fd != -1);
183 assert(fstat(dist_fd, &fst) == 0);
184 b = malloc(fst.st_size);
187 assert(read(dist_fd, b, fst.st_size) == fst.st_size);
189 for (i = 0; i < fst.st_size; i++) {
193 counts++; /* in case the last line has no \n */
195 retkeys = malloc(counts * sizeof(unsigned long long));
199 for (l = strtok(b, "\n"); l; l = strtok(NULL, "\n"))
200 retkeys[counts++] = strtoull(l, NULL, 10);
208 static int create_map(int map_type, int map_flags, unsigned int size)
210 LIBBPF_OPTS(bpf_map_create_opts, opts,
211 .map_flags = map_flags,
215 map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long),
216 sizeof(unsigned long long), size, &opts);
219 perror("bpf_create_map");
224 static int sched_next_online(int pid, int next_to_try)
228 if (next_to_try == nr_cpus)
231 while (next_to_try < nr_cpus) {
233 CPU_SET(next_to_try++, &cpuset);
234 if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset))
241 static void run_parallel(unsigned int tasks, void (*fn)(int i, void *data),
244 int next_sched_cpu = 0;
248 for (i = 0; i < tasks; i++) {
251 next_sched_cpu = sched_next_online(0, next_sched_cpu);
254 } else if (pid[i] == -1) {
255 printf("couldn't spawn #%d process\n", i);
258 /* It is mostly redundant and just allow the parent
259 * process to update next_shced_cpu for the next child
262 next_sched_cpu = sched_next_online(pid[i], next_sched_cpu);
264 for (i = 0; i < tasks; i++) {
267 assert(waitpid(pid[i], &status, 0) == pid[i]);
272 static void do_test_lru_dist(int task, void *data)
274 unsigned int nr_misses = 0;
275 struct pfect_lru pfect_lru;
276 unsigned long long key, value = 1234;
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;
283 pfect_lru_init(&pfect_lru, lru_size, dist_key_counts);
285 for (i = 0; i < dist_key_counts; i++) {
286 key = dist_keys[i] + key_offset;
288 pfect_lru_lookup_or_insert(&pfect_lru, key);
290 if (!bpf_map_lookup_elem(lru_map_fd, &key, &value))
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",
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,
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);
309 pfect_lru_destroy(&pfect_lru);
313 static void test_parallel_lru_dist(int map_type, int map_flags,
314 int nr_tasks, unsigned int lru_size)
319 printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
322 if (map_flags & BPF_F_NO_COMMON_LRU)
323 lru_map_fd = create_map(map_type, map_flags,
326 lru_map_fd = create_map(map_type, map_flags,
327 nr_tasks * lru_size);
328 assert(lru_map_fd != -1);
330 child_data[0] = lru_map_fd;
331 child_data[1] = lru_size;
333 run_parallel(nr_tasks, do_test_lru_dist, child_data);
338 static void test_lru_loss0(int map_type, int map_flags)
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;
346 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
349 assert(sched_next_online(0, 0) != -1);
351 if (map_flags & BPF_F_NO_COMMON_LRU)
352 map_fd = create_map(map_type, map_flags, 900 * nr_cpus);
354 map_fd = create_map(map_type, map_flags, 900);
356 assert(map_fd != -1);
360 for (key = 1; key <= 1000; key++) {
361 int start_key, end_key;
363 assert(bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST) == 0);
366 end_key = min(key, 900);
368 while (start_key <= end_key) {
369 bpf_map_lookup_elem(map_fd, &start_key, value);
374 for (key = 1; key <= 1000; key++) {
375 if (bpf_map_lookup_elem(map_fd, &key, value)) {
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);
392 static void test_lru_loss1(int map_type, int map_flags)
394 unsigned long long key, value[nr_cpus];
396 unsigned int nr_losses = 0;
398 printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
401 assert(sched_next_online(0, 0) != -1);
403 if (map_flags & BPF_F_NO_COMMON_LRU)
404 map_fd = create_map(map_type, map_flags, 1000 * nr_cpus);
406 map_fd = create_map(map_type, map_flags, 1000);
408 assert(map_fd != -1);
412 for (key = 1; key <= 1000; key++)
413 assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
415 for (key = 1; key <= 1000; key++) {
416 if (bpf_map_lookup_elem(map_fd, &key, value))
422 printf("nr_losses:%d(/1000)\n", nr_losses);
425 static void do_test_parallel_lru_loss(int task, void *data)
427 const unsigned int nr_stable_elems = 1000;
428 const unsigned int nr_repeats = 100000;
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;
437 stable_base = task * nr_repeats * 2 + 1;
438 next_ins_key = stable_base;
440 for (i = 0; i < nr_stable_elems; i++) {
441 assert(bpf_map_update_elem(map_fd, &next_ins_key, value,
446 for (i = 0; i < nr_repeats; i++) {
452 key = rn % nr_stable_elems + stable_base;
453 bpf_map_lookup_elem(map_fd, &key, value);
455 bpf_map_update_elem(map_fd, &next_ins_key, value,
462 for (i = 0; i < nr_stable_elems; i++) {
463 if (bpf_map_lookup_elem(map_fd, &key, value))
468 printf(" task:%d nr_losses:%u\n", task, nr_losses);
471 static void test_parallel_lru_loss(int map_type, int map_flags, int nr_tasks)
475 printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
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));
483 map_fd = create_map(map_type, map_flags,
484 nr_tasks * (1000 + 200));
486 assert(map_fd != -1);
488 run_parallel(nr_tasks, do_test_parallel_lru_loss, &map_fd);
493 int main(int argc, char **argv)
495 int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
496 const char *dist_file;
502 printf("Usage: %s <dist-file> <lru-size> <nr-tasks>\n",
508 lru_size = atoi(argv[2]);
509 nr_tasks = atoi(argv[3]);
511 setbuf(stdout, NULL);
515 nr_cpus = bpf_num_possible_cpus();
516 assert(nr_cpus != -1);
517 printf("nr_cpus:%d\n\n", nr_cpus);
519 nr_tasks = min(nr_tasks, nr_cpus);
521 dist_key_counts = read_keys(dist_file, &dist_keys);
522 if (!dist_key_counts) {
523 printf("%s has no key\n", dist_file);
527 for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) {
528 test_lru_loss0(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
529 test_lru_loss1(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
530 test_parallel_lru_loss(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
532 test_parallel_lru_dist(BPF_MAP_TYPE_LRU_HASH, map_flags[f],