ofproto/pinsched.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010 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 "ofpbuf.h"
  25 #include "openflow/openflow.h"
  26 #include "poll-loop.h"
  27 #include "port-array.h"
  28 #include "random.h"
  29 #include "rconn.h"
  30 #include "status.h"
  31 #include "timeval.h"
  32 #include "vconn.h"
  33
  34 struct pinqueue {
  35     struct list packets;        /* Contains "struct ofpbuf"s. */
  36     int n;                      /* Number of packets in 'packets'. */
  37 };
  38
  39 struct pinsched {
  40     /* Client-supplied parameters. */
  41     int rate_limit;           /* Packets added to bucket per second. */
  42     int burst_limit;          /* Maximum token bucket size, in packets. */
  43
  44     /* One queue per physical port. */
  45     struct port_array queues;   /* Array of "struct pinqueue *"s. */
  46     int n_queued;               /* Sum over queues[*].n. */
  47     unsigned int last_tx_port;  /* Last port checked in round-robin. */
  48
  49     /* Token bucket.
  50      *
  51      * It costs 1000 tokens to send a single packet_in message.  A single token
  52      * per message would be more straightforward, but this choice lets us avoid
  53      * round-off error in refill_bucket()'s calculation of how many tokens to
  54      * add to the bucket, since no division step is needed. */
  55     long long int last_fill;    /* Time at which we last added tokens. */
  56     int tokens;                 /* Current number of tokens. */
  57
  58     /* Transmission queue. */
  59     int n_txq;                  /* No. of packets waiting in rconn for tx. */
  60
  61     /* Statistics reporting. */
  62     unsigned long long n_normal;        /* # txed w/o rate limit queuing. */
  63     unsigned long long n_limited;       /* # queued for rate limiting. */
  64     unsigned long long n_queue_dropped; /* # dropped due to queue overflow. */
  65
  66     /* Switch status. */
  67     struct status_category *ss_cat;
  68 };
  69
  70 static struct ofpbuf *
  71 dequeue_packet(struct pinsched *ps, struct pinqueue *q, unsigned int port_no)
  72 {
  73     struct ofpbuf *packet = ofpbuf_from_list(list_pop_front(&q->packets));
  74     if (--q->n == 0) {
  75         free(q);
  76         port_array_delete(&ps->queues, port_no);
  77     }
  78     ps->n_queued--;
  79     return packet;
  80 }
  81
  82 /* Drop a packet from the longest queue in 'ps'. */
  83 static void
  84 drop_packet(struct pinsched *ps)
  85 {
  86     struct pinqueue *longest;   /* Queue currently selected as longest. */
  87     int n_longest;              /* # of queues of same length as 'longest'. */
  88     unsigned int longest_port_no;
  89     unsigned int port_no;
  90     struct pinqueue *q;
  91
  92     ps->n_queue_dropped++;
  93
  94     longest = port_array_first(&ps->queues, &port_no);
  95     longest_port_no = port_no;
  96     n_longest = 1;
  97     while ((q = port_array_next(&ps->queues, &port_no)) != NULL) {
  98         if (longest->n < q->n) {
  99             longest = q;
 100             n_longest = 1;
 101         } else if (longest->n == q->n) {
 102             n_longest++;
 103
 104             /* Randomly select one of the longest queues, with a uniform
 105              * distribution (Knuth algorithm 3.4.2R). */
 106             if (!random_range(n_longest)) {
 107                 longest = q;
 108                 longest_port_no = port_no;
 109             }
 110         }
 111     }
 112
 113     /* FIXME: do we want to pop the tail instead? */
 114     ofpbuf_delete(dequeue_packet(ps, longest, longest_port_no));
 115 }
 116
 117 /* Remove and return the next packet to transmit (in round-robin order). */
 118 static struct ofpbuf *
 119 get_tx_packet(struct pinsched *ps)
 120 {
 121     struct pinqueue *q = port_array_next(&ps->queues, &ps->last_tx_port);
 122     if (!q) {
 123         q = port_array_first(&ps->queues, &ps->last_tx_port);
 124     }
 125     return dequeue_packet(ps, q, ps->last_tx_port);
 126 }
 127
 128 /* Add tokens to the bucket based on elapsed time. */
 129 static void
 130 refill_bucket(struct pinsched *ps)
 131 {
 132     long long int now = time_msec();
 133     long long int tokens = (now - ps->last_fill) * ps->rate_limit + ps->tokens;
 134     if (tokens >= 1000) {
 135         ps->last_fill = now;
 136         ps->tokens = MIN(tokens, ps->burst_limit * 1000);
 137     }
 138 }
 139
 140 /* Attempts to remove enough tokens from 'ps' to transmit a packet.  Returns
 141  * true if successful, false otherwise.  (In the latter case no tokens are
 142  * removed.) */
 143 static bool
 144 get_token(struct pinsched *ps)
 145 {
 146     if (ps->tokens >= 1000) {
 147         ps->tokens -= 1000;
 148         return true;
 149     } else {
 150         return false;
 151     }
 152 }
 153
 154 void
 155 pinsched_send(struct pinsched *ps, uint16_t port_no,
 156               struct ofpbuf *packet, pinsched_tx_cb *cb, void *aux)
 157 {
 158     if (!ps) {
 159         cb(packet, aux);
 160     } else if (!ps->n_queued && get_token(ps)) {
 161         /* In the common case where we are not constrained by the rate limit,
 162          * let the packet take the normal path. */
 163         ps->n_normal++;
 164         cb(packet, aux);
 165     } else {
 166         /* Otherwise queue it up for the periodic callback to drain out. */
 167         struct pinqueue *q;
 168
 169         /* We are called with a buffer obtained from dpif_recv() that has much
 170          * more allocated space than actual content most of the time.  Since
 171          * we're going to store the packet for some time, free up that
 172          * otherwise wasted space. */
 173         ofpbuf_trim(packet);
 174
 175         if (ps->n_queued >= ps->burst_limit) {
 176             drop_packet(ps);
 177         }
 178         q = port_array_get(&ps->queues, port_no);
 179         if (!q) {
 180             q = xmalloc(sizeof *q);
 181             list_init(&q->packets);
 182             q->n = 0;
 183             port_array_set(&ps->queues, port_no, q);
 184         }
 185         list_push_back(&q->packets, &packet->list_node);
 186         q->n++;
 187         ps->n_queued++;
 188         ps->n_limited++;
 189     }
 190 }
 191
 192 static void
 193 pinsched_status_cb(struct status_reply *sr, void *ps_)
 194 {
 195     struct pinsched *ps = ps_;
 196
 197     status_reply_put(sr, "normal=%llu", ps->n_normal);
 198     status_reply_put(sr, "limited=%llu", ps->n_limited);
 199     status_reply_put(sr, "queue-dropped=%llu", ps->n_queue_dropped);
 200 }
 201
 202 void
 203 pinsched_run(struct pinsched *ps, pinsched_tx_cb *cb, void *aux)
 204 {
 205     if (ps) {
 206         int i;
 207
 208         /* Drain some packets out of the bucket if possible, but limit the
 209          * number of iterations to allow other code to get work done too. */
 210         refill_bucket(ps);
 211         for (i = 0; ps->n_queued && get_token(ps) && i < 50; i++) {
 212             cb(get_tx_packet(ps), aux);
 213         }
 214     }
 215 }
 216
 217 void
 218 pinsched_wait(struct pinsched *ps)
 219 {
 220     if (ps && ps->n_queued) {
 221         if (ps->tokens >= 1000) {
 222             /* We can transmit more packets as soon as we're called again. */
 223             poll_immediate_wake();
 224         } else {
 225             /* We have to wait for the bucket to re-fill.  We could calculate
 226              * the exact amount of time here for increased smoothness. */
 227             poll_timer_wait(TIME_UPDATE_INTERVAL / 2);
 228         }
 229     }
 230 }
 231
 232 /* Creates and returns a scheduler for sending packet-in messages. */
 233 struct pinsched *
 234 pinsched_create(int rate_limit, int burst_limit, struct switch_status *ss)
 235 {
 236     struct pinsched *ps;
 237
 238     ps = xzalloc(sizeof *ps);
 239     port_array_init(&ps->queues);
 240     ps->n_queued = 0;
 241     ps->last_tx_port = PORT_ARRAY_SIZE;
 242     ps->last_fill = time_msec();
 243     ps->tokens = rate_limit * 100;
 244     ps->n_txq = 0;
 245     ps->n_normal = 0;
 246     ps->n_limited = 0;
 247     ps->n_queue_dropped = 0;
 248     pinsched_set_limits(ps, rate_limit, burst_limit);
 249
 250     if (ss) {
 251         ps->ss_cat = switch_status_register(ss, "rate-limit",
 252                                             pinsched_status_cb, ps);
 253     }
 254
 255     return ps;
 256 }
 257
 258 void
 259 pinsched_destroy(struct pinsched *ps)
 260 {
 261     if (ps) {
 262         struct pinqueue *queue;
 263         unsigned int port_no;
 264
 265         PORT_ARRAY_FOR_EACH (queue, &ps->queues, port_no) {
 266             ofpbuf_list_delete(&queue->packets);
 267             free(queue);
 268         }
 269         port_array_destroy(&ps->queues);
 270         switch_status_unregister(ps->ss_cat);
 271         free(ps);
 272     }
 273 }
 274
 275 void
 276 pinsched_get_limits(const struct pinsched *ps,
 277                     int *rate_limit, int *burst_limit)
 278 {
 279     *rate_limit = ps->rate_limit;
 280     *burst_limit = ps->burst_limit;
 281 }
 282
 283 void
 284 pinsched_set_limits(struct pinsched *ps, int rate_limit, int burst_limit)
 285 {
 286     if (rate_limit <= 0) {
 287         rate_limit = 1000;
 288     }
 289     if (burst_limit <= 0) {
 290         burst_limit = rate_limit / 4;
 291     }
 292     burst_limit = MAX(burst_limit, 1);
 293     burst_limit = MIN(burst_limit, INT_MAX / 1000);
 294
 295     ps->rate_limit = rate_limit;
 296     ps->burst_limit = burst_limit;
 297     while (ps->n_queued > burst_limit) {
 298         drop_packet(ps);
 299     }
 300 }