ofproto/pinsched.c

   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 "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 advance_txq(struct pinsched *ps)
  60 {
  61     struct hmap_node *next;
  62
  63     next = (ps->next_txq
  64             ? hmap_next(&ps->queues, &ps->next_txq->node)
  65             : hmap_first(&ps->queues));
  66     ps->next_txq = next ? CONTAINER_OF(next, struct pinqueue, node) : NULL;
  67 }
  68
  69 static struct ofpbuf *
  70 dequeue_packet(struct pinsched *ps, struct pinqueue *q)
  71 {
  72     struct ofpbuf *packet = ofpbuf_from_list(ovs_list_pop_front(&q->packets));
  73     q->n--;
  74     ps->n_queued--;
  75     return packet;
  76 }
  77
  78 static void
  79 adjust_limits(int *rate_limit, int *burst_limit)
  80 {
  81     if (*rate_limit <= 0) {
  82         *rate_limit = 1000;
  83     }
  84     if (*burst_limit <= 0) {
  85         *burst_limit = *rate_limit / 4;
  86     }
  87     if (*burst_limit < 1) {
  88         *burst_limit = 1;
  89     }
  90 }
  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 pinqueue_destroy(struct pinsched *ps, struct pinqueue *q)
  96 {
  97     hmap_remove(&ps->queues, &q->node);
  98     free(q);
  99 }
 100
 101 static struct pinqueue *
 102 pinqueue_get(struct pinsched *ps, ofp_port_t port_no)
 103 {
 104     uint32_t hash = hash_ofp_port(port_no);
 105     struct pinqueue *q;
 106
 107     HMAP_FOR_EACH_IN_BUCKET (q, node, hash, &ps->queues) {
 108         if (port_no == q->port_no) {
 109             return q;
 110         }
 111     }
 112
 113     q = xmalloc(sizeof *q);
 114     hmap_insert(&ps->queues, &q->node, hash);
 115     q->port_no = port_no;
 116     ovs_list_init(&q->packets);
 117     q->n = 0;
 118     return q;
 119 }
 120
 121 /* Drop a packet from the longest queue in 'ps'. */
 122 static void
 123 drop_packet(struct pinsched *ps)
 124 {
 125     struct pinqueue *longest;   /* Queue currently selected as longest. */
 126     int n_longest = 0;          /* # of queues of same length as 'longest'. */
 127     struct pinqueue *q;
 128
 129     ps->n_queue_dropped++;
 130
 131     longest = NULL;
 132     HMAP_FOR_EACH (q, node, &ps->queues) {
 133         if (!longest || longest->n < q->n) {
 134             longest = q;
 135             n_longest = 1;
 136         } else if (longest->n == q->n) {
 137             n_longest++;
 138
 139             /* Randomly select one of the longest queues, with a uniform
 140              * distribution (Knuth algorithm 3.4.2R). */
 141             if (!random_range(n_longest)) {
 142                 longest = q;
 143             }
 144         }
 145     }
 146
 147     /* FIXME: do we want to pop the tail instead? */
 148     ofpbuf_delete(dequeue_packet(ps, longest));
 149     if (longest->n == 0) {
 150         pinqueue_destroy(ps, longest);
 151     }
 152 }
 153
 154 /* Remove and return the next packet to transmit (in round-robin order). */
 155 static struct ofpbuf *
 156 get_tx_packet(struct pinsched *ps)
 157 {
 158     struct ofpbuf *packet;
 159     struct pinqueue *q;
 160
 161     if (!ps->next_txq) {
 162         advance_txq(ps);
 163     }
 164
 165     q = ps->next_txq;
 166     packet = dequeue_packet(ps, q);
 167     advance_txq(ps);
 168     if (q->n == 0) {
 169         pinqueue_destroy(ps, q);
 170     }
 171
 172     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 get_token(struct pinsched *ps)
 180 {
 181     return token_bucket_withdraw(&ps->token_bucket, 1000);
 182 }
 183
 184 void
 185 pinsched_send(struct pinsched *ps, ofp_port_t port_no,
 186               struct ofpbuf *packet, struct ovs_list *txq)
 187 {
 188     ovs_list_init(txq);
 189     if (!ps) {
 190         ovs_list_push_back(txq, &packet->list_node);
 191     } 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         ps->n_normal++;
 195         ovs_list_push_back(txq, &packet->list_node);
 196     } else {
 197         /* Otherwise queue it up for the periodic callback to drain out. */
 198         if (ps->n_queued * 1000 >= ps->token_bucket.burst) {
 199             drop_packet(ps);
 200         }
 201
 202         struct pinqueue *q = pinqueue_get(ps, port_no);
 203         ovs_list_push_back(&q->packets, &packet->list_node);
 204         q->n++;
 205         ps->n_queued++;
 206         ps->n_limited++;
 207     }
 208 }
 209
 210 void
 211 pinsched_run(struct pinsched *ps, struct ovs_list *txq)
 212 {
 213     ovs_list_init(txq);
 214     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         for (i = 0; ps->n_queued && get_token(ps) && i < 50; i++) {
 220             struct ofpbuf *packet = get_tx_packet(ps);
 221             ovs_list_push_back(txq, &packet->list_node);
 222         }
 223     }
 224 }
 225
 226 void
 227 pinsched_wait(struct pinsched *ps)
 228 {
 229     if (ps && ps->n_queued) {
 230         token_bucket_wait(&ps->token_bucket, 1000);
 231     }
 232 }
 233
 234 /* Creates and returns a scheduler for sending packet-in messages. */
 235 struct pinsched *
 236 pinsched_create(int rate_limit, int burst_limit)
 237 {
 238     struct pinsched *ps;
 239
 240     ps = xzalloc(sizeof *ps);
 241
 242     adjust_limits(&rate_limit, &burst_limit);
 243     token_bucket_init(&ps->token_bucket,
 244                       rate_limit, sat_mul(burst_limit, 1000));
 245
 246     hmap_init(&ps->queues);
 247     ps->n_queued = 0;
 248     ps->next_txq = NULL;
 249     ps->n_normal = 0;
 250     ps->n_limited = 0;
 251     ps->n_queue_dropped = 0;
 252
 253     return ps;
 254 }
 255
 256 void
 257 pinsched_destroy(struct pinsched *ps)
 258 {
 259     if (ps) {
 260         struct pinqueue *q;
 261
 262         HMAP_FOR_EACH_POP (q, node, &ps->queues) {
 263             ofpbuf_list_delete(&q->packets);
 264             free(q);
 265         }
 266         hmap_destroy(&ps->queues);
 267         free(ps);
 268     }
 269 }
 270
 271 void
 272 pinsched_get_limits(const struct pinsched *ps,
 273                     int *rate_limit, int *burst_limit)
 274 {
 275     *rate_limit = ps->token_bucket.rate;
 276     *burst_limit = ps->token_bucket.burst / 1000;
 277 }
 278
 279 void
 280 pinsched_set_limits(struct pinsched *ps, int rate_limit, int burst_limit)
 281 {
 282     adjust_limits(&rate_limit, &burst_limit);
 283     token_bucket_set(&ps->token_bucket,
 284                      rate_limit, sat_mul(burst_limit, 1000));
 285     while (ps->n_queued > burst_limit) {
 286         drop_packet(ps);
 287     }
 288 }
 289
 290 /* Retrieves statistics for 'ps'.  The statistics will be all zero if 'ps' is
 291  * null. */
 292 void
 293 pinsched_get_stats(const struct pinsched *ps, struct pinsched_stats *stats)
 294 {
 295     if (ps) {
 296         stats->n_queued = ps->n_queued;
 297         stats->n_normal = ps->n_normal;
 298         stats->n_limited = ps->n_limited;
 299         stats->n_queue_dropped = ps->n_queue_dropped;
 300     } else {
 301         memset(stats, 0, sizeof *stats);
 302     }
 303 }