session: rules tables

This introduces 5-tuple lookup tables that may be used to implement
custom session layer actions at connection establishment time (session
layer perspective).

The rules table build mask-match-action lookup trees that for a given
5-tuple key return the action for the first longest match. If rules
overlap, ordering is established by tuple longest match with the
following descending priority: remote ip, local ip, remote port, local
port.

At this time, the only match action supported is to forward packets to
the application identified by the action.

Change-Id: Icbade6fac720fa3979820d50cd7d6137f8b635c3
Signed-off-by: Florin Coras <fcoras@cisco.com>

1 files changed, 265 insertions, 0 deletions

diff --git a/src/vnet/session/mma_template.c b/src/vnet/session/mma_template.c
new file mode 100644
index 00000000000..81333a73ee5
--- /dev/null
+++ b/src/vnet/session/mma_template.c
@@ -0,0 +1,265 @@
+/*
+ * Copyright (c) 2017 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+*/
+
+#include <vppinfra/error.h>
+
+u8 RT (rule_is_exact_match) (RTT (mma_rule) * key, RTT (mma_rule) * r)
+{
+  int i;
+
+  for (i = 0; i < ARRAY_LEN (key->match.as_u64); i++)
+    {
+      if (key->match.as_u64[i] != r->match.as_u64[i])
+	return 0;
+    }
+  for (i = 0; i < ARRAY_LEN (key->mask.as_u64); i++)
+    {
+      if (key->mask.as_u64[i] != r->mask.as_u64[i])
+	return 0;
+    }
+  return 1;
+}
+
+u8
+RT (rule_is_match_for_key) (RTT (mma_mask_or_match) * key, RTT (mma_rule) * r)
+{
+  RTT (mma_mask_or_match) _tmp_key, *tkp = &_tmp_key;
+  int i;
+
+  *tkp = *key;
+  for (i = 0; i < ARRAY_LEN (tkp->as_u64); i++)
+    tkp->as_u64[i] &= r->mask.as_u64[i];
+  for (i = 0; i < ARRAY_LEN (tkp->as_u64); i++)
+    {
+      if (tkp->as_u64[i] != r->match.as_u64[i])
+	return 0;
+    }
+  return 1;
+}
+
+RTT (mma_rule) * RT (mma_rules_table_rule_alloc) (RTT (mma_rules_table) * srt)
+{
+  RTT (mma_rule) * rule;
+  pool_get (srt->rules, rule);
+  memset (rule, 0, sizeof (*rule));
+  return rule;
+}
+
+RTT (mma_rule) *
+RT (mma_rule_free) (RTT (mma_rules_table) * srt, RTT (mma_rule) * rule)
+{
+  pool_put (srt->rules, rule);
+  memset (rule, 0xfa, sizeof (*rule));
+  return rule;
+}
+
+RTT (mma_rule) *
+RT (mma_rules_table_get_rule) (RTT (mma_rules_table) * srt, u32 srt_index)
+{
+  if (!pool_is_free_index (srt->rules, srt_index))
+    return (srt->rules + srt_index);
+  return 0;
+}
+
+u32
+RT (mma_rules_table_rule_index) (RTT (mma_rules_table) * srt,
+				 RTT (mma_rule) * sr)
+{
+  ASSERT (sr);
+  return (sr - srt->rules);
+}
+
+/**
+ * Lookup key in table
+ *
+ * This should be optimized .. eventually
+ */
+u32
+RT (mma_rules_table_lookup) (RTT (mma_rules_table) * srt,
+			     RTT (mma_mask_or_match) * key, u32 rule_index)
+{
+  RTT (mma_rule) * rp;
+  u32 rv;
+  int i;
+
+  ASSERT (rule_index != SESSION_RULES_TABLE_INVALID_INDEX);
+  rp = RT (mma_rules_table_get_rule) (srt, rule_index);
+  ASSERT (rp);
+
+  if (!RT (rule_is_match_for_key) (key, rp))
+    return ~0;
+  for (i = 0; i < vec_len (rp->next_indices); i++)
+    {
+      rv = RT (mma_rules_table_lookup) (srt, key, rp->next_indices[i]);
+      if (rv != ~0)
+	return (rv);
+    }
+  return (rp->action_index);
+}
+
+u32
+RT (mma_rules_table_lookup_rule) (RTT (mma_rules_table) * srt,
+				  RTT (mma_mask_or_match) * key,
+				  u32 rule_index)
+{
+  RTT (mma_rule) * rp;
+  u32 rv;
+  int i;
+
+  ASSERT (rule_index != SESSION_RULES_TABLE_INVALID_INDEX);
+  rp = RT (mma_rules_table_get_rule) (srt, rule_index);
+  ASSERT (rp);
+
+  if (!RT (rule_is_match_for_key) (key, rp))
+    return ~0;
+  for (i = 0; i < vec_len (rp->next_indices); i++)
+    {
+      rv = RT (mma_rules_table_lookup_rule) (srt, key, rp->next_indices[i]);
+      if (rv != ~0)
+	return (rv);
+    }
+  return rule_index;
+}
+
+static
+RTT (mma_rules_table) *
+RTT (sort_srt);
+
+     int RT (mma_sort_indices) (void *e1, void *e2)
+{
+  u32 *ri1 = e1, *ri2 = e2;
+  RTT (mma_rule) * rule1, *rule2;
+  rule1 = RT (mma_rules_table_get_rule) (RTT (sort_srt), *ri1);
+  rule2 = RT (mma_rules_table_get_rule) (RTT (sort_srt), *ri2);
+  return RTT (sort_srt)->rule_cmp_fn (rule1, rule2);
+}
+
+void RT (mma_sort) (RTT (mma_rules_table) * srt, u32 * next_indices)
+{
+  RTT (sort_srt) = srt;
+  vec_sort_with_function (next_indices, RT (mma_sort_indices));
+}
+
+int
+RT (mma_rules_table_add_rule) (RTT (mma_rules_table) * srt,
+			       RTT (mma_rule) * rule)
+{
+  u32 parent_index, i, *next_indices = 0, added = 0, rule_index;
+  RTT (mma_rule) * parent, *child;
+
+  rule_index = RT (mma_rules_table_rule_index) (srt, rule);
+  parent_index = RT (mma_rules_table_lookup_rule) (srt, &rule->match,
+						   srt->root_index);
+  parent = RT (mma_rules_table_get_rule) (srt, parent_index);
+  if (RT (rule_is_exact_match) (rule, parent))
+    {
+      parent->action_index = rule->action_index;
+      RT (mma_rule_free) (srt, rule);
+      return -1;
+    }
+
+  if (vec_len (parent->next_indices) == 0)
+    {
+      vec_add1 (parent->next_indices, rule_index);
+      return 0;
+    }
+
+  /* Check if new rule is parent of some of the existing children */
+  for (i = 0; i < vec_len (parent->next_indices); i++)
+    {
+      child = RT (mma_rules_table_get_rule) (srt, parent->next_indices[i]);
+      if (RT (rule_is_match_for_key) (&child->match, rule))
+	{
+	  vec_add1 (rule->next_indices, parent->next_indices[i]);
+	  if (!added)
+	    {
+	      vec_add1 (next_indices, rule_index);
+	      added = 1;
+	    }
+	}
+      else
+	{
+	  if (!added && srt->rule_cmp_fn (rule, child) < 0)
+	    {
+	      vec_add1 (next_indices, rule_index);
+	      added = 1;
+	    }
+	  vec_add1 (next_indices, parent->next_indices[i]);
+	}
+    }
+  if (!added)
+    vec_add1 (next_indices, rule_index);
+  vec_free (parent->next_indices);
+  parent->next_indices = next_indices;
+  return 0;
+}
+
+int
+RT (mma_rules_table_del_rule) (RTT (mma_rules_table) * srt,
+			       RTT (mma_rule) * rule, u32 rule_index)
+{
+  RTT (mma_rule) * rp;
+  u32 rv;
+  int i;
+
+  ASSERT (rule_index != SESSION_RULES_TABLE_INVALID_INDEX);
+  rp = RT (mma_rules_table_get_rule) (srt, rule_index);
+
+  if (!RT (rule_is_match_for_key) (&rule->match, rp))
+    return ~0;
+  if (RT (rule_is_exact_match) (rule, rp))
+    return 1;
+  for (i = 0; i < vec_len (rp->next_indices); i++)
+    {
+      rv = RT (mma_rules_table_del_rule) (srt, rule, rp->next_indices[i]);
+      if (rv == 1)
+	{
+	  RTT (mma_rule) * child;
+	  u32 *next_indices = 0, *new_elts, left_to_add;
+	  child = RT (mma_rules_table_get_rule) (srt, rp->next_indices[i]);
+	  ASSERT (RT (rule_is_exact_match) (rule, child));
+
+	  if (i != 0)
+	    {
+	      vec_add2 (next_indices, new_elts, i);
+	      clib_memcpy (new_elts, rp->next_indices, i * sizeof (u32));
+	    }
+	  if (vec_len (child->next_indices))
+	    vec_append (next_indices, child->next_indices);
+	  left_to_add = vec_len (rp->next_indices) - i - 1;
+	  if (left_to_add)
+	    {
+	      vec_add2 (next_indices, new_elts, left_to_add);
+	      clib_memcpy (new_elts, &rp->next_indices[i + 1],
+			   left_to_add * sizeof (u32));
+	    }
+	  RT (mma_rule_free) (srt, child);
+	  vec_free (rp->next_indices);
+	  rp->next_indices = next_indices;
+	  return 0;
+	}
+      else if (rv == 0)
+	return rv;
+    }
+  return ~0;
+}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */