ofproto: Rename "private.h" to "ofproto->provider.h".
[openvswitch] / ofproto / pinsched.c
1 /*
2  * Copyright (c) 2008, 2009, 2010, 2011 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 "hmap.h"
25 #include "ofpbuf.h"
26 #include "openflow/openflow.h"
27 #include "poll-loop.h"
28 #include "random.h"
29 #include "rconn.h"
30 #include "timeval.h"
31 #include "vconn.h"
32
33 struct pinqueue {
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'. */
38 };
39
40 struct pinsched {
41     /* Client-supplied parameters. */
42     int rate_limit;           /* Packets added to bucket per second. */
43     int burst_limit;          /* Maximum token bucket size, in packets. */
44
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. */
49
50     /* Token bucket.
51      *
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. */
58
59     /* Transmission queue. */
60     int n_txq;                  /* No. of packets waiting in rconn for tx. */
61
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. */
66 };
67
68 static void
69 advance_txq(struct pinsched *ps)
70 {
71     struct hmap_node *next;
72
73     next = (ps->next_txq
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;
77 }
78
79 static struct ofpbuf *
80 dequeue_packet(struct pinsched *ps, struct pinqueue *q)
81 {
82     struct ofpbuf *packet = ofpbuf_from_list(list_pop_front(&q->packets));
83     q->n--;
84     ps->n_queued--;
85     return packet;
86 }
87
88 /* Destroys 'q' and removes it from 'ps''s set of queues.
89  * (The caller must ensure that 'q' is empty.) */
90 static void
91 pinqueue_destroy(struct pinsched *ps, struct pinqueue *q)
92 {
93     hmap_remove(&ps->queues, &q->node);
94     free(q);
95 }
96
97 static struct pinqueue *
98 pinqueue_get(struct pinsched *ps, uint16_t port_no)
99 {
100     uint32_t hash = hash_int(port_no, 0);
101     struct pinqueue *q;
102
103     HMAP_FOR_EACH_IN_BUCKET (q, node, hash, &ps->queues) {
104         if (port_no == q->port_no) {
105             return q;
106         }
107     }
108
109     q = xmalloc(sizeof *q);
110     hmap_insert(&ps->queues, &q->node, hash);
111     q->port_no = port_no;
112     list_init(&q->packets);
113     q->n = 0;
114     return q;
115 }
116
117 /* Drop a packet from the longest queue in 'ps'. */
118 static void
119 drop_packet(struct pinsched *ps)
120 {
121     struct pinqueue *longest;   /* Queue currently selected as longest. */
122     int n_longest = 0;          /* # of queues of same length as 'longest'. */
123     struct pinqueue *q;
124
125     ps->n_queue_dropped++;
126
127     longest = NULL;
128     HMAP_FOR_EACH (q, node, &ps->queues) {
129         if (!longest || longest->n < q->n) {
130             longest = q;
131             n_longest = 1;
132         } else if (longest->n == q->n) {
133             n_longest++;
134
135             /* Randomly select one of the longest queues, with a uniform
136              * distribution (Knuth algorithm 3.4.2R). */
137             if (!random_range(n_longest)) {
138                 longest = q;
139             }
140         }
141     }
142
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);
147     }
148 }
149
150 /* Remove and return the next packet to transmit (in round-robin order). */
151 static struct ofpbuf *
152 get_tx_packet(struct pinsched *ps)
153 {
154     struct ofpbuf *packet;
155     struct pinqueue *q;
156
157     if (!ps->next_txq) {
158         advance_txq(ps);
159     }
160
161     q = ps->next_txq;
162     packet = dequeue_packet(ps, q);
163     advance_txq(ps);
164     if (q->n == 0) {
165         pinqueue_destroy(ps, q);
166     }
167
168     return packet;
169 }
170
171 /* Add tokens to the bucket based on elapsed time. */
172 static void
173 refill_bucket(struct pinsched *ps)
174 {
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) {
178         ps->last_fill = now;
179         ps->tokens = MIN(tokens, ps->burst_limit * 1000);
180     }
181 }
182
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
185  * removed.) */
186 static bool
187 get_token(struct pinsched *ps)
188 {
189     if (ps->tokens >= 1000) {
190         ps->tokens -= 1000;
191         return true;
192     } else {
193         return false;
194     }
195 }
196
197 void
198 pinsched_send(struct pinsched *ps, uint16_t port_no,
199               struct ofpbuf *packet, pinsched_tx_cb *cb, void *aux)
200 {
201     if (!ps) {
202         cb(packet, 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. */
206         ps->n_normal++;
207         cb(packet, aux);
208     } else {
209         /* Otherwise queue it up for the periodic callback to drain out. */
210         struct pinqueue *q;
211
212         /* We might be called with a buffer obtained from dpif_recv() that has
213          * much more allocated space than actual content most of the time.
214          * Since we're going to store the packet for some time, free up that
215          * otherwise wasted space. */
216         ofpbuf_trim(packet);
217
218         if (ps->n_queued >= ps->burst_limit) {
219             drop_packet(ps);
220         }
221         q = pinqueue_get(ps, port_no);
222         list_push_back(&q->packets, &packet->list_node);
223         q->n++;
224         ps->n_queued++;
225         ps->n_limited++;
226     }
227 }
228
229 void
230 pinsched_run(struct pinsched *ps, pinsched_tx_cb *cb, void *aux)
231 {
232     if (ps) {
233         int i;
234
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. */
237         refill_bucket(ps);
238         for (i = 0; ps->n_queued && get_token(ps) && i < 50; i++) {
239             cb(get_tx_packet(ps), aux);
240         }
241     }
242 }
243
244 void
245 pinsched_wait(struct pinsched *ps)
246 {
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();
251         } else {
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);
255         }
256     }
257 }
258
259 /* Creates and returns a scheduler for sending packet-in messages. */
260 struct pinsched *
261 pinsched_create(int rate_limit, int burst_limit)
262 {
263     struct pinsched *ps;
264
265     ps = xzalloc(sizeof *ps);
266     hmap_init(&ps->queues);
267     ps->n_queued = 0;
268     ps->next_txq = NULL;
269     ps->last_fill = time_msec();
270     ps->tokens = rate_limit * 100;
271     ps->n_txq = 0;
272     ps->n_normal = 0;
273     ps->n_limited = 0;
274     ps->n_queue_dropped = 0;
275     pinsched_set_limits(ps, rate_limit, burst_limit);
276
277     return ps;
278 }
279
280 void
281 pinsched_destroy(struct pinsched *ps)
282 {
283     if (ps) {
284         struct pinqueue *q, *next;
285
286         HMAP_FOR_EACH_SAFE (q, next, node, &ps->queues) {
287             hmap_remove(&ps->queues, &q->node);
288             ofpbuf_list_delete(&q->packets);
289             free(q);
290         }
291         hmap_destroy(&ps->queues);
292         free(ps);
293     }
294 }
295
296 void
297 pinsched_get_limits(const struct pinsched *ps,
298                     int *rate_limit, int *burst_limit)
299 {
300     *rate_limit = ps->rate_limit;
301     *burst_limit = ps->burst_limit;
302 }
303
304 void
305 pinsched_set_limits(struct pinsched *ps, int rate_limit, int burst_limit)
306 {
307     if (rate_limit <= 0) {
308         rate_limit = 1000;
309     }
310     if (burst_limit <= 0) {
311         burst_limit = rate_limit / 4;
312     }
313     burst_limit = MAX(burst_limit, 1);
314     burst_limit = MIN(burst_limit, INT_MAX / 1000);
315
316     ps->rate_limit = rate_limit;
317     ps->burst_limit = burst_limit;
318     while (ps->n_queued > burst_limit) {
319         drop_packet(ps);
320     }
321 }