1/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc. See LICENSE. */ 2/* 3 * lsquic_send_ctl.c -- Logic for sending and sent packets 4 */ 5 6#include <assert.h> 7#include <errno.h> 8#include <inttypes.h> 9#include <stdlib.h> 10#include <string.h> 11#include <sys/queue.h> 12 13#include <openssl/rand.h> 14 15#include "lsquic_types.h" 16#include "lsquic_int_types.h" 17#include "lsquic.h" 18#include "lsquic_mm.h" 19#include "lsquic_engine_public.h" 20#include "lsquic_packet_common.h" 21#include "lsquic_alarmset.h" 22#include "lsquic_parse.h" 23#include "lsquic_packet_in.h" 24#include "lsquic_packet_out.h" 25#include "lsquic_packet_resize.h" 26#include "lsquic_senhist.h" 27#include "lsquic_rtt.h" 28#include "lsquic_cubic.h" 29#include "lsquic_pacer.h" 30#include "lsquic_bw_sampler.h" 31#include "lsquic_minmax.h" 32#include "lsquic_bbr.h" 33#include "lsquic_adaptive_cc.h" 34#include "lsquic_util.h" 35#include "lsquic_sfcw.h" 36#include "lsquic_varint.h" 37#include "lsquic_hq.h" 38#include "lsquic_hash.h" 39#include "lsquic_stream.h" 40#include "lsquic_ver_neg.h" 41#include "lsquic_ev_log.h" 42#include "lsquic_conn.h" 43#include "lsquic_send_ctl.h" 44#include "lsquic_conn_flow.h" 45#include "lsquic_conn_public.h" 46#include "lsquic_cong_ctl.h" 47#include "lsquic_enc_sess.h" 48#include "lsquic_malo.h" 49#include "lsquic_attq.h" 50#include "lsquic_http1x_if.h" 51#include "lsqpack.h" 52#include "lsquic_frab_list.h" 53#include "lsquic_qdec_hdl.h" 54#include "lsquic_crand.h" 55 56#define LSQUIC_LOGGER_MODULE LSQLM_SENDCTL 57#define LSQUIC_LOG_CONN_ID lsquic_conn_log_cid(ctl->sc_conn_pub->lconn) 58#include "lsquic_logger.h" 59 60#if __GNUC__ 61# define UNLIKELY(cond) __builtin_expect(cond, 0) 62#else 63# define UNLIKELY(cond) cond 64#endif 65 66#define MAX_RESUBMITTED_ON_RTO 2 67#define MAX_RTO_BACKOFFS 10 68#define DEFAULT_RETX_DELAY 500000 /* Microseconds */ 69#define MAX_RTO_DELAY 60000000 /* Microseconds */ 70#define MIN_RTO_DELAY 200000 /* Microseconds */ 71#define N_NACKS_BEFORE_RETX 3 72 73#define CGP(ctl) ((struct cong_ctl *) (ctl)->sc_cong_ctl) 74 75#define packet_out_total_sz(p) \ 76 lsquic_packet_out_total_sz(ctl->sc_conn_pub->lconn, p) 77#define packet_out_sent_sz(p) \ 78 lsquic_packet_out_sent_sz(ctl->sc_conn_pub->lconn, p) 79 80enum retx_mode { 81 RETX_MODE_HANDSHAKE, 82 RETX_MODE_LOSS, 83 RETX_MODE_TLP, 84 RETX_MODE_RTO, 85}; 86 87 88static const char *const retx2str[] = { 89 [RETX_MODE_HANDSHAKE] = "RETX_MODE_HANDSHAKE", 90 [RETX_MODE_LOSS] = "RETX_MODE_LOSS", 91 [RETX_MODE_TLP] = "RETX_MODE_TLP", 92 [RETX_MODE_RTO] = "RETX_MODE_RTO", 93}; 94 95#ifdef NDEBUG 96#define MAX_BPQ_COUNT 10 97#else 98static unsigned MAX_BPQ_COUNT = 10; 99void 100lsquic_send_ctl_set_max_bpq_count (unsigned count) { MAX_BPQ_COUNT = count; } 101#endif 102 103 104static void 105update_for_resending (lsquic_send_ctl_t *ctl, lsquic_packet_out_t *packet_out); 106 107 108enum expire_filter { EXFI_ALL, EXFI_HSK, EXFI_LAST, }; 109 110 111static void 112send_ctl_expire (struct lsquic_send_ctl *, enum packnum_space, 113 enum expire_filter); 114 115static void 116set_retx_alarm (struct lsquic_send_ctl *, enum packnum_space, lsquic_time_t); 117 118static int 119send_ctl_detect_losses (struct lsquic_send_ctl *, enum packnum_space, 120 lsquic_time_t time); 121 122static unsigned 123send_ctl_retx_bytes_out (const struct lsquic_send_ctl *ctl); 124 125static unsigned 126send_ctl_all_bytes_out (const struct lsquic_send_ctl *ctl); 127 128static void 129send_ctl_reschedule_poison (struct lsquic_send_ctl *ctl); 130 131static int 132send_ctl_can_send_pre_hsk (struct lsquic_send_ctl *ctl); 133 134static int 135send_ctl_can_send (struct lsquic_send_ctl *ctl); 136 137static int 138split_lost_packet (struct lsquic_send_ctl *, struct lsquic_packet_out *const); 139 140#ifdef NDEBUG 141static 142#elif __GNUC__ 143__attribute__((weak)) 144#endif 145int 146lsquic_send_ctl_schedule_stream_packets_immediately (lsquic_send_ctl_t *ctl) 147{ 148 return !(ctl->sc_flags & SC_BUFFER_STREAM); 149} 150 151 152#ifdef NDEBUG 153static 154#elif __GNUC__ 155__attribute__((weak)) 156#endif 157enum packno_bits 158lsquic_send_ctl_guess_packno_bits (lsquic_send_ctl_t *ctl) 159{ 160 return PACKNO_BITS_1; /* This is 2 bytes in both GQUIC and IQUIC */ 161} 162 163 164int 165lsquic_send_ctl_have_unacked_stream_frames (const lsquic_send_ctl_t *ctl) 166{ 167 const lsquic_packet_out_t *packet_out; 168 169 TAILQ_FOREACH(packet_out, &ctl->sc_unacked_packets[PNS_APP], po_next) 170 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON)) 171 && (packet_out->po_frame_types & 172 ((1 << QUIC_FRAME_STREAM) | (1 << QUIC_FRAME_RST_STREAM)))) 173 return 1; 174 175 return 0; 176} 177 178 179static lsquic_packet_out_t * 180send_ctl_first_unacked_retx_packet (const struct lsquic_send_ctl *ctl, 181 enum packnum_space pns) 182{ 183 lsquic_packet_out_t *packet_out; 184 185 TAILQ_FOREACH(packet_out, &ctl->sc_unacked_packets[pns], po_next) 186 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON)) 187 && (packet_out->po_frame_types & ctl->sc_retx_frames)) 188 return packet_out; 189 190 return NULL; 191} 192 193 194int 195lsquic_send_ctl_have_unacked_retx_data (const struct lsquic_send_ctl *ctl) 196{ 197 return lsquic_alarmset_is_set(ctl->sc_alset, AL_RETX_APP) 198 && send_ctl_first_unacked_retx_packet(ctl, PNS_APP); 199} 200 201 202static lsquic_packet_out_t * 203send_ctl_last_unacked_retx_packet (const struct lsquic_send_ctl *ctl, 204 enum packnum_space pns) 205{ 206 lsquic_packet_out_t *packet_out; 207 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_unacked_packets[pns], 208 lsquic_packets_tailq, po_next) 209 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON)) 210 && (packet_out->po_frame_types & ctl->sc_retx_frames)) 211 return packet_out; 212 return NULL; 213} 214 215 216static int 217have_unacked_handshake_packets (const lsquic_send_ctl_t *ctl) 218{ 219 const lsquic_packet_out_t *packet_out; 220 enum packnum_space pns; 221 222 for (pns = ctl->sc_flags & SC_IETF ? PNS_INIT : PNS_APP; pns < N_PNS; ++pns) 223 TAILQ_FOREACH(packet_out, &ctl->sc_unacked_packets[pns], po_next) 224 if (packet_out->po_flags & PO_HELLO) 225 return 1; 226 return 0; 227} 228 229 230static enum retx_mode 231get_retx_mode (const lsquic_send_ctl_t *ctl) 232{ 233 if (!(ctl->sc_conn_pub->lconn->cn_flags & LSCONN_HANDSHAKE_DONE) 234 && have_unacked_handshake_packets(ctl)) 235 return RETX_MODE_HANDSHAKE; 236 if (ctl->sc_loss_to) 237 return RETX_MODE_LOSS; 238 if (ctl->sc_n_tlp < 2) 239 return RETX_MODE_TLP; 240 return RETX_MODE_RTO; 241} 242 243 244static lsquic_time_t 245get_retx_delay (const struct lsquic_rtt_stats *rtt_stats) 246{ 247 lsquic_time_t srtt, delay; 248 249 srtt = lsquic_rtt_stats_get_srtt(rtt_stats); 250 if (srtt) 251 { 252 delay = srtt + 4 * lsquic_rtt_stats_get_rttvar(rtt_stats); 253 if (delay < MIN_RTO_DELAY) 254 delay = MIN_RTO_DELAY; 255 } 256 else 257 delay = DEFAULT_RETX_DELAY; 258 259 return delay; 260} 261 262 263static void 264retx_alarm_rings (enum alarm_id al_id, void *ctx, lsquic_time_t expiry, lsquic_time_t now) 265{ 266 lsquic_send_ctl_t *ctl = ctx; 267 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 268 lsquic_packet_out_t *packet_out; 269 enum packnum_space pns; 270 enum retx_mode rm; 271 272 pns = al_id - AL_RETX_INIT; 273 274 /* This is a callback -- before it is called, the alarm is unset */ 275 assert(!lsquic_alarmset_is_set(ctl->sc_alset, AL_RETX_INIT + pns)); 276 277 rm = get_retx_mode(ctl); 278 LSQ_INFO("retx timeout, mode %s", retx2str[rm]); 279 280 switch (rm) 281 { 282 case RETX_MODE_HANDSHAKE: 283 send_ctl_expire(ctl, pns, EXFI_HSK); 284 /* Do not register cubic loss during handshake */ 285 break; 286 case RETX_MODE_LOSS: 287 send_ctl_detect_losses(ctl, pns, now); 288 break; 289 case RETX_MODE_TLP: 290 ++ctl->sc_n_tlp; 291 send_ctl_expire(ctl, pns, EXFI_LAST); 292 break; 293 case RETX_MODE_RTO: 294 ctl->sc_last_rto_time = now; 295 ++ctl->sc_n_consec_rtos; 296 ctl->sc_next_limit = 2; 297 LSQ_DEBUG("packet RTO is %"PRIu64" usec", expiry); 298 send_ctl_expire(ctl, pns, EXFI_ALL); 299 ctl->sc_ci->cci_timeout(CGP(ctl)); 300 if (lconn->cn_if->ci_retx_timeout) 301 lconn->cn_if->ci_retx_timeout(lconn); 302 break; 303 } 304 305 packet_out = send_ctl_first_unacked_retx_packet(ctl, pns); 306 if (packet_out) 307 set_retx_alarm(ctl, pns, now); 308 lsquic_send_ctl_sanity_check(ctl); 309} 310 311 312static lsquic_packno_t 313first_packno (const struct lsquic_send_ctl *ctl) 314{ 315 if (ctl->sc_flags & SC_IETF) 316 return 0; 317 else 318 return 1; 319} 320 321 322static void 323send_ctl_pick_initial_packno (struct lsquic_send_ctl *ctl) 324{ 325#ifndef NDEBUG 326 lsquic_packno_t packno; 327 const char *s; 328 329 if (!(ctl->sc_conn_pub->lconn->cn_flags & LSCONN_SERVER) 330 && (s = getenv("LSQUIC_STARTING_PACKNO"), s != NULL)) 331 { 332 packno = (lsquic_packno_t) strtoull(s, NULL, 10); 333 LSQ_DEBUG("starting sending packet numbers starting with %"PRIu64 334 " based on environment variable", packno); 335 ctl->sc_cur_packno = packno - 1; 336 } 337 else 338#endif 339 ctl->sc_cur_packno = first_packno(ctl) - 1; 340} 341 342 343void 344lsquic_send_ctl_init (lsquic_send_ctl_t *ctl, struct lsquic_alarmset *alset, 345 struct lsquic_engine_public *enpub, const struct ver_neg *ver_neg, 346 struct lsquic_conn_public *conn_pub, enum send_ctl_flags flags) 347{ 348 unsigned i; 349 memset(ctl, 0, sizeof(*ctl)); 350 TAILQ_INIT(&ctl->sc_scheduled_packets); 351 TAILQ_INIT(&ctl->sc_unacked_packets[PNS_INIT]); 352 TAILQ_INIT(&ctl->sc_unacked_packets[PNS_HSK]); 353 TAILQ_INIT(&ctl->sc_unacked_packets[PNS_APP]); 354 TAILQ_INIT(&ctl->sc_lost_packets); 355 TAILQ_INIT(&ctl->sc_0rtt_stash); 356 ctl->sc_enpub = enpub; 357 ctl->sc_alset = alset; 358 ctl->sc_ver_neg = ver_neg; 359 ctl->sc_conn_pub = conn_pub; 360 assert(!(flags & ~(SC_IETF|SC_NSTP|SC_ECN))); 361 ctl->sc_flags = flags; 362 send_ctl_pick_initial_packno(ctl); 363 if (enpub->enp_settings.es_pace_packets) 364 ctl->sc_flags |= SC_PACE; 365 if (flags & SC_ECN) 366 ctl->sc_ecn = ECN_ECT0; 367 else 368 ctl->sc_ecn = ECN_NOT_ECT; 369 if (flags & SC_IETF) 370 ctl->sc_retx_frames = IQUIC_FRAME_RETX_MASK; 371 else 372 ctl->sc_retx_frames = GQUIC_FRAME_RETRANSMITTABLE_MASK; 373 lsquic_alarmset_init_alarm(alset, AL_RETX_INIT, retx_alarm_rings, ctl); 374 lsquic_alarmset_init_alarm(alset, AL_RETX_HSK, retx_alarm_rings, ctl); 375 lsquic_alarmset_init_alarm(alset, AL_RETX_APP, retx_alarm_rings, ctl); 376 lsquic_senhist_init(&ctl->sc_senhist, ctl->sc_flags & SC_IETF); 377#ifndef NDEBUG 378 /* TODO: the logic to select the "previously sent" packno should not be 379 * duplicated here and in lsquic_senhist_init()... 380 */ 381 if (!(ctl->sc_conn_pub->lconn->cn_flags & LSCONN_SERVER)) 382 ctl->sc_senhist.sh_last_sent = ctl->sc_cur_packno; 383#endif 384 switch (enpub->enp_settings.es_cc_algo) 385 { 386 case 1: 387 ctl->sc_ci = &lsquic_cong_cubic_if; 388 ctl->sc_cong_ctl = &ctl->sc_adaptive_cc.acc_cubic; 389 break; 390 case 2: 391 ctl->sc_ci = &lsquic_cong_bbr_if; 392 ctl->sc_cong_ctl = &ctl->sc_adaptive_cc.acc_bbr; 393 break; 394 case 3: 395 default: 396 ctl->sc_ci = &lsquic_cong_adaptive_if; 397 ctl->sc_cong_ctl = &ctl->sc_adaptive_cc; 398 break; 399 } 400 ctl->sc_ci->cci_init(CGP(ctl), conn_pub, ctl->sc_retx_frames); 401 if (ctl->sc_flags & SC_PACE) 402 lsquic_pacer_init(&ctl->sc_pacer, conn_pub->lconn, 403 /* TODO: conn_pub has a pointer to enpub: drop third argument */ 404 enpub->enp_settings.es_clock_granularity); 405 for (i = 0; i < sizeof(ctl->sc_buffered_packets) / 406 sizeof(ctl->sc_buffered_packets[0]); ++i) 407 TAILQ_INIT(&ctl->sc_buffered_packets[i].bpq_packets); 408 ctl->sc_max_packno_bits = PACKNO_BITS_2; /* Safe value before verneg */ 409 ctl->sc_cached_bpt.stream_id = UINT64_MAX; 410#if LSQUIC_EXTRA_CHECKS 411 ctl->sc_flags |= SC_SANITY_CHECK; 412 LSQ_DEBUG("sanity checks enabled"); 413#endif 414 ctl->sc_gap = UINT64_MAX - 1 /* Can't have +1 == 0 */; 415 if ((ctl->sc_conn_pub->lconn->cn_flags & (LSCONN_IETF|LSCONN_SERVER)) 416 == (LSCONN_IETF|LSCONN_SERVER)) 417 ctl->sc_can_send = send_ctl_can_send_pre_hsk; 418 else 419 ctl->sc_can_send = send_ctl_can_send; 420 ctl->sc_reord_thresh = N_NACKS_BEFORE_RETX; 421#if LSQUIC_DEVEL 422 const char *s; 423 s = getenv("LSQUIC_DYN_PTHRESH"); 424 if (s == NULL || atoi(s)) 425 ctl->sc_flags |= SC_DYN_PTHRESH; 426#endif 427} 428 429 430static lsquic_time_t 431calculate_packet_rto (lsquic_send_ctl_t *ctl) 432{ 433 lsquic_time_t delay; 434 435 delay = get_retx_delay(&ctl->sc_conn_pub->rtt_stats); 436 437 unsigned exp = ctl->sc_n_consec_rtos; 438 if (exp > MAX_RTO_BACKOFFS) 439 exp = MAX_RTO_BACKOFFS; 440 441 delay = delay * (1 << exp); 442 443 return delay; 444} 445 446 447static lsquic_time_t 448calculate_tlp_delay (lsquic_send_ctl_t *ctl) 449{ 450 lsquic_time_t srtt, delay; 451 452 srtt = lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats); 453 if (ctl->sc_n_in_flight_all > 1) 454 { 455 delay = 10000; /* 10 ms is the minimum tail loss probe delay */ 456 if (delay < 2 * srtt) 457 delay = 2 * srtt; 458 } 459 else 460 { 461 delay = srtt + srtt / 2 + ctl->sc_conn_pub->max_peer_ack_usec; 462 if (delay < 2 * srtt) 463 delay = 2 * srtt; 464 } 465 466 return delay; 467} 468 469 470static void 471set_retx_alarm (struct lsquic_send_ctl *ctl, enum packnum_space pns, 472 lsquic_time_t now) 473{ 474 enum retx_mode rm; 475 lsquic_time_t delay; 476 477 assert(!TAILQ_EMPTY(&ctl->sc_unacked_packets[pns])); 478 479 rm = get_retx_mode(ctl); 480 switch (rm) 481 { 482 case RETX_MODE_HANDSHAKE: 483 /* [draft-iyengar-quic-loss-recovery-01]: 484 * 485 * if (handshake packets are outstanding): 486 * alarm_duration = max(1.5 * smoothed_rtt, 10ms) << handshake_count; 487 * handshake_count++; 488 */ 489 delay = lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats); 490 if (delay) 491 { 492 delay += delay / 2; 493 if (10000 > delay) 494 delay = 10000; 495 } 496 else 497 delay = 150000; 498 delay <<= ctl->sc_n_hsk; 499 ++ctl->sc_n_hsk; 500 break; 501 case RETX_MODE_LOSS: 502 delay = ctl->sc_loss_to; 503 break; 504 case RETX_MODE_TLP: 505 delay = calculate_tlp_delay(ctl); 506 break; 507 default: 508 assert(rm == RETX_MODE_RTO); 509 /* XXX the comment below as well as the name of the function 510 * that follows seem obsolete. 511 */ 512 /* Base RTO on the first unacked packet, following reference 513 * implementation. 514 */ 515 delay = calculate_packet_rto(ctl); 516 break; 517 } 518 519 if (delay > MAX_RTO_DELAY) 520 delay = MAX_RTO_DELAY; 521 522 LSQ_DEBUG("set retx alarm to %"PRIu64", which is %"PRIu64 523 " usec from now, mode %s", now + delay, delay, retx2str[rm]); 524 lsquic_alarmset_set(ctl->sc_alset, AL_RETX_INIT + pns, now + delay); 525 526 if (PNS_APP == pns 527 && ctl->sc_ci == &lsquic_cong_bbr_if 528 && lsquic_alarmset_is_inited(ctl->sc_alset, AL_PACK_TOL) 529 && !lsquic_alarmset_is_set(ctl->sc_alset, AL_PACK_TOL)) 530 lsquic_alarmset_set(ctl->sc_alset, AL_PACK_TOL, now + delay); 531} 532 533 534#define SC_PACK_SIZE(ctl_) (+(ctl_)->sc_conn_pub->path->np_pack_size) 535 536/* XXX can we optimize this by caching the value of this function? It should 537 * not change within one tick. 538 */ 539static lsquic_time_t 540send_ctl_transfer_time (void *ctx) 541{ 542 lsquic_send_ctl_t *const ctl = ctx; 543 lsquic_time_t tx_time; 544 uint64_t pacing_rate; 545 int in_recovery; 546 547 in_recovery = send_ctl_in_recovery(ctl); 548 pacing_rate = ctl->sc_ci->cci_pacing_rate(CGP(ctl), in_recovery); 549 if (!pacing_rate) 550 pacing_rate = 1; 551 tx_time = (uint64_t) SC_PACK_SIZE(ctl) * 1000000 / pacing_rate; 552 return tx_time; 553} 554 555 556static void 557send_ctl_unacked_append (struct lsquic_send_ctl *ctl, 558 struct lsquic_packet_out *packet_out) 559{ 560 enum packnum_space pns; 561 562 pns = lsquic_packet_out_pns(packet_out); 563 assert(0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON))); 564 TAILQ_INSERT_TAIL(&ctl->sc_unacked_packets[pns], packet_out, po_next); 565 packet_out->po_flags |= PO_UNACKED; 566 ctl->sc_bytes_unacked_all += packet_out_sent_sz(packet_out); 567 ctl->sc_n_in_flight_all += 1; 568 if (packet_out->po_frame_types & ctl->sc_retx_frames) 569 { 570 ctl->sc_bytes_unacked_retx += packet_out_total_sz(packet_out); 571 ++ctl->sc_n_in_flight_retx; 572 } 573} 574 575 576static void 577send_ctl_unacked_remove (struct lsquic_send_ctl *ctl, 578 struct lsquic_packet_out *packet_out, unsigned packet_sz) 579{ 580 enum packnum_space pns; 581 582 pns = lsquic_packet_out_pns(packet_out); 583 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, po_next); 584 packet_out->po_flags &= ~PO_UNACKED; 585 assert(ctl->sc_bytes_unacked_all >= packet_sz); 586 ctl->sc_bytes_unacked_all -= packet_sz; 587 ctl->sc_n_in_flight_all -= 1; 588 if (packet_out->po_frame_types & ctl->sc_retx_frames) 589 { 590 ctl->sc_bytes_unacked_retx -= packet_sz; 591 --ctl->sc_n_in_flight_retx; 592 } 593} 594 595 596static void 597send_ctl_sched_Xpend_common (struct lsquic_send_ctl *ctl, 598 struct lsquic_packet_out *packet_out) 599{ 600 packet_out->po_flags |= PO_SCHED; 601 ++ctl->sc_n_scheduled; 602 ctl->sc_bytes_scheduled += packet_out_total_sz(packet_out); 603 lsquic_send_ctl_sanity_check(ctl); 604} 605 606 607static void 608send_ctl_sched_append (struct lsquic_send_ctl *ctl, 609 struct lsquic_packet_out *packet_out) 610{ 611 TAILQ_INSERT_TAIL(&ctl->sc_scheduled_packets, packet_out, po_next); 612 send_ctl_sched_Xpend_common(ctl, packet_out); 613} 614 615 616static void 617send_ctl_sched_prepend (struct lsquic_send_ctl *ctl, 618 struct lsquic_packet_out *packet_out) 619{ 620 TAILQ_INSERT_HEAD(&ctl->sc_scheduled_packets, packet_out, po_next); 621 send_ctl_sched_Xpend_common(ctl, packet_out); 622} 623 624 625static void 626send_ctl_sched_remove (struct lsquic_send_ctl *ctl, 627 struct lsquic_packet_out *packet_out) 628{ 629 TAILQ_REMOVE(&ctl->sc_scheduled_packets, packet_out, po_next); 630 packet_out->po_flags &= ~PO_SCHED; 631 assert(ctl->sc_n_scheduled); 632 --ctl->sc_n_scheduled; 633 ctl->sc_bytes_scheduled -= packet_out_total_sz(packet_out); 634 lsquic_send_ctl_sanity_check(ctl); 635} 636 637 638/* Poisoned packets are used to detect optimistic ACK attacks. We only 639 * use a single poisoned packet at a time. 640 */ 641static int 642send_ctl_add_poison (struct lsquic_send_ctl *ctl) 643{ 644 struct lsquic_packet_out *poison; 645 646 /* XXX Allocating the poison packet out of the regular pool can fail. 647 * This leads to a lot of error checking that could be skipped if we 648 * did not have to allocate this packet at all. 649 */ 650 poison = lsquic_malo_get(ctl->sc_conn_pub->packet_out_malo); 651 if (!poison) 652 return -1; 653 654 memset(poison, 0, sizeof(*poison)); 655 poison->po_flags = PO_UNACKED|PO_POISON; 656 poison->po_packno = ctl->sc_gap; 657 poison->po_loss_chain = poison; /* Won't be used, but just in case */ 658 TAILQ_INSERT_TAIL(&ctl->sc_unacked_packets[PNS_APP], poison, po_next); 659 LSQ_DEBUG("insert poisoned packet %"PRIu64, poison->po_packno); 660 ctl->sc_flags |= SC_POISON; 661 return 0; 662} 663 664 665static void 666send_ctl_reschedule_poison (struct lsquic_send_ctl *ctl) 667{ 668 struct lsquic_packet_out *poison; 669 enum lsq_log_level log_level; 670 lsquic_time_t approx_now; 671 672 TAILQ_FOREACH(poison, &ctl->sc_unacked_packets[PNS_APP], po_next) 673 if (poison->po_flags & PO_POISON) 674 { 675 LSQ_DEBUG("remove poisoned packet %"PRIu64, poison->po_packno); 676 TAILQ_REMOVE(&ctl->sc_unacked_packets[PNS_APP], poison, po_next); 677 lsquic_malo_put(poison); 678 lsquic_send_ctl_begin_optack_detection(ctl); 679 ctl->sc_flags &= ~SC_POISON; 680 return; 681 } 682 683 approx_now = ctl->sc_last_sent_time; 684 if (0 == ctl->sc_enpub->enp_last_warning[WT_NO_POISON] 685 || ctl->sc_enpub->enp_last_warning[WT_NO_POISON] 686 + WARNING_INTERVAL < approx_now) 687 { 688 ctl->sc_enpub->enp_last_warning[WT_NO_POISON] = approx_now; 689 log_level = LSQ_LOG_WARN; 690 } 691 else 692 log_level = LSQ_LOG_DEBUG; 693 LSQ_LOG(log_level, "odd: poisoned packet %"PRIu64" not found during " 694 "reschedule, flag: %d", ctl->sc_gap, !!(ctl->sc_flags & SC_POISON)); 695} 696 697 698static int 699send_ctl_update_poison_hist (struct lsquic_send_ctl *ctl, 700 lsquic_packno_t packno) 701{ 702 if (packno == ctl->sc_gap + 1) 703 { 704 assert(!(ctl->sc_flags & SC_POISON)); 705 lsquic_senhist_add(&ctl->sc_senhist, ctl->sc_gap); 706 if (0 != send_ctl_add_poison(ctl)) 707 return -1; 708 } 709 710 return 0; 711} 712 713 714void 715lsquic_send_ctl_mtu_not_sent (struct lsquic_send_ctl *ctl, 716 struct lsquic_packet_out *packet_out) 717{ 718 (void) /* See comment in send_ctl_add_poison(): the plan is to make 719 this code path always succeed. */ 720 send_ctl_update_poison_hist(ctl, packet_out->po_packno); 721 lsquic_senhist_add(&ctl->sc_senhist, packet_out->po_packno); 722} 723 724 725int 726lsquic_send_ctl_sent_packet (lsquic_send_ctl_t *ctl, 727 struct lsquic_packet_out *packet_out) 728{ 729 enum packnum_space pns; 730 char frames[lsquic_frame_types_str_sz]; 731 732 assert(!(packet_out->po_flags & PO_ENCRYPTED)); 733 ctl->sc_last_sent_time = packet_out->po_sent; 734 pns = lsquic_packet_out_pns(packet_out); 735 if (0 != send_ctl_update_poison_hist(ctl, packet_out->po_packno)) 736 return -1; 737 LSQ_DEBUG("packet %"PRIu64" has been sent (frame types: %s)", 738 packet_out->po_packno, lsquic_frame_types_to_str(frames, 739 sizeof(frames), packet_out->po_frame_types)); 740 lsquic_senhist_add(&ctl->sc_senhist, packet_out->po_packno); 741 if (ctl->sc_ci->cci_sent) 742 ctl->sc_ci->cci_sent(CGP(ctl), packet_out, ctl->sc_bytes_unacked_all, 743 ctl->sc_flags & SC_APP_LIMITED); 744 send_ctl_unacked_append(ctl, packet_out); 745 if (packet_out->po_frame_types & ctl->sc_retx_frames) 746 { 747 if (!lsquic_alarmset_is_set(ctl->sc_alset, AL_RETX_INIT + pns)) 748 set_retx_alarm(ctl, pns, packet_out->po_sent); 749 if (ctl->sc_n_in_flight_retx == 1) 750 ctl->sc_flags |= SC_WAS_QUIET; 751 } 752 /* TODO: Do we really want to use those for RTT info? Revisit this. */ 753 /* Hold on to packets that are not retransmittable because we need them 754 * to sample RTT information. They are released when ACK is received. 755 */ 756#if LSQUIC_SEND_STATS 757 ++ctl->sc_stats.n_total_sent; 758#endif 759 lsquic_send_ctl_sanity_check(ctl); 760 return 0; 761} 762 763 764static void 765send_ctl_select_cc (struct lsquic_send_ctl *ctl) 766{ 767 lsquic_time_t srtt; 768 769 srtt = lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats); 770 771 if (srtt <= ctl->sc_enpub->enp_settings.es_cc_rtt_thresh) 772 { 773 LSQ_INFO("srtt is %"PRIu64" usec, which is smaller than or equal to " 774 "the threshold of %u usec: select Cubic congestion controller", 775 srtt, ctl->sc_enpub->enp_settings.es_cc_rtt_thresh); 776 ctl->sc_ci = &lsquic_cong_cubic_if; 777 ctl->sc_cong_ctl = &ctl->sc_adaptive_cc.acc_cubic; 778 ctl->sc_flags |= SC_CLEANUP_BBR; 779 } 780 else 781 { 782 LSQ_INFO("srtt is %"PRIu64" usec, which is greater than the threshold " 783 "of %u usec: select BBRv1 congestion controller", srtt, 784 ctl->sc_enpub->enp_settings.es_cc_rtt_thresh); 785 ctl->sc_ci = &lsquic_cong_bbr_if; 786 ctl->sc_cong_ctl = &ctl->sc_adaptive_cc.acc_bbr; 787 } 788} 789 790 791static void 792take_rtt_sample (lsquic_send_ctl_t *ctl, 793 lsquic_time_t now, lsquic_time_t lack_delta) 794{ 795 const lsquic_packno_t packno = ctl->sc_largest_acked_packno; 796 const lsquic_time_t sent = ctl->sc_largest_acked_sent_time; 797 const lsquic_time_t measured_rtt = now - sent; 798 if (packno > ctl->sc_max_rtt_packno && lack_delta < measured_rtt) 799 { 800 if (UNLIKELY(ctl->sc_flags & SC_ROUGH_RTT)) 801 { 802 memset(&ctl->sc_conn_pub->rtt_stats, 0, 803 sizeof(ctl->sc_conn_pub->rtt_stats)); 804 ctl->sc_flags &= ~SC_ROUGH_RTT; 805 } 806 ctl->sc_max_rtt_packno = packno; 807 lsquic_rtt_stats_update(&ctl->sc_conn_pub->rtt_stats, measured_rtt, lack_delta); 808 LSQ_DEBUG("packno %"PRIu64"; rtt: %"PRIu64"; delta: %"PRIu64"; " 809 "new srtt: %"PRIu64, packno, measured_rtt, lack_delta, 810 lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats)); 811 if (ctl->sc_ci == &lsquic_cong_adaptive_if) 812 send_ctl_select_cc(ctl); 813 } 814} 815 816 817static void 818send_ctl_return_enc_data (struct lsquic_send_ctl *ctl, 819 struct lsquic_packet_out *packet_out) 820{ 821 ctl->sc_enpub->enp_pmi->pmi_return(ctl->sc_enpub->enp_pmi_ctx, 822 packet_out->po_path->np_peer_ctx, 823 packet_out->po_enc_data, lsquic_packet_out_ipv6(packet_out)); 824 packet_out->po_flags &= ~PO_ENCRYPTED; 825 packet_out->po_enc_data = NULL; 826} 827 828 829static void 830send_ctl_destroy_packet (struct lsquic_send_ctl *ctl, 831 struct lsquic_packet_out *packet_out) 832{ 833 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON))) 834 lsquic_packet_out_destroy(packet_out, ctl->sc_enpub, 835 packet_out->po_path->np_peer_ctx); 836 else 837 lsquic_malo_put(packet_out); 838} 839 840 841static void 842send_ctl_maybe_renumber_sched_to_right (struct lsquic_send_ctl *ctl, 843 const struct lsquic_packet_out *cur) 844{ 845 struct lsquic_packet_out *packet_out; 846 847 /* If current packet has PO_REPACKNO set, it means that all those to the 848 * right of it have this flag set as well. 849 */ 850 if (0 == (cur->po_flags & PO_REPACKNO)) 851 { 852 ctl->sc_cur_packno = cur->po_packno - 1; 853 for (packet_out = TAILQ_NEXT(cur, po_next); 854 packet_out && 0 == (packet_out->po_flags & PO_REPACKNO); 855 packet_out = TAILQ_NEXT(packet_out, po_next)) 856 { 857 packet_out->po_flags |= PO_REPACKNO; 858 } 859 } 860} 861 862 863/* The third argument to advance `next' pointer when modifying the unacked 864 * queue. This is because the unacked queue may contain several elements 865 * of the same chain. This is not true of the lost and scheduled packet 866 * queue, as the loss records are only present on the unacked queue. 867 */ 868static void 869send_ctl_destroy_chain (struct lsquic_send_ctl *ctl, 870 struct lsquic_packet_out *const packet_out, 871 struct lsquic_packet_out **next) 872{ 873 struct lsquic_packet_out *chain_cur, *chain_next; 874 unsigned packet_sz, count; 875 enum packnum_space pns = lsquic_packet_out_pns(packet_out); 876 877 count = 0; 878 for (chain_cur = packet_out->po_loss_chain; chain_cur != packet_out; 879 chain_cur = chain_next) 880 { 881 chain_next = chain_cur->po_loss_chain; 882 switch (chain_cur->po_flags & (PO_SCHED|PO_UNACKED|PO_LOST)) 883 { 884 case PO_SCHED: 885 send_ctl_maybe_renumber_sched_to_right(ctl, chain_cur); 886 send_ctl_sched_remove(ctl, chain_cur); 887 break; 888 case PO_UNACKED: 889 if (chain_cur->po_flags & PO_LOSS_REC) 890 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], chain_cur, po_next); 891 else 892 { 893 packet_sz = packet_out_sent_sz(chain_cur); 894 send_ctl_unacked_remove(ctl, chain_cur, packet_sz); 895 } 896 break; 897 case PO_LOST: 898 TAILQ_REMOVE(&ctl->sc_lost_packets, chain_cur, po_next); 899 break; 900 case 0: 901 /* This is also weird, but let it pass */ 902 break; 903 default: 904 assert(0); 905 break; 906 } 907 if (next && *next == chain_cur) 908 *next = TAILQ_NEXT(*next, po_next); 909 if (0 == (chain_cur->po_flags & PO_LOSS_REC)) 910 lsquic_packet_out_ack_streams(chain_cur); 911 send_ctl_destroy_packet(ctl, chain_cur); 912 ++count; 913 } 914 packet_out->po_loss_chain = packet_out; 915 916 if (count) 917 LSQ_DEBUG("destroyed %u packet%.*s in chain of packet %"PRIu64, 918 count, count != 1, "s", packet_out->po_packno); 919} 920 921 922static struct lsquic_packet_out * 923send_ctl_record_loss (struct lsquic_send_ctl *ctl, 924 struct lsquic_packet_out *packet_out) 925{ 926 struct lsquic_packet_out *loss_record; 927 928 loss_record = lsquic_malo_get(ctl->sc_conn_pub->packet_out_malo); 929 if (loss_record) 930 { 931 memset(loss_record, 0, sizeof(*loss_record)); 932 loss_record->po_flags = PO_UNACKED|PO_LOSS_REC|PO_SENT_SZ; 933 loss_record->po_flags |= 934 ((packet_out->po_flags >> POPNS_SHIFT) & 3) << POPNS_SHIFT; 935 /* Copy values used in ACK processing: */ 936 loss_record->po_packno = packet_out->po_packno; 937 loss_record->po_sent = packet_out->po_sent; 938 loss_record->po_sent_sz = packet_out_sent_sz(packet_out); 939 loss_record->po_frame_types = packet_out->po_frame_types; 940 /* Insert the loss record into the chain: */ 941 loss_record->po_loss_chain = packet_out->po_loss_chain; 942 packet_out->po_loss_chain = loss_record; 943 /* Place the loss record next to the lost packet we are about to 944 * remove from the list: 945 */ 946 TAILQ_INSERT_BEFORE(packet_out, loss_record, po_next); 947 return loss_record; 948 } 949 else 950 { 951 LSQ_INFO("cannot allocate memory for loss record"); 952 return NULL; 953 } 954} 955 956 957static struct lsquic_packet_out * 958send_ctl_handle_regular_lost_packet (struct lsquic_send_ctl *ctl, 959 lsquic_packet_out_t *packet_out, struct lsquic_packet_out **next) 960{ 961 struct lsquic_packet_out *loss_record; 962 unsigned packet_sz; 963 964 assert(ctl->sc_n_in_flight_all); 965 packet_sz = packet_out_sent_sz(packet_out); 966 967 ++ctl->sc_loss_count; 968#if LSQUIC_CONN_STATS 969 ++ctl->sc_conn_pub->conn_stats->out.lost_packets; 970#endif 971 972 if (packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)) 973 { 974 ctl->sc_flags |= SC_LOST_ACK_INIT << lsquic_packet_out_pns(packet_out); 975 LSQ_DEBUG("lost ACK in packet %"PRIu64, packet_out->po_packno); 976 } 977 978 if (ctl->sc_ci->cci_lost) 979 ctl->sc_ci->cci_lost(CGP(ctl), packet_out, packet_sz); 980 981 /* This is a client-only check, server check happens in mini conn */ 982 if (lsquic_send_ctl_ecn_turned_on(ctl) 983 && 0 == ctl->sc_ecn_total_acked[PNS_INIT] 984 && HETY_INITIAL == packet_out->po_header_type 985 && 3 == packet_out->po_packno) 986 { 987 LSQ_DEBUG("possible ECN black hole during handshake, disable ECN"); 988 lsquic_send_ctl_disable_ecn(ctl); 989 } 990 991 if (packet_out->po_frame_types & ctl->sc_retx_frames) 992 { 993 LSQ_DEBUG("lost retransmittable packet %"PRIu64, 994 packet_out->po_packno); 995 loss_record = send_ctl_record_loss(ctl, packet_out); 996 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 997 TAILQ_INSERT_TAIL(&ctl->sc_lost_packets, packet_out, po_next); 998 packet_out->po_flags |= PO_LOST; 999 return loss_record; 1000 } 1001 else 1002 { 1003 LSQ_DEBUG("lost unretransmittable packet %"PRIu64, 1004 packet_out->po_packno); 1005 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 1006 send_ctl_destroy_chain(ctl, packet_out, next); 1007 send_ctl_destroy_packet(ctl, packet_out); 1008 return NULL; 1009 } 1010} 1011 1012 1013static int 1014send_ctl_handle_lost_mtu_probe (struct lsquic_send_ctl *ctl, 1015 struct lsquic_packet_out *packet_out) 1016{ 1017 unsigned packet_sz; 1018 1019 LSQ_DEBUG("lost MTU probe in packet %"PRIu64, packet_out->po_packno); 1020 packet_sz = packet_out_sent_sz(packet_out); 1021 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 1022 assert(packet_out->po_loss_chain == packet_out); 1023 send_ctl_destroy_packet(ctl, packet_out); 1024 return 0; 1025} 1026 1027 1028/* Returns true if packet was rescheduled, false otherwise. In the latter 1029 * case, you should not dereference packet_out after the function returns. 1030 */ 1031static int 1032send_ctl_handle_lost_packet (struct lsquic_send_ctl *ctl, 1033 struct lsquic_packet_out *packet_out, struct lsquic_packet_out **next) 1034{ 1035 if (0 == (packet_out->po_flags & PO_MTU_PROBE)) 1036 return send_ctl_handle_regular_lost_packet(ctl, packet_out, next) != NULL; 1037 else 1038 return send_ctl_handle_lost_mtu_probe(ctl, packet_out); 1039} 1040 1041 1042static lsquic_packno_t 1043largest_retx_packet_number (const struct lsquic_send_ctl *ctl, 1044 enum packnum_space pns) 1045{ 1046 const lsquic_packet_out_t *packet_out; 1047 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_unacked_packets[pns], 1048 lsquic_packets_tailq, po_next) 1049 { 1050 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON)) 1051 && (packet_out->po_frame_types & ctl->sc_retx_frames)) 1052 return packet_out->po_packno; 1053 } 1054 return 0; 1055} 1056 1057 1058static void 1059send_ctl_loss_event (struct lsquic_send_ctl *ctl) 1060{ 1061 ctl->sc_ci->cci_loss(CGP(ctl)); 1062 if (ctl->sc_flags & SC_PACE) 1063 lsquic_pacer_loss_event(&ctl->sc_pacer); 1064 ctl->sc_largest_sent_at_cutback = 1065 lsquic_senhist_largest(&ctl->sc_senhist); 1066} 1067 1068 1069/* Return true if losses were detected, false otherwise */ 1070static int 1071send_ctl_detect_losses (struct lsquic_send_ctl *ctl, enum packnum_space pns, 1072 lsquic_time_t time) 1073{ 1074 struct lsquic_packet_out *packet_out, *next, *loss_record; 1075 lsquic_packno_t largest_retx_packno, largest_lost_packno; 1076 1077 largest_retx_packno = largest_retx_packet_number(ctl, pns); 1078 largest_lost_packno = 0; 1079 ctl->sc_loss_to = 0; 1080 1081 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); 1082 packet_out && packet_out->po_packno <= ctl->sc_largest_acked_packno; 1083 packet_out = next) 1084 { 1085 next = TAILQ_NEXT(packet_out, po_next); 1086 1087 if (packet_out->po_flags & (PO_LOSS_REC|PO_POISON)) 1088 continue; 1089 1090 if (packet_out->po_packno + ctl->sc_reord_thresh < 1091 ctl->sc_largest_acked_packno) 1092 { 1093 LSQ_DEBUG("loss by FACK detected (dist: %"PRIu64"), packet %"PRIu64, 1094 ctl->sc_largest_acked_packno - packet_out->po_packno, 1095 packet_out->po_packno); 1096 if (0 == (packet_out->po_flags & PO_MTU_PROBE)) 1097 { 1098 largest_lost_packno = packet_out->po_packno; 1099 loss_record = send_ctl_handle_regular_lost_packet(ctl, 1100 packet_out, &next); 1101 if (loss_record) 1102 loss_record->po_lflags |= POL_FACKED; 1103 } 1104 else 1105 send_ctl_handle_lost_mtu_probe(ctl, packet_out); 1106 continue; 1107 } 1108 1109 if (largest_retx_packno 1110 && (packet_out->po_frame_types & ctl->sc_retx_frames) 1111 && 0 == (packet_out->po_flags & PO_MTU_PROBE) 1112 && largest_retx_packno <= ctl->sc_largest_acked_packno) 1113 { 1114 LSQ_DEBUG("loss by early retransmit detected, packet %"PRIu64, 1115 packet_out->po_packno); 1116 largest_lost_packno = packet_out->po_packno; 1117 ctl->sc_loss_to = 1118 lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats) / 4; 1119 LSQ_DEBUG("set sc_loss_to to %"PRIu64", packet %"PRIu64, 1120 ctl->sc_loss_to, packet_out->po_packno); 1121 (void) send_ctl_handle_lost_packet(ctl, packet_out, &next); 1122 continue; 1123 } 1124 1125 if (ctl->sc_largest_acked_sent_time > packet_out->po_sent + 1126 lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats)) 1127 { 1128 LSQ_DEBUG("loss by sent time detected: packet %"PRIu64, 1129 packet_out->po_packno); 1130 if ((packet_out->po_frame_types & ctl->sc_retx_frames) 1131 && 0 == (packet_out->po_flags & PO_MTU_PROBE)) 1132 largest_lost_packno = packet_out->po_packno; 1133 else { /* don't count it as a loss */; } 1134 (void) send_ctl_handle_lost_packet(ctl, packet_out, &next); 1135 continue; 1136 } 1137 } 1138 1139 if (largest_lost_packno > ctl->sc_largest_sent_at_cutback) 1140 { 1141 LSQ_DEBUG("detected new loss: packet %"PRIu64"; new lsac: " 1142 "%"PRIu64, largest_lost_packno, ctl->sc_largest_sent_at_cutback); 1143 send_ctl_loss_event(ctl); 1144 } 1145 else if (largest_lost_packno) 1146 /* Lost packets whose numbers are smaller than the largest packet 1147 * number sent at the time of the last loss event indicate the same 1148 * loss event. This follows NewReno logic, see RFC 6582. 1149 */ 1150 LSQ_DEBUG("ignore loss of packet %"PRIu64" smaller than lsac " 1151 "%"PRIu64, largest_lost_packno, ctl->sc_largest_sent_at_cutback); 1152 1153 return largest_lost_packno > ctl->sc_largest_sent_at_cutback; 1154} 1155 1156 1157static void 1158send_ctl_mtu_probe_acked (struct lsquic_send_ctl *ctl, 1159 struct lsquic_packet_out *packet_out) 1160{ 1161 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 1162 1163 LSQ_DEBUG("MTU probe in packet %"PRIu64" has been ACKed", 1164 packet_out->po_packno); 1165 assert(lconn->cn_if->ci_mtu_probe_acked); 1166 if (lconn->cn_if->ci_mtu_probe_acked) 1167 lconn->cn_if->ci_mtu_probe_acked(lconn, packet_out); 1168} 1169 1170 1171static void 1172send_ctl_maybe_increase_reord_thresh (struct lsquic_send_ctl *ctl, 1173 const struct lsquic_packet_out *loss_record, 1174 lsquic_packno_t prev_largest_acked) 1175{ 1176#if LSQUIC_DEVEL 1177 if (ctl->sc_flags & SC_DYN_PTHRESH) 1178#endif 1179 if ((loss_record->po_lflags & POL_FACKED) 1180 && loss_record->po_packno + ctl->sc_reord_thresh 1181 < prev_largest_acked) 1182 { 1183 ctl->sc_reord_thresh = prev_largest_acked - loss_record->po_packno; 1184 LSQ_DEBUG("packet %"PRIu64" was a spurious loss by FACK, increase " 1185 "reordering threshold to %u", loss_record->po_packno, 1186 ctl->sc_reord_thresh); 1187 } 1188} 1189 1190 1191int 1192lsquic_send_ctl_got_ack (lsquic_send_ctl_t *ctl, 1193 const struct ack_info *acki, 1194 lsquic_time_t ack_recv_time, lsquic_time_t now) 1195{ 1196 const struct lsquic_packno_range *range = 1197 &acki->ranges[ acki->n_ranges - 1 ]; 1198 lsquic_packet_out_t *packet_out, *next; 1199 lsquic_packno_t smallest_unacked; 1200 lsquic_packno_t prev_largest_acked; 1201 lsquic_packno_t ack2ed[2]; 1202 unsigned packet_sz; 1203 int app_limited, losses_detected; 1204 signed char do_rtt, skip_checks; 1205 enum packnum_space pns; 1206 unsigned ecn_total_acked, ecn_ce_cnt, one_rtt_cnt; 1207 1208 pns = acki->pns; 1209 ctl->sc_flags |= SC_ACK_RECV_INIT << pns; 1210 packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); 1211#if __GNUC__ 1212 __builtin_prefetch(packet_out); 1213#endif 1214 1215#if __GNUC__ 1216 if (UNLIKELY(LSQ_LOG_ENABLED(LSQ_LOG_DEBUG))) 1217#endif 1218 LSQ_DEBUG("Got ACK frame, largest acked: %"PRIu64"; delta: %"PRIu64, 1219 largest_acked(acki), acki->lack_delta); 1220 1221 /* Validate ACK first: */ 1222 if (UNLIKELY(largest_acked(acki) 1223 > lsquic_senhist_largest(&ctl->sc_senhist))) 1224 { 1225 LSQ_INFO("at least one packet in ACK range [%"PRIu64" - %"PRIu64"] " 1226 "was never sent", acki->ranges[0].low, acki->ranges[0].high); 1227 return -1; 1228 } 1229 1230 if (ctl->sc_ci->cci_begin_ack) 1231 ctl->sc_ci->cci_begin_ack(CGP(ctl), ack_recv_time, 1232 ctl->sc_bytes_unacked_all); 1233 1234 ecn_total_acked = 0; 1235 ecn_ce_cnt = 0; 1236 one_rtt_cnt = 0; 1237 1238 if (UNLIKELY(ctl->sc_flags & SC_WAS_QUIET)) 1239 { 1240 ctl->sc_flags &= ~SC_WAS_QUIET; 1241 LSQ_DEBUG("ACK comes after a period of quiescence"); 1242 ctl->sc_ci->cci_was_quiet(CGP(ctl), now, ctl->sc_bytes_unacked_all); 1243 if (packet_out && (packet_out->po_frame_types & QUIC_FTBIT_PING) 1244 && ctl->sc_conn_pub->last_prog) 1245 { 1246 LSQ_DEBUG("ACK to PING frame, update last progress to %"PRIu64, 1247 ctl->sc_conn_pub->last_tick); 1248 ctl->sc_conn_pub->last_prog = ctl->sc_conn_pub->last_tick; 1249 } 1250 } 1251 1252 if (UNLIKELY(!packet_out)) 1253 goto no_unacked_packets; 1254 1255 smallest_unacked = packet_out->po_packno; 1256 LSQ_DEBUG("Smallest unacked: %"PRIu64, smallest_unacked); 1257 1258 ack2ed[1] = 0; 1259 1260 if (packet_out->po_packno > largest_acked(acki)) 1261 goto detect_losses; 1262 1263 if (largest_acked(acki) > ctl->sc_cur_rt_end) 1264 { 1265 ++ctl->sc_rt_count; 1266 ctl->sc_cur_rt_end = lsquic_senhist_largest(&ctl->sc_senhist); 1267 } 1268 1269 prev_largest_acked = ctl->sc_largest_acked_packno; 1270 do_rtt = 0, skip_checks = 0; 1271 app_limited = -1; 1272 do 1273 { 1274 next = TAILQ_NEXT(packet_out, po_next); 1275#if __GNUC__ 1276 __builtin_prefetch(next); 1277#endif 1278 if (skip_checks) 1279 goto after_checks; 1280 /* This is faster than binary search in the normal case when the number 1281 * of ranges is not much larger than the number of unacked packets. 1282 */ 1283 while (UNLIKELY(range->high < packet_out->po_packno)) 1284 --range; 1285 if (range->low <= packet_out->po_packno) 1286 { 1287 skip_checks = range == acki->ranges; 1288 if (app_limited < 0) 1289 app_limited = send_ctl_retx_bytes_out(ctl) + 3 * SC_PACK_SIZE(ctl) /* This 1290 is the "maximum burst" parameter */ 1291 < ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 1292 after_checks: 1293 ctl->sc_largest_acked_packno = packet_out->po_packno; 1294 ctl->sc_largest_acked_sent_time = packet_out->po_sent; 1295 ecn_total_acked += lsquic_packet_out_ecn(packet_out) != ECN_NOT_ECT; 1296 ecn_ce_cnt += lsquic_packet_out_ecn(packet_out) == ECN_CE; 1297 one_rtt_cnt += lsquic_packet_out_enc_level(packet_out) == ENC_LEV_FORW; 1298 if (0 == (packet_out->po_flags 1299 & (PO_LOSS_REC|PO_POISON|PO_MTU_PROBE))) 1300 { 1301 packet_sz = packet_out_sent_sz(packet_out); 1302 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 1303 lsquic_packet_out_ack_streams(packet_out); 1304 LSQ_DEBUG("acking via regular record %"PRIu64, 1305 packet_out->po_packno); 1306 } 1307 else if (packet_out->po_flags & PO_LOSS_REC) 1308 { 1309 packet_sz = packet_out->po_sent_sz; 1310 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, 1311 po_next); 1312 LSQ_DEBUG("acking via loss record %"PRIu64, 1313 packet_out->po_packno); 1314 send_ctl_maybe_increase_reord_thresh(ctl, packet_out, 1315 prev_largest_acked); 1316#if LSQUIC_CONN_STATS 1317 ++ctl->sc_conn_pub->conn_stats->out.acked_via_loss; 1318#endif 1319 } 1320 else if (packet_out->po_flags & PO_MTU_PROBE) 1321 { 1322 packet_sz = packet_out_sent_sz(packet_out); 1323 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 1324 send_ctl_mtu_probe_acked(ctl, packet_out); 1325 } 1326 else 1327 { 1328 LSQ_WARN("poisoned packet %"PRIu64" acked", 1329 packet_out->po_packno); 1330 return -1; 1331 } 1332 ack2ed[!!(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK))] 1333 = packet_out->po_ack2ed; 1334 do_rtt |= packet_out->po_packno == largest_acked(acki); 1335 ctl->sc_ci->cci_ack(CGP(ctl), packet_out, packet_sz, now, 1336 app_limited); 1337 send_ctl_destroy_chain(ctl, packet_out, &next); 1338 send_ctl_destroy_packet(ctl, packet_out); 1339 } 1340 packet_out = next; 1341 } 1342 while (packet_out && packet_out->po_packno <= largest_acked(acki)); 1343 1344 if (do_rtt) 1345 { 1346 take_rtt_sample(ctl, ack_recv_time, acki->lack_delta); 1347 ctl->sc_n_consec_rtos = 0; 1348 ctl->sc_n_hsk = 0; 1349 ctl->sc_n_tlp = 0; 1350 } 1351 1352 detect_losses: 1353 losses_detected = send_ctl_detect_losses(ctl, pns, ack_recv_time); 1354 if (send_ctl_first_unacked_retx_packet(ctl, pns)) 1355 set_retx_alarm(ctl, pns, now); 1356 else 1357 { 1358 LSQ_DEBUG("No retransmittable packets: clear alarm"); 1359 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 1360 } 1361 lsquic_send_ctl_sanity_check(ctl); 1362 1363 if ((ctl->sc_flags & SC_NSTP) && ack2ed[1] > ctl->sc_largest_ack2ed[pns]) 1364 ctl->sc_largest_ack2ed[pns] = ack2ed[1]; 1365 1366 if (ctl->sc_n_in_flight_retx == 0) 1367 ctl->sc_flags |= SC_WAS_QUIET; 1368 1369 if (one_rtt_cnt) 1370 ctl->sc_flags |= SC_1RTT_ACKED; 1371 1372 if (lsquic_send_ctl_ecn_turned_on(ctl) && (acki->flags & AI_ECN)) 1373 { 1374 const uint64_t sum = acki->ecn_counts[ECN_ECT0] 1375 + acki->ecn_counts[ECN_ECT1] 1376 + acki->ecn_counts[ECN_CE]; 1377 ctl->sc_ecn_total_acked[pns] += ecn_total_acked; 1378 ctl->sc_ecn_ce_cnt[pns] += ecn_ce_cnt; 1379 if (sum >= ctl->sc_ecn_total_acked[pns]) 1380 { 1381 if (sum > ctl->sc_ecn_total_acked[pns]) 1382 ctl->sc_ecn_total_acked[pns] = sum; 1383 if (acki->ecn_counts[ECN_CE] > ctl->sc_ecn_ce_cnt[pns]) 1384 { 1385 ctl->sc_ecn_ce_cnt[pns] = acki->ecn_counts[ECN_CE]; 1386 if (losses_detected) 1387 /* It's either-or. From [draft-ietf-quic-recovery-29], 1388 * Section 7.4: 1389 " When a loss or ECN-CE marking is detected [...] 1390 */ 1391 LSQ_DEBUG("ECN-CE marking detected, but loss event already " 1392 "accounted for"); 1393 else 1394 { 1395 LSQ_DEBUG("ECN-CE marking detected, issue loss event"); 1396 send_ctl_loss_event(ctl); 1397 } 1398 } 1399 } 1400 else 1401 { 1402 LSQ_INFO("ECN total ACKed (%"PRIu64") is greater than the sum " 1403 "of ECN counters (%"PRIu64"): disable ECN", 1404 ctl->sc_ecn_total_acked[pns], sum); 1405 lsquic_send_ctl_disable_ecn(ctl); 1406 } 1407 } 1408 1409 update_n_stop_waiting: 1410 if (!(ctl->sc_flags & (SC_NSTP|SC_IETF))) 1411 { 1412 if (smallest_unacked > smallest_acked(acki)) 1413 /* Peer is acking packets that have been acked already. Schedule 1414 * ACK and STOP_WAITING frame to chop the range if we get two of 1415 * these in a row. 1416 */ 1417 ++ctl->sc_n_stop_waiting; 1418 else 1419 ctl->sc_n_stop_waiting = 0; 1420 } 1421 lsquic_send_ctl_sanity_check(ctl); 1422 if (ctl->sc_ci->cci_end_ack) 1423 ctl->sc_ci->cci_end_ack(CGP(ctl), ctl->sc_bytes_unacked_all); 1424 if (ctl->sc_gap < smallest_acked(acki)) 1425 send_ctl_reschedule_poison(ctl); 1426 return 0; 1427 1428 no_unacked_packets: 1429 smallest_unacked = lsquic_senhist_largest(&ctl->sc_senhist) + 1; 1430 ctl->sc_flags |= SC_WAS_QUIET; 1431 goto update_n_stop_waiting; 1432} 1433 1434 1435lsquic_packno_t 1436lsquic_send_ctl_smallest_unacked (lsquic_send_ctl_t *ctl) 1437{ 1438 const lsquic_packet_out_t *packet_out; 1439 enum packnum_space pns; 1440 1441 /* Packets are always sent out in order (unless we are reordering them 1442 * on purpose). Thus, the first packet on the unacked packets list has 1443 * the smallest packet number of all packets on that list. 1444 */ 1445 for (pns = ctl->sc_flags & SC_IETF ? PNS_INIT : PNS_APP; pns < N_PNS; ++pns) 1446 if ((packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]))) 1447 /* We're OK with using a loss record */ 1448 return packet_out->po_packno; 1449 1450 return lsquic_senhist_largest(&ctl->sc_senhist) + first_packno(ctl); 1451} 1452 1453 1454static struct lsquic_packet_out * 1455send_ctl_next_lost (lsquic_send_ctl_t *ctl) 1456{ 1457 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 1458 struct lsquic_packet_out *lost_packet; 1459 1460 get_next_lost: 1461 lost_packet = TAILQ_FIRST(&ctl->sc_lost_packets); 1462 if (lost_packet) 1463 { 1464 if (lost_packet->po_frame_types & (1 << QUIC_FRAME_STREAM)) 1465 { 1466 if (0 == (lost_packet->po_flags & PO_MINI)) 1467 { 1468 lsquic_packet_out_elide_reset_stream_frames(lost_packet, 1469 UINT64_MAX); 1470 if (lost_packet->po_regen_sz >= lost_packet->po_data_sz) 1471 { 1472 LSQ_DEBUG("Dropping packet %"PRIu64" from lost queue", 1473 lost_packet->po_packno); 1474 TAILQ_REMOVE(&ctl->sc_lost_packets, lost_packet, po_next); 1475 lost_packet->po_flags &= ~PO_LOST; 1476 send_ctl_destroy_chain(ctl, lost_packet, NULL); 1477 send_ctl_destroy_packet(ctl, lost_packet); 1478 goto get_next_lost; 1479 } 1480 } 1481 else 1482 { 1483 /* Mini connection only ever sends data on stream 1. There 1484 * is nothing to elide: always resend it. 1485 */ 1486 ; 1487 } 1488 } 1489 1490 if (!lsquic_send_ctl_can_send(ctl)) 1491 return NULL; 1492 1493 if (packet_out_total_sz(lost_packet) <= SC_PACK_SIZE(ctl)) 1494 { 1495 pop_lost_packet: 1496 TAILQ_REMOVE(&ctl->sc_lost_packets, lost_packet, po_next); 1497 lost_packet->po_flags &= ~PO_LOST; 1498 lost_packet->po_flags |= PO_RETX; 1499 } 1500 else 1501 { 1502 /* We delay resizing lost packets as long as possible, hoping that 1503 * it may be ACKed. At this point, however, we have to resize. 1504 */ 1505 if (0 == split_lost_packet(ctl, lost_packet)) 1506 { 1507 lost_packet = TAILQ_FIRST(&ctl->sc_lost_packets); 1508 goto pop_lost_packet; 1509 } 1510 lconn->cn_if->ci_internal_error(lconn, 1511 "error resizing lost packet"); 1512 return NULL; 1513 } 1514 } 1515 1516 return lost_packet; 1517} 1518 1519 1520static lsquic_packno_t 1521send_ctl_next_packno (lsquic_send_ctl_t *ctl) 1522{ 1523 lsquic_packno_t packno; 1524 1525 packno = ++ctl->sc_cur_packno; 1526 if (packno == ctl->sc_gap) 1527 packno = ++ctl->sc_cur_packno; 1528 1529 return packno; 1530} 1531 1532 1533void 1534lsquic_send_ctl_cleanup (lsquic_send_ctl_t *ctl) 1535{ 1536 lsquic_packet_out_t *packet_out, *next; 1537 enum packnum_space pns; 1538 unsigned n; 1539 1540 lsquic_senhist_cleanup(&ctl->sc_senhist); 1541 while ((packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets))) 1542 { 1543 send_ctl_sched_remove(ctl, packet_out); 1544 send_ctl_destroy_packet(ctl, packet_out); 1545 } 1546 assert(0 == ctl->sc_n_scheduled); 1547 assert(0 == ctl->sc_bytes_scheduled); 1548 for (pns = PNS_INIT; pns < N_PNS; ++pns) 1549 while ((packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]))) 1550 { 1551 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, po_next); 1552 packet_out->po_flags &= ~PO_UNACKED; 1553#ifndef NDEBUG 1554 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON))) 1555 { 1556 ctl->sc_bytes_unacked_all -= packet_out_sent_sz(packet_out); 1557 --ctl->sc_n_in_flight_all; 1558 } 1559#endif 1560 send_ctl_destroy_packet(ctl, packet_out); 1561 } 1562 assert(0 == ctl->sc_n_in_flight_all); 1563 assert(0 == ctl->sc_bytes_unacked_all); 1564 while ((packet_out = TAILQ_FIRST(&ctl->sc_lost_packets))) 1565 { 1566 TAILQ_REMOVE(&ctl->sc_lost_packets, packet_out, po_next); 1567 packet_out->po_flags &= ~PO_LOST; 1568 send_ctl_destroy_packet(ctl, packet_out); 1569 } 1570 while ((packet_out = TAILQ_FIRST(&ctl->sc_0rtt_stash))) 1571 { 1572 TAILQ_REMOVE(&ctl->sc_0rtt_stash, packet_out, po_next); 1573 send_ctl_destroy_packet(ctl, packet_out); 1574 } 1575 for (n = 0; n < sizeof(ctl->sc_buffered_packets) / 1576 sizeof(ctl->sc_buffered_packets[0]); ++n) 1577 { 1578 for (packet_out = TAILQ_FIRST(&ctl->sc_buffered_packets[n].bpq_packets); 1579 packet_out; packet_out = next) 1580 { 1581 next = TAILQ_NEXT(packet_out, po_next); 1582 send_ctl_destroy_packet(ctl, packet_out); 1583 } 1584 } 1585 if (ctl->sc_flags & SC_PACE) 1586 lsquic_pacer_cleanup(&ctl->sc_pacer); 1587 ctl->sc_ci->cci_cleanup(CGP(ctl)); 1588 if (ctl->sc_flags & SC_CLEANUP_BBR) 1589 { 1590 assert(ctl->sc_ci == &lsquic_cong_cubic_if); 1591 lsquic_cong_bbr_if.cci_cleanup(&ctl->sc_adaptive_cc.acc_bbr); 1592 } 1593#if LSQUIC_SEND_STATS 1594 LSQ_NOTICE("stats: n_total_sent: %u; n_resent: %u; n_delayed: %u", 1595 ctl->sc_stats.n_total_sent, ctl->sc_stats.n_resent, 1596 ctl->sc_stats.n_delayed); 1597#endif 1598 free(ctl->sc_token); 1599} 1600 1601 1602static unsigned 1603send_ctl_retx_bytes_out (const struct lsquic_send_ctl *ctl) 1604{ 1605 return ctl->sc_bytes_scheduled 1606 + ctl->sc_bytes_unacked_retx 1607 ; 1608} 1609 1610 1611static unsigned 1612send_ctl_all_bytes_out (const struct lsquic_send_ctl *ctl) 1613{ 1614 return ctl->sc_bytes_scheduled 1615 + ctl->sc_bytes_unacked_all 1616 ; 1617} 1618 1619 1620int 1621lsquic_send_ctl_pacer_blocked (struct lsquic_send_ctl *ctl) 1622{ 1623#ifdef NDEBUG 1624 return (ctl->sc_flags & SC_PACE) 1625 && !lsquic_pacer_can_schedule(&ctl->sc_pacer, 1626 ctl->sc_n_in_flight_all); 1627#else 1628 if (ctl->sc_flags & SC_PACE) 1629 { 1630 const int blocked = !lsquic_pacer_can_schedule(&ctl->sc_pacer, 1631 ctl->sc_n_in_flight_all); 1632 LSQ_DEBUG("pacer blocked: %d, in_flight_all: %u", blocked, 1633 ctl->sc_n_in_flight_all); 1634 return blocked; 1635 } 1636 else 1637 return 0; 1638#endif 1639} 1640 1641 1642static int 1643send_ctl_can_send (struct lsquic_send_ctl *ctl) 1644{ 1645 const unsigned n_out = send_ctl_all_bytes_out(ctl); 1646 LSQ_DEBUG("%s: n_out: %u (unacked_all: %u); cwnd: %"PRIu64, __func__, 1647 n_out, ctl->sc_bytes_unacked_all, 1648 ctl->sc_ci->cci_get_cwnd(CGP(ctl))); 1649 if (ctl->sc_flags & SC_PACE) 1650 { 1651 if (n_out >= ctl->sc_ci->cci_get_cwnd(CGP(ctl))) 1652 return 0; 1653 if (lsquic_pacer_can_schedule(&ctl->sc_pacer, 1654 ctl->sc_n_scheduled + ctl->sc_n_in_flight_all)) 1655 return 1; 1656 if (ctl->sc_flags & SC_SCHED_TICK) 1657 { 1658 ctl->sc_flags &= ~SC_SCHED_TICK; 1659 lsquic_engine_add_conn_to_attq(ctl->sc_enpub, 1660 ctl->sc_conn_pub->lconn, lsquic_pacer_next_sched(&ctl->sc_pacer), 1661 AEW_PACER); 1662 } 1663 return 0; 1664 } 1665 else 1666 return n_out < ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 1667} 1668 1669 1670static int 1671send_ctl_can_send_pre_hsk (struct lsquic_send_ctl *ctl) 1672{ 1673 unsigned bytes_in, bytes_out; 1674 1675 bytes_in = ctl->sc_conn_pub->bytes_in; 1676 bytes_out = ctl->sc_conn_pub->bytes_out + ctl->sc_bytes_scheduled; 1677 if (bytes_out >= bytes_in * 2 + bytes_in / 2 /* This should work out 1678 to around 3 on average */) 1679 { 1680 LSQ_DEBUG("%s: amplification block: %u bytes in, %u bytes out", 1681 __func__, bytes_in, bytes_out); 1682 return 0; 1683 } 1684 else 1685 return send_ctl_can_send(ctl); 1686} 1687 1688 1689#ifndef NDEBUG 1690#if __GNUC__ 1691__attribute__((weak)) 1692#endif 1693#endif 1694int 1695lsquic_send_ctl_can_send (struct lsquic_send_ctl *ctl) 1696{ 1697 return ctl->sc_can_send(ctl); 1698} 1699 1700 1701/* Like lsquic_send_ctl_can_send(), but no mods */ 1702static int 1703send_ctl_could_send (const struct lsquic_send_ctl *ctl) 1704{ 1705 uint64_t cwnd; 1706 unsigned n_out; 1707 1708 if ((ctl->sc_flags & SC_PACE) && lsquic_pacer_delayed(&ctl->sc_pacer)) 1709 return 0; 1710 1711 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 1712 n_out = send_ctl_all_bytes_out(ctl); 1713 return n_out < cwnd; 1714} 1715 1716 1717void 1718lsquic_send_ctl_maybe_app_limited (struct lsquic_send_ctl *ctl, 1719 const struct network_path *path) 1720{ 1721 const struct lsquic_packet_out *packet_out; 1722 1723 packet_out = lsquic_send_ctl_last_scheduled(ctl, PNS_APP, path, 0); 1724 if ((packet_out && lsquic_packet_out_avail(packet_out) > 10) 1725 || send_ctl_could_send(ctl)) 1726 { 1727 LSQ_DEBUG("app-limited"); 1728 ctl->sc_flags |= SC_APP_LIMITED; 1729 } 1730} 1731 1732 1733static void 1734send_ctl_expire (struct lsquic_send_ctl *ctl, enum packnum_space pns, 1735 enum expire_filter filter) 1736{ 1737 lsquic_packet_out_t *packet_out, *next; 1738 int n_resubmitted; 1739 static const char *const filter_type2str[] = { 1740 [EXFI_ALL] = "all", 1741 [EXFI_HSK] = "handshake", 1742 [EXFI_LAST] = "last", 1743 }; 1744 1745 switch (filter) 1746 { 1747 case EXFI_ALL: 1748 n_resubmitted = 0; 1749 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); 1750 packet_out; packet_out = next) 1751 { 1752 next = TAILQ_NEXT(packet_out, po_next); 1753 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON))) 1754 n_resubmitted += send_ctl_handle_lost_packet(ctl, packet_out, 1755 &next); 1756 } 1757 break; 1758 case EXFI_HSK: 1759 n_resubmitted = 0; 1760 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); packet_out; 1761 packet_out = next) 1762 { 1763 next = TAILQ_NEXT(packet_out, po_next); 1764 if (packet_out->po_flags & PO_HELLO) 1765 n_resubmitted += send_ctl_handle_lost_packet(ctl, packet_out, 1766 &next); 1767 } 1768 break; 1769 default: 1770 assert(filter == EXFI_LAST); 1771 packet_out = send_ctl_last_unacked_retx_packet(ctl, pns); 1772 if (packet_out) 1773 n_resubmitted = send_ctl_handle_lost_packet(ctl, packet_out, NULL); 1774 else 1775 n_resubmitted = 0; 1776 break; 1777 } 1778 1779 LSQ_DEBUG("consider %s packets lost: %d resubmitted", 1780 filter_type2str[filter], n_resubmitted); 1781} 1782 1783 1784void 1785lsquic_send_ctl_expire_all (lsquic_send_ctl_t *ctl) 1786{ 1787 enum packnum_space pns; 1788 1789 for (pns = ctl->sc_flags & SC_IETF ? PNS_INIT : PNS_APP; pns < N_PNS; ++pns) 1790 { 1791 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 1792 send_ctl_expire(ctl, pns, EXFI_ALL); 1793 } 1794 lsquic_send_ctl_sanity_check(ctl); 1795} 1796 1797 1798#ifndef NDEBUG 1799void 1800lsquic_send_ctl_do_sanity_check (const struct lsquic_send_ctl *ctl) 1801{ 1802 const struct lsquic_packet_out *packet_out; 1803 lsquic_packno_t prev_packno; 1804 int prev_packno_set; 1805 unsigned count, bytes; 1806 enum packnum_space pns; 1807 1808#if _MSC_VER 1809 prev_packno = 0; 1810#endif 1811 count = 0, bytes = 0; 1812 for (pns = PNS_INIT; pns <= PNS_APP; ++pns) 1813 { 1814 prev_packno_set = 0; 1815 TAILQ_FOREACH(packet_out, &ctl->sc_unacked_packets[pns], po_next) 1816 { 1817 if (prev_packno_set) 1818 assert(packet_out->po_packno > prev_packno); 1819 else 1820 { 1821 prev_packno = packet_out->po_packno; 1822 prev_packno_set = 1; 1823 } 1824 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON))) 1825 { 1826 bytes += packet_out_sent_sz(packet_out); 1827 ++count; 1828 } 1829 } 1830 } 1831 assert(count == ctl->sc_n_in_flight_all); 1832 assert(bytes == ctl->sc_bytes_unacked_all); 1833 1834 count = 0, bytes = 0; 1835 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1836 { 1837 assert(packet_out->po_flags & PO_SCHED); 1838 bytes += packet_out_total_sz(packet_out); 1839 ++count; 1840 } 1841 assert(count == ctl->sc_n_scheduled); 1842 assert(bytes == ctl->sc_bytes_scheduled); 1843} 1844 1845 1846#endif 1847 1848 1849void 1850lsquic_send_ctl_scheduled_one (lsquic_send_ctl_t *ctl, 1851 lsquic_packet_out_t *packet_out) 1852{ 1853#ifndef NDEBUG 1854 const lsquic_packet_out_t *last; 1855 last = TAILQ_LAST(&ctl->sc_scheduled_packets, lsquic_packets_tailq); 1856 if (last) 1857 assert((last->po_flags & PO_REPACKNO) || 1858 last->po_packno < packet_out->po_packno); 1859#endif 1860 if (ctl->sc_flags & SC_PACE) 1861 { 1862 unsigned n_out = ctl->sc_n_in_flight_retx + ctl->sc_n_scheduled; 1863 lsquic_pacer_packet_scheduled(&ctl->sc_pacer, n_out, 1864 send_ctl_in_recovery(ctl), send_ctl_transfer_time, ctl); 1865 } 1866 send_ctl_sched_append(ctl, packet_out); 1867} 1868 1869 1870/* Wrapper is used to reset the counter when it's been too long */ 1871static unsigned 1872send_ctl_get_n_consec_rtos (struct lsquic_send_ctl *ctl) 1873{ 1874 lsquic_time_t timeout; 1875 1876 if (ctl->sc_n_consec_rtos) 1877 { 1878 timeout = calculate_packet_rto(ctl); 1879 if (ctl->sc_last_rto_time + timeout < ctl->sc_last_sent_time) 1880 { 1881 ctl->sc_n_consec_rtos = 0; 1882 LSQ_DEBUG("reset RTO counter after %"PRIu64" usec", 1883 ctl->sc_last_sent_time - ctl->sc_last_rto_time); 1884 } 1885 } 1886 1887 return ctl->sc_n_consec_rtos; 1888} 1889 1890 1891/* This mimics the logic in lsquic_send_ctl_next_packet_to_send(): we want 1892 * to check whether the first scheduled packet cannot be sent. 1893 */ 1894int 1895lsquic_send_ctl_sched_is_blocked (struct lsquic_send_ctl *ctl) 1896{ 1897 const lsquic_packet_out_t *packet_out 1898 = TAILQ_FIRST(&ctl->sc_scheduled_packets); 1899 return send_ctl_get_n_consec_rtos(ctl) 1900 && 0 == ctl->sc_next_limit 1901 && packet_out 1902 && !(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)); 1903} 1904 1905 1906static void 1907send_ctl_maybe_zero_pad (struct lsquic_send_ctl *ctl, 1908 struct lsquic_packet_out *initial_packet, size_t limit) 1909{ 1910 struct lsquic_packet_out *packet_out; 1911 size_t cum_size, size; 1912 1913 cum_size = packet_out_total_sz(initial_packet); 1914 if (cum_size >= limit) 1915 { 1916 LSQ_DEBUG("packet size %zu larger than %zu-byte limit: not " 1917 "zero-padding", cum_size, limit); 1918 return; 1919 } 1920 1921 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1922 { 1923 size = packet_out_total_sz(packet_out); 1924 if (cum_size + size > limit) 1925 break; 1926 cum_size += size; 1927 if (HETY_NOT_SET == packet_out->po_header_type) 1928 break; 1929 } 1930 1931 LSQ_DEBUG("cum_size: %zu; limit: %zu", cum_size, limit); 1932 assert(cum_size <= limit); 1933 size = limit - cum_size; 1934 if (size > lsquic_packet_out_avail(initial_packet)) 1935 size = lsquic_packet_out_avail(initial_packet); 1936 if (size) 1937 { 1938 memset(initial_packet->po_data + initial_packet->po_data_sz, 0, size); 1939 initial_packet->po_data_sz += size; 1940 initial_packet->po_frame_types |= QUIC_FTBIT_PADDING; 1941 } 1942 LSQ_DEBUG("Added %zu bytes of PADDING to packet %"PRIu64, size, 1943 initial_packet->po_packno); 1944} 1945 1946 1947/* Predict whether lsquic_send_ctl_next_packet_to_send() will return a 1948 * packet by mimicking its logic. Returns true if packet will be returned, 1949 * false otherwise. 1950 */ 1951int 1952lsquic_send_ctl_next_packet_to_send_predict (struct lsquic_send_ctl *ctl) 1953{ 1954 const struct lsquic_packet_out *packet_out; 1955 unsigned n_rtos; 1956 1957 n_rtos = ~0u; 1958 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1959 { 1960 if (!(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)) 1961 && 0 == ctl->sc_next_limit 1962 && 0 != (n_rtos == ~0u ? /* Initialize once */ 1963 (n_rtos = send_ctl_get_n_consec_rtos(ctl)) : n_rtos)) 1964 { 1965 LSQ_DEBUG("send prediction: no, n_rtos: %u", n_rtos); 1966 return 0; 1967 } 1968 if ((packet_out->po_flags & PO_REPACKNO) 1969 && packet_out->po_regen_sz == packet_out->po_data_sz 1970 && packet_out->po_frame_types != QUIC_FTBIT_PATH_CHALLENGE) 1971 { 1972 LSQ_DEBUG("send prediction: packet %"PRIu64" would be dropped, " 1973 "continue", packet_out->po_packno); 1974 continue; 1975 } 1976 LSQ_DEBUG("send prediction: yes, packet %"PRIu64", flags %u, frames 0x%X", 1977 packet_out->po_packno, (unsigned) packet_out->po_flags, 1978 (unsigned) packet_out->po_frame_types); 1979 return 1; 1980 } 1981 1982 LSQ_DEBUG("send prediction: no, no matching scheduled packets"); 1983 return 0; 1984} 1985 1986 1987lsquic_packet_out_t * 1988lsquic_send_ctl_next_packet_to_send (struct lsquic_send_ctl *ctl, 1989 const struct to_coal *to_coal) 1990{ 1991 lsquic_packet_out_t *packet_out; 1992 size_t size; 1993 int dec_limit; 1994 1995 get_packet: 1996 packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); 1997 if (!packet_out) 1998 return NULL; 1999 2000 /* Note: keep logic in this function and in 2001 * lsquic_send_ctl_next_packet_to_send_predict() in synch. 2002 */ 2003 if (!(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)) 2004 && send_ctl_get_n_consec_rtos(ctl)) 2005 { 2006 if (ctl->sc_next_limit) 2007 dec_limit = 1; 2008 else 2009 return NULL; 2010 } 2011 else 2012 dec_limit = 0; 2013 2014 if (packet_out->po_flags & PO_REPACKNO) 2015 { 2016 if (packet_out->po_regen_sz < packet_out->po_data_sz 2017 && packet_out->po_frame_types != QUIC_FTBIT_PADDING) 2018 { 2019 update_for_resending(ctl, packet_out); 2020 packet_out->po_flags &= ~PO_REPACKNO; 2021 } 2022 else 2023 { 2024 LSQ_DEBUG("Dropping packet %"PRIu64" from scheduled queue", 2025 packet_out->po_packno); 2026 send_ctl_sched_remove(ctl, packet_out); 2027 send_ctl_destroy_chain(ctl, packet_out, NULL); 2028 send_ctl_destroy_packet(ctl, packet_out); 2029 goto get_packet; 2030 } 2031 } 2032 2033 if (UNLIKELY(to_coal != NULL)) 2034 { 2035 /* From [draft-ietf-quic-transport-30], Section-12.2: 2036 " Senders MUST NOT coalesce QUIC packets with different connection 2037 " IDs into a single UDP datagram. 2038 */ 2039 if (packet_out_total_sz(packet_out) + to_coal->prev_sz_sum 2040 > SC_PACK_SIZE(ctl) 2041 || !lsquic_packet_out_equal_dcids(to_coal->prev_packet, packet_out)) 2042 return NULL; 2043 LSQ_DEBUG("packet %"PRIu64" (%zu bytes) will be tacked on to " 2044 "previous packet(s) (%zu bytes) (coalescing)", 2045 packet_out->po_packno, packet_out_total_sz(packet_out), 2046 to_coal->prev_sz_sum); 2047 size = to_coal->prev_sz_sum; 2048 } 2049 else 2050 size = 0; 2051 send_ctl_sched_remove(ctl, packet_out); 2052 2053 if (dec_limit) 2054 { 2055 --ctl->sc_next_limit; 2056 packet_out->po_lflags |= POL_LIMITED; 2057 } 2058 else 2059 packet_out->po_lflags &= ~POL_LIMITED; 2060 2061 if (UNLIKELY(packet_out->po_header_type == HETY_INITIAL) 2062 && (!(ctl->sc_conn_pub->lconn->cn_flags & LSCONN_SERVER) 2063 || (packet_out->po_frame_types 2064 & IQUIC_FRAME_ACKABLE_MASK)) 2065 && size < 1200) 2066 { 2067 send_ctl_maybe_zero_pad(ctl, packet_out, 1200 - size); 2068 } 2069 2070 if (ctl->sc_flags & SC_QL_BITS) 2071 { 2072 packet_out->po_lflags |= POL_LOG_QL_BITS; 2073 if (ctl->sc_loss_count) 2074 { 2075 --ctl->sc_loss_count; 2076 packet_out->po_lflags |= POL_LOSS_BIT; 2077 } 2078 else 2079 packet_out->po_lflags &= ~POL_LOSS_BIT; 2080 if (packet_out->po_header_type == HETY_NOT_SET) 2081 { 2082 if (ctl->sc_gap + 1 == packet_out->po_packno) 2083 ++ctl->sc_square_count; 2084 if (ctl->sc_square_count++ & 64) 2085 packet_out->po_lflags |= POL_SQUARE_BIT; 2086 else 2087 packet_out->po_lflags &= ~POL_SQUARE_BIT; 2088 } 2089 } 2090 2091 return packet_out; 2092} 2093 2094 2095void 2096lsquic_send_ctl_delayed_one (lsquic_send_ctl_t *ctl, 2097 lsquic_packet_out_t *packet_out) 2098{ 2099 send_ctl_sched_prepend(ctl, packet_out); 2100 if (packet_out->po_lflags & POL_LIMITED) 2101 ++ctl->sc_next_limit; 2102 LSQ_DEBUG("packet %"PRIu64" has been delayed", packet_out->po_packno); 2103#if LSQUIC_SEND_STATS 2104 ++ctl->sc_stats.n_delayed; 2105#endif 2106 if (packet_out->po_lflags & POL_LOSS_BIT) 2107 ++ctl->sc_loss_count; 2108 if ((ctl->sc_flags & SC_QL_BITS) 2109 && packet_out->po_header_type == HETY_NOT_SET) 2110 ctl->sc_square_count -= 1 + (ctl->sc_gap + 1 == packet_out->po_packno); 2111} 2112 2113 2114int 2115lsquic_send_ctl_have_outgoing_stream_frames (const lsquic_send_ctl_t *ctl) 2116{ 2117 const lsquic_packet_out_t *packet_out; 2118 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2119 if (packet_out->po_frame_types & 2120 ((1 << QUIC_FRAME_STREAM) | (1 << QUIC_FRAME_RST_STREAM))) 2121 return 1; 2122 return 0; 2123} 2124 2125 2126int 2127lsquic_send_ctl_have_outgoing_retx_frames (const lsquic_send_ctl_t *ctl) 2128{ 2129 const lsquic_packet_out_t *packet_out; 2130 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2131 if (packet_out->po_frame_types & ctl->sc_retx_frames) 2132 return 1; 2133 return 0; 2134} 2135 2136 2137static int 2138send_ctl_set_packet_out_token (const struct lsquic_send_ctl *ctl, 2139 struct lsquic_packet_out *packet_out) 2140{ 2141 unsigned char *token; 2142 2143 token = malloc(ctl->sc_token_sz); 2144 if (!token) 2145 { 2146 LSQ_WARN("malloc failed: cannot set initial token"); 2147 return -1; 2148 } 2149 2150 memcpy(token, ctl->sc_token, ctl->sc_token_sz); 2151 packet_out->po_token = token; 2152 packet_out->po_token_len = ctl->sc_token_sz; 2153 packet_out->po_flags |= PO_NONCE; 2154 LSQ_DEBUG("set initial token on packet"); 2155 return 0; 2156} 2157 2158 2159static lsquic_packet_out_t * 2160send_ctl_allocate_packet (struct lsquic_send_ctl *ctl, enum packno_bits bits, 2161 unsigned need_at_least, enum packnum_space pns, 2162 const struct network_path *path) 2163{ 2164 static const enum header_type pns2hety[] = 2165 { 2166 [PNS_INIT] = HETY_INITIAL, 2167 [PNS_HSK] = HETY_HANDSHAKE, 2168 [PNS_APP] = HETY_NOT_SET, 2169 }; 2170 lsquic_packet_out_t *packet_out; 2171 2172 packet_out = lsquic_packet_out_new(&ctl->sc_enpub->enp_mm, 2173 ctl->sc_conn_pub->packet_out_malo, 2174 !(ctl->sc_flags & SC_TCID0), ctl->sc_conn_pub->lconn, bits, 2175 ctl->sc_ver_neg->vn_tag, NULL, path, pns2hety[pns]); 2176 if (!packet_out) 2177 return NULL; 2178 2179 if (need_at_least && lsquic_packet_out_avail(packet_out) < need_at_least) 2180 { /* This should never happen, this is why this check is performed at 2181 * this level and not lower, before the packet is actually allocated. 2182 */ 2183 LSQ_ERROR("wanted to allocate packet with at least %u bytes of " 2184 "payload, but only got %u bytes (mtu: %u bytes)", need_at_least, 2185 lsquic_packet_out_avail(packet_out), SC_PACK_SIZE(ctl)); 2186 send_ctl_destroy_packet(ctl, packet_out); 2187 return NULL; 2188 } 2189 2190 if (UNLIKELY(pns != PNS_APP)) 2191 { 2192 if (pns == PNS_INIT) 2193 { 2194 packet_out->po_header_type = HETY_INITIAL; 2195 if (ctl->sc_token) 2196 { 2197 (void) send_ctl_set_packet_out_token(ctl, packet_out); 2198 if (packet_out->po_n_alloc > packet_out->po_token_len) 2199 packet_out->po_n_alloc -= packet_out->po_token_len; 2200 else 2201 { 2202 /* XXX fail earlier: when retry token is parsed out */ 2203 LSQ_INFO("token is too long: cannot allocate packet"); 2204 return NULL; 2205 } 2206 } 2207 } 2208 else 2209 packet_out->po_header_type = HETY_HANDSHAKE; 2210 } 2211 2212 lsquic_packet_out_set_pns(packet_out, pns); 2213 packet_out->po_lflags |= ctl->sc_ecn << POECN_SHIFT; 2214 packet_out->po_loss_chain = packet_out; 2215 return packet_out; 2216} 2217 2218 2219lsquic_packet_out_t * 2220lsquic_send_ctl_new_packet_out (lsquic_send_ctl_t *ctl, unsigned need_at_least, 2221 enum packnum_space pns, const struct network_path *path) 2222{ 2223 lsquic_packet_out_t *packet_out; 2224 enum packno_bits bits; 2225 2226 bits = lsquic_send_ctl_packno_bits(ctl, pns); 2227 packet_out = send_ctl_allocate_packet(ctl, bits, need_at_least, pns, path); 2228 if (!packet_out) 2229 return NULL; 2230 2231 packet_out->po_packno = send_ctl_next_packno(ctl); 2232 LSQ_DEBUG("created packet %"PRIu64, packet_out->po_packno); 2233 EV_LOG_PACKET_CREATED(LSQUIC_LOG_CONN_ID, packet_out); 2234 return packet_out; 2235} 2236 2237 2238struct lsquic_packet_out * 2239lsquic_send_ctl_last_scheduled (struct lsquic_send_ctl *ctl, 2240 enum packnum_space pns, const struct network_path *path, 2241 int regen_match) 2242{ 2243 struct lsquic_packet_out *packet_out; 2244 2245 if (0 == regen_match) 2246 { 2247 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_scheduled_packets, 2248 lsquic_packets_tailq, po_next) 2249 if (pns == lsquic_packet_out_pns(packet_out) 2250 && path == packet_out->po_path) 2251 return packet_out; 2252 } 2253 else 2254 { 2255 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_scheduled_packets, 2256 lsquic_packets_tailq, po_next) 2257 if (pns == lsquic_packet_out_pns(packet_out) 2258 && packet_out->po_regen_sz == packet_out->po_data_sz 2259 && path == packet_out->po_path) 2260 return packet_out; 2261 } 2262 2263 return NULL; 2264} 2265 2266 2267/* Do not use for STREAM frames 2268 */ 2269lsquic_packet_out_t * 2270lsquic_send_ctl_get_writeable_packet (lsquic_send_ctl_t *ctl, 2271 enum packnum_space pns, unsigned need_at_least, 2272 const struct network_path *path, int regen_match, int *is_err) 2273{ 2274 lsquic_packet_out_t *packet_out; 2275 2276 assert(need_at_least > 0); 2277 2278 packet_out = lsquic_send_ctl_last_scheduled(ctl, pns, path, regen_match); 2279 if (packet_out 2280 && !(packet_out->po_flags & (PO_MINI|PO_STREAM_END|PO_RETX)) 2281 && lsquic_packet_out_avail(packet_out) >= need_at_least) 2282 { 2283 return packet_out; 2284 } 2285 2286 if (!lsquic_send_ctl_can_send(ctl)) 2287 { 2288 if (is_err) 2289 *is_err = 0; 2290 return NULL; 2291 } 2292 2293 packet_out = lsquic_send_ctl_new_packet_out(ctl, need_at_least, pns, path); 2294 if (packet_out) 2295 { 2296 lsquic_packet_out_set_pns(packet_out, pns); 2297 lsquic_send_ctl_scheduled_one(ctl, packet_out); 2298 } 2299 else if (is_err) 2300 *is_err = 1; 2301 return packet_out; 2302} 2303 2304 2305struct lsquic_packet_out * 2306lsquic_send_ctl_get_packet_for_crypto (struct lsquic_send_ctl *ctl, 2307 unsigned need_at_least, enum packnum_space pns, 2308 const struct network_path *path) 2309{ 2310 struct lsquic_packet_out *packet_out; 2311 2312 assert(lsquic_send_ctl_schedule_stream_packets_immediately(ctl)); 2313 assert(need_at_least > 0); 2314 2315 packet_out = lsquic_send_ctl_last_scheduled(ctl, pns, path, 0); 2316 if (packet_out 2317 && !(packet_out->po_flags & (PO_STREAM_END|PO_RETX)) 2318 && lsquic_packet_out_avail(packet_out) >= need_at_least) 2319 { 2320 return packet_out; 2321 } 2322 2323 if (!lsquic_send_ctl_can_send(ctl)) 2324 return NULL; 2325 2326 packet_out = lsquic_send_ctl_new_packet_out(ctl, need_at_least, pns, path); 2327 if (!packet_out) 2328 return NULL; 2329 2330 lsquic_send_ctl_scheduled_one(ctl, packet_out); 2331 return packet_out; 2332} 2333 2334 2335static void 2336update_for_resending (lsquic_send_ctl_t *ctl, lsquic_packet_out_t *packet_out) 2337{ 2338 2339 lsquic_packno_t oldno, packno; 2340 2341 /* When the packet is resent, it uses the same number of bytes to encode 2342 * the packet number as the original packet. This follows the reference 2343 * implementation. 2344 */ 2345 oldno = packet_out->po_packno; 2346 packno = send_ctl_next_packno(ctl); 2347 2348 packet_out->po_flags &= ~PO_SENT_SZ; 2349 packet_out->po_frame_types &= ~BQUIC_FRAME_REGEN_MASK; 2350 assert(packet_out->po_frame_types); 2351 packet_out->po_packno = packno; 2352 lsquic_packet_out_set_ecn(packet_out, ctl->sc_ecn); 2353 2354 if (ctl->sc_ver_neg->vn_tag) 2355 { 2356 assert(packet_out->po_flags & PO_VERSION); /* It can only disappear */ 2357 packet_out->po_ver_tag = *ctl->sc_ver_neg->vn_tag; 2358 } 2359 2360 assert(packet_out->po_regen_sz < packet_out->po_data_sz); 2361 if (packet_out->po_regen_sz) 2362 { 2363 if (packet_out->po_flags & PO_SCHED) 2364 ctl->sc_bytes_scheduled -= packet_out->po_regen_sz; 2365 lsquic_packet_out_chop_regen(packet_out); 2366 } 2367 LSQ_DEBUG("Packet %"PRIu64" repackaged for resending as packet %"PRIu64, 2368 oldno, packno); 2369 EV_LOG_CONN_EVENT(LSQUIC_LOG_CONN_ID, "packet %"PRIu64" repackaged for " 2370 "resending as packet %"PRIu64, oldno, packno); 2371} 2372 2373 2374unsigned 2375lsquic_send_ctl_reschedule_packets (lsquic_send_ctl_t *ctl) 2376{ 2377 lsquic_packet_out_t *packet_out; 2378 unsigned n = 0; 2379 2380 while ((packet_out = send_ctl_next_lost(ctl))) 2381 { 2382 assert(packet_out->po_regen_sz < packet_out->po_data_sz); 2383 ++n; 2384#if LSQUIC_CONN_STATS 2385 ++ctl->sc_conn_pub->conn_stats->out.retx_packets; 2386#endif 2387 update_for_resending(ctl, packet_out); 2388 lsquic_send_ctl_scheduled_one(ctl, packet_out); 2389 } 2390 2391 if (n) 2392 LSQ_DEBUG("rescheduled %u packets", n); 2393 2394 return n; 2395} 2396 2397 2398void 2399lsquic_send_ctl_set_tcid0 (lsquic_send_ctl_t *ctl, int tcid0) 2400{ 2401 if (tcid0) 2402 { 2403 LSQ_INFO("set TCID flag"); 2404 ctl->sc_flags |= SC_TCID0; 2405 } 2406 else 2407 { 2408 LSQ_INFO("unset TCID flag"); 2409 ctl->sc_flags &= ~SC_TCID0; 2410 } 2411} 2412 2413 2414/* The controller elides this STREAM frames of stream `stream_id' from 2415 * scheduled and buffered packets. If a packet becomes empty as a result, 2416 * it is dropped. 2417 * 2418 * Packets on other queues do not need to be processed: unacked packets 2419 * have already been sent, and lost packets' reset stream frames will be 2420 * elided in due time. 2421 */ 2422void 2423lsquic_send_ctl_elide_stream_frames (lsquic_send_ctl_t *ctl, 2424 lsquic_stream_id_t stream_id) 2425{ 2426 struct lsquic_packet_out *packet_out, *next; 2427 unsigned n, adj; 2428 int dropped; 2429 2430 dropped = 0; 2431#ifdef WIN32 2432 next = NULL; 2433#endif 2434 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2435 packet_out = next) 2436 { 2437 next = TAILQ_NEXT(packet_out, po_next); 2438 2439 if ((packet_out->po_frame_types & (1 << QUIC_FRAME_STREAM)) 2440 && 0 == (packet_out->po_flags & PO_MINI)) 2441 { 2442 adj = lsquic_packet_out_elide_reset_stream_frames(packet_out, 2443 stream_id); 2444 ctl->sc_bytes_scheduled -= adj; 2445 if (0 == packet_out->po_frame_types) 2446 { 2447 LSQ_DEBUG("cancel packet %"PRIu64" after eliding frames for " 2448 "stream %"PRIu64, packet_out->po_packno, stream_id); 2449 send_ctl_sched_remove(ctl, packet_out); 2450 send_ctl_destroy_chain(ctl, packet_out, NULL); 2451 send_ctl_destroy_packet(ctl, packet_out); 2452 ++dropped; 2453 } 2454 } 2455 } 2456 2457 if (dropped) 2458 lsquic_send_ctl_reset_packnos(ctl); 2459 2460 for (n = 0; n < sizeof(ctl->sc_buffered_packets) / 2461 sizeof(ctl->sc_buffered_packets[0]); ++n) 2462 { 2463 for (packet_out = TAILQ_FIRST(&ctl->sc_buffered_packets[n].bpq_packets); 2464 packet_out; packet_out = next) 2465 { 2466 next = TAILQ_NEXT(packet_out, po_next); 2467 if (packet_out->po_frame_types & (1 << QUIC_FRAME_STREAM)) 2468 { 2469 lsquic_packet_out_elide_reset_stream_frames(packet_out, stream_id); 2470 if (0 == packet_out->po_frame_types) 2471 { 2472 LSQ_DEBUG("cancel buffered packet in queue #%u after eliding " 2473 "frames for stream %"PRIu64, n, stream_id); 2474 TAILQ_REMOVE(&ctl->sc_buffered_packets[n].bpq_packets, 2475 packet_out, po_next); 2476 --ctl->sc_buffered_packets[n].bpq_count; 2477 send_ctl_destroy_packet(ctl, packet_out); 2478 LSQ_DEBUG("Elide packet from buffered queue #%u; count: %u", 2479 n, ctl->sc_buffered_packets[n].bpq_count); 2480 } 2481 } 2482 } 2483 } 2484} 2485 2486 2487/* Count how many packets will remain after the squeezing performed by 2488 * lsquic_send_ctl_squeeze_sched(). This is the number of delayed data 2489 * packets. 2490 */ 2491#ifndef NDEBUG 2492#if __GNUC__ 2493__attribute__((weak)) 2494#endif 2495#endif 2496int 2497lsquic_send_ctl_have_delayed_packets (const lsquic_send_ctl_t *ctl) 2498{ 2499 const struct lsquic_packet_out *packet_out; 2500 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2501 if (packet_out->po_regen_sz < packet_out->po_data_sz) 2502 return 1; 2503 return 0; 2504} 2505 2506 2507#ifndef NDEBUG 2508static void 2509send_ctl_log_packet_q (const lsquic_send_ctl_t *ctl, const char *prefix, 2510 const struct lsquic_packets_tailq *tailq) 2511{ 2512 const lsquic_packet_out_t *packet_out; 2513 unsigned n_packets; 2514 char *buf; 2515 size_t bufsz; 2516 int off; 2517 2518 n_packets = 0; 2519 TAILQ_FOREACH(packet_out, tailq, po_next) 2520 ++n_packets; 2521 2522 if (n_packets == 0) 2523 { 2524 LSQ_DEBUG("%s: [<empty set>]", prefix); 2525 return; 2526 } 2527 2528 bufsz = n_packets * sizeof("18446744073709551615" /* UINT64_MAX */); 2529 buf = malloc(bufsz); 2530 if (!buf) 2531 { 2532 LSQ_ERROR("%s: malloc: %s", __func__, strerror(errno)); 2533 return; 2534 } 2535 2536 off = 0; 2537 TAILQ_FOREACH(packet_out, tailq, po_next) 2538 { 2539 if (off) 2540 buf[off++] = ' '; 2541 off += sprintf(buf + off, "%"PRIu64, packet_out->po_packno); 2542 } 2543 2544 LSQ_DEBUG("%s: [%s]", prefix, buf); 2545 free(buf); 2546} 2547 2548 2549#define LOG_PACKET_Q(prefix, queue) do { \ 2550 if (LSQ_LOG_ENABLED(LSQ_LOG_DEBUG)) \ 2551 send_ctl_log_packet_q(ctl, queue, prefix); \ 2552} while (0) 2553#else 2554#define LOG_PACKET_Q(p, q) 2555#endif 2556 2557 2558int 2559lsquic_send_ctl_squeeze_sched (lsquic_send_ctl_t *ctl) 2560{ 2561 struct lsquic_packet_out *packet_out, *next; 2562 int dropped; 2563#ifndef NDEBUG 2564 int pre_squeeze_logged = 0; 2565#endif 2566 2567 dropped = 0; 2568 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2569 packet_out = next) 2570 { 2571 next = TAILQ_NEXT(packet_out, po_next); 2572 if (packet_out->po_regen_sz < packet_out->po_data_sz 2573 || packet_out->po_frame_types == QUIC_FTBIT_PATH_CHALLENGE) 2574 { 2575 if (packet_out->po_flags & PO_ENCRYPTED) 2576 send_ctl_return_enc_data(ctl, packet_out); 2577 } 2578 else 2579 { 2580#ifndef NDEBUG 2581 /* Log the whole list before we squeeze for the first time */ 2582 if (!pre_squeeze_logged++) 2583 LOG_PACKET_Q(&ctl->sc_scheduled_packets, 2584 "scheduled packets before squeezing"); 2585#endif 2586 send_ctl_sched_remove(ctl, packet_out); 2587 LSQ_DEBUG("Dropping packet %"PRIu64" from scheduled queue", 2588 packet_out->po_packno); 2589 send_ctl_destroy_chain(ctl, packet_out, NULL); 2590 send_ctl_destroy_packet(ctl, packet_out); 2591 ++dropped; 2592 } 2593 } 2594 2595 if (dropped) 2596 lsquic_send_ctl_reset_packnos(ctl); 2597 2598#ifndef NDEBUG 2599 if (pre_squeeze_logged) 2600 LOG_PACKET_Q(&ctl->sc_scheduled_packets, 2601 "scheduled packets after squeezing"); 2602 else if (ctl->sc_n_scheduled > 0) 2603 LOG_PACKET_Q(&ctl->sc_scheduled_packets, "delayed packets"); 2604#endif 2605 2606 return ctl->sc_n_scheduled > 0; 2607} 2608 2609 2610void 2611lsquic_send_ctl_reset_packnos (lsquic_send_ctl_t *ctl) 2612{ 2613 struct lsquic_packet_out *packet_out; 2614 2615 ctl->sc_cur_packno = lsquic_senhist_largest(&ctl->sc_senhist); 2616 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2617 packet_out->po_flags |= PO_REPACKNO; 2618} 2619 2620 2621void 2622lsquic_send_ctl_ack_to_front (struct lsquic_send_ctl *ctl, unsigned n_acks) 2623{ 2624 struct lsquic_packet_out *ack_packet; 2625 2626 assert(n_acks > 0); 2627 assert(ctl->sc_n_scheduled > n_acks); /* Otherwise, why is this called? */ 2628 for ( ; n_acks > 0; --n_acks) 2629 { 2630 ack_packet = TAILQ_LAST(&ctl->sc_scheduled_packets, lsquic_packets_tailq); 2631 assert(ack_packet->po_frame_types & (1 << QUIC_FRAME_ACK)); 2632 TAILQ_REMOVE(&ctl->sc_scheduled_packets, ack_packet, po_next); 2633 TAILQ_INSERT_HEAD(&ctl->sc_scheduled_packets, ack_packet, po_next); 2634 } 2635} 2636 2637 2638void 2639lsquic_send_ctl_drop_scheduled (lsquic_send_ctl_t *ctl) 2640{ 2641 struct lsquic_packet_out *packet_out, *next; 2642 unsigned n; 2643 2644 n = 0; 2645 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2646 packet_out = next) 2647 { 2648 next = TAILQ_NEXT(packet_out, po_next); 2649 if (0 == (packet_out->po_flags & PO_HELLO)) 2650 { 2651 send_ctl_sched_remove(ctl, packet_out); 2652 send_ctl_destroy_chain(ctl, packet_out, NULL); 2653 send_ctl_destroy_packet(ctl, packet_out); 2654 ++n; 2655 } 2656 } 2657 2658 ctl->sc_senhist.sh_flags |= SH_GAP_OK; 2659 2660 LSQ_DEBUG("dropped %u scheduled packet%s (%u left)", n, n != 1 ? "s" : "", 2661 ctl->sc_n_scheduled); 2662} 2663 2664 2665#ifdef NDEBUG 2666static 2667#elif __GNUC__ 2668__attribute__((weak)) 2669#endif 2670enum buf_packet_type 2671lsquic_send_ctl_determine_bpt (lsquic_send_ctl_t *ctl, 2672 const lsquic_stream_t *stream) 2673{ 2674 const lsquic_stream_t *other_stream; 2675 struct lsquic_hash_elem *el; 2676 struct lsquic_hash *all_streams; 2677 2678 all_streams = ctl->sc_conn_pub->all_streams; 2679 for (el = lsquic_hash_first(all_streams); el; 2680 el = lsquic_hash_next(all_streams)) 2681 { 2682 other_stream = lsquic_hashelem_getdata(el); 2683 if (other_stream != stream 2684 && (!(other_stream->stream_flags & STREAM_U_WRITE_DONE)) 2685 && !lsquic_stream_is_critical(other_stream) 2686 && other_stream->sm_priority < stream->sm_priority) 2687 return BPT_OTHER_PRIO; 2688 } 2689 return BPT_HIGHEST_PRIO; 2690} 2691 2692 2693static enum buf_packet_type 2694send_ctl_lookup_bpt (lsquic_send_ctl_t *ctl, 2695 const struct lsquic_stream *stream) 2696{ 2697 if (ctl->sc_cached_bpt.stream_id != stream->id) 2698 { 2699 ctl->sc_cached_bpt.stream_id = stream->id; 2700 ctl->sc_cached_bpt.packet_type = 2701 lsquic_send_ctl_determine_bpt(ctl, stream); 2702 } 2703 return ctl->sc_cached_bpt.packet_type; 2704} 2705 2706 2707static unsigned 2708send_ctl_max_bpq_count (const lsquic_send_ctl_t *ctl, 2709 enum buf_packet_type packet_type) 2710{ 2711 unsigned long cwnd; 2712 unsigned count; 2713 2714 switch (packet_type) 2715 { 2716 case BPT_OTHER_PRIO: 2717 return MAX_BPQ_COUNT; 2718 case BPT_HIGHEST_PRIO: 2719 default: /* clang does not complain about absence of `default'... */ 2720 count = ctl->sc_n_scheduled + ctl->sc_n_in_flight_retx; 2721 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 2722 if (count < cwnd / SC_PACK_SIZE(ctl)) 2723 { 2724 count = cwnd / SC_PACK_SIZE(ctl) - count; 2725 if (count > MAX_BPQ_COUNT) 2726 return count; 2727 } 2728 return MAX_BPQ_COUNT; 2729 } 2730} 2731 2732 2733/* If error is returned, `src' is not modified */ 2734static int 2735send_ctl_move_ack (struct lsquic_send_ctl *ctl, struct lsquic_packet_out *dst, 2736 struct lsquic_packet_out *src) 2737{ 2738 struct packet_out_frec_iter pofi; 2739 const struct frame_rec *frec; 2740 assert(dst->po_data_sz == 0); 2741 2742 /* This checks that we only ever expect to move an ACK frame from one 2743 * buffered packet to another. We don't generate any other regen frame 2744 * types in buffered packets. 2745 */ 2746 assert(!(BQUIC_FRAME_REGEN_MASK & (1 << src->po_frame_types) 2747 & ~QUIC_FTBIT_ACK)); 2748 2749 if (lsquic_packet_out_avail(dst) >= src->po_regen_sz 2750 && (frec = lsquic_pofi_first(&pofi, src), frec != NULL) 2751 && frec->fe_frame_type == QUIC_FRAME_ACK) 2752 { 2753 memcpy(dst->po_data, src->po_data, src->po_regen_sz); 2754 if (0 != lsquic_packet_out_add_frame(dst, &ctl->sc_enpub->enp_mm, 2755 frec->fe_frame_type, QUIC_FRAME_ACK, dst->po_data_sz, 2756 src->po_regen_sz)) 2757 return -1; 2758 dst->po_data_sz = src->po_regen_sz; 2759 dst->po_regen_sz = src->po_regen_sz; 2760 dst->po_frame_types |= (BQUIC_FRAME_REGEN_MASK & src->po_frame_types); 2761 src->po_frame_types &= ~BQUIC_FRAME_REGEN_MASK; 2762 lsquic_packet_out_chop_regen(src); 2763 } 2764 2765 return 0; 2766} 2767 2768 2769static lsquic_packet_out_t * 2770send_ctl_get_buffered_packet (lsquic_send_ctl_t *ctl, 2771 enum buf_packet_type packet_type, unsigned need_at_least, 2772 const struct network_path *path, const struct lsquic_stream *stream) 2773{ 2774 struct buf_packet_q *const packet_q = 2775 &ctl->sc_buffered_packets[packet_type]; 2776 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 2777 lsquic_packet_out_t *packet_out; 2778 enum packno_bits bits; 2779 enum { AA_STEAL, AA_GENERATE, AA_NONE, } ack_action; 2780 2781 packet_out = TAILQ_LAST(&packet_q->bpq_packets, lsquic_packets_tailq); 2782 if (packet_out 2783 && !(packet_out->po_flags & PO_STREAM_END) 2784 && lsquic_packet_out_avail(packet_out) >= need_at_least) 2785 { 2786 return packet_out; 2787 } 2788 2789 if (packet_q->bpq_count >= send_ctl_max_bpq_count(ctl, packet_type)) 2790 return NULL; 2791 2792 if (packet_q->bpq_count == 0) 2793 { 2794 /* If ACK was written to the low-priority queue first, steal it */ 2795 if (packet_q == &ctl->sc_buffered_packets[BPT_HIGHEST_PRIO] 2796 && !TAILQ_EMPTY(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets) 2797 && (TAILQ_FIRST(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets) 2798 ->po_frame_types & QUIC_FTBIT_ACK)) 2799 { 2800 LSQ_DEBUG("steal ACK frame from low-priority buffered queue"); 2801 ack_action = AA_STEAL; 2802 bits = ctl->sc_max_packno_bits; 2803 } 2804 /* If ACK can be generated, write it to the first buffered packet. */ 2805 else if (lconn->cn_if->ci_can_write_ack(lconn)) 2806 { 2807 LSQ_DEBUG("generate ACK frame for first buffered packet in " 2808 "queue #%u", packet_type); 2809 ack_action = AA_GENERATE; 2810 /* Packet length is set to the largest possible size to guarantee 2811 * that buffered packet with the ACK will not need to be split. 2812 */ 2813 bits = ctl->sc_max_packno_bits; 2814 } 2815 else 2816 goto no_ack_action; 2817 } 2818 else 2819 { 2820 no_ack_action: 2821 ack_action = AA_NONE; 2822 bits = lsquic_send_ctl_guess_packno_bits(ctl); 2823 } 2824 2825 packet_out = send_ctl_allocate_packet(ctl, bits, need_at_least, PNS_APP, 2826 path); 2827 if (!packet_out) 2828 return NULL; 2829 2830 switch (ack_action) 2831 { 2832 case AA_STEAL: 2833 if (0 != send_ctl_move_ack(ctl, packet_out, 2834 TAILQ_FIRST(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets))) 2835 { 2836 LSQ_INFO("cannot move ack"); 2837 lsquic_packet_out_destroy(packet_out, ctl->sc_enpub, 2838 packet_out->po_path->np_peer_ctx); 2839 return NULL; 2840 } 2841 break; 2842 case AA_GENERATE: 2843 lconn->cn_if->ci_write_ack(lconn, packet_out); 2844 break; 2845 case AA_NONE: 2846 break; 2847 } 2848 2849 TAILQ_INSERT_TAIL(&packet_q->bpq_packets, packet_out, po_next); 2850 ++packet_q->bpq_count; 2851 LSQ_DEBUG("Add new packet to buffered queue #%u; count: %u", 2852 packet_type, packet_q->bpq_count); 2853 return packet_out; 2854} 2855 2856 2857static void 2858send_ctl_maybe_flush_decoder (struct lsquic_send_ctl *ctl, 2859 const struct lsquic_stream *caller) 2860{ 2861 struct lsquic_stream *decoder; 2862 2863 if ((ctl->sc_flags & SC_IETF) && ctl->sc_conn_pub->u.ietf.qdh) 2864 { 2865 decoder = ctl->sc_conn_pub->u.ietf.qdh->qdh_dec_sm_out; 2866 if (decoder && decoder != caller 2867 && lsquic_stream_has_data_to_flush(decoder)) 2868 { 2869 LSQ_DEBUG("flushing decoder stream"); 2870 lsquic_stream_flush(decoder); 2871 } 2872 } 2873} 2874 2875 2876lsquic_packet_out_t * 2877lsquic_send_ctl_get_packet_for_stream (lsquic_send_ctl_t *ctl, 2878 unsigned need_at_least, const struct network_path *path, 2879 const struct lsquic_stream *stream) 2880{ 2881 enum buf_packet_type packet_type; 2882 2883 if (lsquic_send_ctl_schedule_stream_packets_immediately(ctl)) 2884 return lsquic_send_ctl_get_writeable_packet(ctl, PNS_APP, 2885 need_at_least, path, 0, NULL); 2886 else 2887 { 2888 if (!lsquic_send_ctl_has_buffered(ctl)) 2889 send_ctl_maybe_flush_decoder(ctl, stream); 2890 packet_type = send_ctl_lookup_bpt(ctl, stream); 2891 return send_ctl_get_buffered_packet(ctl, packet_type, need_at_least, 2892 path, stream); 2893 } 2894} 2895 2896 2897#ifdef NDEBUG 2898static 2899#elif __GNUC__ 2900__attribute__((weak)) 2901#endif 2902enum packno_bits 2903lsquic_send_ctl_calc_packno_bits (lsquic_send_ctl_t *ctl) 2904{ 2905 lsquic_packno_t smallest_unacked; 2906 enum packno_bits bits; 2907 unsigned n_in_flight; 2908 unsigned long cwnd; 2909 const struct parse_funcs *pf; 2910 2911 pf = ctl->sc_conn_pub->lconn->cn_pf; 2912 2913 smallest_unacked = lsquic_send_ctl_smallest_unacked(ctl); 2914 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 2915 n_in_flight = cwnd / SC_PACK_SIZE(ctl); 2916 bits = pf->pf_calc_packno_bits(ctl->sc_cur_packno + 1, smallest_unacked, 2917 n_in_flight); 2918 if (bits <= ctl->sc_max_packno_bits) 2919 return bits; 2920 else 2921 return ctl->sc_max_packno_bits; 2922} 2923 2924 2925enum packno_bits 2926lsquic_send_ctl_packno_bits (struct lsquic_send_ctl *ctl, 2927 enum packnum_space pns) 2928{ 2929 if ((ctl->sc_flags & (SC_ACK_RECV_INIT << pns)) 2930 && lsquic_send_ctl_schedule_stream_packets_immediately(ctl)) 2931 return lsquic_send_ctl_calc_packno_bits(ctl); 2932 else if (ctl->sc_flags & (SC_ACK_RECV_INIT << pns)) 2933 return lsquic_send_ctl_guess_packno_bits(ctl); 2934 else 2935/* From [draft-ietf-quic-transport-31] Section 17.1: 2936 * 2937 " Prior to receiving an acknowledgement for a packet number space, the 2938 " full packet number MUST be included; it is not to be truncated as 2939 " described below. 2940 */ 2941 return vint_val2bits(ctl->sc_cur_packno + 1); 2942} 2943 2944 2945struct resize_one_packet_ctx 2946{ 2947 struct lsquic_send_ctl *const ctl; 2948 struct lsquic_packet_out *const victim; 2949 const struct network_path *const path; 2950 const enum packnum_space pns; 2951 int discarded, fetched; 2952}; 2953 2954 2955static struct lsquic_packet_out * 2956resize_one_next_packet (void *ctx) 2957{ 2958 struct resize_one_packet_ctx *const one_ctx = ctx; 2959 2960 if (one_ctx->fetched) 2961 return NULL; 2962 2963 ++one_ctx->fetched; 2964 return one_ctx->victim; 2965} 2966 2967 2968static void 2969resize_one_discard_packet (void *ctx, struct lsquic_packet_out *packet_out) 2970{ 2971 struct resize_one_packet_ctx *const one_ctx = ctx; 2972 2973 /* Delay discarding the packet: we need it for TAILQ_INSERT_BEFORE */ 2974 ++one_ctx->discarded; 2975} 2976 2977 2978static struct lsquic_packet_out * 2979resize_one_new_packet (void *ctx) 2980{ 2981 struct resize_one_packet_ctx *const one_ctx = ctx; 2982 struct lsquic_send_ctl *const ctl = one_ctx->ctl; 2983 struct lsquic_packet_out *packet_out; 2984 enum packno_bits bits; 2985 2986 bits = lsquic_send_ctl_calc_packno_bits(ctl); 2987 packet_out = send_ctl_allocate_packet(ctl, bits, 0, one_ctx->pns, 2988 one_ctx->path); 2989 return packet_out; 2990} 2991 2992 2993static const struct packet_resize_if resize_one_funcs = 2994{ 2995 resize_one_next_packet, 2996 resize_one_discard_packet, 2997 resize_one_new_packet, 2998}; 2999 3000 3001static int 3002split_buffered_packet (lsquic_send_ctl_t *ctl, 3003 enum buf_packet_type packet_type, struct lsquic_packet_out *packet_out) 3004{ 3005 struct buf_packet_q *const packet_q = 3006 &ctl->sc_buffered_packets[packet_type]; 3007 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3008 struct lsquic_packet_out *new; 3009 struct packet_resize_ctx prctx; 3010 struct resize_one_packet_ctx one_ctx = { 3011 ctl, packet_out, packet_out->po_path, 3012 lsquic_packet_out_pns(packet_out), 0, 0, 3013 }; 3014 unsigned count; 3015 3016 assert(TAILQ_FIRST(&packet_q->bpq_packets) == packet_out); 3017 3018 lsquic_packet_resize_init(&prctx, ctl->sc_enpub, lconn, &one_ctx, 3019 &resize_one_funcs); 3020 count = 0; 3021 while (new = lsquic_packet_resize_next(&prctx), new != NULL) 3022 { 3023 ++count; 3024 TAILQ_INSERT_BEFORE(packet_out, new, po_next); 3025 ++packet_q->bpq_count; 3026 LSQ_DEBUG("Add split packet to buffered queue #%u; count: %u", 3027 packet_type, packet_q->bpq_count); 3028 } 3029 if (lsquic_packet_resize_is_error(&prctx)) 3030 { 3031 LSQ_WARN("error resizing buffered packet #%"PRIu64, 3032 packet_out->po_packno); 3033 return -1; 3034 } 3035 if (!(count > 1 && one_ctx.fetched == 1 && one_ctx.discarded == 1)) 3036 { 3037 /* A bit of insurance, this being new code */ 3038 LSQ_WARN("unexpected values resizing buffered packet: count: %u; " 3039 "fetched: %d; discarded: %d", count, one_ctx.fetched, 3040 one_ctx.discarded); 3041 return -1; 3042 } 3043 LSQ_DEBUG("added %u packets to the buffered queue #%u", count, packet_type); 3044 3045 LSQ_DEBUG("drop oversized buffered packet #%"PRIu64, packet_out->po_packno); 3046 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 3047 ++packet_q->bpq_count; 3048 assert(packet_out->po_loss_chain == packet_out); 3049 send_ctl_destroy_packet(ctl, packet_out); 3050 return 0; 3051} 3052 3053 3054int 3055lsquic_send_ctl_schedule_buffered (lsquic_send_ctl_t *ctl, 3056 enum buf_packet_type packet_type) 3057{ 3058 struct buf_packet_q *const packet_q = 3059 &ctl->sc_buffered_packets[packet_type]; 3060 const struct parse_funcs *const pf = ctl->sc_conn_pub->lconn->cn_pf; 3061 lsquic_packet_out_t *packet_out; 3062 unsigned used; 3063 3064 assert(lsquic_send_ctl_schedule_stream_packets_immediately(ctl)); 3065 const enum packno_bits bits = lsquic_send_ctl_calc_packno_bits(ctl); 3066 const unsigned need = pf->pf_packno_bits2len(bits); 3067 3068 while ((packet_out = TAILQ_FIRST(&packet_q->bpq_packets)) && 3069 lsquic_send_ctl_can_send(ctl)) 3070 { 3071 if ((packet_out->po_frame_types & QUIC_FTBIT_ACK) 3072 && packet_out->po_ack2ed < ctl->sc_largest_acked) 3073 { 3074 /* Chrome watches for a decrease in the value of the Largest 3075 * Observed field of the ACK frame and marks it as an error: 3076 * this is why we have to send out ACK in the order they were 3077 * generated. 3078 */ 3079 LSQ_DEBUG("Remove out-of-order ACK from buffered packet"); 3080 lsquic_packet_out_chop_regen(packet_out); 3081 if (packet_out->po_data_sz == 0) 3082 { 3083 LSQ_DEBUG("Dropping now-empty buffered packet"); 3084 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 3085 --packet_q->bpq_count; 3086 send_ctl_destroy_packet(ctl, packet_out); 3087 continue; 3088 } 3089 } 3090 if (bits != lsquic_packet_out_packno_bits(packet_out)) 3091 { 3092 used = pf->pf_packno_bits2len( 3093 lsquic_packet_out_packno_bits(packet_out)); 3094 if (need > used 3095 && need - used > lsquic_packet_out_avail(packet_out)) 3096 { 3097 if (0 == split_buffered_packet(ctl, packet_type, packet_out)) 3098 packet_out = TAILQ_FIRST(&packet_q->bpq_packets); 3099 else 3100 return -1; 3101 } 3102 } 3103 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 3104 --packet_q->bpq_count; 3105 packet_out->po_packno = send_ctl_next_packno(ctl); 3106 LSQ_DEBUG("Remove packet from buffered queue #%u; count: %u. " 3107 "It becomes packet %"PRIu64, packet_type, packet_q->bpq_count, 3108 packet_out->po_packno); 3109 lsquic_send_ctl_scheduled_one(ctl, packet_out); 3110 } 3111 3112 return 0; 3113} 3114 3115 3116int 3117lsquic_send_ctl_turn_on_fin (struct lsquic_send_ctl *ctl, 3118 const struct lsquic_stream *stream) 3119{ 3120 enum buf_packet_type packet_type; 3121 struct buf_packet_q *packet_q; 3122 lsquic_packet_out_t *packet_out; 3123 const struct parse_funcs *pf; 3124 3125 pf = ctl->sc_conn_pub->lconn->cn_pf; 3126 packet_type = send_ctl_lookup_bpt(ctl, stream); 3127 packet_q = &ctl->sc_buffered_packets[packet_type]; 3128 3129 TAILQ_FOREACH_REVERSE(packet_out, &packet_q->bpq_packets, 3130 lsquic_packets_tailq, po_next) 3131 if (0 == lsquic_packet_out_turn_on_fin(packet_out, pf, stream)) 3132 return 0; 3133 3134 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 3135 if (0 == packet_out->po_sent 3136 && 0 == lsquic_packet_out_turn_on_fin(packet_out, pf, stream)) 3137 { 3138 return 0; 3139 } 3140 3141 return -1; 3142} 3143 3144 3145size_t 3146lsquic_send_ctl_mem_used (const struct lsquic_send_ctl *ctl) 3147{ 3148 const lsquic_packet_out_t *packet_out; 3149 unsigned n; 3150 size_t size; 3151 const struct lsquic_packets_tailq queues[] = { 3152 ctl->sc_scheduled_packets, 3153 ctl->sc_unacked_packets[PNS_INIT], 3154 ctl->sc_unacked_packets[PNS_HSK], 3155 ctl->sc_unacked_packets[PNS_APP], 3156 ctl->sc_lost_packets, 3157 ctl->sc_buffered_packets[0].bpq_packets, 3158 ctl->sc_buffered_packets[1].bpq_packets, 3159 }; 3160 3161 size = sizeof(*ctl); 3162 3163 for (n = 0; n < sizeof(queues) / sizeof(queues[0]); ++n) 3164 TAILQ_FOREACH(packet_out, &queues[n], po_next) 3165 size += lsquic_packet_out_mem_used(packet_out); 3166 3167 return size; 3168} 3169 3170 3171void 3172lsquic_send_ctl_verneg_done (struct lsquic_send_ctl *ctl) 3173{ 3174 ctl->sc_max_packno_bits = PACKNO_BITS_3; 3175 LSQ_DEBUG("version negotiation done (%s): max packno bits: %u", 3176 lsquic_ver2str[ ctl->sc_conn_pub->lconn->cn_version ], 3177 ctl->sc_max_packno_bits); 3178} 3179 3180 3181static void 3182strip_trailing_padding (struct lsquic_packet_out *packet_out) 3183{ 3184 struct packet_out_frec_iter pofi; 3185 const struct frame_rec *frec; 3186 unsigned off; 3187 3188 off = 0; 3189 for (frec = lsquic_pofi_first(&pofi, packet_out); frec; 3190 frec = lsquic_pofi_next(&pofi)) 3191 off = frec->fe_off + frec->fe_len; 3192 3193 assert(off); 3194 3195 packet_out->po_data_sz = off; 3196 packet_out->po_frame_types &= ~QUIC_FTBIT_PADDING; 3197} 3198 3199 3200static int 3201split_lost_packet (struct lsquic_send_ctl *ctl, 3202 struct lsquic_packet_out *const packet_out) 3203{ 3204 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3205 struct lsquic_packet_out *new; 3206 struct packet_resize_ctx prctx; 3207 struct resize_one_packet_ctx one_ctx = { 3208 ctl, packet_out, packet_out->po_path, 3209 lsquic_packet_out_pns(packet_out), 0, 0, 3210 }; 3211 unsigned count; 3212 3213 assert(packet_out->po_flags & PO_LOST); 3214 3215 lsquic_packet_resize_init(&prctx, ctl->sc_enpub, lconn, &one_ctx, 3216 &resize_one_funcs); 3217 count = 0; 3218 while (new = lsquic_packet_resize_next(&prctx), new != NULL) 3219 { 3220 ++count; 3221 TAILQ_INSERT_BEFORE(packet_out, new, po_next); 3222 new->po_flags |= PO_LOST; 3223 } 3224 if (lsquic_packet_resize_is_error(&prctx)) 3225 { 3226 LSQ_WARN("error resizing lost packet #%"PRIu64, packet_out->po_packno); 3227 return -1; 3228 } 3229 if (!(count > 1 && one_ctx.fetched == 1 && one_ctx.discarded == 1)) 3230 { 3231 /* A bit of insurance, this being new code */ 3232 LSQ_WARN("unexpected values resizing lost packet: count: %u; " 3233 "fetched: %d; discarded: %d", count, one_ctx.fetched, 3234 one_ctx.discarded); 3235 return -1; 3236 } 3237 LSQ_DEBUG("added %u packets to the lost queue", count); 3238 3239 LSQ_DEBUG("drop oversized lost packet #%"PRIu64, packet_out->po_packno); 3240 TAILQ_REMOVE(&ctl->sc_lost_packets, packet_out, po_next); 3241 packet_out->po_flags &= ~PO_LOST; 3242 send_ctl_destroy_chain(ctl, packet_out, NULL); 3243 send_ctl_destroy_packet(ctl, packet_out); 3244 return 0; 3245} 3246 3247 3248int 3249lsquic_send_ctl_retry (struct lsquic_send_ctl *ctl, 3250 const unsigned char *token, size_t token_sz) 3251{ 3252 struct lsquic_packet_out *packet_out, *next; 3253 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3254 size_t sz; 3255 3256 if (token_sz >= 1ull << (sizeof(packet_out->po_token_len) * 8)) 3257 { 3258 LSQ_WARN("token size %zu is too long", token_sz); 3259 return -1; 3260 } 3261 3262 ++ctl->sc_retry_count; 3263 if (ctl->sc_retry_count > 3) 3264 { 3265 LSQ_INFO("failing connection after %u retries", ctl->sc_retry_count); 3266 return -1; 3267 } 3268 3269 send_ctl_expire(ctl, PNS_INIT, EXFI_ALL); 3270 3271 if (0 != lsquic_send_ctl_set_token(ctl, token, token_sz)) 3272 return -1; 3273 3274 for (packet_out = TAILQ_FIRST(&ctl->sc_lost_packets); packet_out; packet_out = next) 3275 { 3276 next = TAILQ_NEXT(packet_out, po_next); 3277 if (HETY_INITIAL != packet_out->po_header_type) 3278 continue; 3279 3280 if (packet_out->po_nonce) 3281 { 3282 free(packet_out->po_nonce); 3283 packet_out->po_nonce = NULL; 3284 packet_out->po_flags &= ~PO_NONCE; 3285 } 3286 3287 if (0 != send_ctl_set_packet_out_token(ctl, packet_out)) 3288 { 3289 LSQ_INFO("cannot set out token on packet"); 3290 return -1; 3291 } 3292 3293 if (packet_out->po_frame_types & QUIC_FTBIT_PADDING) 3294 strip_trailing_padding(packet_out); 3295 3296 sz = lconn->cn_pf->pf_packout_size(lconn, packet_out); 3297 if (sz > packet_out->po_path->np_pack_size 3298 && 0 != split_lost_packet(ctl, packet_out)) 3299 return -1; 3300 } 3301 3302 return 0; 3303} 3304 3305 3306int 3307lsquic_send_ctl_set_token (struct lsquic_send_ctl *ctl, 3308 const unsigned char *token, size_t token_sz) 3309{ 3310 unsigned char *copy; 3311 3312 if (token_sz > 1 << 3313 (sizeof(((struct lsquic_packet_out *)0)->po_token_len) * 8)) 3314 { 3315 errno = EINVAL; 3316 return -1; 3317 } 3318 3319 copy = malloc(token_sz); 3320 if (!copy) 3321 return -1; 3322 memcpy(copy, token, token_sz); 3323 free(ctl->sc_token); 3324 ctl->sc_token = copy; 3325 ctl->sc_token_sz = token_sz; 3326 LSQ_DEBUG("set token"); 3327 return 0; 3328} 3329 3330 3331void 3332lsquic_send_ctl_maybe_calc_rough_rtt (struct lsquic_send_ctl *ctl, 3333 enum packnum_space pns) 3334{ 3335 const struct lsquic_packet_out *packet_out; 3336 lsquic_time_t min_sent, rtt; 3337 struct lsquic_packets_tailq *const *q; 3338 struct lsquic_packets_tailq *const queues[] = { 3339 &ctl->sc_lost_packets, 3340 &ctl->sc_unacked_packets[pns], 3341 }; 3342 3343 if ((ctl->sc_flags & SC_ROUGH_RTT) 3344 || lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats)) 3345 return; 3346 3347 min_sent = UINT64_MAX; 3348 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 3349 TAILQ_FOREACH(packet_out, *q, po_next) 3350 if (min_sent > packet_out->po_sent) 3351 min_sent = packet_out->po_sent; 3352 3353 /* If we do not have an RTT estimate yet, get a rough estimate of it, 3354 * because now we will ignore packets that carry acknowledgements and 3355 * RTT estimation may be delayed. 3356 */ 3357 if (min_sent < UINT64_MAX) 3358 { 3359 rtt = lsquic_time_now() - min_sent; 3360 lsquic_rtt_stats_update(&ctl->sc_conn_pub->rtt_stats, rtt, 0); 3361 ctl->sc_flags |= SC_ROUGH_RTT; 3362 LSQ_DEBUG("set rough RTT to %"PRIu64" usec", rtt); 3363 } 3364} 3365 3366 3367void 3368lsquic_send_ctl_empty_pns (struct lsquic_send_ctl *ctl, enum packnum_space pns) 3369{ 3370 lsquic_packet_out_t *packet_out, *next; 3371 unsigned count, packet_sz; 3372 struct lsquic_packets_tailq *const *q; 3373 struct lsquic_packets_tailq *const queues[] = { 3374 &ctl->sc_lost_packets, 3375 &ctl->sc_buffered_packets[0].bpq_packets, 3376 &ctl->sc_buffered_packets[1].bpq_packets, 3377 }; 3378 3379 /* Don't bother with chain destruction, as all chains members are always 3380 * within the same packet number space 3381 */ 3382 3383 count = 0; 3384 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 3385 packet_out = next) 3386 { 3387 next = TAILQ_NEXT(packet_out, po_next); 3388 if (pns == lsquic_packet_out_pns(packet_out)) 3389 { 3390 send_ctl_maybe_renumber_sched_to_right(ctl, packet_out); 3391 send_ctl_sched_remove(ctl, packet_out); 3392 send_ctl_destroy_packet(ctl, packet_out); 3393 ++count; 3394 } 3395 } 3396 3397 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); packet_out; 3398 packet_out = next) 3399 { 3400 next = TAILQ_NEXT(packet_out, po_next); 3401 if (packet_out->po_flags & (PO_LOSS_REC|PO_POISON)) 3402 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, po_next); 3403 else 3404 { 3405 packet_sz = packet_out_sent_sz(packet_out); 3406 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 3407 lsquic_packet_out_ack_streams(packet_out); 3408 } 3409 send_ctl_destroy_packet(ctl, packet_out); 3410 ++count; 3411 } 3412 3413 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 3414 for (packet_out = TAILQ_FIRST(*q); packet_out; packet_out = next) 3415 { 3416 next = TAILQ_NEXT(packet_out, po_next); 3417 if (pns == lsquic_packet_out_pns(packet_out)) 3418 { 3419 TAILQ_REMOVE(*q, packet_out, po_next); 3420 send_ctl_destroy_packet(ctl, packet_out); 3421 ++count; 3422 } 3423 } 3424 3425 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 3426 3427 LSQ_DEBUG("emptied %s, destroyed %u packet%.*s", lsquic_pns2str[pns], 3428 count, count != 1, "s"); 3429} 3430 3431 3432struct resize_many_packet_ctx 3433{ 3434 struct lsquic_send_ctl *ctl; 3435 struct lsquic_packets_tailq input_q; 3436 const struct network_path *path; 3437}; 3438 3439 3440static struct lsquic_packet_out * 3441resize_many_next_packet (void *ctx) 3442{ 3443 struct resize_many_packet_ctx *const many_ctx = ctx; 3444 struct lsquic_packet_out *packet_out; 3445 3446 packet_out = TAILQ_FIRST(&many_ctx->input_q); 3447 if (packet_out) 3448 TAILQ_REMOVE(&many_ctx->input_q, packet_out, po_next); 3449 3450 return packet_out; 3451} 3452 3453 3454static void 3455resize_many_discard_packet (void *ctx, struct lsquic_packet_out *packet_out) 3456{ 3457 struct resize_many_packet_ctx *const many_ctx = ctx; 3458 struct lsquic_send_ctl *const ctl = many_ctx->ctl; 3459 3460 send_ctl_destroy_chain(ctl, packet_out, NULL); 3461 send_ctl_destroy_packet(ctl, packet_out); 3462} 3463 3464 3465static struct lsquic_packet_out * 3466resize_many_new_packet (void *ctx) 3467{ 3468 struct resize_many_packet_ctx *const many_ctx = ctx; 3469 struct lsquic_send_ctl *const ctl = many_ctx->ctl; 3470 struct lsquic_packet_out *packet_out; 3471 enum packno_bits bits; 3472 3473 bits = lsquic_send_ctl_calc_packno_bits(ctl); 3474 packet_out = send_ctl_allocate_packet(ctl, bits, 0, PNS_APP, 3475 many_ctx->path); 3476 return packet_out; 3477} 3478 3479 3480static const struct packet_resize_if resize_many_funcs = 3481{ 3482 resize_many_next_packet, 3483 resize_many_discard_packet, 3484 resize_many_new_packet, 3485}; 3486 3487 3488static void 3489send_ctl_resize_q (struct lsquic_send_ctl *ctl, struct lsquic_packets_tailq *q, 3490 const struct network_path *const path) 3491{ 3492 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3493 struct lsquic_packet_out *next, *packet_out; 3494 struct resize_many_packet_ctx many_ctx; 3495 struct packet_resize_ctx prctx; 3496 const char *q_name; 3497 unsigned count_src = 0, count_dst = 0; 3498 int idx; 3499 3500#ifdef _MSC_VER 3501 idx = 0; 3502#endif 3503 3504 /* Initialize input, removing packets from source queue, filtering by path. 3505 * Note: this may reorder packets from different paths. 3506 */ 3507 many_ctx.ctl = ctl; 3508 many_ctx.path = path; 3509 TAILQ_INIT(&many_ctx.input_q); 3510 if (q == &ctl->sc_scheduled_packets) 3511 { 3512 ctl->sc_cur_packno = lsquic_senhist_largest(&ctl->sc_senhist); 3513 q_name = "scheduled"; 3514 for (packet_out = TAILQ_FIRST(q); packet_out != NULL; packet_out = next) 3515 { 3516 next = TAILQ_NEXT(packet_out, po_next); 3517 if (packet_out->po_path == path 3518 && !(packet_out->po_flags & PO_MTU_PROBE)) 3519 { 3520 send_ctl_sched_remove(ctl, packet_out); 3521 TAILQ_INSERT_TAIL(&many_ctx.input_q, packet_out, po_next); 3522 ++count_src; 3523 } 3524 } 3525 } 3526 else 3527 { 3528 /* This function only deals with scheduled or buffered queues */ 3529 assert(q == &ctl->sc_buffered_packets[0].bpq_packets 3530 || q == &ctl->sc_buffered_packets[1].bpq_packets); 3531 idx = q == &ctl->sc_buffered_packets[1].bpq_packets; 3532 q_name = "buffered"; 3533 for (packet_out = TAILQ_FIRST(q); packet_out != NULL; packet_out = next) 3534 { 3535 next = TAILQ_NEXT(packet_out, po_next); 3536 if (packet_out->po_path == path) 3537 { 3538 TAILQ_REMOVE(q, packet_out, po_next); 3539 --ctl->sc_buffered_packets[idx].bpq_count; 3540 TAILQ_INSERT_TAIL(&many_ctx.input_q, packet_out, po_next); 3541 ++count_src; 3542 } 3543 } 3544 } 3545 lsquic_packet_resize_init(&prctx, ctl->sc_enpub, lconn, &many_ctx, 3546 &resize_many_funcs); 3547 3548 /* Get new packets, appending them to appropriate queue */ 3549 if (q == &ctl->sc_scheduled_packets) 3550 while (packet_out = lsquic_packet_resize_next(&prctx), packet_out != NULL) 3551 { 3552 ++count_dst; 3553 packet_out->po_packno = send_ctl_next_packno(ctl); 3554 send_ctl_sched_append(ctl, packet_out); 3555 LSQ_DEBUG("created packet %"PRIu64, packet_out->po_packno); 3556 EV_LOG_PACKET_CREATED(LSQUIC_LOG_CONN_ID, packet_out); 3557 } 3558 else 3559 while (packet_out = lsquic_packet_resize_next(&prctx), packet_out != NULL) 3560 { 3561 ++count_dst; 3562 TAILQ_INSERT_TAIL(q, packet_out, po_next); 3563 ++ctl->sc_buffered_packets[idx].bpq_count; 3564 } 3565 3566 /* Verify success */ 3567 if (lsquic_packet_resize_is_error(&prctx)) 3568 { 3569 LSQ_WARN("error resizing packets in %s queue", q_name); 3570 goto err; 3571 } 3572 if (count_dst < 1 || !TAILQ_EMPTY(&many_ctx.input_q)) 3573 { 3574 /* A bit of insurance, this being new code */ 3575 LSQ_WARN("unexpected values resizing packets in %s queue: count: %d; " 3576 "empty: %d", q_name, count_dst, TAILQ_EMPTY(&many_ctx.input_q)); 3577 goto err; 3578 } 3579 LSQ_DEBUG("resized %u packets in %s queue, outputting %u packets", 3580 count_src, q_name, count_dst); 3581 return; 3582 3583 err: 3584 lconn->cn_if->ci_internal_error(lconn, "error resizing packets"); 3585 return; 3586} 3587 3588 3589void 3590lsquic_send_ctl_repath (struct lsquic_send_ctl *ctl, 3591 const struct network_path *old, const struct network_path *new, 3592 int keep_path_properties) 3593{ 3594 struct lsquic_packet_out *packet_out; 3595 unsigned count; 3596 struct lsquic_packets_tailq *const *q; 3597 struct lsquic_packets_tailq *const queues[] = { 3598 &ctl->sc_scheduled_packets, 3599 &ctl->sc_unacked_packets[PNS_INIT], 3600 &ctl->sc_unacked_packets[PNS_HSK], 3601 &ctl->sc_unacked_packets[PNS_APP], 3602 &ctl->sc_lost_packets, 3603 &ctl->sc_buffered_packets[0].bpq_packets, 3604 &ctl->sc_buffered_packets[1].bpq_packets, 3605 }; 3606 3607 assert(ctl->sc_flags & SC_IETF); 3608 3609 count = 0; 3610 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 3611 TAILQ_FOREACH(packet_out, *q, po_next) 3612 if (packet_out->po_path == old) 3613 { 3614 ++count; 3615 packet_out->po_path = new; 3616 if (packet_out->po_flags & PO_ENCRYPTED) 3617 send_ctl_return_enc_data(ctl, packet_out); 3618 if (packet_out->po_frame_types 3619 & (QUIC_FTBIT_PATH_CHALLENGE|QUIC_FTBIT_PATH_RESPONSE)) 3620 /* This is a corner case, we just want to avoid protocol 3621 * violation. No optimization is done. If we happen to 3622 * send a packet of padding, oh well. 3623 */ 3624 lsquic_packet_out_pad_over(packet_out, 3625 QUIC_FTBIT_PATH_CHALLENGE|QUIC_FTBIT_PATH_RESPONSE); 3626 } 3627 3628 LSQ_DEBUG("repathed %u packet%.*s", count, count != 1, "s"); 3629 3630 if (keep_path_properties) 3631 LSQ_DEBUG("keeping path properties: MTU, RTT, and CC state"); 3632 else 3633 { 3634 lsquic_send_ctl_resize(ctl); 3635 memset(&ctl->sc_conn_pub->rtt_stats, 0, 3636 sizeof(ctl->sc_conn_pub->rtt_stats)); 3637 ctl->sc_ci->cci_reinit(CGP(ctl)); 3638 } 3639} 3640 3641 3642/* Drop PATH_CHALLENGE and PATH_RESPONSE packets for path `path'. */ 3643void 3644lsquic_send_ctl_cancel_path_verification (struct lsquic_send_ctl *ctl, 3645 const struct network_path *path) 3646{ 3647 struct lsquic_packet_out *packet_out, *next; 3648 3649 /* We need only to examine the scheduled queue as lost challenges and 3650 * responses are not retransmitted. 3651 */ 3652 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 3653 packet_out = next) 3654 { 3655 next = TAILQ_NEXT(packet_out, po_next); 3656 if (packet_out->po_path == path) 3657 { 3658 assert((packet_out->po_frame_types 3659 & (QUIC_FTBIT_PATH_CHALLENGE|QUIC_FTBIT_PATH_RESPONSE)) 3660 || packet_out->po_frame_types == QUIC_FTBIT_PADDING); 3661 assert(!(packet_out->po_frame_types & ctl->sc_retx_frames)); 3662 send_ctl_maybe_renumber_sched_to_right(ctl, packet_out); 3663 send_ctl_sched_remove(ctl, packet_out); 3664 assert(packet_out->po_loss_chain == packet_out); 3665 send_ctl_destroy_packet(ctl, packet_out); 3666 } 3667 } 3668} 3669 3670 3671/* Examine packets in scheduled and buffered queues and resize packets if 3672 * they exceed path MTU. 3673 */ 3674void 3675lsquic_send_ctl_resize (struct lsquic_send_ctl *ctl) 3676{ 3677 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3678 struct lsquic_packet_out *packet_out; 3679 struct lsquic_packets_tailq *const *q; 3680 struct lsquic_packets_tailq *const queues[] = { 3681 &ctl->sc_scheduled_packets, 3682 &ctl->sc_buffered_packets[0].bpq_packets, 3683 &ctl->sc_buffered_packets[1].bpq_packets, 3684 }; 3685 size_t size; 3686 int path_ids /* assuming a reasonable number of paths */, q_idxs; 3687 3688 assert(ctl->sc_flags & SC_IETF); 3689 3690 q_idxs = 0; 3691 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 3692 { 3693 path_ids = 0; 3694 redo_q: 3695 TAILQ_FOREACH(packet_out, *q, po_next) 3696 if (0 == (path_ids & (1 << packet_out->po_path->np_path_id)) 3697 && !(packet_out->po_flags & PO_MTU_PROBE)) 3698 { 3699 size = lsquic_packet_out_total_sz(lconn, packet_out); 3700 if (size > packet_out->po_path->np_pack_size) 3701 { 3702 send_ctl_resize_q(ctl, *q, packet_out->po_path); 3703 path_ids |= 1 << packet_out->po_path->np_path_id; 3704 q_idxs |= 1 << (q - queues); 3705 goto redo_q; 3706 } 3707 } 3708 } 3709 3710 LSQ_DEBUG("resized packets in queues: 0x%X", q_idxs); 3711 lsquic_send_ctl_sanity_check(ctl); 3712} 3713 3714 3715void 3716lsquic_send_ctl_return_enc_data (struct lsquic_send_ctl *ctl) 3717{ 3718 struct lsquic_packet_out *packet_out; 3719 3720 assert(!(ctl->sc_flags & SC_IETF)); 3721 3722 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 3723 if (packet_out->po_flags & PO_ENCRYPTED) 3724 send_ctl_return_enc_data(ctl, packet_out); 3725} 3726 3727 3728/* When client updated DCID based on the first packet returned by the server, 3729 * we must update the number of bytes scheduled if the DCID length changed 3730 * because this length is used to calculate packet size. 3731 */ 3732void 3733lsquic_send_ctl_cidlen_change (struct lsquic_send_ctl *ctl, 3734 unsigned orig_cid_len, unsigned new_cid_len) 3735{ 3736 unsigned diff; 3737 3738 assert(!(ctl->sc_conn_pub->lconn->cn_flags & LSCONN_SERVER)); 3739 if (ctl->sc_n_scheduled) 3740 { 3741 ctl->sc_flags |= SC_CIDLEN; 3742 ctl->sc_cidlen = (signed char) new_cid_len - (signed char) orig_cid_len; 3743 if (new_cid_len > orig_cid_len) 3744 { 3745 diff = new_cid_len - orig_cid_len; 3746 diff *= ctl->sc_n_scheduled; 3747 ctl->sc_bytes_scheduled += diff; 3748 LSQ_DEBUG("increased bytes scheduled by %u bytes to %u", 3749 diff, ctl->sc_bytes_scheduled); 3750 } 3751 else if (new_cid_len < orig_cid_len) 3752 { 3753 diff = orig_cid_len - new_cid_len; 3754 diff *= ctl->sc_n_scheduled; 3755 ctl->sc_bytes_scheduled -= diff; 3756 LSQ_DEBUG("decreased bytes scheduled by %u bytes to %u", 3757 diff, ctl->sc_bytes_scheduled); 3758 } 3759 else 3760 LSQ_DEBUG("DCID length did not change"); 3761 } 3762 else 3763 LSQ_DEBUG("no scheduled packets at the time of DCID change"); 3764} 3765 3766 3767void 3768lsquic_send_ctl_begin_optack_detection (struct lsquic_send_ctl *ctl) 3769{ 3770 uint8_t rand; 3771 3772 rand = lsquic_crand_get_byte(ctl->sc_enpub->enp_crand); 3773 ctl->sc_gap = ctl->sc_cur_packno + 1 + rand; 3774} 3775 3776 3777void 3778lsquic_send_ctl_path_validated (struct lsquic_send_ctl *ctl) 3779{ 3780 LSQ_DEBUG("path validated: switch to regular can_send"); 3781 ctl->sc_can_send = send_ctl_can_send; 3782} 3783 3784 3785int 3786lsquic_send_ctl_can_send_probe (const struct lsquic_send_ctl *ctl, 3787 const struct network_path *path) 3788{ 3789 uint64_t cwnd, pacing_rate; 3790 lsquic_time_t tx_time; 3791 unsigned n_out; 3792 3793 assert(!send_ctl_in_recovery(ctl)); 3794 3795 n_out = send_ctl_all_bytes_out(ctl); 3796 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 3797 if (ctl->sc_flags & SC_PACE) 3798 { 3799 if (n_out + path->np_pack_size >= cwnd) 3800 return 0; 3801 pacing_rate = ctl->sc_ci->cci_pacing_rate(CGP(ctl), 0); 3802 if (!pacing_rate) 3803 pacing_rate = 1; 3804 tx_time = (uint64_t) path->np_pack_size * 1000000 / pacing_rate; 3805 return lsquic_pacer_can_schedule_probe(&ctl->sc_pacer, 3806 ctl->sc_n_scheduled + ctl->sc_n_in_flight_all, tx_time); 3807 } 3808 else 3809 return n_out + path->np_pack_size < cwnd; 3810} 3811 3812 3813void 3814lsquic_send_ctl_disable_ecn (struct lsquic_send_ctl *ctl) 3815{ 3816 struct lsquic_packet_out *packet_out; 3817 3818 LSQ_INFO("disable ECN"); 3819 ctl->sc_ecn = ECN_NOT_ECT; 3820 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 3821 lsquic_packet_out_set_ecn(packet_out, ECN_NOT_ECT); 3822} 3823 3824 3825void 3826lsquic_send_ctl_snapshot (struct lsquic_send_ctl *ctl, 3827 struct send_ctl_state *ctl_state) 3828{ 3829 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3830 int buffered, repace; 3831 3832 buffered = !lsquic_send_ctl_schedule_stream_packets_immediately(ctl); 3833 repace = !buffered && (ctl->sc_flags & SC_PACE); 3834 3835 if (repace) 3836 ctl_state->pacer = ctl->sc_pacer; 3837 3838 if (buffered) 3839 { 3840 lconn->cn_if->ci_ack_snapshot(lconn, &ctl_state->ack_state); 3841 ctl_state->buf_counts[BPT_OTHER_PRIO] 3842 = ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_count; 3843 ctl_state->buf_counts[BPT_HIGHEST_PRIO] 3844 = ctl->sc_buffered_packets[BPT_HIGHEST_PRIO].bpq_count; 3845 } 3846} 3847 3848 3849static void 3850send_ctl_repace (struct lsquic_send_ctl *ctl, const struct pacer *pacer, 3851 unsigned count) 3852{ 3853 unsigned n; 3854 int in_rec; 3855 3856 LSQ_DEBUG("repace, count: %u", count); 3857 ctl->sc_pacer = *pacer; 3858 3859 in_rec = send_ctl_in_recovery(ctl); 3860 for (n = 0; n < count; ++n) 3861 lsquic_pacer_packet_scheduled(&ctl->sc_pacer, 3862 ctl->sc_n_in_flight_retx + ctl->sc_n_scheduled + n, in_rec, 3863 send_ctl_transfer_time, ctl); 3864} 3865 3866 3867void 3868lsquic_send_ctl_rollback (struct lsquic_send_ctl *ctl, 3869 struct send_ctl_state *ctl_state, const struct iovec *last_iov, 3870 size_t shortfall) 3871{ 3872 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3873 struct lsquic_packet_out *packet_out, *next; 3874 struct lsquic_packets_tailq *packets; 3875 struct stream_frame stream_frame; 3876 struct packet_out_frec_iter pofi; 3877 enum buf_packet_type packet_type; 3878 unsigned orig_count, new_count; 3879 enum quic_ft_bit lost_types; 3880 int buffered, repace, len, to_end; 3881 unsigned short prev_frec_len; 3882 struct frame_rec *frec; 3883 3884 buffered = !lsquic_send_ctl_schedule_stream_packets_immediately(ctl); 3885 repace = !buffered && (ctl->sc_flags & SC_PACE); 3886 3887 if (!buffered) 3888 { 3889 orig_count = ctl->sc_n_scheduled; 3890 packets = &ctl->sc_scheduled_packets; 3891 packet_type = 0; /* Not necessary, but compiler complains */ 3892 } 3893 else if (ctl_state->buf_counts[BPT_HIGHEST_PRIO] 3894 < ctl->sc_buffered_packets[BPT_HIGHEST_PRIO].bpq_count) 3895 { 3896 packets = &ctl->sc_buffered_packets[BPT_HIGHEST_PRIO].bpq_packets; 3897 orig_count = ctl->sc_buffered_packets[BPT_HIGHEST_PRIO].bpq_count; 3898 packet_type = BPT_HIGHEST_PRIO; 3899 } 3900 else 3901 { 3902 packets = &ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets; 3903 orig_count = ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_count; 3904 packet_type = BPT_OTHER_PRIO; 3905 } 3906 3907 /* Now find last packet: */ 3908 TAILQ_FOREACH(packet_out, packets, po_next) 3909 if ((unsigned char *) last_iov->iov_base >= packet_out->po_data 3910 && (unsigned char *) last_iov->iov_base 3911 < packet_out->po_data + packet_out->po_data_sz) 3912 break; 3913 3914 if (!packet_out) 3915 { 3916 lconn->cn_if->ci_internal_error(lconn, 3917 "rollback failed: cannot find packet"); 3918 return; 3919 } 3920 3921 for (frec = lsquic_pofi_first(&pofi, packet_out); frec; 3922 frec = lsquic_pofi_next(&pofi)) 3923 if (frec->fe_frame_type == QUIC_FRAME_STREAM 3924 /* At the time of this writing, pwritev() generates a single STREAM 3925 * frame per packet. To keep code future-proof, we use an extra 3926 * check. 3927 */ 3928 && (unsigned char *) last_iov->iov_base 3929 > packet_out->po_data + frec->fe_off 3930 && (unsigned char *) last_iov->iov_base 3931 < packet_out->po_data + frec->fe_off + frec->fe_len) 3932 break; 3933 3934 if (!frec) 3935 { 3936 lconn->cn_if->ci_internal_error(lconn, 3937 "rollback failed: cannot find frame record"); 3938 return; 3939 } 3940 3941 /* Strictly less because of the STREAM frame header */ 3942 assert(last_iov->iov_len < frec->fe_len); 3943 3944 len = lconn->cn_pf->pf_parse_stream_frame( 3945 packet_out->po_data + frec->fe_off, frec->fe_len, &stream_frame); 3946 if (len < 0) 3947 { 3948 lconn->cn_if->ci_internal_error(lconn, 3949 "error parsing own STREAM frame"); 3950 return; 3951 } 3952 3953 if (stream_frame.data_frame.df_size > last_iov->iov_len - shortfall) 3954 { 3955 packet_out->po_data_sz = (unsigned char *) last_iov->iov_base 3956 + last_iov->iov_len - shortfall - packet_out->po_data; 3957 prev_frec_len = frec->fe_len; 3958 frec->fe_len = packet_out->po_data_sz - frec->fe_off; 3959 to_end = lconn->cn_pf->pf_dec_stream_frame_size( 3960 packet_out->po_data + frec->fe_off, 3961 stream_frame.data_frame.df_size - (prev_frec_len - frec->fe_len)); 3962 if (to_end) 3963 { /* A frame that's too short may be generated when pwritev runs out 3964 * of iovecs. In that case, we adjust it here. 3965 */ 3966 if (!(packet_out->po_flags & PO_STREAM_END)) 3967 LSQ_DEBUG("set stream-end flag on truncated packet"); 3968 packet_out->po_flags |= PO_STREAM_END; 3969 } 3970 if (!buffered) 3971 ctl->sc_bytes_scheduled -= prev_frec_len - frec->fe_len; 3972 } 3973 else 3974 assert(stream_frame.data_frame.df_size 3975 == last_iov->iov_len - shortfall); 3976 3977 /* Drop any frames that follow */ 3978 for (frec = lsquic_pofi_next(&pofi); frec; frec = lsquic_pofi_next(&pofi)) 3979 frec->fe_frame_type = 0; 3980 3981 /* Return unused packets */ 3982 new_count = orig_count; 3983 lost_types = 0; 3984 for (packet_out = TAILQ_NEXT(packet_out, po_next); packet_out != NULL; 3985 packet_out = next) 3986 { 3987 next = TAILQ_NEXT(packet_out, po_next); 3988 --new_count; 3989 lost_types |= packet_out->po_frame_types; 3990 /* Undo lsquic_send_ctl_get_packet_for_stream() */ 3991 if (!buffered) 3992 send_ctl_sched_remove(ctl, packet_out); 3993 else 3994 { 3995 TAILQ_REMOVE(packets, packet_out, po_next); 3996 --ctl->sc_buffered_packets[packet_type].bpq_count; 3997 } 3998 send_ctl_destroy_packet(ctl, packet_out); 3999 } 4000 4001 if (new_count < orig_count && repace) 4002 send_ctl_repace(ctl, &ctl_state->pacer, new_count); 4003 if (buffered && (lost_types & QUIC_FTBIT_ACK)) 4004 lconn->cn_if->ci_ack_rollback(lconn, &ctl_state->ack_state); 4005} 4006 4007 4008/* Find 0-RTT packets and change them to 1-RTT packets */ 4009void 4010lsquic_send_ctl_0rtt_to_1rtt (struct lsquic_send_ctl *ctl) 4011{ 4012 struct lsquic_packet_out *packet_out; 4013 unsigned count; 4014 struct lsquic_packets_tailq *const *q; 4015 struct lsquic_packets_tailq *const queues[] = { 4016 &ctl->sc_scheduled_packets, 4017 &ctl->sc_unacked_packets[PNS_APP], 4018 &ctl->sc_lost_packets, 4019 &ctl->sc_buffered_packets[0].bpq_packets, 4020 &ctl->sc_buffered_packets[1].bpq_packets, 4021 }; 4022 4023 assert(ctl->sc_flags & SC_IETF); 4024 4025 while (packet_out = TAILQ_FIRST(&ctl->sc_0rtt_stash), packet_out != NULL) 4026 { 4027 TAILQ_REMOVE(&ctl->sc_0rtt_stash, packet_out, po_next); 4028 TAILQ_INSERT_TAIL(&ctl->sc_lost_packets, packet_out, po_next); 4029 packet_out->po_flags |= PO_LOST; 4030 } 4031 4032 count = 0; 4033 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 4034 TAILQ_FOREACH(packet_out, *q, po_next) 4035 if (packet_out->po_header_type == HETY_0RTT) 4036 { 4037 ++count; 4038 packet_out->po_header_type = HETY_NOT_SET; 4039 if (packet_out->po_flags & PO_ENCRYPTED) 4040 send_ctl_return_enc_data(ctl, packet_out); 4041 } 4042 4043 LSQ_DEBUG("handshake ok: changed %u packet%.*s from 0-RTT to 1-RTT", 4044 count, count != 1, "s"); 4045} 4046 4047 4048/* Remove 0-RTT packets from the unacked queue and wait to retransmit them 4049 * after handshake succeeds. This is the most common case. There could 4050 * (theoretically) be some corner cases where 0-RTT packets are in the 4051 * scheduled queue, but we let those be lost naturally if that occurs. 4052 */ 4053void 4054lsquic_send_ctl_stash_0rtt_packets (struct lsquic_send_ctl *ctl) 4055{ 4056 struct lsquic_packet_out *packet_out, *next; 4057 unsigned count, packet_sz; 4058 4059 count = 0; 4060 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[PNS_APP]); 4061 packet_out; packet_out = next) 4062 { 4063 next = TAILQ_NEXT(packet_out, po_next); 4064 if (packet_out->po_header_type == HETY_0RTT) 4065 { 4066 packet_sz = packet_out_sent_sz(packet_out); 4067 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 4068 TAILQ_INSERT_TAIL(&ctl->sc_0rtt_stash, packet_out, po_next); 4069 ++count; 4070 } 4071 } 4072 4073 LSQ_DEBUG("stashed %u 0-RTT packet%.*s", count, count != 1, "s"); 4074} 4075