pintos-os.org Git - openvswitch/blob - 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
  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->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 tag_type
 180 mac_learning_learn(struct mac_learning *ml,
 181                    const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan,
 182                    uint16_t src_port)
 183 {
 184     struct mac_entry *e;
 185     struct list *bucket;
 186
 187     if (!is_learning_vlan(ml, vlan)) {
 188         return 0;
 189     }
 190
 191     if (eth_addr_is_multicast(src_mac)) {
 192         static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 30);
 193         VLOG_DBG_RL(&rl, "multicast packet source "ETH_ADDR_FMT,
 194                     ETH_ADDR_ARGS(src_mac));
 195         return 0;
 196     }
 197
 198     bucket = mac_table_bucket(ml, src_mac, vlan);
 199     e = search_bucket(bucket, src_mac, vlan);
 200     if (!e) {
 201         if (!list_is_empty(&ml->free)) {
 202             e = mac_entry_from_lru_node(ml->free.next);
 203         } else {
 204             e = mac_entry_from_lru_node(ml->lrus.next);
 205             list_remove(&e->hash_node);
 206         }
 207         memcpy(e->mac, src_mac, ETH_ADDR_LEN);
 208         list_push_front(bucket, &e->hash_node);
 209         e->port = -1;
 210         e->vlan = vlan;
 211         e->tag = make_unknown_mac_tag(ml, src_mac, vlan);
 212     }
 213
 214     /* Make the entry most-recently-used. */
 215     list_remove(&e->lru_node);
 216     list_push_back(&ml->lrus, &e->lru_node);
 217     e->expires = time_now() + MAC_ENTRY_IDLE_TIME;
 218
 219     /* Did we learn something? */
 220     if (e->port != src_port) {
 221         tag_type old_tag = e->tag;
 222         e->port = src_port;
 223         e->tag = tag_create_random();
 224         COVERAGE_INC(mac_learning_learned);
 225         return old_tag;
 226     }
 227     return 0;
 228 }
 229
 230 /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'.  Returns the port on which a
 231  * frame destined for 'dst' should be sent, -1 if unknown. */
 232 int
 233 mac_learning_lookup(const struct mac_learning *ml,
 234                     const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan)
 235 {
 236     tag_type tag = 0;
 237     return mac_learning_lookup_tag(ml, dst, vlan, &tag);
 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.
 242  *
 243  * Adds to '*tag' (which the caller must have initialized) the tag that should
 244  * be attached to any flow created based on the return value, if any, to allow
 245  * those flows to be revalidated when the MAC learning entry changes. */
 246 int
 247 mac_learning_lookup_tag(const struct mac_learning *ml,
 248                         const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan,
 249                         tag_type *tag)
 250 {
 251     if (eth_addr_is_multicast(dst) || !is_learning_vlan(ml, vlan)) {
 252         return -1;
 253     } else {
 254         struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst, vlan),
 255                                             dst, vlan);
 256         if (e) {
 257             *tag |= e->tag;
 258             return e->port;
 259         } else {
 260             *tag |= make_unknown_mac_tag(ml, dst, vlan);
 261             return -1;
 262         }
 263     }
 264 }
 265
 266 /* Expires all the mac-learning entries in 'ml'.  The tags in 'ml' are
 267  * discarded, so the client is responsible for revalidating any flows that
 268  * depend on 'ml', if necessary. */
 269 void
 270 mac_learning_flush(struct mac_learning *ml)
 271 {
 272     struct mac_entry *e;
 273     while (get_lru(ml, &e)){
 274         free_mac_entry(ml, e);
 275     }
 276 }
 277
 278 void
 279 mac_learning_run(struct mac_learning *ml, struct tag_set *set)
 280 {
 281     struct mac_entry *e;
 282     while (get_lru(ml, &e) && time_now() >= e->expires) {
 283         COVERAGE_INC(mac_learning_expired);
 284         if (set) {
 285             tag_set_add(set, e->tag);
 286         }
 287         free_mac_entry(ml, e);
 288     }
 289 }
 290
 291 void
 292 mac_learning_wait(struct mac_learning *ml)
 293 {
 294     if (!list_is_empty(&ml->lrus)) {
 295         struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next);
 296         poll_timer_wait((e->expires - time_now()) * 1000);
 297     }
 298 }