X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;ds=sidebyside;f=lib%2Fmac-learning.c;h=b010406c72ff594fda90370fc700853dcd26f4fb;hb=44f2560c67fca0d5712a3bec309e4e93e9e63a7b;hp=eeebce86629b32b3e66b0481866cdc8bf29a0b61;hpb=a14bc59fb8f27db193d74662dc9c5cb8237177ef;p=sliver-openvswitch.git diff --git a/lib/mac-learning.c b/lib/mac-learning.c index eeebce866..b010406c7 100644 --- a/lib/mac-learning.c +++ b/lib/mac-learning.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009 Nicira Networks. + * Copyright (c) 2008, 2009, 2010, 2011 Nicira Networks. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -21,6 +21,7 @@ #include #include +#include "bitmap.h" #include "coverage.h" #include "hash.h" #include "list.h" @@ -28,10 +29,21 @@ #include "tag.h" #include "timeval.h" #include "util.h" - -#define THIS_MODULE VLM_mac_learning #include "vlog.h" +VLOG_DEFINE_THIS_MODULE(mac_learning); + +COVERAGE_DEFINE(mac_learning_learned); +COVERAGE_DEFINE(mac_learning_expired); + +/* Returns the number of seconds since 'e' was last learned. */ +int +mac_entry_age(const struct mac_entry *e) +{ + time_t remaining = e->expires - time_now(); + return MAC_ENTRY_IDLE_TIME - remaining; +} + static uint32_t mac_table_hash(const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) { @@ -61,7 +73,7 @@ mac_table_bucket(const struct mac_learning *ml, uint16_t vlan) { uint32_t hash = mac_table_hash(mac, vlan); - const struct list *list = &ml->table[hash & MAC_HASH_BITS]; + const struct list *list = &ml->table[hash & MAC_HASH_MASK]; return (struct list *) list; } @@ -70,7 +82,7 @@ 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) { + LIST_FOR_EACH (e, hash_node, bucket) { if (eth_addr_equals(e->mac, mac) && e->vlan == vlan) { return e; } @@ -93,16 +105,6 @@ get_lru(struct mac_learning *ml, struct mac_entry **e) } } -/* 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) @@ -121,6 +123,7 @@ mac_learning_create(void) list_push_front(&ml->free, &s->lru_node); } ml->secret = random_uint32(); + ml->flood_vlans = NULL; return ml; } @@ -128,33 +131,62 @@ mac_learning_create(void) void mac_learning_destroy(struct mac_learning *ml) { + if (ml) { + bitmap_free(ml->flood_vlans); + } 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. +/* Provides a bitmap of VLANs which have learning disabled, that is, VLANs on + * which all packets are flooded. It takes ownership of the bitmap. Returns + * true if the set has changed from the previous value. */ +bool +mac_learning_set_flood_vlans(struct mac_learning *ml, unsigned long *bitmap) +{ + bool ret = (bitmap == NULL + ? ml->flood_vlans != NULL + : (ml->flood_vlans == NULL + || !bitmap_equal(bitmap, ml->flood_vlans, 4096))); + + bitmap_free(ml->flood_vlans); + ml->flood_vlans = bitmap; + + return ret; +} + +static bool +is_learning_vlan(const struct mac_learning *ml, uint16_t vlan) +{ + return !(ml->flood_vlans && bitmap_is_set(ml->flood_vlans, vlan)); +} + +/* Returns true if 'src_mac' may be learned on 'vlan' for 'ml'. + * Returns false if 'ml' is NULL, if src_mac is not valid for learning, or if + * 'vlan' is configured on 'ml' to flood all packets. */ +bool +mac_learning_may_learn(const struct mac_learning *ml, + const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan) +{ + return ml && is_learning_vlan(ml, vlan) && !eth_addr_is_multicast(src_mac); +} + +/* Searches 'ml' for and returns a MAC learning entry for 'src_mac' in 'vlan', + * inserting a new entry if necessary. The caller must have already verified, + * by calling mac_learning_may_learn(), that 'src_mac' and 'vlan' are + * learnable. * - * 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) + * If the returned MAC entry is new (as may be determined by calling + * mac_entry_is_new()), then the caller must pass the new entry to + * mac_learning_changed(). The caller must also initialize the new entry's + * 'port' member. Otherwise calling those functions is at the caller's + * discretion. */ +struct mac_entry * +mac_learning_insert(struct mac_learning *ml, + const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan) { 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) { @@ -164,65 +196,78 @@ mac_learning_learn(struct mac_learning *ml, 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; + memcpy(e->mac, src_mac, ETH_ADDR_LEN); e->vlan = vlan; - e->tag = make_unknown_mac_tag(ml, src_mac, vlan); + e->tag = 0; + e->grat_arp_lock = TIME_MIN; } - /* Make the entry most-recently-used. */ + /* Mark 'e' as 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; + e->expires = time_now() + MAC_ENTRY_IDLE_TIME; + + return e; } -/* 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) +/* Changes 'e''s tag to a new, randomly selected one, and returns the tag that + * would have been previously used for this entry's MAC and VLAN (either before + * 'e' was inserted, if it is new, or otherwise before its port was updated.) + * + * The client should call this function after obtaining a MAC learning entry + * from mac_learning_insert(), if the entry is either new or if its learned + * port has changed. */ +tag_type +mac_learning_changed(struct mac_learning *ml, struct mac_entry *e) { - tag_type tag = 0; - return mac_learning_lookup_tag(ml, dst, vlan, &tag); + tag_type old_tag = e->tag; + + COVERAGE_INC(mac_learning_learned); + + e->tag = tag_create_random(); + return old_tag ? old_tag : make_unknown_mac_tag(ml, e->mac, e->vlan); } -/* 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) +/* Looks up MAC 'dst' for VLAN 'vlan' in 'ml' and returns the associated MAC + * learning entry, if any. If 'tag' is nonnull, then the tag that associates + * 'dst' and 'vlan' with its currently learned port will be OR'd into + * '*tag'. */ +struct mac_entry * +mac_learning_lookup(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; + /* No tag because the treatment of multicast destinations never + * changes. */ + return NULL; + } else if (!is_learning_vlan(ml, vlan)) { + /* We don't tag this property. The set of learning VLANs changes so + * rarely that we revalidate every flow when it changes. */ + return NULL; } 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; + assert(e == NULL || e->tag != 0); + if (tag) { + /* Tag either the learned port or the lack thereof. */ + *tag |= e ? e->tag : make_unknown_mac_tag(ml, dst, vlan); } + return e; } } +/* Expires 'e' from the 'ml' hash table. 'e' must not already be on the free + * list. */ +void +mac_learning_expire(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); +} + /* 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. */ @@ -231,7 +276,7 @@ mac_learning_flush(struct mac_learning *ml) { struct mac_entry *e; while (get_lru(ml, &e)){ - free_mac_entry(ml, e); + mac_learning_expire(ml, e); } } @@ -244,7 +289,7 @@ mac_learning_run(struct mac_learning *ml, struct tag_set *set) if (set) { tag_set_add(set, e->tag); } - free_mac_entry(ml, e); + mac_learning_expire(ml, e); } } @@ -253,6 +298,6 @@ 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); + poll_timer_wait_until(e->expires * 1000LL); } }