VPP-1448: Fix error when recurse on down the trie.

Change-Id: Idfed8243643780d3f52dfe6e6ec621c440daa6ae
Signed-off-by: mu.duojiao <mu.duojiao@zte.com.cn>
(cherry picked from commit 59a829533c1345945dc1b6decc3afe29494e85cd)

2 files changed, 69 insertions, 21 deletions

diff --git a/src/vnet/ip/ip4_mtrie.c b/src/vnet/ip/ip4_mtrie.c
index 6df1f8da179..a7f4758c234 100755
--- a/src/vnet/ip/ip4_mtrie.c
+++ b/src/vnet/ip/ip4_mtrie.c
@@ -369,10 +369,10 @@ set_leaf (ip4_fib_mtrie_t * m,
 	  old_ply->n_non_empty_leafs -=
 	    ip4_fib_mtrie_leaf_is_non_empty (old_ply, dst_byte);
 
-	  new_leaf = ply_create (m, old_leaf,
-				 clib_max (old_ply->dst_address_bits_of_leaves
-					   [dst_byte], ply_base_len),
-				 ply_base_len);
+	  new_leaf =
+	    ply_create (m, old_leaf,
+			old_ply->dst_address_bits_of_leaves[dst_byte],
+			ply_base_len);
 	  new_ply = get_next_ply_for_leaf (m, new_leaf);
 
 	  /* Refetch since ply_create may move pool. */
@@ -492,10 +492,10 @@ set_root_leaf (ip4_fib_mtrie_t * m,
       if (ip4_fib_mtrie_leaf_is_terminal (old_leaf))
 	{
 	  /* There is a leaf occupying the slot. Replace it with a new ply */
-	  new_leaf = ply_create (m, old_leaf,
-				 clib_max (old_ply->dst_address_bits_of_leaves
-					   [dst_byte], ply_base_len),
-				 ply_base_len);
+	  new_leaf =
+	    ply_create (m, old_leaf,
+			old_ply->dst_address_bits_of_leaves[dst_byte],
+			ply_base_len);
 	  new_ply = get_next_ply_for_leaf (m, new_leaf);
 
 	  __sync_val_compare_and_swap (&old_ply->leaves[dst_byte], old_leaf,
@@ -712,24 +712,23 @@ format_ip4_fib_mtrie_leaf (u8 * s, va_list * va)
   return s;
 }
 
-#define FORMAT_PLY(s, _p, _i, _base_address, _ply_max_len, _indent)     \
+#define FORMAT_PLY(s, _p, _a, _i, _base_address, _ply_max_len, _indent) \
 ({                                                                      \
   u32 a, ia_length;                                                     \
   ip4_address_t ia;                                                     \
   ip4_fib_mtrie_leaf_t _l = p->leaves[(_i)];                            \
                                                                         \
-  a = (_base_address) + ((_i) << (32 - (_ply_max_len)));                \
+  a = (_base_address) + ((_a) << (32 - (_ply_max_len)));                \
   ia.as_u32 = clib_host_to_net_u32 (a);                                 \
   ia_length = (_p)->dst_address_bits_of_leaves[(_i)];                   \
-  s = format (s, "\n%U%20U %U",                                         \
-              format_white_space, (_indent) + 2,                        \
+  s = format (s, "\n%U%U %U",                                           \
+              format_white_space, (_indent) + 4,                        \
               format_ip4_address_and_length, &ia, ia_length,            \
               format_ip4_fib_mtrie_leaf, _l);                           \
                                                                         \
   if (ip4_fib_mtrie_leaf_is_next_ply (_l))                              \
-    s = format (s, "\n%U%U",                                            \
-                format_white_space, (_indent) + 2,                      \
-                format_ip4_fib_mtrie_ply, m, a,                         \
+    s = format (s, "\n%U",                                              \
+                format_ip4_fib_mtrie_ply, m, a, (_indent) + 8,          \
                 ip4_fib_mtrie_leaf_get_next_ply_index (_l));            \
   s;                                                                    \
 })
@@ -739,21 +738,20 @@ format_ip4_fib_mtrie_ply (u8 * s, va_list * va)
 {
   ip4_fib_mtrie_t *m = va_arg (*va, ip4_fib_mtrie_t *);
   u32 base_address = va_arg (*va, u32);
+  u32 indent = va_arg (*va, u32);
   u32 ply_index = va_arg (*va, u32);
   ip4_fib_mtrie_8_ply_t *p;
-  u32 indent;
   int i;
 
   p = pool_elt_at_index (ip4_ply_pool, ply_index);
-  indent = format_get_indent (s);
-  s = format (s, "ply index %d, %d non-empty leaves", ply_index,
-	      p->n_non_empty_leafs);
+  s = format (s, "%Uply index %d, %d non-empty leaves",
+	      format_white_space, indent, ply_index, p->n_non_empty_leafs);
 
   for (i = 0; i < ARRAY_LEN (p->leaves); i++)
     {
       if (ip4_fib_mtrie_leaf_is_non_empty (p, i))
 	{
-	  s = FORMAT_PLY (s, p, i, base_address,
+	  s = FORMAT_PLY (s, p, i, i, base_address,
 			  p->dst_address_bits_base + 8, indent);
 	}
     }
@@ -789,7 +787,7 @@ format_ip4_fib_mtrie (u8 * s, va_list * va)
 
 	  if (p->dst_address_bits_of_leaves[slot] > 0)
 	    {
-	      s = FORMAT_PLY (s, p, slot, base_address, 16, 2);
+	      s = FORMAT_PLY (s, p, i, slot, base_address, 16, 0);
 	    }
 	}
     }
diff --git a/test/test_ip4.py b/test/test_ip4.py
index be443198595..3f961d591e1 100644
--- a/test/test_ip4.py
+++ b/test/test_ip4.py
@@ -1410,5 +1410,55 @@ class TestIPInput(VppTestCase):
         # Reset MTU for subsequent tests
         self.vapi.sw_interface_set_mtu(self.pg1.sw_if_index, [9000, 0, 0, 0])
 
+
+class TestIPLPM(VppTestCase):
+    """ IPv4 longest Prefix Match """
+
+    def setUp(self):
+        super(TestIPLPM, self).setUp()
+
+        self.create_pg_interfaces(range(4))
+
+        for i in self.pg_interfaces:
+            i.admin_up()
+            i.config_ip4()
+            i.resolve_arp()
+
+    def tearDown(self):
+        super(TestIPLPM, self).tearDown()
+        for i in self.pg_interfaces:
+            i.admin_down()
+            i.unconfig_ip4()
+
+    def test_ip_lpm(self):
+        """ IP longest Prefix Match """
+
+        s_24 = VppIpRoute(self, "10.1.2.0", 24,
+                          [VppRoutePath(self.pg1.remote_ip4,
+                                        self.pg1.sw_if_index)])
+        s_24.add_vpp_config()
+        s_8 = VppIpRoute(self, "10.0.0.0", 8,
+                         [VppRoutePath(self.pg2.remote_ip4,
+                                       self.pg2.sw_if_index)])
+        s_8.add_vpp_config()
+
+        p_8 = (Ether(src=self.pg0.remote_mac,
+                     dst=self.pg0.local_mac) /
+               IP(src="1.1.1.1",
+                  dst="10.1.1.1") /
+               UDP(sport=1234, dport=1234) /
+               Raw('\xa5' * 2000))
+        p_24 = (Ether(src=self.pg0.remote_mac,
+                      dst=self.pg0.local_mac) /
+                IP(src="1.1.1.1",
+                   dst="10.1.2.1") /
+                UDP(sport=1234, dport=1234) /
+                Raw('\xa5' * 2000))
+
+        self.logger.info(self.vapi.cli("sh ip fib mtrie"))
+        rx = self.send_and_expect(self.pg0, p_8 * 65, self.pg2)
+        rx = self.send_and_expect(self.pg0, p_24 * 65, self.pg1)
+
+
 if __name__ == '__main__':
     unittest.main(testRunner=VppTestRunner)