ovsdb-tool: Add commands for printing the database checksum.
[openvswitch] / lib / mac-learning.c
1 /*
2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
3  *
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:
7  *
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.
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
24 #include "bitmap.h"
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"
32 #include "vlog.h"
33
34 VLOG_DEFINE_THIS_MODULE(mac_learning);
35
36 COVERAGE_DEFINE(mac_learning_learned);
37 COVERAGE_DEFINE(mac_learning_expired);
38
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
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;
85     LIST_FOR_EACH (e, hash_node, bucket) {
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();
136     ml->flood_vlans = NULL;
137     return ml;
138 }
139
140 /* Destroys MAC learning table 'ml'. */
141 void
142 mac_learning_destroy(struct mac_learning *ml)
143 {
144     if (ml) {
145         bitmap_free(ml->flood_vlans);
146     }
147     free(ml);
148 }
149
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. */
153 bool
154 mac_learning_set_flood_vlans(struct mac_learning *ml, unsigned long *bitmap)
155 {
156     bool ret = (bitmap == NULL
157                 ? ml->flood_vlans != NULL
158                 : (ml->flood_vlans == NULL
159                    || !bitmap_equal(bitmap, ml->flood_vlans, 4096)));
160
161     bitmap_free(ml->flood_vlans);
162     ml->flood_vlans = bitmap;
163
164     return ret;
165 }
166
167 static bool
168 is_learning_vlan(const struct mac_learning *ml, uint16_t vlan)
169 {
170     return !(ml->flood_vlans && bitmap_is_set(ml->flood_vlans, vlan));
171 }
172
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.
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. */
185 tag_type
186 mac_learning_learn(struct mac_learning *ml,
187                    const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan,
188                    uint16_t src_port, enum grat_arp_lock_type lock_type)
189 {
190     struct mac_entry *e;
191     struct list *bucket;
192
193     if (!is_learning_vlan(ml, vlan)) {
194         return 0;
195     }
196
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);
218         e->grat_arp_lock = TIME_MIN;
219     }
220
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         }
238     }
239
240     return 0;
241 }
242
243 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
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. */
247 int
248 mac_learning_lookup(const struct mac_learning *ml,
249                     const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan,
250                     bool *is_grat_arp_locked)
251 {
252     tag_type tag = 0;
253     return mac_learning_lookup_tag(ml, dst, vlan, &tag, is_grat_arp_locked);
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
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.*/
265 int
266 mac_learning_lookup_tag(const struct mac_learning *ml,
267                         const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan,
268                         tag_type *tag, bool *is_grat_arp_locked)
269 {
270     if (eth_addr_is_multicast(dst) || !is_learning_vlan(ml, vlan)) {
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;
277
278             if (is_grat_arp_locked) {
279                 *is_grat_arp_locked = time_now() < e->grat_arp_lock;
280             }
281
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);
320         poll_timer_wait_until(e->expires * 1000LL);
321     }
322 }