1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright (c) 2016 Facebook
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>
19
20#include <bpf/bpf.h>
21#include "bpf_util.h"
22
23#define min(a, b) ((a) < (b) ? (a) : (b))
24#ifndef offsetof
25# define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
26#endif
27#define container_of(ptr, type, member) ({			\
28	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
29	(type *)( (char *)__mptr - offsetof(type,member) );})
30
31static int nr_cpus;
32static unsigned long long *dist_keys;
33static unsigned int dist_key_counts;
34
35struct list_head {
36	struct list_head *next, *prev;
37};
38
39static inline void INIT_LIST_HEAD(struct list_head *list)
40{
41	list->next = list;
42	list->prev = list;
43}
44
45static inline int list_empty(const struct list_head *head)
46{
47	return head->next == head;
48}
49
50static 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
60static inline void list_add(struct list_head *new, struct list_head *head)
61{
62	__list_add(new, head, head->next);
63}
64
65static inline void __list_del(struct list_head *prev, struct list_head *next)
66{
67	next->prev = prev;
68	prev->next = next;
69}
70
71static inline void __list_del_entry(struct list_head *entry)
72{
73	__list_del(entry->prev, entry->next);
74}
75
76static 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
88struct pfect_lru_node {
89	struct list_head list;
90	unsigned long long key;
91};
92
93struct 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
104static void pfect_lru_init(struct pfect_lru *lru, unsigned int lru_size,
105			   unsigned int nr_possible_elems)
106{
107	lru->map_fd = bpf_map_create(BPF_MAP_TYPE_HASH, NULL,
108				     sizeof(unsigned long long),
109				     sizeof(struct pfect_lru_node *),
110				     nr_possible_elems, NULL);
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
122static void pfect_lru_destroy(struct pfect_lru *lru)
123{
124	close(lru->map_fd);
125	free(lru->free_nodes);
126}
127
128static 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++;
135	if (!bpf_map_lookup_elem(lru->map_fd, &key, &node)) {
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);
152		bpf_map_update_elem(lru->map_fd, &node->key, &null_node, BPF_EXIST);
153	}
154
155	node->key = key;
156	list_move(&node->list, &lru->list);
157
158	lru->nr_misses++;
159	if (seen) {
160		assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_EXIST));
161	} else {
162		lru->nr_unique++;
163		assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_NOEXIST));
164	}
165
166	return seen;
167}
168
169static 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
207static int create_map(int map_type, int map_flags, unsigned int size)
208{
209	LIBBPF_OPTS(bpf_map_create_opts, opts,
210		.map_flags = map_flags,
211	);
212	int map_fd;
213
214	map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long),
215				sizeof(unsigned long long), size, &opts);
216
217	if (map_fd == -1)
218		perror("bpf_create_map");
219
220	return map_fd;
221}
222
223static 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
240static 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
271static 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
289		if (!bpf_map_lookup_elem(lru_map_fd, &key, &value))
290			continue;
291
292		if (bpf_map_update_elem(lru_map_fd, &key, &value, BPF_NOEXIST)) {
293			printf("bpf_map_update_elem(lru_map_fd, %llu): errno:%d\n",
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
312static 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
337static 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
362		assert(bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST) == 0);
363
364		start_key = 101;
365		end_key = min(key, 900);
366
367		while (start_key <= end_key) {
368			bpf_map_lookup_elem(map_fd, &start_key, value);
369			start_key++;
370		}
371	}
372
373	for (key = 1; key <= 1000; key++) {
374		if (bpf_map_lookup_elem(map_fd, &key, value)) {
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
391static 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++)
412		assert(!bpf_map_update_elem(map_fd, &key, value, BPF_NOEXIST));
413
414	for (key = 1; key <= 1000; key++) {
415		if (bpf_map_lookup_elem(map_fd, &key, value))
416			nr_losses++;
417	}
418
419	close(map_fd);
420
421	printf("nr_losses:%d(/1000)\n", nr_losses);
422}
423
424static 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++) {
440		assert(bpf_map_update_elem(map_fd, &next_ins_key, value,
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;
452			bpf_map_lookup_elem(map_fd, &key, value);
453		} else {
454			bpf_map_update_elem(map_fd, &next_ins_key, value,
455					BPF_NOEXIST);
456			next_ins_key++;
457		}
458	}
459
460	key = stable_base;
461	for (i = 0; i < nr_stable_elems; i++) {
462		if (bpf_map_lookup_elem(map_fd, &key, value))
463			nr_losses++;
464		key++;
465	}
466
467	printf("    task:%d nr_losses:%u\n", task, nr_losses);
468}
469
470static 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
492int main(int argc, char **argv)
493{
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
512	srand(time(NULL));
513
514	nr_cpus = bpf_num_possible_cpus();
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 < ARRAY_SIZE(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}
540