lsquic_pr_queue.c revision fb73393f
1/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc. See LICENSE. */ 2/* 3 * lsquic_pr_queue.c -- packet request queue. 4 */ 5 6#include <assert.h> 7#include <errno.h> 8#include <inttypes.h> 9#include <netinet/in.h> 10#include <stdlib.h> 11#include <string.h> 12#include <sys/queue.h> 13#include <sys/socket.h> 14 15#include <openssl/aead.h> 16#include <openssl/rand.h> 17 18#include "lsquic.h" 19#include "lsquic_types.h" 20#include "lsquic_int_types.h" 21#include "lsquic_packet_common.h" 22#include "lsquic_packet_gquic.h" 23#include "lsquic_packet_out.h" 24#include "lsquic_packet_in.h" 25#include "lsquic_hash.h" 26#include "lsquic_conn.h" 27#include "lsquic_parse.h" 28#include "lsquic_malo.h" 29#include "lsquic_pr_queue.h" 30#include "lsquic_parse_common.h" 31#include "lsquic_tokgen.h" 32#include "lsquic_version.h" 33#include "lsquic_mm.h" 34#include "lsquic_engine_public.h" 35#include "lsquic_sizes.h" 36#include "lsquic_handshake.h" 37#include "lsquic_xxhash.h" 38#include "lsquic_crand.h" 39 40#define LSQUIC_LOGGER_MODULE LSQLM_PRQ 41#include "lsquic_logger.h" 42 43#define MAX(a, b) ((a) > (b) ? (a) : (b)) 44#define MIN(a, b) ((a) < (b) ? (a) : (b)) 45 46 47static const struct conn_iface evanescent_conn_iface; 48 49 50struct packet_req 51{ 52 struct lsquic_hash_elem pr_hash_el; 53 lsquic_cid_t pr_scid; 54 lsquic_cid_t pr_dcid; 55 enum packet_req_type pr_type; 56 enum pr_flags { 57 PR_GQUIC = 1 << 0, 58 } pr_flags; 59 enum lsquic_version pr_version; 60 unsigned pr_rst_sz; 61 struct network_path pr_path; 62}; 63 64 65struct evanescent_conn 66{ 67 struct lsquic_conn evc_conn; 68 struct packet_req *evc_req; 69 struct pr_queue *evc_queue; 70 struct lsquic_packet_out evc_packet_out; 71 struct conn_cid_elem evc_cces[1]; 72 enum { 73 EVC_DROP = 1 << 0, 74 } evc_flags; 75 unsigned char evc_buf[0]; 76}; 77 78 79/* [draft-ietf-quic-transport-22], Section 17.2.1 */ 80#define IQUIC_VERNEG_SIZE (1 /* Type */ + 4 /* Version (zero tag) */ \ 81 + 1 /* DCIL */ + MAX_CID_LEN + 1 /* SCIL */ + MAX_CID_LEN + \ 82 4 * N_LSQVER) 83 84 85struct pr_queue 86{ 87 TAILQ_HEAD(, lsquic_conn) prq_free_conns, 88 prq_returned_conns; 89 struct malo *prq_reqs_pool; 90 const struct lsquic_engine_public 91 *prq_enpub; 92 struct lsquic_hash *prq_reqs_hash; 93 unsigned prq_max_reqs; 94 unsigned prq_nreqs; 95 unsigned prq_max_conns; 96 unsigned prq_nconns; 97 unsigned prq_verneg_g_sz; /* Size of prq_verneg_g_buf */ 98 unsigned prq_pubres_g_sz; /* Size of prq_pubres_g_buf */ 99 100 /* GQUIC version negotiation and stateless reset packets are generated 101 * once, when the Packet Request Queue is created. For each request, 102 * these buffers are simply copied and the connection ID is replaced. 103 * 104 * Since IETF QUIC uses variable-length connections IDs, we have to 105 * generate packets every time. 106 */ 107 unsigned char prq_pubres_g_buf[GQUIC_RESET_SZ]; 108 unsigned char prq_verneg_g_buf[1 + GQUIC_CID_LEN 109 + N_LSQVER * 4]; 110}; 111 112 113static int 114comp_reqs (const void *s1, const void *s2, size_t n) 115{ 116 const struct packet_req *a, *b; 117 118 a = s1; 119 b = s2; 120 if (a->pr_type == b->pr_type && LSQUIC_CIDS_EQ(&a->pr_dcid, &b->pr_dcid)) 121 return 0; 122 else 123 return -1; 124} 125 126 127static unsigned 128hash_req (const void *p, size_t len, unsigned seed) 129{ 130 const struct packet_req *req; 131 132 req = p; 133 return XXH32(req->pr_dcid.idbuf, req->pr_dcid.len, seed); 134} 135 136 137struct pr_queue * 138lsquic_prq_create (unsigned max_elems, unsigned max_conns, 139 const struct lsquic_engine_public *enpub) 140{ 141 const struct parse_funcs *pf; 142 struct pr_queue *prq; 143 struct malo *malo; 144 struct lsquic_hash *hash; 145 unsigned verneg_g_sz; 146 ssize_t prst_g_sz; 147 int len; 148 149 malo = lsquic_malo_create(sizeof(struct packet_req)); 150 if (!malo) 151 { 152 LSQ_WARN("malo_create failed: %s", strerror(errno)); 153 goto err0; 154 } 155 156 157 hash = lsquic_hash_create_ext(comp_reqs, hash_req); 158 if (!hash) 159 { 160 LSQ_WARN("cannot create hash"); 161 goto err1; 162 } 163 164 prq = malloc(sizeof(*prq)); 165 if (!prq) 166 { 167 LSQ_WARN("malloc failed: %s", strerror(errno)); 168 goto err2; 169 } 170 171 const lsquic_cid_t cid = { .len = 8, }; 172 pf = select_pf_by_ver(LSQVER_043); 173 len = lsquic_gquic_gen_ver_nego_pkt(prq->prq_verneg_g_buf, 174 sizeof(prq->prq_verneg_g_buf), &cid, 175 enpub->enp_settings.es_versions); 176 assert(len > 0); 177 if (len <= 0) 178 { 179 LSQ_ERROR("cannot generate version negotiation packet"); 180 goto err3; 181 } 182 verneg_g_sz = (unsigned) len; 183 184 prst_g_sz = pf->pf_generate_simple_prst(0 /* This is just placeholder */, 185 prq->prq_pubres_g_buf, sizeof(prq->prq_pubres_g_buf)); 186 if (prst_g_sz < 0) 187 { 188 LSQ_ERROR("cannot generate public reset packet"); 189 goto err3; 190 } 191 192 TAILQ_INIT(&prq->prq_free_conns); 193 TAILQ_INIT(&prq->prq_returned_conns); 194 prq->prq_reqs_hash = hash; 195 prq->prq_reqs_pool = malo; 196 prq->prq_max_reqs = max_elems; 197 prq->prq_nreqs = 0; 198 prq->prq_max_conns = max_conns; 199 prq->prq_nconns = 0; 200 prq->prq_verneg_g_sz = verneg_g_sz; 201 prq->prq_pubres_g_sz = (unsigned) prst_g_sz; 202 prq->prq_enpub = enpub; 203 204 LSQ_INFO("initialized queue of size %d", max_elems); 205 206 return prq; 207 208 err3: 209 free(prq); 210 err2: 211 lsquic_hash_destroy(hash); 212 err1: 213 lsquic_malo_destroy(malo); 214 err0: 215 return NULL; 216} 217 218 219void 220lsquic_prq_destroy (struct pr_queue *prq) 221{ 222 struct lsquic_conn *conn; 223 224 LSQ_INFO("destroy"); 225 while ((conn = TAILQ_FIRST(&prq->prq_free_conns))) 226 { 227 TAILQ_REMOVE(&prq->prq_free_conns, conn, cn_next_pr); 228 free(conn); 229 } 230 lsquic_hash_destroy(prq->prq_reqs_hash); 231 lsquic_malo_destroy(prq->prq_reqs_pool); 232 free(prq); 233} 234 235 236static struct packet_req * 237get_req (struct pr_queue *prq) 238{ 239 struct packet_req *req; 240 if (prq->prq_nreqs < prq->prq_max_reqs) 241 { 242 req = lsquic_malo_get(prq->prq_reqs_pool); 243 if (req) 244 ++prq->prq_nreqs; 245 else 246 LSQ_WARN("malo_get failed: %s", strerror(errno)); 247 return req; 248 } 249 else 250 return NULL; 251} 252 253 254static void 255put_req (struct pr_queue *prq, struct packet_req *req) 256{ 257 lsquic_malo_put(req); 258 --prq->prq_nreqs; 259} 260 261 262static int 263lsquic_prq_new_req_ext (struct pr_queue *prq, enum packet_req_type type, 264 unsigned flags, enum lsquic_version version, unsigned short data_sz, 265 const lsquic_cid_t *dcid, const lsquic_cid_t *scid, void *peer_ctx, 266 const struct sockaddr *local_addr, const struct sockaddr *peer_addr) 267{ 268 struct packet_req *req; 269 unsigned max, size, rand; 270 271 if (type == PACKET_REQ_PUBRES && !(flags & PR_GQUIC)) 272 { 273 if (data_sz <= IQUIC_MIN_SRST_SIZE) 274 { 275 LSQ_DEBUGC("not scheduling public reset: incoming packet for CID " 276 "%"CID_FMT" too small: %hu bytes", CID_BITS(dcid), data_sz); 277 return -1; 278 } 279 /* Use a random stateless reset size */ 280 max = MIN(IQUIC_MAX_SRST_SIZE, data_sz - 1u); 281 if (max > IQUIC_MIN_SRST_SIZE) 282 { 283 rand = lsquic_crand_get_byte(prq->prq_enpub->enp_crand); 284 size = IQUIC_MIN_SRST_SIZE + rand % (max - IQUIC_MIN_SRST_SIZE); 285 } 286 else 287 size = IQUIC_MIN_SRST_SIZE; 288 LSQ_DEBUGC("selected %u-byte reset size for CID %"CID_FMT 289 " (range is [%u, %u])", size, CID_BITS(dcid), 290 IQUIC_MIN_SRST_SIZE, max); 291 } 292 else 293 size = 0; 294 295 req = get_req(prq); 296 if (!req) 297 { 298 LSQ_DEBUG("out of reqs: cannot allocated another one"); 299 return -1; 300 } 301 302 req->pr_type = type; 303 req->pr_dcid = *dcid; 304 if (lsquic_hash_find(prq->prq_reqs_hash, req, sizeof(*req))) 305 { 306 LSQ_DEBUG("request for this DCID and type already exists"); 307 put_req(prq, req); 308 return -1; 309 } 310 311 req->pr_hash_el.qhe_flags = 0; 312 if (!lsquic_hash_insert(prq->prq_reqs_hash, req, sizeof(*req), 313 req, &req->pr_hash_el)) 314 { 315 LSQ_DEBUG("could not insert req into hash"); 316 put_req(prq, req); 317 return -1; 318 } 319 320 req->pr_flags = flags; 321 req->pr_rst_sz = size; 322 req->pr_version = version; 323 req->pr_scid = *scid; 324 req->pr_path.np_peer_ctx = peer_ctx; 325 memcpy(req->pr_path.np_local_addr, local_addr, 326 sizeof(req->pr_path.np_local_addr)); 327 memcpy(NP_PEER_SA(&req->pr_path), peer_addr, 328 sizeof(req->pr_path.np_peer_addr)); 329 330 LSQ_DEBUGC("scheduled %s packet for connection %"CID_FMT, 331 lsquic_preqt2str[type], CID_BITS(&req->pr_dcid)); 332 return 0; 333} 334 335 336int 337lsquic_prq_new_req (struct pr_queue *prq, enum packet_req_type type, 338 const struct lsquic_packet_in *packet_in, void *peer_ctx, 339 const struct sockaddr *local_addr, const struct sockaddr *peer_addr) 340{ 341 lsquic_ver_tag_t ver_tag; 342 enum lsquic_version version; 343 enum pr_flags flags; 344 lsquic_cid_t scid; 345 346 if (packet_in->pi_flags & PI_GQUIC) 347 flags = PR_GQUIC; 348 else 349 flags = 0; 350 351 if (packet_in->pi_quic_ver) 352 { 353 memcpy(&ver_tag, packet_in->pi_data + packet_in->pi_quic_ver, 354 sizeof(ver_tag)); 355 version = lsquic_tag2ver(ver_tag); 356 } 357 else /* Got to set it to something sensible... */ 358 version = LSQVER_ID27; 359 360 lsquic_scid_from_packet_in(packet_in, &scid); 361 return lsquic_prq_new_req_ext(prq, type, flags, version, 362 packet_in->pi_data_sz, &packet_in->pi_dcid, &scid, 363 peer_ctx, local_addr, peer_addr); 364} 365 366 367static size_t 368max_bufsz (const struct pr_queue *prq) 369{ 370 return MAX(MAX(MAX(IQUIC_VERNEG_SIZE, 371 IQUIC_MIN_SRST_SIZE), 372 sizeof(prq->prq_verneg_g_buf)), 373 sizeof(prq->prq_pubres_g_buf)); 374} 375 376 377static struct evanescent_conn * 378get_evconn (struct pr_queue *prq) 379{ 380 struct evanescent_conn *evconn; 381 struct lsquic_conn *lconn; 382 struct lsquic_packet_out *packet_out; 383 size_t bufsz; 384 385 if (prq->prq_nconns >= prq->prq_max_conns) 386 { /* This deserves a warning */ 387 LSQ_WARN("tried to get connection past limit of %u", prq->prq_max_conns); 388 return NULL; 389 } 390 391 lconn = TAILQ_FIRST(&prq->prq_free_conns); 392 if (lconn) 393 { 394 TAILQ_REMOVE(&prq->prq_free_conns, lconn, cn_next_pr); 395 evconn = (struct evanescent_conn *) lconn; 396 evconn->evc_flags = 0; 397 return evconn; 398 } 399 400 bufsz = max_bufsz(prq); 401 evconn = calloc(1, sizeof(*evconn) + bufsz); 402 if (!evconn) 403 { 404 LSQ_WARN("calloc failed: %s", strerror(errno)); 405 return NULL; 406 } 407 408 /* These values stay the same between connection usages: */ 409 evconn->evc_queue = prq; 410 lconn = &evconn->evc_conn; 411 lconn->cn_cces = evconn->evc_cces; 412 lconn->cn_cces_mask = 1; 413 lconn->cn_n_cces = sizeof(evconn->evc_cces) / sizeof(evconn->evc_cces[0]); 414 lconn->cn_if = &evanescent_conn_iface; 415 lconn->cn_flags = LSCONN_EVANESCENT; 416 packet_out = &evconn->evc_packet_out; 417 packet_out->po_flags = PO_NOENCRYPT; 418 packet_out->po_data = evconn->evc_buf; 419 420 return evconn; 421} 422 423 424struct lsquic_conn * 425lsquic_prq_next_conn (struct pr_queue *prq) 426{ 427 struct evanescent_conn *evconn; 428 struct lsquic_conn *lconn; 429 struct lsquic_hash_elem *el; 430 struct packet_req *req; 431 struct lsquic_packet_out *packet_out; 432 int (*gen_verneg) (unsigned char *, size_t, const lsquic_cid_t *, 433 const lsquic_cid_t *, unsigned, uint8_t); 434 int len; 435 436 lconn = TAILQ_FIRST(&prq->prq_returned_conns); 437 if (lconn) 438 { 439 TAILQ_REMOVE(&prq->prq_returned_conns, lconn, cn_next_pr); 440 return lconn; 441 } 442 443 el = lsquic_hash_first(prq->prq_reqs_hash); 444 if (!el) /* Nothing is queued */ 445 return NULL; 446 447 evconn = get_evconn(prq); 448 if (!evconn) /* Reached limit or malloc failed */ 449 return NULL; 450 451 req = lsquic_hashelem_getdata(el); 452 packet_out = &evconn->evc_packet_out; 453 switch ((req->pr_type << 29) | req->pr_flags) 454 { 455 case (PACKET_REQ_VERNEG << 29) | PR_GQUIC: 456 packet_out->po_data_sz = prq->prq_verneg_g_sz; 457 packet_out->po_flags |= PO_VERNEG; 458 memcpy(packet_out->po_data, prq->prq_verneg_g_buf, 459 prq->prq_verneg_g_sz); 460 memcpy(packet_out->po_data + 1, req->pr_dcid.idbuf, GQUIC_CID_LEN); 461 break; 462 case (PACKET_REQ_PUBRES << 29) | PR_GQUIC: 463 packet_out->po_flags &= ~PO_VERNEG; 464 packet_out->po_data_sz = prq->prq_pubres_g_sz; 465 memcpy(packet_out->po_data, prq->prq_pubres_g_buf, 466 prq->prq_pubres_g_sz); 467 memcpy(packet_out->po_data + 1, req->pr_dcid.idbuf, GQUIC_CID_LEN); 468 break; 469 case (PACKET_REQ_VERNEG << 29) | 0: 470 packet_out->po_flags |= PO_VERNEG; 471 if (req->pr_version == LSQVER_046) 472 gen_verneg = lsquic_Q046_gen_ver_nego_pkt; 473 else 474 gen_verneg = lsquic_ietf_v1_gen_ver_nego_pkt; 475 len = gen_verneg(packet_out->po_data, max_bufsz(prq), 476 /* Flip SCID/DCID here: */ &req->pr_dcid, &req->pr_scid, 477 prq->prq_enpub->enp_settings.es_versions, 478 lsquic_crand_get_byte(prq->prq_enpub->enp_crand)); 479 if (len > 0) 480 packet_out->po_data_sz = len; 481 else 482 packet_out->po_data_sz = 0; 483 break; 484 default: 485 packet_out->po_flags &= ~PO_VERNEG; 486 packet_out->po_data_sz = req->pr_rst_sz; 487 RAND_bytes(packet_out->po_data, req->pr_rst_sz - IQUIC_SRESET_TOKEN_SZ); 488 packet_out->po_data[0] &= ~0x80; 489 packet_out->po_data[0] |= 0x40; 490 lsquic_tg_generate_sreset(prq->prq_enpub->enp_tokgen, &req->pr_dcid, 491 packet_out->po_data + req->pr_rst_sz - IQUIC_SRESET_TOKEN_SZ); 492 break; 493 } 494 495 lsquic_hash_erase(prq->prq_reqs_hash, el); 496 evconn->evc_req = req; 497 498 lconn= &evconn->evc_conn; 499 evconn->evc_cces[0].cce_cid = req->pr_dcid; 500 packet_out->po_path = &req->pr_path; 501 502 ++prq->prq_nconns; 503 return lconn; 504} 505 506 507int 508lsquic_prq_have_pending (const struct pr_queue *prq) 509{ 510 return lsquic_hash_count(prq->prq_reqs_hash) > 0; 511} 512 513 514static struct lsquic_packet_out * 515evanescent_conn_ci_next_packet_to_send (struct lsquic_conn *lconn, size_t size) 516{ 517 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 518 assert(size == 0); 519 return &evconn->evc_packet_out; 520} 521 522 523static void 524prq_free_conn (struct pr_queue *prq, struct lsquic_conn *lconn) 525{ 526 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 527 528 TAILQ_INSERT_HEAD(&prq->prq_free_conns, lconn, cn_next_pr); 529 put_req(prq, evconn->evc_req); 530 --prq->prq_nconns; 531} 532 533 534static void 535evanescent_conn_ci_packet_sent (struct lsquic_conn *lconn, 536 struct lsquic_packet_out *packet_out) 537{ 538 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 539 struct pr_queue *const prq = evconn->evc_queue; 540 541 assert(packet_out == &evconn->evc_packet_out); 542 assert(prq->prq_nconns > 0); 543 544 LSQ_DEBUGC("sent %s packet for connection %"CID_FMT"; free resources", 545 lsquic_preqt2str[ evconn->evc_req->pr_type ], 546 CID_BITS(&evconn->evc_req->pr_dcid)); 547 prq_free_conn(prq, lconn); 548} 549 550 551static void 552evanescent_conn_ci_packet_not_sent (struct lsquic_conn *lconn, 553 struct lsquic_packet_out *packet_out) 554{ 555 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 556 struct pr_queue *const prq = evconn->evc_queue; 557 558 assert(packet_out == &evconn->evc_packet_out); 559 assert(prq->prq_nconns > 0); 560 561 if (evconn->evc_flags & EVC_DROP) 562 { 563 LSQ_DEBUGC("packet not sent; drop connection %"CID_FMT, 564 CID_BITS(&evconn->evc_req->pr_dcid)); 565 prq_free_conn(prq, lconn); 566 } 567 else 568 { 569 LSQ_DEBUG("packet not sent; put connection onto used list"); 570 TAILQ_INSERT_HEAD(&prq->prq_returned_conns, lconn, cn_next_pr); 571 } 572} 573 574 575static enum tick_st 576evanescent_conn_ci_tick (struct lsquic_conn *lconn, lsquic_time_t now) 577{ 578 assert(0); 579 return TICK_CLOSE; 580} 581 582 583static void 584evanescent_conn_ci_destroy (struct lsquic_conn *lconn) 585{ 586 assert(0); 587} 588 589 590static struct lsquic_engine * 591evanescent_conn_ci_get_engine (struct lsquic_conn *lconn) 592{ 593 assert(0); 594 return NULL; 595} 596 597 598static void 599evanescent_conn_ci_hsk_done (struct lsquic_conn *lconn, 600 enum lsquic_hsk_status status) 601{ 602 assert(0); 603} 604 605 606static void 607evanescent_conn_ci_packet_in (struct lsquic_conn *lconn, 608 struct lsquic_packet_in *packet_in) 609{ 610 assert(0); 611} 612 613 614static void 615evanescent_conn_ci_client_call_on_new (struct lsquic_conn *lconn) 616{ 617 assert(0); 618} 619 620 621static struct network_path * 622evanescent_conn_ci_get_path (struct lsquic_conn *lconn, 623 const struct sockaddr *sa) 624{ 625 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 626 627 return &evconn->evc_req->pr_path; 628} 629 630 631static unsigned char 632evanescent_conn_ci_record_addrs (struct lsquic_conn *lconn, void *peer_ctx, 633 const struct sockaddr *local_sa, const struct sockaddr *peer_sa) 634{ 635 assert(0); 636 return 0; 637} 638 639 640static const struct conn_iface evanescent_conn_iface = { 641 .ci_client_call_on_new = evanescent_conn_ci_client_call_on_new, 642 .ci_destroy = evanescent_conn_ci_destroy, 643 .ci_get_engine = evanescent_conn_ci_get_engine, 644 .ci_get_path = evanescent_conn_ci_get_path, 645 .ci_hsk_done = evanescent_conn_ci_hsk_done, 646 .ci_next_packet_to_send = evanescent_conn_ci_next_packet_to_send, 647 .ci_packet_in = evanescent_conn_ci_packet_in, 648 .ci_packet_not_sent = evanescent_conn_ci_packet_not_sent, 649 .ci_packet_sent = evanescent_conn_ci_packet_sent, 650 .ci_record_addrs = evanescent_conn_ci_record_addrs, 651 .ci_tick = evanescent_conn_ci_tick, 652}; 653 654 655const char *const lsquic_preqt2str[] = 656{ 657 [PACKET_REQ_VERNEG] = "version negotiation", 658 [PACKET_REQ_PUBRES] = "stateless reset", 659}; 660 661 662void 663lsquic_prq_drop (struct lsquic_conn *lconn) 664{ 665 struct evanescent_conn *const evconn = (void *) lconn; 666 667 evconn->evc_flags |= EVC_DROP; 668 LSQ_DEBUGC("mark for connection %"CID_FMT" for dropping", 669 CID_BITS(&evconn->evc_req->pr_dcid)); 670} 671