Implement basic multiple table support.

This implements basic multiple table support in ofproto and supporting
libraries and utilities. The design is the same as the one that has been
on the Open vSwitch "wdp" branch for a long time.  There is no support for
multiple tables in the software switch implementation (ofproto-dpif), only
a set of hooks for other switch implementations to use.

To allow controllers to add flows in a particular table, Open vSwitch adds
an OpenFlow 1.0 extension called NXT_FLOW_MOD_TABLE_ID.

5 files changed, 361 insertions, 98 deletions

diff --git a/ofproto/connmgr.c b/ofproto/connmgr.c
index a6f23dc1..d49c0698 100644
--- a/ofproto/connmgr.c
+++ b/ofproto/connmgr.c
@@ -49,6 +49,7 @@ struct ofconn {
     struct rconn *rconn;        /* OpenFlow connection. */
     enum ofconn_type type;      /* Type. */
     enum nx_flow_format flow_format; /* Currently selected flow format. */
+    bool flow_mod_table_id;     /* NXT_FLOW_MOD_TABLE_ID enabled? */
 
     /* OFPT_PACKET_IN related data. */
     struct rconn_packet_counter *packet_in_counter; /* # queued on 'rconn'. */
@@ -724,6 +725,24 @@ ofconn_set_flow_format(struct ofconn *ofconn, enum nx_flow_format flow_format)
     ofconn->flow_format = flow_format;
 }
 
+/* Returns true if the NXT_FLOW_MOD_TABLE_ID extension is enabled, false
+ * otherwise.
+ *
+ * By default the extension is not enabled. */
+bool
+ofconn_get_flow_mod_table_id(const struct ofconn *ofconn)
+{
+    return ofconn->flow_mod_table_id;
+}
+
+/* Enables or disables (according to 'enable') the NXT_FLOW_MOD_TABLE_ID
+ * extension on 'ofconn'. */
+void
+ofconn_set_flow_mod_table_id(struct ofconn *ofconn, bool enable)
+{
+    ofconn->flow_mod_table_id = enable;
+}
+
 /* Returns the default miss send length for 'ofconn'. */
 int
 ofconn_get_miss_send_len(const struct ofconn *ofconn)
@@ -773,6 +792,7 @@ ofconn_create(struct connmgr *mgr, struct rconn *rconn, enum ofconn_type type)
     ofconn->rconn = rconn;
     ofconn->type = type;
     ofconn->flow_format = NXFF_OPENFLOW10;
+    ofconn->flow_mod_table_id = false;
     ofconn->role = NX_ROLE_OTHER;
     ofconn->packet_in_counter = rconn_packet_counter_create ();
     ofconn->pktbuf = NULL;
diff --git a/ofproto/connmgr.h b/ofproto/connmgr.h
index 441ecc3d..46d2f5d8 100644
--- a/ofproto/connmgr.h
+++ b/ofproto/connmgr.h
@@ -80,6 +80,9 @@ void ofconn_set_role(struct ofconn *, enum nx_role);
 enum nx_flow_format ofconn_get_flow_format(struct ofconn *);
 void ofconn_set_flow_format(struct ofconn *, enum nx_flow_format);
 
+bool ofconn_get_flow_mod_table_id(const struct ofconn *);
+void ofconn_set_flow_mod_table_id(struct ofconn *, bool enable);
+
 int ofconn_get_miss_send_len(const struct ofconn *);
 void ofconn_set_miss_send_len(struct ofconn *, int miss_send_len);
 
diff --git a/ofproto/ofproto-dpif.c b/ofproto/ofproto-dpif.c
index 3d919846..ca99bec1 100644
--- a/ofproto/ofproto-dpif.c
+++ b/ofproto/ofproto-dpif.c
@@ -43,6 +43,7 @@
 #include "ofproto-sflow.h"
 #include "poll-loop.h"
 #include "timer.h"
+#include "unaligned.h"
 #include "unixctl.h"
 #include "vlan-bitmap.h"
 #include "vlog.h"
@@ -307,6 +308,9 @@ struct ofproto_dpif {
     struct dpif *dpif;
     int max_ports;
 
+    /* Statistics. */
+    uint64_t n_matches;
+
     /* Bridging. */
     struct netflow *netflow;
     struct ofproto_sflow *sflow;
@@ -417,6 +421,7 @@ construct(struct ofproto *ofproto_)
     }
 
     ofproto->max_ports = dpif_get_max_ports(ofproto->dpif);
