hash: Replace primary hash functions by murmurhash.
[sliver-openvswitch.git] / lib / flow.c
index e517a03..2a3dd3d 100644 (file)
@@ -16,7 +16,6 @@
 #include <config.h>
 #include <sys/types.h>
 #include "flow.h"
-#include <assert.h>
 #include <errno.h>
 #include <inttypes.h>
 #include <limits.h>
@@ -31,6 +30,8 @@
 #include "csum.h"
 #include "dynamic-string.h"
 #include "hash.h"
+#include "jhash.h"
+#include "match.h"
 #include "ofpbuf.h"
 #include "openflow/openflow.h"
 #include "packets.h"
@@ -316,7 +317,7 @@ invalid:
 
 }
 
-/* Initializes 'flow' members from 'packet', 'skb_priority', 'tun_id', and
+/* Initializes 'flow' members from 'packet', 'skb_priority', 'tnl', and
  * 'ofp_in_port'.
  *
  * Initializes 'packet' header pointers as follows:
@@ -334,8 +335,9 @@ invalid:
  *      present and has a correct length, and otherwise NULL.
  */
 void
-flow_extract(struct ofpbuf *packet, uint32_t skb_priority, ovs_be64 tun_id,
-             uint16_t ofp_in_port, struct flow *flow)
+flow_extract(struct ofpbuf *packet, uint32_t skb_priority, uint32_t skb_mark,
+             const struct flow_tnl *tnl, uint16_t ofp_in_port,
+             struct flow *flow)
 {
     struct ofpbuf b = *packet;
     struct eth_header *eth;
@@ -343,9 +345,14 @@ flow_extract(struct ofpbuf *packet, uint32_t skb_priority, ovs_be64 tun_id,
     COVERAGE_INC(flow_extract);
 
     memset(flow, 0, sizeof *flow);
-    flow->tun_id = tun_id;
+
+    if (tnl) {
+        ovs_assert(tnl != &flow->tunnel);
+        flow->tunnel = *tnl;
+    }
     flow->in_port = ofp_in_port;
     flow->skb_priority = skb_priority;
+    flow->skb_mark = skb_mark;
 
     packet->l2 = b.data;
     packet->l3 = NULL;
@@ -368,9 +375,33 @@ flow_extract(struct ofpbuf *packet, uint32_t skb_priority, ovs_be64 tun_id,
     }
     flow->dl_type = parse_ethertype(&b);
 
-    /* Network layer. */
     packet->l3 = b.data;
-    if (flow->dl_type == htons(ETH_TYPE_IP)) {
+    flow_extract_l3_onwards(packet, flow, flow->dl_type);
+}
+
+/* Initializes l3 and higher 'flow' members from 'packet'
+ *
+ * This should be called by or after flow_extract()
+ *
+ * Initializes 'packet' header pointers as follows:
+ *
+ *    - packet->l4 to just past the IPv4 header, if one is present and has a
+ *      correct length, and otherwise NULL.
+ *
+ *    - packet->l7 to just past the TCP or UDP or ICMP header, if one is
+ *      present and has a correct length, and otherwise NULL.
+ */
+void
+flow_extract_l3_onwards(struct ofpbuf *packet, struct flow *flow,
+                        ovs_be16 dl_type)
+{
+    struct ofpbuf b;
+
+    ofpbuf_use_const(&b, packet->l3, packet->size -
+                     (size_t)((char *)packet->l3 - (char *)packet->l2));
+
+    /* Network layer. */
+    if (dl_type == htons(ETH_TYPE_IP)) {
         const struct ip_header *nh = pull_ip(&b);
         if (nh) {
             packet->l4 = b.data;
@@ -403,7 +434,7 @@ flow_extract(struct ofpbuf *packet, uint32_t skb_priority, ovs_be64 tun_id,
                 }
             }
         }
-    } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
+    } else if (dl_type == htons(ETH_TYPE_IPV6)) {
         if (parse_ipv6(&b, flow)) {
             return;
         }
@@ -418,7 +449,8 @@ flow_extract(struct ofpbuf *packet, uint32_t skb_priority, ovs_be64 tun_id,
                 packet->l7 = b.data;
             }
         }
-    } else if (flow->dl_type == htons(ETH_TYPE_ARP)) {
+    } else if (dl_type == htons(ETH_TYPE_ARP) ||
+               dl_type == htons(ETH_TYPE_RARP)) {
         const struct arp_eth_header *arp = pull_arp(&b);
         if (arp && arp->ar_hrd == htons(1)
             && arp->ar_pro == htons(ETH_TYPE_IP)
@@ -429,13 +461,10 @@ flow_extract(struct ofpbuf *packet, uint32_t skb_priority, ovs_be64 tun_id,
                 flow->nw_proto = ntohs(arp->ar_op);
             }
 
-            if ((flow->nw_proto == ARP_OP_REQUEST)
-                || (flow->nw_proto == ARP_OP_REPLY)) {
-                flow->nw_src = arp->ar_spa;
-                flow->nw_dst = arp->ar_tpa;
-                memcpy(flow->arp_sha, arp->ar_sha, ETH_ADDR_LEN);
-                memcpy(flow->arp_tha, arp->ar_tha, ETH_ADDR_LEN);
-            }
+            flow->nw_src = arp->ar_spa;
+            flow->nw_dst = arp->ar_tpa;
+            memcpy(flow->arp_sha, arp->ar_sha, ETH_ADDR_LEN);
+            memcpy(flow->arp_tha, arp->ar_tha, ETH_ADDR_LEN);
         }
     }
 }
