lsquic_send_ctl.c revision 4429f8ea
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#if LSQUIC_CONN_STATS 903 ++ctl->sc_conn_pub->conn_stats->out.lost_packets; 904#endif 905 906 if (packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)) 907 { 908 ctl->sc_flags |= SC_LOST_ACK_INIT << lsquic_packet_out_pns(packet_out); 909 LSQ_DEBUG("lost ACK in packet %"PRIu64, packet_out->po_packno); 910 } 911 912 if (ctl->sc_ci->cci_lost) 913 ctl->sc_ci->cci_lost(CGP(ctl), packet_out, packet_sz); 914 915 /* This is a client-only check, server check happens in mini conn */ 916 if (lsquic_send_ctl_ecn_turned_on(ctl) 917 && 0 == ctl->sc_ecn_total_acked[PNS_INIT] 918 && HETY_INITIAL == packet_out->po_header_type 919 && 3 == packet_out->po_packno) 920 { 921 LSQ_DEBUG("possible ECN black hole during handshake, disable ECN"); 922 lsquic_send_ctl_disable_ecn(ctl); 923 } 924 925 if (packet_out->po_frame_types & ctl->sc_retx_frames) 926 { 927 LSQ_DEBUG("lost retransmittable packet %"PRIu64, 928 packet_out->po_packno); 929 send_ctl_record_loss(ctl, packet_out); 930 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 931 TAILQ_INSERT_TAIL(&ctl->sc_lost_packets, packet_out, po_next); 932 packet_out->po_flags |= PO_LOST; 933 return 1; 934 } 935 else 936 { 937 LSQ_DEBUG("lost unretransmittable packet %"PRIu64, 938 packet_out->po_packno); 939 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 940 send_ctl_destroy_chain(ctl, packet_out, next); 941 send_ctl_destroy_packet(ctl, packet_out); 942 return 0; 943 } 944} 945 946 947static int 948send_ctl_handle_lost_mtu_probe (struct lsquic_send_ctl *ctl, 949 struct lsquic_packet_out *packet_out) 950{ 951 unsigned packet_sz; 952 953 LSQ_DEBUG("lost MTU probe in packet %"PRIu64, packet_out->po_packno); 954 packet_sz = packet_out_sent_sz(packet_out); 955 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 956 assert(packet_out->po_loss_chain == packet_out); 957 send_ctl_destroy_packet(ctl, packet_out); 958 return 0; 959} 960 961 962/* Returns true if packet was rescheduled, false otherwise. In the latter 963 * case, you should not dereference packet_out after the function returns. 964 */ 965static int 966send_ctl_handle_lost_packet (struct lsquic_send_ctl *ctl, 967 struct lsquic_packet_out *packet_out, struct lsquic_packet_out **next) 968{ 969 if (0 == (packet_out->po_flags & PO_MTU_PROBE)) 970 return send_ctl_handle_regular_lost_packet(ctl, packet_out, next); 971 else 972 return send_ctl_handle_lost_mtu_probe(ctl, packet_out); 973} 974 975 976static lsquic_packno_t 977largest_retx_packet_number (const struct lsquic_send_ctl *ctl, 978 enum packnum_space pns) 979{ 980 const lsquic_packet_out_t *packet_out; 981 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_unacked_packets[pns], 982 lsquic_packets_tailq, po_next) 983 { 984 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON)) 985 && (packet_out->po_frame_types & ctl->sc_retx_frames)) 986 return packet_out->po_packno; 987 } 988 return 0; 989} 990 991 992static void 993send_ctl_loss_event (struct lsquic_send_ctl *ctl) 994{ 995 ctl->sc_ci->cci_loss(CGP(ctl)); 996 if (ctl->sc_flags & SC_PACE) 997 lsquic_pacer_loss_event(&ctl->sc_pacer); 998 ctl->sc_largest_sent_at_cutback = 999 lsquic_senhist_largest(&ctl->sc_senhist); 1000} 1001 1002 1003/* Return true if losses were detected, false otherwise */ 1004static int 1005send_ctl_detect_losses (struct lsquic_send_ctl *ctl, enum packnum_space pns, 1006 lsquic_time_t time) 1007{ 1008 lsquic_packet_out_t *packet_out, *next; 1009 lsquic_packno_t largest_retx_packno, largest_lost_packno; 1010 1011 largest_retx_packno = largest_retx_packet_number(ctl, pns); 1012 largest_lost_packno = 0; 1013 ctl->sc_loss_to = 0; 1014 1015 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); 1016 packet_out && packet_out->po_packno <= ctl->sc_largest_acked_packno; 1017 packet_out = next) 1018 { 1019 next = TAILQ_NEXT(packet_out, po_next); 1020 1021 if (packet_out->po_flags & (PO_LOSS_REC|PO_POISON)) 1022 continue; 1023 1024 if (packet_out->po_packno + N_NACKS_BEFORE_RETX < 1025 ctl->sc_largest_acked_packno) 1026 { 1027 LSQ_DEBUG("loss by FACK detected, packet %"PRIu64, 1028 packet_out->po_packno); 1029 if (0 == (packet_out->po_flags & PO_MTU_PROBE)) 1030 largest_lost_packno = packet_out->po_packno; 1031 (void) send_ctl_handle_lost_packet(ctl, packet_out, &next); 1032 continue; 1033 } 1034 1035 if (largest_retx_packno 1036 && (packet_out->po_frame_types & ctl->sc_retx_frames) 1037 && 0 == (packet_out->po_flags & PO_MTU_PROBE) 1038 && largest_retx_packno <= ctl->sc_largest_acked_packno) 1039 { 1040 LSQ_DEBUG("loss by early retransmit detected, packet %"PRIu64, 1041 packet_out->po_packno); 1042 largest_lost_packno = packet_out->po_packno; 1043 ctl->sc_loss_to = 1044 lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats) / 4; 1045 LSQ_DEBUG("set sc_loss_to to %"PRIu64", packet %"PRIu64, 1046 ctl->sc_loss_to, packet_out->po_packno); 1047 (void) send_ctl_handle_lost_packet(ctl, packet_out, &next); 1048 continue; 1049 } 1050 1051 if (ctl->sc_largest_acked_sent_time > packet_out->po_sent + 1052 lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats)) 1053 { 1054 LSQ_DEBUG("loss by sent time detected: packet %"PRIu64, 1055 packet_out->po_packno); 1056 if ((packet_out->po_frame_types & ctl->sc_retx_frames) 1057 && 0 == (packet_out->po_flags & PO_MTU_PROBE)) 1058 largest_lost_packno = packet_out->po_packno; 1059 else { /* don't count it as a loss */; } 1060 (void) send_ctl_handle_lost_packet(ctl, packet_out, &next); 1061 continue; 1062 } 1063 } 1064 1065 if (largest_lost_packno > ctl->sc_largest_sent_at_cutback) 1066 { 1067 LSQ_DEBUG("detected new loss: packet %"PRIu64"; new lsac: " 1068 "%"PRIu64, largest_lost_packno, ctl->sc_largest_sent_at_cutback); 1069 send_ctl_loss_event(ctl); 1070 } 1071 else if (largest_lost_packno) 1072 /* Lost packets whose numbers are smaller than the largest packet 1073 * number sent at the time of the last loss event indicate the same 1074 * loss event. This follows NewReno logic, see RFC 6582. 1075 */ 1076 LSQ_DEBUG("ignore loss of packet %"PRIu64" smaller than lsac " 1077 "%"PRIu64, largest_lost_packno, ctl->sc_largest_sent_at_cutback); 1078 1079 return largest_lost_packno > ctl->sc_largest_sent_at_cutback; 1080} 1081 1082 1083static void 1084send_ctl_mtu_probe_acked (struct lsquic_send_ctl *ctl, 1085 struct lsquic_packet_out *packet_out) 1086{ 1087 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 1088 1089 LSQ_DEBUG("MTU probe in packet %"PRIu64" has been ACKed", 1090 packet_out->po_packno); 1091 assert(lconn->cn_if->ci_mtu_probe_acked); 1092 if (lconn->cn_if->ci_mtu_probe_acked) 1093 lconn->cn_if->ci_mtu_probe_acked(lconn, packet_out); 1094} 1095 1096 1097int 1098lsquic_send_ctl_got_ack (lsquic_send_ctl_t *ctl, 1099 const struct ack_info *acki, 1100 lsquic_time_t ack_recv_time, lsquic_time_t now) 1101{ 1102 const struct lsquic_packno_range *range = 1103 &acki->ranges[ acki->n_ranges - 1 ]; 1104 lsquic_packet_out_t *packet_out, *next; 1105 lsquic_packno_t smallest_unacked; 1106 lsquic_packno_t ack2ed[2]; 1107 unsigned packet_sz; 1108 int app_limited, losses_detected; 1109 signed char do_rtt, skip_checks; 1110 enum packnum_space pns; 1111 unsigned ecn_total_acked, ecn_ce_cnt, one_rtt_cnt; 1112 1113 pns = acki->pns; 1114 ctl->sc_flags |= SC_ACK_RECV_INIT << pns; 1115 packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); 1116#if __GNUC__ 1117 __builtin_prefetch(packet_out); 1118#endif 1119 1120#if __GNUC__ 1121# define UNLIKELY(cond) __builtin_expect(cond, 0) 1122#else 1123# define UNLIKELY(cond) cond 1124#endif 1125 1126#if __GNUC__ 1127 if (UNLIKELY(LSQ_LOG_ENABLED(LSQ_LOG_DEBUG))) 1128#endif 1129 LSQ_DEBUG("Got ACK frame, largest acked: %"PRIu64"; delta: %"PRIu64, 1130 largest_acked(acki), acki->lack_delta); 1131 1132 /* Validate ACK first: */ 1133 if (UNLIKELY(largest_acked(acki) 1134 > lsquic_senhist_largest(&ctl->sc_senhist))) 1135 { 1136 LSQ_INFO("at least one packet in ACK range [%"PRIu64" - %"PRIu64"] " 1137 "was never sent", acki->ranges[0].low, acki->ranges[0].high); 1138 return -1; 1139 } 1140 1141 if (ctl->sc_ci->cci_begin_ack) 1142 ctl->sc_ci->cci_begin_ack(CGP(ctl), ack_recv_time, 1143 ctl->sc_bytes_unacked_all); 1144 1145 ecn_total_acked = 0; 1146 ecn_ce_cnt = 0; 1147 one_rtt_cnt = 0; 1148 1149 if (UNLIKELY(ctl->sc_flags & SC_WAS_QUIET)) 1150 { 1151 ctl->sc_flags &= ~SC_WAS_QUIET; 1152 LSQ_DEBUG("ACK comes after a period of quiescence"); 1153 ctl->sc_ci->cci_was_quiet(CGP(ctl), now, ctl->sc_bytes_unacked_all); 1154 } 1155 1156 if (UNLIKELY(!packet_out)) 1157 goto no_unacked_packets; 1158 1159 smallest_unacked = packet_out->po_packno; 1160 LSQ_DEBUG("Smallest unacked: %"PRIu64, smallest_unacked); 1161 1162 ack2ed[1] = 0; 1163 1164 if (packet_out->po_packno > largest_acked(acki)) 1165 goto detect_losses; 1166 1167 if (largest_acked(acki) > ctl->sc_cur_rt_end) 1168 { 1169 ++ctl->sc_rt_count; 1170 ctl->sc_cur_rt_end = lsquic_senhist_largest(&ctl->sc_senhist); 1171 } 1172 1173 do_rtt = 0, skip_checks = 0; 1174 app_limited = -1; 1175 do 1176 { 1177 next = TAILQ_NEXT(packet_out, po_next); 1178#if __GNUC__ 1179 __builtin_prefetch(next); 1180#endif 1181 if (skip_checks) 1182 goto after_checks; 1183 /* This is faster than binary search in the normal case when the number 1184 * of ranges is not much larger than the number of unacked packets. 1185 */ 1186 while (UNLIKELY(range->high < packet_out->po_packno)) 1187 --range; 1188 if (range->low <= packet_out->po_packno) 1189 { 1190 skip_checks = range == acki->ranges; 1191 if (app_limited < 0) 1192 app_limited = send_ctl_retx_bytes_out(ctl) + 3 * SC_PACK_SIZE(ctl) /* This 1193 is the "maximum burst" parameter */ 1194 < ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 1195 after_checks: 1196 ctl->sc_largest_acked_packno = packet_out->po_packno; 1197 ctl->sc_largest_acked_sent_time = packet_out->po_sent; 1198 ecn_total_acked += lsquic_packet_out_ecn(packet_out) != ECN_NOT_ECT; 1199 ecn_ce_cnt += lsquic_packet_out_ecn(packet_out) == ECN_CE; 1200 one_rtt_cnt += lsquic_packet_out_enc_level(packet_out) == ENC_LEV_FORW; 1201 if (0 == (packet_out->po_flags 1202 & (PO_LOSS_REC|PO_POISON|PO_MTU_PROBE))) 1203 { 1204 packet_sz = packet_out_sent_sz(packet_out); 1205 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 1206 lsquic_packet_out_ack_streams(packet_out); 1207 LSQ_DEBUG("acking via regular record %"PRIu64, 1208 packet_out->po_packno); 1209 } 1210 else if (packet_out->po_flags & PO_LOSS_REC) 1211 { 1212 packet_sz = packet_out->po_sent_sz; 1213 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, 1214 po_next); 1215 LSQ_DEBUG("acking via loss record %"PRIu64, 1216 packet_out->po_packno); 1217#if LSQUIC_CONN_STATS 1218 ++ctl->sc_conn_pub->conn_stats->out.acked_via_loss; 1219#endif 1220 } 1221 else if (packet_out->po_flags & PO_MTU_PROBE) 1222 { 1223 packet_sz = packet_out_sent_sz(packet_out); 1224 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 1225 send_ctl_mtu_probe_acked(ctl, packet_out); 1226 } 1227 else 1228 { 1229 LSQ_WARN("poisoned packet %"PRIu64" acked", 1230 packet_out->po_packno); 1231 return -1; 1232 } 1233 ack2ed[!!(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK))] 1234 = packet_out->po_ack2ed; 1235 do_rtt |= packet_out->po_packno == largest_acked(acki); 1236 ctl->sc_ci->cci_ack(CGP(ctl), packet_out, packet_sz, now, 1237 app_limited); 1238 send_ctl_destroy_chain(ctl, packet_out, &next); 1239 send_ctl_destroy_packet(ctl, packet_out); 1240 } 1241 packet_out = next; 1242 } 1243 while (packet_out && packet_out->po_packno <= largest_acked(acki)); 1244 1245 if (do_rtt) 1246 { 1247 take_rtt_sample(ctl, ack_recv_time, acki->lack_delta); 1248 ctl->sc_n_consec_rtos = 0; 1249 ctl->sc_n_hsk = 0; 1250 ctl->sc_n_tlp = 0; 1251 } 1252 1253 detect_losses: 1254 losses_detected = send_ctl_detect_losses(ctl, pns, ack_recv_time); 1255 if (send_ctl_first_unacked_retx_packet(ctl, pns)) 1256 set_retx_alarm(ctl, pns, now); 1257 else 1258 { 1259 LSQ_DEBUG("No retransmittable packets: clear alarm"); 1260 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 1261 } 1262 lsquic_send_ctl_sanity_check(ctl); 1263 1264 if ((ctl->sc_flags & SC_NSTP) && ack2ed[1] > ctl->sc_largest_ack2ed[pns]) 1265 ctl->sc_largest_ack2ed[pns] = ack2ed[1]; 1266 1267 if (ctl->sc_n_in_flight_retx == 0) 1268 ctl->sc_flags |= SC_WAS_QUIET; 1269 1270 if (one_rtt_cnt) 1271 ctl->sc_flags |= SC_1RTT_ACKED; 1272 1273 if (lsquic_send_ctl_ecn_turned_on(ctl)) 1274 { 1275 const uint64_t sum = acki->ecn_counts[ECN_ECT0] 1276 + acki->ecn_counts[ECN_ECT1] 1277 + acki->ecn_counts[ECN_CE]; 1278 ctl->sc_ecn_total_acked[pns] += ecn_total_acked; 1279 ctl->sc_ecn_ce_cnt[pns] += ecn_ce_cnt; 1280 if (sum >= ctl->sc_ecn_total_acked[pns]) 1281 { 1282 if (sum > ctl->sc_ecn_total_acked[pns]) 1283 ctl->sc_ecn_total_acked[pns] = sum; 1284 if (acki->ecn_counts[ECN_CE] > ctl->sc_ecn_ce_cnt[pns]) 1285 { 1286 ctl->sc_ecn_ce_cnt[pns] = acki->ecn_counts[ECN_CE]; 1287 if (losses_detected) 1288 /* It's either-or. From [draft-ietf-quic-recovery-29], 1289 * Section 7.4: 1290 " When a loss or ECN-CE marking is detected [...] 1291 */ 1292 LSQ_DEBUG("ECN-CE marking detected, but loss event already " 1293 "accounted for"); 1294 else 1295 { 1296 LSQ_DEBUG("ECN-CE marking detected, issue loss event"); 1297 send_ctl_loss_event(ctl); 1298 } 1299 } 1300 } 1301 else 1302 { 1303 LSQ_INFO("ECN total ACKed (%"PRIu64") is greater than the sum " 1304 "of ECN counters (%"PRIu64"): disable ECN", 1305 ctl->sc_ecn_total_acked[pns], sum); 1306 lsquic_send_ctl_disable_ecn(ctl); 1307 } 1308 } 1309 1310 update_n_stop_waiting: 1311 if (!(ctl->sc_flags & (SC_NSTP|SC_IETF))) 1312 { 1313 if (smallest_unacked > smallest_acked(acki)) 1314 /* Peer is acking packets that have been acked already. Schedule 1315 * ACK and STOP_WAITING frame to chop the range if we get two of 1316 * these in a row. 1317 */ 1318 ++ctl->sc_n_stop_waiting; 1319 else 1320 ctl->sc_n_stop_waiting = 0; 1321 } 1322 lsquic_send_ctl_sanity_check(ctl); 1323 if (ctl->sc_ci->cci_end_ack) 1324 ctl->sc_ci->cci_end_ack(CGP(ctl), ctl->sc_bytes_unacked_all); 1325 if (ctl->sc_gap < smallest_acked(acki)) 1326 send_ctl_reschedule_poison(ctl); 1327 return 0; 1328 1329 no_unacked_packets: 1330 smallest_unacked = lsquic_senhist_largest(&ctl->sc_senhist) + 1; 1331 ctl->sc_flags |= SC_WAS_QUIET; 1332 goto update_n_stop_waiting; 1333} 1334 1335 1336lsquic_packno_t 1337lsquic_send_ctl_smallest_unacked (lsquic_send_ctl_t *ctl) 1338{ 1339 const lsquic_packet_out_t *packet_out; 1340 enum packnum_space pns; 1341 1342 /* Packets are always sent out in order (unless we are reordering them 1343 * on purpose). Thus, the first packet on the unacked packets list has 1344 * the smallest packet number of all packets on that list. 1345 */ 1346 for (pns = ctl->sc_flags & SC_IETF ? PNS_INIT : PNS_APP; pns < N_PNS; ++pns) 1347 if ((packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]))) 1348 /* We're OK with using a loss record */ 1349 return packet_out->po_packno; 1350 1351 return lsquic_senhist_largest(&ctl->sc_senhist) + first_packno(ctl); 1352} 1353 1354 1355static struct lsquic_packet_out * 1356send_ctl_next_lost (lsquic_send_ctl_t *ctl) 1357{ 1358 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 1359 struct lsquic_packet_out *lost_packet; 1360 1361 get_next_lost: 1362 lost_packet = TAILQ_FIRST(&ctl->sc_lost_packets); 1363 if (lost_packet) 1364 { 1365 if (lost_packet->po_frame_types & (1 << QUIC_FRAME_STREAM)) 1366 { 1367 if (0 == (lost_packet->po_flags & PO_MINI)) 1368 { 1369 lsquic_packet_out_elide_reset_stream_frames(lost_packet, 0); 1370 if (lost_packet->po_regen_sz >= lost_packet->po_data_sz) 1371 { 1372 LSQ_DEBUG("Dropping packet %"PRIu64" from lost queue", 1373 lost_packet->po_packno); 1374 TAILQ_REMOVE(&ctl->sc_lost_packets, lost_packet, po_next); 1375 lost_packet->po_flags &= ~PO_LOST; 1376 send_ctl_destroy_chain(ctl, lost_packet, NULL); 1377 send_ctl_destroy_packet(ctl, lost_packet); 1378 goto get_next_lost; 1379 } 1380 } 1381 else 1382 { 1383 /* Mini connection only ever sends data on stream 1. There 1384 * is nothing to elide: always resend it. 1385 */ 1386 ; 1387 } 1388 } 1389 1390 if (!lsquic_send_ctl_can_send(ctl)) 1391 return NULL; 1392 1393 if (packet_out_total_sz(lost_packet) <= SC_PACK_SIZE(ctl)) 1394 { 1395 pop_lost_packet: 1396 TAILQ_REMOVE(&ctl->sc_lost_packets, lost_packet, po_next); 1397 lost_packet->po_flags &= ~PO_LOST; 1398 lost_packet->po_flags |= PO_RETX; 1399 } 1400 else 1401 { 1402 /* We delay resizing lost packets as long as possible, hoping that 1403 * it may be ACKed. At this point, however, we have to resize. 1404 */ 1405 if (0 == split_lost_packet(ctl, lost_packet)) 1406 { 1407 lost_packet = TAILQ_FIRST(&ctl->sc_lost_packets); 1408 goto pop_lost_packet; 1409 } 1410 lconn->cn_if->ci_internal_error(lconn, 1411 "error resizing lost packet"); 1412 return NULL; 1413 } 1414 } 1415 1416 return lost_packet; 1417} 1418 1419 1420static lsquic_packno_t 1421send_ctl_next_packno (lsquic_send_ctl_t *ctl) 1422{ 1423 lsquic_packno_t packno; 1424 1425 packno = ++ctl->sc_cur_packno; 1426 if (packno == ctl->sc_gap) 1427 packno = ++ctl->sc_cur_packno; 1428 1429 return packno; 1430} 1431 1432 1433void 1434lsquic_send_ctl_cleanup (lsquic_send_ctl_t *ctl) 1435{ 1436 lsquic_packet_out_t *packet_out, *next; 1437 enum packnum_space pns; 1438 unsigned n; 1439 1440 lsquic_senhist_cleanup(&ctl->sc_senhist); 1441 while ((packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets))) 1442 { 1443 send_ctl_sched_remove(ctl, packet_out); 1444 send_ctl_destroy_packet(ctl, packet_out); 1445 } 1446 assert(0 == ctl->sc_n_scheduled); 1447 assert(0 == ctl->sc_bytes_scheduled); 1448 for (pns = PNS_INIT; pns < N_PNS; ++pns) 1449 while ((packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]))) 1450 { 1451 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, po_next); 1452 packet_out->po_flags &= ~PO_UNACKED; 1453#ifndef NDEBUG 1454 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON))) 1455 { 1456 ctl->sc_bytes_unacked_all -= packet_out_sent_sz(packet_out); 1457 --ctl->sc_n_in_flight_all; 1458 } 1459#endif 1460 send_ctl_destroy_packet(ctl, packet_out); 1461 } 1462 assert(0 == ctl->sc_n_in_flight_all); 1463 assert(0 == ctl->sc_bytes_unacked_all); 1464 while ((packet_out = TAILQ_FIRST(&ctl->sc_lost_packets))) 1465 { 1466 TAILQ_REMOVE(&ctl->sc_lost_packets, packet_out, po_next); 1467 packet_out->po_flags &= ~PO_LOST; 1468 send_ctl_destroy_packet(ctl, packet_out); 1469 } 1470 while ((packet_out = TAILQ_FIRST(&ctl->sc_0rtt_stash))) 1471 { 1472 TAILQ_REMOVE(&ctl->sc_0rtt_stash, packet_out, po_next); 1473 send_ctl_destroy_packet(ctl, packet_out); 1474 } 1475 for (n = 0; n < sizeof(ctl->sc_buffered_packets) / 1476 sizeof(ctl->sc_buffered_packets[0]); ++n) 1477 { 1478 for (packet_out = TAILQ_FIRST(&ctl->sc_buffered_packets[n].bpq_packets); 1479 packet_out; packet_out = next) 1480 { 1481 next = TAILQ_NEXT(packet_out, po_next); 1482 send_ctl_destroy_packet(ctl, packet_out); 1483 } 1484 } 1485 if (ctl->sc_flags & SC_PACE) 1486 lsquic_pacer_cleanup(&ctl->sc_pacer); 1487 ctl->sc_ci->cci_cleanup(CGP(ctl)); 1488 if (ctl->sc_flags & SC_CLEANUP_BBR) 1489 { 1490 assert(ctl->sc_ci == &lsquic_cong_cubic_if); 1491 lsquic_cong_bbr_if.cci_cleanup(&ctl->sc_adaptive_cc.acc_bbr); 1492 } 1493#if LSQUIC_SEND_STATS 1494 LSQ_NOTICE("stats: n_total_sent: %u; n_resent: %u; n_delayed: %u", 1495 ctl->sc_stats.n_total_sent, ctl->sc_stats.n_resent, 1496 ctl->sc_stats.n_delayed); 1497#endif 1498 free(ctl->sc_token); 1499} 1500 1501 1502static unsigned 1503send_ctl_retx_bytes_out (const struct lsquic_send_ctl *ctl) 1504{ 1505 return ctl->sc_bytes_scheduled 1506 + ctl->sc_bytes_unacked_retx 1507 ; 1508} 1509 1510 1511static unsigned 1512send_ctl_all_bytes_out (const struct lsquic_send_ctl *ctl) 1513{ 1514 return ctl->sc_bytes_scheduled 1515 + ctl->sc_bytes_unacked_all 1516 ; 1517} 1518 1519 1520int 1521lsquic_send_ctl_pacer_blocked (struct lsquic_send_ctl *ctl) 1522{ 1523 return (ctl->sc_flags & SC_PACE) 1524 && !lsquic_pacer_can_schedule(&ctl->sc_pacer, 1525 ctl->sc_n_in_flight_all); 1526} 1527 1528 1529static int 1530send_ctl_can_send (struct lsquic_send_ctl *ctl) 1531{ 1532 const unsigned n_out = send_ctl_all_bytes_out(ctl); 1533 LSQ_DEBUG("%s: n_out: %u (unacked_all: %u); cwnd: %"PRIu64, __func__, 1534 n_out, ctl->sc_bytes_unacked_all, 1535 ctl->sc_ci->cci_get_cwnd(CGP(ctl))); 1536 if (ctl->sc_flags & SC_PACE) 1537 { 1538 if (n_out >= ctl->sc_ci->cci_get_cwnd(CGP(ctl))) 1539 return 0; 1540 if (lsquic_pacer_can_schedule(&ctl->sc_pacer, 1541 ctl->sc_n_scheduled + ctl->sc_n_in_flight_all)) 1542 return 1; 1543 if (ctl->sc_flags & SC_SCHED_TICK) 1544 { 1545 ctl->sc_flags &= ~SC_SCHED_TICK; 1546 lsquic_engine_add_conn_to_attq(ctl->sc_enpub, 1547 ctl->sc_conn_pub->lconn, lsquic_pacer_next_sched(&ctl->sc_pacer), 1548 AEW_PACER); 1549 } 1550 return 0; 1551 } 1552 else 1553 return n_out < ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 1554} 1555 1556 1557static int 1558send_ctl_can_send_pre_hsk (struct lsquic_send_ctl *ctl) 1559{ 1560 unsigned bytes_in, bytes_out; 1561 1562 bytes_in = ctl->sc_conn_pub->bytes_in; 1563 bytes_out = ctl->sc_conn_pub->bytes_out + ctl->sc_bytes_scheduled; 1564 if (bytes_out >= bytes_in * 2 + bytes_in / 2 /* This should work out 1565 to around 3 on average */) 1566 { 1567 LSQ_DEBUG("%s: amplification block: %u bytes in, %u bytes out", 1568 __func__, bytes_in, bytes_out); 1569 return 0; 1570 } 1571 else 1572 return send_ctl_can_send(ctl); 1573} 1574 1575 1576#ifndef NDEBUG 1577#if __GNUC__ 1578__attribute__((weak)) 1579#endif 1580#endif 1581int 1582lsquic_send_ctl_can_send (struct lsquic_send_ctl *ctl) 1583{ 1584 return ctl->sc_can_send(ctl); 1585} 1586 1587 1588/* Like lsquic_send_ctl_can_send(), but no mods */ 1589static int 1590send_ctl_could_send (const struct lsquic_send_ctl *ctl) 1591{ 1592 uint64_t cwnd; 1593 unsigned n_out; 1594 1595 if ((ctl->sc_flags & SC_PACE) && lsquic_pacer_delayed(&ctl->sc_pacer)) 1596 return 0; 1597 1598 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 1599 n_out = send_ctl_all_bytes_out(ctl); 1600 return n_out < cwnd; 1601} 1602 1603 1604void 1605lsquic_send_ctl_maybe_app_limited (struct lsquic_send_ctl *ctl, 1606 const struct network_path *path) 1607{ 1608 const struct lsquic_packet_out *packet_out; 1609 1610 packet_out = lsquic_send_ctl_last_scheduled(ctl, PNS_APP, path, 0); 1611 if ((packet_out && lsquic_packet_out_avail(packet_out) > 10) 1612 || send_ctl_could_send(ctl)) 1613 { 1614 LSQ_DEBUG("app-limited"); 1615 ctl->sc_flags |= SC_APP_LIMITED; 1616 } 1617} 1618 1619 1620static void 1621send_ctl_expire (struct lsquic_send_ctl *ctl, enum packnum_space pns, 1622 enum expire_filter filter) 1623{ 1624 lsquic_packet_out_t *packet_out, *next; 1625 int n_resubmitted; 1626 static const char *const filter_type2str[] = { 1627 [EXFI_ALL] = "all", 1628 [EXFI_HSK] = "handshake", 1629 [EXFI_LAST] = "last", 1630 }; 1631 1632 switch (filter) 1633 { 1634 case EXFI_ALL: 1635 n_resubmitted = 0; 1636 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); 1637 packet_out; packet_out = next) 1638 { 1639 next = TAILQ_NEXT(packet_out, po_next); 1640 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON))) 1641 n_resubmitted += send_ctl_handle_lost_packet(ctl, packet_out, 1642 &next); 1643 } 1644 break; 1645 case EXFI_HSK: 1646 n_resubmitted = 0; 1647 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); packet_out; 1648 packet_out = next) 1649 { 1650 next = TAILQ_NEXT(packet_out, po_next); 1651 if (packet_out->po_flags & PO_HELLO) 1652 n_resubmitted += send_ctl_handle_lost_packet(ctl, packet_out, 1653 &next); 1654 } 1655 break; 1656 default: 1657 assert(filter == EXFI_LAST); 1658 packet_out = send_ctl_last_unacked_retx_packet(ctl, pns); 1659 if (packet_out) 1660 n_resubmitted = send_ctl_handle_lost_packet(ctl, packet_out, NULL); 1661 else 1662 n_resubmitted = 0; 1663 break; 1664 } 1665 1666 LSQ_DEBUG("consider %s packets lost: %d resubmitted", 1667 filter_type2str[filter], n_resubmitted); 1668} 1669 1670 1671void 1672lsquic_send_ctl_expire_all (lsquic_send_ctl_t *ctl) 1673{ 1674 enum packnum_space pns; 1675 1676 for (pns = ctl->sc_flags & SC_IETF ? PNS_INIT : PNS_APP; pns < N_PNS; ++pns) 1677 { 1678 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 1679 send_ctl_expire(ctl, pns, EXFI_ALL); 1680 } 1681 lsquic_send_ctl_sanity_check(ctl); 1682} 1683 1684 1685#ifndef NDEBUG 1686void 1687lsquic_send_ctl_do_sanity_check (const struct lsquic_send_ctl *ctl) 1688{ 1689 const struct lsquic_packet_out *packet_out; 1690 lsquic_packno_t prev_packno; 1691 int prev_packno_set; 1692 unsigned count, bytes; 1693 enum packnum_space pns; 1694 1695#if _MSC_VER 1696 prev_packno = 0; 1697#endif 1698 count = 0, bytes = 0; 1699 for (pns = PNS_INIT; pns <= PNS_APP; ++pns) 1700 { 1701 prev_packno_set = 0; 1702 TAILQ_FOREACH(packet_out, &ctl->sc_unacked_packets[pns], po_next) 1703 { 1704 if (prev_packno_set) 1705 assert(packet_out->po_packno > prev_packno); 1706 else 1707 { 1708 prev_packno = packet_out->po_packno; 1709 prev_packno_set = 1; 1710 } 1711 if (0 == (packet_out->po_flags & (PO_LOSS_REC|PO_POISON))) 1712 { 1713 bytes += packet_out_sent_sz(packet_out); 1714 ++count; 1715 } 1716 } 1717 } 1718 assert(count == ctl->sc_n_in_flight_all); 1719 assert(bytes == ctl->sc_bytes_unacked_all); 1720 1721 count = 0, bytes = 0; 1722 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1723 { 1724 assert(packet_out->po_flags & PO_SCHED); 1725 bytes += packet_out_total_sz(packet_out); 1726 ++count; 1727 } 1728 assert(count == ctl->sc_n_scheduled); 1729 assert(bytes == ctl->sc_bytes_scheduled); 1730} 1731 1732 1733#endif 1734 1735 1736void 1737lsquic_send_ctl_scheduled_one (lsquic_send_ctl_t *ctl, 1738 lsquic_packet_out_t *packet_out) 1739{ 1740#ifndef NDEBUG 1741 const lsquic_packet_out_t *last; 1742 last = TAILQ_LAST(&ctl->sc_scheduled_packets, lsquic_packets_tailq); 1743 if (last) 1744 assert((last->po_flags & PO_REPACKNO) || 1745 last->po_packno < packet_out->po_packno); 1746#endif 1747 if (ctl->sc_flags & SC_PACE) 1748 { 1749 unsigned n_out = ctl->sc_n_in_flight_retx + ctl->sc_n_scheduled; 1750 lsquic_pacer_packet_scheduled(&ctl->sc_pacer, n_out, 1751 send_ctl_in_recovery(ctl), send_ctl_transfer_time, ctl); 1752 } 1753 send_ctl_sched_append(ctl, packet_out); 1754} 1755 1756 1757/* Wrapper is used to reset the counter when it's been too long */ 1758static unsigned 1759send_ctl_get_n_consec_rtos (struct lsquic_send_ctl *ctl) 1760{ 1761 lsquic_time_t timeout; 1762 1763 if (ctl->sc_n_consec_rtos) 1764 { 1765 timeout = calculate_packet_rto(ctl); 1766 if (ctl->sc_last_rto_time + timeout < ctl->sc_last_sent_time) 1767 { 1768 ctl->sc_n_consec_rtos = 0; 1769 LSQ_DEBUG("reset RTO counter after %"PRIu64" usec", 1770 ctl->sc_last_sent_time - ctl->sc_last_rto_time); 1771 } 1772 } 1773 1774 return ctl->sc_n_consec_rtos; 1775} 1776 1777 1778/* This mimics the logic in lsquic_send_ctl_next_packet_to_send(): we want 1779 * to check whether the first scheduled packet cannot be sent. 1780 */ 1781int 1782lsquic_send_ctl_sched_is_blocked (struct lsquic_send_ctl *ctl) 1783{ 1784 const lsquic_packet_out_t *packet_out 1785 = TAILQ_FIRST(&ctl->sc_scheduled_packets); 1786 return send_ctl_get_n_consec_rtos(ctl) 1787 && 0 == ctl->sc_next_limit 1788 && packet_out 1789 && !(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)); 1790} 1791 1792 1793static void 1794send_ctl_maybe_zero_pad (struct lsquic_send_ctl *ctl, 1795 struct lsquic_packet_out *initial_packet, size_t limit) 1796{ 1797 struct lsquic_packet_out *packet_out; 1798 size_t cum_size, size; 1799 1800 cum_size = packet_out_total_sz(initial_packet); 1801 if (cum_size >= limit) 1802 { 1803 LSQ_DEBUG("packet size %zu larger than %zu-byte limit: not " 1804 "zero-padding", cum_size, limit); 1805 return; 1806 } 1807 1808 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1809 { 1810 size = packet_out_total_sz(packet_out); 1811 if (cum_size + size > limit) 1812 break; 1813 cum_size += size; 1814 } 1815 1816 LSQ_DEBUG("cum_size: %zu; limit: %zu", cum_size, limit); 1817 assert(cum_size <= limit); 1818 size = limit - cum_size; 1819 if (size > lsquic_packet_out_avail(initial_packet)) 1820 size = lsquic_packet_out_avail(initial_packet); 1821 if (size) 1822 { 1823 memset(initial_packet->po_data + initial_packet->po_data_sz, 0, size); 1824 initial_packet->po_data_sz += size; 1825 initial_packet->po_frame_types |= QUIC_FTBIT_PADDING; 1826 } 1827 LSQ_DEBUG("Added %zu bytes of PADDING to packet %"PRIu64, size, 1828 initial_packet->po_packno); 1829} 1830 1831 1832/* Predict whether lsquic_send_ctl_next_packet_to_send() will return a 1833 * packet by mimicking its logic. Returns true if packet will be returned, 1834 * false otherwise. 1835 */ 1836int 1837lsquic_send_ctl_next_packet_to_send_predict (struct lsquic_send_ctl *ctl) 1838{ 1839 const struct lsquic_packet_out *packet_out; 1840 unsigned n_rtos; 1841 1842 n_rtos = ~0u; 1843 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1844 { 1845 if (!(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)) 1846 && 0 == ctl->sc_next_limit 1847 && 0 != (n_rtos == ~0u ? /* Initialize once */ 1848 (n_rtos = send_ctl_get_n_consec_rtos(ctl)) : n_rtos)) 1849 { 1850 LSQ_DEBUG("send prediction: no, n_rtos: %u", n_rtos); 1851 return 0; 1852 } 1853 if ((packet_out->po_flags & PO_REPACKNO) 1854 && packet_out->po_regen_sz == packet_out->po_data_sz 1855 && packet_out->po_frame_types != QUIC_FTBIT_PATH_CHALLENGE) 1856 { 1857 LSQ_DEBUG("send prediction: packet %"PRIu64" would be dropped, " 1858 "continue", packet_out->po_packno); 1859 continue; 1860 } 1861 LSQ_DEBUG("send prediction: yes, packet %"PRIu64", flags %u, frames 0x%X", 1862 packet_out->po_packno, (unsigned) packet_out->po_flags, 1863 (unsigned) packet_out->po_frame_types); 1864 return 1; 1865 } 1866 1867 LSQ_DEBUG("send prediction: no, no matching scheduled packets"); 1868 return 0; 1869} 1870 1871 1872lsquic_packet_out_t * 1873lsquic_send_ctl_next_packet_to_send (struct lsquic_send_ctl *ctl, 1874 const struct to_coal *to_coal) 1875{ 1876 lsquic_packet_out_t *packet_out; 1877 size_t size; 1878 int dec_limit; 1879 1880 get_packet: 1881 packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); 1882 if (!packet_out) 1883 return NULL; 1884 1885 /* Note: keep logic in this function and in 1886 * lsquic_send_ctl_next_packet_to_send_predict() in synch. 1887 */ 1888 if (!(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)) 1889 && send_ctl_get_n_consec_rtos(ctl)) 1890 { 1891 if (ctl->sc_next_limit) 1892 dec_limit = 1; 1893 else 1894 return NULL; 1895 } 1896 else 1897 dec_limit = 0; 1898 1899 if (packet_out->po_flags & PO_REPACKNO) 1900 { 1901 if (packet_out->po_regen_sz < packet_out->po_data_sz) 1902 { 1903 update_for_resending(ctl, packet_out); 1904 packet_out->po_flags &= ~PO_REPACKNO; 1905 } 1906 else 1907 { 1908 LSQ_DEBUG("Dropping packet %"PRIu64" from scheduled queue", 1909 packet_out->po_packno); 1910 send_ctl_sched_remove(ctl, packet_out); 1911 send_ctl_destroy_chain(ctl, packet_out, NULL); 1912 send_ctl_destroy_packet(ctl, packet_out); 1913 goto get_packet; 1914 } 1915 } 1916 1917 if (UNLIKELY(to_coal != NULL)) 1918 { 1919 /* From [draft-ietf-quic-transport-30], Section-12.2: 1920 " Senders MUST NOT coalesce QUIC packets with different connection 1921 " IDs into a single UDP datagram. 1922 */ 1923 if (packet_out_total_sz(packet_out) + to_coal->prev_sz_sum 1924 > SC_PACK_SIZE(ctl) 1925 || !lsquic_packet_out_equal_dcids(to_coal->prev_packet, packet_out)) 1926 return NULL; 1927 LSQ_DEBUG("packet %"PRIu64" (%zu bytes) will be tacked on to " 1928 "previous packet(s) (%zu bytes) (coalescing)", 1929 packet_out->po_packno, packet_out_total_sz(packet_out), 1930 to_coal->prev_sz_sum); 1931 size = to_coal->prev_sz_sum; 1932 } 1933 else 1934 size = 0; 1935 send_ctl_sched_remove(ctl, packet_out); 1936 1937 if (dec_limit) 1938 { 1939 --ctl->sc_next_limit; 1940 packet_out->po_lflags |= POL_LIMITED; 1941 } 1942 else 1943 packet_out->po_lflags &= ~POL_LIMITED; 1944 1945 if (UNLIKELY(packet_out->po_header_type == HETY_INITIAL) 1946 && !(ctl->sc_conn_pub->lconn->cn_flags & LSCONN_SERVER) 1947 && size < 1200) 1948 { 1949 send_ctl_maybe_zero_pad(ctl, packet_out, 1200 - size); 1950 } 1951 1952 if (ctl->sc_flags & SC_QL_BITS) 1953 { 1954 packet_out->po_lflags |= POL_LOG_QL_BITS; 1955 if (ctl->sc_loss_count) 1956 { 1957 --ctl->sc_loss_count; 1958 packet_out->po_lflags |= POL_LOSS_BIT; 1959 } 1960 else 1961 packet_out->po_lflags &= ~POL_LOSS_BIT; 1962 if (packet_out->po_header_type == HETY_NOT_SET) 1963 { 1964 if (ctl->sc_gap + 1 == packet_out->po_packno) 1965 ++ctl->sc_square_count; 1966 if (ctl->sc_square_count++ & 64) 1967 packet_out->po_lflags |= POL_SQUARE_BIT; 1968 else 1969 packet_out->po_lflags &= ~POL_SQUARE_BIT; 1970 } 1971 } 1972 1973 return packet_out; 1974} 1975 1976 1977void 1978lsquic_send_ctl_delayed_one (lsquic_send_ctl_t *ctl, 1979 lsquic_packet_out_t *packet_out) 1980{ 1981 send_ctl_sched_prepend(ctl, packet_out); 1982 if (packet_out->po_lflags & POL_LIMITED) 1983 ++ctl->sc_next_limit; 1984 LSQ_DEBUG("packet %"PRIu64" has been delayed", packet_out->po_packno); 1985#if LSQUIC_SEND_STATS 1986 ++ctl->sc_stats.n_delayed; 1987#endif 1988 if (packet_out->po_lflags & POL_LOSS_BIT) 1989 ++ctl->sc_loss_count; 1990 if ((ctl->sc_flags & SC_QL_BITS) 1991 && packet_out->po_header_type == HETY_NOT_SET) 1992 ctl->sc_square_count -= 1 + (ctl->sc_gap + 1 == packet_out->po_packno); 1993} 1994 1995 1996int 1997lsquic_send_ctl_have_outgoing_stream_frames (const lsquic_send_ctl_t *ctl) 1998{ 1999 const lsquic_packet_out_t *packet_out; 2000 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2001 if (packet_out->po_frame_types & 2002 ((1 << QUIC_FRAME_STREAM) | (1 << QUIC_FRAME_RST_STREAM))) 2003 return 1; 2004 return 0; 2005} 2006 2007 2008int 2009lsquic_send_ctl_have_outgoing_retx_frames (const lsquic_send_ctl_t *ctl) 2010{ 2011 const lsquic_packet_out_t *packet_out; 2012 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2013 if (packet_out->po_frame_types & ctl->sc_retx_frames) 2014 return 1; 2015 return 0; 2016} 2017 2018 2019static int 2020send_ctl_set_packet_out_token (const struct lsquic_send_ctl *ctl, 2021 struct lsquic_packet_out *packet_out) 2022{ 2023 unsigned char *token; 2024 2025 token = malloc(ctl->sc_token_sz); 2026 if (!token) 2027 { 2028 LSQ_WARN("malloc failed: cannot set initial token"); 2029 return -1; 2030 } 2031 2032 memcpy(token, ctl->sc_token, ctl->sc_token_sz); 2033 packet_out->po_token = token; 2034 packet_out->po_token_len = ctl->sc_token_sz; 2035 packet_out->po_flags |= PO_NONCE; 2036 LSQ_DEBUG("set initial token on packet"); 2037 return 0; 2038} 2039 2040 2041static lsquic_packet_out_t * 2042send_ctl_allocate_packet (struct lsquic_send_ctl *ctl, enum packno_bits bits, 2043 unsigned need_at_least, enum packnum_space pns, 2044 const struct network_path *path) 2045{ 2046 static const enum header_type pns2hety[] = 2047 { 2048 [PNS_INIT] = HETY_INITIAL, 2049 [PNS_HSK] = HETY_HANDSHAKE, 2050 [PNS_APP] = HETY_NOT_SET, 2051 }; 2052 lsquic_packet_out_t *packet_out; 2053 2054 packet_out = lsquic_packet_out_new(&ctl->sc_enpub->enp_mm, 2055 ctl->sc_conn_pub->packet_out_malo, 2056 !(ctl->sc_flags & SC_TCID0), ctl->sc_conn_pub->lconn, bits, 2057 ctl->sc_ver_neg->vn_tag, NULL, path, pns2hety[pns]); 2058 if (!packet_out) 2059 return NULL; 2060 2061 if (need_at_least && lsquic_packet_out_avail(packet_out) < need_at_least) 2062 { /* This should never happen, this is why this check is performed at 2063 * this level and not lower, before the packet is actually allocated. 2064 */ 2065 LSQ_ERROR("wanted to allocate packet with at least %u bytes of " 2066 "payload, but only got %u bytes (mtu: %u bytes)", need_at_least, 2067 lsquic_packet_out_avail(packet_out), SC_PACK_SIZE(ctl)); 2068 send_ctl_destroy_packet(ctl, packet_out); 2069 return NULL; 2070 } 2071 2072 if (UNLIKELY(pns != PNS_APP)) 2073 { 2074 if (pns == PNS_INIT) 2075 { 2076 packet_out->po_header_type = HETY_INITIAL; 2077 if (ctl->sc_token) 2078 { 2079 (void) send_ctl_set_packet_out_token(ctl, packet_out); 2080 if (packet_out->po_n_alloc > packet_out->po_token_len) 2081 packet_out->po_n_alloc -= packet_out->po_token_len; 2082 else 2083 { 2084 /* XXX fail earlier: when retry token is parsed out */ 2085 LSQ_INFO("token is too long: cannot allocate packet"); 2086 return NULL; 2087 } 2088 } 2089 } 2090 else 2091 packet_out->po_header_type = HETY_HANDSHAKE; 2092 } 2093 2094 lsquic_packet_out_set_pns(packet_out, pns); 2095 packet_out->po_lflags |= ctl->sc_ecn << POECN_SHIFT; 2096 packet_out->po_loss_chain = packet_out; 2097 return packet_out; 2098} 2099 2100 2101lsquic_packet_out_t * 2102lsquic_send_ctl_new_packet_out (lsquic_send_ctl_t *ctl, unsigned need_at_least, 2103 enum packnum_space pns, const struct network_path *path) 2104{ 2105 lsquic_packet_out_t *packet_out; 2106 enum packno_bits bits; 2107 2108 bits = lsquic_send_ctl_packno_bits(ctl, pns); 2109 packet_out = send_ctl_allocate_packet(ctl, bits, need_at_least, pns, path); 2110 if (!packet_out) 2111 return NULL; 2112 2113 packet_out->po_packno = send_ctl_next_packno(ctl); 2114 LSQ_DEBUG("created packet %"PRIu64, packet_out->po_packno); 2115 EV_LOG_PACKET_CREATED(LSQUIC_LOG_CONN_ID, packet_out); 2116 return packet_out; 2117} 2118 2119 2120struct lsquic_packet_out * 2121lsquic_send_ctl_last_scheduled (struct lsquic_send_ctl *ctl, 2122 enum packnum_space pns, const struct network_path *path, 2123 int regen_match) 2124{ 2125 struct lsquic_packet_out *packet_out; 2126 2127 if (0 == regen_match) 2128 { 2129 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_scheduled_packets, 2130 lsquic_packets_tailq, po_next) 2131 if (pns == lsquic_packet_out_pns(packet_out) 2132 && path == packet_out->po_path) 2133 return packet_out; 2134 } 2135 else 2136 { 2137 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_scheduled_packets, 2138 lsquic_packets_tailq, po_next) 2139 if (pns == lsquic_packet_out_pns(packet_out) 2140 && packet_out->po_regen_sz == packet_out->po_data_sz 2141 && path == packet_out->po_path) 2142 return packet_out; 2143 } 2144 2145 return NULL; 2146} 2147 2148 2149/* Do not use for STREAM frames 2150 */ 2151lsquic_packet_out_t * 2152lsquic_send_ctl_get_writeable_packet (lsquic_send_ctl_t *ctl, 2153 enum packnum_space pns, unsigned need_at_least, 2154 const struct network_path *path, int regen_match, int *is_err) 2155{ 2156 lsquic_packet_out_t *packet_out; 2157 2158 assert(need_at_least > 0); 2159 2160 packet_out = lsquic_send_ctl_last_scheduled(ctl, pns, path, regen_match); 2161 if (packet_out 2162 && !(packet_out->po_flags & (PO_MINI|PO_STREAM_END|PO_RETX)) 2163 && lsquic_packet_out_avail(packet_out) >= need_at_least) 2164 { 2165 return packet_out; 2166 } 2167 2168 if (!lsquic_send_ctl_can_send(ctl)) 2169 { 2170 if (is_err) 2171 *is_err = 0; 2172 return NULL; 2173 } 2174 2175 packet_out = lsquic_send_ctl_new_packet_out(ctl, need_at_least, pns, path); 2176 if (packet_out) 2177 { 2178 lsquic_packet_out_set_pns(packet_out, pns); 2179 lsquic_send_ctl_scheduled_one(ctl, packet_out); 2180 } 2181 else if (is_err) 2182 *is_err = 1; 2183 return packet_out; 2184} 2185 2186 2187struct lsquic_packet_out * 2188lsquic_send_ctl_get_packet_for_crypto (struct lsquic_send_ctl *ctl, 2189 unsigned need_at_least, enum packnum_space pns, 2190 const struct network_path *path) 2191{ 2192 struct lsquic_packet_out *packet_out; 2193 2194 assert(lsquic_send_ctl_schedule_stream_packets_immediately(ctl)); 2195 assert(need_at_least > 0); 2196 2197 packet_out = lsquic_send_ctl_last_scheduled(ctl, pns, path, 0); 2198 if (packet_out 2199 && !(packet_out->po_flags & (PO_STREAM_END|PO_RETX)) 2200 && lsquic_packet_out_avail(packet_out) >= need_at_least) 2201 { 2202 return packet_out; 2203 } 2204 2205 if (!lsquic_send_ctl_can_send(ctl)) 2206 return NULL; 2207 2208 packet_out = lsquic_send_ctl_new_packet_out(ctl, need_at_least, pns, path); 2209 if (!packet_out) 2210 return NULL; 2211 2212 lsquic_send_ctl_scheduled_one(ctl, packet_out); 2213 return packet_out; 2214} 2215 2216 2217static void 2218update_for_resending (lsquic_send_ctl_t *ctl, lsquic_packet_out_t *packet_out) 2219{ 2220 2221 lsquic_packno_t oldno, packno; 2222 2223 /* When the packet is resent, it uses the same number of bytes to encode 2224 * the packet number as the original packet. This follows the reference 2225 * implementation. 2226 */ 2227 oldno = packet_out->po_packno; 2228 packno = send_ctl_next_packno(ctl); 2229 2230 packet_out->po_flags &= ~PO_SENT_SZ; 2231 packet_out->po_frame_types &= ~BQUIC_FRAME_REGEN_MASK; 2232 assert(packet_out->po_frame_types); 2233 packet_out->po_packno = packno; 2234 lsquic_packet_out_set_ecn(packet_out, ctl->sc_ecn); 2235 2236 if (ctl->sc_ver_neg->vn_tag) 2237 { 2238 assert(packet_out->po_flags & PO_VERSION); /* It can only disappear */ 2239 packet_out->po_ver_tag = *ctl->sc_ver_neg->vn_tag; 2240 } 2241 2242 assert(packet_out->po_regen_sz < packet_out->po_data_sz); 2243 if (packet_out->po_regen_sz) 2244 { 2245 if (packet_out->po_flags & PO_SCHED) 2246 ctl->sc_bytes_scheduled -= packet_out->po_regen_sz; 2247 lsquic_packet_out_chop_regen(packet_out); 2248 } 2249 LSQ_DEBUG("Packet %"PRIu64" repackaged for resending as packet %"PRIu64, 2250 oldno, packno); 2251 EV_LOG_CONN_EVENT(LSQUIC_LOG_CONN_ID, "packet %"PRIu64" repackaged for " 2252 "resending as packet %"PRIu64, oldno, packno); 2253} 2254 2255 2256unsigned 2257lsquic_send_ctl_reschedule_packets (lsquic_send_ctl_t *ctl) 2258{ 2259 lsquic_packet_out_t *packet_out; 2260 unsigned n = 0; 2261 2262 while ((packet_out = send_ctl_next_lost(ctl))) 2263 { 2264 assert(packet_out->po_regen_sz < packet_out->po_data_sz); 2265 ++n; 2266#if LSQUIC_CONN_STATS 2267 ++ctl->sc_conn_pub->conn_stats->out.retx_packets; 2268#endif 2269 update_for_resending(ctl, packet_out); 2270 lsquic_send_ctl_scheduled_one(ctl, packet_out); 2271 } 2272 2273 if (n) 2274 LSQ_DEBUG("rescheduled %u packets", n); 2275 2276 return n; 2277} 2278 2279 2280void 2281lsquic_send_ctl_set_tcid0 (lsquic_send_ctl_t *ctl, int tcid0) 2282{ 2283 if (tcid0) 2284 { 2285 LSQ_INFO("set TCID flag"); 2286 ctl->sc_flags |= SC_TCID0; 2287 } 2288 else 2289 { 2290 LSQ_INFO("unset TCID flag"); 2291 ctl->sc_flags &= ~SC_TCID0; 2292 } 2293} 2294 2295 2296/* The controller elides this STREAM frames of stream `stream_id' from 2297 * scheduled and buffered packets. If a packet becomes empty as a result, 2298 * it is dropped. 2299 * 2300 * Packets on other queues do not need to be processed: unacked packets 2301 * have already been sent, and lost packets' reset stream frames will be 2302 * elided in due time. 2303 */ 2304void 2305lsquic_send_ctl_elide_stream_frames (lsquic_send_ctl_t *ctl, 2306 lsquic_stream_id_t stream_id) 2307{ 2308 struct lsquic_packet_out *packet_out, *next; 2309 unsigned n, adj; 2310 int dropped; 2311 2312 dropped = 0; 2313#ifdef WIN32 2314 next = NULL; 2315#endif 2316 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2317 packet_out = next) 2318 { 2319 next = TAILQ_NEXT(packet_out, po_next); 2320 2321 if ((packet_out->po_frame_types & (1 << QUIC_FRAME_STREAM)) 2322 && 0 == (packet_out->po_flags & PO_MINI)) 2323 { 2324 adj = lsquic_packet_out_elide_reset_stream_frames(packet_out, 2325 stream_id); 2326 ctl->sc_bytes_scheduled -= adj; 2327 if (0 == packet_out->po_frame_types) 2328 { 2329 LSQ_DEBUG("cancel packet %"PRIu64" after eliding frames for " 2330 "stream %"PRIu64, packet_out->po_packno, stream_id); 2331 send_ctl_sched_remove(ctl, packet_out); 2332 send_ctl_destroy_chain(ctl, packet_out, NULL); 2333 send_ctl_destroy_packet(ctl, packet_out); 2334 ++dropped; 2335 } 2336 } 2337 } 2338 2339 if (dropped) 2340 lsquic_send_ctl_reset_packnos(ctl); 2341 2342 for (n = 0; n < sizeof(ctl->sc_buffered_packets) / 2343 sizeof(ctl->sc_buffered_packets[0]); ++n) 2344 { 2345 for (packet_out = TAILQ_FIRST(&ctl->sc_buffered_packets[n].bpq_packets); 2346 packet_out; packet_out = next) 2347 { 2348 next = TAILQ_NEXT(packet_out, po_next); 2349 if (packet_out->po_frame_types & (1 << QUIC_FRAME_STREAM)) 2350 { 2351 lsquic_packet_out_elide_reset_stream_frames(packet_out, stream_id); 2352 if (0 == packet_out->po_frame_types) 2353 { 2354 LSQ_DEBUG("cancel buffered packet in queue #%u after eliding " 2355 "frames for stream %"PRIu64, n, stream_id); 2356 TAILQ_REMOVE(&ctl->sc_buffered_packets[n].bpq_packets, 2357 packet_out, po_next); 2358 --ctl->sc_buffered_packets[n].bpq_count; 2359 send_ctl_destroy_packet(ctl, packet_out); 2360 LSQ_DEBUG("Elide packet from buffered queue #%u; count: %u", 2361 n, ctl->sc_buffered_packets[n].bpq_count); 2362 } 2363 } 2364 } 2365 } 2366} 2367 2368 2369/* Count how many packets will remain after the squeezing performed by 2370 * lsquic_send_ctl_squeeze_sched(). This is the number of delayed data 2371 * packets. 2372 */ 2373#ifndef NDEBUG 2374#if __GNUC__ 2375__attribute__((weak)) 2376#endif 2377#endif 2378int 2379lsquic_send_ctl_have_delayed_packets (const lsquic_send_ctl_t *ctl) 2380{ 2381 const struct lsquic_packet_out *packet_out; 2382 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2383 if (packet_out->po_regen_sz < packet_out->po_data_sz) 2384 return 1; 2385 return 0; 2386} 2387 2388 2389#ifndef NDEBUG 2390static void 2391send_ctl_log_packet_q (const lsquic_send_ctl_t *ctl, const char *prefix, 2392 const struct lsquic_packets_tailq *tailq) 2393{ 2394 const lsquic_packet_out_t *packet_out; 2395 unsigned n_packets; 2396 char *buf; 2397 size_t bufsz; 2398 int off; 2399 2400 n_packets = 0; 2401 TAILQ_FOREACH(packet_out, tailq, po_next) 2402 ++n_packets; 2403 2404 if (n_packets == 0) 2405 { 2406 LSQ_DEBUG("%s: [<empty set>]", prefix); 2407 return; 2408 } 2409 2410 bufsz = n_packets * sizeof("18446744073709551615" /* UINT64_MAX */); 2411 buf = malloc(bufsz); 2412 if (!buf) 2413 { 2414 LSQ_ERROR("%s: malloc: %s", __func__, strerror(errno)); 2415 return; 2416 } 2417 2418 off = 0; 2419 TAILQ_FOREACH(packet_out, tailq, po_next) 2420 { 2421 if (off) 2422 buf[off++] = ' '; 2423 off += sprintf(buf + off, "%"PRIu64, packet_out->po_packno); 2424 } 2425 2426 LSQ_DEBUG("%s: [%s]", prefix, buf); 2427 free(buf); 2428} 2429 2430 2431#define LOG_PACKET_Q(prefix, queue) do { \ 2432 if (LSQ_LOG_ENABLED(LSQ_LOG_DEBUG)) \ 2433 send_ctl_log_packet_q(ctl, queue, prefix); \ 2434} while (0) 2435#else 2436#define LOG_PACKET_Q(p, q) 2437#endif 2438 2439 2440int 2441lsquic_send_ctl_squeeze_sched (lsquic_send_ctl_t *ctl) 2442{ 2443 struct lsquic_packet_out *packet_out, *next; 2444 int dropped; 2445#ifndef NDEBUG 2446 int pre_squeeze_logged = 0; 2447#endif 2448 2449 dropped = 0; 2450 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2451 packet_out = next) 2452 { 2453 next = TAILQ_NEXT(packet_out, po_next); 2454 if (packet_out->po_regen_sz < packet_out->po_data_sz 2455 || packet_out->po_frame_types == QUIC_FTBIT_PATH_CHALLENGE) 2456 { 2457 if (packet_out->po_flags & PO_ENCRYPTED) 2458 send_ctl_return_enc_data(ctl, packet_out); 2459 } 2460 else 2461 { 2462#ifndef NDEBUG 2463 /* Log the whole list before we squeeze for the first time */ 2464 if (!pre_squeeze_logged++) 2465 LOG_PACKET_Q(&ctl->sc_scheduled_packets, 2466 "scheduled packets before squeezing"); 2467#endif 2468 send_ctl_sched_remove(ctl, packet_out); 2469 LSQ_DEBUG("Dropping packet %"PRIu64" from scheduled queue", 2470 packet_out->po_packno); 2471 send_ctl_destroy_chain(ctl, packet_out, NULL); 2472 send_ctl_destroy_packet(ctl, packet_out); 2473 ++dropped; 2474 } 2475 } 2476 2477 if (dropped) 2478 lsquic_send_ctl_reset_packnos(ctl); 2479 2480#ifndef NDEBUG 2481 if (pre_squeeze_logged) 2482 LOG_PACKET_Q(&ctl->sc_scheduled_packets, 2483 "scheduled packets after squeezing"); 2484 else if (ctl->sc_n_scheduled > 0) 2485 LOG_PACKET_Q(&ctl->sc_scheduled_packets, "delayed packets"); 2486#endif 2487 2488 return ctl->sc_n_scheduled > 0; 2489} 2490 2491 2492void 2493lsquic_send_ctl_reset_packnos (lsquic_send_ctl_t *ctl) 2494{ 2495 struct lsquic_packet_out *packet_out; 2496 2497 ctl->sc_cur_packno = lsquic_senhist_largest(&ctl->sc_senhist); 2498 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2499 packet_out->po_flags |= PO_REPACKNO; 2500} 2501 2502 2503void 2504lsquic_send_ctl_ack_to_front (struct lsquic_send_ctl *ctl, unsigned n_acks) 2505{ 2506 struct lsquic_packet_out *ack_packet; 2507 2508 assert(n_acks > 0); 2509 assert(ctl->sc_n_scheduled > n_acks); /* Otherwise, why is this called? */ 2510 for ( ; n_acks > 0; --n_acks) 2511 { 2512 ack_packet = TAILQ_LAST(&ctl->sc_scheduled_packets, lsquic_packets_tailq); 2513 assert(ack_packet->po_frame_types & (1 << QUIC_FRAME_ACK)); 2514 TAILQ_REMOVE(&ctl->sc_scheduled_packets, ack_packet, po_next); 2515 TAILQ_INSERT_HEAD(&ctl->sc_scheduled_packets, ack_packet, po_next); 2516 } 2517} 2518 2519 2520void 2521lsquic_send_ctl_drop_scheduled (lsquic_send_ctl_t *ctl) 2522{ 2523 struct lsquic_packet_out *packet_out, *next; 2524 unsigned n; 2525 2526 n = 0; 2527 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2528 packet_out = next) 2529 { 2530 next = TAILQ_NEXT(packet_out, po_next); 2531 if (0 == (packet_out->po_flags & PO_HELLO)) 2532 { 2533 send_ctl_sched_remove(ctl, packet_out); 2534 send_ctl_destroy_chain(ctl, packet_out, NULL); 2535 send_ctl_destroy_packet(ctl, packet_out); 2536 ++n; 2537 } 2538 } 2539 2540 ctl->sc_senhist.sh_flags |= SH_GAP_OK; 2541 2542 LSQ_DEBUG("dropped %u scheduled packet%s (%u left)", n, n != 1 ? "s" : "", 2543 ctl->sc_n_scheduled); 2544} 2545 2546 2547#ifdef NDEBUG 2548static 2549#elif __GNUC__ 2550__attribute__((weak)) 2551#endif 2552enum buf_packet_type 2553lsquic_send_ctl_determine_bpt (lsquic_send_ctl_t *ctl, 2554 const lsquic_stream_t *stream) 2555{ 2556 const lsquic_stream_t *other_stream; 2557 struct lsquic_hash_elem *el; 2558 struct lsquic_hash *all_streams; 2559 2560 all_streams = ctl->sc_conn_pub->all_streams; 2561 for (el = lsquic_hash_first(all_streams); el; 2562 el = lsquic_hash_next(all_streams)) 2563 { 2564 other_stream = lsquic_hashelem_getdata(el); 2565 if (other_stream != stream 2566 && (!(other_stream->stream_flags & STREAM_U_WRITE_DONE)) 2567 && !lsquic_stream_is_critical(other_stream) 2568 && other_stream->sm_priority < stream->sm_priority) 2569 return BPT_OTHER_PRIO; 2570 } 2571 return BPT_HIGHEST_PRIO; 2572} 2573 2574 2575static enum buf_packet_type 2576send_ctl_lookup_bpt (lsquic_send_ctl_t *ctl, 2577 const struct lsquic_stream *stream) 2578{ 2579 if (ctl->sc_cached_bpt.stream_id != stream->id) 2580 { 2581 ctl->sc_cached_bpt.stream_id = stream->id; 2582 ctl->sc_cached_bpt.packet_type = 2583 lsquic_send_ctl_determine_bpt(ctl, stream); 2584 } 2585 return ctl->sc_cached_bpt.packet_type; 2586} 2587 2588 2589static unsigned 2590send_ctl_max_bpq_count (const lsquic_send_ctl_t *ctl, 2591 enum buf_packet_type packet_type) 2592{ 2593 unsigned long cwnd; 2594 unsigned count; 2595 2596 switch (packet_type) 2597 { 2598 case BPT_OTHER_PRIO: 2599 return MAX_BPQ_COUNT; 2600 case BPT_HIGHEST_PRIO: 2601 default: /* clang does not complain about absence of `default'... */ 2602 count = ctl->sc_n_scheduled + ctl->sc_n_in_flight_retx; 2603 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 2604 if (count < cwnd / SC_PACK_SIZE(ctl)) 2605 { 2606 count = cwnd / SC_PACK_SIZE(ctl) - count; 2607 if (count > MAX_BPQ_COUNT) 2608 return count; 2609 } 2610 return MAX_BPQ_COUNT; 2611 } 2612} 2613 2614 2615/* If error is returned, `src' is not modified */ 2616static int 2617send_ctl_move_ack (struct lsquic_send_ctl *ctl, struct lsquic_packet_out *dst, 2618 struct lsquic_packet_out *src) 2619{ 2620 struct packet_out_frec_iter pofi; 2621 const struct frame_rec *frec; 2622 assert(dst->po_data_sz == 0); 2623 2624 /* This checks that we only ever expect to move an ACK frame from one 2625 * buffered packet to another. We don't generate any other regen frame 2626 * types in buffered packets. 2627 */ 2628 assert(!(BQUIC_FRAME_REGEN_MASK & (1 << src->po_frame_types) 2629 & ~QUIC_FTBIT_ACK)); 2630 2631 if (lsquic_packet_out_avail(dst) >= src->po_regen_sz 2632 && (frec = lsquic_pofi_first(&pofi, src), frec != NULL) 2633 && frec->fe_frame_type == QUIC_FRAME_ACK) 2634 { 2635 memcpy(dst->po_data, src->po_data, src->po_regen_sz); 2636 if (0 != lsquic_packet_out_add_frame(dst, &ctl->sc_enpub->enp_mm, 2637 frec->fe_frame_type, QUIC_FRAME_ACK, dst->po_data_sz, 2638 src->po_regen_sz)) 2639 return -1; 2640 dst->po_data_sz = src->po_regen_sz; 2641 dst->po_regen_sz = src->po_regen_sz; 2642 dst->po_frame_types |= (BQUIC_FRAME_REGEN_MASK & src->po_frame_types); 2643 src->po_frame_types &= ~BQUIC_FRAME_REGEN_MASK; 2644 lsquic_packet_out_chop_regen(src); 2645 } 2646 2647 return 0; 2648} 2649 2650 2651static lsquic_packet_out_t * 2652send_ctl_get_buffered_packet (lsquic_send_ctl_t *ctl, 2653 enum buf_packet_type packet_type, unsigned need_at_least, 2654 const struct network_path *path, const struct lsquic_stream *stream) 2655{ 2656 struct buf_packet_q *const packet_q = 2657 &ctl->sc_buffered_packets[packet_type]; 2658 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 2659 lsquic_packet_out_t *packet_out; 2660 enum packno_bits bits; 2661 enum { AA_STEAL, AA_GENERATE, AA_NONE, } ack_action; 2662 2663 packet_out = TAILQ_LAST(&packet_q->bpq_packets, lsquic_packets_tailq); 2664 if (packet_out 2665 && !(packet_out->po_flags & PO_STREAM_END) 2666 && lsquic_packet_out_avail(packet_out) >= need_at_least) 2667 { 2668 return packet_out; 2669 } 2670 2671 if (packet_q->bpq_count >= send_ctl_max_bpq_count(ctl, packet_type)) 2672 return NULL; 2673 2674 if (packet_q->bpq_count == 0) 2675 { 2676 /* If ACK was written to the low-priority queue first, steal it */ 2677 if (packet_q == &ctl->sc_buffered_packets[BPT_HIGHEST_PRIO] 2678 && !TAILQ_EMPTY(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets) 2679 && (TAILQ_FIRST(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets) 2680 ->po_frame_types & QUIC_FTBIT_ACK)) 2681 { 2682 LSQ_DEBUG("steal ACK frame from low-priority buffered queue"); 2683 ack_action = AA_STEAL; 2684 bits = ctl->sc_max_packno_bits; 2685 } 2686 /* If ACK can be generated, write it to the first buffered packet. */ 2687 else if (lconn->cn_if->ci_can_write_ack(lconn)) 2688 { 2689 LSQ_DEBUG("generate ACK frame for first buffered packet in " 2690 "queue #%u", packet_type); 2691 ack_action = AA_GENERATE; 2692 /* Packet length is set to the largest possible size to guarantee 2693 * that buffered packet with the ACK will not need to be split. 2694 */ 2695 bits = ctl->sc_max_packno_bits; 2696 } 2697 else 2698 goto no_ack_action; 2699 } 2700 else 2701 { 2702 no_ack_action: 2703 ack_action = AA_NONE; 2704 bits = lsquic_send_ctl_guess_packno_bits(ctl); 2705 } 2706 2707 packet_out = send_ctl_allocate_packet(ctl, bits, need_at_least, PNS_APP, 2708 path); 2709 if (!packet_out) 2710 return NULL; 2711 2712 switch (ack_action) 2713 { 2714 case AA_STEAL: 2715 if (0 != send_ctl_move_ack(ctl, packet_out, 2716 TAILQ_FIRST(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets))) 2717 { 2718 LSQ_INFO("cannot move ack"); 2719 lsquic_packet_out_destroy(packet_out, ctl->sc_enpub, 2720 packet_out->po_path->np_peer_ctx); 2721 return NULL; 2722 } 2723 break; 2724 case AA_GENERATE: 2725 lconn->cn_if->ci_write_ack(lconn, packet_out); 2726 break; 2727 case AA_NONE: 2728 break; 2729 } 2730 2731 TAILQ_INSERT_TAIL(&packet_q->bpq_packets, packet_out, po_next); 2732 ++packet_q->bpq_count; 2733 LSQ_DEBUG("Add new packet to buffered queue #%u; count: %u", 2734 packet_type, packet_q->bpq_count); 2735 return packet_out; 2736} 2737 2738 2739static void 2740send_ctl_maybe_flush_decoder (struct lsquic_send_ctl *ctl, 2741 const struct lsquic_stream *caller) 2742{ 2743 struct lsquic_stream *decoder; 2744 2745 if ((ctl->sc_flags & SC_IETF) && ctl->sc_conn_pub->u.ietf.qdh) 2746 { 2747 decoder = ctl->sc_conn_pub->u.ietf.qdh->qdh_dec_sm_out; 2748 if (decoder && decoder != caller 2749 && lsquic_stream_has_data_to_flush(decoder)) 2750 { 2751 LSQ_DEBUG("flushing decoder stream"); 2752 lsquic_stream_flush(decoder); 2753 } 2754 } 2755} 2756 2757 2758lsquic_packet_out_t * 2759lsquic_send_ctl_get_packet_for_stream (lsquic_send_ctl_t *ctl, 2760 unsigned need_at_least, const struct network_path *path, 2761 const struct lsquic_stream *stream) 2762{ 2763 enum buf_packet_type packet_type; 2764 2765 if (lsquic_send_ctl_schedule_stream_packets_immediately(ctl)) 2766 return lsquic_send_ctl_get_writeable_packet(ctl, PNS_APP, 2767 need_at_least, path, 0, NULL); 2768 else 2769 { 2770 if (!lsquic_send_ctl_has_buffered(ctl)) 2771 send_ctl_maybe_flush_decoder(ctl, stream); 2772 packet_type = send_ctl_lookup_bpt(ctl, stream); 2773 return send_ctl_get_buffered_packet(ctl, packet_type, need_at_least, 2774 path, stream); 2775 } 2776} 2777 2778 2779#ifdef NDEBUG 2780static 2781#elif __GNUC__ 2782__attribute__((weak)) 2783#endif 2784enum packno_bits 2785lsquic_send_ctl_calc_packno_bits (lsquic_send_ctl_t *ctl) 2786{ 2787 lsquic_packno_t smallest_unacked; 2788 enum packno_bits bits; 2789 unsigned n_in_flight; 2790 unsigned long cwnd; 2791 const struct parse_funcs *pf; 2792 2793 pf = ctl->sc_conn_pub->lconn->cn_pf; 2794 2795 smallest_unacked = lsquic_send_ctl_smallest_unacked(ctl); 2796 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 2797 n_in_flight = cwnd / SC_PACK_SIZE(ctl); 2798 bits = pf->pf_calc_packno_bits(ctl->sc_cur_packno + 1, smallest_unacked, 2799 n_in_flight); 2800 if (bits <= ctl->sc_max_packno_bits) 2801 return bits; 2802 else 2803 return ctl->sc_max_packno_bits; 2804} 2805 2806 2807enum packno_bits 2808lsquic_send_ctl_packno_bits (struct lsquic_send_ctl *ctl, 2809 enum packnum_space pns) 2810{ 2811 if ((ctl->sc_flags & (SC_ACK_RECV_INIT << pns)) 2812 && lsquic_send_ctl_schedule_stream_packets_immediately(ctl)) 2813 return lsquic_send_ctl_calc_packno_bits(ctl); 2814 else if (ctl->sc_flags & (SC_ACK_RECV_INIT << pns)) 2815 return lsquic_send_ctl_guess_packno_bits(ctl); 2816 else 2817/* From [draft-ietf-quic-transport-31] Section 17.1: 2818 * 2819 " Prior to receiving an acknowledgement for a packet number space, the 2820 " full packet number MUST be included; it is not to be truncated as 2821 " described below. 2822 */ 2823 return vint_val2bits(ctl->sc_cur_packno + 1); 2824} 2825 2826 2827struct resize_one_packet_ctx 2828{ 2829 struct lsquic_send_ctl *const ctl; 2830 struct lsquic_packet_out *const victim; 2831 const struct network_path *const path; 2832 const enum packnum_space pns; 2833 int discarded, fetched; 2834}; 2835 2836 2837static struct lsquic_packet_out * 2838resize_one_next_packet (void *ctx) 2839{ 2840 struct resize_one_packet_ctx *const one_ctx = ctx; 2841 2842 if (one_ctx->fetched) 2843 return NULL; 2844 2845 ++one_ctx->fetched; 2846 return one_ctx->victim; 2847} 2848 2849 2850static void 2851resize_one_discard_packet (void *ctx, struct lsquic_packet_out *packet_out) 2852{ 2853 struct resize_one_packet_ctx *const one_ctx = ctx; 2854 2855 /* Delay discarding the packet: we need it for TAILQ_INSERT_BEFORE */ 2856 ++one_ctx->discarded; 2857} 2858 2859 2860static struct lsquic_packet_out * 2861resize_one_new_packet (void *ctx) 2862{ 2863 struct resize_one_packet_ctx *const one_ctx = ctx; 2864 struct lsquic_send_ctl *const ctl = one_ctx->ctl; 2865 struct lsquic_packet_out *packet_out; 2866 enum packno_bits bits; 2867 2868 bits = lsquic_send_ctl_calc_packno_bits(ctl); 2869 packet_out = send_ctl_allocate_packet(ctl, bits, 0, one_ctx->pns, 2870 one_ctx->path); 2871 return packet_out; 2872} 2873 2874 2875static const struct packet_resize_if resize_one_funcs = 2876{ 2877 resize_one_next_packet, 2878 resize_one_discard_packet, 2879 resize_one_new_packet, 2880}; 2881 2882 2883static int 2884split_buffered_packet (lsquic_send_ctl_t *ctl, 2885 enum buf_packet_type packet_type, struct lsquic_packet_out *packet_out) 2886{ 2887 struct buf_packet_q *const packet_q = 2888 &ctl->sc_buffered_packets[packet_type]; 2889 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 2890 struct lsquic_packet_out *new; 2891 struct packet_resize_ctx prctx; 2892 struct resize_one_packet_ctx one_ctx = { 2893 ctl, packet_out, packet_out->po_path, 2894 lsquic_packet_out_pns(packet_out), 0, 0, 2895 }; 2896 unsigned count; 2897 2898 assert(TAILQ_FIRST(&packet_q->bpq_packets) == packet_out); 2899 2900 lsquic_packet_resize_init(&prctx, ctl->sc_enpub, lconn, &one_ctx, 2901 &resize_one_funcs); 2902 count = 0; 2903 while (new = lsquic_packet_resize_next(&prctx), new != NULL) 2904 { 2905 ++count; 2906 TAILQ_INSERT_BEFORE(packet_out, new, po_next); 2907 ++packet_q->bpq_count; 2908 LSQ_DEBUG("Add split packet to buffered queue #%u; count: %u", 2909 packet_type, packet_q->bpq_count); 2910 } 2911 if (lsquic_packet_resize_is_error(&prctx)) 2912 { 2913 LSQ_WARN("error resizing buffered packet #%"PRIu64, 2914 packet_out->po_packno); 2915 return -1; 2916 } 2917 if (!(count > 1 && one_ctx.fetched == 1 && one_ctx.discarded == 1)) 2918 { 2919 /* A bit of insurance, this being new code */ 2920 LSQ_WARN("unexpected values resizing buffered packet: count: %u; " 2921 "fetched: %d; discarded: %d", count, one_ctx.fetched, 2922 one_ctx.discarded); 2923 return -1; 2924 } 2925 LSQ_DEBUG("added %u packets to the buffered queue #%u", count, packet_type); 2926 2927 LSQ_DEBUG("drop oversized buffered packet #%"PRIu64, packet_out->po_packno); 2928 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 2929 ++packet_q->bpq_count; 2930 assert(packet_out->po_loss_chain == packet_out); 2931 send_ctl_destroy_packet(ctl, packet_out); 2932 return 0; 2933} 2934 2935 2936int 2937lsquic_send_ctl_schedule_buffered (lsquic_send_ctl_t *ctl, 2938 enum buf_packet_type packet_type) 2939{ 2940 struct buf_packet_q *const packet_q = 2941 &ctl->sc_buffered_packets[packet_type]; 2942 const struct parse_funcs *const pf = ctl->sc_conn_pub->lconn->cn_pf; 2943 lsquic_packet_out_t *packet_out; 2944 unsigned used; 2945 2946 assert(lsquic_send_ctl_schedule_stream_packets_immediately(ctl)); 2947 const enum packno_bits bits = lsquic_send_ctl_calc_packno_bits(ctl); 2948 const unsigned need = pf->pf_packno_bits2len(bits); 2949 2950 while ((packet_out = TAILQ_FIRST(&packet_q->bpq_packets)) && 2951 lsquic_send_ctl_can_send(ctl)) 2952 { 2953 if ((packet_out->po_frame_types & QUIC_FTBIT_ACK) 2954 && packet_out->po_ack2ed < ctl->sc_largest_acked) 2955 { 2956 /* Chrome watches for a decrease in the value of the Largest 2957 * Observed field of the ACK frame and marks it as an error: 2958 * this is why we have to send out ACK in the order they were 2959 * generated. 2960 */ 2961 LSQ_DEBUG("Remove out-of-order ACK from buffered packet"); 2962 lsquic_packet_out_chop_regen(packet_out); 2963 if (packet_out->po_data_sz == 0) 2964 { 2965 LSQ_DEBUG("Dropping now-empty buffered packet"); 2966 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 2967 --packet_q->bpq_count; 2968 send_ctl_destroy_packet(ctl, packet_out); 2969 continue; 2970 } 2971 } 2972 if (bits != lsquic_packet_out_packno_bits(packet_out)) 2973 { 2974 used = pf->pf_packno_bits2len( 2975 lsquic_packet_out_packno_bits(packet_out)); 2976 if (need > used 2977 && need - used > lsquic_packet_out_avail(packet_out)) 2978 { 2979 if (0 == split_buffered_packet(ctl, packet_type, packet_out)) 2980 packet_out = TAILQ_FIRST(&packet_q->bpq_packets); 2981 else 2982 return -1; 2983 } 2984 } 2985 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 2986 --packet_q->bpq_count; 2987 packet_out->po_packno = send_ctl_next_packno(ctl); 2988 LSQ_DEBUG("Remove packet from buffered queue #%u; count: %u. " 2989 "It becomes packet %"PRIu64, packet_type, packet_q->bpq_count, 2990 packet_out->po_packno); 2991 lsquic_send_ctl_scheduled_one(ctl, packet_out); 2992 } 2993 2994 return 0; 2995} 2996 2997 2998int 2999lsquic_send_ctl_turn_on_fin (struct lsquic_send_ctl *ctl, 3000 const struct lsquic_stream *stream) 3001{ 3002 enum buf_packet_type packet_type; 3003 struct buf_packet_q *packet_q; 3004 lsquic_packet_out_t *packet_out; 3005 const struct parse_funcs *pf; 3006 3007 pf = ctl->sc_conn_pub->lconn->cn_pf; 3008 packet_type = send_ctl_lookup_bpt(ctl, stream); 3009 packet_q = &ctl->sc_buffered_packets[packet_type]; 3010 3011 TAILQ_FOREACH_REVERSE(packet_out, &packet_q->bpq_packets, 3012 lsquic_packets_tailq, po_next) 3013 if (0 == lsquic_packet_out_turn_on_fin(packet_out, pf, stream)) 3014 return 0; 3015 3016 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 3017 if (0 == packet_out->po_sent 3018 && 0 == lsquic_packet_out_turn_on_fin(packet_out, pf, stream)) 3019 { 3020 return 0; 3021 } 3022 3023 return -1; 3024} 3025 3026 3027size_t 3028lsquic_send_ctl_mem_used (const struct lsquic_send_ctl *ctl) 3029{ 3030 const lsquic_packet_out_t *packet_out; 3031 unsigned n; 3032 size_t size; 3033 const struct lsquic_packets_tailq queues[] = { 3034 ctl->sc_scheduled_packets, 3035 ctl->sc_unacked_packets[PNS_INIT], 3036 ctl->sc_unacked_packets[PNS_HSK], 3037 ctl->sc_unacked_packets[PNS_APP], 3038 ctl->sc_lost_packets, 3039 ctl->sc_buffered_packets[0].bpq_packets, 3040 ctl->sc_buffered_packets[1].bpq_packets, 3041 }; 3042 3043 size = sizeof(*ctl); 3044 3045 for (n = 0; n < sizeof(queues) / sizeof(queues[0]); ++n) 3046 TAILQ_FOREACH(packet_out, &queues[n], po_next) 3047 size += lsquic_packet_out_mem_used(packet_out); 3048 3049 return size; 3050} 3051 3052 3053void 3054lsquic_send_ctl_verneg_done (struct lsquic_send_ctl *ctl) 3055{ 3056 ctl->sc_max_packno_bits = PACKNO_BITS_3; 3057 LSQ_DEBUG("version negotiation done (%s): max packno bits: %u", 3058 lsquic_ver2str[ ctl->sc_conn_pub->lconn->cn_version ], 3059 ctl->sc_max_packno_bits); 3060} 3061 3062 3063static void 3064strip_trailing_padding (struct lsquic_packet_out *packet_out) 3065{ 3066 struct packet_out_frec_iter pofi; 3067 const struct frame_rec *frec; 3068 unsigned off; 3069 3070 off = 0; 3071 for (frec = lsquic_pofi_first(&pofi, packet_out); frec; 3072 frec = lsquic_pofi_next(&pofi)) 3073 off = frec->fe_off + frec->fe_len; 3074 3075 assert(off); 3076 3077 packet_out->po_data_sz = off; 3078 packet_out->po_frame_types &= ~QUIC_FTBIT_PADDING; 3079} 3080 3081 3082static int 3083split_lost_packet (struct lsquic_send_ctl *ctl, 3084 struct lsquic_packet_out *const packet_out) 3085{ 3086 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3087 struct lsquic_packet_out *new; 3088 struct packet_resize_ctx prctx; 3089 struct resize_one_packet_ctx one_ctx = { 3090 ctl, packet_out, packet_out->po_path, 3091 lsquic_packet_out_pns(packet_out), 0, 0, 3092 }; 3093 unsigned count; 3094 3095 assert(packet_out->po_flags & PO_LOST); 3096 3097 lsquic_packet_resize_init(&prctx, ctl->sc_enpub, lconn, &one_ctx, 3098 &resize_one_funcs); 3099 count = 0; 3100 while (new = lsquic_packet_resize_next(&prctx), new != NULL) 3101 { 3102 ++count; 3103 TAILQ_INSERT_BEFORE(packet_out, new, po_next); 3104 new->po_flags |= PO_LOST; 3105 } 3106 if (lsquic_packet_resize_is_error(&prctx)) 3107 { 3108 LSQ_WARN("error resizing lost packet #%"PRIu64, packet_out->po_packno); 3109 return -1; 3110 } 3111 if (!(count > 1 && one_ctx.fetched == 1 && one_ctx.discarded == 1)) 3112 { 3113 /* A bit of insurance, this being new code */ 3114 LSQ_WARN("unexpected values resizing lost packet: count: %u; " 3115 "fetched: %d; discarded: %d", count, one_ctx.fetched, 3116 one_ctx.discarded); 3117 return -1; 3118 } 3119 LSQ_DEBUG("added %u packets to the lost queue", count); 3120 3121 LSQ_DEBUG("drop oversized lost packet #%"PRIu64, packet_out->po_packno); 3122 TAILQ_REMOVE(&ctl->sc_lost_packets, packet_out, po_next); 3123 packet_out->po_flags &= ~PO_LOST; 3124 send_ctl_destroy_chain(ctl, packet_out, NULL); 3125 send_ctl_destroy_packet(ctl, packet_out); 3126 return 0; 3127} 3128 3129 3130int 3131lsquic_send_ctl_retry (struct lsquic_send_ctl *ctl, 3132 const unsigned char *token, size_t token_sz) 3133{ 3134 struct lsquic_packet_out *packet_out, *next; 3135 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3136 size_t sz; 3137 3138 if (token_sz >= 1ull << (sizeof(packet_out->po_token_len) * 8)) 3139 { 3140 LSQ_WARN("token size %zu is too long", token_sz); 3141 return -1; 3142 } 3143 3144 ++ctl->sc_retry_count; 3145 if (ctl->sc_retry_count > 3) 3146 { 3147 LSQ_INFO("failing connection after %u retries", ctl->sc_retry_count); 3148 return -1; 3149 } 3150 3151 send_ctl_expire(ctl, PNS_INIT, EXFI_ALL); 3152 3153 if (0 != lsquic_send_ctl_set_token(ctl, token, token_sz)) 3154 return -1; 3155 3156 for (packet_out = TAILQ_FIRST(&ctl->sc_lost_packets); packet_out; packet_out = next) 3157 { 3158 next = TAILQ_NEXT(packet_out, po_next); 3159 if (HETY_INITIAL != packet_out->po_header_type) 3160 continue; 3161 3162 if (packet_out->po_nonce) 3163 { 3164 free(packet_out->po_nonce); 3165 packet_out->po_nonce = NULL; 3166 packet_out->po_flags &= ~PO_NONCE; 3167 } 3168 3169 if (0 != send_ctl_set_packet_out_token(ctl, packet_out)) 3170 { 3171 LSQ_INFO("cannot set out token on packet"); 3172 return -1; 3173 } 3174 3175 if (packet_out->po_frame_types & QUIC_FTBIT_PADDING) 3176 strip_trailing_padding(packet_out); 3177 3178 sz = lconn->cn_pf->pf_packout_size(lconn, packet_out); 3179 if (sz > packet_out->po_path->np_pack_size 3180 && 0 != split_lost_packet(ctl, packet_out)) 3181 return -1; 3182 } 3183 3184 return 0; 3185} 3186 3187 3188int 3189lsquic_send_ctl_set_token (struct lsquic_send_ctl *ctl, 3190 const unsigned char *token, size_t token_sz) 3191{ 3192 unsigned char *copy; 3193 3194 if (token_sz > 1 << 3195 (sizeof(((struct lsquic_packet_out *)0)->po_token_len) * 8)) 3196 { 3197 errno = EINVAL; 3198 return -1; 3199 } 3200 3201 copy = malloc(token_sz); 3202 if (!copy) 3203 return -1; 3204 memcpy(copy, token, token_sz); 3205 free(ctl->sc_token); 3206 ctl->sc_token = copy; 3207 ctl->sc_token_sz = token_sz; 3208 LSQ_DEBUG("set token"); 3209 return 0; 3210} 3211 3212 3213void 3214lsquic_send_ctl_empty_pns (struct lsquic_send_ctl *ctl, enum packnum_space pns) 3215{ 3216 lsquic_packet_out_t *packet_out, *next; 3217 unsigned count, packet_sz; 3218 struct lsquic_packets_tailq *const *q; 3219 struct lsquic_packets_tailq *const queues[] = { 3220 &ctl->sc_lost_packets, 3221 &ctl->sc_buffered_packets[0].bpq_packets, 3222 &ctl->sc_buffered_packets[1].bpq_packets, 3223 }; 3224 3225 /* Don't bother with chain destruction, as all chains members are always 3226 * within the same packet number space 3227 */ 3228 3229 count = 0; 3230 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 3231 packet_out = next) 3232 { 3233 next = TAILQ_NEXT(packet_out, po_next); 3234 if (pns == lsquic_packet_out_pns(packet_out)) 3235 { 3236 send_ctl_maybe_renumber_sched_to_right(ctl, packet_out); 3237 send_ctl_sched_remove(ctl, packet_out); 3238 send_ctl_destroy_packet(ctl, packet_out); 3239 ++count; 3240 } 3241 } 3242 3243 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); packet_out; 3244 packet_out = next) 3245 { 3246 next = TAILQ_NEXT(packet_out, po_next); 3247 if (packet_out->po_flags & (PO_LOSS_REC|PO_POISON)) 3248 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, po_next); 3249 else 3250 { 3251 packet_sz = packet_out_sent_sz(packet_out); 3252 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 3253 lsquic_packet_out_ack_streams(packet_out); 3254 } 3255 send_ctl_destroy_packet(ctl, packet_out); 3256 ++count; 3257 } 3258 3259 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 3260 for (packet_out = TAILQ_FIRST(*q); packet_out; packet_out = next) 3261 { 3262 next = TAILQ_NEXT(packet_out, po_next); 3263 if (pns == lsquic_packet_out_pns(packet_out)) 3264 { 3265 TAILQ_REMOVE(*q, packet_out, po_next); 3266 send_ctl_destroy_packet(ctl, packet_out); 3267 ++count; 3268 } 3269 } 3270 3271 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 3272 3273 LSQ_DEBUG("emptied %s, destroyed %u packet%.*s", lsquic_pns2str[pns], 3274 count, count != 1, "s"); 3275} 3276 3277 3278struct resize_many_packet_ctx 3279{ 3280 struct lsquic_send_ctl *ctl; 3281 struct lsquic_packets_tailq input_q; 3282 const struct network_path *path; 3283}; 3284 3285 3286static struct lsquic_packet_out * 3287resize_many_next_packet (void *ctx) 3288{ 3289 struct resize_many_packet_ctx *const many_ctx = ctx; 3290 struct lsquic_packet_out *packet_out; 3291 3292 packet_out = TAILQ_FIRST(&many_ctx->input_q); 3293 if (packet_out) 3294 TAILQ_REMOVE(&many_ctx->input_q, packet_out, po_next); 3295 3296 return packet_out; 3297} 3298 3299 3300static void 3301resize_many_discard_packet (void *ctx, struct lsquic_packet_out *packet_out) 3302{ 3303 struct resize_many_packet_ctx *const many_ctx = ctx; 3304 struct lsquic_send_ctl *const ctl = many_ctx->ctl; 3305 3306 send_ctl_destroy_chain(ctl, packet_out, NULL); 3307 send_ctl_destroy_packet(ctl, packet_out); 3308} 3309 3310 3311static struct lsquic_packet_out * 3312resize_many_new_packet (void *ctx) 3313{ 3314 struct resize_many_packet_ctx *const many_ctx = ctx; 3315 struct lsquic_send_ctl *const ctl = many_ctx->ctl; 3316 struct lsquic_packet_out *packet_out; 3317 enum packno_bits bits; 3318 3319 bits = lsquic_send_ctl_calc_packno_bits(ctl); 3320 packet_out = send_ctl_allocate_packet(ctl, bits, 0, PNS_APP, 3321 many_ctx->path); 3322 return packet_out; 3323} 3324 3325 3326static const struct packet_resize_if resize_many_funcs = 3327{ 3328 resize_many_next_packet, 3329 resize_many_discard_packet, 3330 resize_many_new_packet, 3331}; 3332 3333 3334static void 3335send_ctl_resize_q (struct lsquic_send_ctl *ctl, struct lsquic_packets_tailq *q, 3336 const struct network_path *const path) 3337{ 3338 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3339 struct lsquic_packet_out *next, *packet_out; 3340 struct resize_many_packet_ctx many_ctx; 3341 struct packet_resize_ctx prctx; 3342 const char *q_name; 3343 unsigned count_src = 0, count_dst = 0; 3344 int idx; 3345 3346#ifdef _MSC_VER 3347 idx = 0; 3348#endif 3349 3350 /* Initialize input, removing packets from source queue, filtering by path. 3351 * Note: this may reorder packets from different paths. 3352 */ 3353 many_ctx.ctl = ctl; 3354 many_ctx.path = path; 3355 TAILQ_INIT(&many_ctx.input_q); 3356 if (q == &ctl->sc_scheduled_packets) 3357 { 3358 ctl->sc_cur_packno = lsquic_senhist_largest(&ctl->sc_senhist); 3359 q_name = "scheduled"; 3360 for (packet_out = TAILQ_FIRST(q); packet_out != NULL; packet_out = next) 3361 { 3362 next = TAILQ_NEXT(packet_out, po_next); 3363 if (packet_out->po_path == path 3364 && !(packet_out->po_flags & PO_MTU_PROBE)) 3365 { 3366 send_ctl_sched_remove(ctl, packet_out); 3367 TAILQ_INSERT_TAIL(&many_ctx.input_q, packet_out, po_next); 3368 ++count_src; 3369 } 3370 } 3371 } 3372 else 3373 { 3374 /* This function only deals with scheduled or buffered queues */ 3375 assert(q == &ctl->sc_buffered_packets[0].bpq_packets 3376 || q == &ctl->sc_buffered_packets[1].bpq_packets); 3377 idx = q == &ctl->sc_buffered_packets[1].bpq_packets; 3378 q_name = "buffered"; 3379 for (packet_out = TAILQ_FIRST(q); packet_out != NULL; packet_out = next) 3380 { 3381 next = TAILQ_NEXT(packet_out, po_next); 3382 if (packet_out->po_path == path) 3383 { 3384 TAILQ_REMOVE(q, packet_out, po_next); 3385 --ctl->sc_buffered_packets[idx].bpq_count; 3386 TAILQ_INSERT_TAIL(&many_ctx.input_q, packet_out, po_next); 3387 ++count_src; 3388 } 3389 } 3390 } 3391 lsquic_packet_resize_init(&prctx, ctl->sc_enpub, lconn, &many_ctx, 3392 &resize_many_funcs); 3393 3394 /* Get new packets, appending them to appropriate queue */ 3395 if (q == &ctl->sc_scheduled_packets) 3396 while (packet_out = lsquic_packet_resize_next(&prctx), packet_out != NULL) 3397 { 3398 ++count_dst; 3399 packet_out->po_packno = send_ctl_next_packno(ctl); 3400 send_ctl_sched_append(ctl, packet_out); 3401 LSQ_DEBUG("created packet %"PRIu64, packet_out->po_packno); 3402 EV_LOG_PACKET_CREATED(LSQUIC_LOG_CONN_ID, packet_out); 3403 } 3404 else 3405 while (packet_out = lsquic_packet_resize_next(&prctx), packet_out != NULL) 3406 { 3407 ++count_dst; 3408 TAILQ_INSERT_TAIL(q, packet_out, po_next); 3409 ++ctl->sc_buffered_packets[idx].bpq_count; 3410 } 3411 3412 /* Verify success */ 3413 if (lsquic_packet_resize_is_error(&prctx)) 3414 { 3415 LSQ_WARN("error resizing packets in %s queue", q_name); 3416 goto err; 3417 } 3418 if (count_dst < 1 || !TAILQ_EMPTY(&many_ctx.input_q)) 3419 { 3420 /* A bit of insurance, this being new code */ 3421 LSQ_WARN("unexpected values resizing packets in %s queue: count: %d; " 3422 "empty: %d", q_name, count_dst, TAILQ_EMPTY(&many_ctx.input_q)); 3423 goto err; 3424 } 3425 LSQ_DEBUG("resized %u packets in %s queue, outputting %u packets", 3426 count_src, q_name, count_dst); 3427 return; 3428 3429 err: 3430 lconn->cn_if->ci_internal_error(lconn, "error resizing packets"); 3431 return; 3432} 3433 3434 3435void 3436lsquic_send_ctl_repath (struct lsquic_send_ctl *ctl, 3437 const struct network_path *old, const struct network_path *new, 3438 int keep_path_properties) 3439{ 3440 struct lsquic_packet_out *packet_out; 3441 unsigned count; 3442 struct lsquic_packets_tailq *const *q; 3443 struct lsquic_packets_tailq *const queues[] = { 3444 &ctl->sc_scheduled_packets, 3445 &ctl->sc_unacked_packets[PNS_INIT], 3446 &ctl->sc_unacked_packets[PNS_HSK], 3447 &ctl->sc_unacked_packets[PNS_APP], 3448 &ctl->sc_lost_packets, 3449 &ctl->sc_buffered_packets[0].bpq_packets, 3450 &ctl->sc_buffered_packets[1].bpq_packets, 3451 }; 3452 3453 assert(ctl->sc_flags & SC_IETF); 3454 3455 count = 0; 3456 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 3457 TAILQ_FOREACH(packet_out, *q, po_next) 3458 if (packet_out->po_path == old) 3459 { 3460 ++count; 3461 packet_out->po_path = new; 3462 if (packet_out->po_flags & PO_ENCRYPTED) 3463 send_ctl_return_enc_data(ctl, packet_out); 3464 } 3465 3466 LSQ_DEBUG("repathed %u packet%.*s", count, count != 1, "s"); 3467 3468 if (keep_path_properties) 3469 LSQ_DEBUG("keeping path properties: MTU, RTT, and CC state"); 3470 else 3471 { 3472 lsquic_send_ctl_resize(ctl); 3473 memset(&ctl->sc_conn_pub->rtt_stats, 0, 3474 sizeof(ctl->sc_conn_pub->rtt_stats)); 3475 ctl->sc_ci->cci_reinit(CGP(ctl)); 3476 } 3477} 3478 3479 3480/* Examine packets in scheduled and buffered queues and resize packets if 3481 * they exceed path MTU. 3482 */ 3483void 3484lsquic_send_ctl_resize (struct lsquic_send_ctl *ctl) 3485{ 3486 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3487 struct lsquic_packet_out *packet_out; 3488 struct lsquic_packets_tailq *const *q; 3489 struct lsquic_packets_tailq *const queues[] = { 3490 &ctl->sc_scheduled_packets, 3491 &ctl->sc_buffered_packets[0].bpq_packets, 3492 &ctl->sc_buffered_packets[1].bpq_packets, 3493 }; 3494 size_t size; 3495 int path_ids /* assuming a reasonable number of paths */, q_idxs; 3496 3497 assert(ctl->sc_flags & SC_IETF); 3498 3499 q_idxs = 0; 3500 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 3501 { 3502 path_ids = 0; 3503 redo_q: 3504 TAILQ_FOREACH(packet_out, *q, po_next) 3505 if (0 == (path_ids & (1 << packet_out->po_path->np_path_id)) 3506 && !(packet_out->po_flags & PO_MTU_PROBE)) 3507 { 3508 size = lsquic_packet_out_total_sz(lconn, packet_out); 3509 if (size > packet_out->po_path->np_pack_size) 3510 { 3511 send_ctl_resize_q(ctl, *q, packet_out->po_path); 3512 path_ids |= 1 << packet_out->po_path->np_path_id; 3513 q_idxs |= 1 << (q - queues); 3514 goto redo_q; 3515 } 3516 } 3517 } 3518 3519 LSQ_DEBUG("resized packets in queues: 0x%X", q_idxs); 3520 lsquic_send_ctl_sanity_check(ctl); 3521} 3522 3523 3524void 3525lsquic_send_ctl_return_enc_data (struct lsquic_send_ctl *ctl) 3526{ 3527 struct lsquic_packet_out *packet_out; 3528 3529 assert(!(ctl->sc_flags & SC_IETF)); 3530 3531 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 3532 if (packet_out->po_flags & PO_ENCRYPTED) 3533 send_ctl_return_enc_data(ctl, packet_out); 3534} 3535 3536 3537/* When client updated DCID based on the first packet returned by the server, 3538 * we must update the number of bytes scheduled if the DCID length changed 3539 * because this length is used to calculate packet size. 3540 */ 3541void 3542lsquic_send_ctl_cidlen_change (struct lsquic_send_ctl *ctl, 3543 unsigned orig_cid_len, unsigned new_cid_len) 3544{ 3545 unsigned diff; 3546 3547 assert(!(ctl->sc_conn_pub->lconn->cn_flags & LSCONN_SERVER)); 3548 if (ctl->sc_n_scheduled) 3549 { 3550 ctl->sc_flags |= SC_CIDLEN; 3551 ctl->sc_cidlen = (signed char) new_cid_len - (signed char) orig_cid_len; 3552 if (new_cid_len > orig_cid_len) 3553 { 3554 diff = new_cid_len - orig_cid_len; 3555 diff *= ctl->sc_n_scheduled; 3556 ctl->sc_bytes_scheduled += diff; 3557 LSQ_DEBUG("increased bytes scheduled by %u bytes to %u", 3558 diff, ctl->sc_bytes_scheduled); 3559 } 3560 else if (new_cid_len < orig_cid_len) 3561 { 3562 diff = orig_cid_len - new_cid_len; 3563 diff *= ctl->sc_n_scheduled; 3564 ctl->sc_bytes_scheduled -= diff; 3565 LSQ_DEBUG("decreased bytes scheduled by %u bytes to %u", 3566 diff, ctl->sc_bytes_scheduled); 3567 } 3568 else 3569 LSQ_DEBUG("DCID length did not change"); 3570 } 3571 else 3572 LSQ_DEBUG("no scheduled packets at the time of DCID change"); 3573} 3574 3575 3576void 3577lsquic_send_ctl_begin_optack_detection (struct lsquic_send_ctl *ctl) 3578{ 3579 uint8_t rand; 3580 3581 rand = lsquic_crand_get_byte(ctl->sc_enpub->enp_crand); 3582 ctl->sc_gap = ctl->sc_cur_packno + 1 + rand; 3583} 3584 3585 3586void 3587lsquic_send_ctl_path_validated (struct lsquic_send_ctl *ctl) 3588{ 3589 LSQ_DEBUG("path validated: switch to regular can_send"); 3590 ctl->sc_can_send = send_ctl_can_send; 3591} 3592 3593 3594int 3595lsquic_send_ctl_can_send_probe (const struct lsquic_send_ctl *ctl, 3596 const struct network_path *path) 3597{ 3598 uint64_t cwnd, pacing_rate; 3599 lsquic_time_t tx_time; 3600 unsigned n_out; 3601 3602 assert(!send_ctl_in_recovery(ctl)); 3603 3604 n_out = send_ctl_all_bytes_out(ctl); 3605 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 3606 if (ctl->sc_flags & SC_PACE) 3607 { 3608 if (n_out + path->np_pack_size >= cwnd) 3609 return 0; 3610 pacing_rate = ctl->sc_ci->cci_pacing_rate(CGP(ctl), 0); 3611 tx_time = (uint64_t) path->np_pack_size * 1000000 / pacing_rate; 3612 return lsquic_pacer_can_schedule_probe(&ctl->sc_pacer, 3613 ctl->sc_n_scheduled + ctl->sc_n_in_flight_all, tx_time); 3614 } 3615 else 3616 return n_out + path->np_pack_size < cwnd; 3617} 3618 3619 3620void 3621lsquic_send_ctl_disable_ecn (struct lsquic_send_ctl *ctl) 3622{ 3623 struct lsquic_packet_out *packet_out; 3624 3625 LSQ_INFO("disable ECN"); 3626 ctl->sc_ecn = ECN_NOT_ECT; 3627 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 3628 lsquic_packet_out_set_ecn(packet_out, ECN_NOT_ECT); 3629} 3630 3631 3632void 3633lsquic_send_ctl_snapshot (struct lsquic_send_ctl *ctl, 3634 struct send_ctl_state *ctl_state) 3635{ 3636 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3637 int buffered, repace; 3638 3639 buffered = !lsquic_send_ctl_schedule_stream_packets_immediately(ctl); 3640 repace = !buffered && (ctl->sc_flags & SC_PACE); 3641 3642 if (repace) 3643 ctl_state->pacer = ctl->sc_pacer; 3644 3645 if (buffered) 3646 { 3647 lconn->cn_if->ci_ack_snapshot(lconn, &ctl_state->ack_state); 3648 ctl_state->buf_counts[BPT_OTHER_PRIO] 3649 = ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_count; 3650 ctl_state->buf_counts[BPT_HIGHEST_PRIO] 3651 = ctl->sc_buffered_packets[BPT_HIGHEST_PRIO].bpq_count; 3652 } 3653} 3654 3655 3656static void 3657send_ctl_repace (struct lsquic_send_ctl *ctl, const struct pacer *pacer, 3658 unsigned count) 3659{ 3660 unsigned n; 3661 int in_rec; 3662 3663 LSQ_DEBUG("repace, count: %u", count); 3664 ctl->sc_pacer = *pacer; 3665 3666 in_rec = send_ctl_in_recovery(ctl); 3667 for (n = 0; n < count; ++n) 3668 lsquic_pacer_packet_scheduled(&ctl->sc_pacer, 3669 ctl->sc_n_in_flight_retx + ctl->sc_n_scheduled + n, in_rec, 3670 send_ctl_transfer_time, ctl); 3671} 3672 3673 3674void 3675lsquic_send_ctl_rollback (struct lsquic_send_ctl *ctl, 3676 struct send_ctl_state *ctl_state, const struct iovec *last_iov, 3677 size_t shortfall) 3678{ 3679 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 3680 struct lsquic_packet_out *packet_out, *next; 3681 struct lsquic_packets_tailq *packets; 3682 struct stream_frame stream_frame; 3683 struct packet_out_frec_iter pofi; 3684 enum buf_packet_type packet_type; 3685 unsigned orig_count, new_count; 3686 enum quic_ft_bit lost_types; 3687 int buffered, repace, len, to_end; 3688 unsigned short prev_frec_len; 3689 struct frame_rec *frec; 3690 3691 buffered = !lsquic_send_ctl_schedule_stream_packets_immediately(ctl); 3692 repace = !buffered && (ctl->sc_flags & SC_PACE); 3693 3694 if (!buffered) 3695 { 3696 orig_count = ctl->sc_n_scheduled; 3697 packets = &ctl->sc_scheduled_packets; 3698 packet_type = 0; /* Not necessary, but compiler complains */ 3699 } 3700 else if (ctl_state->buf_counts[BPT_HIGHEST_PRIO] 3701 < ctl->sc_buffered_packets[BPT_HIGHEST_PRIO].bpq_count) 3702 { 3703 packets = &ctl->sc_buffered_packets[BPT_HIGHEST_PRIO].bpq_packets; 3704 orig_count = ctl->sc_buffered_packets[BPT_HIGHEST_PRIO].bpq_count; 3705 packet_type = BPT_HIGHEST_PRIO; 3706 } 3707 else 3708 { 3709 packets = &ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets; 3710 orig_count = ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_count; 3711 packet_type = BPT_OTHER_PRIO; 3712 } 3713 3714 /* Now find last packet: */ 3715 TAILQ_FOREACH(packet_out, packets, po_next) 3716 if ((unsigned char *) last_iov->iov_base >= packet_out->po_data 3717 && (unsigned char *) last_iov->iov_base 3718 < packet_out->po_data + packet_out->po_data_sz) 3719 break; 3720 3721 if (!packet_out) 3722 { 3723 lconn->cn_if->ci_internal_error(lconn, 3724 "rollback failed: cannot find packet"); 3725 return; 3726 } 3727 3728 for (frec = lsquic_pofi_first(&pofi, packet_out); frec; 3729 frec = lsquic_pofi_next(&pofi)) 3730 if (frec->fe_frame_type == QUIC_FRAME_STREAM 3731 /* At the time of this writing, pwritev() generates a single STREAM 3732 * frame per packet. To keep code future-proof, we use an extra 3733 * check. 3734 */ 3735 && (unsigned char *) last_iov->iov_base 3736 > packet_out->po_data + frec->fe_off 3737 && (unsigned char *) last_iov->iov_base 3738 < packet_out->po_data + frec->fe_off + frec->fe_len) 3739 break; 3740 3741 if (!frec) 3742 { 3743 lconn->cn_if->ci_internal_error(lconn, 3744 "rollback failed: cannot find frame record"); 3745 return; 3746 } 3747 3748 /* Strictly less because of the STREAM frame header */ 3749 assert(last_iov->iov_len < frec->fe_len); 3750 3751 len = lconn->cn_pf->pf_parse_stream_frame( 3752 packet_out->po_data + frec->fe_off, frec->fe_len, &stream_frame); 3753 if (len < 0) 3754 { 3755 lconn->cn_if->ci_internal_error(lconn, 3756 "error parsing own STREAM frame"); 3757 return; 3758 } 3759 3760 if (stream_frame.data_frame.df_size > last_iov->iov_len - shortfall) 3761 { 3762 packet_out->po_data_sz = (unsigned char *) last_iov->iov_base 3763 + last_iov->iov_len - shortfall - packet_out->po_data; 3764 prev_frec_len = frec->fe_len; 3765 frec->fe_len = packet_out->po_data_sz - frec->fe_off; 3766 to_end = lconn->cn_pf->pf_dec_stream_frame_size( 3767 packet_out->po_data + frec->fe_off, 3768 stream_frame.data_frame.df_size - (prev_frec_len - frec->fe_len)); 3769 if (to_end) 3770 { /* A frame that's too short may be generated when pwritev runs out 3771 * of iovecs. In that case, we adjust it here. 3772 */ 3773 if (!(packet_out->po_flags & PO_STREAM_END)) 3774 LSQ_DEBUG("set stream-end flag on truncated packet"); 3775 packet_out->po_flags |= PO_STREAM_END; 3776 } 3777 if (!buffered) 3778 ctl->sc_bytes_scheduled -= prev_frec_len - frec->fe_len; 3779 } 3780 else 3781 assert(stream_frame.data_frame.df_size 3782 == last_iov->iov_len - shortfall); 3783 3784 /* Drop any frames that follow */ 3785 for (frec = lsquic_pofi_next(&pofi); frec; frec = lsquic_pofi_next(&pofi)) 3786 frec->fe_frame_type = 0; 3787 3788 /* Return unused packets */ 3789 new_count = orig_count; 3790 lost_types = 0; 3791 for (packet_out = TAILQ_NEXT(packet_out, po_next); packet_out != NULL; 3792 packet_out = next) 3793 { 3794 next = TAILQ_NEXT(packet_out, po_next); 3795 --new_count; 3796 lost_types |= packet_out->po_frame_types; 3797 /* Undo lsquic_send_ctl_get_packet_for_stream() */ 3798 if (!buffered) 3799 send_ctl_sched_remove(ctl, packet_out); 3800 else 3801 { 3802 TAILQ_REMOVE(packets, packet_out, po_next); 3803 --ctl->sc_buffered_packets[packet_type].bpq_count; 3804 } 3805 send_ctl_destroy_packet(ctl, packet_out); 3806 } 3807 3808 if (new_count < orig_count && repace) 3809 send_ctl_repace(ctl, &ctl_state->pacer, new_count); 3810 if (buffered && (lost_types & QUIC_FTBIT_ACK)) 3811 lconn->cn_if->ci_ack_rollback(lconn, &ctl_state->ack_state); 3812} 3813 3814 3815/* Find 0-RTT packets and change them to 1-RTT packets */ 3816void 3817lsquic_send_ctl_0rtt_to_1rtt (struct lsquic_send_ctl *ctl) 3818{ 3819 struct lsquic_packet_out *packet_out; 3820 unsigned count; 3821 struct lsquic_packets_tailq *const *q; 3822 struct lsquic_packets_tailq *const queues[] = { 3823 &ctl->sc_scheduled_packets, 3824 &ctl->sc_unacked_packets[PNS_APP], 3825 &ctl->sc_lost_packets, 3826 &ctl->sc_buffered_packets[0].bpq_packets, 3827 &ctl->sc_buffered_packets[1].bpq_packets, 3828 }; 3829 3830 assert(ctl->sc_flags & SC_IETF); 3831 3832 while (packet_out = TAILQ_FIRST(&ctl->sc_0rtt_stash), packet_out != NULL) 3833 { 3834 TAILQ_REMOVE(&ctl->sc_0rtt_stash, packet_out, po_next); 3835 TAILQ_INSERT_TAIL(&ctl->sc_lost_packets, packet_out, po_next); 3836 packet_out->po_flags |= PO_LOST; 3837 } 3838 3839 count = 0; 3840 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 3841 TAILQ_FOREACH(packet_out, *q, po_next) 3842 if (packet_out->po_header_type == HETY_0RTT) 3843 { 3844 ++count; 3845 packet_out->po_header_type = HETY_NOT_SET; 3846 if (packet_out->po_flags & PO_ENCRYPTED) 3847 send_ctl_return_enc_data(ctl, packet_out); 3848 } 3849 3850 LSQ_DEBUG("handshake ok: changed %u packet%.*s from 0-RTT to 1-RTT", 3851 count, count != 1, "s"); 3852} 3853 3854 3855/* Remove 0-RTT packets from the unacked queue and wait to retransmit them 3856 * after handshake succeeds. This is the most common case. There could 3857 * (theoretically) be some corner cases where 0-RTT packets are in the 3858 * scheduled queue, but we let those be lost naturally if that occurs. 3859 */ 3860void 3861lsquic_send_ctl_stash_0rtt_packets (struct lsquic_send_ctl *ctl) 3862{ 3863 struct lsquic_packet_out *packet_out, *next; 3864 unsigned count, packet_sz; 3865 3866 count = 0; 3867 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[PNS_APP]); 3868 packet_out; packet_out = next) 3869 { 3870 next = TAILQ_NEXT(packet_out, po_next); 3871 if (packet_out->po_header_type == HETY_0RTT) 3872 { 3873 packet_sz = packet_out_sent_sz(packet_out); 3874 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 3875 TAILQ_INSERT_TAIL(&ctl->sc_0rtt_stash, packet_out, po_next); 3876 ++count; 3877 } 3878 } 3879 3880 LSQ_DEBUG("stashed %u 0-RTT packet%.*s", count, count != 1, "s"); 3881} 3882