125763b3cSThomas Gleixner // SPDX-License-Identifier: GPL-2.0-only
25db58fafSMartin KaFai Lau /*
35db58fafSMartin KaFai Lau * Copyright (c) 2016 Facebook
45db58fafSMartin KaFai Lau */
55db58fafSMartin KaFai Lau #define _GNU_SOURCE
65db58fafSMartin KaFai Lau #include <linux/types.h>
75db58fafSMartin KaFai Lau #include <stdio.h>
85db58fafSMartin KaFai Lau #include <unistd.h>
95db58fafSMartin KaFai Lau #include <linux/bpf.h>
105db58fafSMartin KaFai Lau #include <errno.h>
115db58fafSMartin KaFai Lau #include <string.h>
125db58fafSMartin KaFai Lau #include <assert.h>
135db58fafSMartin KaFai Lau #include <sched.h>
145db58fafSMartin KaFai Lau #include <sys/wait.h>
155db58fafSMartin KaFai Lau #include <sys/stat.h>
165db58fafSMartin KaFai Lau #include <fcntl.h>
175db58fafSMartin KaFai Lau #include <stdlib.h>
185db58fafSMartin KaFai Lau #include <time.h>
19e00c7b21SDaniel Borkmann
202bf3e2efSJakub Kicinski #include <bpf/bpf.h>
21e00c7b21SDaniel Borkmann #include "bpf_util.h"
225db58fafSMartin KaFai Lau
235db58fafSMartin KaFai Lau #define min(a, b) ((a) < (b) ? (a) : (b))
24dfc5be0dSAlexander Alemayhu #ifndef offsetof
255db58fafSMartin KaFai Lau # define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
26dfc5be0dSAlexander Alemayhu #endif
275db58fafSMartin KaFai Lau #define container_of(ptr, type, member) ({ \
285db58fafSMartin KaFai Lau const typeof( ((type *)0)->member ) *__mptr = (ptr); \
295db58fafSMartin KaFai Lau (type *)( (char *)__mptr - offsetof(type,member) );})
305db58fafSMartin KaFai Lau
315db58fafSMartin KaFai Lau static int nr_cpus;
325db58fafSMartin KaFai Lau static unsigned long long *dist_keys;
335db58fafSMartin KaFai Lau static unsigned int dist_key_counts;
345db58fafSMartin KaFai Lau
355db58fafSMartin KaFai Lau struct list_head {
365db58fafSMartin KaFai Lau struct list_head *next, *prev;
375db58fafSMartin KaFai Lau };
385db58fafSMartin KaFai Lau
INIT_LIST_HEAD(struct list_head * list)395db58fafSMartin KaFai Lau static inline void INIT_LIST_HEAD(struct list_head *list)
405db58fafSMartin KaFai Lau {
415db58fafSMartin KaFai Lau list->next = list;
425db58fafSMartin KaFai Lau list->prev = list;
435db58fafSMartin KaFai Lau }
445db58fafSMartin KaFai Lau
__list_add(struct list_head * new,struct list_head * prev,struct list_head * next)455db58fafSMartin KaFai Lau static inline void __list_add(struct list_head *new,
465db58fafSMartin KaFai Lau struct list_head *prev,
475db58fafSMartin KaFai Lau struct list_head *next)
485db58fafSMartin KaFai Lau {
495db58fafSMartin KaFai Lau next->prev = new;
505db58fafSMartin KaFai Lau new->next = next;
515db58fafSMartin KaFai Lau new->prev = prev;
525db58fafSMartin KaFai Lau prev->next = new;
535db58fafSMartin KaFai Lau }
545db58fafSMartin KaFai Lau
list_add(struct list_head * new,struct list_head * head)555db58fafSMartin KaFai Lau static inline void list_add(struct list_head *new, struct list_head *head)
565db58fafSMartin KaFai Lau {
575db58fafSMartin KaFai Lau __list_add(new, head, head->next);
585db58fafSMartin KaFai Lau }
595db58fafSMartin KaFai Lau
__list_del(struct list_head * prev,struct list_head * next)605db58fafSMartin KaFai Lau static inline void __list_del(struct list_head *prev, struct list_head *next)
615db58fafSMartin KaFai Lau {
625db58fafSMartin KaFai Lau next->prev = prev;
635db58fafSMartin KaFai Lau prev->next = next;
645db58fafSMartin KaFai Lau }
655db58fafSMartin KaFai Lau
__list_del_entry(struct list_head * entry)665db58fafSMartin KaFai Lau static inline void __list_del_entry(struct list_head *entry)
675db58fafSMartin KaFai Lau {
685db58fafSMartin KaFai Lau __list_del(entry->prev, entry->next);
695db58fafSMartin KaFai Lau }
705db58fafSMartin KaFai Lau
list_move(struct list_head * list,struct list_head * head)715db58fafSMartin KaFai Lau static inline void list_move(struct list_head *list, struct list_head *head)
725db58fafSMartin KaFai Lau {
735db58fafSMartin KaFai Lau __list_del_entry(list);
745db58fafSMartin KaFai Lau list_add(list, head);
755db58fafSMartin KaFai Lau }
765db58fafSMartin KaFai Lau
775db58fafSMartin KaFai Lau #define list_entry(ptr, type, member) \
785db58fafSMartin KaFai Lau container_of(ptr, type, member)
795db58fafSMartin KaFai Lau
805db58fafSMartin KaFai Lau #define list_last_entry(ptr, type, member) \
815db58fafSMartin KaFai Lau list_entry((ptr)->prev, type, member)
825db58fafSMartin KaFai Lau
835db58fafSMartin KaFai Lau struct pfect_lru_node {
845db58fafSMartin KaFai Lau struct list_head list;
855db58fafSMartin KaFai Lau unsigned long long key;
865db58fafSMartin KaFai Lau };
875db58fafSMartin KaFai Lau
885db58fafSMartin KaFai Lau struct pfect_lru {
895db58fafSMartin KaFai Lau struct list_head list;
905db58fafSMartin KaFai Lau struct pfect_lru_node *free_nodes;
915db58fafSMartin KaFai Lau unsigned int cur_size;
925db58fafSMartin KaFai Lau unsigned int lru_size;
935db58fafSMartin KaFai Lau unsigned int nr_unique;
945db58fafSMartin KaFai Lau unsigned int nr_misses;
955db58fafSMartin KaFai Lau unsigned int total;
965db58fafSMartin KaFai Lau int map_fd;
975db58fafSMartin KaFai Lau };
985db58fafSMartin KaFai Lau
pfect_lru_init(struct pfect_lru * lru,unsigned int lru_size,unsigned int nr_possible_elems)995db58fafSMartin KaFai Lau static void pfect_lru_init(struct pfect_lru *lru, unsigned int lru_size,
1005db58fafSMartin KaFai Lau unsigned int nr_possible_elems)
1015db58fafSMartin KaFai Lau {
102c58f9815SAndrii Nakryiko lru->map_fd = bpf_map_create(BPF_MAP_TYPE_HASH, NULL,
1035db58fafSMartin KaFai Lau sizeof(unsigned long long),
1045db58fafSMartin KaFai Lau sizeof(struct pfect_lru_node *),
105c58f9815SAndrii Nakryiko nr_possible_elems, NULL);
1065db58fafSMartin KaFai Lau assert(lru->map_fd != -1);
1075db58fafSMartin KaFai Lau
1085db58fafSMartin KaFai Lau lru->free_nodes = malloc(lru_size * sizeof(struct pfect_lru_node));
1095db58fafSMartin KaFai Lau assert(lru->free_nodes);
1105db58fafSMartin KaFai Lau
1115db58fafSMartin KaFai Lau INIT_LIST_HEAD(&lru->list);
1125db58fafSMartin KaFai Lau lru->cur_size = 0;
1135db58fafSMartin KaFai Lau lru->lru_size = lru_size;
1145db58fafSMartin KaFai Lau lru->nr_unique = lru->nr_misses = lru->total = 0;
1155db58fafSMartin KaFai Lau }
1165db58fafSMartin KaFai Lau
pfect_lru_destroy(struct pfect_lru * lru)1175db58fafSMartin KaFai Lau static void pfect_lru_destroy(struct pfect_lru *lru)
1185db58fafSMartin KaFai Lau {
1195db58fafSMartin KaFai Lau close(lru->map_fd);
1205db58fafSMartin KaFai Lau free(lru->free_nodes);
1215db58fafSMartin KaFai Lau }
1225db58fafSMartin KaFai Lau
pfect_lru_lookup_or_insert(struct pfect_lru * lru,unsigned long long key)1235db58fafSMartin KaFai Lau static int pfect_lru_lookup_or_insert(struct pfect_lru *lru,
1245db58fafSMartin KaFai Lau unsigned long long key)
1255db58fafSMartin KaFai Lau {
1265db58fafSMartin KaFai Lau struct pfect_lru_node *node = NULL;
1275db58fafSMartin KaFai Lau int seen = 0;
1285db58fafSMartin KaFai Lau
1295db58fafSMartin KaFai Lau lru->total++;
130d40fc181SJoe Stringer if (!bpf_map_lookup_elem(lru->map_fd, &key, &node)) {
1315db58fafSMartin KaFai Lau if (node) {
1325db58fafSMartin KaFai Lau list_move(&node->list, &lru->list);
1335db58fafSMartin KaFai Lau return 1;
1345db58fafSMartin KaFai Lau }
1355db58fafSMartin KaFai Lau seen = 1;
1365db58fafSMartin KaFai Lau }
1375db58fafSMartin KaFai Lau
1385db58fafSMartin KaFai Lau if (lru->cur_size < lru->lru_size) {
1395db58fafSMartin KaFai Lau node = &lru->free_nodes[lru->cur_size++];
1405db58fafSMartin KaFai Lau INIT_LIST_HEAD(&node->list);
1415db58fafSMartin KaFai Lau } else {
1425db58fafSMartin KaFai Lau struct pfect_lru_node *null_node = NULL;
1435db58fafSMartin KaFai Lau
1445db58fafSMartin KaFai Lau node = list_last_entry(&lru->list,
1455db58fafSMartin KaFai Lau struct pfect_lru_node,
1465db58fafSMartin KaFai Lau list);
147d40fc181SJoe Stringer bpf_map_update_elem(lru->map_fd, &node->key, &null_node, BPF_EXIST);
1485db58fafSMartin KaFai Lau }
1495db58fafSMartin KaFai Lau
1505db58fafSMartin KaFai Lau node->key = key;
1515db58fafSMartin KaFai Lau list_move(&node->list, &lru->list);
1525db58fafSMartin KaFai Lau
1535db58fafSMartin KaFai Lau lru->nr_misses++;
1545db58fafSMartin KaFai Lau if (seen) {
155d40fc181SJoe Stringer assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_EXIST));
1565db58fafSMartin KaFai Lau } else {
1575db58fafSMartin KaFai Lau lru->nr_unique++;
158d40fc181SJoe Stringer assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_NOEXIST));
1595db58fafSMartin KaFai Lau }
1605db58fafSMartin KaFai Lau
1615db58fafSMartin KaFai Lau return seen;
1625db58fafSMartin KaFai Lau }
1635db58fafSMartin KaFai Lau
read_keys(const char * dist_file,unsigned long long ** keys)1645db58fafSMartin KaFai Lau static unsigned int read_keys(const char *dist_file,
1655db58fafSMartin KaFai Lau unsigned long long **keys)
1665db58fafSMartin KaFai Lau {
1675db58fafSMartin KaFai Lau struct stat fst;
1685db58fafSMartin KaFai Lau unsigned long long *retkeys;
1695db58fafSMartin KaFai Lau unsigned int counts = 0;
1705db58fafSMartin KaFai Lau int dist_fd;
1715db58fafSMartin KaFai Lau char *b, *l;
1725db58fafSMartin KaFai Lau int i;
1735db58fafSMartin KaFai Lau
1745db58fafSMartin KaFai Lau dist_fd = open(dist_file, 0);
1755db58fafSMartin KaFai Lau assert(dist_fd != -1);
1765db58fafSMartin KaFai Lau
1775db58fafSMartin KaFai Lau assert(fstat(dist_fd, &fst) == 0);
1785db58fafSMartin KaFai Lau b = malloc(fst.st_size);
1795db58fafSMartin KaFai Lau assert(b);
1805db58fafSMartin KaFai Lau
1815db58fafSMartin KaFai Lau assert(read(dist_fd, b, fst.st_size) == fst.st_size);
1825db58fafSMartin KaFai Lau close(dist_fd);
1835db58fafSMartin KaFai Lau for (i = 0; i < fst.st_size; i++) {
1845db58fafSMartin KaFai Lau if (b[i] == '\n')
1855db58fafSMartin KaFai Lau counts++;
1865db58fafSMartin KaFai Lau }
1875db58fafSMartin KaFai Lau counts++; /* in case the last line has no \n */
1885db58fafSMartin KaFai Lau
1895db58fafSMartin KaFai Lau retkeys = malloc(counts * sizeof(unsigned long long));
1905db58fafSMartin KaFai Lau assert(retkeys);
1915db58fafSMartin KaFai Lau
1925db58fafSMartin KaFai Lau counts = 0;
1935db58fafSMartin KaFai Lau for (l = strtok(b, "\n"); l; l = strtok(NULL, "\n"))
1945db58fafSMartin KaFai Lau retkeys[counts++] = strtoull(l, NULL, 10);
1955db58fafSMartin KaFai Lau free(b);
1965db58fafSMartin KaFai Lau
1975db58fafSMartin KaFai Lau *keys = retkeys;
1985db58fafSMartin KaFai Lau
1995db58fafSMartin KaFai Lau return counts;
2005db58fafSMartin KaFai Lau }
2015db58fafSMartin KaFai Lau
create_map(int map_type,int map_flags,unsigned int size)2025db58fafSMartin KaFai Lau static int create_map(int map_type, int map_flags, unsigned int size)
2035db58fafSMartin KaFai Lau {
204c58f9815SAndrii Nakryiko LIBBPF_OPTS(bpf_map_create_opts, opts,
205c58f9815SAndrii Nakryiko .map_flags = map_flags,
206c58f9815SAndrii Nakryiko );
2075db58fafSMartin KaFai Lau int map_fd;
2085db58fafSMartin KaFai Lau
209c58f9815SAndrii Nakryiko map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long),
210c58f9815SAndrii Nakryiko sizeof(unsigned long long), size, &opts);
2115db58fafSMartin KaFai Lau
2125db58fafSMartin KaFai Lau if (map_fd == -1)
2135db58fafSMartin KaFai Lau perror("bpf_create_map");
2145db58fafSMartin KaFai Lau
2155db58fafSMartin KaFai Lau return map_fd;
2165db58fafSMartin KaFai Lau }
2175db58fafSMartin KaFai Lau
sched_next_online(int pid,int next_to_try)2185db58fafSMartin KaFai Lau static int sched_next_online(int pid, int next_to_try)
2195db58fafSMartin KaFai Lau {
2205db58fafSMartin KaFai Lau cpu_set_t cpuset;
2215db58fafSMartin KaFai Lau
2225db58fafSMartin KaFai Lau if (next_to_try == nr_cpus)
2235db58fafSMartin KaFai Lau return -1;
2245db58fafSMartin KaFai Lau
2255db58fafSMartin KaFai Lau while (next_to_try < nr_cpus) {
2265db58fafSMartin KaFai Lau CPU_ZERO(&cpuset);
2275db58fafSMartin KaFai Lau CPU_SET(next_to_try++, &cpuset);
2285db58fafSMartin KaFai Lau if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset))
2295db58fafSMartin KaFai Lau break;
2305db58fafSMartin KaFai Lau }
2315db58fafSMartin KaFai Lau
2325db58fafSMartin KaFai Lau return next_to_try;
2335db58fafSMartin KaFai Lau }
2345db58fafSMartin KaFai Lau
run_parallel(unsigned int tasks,void (* fn)(int i,void * data),void * data)2355db58fafSMartin KaFai Lau static void run_parallel(unsigned int tasks, void (*fn)(int i, void *data),
2365db58fafSMartin KaFai Lau void *data)
2375db58fafSMartin KaFai Lau {
2385db58fafSMartin KaFai Lau int next_sched_cpu = 0;
2395db58fafSMartin KaFai Lau pid_t pid[tasks];
2405db58fafSMartin KaFai Lau int i;
2415db58fafSMartin KaFai Lau
2425db58fafSMartin KaFai Lau for (i = 0; i < tasks; i++) {
2435db58fafSMartin KaFai Lau pid[i] = fork();
2445db58fafSMartin KaFai Lau if (pid[i] == 0) {
2455db58fafSMartin KaFai Lau next_sched_cpu = sched_next_online(0, next_sched_cpu);
2465db58fafSMartin KaFai Lau fn(i, data);
2475db58fafSMartin KaFai Lau exit(0);
2485db58fafSMartin KaFai Lau } else if (pid[i] == -1) {
2495db58fafSMartin KaFai Lau printf("couldn't spawn #%d process\n", i);
2505db58fafSMartin KaFai Lau exit(1);
2515db58fafSMartin KaFai Lau }
2525db58fafSMartin KaFai Lau /* It is mostly redundant and just allow the parent
2535db58fafSMartin KaFai Lau * process to update next_shced_cpu for the next child
2545db58fafSMartin KaFai Lau * process
2555db58fafSMartin KaFai Lau */
2565db58fafSMartin KaFai Lau next_sched_cpu = sched_next_online(pid[i], next_sched_cpu);
2575db58fafSMartin KaFai Lau }
2585db58fafSMartin KaFai Lau for (i = 0; i < tasks; i++) {
2595db58fafSMartin KaFai Lau int status;
2605db58fafSMartin KaFai Lau
2615db58fafSMartin KaFai Lau assert(waitpid(pid[i], &status, 0) == pid[i]);
2625db58fafSMartin KaFai Lau assert(status == 0);
2635db58fafSMartin KaFai Lau }
2645db58fafSMartin KaFai Lau }
2655db58fafSMartin KaFai Lau
do_test_lru_dist(int task,void * data)2665db58fafSMartin KaFai Lau static void do_test_lru_dist(int task, void *data)
2675db58fafSMartin KaFai Lau {
2685db58fafSMartin KaFai Lau unsigned int nr_misses = 0;
2695db58fafSMartin KaFai Lau struct pfect_lru pfect_lru;
2705db58fafSMartin KaFai Lau unsigned long long key, value = 1234;
2715db58fafSMartin KaFai Lau unsigned int i;
2725db58fafSMartin KaFai Lau
2735db58fafSMartin KaFai Lau unsigned int lru_map_fd = ((unsigned int *)data)[0];
2745db58fafSMartin KaFai Lau unsigned int lru_size = ((unsigned int *)data)[1];
2755db58fafSMartin KaFai Lau unsigned long long key_offset = task * dist_key_counts;
2765db58fafSMartin KaFai Lau
2775db58fafSMartin KaFai Lau pfect_lru_init(&pfect_lru, lru_size, dist_key_counts);
2785db58fafSMartin KaFai Lau
2795db58fafSMartin KaFai Lau for (i = 0; i < dist_key_counts; i++) {
2805db58fafSMartin KaFai Lau key = dist_keys[i] + key_offset;
2815db58fafSMartin KaFai Lau
2825db58fafSMartin KaFai Lau pfect_lru_lookup_or_insert(&pfect_lru, key);
2835db58fafSMartin KaFai Lau
284d40fc181SJoe Stringer if (!bpf_map_lookup_elem(lru_map_fd, &key, &value))
2855db58fafSMartin KaFai Lau continue;
2865db58fafSMartin KaFai Lau
287d40fc181SJoe Stringer if (bpf_map_update_elem(lru_map_fd, &key, &value, BPF_NOEXIST)) {
288d40fc181SJoe Stringer printf("bpf_map_update_elem(lru_map_fd, %llu): errno:%d\n",
2895db58fafSMartin KaFai Lau key, errno);
2905db58fafSMartin KaFai Lau assert(0);
2915db58fafSMartin KaFai Lau }
2925db58fafSMartin KaFai Lau
2935db58fafSMartin KaFai Lau nr_misses++;
2945db58fafSMartin KaFai Lau }
2955db58fafSMartin KaFai Lau
2965db58fafSMartin KaFai Lau printf(" task:%d BPF LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
2975db58fafSMartin KaFai Lau task, pfect_lru.nr_unique, dist_key_counts, nr_misses,
2985db58fafSMartin KaFai Lau dist_key_counts);
2995db58fafSMartin KaFai Lau printf(" task:%d Perfect LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
3005db58fafSMartin KaFai Lau task, pfect_lru.nr_unique, pfect_lru.total,
3015db58fafSMartin KaFai Lau pfect_lru.nr_misses, pfect_lru.total);
3025db58fafSMartin KaFai Lau
3035db58fafSMartin KaFai Lau pfect_lru_destroy(&pfect_lru);
3045db58fafSMartin KaFai Lau close(lru_map_fd);
3055db58fafSMartin KaFai Lau }
3065db58fafSMartin KaFai Lau
test_parallel_lru_dist(int map_type,int map_flags,int nr_tasks,unsigned int lru_size)3075db58fafSMartin KaFai Lau static void test_parallel_lru_dist(int map_type, int map_flags,
3085db58fafSMartin KaFai Lau int nr_tasks, unsigned int lru_size)
3095db58fafSMartin KaFai Lau {
3105db58fafSMartin KaFai Lau int child_data[2];
3115db58fafSMartin KaFai Lau int lru_map_fd;
3125db58fafSMartin KaFai Lau
3135db58fafSMartin KaFai Lau printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
3145db58fafSMartin KaFai Lau map_flags);
3155db58fafSMartin KaFai Lau
3165db58fafSMartin KaFai Lau if (map_flags & BPF_F_NO_COMMON_LRU)
3175db58fafSMartin KaFai Lau lru_map_fd = create_map(map_type, map_flags,
3185db58fafSMartin KaFai Lau nr_cpus * lru_size);
3195db58fafSMartin KaFai Lau else
3205db58fafSMartin KaFai Lau lru_map_fd = create_map(map_type, map_flags,
3215db58fafSMartin KaFai Lau nr_tasks * lru_size);
3225db58fafSMartin KaFai Lau assert(lru_map_fd != -1);
3235db58fafSMartin KaFai Lau
3245db58fafSMartin KaFai Lau child_data[0] = lru_map_fd;
3255db58fafSMartin KaFai Lau child_data[1] = lru_size;
3265db58fafSMartin KaFai Lau
3275db58fafSMartin KaFai Lau run_parallel(nr_tasks, do_test_lru_dist, child_data);
3285db58fafSMartin KaFai Lau
3295db58fafSMartin KaFai Lau close(lru_map_fd);
3305db58fafSMartin KaFai Lau }
3315db58fafSMartin KaFai Lau
test_lru_loss0(int map_type,int map_flags)3325db58fafSMartin KaFai Lau static void test_lru_loss0(int map_type, int map_flags)
3335db58fafSMartin KaFai Lau {
3345db58fafSMartin KaFai Lau unsigned long long key, value[nr_cpus];
3355db58fafSMartin KaFai Lau unsigned int old_unused_losses = 0;
3365db58fafSMartin KaFai Lau unsigned int new_unused_losses = 0;
3375db58fafSMartin KaFai Lau unsigned int used_losses = 0;
3385db58fafSMartin KaFai Lau int map_fd;
3395db58fafSMartin KaFai Lau
3405db58fafSMartin KaFai Lau printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
3415db58fafSMartin KaFai Lau map_flags);
3425db58fafSMartin KaFai Lau
3435db58fafSMartin KaFai Lau assert(sched_next_online(0, 0) != -1);
3445db58fafSMartin KaFai Lau
3455db58fafSMartin KaFai Lau if (map_flags & BPF_F_NO_COMMON_LRU)
3465db58fafSMartin KaFai Lau map_fd = create_map(map_type, map_flags, 900 * nr_cpus);
3475db58fafSMartin KaFai Lau else
3485db58fafSMartin KaFai Lau map_fd = create_map(map_type, map_flags, 900);
3495db58fafSMartin KaFai Lau
3505db58fafSMartin KaFai Lau assert(map_fd != -1);
3515db58fafSMartin KaFai Lau
3525db58fafSMartin KaFai Lau value[0] = 1234;
3535db58fafSMartin KaFai Lau
3545db58fafSMartin KaFai Lau for (key = 1; key <= 1000; key++) {
3555db58fafSMartin KaFai Lau int start_key, end_key;
3565db58fafSMartin KaFai Lau
357d40fc181SJoe Stringer assert(bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST) == 0);
3585db58fafSMartin KaFai Lau
3595db58fafSMartin KaFai Lau start_key = 101;
3605db58fafSMartin KaFai Lau end_key = min(key, 900);
3615db58fafSMartin KaFai Lau
3625db58fafSMartin KaFai Lau while (start_key <= end_key) {
363d40fc181SJoe Stringer bpf_map_lookup_elem(map_fd, &start_key, value);
3645db58fafSMartin KaFai Lau start_key++;
3655db58fafSMartin KaFai Lau }
3665db58fafSMartin KaFai Lau }
3675db58fafSMartin KaFai Lau
3685db58fafSMartin KaFai Lau for (key = 1; key <= 1000; key++) {
369d40fc181SJoe Stringer if (bpf_map_lookup_elem(map_fd, &key, value)) {
3705db58fafSMartin KaFai Lau if (key <= 100)
3715db58fafSMartin KaFai Lau old_unused_losses++;
3725db58fafSMartin KaFai Lau else if (key <= 900)
3735db58fafSMartin KaFai Lau used_losses++;
3745db58fafSMartin KaFai Lau else
3755db58fafSMartin KaFai Lau new_unused_losses++;
3765db58fafSMartin KaFai Lau }
3775db58fafSMartin KaFai Lau }
3785db58fafSMartin KaFai Lau
3795db58fafSMartin KaFai Lau close(map_fd);
3805db58fafSMartin KaFai Lau
3815db58fafSMartin KaFai Lau printf("older-elem-losses:%d(/100) active-elem-losses:%d(/800) "
3825db58fafSMartin KaFai Lau "newer-elem-losses:%d(/100)\n",
3835db58fafSMartin KaFai Lau old_unused_losses, used_losses, new_unused_losses);
3845db58fafSMartin KaFai Lau }
3855db58fafSMartin KaFai Lau
test_lru_loss1(int map_type,int map_flags)3865db58fafSMartin KaFai Lau static void test_lru_loss1(int map_type, int map_flags)
3875db58fafSMartin KaFai Lau {
3885db58fafSMartin KaFai Lau unsigned long long key, value[nr_cpus];
3895db58fafSMartin KaFai Lau int map_fd;
3905db58fafSMartin KaFai Lau unsigned int nr_losses = 0;
3915db58fafSMartin KaFai Lau
3925db58fafSMartin KaFai Lau printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
3935db58fafSMartin KaFai Lau map_flags);
3945db58fafSMartin KaFai Lau
3955db58fafSMartin KaFai Lau assert(sched_next_online(0, 0) != -1);
3965db58fafSMartin KaFai Lau
3975db58fafSMartin KaFai Lau if (map_flags & BPF_F_NO_COMMON_LRU)
3985db58fafSMartin KaFai Lau map_fd = create_map(map_type, map_flags, 1000 * nr_cpus);
3995db58fafSMartin KaFai Lau else
4005db58fafSMartin KaFai Lau map_fd = create_map(map_type, map_flags, 1000);
4015db58fafSMartin KaFai Lau
4025db58fafSMartin KaFai Lau assert(map_fd != -1);
4035db58fafSMartin KaFai Lau
4045db58fafSMartin KaFai Lau value[0] = 1234;
4055db58fafSMartin KaFai Lau
4065db58fafSMartin KaFai Lau for (key = 1; key <= 1000; key++)
407d40fc181SJoe Stringer assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
4085db58fafSMartin KaFai Lau
4095db58fafSMartin KaFai Lau for (key = 1; key <= 1000; key++) {
410d40fc181SJoe Stringer if (bpf_map_lookup_elem(map_fd, &key, value))
4115db58fafSMartin KaFai Lau nr_losses++;
4125db58fafSMartin KaFai Lau }
4135db58fafSMartin KaFai Lau
4145db58fafSMartin KaFai Lau close(map_fd);
4155db58fafSMartin KaFai Lau
4165db58fafSMartin KaFai Lau printf("nr_losses:%d(/1000)\n", nr_losses);
4175db58fafSMartin KaFai Lau }
4185db58fafSMartin KaFai Lau
do_test_parallel_lru_loss(int task,void * data)4195db58fafSMartin KaFai Lau static void do_test_parallel_lru_loss(int task, void *data)
4205db58fafSMartin KaFai Lau {
4215db58fafSMartin KaFai Lau const unsigned int nr_stable_elems = 1000;
4225db58fafSMartin KaFai Lau const unsigned int nr_repeats = 100000;
4235db58fafSMartin KaFai Lau
4245db58fafSMartin KaFai Lau int map_fd = *(int *)data;
4255db58fafSMartin KaFai Lau unsigned long long stable_base;
4265db58fafSMartin KaFai Lau unsigned long long key, value[nr_cpus];
4275db58fafSMartin KaFai Lau unsigned long long next_ins_key;
4285db58fafSMartin KaFai Lau unsigned int nr_losses = 0;
4295db58fafSMartin KaFai Lau unsigned int i;
4305db58fafSMartin KaFai Lau
4315db58fafSMartin KaFai Lau stable_base = task * nr_repeats * 2 + 1;
4325db58fafSMartin KaFai Lau next_ins_key = stable_base;
4335db58fafSMartin KaFai Lau value[0] = 1234;
4345db58fafSMartin KaFai Lau for (i = 0; i < nr_stable_elems; i++) {
435d40fc181SJoe Stringer assert(bpf_map_update_elem(map_fd, &next_ins_key, value,
4365db58fafSMartin KaFai Lau BPF_NOEXIST) == 0);
4375db58fafSMartin KaFai Lau next_ins_key++;
4385db58fafSMartin KaFai Lau }
4395db58fafSMartin KaFai Lau
4405db58fafSMartin KaFai Lau for (i = 0; i < nr_repeats; i++) {
4415db58fafSMartin KaFai Lau int rn;
4425db58fafSMartin KaFai Lau
4435db58fafSMartin KaFai Lau rn = rand();
4445db58fafSMartin KaFai Lau
4455db58fafSMartin KaFai Lau if (rn % 10) {
4465db58fafSMartin KaFai Lau key = rn % nr_stable_elems + stable_base;
447d40fc181SJoe Stringer bpf_map_lookup_elem(map_fd, &key, value);
4485db58fafSMartin KaFai Lau } else {
449d40fc181SJoe Stringer bpf_map_update_elem(map_fd, &next_ins_key, value,
4505db58fafSMartin KaFai Lau BPF_NOEXIST);
4515db58fafSMartin KaFai Lau next_ins_key++;
4525db58fafSMartin KaFai Lau }
4535db58fafSMartin KaFai Lau }
4545db58fafSMartin KaFai Lau
4555db58fafSMartin KaFai Lau key = stable_base;
4565db58fafSMartin KaFai Lau for (i = 0; i < nr_stable_elems; i++) {
457d40fc181SJoe Stringer if (bpf_map_lookup_elem(map_fd, &key, value))
4585db58fafSMartin KaFai Lau nr_losses++;
4595db58fafSMartin KaFai Lau key++;
4605db58fafSMartin KaFai Lau }
4615db58fafSMartin KaFai Lau
4625db58fafSMartin KaFai Lau printf(" task:%d nr_losses:%u\n", task, nr_losses);
4635db58fafSMartin KaFai Lau }
4645db58fafSMartin KaFai Lau
test_parallel_lru_loss(int map_type,int map_flags,int nr_tasks)4655db58fafSMartin KaFai Lau static void test_parallel_lru_loss(int map_type, int map_flags, int nr_tasks)
4665db58fafSMartin KaFai Lau {
4675db58fafSMartin KaFai Lau int map_fd;
4685db58fafSMartin KaFai Lau
4695db58fafSMartin KaFai Lau printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
4705db58fafSMartin KaFai Lau map_flags);
4715db58fafSMartin KaFai Lau
4725db58fafSMartin KaFai Lau /* Give 20% more than the active working set */
4735db58fafSMartin KaFai Lau if (map_flags & BPF_F_NO_COMMON_LRU)
4745db58fafSMartin KaFai Lau map_fd = create_map(map_type, map_flags,
4755db58fafSMartin KaFai Lau nr_cpus * (1000 + 200));
4765db58fafSMartin KaFai Lau else
4775db58fafSMartin KaFai Lau map_fd = create_map(map_type, map_flags,
4785db58fafSMartin KaFai Lau nr_tasks * (1000 + 200));
4795db58fafSMartin KaFai Lau
4805db58fafSMartin KaFai Lau assert(map_fd != -1);
4815db58fafSMartin KaFai Lau
4825db58fafSMartin KaFai Lau run_parallel(nr_tasks, do_test_parallel_lru_loss, &map_fd);
4835db58fafSMartin KaFai Lau
4845db58fafSMartin KaFai Lau close(map_fd);
4855db58fafSMartin KaFai Lau }
4865db58fafSMartin KaFai Lau
main(int argc,char ** argv)4875db58fafSMartin KaFai Lau int main(int argc, char **argv)
4885db58fafSMartin KaFai Lau {
4895db58fafSMartin KaFai Lau int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
4905db58fafSMartin KaFai Lau const char *dist_file;
4915db58fafSMartin KaFai Lau int nr_tasks = 1;
4925db58fafSMartin KaFai Lau int lru_size;
4935db58fafSMartin KaFai Lau int f;
4945db58fafSMartin KaFai Lau
4955db58fafSMartin KaFai Lau if (argc < 4) {
4965db58fafSMartin KaFai Lau printf("Usage: %s <dist-file> <lru-size> <nr-tasks>\n",
4975db58fafSMartin KaFai Lau argv[0]);
4985db58fafSMartin KaFai Lau return -1;
4995db58fafSMartin KaFai Lau }
5005db58fafSMartin KaFai Lau
5015db58fafSMartin KaFai Lau dist_file = argv[1];
5025db58fafSMartin KaFai Lau lru_size = atoi(argv[2]);
5035db58fafSMartin KaFai Lau nr_tasks = atoi(argv[3]);
5045db58fafSMartin KaFai Lau
5055db58fafSMartin KaFai Lau setbuf(stdout, NULL);
5065db58fafSMartin KaFai Lau
5075db58fafSMartin KaFai Lau srand(time(NULL));
5085db58fafSMartin KaFai Lau
509e00c7b21SDaniel Borkmann nr_cpus = bpf_num_possible_cpus();
5105db58fafSMartin KaFai Lau assert(nr_cpus != -1);
5115db58fafSMartin KaFai Lau printf("nr_cpus:%d\n\n", nr_cpus);
5125db58fafSMartin KaFai Lau
5135db58fafSMartin KaFai Lau nr_tasks = min(nr_tasks, nr_cpus);
5145db58fafSMartin KaFai Lau
5155db58fafSMartin KaFai Lau dist_key_counts = read_keys(dist_file, &dist_keys);
5165db58fafSMartin KaFai Lau if (!dist_key_counts) {
5175db58fafSMartin KaFai Lau printf("%s has no key\n", dist_file);
5185db58fafSMartin KaFai Lau return -1;
5195db58fafSMartin KaFai Lau }
5205db58fafSMartin KaFai Lau
521*b1fc28b3SLinkui Xiao for (f = 0; f < ARRAY_SIZE(map_flags); f++) {
5225db58fafSMartin KaFai Lau test_lru_loss0(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
5235db58fafSMartin KaFai Lau test_lru_loss1(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
5245db58fafSMartin KaFai Lau test_parallel_lru_loss(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
5255db58fafSMartin KaFai Lau nr_tasks);
5265db58fafSMartin KaFai Lau test_parallel_lru_dist(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
5275db58fafSMartin KaFai Lau nr_tasks, lru_size);
5285db58fafSMartin KaFai Lau printf("\n");
5295db58fafSMartin KaFai Lau }
5305db58fafSMartin KaFai Lau
5315db58fafSMartin KaFai Lau free(dist_keys);
5325db58fafSMartin KaFai Lau
5335db58fafSMartin KaFai Lau return 0;
5345db58fafSMartin KaFai Lau }
535