1 // L2TPNS: token bucket filters
3 char const *cvs_id_tbf
= "$Id: tbf.c,v 1.5 2004/08/26 06:22:37 fred_nerk Exp $";
15 tbft
*filter_list
= NULL
;
16 static int filter_list_size
= 0;
18 static int timer_chain
= -1; // Head of timer chain.
20 static void tbf_run_queue(int tbf_id
);
24 filter_list
= mmap(NULL
, sizeof(*filter_list
) * MAXTBFS
, PROT_READ
| PROT_WRITE
, MAP_SHARED
| MAP_ANONYMOUS
, 0, 0);
28 filter_list_size
= MAXTBFS
;
29 filter_list
[0].sid
= -1; // Reserved.
32 // Put a TBF on the timer list.
33 // This is a doubly linked list..
34 // We put ourselves on the tail of the list.
36 static void add_to_timer(int id
)
41 if (timer_chain
== -1) {
42 filter_list
[id
].next
= filter_list
[id
].prev
= id
;
47 filter_list
[id
].next
= timer_chain
;
48 filter_list
[id
].prev
= filter_list
[timer_chain
].prev
;
49 filter_list
[filter_list
[timer_chain
].prev
].next
= id
;
50 filter_list
[timer_chain
].prev
= id
;
54 // Remove a TBF from the timer list.
55 // This is a doubly linked list.
56 static void del_from_timer(int id
)
61 if (filter_list
[id
].next
== id
) { // Last element in chain?
62 if (timer_chain
!= id
) { // WTF?
63 log(0,0,0,0, "Removed a singleton element from TBF, but tc didn't point to it!\n");
66 filter_list
[id
].next
= filter_list
[id
].prev
= 0;
70 filter_list
[filter_list
[id
].next
].prev
= filter_list
[id
].prev
;
71 filter_list
[filter_list
[id
].prev
].next
= filter_list
[id
].next
;
72 if (timer_chain
== id
)
73 timer_chain
= filter_list
[id
].next
;
75 filter_list
[id
].next
= filter_list
[id
].prev
= 0; // Mark as off the timer chain.
79 // Free a token bucket filter structure for re-use.
84 if (tid
< 1) // Make sure we don't free id # 0
87 if (!filter_list
) // WTF?
90 if (filter_list
[tid
].next
)
92 filter_list
[tid
].sid
= 0;
98 // Allocate a new token bucket filter.
100 int new_tbf(int sid
, int max_credit
, int rate
, void (*f
)(sessionidt
, u8
*, int))
105 log(3,0,0,0, "Allocating new TBF (sess %d, rate %d, helper %p)\n", sid
, rate
, f
);
108 return 0; // Couldn't alloc memory!
112 for (i
= 0 ; i
< filter_list_size
; ++i
, p
= (p
+1)%filter_list_size
) {
113 if (filter_list
[p
].sid
)
116 memset((void*) &filter_list
[p
], 0, sizeof(filter_list
[p
]) ); // Clear counters and data.
117 filter_list
[p
].sid
= sid
;
118 filter_list
[p
].credit
= max_credit
;
119 filter_list
[p
].queued
= 0;
120 filter_list
[p
].max_credit
= max_credit
;
121 filter_list
[p
].rate
= rate
;
122 filter_list
[p
].oldest
= 0;
123 filter_list
[p
].send
= f
;
128 // All allocated filters are used! Increase the size of the allocated
132 int new_size
= filter_list_size
* 2;
133 tbft
*new = mremap(filter_list
, filter_list_size
* sizeof(*new), new_size
* sizeof(*new), MREMAP_MAYMOVE
);
135 if (new == MAP_FAILED
)
137 log(0,0,0,0, "Ran out of token bucket filters and mremap failed! Sess %d will be un-throttled\n", sid
);
141 i
= filter_list_size
;
142 filter_list_size
= new_size
;
146 for (; i
< filter_list_size
; ++i
)
147 filter_list
[i
].sid
= 0;
151 log(0,0,0,0, "Ran out of token bucket filters! Sess %d will be un-throttled\n", sid
);
157 // Sanity check all the TBF records. This is
158 // typically done when we become a master..
167 for (i
= 1; i
< filter_list_size
; ++i
) {
168 if (!filter_list
[i
].sid
) // Is it used??
171 sid
= filter_list
[i
].sid
;
172 if (i
!= session
[sid
].tbf_in
&&
173 i
!= session
[sid
].tbf_out
) { // Ooops.
175 free_tbf(i
); // Mark it as free...
179 for (i
= 0; i
< config
->cluster_highest_sessionid
; ++i
) {
180 if (session
[i
].tbf_in
&& filter_list
[session
[i
].tbf_in
].sid
!= i
) {
181 filter_list
[session
[i
].tbf_in
].sid
= i
; // Ouch!? FIXME. What to do here?
183 if (session
[i
].tbf_out
&& filter_list
[session
[i
].tbf_out
].sid
!= i
) {
184 filter_list
[session
[i
].tbf_out
].sid
= i
; // Ouch!? FIXME. What to do here?
191 // Run a packet through a token bucket filter.
192 // If we can send it right away, we do. Else we
193 // try and queue it to send later. Else we drop it.
195 int tbf_queue_packet(int tbf_id
, char * data
, int size
)
203 if (tbf_id
> filter_list_size
|| tbf_id
< 1) { // Out of range ID??
204 // Very bad. Just drop it.
208 f
= &filter_list
[tbf_id
];
210 if (!f
->sid
) // Is this a real structure??
213 tbf_run_queue(tbf_id
); // Caculate credit and send any queued packets if possible..
218 if (!f
->queued
&& f
->credit
> size
) { // If the queue is empty, and we have
219 // enough credit, just send it now.
222 f
->send(f
->sid
, data
, size
);
226 f
->b_dropped
+= size
;
232 // Not enough credit. Can we have room in the queue?
233 if (f
->queued
>= TBF_MAX_QUEUE
) {
235 f
->b_dropped
+= size
;
236 return -1; // No, just drop it.
239 // Is it too big to fit into a queue slot?
240 if (size
>= TBF_MAX_SIZE
) {
242 f
->b_dropped
+= size
;
243 return -1; // Yes, just drop it.
246 // Ok. We have a slot, and it's big enough to
247 // contain the packet, so queue the packet!
248 i
= ( f
->oldest
+ f
->queued
) % TBF_MAX_QUEUE
;
249 memcpy(f
->packets
[i
], data
, size
);
255 if (!f
->next
) // Are we off the timer chain?
256 add_to_timer(tbf_id
); // Put ourselves on the timer chain.
258 return 0; // All done.
262 // Send queued packets from the filter if possible.
263 // (We're normally only called if this is possible.. )
264 static void tbf_run_queue(int tbf_id
)
271 f
= &filter_list
[tbf_id
];
273 // Calculate available credit...
274 f
->credit
+= (TIME
- f
->lasttime
) * f
->rate
/ 10; // current time is 1/10th of a second.
275 if (f
->credit
> f
->max_credit
)
276 f
->credit
= f
->max_credit
;
279 while (f
->queued
> 0 && f
->credit
>= f
->sizes
[f
->oldest
]) { // While we have enough credit..
282 f
->send(f
->sid
, f
->packets
[f
->oldest
], f
->sizes
[f
->oldest
]);
283 f
->b_sent
+= f
->sizes
[f
->oldest
];
286 f
->b_dropped
+= f
->sizes
[f
->oldest
];
290 f
->credit
-= f
->sizes
[f
->oldest
];
292 f
->oldest
= (f
->oldest
+ 1 ) % TBF_MAX_QUEUE
;
293 f
->queued
--; // One less queued packet..
296 if (f
->queued
) // Still more to do. Hang around on the timer list.
299 if (f
->next
) // Are we on the timer list??
300 del_from_timer(tbf_id
); // Nothing more to do. Get off the timer list.
304 // Periodically walk the timer list..
306 int tbf_run_timer(void)
309 int count
= filter_list_size
+ 1; // Safety check.
311 int tbf_id
; // structure being processed.
314 return 0; // Nothing to do...
316 if (!filter_list
) // No structures built yet.
319 last
= filter_list
[i
].prev
; // last element to process.
323 i
= filter_list
[i
].next
; // Get the next in the queue.
325 tbf_run_queue(tbf_id
); // Run the timer queue..
326 } while ( timer_chain
> 0 && i
&& tbf_id
!= last
&& --count
> 0);
330 for (i
= 0; i
< filter_list_size
; ++i
) {
331 if (!filter_list
[i
].next
)
333 if (filter_list
[i
].lasttime
== TIME
) // Did we just run it?
336 log(1,0,0,0, "Missed tbf %d! Not on the timer chain?(n %d, p %d, tc %d)\n", i
,
337 filter_list
[i
].next
, filter_list
[i
].prev
, timer_chain
);
345 int cmd_show_tbf(struct cli_def
*cli
, char *command
, char **argv
, int argc
)
350 if (CLI_HELP_REQUESTED
)
351 return CLI_HELP_NO_ARGS
;
353 if (!config
->cluster_iam_master
) {
354 cli_print(cli
, "Can't do this on a slave. Do it on %s", inet_toa(config
->cluster_master_address
));
361 cli_print(cli
,"%6s %5s %5s %6s %6s | %7s %7s %8s %8s %8s %8s", "TBF#", "Sid", "Rate", "Credit", "Queued",
362 "ByteIn","PackIn","ByteSent","PackSent", "PackDrop", "PackDelay");
364 for (i
= 1; i
< filter_list_size
; ++i
) {
365 if (!filter_list
[i
].sid
) // Is it used?
368 cli_print(cli
, "%5d%1s %5d %5d %6d %6d | %7d %7d %8d %8d %8d %8d",
369 i
, (filter_list
[i
].next
? "*" : " "),
371 filter_list
[i
].rate
* 8,
372 filter_list
[i
].credit
,
373 filter_list
[i
].queued
,
375 filter_list
[i
].b_queued
,
376 filter_list
[i
].p_queued
,
377 filter_list
[i
].b_sent
,
378 filter_list
[i
].p_sent
,
379 filter_list
[i
].p_dropped
,
380 filter_list
[i
].p_delayed
);
383 cli_print(cli
, "%d tbf entries used, %d total", count
, filter_list_size
);