Use throttle_t for ND throttling (VPP-1480)

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

7 files changed, 71 insertions, 52 deletions

diff --git a/src/vnet/ip/ip4_forward.c b/src/vnet/ip/ip4_forward.c
index 69a8dbad805..ffb873a9611 100644
--- a/src/vnet/ip/ip4_forward.c
+++ b/src/vnet/ip/ip4_forward.c
@@ -1750,7 +1750,7 @@ ip4_arp_inline (vlib_main_t * vm,
   u32 *from, *to_next_drop;
   uword n_left_from, n_left_to_next_drop, next_index;
   u32 thread_index = vm->thread_index;
-  u32 seed;
+  u64 seed;
 
   if (node->flags & VLIB_NODE_FLAG_TRACE)
     ip4_forward_next_trace (vm, node, frame, VLIB_TX);
@@ -1770,10 +1770,11 @@ ip4_arp_inline (vlib_main_t * vm,
 
       while (n_left_from > 0 && n_left_to_next_drop > 0)
 	{
-	  u32 pi0, adj_index0, r0, sw_if_index0, drop0;
+	  u32 pi0, adj_index0, sw_if_index0, drop0;
 	  ip_adjacency_t *adj0;
 	  vlib_buffer_t *p0;
 	  ip4_header_t *ip0;
+	  u64 r0;
 
 	  pi0 = from[0];
 
@@ -1798,6 +1799,9 @@ ip4_arp_inline (vlib_main_t * vm,
 	    {
 	      r0 = adj0->sub_type.nbr.next_hop.ip4.data_u32;
 	    }
+	  /* combine the address and interface for the hash key */
+	  r0 = r0 << 32;
+	  r0 |= sw_if_index0;
 
 	  drop0 = throttle_check (&im->arp_throttle, thread_index, r0, seed);
 
diff --git a/src/vnet/ip/ip6.h b/src/vnet/ip/ip6.h
index bc89a0821ae..e807886cd2a 100644
--- a/src/vnet/ip/ip6.h
+++ b/src/vnet/ip/ip6.h
@@ -49,6 +49,7 @@
 #include <vppinfra/bihash_24_8.h>
 #include <vppinfra/bihash_template.h>
 #include <vnet/util/radix.h>
+#include <vnet/util/throttle.h>
 
 /*
  * Default size of the ip6 fib hash table
@@ -220,10 +221,7 @@ typedef struct ip6_main_t
   u8 hbh_enabled;
 
   /** ND throttling */
-  uword **nd_throttle_bitmaps;
-  u64 *nd_throttle_seeds;
-  f64 *nd_throttle_last_seed_change_time;
-
+  throttle_t nd_throttle;
 } ip6_main_t;
 
 #define ND_THROTTLE_BITS 512
diff --git a/src/vnet/ip/ip6_input.c b/src/vnet/ip/ip6_input.c
index 977d2703d19..a01920a7b48 100644
--- a/src/vnet/ip/ip6_input.c
+++ b/src/vnet/ip/ip6_input.c
@@ -277,16 +277,9 @@ ip6_main_loop_enter (vlib_main_t * vm)
 {
   ip6_main_t *im = &ip6_main;
   vlib_thread_main_t *tm = &vlib_thread_main;
-  u32 n_vlib_mains = tm->n_vlib_mains;
-  int i;
 
-  vec_validate (im->nd_throttle_bitmaps, n_vlib_mains);
-  vec_validate (im->nd_throttle_seeds, n_vlib_mains);
-  vec_validate (im->nd_throttle_last_seed_change_time, n_vlib_mains);
+  throttle_init (&im->nd_throttle, tm->n_vlib_mains, 1e-3);
 
-  for (i = 0; i < n_vlib_mains; i++)
-    vec_validate (im->nd_throttle_bitmaps[i],
-		  (ND_THROTTLE_BITS / BITS (uword)) - 1);
   return 0;
 }
 
diff --git a/src/vnet/ip/ip6_neighbor.c b/src/vnet/ip/ip6_neighbor.c
index 8466ba70313..b6889157cab 100755
--- a/src/vnet/ip/ip6_neighbor.c
+++ b/src/vnet/ip/ip6_neighbor.c
@@ -3163,7 +3163,6 @@ ip6_discover_neighbor_inline (vlib_main_t * vm,
   ip_lookup_main_t *lm = &im->lookup_main;
   u32 *from, *to_next_drop;
   uword n_left_from, n_left_to_next_drop;
-  f64 time_now;
   u64 seed;
   u32 thread_index = vm->thread_index;
   int bogus_length;
@@ -3172,16 +3171,7 @@ ip6_discover_neighbor_inline (vlib_main_t * vm,
   if (node->flags & VLIB_NODE_FLAG_TRACE)
     ip6_forward_next_trace (vm, node, frame, VLIB_TX);
 
-  time_now = vlib_time_now (vm);
-  if (time_now - im->nd_throttle_last_seed_change_time[thread_index] > 1e-3)
-    {
-      (void) random_u64 (&im->nd_throttle_seeds[thread_index]);
-      memset (im->nd_throttle_bitmaps[thread_index], 0,
-	      ND_THROTTLE_BITS / BITS (u8));
-
-      im->nd_throttle_last_seed_change_time[thread_index] = time_now;
-    }
-  seed = im->nd_throttle_seeds[thread_index];
+  seed = throttle_seed (&im->nd_throttle, thread_index, vlib_time_now (vm));
 
   from = vlib_frame_vector_args (frame);
   n_left_from = frame->n_vectors;
@@ -3193,15 +3183,12 @@ ip6_discover_neighbor_inline (vlib_main_t * vm,
 
       while (n_left_from > 0 && n_left_to_next_drop > 0)
 	{
-	  vlib_buffer_t *p0;
-	  ip6_header_t *ip0;
-	  u32 pi0, adj_index0, w0, sw_if_index0, drop0;
-	  u64 r0;
-	  uword m0;
-	  ip_adjacency_t *adj0;
+	  u32 pi0, adj_index0, sw_if_index0, drop0, r0, next0;
 	  vnet_hw_interface_t *hw_if0;
 	  ip6_radv_t *radv_info;
-	  u32 next0;
+	  ip_adjacency_t *adj0;
+	  vlib_buffer_t *p0;
+	  ip6_header_t *ip0;
 
 	  pi0 = from[0];
 
@@ -3224,18 +3211,10 @@ ip6_discover_neighbor_inline (vlib_main_t * vm,
 	  sw_if_index0 = adj0->rewrite_header.sw_if_index;
 	  vnet_buffer (p0)->sw_if_index[VLIB_TX] = sw_if_index0;
 
-	  /* Compute the ND throttle bitmap hash */
-	  r0 = ip0->dst_address.as_u64[0] ^ ip0->dst_address.as_u64[1] ^ seed;
-
-	  /* Find the word and bit */
-	  r0 &= ND_THROTTLE_BITS - 1;
-	  w0 = r0 / BITS (uword);
-	  m0 = (uword) 1 << (r0 % BITS (uword));
+	  /* combine the address and interface for a hash */
+	  r0 = ip6_address_hash_to_u64 (&ip0->dst_address) ^ sw_if_index0;
 
-	  /* If the bit is set, drop the ND request */
-	  drop0 = (im->nd_throttle_bitmaps[thread_index][w0] & m0) != 0;
-	  /* (unconditionally) mark the bit "inuse" */
-	  im->nd_throttle_bitmaps[thread_index][w0] |= m0;
+	  drop0 = throttle_check (&im->nd_throttle, thread_index, r0, seed);
 
 	  from += 1;
 	  n_left_from -= 1;
diff --git a/src/vnet/ip/ip6_packet.h b/src/vnet/ip/ip6_packet.h
index ea2fa155b5e..cdcffa59b8b 100644
--- a/src/vnet/ip/ip6_packet.h
+++ b/src/vnet/ip/ip6_packet.h
@@ -347,6 +347,18 @@ ip6_is_solicited_node_multicast_address (const ip6_address_t * a)
 	  && a->as_u8[12] == 0xff);
 }
 
+always_inline u32
+ip6_address_hash_to_u32 (const ip6_address_t * a)
+{
+  return (a->as_u32[0] ^ a->as_u32[1] ^ a->as_u32[2] ^ a->as_u32[3]);
+}
+
+always_inline u64
+ip6_address_hash_to_u64 (const ip6_address_t * a)
+{
+  return (a->as_u64[0] ^ a->as_u64[1]);
+}
+
 typedef struct
 {
   /* 4 bit version, 8 bit traffic class and 20 bit flow label. */
diff --git a/src/vnet/util/throttle.h b/src/vnet/util/throttle.h
index 97ebb2597b3..28bf7aa2217 100644
--- a/src/vnet/util/throttle.h
+++ b/src/vnet/util/throttle.h
@@ -17,6 +17,7 @@
 #define __THROTTLE_H__
 
 #include <vlib/vlib.h>
+#include <vppinfra/xxhash.h>
 
 /**
  * @brief A throttle
@@ -28,7 +29,7 @@ typedef struct throttle_t_
 {
   f64 time;
   uword **bitmaps;
-  u32 *seeds;
+  u64 *seeds;
   f64 *last_seed_change_time;
 } throttle_t;
 
@@ -36,12 +37,12 @@ typedef struct throttle_t_
 
 extern void throttle_init (throttle_t * t, u32 n_threads, f64 time);
 
-always_inline u32
+always_inline u64
 throttle_seed (throttle_t * t, u32 thread_index, f64 time_now)
 {
   if (time_now - t->last_seed_change_time[thread_index] > t->time)
     {
-      (void) random_u32 (&t->seeds[thread_index]);
+      (void) random_u64 (&t->seeds[thread_index]);
       memset (t->bitmaps[thread_index], 0, THROTTLE_BITS / BITS (u8));
 
       t->last_seed_change_time[thread_index] = time_now;
@@ -50,13 +51,14 @@ throttle_seed (throttle_t * t, u32 thread_index, f64 time_now)
 }
 
 always_inline int
-throttle_check (throttle_t * t, u32 thread_index, u32 hash, u32 seed)
+throttle_check (throttle_t * t, u32 thread_index, u64 hash, u64 seed)
 {
   int drop;
   uword m;
   u32 w;
 
-  hash ^= seed;
+  hash = clib_xxhash (hash ^ seed);
+
   /* Select bit number */
   hash &= THROTTLE_BITS - 1;
   w = hash / BITS (uword);
diff --git a/test/test_neighbor.py b/test/test_neighbor.py
index a15106af1f9..67424048797 100644
--- a/test/test_neighbor.py
+++ b/test/test_neighbor.py
@@ -6,11 +6,12 @@ from socket import AF_INET, AF_INET6, inet_pton
 from framework import VppTestCase, VppTestRunner
 from vpp_neighbor import VppNeighbor, find_nbr
 from vpp_ip_route import VppIpRoute, VppRoutePath, find_route, \
-    VppIpTable
+    VppIpTable, DpoProto
 
 from scapy.packet import Raw
 from scapy.layers.l2 import Ether, ARP, Dot1Q
 from scapy.layers.inet import IP, UDP
+from scapy.layers.inet6 import IPv6
 from scapy.contrib.mpls import MPLS
 from scapy.layers.inet6 import IPv6
 
@@ -1321,14 +1322,16 @@ class ARPTestCase(VppTestCase):
         """ Incomplete Entries """
 
         #
-        # ensure that we throttle the ARP requests
+        # ensure that we throttle the ARP and ND requests
         #
         self.pg0.generate_remote_hosts(2)
 
+        #
+        # IPv4/ARP
+        #
         ip_10_0_0_1 = VppIpRoute(self, "10.0.0.1", 32,
                                  [VppRoutePath(self.pg0.remote_hosts[1].ip4,
-                                               self.pg0.sw_if_index,
-                                               labels=[55])])
+                                               self.pg0.sw_if_index)])
         ip_10_0_0_1.add_vpp_config()
 
         p1 = (Ether(dst=self.pg1.local_mac,
@@ -1349,6 +1352,34 @@ class ARPTestCase(VppTestCase):
         #
         self.assertTrue(len(rx) < 64)
 
+        #
+        # IPv6/ND
+        #
+        ip_10_1 = VppIpRoute(self, "10::1", 128,
+                             [VppRoutePath(self.pg0.remote_hosts[1].ip6,
+                                           self.pg0.sw_if_index,
+                                           proto=DpoProto.DPO_PROTO_IP6)],
+                             is_ip6=1)
+        ip_10_1.add_vpp_config()
+
+        p1 = (Ether(dst=self.pg1.local_mac,
+                    src=self.pg1.remote_mac) /
+              IPv6(src=self.pg1.remote_ip6,
+                   dst="10::1") /
+              UDP(sport=1234, dport=1234) /
+              Raw())
+
+        self.pg1.add_stream(p1 * 257)
+        self.pg_enable_capture(self.pg_interfaces)
+        self.pg_start()
+        rx = self.pg0._get_capture(1)
+
+        #
+        # how many we get is going to be dependent on the time for packet
+        # processing but it should be small
+        #
+        self.assertTrue(len(rx) < 64)
+
 
 class NeighborStatsTestCase(VppTestCase):
     """ ARP Test Case """