1 /* Copyright (c) 2008 The Board of Trustees of The Leland Stanford
4 * We are making the OpenFlow specification and associated documentation
5 * (Software) available for public use and benefit with the expectation
6 * that others will use, modify and enhance the Software and contribute
7 * those enhancements back to the community. However, since we would
8 * like to make the Software available for broadest use, with as few
9 * restrictions as possible permission is hereby granted, free of
10 * charge, to any person obtaining a copy of this Software to deal in
11 * the Software under the copyrights without restriction, including
12 * without limitation the rights to use, copy, modify, merge, publish,
13 * distribute, sublicense, and/or sell copies of the Software, and to
14 * permit persons to whom the Software is furnished to do so, subject to
15 * the following conditions:
17 * The above copyright notice and this permission notice shall be
18 * included in all copies or substantial portions of the Software.
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
24 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
25 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
26 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
29 * The name and trademarks of copyright holder(s) may NOT be used in
30 * advertising or publicity pertaining to the Software or any
31 * derivatives without specific, written prior permission.
35 #include "mac-learning.h"
46 #define THIS_MODULE VLM_mac_learning
49 #define MAC_HASH_BITS 10
50 #define MAC_HASH_MASK (MAC_HASH_SIZE - 1)
51 #define MAC_HASH_SIZE (1u << MAC_HASH_BITS)
55 /* A MAC learning table entry. */
57 struct list hash_node; /* Element in a mac_learning 'table' list. */
58 struct list lru_node; /* Element in mac_learning 'lrus' list. */
59 uint8_t mac[ETH_ADDR_LEN]; /* Known MAC address. */
60 uint16_t port; /* Port on which MAC was most recently seen. */
63 /* MAC learning table. */
65 struct list lrus; /* All entries, least recently used at the
66 front, most recently used at the back. */
67 struct list table[MAC_HASH_SIZE]; /* Hash table. */
68 struct mac_entry entries[MAC_MAX]; /* All entries. */
72 mac_table_bucket(const struct mac_learning *ml,
73 const uint8_t mac[ETH_ADDR_LEN])
75 uint32_t hash = hash_fnv(mac, ETH_ADDR_LEN, HASH_FNV_BASIS);
76 const struct list *list = &ml->table[hash & MAC_HASH_BITS];
77 return (struct list *) list;
80 static struct mac_entry *
81 search_bucket(struct list *bucket, const uint8_t mac[ETH_ADDR_LEN])
84 LIST_FOR_EACH (e, struct mac_entry, hash_node, bucket) {
85 if (eth_addr_equals(e->mac, mac)) {
92 /* Creates and returns a new MAC learning table. */
94 mac_learning_create(void)
96 struct mac_learning *ml;
99 ml = xmalloc(sizeof *ml);
100 list_init(&ml->lrus);
101 for (i = 0; i < MAC_HASH_SIZE; i++) {
102 list_init(&ml->table[i]);
104 for (i = 0; i < MAC_MAX; i++) {
105 struct mac_entry *s = &ml->entries[i];
106 list_push_front(&ml->lrus, &s->lru_node);
107 s->hash_node.next = NULL;
112 /* Destroys MAC learning table 'ml'. */
114 mac_learning_destroy(struct mac_learning *ml)
119 /* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was
120 * just observed arriving on 'src_port'. Returns true if we actually learned
121 * something from this, false if it just confirms what we already knew. */
123 mac_learning_learn(struct mac_learning *ml,
124 const uint8_t src_mac[ETH_ADDR_LEN], uint16_t src_port)
129 assert(src_port != OFPP_FLOOD);
130 if (eth_addr_is_multicast(src_mac)) {
131 VLOG_DBG("multicast packet source "ETH_ADDR_FMT,
132 ETH_ADDR_ARGS(src_mac));
136 bucket = mac_table_bucket(ml, src_mac);
137 e = search_bucket(bucket, src_mac);
139 /* Make 'e' most-recently-used. */
140 list_remove(&e->lru_node);
141 list_push_back(&ml->lrus, &e->lru_node);
142 if (e->port == src_port) {
146 /* Learn a new address.
147 * First drop the least recently used mac source. */
148 e = CONTAINER_OF(ml->lrus.next, struct mac_entry, lru_node);
149 if (e->hash_node.next) {
150 list_remove(&e->hash_node);
152 list_remove(&e->lru_node);
154 /* Create new mac source. */
155 memcpy(e->mac, src_mac, ETH_ADDR_LEN);
156 list_push_front(bucket, &e->hash_node);
157 list_push_back(&ml->lrus, &e->lru_node);
163 /* Looks up address 'dst' in 'ml'. Returns the port on which a frame destined
164 * for 'dst' should be sent, OFPP_FLOOD if unknown. */
166 mac_learning_lookup(const struct mac_learning *ml,
167 const uint8_t dst[ETH_ADDR_LEN])
169 if (!eth_addr_is_multicast(dst)) {
170 struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst), dst);