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