Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
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 : : #include "mac-learning.h"
19 : :
20 : : #include <inttypes.h>
21 : : #include <stdlib.h>
22 : :
23 : : #include "bitmap.h"
24 : : #include "coverage.h"
25 : : #include "hash.h"
26 : : #include "openvswitch/list.h"
27 : : #include "poll-loop.h"
28 : : #include "timeval.h"
29 : : #include "unaligned.h"
30 : : #include "util.h"
31 : : #include "vlan-bitmap.h"
32 : :
33 : 75520 : COVERAGE_DEFINE(mac_learning_learned);
34 : 71668 : COVERAGE_DEFINE(mac_learning_expired);
35 : :
36 : : /* Returns the number of seconds since 'e' (within 'ml') was last learned. */
37 : : int
38 : 4187 : mac_entry_age(const struct mac_learning *ml, const struct mac_entry *e)
39 : : {
40 : 4187 : time_t remaining = e->expires - time_now();
41 : 4187 : return ml->idle_time - remaining;
42 : : }
43 : :
44 : : static uint32_t
45 : 36214 : mac_table_hash(const struct mac_learning *ml, const struct eth_addr mac,
46 : : uint16_t vlan)
47 : : {
48 : 36214 : return hash_mac(mac, vlan, ml->secret);
49 : : }
50 : :
51 : : static struct mac_entry *
52 : 99355 : mac_entry_from_lru_node(struct ovs_list *list)
53 : : {
54 : 99355 : return CONTAINER_OF(list, struct mac_entry, lru_node);
55 : : }
56 : :
57 : : static struct mac_entry *
58 : 35572 : mac_entry_lookup(const struct mac_learning *ml,
59 : : const struct eth_addr mac, uint16_t vlan)
60 : : {
61 : : struct mac_entry *e;
62 : :
63 [ + + ][ - + ]: 35572 : HMAP_FOR_EACH_WITH_HASH (e, hmap_node, mac_table_hash(ml, mac, vlan),
64 : : &ml->table) {
65 [ + - ][ + - ]: 20795 : if (e->vlan == vlan && eth_addr_equals(e->mac, mac)) {
66 : 20795 : return e;
67 : : }
68 : : }
69 : 14777 : return NULL;
70 : : }
71 : :
72 : : static struct mac_learning_port *
73 : 645 : mac_learning_port_lookup(struct mac_learning *ml, void *port)
74 : : {
75 : : struct mac_learning_port *mlport;
76 : :
77 [ + + ][ - + ]: 841 : HMAP_FOR_EACH_IN_BUCKET (mlport, hmap_node, hash_pointer(port, ml->secret),
78 : : &ml->ports_by_ptr) {
79 [ + + ]: 473 : if (mlport->port == port) {
80 : 277 : return mlport;
81 : : }
82 : : }
83 : 368 : return NULL;
84 : : }
85 : :
86 : : /* Changes the client-owned pointer for entry 'e' in 'ml' to 'port'. The
87 : : * pointer can be retrieved with mac_entry_get_port().
88 : : *
89 : : * The MAC-learning implementation treats the data that 'port' points to as
90 : : * opaque and never tries to dereference it. However, when a MAC learning
91 : : * table becomes overfull, so that eviction is required, the implementation
92 : : * does first evict MAC entries for the most common 'port's values in 'ml', so
93 : : * that there is a degree of fairness, that is, each port is entitled to its
94 : : * fair share of MAC entries. */
95 : : void
96 : 1287 : mac_entry_set_port(struct mac_learning *ml, struct mac_entry *e, void *port)
97 : : OVS_REQ_WRLOCK(ml->rwlock)
98 : : {
99 [ + - ]: 1287 : if (mac_entry_get_port(ml, e) != port) {
100 : 1287 : ml->need_revalidate = true;
101 : :
102 [ + + ]: 1287 : if (e->mlport) {
103 : 645 : struct mac_learning_port *mlport = e->mlport;
104 : 645 : ovs_list_remove(&e->port_lru_node);
105 : :
106 [ + + ]: 645 : if (ovs_list_is_empty(&mlport->port_lrus)) {
107 [ - + ]: 368 : ovs_assert(mlport->heap_node.priority == 1);
108 : 368 : hmap_remove(&ml->ports_by_ptr, &mlport->hmap_node);
109 : 368 : heap_remove(&ml->ports_by_usage, &mlport->heap_node);
110 : 368 : free(mlport);
111 : : } else {
112 [ - + ]: 277 : ovs_assert(mlport->heap_node.priority > 1);
113 : 277 : heap_change(&ml->ports_by_usage, &mlport->heap_node,
114 : 277 : mlport->heap_node.priority - 1);
115 : : }
116 : 645 : e->mlport = NULL;
117 : : }
118 : :
119 [ + + ]: 1287 : if (port) {
120 : : struct mac_learning_port *mlport;
121 : :
122 : 645 : mlport = mac_learning_port_lookup(ml, port);
123 [ + + ]: 645 : if (!mlport) {
124 : 368 : mlport = xzalloc(sizeof *mlport);
125 : 368 : hmap_insert(&ml->ports_by_ptr, &mlport->hmap_node,
126 : : hash_pointer(port, ml->secret));
127 : 368 : heap_insert(&ml->ports_by_usage, &mlport->heap_node, 1);
128 : 368 : mlport->port = port;
129 : 368 : ovs_list_init(&mlport->port_lrus);
130 : : } else {
131 : 277 : heap_change(&ml->ports_by_usage, &mlport->heap_node,
132 : 277 : mlport->heap_node.priority + 1);
133 : : }
134 : 645 : ovs_list_push_back(&mlport->port_lrus, &e->port_lru_node);
135 : 645 : e->mlport = mlport;
136 : : }
137 : : }
138 : 1287 : }
139 : :
140 : : /* Finds one of the ports with the most MAC entries and evicts its least
141 : : * recently used entry. */
142 : : static void
143 : 17 : evict_mac_entry_fairly(struct mac_learning *ml)
144 : : OVS_REQ_WRLOCK(ml->rwlock)
145 : : {
146 : : struct mac_learning_port *mlport;
147 : : struct mac_entry *e;
148 : :
149 : 17 : mlport = CONTAINER_OF(heap_max(&ml->ports_by_usage),
150 : : struct mac_learning_port, heap_node);
151 : 17 : e = CONTAINER_OF(ovs_list_front(&mlport->port_lrus),
152 : : struct mac_entry, port_lru_node);
153 : 17 : mac_learning_expire(ml, e);
154 : 17 : }
155 : :
156 : : /* If the LRU list is not empty, stores the least-recently-used entry in '*e'
157 : : * and returns true. Otherwise, if the LRU list is empty, stores NULL in '*e'
158 : : * and return false. */
159 : : static bool
160 : 157612 : get_lru(struct mac_learning *ml, struct mac_entry **e)
161 : : OVS_REQ_RDLOCK(ml->rwlock)
162 : : {
163 [ + + ]: 157612 : if (!ovs_list_is_empty(&ml->lrus)) {
164 : 49851 : *e = mac_entry_from_lru_node(ml->lrus.next);
165 : 49851 : return true;
166 : : } else {
167 : 107761 : *e = NULL;
168 : 107761 : return false;
169 : : }
170 : : }
171 : :
172 : : static unsigned int
173 : 5449 : normalize_idle_time(unsigned int idle_time)
174 : : {
175 : 5449 : return (idle_time < 15 ? 15
176 [ + - ]: 5449 : : idle_time > 3600 ? 3600
177 : : : idle_time);
178 : : }
179 : :
180 : : /* Creates and returns a new MAC learning table with an initial MAC aging
181 : : * timeout of 'idle_time' seconds and an initial maximum of MAC_DEFAULT_MAX
182 : : * entries. */
183 : : struct mac_learning *
184 : 749 : mac_learning_create(unsigned int idle_time)
185 : : {
186 : : struct mac_learning *ml;
187 : :
188 : 749 : ml = xmalloc(sizeof *ml);
189 : 749 : ovs_list_init(&ml->lrus);
190 : 749 : hmap_init(&ml->table);
191 : 749 : ml->secret = random_uint32();
192 : 749 : ml->flood_vlans = NULL;
193 : 749 : ml->idle_time = normalize_idle_time(idle_time);
194 : 749 : ml->max_entries = MAC_DEFAULT_MAX;
195 : 749 : ml->need_revalidate = false;
196 : 749 : hmap_init(&ml->ports_by_ptr);
197 : 749 : heap_init(&ml->ports_by_usage);
198 : 749 : ovs_refcount_init(&ml->ref_cnt);
199 : 749 : ovs_rwlock_init(&ml->rwlock);
200 : 749 : return ml;
201 : : }
202 : :
203 : : struct mac_learning *
204 : 41774 : mac_learning_ref(const struct mac_learning *ml_)
205 : : {
206 : 41774 : struct mac_learning *ml = CONST_CAST(struct mac_learning *, ml_);
207 [ + - ]: 41774 : if (ml) {
208 : 41774 : ovs_refcount_ref(&ml->ref_cnt);
209 : : }
210 : 41774 : return ml;
211 : : }
212 : :
213 : : /* Unreferences (and possibly destroys) MAC learning table 'ml'. */
214 : : void
215 : 84297 : mac_learning_unref(struct mac_learning *ml)
216 : : {
217 [ + + ][ + + ]: 84297 : if (ml && ovs_refcount_unref(&ml->ref_cnt) == 1) {
218 : : struct mac_entry *e, *next;
219 : :
220 : 749 : ovs_rwlock_wrlock(&ml->rwlock);
221 [ + - ][ - + ]: 749 : HMAP_FOR_EACH_SAFE (e, next, hmap_node, &ml->table) {
[ - + ]
222 : 0 : mac_learning_expire(ml, e);
223 : : }
224 : 749 : hmap_destroy(&ml->table);
225 : 749 : hmap_destroy(&ml->ports_by_ptr);
226 : 749 : heap_destroy(&ml->ports_by_usage);
227 : :
228 : 749 : bitmap_free(ml->flood_vlans);
229 : 749 : ovs_rwlock_unlock(&ml->rwlock);
230 : 749 : ovs_rwlock_destroy(&ml->rwlock);
231 : 749 : free(ml);
232 : : }
233 : 84297 : }
234 : :
235 : : /* Provides a bitmap of VLANs which have learning disabled, that is, VLANs on
236 : : * which all packets are flooded. Returns true if the set has changed from the
237 : : * previous value. */
238 : : bool
239 : 4700 : mac_learning_set_flood_vlans(struct mac_learning *ml,
240 : : const unsigned long *bitmap)
241 : : {
242 [ + - ]: 4700 : if (vlan_bitmap_equal(ml->flood_vlans, bitmap)) {
243 : 4700 : return false;
244 : : } else {
245 : 0 : bitmap_free(ml->flood_vlans);
246 : 0 : ml->flood_vlans = vlan_bitmap_clone(bitmap);
247 : 0 : return true;
248 : : }
249 : : }
250 : :
251 : : /* Changes the MAC aging timeout of 'ml' to 'idle_time' seconds. */
252 : : void
253 : 4700 : mac_learning_set_idle_time(struct mac_learning *ml, unsigned int idle_time)
254 : : {
255 : 4700 : idle_time = normalize_idle_time(idle_time);
256 [ - + ]: 4700 : if (idle_time != ml->idle_time) {
257 : : struct mac_entry *e;
258 : : int delta;
259 : :
260 : 0 : delta = (int) idle_time - (int) ml->idle_time;
261 [ # # ]: 0 : LIST_FOR_EACH (e, lru_node, &ml->lrus) {
262 : 0 : e->expires += delta;
263 : : }
264 : 0 : ml->idle_time = idle_time;
265 : : }
266 : 4700 : }
267 : :
268 : : /* Sets the maximum number of entries in 'ml' to 'max_entries', adjusting it
269 : : * to be within a reasonable range. */
270 : : void
271 : 4700 : mac_learning_set_max_entries(struct mac_learning *ml, size_t max_entries)
272 : : {
273 : 4700 : ml->max_entries = (max_entries < 10 ? 10
274 [ + - ]: 4700 : : max_entries > 1000 * 1000 ? 1000 * 1000
275 : : : max_entries);
276 : 4700 : }
277 : :
278 : : static bool
279 : 40346 : is_learning_vlan(const struct mac_learning *ml, uint16_t vlan)
280 : : {
281 [ - + ][ # # ]: 40346 : return !ml->flood_vlans || !bitmap_is_set(ml->flood_vlans, vlan);
282 : : }
283 : :
284 : : /* Returns true if 'src_mac' may be learned on 'vlan' for 'ml'.
285 : : * Returns false if 'ml' is NULL, if src_mac is not valid for learning, or if
286 : : * 'vlan' is configured on 'ml' to flood all packets. */
287 : : bool
288 : 6977 : mac_learning_may_learn(const struct mac_learning *ml,
289 : : const struct eth_addr src_mac, uint16_t vlan)
290 : : {
291 [ + - ][ + - ]: 6977 : return ml && is_learning_vlan(ml, vlan) && !eth_addr_is_multicast(src_mac);
[ + - ]
292 : : }
293 : :
294 : : /* Searches 'ml' for and returns a MAC learning entry for 'src_mac' in 'vlan',
295 : : * inserting a new entry if necessary. The caller must have already verified,
296 : : * by calling mac_learning_may_learn(), that 'src_mac' and 'vlan' are
297 : : * learnable.
298 : : *
299 : : * If the returned MAC entry is new (that is, if it has a NULL client-provided
300 : : * port, as returned by mac_entry_get_port()), then the caller must initialize
301 : : * the new entry's port to a nonnull value with mac_entry_set_port(). */
302 : : struct mac_entry *
303 : 2203 : mac_learning_insert(struct mac_learning *ml,
304 : : const struct eth_addr src_mac, uint16_t vlan)
305 : : {
306 : : struct mac_entry *e;
307 : :
308 : 2203 : e = mac_entry_lookup(ml, src_mac, vlan);
309 [ + + ]: 2203 : if (!e) {
310 : 642 : uint32_t hash = mac_table_hash(ml, src_mac, vlan);
311 : :
312 [ + + ]: 642 : if (hmap_count(&ml->table) >= ml->max_entries) {
313 : 17 : evict_mac_entry_fairly(ml);
314 : : }
315 : :
316 : 642 : e = xmalloc(sizeof *e);
317 : 642 : hmap_insert(&ml->table, &e->hmap_node, hash);
318 : 642 : e->mac = src_mac;
319 : 642 : e->vlan = vlan;
320 : 642 : e->grat_arp_lock = TIME_MIN;
321 : 642 : e->mlport = NULL;
322 : 642 : COVERAGE_INC(mac_learning_learned);
323 : : } else {
324 : 1561 : ovs_list_remove(&e->lru_node);
325 : : }
326 : :
327 : : /* Mark 'e' as recently used. */
328 : 2203 : ovs_list_push_back(&ml->lrus, &e->lru_node);
329 [ + + ]: 2203 : if (e->mlport) {
330 : 1561 : ovs_list_remove(&e->port_lru_node);
331 : 1561 : ovs_list_push_back(&e->mlport->port_lrus, &e->port_lru_node);
332 : : }
333 : 2203 : e->expires = time_now() + ml->idle_time;
334 : :
335 : 2203 : return e;
336 : : }
337 : :
338 : : /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml' and returns the associated MAC
339 : : * learning entry, if any. */
340 : : struct mac_entry *
341 : 35346 : mac_learning_lookup(const struct mac_learning *ml,
342 : : const struct eth_addr dst, uint16_t vlan)
343 : : {
344 [ + + ]: 35346 : if (eth_addr_is_multicast(dst)) {
345 : : /* No tag because the treatment of multicast destinations never
346 : : * changes. */
347 : 1977 : return NULL;
348 [ - + ]: 33369 : } else if (!is_learning_vlan(ml, vlan)) {
349 : : /* We don't tag this property. The set of learning VLANs changes so
350 : : * rarely that we revalidate every flow when it changes. */
351 : 0 : return NULL;
352 : : } else {
353 : 33369 : struct mac_entry *e = mac_entry_lookup(ml, dst, vlan);
354 : :
355 [ + + ][ - + ]: 33369 : ovs_assert(e == NULL || mac_entry_get_port(ml, e) != NULL);
356 : 33369 : return e;
357 : : }
358 : : }
359 : :
360 : : /* Expires 'e' from the 'ml' hash table. */
361 : : void
362 : 642 : mac_learning_expire(struct mac_learning *ml, struct mac_entry *e)
363 : : {
364 : 642 : ml->need_revalidate = true;
365 : 642 : mac_entry_set_port(ml, e, NULL);
366 : 642 : hmap_remove(&ml->table, &e->hmap_node);
367 : 642 : ovs_list_remove(&e->lru_node);
368 : 642 : free(e);
369 : 642 : }
370 : :
371 : : /* Expires all the mac-learning entries in 'ml'. */
372 : : void
373 : 7 : mac_learning_flush(struct mac_learning *ml)
374 : : {
375 : : struct mac_entry *e;
376 [ - + ]: 7 : while (get_lru(ml, &e)){
377 : 0 : mac_learning_expire(ml, e);
378 : : }
379 : 7 : hmap_shrink(&ml->table);
380 : 7 : }
381 : :
382 : : /* Does periodic work required by 'ml'. Returns true if something changed that
383 : : * may require flow revalidation. */
384 : : bool
385 : 157605 : mac_learning_run(struct mac_learning *ml)
386 : : {
387 : : bool need_revalidate;
388 : : struct mac_entry *e;
389 : :
390 [ + + ]: 157605 : while (get_lru(ml, &e)
391 [ - + ]: 49851 : && (hmap_count(&ml->table) > ml->max_entries
392 [ - + ]: 49851 : || time_now() >= e->expires)) {
393 : 0 : COVERAGE_INC(mac_learning_expired);
394 : 0 : mac_learning_expire(ml, e);
395 : : }
396 : :
397 : 157605 : need_revalidate = ml->need_revalidate;
398 : 157605 : ml->need_revalidate = false;
399 : 157605 : return need_revalidate;
400 : : }
401 : :
402 : : void
403 : 153567 : mac_learning_wait(struct mac_learning *ml)
404 : : {
405 [ + - ]: 153567 : if (hmap_count(&ml->table) > ml->max_entries
406 [ + + ]: 153567 : || ml->need_revalidate) {
407 : 72 : poll_immediate_wake();
408 [ + + ]: 153495 : } else if (!ovs_list_is_empty(&ml->lrus)) {
409 : 49504 : struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next);
410 : 49504 : poll_timer_wait_until(e->expires * 1000LL);
411 : : }
412 : 153567 : }
|