+    ofproto->n_matches = 0;
 
     error = dpif_recv_set_mask(ofproto->dpif,
                                ((1u << DPIF_UC_MISS) |
@@ -445,6 +450,10 @@ construct(struct ofproto *ofproto_)
     ofproto->need_revalidate = false;
     tag_set_init(&ofproto->revalidate_set);
 
+    ofproto->up.tables = xmalloc(sizeof *ofproto->up.tables);
+    classifier_init(&ofproto->up.tables[0]);
+    ofproto->up.n_tables = 1;
+
     ofproto_dpif_unixctl_init();
 
     return 0;
@@ -586,6 +595,39 @@ flush(struct ofproto *ofproto_)
     dpif_flow_flush(ofproto->dpif);
 }
 
+static void
+get_features(struct ofproto *ofproto_ OVS_UNUSED,
+             bool *arp_match_ip, uint32_t *actions)
+{
+    *arp_match_ip = true;
+    *actions = ((1u << OFPAT_OUTPUT) |
+                (1u << OFPAT_SET_VLAN_VID) |
+                (1u << OFPAT_SET_VLAN_PCP) |
+                (1u << OFPAT_STRIP_VLAN) |
+                (1u << OFPAT_SET_DL_SRC) |
+                (1u << OFPAT_SET_DL_DST) |
+                (1u << OFPAT_SET_NW_SRC) |
+                (1u << OFPAT_SET_NW_DST) |
+                (1u << OFPAT_SET_NW_TOS) |
+                (1u << OFPAT_SET_TP_SRC) |
+                (1u << OFPAT_SET_TP_DST) |
+                (1u << OFPAT_ENQUEUE));
+}
+
+static void
+get_tables(struct ofproto *ofproto_, struct ofp_table_stats *ots)
+{
+    struct ofproto_dpif *ofproto = ofproto_dpif_cast(ofproto_);
+    struct odp_stats s;
+
+    strcpy(ots->name, "classifier");
+
+    dpif_get_dp_stats(ofproto->dpif, &s);
+    put_32aligned_be64(&ots->lookup_count, htonll(s.n_hit + s.n_missed));
+    put_32aligned_be64(&ots->matched_count,
+                       htonll(s.n_hit + ofproto->n_matches));
+}
+
 static int
 set_netflow(struct ofproto *ofproto_,
             const struct netflow_options *netflow_options)
@@ -1540,6 +1582,7 @@ handle_miss_upcall(struct ofproto_dpif *ofproto, struct dpif_upcall *upcall)
     /* Handle 802.1ag and LACP. */
     if (process_special(ofproto, &flow, upcall->packet)) {
         ofpbuf_delete(upcall->packet);
+        ofproto->n_matches++;
         return;
     }
 
@@ -1594,6 +1637,7 @@ handle_miss_upcall(struct ofproto_dpif *ofproto, struct dpif_upcall *upcall)
 
     facet_execute(ofproto, facet, upcall->packet);
     facet_install(ofproto, facet, false);
+    ofproto->n_matches++;
 }
 
 static void
@@ -1655,7 +1699,7 @@ expire(struct ofproto_dpif *ofproto)
     expire_facets(ofproto, dp_max_idle);
 
     /* Expire OpenFlow flows whose idle_timeout or hard_timeout has passed. */
-    cls_cursor_init(&cursor, &ofproto->up.cls, NULL);
+    cls_cursor_init(&cursor, &ofproto->up.tables[0], NULL);
     CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, up.cr, &cursor) {
         rule_expire(rule);
     }
@@ -2428,7 +2472,8 @@ static struct rule_dpif *
 rule_dpif_lookup(struct ofproto_dpif *ofproto, const struct flow *flow)
 {
     return rule_dpif_cast(rule_from_cls_rule(
-                              classifier_lookup(&ofproto->up.cls, flow)));
+                              classifier_lookup(&ofproto->up.tables[0],
+                                                flow)));
 }
 
 static struct rule *
