c024c6740b1dd42feaba98e899d67fb4e567386d
[l2tpns.git] / tbf.c
1 #include <malloc.h>
2 #include <string.h>
3 #include <unistd.h>
4 #include <sys/mman.h>
5
6 #include "l2tpns.h"
7 #include "tbf.h"
8
9 // Need a time interval.
10
11 #define TBF_MAX_QUEUE 2 // Maximum of 2 queued packet per
12 #define TBF_MAX_SIZE 3000 // Maxiumum queued packet size is 2048.
13
14 #define TBF_MAX_CREDIT 6000 // Maximum 6000 bytes of credit.
15 #define TBF_RATE 360 // 360 bytes per 1/10th of a second.
16
17 typedef struct {
18 int credit;
19 int lasttime;
20 int queued;
21 int oldest; // Position of packet in the ring buffer.
22 sessionidt sid; // associated session ID.
23 int max_credit; // Maximum amount of credit available (burst size).
24 int rate; // How many bytes of credit per second we get? (sustained rate)
25 void (*send)(sessionidt s, u8 *, int); // Routine to actually send out the data.
26 int prev; // Timer chain position.
27 int next; // Timer chain position.
28
29 u32 b_queued; // Total bytes sent through this TBF
30 u32 b_sent; // Total bytes sucessfully made it to the network.
31 u32 p_queued; // ditto packets.
32 u32 p_sent; // ditto packets.
33 u32 b_dropped; // Total bytes dropped.
34 u32 p_dropped; // Total packets dropped.
35 u32 p_delayed; // Total packets not sent immediately.
36
37 int sizes[TBF_MAX_QUEUE];
38 char packets[TBF_MAX_QUEUE][TBF_MAX_SIZE];
39 } tbft;
40
41
42 tbft * filter_list = NULL;
43 int filter_list_size = 0;
44
45 static int timer_chain = -1; // Head of timer chain.
46
47 static void tbf_run_queue(int tbf_id);
48
49 void init_tbf(void)
50 {
51 filter_list = mmap(NULL, sizeof(*filter_list) * MAXTBFS, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, 0, 0);
52 if (!filter_list)
53 return;
54
55 filter_list_size = MAXTBFS;
56 filter_list[0].sid = -1; // Reserved.
57 }
58 //
59 // Put a TBF on the timer list.
60 // This is a doubly linked list..
61 // We put ourselves on the tail of the list.
62 //
63 static void add_to_timer(int id)
64 {
65 if (!filter_list)
66 return;
67
68 if (timer_chain == -1) {
69 filter_list[id].next = filter_list[id].prev = id;
70 timer_chain = id;
71 return;
72 }
73
74 filter_list[id].next = timer_chain;
75 filter_list[id].prev = filter_list[timer_chain].prev;
76 filter_list[filter_list[timer_chain].prev].next = id;
77 filter_list[timer_chain].prev = id;
78 }
79
80 //
81 // Remove a TBF from the timer list.
82 // This is a doubly linked list.
83 static void del_from_timer(int id)
84 {
85 if (!filter_list)
86 return;
87
88 if (filter_list[id].next == id) { // Last element in chain?
89 if (timer_chain != id) { // WTF?
90 log(0,0,0,0, "Removed a singleton element from TBF, but tc didn't point to it!\n");
91 } else
92 timer_chain = -1;
93 filter_list[id].next = filter_list[id].prev = 0;
94 return;
95 }
96
97 filter_list[filter_list[id].next].prev = filter_list[id].prev;
98 filter_list[filter_list[id].prev].next = filter_list[id].next;
99 if (timer_chain == id)
100 timer_chain = filter_list[id].next;
101
102 filter_list[id].next = filter_list[id].prev = 0; // Mark as off the timer chain.
103 }
104
105 //
106 // Free a token bucket filter structure for re-use.
107 //
108
109 int free_tbf(int tid)
110 {
111 if (tid < 1) // Make sure we don't free id # 0
112 return -1;
113
114 if (!filter_list) // WTF?
115 return -1;
116
117 if (filter_list[tid].next)
118 del_from_timer(tid);
119 filter_list[tid].sid = 0;
120
121 return 0; // Done!
122 }
123
124 //
125 // Allocate a new token bucket filter.
126 //
127 int new_tbf(int sid, int max_credit, int rate, void (*f)(sessionidt, u8 *, int))
128 {
129 int i;
130 static int p = 0;
131
132 log(3,0,0,0, "Allocating new TBF (sess %d, rate %d, helper %p)\n", sid, rate, f);
133
134 if (!filter_list)
135 return 0; // Couldn't alloc memory!
136
137 // again:
138
139 for (i = 0 ; i < filter_list_size ; ++i, p = (p+1)%filter_list_size ) {
140 if (filter_list[p].sid)
141 continue;
142
143 memset((void*) &filter_list[p], 0, sizeof(filter_list[p]) ); // Clear counters and data.
144 filter_list[p].sid = sid;
145 filter_list[p].credit = max_credit;
146 filter_list[p].queued = 0;
147 filter_list[p].max_credit = max_credit;
148 filter_list[p].rate = rate;
149 filter_list[p].oldest = 0;
150 filter_list[p].send = f;
151 return p;
152 }
153
154 log(0,0,0,0, "Ran out of token bucket filters! Sess %d will be un-throttled\n", sid);
155 return 0;
156
157 #if 0
158 // Not using. Disasterous if called via the CLI! :)
159 // All allocated filters are used! Increase the size of the allocated
160 // filters.
161
162 i = filter_list_size;
163 filter_list_size = filter_list_size * 2 + 1;
164
165 filter_list = realloc(filter_list, filter_list_size * sizeof(*filter_list) );
166
167 for (; i < filter_list_size; ++i)
168 filter_list[i].sid = 0;
169
170 goto again;
171 #endif
172 }
173
174 //
175 // Sanity check all the TBF records. This is
176 // typically done when we become a master..
177 //
178 void fsck_tbfs(void)
179 {
180 int i , sid;
181
182 if (!filter_list)
183 return;
184
185 for (i = 1; i < filter_list_size; ++i) {
186 if (!filter_list[i].sid) // Is it used??
187 continue;
188
189 sid = filter_list[i].sid;
190 if (i != session[sid].tbf_in &&
191 i != session[sid].tbf_out) { // Ooops.
192
193 free_tbf(i); // Mark it as free...
194 }
195 }
196
197 for (i = 0; i < config->cluster_highest_sessionid ; ++i) {
198 if (session[i].tbf_in && filter_list[session[i].tbf_in].sid != i) {
199 filter_list[session[i].tbf_in].sid = i; // Ouch!? FIXME. What to do here?
200 }
201 if (session[i].tbf_out && filter_list[session[i].tbf_out].sid != i) {
202 filter_list[session[i].tbf_out].sid = i; // Ouch!? FIXME. What to do here?
203 }
204 }
205 }
206
207
208 //
209 // Run a packet through a token bucket filter.
210 // If we can send it right away, we do. Else we
211 // try and queue it to send later. Else we drop it.
212 //
213 int tbf_queue_packet(int tbf_id, char * data, int size)
214 {
215 int i;
216 tbft * f;
217
218 if (!filter_list)
219 return -1;
220
221 if (tbf_id > filter_list_size || tbf_id < 1) { // Out of range ID??
222 // Very bad. Just drop it.
223 return -1;
224 }
225
226 f = &filter_list[tbf_id];
227
228 if (!f->sid) // Is this a real structure??
229 return -1;
230
231 tbf_run_queue(tbf_id); // Caculate credit and send any queued packets if possible..
232
233 f->b_queued += size;
234 f->p_queued ++;
235
236 if (!f->queued && f->credit > size) { // If the queue is empty, and we have
237 // enough credit, just send it now.
238 f->credit -= size;
239 if (f->send) {
240 f->send(f->sid, data, size);
241 f->b_sent += size;
242 f->p_sent ++;
243 } else {
244 f->b_dropped += size;
245 f->p_dropped ++;
246 }
247 return size;
248 }
249
250 // Not enough credit. Can we have room in the queue?
251 if (f->queued >= TBF_MAX_QUEUE) {
252 f->p_dropped ++;
253 f->b_dropped += size;
254 return -1; // No, just drop it.
255 }
256
257 // Is it too big to fit into a queue slot?
258 if (size >= TBF_MAX_SIZE) {
259 f->p_dropped ++;
260 f->b_dropped += size;
261 return -1; // Yes, just drop it.
262 }
263
264 // Ok. We have a slot, and it's big enough to
265 // contain the packet, so queue the packet!
266 i = ( f->oldest + f->queued ) % TBF_MAX_QUEUE;
267 memcpy(f->packets[i], data, size);
268
269 f->sizes[i] = size;
270 f->queued ++;
271 f->p_delayed ++;
272
273 if (!f->next) // Are we off the timer chain?
274 add_to_timer(tbf_id); // Put ourselves on the timer chain.
275
276 return 0; // All done.
277 }
278
279 //
280 // Send queued packets from the filter if possible.
281 // (We're normally only called if this is possible.. )
282 static void tbf_run_queue(int tbf_id)
283 {
284 tbft * f;
285
286 if (!filter_list)
287 return;
288
289 f = &filter_list[tbf_id];
290
291 // Calculate available credit...
292 f->credit += (config->current_time - f->lasttime) * f->rate / 10; // current time is 1/10th of a second.
293 if (f->credit > f->max_credit)
294 f->credit = f->max_credit;
295 f->lasttime = config->current_time;
296
297 while (f->queued > 0 && f->credit >= f->sizes[f->oldest]) { // While we have enough credit..
298
299 if (f->send) {
300 f->send(f->sid, f->packets[f->oldest], f->sizes[f->oldest]);
301 f->b_sent += f->sizes[f->oldest];
302 f->p_sent ++;
303 } else {
304 f->b_dropped += f->sizes[f->oldest];
305 f->p_dropped ++;
306 }
307
308 f->credit -= f->sizes[f->oldest];
309
310 f->oldest = (f->oldest + 1 ) % TBF_MAX_QUEUE;
311 f->queued--; // One less queued packet..
312 }
313
314 if (f->queued) // Still more to do. Hang around on the timer list.
315 return;
316
317 if (f->next) // Are we on the timer list??
318 del_from_timer(tbf_id); // Nothing more to do. Get off the timer list.
319 }
320
321 //
322 // Periodically walk the timer list..
323 //
324 int tbf_run_timer(void)
325 {
326 int i = timer_chain;
327 int count = filter_list_size + 1; // Safety check.
328 int last = -1;
329 int tbf_id; // structure being processed.
330
331 if (timer_chain < 0)
332 return 0; // Nothing to do...
333
334 if (!filter_list) // No structures built yet.
335 return 0;
336
337 last = filter_list[i].prev; // last element to process.
338
339 do {
340 tbf_id = i;
341 i = filter_list[i].next; // Get the next in the queue.
342
343 tbf_run_queue(tbf_id); // Run the timer queue..
344 } while ( timer_chain > 0 && i && tbf_id != last && --count > 0);
345
346
347 #if 0 // Debugging.
348 for (i = 0; i < filter_list_size; ++i) {
349 if (!filter_list[i].next)
350 continue;
351 if (filter_list[i].lasttime == config->current_time) // Did we just run it?
352 continue;
353
354 log(1,0,0,0, "Missed tbf %d! Not on the timer chain?(n %d, p %d, tc %d)\n", i,
355 filter_list[i].next, filter_list[i].prev, timer_chain);
356 tbf_run_queue(i);
357 }
358 #endif
359
360 return 1;
361 }
362
363 int cmd_show_tbf(struct cli_def *cli, char *command, char **argv, int argc)
364 {
365 int i;
366 int count = 0;
367
368 if (!config->cluster_iam_master) {
369 cli_print(cli, "Command can't be run on a slave.");
370 return CLI_OK;
371 }
372 if (!filter_list)
373 return CLI_OK;
374
375 cli_print(cli,"%6s %5s %5s %6s %6s | %7s %7s %8s %8s %8s %8s", "TBF#", "Sid", "Rate", "Credit", "Queued",
376 "ByteIn","PackIn","ByteSent","PackSent", "PackDrop", "PackDelay");
377
378 for (i = 1; i < filter_list_size; ++i) {
379 if (!filter_list[i].sid) // Is it used?
380 continue; // No.
381
382 cli_print(cli, "%5d%1s %5d %5d %6d %6d | %7d %7d %8d %8d %8d %8d",
383 i, (filter_list[i].next ? "*" : " "),
384 filter_list[i].sid,
385 filter_list[i].rate * 8,
386 filter_list[i].credit,
387 filter_list[i].queued,
388
389 filter_list[i].b_queued,
390 filter_list[i].p_queued,
391 filter_list[i].b_sent,
392 filter_list[i].p_sent,
393 filter_list[i].p_dropped,
394 filter_list[i].p_delayed);
395 ++count;
396 }
397 cli_print(cli, "%d tbf entries used, %d total", count, filter_list_size);
398 return CLI_OK;
399 }
400