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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #include <vppinfra/error.h>
18 u8 RT (rule_is_exact_match) (RTT (mma_rule) * key, RTT (mma_rule) * r)
22 for (i = 0; i < ARRAY_LEN (key->match.as_u64); i++)
24 if (key->match.as_u64[i] != r->match.as_u64[i])
27 for (i = 0; i < ARRAY_LEN (key->mask.as_u64); i++)
29 if (key->mask.as_u64[i] != r->mask.as_u64[i])
36 RT (rule_is_match_for_key) (RTT (mma_mask_or_match) * key, RTT (mma_rule) * r)
38 RTT (mma_mask_or_match) _tmp_key, *tkp = &_tmp_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++)
46 if (tkp->as_u64[i] != r->match.as_u64[i])
52 RTT (mma_rule) * RT (mma_rules_table_rule_alloc) (RTT (mma_rules_table) * srt)
54 RTT (mma_rule) * rule;
55 pool_get (srt->rules, rule);
56 clib_memset (rule, 0, sizeof (*rule));
61 RT (mma_rule_free) (RTT (mma_rules_table) * srt, RTT (mma_rule) * rule)
63 clib_memset (rule, 0xfa, sizeof (*rule));
64 pool_put (srt->rules, rule);
68 void RT (mma_rules_table_free) (RTT (mma_rules_table) * srt)
70 pool_free (srt->rules);
74 RT (mma_rules_table_get_rule) (RTT (mma_rules_table) * srt, u32 srt_index)
76 if (!pool_is_free_index (srt->rules, srt_index))
77 return (srt->rules + srt_index);
82 RT (mma_rules_table_rule_index) (RTT (mma_rules_table) * srt,
86 return (sr - srt->rules);
92 * This should be optimized .. eventually
95 RT (mma_rules_table_lookup) (RTT (mma_rules_table) * srt,
96 RTT (mma_mask_or_match) * key, u32 rule_index)
102 ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
103 rp = RT (mma_rules_table_get_rule) (srt, rule_index);
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++)
110 rv = RT (mma_rules_table_lookup) (srt, key, rp->next_indices[i]);
111 if (rv != MMA_TABLE_INVALID_INDEX)
114 return (rp->action_index);
118 RT (mma_rules_table_lookup_rule) (RTT (mma_rules_table) * srt,
119 RTT (mma_mask_or_match) * key,
126 ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
127 rp = RT (mma_rules_table_get_rule) (srt, rule_index);
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++)
134 rv = RT (mma_rules_table_lookup_rule) (srt, key, rp->next_indices[i]);
135 if (rv != MMA_TABLE_INVALID_INDEX)
142 RTT (mma_rules_table) *
145 int RT (mma_sort_indices) (void *e1, void *e2)
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);
154 void RT (mma_sort) (RTT (mma_rules_table) * srt, u32 * next_indices)
156 RTT (sort_srt) = srt;
157 vec_sort_with_function (next_indices, RT (mma_sort_indices));
161 RT (mma_rules_table_add_rule) (RTT (mma_rules_table) * srt,
162 RTT (mma_rule) * rule)
164 u32 parent_index, i, *next_indices = 0, added = 0, rule_index;
165 RTT (mma_rule) * parent, *child;
167 rule_index = RT (mma_rules_table_rule_index) (srt, rule);
168 parent_index = RT (mma_rules_table_lookup_rule) (srt, &rule->match,
170 parent = RT (mma_rules_table_get_rule) (srt, parent_index);
171 if (RT (rule_is_exact_match) (rule, parent))
173 parent->action_index = rule->action_index;
174 RT (mma_rule_free) (srt, rule);
178 if (vec_len (parent->next_indices) == 0)
180 vec_add1 (parent->next_indices, rule_index);
184 /* Check if new rule is parent of some of the existing children */
185 for (i = 0; i < vec_len (parent->next_indices); i++)
187 child = RT (mma_rules_table_get_rule) (srt, parent->next_indices[i]);
188 if (RT (rule_is_match_for_key) (&child->match, rule))
190 vec_add1 (rule->next_indices, parent->next_indices[i]);
193 vec_add1 (next_indices, rule_index);
199 if (!added && srt->rule_cmp_fn (rule, child) < 0)
201 vec_add1 (next_indices, rule_index);
204 vec_add1 (next_indices, parent->next_indices[i]);
208 vec_add1 (next_indices, rule_index);
209 vec_free (parent->next_indices);
210 parent->next_indices = next_indices;
215 RT (mma_rules_table_del_rule) (RTT (mma_rules_table) * srt,
216 RTT (mma_rule) * rule, u32 rule_index)
222 ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
223 rp = RT (mma_rules_table_get_rule) (srt, rule_index);
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))
229 if (rule_index == srt->root_index)
230 rp->action_index = MMA_TABLE_INVALID_INDEX;
233 for (i = 0; i < vec_len (rp->next_indices); i++)
235 rv = RT (mma_rules_table_del_rule) (srt, rule, rp->next_indices[i]);
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));
245 vec_add2 (next_indices, new_elts, i);
246 clib_memcpy_fast (new_elts, rp->next_indices, i * sizeof (u32));
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;
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));
257 RT (mma_rule_free) (srt, child);
258 vec_free (rp->next_indices);
259 rp->next_indices = next_indices;
265 return MMA_TABLE_INVALID_INDEX;
269 * fd.io coding-style-patch-verification: ON
272 * eval: (c-set-style "gnu")