2 * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc.
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>
27 #include "openflow/openflow.h"
28 #include "poll-loop.h"
35 struct hmap_node node; /* In struct pinsched's 'queues' hmap. */
36 uint16_t port_no; /* Port number. */
37 struct list packets; /* Contains "struct ofpbuf"s. */
38 int n; /* Number of packets in 'packets'. */
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 hmap queues; /* Contains "struct pinqueue"s. */
48 int n_queued; /* Sum over queues[*].n. */
49 struct pinqueue *next_txq; /* Next pinqueue check 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. */
70 advance_txq(struct pinsched *ps)
72 struct hmap_node *next;
75 ? hmap_next(&ps->queues, &ps->next_txq->node)
76 : hmap_first(&ps->queues));
77 ps->next_txq = next ? CONTAINER_OF(next, struct pinqueue, node) : NULL;
80 static struct ofpbuf *
81 dequeue_packet(struct pinsched *ps, struct pinqueue *q)
83 struct ofpbuf *packet = ofpbuf_from_list(list_pop_front(&q->packets));
89 /* Destroys 'q' and removes it from 'ps''s set of queues.
90 * (The caller must ensure that 'q' is empty.) */
92 pinqueue_destroy(struct pinsched *ps, struct pinqueue *q)
94 hmap_remove(&ps->queues, &q->node);
98 static struct pinqueue *
99 pinqueue_get(struct pinsched *ps, uint16_t port_no)
101 uint32_t hash = hash_int(port_no, 0);
104 HMAP_FOR_EACH_IN_BUCKET (q, node, hash, &ps->queues) {
105 if (port_no == q->port_no) {
110 q = xmalloc(sizeof *q);
111 hmap_insert(&ps->queues, &q->node, hash);
112 q->port_no = port_no;
113 list_init(&q->packets);
118 /* Drop a packet from the longest queue in 'ps'. */
120 drop_packet(struct pinsched *ps)
122 struct pinqueue *longest; /* Queue currently selected as longest. */
123 int n_longest = 0; /* # of queues of same length as 'longest'. */
126 ps->n_queue_dropped++;
129 HMAP_FOR_EACH (q, node, &ps->queues) {
130 if (!longest || longest->n < q->n) {
133 } else if (longest->n == q->n) {
136 /* Randomly select one of the longest queues, with a uniform
137 * distribution (Knuth algorithm 3.4.2R). */
138 if (!random_range(n_longest)) {
144 /* FIXME: do we want to pop the tail instead? */
145 ofpbuf_delete(dequeue_packet(ps, longest));
146 if (longest->n == 0) {
147 pinqueue_destroy(ps, longest);
151 /* Remove and return the next packet to transmit (in round-robin order). */
152 static struct ofpbuf *
153 get_tx_packet(struct pinsched *ps)
155 struct ofpbuf *packet;
163 packet = dequeue_packet(ps, q);
166 pinqueue_destroy(ps, q);
172 /* Add tokens to the bucket based on elapsed time. */
174 refill_bucket(struct pinsched *ps)
176 long long int now = time_msec();
177 long long int tokens = (now - ps->last_fill) * ps->rate_limit + ps->tokens;
178 if (tokens >= 1000) {
180 ps->tokens = MIN(tokens, ps->burst_limit * 1000);
184 /* Attempts to remove enough tokens from 'ps' to transmit a packet. Returns
185 * true if successful, false otherwise. (In the latter case no tokens are
188 get_token(struct pinsched *ps)
190 if (ps->tokens >= 1000) {
199 pinsched_send(struct pinsched *ps, uint16_t port_no,
200 struct ofpbuf *packet, pinsched_tx_cb *cb, void *aux)
204 } else if (!ps->n_queued && get_token(ps)) {
205 /* In the common case where we are not constrained by the rate limit,
206 * let the packet take the normal path. */
210 /* Otherwise queue it up for the periodic callback to drain out. */
213 /* We might be called with a buffer obtained from dpif_recv() that has
214 * much more allocated space than actual content most of the time.
215 * Since we're going to store the packet for some time, free up that
216 * otherwise wasted space. */
219 if (ps->n_queued >= ps->burst_limit) {
222 q = pinqueue_get(ps, port_no);
223 list_push_back(&q->packets, &packet->list_node);
231 pinsched_run(struct pinsched *ps, pinsched_tx_cb *cb, void *aux)
236 /* Drain some packets out of the bucket if possible, but limit the
237 * number of iterations to allow other code to get work done too. */
239 for (i = 0; ps->n_queued && get_token(ps) && i < 50; i++) {
240 cb(get_tx_packet(ps), aux);
246 pinsched_wait(struct pinsched *ps)
248 if (ps && ps->n_queued) {
249 if (ps->tokens >= 1000) {
250 /* We can transmit more packets as soon as we're called again. */
251 poll_immediate_wake();
253 /* We have to wait for the bucket to re-fill. We could calculate
254 * the exact amount of time here for increased smoothness. */
255 poll_timer_wait(TIME_UPDATE_INTERVAL / 2);
260 /* Creates and returns a scheduler for sending packet-in messages. */
262 pinsched_create(int rate_limit, int burst_limit)
266 ps = xzalloc(sizeof *ps);
267 hmap_init(&ps->queues);
270 ps->last_fill = time_msec();
271 ps->tokens = rate_limit * 100;
275 ps->n_queue_dropped = 0;
276 pinsched_set_limits(ps, rate_limit, burst_limit);
282 pinsched_destroy(struct pinsched *ps)
285 struct pinqueue *q, *next;
287 HMAP_FOR_EACH_SAFE (q, next, node, &ps->queues) {
288 hmap_remove(&ps->queues, &q->node);
289 ofpbuf_list_delete(&q->packets);
292 hmap_destroy(&ps->queues);
298 pinsched_get_limits(const struct pinsched *ps,
299 int *rate_limit, int *burst_limit)
301 *rate_limit = ps->rate_limit;
302 *burst_limit = ps->burst_limit;
306 pinsched_set_limits(struct pinsched *ps, int rate_limit, int burst_limit)
308 if (rate_limit <= 0) {
311 if (burst_limit <= 0) {
312 burst_limit = rate_limit / 4;
314 burst_limit = MAX(burst_limit, 1);
315 burst_limit = MIN(burst_limit, INT_MAX / 1000);
317 ps->rate_limit = rate_limit;
318 ps->burst_limit = burst_limit;
319 while (ps->n_queued > burst_limit) {