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