FD.io VPP  v18.10-34-gcce845e
Vector Packet Processing
mma_template.c
Go to the documentation of this file.
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  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  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))
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))
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))
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  }
261 }
262 
263 /*
264  * fd.io coding-style-patch-verification: ON
265  *
266  * Local Variables:
267  * eval: (c-set-style "gnu")
268  * End:
269  */
u32 RT() mma_rules_table_lookup(RTT(mma_rules_table)*srt, RTT(mma_mask_or_match)*key, u32 rule_index)
Lookup key in table.
Definition: mma_template.c:90
void RT() mma_sort(RTT(mma_rules_table)*srt, u32 *next_indices)
Definition: mma_template.c:149
u8 RT() rule_is_exact_match(RTT(mma_rule)*key, RTT(mma_rule)*r)
Definition: mma_template.c:18
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:523
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:562
for(i=1;i<=collision_buckets;i++)
int i
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:228
unsigned char u8
Definition: types.h:56
RTT(mma_rule)
Definition: mma_template.c:52
u32 RT() mma_rules_table_rule_index(RTT(mma_rules_table)*srt, RTT(mma_rule)*sr)
Definition: mma_template.c:77
memset(h->entries, 0, sizeof(h->entries[0])*entries)
unsigned int u32
Definition: types.h:88
u32 RT() mma_rules_table_lookup_rule(RTT(mma_rules_table)*srt, RTT(mma_mask_or_match)*key, u32 rule_index)
Definition: mma_template.c:113
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:274
#define RT(a)
Definition: mma_template.h:27
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:339
u8 RT() rule_is_match_for_key(RTT(mma_mask_or_match)*key, RTT(mma_rule)*r)
Definition: mma_template.c:36
#define clib_memcpy(a, b, c)
Definition: string.h:75
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:271
#define ARRAY_LEN(x)
Definition: clib.h:61
#define ASSERT(truth)
int RT() mma_rules_table_add_rule(RTT(mma_rules_table)*srt, RTT(mma_rule)*rule)
Definition: mma_template.c:156
#define vec_append(v1, v2)
Append v2 after v1.
Definition: vec.h:820
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
Definition: vec.h:982
int RT() mma_rules_table_del_rule(RTT(mma_rules_table)*srt, RTT(mma_rule)*rule, u32 rule_index)
Definition: mma_template.c:210
u32 srt_index
Definition: mma_template.h:80
#define MMA_TABLE_INVALID_INDEX
Definition: mma_template.h:33