From db8077c315f12fd523ace965cc22778ed8d5939a Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Tue, 22 Mar 2011 09:47:02 -0700 Subject: [PATCH] mac-learning: Refactor to increase generality. In an upcoming commit I want to store a pointer in MAC learning entries in the bridge, instead of an integer port number. The MAC learning library has other clients, and the others do not gracefully fit this new model, so in fact the data will have to become a union. However, this does not fit well with the current mac_learning API, since mac_learning_learn() currently initializes and compares the data. It seems better to break up the API so that only the client has to know the data's format and how to initialize it or compare it. This commit makes this possible. This commit doesn't change the type of the data stored in a MAC learning entry yet. As a side effect this commit has the benefit that clients that don't need gratuitous ARP locking don't have to specify any policy for it at all. --- lib/learning-switch.c | 17 +++-- lib/mac-learning.c | 151 ++++++++++++++++++------------------------ lib/mac-learning.h | 65 ++++++++++++------ ofproto/ofproto.c | 34 ++++++---- vswitchd/bridge.c | 56 ++++++++-------- 5 files changed, 172 insertions(+), 151 deletions(-) diff --git a/lib/learning-switch.c b/lib/learning-switch.c index ca970540..5fa3a53b 100644 --- a/lib/learning-switch.c +++ b/lib/learning-switch.c @@ -324,12 +324,15 @@ lswitch_choose_destination(struct lswitch *sw, const struct flow *flow) uint16_t out_port; /* Learn the source MAC. */ - if (sw->ml) { - if (mac_learning_learn(sw->ml, flow->dl_src, 0, flow->in_port, - GRAT_ARP_LOCK_NONE)) { + if (mac_learning_may_learn(sw->ml, flow->dl_src, 0)) { + struct mac_entry *mac = mac_learning_insert(sw->ml, flow->dl_src, 0); + if (mac_entry_is_new(mac) || mac->port != flow->in_port) { VLOG_DBG_RL(&rl, "%016llx: learned that "ETH_ADDR_FMT" is on " "port %"PRIu16, sw->datapath_id, ETH_ADDR_ARGS(flow->dl_src), flow->in_port); + + mac->port = flow->in_port; + mac_learning_changed(sw->ml, mac); } } @@ -340,9 +343,11 @@ lswitch_choose_destination(struct lswitch *sw, const struct flow *flow) out_port = OFPP_FLOOD; if (sw->ml) { - int learned_port = mac_learning_lookup(sw->ml, flow->dl_dst, 0, NULL); - if (learned_port >= 0) { - out_port = learned_port; + struct mac_entry *mac; + + mac = mac_learning_lookup(sw->ml, flow->dl_dst, 0, NULL); + if (mac) { + out_port = mac->port; if (out_port == flow->in_port) { /* Don't send a packet back out its input port. */ return OFPP_NONE; diff --git a/lib/mac-learning.c b/lib/mac-learning.c index af46e3cc..0bee1523 100644 --- a/lib/mac-learning.c +++ b/lib/mac-learning.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009, 2010 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. @@ -170,37 +170,33 @@ is_learning_vlan(const struct mac_learning *ml, uint16_t vlan) return !(ml->flood_vlans && bitmap_is_set(ml->flood_vlans, vlan)); } -/* 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. +/* 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. * - * 'lock_type' specifies whether the entry should be locked or existing locks - * are check. */ -tag_type -mac_learning_learn(struct mac_learning *ml, - const uint8_t src_mac[ETH_ADDR_LEN], uint16_t vlan, - uint16_t src_port, enum grat_arp_lock_type lock_type) + * 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 (!is_learning_vlan(ml, vlan)) { - return 0; - } - - 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) { @@ -210,80 +206,65 @@ 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; } - if (lock_type != GRAT_ARP_LOCK_CHECK || time_now() >= e->grat_arp_lock) { - /* Make the entry most-recently-used. */ - list_remove(&e->lru_node); - list_push_back(&ml->lrus, &e->lru_node); - e->expires = time_now() + MAC_ENTRY_IDLE_TIME; - if (lock_type == GRAT_ARP_LOCK_SET) { - e->grat_arp_lock = time_now() + MAC_GRAT_ARP_LOCK_TIME; - } - - /* 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; - } - } + /* Mark 'e' as recently used. */ + list_remove(&e->lru_node); + list_push_back(&ml->lrus, &e->lru_node); + e->expires = time_now() + MAC_ENTRY_IDLE_TIME; - return 0; + 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. 'is_grat_arp_locked' - * is an optional parameter that returns whether the entry is currently - * locked. */ -int -mac_learning_lookup(const struct mac_learning *ml, - const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan, - bool *is_grat_arp_locked) +/* 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, is_grat_arp_locked); + 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. - * - * 'is_grat_arp_locked' is an optional parameter that returns whether the entry - * is currently locked.*/ -int -mac_learning_lookup_tag(const struct mac_learning *ml, - const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan, - tag_type *tag, bool *is_grat_arp_locked) +/* 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) || !is_learning_vlan(ml, vlan)) { - return -1; + if (eth_addr_is_multicast(dst)) { + /* 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; - - if (is_grat_arp_locked) { - *is_grat_arp_locked = time_now() < e->grat_arp_lock; - } - - 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; } } diff --git a/lib/mac-learning.h b/lib/mac-learning.h index 89a4e909..c5c94bb3 100644 --- a/lib/mac-learning.h +++ b/lib/mac-learning.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009, 2010 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 "list.h" #include "packets.h" #include "tag.h" +#include "timeval.h" #define MAC_HASH_BITS 10 #define MAC_HASH_MASK (MAC_HASH_SIZE - 1) @@ -35,12 +36,6 @@ * relearning based on a reflection from a bond slave. */ #define MAC_GRAT_ARP_LOCK_TIME 5 -enum grat_arp_lock_type { - GRAT_ARP_LOCK_NONE, - GRAT_ARP_LOCK_SET, - GRAT_ARP_LOCK_CHECK -}; - /* A MAC learning table entry. */ struct mac_entry { struct list hash_node; /* Element in a mac_learning 'table' list. */ @@ -55,6 +50,27 @@ struct mac_entry { int mac_entry_age(const struct mac_entry *); +/* Returns true if mac_learning_insert() just created 'mac' and the caller has + * not yet properly initialized it. */ +static inline bool mac_entry_is_new(const struct mac_entry *mac) +{ + return !mac->tag; +} + +/* Sets a gratuitous ARP lock on 'mac' that will expire in + * MAC_GRAT_ARP_LOCK_TIME seconds. */ +static inline void mac_entry_set_grat_arp_lock(struct mac_entry *mac) +{ + mac->grat_arp_lock = time_now() + MAC_GRAT_ARP_LOCK_TIME; +} + +/* Returns true if a gratuitous ARP lock is in effect on 'mac', false if none + * has ever been asserted or if it has expired. */ +static inline bool mac_entry_is_grat_arp_locked(const struct mac_entry *mac) +{ + return time_now() >= mac->grat_arp_lock; +} + /* MAC learning table. */ struct mac_learning { struct list free; /* Not-in-use entries. */ @@ -66,23 +82,32 @@ struct mac_learning { unsigned long *flood_vlans; /* Bitmap of learning disabled VLANs. */ }; +/* Basics. */ struct mac_learning *mac_learning_create(void); void mac_learning_destroy(struct mac_learning *); + +void mac_learning_run(struct mac_learning *, struct tag_set *); +void mac_learning_wait(struct mac_learning *); + +/* Configuration. */ bool mac_learning_set_flood_vlans(struct mac_learning *, unsigned long *bitmap); -tag_type mac_learning_learn(struct mac_learning *, - const uint8_t src[ETH_ADDR_LEN], uint16_t vlan, - uint16_t src_port, enum grat_arp_lock_type - lock_type); -int mac_learning_lookup(const struct mac_learning *, - const uint8_t dst[ETH_ADDR_LEN], uint16_t vlan, - bool *is_grat_arp_locked); -int mac_learning_lookup_tag(const struct mac_learning *, - const uint8_t dst[ETH_ADDR_LEN], - uint16_t vlan, tag_type *tag, - bool *is_grat_arp_locked); + +/* Learning. */ +bool mac_learning_may_learn(const struct mac_learning *, + const uint8_t src_mac[ETH_ADDR_LEN], + uint16_t vlan); +struct mac_entry *mac_learning_insert(struct mac_learning *, + const uint8_t src[ETH_ADDR_LEN], + uint16_t vlan); +tag_type mac_learning_changed(struct mac_learning *, struct mac_entry *); + +/* Lookup. */ +struct mac_entry *mac_learning_lookup(const struct mac_learning *, + const uint8_t dst[ETH_ADDR_LEN], + uint16_t vlan, tag_type *); + +/* Flushing. */ void mac_learning_flush(struct mac_learning *); -void mac_learning_run(struct mac_learning *, struct tag_set *); -void mac_learning_wait(struct mac_learning *); #endif /* mac-learning.h */ diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c index e914bbf8..fea91196 100644 --- a/ofproto/ofproto.c +++ b/ofproto/ofproto.c @@ -5262,7 +5262,7 @@ default_normal_ofhook_cb(const struct flow *flow, const struct ofpbuf *packet, uint16_t *nf_output_iface, void *ofproto_) { struct ofproto *ofproto = ofproto_; - int out_port; + struct mac_entry *dst_mac; /* Drop frames for reserved multicast addresses. */ if (eth_addr_is_reserved(flow->dl_dst)) { @@ -5270,31 +5270,37 @@ default_normal_ofhook_cb(const struct flow *flow, const struct ofpbuf *packet, } /* Learn source MAC (but don't try to learn from revalidation). */ - if (packet != NULL) { - tag_type rev_tag = mac_learning_learn(ofproto->ml, flow->dl_src, - 0, flow->in_port, - GRAT_ARP_LOCK_NONE); - if (rev_tag) { + if (packet != NULL + && mac_learning_may_learn(ofproto->ml, flow->dl_src, 0)) { + struct mac_entry *src_mac; + + src_mac = mac_learning_insert(ofproto->ml, flow->dl_src, 0); + if (mac_entry_is_new(src_mac) || src_mac->port != flow->in_port) { /* The log messages here could actually be useful in debugging, * so keep the rate limit relatively high. */ static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 300); VLOG_DBG_RL(&rl, "learned that "ETH_ADDR_FMT" is on port %"PRIu16, ETH_ADDR_ARGS(flow->dl_src), flow->in_port); - ofproto_revalidate(ofproto, rev_tag); + + ofproto_revalidate(ofproto, + mac_learning_changed(ofproto->ml, src_mac)); + src_mac->port = flow->in_port; } } /* Determine output port. */ - out_port = mac_learning_lookup_tag(ofproto->ml, flow->dl_dst, 0, tags, - NULL); - if (out_port < 0) { + dst_mac = mac_learning_lookup(ofproto->ml, flow->dl_dst, 0, tags); + if (!dst_mac) { flood_packets(ofproto, flow->in_port, OFPPC_NO_FLOOD, nf_output_iface, odp_actions); - } else if (out_port != flow->in_port) { - nl_msg_put_u32(odp_actions, ODP_ACTION_ATTR_OUTPUT, out_port); - *nf_output_iface = out_port; } else { - /* Drop. */ + int out_port = dst_mac->port; + if (out_port != flow->in_port) { + nl_msg_put_u32(odp_actions, ODP_ACTION_ATTR_OUTPUT, out_port); + *nf_output_iface = out_port; + } else { + /* Drop. */ + } } return true; diff --git a/vswitchd/bridge.c b/vswitchd/bridge.c index 0a6501a3..0bb9cc22 100644 --- a/vswitchd/bridge.c +++ b/vswitchd/bridge.c @@ -2770,27 +2770,34 @@ static void update_learning_table(struct bridge *br, const struct flow *flow, int vlan, struct port *in_port) { - enum grat_arp_lock_type lock_type; - tag_type rev_tag; - - /* We don't want to learn from gratuitous ARP packets that are reflected - * back over bond slaves so we lock the learning table. */ - lock_type = !is_gratuitous_arp(flow) ? GRAT_ARP_LOCK_NONE : - (in_port->n_ifaces == 1) ? GRAT_ARP_LOCK_SET : - GRAT_ARP_LOCK_CHECK; - - rev_tag = mac_learning_learn(br->ml, flow->dl_src, vlan, in_port->port_idx, - lock_type); - if (rev_tag) { + struct mac_entry *mac; + + if (!mac_learning_may_learn(br->ml, flow->dl_src, vlan)) { + return; + } + + mac = mac_learning_insert(br->ml, flow->dl_src, vlan); + if (is_gratuitous_arp(flow)) { + /* We don't want to learn from gratuitous ARP packets that are + * reflected back over bond slaves so we lock the learning table. */ + if (in_port->n_ifaces == 1) { + mac_entry_set_grat_arp_lock(mac); + } else if (mac_entry_is_grat_arp_locked(mac)) { + return; + } + } + + if (mac_entry_is_new(mac) || mac->port != in_port->port_idx) { /* The log messages here could actually be useful in debugging, * so keep the rate limit relatively high. */ - static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, - 300); + static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 300); VLOG_DBG_RL(&rl, "bridge %s: learned that "ETH_ADDR_FMT" is " "on port %s in VLAN %d", br->name, ETH_ADDR_ARGS(flow->dl_src), in_port->name, vlan); - ofproto_revalidate(br->ofproto, rev_tag); + + mac->port = in_port->port_idx; + ofproto_revalidate(br->ofproto, mac_learning_changed(br->ml, mac)); } } @@ -2877,8 +2884,7 @@ is_admissible(struct bridge *br, const struct flow *flow, bool have_packet, /* Packets received on non-LACP bonds need special attention to avoid * duplicates. */ if (in_port->n_ifaces > 1 && !lacp_negotiated(in_port->lacp)) { - int src_idx; - bool is_grat_arp_locked; + struct mac_entry *mac; if (eth_addr_is_multicast(flow->dl_dst)) { *tags |= port_get_active_iface_tag(in_port); @@ -2895,10 +2901,9 @@ is_admissible(struct bridge *br, const struct flow *flow, bool have_packet, * to the exception is if we locked the learning table to avoid * reflections on bond slaves. If this is the case, just drop the * packet now. */ - src_idx = mac_learning_lookup(br->ml, flow->dl_src, vlan, - &is_grat_arp_locked); - if (src_idx != -1 && src_idx != in_port->port_idx && - (!is_gratuitous_arp(flow) || is_grat_arp_locked)) { + mac = mac_learning_lookup(br->ml, flow->dl_src, vlan, NULL); + if (mac && mac->port != in_port->port_idx && + (!is_gratuitous_arp(flow) || mac_entry_is_grat_arp_locked(mac))) { return false; } } @@ -2916,8 +2921,8 @@ process_flow(struct bridge *br, const struct flow *flow, { struct port *in_port; struct port *out_port; + struct mac_entry *mac; int vlan; - int out_port_idx; /* Check whether we should drop packets in this flow. */ if (!is_admissible(br, flow, packet != NULL, tags, &vlan, &in_port)) { @@ -2931,10 +2936,9 @@ process_flow(struct bridge *br, const struct flow *flow, } /* Determine output port. */ - out_port_idx = mac_learning_lookup_tag(br->ml, flow->dl_dst, vlan, tags, - NULL); - if (out_port_idx >= 0 && out_port_idx < br->n_ports) { - out_port = br->ports[out_port_idx]; + mac = mac_learning_lookup(br->ml, flow->dl_dst, vlan, tags); + if (mac && mac->port >= 0 && mac->port < br->n_ports) { + out_port = br->ports[mac->port]; } else if (!packet && !eth_addr_is_multicast(flow->dl_dst)) { /* If we are revalidating but don't have a learning entry then * eject the flow. Installing a flow that floods packets opens -- 2.30.2