socket-util: Move get_mtime() here from stream-ssl.
[openvswitch] / ofproto / pinsched.c
1 /*
2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
3  *
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:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 #include <config.h>
18 #include "pinsched.h"
19 #include <sys/types.h>
20 #include <netinet/in.h>
21 #include <arpa/inet.h>
22 #include <stdint.h>
23 #include <stdlib.h>
24 #include "ofpbuf.h"
25 #include "openflow/openflow.h"
26 #include "poll-loop.h"
27 #include "port-array.h"
28 #include "queue.h"
29 #include "random.h"
30 #include "rconn.h"
31 #include "status.h"
32 #include "timeval.h"
33 #include "vconn.h"
34
35 struct pinsched {
36     /* Client-supplied parameters. */
37     int rate_limit;           /* Packets added to bucket per second. */
38     int burst_limit;          /* Maximum token bucket size, in packets. */
39
40     /* One queue per physical port. */
41     struct port_array queues;   /* Array of "struct ovs_queue *". */
42     int n_queued;               /* Sum over queues[*].n. */
43     unsigned int last_tx_port;  /* Last port checked in round-robin. */
44
45     /* Token bucket.
46      *
47      * It costs 1000 tokens to send a single packet_in message.  A single token
48      * per message would be more straightforward, but this choice lets us avoid
49      * round-off error in refill_bucket()'s calculation of how many tokens to
50      * add to the bucket, since no division step is needed. */
51     long long int last_fill;    /* Time at which we last added tokens. */
52     int tokens;                 /* Current number of tokens. */
53
54     /* Transmission queue. */
55     int n_txq;                  /* No. of packets waiting in rconn for tx. */
56
57     /* Statistics reporting. */
58     unsigned long long n_normal;        /* # txed w/o rate limit queuing. */
59     unsigned long long n_limited;       /* # queued for rate limiting. */
60     unsigned long long n_queue_dropped; /* # dropped due to queue overflow. */
61
62     /* Switch status. */
63     struct status_category *ss_cat;
64 };
65
66 static struct ofpbuf *
67 dequeue_packet(struct pinsched *ps, struct ovs_queue *q,
68                unsigned int port_no)
69 {
70     struct ofpbuf *packet = queue_pop_head(q);
71     if (!q->n) {
72         free(q);
73         port_array_set(&ps->queues, port_no, NULL);
74     }
75     ps->n_queued--;
76     return packet;
77 }
78
79 /* Drop a packet from the longest queue in 'ps'. */
80 static void
81 drop_packet(struct pinsched *ps)
82 {
83     struct ovs_queue *longest;  /* Queue currently selected as longest. */
84     int n_longest;              /* # of queues of same length as 'longest'. */
85     unsigned int longest_port_no;
86     unsigned int port_no;
87     struct ovs_queue *q;
88
89     ps->n_queue_dropped++;
90
91     longest = port_array_first(&ps->queues, &port_no);
92     longest_port_no = port_no;
93     n_longest = 1;
94     while ((q = port_array_next(&ps->queues, &port_no)) != NULL) {
95         if (longest->n < q->n) {
96             longest = q;
97             n_longest = 1;
98         } else if (longest->n == q->n) {
99             n_longest++;
100
101             /* Randomly select one of the longest queues, with a uniform
102              * distribution (Knuth algorithm 3.4.2R). */
103             if (!random_range(n_longest)) {
104                 longest = q;
105                 longest_port_no = port_no;
106             }
107         }
108     }
109
110     /* FIXME: do we want to pop the tail instead? */
111     ofpbuf_delete(dequeue_packet(ps, longest, longest_port_no));
112 }
113
114 /* Remove and return the next packet to transmit (in round-robin order). */
115 static struct ofpbuf *
116 get_tx_packet(struct pinsched *ps)
117 {
118     struct ovs_queue *q = port_array_next(&ps->queues, &ps->last_tx_port);
119     if (!q) {
120         q = port_array_first(&ps->queues, &ps->last_tx_port);
121     }
122     return dequeue_packet(ps, q, ps->last_tx_port);
123 }
124
125 /* Add tokens to the bucket based on elapsed time. */
126 static void
127 refill_bucket(struct pinsched *ps)
128 {
129     long long int now = time_msec();
130     long long int tokens = (now - ps->last_fill) * ps->rate_limit + ps->tokens;
131     if (tokens >= 1000) {
132         ps->last_fill = now;
133         ps->tokens = MIN(tokens, ps->burst_limit * 1000);
134     }
135 }
136
137 /* Attempts to remove enough tokens from 'ps' to transmit a packet.  Returns
138  * true if successful, false otherwise.  (In the latter case no tokens are
139  * removed.) */
140 static bool
141 get_token(struct pinsched *ps)
142 {
143     if (ps->tokens >= 1000) {
144         ps->tokens -= 1000;
145         return true;
146     } else {
147         return false;
148     }
149 }
150
151 void
152 pinsched_send(struct pinsched *ps, uint16_t port_no,
153               struct ofpbuf *packet, pinsched_tx_cb *cb, void *aux)
154 {
155     if (!ps) {
156         cb(packet, aux);
157     } else if (!ps->n_queued && get_token(ps)) {
158         /* In the common case where we are not constrained by the rate limit,
159          * let the packet take the normal path. */
160         ps->n_normal++;
161         cb(packet, aux);
162     } else {
163         /* Otherwise queue it up for the periodic callback to drain out. */
164         struct ovs_queue *q;
165
166         /* We are called with a buffer obtained from dpif_recv() that has much
167          * more allocated space than actual content most of the time.  Since
168          * we're going to store the packet for some time, free up that
169          * otherwise wasted space. */
170         ofpbuf_trim(packet);
171
172         if (ps->n_queued >= ps->burst_limit) {
173             drop_packet(ps);
174         }
175         q = port_array_get(&ps->queues, port_no);
176         if (!q) {
177             q = xmalloc(sizeof *q);
178             queue_init(q);
179             port_array_set(&ps->queues, port_no, q);
180         }
181         queue_push_tail(q, packet);
182         ps->n_queued++;
183         ps->n_limited++;
184     }
185 }
186
187 static void
188 pinsched_status_cb(struct status_reply *sr, void *ps_)
189 {
190     struct pinsched *ps = ps_;
191
192     status_reply_put(sr, "normal=%llu", ps->n_normal);
193     status_reply_put(sr, "limited=%llu", ps->n_limited);
194     status_reply_put(sr, "queue-dropped=%llu", ps->n_queue_dropped);
195 }
196
197 void
198 pinsched_run(struct pinsched *ps, pinsched_tx_cb *cb, void *aux)
199 {
200     if (ps) {
201         int i;
202
203         /* Drain some packets out of the bucket if possible, but limit the
204          * number of iterations to allow other code to get work done too. */
205         refill_bucket(ps);
206         for (i = 0; ps->n_queued && get_token(ps) && i < 50; i++) {
207             cb(get_tx_packet(ps), aux);
208         }
209     }
210 }
211
212 void
213 pinsched_wait(struct pinsched *ps)
214 {
215     if (ps && ps->n_queued) {
216         if (ps->tokens >= 1000) {
217             /* We can transmit more packets as soon as we're called again. */
218             poll_immediate_wake();
219         } else {
220             /* We have to wait for the bucket to re-fill.  We could calculate
221              * the exact amount of time here for increased smoothness. */
222             poll_timer_wait(TIME_UPDATE_INTERVAL / 2);
223         }
224     }
225 }
226
227 /* Creates and returns a scheduler for sending packet-in messages. */
228 struct pinsched *
229 pinsched_create(int rate_limit, int burst_limit, struct switch_status *ss)
230 {
231     struct pinsched *ps;
232
233     ps = xzalloc(sizeof *ps);
234     port_array_init(&ps->queues);
235     ps->n_queued = 0;
236     ps->last_tx_port = PORT_ARRAY_SIZE;
237     ps->last_fill = time_msec();
238     ps->tokens = rate_limit * 100;
239     ps->n_txq = 0;
240     ps->n_normal = 0;
241     ps->n_limited = 0;
242     ps->n_queue_dropped = 0;
243     pinsched_set_limits(ps, rate_limit, burst_limit);
244
245     if (ss) {
246         ps->ss_cat = switch_status_register(ss, "rate-limit",
247                                             pinsched_status_cb, ps);
248     }
249
250     return ps;
251 }
252
253 void
254 pinsched_destroy(struct pinsched *ps)
255 {
256     if (ps) {
257         struct ovs_queue *queue;
258         unsigned int port_no;
259
260         PORT_ARRAY_FOR_EACH (queue, &ps->queues, port_no) {
261             queue_destroy(queue);
262             free(queue);
263         }
264         port_array_destroy(&ps->queues);
265         switch_status_unregister(ps->ss_cat);
266         free(ps);
267     }
268 }
269
270 void
271 pinsched_get_limits(const struct pinsched *ps,
272                     int *rate_limit, int *burst_limit)
273 {
274     *rate_limit = ps->rate_limit;
275     *burst_limit = ps->burst_limit;
276 }
277
278 void
279 pinsched_set_limits(struct pinsched *ps, int rate_limit, int burst_limit)
280 {
281     if (rate_limit <= 0) {
282         rate_limit = 1000;
283     }
284     if (burst_limit <= 0) {
285         burst_limit = rate_limit / 4;
286     }
287     burst_limit = MAX(burst_limit, 1);
288     burst_limit = MIN(burst_limit, INT_MAX / 1000);
289
290     ps->rate_limit = rate_limit;
291     ps->burst_limit = burst_limit;
292     while (ps->n_queued > burst_limit) {
293         drop_packet(ps);
294     }
295 }