BIER in non-MPLS netowrks

as decsribed in section 2.2
  ihttps://tools.ietf.org/html/draft-ietf-bier-mpls-encapsulation-10
with BIFT encoding from:
  https://tools.ietf.org/html/draft-wijnandsxu-bier-non-mpls-bift-encoding-00

changes:
1 - introduce the new BIFT lookup table. BIER tables that have an associated
    MPLS label are added to the MPLS-FIB. Those that don't are added to the
    BIER table
2 - BIER routes that have no associated output MPLS label will add a BIFT label.
3 - The BIER FMask has a path-list as a member to resolve via any possible path.

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

4 files changed, 230 insertions, 35 deletions

diff --git a/test/patches/scapy-2.3.3/bier.patch b/test/patches/scapy-2.3.3/bier.patch
index 024805d0501..50814d41315 100644
--- a/test/patches/scapy-2.3.3/bier.patch
+++ b/test/patches/scapy-2.3.3/bier.patch
@@ -3,7 +3,7 @@ new file mode 100644
 index 0000000..e173cdb
 --- /dev/null
 +++ b/scapy/contrib/bier.py
-@@ -0,0 +1,39 @@
+@@ -0,0 +1,53 @@
 +# http://trac.secdev.org/scapy/ticket/31
 +
 +# scapy.contrib.description = MPLS
@@ -11,7 +11,7 @@ index 0000000..e173cdb
 +
 +from scapy.packet import *
 +from scapy.fields import *
-+from scapy.layers.inet import IP
++from scapy.layers.inet import IP, UDP
 +from scapy.layers.inet6 import IPv6
 +
 +class BIERLength:
@@ -20,12 +20,25 @@ index 0000000..e173cdb
 +   BIER_LEN_256 = 2
 +
 +
-+
 +BIERnhcls = {  1: "MPLS",
 +               2: "MPLS",
 +               4: "IPv4",
 +               5: "IPv6" }
 +
++
++class BIFT(Packet):
++   name = "BIFT"
++   fields_desc =  [ BitField("bsl", 0, 4),
++                    BitField("sd", 0, 8),
++                    BitField("set", 0, 8),
++                    BitField("cos", 0, 3),
++                    BitField("s", 1, 1),
++                    ByteField("ttl", 0)  ]
++
++   def guess_payload_class(self, payload):
++      return BIER
++
++
 +class BIER(Packet):
 +   name = "BIER"
 +   fields_desc =  [ BitField("id", 5, 4),
@@ -43,3 +56,4 @@ index 0000000..e173cdb
 +
 +bind_layers(BIER, IP,   Proto=4)
 +bind_layers(BIER, IPv6, Proto=5)
++bind_layers(UDP, BIFT, dport=8138)
diff --git a/test/test_bier.py b/test/test_bier.py
index 1a4567bd656..48d0a297ca6 100644
--- a/test/test_bier.py
+++ b/test/test_bier.py
@@ -8,6 +8,7 @@ from vpp_ip_route import VppIpRoute, VppRoutePath, VppMplsRoute, \
     VppMplsTable, VppIpMRoute, VppMRoutePath, VppIpTable, \
     MRouteEntryFlags, MRouteItfFlags, MPLS_LABEL_INVALID, DpoProto
 from vpp_bier import *
+from vpp_udp_encap import *
 
 from scapy.packet import Raw
 from scapy.layers.l2 import Ether
@@ -78,6 +79,7 @@ class TestBier(VppTestCase):
         self.pg_enable_capture(self.pg_interfaces)
         self.pg_start()
         rx = output.get_capture(len(pkts))
+        return rx
 
     def test_bier_midpoint(self):
         """BIER midpoint"""
@@ -119,7 +121,9 @@ class TestBier(VppTestCase):
                                                       labels=[2000+i])]))
             nh_routes[-1].add_vpp_config()
 
-            bier_routes.append(VppBierRoute(self, bti, i, nh, 100+i))
+            bier_routes.append(VppBierRoute(self, bti, i,
+                                            [VppRoutePath(nh, 0xffffffff,
+                                                          labels=[100+i])]))
             bier_routes[-1].add_vpp_config()
 
         #
@@ -150,6 +154,7 @@ class TestBier(VppTestCase):
 
             blabel = olabel[MPLS].payload
             self.assertEqual(blabel.label, 100+bp)
+            self.assertEqual(blabel.ttl, 254)
 
             bier_hdr = blabel[MPLS].payload
 
