2 * Copyright (c) 2014, 2015 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
42 static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
44 if (ovsthread_once_start(&once)) {
45 ovs_mutex_init(&mutex);
46 ovs_mutex_lock(&mutex);
47 next_id = 1; /* 0 is not a valid ID. */
49 cmap_init(&metadata_map);
52 ovs_mutex_unlock(&mutex);
54 ovsthread_once_done(&once);
59 /* This should be called by the revalidator once at each round (every 500ms or
64 static long long int last = 0;
65 long long int now = time_msec();
67 /* Do maintenance at most 4 times / sec. */
68 ovs_mutex_lock(&mutex);
69 if (now - last > 250) {
70 struct recirc_id_node *node;
74 /* Nodes in 'expiring' and 'expired' lists have the refcount of zero,
75 * which means that while they can still be found (by id), no new
76 * references can be taken on them. We have removed the entry from the
77 * 'metadata_map', at the time when refcount reached zero, causing any
78 * new translations to allocate a new ID. This allows the expiring
79 * entry to be safely deleted while any sudden new use of the similar
80 * recirculation will safely start using a new recirculation ID. When
81 * the refcount gets to zero, the node is also added to the 'expiring'
82 * list. At any time after that the nodes in the 'expiring' list can
83 * be moved to the 'expired' list, from which they are deleted at least
84 * 250ms afterwards. */
86 /* Delete the expired. These have been lingering for at least 250 ms,
87 * which should be enough for any ongoing recirculations to be
89 LIST_FOR_EACH_POP (node, exp_node, &expired) {
90 cmap_remove(&id_map, &node->id_node, node->id);
91 ovsrcu_postpone(free, node);
94 if (!list_is_empty(&expiring)) {
95 /* 'expired' is now empty, move nodes in 'expiring' to it. */
96 list_splice(&expired, list_front(&expiring), &expiring);
99 ovs_mutex_unlock(&mutex);
102 /* We use the id as the hash value, which works due to cmap internal rehashing.
103 * We also only insert nodes with unique IDs, so all possible hash collisions
104 * remain internal to the cmap. */
105 static struct recirc_id_node *
106 recirc_find__(uint32_t id)
109 struct cmap_node *node = cmap_find_protected(&id_map, id);
111 return node ? CONTAINER_OF(node, struct recirc_id_node, id_node) : NULL;
114 /* Lockless RCU protected lookup. If node is needed accross RCU quiescent
115 * state, caller should copy the contents. */
116 const struct recirc_id_node *
117 recirc_id_node_find(uint32_t id)
119 const struct cmap_node *node = cmap_find(&id_map, id);
122 ? CONTAINER_OF(node, const struct recirc_id_node, id_node)
127 recirc_metadata_hash(struct ofproto_dpif *ofproto, uint8_t table_id,
128 struct recirc_metadata *md, struct ofpbuf *stack,
129 uint32_t action_set_len, uint32_t ofpacts_len,
130 const struct ofpact *ofpacts)
134 BUILD_ASSERT(OFPACT_ALIGNTO == sizeof(uint64_t));
136 hash = hash_pointer(ofproto, 0);
137 hash = hash_int(table_id, hash);
138 hash = hash_words64((const uint64_t *)md, sizeof *md / sizeof(uint64_t),
140 if (stack && stack->size != 0) {
141 hash = hash_words64((const uint64_t *)stack->data,
142 stack->size / sizeof(uint64_t), hash);
144 hash = hash_int(action_set_len, hash);
146 hash = hash_words64(ALIGNED_CAST(const uint64_t *, ofpacts),
147 OFPACT_ALIGN(ofpacts_len) / sizeof(uint64_t),
154 recirc_metadata_equal(const struct recirc_id_node *node,
155 struct ofproto_dpif *ofproto, uint8_t table_id,
156 struct recirc_metadata *md, struct ofpbuf *stack,
157 uint32_t action_set_len, uint32_t ofpacts_len,
158 const struct ofpact *ofpacts)
160 return node->ofproto == ofproto
161 && node->table_id == table_id
162 && !memcmp(&node->metadata, md, sizeof *md)
163 && ((!node->stack && (!stack || stack->size == 0))
164 || (node->stack && stack && ofpbuf_equal(node->stack, stack)))
165 && node->action_set_len == action_set_len
166 && node->ofpacts_len == ofpacts_len
167 && (ofpacts_len == 0 || !memcmp(node->ofpacts, ofpacts, ofpacts_len));
170 /* Lockless RCU protected lookup. If node is needed accross RCU quiescent
171 * state, caller should take a reference. */
172 static struct recirc_id_node *
173 recirc_find_equal(struct ofproto_dpif *ofproto, uint8_t table_id,
174 struct recirc_metadata *md, struct ofpbuf *stack,
175 uint32_t action_set_len, uint32_t ofpacts_len,
176 const struct ofpact *ofpacts, uint32_t hash)
178 struct recirc_id_node *node;
180 CMAP_FOR_EACH_WITH_HASH(node, metadata_node, hash, &metadata_map) {
181 if (recirc_metadata_equal(node, ofproto, table_id, md, stack,
182 action_set_len, ofpacts_len, ofpacts)) {
189 static struct recirc_id_node *
190 recirc_ref_equal(struct ofproto_dpif *ofproto, uint8_t table_id,
191 struct recirc_metadata *md, struct ofpbuf *stack,
192 uint32_t action_set_len, uint32_t ofpacts_len,
193 const struct ofpact *ofpacts, uint32_t hash)
195 struct recirc_id_node *node;
198 node = recirc_find_equal(ofproto, table_id, md, stack, action_set_len,
199 ofpacts_len, ofpacts, hash);
201 /* Try again if the node was released before we get the reference. */
202 } while (node && !ovs_refcount_try_ref_rcu(&node->refcount));
207 /* Allocate a unique recirculation id for the given set of flow metadata.
208 * The ID space is 2^^32, so there should never be a situation in which all
209 * the IDs are used up. We loop until we find a free one.
210 * hash is recomputed if it is passed in as 0. */
211 static struct recirc_id_node *
212 recirc_alloc_id__(struct ofproto_dpif *ofproto, uint8_t table_id,
213 struct recirc_metadata *md, struct ofpbuf *stack,
214 uint32_t action_set_len, uint32_t ofpacts_len,
215 const struct ofpact *ofpacts, uint32_t hash)
217 struct recirc_id_node *node = xzalloc(sizeof *node +
218 OFPACT_ALIGN(ofpacts_len));
220 ovs_refcount_init(&node->refcount);
222 node->ofproto = ofproto;
223 node->table_id = table_id;
224 memcpy(&node->metadata, md, sizeof node->metadata);
225 node->stack = (stack && stack->size) ? ofpbuf_clone(stack) : NULL;
226 node->action_set_len = action_set_len;
227 node->ofpacts_len = ofpacts_len;
229 memcpy(node->ofpacts, ofpacts, ofpacts_len);
232 ovs_mutex_lock(&mutex);
234 /* Claim the next ID. The ID space should be sparse enough for the
235 allocation to succeed at the first try. We do skip the first
236 RECIRC_POOL_STATIC_IDS IDs on the later rounds, though, as some of
237 the initial allocations may be for long term uses (like bonds). */
238 node->id = next_id++;
239 if (OVS_UNLIKELY(!node->id)) {
240 next_id = RECIRC_POOL_STATIC_IDS + 1;
241 node->id = next_id++;
243 /* Find if the id is free. */
244 if (OVS_LIKELY(!recirc_find__(node->id))) {
248 cmap_insert(&id_map, &node->id_node, node->id);
249 cmap_insert(&metadata_map, &node->metadata_node, node->hash);
250 ovs_mutex_unlock(&mutex);
254 /* Look up an existing ID for the given flow's metadata and optional actions.
257 recirc_find_id(struct ofproto_dpif *ofproto, uint8_t table_id,
258 struct recirc_metadata *md, struct ofpbuf *stack,
259 uint32_t action_set_len, uint32_t ofpacts_len,
260 const struct ofpact *ofpacts)
262 /* Check if an ID with the given metadata already exists. */
263 struct recirc_id_node *node;
266 hash = recirc_metadata_hash(ofproto, table_id, md, stack, action_set_len,
267 ofpacts_len, ofpacts);
268 node = recirc_find_equal(ofproto, table_id, md, stack, action_set_len,
269 ofpacts_len, ofpacts, hash);
271 return node ? node->id : 0;
274 /* Allocate a unique recirculation id for the given set of flow metadata and
277 recirc_alloc_id_ctx(struct ofproto_dpif *ofproto, uint8_t table_id,
278 struct recirc_metadata *md, struct ofpbuf *stack,
279 uint32_t action_set_len, uint32_t ofpacts_len,
280 const struct ofpact *ofpacts)
282 struct recirc_id_node *node;
285 /* Look up an existing ID. */
286 hash = recirc_metadata_hash(ofproto, table_id, md, stack, action_set_len,
287 ofpacts_len, ofpacts);
288 node = recirc_ref_equal(ofproto, table_id, md, stack, action_set_len,
289 ofpacts_len, ofpacts, hash);
291 /* Allocate a new recirc ID if needed. */
293 ovs_assert(action_set_len <= ofpacts_len);
295 node = recirc_alloc_id__(ofproto, table_id, md, stack, action_set_len,
296 ofpacts_len, ofpacts, hash);
302 /* Allocate a unique recirculation id. */
304 recirc_alloc_id(struct ofproto_dpif *ofproto)
306 struct recirc_metadata md;
307 struct recirc_id_node *node;
310 memset(&md, 0, sizeof md);
311 md.in_port = OFPP_NONE;
312 hash = recirc_metadata_hash(ofproto, TBL_INTERNAL, &md, NULL, 0, 0, NULL);
313 node = recirc_alloc_id__(ofproto, TBL_INTERNAL, &md, NULL, 0, 0, NULL,
319 recirc_id_node_unref(const struct recirc_id_node *node_)
322 struct recirc_id_node *node = CONST_CAST(struct recirc_id_node *, node_);
324 if (node && ovs_refcount_unref(&node->refcount) == 1) {
325 ovs_mutex_lock(&mutex);
326 /* Prevent re-use of this node by removing the node from 'metadata_map'
328 cmap_remove(&metadata_map, &node->metadata_node, node->hash);
329 /* We keep the node in the 'id_map' so that it can be found as long
330 * as it lingers, and add it to the 'expiring' list. */
331 list_insert(&expiring, &node->exp_node);
332 ovs_mutex_unlock(&mutex);
337 recirc_free_id(uint32_t id)
339 const struct recirc_id_node *node;
341 node = recirc_id_node_find(id);
343 recirc_id_node_unref(node);
345 VLOG_ERR("Freeing nonexistent recirculation ID: %"PRIu32, id);
349 /* Called when 'ofproto' is destructed. Checks for and clears any
351 * No other thread may have access to the 'ofproto' being destructed.
352 * All related datapath flows must be deleted before calling this. */
354 recirc_free_ofproto(struct ofproto_dpif *ofproto, const char *ofproto_name)
356 struct recirc_id_node *n;
358 CMAP_FOR_EACH (n, metadata_node, &metadata_map) {
359 if (n->ofproto == ofproto) {
360 VLOG_ERR("recirc_id %"PRIu32
361 " left allocated when ofproto (%s)"
362 " is destructed", n->id, ofproto_name);