Mercurial > hg > nginx
comparison src/event/ngx_event_quic.c @ 8596:38c7dd720774 quic
QUIC: added ACK frame range support.
The history of acknowledged packet is kept in send context as ranges.
Up to NGX_QUIC_MAX_RANGES ranges is stored.
As a result, instead of separate ack frames, single frame with ranges
is sent.
author | Vladimir Homutov <vl@nginx.com> |
---|---|
date | Tue, 20 Oct 2020 18:53:00 +0300 |
parents | 96798101c3aa |
children | 0351fcf52a03 |
comparison
equal
deleted
inserted
replaced
8595:96798101c3aa | 8596:38c7dd720774 |
---|---|
91 */ | 91 */ |
92 typedef struct { | 92 typedef struct { |
93 ngx_quic_secret_t client_secret; | 93 ngx_quic_secret_t client_secret; |
94 ngx_quic_secret_t server_secret; | 94 ngx_quic_secret_t server_secret; |
95 | 95 |
96 enum ssl_encryption_level_t level; | |
97 | |
96 uint64_t pnum; /* to be sent */ | 98 uint64_t pnum; /* to be sent */ |
97 uint64_t largest_ack; /* received from peer */ | 99 uint64_t largest_ack; /* received from peer */ |
98 uint64_t largest_pn; /* received from peer */ | 100 uint64_t largest_pn; /* received from peer */ |
99 | 101 |
100 ngx_queue_t frames; | 102 ngx_queue_t frames; |
101 ngx_queue_t sent; | 103 ngx_queue_t sent; |
104 | |
105 uint64_t pending_ack; /* non sent ack-eliciting */ | |
106 uint64_t largest_range; | |
107 uint64_t first_range; | |
108 ngx_uint_t nranges; | |
109 ngx_quic_ack_range_t ranges[NGX_QUIC_MAX_RANGES]; | |
110 struct timeval ack_received; | |
111 ngx_uint_t send_ack; /* unsigned send_ack:1 */ | |
102 } ngx_quic_send_ctx_t; | 112 } ngx_quic_send_ctx_t; |
103 | 113 |
104 | 114 |
105 struct ngx_quic_connection_s { | 115 struct ngx_quic_connection_s { |
106 ngx_str_t scid; /* initial client ID */ | 116 ngx_str_t scid; /* initial client ID */ |
228 enum ssl_encryption_level_t level); | 238 enum ssl_encryption_level_t level); |
229 static ngx_int_t ngx_quic_check_peer(ngx_quic_connection_t *qc, | 239 static ngx_int_t ngx_quic_check_peer(ngx_quic_connection_t *qc, |
230 ngx_quic_header_t *pkt); | 240 ngx_quic_header_t *pkt); |
231 static ngx_int_t ngx_quic_payload_handler(ngx_connection_t *c, | 241 static ngx_int_t ngx_quic_payload_handler(ngx_connection_t *c, |
232 ngx_quic_header_t *pkt); | 242 ngx_quic_header_t *pkt); |
233 static ngx_int_t ngx_quic_send_ack(ngx_connection_t *c, ngx_quic_header_t *pkt); | 243 static ngx_int_t ngx_quic_ack_packet(ngx_connection_t *c, |
244 ngx_quic_header_t *pkt); | |
245 static ngx_int_t ngx_quic_send_ack_range(ngx_connection_t *c, | |
246 ngx_quic_send_ctx_t *ctx, uint64_t smallest, uint64_t largest); | |
247 static ngx_int_t ngx_quic_send_ack(ngx_connection_t *c, | |
248 ngx_quic_send_ctx_t *ctx); | |
234 static ngx_int_t ngx_quic_ack_delay(ngx_connection_t *c, | 249 static ngx_int_t ngx_quic_ack_delay(ngx_connection_t *c, |
235 struct timeval *received, enum ssl_encryption_level_t level); | 250 struct timeval *received, enum ssl_encryption_level_t level); |
236 static ngx_int_t ngx_quic_send_cc(ngx_connection_t *c); | 251 static ngx_int_t ngx_quic_send_cc(ngx_connection_t *c); |
237 static ngx_int_t ngx_quic_send_new_token(ngx_connection_t *c); | 252 static ngx_int_t ngx_quic_send_new_token(ngx_connection_t *c); |
238 | 253 |
683 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) { | 698 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) { |
684 ngx_queue_init(&qc->send_ctx[i].frames); | 699 ngx_queue_init(&qc->send_ctx[i].frames); |
685 ngx_queue_init(&qc->send_ctx[i].sent); | 700 ngx_queue_init(&qc->send_ctx[i].sent); |
686 qc->send_ctx[i].largest_pn = (uint64_t) -1; | 701 qc->send_ctx[i].largest_pn = (uint64_t) -1; |
687 qc->send_ctx[i].largest_ack = (uint64_t) -1; | 702 qc->send_ctx[i].largest_ack = (uint64_t) -1; |
688 } | 703 qc->send_ctx[i].largest_range = (uint64_t) -1; |
704 qc->send_ctx[i].pending_ack = (uint64_t) -1; | |
705 } | |
706 | |
707 qc->send_ctx[0].level = ssl_encryption_initial; | |
708 qc->send_ctx[1].level = ssl_encryption_handshake; | |
709 qc->send_ctx[2].level = ssl_encryption_application; | |
689 | 710 |
690 for (i = 0; i < NGX_QUIC_ENCRYPTION_LAST; i++) { | 711 for (i = 0; i < NGX_QUIC_ENCRYPTION_LAST; i++) { |
691 ngx_queue_init(&qc->crypto[i].frames); | 712 ngx_queue_init(&qc->crypto[i].frames); |
692 } | 713 } |
693 | 714 |
1972 | 1993 |
1973 f = ngx_queue_data(q, ngx_quic_frame_t, queue); | 1994 f = ngx_queue_data(q, ngx_quic_frame_t, queue); |
1974 ngx_quic_congestion_ack(c, f); | 1995 ngx_quic_congestion_ack(c, f); |
1975 ngx_quic_free_frame(c, f); | 1996 ngx_quic_free_frame(c, f); |
1976 } | 1997 } |
1998 | |
1999 ctx->send_ack = 0; | |
1977 } | 2000 } |
1978 | 2001 |
1979 | 2002 |
1980 static ngx_int_t | 2003 static ngx_int_t |
1981 ngx_quic_check_peer(ngx_quic_connection_t *qc, ngx_quic_header_t *pkt) | 2004 ngx_quic_check_peer(ngx_quic_connection_t *qc, ngx_quic_header_t *pkt) |
2039 static ngx_int_t | 2062 static ngx_int_t |
2040 ngx_quic_payload_handler(ngx_connection_t *c, ngx_quic_header_t *pkt) | 2063 ngx_quic_payload_handler(ngx_connection_t *c, ngx_quic_header_t *pkt) |
2041 { | 2064 { |
2042 u_char *end, *p; | 2065 u_char *end, *p; |
2043 ssize_t len; | 2066 ssize_t len; |
2044 ngx_uint_t ack_sent, do_close; | 2067 ngx_uint_t do_close; |
2045 ngx_quic_frame_t frame; | 2068 ngx_quic_frame_t frame; |
2046 ngx_quic_connection_t *qc; | 2069 ngx_quic_connection_t *qc; |
2047 | 2070 |
2048 qc = c->quic; | 2071 qc = c->quic; |
2049 | 2072 |
2067 } | 2090 } |
2068 | 2091 |
2069 p = pkt->payload.data; | 2092 p = pkt->payload.data; |
2070 end = p + pkt->payload.len; | 2093 end = p + pkt->payload.len; |
2071 | 2094 |
2072 ack_sent = 0; | |
2073 do_close = 0; | 2095 do_close = 0; |
2074 | 2096 |
2075 while (p < end) { | 2097 while (p < end) { |
2076 | 2098 |
2077 c->log->action = "parsing frames"; | 2099 c->log->action = "parsing frames"; |
2105 do_close = 1; | 2127 do_close = 1; |
2106 continue; | 2128 continue; |
2107 } | 2129 } |
2108 | 2130 |
2109 /* got there with ack-eliciting packet */ | 2131 /* got there with ack-eliciting packet */ |
2110 | 2132 pkt->need_ack = 1; |
2111 if (!ack_sent) { | |
2112 if (ngx_quic_send_ack(c, pkt) != NGX_OK) { | |
2113 return NGX_ERROR; | |
2114 } | |
2115 | |
2116 ack_sent = 1; | |
2117 } | |
2118 | 2133 |
2119 switch (frame.type) { | 2134 switch (frame.type) { |
2120 | 2135 |
2121 case NGX_QUIC_FT_CRYPTO: | 2136 case NGX_QUIC_FT_CRYPTO: |
2122 | 2137 |
2267 if (do_close) { | 2282 if (do_close) { |
2268 qc->draining = 1; | 2283 qc->draining = 1; |
2269 ngx_quic_close_connection(c, NGX_OK); | 2284 ngx_quic_close_connection(c, NGX_OK); |
2270 } | 2285 } |
2271 | 2286 |
2287 if (ngx_quic_ack_packet(c, pkt) != NGX_OK) { | |
2288 return NGX_ERROR; | |
2289 } | |
2290 | |
2272 return NGX_OK; | 2291 return NGX_OK; |
2273 } | 2292 } |
2274 | 2293 |
2275 | 2294 |
2276 static ngx_int_t | 2295 static ngx_int_t |
2277 ngx_quic_send_ack(ngx_connection_t *c, ngx_quic_header_t *pkt) | 2296 ngx_quic_ack_packet(ngx_connection_t *c, ngx_quic_header_t *pkt) |
2297 { | |
2298 uint64_t base, largest, smallest, gs, ge, gap, range, pn; | |
2299 uint64_t prev_pending; | |
2300 ngx_uint_t i, nr; | |
2301 ngx_quic_send_ctx_t *ctx; | |
2302 ngx_quic_ack_range_t *r; | |
2303 | |
2304 c->log->action = "preparing ack"; | |
2305 | |
2306 ctx = ngx_quic_get_send_ctx(c->quic, pkt->level); | |
2307 | |
2308 ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
2309 "ngx_quic_ack_packet pn %uL largest %uL nranges %ui", | |
2310 pkt->pn, ctx->largest_range, ctx->nranges); | |
2311 | |
2312 prev_pending = ctx->pending_ack; | |
2313 | |
2314 if (pkt->need_ack) { | |
2315 | |
2316 ngx_post_event(&c->quic->push, &ngx_posted_events); | |
2317 | |
2318 ctx->send_ack = 1; | |
2319 | |
2320 if (ctx->pending_ack == (uint64_t) -1 | |
2321 || ctx->pending_ack < pkt->pn) | |
2322 { | |
2323 ctx->pending_ack = pkt->pn; | |
2324 } | |
2325 } | |
2326 | |
2327 base = ctx->largest_range; | |
2328 pn = pkt->pn; | |
2329 | |
2330 if (base == (uint64_t) -1) { | |
2331 ctx->largest_range = pn; | |
2332 ctx->ack_received = pkt->received; | |
2333 return NGX_OK; | |
2334 } | |
2335 | |
2336 if (base == pn) { | |
2337 return NGX_OK; | |
2338 } | |
2339 | |
2340 largest = base; | |
2341 smallest = largest - ctx->first_range; | |
2342 | |
2343 if (pn > base) { | |
2344 | |
2345 if (pn - base == 1) { | |
2346 ctx->first_range++; | |
2347 ctx->largest_range = pn; | |
2348 ctx->ack_received = pkt->received; | |
2349 | |
2350 return NGX_OK; | |
2351 | |
2352 } else { | |
2353 /* new gap in front of current largest */ | |
2354 | |
2355 /* no place for new range, send current range as is */ | |
2356 if (ctx->nranges == NGX_QUIC_MAX_RANGES) { | |
2357 | |
2358 if (prev_pending != (uint64_t) -1) { | |
2359 if (ngx_quic_send_ack(c, ctx) != NGX_OK) { | |
2360 return NGX_ERROR; | |
2361 } | |
2362 } | |
2363 | |
2364 if (prev_pending == ctx->pending_ack || !pkt->need_ack) { | |
2365 ctx->pending_ack = (uint64_t) -1; | |
2366 } | |
2367 } | |
2368 | |
2369 gap = pn - base - 2; | |
2370 range = ctx->first_range; | |
2371 | |
2372 ctx->first_range = 0; | |
2373 ctx->largest_range = pn; | |
2374 ctx->ack_received = pkt->received; | |
2375 | |
2376 i = 0; | |
2377 | |
2378 goto insert; | |
2379 } | |
2380 } | |
2381 | |
2382 /* pn < base, perform lookup in existing ranges */ | |
2383 | |
2384 if (pn >= smallest && pn <= largest) { | |
2385 return NGX_OK; | |
2386 } | |
2387 | |
2388 #if (NGX_SUPPRESS_WARN) | |
2389 r = NULL; | |
2390 #endif | |
2391 | |
2392 for (i = 0; i < ctx->nranges; i++) { | |
2393 r = &ctx->ranges[i]; | |
2394 | |
2395 ge = smallest - 1; | |
2396 gs = ge - r->gap; | |
2397 | |
2398 if (pn >= gs && pn <= ge) { | |
2399 | |
2400 if (gs == ge) { | |
2401 /* gap size is exactly one packet, now filled */ | |
2402 | |
2403 /* data moves to previous range, current is removed */ | |
2404 | |
2405 if (i == 0) { | |
2406 ctx->first_range += r->range + 2; | |
2407 | |
2408 } else { | |
2409 ctx->ranges[i - 1].range += r->range + 2; | |
2410 } | |
2411 | |
2412 nr = ctx->nranges - i - 1; | |
2413 if (nr) { | |
2414 ngx_memmove(&ctx->ranges[i], &ctx->ranges[i + 1], | |
2415 sizeof(ngx_quic_ack_range_t) * nr); | |
2416 } | |
2417 | |
2418 ctx->nranges--; | |
2419 | |
2420 } else if (pn == gs) { | |
2421 /* current gap shrinks from tail (current range grows) */ | |
2422 r->gap--; | |
2423 r->range++; | |
2424 | |
2425 } else if (pn == ge) { | |
2426 /* current gap shrinks from head (previous range grows) */ | |
2427 r->gap--; | |
2428 | |
2429 if (i == 0) { | |
2430 ctx->first_range++; | |
2431 | |
2432 } else { | |
2433 ctx->ranges[i - 1].range++; | |
2434 } | |
2435 | |
2436 } else { | |
2437 /* current gap is split into two parts */ | |
2438 | |
2439 gap = ge - pn - 1; | |
2440 range = 0; | |
2441 | |
2442 if (ctx->nranges == NGX_QUIC_MAX_RANGES) { | |
2443 if (prev_pending != (uint64_t) -1) { | |
2444 if (ngx_quic_send_ack(c, ctx) != NGX_OK) { | |
2445 return NGX_ERROR; | |
2446 } | |
2447 } | |
2448 | |
2449 if (prev_pending == ctx->pending_ack || !pkt->need_ack) { | |
2450 ctx->pending_ack = (uint64_t) -1; | |
2451 } | |
2452 } | |
2453 | |
2454 r->gap = pn - gs - 1; | |
2455 goto insert; | |
2456 } | |
2457 | |
2458 return NGX_OK; | |
2459 } | |
2460 | |
2461 largest = smallest - r->gap - 2; | |
2462 smallest = largest - r->range; | |
2463 | |
2464 if (pn >= smallest && pn <= largest) { | |
2465 /* this packet number is already known */ | |
2466 return NGX_OK; | |
2467 } | |
2468 | |
2469 } | |
2470 | |
2471 if (pn == smallest - 1) { | |
2472 /* extend first or last range */ | |
2473 | |
2474 if (i == 0) { | |
2475 ctx->first_range++; | |
2476 | |
2477 } else { | |
2478 r->range++; | |
2479 } | |
2480 | |
2481 return NGX_OK; | |
2482 } | |
2483 | |
2484 /* nothing found, add new range at the tail */ | |
2485 | |
2486 if (ctx->nranges == NGX_QUIC_MAX_RANGES) { | |
2487 /* packet is too old to keep it */ | |
2488 | |
2489 if (pkt->need_ack) { | |
2490 return ngx_quic_send_ack_range(c, ctx, pn, pn); | |
2491 } | |
2492 | |
2493 return NGX_OK; | |
2494 } | |
2495 | |
2496 gap = smallest - 2 - pn; | |
2497 range = 0; | |
2498 | |
2499 insert: | |
2500 | |
2501 if (ctx->nranges < NGX_QUIC_MAX_RANGES) { | |
2502 ctx->nranges++; | |
2503 } | |
2504 | |
2505 ngx_memmove(&ctx->ranges[i + 1], &ctx->ranges[i], | |
2506 sizeof(ngx_quic_ack_range_t) * (ctx->nranges - i - 1)); | |
2507 | |
2508 ctx->ranges[i].gap = gap; | |
2509 ctx->ranges[i].range = range; | |
2510 | |
2511 return NGX_OK; | |
2512 } | |
2513 | |
2514 | |
2515 static ngx_int_t | |
2516 ngx_quic_send_ack_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx, | |
2517 uint64_t smallest, uint64_t largest) | |
2278 { | 2518 { |
2279 ngx_quic_frame_t *frame; | 2519 ngx_quic_frame_t *frame; |
2280 | |
2281 c->log->action = "generating acknowledgment"; | |
2282 | |
2283 /* every ACK-eliciting packet is acknowledged, TODO ACK Ranges */ | |
2284 | 2520 |
2285 frame = ngx_quic_alloc_frame(c, 0); | 2521 frame = ngx_quic_alloc_frame(c, 0); |
2286 if (frame == NULL) { | 2522 if (frame == NULL) { |
2287 return NGX_ERROR; | 2523 return NGX_ERROR; |
2288 } | 2524 } |
2289 | 2525 |
2290 frame->level = (pkt->level == ssl_encryption_early_data) | 2526 frame->level = ctx->level; |
2291 ? ssl_encryption_application | |
2292 : pkt->level; | |
2293 | |
2294 frame->type = NGX_QUIC_FT_ACK; | 2527 frame->type = NGX_QUIC_FT_ACK; |
2295 frame->u.ack.largest = pkt->pn; | 2528 frame->u.ack.largest = largest; |
2296 frame->u.ack.delay = ngx_quic_ack_delay(c, &pkt->received, frame->level); | 2529 frame->u.ack.delay = 0; |
2297 | 2530 frame->u.ack.range_count = 0; |
2298 ngx_sprintf(frame->info, "ACK for PN=%uL from frame handler level=%d", | 2531 frame->u.ack.first_range = largest - smallest; |
2299 pkt->pn, frame->level); | 2532 |
2533 ngx_sprintf(frame->info, "ACK for PN=%uL..%uL 0 ranges level=%d", | |
2534 largest, smallest, frame->level); | |
2535 | |
2536 return NGX_OK; | |
2537 } | |
2538 | |
2539 | |
2540 static ngx_int_t | |
2541 ngx_quic_send_ack(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx) | |
2542 { | |
2543 size_t ranges_len; | |
2544 ngx_quic_frame_t *frame; | |
2545 | |
2546 ranges_len = sizeof(ngx_quic_ack_range_t) * ctx->nranges; | |
2547 | |
2548 frame = ngx_quic_alloc_frame(c, ranges_len); | |
2549 if (frame == NULL) { | |
2550 return NGX_ERROR; | |
2551 } | |
2552 | |
2553 ngx_memcpy(frame->data, ctx->ranges, ranges_len); | |
2554 | |
2555 frame->level = ctx->level; | |
2556 frame->type = NGX_QUIC_FT_ACK; | |
2557 frame->u.ack.largest = ctx->largest_range; | |
2558 frame->u.ack.delay = ngx_quic_ack_delay(c, &ctx->ack_received, ctx->level); | |
2559 frame->u.ack.range_count = ctx->nranges; | |
2560 frame->u.ack.first_range = ctx->first_range; | |
2561 frame->u.ack.ranges_start = frame->data; | |
2562 frame->u.ack.ranges_end = frame->data + ranges_len; | |
2563 | |
2564 ngx_sprintf(frame->info, "ACK for PN=%uL %ui ranges level=%d", | |
2565 ctx->largest_range, ctx->nranges, frame->level); | |
2566 | |
2300 ngx_quic_queue_frame(c->quic, frame); | 2567 ngx_quic_queue_frame(c->quic, frame); |
2301 | 2568 |
2302 return NGX_OK; | 2569 return NGX_OK; |
2303 } | 2570 } |
2304 | 2571 |
3710 | 3977 |
3711 static ngx_int_t | 3978 static ngx_int_t |
3712 ngx_quic_output(ngx_connection_t *c) | 3979 ngx_quic_output(ngx_connection_t *c) |
3713 { | 3980 { |
3714 ngx_uint_t i; | 3981 ngx_uint_t i; |
3982 ngx_quic_send_ctx_t *ctx; | |
3715 ngx_quic_connection_t *qc; | 3983 ngx_quic_connection_t *qc; |
3716 | 3984 |
3717 c->log->action = "sending frames"; | 3985 c->log->action = "sending frames"; |
3718 | 3986 |
3719 qc = c->quic; | 3987 qc = c->quic; |
3720 | 3988 |
3721 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) { | 3989 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) { |
3722 if (ngx_quic_output_frames(c, &qc->send_ctx[i]) != NGX_OK) { | 3990 |
3991 ctx = &qc->send_ctx[i]; | |
3992 | |
3993 if (ctx->send_ack) { | |
3994 if (ngx_quic_send_ack(c, ctx) != NGX_OK) { | |
3995 return NGX_ERROR; | |
3996 } | |
3997 ctx->send_ack = 0; | |
3998 } | |
3999 | |
4000 if (ngx_quic_output_frames(c, ctx) != NGX_OK) { | |
3723 return NGX_ERROR; | 4001 return NGX_ERROR; |
3724 } | 4002 } |
3725 } | 4003 } |
3726 | 4004 |
3727 if (!qc->send_timer_set && !qc->closing) { | 4005 if (!qc->send_timer_set && !qc->closing) { |