1 /*
2 * ngtcp2
3 *
4 * Copyright (c) 2017 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_rtb.h"
26
27 #include <assert.h>
28 #include <string.h>
29
30 #include "ngtcp2_macro.h"
31 #include "ngtcp2_conn.h"
32 #include "ngtcp2_log.h"
33 #include "ngtcp2_vec.h"
34 #include "ngtcp2_cc.h"
35 #include "ngtcp2_rcvry.h"
36 #include "ngtcp2_rst.h"
37
ngtcp2_frame_chain_new(ngtcp2_frame_chain ** pfrc,const ngtcp2_mem * mem)38 int ngtcp2_frame_chain_new(ngtcp2_frame_chain **pfrc, const ngtcp2_mem *mem) {
39 *pfrc = ngtcp2_mem_malloc(mem, sizeof(ngtcp2_frame_chain));
40 if (*pfrc == NULL) {
41 return NGTCP2_ERR_NOMEM;
42 }
43
44 ngtcp2_frame_chain_init(*pfrc);
45
46 return 0;
47 }
48
ngtcp2_frame_chain_objalloc_new(ngtcp2_frame_chain ** pfrc,ngtcp2_objalloc * objalloc)49 int ngtcp2_frame_chain_objalloc_new(ngtcp2_frame_chain **pfrc,
50 ngtcp2_objalloc *objalloc) {
51 *pfrc = ngtcp2_objalloc_frame_chain_get(objalloc);
52 if (*pfrc == NULL) {
53 return NGTCP2_ERR_NOMEM;
54 }
55
56 ngtcp2_frame_chain_init(*pfrc);
57
58 return 0;
59 }
60
ngtcp2_frame_chain_extralen_new(ngtcp2_frame_chain ** pfrc,size_t extralen,const ngtcp2_mem * mem)61 int ngtcp2_frame_chain_extralen_new(ngtcp2_frame_chain **pfrc, size_t extralen,
62 const ngtcp2_mem *mem) {
63 *pfrc = ngtcp2_mem_malloc(mem, sizeof(ngtcp2_frame_chain) + extralen);
64 if (*pfrc == NULL) {
65 return NGTCP2_ERR_NOMEM;
66 }
67
68 ngtcp2_frame_chain_init(*pfrc);
69
70 return 0;
71 }
72
ngtcp2_frame_chain_stream_datacnt_objalloc_new(ngtcp2_frame_chain ** pfrc,size_t datacnt,ngtcp2_objalloc * objalloc,const ngtcp2_mem * mem)73 int ngtcp2_frame_chain_stream_datacnt_objalloc_new(ngtcp2_frame_chain **pfrc,
74 size_t datacnt,
75 ngtcp2_objalloc *objalloc,
76 const ngtcp2_mem *mem) {
77 size_t need, avail = sizeof(ngtcp2_frame) - sizeof(ngtcp2_stream);
78
79 if (datacnt > 1) {
80 need = sizeof(ngtcp2_vec) * (datacnt - 1);
81
82 if (need > avail) {
83 return ngtcp2_frame_chain_extralen_new(pfrc, need - avail, mem);
84 }
85 }
86
87 return ngtcp2_frame_chain_objalloc_new(pfrc, objalloc);
88 }
89
ngtcp2_frame_chain_crypto_datacnt_objalloc_new(ngtcp2_frame_chain ** pfrc,size_t datacnt,ngtcp2_objalloc * objalloc,const ngtcp2_mem * mem)90 int ngtcp2_frame_chain_crypto_datacnt_objalloc_new(ngtcp2_frame_chain **pfrc,
91 size_t datacnt,
92 ngtcp2_objalloc *objalloc,
93 const ngtcp2_mem *mem) {
94 size_t need, avail = sizeof(ngtcp2_frame) - sizeof(ngtcp2_crypto);
95
96 if (datacnt > 1) {
97 need = sizeof(ngtcp2_vec) * (datacnt - 1);
98
99 if (need > avail) {
100 return ngtcp2_frame_chain_extralen_new(pfrc, need - avail, mem);
101 }
102 }
103
104 return ngtcp2_frame_chain_objalloc_new(pfrc, objalloc);
105 }
106
ngtcp2_frame_chain_new_token_objalloc_new(ngtcp2_frame_chain ** pfrc,const ngtcp2_vec * token,ngtcp2_objalloc * objalloc,const ngtcp2_mem * mem)107 int ngtcp2_frame_chain_new_token_objalloc_new(ngtcp2_frame_chain **pfrc,
108 const ngtcp2_vec *token,
109 ngtcp2_objalloc *objalloc,
110 const ngtcp2_mem *mem) {
111 size_t avail = sizeof(ngtcp2_frame) - sizeof(ngtcp2_new_token);
112 int rv;
113 uint8_t *p;
114 ngtcp2_frame *fr;
115
116 if (token->len > avail) {
117 rv = ngtcp2_frame_chain_extralen_new(pfrc, token->len - avail, mem);
118 } else {
119 rv = ngtcp2_frame_chain_objalloc_new(pfrc, objalloc);
120 }
121 if (rv != 0) {
122 return rv;
123 }
124
125 fr = &(*pfrc)->fr;
126 fr->type = NGTCP2_FRAME_NEW_TOKEN;
127
128 p = (uint8_t *)fr + sizeof(ngtcp2_new_token);
129 memcpy(p, token->base, token->len);
130
131 ngtcp2_vec_init(&fr->new_token.token, p, token->len);
132
133 return 0;
134 }
135
ngtcp2_frame_chain_del(ngtcp2_frame_chain * frc,const ngtcp2_mem * mem)136 void ngtcp2_frame_chain_del(ngtcp2_frame_chain *frc, const ngtcp2_mem *mem) {
137 ngtcp2_frame_chain_binder *binder;
138
139 if (frc == NULL) {
140 return;
141 }
142
143 binder = frc->binder;
144 if (binder && --binder->refcount == 0) {
145 ngtcp2_mem_free(mem, binder);
146 }
147
148 ngtcp2_mem_free(mem, frc);
149 }
150
ngtcp2_frame_chain_objalloc_del(ngtcp2_frame_chain * frc,ngtcp2_objalloc * objalloc,const ngtcp2_mem * mem)151 void ngtcp2_frame_chain_objalloc_del(ngtcp2_frame_chain *frc,
152 ngtcp2_objalloc *objalloc,
153 const ngtcp2_mem *mem) {
154 ngtcp2_frame_chain_binder *binder;
155
156 if (frc == NULL) {
157 return;
158 }
159
160 switch (frc->fr.type) {
161 case NGTCP2_FRAME_STREAM:
162 if (frc->fr.stream.datacnt &&
163 sizeof(ngtcp2_vec) * (frc->fr.stream.datacnt - 1) >
164 sizeof(ngtcp2_frame) - sizeof(ngtcp2_stream)) {
165 ngtcp2_frame_chain_del(frc, mem);
166
167 return;
168 }
169
170 break;
171 case NGTCP2_FRAME_CRYPTO:
172 if (frc->fr.crypto.datacnt &&
173 sizeof(ngtcp2_vec) * (frc->fr.crypto.datacnt - 1) >
174 sizeof(ngtcp2_frame) - sizeof(ngtcp2_crypto)) {
175 ngtcp2_frame_chain_del(frc, mem);
176
177 return;
178 }
179
180 break;
181 case NGTCP2_FRAME_NEW_TOKEN:
182 if (frc->fr.new_token.token.len >
183 sizeof(ngtcp2_frame) - sizeof(ngtcp2_new_token)) {
184 ngtcp2_frame_chain_del(frc, mem);
185
186 return;
187 }
188
189 break;
190 }
191
192 binder = frc->binder;
193 if (binder && --binder->refcount == 0) {
194 ngtcp2_mem_free(mem, binder);
195 }
196
197 frc->binder = NULL;
198
199 ngtcp2_objalloc_frame_chain_release(objalloc, frc);
200 }
201
ngtcp2_frame_chain_init(ngtcp2_frame_chain * frc)202 void ngtcp2_frame_chain_init(ngtcp2_frame_chain *frc) {
203 frc->next = NULL;
204 frc->binder = NULL;
205 }
206
ngtcp2_frame_chain_list_objalloc_del(ngtcp2_frame_chain * frc,ngtcp2_objalloc * objalloc,const ngtcp2_mem * mem)207 void ngtcp2_frame_chain_list_objalloc_del(ngtcp2_frame_chain *frc,
208 ngtcp2_objalloc *objalloc,
209 const ngtcp2_mem *mem) {
210 ngtcp2_frame_chain *next;
211
212 for (; frc; frc = next) {
213 next = frc->next;
214
215 ngtcp2_frame_chain_objalloc_del(frc, objalloc, mem);
216 }
217 }
218
ngtcp2_frame_chain_binder_new(ngtcp2_frame_chain_binder ** pbinder,const ngtcp2_mem * mem)219 int ngtcp2_frame_chain_binder_new(ngtcp2_frame_chain_binder **pbinder,
220 const ngtcp2_mem *mem) {
221 *pbinder = ngtcp2_mem_calloc(mem, 1, sizeof(ngtcp2_frame_chain_binder));
222 if (*pbinder == NULL) {
223 return NGTCP2_ERR_NOMEM;
224 }
225
226 return 0;
227 }
228
ngtcp2_bind_frame_chains(ngtcp2_frame_chain * a,ngtcp2_frame_chain * b,const ngtcp2_mem * mem)229 int ngtcp2_bind_frame_chains(ngtcp2_frame_chain *a, ngtcp2_frame_chain *b,
230 const ngtcp2_mem *mem) {
231 ngtcp2_frame_chain_binder *binder;
232 int rv;
233
234 assert(b->binder == NULL);
235
236 if (a->binder == NULL) {
237 rv = ngtcp2_frame_chain_binder_new(&binder, mem);
238 if (rv != 0) {
239 return rv;
240 }
241
242 a->binder = binder;
243 ++a->binder->refcount;
244 }
245
246 b->binder = a->binder;
247 ++b->binder->refcount;
248
249 return 0;
250 }
251
rtb_entry_init(ngtcp2_rtb_entry * ent,const ngtcp2_pkt_hd * hd,ngtcp2_frame_chain * frc,ngtcp2_tstamp ts,size_t pktlen,uint16_t flags)252 static void rtb_entry_init(ngtcp2_rtb_entry *ent, const ngtcp2_pkt_hd *hd,
253 ngtcp2_frame_chain *frc, ngtcp2_tstamp ts,
254 size_t pktlen, uint16_t flags) {
255 memset(ent, 0, sizeof(*ent));
256
257 ent->hd.pkt_num = hd->pkt_num;
258 ent->hd.type = hd->type;
259 ent->hd.flags = hd->flags;
260 ent->frc = frc;
261 ent->ts = ts;
262 ent->lost_ts = UINT64_MAX;
263 ent->pktlen = pktlen;
264 ent->flags = flags;
265 ent->next = NULL;
266 }
267
ngtcp2_rtb_entry_objalloc_new(ngtcp2_rtb_entry ** pent,const ngtcp2_pkt_hd * hd,ngtcp2_frame_chain * frc,ngtcp2_tstamp ts,size_t pktlen,uint16_t flags,ngtcp2_objalloc * objalloc)268 int ngtcp2_rtb_entry_objalloc_new(ngtcp2_rtb_entry **pent,
269 const ngtcp2_pkt_hd *hd,
270 ngtcp2_frame_chain *frc, ngtcp2_tstamp ts,
271 size_t pktlen, uint16_t flags,
272 ngtcp2_objalloc *objalloc) {
273 *pent = ngtcp2_objalloc_rtb_entry_get(objalloc);
274 if (*pent == NULL) {
275 return NGTCP2_ERR_NOMEM;
276 }
277
278 rtb_entry_init(*pent, hd, frc, ts, pktlen, flags);
279
280 return 0;
281 }
282
ngtcp2_rtb_entry_objalloc_del(ngtcp2_rtb_entry * ent,ngtcp2_objalloc * objalloc,ngtcp2_objalloc * frc_objalloc,const ngtcp2_mem * mem)283 void ngtcp2_rtb_entry_objalloc_del(ngtcp2_rtb_entry *ent,
284 ngtcp2_objalloc *objalloc,
285 ngtcp2_objalloc *frc_objalloc,
286 const ngtcp2_mem *mem) {
287 ngtcp2_frame_chain_list_objalloc_del(ent->frc, frc_objalloc, mem);
288
289 ent->frc = NULL;
290
291 ngtcp2_objalloc_rtb_entry_release(objalloc, ent);
292 }
293
greater(const ngtcp2_ksl_key * lhs,const ngtcp2_ksl_key * rhs)294 static int greater(const ngtcp2_ksl_key *lhs, const ngtcp2_ksl_key *rhs) {
295 return *(int64_t *)lhs > *(int64_t *)rhs;
296 }
297
ngtcp2_rtb_init(ngtcp2_rtb * rtb,ngtcp2_pktns_id pktns_id,ngtcp2_strm * crypto,ngtcp2_rst * rst,ngtcp2_cc * cc,ngtcp2_log * log,ngtcp2_qlog * qlog,ngtcp2_objalloc * rtb_entry_objalloc,ngtcp2_objalloc * frc_objalloc,const ngtcp2_mem * mem)298 void ngtcp2_rtb_init(ngtcp2_rtb *rtb, ngtcp2_pktns_id pktns_id,
299 ngtcp2_strm *crypto, ngtcp2_rst *rst, ngtcp2_cc *cc,
300 ngtcp2_log *log, ngtcp2_qlog *qlog,
301 ngtcp2_objalloc *rtb_entry_objalloc,
302 ngtcp2_objalloc *frc_objalloc, const ngtcp2_mem *mem) {
303 rtb->rtb_entry_objalloc = rtb_entry_objalloc;
304 rtb->frc_objalloc = frc_objalloc;
305 ngtcp2_ksl_init(&rtb->ents, greater, sizeof(int64_t), mem);
306 rtb->crypto = crypto;
307 rtb->rst = rst;
308 rtb->cc = cc;
309 rtb->log = log;
310 rtb->qlog = qlog;
311 rtb->mem = mem;
312 rtb->largest_acked_tx_pkt_num = -1;
313 rtb->num_ack_eliciting = 0;
314 rtb->num_retransmittable = 0;
315 rtb->num_pto_eliciting = 0;
316 rtb->probe_pkt_left = 0;
317 rtb->pktns_id = pktns_id;
318 rtb->cc_pkt_num = 0;
319 rtb->cc_bytes_in_flight = 0;
320 rtb->persistent_congestion_start_ts = UINT64_MAX;
321 rtb->num_lost_pkts = 0;
322 rtb->num_lost_pmtud_pkts = 0;
323 }
324
ngtcp2_rtb_free(ngtcp2_rtb * rtb)325 void ngtcp2_rtb_free(ngtcp2_rtb *rtb) {
326 ngtcp2_ksl_it it;
327
328 if (rtb == NULL) {
329 return;
330 }
331
332 it = ngtcp2_ksl_begin(&rtb->ents);
333
334 for (; !ngtcp2_ksl_it_end(&it); ngtcp2_ksl_it_next(&it)) {
335 ngtcp2_rtb_entry_objalloc_del(ngtcp2_ksl_it_get(&it),
336 rtb->rtb_entry_objalloc, rtb->frc_objalloc,
337 rtb->mem);
338 }
339
340 ngtcp2_ksl_free(&rtb->ents);
341 }
342
rtb_on_add(ngtcp2_rtb * rtb,ngtcp2_rtb_entry * ent,ngtcp2_conn_stat * cstat)343 static void rtb_on_add(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
344 ngtcp2_conn_stat *cstat) {
345 ngtcp2_rst_on_pkt_sent(rtb->rst, ent, cstat);
346
347 assert(rtb->cc_pkt_num <= ent->hd.pkt_num);
348
349 cstat->bytes_in_flight += ent->pktlen;
350 rtb->cc_bytes_in_flight += ent->pktlen;
351
352 ngtcp2_rst_update_app_limited(rtb->rst, cstat);
353
354 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING) {
355 ++rtb->num_ack_eliciting;
356 }
357 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE) {
358 ++rtb->num_retransmittable;
359 }
360 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING) {
361 ++rtb->num_pto_eliciting;
362 }
363 }
364
rtb_on_remove(ngtcp2_rtb * rtb,ngtcp2_rtb_entry * ent,ngtcp2_conn_stat * cstat)365 static size_t rtb_on_remove(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
366 ngtcp2_conn_stat *cstat) {
367 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED) {
368 assert(rtb->num_lost_pkts);
369 --rtb->num_lost_pkts;
370
371 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) {
372 assert(rtb->num_lost_pmtud_pkts);
373 --rtb->num_lost_pmtud_pkts;
374 }
375
376 return 0;
377 }
378
379 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING) {
380 assert(rtb->num_ack_eliciting);
381 --rtb->num_ack_eliciting;
382 }
383
384 if ((ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE) &&
385 !(ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED)) {
386 assert(rtb->num_retransmittable);
387 --rtb->num_retransmittable;
388 }
389
390 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING) {
391 assert(rtb->num_pto_eliciting);
392 --rtb->num_pto_eliciting;
393 }
394
395 if (rtb->cc_pkt_num <= ent->hd.pkt_num) {
396 assert(cstat->bytes_in_flight >= ent->pktlen);
397 cstat->bytes_in_flight -= ent->pktlen;
398
399 assert(rtb->cc_bytes_in_flight >= ent->pktlen);
400 rtb->cc_bytes_in_flight -= ent->pktlen;
401
402 /* If PMTUD packet is lost, we do not report the lost bytes to the
403 caller in order to ignore loss of PMTUD packet. */
404 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) {
405 return 0;
406 }
407
408 return ent->pktlen;
409 }
410
411 return 0;
412 }
413
414 /* NGTCP2_RECLAIM_FLAG_NONE indicates that no flag is set. */
415 #define NGTCP2_RECLAIM_FLAG_NONE 0x00u
416 /* NGTCP2_RECLAIM_FLAG_ON_LOSS indicates that frames are reclaimed
417 because of the packet loss.*/
418 #define NGTCP2_RECLAIM_FLAG_ON_LOSS 0x01u
419
420 /*
421 * rtb_reclaim_frame queues unacknowledged frames included in |ent|
422 * for retransmission. The re-queued frames are not deleted from
423 * |ent|. It returns the number of frames queued. |flags| is bitwise
424 * OR of 0 or more of NGTCP2_RECLAIM_FLAG_*.
425 */
rtb_reclaim_frame(ngtcp2_rtb * rtb,uint8_t flags,ngtcp2_conn * conn,ngtcp2_pktns * pktns,ngtcp2_rtb_entry * ent)426 static ngtcp2_ssize rtb_reclaim_frame(ngtcp2_rtb *rtb, uint8_t flags,
427 ngtcp2_conn *conn, ngtcp2_pktns *pktns,
428 ngtcp2_rtb_entry *ent) {
429 ngtcp2_frame_chain *frc, *nfrc, **pfrc = &pktns->tx.frq;
430 ngtcp2_frame *fr;
431 ngtcp2_strm *strm;
432 ngtcp2_range gap, range;
433 size_t num_reclaimed = 0;
434 int rv;
435 int streamfrq_empty;
436
437 assert(ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE);
438
439 /* TODO Reconsider the order of pfrc */
440 for (frc = ent->frc; frc; frc = frc->next) {
441 fr = &frc->fr;
442 /* Check that a late ACK acknowledged this frame. */
443 if (frc->binder &&
444 (frc->binder->flags & NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK)) {
445 continue;
446 }
447 switch (frc->fr.type) {
448 case NGTCP2_FRAME_STREAM:
449 strm = ngtcp2_conn_find_stream(conn, fr->stream.stream_id);
450 if (strm == NULL) {
451 continue;
452 }
453
454 gap = ngtcp2_strm_get_unacked_range_after(strm, fr->stream.offset);
455
456 range.begin = fr->stream.offset;
457 range.end = fr->stream.offset +
458 ngtcp2_vec_len(fr->stream.data, fr->stream.datacnt);
459 range = ngtcp2_range_intersect(&range, &gap);
460 if (ngtcp2_range_len(&range) == 0) {
461 if (!fr->stream.fin) {
462 /* 0 length STREAM frame with offset == 0 must be
463 retransmitted if no non-empty data is sent to this stream
464 and no data in this stream is acknowledged. */
465 if (fr->stream.offset != 0 || fr->stream.datacnt != 0 ||
466 strm->tx.offset || (strm->flags & NGTCP2_STRM_FLAG_ANY_ACKED)) {
467 continue;
468 }
469 } else if (strm->flags & NGTCP2_STRM_FLAG_FIN_ACKED) {
470 continue;
471 }
472 }
473
474 if ((flags & NGTCP2_RECLAIM_FLAG_ON_LOSS) &&
475 ent->hd.pkt_num != strm->tx.last_lost_pkt_num) {
476 strm->tx.last_lost_pkt_num = ent->hd.pkt_num;
477 ++strm->tx.loss_count;
478 }
479
480 rv = ngtcp2_frame_chain_stream_datacnt_objalloc_new(
481 &nfrc, fr->stream.datacnt, rtb->frc_objalloc, rtb->mem);
482 if (rv != 0) {
483 return rv;
484 }
485
486 nfrc->fr = *fr;
487 ngtcp2_vec_copy(nfrc->fr.stream.data, fr->stream.data,
488 fr->stream.datacnt);
489
490 streamfrq_empty = ngtcp2_strm_streamfrq_empty(strm);
491 rv = ngtcp2_strm_streamfrq_push(strm, nfrc);
492 if (rv != 0) {
493 ngtcp2_frame_chain_objalloc_del(nfrc, rtb->frc_objalloc, rtb->mem);
494 return rv;
495 }
496 if (!ngtcp2_strm_is_tx_queued(strm)) {
497 strm->cycle = ngtcp2_conn_tx_strmq_first_cycle(conn);
498 rv = ngtcp2_conn_tx_strmq_push(conn, strm);
499 if (rv != 0) {
500 return rv;
501 }
502 }
503 if (streamfrq_empty) {
504 ++conn->tx.strmq_nretrans;
505 }
506
507 ++num_reclaimed;
508
509 continue;
510 case NGTCP2_FRAME_CRYPTO:
511 /* Don't resend CRYPTO frame if the whole region it contains has
512 been acknowledged */
513 gap = ngtcp2_strm_get_unacked_range_after(rtb->crypto, fr->crypto.offset);
514
515 range.begin = fr->crypto.offset;
516 range.end = fr->crypto.offset +
517 ngtcp2_vec_len(fr->crypto.data, fr->crypto.datacnt);
518 range = ngtcp2_range_intersect(&range, &gap);
519 if (ngtcp2_range_len(&range) == 0) {
520 continue;
521 }
522
523 rv = ngtcp2_frame_chain_crypto_datacnt_objalloc_new(
524 &nfrc, fr->crypto.datacnt, rtb->frc_objalloc, rtb->mem);
525 if (rv != 0) {
526 return rv;
527 }
528
529 nfrc->fr = *fr;
530 ngtcp2_vec_copy(nfrc->fr.crypto.data, fr->crypto.data,
531 fr->crypto.datacnt);
532
533 rv = ngtcp2_ksl_insert(&pktns->crypto.tx.frq, NULL,
534 &nfrc->fr.crypto.offset, nfrc);
535 if (rv != 0) {
536 assert(ngtcp2_err_is_fatal(rv));
537 ngtcp2_frame_chain_objalloc_del(nfrc, rtb->frc_objalloc, rtb->mem);
538 return rv;
539 }
540
541 ++num_reclaimed;
542
543 continue;
544 case NGTCP2_FRAME_NEW_TOKEN:
545 rv = ngtcp2_frame_chain_new_token_objalloc_new(
546 &nfrc, &fr->new_token.token, rtb->frc_objalloc, rtb->mem);
547 if (rv != 0) {
548 return rv;
549 }
550
551 rv = ngtcp2_bind_frame_chains(frc, nfrc, rtb->mem);
552 if (rv != 0) {
553 return rv;
554 }
555
556 break;
557 case NGTCP2_FRAME_DATAGRAM:
558 case NGTCP2_FRAME_DATAGRAM_LEN:
559 continue;
560 default:
561 rv = ngtcp2_frame_chain_objalloc_new(&nfrc, rtb->frc_objalloc);
562 if (rv != 0) {
563 return rv;
564 }
565
566 nfrc->fr = *fr;
567
568 rv = ngtcp2_bind_frame_chains(frc, nfrc, rtb->mem);
569 if (rv != 0) {
570 return rv;
571 }
572
573 break;
574 }
575
576 ++num_reclaimed;
577
578 nfrc->next = *pfrc;
579 *pfrc = nfrc;
580 pfrc = &nfrc->next;
581 }
582
583 return (ngtcp2_ssize)num_reclaimed;
584 }
585
586 /*
587 * conn_process_lost_datagram calls ngtcp2_lost_datagram callback for
588 * lost DATAGRAM frames.
589 */
conn_process_lost_datagram(ngtcp2_conn * conn,ngtcp2_rtb_entry * ent)590 static int conn_process_lost_datagram(ngtcp2_conn *conn,
591 ngtcp2_rtb_entry *ent) {
592 ngtcp2_frame_chain *frc;
593 int rv;
594
595 for (frc = ent->frc; frc; frc = frc->next) {
596 switch (frc->fr.type) {
597 case NGTCP2_FRAME_DATAGRAM:
598 case NGTCP2_FRAME_DATAGRAM_LEN:
599 assert(conn->callbacks.lost_datagram);
600
601 rv = conn->callbacks.lost_datagram(conn, frc->fr.datagram.dgram_id,
602 conn->user_data);
603 if (rv != 0) {
604 return NGTCP2_ERR_CALLBACK_FAILURE;
605 }
606 break;
607 }
608 }
609
610 return 0;
611 }
612
rtb_on_pkt_lost(ngtcp2_rtb * rtb,ngtcp2_ksl_it * it,ngtcp2_rtb_entry * ent,ngtcp2_conn_stat * cstat,ngtcp2_conn * conn,ngtcp2_pktns * pktns,ngtcp2_tstamp ts)613 static int rtb_on_pkt_lost(ngtcp2_rtb *rtb, ngtcp2_ksl_it *it,
614 ngtcp2_rtb_entry *ent, ngtcp2_conn_stat *cstat,
615 ngtcp2_conn *conn, ngtcp2_pktns *pktns,
616 ngtcp2_tstamp ts) {
617 int rv;
618 ngtcp2_ssize reclaimed;
619 ngtcp2_cc *cc = rtb->cc;
620 ngtcp2_cc_pkt pkt;
621
622 ngtcp2_log_pkt_lost(rtb->log, ent->hd.pkt_num, ent->hd.type, ent->hd.flags,
623 ent->ts);
624
625 if (rtb->qlog) {
626 ngtcp2_qlog_pkt_lost(rtb->qlog, ent);
627 }
628
629 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) {
630 ++rtb->num_lost_pmtud_pkts;
631 } else if (rtb->cc->on_pkt_lost) {
632 cc->on_pkt_lost(cc, cstat,
633 ngtcp2_cc_pkt_init(&pkt, ent->hd.pkt_num, ent->pktlen,
634 rtb->pktns_id, ent->ts, ent->rst.lost,
635 ent->rst.tx_in_flight,
636 ent->rst.is_app_limited),
637 ts);
638 }
639
640 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED) {
641 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
642 "pkn=%" PRId64 " has already been reclaimed on PTO",
643 ent->hd.pkt_num);
644 assert(!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED));
645 assert(UINT64_MAX == ent->lost_ts);
646
647 ent->flags |= NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED;
648 ent->lost_ts = ts;
649
650 ++rtb->num_lost_pkts;
651
652 ngtcp2_ksl_it_next(it);
653
654 return 0;
655 }
656
657 if (conn->callbacks.lost_datagram &&
658 (ent->flags & NGTCP2_RTB_ENTRY_FLAG_DATAGRAM)) {
659 rv = conn_process_lost_datagram(conn, ent);
660 if (rv != 0) {
661 return rv;
662 }
663 }
664
665 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE) {
666 assert(ent->frc);
667 assert(!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED));
668 assert(UINT64_MAX == ent->lost_ts);
669
670 reclaimed =
671 rtb_reclaim_frame(rtb, NGTCP2_RECLAIM_FLAG_ON_LOSS, conn, pktns, ent);
672 if (reclaimed < 0) {
673 return (int)reclaimed;
674 }
675 }
676
677 ent->flags |= NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED;
678 ent->lost_ts = ts;
679
680 ++rtb->num_lost_pkts;
681
682 ngtcp2_ksl_it_next(it);
683
684 return 0;
685 }
686
ngtcp2_rtb_add(ngtcp2_rtb * rtb,ngtcp2_rtb_entry * ent,ngtcp2_conn_stat * cstat)687 int ngtcp2_rtb_add(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
688 ngtcp2_conn_stat *cstat) {
689 int rv;
690
691 rv = ngtcp2_ksl_insert(&rtb->ents, NULL, &ent->hd.pkt_num, ent);
692 if (rv != 0) {
693 return rv;
694 }
695
696 rtb_on_add(rtb, ent, cstat);
697
698 return 0;
699 }
700
ngtcp2_rtb_head(ngtcp2_rtb * rtb)701 ngtcp2_ksl_it ngtcp2_rtb_head(ngtcp2_rtb *rtb) {
702 return ngtcp2_ksl_begin(&rtb->ents);
703 }
704
rtb_remove(ngtcp2_rtb * rtb,ngtcp2_ksl_it * it,ngtcp2_rtb_entry ** pent,ngtcp2_rtb_entry * ent,ngtcp2_conn_stat * cstat)705 static void rtb_remove(ngtcp2_rtb *rtb, ngtcp2_ksl_it *it,
706 ngtcp2_rtb_entry **pent, ngtcp2_rtb_entry *ent,
707 ngtcp2_conn_stat *cstat) {
708 int rv;
709 (void)rv;
710
711 rv = ngtcp2_ksl_remove_hint(&rtb->ents, it, it, &ent->hd.pkt_num);
712 assert(0 == rv);
713 rtb_on_remove(rtb, ent, cstat);
714
715 assert(ent->next == NULL);
716
717 ngtcp2_list_insert(ent, pent);
718 }
719
conn_ack_crypto_data(ngtcp2_conn * conn,ngtcp2_pktns * pktns,uint64_t datalen)720 static void conn_ack_crypto_data(ngtcp2_conn *conn, ngtcp2_pktns *pktns,
721 uint64_t datalen) {
722 ngtcp2_buf_chain **pbufchain, *bufchain;
723 size_t left;
724
725 for (pbufchain = &pktns->crypto.tx.data; *pbufchain;) {
726 left = ngtcp2_buf_len(&(*pbufchain)->buf);
727 if (left > datalen) {
728 (*pbufchain)->buf.pos += datalen;
729 return;
730 }
731
732 bufchain = *pbufchain;
733 *pbufchain = bufchain->next;
734
735 ngtcp2_mem_free(conn->mem, bufchain);
736
737 datalen -= left;
738
739 if (datalen == 0) {
740 return;
741 }
742 }
743
744 assert(datalen == 0);
745
746 return;
747 }
748
rtb_process_acked_pkt(ngtcp2_rtb * rtb,ngtcp2_rtb_entry * ent,ngtcp2_conn * conn)749 static int rtb_process_acked_pkt(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
750 ngtcp2_conn *conn) {
751 ngtcp2_frame_chain *frc;
752 uint64_t prev_stream_offset, stream_offset;
753 ngtcp2_strm *strm;
754 int rv;
755 uint64_t datalen;
756 ngtcp2_strm *crypto = rtb->crypto;
757 ngtcp2_pktns *pktns = NULL;
758
759 if ((ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) && conn->pmtud &&
760 conn->pmtud->tx_pkt_num <= ent->hd.pkt_num) {
761 ngtcp2_pmtud_probe_success(conn->pmtud, ent->pktlen);
762
763 conn->dcid.current.max_udp_payload_size =
764 ngtcp2_max(conn->dcid.current.max_udp_payload_size, ent->pktlen);
765
766 if (ngtcp2_pmtud_finished(conn->pmtud)) {
767 ngtcp2_conn_stop_pmtud(conn);
768 }
769 }
770
771 for (frc = ent->frc; frc; frc = frc->next) {
772 if (frc->binder) {
773 frc->binder->flags |= NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK;
774 }
775
776 switch (frc->fr.type) {
777 case NGTCP2_FRAME_STREAM:
778 strm = ngtcp2_conn_find_stream(conn, frc->fr.stream.stream_id);
779 if (strm == NULL) {
780 break;
781 }
782
783 strm->flags |= NGTCP2_STRM_FLAG_ANY_ACKED;
784
785 if (frc->fr.stream.fin) {
786 strm->flags |= NGTCP2_STRM_FLAG_FIN_ACKED;
787 }
788
789 prev_stream_offset = ngtcp2_strm_get_acked_offset(strm);
790 rv = ngtcp2_strm_ack_data(
791 strm, frc->fr.stream.offset,
792 ngtcp2_vec_len(frc->fr.stream.data, frc->fr.stream.datacnt));
793 if (rv != 0) {
794 return rv;
795 }
796
797 if (conn->callbacks.acked_stream_data_offset) {
798 stream_offset = ngtcp2_strm_get_acked_offset(strm);
799 datalen = stream_offset - prev_stream_offset;
800 if (datalen == 0 && !frc->fr.stream.fin) {
801 break;
802 }
803
804 rv = conn->callbacks.acked_stream_data_offset(
805 conn, strm->stream_id, prev_stream_offset, datalen, conn->user_data,
806 strm->stream_user_data);
807 if (rv != 0) {
808 return NGTCP2_ERR_CALLBACK_FAILURE;
809 }
810 }
811
812 rv = ngtcp2_conn_close_stream_if_shut_rdwr(conn, strm);
813 if (rv != 0) {
814 return rv;
815 }
816 break;
817 case NGTCP2_FRAME_CRYPTO:
818 prev_stream_offset = ngtcp2_strm_get_acked_offset(crypto);
819 rv = ngtcp2_strm_ack_data(
820 crypto, frc->fr.crypto.offset,
821 ngtcp2_vec_len(frc->fr.crypto.data, frc->fr.crypto.datacnt));
822 if (rv != 0) {
823 return rv;
824 }
825
826 stream_offset = ngtcp2_strm_get_acked_offset(crypto);
827 datalen = stream_offset - prev_stream_offset;
828 if (datalen == 0) {
829 break;
830 }
831
832 switch (rtb->pktns_id) {
833 case NGTCP2_PKTNS_ID_INITIAL:
834 pktns = conn->in_pktns;
835 break;
836 case NGTCP2_PKTNS_ID_HANDSHAKE:
837 pktns = conn->hs_pktns;
838 break;
839 case NGTCP2_PKTNS_ID_APPLICATION:
840 pktns = &conn->pktns;
841 break;
842 default:
843 assert(0);
844 }
845
846 conn_ack_crypto_data(conn, pktns, datalen);
847
848 break;
849 case NGTCP2_FRAME_RESET_STREAM:
850 strm = ngtcp2_conn_find_stream(conn, frc->fr.reset_stream.stream_id);
851 if (strm == NULL) {
852 break;
853 }
854 strm->flags |= NGTCP2_STRM_FLAG_RST_ACKED;
855 rv = ngtcp2_conn_close_stream_if_shut_rdwr(conn, strm);
856 if (rv != 0) {
857 return rv;
858 }
859 break;
860 case NGTCP2_FRAME_RETIRE_CONNECTION_ID:
861 ngtcp2_conn_untrack_retired_dcid_seq(conn,
862 frc->fr.retire_connection_id.seq);
863 break;
864 case NGTCP2_FRAME_DATAGRAM:
865 case NGTCP2_FRAME_DATAGRAM_LEN:
866 if (!conn->callbacks.ack_datagram) {
867 break;
868 }
869
870 rv = conn->callbacks.ack_datagram(conn, frc->fr.datagram.dgram_id,
871 conn->user_data);
872 if (rv != 0) {
873 return NGTCP2_ERR_CALLBACK_FAILURE;
874 }
875 break;
876 }
877 }
878 return 0;
879 }
880
rtb_on_pkt_acked(ngtcp2_rtb * rtb,ngtcp2_rtb_entry * ent,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)881 static void rtb_on_pkt_acked(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
882 ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts) {
883 ngtcp2_cc *cc = rtb->cc;
884 ngtcp2_cc_pkt pkt;
885
886 ngtcp2_rst_update_rate_sample(rtb->rst, ent, ts);
887
888 cc->on_pkt_acked(cc, cstat,
889 ngtcp2_cc_pkt_init(&pkt, ent->hd.pkt_num, ent->pktlen,
890 rtb->pktns_id, ent->ts, ent->rst.lost,
891 ent->rst.tx_in_flight,
892 ent->rst.is_app_limited),
893 ts);
894
895 if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_PROBE) &&
896 (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING)) {
897 cstat->pto_count = 0;
898 }
899 }
900
conn_verify_ecn(ngtcp2_conn * conn,ngtcp2_pktns * pktns,ngtcp2_cc * cc,ngtcp2_conn_stat * cstat,const ngtcp2_ack * fr,size_t ecn_acked,ngtcp2_tstamp largest_acked_sent_ts,ngtcp2_tstamp ts)901 static void conn_verify_ecn(ngtcp2_conn *conn, ngtcp2_pktns *pktns,
902 ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
903 const ngtcp2_ack *fr, size_t ecn_acked,
904 ngtcp2_tstamp largest_acked_sent_ts,
905 ngtcp2_tstamp ts) {
906 if (conn->tx.ecn.state == NGTCP2_ECN_STATE_FAILED) {
907 return;
908 }
909
910 if ((ecn_acked && fr->type == NGTCP2_FRAME_ACK) ||
911 (fr->type == NGTCP2_FRAME_ACK_ECN &&
912 (pktns->rx.ecn.ack.ect0 > fr->ecn.ect0 ||
913 pktns->rx.ecn.ack.ect1 > fr->ecn.ect1 ||
914 pktns->rx.ecn.ack.ce > fr->ecn.ce ||
915 (fr->ecn.ect0 - pktns->rx.ecn.ack.ect0) +
916 (fr->ecn.ce - pktns->rx.ecn.ack.ce) <
917 ecn_acked ||
918 fr->ecn.ect0 > pktns->tx.ecn.ect0 || fr->ecn.ect1))) {
919 ngtcp2_log_info(&conn->log, NGTCP2_LOG_EVENT_CON,
920 "path is not ECN capable");
921 conn->tx.ecn.state = NGTCP2_ECN_STATE_FAILED;
922 return;
923 }
924
925 if (conn->tx.ecn.state != NGTCP2_ECN_STATE_CAPABLE && ecn_acked) {
926 ngtcp2_log_info(&conn->log, NGTCP2_LOG_EVENT_CON, "path is ECN capable");
927 conn->tx.ecn.state = NGTCP2_ECN_STATE_CAPABLE;
928 }
929
930 if (fr->type == NGTCP2_FRAME_ACK_ECN) {
931 if (largest_acked_sent_ts != UINT64_MAX &&
932 fr->ecn.ce > pktns->rx.ecn.ack.ce) {
933 cc->congestion_event(cc, cstat, largest_acked_sent_ts, ts);
934 }
935
936 pktns->rx.ecn.ack.ect0 = fr->ecn.ect0;
937 pktns->rx.ecn.ack.ect1 = fr->ecn.ect1;
938 pktns->rx.ecn.ack.ce = fr->ecn.ce;
939 }
940 }
941
942 static int rtb_detect_lost_pkt(ngtcp2_rtb *rtb, uint64_t *ppkt_lost,
943 ngtcp2_conn *conn, ngtcp2_pktns *pktns,
944 ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts);
945
ngtcp2_rtb_recv_ack(ngtcp2_rtb * rtb,const ngtcp2_ack * fr,ngtcp2_conn_stat * cstat,ngtcp2_conn * conn,ngtcp2_pktns * pktns,ngtcp2_tstamp pkt_ts,ngtcp2_tstamp ts)946 ngtcp2_ssize ngtcp2_rtb_recv_ack(ngtcp2_rtb *rtb, const ngtcp2_ack *fr,
947 ngtcp2_conn_stat *cstat, ngtcp2_conn *conn,
948 ngtcp2_pktns *pktns, ngtcp2_tstamp pkt_ts,
949 ngtcp2_tstamp ts) {
950 ngtcp2_rtb_entry *ent;
951 int64_t largest_ack = fr->largest_ack, min_ack;
952 size_t i;
953 int rv;
954 ngtcp2_ksl_it it;
955 ngtcp2_ssize num_acked = 0;
956 ngtcp2_tstamp largest_pkt_sent_ts = UINT64_MAX;
957 ngtcp2_tstamp largest_acked_sent_ts = UINT64_MAX;
958 int64_t pkt_num;
959 ngtcp2_cc *cc = rtb->cc;
960 ngtcp2_rtb_entry *acked_ent = NULL;
961 int ack_eliciting_pkt_acked = 0;
962 size_t ecn_acked = 0;
963 int verify_ecn = 0;
964 ngtcp2_cc_ack cc_ack = {0};
965 size_t num_lost_pkts = rtb->num_lost_pkts - rtb->num_lost_pmtud_pkts;
966
967 cc_ack.prior_bytes_in_flight = cstat->bytes_in_flight;
968 cc_ack.rtt = UINT64_MAX;
969
970 if (conn && (conn->flags & NGTCP2_CONN_FLAG_KEY_UPDATE_NOT_CONFIRMED) &&
971 (conn->flags & NGTCP2_CONN_FLAG_KEY_UPDATE_INITIATOR) &&
972 largest_ack >= conn->pktns.crypto.tx.ckm->pkt_num) {
973 conn->flags &= (uint32_t) ~(NGTCP2_CONN_FLAG_KEY_UPDATE_NOT_CONFIRMED |
974 NGTCP2_CONN_FLAG_KEY_UPDATE_INITIATOR);
975 conn->crypto.key_update.confirmed_ts = ts;
976
977 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_CRY, "key update confirmed");
978 }
979
980 if (rtb->largest_acked_tx_pkt_num < largest_ack) {
981 rtb->largest_acked_tx_pkt_num = largest_ack;
982 verify_ecn = 1;
983 }
984
985 /* Assume that ngtcp2_pkt_validate_ack(fr) returns 0 */
986 it = ngtcp2_ksl_lower_bound(&rtb->ents, &largest_ack);
987 if (ngtcp2_ksl_it_end(&it)) {
988 if (conn && verify_ecn) {
989 conn_verify_ecn(conn, pktns, rtb->cc, cstat, fr, ecn_acked,
990 largest_acked_sent_ts, ts);
991 }
992 return 0;
993 }
994
995 min_ack = largest_ack - (int64_t)fr->first_ack_blklen;
996
997 for (; !ngtcp2_ksl_it_end(&it);) {
998 pkt_num = *(int64_t *)ngtcp2_ksl_it_key(&it);
999
1000 assert(pkt_num <= largest_ack);
1001
1002 if (pkt_num < min_ack) {
1003 break;
1004 }
1005
1006 ent = ngtcp2_ksl_it_get(&it);
1007
1008 if (largest_ack == pkt_num) {
1009 largest_pkt_sent_ts = ent->ts;
1010 }
1011
1012 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING) {
1013 ack_eliciting_pkt_acked = 1;
1014 }
1015
1016 rtb_remove(rtb, &it, &acked_ent, ent, cstat);
1017 ++num_acked;
1018 }
1019
1020 for (i = 0; i < fr->num_blks;) {
1021 largest_ack = min_ack - (int64_t)fr->blks[i].gap - 2;
1022 min_ack = largest_ack - (int64_t)fr->blks[i].blklen;
1023
1024 it = ngtcp2_ksl_lower_bound(&rtb->ents, &largest_ack);
1025 if (ngtcp2_ksl_it_end(&it)) {
1026 break;
1027 }
1028
1029 for (; !ngtcp2_ksl_it_end(&it);) {
1030 pkt_num = *(int64_t *)ngtcp2_ksl_it_key(&it);
1031 if (pkt_num < min_ack) {
1032 break;
1033 }
1034 ent = ngtcp2_ksl_it_get(&it);
1035
1036 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING) {
1037 ack_eliciting_pkt_acked = 1;
1038 }
1039
1040 rtb_remove(rtb, &it, &acked_ent, ent, cstat);
1041 ++num_acked;
1042 }
1043
1044 ++i;
1045 }
1046
1047 if (largest_pkt_sent_ts != UINT64_MAX && ack_eliciting_pkt_acked) {
1048 cc_ack.rtt = pkt_ts - largest_pkt_sent_ts;
1049
1050 rv = ngtcp2_conn_update_rtt(conn, cc_ack.rtt, fr->ack_delay_unscaled, ts);
1051 if (rv == 0 && cc->new_rtt_sample) {
1052 cc->new_rtt_sample(cc, cstat, ts);
1053 }
1054 }
1055
1056 if (conn) {
1057 for (ent = acked_ent; ent; ent = acked_ent) {
1058 if (ent->hd.pkt_num >= pktns->tx.ecn.start_pkt_num &&
1059 (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ECN)) {
1060 ++ecn_acked;
1061 }
1062
1063 assert(largest_acked_sent_ts == UINT64_MAX ||
1064 largest_acked_sent_ts <= ent->ts);
1065
1066 largest_acked_sent_ts = ent->ts;
1067
1068 rv = rtb_process_acked_pkt(rtb, ent, conn);
1069 if (rv != 0) {
1070 goto fail;
1071 }
1072
1073 if (ent->hd.pkt_num >= rtb->cc_pkt_num) {
1074 assert(cc_ack.pkt_delivered <= ent->rst.delivered);
1075
1076 cc_ack.bytes_delivered += ent->pktlen;
1077 cc_ack.pkt_delivered = ent->rst.delivered;
1078 }
1079
1080 rtb_on_pkt_acked(rtb, ent, cstat, ts);
1081 acked_ent = ent->next;
1082 ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc,
1083 rtb->frc_objalloc, rtb->mem);
1084 }
1085
1086 if (verify_ecn) {
1087 conn_verify_ecn(conn, pktns, rtb->cc, cstat, fr, ecn_acked,
1088 largest_acked_sent_ts, ts);
1089 }
1090 } else {
1091 /* For unit tests */
1092 for (ent = acked_ent; ent; ent = acked_ent) {
1093 rtb_on_pkt_acked(rtb, ent, cstat, ts);
1094 acked_ent = ent->next;
1095 ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc,
1096 rtb->frc_objalloc, rtb->mem);
1097 }
1098 }
1099
1100 if (rtb->cc->on_spurious_congestion && num_lost_pkts &&
1101 rtb->num_lost_pkts - rtb->num_lost_pmtud_pkts == 0) {
1102 rtb->cc->on_spurious_congestion(cc, cstat, ts);
1103 }
1104
1105 ngtcp2_rst_on_ack_recv(rtb->rst, cstat, cc_ack.pkt_delivered);
1106
1107 if (conn && num_acked > 0) {
1108 rv = rtb_detect_lost_pkt(rtb, &cc_ack.bytes_lost, conn, pktns, cstat, ts);
1109 if (rv != 0) {
1110 return rv;
1111 }
1112 }
1113
1114 rtb->rst->lost += cc_ack.bytes_lost;
1115
1116 cc_ack.largest_acked_sent_ts = largest_acked_sent_ts;
1117 cc->on_ack_recv(cc, cstat, &cc_ack, ts);
1118
1119 return num_acked;
1120
1121 fail:
1122 for (ent = acked_ent; ent; ent = acked_ent) {
1123 acked_ent = ent->next;
1124 ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc,
1125 rtb->frc_objalloc, rtb->mem);
1126 }
1127
1128 return rv;
1129 }
1130
rtb_pkt_lost(ngtcp2_rtb * rtb,ngtcp2_conn_stat * cstat,const ngtcp2_rtb_entry * ent,ngtcp2_duration loss_delay,size_t pkt_thres,ngtcp2_tstamp ts)1131 static int rtb_pkt_lost(ngtcp2_rtb *rtb, ngtcp2_conn_stat *cstat,
1132 const ngtcp2_rtb_entry *ent, ngtcp2_duration loss_delay,
1133 size_t pkt_thres, ngtcp2_tstamp ts) {
1134 ngtcp2_tstamp loss_time;
1135
1136 if (ent->ts + loss_delay <= ts ||
1137 rtb->largest_acked_tx_pkt_num >= ent->hd.pkt_num + (int64_t)pkt_thres) {
1138 return 1;
1139 }
1140
1141 loss_time = cstat->loss_time[rtb->pktns_id];
1142
1143 if (loss_time == UINT64_MAX) {
1144 loss_time = ent->ts + loss_delay;
1145 } else {
1146 loss_time = ngtcp2_min(loss_time, ent->ts + loss_delay);
1147 }
1148
1149 cstat->loss_time[rtb->pktns_id] = loss_time;
1150
1151 return 0;
1152 }
1153
1154 /*
1155 * rtb_compute_pkt_loss_delay computes loss delay.
1156 */
compute_pkt_loss_delay(const ngtcp2_conn_stat * cstat)1157 static ngtcp2_duration compute_pkt_loss_delay(const ngtcp2_conn_stat *cstat) {
1158 /* 9/8 is kTimeThreshold */
1159 ngtcp2_duration loss_delay =
1160 ngtcp2_max(cstat->latest_rtt, cstat->smoothed_rtt) * 9 / 8;
1161 return ngtcp2_max(loss_delay, NGTCP2_GRANULARITY);
1162 }
1163
1164 /*
1165 * conn_all_ecn_pkt_lost returns nonzero if all ECN QUIC packets are
1166 * lost during validation period.
1167 */
conn_all_ecn_pkt_lost(ngtcp2_conn * conn)1168 static int conn_all_ecn_pkt_lost(ngtcp2_conn *conn) {
1169 ngtcp2_pktns *in_pktns = conn->in_pktns;
1170 ngtcp2_pktns *hs_pktns = conn->hs_pktns;
1171 ngtcp2_pktns *pktns = &conn->pktns;
1172
1173 return (!in_pktns || in_pktns->tx.ecn.validation_pkt_sent ==
1174 in_pktns->tx.ecn.validation_pkt_lost) &&
1175 (!hs_pktns || hs_pktns->tx.ecn.validation_pkt_sent ==
1176 hs_pktns->tx.ecn.validation_pkt_lost) &&
1177 pktns->tx.ecn.validation_pkt_sent == pktns->tx.ecn.validation_pkt_lost;
1178 }
1179
rtb_detect_lost_pkt(ngtcp2_rtb * rtb,uint64_t * ppkt_lost,ngtcp2_conn * conn,ngtcp2_pktns * pktns,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1180 static int rtb_detect_lost_pkt(ngtcp2_rtb *rtb, uint64_t *ppkt_lost,
1181 ngtcp2_conn *conn, ngtcp2_pktns *pktns,
1182 ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts) {
1183 ngtcp2_rtb_entry *ent;
1184 ngtcp2_duration loss_delay;
1185 ngtcp2_ksl_it it;
1186 ngtcp2_tstamp latest_ts, oldest_ts;
1187 int64_t last_lost_pkt_num;
1188 ngtcp2_duration loss_window, congestion_period;
1189 ngtcp2_cc *cc = rtb->cc;
1190 int rv;
1191 uint64_t pkt_thres =
1192 rtb->cc_bytes_in_flight / cstat->max_udp_payload_size / 2;
1193 size_t ecn_pkt_lost = 0;
1194 ngtcp2_tstamp start_ts;
1195 ngtcp2_duration pto = ngtcp2_conn_compute_pto(conn, pktns);
1196 uint64_t bytes_lost = 0;
1197 ngtcp2_duration max_ack_delay;
1198
1199 pkt_thres = ngtcp2_max(pkt_thres, NGTCP2_PKT_THRESHOLD);
1200 pkt_thres = ngtcp2_min(pkt_thres, 256);
1201 cstat->loss_time[rtb->pktns_id] = UINT64_MAX;
1202 loss_delay = compute_pkt_loss_delay(cstat);
1203
1204 it = ngtcp2_ksl_lower_bound(&rtb->ents, &rtb->largest_acked_tx_pkt_num);
1205 for (; !ngtcp2_ksl_it_end(&it); ngtcp2_ksl_it_next(&it)) {
1206 ent = ngtcp2_ksl_it_get(&it);
1207
1208 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED) {
1209 break;
1210 }
1211
1212 if (rtb_pkt_lost(rtb, cstat, ent, loss_delay, (size_t)pkt_thres, ts)) {
1213 /* All entries from ent are considered to be lost. */
1214 latest_ts = oldest_ts = ent->ts;
1215 last_lost_pkt_num = ent->hd.pkt_num;
1216 max_ack_delay = conn->remote.transport_params
1217 ? conn->remote.transport_params->max_ack_delay
1218 : 0;
1219
1220 congestion_period =
1221 (cstat->smoothed_rtt +
1222 ngtcp2_max(4 * cstat->rttvar, NGTCP2_GRANULARITY) + max_ack_delay) *
1223 NGTCP2_PERSISTENT_CONGESTION_THRESHOLD;
1224
1225 start_ts = ngtcp2_max(rtb->persistent_congestion_start_ts,
1226 cstat->first_rtt_sample_ts);
1227
1228 for (; !ngtcp2_ksl_it_end(&it);) {
1229 ent = ngtcp2_ksl_it_get(&it);
1230
1231 if (last_lost_pkt_num == ent->hd.pkt_num + 1 && ent->ts >= start_ts) {
1232 last_lost_pkt_num = ent->hd.pkt_num;
1233 oldest_ts = ent->ts;
1234 } else {
1235 last_lost_pkt_num = -1;
1236 }
1237
1238 if ((ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED)) {
1239 if (rtb->pktns_id != NGTCP2_PKTNS_ID_APPLICATION ||
1240 last_lost_pkt_num == -1 ||
1241 latest_ts - oldest_ts >= congestion_period) {
1242 break;
1243 }
1244 ngtcp2_ksl_it_next(&it);
1245 continue;
1246 }
1247
1248 if (ent->hd.pkt_num >= pktns->tx.ecn.start_pkt_num &&
1249 (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ECN)) {
1250 ++ecn_pkt_lost;
1251 }
1252
1253 bytes_lost += rtb_on_remove(rtb, ent, cstat);
1254 rv = rtb_on_pkt_lost(rtb, &it, ent, cstat, conn, pktns, ts);
1255 if (rv != 0) {
1256 return rv;
1257 }
1258 }
1259
1260 /* If only PMTUD packets are lost, do not trigger congestion
1261 event. */
1262 if (bytes_lost == 0) {
1263 break;
1264 }
1265
1266 switch (conn->tx.ecn.state) {
1267 case NGTCP2_ECN_STATE_TESTING:
1268 if (conn->tx.ecn.validation_start_ts == UINT64_MAX) {
1269 break;
1270 }
1271 if (ts - conn->tx.ecn.validation_start_ts < 3 * pto) {
1272 pktns->tx.ecn.validation_pkt_lost += ecn_pkt_lost;
1273 assert(pktns->tx.ecn.validation_pkt_sent >=
1274 pktns->tx.ecn.validation_pkt_lost);
1275 break;
1276 }
1277 conn->tx.ecn.state = NGTCP2_ECN_STATE_UNKNOWN;
1278 /* fall through */
1279 case NGTCP2_ECN_STATE_UNKNOWN:
1280 pktns->tx.ecn.validation_pkt_lost += ecn_pkt_lost;
1281 assert(pktns->tx.ecn.validation_pkt_sent >=
1282 pktns->tx.ecn.validation_pkt_lost);
1283 if (conn_all_ecn_pkt_lost(conn)) {
1284 conn->tx.ecn.state = NGTCP2_ECN_STATE_FAILED;
1285 }
1286 break;
1287 default:
1288 break;
1289 }
1290
1291 cc->congestion_event(cc, cstat, latest_ts, ts);
1292
1293 loss_window = latest_ts - oldest_ts;
1294 /* Persistent congestion situation is only evaluated for app
1295 * packet number space and for the packets sent after handshake
1296 * is confirmed. During handshake, there is not much packets
1297 * sent and also people seem to do lots of effort not to trigger
1298 * persistent congestion there, then it is a lot easier to just
1299 * not enable it during handshake.
1300 */
1301 if (rtb->pktns_id == NGTCP2_PKTNS_ID_APPLICATION && loss_window > 0) {
1302 if (loss_window >= congestion_period) {
1303 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1304 "persistent congestion loss_window=%" PRIu64
1305 " congestion_period=%" PRIu64,
1306 loss_window, congestion_period);
1307
1308 /* Reset min_rtt, srtt, and rttvar here. Next new RTT
1309 sample will be used to recalculate these values. */
1310 cstat->min_rtt = UINT64_MAX;
1311 cstat->smoothed_rtt = conn->local.settings.initial_rtt;
1312 cstat->rttvar = conn->local.settings.initial_rtt / 2;
1313 cstat->first_rtt_sample_ts = UINT64_MAX;
1314
1315 cc->on_persistent_congestion(cc, cstat, ts);
1316 }
1317 }
1318
1319 break;
1320 }
1321 }
1322
1323 ngtcp2_rtb_remove_excessive_lost_pkt(rtb, (size_t)pkt_thres);
1324
1325 if (ppkt_lost) {
1326 *ppkt_lost = bytes_lost;
1327 }
1328
1329 return 0;
1330 }
1331
ngtcp2_rtb_detect_lost_pkt(ngtcp2_rtb * rtb,ngtcp2_conn * conn,ngtcp2_pktns * pktns,ngtcp2_conn_stat * cstat,ngtcp2_tstamp ts)1332 int ngtcp2_rtb_detect_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
1333 ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat,
1334 ngtcp2_tstamp ts) {
1335 return rtb_detect_lost_pkt(rtb, /* ppkt_lost = */ NULL, conn, pktns, cstat,
1336 ts);
1337 }
1338
ngtcp2_rtb_remove_excessive_lost_pkt(ngtcp2_rtb * rtb,size_t n)1339 void ngtcp2_rtb_remove_excessive_lost_pkt(ngtcp2_rtb *rtb, size_t n) {
1340 ngtcp2_ksl_it it = ngtcp2_ksl_end(&rtb->ents);
1341 ngtcp2_rtb_entry *ent;
1342 int rv;
1343 (void)rv;
1344
1345 for (; rtb->num_lost_pkts > n;) {
1346 assert(ngtcp2_ksl_it_end(&it));
1347 ngtcp2_ksl_it_prev(&it);
1348 ent = ngtcp2_ksl_it_get(&it);
1349
1350 assert(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED);
1351
1352 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1353 "removing stale lost pkn=%" PRId64, ent->hd.pkt_num);
1354
1355 --rtb->num_lost_pkts;
1356
1357 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) {
1358 --rtb->num_lost_pmtud_pkts;
1359 }
1360
1361 rv = ngtcp2_ksl_remove_hint(&rtb->ents, &it, &it, &ent->hd.pkt_num);
1362 assert(0 == rv);
1363 ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc,
1364 rtb->frc_objalloc, rtb->mem);
1365 }
1366 }
1367
ngtcp2_rtb_remove_expired_lost_pkt(ngtcp2_rtb * rtb,ngtcp2_duration pto,ngtcp2_tstamp ts)1368 void ngtcp2_rtb_remove_expired_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_duration pto,
1369 ngtcp2_tstamp ts) {
1370 ngtcp2_ksl_it it;
1371 ngtcp2_rtb_entry *ent;
1372 int rv;
1373 (void)rv;
1374
1375 if (ngtcp2_ksl_len(&rtb->ents) == 0) {
1376 return;
1377 }
1378
1379 it = ngtcp2_ksl_end(&rtb->ents);
1380
1381 for (;;) {
1382 assert(ngtcp2_ksl_it_end(&it));
1383
1384 ngtcp2_ksl_it_prev(&it);
1385 ent = ngtcp2_ksl_it_get(&it);
1386
1387 if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED) ||
1388 ts - ent->lost_ts < pto) {
1389 return;
1390 }
1391
1392 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1393 "removing stale lost pkn=%" PRId64, ent->hd.pkt_num);
1394
1395 --rtb->num_lost_pkts;
1396
1397 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) {
1398 --rtb->num_lost_pmtud_pkts;
1399 }
1400
1401 rv = ngtcp2_ksl_remove_hint(&rtb->ents, &it, &it, &ent->hd.pkt_num);
1402 assert(0 == rv);
1403 ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc,
1404 rtb->frc_objalloc, rtb->mem);
1405
1406 if (ngtcp2_ksl_len(&rtb->ents) == 0) {
1407 return;
1408 }
1409 }
1410 }
1411
ngtcp2_rtb_lost_pkt_ts(ngtcp2_rtb * rtb)1412 ngtcp2_tstamp ngtcp2_rtb_lost_pkt_ts(ngtcp2_rtb *rtb) {
1413 ngtcp2_ksl_it it;
1414 ngtcp2_rtb_entry *ent;
1415
1416 if (ngtcp2_ksl_len(&rtb->ents) == 0) {
1417 return UINT64_MAX;
1418 }
1419
1420 it = ngtcp2_ksl_end(&rtb->ents);
1421 ngtcp2_ksl_it_prev(&it);
1422 ent = ngtcp2_ksl_it_get(&it);
1423
1424 if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED)) {
1425 return UINT64_MAX;
1426 }
1427
1428 return ent->lost_ts;
1429 }
1430
rtb_on_pkt_lost_resched_move(ngtcp2_rtb * rtb,ngtcp2_conn * conn,ngtcp2_pktns * pktns,ngtcp2_rtb_entry * ent)1431 static int rtb_on_pkt_lost_resched_move(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
1432 ngtcp2_pktns *pktns,
1433 ngtcp2_rtb_entry *ent) {
1434 ngtcp2_frame_chain **pfrc, *frc;
1435 ngtcp2_stream *sfr;
1436 ngtcp2_strm *strm;
1437 int rv;
1438 int streamfrq_empty;
1439
1440 ngtcp2_log_pkt_lost(rtb->log, ent->hd.pkt_num, ent->hd.type, ent->hd.flags,
1441 ent->ts);
1442
1443 if (rtb->qlog) {
1444 ngtcp2_qlog_pkt_lost(rtb->qlog, ent);
1445 }
1446
1447 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PROBE) {
1448 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1449 "pkn=%" PRId64
1450 " is a probe packet, no retransmission is necessary",
1451 ent->hd.pkt_num);
1452 return 0;
1453 }
1454
1455 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) {
1456 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1457 "pkn=%" PRId64
1458 " is a PMTUD probe packet, no retransmission is necessary",
1459 ent->hd.pkt_num);
1460 return 0;
1461 }
1462
1463 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED) {
1464 --rtb->num_lost_pkts;
1465
1466 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PMTUD_PROBE) {
1467 --rtb->num_lost_pmtud_pkts;
1468 }
1469
1470 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1471 "pkn=%" PRId64
1472 " was declared lost and has already been retransmitted",
1473 ent->hd.pkt_num);
1474 return 0;
1475 }
1476
1477 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED) {
1478 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1479 "pkn=%" PRId64 " has already been reclaimed on PTO",
1480 ent->hd.pkt_num);
1481 return 0;
1482 }
1483
1484 if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE) &&
1485 (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_DATAGRAM) ||
1486 !conn->callbacks.lost_datagram)) {
1487 /* PADDING only (or PADDING + ACK ) packets will have NULL
1488 ent->frc. */
1489 return 0;
1490 }
1491
1492 pfrc = &ent->frc;
1493
1494 for (; *pfrc;) {
1495 switch ((*pfrc)->fr.type) {
1496 case NGTCP2_FRAME_STREAM:
1497 frc = *pfrc;
1498
1499 *pfrc = frc->next;
1500 frc->next = NULL;
1501 sfr = &frc->fr.stream;
1502
1503 strm = ngtcp2_conn_find_stream(conn, sfr->stream_id);
1504 if (!strm) {
1505 ngtcp2_frame_chain_objalloc_del(frc, rtb->frc_objalloc, rtb->mem);
1506 break;
1507 }
1508 streamfrq_empty = ngtcp2_strm_streamfrq_empty(strm);
1509 rv = ngtcp2_strm_streamfrq_push(strm, frc);
1510 if (rv != 0) {
1511 ngtcp2_frame_chain_objalloc_del(frc, rtb->frc_objalloc, rtb->mem);
1512 return rv;
1513 }
1514 if (!ngtcp2_strm_is_tx_queued(strm)) {
1515 strm->cycle = ngtcp2_conn_tx_strmq_first_cycle(conn);
1516 rv = ngtcp2_conn_tx_strmq_push(conn, strm);
1517 if (rv != 0) {
1518 return rv;
1519 }
1520 }
1521 if (streamfrq_empty) {
1522 ++conn->tx.strmq_nretrans;
1523 }
1524 break;
1525 case NGTCP2_FRAME_CRYPTO:
1526 frc = *pfrc;
1527
1528 *pfrc = frc->next;
1529 frc->next = NULL;
1530
1531 rv = ngtcp2_ksl_insert(&pktns->crypto.tx.frq, NULL,
1532 &frc->fr.crypto.offset, frc);
1533 if (rv != 0) {
1534 assert(ngtcp2_err_is_fatal(rv));
1535 ngtcp2_frame_chain_objalloc_del(frc, rtb->frc_objalloc, rtb->mem);
1536 return rv;
1537 }
1538 break;
1539 case NGTCP2_FRAME_DATAGRAM:
1540 case NGTCP2_FRAME_DATAGRAM_LEN:
1541 frc = *pfrc;
1542
1543 if (conn->callbacks.lost_datagram) {
1544 rv = conn->callbacks.lost_datagram(conn, frc->fr.datagram.dgram_id,
1545 conn->user_data);
1546 if (rv != 0) {
1547 return NGTCP2_ERR_CALLBACK_FAILURE;
1548 }
1549 }
1550
1551 *pfrc = (*pfrc)->next;
1552
1553 ngtcp2_frame_chain_objalloc_del(frc, rtb->frc_objalloc, rtb->mem);
1554 break;
1555 default:
1556 pfrc = &(*pfrc)->next;
1557 }
1558 }
1559
1560 *pfrc = pktns->tx.frq;
1561 pktns->tx.frq = ent->frc;
1562 ent->frc = NULL;
1563
1564 return 0;
1565 }
1566
ngtcp2_rtb_remove_all(ngtcp2_rtb * rtb,ngtcp2_conn * conn,ngtcp2_pktns * pktns,ngtcp2_conn_stat * cstat)1567 int ngtcp2_rtb_remove_all(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
1568 ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat) {
1569 ngtcp2_rtb_entry *ent;
1570 ngtcp2_ksl_it it;
1571 int rv;
1572
1573 it = ngtcp2_ksl_begin(&rtb->ents);
1574
1575 for (; !ngtcp2_ksl_it_end(&it);) {
1576 ent = ngtcp2_ksl_it_get(&it);
1577
1578 rtb_on_remove(rtb, ent, cstat);
1579 rv = ngtcp2_ksl_remove_hint(&rtb->ents, &it, &it, &ent->hd.pkt_num);
1580 assert(0 == rv);
1581
1582 rv = rtb_on_pkt_lost_resched_move(rtb, conn, pktns, ent);
1583 ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc,
1584 rtb->frc_objalloc, rtb->mem);
1585 if (rv != 0) {
1586 return rv;
1587 }
1588 }
1589
1590 return 0;
1591 }
1592
ngtcp2_rtb_remove_early_data(ngtcp2_rtb * rtb,ngtcp2_conn_stat * cstat)1593 void ngtcp2_rtb_remove_early_data(ngtcp2_rtb *rtb, ngtcp2_conn_stat *cstat) {
1594 ngtcp2_rtb_entry *ent;
1595 ngtcp2_ksl_it it;
1596 int rv;
1597 (void)rv;
1598
1599 it = ngtcp2_ksl_begin(&rtb->ents);
1600
1601 for (; !ngtcp2_ksl_it_end(&it);) {
1602 ent = ngtcp2_ksl_it_get(&it);
1603
1604 if (ent->hd.type != NGTCP2_PKT_0RTT) {
1605 ngtcp2_ksl_it_next(&it);
1606 continue;
1607 }
1608
1609 rtb_on_remove(rtb, ent, cstat);
1610 rv = ngtcp2_ksl_remove_hint(&rtb->ents, &it, &it, &ent->hd.pkt_num);
1611 assert(0 == rv);
1612
1613 ngtcp2_rtb_entry_objalloc_del(ent, rtb->rtb_entry_objalloc,
1614 rtb->frc_objalloc, rtb->mem);
1615 }
1616 }
1617
ngtcp2_rtb_empty(ngtcp2_rtb * rtb)1618 int ngtcp2_rtb_empty(ngtcp2_rtb *rtb) {
1619 return ngtcp2_ksl_len(&rtb->ents) == 0;
1620 }
1621
ngtcp2_rtb_reset_cc_state(ngtcp2_rtb * rtb,int64_t cc_pkt_num)1622 void ngtcp2_rtb_reset_cc_state(ngtcp2_rtb *rtb, int64_t cc_pkt_num) {
1623 rtb->cc_pkt_num = cc_pkt_num;
1624 rtb->cc_bytes_in_flight = 0;
1625 }
1626
ngtcp2_rtb_reclaim_on_pto(ngtcp2_rtb * rtb,ngtcp2_conn * conn,ngtcp2_pktns * pktns,size_t num_pkts)1627 ngtcp2_ssize ngtcp2_rtb_reclaim_on_pto(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
1628 ngtcp2_pktns *pktns, size_t num_pkts) {
1629 ngtcp2_ksl_it it;
1630 ngtcp2_rtb_entry *ent;
1631 ngtcp2_ssize reclaimed;
1632 size_t atmost = num_pkts;
1633
1634 it = ngtcp2_ksl_end(&rtb->ents);
1635 for (; !ngtcp2_ksl_it_begin(&it) && num_pkts >= 1;) {
1636 ngtcp2_ksl_it_prev(&it);
1637 ent = ngtcp2_ksl_it_get(&it);
1638
1639 if ((ent->flags & (NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED |
1640 NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED)) ||
1641 !(ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE)) {
1642 continue;
1643 }
1644
1645 assert(ent->frc);
1646
1647 reclaimed =
1648 rtb_reclaim_frame(rtb, NGTCP2_RECLAIM_FLAG_NONE, conn, pktns, ent);
1649 if (reclaimed < 0) {
1650 return reclaimed;
1651 }
1652
1653 /* Mark reclaimed even if reclaimed == 0 so that we can skip it in
1654 the next run. */
1655 ent->flags |= NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED;
1656
1657 assert(rtb->num_retransmittable);
1658 --rtb->num_retransmittable;
1659
1660 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING) {
1661 ent->flags &= (uint16_t)~NGTCP2_RTB_ENTRY_FLAG_PTO_ELICITING;
1662 assert(rtb->num_pto_eliciting);
1663 --rtb->num_pto_eliciting;
1664 }
1665
1666 if (reclaimed) {
1667 --num_pkts;
1668 }
1669 }
1670
1671 return (ngtcp2_ssize)(atmost - num_pkts);
1672 }
1673