Thread-safe ARP / ND throttling

Change-Id: I810d834c407bd404d5f0544cdec0674f0bb92d31
Signed-off-by: Dave Barach <dave@barachs.net>
Signed-off-by: Dave Barach <dbarach@cisco.com>

6 files changed, 103 insertions, 75 deletions

diff --git a/src/vnet/ip/ip4.h b/src/vnet/ip/ip4.h
index fcef559010c..e3cbe27dd89 100644
--- a/src/vnet/ip/ip4.h
+++ b/src/vnet/ip/ip4.h
@@ -154,8 +154,16 @@ typedef struct ip4_main_t
 
   /** The memory heap for the mtries */
   void *mtrie_mheap;
+
+  /** ARP throttling */
+  uword **arp_throttle_bitmaps;
+  u32 *arp_throttle_seeds;
+  f64 *arp_throttle_last_seed_change_time;
+
 } ip4_main_t;
 
+#define ARP_THROTTLE_BITS	(512)
+
 /** Global ip4 main structure. */
 extern ip4_main_t ip4_main;
 
diff --git a/src/vnet/ip/ip4_forward.c b/src/vnet/ip/ip4_forward.c
index 8d4aead051e..11bcf3a9435 100644
--- a/src/vnet/ip/ip4_forward.c
+++ b/src/vnet/ip/ip4_forward.c
@@ -1722,29 +1722,23 @@ ip4_arp_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, next_index;
-  static f64 time_last_seed_change = -1e100;
-  static u32 hash_seeds[3];
-  static uword hash_bitmap[256 / BITS (uword)];
+  u32 thread_index = vm->thread_index;
+  u32 seed;
   f64 time_now;
 
   if (node->flags & VLIB_NODE_FLAG_TRACE)
     ip4_forward_next_trace (vm, node, frame, VLIB_TX);
 
   time_now = vlib_time_now (vm);
-  if (time_now - time_last_seed_change > 1e-3)
+  if (time_now - im->arp_throttle_last_seed_change_time[thread_index] > 1e-3)
     {
-      uword i;
-      u32 *r = clib_random_buffer_get_data (&vm->random_buffer,
-					    sizeof (hash_seeds));
-      for (i = 0; i < ARRAY_LEN (hash_seeds); i++)
-	hash_seeds[i] = r[i];
-
-      /* Mark all hash keys as been no-seen before. */
-      for (i = 0; i < ARRAY_LEN (hash_bitmap); i++)
-	hash_bitmap[i] = 0;
+      (void) random_u32 (&im->arp_throttle_seeds[thread_index]);
+      memset (im->arp_throttle_bitmaps[thread_index], 0,
+	      ARP_THROTTLE_BITS / BITS (u8));
 
-      time_last_seed_change = time_now;
+      im->arp_throttle_last_seed_change_time[thread_index] = time_now;
     }
+  seed = im->arp_throttle_seeds[thread_index];
 
   from = vlib_frame_vector_args (frame);
   n_left_from = frame->n_vectors;
