1 /*
2 * Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 /* For generating debug statistics during congestion controller development. */
11 /*#define GENERATE_LOG*/
12
13 #include "testutil.h"
14 #include <openssl/ssl.h>
15 #include "internal/quic_cc.h"
16 #include "internal/priority_queue.h"
17
18 /*
19 * Time Simulation
20 * ===============
21 */
22 static OSSL_TIME fake_time = {0};
23
24 #define TIME_BASE (ossl_ticks2time(5 * OSSL_TIME_SECOND))
25
fake_now(void * arg)26 static OSSL_TIME fake_now(void *arg)
27 {
28 return fake_time;
29 }
30
step_time(uint32_t ms)31 static void step_time(uint32_t ms)
32 {
33 fake_time = ossl_time_add(fake_time, ossl_ms2time(ms));
34 }
35
36 /*
37 * Network Simulation
38 * ==================
39 *
40 * This is a simple 'network simulator' which emulates a network with a certain
41 * bandwidth and latency. Sending a packet into the network causes it to consume
42 * some capacity of the network until the packet exits the network. Note that
43 * the capacity is not known to the congestion controller as the entire point of
44 * a congestion controller is to correctly estimate this capacity and this is
45 * what we are testing. The network simulator does take care of informing the
46 * congestion controller of ack/loss events automatically but the caller is
47 * responsible for querying the congestion controller and choosing the size of
48 * simulated transmitted packets.
49 */
50 typedef struct net_pkt_st {
51 /*
52 * The time at which the packet was sent.
53 */
54 OSSL_TIME tx_time;
55
56 /*
57 * The time at which the simulated packet arrives at the RX side (success)
58 * or is dropped (!success).
59 */
60 OSSL_TIME arrive_time;
61
62 /*
63 * The time at which the transmitting side makes a determination of
64 * acknowledgement (if success) or loss (if !success).
65 */
66 OSSL_TIME determination_time;
67
68 /*
69 * Current earliest time there is something to be done for this packet.
70 * min(arrive_time, determination_time).
71 */
72 OSSL_TIME next_time;
73
74 /* 1 if the packet will be successfully delivered, 0 if it is to be lost. */
75 int success;
76
77 /* 1 if we have already processed packet arrival. */
78 int arrived;
79
80 /* Size of simulated packet in bytes. */
81 size_t size;
82
83 /* pqueue internal index. */
84 size_t idx;
85 } NET_PKT;
86
87 DEFINE_PRIORITY_QUEUE_OF(NET_PKT);
88
net_pkt_cmp(const NET_PKT * a,const NET_PKT * b)89 static int net_pkt_cmp(const NET_PKT *a, const NET_PKT *b)
90 {
91 return ossl_time_compare(a->next_time, b->next_time);
92 }
93
94 struct net_sim {
95 const OSSL_CC_METHOD *ccm;
96 OSSL_CC_DATA *cc;
97
98 uint64_t capacity; /* bytes/s */
99 uint64_t latency; /* ms */
100
101 uint64_t spare_capacity;
102 PRIORITY_QUEUE_OF(NET_PKT) *pkts;
103
104 uint64_t total_acked, total_lost; /* bytes */
105 };
106
net_sim_init(struct net_sim * s,const OSSL_CC_METHOD * ccm,OSSL_CC_DATA * cc,uint64_t capacity,uint64_t latency)107 static int net_sim_init(struct net_sim *s,
108 const OSSL_CC_METHOD *ccm, OSSL_CC_DATA *cc,
109 uint64_t capacity, uint64_t latency)
110 {
111 s->ccm = ccm;
112 s->cc = cc;
113
114 s->capacity = capacity;
115 s->latency = latency;
116
117 s->spare_capacity = capacity;
118
119 s->total_acked = 0;
120 s->total_lost = 0;
121
122 if (!TEST_ptr(s->pkts = ossl_pqueue_NET_PKT_new(net_pkt_cmp)))
123 return 0;
124
125 return 1;
126 }
127
do_free(NET_PKT * pkt)128 static void do_free(NET_PKT *pkt)
129 {
130 OPENSSL_free(pkt);
131 }
132
net_sim_cleanup(struct net_sim * s)133 static void net_sim_cleanup(struct net_sim *s)
134 {
135 ossl_pqueue_NET_PKT_pop_free(s->pkts, do_free);
136 }
137
138 static int net_sim_process(struct net_sim *s, size_t skip_forward);
139
net_sim_send(struct net_sim * s,size_t sz)140 static int net_sim_send(struct net_sim *s, size_t sz)
141 {
142 NET_PKT *pkt = OPENSSL_zalloc(sizeof(*pkt));
143 int success;
144
145 if (!TEST_ptr(pkt))
146 return 0;
147
148 /*
149 * Ensure we have processed any events which have come due as these might
150 * increase our spare capacity.
151 */
152 if (!TEST_true(net_sim_process(s, 0)))
153 goto err;
154
155 /* Do we have room for the packet in the network? */
156 success = (sz <= s->spare_capacity);
157
158 pkt->tx_time = fake_time;
159 pkt->success = success;
160 if (success) {
161 /* This packet will arrive successfully after |latency| time. */
162 pkt->arrive_time = ossl_time_add(pkt->tx_time,
163 ossl_ms2time(s->latency));
164 /* Assume all received packets are acknowledged immediately. */
165 pkt->determination_time = ossl_time_add(pkt->arrive_time,
166 ossl_ms2time(s->latency));
167 pkt->next_time = pkt->arrive_time;
168 s->spare_capacity -= sz;
169 } else {
170 /*
171 * In our network model, assume all packets are dropped due to a
172 * bottleneck at the peer's NIC RX queue; thus dropping occurs after
173 * |latency|.
174 */
175 pkt->arrive_time = ossl_time_add(pkt->tx_time,
176 ossl_ms2time(s->latency));
177 /*
178 * It will take longer to detect loss than to detect acknowledgement.
179 */
180 pkt->determination_time = ossl_time_add(pkt->tx_time,
181 ossl_ms2time(3 * s->latency));
182 pkt->next_time = pkt->determination_time;
183 }
184
185 pkt->size = sz;
186
187 if (!TEST_true(s->ccm->on_data_sent(s->cc, sz)))
188 goto err;
189
190 if (!TEST_true(ossl_pqueue_NET_PKT_push(s->pkts, pkt, &pkt->idx)))
191 goto err;
192
193 return 1;
194
195 err:
196 OPENSSL_free(pkt);
197 return 0;
198 }
199
net_sim_process_one(struct net_sim * s,int skip_forward)200 static int net_sim_process_one(struct net_sim *s, int skip_forward)
201 {
202 NET_PKT *pkt = ossl_pqueue_NET_PKT_peek(s->pkts);
203
204 if (pkt == NULL)
205 return 3;
206
207 /* Jump forward to the next significant point in time. */
208 if (skip_forward && ossl_time_compare(pkt->next_time, fake_time) > 0)
209 fake_time = pkt->next_time;
210
211 if (pkt->success && !pkt->arrived
212 && ossl_time_compare(fake_time, pkt->arrive_time) >= 0) {
213 /* Packet arrives */
214 s->spare_capacity += pkt->size;
215 pkt->arrived = 1;
216
217 ossl_pqueue_NET_PKT_pop(s->pkts);
218 pkt->next_time = pkt->determination_time;
219 if (!ossl_pqueue_NET_PKT_push(s->pkts, pkt, &pkt->idx))
220 return 0;
221
222 return 1;
223 }
224
225 if (ossl_time_compare(fake_time, pkt->determination_time) < 0)
226 return 2;
227
228 if (!TEST_true(!pkt->success || pkt->arrived))
229 return 0;
230
231 if (!pkt->success) {
232 OSSL_CC_LOSS_INFO loss_info = {0};
233
234 loss_info.tx_time = pkt->tx_time;
235 loss_info.tx_size = pkt->size;
236
237 if (!TEST_true(s->ccm->on_data_lost(s->cc, &loss_info)))
238 return 0;
239
240 if (!TEST_true(s->ccm->on_data_lost_finished(s->cc, 0)))
241 return 0;
242
243 s->total_lost += pkt->size;
244 ossl_pqueue_NET_PKT_pop(s->pkts);
245 OPENSSL_free(pkt);
246 } else {
247 OSSL_CC_ACK_INFO ack_info = {0};
248
249 ack_info.tx_time = pkt->tx_time;
250 ack_info.tx_size = pkt->size;
251
252 if (!TEST_true(s->ccm->on_data_acked(s->cc, &ack_info)))
253 return 0;
254
255 s->total_acked += pkt->size;
256 ossl_pqueue_NET_PKT_pop(s->pkts);
257 OPENSSL_free(pkt);
258 }
259
260 return 1;
261 }
262
net_sim_process(struct net_sim * s,size_t skip_forward)263 static int net_sim_process(struct net_sim *s, size_t skip_forward)
264 {
265 int rc;
266
267 while ((rc = net_sim_process_one(s, skip_forward > 0 ? 1 : 0)) == 1)
268 if (skip_forward > 0)
269 --skip_forward;
270
271 return rc;
272 }
273
274 /*
275 * State Dumping Utilities
276 * =======================
277 *
278 * Utilities for outputting CC state information.
279 */
280 #ifdef GENERATE_LOG
281 static FILE *logfile;
282 #endif
283
dump_state(const OSSL_CC_METHOD * ccm,OSSL_CC_DATA * cc,struct net_sim * s)284 static int dump_state(const OSSL_CC_METHOD *ccm, OSSL_CC_DATA *cc,
285 struct net_sim *s)
286 {
287 #ifdef GENERATE_LOG
288 uint64_t cwnd_size, cur_bytes, state;
289
290 if (logfile == NULL)
291 return 1;
292
293 if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_CWND_SIZE,
294 &cwnd_size)))
295 return 0;
296
297 if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
298 &cur_bytes)))
299 return 0;
300
301 if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_STATE,
302 &state)))
303 return 0;
304
305 fprintf(logfile, "%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,\"%c\"\n",
306 ossl_time2ms(fake_time),
307 ccm->get_tx_allowance(cc),
308 cwnd_size,
309 cur_bytes,
310 s->total_acked,
311 s->total_lost,
312 s->capacity,
313 s->spare_capacity,
314 (char)state);
315 #endif
316
317 return 1;
318 }
319
320 /*
321 * Simulation Test
322 * ===============
323 *
324 * Simulator-based unit test in which we simulate a network with a certain
325 * capacity. The average estimated channel capacity should not be too far from
326 * the actual channel capacity.
327 */
test_simulate(void)328 static int test_simulate(void)
329 {
330 int testresult = 0;
331 int rc;
332 int have_sim = 0;
333 const OSSL_CC_METHOD *ccm = &ossl_cc_newreno_method;
334 OSSL_CC_DATA *cc = NULL;
335 size_t mdpl = 1472;
336 uint64_t total_sent = 0, total_to_send, allowance;
337 uint64_t actual_capacity = 16000; /* B/s - 128kb/s */
338 uint64_t cwnd_sample_sum = 0, cwnd_sample_count = 0;
339 uint64_t diag_cur_bytes_in_flight = UINT64_MAX;
340 uint64_t diag_cur_cwnd_size = UINT64_MAX;
341 struct net_sim sim;
342 OSSL_PARAM params[3], *p = params;
343
344 fake_time = TIME_BASE;
345
346 if (!TEST_ptr(cc = ccm->new(fake_now, NULL)))
347 goto err;
348
349 if (!TEST_true(net_sim_init(&sim, ccm, cc, actual_capacity, 100)))
350 goto err;
351
352 have_sim = 1;
353
354 *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
355 &mdpl);
356 *p++ = OSSL_PARAM_construct_end();
357
358 if (!TEST_true(ccm->set_input_params(cc, params)))
359 goto err;
360
361 p = params;
362 *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
363 &diag_cur_bytes_in_flight);
364 *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_CWND_SIZE,
365 &diag_cur_cwnd_size);
366 *p++ = OSSL_PARAM_construct_end();
367
368 if (!TEST_true(ccm->bind_diagnostics(cc, params)))
369 goto err;
370
371 ccm->reset(cc);
372
373 if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), mdpl))
374 goto err;
375
376 /*
377 * Start generating traffic. Stop when we've sent 30 MiB.
378 */
379 total_to_send = 30 * 1024 * 1024;
380
381 while (total_sent < total_to_send) {
382 /*
383 * Assume we are bottlenecked by the network (which is the interesting
384 * case for testing a congestion controller) and always fill our entire
385 * TX allowance as and when it becomes available.
386 */
387 for (;;) {
388 uint64_t sz;
389
390 dump_state(ccm, cc, &sim);
391
392 allowance = ccm->get_tx_allowance(cc);
393 sz = allowance > mdpl ? mdpl : allowance;
394 if (sz > SIZE_MAX)
395 sz = SIZE_MAX;
396
397 /*
398 * QUIC minimum packet sizes, etc. mean that in practice we will not
399 * consume the allowance exactly, so only send above a certain size.
400 */
401 if (sz < 30)
402 break;
403
404 step_time(7);
405
406 if (!TEST_true(net_sim_send(&sim, (size_t)sz)))
407 goto err;
408
409 total_sent += sz;
410 }
411
412 /* Skip to next event. */
413 rc = net_sim_process(&sim, 1);
414 if (!TEST_int_gt(rc, 0))
415 goto err;
416
417 /*
418 * If we are out of any events to handle at all we definitely should
419 * have at least one MDPL's worth of allowance as nothing is in flight.
420 */
421 if (rc == 3) {
422 if (!TEST_uint64_t_eq(diag_cur_bytes_in_flight, 0))
423 goto err;
424
425 if (!TEST_uint64_t_ge(ccm->get_tx_allowance(cc), mdpl))
426 goto err;
427 }
428
429 /* Update our average of the estimated channel capacity. */
430 {
431 uint64_t v = 1;
432
433 if (!TEST_uint64_t_ne(diag_cur_bytes_in_flight, UINT64_MAX)
434 || !TEST_uint64_t_ne(diag_cur_cwnd_size, UINT64_MAX))
435 goto err;
436
437 cwnd_sample_sum += v;
438 ++cwnd_sample_count;
439 }
440 }
441
442 /*
443 * Ensure estimated channel capacity is not too far off from actual channel
444 * capacity.
445 */
446 {
447 uint64_t estimated_capacity = cwnd_sample_sum / cwnd_sample_count;
448
449 double error = ((double)estimated_capacity / (double)actual_capacity) - 1.0;
450
451 TEST_info("est = %6llu kB/s, act=%6llu kB/s (error=%.02f%%)\n",
452 (unsigned long long)estimated_capacity,
453 (unsigned long long)actual_capacity,
454 error * 100.0);
455
456 /* Max 5% error */
457 if (!TEST_double_le(error, 0.05))
458 goto err;
459 }
460
461 testresult = 1;
462 err:
463 if (have_sim)
464 net_sim_cleanup(&sim);
465
466 if (cc != NULL)
467 ccm->free(cc);
468
469 #ifdef GENERATE_LOG
470 if (logfile != NULL)
471 fflush(logfile);
472 #endif
473
474 return testresult;
475 }
476
477 /*
478 * Sanity Test
479 * ===========
480 *
481 * Basic test of the congestion control APIs.
482 */
test_sanity(void)483 static int test_sanity(void)
484 {
485 int testresult = 0;
486 OSSL_CC_DATA *cc = NULL;
487 const OSSL_CC_METHOD *ccm = &ossl_cc_newreno_method;
488 OSSL_CC_LOSS_INFO loss_info = {0};
489 OSSL_CC_ACK_INFO ack_info = {0};
490 uint64_t allowance, allowance2;
491 OSSL_PARAM params[3], *p = params;
492 size_t mdpl = 1472, diag_mdpl = SIZE_MAX;
493 uint64_t diag_cur_bytes_in_flight = UINT64_MAX;
494
495 fake_time = TIME_BASE;
496
497 if (!TEST_ptr(cc = ccm->new(fake_now, NULL)))
498 goto err;
499
500 /* Test configuration of options. */
501 *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
502 &mdpl);
503 *p++ = OSSL_PARAM_construct_end();
504
505 if (!TEST_true(ccm->set_input_params(cc, params)))
506 goto err;
507
508 ccm->reset(cc);
509
510 p = params;
511 *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
512 &diag_mdpl);
513 *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
514 &diag_cur_bytes_in_flight);
515 *p++ = OSSL_PARAM_construct_end();
516
517 if (!TEST_true(ccm->bind_diagnostics(cc, params))
518 || !TEST_size_t_eq(diag_mdpl, 1472))
519 goto err;
520
521 if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), 1472))
522 goto err;
523
524 /* There is TX allowance so wakeup should be immediate */
525 if (!TEST_true(ossl_time_is_zero(ccm->get_wakeup_deadline(cc))))
526 goto err;
527
528 /* No bytes should currently be in flight. */
529 if (!TEST_uint64_t_eq(diag_cur_bytes_in_flight, 0))
530 goto err;
531
532 /* Tell the CC we have sent some data. */
533 if (!TEST_true(ccm->on_data_sent(cc, 1200)))
534 goto err;
535
536 /* Allowance should have decreased. */
537 if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance - 1200))
538 goto err;
539
540 /* Acknowledge the data. */
541 ack_info.tx_time = fake_time;
542 ack_info.tx_size = 1200;
543 step_time(100);
544 if (!TEST_true(ccm->on_data_acked(cc, &ack_info)))
545 goto err;
546
547 /* Allowance should have returned. */
548 if (!TEST_uint64_t_ge(allowance2 = ccm->get_tx_allowance(cc), allowance))
549 goto err;
550
551 /* Test invalidation. */
552 if (!TEST_true(ccm->on_data_sent(cc, 1200)))
553 goto err;
554
555 /* Allowance should have decreased. */
556 if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance - 1200))
557 goto err;
558
559 if (!TEST_true(ccm->on_data_invalidated(cc, 1200)))
560 goto err;
561
562 /* Allowance should have returned. */
563 if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance2))
564 goto err;
565
566 /* Test loss. */
567 if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), 1200 + 1300))
568 goto err;
569
570 if (!TEST_true(ccm->on_data_sent(cc, 1200)))
571 goto err;
572
573 if (!TEST_true(ccm->on_data_sent(cc, 1300)))
574 goto err;
575
576 if (!TEST_uint64_t_eq(allowance2 = ccm->get_tx_allowance(cc),
577 allowance - 1200 - 1300))
578 goto err;
579
580 loss_info.tx_time = fake_time;
581 loss_info.tx_size = 1200;
582 step_time(100);
583
584 if (!TEST_true(ccm->on_data_lost(cc, &loss_info)))
585 goto err;
586
587 loss_info.tx_size = 1300;
588 if (!TEST_true(ccm->on_data_lost(cc, &loss_info)))
589 goto err;
590
591 if (!TEST_true(ccm->on_data_lost_finished(cc, 0)))
592 goto err;
593
594 /* Allowance should have changed due to the lost calls */
595 if (!TEST_uint64_t_ne(ccm->get_tx_allowance(cc), allowance2))
596 goto err;
597
598 /* But it should not be as high as the original value */
599 if (!TEST_uint64_t_lt(ccm->get_tx_allowance(cc), allowance))
600 goto err;
601
602 testresult = 1;
603
604 err:
605 if (cc != NULL)
606 ccm->free(cc);
607
608 return testresult;
609 }
610
setup_tests(void)611 int setup_tests(void)
612 {
613
614 #ifdef GENERATE_LOG
615 logfile = fopen("quic_cc_stats.csv", "w");
616 fprintf(logfile,
617 "\"Time\","
618 "\"TX Allowance\","
619 "\"CWND Size\","
620 "\"Bytes in Flight\","
621 "\"Total Acked\",\"Total Lost\","
622 "\"Capacity\",\"Spare Capacity\","
623 "\"State\"\n");
624 #endif
625
626 ADD_TEST(test_simulate);
627 ADD_TEST(test_sanity);
628 return 1;
629 }
630