@@ -2460,7 +2505,7 @@ rule_construct(struct rule *rule_)
     }
 
     old_rule = rule_dpif_cast(rule_from_cls_rule(classifier_find_rule_exactly(
-                                                     &ofproto->up.cls,
+                                                     &ofproto->up.tables[0],
                                                      &rule->up.cr)));
     if (old_rule) {
         ofproto_rule_destroy(&old_rule->up);
@@ -2470,7 +2515,7 @@ rule_construct(struct rule *rule_)
     rule->packet_count = 0;
     rule->byte_count = 0;
     list_init(&rule->facets);
-    classifier_insert(&ofproto->up.cls, &rule->up.cr);
+    classifier_insert(&ofproto->up.tables[0], &rule->up.cr);
 
     ofproto->need_revalidate = true;
 
@@ -2484,7 +2529,7 @@ rule_destruct(struct rule *rule_)
     struct ofproto_dpif *ofproto = ofproto_dpif_cast(rule->up.ofproto);
     struct facet *facet, *next_facet;
 
-    classifier_remove(&ofproto->up.cls, &rule->up.cr);
+    classifier_remove(&ofproto->up.tables[0], &rule->up.cr);
     LIST_FOR_EACH_SAFE (facet, next_facet, list_node, &rule->facets) {
         facet_revalidate(ofproto, facet);
     }
@@ -3854,6 +3899,8 @@ const struct ofproto_class ofproto_dpif_class = {
     run,
     wait,
     flush,
+    get_features,
+    get_tables,
     port_alloc,
     port_construct,
     port_destruct,
diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
index c58b4483..f0fc4ec7 100644
--- a/ofproto/ofproto.c
+++ b/ofproto/ofproto.c
@@ -261,7 +261,8 @@ ofproto_create(const char *datapath_name, const char *datapath_type,
     ofproto->netdev_monitor = netdev_monitor_create();
     hmap_init(&ofproto->ports);
     shash_init(&ofproto->port_by_name);
-    classifier_init(&ofproto->cls);
+    ofproto->tables = NULL;
+    ofproto->n_tables = 0;
     ofproto->connmgr = connmgr_create(ofproto, datapath_name, datapath_name);
 
     error = ofproto->ofproto_class->construct(ofproto);
@@ -271,6 +272,7 @@ ofproto_create(const char *datapath_name, const char *datapath_type,
         ofproto_destroy__(ofproto);
         return error;
     }
+    assert(ofproto->n_tables > 0);
 
     ofproto->datapath_id = pick_datapath_id(ofproto);
     VLOG_INFO("using datapath ID %016"PRIx64, ofproto->datapath_id);
@@ -588,6 +590,8 @@ ofproto_get_snoops(const struct ofproto *ofproto, struct sset *snoops)
 static void
 ofproto_destroy__(struct ofproto *ofproto)
 {
+    size_t i;
+
     connmgr_destroy(ofproto->connmgr);
 
     hmap_remove(&all_ofprotos, &ofproto->hmap_node);
@@ -600,7 +604,11 @@ ofproto_destroy__(struct ofproto *ofproto)
     netdev_monitor_destroy(ofproto->netdev_monitor);
     hmap_destroy(&ofproto->ports);
     shash_destroy(&ofproto->port_by_name);
-    classifier_destroy(&ofproto->cls);
+
+    for (i = 0; i < ofproto->n_tables; i++) {
+        classifier_destroy(&ofproto->tables[i]);
+    }
+    free(ofproto->tables);
 
     ofproto->ofproto_class->dealloc(ofproto);
 }
@@ -863,7 +871,7 @@ ofproto_port_del(struct ofproto *ofproto, uint16_t ofp_port)
     return error;
 }
 
-/* Adds a flow to the OpenFlow flow table in 'p' that matches 'cls_rule' and
+/* Adds a flow to OpenFlow flow table 0 in 'p' that matches 'cls_rule' and
  * performs the 'n_actions' actions in 'actions'.  The new flow will not
  * timeout.
  *
@@ -871,7 +879,9 @@ ofproto_port_del(struct ofproto *ofproto, uint16_t ofp_port)
  * (0...65535, inclusive) then the flow will be visible to OpenFlow
  * controllers; otherwise, it will be hidden.
  *
- * The caller retains ownership of 'cls_rule' and 'actions'. */
+ * The caller retains ownership of 'cls_rule' and 'actions'.
+ *
+ * This is a helper function for in-band control and fail-open. */
 void
 ofproto_add_flow(struct ofproto *p, const struct cls_rule *cls_rule,
                  const union ofp_action *actions, size_t n_actions)
@@ -880,21 +890,24 @@ ofproto_add_flow(struct ofproto *p, const struct cls_rule *cls_rule,
     rule_create(p, cls_rule, actions, n_actions, 0, 0, 0, false, &rule);
 }
 
+/* Searches for a rule with matching criteria exactly equal to 'target' in
+ * ofproto's table 0 and, if it finds one, deletes it.
+ *
+ * This is a helper function for in-band control and fail-open. */
 void
 ofproto_delete_flow(struct ofproto *ofproto, const struct cls_rule *target)
 {
     struct rule *rule;
 
-    rule = rule_from_cls_rule(classifier_find_rule_exactly(&ofproto->cls,
-                                                           target));
+    rule = rule_from_cls_rule(classifier_find_rule_exactly(
+                                  &ofproto->tables[0], target));
     ofproto_rule_destroy(rule);
 }
 
 static void
 ofproto_flush_flows__(struct ofproto *ofproto)
 {
-    struct rule *rule, *next_rule;
-    struct cls_cursor cursor;
+    size_t i;
 
     COVERAGE_INC(ofproto_flush);
 
@@ -902,12 +915,19 @@ ofproto_flush_flows__(struct ofproto *ofproto)
         ofproto->ofproto_class->flush(ofproto);
     }
 
-    cls_cursor_init(&cursor, &ofproto->cls, NULL);
-    CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, cr, &cursor) {
-        ofproto_rule_destroy(rule);
+    for (i = 0; i < ofproto->n_tables; i++) {
+        struct rule *rule, *next_rule;
+        struct cls_cursor cursor;
+
+        cls_cursor_init(&cursor, &ofproto->tables[i], NULL);
+        CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, cr, &cursor) {
+            ofproto_rule_destroy(rule);
+        }
     }
 }
 
