1/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc. See LICENSE. */ 2/* 3 * lsquic_packet_out.c 4 */ 5 6#include <assert.h> 7#include <errno.h> 8#include <stdlib.h> 9#include <string.h> 10#include <sys/queue.h> 11 12#include "lsquic.h" 13#include "lsquic_int_types.h" 14#include "lsquic_malo.h" 15#include "lsquic_mm.h" 16#include "lsquic_engine_public.h" 17#include "lsquic_packet_common.h" 18#include "lsquic_packet_gquic.h" 19#include "lsquic_packet_in.h" 20#include "lsquic_packet_out.h" 21#include "lsquic_parse.h" 22#include "lsquic_sfcw.h" 23#include "lsquic_varint.h" 24#include "lsquic_hq.h" 25#include "lsquic_hash.h" 26#include "lsquic_stream.h" 27#include "lsquic_logger.h" 28#include "lsquic_ev_log.h" 29#include "lsquic_conn.h" 30#include "lsquic_enc_sess.h" 31 32typedef char _stream_rec_arr_is_at_most_64bytes[ 33 (sizeof(struct frame_rec_arr) <= 64)? 1: - 1]; 34 35static struct frame_rec * 36frec_one_pofi_first (struct packet_out_frec_iter *pofi, 37 struct lsquic_packet_out *packet_out) 38{ 39 if (packet_out->po_frecs.one.fe_frame_type) 40 return &packet_out->po_frecs.one; 41 else 42 return NULL; 43} 44 45 46static struct frame_rec * 47frec_one_pofi_next (struct packet_out_frec_iter *pofi) 48{ 49 return NULL; 50} 51 52 53static struct frame_rec * 54frec_arr_pofi_next (struct packet_out_frec_iter *pofi) 55{ 56 while (pofi->cur_frec_arr) 57 { 58 for (; pofi->frec_idx < sizeof(pofi->cur_frec_arr->frecs) / sizeof(pofi->cur_frec_arr->frecs[0]); 59 ++pofi->frec_idx) 60 { 61 if (pofi->cur_frec_arr->frecs[ pofi->frec_idx ].fe_frame_type) 62 return &pofi->cur_frec_arr->frecs[ pofi->frec_idx++ ]; 63 } 64 pofi->cur_frec_arr = TAILQ_NEXT(pofi->cur_frec_arr, next_stream_rec_arr); 65 pofi->frec_idx = 0; 66 } 67 return NULL; 68} 69 70 71static struct frame_rec * 72frec_arr_pofi_first (struct packet_out_frec_iter *pofi, 73 struct lsquic_packet_out *packet_out) 74{ 75 pofi->packet_out = packet_out; 76 pofi->cur_frec_arr = TAILQ_FIRST(&packet_out->po_frecs.arr); 77 pofi->frec_idx = 0; 78 return frec_arr_pofi_next(pofi); 79} 80 81 82static struct frame_rec * (* const pofi_firsts[]) 83 (struct packet_out_frec_iter *, struct lsquic_packet_out *) = 84{ 85 frec_one_pofi_first, 86 frec_arr_pofi_first, 87}; 88 89 90static struct frame_rec * (* const pofi_nexts[]) 91 (struct packet_out_frec_iter *pofi) = 92{ 93 frec_one_pofi_next, 94 frec_arr_pofi_next, 95}; 96 97 98struct frame_rec * 99lsquic_pofi_first (struct packet_out_frec_iter *pofi, 100 lsquic_packet_out_t *packet_out) 101{ 102 pofi->impl_idx = !!(packet_out->po_flags & PO_FREC_ARR); 103 return pofi_firsts[pofi->impl_idx](pofi, packet_out); 104} 105 106 107struct frame_rec * 108lsquic_pofi_next (struct packet_out_frec_iter *pofi) 109{ 110 return pofi_nexts[pofi->impl_idx](pofi); 111} 112 113 114/* 115 * Assumption: frames are added to the packet_out in order of their placement 116 * in packet_out->po_data. There is no assertion to guard for for this. 117 */ 118int 119lsquic_packet_out_add_frame (lsquic_packet_out_t *packet_out, 120 struct lsquic_mm *mm, 121 uintptr_t data, 122 enum quic_frame_type frame_type, 123 unsigned short off, unsigned short len) 124{ 125 struct frame_rec_arr *frec_arr; 126 int last_taken; 127 unsigned i; 128 129 if (!(packet_out->po_flags & PO_FREC_ARR)) 130 { 131 if (!frec_taken(&packet_out->po_frecs.one)) 132 { 133 packet_out->po_frecs.one.fe_frame_type = frame_type; 134 packet_out->po_frecs.one.fe_u.data = data; 135 packet_out->po_frecs.one.fe_off = off; 136 packet_out->po_frecs.one.fe_len = len; 137 return 0; /* Insert in first slot */ 138 } 139 frec_arr = lsquic_malo_get(mm->malo.frame_rec_arr); 140 if (!frec_arr) 141 return -1; 142 memset(frec_arr, 0, sizeof(*frec_arr)); 143 frec_arr->frecs[0] = packet_out->po_frecs.one; 144 TAILQ_INIT(&packet_out->po_frecs.arr); 145 TAILQ_INSERT_TAIL(&packet_out->po_frecs.arr, frec_arr, 146 next_stream_rec_arr); 147 packet_out->po_flags |= PO_FREC_ARR; 148 i = 1; 149 goto set_elem; 150 } 151 152 /* New records go at the very end: */ 153 frec_arr = TAILQ_LAST(&packet_out->po_frecs.arr, frame_rec_arr_tailq); 154 last_taken = -1; 155 for (i = 0; i < sizeof(frec_arr->frecs) / sizeof(frec_arr->frecs[0]); ++i) 156 if (frec_taken(&frec_arr->frecs[i])) 157 last_taken = i; 158 159 i = last_taken + 1; 160 if (i < sizeof(frec_arr->frecs) / sizeof(frec_arr->frecs[0])) 161 { 162 set_elem: 163 frec_arr->frecs[i].fe_frame_type = frame_type; 164 frec_arr->frecs[i].fe_u.data = data; 165 frec_arr->frecs[i].fe_off = off; 166 frec_arr->frecs[i].fe_len = len; 167 return 0; /* Insert in existing frec */ 168 } 169 170 frec_arr = lsquic_malo_get(mm->malo.frame_rec_arr); 171 if (!frec_arr) 172 return -1; 173 174 memset(frec_arr, 0, sizeof(*frec_arr)); 175 frec_arr->frecs[0].fe_frame_type = frame_type; 176 frec_arr->frecs[0].fe_u.data = data; 177 frec_arr->frecs[0].fe_off = off; 178 frec_arr->frecs[0].fe_len = len; 179 TAILQ_INSERT_TAIL(&packet_out->po_frecs.arr, frec_arr, next_stream_rec_arr); 180 return 0; /* Insert in new frec */ 181} 182 183 184int 185lsquic_packet_out_add_stream (struct lsquic_packet_out *packet_out, 186 struct lsquic_mm *mm, struct lsquic_stream *new_stream, 187 enum quic_frame_type frame_type, unsigned short off, unsigned short len) 188{ 189 assert(!(new_stream->stream_flags & STREAM_FINISHED)); 190 assert((1 << frame_type) 191 & (QUIC_FTBIT_STREAM|QUIC_FTBIT_CRYPTO|QUIC_FTBIT_RST_STREAM)); 192 if (0 == lsquic_packet_out_add_frame(packet_out, mm, 193 (uintptr_t) new_stream, frame_type, off, len)) 194 { 195 ++new_stream->n_unacked; 196 return 0; 197 } 198 else 199 return -1; 200} 201 202 203lsquic_packet_out_t * 204lsquic_packet_out_new (struct lsquic_mm *mm, struct malo *malo, int use_cid, 205 const struct lsquic_conn *lconn, enum packno_bits bits, 206 const lsquic_ver_tag_t *ver_tag, const unsigned char *nonce, 207 const struct network_path *path, enum header_type header_type) 208{ 209 lsquic_packet_out_t *packet_out; 210 enum packet_out_flags flags; 211 size_t header_size, tag_len, max_size; 212 213 flags = bits << POBIT_SHIFT; 214 if (ver_tag) 215 flags |= PO_VERSION; 216 if (nonce) 217 flags |= PO_NONCE; 218 if (use_cid) 219 flags |= PO_CONN_ID; 220 if ((lconn->cn_flags & (LSCONN_MINI|LSCONN_HANDSHAKE_DONE)) 221 != LSCONN_HANDSHAKE_DONE) 222 flags |= PO_LONGHEAD; 223 224 header_size = lconn->cn_pf->pf_packout_max_header_size(lconn, flags, 225 path->np_dcid.len, header_type); 226 tag_len = lconn->cn_esf_c->esf_tag_len; 227 max_size = path->np_pack_size; 228 if (header_size + tag_len >= max_size) 229 { 230 errno = EINVAL; 231 return NULL; 232 } 233 234 packet_out = lsquic_mm_get_packet_out(mm, malo, max_size - header_size 235 - tag_len); 236 if (!packet_out) 237 return NULL; 238 239 packet_out->po_flags = flags; 240 if ((1 << lconn->cn_version) & LSQUIC_GQUIC_HEADER_VERSIONS) 241 packet_out->po_lflags = POL_GQUIC; 242 if (ver_tag) 243 packet_out->po_ver_tag = *ver_tag; 244 if (nonce) 245 { 246 /* Nonces are allocated for a very small number of packets. This 247 * memory is too expensive to carry in every packet. 248 */ 249 packet_out->po_nonce = malloc(32); 250 if (!packet_out->po_nonce) 251 { 252 lsquic_mm_put_packet_out(mm, packet_out); 253 return NULL; 254 } 255 memcpy(packet_out->po_nonce, nonce, 32); 256 } 257 if (flags & PO_LONGHEAD) 258 { 259 if (lconn->cn_version == LSQVER_050) 260 { 261 if (lconn->cn_flags & (LSCONN_SERVER|LSCONN_HANDSHAKE_DONE)) 262 packet_out->po_header_type = HETY_0RTT; 263 else 264 packet_out->po_header_type = HETY_INITIAL; 265 } 266 else 267 packet_out->po_header_type = HETY_HANDSHAKE; 268 } 269 packet_out->po_path = path; 270 271 return packet_out; 272} 273 274 275void 276lsquic_packet_out_destroy (lsquic_packet_out_t *packet_out, 277 struct lsquic_engine_public *enpub, void *peer_ctx) 278{ 279 if (packet_out->po_flags & PO_FREC_ARR) 280 { 281 struct frame_rec_arr *frec_arr, *next; 282 for (frec_arr = TAILQ_FIRST(&packet_out->po_frecs.arr); 283 frec_arr; frec_arr = next) 284 { 285 next = TAILQ_NEXT(frec_arr, next_stream_rec_arr); 286 lsquic_malo_put(frec_arr); 287 } 288 } 289 if (packet_out->po_flags & PO_ENCRYPTED) 290 enpub->enp_pmi->pmi_release(enpub->enp_pmi_ctx, peer_ctx, 291 packet_out->po_enc_data, lsquic_packet_out_ipv6(packet_out)); 292 if (packet_out->po_nonce) 293 free(packet_out->po_nonce); 294 if (packet_out->po_bwp_state) 295 lsquic_malo_put(packet_out->po_bwp_state); 296 lsquic_mm_put_packet_out(&enpub->enp_mm, packet_out); 297} 298 299 300/* If `stream_id' is UINT64_MAX, stream frames from all reset streams are elided. 301 * Otherwise, elision is limited to the specified stream. 302 */ 303unsigned 304lsquic_packet_out_elide_reset_stream_frames (lsquic_packet_out_t *packet_out, 305 lsquic_stream_id_t stream_id) 306{ 307 struct packet_out_frec_iter pofi; 308 struct frame_rec *frec; 309 unsigned short adj = 0; 310 int n_stream_frames = 0, n_elided = 0; 311 int victim; 312 313 for (frec = lsquic_pofi_first(&pofi, packet_out); frec; 314 frec = lsquic_pofi_next(&pofi)) 315 { 316 /* Offsets of all frame records should be adjusted */ 317 frec->fe_off -= adj; 318 319 if (frec->fe_frame_type == QUIC_FRAME_STREAM) 320 { 321 ++n_stream_frames; 322 323 if (stream_id != UINT64_MAX) 324 { 325 victim = frec->fe_stream->id == stream_id; 326 if (victim) 327 { 328 assert(lsquic_stream_is_write_reset(frec->fe_stream)); 329 } 330 } 331 else 332 victim = lsquic_stream_is_write_reset(frec->fe_stream); 333 334 if (victim) 335 { 336 ++n_elided; 337 338 /* Move the data and adjust sizes */ 339 adj += frec->fe_len; 340 memmove(packet_out->po_data + frec->fe_off, 341 packet_out->po_data + frec->fe_off + frec->fe_len, 342 packet_out->po_data_sz - frec->fe_off - frec->fe_len); 343 packet_out->po_data_sz -= frec->fe_len; 344 345 lsquic_stream_acked(frec->fe_stream, frec->fe_frame_type); 346 frec->fe_frame_type = 0; 347 } 348 } 349 } 350 351 assert(n_stream_frames); 352 if (n_elided == n_stream_frames) 353 { 354 packet_out->po_frame_types &= ~(1 << QUIC_FRAME_STREAM); 355 packet_out->po_flags &= ~PO_STREAM_END; 356 } 357 358 return adj; 359} 360 361 362void 363lsquic_packet_out_chop_regen (lsquic_packet_out_t *packet_out) 364{ 365 struct packet_out_frec_iter pofi; 366 struct frame_rec *frec; 367 unsigned short adj; 368 369 adj = 0; 370 for (frec = lsquic_pofi_first(&pofi, packet_out); frec; 371 frec = lsquic_pofi_next(&pofi)) 372 { 373 frec->fe_off -= adj; 374 if (BQUIC_FRAME_REGEN_MASK & (1 << frec->fe_frame_type)) 375 { 376 adj += frec->fe_len; 377 memmove(packet_out->po_data + frec->fe_off, 378 packet_out->po_data + frec->fe_off + frec->fe_len, 379 packet_out->po_data_sz - frec->fe_off - frec->fe_len); 380 packet_out->po_data_sz -= frec->fe_len; 381 frec->fe_frame_type = 0; 382 } 383 } 384 385 assert(adj); /* Otherwise why are we called? */ 386 packet_out->po_regen_sz = 0; 387 packet_out->po_frame_types &= ~BQUIC_FRAME_REGEN_MASK; 388} 389 390 391void 392lsquic_packet_out_ack_streams (lsquic_packet_out_t *packet_out) 393{ 394 struct packet_out_frec_iter pofi; 395 struct frame_rec *frec; 396 for (frec = lsquic_pofi_first(&pofi, packet_out); frec; 397 frec = lsquic_pofi_next(&pofi)) 398 if ((1 << frec->fe_frame_type) 399 & (QUIC_FTBIT_STREAM|QUIC_FTBIT_CRYPTO|QUIC_FTBIT_RST_STREAM)) 400 lsquic_stream_acked(frec->fe_stream, frec->fe_frame_type); 401} 402 403 404void 405lsquic_packet_out_zero_pad (lsquic_packet_out_t *packet_out) 406{ 407 if (packet_out->po_n_alloc > packet_out->po_data_sz) 408 { 409 memset(packet_out->po_data + packet_out->po_data_sz, 0, 410 packet_out->po_n_alloc - packet_out->po_data_sz); 411 packet_out->po_data_sz = packet_out->po_n_alloc; 412 packet_out->po_frame_types |= 1 << QUIC_FRAME_PADDING; 413 } 414} 415 416 417size_t 418lsquic_packet_out_mem_used (const struct lsquic_packet_out *packet_out) 419{ 420 const struct frame_rec_arr *frec_arr; 421 size_t size; 422 423 size = 0; /* The struct is allocated using malo */ 424 if (packet_out->po_enc_data) 425 size += packet_out->po_enc_data_sz; 426 if (packet_out->po_data) 427 size += packet_out->po_n_alloc; 428 if (packet_out->po_nonce) 429 size += 32; 430 431 if (packet_out->po_flags & PO_FREC_ARR) 432 TAILQ_FOREACH(frec_arr, &packet_out->po_frecs.arr, next_stream_rec_arr) 433 size += sizeof(*frec_arr); 434 435 return size; 436} 437 438 439int 440lsquic_packet_out_turn_on_fin (struct lsquic_packet_out *packet_out, 441 const struct parse_funcs *pf, 442 const struct lsquic_stream *stream) 443{ 444 struct packet_out_frec_iter pofi; 445 const struct frame_rec *frec; 446 struct stream_frame stream_frame; 447 uint64_t last_offset; 448 int len; 449 450 for (frec = lsquic_pofi_first(&pofi, packet_out); frec; 451 frec = lsquic_pofi_next(&pofi)) 452 if (frec->fe_frame_type == QUIC_FRAME_STREAM 453 && frec->fe_stream == stream) 454 { 455 len = pf->pf_parse_stream_frame(packet_out->po_data + frec->fe_off, 456 frec->fe_len, &stream_frame); 457 458 // Got a corner case because of short write, df_size == 0 && df_fin == 0 459 // It is OK to just turn on the fin bit. 460 assert(len >= 0 || frec->fe_len == 5); 461 if (len < 0 && stream_frame.data_frame.df_size != 0) 462 return -1; 463 last_offset = stream_frame.data_frame.df_offset 464 + stream_frame.data_frame.df_size; 465 if (last_offset == stream->tosend_off) 466 { 467 pf->pf_turn_on_fin(packet_out->po_data + frec->fe_off); 468 EV_LOG_UPDATED_STREAM_FRAME( 469 lsquic_conn_log_cid(lsquic_stream_conn(stream)), 470 pf, packet_out->po_data + frec->fe_off, frec->fe_len); 471 return 0; 472 } 473 } 474 475 return -1; 476} 477 478 479static unsigned 480offset_to_dcid (const struct lsquic_packet_out *packet_out) 481{ 482 if (packet_out->po_header_type == HETY_NOT_SET) 483 return 1; 484 else 485 { 486 assert(!(packet_out->po_lflags & POL_GQUIC)); 487 return 6; 488 } 489} 490 491 492/* Return true if DCIDs of the two packets are equal, false otherwise. */ 493int 494lsquic_packet_out_equal_dcids (const struct lsquic_packet_out *a, 495 const struct lsquic_packet_out *b) 496{ 497 const int a_encrypted = !!(a->po_flags & PO_ENCRYPTED); 498 const int b_encrypted = !!(b->po_flags & PO_ENCRYPTED); 499 const unsigned char *dcids[2]; 500 size_t sizes[2]; 501 502 switch ((a_encrypted << 1) | b_encrypted) 503 { 504 case (0 << 1) | 0: 505 return a->po_path == b->po_path; 506 case (0 << 1) | 1: 507 dcids[0] = a->po_path->np_dcid.idbuf; 508 sizes[0] = a->po_path->np_dcid.len; 509 dcids[1] = b->po_enc_data + offset_to_dcid(b); 510 sizes[1] = b->po_dcid_len; 511 break; 512 case (1 << 1) | 0: 513 dcids[0] = a->po_enc_data + offset_to_dcid(a); 514 sizes[0] = a->po_dcid_len; 515 dcids[1] = b->po_path->np_dcid.idbuf; 516 sizes[1] = b->po_path->np_dcid.len; 517 break; 518 default: 519 dcids[0] = a->po_enc_data + offset_to_dcid(a); 520 sizes[0] = a->po_dcid_len; 521 dcids[1] = b->po_enc_data + offset_to_dcid(b); 522 sizes[1] = b->po_dcid_len; 523 break; 524 } 525 526 return sizes[0] == sizes[1] 527 && 0 == memcmp(dcids[0], dcids[1], sizes[0]); 528} 529 530 531void 532lsquic_packet_out_pad_over (struct lsquic_packet_out *packet_out, 533 enum quic_ft_bit frame_types) 534{ 535 struct packet_out_frec_iter pofi; 536 struct frame_rec *frec; 537 538 for (frec = lsquic_pofi_first(&pofi, packet_out); frec; 539 frec = lsquic_pofi_next(&pofi)) 540 { 541 if ((1 << frec->fe_frame_type) & frame_types) 542 { 543 memset(packet_out->po_data + frec->fe_off, 0, frec->fe_len); 544 frec->fe_frame_type = QUIC_FRAME_PADDING; 545 } 546 } 547 548 packet_out->po_frame_types &= ~frame_types; 549} 550