BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file PacketPassFairQueue.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  
32 #include <misc/debug.h>
33 #include <misc/offset.h>
34 #include <misc/minmax.h>
35 #include <misc/compare.h>
36  
37 #include <flow/PacketPassFairQueue.h>
38  
39 static int compare_flows (PacketPassFairQueueFlow *f1, PacketPassFairQueueFlow *f2)
40 {
41 int cmp = B_COMPARE(f1->time, f2->time);
42 if (cmp) {
43 return cmp;
44 }
45  
46 return B_COMPARE((uintptr_t)f1, (uintptr_t)f2);
47 }
48  
49 #include "PacketPassFairQueue_tree.h"
50 #include <structure/SAvl_impl.h>
51  
52 static uint64_t get_current_time (PacketPassFairQueue *m)
53 {
54 if (m->sending_flow) {
55 return m->sending_flow->time;
56 }
57  
58 uint64_t time = 0; // to remove warning
59 int have = 0;
60  
61 PacketPassFairQueueFlow *first_flow = PacketPassFairQueue__Tree_GetFirst(&m->queued_tree, 0);
62 if (first_flow) {
63 ASSERT(first_flow->is_queued)
64  
65 time = first_flow->time;
66 have = 1;
67 }
68  
69 if (m->previous_flow) {
70 if (!have || m->previous_flow->time < time) {
71 time = m->previous_flow->time;
72 have = 1;
73 }
74 }
75  
76 return (have ? time : 0);
77 }
78  
79 static void increment_sent_flow (PacketPassFairQueueFlow *flow, uint64_t amount)
80 {
81 PacketPassFairQueue *m = flow->m;
82  
83 ASSERT(amount <= FAIRQUEUE_MAX_TIME)
84 ASSERT(!flow->is_queued)
85 ASSERT(!m->sending_flow)
86  
87 // does time overflow?
88 if (amount > FAIRQUEUE_MAX_TIME - flow->time) {
89 // get time to subtract
90 uint64_t subtract;
91 PacketPassFairQueueFlow *first_flow = PacketPassFairQueue__Tree_GetFirst(&m->queued_tree, 0);
92 if (!first_flow) {
93 subtract = flow->time;
94 } else {
95 ASSERT(first_flow->is_queued)
96 subtract = first_flow->time;
97 }
98  
99 // subtract time from all flows
100 for (LinkedList1Node *list_node = LinkedList1_GetFirst(&m->flows_list); list_node; list_node = LinkedList1Node_Next(list_node)) {
101 PacketPassFairQueueFlow *someflow = UPPER_OBJECT(list_node, PacketPassFairQueueFlow, list_node);
102  
103 // don't subtract more time than there is, except for the just finished flow,
104 // where we allow time to underflow and then overflow to the correct value after adding to it
105 if (subtract > someflow->time && someflow != flow) {
106 ASSERT(!someflow->is_queued)
107 someflow->time = 0;
108 } else {
109 someflow->time -= subtract;
110 }
111 }
112 }
113  
114 // add time to flow
115 flow->time += amount;
116 }
117  
118 static void schedule (PacketPassFairQueue *m)
119 {
120 ASSERT(!m->sending_flow)
121 ASSERT(!m->previous_flow)
122 ASSERT(!m->freeing)
123 ASSERT(!PacketPassFairQueue__Tree_IsEmpty(&m->queued_tree))
124  
125 // get first queued flow
126 PacketPassFairQueueFlow *qflow = PacketPassFairQueue__Tree_GetFirst(&m->queued_tree, 0);
127 ASSERT(qflow->is_queued)
128  
129 // remove flow from queue
130 PacketPassFairQueue__Tree_Remove(&m->queued_tree, 0, qflow);
131 qflow->is_queued = 0;
132  
133 // schedule send
134 PacketPassInterface_Sender_Send(m->output, qflow->queued.data, qflow->queued.data_len);
135 m->sending_flow = qflow;
136 m->sending_len = qflow->queued.data_len;
137 }
138  
139 static void schedule_job_handler (PacketPassFairQueue *m)
140 {
141 ASSERT(!m->sending_flow)
142 ASSERT(!m->freeing)
143 DebugObject_Access(&m->d_obj);
144  
145 // remove previous flow
146 m->previous_flow = NULL;
147  
148 if (!PacketPassFairQueue__Tree_IsEmpty(&m->queued_tree)) {
149 schedule(m);
150 }
151 }
152  
153 static void input_handler_send (PacketPassFairQueueFlow *flow, uint8_t *data, int data_len)
154 {
155 PacketPassFairQueue *m = flow->m;
156  
157 ASSERT(flow != m->sending_flow)
158 ASSERT(!flow->is_queued)
159 ASSERT(!m->freeing)
160 DebugObject_Access(&flow->d_obj);
161  
162 if (flow == m->previous_flow) {
163 // remove from previous flow
164 m->previous_flow = NULL;
165 } else {
166 // raise time
167 flow->time = bmax_uint64(flow->time, get_current_time(m));
168 }
169  
170 // queue flow
171 flow->queued.data = data;
172 flow->queued.data_len = data_len;
173 int res = PacketPassFairQueue__Tree_Insert(&m->queued_tree, 0, flow, NULL);
174 ASSERT_EXECUTE(res)
175 flow->is_queued = 1;
176  
177 if (!m->sending_flow && !BPending_IsSet(&m->schedule_job)) {
178 schedule(m);
179 }
180 }
181  
182 static void output_handler_done (PacketPassFairQueue *m)
183 {
184 ASSERT(m->sending_flow)
185 ASSERT(!m->previous_flow)
186 ASSERT(!BPending_IsSet(&m->schedule_job))
187 ASSERT(!m->freeing)
188 ASSERT(!m->sending_flow->is_queued)
189  
190 PacketPassFairQueueFlow *flow = m->sending_flow;
191  
192 // sending finished
193 m->sending_flow = NULL;
194  
195 // remember this flow so the schedule job can remove its time if it didn's send
196 m->previous_flow = flow;
197  
198 // update flow time by packet size
199 increment_sent_flow(flow, (uint64_t)m->packet_weight + m->sending_len);
200  
201 // schedule schedule
202 BPending_Set(&m->schedule_job);
203  
204 // finish flow packet
205 PacketPassInterface_Done(&flow->input);
206  
207 // call busy handler if set
208 if (flow->handler_busy) {
209 // handler is one-shot, unset it before calling
210 PacketPassFairQueue_handler_busy handler = flow->handler_busy;
211 flow->handler_busy = NULL;
212  
213 // call handler
214 handler(flow->user);
215 return;
216 }
217 }
218  
219 int PacketPassFairQueue_Init (PacketPassFairQueue *m, PacketPassInterface *output, BPendingGroup *pg, int use_cancel, int packet_weight)
220 {
221 ASSERT(packet_weight > 0)
222 ASSERT(use_cancel == 0 || use_cancel == 1)
223 ASSERT(!use_cancel || PacketPassInterface_HasCancel(output))
224  
225 // init arguments
226 m->output = output;
227 m->pg = pg;
228 m->use_cancel = use_cancel;
229 m->packet_weight = packet_weight;
230  
231 // make sure that (output MTU + packet_weight <= FAIRQUEUE_MAX_TIME)
232 if (!(
233 (PacketPassInterface_GetMTU(output) <= FAIRQUEUE_MAX_TIME) &&
234 (packet_weight <= FAIRQUEUE_MAX_TIME - PacketPassInterface_GetMTU(output))
235 )) {
236 goto fail0;
237 }
238  
239 // init output
240 PacketPassInterface_Sender_Init(m->output, (PacketPassInterface_handler_done)output_handler_done, m);
241  
242 // not sending
243 m->sending_flow = NULL;
244  
245 // no previous flow
246 m->previous_flow = NULL;
247  
248 // init queued tree
249 PacketPassFairQueue__Tree_Init(&m->queued_tree);
250  
251 // init flows list
252 LinkedList1_Init(&m->flows_list);
253  
254 // not freeing
255 m->freeing = 0;
256  
257 // init schedule job
258 BPending_Init(&m->schedule_job, m->pg, (BPending_handler)schedule_job_handler, m);
259  
260 DebugObject_Init(&m->d_obj);
261 DebugCounter_Init(&m->d_ctr);
262 return 1;
263  
264 fail0:
265 return 0;
266 }
267  
268 void PacketPassFairQueue_Free (PacketPassFairQueue *m)
269 {
270 ASSERT(LinkedList1_IsEmpty(&m->flows_list))
271 ASSERT(PacketPassFairQueue__Tree_IsEmpty(&m->queued_tree))
272 ASSERT(!m->previous_flow)
273 ASSERT(!m->sending_flow)
274 DebugCounter_Free(&m->d_ctr);
275 DebugObject_Free(&m->d_obj);
276  
277 // free schedule job
278 BPending_Free(&m->schedule_job);
279 }
280  
281 void PacketPassFairQueue_PrepareFree (PacketPassFairQueue *m)
282 {
283 DebugObject_Access(&m->d_obj);
284  
285 // set freeing
286 m->freeing = 1;
287 }
288  
289 int PacketPassFairQueue_GetMTU (PacketPassFairQueue *m)
290 {
291 DebugObject_Access(&m->d_obj);
292  
293 return PacketPassInterface_GetMTU(m->output);
294 }
295  
296 void PacketPassFairQueueFlow_Init (PacketPassFairQueueFlow *flow, PacketPassFairQueue *m)
297 {
298 ASSERT(!m->freeing)
299 DebugObject_Access(&m->d_obj);
300  
301 // init arguments
302 flow->m = m;
303  
304 // have no canfree handler
305 flow->handler_busy = NULL;
306  
307 // init input
308 PacketPassInterface_Init(&flow->input, PacketPassInterface_GetMTU(flow->m->output), (PacketPassInterface_handler_send)input_handler_send, flow, m->pg);
309  
310 // set time
311 flow->time = 0;
312  
313 // add to flows list
314 LinkedList1_Append(&m->flows_list, &flow->list_node);
315  
316 // is not queued
317 flow->is_queued = 0;
318  
319 DebugObject_Init(&flow->d_obj);
320 DebugCounter_Increment(&m->d_ctr);
321 }
322  
323 void PacketPassFairQueueFlow_Free (PacketPassFairQueueFlow *flow)
324 {
325 PacketPassFairQueue *m = flow->m;
326  
327 ASSERT(m->freeing || flow != m->sending_flow)
328 DebugCounter_Decrement(&m->d_ctr);
329 DebugObject_Free(&flow->d_obj);
330  
331 // remove from current flow
332 if (flow == m->sending_flow) {
333 m->sending_flow = NULL;
334 }
335  
336 // remove from previous flow
337 if (flow == m->previous_flow) {
338 m->previous_flow = NULL;
339 }
340  
341 // remove from queue
342 if (flow->is_queued) {
343 PacketPassFairQueue__Tree_Remove(&m->queued_tree, 0, flow);
344 }
345  
346 // remove from flows list
347 LinkedList1_Remove(&m->flows_list, &flow->list_node);
348  
349 // free input
350 PacketPassInterface_Free(&flow->input);
351 }
352  
353 void PacketPassFairQueueFlow_AssertFree (PacketPassFairQueueFlow *flow)
354 {
355 PacketPassFairQueue *m = flow->m;
356 B_USE(m)
357  
358 ASSERT(m->freeing || flow != m->sending_flow)
359 DebugObject_Access(&flow->d_obj);
360 }
361  
362 int PacketPassFairQueueFlow_IsBusy (PacketPassFairQueueFlow *flow)
363 {
364 PacketPassFairQueue *m = flow->m;
365  
366 ASSERT(!m->freeing)
367 DebugObject_Access(&flow->d_obj);
368  
369 return (flow == m->sending_flow);
370 }
371  
372 void PacketPassFairQueueFlow_RequestCancel (PacketPassFairQueueFlow *flow)
373 {
374 PacketPassFairQueue *m = flow->m;
375  
376 ASSERT(flow == m->sending_flow)
377 ASSERT(m->use_cancel)
378 ASSERT(!m->freeing)
379 ASSERT(!BPending_IsSet(&m->schedule_job))
380 DebugObject_Access(&flow->d_obj);
381  
382 // request cancel
383 PacketPassInterface_Sender_RequestCancel(m->output);
384 }
385  
386 void PacketPassFairQueueFlow_SetBusyHandler (PacketPassFairQueueFlow *flow, PacketPassFairQueue_handler_busy handler, void *user)
387 {
388 PacketPassFairQueue *m = flow->m;
389 B_USE(m)
390  
391 ASSERT(flow == m->sending_flow)
392 ASSERT(!m->freeing)
393 DebugObject_Access(&flow->d_obj);
394  
395 // set handler
396 flow->handler_busy = handler;
397 flow->user = user;
398 }
399  
400 PacketPassInterface * PacketPassFairQueueFlow_GetInput (PacketPassFairQueueFlow *flow)
401 {
402 DebugObject_Access(&flow->d_obj);
403  
404 return &flow->input;
405 }