bench-lookups.c

  1// SPDX-License-Identifier: GPL-2.0
  2/* Author: Dmitry Safonov <dima@arista.com> */
  3#include <arpa/inet.h>
  4#include <inttypes.h>
  5#include <math.h>
  6#include <stdlib.h>
  7#include <stdio.h>
  8#include <time.h>
  9
 10#include "../../../../include/linux/bits.h"
 11#include "../../../../include/linux/kernel.h"
 12#include "aolib.h"
 13
 14#define BENCH_NR_ITERS	100 /* number of times to run gathering statistics */
 15
 16static void gen_test_ips(union tcp_addr *ips, size_t ips_nr, bool use_rand)
 17{
 18	union tcp_addr net = {};
 19	size_t i, j;
 20
 21	if (inet_pton(TEST_FAMILY, TEST_NETWORK, &net) != 1)
 22		test_error("Can't convert ip address %s", TEST_NETWORK);
 23
 24	if (!use_rand) {
 25		for (i = 0; i < ips_nr; i++)
 26			ips[i] = gen_tcp_addr(net, 2 * i + 1);
 27		return;
 28	}
 29	for (i = 0; i < ips_nr; i++) {
 30		size_t r = (size_t)random() | 0x1;
 31
 32		ips[i] = gen_tcp_addr(net, r);
 33
 34		for (j = i - 1; j > 0 && i > 0; j--) {
 35			if (!memcmp(&ips[i], &ips[j], sizeof(union tcp_addr))) {
 36				i--; /* collision */
 37				break;
 38			}
 39		}
 40	}
 41}
 42
 43static void test_add_routes(union tcp_addr *ips, size_t ips_nr)
 44{
 45	size_t i;
 46
 47	for (i = 0; i < ips_nr; i++) {
 48		union tcp_addr *p = (union tcp_addr *)&ips[i];
 49		int err;
 50
 51		err = ip_route_add(veth_name, TEST_FAMILY, this_ip_addr, *p);
 52		if (err && err != -EEXIST)
 53			test_error("Failed to add route");
 54	}
 55}
 56
 57static void server_apply_keys(int lsk, union tcp_addr *ips, size_t ips_nr)
 58{
 59	size_t i;
 60
 61	for (i = 0; i < ips_nr; i++) {
 62		union tcp_addr *p = (union tcp_addr *)&ips[i];
 63
 64		if (test_add_key(lsk, DEFAULT_TEST_PASSWORD, *p, -1, 100, 100))
 65			test_error("setsockopt(TCP_AO)");
 66	}
 67}
 68
 69static const size_t nr_keys[] = { 512, 1024, 2048, 4096, 8192 };
 70static union tcp_addr *test_ips;
 71
 72struct bench_stats {
 73	uint64_t min;
 74	uint64_t max;
 75	uint64_t nr;
 76	double mean;
 77	double s2;
 78};
 79
 80static struct bench_tests {
 81	struct bench_stats delete_last_key;
 82	struct bench_stats add_key;
 83	struct bench_stats delete_rand_key;
 84	struct bench_stats connect_last_key;
 85	struct bench_stats connect_rand_key;
 86	struct bench_stats delete_async;
 87} bench_results[ARRAY_SIZE(nr_keys)];
 88
 89#define NSEC_PER_SEC 1000000000ULL
 90
 91static void measure_call(struct bench_stats *st,
 92			 void (*f)(int, void *), int sk, void *arg)
 93{
 94	struct timespec start = {}, end = {};
 95	double delta;
 96	uint64_t nsec;
 97
 98	if (clock_gettime(CLOCK_MONOTONIC, &start))
 99		test_error("clock_gettime()");
100
101	f(sk, arg);
102
103	if (clock_gettime(CLOCK_MONOTONIC, &end))
104		test_error("clock_gettime()");
105
106	nsec = (end.tv_sec - start.tv_sec) * NSEC_PER_SEC;
107	if (end.tv_nsec >= start.tv_nsec)
108		nsec += end.tv_nsec - start.tv_nsec;
109	else
110		nsec -= start.tv_nsec - end.tv_nsec;
111
112	if (st->nr == 0) {
113		st->min = st->max = nsec;
114	} else {
115		if (st->min > nsec)
116			st->min = nsec;
117		if (st->max < nsec)
118			st->max = nsec;
119	}
120
121	/* Welford-Knuth algorithm */
122	st->nr++;
123	delta = (double)nsec - st->mean;
124	st->mean += delta / st->nr;
125	st->s2 += delta * ((double)nsec - st->mean);
126}
127
128static void delete_mkt(int sk, void *arg)
129{
130	struct tcp_ao_del *ao = arg;
131
132	if (setsockopt(sk, IPPROTO_TCP, TCP_AO_DEL_KEY, ao, sizeof(*ao)))
133		test_error("setsockopt(TCP_AO_DEL_KEY)");
134}
135
136static void add_back_mkt(int sk, void *arg)
137{
138	union tcp_addr *p = arg;
139
140	if (test_add_key(sk, DEFAULT_TEST_PASSWORD, *p, -1, 100, 100))
141		test_error("setsockopt(TCP_AO)");
142}
143
144static void bench_delete(int lsk, struct bench_stats *add,
145			 struct bench_stats *del,
146			 union tcp_addr *ips, size_t ips_nr,
147			 bool rand_order, bool async)
148{
149	struct tcp_ao_del ao_del = {};
150	union tcp_addr *p;
151	size_t i;
152
153	ao_del.sndid = 100;
154	ao_del.rcvid = 100;
155	ao_del.del_async = !!async;
156	ao_del.prefix = DEFAULT_TEST_PREFIX;
157
158	/* Remove the first added */
159	p = (union tcp_addr *)&ips[0];
160	tcp_addr_to_sockaddr_in(&ao_del.addr, p, 0);
161
162	for (i = 0; i < BENCH_NR_ITERS; i++) {
163		measure_call(del, delete_mkt, lsk, (void *)&ao_del);
164
165		/* Restore it back */
166		measure_call(add, add_back_mkt, lsk, (void *)p);
167
168		/*
169		 * Slowest for FILO-linked-list:
170		 * on (i) iteration removing ips[i] element. When it gets
171		 * added to the list back - it becomes first to fetch, so
172		 * on (i + 1) iteration go to ips[i + 1] element.
173		 */
174		if (rand_order)
175			p = (union tcp_addr *)&ips[rand() % ips_nr];
176		else
177			p = (union tcp_addr *)&ips[i % ips_nr];
178		tcp_addr_to_sockaddr_in(&ao_del.addr, p, 0);
179	}
180}
181
182static void bench_connect_srv(int lsk, union tcp_addr *ips, size_t ips_nr)
183{
184	size_t i;
185
186	for (i = 0; i < BENCH_NR_ITERS; i++) {
187		int sk;
188
189		synchronize_threads();
190
191		if (test_wait_fd(lsk, TEST_TIMEOUT_SEC, 0))
192			test_error("test_wait_fd()");
193
194		sk = accept(lsk, NULL, NULL);
195		if (sk < 0)
196			test_error("accept()");
197
198		close(sk);
199	}
200}
201
202static void test_print_stats(const char *desc, size_t nr, struct bench_stats *bs)
203{
204	test_ok("%-20s\t%zu keys: min=%" PRIu64 "ms max=%" PRIu64 "ms mean=%gms stddev=%g",
205		desc, nr, bs->min / 1000000, bs->max / 1000000,
206		bs->mean / 1000000, sqrt((bs->mean / 1000000) / bs->nr));
207}
208
209static void *server_fn(void *arg)
210{
211	size_t i;
212
213	for (i = 0; i < ARRAY_SIZE(nr_keys); i++) {
214		struct bench_tests *bt = &bench_results[i];
215		int lsk;
216
217		test_ips = malloc(nr_keys[i] * sizeof(union tcp_addr));
218		if (!test_ips)
219			test_error("malloc()");
220
221		lsk = test_listen_socket(this_ip_addr, test_server_port + i, 1);
222
223		gen_test_ips(test_ips, nr_keys[i], false);
224		test_add_routes(test_ips, nr_keys[i]);
225		test_set_optmem(KERNEL_TCP_AO_KEY_SZ_ROUND_UP * nr_keys[i]);
226		server_apply_keys(lsk, test_ips, nr_keys[i]);
227
228		synchronize_threads();
229		bench_connect_srv(lsk, test_ips, nr_keys[i]);
230		bench_connect_srv(lsk, test_ips, nr_keys[i]);
231
232		/* The worst case for FILO-list */
233		bench_delete(lsk, &bt->add_key, &bt->delete_last_key,
234			     test_ips, nr_keys[i], false, false);
235		test_print_stats("Add a new key",
236				nr_keys[i], &bt->add_key);
237		test_print_stats("Delete: worst case",
238				nr_keys[i], &bt->delete_last_key);
239
240		bench_delete(lsk, &bt->add_key, &bt->delete_rand_key,
241			     test_ips, nr_keys[i], true, false);
242		test_print_stats("Delete: random-search",
243				nr_keys[i], &bt->delete_rand_key);
244
245		bench_delete(lsk, &bt->add_key, &bt->delete_async,
246			     test_ips, nr_keys[i], false, true);
247		test_print_stats("Delete: async", nr_keys[i], &bt->delete_async);
248
249		free(test_ips);
250		close(lsk);
251	}
252
253	return NULL;
254}
255
256static void connect_client(int sk, void *arg)
257{
258	size_t *p = arg;
259
260	if (test_connect_socket(sk, this_ip_dest, test_server_port + *p) <= 0)
261		test_error("failed to connect()");
262}
263
264static void client_addr_setup(int sk, union tcp_addr taddr)
265{
266#ifdef IPV6_TEST
267	struct sockaddr_in6 addr = {
268		.sin6_family	= AF_INET6,
269		.sin6_port	= 0,
270		.sin6_addr	= taddr.a6,
271	};
272#else
273	struct sockaddr_in addr = {
274		.sin_family	= AF_INET,
275		.sin_port	= 0,
276		.sin_addr	= taddr.a4,
277	};
278#endif
279	int ret;
280
281	ret = ip_addr_add(veth_name, TEST_FAMILY, taddr, TEST_PREFIX);
282	if (ret && ret != -EEXIST)
283		test_error("Failed to add ip address");
284	ret = ip_route_add(veth_name, TEST_FAMILY, taddr, this_ip_dest);
285	if (ret && ret != -EEXIST)
286		test_error("Failed to add route");
287
288	if (bind(sk, &addr, sizeof(addr)))
289		test_error("bind()");
290}
291
292static void bench_connect_client(size_t port_off, struct bench_tests *bt,
293		union tcp_addr *ips, size_t ips_nr, bool rand_order)
294{
295	struct bench_stats *con;
296	union tcp_addr *p;
297	size_t i;
298
299	if (rand_order)
300		con = &bt->connect_rand_key;
301	else
302		con = &bt->connect_last_key;
303
304	p = (union tcp_addr *)&ips[0];
305
306	for (i = 0; i < BENCH_NR_ITERS; i++) {
307		int sk = socket(test_family, SOCK_STREAM, IPPROTO_TCP);
308
309		if (sk < 0)
310			test_error("socket()");
311
312		client_addr_setup(sk, *p);
313		if (test_add_key(sk, DEFAULT_TEST_PASSWORD, this_ip_dest,
314				 -1, 100, 100))
315			test_error("setsockopt(TCP_AO_ADD_KEY)");
316
317		synchronize_threads();
318
319		measure_call(con, connect_client, sk, (void *)&port_off);
320
321		close(sk);
322
323		/*
324		 * Slowest for FILO-linked-list:
325		 * on (i) iteration removing ips[i] element. When it gets
326		 * added to the list back - it becomes first to fetch, so
327		 * on (i + 1) iteration go to ips[i + 1] element.
328		 */
329		if (rand_order)
330			p = (union tcp_addr *)&ips[rand() % ips_nr];
331		else
332			p = (union tcp_addr *)&ips[i % ips_nr];
333	}
334}
335
336static void *client_fn(void *arg)
337{
338	size_t i;
339
340	for (i = 0; i < ARRAY_SIZE(nr_keys); i++) {
341		struct bench_tests *bt = &bench_results[i];
342
343		synchronize_threads();
344		bench_connect_client(i, bt, test_ips, nr_keys[i], false);
345		test_print_stats("Connect: worst case",
346				nr_keys[i], &bt->connect_last_key);
347
348		bench_connect_client(i, bt, test_ips, nr_keys[i], false);
349		test_print_stats("Connect: random-search",
350				nr_keys[i], &bt->connect_last_key);
351	}
352	synchronize_threads();
353	return NULL;
354}
355
356int main(int argc, char *argv[])
357{
358	test_init(31, server_fn, client_fn);
359	return 0;
360}