+/* Deletes all of the flows from all of ofproto's flow tables, then
+ * reintroduces rules required by in-band control and fail open. */
 void
 ofproto_flush_flows(struct ofproto *ofproto)
 {
@@ -1352,25 +1372,22 @@ handle_features_request(struct ofconn *ofconn, const struct ofp_header *oh)
     struct ofp_switch_features *osf;
     struct ofpbuf *buf;
     struct ofport *port;
+    bool arp_match_ip;
+    uint32_t actions;
+
+    ofproto->ofproto_class->get_features(ofproto, &arp_match_ip, &actions);
+    assert(actions & (1 << OFPAT_OUTPUT)); /* sanity check */
 
     osf = make_openflow_xid(sizeof *osf, OFPT_FEATURES_REPLY, oh->xid, &buf);
     osf->datapath_id = htonll(ofproto->datapath_id);
     osf->n_buffers = htonl(pktbuf_capacity());
-    osf->n_tables = 1;
+    osf->n_tables = ofproto->n_tables;
     osf->capabilities = htonl(OFPC_FLOW_STATS | OFPC_TABLE_STATS |
-                              OFPC_PORT_STATS | OFPC_ARP_MATCH_IP);
-    osf->actions = htonl((1u << OFPAT_OUTPUT) |
-                         (1u << OFPAT_SET_VLAN_VID) |
-                         (1u << OFPAT_SET_VLAN_PCP) |
-                         (1u << OFPAT_STRIP_VLAN) |
-                         (1u << OFPAT_SET_DL_SRC) |
-                         (1u << OFPAT_SET_DL_DST) |
-                         (1u << OFPAT_SET_NW_SRC) |
-                         (1u << OFPAT_SET_NW_DST) |
-                         (1u << OFPAT_SET_NW_TOS) |
-                         (1u << OFPAT_SET_TP_SRC) |
-                         (1u << OFPAT_SET_TP_DST) |
-                         (1u << OFPAT_ENQUEUE));
+                              OFPC_PORT_STATS);
+    if (arp_match_ip) {
+        osf->capabilities |= htonl(OFPC_ARP_MATCH_IP);
+    }
+    osf->actions = htonl(actions);
 
     HMAP_FOR_EACH (port, hmap_node, &ofproto->ports) {
         ofpbuf_put(buf, &port->opp, sizeof port->opp);
@@ -1651,19 +1668,27 @@ handle_table_stats_request(struct ofconn *ofconn,
     struct ofproto *p = ofconn_get_ofproto(ofconn);
     struct ofp_table_stats *ots;
     struct ofpbuf *msg;
+    size_t i;
+
+    msg = start_ofp_stats_reply(request, sizeof *ots * p->n_tables);
+
+    ots = ofpbuf_put_zeros(msg, sizeof *ots * p->n_tables);
+    for (i = 0; i < p->n_tables; i++) {
+        ots[i].table_id = i;
+        sprintf(ots[i].name, "table%d", i);
+        ots[i].wildcards = htonl(OVSFW_ALL);
+        ots[i].max_entries = htonl(1000000); /* An arbitrary big number. */
+        ots[i].active_count = htonl(classifier_count(&p->tables[i]));
+    }
 
-    msg = start_ofp_stats_reply(request, sizeof *ots * 2);
+    p->ofproto_class->get_tables(p, ots);
 
-    /* Classifier table. */
-    ots = append_ofp_stats_reply(sizeof *ots, ofconn, &msg);
-    memset(ots, 0, sizeof *ots);
-    strcpy(ots->name, "classifier");
-    ots->wildcards = (ofconn_get_flow_format(ofconn) == NXFF_OPENFLOW10
-                      ? htonl(OFPFW_ALL) : htonl(OVSFW_ALL));
-    ots->max_entries = htonl(1024 * 1024); /* An arbitrary big number. */
-    ots->active_count = htonl(classifier_count(&p->cls));
-    put_32aligned_be64(&ots->lookup_count, htonll(0));  /* XXX */
-    put_32aligned_be64(&ots->matched_count, htonll(0)); /* XXX */
+    if (ofconn_get_flow_format(ofconn) == NXFF_OPENFLOW10) {
+        /* OpenFlow 1.0 only supports the OFPFW_* bits. */
+        for (i = 0; i < p->n_tables; i++) {
+            ots[i].wildcards &= htonl(OFPFW_ALL);
+        }
+    }
 
     ofconn_send_reply(ofconn, msg);
     return 0;
@@ -1762,7 +1787,7 @@ put_ofp_flow_stats(struct ofconn *ofconn, struct rule *rule,
 
     ofs = append_ofp_stats_reply(len, ofconn, replyp);
     ofs->length = htons(len);
-    ofs->table_id = 0;
+    ofs->table_id = rule->table_id;
     ofs->pad = 0;
     ofputil_cls_rule_to_match(&rule->cr, ofconn_get_flow_format(ofconn),
                               &ofs->match, rule->flow_cookie, &cookie);
@@ -1779,38 +1804,68 @@ put_ofp_flow_stats(struct ofconn *ofconn, struct rule *rule,
     }
 }
 
-static bool
-is_valid_table(uint8_t table_id)
+static struct classifier *
+first_matching_table(struct ofproto *ofproto, uint8_t table_id)
 {
-    if (table_id == 0 || table_id == 0xff) {
-        return true;
+    if (table_id == 0xff) {
+        return &ofproto->tables[0];
+    } else if (table_id < ofproto->n_tables) {
+        return &ofproto->tables[table_id];
     } else {
         /* It would probably be better to reply with an error but there doesn't
          * seem to be any appropriate value, so that might just be
          * confusing. */
         VLOG_WARN_RL(&rl, "controller asked for invalid table %"PRIu8,
                      table_id);
-        return false;
+        return NULL;
     }
 }
 
+static struct classifier *
+next_matching_table(struct ofproto *ofproto,
+                    struct classifier *cls, uint8_t table_id)
+{
+    return (table_id == 0xff && cls != &ofproto->tables[ofproto->n_tables - 1]
+            ? cls + 1
+            : NULL);
+}
+
+/* Assigns CLS to each classifier table, in turn, that matches TABLE_ID in
+ * OFPROTO:
+ *
+ *   - If TABLE_ID is 0xff, this iterates over every classifier table in
+ *     OFPROTO.
+ *
+ *   - If TABLE_ID is the number of a table in OFPROTO, then the loop iterates
+ *     only once, for that table.
+ *
+ *   - Otherwise, TABLE_ID isn't valid for OFPROTO, so ofproto logs a warning
+ *     and does not enter the loop at all.
+ *
+ * All parameters are evaluated multiple times.
+ */
+#define FOR_EACH_MATCHING_TABLE(CLS, TABLE_ID, OFPROTO)         \
+    for ((CLS) = first_matching_table(OFPROTO, TABLE_ID);       \
+         (CLS) != NULL;                                         \
+         (CLS) = next_matching_table(OFPROTO, CLS, TABLE_ID))
+
 static int
 handle_flow_stats_request(struct ofconn *ofconn, const struct ofp_header *oh)
 {
     const struct ofp_flow_stats_request *fsr = ofputil_stats_body(oh);
     struct ofproto *ofproto = ofconn_get_ofproto(ofconn);
+    struct classifier *cls;
+    struct cls_rule target;
     struct ofpbuf *reply;
 
     COVERAGE_INC(ofproto_flows_req);
     reply = start_ofp_stats_reply(oh, 1024);
-    if (is_valid_table(fsr->table_id)) {
+    ofputil_cls_rule_from_match(&fsr->match, 0, NXFF_OPENFLOW10, 0, &target);
+    FOR_EACH_MATCHING_TABLE (cls, fsr->table_id, ofproto) {
         struct cls_cursor cursor;
-        struct cls_rule target;
         struct rule *rule;
 
-        ofputil_cls_rule_from_match(&fsr->match, 0, NXFF_OPENFLOW10, 0,
-                                    &target);
-        cls_cursor_init(&cursor, &ofproto->cls, &target);
+        cls_cursor_init(&cursor, cls, &target);
         CLS_CURSOR_FOR_EACH (rule, cr, &cursor) {
             put_ofp_flow_stats(ofconn, rule, fsr->out_port, &reply);
         }
@@ -1865,6 +1920,7 @@ handle_nxst_flow(struct ofconn *ofconn, const struct ofp_header *oh)
 {
     struct ofproto *ofproto = ofconn_get_ofproto(ofconn);
     struct nx_flow_stats_request *nfsr;
+    struct classifier *cls;
     struct cls_rule target;
     struct ofpbuf *reply;
     struct ofpbuf b;
@@ -1884,11 +1940,11 @@ handle_nxst_flow(struct ofconn *ofconn, const struct ofp_header *oh)
 
     COVERAGE_INC(ofproto_flows_req);
     reply = start_nxstats_reply(&nfsr->nsm, 1024);
-    if (is_valid_table(nfsr->table_id)) {
+    FOR_EACH_MATCHING_TABLE (cls, nfsr->table_id, ofproto) {
         struct cls_cursor cursor;
         struct rule *rule;
 
-        cls_cursor_init(&cursor, &ofproto->cls, &target);
+        cls_cursor_init(&cursor, cls, &target);
         CLS_CURSOR_FOR_EACH (rule, cr, &cursor) {
             put_nx_flow_stats(ofconn, rule, nfsr->out_port, &reply);
         }
@@ -1907,6 +1963,9 @@ flow_stats_ds(struct rule *rule, struct ds *results)
     rule->ofproto->ofproto_class->rule_get_stats(rule,
                                                  &packet_count, &byte_count);
 
+    if (rule->table_id != 0) {
+        ds_put_format(results, "table_id=%"PRIu8", ", rule->table_id);
+    }
     ds_put_format(results, "duration=%llds, ",
                   (time_msec() - rule->created) / 1000);
     ds_put_format(results, "priority=%u, ", rule->cr.priority);
@@ -1927,12 +1986,16 @@ flow_stats_ds(struct rule *rule, struct ds *results)
 void
 ofproto_get_all_flows(struct ofproto *p, struct ds *results)
 {
-    struct cls_cursor cursor;
-    struct rule *rule;
+    struct classifier *cls;
+
+    for (cls = &p->tables[0]; cls < &p->tables[p->n_tables]; cls++) {
+        struct cls_cursor cursor;
+        struct rule *rule;
 
-    cls_cursor_init(&cursor, &p->cls, NULL);
-    CLS_CURSOR_FOR_EACH (rule, cr, &cursor) {
-        flow_stats_ds(rule, results);
+        cls_cursor_init(&cursor, cls, NULL);
+        CLS_CURSOR_FOR_EACH (rule, cr, &cursor) {
+            flow_stats_ds(rule, results);
+        }
     }
 }
 
@@ -1952,15 +2015,16 @@ query_aggregate_stats(struct ofproto *ofproto, struct cls_rule *target,
 {
     uint64_t total_packets = 0;
     uint64_t total_bytes = 0;
+    struct classifier *cls;
     int n_flows = 0;
 
     COVERAGE_INC(ofproto_agg_request);
 
-    if (is_valid_table(table_id)) {
+    FOR_EACH_MATCHING_TABLE (cls, table_id, ofproto) {
         struct cls_cursor cursor;
         struct rule *rule;
 
-        cls_cursor_init(&cursor, &ofproto->cls, target);
+        cls_cursor_init(&cursor, cls, target);
         CLS_CURSOR_FOR_EACH (rule, cr, &cursor) {
             if (!rule_is_hidden(rule) && rule_has_out_port(rule, out_port)) {
                 uint64_t packet_count;
@@ -2144,9 +2208,14 @@ add_flow(struct ofconn *ofconn, struct flow_mod *fm)
     int buf_err;
     int error;
 
-    if (fm->flags & OFPFF_CHECK_OVERLAP
-        && classifier_rule_overlaps(&p->cls, &fm->cr)) {
-        return ofp_mkerr(OFPET_FLOW_MOD_FAILED, OFPFMFC_OVERLAP);
+    if (fm->flags & OFPFF_CHECK_OVERLAP) {
+        struct classifier *cls;
+
+        FOR_EACH_MATCHING_TABLE (cls, fm->table_id, p) {
+            if (classifier_rule_overlaps(cls, &fm->cr)) {
+                return ofp_mkerr(OFPET_FLOW_MOD_FAILED, OFPFMFC_OVERLAP);
+            }
+        }
     }
 
     buf_err = ofconn_pktbuf_retrieve(ofconn, fm->buffer_id, &packet, &in_port);
@@ -2165,10 +2234,35 @@ add_flow(struct ofconn *ofconn, struct flow_mod *fm)
     return buf_err;
 }
 
-static struct rule *
-find_flow_strict(struct ofproto *p, const struct flow_mod *fm)
+/* Searches 'p' for an exact match for 'fm', in the table or tables indicated
+ * by fm->table_id.  Returns 0 if no match was found, 1 if exactly one match
+ * was found, 2 if more than one match was found.  If exactly one match is
+ * found, sets '*rulep' to the match, otherwise to NULL.
+ *
+ * This implements the rules for "strict" matching explained in the comment on
+ * struct nxt_flow_mod_table_id in nicira-ext.h.
+ *
+ * Ignores hidden rules. */
+static int
+find_flow_strict(struct ofproto *p, const struct flow_mod *fm,
+                 struct rule **rulep)
 {
-    return rule_from_cls_rule(classifier_find_rule_exactly(&p->cls, &fm->cr));
+    struct classifier *cls;
+
+    *rulep = NULL;
+    FOR_EACH_MATCHING_TABLE (cls, fm->table_id, p) {
+        struct rule *rule;
+
+        rule = rule_from_cls_rule(classifier_find_rule_exactly(cls, &fm->cr));
+        if (rule && !rule_is_hidden(rule)) {
+            if (*rulep) {
+                *rulep = NULL;
+                return 2;
+            }
+            *rulep = rule;
+        }
+    }
+    return *rulep != NULL;
 }
 
 static int
@@ -2211,19 +2305,23 @@ modify_flows_loose(struct ofconn *ofconn, struct flow_mod *fm)
 {
     struct ofproto *p = ofconn_get_ofproto(ofconn);
     struct rule *match = NULL;
-    struct cls_cursor cursor;
-    struct rule *rule;
+    struct classifier *cls;
     int error;
 
     error = 0;
-    cls_cursor_init(&cursor, &p->cls, &fm->cr);
-    CLS_CURSOR_FOR_EACH (rule, cr, &cursor) {
-        if (!rule_is_hidden(rule)) {
-            int retval = modify_flow(fm, rule);
-            if (!retval) {
-                match = rule;
-            } else {
-                error = retval;
+    FOR_EACH_MATCHING_TABLE (cls, fm->table_id, p) {
+        struct cls_cursor cursor;
+        struct rule *rule;
+
+        cls_cursor_init(&cursor, cls, &fm->cr);
+        CLS_CURSOR_FOR_EACH (rule, cr, &cursor) {
+            if (!rule_is_hidden(rule)) {
+                int retval = modify_flow(fm, rule);
+                if (!retval) {
+                    match = rule;
+                } else {
+                    error = retval;
+                }
             }
         }
     }
@@ -2250,15 +2348,25 @@ static int
 modify_flow_strict(struct ofconn *ofconn, struct flow_mod *fm)
 {
     struct ofproto *p = ofconn_get_ofproto(ofconn);
-    struct rule *rule = find_flow_strict(p, fm);
-    if (rule && !rule_is_hidden(rule)) {
-        int error = modify_flow(fm, rule);
+    struct rule *rule;
+    int error;
+
+    switch (find_flow_strict(p, fm, &rule)) {
+    case 0:
+        return add_flow(ofconn, fm);
+
+    case 1:
+        error = modify_flow(fm, rule);
         if (!error) {
             error = send_buffered_packet(ofconn, rule, fm->buffer_id);
         }
         return error;
-    } else {
-        return add_flow(ofconn, fm);
+
+    case 2:
+        return 0;
+
+    default:
+        NOT_REACHED();
     }
 }
 
@@ -2303,12 +2411,16 @@ static void delete_flow(struct rule *, ovs_be16 out_port);
 static void
 delete_flows_loose(struct ofproto *p, const struct flow_mod *fm)
 {
-    struct rule *rule, *next_rule;
-    struct cls_cursor cursor;
+    struct classifier *cls;
 
-    cls_cursor_init(&cursor, &p->cls, &fm->cr);
-    CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, cr, &cursor) {
-        delete_flow(rule, htons(fm->out_port));
+    FOR_EACH_MATCHING_TABLE (cls, fm->table_id, p) {
+        struct rule *rule, *next_rule;
+        struct cls_cursor cursor;
+
+        cls_cursor_init(&cursor, cls, &fm->cr);
+        CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, cr, &cursor) {
+            delete_flow(rule, htons(fm->out_port));
+        }
     }
 }
 
@@ -2316,8 +2428,8 @@ delete_flows_loose(struct ofproto *p, const struct flow_mod *fm)
 static void
 delete_flow_strict(struct ofproto *p, struct flow_mod *fm)
 {
-    struct rule *rule = find_flow_strict(p, fm);
-    if (rule) {
+    struct rule *rule;
+    if (find_flow_strict(p, fm, &rule) == 1) {
         delete_flow(rule, htons(fm->out_port));
     }
 }
@@ -2391,7 +2503,8 @@ handle_flow_mod(struct ofconn *ofconn, const struct ofp_header *oh)
         return error;
     }
 
-    error = ofputil_decode_flow_mod(&fm, oh, ofconn_get_flow_format(ofconn));
+    error = ofputil_decode_flow_mod(&fm, oh, ofconn_get_flow_format(ofconn),
+                                    ofconn_get_flow_mod_table_id(ofconn));
     if (error) {
         return error;
     }
@@ -2423,6 +2536,10 @@ handle_flow_mod(struct ofconn *ofconn, const struct ofp_header *oh)
         return 0;
 
     default:
+        if (fm.command > 0xff) {
+            VLOG_WARN_RL(&rl, "flow_mod has explicit table_id but "
+                         "flow_mod_table_id extension is not enabled");
+        }
         return ofp_mkerr(OFPET_FLOW_MOD_FAILED, OFPFMFC_BAD_COMMAND);
     }
 }
@@ -2472,6 +2589,17 @@ handle_role_request(struct ofconn *ofconn, const struct ofp_header *oh)
 }
 
 static int
+handle_nxt_flow_mod_table_id(struct ofconn *ofconn,
+                             const struct ofp_header *oh)
+{
+    const struct nxt_flow_mod_table_id *msg
+        = (const struct nxt_flow_mod_table_id *) oh;
+
+    ofconn_set_flow_mod_table_id(ofconn, msg->set != 0);
+    return 0;
+}
+
+static int
 handle_nxt_set_flow_format(struct ofconn *ofconn, const struct ofp_header *oh)
 {
     const struct nxt_set_flow_format *msg
@@ -2551,6 +2679,9 @@ handle_openflow__(struct ofconn *ofconn, const struct ofpbuf *msg)
     case OFPUTIL_NXT_ROLE_REQUEST:
         return handle_role_request(ofconn, oh);
 
+    case OFPUTIL_NXT_FLOW_MOD_TABLE_ID:
+        return handle_nxt_flow_mod_table_id(ofconn, oh);
+
     case OFPUTIL_NXT_SET_FLOW_FORMAT:
         return handle_nxt_set_flow_format(ofconn, oh);
 
diff --git a/ofproto/private.h b/ofproto/private.h
index 64897913..f2e32045 100644
--- a/ofproto/private.h
+++ b/ofproto/private.h
@@ -49,8 +49,9 @@ struct ofproto {
     struct hmap ports;          /* Contains "struct ofport"s. */
     struct shash port_by_name;
 
-    /* Flow table. */
-    struct classifier cls;      /* Contains "struct rule"s. */
+    /* Flow tables. */
+    struct classifier *tables;  /* Each classifier contains "struct rule"s. */
+    int n_tables;
 
     /* OpenFlow connections. */
     struct connmgr *connmgr;
@@ -84,6 +85,7 @@ struct rule {
     long long int created;       /* Creation time. */
     uint16_t idle_timeout;       /* In seconds from time of last use. */
     uint16_t hard_timeout;       /* In seconds from time of creation. */
+    uint8_t table_id;            /* Index in ofproto's 'tables' array. */
     bool send_flow_removed;      /* Send a flow removed message? */
 
     union ofp_action *actions;   /* OpenFlow actions. */
@@ -235,12 +237,17 @@ struct ofproto_class {
 
     /* Life-cycle functions for an "ofproto" (see "Life Cycle" above).
      *
-     * ->construct() should not modify any base members of the ofproto, even
-     * though it may be tempting in a few cases.  In particular, the client
-     * will initialize the ofproto's 'ports' member after construction is
-     * complete.  An ofproto's flow table should be initially empty, so
-     * ->construct() should delete flows from the underlying datapath, if
-     * necessary, rather than populating the ofproto's 'cls'.
+     * ->construct() should not modify most base members of the ofproto.  In
+     * particular, the client will initialize the ofproto's 'ports' member
+     * after construction is complete.
+     *
+     * ->construct() should initialize the base 'n_tables' member to the number
+     * of flow tables supported by the datapath (between 1 and 254, inclusive),
+     * initialize the base 'tables' member with space for one classifier per
+     * table, and initialize each classifier with classifier_init.  Each flow
+     * table should be initially empty, so ->construct() should delete flows
+     * from the underlying datapath, if necessary, rather than populating the
+     * tables.
      *
      * Only one ofproto instance needs to be supported for any given datapath.
      * If a datapath is already open as part of one "ofproto", then another
@@ -284,6 +291,61 @@ struct ofproto_class {
      * than to do it one by one. */
     void (*flush)(struct ofproto *ofproto);
 
+    /* Helper for the OpenFlow OFPT_FEATURES_REQUEST request.
+     *
+     * The implementation should store true in '*arp_match_ip' if the switch
+     * supports matching IP addresses inside ARP requests and replies, false
+     * otherwise.
+     *
+     * The implementation should store in '*actions' a bitmap of the supported
+     * OpenFlow actions: the bit with value (1 << n) should be set to 1 if the
+     * implementation supports the action with value 'n', and to 0 otherwise.
+     * For example, if the implementation supports the OFPAT_OUTPUT and
+     * OFPAT_ENQUEUE actions, but no others, it would set '*actions' to (1 <<
+     * OFPAT_OUTPUT) | (1 << OFPAT_ENQUEUE).  Vendor actions are not included
+     * in '*actions'. */
+    void (*get_features)(struct ofproto *ofproto,
+                         bool *arp_match_ip, uint32_t *actions);
+
+    /* Helper for the OpenFlow OFPST_TABLE statistics request.
+     *
+     * The 'ots' array contains 'ofproto->n_tables' elements.  Each element is
+     * initialized as:
+     *
+     *   - 'table_id' to the array index.
+     *
+     *   - 'name' to "table#" where # is the table ID.
+     *
+     *   - 'wildcards' to OVSFW_ALL.
+     *
+     *   - 'max_entries' to 1,000,000.
+     *
+     *   - 'active_count' to the classifier_count() for the table.
+     *
+     *   - 'lookup_count' and 'matched_count' to 0.
+     *
+     * The implementation should update any members in each element for which
+     * it has better values:
+     *
+     *   - 'name' to a more meaningful name.
+     *
+     *   - 'wildcards' to the set of wildcards actually supported by the table
+     *     (if it doesn't support all OpenFlow wildcards).
+     *
+     *   - 'max_entries' to the maximum number of flows actually supported by
+     *     the hardware.
+     *
+     *   - 'lookup_count' to the number of packets looked up in this flow table
+     *     so far.
+     *
+     *   - 'matched_count' to the number of packets looked up in this flow
+     *     table so far that matched one of the flow entries.
+     *
+     * Keep in mind that all of the members of struct ofp_table_stats are in
+     * network byte order.
+     */
+    void (*get_tables)(struct ofproto *ofproto, struct ofp_table_stats *ots);
+
 /* ## ---------------- ## */
 /* ## ofport Functions ## */
 /* ## ---------------- ## */