@@ -203,8 +208,12 @@ class TestBier(VppTestCase):
         ip_route_1.add_vpp_config()
         ip_route_2.add_vpp_config()
 
-        bier_route_1 = VppBierRoute(self, bti, 1, nh1, 101)
-        bier_route_2 = VppBierRoute(self, bti, 2, nh2, 102)
+        bier_route_1 = VppBierRoute(self, bti, 1,
+                                    [VppRoutePath(nh1, 0xffffffff,
+                                                  labels=[101])])
+        bier_route_2 = VppBierRoute(self, bti, 2,
+                                    [VppRoutePath(nh2, 0xffffffff,
+                                                  labels=[102])])
         bier_route_1.add_vpp_config()
         bier_route_2.add_vpp_config()
 
@@ -231,7 +240,7 @@ class TestBier(VppTestCase):
         route_ing_232_1_1_1.add_vpp_config()
 
         #
-        # inject a packet an IP. We expect it to be BIER encapped,
+        # inject an IP packet. We expect it to be BIER encapped and
         # replicated.
         #
         p = (Ether(dst=self.pg0.local_mac,
@@ -245,6 +254,29 @@ class TestBier(VppTestCase):
 
         rx = self.pg1.get_capture(2)
 
+        #
+        # Encap Stack is; eth, MPLS, MPLS, BIER
+        #
+        igp_mpls = rx[0][MPLS]
+        self.assertEqual(igp_mpls.label, 2001)
+        self.assertEqual(igp_mpls.ttl, 64)
+        self.assertEqual(igp_mpls.s, 0)
+        bier_mpls = igp_mpls[MPLS].payload
+        self.assertEqual(bier_mpls.label, 101)
+        self.assertEqual(bier_mpls.ttl, 64)
+        self.assertEqual(bier_mpls.s, 1)
+        self.assertEqual(rx[0][BIER].length, 2)
+
+        igp_mpls = rx[1][MPLS]
+        self.assertEqual(igp_mpls.label, 2002)
+        self.assertEqual(igp_mpls.ttl, 64)
+        self.assertEqual(igp_mpls.s, 0)
+        bier_mpls = igp_mpls[MPLS].payload
+        self.assertEqual(bier_mpls.label, 102)
+        self.assertEqual(bier_mpls.ttl, 64)
+        self.assertEqual(bier_mpls.s, 1)
+        self.assertEqual(rx[0][BIER].length, 2)
+
     def test_bier_tail(self):
         """BIER Tail"""
 
@@ -264,8 +296,10 @@ class TestBier(VppTestCase):
         #
         # BIER route in table that's for-us
         #
-        bier_route_1 = VppBierRoute(self, bti, 1, "0.0.0.0", 0,
-                                    disp_table=8)
+        bier_route_1 = VppBierRoute(self, bti, 1,
+                                    [VppRoutePath("0.0.0.0",
+                                                  0xffffffff,
+                                                  nh_table_id=8)])
         bier_route_1.add_vpp_config()
 
         #
@@ -344,9 +378,10 @@ class TestBier(VppTestCase):
         # BIER route in table that's for-us, resolving through
         # disp table 8.
         #
-        bier_route_1 = VppBierRoute(self, bti, 1, "0.0.0.0",
-                                    MPLS_LABEL_INVALID,
-                                    disp_table=8)
+        bier_route_1 = VppBierRoute(self, bti, 1,
+                                    [VppRoutePath("0.0.0.0",
+                                                  0xffffffff,
+                                                  nh_table_id=8)])
         bier_route_1.add_vpp_config()
 
         #
@@ -383,7 +418,155 @@ class TestBier(VppTestCase):
              IP(src="1.1.1.1", dst="232.1.1.1") /
              UDP(sport=1234, dport=1234))
 
-        self.send_and_expect(self.pg0, p*65, self.pg1)
+        rx = self.send_and_expect(self.pg0, p*65, self.pg1)
+
+        #
+        # should be IP
+        #
+        self.assertEqual(rx[0][IP].src, "1.1.1.1")
+        self.assertEqual(rx[0][IP].dst, "232.1.1.1")
+
+    def test_bier_head_o_udp(self):
+        """BIER head over UDP"""
+
+        #
+        # Add a BIER table for sub-domain 1, set 0, and BSL 256
+        #
+        bti = VppBierTableID(1, 0, BIERLength.BIER_LEN_256)
+        bt = VppBierTable(self, bti, 77)
+        bt.add_vpp_config()
+
+        #
+        # 1 bit positions via 1 next hops
+        #
+        nh1 = "10.0.0.1"
+        ip_route = VppIpRoute(self, nh1, 32,
+                              [VppRoutePath(self.pg1.remote_ip4,
+                                            self.pg1.sw_if_index,
+                                            labels=[2001])])
+        ip_route.add_vpp_config()
+
+        udp_encap = VppUdpEncap(self, 4,
+                                self.pg0.local_ip4,
+                                nh1,
+                                330, 8138)
+        udp_encap.add_vpp_config()
+
+        bier_route = VppBierRoute(self, bti, 1,
+                                  [VppRoutePath("0.0.0.0",
+                                                0xFFFFFFFF,
+                                                is_udp_encap=1,
+                                                next_hop_id=4)])
+        bier_route.add_vpp_config()
+
+        #
+        # An imposition object with all bit-positions set
+        #
+        bi = VppBierImp(self, bti, 333, chr(0xff) * 32)
+        bi.add_vpp_config()
+
+        #
+        # Add a multicast route that will forward into the BIER doamin
+        #
+        route_ing_232_1_1_1 = VppIpMRoute(
+            self,
+            "0.0.0.0",
+            "232.1.1.1", 32,
+            MRouteEntryFlags.MFIB_ENTRY_FLAG_NONE,
+            paths=[VppMRoutePath(self.pg0.sw_if_index,
+                                 MRouteItfFlags.MFIB_ITF_FLAG_ACCEPT),
+                   VppMRoutePath(0xffffffff,
+                                 MRouteItfFlags.MFIB_ITF_FLAG_FORWARD,
+                                 proto=DpoProto.DPO_PROTO_BIER,
+                                 bier_imp=bi.bi_index)])
+        route_ing_232_1_1_1.add_vpp_config()
+
+        #
+        # inject a packet an IP. We expect it to be BIER and UDP encapped,
+        #
+        p = (Ether(dst=self.pg0.local_mac,
+                   src=self.pg0.remote_mac) /
+             IP(src="1.1.1.1", dst="232.1.1.1") /
+             UDP(sport=1234, dport=1234))
+
+        self.pg0.add_stream([p])
+        self.pg_enable_capture(self.pg_interfaces)
+        self.pg_start()
+
+        rx = self.pg1.get_capture(1)
+
+        #
+        # Encap Stack is, eth, IP, UDP, BIFT, BIER
+        #
+        self.assertEqual(rx[0][IP].src, self.pg0.local_ip4)
+        self.assertEqual(rx[0][IP].dst, nh1)
+        self.assertEqual(rx[0][UDP].sport, 330)
+        self.assertEqual(rx[0][UDP].dport, 8138)
+        self.assertEqual(rx[0][BIFT].bsl, 2)
+        self.assertEqual(rx[0][BIFT].sd, 1)
+        self.assertEqual(rx[0][BIFT].set, 0)
+        self.assertEqual(rx[0][BIFT].ttl, 64)
+        self.assertEqual(rx[0][BIER].length, 2)
+
+    def test_bier_tail_o_udp(self):
+        """BIER Tail over UDP"""
+
+        #
+        # Add a BIER table for sub-domain 0, set 0, and BSL 256
+        #
+        bti = VppBierTableID(1, 0, BIERLength.BIER_LEN_256)
+        bt = VppBierTable(self, bti, MPLS_LABEL_INVALID)
+        bt.add_vpp_config()
+
+        #
+        # disposition table
+        #
+        bdt = VppBierDispTable(self, 8)
+        bdt.add_vpp_config()
+
+        #
+        # BIER route in table that's for-us
+        #
+        bier_route_1 = VppBierRoute(self, bti, 1,
+                                    [VppRoutePath("0.0.0.0",
+                                                  0xffffffff,
+                                                  nh_table_id=8)])
+        bier_route_1.add_vpp_config()
+
+        #
+        # An entry in the disposition table
+        #
+        bier_de_1 = VppBierDispEntry(self, bdt.id, 99,
+                                     BIER_HDR_PAYLOAD.BIER_HDR_PROTO_IPV4,
+                                     "0.0.0.0", 0, rpf_id=8192)
+        bier_de_1.add_vpp_config()
+
+        #
+        # A multicast route to forward post BIER disposition
+        #
+        route_eg_232_1_1_1 = VppIpMRoute(
+            self,
+            "0.0.0.0",
+            "232.1.1.1", 32,
+            MRouteEntryFlags.MFIB_ENTRY_FLAG_NONE,
+            paths=[VppMRoutePath(self.pg1.sw_if_index,
+                                 MRouteItfFlags.MFIB_ITF_FLAG_FORWARD)])
+        route_eg_232_1_1_1.add_vpp_config()
+        route_eg_232_1_1_1.update_rpf_id(8192)
+
+        #
+        # A packet with all bits set gets spat out to BP:1
+        #
+        p = (Ether(dst=self.pg0.local_mac, src=self.pg0.remote_mac) /
+             IP(src=self.pg0.remote_ip4, dst=self.pg0.local_ip4) /
+             UDP(sport=333, dport=8138) /
+             BIFT(sd=1, set=0, bsl=2, ttl=255) /
+             BIER(length=BIERLength.BIER_LEN_256, BFRID=99) /
+             IP(src="1.1.1.1", dst="232.1.1.1") /
+             UDP(sport=1234, dport=1234) /
+             Raw())
+
+        rx = self.send_and_expect(self.pg0, [p], self.pg1)
 
 
 if __name__ == '__main__':
diff --git a/test/vpp_bier.py b/test/vpp_bier.py
index 58c4f7248da..328d4f03eb5 100644
--- a/test/vpp_bier.py
+++ b/test/vpp_bier.py
@@ -4,6 +4,7 @@
 
 import socket
 from vpp_object import VppObject
+from vpp_ip_route import MPLS_LABEL_INVALID, VppRoutePath
 
 
 class BIER_HDR_PAYLOAD:
@@ -18,7 +19,7 @@ class BIER_HDR_PAYLOAD:
 
 
 class VppBierTableID():
-    def __init__(self, set_id, sub_domain_id, hdr_len_id):
+    def __init__(self, sub_domain_id, set_id, hdr_len_id):
         self.set_id = set_id
         self.sub_domain_id = sub_domain_id
         self.hdr_len_id = hdr_len_id
@@ -113,22 +114,17 @@ class VppBierRoute(VppObject):
     BIER route
     """
 
-    def __init__(self, test, tbl_id, bp, nh, out_label,
-                 disp_table=0):
+    def __init__(self, test, tbl_id, bp, paths):
         self._test = test
         self.tbl_id = tbl_id
-        self.out_label = out_label
         self.bp = bp
-        self.disp_table = disp_table
-        self.nh = socket.inet_pton(socket.AF_INET, nh)
+        self.paths = paths
 
     def add_vpp_config(self):
         self._test.vapi.bier_route_add_del(
             self.tbl_id,
             self.bp,
-            self.nh,
-            self.out_label,
-            self.disp_table,
+            self.paths,
             is_add=1)
         self._test.registry.register(self, self._test.logger)
 
@@ -136,9 +132,7 @@ class VppBierRoute(VppObject):
         self._test.vapi.bier_route_add_del(
             self.tbl_id,
             self.bp,
-            self.nh,
-            self.out_label,
-            self.disp_table,
+            self.paths,
             is_add=0)
 
     def __str__(self):
diff --git a/test/vpp_papi_provider.py b/test/vpp_papi_provider.py
index f8bca821631..c4b1601eb42 100644
--- a/test/vpp_papi_provider.py
+++ b/test/vpp_papi_provider.py
@@ -2701,24 +2701,28 @@ class VppPapiProvider(object):
     def bier_route_add_del(self,
                            bti,
                            bp,
-                           next_hop,
-                           next_hop_label,
-                           next_hop_table_id,
-                           next_hop_is_ip4=1,
+                           paths,
                            is_add=1):
         """ BIER Route add/del """
+        br_paths = []
+        for p in paths:
+            br_paths.append({'next_hop': p.nh_addr,
+                             'weight': 1,
+                             'afi': 0,
+                             'preference': 0,
+                             'table_id': p.nh_table_id,
+                             'next_hop_id': p.next_hop_id,
+                             'is_udp_encap': p.is_udp_encap,
+                             'n_labels': len(p.nh_labels),
+                             'label_stack': p.nh_labels})
         return self.api(
             self.papi.bier_route_add_del,
             {'br_tbl_id': {"bt_set": bti.set_id,
                            "bt_sub_domain": bti.sub_domain_id,
                            "bt_hdr_len_id": bti.hdr_len_id},
              'br_bp': bp,
-             'br_n_paths': 1,
-             'br_paths': [{'next_hop': next_hop,
-                           'afi': 0,
-                           'n_labels': 1,
-                           'table_id': next_hop_table_id,
-                           'label_stack': [next_hop_label]}],
+             'br_n_paths': len(br_paths),
+             'br_paths': br_paths,
              'br_is_add': is_add})
 
     def bier_route_dump(self, bti):