pintos-os.org Git - openvswitch/blob - 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 }