src/vnet/session/mma_template.c

   1 /*
   2  * Copyright (c) 2017-2019 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   clib_memset (rule, 0xfa, sizeof (*rule));
  64   pool_put (srt->rules, rule);
  65   return rule;
  66 }
  67
  68 void RT (mma_rules_table_free) (RTT (mma_rules_table) * srt)
  69 {
  70   pool_free (srt->rules);
  71 }
  72
  73 RTT (mma_rule) *
  74 RT (mma_rules_table_get_rule) (RTT (mma_rules_table) * srt, u32 srt_index)
  75 {
  76   if (!pool_is_free_index (srt->rules, srt_index))
  77     return (srt->rules + srt_index);
  78   return 0;
  79 }
  80
  81 u32
  82 RT (mma_rules_table_rule_index) (RTT (mma_rules_table) * srt,
  83                                  RTT (mma_rule) * sr)
  84 {
  85   ASSERT (sr);
  86   return (sr - srt->rules);
  87 }
  88
  89 /**
  90  * Lookup key in table
  91  *
  92  * This should be optimized .. eventually
  93  */
  94 u32
  95 RT (mma_rules_table_lookup) (RTT (mma_rules_table) * srt,
  96                              RTT (mma_mask_or_match) * key, u32 rule_index)
  97 {
  98   RTT (mma_rule) * rp;
  99   u32 rv;
 100   int i;
 101
 102   ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
 103   rp = RT (mma_rules_table_get_rule) (srt, rule_index);
 104   ASSERT (rp);
 105
 106   if (!RT (rule_is_match_for_key) (key, rp))
 107     return MMA_TABLE_INVALID_INDEX;
 108   for (i = 0; i < vec_len (rp->next_indices); i++)
 109     {
 110       rv = RT (mma_rules_table_lookup) (srt, key, rp->next_indices[i]);
 111       if (rv != MMA_TABLE_INVALID_INDEX)
 112         return (rv);
 113     }
 114   return (rp->action_index);
 115 }
 116
 117 u32
 118 RT (mma_rules_table_lookup_rule) (RTT (mma_rules_table) * srt,
 119                                   RTT (mma_mask_or_match) * key,
 120                                   u32 rule_index)
 121 {
 122   RTT (mma_rule) * rp;
 123   u32 rv;
 124   int i;
 125
 126   ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
 127   rp = RT (mma_rules_table_get_rule) (srt, rule_index);
 128   ASSERT (rp);
 129
 130   if (!RT (rule_is_match_for_key) (key, rp))
 131     return MMA_TABLE_INVALID_INDEX;
 132   for (i = 0; i < vec_len (rp->next_indices); i++)
 133     {
 134       rv = RT (mma_rules_table_lookup_rule) (srt, key, rp->next_indices[i]);
 135       if (rv != MMA_TABLE_INVALID_INDEX)
 136         return (rv);
 137     }
 138   return rule_index;
 139 }
 140
 141 static
 142 RTT (mma_rules_table) *
 143 RTT (sort_srt);
 144
 145      int RT (mma_sort_indices) (void *e1, void *e2)
 146 {
 147   u32 *ri1 = e1, *ri2 = e2;
 148   RTT (mma_rule) * rule1, *rule2;
 149   rule1 = RT (mma_rules_table_get_rule) (RTT (sort_srt), *ri1);
 150   rule2 = RT (mma_rules_table_get_rule) (RTT (sort_srt), *ri2);
 151   return RTT (sort_srt)->rule_cmp_fn (rule1, rule2);
 152 }
 153
 154 void RT (mma_sort) (RTT (mma_rules_table) * srt, u32 * next_indices)
 155 {
 156   RTT (sort_srt) = srt;
 157   vec_sort_with_function (next_indices, RT (mma_sort_indices));
 158 }
 159
 160 int
 161 RT (mma_rules_table_add_rule) (RTT (mma_rules_table) * srt,
 162                                RTT (mma_rule) * rule)
 163 {
 164   u32 parent_index, i, *next_indices = 0, added = 0, rule_index;
 165   RTT (mma_rule) * parent, *child;
 166
 167   rule_index = RT (mma_rules_table_rule_index) (srt, rule);
 168   parent_index = RT (mma_rules_table_lookup_rule) (srt, &rule->match,
 169                                                    srt->root_index);
 170   parent = RT (mma_rules_table_get_rule) (srt, parent_index);
 171   if (RT (rule_is_exact_match) (rule, parent))
 172     {
 173       parent->action_index = rule->action_index;
 174       RT (mma_rule_free) (srt, rule);
 175       return -1;
 176     }
 177
 178   if (vec_len (parent->next_indices) == 0)
 179     {
 180       vec_add1 (parent->next_indices, rule_index);
 181       return 0;
 182     }
 183
 184   /* Check if new rule is parent of some of the existing children */
 185   for (i = 0; i < vec_len (parent->next_indices); i++)
 186     {
 187       child = RT (mma_rules_table_get_rule) (srt, parent->next_indices[i]);
 188       if (RT (rule_is_match_for_key) (&child->match, rule))
 189         {
 190           vec_add1 (rule->next_indices, parent->next_indices[i]);
 191           if (!added)
 192             {
 193               vec_add1 (next_indices, rule_index);
 194               added = 1;
 195             }
 196         }
 197       else
 198         {
 199           if (!added && srt->rule_cmp_fn (rule, child) < 0)
 200             {
 201               vec_add1 (next_indices, rule_index);
 202               added = 1;
 203             }
 204           vec_add1 (next_indices, parent->next_indices[i]);
 205         }
 206     }
 207   if (!added)
 208     vec_add1 (next_indices, rule_index);
 209   vec_free (parent->next_indices);
 210   parent->next_indices = next_indices;
 211   return 0;
 212 }
 213
 214 int
 215 RT (mma_rules_table_del_rule) (RTT (mma_rules_table) * srt,
 216                                RTT (mma_rule) * rule, u32 rule_index)
 217 {
 218   RTT (mma_rule) * rp;
 219   u32 rv;
 220   int i;
 221
 222   ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
 223   rp = RT (mma_rules_table_get_rule) (srt, rule_index);
 224
 225   if (!RT (rule_is_match_for_key) (&rule->match, rp))
 226     return MMA_TABLE_INVALID_INDEX;
 227   if (RT (rule_is_exact_match) (rule, rp))
 228     {
 229       if (rule_index == srt->root_index)
 230         rp->action_index = MMA_TABLE_INVALID_INDEX;
 231       return 1;
 232     }
 233   for (i = 0; i < vec_len (rp->next_indices); i++)
 234     {
 235       rv = RT (mma_rules_table_del_rule) (srt, rule, rp->next_indices[i]);
 236       if (rv == 1)
 237         {
 238           RTT (mma_rule) * child;
 239           u32 *next_indices = 0, *new_elts, left_to_add;
 240           child = RT (mma_rules_table_get_rule) (srt, rp->next_indices[i]);
 241           ASSERT (RT (rule_is_exact_match) (rule, child));
 242
 243           if (i != 0)
 244             {
 245               vec_add2 (next_indices, new_elts, i);
 246               clib_memcpy_fast (new_elts, rp->next_indices, i * sizeof (u32));
 247             }
 248           if (vec_len (child->next_indices))
 249             vec_append (next_indices, child->next_indices);
 250           left_to_add = vec_len (rp->next_indices) - i - 1;
 251           if (left_to_add)
 252             {
 253               vec_add2 (next_indices, new_elts, left_to_add);
 254               clib_memcpy_fast (new_elts, &rp->next_indices[i + 1],
 255                                 left_to_add * sizeof (u32));
 256             }
 257           RT (mma_rule_free) (srt, child);
 258           vec_free (rp->next_indices);
 259           rp->next_indices = next_indices;
 260           return 0;
 261         }
 262       else if (rv == 0)
 263         return rv;
 264     }
 265   return MMA_TABLE_INVALID_INDEX;
 266 }
 267
 268 /*
 269  * fd.io coding-style-patch-verification: ON
 270  *
 271  * Local Variables:
 272  * eval: (c-set-style "gnu")
 273  * End:
 274  */