lib/mac-learning.c

   1 /* Copyright (c) 2008 The Board of Trustees of The Leland Stanford
   2  * Junior University
   3  *
   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:
  16  *
  17  * The above copyright notice and this permission notice shall be
  18  * included in all copies or substantial portions of the Software.
  19  *
  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
  27  * SOFTWARE.
  28  *
  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.
  32  */
  33
  34 #include "mac-learning.h"
  35
  36 #include <assert.h>
  37 #include <inttypes.h>
  38 #include <stdlib.h>
  39
  40 #include "hash.h"
  41 #include "list.h"
  42 #include "openflow.h"
  43 #include "util.h"
  44
  45 #define THIS_MODULE VLM_mac_learning
  46 #include "vlog.h"
  47
  48 #define MAC_HASH_BITS 10
  49 #define MAC_HASH_MASK (MAC_HASH_SIZE - 1)
  50 #define MAC_HASH_SIZE (1u << MAC_HASH_BITS)
  51
  52 #define MAC_MAX 1024
  53
  54 /* A MAC learning table entry. */
  55 struct mac_entry {
  56     struct list hash_node;      /* Element in a mac_learning 'table' list. */
  57     struct list lru_node;       /* Element in mac_learning 'lrus' list. */
  58     uint8_t mac[ETH_ADDR_LEN];  /* Known MAC address. */
  59     uint16_t port;              /* Port on which MAC was most recently seen. */
  60 };
  61
  62 /* MAC learning table. */
  63 struct mac_learning {
  64     struct list lrus;           /* All entries, least recently used at the
  65                                    front, most recently used at the back. */
  66     struct list table[MAC_HASH_SIZE]; /* Hash table. */
  67     struct mac_entry entries[MAC_MAX]; /* All entries. */
  68 };
  69
  70 static struct list *
  71 mac_table_bucket(const struct mac_learning *ml,
  72                  const uint8_t mac[ETH_ADDR_LEN])
  73 {
  74     uint32_t hash = hash_fnv(mac, ETH_ADDR_LEN, HASH_FNV_BASIS);
  75     const struct list *list = &ml->table[hash & MAC_HASH_BITS];
  76     return (struct list *) list;
  77 }
  78
  79 static struct mac_entry *
  80 search_bucket(struct list *bucket, const uint8_t mac[ETH_ADDR_LEN])
  81 {
  82     struct mac_entry *e;
  83     LIST_FOR_EACH (e, struct mac_entry, hash_node, bucket) {
  84         if (eth_addr_equals(e->mac, mac)) {
  85             return e;
  86         }
  87     }
  88     return NULL;
  89 }
  90
  91 /* Creates and returns a new MAC learning table. */
  92 struct mac_learning *
  93 mac_learning_create(void)
  94 {
  95     struct mac_learning *ml;
  96     int i;
  97
  98     ml = xmalloc(sizeof *ml);
  99     list_init(&ml->lrus);
 100     for (i = 0; i < MAC_HASH_SIZE; i++) {
 101         list_init(&ml->table[i]);
 102     }
 103     for (i = 0; i < MAC_MAX; i++) {
 104         struct mac_entry *s = &ml->entries[i];
 105         list_push_front(&ml->lrus, &s->lru_node);
 106         s->hash_node.next = NULL;
 107     }
 108     return ml;
 109 }
 110
 111 /* Destroys MAC learning table 'ml'. */
 112 void
 113 mac_learning_destroy(struct mac_learning *ml)
 114 {
 115     free(ml);
 116 }
 117
 118 /* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was
 119  * just observed arriving on 'src_port'.  Returns true if we actually learned
 120  * something from this, false if it just confirms what we already knew. */
 121 bool
 122 mac_learning_learn(struct mac_learning *ml,
 123                    const uint8_t src_mac[ETH_ADDR_LEN], uint16_t src_port)
 124 {
 125     struct mac_entry *e;
 126     struct list *bucket;
 127
 128     assert(src_port != OFPP_FLOOD);
 129     if (eth_addr_is_multicast(src_mac)) {
 130         VLOG_DBG("multicast packet source "ETH_ADDR_FMT,
 131                  ETH_ADDR_ARGS(src_mac));
 132         return false;
 133     }
 134
 135     bucket = mac_table_bucket(ml, src_mac);
 136     e = search_bucket(bucket, src_mac);
 137     if (e) {
 138         /* Make 'e' most-recently-used.  */
 139         list_remove(&e->lru_node);
 140         list_push_back(&ml->lrus, &e->lru_node);
 141         if (e->port == src_port) {
 142             return false;
 143         }
 144     } else {
 145         /* Learn a new address.
 146          * First drop the least recently used mac source. */
 147         e = CONTAINER_OF(ml->lrus.next, struct mac_entry, lru_node);
 148         if (e->hash_node.next) {
 149             list_remove(&e->hash_node);
 150         }
 151         list_remove(&e->lru_node);
 152
 153         /* Create new mac source. */
 154         memcpy(e->mac, src_mac, ETH_ADDR_LEN);
 155         list_push_front(bucket, &e->hash_node);
 156         list_push_back(&ml->lrus, &e->lru_node);
 157     }
 158     e->port = src_port;
 159     return true;
 160 }
 161
 162 /* Looks up address 'dst' in 'ml'.  Returns the port on which a frame destined
 163  * for 'dst' should be sent, OFPP_FLOOD if unknown. */
 164 uint16_t
 165 mac_learning_lookup(const struct mac_learning *ml,
 166                     const uint8_t dst[ETH_ADDR_LEN])
 167 {
 168     if (!eth_addr_is_multicast(dst)) {
 169         struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst), dst);
 170         if (e) {
 171             return e->port;
 172         }
 173     }
 174     return OFPP_FLOOD;
 175 }