xref: /openssl/test/quic_cc_test.c (revision da1c088f)
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