Mercurial > hg > nginx

comparison src/event/quic/ngx_event_quic_ack.c @ 8751:bc910a5ec737 quic

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
8750:41807e581de9 8751: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 }