lib/mac-learning.c

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