]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
db8077c3 | 2 | * Copyright (c) 2008, 2009, 2010, 2011 Nicira Networks. |
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 | ||
20 | #include <assert.h> | |
21 | #include <inttypes.h> | |
22 | #include <stdlib.h> | |
23 | ||
f2d7fd66 | 24 | #include "bitmap.h" |
064af421 BP |
25 | #include "coverage.h" |
26 | #include "hash.h" | |
27 | #include "list.h" | |
28 | #include "poll-loop.h" | |
29 | #include "tag.h" | |
30 | #include "timeval.h" | |
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 | ||
321943f7 BP |
40 | /* Returns the number of seconds since 'e' was last learned. */ |
41 | int | |
42 | mac_entry_age(const struct mac_entry *e) | |
43 | { | |
44 | time_t remaining = e->expires - time_now(); | |
45 | return MAC_ENTRY_IDLE_TIME - remaining; | |
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 | { |
8e8d5966 | 52 | return hash_bytes(mac, ETH_ADDR_LEN, vlan ^ ml->secret); |
064af421 BP |
53 | } |
54 | ||
55 | static struct mac_entry * | |
56 | mac_entry_from_lru_node(struct list *list) | |
57 | { | |
58 | return CONTAINER_OF(list, struct mac_entry, lru_node); | |
59 | } | |
60 | ||
61 | /* Returns a tag that represents that 'mac' is on an unknown port in 'vlan'. | |
62 | * (When we learn where 'mac' is in 'vlan', this allows flows that were | |
63 | * flooded to be revalidated.) */ | |
64 | static tag_type | |
65 | make_unknown_mac_tag(const struct mac_learning *ml, | |
66 | const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) | |
67 | { | |
8e8d5966 | 68 | return tag_create_deterministic(mac_table_hash(ml, mac, vlan)); |
064af421 BP |
69 | } |
70 | ||
064af421 | 71 | static struct mac_entry * |
8ea45fdc EJ |
72 | mac_entry_lookup(const struct mac_learning *ml, |
73 | const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) | |
064af421 BP |
74 | { |
75 | struct mac_entry *e; | |
8ea45fdc | 76 | |
8e8d5966 | 77 | HMAP_FOR_EACH_WITH_HASH (e, hmap_node, mac_table_hash(ml, mac, vlan), |
8ea45fdc EJ |
78 | &ml->table) { |
79 | if (e->vlan == vlan && eth_addr_equals(e->mac, mac)) { | |
064af421 BP |
80 | return e; |
81 | } | |
82 | } | |
83 | return NULL; | |
84 | } | |
85 | ||
86 | /* If the LRU list is not empty, stores the least-recently-used entry in '*e' | |
87 | * and returns true. Otherwise, if the LRU list is empty, stores NULL in '*e' | |
88 | * and return false. */ | |
89 | static bool | |
90 | get_lru(struct mac_learning *ml, struct mac_entry **e) | |
91 | { | |
92 | if (!list_is_empty(&ml->lrus)) { | |
93 | *e = mac_entry_from_lru_node(ml->lrus.next); | |
94 | return true; | |
95 | } else { | |
96 | *e = NULL; | |
97 | return false; | |
98 | } | |
99 | } | |
100 | ||
064af421 BP |
101 | /* Creates and returns a new MAC learning table. */ |
102 | struct mac_learning * | |
103 | mac_learning_create(void) | |
104 | { | |
105 | struct mac_learning *ml; | |
064af421 BP |
106 | |
107 | ml = xmalloc(sizeof *ml); | |
108 | list_init(&ml->lrus); | |
8ea45fdc | 109 | hmap_init(&ml->table); |
064af421 | 110 | ml->secret = random_uint32(); |
8f30d09a | 111 | ml->flood_vlans = NULL; |
064af421 BP |
112 | return ml; |
113 | } | |
114 | ||
115 | /* Destroys MAC learning table 'ml'. */ | |
116 | void | |
117 | mac_learning_destroy(struct mac_learning *ml) | |
118 | { | |
f2d7fd66 | 119 | if (ml) { |
16a5d1e4 EJ |
120 | struct mac_entry *e, *next; |
121 | ||
122 | HMAP_FOR_EACH_SAFE (e, next, hmap_node, &ml->table) { | |
123 | hmap_remove(&ml->table, &e->hmap_node); | |
124 | free(e); | |
125 | } | |
8ea45fdc | 126 | hmap_destroy(&ml->table); |
16a5d1e4 | 127 | |
8f30d09a | 128 | bitmap_free(ml->flood_vlans); |
8e2e7a5d | 129 | free(ml); |
f2d7fd66 | 130 | } |
064af421 BP |
131 | } |
132 | ||
8f30d09a | 133 | /* Provides a bitmap of VLANs which have learning disabled, that is, VLANs on |
2a4ae635 BP |
134 | * which all packets are flooded. Returns true if the set has changed from the |
135 | * previous value. */ | |
f2d7fd66 | 136 | bool |
2a4ae635 BP |
137 | mac_learning_set_flood_vlans(struct mac_learning *ml, |
138 | const unsigned long *bitmap) | |
f2d7fd66 | 139 | { |
2a4ae635 BP |
140 | if (vlan_bitmap_equal(ml->flood_vlans, bitmap)) { |
141 | return false; | |
142 | } else { | |
143 | bitmap_free(ml->flood_vlans); | |
144 | ml->flood_vlans = vlan_bitmap_clone(bitmap); | |
145 | return true; | |
146 | } | |
f2d7fd66 JG |
147 | } |
148 | ||
149 | static bool | |
150 | is_learning_vlan(const struct mac_learning *ml, uint16_t vlan) | |
151 | { | |
0fb7b915 | 152 | return vlan_bitmap_contains(ml->flood_vlans, vlan); |
f2d7fd66 JG |
153 | } |
154 | ||
db8077c3 BP |
155 | /* Returns true if 'src_mac' may be learned on 'vlan' for 'ml'. |
156 | * Returns false if 'ml' is NULL, if src_mac is not valid for learning, or if | |
157 | * 'vlan' is configured on 'ml' to flood all packets. */ | |
158 | bool | |
159 | mac_learning_may_learn(const struct mac_learning *ml, | |
160 | const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan) | |
161 | { | |
162 | return ml && is_learning_vlan(ml, vlan) && !eth_addr_is_multicast(src_mac); | |
163 | } | |
164 | ||
165 | /* Searches 'ml' for and returns a MAC learning entry for 'src_mac' in 'vlan', | |
166 | * inserting a new entry if necessary. The caller must have already verified, | |
167 | * by calling mac_learning_may_learn(), that 'src_mac' and 'vlan' are | |
168 | * learnable. | |
7febb910 | 169 | * |
db8077c3 BP |
170 | * If the returned MAC entry is new (as may be determined by calling |
171 | * mac_entry_is_new()), then the caller must pass the new entry to | |
172 | * mac_learning_changed(). The caller must also initialize the new entry's | |
173 | * 'port' member. Otherwise calling those functions is at the caller's | |
174 | * discretion. */ | |
175 | struct mac_entry * | |
176 | mac_learning_insert(struct mac_learning *ml, | |
177 | const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan) | |
064af421 BP |
178 | { |
179 | struct mac_entry *e; | |
064af421 | 180 | |
8ea45fdc | 181 | e = mac_entry_lookup(ml, src_mac, vlan); |
064af421 | 182 | if (!e) { |
8e8d5966 EJ |
183 | uint32_t hash = mac_table_hash(ml, src_mac, vlan); |
184 | ||
16a5d1e4 EJ |
185 | if (hmap_count(&ml->table) >= MAC_MAX) { |
186 | get_lru(ml, &e); | |
187 | mac_learning_expire(ml, e); | |
064af421 | 188 | } |
8e8d5966 | 189 | |
16a5d1e4 | 190 | e = xmalloc(sizeof *e); |
8e8d5966 | 191 | hmap_insert(&ml->table, &e->hmap_node, hash); |
db8077c3 | 192 | memcpy(e->mac, src_mac, ETH_ADDR_LEN); |
064af421 | 193 | e->vlan = vlan; |
db8077c3 | 194 | e->tag = 0; |
7febb910 | 195 | e->grat_arp_lock = TIME_MIN; |
16a5d1e4 EJ |
196 | } else { |
197 | list_remove(&e->lru_node); | |
064af421 BP |
198 | } |
199 | ||
db8077c3 | 200 | /* Mark 'e' as recently used. */ |
db8077c3 BP |
201 | list_push_back(&ml->lrus, &e->lru_node); |
202 | e->expires = time_now() + MAC_ENTRY_IDLE_TIME; | |
7febb910 | 203 | |
db8077c3 | 204 | return e; |
064af421 BP |
205 | } |
206 | ||
db8077c3 BP |
207 | /* Changes 'e''s tag to a new, randomly selected one, and returns the tag that |
208 | * would have been previously used for this entry's MAC and VLAN (either before | |
209 | * 'e' was inserted, if it is new, or otherwise before its port was updated.) | |
210 | * | |
211 | * The client should call this function after obtaining a MAC learning entry | |
212 | * from mac_learning_insert(), if the entry is either new or if its learned | |
213 | * port has changed. */ | |
214 | tag_type | |
215 | mac_learning_changed(struct mac_learning *ml, struct mac_entry *e) | |
064af421 | 216 | { |
db8077c3 BP |
217 | tag_type old_tag = e->tag; |
218 | ||
219 | COVERAGE_INC(mac_learning_learned); | |
220 | ||
221 | e->tag = tag_create_random(); | |
222 | return old_tag ? old_tag : make_unknown_mac_tag(ml, e->mac, e->vlan); | |
064af421 BP |
223 | } |
224 | ||
db8077c3 BP |
225 | /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml' and returns the associated MAC |
226 | * learning entry, if any. If 'tag' is nonnull, then the tag that associates | |
227 | * 'dst' and 'vlan' with its currently learned port will be OR'd into | |
228 | * '*tag'. */ | |
229 | struct mac_entry * | |
230 | mac_learning_lookup(const struct mac_learning *ml, | |
231 | const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan, | |
232 | tag_type *tag) | |
064af421 | 233 | { |
db8077c3 BP |
234 | if (eth_addr_is_multicast(dst)) { |
235 | /* No tag because the treatment of multicast destinations never | |
236 | * changes. */ | |
237 | return NULL; | |
238 | } else if (!is_learning_vlan(ml, vlan)) { | |
239 | /* We don't tag this property. The set of learning VLANs changes so | |
240 | * rarely that we revalidate every flow when it changes. */ | |
241 | return NULL; | |
064af421 | 242 | } else { |
8ea45fdc EJ |
243 | struct mac_entry *e = mac_entry_lookup(ml, dst, vlan); |
244 | ||
db8077c3 BP |
245 | assert(e == NULL || e->tag != 0); |
246 | if (tag) { | |
247 | /* Tag either the learned port or the lack thereof. */ | |
248 | *tag |= e ? e->tag : make_unknown_mac_tag(ml, dst, vlan); | |
064af421 | 249 | } |
db8077c3 | 250 | return e; |
064af421 BP |
251 | } |
252 | } | |
253 | ||
16a5d1e4 | 254 | /* Expires 'e' from the 'ml' hash table. */ |
356180a8 BP |
255 | void |
256 | mac_learning_expire(struct mac_learning *ml, struct mac_entry *e) | |
257 | { | |
8ea45fdc | 258 | hmap_remove(&ml->table, &e->hmap_node); |
356180a8 | 259 | list_remove(&e->lru_node); |
16a5d1e4 | 260 | free(e); |
356180a8 BP |
261 | } |
262 | ||
064af421 BP |
263 | /* Expires all the mac-learning entries in 'ml'. The tags in 'ml' are |
264 | * discarded, so the client is responsible for revalidating any flows that | |
265 | * depend on 'ml', if necessary. */ | |
266 | void | |
267 | mac_learning_flush(struct mac_learning *ml) | |
268 | { | |
269 | struct mac_entry *e; | |
270 | while (get_lru(ml, &e)){ | |
356180a8 | 271 | mac_learning_expire(ml, e); |
064af421 | 272 | } |
16a5d1e4 | 273 | hmap_shrink(&ml->table); |
064af421 BP |
274 | } |
275 | ||
276 | void | |
277 | mac_learning_run(struct mac_learning *ml, struct tag_set *set) | |
278 | { | |
279 | struct mac_entry *e; | |
280 | while (get_lru(ml, &e) && time_now() >= e->expires) { | |
281 | COVERAGE_INC(mac_learning_expired); | |
282 | if (set) { | |
283 | tag_set_add(set, e->tag); | |
284 | } | |
356180a8 | 285 | mac_learning_expire(ml, e); |
064af421 BP |
286 | } |
287 | } | |
288 | ||
289 | void | |
290 | mac_learning_wait(struct mac_learning *ml) | |
291 | { | |
292 | if (!list_is_empty(&ml->lrus)) { | |
293 | struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next); | |
7cf8b266 | 294 | poll_timer_wait_until(e->expires * 1000LL); |
064af421 BP |
295 | } |
296 | } |