pintos-os.org Git - openvswitch/blob - 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 are called with a buffer obtained from dpif_recv() that has much
 213          * more allocated space than actual content most of the time.  Since
 214          * 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 }