Line data    Source code

       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          89 : u8 RT (rule_is_exact_match) (RTT (mma_rule) * key, RTT (mma_rule) * r)
      19             : {
      20             :   int i;
      21             : 
      22         175 :   for (i = 0; i < ARRAY_LEN (key->match.as_u64); i++)
      23             :     {
      24         133 :       if (key->match.as_u64[i] != r->match.as_u64[i])
      25          47 :         return 0;
      26             :     }
      27         118 :   for (i = 0; i < ARRAY_LEN (key->mask.as_u64); i++)
      28             :     {
      29          80 :       if (key->mask.as_u64[i] != r->mask.as_u64[i])
      30           4 :         return 0;
      31             :     }
      32          38 :   return 1;
      33             : }
      34             : 
      35             : u8
      36         682 : RT (rule_is_match_for_key) (RTT (mma_mask_or_match) * key, RTT (mma_rule) * r)
      37             : {
      38         682 :   RTT (mma_mask_or_match) _tmp_key, *tkp = &_tmp_key;
      39             :   int i;
      40             : 
      41         682 :   *tkp = *key;
      42        2103 :   for (i = 0; i < ARRAY_LEN (tkp->as_u64); i++)
      43        1421 :     tkp->as_u64[i] &= r->mask.as_u64[i];
      44        2027 :   for (i = 0; i < ARRAY_LEN (tkp->as_u64); i++)
      45             :     {
      46        1392 :       if (tkp->as_u64[i] != r->match.as_u64[i])
      47          47 :         return 0;
      48             :     }
      49         635 :   return 1;
      50             : }
      51             : 
      52        3675 : RTT (mma_rule) * RT (mma_rules_table_rule_alloc) (RTT (mma_rules_table) * srt)
      53             : {
      54             :   RTT (mma_rule) * rule;
      55        3675 :   pool_get (srt->rules, rule);
      56        3675 :   clib_memset (rule, 0, sizeof (*rule));
      57        3675 :   return rule;
      58             : }
      59             : 
      60             : RTT (mma_rule) *
      61          21 : RT (mma_rule_free) (RTT (mma_rules_table) * srt, RTT (mma_rule) * rule)
      62             : {
      63          21 :   clib_memset (rule, 0xfa, sizeof (*rule));
      64          21 :   pool_put (srt->rules, rule);
      65          21 :   return rule;
      66             : }
      67             : 
      68          48 : void RT (mma_rules_table_free) (RTT (mma_rules_table) * srt)
      69             : {
      70          48 :   pool_free (srt->rules);
      71          48 : }
      72             : 
      73             : RTT (mma_rule) *
      74         726 : RT (mma_rules_table_get_rule) (RTT (mma_rules_table) * srt, u32 srt_index)
      75             : {
      76         726 :   if (!pool_is_free_index (srt->rules, srt_index))
      77         726 :     return (srt->rules + srt_index);
      78           0 :   return 0;
      79             : }
      80             : 
      81             : u32
      82        3696 : RT (mma_rules_table_rule_index) (RTT (mma_rules_table) * srt,
      83             :                                  RTT (mma_rule) * sr)
      84             : {
      85        3696 :   ASSERT (sr);
      86        3696 :   return (sr - srt->rules);
      87             : }
      88             : 
      89             : /**
      90             :  * Lookup key in table
      91             :  *
      92             :  * This should be optimized .. eventually
      93             :  */
      94             : u32
      95         553 : 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         553 :   ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
     103         553 :   rp = RT (mma_rules_table_get_rule) (srt, rule_index);
     104         553 :   ASSERT (rp);
     105             : 
     106         553 :   if (!RT (rule_is_match_for_key) (key, rp))
     107          18 :     return MMA_TABLE_INVALID_INDEX;
     108         554 :   for (i = 0; i < vec_len (rp->next_indices); i++)
     109             :     {
     110          71 :       rv = RT (mma_rules_table_lookup) (srt, key, rp->next_indices[i]);
     111          71 :       if (rv != MMA_TABLE_INVALID_INDEX)
     112          52 :         return (rv);
     113             :     }
     114         483 :   return (rp->action_index);
     115             : }
     116             : 
     117             : u32
     118          68 : 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          68 :   ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
     127          68 :   rp = RT (mma_rules_table_get_rule) (srt, rule_index);
     128          68 :   ASSERT (rp);
     129             : 
     130          68 :   if (!RT (rule_is_match_for_key) (key, rp))
     131          18 :     return MMA_TABLE_INVALID_INDEX;
     132          68 :   for (i = 0; i < vec_len (rp->next_indices); i++)
     133             :     {
     134          39 :       rv = RT (mma_rules_table_lookup_rule) (srt, key, rp->next_indices[i]);
     135          39 :       if (rv != MMA_TABLE_INVALID_INDEX)
     136          21 :         return (rv);
     137             :     }
     138          29 :   return rule_index;
     139             : }
     140             : 
     141             : static
     142             : RTT (mma_rules_table) *
     143             : RTT (sort_srt);
     144             : 
     145           0 :      int RT (mma_sort_indices) (void *e1, void *e2)
     146             : {
     147           0 :   u32 *ri1 = e1, *ri2 = e2;
     148             :   RTT (mma_rule) * rule1, *rule2;
     149           0 :   rule1 = RT (mma_rules_table_get_rule) (RTT (sort_srt), *ri1);
     150           0 :   rule2 = RT (mma_rules_table_get_rule) (RTT (sort_srt), *ri2);
     151           0 :   return RTT (sort_srt)->rule_cmp_fn (rule1, rule2);
     152             : }
     153             : 
     154           0 : void RT (mma_sort) (RTT (mma_rules_table) * srt, u32 * next_indices)
     155             : {
     156           0 :   RTT (sort_srt) = srt;
     157           0 :   vec_sort_with_function (next_indices, RT (mma_sort_indices));
     158           0 : }
     159             : 
     160             : int
     161          25 : RT (mma_rules_table_add_rule) (RTT (mma_rules_table) * srt,
     162             :                                RTT (mma_rule) * rule)
     163             : {
     164          25 :   u32 parent_index, i, *next_indices = 0, added = 0, rule_index;
     165             :   RTT (mma_rule) * parent, *child;
     166             : 
     167          25 :   rule_index = RT (mma_rules_table_rule_index) (srt, rule);
     168          25 :   parent_index = RT (mma_rules_table_lookup_rule) (srt, &rule->match,
     169             :                                                    srt->root_index);
     170          25 :   parent = RT (mma_rules_table_get_rule) (srt, parent_index);
     171          25 :   if (RT (rule_is_exact_match) (rule, parent))
     172             :     {
     173           4 :       parent->action_index = rule->action_index;
     174           4 :       RT (mma_rule_free) (srt, rule);
     175           4 :       return -1;
     176             :     }
     177             : 
     178          21 :   if (vec_len (parent->next_indices) == 0)
     179             :     {
     180          14 :       vec_add1 (parent->next_indices, rule_index);
     181          14 :       return 0;
     182             :     }
     183             : 
     184             :   /* Check if new rule is parent of some of the existing children */
     185          19 :   for (i = 0; i < vec_len (parent->next_indices); i++)
     186             :     {
     187          12 :       child = RT (mma_rules_table_get_rule) (srt, parent->next_indices[i]);
     188          12 :       if (RT (rule_is_match_for_key) (&child->match, rule))
     189             :         {
     190           3 :           vec_add1 (rule->next_indices, parent->next_indices[i]);
     191           3 :           if (!added)
     192             :             {
     193           3 :               vec_add1 (next_indices, rule_index);
     194           3 :               added = 1;
     195             :             }
     196             :         }
     197             :       else
     198             :         {
     199           9 :           if (!added && srt->rule_cmp_fn (rule, child) < 0)
     200             :             {
     201           2 :               vec_add1 (next_indices, rule_index);
     202           2 :               added = 1;
     203             :             }
     204           9 :           vec_add1 (next_indices, parent->next_indices[i]);
     205             :         }
     206             :     }
     207           7 :   if (!added)
     208           2 :     vec_add1 (next_indices, rule_index);
     209           7 :   vec_free (parent->next_indices);
     210           7 :   parent->next_indices = next_indices;
     211           7 :   return 0;
     212             : }
     213             : 
     214             : int
     215          49 : 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          49 :   ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
     223          49 :   rp = RT (mma_rules_table_get_rule) (srt, rule_index);
     224             : 
     225          49 :   if (!RT (rule_is_match_for_key) (&rule->match, rp))
     226           2 :     return MMA_TABLE_INVALID_INDEX;
     227          47 :   if (RT (rule_is_exact_match) (rule, rp))
     228             :     {
     229          17 :       if (rule_index == srt->root_index)
     230           0 :         rp->action_index = MMA_TABLE_INVALID_INDEX;
     231          17 :       return 1;
     232             :     }
     233          32 :   for (i = 0; i < vec_len (rp->next_indices); i++)
     234             :     {
     235          30 :       rv = RT (mma_rules_table_del_rule) (srt, rule, rp->next_indices[i]);
     236          30 :       if (rv == 1)
     237             :         {
     238             :           RTT (mma_rule) * child;
     239          17 :           u32 *next_indices = 0, *new_elts, left_to_add;
     240          17 :           child = RT (mma_rules_table_get_rule) (srt, rp->next_indices[i]);
     241          17 :           ASSERT (RT (rule_is_exact_match) (rule, child));
     242             : 
     243          17 :           if (i != 0)
     244             :             {
     245           1 :               vec_add2 (next_indices, new_elts, i);
     246           1 :               clib_memcpy_fast (new_elts, rp->next_indices, i * sizeof (u32));
     247             :             }
     248          17 :           if (vec_len (child->next_indices))
     249           5 :             vec_append (next_indices, child->next_indices);
     250          17 :           left_to_add = vec_len (rp->next_indices) - i - 1;
     251          17 :           if (left_to_add)
     252             :             {
     253           2 :               vec_add2 (next_indices, new_elts, left_to_add);
     254           2 :               clib_memcpy_fast (new_elts, &rp->next_indices[i + 1],
     255             :                                 left_to_add * sizeof (u32));
     256             :             }
     257          17 :           RT (mma_rule_free) (srt, child);
     258          17 :           vec_free (rp->next_indices);
     259          17 :           rp->next_indices = next_indices;
     260          17 :           return 0;
     261             :         }
     262          13 :       else if (rv == 0)
     263          11 :         return rv;
     264             :     }
     265           2 :   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             :  */