From 08a5cfb508d79387036306070abd1365cb465e9e Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Tue, 23 Dec 2008 16:57:23 -0800 Subject: [PATCH] Add support for tags to mac-learning library, and update client code. --- lib/learning-switch.c | 8 +++ lib/mac-learning.c | 125 ++++++++++++++++++++++++++++++++++-------- lib/mac-learning.h | 12 +++- secchan/in-band.c | 18 +++++- vswitchd/bridge.c | 6 ++ 5 files changed, 142 insertions(+), 27 deletions(-) diff --git a/lib/learning-switch.c b/lib/learning-switch.c index ff03ab59..5c6ca4e0 100644 --- a/lib/learning-switch.c +++ b/lib/learning-switch.c @@ -159,6 +159,10 @@ lswitch_run(struct lswitch *sw, struct rconn *rconn) { long long int now = time_msec(); + if (sw->ml) { + mac_learning_run(sw->ml, NULL); + } + /* If we're waiting for more replies, keeping waiting for up to 10 s. */ if (sw->last_reply != LLONG_MIN) { if (now - sw->last_reply > 10000) { @@ -237,6 +241,10 @@ wait_timeout(long long int started) void lswitch_wait(struct lswitch *sw) { + if (sw->ml) { + mac_learning_wait(sw->ml); + } + if (sw->last_reply != LLONG_MIN) { wait_timeout(sw->last_reply); } else if (sw->last_query != LLONG_MIN) { diff --git a/lib/mac-learning.c b/lib/mac-learning.c index c8c241e0..49dfbefa 100644 --- a/lib/mac-learning.c +++ b/lib/mac-learning.c @@ -41,6 +41,8 @@ #include "hash.h" #include "list.h" #include "openflow/openflow.h" +#include "poll-loop.h" +#include "tag.h" #include "timeval.h" #include "util.h" @@ -56,27 +58,53 @@ /* 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 mac_learning 'lrus' list. */ - time_t used; /* Last used time. */ + 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 lrus; /* All entries, least recently used at the + 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_fnv(mac, ETH_ADDR_LEN, HASH_FNV_BASIS) ^ 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) +{ + return tag_create_deterministic(hash_fnv(&ml->secret, sizeof ml->secret, + mac_table_hash(mac, vlan))); +} + static struct list * mac_table_bucket(const struct mac_learning *ml, const uint8_t mac[ETH_ADDR_LEN], uint16_t vlan) { - uint32_t hash = hash_fnv(mac, ETH_ADDR_LEN, HASH_FNV_BASIS) ^ vlan; + uint32_t hash = mac_table_hash(mac, vlan); const struct list *list = &ml->table[hash & MAC_HASH_BITS]; return (struct list *) list; } @@ -103,14 +131,15 @@ mac_learning_create(void) 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->lrus, &s->lru_node); - s->hash_node.next = NULL; + list_push_front(&ml->free, &s->lru_node); } + ml->secret = random_uint32(); return ml; } @@ -122,13 +151,15 @@ mac_learning_destroy(struct mac_learning *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 true if - * we actually learned something from this, false if it just confirms what we - * already knew. + * 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. */ -bool +tag_type mac_learning_learn(struct mac_learning *ml, const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan, uint16_t src_port) @@ -140,48 +171,98 @@ mac_learning_learn(struct mac_learning *ml, 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 false; + return 0; } bucket = mac_table_bucket(ml, src_mac, vlan); e = search_bucket(bucket, src_mac, vlan); if (!e) { - e = CONTAINER_OF(ml->lrus.next, struct mac_entry, lru_node); - memcpy(e->mac, src_mac, ETH_ADDR_LEN); - if (e->hash_node.next) { + 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->used = time_now(); + e->expires = time_now() + 60; /* Did we learn something? */ if (e->port != src_port) { + tag_type old_tag = e->tag; e->port = src_port; - return true; + e->tag = tag_create_random(); + return old_tag; } - return false; + return 0; } /* Looks up MAC 'dst' for VLAN 'vlan' in 'ml'. Returns the port on which a * frame destined for 'dst' should be sent, OFPP_FLOOD if unknown. */ uint16_t mac_learning_lookup(const struct mac_learning *ml, - const uint8_t dst[ETH_ADDR_LEN], - uint16_t vlan) + const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan) { - if (!eth_addr_is_multicast(dst)) { + 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, OFPP_FLOOD 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. */ +uint16_t +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 OFPP_FLOOD; + } else { struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst, vlan), dst, vlan); - if (e && time_now() - e->used < 60) { + if (e) { + *tag |= e->tag; return e->port; + } else { + *tag |= make_unknown_mac_tag(ml, dst, vlan); + return OFPP_FLOOD; } } - return OFPP_FLOOD; +} + +void +mac_learning_run(struct mac_learning *ml, struct tag_set *set) +{ + while (!list_is_empty(&ml->lrus)) { + struct mac_entry *e = mac_entry_from_lru_node(ml->lrus.next); + if (time_now() < e->expires) { + break; + } + if (set) { + tag_set_add(set, e->tag); + } + list_remove(&e->hash_node); + list_remove(&e->lru_node); + list_push_front(&ml->free, &e->lru_node); + } +} + +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); + } } diff --git a/lib/mac-learning.h b/lib/mac-learning.h index 7dc12be3..37ebf0bc 100644 --- a/lib/mac-learning.h +++ b/lib/mac-learning.h @@ -35,13 +35,19 @@ #define MAC_LEARNING_H 1 #include "packets.h" +#include "tag.h" struct mac_learning *mac_learning_create(void); void mac_learning_destroy(struct mac_learning *); -bool mac_learning_learn(struct mac_learning *, - const uint8_t src[ETH_ADDR_LEN], uint16_t vlan, - uint16_t src_port); +tag_type mac_learning_learn(struct mac_learning *, + const uint8_t src[ETH_ADDR_LEN], uint16_t vlan, + uint16_t src_port); uint16_t mac_learning_lookup(const struct mac_learning *, const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan); +uint16_t mac_learning_lookup_tag(const struct mac_learning *, + const uint8_t dst[ETH_ADDR_LEN], + uint16_t vlan, tag_type *tag); +void mac_learning_run(struct mac_learning *, struct tag_set *); +void mac_learning_wait(struct mac_learning *); #endif /* mac-learning.h */ diff --git a/secchan/in-band.c b/secchan/in-band.c index e2b92bb0..6069eabe 100644 --- a/secchan/in-band.c +++ b/secchan/in-band.c @@ -284,11 +284,25 @@ in_band_local_port_cb(const struct ofp_phy_port *port, void *in_band_) } } +static void +in_band_periodic_cb(void *in_band_) +{ + struct in_band_data *in_band = in_band_; + mac_learning_run(in_band->ml, NULL); +} + +static void +in_band_wait_cb(void *in_band_) +{ + struct in_band_data *in_band = in_band_; + mac_learning_wait(in_band->ml); +} + static struct hook_class in_band_hook_class = { in_band_local_packet_cb, /* local_packet_cb */ NULL, /* remote_packet_cb */ - NULL, /* periodic_cb */ - NULL, /* wait_cb */ + in_band_periodic_cb, /* periodic_cb */ + in_band_wait_cb, /* wait_cb */ NULL, /* closing_cb */ }; diff --git a/vswitchd/bridge.c b/vswitchd/bridge.c index a244b097..1f51a599 100644 --- a/vswitchd/bridge.c +++ b/vswitchd/bridge.c @@ -296,6 +296,9 @@ bridge_wait(void) rconn_recv_wait(br->rconn); } process_wait(br->secchan); + if (br->ml) { + mac_learning_wait(br->ml); + } } } @@ -482,6 +485,9 @@ bridge_run_one(struct bridge *br) bridge_process_msg(br, msg); ofpbuf_delete(msg); } + if (br->ml) { + mac_learning_run(br->ml, &br->revalidate_set); + } if (process_exited(br->secchan)) { int status = process_status(br->secchan); VLOG_ERR("%s: secchan subprocess with pid %ld died unexpectedly (%s)", -- 2.30.2