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
26 /* Classifier internal definitions, subject to change at any time. */
28 /* A set of rules that all have the same fields wildcarded. */
30 struct cmap_node cmap_node; /* Within classifier's 'subtables_map'. */
32 /* These fields are only used by writers. */
33 int max_priority; /* Max priority of any rule in subtable. */
34 unsigned int max_count; /* Count of max_priority rules. */
36 /* Accessed by iterators. */
37 struct rculist rules_list; /* Unordered. */
39 /* Identical, but lower priority rules are not inserted to any of the
40 * following data structures. */
42 /* These fields are accessed by readers who care about wildcarding. */
43 const tag_type tag; /* Tag generated from mask for partitioning. */
44 const uint8_t n_indices; /* How many indices to use. */
45 const uint8_t index_ofs[CLS_MAX_INDICES]; /* u64 segment boundaries. */
46 unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask'
47 * (runtime configurable). */
48 const int ports_mask_len;
49 struct cmap indices[CLS_MAX_INDICES]; /* Staged lookup indices. */
50 rcu_trie_ptr ports_trie; /* NULL if none. */
52 /* These fields are accessed by all readers. */
53 struct cmap rules; /* Contains 'cls_match'es. */
54 const struct minimask mask; /* Wildcards for fields. */
55 /* 'mask' must be the last field. */
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
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. */
65 struct tag_tracker tracker; /* Tracks the bits in 'tags'. */
68 /* Internal representation of a rule in a "struct cls_subtable".
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.
76 /* Accessed by everybody. */
77 OVSRCU_TYPE(struct cls_match *) next; /* Equal, lower-priority matches. */
78 OVSRCU_TYPE(struct cls_conjunction_set *) conj_set;
80 /* Accessed only by writers. */
81 struct cls_partition *partition;
83 /* Accessed by readers interested in wildcarding. */
84 const int priority; /* Larger numbers are higher priorities. */
85 struct cmap_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's
87 /* Accessed by all readers. */
88 struct cmap_node cmap_node; /* Within struct cls_subtable 'rules'. */
92 * CLS_NOT_REMOVED_VERSION has a special meaning for 'remove_version',
93 * meaningthat the rule has been added but not yet removed.
95 const cls_version_t add_version; /* Version rule was added in. */
96 ATOMIC(cls_version_t) remove_version; /* Version rule is removed in. */
98 const struct cls_rule *cls_rule;
99 const struct miniflow flow; /* Matching rule. Mask is in the subtable. */
100 /* 'flow' must be the last field. */
103 /* Must be RCU postponed. */
104 void cls_match_free_cb(struct cls_match *);
107 cls_match_set_remove_version(struct cls_match *rule, cls_version_t version)
109 atomic_store_relaxed(&rule->remove_version, version);
113 cls_match_visible_in_version(const struct cls_match *rule,
114 cls_version_t version)
116 cls_version_t remove_version;
118 /* C11 does not want to access an atomic via a const object pointer. */
119 atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->remove_version,
122 return rule->add_version <= version && version < remove_version;
126 cls_match_is_eventually_invisible(const struct cls_match *rule)
128 cls_version_t remove_version;
130 /* C11 does not want to access an atomic via a const object pointer. */
131 atomic_read_relaxed(&CONST_CAST(struct cls_match *, rule)->remove_version,
134 return remove_version <= CLS_MAX_VERSION;
138 /* cls_match 'next' */
140 static inline const struct cls_match *
141 cls_match_next(const struct cls_match *rule)
143 return ovsrcu_get(struct cls_match *, &rule->next);
146 static inline struct cls_match *
147 cls_match_next_protected(const struct cls_match *rule)
149 return ovsrcu_get_protected(struct cls_match *, &rule->next);
152 /* Puts 'rule' in the position between 'prev' and 'next'. If 'prev' == NULL,
153 * then the 'rule' is the new list head, and if 'next' == NULL, the rule is the
155 * If there are any nodes between 'prev' and 'next', they are dropped from the
158 cls_match_insert(struct cls_match *prev, struct cls_match *next,
159 struct cls_match *rule)
161 ovsrcu_set_hidden(&rule->next, next);
164 ovsrcu_set(&prev->next, rule);
168 /* Puts 'new_rule' in the position of 'old_rule', which is the next node after
169 * 'prev'. If 'prev' == NULL, then the 'new_rule' is the new list head.
171 * The replaced cls_match still links to the later rules, and may still be
172 * referenced by other threads until all other threads quiesce. The replaced
173 * rule may not be re-inserted, re-initialized, or deleted until after all
174 * other threads have quiesced (use ovsrcu_postpone). */
176 cls_match_replace(struct cls_match *prev,
177 struct cls_match *old_rule, struct cls_match *new_rule)
179 cls_match_insert(prev, cls_match_next_protected(old_rule), new_rule);
182 /* Removes 'rule' following 'prev' from the list. If 'prev' is NULL, then the
183 * 'rule' is a list head, and the caller is responsible for maintaining its
184 * list head pointer (if any).
186 * Afterward, the removed rule is not linked to any more, but still links to
187 * the following rules, and may still be referenced by other threads until all
188 * other threads quiesce. The removed rule may not be re-inserted,
189 * re-initialized, or deleted until after all other threads have quiesced (use
193 cls_match_remove(struct cls_match *prev, struct cls_match *rule)
196 ovsrcu_set(&prev->next, cls_match_next_protected(rule));
200 #define CLS_MATCH_FOR_EACH(ITER, HEAD) \
201 for ((ITER) = (HEAD); (ITER); (ITER) = cls_match_next(ITER))
203 #define CLS_MATCH_FOR_EACH_AFTER_HEAD(ITER, HEAD) \
204 CLS_MATCH_FOR_EACH(ITER, cls_match_next(HEAD))
206 /* Iterate cls_matches keeping the previous pointer for modifications. */
207 #define FOR_EACH_RULE_IN_LIST_PROTECTED(ITER, PREV, HEAD) \
208 for ((PREV) = NULL, (ITER) = (HEAD); \
210 (PREV) = (ITER), (ITER) = cls_match_next_protected(ITER))
213 /* A longest-prefix match tree. */
215 uint32_t prefix; /* Prefix bits for this node, MSB first. */
216 uint8_t n_bits; /* Never zero, except for the root node. */
217 unsigned int n_rules; /* Number of rules that have this prefix. */
218 rcu_trie_ptr edges[2]; /* Both NULL if leaf. */
221 /* Max bits per node. Must fit in struct trie_node's 'prefix'.
222 * Also tested with 16, 8, and 5 to stress the implementation. */
223 #define TRIE_PREFIX_BITS 32
225 /* flow/miniflow/minimask/minimatch utilities.
226 * These are only used by the classifier, so place them here to allow
227 * for better optimization. */
229 /* Initializes 'map->tnl_map' and 'map->pkt_map' with a subset of 'miniflow'
230 * that includes only the portions with u64-offset 'i' such that start <= i <
231 * end. Does not copy any data from 'miniflow' to 'map'.
233 * TODO: Ensure that 'start' and 'end' are compile-time constants. */
234 static inline unsigned int /* offset */
235 miniflow_get_map_in_range(const struct miniflow *miniflow,
236 uint8_t start, uint8_t end, struct miniflow *map)
238 unsigned int offset = 0;
240 map->tnl_map = miniflow->tnl_map;
241 map->pkt_map = miniflow->pkt_map;
243 if (start >= FLOW_TNL_U64S) {
244 offset += count_1bits(map->tnl_map);
246 if (start > FLOW_TNL_U64S) {
247 /* Clear 'start - FLOW_TNL_U64S' LSBs from pkt_map. */
248 start -= FLOW_TNL_U64S;
249 uint64_t msk = (UINT64_C(1) << start) - 1;
251 offset += count_1bits(map->pkt_map & msk);
252 map->pkt_map &= ~msk;
254 } else if (start > 0) {
255 /* Clear 'start' LSBs from tnl_map. */
256 uint64_t msk = (UINT64_C(1) << start) - 1;
258 offset += count_1bits(map->tnl_map & msk);
259 map->tnl_map &= ~msk;
262 if (end <= FLOW_TNL_U64S) {
264 if (end < FLOW_TNL_U64S) {
265 /* Keep 'end' LSBs in tnl_map. */
266 map->tnl_map &= (UINT64_C(1) << end) - 1;
269 if (end < FLOW_U64S) {
270 /* Keep 'end - FLOW_TNL_U64S' LSBs in pkt_map. */
271 map->pkt_map &= (UINT64_C(1) << (end - FLOW_TNL_U64S)) - 1;
277 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
278 * 'mask', given 'basis'.
280 * The hash values returned by this function are the same as those returned by
281 * miniflow_hash_in_minimask(), only the form of the arguments differ. */
282 static inline uint32_t
283 flow_hash_in_minimask(const struct flow *flow, const struct minimask *mask,
286 const uint64_t *mask_values = miniflow_get_values(&mask->masks);
287 const uint64_t *flow_u64 = (const uint64_t *)flow;
288 const uint64_t *p = mask_values;
293 MAP_FOR_EACH_INDEX(idx, mask->masks.tnl_map) {
294 hash = hash_add64(hash, flow_u64[idx] & *p++);
296 flow_u64 += FLOW_TNL_U64S;
297 MAP_FOR_EACH_INDEX(idx, mask->masks.pkt_map) {
298 hash = hash_add64(hash, flow_u64[idx] & *p++);
301 return hash_finish(hash, (p - mask_values) * 8);
304 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
305 * 'mask', given 'basis'.
307 * The hash values returned by this function are the same as those returned by
308 * flow_hash_in_minimask(), only the form of the arguments differ. */
309 static inline uint32_t
310 miniflow_hash_in_minimask(const struct miniflow *flow,
311 const struct minimask *mask, uint32_t basis)
313 const uint64_t *mask_values = miniflow_get_values(&mask->masks);
314 const uint64_t *p = mask_values;
315 uint32_t hash = basis;
318 MINIFLOW_FOR_EACH_IN_TNL_MAP(flow_u64, flow, mask->masks) {
319 hash = hash_add64(hash, flow_u64 & *p++);
321 MINIFLOW_FOR_EACH_IN_PKT_MAP(flow_u64, flow, mask->masks) {
322 hash = hash_add64(hash, flow_u64 & *p++);
325 return hash_finish(hash, (p - mask_values) * 8);
328 /* Returns a hash value for the bits of range [start, end) in 'flow',
329 * where there are 1-bits in 'mask', given 'hash'.
331 * The hash values returned by this function are the same as those returned by
332 * minimatch_hash_range(), only the form of the arguments differ. */
333 static inline uint32_t
334 flow_hash_in_minimask_range(const struct flow *flow,
335 const struct minimask *mask,
336 uint8_t start, uint8_t end, uint32_t *basis)
338 const uint64_t *mask_values = miniflow_get_values(&mask->masks);
339 const uint64_t *flow_u64 = (const uint64_t *)flow;
343 uint32_t hash = *basis;
346 offset = miniflow_get_map_in_range(&mask->masks, start, end, &map);
347 p = mask_values + offset;
348 MAP_FOR_EACH_INDEX(idx, map.tnl_map) {
349 hash = hash_add64(hash, flow_u64[idx] & *p++);
351 flow_u64 += FLOW_TNL_U64S;
352 MAP_FOR_EACH_INDEX(idx, map.pkt_map) {
353 hash = hash_add64(hash, flow_u64[idx] & *p++);
356 *basis = hash; /* Allow continuation from the unfinished value. */
357 return hash_finish(hash, (p - mask_values) * 8);
360 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
362 flow_wildcards_fold_minimask(struct flow_wildcards *wc,
363 const struct minimask *mask)
365 flow_union_with_miniflow(&wc->masks, &mask->masks);
368 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask
369 * in range [start, end). */
371 flow_wildcards_fold_minimask_range(struct flow_wildcards *wc,
372 const struct minimask *mask,
373 uint8_t start, uint8_t end)
375 const uint64_t *p = miniflow_get_values(&mask->masks);
376 uint64_t *dst_u64 = (uint64_t *)&wc->masks;
380 p += miniflow_get_map_in_range(&mask->masks, start, end, &map);
381 MAP_FOR_EACH_INDEX(idx, map.tnl_map) {
382 dst_u64[idx] |= *p++;
384 dst_u64 += FLOW_TNL_U64S;
385 MAP_FOR_EACH_INDEX(idx, map.pkt_map) {
386 dst_u64[idx] |= *p++;
390 /* Returns a hash value for 'flow', given 'basis'. */
391 static inline uint32_t
392 miniflow_hash(const struct miniflow *flow, uint32_t basis)
394 const uint64_t *values = miniflow_get_values(flow);
395 const uint64_t *p = values;
396 uint32_t hash = basis;
397 uint64_t hash_tnl_map = 0, hash_pkt_map = 0;
400 for (map = flow->tnl_map; map; map = zero_rightmost_1bit(map)) {
402 hash = hash_add64(hash, *p);
403 hash_tnl_map |= rightmost_1bit(map);
407 for (map = flow->pkt_map; map; map = zero_rightmost_1bit(map)) {
409 hash = hash_add64(hash, *p);
410 hash_pkt_map |= rightmost_1bit(map);
414 hash = hash_add64(hash, hash_tnl_map);
415 hash = hash_add64(hash, hash_pkt_map);
417 return hash_finish(hash, p - values);
420 /* Returns a hash value for 'mask', given 'basis'. */
421 static inline uint32_t
422 minimask_hash(const struct minimask *mask, uint32_t basis)
424 return miniflow_hash(&mask->masks, basis);
427 /* Returns a hash value for the bits of range [start, end) in 'minimatch',
430 * The hash values returned by this function are the same as those returned by
431 * flow_hash_in_minimask_range(), only the form of the arguments differ. */
432 static inline uint32_t
433 minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end,
436 const uint64_t *p = miniflow_get_values(match->flow);
437 const uint64_t *q = miniflow_get_values(&match->mask->masks);
440 uint32_t hash = *basis;
443 offset = miniflow_get_map_in_range(&match->mask->masks, start, end, &map);
444 n = miniflow_n_values(&map);
449 for (i = 0; i < n; i++) {
450 hash = hash_add64(hash, p[i] & q[i]);
452 *basis = hash; /* Allow continuation from the unfinished value. */
453 return hash_finish(hash, (offset + n) * 8);