MPLS hash function improvements

Change-Id: I28e98f445c01493562b6196a4f5b532a51f178af
Signed-off-by: Neale Ranns <nranns@cisco.com>

6 files changed, 206 insertions, 48 deletions

diff --git a/src/vnet/dpo/mpls_label_dpo.c b/src/vnet/dpo/mpls_label_dpo.c
index 18479531ca8..1c451a5116b 100644
--- a/src/vnet/dpo/mpls_label_dpo.c
+++ b/src/vnet/dpo/mpls_label_dpo.c
@@ -356,7 +356,7 @@ mpls_label_imposition_inline (vlib_main_t * vm,
                 }
                 if (PREDICT_TRUE(vnet_buffer(b2)->mpls.first))
                 {
-                    ASSERT(2 != vnet_buffer (b2)->mpls.ttl);
+                    ASSERT(1 != vnet_buffer (b2)->mpls.ttl);
 
                     ttl2 = vnet_buffer(b2)->mpls.ttl - 1;
                 }
diff --git a/src/vnet/mpls/mpls_lookup.c b/src/vnet/mpls/mpls_lookup.c
index 322e0db0733..42e5399c2da 100644
--- a/src/vnet/mpls/mpls_lookup.c
+++ b/src/vnet/mpls/mpls_lookup.c
@@ -65,14 +65,70 @@ mpls_compute_flow_hash (const mpls_unicast_header_t * hdr,
                         flow_hash_config_t flow_hash_config)
 {
     /*
-     * improve this to include:
-     *  - all labels in the stack.
-     *  - recognise entropy labels.
-     *
      * We need to byte swap so we use the numerical value. i.e. an odd label
-     * leads to an odd bucket. ass opposed to a label above and below value X.
+     * leads to an odd bucket. as opposed to a label above and below value X.
      */
-    return (vnet_mpls_uc_get_label(clib_net_to_host_u32(hdr->label_exp_s_ttl)));
+    u8 next_label_is_entropy;
+    mpls_label_t ho_label;
+    u32 hash, value;
+
+    ho_label = clib_net_to_host_u32(hdr->label_exp_s_ttl);
+    hash = vnet_mpls_uc_get_label(ho_label);
+    next_label_is_entropy = 0;
+
+    while (MPLS_EOS != vnet_mpls_uc_get_s(ho_label))
+    {
+        hdr++;
+        ho_label = clib_net_to_host_u32(hdr->label_exp_s_ttl);
+        value = vnet_mpls_uc_get_label(ho_label);
+
+        if (1 == next_label_is_entropy)
+        {
+            /*
+             * The label is an entropy value, use it alone as the hash
+             */
+            return (ho_label);
+        }
+        if (MPLS_IETF_ENTROPY_LABEL == value)
+        {
+            /*
+             * we've met a label in the stack indicating that tha next
+             * label is an entropy value
+             */
+            next_label_is_entropy = 1;
+        }
+        else
+        {
+            /*
+             * XOR the label values in the stack together to
+             * build up the hash value
+             */
+            hash ^= value;
+        }
+    }
+
+    /*
+     * check the top nibble for v4 and v6
+     */
+    hdr++;
+
+    switch (((u8*)hdr)[0] >> 4)
+    {
+    case 4:
+        /* incorporate the v4 flow-hash */
+        hash ^= ip4_compute_flow_hash ((const ip4_header_t *)hdr,
+                                       IP_FLOW_HASH_DEFAULT);
+        break;
+    case 6:
+        /* incorporate the v6 flow-hash */
+        hash ^= ip6_compute_flow_hash ((const ip6_header_t *)hdr,
+                                       IP_FLOW_HASH_DEFAULT);
+        break;
+    default:
+        break;
+    }
+
+    return (hash);
 }
 
 static inline uword
