1 /*
2  * Copyright (c) 2017 Fastly, Kazuho Oku
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a copy
5  * of this software and associated documentation files (the "Software"), to
6  * deal in the Software without restriction, including without limitation the
7  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8  * sell copies of the Software, and to permit persons to whom the Software is
9  * furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20  * IN THE SOFTWARE.
21  */
22 #include <assert.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include "picotls.h"
26 #include "quicly/constants.h"
27 #include "quicly/sendstate.h"
28 
quicly_sendstate_init(quicly_sendstate_t * state)29 void quicly_sendstate_init(quicly_sendstate_t *state)
30 {
31     quicly_ranges_init_with_range(&state->acked, 0, 0);
32     quicly_ranges_init(&state->pending);
33     state->size_inflight = 0;
34     state->final_size = UINT64_MAX;
35 }
36 
quicly_sendstate_init_closed(quicly_sendstate_t * state)37 void quicly_sendstate_init_closed(quicly_sendstate_t *state)
38 {
39     quicly_sendstate_init(state);
40     state->acked.ranges[0].end = 1;
41     state->final_size = 0;
42 }
43 
quicly_sendstate_dispose(quicly_sendstate_t * state)44 void quicly_sendstate_dispose(quicly_sendstate_t *state)
45 {
46     quicly_ranges_clear(&state->acked);
47     quicly_ranges_clear(&state->pending);
48     state->final_size = 0;
49     state->size_inflight = 0;
50 }
51 
quicly_sendstate_activate(quicly_sendstate_t * state)52 int quicly_sendstate_activate(quicly_sendstate_t *state)
53 {
54     uint64_t end_off = state->final_size;
55 
56     /* take EOS position into account */
57     if (end_off != UINT64_MAX)
58         ++end_off;
59 
60     /* do nothing if already active */
61     if (state->pending.num_ranges != 0 && state->pending.ranges[state->pending.num_ranges - 1].end == end_off)
62         return 0;
63 
64     return quicly_ranges_add(&state->pending, state->size_inflight, end_off);
65 }
66 
quicly_sendstate_shutdown(quicly_sendstate_t * state,uint64_t final_size)67 int quicly_sendstate_shutdown(quicly_sendstate_t *state, uint64_t final_size)
68 {
69     int ret;
70 
71     assert(quicly_sendstate_is_open(state));
72     assert(state->size_inflight <= final_size);
73 
74     if (state->pending.num_ranges != 0 && state->pending.ranges[state->pending.num_ranges - 1].end == UINT64_MAX) {
75         state->pending.ranges[state->pending.num_ranges - 1].end = final_size + 1;
76     } else {
77         if ((ret = quicly_ranges_add(&state->pending, state->size_inflight, final_size + 1)) != 0)
78             return ret;
79     }
80 
81     state->final_size = final_size;
82     return 0;
83 }
84 
quicly_sendstate_reset(quicly_sendstate_t * state)85 void quicly_sendstate_reset(quicly_sendstate_t *state)
86 {
87     int ret;
88 
89     if (state->final_size == UINT64_MAX)
90         state->final_size = state->size_inflight;
91 
92     ret = quicly_ranges_add(&state->acked, 0, state->final_size + 1);
93     assert(ret == 0 && "guaranteed to succeed, because the numebr of ranges never increases");
94     quicly_ranges_clear(&state->pending);
95 }
96 
check_amount_of_state(quicly_sendstate_t * state)97 static int check_amount_of_state(quicly_sendstate_t *state)
98 {
99     size_t num_ranges = state->acked.num_ranges + state->pending.num_ranges;
100 
101     /* Bail out if number of gaps are small.
102      * In case of HTTP/3, the worst case is when each HTTP request is received as a separate QUIC packet, and sending a small STREAM
103      * frame carrying a HPACK encoder / decoder in response. If half of those STREAM frames are lost (note: loss of every other
104      * packet can happen during slow start), `num_ranges` can become as large as `request_concurrency * 2`, as each gaps will be
105      * recognized in `acked.num_ranges` and `pending.num_ranges`. */
106     if (PTLS_LIKELY(num_ranges < 256))
107         return 0;
108 
109     /* When there are large number of gaps, make sure that the amount of state retained in quicly is relatively smaller than the
110      * amount of state retained by application (in form of the stream-level send buffer). 512 is used as the threshold, based on the
111      * assumption that the STREAM frames that have been sent are on average at least 512 bytes long, when seeing excess number of
112      * gaps. */
113     int64_t bytes_buffered = (int64_t)state->size_inflight - (int64_t)state->acked.ranges[0].end;
114     if ((int64_t)num_ranges * 128 > bytes_buffered)
115         return QUICLY_ERROR_STATE_EXHAUSTION;
116 
117     return 0;
118 }
119 
quicly_sendstate_acked(quicly_sendstate_t * state,quicly_sendstate_sent_t * args,size_t * bytes_to_shift)120 int quicly_sendstate_acked(quicly_sendstate_t *state, quicly_sendstate_sent_t *args, size_t *bytes_to_shift)
121 {
122     uint64_t prev_sent_upto = state->acked.ranges[0].end;
123     int ret;
124 
125     /* adjust acked and pending ranges */
126     if ((ret = quicly_ranges_add(&state->acked, args->start, args->end)) != 0)
127         return ret;
128     if ((ret = quicly_ranges_subtract(&state->pending, args->start, args->end)) != 0)
129         return ret;
130     assert(state->pending.num_ranges == 0 || state->acked.ranges[0].end <= state->pending.ranges[0].start);
131 
132     /* calculate number of bytes that can be retired from the send buffer */
133     if (prev_sent_upto != state->acked.ranges[0].end) {
134         uint64_t sent_upto = state->acked.ranges[0].end;
135         if (sent_upto > state->final_size) {
136             /* adjust EOS position */
137             assert(sent_upto == state->final_size + 1);
138             --sent_upto;
139         }
140         *bytes_to_shift = sent_upto - prev_sent_upto;
141     } else {
142         *bytes_to_shift = 0;
143     }
144 
145     return check_amount_of_state(state);
146 }
147 
quicly_sendstate_lost(quicly_sendstate_t * state,quicly_sendstate_sent_t * args)148 int quicly_sendstate_lost(quicly_sendstate_t *state, quicly_sendstate_sent_t *args)
149 {
150     uint64_t start = args->start, end = args->end;
151     size_t acked_slot = 0;
152     int ret;
153 
154     while (start < end) {
155         if (start < state->acked.ranges[acked_slot].end)
156             start = state->acked.ranges[acked_slot].end;
157         ++acked_slot;
158         if (acked_slot == state->acked.num_ranges || end <= state->acked.ranges[acked_slot].start) {
159             if (start < end) {
160                 if ((ret = quicly_ranges_add(&state->pending, start, end)) != 0)
161                     return ret;
162             }
163             goto Exit;
164         }
165         if (start < state->acked.ranges[acked_slot].start) {
166             if ((ret = quicly_ranges_add(&state->pending, start, state->acked.ranges[acked_slot].start)) != 0)
167                 return ret;
168         }
169     }
170 
171 Exit:
172     assert(state->pending.num_ranges == 0 || state->acked.ranges[0].end <= state->pending.ranges[0].start);
173     return check_amount_of_state(state);
174 }
175