@@ -1759,11 +1753,11 @@ ip4_arp_inline (vlib_main_t * vm,
 
       while (n_left_from > 0 && n_left_to_next_drop > 0)
 	{
-	  u32 pi0, adj_index0, a0, b0, c0, m0, sw_if_index0, drop0;
+	  u32 pi0, adj_index0, r0, w0, sw_if_index0, drop0;
+	  uword m0;
 	  ip_adjacency_t *adj0;
 	  vlib_buffer_t *p0;
 	  ip4_header_t *ip0;
-	  uword bm0;
 
 	  pi0 = from[0];
 
@@ -1773,39 +1767,30 @@ ip4_arp_inline (vlib_main_t * vm,
 	  adj0 = adj_get (adj_index0);
 	  ip0 = vlib_buffer_get_current (p0);
 
-	  a0 = hash_seeds[0];
-	  b0 = hash_seeds[1];
-	  c0 = hash_seeds[2];
-
 	  sw_if_index0 = adj0->rewrite_header.sw_if_index;
 	  vnet_buffer (p0)->sw_if_index[VLIB_TX] = sw_if_index0;
 
-	  if (is_glean)
+	  if (PREDICT_TRUE (is_glean))
 	    {
 	      /*
 	       * this is the Glean case, so we are ARPing for the
 	       * packet's destination
 	       */
-	      a0 ^= ip0->dst_address.data_u32;
+	      r0 = ip0->dst_address.data_u32;
 	    }
 	  else
 	    {
-	      a0 ^= adj0->sub_type.nbr.next_hop.ip4.data_u32;
+	      r0 = adj0->sub_type.nbr.next_hop.ip4.data_u32;
 	    }
-	  b0 ^= sw_if_index0;
-
-	  hash_v3_mix32 (a0, b0, c0);
-	  hash_v3_finalize32 (a0, b0, c0);
-
-	  c0 &= BITS (hash_bitmap) - 1;
-	  m0 = (uword) 1 << (c0 % BITS (uword));
-	  c0 = c0 / BITS (uword);
 
-	  bm0 = hash_bitmap[c0];
-	  drop0 = (bm0 & m0) != 0;
+	  r0 ^= seed;
+	  /* Select bit number */
+	  r0 &= ARP_THROTTLE_BITS - 1;
+	  w0 = r0 / BITS (uword);
+	  m0 = (uword) 1 << (r0 % BITS (uword));
 
-	  /* Mark it as seen. */
-	  hash_bitmap[c0] = bm0 | m0;
+	  drop0 = (im->arp_throttle_bitmaps[thread_index][w0] & m0) != 0;
+	  im->arp_throttle_bitmaps[thread_index][w0] |= m0;
 
 	  from += 1;
 	  n_left_from -= 1;
diff --git a/src/vnet/ip/ip4_input.c b/src/vnet/ip/ip4_input.c
index 971445c7cd0..d11d558eb93 100644
--- a/src/vnet/ip/ip4_input.c
+++ b/src/vnet/ip/ip4_input.c
@@ -383,6 +383,28 @@ ip4_init (vlib_main_t * vm)
 }
 
 VLIB_INIT_FUNCTION (ip4_init);
+
+static clib_error_t *
+ip4_main_loop_enter (vlib_main_t * vm)
+{
+  ip4_main_t *im = &ip4_main;
+  vlib_thread_main_t *tm = &vlib_thread_main;
+  u32 n_vlib_mains = tm->n_vlib_mains;
+  int i;
+
+
+  vec_validate (im->arp_throttle_bitmaps, n_vlib_mains);
+  vec_validate (im->arp_throttle_seeds, n_vlib_mains);
+  vec_validate (im->arp_throttle_last_seed_change_time, n_vlib_mains);
+
+  for (i = 0; i < n_vlib_mains; i++)
+    vec_validate (im->arp_throttle_bitmaps[i],
+		  (ARP_THROTTLE_BITS / BITS (uword)) - 1);
+  return 0;
+}
+
+VLIB_MAIN_LOOP_ENTER_FUNCTION (ip4_main_loop_enter);
+
 #endif
 
 /*
diff --git a/src/vnet/ip/ip6.h b/src/vnet/ip/ip6.h
index 8b1516cf353..a6feec5685e 100644
--- a/src/vnet/ip/ip6.h
+++ b/src/vnet/ip/ip6.h
@@ -219,8 +219,16 @@ typedef struct ip6_main_t
 
   /* HBH processing enabled? */
   u8 hbh_enabled;
+
+  /** ND throttling */
+  uword **nd_throttle_bitmaps;
+  u64 *nd_throttle_seeds;
+  f64 *nd_throttle_last_seed_change_time;
+
 } ip6_main_t;
 
+#define ND_THROTTLE_BITS 512
+
 /* Global ip6 main structure. */
 extern ip6_main_t ip6_main;
 
diff --git a/src/vnet/ip/ip6_input.c b/src/vnet/ip/ip6_input.c
index 6a7669db297..977d2703d19 100644
--- a/src/vnet/ip/ip6_input.c
+++ b/src/vnet/ip/ip6_input.c
@@ -246,8 +246,10 @@ VLIB_REGISTER_NODE (ip6_input_node) = {
 };
 /* *INDENT-ON* */
 
-VLIB_NODE_FUNCTION_MULTIARCH (ip6_input_node, ip6_input)
-     static clib_error_t *ip6_init (vlib_main_t * vm)
+VLIB_NODE_FUNCTION_MULTIARCH (ip6_input_node, ip6_input);
+
+static clib_error_t *
+ip6_init (vlib_main_t * vm)
 {
   ethernet_register_input_type (vm, ETHERNET_TYPE_IP6, ip6_input_node.index);
   ppp_register_input_protocol (vm, PPP_PROTOCOL_ip6, ip6_input_node.index);
@@ -270,6 +272,26 @@ VLIB_NODE_FUNCTION_MULTIARCH (ip6_input_node, ip6_input)
 
 VLIB_INIT_FUNCTION (ip6_init);
 
+static clib_error_t *
+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);
+
+  for (i = 0; i < n_vlib_mains; i++)
+    vec_validate (im->nd_throttle_bitmaps[i],
+		  (ND_THROTTLE_BITS / BITS (uword)) - 1);
+  return 0;
+}
+
+VLIB_MAIN_LOOP_ENTER_FUNCTION (ip6_main_loop_enter);
+
 /*
  * fd.io coding-style-patch-verification: ON
  *
diff --git a/src/vnet/ip/ip6_neighbor.c b/src/vnet/ip/ip6_neighbor.c
index 6227ed6dfb0..fff81749ea2 100644
--- a/src/vnet/ip/ip6_neighbor.c
+++ b/src/vnet/ip/ip6_neighbor.c
@@ -3165,10 +3165,9 @@ 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;
-  static f64 time_last_seed_change = -1e100;
-  static u32 hash_seeds[3];
-  static uword hash_bitmap[256 / BITS (uword)];
   f64 time_now;
+  u64 seed;
+  u32 thread_index = vm->thread_index;
   int bogus_length;
   ip6_neighbor_main_t *nm = &ip6_neighbor_main;
 
@@ -3176,20 +3175,15 @@ ip6_discover_neighbor_inline (vlib_main_t * vm,
     ip6_forward_next_trace (vm, node, frame, VLIB_TX);
 
   time_now = vlib_time_now (vm);
-  if (time_now - time_last_seed_change > 1e-3)
+  if (time_now - im->nd_throttle_last_seed_change_time[thread_index] > 1e-3)
     {
-      uword i;
-      u32 *r = clib_random_buffer_get_data (&vm->random_buffer,
-					    sizeof (hash_seeds));
-      for (i = 0; i < ARRAY_LEN (hash_seeds); i++)
-	hash_seeds[i] = r[i];
+      (void) random_u64 (&im->nd_throttle_seeds[thread_index]);
+      memset (im->nd_throttle_bitmaps[thread_index], 0,
+	      ND_THROTTLE_BITS / BITS (u8));
 
-      /* Mark all hash keys as been not-seen before. */
-      for (i = 0; i < ARRAY_LEN (hash_bitmap); i++)
-	hash_bitmap[i] = 0;
-
-      time_last_seed_change = time_now;
+      im->nd_throttle_last_seed_change_time[thread_index] = time_now;
     }
