ipsec: introduce spd fast path types

This patch introdcues basic types supporting fast path lookup.
Fast path performs policy matching with use of hash lookup
(particularly bihash tries has been used for that purpose). Fast path
lookup addresses situation where huge number of policies is created
(~100k or more). In such scenario adding/removing a policy
and policy matching is not efficient and poorly scales (for example
adding 500k policies takes a few hours. Also lookup time
increases significantly). With fast path adding and matching up to
1M flows scales up linearly (adding 1M of policies takes about 150s
on the test machine vs many hours in case of original implementation,
also matching time is significantly improved). Fast path will not
deal well with a huge number of policies that are spanning large
ip/port ranges. Large range will be masked out almost entirely leaving
only a few bits for calculating the hash key. Such keys will tend to
 gather much more policies than other keys and hash will match most of
the packets anihilating advantages of hashing. Having said that
we also think that it is not the real life scenario.

Type: feature
Signed-off-by: Piotr Bronowski <piotrx.bronowski@intel.com>
Change-Id: I600dae5111a37768ed4b23aa18426e66bbf7b529

1 files changed, 63 insertions, 0 deletions

diff --git a/src/vnet/ipsec/ipsec_spd_policy.h b/src/vnet/ipsec/ipsec_spd_policy.h
index fc9c23a4c62..8b78939cafa 100644
--- a/src/vnet/ipsec/ipsec_spd_policy.h
+++ b/src/vnet/ipsec/ipsec_spd_policy.h
@@ -15,7 +15,13 @@
 #ifndef __IPSEC_SPD_POLICY_H__
 #define __IPSEC_SPD_POLICY_H__
 
+#include <vppinfra/bihash_40_8.h>
+#include <vppinfra/bihash_16_8.h>
 #include <vnet/ipsec/ipsec_spd.h>
+/**
+ * calculated as max number of flows (2^10) divided by KVP_PER_PAGE (4)
+ */
+#define IPSEC_FP_HASH_LOOKUP_HASH_BUCKETS (1 << 8)
 
 #define IPSEC_POLICY_PROTOCOL_ANY IP_PROTOCOL_RESERVED
 
@@ -93,6 +99,63 @@ extern int ipsec_policy_mk_type (bool is_outbound,
 				 ipsec_policy_action_t action,
 				 ipsec_spd_policy_type_t * type);
 
+/* A 5-tuple used to calculate the bihash entry  */
+typedef union
+{
+  struct
+  {
+    union
+    {
+      struct
+      {
+	u32 l3_zero_pad[6];
+	ip4_address_t laddr;
+	ip4_address_t raddr;
+      };
+      ip6_address_t ip6_laddr;
+      ip6_address_t ip6_raddr;
+    };
+
+    u16 lport;
+    u16 rport;
+    u16 protocol;
+    u16 is_ipv6;
+  };
+  /* for ipv6 */
+  clib_bihash_kv_40_8_t kv_40_8;
+  /* for ipv4 */
+  struct
+  {
+    u64 padding_for_kv_16_8[3];
+    clib_bihash_kv_16_8_t kv_16_8;
+  };
+} ipsec_fp_5tuple_t;
+
+/*
+ * An element describing a particular policy  mask,
+ * and refcount of policies with same mask.
+ */
+typedef struct
+{
+  /** Required for pool_get_aligned */
+  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
+  ipsec_fp_5tuple_t mask;
+  u32 refcount; /* counts how many policies use this mask */
+} ipsec_fp_mask_type_entry_t;
+
+/*
+ * Bihash lookup value,
+ * contains an unordered vector of policies indices in policy pool.
+ */
+typedef union
+{
+  u64 as_u64;
+  struct
+  {
+    u32 *fp_policies_ids;
+  };
+} ipsec_fp_lookup_value_t;
+
 #endif /* __IPSEC_SPD_POLICY_H__ */
 
 /*