Mercurial > hg > nginx-quic
comparison src/event/quic/ngx_event_quic_ack.c @ 8411:bc910a5ec737 quic
QUIC: separate files for output and ack related processing.
author | Vladimir Homutov <vl@nginx.com> |
---|---|
date | Tue, 13 Apr 2021 14:41:20 +0300 |
parents | |
children | 915c2f7092ed |
comparison
equal
deleted
inserted
replaced
8410:41807e581de9 | 8411:bc910a5ec737 |
---|---|
1 | |
2 /* | |
3 * Copyright (C) Nginx, Inc. | |
4 */ | |
5 | |
6 | |
7 #include <ngx_config.h> | |
8 #include <ngx_core.h> | |
9 #include <ngx_event.h> | |
10 #include <ngx_event_quic_connection.h> | |
11 | |
12 | |
13 #define NGX_QUIC_MAX_ACK_GAP 2 | |
14 | |
15 /* quic-recovery, section 6.1.1, Packet Threshold */ | |
16 #define NGX_QUIC_PKT_THR 3 /* packets */ | |
17 /* quic-recovery, section 6.1.2, Time Threshold */ | |
18 #define NGX_QUIC_TIME_THR 1.125 | |
19 #define NGX_QUIC_TIME_GRANULARITY 1 /* ms */ | |
20 | |
21 #define ngx_quic_lost_threshold(qc) \ | |
22 ngx_max(NGX_QUIC_TIME_THR * ngx_max((qc)->latest_rtt, (qc)->avg_rtt), \ | |
23 NGX_QUIC_TIME_GRANULARITY) | |
24 | |
25 | |
26 static void ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack, | |
27 enum ssl_encryption_level_t level, ngx_msec_t send_time); | |
28 static ngx_int_t ngx_quic_handle_ack_frame_range(ngx_connection_t *c, | |
29 ngx_quic_send_ctx_t *ctx, uint64_t min, uint64_t max, | |
30 ngx_msec_t *send_time); | |
31 static void ngx_quic_drop_ack_ranges(ngx_connection_t *c, | |
32 ngx_quic_send_ctx_t *ctx, uint64_t pn); | |
33 static ngx_int_t ngx_quic_detect_lost(ngx_connection_t *c); | |
34 static void ngx_quic_congestion_lost(ngx_connection_t *c, | |
35 ngx_quic_frame_t *frame); | |
36 static void ngx_quic_lost_handler(ngx_event_t *ev); | |
37 | |
38 | |
39 ngx_int_t | |
40 ngx_quic_handle_ack_frame(ngx_connection_t *c, ngx_quic_header_t *pkt, | |
41 ngx_quic_frame_t *f) | |
42 { | |
43 ssize_t n; | |
44 u_char *pos, *end; | |
45 uint64_t min, max, gap, range; | |
46 ngx_msec_t send_time; | |
47 ngx_uint_t i; | |
48 ngx_quic_send_ctx_t *ctx; | |
49 ngx_quic_ack_frame_t *ack; | |
50 ngx_quic_connection_t *qc; | |
51 | |
52 qc = ngx_quic_get_connection(c); | |
53 | |
54 ctx = ngx_quic_get_send_ctx(qc, pkt->level); | |
55 | |
56 ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
57 "quic ngx_quic_handle_ack_frame level:%d", pkt->level); | |
58 | |
59 ack = &f->u.ack; | |
60 | |
61 /* | |
62 * If any computed packet number is negative, an endpoint MUST | |
63 * generate a connection error of type FRAME_ENCODING_ERROR. | |
64 * (19.3.1) | |
65 */ | |
66 | |
67 if (ack->first_range > ack->largest) { | |
68 qc->error = NGX_QUIC_ERR_FRAME_ENCODING_ERROR; | |
69 ngx_log_error(NGX_LOG_INFO, c->log, 0, | |
70 "quic invalid first range in ack frame"); | |
71 return NGX_ERROR; | |
72 } | |
73 | |
74 min = ack->largest - ack->first_range; | |
75 max = ack->largest; | |
76 | |
77 if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time) | |
78 != NGX_OK) | |
79 { | |
80 return NGX_ERROR; | |
81 } | |
82 | |
83 /* 13.2.3. Receiver Tracking of ACK Frames */ | |
84 if (ctx->largest_ack < max || ctx->largest_ack == NGX_QUIC_UNSET_PN) { | |
85 ctx->largest_ack = max; | |
86 ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
87 "quic updated largest received ack:%uL", max); | |
88 | |
89 /* | |
90 * An endpoint generates an RTT sample on receiving an | |
91 * ACK frame that meets the following two conditions: | |
92 * | |
93 * - the largest acknowledged packet number is newly acknowledged | |
94 * - at least one of the newly acknowledged packets was ack-eliciting. | |
95 */ | |
96 | |
97 if (send_time != NGX_TIMER_INFINITE) { | |
98 ngx_quic_rtt_sample(c, ack, pkt->level, send_time); | |
99 } | |
100 } | |
101 | |
102 if (f->data) { | |
103 pos = f->data->buf->pos; | |
104 end = f->data->buf->last; | |
105 | |
106 } else { | |
107 pos = NULL; | |
108 end = NULL; | |
109 } | |
110 | |
111 for (i = 0; i < ack->range_count; i++) { | |
112 | |
113 n = ngx_quic_parse_ack_range(pkt->log, pos, end, &gap, &range); | |
114 if (n == NGX_ERROR) { | |
115 return NGX_ERROR; | |
116 } | |
117 pos += n; | |
118 | |
119 if (gap + 2 > min) { | |
120 qc->error = NGX_QUIC_ERR_FRAME_ENCODING_ERROR; | |
121 ngx_log_error(NGX_LOG_INFO, c->log, 0, | |
122 "quic invalid range:%ui in ack frame", i); | |
123 return NGX_ERROR; | |
124 } | |
125 | |
126 max = min - gap - 2; | |
127 | |
128 if (range > max) { | |
129 qc->error = NGX_QUIC_ERR_FRAME_ENCODING_ERROR; | |
130 ngx_log_error(NGX_LOG_INFO, c->log, 0, | |
131 "quic invalid range:%ui in ack frame", i); | |
132 return NGX_ERROR; | |
133 } | |
134 | |
135 min = max - range; | |
136 | |
137 if (ngx_quic_handle_ack_frame_range(c, ctx, min, max, &send_time) | |
138 != NGX_OK) | |
139 { | |
140 return NGX_ERROR; | |
141 } | |
142 } | |
143 | |
144 return ngx_quic_detect_lost(c); | |
145 } | |
146 | |
147 | |
148 static void | |
149 ngx_quic_rtt_sample(ngx_connection_t *c, ngx_quic_ack_frame_t *ack, | |
150 enum ssl_encryption_level_t level, ngx_msec_t send_time) | |
151 { | |
152 ngx_msec_t latest_rtt, ack_delay, adjusted_rtt, rttvar_sample; | |
153 ngx_quic_connection_t *qc; | |
154 | |
155 qc = ngx_quic_get_connection(c); | |
156 | |
157 latest_rtt = ngx_current_msec - send_time; | |
158 qc->latest_rtt = latest_rtt; | |
159 | |
160 if (qc->min_rtt == NGX_TIMER_INFINITE) { | |
161 qc->min_rtt = latest_rtt; | |
162 qc->avg_rtt = latest_rtt; | |
163 qc->rttvar = latest_rtt / 2; | |
164 | |
165 } else { | |
166 qc->min_rtt = ngx_min(qc->min_rtt, latest_rtt); | |
167 | |
168 ack_delay = ack->delay * (1 << qc->ctp.ack_delay_exponent) / 1000; | |
169 | |
170 if (c->ssl->handshaked) { | |
171 ack_delay = ngx_min(ack_delay, qc->ctp.max_ack_delay); | |
172 } | |
173 | |
174 adjusted_rtt = latest_rtt; | |
175 | |
176 if (qc->min_rtt + ack_delay < latest_rtt) { | |
177 adjusted_rtt -= ack_delay; | |
178 } | |
179 | |
180 qc->avg_rtt = 0.875 * qc->avg_rtt + 0.125 * adjusted_rtt; | |
181 rttvar_sample = ngx_abs((ngx_msec_int_t) (qc->avg_rtt - adjusted_rtt)); | |
182 qc->rttvar = 0.75 * qc->rttvar + 0.25 * rttvar_sample; | |
183 } | |
184 | |
185 ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
186 "quic rtt sample latest:%M min:%M avg:%M var:%M", | |
187 latest_rtt, qc->min_rtt, qc->avg_rtt, qc->rttvar); | |
188 } | |
189 | |
190 | |
191 static ngx_int_t | |
192 ngx_quic_handle_ack_frame_range(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx, | |
193 uint64_t min, uint64_t max, ngx_msec_t *send_time) | |
194 { | |
195 ngx_uint_t found; | |
196 ngx_queue_t *q; | |
197 ngx_quic_frame_t *f; | |
198 ngx_quic_connection_t *qc; | |
199 | |
200 qc = ngx_quic_get_connection(c); | |
201 | |
202 *send_time = NGX_TIMER_INFINITE; | |
203 found = 0; | |
204 | |
205 q = ngx_queue_last(&ctx->sent); | |
206 | |
207 while (q != ngx_queue_sentinel(&ctx->sent)) { | |
208 | |
209 f = ngx_queue_data(q, ngx_quic_frame_t, queue); | |
210 q = ngx_queue_prev(q); | |
211 | |
212 if (f->pnum >= min && f->pnum <= max) { | |
213 ngx_quic_congestion_ack(c, f); | |
214 | |
215 switch (f->type) { | |
216 case NGX_QUIC_FT_ACK: | |
217 case NGX_QUIC_FT_ACK_ECN: | |
218 ngx_quic_drop_ack_ranges(c, ctx, f->u.ack.largest); | |
219 break; | |
220 | |
221 case NGX_QUIC_FT_STREAM0: | |
222 case NGX_QUIC_FT_STREAM1: | |
223 case NGX_QUIC_FT_STREAM2: | |
224 case NGX_QUIC_FT_STREAM3: | |
225 case NGX_QUIC_FT_STREAM4: | |
226 case NGX_QUIC_FT_STREAM5: | |
227 case NGX_QUIC_FT_STREAM6: | |
228 case NGX_QUIC_FT_STREAM7: | |
229 ngx_quic_handle_stream_ack(c, f); | |
230 break; | |
231 } | |
232 | |
233 if (f->pnum == max) { | |
234 *send_time = f->last; | |
235 } | |
236 | |
237 ngx_queue_remove(&f->queue); | |
238 ngx_quic_free_frame(c, f); | |
239 found = 1; | |
240 } | |
241 } | |
242 | |
243 if (!found) { | |
244 | |
245 if (max < ctx->pnum) { | |
246 /* duplicate ACK or ACK for non-ack-eliciting frame */ | |
247 return NGX_OK; | |
248 } | |
249 | |
250 ngx_log_error(NGX_LOG_INFO, c->log, 0, | |
251 "quic ACK for the packet not sent"); | |
252 | |
253 qc->error = NGX_QUIC_ERR_PROTOCOL_VIOLATION; | |
254 qc->error_ftype = NGX_QUIC_FT_ACK; | |
255 qc->error_reason = "unknown packet number"; | |
256 | |
257 return NGX_ERROR; | |
258 } | |
259 | |
260 if (!qc->push.timer_set) { | |
261 ngx_post_event(&qc->push, &ngx_posted_events); | |
262 } | |
263 | |
264 qc->pto_count = 0; | |
265 | |
266 return NGX_OK; | |
267 } | |
268 | |
269 | |
270 void | |
271 ngx_quic_congestion_ack(ngx_connection_t *c, ngx_quic_frame_t *f) | |
272 { | |
273 ngx_msec_t timer; | |
274 ngx_quic_congestion_t *cg; | |
275 ngx_quic_connection_t *qc; | |
276 | |
277 if (f->plen == 0) { | |
278 return; | |
279 } | |
280 | |
281 qc = ngx_quic_get_connection(c); | |
282 cg = &qc->congestion; | |
283 | |
284 cg->in_flight -= f->plen; | |
285 | |
286 timer = f->last - cg->recovery_start; | |
287 | |
288 if ((ngx_msec_int_t) timer <= 0) { | |
289 ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
290 "quic congestion ack recovery win:%uz ss:%z if:%uz", | |
291 cg->window, cg->ssthresh, cg->in_flight); | |
292 | |
293 return; | |
294 } | |
295 | |
296 if (cg->window < cg->ssthresh) { | |
297 cg->window += f->plen; | |
298 | |
299 ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
300 "quic congestion slow start win:%uz ss:%z if:%uz", | |
301 cg->window, cg->ssthresh, cg->in_flight); | |
302 | |
303 } else { | |
304 cg->window += qc->tp.max_udp_payload_size * f->plen / cg->window; | |
305 | |
306 ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
307 "quic congestion avoidance win:%uz ss:%z if:%uz", | |
308 cg->window, cg->ssthresh, cg->in_flight); | |
309 } | |
310 | |
311 /* prevent recovery_start from wrapping */ | |
312 | |
313 timer = cg->recovery_start - ngx_current_msec + qc->tp.max_idle_timeout * 2; | |
314 | |
315 if ((ngx_msec_int_t) timer < 0) { | |
316 cg->recovery_start = ngx_current_msec - qc->tp.max_idle_timeout * 2; | |
317 } | |
318 } | |
319 | |
320 | |
321 static void | |
322 ngx_quic_drop_ack_ranges(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx, | |
323 uint64_t pn) | |
324 { | |
325 uint64_t base; | |
326 ngx_uint_t i, smallest, largest; | |
327 ngx_quic_ack_range_t *r; | |
328 | |
329 ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
330 "quic ngx_quic_drop_ack_ranges pn:%uL largest:%uL" | |
331 " fr:%uL nranges:%ui", pn, ctx->largest_range, | |
332 ctx->first_range, ctx->nranges); | |
333 | |
334 base = ctx->largest_range; | |
335 | |
336 if (base == NGX_QUIC_UNSET_PN) { | |
337 return; | |
338 } | |
339 | |
340 if (ctx->pending_ack != NGX_QUIC_UNSET_PN && pn >= ctx->pending_ack) { | |
341 ctx->pending_ack = NGX_QUIC_UNSET_PN; | |
342 } | |
343 | |
344 largest = base; | |
345 smallest = largest - ctx->first_range; | |
346 | |
347 if (pn >= largest) { | |
348 ctx->largest_range = NGX_QUIC_UNSET_PN; | |
349 ctx->first_range = 0; | |
350 ctx->nranges = 0; | |
351 return; | |
352 } | |
353 | |
354 if (pn >= smallest) { | |
355 ctx->first_range = largest - pn - 1; | |
356 ctx->nranges = 0; | |
357 return; | |
358 } | |
359 | |
360 for (i = 0; i < ctx->nranges; i++) { | |
361 r = &ctx->ranges[i]; | |
362 | |
363 largest = smallest - r->gap - 2; | |
364 smallest = largest - r->range; | |
365 | |
366 if (pn >= largest) { | |
367 ctx->nranges = i; | |
368 return; | |
369 } | |
370 if (pn >= smallest) { | |
371 r->range = largest - pn - 1; | |
372 ctx->nranges = i + 1; | |
373 return; | |
374 } | |
375 } | |
376 } | |
377 | |
378 | |
379 static ngx_int_t | |
380 ngx_quic_detect_lost(ngx_connection_t *c) | |
381 { | |
382 ngx_uint_t i; | |
383 ngx_msec_t now, wait, thr; | |
384 ngx_queue_t *q; | |
385 ngx_quic_frame_t *start; | |
386 ngx_quic_send_ctx_t *ctx; | |
387 ngx_quic_connection_t *qc; | |
388 | |
389 qc = ngx_quic_get_connection(c); | |
390 now = ngx_current_msec; | |
391 thr = ngx_quic_lost_threshold(qc); | |
392 | |
393 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) { | |
394 | |
395 ctx = &qc->send_ctx[i]; | |
396 | |
397 if (ctx->largest_ack == NGX_QUIC_UNSET_PN) { | |
398 continue; | |
399 } | |
400 | |
401 while (!ngx_queue_empty(&ctx->sent)) { | |
402 | |
403 q = ngx_queue_head(&ctx->sent); | |
404 start = ngx_queue_data(q, ngx_quic_frame_t, queue); | |
405 | |
406 if (start->pnum > ctx->largest_ack) { | |
407 break; | |
408 } | |
409 | |
410 wait = start->last + thr - now; | |
411 | |
412 ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
413 "quic detect_lost pnum:%uL thr:%M wait:%i level:%d", | |
414 start->pnum, thr, (ngx_int_t) wait, start->level); | |
415 | |
416 if ((ngx_msec_int_t) wait > 0 | |
417 && ctx->largest_ack - start->pnum < NGX_QUIC_PKT_THR) | |
418 { | |
419 break; | |
420 } | |
421 | |
422 ngx_quic_resend_frames(c, ctx); | |
423 } | |
424 } | |
425 | |
426 ngx_quic_set_lost_timer(c); | |
427 | |
428 return NGX_OK; | |
429 } | |
430 | |
431 | |
432 void | |
433 ngx_quic_resend_frames(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx) | |
434 { | |
435 size_t n; | |
436 ngx_buf_t *b; | |
437 ngx_queue_t *q; | |
438 ngx_quic_frame_t *f, *start; | |
439 ngx_quic_stream_t *sn; | |
440 ngx_quic_connection_t *qc; | |
441 | |
442 qc = ngx_quic_get_connection(c); | |
443 q = ngx_queue_head(&ctx->sent); | |
444 start = ngx_queue_data(q, ngx_quic_frame_t, queue); | |
445 | |
446 ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
447 "quic resend packet pnum:%uL", start->pnum); | |
448 | |
449 ngx_quic_congestion_lost(c, start); | |
450 | |
451 do { | |
452 f = ngx_queue_data(q, ngx_quic_frame_t, queue); | |
453 | |
454 if (f->pnum != start->pnum) { | |
455 break; | |
456 } | |
457 | |
458 q = ngx_queue_next(q); | |
459 | |
460 ngx_queue_remove(&f->queue); | |
461 | |
462 switch (f->type) { | |
463 case NGX_QUIC_FT_ACK: | |
464 case NGX_QUIC_FT_ACK_ECN: | |
465 if (ctx->level == ssl_encryption_application) { | |
466 /* force generation of most recent acknowledgment */ | |
467 ctx->send_ack = NGX_QUIC_MAX_ACK_GAP; | |
468 } | |
469 | |
470 ngx_quic_free_frame(c, f); | |
471 break; | |
472 | |
473 case NGX_QUIC_FT_PING: | |
474 case NGX_QUIC_FT_PATH_RESPONSE: | |
475 case NGX_QUIC_FT_CONNECTION_CLOSE: | |
476 ngx_quic_free_frame(c, f); | |
477 break; | |
478 | |
479 case NGX_QUIC_FT_MAX_DATA: | |
480 f->u.max_data.max_data = qc->streams.recv_max_data; | |
481 ngx_quic_queue_frame(qc, f); | |
482 break; | |
483 | |
484 case NGX_QUIC_FT_MAX_STREAMS: | |
485 case NGX_QUIC_FT_MAX_STREAMS2: | |
486 f->u.max_streams.limit = f->u.max_streams.bidi | |
487 ? qc->streams.client_max_streams_bidi | |
488 : qc->streams.client_max_streams_uni; | |
489 ngx_quic_queue_frame(qc, f); | |
490 break; | |
491 | |
492 case NGX_QUIC_FT_MAX_STREAM_DATA: | |
493 sn = ngx_quic_find_stream(&qc->streams.tree, | |
494 f->u.max_stream_data.id); | |
495 if (sn == NULL) { | |
496 ngx_quic_free_frame(c, f); | |
497 break; | |
498 } | |
499 | |
500 b = sn->b; | |
501 n = sn->fs.received + (b->pos - b->start) + (b->end - b->last); | |
502 | |
503 if (f->u.max_stream_data.limit < n) { | |
504 f->u.max_stream_data.limit = n; | |
505 } | |
506 | |
507 ngx_quic_queue_frame(qc, f); | |
508 break; | |
509 | |
510 case NGX_QUIC_FT_STREAM0: | |
511 case NGX_QUIC_FT_STREAM1: | |
512 case NGX_QUIC_FT_STREAM2: | |
513 case NGX_QUIC_FT_STREAM3: | |
514 case NGX_QUIC_FT_STREAM4: | |
515 case NGX_QUIC_FT_STREAM5: | |
516 case NGX_QUIC_FT_STREAM6: | |
517 case NGX_QUIC_FT_STREAM7: | |
518 sn = ngx_quic_find_stream(&qc->streams.tree, f->u.stream.stream_id); | |
519 | |
520 if (sn && sn->c->write->error) { | |
521 /* RESET_STREAM was sent */ | |
522 ngx_quic_free_frame(c, f); | |
523 break; | |
524 } | |
525 | |
526 /* fall through */ | |
527 | |
528 default: | |
529 ngx_queue_insert_tail(&ctx->frames, &f->queue); | |
530 } | |
531 | |
532 } while (q != ngx_queue_sentinel(&ctx->sent)); | |
533 | |
534 if (qc->closing) { | |
535 return; | |
536 } | |
537 | |
538 ngx_post_event(&qc->push, &ngx_posted_events); | |
539 } | |
540 | |
541 | |
542 static void | |
543 ngx_quic_congestion_lost(ngx_connection_t *c, ngx_quic_frame_t *f) | |
544 { | |
545 ngx_msec_t timer; | |
546 ngx_quic_congestion_t *cg; | |
547 ngx_quic_connection_t *qc; | |
548 | |
549 if (f->plen == 0) { | |
550 return; | |
551 } | |
552 | |
553 qc = ngx_quic_get_connection(c); | |
554 cg = &qc->congestion; | |
555 | |
556 cg->in_flight -= f->plen; | |
557 f->plen = 0; | |
558 | |
559 timer = f->last - cg->recovery_start; | |
560 | |
561 if ((ngx_msec_int_t) timer <= 0) { | |
562 ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
563 "quic congestion lost recovery win:%uz ss:%z if:%uz", | |
564 cg->window, cg->ssthresh, cg->in_flight); | |
565 | |
566 return; | |
567 } | |
568 | |
569 cg->recovery_start = ngx_current_msec; | |
570 cg->window /= 2; | |
571 | |
572 if (cg->window < qc->tp.max_udp_payload_size * 2) { | |
573 cg->window = qc->tp.max_udp_payload_size * 2; | |
574 } | |
575 | |
576 cg->ssthresh = cg->window; | |
577 | |
578 ngx_log_debug3(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
579 "quic congestion lost win:%uz ss:%z if:%uz", | |
580 cg->window, cg->ssthresh, cg->in_flight); | |
581 } | |
582 | |
583 | |
584 void | |
585 ngx_quic_set_lost_timer(ngx_connection_t *c) | |
586 { | |
587 ngx_uint_t i; | |
588 ngx_msec_t now; | |
589 ngx_queue_t *q; | |
590 ngx_msec_int_t lost, pto, w; | |
591 ngx_quic_frame_t *f; | |
592 ngx_quic_send_ctx_t *ctx; | |
593 ngx_quic_connection_t *qc; | |
594 | |
595 qc = ngx_quic_get_connection(c); | |
596 now = ngx_current_msec; | |
597 | |
598 lost = -1; | |
599 pto = -1; | |
600 | |
601 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) { | |
602 ctx = &qc->send_ctx[i]; | |
603 | |
604 if (ngx_queue_empty(&ctx->sent)) { | |
605 continue; | |
606 } | |
607 | |
608 if (ctx->largest_ack != NGX_QUIC_UNSET_PN) { | |
609 q = ngx_queue_head(&ctx->sent); | |
610 f = ngx_queue_data(q, ngx_quic_frame_t, queue); | |
611 w = (ngx_msec_int_t) (f->last + ngx_quic_lost_threshold(qc) - now); | |
612 | |
613 if (f->pnum <= ctx->largest_ack) { | |
614 if (w < 0 || ctx->largest_ack - f->pnum >= NGX_QUIC_PKT_THR) { | |
615 w = 0; | |
616 } | |
617 | |
618 if (lost == -1 || w < lost) { | |
619 lost = w; | |
620 } | |
621 } | |
622 } | |
623 | |
624 q = ngx_queue_last(&ctx->sent); | |
625 f = ngx_queue_data(q, ngx_quic_frame_t, queue); | |
626 w = (ngx_msec_int_t) (f->last + ngx_quic_pto(c, ctx) - now); | |
627 | |
628 if (w < 0) { | |
629 w = 0; | |
630 } | |
631 | |
632 if (pto == -1 || w < pto) { | |
633 pto = w; | |
634 } | |
635 } | |
636 | |
637 if (qc->pto.timer_set) { | |
638 ngx_del_timer(&qc->pto); | |
639 } | |
640 | |
641 if (lost != -1) { | |
642 ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
643 "quic lost timer lost:%M", lost); | |
644 | |
645 qc->pto.handler = ngx_quic_lost_handler; | |
646 ngx_add_timer(&qc->pto, lost); | |
647 return; | |
648 } | |
649 | |
650 if (pto != -1) { | |
651 ngx_log_debug1(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
652 "quic lost timer pto:%M", pto); | |
653 | |
654 qc->pto.handler = ngx_quic_pto_handler; | |
655 ngx_add_timer(&qc->pto, pto); | |
656 return; | |
657 } | |
658 | |
659 ngx_log_debug0(NGX_LOG_DEBUG_EVENT, c->log, 0, "quic lost timer unset"); | |
660 } | |
661 | |
662 | |
663 ngx_msec_t | |
664 ngx_quic_pto(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx) | |
665 { | |
666 ngx_msec_t duration; | |
667 ngx_quic_connection_t *qc; | |
668 | |
669 qc = ngx_quic_get_connection(c); | |
670 | |
671 /* PTO calculation: quic-recovery, Appendix 8 */ | |
672 duration = qc->avg_rtt; | |
673 | |
674 duration += ngx_max(4 * qc->rttvar, NGX_QUIC_TIME_GRANULARITY); | |
675 duration <<= qc->pto_count; | |
676 | |
677 if (qc->congestion.in_flight == 0) { /* no in-flight packets */ | |
678 return duration; | |
679 } | |
680 | |
681 if (ctx->level == ssl_encryption_application && c->ssl->handshaked) { | |
682 duration += qc->ctp.max_ack_delay << qc->pto_count; | |
683 } | |
684 | |
685 return duration; | |
686 } | |
687 | |
688 | |
689 static | |
690 void ngx_quic_lost_handler(ngx_event_t *ev) | |
691 { | |
692 ngx_connection_t *c; | |
693 | |
694 ngx_log_debug0(NGX_LOG_DEBUG_EVENT, ev->log, 0, "quic lost timer"); | |
695 | |
696 c = ev->data; | |
697 | |
698 if (ngx_quic_detect_lost(c) != NGX_OK) { | |
699 ngx_quic_close_connection(c, NGX_ERROR); | |
700 } | |
701 | |
702 ngx_quic_connstate_dbg(c); | |
703 } | |
704 | |
705 | |
706 void | |
707 ngx_quic_pto_handler(ngx_event_t *ev) | |
708 { | |
709 ngx_uint_t i; | |
710 ngx_msec_t now; | |
711 ngx_queue_t *q, *next; | |
712 ngx_connection_t *c; | |
713 ngx_quic_frame_t *f; | |
714 ngx_quic_send_ctx_t *ctx; | |
715 ngx_quic_connection_t *qc; | |
716 | |
717 ngx_log_debug0(NGX_LOG_DEBUG_EVENT, ev->log, 0, "quic pto timer"); | |
718 | |
719 c = ev->data; | |
720 qc = ngx_quic_get_connection(c); | |
721 now = ngx_current_msec; | |
722 | |
723 for (i = 0; i < NGX_QUIC_SEND_CTX_LAST; i++) { | |
724 | |
725 ctx = &qc->send_ctx[i]; | |
726 | |
727 if (ngx_queue_empty(&ctx->sent)) { | |
728 continue; | |
729 } | |
730 | |
731 q = ngx_queue_head(&ctx->sent); | |
732 f = ngx_queue_data(q, ngx_quic_frame_t, queue); | |
733 | |
734 if (f->pnum <= ctx->largest_ack | |
735 && ctx->largest_ack != NGX_QUIC_UNSET_PN) | |
736 { | |
737 continue; | |
738 } | |
739 | |
740 if ((ngx_msec_int_t) (f->last + ngx_quic_pto(c, ctx) - now) > 0) { | |
741 continue; | |
742 } | |
743 | |
744 ngx_log_debug2(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
745 "quic pto %s pto_count:%ui", | |
746 ngx_quic_level_name(ctx->level), qc->pto_count); | |
747 | |
748 for (q = ngx_queue_head(&ctx->frames); | |
749 q != ngx_queue_sentinel(&ctx->frames); | |
750 /* void */) | |
751 { | |
752 next = ngx_queue_next(q); | |
753 f = ngx_queue_data(q, ngx_quic_frame_t, queue); | |
754 | |
755 if (f->type == NGX_QUIC_FT_PING) { | |
756 ngx_queue_remove(q); | |
757 ngx_quic_free_frame(c, f); | |
758 } | |
759 | |
760 q = next; | |
761 } | |
762 | |
763 for (q = ngx_queue_head(&ctx->sent); | |
764 q != ngx_queue_sentinel(&ctx->sent); | |
765 /* void */) | |
766 { | |
767 next = ngx_queue_next(q); | |
768 f = ngx_queue_data(q, ngx_quic_frame_t, queue); | |
769 | |
770 if (f->type == NGX_QUIC_FT_PING) { | |
771 ngx_quic_congestion_lost(c, f); | |
772 ngx_queue_remove(q); | |
773 ngx_quic_free_frame(c, f); | |
774 } | |
775 | |
776 q = next; | |
777 } | |
778 | |
779 /* enforce 2 udp datagrams */ | |
780 | |
781 f = ngx_quic_alloc_frame(c); | |
782 if (f == NULL) { | |
783 break; | |
784 } | |
785 | |
786 f->level = ctx->level; | |
787 f->type = NGX_QUIC_FT_PING; | |
788 f->flush = 1; | |
789 | |
790 ngx_quic_queue_frame(qc, f); | |
791 | |
792 f = ngx_quic_alloc_frame(c); | |
793 if (f == NULL) { | |
794 break; | |
795 } | |
796 | |
797 f->level = ctx->level; | |
798 f->type = NGX_QUIC_FT_PING; | |
799 | |
800 ngx_quic_queue_frame(qc, f); | |
801 } | |
802 | |
803 qc->pto_count++; | |
804 | |
805 ngx_quic_connstate_dbg(c); | |
806 } | |
807 | |
808 | |
809 ngx_int_t | |
810 ngx_quic_ack_packet(ngx_connection_t *c, ngx_quic_header_t *pkt) | |
811 { | |
812 uint64_t base, largest, smallest, gs, ge, gap, range, pn; | |
813 uint64_t prev_pending; | |
814 ngx_uint_t i, nr; | |
815 ngx_quic_send_ctx_t *ctx; | |
816 ngx_quic_ack_range_t *r; | |
817 ngx_quic_connection_t *qc; | |
818 | |
819 c->log->action = "preparing ack"; | |
820 | |
821 qc = ngx_quic_get_connection(c); | |
822 | |
823 ctx = ngx_quic_get_send_ctx(qc, pkt->level); | |
824 | |
825 ngx_log_debug4(NGX_LOG_DEBUG_EVENT, c->log, 0, | |
826 "quic ngx_quic_ack_packet pn:%uL largest %L fr:%uL" | |
827 " nranges:%ui", pkt->pn, (int64_t) ctx->largest_range, | |
828 ctx->first_range, ctx->nranges); | |
829 | |
830 prev_pending = ctx->pending_ack; | |
831 | |
832 if (pkt->need_ack) { | |
833 | |
834 ngx_post_event(&qc->push, &ngx_posted_events); | |
835 | |
836 if (ctx->send_ack == 0) { | |
837 ctx->ack_delay_start = ngx_current_msec; | |
838 } | |
839 | |
840 ctx->send_ack++; | |
841 | |
842 if (ctx->pending_ack == NGX_QUIC_UNSET_PN | |
843 || ctx->pending_ack < pkt->pn) | |
844 { | |
845 ctx->pending_ack = pkt->pn; | |
846 } | |
847 } | |
848 | |
849 base = ctx->largest_range; | |
850 pn = pkt->pn; | |
851 | |
852 if (base == NGX_QUIC_UNSET_PN) { | |
853 ctx->largest_range = pn; | |
854 ctx->largest_received = pkt->received; | |
855 return NGX_OK; | |
856 } | |
857 | |
858 if (base == pn) { | |
859 return NGX_OK; | |
860 } | |
861 | |
862 largest = base; | |
863 smallest = largest - ctx->first_range; | |
864 | |
865 if (pn > base) { | |
866 | |
867 if (pn - base == 1) { | |
868 ctx->first_range++; | |
869 ctx->largest_range = pn; | |
870 ctx->largest_received = pkt->received; | |
871 | |
872 return NGX_OK; | |
873 | |
874 } else { | |
875 /* new gap in front of current largest */ | |
876 | |
877 /* no place for new range, send current range as is */ | |
878 if (ctx->nranges == NGX_QUIC_MAX_RANGES) { | |
879 | |
880 if (prev_pending != NGX_QUIC_UNSET_PN) { | |
881 if (ngx_quic_send_ack(c, ctx) != NGX_OK) { | |
882 return NGX_ERROR; | |
883 } | |
884 } | |
885 | |
886 if (prev_pending == ctx->pending_ack || !pkt->need_ack) { | |
887 ctx->pending_ack = NGX_QUIC_UNSET_PN; | |
888 } | |
889 } | |
890 | |
891 gap = pn - base - 2; | |
892 range = ctx->first_range; | |
893 | |
894 ctx->first_range = 0; | |
895 ctx->largest_range = pn; | |
896 ctx->largest_received = pkt->received; | |
897 | |
898 /* packet is out of order, force send */ | |
899 if (pkt->need_ack) { | |
900 ctx->send_ack = NGX_QUIC_MAX_ACK_GAP; | |
901 } | |
902 | |
903 i = 0; | |
904 | |
905 goto insert; | |
906 } | |
907 } | |
908 | |
909 /* pn < base, perform lookup in existing ranges */ | |
910 | |
911 /* packet is out of order */ | |
912 if (pkt->need_ack) { | |
913 ctx->send_ack = NGX_QUIC_MAX_ACK_GAP; | |
914 } | |
915 | |
916 if (pn >= smallest && pn <= largest) { | |
917 return NGX_OK; | |
918 } | |
919 | |
920 #if (NGX_SUPPRESS_WARN) | |
921 r = NULL; | |
922 #endif | |
923 | |
924 for (i = 0; i < ctx->nranges; i++) { | |
925 r = &ctx->ranges[i]; | |
926 | |
927 ge = smallest - 1; | |
928 gs = ge - r->gap; | |
929 | |
930 if (pn >= gs && pn <= ge) { | |
931 | |
932 if (gs == ge) { | |
933 /* gap size is exactly one packet, now filled */ | |
934 | |
935 /* data moves to previous range, current is removed */ | |
936 | |
937 if (i == 0) { | |
938 ctx->first_range += r->range + 2; | |
939 | |
940 } else { | |
941 ctx->ranges[i - 1].range += r->range + 2; | |
942 } | |
943 | |
944 nr = ctx->nranges - i - 1; | |
945 if (nr) { | |
946 ngx_memmove(&ctx->ranges[i], &ctx->ranges[i + 1], | |
947 sizeof(ngx_quic_ack_range_t) * nr); | |
948 } | |
949 | |
950 ctx->nranges--; | |
951 | |
952 } else if (pn == gs) { | |
953 /* current gap shrinks from tail (current range grows) */ | |
954 r->gap--; | |
955 r->range++; | |
956 | |
957 } else if (pn == ge) { | |
958 /* current gap shrinks from head (previous range grows) */ | |
959 r->gap--; | |
960 | |
961 if (i == 0) { | |
962 ctx->first_range++; | |
963 | |
964 } else { | |
965 ctx->ranges[i - 1].range++; | |
966 } | |
967 | |
968 } else { | |
969 /* current gap is split into two parts */ | |
970 | |
971 gap = ge - pn - 1; | |
972 range = 0; | |
973 | |
974 if (ctx->nranges == NGX_QUIC_MAX_RANGES) { | |
975 if (prev_pending != NGX_QUIC_UNSET_PN) { | |
976 if (ngx_quic_send_ack(c, ctx) != NGX_OK) { | |
977 return NGX_ERROR; | |
978 } | |
979 } | |
980 | |
981 if (prev_pending == ctx->pending_ack || !pkt->need_ack) { | |
982 ctx->pending_ack = NGX_QUIC_UNSET_PN; | |
983 } | |
984 } | |
985 | |
986 r->gap = pn - gs - 1; | |
987 goto insert; | |
988 } | |
989 | |
990 return NGX_OK; | |
991 } | |
992 | |
993 largest = smallest - r->gap - 2; | |
994 smallest = largest - r->range; | |
995 | |
996 if (pn >= smallest && pn <= largest) { | |
997 /* this packet number is already known */ | |
998 return NGX_OK; | |
999 } | |
1000 | |
1001 } | |
1002 | |
1003 if (pn == smallest - 1) { | |
1004 /* extend first or last range */ | |
1005 | |
1006 if (i == 0) { | |
1007 ctx->first_range++; | |
1008 | |
1009 } else { | |
1010 r->range++; | |
1011 } | |
1012 | |
1013 return NGX_OK; | |
1014 } | |
1015 | |
1016 /* nothing found, add new range at the tail */ | |
1017 | |
1018 if (ctx->nranges == NGX_QUIC_MAX_RANGES) { | |
1019 /* packet is too old to keep it */ | |
1020 | |
1021 if (pkt->need_ack) { | |
1022 return ngx_quic_send_ack_range(c, ctx, pn, pn); | |
1023 } | |
1024 | |
1025 return NGX_OK; | |
1026 } | |
1027 | |
1028 gap = smallest - 2 - pn; | |
1029 range = 0; | |
1030 | |
1031 insert: | |
1032 | |
1033 if (ctx->nranges < NGX_QUIC_MAX_RANGES) { | |
1034 ctx->nranges++; | |
1035 } | |
1036 | |
1037 ngx_memmove(&ctx->ranges[i + 1], &ctx->ranges[i], | |
1038 sizeof(ngx_quic_ack_range_t) * (ctx->nranges - i - 1)); | |
1039 | |
1040 ctx->ranges[i].gap = gap; | |
1041 ctx->ranges[i].range = range; | |
1042 | |
1043 return NGX_OK; | |
1044 } | |
1045 | |
1046 | |
1047 ngx_int_t | |
1048 ngx_quic_generate_ack(ngx_connection_t *c, ngx_quic_send_ctx_t *ctx) | |
1049 { | |
1050 ngx_msec_t delay; | |
1051 ngx_quic_connection_t *qc; | |
1052 | |
1053 if (!ctx->send_ack) { | |
1054 return NGX_OK; | |
1055 } | |
1056 | |
1057 if (ctx->level == ssl_encryption_application) { | |
1058 | |
1059 delay = ngx_current_msec - ctx->ack_delay_start; | |
1060 qc = ngx_quic_get_connection(c); | |
1061 | |
1062 if (ctx->send_ack < NGX_QUIC_MAX_ACK_GAP | |
1063 && delay < qc->tp.max_ack_delay) | |
1064 { | |
1065 if (!qc->push.timer_set && !qc->closing) { | |
1066 ngx_add_timer(&qc->push, | |
1067 qc->tp.max_ack_delay - delay); | |
1068 } | |
1069 | |
1070 return NGX_OK; | |
1071 } | |
1072 } | |
1073 | |
1074 if (ngx_quic_send_ack(c, ctx) != NGX_OK) { | |
1075 return NGX_ERROR; | |
1076 } | |
1077 | |
1078 ctx->send_ack = 0; | |
1079 | |
1080 return NGX_OK; | |
1081 } |