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