lib/mac-learning.c

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