BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
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 }