[linux-block.git] / samples / bpf / test_lru_dist.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright (c) 2016 Facebook
 */
#define _GNU_SOURCE
#include <linux/types.h>
#include <stdio.h>
#include <unistd.h>
#include <linux/bpf.h>
#include <errno.h>
#include <string.h>
#include <assert.h>
#include <sched.h>
#include <sys/wait.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <time.h>

#include <bpf/bpf.h>
#include "bpf_util.h"

#define min(a, b) ((a) < (b) ? (a) : (b))
#ifndef offsetof
# define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
#endif
#define container_of(ptr, type, member) ({			\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
	(type *)( (char *)__mptr - offsetof(type,member) );})

static int nr_cpus;
static unsigned long long *dist_keys;
static unsigned int dist_key_counts;

struct list_head {
	struct list_head *next, *prev;
};

static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
	next->prev = prev;
	prev->next = next;
}

static inline void __list_del_entry(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
}

static inline void list_move(struct list_head *list, struct list_head *head)
{
	__list_del_entry(list);
	list_add(list, head);
}

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

#define list_last_entry(ptr, type, member) \
	list_entry((ptr)->prev, type, member)

struct pfect_lru_node {
	struct list_head list;
	unsigned long long key;
};

struct pfect_lru {
	struct list_head list;
	struct pfect_lru_node *free_nodes;
	unsigned int cur_size;
	unsigned int lru_size;
	unsigned int nr_unique;
	unsigned int nr_misses;
	unsigned int total;
	int map_fd;
};

static void pfect_lru_init(struct pfect_lru *lru, unsigned int lru_size,
			   unsigned int nr_possible_elems)
{
	lru->map_fd = bpf_map_create(BPF_MAP_TYPE_HASH, NULL,
				     sizeof(unsigned long long),
				     sizeof(struct pfect_lru_node *),
				     nr_possible_elems, NULL);
	assert(lru->map_fd != -1);

	lru->free_nodes = malloc(lru_size * sizeof(struct pfect_lru_node));
	assert(lru->free_nodes);

	INIT_LIST_HEAD(&lru->list);
	lru->cur_size = 0;
	lru->lru_size = lru_size;
	lru->nr_unique = lru->nr_misses = lru->total = 0;
}

static void pfect_lru_destroy(struct pfect_lru *lru)
{
	close(lru->map_fd);
	free(lru->free_nodes);
}

static int pfect_lru_lookup_or_insert(struct pfect_lru *lru,
				      unsigned long long key)
{
	struct pfect_lru_node *node = NULL;
	int seen = 0;

	lru->total++;
	if (!bpf_map_lookup_elem(lru->map_fd, &key, &node)) {
		if (node) {
			list_move(&node->list, &lru->list);
			return 1;
		}
		seen = 1;
	}

	if (lru->cur_size < lru->lru_size) {
		node =  &lru->free_nodes[lru->cur_size++];
		INIT_LIST_HEAD(&node->list);
	} else {
		struct pfect_lru_node *null_node = NULL;

		node = list_last_entry(&lru->list,
				       struct pfect_lru_node,
				       list);
		bpf_map_update_elem(lru->map_fd, &node->key, &null_node, BPF_EXIST);
	}

	node->key = key;
	list_move(&node->list, &lru->list);

	lru->nr_misses++;
	if (seen) {
		assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_EXIST));
	} else {
		lru->nr_unique++;
		assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_NOEXIST));
	}

	return seen;
}

static unsigned int read_keys(const char *dist_file,
			      unsigned long long **keys)
{
	struct stat fst;
	unsigned long long *retkeys;
	unsigned int counts = 0;
	int dist_fd;
	char *b, *l;
	int i;

	dist_fd = open(dist_file, 0);
	assert(dist_fd != -1);

	assert(fstat(dist_fd, &fst) == 0);
	b = malloc(fst.st_size);
	assert(b);

	assert(read(dist_fd, b, fst.st_size) == fst.st_size);
	close(dist_fd);
	for (i = 0; i < fst.st_size; i++) {
		if (b[i] == '\n')
			counts++;
	}
	counts++; /* in case the last line has no \n */

	retkeys = malloc(counts * sizeof(unsigned long long));
	assert(retkeys);

	counts = 0;
	for (l = strtok(b, "\n"); l; l = strtok(NULL, "\n"))
		retkeys[counts++] = strtoull(l, NULL, 10);
	free(b);

	*keys = retkeys;

	return counts;
}

static int create_map(int map_type, int map_flags, unsigned int size)
{
	LIBBPF_OPTS(bpf_map_create_opts, opts,
		.map_flags = map_flags,
	);
	int map_fd;

	map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long),
				sizeof(unsigned long long), size, &opts);

	if (map_fd == -1)
		perror("bpf_create_map");

	return map_fd;
}

