lsquic_send_ctl.c revision 92f6e17b
1/* Copyright (c) 2017 - 2019 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 "lsquic_types.h" 14#include "lsquic_int_types.h" 15#include "lsquic.h" 16#include "lsquic_mm.h" 17#include "lsquic_engine_public.h" 18#include "lsquic_packet_common.h" 19#include "lsquic_alarmset.h" 20#include "lsquic_parse.h" 21#include "lsquic_packet_out.h" 22#include "lsquic_senhist.h" 23#include "lsquic_rtt.h" 24#include "lsquic_cubic.h" 25#include "lsquic_pacer.h" 26#include "lsquic_bw_sampler.h" 27#include "lsquic_minmax.h" 28#include "lsquic_bbr.h" 29#include "lsquic_send_ctl.h" 30#include "lsquic_util.h" 31#include "lsquic_sfcw.h" 32#include "lsquic_varint.h" 33#include "lsquic_hq.h" 34#include "lsquic_hash.h" 35#include "lsquic_stream.h" 36#include "lsquic_ver_neg.h" 37#include "lsquic_ev_log.h" 38#include "lsquic_conn.h" 39#include "lsquic_conn_flow.h" 40#include "lsquic_conn_public.h" 41#include "lsquic_cong_ctl.h" 42#include "lsquic_enc_sess.h" 43#include "lsquic_hash.h" 44#include "lsquic_malo.h" 45 46#define LSQUIC_LOGGER_MODULE LSQLM_SENDCTL 47#define LSQUIC_LOG_CONN_ID lsquic_conn_log_cid(ctl->sc_conn_pub->lconn) 48#include "lsquic_logger.h" 49 50#define MAX_RESUBMITTED_ON_RTO 2 51#define MAX_RTO_BACKOFFS 10 52#define DEFAULT_RETX_DELAY 500000 /* Microseconds */ 53#define MAX_RTO_DELAY 60000000 /* Microseconds */ 54#define MIN_RTO_DELAY 1000000 /* Microseconds */ 55#define N_NACKS_BEFORE_RETX 3 56 57#define CGP(ctl) ((struct cong_ctl *) &(ctl)->sc_cong_u) 58 59#define packet_out_total_sz(p) \ 60 lsquic_packet_out_total_sz(ctl->sc_conn_pub->lconn, p) 61#define packet_out_sent_sz(p) \ 62 lsquic_packet_out_sent_sz(ctl->sc_conn_pub->lconn, p) 63 64enum retx_mode { 65 RETX_MODE_HANDSHAKE, 66 RETX_MODE_LOSS, 67 RETX_MODE_TLP, 68 RETX_MODE_RTO, 69}; 70 71 72static const char *const retx2str[] = { 73 [RETX_MODE_HANDSHAKE] = "RETX_MODE_HANDSHAKE", 74 [RETX_MODE_LOSS] = "RETX_MODE_LOSS", 75 [RETX_MODE_TLP] = "RETX_MODE_TLP", 76 [RETX_MODE_RTO] = "RETX_MODE_RTO", 77}; 78 79#ifdef NDEBUG 80#define MAX_BPQ_COUNT 10 81#else 82static unsigned MAX_BPQ_COUNT = 10; 83void 84lsquic_send_ctl_set_max_bpq_count (unsigned count) { MAX_BPQ_COUNT = count; } 85#endif 86 87 88static void 89update_for_resending (lsquic_send_ctl_t *ctl, lsquic_packet_out_t *packet_out); 90 91 92enum expire_filter { EXFI_ALL, EXFI_HSK, EXFI_LAST, }; 93 94 95static void 96send_ctl_expire (struct lsquic_send_ctl *, enum packnum_space, 97 enum expire_filter); 98 99static void 100set_retx_alarm (struct lsquic_send_ctl *, enum packnum_space, lsquic_time_t); 101 102static void 103send_ctl_detect_losses (struct lsquic_send_ctl *, enum packnum_space, 104 lsquic_time_t time); 105 106static unsigned 107send_ctl_retx_bytes_out (const struct lsquic_send_ctl *ctl); 108 109static unsigned 110send_ctl_all_bytes_out (const struct lsquic_send_ctl *ctl); 111 112 113#ifdef NDEBUG 114static 115#elif __GNUC__ 116__attribute__((weak)) 117#endif 118int 119lsquic_send_ctl_schedule_stream_packets_immediately (lsquic_send_ctl_t *ctl) 120{ 121 return !(ctl->sc_flags & SC_BUFFER_STREAM); 122} 123 124 125#ifdef NDEBUG 126static 127#elif __GNUC__ 128__attribute__((weak)) 129#endif 130enum packno_bits 131lsquic_send_ctl_guess_packno_bits (lsquic_send_ctl_t *ctl) 132{ 133 return PACKNO_BITS_1; /* This is 2 bytes in both GQUIC and IQUIC */ 134} 135 136 137int 138lsquic_send_ctl_have_unacked_stream_frames (const lsquic_send_ctl_t *ctl) 139{ 140 const lsquic_packet_out_t *packet_out; 141 142 TAILQ_FOREACH(packet_out, &ctl->sc_unacked_packets[PNS_APP], po_next) 143 if (0 == (packet_out->po_flags & PO_LOSS_REC) 144 && (packet_out->po_frame_types & 145 ((1 << QUIC_FRAME_STREAM) | (1 << QUIC_FRAME_RST_STREAM)))) 146 return 1; 147 148 return 0; 149} 150 151 152static lsquic_packet_out_t * 153send_ctl_first_unacked_retx_packet (const struct lsquic_send_ctl *ctl, 154 enum packnum_space pns) 155{ 156 lsquic_packet_out_t *packet_out; 157 158 TAILQ_FOREACH(packet_out, &ctl->sc_unacked_packets[pns], po_next) 159 if (0 == (packet_out->po_flags & PO_LOSS_REC) 160 && (packet_out->po_frame_types & ctl->sc_retx_frames)) 161 return packet_out; 162 163 return NULL; 164} 165 166 167static lsquic_packet_out_t * 168send_ctl_last_unacked_retx_packet (const struct lsquic_send_ctl *ctl, 169 enum packnum_space pns) 170{ 171 lsquic_packet_out_t *packet_out; 172 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_unacked_packets[pns], 173 lsquic_packets_tailq, po_next) 174 if (0 == (packet_out->po_flags & PO_LOSS_REC) 175 && (packet_out->po_frame_types & ctl->sc_retx_frames)) 176 return packet_out; 177 return NULL; 178} 179 180 181static int 182have_unacked_handshake_packets (const lsquic_send_ctl_t *ctl) 183{ 184 const lsquic_packet_out_t *packet_out; 185 enum packnum_space pns; 186 187 for (pns = ctl->sc_flags & SC_IETF ? PNS_INIT : PNS_APP; pns < N_PNS; ++pns) 188 TAILQ_FOREACH(packet_out, &ctl->sc_unacked_packets[pns], po_next) 189 if (packet_out->po_flags & PO_HELLO) 190 return 1; 191 return 0; 192} 193 194 195static enum retx_mode 196get_retx_mode (const lsquic_send_ctl_t *ctl) 197{ 198 if (!(ctl->sc_conn_pub->lconn->cn_flags & LSCONN_HANDSHAKE_DONE) 199 && have_unacked_handshake_packets(ctl)) 200 return RETX_MODE_HANDSHAKE; 201 if (ctl->sc_loss_to) 202 return RETX_MODE_LOSS; 203 if (ctl->sc_n_tlp < 2) 204 return RETX_MODE_TLP; 205 return RETX_MODE_RTO; 206} 207 208 209static lsquic_time_t 210get_retx_delay (const struct lsquic_rtt_stats *rtt_stats) 211{ 212 lsquic_time_t srtt, delay; 213 214 srtt = lsquic_rtt_stats_get_srtt(rtt_stats); 215 if (srtt) 216 { 217 delay = srtt + 4 * lsquic_rtt_stats_get_rttvar(rtt_stats); 218 if (delay < MIN_RTO_DELAY) 219 delay = MIN_RTO_DELAY; 220 } 221 else 222 delay = DEFAULT_RETX_DELAY; 223 224 return delay; 225} 226 227 228static void 229retx_alarm_rings (enum alarm_id al_id, void *ctx, lsquic_time_t expiry, lsquic_time_t now) 230{ 231 lsquic_send_ctl_t *ctl = ctx; 232 lsquic_packet_out_t *packet_out; 233 enum packnum_space pns; 234 enum retx_mode rm; 235 236 pns = al_id - AL_RETX_INIT; 237 238 /* This is a callback -- before it is called, the alarm is unset */ 239 assert(!lsquic_alarmset_is_set(ctl->sc_alset, AL_RETX_INIT + pns)); 240 241 rm = get_retx_mode(ctl); 242 LSQ_INFO("retx timeout, mode %s", retx2str[rm]); 243 244 switch (rm) 245 { 246 case RETX_MODE_HANDSHAKE: 247 send_ctl_expire(ctl, pns, EXFI_HSK); 248 /* Do not register cubic loss during handshake */ 249 break; 250 case RETX_MODE_LOSS: 251 send_ctl_detect_losses(ctl, pns, now); 252 break; 253 case RETX_MODE_TLP: 254 ++ctl->sc_n_tlp; 255 send_ctl_expire(ctl, pns, EXFI_LAST); 256 break; 257 case RETX_MODE_RTO: 258 ctl->sc_last_rto_time = now; 259 ++ctl->sc_n_consec_rtos; 260 ctl->sc_next_limit = 2; 261 LSQ_DEBUG("packet RTO is %"PRIu64" usec", expiry); 262 send_ctl_expire(ctl, pns, EXFI_ALL); 263 ctl->sc_ci->cci_timeout(CGP(ctl)); 264 break; 265 } 266 267 packet_out = send_ctl_first_unacked_retx_packet(ctl, pns); 268 if (packet_out) 269 set_retx_alarm(ctl, pns, now); 270 lsquic_send_ctl_sanity_check(ctl); 271} 272 273 274static lsquic_packno_t 275first_packno (const struct lsquic_send_ctl *ctl) 276{ 277 if (ctl->sc_flags & SC_IETF) 278 return 0; 279 else 280 return 1; 281} 282 283 284/* 285 * [draft-ietf-quic-transport-12], Section 4.4.1: 286 * 287 * " The first Initial packet that is sent by a client contains a packet 288 * " number of 0. All subsequent packets contain a packet number that is 289 * " incremented by at least one, see (Section 4.8). 290 */ 291static void 292send_ctl_pick_initial_packno (struct lsquic_send_ctl *ctl) 293{ 294 ctl->sc_cur_packno = first_packno(ctl) - 1; 295} 296 297 298void 299lsquic_send_ctl_init (lsquic_send_ctl_t *ctl, struct lsquic_alarmset *alset, 300 struct lsquic_engine_public *enpub, const struct ver_neg *ver_neg, 301 struct lsquic_conn_public *conn_pub, enum send_ctl_flags flags) 302{ 303 unsigned i, algo; 304 memset(ctl, 0, sizeof(*ctl)); 305 TAILQ_INIT(&ctl->sc_scheduled_packets); 306 TAILQ_INIT(&ctl->sc_unacked_packets[PNS_INIT]); 307 TAILQ_INIT(&ctl->sc_unacked_packets[PNS_HSK]); 308 TAILQ_INIT(&ctl->sc_unacked_packets[PNS_APP]); 309 TAILQ_INIT(&ctl->sc_lost_packets); 310 ctl->sc_enpub = enpub; 311 ctl->sc_alset = alset; 312 ctl->sc_ver_neg = ver_neg; 313 ctl->sc_conn_pub = conn_pub; 314 assert(!(flags & ~(SC_IETF|SC_NSTP|SC_ECN))); 315 ctl->sc_flags = flags; 316 send_ctl_pick_initial_packno(ctl); 317 if (enpub->enp_settings.es_pace_packets) 318 ctl->sc_flags |= SC_PACE; 319 if (flags & SC_ECN) 320 ctl->sc_ecn = ECN_ECT0; 321 else 322 ctl->sc_ecn = ECN_NOT_ECT; 323 if (flags & SC_IETF) 324 ctl->sc_retx_frames = IQUIC_FRAME_RETX_MASK; 325 else 326 ctl->sc_retx_frames = GQUIC_FRAME_RETRANSMITTABLE_MASK; 327 lsquic_alarmset_init_alarm(alset, AL_RETX_INIT, retx_alarm_rings, ctl); 328 lsquic_alarmset_init_alarm(alset, AL_RETX_HSK, retx_alarm_rings, ctl); 329 lsquic_alarmset_init_alarm(alset, AL_RETX_APP, retx_alarm_rings, ctl); 330 lsquic_senhist_init(&ctl->sc_senhist, ctl->sc_flags & SC_IETF); 331 if (0 == enpub->enp_settings.es_cc_algo) 332 algo = LSQUIC_DF_CC_ALGO; 333 else 334 algo = enpub->enp_settings.es_cc_algo; 335 if (algo == 2) 336 ctl->sc_ci = &lsquic_cong_bbr_if; 337 else 338 ctl->sc_ci = &lsquic_cong_cubic_if; 339 ctl->sc_ci->cci_init(CGP(ctl), conn_pub, ctl->sc_retx_frames); 340 if (ctl->sc_flags & SC_PACE) 341 pacer_init(&ctl->sc_pacer, conn_pub->lconn, 342 /* TODO: conn_pub has a pointer to enpub: drop third argument */ 343 enpub->enp_settings.es_clock_granularity); 344 for (i = 0; i < sizeof(ctl->sc_buffered_packets) / 345 sizeof(ctl->sc_buffered_packets[0]); ++i) 346 TAILQ_INIT(&ctl->sc_buffered_packets[i].bpq_packets); 347 ctl->sc_max_packno_bits = PACKNO_BITS_2; /* Safe value before verneg */ 348} 349 350 351static int 352send_ctl_ecn_on (const struct lsquic_send_ctl *ctl) 353{ 354 return ctl->sc_ecn != ECN_NOT_ECT; 355} 356 357 358static lsquic_time_t 359calculate_packet_rto (lsquic_send_ctl_t *ctl) 360{ 361 lsquic_time_t delay; 362 363 delay = get_retx_delay(&ctl->sc_conn_pub->rtt_stats); 364 365 unsigned exp = ctl->sc_n_consec_rtos; 366 if (exp > MAX_RTO_BACKOFFS) 367 exp = MAX_RTO_BACKOFFS; 368 369 delay = delay * (1 << exp); 370 371 return delay; 372} 373 374 375static lsquic_time_t 376calculate_tlp_delay (lsquic_send_ctl_t *ctl) 377{ 378 lsquic_time_t srtt, delay; 379 380 srtt = lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats); 381 if (ctl->sc_n_in_flight_all > 1) 382 { 383 delay = 10000; /* 10 ms is the minimum tail loss probe delay */ 384 if (delay < 2 * srtt) 385 delay = 2 * srtt; 386 } 387 else 388 { 389 delay = srtt + srtt / 2 + MIN_RTO_DELAY; 390 if (delay < 2 * srtt) 391 delay = 2 * srtt; 392 } 393 394 return delay; 395} 396 397 398static void 399set_retx_alarm (struct lsquic_send_ctl *ctl, enum packnum_space pns, 400 lsquic_time_t now) 401{ 402 enum retx_mode rm; 403 lsquic_time_t delay; 404 405 assert(!TAILQ_EMPTY(&ctl->sc_unacked_packets[pns])); 406 407 rm = get_retx_mode(ctl); 408 switch (rm) 409 { 410 case RETX_MODE_HANDSHAKE: 411 /* [draft-iyengar-quic-loss-recovery-01]: 412 * 413 * if (handshake packets are outstanding): 414 * alarm_duration = max(1.5 * smoothed_rtt, 10ms) << handshake_count; 415 * handshake_count++; 416 */ 417 delay = lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats); 418 if (delay) 419 { 420 delay += delay / 2; 421 if (10000 > delay) 422 delay = 10000; 423 } 424 else 425 delay = 150000; 426 delay <<= ctl->sc_n_hsk; 427 ++ctl->sc_n_hsk; 428 break; 429 case RETX_MODE_LOSS: 430 delay = ctl->sc_loss_to; 431 break; 432 case RETX_MODE_TLP: 433 delay = calculate_tlp_delay(ctl); 434 break; 435 default: 436 assert(rm == RETX_MODE_RTO); 437 /* XXX the comment below as well as the name of the function 438 * that follows seem obsolete. 439 */ 440 /* Base RTO on the first unacked packet, following reference 441 * implementation. 442 */ 443 delay = calculate_packet_rto(ctl); 444 break; 445 } 446 447 if (delay > MAX_RTO_DELAY) 448 delay = MAX_RTO_DELAY; 449 450 LSQ_DEBUG("set retx alarm to %"PRIu64", which is %"PRIu64 451 " usec from now, mode %s", now + delay, delay, retx2str[rm]); 452 lsquic_alarmset_set(ctl->sc_alset, AL_RETX_INIT + pns, now + delay); 453} 454 455 456static int 457send_ctl_in_recovery (lsquic_send_ctl_t *ctl) 458{ 459 return ctl->sc_largest_acked_packno 460 && ctl->sc_largest_acked_packno <= ctl->sc_largest_sent_at_cutback; 461} 462 463 464#define SC_PACK_SIZE(ctl_) (+(ctl_)->sc_conn_pub->path->np_pack_size) 465 466static lsquic_time_t 467send_ctl_transfer_time (void *ctx) 468{ 469 lsquic_send_ctl_t *const ctl = ctx; 470 lsquic_time_t tx_time; 471 uint64_t pacing_rate; 472 int in_recovery; 473 474 in_recovery = send_ctl_in_recovery(ctl); 475 pacing_rate = ctl->sc_ci->cci_pacing_rate(CGP(ctl), in_recovery); 476 tx_time = (uint64_t) SC_PACK_SIZE(ctl) * 1000000 / pacing_rate; 477 return tx_time; 478} 479 480 481static void 482send_ctl_unacked_append (struct lsquic_send_ctl *ctl, 483 struct lsquic_packet_out *packet_out) 484{ 485 enum packnum_space pns; 486 487 pns = lsquic_packet_out_pns(packet_out); 488 assert(0 == (packet_out->po_flags & PO_LOSS_REC)); 489 TAILQ_INSERT_TAIL(&ctl->sc_unacked_packets[pns], packet_out, po_next); 490 packet_out->po_flags |= PO_UNACKED; 491 ctl->sc_bytes_unacked_all += packet_out_sent_sz(packet_out); 492 ctl->sc_n_in_flight_all += 1; 493 if (packet_out->po_frame_types & ctl->sc_retx_frames) 494 { 495 ctl->sc_bytes_unacked_retx += packet_out_total_sz(packet_out); 496 ++ctl->sc_n_in_flight_retx; 497 } 498} 499 500 501static void 502send_ctl_unacked_remove (struct lsquic_send_ctl *ctl, 503 struct lsquic_packet_out *packet_out, unsigned packet_sz) 504{ 505 enum packnum_space pns; 506 507 pns = lsquic_packet_out_pns(packet_out); 508 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, po_next); 509 packet_out->po_flags &= ~PO_UNACKED; 510 assert(ctl->sc_bytes_unacked_all >= packet_sz); 511 ctl->sc_bytes_unacked_all -= packet_sz; 512 ctl->sc_n_in_flight_all -= 1; 513 if (packet_out->po_frame_types & ctl->sc_retx_frames) 514 { 515 ctl->sc_bytes_unacked_retx -= packet_sz; 516 --ctl->sc_n_in_flight_retx; 517 } 518} 519 520 521static void 522send_ctl_sched_Xpend_common (struct lsquic_send_ctl *ctl, 523 struct lsquic_packet_out *packet_out) 524{ 525 packet_out->po_flags |= PO_SCHED; 526 ++ctl->sc_n_scheduled; 527 ctl->sc_bytes_scheduled += packet_out_total_sz(packet_out); 528 lsquic_send_ctl_sanity_check(ctl); 529} 530 531 532static void 533send_ctl_sched_append (struct lsquic_send_ctl *ctl, 534 struct lsquic_packet_out *packet_out) 535{ 536 TAILQ_INSERT_TAIL(&ctl->sc_scheduled_packets, packet_out, po_next); 537 send_ctl_sched_Xpend_common(ctl, packet_out); 538} 539 540 541static void 542send_ctl_sched_prepend (struct lsquic_send_ctl *ctl, 543 struct lsquic_packet_out *packet_out) 544{ 545 TAILQ_INSERT_HEAD(&ctl->sc_scheduled_packets, packet_out, po_next); 546 send_ctl_sched_Xpend_common(ctl, packet_out); 547} 548 549 550static void 551send_ctl_sched_remove (struct lsquic_send_ctl *ctl, 552 struct lsquic_packet_out *packet_out) 553{ 554 TAILQ_REMOVE(&ctl->sc_scheduled_packets, packet_out, po_next); 555 packet_out->po_flags &= ~PO_SCHED; 556 assert(ctl->sc_n_scheduled); 557 --ctl->sc_n_scheduled; 558 ctl->sc_bytes_scheduled -= packet_out_total_sz(packet_out); 559 lsquic_send_ctl_sanity_check(ctl); 560} 561 562 563int 564lsquic_send_ctl_sent_packet (lsquic_send_ctl_t *ctl, 565 struct lsquic_packet_out *packet_out) 566{ 567 enum packnum_space pns; 568 char frames[lsquic_frame_types_str_sz]; 569 570 assert(!(packet_out->po_flags & PO_ENCRYPTED)); 571 ctl->sc_last_sent_time = packet_out->po_sent; 572 pns = lsquic_packet_out_pns(packet_out); 573 LSQ_DEBUG("packet %"PRIu64" has been sent (frame types: %s)", 574 packet_out->po_packno, lsquic_frame_types_to_str(frames, 575 sizeof(frames), packet_out->po_frame_types)); 576 lsquic_senhist_add(&ctl->sc_senhist, packet_out->po_packno); 577 send_ctl_unacked_append(ctl, packet_out); 578 if (packet_out->po_frame_types & ctl->sc_retx_frames) 579 { 580 if (!lsquic_alarmset_is_set(ctl->sc_alset, AL_RETX_INIT + pns)) 581 set_retx_alarm(ctl, pns, packet_out->po_sent); 582 if (ctl->sc_n_in_flight_retx == 1) 583 ctl->sc_flags |= SC_WAS_QUIET; 584 } 585 /* TODO: Do we really want to use those for RTT info? Revisit this. */ 586 /* Hold on to packets that are not retransmittable because we need them 587 * to sample RTT information. They are released when ACK is received. 588 */ 589#if LSQUIC_SEND_STATS 590 ++ctl->sc_stats.n_total_sent; 591#endif 592 if (ctl->sc_ci->cci_sent) 593 ctl->sc_ci->cci_sent(CGP(ctl), packet_out, ctl->sc_n_in_flight_all, 594 ctl->sc_flags & SC_APP_LIMITED); 595 lsquic_send_ctl_sanity_check(ctl); 596 return 0; 597} 598 599 600static void 601take_rtt_sample (lsquic_send_ctl_t *ctl, 602 lsquic_time_t now, lsquic_time_t lack_delta) 603{ 604 const lsquic_packno_t packno = ctl->sc_largest_acked_packno; 605 const lsquic_time_t sent = ctl->sc_largest_acked_sent_time; 606 const lsquic_time_t measured_rtt = now - sent; 607 if (packno > ctl->sc_max_rtt_packno && lack_delta < measured_rtt) 608 { 609 ctl->sc_max_rtt_packno = packno; 610 lsquic_rtt_stats_update(&ctl->sc_conn_pub->rtt_stats, measured_rtt, lack_delta); 611 LSQ_DEBUG("packno %"PRIu64"; rtt: %"PRIu64"; delta: %"PRIu64"; " 612 "new srtt: %"PRIu64, packno, measured_rtt, lack_delta, 613 lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats)); 614 } 615} 616 617 618static void 619send_ctl_return_enc_data (struct lsquic_send_ctl *ctl, 620 struct lsquic_packet_out *packet_out) 621{ 622 ctl->sc_enpub->enp_pmi->pmi_return(ctl->sc_enpub->enp_pmi_ctx, 623 packet_out->po_path->np_peer_ctx, 624 packet_out->po_enc_data, lsquic_packet_out_ipv6(packet_out)); 625 packet_out->po_flags &= ~PO_ENCRYPTED; 626 packet_out->po_enc_data = NULL; 627} 628 629 630static void 631send_ctl_destroy_packet (struct lsquic_send_ctl *ctl, 632 struct lsquic_packet_out *packet_out) 633{ 634 if (0 == (packet_out->po_flags & PO_LOSS_REC)) 635 lsquic_packet_out_destroy(packet_out, ctl->sc_enpub, 636 packet_out->po_path->np_peer_ctx); 637 else 638 lsquic_malo_put(packet_out); 639} 640 641 642static void 643send_ctl_maybe_renumber_sched_to_right (struct lsquic_send_ctl *ctl, 644 const struct lsquic_packet_out *cur) 645{ 646 struct lsquic_packet_out *packet_out; 647 648 /* If current packet has PO_REPACKNO set, it means that all those to the 649 * right of it have this flag set as well. 650 */ 651 if (0 == (cur->po_flags & PO_REPACKNO)) 652 { 653 ctl->sc_cur_packno = cur->po_packno - 1; 654 for (packet_out = TAILQ_NEXT(cur, po_next); 655 packet_out && 0 == (packet_out->po_flags & PO_REPACKNO); 656 packet_out = TAILQ_NEXT(packet_out, po_next)) 657 { 658 packet_out->po_flags |= PO_REPACKNO; 659 } 660 } 661} 662 663 664/* The third argument to advance `next' pointer when modifying the unacked 665 * queue. This is because the unacked queue may contain several elements 666 * of the same chain. This is not true of the lost and scheduled packet 667 * queue, as the loss records are only present on the unacked queue. 668 */ 669static void 670send_ctl_destroy_chain (struct lsquic_send_ctl *ctl, 671 struct lsquic_packet_out *const packet_out, 672 struct lsquic_packet_out **next) 673{ 674 struct lsquic_packet_out *chain_cur, *chain_next; 675 unsigned packet_sz, count; 676 enum packnum_space pns = lsquic_packet_out_pns(packet_out); 677 678 count = 0; 679 for (chain_cur = packet_out->po_loss_chain; chain_cur != packet_out; 680 chain_cur = chain_next) 681 { 682 chain_next = chain_cur->po_loss_chain; 683 switch (chain_cur->po_flags & (PO_SCHED|PO_UNACKED|PO_LOST)) 684 { 685 case PO_SCHED: 686 send_ctl_maybe_renumber_sched_to_right(ctl, chain_cur); 687 send_ctl_sched_remove(ctl, chain_cur); 688 break; 689 case PO_UNACKED: 690 if (chain_cur->po_flags & PO_LOSS_REC) 691 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], chain_cur, po_next); 692 else 693 { 694 packet_sz = packet_out_sent_sz(chain_cur); 695 send_ctl_unacked_remove(ctl, chain_cur, packet_sz); 696 } 697 break; 698 case PO_LOST: 699 TAILQ_REMOVE(&ctl->sc_lost_packets, chain_cur, po_next); 700 break; 701 case 0: 702 /* This is also weird, but let it pass */ 703 break; 704 default: 705 assert(0); 706 break; 707 } 708 if (next && *next == chain_cur) 709 *next = TAILQ_NEXT(*next, po_next); 710 if (0 == (chain_cur->po_flags & PO_LOSS_REC)) 711 lsquic_packet_out_ack_streams(chain_cur); 712 send_ctl_destroy_packet(ctl, chain_cur); 713 ++count; 714 } 715 packet_out->po_loss_chain = packet_out; 716 717 if (count) 718 LSQ_DEBUG("destroyed %u packet%.*s in chain of packet %"PRIu64, 719 count, count != 1, "s", packet_out->po_packno); 720} 721 722 723static void 724send_ctl_record_loss (struct lsquic_send_ctl *ctl, 725 struct lsquic_packet_out *packet_out) 726{ 727 struct lsquic_packet_out *loss_record; 728 729 loss_record = lsquic_malo_get(ctl->sc_conn_pub->packet_out_malo); 730 if (loss_record) 731 { 732 memset(loss_record, 0, sizeof(*loss_record)); 733 loss_record->po_flags = PO_UNACKED|PO_LOSS_REC|PO_SENT_SZ; 734 loss_record->po_flags |= 735 ((packet_out->po_flags >> POPNS_SHIFT) & 3) << POPNS_SHIFT; 736 /* Copy values used in ACK processing: */ 737 loss_record->po_packno = packet_out->po_packno; 738 loss_record->po_sent = packet_out->po_sent; 739 loss_record->po_sent_sz = packet_out_sent_sz(packet_out); 740 loss_record->po_frame_types = packet_out->po_frame_types; 741 /* Insert the loss record into the chain: */ 742 loss_record->po_loss_chain = packet_out->po_loss_chain; 743 packet_out->po_loss_chain = loss_record; 744 /* Place the loss record next to the lost packet we are about to 745 * remove from the list: 746 */ 747 TAILQ_INSERT_BEFORE(packet_out, loss_record, po_next); 748 } 749 else 750 LSQ_INFO("cannot allocate memory for loss record"); 751} 752 753 754/* Returns true if packet was rescheduled, false otherwise. In the latter 755 * case, you should not dereference packet_out after the function returns. 756 */ 757static int 758send_ctl_handle_lost_packet (lsquic_send_ctl_t *ctl, 759 lsquic_packet_out_t *packet_out, struct lsquic_packet_out **next) 760{ 761 unsigned packet_sz; 762 763 assert(ctl->sc_n_in_flight_all); 764 packet_sz = packet_out_sent_sz(packet_out); 765 766 if (packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)) 767 { 768 ctl->sc_flags |= SC_LOST_ACK_INIT << lsquic_packet_out_pns(packet_out); 769 LSQ_DEBUG("lost ACK in packet %"PRIu64, packet_out->po_packno); 770 } 771 772 if (ctl->sc_ci->cci_lost) 773 ctl->sc_ci->cci_lost(CGP(ctl), packet_out, packet_sz); 774 775 /* This is a client-only check, server check happens in mini conn */ 776 if (send_ctl_ecn_on(ctl) 777 && 0 == ctl->sc_ecn_total_acked[PNS_INIT] 778 && HETY_INITIAL == packet_out->po_header_type 779 && 3 == packet_out->po_packno) 780 { 781 LSQ_DEBUG("possible ECN black hole during handshake, disable ECN"); 782 ctl->sc_ecn = ECN_NOT_ECT; 783 } 784 785 if (packet_out->po_frame_types & ctl->sc_retx_frames) 786 { 787 LSQ_DEBUG("lost retransmittable packet %"PRIu64, 788 packet_out->po_packno); 789 send_ctl_record_loss(ctl, packet_out); 790 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 791 TAILQ_INSERT_TAIL(&ctl->sc_lost_packets, packet_out, po_next); 792 packet_out->po_flags |= PO_LOST; 793 return 1; 794 } 795 else 796 { 797 LSQ_DEBUG("lost unretransmittable packet %"PRIu64, 798 packet_out->po_packno); 799 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 800 send_ctl_destroy_chain(ctl, packet_out, next); 801 send_ctl_destroy_packet(ctl, packet_out); 802 return 0; 803 } 804} 805 806 807static lsquic_packno_t 808largest_retx_packet_number (const struct lsquic_send_ctl *ctl, 809 enum packnum_space pns) 810{ 811 const lsquic_packet_out_t *packet_out; 812 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_unacked_packets[pns], 813 lsquic_packets_tailq, po_next) 814 { 815 if (0 == (packet_out->po_flags & PO_LOSS_REC) 816 && (packet_out->po_frame_types & ctl->sc_retx_frames)) 817 return packet_out->po_packno; 818 } 819 return 0; 820} 821 822 823static void 824send_ctl_detect_losses (struct lsquic_send_ctl *ctl, enum packnum_space pns, 825 lsquic_time_t time) 826{ 827 lsquic_packet_out_t *packet_out, *next; 828 lsquic_packno_t largest_retx_packno, largest_lost_packno; 829 830 largest_retx_packno = largest_retx_packet_number(ctl, pns); 831 largest_lost_packno = 0; 832 ctl->sc_loss_to = 0; 833 834 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); 835 packet_out && packet_out->po_packno <= ctl->sc_largest_acked_packno; 836 packet_out = next) 837 { 838 next = TAILQ_NEXT(packet_out, po_next); 839 840 if (packet_out->po_flags & PO_LOSS_REC) 841 continue; 842 843 if (packet_out->po_packno + N_NACKS_BEFORE_RETX < 844 ctl->sc_largest_acked_packno) 845 { 846 LSQ_DEBUG("loss by FACK detected, packet %"PRIu64, 847 packet_out->po_packno); 848 largest_lost_packno = packet_out->po_packno; 849 (void) send_ctl_handle_lost_packet(ctl, packet_out, &next); 850 continue; 851 } 852 853 if (largest_retx_packno 854 && (packet_out->po_frame_types & ctl->sc_retx_frames) 855 && largest_retx_packno <= ctl->sc_largest_acked_packno) 856 { 857 LSQ_DEBUG("loss by early retransmit detected, packet %"PRIu64, 858 packet_out->po_packno); 859 largest_lost_packno = packet_out->po_packno; 860 ctl->sc_loss_to = 861 lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats) / 4; 862 LSQ_DEBUG("set sc_loss_to to %"PRIu64", packet %"PRIu64, 863 ctl->sc_loss_to, packet_out->po_packno); 864 (void) send_ctl_handle_lost_packet(ctl, packet_out, &next); 865 continue; 866 } 867 868 if (ctl->sc_largest_acked_sent_time > packet_out->po_sent + 869 lsquic_rtt_stats_get_srtt(&ctl->sc_conn_pub->rtt_stats)) 870 { 871 LSQ_DEBUG("loss by sent time detected: packet %"PRIu64, 872 packet_out->po_packno); 873 if (packet_out->po_frame_types & ctl->sc_retx_frames) 874 largest_lost_packno = packet_out->po_packno; 875 else { /* don't count it as a loss */; } 876 (void) send_ctl_handle_lost_packet(ctl, packet_out, &next); 877 continue; 878 } 879 } 880 881 if (largest_lost_packno > ctl->sc_largest_sent_at_cutback) 882 { 883 LSQ_DEBUG("detected new loss: packet %"PRIu64"; new lsac: " 884 "%"PRIu64, largest_lost_packno, ctl->sc_largest_sent_at_cutback); 885 ctl->sc_ci->cci_loss(CGP(ctl)); 886 if (ctl->sc_flags & SC_PACE) 887 pacer_loss_event(&ctl->sc_pacer); 888 ctl->sc_largest_sent_at_cutback = 889 lsquic_senhist_largest(&ctl->sc_senhist); 890 } 891 else if (largest_lost_packno) 892 /* Lost packets whose numbers are smaller than the largest packet 893 * number sent at the time of the last loss event indicate the same 894 * loss event. This follows NewReno logic, see RFC 6582. 895 */ 896 LSQ_DEBUG("ignore loss of packet %"PRIu64" smaller than lsac " 897 "%"PRIu64, largest_lost_packno, ctl->sc_largest_sent_at_cutback); 898} 899 900 901int 902lsquic_send_ctl_got_ack (lsquic_send_ctl_t *ctl, 903 const struct ack_info *acki, 904 lsquic_time_t ack_recv_time, lsquic_time_t now) 905{ 906 const struct lsquic_packno_range *range = 907 &acki->ranges[ acki->n_ranges - 1 ]; 908 lsquic_packet_out_t *packet_out, *next; 909 lsquic_packno_t smallest_unacked; 910 lsquic_packno_t ack2ed[2]; 911 unsigned packet_sz; 912 int app_limited; 913 signed char do_rtt, skip_checks; 914 enum packnum_space pns; 915 unsigned ecn_total_acked, ecn_ce_cnt, one_rtt_cnt; 916 917 pns = acki->pns; 918 packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); 919#if __GNUC__ 920 __builtin_prefetch(packet_out); 921#endif 922 923#if __GNUC__ 924# define UNLIKELY(cond) __builtin_expect(cond, 0) 925#else 926# define UNLIKELY(cond) cond 927#endif 928 929#if __GNUC__ 930 if (UNLIKELY(LSQ_LOG_ENABLED(LSQ_LOG_DEBUG))) 931#endif 932 LSQ_DEBUG("Got ACK frame, largest acked: %"PRIu64"; delta: %"PRIu64, 933 largest_acked(acki), acki->lack_delta); 934 935 /* Validate ACK first: */ 936 if (UNLIKELY(largest_acked(acki) 937 > lsquic_senhist_largest(&ctl->sc_senhist))) 938 { 939 LSQ_INFO("at least one packet in ACK range [%"PRIu64" - %"PRIu64"] " 940 "was never sent", acki->ranges[0].low, acki->ranges[0].high); 941 return -1; 942 } 943 944 if (ctl->sc_ci->cci_begin_ack) 945 ctl->sc_ci->cci_begin_ack(CGP(ctl), ack_recv_time, 946 ctl->sc_bytes_unacked_all); 947 948 ecn_total_acked = 0; 949 ecn_ce_cnt = 0; 950 one_rtt_cnt = 0; 951 952 if (UNLIKELY(ctl->sc_flags & SC_WAS_QUIET)) 953 { 954 ctl->sc_flags &= ~SC_WAS_QUIET; 955 LSQ_DEBUG("ACK comes after a period of quiescence"); 956 ctl->sc_ci->cci_was_quiet(CGP(ctl), now, ctl->sc_bytes_unacked_all); 957 } 958 959 if (UNLIKELY(!packet_out)) 960 goto no_unacked_packets; 961 962 smallest_unacked = packet_out->po_packno; 963 LSQ_DEBUG("Smallest unacked: %"PRIu64, smallest_unacked); 964 965 ack2ed[1] = 0; 966 967 if (packet_out->po_packno > largest_acked(acki)) 968 goto detect_losses; 969 970 if (largest_acked(acki) > ctl->sc_cur_rt_end) 971 { 972 ++ctl->sc_rt_count; 973 ctl->sc_cur_rt_end = lsquic_senhist_largest(&ctl->sc_senhist); 974 } 975 976 do_rtt = 0, skip_checks = 0; 977 app_limited = -1; 978 do 979 { 980 next = TAILQ_NEXT(packet_out, po_next); 981#if __GNUC__ 982 __builtin_prefetch(next); 983#endif 984 if (skip_checks) 985 goto after_checks; 986 /* This is faster than binary search in the normal case when the number 987 * of ranges is not much larger than the number of unacked packets. 988 */ 989 while (UNLIKELY(range->high < packet_out->po_packno)) 990 --range; 991 if (range->low <= packet_out->po_packno) 992 { 993 skip_checks = range == acki->ranges; 994 if (app_limited < 0) 995 app_limited = send_ctl_retx_bytes_out(ctl) + 3 * SC_PACK_SIZE(ctl) /* This 996 is the "maximum burst" parameter */ 997 < ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 998 after_checks: 999 ctl->sc_largest_acked_packno = packet_out->po_packno; 1000 ctl->sc_largest_acked_sent_time = packet_out->po_sent; 1001 ecn_total_acked += lsquic_packet_out_ecn(packet_out) != ECN_NOT_ECT; 1002 ecn_ce_cnt += lsquic_packet_out_ecn(packet_out) == ECN_CE; 1003 one_rtt_cnt += lsquic_packet_out_enc_level(packet_out) == ENC_LEV_FORW; 1004 if (0 == (packet_out->po_flags & PO_LOSS_REC)) 1005 { 1006 packet_sz = packet_out_sent_sz(packet_out); 1007 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 1008 lsquic_packet_out_ack_streams(packet_out); 1009 LSQ_DEBUG("acking via regular record %"PRIu64, 1010 packet_out->po_packno); 1011 } 1012 else 1013 { 1014 packet_sz = packet_out->po_sent_sz; 1015 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, 1016 po_next); 1017 LSQ_DEBUG("acking via loss record %"PRIu64, 1018 packet_out->po_packno); 1019#if LSQUIC_CONN_STATS 1020 ++ctl->sc_conn_pub->conn_stats->out.acked_via_loss; 1021 LSQ_DEBUG("acking via loss record %"PRIu64, 1022 packet_out->po_packno); 1023#endif 1024 } 1025 ack2ed[!!(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK))] 1026 = packet_out->po_ack2ed; 1027 do_rtt |= packet_out->po_packno == largest_acked(acki); 1028 ctl->sc_ci->cci_ack(CGP(ctl), packet_out, packet_sz, now, 1029 app_limited); 1030 send_ctl_destroy_chain(ctl, packet_out, &next); 1031 send_ctl_destroy_packet(ctl, packet_out); 1032 } 1033 packet_out = next; 1034 } 1035 while (packet_out && packet_out->po_packno <= largest_acked(acki)); 1036 1037 if (do_rtt) 1038 { 1039 take_rtt_sample(ctl, ack_recv_time, acki->lack_delta); 1040 ctl->sc_n_consec_rtos = 0; 1041 ctl->sc_n_hsk = 0; 1042 ctl->sc_n_tlp = 0; 1043 } 1044 1045 detect_losses: 1046 send_ctl_detect_losses(ctl, pns, ack_recv_time); 1047 if (send_ctl_first_unacked_retx_packet(ctl, pns)) 1048 set_retx_alarm(ctl, pns, now); 1049 else 1050 { 1051 LSQ_DEBUG("No retransmittable packets: clear alarm"); 1052 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 1053 } 1054 lsquic_send_ctl_sanity_check(ctl); 1055 1056 if ((ctl->sc_flags & SC_NSTP) && ack2ed[1] > ctl->sc_largest_ack2ed[pns]) 1057 ctl->sc_largest_ack2ed[pns] = ack2ed[1]; 1058 1059 if (ctl->sc_n_in_flight_retx == 0) 1060 ctl->sc_flags |= SC_WAS_QUIET; 1061 1062 if (one_rtt_cnt) 1063 ctl->sc_flags |= SC_1RTT_ACKED; 1064 1065 if (send_ctl_ecn_on(ctl)) 1066 { 1067 const uint64_t sum = acki->ecn_counts[ECN_ECT0] 1068 + acki->ecn_counts[ECN_ECT1] 1069 + acki->ecn_counts[ECN_CE]; 1070 ctl->sc_ecn_total_acked[pns] += ecn_total_acked; 1071 ctl->sc_ecn_ce_cnt[pns] += ecn_ce_cnt; 1072 if (sum >= ctl->sc_ecn_total_acked[pns]) 1073 { 1074 if (sum > ctl->sc_ecn_total_acked[pns]) 1075 ctl->sc_ecn_total_acked[pns] = sum; 1076 if (acki->ecn_counts[ECN_CE] > ctl->sc_ecn_ce_cnt[pns]) 1077 { 1078 ctl->sc_ecn_ce_cnt[pns] = acki->ecn_counts[ECN_CE]; 1079 LSQ_WARN("TODO: handle ECN CE event"); /* XXX TODO */ 1080 } 1081 } 1082 else 1083 { 1084 LSQ_INFO("ECN total ACKed (%"PRIu64") is greater than the sum " 1085 "of ECN counters (%"PRIu64"): disable ECN", 1086 ctl->sc_ecn_total_acked[pns], sum); 1087 ctl->sc_ecn = ECN_NOT_ECT; 1088 } 1089 } 1090 1091 update_n_stop_waiting: 1092 if (!(ctl->sc_flags & (SC_NSTP|SC_IETF))) 1093 { 1094 if (smallest_unacked > smallest_acked(acki)) 1095 /* Peer is acking packets that have been acked already. Schedule 1096 * ACK and STOP_WAITING frame to chop the range if we get two of 1097 * these in a row. 1098 */ 1099 ++ctl->sc_n_stop_waiting; 1100 else 1101 ctl->sc_n_stop_waiting = 0; 1102 } 1103 lsquic_send_ctl_sanity_check(ctl); 1104 if (ctl->sc_ci->cci_end_ack) 1105 ctl->sc_ci->cci_end_ack(CGP(ctl), ctl->sc_bytes_unacked_all); 1106 return 0; 1107 1108 no_unacked_packets: 1109 smallest_unacked = lsquic_senhist_largest(&ctl->sc_senhist) + 1; 1110 ctl->sc_flags |= SC_WAS_QUIET; 1111 goto update_n_stop_waiting; 1112} 1113 1114 1115lsquic_packno_t 1116lsquic_send_ctl_smallest_unacked (lsquic_send_ctl_t *ctl) 1117{ 1118 const lsquic_packet_out_t *packet_out; 1119 enum packnum_space pns; 1120 1121 /* Packets are always sent out in order (unless we are reordering them 1122 * on purpose). Thus, the first packet on the unacked packets list has 1123 * the smallest packet number of all packets on that list. 1124 */ 1125 for (pns = ctl->sc_flags & SC_IETF ? PNS_INIT : PNS_APP; pns < N_PNS; ++pns) 1126 if ((packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]))) 1127 /* We're OK with using a loss record */ 1128 return packet_out->po_packno; 1129 1130 return lsquic_senhist_largest(&ctl->sc_senhist) + first_packno(ctl); 1131} 1132 1133 1134static struct lsquic_packet_out * 1135send_ctl_next_lost (lsquic_send_ctl_t *ctl) 1136{ 1137 struct lsquic_packet_out *lost_packet; 1138 1139 get_next_lost: 1140 lost_packet = TAILQ_FIRST(&ctl->sc_lost_packets); 1141 if (lost_packet) 1142 { 1143 if (lost_packet->po_frame_types & (1 << QUIC_FRAME_STREAM)) 1144 { 1145 if (0 == (lost_packet->po_flags & PO_MINI)) 1146 { 1147 lsquic_packet_out_elide_reset_stream_frames(lost_packet, 0); 1148 if (lost_packet->po_regen_sz >= lost_packet->po_data_sz) 1149 { 1150 LSQ_DEBUG("Dropping packet %"PRIu64" from lost queue", 1151 lost_packet->po_packno); 1152 TAILQ_REMOVE(&ctl->sc_lost_packets, lost_packet, po_next); 1153 lost_packet->po_flags &= ~PO_LOST; 1154 send_ctl_destroy_chain(ctl, lost_packet, NULL); 1155 send_ctl_destroy_packet(ctl, lost_packet); 1156 goto get_next_lost; 1157 } 1158 } 1159 else 1160 { 1161 /* Mini connection only ever sends data on stream 1. There 1162 * is nothing to elide: always resend it. 1163 */ 1164 ; 1165 } 1166 } 1167 1168 if (!lsquic_send_ctl_can_send(ctl)) 1169 return NULL; 1170 1171 TAILQ_REMOVE(&ctl->sc_lost_packets, lost_packet, po_next); 1172 lost_packet->po_flags &= ~PO_LOST; 1173 lost_packet->po_flags |= PO_RETX; 1174 } 1175 1176 return lost_packet; 1177} 1178 1179 1180static lsquic_packno_t 1181send_ctl_next_packno (lsquic_send_ctl_t *ctl) 1182{ 1183 return ++ctl->sc_cur_packno; 1184} 1185 1186 1187void 1188lsquic_send_ctl_cleanup (lsquic_send_ctl_t *ctl) 1189{ 1190 lsquic_packet_out_t *packet_out, *next; 1191 enum packnum_space pns; 1192 unsigned n; 1193 1194 lsquic_senhist_cleanup(&ctl->sc_senhist); 1195 while ((packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets))) 1196 { 1197 send_ctl_sched_remove(ctl, packet_out); 1198 send_ctl_destroy_packet(ctl, packet_out); 1199 } 1200 assert(0 == ctl->sc_n_scheduled); 1201 assert(0 == ctl->sc_bytes_scheduled); 1202 for (pns = PNS_INIT; pns < N_PNS; ++pns) 1203 while ((packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]))) 1204 { 1205 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, po_next); 1206 packet_out->po_flags &= ~PO_UNACKED; 1207#ifndef NDEBUG 1208 if (0 == (packet_out->po_flags & PO_LOSS_REC)) 1209 { 1210 ctl->sc_bytes_unacked_all -= packet_out_sent_sz(packet_out); 1211 --ctl->sc_n_in_flight_all; 1212 } 1213#endif 1214 send_ctl_destroy_packet(ctl, packet_out); 1215 } 1216 assert(0 == ctl->sc_n_in_flight_all); 1217 assert(0 == ctl->sc_bytes_unacked_all); 1218 while ((packet_out = TAILQ_FIRST(&ctl->sc_lost_packets))) 1219 { 1220 TAILQ_REMOVE(&ctl->sc_lost_packets, packet_out, po_next); 1221 packet_out->po_flags &= ~PO_LOST; 1222 send_ctl_destroy_packet(ctl, packet_out); 1223 } 1224 for (n = 0; n < sizeof(ctl->sc_buffered_packets) / 1225 sizeof(ctl->sc_buffered_packets[0]); ++n) 1226 { 1227 for (packet_out = TAILQ_FIRST(&ctl->sc_buffered_packets[n].bpq_packets); 1228 packet_out; packet_out = next) 1229 { 1230 next = TAILQ_NEXT(packet_out, po_next); 1231 send_ctl_destroy_packet(ctl, packet_out); 1232 } 1233 } 1234 if (ctl->sc_flags & SC_PACE) 1235 pacer_cleanup(&ctl->sc_pacer); 1236 ctl->sc_ci->cci_cleanup(CGP(ctl)); 1237#if LSQUIC_SEND_STATS 1238 LSQ_NOTICE("stats: n_total_sent: %u; n_resent: %u; n_delayed: %u", 1239 ctl->sc_stats.n_total_sent, ctl->sc_stats.n_resent, 1240 ctl->sc_stats.n_delayed); 1241#endif 1242 free(ctl->sc_token); 1243} 1244 1245 1246static unsigned 1247send_ctl_retx_bytes_out (const struct lsquic_send_ctl *ctl) 1248{ 1249 return ctl->sc_bytes_scheduled 1250 + ctl->sc_bytes_unacked_retx 1251 ; 1252} 1253 1254 1255static unsigned 1256send_ctl_all_bytes_out (const struct lsquic_send_ctl *ctl) 1257{ 1258 return ctl->sc_bytes_scheduled 1259 + ctl->sc_bytes_unacked_all 1260 ; 1261} 1262 1263 1264int 1265lsquic_send_ctl_pacer_blocked (struct lsquic_send_ctl *ctl) 1266{ 1267 return (ctl->sc_flags & SC_PACE) 1268 && !pacer_can_schedule(&ctl->sc_pacer, 1269 ctl->sc_n_scheduled + ctl->sc_n_in_flight_all); 1270} 1271 1272 1273#ifndef NDEBUG 1274#if __GNUC__ 1275__attribute__((weak)) 1276#endif 1277#endif 1278int 1279lsquic_send_ctl_can_send (lsquic_send_ctl_t *ctl) 1280{ 1281 const unsigned n_out = send_ctl_all_bytes_out(ctl); 1282 LSQ_DEBUG("%s: n_out: %u (unacked_all: %u); cwnd: %"PRIu64, __func__, 1283 n_out, ctl->sc_bytes_unacked_all, 1284 ctl->sc_ci->cci_get_cwnd(CGP(ctl))); 1285 if (ctl->sc_flags & SC_PACE) 1286 { 1287 if (n_out >= ctl->sc_ci->cci_get_cwnd(CGP(ctl))) 1288 return 0; 1289 if (pacer_can_schedule(&ctl->sc_pacer, 1290 ctl->sc_n_scheduled + ctl->sc_n_in_flight_all)) 1291 return 1; 1292 if (ctl->sc_flags & SC_SCHED_TICK) 1293 { 1294 ctl->sc_flags &= ~SC_SCHED_TICK; 1295 lsquic_engine_add_conn_to_attq(ctl->sc_enpub, 1296 ctl->sc_conn_pub->lconn, pacer_next_sched(&ctl->sc_pacer)); 1297 } 1298 return 0; 1299 } 1300 else 1301 return n_out < ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 1302} 1303 1304 1305/* Like lsquic_send_ctl_can_send(), but no mods */ 1306static int 1307send_ctl_could_send (const struct lsquic_send_ctl *ctl) 1308{ 1309 uint64_t cwnd; 1310 unsigned n_out; 1311 1312 if ((ctl->sc_flags & SC_PACE) && pacer_delayed(&ctl->sc_pacer)) 1313 return 0; 1314 1315 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 1316 n_out = send_ctl_all_bytes_out(ctl); 1317 return n_out < cwnd; 1318} 1319 1320 1321void 1322lsquic_send_ctl_maybe_app_limited (struct lsquic_send_ctl *ctl, 1323 const struct network_path *path) 1324{ 1325 const struct lsquic_packet_out *packet_out; 1326 1327 packet_out = lsquic_send_ctl_last_scheduled(ctl, PNS_APP, path, 0); 1328 if ((packet_out && lsquic_packet_out_avail(packet_out) > 10) 1329 || send_ctl_could_send(ctl)) 1330 { 1331 LSQ_DEBUG("app-limited"); 1332 ctl->sc_flags |= SC_APP_LIMITED; 1333 } 1334} 1335 1336 1337static void 1338send_ctl_expire (struct lsquic_send_ctl *ctl, enum packnum_space pns, 1339 enum expire_filter filter) 1340{ 1341 lsquic_packet_out_t *packet_out, *next; 1342 int n_resubmitted; 1343 static const char *const filter_type2str[] = { 1344 [EXFI_ALL] = "all", 1345 [EXFI_HSK] = "handshake", 1346 [EXFI_LAST] = "last", 1347 }; 1348 1349 switch (filter) 1350 { 1351 case EXFI_ALL: 1352 n_resubmitted = 0; 1353 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); 1354 packet_out; packet_out = next) 1355 { 1356 next = TAILQ_NEXT(packet_out, po_next); 1357 if (0 == (packet_out->po_flags & PO_LOSS_REC)) 1358 n_resubmitted += send_ctl_handle_lost_packet(ctl, packet_out, 1359 &next); 1360 } 1361 break; 1362 case EXFI_HSK: 1363 n_resubmitted = 0; 1364 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); packet_out; 1365 packet_out = next) 1366 { 1367 next = TAILQ_NEXT(packet_out, po_next); 1368 if (packet_out->po_flags & PO_HELLO) 1369 n_resubmitted += send_ctl_handle_lost_packet(ctl, packet_out, 1370 &next); 1371 } 1372 break; 1373 case EXFI_LAST: 1374 packet_out = send_ctl_last_unacked_retx_packet(ctl, pns); 1375 if (packet_out) 1376 n_resubmitted = send_ctl_handle_lost_packet(ctl, packet_out, NULL); 1377 else 1378 n_resubmitted = 0; 1379 break; 1380#ifdef WIN32 1381 default: 1382 n_resubmitted = 0; 1383#endif 1384 } 1385 1386 LSQ_DEBUG("consider %s packets lost: %d resubmitted", 1387 filter_type2str[filter], n_resubmitted); 1388} 1389 1390 1391void 1392lsquic_send_ctl_expire_all (lsquic_send_ctl_t *ctl) 1393{ 1394 enum packnum_space pns; 1395 1396 for (pns = ctl->sc_flags & SC_IETF ? PNS_INIT : PNS_APP; pns < N_PNS; ++pns) 1397 { 1398 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 1399 send_ctl_expire(ctl, pns, EXFI_ALL); 1400 } 1401 lsquic_send_ctl_sanity_check(ctl); 1402} 1403 1404 1405#if LSQUIC_EXTRA_CHECKS 1406void 1407lsquic_send_ctl_sanity_check (const lsquic_send_ctl_t *ctl) 1408{ 1409 const struct lsquic_packet_out *packet_out; 1410 lsquic_packno_t prev_packno; 1411 int prev_packno_set; 1412 unsigned count, bytes; 1413 enum packnum_space pns; 1414 1415 assert(!send_ctl_first_unacked_retx_packet(ctl, PNS_APP) || 1416 lsquic_alarmset_is_set(ctl->sc_alset, AL_RETX_APP)); 1417 if (lsquic_alarmset_is_set(ctl->sc_alset, AL_RETX_APP)) 1418 { 1419 assert(send_ctl_first_unacked_retx_packet(ctl, PNS_APP)); 1420 assert(lsquic_time_now() 1421 < ctl->sc_alset->as_expiry[AL_RETX_APP] + MAX_RTO_DELAY); 1422 } 1423 1424 count = 0, bytes = 0; 1425 for (pns = PNS_INIT; pns <= PNS_APP; ++pns) 1426 { 1427 prev_packno_set = 0; 1428 TAILQ_FOREACH(packet_out, &ctl->sc_unacked_packets[pns], po_next) 1429 { 1430 if (prev_packno_set) 1431 assert(packet_out->po_packno > prev_packno); 1432 else 1433 { 1434 prev_packno = packet_out->po_packno; 1435 prev_packno_set = 1; 1436 } 1437 if (0 == (packet_out->po_flags & PO_LOSS_REC)) 1438 { 1439 bytes += packet_out_sent_sz(packet_out); 1440 ++count; 1441 } 1442 } 1443 } 1444 assert(count == ctl->sc_n_in_flight_all); 1445 assert(bytes == ctl->sc_bytes_unacked_all); 1446 1447 count = 0, bytes = 0; 1448 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1449 { 1450 assert(packet_out->po_flags & PO_SCHED); 1451 bytes += packet_out_total_sz(packet_out); 1452 ++count; 1453 } 1454 assert(count == ctl->sc_n_scheduled); 1455 assert(bytes == ctl->sc_bytes_scheduled); 1456} 1457#endif 1458 1459 1460void 1461lsquic_send_ctl_scheduled_one (lsquic_send_ctl_t *ctl, 1462 lsquic_packet_out_t *packet_out) 1463{ 1464#ifndef NDEBUG 1465 const lsquic_packet_out_t *last; 1466 last = TAILQ_LAST(&ctl->sc_scheduled_packets, lsquic_packets_tailq); 1467 if (last) 1468 assert((last->po_flags & PO_REPACKNO) || 1469 last->po_packno < packet_out->po_packno); 1470#endif 1471 if (ctl->sc_flags & SC_PACE) 1472 { 1473 unsigned n_out = ctl->sc_n_in_flight_retx + ctl->sc_n_scheduled; 1474 pacer_packet_scheduled(&ctl->sc_pacer, n_out, 1475 send_ctl_in_recovery(ctl), send_ctl_transfer_time, ctl); 1476 } 1477 send_ctl_sched_append(ctl, packet_out); 1478} 1479 1480 1481/* Wrapper is used to reset the counter when it's been too long */ 1482static unsigned 1483send_ctl_get_n_consec_rtos (struct lsquic_send_ctl *ctl) 1484{ 1485 lsquic_time_t timeout; 1486 1487 if (ctl->sc_n_consec_rtos) 1488 { 1489 timeout = calculate_packet_rto(ctl); 1490 if (ctl->sc_last_rto_time + timeout < ctl->sc_last_sent_time) 1491 { 1492 ctl->sc_n_consec_rtos = 0; 1493 LSQ_DEBUG("reset RTO counter after %"PRIu64" usec", 1494 ctl->sc_last_sent_time - ctl->sc_last_rto_time); 1495 } 1496 } 1497 1498 return ctl->sc_n_consec_rtos; 1499} 1500 1501 1502/* This mimics the logic in lsquic_send_ctl_next_packet_to_send(): we want 1503 * to check whether the first scheduled packet cannot be sent. 1504 */ 1505int 1506lsquic_send_ctl_sched_is_blocked (struct lsquic_send_ctl *ctl) 1507{ 1508 const lsquic_packet_out_t *packet_out 1509 = TAILQ_FIRST(&ctl->sc_scheduled_packets); 1510 return send_ctl_get_n_consec_rtos(ctl) 1511 && 0 == ctl->sc_next_limit 1512 && packet_out 1513 && !(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)); 1514} 1515 1516 1517static void 1518send_ctl_maybe_zero_pad (struct lsquic_send_ctl *ctl, 1519 struct lsquic_packet_out *initial_packet, size_t limit) 1520{ 1521 struct lsquic_packet_out *packet_out; 1522 size_t cum_size, size; 1523 1524 cum_size = packet_out_total_sz(initial_packet); 1525 if (cum_size >= limit) 1526 return; 1527 1528 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1529 { 1530 size = packet_out_total_sz(packet_out); 1531 if (cum_size + size > SC_PACK_SIZE(ctl)) 1532 break; 1533 cum_size += size; 1534 if (cum_size >= limit) 1535 return; 1536 } 1537 1538 assert(cum_size < limit); 1539 size = limit - cum_size; 1540 if (size > lsquic_packet_out_avail(initial_packet)) 1541 size = lsquic_packet_out_avail(initial_packet); 1542 memset(initial_packet->po_data + initial_packet->po_data_sz, 0, size); 1543 initial_packet->po_data_sz += size; 1544 initial_packet->po_frame_types |= QUIC_FTBIT_PADDING; 1545 LSQ_DEBUG("Added %zu bytes of PADDING to packet %"PRIu64, size, 1546 initial_packet->po_packno); 1547} 1548 1549 1550lsquic_packet_out_t * 1551lsquic_send_ctl_next_packet_to_send (struct lsquic_send_ctl *ctl, size_t size) 1552{ 1553 lsquic_packet_out_t *packet_out; 1554 int dec_limit; 1555 1556 get_packet: 1557 packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); 1558 if (!packet_out) 1559 return NULL; 1560 1561 if (!(packet_out->po_frame_types & (1 << QUIC_FRAME_ACK)) 1562 && send_ctl_get_n_consec_rtos(ctl)) 1563 { 1564 if (ctl->sc_next_limit) 1565 dec_limit = 1; 1566 else 1567 return NULL; 1568 } 1569 else 1570 dec_limit = 0; 1571 1572 if (packet_out->po_flags & PO_REPACKNO) 1573 { 1574 if (packet_out->po_regen_sz < packet_out->po_data_sz) 1575 { 1576 update_for_resending(ctl, packet_out); 1577 packet_out->po_flags &= ~PO_REPACKNO; 1578 } 1579 else 1580 { 1581 LSQ_DEBUG("Dropping packet %"PRIu64" from scheduled queue", 1582 packet_out->po_packno); 1583 send_ctl_sched_remove(ctl, packet_out); 1584 send_ctl_destroy_chain(ctl, packet_out, NULL); 1585 send_ctl_destroy_packet(ctl, packet_out); 1586 goto get_packet; 1587 } 1588 } 1589 1590 if (UNLIKELY(size)) 1591 { 1592 if (packet_out_total_sz(packet_out) + size > SC_PACK_SIZE(ctl)) 1593 return NULL; 1594 LSQ_DEBUG("packet %"PRIu64" will be tacked on to previous packet " 1595 "(coalescing)", packet_out->po_packno); 1596 } 1597 send_ctl_sched_remove(ctl, packet_out); 1598 1599 if (dec_limit) 1600 { 1601 --ctl->sc_next_limit; 1602 packet_out->po_flags |= PO_LIMITED; 1603 } 1604 else 1605 packet_out->po_flags &= ~PO_LIMITED; 1606 1607 if (UNLIKELY(packet_out->po_header_type == HETY_INITIAL) 1608 && !(ctl->sc_conn_pub->lconn->cn_flags & LSCONN_SERVER)) 1609 { 1610 send_ctl_maybe_zero_pad(ctl, packet_out, size ? size : 1200); 1611 } 1612 1613 return packet_out; 1614} 1615 1616 1617void 1618lsquic_send_ctl_delayed_one (lsquic_send_ctl_t *ctl, 1619 lsquic_packet_out_t *packet_out) 1620{ 1621 send_ctl_sched_prepend(ctl, packet_out); 1622 if (packet_out->po_flags & PO_LIMITED) 1623 ++ctl->sc_next_limit; 1624 LSQ_DEBUG("packet %"PRIu64" has been delayed", packet_out->po_packno); 1625#if LSQUIC_SEND_STATS 1626 ++ctl->sc_stats.n_delayed; 1627#endif 1628} 1629 1630 1631int 1632lsquic_send_ctl_have_outgoing_stream_frames (const lsquic_send_ctl_t *ctl) 1633{ 1634 const lsquic_packet_out_t *packet_out; 1635 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1636 if (packet_out->po_frame_types & 1637 ((1 << QUIC_FRAME_STREAM) | (1 << QUIC_FRAME_RST_STREAM))) 1638 return 1; 1639 return 0; 1640} 1641 1642 1643int 1644lsquic_send_ctl_have_outgoing_retx_frames (const lsquic_send_ctl_t *ctl) 1645{ 1646 const lsquic_packet_out_t *packet_out; 1647 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 1648 if (packet_out->po_frame_types & ctl->sc_retx_frames) 1649 return 1; 1650 return 0; 1651} 1652 1653 1654static void 1655send_ctl_set_packet_out_token (const struct lsquic_send_ctl *ctl, 1656 struct lsquic_packet_out *packet_out) 1657{ 1658 unsigned char *token; 1659 1660 token = malloc(ctl->sc_token_sz); 1661 if (!token) 1662 { 1663 LSQ_WARN("malloc failed: cannot set initial token"); 1664 return; 1665 } 1666 1667 memcpy(token, ctl->sc_token, ctl->sc_token_sz); 1668 packet_out->po_token = token; 1669 packet_out->po_token_len = ctl->sc_token_sz; 1670 packet_out->po_flags |= PO_NONCE; 1671 LSQ_DEBUG("set initial token on packet"); 1672} 1673 1674 1675static lsquic_packet_out_t * 1676send_ctl_allocate_packet (struct lsquic_send_ctl *ctl, enum packno_bits bits, 1677 unsigned need_at_least, enum packnum_space pns, 1678 const struct network_path *path) 1679{ 1680 lsquic_packet_out_t *packet_out; 1681 1682 packet_out = lsquic_packet_out_new(&ctl->sc_enpub->enp_mm, 1683 ctl->sc_conn_pub->packet_out_malo, 1684 !(ctl->sc_flags & SC_TCID0), ctl->sc_conn_pub->lconn, bits, 1685 ctl->sc_ver_neg->vn_tag, NULL, path); 1686 if (!packet_out) 1687 return NULL; 1688 1689 if (need_at_least && lsquic_packet_out_avail(packet_out) < need_at_least) 1690 { /* This should never happen, this is why this check is performed at 1691 * this level and not lower, before the packet is actually allocated. 1692 */ 1693 LSQ_ERROR("wanted to allocate packet with at least %u bytes of " 1694 "payload, but only got %u bytes (mtu: %u bytes)", need_at_least, 1695 lsquic_packet_out_avail(packet_out), SC_PACK_SIZE(ctl)); 1696 send_ctl_destroy_packet(ctl, packet_out); 1697 return NULL; 1698 } 1699 1700 if (UNLIKELY(pns != PNS_APP)) 1701 { 1702 if (pns == PNS_INIT) 1703 { 1704 packet_out->po_header_type = HETY_INITIAL; 1705 if (ctl->sc_token) 1706 send_ctl_set_packet_out_token(ctl, packet_out); 1707 } 1708 else 1709 packet_out->po_header_type = HETY_HANDSHAKE; 1710 } 1711 1712 lsquic_packet_out_set_pns(packet_out, pns); 1713 packet_out->po_lflags |= ctl->sc_ecn << POECN_SHIFT; 1714 packet_out->po_loss_chain = packet_out; 1715 return packet_out; 1716} 1717 1718 1719lsquic_packet_out_t * 1720lsquic_send_ctl_new_packet_out (lsquic_send_ctl_t *ctl, unsigned need_at_least, 1721 enum packnum_space pns, const struct network_path *path) 1722{ 1723 lsquic_packet_out_t *packet_out; 1724 enum packno_bits bits; 1725 1726 bits = lsquic_send_ctl_packno_bits(ctl); 1727 packet_out = send_ctl_allocate_packet(ctl, bits, need_at_least, pns, path); 1728 if (!packet_out) 1729 return NULL; 1730 1731 packet_out->po_packno = send_ctl_next_packno(ctl); 1732 LSQ_DEBUG("created packet %"PRIu64, packet_out->po_packno); 1733 EV_LOG_PACKET_CREATED(LSQUIC_LOG_CONN_ID, packet_out); 1734 return packet_out; 1735} 1736 1737 1738struct lsquic_packet_out * 1739lsquic_send_ctl_last_scheduled (struct lsquic_send_ctl *ctl, 1740 enum packnum_space pns, const struct network_path *path, 1741 int regen_match) 1742{ 1743 struct lsquic_packet_out *packet_out; 1744 1745 if (0 == regen_match) 1746 { 1747 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_scheduled_packets, 1748 lsquic_packets_tailq, po_next) 1749 if (pns == lsquic_packet_out_pns(packet_out) 1750 && path == packet_out->po_path) 1751 return packet_out; 1752 } 1753 else 1754 { 1755 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_scheduled_packets, 1756 lsquic_packets_tailq, po_next) 1757 if (pns == lsquic_packet_out_pns(packet_out) 1758 && packet_out->po_regen_sz == packet_out->po_data_sz 1759 && path == packet_out->po_path) 1760 return packet_out; 1761 } 1762 1763 return NULL; 1764} 1765 1766 1767/* Do not use for STREAM frames 1768 */ 1769lsquic_packet_out_t * 1770lsquic_send_ctl_get_writeable_packet (lsquic_send_ctl_t *ctl, 1771 enum packnum_space pns, unsigned need_at_least, 1772 const struct network_path *path, int regen_match, int *is_err) 1773{ 1774 lsquic_packet_out_t *packet_out; 1775 1776 assert(need_at_least > 0); 1777 1778 packet_out = lsquic_send_ctl_last_scheduled(ctl, pns, path, regen_match); 1779 if (packet_out 1780 && !(packet_out->po_flags & (PO_MINI|PO_STREAM_END|PO_RETX)) 1781 && lsquic_packet_out_avail(packet_out) >= need_at_least) 1782 { 1783 return packet_out; 1784 } 1785 1786 if (!lsquic_send_ctl_can_send(ctl)) 1787 { 1788 if (is_err) 1789 *is_err = 0; 1790 return NULL; 1791 } 1792 1793 packet_out = lsquic_send_ctl_new_packet_out(ctl, need_at_least, pns, path); 1794 if (packet_out) 1795 { 1796 lsquic_packet_out_set_pns(packet_out, pns); 1797 lsquic_send_ctl_scheduled_one(ctl, packet_out); 1798 } 1799 else if (is_err) 1800 *is_err = 1; 1801 return packet_out; 1802} 1803 1804 1805struct lsquic_packet_out * 1806lsquic_send_ctl_get_packet_for_crypto (struct lsquic_send_ctl *ctl, 1807 unsigned need_at_least, enum packnum_space pns, 1808 const struct network_path *path) 1809{ 1810 struct lsquic_packet_out *packet_out; 1811 1812 assert(lsquic_send_ctl_schedule_stream_packets_immediately(ctl)); 1813 assert(need_at_least > 0); 1814 1815 packet_out = lsquic_send_ctl_last_scheduled(ctl, pns, path, 0); 1816 if (packet_out 1817 && !(packet_out->po_flags & (PO_STREAM_END|PO_RETX)) 1818 && lsquic_packet_out_avail(packet_out) >= need_at_least) 1819 { 1820 return packet_out; 1821 } 1822 1823 if (!lsquic_send_ctl_can_send(ctl)) 1824 return NULL; 1825 1826 packet_out = lsquic_send_ctl_new_packet_out(ctl, need_at_least, pns, path); 1827 if (!packet_out) 1828 return NULL; 1829 1830 lsquic_send_ctl_scheduled_one(ctl, packet_out); 1831 return packet_out; 1832} 1833 1834 1835static void 1836update_for_resending (lsquic_send_ctl_t *ctl, lsquic_packet_out_t *packet_out) 1837{ 1838 1839 lsquic_packno_t oldno, packno; 1840 1841 /* When the packet is resent, it uses the same number of bytes to encode 1842 * the packet number as the original packet. This follows the reference 1843 * implementation. 1844 */ 1845 oldno = packet_out->po_packno; 1846 packno = send_ctl_next_packno(ctl); 1847 1848 packet_out->po_flags &= ~PO_SENT_SZ; 1849 packet_out->po_frame_types &= ~GQUIC_FRAME_REGEN_MASK; 1850 assert(packet_out->po_frame_types); 1851 packet_out->po_packno = packno; 1852 lsquic_packet_out_set_ecn(packet_out, ctl->sc_ecn); 1853 1854 if (ctl->sc_ver_neg->vn_tag) 1855 { 1856 assert(packet_out->po_flags & PO_VERSION); /* It can only disappear */ 1857 packet_out->po_ver_tag = *ctl->sc_ver_neg->vn_tag; 1858 } 1859 1860 assert(packet_out->po_regen_sz < packet_out->po_data_sz); 1861 if (packet_out->po_regen_sz) 1862 { 1863 if (packet_out->po_flags & PO_SCHED) 1864 ctl->sc_bytes_scheduled -= packet_out->po_regen_sz; 1865 lsquic_packet_out_chop_regen(packet_out); 1866 } 1867 LSQ_DEBUG("Packet %"PRIu64" repackaged for resending as packet %"PRIu64, 1868 oldno, packno); 1869 EV_LOG_CONN_EVENT(LSQUIC_LOG_CONN_ID, "packet %"PRIu64" repackaged for " 1870 "resending as packet %"PRIu64, oldno, packno); 1871} 1872 1873 1874unsigned 1875lsquic_send_ctl_reschedule_packets (lsquic_send_ctl_t *ctl) 1876{ 1877 lsquic_packet_out_t *packet_out; 1878 unsigned n = 0; 1879 1880 while ((packet_out = send_ctl_next_lost(ctl))) 1881 { 1882 assert(packet_out->po_regen_sz < packet_out->po_data_sz); 1883 ++n; 1884#if LSQUIC_CONN_STATS 1885 ++ctl->sc_conn_pub->conn_stats->out.retx_packets; 1886#endif 1887 update_for_resending(ctl, packet_out); 1888 lsquic_send_ctl_scheduled_one(ctl, packet_out); 1889 } 1890 1891 if (n) 1892 LSQ_DEBUG("rescheduled %u packets", n); 1893 1894 return n; 1895} 1896 1897 1898void 1899lsquic_send_ctl_set_tcid0 (lsquic_send_ctl_t *ctl, int tcid0) 1900{ 1901 if (tcid0) 1902 { 1903 LSQ_INFO("set TCID flag"); 1904 ctl->sc_flags |= SC_TCID0; 1905 } 1906 else 1907 { 1908 LSQ_INFO("unset TCID flag"); 1909 ctl->sc_flags &= ~SC_TCID0; 1910 } 1911} 1912 1913 1914/* The controller elides this STREAM frames of stream `stream_id' from 1915 * scheduled and buffered packets. If a packet becomes empty as a result, 1916 * it is dropped. 1917 * 1918 * Packets on other queues do not need to be processed: unacked packets 1919 * have already been sent, and lost packets' reset stream frames will be 1920 * elided in due time. 1921 */ 1922void 1923lsquic_send_ctl_elide_stream_frames (lsquic_send_ctl_t *ctl, 1924 lsquic_stream_id_t stream_id) 1925{ 1926 struct lsquic_packet_out *packet_out, *next; 1927 unsigned n, adj; 1928 int dropped; 1929 1930 dropped = 0; 1931#ifdef WIN32 1932 next = NULL; 1933#endif 1934 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 1935 packet_out = next) 1936 { 1937 next = TAILQ_NEXT(packet_out, po_next); 1938 1939 if ((packet_out->po_frame_types & (1 << QUIC_FRAME_STREAM)) 1940 && 0 == (packet_out->po_flags & PO_MINI)) 1941 { 1942 adj = lsquic_packet_out_elide_reset_stream_frames(packet_out, 1943 stream_id); 1944 ctl->sc_bytes_scheduled -= adj; 1945 if (0 == packet_out->po_frame_types) 1946 { 1947 LSQ_DEBUG("cancel packet %"PRIu64" after eliding frames for " 1948 "stream %"PRIu64, packet_out->po_packno, stream_id); 1949 send_ctl_sched_remove(ctl, packet_out); 1950 send_ctl_destroy_chain(ctl, packet_out, NULL); 1951 send_ctl_destroy_packet(ctl, packet_out); 1952 ++dropped; 1953 } 1954 } 1955 } 1956 1957 if (dropped) 1958 lsquic_send_ctl_reset_packnos(ctl); 1959 1960 for (n = 0; n < sizeof(ctl->sc_buffered_packets) / 1961 sizeof(ctl->sc_buffered_packets[0]); ++n) 1962 { 1963 for (packet_out = TAILQ_FIRST(&ctl->sc_buffered_packets[n].bpq_packets); 1964 packet_out; packet_out = next) 1965 { 1966 next = TAILQ_NEXT(packet_out, po_next); 1967 if (packet_out->po_frame_types & (1 << QUIC_FRAME_STREAM)) 1968 { 1969 lsquic_packet_out_elide_reset_stream_frames(packet_out, stream_id); 1970 if (0 == packet_out->po_frame_types) 1971 { 1972 LSQ_DEBUG("cancel buffered packet in queue #%u after eliding " 1973 "frames for stream %"PRIu64, n, stream_id); 1974 TAILQ_REMOVE(&ctl->sc_buffered_packets[n].bpq_packets, 1975 packet_out, po_next); 1976 --ctl->sc_buffered_packets[n].bpq_count; 1977 send_ctl_destroy_packet(ctl, packet_out); 1978 LSQ_DEBUG("Elide packet from buffered queue #%u; count: %u", 1979 n, ctl->sc_buffered_packets[n].bpq_count); 1980 } 1981 } 1982 } 1983 } 1984} 1985 1986 1987/* Count how many packets will remain after the squeezing performed by 1988 * lsquic_send_ctl_squeeze_sched(). This is the number of delayed data 1989 * packets. 1990 */ 1991#ifndef NDEBUG 1992#if __GNUC__ 1993__attribute__((weak)) 1994#endif 1995#endif 1996int 1997lsquic_send_ctl_have_delayed_packets (const lsquic_send_ctl_t *ctl) 1998{ 1999 const struct lsquic_packet_out *packet_out; 2000 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2001 if (packet_out->po_regen_sz < packet_out->po_data_sz) 2002 return 1; 2003 return 0; 2004} 2005 2006 2007#ifndef NDEBUG 2008static void 2009send_ctl_log_packet_q (const lsquic_send_ctl_t *ctl, const char *prefix, 2010 const struct lsquic_packets_tailq *tailq) 2011{ 2012 const lsquic_packet_out_t *packet_out; 2013 unsigned n_packets; 2014 char *buf; 2015 size_t bufsz; 2016 int off; 2017 2018 n_packets = 0; 2019 TAILQ_FOREACH(packet_out, tailq, po_next) 2020 ++n_packets; 2021 2022 if (n_packets == 0) 2023 { 2024 LSQ_DEBUG("%s: [<empty set>]", prefix); 2025 return; 2026 } 2027 2028 bufsz = n_packets * sizeof("18446744073709551615" /* UINT64_MAX */); 2029 buf = malloc(bufsz); 2030 if (!buf) 2031 { 2032 LSQ_ERROR("%s: malloc: %s", __func__, strerror(errno)); 2033 return; 2034 } 2035 2036 off = 0; 2037 TAILQ_FOREACH(packet_out, tailq, po_next) 2038 { 2039 if (off) 2040 buf[off++] = ' '; 2041 off += sprintf(buf + off, "%"PRIu64, packet_out->po_packno); 2042 } 2043 2044 LSQ_DEBUG("%s: [%s]", prefix, buf); 2045 free(buf); 2046} 2047 2048#define LOG_PACKET_Q(prefix, queue) do { \ 2049 if (LSQ_LOG_ENABLED(LSQ_LOG_DEBUG)) \ 2050 send_ctl_log_packet_q(ctl, queue, prefix); \ 2051} while (0) 2052#else 2053#define LOG_PACKET_Q(p, q) 2054#endif 2055 2056 2057int 2058lsquic_send_ctl_squeeze_sched (lsquic_send_ctl_t *ctl) 2059{ 2060 struct lsquic_packet_out *packet_out, *next; 2061 int dropped; 2062#ifndef NDEBUG 2063 int pre_squeeze_logged = 0; 2064#endif 2065 2066 dropped = 0; 2067 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2068 packet_out = next) 2069 { 2070 next = TAILQ_NEXT(packet_out, po_next); 2071 if (packet_out->po_regen_sz < packet_out->po_data_sz) 2072 { 2073 if (packet_out->po_flags & PO_ENCRYPTED) 2074 send_ctl_return_enc_data(ctl, packet_out); 2075 } 2076 else 2077 { 2078#ifndef NDEBUG 2079 /* Log the whole list before we squeeze for the first time */ 2080 if (!pre_squeeze_logged++) 2081 LOG_PACKET_Q(&ctl->sc_scheduled_packets, 2082 "unacked packets before squeezing"); 2083#endif 2084 send_ctl_sched_remove(ctl, packet_out); 2085 LSQ_DEBUG("Dropping packet %"PRIu64" from scheduled queue", 2086 packet_out->po_packno); 2087 send_ctl_destroy_chain(ctl, packet_out, NULL); 2088 send_ctl_destroy_packet(ctl, packet_out); 2089 ++dropped; 2090 } 2091 } 2092 2093 if (dropped) 2094 lsquic_send_ctl_reset_packnos(ctl); 2095 2096#ifndef NDEBUG 2097 if (pre_squeeze_logged) 2098 LOG_PACKET_Q(&ctl->sc_scheduled_packets, 2099 "unacked packets after squeezing"); 2100 else if (ctl->sc_n_scheduled > 0) 2101 LOG_PACKET_Q(&ctl->sc_scheduled_packets, "delayed packets"); 2102#endif 2103 2104 return ctl->sc_n_scheduled > 0; 2105} 2106 2107 2108void 2109lsquic_send_ctl_reset_packnos (lsquic_send_ctl_t *ctl) 2110{ 2111 struct lsquic_packet_out *packet_out; 2112 2113 ctl->sc_cur_packno = lsquic_senhist_largest(&ctl->sc_senhist); 2114 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2115 packet_out->po_flags |= PO_REPACKNO; 2116} 2117 2118 2119void 2120lsquic_send_ctl_ack_to_front (struct lsquic_send_ctl *ctl, unsigned n_acks) 2121{ 2122 struct lsquic_packet_out *ack_packet; 2123 2124 assert(n_acks > 0); 2125 assert(ctl->sc_n_scheduled > n_acks); /* Otherwise, why is this called? */ 2126 for ( ; n_acks > 0; --n_acks) 2127 { 2128 ack_packet = TAILQ_LAST(&ctl->sc_scheduled_packets, lsquic_packets_tailq); 2129 assert(ack_packet->po_frame_types & (1 << QUIC_FRAME_ACK)); 2130 TAILQ_REMOVE(&ctl->sc_scheduled_packets, ack_packet, po_next); 2131 TAILQ_INSERT_HEAD(&ctl->sc_scheduled_packets, ack_packet, po_next); 2132 } 2133} 2134 2135 2136void 2137lsquic_send_ctl_drop_scheduled (lsquic_send_ctl_t *ctl) 2138{ 2139 struct lsquic_packet_out *packet_out, *next; 2140 unsigned n; 2141 2142 n = 0; 2143 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2144 packet_out = next) 2145 { 2146 next = TAILQ_NEXT(packet_out, po_next); 2147 if (0 == (packet_out->po_flags & PO_HELLO)) 2148 { 2149 send_ctl_sched_remove(ctl, packet_out); 2150 send_ctl_destroy_chain(ctl, packet_out, NULL); 2151 send_ctl_destroy_packet(ctl, packet_out); 2152 ++n; 2153 } 2154 } 2155 2156 ctl->sc_senhist.sh_flags |= SH_GAP_OK; 2157 2158 LSQ_DEBUG("dropped %u scheduled packet%s (%u left)", n, n != 1 ? "s" : "", 2159 ctl->sc_n_scheduled); 2160} 2161 2162 2163#ifdef NDEBUG 2164static 2165#elif __GNUC__ 2166__attribute__((weak)) 2167#endif 2168enum buf_packet_type 2169lsquic_send_ctl_determine_bpt (lsquic_send_ctl_t *ctl, 2170 const lsquic_stream_t *stream) 2171{ 2172 const lsquic_stream_t *other_stream; 2173 struct lsquic_hash_elem *el; 2174 struct lsquic_hash *all_streams; 2175 2176 all_streams = ctl->sc_conn_pub->all_streams; 2177 for (el = lsquic_hash_first(all_streams); el; 2178 el = lsquic_hash_next(all_streams)) 2179 { 2180 other_stream = lsquic_hashelem_getdata(el); 2181 if (other_stream != stream 2182 && (!(other_stream->stream_flags & STREAM_U_WRITE_DONE)) 2183 && !lsquic_stream_is_critical(other_stream) 2184 && other_stream->sm_priority < stream->sm_priority) 2185 return BPT_OTHER_PRIO; 2186 } 2187 return BPT_HIGHEST_PRIO; 2188} 2189 2190 2191static enum buf_packet_type 2192send_ctl_lookup_bpt (lsquic_send_ctl_t *ctl, 2193 const struct lsquic_stream *stream) 2194{ 2195 if (ctl->sc_cached_bpt.stream_id != stream->id) 2196 { 2197 ctl->sc_cached_bpt.stream_id = stream->id; 2198 ctl->sc_cached_bpt.packet_type = 2199 lsquic_send_ctl_determine_bpt(ctl, stream); 2200 } 2201 return ctl->sc_cached_bpt.packet_type; 2202} 2203 2204 2205static unsigned 2206send_ctl_max_bpq_count (const lsquic_send_ctl_t *ctl, 2207 enum buf_packet_type packet_type) 2208{ 2209 unsigned long cwnd; 2210 unsigned count; 2211 2212 switch (packet_type) 2213 { 2214 case BPT_OTHER_PRIO: 2215 return MAX_BPQ_COUNT; 2216 case BPT_HIGHEST_PRIO: 2217 default: /* clang does not complain about absence of `default'... */ 2218 count = ctl->sc_n_scheduled + ctl->sc_n_in_flight_retx; 2219 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 2220 if (count < cwnd / SC_PACK_SIZE(ctl)) 2221 { 2222 count -= cwnd / SC_PACK_SIZE(ctl); 2223 if (count > MAX_BPQ_COUNT) 2224 return count; 2225 } 2226 return MAX_BPQ_COUNT; 2227 } 2228} 2229 2230 2231static void 2232send_ctl_move_ack (struct lsquic_send_ctl *ctl, struct lsquic_packet_out *dst, 2233 struct lsquic_packet_out *src) 2234{ 2235 assert(dst->po_data_sz == 0); 2236 2237 if (lsquic_packet_out_avail(dst) >= src->po_regen_sz) 2238 { 2239 memcpy(dst->po_data, src->po_data, src->po_regen_sz); 2240 dst->po_data_sz = src->po_regen_sz; 2241 dst->po_regen_sz = src->po_regen_sz; 2242 dst->po_frame_types |= (GQUIC_FRAME_REGEN_MASK & src->po_frame_types); 2243 src->po_frame_types &= ~GQUIC_FRAME_REGEN_MASK; 2244 lsquic_packet_out_chop_regen(src); 2245 } 2246} 2247 2248 2249static lsquic_packet_out_t * 2250send_ctl_get_buffered_packet (lsquic_send_ctl_t *ctl, 2251 enum buf_packet_type packet_type, unsigned need_at_least, 2252 const struct network_path *path, const struct lsquic_stream *stream) 2253{ 2254 struct buf_packet_q *const packet_q = 2255 &ctl->sc_buffered_packets[packet_type]; 2256 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 2257 lsquic_packet_out_t *packet_out; 2258 enum packno_bits bits; 2259 enum { AA_STEAL, AA_GENERATE, AA_NONE, } ack_action; 2260 2261 packet_out = TAILQ_LAST(&packet_q->bpq_packets, lsquic_packets_tailq); 2262 if (packet_out 2263 && !(packet_out->po_flags & PO_STREAM_END) 2264 && lsquic_packet_out_avail(packet_out) >= need_at_least) 2265 { 2266 return packet_out; 2267 } 2268 2269 if (packet_q->bpq_count >= send_ctl_max_bpq_count(ctl, packet_type)) 2270 return NULL; 2271 2272 if (packet_q->bpq_count == 0) 2273 { 2274 /* If ACK was written to the low-priority queue first, steal it */ 2275 if (packet_q == &ctl->sc_buffered_packets[BPT_HIGHEST_PRIO] 2276 && !TAILQ_EMPTY(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets) 2277 && (TAILQ_FIRST(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets) 2278 ->po_frame_types & QUIC_FTBIT_ACK)) 2279 { 2280 LSQ_DEBUG("steal ACK frame from low-priority buffered queue"); 2281 ack_action = AA_STEAL; 2282 bits = ctl->sc_max_packno_bits; 2283 } 2284 /* If ACK can be generated, write it to the first buffered packet. */ 2285 else if (lconn->cn_if->ci_can_write_ack(lconn)) 2286 { 2287 LSQ_DEBUG("generate ACK frame for first buffered packet in " 2288 "queue #%u", packet_type); 2289 ack_action = AA_GENERATE; 2290 /* Packet length is set to the largest possible size to guarantee 2291 * that buffered packet with the ACK will not need to be split. 2292 */ 2293 bits = ctl->sc_max_packno_bits; 2294 } 2295 else 2296 goto no_ack_action; 2297 } 2298 else 2299 { 2300 no_ack_action: 2301 ack_action = AA_NONE; 2302 bits = lsquic_send_ctl_guess_packno_bits(ctl); 2303 } 2304 2305 packet_out = send_ctl_allocate_packet(ctl, bits, need_at_least, PNS_APP, 2306 path); 2307 if (!packet_out) 2308 return NULL; 2309 2310 switch (ack_action) 2311 { 2312 case AA_STEAL: 2313 send_ctl_move_ack(ctl, packet_out, 2314 TAILQ_FIRST(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets)); 2315 break; 2316 case AA_GENERATE: 2317 lconn->cn_if->ci_write_ack(lconn, packet_out); 2318 break; 2319 case AA_NONE: 2320 break; 2321 } 2322 2323 TAILQ_INSERT_TAIL(&packet_q->bpq_packets, packet_out, po_next); 2324 ++packet_q->bpq_count; 2325 LSQ_DEBUG("Add new packet to buffered queue #%u; count: %u", 2326 packet_type, packet_q->bpq_count); 2327 return packet_out; 2328} 2329 2330 2331lsquic_packet_out_t * 2332lsquic_send_ctl_get_packet_for_stream (lsquic_send_ctl_t *ctl, 2333 unsigned need_at_least, const struct network_path *path, 2334 const struct lsquic_stream *stream) 2335{ 2336 enum buf_packet_type packet_type; 2337 2338 if (lsquic_send_ctl_schedule_stream_packets_immediately(ctl)) 2339 return lsquic_send_ctl_get_writeable_packet(ctl, PNS_APP, 2340 need_at_least, path, 0, NULL); 2341 else 2342 { 2343 packet_type = send_ctl_lookup_bpt(ctl, stream); 2344 return send_ctl_get_buffered_packet(ctl, packet_type, need_at_least, 2345 path, stream); 2346 } 2347} 2348 2349 2350 2351int 2352lsquic_send_ctl_buffered_and_same_prio_as_headers (struct lsquic_send_ctl *ctl, 2353 const struct lsquic_stream *stream) 2354{ 2355 return !lsquic_send_ctl_schedule_stream_packets_immediately(ctl) 2356 && BPT_HIGHEST_PRIO == send_ctl_lookup_bpt(ctl, stream); 2357} 2358 2359 2360#ifdef NDEBUG 2361static 2362#elif __GNUC__ 2363__attribute__((weak)) 2364#endif 2365enum packno_bits 2366lsquic_send_ctl_calc_packno_bits (lsquic_send_ctl_t *ctl) 2367{ 2368 lsquic_packno_t smallest_unacked; 2369 enum packno_bits bits; 2370 unsigned n_in_flight; 2371 unsigned long cwnd; 2372 const struct parse_funcs *pf; 2373 2374 pf = ctl->sc_conn_pub->lconn->cn_pf; 2375 2376 smallest_unacked = lsquic_send_ctl_smallest_unacked(ctl); 2377 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 2378 n_in_flight = cwnd / SC_PACK_SIZE(ctl); 2379 bits = pf->pf_calc_packno_bits(ctl->sc_cur_packno + 1, smallest_unacked, 2380 n_in_flight); 2381 if (bits <= ctl->sc_max_packno_bits) 2382 return bits; 2383 else 2384 return ctl->sc_max_packno_bits; 2385} 2386 2387 2388enum packno_bits 2389lsquic_send_ctl_packno_bits (lsquic_send_ctl_t *ctl) 2390{ 2391 2392 if (lsquic_send_ctl_schedule_stream_packets_immediately(ctl)) 2393 return lsquic_send_ctl_calc_packno_bits(ctl); 2394 else 2395 return lsquic_send_ctl_guess_packno_bits(ctl); 2396} 2397 2398 2399static int 2400split_buffered_packet (lsquic_send_ctl_t *ctl, 2401 enum buf_packet_type packet_type, lsquic_packet_out_t *packet_out, 2402 enum packno_bits bits, unsigned excess_bytes) 2403{ 2404 struct buf_packet_q *const packet_q = 2405 &ctl->sc_buffered_packets[packet_type]; 2406 lsquic_packet_out_t *new_packet_out; 2407 2408 assert(TAILQ_FIRST(&packet_q->bpq_packets) == packet_out); 2409 2410 new_packet_out = send_ctl_allocate_packet(ctl, bits, 0, 2411 lsquic_packet_out_pns(packet_out), packet_out->po_path); 2412 if (!packet_out) 2413 return -1; 2414 2415 if (0 == lsquic_packet_out_split_in_two(&ctl->sc_enpub->enp_mm, packet_out, 2416 new_packet_out, ctl->sc_conn_pub->lconn->cn_pf, excess_bytes)) 2417 { 2418 lsquic_packet_out_set_packno_bits(packet_out, bits); 2419 TAILQ_INSERT_AFTER(&packet_q->bpq_packets, packet_out, new_packet_out, 2420 po_next); 2421 ++packet_q->bpq_count; 2422 LSQ_DEBUG("Add split packet to buffered queue #%u; count: %u", 2423 packet_type, packet_q->bpq_count); 2424 return 0; 2425 } 2426 else 2427 { 2428 send_ctl_destroy_packet(ctl, packet_out); 2429 return -1; 2430 } 2431} 2432 2433 2434int 2435lsquic_send_ctl_schedule_buffered (lsquic_send_ctl_t *ctl, 2436 enum buf_packet_type packet_type) 2437{ 2438 struct buf_packet_q *const packet_q = 2439 &ctl->sc_buffered_packets[packet_type]; 2440 const struct parse_funcs *const pf = ctl->sc_conn_pub->lconn->cn_pf; 2441 lsquic_packet_out_t *packet_out; 2442 unsigned used, excess; 2443 2444 assert(lsquic_send_ctl_schedule_stream_packets_immediately(ctl)); 2445 const enum packno_bits bits = lsquic_send_ctl_calc_packno_bits(ctl); 2446 const unsigned need = pf->pf_packno_bits2len(bits); 2447 2448 while ((packet_out = TAILQ_FIRST(&packet_q->bpq_packets)) && 2449 lsquic_send_ctl_can_send(ctl)) 2450 { 2451 if ((packet_out->po_frame_types & QUIC_FTBIT_ACK) 2452 && packet_out->po_ack2ed < ctl->sc_largest_acked) 2453 { 2454 /* Chrome watches for a decrease in the value of the Largest 2455 * Observed field of the ACK frame and marks it as an error: 2456 * this is why we have to send out ACK in the order they were 2457 * generated. 2458 */ 2459 LSQ_DEBUG("Remove out-of-order ACK from buffered packet"); 2460 lsquic_packet_out_chop_regen(packet_out); 2461 if (packet_out->po_data_sz == 0) 2462 { 2463 LSQ_DEBUG("Dropping now-empty buffered packet"); 2464 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 2465 --packet_q->bpq_count; 2466 send_ctl_destroy_packet(ctl, packet_out); 2467 continue; 2468 } 2469 } 2470 if (bits != lsquic_packet_out_packno_bits(packet_out)) 2471 { 2472 used = pf->pf_packno_bits2len( 2473 lsquic_packet_out_packno_bits(packet_out)); 2474 if (need > used 2475 && need - used > lsquic_packet_out_avail(packet_out)) 2476 { 2477 excess = need - used - lsquic_packet_out_avail(packet_out); 2478 if (0 != split_buffered_packet(ctl, packet_type, 2479 packet_out, bits, excess)) 2480 { 2481 return -1; 2482 } 2483 } 2484 } 2485 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 2486 --packet_q->bpq_count; 2487 packet_out->po_packno = send_ctl_next_packno(ctl); 2488 LSQ_DEBUG("Remove packet from buffered queue #%u; count: %u. " 2489 "It becomes packet %"PRIu64, packet_type, packet_q->bpq_count, 2490 packet_out->po_packno); 2491 lsquic_send_ctl_scheduled_one(ctl, packet_out); 2492 } 2493 2494 return 0; 2495} 2496 2497 2498int 2499lsquic_send_ctl_turn_on_fin (struct lsquic_send_ctl *ctl, 2500 const struct lsquic_stream *stream) 2501{ 2502 enum buf_packet_type packet_type; 2503 struct buf_packet_q *packet_q; 2504 lsquic_packet_out_t *packet_out; 2505 const struct parse_funcs *pf; 2506 2507 pf = ctl->sc_conn_pub->lconn->cn_pf; 2508 packet_type = send_ctl_lookup_bpt(ctl, stream); 2509 packet_q = &ctl->sc_buffered_packets[packet_type]; 2510 2511 TAILQ_FOREACH_REVERSE(packet_out, &packet_q->bpq_packets, 2512 lsquic_packets_tailq, po_next) 2513 if (0 == lsquic_packet_out_turn_on_fin(packet_out, pf, stream)) 2514 return 0; 2515 2516 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2517 if (0 == packet_out->po_sent 2518 && 0 == lsquic_packet_out_turn_on_fin(packet_out, pf, stream)) 2519 { 2520 return 0; 2521 } 2522 2523 return -1; 2524} 2525 2526 2527size_t 2528lsquic_send_ctl_mem_used (const struct lsquic_send_ctl *ctl) 2529{ 2530 const lsquic_packet_out_t *packet_out; 2531 unsigned n; 2532 size_t size; 2533 const struct lsquic_packets_tailq queues[] = { 2534 ctl->sc_scheduled_packets, 2535 ctl->sc_unacked_packets[PNS_INIT], 2536 ctl->sc_unacked_packets[PNS_HSK], 2537 ctl->sc_unacked_packets[PNS_APP], 2538 ctl->sc_lost_packets, 2539 ctl->sc_buffered_packets[0].bpq_packets, 2540 ctl->sc_buffered_packets[1].bpq_packets, 2541 }; 2542 2543 size = sizeof(*ctl); 2544 2545 for (n = 0; n < sizeof(queues) / sizeof(queues[0]); ++n) 2546 TAILQ_FOREACH(packet_out, &queues[n], po_next) 2547 size += lsquic_packet_out_mem_used(packet_out); 2548 2549 return size; 2550} 2551 2552 2553void 2554lsquic_send_ctl_verneg_done (struct lsquic_send_ctl *ctl) 2555{ 2556 ctl->sc_max_packno_bits = PACKNO_BITS_3; 2557 LSQ_DEBUG("version negotiation done (%s): max packno bits: %u", 2558 lsquic_ver2str[ ctl->sc_conn_pub->lconn->cn_version ], 2559 ctl->sc_max_packno_bits); 2560} 2561 2562 2563int 2564lsquic_send_ctl_retry (struct lsquic_send_ctl *ctl, 2565 const unsigned char *token, size_t token_sz, int cidlen_diff) 2566{ 2567 struct lsquic_packet_out *packet_out; 2568 2569 if (token_sz >= 1ull << (sizeof(packet_out->po_token_len) * 8)) 2570 { 2571 LSQ_WARN("token size %zu is too long", token_sz); 2572 return -1; 2573 } 2574 2575 send_ctl_expire(ctl, PNS_INIT, EXFI_ALL); 2576 packet_out = TAILQ_FIRST(&ctl->sc_lost_packets); 2577 if (!(packet_out && HETY_INITIAL == packet_out->po_header_type)) 2578 { 2579 LSQ_INFO("cannot find initial packet to add token to"); 2580 return -1; 2581 } 2582 2583 ++ctl->sc_retry_count; 2584 if (ctl->sc_retry_count > 3) 2585 { 2586 LSQ_INFO("failing connection after %u retries", ctl->sc_retry_count); 2587 return -1; 2588 } 2589 2590 if (0 != lsquic_send_ctl_set_token(ctl, token, token_sz)) 2591 return -1; 2592 2593 if (packet_out->po_nonce) 2594 free(packet_out->po_nonce); 2595 2596 packet_out->po_nonce = malloc(token_sz); 2597 if (!packet_out->po_nonce) 2598 { 2599 LSQ_WARN("%s: malloc failed", __func__); 2600 return -1; 2601 } 2602 memcpy(packet_out->po_nonce, token, token_sz); 2603 packet_out->po_flags |= PO_NONCE; 2604 packet_out->po_token_len = token_sz; 2605 packet_out->po_data_sz -= token_sz; 2606 if (cidlen_diff > 0) 2607 packet_out->po_data_sz += cidlen_diff; 2608 else if (cidlen_diff < 0) 2609 packet_out->po_data_sz -= -cidlen_diff; 2610 return 0; 2611} 2612 2613 2614int 2615lsquic_send_ctl_set_token (struct lsquic_send_ctl *ctl, 2616 const unsigned char *token, size_t token_sz) 2617{ 2618 unsigned char *copy; 2619 2620 if (token_sz > 1 << 2621 (sizeof(((struct lsquic_packet_out *)0)->po_token_len) * 8)) 2622 { 2623 errno = EINVAL; 2624 return -1; 2625 } 2626 2627 copy = malloc(token_sz); 2628 if (!copy) 2629 return -1; 2630 memcpy(copy, token, token_sz); 2631 free(ctl->sc_token); 2632 ctl->sc_token = copy; 2633 ctl->sc_token_sz = token_sz; 2634 LSQ_DEBUG("set token"); 2635 return 0; 2636} 2637 2638 2639void 2640lsquic_send_ctl_empty_pns (struct lsquic_send_ctl *ctl, enum packnum_space pns) 2641{ 2642 lsquic_packet_out_t *packet_out, *next; 2643 unsigned count, packet_sz; 2644 struct lsquic_packets_tailq *const *q; 2645 struct lsquic_packets_tailq *const queues[] = { 2646 &ctl->sc_scheduled_packets, 2647 &ctl->sc_unacked_packets[pns], 2648 &ctl->sc_lost_packets, 2649 &ctl->sc_buffered_packets[0].bpq_packets, 2650 &ctl->sc_buffered_packets[1].bpq_packets, 2651 }; 2652 2653 count = 0; 2654 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 2655 for (packet_out = TAILQ_FIRST(*q); packet_out; packet_out = next) 2656 { 2657 next = TAILQ_NEXT(packet_out, po_next); 2658 if (pns == lsquic_packet_out_pns(packet_out)) 2659 { 2660 TAILQ_REMOVE(*q, packet_out, po_next); 2661 if (*q == &ctl->sc_unacked_packets[pns]) 2662 { 2663 if (0 == (packet_out->po_flags & PO_LOSS_REC)) 2664 { 2665 packet_sz = packet_out_sent_sz(packet_out); 2666 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 2667 lsquic_packet_out_ack_streams(packet_out); 2668 } 2669 send_ctl_destroy_chain(ctl, packet_out, &next); 2670 } 2671 send_ctl_destroy_packet(ctl, packet_out); 2672 ++count; 2673 } 2674 } 2675 2676 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 2677 2678 LSQ_DEBUG("emptied %s, destroyed %u packet%.*s", lsquic_pns2str[pns], 2679 count, count != 1, "s"); 2680} 2681 2682 2683void 2684lsquic_send_ctl_repath (struct lsquic_send_ctl *ctl, struct network_path *old, 2685 struct network_path *new) 2686{ 2687 struct lsquic_packet_out *packet_out; 2688 unsigned count; 2689 struct lsquic_packets_tailq *const *q; 2690 struct lsquic_packets_tailq *const queues[] = { 2691 &ctl->sc_scheduled_packets, 2692 &ctl->sc_unacked_packets[PNS_INIT], 2693 &ctl->sc_unacked_packets[PNS_HSK], 2694 &ctl->sc_unacked_packets[PNS_APP], 2695 &ctl->sc_lost_packets, 2696 &ctl->sc_buffered_packets[0].bpq_packets, 2697 &ctl->sc_buffered_packets[1].bpq_packets, 2698 }; 2699 2700 assert(ctl->sc_flags & SC_IETF); 2701 2702 count = 0; 2703 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 2704 TAILQ_FOREACH(packet_out, *q, po_next) 2705 if (packet_out->po_path == old) 2706 { 2707 ++count; 2708 packet_out->po_path = new; 2709 if (packet_out->po_flags & PO_ENCRYPTED) 2710 send_ctl_return_enc_data(ctl, packet_out); 2711 } 2712 2713 LSQ_DEBUG("repathed %u packet%.*s", count, count != 1, "s"); 2714} 2715 2716 2717void 2718lsquic_send_ctl_return_enc_data (struct lsquic_send_ctl *ctl) 2719{ 2720 struct lsquic_packet_out *packet_out; 2721 2722 assert(!(ctl->sc_flags & SC_IETF)); 2723 2724 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2725 if (packet_out->po_flags & PO_ENCRYPTED) 2726 send_ctl_return_enc_data(ctl, packet_out); 2727} 2728