diff --git a/src/vnet/mpls/mpls_types.h b/src/vnet/mpls/mpls_types.h
index b1075cdda57..f1c3191e00c 100644
--- a/src/vnet/mpls/mpls_types.h
+++ b/src/vnet/mpls/mpls_types.h
@@ -30,6 +30,7 @@
 #define MPLS_IETF_IMPLICIT_NULL_LABEL        0x00003
 #define MPLS_IETF_ELI_LABEL                  0x00007
 #define MPLS_IETF_GAL_LABEL                  0x0000D
+#define MPLS_IETF_ENTROPY_LABEL              0x0000E
 
 #define MPLS_IETF_IPV4_EXPLICIT_NULL_STRING          "ip4-explicit-null"
 #define MPLS_IETF_IPV4_EXPLICIT_NULL_BRIEF_STRING    "e-nul"
diff --git a/test/patches/scapy-2.3.3/mpls.py.patch b/test/patches/scapy-2.3.3/mpls.py.patch
index 5c819110ddc..f63a70a3cd7 100644
--- a/test/patches/scapy-2.3.3/mpls.py.patch
+++ b/test/patches/scapy-2.3.3/mpls.py.patch
@@ -11,3 +11,8 @@ index 640a0c5..6af1d4a 100644
             ip_version = (ord(payload[0]) >> 4) & 0xF
             if ip_version == 4:
                 return IP
+@@ -27,3 +29,4 @@ class MPLS(Packet):
+ 
+ bind_layers(Ether, MPLS, type=0x8847)
+ bind_layers(GRE, MPLS, proto=0x8847)
++bind_layers(MPLS, MPLS, s=0)
diff --git a/test/test_ip4.py b/test/test_ip4.py
index 3fe61e266be..ddfd2187490 100644
--- a/test/test_ip4.py
+++ b/test/test_ip4.py
@@ -6,12 +6,13 @@ import unittest
 from framework import VppTestCase, VppTestRunner
 from vpp_sub_interface import VppSubInterface, VppDot1QSubint, VppDot1ADSubint
 from vpp_ip_route import VppIpRoute, VppRoutePath, VppIpMRoute, \
-    VppMRoutePath, MRouteItfFlags, MRouteEntryFlags
+    VppMRoutePath, MRouteItfFlags, MRouteEntryFlags, VppMplsIpBind
 
 from scapy.packet import Raw
 from scapy.layers.l2 import Ether, Dot1Q, ARP
 from scapy.layers.inet import IP, UDP, ICMP, icmptypes, icmpcodes
 from util import ppp
+from scapy.contrib.mpls import MPLS
 
 
 class TestIPv4(VppTestCase):
@@ -778,10 +779,12 @@ class TestIPLoadBalance(VppTestCase):
             i.admin_up()
             i.config_ip4()
             i.resolve_arp()
+            i.enable_mpls()
 
     def tearDown(self):
         super(TestIPLoadBalance, self).tearDown()
         for i in self.pg_interfaces:
+            i.disable_mpls()
             i.unconfig_ip4()
             i.admin_down()
 
@@ -799,24 +802,37 @@ class TestIPLoadBalance(VppTestCase):
         #
         # An array of packets that differ only in the destination port
         #
-        port_pkts = []
+        port_ip_pkts = []
+        port_mpls_pkts = []
 
         #
         # An array of packets that differ only in the source address
         #
-        src_pkts = []
+        src_ip_pkts = []
+        src_mpls_pkts = []
 
         for ii in range(65):
