]>
git.proxmox.com Git - mirror_ovs.git/blob - ofproto/pinsched.c
2 * Copyright (c) 2008, 2009 Nicira Networks.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
19 #include <arpa/inet.h>
22 #include "openflow/openflow.h"
23 #include "poll-loop.h"
24 #include "port-array.h"
33 /* Client-supplied parameters. */
34 int rate_limit
; /* Packets added to bucket per second. */
35 int burst_limit
; /* Maximum token bucket size, in packets. */
37 /* One queue per physical port. */
38 struct port_array queues
; /* Array of "struct ovs_queue *". */
39 int n_queued
; /* Sum over queues[*].n. */
40 unsigned int last_tx_port
; /* Last port checked in round-robin. */
44 * It costs 1000 tokens to send a single packet_in message. A single token
45 * per message would be more straightforward, but this choice lets us avoid
46 * round-off error in refill_bucket()'s calculation of how many tokens to
47 * add to the bucket, since no division step is needed. */
48 long long int last_fill
; /* Time at which we last added tokens. */
49 int tokens
; /* Current number of tokens. */
51 /* Transmission queue. */
52 int n_txq
; /* No. of packets waiting in rconn for tx. */
54 /* Statistics reporting. */
55 unsigned long long n_normal
; /* # txed w/o rate limit queuing. */
56 unsigned long long n_limited
; /* # queued for rate limiting. */
57 unsigned long long n_queue_dropped
; /* # dropped due to queue overflow. */
60 struct status_category
*ss_cat
;
63 static struct ofpbuf
*
64 dequeue_packet(struct pinsched
*ps
, struct ovs_queue
*q
,
67 struct ofpbuf
*packet
= queue_pop_head(q
);
70 port_array_set(&ps
->queues
, port_no
, NULL
);
76 /* Drop a packet from the longest queue in 'ps'. */
78 drop_packet(struct pinsched
*ps
)
80 struct ovs_queue
*longest
; /* Queue currently selected as longest. */
81 int n_longest
; /* # of queues of same length as 'longest'. */
82 unsigned int longest_port_no
;
86 ps
->n_queue_dropped
++;
88 longest
= port_array_first(&ps
->queues
, &port_no
);
89 longest_port_no
= port_no
;
91 while ((q
= port_array_next(&ps
->queues
, &port_no
)) != NULL
) {
92 if (longest
->n
< q
->n
) {
95 } else if (longest
->n
== q
->n
) {
98 /* Randomly select one of the longest queues, with a uniform
99 * distribution (Knuth algorithm 3.4.2R). */
100 if (!random_range(n_longest
)) {
102 longest_port_no
= port_no
;
107 /* FIXME: do we want to pop the tail instead? */
108 ofpbuf_delete(dequeue_packet(ps
, longest
, longest_port_no
));
111 /* Remove and return the next packet to transmit (in round-robin order). */
112 static struct ofpbuf
*
113 get_tx_packet(struct pinsched
*ps
)
115 struct ovs_queue
*q
= port_array_next(&ps
->queues
, &ps
->last_tx_port
);
117 q
= port_array_first(&ps
->queues
, &ps
->last_tx_port
);
119 return dequeue_packet(ps
, q
, ps
->last_tx_port
);
122 /* Add tokens to the bucket based on elapsed time. */
124 refill_bucket(struct pinsched
*ps
)
126 long long int now
= time_msec();
127 long long int tokens
= (now
- ps
->last_fill
) * ps
->rate_limit
+ ps
->tokens
;
128 if (tokens
>= 1000) {
130 ps
->tokens
= MIN(tokens
, ps
->burst_limit
* 1000);
134 /* Attempts to remove enough tokens from 'ps' to transmit a packet. Returns
135 * true if successful, false otherwise. (In the latter case no tokens are
138 get_token(struct pinsched
*ps
)
140 if (ps
->tokens
>= 1000) {
149 pinsched_send(struct pinsched
*ps
, uint16_t port_no
,
150 struct ofpbuf
*packet
, pinsched_tx_cb
*cb
, void *aux
)
154 } else if (!ps
->n_queued
&& get_token(ps
)) {
155 /* In the common case where we are not constrained by the rate limit,
156 * let the packet take the normal path. */
160 /* Otherwise queue it up for the periodic callback to drain out. */
163 /* We are called with a buffer obtained from dpif_recv() that has much
164 * more allocated space than actual content most of the time. Since
165 * we're going to store the packet for some time, free up that
166 * otherwise wasted space. */
169 if (ps
->n_queued
>= ps
->burst_limit
) {
172 q
= port_array_get(&ps
->queues
, port_no
);
174 q
= xmalloc(sizeof *q
);
176 port_array_set(&ps
->queues
, port_no
, q
);
178 queue_push_tail(q
, packet
);
185 pinsched_status_cb(struct status_reply
*sr
, void *ps_
)
187 struct pinsched
*ps
= ps_
;
189 status_reply_put(sr
, "normal=%llu", ps
->n_normal
);
190 status_reply_put(sr
, "limited=%llu", ps
->n_limited
);
191 status_reply_put(sr
, "queue-dropped=%llu", ps
->n_queue_dropped
);
195 pinsched_run(struct pinsched
*ps
, pinsched_tx_cb
*cb
, void *aux
)
200 /* Drain some packets out of the bucket if possible, but limit the
201 * number of iterations to allow other code to get work done too. */
203 for (i
= 0; ps
->n_queued
&& get_token(ps
) && i
< 50; i
++) {
204 cb(get_tx_packet(ps
), aux
);
210 pinsched_wait(struct pinsched
*ps
)
212 if (ps
&& ps
->n_queued
) {
213 if (ps
->tokens
>= 1000) {
214 /* We can transmit more packets as soon as we're called again. */
215 poll_immediate_wake();
217 /* We have to wait for the bucket to re-fill. We could calculate
218 * the exact amount of time here for increased smoothness. */
219 poll_timer_wait(TIME_UPDATE_INTERVAL
/ 2);
224 /* Creates and returns a scheduler for sending packet-in messages. */
226 pinsched_create(int rate_limit
, int burst_limit
, struct switch_status
*ss
)
230 ps
= xcalloc(1, sizeof *ps
);
231 port_array_init(&ps
->queues
);
233 ps
->last_tx_port
= PORT_ARRAY_SIZE
;
234 ps
->last_fill
= time_msec();
235 ps
->tokens
= rate_limit
* 100;
239 ps
->n_queue_dropped
= 0;
240 pinsched_set_limits(ps
, rate_limit
, burst_limit
);
243 ps
->ss_cat
= switch_status_register(ss
, "rate-limit",
244 pinsched_status_cb
, ps
);
251 pinsched_destroy(struct pinsched
*ps
)
254 struct ovs_queue
*queue
;
255 unsigned int port_no
;
257 PORT_ARRAY_FOR_EACH (queue
, &ps
->queues
, port_no
) {
258 queue_destroy(queue
);
261 port_array_destroy(&ps
->queues
);
262 switch_status_unregister(ps
->ss_cat
);
268 pinsched_set_limits(struct pinsched
*ps
, int rate_limit
, int burst_limit
)
270 if (rate_limit
<= 0) {
273 if (burst_limit
<= 0) {
274 burst_limit
= rate_limit
/ 4;
276 burst_limit
= MAX(burst_limit
, 1);
277 burst_limit
= MIN(burst_limit
, INT_MAX
/ 1000);
279 ps
->rate_limit
= rate_limit
;
280 ps
->burst_limit
= burst_limit
;
281 while (ps
->n_queued
> burst_limit
) {