static int sched_next_online(int pid, int next_to_try)
{
	cpu_set_t cpuset;

	if (next_to_try == nr_cpus)
		return -1;

	while (next_to_try < nr_cpus) {
		CPU_ZERO(&cpuset);
		CPU_SET(next_to_try++, &cpuset);
		if (!sched_setaffinity(pid, sizeof(cpuset), &cpuset))
			break;
	}

	return next_to_try;
}

static void run_parallel(unsigned int tasks, void (*fn)(int i, void *data),
			 void *data)
{
	int next_sched_cpu = 0;
	pid_t pid[tasks];
	int i;

	for (i = 0; i < tasks; i++) {
		pid[i] = fork();
		if (pid[i] == 0) {
			next_sched_cpu = sched_next_online(0, next_sched_cpu);
			fn(i, data);
			exit(0);
		} else if (pid[i] == -1) {
			printf("couldn't spawn #%d process\n", i);
			exit(1);
		}
		/* It is mostly redundant and just allow the parent
		 * process to update next_shced_cpu for the next child
		 * process
		 */
		next_sched_cpu = sched_next_online(pid[i], next_sched_cpu);
	}
	for (i = 0; i < tasks; i++) {
		int status;

		assert(waitpid(pid[i], &status, 0) == pid[i]);
		assert(status == 0);
	}
}

static void do_test_lru_dist(int task, void *data)
{
	unsigned int nr_misses = 0;
	struct pfect_lru pfect_lru;
	unsigned long long key, value = 1234;
	unsigned int i;

	unsigned int lru_map_fd = ((unsigned int *)data)[0];
	unsigned int lru_size = ((unsigned int *)data)[1];
	unsigned long long key_offset = task * dist_key_counts;

	pfect_lru_init(&pfect_lru, lru_size, dist_key_counts);

	for (i = 0; i < dist_key_counts; i++) {
		key = dist_keys[i] + key_offset;

		pfect_lru_lookup_or_insert(&pfect_lru, key);

		if (!bpf_map_lookup_elem(lru_map_fd, &key, &value))
			continue;

		if (bpf_map_update_elem(lru_map_fd, &key, &value, BPF_NOEXIST)) {
			printf("bpf_map_update_elem(lru_map_fd, %llu): errno:%d\n",
			       key, errno);
			assert(0);
		}

		nr_misses++;
	}

	printf("    task:%d BPF LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
	       task, pfect_lru.nr_unique, dist_key_counts, nr_misses,
	       dist_key_counts);
	printf("    task:%d Perfect LRU: nr_unique:%u(/%u) nr_misses:%u(/%u)\n",
	       task, pfect_lru.nr_unique, pfect_lru.total,
	       pfect_lru.nr_misses, pfect_lru.total);

	pfect_lru_destroy(&pfect_lru);
	close(lru_map_fd);
}

static void test_parallel_lru_dist(int map_type, int map_flags,
				   int nr_tasks, unsigned int lru_size)
{
	int child_data[2];
	int lru_map_fd;

	printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
	       map_flags);

	if (map_flags & BPF_F_NO_COMMON_LRU)
		lru_map_fd = create_map(map_type, map_flags,
					nr_cpus * lru_size);
	else
		lru_map_fd = create_map(map_type, map_flags,
					nr_tasks * lru_size);
	assert(lru_map_fd != -1);

	child_data[0] = lru_map_fd;
	child_data[1] = lru_size;

	run_parallel(nr_tasks, do_test_lru_dist, child_data);

	close(lru_map_fd);
}

static void test_lru_loss0(int map_type, int map_flags)
{
	unsigned long long key, value[nr_cpus];
	unsigned int old_unused_losses = 0;
	unsigned int new_unused_losses = 0;
	unsigned int used_losses = 0;
	int map_fd;

	printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
	       map_flags);

	assert(sched_next_online(0, 0) != -1);

	if (map_flags & BPF_F_NO_COMMON_LRU)
		map_fd = create_map(map_type, map_flags, 900 * nr_cpus);
	else
		map_fd = create_map(map_type, map_flags, 900);

	assert(map_fd != -1);

	value[0] = 1234;

	for (key = 1; key <= 1000; key++) {
		int start_key, end_key;

		assert(bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST) == 0);

		start_key = 101;
		end_key = min(key, 900);

		while (start_key <= end_key) {
			bpf_map_lookup_elem(map_fd, &start_key, value);
			start_key++;
		}
	}

	for (key = 1; key <= 1000; key++) {
		if (bpf_map_lookup_elem(map_fd, &key, value)) {
			if (key <= 100)
				old_unused_losses++;
			else if (key <= 900)
				used_losses++;
			else
				new_unused_losses++;
		}
	}

	close(map_fd);

	printf("older-elem-losses:%d(/100) active-elem-losses:%d(/800) "
	       "newer-elem-losses:%d(/100)\n",
	       old_unused_losses, used_losses, new_unused_losses);
}

