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