src/vnet/session/mma_template.c

   1 /*
   2  * Copyright (c) 2017 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14 */
  15
  16 #include <vppinfra/error.h>
  17
  18 u8 RT (rule_is_exact_match) (RTT (mma_rule) * key, RTT (mma_rule) * r)
  19 {
  20   int i;
  21
  22   for (i = 0; i < ARRAY_LEN (key->match.as_u64); i++)
  23     {
  24       if (key->match.as_u64[i] != r->match.as_u64[i])
  25         return 0;
  26     }
  27   for (i = 0; i < ARRAY_LEN (key->mask.as_u64); i++)
  28     {
  29       if (key->mask.as_u64[i] != r->mask.as_u64[i])
  30         return 0;
  31     }
  32   return 1;
  33 }
  34
  35 u8
  36 RT (rule_is_match_for_key) (RTT (mma_mask_or_match) * key, RTT (mma_rule) * r)
  37 {
  38   RTT (mma_mask_or_match) _tmp_key, *tkp = &_tmp_key;
  39   int i;
  40
  41   *tkp = *key;
  42   for (i = 0; i < ARRAY_LEN (tkp->as_u64); i++)
  43     tkp->as_u64[i] &= r->mask.as_u64[i];
  44   for (i = 0; i < ARRAY_LEN (tkp->as_u64); i++)
  45     {
  46       if (tkp->as_u64[i] != r->match.as_u64[i])
  47         return 0;
  48     }
  49   return 1;
  50 }
  51
  52 RTT (mma_rule) * RT (mma_rules_table_rule_alloc) (RTT (mma_rules_table) * srt)
  53 {
  54   RTT (mma_rule) * rule;
  55   pool_get (srt->rules, rule);
  56   clib_memset (rule, 0, sizeof (*rule));
  57   return rule;
  58 }
  59
  60 RTT (mma_rule) *
  61 RT (mma_rule_free) (RTT (mma_rules_table) * srt, RTT (mma_rule) * rule)
  62 {
  63   pool_put (srt->rules, rule);
  64   clib_memset (rule, 0xfa, sizeof (*rule));
  65   return rule;
  66 }
  67
  68 RTT (mma_rule) *
  69 RT (mma_rules_table_get_rule) (RTT (mma_rules_table) * srt, u32 srt_index)
  70 {
  71   if (!pool_is_free_index (srt->rules, srt_index))
  72     return (srt->rules + srt_index);
  73   return 0;
  74 }
  75
  76 u32
  77 RT (mma_rules_table_rule_index) (RTT (mma_rules_table) * srt,
  78                                  RTT (mma_rule) * sr)
  79 {
  80   ASSERT (sr);
  81   return (sr - srt->rules);
  82 }
  83
  84 /**
  85  * Lookup key in table
  86  *
  87  * This should be optimized .. eventually
  88  */
  89 u32
  90 RT (mma_rules_table_lookup) (RTT (mma_rules_table) * srt,
  91                              RTT (mma_mask_or_match) * key, u32 rule_index)
  92 {
  93   RTT (mma_rule) * rp;
  94   u32 rv;
  95   int i;
  96
  97   ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
  98   rp = RT (mma_rules_table_get_rule) (srt, rule_index);
  99   ASSERT (rp);
 100
 101   if (!RT (rule_is_match_for_key) (key, rp))
 102     return MMA_TABLE_INVALID_INDEX;
 103   for (i = 0; i < vec_len (rp->next_indices); i++)
 104     {
 105       rv = RT (mma_rules_table_lookup) (srt, key, rp->next_indices[i]);
 106       if (rv != MMA_TABLE_INVALID_INDEX)
 107         return (rv);
 108     }
 109   return (rp->action_index);
 110 }
 111
 112 u32
 113 RT (mma_rules_table_lookup_rule) (RTT (mma_rules_table) * srt,
 114                                   RTT (mma_mask_or_match) * key,
 115                                   u32 rule_index)
 116 {
 117   RTT (mma_rule) * rp;
 118   u32 rv;
 119   int i;
 120
 121   ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
 122   rp = RT (mma_rules_table_get_rule) (srt, rule_index);
 123   ASSERT (rp);
 124
 125   if (!RT (rule_is_match_for_key) (key, rp))
 126     return MMA_TABLE_INVALID_INDEX;
 127   for (i = 0; i < vec_len (rp->next_indices); i++)
 128     {
 129       rv = RT (mma_rules_table_lookup_rule) (srt, key, rp->next_indices[i]);
 130       if (rv != MMA_TABLE_INVALID_INDEX)
 131         return (rv);
 132     }
 133   return rule_index;
 134 }
 135
 136 static
 137 RTT (mma_rules_table) *
 138 RTT (sort_srt);
 139
 140      int RT (mma_sort_indices) (void *e1, void *e2)
 141 {
 142   u32 *ri1 = e1, *ri2 = e2;
 143   RTT (mma_rule) * rule1, *rule2;
 144   rule1 = RT (mma_rules_table_get_rule) (RTT (sort_srt), *ri1);
 145   rule2 = RT (mma_rules_table_get_rule) (RTT (sort_srt), *ri2);
 146   return RTT (sort_srt)->rule_cmp_fn (rule1, rule2);
 147 }
 148
 149 void RT (mma_sort) (RTT (mma_rules_table) * srt, u32 * next_indices)
 150 {
 151   RTT (sort_srt) = srt;
 152   vec_sort_with_function (next_indices, RT (mma_sort_indices));
 153 }
 154
 155 int
 156 RT (mma_rules_table_add_rule) (RTT (mma_rules_table) * srt,
 157                                RTT (mma_rule) * rule)
 158 {
 159   u32 parent_index, i, *next_indices = 0, added = 0, rule_index;
 160   RTT (mma_rule) * parent, *child;
 161
 162   rule_index = RT (mma_rules_table_rule_index) (srt, rule);
 163   parent_index = RT (mma_rules_table_lookup_rule) (srt, &rule->match,
 164                                                    srt->root_index);
 165   parent = RT (mma_rules_table_get_rule) (srt, parent_index);
 166   if (RT (rule_is_exact_match) (rule, parent))
 167     {
 168       parent->action_index = rule->action_index;
 169       RT (mma_rule_free) (srt, rule);
 170       return -1;
 171     }
 172
 173   if (vec_len (parent->next_indices) == 0)
 174     {
 175       vec_add1 (parent->next_indices, rule_index);
 176       return 0;
 177     }
 178
 179   /* Check if new rule is parent of some of the existing children */
 180   for (i = 0; i < vec_len (parent->next_indices); i++)
 181     {
 182       child = RT (mma_rules_table_get_rule) (srt, parent->next_indices[i]);
 183       if (RT (rule_is_match_for_key) (&child->match, rule))
 184         {
 185           vec_add1 (rule->next_indices, parent->next_indices[i]);
 186           if (!added)
 187             {
 188               vec_add1 (next_indices, rule_index);
 189               added = 1;
 190             }
 191         }
 192       else
 193         {
 194           if (!added && srt->rule_cmp_fn (rule, child) < 0)
 195             {
 196               vec_add1 (next_indices, rule_index);
 197               added = 1;
 198             }
 199           vec_add1 (next_indices, parent->next_indices[i]);
 200         }
 201     }
 202   if (!added)
 203     vec_add1 (next_indices, rule_index);
 204   vec_free (parent->next_indices);
 205   parent->next_indices = next_indices;
 206   return 0;
 207 }
 208
 209 int
 210 RT (mma_rules_table_del_rule) (RTT (mma_rules_table) * srt,
 211                                RTT (mma_rule) * rule, u32 rule_index)
 212 {
 213   RTT (mma_rule) * rp;
 214   u32 rv;
 215   int i;
 216
 217   ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
 218   rp = RT (mma_rules_table_get_rule) (srt, rule_index);
 219
 220   if (!RT (rule_is_match_for_key) (&rule->match, rp))
 221     return MMA_TABLE_INVALID_INDEX;
 222   if (RT (rule_is_exact_match) (rule, rp))
 223     {
 224       if (rule_index == srt->root_index)
 225         rp->action_index = MMA_TABLE_INVALID_INDEX;
 226       return 1;
 227     }
 228   for (i = 0; i < vec_len (rp->next_indices); i++)
 229     {
 230       rv = RT (mma_rules_table_del_rule) (srt, rule, rp->next_indices[i]);
 231       if (rv == 1)
 232         {
 233           RTT (mma_rule) * child;
 234           u32 *next_indices = 0, *new_elts, left_to_add;
 235           child = RT (mma_rules_table_get_rule) (srt, rp->next_indices[i]);
 236           ASSERT (RT (rule_is_exact_match) (rule, child));
 237
 238           if (i != 0)
 239             {
 240               vec_add2 (next_indices, new_elts, i);
 241               clib_memcpy (new_elts, rp->next_indices, i * sizeof (u32));
 242             }
 243           if (vec_len (child->next_indices))
 244             vec_append (next_indices, child->next_indices);
 245           left_to_add = vec_len (rp->next_indices) - i - 1;
 246           if (left_to_add)
 247             {
 248               vec_add2 (next_indices, new_elts, left_to_add);
 249               clib_memcpy (new_elts, &rp->next_indices[i + 1],
 250                            left_to_add * sizeof (u32));
 251             }
 252           RT (mma_rule_free) (srt, child);
 253           vec_free (rp->next_indices);
 254           rp->next_indices = next_indices;
 255           return 0;
 256         }
 257       else if (rv == 0)
 258         return rv;
 259     }
 260   return MMA_TABLE_INVALID_INDEX;
 261 }
 262
 263 /*
 264  * fd.io coding-style-patch-verification: ON
 265  *
 266  * Local Variables:
 267  * eval: (c-set-style "gnu")
 268  * End:
 269  */