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