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