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 "timeval.h"
  45 #include "util.h"
  46
  47 #define THIS_MODULE VLM_mac_learning
  48 #include "vlog.h"
  49
  50 #define MAC_HASH_BITS 10
  51 #define MAC_HASH_MASK (MAC_HASH_SIZE - 1)
  52 #define MAC_HASH_SIZE (1u << MAC_HASH_BITS)
  53
  54 #define MAC_MAX 1024
  55
  56 /* A MAC learning table entry. */
  57 struct mac_entry {
  58     struct list hash_node;      /* Element in a mac_learning 'table' list. */
  59     struct list lru_node;       /* Element in mac_learning 'lrus' list. */
  60     time_t used;                /* Last used time. */
  61     uint8_t mac[ETH_ADDR_LEN];  /* Known MAC address. */
  62     int port;                   /* Port on which MAC was most recently seen. */
  63 };
  64
  65 /* MAC learning table. */
  66 struct mac_learning {
  67     struct list lrus;           /* All entries, least recently used at the
  68                                    front, most recently used at the back. */
  69     struct list table[MAC_HASH_SIZE]; /* Hash table. */
  70     struct mac_entry entries[MAC_MAX]; /* All entries. */
  71 };
  72
  73 static struct list *
  74 mac_table_bucket(const struct mac_learning *ml,
  75                  const uint8_t mac[ETH_ADDR_LEN])
  76 {
  77     uint32_t hash = hash_fnv(mac, ETH_ADDR_LEN, HASH_FNV_BASIS);
  78     const struct list *list = &ml->table[hash & MAC_HASH_BITS];
  79     return (struct list *) list;
  80 }
  81
  82 static struct mac_entry *
  83 search_bucket(struct list *bucket, const uint8_t mac[ETH_ADDR_LEN])
  84 {
  85     struct mac_entry *e;
  86     LIST_FOR_EACH (e, struct mac_entry, hash_node, bucket) {
  87         if (eth_addr_equals(e->mac, mac)) {
  88             return e;
  89         }
  90     }
  91     return NULL;
  92 }
  93
  94 /* Creates and returns a new MAC learning table. */
  95 struct mac_learning *
  96 mac_learning_create(void)
  97 {
  98     struct mac_learning *ml;
  99     int i;
 100
 101     ml = xmalloc(sizeof *ml);
 102     list_init(&ml->lrus);
 103     for (i = 0; i < MAC_HASH_SIZE; i++) {
 104         list_init(&ml->table[i]);
 105     }
 106     for (i = 0; i < MAC_MAX; i++) {
 107         struct mac_entry *s = &ml->entries[i];
 108         list_push_front(&ml->lrus, &s->lru_node);
 109         s->hash_node.next = NULL;
 110     }
 111     return ml;
 112 }
 113
 114 /* Destroys MAC learning table 'ml'. */
 115 void
 116 mac_learning_destroy(struct mac_learning *ml)
 117 {
 118     free(ml);
 119 }
 120
 121 /* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was
 122  * just observed arriving on 'src_port'.  Returns true if we actually learned
 123  * something from this, false if it just confirms what we already knew. */
 124 bool
 125 mac_learning_learn(struct mac_learning *ml,
 126                    const uint8_t src_mac[ETH_ADDR_LEN], uint16_t src_port)
 127 {
 128     struct mac_entry *e;
 129     struct list *bucket;
 130
 131     if (eth_addr_is_multicast(src_mac)) {
 132         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 30);
 133         VLOG_DBG_RL(&rl, "multicast packet source "ETH_ADDR_FMT,
 134                     ETH_ADDR_ARGS(src_mac));
 135         return false;
 136     }
 137
 138     bucket = mac_table_bucket(ml, src_mac);
 139     e = search_bucket(bucket, src_mac);
 140     if (!e) {
 141         e = CONTAINER_OF(ml->lrus.next, struct mac_entry, lru_node);
 142         memcpy(e->mac, src_mac, ETH_ADDR_LEN);
 143         if (e->hash_node.next) {
 144             list_remove(&e->hash_node);
 145         }
 146         list_push_front(bucket, &e->hash_node);
 147         e->port = -1;
 148     }
 149
 150     /* Make the entry most-recently-used. */
 151     list_remove(&e->lru_node);
 152     list_push_back(&ml->lrus, &e->lru_node);
 153     e->used = time_now();
 154
 155     /* Did we learn something? */
 156     if (e->port != src_port) {
 157         e->port = src_port;
 158         return true;
 159     }
 160     return false;
 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 && time_now() - e->used < 60) {
 172             return e->port;
 173         }
 174     }
 175     return OFPP_FLOOD;
 176 }