From 711c48de9dc8047b6780299584526d17d4b8b906 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 21 May 2008 10:06:58 -0700 Subject: [PATCH] Break MAC learning out of controller into library. This is preparation for use of MAC learning in the secure channel. --- controller/controller.c | 220 +++++++--------------------------------- include/Makefile.am | 1 + include/mac-learning.h | 46 +++++++++ include/vlog.h | 1 + lib/Makefile.am | 1 + lib/mac-learning.c | 175 ++++++++++++++++++++++++++++++++ 6 files changed, 258 insertions(+), 186 deletions(-) create mode 100644 include/mac-learning.h create mode 100644 lib/mac-learning.c diff --git a/controller/controller.c b/controller/controller.c index 8b69686b..387f8c74 100644 --- a/controller/controller.c +++ b/controller/controller.c @@ -49,6 +49,7 @@ #include "hash.h" #include "list.h" #include "ofp-print.h" +#include "mac-learning.h" #include "openflow.h" #include "packets.h" #include "poll-loop.h" @@ -74,13 +75,14 @@ struct switch_ { time_t last_features_request; struct queue txq; + struct mac_learning *ml; }; -/* -H, --hub: Use dumb hub instead of learning switch? */ -static bool hub = false; +/* Learn the ports on which MAC addresses appear? */ +static bool learn_macs = true; -/* -n, --noflow: Pass traffic, but don't setup flows in switch */ -static bool noflow = false; +/* Set up flows? (If not, every packet is processed at the controller.) */ +static bool setup_flows = true; static void parse_options(int argc, char *argv[]); static void usage(void) NO_RETURN; @@ -97,11 +99,7 @@ static int do_switch_recv(struct switch_ *this); static int do_switch_send(struct switch_ *this); static void process_packet(struct switch_ *, struct buffer *); -static void process_hub(struct switch_ *, struct ofp_packet_in *); -static void process_noflow(struct switch_ *, struct ofp_packet_in *); - -static void switch_init(void); -static void process_switch(struct switch_ *, struct ofp_packet_in *); +static void process_packet_in(struct switch_ *, struct ofp_packet_in *); int main(int argc, char *argv[]) @@ -116,10 +114,6 @@ main(int argc, char *argv[]) vlog_init(); parse_options(argc, argv); - if (!hub && !noflow) { - switch_init(); - } - if (argc - optind < 1) { fatal(0, "at least one vconn argument required; use --help for usage"); } @@ -265,6 +259,9 @@ new_switch(const char *name, struct vconn *vconn) if (!vconn_is_passive(vconn)) { send_features_request(this); } + if (learn_macs) { + this->ml = mac_learning_create(); + } return this; } @@ -275,6 +272,7 @@ close_switch(struct switch_ *this) free(this->name); vconn_close(this->vconn); queue_destroy(&this->txq); + mac_learning_destroy(this->ml); free(this); } } @@ -345,12 +343,8 @@ process_packet(struct switch_ *sw, struct buffer *msg) if (sw->txq.n >= MAX_TXQ) { /* FIXME: ratelimit. */ VLOG_WARN("%s: tx queue overflow", sw->name); - } else if (noflow) { - process_noflow(sw, opi); - } else if (hub) { - process_hub(sw, opi); } else { - process_switch(sw, opi); + process_packet_in(sw, opi); } } else { ofp_print(stdout, msg->data, msg->size, 2); @@ -358,196 +352,50 @@ process_packet(struct switch_ *sw, struct buffer *msg) } static void -process_hub(struct switch_ *sw, struct ofp_packet_in *opi) -{ - size_t pkt_ofs, pkt_len; - struct buffer pkt; - struct flow flow; - - /* Extract flow data from 'opi' into 'flow'. */ - 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, ntohs(opi->in_port), &flow); - - /* Add new flow. */ - queue_tx(sw, make_add_simple_flow(&flow, ntohl(opi->buffer_id), - OFPP_FLOOD)); - - /* If the switch didn't buffer the packet, we need to send a copy. */ - if (ntohl(opi->buffer_id) == UINT32_MAX) { - queue_tx(sw, make_unbuffered_packet_out(&pkt, ntohs(flow.in_port), - OFPP_FLOOD)); - } -} - -static void -process_noflow(struct switch_ *sw, struct ofp_packet_in *opi) +process_packet_in(struct switch_ *sw, struct ofp_packet_in *opi) { - /* If the switch didn't buffer the packet, we need to send a copy. */ - if (ntohl(opi->buffer_id) == UINT32_MAX) { - size_t pkt_ofs, pkt_len; - struct buffer pkt; - - /* Extract flow data from 'opi' into 'flow'. */ - pkt_ofs = offsetof(struct ofp_packet_in, data); - pkt_len = ntohs(opi->header.length) - pkt_ofs; - pkt.data = opi->data; - pkt.size = pkt_len; - - queue_tx(sw, make_unbuffered_packet_out(&pkt, ntohs(opi->in_port), - OFPP_FLOOD)); - } else { - queue_tx(sw, make_buffered_packet_out(ntohl(opi->buffer_id), - ntohs(opi->in_port), OFPP_FLOOD)); - } -} - - -#define MAC_HASH_BITS 10 -#define MAC_HASH_MASK (MAC_HASH_SIZE - 1) -#define MAC_HASH_SIZE (1u << MAC_HASH_BITS) - -#define MAC_MAX 1024 - -struct mac_source { - struct list hash_list; - struct list lru_list; - uint64_t datapath_id; - uint8_t mac[ETH_ADDR_LEN]; - uint16_t port; -}; - -static struct list mac_table[MAC_HASH_SIZE]; -static struct list lrus; -static size_t mac_count; + uint16_t in_port = ntohs(opi->in_port); + uint16_t out_port = OFPP_FLOOD; -static void -switch_init(void) -{ - int i; - - list_init(&lrus); - for (i = 0; i < MAC_HASH_SIZE; i++) { - list_init(&mac_table[i]); - } -} - -static struct list * -mac_table_bucket(uint64_t datapath_id, const uint8_t mac[ETH_ADDR_LEN]) -{ - uint32_t hash; - hash = hash_fnv(&datapath_id, sizeof datapath_id, HASH_FNV_BASIS); - hash = hash_fnv(mac, ETH_ADDR_LEN, hash); - return &mac_table[hash & MAC_HASH_BITS]; -} - -static void -process_switch(struct switch_ *sw, struct ofp_packet_in *opi) -{ size_t pkt_ofs, pkt_len; struct buffer pkt; struct flow flow; - uint16_t out_port; - /* Extract flow data from 'opi' into 'flow'. */ 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, ntohs(opi->in_port), &flow); - - /* Learn the source. */ - if (!eth_addr_is_multicast(flow.dl_src)) { - struct mac_source *src; - struct list *bucket; - bool found; - - bucket = mac_table_bucket(sw->datapath_id, flow.dl_src); - found = false; - LIST_FOR_EACH (src, struct mac_source, hash_list, bucket) { - if (src->datapath_id == sw->datapath_id - && eth_addr_equals(src->mac, flow.dl_src)) { - found = true; - break; - } - } - - if (!found) { - /* Learn a new address. */ - - if (mac_count >= MAC_MAX) { - /* Drop the least recently used mac source. */ - struct mac_source *lru; - lru = CONTAINER_OF(lrus.next, struct mac_source, lru_list); - list_remove(&lru->hash_list); - list_remove(&lru->lru_list); - free(lru); - } else { - mac_count++; - } - - /* Create new mac source */ - src = xmalloc(sizeof *src); - src->datapath_id = sw->datapath_id; - memcpy(src->mac, flow.dl_src, ETH_ADDR_LEN); - src->port = -1; - list_push_front(bucket, &src->hash_list); - list_push_back(&lrus, &src->lru_list); - } else { - /* Make 'src' most-recently-used. */ - list_remove(&src->lru_list); - list_push_back(&lrus, &src->lru_list); - } + flow_extract(&pkt, in_port, &flow); - if (ntohs(flow.in_port) != src->port) { - src->port = ntohs(flow.in_port); + if (learn_macs) { + if (mac_learning_learn(sw->ml, flow.dl_src, in_port)) { VLOG_DBG("learned that "ETH_ADDR_FMT" is on datapath %" - PRIx64" port %d", - ETH_ADDR_ARGS(src->mac), ntohll(src->datapath_id), - src->port); - } - } else { - VLOG_DBG("multicast packet source "ETH_ADDR_FMT, - ETH_ADDR_ARGS(flow.dl_src)); - } - - /* Figure out the destination. */ - out_port = OFPP_FLOOD; - if (!eth_addr_is_multicast(flow.dl_dst)) { - struct mac_source *dst; - struct list *bucket; - - bucket = mac_table_bucket(sw->datapath_id, flow.dl_dst); - LIST_FOR_EACH (dst, struct mac_source, hash_list, bucket) { - if (dst->datapath_id == sw->datapath_id - && eth_addr_equals(dst->mac, flow.dl_dst)) { - out_port = dst->port; - break; - } + PRIx64" port %"PRIu16, ETH_ADDR_ARGS(flow.dl_src), + ntohll(sw->datapath_id), in_port); } + out_port = mac_learning_lookup(sw->ml, flow.dl_dst); } - if (out_port != OFPP_FLOOD) { - /* The output port is known, so add a new flow. */ - queue_tx(sw, make_add_simple_flow(&flow, ntohl(opi->buffer_id), - out_port)); + if (setup_flows && (!learn_macs || out_port != OFPP_FLOOD)) { + /* The output port is known, or we always flood everything, so add a + * new flow. */ + queue_tx(sw, make_add_simple_flow(&flow, ntohl(opi->buffer_id), + out_port)); /* If the switch didn't buffer the packet, we need to send a copy. */ if (ntohl(opi->buffer_id) == UINT32_MAX) { - queue_tx(sw, make_unbuffered_packet_out(&pkt, ntohs(flow.in_port), - out_port)); + queue_tx(sw, make_unbuffered_packet_out(&pkt, in_port, out_port)); } } else { - /* We don't know that MAC. Flood the packet. */ + /* We don't know that MAC, or we don't set up flows. 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, ntohs(flow.in_port), out_port); + b = make_unbuffered_packet_out(&pkt, in_port, out_port); } else { - b = make_buffered_packet_out(ntohl(opi->buffer_id), - ntohs(flow.in_port), out_port); + b = make_buffered_packet_out(ntohl(opi->buffer_id), + in_port, out_port); } queue_tx(sw, b); } @@ -578,11 +426,11 @@ parse_options(int argc, char *argv[]) switch (c) { case 'H': - hub = true; + learn_macs = false; break; case 'n': - noflow = true; + setup_flows = false; break; case 'h': diff --git a/include/Makefile.am b/include/Makefile.am index b6900973..848acc08 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -9,6 +9,7 @@ noinst_HEADERS = \ flow.h \ hash.h \ list.h \ + mac-learning.h \ netdev.h \ netlink-protocol.h \ netlink.h \ diff --git a/include/mac-learning.h b/include/mac-learning.h new file mode 100644 index 00000000..3c1b3dc3 --- /dev/null +++ b/include/mac-learning.h @@ -0,0 +1,46 @@ +/* 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 MAC_LEARNING_H +#define MAC_LEARNING_H 1 + +#include "packets.h" + +struct mac_learning *mac_learning_create(void); +void mac_learning_destroy(struct mac_learning *); +bool mac_learning_learn(struct mac_learning *, + const uint8_t src[ETH_ADDR_LEN], uint16_t src_port); +uint16_t mac_learning_lookup(const struct mac_learning *, + const uint8_t dst[ETH_ADDR_LEN]); + +#endif /* mac-learning.h */ diff --git a/include/vlog.h b/include/vlog.h index 01b2a851..58d3d5ab 100644 --- a/include/vlog.h +++ b/include/vlog.h @@ -69,6 +69,7 @@ enum vlog_facility vlog_get_facility_val(const char *name); VLOG_MODULE(dpctl) \ VLOG_MODULE(fault) \ VLOG_MODULE(flow) \ + VLOG_MODULE(mac_learning) \ VLOG_MODULE(netdev) \ VLOG_MODULE(netlink) \ VLOG_MODULE(poll_loop) \ diff --git a/lib/Makefile.am b/lib/Makefile.am index 8448333e..3f594390 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -11,6 +11,7 @@ libopenflow_la_SOURCES = \ flow.c \ hash.c \ list.c \ + mac-learning.c \ netdev.c \ ofp-print.c \ poll-loop.c \ diff --git a/lib/mac-learning.c b/lib/mac-learning.c new file mode 100644 index 00000000..5311ccf6 --- /dev/null +++ b/lib/mac-learning.c @@ -0,0 +1,175 @@ +/* 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 "mac-learning.h" + +#include +#include +#include + +#include "hash.h" +#include "list.h" +#include "openflow.h" +#include "util.h" + +#define THIS_MODULE VLM_mac_learning +#include "vlog.h" + +#define MAC_HASH_BITS 10 +#define MAC_HASH_MASK (MAC_HASH_SIZE - 1) +#define MAC_HASH_SIZE (1u << MAC_HASH_BITS) + +#define MAC_MAX 1024 + +/* A MAC learning table entry. */ +struct mac_entry { + struct list hash_node; /* Element in a mac_learning 'table' list. */ + struct list lru_node; /* Element in mac_learning 'lrus' list. */ + uint8_t mac[ETH_ADDR_LEN]; /* Known MAC address. */ + uint16_t port; /* Port on which MAC was most recently seen. */ +}; + +/* MAC learning table. */ +struct mac_learning { + struct list lrus; /* All entries, least recently used at the + front, most recently used at the back. */ + struct list table[MAC_HASH_SIZE]; /* Hash table. */ + struct mac_entry entries[MAC_MAX]; /* All entries. */ +}; + +static struct list * +mac_table_bucket(const struct mac_learning *ml, + const uint8_t mac[ETH_ADDR_LEN]) +{ + uint32_t hash = hash_fnv(mac, ETH_ADDR_LEN, HASH_FNV_BASIS); + const struct list *list = &ml->table[hash & MAC_HASH_BITS]; + return (struct list *) list; +} + +static struct mac_entry * +search_bucket(struct list *bucket, const uint8_t mac[ETH_ADDR_LEN]) +{ + struct mac_entry *e; + LIST_FOR_EACH (e, struct mac_entry, hash_node, bucket) { + if (eth_addr_equals(e->mac, mac)) { + return e; + } + } + return NULL; +} + +/* Creates and returns a new MAC learning table. */ +struct mac_learning * +mac_learning_create(void) +{ + struct mac_learning *ml; + int i; + + ml = xmalloc(sizeof *ml); + list_init(&ml->lrus); + for (i = 0; i < MAC_HASH_SIZE; i++) { + list_init(&ml->table[i]); + } + for (i = 0; i < MAC_MAX; i++) { + struct mac_entry *s = &ml->entries[i]; + list_push_front(&ml->lrus, &s->lru_node); + s->hash_node.next = NULL; + } + return ml; +} + +/* Destroys MAC learning table 'ml'. */ +void +mac_learning_destroy(struct mac_learning *ml) +{ + free(ml); +} + +/* Attempts to make 'ml' learn from the fact that a frame from 'src_mac' was + * just observed arriving on 'src_port'. Returns true if we actually learned + * something from this, false if it just confirms what we already knew. */ +bool +mac_learning_learn(struct mac_learning *ml, + const uint8_t src_mac[ETH_ADDR_LEN], uint16_t src_port) +{ + struct mac_entry *e; + struct list *bucket; + + assert(src_port != OFPP_FLOOD); + if (eth_addr_is_multicast(src_mac)) { + VLOG_DBG("multicast packet source "ETH_ADDR_FMT, + ETH_ADDR_ARGS(src_mac)); + return false; + } + + bucket = mac_table_bucket(ml, src_mac); + e = search_bucket(bucket, src_mac); + if (e) { + /* Make 'e' most-recently-used. */ + list_remove(&e->lru_node); + list_push_back(&ml->lrus, &e->lru_node); + if (e->port == src_port) { + return false; + } + } else { + /* Learn a new address. + * First drop the least recently used mac source. */ + e = CONTAINER_OF(ml->lrus.next, struct mac_entry, lru_node); + if (e->hash_node.next) { + list_remove(&e->hash_node); + } + list_remove(&e->lru_node); + + /* Create new mac source. */ + memcpy(e->mac, src_mac, ETH_ADDR_LEN); + list_push_front(bucket, &e->hash_node); + list_push_back(&ml->lrus, &e->lru_node); + } + e->port = src_port; + return true; +} + +/* Looks up address 'dst' in 'ml'. Returns the port on which a frame destined + * for 'dst' should be sent, OFPP_FLOOD if unknown. */ +uint16_t +mac_learning_lookup(const struct mac_learning *ml, + const uint8_t dst[ETH_ADDR_LEN]) +{ + if (!eth_addr_is_multicast(dst)) { + struct mac_entry *e = search_bucket(mac_table_bucket(ml, dst), dst); + if (e) { + return e->port; + } + } + return OFPP_FLOOD; +} -- 2.30.2