-            port_pkts.append((Ether(src=self.pg0.remote_mac,
-                                    dst=self.pg0.local_mac) /
-                              IP(dst="10.0.0.1", src="20.0.0.1") /
-                              UDP(sport=1234, dport=1234 + ii) /
-                              Raw('\xa5' * 100)))
-            src_pkts.append((Ether(src=self.pg0.remote_mac,
-                                   dst=self.pg0.local_mac) /
-                             IP(dst="10.0.0.1", src="20.0.0.%d" % ii) /
-                             UDP(sport=1234, dport=1234) /
-                             Raw('\xa5' * 100)))
+            port_ip_hdr = (IP(dst="10.0.0.1", src="20.0.0.1") /
+                           UDP(sport=1234, dport=1234 + ii) /
+                           Raw('\xa5' * 100))
+            port_ip_pkts.append((Ether(src=self.pg0.remote_mac,
+                                       dst=self.pg0.local_mac) /
+                                 port_ip_hdr))
+            port_mpls_pkts.append((Ether(src=self.pg0.remote_mac,
+                                         dst=self.pg0.local_mac) /
+                                   MPLS(label=66, ttl=2) /
+                                   port_ip_hdr))
+
+            src_ip_hdr = (IP(dst="10.0.0.1", src="20.0.0.%d" % ii) /
+                          UDP(sport=1234, dport=1234) /
+                          Raw('\xa5' * 100))
+            src_ip_pkts.append((Ether(src=self.pg0.remote_mac,
+                                      dst=self.pg0.local_mac) /
+                                src_ip_hdr))
+            src_mpls_pkts.append((Ether(src=self.pg0.remote_mac,
+                                        dst=self.pg0.local_mac) /
+                                  MPLS(label=66, ttl=2) /
+                                  src_ip_hdr))
 
         route_10_0_0_1 = VppIpRoute(self, "10.0.0.1", 32,
                                     [VppRoutePath(self.pg1.remote_ip4,
@@ -825,6 +841,9 @@ class TestIPLoadBalance(VppTestCase):
                                                   self.pg2.sw_if_index)])
         route_10_0_0_1.add_vpp_config()
 
+        binding = VppMplsIpBind(self, 66, "10.0.0.1", 32)
+        binding.add_vpp_config()
+
         #
         # inject the packet on pg0 - expect load-balancing across the 2 paths
         #  - since the default hash config is to use IP src,dst and port
@@ -834,9 +853,13 @@ class TestIPLoadBalance(VppTestCase):
         # be guaranteed. But wuth 64 different packets we do expect some
         # balancing. So instead just ensure there is traffic on each link.
         #
