nat: ED: port re-use algorithm

Type: fix

Change-Id: I11440c855eb35d2a6095dfe135e4ab5090f11ff3
Signed-off-by: Klement Sekera <ksekera@cisco.com>

6 files changed, 196 insertions, 45 deletions

diff --git a/src/plugins/nat/in2out_ed.c b/src/plugins/nat/in2out_ed.c
index 6ca1e6ecb4d..0ca1dd89ca8 100644
--- a/src/plugins/nat/in2out_ed.c
+++ b/src/plugins/nat/in2out_ed.c
@@ -107,6 +107,16 @@ nat44_i2o_ed_is_idle_session_cb (clib_bihash_kv_16_8_t * kv, void *arg)
       if (clib_bihash_add_del_16_8 (&tsm->out2in_ed, &ed_kv, 0))
 	nat_elog_warn ("out2in_ed key del failed");
 
+      ed_bihash_kv_t bihash_key;
+      clib_memset (&bihash_key, 0, sizeof (bihash_key));
+      bihash_key.k.dst_address = s->ext_host_addr.as_u32;
+      bihash_key.k.dst_port = s->ext_host_port;
+      bihash_key.k.src_address = s->out2in.addr.as_u32;
+      bihash_key.k.src_port = s->out2in.port;
+      bihash_key.k.protocol = s->out2in.protocol;
+      clib_bihash_add_del_16_8 (&sm->ed_ext_ports, &bihash_key.kv,
+				0 /* is_add */ );
+
       if (snat_is_unk_proto_session (s))
 	goto delete;
 
@@ -182,6 +192,96 @@ icmp_in2out_ed_slow_path (snat_main_t * sm, vlib_buffer_t * b0,
   return next0;
 }
 
