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 <sys/resource.h>
17#include <fcntl.h>
18#include <stdlib.h>
19#include <time.h>
20
21#include <bpf/bpf.h>
22#include "bpf_util.h"
23
24#define min(a, b) ((a) < (b) ? (a) : (b))
25#ifndef offsetof
26# define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
27#endif
28#define container_of(ptr, type, member) ({			\
29	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
30	(type *)( (char *)__mptr - offsetof(type,member) );})
31
32static int nr_cpus;
33static unsigned long long *dist_keys;
34static unsigned int dist_key_counts;
35
36struct list_head {
37	struct list_head *next, *prev;
38};
39
40static inline void INIT_LIST_HEAD(struct list_head *list)
41{
42	list->next = list;
43	list->prev = list;
44}
45
46static inline int list_empty(const struct list_head *head)
47{
48	return head->next == head;
49}
50
51static inline void __list_add(struct list_head *new,
52			      struct list_head *prev,
53			      struct list_head *next)
54{
55	next->prev = new;
56	new->next = next;
57	new->prev = prev;
58	prev->next = new;
59}
60
61static inline void list_add(struct list_head *new, struct list_head *head)
62{
63	__list_add(new, head, head->next);
64}
65
66static inline void __list_del(struct list_head *prev, struct list_head *next)
67{
68	next->prev = prev;
69	prev->next = next;
70}
71
72static inline void __list_del_entry(struct list_head *entry)
73{
74	__list_del(entry->prev, entry->next);
75}
76
77static inline void list_move(struct list_head *list, struct list_head *head)
78{
79	__list_del_entry(list);
80	list_add(list, head);
81}
82
83#define list_entry(ptr, type, member) \
84	container_of(ptr, type, member)
85
86#define list_last_entry(ptr, type, member) \
87	list_entry((ptr)->prev, type, member)
88
89struct pfect_lru_node {
90	struct list_head list;
91	unsigned long long key;
92};
93
94struct pfect_lru {
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;
101	unsigned int total;
102	int map_fd;
103};
104
105static void pfect_lru_init(struct pfect_lru *lru, unsigned int lru_size,
106			   unsigned int nr_possible_elems)
107{
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);
113
114	lru->free_nodes = malloc(lru_size * sizeof(struct pfect_lru_node));
115	assert(lru->free_nodes);
116
117	INIT_LIST_HEAD(&lru->list);
118	lru->cur_size = 0;
119	lru->lru_size = lru_size;
120	lru->nr_unique = lru->nr_misses = lru->total = 0;
121}
122
123static void pfect_lru_destroy(struct pfect_lru *lru)
124{
125	close(lru->map_fd);
126	free(lru->free_nodes);
127}
128
129static int pfect_lru_lookup_or_insert(struct pfect_lru *lru,
130				      unsigned long long key)
131{
132	struct pfect_lru_node *node = NULL;
133	int seen = 0;
134
135	lru->total++;
136	if (!bpf_map_lookup_elem(lru->map_fd, &key, &node)) {
137		if (node) {
138			list_move(&node->list, &lru->list);
139			return 1;
140		}
141		seen = 1;
142	}
143
144	if (lru->cur_size < lru->lru_size) {
145		node =  &lru->free_nodes[lru->cur_size++];
146		INIT_LIST_HEAD(&node->list);
147	} else {
148		struct pfect_lru_node *null_node = NULL;
149
150		node = list_last_entry(&lru->list,
151				       struct pfect_lru_node,
152				       list);
153		bpf_map_update_elem(lru->map_fd, &node->key, &null_node, BPF_EXIST);
154	}
155
156	node->key = key;
157	list_move(&node->list, &lru->list);
158
159	lru->nr_misses++;
160	if (seen) {
161		assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_EXIST));
162	} else {
163		lru->nr_unique++;
164		assert(!bpf_map_update_elem(lru->map_fd, &key, &node, BPF_NOEXIST));
165	}
166
167	return seen;
168}
169
170static unsigned int read_keys(const char *dist_file,
171			      unsigned long long **keys)
172{
173	struct stat fst;
174	unsigned long long *retkeys;
175	unsigned int counts = 0;
176	int dist_fd;
177	char *b, *l;
178	int i;
179
180	dist_fd = open(dist_file, 0);
181	assert(dist_fd != -1);
182
183	assert(fstat(dist_fd, &fst) == 0);
184	b = malloc(fst.st_size);
185	assert(b);
186
187	assert(read(dist_fd, b, fst.st_size) == fst.st_size);
188	close(dist_fd);
189	for (i = 0; i < fst.st_size; i++) {
190		if (b[i] == '\n')
191			counts++;
192	}
193	counts++; /* in case the last line has no \n */
194
195	retkeys = malloc(counts * sizeof(unsigned long long));
196	assert(retkeys);
197
198	counts = 0;
199	for (l = strtok(b, "\n"); l; l = strtok(NULL, "\n"))
200		retkeys[counts++] = strtoull(l, NULL, 10);
201	free(b);
202
203	*keys = retkeys;
204
205	return counts;
206}
207
208static int create_map(int map_type, int map_flags, unsigned int size)
209{
210	LIBBPF_OPTS(bpf_map_create_opts, opts,
211		.map_flags = map_flags,
212	);
213	int map_fd;
214
215	map_fd = bpf_map_create(map_type, NULL, sizeof(unsigned long long),
216				sizeof(unsigned long long), size, &opts);
217
218	if (map_fd == -1)
219		perror("bpf_create_map");
220
221	return map_fd;
222}
223
224static 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
241static 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
272static 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
313static 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
338static 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
392static 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
425static 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
471static 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
493int main(int argc, char **argv)
494{
495	int map_flags[] = {0, BPF_F_NO_COMMON_LRU};
496	const char *dist_file;
497	int nr_tasks = 1;
498	int lru_size;
499	int f;
500
501	if (argc < 4) {
502		printf("Usage: %s <dist-file> <lru-size> <nr-tasks>\n",
503		       argv[0]);
504		return -1;
505	}
506
507	dist_file = argv[1];
508	lru_size = atoi(argv[2]);
509	nr_tasks = atoi(argv[3]);
510
511	setbuf(stdout, NULL);
512
513	srand(time(NULL));
514
515	nr_cpus = bpf_num_possible_cpus();
516	assert(nr_cpus != -1);
517	printf("nr_cpus:%d\n\n", nr_cpus);
518
519	nr_tasks = min(nr_tasks, nr_cpus);
520
521	dist_key_counts = read_keys(dist_file, &dist_keys);
522	if (!dist_key_counts) {
523		printf("%s has no key\n", dist_file);
524		return -1;
525	}
526
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],
531				       nr_tasks);
532		test_parallel_lru_dist(BPF_MAP_TYPE_LRU_HASH, map_flags[f],
533				       nr_tasks, lru_size);
534		printf("\n");
535	}
536
537	free(dist_keys);
538
539	return 0;
540}
541