From b5e9402df53a1f0cd745bf8b91c246e1c5e4b11d Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Tue, 9 Sep 2008 14:15:57 -0700 Subject: [PATCH] Implement 802.1D Spanning Tree Protocol. --- datapath/datapath.c | 84 +- datapath/datapath.h | 19 +- datapath/dp_dev.c | 2 +- datapath/forward.c | 53 +- datapath/forward.h | 11 +- include/Makefile.am | 1 + include/openflow.h | 31 +- include/stp.h | 107 +++ include/vlog-modules.def | 1 + lib/Makefile.am | 1 + lib/learning-switch.c | 88 +- lib/stp.c | 1064 ++++++++++++++++++++++++ secchan/secchan.c | 736 ++++++++++++++-- switch/datapath.c | 128 +-- tests/Makefile.am | 30 +- tests/test-stp-ieee802.1d-1998 | 12 + tests/test-stp-ieee802.1d-2004-fig17.4 | 31 + tests/test-stp-ieee802.1d-2004-fig17.6 | 14 + tests/test-stp-ieee802.1d-2004-fig17.7 | 17 + tests/test-stp-iol-io-1.1 | 25 + tests/test-stp-iol-io-1.2 | 14 + tests/test-stp-iol-io-1.4 | 13 + tests/test-stp-iol-io-1.5 | 40 + tests/test-stp-iol-op-1.1 | 7 + tests/test-stp-iol-op-1.4 | 8 + tests/test-stp-iol-op-3.1 | 11 + tests/test-stp-iol-op-3.3 | 11 + tests/test-stp-iol-op-3.4 | 11 + tests/test-stp.c | 661 +++++++++++++++ tests/test-stp.sh | 7 + 30 files changed, 3013 insertions(+), 225 deletions(-) create mode 100644 include/stp.h create mode 100644 lib/stp.c create mode 100644 tests/test-stp-ieee802.1d-1998 create mode 100644 tests/test-stp-ieee802.1d-2004-fig17.4 create mode 100644 tests/test-stp-ieee802.1d-2004-fig17.6 create mode 100644 tests/test-stp-ieee802.1d-2004-fig17.7 create mode 100644 tests/test-stp-iol-io-1.1 create mode 100644 tests/test-stp-iol-io-1.2 create mode 100644 tests/test-stp-iol-io-1.4 create mode 100644 tests/test-stp-iol-io-1.5 create mode 100644 tests/test-stp-iol-op-1.1 create mode 100644 tests/test-stp-iol-op-1.4 create mode 100644 tests/test-stp-iol-op-3.1 create mode 100644 tests/test-stp-iol-op-3.3 create mode 100644 tests/test-stp-iol-op-3.4 create mode 100644 tests/test-stp.c create mode 100755 tests/test-stp.sh diff --git a/datapath/datapath.c b/datapath/datapath.c index d405fc152..107ac1470 100644 --- a/datapath/datapath.c +++ b/datapath/datapath.c @@ -65,30 +65,10 @@ MODULE_PARM(serial_num, "s"); /* Number of milliseconds between runs of the maintenance thread. */ #define MAINT_SLEEP_MSECS 1000 -enum br_port_flags { - BRPF_NO_FLOOD = 1 << 0, -}; - -enum br_port_status { - BRPS_PORT_DOWN = 1 << 0, - BRPS_LINK_DOWN = 1 << 1, -}; - #define UINT32_MAX 4294967295U #define UINT16_MAX 65535 #define MAX(X, Y) ((X) > (Y) ? (X) : (Y)) -struct net_bridge_port { - u16 port_no; - u32 flags; /* BRPF_* flags */ - u32 status; /* BRPS_* flags */ - spinlock_t lock; - struct work_struct port_task; - struct datapath *dp; - struct net_device *dev; - struct list_head node; /* Element in datapath.ports. */ -}; - static struct genl_family dp_genl_family; static struct genl_multicast_group mc_group; @@ -485,7 +465,7 @@ do_port_input(struct net_bridge_port *p, struct sk_buff *skb) { /* Push the Ethernet header back on. */ skb_push(skb, ETH_HLEN); - fwd_port_input(p->dp->chain, skb, p->port_no); + fwd_port_input(p->dp->chain, skb, p); } /* @@ -537,7 +517,7 @@ static inline unsigned packet_length(const struct sk_buff *skb) static int output_all(struct datapath *dp, struct sk_buff *skb, int flood) { - u32 disable = flood ? BRPF_NO_FLOOD : 0; + u32 disable = flood ? OFPPFL_NO_FLOOD : 0; struct net_bridge_port *p; int prev_port = -1; @@ -550,12 +530,12 @@ output_all(struct datapath *dp, struct sk_buff *skb, int flood) kfree_skb(skb); return -ENOMEM; } - dp_output_port(dp, clone, prev_port); + dp_output_port(dp, clone, prev_port, 0); } prev_port = p->port_no; } if (prev_port != -1) - dp_output_port(dp, skb, prev_port); + dp_output_port(dp, skb, prev_port, 0); else kfree_skb(skb); @@ -594,7 +574,8 @@ static int xmit_skb(struct sk_buff *skb) /* Takes ownership of 'skb' and transmits it to 'out_port' on 'dp'. */ -int dp_output_port(struct datapath *dp, struct sk_buff *skb, int out_port) +int dp_output_port(struct datapath *dp, struct sk_buff *skb, int out_port, + int ignore_no_fwd) { BUG_ON(!skb); switch (out_port){ @@ -610,10 +591,8 @@ int dp_output_port(struct datapath *dp, struct sk_buff *skb, int out_port) return xmit_skb(skb); case OFPP_TABLE: { - struct net_bridge_port *p = skb->dev->br_port; - int retval; - retval = run_flow_through_tables(dp->chain, skb, - p ? p->port_no : OFPP_LOCAL); + int retval = run_flow_through_tables(dp->chain, skb, + skb->dev->br_port); if (retval) kfree_skb(skb); return retval; @@ -645,6 +624,10 @@ int dp_output_port(struct datapath *dp, struct sk_buff *skb, int out_port) printk("can't directly forward to input port\n"); return -EINVAL; } + if (p->flags & OFPPFL_NO_FWD && !ignore_no_fwd) { + kfree_skb(skb); + return 0; + } skb->dev = p->dev; return xmit_skb(skb); } @@ -713,13 +696,15 @@ static void fill_port_desc(struct net_bridge_port *p, struct ofp_phy_port *desc) desc->features = 0; desc->speed = 0; + if (p->port_no < 255) { + /* FIXME: this is a layering violation and should really be + * done in the secchan, as with OFPC_STP in + * OFP_SUPPORTED_CAPABILITIES. */ + desc->features |= OFPPF_STP; + } + spin_lock_irqsave(&p->lock, flags); - if (p->flags & BRPF_NO_FLOOD) - desc->flags |= htonl(OFPPFL_NO_FLOOD); - else if (p->status & BRPS_PORT_DOWN) - desc->flags |= htonl(OFPPFL_PORT_DOWN); - else if (p->status & BRPS_LINK_DOWN) - desc->flags |= htonl(OFPPFL_LINK_DOWN); + desc->flags = htonl(p->flags | p->status); spin_unlock_irqrestore(&p->lock, flags); #if LINUX_VERSION_CODE >= KERNEL_VERSION(2,4,24) @@ -743,11 +728,11 @@ static void fill_port_desc(struct net_bridge_port *p, struct ofp_phy_port *desc) if (ecmd.supported & SUPPORTED_10000baseT_Full) desc->features |= OFPPF_10GB_FD; - desc->features = htonl(desc->features); desc->speed = htonl(ecmd.speed); } } #endif + desc->features = htonl(desc->features); } static int @@ -827,7 +812,7 @@ down_port_cb(struct work_struct *work) if (net_ratelimit()) printk("problem bringing up port %s\n", p->dev->name); rtnl_unlock(); - p->status |= BRPS_PORT_DOWN; + p->status |= OFPPFL_PORT_DOWN; } /* Callback function for a workqueue to enable an interface */ @@ -842,7 +827,7 @@ up_port_cb(struct work_struct *work) if (net_ratelimit()) printk("problem bringing down port %s\n", p->dev->name); rtnl_unlock(); - p->status &= ~BRPS_PORT_DOWN; + p->status &= ~OFPPFL_PORT_DOWN; } int @@ -854,16 +839,17 @@ dp_update_port_flags(struct datapath *dp, const struct ofp_port_mod *opm) struct net_bridge_port *p = (port_no < OFPP_MAX ? dp->ports[port_no] : port_no == OFPP_LOCAL ? dp->local_port : NULL); + uint32_t flag_mask; + /* Make sure the port id hasn't changed since this was sent */ if (!p || memcmp(opp->hw_addr, p->dev->dev_addr, ETH_ALEN)) return -1; spin_lock_irqsave(&p->lock, flags); - if (opm->mask & htonl(OFPPFL_NO_FLOOD)) { - if (opp->flags & htonl(OFPPFL_NO_FLOOD)) - p->flags |= BRPF_NO_FLOOD; - else - p->flags &= ~BRPF_NO_FLOOD; + flag_mask = ntohl(opm->mask) & PORT_FLAG_BITS; + if (flag_mask) { + p->flags &= ~flag_mask; + p->flags |= ntohl(opp->flags) & flag_mask; } /* Modifying the status of an interface requires taking a lock @@ -872,11 +858,11 @@ dp_update_port_flags(struct datapath *dp, const struct ofp_port_mod *opm) * context. */ if (opm->mask & htonl(OFPPFL_PORT_DOWN)) { if ((opp->flags & htonl(OFPPFL_PORT_DOWN)) - && (p->status & BRPS_PORT_DOWN) == 0) { + && (p->status & OFPPFL_PORT_DOWN) == 0) { PREPARE_WORK(&p->port_task, down_port_cb); schedule_work(&p->port_task); } else if ((opp->flags & htonl(OFPPFL_PORT_DOWN)) == 0 - && (p->status & BRPS_PORT_DOWN)) { + && (p->status & OFPPFL_PORT_DOWN)) { PREPARE_WORK(&p->port_task, up_port_cb); schedule_work(&p->port_task); } @@ -902,14 +888,14 @@ update_port_status(struct net_bridge_port *p) orig_status = p->status; if (p->dev->flags & IFF_UP) - p->status &= ~BRPS_PORT_DOWN; + p->status &= ~OFPPFL_PORT_DOWN; else - p->status |= BRPS_PORT_DOWN; + p->status |= OFPPFL_PORT_DOWN; if (netif_carrier_ok(p->dev)) - p->status &= ~BRPS_LINK_DOWN; + p->status &= ~OFPPFL_LINK_DOWN; else - p->status |= BRPS_LINK_DOWN; + p->status |= OFPPFL_LINK_DOWN; spin_unlock_irqrestore(&p->lock, flags); return (orig_status != p->status); diff --git a/datapath/datapath.h b/datapath/datapath.h index 44a3b6952..f13a6722c 100644 --- a/datapath/datapath.h +++ b/datapath/datapath.h @@ -6,6 +6,7 @@ #include #include #include +#include #include #include "openflow.h" #include "flow.h" @@ -23,6 +24,7 @@ #define OFP_SUPPORTED_CAPABILITIES ( OFPC_FLOW_STATS \ | OFPC_TABLE_STATS \ | OFPC_PORT_STATS \ + | OFPC_STP \ | OFPC_MULTI_PHY_TX ) /* Actions supported by this implementation. */ @@ -68,9 +70,24 @@ struct sender { uint32_t seq; /* Netlink sequence ID of request. */ }; +#define PORT_STATUS_BITS (OFPPFL_PORT_DOWN | OFPPFL_LINK_DOWN) +#define PORT_FLAG_BITS (~PORT_STATUS_BITS) + +struct net_bridge_port { + u16 port_no; + u32 flags; /* Some subset of PORT_FLAG_BITS. */ + u32 status; /* Some subset of PORT_STATUS_BITS. */ + spinlock_t lock; + struct work_struct port_task; + struct datapath *dp; + struct net_device *dev; + struct list_head node; /* Element in datapath.ports. */ +}; + extern struct mutex dp_mutex; -int dp_output_port(struct datapath *, struct sk_buff *, int out_port); +int dp_output_port(struct datapath *, struct sk_buff *, int out_port, + int ignore_no_fwd); int dp_output_control(struct datapath *, struct sk_buff *, uint32_t, size_t, int); int dp_set_origin(struct datapath *, uint16_t, struct sk_buff *); diff --git a/datapath/dp_dev.c b/datapath/dp_dev.c index 7817d0d6d..195accb2a 100644 --- a/datapath/dp_dev.c +++ b/datapath/dp_dev.c @@ -89,7 +89,7 @@ static void dp_dev_do_xmit(struct work_struct *work) while ((skb = skb_dequeue(&dp_dev->xmit_queue)) != NULL) { skb_reset_mac_header(skb); rcu_read_lock(); - fwd_port_input(dp->chain, skb, OFPP_LOCAL); + fwd_port_input(dp->chain, skb, dp->local_port); rcu_read_unlock(); } netif_wake_queue(dp->netdev); diff --git a/datapath/forward.c b/datapath/forward.c index 239e80153..97aceb9c8 100644 --- a/datapath/forward.c +++ b/datapath/forward.c @@ -4,6 +4,8 @@ * Stanford Junior University */ +#include +#include #include #include #include @@ -26,59 +28,70 @@ static int make_writable(struct sk_buff **); static struct sk_buff *retrieve_skb(uint32_t id); static void discard_skb(uint32_t id); -/* 'skb' was received on 'in_port', a physical switch port between 0 and - * OFPP_MAX. Process it according to 'chain'. Returns 0 if successful, in - * which case 'skb' is destroyed, or -ESRCH if there is no matching flow, in - * which case 'skb' still belongs to the caller. */ +/* 'skb' was received on port 'p', which may be a physical switch port, the + * local port, or a null pointer. Process it according to 'chain'. Returns 0 + * if successful, in which case 'skb' is destroyed, or -ESRCH if there is no + * matching flow, in which case 'skb' still belongs to the caller. */ int run_flow_through_tables(struct sw_chain *chain, struct sk_buff *skb, - int in_port) + struct net_bridge_port *p) { + /* Ethernet address used as the destination for STP frames. */ + static const uint8_t stp_eth_addr[ETH_ALEN] + = { 0x01, 0x80, 0xC2, 0x00, 0x00, 0x01 }; struct sw_flow_key key; struct sw_flow *flow; - if (flow_extract(skb, in_port, &key) + if (flow_extract(skb, p ? p->port_no : OFPP_NONE, &key) && (chain->dp->flags & OFPC_FRAG_MASK) == OFPC_FRAG_DROP) { /* Drop fragment. */ kfree_skb(skb); return 0; } + if (p && p->flags & (OFPPFL_NO_RECV | OFPPFL_NO_RECV_STP) && + p->flags & (compare_ether_addr(key.dl_dst, stp_eth_addr) + ? OFPPFL_NO_RECV : OFPPFL_NO_RECV_STP)) { + kfree_skb(skb); + return 0; + } flow = chain_lookup(chain, &key); if (likely(flow != NULL)) { flow_used(flow, skb); execute_actions(chain->dp, skb, &key, - flow->actions, flow->n_actions); + flow->actions, flow->n_actions, 0); return 0; } else { return -ESRCH; } } -/* 'skb' was received on 'in_port', a physical switch port between 0 and - * OFPP_MAX. Process it according to 'chain', sending it up to the controller - * if no flow matches. Takes ownership of 'skb'. */ -void fwd_port_input(struct sw_chain *chain, struct sk_buff *skb, int in_port) +/* 'skb' was received on port 'p', which may be a physical switch port, the + * local port, or a null pointer. Process it according to 'chain', sending it + * up to the controller if no flow matches. Takes ownership of 'skb'. */ +void fwd_port_input(struct sw_chain *chain, struct sk_buff *skb, + struct net_bridge_port *p) { - if (run_flow_through_tables(chain, skb, in_port)) + if (run_flow_through_tables(chain, skb, p)) dp_output_control(chain->dp, skb, fwd_save_skb(skb), chain->dp->miss_send_len, OFPR_NO_MATCH); } static int do_output(struct datapath *dp, struct sk_buff *skb, size_t max_len, - int out_port) + int out_port, int ignore_no_fwd) { if (!skb) return -ENOMEM; return (likely(out_port != OFPP_CONTROLLER) - ? dp_output_port(dp, skb, out_port) + ? dp_output_port(dp, skb, out_port, ignore_no_fwd) : dp_output_control(dp, skb, fwd_save_skb(skb), max_len, OFPR_ACTION)); } void execute_actions(struct datapath *dp, struct sk_buff *skb, - const struct sw_flow_key *key, - const struct ofp_action *actions, int n_actions) + const struct sw_flow_key *key, + const struct ofp_action *actions, int n_actions, + int ignore_no_fwd) { /* Every output action needs a separate clone of 'skb', but the common * case is just a single output action, so that doing a clone and @@ -97,7 +110,7 @@ void execute_actions(struct datapath *dp, struct sk_buff *skb, if (prev_port != -1) { do_output(dp, skb_clone(skb, GFP_ATOMIC), - max_len, prev_port); + max_len, prev_port, ignore_no_fwd); prev_port = -1; } @@ -119,7 +132,7 @@ void execute_actions(struct datapath *dp, struct sk_buff *skb, } } if (prev_port != -1) - do_output(dp, skb, max_len, prev_port); + do_output(dp, skb, max_len, prev_port, ignore_no_fwd); else kfree_skb(skb); } @@ -367,7 +380,7 @@ recv_packet_out(struct sw_chain *chain, const struct sender *sender, dp_set_origin(chain->dp, ntohs(opo->in_port), skb); flow_extract(skb, ntohs(opo->in_port), &key); - execute_actions(chain->dp, skb, &key, opo->actions, n_actions); + execute_actions(chain->dp, skb, &key, opo->actions, n_actions, 1); return 0; } @@ -452,7 +465,7 @@ add_flow(struct sw_chain *chain, const struct ofp_flow_mod *ofm) struct sw_flow_key key; flow_used(flow, skb); flow_extract(skb, ntohs(ofm->match.in_port), &key); - execute_actions(chain->dp, skb, &key, ofm->actions, n_actions); + execute_actions(chain->dp, skb, &key, ofm->actions, n_actions, 0); } else error = -ESRCH; diff --git a/datapath/forward.h b/datapath/forward.h index 90288d022..73152f9f1 100644 --- a/datapath/forward.h +++ b/datapath/forward.h @@ -22,8 +22,10 @@ struct sender; #define PKT_COOKIE_BITS (32 - PKT_BUFFER_BITS) -void fwd_port_input(struct sw_chain *, struct sk_buff *, int in_port); -int run_flow_through_tables(struct sw_chain *, struct sk_buff *, int in_port); +void fwd_port_input(struct sw_chain *, struct sk_buff *, + struct net_bridge_port *); +int run_flow_through_tables(struct sw_chain *, struct sk_buff *, + struct net_bridge_port *); int fwd_control_input(struct sw_chain *, const struct sender *, const void *, size_t); @@ -33,8 +35,9 @@ void fwd_discard_all(void); void fwd_exit(void); void execute_actions(struct datapath *, struct sk_buff *, - const struct sw_flow_key *, - const struct ofp_action *, int n_actions); + const struct sw_flow_key *, + const struct ofp_action *, int n_actions, + int ignore_no_fwd); struct sk_buff *execute_setter(struct sk_buff *, uint16_t, const struct sw_flow_key *, const struct ofp_action *); diff --git a/include/Makefile.am b/include/Makefile.am index 741618a36..5591c6acd 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -30,6 +30,7 @@ noinst_HEADERS = \ socket-util.h \ type-props.h \ timeval.h \ + stp.h \ util.h \ vconn.h \ vconn-ssl.h \ diff --git a/include/openflow.h b/include/openflow.h index 1ad8227e4..69d785370 100644 --- a/include/openflow.h +++ b/include/openflow.h @@ -164,12 +164,32 @@ enum ofp_capabilities { OFPC_IP_REASM = 1 << 5 /* Can reassemble IP fragments. */ }; -/* Flags to indicate behavior of the physical port */ +/* Flags to indicate behavior of the physical port. */ enum ofp_port_flags { - OFPPFL_NO_FLOOD = 1 << 0, /* Do not include this port when flooding. */ - OFPPFL_PORT_DOWN = 1 << 1, /* Port is configured down. */ - OFPPFL_LINK_DOWN = 1 << 2, /* No physical link on interface. - NOTE: Non-settable field */ + /* Read/write bits. */ + OFPPFL_PORT_DOWN = 1 << 1, /* Port is configured down. */ + OFPPFL_NO_STP = 1 << 3, /* Disable 802.1D spanning tree on port. */ + OFPPFL_NO_RECV = 1 << 4, /* Drop most packets received on port. */ + OFPPFL_NO_RECV_STP = 1 << 5, /* Drop received 802.1D STP packets. */ + OFPPFL_NO_FWD = 1 << 6, /* Drop packets forwarded to port. */ + OFPPFL_NO_PACKET_IN = 1 << 7, /* Do not send packet-in msgs for port. */ + + /* Read-only bits. */ + OFPPFL_LINK_DOWN = 1 << 2, /* No physical link present. */ + + /* Read-only when STP is enabled (when OFPPFL_NO_STP is not set). + * Read/write when STP is disabled (when OFPPFL_NO_STP is set). + * + * The OFPPFL_STP_* bits have no effect on switch operation. The + * controller must adjust OFPPFL_NO_RECV, OFPPFL_NO_FWD, and + * OFPPFL_NO_PACKET_IN appropriately to fully implement an 802.1D spanning + * tree. */ + OFPPFL_NO_FLOOD = 1 << 0, /* Do not include this port when flooding. */ + OFPPFL_STP_LISTEN = 0 << 8, /* Not learning or relaying frames. */ + OFPPFL_STP_LEARN = 1 << 8, /* Learning but not relaying frames. */ + OFPPFL_STP_FORWARD = 2 << 8, /* Learning and relaying frames. */ + OFPPFL_STP_BLOCK = 3 << 8, /* Not part of spanning tree. */ + OFPPFL_STP_MASK = 3 << 8, /* Bit mask for OFPPFL_STP_* values. */ }; /* Features of physical ports available in a datapath. */ @@ -181,6 +201,7 @@ enum ofp_port_features { OFPPF_1GB_HD = 1 << 4, /* 1 Gb half-duplex rate support. */ OFPPF_1GB_FD = 1 << 5, /* 1 Gb full-duplex rate support. */ OFPPF_10GB_FD = 1 << 6, /* 10 Gb full-duplex rate support. */ + OFPPF_STP = 1 << 7, /* 802.1D spanning tree supported on port. */ }; diff --git a/include/stp.h b/include/stp.h new file mode 100644 index 000000000..3305e60c4 --- /dev/null +++ b/include/stp.h @@ -0,0 +1,107 @@ +/* Copyright (c) 2008 The Board of Trustees of The Leland Stanford + * Junior University + * + * We are making the OpenFlow specification and associated documentation + * (Software) available for public use and benefit with the expectation + * that others will use, modify and enhance the Software and contribute + * those enhancements back to the community. However, since we would + * like to make the Software available for broadest use, with as few + * restrictions as possible permission is hereby granted, free of + * charge, to any person obtaining a copy of this Software to deal in + * the Software under the copyrights without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * The name and trademarks of copyright holder(s) may NOT be used in + * advertising or publicity pertaining to the Software or any + * derivatives without specific, written prior permission. + */ + +#ifndef STP_H +#define STP_H 1 + +/* This is an implementation of Spanning Tree Protocol as described in IEEE + * 802.1D-1998, clauses 8 and 9. Section numbers refer to this standard. */ + +#include +#include +#include "compiler.h" +#include "util.h" + +/* Ethernet address used as the destination for STP frames. */ +extern const uint8_t stp_eth_addr[6]; + +/* LLC field values used for STP frames. */ +#define STP_LLC_SSAP 0x42 +#define STP_LLC_DSAP 0x42 +#define STP_LLC_CNTL 0x03 + +/* Bridge identifier. Top 16 bits are a priority value (numerically lower + * values are higher priorities). Bottom 48 bits are MAC address of bridge. */ +typedef uint64_t stp_identifier; + +/* Basic STP functionality. */ +#define STP_MAX_PORTS 255 +struct stp *stp_create(const char *name, stp_identifier bridge_id, + void (*send_bpdu)(const void *bpdu, size_t bpdu_size, + int port_no, void *aux), + void *aux); +void stp_destroy(struct stp *); +void stp_tick(struct stp *, int elapsed); +void stp_set_bridge_priority(struct stp *, uint16_t new_priority); + +/* STP properties. */ +const char *stp_get_name(const struct stp *); +stp_identifier stp_get_bridge_id(const struct stp *); +stp_identifier stp_get_designated_root(const struct stp *); +bool stp_is_root_bridge(const struct stp *); +int stp_get_root_path_cost(const struct stp *); + +/* Obtaining STP ports. */ +struct stp_port *stp_get_port(struct stp *, int port_no); +struct stp_port *stp_get_root_port(struct stp *); +bool stp_get_changed_port(struct stp *, struct stp_port **portp); + +/* State of an STP port. + * + * A port is in exactly one state at any given time, but distinct bits are used + * for states to allow testing for more than one state with a bit mask. */ +enum stp_state { + STP_DISABLED = 1 << 0, /* 8.4.5: Disabled by management. */ + STP_LISTENING = 1 << 1, /* 8.4.2: Not learning or relaying frames. */ + STP_LEARNING = 1 << 2, /* 8.4.3: Learning but not relaying frames. */ + STP_FORWARDING = 1 << 3, /* 8.4.4: Learning and relaying frames. */ + STP_BLOCKING = 1 << 4 /* 8.4.1: Initial boot state. */ +}; +const char *stp_state_name(enum stp_state); +bool stp_forward_in_state(enum stp_state); +bool stp_learn_in_state(enum stp_state); + +void stp_received_bpdu(struct stp_port *, const void *bpdu, size_t bpdu_size); + +struct stp *stp_port_get_stp(struct stp_port *); +int stp_port_no(const struct stp_port *); +enum stp_state stp_port_get_state(const struct stp_port *); +void stp_port_enable(struct stp_port *); +void stp_port_disable(struct stp_port *); +void stp_port_set_priority(struct stp_port *, uint8_t new_priority); +void stp_port_set_path_cost(struct stp_port *, unsigned int path_cost); +void stp_port_set_speed(struct stp_port *, unsigned int speed); +void stp_port_enable_change_detection(struct stp_port *); +void stp_port_disable_change_detection(struct stp_port *); + +#endif /* stp.h */ diff --git a/include/vlog-modules.def b/include/vlog-modules.def index 22553de97..9edb8a827 100644 --- a/include/vlog-modules.def +++ b/include/vlog-modules.def @@ -18,6 +18,7 @@ VLOG_MODULE(ofp_discover) VLOG_MODULE(poll_loop) VLOG_MODULE(secchan) VLOG_MODULE(rconn) +VLOG_MODULE(stp) VLOG_MODULE(switch) VLOG_MODULE(terminal) VLOG_MODULE(socket_util) diff --git a/lib/Makefile.am b/lib/Makefile.am index 6c02909f9..229e11bed 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -25,6 +25,7 @@ libopenflow_a_SOURCES = \ rconn.c \ socket-util.c \ timeval.c \ + stp.c \ util.c \ vconn-tcp.c \ vconn-unix.c \ diff --git a/lib/learning-switch.c b/lib/learning-switch.c index d231e3863..d09902614 100644 --- a/lib/learning-switch.c +++ b/lib/learning-switch.c @@ -61,6 +61,7 @@ struct lswitch { int max_idle; uint64_t datapath_id; + uint32_t capabilities; time_t last_features_request; struct mac_learning *ml; /* NULL to act as hub instead of switch. */ @@ -74,10 +75,16 @@ static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(30, 300); static void queue_tx(struct lswitch *, struct rconn *, struct buffer *); static void send_features_request(struct lswitch *, struct rconn *); +static void process_switch_features(struct lswitch *, struct rconn *, + struct ofp_switch_features *); static void process_packet_in(struct lswitch *, struct rconn *, struct ofp_packet_in *); static void process_echo_request(struct lswitch *, struct rconn *, struct ofp_header *); +static void process_port_status(struct lswitch *, struct rconn *, + struct ofp_port_status *); +static void process_phy_port(struct lswitch *, struct rconn *, + const struct ofp_phy_port *); /* Creates and returns a new learning switch. * @@ -123,6 +130,7 @@ lswitch_process_packet(struct lswitch *sw, struct rconn *rconn, [0 ... UINT8_MAX] = sizeof (struct ofp_header), [OFPT_FEATURES_REPLY] = sizeof (struct ofp_switch_features), [OFPT_PACKET_IN] = offsetof (struct ofp_packet_in, data), + [OFPT_PORT_STATUS] = sizeof(struct ofp_port_status), }; struct ofp_header *oh; @@ -138,12 +146,13 @@ lswitch_process_packet(struct lswitch *sw, struct rconn *rconn, if (oh->type == OFPT_ECHO_REQUEST) { process_echo_request(sw, rconn, msg->data); } else if (oh->type == OFPT_FEATURES_REPLY) { - struct ofp_switch_features *osf = msg->data; - sw->datapath_id = osf->datapath_id; + process_switch_features(sw, rconn, msg->data); } else if (sw->datapath_id == 0) { send_features_request(sw, rconn); } else if (oh->type == OFPT_PACKET_IN) { process_packet_in(sw, rconn, msg->data); + } else if (oh->type == OFPT_PORT_STATUS) { + process_port_status(sw, rconn, msg->data); } else { if (VLOG_IS_DBG_ENABLED()) { char *p = ofp_to_string(msg->data, msg->size, 2); @@ -189,6 +198,22 @@ queue_tx(struct lswitch *sw, struct rconn *rconn, struct buffer *b) } } +static void +process_switch_features(struct lswitch *sw, struct rconn *rconn, + struct ofp_switch_features *osf) +{ + size_t n_ports = ((ntohs(osf->header.length) + - offsetof(struct ofp_switch_features, ports)) + / sizeof *osf->ports); + size_t i; + + sw->datapath_id = osf->datapath_id; + sw->capabilities = ntohl(osf->capabilities); + for (i = 0; i < n_ports; i++) { + process_phy_port(sw, rconn, &osf->ports[i]); + } +} + static void process_packet_in(struct lswitch *sw, struct rconn *rconn, struct ofp_packet_in *opi) @@ -251,3 +276,62 @@ process_echo_request(struct lswitch *sw, struct rconn *rconn, { queue_tx(sw, rconn, make_echo_reply(rq)); } + +static void +process_port_status(struct lswitch *sw, struct rconn *rconn, + struct ofp_port_status *ops) +{ + process_phy_port(sw, rconn, &ops->desc); +} + +static void +process_phy_port(struct lswitch *sw, struct rconn *rconn, + const struct ofp_phy_port *opp) +{ + if (sw->capabilities & OFPC_STP && opp->features & ntohl(OFPPF_STP)) { + uint32_t flags = ntohl(opp->flags); + uint32_t new_flags = flags & ~(OFPPFL_NO_RECV | OFPPFL_NO_RECV_STP + | OFPPFL_NO_FWD | OFPPFL_NO_PACKET_IN); + if (!(flags & (OFPPFL_NO_STP | OFPPFL_PORT_DOWN | OFPPFL_LINK_DOWN))) { + bool forward = false; + bool learn = false; + switch (flags & OFPPFL_STP_MASK) { + case OFPPFL_STP_LISTEN: + case OFPPFL_STP_BLOCK: + break; + case OFPPFL_STP_LEARN: + learn = true; + break; + case OFPPFL_STP_FORWARD: + forward = learn = true; + break; + } + if (!forward) { + new_flags |= OFPPFL_NO_RECV | OFPPFL_NO_FWD; + } + if (!learn) { + new_flags |= OFPPFL_NO_PACKET_IN; + } + } + if (flags != new_flags) { + struct ofp_port_mod *opm; + struct buffer *b; + int retval; + + VLOG_WARN("port %d: flags=%x new_flags=%x", + ntohs(opp->port_no), flags, new_flags); + opm = make_openflow(sizeof *opm, OFPT_PORT_MOD, &b); + opm->mask = htonl(flags ^ new_flags); + opm->desc = *opp; + opm->desc.flags = htonl(new_flags); + retval = rconn_send(rconn, b, NULL); + if (retval) { + if (retval != ENOTCONN) { + VLOG_WARN_RL(&rl, "%s: send: %s", + rconn_get_name(rconn), strerror(retval)); + } + buffer_delete(b); + } + } + } +} diff --git a/lib/stp.c b/lib/stp.c new file mode 100644 index 000000000..6f7f09a54 --- /dev/null +++ b/lib/stp.c @@ -0,0 +1,1064 @@ +/* Copyright (c) 2008 The Board of Trustees of The Leland Stanford + * Junior University + * + * We are making the OpenFlow specification and associated documentation + * (Software) available for public use and benefit with the expectation + * that others will use, modify and enhance the Software and contribute + * those enhancements back to the community. However, since we would + * like to make the Software available for broadest use, with as few + * restrictions as possible permission is hereby granted, free of + * charge, to any person obtaining a copy of this Software to deal in + * the Software under the copyrights without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * The name and trademarks of copyright holder(s) may NOT be used in + * advertising or publicity pertaining to the Software or any + * derivatives without specific, written prior permission. + */ + +/* Based on sample implementation in 802.1D-1998. Above copyright and license + * applies to all modifications. */ + +#include "stp.h" +#include +#include +#include +#include +#include "packets.h" +#include "util.h" +#include "xtoxll.h" + +#include "vlog.h" +#define THIS_MODULE VLM_stp + +/* Ethernet address used as the destination for STP frames. */ +const uint8_t stp_eth_addr[ETH_ADDR_LEN] += { 0x01, 0x80, 0xC2, 0x00, 0x00, 0x01 }; + +#define STP_PROTOCOL_ID 0x0000 +#define STP_PROTOCOL_VERSION 0x00 +#define STP_TYPE_CONFIG 0x00 +#define STP_TYPE_TCN 0x80 + +struct stp_bpdu_header { + uint16_t protocol_id; /* STP_PROTOCOL_ID. */ + uint8_t protocol_version; /* STP_PROTOCOL_VERSION. */ + uint8_t bpdu_type; /* One of STP_TYPE_*. */ +} __attribute__((packed)); +BUILD_ASSERT_DECL(sizeof(struct stp_bpdu_header) == 4); + +enum stp_config_bpdu_flags { + STP_CONFIG_TOPOLOGY_CHANGE_ACK = 0x80, + STP_CONFIG_TOPOLOGY_CHANGE = 0x01 +}; + +struct stp_config_bpdu { + struct stp_bpdu_header header; /* Type STP_TYPE_CONFIG. */ + uint8_t flags; /* STP_CONFIG_* flags. */ + uint64_t root_id; /* 8.5.1.1: Bridge believed to be root. */ + uint32_t root_path_cost; /* 8.5.1.2: Cost of path to root. */ + uint64_t bridge_id; /* 8.5.1.3: ID of transmitting bridge. */ + uint16_t port_id; /* 8.5.1.4: Port transmitting the BPDU. */ + uint16_t message_age; /* 8.5.1.5: Age of BPDU at tx time. */ + uint16_t max_age; /* 8.5.1.6: Timeout for received data. */ + uint16_t hello_time; /* 8.5.1.7: Time between BPDU generation. */ + uint16_t forward_delay; /* 8.5.1.8: State progression delay. */ +} __attribute__((packed)); +BUILD_ASSERT_DECL(sizeof(struct stp_config_bpdu) == 35); + +struct stp_tcn_bpdu { + struct stp_bpdu_header header; /* Type STP_TYPE_TCN. */ +} __attribute__((packed)); +BUILD_ASSERT_DECL(sizeof(struct stp_tcn_bpdu) == 4); + +struct stp_timer { + bool active; /* Timer in use? */ + int value; /* Current value of timer, counting up. */ +}; + +struct stp_port { + struct stp *stp; + int port_id; /* 8.5.5.1: Unique port identifier. */ + enum stp_state state; /* 8.5.5.2: Current state. */ + int path_cost; /* 8.5.5.3: Cost of tx/rx on this port. */ + stp_identifier designated_root; /* 8.5.5.4. */ + int designated_cost; /* 8.5.5.5: Path cost to root on port. */ + stp_identifier designated_bridge; /* 8.5.5.6. */ + int designated_port; /* 8.5.5.7: Port to send config msgs on. */ + bool topology_change_ack; /* 8.5.5.8: Flag for next config BPDU. */ + bool config_pending; /* 8.5.5.9: Send BPDU when hold expires? */ + bool change_detection_enabled; /* 8.5.5.10: Detect topology changes? */ + + struct stp_timer message_age_timer; /* 8.5.6.1: Age of received info. */ + struct stp_timer forward_delay_timer; /* 8.5.6.2: State change timer. */ + struct stp_timer hold_timer; /* 8.5.6.3: BPDU rate limit timer. */ + + bool state_changed; +}; + +struct stp { + /* Static bridge data. */ + char *name; /* Human-readable name for log messages. */ + stp_identifier bridge_id; /* 8.5.3.7: This bridge. */ + int max_age; /* 8.5.3.4: Time to drop received data. */ + int hello_time; /* 8.5.3.5: Time between sending BPDUs. */ + int forward_delay; /* 8.5.3.6: Delay between state changes. */ + int bridge_max_age; /* 8.5.3.8: max_age when we're root. */ + int bridge_hello_time; /* 8.5.3.9: hello_time as root. */ + int bridge_forward_delay; /* 8.5.3.10: forward_delay as root. */ + + /* Dynamic bridge data. */ + stp_identifier designated_root; /* 8.5.3.1: Bridge believed to be root. */ + unsigned int root_path_cost; /* 8.5.3.2: Cost of path to root. */ + struct stp_port *root_port; /* 8.5.3.3: Lowest cost port to root. */ + bool topology_change_detected; /* 8.5.3.11: Detected a topology change? */ + bool topology_change; /* 8.5.3.12: Received topology change? */ + + /* Bridge timers. */ + struct stp_timer hello_timer; /* 8.5.4.1: Hello timer. */ + struct stp_timer tcn_timer; /* 8.5.4.2: Topology change timer. */ + struct stp_timer topology_change_timer; /* 8.5.4.3. */ + + /* Ports. */ + struct stp_port ports[STP_MAX_PORTS]; + + /* Interface to client. */ + struct stp_port *first_changed_port; + void (*send_bpdu)(const void *bpdu, size_t bpdu_size, + int port_no, void *aux); + void *aux; +}; + +#define FOR_EACH_ENABLED_PORT(PORT, STP) \ + for ((PORT) = stp_next_enabled_port((STP), (STP)->ports); \ + (PORT); \ + (PORT) = stp_next_enabled_port((STP), (PORT) + 1)) +static struct stp_port * +stp_next_enabled_port(const struct stp *stp, const struct stp_port *port) +{ + for (; port < &stp->ports[ARRAY_SIZE(stp->ports)]; port++) { + if (port->state != STP_DISABLED) { + return (struct stp_port *) port; + } + } + return NULL; +} + +#define SECONDS_TO_TIMER(SECS) ((SECS) * 0x100) + +#define MESSAGE_AGE_INCREMENT 1 + +static void stp_transmit_config(struct stp_port *); +static bool stp_supersedes_port_info(const struct stp_port *, + const struct stp_config_bpdu *); +static void stp_record_config_information(struct stp_port *, + const struct stp_config_bpdu *); +static void stp_record_config_timeout_values(struct stp *, + const struct stp_config_bpdu *); +static bool stp_is_designated_port(const struct stp_port *); +static void stp_config_bpdu_generation(struct stp *); +static void stp_transmit_tcn(struct stp *); +static void stp_configuration_update(struct stp *); +static bool stp_supersedes_root(const struct stp_port *root, + const struct stp_port *); +static void stp_root_selection(struct stp *); +static void stp_designated_port_selection(struct stp *); +static void stp_become_designated_port(struct stp_port *); +static void stp_port_state_selection(struct stp *); +static void stp_make_forwarding(struct stp_port *); +static void stp_make_blocking(struct stp_port *); +static void stp_set_port_state(struct stp_port *, enum stp_state); +static void stp_topology_change_detection(struct stp *); +static void stp_topology_change_acknowledged(struct stp *); +static void stp_acknowledge_topology_change(struct stp_port *); +static void stp_received_config_bpdu(struct stp *, struct stp_port *, + const struct stp_config_bpdu *); +static void stp_received_tcn_bpdu(struct stp *, struct stp_port *, + const struct stp_tcn_bpdu *); +static void stp_hello_timer_expiry(struct stp *); +static void stp_message_age_timer_expiry(struct stp_port *); +static bool stp_is_designated_for_some_port(const struct stp *); +static void stp_forward_delay_timer_expiry(struct stp_port *); +static void stp_tcn_timer_expiry(struct stp *); +static void stp_topology_change_timer_expiry(struct stp *); +static void stp_hold_timer_expiry(struct stp_port *); +static void stp_initialize_port(struct stp_port *, enum stp_state); +static void stp_become_root_bridge(struct stp *stp); + +static void stp_start_timer(struct stp_timer *, int value); +static void stp_stop_timer(struct stp_timer *); +static bool stp_timer_expired(struct stp_timer *, int elapsed, int timeout); + +/* Creates and returns a new STP instance that initially has no port enabled. + * + * 'bridge_id' should be a 48-bit MAC address as returned by + * eth_addr_to_uint64(). 'bridge_id' may also have a priority value in its top + * 16 bits; if those bits are set to 0, the default bridge priority of 32768 is + * used. (This priority may be changed with stp_set_bridge_priority().) + * + * When the bridge needs to send out a BPDU, it calls 'send_bpdu', passing + * 'aux' as auxiliary data. This callback may be called from stp_tick() or + * stp_received_bpdu(). + */ +struct stp * +stp_create(const char *name, stp_identifier bridge_id, + void (*send_bpdu)(const void *bpdu, size_t bpdu_size, + int port_no, void *aux), + void *aux) +{ + struct stp *stp; + struct stp_port *p; + + stp = xcalloc(1, sizeof *stp); + stp->name = xstrdup(name); + stp->bridge_id = bridge_id; + if (!(stp->bridge_id >> 48)) { + stp->bridge_id |= UINT64_C(32768) << 48; + } + stp->max_age = SECONDS_TO_TIMER(20); + stp->hello_time = SECONDS_TO_TIMER(2); + stp->forward_delay = SECONDS_TO_TIMER(15); + stp->bridge_max_age = stp->max_age; + stp->bridge_hello_time = stp->hello_time; + stp->bridge_forward_delay = stp->forward_delay; + + stp->designated_root = stp->bridge_id; + stp->root_path_cost = 0; + stp->root_port = NULL; + stp->topology_change_detected = false; + stp->topology_change = false; + + stp_stop_timer(&stp->tcn_timer); + stp_stop_timer(&stp->topology_change_timer); + stp_start_timer(&stp->hello_timer, 0); + + stp->send_bpdu = send_bpdu; + stp->aux = aux; + + stp->first_changed_port = &stp->ports[ARRAY_SIZE(stp->ports)]; + for (p = stp->ports; p < &stp->ports[ARRAY_SIZE(stp->ports)]; p++) { + p->stp = stp; + p->port_id = (stp_port_no(p) + 1) | (128 << 8); + p->path_cost = 19; /* Recommended default for 100 Mb/s link. */ + stp_initialize_port(p, STP_DISABLED); + } + return stp; +} + +/* Destroys 'stp'. */ +void +stp_destroy(struct stp *stp) +{ + free(stp); +} + +void +stp_tick(struct stp *stp, int elapsed) +{ + struct stp_port *p; + + if (stp_timer_expired(&stp->hello_timer, elapsed, stp->hello_time)) { + stp_hello_timer_expiry(stp); + } + if (stp_timer_expired(&stp->tcn_timer, elapsed, stp->bridge_hello_time)) { + stp_tcn_timer_expiry(stp); + } + if (stp_timer_expired(&stp->topology_change_timer, elapsed, + stp->max_age + stp->forward_delay)) { + stp_topology_change_timer_expiry(stp); + } + FOR_EACH_ENABLED_PORT (p, stp) { + if (stp_timer_expired(&p->message_age_timer, elapsed, stp->max_age)) { + stp_message_age_timer_expiry(p); + } + } + FOR_EACH_ENABLED_PORT (p, stp) { + if (stp_timer_expired(&p->forward_delay_timer, elapsed, + stp->forward_delay)) { + stp_forward_delay_timer_expiry(p); + } + if (stp_timer_expired(&p->hold_timer, elapsed, SECONDS_TO_TIMER(1))) { + stp_hold_timer_expiry(p); + } + } +} + +void +stp_set_bridge_priority(struct stp *stp, uint16_t new_priority) +{ + stp_identifier new_bridge_id; + bool root; + struct stp_port *p; + + new_bridge_id = ((stp->bridge_id & UINT64_C(0xffffffffffff)) + | ((uint64_t) new_priority << 48)); + root = stp_is_root_bridge(stp); + FOR_EACH_ENABLED_PORT (p, stp) { + if (stp_is_designated_port(p)) { + p->designated_bridge = new_bridge_id; + } + } + stp->bridge_id = new_bridge_id; + stp_configuration_update(stp); + stp_port_state_selection(stp); + if (stp_is_root_bridge(stp) && !root) { + stp_become_root_bridge(stp); + } +} + +/* Returns the name given to 'stp' in the call to stp_create(). */ +const char * +stp_get_name(const struct stp *stp) +{ + return stp->name; +} + +/* Returns the bridge ID for 'stp'. */ +stp_identifier +stp_get_bridge_id(const struct stp *stp) +{ + return stp->bridge_id; +} + +/* Returns the bridge ID of the bridge currently believed to be the root. */ +stp_identifier +stp_get_designated_root(const struct stp *stp) +{ + return stp->designated_root; +} + +/* Returns true if 'stp' believes itself to the be root of the spanning tree, + * false otherwise. */ +bool +stp_is_root_bridge(const struct stp *stp) +{ + return stp->bridge_id == stp->designated_root; +} + +/* Returns the cost of the path from 'stp' to the root of the spanning tree. */ +int +stp_get_root_path_cost(const struct stp *stp) +{ + return stp->root_path_cost; +} + +/* Returns the port in 'stp' with index 'port_no', which must be between 0 and + * STP_MAX_PORTS. */ +struct stp_port * +stp_get_port(struct stp *stp, int port_no) +{ + assert(port_no >= 0 && port_no < ARRAY_SIZE(stp->ports)); + return &stp->ports[port_no]; +} + +/* Returns the port connecting 'stp' to the root bridge, or a null pointer if + * there is no such port. */ +struct stp_port * +stp_get_root_port(struct stp *stp) +{ + return stp->root_port; +} + +/* Finds a port whose state has changed. If successful, stores the port whose + * state changed in '*portp' and returns true. If no port has changed, stores + * NULL in '*portp' and returns false. */ +bool +stp_get_changed_port(struct stp *stp, struct stp_port **portp) +{ + struct stp_port *end = &stp->ports[ARRAY_SIZE(stp->ports)]; + struct stp_port *p; + + for (p = stp->first_changed_port; p < end; p++) { + if (p->state_changed) { + p->state_changed = false; + stp->first_changed_port = p + 1; + *portp = p; + return true; + } + } + stp->first_changed_port = end; + *portp = NULL; + return false; +} + +/* Returns the name for the given 'state' (for use in debugging and log + * messages). */ +const char * +stp_state_name(enum stp_state state) +{ + switch (state) { + case STP_DISABLED: + return "disabled"; + case STP_LISTENING: + return "listening"; + case STP_LEARNING: + return "learning"; + case STP_FORWARDING: + return "forwarding"; + case STP_BLOCKING: + return "blocking"; + default: + NOT_REACHED(); + } +} + +/* Returns true if 'state' is one in which packets received on a port should + * be forwarded, false otherwise. */ +bool +stp_forward_in_state(enum stp_state state) +{ + return state == STP_FORWARDING; +} + +/* Returns true if 'state' is one in which MAC learning should be done on + * packets received on a port, false otherwise. */ +bool +stp_learn_in_state(enum stp_state state) +{ + return state & (STP_LEARNING | STP_FORWARDING); +} + +/* Notifies the STP entity that bridge protocol data unit 'bpdu', which is + * 'bpdu_size' bytes in length, was received on port 'p'. + * + * This function may call the 'send_bpdu' function provided to stp_create(). */ +void +stp_received_bpdu(struct stp_port *p, const void *bpdu, size_t bpdu_size) +{ + struct stp *stp = p->stp; + const struct stp_bpdu_header *header; + + if (p->state == STP_DISABLED) { + return; + } + + if (bpdu_size < sizeof(struct stp_bpdu_header)) { + VLOG_WARN("%s: received runt %zu-byte BPDU", stp->name, bpdu_size); + return; + } + + header = bpdu; + if (header->protocol_id != htons(STP_PROTOCOL_ID)) { + VLOG_WARN("%s: received BPDU with unexpected protocol ID %"PRIu16, + stp->name, ntohs(header->protocol_id)); + return; + } + if (header->protocol_version != STP_PROTOCOL_VERSION) { + VLOG_DBG("%s: received BPDU with unexpected protocol version %"PRIu8, + stp->name, header->protocol_version); + } + + switch (header->bpdu_type) { + case STP_TYPE_CONFIG: + if (bpdu_size < sizeof(struct stp_config_bpdu)) { + VLOG_WARN("%s: received config BPDU with invalid size %zu", + stp->name, bpdu_size); + return; + } + stp_received_config_bpdu(stp, p, bpdu); + break; + + case STP_TYPE_TCN: + if (bpdu_size != sizeof(struct stp_tcn_bpdu)) { + VLOG_WARN("%s: received TCN BPDU with invalid size %zu", + stp->name, bpdu_size); + return; + } + stp_received_tcn_bpdu(stp, p, bpdu); + break; + + default: + VLOG_WARN("%s: received BPDU of unexpected type %"PRIu8, + stp->name, header->bpdu_type); + return; + } +} + +/* Returns the STP entity in which 'p' is nested. */ +struct stp * +stp_port_get_stp(struct stp_port *p) +{ + return p->stp; +} + +/* Returns the index of port 'p' within its bridge. */ +int +stp_port_no(const struct stp_port *p) +{ + struct stp *stp = p->stp; + assert(p >= stp->ports && p < &stp->ports[ARRAY_SIZE(stp->ports)]); + return p - stp->ports; +} + +/* Returns the state of port 'p'. */ +enum stp_state +stp_port_get_state(const struct stp_port *p) +{ + return p->state; +} + +/* Disables STP on port 'p'. */ +void +stp_port_disable(struct stp_port *p) +{ + struct stp *stp = p->stp; + if (p->state != STP_DISABLED) { + bool root = stp_is_root_bridge(stp); + stp_become_designated_port(p); + stp_set_port_state(p, STP_DISABLED); + p->topology_change_ack = false; + p->config_pending = false; + stp_stop_timer(&p->message_age_timer); + stp_stop_timer(&p->forward_delay_timer); + stp_configuration_update(stp); + stp_port_state_selection(stp); + if (stp_is_root_bridge(stp) && !root) { + stp_become_root_bridge(stp); + } + } +} + +/* Enables STP on port 'p'. The port will initially be in "blocking" state. */ +void +stp_port_enable(struct stp_port *p) +{ + if (p->state == STP_DISABLED) { + stp_initialize_port(p, STP_BLOCKING); + stp_port_state_selection(p->stp); + } +} + +/* Sets the priority of port 'p' to 'new_priority'. Lower numerical values + * are interpreted as higher priorities. */ +void +stp_port_set_priority(struct stp_port *p, uint8_t new_priority) +{ + uint16_t new_port_id = (p->port_id & 0xff) | (new_priority << 8); + if (p->port_id != new_port_id) { + struct stp *stp = p->stp; + if (stp_is_designated_port(p)) { + p->designated_port = new_port_id; + } + p->port_id = new_port_id; + if (stp->bridge_id == p->designated_bridge + && p->port_id < p->designated_port) { + stp_become_designated_port(p); + stp_port_state_selection(stp); + } + } +} + +/* Sets the path cost of port 'p' to 'path_cost'. Lower values are generally + * used to indicate faster links. Use stp_port_set_speed() to automatically + * generate a default path cost from a link speed. */ +void +stp_port_set_path_cost(struct stp_port *p, unsigned int path_cost) +{ + if (p->path_cost != path_cost) { + struct stp *stp = p->stp; + p->path_cost = path_cost; + stp_configuration_update(stp); + stp_port_state_selection(stp); + } +} + +/* Sets the path cost of port 'p' based on 'speed' (measured in Mb/s). */ +void +stp_port_set_speed(struct stp_port *p, unsigned int speed) +{ + stp_port_set_path_cost(p, (speed >= 10000 ? 2 /* 10 Gb/s. */ + : speed >= 1000 ? 4 /* 1 Gb/s. */ + : speed >= 100 ? 19 /* 100 Mb/s. */ + : speed >= 16 ? 62 /* 16 Mb/s. */ + : speed >= 10 ? 100 /* 10 Mb/s. */ + : speed >= 4 ? 250 /* 4 Mb/s. */ + : 19)); /* 100 Mb/s (guess). */ +} + +/* Enables topology change detection on port 'p'. */ +void +stp_port_enable_change_detection(struct stp_port *p) +{ + p->change_detection_enabled = true; +} + +/* Disables topology change detection on port 'p'. */ +void +stp_port_disable_change_detection(struct stp_port *p) +{ + p->change_detection_enabled = false; +} + +static void +stp_transmit_config(struct stp_port *p) +{ + struct stp *stp = p->stp; + bool root = stp_is_root_bridge(stp); + if (!root && !stp->root_port) { + return; + } + if (p->hold_timer.active) { + p->config_pending = true; + } else { + struct stp_config_bpdu config; + memset(&config, 0, sizeof config); + config.header.protocol_id = htons(STP_PROTOCOL_ID); + config.header.protocol_version = STP_PROTOCOL_VERSION; + config.header.bpdu_type = STP_TYPE_CONFIG; + config.flags = 0; + if (p->topology_change_ack) { + config.flags |= htons(STP_CONFIG_TOPOLOGY_CHANGE_ACK); + } + if (stp->topology_change) { + config.flags |= htons(STP_CONFIG_TOPOLOGY_CHANGE); + } + config.root_id = htonll(stp->designated_root); + config.root_path_cost = htonl(stp->root_path_cost); + config.bridge_id = htonll(stp->bridge_id); + config.port_id = htons(p->port_id); + if (root) { + config.message_age = htons(0); + } else { + config.message_age = htons(stp->root_port->message_age_timer.value + + MESSAGE_AGE_INCREMENT); + } + config.max_age = htons(stp->max_age); + config.hello_time = htons(stp->hello_time); + config.forward_delay = htons(stp->forward_delay); + if (ntohs(config.message_age) < stp->max_age) { + p->topology_change_ack = false; + p->config_pending = false; + stp->send_bpdu(&config, sizeof config, stp_port_no(p), stp->aux); + stp_start_timer(&p->hold_timer, 0); + } + } +} + +static bool +stp_supersedes_port_info(const struct stp_port *p, + const struct stp_config_bpdu *config) +{ + if (ntohll(config->root_id) != p->designated_root) { + return ntohll(config->root_id) < p->designated_root; + } else if (ntohl(config->root_path_cost) != p->designated_cost) { + return ntohl(config->root_path_cost) < p->designated_cost; + } else if (ntohll(config->bridge_id) != p->designated_bridge) { + return ntohll(config->bridge_id) < p->designated_bridge; + } else { + return (ntohll(config->bridge_id) != p->stp->bridge_id + || ntohs(config->port_id) <= p->designated_port); + } +} + +static void +stp_record_config_information(struct stp_port *p, + const struct stp_config_bpdu *config) +{ + p->designated_root = ntohll(config->root_id); + p->designated_cost = ntohl(config->root_path_cost); + p->designated_bridge = ntohll(config->bridge_id); + p->designated_port = ntohs(config->port_id); + stp_start_timer(&p->message_age_timer, ntohs(config->message_age)); +} + +static void +stp_record_config_timeout_values(struct stp *stp, + const struct stp_config_bpdu *config) +{ + stp->max_age = ntohs(config->max_age); + stp->hello_time = ntohs(config->hello_time); + stp->forward_delay = ntohs(config->forward_delay); + stp->topology_change = config->flags & htons(STP_CONFIG_TOPOLOGY_CHANGE); +} + +static bool +stp_is_designated_port(const struct stp_port *p) +{ + return (p->designated_bridge == p->stp->bridge_id + && p->designated_port == p->port_id); +} + +static void +stp_config_bpdu_generation(struct stp *stp) +{ + struct stp_port *p; + + FOR_EACH_ENABLED_PORT (p, stp) { + if (stp_is_designated_port(p)) { + stp_transmit_config(p); + } + } +} + +static void +stp_transmit_tcn(struct stp *stp) +{ + struct stp_port *p = stp->root_port; + struct stp_tcn_bpdu tcn_bpdu; + if (!p) { + return; + } + tcn_bpdu.header.protocol_id = htons(STP_PROTOCOL_ID); + tcn_bpdu.header.protocol_version = STP_PROTOCOL_VERSION; + tcn_bpdu.header.bpdu_type = STP_TYPE_TCN; + stp->send_bpdu(&tcn_bpdu, sizeof tcn_bpdu, stp_port_no(p), stp->aux); +} + +static void +stp_configuration_update(struct stp *stp) +{ + stp_root_selection(stp); + stp_designated_port_selection(stp); +} + +static bool +stp_supersedes_root(const struct stp_port *root, const struct stp_port *p) +{ + int p_cost = p->designated_cost + p->path_cost; + int root_cost = root->designated_cost + root->path_cost; + + if (p->designated_root != root->designated_root) { + return p->designated_root < root->designated_root; + } else if (p_cost != root_cost) { + return p_cost < root_cost; + } else if (p->designated_bridge != root->designated_bridge) { + return p->designated_bridge < root->designated_bridge; + } else if (p->designated_port != root->designated_port) { + return p->designated_port < root->designated_port; + } else { + return p->port_id < root->port_id; + } +} + +static void +stp_root_selection(struct stp *stp) +{ + struct stp_port *p, *root; + + root = NULL; + FOR_EACH_ENABLED_PORT (p, stp) { + if (stp_is_designated_port(p) + || p->designated_root >= stp->bridge_id) { + continue; + } + if (root && !stp_supersedes_root(root, p)) { + continue; + } + root = p; + } + stp->root_port = root; + if (!root) { + stp->designated_root = stp->bridge_id; + stp->root_path_cost = 0; + } else { + stp->designated_root = root->designated_root; + stp->root_path_cost = root->designated_cost + root->path_cost; + } +} + +static void +stp_designated_port_selection(struct stp *stp) +{ + struct stp_port *p; + + FOR_EACH_ENABLED_PORT (p, stp) { + if (stp_is_designated_port(p) + || p->designated_root != stp->designated_root + || stp->root_path_cost < p->designated_cost + || (stp->root_path_cost == p->designated_cost + && (stp->bridge_id < p->designated_bridge + || (stp->bridge_id == p->designated_bridge + && p->port_id <= p->designated_port)))) + { + stp_become_designated_port(p); + } + } +} + +static void +stp_become_designated_port(struct stp_port *p) +{ + struct stp *stp = p->stp; + p->designated_root = stp->designated_root; + p->designated_cost = stp->root_path_cost; + p->designated_bridge = stp->bridge_id; + p->designated_port = p->port_id; +} + +static void +stp_port_state_selection(struct stp *stp) +{ + struct stp_port *p; + + FOR_EACH_ENABLED_PORT (p, stp) { + if (p == stp->root_port) { + p->config_pending = false; + p->topology_change_ack = false; + stp_make_forwarding(p); + } else if (stp_is_designated_port(p)) { + stp_stop_timer(&p->message_age_timer); + stp_make_forwarding(p); + } else { + p->config_pending = false; + p->topology_change_ack = false; + stp_make_blocking(p); + } + } +} + +static void +stp_make_forwarding(struct stp_port *p) +{ + if (p->state == STP_BLOCKING) { + stp_set_port_state(p, STP_LISTENING); + stp_start_timer(&p->forward_delay_timer, 0); + } +} + +static void +stp_make_blocking(struct stp_port *p) +{ + if (!(p->state & (STP_DISABLED | STP_BLOCKING))) { + if (p->state & (STP_FORWARDING | STP_LEARNING)) { + if (p->change_detection_enabled) { + stp_topology_change_detection(p->stp); + } + } + stp_set_port_state(p, STP_BLOCKING); + stp_stop_timer(&p->forward_delay_timer); + } +} + +static void +stp_set_port_state(struct stp_port *p, enum stp_state state) +{ + if (state != p->state && !p->state_changed) { + p->state_changed = true; + if (p < p->stp->first_changed_port) { + p->stp->first_changed_port = p; + } + } + p->state = state; +} + +static void +stp_topology_change_detection(struct stp *stp) +{ + if (stp_is_root_bridge(stp)) { + stp->topology_change = true; + stp_start_timer(&stp->topology_change_timer, 0); + } else if (!stp->topology_change_detected) { + stp_transmit_tcn(stp); + stp_start_timer(&stp->tcn_timer, 0); + } + stp->topology_change_detected = true; +} + +static void +stp_topology_change_acknowledged(struct stp *stp) +{ + stp->topology_change_detected = false; + stp_stop_timer(&stp->tcn_timer); +} + +static void +stp_acknowledge_topology_change(struct stp_port *p) +{ + p->topology_change_ack = true; + stp_transmit_config(p); +} + +void +stp_received_config_bpdu(struct stp *stp, struct stp_port *p, + const struct stp_config_bpdu *config) +{ + if (ntohs(config->message_age) >= ntohs(config->max_age)) { + VLOG_WARN("%s: received config BPDU with message age (%u) greater " + "than max age (%u)", + stp->name, + ntohs(config->message_age), ntohs(config->max_age)); + return; + } + if (p->state != STP_DISABLED) { + bool root = stp_is_root_bridge(stp); + if (stp_supersedes_port_info(p, config)) { + stp_record_config_information(p, config); + stp_configuration_update(stp); + stp_port_state_selection(stp); + if (!stp_is_root_bridge(stp) && root) { + stp_stop_timer(&stp->hello_timer); + if (stp->topology_change_detected) { + stp_stop_timer(&stp->topology_change_timer); + stp_transmit_tcn(stp); + stp_start_timer(&stp->tcn_timer, 0); + } + } + if (p == stp->root_port) { + stp_record_config_timeout_values(stp, config); + stp_config_bpdu_generation(stp); + if (config->flags & htons(STP_CONFIG_TOPOLOGY_CHANGE_ACK)) { + stp_topology_change_acknowledged(stp); + } + } + } else if (stp_is_designated_port(p)) { + stp_transmit_config(p); + } + } +} + +void +stp_received_tcn_bpdu(struct stp *stp, struct stp_port *p, + const struct stp_tcn_bpdu *tcn) +{ + if (p->state != STP_DISABLED) { + if (stp_is_designated_port(p)) { + stp_topology_change_detection(stp); + stp_acknowledge_topology_change(p); + } + } +} + +static void +stp_hello_timer_expiry(struct stp *stp) +{ + stp_config_bpdu_generation(stp); + stp_start_timer(&stp->hello_timer, 0); +} + +static void +stp_message_age_timer_expiry(struct stp_port *p) +{ + struct stp *stp = p->stp; + bool root = stp_is_root_bridge(stp); + stp_become_designated_port(p); + stp_configuration_update(stp); + stp_port_state_selection(stp); + if (stp_is_root_bridge(stp) && !root) { + stp->max_age = stp->bridge_max_age; + stp->hello_time = stp->bridge_hello_time; + stp->forward_delay = stp->bridge_forward_delay; + stp_topology_change_detection(stp); + stp_stop_timer(&stp->tcn_timer); + stp_config_bpdu_generation(stp); + stp_start_timer(&stp->hello_timer, 0); + } +} + +static bool +stp_is_designated_for_some_port(const struct stp *stp) +{ + const struct stp_port *p; + + FOR_EACH_ENABLED_PORT (p, stp) { + if (p->designated_bridge == stp->bridge_id) { + return true; + } + } + return false; +} + +static void +stp_forward_delay_timer_expiry(struct stp_port *p) +{ + if (p->state == STP_LISTENING) { + stp_set_port_state(p, STP_LEARNING); + stp_start_timer(&p->forward_delay_timer, 0); + } else if (p->state == STP_LEARNING) { + stp_set_port_state(p, STP_FORWARDING); + if (stp_is_designated_for_some_port(p->stp)) { + if (p->change_detection_enabled) { + stp_topology_change_detection(p->stp); + } + } + } +} + +static void +stp_tcn_timer_expiry(struct stp *stp) +{ + stp_transmit_tcn(stp); + stp_start_timer(&stp->tcn_timer, 0); +} + +static void +stp_topology_change_timer_expiry(struct stp *stp) +{ + stp->topology_change_detected = false; + stp->topology_change = false; +} + +static void +stp_hold_timer_expiry(struct stp_port *p) +{ + if (p->config_pending) { + stp_transmit_config(p); + } +} + +static void +stp_initialize_port(struct stp_port *p, enum stp_state state) +{ + assert(state & (STP_DISABLED | STP_BLOCKING)); + stp_become_designated_port(p); + stp_set_port_state(p, state); + p->topology_change_ack = false; + p->config_pending = false; + p->change_detection_enabled = true; + stp_stop_timer(&p->message_age_timer); + stp_stop_timer(&p->forward_delay_timer); + stp_stop_timer(&p->hold_timer); +} + +static void +stp_become_root_bridge(struct stp *stp) +{ + stp->max_age = stp->bridge_max_age; + stp->hello_time = stp->bridge_hello_time; + stp->forward_delay = stp->bridge_forward_delay; + stp_topology_change_detection(stp); + stp_stop_timer(&stp->tcn_timer); + stp_config_bpdu_generation(stp); + stp_start_timer(&stp->hello_timer, 0); +} + +static void +stp_start_timer(struct stp_timer *timer, int value) +{ + timer->value = value; + timer->active = true; +} + +static void +stp_stop_timer(struct stp_timer *timer) +{ + timer->active = false; +} + +static bool +stp_timer_expired(struct stp_timer *timer, int elapsed, int timeout) +{ + if (timer->active) { + timer->value += elapsed; + if (timer->value >= timeout) { + timer->active = false; + return true; + } + } + return false; +} + diff --git a/secchan/secchan.c b/secchan/secchan.c index 5a41cc204..48f1bb7c9 100644 --- a/secchan/secchan.c +++ b/secchan/secchan.c @@ -62,6 +62,7 @@ #include "packets.h" #include "poll-loop.h" #include "rconn.h" +#include "stp.h" #include "timeval.h" #include "util.h" #include "vconn-ssl.h" @@ -108,6 +109,9 @@ struct settings { regex_t accept_controller_regex; /* Controller vconns to accept. */ const char *accept_controller_re; /* String version of regex. */ bool update_resolv_conf; /* Update /etc/resolv.conf? */ + + /* Spanning tree protocol. */ + bool stp; /* Enable spanning tree protocol? */ }; struct half { @@ -127,7 +131,7 @@ struct relay { }; struct hook { - bool (*packet_cb)(struct relay *, int half, void *aux); + bool (*packet_cb[2])(struct relay *, void *aux); void (*periodic_cb)(void *aux); void (*wait_cb)(void *aux); void *aux; @@ -148,10 +152,15 @@ static void relay_run(struct relay *, const struct hook[], size_t n_hooks); static void relay_wait(struct relay *); static void relay_destroy(struct relay *); -static struct hook make_hook(bool (*packet_cb)(struct relay *, int, void *), +static struct hook make_hook(bool (*local_packet_cb)(struct relay *, void *), + bool (*remote_packet_cb)(struct relay *, void *), void (*periodic_cb)(void *), void (*wait_cb)(void *), void *aux); +static struct ofp_packet_in *get_ofp_packet_in(struct relay *); +static bool get_ofp_packet_eth_header(struct relay *, struct ofp_packet_in **, + struct eth_header **); +static void get_ofp_packet_payload(struct ofp_packet_in *, struct buffer *); struct switch_status; struct status_reply; @@ -176,6 +185,20 @@ static void discovery_wait(struct discovery *); static struct hook in_band_hook_create(const struct settings *, struct switch_status *, struct rconn *remote); + +struct port_watcher; +static struct hook port_watcher_create(struct rconn *local, + struct rconn *remote, + struct port_watcher **); +static uint32_t port_watcher_get_flags(const struct port_watcher *, + int port_no); +static void port_watcher_set_flags(struct port_watcher *, + int port_no, uint32_t flags, uint32_t mask); + +static struct hook stp_hook_create(const struct settings *, + struct port_watcher *, + struct rconn *local, struct rconn *remote); + static struct hook fail_open_hook_create(const struct settings *, struct switch_status *, struct rconn *local, @@ -265,6 +288,11 @@ main(int argc, char *argv[]) list_push_back(&relays, &controller_relay->node); /* Set up hooks. */ + if (s.stp) { + struct port_watcher *pw; + hooks[n_hooks++] = port_watcher_create(local_rconn, remote_rconn, &pw); + hooks[n_hooks++] = stp_hook_create(&s, pw, local_rconn, remote_rconn); + } if (s.in_band) { hooks[n_hooks++] = in_band_hook_create(&s, switch_status, remote_rconn); @@ -375,18 +403,51 @@ accept_vconn(struct vconn *vconn) } static struct hook -make_hook(bool (*packet_cb)(struct relay *, int half, void *aux), +make_hook(bool (*local_packet_cb)(struct relay *, void *aux), + bool (*remote_packet_cb)(struct relay *, void *aux), void (*periodic_cb)(void *aux), void (*wait_cb)(void *aux), void *aux) { struct hook h; - h.packet_cb = packet_cb; + h.packet_cb[HALF_LOCAL] = local_packet_cb; + h.packet_cb[HALF_REMOTE] = remote_packet_cb; h.periodic_cb = periodic_cb; h.wait_cb = wait_cb; h.aux = aux; return h; } + +static struct ofp_packet_in * +get_ofp_packet_in(struct relay *r) +{ + struct buffer *msg = r->halves[HALF_LOCAL].rxbuf; + struct ofp_header *oh = msg->data; + if (oh->type == OFPT_PACKET_IN) { + if (msg->size >= offsetof (struct ofp_packet_in, data)) { + return msg->data; + } else { + VLOG_WARN("packet too short (%zu bytes) for packet_in", + msg->size); + } + } + return NULL; +} + +static bool +get_ofp_packet_eth_header(struct relay *r, struct ofp_packet_in **opip, + struct eth_header **ethp) +{ + const int min_len = offsetof(struct ofp_packet_in, data) + ETH_HEADER_LEN; + struct ofp_packet_in *opi = get_ofp_packet_in(r); + if (opi && ntohs(opi->header.length) >= min_len) { + *opip = opi; + *ethp = (void *) opi->data; + return true; + } + return false; +} + /* OpenFlow message relaying. */ @@ -459,10 +520,10 @@ relay_run(struct relay *r, const struct hook hooks[], size_t n_hooks) if (!this->rxbuf) { this->rxbuf = rconn_recv(this->rconn); - if (this->rxbuf) { + if (this->rxbuf && (i == HALF_REMOTE || !r->is_mgmt_conn)) { const struct hook *h; for (h = hooks; h < &hooks[n_hooks]; h++) { - if (h->packet_cb(r, i, h->aux)) { + if (h->packet_cb[i] && h->packet_cb[i](r, h->aux)) { buffer_delete(this->rxbuf); this->rxbuf = NULL; progress = true; @@ -530,6 +591,532 @@ relay_destroy(struct relay *r) free(r); } +/* Port status watcher. */ + +typedef void port_watcher_cb_func(uint16_t port_no, + const struct ofp_phy_port *old, + const struct ofp_phy_port *new, + void *aux); + +struct port_watcher_cb { + port_watcher_cb_func *function; + void *aux; +}; + +struct port_watcher { + struct rconn *local_rconn; + struct rconn *remote_rconn; + struct ofp_phy_port ports[OFPP_MAX + 1]; + time_t last_feature_request; + bool got_feature_reply; + int n_txq; + struct port_watcher_cb cbs[2]; + int n_cbs; +}; + +/* Returns the number of fields that differ from 'a' to 'b'. */ +static int +opp_differs(const struct ofp_phy_port *a, const struct ofp_phy_port *b) +{ + BUILD_ASSERT_DECL(sizeof *a == 36); /* Trips when we add or remove fields. */ + return ((a->port_no != b->port_no) + + (memcmp(a->hw_addr, b->hw_addr, sizeof a->hw_addr) != 0) + + (memcmp(a->name, b->name, sizeof a->name) != 0) + + (a->flags != b->flags) + + (a->speed != b->speed) + + (a->features != b->features)); +} + +static void +sanitize_opp(struct ofp_phy_port *opp) +{ + size_t i; + + for (i = 0; i < sizeof opp->name; i++) { + char c = opp->name[i]; + if (c && (c < 0x20 || c > 0x7e)) { + opp->name[i] = '.'; + } + } + opp->name[sizeof opp->name - 1] = '\0'; +} + +static int +port_no_to_pw_idx(int port_no) +{ + return (port_no < OFPP_MAX ? port_no + : port_no == OFPP_LOCAL ? OFPP_MAX + : -1); +} + +static void +call_pw_callbacks(struct port_watcher *pw, int port_no, + const struct ofp_phy_port *old, + const struct ofp_phy_port *new) +{ + if (opp_differs(old, new)) { + int i; + for (i = 0; i < pw->n_cbs; i++) { + pw->cbs[i].function(port_no, old, new, pw->cbs[i].aux); + } + } +} + +static void +update_phy_port(struct port_watcher *pw, struct ofp_phy_port *opp, + uint8_t reason, bool seen[OFPP_MAX + 1]) +{ + struct ofp_phy_port *pw_opp; + struct ofp_phy_port old; + uint16_t port_no; + int idx; + + port_no = ntohs(opp->port_no); + idx = port_no_to_pw_idx(port_no); + if (idx < 0) { + return; + } + + if (seen) { + seen[idx] = true; + } + + pw_opp = &pw->ports[idx]; + old = *pw_opp; + if (reason == OFPPR_DELETE) { + memset(pw_opp, 0, sizeof *pw_opp); + pw_opp->port_no = htons(OFPP_NONE); + } else if (reason == OFPPR_MOD || reason == OFPPR_ADD) { + *pw_opp = *opp; + sanitize_opp(pw_opp); + } + call_pw_callbacks(pw, port_no, &old, pw_opp); +} + +static bool +port_watcher_local_packet_cb(struct relay *r, void *pw_) +{ + struct port_watcher *pw = pw_; + struct buffer *msg = r->halves[HALF_LOCAL].rxbuf; + struct ofp_header *oh = msg->data; + + if (oh->type == OFPT_FEATURES_REPLY + && msg->size >= offsetof(struct ofp_switch_features, ports)) { + struct ofp_switch_features *osf = msg->data; + bool seen[ARRAY_SIZE(pw->ports)]; + size_t n_ports; + size_t i; + + pw->got_feature_reply = true; + + /* Update each port included in the message. */ + memset(seen, 0, sizeof seen); + n_ports = ((msg->size - offsetof(struct ofp_switch_features, ports)) + / sizeof *osf->ports); + for (i = 0; i < n_ports; i++) { + update_phy_port(pw, &osf->ports[i], OFPPR_MOD, seen); + } + + /* Delete all the ports not included in the message. */ + for (i = 0; i < ARRAY_SIZE(pw->ports); i++) { + if (!seen[i]) { + update_phy_port(pw, &pw->ports[i], OFPPR_DELETE, NULL); + } + } + } else if (oh->type == OFPT_PORT_STATUS + && msg->size >= sizeof(struct ofp_port_status)) { + struct ofp_port_status *ops = msg->data; + update_phy_port(pw, &ops->desc, ops->reason, NULL); + } + return false; +} + +static void +port_watcher_periodic_cb(void *pw_) +{ + struct port_watcher *pw = pw_; + + if (!pw->got_feature_reply && time_now() >= pw->last_feature_request + 5) { + struct buffer *b; + make_openflow(sizeof(struct ofp_header), OFPT_FEATURES_REQUEST, &b); + rconn_send_with_limit(pw->local_rconn, b, &pw->n_txq, 1); + pw->last_feature_request = time_now(); + } +} + +static void +put_duplexes(struct ds *ds, const char *name, uint32_t features, + uint32_t hd_bit, uint32_t fd_bit) +{ + if (features & (hd_bit | fd_bit)) { + ds_put_format(ds, " %s", name); + if (features & hd_bit) { + ds_put_cstr(ds, "(HD)"); + } + if (features & fd_bit) { + ds_put_cstr(ds, "(FD)"); + } + } +} + +static void +log_port_status(uint16_t port_no, + const struct ofp_phy_port *old, + const struct ofp_phy_port *new, + void *aux) +{ + if (VLOG_IS_DBG_ENABLED()) { + bool was_enabled = old->port_no != htons(OFPP_NONE); + bool now_enabled = new->port_no != htons(OFPP_NONE); + uint32_t features = ntohl(new->features); + struct ds ds; + + if (old->flags != new->flags && opp_differs(old, new) == 1) { + /* Don't care if only flags changed. */ + return; + } + + ds_init(&ds); + ds_put_format(&ds, "\"%s\", "ETH_ADDR_FMT, new->name, + ETH_ADDR_ARGS(new->hw_addr)); + if (ntohl(new->speed)) { + ds_put_format(&ds, ", speed %"PRIu32, ntohl(new->speed)); + } + if (features & (OFPPF_10MB_HD | OFPPF_10MB_FD + | OFPPF_100MB_HD | OFPPF_100MB_FD + | OFPPF_1GB_HD | OFPPF_1GB_FD | OFPPF_10GB_FD)) { + ds_put_cstr(&ds, ", supports"); + put_duplexes(&ds, "10M", features, OFPPF_10MB_HD, OFPPF_10MB_FD); + put_duplexes(&ds, "100M", features, + OFPPF_100MB_HD, OFPPF_100MB_FD); + put_duplexes(&ds, "1G", features, OFPPF_100MB_HD, OFPPF_100MB_FD); + if (features & OFPPF_10GB_FD) { + ds_put_cstr(&ds, " 10G"); + } + } + if (was_enabled != now_enabled) { + if (now_enabled) { + VLOG_DBG("Port %d added: %s", port_no, ds_cstr(&ds)); + } else { + VLOG_DBG("Port %d deleted", port_no); + } + } else { + VLOG_DBG("Port %d changed: %s", port_no, ds_cstr(&ds)); + } + ds_destroy(&ds); + } +} + +static void +port_watcher_register_callback(struct port_watcher *pw, + port_watcher_cb_func *function, + void *aux) +{ + assert(pw->n_cbs < ARRAY_SIZE(pw->cbs)); + pw->cbs[pw->n_cbs].function = function; + pw->cbs[pw->n_cbs].aux = aux; + pw->n_cbs++; +} + +static uint32_t +port_watcher_get_flags(const struct port_watcher *pw, int port_no) +{ + int idx = port_no_to_pw_idx(port_no); + return idx >= 0 ? ntohl(pw->ports[idx].flags) : 0; +} + +static void +port_watcher_set_flags(struct port_watcher *pw, + int port_no, uint32_t flags, uint32_t mask) +{ + struct ofp_phy_port old; + struct ofp_phy_port *p; + struct ofp_port_mod *opm; + struct ofp_port_status *ops; + struct buffer *b; + int idx; + + idx = port_no_to_pw_idx(port_no); + if (idx < 0) { + return; + } + + p = &pw->ports[idx]; + if (!((ntohl(p->flags) ^ flags) & mask)) { + return; + } + old = *p; + + /* Update our idea of the flags. */ + p->flags = ntohl(flags); + call_pw_callbacks(pw, port_no, &old, p); + + /* Change the flags in the datapath. */ + opm = make_openflow(sizeof *opm, OFPT_PORT_MOD, &b); + opm->mask = htonl(mask); + opm->desc = *p; + rconn_send(pw->local_rconn, b, NULL); + + /* Notify the controller that the flags changed. */ + ops = make_openflow(sizeof *ops, OFPT_PORT_STATUS, &b); + ops->reason = OFPPR_MOD; + ops->desc = *p; + rconn_send(pw->remote_rconn, b, NULL); +} + +static bool +port_watcher_is_ready(const struct port_watcher *pw) +{ + return pw->got_feature_reply; +} + +static struct hook +port_watcher_create(struct rconn *local_rconn, struct rconn *remote_rconn, + struct port_watcher **pwp) +{ + struct port_watcher *pw; + int i; + + pw = *pwp = xcalloc(1, sizeof *pw); + pw->local_rconn = local_rconn; + pw->remote_rconn = remote_rconn; + pw->last_feature_request = TIME_MIN; + for (i = 0; i < OFPP_MAX; i++) { + pw->ports[i].port_no = htons(OFPP_NONE); + } + port_watcher_register_callback(pw, log_port_status, NULL); + return make_hook(port_watcher_local_packet_cb, NULL, + port_watcher_periodic_cb, NULL, pw); +} + +/* Spanning tree protocol. */ + +/* Extra time, in seconds, at boot before going into fail-open, to give the + * spanning tree protocol time to figure out the network layout. */ +#define STP_EXTRA_BOOT_TIME 30 + +struct stp_data { + struct stp *stp; + struct port_watcher *pw; + struct rconn *local_rconn; + struct rconn *remote_rconn; + uint8_t dpid[ETH_ADDR_LEN]; + long long int last_tick_256ths; + int n_txq; +}; + +static bool +stp_local_packet_cb(struct relay *r, void *stp_) +{ + struct stp_data *stp = stp_; + struct ofp_packet_in *opi; + struct eth_header *eth; + struct llc_header *llc; + struct buffer payload; + uint16_t port_no; + struct flow flow; + + if (!get_ofp_packet_eth_header(r, &opi, ð) + || !eth_addr_equals(eth->eth_dst, stp_eth_addr)) { + return false; + } + + port_no = ntohs(opi->in_port); + if (port_no >= STP_MAX_PORTS) { + /* STP only supports 255 ports. */ + return false; + } + if (port_watcher_get_flags(stp->pw, port_no) & OFPPFL_NO_STP) { + /* We're not doing STP on this port. */ + return false; + } + + if (opi->reason == OFPR_ACTION) { + /* The controller set up a flow for this, so we won't intercept it. */ + return false; + } + + get_ofp_packet_payload(opi, &payload); + flow_extract(&payload, port_no, &flow); + if (flow.dl_type != htons(OFP_DL_TYPE_NOT_ETH_TYPE)) { + VLOG_DBG("non-LLC frame received on STP multicast address"); + return false; + } + llc = buffer_at_assert(&payload, sizeof *eth, sizeof *llc); + if (llc->llc_dsap != STP_LLC_DSAP) { + VLOG_DBG("bad DSAP 0x%02"PRIx8" received on STP multicast address", + llc->llc_dsap); + return false; + } + + /* Trim off padding on payload. */ + if (payload.size > ntohs(eth->eth_type) + ETH_HEADER_LEN) { + payload.size = ntohs(eth->eth_type) + ETH_HEADER_LEN; + } + if (buffer_try_pull(&payload, ETH_HEADER_LEN + LLC_HEADER_LEN)) { + struct stp_port *p = stp_get_port(stp->stp, port_no); + stp_received_bpdu(p, payload.data, payload.size); + } + + return true; +} + +static long long int +time_256ths(void) +{ + return time_msec() * 256 / 1000; +} + +static void +stp_periodic_cb(void *stp_) +{ + struct stp_data *stp = stp_; + long long int now_256ths = time_256ths(); + long long int elapsed_256ths = now_256ths - stp->last_tick_256ths; + struct stp_port *p; + + if (!port_watcher_is_ready(stp->pw)) { + /* Can't start STP until we know port flags, because port flags can + * disable STP. */ + return; + } + if (elapsed_256ths <= 0) { + return; + } + + stp_tick(stp->stp, MIN(INT_MAX, elapsed_256ths)); + stp->last_tick_256ths = now_256ths; + + while (stp_get_changed_port(stp->stp, &p)) { + int port_no = stp_port_no(p); + enum stp_state state = stp_port_get_state(p); + + if (state != STP_DISABLED) { + VLOG_WARN("STP: Port %d entered %s state", + port_no, stp_state_name(state)); + } + if (!(port_watcher_get_flags(stp->pw, port_no) & OFPPFL_NO_STP)) { + uint32_t flags; + switch (state) { + case STP_LISTENING: + flags = OFPPFL_STP_LISTEN; + break; + case STP_LEARNING: + flags = OFPPFL_STP_LEARN; + break; + case STP_DISABLED: + case STP_FORWARDING: + flags = OFPPFL_STP_FORWARD; + break; + case STP_BLOCKING: + flags = OFPPFL_STP_BLOCK; + break; + default: + VLOG_DBG_RL(&vrl, "STP: Port %d has bad state %x", + port_no, state); + flags = OFPPFL_STP_FORWARD; + break; + } + if (!stp_forward_in_state(state)) { + flags |= OFPPFL_NO_FLOOD; + } + port_watcher_set_flags(stp->pw, port_no, flags, + OFPPFL_STP_MASK | OFPPFL_NO_FLOOD); + } else { + /* We don't own those flags. */ + } + } +} + +static void +stp_wait_cb(void *stp_ UNUSED) +{ + poll_timer_wait(1000); +} + +static void +send_bpdu(const void *bpdu, size_t bpdu_size, int port_no, void *stp_) +{ + struct stp_data *stp = stp_; + struct eth_header *eth; + struct llc_header *llc; + struct buffer pkt, *opo; + + /* Packet skeleton. */ + buffer_init(&pkt, ETH_HEADER_LEN + LLC_HEADER_LEN + bpdu_size); + eth = buffer_put_uninit(&pkt, sizeof *eth); + llc = buffer_put_uninit(&pkt, sizeof *llc); + buffer_put(&pkt, bpdu, bpdu_size); + + /* 802.2 header. */ + memcpy(eth->eth_dst, stp_eth_addr, ETH_ADDR_LEN); + memcpy(eth->eth_src, stp->pw->ports[port_no].hw_addr, ETH_ADDR_LEN); + eth->eth_type = htons(pkt.size - ETH_HEADER_LEN); + + /* LLC header. */ + llc->llc_dsap = STP_LLC_DSAP; + llc->llc_ssap = STP_LLC_SSAP; + llc->llc_cntl = STP_LLC_CNTL; + + opo = make_unbuffered_packet_out(&pkt, OFPP_NONE, port_no); + buffer_uninit(&pkt); + rconn_send_with_limit(stp->local_rconn, opo, &stp->n_txq, OFPP_MAX); +} + +static void +stp_port_watcher_cb(uint16_t port_no, + const struct ofp_phy_port *old, + const struct ofp_phy_port *new, + void *stp_) +{ + struct stp_data *stp = stp_; + struct stp_port *p; + + /* STP only supports a maximum of 255 ports, one less than OpenFlow. We + * don't support STP on OFPP_LOCAL, either. */ + if (port_no >= STP_MAX_PORTS) { + return; + } + + p = stp_get_port(stp->stp, port_no); + if (new->port_no == htons(OFPP_NONE) + || new->flags & htonl(OFPPFL_NO_STP)) { + stp_port_disable(p); + } else { + stp_port_enable(p); + stp_port_set_speed(p, new->speed); + } +} + +static struct hook +stp_hook_create(const struct settings *s, struct port_watcher *pw, + struct rconn *local, struct rconn *remote) +{ + uint8_t dpid[ETH_ADDR_LEN]; + struct netdev *netdev; + struct stp_data *stp; + int retval; + + retval = netdev_open(s->of_name, NETDEV_ETH_TYPE_NONE, &netdev); + if (retval) { + fatal(retval, "Could not open %s device", s->of_name); + } + memcpy(dpid, netdev_get_etheraddr(netdev), ETH_ADDR_LEN); + netdev_close(netdev); + + stp = xcalloc(1, sizeof *stp); + stp->stp = stp_create("stp", eth_addr_to_uint64(dpid), send_bpdu, stp); + stp->pw = pw; + memcpy(stp->dpid, dpid, ETH_ADDR_LEN); + stp->local_rconn = local; + stp->remote_rconn = remote; + stp->last_tick_256ths = time_256ths(); + + port_watcher_register_callback(pw, stp_port_watcher_cb, stp); + return make_hook(stp_local_packet_cb, NULL, + stp_periodic_cb, stp_wait_cb, stp); +} + /* In-band control. */ struct in_band_data { @@ -605,73 +1192,70 @@ is_controller_mac(const uint8_t dl_addr[ETH_ADDR_LEN], } static void -in_band_learn_mac(struct in_band_data *in_band, const struct flow *flow) +in_band_learn_mac(struct in_band_data *in_band, + uint16_t in_port, const uint8_t src_mac[ETH_ADDR_LEN]) { - uint16_t in_port = ntohs(flow->in_port); - if (mac_learning_learn(in_band->ml, flow->dl_src, in_port)) { + if (mac_learning_learn(in_band->ml, src_mac, in_port)) { VLOG_DBG_RL(&vrl, "learned that "ETH_ADDR_FMT" is on port %"PRIu16, - ETH_ADDR_ARGS(flow->dl_src), in_port); + ETH_ADDR_ARGS(src_mac), in_port); } } static bool -in_band_packet_cb(struct relay *r, int half, void *in_band_) +in_band_local_packet_cb(struct relay *r, void *in_band_) { struct in_band_data *in_band = in_band_; struct rconn *rc = r->halves[HALF_LOCAL].rconn; - struct buffer *msg = r->halves[HALF_LOCAL].rxbuf; struct ofp_packet_in *opi; - struct ofp_header *oh; - size_t pkt_ofs, pkt_len; - struct buffer pkt; + struct eth_header *eth; + struct buffer payload; struct flow flow; - uint16_t in_port, out_port; + uint16_t in_port; + int out_port; - if (half != HALF_LOCAL || r->is_mgmt_conn) { + if (!get_ofp_packet_eth_header(r, &opi, ð)) { return false; } - - oh = msg->data; - if (oh->type != OFPT_PACKET_IN) { - return false; - } - if (msg->size < offsetof(struct ofp_packet_in, data)) { - VLOG_WARN_RL(&vrl, "packet too short (%zu bytes) for packet_in", - msg->size); - return false; - } - - /* Extract flow data from 'opi' into 'flow'. */ - opi = msg->data; in_port = ntohs(opi->in_port); - pkt_ofs = offsetof(struct ofp_packet_in, data); - pkt_len = ntohs(opi->header.length) - pkt_ofs; - pkt.data = opi->data; - pkt.size = pkt_len; - flow_extract(&pkt, in_port, &flow); /* Deal with local stuff. */ if (in_port == OFPP_LOCAL) { /* Sent by secure channel. */ - out_port = mac_learning_lookup(in_band->ml, flow.dl_dst); - } else if (eth_addr_equals(flow.dl_dst, in_band->mac)) { + out_port = mac_learning_lookup(in_band->ml, eth->eth_dst); + } else if (eth_addr_equals(eth->eth_dst, in_band->mac)) { /* Sent to secure channel. */ out_port = OFPP_LOCAL; - in_band_learn_mac(in_band, &flow); - } else if (flow.dl_type == htons(ETH_TYPE_ARP) - && eth_addr_is_broadcast(flow.dl_dst) - && is_controller_mac(flow.dl_src, in_band)) { + in_band_learn_mac(in_band, in_port, eth->eth_src); + } else if (eth->eth_type == htons(ETH_TYPE_ARP) + && eth_addr_is_broadcast(eth->eth_dst) + && is_controller_mac(eth->eth_src, in_band)) { /* ARP sent by controller. */ out_port = OFPP_FLOOD; - } else if (is_controller_mac(flow.dl_dst, in_band) - || is_controller_mac(flow.dl_src, in_band)) { + } else if (is_controller_mac(eth->eth_dst, in_band) + || is_controller_mac(eth->eth_src, in_band)) { /* Traffic to or from controller. Switch it by hand. */ - in_band_learn_mac(in_band, &flow); - out_port = mac_learning_lookup(in_band->ml, flow.dl_dst); + in_band_learn_mac(in_band, in_port, eth->eth_src); + out_port = mac_learning_lookup(in_band->ml, eth->eth_dst); } else { - return false; + const uint8_t *controller_mac; + controller_mac = get_controller_mac(in_band); + if (eth->eth_type == htons(ETH_TYPE_ARP) + && eth_addr_is_broadcast(eth->eth_dst) + && is_controller_mac(eth->eth_src, in_band)) { + /* ARP sent by controller. */ + out_port = OFPP_FLOOD; + } else if (is_controller_mac(eth->eth_dst, in_band) + && in_port == mac_learning_lookup(in_band->ml, + controller_mac)) { + /* Drop controller traffic that arrives on the controller port. */ + out_port = -1; + } else { + return false; + } } + get_ofp_packet_payload(opi, &payload); + flow_extract(&payload, in_port, &flow); if (in_port == out_port) { /* The input and output port match. Set up a flow to drop packets. */ queue_tx(rc, in_band, make_add_flow(&flow, ntohl(opi->buffer_id), @@ -685,14 +1269,14 @@ in_band_packet_cb(struct relay *r, int half, void *in_band_) /* If the switch didn't buffer the packet, we need to send a copy. */ if (ntohl(opi->buffer_id) == UINT32_MAX) { queue_tx(rc, in_band, - make_unbuffered_packet_out(&pkt, in_port, out_port)); + make_unbuffered_packet_out(&payload, in_port, out_port)); } } else { /* We don't know that MAC. Send along the packet without setting up a * flow. */ struct buffer *b; if (ntohl(opi->buffer_id) == UINT32_MAX) { - b = make_unbuffered_packet_out(&pkt, in_port, out_port); + b = make_unbuffered_packet_out(&payload, in_port, out_port); } else { b = make_buffered_packet_out(ntohl(opi->buffer_id), in_port, out_port); @@ -728,6 +1312,14 @@ in_band_status_cb(struct status_reply *sr, void *in_band_) } } +static void +get_ofp_packet_payload(struct ofp_packet_in *opi, struct buffer *payload) +{ + payload->data = opi->data; + payload->size = ntohs(opi->header.length) - offsetof(struct ofp_packet_in, + data); +} + static struct hook in_band_hook_create(const struct settings *s, struct switch_status *ss, struct rconn *remote) @@ -747,7 +1339,7 @@ in_band_hook_create(const struct settings *s, struct switch_status *ss, ETH_ADDR_LEN); in_band->controller = remote; switch_status_register_category(ss, "in-band", in_band_status_cb, in_band); - return make_hook(in_band_packet_cb, NULL, NULL, in_band); + return make_hook(in_band_local_packet_cb, NULL, NULL, NULL, in_band); } /* Fail open support. */ @@ -758,6 +1350,7 @@ struct fail_open_data { struct rconn *remote_rconn; struct lswitch *lswitch; int last_disconn_secs; + time_t boot_deadline; }; /* Causes 'r' to enter or leave fail-open mode, if appropriate. */ @@ -768,6 +1361,9 @@ fail_open_periodic_cb(void *fail_open_) int disconn_secs; bool open; + if (time_now() < fail_open->boot_deadline) { + return; + } disconn_secs = rconn_disconnected_duration(fail_open->remote_rconn); open = disconn_secs >= fail_open->s->probe_interval * 3; if (open != (fail_open->lswitch != NULL)) { @@ -790,10 +1386,10 @@ fail_open_periodic_cb(void *fail_open_) } static bool -fail_open_packet_cb(struct relay *r, int half, void *fail_open_) +fail_open_local_packet_cb(struct relay *r, void *fail_open_) { struct fail_open_data *fail_open = fail_open_; - if (half != HALF_LOCAL || r->is_mgmt_conn || !fail_open->lswitch) { + if (!fail_open->lswitch) { return false; } else { lswitch_process_packet(fail_open->lswitch, fail_open->local_rconn, @@ -827,10 +1423,14 @@ fail_open_hook_create(const struct settings *s, struct switch_status *ss, fail_open->local_rconn = local_rconn; fail_open->remote_rconn = remote_rconn; fail_open->lswitch = NULL; + fail_open->boot_deadline = time_now() + s->probe_interval * 3; + if (s->stp) { + fail_open->boot_deadline += STP_EXTRA_BOOT_TIME; + } switch_status_register_category(ss, "fail-open", fail_open_status_cb, fail_open); - return make_hook(fail_open_packet_cb, fail_open_periodic_cb, NULL, - fail_open); + return make_hook(fail_open_local_packet_cb, NULL, + fail_open_periodic_cb, NULL, fail_open); } struct rate_limiter { @@ -937,24 +1537,14 @@ get_token(struct rate_limiter *rl) } static bool -rate_limit_packet_cb(struct relay *r, int half, void *rl_) +rate_limit_local_packet_cb(struct relay *r, void *rl_) { struct rate_limiter *rl = rl_; const struct settings *s = rl->s; - struct buffer *msg = r->halves[HALF_LOCAL].rxbuf; - struct ofp_header *oh; + struct ofp_packet_in *opi; - if (half == HALF_REMOTE) { - return false; - } - - oh = msg->data; - if (oh->type != OFPT_PACKET_IN) { - return false; - } - if (msg->size < offsetof(struct ofp_packet_in, data)) { - VLOG_WARN_RL(&vrl, "packet too short (%zu bytes) for packet_in", - msg->size); + opi = get_ofp_packet_in(r); + if (!opi) { return false; } @@ -965,7 +1555,7 @@ rate_limit_packet_cb(struct relay *r, int half, void *rl_) return false; } else { /* Otherwise queue it up for the periodic callback to drain out. */ - struct ofp_packet_in *opi = msg->data; + struct buffer *msg = r->halves[HALF_LOCAL].rxbuf; int port = ntohs(opi->in_port) % OFPP_MAX; if (rl->n_queued >= s->burst_limit) { drop_packet(rl); @@ -1042,7 +1632,7 @@ rate_limit_hook_create(const struct settings *s, struct switch_status *ss, rl->tokens = s->rate_limit * 100; switch_status_register_category(ss, "rate-limit", rate_limit_status_cb, rl); - return make_hook(rate_limit_packet_cb, rate_limit_periodic_cb, + return make_hook(rate_limit_local_packet_cb, NULL, rate_limit_periodic_cb, rate_limit_wait_cb, rl); } @@ -1068,7 +1658,7 @@ struct status_reply { }; static bool -switch_status_packet_cb(struct relay *r, int half, void *ss_) +switch_status_remote_packet_cb(struct relay *r, void *ss_) { struct switch_status *ss = ss_; struct rconn *rc = r->halves[HALF_REMOTE].rconn; @@ -1081,10 +1671,6 @@ switch_status_packet_cb(struct relay *r, int half, void *ss_) struct buffer *b; int retval; - if (half == HALF_LOCAL) { - return false; - } - oh = msg->data; if (oh->type != OFPT_STATS_REQUEST) { return false; @@ -1186,7 +1772,7 @@ switch_status_hook_create(const struct settings *s, struct switch_status **ssp) config_status_cb, (void *) s); switch_status_register_category(ss, "switch", switch_status_cb, ss); *ssp = ss; - return make_hook(switch_status_packet_cb, NULL, NULL, ss); + return make_hook(NULL, switch_status_remote_packet_cb, NULL, NULL, ss); } static void diff --git a/switch/datapath.c b/switch/datapath.c index 953a30ba4..e91fc9982 100644 --- a/switch/datapath.c +++ b/switch/datapath.c @@ -46,6 +46,7 @@ #include "packets.h" #include "poll-loop.h" #include "rconn.h" +#include "stp.h" #include "vconn.h" #include "table.h" #include "timeval.h" @@ -54,15 +55,6 @@ #define THIS_MODULE VLM_datapath #include "vlog.h" -enum br_port_flags { - BRPF_NO_FLOOD = 1 << 0, -}; - -enum br_port_status { - BRPS_PORT_DOWN = 1 << 0, - BRPS_LINK_DOWN = 1 << 1, -}; - extern char mfr_desc; extern char hw_desc; extern char sw_desc; @@ -84,9 +76,12 @@ extern char serial_num; | (1 << OFPAT_SET_TP_SRC) \ | (1 << OFPAT_SET_TP_DST) ) +#define PORT_STATUS_BITS (OFPPFL_PORT_DOWN | OFPPFL_LINK_DOWN) +#define PORT_FLAG_BITS (~PORT_STATUS_BITS) + struct sw_port { - uint32_t flags; /* BRPF_* flags */ - uint32_t status; /* BRPS_* flags */ + uint32_t flags; /* Some subset of PORT_FLAG_BITS. */ + uint32_t status; /* Some subset of PORT_STATUS_BITS. */ struct datapath *dp; struct netdev *netdev; struct list node; /* Element in datapath.ports. */ @@ -148,7 +143,7 @@ static void remote_wait(struct remote *); static void remote_destroy(struct remote *); void dp_output_port(struct datapath *, struct buffer *, - int in_port, int out_port); + int in_port, int out_port, bool ignore_no_fwd); void dp_update_port_flags(struct datapath *dp, const struct ofp_port_mod *opm); void dp_output_control(struct datapath *, struct buffer *, int in_port, size_t max_len, int reason); @@ -159,7 +154,8 @@ static void send_port_status(struct sw_port *p, uint8_t status); static void del_switch_port(struct sw_port *p); static void execute_actions(struct datapath *, struct buffer *, int in_port, const struct sw_flow_key *, - const struct ofp_action *, int n_actions); + const struct ofp_action *, int n_actions, + bool ignore_no_fwd); static void modify_vlan(struct buffer *buffer, const struct sw_flow_key *key, const struct ofp_action *a); static void modify_nh(struct buffer *buffer, uint16_t eth_proto, @@ -178,8 +174,9 @@ static void modify_th(struct buffer *buffer, uint16_t eth_proto, #define PKT_COOKIE_BITS (32 - PKT_BUFFER_BITS) -int run_flow_through_tables(struct datapath *, struct buffer *, int in_port); -void fwd_port_input(struct datapath *, struct buffer *, int in_port); +int run_flow_through_tables(struct datapath *, struct buffer *, + struct sw_port *); +void fwd_port_input(struct datapath *, struct buffer *, struct sw_port *); int fwd_control_input(struct datapath *, const struct sender *, const void *, size_t); @@ -331,7 +328,7 @@ dp_run(struct datapath *dp) if (!error) { p->rx_packets++; p->rx_bytes += buffer->size; - fwd_port_input(dp, buffer, port_no(dp, p)); + fwd_port_input(dp, buffer, p); buffer = NULL; } else if (error != EAGAIN) { VLOG_ERR_RL(&rl, "error receiving data from %s: %s", @@ -527,16 +524,17 @@ output_all(struct datapath *dp, struct buffer *buffer, int in_port, int flood) if (port_no(dp, p) == in_port) { continue; } - if (flood && p->flags & BRPF_NO_FLOOD) { + if (flood && p->flags & OFPPFL_NO_FLOOD) { continue; } if (prev_port != -1) { - dp_output_port(dp, buffer_clone(buffer), in_port, prev_port); + dp_output_port(dp, buffer_clone(buffer), in_port, prev_port, + false); } prev_port = port_no(dp, p); } if (prev_port != -1) - dp_output_port(dp, buffer, in_port, prev_port); + dp_output_port(dp, buffer, in_port, prev_port, false); else buffer_delete(buffer); @@ -548,7 +546,7 @@ output_packet(struct datapath *dp, struct buffer *buffer, int out_port) { if (out_port >= 0 && out_port < OFPP_MAX) { struct sw_port *p = &dp->ports[out_port]; - if (p->netdev != NULL && !(p->status & BRPS_PORT_DOWN)) { + if (p->netdev != NULL && !(p->status & OFPPFL_PORT_DOWN)) { if (!netdev_send(p->netdev, buffer)) { p->tx_packets++; p->tx_bytes += buffer->size; @@ -567,7 +565,7 @@ output_packet(struct datapath *dp, struct buffer *buffer, int out_port) */ void dp_output_port(struct datapath *dp, struct buffer *buffer, - int in_port, int out_port) + int in_port, int out_port, bool ignore_no_fwd) { assert(buffer); @@ -580,7 +578,8 @@ dp_output_port(struct datapath *dp, struct buffer *buffer, } else if (out_port == OFPP_IN_PORT) { output_packet(dp, buffer, in_port); } else if (out_port == OFPP_TABLE) { - if (run_flow_through_tables(dp, buffer, in_port)) { + struct sw_port *p = in_port < OFPP_MAX ? &dp->ports[in_port] : 0; + if (run_flow_through_tables(dp, buffer, p)) { buffer_delete(buffer); } } else { @@ -661,14 +660,7 @@ static void fill_port_desc(struct datapath *dp, struct sw_port *p, desc->flags = 0; desc->features = htonl(netdev_get_features(p->netdev)); desc->speed = htonl(netdev_get_speed(p->netdev)); - - if (p->flags & BRPF_NO_FLOOD) { - desc->flags |= htonl(OFPPFL_NO_FLOOD); - } else if (p->status & BRPS_PORT_DOWN) { - desc->flags |= htonl(OFPPFL_PORT_DOWN); - } else if (p->status & BRPS_LINK_DOWN) { - desc->flags |= htonl(OFPPFL_LINK_DOWN); - } + desc->flags = htonl(p->flags | p->status); } static void @@ -703,6 +695,7 @@ dp_update_port_flags(struct datapath *dp, const struct ofp_port_mod *opm) int port_no = ntohs(opp->port_no); if (port_no < OFPP_MAX) { struct sw_port *p = &dp->ports[port_no]; + uint32_t flag_mask; /* Make sure the port id hasn't changed since this was sent */ if (!p || memcmp(opp->hw_addr, netdev_get_etheraddr(p->netdev), @@ -711,21 +704,20 @@ dp_update_port_flags(struct datapath *dp, const struct ofp_port_mod *opm) } - if (opm->mask & htonl(OFPPFL_NO_FLOOD)) { - if (opp->flags & htonl(OFPPFL_NO_FLOOD)) - p->flags |= BRPF_NO_FLOOD; - else - p->flags &= ~BRPF_NO_FLOOD; + flag_mask = ntohl(opm->mask) & PORT_FLAG_BITS; + if (flag_mask) { + p->flags &= ~flag_mask; + p->flags |= ntohl(opp->flags) & flag_mask; } if (opm->mask & htonl(OFPPFL_PORT_DOWN)) { if ((opp->flags & htonl(OFPPFL_PORT_DOWN)) - && (p->status & BRPS_PORT_DOWN) == 0) { - p->status |= BRPS_PORT_DOWN; + && (p->status & OFPPFL_PORT_DOWN) == 0) { + p->status |= OFPPFL_PORT_DOWN; netdev_turn_flags_off(p->netdev, NETDEV_UP, true); } else if ((opp->flags & htonl(OFPPFL_PORT_DOWN)) == 0 - && (p->status & BRPS_PORT_DOWN)) { - p->status &= ~BRPS_PORT_DOWN; + && (p->status & OFPPFL_PORT_DOWN)) { + p->status &= ~OFPPFL_PORT_DOWN; netdev_turn_flags_on(p->netdev, NETDEV_UP, true); } } @@ -751,9 +743,9 @@ update_port_status(struct sw_port *p) return 0; } else { if (flags & NETDEV_UP) { - p->status &= ~BRPS_PORT_DOWN; + p->status &= ~OFPPFL_PORT_DOWN; } else { - p->status |= BRPS_PORT_DOWN; + p->status |= OFPPFL_PORT_DOWN; } } @@ -761,9 +753,9 @@ update_port_status(struct sw_port *p) * error. */ retval = netdev_get_link_status(p->netdev); if (retval == 1) { - p->status &= ~BRPS_LINK_DOWN; + p->status &= ~OFPPFL_LINK_DOWN; } else if (retval == 0) { - p->status |= BRPS_LINK_DOWN; + p->status |= OFPPFL_LINK_DOWN; } return (orig_status != p->status); @@ -850,52 +842,59 @@ fill_flow_stats(struct buffer *buffer, struct sw_flow *flow, } -/* 'buffer' was received on 'in_port', a physical switch port between 0 and - * OFPP_MAX. Process it according to 'dp''s flow table. Returns 0 if +/* 'buffer' was received on 'p', which may be a a physical switch port or a + * null pointer. Process it according to 'dp''s flow table. Returns 0 if * successful, in which case 'buffer' is destroyed, or -ESRCH if there is no * matching flow, in which case 'buffer' still belongs to the caller. */ int run_flow_through_tables(struct datapath *dp, struct buffer *buffer, - int in_port) + struct sw_port *p) { struct sw_flow_key key; struct sw_flow *flow; key.wildcards = 0; - if (flow_extract(buffer, in_port, &key.flow) + if (flow_extract(buffer, p ? port_no(dp, p) : OFPP_NONE, &key.flow) && (dp->flags & OFPC_FRAG_MASK) == OFPC_FRAG_DROP) { /* Drop fragment. */ buffer_delete(buffer); return 0; } + if (p && p->flags & (OFPPFL_NO_RECV | OFPPFL_NO_RECV_STP) + && p->flags & (!eth_addr_equals(key.flow.dl_dst, stp_eth_addr) + ? OFPPFL_NO_RECV : OFPPFL_NO_RECV_STP)) { + buffer_delete(buffer); + return 0; + } flow = chain_lookup(dp->chain, &key); if (flow != NULL) { flow_used(flow, buffer); - execute_actions(dp, buffer, in_port, &key, - flow->actions, flow->n_actions); + execute_actions(dp, buffer, port_no(dp, p), + &key, flow->actions, flow->n_actions, false); return 0; } else { return -ESRCH; } } -/* 'buffer' was received on 'in_port', a physical switch port between 0 and - * OFPP_MAX. Process it according to 'dp''s flow table, sending it up to the - * controller if no flow matches. Takes ownership of 'buffer'. */ -void fwd_port_input(struct datapath *dp, struct buffer *buffer, int in_port) +/* 'buffer' was received on 'p', which may be a a physical switch port or a + * null pointer. Process it according to 'dp''s flow table, sending it up to + * the controller if no flow matches. Takes ownership of 'buffer'. */ +void fwd_port_input(struct datapath *dp, struct buffer *buffer, + struct sw_port *p) { - if (run_flow_through_tables(dp, buffer, in_port)) { - dp_output_control(dp, buffer, in_port, dp->miss_send_len, - OFPR_NO_MATCH); + if (run_flow_through_tables(dp, buffer, p)) { + dp_output_control(dp, buffer, port_no(dp, p), + dp->miss_send_len, OFPR_NO_MATCH); } } static void do_output(struct datapath *dp, struct buffer *buffer, int in_port, - size_t max_len, int out_port) + size_t max_len, int out_port, bool ignore_no_fwd) { if (out_port != OFPP_CONTROLLER) { - dp_output_port(dp, buffer, in_port, out_port); + dp_output_port(dp, buffer, in_port, out_port, ignore_no_fwd); } else { dp_output_control(dp, buffer, in_port, max_len, OFPR_ACTION); } @@ -904,7 +903,8 @@ do_output(struct datapath *dp, struct buffer *buffer, int in_port, static void execute_actions(struct datapath *dp, struct buffer *buffer, int in_port, const struct sw_flow_key *key, - const struct ofp_action *actions, int n_actions) + const struct ofp_action *actions, int n_actions, + bool ignore_no_fwd) { /* Every output action needs a separate clone of 'buffer', but the common * case is just a single output action, so that doing a clone and then @@ -923,7 +923,8 @@ execute_actions(struct datapath *dp, struct buffer *buffer, struct eth_header *eh = buffer->l2; if (prev_port != -1) { - do_output(dp, buffer_clone(buffer), in_port, max_len, prev_port); + do_output(dp, buffer_clone(buffer), in_port, max_len, prev_port, + ignore_no_fwd); prev_port = -1; } @@ -960,7 +961,7 @@ execute_actions(struct datapath *dp, struct buffer *buffer, } } if (prev_port != -1) - do_output(dp, buffer, in_port, max_len, prev_port); + do_output(dp, buffer, in_port, max_len, prev_port, ignore_no_fwd); else buffer_delete(buffer); } @@ -1128,7 +1129,7 @@ recv_packet_out(struct datapath *dp, const struct sender *sender UNUSED, flow_extract(buffer, ntohs(opo->in_port), &key.flow); execute_actions(dp, buffer, ntohs(opo->in_port), - &key, opo->actions, n_actions); + &key, opo->actions, n_actions, true); return 0; } @@ -1199,7 +1200,8 @@ add_flow(struct datapath *dp, const struct ofp_flow_mod *ofm) uint16_t in_port = ntohs(ofm->match.in_port); flow_used(flow, buffer); flow_extract(buffer, in_port, &key.flow); - execute_actions(dp, buffer, in_port, &key, ofm->actions, n_actions); + execute_actions(dp, buffer, in_port, &key, + ofm->actions, n_actions, false); } else { error = -ESRCH; } diff --git a/tests/Makefile.am b/tests/Makefile.am index 2548ea0af..e3981bfd0 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -1,17 +1,37 @@ include ../Make.vars TESTS = test-list - -check_PROGRAMS = test-list - +noinst_PROGRAMS = test-list test_list_SOURCES = test-list.c test_list_LDADD = ../lib/libopenflow.a TESTS += test-type-props -check_PROGRAMS += test-type-props +noinst_PROGRAMS += test-type-props test_type_props_SOURCES = test-type-props.c -noinst_PROGRAMS = test-dhcp-client +noinst_PROGRAMS += test-dhcp-client test_dhcp_client_SOURCES = test-dhcp-client.c test_dhcp_client_LDADD = ../lib/libopenflow.a $(FAULT_LIBS) +TESTS += test-stp.sh +EXTRA_DIST = test-stp.sh +noinst_PROGRAMS += test-stp + +test_stp_SOURCES = test-stp.c +test_stp_LDADD = ../lib/libopenflow.a +stp_files = \ + test-stp-ieee802.1d-1998 \ + test-stp-ieee802.1d-2004-fig17.4 \ + test-stp-ieee802.1d-2004-fig17.6 \ + test-stp-ieee802.1d-2004-fig17.7 \ + test-stp-iol-op-1.1 \ + test-stp-iol-op-1.4 \ + test-stp-iol-op-3.1 \ + test-stp-iol-op-3.3 \ + test-stp-iol-io-1.1 \ + test-stp-iol-io-1.2 \ + test-stp-iol-io-1.4 \ + test-stp-iol-io-1.5 +TESTS_ENVIRONMENT = stp_files='$(stp_files)' + +EXTRA_DIST += $(stp_files) diff --git a/tests/test-stp-ieee802.1d-1998 b/tests/test-stp-ieee802.1d-1998 new file mode 100644 index 000000000..88aedb42f --- /dev/null +++ b/tests/test-stp-ieee802.1d-1998 @@ -0,0 +1,12 @@ +# This is the STP example from IEEE 802.1D-1998. +bridge 0 0x42 = a b +bridge 1 0x97 = c:5 a d:5 +bridge 2 0x45 = b e +bridge 3 0x57 = b:5 e:5 +bridge 4 0x83 = a:5 e:5 +run 256 +check 0 = root +check 1 = F F:10 F +check 2 = F:10 B +check 3 = F:5 F +check 4 = F:5 B diff --git a/tests/test-stp-ieee802.1d-2004-fig17.4 b/tests/test-stp-ieee802.1d-2004-fig17.4 new file mode 100644 index 000000000..29b13ff83 --- /dev/null +++ b/tests/test-stp-ieee802.1d-2004-fig17.4 @@ -0,0 +1,31 @@ +# This is the STP example from IEEE 802.1D-2004 figures 17.4 and 17.5. +bridge 0 0x111 = a b e c +bridge 1 0x222 = a b d f +bridge 2 0x333 = c d l j h g +bridge 3 0x444 = e f n m k i +bridge 4 0x555 = g i 0 0 +bridge 5 0x666 = h k 0 0 +bridge 6 0x777 = j m 0 0 +bridge 7 0x888 = l n 0 0 +run 256 +check 0 = root +check 1 = F:10 B F F +check 2 = F:10 B F F F F +check 3 = F:10 B F F F F +check 4 = F:20 B F F +check 5 = F:20 B F F +check 6 = F:20 B F F +check 7 = F:20 B F F + +# Now connect two ports of bridge 7 to the same LAN. +bridge 7 = l n o o +# Same results except for bridge 7: +run 256 +check 0 = root +check 1 = F:10 B F F +check 2 = F:10 B F F F F +check 3 = F:10 B F F F F +check 4 = F:20 B F F +check 5 = F:20 B F F +check 6 = F:20 B F F +check 7 = F:20 B F B diff --git a/tests/test-stp-ieee802.1d-2004-fig17.6 b/tests/test-stp-ieee802.1d-2004-fig17.6 new file mode 100644 index 000000000..694d2383f --- /dev/null +++ b/tests/test-stp-ieee802.1d-2004-fig17.6 @@ -0,0 +1,14 @@ +# This is the STP example from IEEE 802.1D-2004 figure 17.6. +bridge 0 0x111 = a b l +bridge 1 0x222 = b c d +bridge 2 0x333 = d e f +bridge 3 0x444 = f g h +bridge 4 0x555 = j h i +bridge 5 0x666 = l j k +run 256 +check 0 = root +check 1 = F:10 F F +check 2 = F:20 F F +check 3 = F:30 F B +check 4 = F:20 F F +check 5 = F:10 F F diff --git a/tests/test-stp-ieee802.1d-2004-fig17.7 b/tests/test-stp-ieee802.1d-2004-fig17.7 new file mode 100644 index 000000000..278655e28 --- /dev/null +++ b/tests/test-stp-ieee802.1d-2004-fig17.7 @@ -0,0 +1,17 @@ +# This is the STP example from IEEE 802.1D-2004 figure 17.7. +bridge 0 0xaa = b +bridge 1 0x111 = a b d f h g e c +bridge 2 0x222 = g h j l n m k i +run 256 +check 0 = root +check 1 = F F:10 F F F F F F +check 2 = B F:20 F F F F F F + +# This is not the port priority change described in that figure, +# but I don't understand what port priority change would cause +# that change. +bridge 2 = g X j l n m k i +run 256 +check 0 = root +check 1 = F F:10 F F F F F F +check 2 = F:20 D F F F F F F diff --git a/tests/test-stp-iol-io-1.1 b/tests/test-stp-iol-io-1.1 new file mode 100644 index 000000000..1b53fedba --- /dev/null +++ b/tests/test-stp-iol-io-1.1 @@ -0,0 +1,25 @@ +# This test file approximates the following test from "Bridge +# Functions Consortium Spanning Tree Interoperability Test Suite +# Version 1.5": +# STP.io.1.1: Link Failure +bridge 0 0x111 = a b c +bridge 1 0x222 = a b c +run 256 +check 0 = root +check 1 = F:10 B B +bridge 1 = 0 _ _ +run 256 +check 0 = root +check 1 = F F:10 B +bridge 1 = X _ _ +run 256 +check 0 = root +check 1 = D F:10 B +bridge 1 = _ 0 _ +run 256 +check 0 = root +check 1 = D F F:10 +bridge 1 = _ X _ +run 256 +check 0 = root +check 1 = D D F:10 diff --git a/tests/test-stp-iol-io-1.2 b/tests/test-stp-iol-io-1.2 new file mode 100644 index 000000000..a2ed48cb4 --- /dev/null +++ b/tests/test-stp-iol-io-1.2 @@ -0,0 +1,14 @@ +# This test file approximates the following test from "Bridge +# Functions Consortium Spanning Tree Interoperability Test Suite +# Version 1.5": +# STP.io.1.2: Repeated Network +bridge 0 0x111 = a a +bridge 1 0x222 = a a +run 256 +check 0 = rootid:0x111 F B +check 1 = rootid:0x111 F:10 B +bridge 1 = a^0x90 _ +run 256 +check 0 = rootid:0x111 F B +check 1 = rootid:0x111 B F:10 + diff --git a/tests/test-stp-iol-io-1.4 b/tests/test-stp-iol-io-1.4 new file mode 100644 index 000000000..f8b0b722a --- /dev/null +++ b/tests/test-stp-iol-io-1.4 @@ -0,0 +1,13 @@ +# This test file approximates the following test from "Bridge +# Functions Consortium Spanning Tree Interoperability Test Suite +# Version 1.5": +# STP.io.1.4: Network Initialization +bridge 0 0x111 = a b c +bridge 1 0x222 = b d e +bridge 2 0x333 = a d f +bridge 3 0x444 = c e f +run 256 +check 0 = root +check 1 = F:10 F F +check 2 = F:10 B F +check 3 = F:10 B B diff --git a/tests/test-stp-iol-io-1.5 b/tests/test-stp-iol-io-1.5 new file mode 100644 index 000000000..c5f08b8ed --- /dev/null +++ b/tests/test-stp-iol-io-1.5 @@ -0,0 +1,40 @@ +# This test file approximates the following test from "Bridge +# Functions Consortium Spanning Tree Interoperability Test Suite +# Version 1.5": +# STP.io.1.5: Topology Change +bridge 0 0x111 = a b d c +bridge 1 0x222 = a b f e +bridge 2 0x333 = c d g h +bridge 3 0x444 = e f g h +run 256 +check 0 = root +check 1 = F:10 B F F +check 2 = B F:10 F F +check 3 = B F:20 B B +bridge 1^0x7000 +run 256 +check 0 = F:10 B F F +check 1 = root +check 2 = B F:20 B B +check 3 = B F:10 F F +bridge 2^0x6000 +run 256 +check 0 = F F B F:10 +check 1 = F:20 B B B +check 2 = root +check 3 = F F F:10 B +bridge 3^0x5000 +run 256 +check 0 = B B B F:20 +check 1 = F F B F:10 +check 2 = F F F:10 B +check 3 = root +bridge 0^0x4000 +bridge 1^0x4001 +bridge 2^0x4002 +bridge 3^0x4003 +run 256 +check 0 = root +check 1 = F:10 B F F +check 2 = B F:10 F F +check 3 = B F:20 B B diff --git a/tests/test-stp-iol-op-1.1 b/tests/test-stp-iol-op-1.1 new file mode 100644 index 000000000..8432bf36e --- /dev/null +++ b/tests/test-stp-iol-op-1.1 @@ -0,0 +1,7 @@ +# This test file approximates the following tests from "Bridge +# Functions Consortium Spanning Tree Protocol Operations Test Suite +# Version 2.3": +# Test STP.op.1.1 ­ Root ID Initialized to Bridge ID +# Test STP.op.1.2 ­ Root Path Cost Initialized to Zero +bridge 0 0x123 = +check 0 = root diff --git a/tests/test-stp-iol-op-1.4 b/tests/test-stp-iol-op-1.4 new file mode 100644 index 000000000..18c09b897 --- /dev/null +++ b/tests/test-stp-iol-op-1.4 @@ -0,0 +1,8 @@ +# This test file approximates the following test from "Bridge +# Functions Consortium Spanning Tree Protocol Operations Test Suite +# Version 2.3": +# Test STP.op.1.4 ­ All Ports Initialized to Designated Ports +bridge 0 0x123 = a b c d e f +check 0 = Li Li Li Li Li Li +run 256 +check 0 = F F F F F F diff --git a/tests/test-stp-iol-op-3.1 b/tests/test-stp-iol-op-3.1 new file mode 100644 index 000000000..2e0a2f2cf --- /dev/null +++ b/tests/test-stp-iol-op-3.1 @@ -0,0 +1,11 @@ +# This test file approximates the following test from "Bridge +# Functions Consortium Spanning Tree Protocol Operations Test Suite +# Version 2.3": +# Test STP.op.3.1 ­ Root Bridge Selection: Root ID Values +bridge 0 0x111 = a +bridge 1 0x222 = a +check 0 = rootid:0x111 Li +check 1 = rootid:0x222 Li +run 256 +check 0 = rootid:0x111 root +check 1 = rootid:0x111 F:10 diff --git a/tests/test-stp-iol-op-3.3 b/tests/test-stp-iol-op-3.3 new file mode 100644 index 000000000..093c64edc --- /dev/null +++ b/tests/test-stp-iol-op-3.3 @@ -0,0 +1,11 @@ +# This test file approximates the following test from "Bridge +# Functions Consortium Spanning Tree Protocol Operations Test Suite +# Version 2.3": +# Test STP.op.3.3 ­ Root Bridge Selection: Bridge ID Values +bridge 0 0x333^0x6000 = a +bridge 1 0x222^0x7000 = b +bridge 2 0x111 = a b +run 256 +check 0 = rootid:0x333^0x6000 root +check 1 = rootid:0x333^0x6000 F:20 +check 2 = rootid:0x333^0x6000 F:10 F diff --git a/tests/test-stp-iol-op-3.4 b/tests/test-stp-iol-op-3.4 new file mode 100644 index 000000000..093c64edc --- /dev/null +++ b/tests/test-stp-iol-op-3.4 @@ -0,0 +1,11 @@ +# This test file approximates the following test from "Bridge +# Functions Consortium Spanning Tree Protocol Operations Test Suite +# Version 2.3": +# Test STP.op.3.3 ­ Root Bridge Selection: Bridge ID Values +bridge 0 0x333^0x6000 = a +bridge 1 0x222^0x7000 = b +bridge 2 0x111 = a b +run 256 +check 0 = rootid:0x333^0x6000 root +check 1 = rootid:0x333^0x6000 F:20 +check 2 = rootid:0x333^0x6000 F:10 F diff --git a/tests/test-stp.c b/tests/test-stp.c new file mode 100644 index 000000000..237e7d567 --- /dev/null +++ b/tests/test-stp.c @@ -0,0 +1,661 @@ +/* Copyright (c) 2008 The Board of Trustees of The Leland Stanford + * Junior University + * + * We are making the OpenFlow specification and associated documentation + * (Software) available for public use and benefit with the expectation + * that others will use, modify and enhance the Software and contribute + * those enhancements back to the community. However, since we would + * like to make the Software available for broadest use, with as few + * restrictions as possible permission is hereby granted, free of + * charge, to any person obtaining a copy of this Software to deal in + * the Software under the copyrights without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * The name and trademarks of copyright holder(s) may NOT be used in + * advertising or publicity pertaining to the Software or any + * derivatives without specific, written prior permission. + */ + +#include "stp.h" +#include +#include +#include +#include +#include +#include +#include "packets.h" + +struct bpdu { + int port_no; + void *data; + size_t size; +}; + +struct bridge { + struct test_case *tc; + int id; + bool reached; + + struct stp *stp; + + struct lan *ports[STP_MAX_PORTS]; + int n_ports; + +#define RXQ_SIZE 16 + struct bpdu rxq[RXQ_SIZE]; + int rxq_head, rxq_tail; +}; + +struct lan_conn { + struct bridge *bridge; + int port_no; +}; + +struct lan { + struct test_case *tc; + const char *name; + bool reached; + struct lan_conn conns[16]; + int n_conns; +}; + +struct test_case { + struct bridge *bridges[16]; + int n_bridges; + struct lan *lans[26]; + int n_lans; +}; + +static const char *file_name; +static int line_number; +static char line[128]; +static char *pos, *token; +static int n_warnings; + +static struct test_case * +new_test_case(void) +{ + struct test_case *tc = xmalloc(sizeof *tc); + tc->n_bridges = 0; + tc->n_lans = 0; + return tc; +} + +static void +send_bpdu(const void *data, size_t size, int port_no, void *b_) +{ + struct bridge *b = b_; + struct lan *lan; + int i; + + assert(port_no < b->n_ports); + lan = b->ports[port_no]; + if (!lan) { + return; + } + for (i = 0; i < lan->n_conns; i++) { + struct lan_conn *conn = &lan->conns[i]; + if (conn->bridge != b || conn->port_no != port_no) { + struct bridge *dst = conn->bridge; + struct bpdu *bpdu = &dst->rxq[dst->rxq_head++ % RXQ_SIZE]; + assert(dst->rxq_head - dst->rxq_tail <= RXQ_SIZE); + bpdu->data = xmemdup(data, size); + bpdu->size = size; + bpdu->port_no = conn->port_no; + } + } +} + +static struct bridge * +new_bridge(struct test_case *tc, int id) +{ + struct bridge *b = xmalloc(sizeof *b); + char name[16]; + b->tc = tc; + b->id = id; + snprintf(name, sizeof name, "stp%x", id); + b->stp = stp_create(name, id, send_bpdu, b); + assert(tc->n_bridges < ARRAY_SIZE(tc->bridges)); + b->n_ports = 0; + b->rxq_head = b->rxq_tail = 0; + tc->bridges[tc->n_bridges++] = b; + return b; +} + +static struct lan * +new_lan(struct test_case *tc, const char *name) +{ + struct lan *lan = xmalloc(sizeof *lan); + lan->tc = tc; + lan->name = xstrdup(name); + lan->n_conns = 0; + assert(tc->n_lans < ARRAY_SIZE(tc->lans)); + tc->lans[tc->n_lans++] = lan; + return lan; +} + +static void +reconnect_port(struct bridge *b, int port_no, struct lan *new_lan) +{ + struct lan *old_lan; + int j; + + assert(port_no < b->n_ports); + old_lan = b->ports[port_no]; + if (old_lan == new_lan) { + return; + } + + /* Disconnect from old_lan. */ + if (old_lan) { + for (j = 0; j < old_lan->n_conns; j++) { + struct lan_conn *c = &old_lan->conns[j]; + if (c->bridge == b && c->port_no == port_no) { + memmove(c, c + 1, sizeof *c * (old_lan->n_conns - j - 1)); + old_lan->n_conns--; + break; + } + } + } + + /* Connect to new_lan. */ + b->ports[port_no] = new_lan; + if (new_lan) { + int conn_no = new_lan->n_conns++; + assert(conn_no < ARRAY_SIZE(new_lan->conns)); + new_lan->conns[conn_no].bridge = b; + new_lan->conns[conn_no].port_no = port_no; + } +} + +static void +new_port(struct bridge *b, struct lan *lan, int path_cost) +{ + int port_no = b->n_ports++; + struct stp_port *p = stp_get_port(b->stp, port_no); + assert(port_no < ARRAY_SIZE(b->ports)); + b->ports[port_no] = NULL; + stp_port_set_path_cost(p, path_cost); + stp_port_enable(p); + reconnect_port(b, port_no, lan); +} + +static void +dump(struct test_case *tc) +{ + int i; + + for (i = 0; i < tc->n_bridges; i++) { + struct bridge *b = tc->bridges[i]; + struct stp *stp = b->stp; + int j; + + printf("%s:", stp_get_name(stp)); + if (stp_is_root_bridge(stp)) { + printf(" root"); + } + printf("\n"); + for (j = 0; j < b->n_ports; j++) { + struct stp_port *p = stp_get_port(stp, j); + enum stp_state state = stp_port_get_state(p); + + printf("\tport %d", j); + if (b->ports[j]) { + printf(" (lan %s)", b->ports[j]->name); + } else { + printf(" (disconnected)"); + } + printf(": %s", stp_state_name(state)); + if (p == stp_get_root_port(stp)) { + printf(" (root port, root_path_cost=%u)", stp_get_root_path_cost(stp)); + } + printf("\n"); + } + } +} + +static void dump_lan_tree(struct test_case *, struct lan *, int level); + +static void +dump_bridge_tree(struct test_case *tc, struct bridge *b, int level) +{ + int i; + + if (b->reached) { + return; + } + b->reached = true; + for (i = 0; i < level; i++) { + printf("\t"); + } + printf("%s\n", stp_get_name(b->stp)); + for (i = 0; i < b->n_ports; i++) { + struct lan *lan = b->ports[i]; + struct stp_port *p = stp_get_port(b->stp, i); + if (stp_port_get_state(p) == STP_FORWARDING && lan) { + dump_lan_tree(tc, lan, level + 1); + } + } +} + +static void +dump_lan_tree(struct test_case *tc, struct lan *lan, int level) +{ + int i; + + if (lan->reached) { + return; + } + lan->reached = true; + for (i = 0; i < level; i++) { + printf("\t"); + } + printf("%s\n", lan->name); + for (i = 0; i < lan->n_conns; i++) { + struct bridge *b = lan->conns[i].bridge; + dump_bridge_tree(tc, b, level + 1); + } +} + +static void +tree(struct test_case *tc) +{ + int i; + + for (i = 0; i < tc->n_bridges; i++) { + struct bridge *b = tc->bridges[i]; + b->reached = false; + } + for (i = 0; i < tc->n_lans; i++) { + struct lan *lan = tc->lans[i]; + lan->reached = false; + } + for (i = 0; i < tc->n_bridges; i++) { + struct bridge *b = tc->bridges[i]; + struct stp *stp = b->stp; + if (stp_is_root_bridge(stp)) { + dump_bridge_tree(tc, b, 0); + } + } +} + +static void +simulate(struct test_case *tc, int granularity) +{ + int time; + + for (time = 0; time < 256 * 180; time += granularity) { + int round_trips; + int i; + + for (i = 0; i < tc->n_bridges; i++) { + stp_tick(tc->bridges[i]->stp, granularity); + } + for (round_trips = 0; round_trips < granularity; round_trips++) { + bool any = false; + for (i = 0; i < tc->n_bridges; i++) { + struct bridge *b = tc->bridges[i]; + for (; b->rxq_tail != b->rxq_head; b->rxq_tail++) { + struct bpdu *bpdu = &b->rxq[b->rxq_tail % RXQ_SIZE]; + stp_received_bpdu(stp_get_port(b->stp, bpdu->port_no), + bpdu->data, bpdu->size); + any = true; + } + } + if (!any) { + break; + } + } + } +} + +static void +err(const char *message, ...) + PRINTF_FORMAT(1, 2) + NO_RETURN; + +static void +err(const char *message, ...) +{ + va_list args; + + fprintf(stderr, "%s:%d:%td: ", file_name, line_number, pos - line); + va_start(args, message); + vfprintf(stderr, message, args); + va_end(args); + putc('\n', stderr); + + exit(EXIT_FAILURE); +} + +static void +warn(const char *message, ...) + PRINTF_FORMAT(1, 2); + +static void +warn(const char *message, ...) +{ + va_list args; + + fprintf(stderr, "%s:%d: ", file_name, line_number); + va_start(args, message); + vfprintf(stderr, message, args); + va_end(args); + putc('\n', stderr); + + n_warnings++; +} + +static bool +get_token(void) +{ + char *start; + + while (isspace((unsigned char) *pos)) { + pos++; + } + if (*pos == '\0') { + token = NULL; + return false; + } + + start = pos; + if (isalpha((unsigned char) *pos)) { + while (isalpha((unsigned char) *++pos)) { + continue; + } + } else if (isdigit((unsigned char) *pos)) { + if (*pos == '0' && (pos[1] == 'x' || pos[1] == 'X')) { + pos += 2; + while (isxdigit((unsigned char) *pos)) { + pos++; + } + } else { + while (isdigit((unsigned char) *++pos)) { + continue; + } + } + } else { + pos++; + } + + free(token); + token = xmemdup0(start, pos - start); + return true; +} + +static bool +get_int(int *intp) +{ + char *save_pos = pos; + if (token && isdigit((unsigned char) *token)) { + *intp = strtol(token, NULL, 0); + get_token(); + return true; + } else { + pos = save_pos; + return false; + } +} + +static bool +match(const char *want) +{ + if (token && !strcmp(want, token)) { + get_token(); + return true; + } else { + return false; + } +} + +static int +must_get_int(void) +{ + int x; + if (!get_int(&x)) { + err("expected integer"); + } + return x; +} + +static void +must_match(const char *want) +{ + if (!match(want)) { + err("expected \"%s\"", want); + } +} + +int +main(int argc, char *argv[]) +{ + struct test_case *tc; + FILE *input_file; + int i; + + if (argc != 2) { + fatal(0, "usage: test-stp INPUT.STP\n"); + } + file_name = argv[1]; + + input_file = fopen(file_name, "r"); + if (!input_file) { + fatal(errno, "error opening \"%s\"", file_name); + } + + tc = new_test_case(); + for (i = 0; i < 26; i++) { + char name[2]; + name[0] = 'a' + i; + name[1] = '\0'; + new_lan(tc, name); + } + + for (line_number = 1; fgets(line, sizeof line, input_file); + line_number++) + { + char *newline, *hash; + + newline = strchr(line, '\n'); + if (newline) { + *newline = '\0'; + } + hash = strchr(line, '#'); + if (hash) { + *hash = '\0'; + } + + pos = line; + if (!get_token()) { + continue; + } + if (match("bridge")) { + struct bridge *bridge; + int bridge_no, port_no; + + bridge_no = must_get_int(); + if (bridge_no < tc->n_bridges) { + bridge = tc->bridges[bridge_no]; + } else if (bridge_no == tc->n_bridges) { + bridge = new_bridge(tc, must_get_int()); + } else { + err("bridges must be numbered consecutively from 0"); + } + if (match("^")) { + stp_set_bridge_priority(bridge->stp, must_get_int()); + } + + if (match("=")) { + for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) { + struct stp_port *p = stp_get_port(bridge->stp, port_no); + if (!token || match("X")) { + stp_port_disable(p); + } else if (match("_")) { + /* Nothing to do. */ + } else { + struct lan *lan; + int path_cost; + + if (!strcmp(token, "0")) { + lan = NULL; + } else if (strlen(token) == 1 && islower(*token)) { + lan = tc->lans[*token - 'a']; + } else { + err("%s is not a valid LAN name " + "(0 or a lowercase letter)", token); + } + get_token(); + + path_cost = match(":") ? must_get_int() : 10; + if (port_no < bridge->n_ports) { + stp_port_set_path_cost(p, path_cost); + stp_port_enable(p); + reconnect_port(bridge, port_no, lan); + } else if (port_no == bridge->n_ports) { + new_port(bridge, lan, path_cost); + } else { + err("ports must be numbered consecutively"); + } + if (match("^")) { + stp_port_set_priority(p, must_get_int()); + } + } + } + } + } else if (match("run")) { + simulate(tc, must_get_int()); + } else if (match("dump")) { + dump(tc); + } else if (match("tree")) { + tree(tc); + } else if (match("check")) { + struct bridge *b; + struct stp *stp; + int bridge_no, port_no; + + bridge_no = must_get_int(); + if (bridge_no >= tc->n_bridges) { + err("no bridge numbered %d", bridge_no); + } + b = tc->bridges[bridge_no]; + stp = b->stp; + + must_match("="); + + if (match("rootid")) { + uint64_t rootid; + must_match(":"); + rootid = must_get_int(); + if (match("^")) { + rootid |= (uint64_t) must_get_int() << 48; + } else { + rootid |= UINT64_C(0x8000) << 48; + } + if (stp_get_designated_root(stp) != rootid) { + warn("%s: root %"PRIx64", not %"PRIx64, + stp_get_name(stp), stp_get_designated_root(stp), + rootid); + } + } + + if (match("root")) { + if (stp_get_root_path_cost(stp)) { + warn("%s: root path cost of root is %u but should be 0", + stp_get_name(stp), stp_get_root_path_cost(stp)); + } + if (!stp_is_root_bridge(stp)) { + warn("%s: root is %"PRIx64", not %"PRIx64, + stp_get_name(stp), + stp_get_designated_root(stp), stp_get_bridge_id(stp)); + } + for (port_no = 0; port_no < b->n_ports; port_no++) { + struct stp_port *p = stp_get_port(stp, port_no); + enum stp_state state = stp_port_get_state(p); + if (!(state & (STP_DISABLED | STP_FORWARDING))) { + warn("%s: root port %d in state %s", + stp_get_name(b->stp), port_no, + stp_state_name(state)); + } + } + } else { + for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) { + struct stp_port *p = stp_get_port(stp, port_no); + enum stp_state state; + if (token == NULL || match("D")) { + state = STP_DISABLED; + } else if (match("B")) { + state = STP_BLOCKING; + } else if (match("Li")) { + state = STP_LISTENING; + } else if (match("Le")) { + state = STP_LEARNING; + } else if (match("F")) { + state = STP_FORWARDING; + } else if (match("_")) { + continue; + } else { + err("unknown port state %s", token); + } + if (stp_port_get_state(p) != state) { + warn("%s port %d: state is %s but should be %s", + stp_get_name(stp), port_no, + stp_state_name(stp_port_get_state(p)), + stp_state_name(state)); + } + if (state == STP_FORWARDING) { + struct stp_port *root_port = stp_get_root_port(stp); + if (match(":")) { + int root_path_cost = must_get_int(); + if (p != root_port) { + warn("%s: port %d is not the root port", + stp_get_name(stp), port_no); + if (!root_port) { + warn("%s: (there is no root port)", + stp_get_name(stp)); + } else { + warn("%s: (port %d is the root port)", + stp_get_name(stp), + stp_port_no(root_port)); + } + } else if (root_path_cost + != stp_get_root_path_cost(stp)) { + warn("%s: root path cost is %u, should be %d", + stp_get_name(stp), + stp_get_root_path_cost(stp), + root_path_cost); + } + } else if (p == root_port) { + warn("%s: port %d is the root port but " + "not expected to be", + stp_get_name(stp), port_no); + } + } + } + } + if (n_warnings) { + exit(EXIT_FAILURE); + } + } + if (get_token()) { + err("trailing garbage on line"); + } + } + + return 0; +} diff --git a/tests/test-stp.sh b/tests/test-stp.sh new file mode 100755 index 000000000..8d0f53888 --- /dev/null +++ b/tests/test-stp.sh @@ -0,0 +1,7 @@ +#! /bin/sh +set -e +progress= +for d in ${stp_files}; do + echo "Testing $d..." + $SUPERVISOR ./test-stp ${srcdir}/$d +done -- 2.43.0