-        self.send_and_expect_load_balancing(self.pg0, port_pkts,
+        self.send_and_expect_load_balancing(self.pg0, port_ip_pkts,
                                             [self.pg1, self.pg2])
-        self.send_and_expect_load_balancing(self.pg0, src_pkts,
+        self.send_and_expect_load_balancing(self.pg0, src_ip_pkts,
+                                            [self.pg1, self.pg2])
+        self.send_and_expect_load_balancing(self.pg0, port_mpls_pkts,
+                                            [self.pg1, self.pg2])
+        self.send_and_expect_load_balancing(self.pg0, src_mpls_pkts,
                                             [self.pg1, self.pg2])
 
         #
@@ -846,14 +869,16 @@ class TestIPLoadBalance(VppTestCase):
         #
         self.vapi.set_ip_flow_hash(0, src=1, dst=1, sport=0, dport=0)
 
-        self.send_and_expect_load_balancing(self.pg0, src_pkts,
+        self.send_and_expect_load_balancing(self.pg0, src_ip_pkts,
+                                            [self.pg1, self.pg2])
+        self.send_and_expect_load_balancing(self.pg0, src_mpls_pkts,
                                             [self.pg1, self.pg2])
 
-        self.pg0.add_stream(port_pkts)
+        self.pg0.add_stream(port_ip_pkts)
         self.pg_enable_capture(self.pg_interfaces)
         self.pg_start()
 
-        rx = self.pg2.get_capture(len(port_pkts))
+        rx = self.pg2.get_capture(len(port_ip_pkts))
 
         #
         # change the flow hash config back to defaults
diff --git a/test/test_ip6.py b/test/test_ip6.py
index ebeffe20461..700b3344a9e 100644
--- a/test/test_ip6.py
+++ b/test/test_ip6.py
@@ -7,7 +7,8 @@ from framework import VppTestCase, VppTestRunner
 from vpp_sub_interface import VppSubInterface, VppDot1QSubint
 from vpp_pg_interface import is_ipv6_misc
 from vpp_ip_route import VppIpRoute, VppRoutePath, find_route, VppIpMRoute, \
-    VppMRoutePath, MRouteItfFlags, MRouteEntryFlags
+    VppMRoutePath, MRouteItfFlags, MRouteEntryFlags, VppMplsIpBind, \
+    VppMplsRoute
 from vpp_neighbor import find_nbr, VppNeighbor
 
 from scapy.packet import Raw
@@ -21,6 +22,7 @@ from util import ppp
 from scapy.utils6 import in6_getnsma, in6_getnsmac, in6_ptop, in6_islladdr, \
     in6_mactoifaceid, in6_ismaddr
 from scapy.utils import inet_pton, inet_ntop
+from scapy.contrib.mpls import MPLS
 
 
 def mk_ll_addr(mac):
@@ -1145,12 +1147,14 @@ class TestIP6LoadBalance(VppTestCase):
             i.admin_up()
             i.config_ip6()
             i.resolve_ndp()
+            i.enable_mpls()
 
     def tearDown(self):
         super(TestIP6LoadBalance, self).tearDown()
         for i in self.pg_interfaces:
             i.unconfig_ip6()
             i.admin_down()
+            i.disable_mpls()
 
     def send_and_expect_load_balancing(self, input, pkts, outputs):
         input.add_stream(pkts)
@@ -1160,31 +1164,69 @@ class TestIP6LoadBalance(VppTestCase):
             rx = oo._get_capture(1)
             self.assertNotEqual(0, len(rx))
 
+    def send_and_expect_one_itf(self, input, pkts, itf):
+        input.add_stream(pkts)
+        self.pg_enable_capture(self.pg_interfaces)
+        self.pg_start()
+        rx = itf.get_capture(len(pkts))
+
     def test_ip6_load_balance(self):
         """ IPv6 Load-Balancing """
 
         #
         # An array of packets that differ only in the destination port
+        #  - IP only
+        #  - MPLS EOS
+        #  - MPLS non-EOS
+        #  - MPLS non-EOS with an entropy label
         #
-        port_pkts = []
+        port_ip_pkts = []
+        port_mpls_pkts = []
+        port_mpls_neos_pkts = []
+        port_ent_pkts = []
 
         #
         # An array of packets that differ only in the source address
         #
-        src_pkts = []
+        src_ip_pkts = []
+        src_mpls_pkts = []
 
         for ii in range(65):
-            port_pkts.append((Ether(src=self.pg0.remote_mac,
-                                    dst=self.pg0.local_mac) /
-                              IPv6(dst="3000::1", src="3000:1::1") /
-                              UDP(sport=1234, dport=1234 + ii) /
-                              Raw('\xa5' * 100)))
-            src_pkts.append((Ether(src=self.pg0.remote_mac,
-                                   dst=self.pg0.local_mac) /
-                             IPv6(dst="3000::1", src="3000:1::%d" % ii) /
-                             UDP(sport=1234, dport=1234) /
-                             Raw('\xa5' * 100)))
-
+            port_ip_hdr = (IPv6(dst="3000::1", src="3000:1::1") /
+                           UDP(sport=1234, dport=1234 + ii) /
+                           Raw('\xa5' * 100))
+            port_ip_pkts.append((Ether(src=self.pg0.remote_mac,
+                                       dst=self.pg0.local_mac) /
+                                 port_ip_hdr))
+            port_mpls_pkts.append((Ether(src=self.pg0.remote_mac,
+                                         dst=self.pg0.local_mac) /
+                                   MPLS(label=66, ttl=2) /
+                                   port_ip_hdr))
+            port_mpls_neos_pkts.append((Ether(src=self.pg0.remote_mac,
+                                              dst=self.pg0.local_mac) /
+                                        MPLS(label=67, ttl=2) /
+                                        MPLS(label=77, ttl=2) /
+                                        port_ip_hdr))
+            port_ent_pkts.append((Ether(src=self.pg0.remote_mac,
+                                        dst=self.pg0.local_mac) /
+                                  MPLS(label=67, ttl=2) /
+                                  MPLS(label=14, ttl=2) /
+                                  MPLS(label=999, ttl=2) /
+                                  port_ip_hdr))
+            src_ip_hdr = (IPv6(dst="3000::1", src="3000:1::%d" % ii) /
+                          UDP(sport=1234, dport=1234) /
+                          Raw('\xa5' * 100))
+            src_ip_pkts.append((Ether(src=self.pg0.remote_mac,
+                                      dst=self.pg0.local_mac) /
+                                src_ip_hdr))
+            src_mpls_pkts.append((Ether(src=self.pg0.remote_mac,
+                                        dst=self.pg0.local_mac) /
+                                  MPLS(label=66, ttl=2) /
+                                  src_ip_hdr))
+
+        #
+        # A route for the IP pacekts
+        #
         route_3000_1 = VppIpRoute(self, "3000::1", 128,
                                   [VppRoutePath(self.pg1.remote_ip6,
                                                 self.pg1.sw_if_index,
@@ -1196,6 +1238,26 @@ class TestIP6LoadBalance(VppTestCase):
         route_3000_1.add_vpp_config()
 
         #
+        # a local-label for the EOS packets
+        #
+        binding = VppMplsIpBind(self, 66, "3000::1", 128, is_ip6=1)
+        binding.add_vpp_config()
+
+        #
+        # An MPLS route for the non-EOS packets
+        #
+        route_67 = VppMplsRoute(self, 67, 0,
+                                [VppRoutePath(self.pg1.remote_ip6,
+                                              self.pg1.sw_if_index,
+                                              labels=[67],
+                                              is_ip6=1),
+                                 VppRoutePath(self.pg2.remote_ip6,
+                                              self.pg2.sw_if_index,
+                                              labels=[67],
+                                              is_ip6=1)])
+        route_67.add_vpp_config()
+
+        #
         # inject the packet on pg0 - expect load-balancing across the 2 paths
         #  - since the default hash config is to use IP src,dst and port
         #    src,dst
@@ -1204,26 +1266,35 @@ class TestIP6LoadBalance(VppTestCase):
         # be guaranteed. But wuth 64 different packets we do expect some
         # balancing. So instead just ensure there is traffic on each link.
         #
-        self.send_and_expect_load_balancing(self.pg0, port_pkts,
+        self.send_and_expect_load_balancing(self.pg0, port_ip_pkts,
                                             [self.pg1, self.pg2])
-        self.send_and_expect_load_balancing(self.pg0, src_pkts,
+        self.send_and_expect_load_balancing(self.pg0, src_ip_pkts,
+                                            [self.pg1, self.pg2])
+        self.send_and_expect_load_balancing(self.pg0, port_mpls_pkts,
+                                            [self.pg1, self.pg2])
+        self.send_and_expect_load_balancing(self.pg0, src_mpls_pkts,
+                                            [self.pg1, self.pg2])
+        self.send_and_expect_load_balancing(self.pg0, port_mpls_neos_pkts,
                                             [self.pg1, self.pg2])
 
         #
+        # The packets with Entropy label in should not load-balance,
+        # since the Entorpy value is fixed.
+        #
+        self.send_and_expect_one_itf(self.pg0, port_ent_pkts, self.pg1)
+
+        #
         # change the flow hash config so it's only IP src,dst
         #  - now only the stream with differing source address will
         #    load-balance
         #
         self.vapi.set_ip_flow_hash(0, is_ip6=1, src=1, dst=1, sport=0, dport=0)
 
-        self.send_and_expect_load_balancing(self.pg0, src_pkts,
+        self.send_and_expect_load_balancing(self.pg0, src_ip_pkts,
                                             [self.pg1, self.pg2])
-
-        self.pg0.add_stream(port_pkts)
-        self.pg_enable_capture(self.pg_interfaces)
-        self.pg_start()
-
-        rx = self.pg2.get_capture(len(port_pkts))
+        self.send_and_expect_load_balancing(self.pg0, src_mpls_pkts,
+                                            [self.pg1, self.pg2])
+        self.send_and_expect_one_itf(self.pg0, port_ip_pkts, self.pg2)
 
         #
         # change the flow hash config back to defaults