Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2014, 2015, 2016 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 "openvswitch/ofpbuf.h"
20 : : #include "ofproto-dpif.h"
21 : : #include "ofproto-dpif-rid.h"
22 : : #include "ofproto-provider.h"
23 : : #include "openvswitch/vlog.h"
24 : :
25 : 1288 : VLOG_DEFINE_THIS_MODULE(ofproto_dpif_rid);
26 : :
27 : : static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER;
28 : :
29 : : static struct cmap id_map = CMAP_INITIALIZER;
30 : : static struct cmap metadata_map = CMAP_INITIALIZER;
31 : :
32 : : static struct ovs_list expiring OVS_GUARDED_BY(mutex)
33 : : = OVS_LIST_INITIALIZER(&expiring);
34 : : static struct ovs_list expired OVS_GUARDED_BY(mutex)
35 : : = OVS_LIST_INITIALIZER(&expired);
36 : :
37 : : static uint32_t next_id OVS_GUARDED_BY(mutex) = 1; /* Possible next free id. */
38 : :
39 : : #define RECIRC_POOL_STATIC_IDS 1024
40 : :
41 : : static void recirc_id_node_free(struct recirc_id_node *);
42 : :
43 : : /* This should be called by the revalidator once at each round (every 500ms or
44 : : * more). */
45 : : void
46 : 30430 : recirc_run(void)
47 : : {
48 : : static long long int last = 0;
49 : 30430 : long long int now = time_msec();
50 : :
51 : : /* Do maintenance at most 4 times / sec. */
52 : 30430 : ovs_mutex_lock(&mutex);
53 [ + + ]: 30430 : if (now - last > 250) {
54 : : struct recirc_id_node *node;
55 : :
56 : 8508 : last = now;
57 : :
58 : : /* Nodes in 'expiring' and 'expired' lists have the refcount of zero,
59 : : * which means that while they can still be found (by id), no new
60 : : * references can be taken on them. We have removed the entry from the
61 : : * 'metadata_map', at the time when refcount reached zero, causing any
62 : : * new translations to allocate a new ID. This allows the expiring
63 : : * entry to be safely deleted while any sudden new use of the similar
64 : : * recirculation will safely start using a new recirculation ID. When
65 : : * the refcount gets to zero, the node is also added to the 'expiring'
66 : : * list. At any time after that the nodes in the 'expiring' list can
67 : : * be moved to the 'expired' list, from which they are deleted at least
68 : : * 250ms afterwards. */
69 : :
70 : : /* Delete the expired. These have been lingering for at least 250 ms,
71 : : * which should be enough for any ongoing recirculations to be
72 : : * finished. */
73 [ + + ]: 8550 : LIST_FOR_EACH_POP (node, exp_node, &expired) {
74 : 42 : cmap_remove(&id_map, &node->id_node, node->id);
75 : 42 : ovsrcu_postpone(recirc_id_node_free, node);
76 : : }
77 : :
78 [ + + ]: 8508 : if (!ovs_list_is_empty(&expiring)) {
79 : : /* 'expired' is now empty, move nodes in 'expiring' to it. */
80 : 39 : ovs_list_splice(&expired, ovs_list_front(&expiring), &expiring);
81 : : }
82 : : }
83 : 30430 : ovs_mutex_unlock(&mutex);
84 : 30430 : }
85 : :
86 : : /* We use the id as the hash value, which works due to cmap internal rehashing.
87 : : * We also only insert nodes with unique IDs, so all possible hash collisions
88 : : * remain internal to the cmap. */
89 : : static struct recirc_id_node *
90 : 254 : recirc_find__(uint32_t id)
91 : : OVS_REQUIRES(mutex)
92 : : {
93 : 254 : struct cmap_node *node = cmap_find_protected(&id_map, id);
94 : :
95 [ - + ]: 254 : return node ? CONTAINER_OF(node, struct recirc_id_node, id_node) : NULL;
96 : : }
97 : :
98 : : /* Lockless RCU protected lookup. If node is needed accross RCU quiescent
99 : : * state, caller should copy the contents. */
100 : : const struct recirc_id_node *
101 : 3024 : recirc_id_node_find(uint32_t id)
102 : : {
103 : 3024 : const struct cmap_node *node = cmap_find(&id_map, id);
104 : :
105 : 3024 : return node
106 : : ? CONTAINER_OF(node, const struct recirc_id_node, id_node)
107 [ + - ]: 3024 : : NULL;
108 : : }
109 : :
110 : : static uint32_t
111 : 959 : frozen_state_hash(const struct frozen_state *state)
112 : : {
113 : : uint32_t hash;
114 : :
115 : 959 : hash = uuid_hash(&state->ofproto_uuid);
116 : 959 : hash = hash_int(state->table_id, hash);
117 [ - + ]: 959 : if (flow_tnl_dst_is_set(state->metadata.tunnel)) {
118 : : /* We may leave remainder bytes unhashed, but that is unlikely as
119 : : * the tunnel is not in the datapath format. */
120 : 0 : hash = hash_bytes64((const uint64_t *) state->metadata.tunnel,
121 : : flow_tnl_size(state->metadata.tunnel), hash);
122 : : }
123 : 959 : hash = hash_boolean(state->conntracked, hash);
124 : 959 : hash = hash_bytes64((const uint64_t *) &state->metadata.metadata,
125 : : sizeof state->metadata - sizeof state->metadata.tunnel,
126 : : hash);
127 [ + + ][ + + ]: 959 : if (state->stack && state->n_stack) {
128 : 1 : hash = hash_bytes64((const uint64_t *) state->stack,
129 : 1 : state->n_stack * sizeof *state->stack, hash);
130 : : }
131 : 959 : hash = hash_int(state->mirrors, hash);
132 : 959 : hash = hash_int(state->action_set_len, hash);
133 [ - + ]: 959 : if (state->action_set_len) {
134 : 0 : hash = hash_bytes64(ALIGNED_CAST(const uint64_t *, state->action_set),
135 : : state->action_set_len, hash);
136 : : }
137 [ + + ]: 959 : if (state->ofpacts_len) {
138 : 43 : hash = hash_bytes64(ALIGNED_CAST(const uint64_t *, state->ofpacts),
139 : : state->ofpacts_len, hash);
140 : : }
141 : 959 : return hash;
142 : : }
143 : :
144 : : static bool
145 : 705 : frozen_state_equal(const struct frozen_state *a, const struct frozen_state *b)
146 : : {
147 : 705 : return (a->table_id == b->table_id
148 [ + - ]: 705 : && uuid_equals(&a->ofproto_uuid, &b->ofproto_uuid)
149 [ + - ]: 705 : && flow_tnl_equal(a->metadata.tunnel, b->metadata.tunnel)
150 [ + - ]: 705 : && !memcmp(&a->metadata.metadata, &b->metadata.metadata,
151 : : sizeof a->metadata - sizeof a->metadata.tunnel)
152 [ + - ]: 705 : && a->n_stack == b->n_stack
153 [ + - ]: 705 : && !memcmp(a->stack, b->stack, a->n_stack * sizeof *a->stack)
154 [ + - ]: 705 : && a->mirrors == b->mirrors
155 [ + - ]: 705 : && a->conntracked == b->conntracked
156 [ + - ]: 705 : && ofpacts_equal(a->ofpacts, a->ofpacts_len,
157 : 705 : b->ofpacts, b->ofpacts_len)
158 [ + - ][ + - ]: 1410 : && ofpacts_equal(a->action_set, a->action_set_len,
159 : 705 : b->action_set, b->action_set_len));
160 : : }
161 : :
162 : : /* Lockless RCU protected lookup. If node is needed accross RCU quiescent
163 : : * state, caller should take a reference. */
164 : : static struct recirc_id_node *
165 : 947 : recirc_find_equal(const struct frozen_state *target, uint32_t hash)
166 : : {
167 : : struct recirc_id_node *node;
168 : :
169 [ + + ]: 947 : CMAP_FOR_EACH_WITH_HASH (node, metadata_node, hash, &metadata_map) {
170 [ + - ]: 705 : if (frozen_state_equal(&node->state, target)) {
171 : 705 : return node;
172 : : }
173 : : }
174 : 242 : return NULL;
175 : : }
176 : :
177 : : static struct recirc_id_node *
178 : 947 : recirc_ref_equal(const struct frozen_state *target, uint32_t hash)
179 : : {
180 : : struct recirc_id_node *node;
181 : :
182 : : do {
183 : 947 : node = recirc_find_equal(target, hash);
184 : :
185 : : /* Try again if the node was released before we get the reference. */
186 [ + + ][ - + ]: 947 : } while (node && !ovs_refcount_try_ref_rcu(&node->refcount));
187 : :
188 : 947 : return node;
189 : : }
190 : :
191 : : static void
192 : 254 : frozen_state_clone(struct frozen_state *new, const struct frozen_state *old,
193 : : struct flow_tnl *tunnel)
194 : : {
195 : 254 : *new = *old;
196 : 254 : flow_tnl_copy__(tunnel, old->metadata.tunnel);
197 : 254 : new->metadata.tunnel = tunnel;
198 : :
199 : 508 : new->stack = (new->n_stack
200 : 1 : ? xmemdup(new->stack, new->n_stack * sizeof *new->stack)
201 [ + + ]: 254 : : NULL);
202 : 508 : new->ofpacts = (new->ofpacts_len
203 : 24 : ? xmemdup(new->ofpacts, new->ofpacts_len)
204 [ + + ]: 254 : : NULL);
205 : 508 : new->action_set = (new->action_set_len
206 : 0 : ? xmemdup(new->action_set, new->action_set_len)
207 [ - + ]: 254 : : NULL);
208 : 254 : }
209 : :
210 : : static void
211 : 42 : frozen_state_free(struct frozen_state *state)
212 : : {
213 : 42 : free(state->stack);
214 : 42 : free(state->ofpacts);
215 : 42 : free(state->action_set);
216 : 42 : }
217 : :
218 : : /* Allocate a unique recirculation id for the given set of flow metadata.
219 : : * The ID space is 2^^32, so there should never be a situation in which all
220 : : * the IDs are used up. We loop until we find a free one.
221 : : * hash is recomputed if it is passed in as 0. */
222 : : static struct recirc_id_node *
223 : 254 : recirc_alloc_id__(const struct frozen_state *state, uint32_t hash)
224 : : {
225 [ - + ]: 254 : ovs_assert(state->action_set_len <= state->ofpacts_len);
226 : :
227 : 254 : struct recirc_id_node *node = xzalloc(sizeof *node);
228 : :
229 : 254 : node->hash = hash;
230 : 254 : ovs_refcount_init(&node->refcount);
231 : 254 : frozen_state_clone(CONST_CAST(struct frozen_state *, &node->state), state,
232 : : &node->state_metadata_tunnel);
233 : :
234 : 254 : ovs_mutex_lock(&mutex);
235 : : for (;;) {
236 : : /* Claim the next ID. The ID space should be sparse enough for the
237 : : allocation to succeed at the first try. We do skip the first
238 : : RECIRC_POOL_STATIC_IDS IDs on the later rounds, though, as some of
239 : : the initial allocations may be for long term uses (like bonds). */
240 : 254 : node->id = next_id++;
241 [ - + ]: 254 : if (OVS_UNLIKELY(!node->id)) {
242 : 0 : next_id = RECIRC_POOL_STATIC_IDS + 1;
243 : 0 : node->id = next_id++;
244 : : }
245 : : /* Find if the id is free. */
246 [ + - ]: 254 : if (OVS_LIKELY(!recirc_find__(node->id))) {
247 : 254 : break;
248 : : }
249 : 0 : }
250 : 254 : cmap_insert(&id_map, &node->id_node, node->id);
251 : 254 : cmap_insert(&metadata_map, &node->metadata_node, node->hash);
252 : 254 : ovs_mutex_unlock(&mutex);
253 : 254 : return node;
254 : : }
255 : :
256 : : /* Look up an existing ID for the given flow's metadata and optional actions.
257 : : */
258 : : uint32_t
259 : 0 : recirc_find_id(const struct frozen_state *target)
260 : : {
261 : 0 : uint32_t hash = frozen_state_hash(target);
262 : 0 : struct recirc_id_node *node = recirc_find_equal(target, hash);
263 [ # # ]: 0 : return node ? node->id : 0;
264 : : }
265 : :
266 : : /* Allocate a unique recirculation id for the given set of flow metadata and
267 : : optional actions. */
268 : : uint32_t
269 : 947 : recirc_alloc_id_ctx(const struct frozen_state *state)
270 : : {
271 : 947 : uint32_t hash = frozen_state_hash(state);
272 : 947 : struct recirc_id_node *node = recirc_ref_equal(state, hash);
273 [ + + ]: 947 : if (!node) {
274 : 242 : node = recirc_alloc_id__(state, hash);
275 : : }
276 : 947 : return node->id;
277 : : }
278 : :
279 : : /* Allocate a unique recirculation id. */
280 : : uint32_t
281 : 12 : recirc_alloc_id(struct ofproto_dpif *ofproto)
282 : : {
283 : : struct flow_tnl tunnel;
284 : 12 : tunnel.ip_dst = htonl(0);
285 : 12 : tunnel.ipv6_dst = in6addr_any;
286 : 24 : struct frozen_state state = {
287 : : .table_id = TBL_INTERNAL,
288 : 12 : .ofproto_uuid = *ofproto_dpif_get_uuid(ofproto),
289 : : .metadata = { .tunnel = &tunnel, .in_port = OFPP_NONE },
290 : : };
291 : 12 : return recirc_alloc_id__(&state, frozen_state_hash(&state))->id;
292 : : }
293 : :
294 : : static void
295 : 42 : recirc_id_node_free(struct recirc_id_node *node)
296 : : {
297 : 42 : frozen_state_free(CONST_CAST(struct frozen_state *, &node->state));
298 : 42 : free(node);
299 : 42 : }
300 : :
301 : : void
302 : 1720 : recirc_id_node_unref(const struct recirc_id_node *node_)
303 : : OVS_EXCLUDED(mutex)
304 : : {
305 : 1720 : struct recirc_id_node *node = CONST_CAST(struct recirc_id_node *, node_);
306 : :
307 [ + - ][ + + ]: 1720 : if (node && ovs_refcount_unref(&node->refcount) == 1) {
308 : 251 : ovs_mutex_lock(&mutex);
309 : : /* Prevent re-use of this node by removing the node from 'metadata_map'
310 : : */
311 : 251 : cmap_remove(&metadata_map, &node->metadata_node, node->hash);
312 : : /* We keep the node in the 'id_map' so that it can be found as long
313 : : * as it lingers, and add it to the 'expiring' list. */
314 : 251 : ovs_list_insert(&expiring, &node->exp_node);
315 : 251 : ovs_mutex_unlock(&mutex);
316 : : }
317 : 1720 : }
318 : :
319 : : void
320 : 1720 : recirc_free_id(uint32_t id)
321 : : {
322 : : const struct recirc_id_node *node;
323 : :
324 : 1720 : node = recirc_id_node_find(id);
325 [ + - ]: 1720 : if (node) {
326 : 1720 : recirc_id_node_unref(node);
327 : : } else {
328 [ # # ]: 0 : VLOG_ERR("Freeing nonexistent recirculation ID: %"PRIu32, id);
329 : : }
330 : 1720 : }
331 : :
332 : : /* Called when 'ofproto' is destructed. Checks for and clears any
333 : : * recirc_id leak.
334 : : * No other thread may have access to the 'ofproto' being destructed.
335 : : * All related datapath flows must be deleted before calling this. */
336 : : void
337 : 749 : recirc_free_ofproto(struct ofproto_dpif *ofproto, const char *ofproto_name)
338 : : {
339 : : struct recirc_id_node *n;
340 : :
341 : 749 : const struct uuid *ofproto_uuid = ofproto_dpif_get_uuid(ofproto);
342 [ + + ][ + + ]: 766 : CMAP_FOR_EACH (n, metadata_node, &metadata_map) {
343 [ + + ]: 17 : if (uuid_equals(&n->state.ofproto_uuid, ofproto_uuid)) {
344 [ + - ]: 10 : VLOG_ERR("recirc_id %"PRIu32
345 : : " left allocated when ofproto (%s)"
346 : : " is destructed", n->id, ofproto_name);
347 : : }
348 : : }
349 : 749 : }
|