+static_always_inline u16
+snat_random_port (u16 min, u16 max)
+{
+  snat_main_t *sm = &snat_main;
+  return min + random_u32 (&sm->random_seed) /
+    (random_u32_max () / (max - min + 1) + 1);
+}
+
+static int
+nat_alloc_addr_and_port_ed (snat_address_t * addresses, u32 fib_index,
+			    u32 thread_index, nat_ed_ses_key_t * key,
+			    snat_session_key_t * key1, u16 port_per_thread,
+			    u32 snat_thread_index)
+{
+  int i;
+  snat_address_t *a, *ga = 0;
+  u32 portnum;
+
+  const u16 port_thread_offset = (port_per_thread * snat_thread_index) + 1024;
+  ed_bihash_kv_t bihash_key;
+  clib_memset (&bihash_key, 0, sizeof (bihash_key));
+  bihash_key.k.dst_address = key->r_addr.as_u32;
+  bihash_key.k.dst_port = key->r_port;
+  bihash_key.k.protocol = key1->protocol;
+
+  for (i = 0; i < vec_len (addresses); i++)
+    {
+      a = addresses + i;
+      switch (key1->protocol)
+	{
+#define _(N, j, n, s)                                                     \
+  case SNAT_PROTOCOL_##N:                                                 \
+    if (a->fib_index == fib_index)                                        \
+      {                                                                   \
+        bihash_key.k.src_address = a->addr.as_u32;                        \
+        u16 port = snat_random_port (1, port_per_thread);                 \
+        u16 attempts = port_per_thread;                                   \
+        while (attempts > 0)                                              \
+          {                                                               \
+            --attempts;                                                   \
+            portnum = port_thread_offset + port;                          \
+            bihash_key.k.src_port = clib_host_to_net_u16 (portnum);       \
+            int rv = clib_bihash_add_del_16_8 (                           \
+                &snat_main.ed_ext_ports, &bihash_key.kv, 2 /* is_add */); \
+            if (0 == rv)                                                  \
+              {                                                           \
+                ++a->busy_##n##_port_refcounts[portnum];                  \
+                a->busy_##n##_ports_per_thread[thread_index]++;           \
+                a->busy_##n##_ports++;                                    \
+                key1->addr = a->addr;                                     \
+                key1->port = clib_host_to_net_u16 (portnum);              \
+                return 0;                                                 \
+              }                                                           \
+            port = (port + 1) % port_per_thread;                          \
+          }                                                               \
+      }                                                                   \
+    else if (a->fib_index == ~0)                                          \
+      {                                                                   \
+        ga = a;                                                           \
+      }                                                                   \
+    break;
+
+	  foreach_snat_protocol;
+	default:
+	  nat_elog_info ("unknown protocol");
+	  return 1;
+	}
+    }
+
+  if (ga)
+    {
+      /* fake fib_index to reuse macro */
+      fib_index = ~0;
+      a = ga;
+      switch (key1->protocol)
+	{
+	  foreach_snat_protocol;
+	default:
+	  nat_elog_info ("unknown protocol");
+	  return 1;
+	}
+    }
+
+#undef _
+
+  /* Totally out of translations to use... */
+  snat_ipfix_logging_addresses_exhausted (thread_index, 0);
+  return 1;
+}
+
 static u32
 slow_path_ed (snat_main_t * sm,
 	      vlib_buffer_t * b,
@@ -234,16 +334,16 @@ slow_path_ed (snat_main_t * sm,
       (sm, key0, &key1, 0, 0, 0, &lb, 0, &identity_nat))
     {
       /* Try to create dynamic translation */
-      if (snat_alloc_outside_address_and_port (sm->addresses, rx_fib_index,
-					       thread_index, &key1,
-					       sm->port_per_thread,
-					       tsm->snat_thread_index))
+      if (nat_alloc_addr_and_port_ed (sm->addresses, rx_fib_index,
+				      thread_index, key, &key1,
+				      sm->port_per_thread,
+				      tsm->snat_thread_index))
 	{
 	  if (cleared || !nat44_out_of_ports_cleanup (thread_index, now) ||
-	      snat_alloc_outside_address_and_port (sm->addresses,
-						   rx_fib_index, thread_index,
-						   &key1, sm->port_per_thread,
-						   tsm->snat_thread_index))
+	      nat_alloc_addr_and_port_ed (sm->addresses, rx_fib_index,
+					  thread_index, key, &key1,
+					  sm->port_per_thread,
+					  tsm->snat_thread_index))
 	    {
 	      nat_elog_notice ("addresses exhausted");
 	      b->error = node->errors[NAT_IN2OUT_ED_ERROR_OUT_OF_PORTS];
diff --git a/src/plugins/nat/nat.c b/src/plugins/nat/nat.c
index ffa94a1fd94..2b5c428ebc9 100755
--- a/src/plugins/nat/nat.c
+++ b/src/plugins/nat/nat.c
@@ -33,6 +33,7 @@
 #include <vnet/fib/fib_table.h>
 #include <vnet/fib/ip4_fib.h>
 #include <vnet/ip/reass/ip4_sv_reass.h>
+#include <vppinfra/bihash_16_8.h>
 
 #include <vpp/app/version.h>
 
@@ -322,6 +323,16 @@ nat_free_session_data (snat_main_t * sm, snat_session_t * s, u32 thread_index,
   if (snat_is_session_static (s))
     return;
 
+  ed_bihash_kv_t bihash_key;
+  clib_memset (&bihash_key, 0, sizeof (bihash_key));
+  bihash_key.k.dst_address = s->ext_host_addr.as_u32;
+  bihash_key.k.dst_port = s->ext_host_port;
+  bihash_key.k.src_address = s->out2in.addr.as_u32;
+  bihash_key.k.src_port = s->out2in.port;
+  bihash_key.k.protocol = s->out2in.protocol;
+  clib_bihash_add_del_16_8 (&sm->ed_ext_ports, &bihash_key.kv,
+			    0 /* is_add */ );
+
   snat_free_outside_address_and_port (sm->addresses, thread_index,
 				      &s->out2in);
 }
@@ -447,6 +458,16 @@ nat44_free_session_data (snat_main_t * sm, snat_session_t * s,
   if (snat_is_session_static (s))
     return;
 
+  ed_bihash_kv_t bihash_key;
+  clib_memset (&bihash_key, 0, sizeof (bihash_key));
+  bihash_key.k.dst_address = s->ext_host_addr.as_u32;
+  bihash_key.k.dst_port = s->ext_host_port;
+  bihash_key.k.src_address = s->out2in.addr.as_u32;
+  bihash_key.k.src_port = s->out2in.port;
+  bihash_key.k.protocol = s->out2in.protocol;
+  clib_bihash_add_del_16_8 (&sm->ed_ext_ports, &bihash_key.kv,
+			    0 /* is_add */ );
+
   // should be called for every dynamic session
   snat_free_outside_address_and_port (sm->addresses, thread_index,
 				      &s->out2in);
@@ -701,7 +722,7 @@ snat_add_address (snat_main_t * sm, ip4_address_t * addr, u32 vrf_id,
   else
     ap->fib_index = ~0;
 #define _(N, i, n, s) \
-  clib_bitmap_alloc (ap->busy_##n##_port_bitmap, 65535); \
+  clib_memset(ap->busy_##n##_port_refcounts, 0, sizeof(ap->busy_##n##_port_refcounts));\
   ap->busy_##n##_ports = 0; \
   ap->busy_##n##_ports_per_thread = 0;\
   vec_validate_init_empty (ap->busy_##n##_ports_per_thread, tm->n_vlib_mains - 1, 0);
@@ -980,9 +1001,9 @@ snat_add_static_mapping (ip4_address_t l_addr, ip4_address_t e_addr,
 		    {
 #define _(N, j, n, s) \
                     case SNAT_PROTOCOL_##N: \
-                      if (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, e_port)) \
+                      if (a->busy_##n##_port_refcounts[e_port]) \
                         return VNET_API_ERROR_INVALID_VALUE; \
-                      clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, e_port, 1); \
+                      ++a->busy_##n##_port_refcounts[e_port]; \
                       if (e_port > 1024) \
                         { \
                           a->busy_##n##_ports++; \
@@ -1164,7 +1185,7 @@ snat_add_static_mapping (ip4_address_t l_addr, ip4_address_t e_addr,
 		    {
 #define _(N, j, n, s) \
                     case SNAT_PROTOCOL_##N: \
-                      clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, e_port, 0); \
+                      --a->busy_##n##_port_refcounts[e_port]; \
                       if (e_port > 1024) \
                         { \
                           a->busy_##n##_ports--; \
@@ -1343,9 +1364,9 @@ nat44_add_del_lb_static_mapping (ip4_address_t e_addr, u16 e_port,
 		    {
 #define _(N, j, n, s) \
                     case SNAT_PROTOCOL_##N: \
-                      if (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, e_port)) \
+                      if (a->busy_##n##_port_refcounts[e_port]) \
                         return VNET_API_ERROR_INVALID_VALUE; \
-                      clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, e_port, 1); \
+                      ++a->busy_##n##_port_refcounts[e_port]; \
                       if (e_port > 1024) \
                         { \
                           a->busy_##n##_ports++; \
@@ -1459,7 +1480,7 @@ nat44_add_del_lb_static_mapping (ip4_address_t e_addr, u16 e_port,
 		    {
 #define _(N, j, n, s) \
                     case SNAT_PROTOCOL_##N: \
-                      clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, e_port, 0); \
+                      --a->busy_##n##_port_refcounts[e_port]; \
                       if (e_port > 1024) \
                         { \
                           a->busy_##n##_ports--; \
@@ -1826,7 +1847,6 @@ snat_del_address (snat_main_t * sm, ip4_address_t addr, u8 delete_sm,
     }
 
 #define _(N, i, n, s) \
-  clib_bitmap_free (a->busy_##n##_port_bitmap); \
   vec_free (a->busy_##n##_ports_per_thread);
   foreach_snat_protocol
 #undef _
@@ -2651,10 +2671,8 @@ snat_free_outside_address_and_port (snat_address_t * addresses,
     {
 #define _(N, i, n, s) \
     case SNAT_PROTOCOL_##N: \
-      ASSERT (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, \
-        port_host_byte_order) == 1); \
-      clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, \
-        port_host_byte_order, 0); \
+      ASSERT (a->busy_##n##_port_refcounts[port_host_byte_order] >= 1); \
+      --a->busy_##n##_port_refcounts[port_host_byte_order]; \
       a->busy_##n##_ports--; \
       a->busy_##n##_ports_per_thread[thread_index]--; \
       break;
@@ -2685,9 +2703,9 @@ nat_set_outside_address_and_port (snat_address_t * addresses,
 	{
 #define _(N, j, n, s) \
         case SNAT_PROTOCOL_##N: \
-          if (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, port_host_byte_order)) \
+          if (a->busy_##n##_port_refcounts[port_host_byte_order]) \
             return VNET_API_ERROR_INSTANCE_IN_USE; \
-          clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, port_host_byte_order, 1); \
+	  ++a->busy_##n##_port_refcounts[port_host_byte_order]; \
           a->busy_##n##_ports_per_thread[thread_index]++; \
           a->busy_##n##_ports++; \
           return 0;
@@ -2902,9 +2920,9 @@ nat_alloc_addr_and_port_default (snat_address_t * addresses,
                       portnum = (port_per_thread * \
                         snat_thread_index) + \
                         snat_random_port(1, port_per_thread) + 1024; \
-                      if (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, portnum)) \
+                      if (a->busy_##n##_port_refcounts[portnum]) \
                         continue; \
-                      clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, portnum, 1); \
+		      --a->busy_##n##_port_refcounts[portnum]; \
                       a->busy_##n##_ports_per_thread[thread_index]++; \
                       a->busy_##n##_ports++; \
                       k->addr = a->addr; \
@@ -2939,9 +2957,9 @@ nat_alloc_addr_and_port_default (snat_address_t * addresses,
               portnum = (port_per_thread * \
                 snat_thread_index) + \
                 snat_random_port(1, port_per_thread) + 1024; \
-              if (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, portnum)) \
+	      if (a->busy_##n##_port_refcounts[portnum]) \
                 continue; \
-              clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, portnum, 1); \
+	      ++a->busy_##n##_port_refcounts[portnum]; \
               a->busy_##n##_ports_per_thread[thread_index]++; \
               a->busy_##n##_ports++; \
               k->addr = a->addr; \
@@ -2989,9 +3007,9 @@ nat_alloc_addr_and_port_mape (snat_address_t * addresses,
               A = snat_random_port(1, pow2_mask(sm->psid_offset)); \
               j = snat_random_port(0, pow2_mask(m)); \
               portnum = A | (sm->psid << sm->psid_offset) | (j << (16 - m)); \
-              if (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, portnum)) \
+	      if (a->busy_##n##_port_refcounts[portnum]) \
                 continue; \
-              clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, portnum, 1); \
+	      ++a->busy_##n##_port_refcounts[portnum]; \
               a->busy_##n##_ports++; \
               k->addr = a->addr; \
               k->port = clib_host_to_net_u16 (portnum); \
@@ -3037,9 +3055,9 @@ nat_alloc_addr_and_port_range (snat_address_t * addresses,
           while (1) \
             { \
               portnum = snat_random_port(sm->start_port, sm->end_port); \
-              if (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, portnum)) \
+	      if (a->busy_##n##_port_refcounts[portnum]) \
                 continue; \
-              clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, portnum, 1); \
+	      ++a->busy_##n##_port_refcounts[portnum]; \
               a->busy_##n##_ports++; \
               k->addr = a->addr; \
               k->port = clib_host_to_net_u16 (portnum); \
@@ -4068,6 +4086,9 @@ snat_config (vlib_main_t * vm, unformat_input_t * input)
                                          translation_memory_size);
                   clib_bihash_set_kvp_format_fn_16_8 (&tsm->out2in_ed,
                                                       format_ed_session_kvp);
+                  clib_bihash_init_16_8
+                  (&sm->ed_ext_ports, "ed-nat-5-tuple-port-overload-hash",
+                   translation_buckets, translation_memory_size);
                 }
               else
                 {
diff --git a/src/plugins/nat/nat.h b/src/plugins/nat/nat.h
index fde6a0a7308..46dc040c574 100644
--- a/src/plugins/nat/nat.h
+++ b/src/plugins/nat/nat.h
@@ -31,6 +31,7 @@
 #include <vppinfra/error.h>
 #include <vlibapi/api.h>
 #include <vlib/log.h>
+#include <vppinfra/bihash_16_8.h>
 
 /* default session timeouts */
 #define SNAT_UDP_TIMEOUT 300
@@ -368,7 +369,7 @@ typedef struct
 #define _(N, i, n, s) \
   u16 busy_##n##_ports; \
   u16 * busy_##n##_ports_per_thread; \
-  uword * busy_##n##_port_bitmap;
+  u32 busy_##n##_port_refcounts[65535];
   foreach_snat_protocol
 #undef _
 /* *INDENT-ON* */
@@ -567,6 +568,28 @@ typedef int (nat_alloc_out_addr_and_port_function_t) (snat_address_t *
 						      u16 port_per_thread,
 						      u32 snat_thread_index);
 
+typedef struct ed_bihash_key_s
+{
+  u32 src_address;
+  u32 dst_address;
+  u16 src_port;
+  u16 dst_port;
+  u8 protocol;
+} ed_bihash_key_t;
+
+typedef struct ed_bihash_kv_s
+{
+  union
+  {
+    ed_bihash_key_t k;
+    clib_bihash_kv_16_8_t kv;
+  };
+} ed_bihash_kv_t;
+
+STATIC_ASSERT (STRUCT_SIZE_OF (ed_bihash_kv_t, k) <=
+	       STRUCT_SIZE_OF (ed_bihash_kv_t, kv.key),
+	       "ed key needs to fit in bihash key");
+
 typedef struct snat_main_s
 {
   /* ICMP session match functions */
@@ -723,6 +746,7 @@ typedef struct snat_main_s
   ip_lookup_main_t *ip4_lookup_main;
   api_main_t *api_main;
 
+  clib_bihash_16_8_t ed_ext_ports;
 } snat_main_t;
 
 typedef struct
diff --git a/src/plugins/nat/nat44_cli.c b/src/plugins/nat/nat44_cli.c
index cdf94a8dc9d..6712b8b29a7 100644
--- a/src/plugins/nat/nat44_cli.c
+++ b/src/plugins/nat/nat44_cli.c
@@ -252,8 +252,11 @@ nat44_show_hash_commnad_fn (vlib_main_t * vm, unformat_input_t * input,
   }
 
   if (sm->endpoint_dependent)
-    vlib_cli_output (vm, "%U", format_bihash_16_8, &nam->affinity_hash,
-		     verbose);
+    {
+      vlib_cli_output (vm, "%U", format_bihash_16_8, &nam->affinity_hash,
+		       verbose);
+      vlib_cli_output (vm, "%U", format_bihash_16_8, &sm->ed_ext_ports, 0);
+    }
   return 0;
 }
 
diff --git a/src/plugins/nat/nat64.c b/src/plugins/nat/nat64.c
index 405fc84c7b8..0dbeb5f4171 100644
--- a/src/plugins/nat/nat64.c
+++ b/src/plugins/nat/nat64.c
@@ -311,7 +311,7 @@ nat64_add_del_pool_addr (u32 thread_index,
 	  fib_table_find_or_create_and_lock (FIB_PROTOCOL_IP6, vrf_id,
 					     nat_fib_src_hi);
 #define _(N, id, n, s) \
-      clib_bitmap_alloc (a->busy_##n##_port_bitmap, 65535); \
+      clib_memset (a->busy_##n##_port_refcounts, 0, sizeof(a->busy_##n##_port_refcounts)); \
       a->busy_##n##_ports = 0; \
       vec_validate_init_empty (a->busy_##n##_ports_per_thread, tm->n_vlib_mains - 1, 0);
       foreach_snat_protocol
@@ -334,10 +334,6 @@ nat64_add_del_pool_addr (u32 thread_index,
             vlib_set_simple_counter (&nm->total_sessions, db - nm->db, 0,
                                      db->st.st_entries_num);
           }
-#define _(N, id, n, s) \
-      clib_bitmap_free (a->busy_##n##_port_bitmap);
-      foreach_snat_protocol
-#undef _
         /* *INDENT-ON* */
       vec_del1 (nm->addr_pool, i);
     }
@@ -575,9 +571,8 @@ nat64_free_out_addr_and_port (struct nat64_db_s *db, ip4_address_t * addr,
 	{
 #define _(N, j, n, s) \
         case SNAT_PROTOCOL_##N: \
-          ASSERT (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, \
-                  port_host_byte_order) == 1); \
-          clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, port_host_byte_order, 0); \
+          ASSERT (a->busy_##n##_port_refcounts[port_host_byte_order] >= 1); \
+          --a->busy_##n##_port_refcounts[port_host_byte_order]; \
           a->busy_##n##_ports--; \
           a->busy_##n##_ports_per_thread[thread_index]--; \
           break;
@@ -712,11 +707,9 @@ nat64_add_del_static_bib_entry (ip6_address_t * in_addr,
 	    {
 #define _(N, j, n, s) \
             case SNAT_PROTOCOL_##N: \
-              if (clib_bitmap_get_no_check (a->busy_##n##_port_bitmap, \
-                                            out_port)) \
+              if (a->busy_##n##_port_refcounts[out_port]) \
                 return VNET_API_ERROR_INVALID_VALUE; \
-              clib_bitmap_set_no_check (a->busy_##n##_port_bitmap, \
-                                        out_port, 1); \
+	      ++a->busy_##n##_port_refcounts[out_port]; \
               if (out_port > 1024) \
                 { \
                   a->busy_##n##_ports++; \
diff --git a/src/plugins/nat/out2in_ed.c b/src/plugins/nat/out2in_ed.c
index 64f40cf1917..e1eda3208e3 100644
--- a/src/plugins/nat/out2in_ed.c
+++ b/src/plugins/nat/out2in_ed.c
@@ -131,6 +131,16 @@ nat44_o2i_ed_is_idle_session_cb (clib_bihash_kv_16_8_t * kv, void *arg)
       if (clib_bihash_add_del_16_8 (&tsm->in2out_ed, &ed_kv, 0))
 	nat_elog_warn ("in2out_ed key del failed");
 
+      ed_bihash_kv_t bihash_key;
+      clib_memset (&bihash_key, 0, sizeof (bihash_key));
+      bihash_key.k.dst_address = s->ext_host_addr.as_u32;
+      bihash_key.k.dst_port = s->ext_host_port;
+      bihash_key.k.src_address = s->out2in.addr.as_u32;
+      bihash_key.k.src_port = s->out2in.port;
+      bihash_key.k.protocol = s->out2in.protocol;
+      clib_bihash_add_del_16_8 (&sm->ed_ext_ports, &bihash_key.kv,
+				0 /* is_add */ );
+
       if (snat_is_unk_proto_session (s))
 	goto delete;