lib/mac-learning.c

   1 /*
   2  * Copyright (c) 2008, 2009 Nicira Networks.
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  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 "coverage.h"
  25 #include "hash.h"
  26 #include "list.h"
  27 #include "poll-loop.h"
  28 #include "tag.h"
  29 #include "timeval.h"
  30 #include "util.h"
  31
  32 #define THIS_MODULE VLM_mac_learning
  33 #include "vlog.h"
  34
  35 static uint32_t
  36 mac_table_hash(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan)
  37 {
  38     return hash_bytes(mac, ETH_ADDR_LEN, vlan);
  39 }
  40
  41 static struct mac_entry *
  42 mac_entry_from_lru_node(struct list *list)
  43 {
  44     return CONTAINER_OF(list, struct mac_entry, lru_node);
  45 }
  46
  47 /* Returns a tag that represents that 'mac' is on an unknown port in 'vlan'.
  48  * (When we learn where 'mac' is in 'vlan', this allows flows that were
  49  * flooded to be revalidated.) */
  50 static tag_type
  51 make_unknown_mac_tag(const struct mac_learning *ml,
  52                      const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan)
  53 {
  54     uint32_t h = hash_int(ml->secret, mac_table_hash(mac, vlan));
  55     return tag_create_deterministic(h);
  56 }
  57
  58 static struct list *
  59 mac_table_bucket(const struct mac_learning *ml,
  60                  const uint8_t mac[ETH_ADDR_LEN],
  61                  uint16_t vlan)
  62 {
  63     uint32_t hash = mac_table_hash(mac, vlan);
  64     const struct list *list = &ml->table[hash & MAC_HASH_BITS];
  65     return (struct list *) list;
  66 }
  67
  68 static struct mac_entry *
  69 search_bucket(struct list *bucket, const uint8_t mac[ETH_ADDR_LEN],
  70               uint16_t vlan)
  71 {
  72     struct mac_entry *e;
  73     LIST_FOR_EACH (e, struct mac_entry, hash_node, bucket) {
  74         if (eth_addr_equals(e->mac, mac) && e->vlan == vlan) {
  75             return e;
  76         }
  77     }
  78     return NULL;
  79 }
  80
  81 /* If the LRU list is not empty, stores the least-recently-used entry in '*e'
  82  * and returns true.  Otherwise, if the LRU list is empty, stores NULL in '*e'
  83  * and return false. */
  84 static bool
  85 get_lru(struct mac_learning *ml, struct mac_entry **e)
  86 {
  87     if (!list_is_empty(&ml->lrus)) {
  88         *e = mac_entry_from_lru_node(ml->lrus.next);
  89         return true;
  90     } else {
  91         *e = NULL;
  92         return false;
  93     }
  94 }
  95
  96 /* Removes 'e' from the 'ml' hash table.  'e' must not already be on the free
  97  * list. */
  98 static void
  99 free_mac_entry(struct mac_learning *ml, struct mac_entry *e)
 100 {
 101     list_remove(&e->hash_node);
 102     list_remove(&e->lru_node);
 103     list_push_front(&ml->free, &e->lru_node);
 104 }
 105
 106 /* Creates and returns a new MAC learning table. */
 107 struct mac_learning *
 108 mac_learning_create(void)
 109 {
 110     struct mac_learning *ml;
 111     int i;
 112
 113     ml = xmalloc(sizeof *ml);
 114     list_init(&ml->lrus);
 115     list_init(&ml->free);
 116     for (i = 0; i < MAC_HASH_SIZE; i++) {
 117         list_init(&ml->table[i]);
 118     }
 119     for (i = 0; i < MAC_MAX; i++) {
 120         struct mac_entry *s = &ml->entries[i];
 121         list_push_front(&ml->free, &s->lru_node);
 122     }
 123     ml->secret = random_uint32();
 124     return ml;
 125 }
 126
 127 /* Destroys MAC learning table 'ml'. */
 128 void
 129 mac_learning_destroy(struct mac_learning *ml)
 130 {
 131     free(ml);
 132 }
 133
 134 /* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was
 135  * just observed arriving from 'src_port' on the given 'vlan'.
 136  *
 137  * Returns nonzero if we actually learned something from this, zero if it just
 138  * confirms what we already knew.  The nonzero return value is the tag of flows
 139  * that now need revalidation.
 140  *
 141  * The 'vlan' parameter is used to maintain separate per-VLAN learning tables.
 142  * Specify 0 if this behavior is undesirable. */
 143 tag_type
 144 mac_learning_learn(struct mac_learning *ml,
 145                    const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan,
 146                    uint16_t src_port)
 147 {
 148     struct mac_entry *e;
 149     struct list *bucket;
 150
 151     if (eth_addr_is_multicast(src_mac)) {
 152         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 30);
 153         VLOG_DBG_RL(&rl, "multicast packet source "ETH_ADDR_FMT,
 154                     ETH_ADDR_ARGS(src_mac));
 155         return 0;
 156     }
 157
 158     bucket = mac_table_bucket(ml, src_mac, vlan);
 159     e = search_bucket(bucket, src_mac, vlan);
 160     if (!e) {
 161         if (!list_is_empty(&ml->free)) {
 162             e = mac_entry_from_lru_node(ml->free.next);
 163         } else {
 164             e = mac_entry_from_lru_node(ml->lrus.next);
 165             list_remove(&e->hash_node);
 166         }
 167         memcpy(e->mac, src_mac, ETH_ADDR_LEN);
 168         list_push_front(bucket, &e->hash_node);
 169         e->port = -1;
 170         e->vlan = vlan;
 171         e->tag = make_unknown_mac_tag(ml, src_mac, vlan);
 172     }
 173
 174     /* Make the entry most-recently-used. */
 175     list_remove(&e->lru_node);
 176     list_push_back(&ml->lrus, &e->lru_node);
 177     e->expires = time_now() + 60;
 178
 179     /* Did we learn something? */
 180     if (e->port != src_port) {
 181         tag_type old_tag = e->tag;
 182         e->port = src_port;
 183         e->tag = tag_create_random();
 184         COVERAGE_INC(mac_learning_learned);
 185         return old_tag;
 186     }
 187     return 0;
 188 }
 189
 190 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
 191  * frame destined for 'dst' should be sent, -1 if unknown. */
 192 int
 193 mac_learning_lookup(const struct mac_learning *ml,
 194                     const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan)
 195 {
 196     tag_type tag = 0;
 197     return mac_learning_lookup_tag(ml, dst, vlan, &tag);
 198 }
 199
 200 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
 201  * frame destined for 'dst' should be sent, -1 if unknown.
 202  *
 203  * Adds to '*tag' (which the caller must have initialized) the tag that should
 204  * be attached to any flow created based on the return value, if any, to allow
 205  * those flows to be revalidated when the MAC learning entry changes. */
 206 int
 207 mac_learning_lookup_tag(const struct mac_learning *ml,
 208                         const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan,
 209                         tag_type *tag)
 210 {
 211     if (eth_addr_is_multicast(dst)) {
 212         return -1;
 213     } else {
 214         struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst, vlan),
 215                                             dst, vlan);
 216         if (e) {
 217             *tag |= e->tag;
 218             return e->port;
 219         } else {
 220             *tag |= make_unknown_mac_tag(ml, dst, vlan);
 221             return -1;
 222         }
 223     }
 224 }
 225
 226 /* Expires all the mac-learning entries in 'ml'.  The tags in 'ml' are
 227  * discarded, so the client is responsible for revalidating any flows that
 228  * depend on 'ml', if necessary. */
 229 void
 230 mac_learning_flush(struct mac_learning *ml)
 231 {
 232     struct mac_entry *e;
 233     while (get_lru(ml, &e)){
 234         free_mac_entry(ml, e);
 235     }
 236 }
 237
 238 void
 239 mac_learning_run(struct mac_learning *ml, struct tag_set *set)
 240 {
 241     struct mac_entry *e;
 242     while (get_lru(ml, &e) && time_now() >= e->expires) {
 243         COVERAGE_INC(mac_learning_expired);
 244         if (set) {
 245             tag_set_add(set, e->tag);
 246         }
 247         free_mac_entry(ml, e);
 248     }
 249 }
 250
 251 void
 252 mac_learning_wait(struct mac_learning *ml)
 253 {
 254     if (!list_is_empty(&ml->lrus)) {
 255         struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next);
 256         poll_timer_wait((e->expires - time_now()) * 1000);
 257     }
 258 }