Bug Summary

File:out/../deps/ngtcp2/ngtcp2/lib/ngtcp2_rtb.c
Warning:line 672, column 7
Dereference of null pointer

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name ngtcp2_rtb.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/maurizio/node-v18.6.0/out -resource-dir /usr/local/lib/clang/16.0.0 -D _U_= -D V8_DEPRECATION_WARNINGS -D V8_IMMINENT_DEPRECATION_WARNINGS -D _GLIBCXX_USE_CXX11_ABI=1 -D NODE_OPENSSL_CONF_NAME=nodejs_conf -D NODE_OPENSSL_HAS_QUIC -D __STDC_FORMAT_MACROS -D OPENSSL_NO_PINSHARED -D OPENSSL_THREADS -D BUILDING_NGTCP2 -D NGTCP2_STATICLIB -D HAVE_ARPA_INET_H -D HAVE_NETINET_IN_H -D NDEBUG -D OPENSSL_USE_NODELETE -D L_ENDIAN -D OPENSSL_BUILDING_OPENSSL -D AES_ASM -D BSAES_ASM -D CMLL_ASM -D ECP_NISTZ256_ASM -D GHASH_ASM -D KECCAK1600_ASM -D MD5_ASM -D OPENSSL_BN_ASM_GF2m -D OPENSSL_BN_ASM_MONT -D OPENSSL_BN_ASM_MONT5 -D OPENSSL_CPUID_OBJ -D OPENSSL_IA32_SSE2 -D PADLOCK_ASM -D POLY1305_ASM -D SHA1_ASM -D SHA256_ASM -D SHA512_ASM -D VPAES_ASM -D WHIRLPOOL_ASM -D X25519_ASM -D OPENSSL_PIC -I ../deps/ngtcp2 -I ../deps/ngtcp2/ngtcp2/lib/includes -I ../deps/ngtcp2/ngtcp2/crypto/includes -I ../deps/ngtcp2/ngtcp2/lib -I ../deps/ngtcp2/ngtcp2/crypto -I ../deps/openssl/openssl/include -I ../deps/openssl/openssl/crypto/include -I ../deps/openssl/config/archs/linux-x86_64/asm/include -I ../deps/openssl/config/archs/linux-x86_64/asm -internal-isystem /usr/local/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../x86_64-redhat-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Wno-unused-parameter -fdebug-compilation-dir=/home/maurizio/node-v18.6.0/out -ferror-limit 19 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-08-22-142216-507842-1 -x c ../deps/ngtcp2/ngtcp2/lib/ngtcp2_rtb.c
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
38int 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((void*)0)) {
41 return NGTCP2_ERR_NOMEM-501;
42 }
43
44 ngtcp2_frame_chain_init(*pfrc);
45
46 return 0;
47}
48
49int ngtcp2_frame_chain_extralen_new(ngtcp2_frame_chain **pfrc, size_t extralen,
50 const ngtcp2_mem *mem) {
51 *pfrc = ngtcp2_mem_malloc(mem, sizeof(ngtcp2_frame_chain) + extralen);
52 if (*pfrc == NULL((void*)0)) {
53 return NGTCP2_ERR_NOMEM-501;
54 }
55
56 ngtcp2_frame_chain_init(*pfrc);
57
58 return 0;
59}
60
61int ngtcp2_frame_chain_stream_datacnt_new(ngtcp2_frame_chain **pfrc,
62 size_t datacnt,
63 const ngtcp2_mem *mem) {
64 size_t need = sizeof(ngtcp2_vec) * (datacnt - 1);
65 size_t avail = sizeof(ngtcp2_frame) - sizeof(ngtcp2_stream);
66
67 if (datacnt > 0 && need > avail) {
68 return ngtcp2_frame_chain_extralen_new(pfrc, need - avail, mem);
69 }
70
71 return ngtcp2_frame_chain_new(pfrc, mem);
72}
73
74int ngtcp2_frame_chain_crypto_datacnt_new(ngtcp2_frame_chain **pfrc,
75 size_t datacnt,
76 const ngtcp2_mem *mem) {
77 size_t need = sizeof(ngtcp2_vec) * (datacnt - 1);
78 size_t avail = sizeof(ngtcp2_frame) - sizeof(ngtcp2_crypto);
79
80 if (datacnt > 0 && need > avail) {
81 return ngtcp2_frame_chain_extralen_new(pfrc, need - avail, mem);
82 }
83
84 return ngtcp2_frame_chain_new(pfrc, mem);
85}
86
87int ngtcp2_frame_chain_new_token_new(ngtcp2_frame_chain **pfrc,
88 const ngtcp2_vec *token,
89 const ngtcp2_mem *mem) {
90 size_t avail = sizeof(ngtcp2_frame) - sizeof(ngtcp2_new_token);
91 int rv;
92 uint8_t *p;
93 ngtcp2_frame *fr;
94
95 if (token->len > avail) {
96 rv = ngtcp2_frame_chain_extralen_new(pfrc, token->len - avail, mem);
97 } else {
98 rv = ngtcp2_frame_chain_new(pfrc, mem);
99 }
100 if (rv != 0) {
101 return rv;
102 }
103
104 fr = &(*pfrc)->fr;
105 fr->type = NGTCP2_FRAME_NEW_TOKEN;
106
107 p = (uint8_t *)(*pfrc) + sizeof(ngtcp2_new_token);
108 memcpy(p, token->base, token->len);
109
110 ngtcp2_vec_init(&fr->new_token.token, p, token->len);
111
112 return 0;
113}
114
115void ngtcp2_frame_chain_del(ngtcp2_frame_chain *frc, const ngtcp2_mem *mem) {
116 ngtcp2_frame_chain_binder *binder;
117
118 if (frc == NULL((void*)0)) {
119 return;
120 }
121
122 binder = frc->binder;
123 if (binder && --binder->refcount == 0) {
124 ngtcp2_mem_free(mem, binder);
125 }
126
127 ngtcp2_mem_free(mem, frc);
128}
129
130void ngtcp2_frame_chain_init(ngtcp2_frame_chain *frc) {
131 frc->next = NULL((void*)0);
132 frc->binder = NULL((void*)0);
133}
134
135void ngtcp2_frame_chain_list_del(ngtcp2_frame_chain *frc,
136 const ngtcp2_mem *mem) {
137 ngtcp2_frame_chain *next;
138
139 for (; frc;) {
140 next = frc->next;
141 ngtcp2_frame_chain_del(frc, mem);
142 frc = next;
143 }
144}
145
146int ngtcp2_frame_chain_binder_new(ngtcp2_frame_chain_binder **pbinder,
147 const ngtcp2_mem *mem) {
148 *pbinder = ngtcp2_mem_calloc(mem, 1, sizeof(ngtcp2_frame_chain_binder));
149 if (*pbinder == NULL((void*)0)) {
150 return NGTCP2_ERR_NOMEM-501;
151 }
152
153 return 0;
154}
155
156int ngtcp2_bind_frame_chains(ngtcp2_frame_chain *a, ngtcp2_frame_chain *b,
157 const ngtcp2_mem *mem) {
158 ngtcp2_frame_chain_binder *binder;
159 int rv;
160
161 assert(b->binder == NULL)((void) (0));
162
163 if (a->binder == NULL((void*)0)) {
164 rv = ngtcp2_frame_chain_binder_new(&binder, mem);
165 if (rv != 0) {
166 return rv;
167 }
168
169 a->binder = binder;
170 ++a->binder->refcount;
171 }
172
173 b->binder = a->binder;
174 ++b->binder->refcount;
175
176 return 0;
177}
178
179int ngtcp2_rtb_entry_new(ngtcp2_rtb_entry **pent, const ngtcp2_pkt_hd *hd,
180 ngtcp2_frame_chain *frc, ngtcp2_tstamp ts,
181 size_t pktlen, uint8_t flags, const ngtcp2_mem *mem) {
182 (*pent) = ngtcp2_mem_calloc(mem, 1, sizeof(ngtcp2_rtb_entry));
183 if (*pent == NULL((void*)0)) {
184 return NGTCP2_ERR_NOMEM-501;
185 }
186
187 (*pent)->hd.pkt_num = hd->pkt_num;
188 (*pent)->hd.type = hd->type;
189 (*pent)->hd.flags = hd->flags;
190 (*pent)->frc = frc;
191 (*pent)->ts = ts;
192 (*pent)->lost_ts = UINT64_MAX(18446744073709551615UL);
193 (*pent)->pktlen = pktlen;
194 (*pent)->flags = flags;
195 (*pent)->next = NULL((void*)0);
196
197 return 0;
198}
199
200void ngtcp2_rtb_entry_del(ngtcp2_rtb_entry *ent, const ngtcp2_mem *mem) {
201 if (ent == NULL((void*)0)) {
202 return;
203 }
204
205 ngtcp2_frame_chain_list_del(ent->frc, mem);
206
207 ngtcp2_mem_free(mem, ent);
208}
209
210static int greater(const ngtcp2_ksl_key *lhs, const ngtcp2_ksl_key *rhs) {
211 return *(int64_t *)lhs > *(int64_t *)rhs;
212}
213
214void ngtcp2_rtb_init(ngtcp2_rtb *rtb, ngtcp2_pktns_id pktns_id,
215 ngtcp2_strm *crypto, ngtcp2_rst *rst, ngtcp2_cc *cc,
216 ngtcp2_log *log, ngtcp2_qlog *qlog,
217 const ngtcp2_mem *mem) {
218 ngtcp2_ksl_init(&rtb->ents, greater, sizeof(int64_t), mem);
219 rtb->crypto = crypto;
220 rtb->rst = rst;
221 rtb->cc = cc;
222 rtb->log = log;
223 rtb->qlog = qlog;
224 rtb->mem = mem;
225 rtb->largest_acked_tx_pkt_num = -1;
226 rtb->num_ack_eliciting = 0;
227 rtb->num_retransmittable = 0;
228 rtb->probe_pkt_left = 0;
229 rtb->pktns_id = pktns_id;
230 rtb->cc_pkt_num = 0;
231 rtb->cc_bytes_in_flight = 0;
232 rtb->persistent_congestion_start_ts = UINT64_MAX(18446744073709551615UL);
233 rtb->num_lost_pkts = 0;
234}
235
236void ngtcp2_rtb_free(ngtcp2_rtb *rtb) {
237 ngtcp2_ksl_it it;
238
239 if (rtb == NULL((void*)0)) {
240 return;
241 }
242
243 it = ngtcp2_ksl_begin(&rtb->ents);
244
245 for (; !ngtcp2_ksl_it_end(&it)((&it)->blk->n == (&it)->i && (&
it)->blk->next == ((void*)0)); ngtcp2_ksl_it_next(&it)(++(&it)->i == (&it)->blk->n && (&
it)->blk->next ? ((&it)->blk = (&it)->blk
->next, (&it)->i = 0) : 0)) {
246 ngtcp2_rtb_entry_del(ngtcp2_ksl_it_get(&it), rtb->mem);
247 }
248
249 ngtcp2_ksl_free(&rtb->ents);
250}
251
252static void rtb_on_add(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
253 ngtcp2_conn_stat *cstat) {
254 ngtcp2_rst_on_pkt_sent(rtb->rst, ent, cstat);
255
256 assert(rtb->cc_pkt_num <= ent->hd.pkt_num)((void) (0));
257
258 cstat->bytes_in_flight += ent->pktlen;
259 rtb->cc_bytes_in_flight += ent->pktlen;
260
261 ngtcp2_rst_update_app_limited(rtb->rst, cstat);
262
263 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING0x04) {
264 ++rtb->num_ack_eliciting;
265 }
266 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE0x02) {
267 ++rtb->num_retransmittable;
268 }
269}
270
271static void rtb_on_remove(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
272 ngtcp2_conn_stat *cstat) {
273 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10) {
274 assert(rtb->num_lost_pkts)((void) (0));
275 --rtb->num_lost_pkts;
276 return;
277 }
278
279 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING0x04) {
280 assert(rtb->num_ack_eliciting)((void) (0));
281 --rtb->num_ack_eliciting;
282 }
283
284 if ((ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE0x02) &&
285 !(ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED0x08)) {
286 assert(rtb->num_retransmittable)((void) (0));
287 --rtb->num_retransmittable;
288 }
289
290 if (rtb->cc_pkt_num <= ent->hd.pkt_num) {
291 assert(cstat->bytes_in_flight >= ent->pktlen)((void) (0));
292 cstat->bytes_in_flight -= ent->pktlen;
293
294 assert(rtb->cc_bytes_in_flight >= ent->pktlen)((void) (0));
295 rtb->cc_bytes_in_flight -= ent->pktlen;
296 }
297}
298
299/*
300 * rtb_reclaim_frame queues unacknowledged frames included in |ent|
301 * for retransmission. The re-queued frames are not deleted from
302 * |ent|. It returns the number of frames queued.
303 */
304static ngtcp2_ssize rtb_reclaim_frame(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
305 ngtcp2_pktns *pktns,
306 ngtcp2_rtb_entry *ent) {
307 ngtcp2_frame_chain *frc, *nfrc, **pfrc = &pktns->tx.frq;
308 ngtcp2_frame *fr;
309 ngtcp2_strm *strm;
310 ngtcp2_range gap, range;
311 size_t num_reclaimed = 0;
312 int rv;
313
314 /* PADDING only (or PADDING + ACK ) packets will have NULL
315 ent->frc. */
316 /* TODO Reconsider the order of pfrc */
317 for (frc = ent->frc; frc; frc = frc->next) {
318 fr = &frc->fr;
319 /* Check that a late ACK acknowledged this frame. */
320 if (frc->binder &&
321 (frc->binder->flags & NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK0x01)) {
322 continue;
323 }
324 switch (frc->fr.type) {
325 case NGTCP2_FRAME_STREAM:
326 strm = ngtcp2_conn_find_stream(conn, fr->stream.stream_id);
327 if (strm == NULL((void*)0)) {
328 continue;
329 }
330
331 gap = ngtcp2_strm_get_unacked_range_after(strm, fr->stream.offset);
332
333 range.begin = fr->stream.offset;
334 range.end = fr->stream.offset +
335 ngtcp2_vec_len(fr->stream.data, fr->stream.datacnt);
336 range = ngtcp2_range_intersect(&range, &gap);
337 if (ngtcp2_range_len(&range) == 0 &&
338 (!fr->stream.fin || (strm->flags & NGTCP2_STRM_FLAG_FIN_ACKED0x40))) {
339 continue;
340 }
341
342 rv = ngtcp2_frame_chain_stream_datacnt_new(&nfrc, fr->stream.datacnt,
343 rtb->mem);
344 if (rv != 0) {
345 return rv;
346 }
347
348 nfrc->fr = *fr;
349 ngtcp2_vec_copy(nfrc->fr.stream.data, fr->stream.data,
350 fr->stream.datacnt);
351
352 rv = ngtcp2_strm_streamfrq_push(strm, nfrc);
353 if (rv != 0) {
354 ngtcp2_frame_chain_del(nfrc, conn->mem);
355 return rv;
356 }
357 if (!ngtcp2_strm_is_tx_queued(strm)) {
358 strm->cycle = ngtcp2_conn_tx_strmq_first_cycle(conn);
359 rv = ngtcp2_conn_tx_strmq_push(conn, strm);
360 if (rv != 0) {
361 return rv;
362 }
363 }
364
365 ++num_reclaimed;
366
367 continue;
368 case NGTCP2_FRAME_CRYPTO:
369 /* Don't resend CRYPTO frame if the whole region it contains has
370 been acknowledged */
371 gap = ngtcp2_strm_get_unacked_range_after(rtb->crypto, fr->crypto.offset);
372
373 range.begin = fr->crypto.offset;
374 range.end = fr->crypto.offset +
375 ngtcp2_vec_len(fr->crypto.data, fr->crypto.datacnt);
376 range = ngtcp2_range_intersect(&range, &gap);
377 if (ngtcp2_range_len(&range) == 0) {
378 continue;
379 }
380
381 rv = ngtcp2_frame_chain_crypto_datacnt_new(&nfrc, fr->crypto.datacnt,
382 rtb->mem);
383 if (rv != 0) {
384 return rv;
385 }
386
387 nfrc->fr = *fr;
388 ngtcp2_vec_copy(nfrc->fr.crypto.data, fr->crypto.data,
389 fr->crypto.datacnt);
390
391 rv = ngtcp2_ksl_insert(&pktns->crypto.tx.frq, NULL((void*)0),
392 &nfrc->fr.crypto.offset, nfrc);
393 if (rv != 0) {
394 assert(ngtcp2_err_is_fatal(rv))((void) (0));
395 ngtcp2_frame_chain_del(nfrc, conn->mem);
396 return rv;
397 }
398
399 ++num_reclaimed;
400
401 continue;
402 case NGTCP2_FRAME_NEW_TOKEN:
403 rv = ngtcp2_frame_chain_new_token_new(&nfrc, &fr->new_token.token,
404 rtb->mem);
405 if (rv != 0) {
406 return rv;
407 }
408
409 rv = ngtcp2_bind_frame_chains(frc, nfrc, rtb->mem);
410 if (rv != 0) {
411 return rv;
412 }
413
414 break;
415 default:
416 rv = ngtcp2_frame_chain_new(&nfrc, rtb->mem);
417 if (rv != 0) {
418 return rv;
419 }
420
421 nfrc->fr = *fr;
422
423 rv = ngtcp2_bind_frame_chains(frc, nfrc, rtb->mem);
424 if (rv != 0) {
425 return rv;
426 }
427
428 break;
429 }
430
431 ++num_reclaimed;
432
433 nfrc->next = *pfrc;
434 *pfrc = nfrc;
435 pfrc = &nfrc->next;
436 }
437
438 return (ngtcp2_ssize)num_reclaimed;
439}
440
441static int rtb_on_pkt_lost(ngtcp2_rtb *rtb, ngtcp2_ksl_it *it,
442 ngtcp2_rtb_entry *ent, ngtcp2_conn *conn,
443 ngtcp2_pktns *pktns, ngtcp2_tstamp ts) {
444 int rv;
445 ngtcp2_ssize reclaimed;
446
447 ngtcp2_log_pkt_lost(rtb->log, ent->hd.pkt_num, ent->hd.type, ent->hd.flags,
448 ent->ts);
449
450 if (rtb->qlog) {
451 ngtcp2_qlog_pkt_lost(rtb->qlog, ent);
452 }
453
454 if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_PROBE0x01)) {
455 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED0x08) {
456 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
457 "pkn=%" PRId64"l" "d" " has already been reclaimed on PTO",
458 ent->hd.pkt_num);
459 assert(!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED))((void) (0));
460 assert(UINT64_MAX == ent->lost_ts)((void) (0));
461
462 ent->flags |= NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10;
463 ent->lost_ts = ts;
464
465 ++rtb->num_lost_pkts;
466
467 ngtcp2_ksl_it_next(it)(++(it)->i == (it)->blk->n && (it)->blk->
next ? ((it)->blk = (it)->blk->next, (it)->i = 0)
: 0);
468
469 return 0;
470 }
471
472 if (ent->frc) {
473 assert(!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED))((void) (0));
474 assert(UINT64_MAX == ent->lost_ts)((void) (0));
475
476 reclaimed = rtb_reclaim_frame(rtb, conn, pktns, ent);
477 if (reclaimed < 0) {
478 return (int)reclaimed;
479 }
480
481 if (reclaimed) {
482 ent->flags |= NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10;
483 ent->lost_ts = ts;
484
485 ++rtb->num_lost_pkts;
486
487 ngtcp2_ksl_it_next(it)(++(it)->i == (it)->blk->n && (it)->blk->
next ? ((it)->blk = (it)->blk->next, (it)->i = 0)
: 0);
488
489 return 0;
490 }
491 }
492 } else {
493 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
494 "pkn=%" PRId64"l" "d"
495 " is a probe packet, no retransmission is necessary",
496 ent->hd.pkt_num);
497 }
498
499 rv = ngtcp2_ksl_remove(&rtb->ents, it, &ent->hd.pkt_num);
500 assert(0 == rv)((void) (0));
501
502 ngtcp2_rtb_entry_del(ent, rtb->mem);
503
504 return 0;
505}
506
507int ngtcp2_rtb_add(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
508 ngtcp2_conn_stat *cstat) {
509 int rv;
510
511 rv = ngtcp2_ksl_insert(&rtb->ents, NULL((void*)0), &ent->hd.pkt_num, ent);
512 if (rv != 0) {
513 return rv;
514 }
515
516 rtb_on_add(rtb, ent, cstat);
517
518 return 0;
519}
520
521ngtcp2_ksl_it ngtcp2_rtb_head(ngtcp2_rtb *rtb) {
522 return ngtcp2_ksl_begin(&rtb->ents);
523}
524
525static void rtb_remove(ngtcp2_rtb *rtb, ngtcp2_ksl_it *it,
526 ngtcp2_rtb_entry **pent, ngtcp2_rtb_entry *ent,
527 ngtcp2_conn_stat *cstat) {
528 int rv;
529 rv = ngtcp2_ksl_remove(&rtb->ents, it, &ent->hd.pkt_num);
530 assert(0 == rv)((void) (0));
531 rtb_on_remove(rtb, ent, cstat);
532
533 assert(ent->next == NULL)((void) (0));
534
535 ngtcp2_list_insert(ent, pent)do { (ent)->next = *(pent); *(pent) = (ent); } while (0);
536}
537
538static int rtb_process_acked_pkt(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
539 ngtcp2_conn *conn) {
540 ngtcp2_frame_chain *frc;
541 uint64_t prev_stream_offset, stream_offset;
542 ngtcp2_strm *strm;
543 int rv;
544 uint64_t datalen;
545 ngtcp2_strm *crypto = rtb->crypto;
546 ngtcp2_crypto_level crypto_level;
547
548 for (frc = ent->frc; frc; frc = frc->next) {
549 if (frc->binder) {
550 frc->binder->flags |= NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK0x01;
551 }
552
553 switch (frc->fr.type) {
554 case NGTCP2_FRAME_STREAM:
555 strm = ngtcp2_conn_find_stream(conn, frc->fr.stream.stream_id);
556 if (strm == NULL((void*)0)) {
557 break;
558 }
559
560 if (frc->fr.stream.fin) {
561 strm->flags |= NGTCP2_STRM_FLAG_FIN_ACKED0x40;
562 }
563
564 prev_stream_offset = ngtcp2_strm_get_acked_offset(strm);
565 rv = ngtcp2_strm_ack_data(
566 strm, frc->fr.stream.offset,
567 ngtcp2_vec_len(frc->fr.stream.data, frc->fr.stream.datacnt));
568 if (rv != 0) {
569 return rv;
570 }
571
572 if (conn->callbacks.acked_stream_data_offset) {
573 stream_offset = ngtcp2_strm_get_acked_offset(strm);
574 datalen = stream_offset - prev_stream_offset;
575 if (datalen == 0 && !frc->fr.stream.fin) {
576 break;
577 }
578
579 rv = conn->callbacks.acked_stream_data_offset(
580 conn, strm->stream_id, prev_stream_offset, datalen, conn->user_data,
581 strm->stream_user_data);
582 if (rv != 0) {
583 return NGTCP2_ERR_CALLBACK_FAILURE-502;
584 }
585 }
586
587 rv = ngtcp2_conn_close_stream_if_shut_rdwr(conn, strm, NGTCP2_NO_ERROR0x0u);
588 if (rv != 0) {
589 return rv;
590 }
591 break;
592 case NGTCP2_FRAME_CRYPTO:
593 prev_stream_offset = ngtcp2_strm_get_acked_offset(crypto);
594 rv = ngtcp2_strm_ack_data(
595 crypto, frc->fr.crypto.offset,
596 ngtcp2_vec_len(frc->fr.crypto.data, frc->fr.crypto.datacnt));
597 if (rv != 0) {
598 return rv;
599 }
600
601 if (conn->callbacks.acked_crypto_offset) {
602 stream_offset = ngtcp2_strm_get_acked_offset(crypto);
603 datalen = stream_offset - prev_stream_offset;
604 if (datalen == 0) {
605 break;
606 }
607
608 switch (rtb->pktns_id) {
609 case NGTCP2_PKTNS_ID_INITIAL:
610 crypto_level = NGTCP2_CRYPTO_LEVEL_INITIAL;
611 break;
612 case NGTCP2_PKTNS_ID_HANDSHAKE:
613 crypto_level = NGTCP2_CRYPTO_LEVEL_HANDSHAKE;
614 break;
615 case NGTCP2_PKTNS_ID_APPLICATION:
616 crypto_level = NGTCP2_CRYPTO_LEVEL_APPLICATION;
617 break;
618 default:
619 assert(0)((void) (0));
620 }
621
622 rv = conn->callbacks.acked_crypto_offset(
623 conn, crypto_level, prev_stream_offset, datalen, conn->user_data);
624 if (rv != 0) {
625 return NGTCP2_ERR_CALLBACK_FAILURE-502;
626 }
627 }
628 break;
629 case NGTCP2_FRAME_RESET_STREAM:
630 strm = ngtcp2_conn_find_stream(conn, frc->fr.reset_stream.stream_id);
631 if (strm == NULL((void*)0)) {
632 break;
633 }
634 strm->flags |= NGTCP2_STRM_FLAG_RST_ACKED0x20;
635 rv = ngtcp2_conn_close_stream_if_shut_rdwr(conn, strm, NGTCP2_NO_ERROR0x0u);
636 if (rv != 0) {
637 return rv;
638 }
639 break;
640 case NGTCP2_FRAME_RETIRE_CONNECTION_ID:
641 assert(conn->dcid.num_retire_queued)((void) (0));
642 --conn->dcid.num_retire_queued;
643 break;
644 }
645 }
646 return 0;
647}
648
649static void rtb_on_pkt_acked(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent,
650 ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts) {
651 ngtcp2_cc *cc = rtb->cc;
652 ngtcp2_cc_pkt pkt;
653
654 ngtcp2_rst_update_rate_sample(rtb->rst, ent, ts);
655
656 cc->on_pkt_acked(cc, cstat,
657 ngtcp2_cc_pkt_init(&pkt, ent->hd.pkt_num, ent->pktlen,
658 rtb->pktns_id, ent->ts),
659 ts);
660
661 if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_PROBE0x01) &&
662 (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING0x04)) {
663 cstat->pto_count = 0;
664 }
665}
666
667static void conn_verify_ecn(ngtcp2_conn *conn, ngtcp2_pktns *pktns,
668 ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
669 const ngtcp2_ack *fr, size_t ecn_acked,
670 ngtcp2_tstamp largest_acked_sent_ts,
671 ngtcp2_tstamp ts) {
672 if (conn->tx.ecn.state == NGTCP2_ECN_STATE_FAILED) {
10
←
Dereference of null pointer
673 return;
674 }
675
676 if ((ecn_acked && fr->type == NGTCP2_FRAME_ACK) ||
677 (fr->type == NGTCP2_FRAME_ACK_ECN &&
678 (pktns->rx.ecn.ack.ect0 > fr->ecn.ect0 ||
679 pktns->rx.ecn.ack.ect1 > fr->ecn.ect1 ||
680 pktns->rx.ecn.ack.ce > fr->ecn.ce ||
681 (fr->ecn.ect0 - pktns->rx.ecn.ack.ect0) +
682 (fr->ecn.ce - pktns->rx.ecn.ack.ce) <
683 ecn_acked ||
684 fr->ecn.ect0 > pktns->tx.ecn.ect0 || fr->ecn.ect1))) {
685 ngtcp2_log_info(&conn->log, NGTCP2_LOG_EVENT_CON,
686 "path is not ECN capable");
687 conn->tx.ecn.state = NGTCP2_ECN_STATE_FAILED;
688 return;
689 }
690
691 if (conn->tx.ecn.state != NGTCP2_ECN_STATE_CAPABLE && ecn_acked) {
692 ngtcp2_log_info(&conn->log, NGTCP2_LOG_EVENT_CON, "path is ECN capable");
693 conn->tx.ecn.state = NGTCP2_ECN_STATE_CAPABLE;
694 }
695
696 if (fr->type == NGTCP2_FRAME_ACK_ECN) {
697 if (largest_acked_sent_ts != UINT64_MAX(18446744073709551615UL) &&
698 fr->ecn.ce > pktns->rx.ecn.ack.ce) {
699 cc->congestion_event(cc, cstat, largest_acked_sent_ts, ts);
700 }
701
702 pktns->rx.ecn.ack.ect0 = fr->ecn.ect0;
703 pktns->rx.ecn.ack.ect1 = fr->ecn.ect1;
704 pktns->rx.ecn.ack.ce = fr->ecn.ce;
705 }
706}
707
708ngtcp2_ssize ngtcp2_rtb_recv_ack(ngtcp2_rtb *rtb, const ngtcp2_ack *fr,
709 ngtcp2_conn_stat *cstat, ngtcp2_conn *conn,
710 ngtcp2_pktns *pktns, ngtcp2_tstamp pkt_ts,
711 ngtcp2_tstamp ts) {
712 ngtcp2_rtb_entry *ent;
713 int64_t largest_ack = fr->largest_ack, min_ack;
714 size_t i;
715 int rv;
716 ngtcp2_ksl_it it;
717 ngtcp2_ssize num_acked = 0;
718 ngtcp2_tstamp largest_pkt_sent_ts = UINT64_MAX(18446744073709551615UL);
719 ngtcp2_tstamp largest_acked_sent_ts = UINT64_MAX(18446744073709551615UL);
720 int64_t pkt_num;
721 ngtcp2_cc *cc = rtb->cc;
722 ngtcp2_rtb_entry *acked_ent = NULL((void*)0);
723 int ack_eliciting_pkt_acked = 0;
724 size_t ecn_acked = 0;
725 int verify_ecn = 0;
726
727 if (conn && (conn->flags & NGTCP2_CONN_FLAG_KEY_UPDATE_NOT_CONFIRMED0x0800) &&
1
Assuming 'conn' is null
→
728 largest_ack >= conn->pktns.crypto.tx.ckm->pkt_num) {
729 conn->flags &= (uint16_t)~NGTCP2_CONN_FLAG_KEY_UPDATE_NOT_CONFIRMED0x0800;
730 conn->crypto.key_update.confirmed_ts = ts;
731
732 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_CRY, "key update confirmed");
733 }
734
735 if (rtb->largest_acked_tx_pkt_num < largest_ack) {
2
←
Assuming 'largest_ack' is > field 'largest_acked_tx_pkt_num'
→
3
←
Taking true branch
→
736 rtb->largest_acked_tx_pkt_num = largest_ack;
737 verify_ecn = 1;
738 }
739
740 /* Assume that ngtcp2_pkt_validate_ack(fr) returns 0 */
741 it = ngtcp2_ksl_lower_bound(&rtb->ents, &largest_ack);
742 if (ngtcp2_ksl_it_end(&it)((&it)->blk->n == (&it)->i && (&
it)->blk->next == ((void*)0))) {
4
←
Assuming field 'n' is equal to field 'i'
→
5
←
Assuming field 'next' is equal to null
→
6
←
Taking true branch
→
743 if (verify_ecn
6.1
'verify_ecn' is 1
) {
7
←
Taking true branch
→
744 conn_verify_ecn(conn, pktns, rtb->cc, cstat, fr, ecn_acked,
8
←
Passing null pointer value via 1st parameter 'conn'
→
9
←
Calling 'conn_verify_ecn'
→
745 largest_acked_sent_ts, ts);
746 }
747 return 0;
748 }
749
750 min_ack = largest_ack - (int64_t)fr->first_ack_blklen;
751
752 for (; !ngtcp2_ksl_it_end(&it)((&it)->blk->n == (&it)->i && (&
it)->blk->next == ((void*)0));) {
753 pkt_num = *(int64_t *)ngtcp2_ksl_it_key(&it)((ngtcp2_ksl_key *)((ngtcp2_ksl_node *)(void *)(((&it)->
blk)->nodes + ((&it)->ksl)->nodelen * ((&it)
->i)))->key);
754
755 assert(pkt_num <= largest_ack)((void) (0));
756
757 if (pkt_num < min_ack) {
758 break;
759 }
760
761 ent = ngtcp2_ksl_it_get(&it);
762
763 if (largest_ack == pkt_num) {
764 largest_pkt_sent_ts = ent->ts;
765 }
766
767 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING0x04) {
768 ack_eliciting_pkt_acked = 1;
769 }
770
771 rtb_remove(rtb, &it, &acked_ent, ent, cstat);
772 ++num_acked;
773 }
774
775 for (i = 0; i < fr->num_blks;) {
776 largest_ack = min_ack - (int64_t)fr->blks[i].gap - 2;
777 min_ack = largest_ack - (int64_t)fr->blks[i].blklen;
778
779 it = ngtcp2_ksl_lower_bound(&rtb->ents, &largest_ack);
780 if (ngtcp2_ksl_it_end(&it)((&it)->blk->n == (&it)->i && (&
it)->blk->next == ((void*)0))) {
781 break;
782 }
783
784 for (; !ngtcp2_ksl_it_end(&it)((&it)->blk->n == (&it)->i && (&
it)->blk->next == ((void*)0));) {
785 pkt_num = *(int64_t *)ngtcp2_ksl_it_key(&it)((ngtcp2_ksl_key *)((ngtcp2_ksl_node *)(void *)(((&it)->
blk)->nodes + ((&it)->ksl)->nodelen * ((&it)
->i)))->key);
786 if (pkt_num < min_ack) {
787 break;
788 }
789 ent = ngtcp2_ksl_it_get(&it);
790
791 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING0x04) {
792 ack_eliciting_pkt_acked = 1;
793 }
794
795 rtb_remove(rtb, &it, &acked_ent, ent, cstat);
796 ++num_acked;
797 }
798
799 ++i;
800 }
801
802 if (largest_pkt_sent_ts != UINT64_MAX(18446744073709551615UL) && ack_eliciting_pkt_acked) {
803 ngtcp2_conn_update_rtt(conn, pkt_ts - largest_pkt_sent_ts,
804 fr->ack_delay_unscaled, ts);
805 if (cc->new_rtt_sample) {
806 cc->new_rtt_sample(cc, cstat, ts);
807 }
808 }
809
810 ngtcp2_rst_on_ack_recv(rtb->rst, cstat);
811
812 if (conn) {
813 for (ent = acked_ent; ent; ent = acked_ent) {
814 if (ent->hd.pkt_num >= pktns->tx.ecn.start_pkt_num &&
815 (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ECN0x20)) {
816 ++ecn_acked;
817 }
818
819 assert(largest_acked_sent_ts == UINT64_MAX ||((void) (0))
820 largest_acked_sent_ts <= ent->ts)((void) (0));
821
822 largest_acked_sent_ts = ent->ts;
823
824 rv = rtb_process_acked_pkt(rtb, ent, conn);
825 if (rv != 0) {
826 goto fail;
827 }
828
829 rtb_on_pkt_acked(rtb, ent, cstat, ts);
830 acked_ent = ent->next;
831 ngtcp2_rtb_entry_del(ent, rtb->mem);
832 }
833
834 if (verify_ecn) {
835 conn_verify_ecn(conn, pktns, rtb->cc, cstat, fr, ecn_acked,
836 largest_acked_sent_ts, ts);
837 }
838 } else {
839 /* For unit tests */
840 for (ent = acked_ent; ent; ent = acked_ent) {
841 rtb_on_pkt_acked(rtb, ent, cstat, ts);
842 acked_ent = ent->next;
843 ngtcp2_rtb_entry_del(ent, rtb->mem);
844 }
845 }
846
847 cc->on_ack_recv(cc, cstat, ts);
848
849 return num_acked;
850
851fail:
852 for (ent = acked_ent; ent; ent = acked_ent) {
853 acked_ent = ent->next;
854 ngtcp2_rtb_entry_del(ent, rtb->mem);
855 }
856
857 return rv;
858}
859
860static int rtb_pkt_lost(ngtcp2_rtb *rtb, ngtcp2_conn_stat *cstat,
861 const ngtcp2_rtb_entry *ent, uint64_t loss_delay,
862 ngtcp2_tstamp lost_send_time, uint64_t pkt_thres) {
863 ngtcp2_tstamp loss_time;
864
865 if (ent->ts <= lost_send_time ||
866 rtb->largest_acked_tx_pkt_num >= ent->hd.pkt_num + (int64_t)pkt_thres) {
867 return 1;
868 }
869
870 loss_time = cstat->loss_time[rtb->pktns_id];
871
872 if (loss_time == UINT64_MAX(18446744073709551615UL)) {
873 loss_time = ent->ts + loss_delay;
874 } else {
875 loss_time = ngtcp2_min(loss_time, ent->ts + loss_delay)((loss_time) < (ent->ts + loss_delay) ? (loss_time) : (
ent->ts + loss_delay));
876 }
877
878 cstat->loss_time[rtb->pktns_id] = loss_time;
879
880 return 0;
881}
882
883/*
884 * rtb_compute_pkt_loss_delay computes loss delay.
885 */
886static ngtcp2_duration compute_pkt_loss_delay(const ngtcp2_conn_stat *cstat) {
887 /* 9/8 is kTimeThreshold */
888 ngtcp2_duration loss_delay =
889 ngtcp2_max(cstat->latest_rtt, cstat->smoothed_rtt)((cstat->latest_rtt) > (cstat->smoothed_rtt) ? (cstat
->latest_rtt) : (cstat->smoothed_rtt)) * 9 / 8;
890 return ngtcp2_max(loss_delay, NGTCP2_GRANULARITY)((loss_delay) > (((uint64_t)1000000ULL)) ? (loss_delay) : (
((uint64_t)1000000ULL)));
891}
892
893/*
894 * conn_all_ecn_pkt_lost returns nonzero if all ECN QUIC packets are
895 * lost during validation period.
896 */
897static int conn_all_ecn_pkt_lost(ngtcp2_conn *conn) {
898 ngtcp2_pktns *in_pktns = conn->in_pktns;
899 ngtcp2_pktns *hs_pktns = conn->hs_pktns;
900 ngtcp2_pktns *pktns = &conn->pktns;
901
902 return (!in_pktns || in_pktns->tx.ecn.validation_pkt_sent ==
903 in_pktns->tx.ecn.validation_pkt_lost) &&
904 (!hs_pktns || hs_pktns->tx.ecn.validation_pkt_sent ==
905 hs_pktns->tx.ecn.validation_pkt_lost) &&
906 pktns->tx.ecn.validation_pkt_sent == pktns->tx.ecn.validation_pkt_lost;
907}
908
909int ngtcp2_rtb_detect_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
910 ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat,
911 ngtcp2_duration pto, ngtcp2_tstamp ts) {
912 ngtcp2_rtb_entry *ent;
913 ngtcp2_duration loss_delay;
914 ngtcp2_tstamp lost_send_time;
915 ngtcp2_ksl_it it;
916 ngtcp2_tstamp latest_ts, oldest_ts;
917 int64_t last_lost_pkt_num;
918 ngtcp2_duration loss_window, congestion_period;
919 ngtcp2_cc *cc = rtb->cc;
920 int rv;
921 uint64_t pkt_thres =
922 rtb->cc_bytes_in_flight / cstat->max_udp_payload_size / 2;
923 size_t ecn_pkt_lost = 0;
924 ngtcp2_tstamp start_ts;
925
926 pkt_thres = ngtcp2_max(pkt_thres, NGTCP2_PKT_THRESHOLD)((pkt_thres) > (3) ? (pkt_thres) : (3));
927 cstat->loss_time[rtb->pktns_id] = UINT64_MAX(18446744073709551615UL);
928 loss_delay = compute_pkt_loss_delay(cstat);
929 lost_send_time = ts - loss_delay;
930
931 it = ngtcp2_ksl_lower_bound(&rtb->ents, &rtb->largest_acked_tx_pkt_num);
932 for (; !ngtcp2_ksl_it_end(&it)((&it)->blk->n == (&it)->i && (&
it)->blk->next == ((void*)0)); ngtcp2_ksl_it_next(&it)(++(&it)->i == (&it)->blk->n && (&
it)->blk->next ? ((&it)->blk = (&it)->blk
->next, (&it)->i = 0) : 0)) {
933 ent = ngtcp2_ksl_it_get(&it);
934
935 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10) {
936 break;
937 }
938
939 if (rtb_pkt_lost(rtb, cstat, ent, loss_delay, lost_send_time, pkt_thres)) {
940 /* All entries from ent are considered to be lost. */
941 latest_ts = oldest_ts = ent->ts;
942 last_lost_pkt_num = ent->hd.pkt_num;
943
944 congestion_period = (cstat->smoothed_rtt +
945 ngtcp2_max(4 * cstat->rttvar, NGTCP2_GRANULARITY)((4 * cstat->rttvar) > (((uint64_t)1000000ULL)) ? (4 * cstat
->rttvar) : (((uint64_t)1000000ULL))) +
946 conn->remote.transport_params.max_ack_delay) *
947 NGTCP2_PERSISTENT_CONGESTION_THRESHOLD3;
948
949 start_ts = ngtcp2_max(rtb->persistent_congestion_start_ts,((rtb->persistent_congestion_start_ts) > (cstat->first_rtt_sample_ts
) ? (rtb->persistent_congestion_start_ts) : (cstat->first_rtt_sample_ts
))
950 cstat->first_rtt_sample_ts)((rtb->persistent_congestion_start_ts) > (cstat->first_rtt_sample_ts
) ? (rtb->persistent_congestion_start_ts) : (cstat->first_rtt_sample_ts
));
951
952 for (; !ngtcp2_ksl_it_end(&it)((&it)->blk->n == (&it)->i && (&
it)->blk->next == ((void*)0));) {
953 ent = ngtcp2_ksl_it_get(&it);
954
955 if (last_lost_pkt_num == ent->hd.pkt_num + 1 && ent->ts >= start_ts) {
956 last_lost_pkt_num = ent->hd.pkt_num;
957 oldest_ts = ent->ts;
958 } else {
959 last_lost_pkt_num = -1;
960 }
961
962 if ((ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10)) {
963 if (rtb->pktns_id != NGTCP2_PKTNS_ID_APPLICATION ||
964 last_lost_pkt_num == -1 ||
965 latest_ts - oldest_ts >= congestion_period) {
966 break;
967 }
968 ngtcp2_ksl_it_next(&it)(++(&it)->i == (&it)->blk->n && (&
it)->blk->next ? ((&it)->blk = (&it)->blk
->next, (&it)->i = 0) : 0);
969 continue;
970 }
971
972 if (ent->hd.pkt_num >= pktns->tx.ecn.start_pkt_num &&
973 (ent->flags & NGTCP2_RTB_ENTRY_FLAG_ECN0x20)) {
974 ++ecn_pkt_lost;
975 }
976
977 rtb_on_remove(rtb, ent, cstat);
978 rv = rtb_on_pkt_lost(rtb, &it, ent, conn, pktns, ts);
979 if (rv != 0) {
980 return rv;
981 }
982 }
983
984 switch (conn->tx.ecn.state) {
985 case NGTCP2_ECN_STATE_TESTING:
986 if (conn->tx.ecn.validation_start_ts == UINT64_MAX(18446744073709551615UL)) {
987 break;
988 }
989 if (ts - conn->tx.ecn.validation_start_ts < 3 * pto) {
990 pktns->tx.ecn.validation_pkt_lost += ecn_pkt_lost;
991 assert(pktns->tx.ecn.validation_pkt_sent >=((void) (0))
992 pktns->tx.ecn.validation_pkt_lost)((void) (0));
993 break;
994 }
995 conn->tx.ecn.state = NGTCP2_ECN_STATE_UNKNOWN;
996 /* fall through */
997 case NGTCP2_ECN_STATE_UNKNOWN:
998 pktns->tx.ecn.validation_pkt_lost += ecn_pkt_lost;
999 assert(pktns->tx.ecn.validation_pkt_sent >=((void) (0))
1000 pktns->tx.ecn.validation_pkt_lost)((void) (0));
1001 if (conn_all_ecn_pkt_lost(conn)) {
1002 conn->tx.ecn.state = NGTCP2_ECN_STATE_FAILED;
1003 }
1004 break;
1005 default:
1006 break;
1007 }
1008
1009 cc->congestion_event(cc, cstat, latest_ts, ts);
1010
1011 loss_window = latest_ts - oldest_ts;
1012 /* Persistent congestion situation is only evaluated for app
1013 * packet number space and for the packets sent after handshake
1014 * is confirmed. During handshake, there is not much packets
1015 * sent and also people seem to do lots of effort not to trigger
1016 * persistent congestion there, then it is a lot easier to just
1017 * not enable it during handshake.
1018 */
1019 if (rtb->pktns_id == NGTCP2_PKTNS_ID_APPLICATION && loss_window > 0) {
1020 if (loss_window >= congestion_period) {
1021 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1022 "persistent congestion loss_window=%" PRIu64"l" "u"
1023 " congestion_period=%" PRIu64"l" "u",
1024 loss_window, congestion_period);
1025
1026 /* Reset min_rtt, srtt, and rttvar here. Next new RTT
1027 sample will be used to recalculate these values. */
1028 cstat->min_rtt = UINT64_MAX(18446744073709551615UL);
1029 cstat->smoothed_rtt = conn->local.settings.initial_rtt;
1030 cstat->rttvar = conn->local.settings.initial_rtt / 2;
1031 cstat->first_rtt_sample_ts = UINT64_MAX(18446744073709551615UL);
1032
1033 cc->on_persistent_congestion(cc, cstat, ts);
1034 }
1035 }
1036
1037 break;
1038 }
1039 }
1040
1041 ngtcp2_rtb_remove_excessive_lost_pkt(rtb, pkt_thres);
1042
1043 return 0;
1044}
1045
1046void ngtcp2_rtb_remove_excessive_lost_pkt(ngtcp2_rtb *rtb, size_t n) {
1047 ngtcp2_ksl_it it = ngtcp2_ksl_end(&rtb->ents);
1048 ngtcp2_rtb_entry *ent;
1049 int rv;
1050
1051 for (; rtb->num_lost_pkts > n;) {
1052 assert(ngtcp2_ksl_it_end(&it))((void) (0));
1053 ngtcp2_ksl_it_prev(&it);
1054 ent = ngtcp2_ksl_it_get(&it);
1055
1056 assert(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED)((void) (0));
1057
1058 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1059 "removing stale lost pkn=%" PRId64"l" "d", ent->hd.pkt_num);
1060
1061 --rtb->num_lost_pkts;
1062 rv = ngtcp2_ksl_remove(&rtb->ents, &it, &ent->hd.pkt_num);
1063 assert(0 == rv)((void) (0));
1064 ngtcp2_rtb_entry_del(ent, rtb->mem);
1065 }
1066}
1067
1068void ngtcp2_rtb_remove_expired_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_duration pto,
1069 ngtcp2_tstamp ts) {
1070 ngtcp2_ksl_it it;
1071 ngtcp2_rtb_entry *ent;
1072 int rv;
1073
1074 if (ngtcp2_ksl_len(&rtb->ents) == 0) {
1075 return;
1076 }
1077
1078 it = ngtcp2_ksl_end(&rtb->ents);
1079
1080 for (;;) {
1081 assert(ngtcp2_ksl_it_end(&it))((void) (0));
1082
1083 ngtcp2_ksl_it_prev(&it);
1084 ent = ngtcp2_ksl_it_get(&it);
1085
1086 if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10) ||
1087 ts - ent->lost_ts < pto) {
1088 return;
1089 }
1090
1091 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1092 "removing stale lost pkn=%" PRId64"l" "d", ent->hd.pkt_num);
1093
1094 --rtb->num_lost_pkts;
1095 rv = ngtcp2_ksl_remove(&rtb->ents, &it, &ent->hd.pkt_num);
1096 assert(0 == rv)((void) (0));
1097 ngtcp2_rtb_entry_del(ent, rtb->mem);
1098
1099 if (ngtcp2_ksl_len(&rtb->ents) == 0) {
1100 return;
1101 }
1102 }
1103}
1104
1105ngtcp2_tstamp ngtcp2_rtb_lost_pkt_ts(ngtcp2_rtb *rtb) {
1106 ngtcp2_ksl_it it;
1107 ngtcp2_rtb_entry *ent;
1108
1109 if (ngtcp2_ksl_len(&rtb->ents) == 0) {
1110 return UINT64_MAX(18446744073709551615UL);
1111 }
1112
1113 it = ngtcp2_ksl_end(&rtb->ents);
1114 ngtcp2_ksl_it_prev(&it);
1115 ent = ngtcp2_ksl_it_get(&it);
1116
1117 if (!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10)) {
1118 return UINT64_MAX(18446744073709551615UL);
1119 }
1120
1121 return ent->lost_ts;
1122}
1123
1124static int rtb_on_pkt_lost_resched_move(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
1125 ngtcp2_pktns *pktns,
1126 ngtcp2_rtb_entry *ent) {
1127 ngtcp2_frame_chain **pfrc, *frc;
1128 ngtcp2_stream *sfr;
1129 ngtcp2_strm *strm;
1130 int rv;
1131
1132 ngtcp2_log_pkt_lost(rtb->log, ent->hd.pkt_num, ent->hd.type, ent->hd.flags,
1133 ent->ts);
1134
1135 if (rtb->qlog) {
1136 ngtcp2_qlog_pkt_lost(rtb->qlog, ent);
1137 }
1138
1139 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PROBE0x01) {
1140 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1141 "pkn=%" PRId64"l" "d"
1142 " is a probe packet, no retransmission is necessary",
1143 ent->hd.pkt_num);
1144 return 0;
1145 }
1146
1147 if (!ent->frc) {
1148 /* PADDING only (or PADDING + ACK ) packets will have NULL
1149 ent->frc. */
1150 assert(!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED))((void) (0));
1151 assert(!(ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED))((void) (0));
1152 return 0;
1153 }
1154
1155 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10) {
1156 --rtb->num_lost_pkts;
1157 }
1158
1159 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10) {
1160 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1161 "pkn=%" PRId64"l" "d"
1162 " was declared lost and has already been retransmitted",
1163 ent->hd.pkt_num);
1164 return 0;
1165 }
1166
1167 if (ent->flags & NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED0x08) {
1168 ngtcp2_log_info(rtb->log, NGTCP2_LOG_EVENT_RCV,
1169 "pkn=%" PRId64"l" "d" " has already been reclaimed on PTO",
1170 ent->hd.pkt_num);
1171 return 0;
1172 }
1173
1174 pfrc = &ent->frc;
1175
1176 for (; *pfrc;) {
1177 switch ((*pfrc)->fr.type) {
1178 case NGTCP2_FRAME_STREAM:
1179 frc = *pfrc;
1180
1181 *pfrc = frc->next;
1182 frc->next = NULL((void*)0);
1183 sfr = &frc->fr.stream;
1184
1185 strm = ngtcp2_conn_find_stream(conn, sfr->stream_id);
1186 if (!strm) {
1187 ngtcp2_frame_chain_del(frc, conn->mem);
1188 break;
1189 }
1190 rv = ngtcp2_strm_streamfrq_push(strm, frc);
1191 if (rv != 0) {
1192 ngtcp2_frame_chain_del(frc, conn->mem);
1193 return rv;
1194 }
1195 if (!ngtcp2_strm_is_tx_queued(strm)) {
1196 strm->cycle = ngtcp2_conn_tx_strmq_first_cycle(conn);
1197 rv = ngtcp2_conn_tx_strmq_push(conn, strm);
1198 if (rv != 0) {
1199 return rv;
1200 }
1201 }
1202 break;
1203 case NGTCP2_FRAME_CRYPTO:
1204 frc = *pfrc;
1205
1206 *pfrc = frc->next;
1207 frc->next = NULL((void*)0);
1208
1209 rv = ngtcp2_ksl_insert(&pktns->crypto.tx.frq, NULL((void*)0),
1210 &frc->fr.crypto.offset, frc);
1211 if (rv != 0) {
1212 assert(ngtcp2_err_is_fatal(rv))((void) (0));
1213 ngtcp2_frame_chain_del(frc, conn->mem);
1214 return rv;
1215 }
1216 break;
1217 default:
1218 pfrc = &(*pfrc)->next;
1219 }
1220 }
1221
1222 *pfrc = pktns->tx.frq;
1223 pktns->tx.frq = ent->frc;
1224 ent->frc = NULL((void*)0);
1225
1226 return 0;
1227}
1228
1229int ngtcp2_rtb_remove_all(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
1230 ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat) {
1231 ngtcp2_rtb_entry *ent;
1232 ngtcp2_ksl_it it;
1233 int rv;
1234
1235 it = ngtcp2_ksl_begin(&rtb->ents);
1236
1237 for (; !ngtcp2_ksl_it_end(&it)((&it)->blk->n == (&it)->i && (&
it)->blk->next == ((void*)0));) {
1238 ent = ngtcp2_ksl_it_get(&it);
1239
1240 rtb_on_remove(rtb, ent, cstat);
1241 rv = ngtcp2_ksl_remove(&rtb->ents, &it, &ent->hd.pkt_num);
1242 assert(0 == rv)((void) (0));
1243
1244 rv = rtb_on_pkt_lost_resched_move(rtb, conn, pktns, ent);
1245 ngtcp2_rtb_entry_del(ent, rtb->mem);
1246 if (rv != 0) {
1247 return rv;
1248 }
1249 }
1250
1251 return 0;
1252}
1253
1254int ngtcp2_rtb_empty(ngtcp2_rtb *rtb) {
1255 return ngtcp2_ksl_len(&rtb->ents) == 0;
1256}
1257
1258void ngtcp2_rtb_reset_cc_state(ngtcp2_rtb *rtb, int64_t cc_pkt_num) {
1259 rtb->cc_pkt_num = cc_pkt_num;
1260 rtb->cc_bytes_in_flight = 0;
1261}
1262
1263ngtcp2_ssize ngtcp2_rtb_reclaim_on_pto(ngtcp2_rtb *rtb, ngtcp2_conn *conn,
1264 ngtcp2_pktns *pktns, size_t num_pkts) {
1265 ngtcp2_ksl_it it;
1266 ngtcp2_rtb_entry *ent;
1267 ngtcp2_ssize reclaimed;
1268 size_t atmost = num_pkts;
1269
1270 it = ngtcp2_ksl_end(&rtb->ents);
1271 for (; !ngtcp2_ksl_it_begin(&it) && num_pkts >= 1;) {
1272 ngtcp2_ksl_it_prev(&it);
1273 ent = ngtcp2_ksl_it_get(&it);
1274
1275 if ((ent->flags & (NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED0x10 |
1276 NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED0x08)) ||
1277 !(ent->flags & NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE0x02)) {
1278 continue;
1279 }
1280
1281 assert(ent->frc)((void) (0));
1282
1283 reclaimed = rtb_reclaim_frame(rtb, conn, pktns, ent);
1284 if (reclaimed < 0) {
1285 return reclaimed;
1286 }
1287
1288 /* Mark reclaimed even if reclaimed == 0 so that we can skip it in
1289 the next run. */
1290 ent->flags |= NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED0x08;
1291
1292 assert(rtb->num_retransmittable)((void) (0));
1293 --rtb->num_retransmittable;
1294
1295 if (reclaimed) {
1296 --num_pkts;
1297 }
1298 }
1299
1300 return (ngtcp2_ssize)(atmost - num_pkts);
1301}