1 /*
2 * ngtcp2
3 *
4 * Copyright (c) 2017 ngtcp2 contributors
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25 #include "ngtcp2_acktr.h"
26
27 #include <assert.h>
28
29 #include "ngtcp2_macro.h"
30
acktr_entry_init(ngtcp2_acktr_entry * ent,int64_t pkt_num,ngtcp2_tstamp tstamp)31 static void acktr_entry_init(ngtcp2_acktr_entry *ent, int64_t pkt_num,
32 ngtcp2_tstamp tstamp) {
33 ent->pkt_num = pkt_num;
34 ent->len = 1;
35 ent->tstamp = tstamp;
36 }
37
ngtcp2_acktr_entry_objalloc_new(ngtcp2_acktr_entry ** ent,int64_t pkt_num,ngtcp2_tstamp tstamp,ngtcp2_objalloc * objalloc)38 int ngtcp2_acktr_entry_objalloc_new(ngtcp2_acktr_entry **ent, int64_t pkt_num,
39 ngtcp2_tstamp tstamp,
40 ngtcp2_objalloc *objalloc) {
41 *ent = ngtcp2_objalloc_acktr_entry_get(objalloc);
42 if (*ent == NULL) {
43 return NGTCP2_ERR_NOMEM;
44 }
45
46 acktr_entry_init(*ent, pkt_num, tstamp);
47
48 return 0;
49 }
50
ngtcp2_acktr_entry_objalloc_del(ngtcp2_acktr_entry * ent,ngtcp2_objalloc * objalloc)51 void ngtcp2_acktr_entry_objalloc_del(ngtcp2_acktr_entry *ent,
52 ngtcp2_objalloc *objalloc) {
53 ngtcp2_objalloc_acktr_entry_release(objalloc, ent);
54 }
55
greater(const ngtcp2_ksl_key * lhs,const ngtcp2_ksl_key * rhs)56 static int greater(const ngtcp2_ksl_key *lhs, const ngtcp2_ksl_key *rhs) {
57 return *(int64_t *)lhs > *(int64_t *)rhs;
58 }
59
ngtcp2_acktr_init(ngtcp2_acktr * acktr,ngtcp2_log * log,const ngtcp2_mem * mem)60 int ngtcp2_acktr_init(ngtcp2_acktr *acktr, ngtcp2_log *log,
61 const ngtcp2_mem *mem) {
62 int rv;
63
64 ngtcp2_objalloc_acktr_entry_init(&acktr->objalloc, 32, mem);
65
66 rv = ngtcp2_ringbuf_init(&acktr->acks, 32, sizeof(ngtcp2_acktr_ack_entry),
67 mem);
68 if (rv != 0) {
69 return rv;
70 }
71
72 ngtcp2_ksl_init(&acktr->ents, greater, sizeof(int64_t), mem);
73
74 acktr->log = log;
75 acktr->mem = mem;
76 acktr->flags = NGTCP2_ACKTR_FLAG_NONE;
77 acktr->first_unacked_ts = UINT64_MAX;
78 acktr->rx_npkt = 0;
79
80 return 0;
81 }
82
ngtcp2_acktr_free(ngtcp2_acktr * acktr)83 void ngtcp2_acktr_free(ngtcp2_acktr *acktr) {
84 #ifdef NOMEMPOOL
85 ngtcp2_ksl_it it;
86 #endif /* NOMEMPOOL */
87
88 if (acktr == NULL) {
89 return;
90 }
91
92 #ifdef NOMEMPOOL
93 for (it = ngtcp2_ksl_begin(&acktr->ents); !ngtcp2_ksl_it_end(&it);
94 ngtcp2_ksl_it_next(&it)) {
95 ngtcp2_acktr_entry_objalloc_del(ngtcp2_ksl_it_get(&it), &acktr->objalloc);
96 }
97 #endif /* NOMEMPOOL */
98
99 ngtcp2_ksl_free(&acktr->ents);
100
101 ngtcp2_ringbuf_free(&acktr->acks);
102
103 ngtcp2_objalloc_free(&acktr->objalloc);
104 }
105
ngtcp2_acktr_add(ngtcp2_acktr * acktr,int64_t pkt_num,int active_ack,ngtcp2_tstamp ts)106 int ngtcp2_acktr_add(ngtcp2_acktr *acktr, int64_t pkt_num, int active_ack,
107 ngtcp2_tstamp ts) {
108 ngtcp2_ksl_it it, prev_it;
109 ngtcp2_acktr_entry *ent, *prev_ent, *delent;
110 int rv;
111 int added = 0;
112
113 if (ngtcp2_ksl_len(&acktr->ents)) {
114 it = ngtcp2_ksl_lower_bound(&acktr->ents, &pkt_num);
115 if (ngtcp2_ksl_it_end(&it)) {
116 ngtcp2_ksl_it_prev(&it);
117 ent = ngtcp2_ksl_it_get(&it);
118
119 assert(ent->pkt_num >= pkt_num + (int64_t)ent->len);
120
121 if (ent->pkt_num == pkt_num + (int64_t)ent->len) {
122 ++ent->len;
123 added = 1;
124 }
125 } else {
126 ent = ngtcp2_ksl_it_get(&it);
127
128 assert(ent->pkt_num != pkt_num);
129
130 if (ngtcp2_ksl_it_begin(&it)) {
131 if (ent->pkt_num + 1 == pkt_num) {
132 ngtcp2_ksl_update_key(&acktr->ents, &ent->pkt_num, &pkt_num);
133 ent->pkt_num = pkt_num;
134 ent->tstamp = ts;
135 ++ent->len;
136 added = 1;
137 }
138 } else {
139 prev_it = it;
140 ngtcp2_ksl_it_prev(&prev_it);
141 prev_ent = ngtcp2_ksl_it_get(&prev_it);
142
143 assert(prev_ent->pkt_num >= pkt_num + (int64_t)prev_ent->len);
144
145 if (ent->pkt_num + 1 == pkt_num) {
146 if (prev_ent->pkt_num == pkt_num + (int64_t)prev_ent->len) {
147 prev_ent->len += ent->len + 1;
148 ngtcp2_ksl_remove_hint(&acktr->ents, NULL, &it, &ent->pkt_num);
149 ngtcp2_acktr_entry_objalloc_del(ent, &acktr->objalloc);
150 added = 1;
151 } else {
152 ngtcp2_ksl_update_key(&acktr->ents, &ent->pkt_num, &pkt_num);
153 ent->pkt_num = pkt_num;
154 ent->tstamp = ts;
155 ++ent->len;
156 added = 1;
157 }
158 } else if (prev_ent->pkt_num == pkt_num + (int64_t)prev_ent->len) {
159 ++prev_ent->len;
160 added = 1;
161 }
162 }
163 }
164 }
165
166 if (!added) {
167 rv = ngtcp2_acktr_entry_objalloc_new(&ent, pkt_num, ts, &acktr->objalloc);
168 if (rv != 0) {
169 return rv;
170 }
171 rv = ngtcp2_ksl_insert(&acktr->ents, NULL, &ent->pkt_num, ent);
172 if (rv != 0) {
173 ngtcp2_acktr_entry_objalloc_del(ent, &acktr->objalloc);
174 return rv;
175 }
176 }
177
178 if (active_ack) {
179 acktr->flags |= NGTCP2_ACKTR_FLAG_ACTIVE_ACK;
180 if (acktr->first_unacked_ts == UINT64_MAX) {
181 acktr->first_unacked_ts = ts;
182 }
183 }
184
185 if (ngtcp2_ksl_len(&acktr->ents) > NGTCP2_ACKTR_MAX_ENT) {
186 it = ngtcp2_ksl_end(&acktr->ents);
187 ngtcp2_ksl_it_prev(&it);
188 delent = ngtcp2_ksl_it_get(&it);
189 ngtcp2_ksl_remove_hint(&acktr->ents, NULL, &it, &delent->pkt_num);
190 ngtcp2_acktr_entry_objalloc_del(delent, &acktr->objalloc);
191 }
192
193 return 0;
194 }
195
ngtcp2_acktr_forget(ngtcp2_acktr * acktr,ngtcp2_acktr_entry * ent)196 void ngtcp2_acktr_forget(ngtcp2_acktr *acktr, ngtcp2_acktr_entry *ent) {
197 ngtcp2_ksl_it it;
198
199 it = ngtcp2_ksl_lower_bound(&acktr->ents, &ent->pkt_num);
200 assert(*(int64_t *)ngtcp2_ksl_it_key(&it) == (int64_t)ent->pkt_num);
201
202 for (; !ngtcp2_ksl_it_end(&it);) {
203 ent = ngtcp2_ksl_it_get(&it);
204 ngtcp2_ksl_remove_hint(&acktr->ents, &it, &it, &ent->pkt_num);
205 ngtcp2_acktr_entry_objalloc_del(ent, &acktr->objalloc);
206 }
207 }
208
ngtcp2_acktr_get(ngtcp2_acktr * acktr)209 ngtcp2_ksl_it ngtcp2_acktr_get(ngtcp2_acktr *acktr) {
210 return ngtcp2_ksl_begin(&acktr->ents);
211 }
212
ngtcp2_acktr_empty(ngtcp2_acktr * acktr)213 int ngtcp2_acktr_empty(ngtcp2_acktr *acktr) {
214 ngtcp2_ksl_it it = ngtcp2_ksl_begin(&acktr->ents);
215 return ngtcp2_ksl_it_end(&it);
216 }
217
ngtcp2_acktr_add_ack(ngtcp2_acktr * acktr,int64_t pkt_num,int64_t largest_ack)218 ngtcp2_acktr_ack_entry *ngtcp2_acktr_add_ack(ngtcp2_acktr *acktr,
219 int64_t pkt_num,
220 int64_t largest_ack) {
221 ngtcp2_acktr_ack_entry *ent = ngtcp2_ringbuf_push_front(&acktr->acks);
222
223 ent->largest_ack = largest_ack;
224 ent->pkt_num = pkt_num;
225
226 return ent;
227 }
228
229 /*
230 * acktr_remove removes |ent| from |acktr|. |it| must point to the
231 * node whose key identifies |ent|. The iterator which points to the
232 * entry next to |ent| is assigned to |it|.
233 */
acktr_remove(ngtcp2_acktr * acktr,ngtcp2_ksl_it * it,ngtcp2_acktr_entry * ent)234 static void acktr_remove(ngtcp2_acktr *acktr, ngtcp2_ksl_it *it,
235 ngtcp2_acktr_entry *ent) {
236 ngtcp2_ksl_remove_hint(&acktr->ents, it, it, &ent->pkt_num);
237 ngtcp2_acktr_entry_objalloc_del(ent, &acktr->objalloc);
238 }
239
acktr_on_ack(ngtcp2_acktr * acktr,ngtcp2_ringbuf * rb,size_t ack_ent_offset)240 static void acktr_on_ack(ngtcp2_acktr *acktr, ngtcp2_ringbuf *rb,
241 size_t ack_ent_offset) {
242 ngtcp2_acktr_ack_entry *ack_ent;
243 ngtcp2_acktr_entry *ent;
244 ngtcp2_ksl_it it;
245
246 assert(ngtcp2_ringbuf_len(rb));
247
248 ack_ent = ngtcp2_ringbuf_get(rb, ack_ent_offset);
249
250 /* Assume that ngtcp2_pkt_validate_ack(fr) returns 0 */
251 it = ngtcp2_ksl_lower_bound(&acktr->ents, &ack_ent->largest_ack);
252 for (; !ngtcp2_ksl_it_end(&it);) {
253 ent = ngtcp2_ksl_it_get(&it);
254 acktr_remove(acktr, &it, ent);
255 }
256
257 if (ngtcp2_ksl_len(&acktr->ents)) {
258 assert(ngtcp2_ksl_it_end(&it));
259
260 ngtcp2_ksl_it_prev(&it);
261 ent = ngtcp2_ksl_it_get(&it);
262 if (ent->pkt_num > ack_ent->largest_ack &&
263 ack_ent->largest_ack >= ent->pkt_num - (int64_t)(ent->len - 1)) {
264 ent->len = (size_t)(ent->pkt_num - ack_ent->largest_ack);
265 }
266 }
267
268 ngtcp2_ringbuf_resize(rb, ack_ent_offset);
269 }
270
ngtcp2_acktr_recv_ack(ngtcp2_acktr * acktr,const ngtcp2_ack * fr)271 void ngtcp2_acktr_recv_ack(ngtcp2_acktr *acktr, const ngtcp2_ack *fr) {
272 ngtcp2_acktr_ack_entry *ent;
273 int64_t largest_ack = fr->largest_ack, min_ack;
274 size_t i, j;
275 ngtcp2_ringbuf *rb = &acktr->acks;
276 size_t nacks = ngtcp2_ringbuf_len(rb);
277
278 /* Assume that ngtcp2_pkt_validate_ack(fr) returns 0 */
279 for (j = 0; j < nacks; ++j) {
280 ent = ngtcp2_ringbuf_get(rb, j);
281 if (largest_ack >= ent->pkt_num) {
282 break;
283 }
284 }
285 if (j == nacks) {
286 return;
287 }
288
289 min_ack = largest_ack - (int64_t)fr->first_ack_blklen;
290
291 if (min_ack <= ent->pkt_num && ent->pkt_num <= largest_ack) {
292 acktr_on_ack(acktr, rb, j);
293 return;
294 }
295
296 for (i = 0; i < fr->num_blks && j < nacks; ++i) {
297 largest_ack = min_ack - (int64_t)fr->blks[i].gap - 2;
298 min_ack = largest_ack - (int64_t)fr->blks[i].blklen;
299
300 for (;;) {
301 if (ent->pkt_num > largest_ack) {
302 ++j;
303 if (j == nacks) {
304 return;
305 }
306 ent = ngtcp2_ringbuf_get(rb, j);
307 continue;
308 }
309 if (ent->pkt_num < min_ack) {
310 break;
311 }
312 acktr_on_ack(acktr, rb, j);
313 return;
314 }
315 }
316 }
317
ngtcp2_acktr_commit_ack(ngtcp2_acktr * acktr)318 void ngtcp2_acktr_commit_ack(ngtcp2_acktr *acktr) {
319 acktr->flags &= (uint16_t) ~(NGTCP2_ACKTR_FLAG_ACTIVE_ACK |
320 NGTCP2_ACKTR_FLAG_IMMEDIATE_ACK |
321 NGTCP2_ACKTR_FLAG_CANCEL_TIMER);
322 acktr->first_unacked_ts = UINT64_MAX;
323 acktr->rx_npkt = 0;
324 }
325
ngtcp2_acktr_require_active_ack(ngtcp2_acktr * acktr,ngtcp2_duration max_ack_delay,ngtcp2_tstamp ts)326 int ngtcp2_acktr_require_active_ack(ngtcp2_acktr *acktr,
327 ngtcp2_duration max_ack_delay,
328 ngtcp2_tstamp ts) {
329 return acktr->first_unacked_ts != UINT64_MAX &&
330 acktr->first_unacked_ts + max_ack_delay <= ts;
331 }
332
ngtcp2_acktr_immediate_ack(ngtcp2_acktr * acktr)333 void ngtcp2_acktr_immediate_ack(ngtcp2_acktr *acktr) {
334 acktr->flags |= NGTCP2_ACKTR_FLAG_IMMEDIATE_ACK;
335 }
336