Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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); |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame^] | 56 | clib_memset (rule, 0, sizeof (*rule)); |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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); |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame^] | 64 | clib_memset (rule, 0xfa, sizeof (*rule)); |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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 | |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 97 | ASSERT (rule_index != MMA_TABLE_INVALID_INDEX); |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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)) |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 102 | return MMA_TABLE_INVALID_INDEX; |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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]); |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 106 | if (rv != MMA_TABLE_INVALID_INDEX) |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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 | |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 121 | ASSERT (rule_index != MMA_TABLE_INVALID_INDEX); |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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)) |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 126 | return MMA_TABLE_INVALID_INDEX; |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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]); |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 130 | if (rv != MMA_TABLE_INVALID_INDEX) |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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 | |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 217 | ASSERT (rule_index != MMA_TABLE_INVALID_INDEX); |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 218 | rp = RT (mma_rules_table_get_rule) (srt, rule_index); |
| 219 | |
| 220 | if (!RT (rule_is_match_for_key) (&rule->match, rp)) |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 221 | return MMA_TABLE_INVALID_INDEX; |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 222 | if (RT (rule_is_exact_match) (rule, rp)) |
Florin Coras | 7999e83 | 2017-10-31 01:51:04 -0700 | [diff] [blame] | 223 | { |
| 224 | if (rule_index == srt->root_index) |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 225 | rp->action_index = MMA_TABLE_INVALID_INDEX; |
Florin Coras | 7999e83 | 2017-10-31 01:51:04 -0700 | [diff] [blame] | 226 | return 1; |
| 227 | } |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 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 | } |
Florin Coras | c97a739 | 2017-11-05 23:07:07 -0800 | [diff] [blame] | 260 | return MMA_TABLE_INVALID_INDEX; |
Florin Coras | 1c71045 | 2017-10-17 00:03:13 -0700 | [diff] [blame] | 261 | } |
| 262 | |
| 263 | /* |
| 264 | * fd.io coding-style-patch-verification: ON |
| 265 | * |
| 266 | * Local Variables: |
| 267 | * eval: (c-set-style "gnu") |
| 268 | * End: |
| 269 | */ |