From 064af42167bf4fc9aaea2702d80ce08074b889c0 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 8 Jul 2009 13:19:16 -0700 Subject: Import from old repository commit 61ef2b42a9c4ba8e1600f15bb0236765edc2ad45. --- lib/mac-learning.c | 285 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 285 insertions(+) create mode 100644 lib/mac-learning.c (limited to 'lib/mac-learning.c') diff --git a/lib/mac-learning.c b/lib/mac-learning.c new file mode 100644 index 00000000..f0366808 --- /dev/null +++ b/lib/mac-learning.c @@ -0,0 +1,285 @@ +/* + * Copyright (c) 2008, 2009 Nicira Networks. + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include +#include "mac-learning.h" + +#include +#include +#include + +#include "coverage.h" +#include "hash.h" +#include "list.h" +#include "poll-loop.h" +#include "tag.h" +#include "timeval.h" +#include "util.h" + +#define THIS_MODULE VLM_mac_learning +#include "vlog.h" + +#define MAC_HASH_BITS 10 +#define MAC_HASH_MASK (MAC_HASH_SIZE - 1) +#define MAC_HASH_SIZE (1u << MAC_HASH_BITS) + +#define MAC_MAX 1024 + +/* A MAC learning table entry. */ +struct mac_entry { + struct list hash_node; /* Element in a mac_learning 'table' list. */ + struct list lru_node; /* Element in 'lrus' or 'free' list. */ + time_t expires; /* Expiration time. */ + uint8_t mac[ETH_ADDR_LEN]; /* Known MAC address. */ + uint16_t vlan; /* VLAN tag. */ + int port; /* Port on which MAC was most recently seen. */ + tag_type tag; /* Tag for this learning entry. */ +}; + +/* MAC learning table. */ +struct mac_learning { + struct list free; /* Not-in-use entries. */ + struct list lrus; /* In-use entries, least recently used at the + front, most recently used at the back. */ + struct list table[MAC_HASH_SIZE]; /* Hash table. */ + struct mac_entry entries[MAC_MAX]; /* All entries. */ + uint32_t secret; /* Secret for */ +}; + +static uint32_t +mac_table_hash(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) +{ + return hash_bytes(mac, ETH_ADDR_LEN, vlan); +} + +static struct mac_entry * +mac_entry_from_lru_node(struct list *list) +{ + return CONTAINER_OF(list, struct mac_entry, lru_node); +} + +/* Returns a tag that represents that 'mac' is on an unknown port in 'vlan'. + * (When we learn where 'mac' is in 'vlan', this allows flows that were + * flooded to be revalidated.) */ +static tag_type +make_unknown_mac_tag(const struct mac_learning *ml, + const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) +{ + uint32_t h = hash_int(ml->secret, mac_table_hash(mac, vlan)); + return tag_create_deterministic(h); +} + +static struct list * +mac_table_bucket(const struct mac_learning *ml, + const uint8_t mac[ETH_ADDR_LEN], + uint16_t vlan) +{ + uint32_t hash = mac_table_hash(mac, vlan); + const struct list *list = &ml->table[hash & MAC_HASH_BITS]; + return (struct list *) list; +} + +static struct mac_entry * +search_bucket(struct list *bucket, const uint8_t mac[ETH_ADDR_LEN], + uint16_t vlan) +{ + struct mac_entry *e; + LIST_FOR_EACH (e, struct mac_entry, hash_node, bucket) { + if (eth_addr_equals(e->mac, mac) && e->vlan == vlan) { + return e; + } + } + return NULL; +} + +/* If the LRU list is not empty, stores the least-recently-used entry in '*e' + * and returns true. Otherwise, if the LRU list is empty, stores NULL in '*e' + * and return false. */ +static bool +get_lru(struct mac_learning *ml, struct mac_entry **e) +{ + if (!list_is_empty(&ml->lrus)) { + *e = mac_entry_from_lru_node(ml->lrus.next); + return true; + } else { + *e = NULL; + return false; + } +} + +/* Removes 'e' from the 'ml' hash table. 'e' must not already be on the free + * list. */ +static void +free_mac_entry(struct mac_learning *ml, struct mac_entry *e) +{ + list_remove(&e->hash_node); + list_remove(&e->lru_node); + list_push_front(&ml->free, &e->lru_node); +} + +/* Creates and returns a new MAC learning table. */ +struct mac_learning * +mac_learning_create(void) +{ + struct mac_learning *ml; + int i; + + ml = xmalloc(sizeof *ml); + list_init(&ml->lrus); + list_init(&ml->free); + for (i = 0; i < MAC_HASH_SIZE; i++) { + list_init(&ml->table[i]); + } + for (i = 0; i < MAC_MAX; i++) { + struct mac_entry *s = &ml->entries[i]; + list_push_front(&ml->free, &s->lru_node); + } + ml->secret = random_uint32(); + return ml; +} + +/* Destroys MAC learning table 'ml'. */ +void +mac_learning_destroy(struct mac_learning *ml) +{ + free(ml); +} + +/* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was + * just observed arriving from 'src_port' on the given 'vlan'. + * + * Returns nonzero if we actually learned something from this, zero if it just + * confirms what we already knew. The nonzero return value is the tag of flows + * that now need revalidation. + * + * The 'vlan' parameter is used to maintain separate per-VLAN learning tables. + * Specify 0 if this behavior is undesirable. */ +tag_type +mac_learning_learn(struct mac_learning *ml, + const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan, + uint16_t src_port) +{ + struct mac_entry *e; + struct list *bucket; + + if (eth_addr_is_multicast(src_mac)) { + static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 30); + VLOG_DBG_RL(&rl, "multicast packet source "ETH_ADDR_FMT, + ETH_ADDR_ARGS(src_mac)); + return 0; + } + + bucket = mac_table_bucket(ml, src_mac, vlan); + e = search_bucket(bucket, src_mac, vlan); + if (!e) { + if (!list_is_empty(&ml->free)) { + e = mac_entry_from_lru_node(ml->free.next); + } else { + e = mac_entry_from_lru_node(ml->lrus.next); + list_remove(&e->hash_node); + } + memcpy(e->mac, src_mac, ETH_ADDR_LEN); + list_push_front(bucket, &e->hash_node); + e->port = -1; + e->vlan = vlan; + e->tag = make_unknown_mac_tag(ml, src_mac, vlan); + } + + /* Make the entry most-recently-used. */ + list_remove(&e->lru_node); + list_push_back(&ml->lrus, &e->lru_node); + e->expires = time_now() + 60; + + /* Did we learn something? */ + if (e->port != src_port) { + tag_type old_tag = e->tag; + e->port = src_port; + e->tag = tag_create_random(); + COVERAGE_INC(mac_learning_learned); + return old_tag; + } + return 0; +} + +/* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'. Returns the port on which a + * frame destined for 'dst' should be sent, -1 if unknown. */ +int +mac_learning_lookup(const struct mac_learning *ml, + const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan) +{ + tag_type tag = 0; + return mac_learning_lookup_tag(ml, dst, vlan, &tag); +} + +/* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'. Returns the port on which a + * frame destined for 'dst' should be sent, -1 if unknown. + * + * Adds to '*tag' (which the caller must have initialized) the tag that should + * be attached to any flow created based on the return value, if any, to allow + * those flows to be revalidated when the MAC learning entry changes. */ +int +mac_learning_lookup_tag(const struct mac_learning *ml, + const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan, + tag_type *tag) +{ + if (eth_addr_is_multicast(dst)) { + return -1; + } else { + struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst, vlan), + dst, vlan); + if (e) { + *tag |= e->tag; + return e->port; + } else { + *tag |= make_unknown_mac_tag(ml, dst, vlan); + return -1; + } + } +} + +/* Expires all the mac-learning entries in 'ml'. The tags in 'ml' are + * discarded, so the client is responsible for revalidating any flows that + * depend on 'ml', if necessary. */ +void +mac_learning_flush(struct mac_learning *ml) +{ + struct mac_entry *e; + while (get_lru(ml, &e)){ + free_mac_entry(ml, e); + } +} + +void +mac_learning_run(struct mac_learning *ml, struct tag_set *set) +{ + struct mac_entry *e; + while (get_lru(ml, &e) && time_now() >= e->expires) { + COVERAGE_INC(mac_learning_expired); + if (set) { + tag_set_add(set, e->tag); + } + free_mac_entry(ml, e); + } +} + +void +mac_learning_wait(struct mac_learning *ml) +{ + if (!list_is_empty(&ml->lrus)) { + struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next); + poll_timer_wait((e->expires - time_now()) * 1000); + } +} -- cgit v1.2.3