bridge: Run fast when adding and deleting ports.
[openvswitch] / ofproto / pinsched.c
1 /*
2  * Copyright (c) 2008, 2009, 2010, 2011, 2012 Nicira, Inc.
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 "hash.h"
25 #include "hmap.h"
26 #include "ofpbuf.h"
27 #include "openflow/openflow.h"
28 #include "poll-loop.h"
29 #include "random.h"
30 #include "rconn.h"
31 #include "sat-math.h"
32 #include "timeval.h"
33 #include "token-bucket.h"
34 #include "vconn.h"
35
36 struct pinqueue {
37     struct hmap_node node;      /* In struct pinsched's 'queues' hmap. */
38     uint16_t port_no;           /* Port number. */
39     struct list packets;        /* Contains "struct ofpbuf"s. */
40     int n;                      /* Number of packets in 'packets'. */
41 };
42
43 struct pinsched {
44     struct token_bucket token_bucket;
45
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. */
50
51     /* Transmission queue. */
52     int n_txq;                  /* No. of packets waiting in rconn for tx. */
53
54     /* Statistics reporting. */
55     unsigned long long n_normal;        /* # txed w/o rate limit queuing. */
56     unsigned long long n_limited;       /* # queued for rate limiting. */
57     unsigned long long n_queue_dropped; /* # dropped due to queue overflow. */
58 };
59
60 static void
61 advance_txq(struct pinsched *ps)
62 {
63     struct hmap_node *next;
64
65     next = (ps->next_txq
66             ? hmap_next(&ps->queues, &ps->next_txq->node)
67             : hmap_first(&ps->queues));
68     ps->next_txq = next ? CONTAINER_OF(next, struct pinqueue, node) : NULL;
69 }
70
71 static struct ofpbuf *
72 dequeue_packet(struct pinsched *ps, struct pinqueue *q)
73 {
74     struct ofpbuf *packet = ofpbuf_from_list(list_pop_front(&q->packets));
75     q->n--;
76     ps->n_queued--;
77     return packet;
78 }
79
80 static void
81 adjust_limits(int *rate_limit, int *burst_limit)
82 {
83     if (*rate_limit <= 0) {
84         *rate_limit = 1000;
85     }
86     if (*burst_limit <= 0) {
87         *burst_limit = *rate_limit / 4;
88     }
89     if (*burst_limit < 1) {
90         *burst_limit = 1;
91     }
92 }
93
94 /* Destroys 'q' and removes it from 'ps''s set of queues.
95  * (The caller must ensure that 'q' is empty.) */
96 static void
97 pinqueue_destroy(struct pinsched *ps, struct pinqueue *q)
98 {
99     hmap_remove(&ps->queues, &q->node);
100     free(q);
101 }
102
103 static struct pinqueue *
104 pinqueue_get(struct pinsched *ps, uint16_t port_no)
105 {
106     uint32_t hash = hash_int(port_no, 0);
107     struct pinqueue *q;
108
109     HMAP_FOR_EACH_IN_BUCKET (q, node, hash, &ps->queues) {
110         if (port_no == q->port_no) {
111             return q;
112         }
113     }
114
115     q = xmalloc(sizeof *q);
116     hmap_insert(&ps->queues, &q->node, hash);
117     q->port_no = port_no;
118     list_init(&q->packets);
119     q->n = 0;
120     return q;
121 }
122
123 /* Drop a packet from the longest queue in 'ps'. */
124 static void
125 drop_packet(struct pinsched *ps)
126 {
127     struct pinqueue *longest;   /* Queue currently selected as longest. */
128     int n_longest = 0;          /* # of queues of same length as 'longest'. */
129     struct pinqueue *q;
130
131     ps->n_queue_dropped++;
132
133     longest = NULL;
134     HMAP_FOR_EACH (q, node, &ps->queues) {
135         if (!longest || longest->n < q->n) {
136             longest = q;
137             n_longest = 1;
138         } else if (longest->n == q->n) {
139             n_longest++;
140
141             /* Randomly select one of the longest queues, with a uniform
142              * distribution (Knuth algorithm 3.4.2R). */
143             if (!random_range(n_longest)) {
144                 longest = q;
145             }
146         }
147     }
148
149     /* FIXME: do we want to pop the tail instead? */
150     ofpbuf_delete(dequeue_packet(ps, longest));
151     if (longest->n == 0) {
152         pinqueue_destroy(ps, longest);
153     }
154 }
155
156 /* Remove and return the next packet to transmit (in round-robin order). */
157 static struct ofpbuf *
158 get_tx_packet(struct pinsched *ps)
159 {
160     struct ofpbuf *packet;
161     struct pinqueue *q;
162
163     if (!ps->next_txq) {
164         advance_txq(ps);
165     }
166
167     q = ps->next_txq;
168     packet = dequeue_packet(ps, q);
169     advance_txq(ps);
170     if (q->n == 0) {
171         pinqueue_destroy(ps, q);
172     }
173
174     return packet;
175 }
176
177 /* Attempts to remove enough tokens from 'ps' to transmit a packet.  Returns
178  * true if successful, false otherwise.  (In the latter case no tokens are
179  * removed.) */
180 static bool
181 get_token(struct pinsched *ps)
182 {
183     return token_bucket_withdraw(&ps->token_bucket, 1000);
184 }
185
186 void
187 pinsched_send(struct pinsched *ps, uint16_t port_no,
188               struct ofpbuf *packet, pinsched_tx_cb *cb, void *aux)
189 {
190     if (!ps) {
191         cb(packet, aux);
192     } else if (!ps->n_queued && get_token(ps)) {
193         /* In the common case where we are not constrained by the rate limit,
194          * let the packet take the normal path. */
195         ps->n_normal++;
196         cb(packet, aux);
197     } else {
198         /* Otherwise queue it up for the periodic callback to drain out. */
199         struct pinqueue *q;
200
201         /* We might be called with a buffer obtained from dpif_recv() that has
202          * much more allocated space than actual content most of the time.
203          * Since we're going to store the packet for some time, free up that
204          * otherwise wasted space. */
205         ofpbuf_trim(packet);
206
207         if (ps->n_queued * 1000 >= ps->token_bucket.burst) {
208             drop_packet(ps);
209         }
210         q = pinqueue_get(ps, port_no);
211         list_push_back(&q->packets, &packet->list_node);
212         q->n++;
213         ps->n_queued++;
214         ps->n_limited++;
215     }
216 }
217
218 void
219 pinsched_run(struct pinsched *ps, pinsched_tx_cb *cb, void *aux)
220 {
221     if (ps) {
222         int i;
223
224         /* Drain some packets out of the bucket if possible, but limit the
225          * number of iterations to allow other code to get work done too. */
226         for (i = 0; ps->n_queued && get_token(ps) && i < 50; i++) {
227             cb(get_tx_packet(ps), aux);
228         }
229     }
230 }
231
232 void
233 pinsched_wait(struct pinsched *ps)
234 {
235     if (ps && ps->n_queued) {
236         token_bucket_wait(&ps->token_bucket, 1000);
237     }
238 }
239
240 /* Creates and returns a scheduler for sending packet-in messages. */
241 struct pinsched *
242 pinsched_create(int rate_limit, int burst_limit)
243 {
244     struct pinsched *ps;
245
246     ps = xzalloc(sizeof *ps);
247
248     adjust_limits(&rate_limit, &burst_limit);
249     token_bucket_init(&ps->token_bucket,
250                       rate_limit, sat_mul(burst_limit, 1000));
251
252     hmap_init(&ps->queues);
253     ps->n_queued = 0;
254     ps->next_txq = NULL;
255     ps->n_txq = 0;
256     ps->n_normal = 0;
257     ps->n_limited = 0;
258     ps->n_queue_dropped = 0;
259
260     return ps;
261 }
262
263 void
264 pinsched_destroy(struct pinsched *ps)
265 {
266     if (ps) {
267         struct pinqueue *q, *next;
268
269         HMAP_FOR_EACH_SAFE (q, next, node, &ps->queues) {
270             hmap_remove(&ps->queues, &q->node);
271             ofpbuf_list_delete(&q->packets);
272             free(q);
273         }
274         hmap_destroy(&ps->queues);
275         free(ps);
276     }
277 }
278
279 void
280 pinsched_get_limits(const struct pinsched *ps,
281                     int *rate_limit, int *burst_limit)
282 {
283     *rate_limit = ps->token_bucket.rate;
284     *burst_limit = ps->token_bucket.burst / 1000;
285 }
286
287 void
288 pinsched_set_limits(struct pinsched *ps, int rate_limit, int burst_limit)
289 {
290     adjust_limits(&rate_limit, &burst_limit);
291     token_bucket_set(&ps->token_bucket,
292                      rate_limit, sat_mul(burst_limit, 1000));
293     while (ps->n_queued > burst_limit) {
294         drop_packet(ps);
295     }
296 }
297
298 /* Returns the number of packets scheduled to be sent eventually by 'ps'.
299  * Returns 0 if 'ps' is null. */
300 unsigned int
301 pinsched_count_txqlen(const struct pinsched *ps)
302 {
303     return ps ? ps->n_txq : 0;
304 }