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