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