]>
git.proxmox.com Git - mirror_ovs.git/blob - ofproto/ofproto-dpif-rid.c
2 * Copyright (c) 2014, 2015, 2016, 2017 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 recirc_id_node_find_and_ref(uint32_t id
)
113 struct recirc_id_node
*rid_node
=
114 CONST_CAST(struct recirc_id_node
*, recirc_id_node_find(id
));
120 return ovs_refcount_try_ref_rcu(&rid_node
->refcount
);
124 frozen_state_hash(const struct frozen_state
*state
)
128 hash
= uuid_hash(&state
->ofproto_uuid
);
129 hash
= hash_int(state
->table_id
, hash
);
130 hash
= hash_bytes64((const uint64_t *) &state
->metadata
,
131 sizeof state
->metadata
, hash
);
132 hash
= hash_boolean(state
->conntracked
, hash
);
133 hash
= hash_boolean(state
->was_mpls
, hash
);
134 if (state
->stack
&& state
->stack_size
) {
135 hash
= hash_bytes(state
->stack
, state
->stack_size
, hash
);
137 hash
= hash_int(state
->mirrors
, hash
);
138 if (state
->action_set_len
) {
139 hash
= hash_bytes64(ALIGNED_CAST(const uint64_t *, state
->action_set
),
140 state
->action_set_len
, hash
);
142 if (state
->ofpacts_len
) {
143 hash
= hash_bytes64(ALIGNED_CAST(const uint64_t *, state
->ofpacts
),
144 state
->ofpacts_len
, hash
);
146 if (state
->userdata
&& state
->userdata_len
) {
147 hash
= hash_bytes(state
->userdata
, state
->userdata_len
, hash
);
153 frozen_state_equal(const struct frozen_state
*a
, const struct frozen_state
*b
)
155 return (a
->table_id
== b
->table_id
156 && uuid_equals(&a
->ofproto_uuid
, &b
->ofproto_uuid
)
157 && !memcmp(&a
->metadata
, &b
->metadata
, sizeof a
->metadata
)
158 && a
->stack_size
== b
->stack_size
159 && !memcmp(a
->stack
, b
->stack
, a
->stack_size
)
160 && a
->mirrors
== b
->mirrors
161 && a
->conntracked
== b
->conntracked
162 && a
->was_mpls
== b
->was_mpls
163 && ofpacts_equal(a
->ofpacts
, a
->ofpacts_len
,
164 b
->ofpacts
, b
->ofpacts_len
)
165 && ofpacts_equal(a
->action_set
, a
->action_set_len
,
166 b
->action_set
, b
->action_set_len
)
167 && !memcmp(a
->userdata
, b
->userdata
, a
->userdata_len
)
168 && uuid_equals(&a
->xport_uuid
, &b
->xport_uuid
));
171 /* Lockless RCU protected lookup. If node is needed accross RCU quiescent
172 * state, caller should take a reference. */
173 static struct recirc_id_node
*
174 recirc_find_equal(const struct frozen_state
*target
, uint32_t hash
)
176 struct recirc_id_node
*node
;
178 CMAP_FOR_EACH_WITH_HASH (node
, metadata_node
, hash
, &metadata_map
) {
179 if (frozen_state_equal(&node
->state
, target
)) {
186 static struct recirc_id_node
*
187 recirc_ref_equal(const struct frozen_state
*target
, uint32_t hash
)
189 struct recirc_id_node
*node
;
192 node
= recirc_find_equal(target
, hash
);
194 /* Try again if the node was released before we get the reference. */
195 } while (node
&& !ovs_refcount_try_ref_rcu(&node
->refcount
));
201 frozen_state_clone(struct frozen_state
*new, const struct frozen_state
*old
)
204 new->stack
= (new->stack_size
205 ? xmemdup(new->stack
, new->stack_size
)
207 new->ofpacts
= (new->ofpacts_len
208 ? xmemdup(new->ofpacts
, new->ofpacts_len
)
210 new->action_set
= (new->action_set_len
211 ? xmemdup(new->action_set
, new->action_set_len
)
213 new->userdata
= (new->userdata_len
214 ? xmemdup(new->userdata
, new->userdata_len
)
219 frozen_state_free(struct frozen_state
*state
)
222 free(state
->ofpacts
);
223 free(state
->action_set
);
224 free(state
->userdata
);
227 /* Allocate a unique recirculation id for the given set of flow metadata.
228 * The ID space is 2^^32, so there should never be a situation in which all
229 * the IDs are used up. We loop until we find a free one. */
230 static struct recirc_id_node
*
231 recirc_alloc_id__(const struct frozen_state
*state
, uint32_t hash
)
233 ovs_assert(state
->action_set_len
<= state
->ofpacts_len
);
235 struct recirc_id_node
*node
= xzalloc(sizeof *node
);
238 ovs_refcount_init(&node
->refcount
);
239 frozen_state_clone(CONST_CAST(struct frozen_state
*, &node
->state
), state
);
241 ovs_mutex_lock(&mutex
);
243 /* Claim the next ID. The ID space should be sparse enough for the
244 allocation to succeed at the first try. We do skip the first
245 RECIRC_POOL_STATIC_IDS IDs on the later rounds, though, as some of
246 the initial allocations may be for long term uses (like bonds). */
247 node
->id
= next_id
++;
248 if (OVS_UNLIKELY(!node
->id
)) {
249 next_id
= RECIRC_POOL_STATIC_IDS
+ 1;
250 node
->id
= next_id
++;
252 /* Find if the id is free. */
253 if (OVS_LIKELY(!recirc_find__(node
->id
))) {
257 cmap_insert(&id_map
, &node
->id_node
, node
->id
);
258 cmap_insert(&metadata_map
, &node
->metadata_node
, node
->hash
);
259 ovs_mutex_unlock(&mutex
);
263 /* Look up an existing ID for the given flow's metadata and optional actions.
266 recirc_find_id(const struct frozen_state
*target
)
268 uint32_t hash
= frozen_state_hash(target
);
269 struct recirc_id_node
*node
= recirc_find_equal(target
, hash
);
270 return node
? node
->id
: 0;
273 /* Allocate a unique recirculation id for the given set of flow metadata and
276 recirc_alloc_id_ctx(const struct frozen_state
*state
)
278 uint32_t hash
= frozen_state_hash(state
);
279 struct recirc_id_node
*node
= recirc_ref_equal(state
, hash
);
281 node
= recirc_alloc_id__(state
, hash
);
286 /* Allocate a unique recirculation id. */
288 recirc_alloc_id(struct ofproto_dpif
*ofproto
)
290 struct frozen_state state
= {
291 .table_id
= TBL_INTERNAL
,
292 .ofproto_uuid
= ofproto
->uuid
,
296 .ipv6_dst
= in6addr_any
,
298 .in_port
= OFPP_NONE
},
300 /* In order to make sparse happy, xport_uuid needs to be set separately. */
301 state
.xport_uuid
= UUID_ZERO
;
302 return recirc_alloc_id__(&state
, frozen_state_hash(&state
))->id
;
306 recirc_id_node_free(struct recirc_id_node
*node
)
308 frozen_state_free(CONST_CAST(struct frozen_state
*, &node
->state
));
313 recirc_id_node_unref(const struct recirc_id_node
*node_
)
316 struct recirc_id_node
*node
= CONST_CAST(struct recirc_id_node
*, node_
);
318 if (node
&& ovs_refcount_unref(&node
->refcount
) == 1) {
319 ovs_mutex_lock(&mutex
);
320 /* Prevent re-use of this node by removing the node from 'metadata_map'
322 cmap_remove(&metadata_map
, &node
->metadata_node
, node
->hash
);
323 /* We keep the node in the 'id_map' so that it can be found as long
324 * as it lingers, and add it to the 'expiring' list. */
325 ovs_list_insert(&expiring
, &node
->exp_node
);
326 ovs_mutex_unlock(&mutex
);
331 recirc_free_id(uint32_t id
)
333 const struct recirc_id_node
*node
;
335 node
= recirc_id_node_find(id
);
337 recirc_id_node_unref(node
);
339 VLOG_ERR("Freeing nonexistent recirculation ID: %"PRIu32
, id
);
343 /* Called when 'ofproto' is destructed. Checks for and clears any
345 * No other thread may have access to the 'ofproto' being destructed.
346 * All related datapath flows must be deleted before calling this. */
348 recirc_free_ofproto(struct ofproto_dpif
*ofproto
, const char *ofproto_name
)
350 struct recirc_id_node
*n
;
352 CMAP_FOR_EACH (n
, metadata_node
, &metadata_map
) {
353 if (uuid_equals(&n
->state
.ofproto_uuid
, &ofproto
->uuid
)) {
354 VLOG_ERR("recirc_id %"PRIu32
355 " left allocated when ofproto (%s)"
356 " is destructed", n
->id
, ofproto_name
);