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