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_rob.h"
26
27 #include <string.h>
28 #include <assert.h>
29
30 #include "ngtcp2_macro.h"
31
ngtcp2_rob_gap_new(ngtcp2_rob_gap ** pg,uint64_t begin,uint64_t end,const ngtcp2_mem * mem)32 int ngtcp2_rob_gap_new(ngtcp2_rob_gap **pg, uint64_t begin, uint64_t end,
33 const ngtcp2_mem *mem) {
34 *pg = ngtcp2_mem_malloc(mem, sizeof(ngtcp2_rob_gap));
35 if (*pg == NULL) {
36 return NGTCP2_ERR_NOMEM;
37 }
38
39 (*pg)->range.begin = begin;
40 (*pg)->range.end = end;
41
42 return 0;
43 }
44
ngtcp2_rob_gap_del(ngtcp2_rob_gap * g,const ngtcp2_mem * mem)45 void ngtcp2_rob_gap_del(ngtcp2_rob_gap *g, const ngtcp2_mem *mem) {
46 ngtcp2_mem_free(mem, g);
47 }
48
ngtcp2_rob_data_new(ngtcp2_rob_data ** pd,uint64_t offset,size_t chunk,const ngtcp2_mem * mem)49 int ngtcp2_rob_data_new(ngtcp2_rob_data **pd, uint64_t offset, size_t chunk,
50 const ngtcp2_mem *mem) {
51 *pd = ngtcp2_mem_malloc(mem, sizeof(ngtcp2_rob_data) + chunk);
52 if (*pd == NULL) {
53 return NGTCP2_ERR_NOMEM;
54 }
55
56 (*pd)->range.begin = offset;
57 (*pd)->range.end = offset + chunk;
58 (*pd)->begin = (uint8_t *)(*pd) + sizeof(ngtcp2_rob_data);
59 (*pd)->end = (*pd)->begin + chunk;
60
61 return 0;
62 }
63
ngtcp2_rob_data_del(ngtcp2_rob_data * d,const ngtcp2_mem * mem)64 void ngtcp2_rob_data_del(ngtcp2_rob_data *d, const ngtcp2_mem *mem) {
65 ngtcp2_mem_free(mem, d);
66 }
67
ngtcp2_rob_init(ngtcp2_rob * rob,size_t chunk,const ngtcp2_mem * mem)68 int ngtcp2_rob_init(ngtcp2_rob *rob, size_t chunk, const ngtcp2_mem *mem) {
69 int rv;
70 ngtcp2_rob_gap *g;
71
72 ngtcp2_ksl_init(&rob->gapksl, ngtcp2_ksl_range_compar, sizeof(ngtcp2_range),
73 mem);
74
75 rv = ngtcp2_rob_gap_new(&g, 0, UINT64_MAX, mem);
76 if (rv != 0) {
77 goto fail_rob_gap_new;
78 }
79
80 rv = ngtcp2_ksl_insert(&rob->gapksl, NULL, &g->range, g);
81 if (rv != 0) {
82 goto fail_gapksl_ksl_insert;
83 }
84
85 ngtcp2_ksl_init(&rob->dataksl, ngtcp2_ksl_range_compar, sizeof(ngtcp2_range),
86 mem);
87
88 rob->chunk = chunk;
89 rob->mem = mem;
90
91 return 0;
92
93 fail_gapksl_ksl_insert:
94 ngtcp2_rob_gap_del(g, mem);
95 fail_rob_gap_new:
96 ngtcp2_ksl_free(&rob->gapksl);
97 return rv;
98 }
99
ngtcp2_rob_free(ngtcp2_rob * rob)100 void ngtcp2_rob_free(ngtcp2_rob *rob) {
101 ngtcp2_ksl_it it;
102
103 if (rob == NULL) {
104 return;
105 }
106
107 for (it = ngtcp2_ksl_begin(&rob->dataksl); !ngtcp2_ksl_it_end(&it);
108 ngtcp2_ksl_it_next(&it)) {
109 ngtcp2_rob_data_del(ngtcp2_ksl_it_get(&it), rob->mem);
110 }
111
112 for (it = ngtcp2_ksl_begin(&rob->gapksl); !ngtcp2_ksl_it_end(&it);
113 ngtcp2_ksl_it_next(&it)) {
114 ngtcp2_rob_gap_del(ngtcp2_ksl_it_get(&it), rob->mem);
115 }
116
117 ngtcp2_ksl_free(&rob->dataksl);
118 ngtcp2_ksl_free(&rob->gapksl);
119 }
120
rob_write_data(ngtcp2_rob * rob,uint64_t offset,const uint8_t * data,size_t len)121 static int rob_write_data(ngtcp2_rob *rob, uint64_t offset, const uint8_t *data,
122 size_t len) {
123 size_t n;
124 int rv;
125 ngtcp2_rob_data *d;
126 ngtcp2_range range = {offset, offset + len};
127 ngtcp2_ksl_it it;
128
129 for (it = ngtcp2_ksl_lower_bound_compar(&rob->dataksl, &range,
130 ngtcp2_ksl_range_exclusive_compar);
131 len; ngtcp2_ksl_it_next(&it)) {
132 if (ngtcp2_ksl_it_end(&it)) {
133 d = NULL;
134 } else {
135 d = ngtcp2_ksl_it_get(&it);
136 }
137
138 if (d == NULL || offset < d->range.begin) {
139 rv = ngtcp2_rob_data_new(&d, (offset / rob->chunk) * rob->chunk,
140 rob->chunk, rob->mem);
141 if (rv != 0) {
142 return rv;
143 }
144
145 rv = ngtcp2_ksl_insert(&rob->dataksl, &it, &d->range, d);
146 if (rv != 0) {
147 ngtcp2_rob_data_del(d, rob->mem);
148 return rv;
149 }
150 }
151
152 n = (size_t)ngtcp2_min((uint64_t)len, d->range.begin + rob->chunk - offset);
153 memcpy(d->begin + (offset - d->range.begin), data, n);
154 offset += n;
155 data += n;
156 len -= n;
157 }
158
159 return 0;
160 }
161
ngtcp2_rob_push(ngtcp2_rob * rob,uint64_t offset,const uint8_t * data,size_t datalen)162 int ngtcp2_rob_push(ngtcp2_rob *rob, uint64_t offset, const uint8_t *data,
163 size_t datalen) {
164 int rv;
165 ngtcp2_rob_gap *g;
166 ngtcp2_range m, l, r, q = {offset, offset + datalen};
167 ngtcp2_ksl_it it;
168
169 it = ngtcp2_ksl_lower_bound_compar(&rob->gapksl, &q,
170 ngtcp2_ksl_range_exclusive_compar);
171
172 for (; !ngtcp2_ksl_it_end(&it);) {
173 g = ngtcp2_ksl_it_get(&it);
174
175 m = ngtcp2_range_intersect(&q, &g->range);
176 if (!ngtcp2_range_len(&m)) {
177 break;
178 }
179 if (ngtcp2_range_eq(&g->range, &m)) {
180 ngtcp2_ksl_remove_hint(&rob->gapksl, &it, &it, &g->range);
181 ngtcp2_rob_gap_del(g, rob->mem);
182 rv = rob_write_data(rob, m.begin, data + (m.begin - offset),
183 (size_t)ngtcp2_range_len(&m));
184 if (rv != 0) {
185 return rv;
186 }
187
188 continue;
189 }
190 ngtcp2_range_cut(&l, &r, &g->range, &m);
191 if (ngtcp2_range_len(&l)) {
192 ngtcp2_ksl_update_key(&rob->gapksl, &g->range, &l);
193 g->range = l;
194
195 if (ngtcp2_range_len(&r)) {
196 ngtcp2_rob_gap *ng;
197 rv = ngtcp2_rob_gap_new(&ng, r.begin, r.end, rob->mem);
198 if (rv != 0) {
199 return rv;
200 }
201 rv = ngtcp2_ksl_insert(&rob->gapksl, &it, &ng->range, ng);
202 if (rv != 0) {
203 ngtcp2_rob_gap_del(ng, rob->mem);
204 return rv;
205 }
206 }
207 } else if (ngtcp2_range_len(&r)) {
208 ngtcp2_ksl_update_key(&rob->gapksl, &g->range, &r);
209 g->range = r;
210 }
211 rv = rob_write_data(rob, m.begin, data + (m.begin - offset),
212 (size_t)ngtcp2_range_len(&m));
213 if (rv != 0) {
214 return rv;
215 }
216 ngtcp2_ksl_it_next(&it);
217 }
218 return 0;
219 }
220
ngtcp2_rob_remove_prefix(ngtcp2_rob * rob,uint64_t offset)221 int ngtcp2_rob_remove_prefix(ngtcp2_rob *rob, uint64_t offset) {
222 ngtcp2_rob_gap *g;
223 ngtcp2_rob_data *d;
224 ngtcp2_ksl_it it;
225
226 it = ngtcp2_ksl_begin(&rob->gapksl);
227
228 for (; !ngtcp2_ksl_it_end(&it);) {
229 g = ngtcp2_ksl_it_get(&it);
230 if (offset <= g->range.begin) {
231 break;
232 }
233 if (offset < g->range.end) {
234 ngtcp2_range r = {offset, g->range.end};
235 ngtcp2_ksl_update_key(&rob->gapksl, &g->range, &r);
236 g->range.begin = offset;
237 break;
238 }
239 ngtcp2_ksl_remove_hint(&rob->gapksl, &it, &it, &g->range);
240 ngtcp2_rob_gap_del(g, rob->mem);
241 }
242
243 it = ngtcp2_ksl_begin(&rob->dataksl);
244
245 for (; !ngtcp2_ksl_it_end(&it);) {
246 d = ngtcp2_ksl_it_get(&it);
247 if (offset < d->range.begin + rob->chunk) {
248 return 0;
249 }
250 ngtcp2_ksl_remove_hint(&rob->dataksl, &it, &it, &d->range);
251 ngtcp2_rob_data_del(d, rob->mem);
252 }
253
254 return 0;
255 }
256
ngtcp2_rob_data_at(ngtcp2_rob * rob,const uint8_t ** pdest,uint64_t offset)257 size_t ngtcp2_rob_data_at(ngtcp2_rob *rob, const uint8_t **pdest,
258 uint64_t offset) {
259 ngtcp2_rob_gap *g;
260 ngtcp2_rob_data *d;
261 ngtcp2_ksl_it it;
262
263 it = ngtcp2_ksl_begin(&rob->gapksl);
264 if (ngtcp2_ksl_it_end(&it)) {
265 return 0;
266 }
267
268 g = ngtcp2_ksl_it_get(&it);
269
270 if (g->range.begin <= offset) {
271 return 0;
272 }
273
274 it = ngtcp2_ksl_begin(&rob->dataksl);
275 d = ngtcp2_ksl_it_get(&it);
276
277 assert(d);
278 assert(d->range.begin <= offset);
279 assert(offset < d->range.begin + rob->chunk);
280
281 *pdest = d->begin + (offset - d->range.begin);
282
283 return (size_t)(ngtcp2_min(g->range.begin, d->range.begin + rob->chunk) -
284 offset);
285 }
286
ngtcp2_rob_pop(ngtcp2_rob * rob,uint64_t offset,size_t len)287 void ngtcp2_rob_pop(ngtcp2_rob *rob, uint64_t offset, size_t len) {
288 ngtcp2_ksl_it it;
289 ngtcp2_rob_data *d;
290
291 it = ngtcp2_ksl_begin(&rob->dataksl);
292 d = ngtcp2_ksl_it_get(&it);
293
294 assert(d);
295
296 if (offset + len < d->range.begin + rob->chunk) {
297 return;
298 }
299
300 ngtcp2_ksl_remove_hint(&rob->dataksl, NULL, &it, &d->range);
301 ngtcp2_rob_data_del(d, rob->mem);
302 }
303
ngtcp2_rob_first_gap_offset(ngtcp2_rob * rob)304 uint64_t ngtcp2_rob_first_gap_offset(ngtcp2_rob *rob) {
305 ngtcp2_ksl_it it = ngtcp2_ksl_begin(&rob->gapksl);
306 ngtcp2_rob_gap *g;
307
308 if (ngtcp2_ksl_it_end(&it)) {
309 return UINT64_MAX;
310 }
311
312 g = ngtcp2_ksl_it_get(&it);
313
314 return g->range.begin;
315 }
316
ngtcp2_rob_data_buffered(ngtcp2_rob * rob)317 int ngtcp2_rob_data_buffered(ngtcp2_rob *rob) {
318 return ngtcp2_ksl_len(&rob->dataksl) != 0;
319 }
320