]>
git.proxmox.com Git - ovs.git/blob - ofproto/pinsched.c
2 * Copyright (c) 2008, 2009, 2010, 2011 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"
34 struct hmap_node node
; /* In struct pinsched's 'queues' hmap. */
35 uint16_t port_no
; /* Port number. */
36 struct list packets
; /* Contains "struct ofpbuf"s. */
37 int n
; /* Number of packets in 'packets'. */
41 /* Client-supplied parameters. */
42 int rate_limit
; /* Packets added to bucket per second. */
43 int burst_limit
; /* Maximum token bucket size, in packets. */
45 /* One queue per physical port. */
46 struct hmap queues
; /* Contains "struct pinqueue"s. */
47 int n_queued
; /* Sum over queues[*].n. */
48 struct pinqueue
*next_txq
; /* Next pinqueue check in round-robin. */
52 * It costs 1000 tokens to send a single packet_in message. A single token
53 * per message would be more straightforward, but this choice lets us avoid
54 * round-off error in refill_bucket()'s calculation of how many tokens to
55 * add to the bucket, since no division step is needed. */
56 long long int last_fill
; /* Time at which we last added tokens. */
57 int tokens
; /* Current number of tokens. */
59 /* Transmission queue. */
60 int n_txq
; /* No. of packets waiting in rconn for tx. */
62 /* Statistics reporting. */
63 unsigned long long n_normal
; /* # txed w/o rate limit queuing. */
64 unsigned long long n_limited
; /* # queued for rate limiting. */
65 unsigned long long n_queue_dropped
; /* # dropped due to queue overflow. */
69 advance_txq(struct pinsched
*ps
)
71 struct hmap_node
*next
;
74 ? hmap_next(&ps
->queues
, &ps
->next_txq
->node
)
75 : hmap_first(&ps
->queues
));
76 ps
->next_txq
= next
? CONTAINER_OF(next
, struct pinqueue
, node
) : NULL
;
79 static struct ofpbuf
*
80 dequeue_packet(struct pinsched
*ps
, struct pinqueue
*q
)
82 struct ofpbuf
*packet
= ofpbuf_from_list(list_pop_front(&q
->packets
));
88 /* Destroys 'q' and removes it from 'ps''s set of queues.
89 * (The caller must ensure that 'q' is empty.) */
91 pinqueue_destroy(struct pinsched
*ps
, struct pinqueue
*q
)
93 hmap_remove(&ps
->queues
, &q
->node
);
97 static struct pinqueue
*
98 pinqueue_get(struct pinsched
*ps
, uint16_t port_no
)
100 uint32_t hash
= hash_int(port_no
, 0);
103 HMAP_FOR_EACH_IN_BUCKET (q
, node
, hash
, &ps
->queues
) {
104 if (port_no
== q
->port_no
) {
109 q
= xmalloc(sizeof *q
);
110 hmap_insert(&ps
->queues
, &q
->node
, hash
);
111 q
->port_no
= port_no
;
112 list_init(&q
->packets
);
117 /* Drop a packet from the longest queue in 'ps'. */
119 drop_packet(struct pinsched
*ps
)
121 struct pinqueue
*longest
; /* Queue currently selected as longest. */
122 int n_longest
= 0; /* # of queues of same length as 'longest'. */
125 ps
->n_queue_dropped
++;
128 HMAP_FOR_EACH (q
, node
, &ps
->queues
) {
129 if (!longest
|| longest
->n
< q
->n
) {
132 } else if (longest
->n
== q
->n
) {
135 /* Randomly select one of the longest queues, with a uniform
136 * distribution (Knuth algorithm 3.4.2R). */
137 if (!random_range(n_longest
)) {
143 /* FIXME: do we want to pop the tail instead? */
144 ofpbuf_delete(dequeue_packet(ps
, longest
));
145 if (longest
->n
== 0) {
146 pinqueue_destroy(ps
, longest
);
150 /* Remove and return the next packet to transmit (in round-robin order). */
151 static struct ofpbuf
*
152 get_tx_packet(struct pinsched
*ps
)
154 struct ofpbuf
*packet
;
162 packet
= dequeue_packet(ps
, q
);
165 pinqueue_destroy(ps
, q
);
171 /* Add tokens to the bucket based on elapsed time. */
173 refill_bucket(struct pinsched
*ps
)
175 long long int now
= time_msec();
176 long long int tokens
= (now
- ps
->last_fill
) * ps
->rate_limit
+ ps
->tokens
;
177 if (tokens
>= 1000) {
179 ps
->tokens
= MIN(tokens
, ps
->burst_limit
* 1000);
183 /* Attempts to remove enough tokens from 'ps' to transmit a packet. Returns
184 * true if successful, false otherwise. (In the latter case no tokens are
187 get_token(struct pinsched
*ps
)
189 if (ps
->tokens
>= 1000) {
198 pinsched_send(struct pinsched
*ps
, uint16_t port_no
,
199 struct ofpbuf
*packet
, pinsched_tx_cb
*cb
, void *aux
)
203 } else if (!ps
->n_queued
&& get_token(ps
)) {
204 /* In the common case where we are not constrained by the rate limit,
205 * let the packet take the normal path. */
209 /* Otherwise queue it up for the periodic callback to drain out. */
212 /* We are called with a buffer obtained from dpif_recv() that has much
213 * more allocated space than actual content most of the time. Since
214 * we're going to store the packet for some time, free up that
215 * otherwise wasted space. */
218 if (ps
->n_queued
>= ps
->burst_limit
) {
221 q
= pinqueue_get(ps
, port_no
);
222 list_push_back(&q
->packets
, &packet
->list_node
);
230 pinsched_run(struct pinsched
*ps
, pinsched_tx_cb
*cb
, void *aux
)
235 /* Drain some packets out of the bucket if possible, but limit the
236 * number of iterations to allow other code to get work done too. */
238 for (i
= 0; ps
->n_queued
&& get_token(ps
) && i
< 50; i
++) {
239 cb(get_tx_packet(ps
), aux
);
245 pinsched_wait(struct pinsched
*ps
)
247 if (ps
&& ps
->n_queued
) {
248 if (ps
->tokens
>= 1000) {
249 /* We can transmit more packets as soon as we're called again. */
250 poll_immediate_wake();
252 /* We have to wait for the bucket to re-fill. We could calculate
253 * the exact amount of time here for increased smoothness. */
254 poll_timer_wait(TIME_UPDATE_INTERVAL
/ 2);
259 /* Creates and returns a scheduler for sending packet-in messages. */
261 pinsched_create(int rate_limit
, int burst_limit
)
265 ps
= xzalloc(sizeof *ps
);
266 hmap_init(&ps
->queues
);
269 ps
->last_fill
= time_msec();
270 ps
->tokens
= rate_limit
* 100;
274 ps
->n_queue_dropped
= 0;
275 pinsched_set_limits(ps
, rate_limit
, burst_limit
);
281 pinsched_destroy(struct pinsched
*ps
)
284 struct pinqueue
*q
, *next
;
286 HMAP_FOR_EACH_SAFE (q
, next
, node
, &ps
->queues
) {
287 hmap_remove(&ps
->queues
, &q
->node
);
288 ofpbuf_list_delete(&q
->packets
);
291 hmap_destroy(&ps
->queues
);
297 pinsched_get_limits(const struct pinsched
*ps
,
298 int *rate_limit
, int *burst_limit
)
300 *rate_limit
= ps
->rate_limit
;
301 *burst_limit
= ps
->burst_limit
;
305 pinsched_set_limits(struct pinsched
*ps
, int rate_limit
, int burst_limit
)
307 if (rate_limit
<= 0) {
310 if (burst_limit
<= 0) {
311 burst_limit
= rate_limit
/ 4;
313 burst_limit
= MAX(burst_limit
, 1);
314 burst_limit
= MIN(burst_limit
, INT_MAX
/ 1000);
316 ps
->rate_limit
= rate_limit
;
317 ps
->burst_limit
= burst_limit
;
318 while (ps
->n_queued
> burst_limit
) {