static void test_lru_loss1(int map_type, int map_flags)
{
	unsigned long long key, value[nr_cpus];
	int map_fd;
	unsigned int nr_losses = 0;

	printf("%s (map_type:%d map_flags:0x%X): ", __func__, map_type,
	       map_flags);

	assert(sched_next_online(0, 0) != -1);

	if (map_flags & BPF_F_NO_COMMON_LRU)
		map_fd = create_map(map_type, map_flags, 1000 * nr_cpus);
	else
		map_fd = create_map(map_type, map_flags, 1000);

	assert(map_fd != -1);

	value[0] = 1234;

	for (key = 1; key <= 1000; key++)
		assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));

	for (key = 1; key <= 1000; key++) {
		if (bpf_map_lookup_elem(map_fd, &key, value))
			nr_losses++;
	}

	close(map_fd);

	printf("nr_losses:%d(/1000)\n", nr_losses);
}

static void do_test_parallel_lru_loss(int task, void *data)
{
	const unsigned int nr_stable_elems = 1000;
	const unsigned int nr_repeats = 100000;

	int map_fd = *(int *)data;
	unsigned long long stable_base;
	unsigned long long key, value[nr_cpus];
	unsigned long long next_ins_key;
	unsigned int nr_losses = 0;
	unsigned int i;

	stable_base = task * nr_repeats * 2 + 1;
	next_ins_key = stable_base;
	value[0] = 1234;
	for (i = 0; i < nr_stable_elems; i++) {
		assert(bpf_map_update_elem(map_fd, &next_ins_key, value,
				       BPF_NOEXIST) == 0);
		next_ins_key++;
	}

	for (i = 0; i < nr_repeats; i++) {
		int rn;

		rn = rand();

		if (rn % 10) {
			key = rn % nr_stable_elems + stable_base;
			bpf_map_lookup_elem(map_fd, &key, value);
		} else {
			bpf_map_update_elem(map_fd, &next_ins_key, value,
					BPF_NOEXIST);
			next_ins_key++;
		}
	}

	key = stable_base;
	for (i = 0; i < nr_stable_elems; i++) {
		if (bpf_map_lookup_elem(map_fd, &key, value))
			nr_losses++;
		key++;
	}

	printf("    task:%d nr_losses:%u\n", task, nr_losses);
}

static void test_parallel_lru_loss(int map_type, int map_flags, int nr_tasks)
{
	int map_fd;

	printf("%s (map_type:%d map_flags:0x%X):\n", __func__, map_type,
	       map_flags);

	/* Give 20% more than the active working set */
	if (map_flags & BPF_F_NO_COMMON_LRU)
		map_fd = create_map(map_type, map_flags,
				    nr_cpus * (1000 + 200));
	else
		map_fd = create_map(map_type, map_flags,
				    nr_tasks * (1000 + 200));

	assert(map_fd != -1);

	run_parallel(nr_tasks, do_test_parallel_lru_loss, &map_fd);

	close(map_fd);
}

int main(int argc, char **argv)
{
	int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
	const char *dist_file;
	int nr_tasks = 1;
	int lru_size;
	int f;

	if (argc < 4) {
		printf("Usage: %s <dist-file> <lru-size> <nr-tasks>\n",
		       argv[0]);
		return -1;
	}

	dist_file = argv[1];
	lru_size = atoi(argv[2]);
	nr_tasks = atoi(argv[3]);

	setbuf(stdout, NULL);

	srand(time(NULL));

	nr_cpus = bpf_num_possible_cpus();
	assert(nr_cpus != -1);
	printf("nr_cpus:%d\n\n", nr_cpus);

	nr_tasks = min(nr_tasks, nr_cpus);

	dist_key_counts = read_keys(dist_file, &dist_keys);
	if (!dist_key_counts) {
		printf("%s has no key\n", dist_file);
		return -1;
	}

	for (f = 0; f < sizeof(map_flags) / sizeof(*map_flags); f++) {
		test_lru_loss0(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
		test_lru_loss1(BPF_MAP_TYPE_LRU_HASH, map_flags[f]);
		test_parallel_lru_loss(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
				       nr_tasks);
		test_parallel_lru_dist(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
				       nr_tasks, lru_size);
		printf("\n");
	}

	free(dist_keys);

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