]>
Commit | Line | Data |
---|---|---|
9d6ac44e | 1 | /* |
e0edde6f | 2 | * Copyright (c) 2012 Nicira, Inc. |
9d6ac44e BP |
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 | poll_timer_wait_until(g->start + MAX_ELAPSED); | |
97 | } | |
98 | ||
99 | /* Returns true if 'g' has been doing only a minimal amount of work and thus | |
100 | * the client should consider getting rid of it entirely. */ | |
101 | bool | |
102 | governor_is_idle(struct governor *g) | |
103 | { | |
104 | return g->size == MIN_SIZE && time_msec() - g->start > MAX_ELAPSED; | |
105 | } | |
106 | ||
107 | /* Tests whether a flow whose hash is 'hash' and for which 'n' packets have | |
108 | * just arrived should be set up in the datapath or just processed on a | |
109 | * packet-by-packet basis. Returns true to set up a datapath flow, false to | |
110 | * process the packets individually. | |
111 | * | |
112 | * One would expect 'n' to ordinarily be 1, if batching leads multiple packets | |
113 | * to be processed at a time then it could be greater. */ | |
114 | bool | |
115 | governor_should_install_flow(struct governor *g, uint32_t hash, int n) | |
116 | { | |
117 | bool install_flow; | |
118 | uint8_t *e; | |
119 | int count; | |
120 | ||
121 | assert(n > 0); | |
122 | ||
123 | /* Count these packets and begin a new generation if necessary. */ | |
124 | g->n_packets += n; | |
125 | if (g->n_packets >= g->size / 4) { | |
126 | unsigned int new_size; | |
127 | long long elapsed; | |
128 | ||
129 | elapsed = time_msec() - g->start; | |
130 | new_size = (elapsed < MIN_ELAPSED && g->size < MAX_SIZE ? g->size * 2 | |
131 | : elapsed > MAX_ELAPSED && g->size > MIN_SIZE ? g->size / 2 | |
132 | : g->size); | |
133 | governor_new_generation(g, new_size); | |
134 | } | |
135 | ||
136 | /* Do hash table processing. | |
137 | * | |
138 | * Even-numbered hash values use high-order nibbles. | |
139 | * Odd-numbered hash values use low-order nibbles. */ | |
140 | e = &g->table[(hash >> 1) & (g->size - 1)]; | |
141 | count = n + (hash & 1 ? *e >> 4 : *e & 0x0f); | |
142 | if (count >= FLOW_SETUP_THRESHOLD) { | |
143 | install_flow = true; | |
144 | count = 0; | |
145 | } else { | |
146 | install_flow = false; | |
147 | } | |
148 | *e = hash & 1 ? (count << 4) | (*e & 0x0f) : (*e & 0xf0) | count; | |
149 | ||
150 | return install_flow; | |
151 | } | |
152 | \f | |
153 | /* Starts a new generation in 'g' with a table size of 'size' bytes. 'size' | |
154 | * must be a power of two between MIN_SIZE and MAX_SIZE, inclusive. */ | |
155 | static void | |
156 | governor_new_generation(struct governor *g, unsigned int size) | |
157 | { | |
158 | assert(size >= MIN_SIZE && size <= MAX_SIZE); | |
159 | assert(is_pow2(size)); | |
160 | ||
161 | /* Allocate new table, if necessary. */ | |
162 | if (g->size != size) { | |
163 | if (!g->size) { | |
164 | VLOG_INFO("%s: engaging governor with %u kB hash table", | |
165 | g->name, g->size / 1024); | |
166 | } else { | |
167 | VLOG_INFO("%s: processed %u packets in %.2f s, " | |
168 | "%s hash table to %u kB", | |
169 | g->name, g->n_packets, | |
170 | (time_msec() - g->start) / 1000.0, | |
171 | size > g->size ? "enlarging" : "shrinking", | |
172 | size / 1024); | |
173 | } | |
174 | ||
175 | free(g->table); | |
176 | g->table = xmalloc(size * sizeof *g->table); | |
177 | g->size = size; | |
178 | } else { | |
179 | VLOG_DBG("%s: processed %u packets in %.2f s with %u kB hash table", | |
180 | g->name, g->n_packets, (time_msec() - g->start) / 1000.0, | |
181 | size / 1024); | |
182 | } | |
183 | ||
184 | /* Clear data for next generation. */ | |
185 | memset(g->table, 0, size * sizeof *g->table); | |
186 | g->start = time_msec(); | |
187 | g->n_packets = 0; | |
188 | } |