lsquic_send_ctl.c revision 1c9cee3e
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 void 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; 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} 1676 1677 1678static lsquic_packet_out_t * 1679send_ctl_allocate_packet (struct lsquic_send_ctl *ctl, enum packno_bits bits, 1680 unsigned need_at_least, enum packnum_space pns, 1681 const struct network_path *path) 1682{ 1683 lsquic_packet_out_t *packet_out; 1684 1685 packet_out = lsquic_packet_out_new(&ctl->sc_enpub->enp_mm, 1686 ctl->sc_conn_pub->packet_out_malo, 1687 !(ctl->sc_flags & SC_TCID0), ctl->sc_conn_pub->lconn, bits, 1688 ctl->sc_ver_neg->vn_tag, NULL, path); 1689 if (!packet_out) 1690 return NULL; 1691 1692 if (need_at_least && lsquic_packet_out_avail(packet_out) < need_at_least) 1693 { /* This should never happen, this is why this check is performed at 1694 * this level and not lower, before the packet is actually allocated. 1695 */ 1696 LSQ_ERROR("wanted to allocate packet with at least %u bytes of " 1697 "payload, but only got %u bytes (mtu: %u bytes)", need_at_least, 1698 lsquic_packet_out_avail(packet_out), SC_PACK_SIZE(ctl)); 1699 send_ctl_destroy_packet(ctl, packet_out); 1700 return NULL; 1701 } 1702 1703 if (UNLIKELY(pns != PNS_APP)) 1704 { 1705 if (pns == PNS_INIT) 1706 { 1707 packet_out->po_header_type = HETY_INITIAL; 1708 if (ctl->sc_token) 1709 send_ctl_set_packet_out_token(ctl, packet_out); 1710 } 1711 else 1712 packet_out->po_header_type = HETY_HANDSHAKE; 1713 } 1714 1715 lsquic_packet_out_set_pns(packet_out, pns); 1716 packet_out->po_lflags |= ctl->sc_ecn << POECN_SHIFT; 1717 packet_out->po_loss_chain = packet_out; 1718 return packet_out; 1719} 1720 1721 1722lsquic_packet_out_t * 1723lsquic_send_ctl_new_packet_out (lsquic_send_ctl_t *ctl, unsigned need_at_least, 1724 enum packnum_space pns, const struct network_path *path) 1725{ 1726 lsquic_packet_out_t *packet_out; 1727 enum packno_bits bits; 1728 1729 bits = lsquic_send_ctl_packno_bits(ctl); 1730 packet_out = send_ctl_allocate_packet(ctl, bits, need_at_least, pns, path); 1731 if (!packet_out) 1732 return NULL; 1733 1734 packet_out->po_packno = send_ctl_next_packno(ctl); 1735 LSQ_DEBUG("created packet %"PRIu64, packet_out->po_packno); 1736 EV_LOG_PACKET_CREATED(LSQUIC_LOG_CONN_ID, packet_out); 1737 return packet_out; 1738} 1739 1740 1741struct lsquic_packet_out * 1742lsquic_send_ctl_last_scheduled (struct lsquic_send_ctl *ctl, 1743 enum packnum_space pns, const struct network_path *path, 1744 int regen_match) 1745{ 1746 struct lsquic_packet_out *packet_out; 1747 1748 if (0 == regen_match) 1749 { 1750 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_scheduled_packets, 1751 lsquic_packets_tailq, po_next) 1752 if (pns == lsquic_packet_out_pns(packet_out) 1753 && path == packet_out->po_path) 1754 return packet_out; 1755 } 1756 else 1757 { 1758 TAILQ_FOREACH_REVERSE(packet_out, &ctl->sc_scheduled_packets, 1759 lsquic_packets_tailq, po_next) 1760 if (pns == lsquic_packet_out_pns(packet_out) 1761 && packet_out->po_regen_sz == packet_out->po_data_sz 1762 && path == packet_out->po_path) 1763 return packet_out; 1764 } 1765 1766 return NULL; 1767} 1768 1769 1770/* Do not use for STREAM frames 1771 */ 1772lsquic_packet_out_t * 1773lsquic_send_ctl_get_writeable_packet (lsquic_send_ctl_t *ctl, 1774 enum packnum_space pns, unsigned need_at_least, 1775 const struct network_path *path, int regen_match, int *is_err) 1776{ 1777 lsquic_packet_out_t *packet_out; 1778 1779 assert(need_at_least > 0); 1780 1781 packet_out = lsquic_send_ctl_last_scheduled(ctl, pns, path, regen_match); 1782 if (packet_out 1783 && !(packet_out->po_flags & (PO_MINI|PO_STREAM_END|PO_RETX)) 1784 && lsquic_packet_out_avail(packet_out) >= need_at_least) 1785 { 1786 return packet_out; 1787 } 1788 1789 if (!lsquic_send_ctl_can_send(ctl)) 1790 { 1791 if (is_err) 1792 *is_err = 0; 1793 return NULL; 1794 } 1795 1796 packet_out = lsquic_send_ctl_new_packet_out(ctl, need_at_least, pns, path); 1797 if (packet_out) 1798 { 1799 lsquic_packet_out_set_pns(packet_out, pns); 1800 lsquic_send_ctl_scheduled_one(ctl, packet_out); 1801 } 1802 else if (is_err) 1803 *is_err = 1; 1804 return packet_out; 1805} 1806 1807 1808struct lsquic_packet_out * 1809lsquic_send_ctl_get_packet_for_crypto (struct lsquic_send_ctl *ctl, 1810 unsigned need_at_least, enum packnum_space pns, 1811 const struct network_path *path) 1812{ 1813 struct lsquic_packet_out *packet_out; 1814 1815 assert(lsquic_send_ctl_schedule_stream_packets_immediately(ctl)); 1816 assert(need_at_least > 0); 1817 1818 packet_out = lsquic_send_ctl_last_scheduled(ctl, pns, path, 0); 1819 if (packet_out 1820 && !(packet_out->po_flags & (PO_STREAM_END|PO_RETX)) 1821 && lsquic_packet_out_avail(packet_out) >= need_at_least) 1822 { 1823 return packet_out; 1824 } 1825 1826 if (!lsquic_send_ctl_can_send(ctl)) 1827 return NULL; 1828 1829 packet_out = lsquic_send_ctl_new_packet_out(ctl, need_at_least, pns, path); 1830 if (!packet_out) 1831 return NULL; 1832 1833 lsquic_send_ctl_scheduled_one(ctl, packet_out); 1834 return packet_out; 1835} 1836 1837 1838static void 1839update_for_resending (lsquic_send_ctl_t *ctl, lsquic_packet_out_t *packet_out) 1840{ 1841 1842 lsquic_packno_t oldno, packno; 1843 1844 /* When the packet is resent, it uses the same number of bytes to encode 1845 * the packet number as the original packet. This follows the reference 1846 * implementation. 1847 */ 1848 oldno = packet_out->po_packno; 1849 packno = send_ctl_next_packno(ctl); 1850 1851 packet_out->po_flags &= ~PO_SENT_SZ; 1852 packet_out->po_frame_types &= ~GQUIC_FRAME_REGEN_MASK; 1853 assert(packet_out->po_frame_types); 1854 packet_out->po_packno = packno; 1855 lsquic_packet_out_set_ecn(packet_out, ctl->sc_ecn); 1856 1857 if (ctl->sc_ver_neg->vn_tag) 1858 { 1859 assert(packet_out->po_flags & PO_VERSION); /* It can only disappear */ 1860 packet_out->po_ver_tag = *ctl->sc_ver_neg->vn_tag; 1861 } 1862 1863 assert(packet_out->po_regen_sz < packet_out->po_data_sz); 1864 if (packet_out->po_regen_sz) 1865 { 1866 if (packet_out->po_flags & PO_SCHED) 1867 ctl->sc_bytes_scheduled -= packet_out->po_regen_sz; 1868 lsquic_packet_out_chop_regen(packet_out); 1869 } 1870 LSQ_DEBUG("Packet %"PRIu64" repackaged for resending as packet %"PRIu64, 1871 oldno, packno); 1872 EV_LOG_CONN_EVENT(LSQUIC_LOG_CONN_ID, "packet %"PRIu64" repackaged for " 1873 "resending as packet %"PRIu64, oldno, packno); 1874} 1875 1876 1877unsigned 1878lsquic_send_ctl_reschedule_packets (lsquic_send_ctl_t *ctl) 1879{ 1880 lsquic_packet_out_t *packet_out; 1881 unsigned n = 0; 1882 1883 while ((packet_out = send_ctl_next_lost(ctl))) 1884 { 1885 assert(packet_out->po_regen_sz < packet_out->po_data_sz); 1886 ++n; 1887#if LSQUIC_CONN_STATS 1888 ++ctl->sc_conn_pub->conn_stats->out.retx_packets; 1889#endif 1890 update_for_resending(ctl, packet_out); 1891 lsquic_send_ctl_scheduled_one(ctl, packet_out); 1892 } 1893 1894 if (n) 1895 LSQ_DEBUG("rescheduled %u packets", n); 1896 1897 return n; 1898} 1899 1900 1901void 1902lsquic_send_ctl_set_tcid0 (lsquic_send_ctl_t *ctl, int tcid0) 1903{ 1904 if (tcid0) 1905 { 1906 LSQ_INFO("set TCID flag"); 1907 ctl->sc_flags |= SC_TCID0; 1908 } 1909 else 1910 { 1911 LSQ_INFO("unset TCID flag"); 1912 ctl->sc_flags &= ~SC_TCID0; 1913 } 1914} 1915 1916 1917/* The controller elides this STREAM frames of stream `stream_id' from 1918 * scheduled and buffered packets. If a packet becomes empty as a result, 1919 * it is dropped. 1920 * 1921 * Packets on other queues do not need to be processed: unacked packets 1922 * have already been sent, and lost packets' reset stream frames will be 1923 * elided in due time. 1924 */ 1925void 1926lsquic_send_ctl_elide_stream_frames (lsquic_send_ctl_t *ctl, 1927 lsquic_stream_id_t stream_id) 1928{ 1929 struct lsquic_packet_out *packet_out, *next; 1930 unsigned n, adj; 1931 int dropped; 1932 1933 dropped = 0; 1934#ifdef WIN32 1935 next = NULL; 1936#endif 1937 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 1938 packet_out = next) 1939 { 1940 next = TAILQ_NEXT(packet_out, po_next); 1941 1942 if ((packet_out->po_frame_types & (1 << QUIC_FRAME_STREAM)) 1943 && 0 == (packet_out->po_flags & PO_MINI)) 1944 { 1945 adj = lsquic_packet_out_elide_reset_stream_frames(packet_out, 1946 stream_id); 1947 ctl->sc_bytes_scheduled -= adj; 1948 if (0 == packet_out->po_frame_types) 1949 { 1950 LSQ_DEBUG("cancel packet %"PRIu64" after eliding frames for " 1951 "stream %"PRIu64, packet_out->po_packno, stream_id); 1952 send_ctl_sched_remove(ctl, packet_out); 1953 send_ctl_destroy_chain(ctl, packet_out, NULL); 1954 send_ctl_destroy_packet(ctl, packet_out); 1955 ++dropped; 1956 } 1957 } 1958 } 1959 1960 if (dropped) 1961 lsquic_send_ctl_reset_packnos(ctl); 1962 1963 for (n = 0; n < sizeof(ctl->sc_buffered_packets) / 1964 sizeof(ctl->sc_buffered_packets[0]); ++n) 1965 { 1966 for (packet_out = TAILQ_FIRST(&ctl->sc_buffered_packets[n].bpq_packets); 1967 packet_out; packet_out = next) 1968 { 1969 next = TAILQ_NEXT(packet_out, po_next); 1970 if (packet_out->po_frame_types & (1 << QUIC_FRAME_STREAM)) 1971 { 1972 lsquic_packet_out_elide_reset_stream_frames(packet_out, stream_id); 1973 if (0 == packet_out->po_frame_types) 1974 { 1975 LSQ_DEBUG("cancel buffered packet in queue #%u after eliding " 1976 "frames for stream %"PRIu64, n, stream_id); 1977 TAILQ_REMOVE(&ctl->sc_buffered_packets[n].bpq_packets, 1978 packet_out, po_next); 1979 --ctl->sc_buffered_packets[n].bpq_count; 1980 send_ctl_destroy_packet(ctl, packet_out); 1981 LSQ_DEBUG("Elide packet from buffered queue #%u; count: %u", 1982 n, ctl->sc_buffered_packets[n].bpq_count); 1983 } 1984 } 1985 } 1986 } 1987} 1988 1989 1990/* Count how many packets will remain after the squeezing performed by 1991 * lsquic_send_ctl_squeeze_sched(). This is the number of delayed data 1992 * packets. 1993 */ 1994#ifndef NDEBUG 1995#if __GNUC__ 1996__attribute__((weak)) 1997#endif 1998#endif 1999int 2000lsquic_send_ctl_have_delayed_packets (const lsquic_send_ctl_t *ctl) 2001{ 2002 const struct lsquic_packet_out *packet_out; 2003 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2004 if (packet_out->po_regen_sz < packet_out->po_data_sz) 2005 return 1; 2006 return 0; 2007} 2008 2009 2010#ifndef NDEBUG 2011static void 2012send_ctl_log_packet_q (const lsquic_send_ctl_t *ctl, const char *prefix, 2013 const struct lsquic_packets_tailq *tailq) 2014{ 2015 const lsquic_packet_out_t *packet_out; 2016 unsigned n_packets; 2017 char *buf; 2018 size_t bufsz; 2019 int off; 2020 2021 n_packets = 0; 2022 TAILQ_FOREACH(packet_out, tailq, po_next) 2023 ++n_packets; 2024 2025 if (n_packets == 0) 2026 { 2027 LSQ_DEBUG("%s: [<empty set>]", prefix); 2028 return; 2029 } 2030 2031 bufsz = n_packets * sizeof("18446744073709551615" /* UINT64_MAX */); 2032 buf = malloc(bufsz); 2033 if (!buf) 2034 { 2035 LSQ_ERROR("%s: malloc: %s", __func__, strerror(errno)); 2036 return; 2037 } 2038 2039 off = 0; 2040 TAILQ_FOREACH(packet_out, tailq, po_next) 2041 { 2042 if (off) 2043 buf[off++] = ' '; 2044 off += sprintf(buf + off, "%"PRIu64, packet_out->po_packno); 2045 } 2046 2047 LSQ_DEBUG("%s: [%s]", prefix, buf); 2048 free(buf); 2049} 2050 2051#define LOG_PACKET_Q(prefix, queue) do { \ 2052 if (LSQ_LOG_ENABLED(LSQ_LOG_DEBUG)) \ 2053 send_ctl_log_packet_q(ctl, queue, prefix); \ 2054} while (0) 2055#else 2056#define LOG_PACKET_Q(p, q) 2057#endif 2058 2059 2060int 2061lsquic_send_ctl_squeeze_sched (lsquic_send_ctl_t *ctl) 2062{ 2063 struct lsquic_packet_out *packet_out, *next; 2064 int dropped; 2065#ifndef NDEBUG 2066 int pre_squeeze_logged = 0; 2067#endif 2068 2069 dropped = 0; 2070 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2071 packet_out = next) 2072 { 2073 next = TAILQ_NEXT(packet_out, po_next); 2074 if (packet_out->po_regen_sz < packet_out->po_data_sz) 2075 { 2076 if (packet_out->po_flags & PO_ENCRYPTED) 2077 send_ctl_return_enc_data(ctl, packet_out); 2078 } 2079 else 2080 { 2081#ifndef NDEBUG 2082 /* Log the whole list before we squeeze for the first time */ 2083 if (!pre_squeeze_logged++) 2084 LOG_PACKET_Q(&ctl->sc_scheduled_packets, 2085 "unacked packets before squeezing"); 2086#endif 2087 send_ctl_sched_remove(ctl, packet_out); 2088 LSQ_DEBUG("Dropping packet %"PRIu64" from scheduled queue", 2089 packet_out->po_packno); 2090 send_ctl_destroy_chain(ctl, packet_out, NULL); 2091 send_ctl_destroy_packet(ctl, packet_out); 2092 ++dropped; 2093 } 2094 } 2095 2096 if (dropped) 2097 lsquic_send_ctl_reset_packnos(ctl); 2098 2099#ifndef NDEBUG 2100 if (pre_squeeze_logged) 2101 LOG_PACKET_Q(&ctl->sc_scheduled_packets, 2102 "unacked packets after squeezing"); 2103 else if (ctl->sc_n_scheduled > 0) 2104 LOG_PACKET_Q(&ctl->sc_scheduled_packets, "delayed packets"); 2105#endif 2106 2107 return ctl->sc_n_scheduled > 0; 2108} 2109 2110 2111void 2112lsquic_send_ctl_reset_packnos (lsquic_send_ctl_t *ctl) 2113{ 2114 struct lsquic_packet_out *packet_out; 2115 2116 ctl->sc_cur_packno = lsquic_senhist_largest(&ctl->sc_senhist); 2117 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2118 packet_out->po_flags |= PO_REPACKNO; 2119} 2120 2121 2122void 2123lsquic_send_ctl_ack_to_front (struct lsquic_send_ctl *ctl, unsigned n_acks) 2124{ 2125 struct lsquic_packet_out *ack_packet; 2126 2127 assert(n_acks > 0); 2128 assert(ctl->sc_n_scheduled > n_acks); /* Otherwise, why is this called? */ 2129 for ( ; n_acks > 0; --n_acks) 2130 { 2131 ack_packet = TAILQ_LAST(&ctl->sc_scheduled_packets, lsquic_packets_tailq); 2132 assert(ack_packet->po_frame_types & (1 << QUIC_FRAME_ACK)); 2133 TAILQ_REMOVE(&ctl->sc_scheduled_packets, ack_packet, po_next); 2134 TAILQ_INSERT_HEAD(&ctl->sc_scheduled_packets, ack_packet, po_next); 2135 } 2136} 2137 2138 2139void 2140lsquic_send_ctl_drop_scheduled (lsquic_send_ctl_t *ctl) 2141{ 2142 struct lsquic_packet_out *packet_out, *next; 2143 unsigned n; 2144 2145 n = 0; 2146 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2147 packet_out = next) 2148 { 2149 next = TAILQ_NEXT(packet_out, po_next); 2150 if (0 == (packet_out->po_flags & PO_HELLO)) 2151 { 2152 send_ctl_sched_remove(ctl, packet_out); 2153 send_ctl_destroy_chain(ctl, packet_out, NULL); 2154 send_ctl_destroy_packet(ctl, packet_out); 2155 ++n; 2156 } 2157 } 2158 2159 ctl->sc_senhist.sh_flags |= SH_GAP_OK; 2160 2161 LSQ_DEBUG("dropped %u scheduled packet%s (%u left)", n, n != 1 ? "s" : "", 2162 ctl->sc_n_scheduled); 2163} 2164 2165 2166#ifdef NDEBUG 2167static 2168#elif __GNUC__ 2169__attribute__((weak)) 2170#endif 2171enum buf_packet_type 2172lsquic_send_ctl_determine_bpt (lsquic_send_ctl_t *ctl, 2173 const lsquic_stream_t *stream) 2174{ 2175 const lsquic_stream_t *other_stream; 2176 struct lsquic_hash_elem *el; 2177 struct lsquic_hash *all_streams; 2178 2179 all_streams = ctl->sc_conn_pub->all_streams; 2180 for (el = lsquic_hash_first(all_streams); el; 2181 el = lsquic_hash_next(all_streams)) 2182 { 2183 other_stream = lsquic_hashelem_getdata(el); 2184 if (other_stream != stream 2185 && (!(other_stream->stream_flags & STREAM_U_WRITE_DONE)) 2186 && !lsquic_stream_is_critical(other_stream) 2187 && other_stream->sm_priority < stream->sm_priority) 2188 return BPT_OTHER_PRIO; 2189 } 2190 return BPT_HIGHEST_PRIO; 2191} 2192 2193 2194static enum buf_packet_type 2195send_ctl_lookup_bpt (lsquic_send_ctl_t *ctl, 2196 const struct lsquic_stream *stream) 2197{ 2198 if (ctl->sc_cached_bpt.stream_id != stream->id) 2199 { 2200 ctl->sc_cached_bpt.stream_id = stream->id; 2201 ctl->sc_cached_bpt.packet_type = 2202 lsquic_send_ctl_determine_bpt(ctl, stream); 2203 } 2204 return ctl->sc_cached_bpt.packet_type; 2205} 2206 2207 2208static unsigned 2209send_ctl_max_bpq_count (const lsquic_send_ctl_t *ctl, 2210 enum buf_packet_type packet_type) 2211{ 2212 unsigned long cwnd; 2213 unsigned count; 2214 2215 switch (packet_type) 2216 { 2217 case BPT_OTHER_PRIO: 2218 return MAX_BPQ_COUNT; 2219 case BPT_HIGHEST_PRIO: 2220 default: /* clang does not complain about absence of `default'... */ 2221 count = ctl->sc_n_scheduled + ctl->sc_n_in_flight_retx; 2222 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 2223 if (count < cwnd / SC_PACK_SIZE(ctl)) 2224 { 2225 count -= cwnd / SC_PACK_SIZE(ctl); 2226 if (count > MAX_BPQ_COUNT) 2227 return count; 2228 } 2229 return MAX_BPQ_COUNT; 2230 } 2231} 2232 2233 2234static void 2235send_ctl_move_ack (struct lsquic_send_ctl *ctl, struct lsquic_packet_out *dst, 2236 struct lsquic_packet_out *src) 2237{ 2238 assert(dst->po_data_sz == 0); 2239 2240 if (lsquic_packet_out_avail(dst) >= src->po_regen_sz) 2241 { 2242 memcpy(dst->po_data, src->po_data, src->po_regen_sz); 2243 dst->po_data_sz = src->po_regen_sz; 2244 dst->po_regen_sz = src->po_regen_sz; 2245 dst->po_frame_types |= (GQUIC_FRAME_REGEN_MASK & src->po_frame_types); 2246 src->po_frame_types &= ~GQUIC_FRAME_REGEN_MASK; 2247 lsquic_packet_out_chop_regen(src); 2248 } 2249} 2250 2251 2252static lsquic_packet_out_t * 2253send_ctl_get_buffered_packet (lsquic_send_ctl_t *ctl, 2254 enum buf_packet_type packet_type, unsigned need_at_least, 2255 const struct network_path *path, const struct lsquic_stream *stream) 2256{ 2257 struct buf_packet_q *const packet_q = 2258 &ctl->sc_buffered_packets[packet_type]; 2259 struct lsquic_conn *const lconn = ctl->sc_conn_pub->lconn; 2260 lsquic_packet_out_t *packet_out; 2261 enum packno_bits bits; 2262 enum { AA_STEAL, AA_GENERATE, AA_NONE, } ack_action; 2263 2264 packet_out = TAILQ_LAST(&packet_q->bpq_packets, lsquic_packets_tailq); 2265 if (packet_out 2266 && !(packet_out->po_flags & PO_STREAM_END) 2267 && lsquic_packet_out_avail(packet_out) >= need_at_least) 2268 { 2269 return packet_out; 2270 } 2271 2272 if (packet_q->bpq_count >= send_ctl_max_bpq_count(ctl, packet_type)) 2273 return NULL; 2274 2275 if (packet_q->bpq_count == 0) 2276 { 2277 /* If ACK was written to the low-priority queue first, steal it */ 2278 if (packet_q == &ctl->sc_buffered_packets[BPT_HIGHEST_PRIO] 2279 && !TAILQ_EMPTY(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets) 2280 && (TAILQ_FIRST(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets) 2281 ->po_frame_types & QUIC_FTBIT_ACK)) 2282 { 2283 LSQ_DEBUG("steal ACK frame from low-priority buffered queue"); 2284 ack_action = AA_STEAL; 2285 bits = ctl->sc_max_packno_bits; 2286 } 2287 /* If ACK can be generated, write it to the first buffered packet. */ 2288 else if (lconn->cn_if->ci_can_write_ack(lconn)) 2289 { 2290 LSQ_DEBUG("generate ACK frame for first buffered packet in " 2291 "queue #%u", packet_type); 2292 ack_action = AA_GENERATE; 2293 /* Packet length is set to the largest possible size to guarantee 2294 * that buffered packet with the ACK will not need to be split. 2295 */ 2296 bits = ctl->sc_max_packno_bits; 2297 } 2298 else 2299 goto no_ack_action; 2300 } 2301 else 2302 { 2303 no_ack_action: 2304 ack_action = AA_NONE; 2305 bits = lsquic_send_ctl_guess_packno_bits(ctl); 2306 } 2307 2308 packet_out = send_ctl_allocate_packet(ctl, bits, need_at_least, PNS_APP, 2309 path); 2310 if (!packet_out) 2311 return NULL; 2312 2313 switch (ack_action) 2314 { 2315 case AA_STEAL: 2316 send_ctl_move_ack(ctl, packet_out, 2317 TAILQ_FIRST(&ctl->sc_buffered_packets[BPT_OTHER_PRIO].bpq_packets)); 2318 break; 2319 case AA_GENERATE: 2320 lconn->cn_if->ci_write_ack(lconn, packet_out); 2321 break; 2322 case AA_NONE: 2323 break; 2324 } 2325 2326 TAILQ_INSERT_TAIL(&packet_q->bpq_packets, packet_out, po_next); 2327 ++packet_q->bpq_count; 2328 LSQ_DEBUG("Add new packet to buffered queue #%u; count: %u", 2329 packet_type, packet_q->bpq_count); 2330 return packet_out; 2331} 2332 2333 2334lsquic_packet_out_t * 2335lsquic_send_ctl_get_packet_for_stream (lsquic_send_ctl_t *ctl, 2336 unsigned need_at_least, const struct network_path *path, 2337 const struct lsquic_stream *stream) 2338{ 2339 enum buf_packet_type packet_type; 2340 2341 if (lsquic_send_ctl_schedule_stream_packets_immediately(ctl)) 2342 return lsquic_send_ctl_get_writeable_packet(ctl, PNS_APP, 2343 need_at_least, path, 0, NULL); 2344 else 2345 { 2346 packet_type = send_ctl_lookup_bpt(ctl, stream); 2347 return send_ctl_get_buffered_packet(ctl, packet_type, need_at_least, 2348 path, stream); 2349 } 2350} 2351 2352 2353#ifdef NDEBUG 2354static 2355#elif __GNUC__ 2356__attribute__((weak)) 2357#endif 2358enum packno_bits 2359lsquic_send_ctl_calc_packno_bits (lsquic_send_ctl_t *ctl) 2360{ 2361 lsquic_packno_t smallest_unacked; 2362 enum packno_bits bits; 2363 unsigned n_in_flight; 2364 unsigned long cwnd; 2365 const struct parse_funcs *pf; 2366 2367 pf = ctl->sc_conn_pub->lconn->cn_pf; 2368 2369 smallest_unacked = lsquic_send_ctl_smallest_unacked(ctl); 2370 cwnd = ctl->sc_ci->cci_get_cwnd(CGP(ctl)); 2371 n_in_flight = cwnd / SC_PACK_SIZE(ctl); 2372 bits = pf->pf_calc_packno_bits(ctl->sc_cur_packno + 1, smallest_unacked, 2373 n_in_flight); 2374 if (bits <= ctl->sc_max_packno_bits) 2375 return bits; 2376 else 2377 return ctl->sc_max_packno_bits; 2378} 2379 2380 2381enum packno_bits 2382lsquic_send_ctl_packno_bits (lsquic_send_ctl_t *ctl) 2383{ 2384 2385 if (lsquic_send_ctl_schedule_stream_packets_immediately(ctl)) 2386 return lsquic_send_ctl_calc_packno_bits(ctl); 2387 else 2388 return lsquic_send_ctl_guess_packno_bits(ctl); 2389} 2390 2391 2392static int 2393split_buffered_packet (lsquic_send_ctl_t *ctl, 2394 enum buf_packet_type packet_type, lsquic_packet_out_t *packet_out, 2395 enum packno_bits bits, unsigned excess_bytes) 2396{ 2397 struct buf_packet_q *const packet_q = 2398 &ctl->sc_buffered_packets[packet_type]; 2399 lsquic_packet_out_t *new_packet_out; 2400 2401 assert(TAILQ_FIRST(&packet_q->bpq_packets) == packet_out); 2402 2403 new_packet_out = send_ctl_allocate_packet(ctl, bits, 0, 2404 lsquic_packet_out_pns(packet_out), packet_out->po_path); 2405 if (!new_packet_out) 2406 return -1; 2407 2408 if (0 == lsquic_packet_out_split_in_two(&ctl->sc_enpub->enp_mm, packet_out, 2409 new_packet_out, ctl->sc_conn_pub->lconn->cn_pf, excess_bytes)) 2410 { 2411 lsquic_packet_out_set_packno_bits(packet_out, bits); 2412 TAILQ_INSERT_AFTER(&packet_q->bpq_packets, packet_out, new_packet_out, 2413 po_next); 2414 ++packet_q->bpq_count; 2415 LSQ_DEBUG("Add split packet to buffered queue #%u; count: %u", 2416 packet_type, packet_q->bpq_count); 2417 return 0; 2418 } 2419 else 2420 { 2421 send_ctl_destroy_packet(ctl, packet_out); 2422 return -1; 2423 } 2424} 2425 2426 2427int 2428lsquic_send_ctl_schedule_buffered (lsquic_send_ctl_t *ctl, 2429 enum buf_packet_type packet_type) 2430{ 2431 struct buf_packet_q *const packet_q = 2432 &ctl->sc_buffered_packets[packet_type]; 2433 const struct parse_funcs *const pf = ctl->sc_conn_pub->lconn->cn_pf; 2434 lsquic_packet_out_t *packet_out; 2435 unsigned used, excess; 2436 2437 assert(lsquic_send_ctl_schedule_stream_packets_immediately(ctl)); 2438 const enum packno_bits bits = lsquic_send_ctl_calc_packno_bits(ctl); 2439 const unsigned need = pf->pf_packno_bits2len(bits); 2440 2441 while ((packet_out = TAILQ_FIRST(&packet_q->bpq_packets)) && 2442 lsquic_send_ctl_can_send(ctl)) 2443 { 2444 if ((packet_out->po_frame_types & QUIC_FTBIT_ACK) 2445 && packet_out->po_ack2ed < ctl->sc_largest_acked) 2446 { 2447 /* Chrome watches for a decrease in the value of the Largest 2448 * Observed field of the ACK frame and marks it as an error: 2449 * this is why we have to send out ACK in the order they were 2450 * generated. 2451 */ 2452 LSQ_DEBUG("Remove out-of-order ACK from buffered packet"); 2453 lsquic_packet_out_chop_regen(packet_out); 2454 if (packet_out->po_data_sz == 0) 2455 { 2456 LSQ_DEBUG("Dropping now-empty buffered packet"); 2457 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 2458 --packet_q->bpq_count; 2459 send_ctl_destroy_packet(ctl, packet_out); 2460 continue; 2461 } 2462 } 2463 if (bits != lsquic_packet_out_packno_bits(packet_out)) 2464 { 2465 used = pf->pf_packno_bits2len( 2466 lsquic_packet_out_packno_bits(packet_out)); 2467 if (need > used 2468 && need - used > lsquic_packet_out_avail(packet_out)) 2469 { 2470 excess = need - used - lsquic_packet_out_avail(packet_out); 2471 if (0 != split_buffered_packet(ctl, packet_type, 2472 packet_out, bits, excess)) 2473 { 2474 return -1; 2475 } 2476 } 2477 } 2478 TAILQ_REMOVE(&packet_q->bpq_packets, packet_out, po_next); 2479 --packet_q->bpq_count; 2480 packet_out->po_packno = send_ctl_next_packno(ctl); 2481 LSQ_DEBUG("Remove packet from buffered queue #%u; count: %u. " 2482 "It becomes packet %"PRIu64, packet_type, packet_q->bpq_count, 2483 packet_out->po_packno); 2484 lsquic_send_ctl_scheduled_one(ctl, packet_out); 2485 } 2486 2487 return 0; 2488} 2489 2490 2491int 2492lsquic_send_ctl_turn_on_fin (struct lsquic_send_ctl *ctl, 2493 const struct lsquic_stream *stream) 2494{ 2495 enum buf_packet_type packet_type; 2496 struct buf_packet_q *packet_q; 2497 lsquic_packet_out_t *packet_out; 2498 const struct parse_funcs *pf; 2499 2500 pf = ctl->sc_conn_pub->lconn->cn_pf; 2501 packet_type = send_ctl_lookup_bpt(ctl, stream); 2502 packet_q = &ctl->sc_buffered_packets[packet_type]; 2503 2504 TAILQ_FOREACH_REVERSE(packet_out, &packet_q->bpq_packets, 2505 lsquic_packets_tailq, po_next) 2506 if (0 == lsquic_packet_out_turn_on_fin(packet_out, pf, stream)) 2507 return 0; 2508 2509 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2510 if (0 == packet_out->po_sent 2511 && 0 == lsquic_packet_out_turn_on_fin(packet_out, pf, stream)) 2512 { 2513 return 0; 2514 } 2515 2516 return -1; 2517} 2518 2519 2520size_t 2521lsquic_send_ctl_mem_used (const struct lsquic_send_ctl *ctl) 2522{ 2523 const lsquic_packet_out_t *packet_out; 2524 unsigned n; 2525 size_t size; 2526 const struct lsquic_packets_tailq queues[] = { 2527 ctl->sc_scheduled_packets, 2528 ctl->sc_unacked_packets[PNS_INIT], 2529 ctl->sc_unacked_packets[PNS_HSK], 2530 ctl->sc_unacked_packets[PNS_APP], 2531 ctl->sc_lost_packets, 2532 ctl->sc_buffered_packets[0].bpq_packets, 2533 ctl->sc_buffered_packets[1].bpq_packets, 2534 }; 2535 2536 size = sizeof(*ctl); 2537 2538 for (n = 0; n < sizeof(queues) / sizeof(queues[0]); ++n) 2539 TAILQ_FOREACH(packet_out, &queues[n], po_next) 2540 size += lsquic_packet_out_mem_used(packet_out); 2541 2542 return size; 2543} 2544 2545 2546void 2547lsquic_send_ctl_verneg_done (struct lsquic_send_ctl *ctl) 2548{ 2549 ctl->sc_max_packno_bits = PACKNO_BITS_3; 2550 LSQ_DEBUG("version negotiation done (%s): max packno bits: %u", 2551 lsquic_ver2str[ ctl->sc_conn_pub->lconn->cn_version ], 2552 ctl->sc_max_packno_bits); 2553} 2554 2555 2556int 2557lsquic_send_ctl_retry (struct lsquic_send_ctl *ctl, 2558 const unsigned char *token, size_t token_sz, int cidlen_diff) 2559{ 2560 struct lsquic_packet_out *packet_out; 2561 2562 if (token_sz >= 1ull << (sizeof(packet_out->po_token_len) * 8)) 2563 { 2564 LSQ_WARN("token size %zu is too long", token_sz); 2565 return -1; 2566 } 2567 2568 send_ctl_expire(ctl, PNS_INIT, EXFI_ALL); 2569 packet_out = TAILQ_FIRST(&ctl->sc_lost_packets); 2570 if (!(packet_out && HETY_INITIAL == packet_out->po_header_type)) 2571 { 2572 LSQ_INFO("cannot find initial packet to add token to"); 2573 return -1; 2574 } 2575 2576 ++ctl->sc_retry_count; 2577 if (ctl->sc_retry_count > 3) 2578 { 2579 LSQ_INFO("failing connection after %u retries", ctl->sc_retry_count); 2580 return -1; 2581 } 2582 2583 if (0 != lsquic_send_ctl_set_token(ctl, token, token_sz)) 2584 return -1; 2585 2586 if (packet_out->po_nonce) 2587 free(packet_out->po_nonce); 2588 2589 packet_out->po_nonce = malloc(token_sz); 2590 if (!packet_out->po_nonce) 2591 { 2592 LSQ_WARN("%s: malloc failed", __func__); 2593 return -1; 2594 } 2595 memcpy(packet_out->po_nonce, token, token_sz); 2596 packet_out->po_flags |= PO_NONCE; 2597 packet_out->po_token_len = token_sz; 2598 packet_out->po_data_sz -= token_sz; 2599 if (cidlen_diff > 0) 2600 packet_out->po_data_sz += cidlen_diff; 2601 else if (cidlen_diff < 0) 2602 packet_out->po_data_sz -= -cidlen_diff; 2603 return 0; 2604} 2605 2606 2607int 2608lsquic_send_ctl_set_token (struct lsquic_send_ctl *ctl, 2609 const unsigned char *token, size_t token_sz) 2610{ 2611 unsigned char *copy; 2612 2613 if (token_sz > 1 << 2614 (sizeof(((struct lsquic_packet_out *)0)->po_token_len) * 8)) 2615 { 2616 errno = EINVAL; 2617 return -1; 2618 } 2619 2620 copy = malloc(token_sz); 2621 if (!copy) 2622 return -1; 2623 memcpy(copy, token, token_sz); 2624 free(ctl->sc_token); 2625 ctl->sc_token = copy; 2626 ctl->sc_token_sz = token_sz; 2627 LSQ_DEBUG("set token"); 2628 return 0; 2629} 2630 2631 2632void 2633lsquic_send_ctl_empty_pns (struct lsquic_send_ctl *ctl, enum packnum_space pns) 2634{ 2635 lsquic_packet_out_t *packet_out, *next; 2636 unsigned count, packet_sz; 2637 struct lsquic_packets_tailq *const *q; 2638 struct lsquic_packets_tailq *const queues[] = { 2639 &ctl->sc_lost_packets, 2640 &ctl->sc_buffered_packets[0].bpq_packets, 2641 &ctl->sc_buffered_packets[1].bpq_packets, 2642 }; 2643 2644 /* Don't bother with chain destruction, as all chains members are always 2645 * within the same packet number space 2646 */ 2647 2648 count = 0; 2649 for (packet_out = TAILQ_FIRST(&ctl->sc_scheduled_packets); packet_out; 2650 packet_out = next) 2651 { 2652 next = TAILQ_NEXT(packet_out, po_next); 2653 if (pns == lsquic_packet_out_pns(packet_out)) 2654 { 2655 send_ctl_maybe_renumber_sched_to_right(ctl, packet_out); 2656 send_ctl_sched_remove(ctl, packet_out); 2657 send_ctl_destroy_packet(ctl, packet_out); 2658 ++count; 2659 } 2660 } 2661 2662 for (packet_out = TAILQ_FIRST(&ctl->sc_unacked_packets[pns]); packet_out; 2663 packet_out = next) 2664 { 2665 next = TAILQ_NEXT(packet_out, po_next); 2666 if (packet_out->po_flags & PO_LOSS_REC) 2667 TAILQ_REMOVE(&ctl->sc_unacked_packets[pns], packet_out, po_next); 2668 else 2669 { 2670 packet_sz = packet_out_sent_sz(packet_out); 2671 send_ctl_unacked_remove(ctl, packet_out, packet_sz); 2672 lsquic_packet_out_ack_streams(packet_out); 2673 } 2674 send_ctl_destroy_packet(ctl, packet_out); 2675 ++count; 2676 } 2677 2678 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 2679 for (packet_out = TAILQ_FIRST(*q); packet_out; packet_out = next) 2680 { 2681 next = TAILQ_NEXT(packet_out, po_next); 2682 if (pns == lsquic_packet_out_pns(packet_out)) 2683 { 2684 TAILQ_REMOVE(*q, packet_out, po_next); 2685 send_ctl_destroy_packet(ctl, packet_out); 2686 ++count; 2687 } 2688 } 2689 2690 lsquic_alarmset_unset(ctl->sc_alset, AL_RETX_INIT + pns); 2691 2692 LSQ_DEBUG("emptied %s, destroyed %u packet%.*s", lsquic_pns2str[pns], 2693 count, count != 1, "s"); 2694} 2695 2696 2697void 2698lsquic_send_ctl_repath (struct lsquic_send_ctl *ctl, struct network_path *old, 2699 struct network_path *new) 2700{ 2701 struct lsquic_packet_out *packet_out; 2702 unsigned count; 2703 struct lsquic_packets_tailq *const *q; 2704 struct lsquic_packets_tailq *const queues[] = { 2705 &ctl->sc_scheduled_packets, 2706 &ctl->sc_unacked_packets[PNS_INIT], 2707 &ctl->sc_unacked_packets[PNS_HSK], 2708 &ctl->sc_unacked_packets[PNS_APP], 2709 &ctl->sc_lost_packets, 2710 &ctl->sc_buffered_packets[0].bpq_packets, 2711 &ctl->sc_buffered_packets[1].bpq_packets, 2712 }; 2713 2714 assert(ctl->sc_flags & SC_IETF); 2715 2716 count = 0; 2717 for (q = queues; q < queues + sizeof(queues) / sizeof(queues[0]); ++q) 2718 TAILQ_FOREACH(packet_out, *q, po_next) 2719 if (packet_out->po_path == old) 2720 { 2721 ++count; 2722 packet_out->po_path = new; 2723 if (packet_out->po_flags & PO_ENCRYPTED) 2724 send_ctl_return_enc_data(ctl, packet_out); 2725 } 2726 2727 LSQ_DEBUG("repathed %u packet%.*s", count, count != 1, "s"); 2728} 2729 2730 2731void 2732lsquic_send_ctl_return_enc_data (struct lsquic_send_ctl *ctl) 2733{ 2734 struct lsquic_packet_out *packet_out; 2735 2736 assert(!(ctl->sc_flags & SC_IETF)); 2737 2738 TAILQ_FOREACH(packet_out, &ctl->sc_scheduled_packets, po_next) 2739 if (packet_out->po_flags & PO_ENCRYPTED) 2740 send_ctl_return_enc_data(ctl, packet_out); 2741} 2742