lsquic_pr_queue.c revision bc520ef7
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 * 138prq_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 220prq_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 262int 263lsquic_prq_new_req (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 337prq_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_ID25; 359 360 lsquic_scid_from_packet_in(packet_in, &scid); 361 return lsquic_prq_new_req(prq, type, flags, version, packet_in->pi_data_sz, 362 &packet_in->pi_dcid, &scid, peer_ctx, local_addr, peer_addr); 363} 364 365 366static size_t 367max_bufsz (const struct pr_queue *prq) 368{ 369 return MAX(MAX(MAX(IQUIC_VERNEG_SIZE, 370 IQUIC_MIN_SRST_SIZE), 371 sizeof(prq->prq_verneg_g_buf)), 372 sizeof(prq->prq_pubres_g_buf)); 373} 374 375 376static struct evanescent_conn * 377get_evconn (struct pr_queue *prq) 378{ 379 struct evanescent_conn *evconn; 380 struct lsquic_conn *lconn; 381 struct lsquic_packet_out *packet_out; 382 size_t bufsz; 383 384 if (prq->prq_nconns >= prq->prq_max_conns) 385 { /* This deserves a warning */ 386 LSQ_WARN("tried to get connection past limit of %u", prq->prq_max_conns); 387 return NULL; 388 } 389 390 lconn = TAILQ_FIRST(&prq->prq_free_conns); 391 if (lconn) 392 { 393 TAILQ_REMOVE(&prq->prq_free_conns, lconn, cn_next_pr); 394 evconn = (struct evanescent_conn *) lconn; 395 evconn->evc_flags = 0; 396 return evconn; 397 } 398 399 bufsz = max_bufsz(prq); 400 evconn = calloc(1, sizeof(*evconn) + bufsz); 401 if (!evconn) 402 { 403 LSQ_WARN("calloc failed: %s", strerror(errno)); 404 return NULL; 405 } 406 407 /* These values stay the same between connection usages: */ 408 evconn->evc_queue = prq; 409 lconn = &evconn->evc_conn; 410 lconn->cn_cces = evconn->evc_cces; 411 lconn->cn_cces_mask = 1; 412 lconn->cn_n_cces = sizeof(evconn->evc_cces) / sizeof(evconn->evc_cces[0]); 413 lconn->cn_if = &evanescent_conn_iface; 414 lconn->cn_flags = LSCONN_EVANESCENT; 415 packet_out = &evconn->evc_packet_out; 416 packet_out->po_flags = PO_NOENCRYPT; 417 packet_out->po_data = evconn->evc_buf; 418 419 return evconn; 420} 421 422 423struct lsquic_conn * 424prq_next_conn (struct pr_queue *prq) 425{ 426 struct evanescent_conn *evconn; 427 struct lsquic_conn *lconn; 428 struct lsquic_hash_elem *el; 429 struct packet_req *req; 430 struct lsquic_packet_out *packet_out; 431 int (*gen_verneg) (unsigned char *, size_t, const lsquic_cid_t *, 432 const lsquic_cid_t *, unsigned, uint8_t); 433 int len; 434 435 lconn = TAILQ_FIRST(&prq->prq_returned_conns); 436 if (lconn) 437 { 438 TAILQ_REMOVE(&prq->prq_returned_conns, lconn, cn_next_pr); 439 return lconn; 440 } 441 442 el = lsquic_hash_first(prq->prq_reqs_hash); 443 if (!el) /* Nothing is queued */ 444 return NULL; 445 446 evconn = get_evconn(prq); 447 if (!evconn) /* Reached limit or malloc failed */ 448 return NULL; 449 450 req = lsquic_hashelem_getdata(el); 451 packet_out = &evconn->evc_packet_out; 452 switch ((req->pr_type << 29) | req->pr_flags) 453 { 454 case (PACKET_REQ_VERNEG << 29) | PR_GQUIC: 455 packet_out->po_data_sz = prq->prq_verneg_g_sz; 456 packet_out->po_flags |= PO_VERNEG; 457 memcpy(packet_out->po_data, prq->prq_verneg_g_buf, 458 prq->prq_verneg_g_sz); 459 memcpy(packet_out->po_data + 1, req->pr_dcid.idbuf, GQUIC_CID_LEN); 460 break; 461 case (PACKET_REQ_PUBRES << 29) | PR_GQUIC: 462 packet_out->po_flags &= ~PO_VERNEG; 463 packet_out->po_data_sz = prq->prq_pubres_g_sz; 464 memcpy(packet_out->po_data, prq->prq_pubres_g_buf, 465 prq->prq_pubres_g_sz); 466 memcpy(packet_out->po_data + 1, req->pr_dcid.idbuf, GQUIC_CID_LEN); 467 break; 468 case (PACKET_REQ_VERNEG << 29) | 0: 469 packet_out->po_flags |= PO_VERNEG; 470 if (req->pr_version == LSQVER_046) 471 gen_verneg = lsquic_Q046_gen_ver_nego_pkt; 472 else 473 gen_verneg = lsquic_ietf_v1_gen_ver_nego_pkt; 474 len = gen_verneg(packet_out->po_data, max_bufsz(prq), 475 /* Flip SCID/DCID here: */ &req->pr_dcid, &req->pr_scid, 476 prq->prq_enpub->enp_settings.es_versions, 477 lsquic_crand_get_byte(prq->prq_enpub->enp_crand)); 478 if (len > 0) 479 packet_out->po_data_sz = len; 480 else 481 packet_out->po_data_sz = 0; 482 break; 483 default: 484 packet_out->po_flags &= ~PO_VERNEG; 485 packet_out->po_data_sz = req->pr_rst_sz; 486 RAND_bytes(packet_out->po_data, req->pr_rst_sz - IQUIC_SRESET_TOKEN_SZ); 487 packet_out->po_data[0] &= ~0x80; 488 packet_out->po_data[0] |= 0x40; 489 lsquic_tg_generate_sreset(prq->prq_enpub->enp_tokgen, &req->pr_dcid, 490 packet_out->po_data + req->pr_rst_sz - IQUIC_SRESET_TOKEN_SZ); 491 break; 492 } 493 494 lsquic_hash_erase(prq->prq_reqs_hash, el); 495 evconn->evc_req = req; 496 497 lconn= &evconn->evc_conn; 498 evconn->evc_cces[0].cce_cid = req->pr_dcid; 499 packet_out->po_path = &req->pr_path; 500 501 ++prq->prq_nconns; 502 return lconn; 503} 504 505 506int 507prq_have_pending (const struct pr_queue *prq) 508{ 509 return lsquic_hash_count(prq->prq_reqs_hash) > 0; 510} 511 512 513static struct lsquic_packet_out * 514evanescent_conn_ci_next_packet_to_send (struct lsquic_conn *lconn, size_t size) 515{ 516 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 517 assert(size == 0); 518 return &evconn->evc_packet_out; 519} 520 521 522static void 523prq_free_conn (struct pr_queue *prq, struct lsquic_conn *lconn) 524{ 525 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 526 527 TAILQ_INSERT_HEAD(&prq->prq_free_conns, lconn, cn_next_pr); 528 put_req(prq, evconn->evc_req); 529 --prq->prq_nconns; 530} 531 532 533static void 534evanescent_conn_ci_packet_sent (struct lsquic_conn *lconn, 535 struct lsquic_packet_out *packet_out) 536{ 537 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 538 struct pr_queue *const prq = evconn->evc_queue; 539 540 assert(packet_out == &evconn->evc_packet_out); 541 assert(prq->prq_nconns > 0); 542 543 LSQ_DEBUGC("sent %s packet for connection %"CID_FMT"; free resources", 544 lsquic_preqt2str[ evconn->evc_req->pr_type ], 545 CID_BITS(&evconn->evc_req->pr_dcid)); 546 prq_free_conn(prq, lconn); 547} 548 549 550static void 551evanescent_conn_ci_packet_not_sent (struct lsquic_conn *lconn, 552 struct lsquic_packet_out *packet_out) 553{ 554 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 555 struct pr_queue *const prq = evconn->evc_queue; 556 557 assert(packet_out == &evconn->evc_packet_out); 558 assert(prq->prq_nconns > 0); 559 560 if (evconn->evc_flags & EVC_DROP) 561 { 562 LSQ_DEBUGC("packet not sent; drop connection %"CID_FMT, 563 CID_BITS(&evconn->evc_req->pr_dcid)); 564 prq_free_conn(prq, lconn); 565 } 566 else 567 { 568 LSQ_DEBUG("packet not sent; put connection onto used list"); 569 TAILQ_INSERT_HEAD(&prq->prq_returned_conns, lconn, cn_next_pr); 570 } 571} 572 573 574static enum tick_st 575evanescent_conn_ci_tick (struct lsquic_conn *lconn, lsquic_time_t now) 576{ 577 assert(0); 578 return TICK_CLOSE; 579} 580 581 582static void 583evanescent_conn_ci_destroy (struct lsquic_conn *lconn) 584{ 585 assert(0); 586} 587 588 589static struct lsquic_engine * 590evanescent_conn_ci_get_engine (struct lsquic_conn *lconn) 591{ 592 assert(0); 593 return NULL; 594} 595 596 597static void 598evanescent_conn_ci_hsk_done (struct lsquic_conn *lconn, 599 enum lsquic_hsk_status status) 600{ 601 assert(0); 602} 603 604 605static void 606evanescent_conn_ci_packet_in (struct lsquic_conn *lconn, 607 struct lsquic_packet_in *packet_in) 608{ 609 assert(0); 610} 611 612 613static void 614evanescent_conn_ci_client_call_on_new (struct lsquic_conn *lconn) 615{ 616 assert(0); 617} 618 619 620static struct network_path * 621evanescent_conn_ci_get_path (struct lsquic_conn *lconn, 622 const struct sockaddr *sa) 623{ 624 struct evanescent_conn *const evconn = (struct evanescent_conn *) lconn; 625 626 return &evconn->evc_req->pr_path; 627} 628 629 630static unsigned char 631evanescent_conn_ci_record_addrs (struct lsquic_conn *lconn, void *peer_ctx, 632 const struct sockaddr *local_sa, const struct sockaddr *peer_sa) 633{ 634 assert(0); 635 return 0; 636} 637 638 639static const struct conn_iface evanescent_conn_iface = { 640 .ci_client_call_on_new = evanescent_conn_ci_client_call_on_new, 641 .ci_destroy = evanescent_conn_ci_destroy, 642 .ci_get_engine = evanescent_conn_ci_get_engine, 643 .ci_get_path = evanescent_conn_ci_get_path, 644 .ci_hsk_done = evanescent_conn_ci_hsk_done, 645 .ci_next_packet_to_send = evanescent_conn_ci_next_packet_to_send, 646 .ci_packet_in = evanescent_conn_ci_packet_in, 647 .ci_packet_not_sent = evanescent_conn_ci_packet_not_sent, 648 .ci_packet_sent = evanescent_conn_ci_packet_sent, 649 .ci_record_addrs = evanescent_conn_ci_record_addrs, 650 .ci_tick = evanescent_conn_ci_tick, 651}; 652 653 654const char *const lsquic_preqt2str[] = 655{ 656 [PACKET_REQ_VERNEG] = "version negotiation", 657 [PACKET_REQ_PUBRES] = "stateless reset", 658}; 659 660 661void 662lsquic_prq_drop (struct lsquic_conn *lconn) 663{ 664 struct evanescent_conn *const evconn = (void *) lconn; 665 666 evconn->evc_flags |= EVC_DROP; 667 LSQ_DEBUGC("mark for connection %"CID_FMT" for dropping", 668 CID_BITS(&evconn->evc_req->pr_dcid)); 669} 670