2 * Copyright (c) 2014, 2015 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef CLASSIFIER_PRIVATE_H
18 #define CLASSIFIER_PRIVATE_H 1
25 /* Classifier internal definitions, subject to change at any time. */
27 /* A set of rules that all have the same fields wildcarded. */
29 struct cmap_node cmap_node
; /* Within classifier's 'subtables_map'. */
31 /* These fields are only used by writers. */
32 int max_priority
; /* Max priority of any rule in subtable. */
33 unsigned int max_count
; /* Count of max_priority rules. */
35 /* Accessed by iterators. */
36 struct rculist rules_list
; /* Unordered. */
38 /* Identical, but lower priority rules are not inserted to any of the
39 * following data structures. */
41 /* These fields are accessed by readers who care about wildcarding. */
42 const uint8_t n_indices
; /* How many indices to use. */
43 const struct flowmap index_maps
[CLS_MAX_INDICES
+ 1]; /* Stage maps. */
44 unsigned int trie_plen
[CLS_MAX_TRIES
]; /* Trie prefix length in 'mask'
45 * (runtime configurable). */
46 const int ports_mask_len
;
47 struct cmap indices
[CLS_MAX_INDICES
]; /* Staged lookup indices. */
48 rcu_trie_ptr ports_trie
; /* NULL if none. */
50 /* These fields are accessed by all readers. */
51 struct cmap rules
; /* Contains 'cls_match'es. */
52 const struct minimask mask
; /* Wildcards for fields. */
53 /* 'mask' must be the last field. */
56 /* Internal representation of a rule in a "struct cls_subtable".
58 * The 'next' member is an element in a singly linked, null-terminated list.
59 * This list links together identical "cls_match"es in order of decreasing
60 * priority. The classifier code maintains the invariant that at most one rule
61 * of a given priority is visible for any given lookup version.
64 /* Accessed by everybody. */
65 OVSRCU_TYPE(struct cls_match
*) next
; /* Equal, lower-priority matches. */
66 OVSRCU_TYPE(struct cls_conjunction_set
*) conj_set
;
68 /* Accessed by readers interested in wildcarding. */
69 const int priority
; /* Larger numbers are higher priorities. */
70 struct cmap_node index_nodes
[CLS_MAX_INDICES
]; /* Within subtable's
72 /* Accessed by all readers. */
73 struct cmap_node cmap_node
; /* Within struct cls_subtable 'rules'. */
77 * CLS_NOT_REMOVED_VERSION has a special meaning for 'remove_version',
78 * meaning that the rule has been added but not yet removed.
80 const cls_version_t add_version
; /* Version rule was added in. */
81 ATOMIC(cls_version_t
) remove_version
; /* Version rule is removed in. */
83 const struct cls_rule
*cls_rule
;
84 const struct miniflow flow
; /* Matching rule. Mask is in the subtable. */
85 /* 'flow' must be the last field. */
88 /* Must be RCU postponed. */
89 void cls_match_free_cb(struct cls_match
*);
92 cls_match_set_remove_version(struct cls_match
*rule
, cls_version_t version
)
94 atomic_store_relaxed(&rule
->remove_version
, version
);
98 cls_match_visible_in_version(const struct cls_match
*rule
,
99 cls_version_t version
)
101 cls_version_t remove_version
;
103 /* C11 does not want to access an atomic via a const object pointer. */
104 atomic_read_relaxed(&CONST_CAST(struct cls_match
*, rule
)->remove_version
,
107 return rule
->add_version
<= version
&& version
< remove_version
;
111 cls_match_is_eventually_invisible(const struct cls_match
*rule
)
113 cls_version_t remove_version
;
115 /* C11 does not want to access an atomic via a const object pointer. */
116 atomic_read_relaxed(&CONST_CAST(struct cls_match
*, rule
)->remove_version
,
119 return remove_version
<= CLS_MAX_VERSION
;
123 /* cls_match 'next' */
125 static inline const struct cls_match
*
126 cls_match_next(const struct cls_match
*rule
)
128 return ovsrcu_get(struct cls_match
*, &rule
->next
);
131 static inline struct cls_match
*
132 cls_match_next_protected(const struct cls_match
*rule
)
134 return ovsrcu_get_protected(struct cls_match
*, &rule
->next
);
137 /* Puts 'rule' in the position between 'prev' and 'next'. If 'prev' == NULL,
138 * then the 'rule' is the new list head, and if 'next' == NULL, the rule is the
140 * If there are any nodes between 'prev' and 'next', they are dropped from the
143 cls_match_insert(struct cls_match
*prev
, struct cls_match
*next
,
144 struct cls_match
*rule
)
146 ovsrcu_set_hidden(&rule
->next
, next
);
149 ovsrcu_set(&prev
->next
, rule
);
153 /* Puts 'new_rule' in the position of 'old_rule', which is the next node after
154 * 'prev'. If 'prev' == NULL, then the 'new_rule' is the new list head.
156 * The replaced cls_match still links to the later rules, and may still be
157 * referenced by other threads until all other threads quiesce. The replaced
158 * rule may not be re-inserted, re-initialized, or deleted until after all
159 * other threads have quiesced (use ovsrcu_postpone). */
161 cls_match_replace(struct cls_match
*prev
,
162 struct cls_match
*old_rule
, struct cls_match
*new_rule
)
164 cls_match_insert(prev
, cls_match_next_protected(old_rule
), new_rule
);
167 /* Removes 'rule' following 'prev' from the list. If 'prev' is NULL, then the
168 * 'rule' is a list head, and the caller is responsible for maintaining its
169 * list head pointer (if any).
171 * Afterward, the removed rule is not linked to any more, but still links to
172 * the following rules, and may still be referenced by other threads until all
173 * other threads quiesce. The removed rule may not be re-inserted,
174 * re-initialized, or deleted until after all other threads have quiesced (use
178 cls_match_remove(struct cls_match
*prev
, struct cls_match
*rule
)
181 ovsrcu_set(&prev
->next
, cls_match_next_protected(rule
));
185 #define CLS_MATCH_FOR_EACH(ITER, HEAD) \
186 for ((ITER) = (HEAD); (ITER); (ITER) = cls_match_next(ITER))
188 #define CLS_MATCH_FOR_EACH_AFTER_HEAD(ITER, HEAD) \
189 CLS_MATCH_FOR_EACH(ITER, cls_match_next(HEAD))
191 /* Iterate cls_matches keeping the previous pointer for modifications. */
192 #define FOR_EACH_RULE_IN_LIST_PROTECTED(ITER, PREV, HEAD) \
193 for ((PREV) = NULL, (ITER) = (HEAD); \
195 (PREV) = (ITER), (ITER) = cls_match_next_protected(ITER))
198 /* A longest-prefix match tree. */
200 uint32_t prefix
; /* Prefix bits for this node, MSB first. */
201 uint8_t n_bits
; /* Never zero, except for the root node. */
202 unsigned int n_rules
; /* Number of rules that have this prefix. */
203 rcu_trie_ptr edges
[2]; /* Both NULL if leaf. */
206 /* Max bits per node. Must fit in struct trie_node's 'prefix'.
207 * Also tested with 16, 8, and 5 to stress the implementation. */
208 #define TRIE_PREFIX_BITS 32
210 /* flow/miniflow/minimask/minimatch utilities.
211 * These are only used by the classifier, so place them here to allow
212 * for better optimization. */
214 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
215 * 'mask', given 'basis'.
217 * The hash values returned by this function are the same as those returned by
218 * miniflow_hash_in_minimask(), only the form of the arguments differ. */
219 static inline uint32_t
220 flow_hash_in_minimask(const struct flow
*flow
, const struct minimask
*mask
,
223 const uint64_t *mask_values
= miniflow_get_values(&mask
->masks
);
224 const uint64_t *flow_u64
= (const uint64_t *)flow
;
225 const uint64_t *p
= mask_values
;
226 uint32_t hash
= basis
;
229 FLOWMAP_FOR_EACH_MAP (map
, mask
->masks
.map
) {
232 MAP_FOR_EACH_INDEX (idx
, map
) {
233 hash
= hash_add64(hash
, flow_u64
[idx
] & *p
++);
235 flow_u64
+= MAP_T_BITS
;
238 return hash_finish(hash
, (p
- mask_values
) * 8);
241 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
242 * 'mask', given 'basis'.
244 * The hash values returned by this function are the same as those returned by
245 * flow_hash_in_minimask(), only the form of the arguments differ. */
246 static inline uint32_t
247 miniflow_hash_in_minimask(const struct miniflow
*flow
,
248 const struct minimask
*mask
, uint32_t basis
)
250 const uint64_t *mask_values
= miniflow_get_values(&mask
->masks
);
251 const uint64_t *p
= mask_values
;
252 uint32_t hash
= basis
;
255 MINIFLOW_FOR_EACH_IN_FLOWMAP(value
, flow
, mask
->masks
.map
) {
256 hash
= hash_add64(hash
, value
& *p
++);
259 return hash_finish(hash
, (p
- mask_values
) * 8);
262 /* Returns a hash value for the values of 'flow', indicated by 'range', where
263 * there are 1-bits in 'mask', given 'basis'. 'range' must be a continuous
264 * subset of the bits in 'mask''s map, representing a continuous range of the
265 * minimask's mask data. '*offset' must be the number of 64-bit units of the
266 * minimask's data to skip to get to the first unit covered by 'range'. On
267 * return '*offset' is updated with the number of 64-bit units of the minimask
270 * Typically this function is called for successive ranges of minimask's masks,
271 * and the first invocation passes '*offset' as zero.
273 * The hash values returned by this function are the same as those returned by
274 * minimatch_hash_range(), only the form of the arguments differ. */
275 static inline uint32_t
276 flow_hash_in_minimask_range(const struct flow
*flow
,
277 const struct minimask
*mask
,
278 const struct flowmap range
,
279 unsigned int *offset
,
282 const uint64_t *mask_values
= miniflow_get_values(&mask
->masks
);
283 const uint64_t *flow_u64
= (const uint64_t *)flow
;
284 const uint64_t *p
= mask_values
+ *offset
;
285 uint32_t hash
= *basis
;
288 FLOWMAP_FOR_EACH_MAP (map
, range
) {
291 MAP_FOR_EACH_INDEX (idx
, map
) {
292 hash
= hash_add64(hash
, flow_u64
[idx
] & *p
++);
294 flow_u64
+= MAP_T_BITS
;
297 *basis
= hash
; /* Allow continuation from the unfinished value. */
298 *offset
= p
- mask_values
;
299 return hash_finish(hash
, *offset
* 8);
302 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
304 flow_wildcards_fold_minimask(struct flow_wildcards
*wc
,
305 const struct minimask
*mask
)
307 flow_union_with_miniflow(&wc
->masks
, &mask
->masks
);
310 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask for bits in
311 * 'fmap'. 1-bits in 'fmap' are a subset of 1-bits in 'mask''s map. */
313 flow_wildcards_fold_minimask_in_map(struct flow_wildcards
*wc
,
314 const struct minimask
*mask
,
315 const struct flowmap fmap
)
317 flow_union_with_miniflow_subset(&wc
->masks
, &mask
->masks
, fmap
);
320 /* Returns a hash value for 'mask', given 'basis'. */
321 static inline uint32_t
322 minimask_hash(const struct minimask
*mask
, uint32_t basis
)
324 const uint64_t *p
= miniflow_get_values(&mask
->masks
);
325 size_t n_values
= miniflow_n_values(&mask
->masks
);
326 uint32_t hash
= basis
;
328 for (size_t i
= 0; i
< n_values
; i
++) {
329 hash
= hash_add64(hash
, *p
++);
333 FLOWMAP_FOR_EACH_MAP (map
, mask
->masks
.map
) {
334 hash
= hash_add64(hash
, map
);
337 return hash_finish(hash
, n_values
);
340 /* Returns a hash value for the values of 'match->flow', indicated by 'range',
341 * where there are 1-bits in 'match->mask', given 'basis'. 'range' must be a
342 * continuous subset of the bits in the map of 'match', representing a
343 * continuous range of the mask data of 'match'. '*offset' must be the number
344 * of 64-bit units of the match data to skip to get to the first unit covered
345 * by 'range'. On return '*offset' is updated with the number of 64-bit units
346 * of the match consumed.
348 * Typically this function is called for successive ranges of minimask's masks,
349 * and the first invocation passes '*offset' as zero.
351 * The hash values returned by this function are the same as those returned by
352 * flow_hash_in_minimask_range(), only the form of the arguments differ. */
353 static inline uint32_t
354 minimatch_hash_range(const struct minimatch
*match
,
355 const struct flowmap range
, unsigned int *offset
,
358 const uint64_t *p
= miniflow_get_values(match
->flow
) + *offset
;
359 const uint64_t *q
= miniflow_get_values(&match
->mask
->masks
) + *offset
;
360 unsigned int n
= flowmap_n_1bits(range
);
361 uint32_t hash
= *basis
;
363 for (unsigned int i
= 0; i
< n
; i
++) {
364 hash
= hash_add64(hash
, p
[i
] & q
[i
]);
366 *basis
= hash
; /* Allow continuation from the unfinished value. */
368 return hash_finish(hash
, *offset
* 8);