lib/mac-learning.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2012 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 "bitmap.h"
  25 #include "coverage.h"
  26 #include "hash.h"
  27 #include "list.h"
  28 #include "poll-loop.h"
  29 #include "tag.h"
  30 #include "timeval.h"
  31 #include "util.h"
  32 #include "vlog.h"
  33
  34 VLOG_DEFINE_THIS_MODULE(mac_learning);
  35
  36 COVERAGE_DEFINE(mac_learning_learned);
  37 COVERAGE_DEFINE(mac_learning_expired);
  38
  39 /* Returns the number of seconds since 'e' (within 'ml') was last learned. */
  40 int
  41 mac_entry_age(const struct mac_learning *ml, const struct mac_entry *e)
  42 {
  43     time_t remaining = e->expires - time_now();
  44     return ml->idle_time - remaining;
  45 }
  46
  47 static uint32_t
  48 mac_table_hash(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan)
  49 {
  50     return hash_bytes(mac, ETH_ADDR_LEN, vlan);
  51 }
  52
  53 static struct mac_entry *
  54 mac_entry_from_lru_node(struct list *list)
  55 {
  56     return CONTAINER_OF(list, struct mac_entry, lru_node);
  57 }
  58
  59 /* Returns a tag that represents that 'mac' is on an unknown port in 'vlan'.
  60  * (When we learn where 'mac' is in 'vlan', this allows flows that were
  61  * flooded to be revalidated.) */
  62 static tag_type
  63 make_unknown_mac_tag(const struct mac_learning *ml,
  64                      const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan)
  65 {
  66     uint32_t h = hash_int(ml->secret, mac_table_hash(mac, vlan));
  67     return tag_create_deterministic(h);
  68 }
  69
  70 static struct list *
  71 mac_table_bucket(const struct mac_learning *ml,
  72                  const uint8_t mac[ETH_ADDR_LEN],
  73                  uint16_t vlan)
  74 {
  75     uint32_t hash = mac_table_hash(mac, vlan);
  76     const struct list *list = &ml->table[hash & MAC_HASH_MASK];
  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               uint16_t vlan)
  83 {
  84     struct mac_entry *e;
  85     LIST_FOR_EACH (e, hash_node, bucket) {
  86         if (eth_addr_equals(e->mac, mac) && e->vlan == vlan) {
  87             return e;
  88         }
  89     }
  90     return NULL;
  91 }
  92
  93 /* If the LRU list is not empty, stores the least-recently-used entry in '*e'
  94  * and returns true.  Otherwise, if the LRU list is empty, stores NULL in '*e'
  95  * and return false. */
  96 static bool
  97 get_lru(struct mac_learning *ml, struct mac_entry **e)
  98 {
  99     if (!list_is_empty(&ml->lrus)) {
 100         *e = mac_entry_from_lru_node(ml->lrus.next);
 101         return true;
 102     } else {
 103         *e = NULL;
 104         return false;
 105     }
 106 }
 107
 108 /* Removes 'e' from the 'ml' hash table.  'e' must not already be on the free
 109  * list. */
 110 static void
 111 free_mac_entry(struct mac_learning *ml, struct mac_entry *e)
 112 {
 113     list_remove(&e->hash_node);
 114     list_remove(&e->lru_node);
 115     list_push_front(&ml->free, &e->lru_node);
 116 }
 117
 118 static unsigned int
 119 normalize_idle_time(unsigned int idle_time)
 120 {
 121     return (idle_time < 15 ? 15
 122             : idle_time > 3600 ? 3600
 123             : idle_time);
 124 }
 125
 126 /* Creates and returns a new MAC learning table with an initial MAC aging
 127  * timeout of 'idle_time' seconds. */
 128 struct mac_learning *
 129 mac_learning_create(unsigned int idle_time)
 130 {
 131     struct mac_learning *ml;
 132     int i;
 133
 134     ml = xmalloc(sizeof *ml);
 135     list_init(&ml->lrus);
 136     list_init(&ml->free);
 137     for (i = 0; i < MAC_HASH_SIZE; i++) {
 138         list_init(&ml->table[i]);
 139     }
 140     for (i = 0; i < MAC_MAX; i++) {
 141         struct mac_entry *s = &ml->entries[i];
 142         list_push_front(&ml->free, &s->lru_node);
 143     }
 144     ml->secret = random_uint32();
 145     ml->flood_vlans = NULL;
 146     ml->idle_time = normalize_idle_time(idle_time);
 147     return ml;
 148 }
 149
 150 /* Destroys MAC learning table 'ml'. */
 151 void
 152 mac_learning_destroy(struct mac_learning *ml)
 153 {
 154     if (ml) {
 155         bitmap_free(ml->flood_vlans);
 156     }
 157     free(ml);
 158 }
 159
 160 /* Provides a bitmap of VLANs which have learning disabled, that is, VLANs on
 161  * which all packets are flooded.  It takes ownership of the bitmap.  Returns
 162  * true if the set has changed from the previous value. */
 163 bool
 164 mac_learning_set_flood_vlans(struct mac_learning *ml, unsigned long *bitmap)
 165 {
 166     bool ret = (bitmap == NULL
 167                 ? ml->flood_vlans != NULL
 168                 : (ml->flood_vlans == NULL
 169                    || !bitmap_equal(bitmap, ml->flood_vlans, 4096)));
 170
 171     bitmap_free(ml->flood_vlans);
 172     ml->flood_vlans = bitmap;
 173
 174     return ret;
 175 }
 176
 177 /* Changes the MAC aging timeout of 'ml' to 'idle_time' seconds. */
 178 void
 179 mac_learning_set_idle_time(struct mac_learning *ml, unsigned int idle_time)
 180 {
 181     idle_time = normalize_idle_time(idle_time);
 182     if (idle_time != ml->idle_time) {
 183         struct mac_entry *e;
 184         int delta;
 185
 186         delta = (int) idle_time - (int) ml->idle_time;
 187         LIST_FOR_EACH (e, lru_node, &ml->lrus) {
 188             e->expires += delta;
 189         }
 190         ml->idle_time = idle_time;
 191     }
 192 }
 193
 194 static bool
 195 is_learning_vlan(const struct mac_learning *ml, uint16_t vlan)
 196 {
 197     return !(ml->flood_vlans && bitmap_is_set(ml->flood_vlans, vlan));
 198 }
 199
 200 /* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was
 201  * just observed arriving from 'src_port' on the given 'vlan'.
 202  *
 203  * Returns nonzero if we actually learned something from this, zero if it just
 204  * confirms what we already knew.  The nonzero return value is the tag of flows
 205  * that now need revalidation.
 206  *
 207  * The 'vlan' parameter is used to maintain separate per-VLAN learning tables.
 208  * Specify 0 if this behavior is undesirable.
 209  *
 210  * 'lock_type' specifies whether the entry should be locked or existing locks
 211  * are check. */
 212 tag_type
 213 mac_learning_learn(struct mac_learning *ml,
 214                    const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan,
 215                    uint16_t src_port, enum grat_arp_lock_type lock_type)
 216 {
 217     struct mac_entry *e;
 218     struct list *bucket;
 219
 220     if (!is_learning_vlan(ml, vlan)) {
 221         return 0;
 222     }
 223
 224     if (eth_addr_is_multicast(src_mac)) {
 225         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 30);
 226         VLOG_DBG_RL(&rl, "multicast packet source "ETH_ADDR_FMT,
 227                     ETH_ADDR_ARGS(src_mac));
 228         return 0;
 229     }
 230
 231     bucket = mac_table_bucket(ml, src_mac, vlan);
 232     e = search_bucket(bucket, src_mac, vlan);
 233     if (!e) {
 234         if (!list_is_empty(&ml->free)) {
 235             e = mac_entry_from_lru_node(ml->free.next);
 236         } else {
 237             e = mac_entry_from_lru_node(ml->lrus.next);
 238             list_remove(&e->hash_node);
 239         }
 240         memcpy(e->mac, src_mac, ETH_ADDR_LEN);
 241         list_push_front(bucket, &e->hash_node);
 242         e->port = -1;
 243         e->vlan = vlan;
 244         e->tag = make_unknown_mac_tag(ml, src_mac, vlan);
 245         e->grat_arp_lock = TIME_MIN;
 246     }
 247
 248     if (lock_type != GRAT_ARP_LOCK_CHECK || time_now() >= e->grat_arp_lock) {
 249         /* Make the entry most-recently-used. */
 250         list_remove(&e->lru_node);
 251         list_push_back(&ml->lrus, &e->lru_node);
 252         e->expires = time_now() + ml->idle_time;
 253         if (lock_type == GRAT_ARP_LOCK_SET) {
 254             e->grat_arp_lock = time_now() + MAC_GRAT_ARP_LOCK_TIME;
 255         }
 256
 257         /* Did we learn something? */
 258         if (e->port != src_port) {
 259             tag_type old_tag = e->tag;
 260             e->port = src_port;
 261             e->tag = tag_create_random();
 262             COVERAGE_INC(mac_learning_learned);
 263             return old_tag;
 264         }
 265     }
 266
 267     return 0;
 268 }
 269
 270 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
 271  * frame destined for 'dst' should be sent, -1 if unknown. 'is_grat_arp_locked'
 272  * is an optional parameter that returns whether the entry is currently
 273  * locked. */
 274 int
 275 mac_learning_lookup(const struct mac_learning *ml,
 276                     const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan,
 277                     bool *is_grat_arp_locked)
 278 {
 279     tag_type tag = 0;
 280     return mac_learning_lookup_tag(ml, dst, vlan, &tag, is_grat_arp_locked);
 281 }
 282
 283 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
 284  * frame destined for 'dst' should be sent, -1 if unknown.
 285  *
 286  * Adds to '*tag' (which the caller must have initialized) the tag that should
 287  * be attached to any flow created based on the return value, if any, to allow
 288  * those flows to be revalidated when the MAC learning entry changes.
 289  *
 290  * 'is_grat_arp_locked' is an optional parameter that returns whether the entry
 291  * is currently locked.*/
 292 int
 293 mac_learning_lookup_tag(const struct mac_learning *ml,
 294                         const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan,
 295                         tag_type *tag, bool *is_grat_arp_locked)
 296 {
 297     if (eth_addr_is_multicast(dst) || !is_learning_vlan(ml, vlan)) {
 298         return -1;
 299     } else {
 300         struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst, vlan),
 301                                             dst, vlan);
 302         if (e) {
 303             *tag |= e->tag;
 304
 305             if (is_grat_arp_locked) {
 306                 *is_grat_arp_locked = time_now() < e->grat_arp_lock;
 307             }
 308
 309             return e->port;
 310         } else {
 311             *tag |= make_unknown_mac_tag(ml, dst, vlan);
 312             return -1;
 313         }
 314     }
 315 }
 316
 317 /* Expires all the mac-learning entries in 'ml'.  The tags in 'ml' are
 318  * discarded, so the client is responsible for revalidating any flows that
 319  * depend on 'ml', if necessary. */
 320 void
 321 mac_learning_flush(struct mac_learning *ml)
 322 {
 323     struct mac_entry *e;
 324     while (get_lru(ml, &e)){
 325         free_mac_entry(ml, e);
 326     }
 327 }
 328
 329 void
 330 mac_learning_run(struct mac_learning *ml, struct tag_set *set)
 331 {
 332     struct mac_entry *e;
 333     while (get_lru(ml, &e) && time_now() >= e->expires) {
 334         COVERAGE_INC(mac_learning_expired);
 335         if (set) {
 336             tag_set_add(set, e->tag);
 337         }
 338         free_mac_entry(ml, e);
 339     }
 340 }
 341
 342 void
 343 mac_learning_wait(struct mac_learning *ml)
 344 {
 345     if (!list_is_empty(&ml->lrus)) {
 346         struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next);
 347         poll_timer_wait_until(e->expires * 1000LL);
 348     }
 349 }