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 #define MAC_HASH_BITS 10
  36 #define MAC_HASH_MASK (MAC_HASH_SIZE - 1)
  37 #define MAC_HASH_SIZE (1u << MAC_HASH_BITS)
  38
  39 #define MAC_MAX 1024
  40
  41 /* A MAC learning table entry. */
  42 struct mac_entry {
  43     struct list hash_node;      /* Element in a mac_learning 'table' list. */
  44     struct list lru_node;       /* Element in 'lrus' or 'free' list. */
  45     time_t expires;             /* Expiration time. */
  46     uint8_t mac[ETH_ADDR_LEN];  /* Known MAC address. */
  47     uint16_t vlan;              /* VLAN tag. */
  48     int port;                   /* Port on which MAC was most recently seen. */
  49     tag_type tag;               /* Tag for this learning entry. */
  50 };
  51
  52 /* MAC learning table. */
  53 struct mac_learning {
  54     struct list free;           /* Not-in-use entries. */
  55     struct list lrus;           /* In-use entries, least recently used at the
  56                                    front, most recently used at the back. */
  57     struct list table[MAC_HASH_SIZE]; /* Hash table. */
  58     struct mac_entry entries[MAC_MAX]; /* All entries. */
  59     uint32_t secret;            /* Secret for  */
  60 };
  61
  62 static uint32_t
  63 mac_table_hash(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan)
  64 {
  65     return hash_bytes(mac, ETH_ADDR_LEN, vlan);
  66 }
  67
  68 static struct mac_entry *
  69 mac_entry_from_lru_node(struct list *list)
  70 {
  71     return CONTAINER_OF(list, struct mac_entry, lru_node);
  72 }
  73
  74 /* Returns a tag that represents that 'mac' is on an unknown port in 'vlan'.
  75  * (When we learn where 'mac' is in 'vlan', this allows flows that were
  76  * flooded to be revalidated.) */
  77 static tag_type
  78 make_unknown_mac_tag(const struct mac_learning *ml,
  79                      const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan)
  80 {
  81     uint32_t h = hash_int(ml->secret, mac_table_hash(mac, vlan));
  82     return tag_create_deterministic(h);
  83 }
  84
  85 static struct list *
  86 mac_table_bucket(const struct mac_learning *ml,
  87                  const uint8_t mac[ETH_ADDR_LEN],
  88                  uint16_t vlan)
  89 {
  90     uint32_t hash = mac_table_hash(mac, vlan);
  91     const struct list *list = &ml->table[hash & MAC_HASH_BITS];
  92     return (struct list *) list;
  93 }
  94
  95 static struct mac_entry *
  96 search_bucket(struct list *bucket, const uint8_t mac[ETH_ADDR_LEN],
  97               uint16_t vlan)
  98 {
  99     struct mac_entry *e;
 100     LIST_FOR_EACH (e, struct mac_entry, hash_node, bucket) {
 101         if (eth_addr_equals(e->mac, mac) && e->vlan == vlan) {
 102             return e;
 103         }
 104     }
 105     return NULL;
 106 }
 107
 108 /* If the LRU list is not empty, stores the least-recently-used entry in '*e'
 109  * and returns true.  Otherwise, if the LRU list is empty, stores NULL in '*e'
 110  * and return false. */
 111 static bool
 112 get_lru(struct mac_learning *ml, struct mac_entry **e)
 113 {
 114     if (!list_is_empty(&ml->lrus)) {
 115         *e = mac_entry_from_lru_node(ml->lrus.next);
 116         return true;
 117     } else {
 118         *e = NULL;
 119         return false;
 120     }
 121 }
 122
 123 /* Removes 'e' from the 'ml' hash table.  'e' must not already be on the free
 124  * list. */
 125 static void
 126 free_mac_entry(struct mac_learning *ml, struct mac_entry *e)
 127 {
 128     list_remove(&e->hash_node);
 129     list_remove(&e->lru_node);
 130     list_push_front(&ml->free, &e->lru_node);
 131 }
 132
 133 /* Creates and returns a new MAC learning table. */
 134 struct mac_learning *
 135 mac_learning_create(void)
 136 {
 137     struct mac_learning *ml;
 138     int i;
 139
 140     ml = xmalloc(sizeof *ml);
 141     list_init(&ml->lrus);
 142     list_init(&ml->free);
 143     for (i = 0; i < MAC_HASH_SIZE; i++) {
 144         list_init(&ml->table[i]);
 145     }
 146     for (i = 0; i < MAC_MAX; i++) {
 147         struct mac_entry *s = &ml->entries[i];
 148         list_push_front(&ml->free, &s->lru_node);
 149     }
 150     ml->secret = random_uint32();
 151     return ml;
 152 }
 153
 154 /* Destroys MAC learning table 'ml'. */
 155 void
 156 mac_learning_destroy(struct mac_learning *ml)
 157 {
 158     free(ml);
 159 }
 160
 161 /* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was
 162  * just observed arriving from 'src_port' on the given 'vlan'.
 163  *
 164  * Returns nonzero if we actually learned something from this, zero if it just
 165  * confirms what we already knew.  The nonzero return value is the tag of flows
 166  * that now need revalidation.
 167  *
 168  * The 'vlan' parameter is used to maintain separate per-VLAN learning tables.
 169  * Specify 0 if this behavior is undesirable. */
 170 tag_type
 171 mac_learning_learn(struct mac_learning *ml,
 172                    const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan,
 173                    uint16_t src_port)
 174 {
 175     struct mac_entry *e;
 176     struct list *bucket;
 177
 178     if (eth_addr_is_multicast(src_mac)) {
 179         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 30);
 180         VLOG_DBG_RL(&rl, "multicast packet source "ETH_ADDR_FMT,
 181                     ETH_ADDR_ARGS(src_mac));
 182         return 0;
 183     }
 184
 185     bucket = mac_table_bucket(ml, src_mac, vlan);
 186     e = search_bucket(bucket, src_mac, vlan);
 187     if (!e) {
 188         if (!list_is_empty(&ml->free)) {
 189             e = mac_entry_from_lru_node(ml->free.next);
 190         } else {
 191             e = mac_entry_from_lru_node(ml->lrus.next);
 192             list_remove(&e->hash_node);
 193         }
 194         memcpy(e->mac, src_mac, ETH_ADDR_LEN);
 195         list_push_front(bucket, &e->hash_node);
 196         e->port = -1;
 197         e->vlan = vlan;
 198         e->tag = make_unknown_mac_tag(ml, src_mac, vlan);
 199     }
 200
 201     /* Make the entry most-recently-used. */
 202     list_remove(&e->lru_node);
 203     list_push_back(&ml->lrus, &e->lru_node);
 204     e->expires = time_now() + 60;
 205
 206     /* Did we learn something? */
 207     if (e->port != src_port) {
 208         tag_type old_tag = e->tag;
 209         e->port = src_port;
 210         e->tag = tag_create_random();
 211         COVERAGE_INC(mac_learning_learned);
 212         return old_tag;
 213     }
 214     return 0;
 215 }
 216
 217 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
 218  * frame destined for 'dst' should be sent, -1 if unknown. */
 219 int
 220 mac_learning_lookup(const struct mac_learning *ml,
 221                     const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan)
 222 {
 223     tag_type tag = 0;
 224     return mac_learning_lookup_tag(ml, dst, vlan, &tag);
 225 }
 226
 227 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
 228  * frame destined for 'dst' should be sent, -1 if unknown.
 229  *
 230  * Adds to '*tag' (which the caller must have initialized) the tag that should
 231  * be attached to any flow created based on the return value, if any, to allow
 232  * those flows to be revalidated when the MAC learning entry changes. */
 233 int
 234 mac_learning_lookup_tag(const struct mac_learning *ml,
 235                         const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan,
 236                         tag_type *tag)
 237 {
 238     if (eth_addr_is_multicast(dst)) {
 239         return -1;
 240     } else {
 241         struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst, vlan),
 242                                             dst, vlan);
 243         if (e) {
 244             *tag |= e->tag;
 245             return e->port;
 246         } else {
 247             *tag |= make_unknown_mac_tag(ml, dst, vlan);
 248             return -1;
 249         }
 250     }
 251 }
 252
 253 /* Expires all the mac-learning entries in 'ml'.  The tags in 'ml' are
 254  * discarded, so the client is responsible for revalidating any flows that
 255  * depend on 'ml', if necessary. */
 256 void
 257 mac_learning_flush(struct mac_learning *ml)
 258 {
 259     struct mac_entry *e;
 260     while (get_lru(ml, &e)){
 261         free_mac_entry(ml, e);
 262     }
 263 }
 264
 265 void
 266 mac_learning_run(struct mac_learning *ml, struct tag_set *set)
 267 {
 268     struct mac_entry *e;
 269     while (get_lru(ml, &e) && time_now() >= e->expires) {
 270         COVERAGE_INC(mac_learning_expired);
 271         if (set) {
 272             tag_set_add(set, e->tag);
 273         }
 274         free_mac_entry(ml, e);
 275     }
 276 }
 277
 278 void
 279 mac_learning_wait(struct mac_learning *ml)
 280 {
 281     if (!list_is_empty(&ml->lrus)) {
 282         struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next);
 283         poll_timer_wait((e->expires - time_now()) * 1000);
 284     }
 285 }