1 /*
2  * ngtcp2
3  *
4  * Copyright (c) 2018 ngtcp2 contributors
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining
7  * a copy of this software and associated documentation files (the
8  * "Software"), to deal in the Software without restriction, including
9  * without limitation the rights to use, copy, modify, merge, publish,
10  * distribute, sublicense, and/or sell copies of the Software, and to
11  * permit persons to whom the Software is furnished to do so, subject to
12  * the following conditions:
13  *
14  * The above copyright notice and this permission notice shall be
15  * included in all copies or substantial portions of the Software.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24  */
25 #include "ngtcp2_cc.h"
26 
27 #include <assert.h>
28 
29 #if defined(_MSC_VER)
30 #  include <intrin.h>
31 #endif
32 
33 #include "ngtcp2_log.h"
34 #include "ngtcp2_macro.h"
35 #include "ngtcp2_mem.h"
36 #include "ngtcp2_rcvry.h"
37 
ngtcp2_cc_compute_initcwnd(size_t max_udp_payload_size)38 uint64_t ngtcp2_cc_compute_initcwnd(size_t max_udp_payload_size) {
39   uint64_t n = 2 * max_udp_payload_size;
40   n = ngtcp2_max(n, 14720);
41   return ngtcp2_min(10 * max_udp_payload_size, n);
42 }
43 
ngtcp2_cc_pkt_init(ngtcp2_cc_pkt * pkt,int64_t pkt_num,size_t pktlen,ngtcp2_pktns_id pktns_id,ngtcp2_tstamp sent_ts)44 ngtcp2_cc_pkt *ngtcp2_cc_pkt_init(ngtcp2_cc_pkt *pkt, int64_t pkt_num,
45                                   size_t pktlen, ngtcp2_pktns_id pktns_id,
46                                   ngtcp2_tstamp sent_ts) {
47   pkt->pkt_num = pkt_num;
48   pkt->pktlen = pktlen;
49   pkt->pktns_id = pktns_id;
50   pkt->sent_ts = sent_ts;
51 
52   return pkt;
53 }
54 
reno_cc_reset(ngtcp2_reno_cc * cc)55 static void reno_cc_reset(ngtcp2_reno_cc *cc) {
56   cc->max_delivery_rate_sec = 0;
57   cc->target_cwnd = 0;
58   cc->pending_add = 0;
59 }
60 
ngtcp2_reno_cc_init(ngtcp2_reno_cc * cc,ngtcp2_log * log)61 void ngtcp2_reno_cc_init(ngtcp2_reno_cc *cc, ngtcp2_log *log) {
62   cc->ccb.log = log;
63   reno_cc_reset(cc);
64 }
65 
ngtcp2_reno_cc_free(ngtcp2_reno_cc * cc)66 void ngtcp2_reno_cc_free(ngtcp2_reno_cc *cc) { (void)cc; }
67 
ngtcp2_cc_reno_cc_init(ngtcp2_cc * cc,ngtcp2_log * log,const ngtcp2_mem * mem)68 int ngtcp2_cc_reno_cc_init(ngtcp2_cc *cc, ngtcp2_log *log,
69                            const ngtcp2_mem *mem) {
70   ngtcp2_reno_cc *reno_cc;
71 
72   reno_cc = ngtcp2_mem_calloc(mem, 1, sizeof(ngtcp2_reno_cc));
73   if (reno_cc == NULL) {
74     return NGTCP2_ERR_NOMEM;
75   }
76 
77   ngtcp2_reno_cc_init(reno_cc, log);
78 
79   cc->ccb = &reno_cc->ccb;
80   cc->on_pkt_acked = ngtcp2_cc_reno_cc_on_pkt_acked;
81   cc->congestion_event = ngtcp2_cc_reno_cc_congestion_event;
82   cc->on_persistent_congestion = ngtcp2_cc_reno_cc_on_persistent_congestion;
83   cc->on_ack_recv = ngtcp2_cc_reno_cc_on_ack_recv;
84   cc->reset = ngtcp2_cc_reno_cc_reset;
85 
86   return 0;
87 }
88 
ngtcp2_cc_reno_cc_free(ngtcp2_cc * cc,const ngtcp2_mem * mem)89 void ngtcp2_cc_reno_cc_free(ngtcp2_cc *cc, const ngtcp2_mem *mem) {
90   ngtcp2_reno_cc *reno_cc = ngtcp2_struct_of(cc->ccb, ngtcp2_reno_cc, ccb);
91 
92   ngtcp2_reno_cc_free(reno_cc);
93   ngtcp2_mem_free(mem, reno_cc);
94 }
95 
in_congestion_recovery(const ngtcp2_conn_stat * cstat,ngtcp2_tstamp sent_time)96 static int in_congestion_recovery(const ngtcp2_conn_stat *cstat,
97                                   ngtcp2_tstamp sent_time) {
98   return cstat->congestion_recovery_start_ts != UINT64_MAX &&
99          sent_time <= cstat->congestion_recovery_start_ts;
100 }
101 
ngtcp2_cc_reno_cc_on_pkt_acked(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt,ngtcp2_tstamp ts)102 void ngtcp2_cc_reno_cc_on_pkt_acked(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
103                                     const ngtcp2_cc_pkt *pkt,
104                                     ngtcp2_tstamp ts) {
105   ngtcp2_reno_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_reno_cc, ccb);
106   uint64_t m;
107   (void)ts;
108 
109   if (in_congestion_recovery(cstat, pkt->sent_ts)) {
110     return;
111   }
112 
113   if (cc->target_cwnd && cc->target_cwnd < cstat->cwnd) {
114     return;
115   }
116 
117   if (cstat->cwnd < cstat->ssthresh) {
118     cstat->cwnd += pkt->pktlen;
119     ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
120                     "pkn=%" PRId64 " acked, slow start cwnd=%" PRIu64,
121                     pkt->pkt_num, cstat->cwnd);
122     return;
123   }
124 
125   m = cstat->max_udp_payload_size * pkt->pktlen + cc->pending_add;
126   cc->pending_add = m % cstat->cwnd;
127 
128   cstat->cwnd += m / cstat->cwnd;
129 }
130 
ngtcp2_cc_reno_cc_congestion_event(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp sent_ts,ngtcp2_tstamp ts)131 void ngtcp2_cc_reno_cc_congestion_event(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
132                                         ngtcp2_tstamp sent_ts,
133                                         ngtcp2_tstamp ts) {
134   ngtcp2_reno_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_reno_cc, ccb);
135   uint64_t min_cwnd;
136 
137   if (in_congestion_recovery(cstat, sent_ts)) {
138     return;
139   }
140 
141   cstat->congestion_recovery_start_ts = ts;
142   cstat->cwnd >>= NGTCP2_LOSS_REDUCTION_FACTOR_BITS;
143   min_cwnd = 2 * cstat->max_udp_payload_size;
144   cstat->cwnd = ngtcp2_max(cstat->cwnd, min_cwnd);
145   cstat->ssthresh = cstat->cwnd;
146 
147   cc->pending_add = 0;
148 
149   ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
150                   "reduce cwnd because of packet loss cwnd=%" PRIu64,
151                   cstat->cwnd);
152 }
153 
ngtcp2_cc_reno_cc_on_persistent_congestion(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)154 void ngtcp2_cc_reno_cc_on_persistent_congestion(ngtcp2_cc *ccx,
155                                                 ngtcp2_conn_stat *cstat,
156                                                 ngtcp2_tstamp ts) {
157   (void)ccx;
158   (void)ts;
159 
160   cstat->cwnd = 2 * cstat->max_udp_payload_size;
161   cstat->congestion_recovery_start_ts = UINT64_MAX;
162 }
163 
ngtcp2_cc_reno_cc_on_ack_recv(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)164 void ngtcp2_cc_reno_cc_on_ack_recv(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
165                                    const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts) {
166   ngtcp2_reno_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_reno_cc, ccb);
167   uint64_t target_cwnd, initcwnd;
168   (void)ack;
169   (void)ts;
170 
171   /* TODO Use sliding window for min rtt measurement */
172   /* TODO Use sliding window */
173   cc->max_delivery_rate_sec =
174       ngtcp2_max(cc->max_delivery_rate_sec, cstat->delivery_rate_sec);
175 
176   if (cstat->min_rtt != UINT64_MAX && cc->max_delivery_rate_sec) {
177     target_cwnd = cc->max_delivery_rate_sec * cstat->min_rtt / NGTCP2_SECONDS;
178     initcwnd = ngtcp2_cc_compute_initcwnd(cstat->max_udp_payload_size);
179     cc->target_cwnd = ngtcp2_max(initcwnd, target_cwnd) * 289 / 100;
180 
181     ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
182                     "target_cwnd=%" PRIu64 " max_delivery_rate_sec=%" PRIu64
183                     " min_rtt=%" PRIu64,
184                     cc->target_cwnd, cc->max_delivery_rate_sec, cstat->min_rtt);
185   }
186 }
187 
ngtcp2_cc_reno_cc_reset(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)188 void ngtcp2_cc_reno_cc_reset(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
189                              ngtcp2_tstamp ts) {
190   ngtcp2_reno_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_reno_cc, ccb);
191   (void)cstat;
192   (void)ts;
193 
194   reno_cc_reset(cc);
195 }
196 
cubic_cc_reset(ngtcp2_cubic_cc * cc)197 static void cubic_cc_reset(ngtcp2_cubic_cc *cc) {
198   cc->max_delivery_rate_sec = 0;
199   cc->target_cwnd = 0;
200   cc->w_last_max = 0;
201   cc->w_tcp = 0;
202   cc->origin_point = 0;
203   cc->epoch_start = UINT64_MAX;
204   cc->k = 0;
205 
206   cc->prior.cwnd = 0;
207   cc->prior.ssthresh = 0;
208   cc->prior.w_last_max = 0;
209   cc->prior.w_tcp = 0;
210   cc->prior.origin_point = 0;
211   cc->prior.epoch_start = UINT64_MAX;
212   cc->prior.k = 0;
213 
214   cc->rtt_sample_count = 0;
215   cc->current_round_min_rtt = UINT64_MAX;
216   cc->last_round_min_rtt = UINT64_MAX;
217   cc->window_end = -1;
218 }
219 
ngtcp2_cubic_cc_init(ngtcp2_cubic_cc * cc,ngtcp2_log * log)220 void ngtcp2_cubic_cc_init(ngtcp2_cubic_cc *cc, ngtcp2_log *log) {
221   cc->ccb.log = log;
222   cubic_cc_reset(cc);
223 }
224 
ngtcp2_cubic_cc_free(ngtcp2_cubic_cc * cc)225 void ngtcp2_cubic_cc_free(ngtcp2_cubic_cc *cc) { (void)cc; }
226 
ngtcp2_cc_cubic_cc_init(ngtcp2_cc * cc,ngtcp2_log * log,const ngtcp2_mem * mem)227 int ngtcp2_cc_cubic_cc_init(ngtcp2_cc *cc, ngtcp2_log *log,
228                             const ngtcp2_mem *mem) {
229   ngtcp2_cubic_cc *cubic_cc;
230 
231   cubic_cc = ngtcp2_mem_calloc(mem, 1, sizeof(ngtcp2_cubic_cc));
232   if (cubic_cc == NULL) {
233     return NGTCP2_ERR_NOMEM;
234   }
235 
236   ngtcp2_cubic_cc_init(cubic_cc, log);
237 
238   cc->ccb = &cubic_cc->ccb;
239   cc->on_pkt_acked = ngtcp2_cc_cubic_cc_on_pkt_acked;
240   cc->congestion_event = ngtcp2_cc_cubic_cc_congestion_event;
241   cc->on_spurious_congestion = ngtcp2_cc_cubic_cc_on_spurious_congestion;
242   cc->on_persistent_congestion = ngtcp2_cc_cubic_cc_on_persistent_congestion;
243   cc->on_ack_recv = ngtcp2_cc_cubic_cc_on_ack_recv;
244   cc->on_pkt_sent = ngtcp2_cc_cubic_cc_on_pkt_sent;
245   cc->new_rtt_sample = ngtcp2_cc_cubic_cc_new_rtt_sample;
246   cc->reset = ngtcp2_cc_cubic_cc_reset;
247   cc->event = ngtcp2_cc_cubic_cc_event;
248 
249   return 0;
250 }
251 
ngtcp2_cc_cubic_cc_free(ngtcp2_cc * cc,const ngtcp2_mem * mem)252 void ngtcp2_cc_cubic_cc_free(ngtcp2_cc *cc, const ngtcp2_mem *mem) {
253   ngtcp2_cubic_cc *cubic_cc = ngtcp2_struct_of(cc->ccb, ngtcp2_cubic_cc, ccb);
254 
255   ngtcp2_cubic_cc_free(cubic_cc);
256   ngtcp2_mem_free(mem, cubic_cc);
257 }
258 
ngtcp2_cbrt(uint64_t n)259 static uint64_t ngtcp2_cbrt(uint64_t n) {
260   int d;
261   uint64_t a;
262 
263   if (n == 0) {
264     return 0;
265   }
266 
267 #if defined(_MSC_VER)
268 #  if defined(_M_X64)
269   d = (int)__lzcnt64(n);
270 #  elif defined(_M_ARM64)
271   {
272     unsigned long index;
273     d = sizeof(uint64_t) * CHAR_BIT;
274     if (_BitScanReverse64(&index, n)) {
275       d = d - 1 - index;
276     }
277   }
278 #  else
279   if ((n >> 32) != 0) {
280     d = __lzcnt((unsigned int)(n >> 32));
281   } else {
282     d = 32 + __lzcnt((unsigned int)n);
283   }
284 #  endif
285 #else
286   d = __builtin_clzll(n);
287 #endif
288   a = 1ULL << ((64 - d) / 3 + 1);
289 
290   for (; a * a * a > n;) {
291     a = (2 * a + n / a / a) / 3;
292   }
293   return a;
294 }
295 
296 /* HyStart++ constants */
297 #define NGTCP2_HS_MIN_SSTHRESH 16
298 #define NGTCP2_HS_N_RTT_SAMPLE 8
299 #define NGTCP2_HS_MIN_ETA (4 * NGTCP2_MILLISECONDS)
300 #define NGTCP2_HS_MAX_ETA (16 * NGTCP2_MILLISECONDS)
301 
ngtcp2_cc_cubic_cc_on_pkt_acked(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt,ngtcp2_tstamp ts)302 void ngtcp2_cc_cubic_cc_on_pkt_acked(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
303                                      const ngtcp2_cc_pkt *pkt,
304                                      ngtcp2_tstamp ts) {
305   ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
306   ngtcp2_duration t, min_rtt, eta;
307   uint64_t target;
308   uint64_t tx, kx, time_delta, delta;
309   uint64_t add, tcp_add;
310   uint64_t m;
311 
312   if (pkt->pktns_id == NGTCP2_PKTNS_ID_APPLICATION && cc->window_end != -1 &&
313       cc->window_end <= pkt->pkt_num) {
314     cc->window_end = -1;
315   }
316 
317   if (in_congestion_recovery(cstat, pkt->sent_ts)) {
318     return;
319   }
320 
321   if (cc->target_cwnd && cc->target_cwnd < cstat->cwnd) {
322     return;
323   }
324 
325   if (cstat->cwnd < cstat->ssthresh) {
326     /* slow-start */
327     cstat->cwnd += pkt->pktlen;
328 
329     ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
330                     "pkn=%" PRId64 " acked, slow start cwnd=%" PRIu64,
331                     pkt->pkt_num, cstat->cwnd);
332 
333     if (cc->last_round_min_rtt != UINT64_MAX &&
334         cc->current_round_min_rtt != UINT64_MAX &&
335         cstat->cwnd >= NGTCP2_HS_MIN_SSTHRESH * cstat->max_udp_payload_size &&
336         cc->rtt_sample_count >= NGTCP2_HS_N_RTT_SAMPLE) {
337       eta = cc->last_round_min_rtt / 8;
338 
339       if (eta < NGTCP2_HS_MIN_ETA) {
340         eta = NGTCP2_HS_MIN_ETA;
341       } else if (eta > NGTCP2_HS_MAX_ETA) {
342         eta = NGTCP2_HS_MAX_ETA;
343       }
344 
345       if (cc->current_round_min_rtt >= cc->last_round_min_rtt + eta) {
346         ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
347                         "HyStart++ exit slow start");
348 
349         cc->w_last_max = cstat->cwnd;
350         cstat->ssthresh = cstat->cwnd;
351       }
352     }
353 
354     return;
355   }
356 
357   /* congestion avoidance */
358 
359   if (cc->epoch_start == UINT64_MAX) {
360     cc->epoch_start = ts;
361     if (cstat->cwnd < cc->w_last_max) {
362       cc->k = ngtcp2_cbrt((cc->w_last_max - cstat->cwnd) * 10 / 4 /
363                           cstat->max_udp_payload_size);
364       cc->origin_point = cc->w_last_max;
365     } else {
366       cc->k = 0;
367       cc->origin_point = cstat->cwnd;
368     }
369 
370     cc->w_tcp = cstat->cwnd;
371 
372     ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
373                     "cubic-ca epoch_start=%" PRIu64 " k=%" PRIu64
374                     " origin_point=%" PRIu64,
375                     cc->epoch_start, cc->k, cc->origin_point);
376 
377     cc->pending_add = 0;
378     cc->pending_w_add = 0;
379   }
380 
381   min_rtt = cstat->min_rtt == UINT64_MAX ? cstat->initial_rtt : cstat->min_rtt;
382 
383   t = ts + min_rtt - cc->epoch_start;
384 
385   tx = (t << 4) / NGTCP2_SECONDS;
386   kx = (cc->k << 4);
387 
388   if (tx > kx) {
389     time_delta = tx - kx;
390   } else {
391     time_delta = kx - tx;
392   }
393 
394   delta = cstat->max_udp_payload_size *
395           ((((time_delta * time_delta) >> 4) * time_delta) >> 8) * 4 / 10;
396 
397   if (tx > kx) {
398     target = cc->origin_point + delta;
399   } else {
400     target = cc->origin_point - delta;
401   }
402 
403   if (target > cstat->cwnd) {
404     m = cc->pending_add + cstat->max_udp_payload_size * (target - cstat->cwnd);
405     add = m / cstat->cwnd;
406     cc->pending_add = m % cstat->cwnd;
407   } else {
408     m = cc->pending_add + cstat->max_udp_payload_size;
409     add = m / (100 * cstat->cwnd);
410     cc->pending_add = m % (100 * cstat->cwnd);
411   }
412 
413   m = cc->pending_w_add + cstat->max_udp_payload_size * pkt->pktlen;
414 
415   cc->w_tcp += m / cstat->cwnd;
416   cc->pending_w_add = m % cstat->cwnd;
417 
418   if (cc->w_tcp > cstat->cwnd) {
419     tcp_add =
420         cstat->max_udp_payload_size * (cc->w_tcp - cstat->cwnd) / cstat->cwnd;
421     if (tcp_add > add) {
422       add = tcp_add;
423     }
424   }
425 
426   cstat->cwnd += add;
427 
428   ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
429                   "pkn=%" PRId64 " acked, cubic-ca cwnd=%" PRIu64 " t=%" PRIu64
430                   " k=%" PRIi64 " time_delta=%" PRIu64 " delta=%" PRIu64
431                   " target=%" PRIu64 " w_tcp=%" PRIu64,
432                   pkt->pkt_num, cstat->cwnd, t, cc->k, time_delta >> 4, delta,
433                   target, cc->w_tcp);
434 }
435 
ngtcp2_cc_cubic_cc_congestion_event(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp sent_ts,ngtcp2_tstamp ts)436 void ngtcp2_cc_cubic_cc_congestion_event(ngtcp2_cc *ccx,
437                                          ngtcp2_conn_stat *cstat,
438                                          ngtcp2_tstamp sent_ts,
439                                          ngtcp2_tstamp ts) {
440   ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
441   uint64_t min_cwnd;
442 
443   if (in_congestion_recovery(cstat, sent_ts)) {
444     return;
445   }
446 
447   if (cc->prior.cwnd < cstat->cwnd) {
448     cc->prior.cwnd = cstat->cwnd;
449     cc->prior.ssthresh = cstat->ssthresh;
450     cc->prior.w_last_max = cc->w_last_max;
451     cc->prior.w_tcp = cc->w_tcp;
452     cc->prior.origin_point = cc->origin_point;
453     cc->prior.epoch_start = cc->epoch_start;
454     cc->prior.k = cc->k;
455   }
456 
457   cstat->congestion_recovery_start_ts = ts;
458 
459   cc->epoch_start = UINT64_MAX;
460   if (cstat->cwnd < cc->w_last_max) {
461     cc->w_last_max = cstat->cwnd * 17 / 10 / 2;
462   } else {
463     cc->w_last_max = cstat->cwnd;
464   }
465 
466   min_cwnd = 2 * cstat->max_udp_payload_size;
467   cstat->ssthresh = cstat->cwnd * 7 / 10;
468   cstat->ssthresh = ngtcp2_max(cstat->ssthresh, min_cwnd);
469   cstat->cwnd = cstat->ssthresh;
470 
471   ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
472                   "reduce cwnd because of packet loss cwnd=%" PRIu64,
473                   cstat->cwnd);
474 }
475 
ngtcp2_cc_cubic_cc_on_spurious_congestion(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)476 void ngtcp2_cc_cubic_cc_on_spurious_congestion(ngtcp2_cc *ccx,
477                                                ngtcp2_conn_stat *cstat,
478                                                ngtcp2_tstamp ts) {
479   ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
480   (void)ts;
481 
482   if (cstat->cwnd >= cc->prior.cwnd) {
483     return;
484   }
485 
486   cstat->congestion_recovery_start_ts = UINT64_MAX;
487 
488   cstat->cwnd = cc->prior.cwnd;
489   cstat->ssthresh = cc->prior.ssthresh;
490   cc->w_last_max = cc->prior.w_last_max;
491   cc->w_tcp = cc->prior.w_tcp;
492   cc->origin_point = cc->prior.origin_point;
493   cc->epoch_start = cc->prior.epoch_start;
494   cc->k = cc->prior.k;
495 
496   cc->prior.cwnd = 0;
497   cc->prior.ssthresh = 0;
498   cc->prior.w_last_max = 0;
499   cc->prior.w_tcp = 0;
500   cc->prior.origin_point = 0;
501   cc->prior.epoch_start = UINT64_MAX;
502   cc->prior.k = 0;
503 
504   ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
505                   "spurious congestion is detected and congestion state is "
506                   "restored cwnd=%" PRIu64,
507                   cstat->cwnd);
508 }
509 
ngtcp2_cc_cubic_cc_on_persistent_congestion(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)510 void ngtcp2_cc_cubic_cc_on_persistent_congestion(ngtcp2_cc *ccx,
511                                                  ngtcp2_conn_stat *cstat,
512                                                  ngtcp2_tstamp ts) {
513   (void)ccx;
514   (void)ts;
515 
516   cstat->cwnd = 2 * cstat->max_udp_payload_size;
517   cstat->congestion_recovery_start_ts = UINT64_MAX;
518 }
519 
ngtcp2_cc_cubic_cc_on_ack_recv(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_ack * ack,ngtcp2_tstamp ts)520 void ngtcp2_cc_cubic_cc_on_ack_recv(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
521                                     const ngtcp2_cc_ack *ack,
522                                     ngtcp2_tstamp ts) {
523   ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
524   uint64_t target_cwnd, initcwnd;
525   (void)ack;
526   (void)ts;
527 
528   /* TODO Use sliding window for min rtt measurement */
529   /* TODO Use sliding window */
530   cc->max_delivery_rate_sec =
531       ngtcp2_max(cc->max_delivery_rate_sec, cstat->delivery_rate_sec);
532 
533   if (cstat->min_rtt != UINT64_MAX && cc->max_delivery_rate_sec) {
534     target_cwnd = cc->max_delivery_rate_sec * cstat->min_rtt / NGTCP2_SECONDS;
535     initcwnd = ngtcp2_cc_compute_initcwnd(cstat->max_udp_payload_size);
536     cc->target_cwnd = ngtcp2_max(initcwnd, target_cwnd) * 289 / 100;
537 
538     ngtcp2_log_info(cc->ccb.log, NGTCP2_LOG_EVENT_RCV,
539                     "target_cwnd=%" PRIu64 " max_delivery_rate_sec=%" PRIu64
540                     " min_rtt=%" PRIu64,
541                     cc->target_cwnd, cc->max_delivery_rate_sec, cstat->min_rtt);
542   }
543 }
544 
ngtcp2_cc_cubic_cc_on_pkt_sent(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,const ngtcp2_cc_pkt * pkt)545 void ngtcp2_cc_cubic_cc_on_pkt_sent(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
546                                     const ngtcp2_cc_pkt *pkt) {
547   ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
548   (void)cstat;
549 
550   if (pkt->pktns_id != NGTCP2_PKTNS_ID_APPLICATION || cc->window_end != -1) {
551     return;
552   }
553 
554   cc->window_end = pkt->pkt_num;
555   cc->last_round_min_rtt = cc->current_round_min_rtt;
556   cc->current_round_min_rtt = UINT64_MAX;
557   cc->rtt_sample_count = 0;
558 }
559 
ngtcp2_cc_cubic_cc_new_rtt_sample(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)560 void ngtcp2_cc_cubic_cc_new_rtt_sample(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
561                                        ngtcp2_tstamp ts) {
562   ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
563   (void)ts;
564 
565   if (cc->window_end == -1) {
566     return;
567   }
568 
569   cc->current_round_min_rtt =
570       ngtcp2_min(cc->current_round_min_rtt, cstat->latest_rtt);
571   ++cc->rtt_sample_count;
572 }
573 
ngtcp2_cc_cubic_cc_reset(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)574 void ngtcp2_cc_cubic_cc_reset(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
575                               ngtcp2_tstamp ts) {
576   ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
577   (void)cstat;
578   (void)ts;
579 
580   cubic_cc_reset(cc);
581 }
582 
ngtcp2_cc_cubic_cc_event(ngtcp2_cc * ccx,ngtcp2_conn_stat * cstat,ngtcp2_cc_event_type event,ngtcp2_tstamp ts)583 void ngtcp2_cc_cubic_cc_event(ngtcp2_cc *ccx, ngtcp2_conn_stat *cstat,
584                               ngtcp2_cc_event_type event, ngtcp2_tstamp ts) {
585   ngtcp2_cubic_cc *cc = ngtcp2_struct_of(ccx->ccb, ngtcp2_cubic_cc, ccb);
586   ngtcp2_tstamp last_ts;
587 
588   if (event != NGTCP2_CC_EVENT_TYPE_TX_START || cc->epoch_start == UINT64_MAX) {
589     return;
590   }
591 
592   last_ts = cstat->last_tx_pkt_ts[NGTCP2_PKTNS_ID_APPLICATION];
593   if (last_ts == UINT64_MAX || last_ts <= cc->epoch_start) {
594     return;
595   }
596 
597   assert(ts >= last_ts);
598 
599   cc->epoch_start += ts - last_ts;
600 }
601