ofproto: Implement asynchronous OFPT_FLOW_MOD commands.

Some switching hardware takes a very long time to update its forwarding
rules, up to hundreds of milliseconds.  It is undesirable for Open
vSwitch to block waiting this long for individual OpenFlow flow table
modification commands to complete.  This commit enables ofproto to queue
up any number of independent flow table operations with asynchronous
completion.

I tested earlier versions of this commit using the "ofproto/clog" and
"ofproto/unclog" commands that it implements in the software switch
implementation.  I have not tested the current version very much at all.

CC: Casey Barker <crbarker@google.com>
CC: Rajiv Ramanathan <rajivr@google.com>

1 files changed, 122 insertions, 174 deletions

diff --git a/ofproto/in-band.c b/ofproto/in-band.c
index 710aadd9d..14cfa040a 100644
--- a/ofproto/in-band.c
+++ b/ofproto/in-band.c
@@ -73,9 +73,21 @@ struct in_band_remote {
     struct netdev *remote_netdev; /* Device to send to next-hop MAC. */
 };
 
+/* What to do to an in_band_rule. */
+enum in_band_op {
+    ADD,                       /* Add the rule to ofproto's flow table. */
+    DELETE                     /* Delete the rule from ofproto's flow table. */
+};
+
+/* A rule to add to or delete from ofproto's flow table.  */
+struct in_band_rule {
+    struct cls_rule cls_rule;
+    enum in_band_op op;
+};
+
 struct in_band {
     struct ofproto *ofproto;
-    int queue_id, prev_queue_id;
+    int queue_id;
 
     /* Remote information. */
     time_t next_remote_refresh; /* Refresh timer. */
@@ -87,12 +99,8 @@ struct in_band {
     uint8_t local_mac[ETH_ADDR_LEN]; /* Current MAC. */
     struct netdev *local_netdev;     /* Local port's network device. */
 
-    /* Local and remote addresses that are installed as flows. */
-    uint8_t installed_local_mac[ETH_ADDR_LEN];
-    struct sockaddr_in *remote_addrs;
-    size_t n_remote_addrs;
-    uint8_t *remote_macs;
-    size_t n_remote_macs;
+    /* Flow tracking. */
+    struct hmap rules;          /* Contains "struct in_band_rule"s. */
 };
 
 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(60, 60);
@@ -271,47 +279,68 @@ in_band_rule_check(const struct flow *flow,
 }
 
 static void
-make_rules(struct in_band *ib,
-           void (*cb)(struct in_band *, const struct cls_rule *))
+add_rule(struct in_band *ib, const struct cls_rule *cls_rule)
 {
+    uint32_t hash = cls_rule_hash(cls_rule, 0);
+    struct in_band_rule *rule;
+
+    HMAP_FOR_EACH_WITH_HASH (rule, cls_rule.hmap_node, hash, &ib->rules) {
+        if (cls_rule_equal(&rule->cls_rule, cls_rule)) {
+            rule->op = ADD;
+            return;
+        }
+    }
+
+    rule = xmalloc(sizeof *rule);
+    rule->cls_rule = *cls_rule;
+    rule->op = ADD;
+    hmap_insert(&ib->rules, &rule->cls_rule.hmap_node, hash);
+}
+
+static void
+update_rules(struct in_band *ib)
+{
+    struct in_band_rule *ib_rule;
+    struct in_band_remote *r;
     struct cls_rule rule;
-    size_t i;
 
-    if (!eth_addr_is_zero(ib->installed_local_mac)) {
+    /* Mark all the existing rules for deletion.  (Afterward we will re-add any
+     * rules that are still valid.) */
+    HMAP_FOR_EACH (ib_rule, cls_rule.hmap_node, &ib->rules) {
+        ib_rule->op = DELETE;
+    }
+
+    if (!eth_addr_is_zero(ib->local_mac)) {
         /* (a) Allow DHCP requests sent from the local port. */
         cls_rule_init_catchall(&rule, IBR_FROM_LOCAL_DHCP);
         cls_rule_set_in_port(&rule, ODPP_LOCAL);
         cls_rule_set_dl_type(&rule, htons(ETH_TYPE_IP));
-        cls_rule_set_dl_src(&rule, ib->installed_local_mac);
+        cls_rule_set_dl_src(&rule, ib->local_mac);
         cls_rule_set_nw_proto(&rule, IPPROTO_UDP);
         cls_rule_set_tp_src(&rule, htons(DHCP_CLIENT_PORT));
         cls_rule_set_tp_dst(&rule, htons(DHCP_SERVER_PORT));
-        cb(ib, &rule);
+        add_rule(ib, &rule);
 
         /* (b) Allow ARP replies to the local port's MAC address. */
         cls_rule_init_catchall(&rule, IBR_TO_LOCAL_ARP);
         cls_rule_set_dl_type(&rule, htons(ETH_TYPE_ARP));
-        cls_rule_set_dl_dst(&rule, ib->installed_local_mac);
+        cls_rule_set_dl_dst(&rule, ib->local_mac);
         cls_rule_set_nw_proto(&rule, ARP_OP_REPLY);
-        cb(ib, &rule);
+        add_rule(ib, &rule);
 
         /* (c) Allow ARP requests from the local port's MAC address.  */
         cls_rule_init_catchall(&rule, IBR_FROM_LOCAL_ARP);
         cls_rule_set_dl_type(&rule, htons(ETH_TYPE_ARP));
-        cls_rule_set_dl_src(&rule, ib->installed_local_mac);
+        cls_rule_set_dl_src(&rule, ib->local_mac);
         cls_rule_set_nw_proto(&rule, ARP_OP_REQUEST);
-        cb(ib, &rule);
+        add_rule(ib, &rule);
     }
 
-    for (i = 0; i < ib->n_remote_macs; i++) {
-        const uint8_t *remote_mac = &ib->remote_macs[i * ETH_ADDR_LEN];
+    for (r = ib->remotes; r < &ib->remotes[ib->n_remotes]; r++) {
+        const uint8_t *remote_mac = r->remote_mac;
 
-        if (i > 0) {
-            const uint8_t *prev_mac = &ib->remote_macs[(i - 1) * ETH_ADDR_LEN];
-            if (eth_addr_equals(remote_mac, prev_mac)) {
-                /* Skip duplicates. */
-                continue;
-            }
+        if (eth_addr_is_zero(remote_mac)) {
+            continue;
         }
 
         /* (d) Allow ARP replies to the next hop's MAC address. */
@@ -319,184 +348,104 @@ make_rules(struct in_band *ib,
         cls_rule_set_dl_type(&rule, htons(ETH_TYPE_ARP));
         cls_rule_set_dl_dst(&rule, remote_mac);
         cls_rule_set_nw_proto(&rule, ARP_OP_REPLY);
-        cb(ib, &rule);
+        add_rule(ib, &rule);
 
         /* (e) Allow ARP requests from the next hop's MAC address. */
         cls_rule_init_catchall(&rule, IBR_FROM_NEXT_HOP_ARP);
         cls_rule_set_dl_type(&rule, htons(ETH_TYPE_ARP));
         cls_rule_set_dl_src(&rule, remote_mac);
         cls_rule_set_nw_proto(&rule, ARP_OP_REQUEST);
-        cb(ib, &rule);
+        add_rule(ib, &rule);
     }
 
-    for (i = 0; i < ib->n_remote_addrs; i++) {
-        const struct sockaddr_in *a = &ib->remote_addrs[i];
-
-        if (!i || a->sin_addr.s_addr != a[-1].sin_addr.s_addr) {
-            /* (f) Allow ARP replies containing the remote's IP address as a
-             * target. */
-            cls_rule_init_catchall(&rule, IBR_TO_REMOTE_ARP);
-            cls_rule_set_dl_type(&rule, htons(ETH_TYPE_ARP));
-            cls_rule_set_nw_proto(&rule, ARP_OP_REPLY);
-            cls_rule_set_nw_dst(&rule, a->sin_addr.s_addr);
-            cb(ib, &rule);
-
-            /* (g) Allow ARP requests containing the remote's IP address as a
-             * source. */
-            cls_rule_init_catchall(&rule, IBR_FROM_REMOTE_ARP);
-            cls_rule_set_dl_type(&rule, htons(ETH_TYPE_ARP));
-            cls_rule_set_nw_proto(&rule, ARP_OP_REQUEST);
-            cls_rule_set_nw_src(&rule, a->sin_addr.s_addr);
-            cb(ib, &rule);
-        }
-
-        if (!i
-            || a->sin_addr.s_addr != a[-1].sin_addr.s_addr
-            || a->sin_port != a[-1].sin_port) {
-            /* (h) Allow TCP traffic to the remote's IP and port. */
-            cls_rule_init_catchall(&rule, IBR_TO_REMOTE_TCP);
-            cls_rule_set_dl_type(&rule, htons(ETH_TYPE_IP));
-            cls_rule_set_nw_proto(&rule, IPPROTO_TCP);
-            cls_rule_set_nw_dst(&rule, a->sin_addr.s_addr);
-            cls_rule_set_tp_dst(&rule, a->sin_port);
-            cb(ib, &rule);
-
-            /* (i) Allow TCP traffic from the remote's IP and port. */
-            cls_rule_init_catchall(&rule, IBR_FROM_REMOTE_TCP);
-            cls_rule_set_dl_type(&rule, htons(ETH_TYPE_IP));
-            cls_rule_set_nw_proto(&rule, IPPROTO_TCP);
-            cls_rule_set_nw_src(&rule, a->sin_addr.s_addr);
-            cls_rule_set_tp_src(&rule, a->sin_port);
-            cb(ib, &rule);
-        }
-    }
-}
-
-static void
-drop_rule(struct in_band *ib, const struct cls_rule *rule)
-{
-    ofproto_delete_flow(ib->ofproto, rule);
-}
+    for (r = ib->remotes; r < &ib->remotes[ib->n_remotes]; r++) {
+        const struct sockaddr_in *a = &r->remote_addr;
 
-/* Drops from the flow table all of the flows set up by 'ib', then clears out
- * the information about the installed flows so that they can be filled in
- * again if necessary. */
-static void
-drop_rules(struct in_band *ib)
-{
-    /* Drop rules. */
-    make_rules(ib, drop_rule);
+        /* (f) Allow ARP replies containing the remote's IP address as a
+         * target. */
+        cls_rule_init_catchall(&rule, IBR_TO_REMOTE_ARP);
+        cls_rule_set_dl_type(&rule, htons(ETH_TYPE_ARP));
+        cls_rule_set_nw_proto(&rule, ARP_OP_REPLY);
+        cls_rule_set_nw_dst(&rule, a->sin_addr.s_addr);
+        add_rule(ib, &rule);
 
-    /* Clear out state. */
-    memset(ib->installed_local_mac, 0, sizeof ib->installed_local_mac);
+        /* (g) Allow ARP requests containing the remote's IP address as a
+         * source. */
+        cls_rule_init_catchall(&rule, IBR_FROM_REMOTE_ARP);
+        cls_rule_set_dl_type(&rule, htons(ETH_TYPE_ARP));
+        cls_rule_set_nw_proto(&rule, ARP_OP_REQUEST);
+        cls_rule_set_nw_src(&rule, a->sin_addr.s_addr);
+        add_rule(ib, &rule);
 
-    free(ib->remote_addrs);
-    ib->remote_addrs = NULL;
-    ib->n_remote_addrs = 0;
+        /* (h) Allow TCP traffic to the remote's IP and port. */
+        cls_rule_init_catchall(&rule, IBR_TO_REMOTE_TCP);
+        cls_rule_set_dl_type(&rule, htons(ETH_TYPE_IP));
+        cls_rule_set_nw_proto(&rule, IPPROTO_TCP);
+        cls_rule_set_nw_dst(&rule, a->sin_addr.s_addr);
+        cls_rule_set_tp_dst(&rule, a->sin_port);
+        add_rule(ib, &rule);
 
-    free(ib->remote_macs);
-    ib->remote_macs = NULL;
-    ib->n_remote_macs = 0;
+        /* (i) Allow TCP traffic from the remote's IP and port. */
+        cls_rule_init_catchall(&rule, IBR_FROM_REMOTE_TCP);
+        cls_rule_set_dl_type(&rule, htons(ETH_TYPE_IP));
+        cls_rule_set_nw_proto(&rule, IPPROTO_TCP);
+        cls_rule_set_nw_src(&rule, a->sin_addr.s_addr);
+        cls_rule_set_tp_src(&rule, a->sin_port);
+        add_rule(ib, &rule);
+    }
 }
 
-static void
-add_rule(struct in_band *ib, const struct cls_rule *rule)
+void
+in_band_run(struct in_band *ib)
 {
     struct {
         struct nx_action_set_queue nxsq;
         union ofp_action oa;
     } actions;
+    const void *a;
+    size_t na;
 
-    memset(&actions, 0, sizeof actions);
+    struct in_band_rule *rule, *next;
 
+    memset(&actions, 0, sizeof actions);
     actions.oa.output.type = htons(OFPAT_OUTPUT);
     actions.oa.output.len = htons(sizeof actions.oa);
     actions.oa.output.port = htons(OFPP_NORMAL);
     actions.oa.output.max_len = htons(0);
-
     if (ib->queue_id < 0) {
-        ofproto_add_flow(ib->ofproto, rule, &actions.oa, 1);
+        a = &actions.oa;
+        na = sizeof actions.oa / sizeof(union ofp_action);
     } else {
         actions.nxsq.type = htons(OFPAT_VENDOR);
         actions.nxsq.len = htons(sizeof actions.nxsq);
         actions.nxsq.vendor = htonl(NX_VENDOR_ID);
         actions.nxsq.subtype = htons(NXAST_SET_QUEUE);
         actions.nxsq.queue_id = htonl(ib->queue_id);
-
-        ofproto_add_flow(ib->ofproto, rule, (union ofp_action *) &actions,
-                         sizeof actions / sizeof(union ofp_action));
+        a = &actions;
+        na = sizeof actions / sizeof(union ofp_action);
     }
-}
 
-/* Inserts flows into the flow table for the current state of 'ib'. */
-static void
-add_rules(struct in_band *ib)
-{
-    make_rules(ib, add_rule);
-}
+    refresh_local(ib);
+    refresh_remotes(ib);
 
-static int
-compare_addrs(const void *a_, const void *b_)
-{
-    const struct sockaddr_in *a = a_;
-    const struct sockaddr_in *b = b_;
-    int cmp;
-
-    cmp = memcmp(&a->sin_addr.s_addr,
-                 &b->sin_addr.s_addr,
-                 sizeof a->sin_addr.s_addr);
-    if (cmp) {
-        return cmp;
-    }
-    return memcmp(&a->sin_port, &b->sin_port, sizeof a->sin_port);
-}
+    update_rules(ib);
 
-static int
-compare_macs(const void *a, const void *b)
-{
-    return eth_addr_compare_3way(a, b);
-}
+    HMAP_FOR_EACH_SAFE (rule, next, cls_rule.hmap_node, &ib->rules) {
+        switch (rule->op) {
+        case ADD:
+            ofproto_add_flow(ib->ofproto, &rule->cls_rule, a, na);
+            break;
 
-void
-in_band_run(struct in_band *ib)
-{
-    bool local_change, remote_change, queue_id_change;
-    struct in_band_remote *r;
-
-    local_change = refresh_local(ib);
-    remote_change = refresh_remotes(ib);
-    queue_id_change = ib->queue_id != ib->prev_queue_id;
-    if (!local_change && !remote_change && !queue_id_change) {
-        /* Nothing changed, nothing to do. */
-        return;
-    }
-    ib->prev_queue_id = ib->queue_id;
-
-    /* Drop old rules. */
-    drop_rules(ib);
-
-    /* Figure out new rules. */
-    memcpy(ib->installed_local_mac, ib->local_mac, ETH_ADDR_LEN);
-    ib->remote_addrs = xmalloc(ib->n_remotes * sizeof *ib->remote_addrs);
-    ib->n_remote_addrs = 0;
-    ib->remote_macs = xmalloc(ib->n_remotes * ETH_ADDR_LEN);
-    ib->n_remote_macs = 0;
-    for (r = ib->remotes; r < &ib->remotes[ib->n_remotes]; r++) {
-        ib->remote_addrs[ib->n_remote_addrs++] = r->remote_addr;
-        if (!eth_addr_is_zero(r->remote_mac)) {
-            memcpy(&ib->remote_macs[ib->n_remote_macs * ETH_ADDR_LEN],
-                   r->remote_mac, ETH_ADDR_LEN);
-            ib->n_remote_macs++;
+        case DELETE:
+            if (ofproto_delete_flow(ib->ofproto, &rule->cls_rule)) {
+                /* ofproto doesn't have the rule anymore so there's no reason
+                 * for us to track it any longer. */
+                hmap_remove(&ib->rules, &rule->cls_rule.hmap_node);
+                free(rule);
+            }
+            break;
         }
     }
-
-    /* Sort, to allow make_rules() to easily skip duplicates. */
-    qsort(ib->remote_addrs, ib->n_remote_addrs, sizeof *ib->remote_addrs,
-          compare_addrs);
-    qsort(ib->remote_macs, ib->n_remote_macs, ETH_ADDR_LEN, compare_macs);
-
-    /* Add new rules. */
-    add_rules(ib);
 }
 
 void
@@ -507,14 +456,6 @@ in_band_wait(struct in_band *in_band)
     poll_timer_wait_until(wakeup * 1000);
 }
 
-/* ofproto has flushed all flows from the flow table and it is calling us back
- * to allow us to reinstall the ones that are important to us. */
-void
-in_band_flushed(struct in_band *in_band)
-{
-    add_rules(in_band);
-}
-
 int
 in_band_create(struct ofproto *ofproto, const char *local_name,
                struct in_band **in_bandp)
@@ -533,10 +474,11 @@ in_band_create(struct ofproto *ofproto, const char *local_name,
 
     in_band = xzalloc(sizeof *in_band);
     in_band->ofproto = ofproto;
-    in_band->queue_id = in_band->prev_queue_id = -1;
+    in_band->queue_id = -1;
     in_band->next_remote_refresh = TIME_MIN;
     in_band->next_local_refresh = TIME_MIN;
     in_band->local_netdev = local_netdev;
+    hmap_init(&in_band->rules);
 
     *in_bandp = in_band;
 
@@ -547,7 +489,13 @@ void
 in_band_destroy(struct in_band *ib)
 {
     if (ib) {
-        drop_rules(ib);
+        struct in_band_rule *rule, *next;
+
+        HMAP_FOR_EACH_SAFE (rule, next, cls_rule.hmap_node, &ib->rules) {
+            hmap_remove(&ib->rules, &rule->cls_rule.hmap_node);
+            free(rule);
+        }
+        hmap_destroy(&ib->rules);
         in_band_set_remotes(ib, NULL, 0);
         netdev_close(ib->local_netdev);
         free(ib);