]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
8917f72c | 2 | * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc. |
064af421 | 3 | * |
a14bc59f BP |
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: | |
064af421 | 7 | * |
a14bc59f BP |
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. | |
064af421 BP |
15 | */ |
16 | ||
17 | #include <config.h> | |
18 | #include "mac-learning.h" | |
19 | ||
064af421 BP |
20 | #include <inttypes.h> |
21 | #include <stdlib.h> | |
22 | ||
f2d7fd66 | 23 | #include "bitmap.h" |
064af421 BP |
24 | #include "coverage.h" |
25 | #include "hash.h" | |
26 | #include "list.h" | |
27 | #include "poll-loop.h" | |
064af421 | 28 | #include "timeval.h" |
18e89129 | 29 | #include "unaligned.h" |
064af421 | 30 | #include "util.h" |
0fb7b915 | 31 | #include "vlan-bitmap.h" |
5136ce49 | 32 | |
d76f09ea BP |
33 | COVERAGE_DEFINE(mac_learning_learned); |
34 | COVERAGE_DEFINE(mac_learning_expired); | |
35 | ||
e764773c | 36 | /* Returns the number of seconds since 'e' (within 'ml') was last learned. */ |
321943f7 | 37 | int |
e764773c | 38 | mac_entry_age(const struct mac_learning *ml, const struct mac_entry *e) |
321943f7 BP |
39 | { |
40 | time_t remaining = e->expires - time_now(); | |
e764773c | 41 | return ml->idle_time - remaining; |
321943f7 BP |
42 | } |
43 | ||
064af421 | 44 | static uint32_t |
8e8d5966 EJ |
45 | mac_table_hash(const struct mac_learning *ml, const uint8_t mac[ETH_ADDR_LEN], |
46 | uint16_t vlan) | |
064af421 | 47 | { |
7e36ac42 | 48 | return hash_mac(mac, vlan, ml->secret); |
064af421 BP |
49 | } |
50 | ||
51 | static struct mac_entry * | |
52 | mac_entry_from_lru_node(struct list *list) | |
53 | { | |
54 | return CONTAINER_OF(list, struct mac_entry, lru_node); | |
55 | } | |
56 | ||
064af421 | 57 | static struct mac_entry * |
8ea45fdc EJ |
58 | mac_entry_lookup(const struct mac_learning *ml, |
59 | const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) | |
064af421 BP |
60 | { |
61 | struct mac_entry *e; | |
8ea45fdc | 62 | |
8e8d5966 | 63 | HMAP_FOR_EACH_WITH_HASH (e, hmap_node, mac_table_hash(ml, mac, vlan), |
8ea45fdc EJ |
64 | &ml->table) { |
65 | if (e->vlan == vlan && eth_addr_equals(e->mac, mac)) { | |
064af421 BP |
66 | return e; |
67 | } | |
68 | } | |
69 | return NULL; | |
70 | } | |
71 | ||
72 | /* If the LRU list is not empty, stores the least-recently-used entry in '*e' | |
73 | * and returns true. Otherwise, if the LRU list is empty, stores NULL in '*e' | |
74 | * and return false. */ | |
75 | static bool | |
76 | get_lru(struct mac_learning *ml, struct mac_entry **e) | |
509c0149 | 77 | OVS_REQ_RDLOCK(ml->rwlock) |
064af421 BP |
78 | { |
79 | if (!list_is_empty(&ml->lrus)) { | |
80 | *e = mac_entry_from_lru_node(ml->lrus.next); | |
81 | return true; | |
82 | } else { | |
83 | *e = NULL; | |
84 | return false; | |
85 | } | |
86 | } | |
87 | ||
e764773c BP |
88 | static unsigned int |
89 | normalize_idle_time(unsigned int idle_time) | |
90 | { | |
91 | return (idle_time < 15 ? 15 | |
92 | : idle_time > 3600 ? 3600 | |
93 | : idle_time); | |
94 | } | |
95 | ||
96 | /* Creates and returns a new MAC learning table with an initial MAC aging | |
c4069512 BP |
97 | * timeout of 'idle_time' seconds and an initial maximum of MAC_DEFAULT_MAX |
98 | * entries. */ | |
064af421 | 99 | struct mac_learning * |
e764773c | 100 | mac_learning_create(unsigned int idle_time) |
064af421 BP |
101 | { |
102 | struct mac_learning *ml; | |
064af421 BP |
103 | |
104 | ml = xmalloc(sizeof *ml); | |
105 | list_init(&ml->lrus); | |
8ea45fdc | 106 | hmap_init(&ml->table); |
064af421 | 107 | ml->secret = random_uint32(); |
8f30d09a | 108 | ml->flood_vlans = NULL; |
e764773c | 109 | ml->idle_time = normalize_idle_time(idle_time); |
c4069512 | 110 | ml->max_entries = MAC_DEFAULT_MAX; |
30618594 | 111 | ml->need_revalidate = false; |
37bec3d3 | 112 | ovs_refcount_init(&ml->ref_cnt); |
509c0149 | 113 | ovs_rwlock_init(&ml->rwlock); |
064af421 BP |
114 | return ml; |
115 | } | |
116 | ||
5d989517 EJ |
117 | struct mac_learning * |
118 | mac_learning_ref(const struct mac_learning *ml_) | |
064af421 | 119 | { |
5d989517 | 120 | struct mac_learning *ml = CONST_CAST(struct mac_learning *, ml_); |
f2d7fd66 | 121 | if (ml) { |
37bec3d3 | 122 | ovs_refcount_ref(&ml->ref_cnt); |
5d989517 EJ |
123 | } |
124 | return ml; | |
125 | } | |
126 | ||
127 | /* Unreferences (and possibly destroys) MAC learning table 'ml'. */ | |
128 | void | |
129 | mac_learning_unref(struct mac_learning *ml) | |
130 | { | |
37bec3d3 | 131 | if (ml && ovs_refcount_unref(&ml->ref_cnt) == 1) { |
16a5d1e4 EJ |
132 | struct mac_entry *e, *next; |
133 | ||
134 | HMAP_FOR_EACH_SAFE (e, next, hmap_node, &ml->table) { | |
135 | hmap_remove(&ml->table, &e->hmap_node); | |
136 | free(e); | |
137 | } | |
8ea45fdc | 138 | hmap_destroy(&ml->table); |
16a5d1e4 | 139 | |
8f30d09a | 140 | bitmap_free(ml->flood_vlans); |
509c0149 | 141 | ovs_rwlock_destroy(&ml->rwlock); |
8e2e7a5d | 142 | free(ml); |
f2d7fd66 | 143 | } |
064af421 BP |
144 | } |
145 | ||
8f30d09a | 146 | /* Provides a bitmap of VLANs which have learning disabled, that is, VLANs on |
2a4ae635 BP |
147 | * which all packets are flooded. Returns true if the set has changed from the |
148 | * previous value. */ | |
f2d7fd66 | 149 | bool |
2a4ae635 BP |
150 | mac_learning_set_flood_vlans(struct mac_learning *ml, |
151 | const unsigned long *bitmap) | |
f2d7fd66 | 152 | { |
2a4ae635 BP |
153 | if (vlan_bitmap_equal(ml->flood_vlans, bitmap)) { |
154 | return false; | |
155 | } else { | |
156 | bitmap_free(ml->flood_vlans); | |
157 | ml->flood_vlans = vlan_bitmap_clone(bitmap); | |
158 | return true; | |
159 | } | |
f2d7fd66 JG |
160 | } |
161 | ||
e764773c BP |
162 | /* Changes the MAC aging timeout of 'ml' to 'idle_time' seconds. */ |
163 | void | |
164 | mac_learning_set_idle_time(struct mac_learning *ml, unsigned int idle_time) | |
165 | { | |
166 | idle_time = normalize_idle_time(idle_time); | |
167 | if (idle_time != ml->idle_time) { | |
168 | struct mac_entry *e; | |
169 | int delta; | |
170 | ||
171 | delta = (int) idle_time - (int) ml->idle_time; | |
172 | LIST_FOR_EACH (e, lru_node, &ml->lrus) { | |
173 | e->expires += delta; | |
174 | } | |
175 | ml->idle_time = idle_time; | |
176 | } | |
177 | } | |
178 | ||
c4069512 BP |
179 | /* Sets the maximum number of entries in 'ml' to 'max_entries', adjusting it |
180 | * to be within a reasonable range. */ | |
181 | void | |
182 | mac_learning_set_max_entries(struct mac_learning *ml, size_t max_entries) | |
183 | { | |
184 | ml->max_entries = (max_entries < 10 ? 10 | |
185 | : max_entries > 1000 * 1000 ? 1000 * 1000 | |
186 | : max_entries); | |
187 | } | |
188 | ||
f2d7fd66 JG |
189 | static bool |
190 | is_learning_vlan(const struct mac_learning *ml, uint16_t vlan) | |
191 | { | |
82062a20 | 192 | return !ml->flood_vlans || !bitmap_is_set(ml->flood_vlans, vlan); |
f2d7fd66 JG |
193 | } |
194 | ||
db8077c3 BP |
195 | /* Returns true if 'src_mac' may be learned on 'vlan' for 'ml'. |
196 | * Returns false if 'ml' is NULL, if src_mac is not valid for learning, or if | |
197 | * 'vlan' is configured on 'ml' to flood all packets. */ | |
198 | bool | |
199 | mac_learning_may_learn(const struct mac_learning *ml, | |
200 | const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan) | |
201 | { | |
202 | return ml && is_learning_vlan(ml, vlan) && !eth_addr_is_multicast(src_mac); | |
203 | } | |
204 | ||
205 | /* Searches 'ml' for and returns a MAC learning entry for 'src_mac' in 'vlan', | |
206 | * inserting a new entry if necessary. The caller must have already verified, | |
207 | * by calling mac_learning_may_learn(), that 'src_mac' and 'vlan' are | |
208 | * learnable. | |
7febb910 | 209 | * |
db8077c3 BP |
210 | * If the returned MAC entry is new (as may be determined by calling |
211 | * mac_entry_is_new()), then the caller must pass the new entry to | |
212 | * mac_learning_changed(). The caller must also initialize the new entry's | |
213 | * 'port' member. Otherwise calling those functions is at the caller's | |
214 | * discretion. */ | |
215 | struct mac_entry * | |
216 | mac_learning_insert(struct mac_learning *ml, | |
217 | const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan) | |
064af421 BP |
218 | { |
219 | struct mac_entry *e; | |
064af421 | 220 | |
8ea45fdc | 221 | e = mac_entry_lookup(ml, src_mac, vlan); |
064af421 | 222 | if (!e) { |
8e8d5966 EJ |
223 | uint32_t hash = mac_table_hash(ml, src_mac, vlan); |
224 | ||
c4069512 | 225 | if (hmap_count(&ml->table) >= ml->max_entries) { |
16a5d1e4 EJ |
226 | get_lru(ml, &e); |
227 | mac_learning_expire(ml, e); | |
064af421 | 228 | } |
8e8d5966 | 229 | |
16a5d1e4 | 230 | e = xmalloc(sizeof *e); |
8e8d5966 | 231 | hmap_insert(&ml->table, &e->hmap_node, hash); |
db8077c3 | 232 | memcpy(e->mac, src_mac, ETH_ADDR_LEN); |
064af421 | 233 | e->vlan = vlan; |
7febb910 | 234 | e->grat_arp_lock = TIME_MIN; |
30618594 | 235 | e->port.p = NULL; |
16a5d1e4 EJ |
236 | } else { |
237 | list_remove(&e->lru_node); | |
064af421 BP |
238 | } |
239 | ||
db8077c3 | 240 | /* Mark 'e' as recently used. */ |
db8077c3 | 241 | list_push_back(&ml->lrus, &e->lru_node); |
e764773c | 242 | e->expires = time_now() + ml->idle_time; |
7febb910 | 243 | |
db8077c3 | 244 | return e; |
064af421 BP |
245 | } |
246 | ||
ae1736c0 EJ |
247 | /* Changes 'e''s tag to a new, randomly selected one. Causes |
248 | * mac_learning_run() to flag for revalidation the tag that would have been | |
249 | * previously used for this entry's MAC and VLAN (either before 'e' was | |
250 | * inserted, if it is new, or otherwise before its port was updated.) | |
db8077c3 BP |
251 | * |
252 | * The client should call this function after obtaining a MAC learning entry | |
253 | * from mac_learning_insert(), if the entry is either new or if its learned | |
254 | * port has changed. */ | |
ae1736c0 | 255 | void |
30618594 | 256 | mac_learning_changed(struct mac_learning *ml) |
064af421 | 257 | { |
db8077c3 | 258 | COVERAGE_INC(mac_learning_learned); |
30618594 | 259 | ml->need_revalidate = true; |
064af421 BP |
260 | } |
261 | ||
db8077c3 BP |
262 | /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml' and returns the associated MAC |
263 | * learning entry, if any. If 'tag' is nonnull, then the tag that associates | |
264 | * 'dst' and 'vlan' with its currently learned port will be OR'd into | |
265 | * '*tag'. */ | |
266 | struct mac_entry * | |
267 | mac_learning_lookup(const struct mac_learning *ml, | |
30618594 | 268 | const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan) |
064af421 | 269 | { |
db8077c3 BP |
270 | if (eth_addr_is_multicast(dst)) { |
271 | /* No tag because the treatment of multicast destinations never | |
272 | * changes. */ | |
273 | return NULL; | |
274 | } else if (!is_learning_vlan(ml, vlan)) { | |
275 | /* We don't tag this property. The set of learning VLANs changes so | |
276 | * rarely that we revalidate every flow when it changes. */ | |
277 | return NULL; | |
064af421 | 278 | } else { |
8ea45fdc EJ |
279 | struct mac_entry *e = mac_entry_lookup(ml, dst, vlan); |
280 | ||
4319a5bc | 281 | ovs_assert(e == NULL || e->port.p != NULL); |
db8077c3 | 282 | return e; |
064af421 BP |
283 | } |
284 | } | |
285 | ||
16a5d1e4 | 286 | /* Expires 'e' from the 'ml' hash table. */ |
356180a8 BP |
287 | void |
288 | mac_learning_expire(struct mac_learning *ml, struct mac_entry *e) | |
289 | { | |
8ea45fdc | 290 | hmap_remove(&ml->table, &e->hmap_node); |
356180a8 | 291 | list_remove(&e->lru_node); |
16a5d1e4 | 292 | free(e); |
356180a8 BP |
293 | } |
294 | ||
d0040604 EJ |
295 | /* Expires all the mac-learning entries in 'ml'. If not NULL, the tags in 'ml' |
296 | * are added to 'tags'. Otherwise the tags in 'ml' are discarded. The client | |
297 | * is responsible for revalidating any flows that depend on 'ml', if | |
298 | * necessary. */ | |
064af421 | 299 | void |
30618594 | 300 | mac_learning_flush(struct mac_learning *ml) |
064af421 BP |
301 | { |
302 | struct mac_entry *e; | |
303 | while (get_lru(ml, &e)){ | |
30618594 | 304 | ml->need_revalidate = true; |
356180a8 | 305 | mac_learning_expire(ml, e); |
064af421 | 306 | } |
16a5d1e4 | 307 | hmap_shrink(&ml->table); |
064af421 BP |
308 | } |
309 | ||
30618594 EJ |
310 | /* Does periodic work required by 'ml'. Returns true if something changed that |
311 | * may require flow revalidation. */ | |
312 | bool | |
313 | mac_learning_run(struct mac_learning *ml) | |
064af421 | 314 | { |
30618594 | 315 | bool need_revalidate; |
064af421 | 316 | struct mac_entry *e; |
ae1736c0 | 317 | |
c4069512 BP |
318 | while (get_lru(ml, &e) |
319 | && (hmap_count(&ml->table) > ml->max_entries | |
320 | || time_now() >= e->expires)) { | |
064af421 | 321 | COVERAGE_INC(mac_learning_expired); |
30618594 | 322 | ml->need_revalidate = true; |
356180a8 | 323 | mac_learning_expire(ml, e); |
064af421 | 324 | } |
30618594 EJ |
325 | |
326 | need_revalidate = ml->need_revalidate; | |
327 | ml->need_revalidate = false; | |
328 | return need_revalidate; | |
064af421 BP |
329 | } |
330 | ||
331 | void | |
332 | mac_learning_wait(struct mac_learning *ml) | |
333 | { | |
ae1736c0 | 334 | if (hmap_count(&ml->table) > ml->max_entries |
30618594 | 335 | || ml->need_revalidate) { |
c4069512 BP |
336 | poll_immediate_wake(); |
337 | } else if (!list_is_empty(&ml->lrus)) { | |
064af421 | 338 | struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next); |
7cf8b266 | 339 | poll_timer_wait_until(e->expires * 1000LL); |
064af421 BP |
340 | } |
341 | } |