2 * Copyright (c) 2014, 2015, 2016 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 "openvswitch/ofpbuf.h"
20 #include "ofproto-dpif.h"
21 #include "ofproto-dpif-rid.h"
22 #include "ofproto-provider.h"
23 #include "openvswitch/vlog.h"
25 VLOG_DEFINE_THIS_MODULE(ofproto_dpif_rid);
27 static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER;
29 static struct cmap id_map = CMAP_INITIALIZER;
30 static struct cmap metadata_map = CMAP_INITIALIZER;
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);
37 static uint32_t next_id OVS_GUARDED_BY(mutex) = 1; /* Possible next free id. */
39 #define RECIRC_POOL_STATIC_IDS 1024
41 static void recirc_id_node_free(struct recirc_id_node *);
43 /* This should be called by the revalidator once at each round (every 500ms or
48 static long long int last = 0;
49 long long int now = time_msec();
51 /* Do maintenance at most 4 times / sec. */
52 ovs_mutex_lock(&mutex);
53 if (now - last > 250) {
54 struct recirc_id_node *node;
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. */
70 /* Delete the expired. These have been lingering for at least 250 ms,
71 * which should be enough for any ongoing recirculations to be
73 LIST_FOR_EACH_POP (node, exp_node, &expired) {
74 cmap_remove(&id_map, &node->id_node, node->id);
75 ovsrcu_postpone(recirc_id_node_free, node);
78 if (!ovs_list_is_empty(&expiring)) {
79 /* 'expired' is now empty, move nodes in 'expiring' to it. */
80 ovs_list_splice(&expired, ovs_list_front(&expiring), &expiring);
83 ovs_mutex_unlock(&mutex);
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 recirc_find__(uint32_t id)
93 struct cmap_node *node = cmap_find_protected(&id_map, id);
95 return node ? CONTAINER_OF(node, struct recirc_id_node, id_node) : NULL;
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 recirc_id_node_find(uint32_t id)
103 const struct cmap_node *node = cmap_find(&id_map, id);
106 ? CONTAINER_OF(node, const struct recirc_id_node, id_node)
111 frozen_state_hash(const struct frozen_state *state)
115 hash = uuid_hash(&state->ofproto_uuid);
116 hash = hash_int(state->table_id, hash);
117 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 hash = hash_bytes64((const uint64_t *) state->metadata.tunnel,
121 flow_tnl_size(state->metadata.tunnel), hash);
123 hash = hash_boolean(state->conntracked, hash);
124 hash = hash_bytes64((const uint64_t *) &state->metadata.metadata,
125 sizeof state->metadata - sizeof state->metadata.tunnel,
127 if (state->stack && state->n_stack) {
128 hash = hash_bytes64((const uint64_t *) state->stack,
129 state->n_stack * sizeof *state->stack, hash);
131 hash = hash_int(state->mirrors, hash);
132 hash = hash_int(state->action_set_len, hash);
133 if (state->action_set_len) {
134 hash = hash_bytes64(ALIGNED_CAST(const uint64_t *, state->action_set),
135 state->action_set_len, hash);
137 if (state->ofpacts_len) {
138 hash = hash_bytes64(ALIGNED_CAST(const uint64_t *, state->ofpacts),
139 state->ofpacts_len, hash);
145 frozen_state_equal(const struct frozen_state *a, const struct frozen_state *b)
147 return (a->table_id == b->table_id
148 && uuid_equals(&a->ofproto_uuid, &b->ofproto_uuid)
149 && flow_tnl_equal(a->metadata.tunnel, b->metadata.tunnel)
150 && !memcmp(&a->metadata.metadata, &b->metadata.metadata,
151 sizeof a->metadata - sizeof a->metadata.tunnel)
152 && a->n_stack == b->n_stack
153 && !memcmp(a->stack, b->stack, a->n_stack * sizeof *a->stack)
154 && a->mirrors == b->mirrors
155 && a->conntracked == b->conntracked
156 && ofpacts_equal(a->ofpacts, a->ofpacts_len,
157 b->ofpacts, b->ofpacts_len)
158 && ofpacts_equal(a->action_set, a->action_set_len,
159 b->action_set, b->action_set_len));
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 recirc_find_equal(const struct frozen_state *target, uint32_t hash)
167 struct recirc_id_node *node;
169 CMAP_FOR_EACH_WITH_HASH (node, metadata_node, hash, &metadata_map) {
170 if (frozen_state_equal(&node->state, target)) {
177 static struct recirc_id_node *
178 recirc_ref_equal(const struct frozen_state *target, uint32_t hash)
180 struct recirc_id_node *node;
183 node = recirc_find_equal(target, hash);
185 /* Try again if the node was released before we get the reference. */
186 } while (node && !ovs_refcount_try_ref_rcu(&node->refcount));
192 frozen_state_clone(struct frozen_state *new, const struct frozen_state *old,
193 struct flow_tnl *tunnel)
196 flow_tnl_copy__(tunnel, old->metadata.tunnel);
197 new->metadata.tunnel = tunnel;
199 new->stack = (new->n_stack
200 ? xmemdup(new->stack, new->n_stack * sizeof *new->stack)
202 new->ofpacts = (new->ofpacts_len
203 ? xmemdup(new->ofpacts, new->ofpacts_len)
205 new->action_set = (new->action_set_len
206 ? xmemdup(new->action_set, new->action_set_len)
211 frozen_state_free(struct frozen_state *state)
214 free(state->ofpacts);
215 free(state->action_set);
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 recirc_alloc_id__(const struct frozen_state *state, uint32_t hash)
225 ovs_assert(state->action_set_len <= state->ofpacts_len);
227 struct recirc_id_node *node = xzalloc(sizeof *node);
230 ovs_refcount_init(&node->refcount);
231 frozen_state_clone(CONST_CAST(struct frozen_state *, &node->state), state,
232 &node->state_metadata_tunnel);
234 ovs_mutex_lock(&mutex);
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 node->id = next_id++;
241 if (OVS_UNLIKELY(!node->id)) {
242 next_id = RECIRC_POOL_STATIC_IDS + 1;
243 node->id = next_id++;
245 /* Find if the id is free. */
246 if (OVS_LIKELY(!recirc_find__(node->id))) {
250 cmap_insert(&id_map, &node->id_node, node->id);
251 cmap_insert(&metadata_map, &node->metadata_node, node->hash);
252 ovs_mutex_unlock(&mutex);
256 /* Look up an existing ID for the given flow's metadata and optional actions.
259 recirc_find_id(const struct frozen_state *target)
261 uint32_t hash = frozen_state_hash(target);
262 struct recirc_id_node *node = recirc_find_equal(target, hash);
263 return node ? node->id : 0;
266 /* Allocate a unique recirculation id for the given set of flow metadata and
269 recirc_alloc_id_ctx(const struct frozen_state *state)
271 uint32_t hash = frozen_state_hash(state);
272 struct recirc_id_node *node = recirc_ref_equal(state, hash);
274 node = recirc_alloc_id__(state, hash);
279 /* Allocate a unique recirculation id. */
281 recirc_alloc_id(struct ofproto_dpif *ofproto)
283 struct flow_tnl tunnel;
284 tunnel.ip_dst = htonl(0);
285 tunnel.ipv6_dst = in6addr_any;
286 struct frozen_state state = {
287 .table_id = TBL_INTERNAL,
288 .ofproto_uuid = *ofproto_dpif_get_uuid(ofproto),
289 .metadata = { .tunnel = &tunnel, .in_port = OFPP_NONE },
291 return recirc_alloc_id__(&state, frozen_state_hash(&state))->id;
295 recirc_id_node_free(struct recirc_id_node *node)
297 frozen_state_free(CONST_CAST(struct frozen_state *, &node->state));
302 recirc_id_node_unref(const struct recirc_id_node *node_)
305 struct recirc_id_node *node = CONST_CAST(struct recirc_id_node *, node_);
307 if (node && ovs_refcount_unref(&node->refcount) == 1) {
308 ovs_mutex_lock(&mutex);
309 /* Prevent re-use of this node by removing the node from 'metadata_map'
311 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 ovs_list_insert(&expiring, &node->exp_node);
315 ovs_mutex_unlock(&mutex);
320 recirc_free_id(uint32_t id)
322 const struct recirc_id_node *node;
324 node = recirc_id_node_find(id);
326 recirc_id_node_unref(node);
328 VLOG_ERR("Freeing nonexistent recirculation ID: %"PRIu32, id);
332 /* Called when 'ofproto' is destructed. Checks for and clears any
334 * No other thread may have access to the 'ofproto' being destructed.
335 * All related datapath flows must be deleted before calling this. */
337 recirc_free_ofproto(struct ofproto_dpif *ofproto, const char *ofproto_name)
339 struct recirc_id_node *n;
341 const struct uuid *ofproto_uuid = ofproto_dpif_get_uuid(ofproto);
342 CMAP_FOR_EACH (n, metadata_node, &metadata_map) {
343 if (uuid_equals(&n->state.ofproto_uuid, ofproto_uuid)) {
344 VLOG_ERR("recirc_id %"PRIu32
345 " left allocated when ofproto (%s)"
346 " is destructed", n->id, ofproto_name);