2 * Copyright (c) 2012 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include "ofproto-dpif-governor.h"
25 #include "poll-loop.h"
32 VLOG_DEFINE_THIS_MODULE(ofproto_dpif_governor);
34 /* Minimum number of observed packets before setting up a flow.
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);
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));
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. */
55 static void governor_new_generation(struct governor *, unsigned int size);
57 /* Creates and returns a new governor named 'name' (which is used only for log
60 governor_create(const char *name)
62 struct governor *g = xzalloc(sizeof *g);
63 g->name = xstrdup(name);
64 governor_new_generation(g, MIN_SIZE);
70 governor_destroy(struct governor *g)
73 VLOG_INFO("%s: disengaging", g->name);
80 /* Performs periodic maintenance work on 'g'. */
82 governor_run(struct governor *g)
84 if (time_msec() - g->start > MAX_ELAPSED) {
85 if (g->size > MIN_SIZE) {
86 governor_new_generation(g, g->size / 2);
88 /* Don't start a new generation (we'd never go idle). */
93 /* Arranges for the poll loop to wake up when 'g' needs to do some work. */
95 governor_wait(struct governor *g)
97 if (g->size > MIN_SIZE) {
98 poll_timer_wait_until(g->start + MAX_ELAPSED);
102 /* Returns true if 'g' has been doing only a minimal amount of work and thus
103 * the client should consider getting rid of it entirely. */
105 governor_is_idle(struct governor *g)
107 return g->size == MIN_SIZE && time_msec() - g->start > MAX_ELAPSED;
110 /* Tests whether a flow whose hash is 'hash' and for which 'n' packets have
111 * just arrived should be set up in the datapath or just processed on a
112 * packet-by-packet basis. Returns true to set up a datapath flow, false to
113 * process the packets individually.
115 * One would expect 'n' to ordinarily be 1, if batching leads multiple packets
116 * to be processed at a time then it could be greater. */
118 governor_should_install_flow(struct governor *g, uint32_t hash, int n)
120 int old_count, new_count;
126 /* Count these packets and begin a new generation if necessary. */
128 if (g->n_packets >= g->size / 4) {
129 unsigned int new_size;
132 elapsed = time_msec() - g->start;
133 new_size = (elapsed < MIN_ELAPSED && g->size < MAX_SIZE ? g->size * 2
134 : elapsed > MAX_ELAPSED && g->size > MIN_SIZE ? g->size / 2
136 governor_new_generation(g, new_size);
139 /* If we've set up most of the flows we've seen, then we're wasting time
140 * handling most packets one at a time, so in this case instead set up most
141 * flows directly and use the remaining flows as a sample set to adjust our
144 * The definition of "most" is conservative, but the sample size is tuned
145 * based on a few experiments with TCP_CRR mode in netperf. */
146 if (g->n_setups >= g->n_flows - g->n_flows / 16
153 /* Do hash table processing.
155 * Even-numbered hash values use high-order nibbles.
156 * Odd-numbered hash values use low-order nibbles. */
157 e = &g->table[(hash >> 1) & (g->size - 1)];
158 old_count = (hash & 1 ? *e >> 4 : *e & 0x0f);
162 new_count = n + old_count;
163 if (new_count >= FLOW_SETUP_THRESHOLD) {
168 install_flow = false;
170 *e = hash & 1 ? (new_count << 4) | (*e & 0x0f) : (*e & 0xf0) | new_count;
175 /* Starts a new generation in 'g' with a table size of 'size' bytes. 'size'
176 * must be a power of two between MIN_SIZE and MAX_SIZE, inclusive. */
178 governor_new_generation(struct governor *g, unsigned int size)
180 assert(size >= MIN_SIZE && size <= MAX_SIZE);
181 assert(is_pow2(size));
183 /* Allocate new table, if necessary. */
184 if (g->size != size) {
186 VLOG_INFO("%s: engaging governor with %u kB hash table",
187 g->name, size / 1024);
189 VLOG_INFO("%s: processed %u packets in %.2f s, "
190 "%s hash table to %u kB "
191 "(%u hashes, %u setups, %u shortcuts)",
192 g->name, g->n_packets,
193 (time_msec() - g->start) / 1000.0,
194 size > g->size ? "enlarging" : "shrinking",
196 g->n_flows, g->n_setups, g->n_shortcuts);
200 g->table = xmalloc(size * sizeof *g->table);
203 VLOG_DBG("%s: processed %u packets in %.2f s with %u kB hash table "
204 "(%u hashes, %u setups, %u shortcuts)",
205 g->name, g->n_packets, (time_msec() - g->start) / 1000.0,
206 size / 1024, g->n_flows, g->n_setups, g->n_shortcuts);
209 /* Clear data for next generation. */
210 memset(g->table, 0, size * sizeof *g->table);
211 g->start = time_msec();