blob: 15fd7c7aeed83629a2d556079bb95a0c89f7184a [file] [log] [blame]
Florin Coras1c710452017-10-17 00:03:13 -07001/*
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
18u8 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
35u8
36RT (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
52RTT (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);
Dave Barachb7b92992018-10-17 10:38:51 -040056 clib_memset (rule, 0, sizeof (*rule));
Florin Coras1c710452017-10-17 00:03:13 -070057 return rule;
58}
59
60RTT (mma_rule) *
61RT (mma_rule_free) (RTT (mma_rules_table) * srt, RTT (mma_rule) * rule)
62{
63 pool_put (srt->rules, rule);
Dave Barachb7b92992018-10-17 10:38:51 -040064 clib_memset (rule, 0xfa, sizeof (*rule));
Florin Coras1c710452017-10-17 00:03:13 -070065 return rule;
66}
67
68RTT (mma_rule) *
69RT (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
76u32
77RT (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 */
89u32
90RT (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
Florin Corasc97a7392017-11-05 23:07:07 -080097 ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
Florin Coras1c710452017-10-17 00:03:13 -070098 rp = RT (mma_rules_table_get_rule) (srt, rule_index);
99 ASSERT (rp);
100
101 if (!RT (rule_is_match_for_key) (key, rp))
Florin Corasc97a7392017-11-05 23:07:07 -0800102 return MMA_TABLE_INVALID_INDEX;
Florin Coras1c710452017-10-17 00:03:13 -0700103 for (i = 0; i < vec_len (rp->next_indices); i++)
104 {
105 rv = RT (mma_rules_table_lookup) (srt, key, rp->next_indices[i]);
Florin Corasc97a7392017-11-05 23:07:07 -0800106 if (rv != MMA_TABLE_INVALID_INDEX)
Florin Coras1c710452017-10-17 00:03:13 -0700107 return (rv);
108 }
109 return (rp->action_index);
110}
111
112u32
113RT (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
Florin Corasc97a7392017-11-05 23:07:07 -0800121 ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
Florin Coras1c710452017-10-17 00:03:13 -0700122 rp = RT (mma_rules_table_get_rule) (srt, rule_index);
123 ASSERT (rp);
124
125 if (!RT (rule_is_match_for_key) (key, rp))
Florin Corasc97a7392017-11-05 23:07:07 -0800126 return MMA_TABLE_INVALID_INDEX;
Florin Coras1c710452017-10-17 00:03:13 -0700127 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]);
Florin Corasc97a7392017-11-05 23:07:07 -0800130 if (rv != MMA_TABLE_INVALID_INDEX)
Florin Coras1c710452017-10-17 00:03:13 -0700131 return (rv);
132 }
133 return rule_index;
134}
135
136static
137RTT (mma_rules_table) *
138RTT (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
149void 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
155int
156RT (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
209int
210RT (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
Florin Corasc97a7392017-11-05 23:07:07 -0800217 ASSERT (rule_index != MMA_TABLE_INVALID_INDEX);
Florin Coras1c710452017-10-17 00:03:13 -0700218 rp = RT (mma_rules_table_get_rule) (srt, rule_index);
219
220 if (!RT (rule_is_match_for_key) (&rule->match, rp))
Florin Corasc97a7392017-11-05 23:07:07 -0800221 return MMA_TABLE_INVALID_INDEX;
Florin Coras1c710452017-10-17 00:03:13 -0700222 if (RT (rule_is_exact_match) (rule, rp))
Florin Coras7999e832017-10-31 01:51:04 -0700223 {
224 if (rule_index == srt->root_index)
Florin Corasc97a7392017-11-05 23:07:07 -0800225 rp->action_index = MMA_TABLE_INVALID_INDEX;
Florin Coras7999e832017-10-31 01:51:04 -0700226 return 1;
227 }
Florin Coras1c710452017-10-17 00:03:13 -0700228 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 }
Florin Corasc97a7392017-11-05 23:07:07 -0800260 return MMA_TABLE_INVALID_INDEX;
Florin Coras1c710452017-10-17 00:03:13 -0700261}
262
263/*
264 * fd.io coding-style-patch-verification: ON
265 *
266 * Local Variables:
267 * eval: (c-set-style "gnu")
268 * End:
269 */