BadVPN – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 1 | /** |
2 | * @file FragmentProtoAssembler.c |
||
3 | * @author Ambroz Bizjak <ambrop7@gmail.com> |
||
4 | * |
||
5 | * @section LICENSE |
||
6 | * |
||
7 | * Redistribution and use in source and binary forms, with or without |
||
8 | * modification, are permitted provided that the following conditions are met: |
||
9 | * 1. Redistributions of source code must retain the above copyright |
||
10 | * notice, this list of conditions and the following disclaimer. |
||
11 | * 2. Redistributions in binary form must reproduce the above copyright |
||
12 | * notice, this list of conditions and the following disclaimer in the |
||
13 | * documentation and/or other materials provided with the distribution. |
||
14 | * 3. Neither the name of the author nor the |
||
15 | * names of its contributors may be used to endorse or promote products |
||
16 | * derived from this software without specific prior written permission. |
||
17 | * |
||
18 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND |
||
19 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
||
20 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
||
21 | * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
||
22 | * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
||
23 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
||
24 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
||
25 | * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
||
26 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
||
27 | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
||
28 | */ |
||
29 | |||
30 | #include <stdlib.h> |
||
31 | #include <string.h> |
||
32 | |||
33 | #include <misc/offset.h> |
||
34 | #include <misc/byteorder.h> |
||
35 | #include <misc/balloc.h> |
||
36 | |||
37 | #include "FragmentProtoAssembler.h" |
||
38 | |||
39 | #include <generated/blog_channel_FragmentProtoAssembler.h> |
||
40 | |||
41 | #define PeerLog(_o, ...) BLog_LogViaFunc((_o)->logfunc, (_o)->user, BLOG_CURRENT_CHANNEL, __VA_ARGS__) |
||
42 | |||
43 | #include "FragmentProtoAssembler_tree.h" |
||
44 | #include <structure/SAvl_impl.h> |
||
45 | |||
46 | static void free_frame (FragmentProtoAssembler *o, struct FragmentProtoAssembler_frame *frame) |
||
47 | { |
||
48 | // remove from used list |
||
49 | LinkedList1_Remove(&o->frames_used, &frame->list_node); |
||
50 | // remove from used tree |
||
51 | FPAFramesTree_Remove(&o->frames_used_tree, 0, frame); |
||
52 | |||
53 | // append to free list |
||
54 | LinkedList1_Append(&o->frames_free, &frame->list_node); |
||
55 | } |
||
56 | |||
57 | static void free_oldest_frame (FragmentProtoAssembler *o) |
||
58 | { |
||
59 | ASSERT(!LinkedList1_IsEmpty(&o->frames_used)) |
||
60 | |||
61 | // obtain oldest frame (first on the list) |
||
62 | LinkedList1Node *list_node = LinkedList1_GetFirst(&o->frames_used); |
||
63 | ASSERT(list_node) |
||
64 | struct FragmentProtoAssembler_frame *frame = UPPER_OBJECT(list_node, struct FragmentProtoAssembler_frame, list_node); |
||
65 | |||
66 | // free frame |
||
67 | free_frame(o, frame); |
||
68 | } |
||
69 | |||
70 | static struct FragmentProtoAssembler_frame * allocate_new_frame (FragmentProtoAssembler *o, fragmentproto_frameid id) |
||
71 | { |
||
72 | ASSERT(!FPAFramesTree_LookupExact(&o->frames_used_tree, 0, id)) |
||
73 | |||
74 | // if there are no free entries, free the oldest used one |
||
75 | if (LinkedList1_IsEmpty(&o->frames_free)) { |
||
76 | PeerLog(o, BLOG_INFO, "freeing used frame"); |
||
77 | free_oldest_frame(o); |
||
78 | } |
||
79 | |||
80 | // obtain frame entry |
||
81 | LinkedList1Node *list_node = LinkedList1_GetFirst(&o->frames_free); |
||
82 | ASSERT(list_node) |
||
83 | struct FragmentProtoAssembler_frame *frame = UPPER_OBJECT(list_node, struct FragmentProtoAssembler_frame, list_node); |
||
84 | |||
85 | // remove from free list |
||
86 | LinkedList1_Remove(&o->frames_free, &frame->list_node); |
||
87 | |||
88 | // initialize values |
||
89 | frame->id = id; |
||
90 | frame->time = o->time; |
||
91 | frame->num_chunks = 0; |
||
92 | frame->sum = 0; |
||
93 | frame->length = -1; |
||
94 | frame->length_so_far = 0; |
||
95 | |||
96 | // append to used list |
||
97 | LinkedList1_Append(&o->frames_used, &frame->list_node); |
||
98 | // insert to used tree |
||
99 | int res = FPAFramesTree_Insert(&o->frames_used_tree, 0, frame, NULL); |
||
100 | ASSERT_EXECUTE(res) |
||
101 | |||
102 | return frame; |
||
103 | } |
||
104 | |||
105 | static int chunks_overlap (int c1_start, int c1_len, int c2_start, int c2_len) |
||
106 | { |
||
107 | return (c1_start + c1_len > c2_start && c2_start + c2_len > c1_start); |
||
108 | } |
||
109 | |||
110 | static int frame_is_timed_out (FragmentProtoAssembler *o, struct FragmentProtoAssembler_frame *frame) |
||
111 | { |
||
112 | ASSERT(frame->time <= o->time) |
||
113 | |||
114 | return (o->time - frame->time > o->time_tolerance); |
||
115 | } |
||
116 | |||
117 | static void reduce_times (FragmentProtoAssembler *o) |
||
118 | { |
||
119 | // find the frame with minimal time, removing timed out frames |
||
120 | struct FragmentProtoAssembler_frame *minframe = NULL; |
||
121 | LinkedList1Node *list_node = LinkedList1_GetFirst(&o->frames_used); |
||
122 | while (list_node) { |
||
123 | LinkedList1Node *next = LinkedList1Node_Next(list_node); |
||
124 | struct FragmentProtoAssembler_frame *frame = UPPER_OBJECT(list_node, struct FragmentProtoAssembler_frame, list_node); |
||
125 | if (frame_is_timed_out(o, frame)) { |
||
126 | PeerLog(o, BLOG_INFO, "freeing timed out frame (while reducing times)"); |
||
127 | free_frame(o, frame); |
||
128 | } else { |
||
129 | if (!minframe || frame->time < minframe->time) { |
||
130 | minframe = frame; |
||
131 | } |
||
132 | } |
||
133 | list_node = next; |
||
134 | } |
||
135 | |||
136 | if (!minframe) { |
||
137 | // have no frames, set packet time to zero |
||
138 | o->time = 0; |
||
139 | return; |
||
140 | } |
||
141 | |||
142 | uint32_t min_time = minframe->time; |
||
143 | |||
144 | // subtract minimal time from all frames |
||
145 | for (list_node = LinkedList1_GetFirst(&o->frames_used); list_node; list_node = LinkedList1Node_Next(list_node)) { |
||
146 | struct FragmentProtoAssembler_frame *frame = UPPER_OBJECT(list_node, struct FragmentProtoAssembler_frame, list_node); |
||
147 | frame->time -= min_time; |
||
148 | } |
||
149 | |||
150 | // subtract minimal time from packet time |
||
151 | o->time -= min_time; |
||
152 | } |
||
153 | |||
154 | static int process_chunk (FragmentProtoAssembler *o, fragmentproto_frameid frame_id, int chunk_start, int chunk_len, int is_last, uint8_t *payload) |
||
155 | { |
||
156 | ASSERT(chunk_start >= 0) |
||
157 | ASSERT(chunk_len >= 0) |
||
158 | ASSERT(is_last == 0 || is_last == 1) |
||
159 | |||
160 | // verify chunk |
||
161 | |||
162 | // check start |
||
163 | if (chunk_start > o->output_mtu) { |
||
164 | PeerLog(o, BLOG_INFO, "chunk starts outside"); |
||
165 | return 0; |
||
166 | } |
||
167 | |||
168 | // check frame size bound |
||
169 | if (chunk_len > o->output_mtu - chunk_start) { |
||
170 | PeerLog(o, BLOG_INFO, "chunk ends outside"); |
||
171 | return 0; |
||
172 | } |
||
173 | |||
174 | // calculate end |
||
175 | int chunk_end = chunk_start + chunk_len; |
||
176 | ASSERT(chunk_end >= 0) |
||
177 | ASSERT(chunk_end <= o->output_mtu) |
||
178 | |||
179 | // lookup frame |
||
180 | struct FragmentProtoAssembler_frame *frame = FPAFramesTree_LookupExact(&o->frames_used_tree, 0, frame_id); |
||
181 | if (!frame) { |
||
182 | // frame not found, add a new one |
||
183 | frame = allocate_new_frame(o, frame_id); |
||
184 | } else { |
||
185 | // have existing frame with that ID |
||
186 | // check frame time |
||
187 | if (frame_is_timed_out(o, frame)) { |
||
188 | // frame is timed out, remove it and use a new one |
||
189 | PeerLog(o, BLOG_INFO, "freeing timed out frame (while processing chunk)"); |
||
190 | free_frame(o, frame); |
||
191 | frame = allocate_new_frame(o, frame_id); |
||
192 | } |
||
193 | } |
||
194 | |||
195 | ASSERT(frame->num_chunks < o->num_chunks) |
||
196 | |||
197 | // check if the chunk overlaps with any existing chunks |
||
198 | for (int i = 0; i < frame->num_chunks; i++) { |
||
199 | struct FragmentProtoAssembler_chunk *chunk = &frame->chunks[i]; |
||
200 | if (chunks_overlap(chunk->start, chunk->len, chunk_start, chunk_len)) { |
||
201 | PeerLog(o, BLOG_INFO, "chunk overlaps with existing chunk"); |
||
202 | goto fail_frame; |
||
203 | } |
||
204 | } |
||
205 | |||
206 | if (is_last) { |
||
207 | // this chunk is marked as last |
||
208 | if (frame->length >= 0) { |
||
209 | PeerLog(o, BLOG_INFO, "got last chunk, but already have one"); |
||
210 | goto fail_frame; |
||
211 | } |
||
212 | // check if frame size according to this packet is consistent |
||
213 | // with existing chunks |
||
214 | if (frame->length_so_far > chunk_end) { |
||
215 | PeerLog(o, BLOG_INFO, "got last chunk, but already have data over its bound"); |
||
216 | goto fail_frame; |
||
217 | } |
||
218 | } else { |
||
219 | // if we have length, chunk must be in its bound |
||
220 | if (frame->length >= 0) { |
||
221 | if (chunk_end > frame->length) { |
||
222 | PeerLog(o, BLOG_INFO, "chunk out of length bound"); |
||
223 | goto fail_frame; |
||
224 | } |
||
225 | } |
||
226 | } |
||
227 | |||
228 | // chunk is good, add it |
||
229 | |||
230 | // update frame time |
||
231 | frame->time = o->time; |
||
232 | |||
233 | // add chunk entry |
||
234 | struct FragmentProtoAssembler_chunk *chunk = &frame->chunks[frame->num_chunks]; |
||
235 | chunk->start = chunk_start; |
||
236 | chunk->len = chunk_len; |
||
237 | frame->num_chunks++; |
||
238 | |||
239 | // update sum |
||
240 | frame->sum += chunk_len; |
||
241 | |||
242 | // update length |
||
243 | if (is_last) { |
||
244 | frame->length = chunk_end; |
||
245 | } else { |
||
246 | if (frame->length < 0) { |
||
247 | if (frame->length_so_far < chunk_end) { |
||
248 | frame->length_so_far = chunk_end; |
||
249 | } |
||
250 | } |
||
251 | } |
||
252 | |||
253 | // copy chunk payload to buffer |
||
254 | memcpy(frame->buffer + chunk_start, payload, chunk_len); |
||
255 | |||
256 | // is frame incomplete? |
||
257 | if (frame->length < 0 || frame->sum < frame->length) { |
||
258 | // if all chunks are used, fail it |
||
259 | if (frame->num_chunks == o->num_chunks) { |
||
260 | PeerLog(o, BLOG_INFO, "all chunks used, but frame not complete"); |
||
261 | goto fail_frame; |
||
262 | } |
||
263 | |||
264 | // wait for more chunks |
||
265 | return 0; |
||
266 | } |
||
267 | |||
268 | ASSERT(frame->sum == frame->length) |
||
269 | |||
270 | PeerLog(o, BLOG_DEBUG, "frame complete"); |
||
271 | |||
272 | // free frame entry |
||
273 | free_frame(o, frame); |
||
274 | |||
275 | // send frame |
||
276 | PacketPassInterface_Sender_Send(o->output, frame->buffer, frame->length); |
||
277 | |||
278 | return 1; |
||
279 | |||
280 | fail_frame: |
||
281 | free_frame(o, frame); |
||
282 | return 0; |
||
283 | } |
||
284 | |||
285 | static void process_input (FragmentProtoAssembler *o) |
||
286 | { |
||
287 | ASSERT(o->in_len >= 0) |
||
288 | |||
289 | // read chunks |
||
290 | while (o->in_pos < o->in_len) { |
||
291 | // obtain header |
||
292 | if (o->in_len - o->in_pos < sizeof(struct fragmentproto_chunk_header)) { |
||
293 | PeerLog(o, BLOG_INFO, "too little data for chunk header"); |
||
294 | break; |
||
295 | } |
||
296 | struct fragmentproto_chunk_header header; |
||
297 | memcpy(&header, o->in + o->in_pos, sizeof(header)); |
||
298 | o->in_pos += sizeof(struct fragmentproto_chunk_header); |
||
299 | fragmentproto_frameid frame_id = ltoh16(header.frame_id); |
||
300 | int chunk_start = ltoh16(header.chunk_start); |
||
301 | int chunk_len = ltoh16(header.chunk_len); |
||
302 | int is_last = ltoh8(header.is_last); |
||
303 | |||
304 | // check is_last field |
||
305 | if (!(is_last == 0 || is_last == 1)) { |
||
306 | PeerLog(o, BLOG_INFO, "chunk is_last wrong"); |
||
307 | break; |
||
308 | } |
||
309 | |||
310 | // obtain data |
||
311 | if (o->in_len - o->in_pos < chunk_len) { |
||
312 | PeerLog(o, BLOG_INFO, "too little data for chunk data"); |
||
313 | break; |
||
314 | } |
||
315 | |||
316 | // process chunk |
||
317 | int res = process_chunk(o, frame_id, chunk_start, chunk_len, is_last, o->in + o->in_pos); |
||
318 | o->in_pos += chunk_len; |
||
319 | |||
320 | if (res) { |
||
321 | // sending complete frame, stop processing input |
||
322 | return; |
||
323 | } |
||
324 | } |
||
325 | |||
326 | // increment packet time |
||
327 | if (o->time == FPA_MAX_TIME) { |
||
328 | reduce_times(o); |
||
329 | if (!LinkedList1_IsEmpty(&o->frames_used)) { |
||
330 | ASSERT(o->time < FPA_MAX_TIME) // If there was a frame with zero time, it was removed because |
||
331 | // time_tolerance < FPA_MAX_TIME. So something >0 was subtracted. |
||
332 | o->time++; |
||
333 | } else { |
||
334 | // it was set to zero by reduce_times |
||
335 | ASSERT(o->time == 0) |
||
336 | } |
||
337 | } else { |
||
338 | o->time++; |
||
339 | } |
||
340 | |||
341 | // set no input packet |
||
342 | o->in_len = -1; |
||
343 | |||
344 | // finish input |
||
345 | PacketPassInterface_Done(&o->input); |
||
346 | } |
||
347 | |||
348 | static void input_handler_send (FragmentProtoAssembler *o, uint8_t *data, int data_len) |
||
349 | { |
||
350 | ASSERT(data_len >= 0) |
||
351 | ASSERT(o->in_len == -1) |
||
352 | DebugObject_Access(&o->d_obj); |
||
353 | |||
354 | // save input packet |
||
355 | o->in_len = data_len; |
||
356 | o->in = data; |
||
357 | o->in_pos = 0; |
||
358 | |||
359 | process_input(o); |
||
360 | } |
||
361 | |||
362 | static void output_handler_done (FragmentProtoAssembler *o) |
||
363 | { |
||
364 | ASSERT(o->in_len >= 0) |
||
365 | DebugObject_Access(&o->d_obj); |
||
366 | |||
367 | process_input(o); |
||
368 | } |
||
369 | |||
370 | int FragmentProtoAssembler_Init (FragmentProtoAssembler *o, int input_mtu, PacketPassInterface *output, int num_frames, int num_chunks, BPendingGroup *pg, void *user, BLog_logfunc logfunc) |
||
371 | { |
||
372 | ASSERT(input_mtu >= 0) |
||
373 | ASSERT(num_frames > 0) |
||
374 | ASSERT(num_frames < FPA_MAX_TIME) // needed so we can always subtract times when packet time is maximum |
||
375 | ASSERT(num_chunks > 0) |
||
376 | |||
377 | // init arguments |
||
378 | o->output = output; |
||
379 | o->num_chunks = num_chunks; |
||
380 | o->user = user; |
||
381 | o->logfunc = logfunc; |
||
382 | |||
383 | // init input |
||
384 | PacketPassInterface_Init(&o->input, input_mtu, (PacketPassInterface_handler_send)input_handler_send, o, pg); |
||
385 | |||
386 | // init output |
||
387 | PacketPassInterface_Sender_Init(o->output, (PacketPassInterface_handler_done)output_handler_done, o); |
||
388 | |||
389 | // remebmer output MTU |
||
390 | o->output_mtu = PacketPassInterface_GetMTU(o->output); |
||
391 | |||
392 | // set packet time to zero |
||
393 | o->time = 0; |
||
394 | |||
395 | // set time tolerance to num_frames |
||
396 | o->time_tolerance = num_frames; |
||
397 | |||
398 | // allocate frames |
||
399 | if (!(o->frames_entries = (struct FragmentProtoAssembler_frame *)BAllocArray(num_frames, sizeof(o->frames_entries[0])))) { |
||
400 | goto fail1; |
||
401 | } |
||
402 | |||
403 | // allocate chunks |
||
404 | if (!(o->frames_chunks = (struct FragmentProtoAssembler_chunk *)BAllocArray2(num_frames, o->num_chunks, sizeof(o->frames_chunks[0])))) { |
||
405 | goto fail2; |
||
406 | } |
||
407 | |||
408 | // allocate buffers |
||
409 | if (!(o->frames_buffer = (uint8_t *)BAllocArray(num_frames, o->output_mtu))) { |
||
410 | goto fail3; |
||
411 | } |
||
412 | |||
413 | // init frame lists |
||
414 | LinkedList1_Init(&o->frames_free); |
||
415 | LinkedList1_Init(&o->frames_used); |
||
416 | |||
417 | // initialize frame entries |
||
418 | for (int i = 0; i < num_frames; i++) { |
||
419 | struct FragmentProtoAssembler_frame *frame = &o->frames_entries[i]; |
||
420 | // set chunks array pointer |
||
421 | frame->chunks = o->frames_chunks + (size_t)i * o->num_chunks; |
||
422 | // set buffer pointer |
||
423 | frame->buffer = o->frames_buffer + (size_t)i * o->output_mtu; |
||
424 | // add to free list |
||
425 | LinkedList1_Append(&o->frames_free, &frame->list_node); |
||
426 | } |
||
427 | |||
428 | // init tree |
||
429 | FPAFramesTree_Init(&o->frames_used_tree); |
||
430 | |||
431 | // have no input packet |
||
432 | o->in_len = -1; |
||
433 | |||
434 | DebugObject_Init(&o->d_obj); |
||
435 | |||
436 | return 1; |
||
437 | |||
438 | fail3: |
||
439 | BFree(o->frames_chunks); |
||
440 | fail2: |
||
441 | BFree(o->frames_entries); |
||
442 | fail1: |
||
443 | PacketPassInterface_Free(&o->input); |
||
444 | return 0; |
||
445 | } |
||
446 | |||
447 | void FragmentProtoAssembler_Free (FragmentProtoAssembler *o) |
||
448 | { |
||
449 | DebugObject_Free(&o->d_obj); |
||
450 | |||
451 | // free buffers |
||
452 | BFree(o->frames_buffer); |
||
453 | |||
454 | // free chunks |
||
455 | BFree(o->frames_chunks); |
||
456 | |||
457 | // free frames |
||
458 | BFree(o->frames_entries); |
||
459 | |||
460 | // free input |
||
461 | PacketPassInterface_Free(&o->input); |
||
462 | } |
||
463 | |||
464 | PacketPassInterface * FragmentProtoAssembler_GetInput (FragmentProtoAssembler *o) |
||
465 | { |
||
466 | DebugObject_Access(&o->d_obj); |
||
467 | |||
468 | return &o->input; |
||
469 | } |