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