+  seed = im->nd_throttle_seeds[thread_index];
 
   from = vlib_frame_vector_args (frame);
   n_left_from = frame->n_vectors;
@@ -3203,8 +3197,9 @@ ip6_discover_neighbor_inline (vlib_main_t * vm,
 	{
 	  vlib_buffer_t *p0;
 	  ip6_header_t *ip0;
-	  u32 pi0, adj_index0, a0, b0, c0, m0, sw_if_index0, drop0;
-	  uword bm0;
+	  u32 pi0, adj_index0, w0, sw_if_index0, drop0;
+	  u64 r0;
+	  uword m0;
 	  ip_adjacency_t *adj0;
 	  vnet_hw_interface_t *hw_if0;
 	  ip6_radv_t *radv_info;
@@ -3228,33 +3223,21 @@ ip6_discover_neighbor_inline (vlib_main_t * vm,
 		adj0->sub_type.nbr.next_hop.ip6.as_u64[1];
 	    }
 
-	  a0 = hash_seeds[0];
-	  b0 = hash_seeds[1];
-	  c0 = hash_seeds[2];
-
 	  sw_if_index0 = adj0->rewrite_header.sw_if_index;
 	  vnet_buffer (p0)->sw_if_index[VLIB_TX] = sw_if_index0;
 
-	  a0 ^= sw_if_index0;
-	  b0 ^= ip0->dst_address.as_u32[0];
-	  c0 ^= ip0->dst_address.as_u32[1];
-
-	  hash_v3_mix32 (a0, b0, c0);
-
-	  b0 ^= ip0->dst_address.as_u32[2];
-	  c0 ^= ip0->dst_address.as_u32[3];
-
-	  hash_v3_finalize32 (a0, b0, c0);
-
-	  c0 &= BITS (hash_bitmap) - 1;
-	  c0 = c0 / BITS (uword);
-	  m0 = (uword) 1 << (c0 % BITS (uword));
+	  /* Compute the ND throttle bitmap hash */
+	  r0 = ip0->dst_address.as_u64[0] ^ ip0->dst_address.as_u64[1] ^ seed;
 
-	  bm0 = hash_bitmap[c0];
-	  drop0 = (bm0 & m0) != 0;
+	  /* Find the word and bit */
+	  r0 &= ND_THROTTLE_BITS - 1;
+	  w0 = r0 / BITS (uword);
+	  m0 = (uword) 1 << (r0 % BITS (uword));
 
-	  /* Mark it as seen. */
-	  hash_bitmap[c0] = bm0 | m0;
+	  /* 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;
 
 	  from += 1;
 	  n_left_from -= 1;