]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
8f30d09a | 2 | * Copyright (c) 2008, 2009, 2010 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" | |
064af421 BP |
32 | #include "vlog.h" |
33 | ||
d98e6007 | 34 | VLOG_DEFINE_THIS_MODULE(mac_learning); |
5136ce49 | 35 | |
321943f7 BP |
36 | /* Returns the number of seconds since 'e' was last learned. */ |
37 | int | |
38 | mac_entry_age(const struct mac_entry *e) | |
39 | { | |
40 | time_t remaining = e->expires - time_now(); | |
41 | return MAC_ENTRY_IDLE_TIME - remaining; | |
42 | } | |
43 | ||
064af421 BP |
44 | static uint32_t |
45 | mac_table_hash(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) | |
46 | { | |
47 | return hash_bytes(mac, ETH_ADDR_LEN, vlan); | |
48 | } | |
49 | ||
50 | static struct mac_entry * | |
51 | mac_entry_from_lru_node(struct list *list) | |
52 | { | |
53 | return CONTAINER_OF(list, struct mac_entry, lru_node); | |
54 | } | |
55 | ||
56 | /* Returns a tag that represents that 'mac' is on an unknown port in 'vlan'. | |
57 | * (When we learn where 'mac' is in 'vlan', this allows flows that were | |
58 | * flooded to be revalidated.) */ | |
59 | static tag_type | |
60 | make_unknown_mac_tag(const struct mac_learning *ml, | |
61 | const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) | |
62 | { | |
63 | uint32_t h = hash_int(ml->secret, mac_table_hash(mac, vlan)); | |
64 | return tag_create_deterministic(h); | |
65 | } | |
66 | ||
67 | static struct list * | |
68 | mac_table_bucket(const struct mac_learning *ml, | |
69 | const uint8_t mac[ETH_ADDR_LEN], | |
70 | uint16_t vlan) | |
71 | { | |
72 | uint32_t hash = mac_table_hash(mac, vlan); | |
73 | const struct list *list = &ml->table[hash & MAC_HASH_BITS]; | |
74 | return (struct list *) list; | |
75 | } | |
76 | ||
77 | static struct mac_entry * | |
78 | search_bucket(struct list *bucket, const uint8_t mac[ETH_ADDR_LEN], | |
79 | uint16_t vlan) | |
80 | { | |
81 | struct mac_entry *e; | |
4e8e4213 | 82 | LIST_FOR_EACH (e, hash_node, bucket) { |
064af421 BP |
83 | if (eth_addr_equals(e->mac, mac) && e->vlan == vlan) { |
84 | return e; | |
85 | } | |
86 | } | |
87 | return NULL; | |
88 | } | |
89 | ||
90 | /* If the LRU list is not empty, stores the least-recently-used entry in '*e' | |
91 | * and returns true. Otherwise, if the LRU list is empty, stores NULL in '*e' | |
92 | * and return false. */ | |
93 | static bool | |
94 | get_lru(struct mac_learning *ml, struct mac_entry **e) | |
95 | { | |
96 | if (!list_is_empty(&ml->lrus)) { | |
97 | *e = mac_entry_from_lru_node(ml->lrus.next); | |
98 | return true; | |
99 | } else { | |
100 | *e = NULL; | |
101 | return false; | |
102 | } | |
103 | } | |
104 | ||
105 | /* Removes 'e' from the 'ml' hash table. 'e' must not already be on the free | |
106 | * list. */ | |
107 | static void | |
108 | free_mac_entry(struct mac_learning *ml, struct mac_entry *e) | |
109 | { | |
110 | list_remove(&e->hash_node); | |
111 | list_remove(&e->lru_node); | |
112 | list_push_front(&ml->free, &e->lru_node); | |
113 | } | |
114 | ||
115 | /* Creates and returns a new MAC learning table. */ | |
116 | struct mac_learning * | |
117 | mac_learning_create(void) | |
118 | { | |
119 | struct mac_learning *ml; | |
120 | int i; | |
121 | ||
122 | ml = xmalloc(sizeof *ml); | |
123 | list_init(&ml->lrus); | |
124 | list_init(&ml->free); | |
125 | for (i = 0; i < MAC_HASH_SIZE; i++) { | |
126 | list_init(&ml->table[i]); | |
127 | } | |
128 | for (i = 0; i < MAC_MAX; i++) { | |
129 | struct mac_entry *s = &ml->entries[i]; | |
130 | list_push_front(&ml->free, &s->lru_node); | |
131 | } | |
132 | ml->secret = random_uint32(); | |
8f30d09a | 133 | ml->flood_vlans = NULL; |
064af421 BP |
134 | return ml; |
135 | } | |
136 | ||
137 | /* Destroys MAC learning table 'ml'. */ | |
138 | void | |
139 | mac_learning_destroy(struct mac_learning *ml) | |
140 | { | |
f2d7fd66 | 141 | if (ml) { |
8f30d09a | 142 | bitmap_free(ml->flood_vlans); |
f2d7fd66 | 143 | } |
064af421 BP |
144 | free(ml); |
145 | } | |
146 | ||
8f30d09a BP |
147 | /* Provides a bitmap of VLANs which have learning disabled, that is, VLANs on |
148 | * which all packets are flooded. It takes ownership of the bitmap. Returns | |
149 | * true if the set has changed from the previous value. */ | |
f2d7fd66 | 150 | bool |
8f30d09a | 151 | mac_learning_set_flood_vlans(struct mac_learning *ml, unsigned long *bitmap) |
f2d7fd66 JG |
152 | { |
153 | bool ret = (bitmap == NULL | |
8f30d09a BP |
154 | ? ml->flood_vlans != NULL |
155 | : (ml->flood_vlans == NULL | |
156 | || !bitmap_equal(bitmap, ml->flood_vlans, 4096))); | |
f2d7fd66 | 157 | |
8f30d09a BP |
158 | bitmap_free(ml->flood_vlans); |
159 | ml->flood_vlans = bitmap; | |
f2d7fd66 JG |
160 | |
161 | return ret; | |
162 | } | |
163 | ||
164 | static bool | |
165 | is_learning_vlan(const struct mac_learning *ml, uint16_t vlan) | |
166 | { | |
8f30d09a | 167 | return !(ml->flood_vlans && bitmap_is_set(ml->flood_vlans, vlan)); |
f2d7fd66 JG |
168 | } |
169 | ||
064af421 BP |
170 | /* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was |
171 | * just observed arriving from 'src_port' on the given 'vlan'. | |
172 | * | |
173 | * Returns nonzero if we actually learned something from this, zero if it just | |
174 | * confirms what we already knew. The nonzero return value is the tag of flows | |
175 | * that now need revalidation. | |
176 | * | |
177 | * The 'vlan' parameter is used to maintain separate per-VLAN learning tables. | |
7febb910 JG |
178 | * Specify 0 if this behavior is undesirable. |
179 | * | |
180 | * 'lock_type' specifies whether the entry should be locked or existing locks | |
181 | * are check. */ | |
064af421 BP |
182 | tag_type |
183 | mac_learning_learn(struct mac_learning *ml, | |
184 | const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan, | |
7febb910 | 185 | uint16_t src_port, enum grat_arp_lock_type lock_type) |
064af421 BP |
186 | { |
187 | struct mac_entry *e; | |
188 | struct list *bucket; | |
189 | ||
f2d7fd66 JG |
190 | if (!is_learning_vlan(ml, vlan)) { |
191 | return 0; | |
192 | } | |
193 | ||
064af421 BP |
194 | if (eth_addr_is_multicast(src_mac)) { |
195 | static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 30); | |
196 | VLOG_DBG_RL(&rl, "multicast packet source "ETH_ADDR_FMT, | |
197 | ETH_ADDR_ARGS(src_mac)); | |
198 | return 0; | |
199 | } | |
200 | ||
201 | bucket = mac_table_bucket(ml, src_mac, vlan); | |
202 | e = search_bucket(bucket, src_mac, vlan); | |
203 | if (!e) { | |
204 | if (!list_is_empty(&ml->free)) { | |
205 | e = mac_entry_from_lru_node(ml->free.next); | |
206 | } else { | |
207 | e = mac_entry_from_lru_node(ml->lrus.next); | |
208 | list_remove(&e->hash_node); | |
209 | } | |
210 | memcpy(e->mac, src_mac, ETH_ADDR_LEN); | |
211 | list_push_front(bucket, &e->hash_node); | |
212 | e->port = -1; | |
213 | e->vlan = vlan; | |
214 | e->tag = make_unknown_mac_tag(ml, src_mac, vlan); | |
7febb910 | 215 | e->grat_arp_lock = TIME_MIN; |
064af421 BP |
216 | } |
217 | ||
7febb910 JG |
218 | if (lock_type != GRAT_ARP_LOCK_CHECK || time_now() >= e->grat_arp_lock) { |
219 | /* Make the entry most-recently-used. */ | |
220 | list_remove(&e->lru_node); | |
221 | list_push_back(&ml->lrus, &e->lru_node); | |
222 | e->expires = time_now() + MAC_ENTRY_IDLE_TIME; | |
223 | if (lock_type == GRAT_ARP_LOCK_SET) { | |
224 | e->grat_arp_lock = time_now() + MAC_GRAT_ARP_LOCK_TIME; | |
225 | } | |
226 | ||
227 | /* Did we learn something? */ | |
228 | if (e->port != src_port) { | |
229 | tag_type old_tag = e->tag; | |
230 | e->port = src_port; | |
231 | e->tag = tag_create_random(); | |
232 | COVERAGE_INC(mac_learning_learned); | |
233 | return old_tag; | |
234 | } | |
064af421 | 235 | } |
7febb910 | 236 | |
064af421 BP |
237 | return 0; |
238 | } | |
239 | ||
240 | /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'. Returns the port on which a | |
7febb910 JG |
241 | * frame destined for 'dst' should be sent, -1 if unknown. 'is_grat_arp_locked' |
242 | * is an optional parameter that returns whether the entry is currently | |
243 | * locked. */ | |
064af421 BP |
244 | int |
245 | mac_learning_lookup(const struct mac_learning *ml, | |
7febb910 JG |
246 | const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan, |
247 | bool *is_grat_arp_locked) | |
064af421 BP |
248 | { |
249 | tag_type tag = 0; | |
7febb910 | 250 | return mac_learning_lookup_tag(ml, dst, vlan, &tag, is_grat_arp_locked); |
064af421 BP |
251 | } |
252 | ||
253 | /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'. Returns the port on which a | |
254 | * frame destined for 'dst' should be sent, -1 if unknown. | |
255 | * | |
256 | * Adds to '*tag' (which the caller must have initialized) the tag that should | |
257 | * be attached to any flow created based on the return value, if any, to allow | |
7febb910 JG |
258 | * those flows to be revalidated when the MAC learning entry changes. |
259 | * | |
260 | * 'is_grat_arp_locked' is an optional parameter that returns whether the entry | |
261 | * is currently locked.*/ | |
064af421 BP |
262 | int |
263 | mac_learning_lookup_tag(const struct mac_learning *ml, | |
264 | const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan, | |
7febb910 | 265 | tag_type *tag, bool *is_grat_arp_locked) |
064af421 | 266 | { |
f2d7fd66 | 267 | if (eth_addr_is_multicast(dst) || !is_learning_vlan(ml, vlan)) { |
064af421 BP |
268 | return -1; |
269 | } else { | |
270 | struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst, vlan), | |
271 | dst, vlan); | |
272 | if (e) { | |
273 | *tag |= e->tag; | |
7febb910 JG |
274 | |
275 | if (is_grat_arp_locked) { | |
276 | *is_grat_arp_locked = time_now() < e->grat_arp_lock; | |
277 | } | |
278 | ||
064af421 BP |
279 | return e->port; |
280 | } else { | |
281 | *tag |= make_unknown_mac_tag(ml, dst, vlan); | |
282 | return -1; | |
283 | } | |
284 | } | |
285 | } | |
286 | ||
287 | /* Expires all the mac-learning entries in 'ml'. The tags in 'ml' are | |
288 | * discarded, so the client is responsible for revalidating any flows that | |
289 | * depend on 'ml', if necessary. */ | |
290 | void | |
291 | mac_learning_flush(struct mac_learning *ml) | |
292 | { | |
293 | struct mac_entry *e; | |
294 | while (get_lru(ml, &e)){ | |
295 | free_mac_entry(ml, e); | |
296 | } | |
297 | } | |
298 | ||
299 | void | |
300 | mac_learning_run(struct mac_learning *ml, struct tag_set *set) | |
301 | { | |
302 | struct mac_entry *e; | |
303 | while (get_lru(ml, &e) && time_now() >= e->expires) { | |
304 | COVERAGE_INC(mac_learning_expired); | |
305 | if (set) { | |
306 | tag_set_add(set, e->tag); | |
307 | } | |
308 | free_mac_entry(ml, e); | |
309 | } | |
310 | } | |
311 | ||
312 | void | |
313 | mac_learning_wait(struct mac_learning *ml) | |
314 | { | |
315 | if (!list_is_empty(&ml->lrus)) { | |
316 | struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next); | |
7cf8b266 | 317 | poll_timer_wait_until(e->expires * 1000LL); |
064af421 BP |
318 | } |
319 | } |