]>
Commit | Line | Data |
---|---|---|
38c449e0 | 1 | /* |
fc02ecc7 | 2 | * Copyright (c) 2014, 2015 Nicira, Inc. |
38c449e0 JR |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
15 | */ | |
16 | ||
17 | #ifndef CLASSIFIER_PRIVATE_H | |
18 | #define CLASSIFIER_PRIVATE_H 1 | |
19 | ||
c501b427 | 20 | #include "cmap.h" |
38c449e0 JR |
21 | #include "flow.h" |
22 | #include "hash.h" | |
c501b427 | 23 | #include "rculist.h" |
38c449e0 JR |
24 | #include "tag.h" |
25 | ||
26 | /* Classifier internal definitions, subject to change at any time. */ | |
27 | ||
28 | /* A set of rules that all have the same fields wildcarded. */ | |
29 | struct cls_subtable { | |
fccd7c09 JR |
30 | struct cmap_node cmap_node; /* Within classifier's 'subtables_map'. */ |
31 | ||
de4ad4a2 | 32 | /* These fields are only used by writers. */ |
fccd7c09 JR |
33 | int max_priority; /* Max priority of any rule in subtable. */ |
34 | unsigned int max_count; /* Count of max_priority rules. */ | |
38c449e0 | 35 | |
de4ad4a2 JR |
36 | /* Accessed by iterators. */ |
37 | struct rculist rules_list; /* Unordered. */ | |
38 | ||
f47eef15 JR |
39 | /* Identical, but lower priority rules are not inserted to any of the |
40 | * following data structures. */ | |
41 | ||
38c449e0 | 42 | /* These fields are accessed by readers who care about wildcarding. */ |
f80028fe JR |
43 | const tag_type tag; /* Tag generated from mask for partitioning. */ |
44 | const uint8_t n_indices; /* How many indices to use. */ | |
d70e8c28 | 45 | const uint8_t index_ofs[CLS_MAX_INDICES]; /* u64 segment boundaries. */ |
38c449e0 JR |
46 | unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask' |
47 | * (runtime configurable). */ | |
f80028fe | 48 | const int ports_mask_len; |
38c449e0 JR |
49 | struct cmap indices[CLS_MAX_INDICES]; /* Staged lookup indices. */ |
50 | rcu_trie_ptr ports_trie; /* NULL if none. */ | |
51 | ||
52 | /* These fields are accessed by all readers. */ | |
f80028fe JR |
53 | struct cmap rules; /* Contains 'cls_match'es. */ |
54 | const struct minimask mask; /* Wildcards for fields. */ | |
38c449e0 JR |
55 | /* 'mask' must be the last field. */ |
56 | }; | |
57 | ||
58 | /* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata | |
59 | * field) with tags for the "cls_subtable"s that contain rules that match that | |
60 | * metadata value. */ | |
61 | struct cls_partition { | |
62 | struct cmap_node cmap_node; /* In struct classifier's 'partitions' map. */ | |
63 | ovs_be64 metadata; /* metadata value for this partition. */ | |
64 | tag_type tags; /* OR of each flow's cls_subtable tag. */ | |
fccd7c09 | 65 | struct tag_tracker tracker; /* Tracks the bits in 'tags'. */ |
38c449e0 JR |
66 | }; |
67 | ||
8f8023b3 JR |
68 | /* Internal representation of a rule in a "struct cls_subtable". |
69 | * | |
70 | * The 'next' member is an element in a singly linked, null-terminated list. | |
71 | * This list links together identical "cls_match"es in order of decreasing | |
72 | * priority. The classifier code maintains the invariant that at most one rule | |
73 | * of a given priority is visible for any given lookup version. | |
74 | */ | |
38c449e0 | 75 | struct cls_match { |
f80028fe | 76 | /* Accessed by everybody. */ |
8f8023b3 JR |
77 | OVSRCU_TYPE(struct cls_match *) next; /* Equal, lower-priority matches. */ |
78 | OVSRCU_TYPE(struct cls_conjunction_set *) conj_set; | |
38c449e0 JR |
79 | |
80 | /* Accessed only by writers. */ | |
fccd7c09 | 81 | struct cls_partition *partition; |
38c449e0 JR |
82 | |
83 | /* Accessed by readers interested in wildcarding. */ | |
f80028fe | 84 | const int priority; /* Larger numbers are higher priorities. */ |
38c449e0 JR |
85 | struct cmap_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's |
86 | * 'indices'. */ | |
87 | /* Accessed by all readers. */ | |
88 | struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */ | |
2b7b1427 JR |
89 | |
90 | /* Controls rule's visibility to lookups. | |
91 | * | |
92 | * When 'visibility' is: | |
93 | * | |
94 | * > 0 - rule is visible starting from version 'visibility' | |
95 | * <= 0 - rule is invisible starting from version '-(visibility)' | |
96 | * | |
97 | * The minimum version number used in lookups is 1 (== CLS_NO_VERSION), | |
98 | * which implies that when 'visibility' is: | |
99 | * | |
100 | * 1 - rule is visible in all lookup versions | |
101 | * 0 - rule is invisible in all lookup versions. */ | |
102 | atomic_llong visibility; | |
103 | ||
f80028fe JR |
104 | const struct cls_rule *cls_rule; |
105 | const struct miniflow flow; /* Matching rule. Mask is in the subtable. */ | |
38c449e0 JR |
106 | /* 'flow' must be the last field. */ |
107 | }; | |
108 | ||
8f8023b3 JR |
109 | /* Must be RCU postponed. */ |
110 | void cls_match_free_cb(struct cls_match *); | |
111 | ||
2b7b1427 JR |
112 | static inline void |
113 | cls_match_set_visibility(struct cls_match *rule, long long version) | |
114 | { | |
115 | atomic_store_relaxed(&rule->visibility, version); | |
116 | } | |
117 | ||
118 | static inline bool | |
119 | cls_match_visible_in_version(const struct cls_match *rule, long long version) | |
120 | { | |
121 | long long visibility; | |
122 | ||
123 | /* C11 does not want to access an atomic via a const object pointer. */ | |
124 | atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->visibility, | |
125 | &visibility); | |
126 | ||
127 | if (OVS_LIKELY(visibility > 0)) { | |
128 | /* Rule is visible starting from version 'visibility'. */ | |
129 | return version >= visibility; | |
130 | } else { | |
131 | /* Rule is invisible starting from version '-visibility'. */ | |
132 | return version < -visibility; | |
133 | } | |
134 | } | |
135 | ||
136 | static inline bool | |
137 | cls_match_is_eventually_invisible(const struct cls_match *rule) | |
138 | { | |
139 | long long visibility; | |
140 | ||
141 | /* C11 does not want to access an atomic via a const object pointer. */ | |
142 | atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->visibility, | |
143 | &visibility); | |
144 | ||
145 | return visibility <= 0; | |
146 | } | |
147 | ||
8f8023b3 JR |
148 | \f |
149 | /* cls_match 'next' */ | |
150 | ||
151 | static inline const struct cls_match * | |
152 | cls_match_next(const struct cls_match *rule) | |
153 | { | |
154 | return ovsrcu_get(struct cls_match *, &rule->next); | |
155 | } | |
156 | ||
157 | static inline struct cls_match * | |
158 | cls_match_next_protected(const struct cls_match *rule) | |
159 | { | |
160 | return ovsrcu_get_protected(struct cls_match *, &rule->next); | |
161 | } | |
162 | ||
163 | /* Puts 'rule' in the position between 'prev' and 'next'. If 'prev' == NULL, | |
164 | * then the 'rule' is the new list head, and if 'next' == NULL, the rule is the | |
165 | * new list tail. | |
166 | * If there are any nodes between 'prev' and 'next', they are dropped from the | |
167 | * list. */ | |
168 | static inline void | |
169 | cls_match_insert(struct cls_match *prev, struct cls_match *next, | |
170 | struct cls_match *rule) | |
171 | { | |
172 | ovsrcu_set_hidden(&rule->next, next); | |
173 | ||
174 | if (prev) { | |
175 | ovsrcu_set(&prev->next, rule); | |
176 | } | |
177 | } | |
178 | ||
179 | /* Puts 'new_rule' in the position of 'old_rule', which is the next node after | |
180 | * 'prev'. If 'prev' == NULL, then the 'new_rule' is the new list head. | |
181 | * | |
182 | * The replaced cls_match still links to the later rules, and may still be | |
183 | * referenced by other threads until all other threads quiesce. The replaced | |
184 | * rule may not be re-inserted, re-initialized, or deleted until after all | |
185 | * other threads have quiesced (use ovsrcu_postpone). */ | |
186 | static inline void | |
187 | cls_match_replace(struct cls_match *prev, | |
188 | struct cls_match *old_rule, struct cls_match *new_rule) | |
189 | { | |
190 | cls_match_insert(prev, cls_match_next_protected(old_rule), new_rule); | |
191 | } | |
192 | ||
193 | /* Removes 'rule' following 'prev' from the list. If 'prev' is NULL, then the | |
194 | * 'rule' is a list head, and the caller is responsible for maintaining its | |
195 | * list head pointer (if any). | |
196 | * | |
197 | * Afterward, the removed rule is not linked to any more, but still links to | |
198 | * the following rules, and may still be referenced by other threads until all | |
199 | * other threads quiesce. The removed rule may not be re-inserted, | |
200 | * re-initialized, or deleted until after all other threads have quiesced (use | |
201 | * ovsrcu_postpone). | |
202 | */ | |
203 | static inline void | |
204 | cls_match_remove(struct cls_match *prev, struct cls_match *rule) | |
205 | { | |
206 | if (prev) { | |
207 | ovsrcu_set(&prev->next, cls_match_next_protected(rule)); | |
208 | } | |
209 | } | |
210 | ||
211 | #define CLS_MATCH_FOR_EACH(ITER, HEAD) \ | |
212 | for ((ITER) = (HEAD); (ITER); (ITER) = cls_match_next(ITER)) | |
213 | ||
214 | #define CLS_MATCH_FOR_EACH_AFTER_HEAD(ITER, HEAD) \ | |
215 | CLS_MATCH_FOR_EACH(ITER, cls_match_next(HEAD)) | |
216 | ||
217 | /* Iterate cls_matches keeping the previous pointer for modifications. */ | |
218 | #define FOR_EACH_RULE_IN_LIST_PROTECTED(ITER, PREV, HEAD) \ | |
219 | for ((PREV) = NULL, (ITER) = (HEAD); \ | |
220 | (ITER); \ | |
221 | (PREV) = (ITER), (ITER) = cls_match_next_protected(ITER)) | |
222 | ||
223 | \f | |
38c449e0 JR |
224 | /* A longest-prefix match tree. */ |
225 | struct trie_node { | |
226 | uint32_t prefix; /* Prefix bits for this node, MSB first. */ | |
227 | uint8_t n_bits; /* Never zero, except for the root node. */ | |
228 | unsigned int n_rules; /* Number of rules that have this prefix. */ | |
229 | rcu_trie_ptr edges[2]; /* Both NULL if leaf. */ | |
230 | }; | |
231 | ||
232 | /* Max bits per node. Must fit in struct trie_node's 'prefix'. | |
233 | * Also tested with 16, 8, and 5 to stress the implementation. */ | |
234 | #define TRIE_PREFIX_BITS 32 | |
235 | \f | |
236 | /* flow/miniflow/minimask/minimatch utilities. | |
237 | * These are only used by the classifier, so place them here to allow | |
238 | * for better optimization. */ | |
239 | ||
240 | static inline uint64_t | |
241 | miniflow_get_map_in_range(const struct miniflow *miniflow, | |
242 | uint8_t start, uint8_t end, unsigned int *offset) | |
243 | { | |
244 | uint64_t map = miniflow->map; | |
245 | *offset = 0; | |
246 | ||
247 | if (start > 0) { | |
248 | uint64_t msk = (UINT64_C(1) << start) - 1; /* 'start' LSBs set */ | |
249 | *offset = count_1bits(map & msk); | |
250 | map &= ~msk; | |
251 | } | |
d70e8c28 | 252 | if (end < FLOW_U64S) { |
38c449e0 JR |
253 | uint64_t msk = (UINT64_C(1) << end) - 1; /* 'end' LSBs set */ |
254 | map &= msk; | |
255 | } | |
256 | return map; | |
257 | } | |
258 | ||
259 | /* Returns a hash value for the bits of 'flow' where there are 1-bits in | |
260 | * 'mask', given 'basis'. | |
261 | * | |
262 | * The hash values returned by this function are the same as those returned by | |
263 | * miniflow_hash_in_minimask(), only the form of the arguments differ. */ | |
264 | static inline uint32_t | |
265 | flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask, | |
266 | uint32_t basis) | |
267 | { | |
d70e8c28 JR |
268 | const uint64_t *mask_values = miniflow_get_values(&mask->masks); |
269 | const uint64_t *flow_u64 = (const uint64_t *)flow; | |
270 | const uint64_t *p = mask_values; | |
38c449e0 | 271 | uint32_t hash; |
1cea007c | 272 | int idx; |
38c449e0 JR |
273 | |
274 | hash = basis; | |
1cea007c | 275 | MAP_FOR_EACH_INDEX(idx, mask->masks.map) { |
d70e8c28 | 276 | hash = hash_add64(hash, flow_u64[idx] & *p++); |
38c449e0 JR |
277 | } |
278 | ||
d70e8c28 | 279 | return hash_finish(hash, (p - mask_values) * 8); |
38c449e0 JR |
280 | } |
281 | ||
282 | /* Returns a hash value for the bits of 'flow' where there are 1-bits in | |
283 | * 'mask', given 'basis'. | |
284 | * | |
285 | * The hash values returned by this function are the same as those returned by | |
286 | * flow_hash_in_minimask(), only the form of the arguments differ. */ | |
287 | static inline uint32_t | |
288 | miniflow_hash_in_minimask(const struct miniflow *flow, | |
289 | const struct minimask *mask, uint32_t basis) | |
290 | { | |
d70e8c28 JR |
291 | const uint64_t *mask_values = miniflow_get_values(&mask->masks); |
292 | const uint64_t *p = mask_values; | |
38c449e0 | 293 | uint32_t hash = basis; |
d70e8c28 | 294 | uint64_t flow_u64; |
38c449e0 | 295 | |
d70e8c28 JR |
296 | MINIFLOW_FOR_EACH_IN_MAP(flow_u64, flow, mask->masks.map) { |
297 | hash = hash_add64(hash, flow_u64 & *p++); | |
38c449e0 JR |
298 | } |
299 | ||
d70e8c28 | 300 | return hash_finish(hash, (p - mask_values) * 8); |
38c449e0 JR |
301 | } |
302 | ||
303 | /* Returns a hash value for the bits of range [start, end) in 'flow', | |
304 | * where there are 1-bits in 'mask', given 'hash'. | |
305 | * | |
306 | * The hash values returned by this function are the same as those returned by | |
307 | * minimatch_hash_range(), only the form of the arguments differ. */ | |
308 | static inline uint32_t | |
309 | flow_hash_in_minimask_range(const struct flow *flow, | |
310 | const struct minimask *mask, | |
311 | uint8_t start, uint8_t end, uint32_t *basis) | |
312 | { | |
d70e8c28 JR |
313 | const uint64_t *mask_values = miniflow_get_values(&mask->masks); |
314 | const uint64_t *flow_u64 = (const uint64_t *)flow; | |
38c449e0 | 315 | unsigned int offset; |
a1235ee5 | 316 | uint64_t map; |
d70e8c28 | 317 | const uint64_t *p; |
38c449e0 | 318 | uint32_t hash = *basis; |
1cea007c | 319 | int idx; |
38c449e0 | 320 | |
a1235ee5 TG |
321 | map = miniflow_get_map_in_range(&mask->masks, start, end, &offset); |
322 | p = mask_values + offset; | |
1cea007c | 323 | MAP_FOR_EACH_INDEX(idx, map) { |
d70e8c28 | 324 | hash = hash_add64(hash, flow_u64[idx] & *p++); |
38c449e0 JR |
325 | } |
326 | ||
327 | *basis = hash; /* Allow continuation from the unfinished value. */ | |
d70e8c28 | 328 | return hash_finish(hash, (p - mask_values) * 8); |
38c449e0 JR |
329 | } |
330 | ||
331 | /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */ | |
332 | static inline void | |
333 | flow_wildcards_fold_minimask(struct flow_wildcards *wc, | |
334 | const struct minimask *mask) | |
335 | { | |
336 | flow_union_with_miniflow(&wc->masks, &mask->masks); | |
337 | } | |
338 | ||
339 | /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask | |
340 | * in range [start, end). */ | |
341 | static inline void | |
342 | flow_wildcards_fold_minimask_range(struct flow_wildcards *wc, | |
343 | const struct minimask *mask, | |
344 | uint8_t start, uint8_t end) | |
345 | { | |
d70e8c28 | 346 | uint64_t *dst_u64 = (uint64_t *)&wc->masks; |
38c449e0 | 347 | unsigned int offset; |
a1235ee5 | 348 | uint64_t map; |
d70e8c28 | 349 | const uint64_t *p; |
1cea007c | 350 | int idx; |
38c449e0 | 351 | |
a1235ee5 | 352 | map = miniflow_get_map_in_range(&mask->masks, start, end, &offset); |
d70e8c28 | 353 | p = miniflow_get_values(&mask->masks) + offset; |
1cea007c | 354 | MAP_FOR_EACH_INDEX(idx, map) { |
d70e8c28 | 355 | dst_u64[idx] |= *p++; |
38c449e0 JR |
356 | } |
357 | } | |
358 | ||
359 | /* Returns a hash value for 'flow', given 'basis'. */ | |
360 | static inline uint32_t | |
361 | miniflow_hash(const struct miniflow *flow, uint32_t basis) | |
362 | { | |
d70e8c28 JR |
363 | const uint64_t *values = miniflow_get_values(flow); |
364 | const uint64_t *p = values; | |
38c449e0 JR |
365 | uint32_t hash = basis; |
366 | uint64_t hash_map = 0; | |
367 | uint64_t map; | |
368 | ||
369 | for (map = flow->map; map; map = zero_rightmost_1bit(map)) { | |
370 | if (*p) { | |
d70e8c28 | 371 | hash = hash_add64(hash, *p); |
38c449e0 JR |
372 | hash_map |= rightmost_1bit(map); |
373 | } | |
374 | p++; | |
375 | } | |
aae7c34f | 376 | hash = hash_add64(hash, hash_map); |
38c449e0 JR |
377 | |
378 | return hash_finish(hash, p - values); | |
379 | } | |
380 | ||
381 | /* Returns a hash value for 'mask', given 'basis'. */ | |
382 | static inline uint32_t | |
383 | minimask_hash(const struct minimask *mask, uint32_t basis) | |
384 | { | |
385 | return miniflow_hash(&mask->masks, basis); | |
386 | } | |
387 | ||
388 | /* Returns a hash value for 'match', given 'basis'. */ | |
389 | static inline uint32_t | |
390 | minimatch_hash(const struct minimatch *match, uint32_t basis) | |
391 | { | |
392 | return miniflow_hash(&match->flow, minimask_hash(&match->mask, basis)); | |
393 | } | |
394 | ||
395 | /* Returns a hash value for the bits of range [start, end) in 'minimatch', | |
396 | * given 'basis'. | |
397 | * | |
398 | * The hash values returned by this function are the same as those returned by | |
399 | * flow_hash_in_minimask_range(), only the form of the arguments differ. */ | |
400 | static inline uint32_t | |
401 | minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end, | |
402 | uint32_t *basis) | |
403 | { | |
404 | unsigned int offset; | |
d70e8c28 | 405 | const uint64_t *p, *q; |
38c449e0 JR |
406 | uint32_t hash = *basis; |
407 | int n, i; | |
408 | ||
409 | n = count_1bits(miniflow_get_map_in_range(&match->mask.masks, start, end, | |
410 | &offset)); | |
d70e8c28 JR |
411 | q = miniflow_get_values(&match->mask.masks) + offset; |
412 | p = miniflow_get_values(&match->flow) + offset; | |
38c449e0 JR |
413 | |
414 | for (i = 0; i < n; i++) { | |
d70e8c28 | 415 | hash = hash_add64(hash, p[i] & q[i]); |
38c449e0 JR |
416 | } |
417 | *basis = hash; /* Allow continuation from the unfinished value. */ | |
d70e8c28 | 418 | return hash_finish(hash, (offset + n) * 8); |
38c449e0 JR |
419 | } |
420 | ||
421 | #endif |