]>
Commit | Line | Data |
---|---|---|
f5374617 | 1 | /* |
e672ff9b | 2 | * Copyright (c) 2014, 2015 Nicira, Inc. |
f5374617 AZ |
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 | ||
e672ff9b JR |
19 | #include "ofpbuf.h" |
20 | #include "ofproto-dpif.h" | |
f5374617 | 21 | #include "ofproto-dpif-rid.h" |
e672ff9b JR |
22 | #include "ofproto-provider.h" |
23 | #include "openvswitch/vlog.h" | |
f5374617 | 24 | |
e672ff9b | 25 | VLOG_DEFINE_THIS_MODULE(ofproto_dpif_rid); |
f5374617 | 26 | |
e672ff9b | 27 | static struct ovs_mutex mutex; |
f5374617 | 28 | |
e672ff9b JR |
29 | static struct cmap id_map; |
30 | static struct cmap metadata_map; | |
31 | ||
32 | static struct ovs_list expiring OVS_GUARDED_BY(mutex); | |
33 | static struct ovs_list expired OVS_GUARDED_BY(mutex); | |
34 | ||
35 | static uint32_t next_id OVS_GUARDED_BY(mutex); /* Possible next free id. */ | |
36 | ||
37 | #define RECIRC_POOL_STATIC_IDS 1024 | |
38 | ||
39 | void | |
40 | recirc_init(void) | |
f5374617 | 41 | { |
e672ff9b | 42 | static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER; |
f5374617 | 43 | |
e672ff9b JR |
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. */ | |
48 | cmap_init(&id_map); | |
49 | cmap_init(&metadata_map); | |
50 | list_init(&expiring); | |
51 | list_init(&expired); | |
52 | ovs_mutex_unlock(&mutex); | |
53 | ||
54 | ovsthread_once_done(&once); | |
55 | } | |
f5374617 | 56 | |
f5374617 AZ |
57 | } |
58 | ||
e672ff9b JR |
59 | /* This should be called by the revalidator once at each round (every 500ms or |
60 | * more). */ | |
f5374617 | 61 | void |
e672ff9b JR |
62 | recirc_run(void) |
63 | { | |
64 | static long long int last = 0; | |
65 | long long int now = time_msec(); | |
66 | ||
67 | /* Do maintenance at most 4 times / sec. */ | |
68 | ovs_mutex_lock(&mutex); | |
69 | if (now - last > 250) { | |
5f03c983 | 70 | struct recirc_id_node *node; |
e672ff9b JR |
71 | |
72 | last = now; | |
73 | ||
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. */ | |
85 | ||
86 | /* Delete the expired. These have been lingering for at least 250 ms, | |
87 | * which should be enough for any ongoing recirculations to be | |
88 | * finished. */ | |
5f03c983 | 89 | LIST_FOR_EACH_POP (node, exp_node, &expired) { |
e672ff9b JR |
90 | cmap_remove(&id_map, &node->id_node, node->id); |
91 | ovsrcu_postpone(free, node); | |
92 | } | |
93 | ||
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); | |
97 | } | |
98 | } | |
99 | ovs_mutex_unlock(&mutex); | |
100 | } | |
101 | ||
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) | |
107 | OVS_REQUIRES(mutex) | |
108 | { | |
109 | struct cmap_node *node = cmap_find_protected(&id_map, id); | |
110 | ||
111 | return node ? CONTAINER_OF(node, struct recirc_id_node, id_node) : NULL; | |
112 | } | |
113 | ||
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) | |
118 | { | |
119 | const struct cmap_node *node = cmap_find(&id_map, id); | |
120 | ||
121 | return node | |
122 | ? CONTAINER_OF(node, const struct recirc_id_node, id_node) | |
123 | : NULL; | |
124 | } | |
125 | ||
126 | static uint32_t | |
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) | |
131 | { | |
132 | uint32_t hash; | |
133 | ||
134 | BUILD_ASSERT(OFPACT_ALIGNTO == sizeof(uint64_t)); | |
135 | ||
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), | |
139 | hash); | |
140 | if (stack && stack->size != 0) { | |
141 | hash = hash_words64((const uint64_t *)stack->data, | |
142 | stack->size / sizeof(uint64_t), hash); | |
143 | } | |
144 | hash = hash_int(action_set_len, hash); | |
145 | if (ofpacts_len) { | |
146 | hash = hash_words64(ALIGNED_CAST(const uint64_t *, ofpacts), | |
147 | OFPACT_ALIGN(ofpacts_len) / sizeof(uint64_t), | |
148 | hash); | |
149 | } | |
150 | return hash; | |
151 | } | |
152 | ||
153 | static bool | |
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) | |
159 | { | |
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)); | |
168 | } | |
169 | ||
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) | |
177 | { | |
178 | struct recirc_id_node *node; | |
179 | ||
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)) { | |
183 | return node; | |
184 | } | |
185 | } | |
186 | return NULL; | |
187 | } | |
188 | ||
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) | |
194 | { | |
195 | struct recirc_id_node *node; | |
196 | ||
197 | do { | |
198 | node = recirc_find_equal(ofproto, table_id, md, stack, action_set_len, | |
199 | ofpacts_len, ofpacts, hash); | |
200 | ||
201 | /* Try again if the node was released before we get the reference. */ | |
202 | } while (node && !ovs_refcount_try_ref_rcu(&node->refcount)); | |
203 | ||
204 | return node; | |
205 | } | |
206 | ||
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) | |
216 | { | |
217 | struct recirc_id_node *node = xzalloc(sizeof *node + | |
218 | OFPACT_ALIGN(ofpacts_len)); | |
219 | node->hash = hash; | |
220 | ovs_refcount_init(&node->refcount); | |
221 | ||
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; | |
228 | if (ofpacts_len) { | |
229 | memcpy(node->ofpacts, ofpacts, ofpacts_len); | |
230 | } | |
231 | ||
232 | ovs_mutex_lock(&mutex); | |
233 | for (;;) { | |
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++; | |
242 | } | |
243 | /* Find if the id is free. */ | |
244 | if (OVS_LIKELY(!recirc_find__(node->id))) { | |
245 | break; | |
246 | } | |
247 | } | |
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); | |
251 | return node; | |
252 | } | |
253 | ||
254 | /* Look up an existing ID for the given flow's metadata and optional actions. | |
255 | */ | |
256 | uint32_t | |
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) | |
261 | { | |
262 | /* Check if an ID with the given metadata already exists. */ | |
263 | struct recirc_id_node *node; | |
264 | uint32_t hash; | |
265 | ||
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); | |
270 | ||
271 | return node ? node->id : 0; | |
272 | } | |
273 | ||
274 | /* Allocate a unique recirculation id for the given set of flow metadata and | |
275 | optional actions. */ | |
276 | uint32_t | |
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) | |
f5374617 | 281 | { |
e672ff9b JR |
282 | struct recirc_id_node *node; |
283 | uint32_t hash; | |
284 | ||
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); | |
290 | ||
291 | /* Allocate a new recirc ID if needed. */ | |
292 | if (!node) { | |
293 | ovs_assert(action_set_len <= ofpacts_len); | |
294 | ||
295 | node = recirc_alloc_id__(ofproto, table_id, md, stack, action_set_len, | |
296 | ofpacts_len, ofpacts, hash); | |
297 | } | |
298 | ||
299 | return node->id; | |
f5374617 AZ |
300 | } |
301 | ||
e672ff9b | 302 | /* Allocate a unique recirculation id. */ |
f5374617 | 303 | uint32_t |
e672ff9b | 304 | recirc_alloc_id(struct ofproto_dpif *ofproto) |
f5374617 | 305 | { |
e672ff9b JR |
306 | struct recirc_metadata md; |
307 | struct recirc_id_node *node; | |
308 | uint32_t hash; | |
f5374617 | 309 | |
e672ff9b JR |
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, | |
314 | hash); | |
315 | return node->id; | |
316 | } | |
f5374617 | 317 | |
e672ff9b JR |
318 | void |
319 | recirc_id_node_unref(const struct recirc_id_node *node_) | |
320 | OVS_EXCLUDED(mutex) | |
321 | { | |
322 | struct recirc_id_node *node = CONST_CAST(struct recirc_id_node *, node_); | |
323 | ||
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' | |
327 | */ | |
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); | |
27c24749 | 333 | } |
e672ff9b | 334 | } |
27c24749 | 335 | |
e672ff9b JR |
336 | void |
337 | recirc_free_id(uint32_t id) | |
338 | { | |
339 | const struct recirc_id_node *node; | |
340 | ||
341 | node = recirc_id_node_find(id); | |
342 | if (node) { | |
343 | recirc_id_node_unref(node); | |
344 | } else { | |
345 | VLOG_ERR("Freeing nonexistent recirculation ID: %"PRIu32, id); | |
346 | } | |
f5374617 AZ |
347 | } |
348 | ||
e672ff9b JR |
349 | /* Called when 'ofproto' is destructed. Checks for and clears any |
350 | * recirc_id leak. | |
351 | * No other thread may have access to the 'ofproto' being destructed. | |
352 | * All related datapath flows must be deleted before calling this. */ | |
f5374617 | 353 | void |
e672ff9b | 354 | recirc_free_ofproto(struct ofproto_dpif *ofproto, const char *ofproto_name) |
f5374617 | 355 | { |
e672ff9b JR |
356 | struct recirc_id_node *n; |
357 | ||
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); | |
363 | } | |
364 | } | |
f5374617 | 365 | } |