pintos-os.org Git - openvswitch/blob - 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 "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
  33 #define THIS_MODULE VLM_mac_learning
  34 #include "vlog.h"
  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, struct mac_entry, 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->non_learning_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->non_learning_vlans);
 143     }
 144     free(ml);
 145 }
 146
 147 /* Provides a bitmap of VLANs which have learning disabled.  It takes
 148  * ownership of the bitmap.  Returns true if the set has changed from
 149  * the previous value. */
 150 bool
 151 mac_learning_set_disabled_vlans(struct mac_learning *ml, unsigned long *bitmap)
 152 {
 153     bool ret = (bitmap == NULL
 154         ? ml->non_learning_vlans != NULL
 155         : (ml->non_learning_vlans == NULL
 156           || !bitmap_equal(bitmap, ml->non_learning_vlans, 4096)));
 157
 158     bitmap_free(ml->non_learning_vlans);
 159     ml->non_learning_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->non_learning_vlans
 168             && bitmap_is_set(ml->non_learning_vlans, vlan));
 169 }
 170
 171 /* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was
 172  * just observed arriving from 'src_port' on the given 'vlan'.
 173  *
 174  * Returns nonzero if we actually learned something from this, zero if it just
 175  * confirms what we already knew.  The nonzero return value is the tag of flows
 176  * that now need revalidation.
 177  *
 178  * The 'vlan' parameter is used to maintain separate per-VLAN learning tables.
 179  * Specify 0 if this behavior is undesirable. */
 180 tag_type
 181 mac_learning_learn(struct mac_learning *ml,
 182                    const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan,
 183                    uint16_t src_port)
 184 {
 185     struct mac_entry *e;
 186     struct list *bucket;
 187
 188     if (!is_learning_vlan(ml, vlan)) {
 189         return 0;
 190     }
 191
 192     if (eth_addr_is_multicast(src_mac)) {
 193         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 30);
 194         VLOG_DBG_RL(&rl, "multicast packet source "ETH_ADDR_FMT,
 195                     ETH_ADDR_ARGS(src_mac));
 196         return 0;
 197     }
 198
 199     bucket = mac_table_bucket(ml, src_mac, vlan);
 200     e = search_bucket(bucket, src_mac, vlan);
 201     if (!e) {
 202         if (!list_is_empty(&ml->free)) {
 203             e = mac_entry_from_lru_node(ml->free.next);
 204         } else {
 205             e = mac_entry_from_lru_node(ml->lrus.next);
 206             list_remove(&e->hash_node);
 207         }
 208         memcpy(e->mac, src_mac, ETH_ADDR_LEN);
 209         list_push_front(bucket, &e->hash_node);
 210         e->port = -1;
 211         e->vlan = vlan;
 212         e->tag = make_unknown_mac_tag(ml, src_mac, vlan);
 213     }
 214
 215     /* Make the entry most-recently-used. */
 216     list_remove(&e->lru_node);
 217     list_push_back(&ml->lrus, &e->lru_node);
 218     e->expires = time_now() + MAC_ENTRY_IDLE_TIME;
 219
 220     /* Did we learn something? */
 221     if (e->port != src_port) {
 222         tag_type old_tag = e->tag;
 223         e->port = src_port;
 224         e->tag = tag_create_random();
 225         COVERAGE_INC(mac_learning_learned);
 226         return old_tag;
 227     }
 228     return 0;
 229 }
 230
 231 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
 232  * frame destined for 'dst' should be sent, -1 if unknown. */
 233 int
 234 mac_learning_lookup(const struct mac_learning *ml,
 235                     const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan)
 236 {
 237     tag_type tag = 0;
 238     return mac_learning_lookup_tag(ml, dst, vlan, &tag);
 239 }
 240
 241 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
 242  * frame destined for 'dst' should be sent, -1 if unknown.
 243  *
 244  * Adds to '*tag' (which the caller must have initialized) the tag that should
 245  * be attached to any flow created based on the return value, if any, to allow
 246  * those flows to be revalidated when the MAC learning entry changes. */
 247 int
 248 mac_learning_lookup_tag(const struct mac_learning *ml,
 249                         const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan,
 250                         tag_type *tag)
 251 {
 252     if (eth_addr_is_multicast(dst) || !is_learning_vlan(ml, vlan)) {
 253         return -1;
 254     } else {
 255         struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst, vlan),
 256                                             dst, vlan);
 257         if (e) {
 258             *tag |= e->tag;
 259             return e->port;
 260         } else {
 261             *tag |= make_unknown_mac_tag(ml, dst, vlan);
 262             return -1;
 263         }
 264     }
 265 }
 266
 267 /* Expires all the mac-learning entries in 'ml'.  The tags in 'ml' are
 268  * discarded, so the client is responsible for revalidating any flows that
 269  * depend on 'ml', if necessary. */
 270 void
 271 mac_learning_flush(struct mac_learning *ml)
 272 {
 273     struct mac_entry *e;
 274     while (get_lru(ml, &e)){
 275         free_mac_entry(ml, e);
 276     }
 277 }
 278
 279 void
 280 mac_learning_run(struct mac_learning *ml, struct tag_set *set)
 281 {
 282     struct mac_entry *e;
 283     while (get_lru(ml, &e) && time_now() >= e->expires) {
 284         COVERAGE_INC(mac_learning_expired);
 285         if (set) {
 286             tag_set_add(set, e->tag);
 287         }
 288         free_mac_entry(ml, e);
 289     }
 290 }
 291
 292 void
 293 mac_learning_wait(struct mac_learning *ml)
 294 {
 295     if (!list_is_empty(&ml->lrus)) {
 296         struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next);
 297         poll_timer_wait((e->expires - time_now()) * 1000);
 298     }
 299 }