]>
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; |
064af421 BP |
126 | return ml; |
127 | } | |
128 | ||
129 | /* Destroys MAC learning table 'ml'. */ | |
130 | void | |
131 | mac_learning_destroy(struct mac_learning *ml) | |
132 | { | |
f2d7fd66 | 133 | if (ml) { |
16a5d1e4 EJ |
134 | struct mac_entry *e, *next; |
135 | ||
136 | HMAP_FOR_EACH_SAFE (e, next, hmap_node, &ml->table) { | |
137 | hmap_remove(&ml->table, &e->hmap_node); | |
138 | free(e); | |
139 | } | |
8ea45fdc | 140 | hmap_destroy(&ml->table); |
16a5d1e4 | 141 | |
8f30d09a | 142 | bitmap_free(ml->flood_vlans); |
8e2e7a5d | 143 | free(ml); |
f2d7fd66 | 144 | } |
064af421 BP |
145 | } |
146 | ||
8f30d09a | 147 | /* Provides a bitmap of VLANs which have learning disabled, that is, VLANs on |
2a4ae635 BP |
148 | * which all packets are flooded. Returns true if the set has changed from the |
149 | * previous value. */ | |
f2d7fd66 | 150 | bool |
2a4ae635 BP |
151 | mac_learning_set_flood_vlans(struct mac_learning *ml, |
152 | const unsigned long *bitmap) | |
f2d7fd66 | 153 | { |
2a4ae635 BP |
154 | if (vlan_bitmap_equal(ml->flood_vlans, bitmap)) { |
155 | return false; | |
156 | } else { | |
157 | bitmap_free(ml->flood_vlans); | |
158 | ml->flood_vlans = vlan_bitmap_clone(bitmap); | |
159 | return true; | |
160 | } | |
f2d7fd66 JG |
161 | } |
162 | ||
e764773c BP |
163 | /* Changes the MAC aging timeout of 'ml' to 'idle_time' seconds. */ |
164 | void | |
165 | mac_learning_set_idle_time(struct mac_learning *ml, unsigned int idle_time) | |
166 | { | |
167 | idle_time = normalize_idle_time(idle_time); | |
168 | if (idle_time != ml->idle_time) { | |
169 | struct mac_entry *e; | |
170 | int delta; | |
171 | ||
172 | delta = (int) idle_time - (int) ml->idle_time; | |
173 | LIST_FOR_EACH (e, lru_node, &ml->lrus) { | |
174 | e->expires += delta; | |
175 | } | |
176 | ml->idle_time = idle_time; | |
177 | } | |
178 | } | |
179 | ||
c4069512 BP |
180 | /* Sets the maximum number of entries in 'ml' to 'max_entries', adjusting it |
181 | * to be within a reasonable range. */ | |
182 | void | |
183 | mac_learning_set_max_entries(struct mac_learning *ml, size_t max_entries) | |
184 | { | |
185 | ml->max_entries = (max_entries < 10 ? 10 | |
186 | : max_entries > 1000 * 1000 ? 1000 * 1000 | |
187 | : max_entries); | |
188 | } | |
189 | ||
f2d7fd66 JG |
190 | static bool |
191 | is_learning_vlan(const struct mac_learning *ml, uint16_t vlan) | |
192 | { | |
82062a20 | 193 | return !ml->flood_vlans || !bitmap_is_set(ml->flood_vlans, vlan); |
f2d7fd66 JG |
194 | } |
195 | ||
db8077c3 BP |
196 | /* Returns true if 'src_mac' may be learned on 'vlan' for 'ml'. |
197 | * Returns false if 'ml' is NULL, if src_mac is not valid for learning, or if | |
198 | * 'vlan' is configured on 'ml' to flood all packets. */ | |
199 | bool | |
200 | mac_learning_may_learn(const struct mac_learning *ml, | |
201 | const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan) | |
202 | { | |
203 | return ml && is_learning_vlan(ml, vlan) && !eth_addr_is_multicast(src_mac); | |
204 | } | |
205 | ||
206 | /* Searches 'ml' for and returns a MAC learning entry for 'src_mac' in 'vlan', | |
207 | * inserting a new entry if necessary. The caller must have already verified, | |
208 | * by calling mac_learning_may_learn(), that 'src_mac' and 'vlan' are | |
209 | * learnable. | |
7febb910 | 210 | * |
db8077c3 BP |
211 | * If the returned MAC entry is new (as may be determined by calling |
212 | * mac_entry_is_new()), then the caller must pass the new entry to | |
213 | * mac_learning_changed(). The caller must also initialize the new entry's | |
214 | * 'port' member. Otherwise calling those functions is at the caller's | |
215 | * discretion. */ | |
216 | struct mac_entry * | |
217 | mac_learning_insert(struct mac_learning *ml, | |
218 | const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan) | |
064af421 BP |
219 | { |
220 | struct mac_entry *e; | |
064af421 | 221 | |
8ea45fdc | 222 | e = mac_entry_lookup(ml, src_mac, vlan); |
064af421 | 223 | if (!e) { |
8e8d5966 EJ |
224 | uint32_t hash = mac_table_hash(ml, src_mac, vlan); |
225 | ||
c4069512 | 226 | if (hmap_count(&ml->table) >= ml->max_entries) { |
16a5d1e4 EJ |
227 | get_lru(ml, &e); |
228 | mac_learning_expire(ml, e); | |
064af421 | 229 | } |
8e8d5966 | 230 | |
16a5d1e4 | 231 | e = xmalloc(sizeof *e); |
8e8d5966 | 232 | hmap_insert(&ml->table, &e->hmap_node, hash); |
db8077c3 | 233 | memcpy(e->mac, src_mac, ETH_ADDR_LEN); |
064af421 | 234 | e->vlan = vlan; |
db8077c3 | 235 | e->tag = 0; |
7febb910 | 236 | e->grat_arp_lock = TIME_MIN; |
16a5d1e4 EJ |
237 | } else { |
238 | list_remove(&e->lru_node); | |
064af421 BP |
239 | } |
240 | ||
db8077c3 | 241 | /* Mark 'e' as recently used. */ |
db8077c3 | 242 | list_push_back(&ml->lrus, &e->lru_node); |
e764773c | 243 | e->expires = time_now() + ml->idle_time; |
7febb910 | 244 | |
db8077c3 | 245 | return e; |
064af421 BP |
246 | } |
247 | ||
db8077c3 BP |
248 | /* Changes 'e''s tag to a new, randomly selected one, and returns the tag that |
249 | * would have been previously used for this entry's MAC and VLAN (either before | |
250 | * 'e' was inserted, if it is new, or otherwise before its port was updated.) | |
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. */ | |
255 | tag_type | |
256 | mac_learning_changed(struct mac_learning *ml, struct mac_entry *e) | |
064af421 | 257 | { |
db8077c3 BP |
258 | tag_type old_tag = e->tag; |
259 | ||
260 | COVERAGE_INC(mac_learning_learned); | |
261 | ||
262 | e->tag = tag_create_random(); | |
263 | return old_tag ? old_tag : make_unknown_mac_tag(ml, e->mac, e->vlan); | |
064af421 BP |
264 | } |
265 | ||
db8077c3 BP |
266 | /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml' and returns the associated MAC |
267 | * learning entry, if any. If 'tag' is nonnull, then the tag that associates | |
268 | * 'dst' and 'vlan' with its currently learned port will be OR'd into | |
269 | * '*tag'. */ | |
270 | struct mac_entry * | |
271 | mac_learning_lookup(const struct mac_learning *ml, | |
272 | const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan, | |
273 | tag_type *tag) | |
064af421 | 274 | { |
db8077c3 BP |
275 | if (eth_addr_is_multicast(dst)) { |
276 | /* No tag because the treatment of multicast destinations never | |
277 | * changes. */ | |
278 | return NULL; | |
279 | } else if (!is_learning_vlan(ml, vlan)) { | |
280 | /* We don't tag this property. The set of learning VLANs changes so | |
281 | * rarely that we revalidate every flow when it changes. */ | |
282 | return NULL; | |
064af421 | 283 | } else { |
8ea45fdc EJ |
284 | struct mac_entry *e = mac_entry_lookup(ml, dst, vlan); |
285 | ||
cb22974d | 286 | ovs_assert(e == NULL || e->tag != 0); |
db8077c3 BP |
287 | if (tag) { |
288 | /* Tag either the learned port or the lack thereof. */ | |
289 | *tag |= e ? e->tag : make_unknown_mac_tag(ml, dst, vlan); | |
064af421 | 290 | } |
db8077c3 | 291 | return e; |
064af421 BP |
292 | } |
293 | } | |
294 | ||
16a5d1e4 | 295 | /* Expires 'e' from the 'ml' hash table. */ |
356180a8 BP |
296 | void |
297 | mac_learning_expire(struct mac_learning *ml, struct mac_entry *e) | |
298 | { | |
8ea45fdc | 299 | hmap_remove(&ml->table, &e->hmap_node); |
356180a8 | 300 | list_remove(&e->lru_node); |
16a5d1e4 | 301 | free(e); |
356180a8 BP |
302 | } |
303 | ||
d0040604 EJ |
304 | /* Expires all the mac-learning entries in 'ml'. If not NULL, the tags in 'ml' |
305 | * are added to 'tags'. Otherwise the tags in 'ml' are discarded. The client | |
306 | * is responsible for revalidating any flows that depend on 'ml', if | |
307 | * necessary. */ | |
064af421 | 308 | void |
d0040604 | 309 | mac_learning_flush(struct mac_learning *ml, struct tag_set *tags) |
064af421 BP |
310 | { |
311 | struct mac_entry *e; | |
312 | while (get_lru(ml, &e)){ | |
d0040604 EJ |
313 | if (tags) { |
314 | tag_set_add(tags, e->tag); | |
315 | } | |
356180a8 | 316 | mac_learning_expire(ml, e); |
064af421 | 317 | } |
16a5d1e4 | 318 | hmap_shrink(&ml->table); |
064af421 BP |
319 | } |
320 | ||
321 | void | |
322 | mac_learning_run(struct mac_learning *ml, struct tag_set *set) | |
323 | { | |
324 | struct mac_entry *e; | |
c4069512 BP |
325 | while (get_lru(ml, &e) |
326 | && (hmap_count(&ml->table) > ml->max_entries | |
327 | || time_now() >= e->expires)) { | |
064af421 BP |
328 | COVERAGE_INC(mac_learning_expired); |
329 | if (set) { | |
330 | tag_set_add(set, e->tag); | |
331 | } | |
356180a8 | 332 | mac_learning_expire(ml, e); |
064af421 BP |
333 | } |
334 | } | |
335 | ||
336 | void | |
337 | mac_learning_wait(struct mac_learning *ml) | |
338 | { | |
c4069512 BP |
339 | if (hmap_count(&ml->table) > ml->max_entries) { |
340 | poll_immediate_wake(); | |
341 | } else if (!list_is_empty(&ml->lrus)) { | |
064af421 | 342 | struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next); |
7cf8b266 | 343 | poll_timer_wait_until(e->expires * 1000LL); |
064af421 BP |
344 | } |
345 | } |