pintos-os.org Git - openvswitch/blob - ofproto/ofproto-dpif-governor.c

   1 /*
   2  * Copyright (c) 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
  19 #include "ofproto-dpif-governor.h"
  20
  21 #include <assert.h>
  22 #include <stdlib.h>
  23
  24 #include "coverage.h"
  25 #include "poll-loop.h"
  26 #include "random.h"
  27 #include "timeval.h"
  28 #include "util.h"
  29 #include "valgrind.h"
  30 #include "vlog.h"
  31
  32 VLOG_DEFINE_THIS_MODULE(ofproto_dpif_governor);
  33
  34 /* Minimum number of observed packets before setting up a flow.
  35  *
  36  * This value seems OK empirically. */
  37 #define FLOW_SETUP_THRESHOLD 5
  38 BUILD_ASSERT_DECL(FLOW_SETUP_THRESHOLD > 1);
  39 BUILD_ASSERT_DECL(FLOW_SETUP_THRESHOLD < 16);
  40
  41 /* Minimum and maximum size of a governor, in bytes. */
  42 enum { MIN_SIZE = 16 * 1024 };
  43 enum { MAX_SIZE = 256 * 1024 };
  44 BUILD_ASSERT_DECL(IS_POW2(MIN_SIZE));
  45 BUILD_ASSERT_DECL(IS_POW2(MAX_SIZE));
  46
  47 /* Minimum and maximum time to process the number of packets that make up a
  48  * given generation.  If a generation completes faster than the minimum time,
  49  * we double the table size (but no more than MAX_SIZE).  If a generation take
  50  * more than the maximum time to complete, we halve the table size (but no
  51  * smaller than MIN_SIZE). */
  52 enum { MIN_ELAPSED = 1000 }; /* In milliseconds. */
  53 enum { MAX_ELAPSED = 5000 }; /* In milliseconds. */
  54
  55 static void governor_new_generation(struct governor *, unsigned int size);
  56
  57 /* Creates and returns a new governor named 'name' (which is used only for log
  58  * messages). */
  59 struct governor *
  60 governor_create(const char *name)
  61 {
  62     struct governor *g = xzalloc(sizeof *g);
  63     g->name = xstrdup(name);
  64     governor_new_generation(g, MIN_SIZE);
  65     return g;
  66 }
  67
  68 /* Destroys 'g'. */
  69 void
  70 governor_destroy(struct governor *g)
  71 {
  72     if (g) {
  73         VLOG_INFO("%s: disengaging", g->name);
  74         free(g->table);
  75         free(g);
  76     }
  77 }
  78
  79 /* Performs periodic maintenance work on 'g'. */
  80 void
  81 governor_run(struct governor *g)
  82 {
  83     if (time_msec() - g->start > MAX_ELAPSED) {
  84         if (g->size > MIN_SIZE) {
  85             governor_new_generation(g, g->size / 2);
  86         } else {
  87             /* Don't start a new generation (we'd never go idle). */
  88         }
  89     }
  90 }
  91
  92 /* Arranges for the poll loop to wake up when 'g' needs to do some work. */
  93 void
  94 governor_wait(struct governor *g)
  95 {
  96     if (g->size > MIN_SIZE) {
  97         poll_timer_wait_until(g->start + MAX_ELAPSED);
  98     }
  99 }
 100
 101 /* Returns true if 'g' has been doing only a minimal amount of work and thus
 102  * the client should consider getting rid of it entirely.  */
 103 bool
 104 governor_is_idle(struct governor *g)
 105 {
 106     return g->size == MIN_SIZE && time_msec() - g->start > MAX_ELAPSED;
 107 }
 108
 109 /* Tests whether a flow whose hash is 'hash' and for which 'n' packets have
 110  * just arrived should be set up in the datapath or just processed on a
 111  * packet-by-packet basis.  Returns true to set up a datapath flow, false to
 112  * process the packets individually.
 113  *
 114  * One would expect 'n' to ordinarily be 1, if batching leads multiple packets
 115  * to be processed at a time then it could be greater. */
 116 bool
 117 governor_should_install_flow(struct governor *g, uint32_t hash, int n)
 118 {
 119     bool install_flow;
 120     uint8_t *e;
 121     int count;
 122
 123     assert(n > 0);
 124
 125     /* Count these packets and begin a new generation if necessary. */
 126     g->n_packets += n;
 127     if (g->n_packets >= g->size / 4) {
 128         unsigned int new_size;
 129         long long elapsed;
 130
 131         elapsed = time_msec() - g->start;
 132         new_size = (elapsed < MIN_ELAPSED && g->size < MAX_SIZE ? g->size * 2
 133                     : elapsed > MAX_ELAPSED && g->size > MIN_SIZE ? g->size / 2
 134                     : g->size);
 135         governor_new_generation(g, new_size);
 136     }
 137
 138     /* Do hash table processing.
 139      *
 140      * Even-numbered hash values use high-order nibbles.
 141      * Odd-numbered hash values use low-order nibbles. */
 142     e = &g->table[(hash >> 1) & (g->size - 1)];
 143     count = n + (hash & 1 ? *e >> 4 : *e & 0x0f);
 144     if (count >= FLOW_SETUP_THRESHOLD) {
 145         install_flow = true;
 146         count = 0;
 147     } else {
 148         install_flow = false;
 149     }
 150     *e = hash & 1 ? (count << 4) | (*e & 0x0f) : (*e & 0xf0) | count;
 151
 152     return install_flow;
 153 }
 154 \f
 155 /* Starts a new generation in 'g' with a table size of 'size' bytes.  'size'
 156  * must be a power of two between MIN_SIZE and MAX_SIZE, inclusive. */
 157 static void
 158 governor_new_generation(struct governor *g, unsigned int size)
 159 {
 160     assert(size >= MIN_SIZE && size <= MAX_SIZE);
 161     assert(is_pow2(size));
 162
 163     /* Allocate new table, if necessary. */
 164     if (g->size != size) {
 165         if (!g->size) {
 166             VLOG_INFO("%s: engaging governor with %u kB hash table",
 167                       g->name, size / 1024);
 168         } else {
 169             VLOG_INFO("%s: processed %u packets in %.2f s, "
 170                       "%s hash table to %u kB",
 171                       g->name, g->n_packets,
 172                       (time_msec() - g->start) / 1000.0,
 173                       size > g->size ? "enlarging" : "shrinking",
 174                       size / 1024);
 175         }
 176
 177         free(g->table);
 178         g->table = xmalloc(size * sizeof *g->table);
 179         g->size = size;
 180     } else {
 181         VLOG_DBG("%s: processed %u packets in %.2f s with %u kB hash table",
 182                  g->name, g->n_packets, (time_msec() - g->start) / 1000.0,
 183                  size / 1024);
 184     }
 185
 186     /* Clear data for next generation. */
 187     memset(g->table, 0, size * sizeof *g->table);
 188     g->start = time_msec();
 189     g->n_packets = 0;
 190 }