2 * Copyright (c) 2008, 2009, 2010 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 <sys/types.h>
20 #include <netinet/in.h>
21 #include <arpa/inet.h>
26 #include "openflow/openflow.h"
27 #include "poll-loop.h"
28 #include "port-array.h"
36 struct wdp_packet_queue {
42 /* Client-supplied parameters. */
43 int rate_limit; /* Packets added to bucket per second. */
44 int burst_limit; /* Maximum token bucket size, in packets. */
46 /* One queue per physical port. */
47 struct port_array queues; /* Array of "struct wdp_packet_queue". */
48 int n_queued; /* Sum over queues[*].n. */
49 unsigned int last_tx_port; /* Last port checked in round-robin. */
53 * It costs 1000 tokens to send a single packet_in message. A single token
54 * per message would be more straightforward, but this choice lets us avoid
55 * round-off error in refill_bucket()'s calculation of how many tokens to
56 * add to the bucket, since no division step is needed. */
57 long long int last_fill; /* Time at which we last added tokens. */
58 int tokens; /* Current number of tokens. */
60 /* Transmission queue. */
61 int n_txq; /* No. of packets waiting in rconn for tx. */
63 /* Statistics reporting. */
64 unsigned long long n_normal; /* # txed w/o rate limit queuing. */
65 unsigned long long n_limited; /* # queued for rate limiting. */
66 unsigned long long n_queue_dropped; /* # dropped due to queue overflow. */
69 struct status_category *ss_cat;
72 static struct wdp_packet *
73 dequeue_packet(struct pinsched *ps, struct wdp_packet_queue *q,
76 struct wdp_packet *packet;
78 packet = CONTAINER_OF(list_pop_front(&q->list), struct wdp_packet, list);
80 if (list_is_empty(&q->list)) {
82 port_array_delete(&ps->queues, port_no);
88 /* Drop a packet from the longest queue in 'ps'. */
90 drop_packet(struct pinsched *ps)
92 struct wdp_packet_queue *longest;
94 unsigned int longest_port_no;
96 struct wdp_packet_queue *q;
98 ps->n_queue_dropped++;
100 longest = port_array_first(&ps->queues, &port_no);
101 longest_port_no = port_no;
103 while ((q = port_array_next(&ps->queues, &port_no)) != NULL) {
104 if (longest->n < q->n) {
107 } else if (longest->n == q->n) {
110 /* Randomly select one of the longest queues, with a uniform
111 * distribution (Knuth algorithm 3.4.2R). */
112 if (!random_range(n_longest)) {
114 longest_port_no = port_no;
119 /* FIXME: do we want to pop the tail instead? */
120 wdp_packet_destroy(dequeue_packet(ps, longest, longest_port_no));
123 /* Remove and return the next packet to transmit (in round-robin order). */
124 static struct wdp_packet *
125 get_tx_packet(struct pinsched *ps)
127 struct wdp_packet_queue *q;
129 q = port_array_next(&ps->queues, &ps->last_tx_port);
131 q = port_array_first(&ps->queues, &ps->last_tx_port);
133 return dequeue_packet(ps, q, ps->last_tx_port);
136 /* Add tokens to the bucket based on elapsed time. */
138 refill_bucket(struct pinsched *ps)
140 long long int now = time_msec();
141 long long int tokens = (now - ps->last_fill) * ps->rate_limit + ps->tokens;
142 if (tokens >= 1000) {
144 ps->tokens = MIN(tokens, ps->burst_limit * 1000);
148 /* Attempts to remove enough tokens from 'ps' to transmit a packet. Returns
149 * true if successful, false otherwise. (In the latter case no tokens are
152 get_token(struct pinsched *ps)
154 if (ps->tokens >= 1000) {
163 pinsched_send(struct pinsched *ps, uint16_t port_no,
164 struct wdp_packet *packet, pinsched_tx_cb *cb, void *aux)
168 } else if (!ps->n_queued && get_token(ps)) {
169 /* In the common case where we are not constrained by the rate limit,
170 * let the packet take the normal path. */
174 /* Otherwise queue it up for the periodic callback to drain out. */
175 struct wdp_packet_queue *q;
177 /* We are called with a buffer obtained from xfif_recv() that has much
178 * more allocated space than actual content most of the time. Since
179 * we're going to store the packet for some time, free up that
180 * otherwise wasted space. */
181 ofpbuf_trim(packet->payload);
183 if (ps->n_queued >= ps->burst_limit) {
186 q = port_array_get(&ps->queues, port_no);
188 q = xmalloc(sizeof *q);
191 port_array_set(&ps->queues, port_no, q);
193 list_push_back(&q->list, &packet->list);
201 pinsched_status_cb(struct status_reply *sr, void *ps_)
203 struct pinsched *ps = ps_;
205 status_reply_put(sr, "normal=%llu", ps->n_normal);
206 status_reply_put(sr, "limited=%llu", ps->n_limited);
207 status_reply_put(sr, "queue-dropped=%llu", ps->n_queue_dropped);
211 pinsched_run(struct pinsched *ps, pinsched_tx_cb *cb, void *aux)
216 /* Drain some packets out of the bucket if possible, but limit the
217 * number of iterations to allow other code to get work done too. */
219 for (i = 0; ps->n_queued && get_token(ps) && i < 50; i++) {
220 cb(get_tx_packet(ps), aux);
226 pinsched_wait(struct pinsched *ps)
228 if (ps && ps->n_queued) {
229 if (ps->tokens >= 1000) {
230 /* We can transmit more packets as soon as we're called again. */
231 poll_immediate_wake();
233 /* We have to wait for the bucket to re-fill. We could calculate
234 * the exact amount of time here for increased smoothness. */
235 poll_timer_wait(TIME_UPDATE_INTERVAL / 2);
240 /* Creates and returns a scheduler for sending packet-in messages. */
242 pinsched_create(int rate_limit, int burst_limit, struct switch_status *ss)
246 ps = xzalloc(sizeof *ps);
247 port_array_init(&ps->queues);
249 ps->last_tx_port = PORT_ARRAY_SIZE;
250 ps->last_fill = time_msec();
251 ps->tokens = rate_limit * 100;
255 ps->n_queue_dropped = 0;
256 pinsched_set_limits(ps, rate_limit, burst_limit);
259 ps->ss_cat = switch_status_register(ss, "rate-limit",
260 pinsched_status_cb, ps);
267 pinsched_destroy(struct pinsched *ps)
270 struct ovs_queue *queue;
271 unsigned int port_no;
273 PORT_ARRAY_FOR_EACH (queue, &ps->queues, port_no) {
274 queue_destroy(queue);
277 port_array_destroy(&ps->queues);
278 switch_status_unregister(ps->ss_cat);
284 pinsched_get_limits(const struct pinsched *ps,
285 int *rate_limit, int *burst_limit)
287 *rate_limit = ps->rate_limit;
288 *burst_limit = ps->burst_limit;
292 pinsched_set_limits(struct pinsched *ps, int rate_limit, int burst_limit)
294 if (rate_limit <= 0) {
297 if (burst_limit <= 0) {
298 burst_limit = rate_limit / 4;
300 burst_limit = MAX(burst_limit, 1);
301 burst_limit = MIN(burst_limit, INT_MAX / 1000);
303 ps->rate_limit = rate_limit;
304 ps->burst_limit = burst_limit;
305 while (ps->n_queued > burst_limit) {