]>
git.proxmox.com Git - ovs.git/blob - lib/classifier-private.h
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 /* Accessed by everybody. */
71 struct rculist list
; /* Identical, lower-priority "cls_match"es. */
73 /* Accessed only by writers. */
74 struct cls_partition
*partition
;
76 /* Accessed by readers interested in wildcarding. */
77 const int priority
; /* Larger numbers are higher priorities. */
78 struct cmap_node index_nodes
[CLS_MAX_INDICES
]; /* Within subtable's
80 /* Accessed by all readers. */
81 struct cmap_node cmap_node
; /* Within struct cls_subtable 'rules'. */
83 const struct cls_rule
*cls_rule
;
84 OVSRCU_TYPE(struct cls_conjunction_set
*) conj_set
;
85 const struct miniflow flow
; /* Matching rule. Mask is in the subtable. */
86 /* 'flow' must be the last field. */
89 /* A longest-prefix match tree. */
91 uint32_t prefix
; /* Prefix bits for this node, MSB first. */
92 uint8_t n_bits
; /* Never zero, except for the root node. */
93 unsigned int n_rules
; /* Number of rules that have this prefix. */
94 rcu_trie_ptr edges
[2]; /* Both NULL if leaf. */
97 /* Max bits per node. Must fit in struct trie_node's 'prefix'.
98 * Also tested with 16, 8, and 5 to stress the implementation. */
99 #define TRIE_PREFIX_BITS 32
101 /* flow/miniflow/minimask/minimatch utilities.
102 * These are only used by the classifier, so place them here to allow
103 * for better optimization. */
105 static inline uint64_t
106 miniflow_get_map_in_range(const struct miniflow
*miniflow
,
107 uint8_t start
, uint8_t end
, unsigned int *offset
)
109 uint64_t map
= miniflow
->map
;
113 uint64_t msk
= (UINT64_C(1) << start
) - 1; /* 'start' LSBs set */
114 *offset
= count_1bits(map
& msk
);
117 if (end
< FLOW_U64S
) {
118 uint64_t msk
= (UINT64_C(1) << end
) - 1; /* 'end' LSBs set */
124 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
125 * 'mask', given 'basis'.
127 * The hash values returned by this function are the same as those returned by
128 * miniflow_hash_in_minimask(), only the form of the arguments differ. */
129 static inline uint32_t
130 flow_hash_in_minimask(const struct flow
*flow
, const struct minimask
*mask
,
133 const uint64_t *mask_values
= miniflow_get_values(&mask
->masks
);
134 const uint64_t *flow_u64
= (const uint64_t *)flow
;
135 const uint64_t *p
= mask_values
;
140 MAP_FOR_EACH_INDEX(idx
, mask
->masks
.map
) {
141 hash
= hash_add64(hash
, flow_u64
[idx
] & *p
++);
144 return hash_finish(hash
, (p
- mask_values
) * 8);
147 /* Returns a hash value for the bits of 'flow' where there are 1-bits in
148 * 'mask', given 'basis'.
150 * The hash values returned by this function are the same as those returned by
151 * flow_hash_in_minimask(), only the form of the arguments differ. */
152 static inline uint32_t
153 miniflow_hash_in_minimask(const struct miniflow
*flow
,
154 const struct minimask
*mask
, uint32_t basis
)
156 const uint64_t *mask_values
= miniflow_get_values(&mask
->masks
);
157 const uint64_t *p
= mask_values
;
158 uint32_t hash
= basis
;
161 MINIFLOW_FOR_EACH_IN_MAP(flow_u64
, flow
, mask
->masks
.map
) {
162 hash
= hash_add64(hash
, flow_u64
& *p
++);
165 return hash_finish(hash
, (p
- mask_values
) * 8);
168 /* Returns a hash value for the bits of range [start, end) in 'flow',
169 * where there are 1-bits in 'mask', given 'hash'.
171 * The hash values returned by this function are the same as those returned by
172 * minimatch_hash_range(), only the form of the arguments differ. */
173 static inline uint32_t
174 flow_hash_in_minimask_range(const struct flow
*flow
,
175 const struct minimask
*mask
,
176 uint8_t start
, uint8_t end
, uint32_t *basis
)
178 const uint64_t *mask_values
= miniflow_get_values(&mask
->masks
);
179 const uint64_t *flow_u64
= (const uint64_t *)flow
;
183 uint32_t hash
= *basis
;
186 map
= miniflow_get_map_in_range(&mask
->masks
, start
, end
, &offset
);
187 p
= mask_values
+ offset
;
188 MAP_FOR_EACH_INDEX(idx
, map
) {
189 hash
= hash_add64(hash
, flow_u64
[idx
] & *p
++);
192 *basis
= hash
; /* Allow continuation from the unfinished value. */
193 return hash_finish(hash
, (p
- mask_values
) * 8);
196 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
198 flow_wildcards_fold_minimask(struct flow_wildcards
*wc
,
199 const struct minimask
*mask
)
201 flow_union_with_miniflow(&wc
->masks
, &mask
->masks
);
204 /* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask
205 * in range [start, end). */
207 flow_wildcards_fold_minimask_range(struct flow_wildcards
*wc
,
208 const struct minimask
*mask
,
209 uint8_t start
, uint8_t end
)
211 uint64_t *dst_u64
= (uint64_t *)&wc
->masks
;
217 map
= miniflow_get_map_in_range(&mask
->masks
, start
, end
, &offset
);
218 p
= miniflow_get_values(&mask
->masks
) + offset
;
219 MAP_FOR_EACH_INDEX(idx
, map
) {
220 dst_u64
[idx
] |= *p
++;
224 /* Returns a hash value for 'flow', given 'basis'. */
225 static inline uint32_t
226 miniflow_hash(const struct miniflow
*flow
, uint32_t basis
)
228 const uint64_t *values
= miniflow_get_values(flow
);
229 const uint64_t *p
= values
;
230 uint32_t hash
= basis
;
231 uint64_t hash_map
= 0;
234 for (map
= flow
->map
; map
; map
= zero_rightmost_1bit(map
)) {
236 hash
= hash_add64(hash
, *p
);
237 hash_map
|= rightmost_1bit(map
);
241 hash
= hash_add64(hash
, hash_map
);
243 return hash_finish(hash
, p
- values
);
246 /* Returns a hash value for 'mask', given 'basis'. */
247 static inline uint32_t
248 minimask_hash(const struct minimask
*mask
, uint32_t basis
)
250 return miniflow_hash(&mask
->masks
, basis
);
253 /* Returns a hash value for 'match', given 'basis'. */
254 static inline uint32_t
255 minimatch_hash(const struct minimatch
*match
, uint32_t basis
)
257 return miniflow_hash(&match
->flow
, minimask_hash(&match
->mask
, basis
));
260 /* Returns a hash value for the bits of range [start, end) in 'minimatch',
263 * The hash values returned by this function are the same as those returned by
264 * flow_hash_in_minimask_range(), only the form of the arguments differ. */
265 static inline uint32_t
266 minimatch_hash_range(const struct minimatch
*match
, uint8_t start
, uint8_t end
,
270 const uint64_t *p
, *q
;
271 uint32_t hash
= *basis
;
274 n
= count_1bits(miniflow_get_map_in_range(&match
->mask
.masks
, start
, end
,
276 q
= miniflow_get_values(&match
->mask
.masks
) + offset
;
277 p
= miniflow_get_values(&match
->flow
) + offset
;
279 for (i
= 0; i
< n
; i
++) {
280 hash
= hash_add64(hash
, p
[i
] & q
[i
]);
282 *basis
= hash
; /* Allow continuation from the unfinished value. */
283 return hash_finish(hash
, (offset
+ n
) * 8);