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.
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
;
29 static struct cmap id_map
;
30 static struct cmap metadata_map
;
32 static struct ovs_list expiring
OVS_GUARDED_BY(mutex
);
33 static struct ovs_list expired
OVS_GUARDED_BY(mutex
);
35 static uint32_t next_id
OVS_GUARDED_BY(mutex
); /* Possible next free id. */
37 #define RECIRC_POOL_STATIC_IDS 1024
39 static void recirc_id_node_free(struct recirc_id_node
*);
44 static struct ovsthread_once once
= OVSTHREAD_ONCE_INITIALIZER
;
46 if (ovsthread_once_start(&once
)) {
47 ovs_mutex_init(&mutex
);
48 ovs_mutex_lock(&mutex
);
49 next_id
= 1; /* 0 is not a valid ID. */
51 cmap_init(&metadata_map
);
54 ovs_mutex_unlock(&mutex
);
56 ovsthread_once_done(&once
);
61 /* This should be called by the revalidator once at each round (every 500ms or
66 static long long int last
= 0;
67 long long int now
= time_msec();
69 /* Do maintenance at most 4 times / sec. */
70 ovs_mutex_lock(&mutex
);
71 if (now
- last
> 250) {
72 struct recirc_id_node
*node
;
76 /* Nodes in 'expiring' and 'expired' lists have the refcount of zero,
77 * which means that while they can still be found (by id), no new
78 * references can be taken on them. We have removed the entry from the
79 * 'metadata_map', at the time when refcount reached zero, causing any
80 * new translations to allocate a new ID. This allows the expiring
81 * entry to be safely deleted while any sudden new use of the similar
82 * recirculation will safely start using a new recirculation ID. When
83 * the refcount gets to zero, the node is also added to the 'expiring'
84 * list. At any time after that the nodes in the 'expiring' list can
85 * be moved to the 'expired' list, from which they are deleted at least
86 * 250ms afterwards. */
88 /* Delete the expired. These have been lingering for at least 250 ms,
89 * which should be enough for any ongoing recirculations to be
91 LIST_FOR_EACH_POP (node
, exp_node
, &expired
) {
92 cmap_remove(&id_map
, &node
->id_node
, node
->id
);
93 ovsrcu_postpone(recirc_id_node_free
, node
);
96 if (!list_is_empty(&expiring
)) {
97 /* 'expired' is now empty, move nodes in 'expiring' to it. */
98 list_splice(&expired
, list_front(&expiring
), &expiring
);
101 ovs_mutex_unlock(&mutex
);
104 /* We use the id as the hash value, which works due to cmap internal rehashing.
105 * We also only insert nodes with unique IDs, so all possible hash collisions
106 * remain internal to the cmap. */
107 static struct recirc_id_node
*
108 recirc_find__(uint32_t id
)
111 struct cmap_node
*node
= cmap_find_protected(&id_map
, id
);
113 return node
? CONTAINER_OF(node
, struct recirc_id_node
, id_node
) : NULL
;
116 /* Lockless RCU protected lookup. If node is needed accross RCU quiescent
117 * state, caller should copy the contents. */
118 const struct recirc_id_node
*
119 recirc_id_node_find(uint32_t id
)
121 const struct cmap_node
*node
= cmap_find(&id_map
, id
);
124 ? CONTAINER_OF(node
, const struct recirc_id_node
, id_node
)
129 recirc_metadata_hash(const struct recirc_state
*state
)
133 hash
= hash_pointer(state
->ofproto
, 0);
134 hash
= hash_int(state
->table_id
, hash
);
135 if (flow_tnl_dst_is_set(state
->metadata
.tunnel
)) {
136 /* We may leave remainder bytes unhashed, but that is unlikely as
137 * the tunnel is not in the datapath format. */
138 hash
= hash_bytes64((const uint64_t *) state
->metadata
.tunnel
,
139 flow_tnl_size(state
->metadata
.tunnel
), hash
);
141 hash
= hash_boolean(state
->conntracked
, hash
);
142 hash
= hash_bytes64((const uint64_t *) &state
->metadata
.metadata
,
143 sizeof state
->metadata
- sizeof state
->metadata
.tunnel
,
145 if (state
->stack
&& state
->stack
->size
!= 0) {
146 hash
= hash_bytes64((const uint64_t *) state
->stack
->data
,
147 state
->stack
->size
, hash
);
149 hash
= hash_int(state
->mirrors
, hash
);
150 hash
= hash_int(state
->action_set_len
, hash
);
151 if (state
->ofpacts_len
) {
152 hash
= hash_bytes64(ALIGNED_CAST(const uint64_t *, state
->ofpacts
),
153 state
->ofpacts_len
, hash
);
159 recirc_metadata_equal(const struct recirc_state
*a
,
160 const struct recirc_state
*b
)
162 return (a
->table_id
== b
->table_id
163 && a
->ofproto
== b
->ofproto
164 && flow_tnl_equal(a
->metadata
.tunnel
, b
->metadata
.tunnel
)
165 && !memcmp(&a
->metadata
.metadata
, &b
->metadata
.metadata
,
166 sizeof a
->metadata
- sizeof a
->metadata
.tunnel
)
167 && (((!a
->stack
|| !a
->stack
->size
) &&
168 (!b
->stack
|| !b
->stack
->size
))
169 || (a
->stack
&& b
->stack
&& ofpbuf_equal(a
->stack
, b
->stack
)))
170 && a
->mirrors
== b
->mirrors
171 && a
->conntracked
== b
->conntracked
172 && a
->action_set_len
== b
->action_set_len
173 && ofpacts_equal(a
->ofpacts
, a
->ofpacts_len
,
174 b
->ofpacts
, b
->ofpacts_len
));
177 /* Lockless RCU protected lookup. If node is needed accross RCU quiescent
178 * state, caller should take a reference. */
179 static struct recirc_id_node
*
180 recirc_find_equal(const struct recirc_state
*target
, uint32_t hash
)
182 struct recirc_id_node
*node
;
184 CMAP_FOR_EACH_WITH_HASH (node
, metadata_node
, hash
, &metadata_map
) {
185 if (recirc_metadata_equal(&node
->state
, target
)) {
192 static struct recirc_id_node
*
193 recirc_ref_equal(const struct recirc_state
*target
, uint32_t hash
)
195 struct recirc_id_node
*node
;
198 node
= recirc_find_equal(target
, hash
);
200 /* Try again if the node was released before we get the reference. */
201 } while (node
&& !ovs_refcount_try_ref_rcu(&node
->refcount
));
207 recirc_state_clone(struct recirc_state
*new, const struct recirc_state
*old
,
208 struct flow_tnl
*tunnel
)
211 flow_tnl_copy__(tunnel
, old
->metadata
.tunnel
);
212 new->metadata
.tunnel
= tunnel
;
215 new->stack
= new->stack
->size
? ofpbuf_clone(new->stack
) : NULL
;
218 new->ofpacts
= (new->ofpacts_len
219 ? xmemdup(new->ofpacts
, new->ofpacts_len
)
225 recirc_state_free(struct recirc_state
*state
)
227 ofpbuf_delete(state
->stack
);
228 free(state
->ofpacts
);
231 /* Allocate a unique recirculation id for the given set of flow metadata.
232 * The ID space is 2^^32, so there should never be a situation in which all
233 * the IDs are used up. We loop until we find a free one.
234 * hash is recomputed if it is passed in as 0. */
235 static struct recirc_id_node
*
236 recirc_alloc_id__(const struct recirc_state
*state
, uint32_t hash
)
238 ovs_assert(state
->action_set_len
<= state
->ofpacts_len
);
240 struct recirc_id_node
*node
= xzalloc(sizeof *node
);
243 ovs_refcount_init(&node
->refcount
);
244 recirc_state_clone(CONST_CAST(struct recirc_state
*, &node
->state
), state
,
245 &node
->state_metadata_tunnel
);
247 ovs_mutex_lock(&mutex
);
249 /* Claim the next ID. The ID space should be sparse enough for the
250 allocation to succeed at the first try. We do skip the first
251 RECIRC_POOL_STATIC_IDS IDs on the later rounds, though, as some of
252 the initial allocations may be for long term uses (like bonds). */
253 node
->id
= next_id
++;
254 if (OVS_UNLIKELY(!node
->id
)) {
255 next_id
= RECIRC_POOL_STATIC_IDS
+ 1;
256 node
->id
= next_id
++;
258 /* Find if the id is free. */
259 if (OVS_LIKELY(!recirc_find__(node
->id
))) {
263 cmap_insert(&id_map
, &node
->id_node
, node
->id
);
264 cmap_insert(&metadata_map
, &node
->metadata_node
, node
->hash
);
265 ovs_mutex_unlock(&mutex
);
269 /* Look up an existing ID for the given flow's metadata and optional actions.
272 recirc_find_id(const struct recirc_state
*target
)
274 uint32_t hash
= recirc_metadata_hash(target
);
275 struct recirc_id_node
*node
= recirc_find_equal(target
, hash
);
276 return node
? node
->id
: 0;
279 /* Allocate a unique recirculation id for the given set of flow metadata and
282 recirc_alloc_id_ctx(const struct recirc_state
*state
)
284 uint32_t hash
= recirc_metadata_hash(state
);
285 struct recirc_id_node
*node
= recirc_ref_equal(state
, hash
);
287 node
= recirc_alloc_id__(state
, hash
);
292 /* Allocate a unique recirculation id. */
294 recirc_alloc_id(struct ofproto_dpif
*ofproto
)
296 struct flow_tnl tunnel
;
297 tunnel
.ip_dst
= htonl(0);
298 tunnel
.ipv6_dst
= in6addr_any
;
299 struct recirc_state state
= {
300 .table_id
= TBL_INTERNAL
,
302 .metadata
= { .tunnel
= &tunnel
, .in_port
= OFPP_NONE
},
304 return recirc_alloc_id__(&state
, recirc_metadata_hash(&state
))->id
;
308 recirc_id_node_free(struct recirc_id_node
*node
)
310 recirc_state_free(CONST_CAST(struct recirc_state
*, &node
->state
));
315 recirc_id_node_unref(const struct recirc_id_node
*node_
)
318 struct recirc_id_node
*node
= CONST_CAST(struct recirc_id_node
*, node_
);
320 if (node
&& ovs_refcount_unref(&node
->refcount
) == 1) {
321 ovs_mutex_lock(&mutex
);
322 /* Prevent re-use of this node by removing the node from 'metadata_map'
324 cmap_remove(&metadata_map
, &node
->metadata_node
, node
->hash
);
325 /* We keep the node in the 'id_map' so that it can be found as long
326 * as it lingers, and add it to the 'expiring' list. */
327 list_insert(&expiring
, &node
->exp_node
);
328 ovs_mutex_unlock(&mutex
);
333 recirc_free_id(uint32_t id
)
335 const struct recirc_id_node
*node
;
337 node
= recirc_id_node_find(id
);
339 recirc_id_node_unref(node
);
341 VLOG_ERR("Freeing nonexistent recirculation ID: %"PRIu32
, id
);
345 /* Called when 'ofproto' is destructed. Checks for and clears any
347 * No other thread may have access to the 'ofproto' being destructed.
348 * All related datapath flows must be deleted before calling this. */
350 recirc_free_ofproto(struct ofproto_dpif
*ofproto
, const char *ofproto_name
)
352 struct recirc_id_node
*n
;
354 CMAP_FOR_EACH (n
, metadata_node
, &metadata_map
) {
355 if (n
->state
.ofproto
== ofproto
) {
356 VLOG_ERR("recirc_id %"PRIu32
357 " left allocated when ofproto (%s)"
358 " is destructed", n
->id
, ofproto_name
);