@@ -458,9 +487,9 @@ flow_zero_wildcards(struct flow *flow, const struct flow_wildcards *wildcards)
 void
 flow_get_metadata(const struct flow *flow, struct flow_metadata *fmd)
 {
-    BUILD_ASSERT_DECL(FLOW_WC_SEQ == 17);
+    BUILD_ASSERT_DECL(FLOW_WC_SEQ == 18);
 
-    fmd->tun_id = flow->tun_id;
+    fmd->tun_id = flow->tunnel.tun_id;
     fmd->metadata = flow->metadata;
     memcpy(fmd->regs, flow->regs, sizeof fmd->regs);
     fmd->in_port = flow->in_port;
@@ -474,63 +503,57 @@ flow_to_string(const struct flow *flow)
     return ds_cstr(&ds);
 }
 
-void
-flow_format(struct ds *ds, const struct flow *flow)
+const char *
+flow_tun_flag_to_string(uint32_t flags)
 {
-    ds_put_format(ds, "priority:%"PRIu32
-                      ",tunnel:%#"PRIx64
-                      ",metadata:%#"PRIx64
-                      ",in_port:%04"PRIx16,
-                      flow->skb_priority,
-                      ntohll(flow->tun_id),
-                      ntohll(flow->metadata),
-                      flow->in_port);
-
-    ds_put_format(ds, ",tci(");
-    if (flow->vlan_tci) {
-        ds_put_format(ds, "vlan:%"PRIu16",pcp:%d",
-                      vlan_tci_to_vid(flow->vlan_tci),
-                      vlan_tci_to_pcp(flow->vlan_tci));
-    } else {
-        ds_put_char(ds, '0');
-    }
-    ds_put_format(ds, ") mac("ETH_ADDR_FMT"->"ETH_ADDR_FMT
-                      ") type:%04"PRIx16,
-                  ETH_ADDR_ARGS(flow->dl_src),
-                  ETH_ADDR_ARGS(flow->dl_dst),
-                  ntohs(flow->dl_type));
-
-    if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
-        ds_put_format(ds, " label:%#"PRIx32" proto:%"PRIu8" tos:%#"PRIx8
-                          " ttl:%"PRIu8" ipv6(",
-                      ntohl(flow->ipv6_label), flow->nw_proto,
-                      flow->nw_tos, flow->nw_ttl);
-        print_ipv6_addr(ds, &flow->ipv6_src);
-        ds_put_cstr(ds, "->");
-        print_ipv6_addr(ds, &flow->ipv6_dst);
-        ds_put_char(ds, ')');
-    } else if (flow->dl_type == htons(ETH_TYPE_IP) ||
-               flow->dl_type == htons(ETH_TYPE_ARP)) {
-        ds_put_format(ds, " proto:%"PRIu8" tos:%#"PRIx8" ttl:%"PRIu8
-                          " ip("IP_FMT"->"IP_FMT")",
-                          flow->nw_proto, flow->nw_tos, flow->nw_ttl,
-                          IP_ARGS(&flow->nw_src), IP_ARGS(&flow->nw_dst));
+    switch (flags) {
+    case FLOW_TNL_F_DONT_FRAGMENT:
+        return "df";
+    case FLOW_TNL_F_CSUM:
+        return "csum";
+    case FLOW_TNL_F_KEY:
+        return "key";
+    default:
+        return NULL;
     }
-    if (flow->nw_frag) {
-        ds_put_format(ds, " frag(%s)",
-                      flow->nw_frag == FLOW_NW_FRAG_ANY ? "first"
-                      : flow->nw_frag == (FLOW_NW_FRAG_ANY | FLOW_NW_FRAG_LATER)
-                      ? "later" : "<error>");
+}
+
+void
+format_flags(struct ds *ds, const char *(*bit_to_string)(uint32_t),
+             uint32_t flags, char del)
+{
+    uint32_t bad = 0;
+
+    if (!flags) {
+        return;
     }
-    if (flow->tp_src || flow->tp_dst) {
-        ds_put_format(ds, " port(%"PRIu16"->%"PRIu16")",
-                ntohs(flow->tp_src), ntohs(flow->tp_dst));
+    while (flags) {
+        uint32_t bit = rightmost_1bit(flags);
+        const char *s;
+
+        s = bit_to_string(bit);
+        if (s) {
+            ds_put_format(ds, "%s%c", s, del);
+        } else {
+            bad |= bit;
+        }
+
+        flags &= ~bit;
     }
-    if (!eth_addr_is_zero(flow->arp_sha) || !eth_addr_is_zero(flow->arp_tha)) {
-        ds_put_format(ds, " arp_ha("ETH_ADDR_FMT"->"ETH_ADDR_FMT")",
-                ETH_ADDR_ARGS(flow->arp_sha),
-                ETH_ADDR_ARGS(flow->arp_tha));
+
+    if (bad) {
+        ds_put_format(ds, "0x%"PRIx32"%c", bad, del);
     }
+    ds_chomp(ds, del);
+}
+
+void
+flow_format(struct ds *ds, const struct flow *flow)
+{
+    struct match match;
+
+    match_wc_init(&match, flow);
+    match_format(&match, ds, OFP_DEFAULT_PRIORITY);
 }
 
 void
@@ -597,7 +620,7 @@ flow_wildcards_combine(struct flow_wildcards *dst,
 uint32_t
 flow_wildcards_hash(const struct flow_wildcards *wc, uint32_t basis)
 {
-    return flow_hash(&wc->masks, basis);;
+    return flow_hash(&wc->masks, basis);
 }
 
 /* Returns true if 'a' and 'b' represent the same wildcards, false if they are
@@ -700,7 +723,7 @@ flow_hash_symmetric_l4(const struct flow *flow, uint32_t basis)
             fields.tp_port = flow->tp_src ^ flow->tp_dst;
         }
     }
-    return hash_bytes(&fields, sizeof fields, basis);
+    return jhash_bytes(&fields, sizeof fields, basis);
 }
 
 /* Hashes the portions of 'flow' designated by 'fields'. */
@@ -711,7 +734,7 @@ flow_hash_fields(const struct flow *flow, enum nx_hash_fields fields,
     switch (fields) {
 
     case NX_HASH_FIELDS_ETH_SRC:
-        return hash_bytes(flow->dl_src, sizeof flow->dl_src, basis);
+        return jhash_bytes(flow->dl_src, sizeof flow->dl_src, basis);
 
     case NX_HASH_FIELDS_SYMMETRIC_L4:
         return flow_hash_symmetric_l4(flow, basis);
@@ -814,6 +837,7 @@ flow_compose(struct ofpbuf *b, const struct flow *flow)
         b->l3 = ip = ofpbuf_put_zeros(b, sizeof *ip);
         ip->ip_ihl_ver = IP_IHL_VER(5, 4);
         ip->ip_tos = flow->nw_tos;
+        ip->ip_ttl = flow->nw_ttl;
         ip->ip_proto = flow->nw_proto;
         ip->ip_src = flow->nw_src;
         ip->ip_dst = flow->nw_dst;
@@ -855,7 +879,8 @@ flow_compose(struct ofpbuf *b, const struct flow *flow)
         ip->ip_csum = csum(ip, sizeof *ip);
     } else if (flow->dl_type == htons(ETH_TYPE_IPV6)) {
         /* XXX */
-    } else if (flow->dl_type == htons(ETH_TYPE_ARP)) {
+    } else if (flow->dl_type == htons(ETH_TYPE_ARP) ||
+               flow->dl_type == htons(ETH_TYPE_RARP)) {
         struct arp_eth_header *arp;
 
         b->l3 = arp = ofpbuf_put_zeros(b, sizeof *arp);
@@ -1124,7 +1149,7 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
         }
     }
 
-    return mhash_finish(hash, p - mask->masks.values);
+    return mhash_finish(hash, (p - mask->masks.values) * 4);
 }
 
 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
@@ -1153,7 +1178,7 @@ flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
         }
     }
 
-    return mhash_finish(hash, p - mask->masks.values);
+    return mhash_finish(hash, (p - mask->masks.values) * 4);
 }
 \f
 /* Initializes 'dst' as a copy of 'src'.  The caller must eventually free 'dst'