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 <config.h>
  35 #include "mac-learning.h"
  36
  37 #include <assert.h>
  38 #include <inttypes.h>
  39 #include <stdlib.h>
  40
  41 #include "hash.h"
  42 #include "list.h"
  43 #include "openflow.h"
  44 #include "util.h"
  45
  46 #define THIS_MODULE VLM_mac_learning
  47 #include "vlog.h"
  48
  49 #define MAC_HASH_BITS 10
  50 #define MAC_HASH_MASK (MAC_HASH_SIZE - 1)
  51 #define MAC_HASH_SIZE (1u << MAC_HASH_BITS)
  52
  53 #define MAC_MAX 1024
  54
  55 /* A MAC learning table entry. */
  56 struct mac_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. */
  61 };
  62
  63 /* MAC learning table. */
  64 struct mac_learning {
  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. */
  69 };
  70
  71 static struct list *
  72 mac_table_bucket(const struct mac_learning *ml,
  73                  const uint8_t mac[ETH_ADDR_LEN])
  74 {
  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;
  78 }
  79
  80 static struct mac_entry *
  81 search_bucket(struct list *bucket, const uint8_t mac[ETH_ADDR_LEN])
  82 {
  83     struct mac_entry *e;
  84     LIST_FOR_EACH (e, struct mac_entry, hash_node, bucket) {
  85         if (eth_addr_equals(e->mac, mac)) {
  86             return e;
  87         }
  88     }
  89     return NULL;
  90 }
  91
  92 /* Creates and returns a new MAC learning table. */
  93 struct mac_learning *
  94 mac_learning_create(void)
  95 {
  96     struct mac_learning *ml;
  97     int i;
  98
  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]);
 103     }
 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;
 108     }
 109     return ml;
 110 }
 111
 112 /* Destroys MAC learning table 'ml'. */
 113 void
 114 mac_learning_destroy(struct mac_learning *ml)
 115 {
 116     free(ml);
 117 }
 118
 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. */
 122 bool
 123 mac_learning_learn(struct mac_learning *ml,
 124                    const uint8_t src_mac[ETH_ADDR_LEN], uint16_t src_port)
 125 {
 126     struct mac_entry *e;
 127     struct list *bucket;
 128
 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));
 133         return false;
 134     }
 135
 136     bucket = mac_table_bucket(ml, src_mac);
 137     e = search_bucket(bucket, src_mac);
 138     if (e) {
 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) {
 143             return false;
 144         }
 145     } else {
 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);
 151         }
 152         list_remove(&e->lru_node);
 153
 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);
 158     }
 159     e->port = src_port;
 160     return true;
 161 }
 162
 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. */
 165 uint16_t
 166 mac_learning_lookup(const struct mac_learning *ml,
 167                     const uint8_t dst[ETH_ADDR_LEN])
 168 {
 169     if (!eth_addr_is_multicast(dst)) {
 170         struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst), dst);
 171         if (e) {
 172             return e->port;
 173         }
 174     }
 175     return OFPP_FLOOD;
 176 }